Анализ оптимального плана транспортной задачи

Задание. На трех складах A1, A2 и A3 хранится a1=100, a2=200 и a3=70 единиц одного и того же груза. Этот груз требуется доставить трем потребителям B1, B2 и B3, заказы которых составляют b1=190, b2=120 и b3=10 единиц груза соответственно. Стоимость перевозок cij единицы груза с i-го склада j-му потребителю указаны в правых верхних углах соответствующих клеток транспортной таблицы.
1. Сравнивая суммарный запас a и суммарную потребность b в грузе, установить, является ли модель транспортной задачи, заданная этой таблицей, открытой или закрытой. Если модель является открытой, то ее необходимо закрыть, добавив фиктивный склад A с запасом a в случае a<b или фиктивного потребителя B с потребностью b в случае a>b и положив соответствующие им тарифы перевозок нулевыми.
2. Составить первоначальный план перевозок. (Рекомендуется воспользоваться методом наименьшей стоимости.)
3. Проверить, является ли первоначальный план оптимальным в смысле суммарной стоимости перевозок, и если это так, то составить оптимальный план, обеспечивающий минимальную стоимость перевозок Z. Найти эту стоимость. (Рекомендуется воспользоваться методом потенциалов).

Решение находим с помощью калькулятора. Математическая модель транспортной задачи:
F = ∑∑c_ijx_ij, (1)
при условиях:
∑x_ij = a_i, i = 1,2,…, m, (2)
∑x_ij = b_j, j = 1,2,…, n, (3)
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

	1	2	3	Запасы
1	4	2	1	100
2	1	5	3	200
3	1	2	6	70
Потребности	190	120	10

Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 100 + 200 + 70 = 370
∑b = 190 + 120 + 10 = 320
Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным 50 (370—320). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.
Занесем исходные данные в распределительную таблицу.

	1	2	3	4	Запасы
1	4	2	1	0	100
2	1	5	3	0	200
3	1	2	6	0	70
Потребности	190	120	10	50

Этап I. Поиск опорного плана

1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел a_i, или b_j.
Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.
Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Искомый элемент равен 1
Для этого элемента запасы равны 100, потребности 10. Поскольку минимальным является 10, то вычитаем его.
x₁₃ = min(100,10) = 10.

4	2	1	0	100 - 10 = 90
1	5	x	0	200
1	2	x	0	70
190	120	10 - 10 = 0	50	0

Искомый элемент равен 1
Для этого элемента запасы равны 200, потребности 190. Поскольку минимальным является 190, то вычитаем его.
x₂₁ = min(200,190) = 190.

x	2	1	0	90
1	5	x	0	200 - 190 = 10
x	2	x	0	70
190 - 190 = 0	120	0	50	0

Искомый элемент равен 2
Для этого элемента запасы равны 90, потребности 120. Поскольку минимальным является 90, то вычитаем его.
x₁₂ = min(90,120) = 90.

x	2	1	x	90 - 90 = 0
1	5	x	0	10
x	2	x	0	70
0	120 - 90 = 30	0	50	0

Искомый элемент равен 2
Для этого элемента запасы равны 70, потребности 30. Поскольку минимальным является 30, то вычитаем его.
x₃₂ = min(70,30) = 30.

x	2	1	x	0
1	x	x	0	10
x	2	x	0	70 - 30 = 40
0	30 - 30 = 0	0	50	0

Искомый элемент равен 0
Для этого элемента запасы равны 10, потребности 50. Поскольку минимальным является 10, то вычитаем его.
x₂₄ = min(10,50) = 10.

x	2	1	x	0
1	x	x	0	10 - 10 = 0
x	2	x	0	40
0	0	0	50 - 10 = 40	0

Искомый элемент равен 0
Для этого элемента запасы равны 40, потребности 40. Поскольку минимальным является 40, то вычитаем его.
x₃₄ = min(40,40) = 40.

x	2	1	x	0
1	x	x	0	0
x	2	x	0	40 - 40 = 0
0	0	0	40 - 40 = 0	0

	1	2	3	4	Запасы
1	4	2[90]	1[10]	0	100
2	1[190]	5	3	0[10]	200
3	1	2[30]	6	0[40]	70
Потребности	190	120	10	50

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 2*90 + 1*10 + 1*190 + 0*10 + 2*30 + 0*40 = 440

Этап II. Улучшение опорного плана

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.
u₁ + v₂ = 2; 0 + v₂ = 2; v₂ = 2
u₃ + v₂ = 2; 2 + u₃ = 2; u₃ = 0
u₃ + v₄ = 0; 0 + v₄ = 0; v₄ = 0
u₂ + v₄ = 0; 0 + u₂ = 0; u₂ = 0
u₂ + v₁ = 1; 0 + v₁ = 1; v₁ = 1
u₁ + v₃ = 1; 0 + v₃ = 1; v₃ = 1

	v₁=1	v₂=2	v₃=1	v₄=0
u₁=0	4	2[90]	1[10]	0
u₂=0	1[190]	5	3	0[10]
u₃=0	1	2[30]	6	0[40]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j <= c_ij.
Минимальные затраты составят:
F(x) = 2*90 + 1*10 + 1*190 + 0*10 + 2*30 + 0*40 = 440