Логотип

Решение задач по математике онлайн

Подробное решение типовых задач по высшей математике
Главная   >>   Пример №1. Транспортная задача. Метод наименьшей стоимости (сбалансированная задача)

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

Задача:
Стоимость доставки единицы продукции от поставщика к потребителю располагается в правом нижнем углу ячейки.
Поставщик Потребитель   Запас  
B 1 B 2 B 3
A 1
5
3
1
  10  
A 2
3
2
4
  20  
A 3
4
1
2
  30  
  Потребность   15 20 25
Требуется составить план перевозок, при котором общая стоимость доставки продукции будет наименьшей.
Решение:
Для решения задачи необходимо выполнение следующего условия:
cуммарные запасы продукции у поставщиков должны равняться суммарной потребности потребителей.

Проверим.
Запасы поставщиков: 10 + 20 + 30 = 60 единиц продукции.
Потребность потребителей: 15 + 20 + 25 = 60 единиц продукции.
Суммарные запасы продукции у поставщиков равны суммарной потребности потребителей.
Для решения задачи необходимо выполнение следующего условия:
количество задействованных маршрутов = количество поставщиков + количество потребителей - 1.

Поэтому если возникнет ситуация, в которой будет необходимо исключить столбец и строку одновременно, мы исключим что-то одно.
В первую очередь, будем задействовать маршруты с наименьшей стоимостью доставки.
Поставщик Потребитель   Запас  
B 1 B 2 B 3
A 1
5
3
1
  10  
A 2
3
2
4
  20  
A 3
4
1
2
  30  
  Потребность   15 20 25
10 = min { 25, 10 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3
A 1
5
3
10
1
  10   нет  
A 2
3
2
4
  20  
A 3
4
1
2
  30  
  Потребность   15 20 25
15
20 = min { 20, 30 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3
A 1
5
3
10
1
  10   нет  
A 2
3
2
4
  20  
A 3
4
20
1
2
  30   10  
  Потребность   15 20
нет
25
15
10 = min { 15, 10 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3
A 1
5
3
10
1
  10   нет  
A 2
3
2
4
  20  
A 3
4
20
1
10
2
  30   10   нет  
  Потребность   15 20
нет
25
15
5
15 = min { 15, 20 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3
A 1
5
3
10
1
  10   нет  
A 2
15
3
2
4
  20   5  
A 3
4
20
1
10
2
  30   10   нет  
  Потребность   15
нет
20
нет
25
15
5
5 = min { 5, 5 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3
A 1
5
3
10
1
  10   нет  
A 2
15
3
2
5
4
  20   5   нет  
A 3
4
20
1
10
2
  30   10   нет  
  Потребность   15
нет
20
нет
25
15
5
нет
Стоимость доставки продукции, для начального решения, не сложно посчитать.

10*1 + 15*3 + 5*4 + 20*1 + 10*2 = 115 ден. ед.

Полученное решение является оптимальным?
Проверим.
Каждому поставщику A i ставим в соответствие некоторое число u i , называемое потенциалом поставщика.
Каждому потребителю B j ставим в соответствие некоторое число v j , называемое потенциалом потребителя.
Для задействованного маршрута, сумма потенциалов поставщика и потребителя равна тарифу задействованного маршрута.
Значение одного потенциала необходимо задать. Пусть u2 = 0.
Последовательно найдем значения потенциалов.
A2B1 :   v1 + u2 = 3         v1 = 3 - 0 = 3
A2B3 :   v3 + u2 = 4         v3 = 4 - 0 = 4
A3B3 :   v3 + u3 = 2         u3 = 2 - 4 = -2
A1B3 :   v3 + u1 = 1         u1 = 1 - 4 = -3
A3B2 :   v2 + u3 = 1         v2 = 1 - (-2) = 3
Найдем оценки незадействованных маршрутов.
A1B1 :   Δ11 = c11 - ( u1 + v1 ) = 5 - ( -3 + 3 ) = 5
A1B2 :   Δ12 = c12 - ( u1 + v2 ) = 3 - ( -3 + 3 ) = 3
A2B2 :   Δ22 = c22 - ( u2 + v2 ) = 2 - ( 0 + 3 ) = -1
A3B1 :   Δ31 = c31 - ( u3 + v1 ) = 4 - ( -2 + 3 ) = 3
Поставщик Потребитель   U  
B 1 B 2 B 3
A 1
5
3
10
1
  u1 = -3  
A 2
15
3
2
5
4
  u2 = 0  
A 3
4
20
1
10
2
  u3 = -2  
  V     v1 = 3     v2 = 3     v3 = 4  
Есть отрицательные оценки, следовательно, возможно получить новое решение, как минимум, не хуже имеющегося.
ШАГ №1.
Выберем ячейку A2B2, ее оценка отрицательная. Поставьте курсор мыши в выбранную ячейку A2B2.
Используя горизонтальные и вертикальные перемещения курсора, соедините непрерывной линией заполненные ячейки так, чтобы вернуться в исходную ячейку.
Ячейки, расположенные в вершинах построенной ломаной линии, образуют цикл для выбранной ячейки.
Он единственный. Направление обхода не имеет значения.
Поставщик Потребитель   Запас  
B 1 B 2 B 3
A 1
5
3
10
1
  10  
A 2
15
3
-1
2
5
4
  20  
A 3
4
20
1
10
2
  30  
  Потребность     15     20     25  
5 = min { 5, 20 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3
A 1
5
3
10
1
  10  
A 2
15
3
-1
2
5
4
  20  
A 3
4
20
1
10
2
  30  
  Потребность     15     20     25  
Данное преобразование не изменит баланса.
А вот общая стоимость доставки продукции изменится на величину:
2 * 5 - 4 * 5 + 2 * 5 - 1 * 5 = ( 2 - 4 + 2 - 1 ) * 5 = -1 * 5 ден. ед.
Вы правильно заметили, что -1 * 5 = Δ22 * 5
Поставщик Потребитель   Запас  
B 1 B 2 B 3
A 1
5
3
10
1
  10  
A 2
15
3
+5
-1
2
5 - 5
4
  20  
A 3
4
20 - 5
1
10 + 5
2
  30  
  Потребность     15     20     25  
Получили новое решение.
Поставщик Потребитель   Запас  
B 1 B 2 B 3
A 1
5
3
10
1
  10  
A 2
15
3
5
2
4
  20  
A 3
4
15
1
15
2
  30  
  Потребность     15     20     25  
Общую сумму доставки продукции, для данного решения, легко посчитать.

S = 115 + Δ22 * 5 = 115 -1 * 5 = 110 ден. ед.

Полученное решение является оптимальным?
Проверим.
Каждому поставщику A i ставим в соответствие некоторое число u i , называемое потенциалом поставщика.
Каждому потребителю B j ставим в соответствие некоторое число v j , называемое потенциалом потребителя.
Для задействованного маршрута, сумма потенциалов поставщика и потребителя равна тарифу задействованного маршрута.
Значение одного потенциала необходимо задать. Пусть u2 = 0.
Последовательно найдем значения потенциалов.
A2B1 :   v1 + u2 = 3         v1 = 3 - 0 = 3
A2B2 :   v2 + u2 = 2         v2 = 2 - 0 = 2
A3B2 :   v2 + u3 = 1         u3 = 1 - 2 = -1
A3B3 :   v3 + u3 = 2         v3 = 2 - (-1) = 3
A1B3 :   v3 + u1 = 1         u1 = 1 - 3 = -2
Найдем оценки незадействованных маршрутов.
A1B1 :   Δ11 = c11 - ( u1 + v1 ) = 5 - ( -2 + 3 ) = 4
A1B2 :   Δ12 = c12 - ( u1 + v2 ) = 3 - ( -2 + 2 ) = 3
A2B3 :   Δ23 = c23 - ( u2 + v3 ) = 4 - ( 0 + 3 ) = 1
A3B1 :   Δ31 = c31 - ( u3 + v1 ) = 4 - ( -1 + 3 ) = 2
Поставщик Потребитель   U  
B 1 B 2 B 3
A 1
5
3
10
1
  u1 = -2  
A 2
15
3
5
2
4
  u2 = 0  
A 3
4
15
1
15
2
  u3 = -1  
  V     v1 = 3     v2 = 2     v3 = 3  
Нет отрицательных оценок, следовательно, уменьшить общую стоимость достаки продукции невозможно.

Ответ:

X опт =

Знак системы
0
0
10
Знак системы
15
5
0
0
15
15

Smin = 110 ден. ед.










© 2010-2018, по всем вопросам пишите по адресу matematika1974@yandex.ru



Ссылки