Министерство образования и науки РФ

Министерство образования и науки РФ

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

Кафедра ИТАС

Контрольная работа

по дисциплине «Системный анализ и исследование операций»

Транспортная задача

Вариант 26

Выполнил

студент группы АСУбз-10-2у

Субботин С. А.

Проверил

преподаватель

Рустамханова Г. И.

Пермь, 2012

Решить задачу транспортного типа (Т-задачу) методом потенциалов.

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

bj ai

Найдем опорный план транспортной задачи по правилу северо-западного угла.

Поставщик	Потребитель	Запасы груза
В1	В2	В3
А1
А2
А3
А4
Потребность в грузе				105 / 197

Транспортная задача является открытой, т.к. запас груза больше потребностей на 92 единицы. Приведем задачу к закрытому типу – введем фиктивного потребителя B4.

Поставщик	Потребитель	Запасы груза
В1	В2	В3	В4
А1	4	7	3
А2			13
А3			9	0
А4
Потребность в грузе

Решение: Опорный план перевозок найдем, например, по правилу северо-западного угла. Полученный план невырожденный. Число занятых клеток r=m+n-1=4+4-1=7.

Значение критерия:

L₀ = 18*4+37*7+5*3+42*13+3*9+17*0+75*0=919

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

Определим потенциалы всех пунктов в начальном плане u_i и v_j ( - = ):

v1 - u1 = 4;

v2 – u1 = 7;

v3 – u1 = 3;

v3 – u2 = 13;

v3 – u3 = 9;

v4 – u3 = 0;

v4 – u4 = 0;

Полагая, например, u1=0, находим остальные потенциалы:

v₁=4; v2=7; v3=3; u2= -10; u3= -6; v4= -6; u4= -6

Вычисляем для свободных клеток:

∆21=v1-u2-c21=4+10-9=5

∆31=v1-u3-c31=4+6-11= -1

∆41=v1-u4-c41=4+6-7=3

∆22=v2-u2-c22=7+10-5=12

∆32=v2-u3-c32=7+6-8=5

∆42=v2-u4-c42=7+6-12=1

∆43=v3-u4-c43=3+6-20= -11

∆14=v4-u1-c14= -6-0-0= -6

∆24=v4-u2-c24= -6+10+0=4

∆(0)=				-6
-1
		-11

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

Строим цикл на той клетке, где самая большая оценка. Это клетка (2,2)

x(0)=		37	5
	0	42

Получится цикл из 4 вершин

x₁₂=37 x₁₃=5 x₂₂=0 x₂₃=42

Ө₀=min x_ij, ij-индексы нечетных вершин

Ө₀=min (x₁₂, x₂₃)=37

Перемещаем Ө₀ по циклу: в нечетных вершинах вычитаем Ө₀, а в четных – прибавляем Ө₀ и получим новый план перевозок:

X₁₂=0

x₁₃=42

x₂₂=37

x₂₃=5

x(1)=

L1=L0 - Ө₀*∆22=919-37*12=475

первая итерация улучшила критерий на 444 единицы.

Преобразуя матрицу D⁽⁰⁾ по решению x⁽¹⁾, находим новую матрицу оценок:

∆(0)=				-6	-12
				-12
-1				-12
		-11		-12
	+12		+12	+12
∆(1)=		-12		-6
-1	-8
	-11	-11

Есть положительные оценки в D⁽¹⁾ , оптимальное значение не получено. Строим новый цикл в клетке с самой большой оценкой (2,1):

x(1)=	18		42
0		5

Ө₀=min (x₁₁, x₂₃)=5

x₁₁=18-5=13

x₁₃=42+5=47

x₂₃=5-5=0

x₂₁=0+5=5

x(2)=

Общие затраты на доставку всей продукции, для данного решения составляют

L2=L1- Ө₀*∆34=525-10*5=475

∆(1)=		-12		-6
				-5
-1	-8
	-11	-11
		+5

∆(2)=		-7		-6
		-5	-1
-1	-3
	-6	-11

Есть положительные оценки в D⁽²⁾ , оптимальное значение не получено. Строим новый цикл в клетке с самой большой оценкой (4,1):

x(2)=	13		47
		3	17
0			75

Ө₀=min (x₁₁, x₃₃, x₄₄)=3

x(3)=

Общие затраты на доставку всей продукции, для данного решения составляют

475-3*5=450

∆(2)=		-7		-6	-3
		-5	-1
-1	-3			-3
	-6	-11		-3
			+3	+3
∆(3)=	-3	-10		-6
		-2
-4	-6
	-9	-11

Есть положительные оценки в D⁽²⁾ , оптимальное значение не получено. Строим новый цикл в клетке с самой большой оценкой (2,4):

x(3)=
5			0
3			72

Ө₀=min (x₂₁, x₄₄)=5

x(4)=

Общие затраты на доставку всей продукции, для данного решения составляют

∆(3)=	-3	-10		-6
0		-2		-2
-4	-6
0	-9	-11		-2
	+2	+2

∆(4)=	-1	-8		-6
		-4
-2	-4
	-9	-13	-2

Дата добавления: 2015-09-29