Логотип

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

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

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

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

Задача:
Стоимость доставки единицы продукции от поставщика к потребителю располагается в правом нижнем углу ячейки.
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
7
8
1
2
  200  
A 2
4
5
9
8
  180  
A 3
9
2
3
6
  240  
  Потребность   150 130 150 140
Требуется составить план перевозок, при котором общая стоимость доставки продукции будет наименьшей.
Решение:
Для решения задачи необходимо выполнение следующего условия:
cуммарные запасы продукции у поставщиков должны равняться суммарной потребности потребителей.

Проверим.
Запасы поставщиков: 200 + 180 + 240 = 620 единиц продукции.
Потребность потребителей: 150 + 130 + 150 + 140 = 570 единиц продукции.
Разница в 50 единиц продукции.
Введем в рассмотрение фиктивного потребителя B5, с потребностью 50 единиц продукции.
Стоимость доставки единицы продукции от всех поставщиков к потребителю B5 примем равной нулю (см. таблицу ниже).
Теперь суммарные запасы продукции у поставщиков равны суммарной потребности потребителей.
Для решения задачи необходимо выполнение следующего условия:
количество задействованных маршрутов = количество поставщиков + количество потребителей - 1.

Поэтому если возникнет ситуация, в которой будет необходимо исключить столбец и строку одновременно, мы исключим что-то одно.
В первую очередь, будем задействовать маршруты с наименьшей стоимостью доставки.
Маршруты доставки продукции от поставщиков к фиктивному потребителю B5 будем рассматривать в последнюю очередь.
Это позволит получить меньшую стоимость доставки продукции для начального решения.
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4 B 5
A 1
7
8
1
2
0
  200  
A 2
4
5
9
8
0
  180  
A 3
9
2
3
6
0
  240  
  Потребность   150 130 150 140 50
150 = min { 150, 200 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4 B 5
A 1
7
8
150
1
2
0
  200   50  
A 2
4
5
9
8
0
  180  
A 3
9
2
3
6
0
  240  
  Потребность   150 130 150
нет
140 50
50 = min { 140, 50 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4 B 5
A 1
7
8
150
1
50
2
0
  200   50   нет  
A 2
4
5
9
8
0
  180  
A 3
9
2
3
6
0
  240  
  Потребность   150 130 150
нет
140
90
50
130 = min { 130, 240 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4 B 5
A 1
7
8
150
1
50
2
0
  200   50   нет  
A 2
4
5
9
8
0
  180  
A 3
9
130
2
3
6
0
  240   110  
  Потребность   150 130
нет
150
нет
140
90
50
150 = min { 150, 180 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4 B 5
A 1
7
8
150
1
50
2
0
  200   50   нет  
A 2
150
4
5
9
8
0
  180   30  
A 3
9
130
2
3
6
0
  240   110  
  Потребность   150
нет
130
нет
150
нет
140
90
50
90 = min { 90, 110 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4 B 5
A 1
7
8
150
1
50
2
0
  200   50   нет  
A 2
150
4
5
9
8
0
  180   30  
A 3
9
130
2
3
90
6
0
  240   110   20  
  Потребность   150
нет
130
нет
150
нет
140
90
нет
50
30 = min { 50, 30 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4 B 5
A 1
7
8
150
1
50
2
0
  200   50   нет  
A 2
150
4
5
9
8
30
0
  180   30   нет  
A 3
9
130
2
3
90
6
0
  240   110   20  
  Потребность   150
нет
130
нет
150
нет
140
90
нет
50
20
20 = min { 20, 20 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4 B 5
A 1
7
8
150
1
50
2
0
  200   50   нет  
A 2
150
4
5
9
8
30
0
  180   30   нет  
A 3
9
130
2
3
90
6
20
0
  240   110   20   нет  
  Потребность   150
нет
130
нет
150
нет
140
90
нет
50
20
нет
Стоимость доставки продукции, для начального решения, не сложно посчитать.

150*1 + 50*2 + 150*4 + 30*0 + 130*2 + 90*6 + 20*0 = 1650 ден. ед.

Полученное решение является оптимальным?
Проверим.
Каждому поставщику A i ставим в соответствие некоторое число u i , называемое потенциалом поставщика.
Каждому потребителю B j ставим в соответствие некоторое число v j , называемое потенциалом потребителя.
Для задействованного маршрута, сумма потенциалов поставщика и потребителя равна тарифу задействованного маршрута.
Значение одного потенциала необходимо задать. Пусть u3 = 0.
Последовательно найдем значения потенциалов.
A3B2 :   v2 + u3 = 2         v2 = 2 - 0 = 2
A3B4 :   v4 + u3 = 6         v4 = 6 - 0 = 6
A3B5 :   v5 + u3 = 0         v5 = 0 - 0 = 0
A1B4 :   v4 + u1 = 2         u1 = 2 - 6 = -4
A2B5 :   v5 + u2 = 0         u2 = 0 - 0 = 0
A1B3 :   v3 + u1 = 1         v3 = 1 - (-4) = 5
A2B1 :   v1 + u2 = 4         v1 = 4 - 0 = 4
Найдем оценки незадействованных маршрутов.
A1B1 :   Δ11 = c11 - ( u1 + v1 ) = 7 - ( -4 + 4 ) = 7
A1B2 :   Δ12 = c12 - ( u1 + v2 ) = 8 - ( -4 + 2 ) = 10
A1B5 :   Δ15 = c15 - ( u1 + v5 ) = 0 - ( -4 + 0 ) = 4
A2B2 :   Δ22 = c22 - ( u2 + v2 ) = 5 - ( 0 + 2 ) = 3
A2B3 :   Δ23 = c23 - ( u2 + v3 ) = 9 - ( 0 + 5 ) = 4
A2B4 :   Δ24 = c24 - ( u2 + v4 ) = 8 - ( 0 + 6 ) = 2
A3B1 :   Δ31 = c31 - ( u3 + v1 ) = 9 - ( 0 + 4 ) = 5
A3B3 :   Δ33 = c33 - ( u3 + v3 ) = 3 - ( 0 + 5 ) = -2
Поставщик Потребитель   U  
B 1 B 2 B 3 B 4 B 5
A 1
7
8
150
1
50
2
0
  u1 = -4  
A 2
150
4
5
9
8
30
0
  u2 = 0  
A 3
9
130
2
3
90
6
20
0
  u3 = 0  
  V     v1 = 4     v2 = 2     v3 = 5     v4 = 6     v5 = 0  
Есть отрицательные оценки, следовательно, возможно получить новое решение, как минимум, не хуже имеющегося.
ШАГ №1.
Выберем ячейку A3B3, ее оценка отрицательная. Поставьте курсор мыши в выбранную ячейку A3B3.
Используя горизонтальные и вертикальные перемещения курсора, соедините непрерывной линией заполненные ячейки так, чтобы вернуться в исходную ячейку.
Ячейки, расположенные в вершинах построенной ломаной линии, образуют цикл для выбранной ячейки.
Он единственный. Направление обхода не имеет значения.
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4 B 5
A 1
7
8
150
1
50
2
0
  200  
A 2
150
4
5
9
8
30
0
  180  
A 3
9
130
2
-2
3
90
6
20
0
  240  
  Потребность     150     130     150     140     50  
90 = min { 90, 150 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4 B 5
A 1
7
8
150
1
50
2
0
  200  
A 2
150
4
5
9
8
30
0
  180  
A 3
9
130
2
-2
3
90
6
20
0
  240  
  Потребность     150     130     150     140     50  
Данное преобразование не изменит баланса.
А вот общая стоимость доставки продукции изменится на величину:
3 * 90 - 6 * 90 + 2 * 90 - 1 * 90 = ( 3 - 6 + 2 - 1 ) * 90 = -2 * 90 ден. ед.
Вы правильно заметили, что -2 * 90 = Δ33 * 90
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4 B 5
A 1
7
8
150 - 90
1
50 + 90
2
0
  200  
A 2
150
4
5
9
8
30
0
  180  
A 3
9
130
2
+90
-2
3
90 - 90
6
20
0
  240  
  Потребность     150     130     150     140     50  
Получили новое решение.
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4 B 5
A 1
7
8
60
1
140
2
0
  200  
A 2
150
4
5
9
8
30
0
  180  
A 3
9
130
2
90
3
6
20
0
  240  
  Потребность     150     130     150     140     50  
Общую сумму доставки продукции, для данного решения, легко посчитать.

S = 1650 + Δ33 * 90 = 1650 -2 * 90 = 1470 ден. ед.

Полученное решение является оптимальным?
Проверим.
Каждому поставщику A i ставим в соответствие некоторое число u i , называемое потенциалом поставщика.
Каждому потребителю B j ставим в соответствие некоторое число v j , называемое потенциалом потребителя.
Для задействованного маршрута, сумма потенциалов поставщика и потребителя равна тарифу задействованного маршрута.
Значение одного потенциала необходимо задать. Пусть u3 = 0.
Последовательно найдем значения потенциалов.
A3B2 :   v2 + u3 = 2         v2 = 2 - 0 = 2
A3B3 :   v3 + u3 = 3         v3 = 3 - 0 = 3
A3B5 :   v5 + u3 = 0         v5 = 0 - 0 = 0
A1B3 :   v3 + u1 = 1         u1 = 1 - 3 = -2
A1B4 :   v4 + u1 = 2         v4 = 2 - (-2) = 4
A2B5 :   v5 + u2 = 0         u2 = 0 - 0 = 0
A2B1 :   v1 + u2 = 4         v1 = 4 - 0 = 4
Найдем оценки незадействованных маршрутов.
A1B1 :   Δ11 = c11 - ( u1 + v1 ) = 7 - ( -2 + 4 ) = 5
A1B2 :   Δ12 = c12 - ( u1 + v2 ) = 8 - ( -2 + 2 ) = 8
A1B5 :   Δ15 = c15 - ( u1 + v5 ) = 0 - ( -2 + 0 ) = 2
A2B2 :   Δ22 = c22 - ( u2 + v2 ) = 5 - ( 0 + 2 ) = 3
A2B3 :   Δ23 = c23 - ( u2 + v3 ) = 9 - ( 0 + 3 ) = 6
A2B4 :   Δ24 = c24 - ( u2 + v4 ) = 8 - ( 0 + 4 ) = 4
A3B1 :   Δ31 = c31 - ( u3 + v1 ) = 9 - ( 0 + 4 ) = 5
A3B4 :   Δ34 = c34 - ( u3 + v4 ) = 6 - ( 0 + 4 ) = 2
Поставщик Потребитель   U  
B 1 B 2 B 3 B 4 B 5
A 1
7
8
60
1
140
2
0
  u1 = -2  
A 2
150
4
5
9
8
30
0
  u2 = 0  
A 3
9
130
2
90
3
6
20
0
  u3 = 0  
  V     v1 = 4     v2 = 2     v3 = 3     v4 = 4     v5 = 0  
Нет отрицательных оценок, следовательно, уменьшить общую стоимость достаки продукции невозможно.

Ответ:

X опт =

Знак системы
0
0
60
140
0
Знак системы
150
0
0
0
30
0
130
90
0
20

Smin = 1470 ден. ед.











© 2010–2016
По всем вопросам пишите по адресу matematika1974@yandex.ru


Ссылки