Пример 2. Пусть имеется 3 поставщика и 4 потребителя

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

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

Таблица 4.2

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

Решение

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

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

Таблица 4.3

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

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

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

Построим систему потенциалов на основе равенства

V_j = U _i + c_ij.

Присвоим первому поставщику потенциал 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. Вычисленные потенциалы помещаем в табл. 3.9.

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

U _i + c_ij ³ 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

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

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

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

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

Последовательное улучшение плана представлено в табл. 4.4–4.6.

Таблица 4.4.

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

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

Таблица 4.5.

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

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

Таблица 4.6.

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