Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 23
Текст из файла (страница 23)
Смысл такого назначения заключается в том, что оно позволяет избежать наибольшего из минимальных значений штрафа. После «насыщения» выбранного маршрута необходимо выполнить проверку условий, касающихся предложения и спроса соответственно в начальном и конечном узлах этого маршрута. Источник или сток, для которого соответствующее условие выполнено, исключается, и вычисляются новые значения штрафа.
Данная процедура повторяется до тех пор, пока не будут исключены все источники и стоки. Штраф для каждого источника или стока легко вычисляется. Он равен разности между двумя минимальными стоимостями. Если эти стоимости равны между собой, то штраф равен нулю. Кроме того, если на множестве источников и стоков существует несколько максимальных значений минимального штрафа, то можно выбрать произвольный узел, соответствующий одному из этих значений.
Обратимся к рассмотренному выше примеру. Результаты вычислений, выполняемых при определении начального базисного допустимого решения с помощью ПМФ-алгоритма, приведены в табл. 2.25. В скобках записаны значения штрафов для источников и стоков. Максимальное из этих значений помечается звездочкой. В таблице указаны также величины предложения и спроса, вычисляемые на каждой итерации. Таким образом, выполняя вычисления по ПМФ-алгоритму (табл.
2.25), мы получили следующее начальное базисное допустимое решение: Глава 2 Таблица 2.25. Начальное решение, найденное с помощью ПМФ-алгоритма (0) (10) (8) (10) (5) (3) *(24) 150 (8) (13) (0) 350 250 150 250 250 300 200 (1О) (8) (10) (5) (3) (4) 300 350 (2) 250 (3) 150 ' 250 250 300 200 (8) (10) (5) (3) 50 (4) (2) 300 (3) (5) 250 (8) 250 250 300 200 Продолжена (1) (2) (7) (3) 50 250 250 50 300 200 (2) (1 7) (3) 50 300 200 (15) (23) (18) 50 50 100 300 50 50 200 В рассмотренном примере т+л — 1=10. Поэтому решение, полученное с помощью ПМФ, является вырожденным, а решение, полученное с помощью метода «северо-западного угла»,— невырожденным. Шаг 2.
Определение внебазисного маршрута, который должен быть включен в базис. Поскольку в двойственной задаче число переменных равно т+и и мы должны решить т+и — 1 уравнений вида И;+К;+си=0, то можно значение Р~ положить равным нулю и искать значения остальных переменных. После того как переменной Я~ присвоено значение О, могут быть найдены значения переменных Кь соответствующих столбцам матрицы условий с базисными переменными в первой позиции. Затем можно определить строки с базиснымн переменными, расположенными в столбцах, соответствующих только что найденным значениям Кь Для каждой такой строки определяем значение соответствующей ей переменной кь Будем повторять описанную процедуру до тех пор, пока не определятся значения всех двойственных переменных. После того как для каждого внебазисного маршрута будет вычислена сумма Р;+К~+сш для каждого из них проверяется условие оптимальности.
Напомним, что решение является оптимальным, когда все значения %+К;+сн О. Если не все эти значения неотрицательные, то наименьшее отрицательное значение соответствует маршруту с наибольшей возможностью улучшить решение и данный маршрут должен быть включен в базис. Отметим, что, когда число базисных маршрутов меньше т+и — 1, значения Р~ и К~ не могут быть найдены и поэтому для внебазисных маршрутов нельзя оценить их возможность улучшить решение. Наиболее простой путь определения значений двойственных переменных в данном случае заключается в следующем.
Нужно приписать бесконечно малые потоки стольким маршрутам, сколько необходимо для того, чтобы построить невырожденное решение. Эти бесконечно малые потоки должны быть приписаны независимым маршрутам. Независимым маршрутом называется такой маршрут, поток по которому не может быть представлен линейной комбинацией базисных потоков. Каждому маршруту соответствует некоторая клетка таблицы размером тХп, используемой для записи входных данных и решений. Независимому маршруту соответствует клетка, для которой не существует контура, в одном из углов которого расположена данная клетка, а в остальных углах— клетки с положительными потоками.
Для иллюстрации шага 2 рассмотрим начальное базисное допустимое решение, полученное с помощью ПМФ-алгоритма. Как отмечалось выше, данное решение является вырожденным, поскольку число базисных маршрутов меньше и+я — 1=10. 139 Детерминированные потехи в сетях Таблица 2.2б. Правильное расположение в-клеткн 150 200 300 350 250 200 100 150 250 250 300 В данном случае необходимо ввести один бесконечно малый поток, величину которого мы обозначим через е (табл. 2.26). Читателю предлагается проверить, что для данной клетки нельзя построить контур, о котором говорилось выше.
Отметим, что расположение в-клетки в табл. 2.27 неправильное, поскольку маршруты, соответствующие клеткам, расположенным в углах обозначенного контура, не являются независимыми. Таблица 2.27. Неправильное расположение в-клетки 200 300 350 100 150 250 250 300 200 Проверим, является ли оптимальным решение, полученное с помощью ПМФ-алгоритма. В табл.
2.28 символом ° обозначены базисные потоки (включая в-поток). В нижнем левом углу каждой клетки, соответствующей внебазисному маршруту, указано значение 15';+К +си. Значения Р; указаны слева от каждой строки, а значения Кг — над каждым столбцом. Поскольку среди отрицательных величин )(с+Кг+сц наименьшей является величина Ле+Кв+сев= — 36 (т. е.
маршрут (4, 6) имеет максимальную возможность улучшить решение), то в ре- Глава 2 зультате выполнения шага 2 внебазисный маршрут, соответствующий клетке (4,5), будет включен в базис. Шаг 3. Нахождение маршрута, который должен быть исключен из базиса. Определив маршрут, который следует включить в базис (т. е. маршрут, поток по которому возрос с нулевого до некоторого положительного значения), можно построить схему перестройки базисных маршрутов. Данная схема перестройки называется ступенчатым путем. Таблица 2.28.
Возможности маршрутов улучшить решение К = — б з К =-9 ! Кл = — 17 Кл =-47 Кв = — !2 К, = — !9 л,=о Лз =17 Яз 23 Яз =-23 В рассматриваемом примере было показано, что маршрут, соответствующий элементу (4, 5), следует включить в базис. При возрастании потока по данному маршруту необходимо увеличить или уменьшить потоки по некоторым другим маршрутам, с тем чтобы не нарушались исходные ограничения на спрос и предложение и новое решение было бы допустимым. Маршрут, поток по которому возрос, будем называть получаю- а(им, а маршрут, поток по которому уменьшился, — отдаю- и(им.
Очевидно, что маршрут, который исключается из базиса, должен быть отдающим маршрутом, а поток по нему должен быть наименьшим среди всех текущих базисных потоков. В результате выполнения данной процедуры одна или более базисных переменных станут равными нулю. В последнем случае решение становится вырожденным. Для нахождения получающих и отдающих маршрутов мы строим ступенчатый путь, который имеет форму контура, состоящего из вертикальных и горизонтальных отрезков, соответствующих выполняемым заменам. В одном из углов данного контура расположена клетка, соответствующая маршруту, включенному в базис, а в остальных углах — клетки, соответствующие базисным маршрутам. Поскольку включенный в базис маршрут является получающим, то соседние с ним маршруты, относящиеся к построенному контуру, могут быть поме- 141 Детерминированные потони в сетлл Таблица 2.29.
Ступенчатый путь 3 4 5 6 1 2 + Попучеюе1ий — Отдееиций чены как отдающие. Остальные маршруты, относящиеся к контуру, попеременно помечаются как получающие (+) и отдающие ( — ). В табл. 2.29 показан ступенчатый путь для рассматриваемого примера и указано, как следует изменить потоки, чтобы при включении маршрута, соответствующего клетке (4, 5), в базис решение оставалось допустимым. Отдающим маршрутам соответствуют клетки (3, 5) и (4, 4), а потоки по этим маршрутам равны 50 и 200 соответственно. Поэтому маршрут, соответствующий клетке (3, 5), следует исключить из базиса.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
