На этом шаге мы рассмотрим М-метод решения задач линейного программирования.
Пусть задача линейного программирования записана в стандартной форме. Для любого равенства i в котором не содержится дополнительная остаточная переменная, введем искусственную переменную Ri, которая далее войдет в начальное базисное решение. Но поскольку эта переменная искусственная (другими словами, не имеет никакого "физического смысла" в данной задаче), необходимо сделать так, чтобы на последующих итерациях она обратилась в нуль. Для этого в выражение целевой функции вводят штраф.
Переменная Ri, с помощью достаточно большого положительного числа М, штрафуется путем ввода в целевую функцию выражения –MRi в случае максимизации целевой функции и выражения +MRi — в случае минимизации. Вследствие этого штрафа естественно предположить, что процесс оптимизации симплекс-метода приведет к нулевому значению переменной Ri. Далее следует применить симплекс-метод.
При использовании М-метода следует обратить внимание на следующие два обстоятельства.
- Использование штрафа М может и не привести к исключению искусственной переменной в конечной симплекс-итерации. Если исходная задача линейного программирования не имеет допустимого решения (например, система ограничений несовместна), тогда в конечной симплекс-итерации, по крайней мере, одна искусственная переменная будет иметь положительное значение. Это "индикатор" того, что задача не имеет допустимого решения.
- Теоретически применение М-метода требует, чтобы М → ∞. Однако с точки зрения компьютерных вычислений величина М должна быть конечной и, вместе с тем, достаточно большой. Величина М должна быть настолько большой, чтобы выполнять роль "штрафа", но не слишком большой, чтобы не уменьшить точность вычислений. На практике вы должны помнить о возможных ошибках машинного округления при выполнении вычислений, в которых совместно участвуют как большие, так и малые числа.
На следующем шаге рассмотрим решение задачи линейного программирования М-методом.
