1.1. Закрытая транспортная задача
В задачах с закрытой моделью запасы поставщиков совпадают с потребностями потребителей.
Пример 1
Требуется перевезти однородный груз от трех поставщиков А1, А2, А3 к пяти потребителям В1, В2, В3, В4, В5:
Данные по запасам, потребностям в продукте и стоимости перевозок (в правых верхних углах) приведены в таблице 1.
Таблица 1
Пункт отправления |
Пункт назначения |
Запасы |
||||
В1 |
В2 |
В3 |
В4 |
В5 |
||
А1 |
2 х11 |
3 х12 |
4 х13 |
2 х14 |
4 х15 |
140 |
А2 |
8 х21 |
4 х22 |
1 х23 |
4 х24 |
1 х25 |
180 |
А3 |
9 х31 |
7 х32 |
3 х33 |
7 х34 |
2 х35 |
160 |
Потребности |
60 |
70 |
120 |
130 |
100 |
480 |
Построим опорный план методом северо-западного угла. При этом переменной х11 присваивается максимально допустимое значение в данном столбце (в нашем примере – 60). Затем, двигаясь вправо и вниз, заполняются другие клетки таблицы (таблица 2). По правилам, число заполненных клеток должно быть: m +n -1 = 3 + 5 - 1 = 7.
Таблица 2
-
v1
v2
v3
v4
v5
u1
2
60
3
70
4
10
2
4
u2
8
4
1
110
4
70
1
u3
9
7
3
7
60
2
100
Стоимость этого плана равна:
2*60+3*70+4*10+1*110+4*70+7*60+2*100=1380.
Определяем оптимальный план методом потенциала. Введем потенциалы u1, u2, u3, v1, v2, v3, v4, v5. Для заполненных клеток составляем систему уравнений для определения потенциалов:
ui +vj = Cij,
то есть
u
1
+v1
=2;
u1 +v2 =3;
u1 +v3 =4;
u2 +v3 =1; (3)
u2 +v4 =4;
u3 +v4 =7;
u3 +v5 =2.
Так как число переменных равно 8, а уравнений 7, то задаем значение одной из переменных произвольно. Удобно принять u1=0. Тогда из (3) получим значения потенциалов:
-
u1 =0;
u2 =-3;
u3 =0;
v1 =2;
v2 =3;
v3 =4;
v4 =7;
v5 =2.
Проверяем условия ui +vj < Cij для незаполненных клеток:
u1 +v4 =7 >2;
u1 +v5 =2 <4;
u2 +v1 =-1 <8;
u2 +v2 =0 <4;
u2 +v5 =-1 <1;
u3 +v2 =3 <7;
u3 +v1 =2 <9;
u3 +v3 =4 >3,
то есть для клеток х14 и х33 условие не выполняется. Для одной из этих клеток необходимо произвести перераспределение плана по циклу (выбирается клетка, где разница наибольшая, то есть х14: 7-2=5). Циклом называется ломаная линия, три вершины которой расположены в занятых клетках, а одна в свободной клетке. В нашем примере вершинами в выделенном цикле будут: [х13, х14, х24, х23]. В заполняемой клетке ставится знак «+», а рядом стоящим – «-». Знак «+/-» означает складывать или вычитать нужно переносимую величину со значением, стоящим в этой клетке (табл. 3). В заполняемую ячейку переносят меньшее значение из минусовых клеток. В данном примере это 10.
Таблица 3
-
v1=2
v2=3
v3=4
v4=7
v5=2
u1=0
2
60
3
70
4
10 -2
+
4
u2=-3
8
4
1+
110
- 4
70
1
u3=0
9
7
3
7
60
2
100
После перемещения получаем новый план:
Таблица 4
-
v1=2
v2=3
v3=4
v4=7
v5=2
u1=0
2
60
3
70
4
2
10
4
u2=-3
8
4
1
120
4
60
1
u3=0
9
7
3
7
60
2
100
Проверяем его на оптимальность и находим новые значения потенциалов.
u1 +v1 =2; u1 +v2 =3; u1 +v4 =2; u2 +v3 =1; u2 +v4 =4; u3 +v4 =7; u3 +v5 =2; |
u u2 =2; u3 =5;
|
v1 =2; v2 =3; v3 =-1; v4 =2; v5 =-3. |
1
=0;Проверяем условие ui +vj Cij для свободных клеток:
u1 +v3 =-1 4;
u1 +v5 =-3 4;
u2 +v1 =4 8;
u2 +v2 =5 4;
u2 +v5 =-1 1;
u3 +v1 =7 9;
u3 +v2 =8 7;
u3 +v3 =4 3.
Для ячеек х22 , х32 и х33 условие оптимальности не выполняется. Устанавливаем цикл с вершинами [х12, х14, х24, х22]. Наименьшее из минусовых клеток – 60.
Таблица 5
-
v1=2
v2=3
v3=2
v4=-1
v5=-3
u1=0
2
60
3
70
-4
2
+ 10
4
u2=2
8
4
+
1
120
4
- 60
1
u3=5
9
7
3
7
60
2
100
Далее решаем по аналогии:
-
u1 +v1 =2;
u1 +v2 =3;
u1 +v4 =2;
u2 +v4 =4;
u2 +v3 =1;
u3 +v4 =7;
u3 +v5 =2;
u
1
=0;u2 =1;
u3 =5;
v1 =2;
v2 =3;
v3 =0;
v4 =2;
v5 =-3.
Новый план примет вид:
Таблица 6
-
v1=2
v2=3
v3=0
v4=2
v5= -3
u1=0
2
60
3
10
4
2
70
4
u2=1
8
4
60
1
120
4
1
u3=5
9
7
3
7
60
2
100
Проверяем условие ui +vj Cij для свободных клеток
u1 +v3 =0 4;
u1 +v5 =-3 4;
u2 +v1 =3 8;
u2 +v4 =3 4;
u2 +v5 =-2 1;
u3 +v1 =7 9;
u3 +v2 =8 7;
u3 +v3 =5 3.
Для клетки х32 и х33 условие оптимальности не выполняется. Выбираем цикл с вершинами [х12, х14, х34, х32].
Таблица 7
-
v1=2
v2=3
v3=0
v4=2
v5= -3
u1=0
2
60
3
10 -4
2
+ 70
4
u2=1
8
4
60
1
120
4
1
u3=5
9
7 +
3
- 7
60
2
100
После перемещения 10 получаем новую таблицу:
Таблица 8
-
v1=2
v2=3
v3= 0
v4=2
v5= -3
u1=0
2
60
3
4
2
80
4
u2=1
8
4
60
1
120
4
1
u3=5
9
7
10
3
7
50
2
100
Решаем по аналогии:
-
u1 +v1 =2;
u1 +v4 =2;
u2 +v2 =4;
u2 +v3 =1;
u3 +v2 =7;
u3 +v4 =7;
u3 +v5 =2;
u
1
=0;u2 =2;
u3 =5;
v1 =2;
v2 =2;
v3 =-1;
v4 =2;
v5 =-3.
Проверяем условие ui +vj Cij:
u1 +v2 =2 3;
u1 +v3 =-1 4;
u1 +v5 =-3 4;
u2 +v1 =4 8;
u2 +v4 =4 = 4;
u2 +v5 =-1 1;
u3 +v1 =7 9;
u3 +v3 =4 3.
Для клетки х33 условие оптимальности не выполняется. Выбираем цикл с вершинами [х22, х23, х33, х32]
Таблица 9
-
v1=2
v2=2
v3= -1
v4=2
v5= -3
u1=0
2
60
3
4
2
80
4
u2=2
8
4
60 +1
- 120
4
1
u3=5
9
7 -
10
+ 3
7
50
2
100
Наименьшее отрицательное значение равно 10, после перемещения получаем таблицу:
Таблица 10
-
v1=2
v2=2
v3= -1
v4=2
v5= -3
u1=0
2
60
3
4
2
80
4
u2=2
8
4
70
1
110
4
1
u3=5
9
7
3
10
7
50
2
100
Находим потенциалы:
-
u1 +v1 =2;
u1 +v4 =2;
u2 +v2 =4;
u2 +v3 =1;
u3 +v3 =3;
u3 +v4 =7;
u3 +v5 =2;
u
1
=0;u2 =3;
u3 =5;
v1 =2;
v2 =2;
v3 =-2;
v4 =2;
v5 =-3.
Проверяем условие оптимальности ui +vj Cij:
u1 +v2 =2 3;
u1 +v3 =-2 4;
u1 +v5 =-3 4;
u2 +v1 =5 8;
u2 +v4 =5 4;
u2 +v5 =0 1;
u3 +v1 =7 9;
u3 +v2 =6 7.
Для клетки х24 условие оптимальности не выполняется. Выбираем цикл с вершинами [х23, х24, х34, х33].
Таблица 11
-
v1=2
v2=2
v3= -2
v4=2
v5= -3
u1=0
2
60
3
4
2
80
4
u2=3
8
4
70
1
110 -
4
+
1
u3=5
9
7
3 +
10
- 7
50
2
100
Перемещаем 50. Новый план представлен в таблице 12. Находим новые потенциалы:
u1 +v1 =2; u1 +v4 =2; u2 +v2 =4; u2 +v3 =1; u2 +v4 =4; u3 +v3 =3; u3 +v5 =2; |
u u2 =2; u3 =4;
|
v1 =2; v2 =2; v3 =-1; v4 =2; v5 =-2. |
1
=0;
Таблица 12
-
v1=2
v2=2
v3= -1
v4=2
v5= -2
u1=0
2
60
3
4
2
80
4
u2=2
8
4
70
1
60
4
50
1
u3=4
9
7
3
60
7
2
100
Проверяем условие оптимальности ui +vj Cij:
u1 +v2 =2 3;
u1 +v3 =-1 4;
u1 +v5 =-2 4;
u2 +v1 =4 8;
u2 +v5 =0 1;
u3 +v1 =6 9;
u3 +v2 =6 7;
u3 +v4 =6 7.
Условие оптимальности выполняется для всех клеток, значит и полученный план является оптимальным. Стоимость этого плана:
F = 2*60 +2*80 + 4*70 + 1*60 + 4*50 + 3*60 + 2*100 = 1000.