Мастерская программиста Гирича Семёна Николаевича
Решение задач линейного программирования
Главная Ассемблер     1С     Статьи Скачать

6.5. Пример решения транспортной задачи

Задача:

Решить транспортную задачу.

Постав- Потребители и их спрос   Мощность         
щики    1      2      3      4  поставщиков
        33     13     27     17
1       14(27) 28     21     28       27
2       10(6)  17(13) 15(1)  24       20
3       14     30     25(26) 21(17)   43
Первоначальный план получен по методу северо-западного угла.
 

Таблица - план перевозок по условию задачи:

Поставщики
и их ресурсы		 Потребители и их спрос
B1
33
B2
13
B3
27
B4
17
A1
27
14
27
28
0
21
0
28
0
A2
20
10
6
17
13
15
1
24
0
A3
43
14
0
30
0
25
26
21
17

Решение задачи.

Первоначальный план перевозок.

Задача сбалансированная (закрытая).
Таблица 1.
Поставщики
и их ресурсы		 Потребители и их спрос
B1
33
B2
13
B3
27
B4
17
A1
27
14
27
28
0
21
0
28
0
A2
20
10
6
17
13
15
1
24
0
A3
43
14
0
30
0
25
26
21
17
Стоимость перевозок по данному плану составляет: 1681

Решим задачу с применением метода потенциалов.

1. Рассчитаем потенциалы пунктов отправки и пунктов доставки alfa и betta. Для этого составьте систему для заполненных клеток плана перевозок: betta[j] - alfa[i] = C[i,j]; где C - стоимость перевозки из пункта i в пункт j. Решим данную систему, полагая alfa[1]=0.

2. Вычислим коэффициенты изменения стоимости ( dC[i,j] ) для незаполненных клеток плана: dC[i,j] =betta[j] - alfa[i] - C[i,j];


Таблица 2.
Поставщики
и их ресурсы		 Потребители и их спрос alfa
B1
33
B2
13
B3
27
B4
17
A1
27
14
0 27
28
-7 0
21
-2 0
28
-13 0
 0
A2
20
10 [-6]
0 6
17
0 13
15 [+6]
0 1
24
-13 0
 4
A3
43
14 [+6]
6 0
30
-3 0
25 [-6]
0 26
21
0 17
 -6
betta 14 21 19 15
Стоимость перевозок по данному плану составляет: 1681
Получим потенциалы alfa и betta. Рассчитаем коэффициенты изменения стоимости перевозок.
Составим цикл пересчета:
Опорная клетка: (3:1) , далее (3:3) [-6], (2:3) [+6], (2:1) [-6]
Количество единиц изменения плана: 6
Потенциалы, коэффициенты и цикл пересчета указаны в таблице 2.
Получим следующий план перевозок (Табл.3)
Таблица 3.
Поставщики
и их ресурсы		 Потребители и их спрос alfa
B1
33
B2
13
B3
27
B4
17
A1
27
14 [-20]
0 27
28
-1 0
21 [+20]
4 0
28
-7 0
 0
A2
20
10
-6 0
17
0 13
15
0 7
24
-13 0
 10
A3
43
14 [+20]
0 6
30
-3 0
25 [-20]
0 20
21
0 17
 0
betta 14 27 25 21
Стоимость перевозок по данному плану составляет: 1645
Получим потенциалы alfa и betta. Рассчитаем коэффициенты изменения стоимости перевозок.
Составим цикл пересчета:
Опорная клетка: (1:3) , далее (1:1) [-20], (3:1) [+20], (3:3) [-20]
Количество единиц изменения плана: 20
Потенциалы, коэффициенты и цикл пересчета указаны в таблице 3.
Получим следующий план перевозок (Табл.4)
Таблица 4.
Поставщики
и их ресурсы		 Потребители и их спрос alfa
B1
33
B2
13
B3
27
B4
17
A1
27
14
0 7
28
-5 0
21
0 20
28
-7 0
 0
A2
20
10
-2 0
17
0 13
15
0 7
24
-9 0
 6
A3
43
14
0 26
30
-7 0
25
-4 0
21
0 17
 0
betta 14 23 21 21
Стоимость перевозок по данному плану составляет: 1565
Получим потенциалы alfa и betta. Рассчитаем коэффициенты изменения стоимости перевозок.
Потенциалы и коэффициенты указаны в таблице 4.
Полученный план оптимальный, т.к. все коэффициенты изменения стоимости (dC[i,j]) отрицательны или равны нулю.

Вернуться в Начало
© 2011 Семён Гирич,
Система Orphus: Выделите текст с ошибкой и нажмите [Ctrl] + [Enter]
Назад    Вверх