Решение транспортной задачи по оптимизации грузопотока автотранспортного предприятия двумя способами - Оптимизация грузопотока автомобильного предприятия

Исходные данные для решения транспортной задачи оптимизации грузотопотока

Пункты отправления

Пункты назначения и расстояния перевозок

Запасы, aij, т

В1

В2

В3

В4

А1

5

3

2

8

130

А2

9

4

3

7

150

А3

5

6

2

9

190

Потребности, Bj, т

100

150

90

130

470

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

Суммарные запасы продукции у поставщиков должны равняться суммарной потребности потребителей:

Запасы поставщиков: 130+150+190=470 единиц продукции.
Потребность потребителей: 100 + 150 + 90 + 130 = 470 единиц продукции.

Суммарные запасы продукции у поставщиков равны суммарной потребности потребителей.

Для решения задачи необходимо выполнение следующего условия:
Количество задействованных маршрутов = количество поставщиков + количество потребителей - 1. Поэтому если возникнет ситуация, в которой будет необходимо исключить столбец и строку одновременно, мы исключим что-то одно. Начинаем заполнять таблицу от левого верхнего угла и постепенно "двигаемся" к правому нижнему.

От северо-запада к юго-востоку

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

A 1

5

3

2

8

130

A 2

9

4

3

7

150

A 3

5

6

2

9

190

Потребность

100

150

90

130

100 = min { 100, 130 }

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

A 1
    100 5

3

2

8

130 30

A 2

9

4

3

7

150

A 3

5

6

2

9

190

Потребность

100

150

90

130

30 = min { 150, 30 }

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

A 1
    100 5
    30 3

2

8

130 30

A 2

9

4

3

7

150

A 3

5

6

2

9

190

Потребность

100
    150 120

90

130

120 = min { 120, 150 }

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

A 1
    100 5
    30 3

2

8

130 30

A 2

9
    120 4

3

7

150 30

A 3

5

6

2

9

190

Потребность

100
    150 120

90

130

30 = min { 90, 30 }

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

A 1
    100 5
    30 3

2

8

130 30

A 2

9
    120 4
    30 3

7

150 30

A 3

5

6

2

9

190

Потребность

100
    150 120
    90 60

130

60 = min { 190, 60 }

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

A 1
    100 5
    30 3

2

8

130 30

A 2

9
    120 4
    30 3

7

150 30

A 3

5

6
    60 2

9

190 130

Потребность

100
    150 120
    90 60

130

130 = min { 130, 130 }

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

A 1
    100 5
    30 3

2

8

130 30

A 2

9
    120 4
    30 3

7

150 30

A 3

5

6
    60 2
    130 9

190 130

Потребность

100
    150 120
    90 60

130

Рассчитаем стоимость доставки продукции для начального решения.

100*5 + 30*3 + 120*4 + 30*3 + 60*2 + 130*9 = 2450 ден. ед.

Проверим, является ли найденное решение оптимальным.

Каждому поставщику Ai ставим в соответствие некоторое число ui, называемое потенциалом поставщика.

Каждому потребителю Bj ставим в соответствие некоторое число vj, называемое потенциалом потребителя.

Для задействованного маршрута, сумма потенциалов поставщика и потребителя равна тарифу задействованного маршрута.

Значение одного потенциала необходимо задать. Пусть u1= 0.

Последовательно найдем значения потенциалов

A1B1:

V1 + u1 = 5

V1 = 5 - 0 = 5

A1B2:

V2 + u1 = 3

V2 = 3 - 0 = 3

A2B2 :

V2 + u2 = 4

U2 = 4 - 3 = 1

A2B3 :

V3 + u2 = 3

V3 = 3 - 1 = 2

A3B3 :

V3 + u3 = 2

U3 = 2 - 2 = 0

A3B4 :

V4 + u3 = 9

V4 = 9 - 0 = 9

Поставщик

Потребитель

U

B 1

B 2

B 3

B 4

A 1

    100 5
    30 3

2

8

U1 = 0

A 2

9

    120 4
    30 3

7

U2 = 1

A 3

5

6

    60 2
    130 9

U3 = 0

V

V1 = 5

V2 = 3

V3 = 2

V4 = 9

Найдем оценки незадействованных маршрутов.

A1B3 :

Д13 = c13 - ( u1 + v3 ) = 2 - ( 0 + 2) = 0

A1B4 :

Д14 = c14 - ( u1 + v4 ) = 8 - ( 0 + 9 ) = -1

A2B1 :

Д21 = c21 - ( u2 + v1 ) = 9 - ( 5 + 1 ) = 3

A2B4 :

Д24 = c24 - ( u2 + v4 ) = 7 - ( 9 + 1 ) = -3

A3B1 :

Д31 = c31 - ( u3 + v1 ) = 5 - ( 5 + 0 ) = 0

A3B2 :

Д32 = c32 - ( u3 + v2 ) = 6 - ( 3 +0 ) = 3

Доставка автотранспортный маршрут

Наличие отрицательных оценок свидетельствуют о возможности получения нового решения.

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

Ячейки, расположенные в вершинах построенной ломаной линии, образуют цикл для выбранной ячейки. Он единственный. Направление обхода не имеет значения.

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

A 1
    100 5
    30 3

2

8

130

A 2

9
    120 4
    30 3
    -3 7

150

A 3

5

6
    60 2
    130 9

190

Потребность

100

150

90

130

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

A 1
    100 5
    30 3

2

8

130

A 2

9
    120 4
    30 3
    -3 7

150

A 3

5

6
    60 2
    130 9

190

Потребность

100

150

90

130

Данное преобразование не изменит баланса.

А вот общая стоимость доставки продукции изменится на величину:

7 * 30 - 9 * 30 + 2 * 30 - 3 * 30 = ( 7 - 9 + 2 - 3 ) * 30 = -3 * 30 ден. ед. или -3 * 30 = Д42 * 30

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

A 1
    100 5
    30 3

2

8

130

A 2

9
    120 4
    30-30 3

-3

+30

7

150

A 3

5

6
    60+30 2
    130-30 9

190

Потребность

100

150

90

130

Получили новое решение

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

A 1
    100 5
    30 3

2

8

130

A 2

9
    120 4

3
    30 7

150

A 3

5

6
    90 2
    100 9

190

Потребность

100

150

90

130

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

S = 2450 + Д24 * 30 = 2450 -3 * 30 = 2360 ден. ед.

Проверим, является ли найденное решение оптимальным.

Каждому поставщику Ai ставим в соответствие некоторое число ui, называемое потенциалом поставщика.

Каждому потребителю Bj ставим в соответствие некоторое число vj, называемое потенциалом потребителя.

Для задействованного маршрута, сумма потенциалов поставщика и потребителя равна тарифу задействованного маршрута.

Значение одного потенциала необходимо задать. Пусть u1= 0.

Последовательно найдем значения потенциалов

Поставщик

Потребитель

U

B 1

B 2

B 3

B 4

A 1
    40 5
    90 3

2

8

U1 = 0

A 2

9
    60 4

3
    30 7

U2 = 1

A 3

5

6
    90 2
    60 9

U3 = 3

V

V1 = 5

V2 = 3

V3 = -1

V4 = 6

A1B1:

V1 + u1 = 5

V1 = 5 - 0 = 5

A1B2:

V2 + u1 = 3

V2 = 3 - 0 = 3

A2B2 :

V2 + u2 = 4

U2 = 4 - 3 = 1

A2B4 :

V4 + u2 = 7

V4 = 7 - 1 = 6

A3B4 :

V4 + u3 = 9

U3 = 9 - 6 = 3

A3B3 :

V3 + u3 = 2

V3 = 2 - 3 = -1

Найдем оценки незадействованных маршрутов.

A1B3 :

Д13 = c13 - ( u1 + v3 ) = 2 - ( 0 -1) =3

A1B4 :

Д14 = c14 - ( u1 + v4 ) = 8 - ( 0 + 6) = 2

A2B1 :

Д21 = c21 - ( u2 + v1 ) = 9 - ( 5 +1 ) = 3

A2B3 :

Д23 = c23 - ( u2 + v3 ) = 3 - ( 1 - 1 ) = 3

A3B1 :

Д31 = c31 - ( u3 + v1 ) = 5 - ( 5 +3) = -3

A3B2 :

Д32 = c32 - ( u3 + v2)= 6 - (3 +3) = 0

Наличие отрицательных оценок свидетельствуют о возможности получения нового решения.

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

Ячейки, расположенные в вершинах построенной ломаной линии, образуют цикл для выбранной ячейки. Он единственный. Направление обхода не имеет значения.

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

A 1
    100 5
    30 3

2

8

130

A 2

9
    120 4

3
    30 7

150

A 3
    -3 5

6
    90 2
    100 9

190

Потребность

100

150

90

130

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

A 1
    100 5
    30 3

2

8

130

A 2

9
    120 4

3
    30 7

150

A 3
    -3 5

6
    90 2
    100 9

190

Потребность

100

150

90

130

Данное преобразование не изменит баланса. А вот общая стоимость доставки продукции изменится на величину: 5 * 100 - 5 * 100 + 7 * 100 - 9 * 100 + 3 * 100 -4 * 100 = ( 5 - 5 + 7 - 9 + 3 - 4 ) * 100 = -3 * 100 ден. ед. или -3 * 100 = Д31 * 100

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

A 1
    100-100 5
    30+100 3

2

8

130

A 2

9
    120-100 4

3
    30+100 7

150

A 3

-3

+100

5

6
    90 2
    100-100 9

190

Потребность

100

150

90

130

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

A 1
    0 5
    130 3

2

8

130

A 2

9
    20 4

3
    130 7

150

A 3
    100 5

6
    90 2

9

190

Потребность

100

150

90

130

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

S = 2360 + Д31 * 100 = 2360 -3 * 100 = 2060 ден. ед.

Проверим, является ли найденное решение оптимальным.

Каждому поставщику Ai ставим в соответствие некоторое число ui, называемое потенциалом поставщика.

Каждому потребителю Bj ставим в соответствие некоторое число vj, называемое потенциалом потребителя.

Для задействованного маршрута, сумма потенциалов поставщика и потребителя равна тарифу задействованного маршрута.

Значение одного потенциала необходимо задать. Пусть u1= 0.

Последовательно найдем значения потенциалов.

A1B1:

V1 + u1 = 5

V1 = 5 - 0 = 5

A1B2:

V1 + u2 = 3

V2 = 3 - 0 = 3

A2B2 :

V2 + u2 = 4

U2 = 4 - 3 = 1

A2B4 :

V4 + u2 = 7

V4 = 7 - 1 = 6

A3B1 :

V1 + u3 = 5

U3 = 5 - 5 = 0

A3B3 :

V4 + u3 = 2

V3 = 2 - 0 = 2

Поставщик

Потребитель

U

B 1

B 2

B 3

B 4

A 1
    0 5
    130 3

2

8

U1 = 0

A 2

9
    20 4

3
    130 7

U2 = 1

A 3
    100 5

6
    90 2

9

U3 = 0

V

V1 = 5

V2 = 3

V3 = 2

V4 = 6

Найдем оценки незадействованных маршрутов.

A1B3 :

Д13 = c13 - ( u1 + v3 ) = 2 - ( 2 + 0) =0

A1B4 :

Д14 = c14 - ( u1 + v4 ) = 8 - ( 0 + 6 ) = 2

A2B1 :

Д21 = c21 - ( u2 + v1 ) = 9 - ( 5 + 1 ) = 3

A2B3 :

Д23 = c23 - ( u2 + v3 ) = 3 - ( 2 + 1 ) = 0

A3B2 :

Д32 = c32 - ( u3 + v2 ) = 6 - ( 3 + 0) = 3

A3B4 :

Д34 = c34 - ( u3 + v4)= 9 - (6 + 0) = 3

Нет отрицательных оценок, следовательно, уменьшить общую стоимость достаки продукции невозможно.

Ответ:

X опт =

0

130

0

0

0

20

0

130

100

0

90

0

Smin = 2060 ден. ед.

Похожие статьи




Решение транспортной задачи по оптимизации грузопотока автотранспортного предприятия двумя способами - Оптимизация грузопотока автомобильного предприятия

Предыдущая | Следующая