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

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

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

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

Скачать полностью (192.18 Кб) Сколько стоит заказать работу?
Прикрепленные файлы: 1 файл

задача.doc

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

 

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


min = { 10, 30, 50 } = 10


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


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


Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

B 5

B 6

A 1

-

 

13  

30

 

5  

-

 

13  

10

 

1  

60

 

5  

-

 

0  

100

A 2

-

-2

1  

-

 

15  

130

 

1  

-

 

6  

10

 

7  

30

 

0  

170

A 3

-

 

15  

-

 

6  

-

 

4  

-

 

10  

140

 

5  

-

 

0  

140

A 4

50

 

2  

130

 

6  

-

 

13  

-

 

3  

-

 

11  

-

 

0  

180

Потребность

50

160

130

10

210

30

  

 

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


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


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


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


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


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


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


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


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


Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

B 5

B 6

A 1

-

 

13  

30 - 10

 

5  

-

 

13  

10

 

1  

60 + 10

 

5  

-

 

0  

100

A 2

+ 10

-2

1  

-

 

15  

130

 

1  

-

 

6  

10 - 10

 

7  

30

 

0  

170

A 3

-

 

15  

-

 

6  

-

 

4  

-

 

10  

140

 

5  

-

 

0  

140

A 4

50 - 10

 

2  

130 + 10

 

6  

-

 

13  

-

 

3  

-

 

11  

-

 

0  

180

Потребность

50

160

130

10

210

30

  

 

Что в итоге?


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


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


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


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


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


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


Ячейка A2B5 выйдет из базиса, мы перестали доставлять продукцию от поставщика A2 к потребителю B5


Ячейка A2B1 станет базисной, мы ввели новый маршрут доставки продукции от поставщика A2 к потребителю B1 .


Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

B 5

B 6

A 1

-

 

13  

20

 

5  

-

 

13  

10

 

1  

70

 

5  

-

 

0  

100

A 2

10

 

1  

-

 

15  

130

 

1  

-

 

6  

-

 

7  

30

 

0  

170

A 3

-

 

15  

-

 

6  

-

 

4  

-

 

10  

140

 

5  

-

 

0  

140

A 4

40

 

2  

140

 

6  

-

 

13  

-

 

3  

-

 

11  

-

 

0  

180

Потребность

50

160

130

10

210

30

  

Шаг 3

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


Каждому поставщику Ai ставим в соответствие некоторое число - ui, называемое потенциалом поставщика. 
Каждому потребителю Bj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя. 
Для базисной ячеки (задействованного маршрута), сумма потенциалов поставщика и потребителя должна быть равна тарифу данного маршрута.  
(ui + vj = cij, где cij - тариф клетки AiBj)  
Поскольку, число базисных клеток - 9, а общее количество потенциалов равно 10, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.


Примем u2 = 0.


v1 + u2 = c21

v1 + u2 = 1

v1 = 1 - 0 = 1


v3 + u2 = c23

v3 + u2 = 1

v3 = 1 - 0 = 1


v6 + u2 = c26

v6 + u2 = 0

v6 = 0 - 0 = 0


v1 + u4 = c41

v1 + u4 = 2

u4 = 2 - 1 = 1


v2 + u4 = c42

v2 + u4 = 6

v2 = 6 - 1 = 5


v2 + u1 = c12

v2 + u1 = 5

u1 = 5 - 5 = 0


v4 + u1 = c14

v4 + u1 = 1

v4 = 1 - 0 = 1


v5 + u1 = c15

v5 + u1 = 5

v5 = 5 - 0 = 5


v5 + u3 = c35

v5 + u3 = 5

u3 = 5 - 5 = 0

Поставщик

Потребитель

U j

B 1

B 2

B 3

B 4

B 5

B 6

A 1

-

 

13  

20

 

5  

-

 

13  

10

 

1  

70

 

5  

-

 

0  

u 1 = 0

A 2

10

 

1  

-

 

15  

130

 

1  

-

 

6  

-

 

7  

30

 

0  

u 2 = 0

A 3

-

 

15  

-

 

6  

-

 

4  

-

 

10  

140

 

5  

-

 

0  

u 3 = 0

A 4

40

 

2  

140

 

6  

-

 

13  

-

 

3  

-

 

11  

-

 

0  

u 4 = 1

V i

v 1 = 1

v 2 = 5

v 3 = 1

v 4 = 1

v 5 = 5

v 6 = 0

  

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


11 = c11 - ( u1 + v1 ) = 13 - ( 0 + 1 ) = 12


13 = c13 - ( u1 + v3 ) = 13 - ( 0 + 1 ) = 12


16 = c16 - ( u1 + v6 ) = 0 - ( 0 + 0 ) = 0


22 = c22 - ( u2 + v2 ) = 15 - ( 0 + 5 ) = 10


24 = c24 - ( u2 + v4 ) = 6 - ( 0 + 1 ) = 5


25 = c25 - ( u2 + v5 ) = 7 - ( 0 + 5 ) = 2


31 = c31 - ( u3 + v1 ) = 15 - ( 0 + 1 ) = 14


32 = c32 - ( u3 + v2 ) = 6 - ( 0 + 5 ) = 1


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


34 = c34 - ( u3 + v4 ) = 10 - ( 0 + 1 ) = 9


36 = c36 - ( u3 + v6 ) = 0 - ( 0 + 0 ) = 0


43 = c43 - ( u4 + v3 ) = 13 - ( 1 + 1 ) = 11


44 = c44 - ( u4 + v4 ) = 3 - ( 1 + 1 ) = 1


45 = c45 - ( u4 + v5 ) = 11 - ( 1 + 5 ) = 5


46 = c46 - ( u4 + v6 ) = 0 - ( 1 + 0 ) = -1

Поставщик

Потребитель

U j

B 1

B 2

B 3

B 4

B 5

B 6

A 1

-

12

13  

20

 

5  

-

12

13  

10

 

1  

70

 

5  

-

0

0  

u 1 = 0

A 2

10

 

1  

-

10

15  

130

 

1  

-

5

6  

-

2

7  

30

 

0  

u 2 = 0

A 3

-

14

15  

-

1

6  

-

3

4  

-

9

10  

140

 

5  

-

0

0  

u 3 = 0

A 4

40

 

2  

140

 

6  

-

11

13  

-

1

3  

-

5

11  

-

-1

0  

u 4 = 1

V i

v 1 = 1

v 2 = 5

v 3 = 1

v 4 = 1

v 5 = 5

v 6 = 0

  


 

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


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


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


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


A4B6 , A4B1 , A2B1 , A2B6


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


Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

B 5

B 6

A 1

-

 

13  

20

 

5  

-

 

13  

10

 

1  

70

 

5  

-

 

0  

100

A 2

10

 

1  

-

 

15  

130

 

1  

-

 

6  

-

 

7  

30

 

0  

170

A 3

-

 

15  

-

 

6  

-

 

4  

-

 

10  

140

 

5  

-

 

0  

140

A 4

40

 

2  

140

 

6  

-

 

13  

-

 

3  

-

 

11  

-

-1

0  

180

Потребность

50

160

130

10

210

30

  

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