Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 26
Текст из файла (страница 26)
Если построенное назначение полное, то оно является оптимальным. Если некоторые нули остались невычеркнутымн, то можно попытаться найти полное назначение (например, методом проб и ошибок) среди нескольких оптимальных вариантов. Если нельзя найти ни одного полного назначения, то необходима дальнейшая модификация матрицы. 2. Процедуры, используемые для модификации редуцированной матрицы (шаг 3).
а. Вычислить число нулей в каждой невычеркнутой строке и каждом невычеркнутом столбце. б. Вычеркнуть строку или столбец с максимальным числом нулей. В случае равенства числа нулей в нескольких строках и столбцах вычеркнуть любую нз этих строк (или любой из этих столбцов). Строки вычеркиваются горизонтальными линиями, а столбцы в вертикальными линиями.
в. Выполнять шаги «а» н «б» до тех пор, пока не будут вычеркнуты все нули. г. Из всех невычеркнутых элементов вычесть минимальный невычеркнутый элемент н прибавить его к каждому элементу, расположенному на пересечении двух линий. На рис. 2.45 изображена блок-схема венгерского алгоритма. На шаге 3 используются описанные выше процедуры.
Отметим, что в данных процедурах явно не используются отрицательные элементы, о которых говорилось при обосновании алгоритма. 2.12.3. РЕШЕНИЕ ПРИМЕРА С ПОМОЩЬЮ ВЕНГЕРСКОГО АЛГОРИТМА Покажем работу венгерского алгоритма на примере задачи о назначениях со следующей матрицей стоимостей: С = (о„) = 1. Редукция строк и столбцов. а. Значения минимальных элементов строк 1, 2, 3 н 4 рав- ны 2, 4, 11 н 4 соответственно. Вычитая из элементов каждой Глава л строки соответствующее минимальное значение, получим следующую матрицу: б.
Значения минимальных элементов столбцов 1, 2, 3 и 4 равны О, О, 5 н О соответственно. Вычитая из элементов каждого столбца соответствующее минимальное значение, получим следующую матрицу: 2. Поиск допустимого решения, для которого все назначения имеют нулевую стоимость. а. Строки 1, 2 и 4 содержат по одному невычеркнутому нулю. Рассматривая эти строки в порядке возрастания их номеров, произведем вначале назначение, соответствующее элементу (1, 1), и вычеркнем нулевой элемент (4, 1). Затем произве' дем назначение, соответствующее элементу (2, 2). Строка 4 не может быть использована, поскольку нулевой элемент (4, 1) был вычеркнут после того, как мы произвели назначение, соответствующее элементу (1, 1).
б. Столбцы 3 н 4 содержат по одному невычеркнутому нулю. Рассматривая эти столбцы в порядке возрастания нх номеров, мы можем произвести третье назначение, соответствующее элементу (3, 3). В столбце 4 нн одно назначение невозможно, так как расположенные в нем нулевые элементы были вычеркнуты после того, как мы произвели назначение, соответствующее элементу (3, 3). После выполнения данного шага матрица стоимостей имеет следующий вид: Таким образом, ни одно полное назначение не может быть получено, и необходимо провести дальнейшую модификацию редуцированной матрицы стоимостей. Детерминированные нотони в сетях 3.
Модификация редуцированной матрицы стоимостей. а. Число нулей в строках 1, 2, 3 и 4 матрицы, полученной на предыдущем шаге, равно 1, 1, 2 и 1 соответственно. Для столбцов соответствующие величины равны 2, 1, 1 и 1. б. Максимальное число нулей, по два, содержат строка 3 и столбец 1. Выбираем строку 3 и вычеркиваем все ее элементы горизонтальной линией. в. Число невычеркнутых нулей в строках 1, 2 и 4 равно 1, 1 и 1 соответственно. Для столбцов соответствующие значения равны 2, 1, О и О. Поэтому мы должны выбрать столбец 1 и вычеркнуть его вертикальной линией. После этого останется только один невычеркнутый нуль — элемент (2, 2).
Поэтому можно вычеркнуть либо строку 2, либо столбец 2. Вычеркивая строку 2 горизонтальной линией, получаем следующую матрицу: г. Значение минимального невычеркнутого элемента равно 2. Вычитая его из всех невычеркнутых элементов и складывая его со всеми элементами, расположенными на пересечении двух линий, получаем новую редуцированную матрицу стоимостей: Выполняя вновь процедуру построения допустимого решения нулевой стоимости, получаем следующее оптимальное решение: Результаты вычислений, проведенных в данном разделе, отражены на рис. 2.46. 156 Глава 2 Пример На Ми Ос Шаг в .г= 26 Рис.
2.46. Шаги вычислений в венгерском алгоритме. Детерминированные потоки в сетпх 2.12.4. ЗАМЕЧАНИЯ 1. Число допустимых назначений равно пт1, где пт — число строк или столбцов матрицы стоимостей (матрица является квадратной). 2. Для любого недопустимого назначения соответствующая ему стоимость полагается равной М (достаточно большому числу в минимизационных задачах). 3. Если исходная матрица не является квадратной, то следует ввести нужное количество строк или столбцов и их элементам присвоить значения, определяемые условиями решаемой задачи.
4. Если исходная задача является задачей максимизации, то все элементы матрицы стоимостей следует умножить на — 1 и сложить их с достаточно большим числом так, чтобы матрица не содержала бы отрицательных элементов. Затем задачу следует решать как задачу минимизации. б. Если число линий, необходимое для того чтобы вычеркнуть нулевые элементы, равно числу строк или столбцов (квадратной матрицы), то существует назначение нулевой стоимости. 2.12.5.
ЗАДАЧА РАЗМЕЩЕНИЯ ПРОИЗВОДСТВА Компания разрабатывает план выпуска трех новых видов продукции. Предположим, что компания владеет пятью предприятиями и что на трех из них должны производиться новые виды продукции — по одному виду на одно предприятие. Ниже указаны издержки производства и сбыта единицы продукции, соответствующие каждой паре вид продукции — предприятие. 1. Издержки производства единицы продукции (долл.): Предприятие 1 2 3 4 5 Вид продукции 3 2.
Издержки сбыта единицы продукции (долл.): Предприятие 1 2 3 4 5 Вид продукции 2 3 Гааеа Я Плановый объем годового производства, который позволил бы удовлетворить спрос, и плановая стоимость единицы продукции каждого вида следующие: Решение. Общие издержки на единицу продукции складываются из издержек производства и издержек сбыта единицы продукции. Поскольку продажная цена единицы каждого вида продукции известна, то для каждой пары вид продукции— предприятие можно вычислить прибыль на единицу продукции: Предприятие 1 2 3 4 5 Вид 1 продукции 3 Умножая прибыль, приходящуюся на единицу продукции, иа годовой объем сбыта, можно получить общую годовую прибыль, соответствующую каждой паре вид продукции — предприятие.
Данные величины (в тыс долл.) приведены в следующей таблице: Предприятие 3 4 5 1 2 Вид 1 продукции 3 Если прибыль рассматривать как отрицательные затраты и ввести два вида фиктивной продукции (4 и б), которой соответ- 159 Детерминированные потони в сетях ствует нулевая прибыль, то исходная задача максимизации может быть сведена к минимизационной задачи о назначениях. Для того чтобы матрица стоимостей не содержала отрицательных элементов, сложим каждый элемент матрицы с числом 5760.
В результате будет получена следующая матрица: Предприятие 1 2 3 4 5 1 В,д 2 продукции 3 4 5 Оптимальное решение данной задачи следующее: производство первого вида продукции назначается предприятию 4, второго вида — предприятию 1, третьего вида — предприятию 3, четвертого вида — предприятию 2 и пятого вида — предприятию 5. Очевидно, что два последних назначения являются фиктивными. Суммарная годовая прибыль, соответствующая данному решению, равна 7892000 долл. Предприятие 1 2 3 4 5 1 Вид 2 продукции 5 Это решение получается так: модифицируем редуцированную матрицу, вычеркивая в ней третий и четвертый столбцы и четвертую и пятую строки.
2.13. ЗАДАЧА О НАЗНАЧЕНИЯХ И ЗАДАЧА КОММИВОЯЖЕРА В равд. 2.9 был описан алгоритм решения задачи коммивояжера. Алгоритм решения задачи о назначениях, описанный в равд. 2.12, также может быть использован в качестве составной части специальной программы решения задачи коммивояжера. Глава 2 Очевидно, что в общем случае оптимальное решение (решение минимальной стоимости) (пХп)-задачи о назначениях может не быть решением соответствующей (п,к',п)-задачи коммивояжера. Однако алгоритм решения задачи о назначениях может быть соответствующим образом модифицирован и использован для решения более сложной задачи. Пусть Р— матрица расстояний (стоимостей) размером пХп, элементы с(у которой представляют собой штраф за переезд из города, илн пункта, 1 в другой город, или пункт, 1, где 2=1,2, ..., п,)'=1,2, ..., п. Преобразуем далее матрицу Р, полагая с(ц — — 0 при !)1 и оставляя без изменения элементы А; (которые могут быть положительными, отрицательными или равными нулю) при !(1 (табл.
2.36). Данная матрица расстояний (стоимостей) называется верхней треугольной матрицей. Будем обозначать ее через Р. Таблица 2.ЕЕ. Верхняя треугольная матрица мзщ 3 Предлагаемый алгоритм решения задачи коммивояжера, разработанный Лоулером [40], состоит в следующем. 1Иаг !. Исключить первый столбец и п-ю строку из матрицы Р и решить соответствующую (п — 1)Х(п — 1)-задачу о назначениях. Замечание, В результате выполнения шага 1 будет построен путь нз узла ! в узел и. Возможно, будут построены также и другие неиврвсвкаляцився замкнутые подиути. Эти подпути содержат узлы, не принадлежащие главному пути из узла ! в узел и. Если в результате работы алгоритма решения задачи о назначениих будет построен путь или цепь, не содержащий циклов н проходящий через каждый узел ровно один раз, то решение ясходной Детврминированныв потоки в сетях задачи будет найдено.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
