9.6 Метод севево-западного угла

            Рассмотрим "северо-западный угол" незаполненной таблицы, то

есть клетку, соответствующую первому поставщику и первому потребителю.

            Возможны три случая.

            

Это означает, что первый поставщик отгрузил весь произведенный продукт первому потребителю и его

запас равен нулю, поэтому

                                   

При этом неудовлетворенный спрос в первом пункте потребления равен

                                   

            

то есть спрос первого потребителя полностью удовлетворен и поэтому                    

а остаток продукта в первом пункте производства равен

                                   

            

из рассмотрения можно исключить и поставщика, и потребителя. Однако при атом план получается вырожденным,

поэтому условно считается, что выбывает только поставщик,

                        

а спрос потребителя остается неудовлетворенным и равным нулю.

                                   

            После этого рассматриваем северо-западный угол оставшейся не-

заполненной части таблицы и повторяем те же действия. В результате

через n+m-1   шагов получим опорный план.

9. Математическая модель транспортной задачи. Открытые и закрытые задачи. Допустимый, опорный и оптимальный планы перевозок.

Под названием «транспортная задача» объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.

Открытая и закрытая транспортные задачи. Выделяют два типа ТЗ:  открытая ТЗ и закрытая ТЗ.

Транспортная задача называется закрытой, если выполняется условие баланса : суммарный объем производства равен суммарному объему потребления:

.                                        (3.1)

Следнет обратить внимание на то, что математическая модель задает закрытую транспортную задачу. 

Открытая ТЗ имеет место в двух случаях.

Первый случай. Суммарный объем производства меньше суммарного объема потребления:

.                                      (3.2)

Известно, что для существования допустимого решения транспортной задачи необходимо и достаточно, чтобы задача была закрытой. Поэтому транспортную задачу открытого типа предварительно необходимо свести к закрытой, для чего вводится фиктивный пункт производства с номером m+1 с объемом производства:

,                              (3.3)

при этом полагают  .

Второй случай. Суммарный объем производства больше суммарного объема потребления:

.                                     (3.4)

Для сведения ТЗ к закрытому типу вводят фиктивный пункт потребления с номером n+1 с объемом потребления:

,                               (3.5)

при этом полагают  .

Методы решения.

·     Как задача линейного программирования ТЗ может быть решена симплекс методом [4].

·     Также разработаны специальные (более эффективные) методы решения транспортной задачи: обобщенный венгерский метод [4]; метод северо-западного угла, метод минимального элемента для нахождения опорного плана; метод потенциалов для нахождения оптимального плана [3].