Переменная Ri, с помощью достаточно большого положительного числа М, штрафуется путём ввода в целевую функцию выражения – MRi в случае максимизации целевой функции и выражения +MRi – в случае минимизации. Вследствие этого штрафа естественно предположить, что процесс оптимизации симплекс-метода приведёт к нулевому значению переменной Ri. Следующий пример проясняет детали этого метода.
Пример 3.4-1
Минимизировать z = 4x1 + x2
при выполнении условий
3x1 + x2 = 3,
4x1 + 3x2 >= 6,
x1 + 2x2 <= 4,
x1, x2 >= 0.
Стандартная форма этой задачи получается в результате добавления дополнительной (избыточной) переменной x3 во второе неравенство и дополнительной (остаточной) переменной x4 в третье неравенство. Эта задача в стандартной форме будет записана следующим образом.
Минимизировать z = 4x1 + x2
при выполнении условий
3x1 + x2 = 3,
4x1 + 3x2 – x3 = 6,
x1 + 2x2 + x4 = 4,
x1, x2, x3, x4 >= 0.
В полученной задаче первое и второе уравнения не имеют дополнительных (остаточных) переменных, которые можно ввести в базисное решение. Поэтому введём в эти уравнения искусственные переменные R1 и R2, а в целевую функцию добавим штраф MR1 + MR2. В результате получим следующую задачу ЛП.
Минимизировать z = 4x1 + x2 + MR1 + MR2
при выполнении условий
3x1 + x2 + R1 = 3,
4x1 + 3x2 – x3 + R2 = 6,
x1 + 2x2 + x4 = 4,
x1, x2, x3, x4, R1, R2 >= 0.
В этой модифицированной задаче переменные R1, R2 и x4 можно использовать в качестве начального допустимого базисного решения.
При использовании М-метода следует обратить внимание на следующие два обстоятельства.
1. Использование штрафа М может и не привести к исключению искусственной переменной в конечной симплекс-итерации. Если исходная задача линейного программирования не имеет допустимого решения (например, система ограничений несовместна), тогда в конечной симплекс-итерации, по крайней мере, одна искусственная переменная будет иметь положительное значение. Это «индикатор» того, что задача не имеет допустимого решения.
2. Теоретически применение М-метода требует, чтобы М → ∞. Однако с точки зрения компьютерных вычислений величина М должна быть конечной и, вместе с тем, достаточно большой. Как понимать термин «достаточно большая» – это открытый вопрос. Величина М должна быть настолько большой, чтобы выполнить роль «штрафа», но не слишком большой, чтобы не уменьшить точность вычислений. На практике вы должны помнить о возможных ошибках машинного округления при выполнении выполнений, в которых совместно участвуют как большие, так и малые числа.
Правильный выбор значения М зависит от данных исходной задачи. Бездумное следование теоретическому требованию, что М должно быть «очень большим», может привести к значительным ошибкам округления. Именно поэтому М-метод никогда не применяется в коммерческих программах, реализующих симплекс-метод. Вместо него используется двухэтапный метод, который будет описан в следующем разделе.
2.2 Алгоритм двухэтапного метода.
Пример 2.2-2 демонстрирует проблемы, которые могут возникнуть при М-методе вследствие ошибок округления. Двухэтапный метод полностью лишён тех недостатков, которые присущи М-методу. Как следует из названия этого метода, процесс решения задачи ЛП разбивается на два этапа. На первом этапе ведётся поиск начального допустимого базисного решения. Если такое решение найдено, то на втором этапе решается исходная задача.
Этап 1. Задача ЛП записывается в стандартной форме, а в ограничения добавляются необходимые искусственные переменные (как и в М-методе) для получения начального базисного решения. Решается задача ЛП минимизации суммы искусственных переменных с исходными ограничениями. Если минимальное значение этой новой целевой функции больше нуля, значит, исходная задача не имеет допустимого решения, и процесс вычислений заканчивается. (Напомним, что положительные значения искусственных переменных указывают на то, что исходная система ограничений несовместна.) Если новая целевая функция равна нулю, переходим ко второму этапу.
Этап 2. Оптимальное базисное решение, полученное на первом этапе, используется как начальное допустимое базисное решение исходной задачи.
Пример 2.2-3
К задаче из примера 2.2-3 применим двухэтапный метод.
Этап 1
Минимизировать r = R1 + R2
С ограничениями
3x1 + x2 + R1 = 3,
4x1 + 3x2 – x3 + R2 = 6,
x1 + 2x2 + x4 = 4,
x1, x2, x3, x4, R1, R2, >= 0.
Соответствующая таблица имеет следующий вид.
| Базис | x1 | x2 | x3 | R1 | R2 | x4 | Решение |
| r | 0 | 0 | 0 | -1 | -1 | 0 | 0 |
| R1 | 3 | 1 | 0 | 1 | 0 | 0 | 3 |
| R2 | 4 | 3 | -1 | 0 | 1 | 0 | 6 |
| x4 | 1 | 2 | 0 | 0 | 0 | 1 | 4 |
Как и в М-методе, сначала вычисляется новая r-строка.
Старая r-строка: (0 0 0 -1 -1 0 | 0)
+ 1 * R1-строка: (3 1 0 1 0 0 | 3)
+ 1 * R2-строка: (4 3 -1 0 1 0 | 6)
= Новая r-строка: (7 4 -1 0 0 0 | 9)
Новая строка
r + 7x1 + 4x2 – x3 + 0R1 + 0R2 + 0x4 = 9
используется для решения первого этапа, что приведёт к следующему оптимальному решению (проверьте!).
| Базис | x1 | x2 | x3 | R1 | R2 | x4 | Решение |
| r | 0 | 0 | 0 | -1 | -1 | 0 | 0 |
| x1 | 1 | 0 | 1/5 | 3/5 | -1/5 | 0 | 3/5 |
| x2 | 0 | 1 | -3/5 | -4/5 | 3/5 | 0 | 6/5 |
| x4 | 0 | 0 | 1 | 1 | -1 | 1 | 1 |
Поскольку достигнут минимум r = 0, значит, на первом этапе получено допустимое базисное решение x1 = 3/5, x2 = 6/5 и x4 = 1. Искусственные переменные полностью выполнили свою «миссию», поэтому из последней таблицы можно удалить их столбцы. Переходим ко второму этапу.
Этап 2
После удаления искусственных переменных исходная задача будет записана следующим образом.
Минимизировать z = 4x1 + x2
с ограничениями
x1 + 1/5 x3 = 3/5,
x2 + 3/5 x3 = 6/5,
x3 + x4 = 1,
x1, x2, x3, x4 >= 0.
Обратите внимание, что после первого этапа исходная задача претерпела некоторые изменения, которые учитывают полученное базисное решение. Этой трансформированной задаче соответствует следующая таблица:
| Базис | x1 | x2 | x3 | x4 | Решение |
| z | -4 | -1 | 0 | 0 | 0 |
| x1 | 1 | 0 | 1/5 | 0 | 3/5 |
| x2 | 0 | 1 | -3/5 | 0 | 6/5 |
| x4 | 0 | 0 | 1 | 1 | 1 |
Поскольку базисные переменные x1 и x2 имеют ненулевые коэффициенты в z-строке, эту строку следует преобразовать.
Старая z-строка: (-4 -1 0 0 | 0)
+ 4 * x1-строка: (4 0 4/5 0 | 12/5)
+ 1 * x2-строка: (0 1 -3/5 0 | 6/5)
= Новая z-строка: (0 0 1/5 0 | 18/5)
Начальная таблица второго этапа примет следующий вид:
| Базис | x1 | x2 | x3 | x4 | Решение |
| z | 0 | 0 | 1/5 | 0 | 18/5 |
| x1 | 1 | 0 | 1/5 | 0 | 3/5 |
| x2 | 0 | 1 | -3/5 | 0 | 6/5 |
| x4 | 0 | 0 | 1 | 1 | 1 |
Так как решается задача минимизации, следует ввести переменную x3 в базис. Применение алгоритма симплекс-метода уже на следующей итерации приведёт к оптимальному решению (проверьте!).
Удаление искусственных переменных в конце первого этапа имеет смысл только тогда, когда все они являются небазисными (как в примере 2.2-4). Однако возможна ситуация, когда в конце первого этапа искусственные переменные останутся в базисе, но будут иметь нулевые значения. В этом случае такие переменные при необходимости будут формировать часть начального базисного решения для второго этапа. При этом необходимо так изменить вычисления, выполняемые на втором этапе, чтобы искусственные переменные никогда не смогли принять положительные значения ни в каких итерациях симплекс-метода.
Существует простое правило, которое гарантирует, что нулевая базисная искусственная переменная на втором этапе никогда не станет положительной. Если в ведущем столбце коэффициент, соответствующий нулевой базисной искусственной переменной, положителен, тогда ведущий элемент определяется автоматически (поскольку ему соответствует минимальное отношение, равное нулю) и искусственная переменная на следующей итерации становится небазисной. Если ведущий элемент равен нулю, следующая итерация оставляет искусственную переменную нулевой. И наконец, рассмотрим отрицательный ведущий элемент. В этом случае минимальное отношение не ассоциируется с базисной (нулевой) искусственной переменной. Если минимальное отношение будет положительным, то на следующей итерации искусственная переменная примет положительное значение (обоснуйте это утверждение). Чтобы исключить эту возможность, мы принуждаем искусственную переменную всегда оставаться в базисном решении. Поскольку искусственная переменная равна нулю, её удаление из базисного решения не влияет на то, будет ли допустимым решение из оставшихся в базисе переменных. (Было бы полезно для читателя рассмотреть все описанные случаи с помощью симплекс-таблиц.)
Итак, правило для второго этапа заключается в том, чтобы искусственные переменные оставлять в базисе всегда, когда коэффициент в ведущем столбце положительный или отрицательный. Фактически это правило применяется в конце первого этапа, когда удаляем нулевые искусственные переменные из базисного решения, перед тем как приступить ко второму этапу.