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

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

                                        m             n
                                       ∑ ai = ∑ bj .
                                       i =1          j =1
      Такая задача называется закрытой транспортной задачей. Математиче-
ская постановка этой задачи имеет следующий вид
                                         m     n
                                        ∑ ∑ cij xij           → min                         (1)
                                         i =1 j =1
при ограничениях
                                   n
                              ∑ x ij           =ai          i =1, m                         (2)
                                 j =1
                             m
                            ∑ x ij          =bj       j =1, n                               (3)
                            i =1


                         x ij ≥0 i =1, m,                    j =1, n ,                      (4)
где x ij - количество продукта, перевозимое из пункта A i в пункт B j .
     Без ограничения общности всегда можно считать, что ai >0, i =1, m и
b j >0, j =1, n .
      Задача (1)-(4) является задачей линейного программирования, записан-
ной в канонической форме. Она имеет mn переменных и m +n ограничений.
Любая допустимая точка задачи может быть записана в виде матрицы

                                  � x 11 ... x 1n �
                                   �                  �
                             ( )
                       X = x ij =� ... ... ... � .
                                     � x                �
                                      � m1 ... x mn �
     Как известно, не любая задача линейного программирования имеет ре-
шение. Условия разрешимости транспортной задачи формулируются в сле-
дующей теореме.
     Теорема 1. Для разрешимости транспортной задачи необходимо и
достаточно выполнение следующего условия баланса
                                         m             n
                                        ∑ ai =∑ bj .
                                        i =1          j =1
      Можно показать, что число независимых уравнений системы (2)-(3)
равно m +n −1. Отсюда, в частности, следует, что любая допустимая базис-
ная точка транспортной задачи содержит не более m +n −1 положительных
координат.
      Рассмотрим два метода нахождения исходной базисной точки для
транспортной задачи: метод "северо-западного угла" и метод минимального
элемента.


                                               39