Симплекс-метод. Анализ процедуры решения задачи линейного программирования (с примером).

Рассмотрим вычислительные и логические процедуры, обеспечивающие поиск решения задачи линейного программирования симплекс-методом. Процедуры поясняются в процессе решения конкретной задачи: найти совокупность значений , удовлетворяющих системе неравенств:

(3.1)

и условиям неотрицательности переменных , для которых

целевая функция

z=10+7x₁-5/3x₂ (3.2)

достигает максимума.

Преобразуем заданную форму задачи в каноническую, введя дополнительные переменные . Получим систему линейных уравнений (здесь дополнительные переменные составляют единичный базис):

(3.3)

и форму z: (3.4)

Выберем в качестве свободных (независимых) переменных и , так как через них выражена линейная форма; переменные , , , - базисные. Так как все величины должны быть неотрицательны, то их наименьшие значения равны нулю: , . Подставив эти значения в систему, получим следующие значения несвободных (базисных) переменных: . Эти значения также положительны, поэтому система значений ; ; образует допустимое базисное решение системы (3.3). При найденном решении значение z оказывается равным «-10».

Выше были приняты значения свободных переменных равными нулю (наименьшими при условии их неотрицательности). Попробуем за счёт их увеличения добиться уменьшения формы z.

Из выражения целевой функции видно, что, так как входит в неё со знаком плюс, то её увеличение может привести только к увеличению значения z. Неизвестная входит в неё со знаком минус, поэтому её увеличение «выгодно». Однако неограниченное увеличение этой свободной неизвестной может привести к отрицательности несвободных (базисных) неизвестных, то есть привести к недопустимому решению. Так, из первого уравнения видно, что, если станет больше двух ( остаётся свободной и равной нулю), то станет отрицательной. Таким образом, при , остальные переменные примут значения: , следовательно, получаем новое допустимое базисное решение. Теперь свободными стали и ; остальные – базисными. Проведя преобразования (выразив ограничения и линейную форму через новые свободные переменные) получим:

(3.5)

(3.6)

Соответствующее допустимое базисное решение:

; ;

Проведя аналогичные рассуждения, принимая во внимание, что входит в целевую функцию со знаком минус, на основе второго уравнения из системы (3.5) увеличиваем до значения = 6. При этом происходит ввод переменной в базис и вывод из него в качестве свободной. Получаем:

(3.7)

(3.8)

Теперь свободные неизвестные входят в выражение линейной формы со знаком плюс. Их увеличение может привести только к увеличению формы. Следовательно, базисное решение, являющееся оптимальным, имеет вид:

; ; ,

минимальное значение формы: , а максимальное значение .

Таким образом, идея симплекс-метода преобразования модели заключается в таком итеративном направленном переходе от одного допустимого базисного решения к другому, при котором последовательно улучшается значение линейной формы.