Методы оптимизации. Рейзлин В.И. - 35 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

Составители: 

Рубрика: 

3.4 Условия окончания преобразований
Если в симплексной таблице в
1m
-й строке все оценки
0CZ
jj
, то
полученный план является оптимальным; если же имеются положительные
оценки, то ищется следующий опорный план.
Если хотя бы для одной положительной оценки коэффициенты разложения
ij
x соответствующего вектора неположительные, то линейная функция не
ограничена на многограннике решений. При этом линейная функция может
принимать сколь угодно малое значение.
Процесс продолжается либо до получения оптимального плана, либо до
установления неограниченности линейной функции решаемой задачи. Если среди
оценок оптимального плана нулевые только оценки, соответствующие базисным
векторам, то это говорит о единственности оптимального плана.
Если система ограничений задачи линейного программирования содержит
единичный базис, то для решения задачи необходимо примерно
m
итераций.
Пример 3.2
Продолжим рассмотрение задачи из примера 3.1.
В
1m
-й строке первоначальной таблицы (табл.2) имеются две
положительные оценки. Они соответствуют векторам
2
A и
3
A . Это означает, что
первоначальный план не является оптимальным и его можно улучшить, включив
в базис вектор с
0CZmax
jjj0
. Среди коэффициентов разложения векторов
2
A и
3
A по базису имеются положительные, поэтому 0
02
и 0
03
, которые
исключают из базиса хотя бы один из векторов, существуют. Найдем эти
значения:
22
02
;
115,11min
03
;
111CZ
2202
;
331CZ
3303
;
33,1max
.
Следовательно, разрешающим элементом служит число
1
, стоящее на
пересечении первой строки и третьего столбца. Это означает, что необходимо
вектор
3
A включить в базис, а вектор
4
A исключить.
Составим вторую симплексную таблицу (табл.3).

Страницы