Как известно, транспортная задача бывает открытая и закрытая. Открытой называется задача, в которой баланс поставщиков и потребителей не равны между собой. Это явление обычно и встречается сплошь и рядом. Способ борьбы с этим единственен и прост: добавляем фиктивного поставщика, если баланс поставщиков меньше, чем баланс потребителей, и наоборот.
К сожалению, известно и то, что транспортная задача является вырожденной и невырожденной. Вырожденной является такая задача, в которой количество клеток в плане меньше m+n-1, где m - количество поставщиков, n – количество потребителей. Понятно, что это явление тоже часто встречается. Способ борьбы с ним у каждого свой: от случайно размещаемых нулевых клеток в плане до перебора по очереди всех пустых клеток. Ни то ни другое не дает гарантий в том, что вновь размещенная клетка не образует цикл с имеющимися клетками.
С первого взгляда кажется, что вырожденность задачи – явление случайное и никаким законам не подчиняется. Даже более того, базовые планы, созданные с помощью различных методов, например, Северо-западного угла и Минимальных значений, дают вырожденный и невырожденный планы для одной и той же задачи. Это, естественно, порождает мысли: скрыта вырожденность в задаче или метод создания плана создает ее. Но когда в другой задаче не срабатывает, наоборот, тот метод, который только что создал нормальный невырожденный план, остается одна мысль: вырожденность – явление потустороннее и не зависит от задачи и применяемого метода создания плана.
И все-таки существует способ не только избавиться от вырожденности, но и «уничтожить» ее насовсем. Каким образом? Какова природа вырожденности и откуда она возникает? Рассмотрим вопрос в таком порядке: природа вырожденности; откуда (и почему) возникает вырожденность; как с ней бороться.
Итак, природа вырожденности. Вырожденность – когда не хватает клеток-уравнений для определения потенциалов в плане. Это, когда необходимо для нормальной работы m+n-1 уравнение, а их, к сожалению, m+n-2. И еще хуже, если их получается только m, как в этой задаче (см. таблица 1) при использовании метода Северо-западного угла.
Таблица 1
| Получатель> Источник v |
10 |
20 |
30 |
|
10 |
5 |
4 |
1 |
|
20 |
4 |
3 |
2 |
|
30 |
1 |
2 |
3 |
Как видим, в таблице (см. таблица 2) заполнены только 3 клетки при необходимом количестве 5. Ну, очень вырожденный план. Какие 2 из 4-х пустых клеток ввести в план? Кстати, оценка этого плана равна 200, оценка оптимального плана, который получится при решении задачи, будет равна 100. Такие задачи можно придумать для любого метода составления базового плана, даже в этой задаче, где все другие методы сразу дают оптимальный план, у них в плане участвуют только по 4 клетки.
Таблица 2
| 10 | ||
| 20 | ||
| 30 |
Оптимальный план данной задачи имеет следующий вид (см. таблица 3) и в нем, как можно заметить, уже присутствуют m+n-1 клеток, из которых одна оказалась нулевой. Этот план у нас получится в процессе пошагового решения задачи.
Таблица 3
| 10 | ||
| 0 | 20 | |
| 10 | 20 |
Далее, откуда возникает вырожденность. Рассмотрим по шагам составление базового плана нашей задачи. Распределяя первую строку, получаем клетку (1,1), обнуляем поставщика и получателя. То есть, добавляя одну клетку, мы избавились (к сожалению) от двух переменных сразу. Со второй строкой получается аналогичная картина. И к окончанию создания плана мы имеем «недостачу» трех
Как бороться с вырожденностью. Многие разработчики просто добавляют нулевые клетки, проверяют получившуюся конструкцию на циклы и, если таковые появляются, переставляют клетки случайным образом в другие места. В нашей задаче цикл появляется при включении в план клеток (1,2) и (2,1) (см. таблица 4).
Таблица 4
| 10 | 0 | |
| 0 | 20 | |
| 30 |
Таким образом, перебрав несколько (а в большой матрице много) вариантов, приходим к следующему плану (см. таблица 5).
Таблица 5
| 10 | 0 | |
| 20 | 0 | |
| 30 |
В дальнейшем будет показано и обосновано, как можно создать план, обладающий двумя очень важными достоинствами: количество клеток равно точно m+n-1, полное отсутствие циклов. Для этого необходимо в случае, когда обнуляются поставщик и получатель, добавлять клетку с нулевым значением в ЛЮБОЙ незанятый столбец (такая операция некоторыми, бывает, проводится интуитивно). Если незанятых столбцов нет, то никаких действий не производится. Просто это означает, что все столбцы обнулены, и план составлен. Естественно, возникают два вопроса: об образовании циклов с участием этой нулевой клетки и о вырожденности полученного плана. Для решения первого вопроса докажем теорему «О невозможном внедренном цикле». После этого посчитаем количество получившихся клеток и сравним с m+n-1.
Теорема: О невозможном внедренном цикле
Определения:
Занятый столбец – столбец, в котором находится клетка плана и значение получателя равно 0.
Незанятый столбец - столбец, в котором находится клетка плана и значение получателя не равно 0, либо в столбце нет ни одной клетки плана.
П-конструкция – вертикальный отрезок в столбце k (туловище) с концами на строках i и j и двумя горизонтальными «хвостами», направленными в одну сторону, например, вправо. Любые другие ориентации сводятся к данной путем поворотов или отражений.
Формулировка: В том случае, когда при создании плана одновременно обнуляются поставщик и получатель, и нулевая клетка помещается в любой незанятый столбец, цикл не образуется.
Доказательство: любой цикл содержит в себе П-образную конструкцию, обозначены номерами от 1 до 4 (см. рисунок 1).
Рисунок 1. Различные виды циклов.
Эту конструкцию в нашей задаче можно представить так: (1,1), (1,2), (2,2), (2,1) или (2,1), (1,1), (1,2), (2,2) (см. таблица 6). Она появляется, когда нулевая клетка помещается в (1,1) при наличии занятых клеток (1,2), (2,2), (2,1).
Таблица 6
| 0 | 10 | |
| 10 | 10 | |
Если мы докажем, что такая конструкция не может появиться в нашем случае, это и будет означать, что циклы в созданном по правилам плане невозможны.
Лемма: В правильно составляемом плане П-конструкции не появляются.
Доказательство: Проверим варианты ситуаций, когда данная конструкция может образоваться. Во всех случаях обрабатывается строка j.
1. Строка i имеет одну занятую клетку, и обработка ее закончена.
2. Строка i имеет одну занятую клетку, и обработка ее не закончена.
3. Строка i имеет более одной занятой клетки.
Чтобы не запутывать доказательство, условно примем, что в других строках нет ни одной занятой клетки. В противном случае в качестве строки i необходимо проверить все строки по очереди.
В первом случае в строке j в том столбце, где строка i имеет занятую клетку, можно разместить как клетку плана, так и нулевую клетку, поскольку в строке i нет «хвоста», как одного из элементов П-конструкции. В дальнейшем рассмотрении будем рассматривать случай 3 для столбца, в который мы поместили две клетки.
Во втором случае в строке j в том же столбце нельзя ничего разместить, поскольку столбец уже занят (вспомним, как появляются клетки плана). Так что основы для П-конструкции нет.
Значит, «краеугольным» в доказательстве является случай 3. Очевидно, что все столбцы, в которых расположены занятые клетки строки i, заняты, кроме одного, в котором строка обнулилась (Естественно, два и более незанятых столбцов при наличии клеток плана означают, что строка i обнулялась несколько раз, чего быть не может). Но и он может быть занят, если обнулился вместе со строкой. Если все столбцы заняты, то как и в случае 2, основы для П-конструкции нет.
Остается одна возможность – единственный незанятый столбец. Помещаем в него клетку. Если строка j обнулилась, а столбец - нет, то хвост из данной клетки не появится. Если и столбец обнулился, то помещаем нулевую клетку в свободный столбец как часть плана. Эта клетка не замкнет цикл, поскольку из строки i не появится новых клеток плана (все столбцы обнулены), а уже имеющиеся, вместе с идущими из них путями, не касаются незанятого столбца.
Таким образом, П-конструкции в правильно составляемом плане не появляются. И, следовательно, циклы не образуются. Что и требовалось доказать.
Вернемся к вопросу о вырожденности полученного плана. Вспомним, что каждая клетка плана есть по сути одно уравнение в методе потенциалов, связывающее две переменных v(i) и u(j). При расчетах одна переменная является определяемой, вторая определенной. Нам надо сосчитать, сколько определяемых переменных имеется во всех клетках-уравнениях.
Пусть в строке i находится m(i) клеток, не считая нулевой. Посмотрим, что определяют эти уравнения. Если строка i в процессе занесения в план клетки (i, j) обнуляется, а столбец j – нет, то этим уравнением определяется переменная v(i) и (m(i) – 1) переменных u, кроме, естественно, переменной u(j), которая определится, когда обнулится столбец j. Если столбец обнуляется вместе со строкой, то определяется m(i) переменных u, а добавление нулевой ячейки определяется переменная v(i) (не забываем, что в последней заполненной строке нет нулевой клетки). Теперь посчитаем уравнения и переменные. Поскольку все столбцы в процессе составления плана обнулены, то сумма m(i) равна общему количеству столбцов, то есть m. Поскольку при обнулении каждой строки (кроме последней) определяется одна переменная v(i), то при обнулении всех строк мы определили n‑1 переменных. Общее количество определенных переменных составляет m + (n‑1). Что и требовалось!
ВЫВОД: Применяя правило «Если при создании плана одновременно обнуляются поставщик и получатель, то нулевая клетка плана помещается в любой незанятый столбец» мы получаем невырожденный и незацикленный план, и без всяких ухищрений.
В завершение приводим базовый план, составленный с учетом правила, итерации и оптимальный план рассматриваемой задачи с разностями потенциалов и ценой (оценкой) плана.
Таблица 7
| План | Разности | Цена | ||||||
| 10 | 0 | 0 | 0 | -2 | 200 | |||
| 20 | 0 | 0 | 0 | 0 | ||||
| 20 | -4 | -2 | 0 | |||||
| План | Разности | Цена | ||||||
| 10 | 4 | 0 | -2 | 160 | ||||
| 10 | 10 | 4 | 0 | 0 | ||||
| 10 | 20 | 0 | -2 | 0 | ||||
| План | Разности | Цена | ||||||
| 0 | 10 | 6 | 0 | 0 | 140 | |||
| 20 | 6 | 0 | 2 | |||||
| 10 | 20 | 0 | -4 | 0 | ||||
| План | Разности | Цена | ||||||
| 10 | 6 | 4 | 0 | 140 | ||||
| 20 | 2 | 0 | -2 | |||||
| 10 | 0 | 20 | 6 | 0 | 0 | |||
| План | Разности | Цена | ||||||
| 10 | 4 | 2 | 0 | 100 | ||||
| 0 | 20 | 2 | 0 | 0 | ||||
| 10 | 20 | 0 | 0 | 2 | ||||
* * *
Дополнение к вышесказанному: При составлении плана некоторые строки и столбцы имеют по несколько клеток. В процессе расчета очередной итерации по методу потенциалов требуется найти цикл, содержащий вновь введенную в план клетку. Для этого достаточно стереть (временно – для данной итерации) клетки, которые находятся в строке или столбце в единственном числе. Этот факт означает, что войдя в клетку, выйти из нее невозможно. Проделать такую операцию необходимо рекурсивно до тех пор, пока одиночных клеток не останется. Не трудно понять, что оставшиеся клетки и будут тем самым циклом. И опять без всяких ухищрений (Не забывайте после пересчета вернуть все временно удаленные клетки на место).
Устранение вырожденности в имеющемся плане
Если базовый план уже составлен и обнаружено, что он вырожденный, то предлагается формализованное правило для исправления таких планов.
Он состоит в определении несвязных групп клеток плана (уравнений вычислений потенциалов). Для этого берется клетка с минимальным номером строки и столбца, не вошедшая ни в одну группу. Образуется группа с очередным номером, если группы еще не образовывались, то номер будет равен 1(единице). Остальные клетки, содержащиеся в данной строке, помечаются тем же номером (в правом нижнем углу). Клетки, содержащиеся в данном столбце помечаются в левом нижнем углу. Если оказалась помеченной клетка плана, то она берется за основу для новых пометок, до тех пор пока не будут помечены все связанные клетки. Если оказывается, что не все клетки плана помечены, то весь процесс повторяется. В конце работы подчитывается число групп. Если оно равно 1, то все клетки плана входят в одну группу, это означает, что план невырожденный.
Действительно: одна клетка базового плана, если она первая в группе, отмечает одну строку плюс один столбец, не первая- одну строку или один столбец. Таким образом K клеток группы отмечают K +1 строк или столбцов. Поскольку всего N+ M строк или столбцов, N- количество строк, M -количество столбцов. Для одной группы получаем:
K +1= N+ M или K = N+ M-1
что и требовалось доказать.
Предположим, что в конце процесса получилось L групп. В каждой группе количество строк и столбцов на единицу больше количества клеток плана. Таким образом для всех групп получаем, что количество отмеченных строк или столбцов на L больше количества клеток плана, что означает:
K + L = N+ M или K = N+ M- L
То есть для получения невырожденного плана нужно добавить L -1 клетку в план. Определим места для этих клеток. Если новая клетка плана попадет в пустую клетку с двумя одинаковыми номерами, то она замкнет цикл, что для плана нежелательно. При распределение новых клеток плана таким образом, чтобы один из номеров был равен 1, не допуская повторов номеров, мы связываем разные группы и получаем L -1 новую клетку. Утверждение таким образом доказано.
Результат вышеописанного алгоритма приведен в таблице
|
С 1 1 |
С 1 1 |
Н 2 1 |
Н 3 1 |
3 1 |
| 1 2 |
1 2 |
С 2 2 |
3 2 |
3 2 |
|
П 1 1 |
С 1 1 |
2 1 |
3 1 |
3 1 |
|
1 3 |
1 3 |
2 3 |
С 3 3 |
3 3 |
|
1 3 |
1 3 |
2 3 |
С 3 3 |
С 3 3 |
С- существующие клетки плана (7)
Н- новые (или добавляемые) клетки плана (2)
П- плохие клетки (замыкающие цикл)
K=7 (количество клеток существующего плана);
L=3 (количество образовавшихся групп);
N=5 (количество строк);
M=5 (количество столбцов).
Вывод: необходимо определить группы связных клеток, если эта группа не одна, то новые клетки плана ставить в местах связанных с разными группами.
Количество просмотров публикации: Please wait