183523 (584664), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Задача №3

Решить методом потенциалов транспортную задачу, где – цена перевозки единицы груза из пункта в пункт .

Решение

Поскольку суммарные запасы = 35 (ед. груза) и суммарные потребности = 48 (ед. груза) не совпадают (т.е. мы имеем дело с открытой транспортной задачей), необходимо ввести фиктивный пункт производства . Тогда транспортная матрица будет иметь следующий вид (табл.1).

Таблица 1- Общий вид транспортной матрицы

Пункты производства, i	Пункты потребления, j				Объем производства
	1	2	3	4
1	6	8	4	2		10
2	5	6	9	8		10
3	4	2	3	8		15
4	0	0	0	0		13
Объем потребления (спрос)	5	8	15	20		48

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

Таблица 2 – Транспортная матрица с опорным планом северо-западного угла

Пункты производства, i	Пункты потребления, j					Объем производства
	1	2	3	4
1	6 5	8 5	4 -	2 -	10/5/0
2	5 -	6 3	9 7	8 -	10/7/0
3	4 -	2 -	3 8	8 7	15/7/0
4	0 -	0 -	0 -	0 13	13/0
Объем потребления	5/0	8/3/0	15/8/0	20/13/0	48

Опорный план , найденный методом северо-западного угла имеет вид:

(ед. груза) или = (5; 5; 0; 0; 0; 3; 7;0;0;0;8;7;0;0;0;13).

Целевая функция, выражающая общие затраты на перевозку, будет иметь вид: (ден. ед.).

Итерация 1.

Шаг 1.1. Вычисление потенциалов

	6 5	8 5	4 -	2 -	u1=0
	5 -	6 3	9 7	8 -	u2=2
	4 -	2 -	3 8	8 7	u3=8
	0 -	0 -	0 -	0 13	u4=16
	v1=6	v2=8	v3=11	v4=16

Система для плана имеет вид:

Полагая u₁=0, находим значения всех потенциалов: v₁=6, v₂=8, u₂=2,v₃=11, v₄=16, u₃=8, u₄=16, т.е. (0; 2; 8; 16; 6; 8; 11; 16).

Шаг 1.2. Проверка на оптимальность. Составляем таблицу оценок .

	0	0	7	14	u1=0
	-1	0	0	6	u2=2
∆1=	-6	-2	0	0	u3=8
	-10	-8	-5	0	u4=16
	v1=6	v2=8	v3=11	v4=16

Так как имеются >0, то переходим к шагу 3.

Шаг 1.3. Составление нового плана перевозок. соответствует клетка К₁₄.

	- 8 5	4 -	+2 -
	+6 3	- 9 7	8 -
∆1=	2 -	+3 8	- 8 7
	0 -	0 -	0 13

Θ = = 5. Составим новый план перевозки.

Итерация 2.

Шаг 2.1. Вычисление потенциалов

	6 5	8 -	4 -	2 5	u1=0
	5 -	6 8	9 2	8 -	u2=-12
	4 -	2 -	3 13	8 2	u3=-6
	0 -	0 -	0 -	0 13	u4=2
	v1=6	v2=-6	v3=-3	v4=2

Система для плана имеет вид:

Полагая u₁=0, находим значения всех потенциалов: v₁=6, v₂=-6, u₂=-12,v₃=-3, v₄=2, u₃=-6, u₄=2, т.е. (0; -12; -6; 2; 6; -6; -3; 2).

Шаг 2.2. Проверка на оптимальность. Составляем таблицу оценок .

	0	-14	-7	0	u1=0
	13	0	0	6	u2=-12
∆1=	8	-2	0	0	u3=-6
	4	-8	-5	0	u4=2
	v1=6	v2=-6	v3=-3	v4=2

Так как имеются >0, то переходим к шагу 3.

Шаг 1.3. Составление нового плана перевозок. соответствует клетка К₂₁.

	-6 5	8 -	4 -	+2 5
∆1=	+5 -	6 8	-9 2	8 -
	4 -	2 -	+3 1 3	-8 2

Θ = = = 2. Возьмем и составим новый план перевозки.

Итерация 3.

Шаг 3.1. Вычисление потенциалов

	6 3	8 -	4 -	2 7	u1=0
	5 2	6 8	9 0	8 -	u2=1
	4 -	2 -	3 15	8 -	u3=7
	0 -	0 -	0 -	0 13	u4=2
	v1=6	v2=7	v3=10	v4=2

Система для плана имеет вид:

Характеристики

Список файлов ответов (шпаргалок)