Логотип

Линейное программирование онлайн

Добротный сервис для решения задач по линейному программированию
Главная   >>   Пример №5. Транспортная задача. Метод северо-западного угла (фиктивный поставщик)

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

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

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

Поэтому если возникнет ситуация, в которой будет необходимо исключить столбец и строку одновременно, мы исключим что-то одно.
Начинаем заполнять таблицу от левого верхнего угла и постепенно "двигаемся" к правому нижнему.
От северо-запада к юго-востоку.
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
4
5
3
6
  300  
A 2
7
2
1
5
  250  
A 3
6
1
4
2
  200  
A 4
0
0
0
0
  50  
  Потребность   220 150 250 180
220 = min { 220, 300 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
220
4
5
3
6
  300   80  
A 2
7
2
1
5
  250  
A 3
6
1
4
2
  200  
A 4
0
0
0
0
  50  
  Потребность   220
нет
150 250 180
80 = min { 150, 80 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
220
4
80
5
3
6
  300   80   нет  
A 2
7
2
1
5
  250  
A 3
6
1
4
2
  200  
A 4
0
0
0
0
  50  
  Потребность   220
нет
150
70
250 180
70 = min { 70, 250 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
220
4
80
5
3
6
  300   80   нет  
A 2
7
70
2
1
5
  250   180  
A 3
6
1
4
2
  200  
A 4
0
0
0
0
  50  
  Потребность   220
нет
150
70
нет
250 180
180 = min { 250, 180 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
220
4
80
5
3
6
  300   80   нет  
A 2
7
70
2
180
1
5
  250   180   нет  
A 3
6
1
4
2
  200  
A 4
0
0
0
0
  50  
  Потребность   220
нет
150
70
нет
250
70
180
70 = min { 70, 200 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
220
4
80
5
3
6
  300   80   нет  
A 2
7
70
2
180
1
5
  250   180   нет  
A 3
6
1
70
4
2
  200   130  
A 4
0
0
0
0
  50  
  Потребность   220
нет
150
70
нет
250
70
нет
180
130 = min { 180, 130 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
220
4
80
5
3
6
  300   80   нет  
A 2
7
70
2
180
1
5
  250   180   нет  
A 3
6
1
70
4
130
2
  200   130   нет  
A 4
0
0
0
0
  50  
  Потребность   220
нет
150
70
нет
250
70
нет
180
50
50 = min { 50, 50 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
220
4
80
5
3
6
  300   80   нет  
A 2
7
70
2
180
1
5
  250   180   нет  
A 3
6
1
70
4
130
2
  200   130   нет  
A 4
0
0
0
50
0
  50   нет  
  Потребность   220
нет
150
70
нет
250
70
нет
180
50
нет
Стоимость доставки продукции, для начального решения, не сложно посчитать.

220*4 + 80*5 + 70*2 + 180*1 + 70*4 + 130*2 + 50*0 = 2140 ден. ед.

Полученное решение является оптимальным?
Проверим.
Каждому поставщику A i ставим в соответствие некоторое число u i , называемое потенциалом поставщика.
Каждому потребителю B j ставим в соответствие некоторое число v j , называемое потенциалом потребителя.
Для задействованного маршрута, сумма потенциалов поставщика и потребителя равна тарифу задействованного маршрута.
Значение одного потенциала необходимо задать. Пусть u1 = 0.
Последовательно найдем значения потенциалов.
A1B1 :   v1 + u1 = 4         v1 = 4 - 0 = 4
A1B2 :   v2 + u1 = 5         v2 = 5 - 0 = 5
A2B2 :   v2 + u2 = 2         u2 = 2 - 5 = -3
A2B3 :   v3 + u2 = 1         v3 = 1 - (-3) = 4
A3B3 :   v3 + u3 = 4         u3 = 4 - 4 = 0
A3B4 :   v4 + u3 = 2         v4 = 2 - 0 = 2
A4B4 :   v4 + u4 = 0         u4 = 0 - 2 = -2
Найдем оценки незадействованных маршрутов.
A1B3 :   Δ13 = c13 - ( u1 + v3 ) = 3 - ( 0 + 4 ) = -1
A1B4 :   Δ14 = c14 - ( u1 + v4 ) = 6 - ( 0 + 2 ) = 4
A2B1 :   Δ21 = c21 - ( u2 + v1 ) = 7 - ( -3 + 4 ) = 6
A2B4 :   Δ24 = c24 - ( u2 + v4 ) = 5 - ( -3 + 2 ) = 6
A3B1 :   Δ31 = c31 - ( u3 + v1 ) = 6 - ( 0 + 4 ) = 2
A3B2 :   Δ32 = c32 - ( u3 + v2 ) = 1 - ( 0 + 5 ) = -4
A4B1 :   Δ41 = c41 - ( u4 + v1 ) = 0 - ( -2 + 4 ) = -2
A4B2 :   Δ42 = c42 - ( u4 + v2 ) = 0 - ( -2 + 5 ) = -3
A4B3 :   Δ43 = c43 - ( u4 + v3 ) = 0 - ( -2 + 4 ) = -2
Поставщик Потребитель   U  
B 1 B 2 B 3 B 4
A 1
220
4
80
5
3
6
  u1 = 0  
A 2
7
70
2
180
1
5
  u2 = -3  
A 3
6
1
70
4
130
2
  u3 = 0  
A 4
0
0
0
50
0
  u4 = -2  
  V     v1 = 4     v2 = 5     v3 = 4     v4 = 2  
Есть отрицательные оценки, следовательно, возможно получить новое решение, как минимум, не хуже имеющегося.
ШАГ №1.
Выберем ячейку A1B3, ее оценка отрицательная. Поставьте курсор мыши в выбранную ячейку A1B3.
Используя горизонтальные и вертикальные перемещения курсора, соедините непрерывной линией заполненные ячейки так, чтобы вернуться в исходную ячейку.
Ячейки, расположенные в вершинах построенной ломаной линии, образуют цикл для выбранной ячейки.
Он единственный. Направление обхода не имеет значения.
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
220
4
80
5
-1
3
6
  300  
A 2
7
70
2
180
1
5
  250  
A 3
6
1
70
4
130
2
  200  
A 4
0
0
0
50
0
  50  
  Потребность     220     150     250     180  
80 = min { 80, 180 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
220
4
80
5
-1
3
6
  300  
A 2
7
70
2
180
1
5
  250  
A 3
6
1
70
4
130
2
  200  
A 4
0
0
0
50
0
  50  
  Потребность     220     150     250     180  
Данное преобразование не изменит баланса.
А вот общая стоимость доставки продукции изменится на величину:
3 * 80 - 5 * 80 + 2 * 80 - 1 * 80 = ( 3 - 5 + 2 - 1 ) * 80 = -1 * 80 ден. ед.
Вы правильно заметили, что -1 * 80 = Δ13 * 80
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
220
4
80 - 80
5
+80
-1
3
6
  300  
A 2
7
70 + 80
2
180 - 80
1
5
  250  
A 3
6
1
70
4
130
2
  200  
A 4
0
0
0
50
0
  50  
  Потребность     220     150     250     180  
Получили новое решение.
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
220
4
5
80
3
6
  300  
A 2
7
150
2
100
1
5
  250  
A 3
6
1
70
4
130
2
  200  
A 4
0
0
0
50
0
  50  
  Потребность     220     150     250     180  
Общую сумму доставки продукции, для данного решения, легко посчитать.

S = 2140 + Δ13 * 80 = 2140 -1 * 80 = 2060 ден. ед.

Полученное решение является оптимальным?
Проверим.
Каждому поставщику A i ставим в соответствие некоторое число u i , называемое потенциалом поставщика.
Каждому потребителю B j ставим в соответствие некоторое число v j , называемое потенциалом потребителя.
Для задействованного маршрута, сумма потенциалов поставщика и потребителя равна тарифу задействованного маршрута.
Значение одного потенциала необходимо задать. Пусть u1 = 0.
Последовательно найдем значения потенциалов.
A1B1 :   v1 + u1 = 4         v1 = 4 - 0 = 4
A1B3 :   v3 + u1 = 3         v3 = 3 - 0 = 3
A2B3 :   v3 + u2 = 1         u2 = 1 - 3 = -2
A3B3 :   v3 + u3 = 4         u3 = 4 - 3 = 1
A3B4 :   v4 + u3 = 2         v4 = 2 - 1 = 1
A4B4 :   v4 + u4 = 0         u4 = 0 - 1 = -1
A2B2 :   v2 + u2 = 2         v2 = 2 - (-2) = 4
Найдем оценки незадействованных маршрутов.
A1B2 :   Δ12 = c12 - ( u1 + v2 ) = 5 - ( 0 + 4 ) = 1
A1B4 :   Δ14 = c14 - ( u1 + v4 ) = 6 - ( 0 + 1 ) = 5
A2B1 :   Δ21 = c21 - ( u2 + v1 ) = 7 - ( -2 + 4 ) = 5
A2B4 :   Δ24 = c24 - ( u2 + v4 ) = 5 - ( -2 + 1 ) = 6
A3B1 :   Δ31 = c31 - ( u3 + v1 ) = 6 - ( 1 + 4 ) = 1
A3B2 :   Δ32 = c32 - ( u3 + v2 ) = 1 - ( 1 + 4 ) = -4
A4B1 :   Δ41 = c41 - ( u4 + v1 ) = 0 - ( -1 + 4 ) = -3
A4B2 :   Δ42 = c42 - ( u4 + v2 ) = 0 - ( -1 + 4 ) = -3
A4B3 :   Δ43 = c43 - ( u4 + v3 ) = 0 - ( -1 + 3 ) = -2
Поставщик Потребитель   U  
B 1 B 2 B 3 B 4
A 1
220
4
5
80
3
6
  u1 = 0  
A 2
7
150
2
100
1
5
  u2 = -2  
A 3
6
1
70
4
130
2
  u3 = 1  
A 4
0
0
0
50
0
  u4 = -1  
  V     v1 = 4     v2 = 4     v3 = 3     v4 = 1  
Есть отрицательные оценки, следовательно, возможно получить новое решение, как минимум, не хуже имеющегося.
ШАГ №2.
Выберем ячейку A3B2, ее оценка отрицательная. Поставьте курсор мыши в выбранную ячейку A3B2.
Используя горизонтальные и вертикальные перемещения курсора, соедините непрерывной линией заполненные ячейки так, чтобы вернуться в исходную ячейку.
Ячейки, расположенные в вершинах построенной ломаной линии, образуют цикл для выбранной ячейки.
Он единственный. Направление обхода не имеет значения.
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
220
4
5
80
3
6
  300  
A 2
7
150
2
100
1
5
  250  
A 3
6
-4
1
70
4
130
2
  200  
A 4
0
0
0
50
0
  50  
  Потребность     220     150     250     180  
70 = min { 70, 150 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
220
4
5
80
3
6
  300  
A 2
7
150
2
100
1
5
  250  
A 3
6
-4
1
70
4
130
2
  200  
A 4
0
0
0
50
0
  50  
  Потребность     220     150     250     180  
Данное преобразование не изменит баланса.
А вот общая стоимость доставки продукции изменится на величину:
1 * 70 - 4 * 70 + 1 * 70 - 2 * 70 = ( 1 - 4 + 1 - 2 ) * 70 = -4 * 70 ден. ед.
Вы правильно заметили, что -4 * 70 = Δ32 * 70
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
220
4
5
80
3
6
  300  
A 2
7
150 - 70
2
100 + 70
1
5
  250  
A 3
6
+70
-4
1
70 - 70
4
130
2
  200  
A 4
0
0
0
50
0
  50  
  Потребность     220     150     250     180  
Получили новое решение.
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
220
4
5
80
3
6
  300  
A 2
7
80
2
170
1
5
  250  
A 3
6
70
1
4
130
2
  200  
A 4
0
0
0
50
0
  50  
  Потребность     220     150     250     180  
Общую сумму доставки продукции, для данного решения, легко посчитать.

S = 2060 + Δ32 * 70 = 2060 -4 * 70 = 1780 ден. ед.

Полученное решение является оптимальным?
Проверим.
Каждому поставщику A i ставим в соответствие некоторое число u i , называемое потенциалом поставщика.
Каждому потребителю B j ставим в соответствие некоторое число v j , называемое потенциалом потребителя.
Для задействованного маршрута, сумма потенциалов поставщика и потребителя равна тарифу задействованного маршрута.
Значение одного потенциала необходимо задать. Пусть u1 = 0.
Последовательно найдем значения потенциалов.
A1B1 :   v1 + u1 = 4         v1 = 4 - 0 = 4
A1B3 :   v3 + u1 = 3         v3 = 3 - 0 = 3
A2B3 :   v3 + u2 = 1         u2 = 1 - 3 = -2
A2B2 :   v2 + u2 = 2         v2 = 2 - (-2) = 4
A3B2 :   v2 + u3 = 1         u3 = 1 - 4 = -3
A3B4 :   v4 + u3 = 2         v4 = 2 - (-3) = 5
A4B4 :   v4 + u4 = 0         u4 = 0 - 5 = -5
Найдем оценки незадействованных маршрутов.
A1B2 :   Δ12 = c12 - ( u1 + v2 ) = 5 - ( 0 + 4 ) = 1
A1B4 :   Δ14 = c14 - ( u1 + v4 ) = 6 - ( 0 + 5 ) = 1
A2B1 :   Δ21 = c21 - ( u2 + v1 ) = 7 - ( -2 + 4 ) = 5
A2B4 :   Δ24 = c24 - ( u2 + v4 ) = 5 - ( -2 + 5 ) = 2
A3B1 :   Δ31 = c31 - ( u3 + v1 ) = 6 - ( -3 + 4 ) = 5
A3B3 :   Δ33 = c33 - ( u3 + v3 ) = 4 - ( -3 + 3 ) = 4
A4B1 :   Δ41 = c41 - ( u4 + v1 ) = 0 - ( -5 + 4 ) = 1
A4B2 :   Δ42 = c42 - ( u4 + v2 ) = 0 - ( -5 + 4 ) = 1
A4B3 :   Δ43 = c43 - ( u4 + v3 ) = 0 - ( -5 + 3 ) = 2
Поставщик Потребитель   U  
B 1 B 2 B 3 B 4
A 1
220
4
5
80
3
6
  u1 = 0  
A 2
7
80
2
170
1
5
  u2 = -2  
A 3
6
70
1
4
130
2
  u3 = -3  
A 4
0
0
0
50
0
  u4 = -5  
  V     v1 = 4     v2 = 4     v3 = 3     v4 = 5  
Нет отрицательных оценок, следовательно, уменьшить общую стоимость достаки продукции невозможно.

Ответ:

X опт =

Знак системы
220
0
80
0
Знак системы
0
80
170
0
0
70
0
130
0
0
0
50

Smin = 1780 ден. ед.










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



Ссылки