ВУЗ:
Составители:
88
Т а б л и ц а 5.4
Свободный
член
у
2
х
2
х
3
L
-5 2 -2 3
у
1
5 -2 1 -3
х
1
6 -2 0 -2
у
3
0 0 -3 2
С помощью табличного алгоритма обмена переменных в уравне-
ниях ограничений ОЗЛП можно решить любую задачу линейного про-
граммирования или убедиться, что она не имеет решений. Нахождение
решения каждой задачи линейного программирования распадается на
два этапа:
1. Отыскание опорного решения.
2. Отыскание оптимального решения, минимизирующего линей-
ную функцию. На первом этапе выясняется,
имеет ли вообще данная за-
дача допустимые (неотрицательные) решения; если да, то находится
опорное решение, для которого все свободные переменные равны нулю,
а все базисные – неотрицательны.
В процессе второго этапа попутно выясняется, ограничена ли сни-
зу минимизируемая функция; если нет, то оптимального решения не
существует. Если да, то оно находится
после того или другого числа
взамен х
j
↔ у
i
.
5.5.3. Отыскание опорного решения ОЗЛП
Пусть имеется ОЗЛП с ограничениями-равенствами, записанными
в стандартной форме:
⎪
⎪
⎭
⎪
⎪
⎬
⎫
α
++
α
+
α
−=
α
++
α
+
α
−=
α
++
α
+
α
−=
),...(
...................................................
),...(
),...(
2211
22221212
2
12121111
1
хххв
у
хххв
у
хххв
у
nmnmmm
m
nn
nn
(5.19)
разрешенными относительно базисных переменных у
1
, у
2
, …, у
m
. В ка-
ждой вершине ОДР (опорном решении) по крайней мере n перемен-
ных должно обращаться в нуль. Попробуем получить опорное решение,
полагая в формулах (5.19) все свободные переменные равными нулю.
Имеем
Страницы
- « первая
- ‹ предыдущая
- …
- 86
- 87
- 88
- 89
- 90
- …
- следующая ›
- последняя »
