Закрепление потребителей однородного груза за поставщиками

Задача оптимизации закрепления потребителей однородного груза за поставщиками может быть решена любым из известных методов, например, методом МОДИ [3, 4, 5, 8]. Сущность этого метода состоит в следующем. Вначале строится какой-либо план перевозок, который по специальным правилам проверяется на оптимальность. Если он не оптимален, то строится новый улучшенный план. Таким образом, за конечное число шагов может быть получен искомый оптимальный план.

Первоначальный (опорный) план целесообразно получить методом «двойного предпочтения» [5]. Для этого по каждой строке и по каждому столбцу отмечается знаком * клетка с минимальным расстоянием. В табл. 1 клетки БЗ и ГВ имеют одновременно два знака **. Их загружают в первую очередь (у поставщика Б имеется 210 т, а потребителю З требуется 50 т, следовательно, в клетку БЗ проставляем 50 т и т.д.). Далее проставляем загрузку в клетки, имеющие одну отметку * (140 т в клетку АВ). Оставшуюся загрузку распределяем по свободным клеткам (потребителю И 20 т завезем от поставщика Б; потребителю И завезем оставшиеся 20 т от поставщика Г). Таким образом, в полученном опорном плане от всех поставщиков имеющийся груз вывезен, всем потребителям завезено все, что им требуется. При этом опорный план должен удовлетворять двум условиям:

1. Ацикличности, то есть в таблице нельзя построить замкнутый цикл, все вершины которого лежат в загруженных клетках.

Число загруженных клеток должно быть равно:

Nзаг = m + n – 1, (2.1)

где m – число поставщиков;

n – число потребителей.

В моем случае опорный план не удовлетворяет 2 условию, определить все потенциалы ui и vj невозможно. Поэтому недостающее количество клеток загружаю нулевой загрузкой.

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

В моем случае нулевую загрузку размещаю в клетке АЗ.

Теперь опорный план, представленный в табл. 3, обоим этим условиям удовлетворяет.

Таблица 2 – Первоначальный (опорный) план для решения задачи оптимизации закрепления потребителей за поставщиками