Задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления

Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).

Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку).

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

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

W=23*14+10*2+11*17+4*16+7*7+11*15+7*22+27*10=1231

Метод минимального элемента

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

W=23*14+10*2+15*2+11*3+11*7+3*15+8*23+19*10=901

Метод двойного предпочтения

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

W=8*14+25*2+11*3+11*7+8*19+3*15+7*23+27*10=900

Метод потенциалов

Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче.

            Заполним таблицу методом северо-западного угла. Потенциал строки или столбца с наибольшим количеством элементов примем равным нулю. Подсчитаем потенциалы по заполненным ячейкам, используя формулу c_ij=u_i+v_j, где c_ij – стоимость перевозки единицы груза, u_i – потенциал строки, v_j – потенциал столбца. Уменьшаем стоимость транспортировки, перемещая груз в ячейки с наименьшими стоимостями.  Повторяем цикл до тех пор, пока во всех пустых клетках не будет выполняться условие c_iju_i+v_j .