21. Транспортная задача (метод потенциалов).
Пример: Построим систему потенциалов для транспортной задачи.
a(100, 250, 200, 300) – вектор поставщиков
b(200, 200, 100, 100, 250) – вектор потребителей
C=
∑a=850 ∑b=850 –
закрытая модель
|
200 |
200 |
100 |
100 |
250 |
u |
|
100 |
10 |
7 |
4 |
1 |
4 |
-6 |
|
250 |
2 |
7 |
10 |
6 |
11 |
-1 |
|
200 |
8 |
5 |
3 |
2 |
2 |
-11 |
|
300 |
11 |
8 |
12 |
16 |
13 |
0 |
|
v |
3 |
8 |
12 |
7 |
13 |
|
|
Замечание:
Далее при решении задачи по методу
потенциалов выбирают клетку с наименьшей
отрицательной оценкой и выбранную
клетку включают в план перевозок. В этом
случае можно будет построить цикл,
проходящий через выбранную клетку и
какие-то – из занятых клеток. Выбранную
клетку помечают знаком «+» и идя по циклу
поочередно помечают клетки знаками
«-», «+». Далее рассматривают клетки,
помеченные знаками «-» и выбирают меньшую
перевозку (θ=min{
})
перераспределяют θ единиц груза по
циклу, прибавляя θ в клетках со знаком
«+» и отнимают θ в клетках со знаком «-».
На каждой итерации одна клетка должна
войти в план перевозок, а одна – выйти,
чтобы число занятых клеток оставалось
неизменным m=n-1.
Далее для получения нового плана строят систему потенциалов.
Пример: Продолжим предыдущий.
|
200 |
200 |
100 |
100 |
250 |
u |
|
100 |
10 |
7 |
-2 4 |
|
-3 4 |
-6 |
|
250 |
200 2 |
50 7 |
-1 10 |
6 |
-1 11 |
-1 |
|
200 |
8 |
5 |
3 |
2 |
2 |
-11 |
|
300 |
11 |
8 |
12 |
16 |
13 |
0 |
|
v |
3 |
150 8 |
100 12 |
7 |
13 |
|
|
100
1
|
200 |
200 |
100 |
100 |
250 |
u |
|
100 |
10 |
7 |
-2 4 |
50 1 |
4 |
-5 |
|
250 |
100 2 |
0 7 |
-1 10 |
50 6 |
11 |
0 |
|
200 |
8 |
5 |
-1 3 |
2 |
2 |
-7 |
|
300 |
11 |
200 8 |
100 12 |
16 |
13 |
1 |
|
v |
2 |
7 |
11 |
6 |
9 |
|
|
|
200 |
200 |
100 |
100 |
250 |
u |
|
100 |
10 |
7 |
4 |
50 1 |
50 4 |
0 |
|
250 |
200 2 |
7 |
10 |
50 6 |
11 |
5 |
|
200 |
8 |
5 |
3 |
2 |
200 2 |
-2 |
|
300 |
11 |
200 8 |
10012 |
16 |
13 |
8 |
|
v |
-3 |
0 |
4 |
1 |
4 |
|
|
X*=
Z min= 50*1+50*4+200*2+50*6+200*2+200*8+100*12=4150