рис.3.2
Начальное решение имеет вид:
Общая стоимость перевозки:
ден. ед.
Проверим полученное решение на оптимальность. Проверку на оптимальность производим методом потенциалов.
Определим потенциалы поставщиков и потребителей, составив уравнения (где – стоимость перевозки с i-го склада на j-й пункт; – потенциал i-го поставщика; - потенциал j-го потребителя) для заполненных клеток:
Составляем разности для свободных клеток:
Если все разности , то найденный план перевозки грузов является оптимальным, в противном случае, его можно улучшить. Для ячейки изменяем цикл перевозок (см. рис. 3.2.), находим новое решение и проверяем его на оптимальность Пункты поставки
| Пункты потребления
| Имеется на складе
|
|
|
|
|
|
| 8
| 9
| 7
| 4
| 6
| 63
| 62
|
|
|
| 1
|
| 14
| 15
| 12
| 10
| 13
| 28
|
| 28
|
|
|
|
| 11
| 9
| 8
| 8
| 9
| 97
|
|
| 75
| 22
|
|
| 0
| 0
| 0
| 0
| 0
| 62
|
| 1
|
| 14
| 47
| Спрос на груз
| 62
| 29
| 75
| 36
| 48
|
| рис.3.3.
решение имеет вид:
Общая стоимость перевозки:
ден. ед.
Проверим полученное решение на оптимальность.
Составляем разности для свободных клеток:
. Для ячейки изменяем цикл перевозок (см. рис. 3.3.), находим новое решение и проверяем его на оптимальность Пункты поставки
| Пункты потребления
| Имеется на складе
|
|
|
|
|
|
| 9
| 10
| 8
| 5
| 7
| 67
| 26
|
|
|
| 41
|
| 8
| 9
| 6
| 4
| 7
| 6
|
| 6 -
|
| +
|
|
| 6
| 4
| 3
| 3
| 4
| 91
|
| 15 +
| 46
| 13 -
| 17
|
| 0
| 0
| 0
| 0
| 0
| 26
|
| 26
|
|
|
| Спрос на груз
| 26
| 47
| 46
| 13
| 58
|
|
рис.3.4
решение имеет вид:
Общая стоимость перевозки:
ден. ед.
Проверим полученное решение на оптимальность.
Составляем разности для свободных клеток:
. Для ячейки изменяем цикл перевозок (см. рис. 3.4.), находим новое решение и проверяем его на оптимальность Пункты поставки
| Пункты потребления
| Имеется на складе
|
|
|
|
|
|
| 9
| 10
| 8
| 5
| 7
| 67
| 26 -
|
|
|
| 41 +
|
| 8
| 9
| 6
| 4
| 7
| 6
|
|
|
| 6
|
|
| 6
| 4
| 3
| 3
| 4
| 91
|
| 21 +
| 46
| 7
| 17 -
|
| 0
| 0
| 0
| 0
| 0
| 26
| +
| 26 -
|
|
|
| Спрос на груз
| 26
| 47
| 46
| 13
| 58
|
| |