64
Опыт показывает, что при решении большинства практических задач число
итераций, необходимое для получения окончательного результата, лежит в
пределах от 1,5т до 3т, где т – число ограничений (Данная оценка
справедлива лишь в том случае, если исходный базис содержит только
свободные или искусственные переменные.)
Как было показано на примере, приведенном в
разд. 3.4, одна из
переменных (в упомянутой задаче х
4
) вначале была включена в базис, а затем
из него выпала. Именно этим объясняется тот факт, что число итераций
превышает число соотношений, задающих ограничения. Для развития
интуитивного представления о том, что может произойти в процессе
выполнения симплекс-итераций, полезно рассмотреть следующий
Пример 3.5. Максимизировать 1y (3.5.1)
при ограничениях
3х – 2у
+ 4z + 1и = –2,
3х – 8z + lv= 6,
15x +6y – 12z + 1w == 222, (3.5.2)
Ix + 4z + 1t = 12,
x≥0, y≥0, z≥0, u≥0, v≥0, w≥0, t≥0.
В табл. 3.4 показана последовательность пробных решений. Заметим, что при
переходе от четвертого пробного решения к пятому в последнем вместо z появляется t.
Наконец, при переходе
от шестого пробного решения к седьмому t снова заменяется на
z. Переменная z в исходном варианте в базис не входит. Затем она становится
базисной. После этого ее снова исключают из базиса. И, наконец, переменная z опять
оказывается в числе базисных. Переменная t вначале является базисной, потом
выпадает из базиса, на
следующей итерации вновь становится базисной, а затем
выпадает из базиса окончательно. Обратим внимание также на то, что переменная х в
третьем пробном решении заменяет v, а в шестом пробном варианте вместо х снова
фигурирует v. В итоге после семи симплекс-итераций процесс сходимости
завершается. (Следует отметить, что в данном случае значение
целевой функции
улучшается на каждой итерации.)