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

Лабораторная работа, 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 Мб (Скачать документ)

Из полученных разностей выберем наибольшую.

Наибольшей разностью обладает столбец 5. В данном столбце выберем ячейку A₁B₅, как обладающую наименьшим тарифом.

Почему?
Стоимость доставки единицы продукции от поставщика A₁к потребителю B₅, как минимум, на 0 ден.ед. меньше чем от остальных поставщиков к потребителю B₅(см. правую таблицу).

Запасы поставщика A₁составляют 60 единиц продукции. Потребность потребителя B₅составляет 170 единиц продукции. (см. таблицу пункта 7)

От поставщика A₁к потребителю B₅будем доставлять min = { 60 , 170 } = 60 единиц продукции.

Разместим в ячейку A₁B₅значение равное 60

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

B ₆

A ₁

-
	13

30
	5

-
	13

10
	1

60
	5

-
	0

100

A ₂

-
	1

-
	15

130
	1

-
	6

40
	7

-
	0

170

A ₃

-
	15

-
	6

-
	4

-
	10

-
	5

-
	0

140

A ₄

50
	2

130
	6

-
	13

-
	3

-
	11

-
	0

180

Потребность

160

130

210

Запасы поставщика A₃составляют 140 единиц продукции. Потребность потребителя B₅составляет 110 единиц продукции. (см. таблицу пункта 8)

От поставщика A₃к потребителю B₅будем доставлять min = { 140 , 110 } = 110 единиц продукции.

Разместим в ячейку A₃B₅значение равное 110

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

B ₆

A ₁

-
	13

30
	5

-
	13

10
	1

60
	5

-
	0

100

A ₂

-
	1

-
	15

130
	1

-
	6

40
	7

-
	0

170

A ₃

-
	15

-
	6

-
	4

-
	10

110
	5

-
	0

140

A ₄

50
	2

130
	6

-
	13

-
	3

-
	11

-
	0

180

Потребность

160

130

210

10)

Запасы поставщика A₃составляют 30 единиц продукции. Потребность потребителя B₆составляет 30 единиц продукции. (см. таблицу пункта 9)

От поставщика A₃к потребителю B₆будем доставлять 30 единиц продукции.

Разместим в ячейку A₃B₆значение равное 30

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

B ₆

A ₁

-
	13

30
	5

-
	13

10
	1

60
	5

-
	0

100

A ₂

-
	1

-
	15

130
	1

-
	6

40
	7

-
	0

170

A ₃

-
	15

-
	6

-
	4

-
	10

110
	5

30
	0

140

A ₄

50
	2

130
	6

-
	13

-
	3

-
	11

-
	0

180

Потребность

160

130

210

Заполненные нами ячейки будем называть базисными, остальные - свободными.

Для решения задачи методом потенциалов, количество базисных ячеек (задействованных маршрутов) должно равняться m + n - 1, где m - количество строк в таблице, n - количество столбцов в таблице.

Количество базисных ячеек (задействованных маршрутов) равно 9, что и требовалось.

Мы нашли начальное решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.

S₀= 5 * 30 + 1 * 10 + 5 * 60 + 1 * 130 + 7 * 40 + 5 * 110 + 0 * 30 + 2 * 50 + 6 * 130 = 2300 ден. ед.

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

Дальнейшие наши действия будут состоять из шагов, каждый из которых состоит в следующем:

· Находим потенциалы поставщиков и потребителей для имеющегося решения.

· Находим оценки свободных ячеек. Если все оценки окажутся неотрицательными - задача решена.

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

· Находим новое решение, как минимум, не хуже предыдущего.

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

Шаг 1

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

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

Примем v₅= 0.

v₅+ u₁= c₁₅

v₅+ u₁= 5

u₁= 5 - 0 = 5

v₅+ u₂= c₂₅

v₅+ u₂= 7

u₂= 7 - 0 = 7

v₅+ u₃= c₃₅

v₅+ u₃= 5

u₃= 5 - 0 = 5

v₆+ u₃= c₃₆

v₆+ u₃= 0

v₆= 0 - 5 = -5

v₂+ u₁= c₁₂

v₂+ u₁= 5

v₂= 5 - 5 = 0

v₄+ u₁= c₁₄

v₄+ u₁= 1

v₄= 1 - 5 = -4

v₃+ u₂= c₂₃

v₃+ u₂= 1

v₃= 1 - 7 = -6

v₂+ u₄= c₄₂

v₂+ u₄= 6

u₄= 6 - 0 = 6

v₁+ u₄= c₄₁

v₁+ u₄= 2

v₁= 2 - 6 = -4

Поставщик

Потребитель

U _j

B ₁

B ₂

B ₃

B ₄

B ₅

B ₆

A ₁

-
	13

30
	5

-
	13

10
	1

60
	5

-
	0

u ₁= 5

A ₂

-
	1

-
	15

130
	1

-
	6

40
	7

-
	0

u ₂= 7

A ₃

-
	15

-
	6

-
	4

-
	10

110
	5

30
	0

u ₃= 5

A ₄

50
	2

130
	6

-
	13

-
	3

-
	11

-
	0

u ₄= 6

V _i

v ₁= -4

v ₂= 0

v ₃= -6

v ₄= -4

v ₅= 0

v ₆= -5

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

₁₁= c₁₁- ( u₁+ v₁) = 13 - ( 5 + ( -4 ) ) = 12

₁₃= c₁₃- ( u₁+ v₃) = 13 - ( 5 + ( -6 ) ) = 14

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

₂₁= c₂₁- ( u₂+ v₁) = 1 - ( 7 + ( -4 ) ) = -2

₂₂= c₂₂- ( u₂+ v₂) = 15 - ( 7 + 0 ) = 8

₂₄= c₂₄- ( u₂+ v₄) = 6 - ( 7 + ( -4 ) ) = 3

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

₃₁= c₃₁- ( u₃+ v₁) = 15 - ( 5 + ( -4 ) ) = 14

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

₃₃= c₃₃- ( u₃+ v₃) = 4 - ( 5 + ( -6 ) ) = 5

₃₄= c₃₄- ( u₃+ v₄) = 10 - ( 5 + ( -4 ) ) = 9

₄₃= c₄₃- ( u₄+ v₃) = 13 - ( 6 + ( -6 ) ) = 13

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

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

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

Поставщик

Потребитель

U _j

B ₁

B ₂

B ₃

B ₄

B ₅

B ₆

A ₁

-
12	13

30
	5

-
14	13

10
	1

60
	5

-
0	0

u ₁= 5

A ₂

-
-2	1

-
8	15

130
	1

-
3	6

40
	7

-
-2	0

u ₂= 7

A ₃

-
14	15

-
1	6

-
5	4

-
9	10

110
	5

30
	0

u ₃= 5

A ₄

50
	2

130
	6

-
13	13

-
1	3

-
5	11

-
-1	0

u ₄= 6

V _i

v ₁= -4

v ₂= 0

v ₃= -6

v ₄= -4

v ₅= 0

v ₆= -5

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

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

Построим цикл для выбранной ячейки 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

30
	5

-
	13

10
	1

60
	5

-
	0

100

A ₂

-
	1

-
	15

130
	1

-
	6

40
	7

-
-2	0

170

A ₃

-
	15

-
	6

-
	4

-
	10

110
	5

30
	0

140

A ₄

50
	2

130
	6

-
	13

-
	3

-
	11

-
	0

180

Потребность

160

130

210

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

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

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

задача.doc

Шаг 1

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

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