Симплекс метод

x1+14x2= min

Определим минимальное значение целевой функции F(X) = 16x1 + 14x2 при следующих условиях-ограничений.

Умножим коэффициенты исходной функции на -1.

К левой части неравенства 1 системы ограничений прибавляем неотрицательную переменную x3 - преобразуем неравенство 1 в равенство.

К левой части неравенства 2 системы ограничений прибавляем неотрицательную переменную x4 - преобразуем неравенство 2 в равенство.

К левой части неравенства 3 системы ограничений прибавляем неотрицательную переменную x5 - преобразуем неравенство 3 в равенство.

Система ограничений приведена к каноническому виду, т.е. все условия системы представляют собой уравнения.

Наличие единичного базиса в системе ограничений позволяет легко найти начальное опорное решение. Рассмотрим подробнее:

Переменная x3 входит в уравнение 1 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x3 - базисная переменная.

Переменная x4 входит в уравнение 2 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x4 - базисная переменная.

Переменная x5 входит в уравнение 3 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x5 - базисная переменная.

Переменные, которые не являются базисными называются свободными переменными. Приравняв свободные переменные нулю в получившийся системе ограничений мы получим начальное опорное решение. нач = (0, 0, 220, 220, 240)

Функция G не должна содержать базисных переменных

Вернемся к рассмотрению функции G.

G = -16 x1-14 x2

Функция G не содержат базисных переменных.

Значение функции G для начального решения: G (X нач) = 0

Для составления начальной симплекс таблицы мы выполнили все условия.

В процессе дальнейших преобразований возможны два случая. Если в симплекс таблице, на каком то шаге, мы получим строку L состоящую из неотрицательных элементов - задача решена, мы нашли оптимальное решение. В противном случае - функция не является ограниченной.