Линейное программирование. Элементы теории, алгоритмы и примеры. Азарнова Т.В - 37 стр.

UptoLike

Рубрика: 

Линейное программирование
39
3) допустимые области обеих задач пустые;
4) допустимые области обеих задач неограниченные.
5. Определить, являются ли данные векторы
x
и
y
решениями данной зада-
чи и двойственной к ней:
max4
321
+
+
xxx
92125
321
=
+
+
xxx
114103
321
=
+
+
xxx
0,0,0
321
xxx
()
==
14
1
,
14
3
,2,0,1 yx .
6. Решить двойственные задачи , используя решение исходных задач сим -
плексным методом :
1) max23
321
+
+
xxx 2) min
4321
+
+
+
xxxx
523
321
+
xxx 62
4321
+
xxxx
102
321
+
+
xxx 2
31
+
xx
23
321
+
xxx 8232
432
+
xxx
0,0,0
321
xxx 0,0,0,0
4321
xxxx
3) max32
4321
+
+
xxxx
1032
321
=
+
xxx
7
431
=
+
+
xxx
423
531
=
+
+
xxx
0,0,0,0,0
54321
xxxxx
§ 7. Транспортная задача
Транспортная задача формулируется следующим образом . Имеется
m
пунктов производства AAA
m12
,,..., однородного продукта и
n
пунктов по-
требления BBB
n12
,,..., . Заданы объемы производства aim
i
,,
=
1 каждого
пункта A
i
и размеры спроса каждого пункта bjn
j
,,
=
1 в одних и тех же
единицах измерения . Известна также матрица njmicC
ij
,1,,1),( === рас-
ходов
ij
c
, связанных с перевозкой единицы продукции из пункта
A
i
в пункт
B
j
. Требуется составить план перевозок , обеспечивающий при минимальных
суммарных расходах удовлетворение всех пунктов потребления за счет
имеющегося в пунктах производства продукта .
Приведенная формулировка предполагает наличие равенства (условия
баланса )
                                                          Линейное программирование


3) допустимые области обеих задач пустые;
4) допустимые области обеих задач неограниченные.
5. Определить, являются ли данные векторы x и y решениями данной зада-
чи и двойственной к ней:
                                     x1 +4 x 2 +x 3 → max
                                      5 x1 +12 x 2 +2 x 3 =9
                                     3 x1 +10 x 2 +4 x 3 =11
                                      x1 ≥0, x 2 ≥0, x 3 ≥0
                                                      � 3 1�
                                    x =(1,0,2 ), y =�       , � .
                                                       � 14 14 �
6. Решить двойственные задачи, используя решение исходных задач сим-
плексным методом:
1) x1 +3 x 2 +2 x 3 → max                           2) x1 +x 2 +x3 +x 4 → min
   3 x1 −2 x 2 +x 3 ≥5                                    x1 −x 2 −2 x 3 +x 4 ≤6
     x1 +x 2 +2 x 3 ≥10                                 −x1         +x 3      ≤2
  −x1 +3 x 2 −x 3 ≥2                                         2 x 2 −3 x 3 +2 x 4 ≤8
     x1 ≥0, x 2 ≥0, x 3 ≥0                                x1 ≥0, x 2 ≥0, x 3 ≥0, x 4 ≥0
3) 2 x1 −x 2 +3x 3 +x 4 → max
     2 x1 +x 2 −3x 3 =10
       x1      + x3 + x4 =7
    −3x1         +2 x3 +x5 =4
       x1 ≥0, x 2 ≥0, x 3 ≥0, x 4 ≥0, x 5 ≥0

                            §7. Транспортная задача

     Транспортная задача формулируется следующим образом. Имеется m
пунктов производства A1 , A 2 ,..., A m однородного продукта и n пунктов по-
требления B1 , B 2 ,..., B n . Заданы объемы производства ai , i =1, m каждого
пункта A i и размеры спроса каждого пункта b j , j =1, n в одних и тех же
единицах измерения . Известна также матрица C =(cij ), i =1, m, j =1, n рас-
ходов c ij , связанных с перевозкой единицы продукции из пункта A i в пункт
B j . Требуется составить план перевозок, обеспечивающий при минимальных
суммарных расходах удовлетворение всех пунктов потребления за счет
имеющегося в пунктах производства продукта.
       Приведенная формулировка предполагает наличие равенства (условия
баланса)




                                         39