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

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

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


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


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


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


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


Разместим в  ячейку A1B5 значение равное 60


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


Поставщик

Потребитель

Запас

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  

-

 

0  

170

A 3

-

 

15  

-

 

6  

-

 

4  

-

 

10  

-

 

5  

-

 

0  

140

A 4

50

 

2  

130

 

6  

-

 

13  

-

 

3  

-

 

11  

-

 

0  

180

Потребность

50

160

130

10

210

30

  

 

9)

    

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


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


Разместим в  ячейку A3B5 значение равное 110


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


Поставщик

Потребитель

Запас

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  

-

 

0  

170

A 3

-

 

15  

-

 

6  

-

 

4  

-

 

10  

110

 

5  

-

 

0  

140

A 4

50

 

2  

130

 

6  

-

 

13  

-

 

3  

-

 

11  

-

 

0  

180

Потребность

50

160

130

10

210

30

  

 

10)

    

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


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


Разместим в  ячейку A3B6 значение равное 30


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


Поставщик

Потребитель

Запас

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  

-

 

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

  

 

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


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


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


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


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


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


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


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


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


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


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


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


 

Шаг 1

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


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


v5 + u3 = c35

v5 + u3 = 5

u3 = 5 - 0 = 5


v6 + u3 = c36

v6 + u3 = 0

v6 = 0 - 5 = -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  

40

 

7  

-

 

0  

u 2 = 7

A 3

-

 

15  

-

 

6  

-

 

4  

-

 

10  

110

 

5  

30

 

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

  

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


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


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


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


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


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


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


26 = c26 - ( u2 + v6 ) = 0 - ( 7 + ( -5 ) ) = -2


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


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 + ( -5 ) ) = -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  

-

0

0  

u 1 = 5

A 2

-

-2

1  

-

8

15  

130

 

1  

-

3

6  

40

 

7  

-

-2

0  

u 2 = 7

A 3

-

14

15  

-

1

6  

-

5

4  

-

9

10  

110

 

5  

30

 

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

  


 

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


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


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


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


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


A2B6 , A2B5 , A3B5 , A3B6


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


Поставщик

Потребитель

Запас

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

  

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