Транспортная задача. Усов Михаил

Транспортная задача. Усов Михаил

Математическая модель транспортной задачи:

F = ∑∑c_ijx_ij, (1)

при условиях:

∑x_ij = a_i, i = 1,2,…, m, (2)

∑x_ij = b_j, j = 1,2,…, n, (3)

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

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

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

∑a = 600 + 400 + 700 = 1700

∑b = 400 + 300 + 800 + 200 = 1700

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

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

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

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

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

План начинается заполняться с верхнего левого угла.

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

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

x₁₁ = min(600,400) = 400.

				600 - 400 = 200
x
x
400 - 400 = 0

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

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

x₁₂ = min(200,300) = 200.

		x	x	200 - 200 = 0
x
x
	300 - 200 = 100

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

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

x₂₂ = min(400,100) = 100.

		x	x
x				400 - 100 = 300
x	x
	100 - 100 = 0

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

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

x₂₃ = min(300,800) = 300.

		x	x
x			x	300 - 300 = 0
x	x
		800 - 300 = 500

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

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

x₃₃ = min(700,500) = 500.

		x	x
x			x
x	x			700 - 500 = 200
		500 - 500 = 0

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

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

x₃₄ = min(200,200) = 200.

		x	x
x			x
x	x			200 - 200 = 0
			200 - 200 = 0

					Запасы
	4[400]	40[200]
		7[100]	3[300]
			6[500]	2[200]
Потребности

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

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

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

F(x) = 4*400 + 40*200 + 7*100 + 3*300 + 6*500 + 2*200 = 14600

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

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

u₁ + v₁ = 4; 0 + v₁ = 4; v₁ = 4

u₁ + v₂ = 40; 0 + v₂ = 40; v₂ = 40

u₂ + v₂ = 7; 40 + u₂ = 7; u₂ = -33

u₂ + v₃ = 3; -33 + v₃ = 3; v₃ = 36

u₃ + v₃ = 6; 36 + u₃ = 6; u₃ = -30

u₃ + v₄ = 2; -30 + v₄ = 2; v₄ = 32

	v1=4	v2=40	v3=36	v4=32
u1=0	4[400]	40[200]
u2=-33		7[100]	3[300]
u3=-30			6[500]	2[200]

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

(1;3): 0 + 36 > 6; ∆₁₃ = 0 + 36 - 6 = 30

(1;4): 0 + 32 > 8; ∆₁₄ = 0 + 32 - 8 = 24

(3;2): -30 + 40 > 8; ∆₃₂ = -30 + 40 - 8 = 2

max(30,24,2) = 30

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

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

					Запасы
	4[400]	40[200][-]	6[+]
		7[100][+]	3[300][-]
			6[500]	2[200]
Потребности

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

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

					Запасы
	4[400]		6[200]
		7[300]	3[100]
			6[500]	2[200]
Потребности

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

u₁ + v₁ = 4; 0 + v₁ = 4; v₁ = 4

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

u₂ + v₃ = 3; 6 + u₂ = 3; u₂ = -3

u₂ + v₂ = 7; -3 + v₂ = 7; v₂ = 10

u₃ + v₃ = 6; 6 + u₃ = 6; u₃ = 0

u₃ + v₄ = 2; 0 + v₄ = 2; v₄ = 2

	v1=4	v2=10	v3=6	v4=2
u1=0	4[400]		6[200]
u2=-3		7[300]	3[100]
u3=0			6[500]	2[200]

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

(3;2): 0 + 10 > 8; ∆₃₂ = 0 + 10 - 8 = 2

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

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

					Запасы
	4[400]		6[200]
		7[300][-]	3[100][+]
		8[+]	6[500][-]	2[200]
Потребности

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

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

					Запасы
	4[400]		6[200]
			3[400]
		8[300]	6[200]	2[200]
Потребности

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

u₁ + v₁ = 4; 0 + v₁ = 4; v₁ = 4

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

u₂ + v₃ = 3; 6 + u₂ = 3; u₂ = -3

u₃ + v₃ = 6; 6 + u₃ = 6; u₃ = 0

u₃ + v₂ = 8; 0 + v₂ = 8; v₂ = 8

u₃ + v₄ = 2; 0 + v₄ = 2; v₄ = 2

	v1=4	v2=8	v3=6	v4=2
u1=0	4[400]		6[200]
u2=-3			3[400]
u3=0		8[300]	6[200]	2[200]

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

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

F(x) = 4*400 + 6*200 + 3*400 + 8*300 + 6*200 + 2*200 = 8000

Анализ оптимального плана.

Из 1-го склада необходимо груз направить в 1-й магазин (400), в 3-й магазин (200)

Из 2-го склада необходимо весь груз направить в 3-й магазин

Из 3-го склада необходимо груз направить в 2-й магазин (300), в 3-й магазин (200), в 4-й магазин (200)

Задача имеет множество оптимальных планов, поскольку оценка для (3;1) равна 0.

Дата добавления: 2015-10-21