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

Лабораторная работа, 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₆, номера которых четные, найдем ячейку, обладающую найменьшим значением.

min = { 40, 30 } = 30

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

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

Поставщик

Потребитель

Запас

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

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

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

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

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

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

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

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

B ₆

A ₁

-
	13

20
	5

-
	13

10
	1

70
	5

-
	0

100

A ₂

10 + 30
	1

-
	15

130
	1

-
	6

-
	7

30 - 30
	0

170

A ₃

-
	15

-
	6

-
	4

-
	10

140
	5

-
	0

140

A ₄

40 - 30
	2

140
	6

-
	13

-
	3

-
	11

+ 30
-1	0

180

Потребность

160

130

210

Что в итоге?

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

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

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

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

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

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

Ячейка 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 ₂

40
	1

-
	15

130
	1

-
	6

-
	7

-
	0

170

A ₃

-
	15

-
	6

-
	4

-
	10

140
	5

-
	0

140

A ₄

10
	2

140
	6

-
	13

-
	3

-
	11

30
	0

180

Потребность

160

130

210

Шаг 4

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

Каждому поставщику 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₄= 2

v₁= 2 - 0 = 2

v₂+ u₄= c₄₂

v₂+ u₄= 6

v₂= 6 - 0 = 6

v₆+ u₄= c₄₆

v₆+ u₄= 0

v₆= 0 - 0 = 0

v₂+ u₁= c₁₂

v₂+ u₁= 5

u₁= 5 - 6 = -1

v₄+ u₁= c₁₄

v₄+ u₁= 1

v₄= 1 - ( -1 ) = 2

v₅+ u₁= c₁₅

v₅+ u₁= 5

v₅= 5 - ( -1 ) = 6

v₁+ u₂= c₂₁

v₁+ u₂= 1

u₂= 1 - 2 = -1

v₃+ u₂= c₂₃

v₃+ u₂= 1

v₃= 1 - ( -1 ) = 2

v₅+ u₃= c₃₅

v₅+ u₃= 5

u₃= 5 - 6 = -1

Поставщик

Потребитель

U _j

B ₁

B ₂

B ₃

B ₄

B ₅

B ₆

A ₁

-
	13

20
	5

-
	13

10
	1

70
	5

-
	0

u ₁= -1

A ₂

40
	1

-
	15

130
	1

-
	6

-
	7

-
	0

u ₂= -1

A ₃

-
	15

-
	6

-
	4

-
	10

140
	5

-
	0

u ₃= -1

A ₄

10
	2

140
	6

-
	13

-
	3

-
	11

30
	0

u ₄= 0

V _i

v ₁= 2

v ₂= 6

v ₃= 2

v ₄= 2

v ₅= 6

v ₆= 0

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

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

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

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

₂₂= c₂₂- ( u₂+ v₂) = 15 - ( -1 + 6 ) = 10

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

₂₅= c₂₅- ( u₂+ v₅) = 7 - ( -1 + 6 ) = 2

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

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

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

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

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

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

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

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

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

Поставщик

Потребитель

U _j

B ₁

B ₂

B ₃

B ₄

B ₅

B ₆

A ₁

-
12	13

20
	5

-
12	13

10
	1

70
	5

-
1	0

u ₁= -1

A ₂

40
	1

-
10	15

130
	1

-
5	6

-
2	7

-
1	0

u ₂= -1

A ₃

-
14	15

-
1	6

-
3	4

-
9	10

140
	5

-
1	0

u ₃= -1

A ₄

10
	2

140
	6

-
11	13

-
1	3

-
5	11

30
	0

u ₄= 0

V _i

v ₁= 2

v ₂= 6

v ₃= 2

v ₄= 2

v ₅= 6

v ₆= 0

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

Ответ:

X _опт=	0	20	0	10	70	0
	40	0	130	0	0	0
	0	0	0	0	140	0
	10	140	0	0	0	30

S_min= 5 * 20 + 1 * 10 + 5 * 70 + 1 * 40 + 1 * 130 + 5 * 140 + 2 * 10 + 6 * 140 + 0 * 30 = 2190

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

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

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

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

задача.doc

Шаг 4

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

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

Транспортные задачи