MOR_variant_8_inzhekon_18_04_15
.doc
Решение:
Проверим условие закрытости задачи:
Задача открытая. Введем потребителя с потребностью 70-50=20
Составим план методом наименьшей стоимости. Находим клетку с наименьшей стоимостью=1: клетки (2,1).Заполняем клетку (2,1)=min(15,14)=14. Исключаем из рассмотрения 2 столбец, так как потребности 2 потребителя удовлетворены. Заполняем следующую клетку (2,1)=min(1,20)=1. Исключаем из рассмотрения 2 строку, так как запасы 2 поставщика исчерпаны. Клетка (3,1) =min(25,19)=19, исключаем 1 столбец и т.д.
Пункты отправления |
Пункты назначения |
Запасы |
||||||||||||
|
|
|||||||||||||
5 |
2 |
+ |
* |
6 |
0 |
- |
14 |
30 |
0 |
|||||
|
16 |
|||||||||||||
2 |
+ |
1 |
1 |
- |
14 |
3 |
0 |
15 |
-2 |
|||||
|
|
|||||||||||||
4 |
- |
19 |
2 |
8 |
0 |
+ |
6 |
25 |
0 |
|||||
|
|
|||||||||||||
Потребности |
20 |
14 |
16 |
20 |
|
|
||||||||
4 |
3 |
6 |
0 |
|
|
Для занятых клеток подсчитаем потенциалы поставщиков и потребителей:
Положим , тогда, работая с занятыми клетками, получаем:
Для свободных клеток подсчитаем оценки :
, , ,
, , .
Так как среди чисел есть положительные, то полученный план не является оптимальным. Для клетки (1,2) строим цикл пересчета.
Пункты отправления |
Пункты назначения |
Запасы |
||||||||||||
|
|
|||||||||||||
5 |
2 |
6 |
- |
16 |
0 |
+ |
0 |
30 |
0 |
|||||
|
14 |
|||||||||||||
2 |
- |
15 |
1 |
3 |
+ |
* |
0 |
15 |
-2 |
|||||
|
|
|||||||||||||
4 |
+ |
5 |
2 |
8 |
0 |
- |
20 |
25 |
0 |
|||||
|
|
|||||||||||||
Потребности |
20 |
14 |
16 |
20 |
|
|
||||||||
4 |
2 |
6 |
0 |
|
|
Для занятых клеток подсчитаем потенциалы поставщиков и потребителей:
Положим , тогда, работая с занятыми клетками, получаем:
Для свободных клеток подсчитаем оценки :
, , ,
, , .
Так как среди чисел есть положительные, то полученный план не является оптимальным. Для клетки (2,3) строим цикл пересчета.
Пункты отправления |
Пункты назначения |
Запасы |
||||
|
|
|||||
5 |
2 |
6 |
0 |
30 |
0 |
|
|
14 |
1 |
15 |
|||
2 |
1 |
3 |
0 |
15 |
-3 |
|
|
|
15 |
|
|||
4 |
2 |
8 |
0 |
25 |
0 |
|
20 |
|
|
5 |
|||
Потребности |
20 |
14 |
16 |
20 |
|
|
4 |
2 |
6 |
0 |
|
|
Для занятых клеток подсчитаем потенциалы поставщиков и потребителей:
Положим , тогда, работая с занятыми клетками, получаем:
Для свободных клеток подсчитаем оценки :
, , ,
, , .
Так как среди чисел нет положительных, то полученный план является оптимальным.
.
При данном плане транспортные расходы составляют: