ВУЗ:
Составители:
Рубрика:
17
←А
8
-M 36 3 2 0 1 0 -1 0 1
0 2 -1 0 0 0 0 0 0
Z
j
-C
j
-54 -1 -1↑ 0 1 1 1 0 0
A
3
0 46 4 0 1 1 0 -1 0
A
7
-M 36 -1/2 0 0 -3/2 -1 -1/2 1
A
2
1 18 3/2 1 0 Ѕ 0 -1/2 0
18 7/2 0 0 72/2 0 -1/2 0
Z
j
-C
j
-36 1/2 0 0 3/2 1 -1/2 0
Таблицы 8 и 9. Первое и второе опорные решения.
Из базиса надо исключить искусственную переменную х
7
и соответст-
вующий вектор А
7
, но мы не можем этого сделать, т.к. все элементы стоящие
в нижней строке (кроме элемента стоящего в столбце А
6
) неотрицательны, а
вектор А
6
мы не можем включить в базис, так как среди его компонент нет
положительных. Такая ситуация говорит о том, что исходная задача не имеет
опорного плана (а значит оптимального). Другими словами система ограни-
чений первоначальной задачи несовместима, то есть существуют ограниче-
ния, противоречащие друг другу. Если в практической задаче встречается та-
кая
ситуация, то это означает, что систему ограничений нужно пересмотреть.
Двойственные задачи линейного программирования.
В каждой задаче ЛП можно определённым образом сопоставить неко-
торую другую задачу ЛП называемую двойственной или сопряжённой по от-
ношению к исходной.
Рассмотрим например следующую задачу ЛП.
Z=C
1
x
1
+C
2
x
2
+…+C
n
x
n
→ max
⎪
⎪
⎩
⎪
⎪
⎨
⎧
≤+++
≤+++
≤+++
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
...
........................................
...
...
2211
22222121
11212111
(1)
njx
j
,10
=
≥
Двойственной к ней будет являться следующая:
W= b
1
y
1
+b
2
y
2
+…+b
m
y
m
→min
⎪
⎪
⎩
⎪
⎪
⎨
⎧
≥+++
≥+++
≥+++
nmmnnn
mm
mm
cyayaya
cyayaya
cyayaya
...
........................................
...
...
2211
22222112
11221111
(2)
miy
i
,10 =≥
←А8 -M 36 3 2 0 1 0 -1 0 1
0 2 -1 0 0 0 0 0 0
Zj-Cj
-54 -1 -1↑ 0 1 1 1 0 0
A3 0 46 4 0 1 1 0 -1 0
A7 -M 36 -1/2 0 0 -3/2 -1 -1/2 1
A2 1 18 3/2 1 0 Ѕ 0 -1/2 0
18 7/2 0 0 72/2 0 -1/2 0
Zj-Cj
-36 1/2 0 0 3/2 1 -1/2 0
Таблицы 8 и 9. Первое и второе опорные решения.
Из базиса надо исключить искусственную переменную х7 и соответст-
вующий вектор А7, но мы не можем этого сделать, т.к. все элементы стоящие
в нижней строке (кроме элемента стоящего в столбце А6) неотрицательны, а
вектор А6 мы не можем включить в базис, так как среди его компонент нет
положительных. Такая ситуация говорит о том, что исходная задача не имеет
опорного плана (а значит оптимального). Другими словами система ограни-
чений первоначальной задачи несовместима, то есть существуют ограниче-
ния, противоречащие друг другу. Если в практической задаче встречается та-
кая ситуация, то это означает, что систему ограничений нужно пересмотреть.
Двойственные задачи линейного программирования.
В каждой задаче ЛП можно определённым образом сопоставить неко-
торую другую задачу ЛП называемую двойственной или сопряжённой по от-
ношению к исходной.
Рассмотрим например следующую задачу ЛП.
Z=C1x1+C2x2+…+Cnxn → max
⎧
⎪ a11 x1 + a12 x2 + ... + a1n xn ≤ b1
⎪
⎨ a21 x1 + a22 x2 + ... + a2 n xn ≤ b2 (1)
⎪ ........................................
⎪
⎩am1 x1 + am 2 x2 + ... + amn xn ≤ bm
xj ≥ 0 j = 1, n
Двойственной к ней будет являться следующая:
W= b1y1+b2y2+…+bmym →min
⎧
⎪ a11 y1 + a21 y2 + ... + am1 ym ≥ c1
⎪
⎨a12 y1 + a22 y2 + ... + am 2 ym ≥ c2 (2)
⎪ ........................................
⎪
⎩a1n y1 + a2 n y2 + ... + amn ym ≥ cn
yi ≥ 0 i = 1, m
17
