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

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


min = { 40, 30 } = 30


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


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


Поставщик

Потребитель

Запас

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

-

 

1  

-

 

15  

130

 

1  

-

 

6  

40

 

7  

-

-2

0  

170

A 3

-

 

15  

-

 

6  

-

 

4  

-

 

10  

110

 

5  

30

 

0  

140

A 4

50

 

2  

130

 

6  

-

 

13  

-

 

3  

-

 

11  

-

 

0  

180

Потребность

50

160

130

10

210

30

  

 

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


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


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


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


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


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


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


Поставщик

Потребитель

Запас

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

-

 

1  

-

 

15  

130

 

1  

-

 

6  

40 - 30

 

7  

+ 30

-2

0  

170

A 3

-

 

15  

-

 

6  

-

 

4  

-

 

10  

110 + 30

 

5  

30 - 30

 

0  

140

A 4

50

 

2  

130

 

6  

-

 

13  

-

 

3  

-

 

11  

-

 

0  

180

Потребность

50

160

130

10

210

30

  

 

Что в итоге?


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


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


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


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


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


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


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


           ячейки A2B1, общая стоимость доставки всей продукции изменилась бы на 21 * 30 = -2 * 30 = -60 ден. ед.


           ячейки A4B6, общая стоимость доставки всей продукции изменилась бы на 46 * 30 = -1 * 30 = -30 ден. ед.


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


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


Поставщик

Потребитель

Запас

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

-

 

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

  

Шаг 2

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


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


Примем v5 = 0.


v5 + u1 = c15

v5 + u1 = 5

u1 = 5 - 0 = 5


v5 + u2 = c25

v5 + u2 = 7

u2 = 7 - 0 = 7


v6 + u2 = c26

v6 + u2 = 0

v6 = 0 - 7 = -7


v5 + u3 = c35

v5 + u3 = 5

u3 = 5 - 0 = 5


v2 + u1 = c12

v2 + u1 = 5

v2 = 5 - 5 = 0


v4 + u1 = c14

v4 + u1 = 1

v4 = 1 - 5 = -4


v3 + u2 = c23

v3 + u2 = 1

v3 = 1 - 7 = -6


v2 + u4 = c42

v2 + u4 = 6

u4 = 6 - 0 = 6


v1 + u4 = c41

v1 + u4 = 2

v1 = 2 - 6 = -4

Поставщик

Потребитель

U j

B 1

B 2

B 3

B 4

B 5

B 6

A 1

-

 

13  

30

 

5  

-

 

13  

10

 

1  

60

 

5  

-

 

0  

u 1 = 5

A 2

-

 

1  

-

 

15  

130

 

1  

-

 

6  

10

 

7  

30

 

0  

u 2 = 7

A 3

-

 

15  

-

 

6  

-

 

4  

-

 

10  

140

 

5  

-

 

0  

u 3 = 5

A 4

50

 

2  

130

 

6  

-

 

13  

-

 

3  

-

 

11  

-

 

0  

u 4 = 6

V i

v 1 = -4

v 2 = 0

v 3 = -6

v 4 = -4

v 5 = 0

v 6 = -7

  

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


11 = c11 - ( u1 + v1 ) = 13 - ( 5 + ( -4 ) ) = 12


13 = c13 - ( u1 + v3 ) = 13 - ( 5 + ( -6 ) ) = 14


16 = c16 - ( u1 + v6 ) = 0 - ( 5 + ( -7 ) ) = 2


21 = c21 - ( u2 + v1 ) = 1 - ( 7 + ( -4 ) ) = -2


22 = c22 - ( u2 + v2 ) = 15 - ( 7 + 0 ) = 8


24 = c24 - ( u2 + v4 ) = 6 - ( 7 + ( -4 ) ) = 3


31 = c31 - ( u3 + v1 ) = 15 - ( 5 + ( -4 ) ) = 14


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


33 = c33 - ( u3 + v3 ) = 4 - ( 5 + ( -6 ) ) = 5


34 = c34 - ( u3 + v4 ) = 10 - ( 5 + ( -4 ) ) = 9


36 = c36 - ( u3 + v6 ) = 0 - ( 5 + ( -7 ) ) = 2


43 = c43 - ( u4 + v3 ) = 13 - ( 6 + ( -6 ) ) = 13


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


45 = c45 - ( u4 + v5 ) = 11 - ( 6 + 0 ) = 5


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

Поставщик

Потребитель

U j

B 1

B 2

B 3

B 4

B 5

B 6

A 1

-

12

13  

30

 

5  

-

14

13  

10

 

1  

60

 

5  

-

2

0  

u 1 = 5

A 2

-

-2

1  

-

8

15  

130

 

1  

-

3

6  

10

 

7  

30

 

0  

u 2 = 7

A 3

-

14

15  

-

1

6  

-

5

4  

-

9

10  

140

 

5  

-

2

0  

u 3 = 5

A 4

50

 

2  

130

 

6  

-

13

13  

-

1

3  

-

5

11  

-

1

0  

u 4 = 6

V i

v 1 = -4

v 2 = 0

v 3 = -6

v 4 = -4

v 5 = 0

v 6 = -7

  


 

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


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


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


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


A2B1 , A2B5 , A1B5 , A1B2 , A4B2 , A4B1


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


Поставщик

Потребитель

Запас

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

  

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