Элементы теории двойственности. Чернышова Г.Д - 15 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

15
Модель, двойственная к ней:
0
2
42
32
min681618
421
4321
321
4321
³
ï
î
ï
í
ì
³++
³+++
³++
®
+
+
+
y
yyy
yyyy
yyy
yyyy
(*)
Для нахождения решения двойственной задачи, сначала найдем решение
исходной задачи методом искусственного базиса. Оно приведено в таблице.
Таблица 1
B
B
C
b
1
A 3
2
A 4
3
A 2
4
A 0
5
A 0
6
A 0
7
A 0
4
A
0 18 1 2 1 1 0 0 0
5
A
0 16 2 1 1 0 1 0 0
6
A
0 8 1 1 0 0 0 1 0
7
A
0 6 0
1
1 0 0 0 1
–3 –4 –2 0 0 0 0
4
A
0 6 1 0 –1 1 0 0 –2
5
A
0 10 2 0 0 0 1 0 –1
6
A
0 2 1 0 –1 0 0 1 –1
2
A
4 6 0 1 1 0 0 0 1
–3 0 2 0 0 0 4
4
A
0 4 0 0 0 1 0 –1 –1
5
A
0 6 0 0 2 0 1 –2 1
1
A
3 2 1 0 –1 0 0 1 –1
2
A
4 6 0 1 1 0 0 0 1
0 0 –1 0 0 3 1
4
A
0 4 0 0 0 1 0 –1 –1
3
A
2 3 0 0 1 0 ½ –1 ½
1
A
3 5 1 0 0 0 ½ 0 –1/2
2
A
4 3 0 1 0 0 –1/2 1 ½
0 0 0 0 1/2 2 3/2
Из таблицы видно, что базис состоит из векторов
4312
,,,
AAAA
.
÷
÷
÷
÷
÷
ø
ö
ç
ç
ç
ç
ç
è
æ
--
-
-
-
=
-
1101
2/112/10
2/112/10
2/102/10
1
B ,
(
)
335
*
=x . 
       Модель, двойственная к ней:
                                   18 y1 � 16 y 2 � 8 y3 � 6 y 4 � min
                                   � y1 � 2 y 2 � y 3 � 3
                                   �
                                   �2 y1 � y 2 � y 3 � y 4 � 4                        (*)
                                   �y � y � y � 2
                                   � 1      2     4

                                   y�0
    Для нахождения решения двойственной задачи, сначала найдем решение
исходной задачи методом искусственного базиса. Оно приведено в таблице.
                                                                                  Таблица 1
  B        CB      b        A1 3       A2 4        A3 2     A4 0     A5 0    A6 0     A7 0
  A4       0       18        1          2           1        1           0    0        0
  A5       0       16        2          1           1        0           1    0        0
  A6       0       8         1          1           0        0           0    1        0
  A7       0       6         0          1           1        0           0    0        1
                             –3         –4         –2        0           0    0       0
  A4       0       6         1           0         –1        1           0    0       –2
  A5       0       10        2          0           0        0           1    0       –1
  A6       0       2         1          0          –1        0           0    1       –1
  A2       4       6         0          1           1        0           0    0        1
                             –3         0           2        0           0   0        4
  A4       0       4         0          0           0        1           0   –1       –1
  A5       0       6         0          0           2        0           1   –2        1
  A1       3       2         1          0          –1        0           0    1       –1
  A2       4       6         0          1           1        0           0    0        1
                             0          0          –1        0           0   3        1
  A4       0       4         0          0           0        1           0   –1       –1
  A3       2       3         0          0           1        0           ½   –1       ½
  A1       3       5         1          0           0        0           ½    0      –1/2
  A2       4       3         0          1           0        0       –1/2     1       ½
                             0          0           0        0       1/2      2       3/2

       Из таблицы видно, что базис состоит из векторов A4 , A3 , A1 , A2 .
                          � 0 1/ 2    0 � 1/ 2�
                          �                   �
                          � 0 � 1/ 2 1   1/ 2 � *
                  B �1   ��                      , x � �5 3 3� .
                             0 1/ 2 � 1 1/ 2 �
                          ��                  ��
                           � 1  0    � 1  � 1  �
                                              15

Страницы