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

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

                                          m              n
                                          ∑ ai = ∑ b j .
                                          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 положительных
координат.
      Рассмотрим два метода нахождения исходной базисной точки для
транспортной задачи: метод "северо-западного угла" и метод минимального
элемента.


                                                  40