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

Лабораторная работа № 3

Задача:

Имеется три склада, запасы на которых соответственно равны:

1 – 200

2- 250

3- 200

Имеется 5 магазинов, потребности в продукции которых соответственно равны:

1 – 190

2 – 100

3 – 120

4 – 110

5 – 130

Тарифы перевозок со склада в магазин, следующие:

С первого склада в первый магазин – 28

С первого склада во второй магазин – 27

С первого склада в третий магазин – 18

С первого склада в четвёртый магазин – 27

С первого склада в пятый магазин – 24

С второго склада в первый магазин – 18

С второго склада во второй магазин – 26

С второго склада в третий магазин – 27

С второго склада в четвёртый магазин – 32

С второго склада в пятый магазин – 21

С третьего склада в первый магазин – 27

С третьего склада во второй магазин – 33

С третьего склада в третий магазин – 23

С третьего склада в четвёртый магазин – 31

С третьего склада в пятый магазин – 34

Найти оптимальный план перевозок

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

F = ∑∑c_ijx_ij, (1)

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

∑x_ij = a_i, i = 1,2,…, m, (2)

∑x_ij = b_j, j = 1,2,…, n, (3)

С целью составления двойственной задачи переменные x_ij в условии (2) заменим на u₁, u₂, u_i,.., u_m, а переменные x_ij в условия (3) на v₁, v₂, v_j,.., v_n.

Поскольку каждая переменная x_ij входит в условия (2,3) и целевую функцию (1) по одному разу, то двойственную задачу по отношению к прямой транспортной задаче можно сформулировать следующим образом.

Требуется найти не отрицательные числа u_i (при i = 1,2,…,m) и v_j (при j = 1,2,..,n), обращающие в максимум целевую функцию

G = ∑a_iu_i + ∑b_jv_j

при условии

u_i + v_j ≤ c_ij, i = 1,2,..,m; j = 1,2,..,n (4)

В систему условий (4) будет mxn неравенств. По теории двойственности для оптимальных планов прямой и двойственной задачи для всех i,j должно быть:

u_i + v_j ≤ c_ij, если x_ij = 0,

u_i + v_j = c_ij, если x_ij ≥ 0,

Эти условия являются необходимыми и достаточными признаками оптимальности плана транспортной задачи.

Числа u_i, v_j называются потенциалами. Причем число u_i называется потенциалом поставщика, а число v_j – потенциалом потребителя.

По первой теореме двойственности в оптимальном решении значения целевых функций прямой и двойственных задач совпадают: F = G.

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

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

∑a = 200 + 250 + 200 = 650

∑b = 190 + 100 + 120 + 110 + 130 = 650

Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.

Занесем исходные данные в распределительную таблицу.

Этап I. Поиск первого опорного плана.

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

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

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

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

Искомый элемент равен 18

Для этого элемента запасы равны 200, потребности 120. Поскольку минимальным является 120, то вычитаем его.

x₁₃ = min(200,120) = 120.

Искомый элемент равен 18

Для этого элемента запасы равны 250, потребности 190. Поскольку минимальным является 190, то вычитаем его.

x₂₁ = min(250,190) = 190.

Искомый элемент равен 21

Для этого элемента запасы равны 60, потребности 130. Поскольку минимальным является 60, то вычитаем его.

x₂₅ = min(60,130) = 60.

Искомый элемент равен 24

Для этого элемента запасы равны 80, потребности 70. Поскольку минимальным является 70, то вычитаем его.

x₁₅ = min(80,70) = 70.

Искомый элемент равен 27

Для этого элемента запасы равны 10, потребности 100. Поскольку минимальным является 10, то вычитаем его.

x₁₂ = min(10,100) = 10.

Искомый элемент равен 31

Для этого элемента запасы равны 200, потребности 110. Поскольку минимальным является 110, то вычитаем его.

x₃₄ = min(200,110) = 110.

Искомый элемент равен 33

Для этого элемента запасы равны 90, потребности 90. Поскольку минимальным является 90, то вычитаем его.

x₃₂ = min(90,90) = 90.

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

2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 27*10 + 18*120 + 24*70 + 18*190 + 21*60 + 33*90 + 31*110 = 15170

Этап II. Улучшение опорного плана.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

u₁ + v₂ = 27; 0 + v₂ = 27; v₂ = 27

u₃ + v₂ = 33; 27 + u₃ = 33; u₃ = 6

u₃ + v₄ = 31; 6 + v₄ = 31; v₄ = 25

u₁ + v₃ = 18; 0 + v₃ = 18; v₃ = 18

u₁ + v₅ = 24; 0 + v₅ = 24; v₅ = 24

u₂ + v₅ = 21; 24 + u₂ = 21; u₂ = -3

u₂ + v₁ = 18; -3 + v₁ = 18; v₁ = 21

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

(3;3): 6 + 18 > 23; ∆₃₃ = 6 + 18 - 23 = 1

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

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

Цикл приведен в таблице (3,3; 3,2; 1,2; 1,3;).

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

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

u₁ + v₂ = 27; 0 + v₂ = 27; v₂ = 27

u₁ + v₃ = 18; 0 + v₃ = 18; v₃ = 18

u₃ + v₃ = 23; 18 + u₃ = 23; u₃ = 5

u₃ + v₄ = 31; 5 + v₄ = 31; v₄ = 26

u₁ + v₅ = 24; 0 + v₅ = 24; v₅ = 24

u₂ + v₅ = 21; 24 + u₂ = 21; u₂ = -3

u₂ + v₁ = 18; -3 + v₁ = 18; v₁ = 21

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

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

F(x) = 27*100 + 18*30 + 24*70 + 18*190 + 21*60 + 23*90 + 31*110 = 15080

Проверим оптимальность найденного плана по первой теореме двойственности (в оптимальном решении значения целевых функций прямой и двойственных задач совпадают: F = G).

G = 0•200 + -3•250 + 5•200 + 21•190 + 27•100 + 18•120 + 26•110 + 24•130 = 15080