Автоматизация технологического проектирования. Смирнов О.Л. - 23 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

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

Рубрика: 

23
мальности этой вершины, и в случае неоптимальности принимают ре-
шение об удалении из базиса очередной переменной с максимальным
значением отрицательного коэффициента, и цикл повторяется, пока не
встретится оптимальная вершина.
Анализ системы (26) для приведенного примера показывает, что ба-
зис (x
1
, x
2
) и соответствующая вершина A – неоптимальны, значение
целевой функции x
0
= 0 в силу равенства нулю базисных переменных
x
2
, а удаляемой из базиса переменной является x
2
, так как при ней наи-
больший по модулю коэффициент – со знаком минус. Значение, с кото-
рым x
2
удаляется из базиса, равно четырем. Оно определяется в соот-
ветствии с описанным выше правилом
2
x
= min (7/0, 15/3, 9/1, 4/1) = 4. (27)
При этом опоpным равенством становится пятое, а базисной перемен-
ной – x
6
. С его помощью система (26) алгебраически преобразуется в кано-
ническую систему для следующего базиса (x
1
, x
6
) и соответствующей ему
вершины B. Для преобразования системы (26) в новую каноническую фор-
му нужно с его помощью удалить из остальных уравнений и целевого урав-
нения исключаемую из базиса (x
1
, x
2
) переменную
2
x
, а само опорное урав-
нение оставить без изменения. Для этого уравнение с удаляемой перемен-
ной и опорное умножаются на такие коэффициенты, чтобы при их сложе-
нии члены с удаляемой переменной взаимно исключались. В данном слу-
чае для исключения x
2
из целевого уравнения надо сложить с ним удвоен-
ное опорное. Для исключения его из третьего уравнения надо из него вы-
честь утроенное опорное, а для четвертого надо из него вычесть одно опор-
ное. В результате этого получим каноническую форму системы для верши-
ны B и соответствующего ей базиса (x
1
, x
6
)
01 6
13
14 6
156
26
2
8;
7;
3
3;
5
;
4.
xx x
xx
xx x
xxx
xx
−− =
+=
+− =
+−=
+=
(28)
Из анализа системы (28) следует, что вершина B неоптимальная, зна-
чение целевой функции в ней равно 8, удалять из базиса нужно пере-
менную x
1
со значением

Страницы