Транспортная модель открытого типа

Автор работы: Пользователь скрыл имя, 28 Февраля 2014 в 11:52, курсовая работа

Краткое описание

Целью данной работы является решение транспортной задачи в заданных условиях.
В связи с поставленной целью необходимо решить ряд задач:
- построить опорные планы транспортной модели методами северо-западного угла, минимальной стоимости и методом Фогеля;
- произвести оценку полученных решений методом потенциалов;
- сделать выводы по результатам решения.

Содержание

Введение
1. Транспортная модель закрытого типа
1.1 Условие задачи
1.2 Построение опорных планов транспортной модели
1.2.1 Построение опорного плана методом северо-западного угла
1.2.2 Построение опорного плана методом минимальной стоимости
1.2.3 Построение опорного плана методом Фогеля
1.3 Оптимизация транспортной модели закрытого типа
1.3.1 Метод потенциалов на основе опорного плана, построенного методом северо-западного угла
1.3.2 Метод потенциала на основе опорного плана, построенного методом минимальной стоимости
1.3.3 Метод потенциалов на основе опорного плана, построенного методом Фогеля
2. Транспортная модель открытого типа
2.1 Условия задачи
Построение опорных планов транспортной модели
2.2.1 Построение опорного плана методом северо-западного угла
2.2.2 Построение опорного плана методом минимальной стоимости
2.2.3 Построение опорного плана методом Фогеля
2.3 Оптимизация транспортной модели открытого типа
2.3.1 Метод потенциала на основе опорного плана, построенного методом северо-западного угла
2.3.1 Метод потенциала на основе опорного плана, построенного методом минимальной стоимости
2.3.1 Метод потенциала на основе опорного плана, построенного методом Фогеля
Заключение
Список использованных источников

Скачать полностью (75.43 Кб) Сколько стоит заказать работу?

Прикрепленные файлы: 1 файл

ТЗ в8.doc

— 666.00 Кб (Скачать документ)

Произведем оценку полученного решения методом северо-западногоугла.

Каждому поставщику Ai ставим в соответствие некоторое число - ui, называемое потенциалом поставщика.

Каждому потребителю Bj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя.

Для базисной ячеки (задействованного маршрута), сумма потенциалов поставщика и потребителя должна быть равна тарифу данного маршрута.

(ui + vj = cij, где cij - тариф клетки AiBj)

Поскольку, число базисных клеток - 7, а общее количество потенциалов равно 8, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.

Примем v2 = 0.

v2 + u3 = c32

v2 + u3 = 4

u3 = 4 - 0 = 4

v2 + u4 = c42

v2 + u4 = 3

u4 = 3 - 0 = 3

v2 + u5 = c52

v2 + u5 = 0

u5 = 0 - 0 = 0

v3 + u5 = c53

v3 + u5 = 0

v3 = 0 - 0 = 0

v3 + u2 = c23

v3 + u2 = 1

u2 = 1 - 0 = 1

v1 + u2 = c21

v1 + u2 = 3

v1 = 3 - 1 = 2

v1 + u1 = c11

v1 + u1 = 1

u1 = 1 - 2 = -1

Поставщик	Потребитель						U j
	B 1		B 2		B 3
A 1	120		-		-		u 1 = -1
		1		2		9
A 2	105		-		5		u 2 = 1
		3		4		1
A 3	-		20		-		u 3 = 4
		6		4		8
A 4	-		70		-		u 4 = 3
		2		3		3
A 5	-		10		135		u 5 = 0
		0		0		0
V i	v 1 = 2		v 2 = 0		v 3 = 0

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

12 = c12 - ( u1 + v2 ) = 2 - ( -1 + 0 ) = 3

13 = c13 - ( u1 + v3 ) = 9 - ( -1 + 0 ) = 10

22 = c22 - ( u2 + v2 ) = 4 - ( 1 + 0 ) = 3

31 = c31 - ( u3 + v1 ) = 6 - ( 4 + 2 ) = 0

33 = c33 - ( u3 + v3 ) = 8 - ( 4 + 0 ) = 4

41 = c41 - ( u4 + v1 ) = 2 - ( 3 + 2 ) = -3

43 = c43 - ( u4 + v3 ) = 3 - ( 3 + 0 ) = 0

51 = c51 - ( u5 + v1 ) = 0 - ( 0 + 2 ) = -2

Поставщик	Потребитель						U j
	B 1		B 2		B 3
A 1	120		-		-		u 1 = -1
		1	3	2	10	9
A 2	105		-		5		u 2 = 1
		3	3	4		1
A 3	-		20		-		u 3 = 4
	0	6		4	4	8
A 4	-		70		-		u 4 = 3
	-3	2		3	0	3
A 5	-		10		135		u 5 = 0
	-2	0		0		0
V i	v 1 = 2		v 2 = 0		v 3 = 0

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

Поставщик	Потребитель						Запас
	B 1		B 2		B 3
A 1	120		-		-		120
		1		2		9
A 2	-		-		110		110
		3		4		1
A 3	-		20		-		20
		6		4		8
A 4	-		70		-		70
	-1	2		3		3
A 5	105		10		30		145
		0		0		0
Потребность	225		100		140

Затраты на перевозку по данному плану составят:

S =120*1+110*1+20*4+70*3+105*0+10*0+30*0 = 520 ден.ед.

2.3.1 Метод потенциала на основе опорного плана, построенного методом минимальной стоимости

Произведем оценку плана, построенного методом минимальной стоимости.

Примем v1 = 0.

v1 + u1 = c11 v1 + u1 = 1 u1 = 1 - 0 = 1

v1 + u4 = c41 v1 + u4 = 2 u4 = 2 - 0 = 2

v1 + u5 = c51 v1 + u5 = 0 u5 = 0 - 0 = 0

v2 + u5 = c52 v2 + u5 = 0 v2 = 0 - 0 = 0

v3 + u5 = c53 v3 + u5 = 0 v3 = 0 - 0 = 0

v3 + u2 = c23 v3 + u2 = 1 u2 = 1 - 0 = 1

v2 + u3 = c32 v2 + u3 = 4 u3 = 4 - 0 = 4

Поставщик	Потребитель						U j
	B 1		B 2		B 3
A 1	120		-		-		u 1 = 1
		1		2		9
A 2	-		-		110		u 2 = 1
		3		4		1
A 3	-		20		-		u 3 = 4
		6		4		8
A 4	70		-		-		u 4 = 2
		2		3		3
A 5	35		80		30		u 5 = 0
		0		0		0
V i	v 1 = 0		v 2 = 0		v 3 = 0

12 = c12 - ( u1 + v2 ) = 2 - ( 1 + 0 ) = 1

13 = c13 - ( u1 + v3 ) = 9 - ( 1 + 0 ) = 8

21 = c21 - ( u2 + v1 ) = 3 - ( 1 + 0 ) = 2

22 = c22 - ( u2 + v2 ) = 4 - ( 1 + 0 ) = 3

31 = c31 - ( u3 + v1 ) = 6 - ( 4 + 0 ) = 2

33 = c33 - ( u3 + v3 ) = 8 - ( 4 + 0 ) = 4

42 = c42 - ( u4 + v2 ) = 3 - ( 2 + 0 ) = 1

43 = c43 - ( u4 + v3 ) = 3 - ( 2 + 0 ) = 1

Поставщик	Потребитель						U j
	B 1		B 2		B 3
A 1	120		-		-		u 1 = 1
		1	1	2	8	9
A 2	-		-		110		u 2 = 1
	2	3	3	4		1
A 3	-		20		-		u 3 = 4
	2	6		4	4	8
A 4	70		-		-		u 4 = 2
		2	1	3	1	3
A 5	35		80		30		u 5 = 0
		0		0		0
V i	v 1 = 0		v 2 = 0		v 3 = 0

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

Smin = 1 * 120 + 1 * 110 + 4 * 20 + 2 * 70 + 0 * 35 + 0 * 80 + 0 * 30 = 450

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

2.3.1 Метод потенциала на основе опорного плана, построенного методом Фогеля

Произведем оценку решения методом потенциала.