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

Автор работы: Пользователь скрыл имя, 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 Мб (Скачать документ)

 

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


min = { 40, 30 } = 30


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


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


Поставщик

Потребитель

Запас

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

  

 

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


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


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


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


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


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


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


Поставщик

Потребитель

Запас

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 + 30

 

1  

-

 

15  

130

 

1  

-

 

6  

-

 

7  

30 - 30

 

0  

170

A 3

-

 

15  

-

 

6  

-

 

4  

-

 

10  

140

 

5  

-

 

0  

140

A 4

40 - 30

 

2  

140

 

6  

-

 

13  

-

 

3  

-

 

11  

+ 30

-1

0  

180

Потребность

50

160

130

10

210

30

  

 

Что в итоге?


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


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


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


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


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


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


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


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


Поставщик

Потребитель

Запас

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

40

 

1  

-

 

15  

130

 

1  

-

 

6  

-

 

7  

-

 

0  

170

A 3

-

 

15  

-

 

6  

-

 

4  

-

 

10  

140

 

5  

-

 

0  

140

A 4

10

 

2  

140

 

6  

-

 

13  

-

 

3  

-

 

11  

30

 

0  

180

Потребность

50

160

130

10

210

30

  

Шаг 4

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


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


Примем u4 = 0.


v1 + u4 = c41

v1 + u4 = 2

v1 = 2 - 0 = 2


v2 + u4 = c42

v2 + u4 = 6

v2 = 6 - 0 = 6


v6 + u4 = c46

v6 + u4 = 0

v6 = 0 - 0 = 0


v2 + u1 = c12

v2 + u1 = 5

u1 = 5 - 6 = -1


v4 + u1 = c14

v4 + u1 = 1

v4 = 1 - ( -1 ) = 2


v5 + u1 = c15

v5 + u1 = 5

v5 = 5 - ( -1 ) = 6


v1 + u2 = c21

v1 + u2 = 1

u2 = 1 - 2 = -1


v3 + u2 = c23

v3 + u2 = 1

v3 = 1 - ( -1 ) = 2


v5 + u3 = c35

v5 + u3 = 5

u3 = 5 - 6 = -1

Поставщик

Потребитель

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 = -1

A 2

40

 

1  

-

 

15  

130

 

1  

-

 

6  

-

 

7  

-

 

0  

u 2 = -1

A 3

-

 

15  

-

 

6  

-

 

4  

-

 

10  

140

 

5  

-

 

0  

u 3 = -1

A 4

10

 

2  

140

 

6  

-

 

13  

-

 

3  

-

 

11  

30

 

0  

u 4 = 0

V i

v 1 = 2

v 2 = 6

v 3 = 2

v 4 = 2

v 5 = 6

v 6 = 0

  

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


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


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


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


22 = c22 - ( u2 + v2 ) = 15 - ( -1 + 6 ) = 10


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


25 = c25 - ( u2 + v5 ) = 7 - ( -1 + 6 ) = 2


26 = c26 - ( u2 + v6 ) = 0 - ( -1 + 0 ) = 1


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


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


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


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


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


43 = c43 - ( u4 + v3 ) = 13 - ( 0 + 2 ) = 11


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


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

Поставщик

Потребитель

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  

-

1

0  

u 1 = -1

A 2

40

 

1  

-

10

15  

130

 

1  

-

5

6  

-

2

7  

-

1

0  

u 2 = -1

A 3

-

14

15  

-

1

6  

-

3

4  

-

9

10  

140

 

5  

-

1

0  

u 3 = -1

A 4

10

 

2  

140

 

6  

-

11

13  

-

1

3  

-

5

11  

30

 

0  

u 4 = 0

V i

v 1 = 2

v 2 = 6

v 3 = 2

v 4 = 2

v 5 = 6

v 6 = 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


 

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


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



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