Анализ возможностей уменьшения целевой функции

Для заключения о возможности дальнейшего улучшения решения необходимо проанализировать вид функции (8.12). Исследование возможности уменьшения целевой функции сводится к анализу строки коэффициентов и может дать следующие результаты:

1. Все компоненты вектора положительны. Это означает, что дальнейшее улучшение целевой функции невозможно и рассматриваемое базисное решение является единственно возможным: при .

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

Границы изменения

Увеличение переменной связано с изменением всех зависимых (базисных) переменных (8.10). Некоторые из них будут уменьшаться. Увеличивать переменную можно лишь до той поры, пока одна из зависимых переменных в системе не перейдет через ноль.

Поскольку на этом шаге симплекс–метода все независимые переменные за исключением (это лишь обозначение некоторой реальной переменной ) равны нулю, то система ограничений может быть представлена в более простом виде:

.

(8.13)

Зависимости показаны на рис. 8.2.

На рассматриваемом этапе возможны две ситуации:

1. Все . Увеличение ведет к увеличению всех зависимых переменных (по аналогии с прямой на рис. 8.2). Поскольку стандартная задача линейного программирования не содержит ограничений по максимальному значению переменных, то можно увеличивать до бесконечности и целевая функция будет при этом уменьшаться до минус бесконечности. Эта ситуация приводит к окончанию работы симплекс–метода с результатом

.

2. Среди компонент есть положительные. Это значит, что с увеличением некоторые зависимые переменные уменьшаются и при достижении определенной величины первая из них ( на рис. 8.2) пересекает ноль, сигнализируя о невозможности дальнейшего увеличения независимой переменной.

Рассмотрим этот случай более подробно. Для этого формируется столбец:

.

Очевидно, что минимальная компонента этого столбца определяет максимально возможное изменение варьируемой переменной, и номер базисной переменной , которая первой пересекает ноль при увеличении ;

Переменная в дальнейшем не может рассматриваться в качестве независимой переменной. Ее необходимо перевести в класс зависимых переменных. За счет какой другой переменной? Вероятно за счет той, ранее зависимой переменной , что стала равной нулю, и которую, возможно, следует увеличить.

Совершенно очевидно, что при полученном ограничении все остальные независимые переменные останутся положительными. Действительно, если подставить значение в систему (8.13), то получим:

т.к. .