Задача 3

Выполнение третьего задания предполагает решение транспортной задачи, включающее:

1. построение математической модели

2. непосредственное решение задачи.

Условие ЗАДАЧИ 3:

		Пункты назначения					Наличие
		В1	В2	В3	В4	В5
Пункты отправления	А1	8	5	7	8	15	460
	А2	3	9	4	6	10	400
	А3	5	2	10	5	12	440
	Потребность	250	180	220	260	390

Решение:

В общем виде формулировка транспортной задачи осуществляется следующим образом: требуется перевезти определенное количество однородного груза из m пунктов отправления в n пунктов назначения. Известны расходы на перевозку единицы груза из каждого пункта отправления в каждый пункт назначения.

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

Для составления экономико-математической модели задачи введем обозначения:

n число пунктов отправления;

m число пунктов назначения;

ai общее количество груза в I-м пункте отправления;

bj общее количество груза, необходимое в j-м пункте назначения;

cij затраты на транспортировку единицы груза из I-го пункта

отправления в j-й пункт назначения;

Z совокупные затраты на перевозку всего груза;

xij исходно неизвестное количество груза, которое перевозится из

i-го пункта отправления в j-й пункт назначения.

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

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

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

Математическая формулировка транспортной задачи такова: найти переменные задачи X=(x_ij), i=1,2,...,m; j=1,2,...,n, удовлетворяющие системе ограничений (цифра 2 на математической модели) , (3), условиям неотрицательности (4) и обеспечивающие минимум целевой функции (1). Целевая функция минимизирует совокупные затраты на транспортировку всех партий грузов из всех пунктов отправления во все пункты назначения. Система ограничений (2)говорит о том, что весь груз из каждого пункта его сосредоточения должен быть вывезен. Система ограничений (3) говорит о том, что потребность в грузе в каждом пункте назначения должна быть удовлетворена. Система ограничений (4) говорит о том, что по любому маршруту некоторое количество груза либо перевозится, либо нет.

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

	Матрица исходных данных
Пункты отправления	Пункты назначения
	B1	B2	B3	B4	B5
	250	180	220	260	390
460	8	5	7	8	15
400	3	9	4	6	10
440	5	2	10	5	12

Вводим переменные задачи (матрицу перевозок):

x₁₁ x₁₂ x₁₃ x₁₄ x₁₅

Х= x₂₁ x₂₂ x₂₃ x₂₄ x₂₅

x₃₁ x₃₂ x₃₃ x₃₄ x₃₅

Записываем матрицу стоимостей:

8 5 7 8 15

C= 3 9 4 6 10

5 2 10 5 12

Целевая функция задачи равняется сумме произведений всех соответствующих элементов матриц C и X.

Z(X)= 8x₁₁ + 5 x₁₂ + 9₇x₁₃ + 8 x₁₄ + 15x₁₅ + 3x₂₁ + 9x₂₂ + 4x₂₃ +6x₂₄+ 10x₂₅ + +5x₃₁ + 2x₃₂ + 10x₃₃ + 5x₃₄ + 12x₃₅

Составим систему ограничений задачи. Сумма всех перевозок, стоящих в первой строке матрицы X, должна равняться запасам первого поставщика, а сумма перевозок во второй строке матрицы X равняться запасам второго поставщика:

x₁₁ + x₁₂ + x₁₃ + x₁₄ + x₁₅ = 460

x₂₁ + x₂₂ + x₂₃ + x₂₄ + x₂₅ = 400

x₃₁ + x₃₂ + x₃₃ + x₃₄ + x₃₅ = 440

Это означает, что запасы поставщиков вывозятся полностью.

Суммы перевозок, стоящих в каждом столбце матрицы X, должны быть равны запросам соответствующих потребителей:

x₁₁ + x₂₁ + x₃₁ = 250

x₁₂ + x₂₂ + x₃₂ =180

x₁₃ + x₂₃ + x₃₃ =220

x₁₄ + x₂₄ + x₃₄ =260

x₁₅ + x₂₅ + x₃₅ =390

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

X_iy >=0, i=1, 2,…, m; j=1, 2…, n

Для решения задачи средством EXCEL «Поиск решения» необходимо разместить в рабочем листе исходные данные и подготовить поля для размещения условий и результатов решения задачи (выбор ячеек листа произвольный). Таким образом, будет создана «Электронная модель транспортной задачи».

Матрица оптимальных перевозок Потребители Поставщики В1 В2 В3 В4 В5 Итог по поставщикам А1 1 1 1 1 1 5 А2 1 1 1 1 1 5 А3 1 1 1 1 1 5 Итог по потребителям 3 3 3 3 3 Матрица исходных данных Мощности поставщиков (ai) Мощность потребителей (bj) 250 180 220 260 390 460 8 5 7 8 15 400 3 9 4 6 10 440 5 2 10 5 12 Целевая функция 109

В матрице результата во все ячейки диапазона (B6:F8) внести «1» в качестве исходных значений объемов поставок xij, после решения задачи в этих ячейках будут находиться значения поставок, обеспечивающие минимальные затраты на перевозку груза.

Вводим в ячейки (В9;F9) итог поставок по потребителям: в ячейку В9 ввести формулу =СУММ(В6:В8) − итог поставок по1-му потребителю, скопировать эту формулу в ячейки (С9:Е9);

Вводим в ячейки (G6:G8) итоги реализации мощности каждого из поставщиков: в ячейку G6 ввести формулу =СУММ(В6:F8) − итог реализации поставок от 1-го поставщика, скопировать эту формулу в ячейки (G7:G9);

Выделяем ячейку для ввода формулы целевой функции, в этом случае В21 и ввести формулу =СУММПРОИЗВ(В16:F18;В6:F8) − суммарная стоимость перевозок по всем направлениям.

В окне Поиск решения указываем целевую ячейку В21 равную минимальному значению, а также вводим ограничения. Окно Поиска решения будет выглядеть следующим образом:

После проведенной подготовительной работы можно запустить задачу на выполнение. В результате решения ячейки (В6:F8) заполнились значениями объемов перевозок, которые обеспечивают минимальные суммарные затраты на транспортировку всего груза:

	Матрица оптимальных перевозок
	Потребители
Поставщики	В1	В2	В3	В4	В5	Итог по поставщикам
А1	250	0	0	40	170	460
А2	0	180	0	220	0	400
А3	0	0	220	0	220	440
Итог по потребителям	250	180	220	260	390
	Матрица исходных данных
Мощности поставщиков (ai)	Мощность потребителей (bj)
	250	180	220	260	390
460	8	5	7	8	15
400	3	9	4	6	10
440	5	2	10	5	12
Целевая функция	12650

Целевая функция минимизирует совокупные затраты на транспортировку всех партий грузов из всех пунктов отправления во все пункты назначения. Величина затрат равна 12650 единицам.