Задачи минимизации

Для решения задач минимизации можно использовать два подхода.

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

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

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