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

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


2. Решить М- методом задачу ЛП.
                         x1 −x 2 +x3 −3x5 → max
                        −2 x1 +x2 + x4 −x5 =a
                                             b
                      2 x1 −x 2 +x3 −x4 −        x5 =1
                                           b +1
                                         c
                      −x1 +x 2 −x3 +        x 4 +x5 =8 ;
                                       c +1
                         x j ≥0, j =1,5.

     а    в    с                а         в          с             а    в          с        а   в   с

1    1    1    2          6     6         2          2        11   2    2          3   16   3   2   4
2    2    1    2          7     7         2          2        12   4    2          3   17   6   2   4
3    3    1    2          8     2         1          3        13   6    2          3   18   3   3   4
4    4    1    2          9     4         1          3        14   3    1          4   19   6   3   4
5    5    2    2          10    6         1          3        15   6    1          4   20   3   4   4

         §5. Двойственные задачи линейного программирования

     Рассмотрим задачу линейного программирования, записанную в произ-
вольной форме:
                                              n
                                              ∑ c j x j → max (min)
                                              j =1
                                      n
                                     ∑ a ij x j          ≤(≥, =) bi , i =1, m .
                                      j =1

                x j ≥0 (≤, нет требований на знак ) , j =1, n .
Данную задачу будем называть исходной. Под двойственной задачей (ДЗ) к
исходной понимается задача линейного программирования, которая строится
по следующим правилам, приведенным в таблице.

                Исходная задача                                        Двойственная задача
                   n                                                        m
                   ∑cjxj       → max                                        ∑ bi y i → min
                   j =1                                                     i =1
                          n                                                        y i ≥0
                       ∑ a ij x j   ≤bi
                       j =1
                          n                                                        y i ≤0
                       ∑ a ij x j   ≥bi
                       j =1




                                                         30