Ручной способ решения задачи

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

					Запасы
Потребности

Проверим необходимое и достаточное условие разрешимости задачи.

∑a = 19 + 8 + 25 + 14 = 66

∑b = 32 + 8 + 25 + 1 = 66

Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.

Занесем исходные данные в распределительную таблицу.

					Запасы
Потребности

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

1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел a_i, или b_j.

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

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

Искомый элемент равен 4

Для этого элемента запасы равны 25, потребности 8. Поскольку минимальным является 8, то вычитаем его.

x₃₂ = min(25,8) = 8.

	x
	x
				25 - 8 = 17
	x
	8 - 8 = 0

Искомый элемент равен 6

Для этого элемента запасы равны 14, потребности 32. Поскольку минимальным является 14, то вычитаем его.

x₄₁ = min(14,32) = 14.

	x
	x
	x	x	x	14 - 14 = 0
32 - 14 = 18

Искомый элемент равен 7

Для этого элемента запасы равны 19, потребности 18. Поскольку минимальным является 18, то вычитаем его.

x₁₁ = min(19,18) = 18.

	x			19 - 18 = 1
x	x
x
	x	x	x
18 - 18 = 0

Искомый элемент равен 7

Для этого элемента запасы равны 17, потребности 1. Поскольку минимальным является 1, то вычитаем его.

x₃₄ = min(17,1) = 1.

	x		x
x	x		x
x				17 - 1 = 16
	x	x	x
			1 - 1 = 0

Искомый элемент равен 11

Для этого элемента запасы равны 8, потребности 25. Поскольку минимальным является 8, то вычитаем его.

x₂₃ = min(8,25) = 8.

	x		x
x	x		x	8 - 8 = 0
x
	x	x	x
		25 - 8 = 17

Искомый элемент равен 14

Для этого элемента запасы равны 1, потребности 17. Поскольку минимальным является 1, то вычитаем его.

x₁₃ = min(1,17) = 1.

	x		x	1 - 1 = 0
x	x		x
x
	x	x	x
		17 - 1 = 16

Искомый элемент равен 30

Для этого элемента запасы равны 16, потребности 16. Поскольку минимальным является 16, то вычитаем его.

x₃₃ = min(16,16) = 16.

	x		x
x	x		x
x				16 - 16 = 0
	x	x	x
		16 - 16 = 0

					Запасы
	7[18]		14[1]
			11[8]
		4[8]	30[16]	7[1]
	6[14]
Потребности

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

2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 7*18 + 14*1 + 11*8 + 4*8 + 30*16 + 7*1 + 6*14 = 831

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

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

u₁ + v₁ = 7; 0 + v₁ = 7; v₁ = 7

u₄ + v₁ = 6; 7 + u₄ = 6; u₄ = -1

u₁ + v₃ = 14; 0 + v₃ = 14; v₃ = 14

u₂ + v₃ = 11; 14 + u₂ = 11; u₂ = -3

u₃ + v₃ = 30; 14 + u₃ = 30; u₃ = 16

u₃ + v₂ = 4; 16 + v₂ = 4; v₂ = -12

u₃ + v₄ = 7; 16 + v₄ = 7; v₄ = -9

	v1=7	v2=-12	v3=14	v4=-9
u1=0	7[18]		14[1]
u2=-3			11[8]
u3=16		4[8]	30[16]	7[1]
u4=-1	6[14]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij

(3;1): 16 + 7 > 8; ∆₃₁ = 16 + 7 - 8 = 15

Выбираем максимальную оценку свободной клетки (3;1): 8

Для этого в перспективную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

					Запасы
	7[18][-]		14[1][+]
			11[8]
	8[+]	4[8]	30[16][-]	7[1]
	6[14]
Потребности

Цикл приведен в таблице (3,1; 3,3; 1,3; 1,1;).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 16. Прибавляем 16 к объемам грузов, стоящих в плюсовых клетках и вычитаем 16 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

					Запасы
	7[2]		14[17]
			11[8]
	8[16]	4[8]		7[1]
	6[14]
Потребности

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

u₁ + v₁ = 7; 0 + v₁ = 7; v₁ = 7

u₃ + v₁ = 8; 7 + u₃ = 8; u₃ = 1

u₃ + v₂ = 4; 1 + v₂ = 4; v₂ = 3

u₃ + v₄ = 7; 1 + v₄ = 7; v₄ = 6

u₄ + v₁ = 6; 7 + u₄ = 6; u₄ = -1

u₁ + v₃ = 14; 0 + v₃ = 14; v₃ = 14

u₂ + v₃ = 11; 14 + u₂ = 11; u₂ = -3

	v1=7	v2=3	v3=14	v4=6
u1=0	7[2]		14[17]
u2=-3			11[8]
u3=1	8[16]	4[8]		7[1]
u4=-1	6[14]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i <= c_ij.

Минимальные затраты составят:

F(x) = 7*2 + 14*17 + 11*8 + 8*16 + 4*8 + 7*1 + 6*14 = 591