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

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

Задача: В пунктах А и В находятся соответственно 150 и 90 т горючего. Пунктам 1, 2, 3 требуются соответственно 60, 70, 110 т горючего. Стоимость перевозки 1 т горючего из пункта А в пункты 1, 2, 3 равна 60, 10, 40 тыс. руб. за 1 т соответственно, а их пункта В в пункты 1, 2, 3 – 120, 20, 80 тыс. руб. за 1 т соответственно. Составить план перевозок горючего, минимизирующий общую сумму транспортных расходов.

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

Экономико-математическая модель задачи:

Пусть – Xij- объем перевозки от i- го поставщика j-ому потребителю.

Потребители Вj В1 В2 В3 Запасы пост.
Поставщики Ai
А1   X11   X12   X13  
     
А2   X21   X22   X23  
     
Спрос потр.

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

Решение транспортной задачи - student2.ru

Х11 + Х12 + Х13 = 150

Х21 + Х22 + Х23 = 90

(1) Х11 + Х21 = 60

Х12 + Х22 = 70

Х13 + Х23 = 110

Составим целевую функцию:

(2) Z = 60X11 + 10X12 + 40X13 + 120 X21 + 20X22 + 80X23 → min

Таким образом, на множестве неотрицательных решений, системы ограничений (1) найдем такое решение

Решение транспортной задачи - student2.ru Решение транспортной задачи - student2.ru Х11 Х12 Х13

Х = Х21 Х22 Х23 ,

при котором целевая функция (2) принимает наименьшее значение.

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

Ui Потребители Вj В1 В2 В3 Запасы пост.
Поставщики Ai
U1= А1              
     
U2= А2              
     
  Спрос потр.
  Vj V1= V2= V3=  

Найдем первый опорный план поставок. Для этого воспользуемся методом наименьших затрат. Найдем в таблице клетку с наименьшим тарифом. Это клетка (1, 2). ЕЕ тариф С12 = 10. Дадим в эту клетку максимально возможную поставку. Х12 = min (150, 70) = 70. Клетку (2, 1) вычеркиваем (в эту клетку поставок давать не будем), т.к. потребность второго пункта полностью удовлетворена. Находим следующую клетку с наименьшим тарифом. Это клетка (1, 3), ее тариф С13 = 40. Дадим в эту клетку максимально возможную поставку. Х13 = min (150 – 70, 110) = 80. Клетку (1, 1) вычеркиваем (в эту клетку поставок давать не будем), т.к. запас первого поставщика (пункт А) полностью использован. Находим следующую клетку с наименьшим тарифом. Это клетка (2, 3), ее тариф С23 = 80. Дадим в эту клетку максимально возможную поставку. Х23 = min (110 – 80, 90) = 30. И в последнюю свободную клетку (2, 1) даем поставку 60.

Проверяем баланс по строкам и столбцам (соответствующие суммы).

Т.О. получен первый опорный план поставок. Полученный план невырожденный, т.к. число занятых клеток равно рангу системы. Ранг системы вычисляется по формуле: r = m + n – 1, где m – число поставщиков, n – число потребителей.

r = 2 + 3 – 1 =4, число занятых клеток р = 4.

Решение транспортной задачи - student2.ru

Х1 = 0 70 80

60 0 30

Z1 = 70*10 + 80*40 + 60*120 + 30*80 = 13500 руб.

Проверим, будет ли полученный план оптимальным. Для этого воспользуемся методом потенциалов. Обозначим потенциалы поставщиков Ui , а потенциалы потребителей Vj . Для нахождения этих потенциалов составим систему уравнений по формуле Ui + Vj = Сi j , где Сi j – тариф занятой клетки.

 
  Решение транспортной задачи - student2.ru

U1 + V2 = 10 Эта система имеет бесконечное множество решений.

U1 + V3 = 40 Найдем одно их них. Положим U1 = 0. Тогда V2 = 10,

U2 + V1 = 120 V3 = 40, U2 = 40, V1 = 80.

U2 + V3 = 80

Ui Потребители Вj В1 В2 В3 Запасы пост.
Поставщики Ai
U1=0 А1   —      
     
U2=40 А2     —    
     
  Спрос потр.
  Vj V1=80 V2=10 V3=40  

Далее, оценим свободные клетки по формуле: Di j = Сi j – (Ui + Vj), где Сi j – тариф свободной клетки.

D11 = 60 – (0 + 80) = - 20 ≤ 0, D22 = 20 – (40 + 10) = - 30 ≤ 0

Среди оценок свободных клеток есть отрицательные. Это значит, что полученный план не является оптимальным. Поэтому надо перераспределить поставки в одну из этих свободных клеток (с отрицательной оценкой). Перераспределим поставки в клетку (1, 1) (отрицательная оценка по модулю меньше). Для этого введем несколько определений.

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

Циклом пересчета называется такой цикл в таблице с базисным распределением поставок, при котором одна из его вершин лежит в свободной клетке, остальные – в заполненных.

Цикл пересчета называется означенным, если в его вершинах расставлены знаки «+» и «−», так, что в свободной клетке стоит знак «+», а соседние вершины имеют противоположные знаки «−».

НАПРИМЕР

Решение транспортной задачи - student2.ru Решение транспортной задачи - student2.ru 70 + Решение транспортной задачи - student2.ru 120 ‒
Решение транспортной задачи - student2.ru — + * 20 ‒
Решение транспортной задачи - student2.ru 60 ‒ 50 +
Решение транспортной задачи - student2.ru
Решение транспортной задачи - student2.ru — * Решение транспортной задачи - student2.ru 120
Решение транспортной задачи - student2.ru
Решение транспортной задачи - student2.ru 60

Построим для клетки (1, 1) означенный цикл пересчета:

+ −

Решение транспортной задачи - student2.ru Решение транспортной задачи - student2.ru Решение транспортной задачи - student2.ru * 80

Величина пересчета λ = min (60, 80) = 60.

Решение транспортной задачи - student2.ru − 60 30 +

Эту величину добавляют в клетки положительного полуцикла и вычитают в клетках отрицательного полуцикла. После пересчета по циклу строим новую транспортную таблицу, при этом значения потенциалов берем новые.

Ui   В1 В2 В3 Запасы пост.
U1= А1        
     
U2= А2   —   —    
     
  Спрос потр.
  Vj V1= V2= V3=  

Полученный план невырожденный, т.к. число занятых клеток равно рангу системы.

Решение транспортной задачи - student2.ru

Х1 = 60 70 20

0 0 90

Z1 = 60*60 + 70*10 + 20*40 + 90*80 = 12300 руб.

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

Решение транспортной задачи - student2.ru Для нахождения новых потенциалов составим систему уравнений по формуле Ui + Vj = Сi j , где Сi j – тариф занятой клетки.

U1 + V1 = 60 Эта система имеет бесконечное множество решений.

U1 + V2 = 10 Найдем одно их них. Положим U1 = 0. Тогда V1 = 60,

U1 + V3 = 40 V2 = 10, V3 = 40, U2 = 40,.

U2 + V3 = 80

Ui   В1 В2 В3 Запасы пост.
U1=0 А1        
     
U2=40 А2   —   —    
     
  Спрос потр.
  Vj V1=60 V2=10 V3=40  

Далее, оценим свободные клетки по формуле: Di j = Сi j – (Ui + Vj), где Сi j – тариф свободной клетки.

D21 = 120 – (40 + 60) = 20 ≥ 0, D22 = 20 – (40 + 10) = - 30 ≤ 0

Среди оценок свободных клеток есть отрицательная. Это значит, что полученный план не является оптимальным. Поэтому надо перераспределить поставки в одну из этих свободных клеток (с отрицательной оценкой). Перераспределим поставки в клетку (2, 2) (отрицательная оценка).

Построим для клетки (2, 2) означенный цикл пересчета:

− +

Решение транспортной задачи - student2.ru Решение транспортной задачи - student2.ru Решение транспортной задачи - student2.ru 70 20

Величина пересчета λ = min (70, 90) = 70.

Решение транспортной задачи - student2.ru + * 90 −

Эту величину добавляют в клетки положительного полуцикла и вычитаются в клетках отрицательного цикла. После пересчета по циклу строим новую транспортную таблицу, при этом значения потенциалов берем новые.

Ui   В1 В2 В3 Запасы пост.
U1=0 А1     —    
     
U2=40 А2   —      
     
  Спрос потр.
  Vj V1=60 V2= - 20 V3=40  

Полученный план невырожденный, т.к. число занятых клеток равно рангу системы.

Решение транспортной задачи - student2.ru

Х1 = 60 0 90

0 70 20

Z1 = 60*60 + 90*40 + 70*20 + 20*80 = 10200 руб.

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

Решение транспортной задачи - student2.ru Для нахождения новых потенциалов составим систему уравнений по формуле Ui + Vj = Сi j , где Сi j – тариф занятой клетки.

U1 + V1 = 60 Эта система имеет бесконечное множество решений.

U1 + V3 = 40 Найдем одно их них. Положим U1 = 0. Тогда V1 = 60,

U2 + V2 = 20 V2 = - 20, V3 = 40, U2 = 40,.

U2 + V3 = 80

Далее, оценим свободные клетки по формуле: Di j = Сi j – (Ui + Vj), где Сi j – тариф свободной клетки.

D21 = 120 – (40 + 60) = 20 ≥ 0, D12 = 10 – (0 + (- 20)) = 30 ≥ 0.

Среди оценок свободных клеток нет отрицательных. Все оценки положительны. Это значит, что полученный план оптимален.

Решение транспортной задачи - student2.ru

Хопт = 60 0 90

0 70 20

Zопт = 60*60 + 90*40 + 70*20 + 20*80 = 10200 руб.

Экономический анализ. Общая сумма транспортных расходов будет минимальной и составит 10200 руб., если перевозку горючего запланировать следующим образом: из пункта А доставить в пункт 1- 60 тонн горючего, в пункт 3 – 90 тонн; из пункта В отправить в пункт 2- 70 тонн, в 3 пункт – 20 тонн горючего. При этом запасы в пунктах А и В полностью реализованы и потребности пунктов 1, 2 и 3 будут удовлетворены.

Наши рекомендации