Тема 4. Транспортная задача

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

Обычно начальные условия записываются в исходную транспортную таблицу:

В таблице a_ij означают затраты на перевозку одной единицы груза от i - го поставщика (i=1,2,...,k) к j - му потребителю (j=1,2,...l), M_i - мощность i-го поставщика в планируемый период, N_j - спрос j -го потребителя в этот же период.

Обозначим x_ij количество груза, которое нужно перевезти от i -го поставщика к j -му потребителю. Математическая модель задачи сведется к нахождению минимума функции цели, выражающей суммарные затраты на перевозки груза, т.е. функции F= при следующих ограничениях:

Решение транспортной задачи может быть найдено так называемым распределительным методом.

Задача 4. Исходная таблица транспортной задачи:

Методические указания к решению

Задачи, в которых SA_i= S B_j, называются закрытыми. Если это условие не выполняется, то задача открытая, и ее необходимо сделать закрытой, добавив соответственно фиктивного поставщика или потребителя со стоимостями перевозок равными 0.

Поскольку SA_i=50+70+80=200, а S B_j = 20+100+60+50=230, следует ввести дополнительного, фиктивного поставщика мощностью 30.

После этого следует определить исходный (отправной) план перевозок любым из двух методов: метод северо-западного угла; метод минимального элемента. Покажем применение каждого из этих методов.

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

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

Последовательно заполняем объемы поставок, начиная с верхнего левого угла (северо-западного). Затем проверяем баланс (суммы по колонкам и столбцам). Если план построен правильно, то для каждой свободной клетки можно построить цикл, т.е. замкнутый контур с прямыми углами, такой, чтобы начинаясь в свободной клетке, он проходил через заполненные клетки. Вид этого контура может быть различным. Например:

Кроме того, число занятых клеток должно быть m+n -1.

В данном случае это условие не соблюдается - число занятых клеток должно быть 4+4-1=7, а в таблице их только 6. Следует в любую пустую клетку вписать 0, выбирая сначала клетки с минимальными стоимостями, но так, чтобы для нее нельзя было построить цикл. В нашем случае нельзя вписать в клетки A₂B₁ и A₄B₃, а во все остальные - можно. Выберем клетку со стоимостью 1 A₂B₃. Теперь в таблице 7 заполненных клеток.

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

S= 20*1+ 30*3+70*5+ 0*1+60*3+20*4+30*0=720 (руб)