Линейное программирование (стр. 5 из 8)
В случае минимизации целевой функции в этом алгоритме необходимо изменить только условие оптимальности: в качестве новой базисной переменной следует выбирать переменную, которая в
-уравнении имеет наибольший положительный коэффициент. Условия допустимости в обоих случаях одинаковы.4.2.3. Искусственное начальное решение
Для получения начального базисного решения мы использовали остаточные переменные. Однако когда исходное ограничение записано в виде равенства или имеет знак, нельзя сразу же получить НДБР. Поэтому были разработаны два метода, в которых используется «штрафование» искусственных переменных.
1. Метод больших штрафов (М-метод)
Рассмотрим линейную модель, приведённую к стандартной форме:
минимизировать
при ограничениях
В первом и втором уравнениях нет переменных, исполняющих роль остаточных. Поэтому введём в каждое из этих уравнений по одной из искусственных переменных R1 и R2:
За использование этих переменных в составе целевой функции можно ввести штраф, приписывая им достаточно большой положительный коэфффициент
. Получим линейную модель:минимизировать
при ограничениях
Теперь если
,то начальное допустимое решение:
Метод оптимизации, направленный на нахождение минимального значения
, приведёт к тому, что переменные R1 и R2 в оптимальном решении обратятся в нуль.Необходимо переформулировать условие задачи, чтобы представить процесс решения в удобной табличной форме. Подставив в целевую функцию полученные из соответствующих ограничений выражения для искусственных переменных
получим выражение для
: 
Решение представлено в сводной таблице:
2. Т.к. целевая функция минимизируется, переменные, включаемые в базис, должны иметь наибольшие положительные коэффициенты в
-уравнении. Оптимум достигается, когда все небазисные переменные имеют коэффициенты в -уравнении. Оптимальному решению соответствует точка 
.