Постановка и методы решения транспортной задачи

Транспортная задача – это задача о выборе плана перевозок однородного продукта из пунктов производства в пункты потребления.

Пусть имеется т пунктов отправления и п пунктов назначения. Запасы продукта в пунктах отправления обозначим через а_i, потребность в продукте в пункте потребления – b_j. Расходы на доставку единицы продукта из i-го пункта отправления в j-й пункт назначения равняются C_{i j}.

Балансовое условие производства и потребления имеет вид

.

Требуется определить x_{i j} – количество продукта, доставляемого от i-го пункта отправления к j-му пункту потребления. При этом обязательными условиями являются: необходимость вывоза всего произведённого продукта, необходимость удовлетворения всех потребителей, оптимальный план доставки продукта должен обеспечить минимум общей суммы затрат на доставку.

Экономико-математическая модель задачи:

.

.

В рассмотренной модели предполагается, что суммарные запасы равны суммарным потребностям. Такая модель называется закрытой. Если это условие не выполняется, то модель называется открытой. Для сведения открытой модели к закрытой вводится или фиктивный пункт отправления или фиктивный пункт назначения.

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

Согласно методу потенциалов, каждому i-му пункту оправления устанавливается потенциал U_i, который можно интерпретировать как цену продукта в пункте отправления, а каждому j-му пункту назначения устанавливается потенциал V_j, который можно условно принять как цену продукта в пункте назначения. В простейшем случае цена продукта в пункте назначения равна его цене в пункте отправления плюс транспортные расходы на его доставку, т.е. V_j=U_i+c_{i j}.

Алгоритм решения транспортной задачи методом потенциалов включает следующие этапы:

1) определение начального плана перевозок с помощью метода северо-западного угла, наименьших стоимостей или аппроксимации Фогеля;

2) построение системы потенциалов на основе равенства V_j = U_i+ c_{i j};

3) проверка начального плана на оптимальность, и в случае его неоптимальности реализация циклов перераспределения плана перевозок.

Третий этап повторяется до тех пор, пока план перевозок не станет оптимальным.

Пример 2.1. Пусть имеется 3 поставщика и 4 потребителя. Запасы продукта у поставщиков, спрос потребителей и транспортные расходы на доставку единицы продукта от i-го поставщика к j-му потребителю заданы (табл.2.1).

Таблица 2.1

Поставщик	Потребитель	Запас
Спрос

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

Решение. Обозначим x_{i j} – количество продукта, доставляемого от i-го поставщика к j-му потребителю. Тогда модель

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

Мы должны заполнить т+п–1 клеток. Если число заполненных клеток меньше т+п–1 (случай вырождения), то недостающие клетки выбираются произвольно и заполняются нулями. Это так называемые условные поставки.

Первоначальный план содержит шесть перевозок: от первого поставщика – 150 ед. к первому потребителю и 20 ед. ко второму; от второго поставщика – 210 ед. ко второму и 40 ед. к третьему; от третьего поставщика – 120 ед. к третьему потребителю и 60 ед. к четвёртому.

Построим систему потенциалов на основе равенства V_j = U_i+ c_{i j}.

Присвоим первому поставщику потенциал U₁=0. От первого поставщика продукт направляют первому и второму потребителю, следовательно, V₁ = U₁+ c₁₁ = 0+3=3; V₂ =0+5=5. Зная потенциал второго потребителя, найдём потенциал второго поставщика U₂ = V₂ – c₂₂ = 5–4=1. Потенциал третьего потребителя V₃ = 1+7=8. Потенциал третьего поставщика U₃ = 8–6=2. Потенциал четвёртого потребителя V₄=2+5=7. Вычисленные потенциалы помещаем в табл.2.2.

Проверим первоначальные план на оптимальность. План считается оптимальным, если для всех свободных ячеек выполняется условие U_i + c_{i j} ³ U_j.

Осуществляем проверку: U₁ + c₁₃ = 0+6=6<8 – не выполняется, т.е. если бы продукт отправлялся от первого поставщика к третьему потребителю, то его цена у первого поставщика была бы ниже, чем в первоначальном плане.

U₁ + c₁₄ = 0+2 = 2 < 7 – не выполняется

U₂ + c₁₁ = 1+6 = 7 ³ 3

U₂ + c₁₄ = 1+5 = 6 < 7 – не выполняется

U₃ + c₁₁ = 2+5 = 7 ³ 3

U₃ + c₁₂ = 2+4 = 6 ³ 5.

Рассчитанные значения заносятся в свободные ячейки табл.2.2.

Для улучшения плана (целевая функция = 2690) необходимо переместить перевозку в ячейку, где условие оптимальности нарушено больше всего, т.е. разность V_j–(U_i+c_{i j}) максимальная (ячейка 1.4).

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

Далее каждой ячейке в связке поочерёдно присваиваются знаки плюс и минус, начиная со свободной. Из ячеек со знаком минус перемещаем перевозки в ячейки со знаком плюс. Чтобы не получить отрицательных перевозок, перемещаем наименьшее количество продукта, которое находится в ячейках связки со знаком минус.

Последовательное улучшение плана представлено в табл.2.2-2.5.

Таблица 2.2

Поставщик	Потребитель	Запас
V1 = 3	V2 = 5	V3 = 8	V4 = 7
1	U1 = 0
	U2 = 1
	U3 = 2
Спрос

Таблица 2.3

Итерация 1. Целевая функция = 2590

Поставщик	Потребитель	Запас
V1 = 3	V2 = 0	V3 = 3	V4 = 2
1	U1 = 0
2	U2 = –4
3	U3 = –3
Спрос

Таблица 2.4

Итерация 2. Целевая функция = 2570

Поставщик	Потребитель	Запас
V1 = 3	V2 = 1	V3 = 3	V4 = 2
1	U1 = 0
	U2 = –3
3	U3 = –3
Спрос

Таблица 2.5

Итерация 3. Целевая функция = 2550

Поставщик	Потребитель	Запас
V1 = 3	V2 = 1	V3 = 4	V4 = 2
	U1 = 0
	U2 = –3
	U3 = –2
Спрос