Логотип

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

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

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

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

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

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

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

5*8 + 5*3 + 5*1 + 10*6 + 10*4 + 15*3 + 10*0 = 205 ден. ед.

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

S = 205 + Δ14 * 5 = 205 -5 * 5 = 180 ден. ед.

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

S = 180 + Δ31 * 5 = 180 -8 * 5 = 140 ден. ед.

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

S = 140 + Δ43 * 10 = 140 -1 * 10 = 130 ден. ед.

Полученное решение является оптимальным?
Проверим.
Каждому поставщику A i ставим в соответствие некоторое число u i , называемое потенциалом поставщика.
Каждому потребителю B j ставим в соответствие некоторое число v j , называемое потенциалом потребителя.
Для задействованного маршрута, сумма потенциалов поставщика и потребителя равна тарифу задействованного маршрута.
Значение одного потенциала необходимо задать. Пусть u3 = 0.
Последовательно найдем значения потенциалов.
A3B1 :   v1 + u3 = 1         v1 = 1 - 0 = 1
A3B3 :   v3 + u3 = 4         v3 = 4 - 0 = 4
A3B4 :   v4 + u3 = 3         v4 = 3 - 0 = 3
A4B3 :   v3 + u4 = 0         u4 = 0 - 4 = -4
A1B4 :   v4 + u1 = 2         u1 = 2 - 3 = -1
A2B3 :   v3 + u2 = 6         u2 = 6 - 4 = 2
A2B2 :   v2 + u2 = 1         v2 = 1 - 2 = -1
Найдем оценки незадействованных маршрутов.
A1B1 :   Δ11 = c11 - ( u1 + v1 ) = 8 - ( -1 + 1 ) = 8
A1B2 :   Δ12 = c12 - ( u1 + v2 ) = 3 - ( -1 + -1 ) = 5
A1B3 :   Δ13 = c13 - ( u1 + v3 ) = 5 - ( -1 + 4 ) = 2
A2B1 :   Δ21 = c21 - ( u2 + v1 ) = 4 - ( 2 + 1 ) = 1
A2B4 :   Δ24 = c24 - ( u2 + v4 ) = 7 - ( 2 + 3 ) = 2
A3B2 :   Δ32 = c32 - ( u3 + v2 ) = 9 - ( 0 + -1 ) = 10
A4B1 :   Δ41 = c41 - ( u4 + v1 ) = 0 - ( -4 + 1 ) = 3
A4B2 :   Δ42 = c42 - ( u4 + v2 ) = 0 - ( -4 + -1 ) = 5
A4B4 :   Δ44 = c44 - ( u4 + v4 ) = 0 - ( -4 + 3 ) = 1
Поставщик Потребитель   U  
B 1 B 2 B 3 B 4
A 1
8
3
5
10
2
  u1 = -1  
A 2
4
10
1
5
6
7
  u2 = 2  
A 3
5
1
9
5
4
15
3
  u3 = 0  
A 4
0
0
10
0
0
  u4 = -4  
  V     v1 = 1     v2 = -1     v3 = 4     v4 = 3  
Нет отрицательных оценок, следовательно, уменьшить общую стоимость достаки продукции невозможно.

Ответ:

X опт =

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

Smin = 130 ден. ед.











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


Ссылки