Базисные |
|
x1 |
|
x2 |
y1 |
y2 |
y3 |
Свободные |
отношение |
|
переменные |
|
|
члены |
|||||||
|
|
|
|
|
|
|
|
|
|
|
x2 |
|
5 |
|
1 |
5 |
|
0 |
0 |
100 |
160 |
|
8 |
|
4 |
|
||||||
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
y2 |
|
17 |
|
0 |
− |
3 |
1 |
0 |
30 |
2400 |
|
|
80 |
|
|
|
8 |
|
|
|
17 |
y3 |
|
|
|
0 |
− |
10 |
0 |
80 |
160 |
160 |
1 |
||||||||||
|
|
|
|
|
|
3 |
|
3 |
3 |
3 |
|
|
|
|
|
|
|
||||
f |
|
-38 |
|
0 |
140 |
0 |
0 |
11200 |
~ |
|
|
|
|
|
|
|
|
|
|
|
|
От элементов строки 1 отнимаем соответствующие элементы строки 3, умноженные на 5/8. От элементов строки 2 отнимаем соответствующие элементы строки 3, умноженные на 17/80. От элементов строки f отнимаем соответствующие элементы строки 3, умноженные на -38.
Базисные |
|
|
x1 |
|
|
|
|
|
|
x2 |
|
|
|
y1 |
y2 |
y3 |
Свободные члены |
||
переменные |
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
x2 |
|
|
0 |
|
|
|
|
1 |
|
|
|
|
10 |
0 |
− |
50 |
200 |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
3 |
3 |
y2 |
|
|
0 |
|
|
|
|
0 |
|
|
|
|
1 |
|
1 |
− |
17 |
56 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
3 |
3 |
x1 |
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
10 |
0 |
80 |
160 |
|
|
|
1 |
|
|
|
|
|
|
|
|
− |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
3 |
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
f |
|
|
0 |
|
|
|
|
|
0 |
|
|
|
|
40 |
0 |
3040 |
39680 |
||
|
|
|
|
|
|
|
|
|
|
3 |
|
|
3 |
3 |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
X 2=( |
160 , |
200 |
, |
0, |
56 |
, |
|
0) , |
|
|
|
|
|
|
|||||
|
3 |
|
|
3 |
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
f =39680 − |
40 |
y |
−3040 |
y |
|
, |
|
|
|
|
|
|
|||||||
3 |
|
|
|
3 |
|
1 |
3 |
|
|
3 |
|
|
|
|
|
|
|
||
f ( X 2)=39680/3 .
Учитывая, что все переменные неотрицательны по условию задачи, наибольшее значение функции f равно свободному члену 39680/3, т.е. мы получили оптимальное решение.
г) Построение двойственной задачи
Исходная задача:
найти max(108 x1+112 x2) при ограничениях
0,5 x1+0,8 x2 80 ;
0,4 x1+0,3 x2 60 ; 0,1 x1+0,1 x2 12 ; x1 0, x2 0.
Двойственная ей задача будет иметь вид: найти min(80 u1+60u2+12u3)
при ограничениях
0,5 u1+0,4 u2+0,1 u3 108;
0,8 u1+0,3u2+0,1 u3 112; u1 0, u2 0, u3 0.
Решение исходной задачи известно: x1=160 /3, x2 =200/3, f =39680 /3. Найдем решение двойственной задачи, используя соотношения двойственности.
Так как x1=160 /3>0 , то для оптимальных решений двойственной задачи первое ограничение должно выполняться как равенство:
|
0,5 u1+0,4 u2+0,1 u3=108. |
|
|
|
|
Так как |
x2=200/3>0 , то аналогично для оптимальных |
решений |
|||
двойственной задачи выполняется: |
|
|
|
|
|
|
0,8 u1+0,3u2 +0,1 u3=112. |
|
|
|
|
Подставляем |
оптимальное решение |
x1=160 /3, |
x 2=200 /3 в |
|
первое |
неравенство исходной задачи, видим, что |
0,5 160 /3+0,8 200/3=80 |
, |
то есть |
||
первое неравенство выполняется как равенство. Значит, сказать, что |
u1=0 |
||||
нельзя. |
|
|
x1=160 /3, x 2=200 /3 во |
||
Аналогично, |
подставляем оптимальное |
решение |
|||
второе неравенство исходной задачи, видим, что 0,4 160 /3+0,3 200/3=124/3<60 , то есть выполняется строго. Значит, для оптимальных решений двойственной
задачи u2=0 . |
|
|
|
|
|
|
Подставим |
решение |
в |
третье |
неравенство. |
Видим, |
что |
0,1 160 /3+0,1 200/3=12 , значит, |
u3≠0 . |
|
|
|
||
Таким образом, оптимальное решение двойственной задачи удовлетворяет системе уравнений:
0,5 u1+0,1u3=108 ;
0,8 u1+0,1u3=112.
Решая ее, находим
u1= 403 ;
u2=0 ; u3=30403 .
Оптимальное |
значение |
целевой |
функции |
двойственной задачи |
f двойств =80 40 |
+60 0+12 3040 |
=39680/3 . |
3 |
3 |
|