Сервис для решения задач по линейному программированию

и другие интересные типовые задачи		 English

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

Данное решение сделано калькулятором, представленным на сайте.
Перейти к решению своей задачи
Задача:
Стоимость доставки единицы продукции от поставщика к потребителю располагается в правом нижнем углу ячейки.
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
4
5
3
6
   30  
A 2
7
2
1
5
   25  
A 3
6
1
4
2
   20  
  Потребность   20 15 25 20
Требуется составить план перевозок, при котором общая стоимость доставки продукции будет наименьшей.
Решение:
Для решения задачи необходимо выполнение следующего условия:
cуммарные запасы продукции у поставщиков должны равняться суммарной потребности потребителей.
Проверим.
Запасы поставщиков: 30 + 25 + 20 = 75 единиц продукции.
Потребность потребителей: 20 + 15 + 25 + 20 = 80 единиц продукции.
Разница в 5 единиц продукции.
Введем в рассмотрение фиктивного поставщика A4, с запасом продукции равным 5 единиц.
Стоимость доставки единицы продукции от поставщика A4 ко всем потребителям примем равной нулю (см. таблицу ниже).
Теперь суммарные запасы продукции у поставщиков равны суммарной потребности потребителей.
Для решения задачи необходимо выполнение следующего условия:
количество задействованных маршрутов = количество поставщиков + количество потребителей - 1.
Поэтому если возникнет ситуация, в которой будет необходимо исключить столбец и строку одновременно, мы исключим что-то одно.
Начинаем заполнять таблицу от левого верхнего угла и постепенно "двигаемся" к правому нижнему.
От северо-запада к юго-востоку.
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
?
4
5
3
6
   30  
A 2
7
2
1
5
   25  
A 3
6
1
4
2
   20  
A 4
0
0
0
0
   5  
  Потребность   20 15 25 20
20 = min { 20, 30 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
20
4
?
5
3
6
   30   10  
A 2
7
2
1
5
   25  
A 3
6
1
4
2
   20  
A 4
0
0
0
0
   5  
  Потребность   20
нет		 15 25 20
10 = min { 15, 10 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
20
4
10
5
3
6
   30   10   нет  
A 2
7
?
2
1
5
   25  
A 3
6
1
4
2
   20  
A 4
0
0
0
0
   5  
  Потребность   20
нет		 15
5 		25 20
5 = min { 5, 25 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
20
4
10
5
3
6
   30   10   нет  
A 2
7
5
2
?
1
5
   25   20  
A 3
6
1
4
2
   20  
A 4
0
0
0
0
   5  
  Потребность   20
нет		 15
5
нет		 25 20
20 = min { 25, 20 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
20
4
10
5
3
6
   30   10   нет  
A 2
7
5
2
20
1
5
   25   20   нет  
A 3
6
1
?
4
2
   20  
A 4
0
0
0
0
   5  
  Потребность   20
нет		 15
5
нет		 25
5 		20
5 = min { 5, 20 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
20
4
10
5
3
6
   30   10   нет  
A 2
7
5
2
20
1
5
   25   20   нет  
A 3
6
1
5
4
?
2
   20   15  
A 4
0
0
0
0
   5  
  Потребность   20
нет		 15
5
нет		 25
5
нет		 20
15 = min { 20, 15 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
20
4
10
5
3
6
   30   10   нет  
A 2
7
5
2
20
1
5
   25   20   нет  
A 3
6
1
5
4
15
2
   20   15   нет  
A 4
0
0
0
?
0
   5  
  Потребность   20
нет		 15
5
нет		 25
5
нет		 20
5
5 = min { 5, 5 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
20
4
10
5
3
6
   30   10   нет  
A 2
7
5
2
20
1
5
   25   20   нет  
A 3
6
1
5
4
15
2
   20   15   нет  
A 4
0
0
0
5
0
   5   нет  
  Потребность   20
нет		 15
5
нет		 25
5
нет		 20
5
нет
Стоимость доставки продукции, для начального решения, не сложно посчитать.

20*4 + 10*5 + 5*2 + 20*1 + 5*4 + 15*2 + 5*0 = 210 ден. ед.

Полученное решение является оптимальным?
Проверим.
Каждому поставщику 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
Подробнее о нахождении потенциалов
  Поставщик   Потребитель   U  
B 1 B 2 B 3 B 4
A 1
20
4
10
5
3
6
   u1 = 0  
A 2
7
5
2
20
1
5
   u2 = -3  
A 3
6
1
5
4
15
2
   u3 = 0  
A 4
0
0
0
5
0
   u4 = -2  
  V   v1 = 4 v2 = 5 v3 = 4 v4 = 2
Найдем оценки незадействованных маршрутов (cij - стоимость доставки). ?
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
Есть отрицательные оценки. Следовательно, возможно получить новое решение, как минимум, не хуже имеющегося.
ШАГ №1.
Выберем ячейку A3B2, ее оценка отрицательная. ? Пожалуйста, поставьте курсор мыши в выбранную ячейку A3B2
Используя только горизонтальные и вертикальные перемещения курсора, соедините непрерывной линией заполненные ячейки так, чтобы вернуться в исходную ячейку A3B2
Ячейки, расположенные в вершинах построенной ломаной линии, образуют цикл для выбранной ячейки
(см. выделенные ячейки в таблице ниже). Он единственный. Направление обхода не имеет значения.
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
20
4
10
5
3
6
   30  
A 2
7
5
2
20
1
5
   25  
A 3
6
-4
1
5
4
15
2
   20  
A 4
0
0
0
5
0
   5  
  Потребность     20     15     25     20  
5 = min { 5, 5 } ?
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
20
4
10
5
3
6
   30  
A 2
7
5
2
20
1
5
   25  
A 3
6
-4
1
5
4
15
2
   20  
A 4
0
0
0
5
0
   5  
  Потребность     20     15     25     20  
Данное преобразование не изменит баланса.
А вот общая стоимость доставки продукции изменится на величину:
1 * 5 - 4 * 5 + 1 * 5 - 2 * 5 = ( 1 - 4 + 1 - 2 ) * 5 = -4 * 5 ден. ед.
Вы правильно заметили, что -4 * 5 = Δ32 * 5 ?
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
20
4
10
5
3
6
   30  
A 2
7
5 - 5
2
20 + 5
1
5
   25  
A 3
6
+5
-4
1
5 - 5
4
15
2
   20  
A 4
0
0
0
5
0
   5  
  Потребность     20     15     25     20  
Получили новое решение. ?
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
20
4
10
5
3
6
   30  
A 2
7
0
2
25
1
5
   25  
A 3
6
5
1
4
15
2
   20  
A 4
0
0
0
5
0
   5  
  Потребность     20     15     25     20  
Общую сумму доставки продукции, для данного решения, легко посчитать.

S = 210 + Δ32 * 5 = 210 -4 * 5 = 190 ден. ед.

Полученное решение является оптимальным?
Проверим.
Каждому поставщику 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
A3B2 :   v2 + u3 = 1     u3 = 1 - 5 = -4
A3B4 :   v4 + u3 = 2     v4 = 2 - (-4) = 6
A4B4 :   v4 + u4 = 0     u4 = 0 - 6 = -6
Подробнее о нахождении потенциалов
  Поставщик   Потребитель   U  
B 1 B 2 B 3 B 4
A 1
20
4
10
5
3
6
   u1 = 0  
A 2
7
0
2
25
1
5
   u2 = -3  
A 3
6
5
1
4
15
2
   u3 = -4  
A 4
0
0
0
5
0
   u4 = -6  
  V   v1 = 4 v2 = 5 v3 = 4 v4 = 6
Найдем оценки незадействованных маршрутов (cij - стоимость доставки). ?
A1B3 :   Δ13 = c13 - ( u1 + v3 ) = 3 - ( 0 + 4 ) = -1
A1B4 :   Δ14 = c14 - ( u1 + v4 ) = 6 - ( 0 + 6 ) = 0
A2B1 :   Δ21 = c21 - ( u2 + v1 ) = 7 - ( -3 + 4 ) = 6
A2B4 :   Δ24 = c24 - ( u2 + v4 ) = 5 - ( -3 + 6 ) = 2
A3B1 :   Δ31 = c31 - ( u3 + v1 ) = 6 - ( -4 + 4 ) = 6
A3B3 :   Δ33 = c33 - ( u3 + v3 ) = 4 - ( -4 + 4 ) = 4
A4B1 :   Δ41 = c41 - ( u4 + v1 ) = 0 - ( -6 + 4 ) = 2
A4B2 :   Δ42 = c42 - ( u4 + v2 ) = 0 - ( -6 + 5 ) = 1
A4B3 :   Δ43 = c43 - ( u4 + v3 ) = 0 - ( -6 + 4 ) = 2
Есть отрицательная оценка. Следовательно, возможно получить новое решение, как минимум, не хуже имеющегося.
ШАГ №2.
Выберем ячейку A1B3, ее оценка отрицательная. Пожалуйста, поставьте курсор мыши в выбранную ячейку A1B3
Используя только горизонтальные и вертикальные перемещения курсора, соедините непрерывной линией заполненные ячейки так, чтобы вернуться в исходную ячейку A1B3
Ячейки, расположенные в вершинах построенной ломаной линии, образуют цикл для выбранной ячейки
(см. выделенные ячейки в таблице ниже). Он единственный. Направление обхода не имеет значения.
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
20
4
10
5
-1
3
6
   30  
A 2
7
0
2
25
1
5
   25  
A 3
6
5
1
4
15
2
   20  
A 4
0
0
0
5
0
   5  
  Потребность     20     15     25     20  
10 = min { 10, 25 } ?
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
20
4
10
5
-1
3
6
   30  
A 2
7
0
2
25
1
5
   25  
A 3
6
5
1
4
15
2
   20  
A 4
0
0
0
5
0
   5  
  Потребность     20     15     25     20  
Данное преобразование не изменит баланса.
А вот общая стоимость доставки продукции изменится на величину:
3 * 10 - 5 * 10 + 2 * 10 - 1 * 10 = ( 3 - 5 + 2 - 1 ) * 10 = -1 * 10 ден. ед.
Вы правильно заметили, что -1 * 10 = Δ13 * 10 ?
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
20
4
10 - 10
5
+10
-1
3
6
   30  
A 2
7
0 + 10
2
25 - 10
1
5
   25  
A 3
6
5
1
4
15
2
   20  
A 4
0
0
0
5
0
   5  
  Потребность     20     15     25     20  
Получили новое решение. ?
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
20
4
5
10
3
6
   30  
A 2
7
10
2
15
1
5
   25  
A 3
6
5
1
4
15
2
   20  
A 4
0
0
0
5
0
   5  
  Потребность     20     15     25     20  
Общую сумму доставки продукции, для данного решения, легко посчитать.

S = 190 + Δ13 * 10 = 190 -1 * 10 = 180 ден. ед.

Полученное решение является оптимальным?
Проверим.
Каждому поставщику 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
Подробнее о нахождении потенциалов
  Поставщик   Потребитель   U  
B 1 B 2 B 3 B 4
A 1
20
4
5
10
3
6
   u1 = 0  
A 2
7
10
2
15
1
5
   u2 = -2  
A 3
6
5
1
4
15
2
   u3 = -3  
A 4
0
0
0
5
0
   u4 = -5  
  V   v1 = 4 v2 = 4 v3 = 3 v4 = 5
Найдем оценки незадействованных маршрутов (cij - стоимость доставки). ?
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
Нет отрицательных оценок. Следовательно, уменьшить общую стоимость доставки продукции невозможно.
Ответ:

X опт =

Знак матрицы200100Знак матрицы
010150
05015
0005

Smin = 180 ден. ед.


Перейти к решению своей задачи
Наверх








© 2010-2024

Если у Вас есть замечания, пожалуйста, пишите siteReshmat@yandex.ru


Ссылки