2.10. Признак оптимальности опорного плана
Если начальный опорный план найден, то далее следует проверить, можно ли улучшить значение целевой функции, если увеличить одну из небазисных (нулевых) переменных и ввести ее в базис.
Пусть задача линейного программирования преобразована к канонической форме и ее ограничения имеют предпочтительный вид:
Выражая базисные переменные через свободные, получим
и после подстановки в целевую функцию выразим ее значение только через небазисные переменные, как
Используем векторные обозначения для столбцов матрицы коэффициентов и столбца свободных членов
,
,
… ,
,
;
а также для коэффициентов целевой функции при базисных переменных
.
Тогда целевая функция может быть представлена как
,
а если ввести обозначения для входящих в нее слагаемых
и
,
то окончательно получим
.
Переменные
– это свободные переменные, поэтому
величины
называют оценками свободных переменных.
Если все эти оценки неотрицательны, то
опорный план
является оптимальным, так как введение
любой из этих переменных в базис только
уменьшит величину функционала. Его
значение для текущего опорного плана
есть
и определяется базисными переменными.
Если для нескольких свободных переменных оценки отрицательны, то включение любой из них в базис приведет к увеличению функционала. Обычно для очередной итерации вводят в базис ту свободную переменную, которой соответствует наибольшая по абсолютной величине отрицательная оценка. Однако вполне может случиться, что такая переменная требует значительных затрат дефицитных ресурсов и при последующих итерациях ее место займет переменная, не столь требовательная к ресурсам и обеспечивающая за счет своей величины более значительный прирост функционала, несмотря на меньшую оценку.
На практике симплекс-метод применяется для решения очень больших задач, а приведенные выше соображения поясняют, почему количество необходимых итераций зависит не только от размерности модели, но и от ее структуры. Довольно часто число итераций для нахождения оптимального решения оказывается примерно таким же, как и число ограничений модели, но можно искусственно построить задачу, содержащую n переменных, при решении которой потребуется 2n итераций.
Если все оценки свободных переменных неотрицательны, но хотя бы одна из них нулевая, то при включении этой переменной в базис функционал не изменится и мы получим альтернативное оптимальное решение. Это будет еще одна угловая точка, и получается бесконечное множество решений, которым соответствует отрезок, соединяющий найденные угловые точки. Для интерпретации возникшей проблемы выбора одного из множества решений предположим, что одинаковые результаты получаются при производстве любого из двух видов товаров. Скорее всего, будет принято решение производить оба товара, чтобы в условиях конкуренции «не класть все яйца в одну корзину».
2.11. Переход к нехудшему опорному плану
Представим все данные рассматриваемой задачи в виде таблицы, которую называют симплексной. Это естественный способ организации данных и на бумаге, и в памяти компьютера. В первой строке табл. 2.2 записаны все переменные, входящие в модель, а под ними – соответствующие им коэффициенты целевой функции. Очевидно, что при переходе к нехудшему опорному плану эти строки изменяться не должны. Первоначальный порядок перечисления переменных модели может быть любым.
В столбце БП
перечислены все переменные, входящие
в текущий базис, в столбцах
и
– коэффициенты функционала при базисных
переменных и сами значения этих
переменных.