Метод больших штрафов

На этом шаге мы рассмотрим М-метод решения задач линейного программирования.

Пусть задача линейного программирования записана в стандартной форме. Для любого равенства i в котором не содержится дополнительная остаточная переменная, введем искусственную переменную R_i, которая далее войдет в начальное базисное решение. Но поскольку эта переменная искусственная (другими словами, не имеет никакого "физического смысла" в данной задаче), необходимо сделать так, чтобы на последующих итерациях она обратилась в нуль. Для этого в выражение целевой функции вводят штраф.

Переменная R_i, с помощью достаточно большого положительного числа М, штрафуется путем ввода в целевую функцию выражения –MR_i в случае максимизации целевой функции и выражения +MR_i — в случае минимизации. Вследствие этого штрафа естественно предположить, что процесс оптимизации симплекс-метода приведет к нулевому значению переменной R_i. Далее следует применить симплекс-метод.

При использовании М-метода следует обратить внимание на следующие два обстоятельства.

1. Использование штрафа М может и не привести к исключению искусственной переменной в конечной симплекс-итерации. Если исходная задача линейного программирования не имеет допустимого решения (например, система ограничений несовместна), тогда в конечной симплекс-итерации, по крайней мере, одна искусственная переменная будет иметь положительное значение. Это "индикатор" того, что задача не имеет допустимого решения.

2. Теоретически применение М-метода требует, чтобы М → ∞. Однако с точки зрения компьютерных вычислений величина М должна быть конечной и, вместе с тем, достаточно большой. Величина М должна быть настолько большой, чтобы выполнять роль "штрафа", но не слишком большой, чтобы не уменьшить точность вычислений. На практике вы должны помнить о возможных ошибках машинного округления при выполнении вычислений, в которых совместно участвуют как большие, так и малые числа.

На следующем шаге рассмотрим решение задачи линейного программирования М-методом.