Логотип

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

Главная >> Пример №4. Транспортная задача. Метод северо-западного угла (сбалансированная задача).

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

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

Задача:
Стоимость доставки единицы продукции от поставщика к потребителю располагается в правом нижнем углу ячейки.
Поставщик Потребитель   Запас  
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
  190  
  Потребность   150 130 150 140
Требуется составить план перевозок, при котором общая стоимость доставки продукции будет наименьшей.
Решение:
Для решения задачи необходимо выполнение следующего условия:
cуммарные запасы продукции у поставщиков должны равняться суммарной потребности потребителей.

Проверим.
Запасы поставщиков: 200 + 180 + 190 = 570 единиц продукции.
Потребность потребителей: 150 + 130 + 150 + 140 = 570 единиц продукции.
Суммарные запасы продукции у поставщиков равны суммарной потребности потребителей.
Для решения задачи необходимо выполнение следующего условия:
количество задействованных маршрутов = количество поставщиков + количество потребителей - 1.

Поэтому если возникнет ситуация, в которой будет необходимо исключить столбец и строку одновременно, мы исключим что-то одно.
Начинаем заполнять таблицу от левого верхнего угла и постепенно "двигаемся" к правому нижнему.
От северо-запада к юго-востоку.
Поставщик Потребитель   Запас  
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
  190  
  Потребность   150 130 150 140
150 = min { 150, 200 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
150
7
8
1
2
  200   50  
A 2
4
5
9
8
  180  
A 3
9
2
3
6
  190  
  Потребность   150
нет
130 150 140
50 = min { 130, 50 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
150
7
50
8
1
2
  200   50   нет  
A 2
4
5
9
8
  180  
A 3
9
2
3
6
  190  
  Потребность   150
нет
130
80
150 140
80 = min { 80, 180 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
150
7
50
8
1
2
  200   50   нет  
A 2
4
80
5
9
8
  180   100  
A 3
9
2
3
6
  190  
  Потребность   150
нет
130
80
нет
150 140
100 = min { 150, 100 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
150
7
50
8
1
2
  200   50   нет  
A 2
4
80
5
100
9
8
  180   100   нет  
A 3
9
2
3
6
  190  
  Потребность   150
нет
130
80
нет
150
50
140
50 = min { 50, 190 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
150
7
50
8
1
2
  200   50   нет  
A 2
4
80
5
100
9
8
  180   100   нет  
A 3
9
2
50
3
6
  190   140  
  Потребность   150
нет
130
80
нет
150
50
нет
140
140 = min { 140, 140 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3 B 4
A 1
150
7
50
8
1
2
  200   50   нет  
A 2
4
80
5
100
9
8
  180   100   нет  
A 3
9
2
50
3
140
6
  190   140   нет  
  Потребность   150
нет
130
80
нет
150
50
нет
140
нет
Стоимость доставки продукции, для начального решения, не сложно посчитать.

150*7 + 50*8 + 80*5 + 100*9 + 50*3 + 140*6 = 3740 ден. ед.

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

S = 3740 + Δ14 * 50 = 3740 -13 * 50 = 3090 ден. ед.

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

S = 3090 + Δ21 * 50 = 3090 -13 * 50 = 2440 ден. ед.

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

S = 2440 + Δ32 * 40 = 2440 -10 * 40 = 2040 ден. ед.

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

S = 2040 + Δ13 * 60 = 2040 -8 * 60 = 1560 ден. ед.

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

Ответ:

X опт =

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

Smin = 1560 ден. ед.











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


Ссылки