Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 25

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 25)

Отметим, что если вместо 1 использовать величину 1(1, то некоторые планы перевозок, являющиеся допустимыми в исходной задаче, станут недопустимыми в новой задаче. В то же время выбор величины ~)~ не приведет к дополнительным ограничениям на перевозки, не отраженным в исходной задаче. Поэтому наиболее разумным является выбор величины 1. Рассмотрим следующую задачу о перевозках.

Предположим, что в транспортной задаче, сформулированной в равд. 2.!0.1, каждый источник н каждый сток может использоваться в ка- 10' 148 Глава 2 честве промежуточного пункта. Исходные данные рассматриваемой транспортной задачи таковы, что Е а;=Е Ь;=30. Сле- 2 довательно, 1=30. Задача о перевозках может быть сведена к транспортной задаче со следующими величинами предложения и спроса: 1. и;=а;+30 для исходных источников 1=1, 2; 2. Ь;=30 для исходных источников 1=1, 2; 3. а;=30 для исходных стоков 1'=1, 2, 3; 4.

Ьт=Ь|+30 длЯ исходных стоков 1=1, 2, 3. Транспортные затраты, соответствующие дополнительным маршрутам, предполагаются известными. Матрица условий данной транспортной задачи приводится в табл. 2.34. Таблица 2.34. Матрица условий в задаче о перевозках Исходные источники г Исходные стоки г з Исходные (1 исто ники 1 4О Иоходные стоки зо зо зо 40 42 38 ЗО 36 з п2. ЗАДАЧА 0 НАЗНАЧЕНИЯХ Данная задача заключается в выборе такого распределения ресурсов по некоторым действующим объектам, при котором минимизируются стоимости назначений. Предполагается, что каждый ресурс назначается ровно один раз и каждому объекту приписывается ровно один ресурс. Примеры ресурсов и объектов, а также соответствующие им критерии эффективности, или «стоимости», приводятся в табл. 2.35.

Матрица стоимостей С определяется следующим образом: С=~с2Д, где сн — затраты, связанные с назначением 1-го ресурса на 1-й объект. Индексы 1 и 1 принимают значения 1, 2, ..., лз, где лз — число объектов или ресурсов. Определим хп следующим образом: 1, если 1ий ресурс назначается на 1'-й объект, хм= 0 в противном случае. 149 Детерминированные нотона и сетяс Таблица 2.бб. Применения задачи о назначениях 4 7 ® С вЂ” [бт11 — ® 3 8 б Оз 0 0 1 .Х=[хи3= 1 О 0 0 1 0 2.12.1.

МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ В данной задаче требуется минимизировать целевую функцию, выражающую общую стоимость назначений': Ограничения можно разбить на две группы. Ограничения первой группы необходимы для того, чтобы каждый ресурс использовался ровно один раз. Ограничения второй группы гарантируют, что каждому объекту будет приписан ровно один ресурс. Математическая постановка задачи выглядит следующим образом: минимизиронать Е ~ "~~~ опхы Ф Таким образом, решение задачи может быть записано в виде двумерного массива Х= [хп).

Допустимое решение называется назначением. Для заданного значения и существует т! допустимых решений. Допустимое решение строится путем выбора ровно одного элемента в каждой строке матрицы Х= [хп] и ровно одного элемента в каждом столбце этой матрицы. Элементы сц матрицы С, соответствующие элементам хи=1 матрицы Х, будем помечать кружками.

Эти величины сн выражают затраты, соответствующие допустимому решению Х. Например, при т=З допустимое решение и соответствующие ему затраты могут быть записаны следующим образом: Глава 2 150 при условии, что Х— хм —— 1 для всех /, / хм — — 1 для всех /. х,/>~ О для всех 1 и всех /.

Очевидно, что задача о назначениях является частным слу. чаем транспортной задачи, соответствующим единичным значениям параметров и; и Ьь Поэтому для решения задачи о назначениях можно воспользоваться любым алгоритмом линейного программирования или симплексным алгоритмом для транспортной задачи. Однако метод, описанный в следующем разделе, является более эффективным, поскольку он использует специфику математической постановки данной задачи. 2.12.2. ВЕНГЕРОКИИ АЛГОРИТМ Рассмотрим задачу о назначениях с матрицей стоимостей С=(с//).

Предположим, что каждый элемент /ай строки складывается с действительным числом уь а каждый элемент /-го столбца — с действительным числом б/. В результате такого преобразования матрицы С будет получена новая матрица стоимостей Р, для которой А/=си+у/+6/ или сц=А/ — у; — б/. Из последнего равенства следует, что сцхц=А/хц — у/х//— — 6;хц. Поэтому ХЕ сцхц= ЕЕ А/х/; — ЕЕ у/х// — ЕЕ б;хц= // // с/ с/ = ЕЕ А/хц — Еу/ — Еб/. С / Отсюда следует, что при ограничениях задачи о назначениях минимизация функции ХХс//хц эквивалентна минимизации функции ЕЕА/хц. Основанный на данном результате венгерский алгоритм работает следующим образом: из элементов каждой строки и каждого столбца матрицы стоимостей вычитаются их наименьшие элементы, после чего ведется поиск допустимого решения, единичным элементам которого соответствуют нулевые элементы модифицированной матрицы стоимостей.

Если такое допустимое решение существует, то оно является оптимальным назначением. В противном случае матрица стоимостей модифицируется еще раз с целью получить в ней большее число нулевых элементов. Алгоритм состоит из следующих трех шагов: (1) редукция строк и столбцов; (2) определение назначения; (3) модификация редуцированной матрицы. Ниже дается краткое описание каждого шага.

Детерминированные иотоки е сетях 151 Шаг 1. Редукция строк и столбцов, 1Лель данного шага состоит в получении максимально возможного числа нулевых элементов в матрице стоимостей. Для этого можно из всех элементов каждой строки вычесть минимальный элемент соответствующей строки, а из всех элементов каждого столбца вычесть минимальный элемент соответствующего столбца. Затем можно исходную матрицу стоимостей заменить редуцированной матрицей стоимостей и перейти к поиску назначения. Шаг 2.

Определение назначений. Если после выполнения процедуры редукции в каждой строке и каждом столбце матрицы стоимостей можно выбрать по одному нулевому элементу, так что соответствующее этим элементам решение будет допустимым, то данное назначение будет оптимальным. Если назначения нулевой стоимости для редуцированной матрицы не существует, то данная матрица подлежит дальнейшей модификации (см. шаг. 3). Шаг 3.

Модификация редуцированной матрицы. Если нулевых элементов в матрице стоимостей не достаточно для того, чтобы построить назначение нулевой стоимости, то с помощью следующей простой процедуры можно получить новые нулевые элементы. Определим для редуцированной матрицы стоимостей минимальное множество строк и столбцов, содержащих все нулевые элементы, и найдем минимальный элемент вне данного множества.

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

Для того чтобы матрица не содержала отрицательных элементов, прибавим абсолютную величину наименьшего отрицательного элемента ко всем элементам выделенных строк и столбцов. Отметим, что к элементам, расположенным на пересечении выделенных строк и столбцов, данная величина будет прибавляться дважды. Кроме того, как и раньше, все отрицательные элементы будут преобразованы в нулевые или положительные элементы. В результате выполнения данной процедуры новая редуцированная матрица стала содержать больше нулей, расположенных вне строк и столбцов, соответствующих нулевым элементам текущего неоптимального решения. Основную процедуру венгерского алгоритма, который был только что описан, можно свести к следующим двум наборам процедур.

Процедуры первого набора могут быть использованы для поиска назначения, которому соответствуют нулевые 162 Глава 2 элементы редуцированной матрицы стоимостей. Второй набор процедур может быть использован для модификации редуциро- ванной матрицы стоимостей. 1. Процедуры, используемые для поиска допустимого решения нулевой стоимости (шаг. 2). Выбрать начальное базисное допустимое Шагз решение Проверить, не будет ли улучшена решение, если включить в базис внеба- зисныд маршрут Шаг 2 Стоп Нет Да Определить, какал маршрут оледует исключить из базиса с тем, чтобы маршрут, выб- ранный на шаге 2, включить в базис Шат 3 Скорректировать потоки по другим базисным маршрутам такимобразом,чтобы новое базисное решенивоставалось допустимым Шаг4 Ряс.

2.45. Блок-схема венгерского алгорятма. а. Найти строки, содержащие ровно один невычеркнутый нулевой элемент. В каждой такой строке произвести назначение, соответствующее невычеркнутому нулевому элементу. В каждом столбце, в котором было произведено назначение, вычеркнуть все невычеркнутые ранее нулевые элементы. Строки рассматриваются в порядке возрастания их номеров.

б. Найти столбцы, содержащие ровно один невычеркнутый нулевой элемент. В каждом таком столбце произвести назначение, соответствующее невычеркнутому нулевому элементу. В каждой строке, в которой было произведено назначение, вы- 153 Дегерыини евонные иогоки в сеген черкнуть все невычеркнутые ранее нулевые элементы. Столбцы рассматриваются в порядке возрастания их номеров. в. Выполнять шаги «а» и «б» до тех пор, пока не будет вычеркнуто максимально возможное число нулевых элементов.

Характеристики

Список файлов книги