Исследование операций. Линейное, динамическое программирование



Исследование операций - часть 62


Если такая клетка есть, нужно для нее найти цикл, вычислить его цену и, если она будет отрицательной, перенести по этому циклу столько единиц груза, сколько будет возможно (без того, чтобы какие-то перевозки сделать отрицательными). При этом данная свободная клетка становится базисной, а какая-то из бывших базисных — свободной. Очевидно, это равносильно «переразрешению» системы уравнений относительно других базисных переменных, по делается это гораздо легче.

Попробуем еще раз улучшить план, приведенный и таблице 10.3. Например, нас «соблазняет» дешевая клетка (1.5) со стоимостью 5. Нельзя ли улучшить план, увеличив перевозки в этой клетке, зато, уменьшив в других (при этом, конечно, придется кое-где перевозки тоже увеличить). Давайте разглядим внимательно таблицу 10.3 и найдем в пей цикл, первая вершина которого лежит в свободной клетке (1.5), а остальные — все в базисных клетках.' Немного подумав, мы этот цикл обнаружим: это последовательность клеток (1.5)

 (4.5)
 (4.4)
 (2.4)
 (2.2)
 (1.2) (и замыкая цикл, снова возвращаемся в (1.5)). Нечетные вершины цикла отмечены плюсом — это значит, что перевозки в этих клетках увеличиваются: четные — знаком минус (перевозки уменьшаются). Цикл показан стрелками в таблице 10.4.

Подсчитаем цену этого цикла. Она равна 5 – 15 + 10 – 6 + 8 - 7= - 5. Так как цена цикла отрицатель-па, то переброска перевозок по этому циклу выгодна. Посмотрим, сколько же единиц мы можем по нему перебросить? Это определяется наименьшей перевозкой, стоящей в отрицательной вершине цикла. В данном случае это опять 11 (чистое совпадение!). Умножая 11 па цепу цикла — 5 получим, что за счет переброски 11 единиц груза по данному циклу мы еще уменьшим стоимость перевозок на 55 (предоставляем любознательному читателю сделать это самостоятельно).

Таким образом, разыскивая в транспортной таблице свободные клетки с отрицательной ценой цикла и перебрасывая по этому циклу наибольшее возможное количество груза, мы будем все уменьшать и уменьшать стоимость перевозок.


Содержание  Назад  Вперед