Построение опорного плана транспортной задачи.

Методы решения транспортной задачи сводятся к простым операциям с транспортной таблицей, которая имеет вид:                                                 

Базисными клетками транспортной таблицы являются клетки с от-

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

            1) сумма перевозок в каждой строке равна запасу в данной

строке;

            2) сумма перевозок в каждом столбце равна соответствующему

столбцу спросу

                                              

            Опорный план транспортной задачи содержит не более n+m-1

отличных от нуля перевозок

                                              

            Опорный план называется вырожденным, если число ненулевых перевозок

                                              

 меньше и n+m-1, опорный план - невырожден, если число

ненулевых перевозок равно n+m-1.

            Рассмотрим способы построения опорного плана в невырожденном и вырожденном случаях.

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

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

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

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

           

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

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

                                  

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

                                  

           

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

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

                                  

           

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

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

                       

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

                                  

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

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

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

Разработка основных алгоритмов решения задачи

1 Алгоритм решения транспортной задачи

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

2. Построить начальное опорное решение (методом северо-западного угла), проверить правильность его построения по количеству занятых клеток (их должно быть m+n-1).

3. Построить систему, соответствующую опорному решению.

4. Проверить выполнения условия оптимальности.

5. Перейти к опорному решению, на котором значение целевой функции будет меньше. Для этого находят клетку таблицы задачи, которой соответствует наибольшая положительная оценка

Строят цикл, включающий в свой состав данную клетку и часть клеток, занятых опорным решением. В клетках цикла расставляют поочередно знаки «+» и «-», начиная с «+» в клетке с наибольшей положительной оценкой. Осуществляют сдвиг (перераспределение груза) по циклу на величину . Клетка со знаком «-», в которой достигается остается пустой. Если минимум достигается в нескольких клетках, то одна из них остается пустой, а в остальных проставляют базисные нули, чтобы число занятых клеток оставалось равным .

Далее перейти к пункту 3 данного алгоритма.