Основы теории систем и системного анализа. Матвеев Ю.Н. - 91 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

91
Опорное решение достигнуто:
,5,1,2,0
321321
=
=
=
=
=
=
уууххх
,2
4
=у значение W = 0. Но оно не является оптимальным, т.к. увеличение
2
х в W приводит к уменьшению W против нуля в опорном решении.
Правила нахождения оптимального решения ОЗЛП:
1. Если все
i
b ≥0 в симплекс-таблице, а в строке W (не считая
свободного члена) нет ни одного положительного элемента, то
оптимальное решение достигнуто.
2. Если в строке W есть положительный коэффициент 0>
р
γ , а в
столбце Р нет ни одного коэффициента
mi
pi
,1,0 =>
α
, то линейная
функция W не ограничена снизу и оптимального решения ОЗЛП не
существует.
3.
Если в столбце 0>
р
γ имеются
mi
pi
,1,0 =>
α
, то необходимо
произвести замену свободной переменной Р на базисную Z, используя тот
же принцип выбора разрешающего элемента, как при поиске опорного
решения.
Из таблицы примера 12 видно, что столбец х
2
является разрешаю-
щим (γ
2
= 1 > 0).
Найдем разрешающий элемент:
.52
,5
1
5
,2
1
2
32
3
12
1
<
==
==
α
α
b
b
Разрешающим элементом является
1
12
=
α
, следовательно, разре-
шающая строка – у
1
. Производим замену у
1
↔ х
2
, получаем таблицу:
Своб.
член
х
1
у
1
х
3
W
–2 –2 –1 0
х
2
2 1 1 –2
у
2
3 2 1 –1
у
3
3 –1 –1 3
у
4
4 3 1 –2
Оптимальное решение получено:
,3,3,2,0
0
3
0
2
0
2
0
1
0
3
0
1
====== yyxyxx
.2,4
0
min
0
4
−== Wy
Вернёмся к п. 2 правил нахождения оптимального решения ОЗЛП.
Если коэффициент 0>
р
γ в строке W, а в столбце P нет ни одного
коэффициента
mi
pi
,1,0 =>
α
, то увеличение свободной переменной х
р
≥ 0
приводит к неограниченному уменьшению линейной функции W.

Страницы