Логотип

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

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

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

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

Проверим.
Запасы поставщиков: 20 + 40 + 30 = 90 единиц продукции.
Потребность потребителей: 30 + 35 + 20 = 85 единиц продукции.
Разница в 5 единиц продукции.
Введем в рассмотрение фиктивного потребителя B4, с потребностью 5 единиц продукции.
Стоимость доставки единицы продукции от всех поставщиков к потребителю B4 примем равной нулю (см. таблицу ниже).
Теперь суммарные запасы продукции у поставщиков равны суммарной потребности потребителей.
Для решения задачи необходимо выполнение следующего условия:
количество задействованных маршрутов = количество поставщиков + количество потребителей - 1.

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

20*3 + 10*6 + 30*3 + 5*2 + 20*7 + 5*0 = 360 ден. ед.

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

S = 360 + Δ23 * 20 = 360 -7 * 20 = 220 ден. ед.

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

S = 220 + Δ24 * 5 = 220 -1 * 5 = 215 ден. ед.

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

S = 215 + Δ31 * 10 = 215 -2 * 10 = 195 ден. ед.

Полученное решение является оптимальным?
Проверим.
Каждому поставщику A i ставим в соответствие некоторое число u i , называемое потенциалом поставщика.
Каждому потребителю B j ставим в соответствие некоторое число v j , называемое потенциалом потребителя.
Для задействованного маршрута, сумма потенциалов поставщика и потребителя равна тарифу задействованного маршрута.
Значение одного потенциала необходимо задать. Пусть u2 = 0.
Последовательно найдем значения потенциалов.
A2B2 :   v2 + u2 = 3         v2 = 3 - 0 = 3
A2B3 :   v3 + u2 = 1         v3 = 1 - 0 = 1
A2B4 :   v4 + u2 = 0         v4 = 0 - 0 = 0
A3B2 :   v2 + u3 = 2         u3 = 2 - 3 = -1
A3B1 :   v1 + u3 = 3         v1 = 3 - (-1) = 4
A1B1 :   v1 + u1 = 3         u1 = 3 - 4 = -1
Найдем оценки незадействованных маршрутов.
A1B2 :   Δ12 = c12 - ( u1 + v2 ) = 5 - ( -1 + 3 ) = 3
A1B3 :   Δ13 = c13 - ( u1 + v3 ) = 4 - ( -1 + 1 ) = 4
A1B4 :   Δ14 = c14 - ( u1 + v4 ) = 0 - ( -1 + 0 ) = 1
A2B1 :   Δ21 = c21 - ( u2 + v1 ) = 6 - ( 0 + 4 ) = 2
A3B3 :   Δ33 = c33 - ( u3 + v3 ) = 7 - ( -1 + 1 ) = 7
A3B4 :   Δ34 = c34 - ( u3 + v4 ) = 0 - ( -1 + 0 ) = 1
Поставщик Потребитель   U  
B 1 B 2 B 3 B 4
A 1
20
3
5
4
0
  u1 = -1  
A 2
6
15
3
20
1
5
0
  u2 = 0  
A 3
10
3
20
2
7
0
  u3 = -1  
  V     v1 = 4     v2 = 3     v3 = 1     v4 = 0  
Нет отрицательных оценок, следовательно, уменьшить общую стоимость достаки продукции невозможно.

Ответ:

X опт =

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

Smin = 195 ден. ед.










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



Ссылки