Составители:
Рубрика:
115 116
свободные, т.е. какая строка таблицы станет разрешающей. Ис-
пользуя правило выбора разрешающей строки, получим:
34
3
120
2
240
2
400
1
260
min
a
b
,, ==
⎭
⎬
⎫
⎩
⎨
⎧
,
таким образом, разрешающей становится третья строка (третье
уравнение системы ограничений). Следовательно, из базиса вый-
дет переменная х
7
.
Симплекс-таблица решения данной задачи:
БП x
1
x
2
x
3
x
4
x
5
x
6
x
7
Свобод
-
ный
член
x
5
2 1 3 1 1 0 0 260
x
6
1 2 1 2 0 1 0 400
x
7
2 0 1
2
0 0 1 240
X
1
=(0, 0, 0, 0, 260, 400, 240)
Т
)5241(
120
2
240
2
400
1
260
min
−−−−=
=
⎭
⎬
⎫
⎩
⎨
⎧
,,,r
,,
Z
1
–1 –4 –2 –5
0 0 0 0
x
5
1 1 5/2 0 1 0
2
1
−
140
x
6
–1
2
0 0 0 1 –1 160
x
4
1 0 1/2 1 0 0 1/2 120
X
2
=(0, 0, 0, 120, 140, 160, 0)
Т
)
2
5
2
9
44(
80
2
160
1
140
min
,,,r
,
−=
=
⎭
⎬
⎫
⎩
⎨
⎧
Z
1
4 –4 9/2
0 0 0
5/2
600
x
5
0 0 1 60
x
2
1 0 0 80
x
4
0 1 0 120
0)
2
1
,2,
2
9
,2(
920
min1
)0,60,120,0,80,0(
*
~
>=
−=
=
r
Z
T
X
Z
1
2
0
9/2
0 0
2 1/2
920
Так как r>0, то задача имеет единственное оптимальное ре-
шение:
T
X )120,0,80,0(
*
= , а .920
max
=
Z
Двойственная задача имеет вид:
min240400260
321
→++
=
yyyW
при ограничениях:
⎪
⎪
⎩
⎪
⎪
⎨
⎧
≥++
≥++
≥+
≥++
,522
,23
,42
,122
321
321
21
321
yyy
yyy
yy
yyy
)31(0 ,iy
i
=≥
Согласно первой теореме двойственности имеем:
.920
maxmin
=
=
ZW
Для нахождения оптимальных оценок
*
1
y ,
*
2
y и
*
3
y ресурсов
воспользуемся второй теоремой двойственности. Из того, что
.5220120
,42080
*
3
*
2
*
1
*
4
*
2
*
1
*
2
=++⇒>=
=+⇒>=
yyyx
yyx
Имеем систему двух линейных уравнений с тремя неизвест-
ными. При подстановке в первое ограничение значений
120,0,80,0
*
4
*
3
*
2
*
1
==== xxxx получим строгое неравенство:
.26012010380102
<
⋅
+
⋅
+
⋅
+
⋅
Следовательно,
.0
*
1
=y
Второе и третье ограничения обра-
щаются в равенства:
.; 2401202010240012020180201 =
⋅
+
⋅
+
⋅
=
⋅
+
⋅
+
⋅
+
⋅
Подставив значение
*
1
y в систему, получим 2
*
2
=y и
5,0
*
3
=y . Таким образом, имеем оптимальный план двойственной
задачи:
)5,0;2;0(
*
=Y ,
из которого следует, что самым дефицитным является второй ре-
сурс, так как его оценка самая высокая: 2
*
2
=y . Менее дефицит-
ным является третий ресурс:
*
2
*
3
5,0 yy <= ; избыточным (недефи-
цитным) является первый ресурс, имеющий оценку
.0
*
1
=y
свободные, т.е. какая строка таблицы станет разрешающей. Ис- ⎧ 2 y1 + y 2 + 2 y 3 ≥ 1,
пользуя правило выбора разрешающей строки, получим: ⎪ y + 2 y ≥ 4,
⎪ 1 2
⎧ 260 400 240 ⎫ b3 ⎨
min ⎨ , , ⎬ = 120 = , ⎪ 13 y + y 2 + y 3 ≥ 2,
⎩ 1 2 2 ⎭ a34 ⎪⎩ y1 + 2 y 2 + 2 y 3 ≥ 5,
таким образом, разрешающей становится третья строка (третье
уравнение системы ограничений). Следовательно, из базиса вый- yi ≥ 0 (i = 1,3)
дет переменная х7. Согласно первой теореме двойственности имеем:
Симплекс-таблица решения данной задачи: Wmin = Z max = 920.
Свобод-
БП x1 x2 x3 x4 x5 x6 x7 ный Для нахождения оптимальных оценок y1* , y 2* и y 3* ресурсов
член
x5 2 1 3 1 1 0 0 260 X1=(0, 0, 0, 0, 260, 400, 240)Т воспользуемся второй теоремой двойственности. Из того, что
x6 1 2 1 2 0 1 0 400 ⎧ 260 400 240 ⎫
min ⎨ , , ⎬ = 120
x 2* = 80 > 0 ⇒ y1* + 2 y 2* = 4,
⎩ 1 2 2 ⎭
x7 2 0 1 2 0 0 1 240 r = ( −1, − 4 , − 2 , − 5)
x 4* = 120 > 0 ⇒ y1* + 2 y 2* + 2 y 3* = 5.
Имеем систему двух линейных уравнений с тремя неизвест-
Z1 –1 –4 –2 –5 0 0 0 0 ными. При подстановке в первое ограничение значений
x5 1 1 5/2 0 1 0 −
1
140
X2=(0, 0, 0, 120, 140, 160, 0)Т x1* = 0, x 2* = 80, x3* = 0, x 4* = 120 получим строгое неравенство:
2 ⎧ 140 160 ⎫ 2 ⋅ 0 + 1 ⋅ 80 + 3 ⋅ 0 + 1 ⋅ 120 < 260.
min ⎨ , ⎬ = 80
x6 –1 2 0 0 0 1 –1 160 ⎩ 1 2 ⎭
Следовательно, y1* = 0. Второе и третье ограничения обра-
9 5
x4 1 0 1/2 1 0 0 1/2 120 r = (4 , − 4 , , ) щаются в равенства:
2 2
Z1 4 –4 9/2 0 0 0 5/2 600 1 ⋅ 0 + 2 ⋅ 80 + 1 ⋅ 0 + 2 ⋅ 120 = 400; 2 ⋅ 0 + 1 ⋅ 0 + 2 ⋅ 120 = 240.
~
x5 0 0 1 60 X * = (0, 80, 0, 120, 60, 0)T Подставив значение y1* в систему, получим y 2* = 2 и
Z1 min = −920
x2 1 0 0 80 y 3* = 0,5 . Таким образом, имеем оптимальный план двойственной
9 1 задачи:
x4 0 1 0 120 r = ( 2, , 2, ) > 0
2 2
Z1 2 0 9/2 0 0 2 1/2 920 Y * = (0; 2; 0,5) ,
Так как r>0, то задача имеет единственное оптимальное ре- из которого следует, что самым дефицитным является второй ре-
шение: сурс, так как его оценка самая высокая: y 2* = 2 . Менее дефицит-
X * = (0, 80, 0, 120) T , а Z max = 920. ным является третий ресурс: y 3* = 0,5 < y 2* ; избыточным (недефи-
Двойственная задача имеет вид:
цитным) является первый ресурс, имеющий оценку y1* = 0.
W = 260 y1 + 400 y 2 + 240 y 3 → min
при ограничениях:
115 116
Страницы
- « первая
- ‹ предыдущая
- …
- 55
- 56
- 57
- 58
- 59
- …
- следующая ›
- последняя »
