Метод штрафов ( М-метод)

В задачах линейного программирования в неравенствах (ограничениях), которые не содержат остаточных переменных, добавляются искусственные переменные -индекс ограничений, т.к. эти искусственные переменные не обладают физическим смыслом. Решение задачи строится таким образом, чтобы на последних итерациях переменные обратились в 0. Для этого в целевую функцию вводится штраф. Переменные умножаются на достаточно большое число m и добавляются в выражения целевой функции.

Вследствие этого штрафа естественно предположить, что процесс оптимизации приведет к 0 значениям искусственных переменных.

Пример:

В столбце решения у нас записано что оно=0, однако же используя новую целевую функцию при , входящее в базис решение должно быть равно 9М.

Перед началом симплекс-метода надо согласовать значения в F- строке. Это достигается с помощью линейного преобразования F-строки.

Новая -строка=старая +М