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

 

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

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

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

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

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

Примем v1 = 0.

v1 + u1 = c11

v1 + u1 = 1

u1 = 1 - 0 = 1

v1 + u4 = c41

v1 + u4 = 2

u4 = 2 - 0 = 2

v3 + u4 = c43

v3 + u4 = 3

v3 = 3 - 2 = 1

v1 + u5 = c51

v1 + u5 = 0

u5 = 0 - 0 = 0

v2 + u5 = c52

v2 + u5 = 0

v2 = 0 - 0 = 0

v3 + u2 = c23

v3 + u2 = 1

u2 = 1 - 1 = 0

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 = 0
		3		4		1
A 3	-		20		-		u 3 = 4
		6		4		8
A 4	40		-		30		u 4 = 2
		2		3		3
A 5	65		115		-		u 5 = 0
		0		0		0
V i	v 1 = 0		v 2 = 0		v 3 = 1

 

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

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

13 = c13 - ( u1 + v3 ) = 9 - ( 1 + 1 ) = 7

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

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

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

33 = c33 - ( u3 + v3 ) = 8 - ( 4 + 1 ) = 3

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

53 = c53 - ( u5 + v3 ) = 0 - ( 0 + 1 ) = -1

 

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

 

Оценка свободной ячейки A5B3 (незадействованного маршрута) отрицательная (53 =-1) , следовательно решение не является оптимальным.

Построим цикл для выбранной ячейки A5B3:

Поставьте курсор мыши в выбранную свободную ячейку A5B3. Используя горизонтальные и вертикальные перемещения курсора, соедините непрерывной линией базисные ячейки так, чтобы вернуться в исходную ячейку A5B3. Базисные ячейки, расположенные в вершинах построенной ломаной линии, образуют цикл для выбранной нами ячейки. Он единственный. Направление обхода не имеет значения.

Ячейки образующие цикл для свободной ячейки A5B3 :

A5B3 , A5B1 , A4B1 , A4B3

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

Среди ячеек цикла A5B1 , A4B3 , номера которых четные, найдем ячейку, обладающую наименьшим значением.

min = ( 65, 30 ) = 30

В данном случае, это ячейка A4B3.

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

Мы вводим новый маршрут доставки продукции от поставщика A5 к потребителю B3. По данному маршруту доставим 30 единиц продукции, по цене доставки 0 за единицу продукции. Общие затраты увеличатся на 0 * 30 ден. ед.

Сократим поставку от поставщика A5 к потребителю B1 на 30 единиц продукции, по цене доставки 0 за единицу продукции. Общие затраты уменьшатся на 0 * 30 ден. ед.

От поставщика A4 к потребителю B1 дополнительно поставим 30 единиц продукции, по цене доставки 2 за единицу продукции. Общие затраты увеличатся на 2 * 30 ден. ед.

По маршруту от поставщика A4 к потребителю B3 мы полностью перестаем доставлять продукцию.

Общие затраты уменьшатся на 3 * 30 ден. ед.

Данные преобразования не изменят баланс между поставщиками и потребителями. Все поставщики израсходуют все свои запасы, а все потребители получат необходимое им количество продукции.

Общие расходы на доставку продукции от поставщиков к потребителям изменятся на

0 * 30 - 0 * 30 + 2 * 30 - 3 * 30 = ( 0 - 0 + 2 - 3 ) * 30 = -1 * 30 ден. ед.

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

Общие затраты на доставку всей продукции, для данного решения, составляют S0 = 480 + ( - 30) = 450 ден. ед..

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

2.1 Условия задачи

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

Исходные данные:

а1 =120

а2 =110

а3 = 20

а4 = 70

b1 = 225

b2 = 100

b3 = 140

 

 

Решим поставленную задачу тремя способами: методом северо-западного угла, методом наименьшей стоимости и методом Фогеля.

2.2 Построение  опорных планов транспортной  модели

2.2.1 Построение опорного плана методом северо-западного угла

Для разрешимости транспортной задачи необходимо, чтобы суммарные запасы продукции у поставщиков равнялись суммарной потребности потребителей. Проверим это условие.

В нашем случае, запасы поставщиков - 320 единиц продукции меньше, чем потребность потребителей - 465 на 145 единиц. Введем в рассмотрение фиктивного поставщика A5, с запасом продукции равным 145. Стоимость доставки единицы продукции от данного поставщика ко всем потребителям примем равной нулю.

Маршруты доставки продукции от фиктивного поставщика A5 к потребителям мы будем рассматривать в последнюю очередь. Не факт, но, скорее всего, это позволит получить более рентабельное начальное решение.

Согласно условию задачи составим таблицу. (тарифы cij располагаются в нижнем правом углу ячейки)

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

 

При анализе методом северо-западного угла анализ начинаем с ячейки А1В1.

Рассмотрим маршрут доставки от поставщика A1 к потребителю B1 (ячейка A1B1).

Запасы поставщика A1 составляют 120 единиц продукции. Потребность потребителя B1 составляет 225 единиц продукции.

От поставщика A1 к потребителю B1 будем доставлять min = (120 , 225) = 120 единиц продукции.

Разместим в ячейку A1B1 значение равное 120

Мы полностью израсходoвали запасы поставщика A1. Вычеркиваем строку 1 таблицы, т.е исключаем ее из дальнейшего рассмотрения.

Рассмотрим маршрут доставки от поставщика A2 к потребителю B1 (ячейка A2B1).

Запасы поставщика A2 составляют 110 единиц продукции. Потребность потребителя B1 составляет 105 единиц продукции.

От поставщика A2 к потребителю B1 будем доставлять min = (110 , 105) = 105 единиц продукции.

Разместим в ячейку A2B1 значение равное 105

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

Затем переходим к удовлетворению потребности поставщика В2 и так далее. В результате получим таблицу.

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