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

                                                          Линейное программирование


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