Содержание
Вид материала | Документы |
Содержание4.5. Алгоритм улучшения плана Вторая итерация Этап 1 |
- Содержание дисциплины наименование тем, их содержание, объем в часах лекционных занятий, 200.99kb.
- Содержание рабочей программы Содержание обучения по профессиональному модулю (ПМ) Наименование, 139.63kb.
- Заключительный отчет июль 2010 содержание содержание 1 список аббревиатур 3 введение, 6029.85kb.
- 5. Содержание родительского правоотношения Содержание правоотношения, 110.97kb.
- Содержание введение, 1420.36kb.
- Сборник статей Содержание, 1251.1kb.
- Сборник статей Содержание, 1248.25kb.
- Анонсы ведущих периодических изданий содержание выпуска, 806.18kb.
- Вопросы к экзамену по дисциплине «Коммерческая деятельность», 28.08kb.
- Конспект лекций содержание содержание 3 налог на прибыль организаций 5 Плательщики, 795.2kb.
4.5. Алгоритм улучшения плана
Сформулируем теперь алгоритм перехода к новому опорному плану, дающему меньшее значение функции потерь. Прежде, чем формулировать его в общем виде, покажем его основные моменты на том примере, который мы начали рассматривать.
Вспомним, что ограничения двойственной задачи соответствовали тому, что , а выполнение условия говорило о том, что соответствующий вектор надо вводить в базис. Поэтому и выполнение
условия | говорит о том, что вектор | надо вводить в базис. |
У нас условие выполнено в двух случаях для и . Вообще
принято вводить в базис тот вектор, для которого |
максимально. В данном случае это вектор , | но в учебных целях мы |
введем в базис вектор . |
Введение в базис вектора означает, что мы должны запланировать какую-то перевозку из третьего склада в первый пункт потребления. Пусть величина этой перевозки равна . Поставим ее в клетку, соответствующую i =3, j =1. Тогда мы получим следующий план перевозок:
2 | 3.1 | | |
| 3.9 | 4.2 | |
| | 2.8 | 6.3 |
Но теперь у нас нарушился баланс запасов и потребностей получилось, что
из третьего склада вывозится , | а в первый пункт потребления |
поступает . | |
Необходимо восстановить баланс запасов и потребностей. Для этого поступают следующим образом: по ненулевым компонентам плана перевозок (включая и компоненту ) строят цикл вида столбец строка столбец строка ... строка (см. рисунок), который начинается и кончается на компоненте .
Теперь для восстановления баланса запасов и потребностей можно поступить очень просто: при движении по столбцу от имеющихся компонентов плана надо отнимать , а при движении по строке наоборот, прибавлять . В результате получится следующий план перевозок, уже сохраняющий баланс запасов и потребностей:
2- | 3.1+ | | |
| 3.9- | 4.2+ | |
| | 2.8- | 6.3 |
С балансом всё в порядке, но теперь у нас стало компонент плана, а должно быть . Поэтому надо выбрать так, чтобы одна из бывших компонент обратилась в нуль, но все остальные компоненты остались положительными. Легко догадаться, что для этого надо взять равным минимальному из тех чисел, из которых вычитается. В нашем случае вычитается из чисел 2; 3.9; 2.8 . Минимальное из них есть 2 и поэтому надо взять =2.
В результате получится новый опорный план следующего вида
| 5.1 | | |
| 1.9 | 6.2 | |
2 | | 0.8 | 6.3 |
в котором снова будет положенные ему | компонент. |
Вычисляя транспортные расходы для этого плана, мы получим , откуда видно, что по сравнению с исходным планом транспортные расходы уменьшились на 2 единицы.
Опишем этот процесс в общем виде.
Итак, пусть для некоторой пары индексов выполнено условие . Тогда вектор надо вводить в базис. Если таких векторов окажется несколько, то обычно вводят в базис тот вектор, для которого
величина разности | максимальна. |
Исходя из клетки строят цикл по ненулевым компонентам плана перевозок по маршруту столбец строка столбец строка ... строка, который начинается и заканчивается в клетке . Мы не будем доказывать следующие два утверждения:
такой цикл всегда может быть построен;
такой цикл единственный.
Итак, пусть этот цикл имеет вид
Установим новый план перевозок вида
Все остальные компоненты плана перевозок, не входящие в цикл, остаются неизменными.
Наконец, выберем таким образом, чтобы одна из новых компонент плана обратилась в нуль, а все остальные остались положительными. Для этого следует взять в виде ,
где считается . | |
В результате получится новый опорный план. Покажем, что этот новый опорный план дает меньшее значение транспортных расходов, чем старый план.
Так как компоненты плана, не входящие в цикл, не изменяются, то их можно не учитывать. Для ненулевых компонент исходного плана
выполнялось условие | и поэтому |
Для нового плана перевозок мы имеем
В выражении, стоящем в квадратных скобках, большинство слагаемых сокращается и окончательно получаем
так как мы вводим перевозку, для которой . | |
Ну, а дальнейшее очевидно: надо повторять все итерации до тех пор, пока не будет получен оптимальный план. В силу конечности числа вершин допустимой области, это может быть сделано за конечное число шагов.
Закончим наш учебный пример. Одну итерацию мы уже проделали.
Вторая итерация
Этап 1
Определение потенциалов и проверка оптимальности плана. Обычно это совмещается в одной таблице и выглядит в виде таблицы, приведенной на следующей странице.
Сначала в таблицу выписываются , соответствующие ненулевым компонентам плана. Для наглядности их можно как-то помечать, скажем, обводить рамкой (в книге они отмечены жирным шрифтом).
| 2 | 5 | 7 | 4 |
0 | 2 | 5 | 7 | 4 |
-3 | -1 | 2 | 4 | 1 |
-1 | 1 | 4 | 6 | 3 |
Затем определяются потенциалы. Обычно это легко сделать в уме, двигаясь по строкам и столбцам.
Затем оставшиеся клетки заполняются суммами соответствующих
потенциалов, то есть величинами . | |
Наконец, производится сравнение получившейся таблицы с таблицей
величин | и определяются те клетки, где . |
Этап 2
Из тех пар индексов, где , находится та пара, где разность максимальна (в нашем случае это пара i =1, j =3). Строится цикл, определяется и строится новый опорный план.
В нашем случае эти преобразования имеют следующий вид:
| 5.1- | | | | | | 5.1 | |
| 1.9+ | 6.2- | | | | 7 | 1.1 | |
2 | | 0.8 | 6.3 | | 2 | | 0.8 | 6.3 |
В нашем случае , так что новый опорный план нарисован в таблице справа. Значение транспортных расходов уменьшилось на величину
,
то есть на 15.3 единицы.
Следующая итерация дается без пояснений.
Третья итерация
Этап 1
| -1 | 2 | 4 | 1 |
0 | -1 | 2 | 4 | 1 |
0 | -1 | 2 | 4 | 1 |
2 | 1 | 4 | 6 | 3 |
В данном случае для всех клеток таблицы выполняется условие , что говорит о том, что план перевозок, полученный на предыдущей итерации, является оптимальным.
Для этого плана перевозок значение транспортных расходов
.
По сравнению с исходным планом, полученным методом северо-западного угла, транспортные расходы уменьшились на 17.3 единицы, то есть на 21%.
Теперь мы в состоянии доказать одну интересную теорему
Теорема Если все запасы и все потребности целые числа, то оптимальный план перевозок тоже целочисленный.
Доказательство
Действительно, вспомните, как строился исходный опорный план методом северо-западного угла. При этом применялась только одна арифметическая операция операция вычитания. А при вычитании целых чисел всегда получаются только целые числа. Поэтому исходный опорный план целочисленный.
При переходе к новому опорному плану применялись три операции: нахождение минимума из нескольких чисел (при определении ), вычитание и сложение. В применении к целым числам эти операции всегда дают целые числа. Поэтому на любой итерации получающийся план является целочисленным, в том числе и оптимальный план. Теорема доказана.