Сделай Сам Свою Работу на 5

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





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

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

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

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

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



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

. (8.13)

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

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

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

.

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



Рис. 8.2. Поведение зависимых переменных

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

.

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

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

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

т.к. .

Определение нового базисного решения (замена базиса)

Метод подстановки

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

во все остальные уравнения этой системы: Для этого выразим через и .

.

Подставим полученное выражение в остальные уравнения:

.

В результате подстановки изменяются:

столбец свободных членов:

; (8.14)

и элементы всех столбцов матрицы

; . (8.15)

Необходимо сделать пояснение относительно столбца a. Поскольку переменные и поменялись местами, то на месте столбца a в новой матрице будут стоять коэффициенты, связанные с , что и отражено в формуле (8.15).



После выполнения подстановки вновь образуется система из m уравнений, разрешенная относительно r = n – m независимых переменных. В новой системе независимых переменных заменяет . Новый базис является допустимым, поскольку, по условиям построения нового базиса ни одна из переменных не перешла через ноль. Последующая работа симплекс–метода аналогична описанной, но выполняется уже для другого базисного решения.

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.