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

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


                                       x ij ≥0 i =1, m,                       j =1, n
             m      n
Случай 2.   ∑ a i >∑ b j . В этом случае математическая постановка задачи
             i =1   j =1
имеет вид:
                                                    m
                                                    ∑ ∑ cij x ij →            min                 (10)
                                                    i =1 j =1
                                               n
                                             ∑ xij        ≤a i , i =1, m                          (11)
                                             j =1
                                           m
                                          ∑ x ij      =b j ,        j =1, n                       (12)
                                          i =1
                              x ij ≥0 i =1, m, j =1, n
Рассмотрим решение задачи (7)-(9). В ограничениях (8) введем дополнитель-
ные переменные x m +1, j , j =1, n .
                                       m                               m +1
                                      ∑ xij         +x m +1, j = ∑ xij =b j ,           j =1, n   (13)
                                      i =1                             i =1
Если сложить все ограничения (13) и вычесть из них сумму ограничений (7),
то получим равенство
 n                                                    n         m
∑ x m +1, j =a m +1 , i =1, m, где a m +1 =∑ b j −∑ ai >0.
j =1                                                 j =1       i =1
В результате задача может быть записана в виде
                                      m
                                   ∑ ∑ cij x ij →               min
                                   i =1 j =1
                               n
                              ∑ xij            ≤a i , i =1, m +1
                               j =1
                                      m +1
                                      ∑ xij         =b j ,       j =1, n
                                      i =1

                            x ij ≥0, i =1, m +1, j =1, n .
 Так как коэффициенты функции цели при дополнительных переменных
равны нулю, то c m +1, j =0, j =1, n . Таким образом, открытая транспортная за-
дача (7)- (9) сводится к закрытой транспортной задаче добавлением одного
ограничения, при этом условие баланса выполняется. Следовательно, новая
задача разрешима. Таким же способом может быть сведена к закрытой и за-
дача (10) - (12).
Пример 2. a1 =3, a 2 =6, a 3 =4,
b1 =8, b2 =15, b3 =20, b4 =7.



                                                     50