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

Лабораторная работа, 12 Ноября 2012, автор: пользователь скрыл имя

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

У поставщиков A1 , A2 , A3 , A4 , находится соответственно 100 , 170 , 140 , 180 единиц однотипной продукции, которая должна быть доставлена потребителям B1 , B2 , B3 , B4 , B5 в количестве 50 , 160 , 130 , 10 , 210 единиц соответственно.

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

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

задача.doc

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

Среди ячеек цикла A₂B₅, A₁B₂, A₄B₁, номера которых четные, найдем ячейку, обладающую найменьшим значением.

min = { 10, 30, 50 } = 10

В данном случае, это ячейка A₂B₅.

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

B ₆

A ₁

-
	13

30
	5

-
	13

10
	1

60
	5

-
	0

100

A ₂

-
-2	1

-
	15

130
	1

-
	6

10
	7

30
	0

170

A ₃

-
	15

-
	6

-
	4

-
	10

140
	5

-
	0

140

A ₄

50
	2

130
	6

-
	13

-
	3

-
	11

-
	0

180

Потребность

160

130

210

От ячеек цикла с четными номерами отнимает 10. К ячейкам с нечетными номерами прибавляем 10.

Что мы делаем?

Мы вводим новый маршрут доставки продукции от поставщика A₂к потребителю B₁. По данному маршруту доставим 10 единиц продукции, по цене доставки 1 за единицу продукции. Общие затраты увеличатся на 1 * 10 ден. ед.

По маршруту от поставщика A₂к потребителю B₅мы полностью перестаем доставлять продукцию.
Общие затраты уменьшатся на 7 * 10 ден. ед.

От поставщика A₁к потребителю B₅дополнительно поставим 10 единиц продукции, по цене доставки 5 за единицу продукции. Общие затраты увеличатся на 5 * 10 ден. ед.

Сократим поставку от поставщика A₁к потребителю B₂на 10 единиц продукции, по цене доставки 5 за единицу продукции. Общие затраты уменьшатся на 5 * 10 ден. ед.

От поставщика A₄к потребителю B₂дополнительно поставим 10 единиц продукции, по цене доставки 6 за единицу продукции. Общие затраты увеличатся на 6 * 10 ден. ед.

Сократим поставку от поставщика A₄к потребителю B₁на 10 единиц продукции, по цене доставки 2 за единицу продукции. Общие затраты уменьшатся на 2 * 10 ден. ед.

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

B ₆

A ₁

-
	13

30 - 10
	5

-
	13

10
	1

60 + 10
	5

-
	0

100

A ₂

+ 10
-2	1

-
	15

130
	1

-
	6

10 - 10
	7

30
	0

170

A ₃

-
	15

-
	6

-
	4

-
	10

140
	5

-
	0

140

A ₄

50 - 10
	2

130 + 10
	6

-
	13

-
	3

-
	11

-
	0

180

Потребность

160

130

210

Что в итоге?

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

1 * 10 - 7 * 10 + 5 * 10 - 5 * 10 + 6 * 10 - 2 * 10 = ( 1 - 7 + 5 - 5 + 6 - 2 ) * 10 = -2 * 10 ден. ед.

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

ГЛАВНОЕ :
В тот момент, когда мы нашли ячейку с наименьшим значением (среди ячеек, номера которых четные в цикле), мы уже могли сказать, что общие затраты изменятся на ₂₁* 10 = -2 * 10 = -20 ден. ед.

Общие затраты на доставку всей продукции, для данного решения, составляют S₀= 2240 + ( - 20 ) = 2220 ден. ед. .

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

Ячейка A₂B₅выйдет из базиса, мы перестали доставлять продукцию от поставщика A₂к потребителю B₅

Ячейка A₂B₁станет базисной, мы ввели новый маршрут доставки продукции от поставщика A₂к потребителю B₁.

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

B ₆

A ₁

-
	13

20
	5

-
	13

10
	1

70
	5

-
	0

100

A ₂

10
	1

-
	15

130
	1

-
	6

-
	7

30
	0

170

A ₃

-
	15

-
	6

-
	4

-
	10

140
	5

-
	0

140

A ₄

40
	2

140
	6

-
	13

-
	3

-
	11

-
	0

180

Потребность

160

130

210

Шаг 3

ПРОИЗВЕДЕМ ОЦЕНКУ ПОЛУЧЕННОГО РЕШЕНИЯ.

Каждому поставщику A_iставим в соответствие некоторое число - u_i, называемое потенциалом поставщика.
Каждому потребителю B_jставим в соответствие некоторое число - v_j, называемое потенциалом потребителя.
Для базисной ячеки (задействованного маршрута), сумма потенциалов поставщика и потребителя должна быть равна тарифу данного маршрута.
(u_i+ v_j= c_ij, где c_ij- тариф клетки A_iB_j)
Поскольку, число базисных клеток - 9, а общее количество потенциалов равно 10, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.

Примем u₂= 0.

v₁+ u₂= c₂₁

v₁+ u₂= 1

v₁= 1 - 0 = 1

v₃+ u₂= c₂₃

v₃+ u₂= 1

v₃= 1 - 0 = 1

v₆+ u₂= c₂₆

v₆+ u₂= 0

v₆= 0 - 0 = 0

v₁+ u₄= c₄₁

v₁+ u₄= 2

u₄= 2 - 1 = 1

v₂+ u₄= c₄₂

v₂+ u₄= 6

v₂= 6 - 1 = 5

v₂+ u₁= c₁₂

v₂+ u₁= 5

u₁= 5 - 5 = 0

v₄+ u₁= c₁₄

v₄+ u₁= 1

v₄= 1 - 0 = 1

v₅+ u₁= c₁₅

v₅+ u₁= 5

v₅= 5 - 0 = 5

v₅+ u₃= c₃₅

v₅+ u₃= 5

u₃= 5 - 5 = 0

Поставщик

Потребитель

U _j

B ₁

B ₂

B ₃

B ₄

B ₅

B ₆

A ₁

-
	13

20
	5

-
	13

10
	1

70
	5

-
	0

u ₁= 0

A ₂

10
	1

-
	15

130
	1

-
	6

-
	7

30
	0

u ₂= 0

A ₃

-
	15

-
	6

-
	4

-
	10

140
	5

-
	0

u ₃= 0

A ₄

40
	2

140
	6

-
	13

-
	3

-
	11

-
	0

u ₄= 1

V _i

v ₁= 1

v ₂= 5

v ₃= 1

v ₄= 1

v ₅= 5

v ₆= 0

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

₁₁= c₁₁- ( u₁+ v₁) = 13 - ( 0 + 1 ) = 12

₁₃= c₁₃- ( u₁+ v₃) = 13 - ( 0 + 1 ) = 12

₁₆= c₁₆- ( u₁+ v₆) = 0 - ( 0 + 0 ) = 0

₂₂= c₂₂- ( u₂+ v₂) = 15 - ( 0 + 5 ) = 10

₂₄= c₂₄- ( u₂+ v₄) = 6 - ( 0 + 1 ) = 5

₂₅= c₂₅- ( u₂+ v₅) = 7 - ( 0 + 5 ) = 2

₃₁= c₃₁- ( u₃+ v₁) = 15 - ( 0 + 1 ) = 14

₃₂= c₃₂- ( u₃+ v₂) = 6 - ( 0 + 5 ) = 1

₃₃= c₃₃- ( u₃+ v₃) = 4 - ( 0 + 1 ) = 3

₃₄= c₃₄- ( u₃+ v₄) = 10 - ( 0 + 1 ) = 9

₃₆= c₃₆- ( u₃+ v₆) = 0 - ( 0 + 0 ) = 0

₄₃= c₄₃- ( u₄+ v₃) = 13 - ( 1 + 1 ) = 11

₄₄= c₄₄- ( u₄+ v₄) = 3 - ( 1 + 1 ) = 1

₄₅= c₄₅- ( u₄+ v₅) = 11 - ( 1 + 5 ) = 5

₄₆= c₄₆- ( u₄+ v₆) = 0 - ( 1 + 0 ) = -1

Поставщик

Потребитель

U _j

B ₁

B ₂

B ₃

B ₄

B ₅

B ₆

A ₁

-
12	13

20
	5

-
12	13

10
	1

70
	5

-
0	0

u ₁= 0

A ₂

10
	1

-
10	15

130
	1

-
5	6

-
2	7

30
	0

u ₂= 0

A ₃

-
14	15

-
1	6

-
3	4

-
9	10

140
	5

-
0	0

u ₃= 0

A ₄

40
	2

140
	6

-
11	13

-
1	3

-
5	11

-
-1	0

u ₄= 1

V _i

v ₁= 1

v ₂= 5

v ₃= 1

v ₄= 1

v ₅= 5

v ₆= 0

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

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

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

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

A₄B₆, A₄B₁, A₂B₁, A₂B₆

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

B ₆

A ₁

-
	13

20
	5

-
	13

10
	1

70
	5

-
	0

100

A ₂

10
	1

-
	15

130
	1

-
	6

-
	7

30
	0

170

A ₃

-
	15

-
	6

-
	4

-
	10

140
	5

-
	0

140

A ₄

40
	2

140
	6

-
	13

-
	3

-
	11

-
-1	0

180

Потребность

160

130

210

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

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

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

задача.doc

Шаг 3

Информация о работе Транспортная задача

Связанные документы