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

1. Построение исходного опорного плана.

2. Оценка полученного плана.

3. Переход от имеющегося опорного плана к новому опорному плану с меньшими транспортными затратами.

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

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

2. Записать условие задачи в виде транспортной таблицы.

3. Построить начальный опорный план перевозок.

4. Вычислить потенциалы.

5. Вычислить оценки свободных клеток и оценить оптимальность плана.

6. Если план оптимальный – закончить расчеты. Если не оптимальный – построить новый опорный план и перейти к п.4.

Основные определения.

Циклом в транспортной задаче называют набор клеток, в котором две и только две клетки расположены в одной строке или в одном столбце, и последняя клетка набора лежит в той же строке или столбце, что и первая 

План транспортной задачи является опорным тогда и только тогда, когда из занятых им  m+n-1 клеток нельзя образовать ни оного цикла.

Построение опорного плана.

Выбирается клетка в транспортной таблице. В выбранную клетку записывается максимально возможная величина поставки. При этом либо исчерпывается запас груза у поставщиков (“закрывается строка”), либо полностью удовлетворяется спрос потребителя (“закрывается столбец”). Соблюдение этого требования обеспечит заполнение m+n-1  клеток.

Основные способы построения опорного плана:

1. Способ “Северо-западного угла”: Первой загружается клетка(1;1) ; Если закрывается строка , то следующей загружается клетка (2;1); Если закрывается столбец, то следующей загружается(1;2) ; Далее загружается клетка соседняя либо по строке, либо по столбцу; Процесс заканчивается, когда распределяют весь груз.

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

3. Способ Фогеля.

Преобразование опорного плана в другой опорный план.

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

Решения транспортной задачи методом потенциалов.

Каждому поставщику (каждой строке) ставят в соответствие число u-i, называемое потенциалом поставщика. Каждому потребителю (каждому столбцу) ставят в соответствие некоторое число v-j, называемое потенциалом потребителя. Числа u-i и v-j выбирают так, чтобы в любой загруженной клетке их сумма равнялась тарифу  . Решают систему из m_n-1 уравнений с m+n неизвестными, одному из потенциалов дают произвольное значение (обычно 0), а другие определяют однозначно. Определяют оценки свободных клеток  .Если все оценки не отрицательные то план оптимальный. Если есть отрицательные оценки, то строят новый опорный план: выбирают клетку с минимальной оценкой  , загружают ее и строят цикл по загруженным клеткам. Получают улучшенный план.