Решение транспортной задачи

Задание

Минимизировать стоимость перевозки при распределении товара внутри города. Данные о наличии товара на складах, спрос потребителей и затратах на перевозку единицы груза от отдельного склада к отдельному потребителю приведены ниже в таблицах.

Таблица 2

Исходные данные

Поставщик

Мощность поставщиков

Потребители и их спрос

1

2

3

4

17

42

21

40

1

60

Х11

5

Х12

1

Х13

4

Х14

2

2

40

Х21

2

Х22

3

Х23

3

Х24

4

3

20

Х31

4

Х32

2

Х33

3

Х34

6

Решение

Математическая модель транспортной задачи:

F = ??cijxij, (1)

при условиях:

  • ?xij = ai, i = 1,2,…, m, (2)
  • ?xij = bj, j = 1,2,…, n, (3)

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов, которая представлена в таблице 3.

Таблица 3

Матрица тарифов

1

2

3

4

Запасы

1

5

1

4

2

60

2

2

3

3

4

40

3

4

2

3

6

20

Потребности

17

42

21

40

Проверим необходимое и достаточное условие разрешимости задачи.

  • ?a = 60 + 40 + 20 = 120
  • ?b = 17 + 42 + 21 + 40 = 120

Используя метод наименьшей стоимости, построим опорный план транспортной задачи.

Таблица 5

Опорный план транспортной задачи

1

2

3

4

Запасы

1

5

1[42]

4

2[18]

60

2

2[17]

3

3[21]

4[2]

40

3

4

2

3

6[20]

20

Потребности

17

42

21

40

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

Таблица 6

Оптимальность опорного плана

v1=0

v2=1

v3=1

v4=2

u1=0

5

1[42]

4

2[18]

u2=2

2[17]

3

3[21]

4[2]

u3=4

4

2

3

6[20]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij.

Выбираем максимальную оценку свободной клетки (3;2): 2

Для этого в перспективную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Таблица 7

1

2

3

4

Запасы

1

5

1[42][-]

4

2[18][+]

60

2

2[17]

3

3[21]

4[2]

40

3

4

2[+]

3

6[20][-]

20

Потребности

17

42

21

40

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3,4) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из хij, стоящих в минусовых клетках. В результате получим новый опорный план.

Таблица 8

Новый опорный план

1

2

3

4

Запасы

1

5

1[22]

4

2[38]

60

2

2[17]

3

3[21]

4[2]

40

3

4

2[20]

3

6

20

Потребности

17

42

21

40

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

Таблица 9

Оптимальность нового опорного плана

v1=0

v2=1

v3=1

v4=2

u1=0

5

1[22]

4

2[38]

u2=2

2[17]

3

3[21]

4[2]

u3=1

4

2[20]

3

6

Опорный план является оптимальным, так как все оценки свободных клеток удовлетворяют условию ui + vi <= cij.

Минимальные затраты составят:

F(x) = 1*22 + 2*38 + 2*17 + 3*21 + 4*2 + 2*20 = 2

 
< Пред   СОДЕРЖАНИЕ   Загрузить   След >