Линейное программирование. Азарнова Т.В - 47 стр.

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


                                       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 = ∑ x ij =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 −∑ a i >0.
j =1                                               j =1      i =1
В результате задача может быть записана в виде
                                      m
                                    ∑ ∑ cij x ij →           min
                                    i =1 j =1
                                n
                               ∑ x ij         ≤a i , i =1, m +1
                               j =1
                                      m +1
                                      ∑ x ij      =b j ,      j =1, n
                                      i =1

                            xij ≥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, a3 =4,
b1 =8, b2 =15, b3 =20, b4 =7.



                                                   49