2015-06-30
265
1) Определяется начальный опорный план перевозок любым из вышеперечисленных способов.
2) Для каждой строки и каждого столбца вводятся и рассчитываются потенциалы 
и 
соответственно.
Вот как это выглядит в таблице (в качестве начального опорного плана взята итоговая таблица, полученная в ходе выполнения алгоритма «план минимального элемента»):
| Номер склада | Количество товара на складе | Потребность потребителя 1 | Потребность потребителя 2 | Потребность потребителя 3 | Потребность потребителя 4 |
| ||||
|
|
Для расчета коэффициента используется формула
где 
- стоимость перевозки, записанная в i-строке, j-ом столбце.
Расчет потенциалов начинается с того что элемент 
предполагают равным нулю:
| Номер склада | Количество товара на складе | Потребность потребителя 1 | Потребность потребителя 2 | Потребность потребителя 3 | Потребность потребителя 4 |
| ||||
|
|
Дальше решаются уравнения 
для тех 
которые соответствуют ненулевым ячейкам:
|
|
|
| Номер склада | Количество товара на складе | Потребность потребителя 1 | Потребность потребителя 2 | Потребность потребителя 3 | Потребность потребителя 4 |
| ||||
|
|
Далее мы видим, что по формуле 
больше ничего подсчитать нельзя, так как остальные элементы первой строки = 0
Начинаем искать ненулевой элемент в таблице который можно зафигачить в одну из формул
Для другого примера эти формулы могут отличатся, так как могут быть по другому распределены перевозки. Думайте логически.
Такой элемент всего один:
| Номер склада | Количество товара на складе | Потребность потребителя 1 | Потребность потребителя 2 | Потребность потребителя 3 | Потребность потребителя 4 |
| ||||
|
|
Далее ищем подходящий элемент для формулы
Вот подходящий элемент:
| Номер склада | Количество товара на складе | Потребность потребителя 1 | Потребность потребителя 2 | Потребность потребителя 3 | Потребность потребителя 4 |
| ||||
|
|
Теперь можем найти 
|
|
|
| Номер склада | Количество товара на складе | Потребность потребителя 1 | Потребность потребителя 2 | Потребность потребителя 3 | Потребность потребителя 4 |
| ||||
| -1 | ||||||||||
|
|
И, наконец, находим последний потенциал
| Номер склада | Количество товара на складе | Потребность потребителя 1 | Потребность потребителя 2 | Потребность потребителя 3 | Потребность потребителя 4 |
| ||||
| -1 | ||||||||||
|
|
Далее среди всех ячеек = 0 мы ищем плохие ячейки.
Ячейка плоха, если 
Если таких клеток нет (для всех нулевых выполняется 
), возрадуйся, ибо тогда план перевозок оптимален, конец решения.
| Номер склада | Количество товара на складе | Потребность потребителя 1 | Потребность потребителя 2 | Потребность потребителя 3 | Потребность потребителя 4 |
| ||||
| -1 | ||||||||||
|
|
Итак, проверяем на условие
1>1+(-1) – хорошо
6>1+1– хорошо
6>2+(-1) – хорошо
5<6+0 – плохо
3=3+0 – хорошо
4=3+1 – хорошо
Нашли одну плохую клетку. Значит план неоптимальным
Если их будет больше, тогда для дальнейшей обработки берем любую из них (насчет этого я не уверен до конца, уточните это в учебнике).
Как сделать неоптимальный план оптимальным?
Берем эту плохую клетку и как-нибудь помечаем ее
| Номер склада | Количество товара на складе | Потребность потребителя 1 | Потребность потребителя 2 | Потребность потребителя 3 | Потребность потребителя 4 |
| ||||
| * | ||||||||||
| -1 | ||||||||||
|
|
Затем надо построить замкнутый маршрут обхода элементов таблицы.
Строится он по таким правилам:
1)Цикл начинается и заканчивается в плохой клетке
2)Цикл состоит из чередующихся вертикальных и горизонтальных звеньев (т.е. в маршруте после каждого шага мы поворачиваем на 90 градусов в подходящую сторону и доходим до следующей ячейки, причем, необязательно что бы следующая клетка была соседней, можно «перепрыгивать» клетки)
3)Каждое звено начинается и заканчивается в клетке со значением > 0 (кроме начальной плохой клетки)
4)Нельзя проходить по одной и той же клетке больше одного раза.
Эти маршруты могут быть довольно сложными.
Например:
  *
|  4
| |||
 33
|  10
| |||
 49
| ||||
Построив маршрут, помечаем знаками «+» и «-» те клетки, которые входят в маршрут по правилу:
Поставить «+» в плохую клетку с которой начинается цикл, и далее заносить знаки по мере движения по маршруту, чередуя их.
Например
| + *
| 4 -
| |||
 - 33
| 10 +
| |||
| 49 +
| 56 - | |||
Вернемся к нашему примеру, там маршрут гораздо легче
| Номер склада | Количество товара на складе | Потребность потребителя 1 | Потребность потребителя 2 | Потребность потребителя 3 | Потребность потребителя 4 |
| ||||
  40 -
|  + *
| |||||||||
| -1 | ||||||||||
 70 +
| 30 - | |||||||||
|
|
Далее ищем среди клеток, помеченных минусом, ячейку с наименьшим значением
|
|
|
| Номер склада | Количество товара на складе | Потребность потребителя 1 | Потребность потребителя 2 | Потребность потребителя 3 | Потребность потребителя 4 |
| ||||
| 40 -
| + *
| |||||||||
| -1 | ||||||||||
| 70 +
| 30 - | |||||||||
|
|
Вычитаем это значение из всех клеток, помеченных минусом, прибавляем это значение во все клетки с плюсом.
| Номер склада | Количество товара на складе | Потребность потребителя 1 | Потребность потребителя 2 | Потребность потребителя 3 | Потребность потребителя 4 |
| ||||
| 10
| 30
| |||||||||
| -1 | ||||||||||
| 100
| ||||||||||
|
|
Получаем таблицу
| Номер склада | Количество товара на складе | Потребность потребителя 1 | Потребность потребителя 2 | Потребность потребителя 3 | Потребность потребителя 4 |
| ||||
| -1 | ||||||||||
|
|
Обязательно проверяем, что ограничения (1*) и (2*) не нарушены
Теперь стираем все потенциалы кроме
| Номер склада | Количество товара на складе | Потребность потребителя 1 | Потребность потребителя 2 | Потребность потребителя 3 | Потребность потребителя 4 |
| ||||
|
|
Рассчитывай новые потенциалы (одна клетка обнулилась, одна получила значение > 0).
|
|
|
Если в новой таблице будут отсутствовать плохие ячейки, то решение оптимально.
| Номер склада | Количество товара на складе | Потребность потребителя 1 | Потребность потребителя 2 | Потребность потребителя 3 | Потребность потребителя 4 |
| ||||
|
|
Таки оптимально.
