XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 56
Текст из файла (страница 56)
Вычитаем эти значения иэ соответствующих столбцов и приходим к матрице Шаг 2. Находим минимальные элементы в строках матрицы С'. В первой строке п1 = с~~1 — О, во второй — 41з = с'з — — О, в третьей — 11з = с~за О, в четвертой — 114 = с~4з — — 1. Вычитая зти значения из соответствующих строк, получаем матрицу Шаг 3. Отмечаем систему независимых нулей: 399 пРилОжение ь ВенГеРский метОд 398 Теперь перейдем к описанию итерации алгоритма венгерского метода решения задачи о назначениях.
Пусть проведено т итераций (т > 0), в результате которых получена эквивалентная матрица стоимости С Ш аг 1. В матрице С подсчитываем число элементов в системе независимых нулей, которое обозначим через й. Если й = п, то переходим к шагу 2. Если й < и, то переходим к шагу 3. Шаг 2.
В соответствии с системой и независимых нулей эквивалентной матрицы стоимости С" = С в матрице переменных модели Х расставляем и единиц, а остальные ее элементы заменяем нулями. Решение завершено. Ш аг 3. Столбцы матрицы С, содержащие 0*, выделяем знаком „+", их элементы называют выделеккььма (остальные элементы матрицы называют кевыделеккыляи). Переходим к шагу 4.
Ш аг 4. Если среди невыделенных элементов матрицы С есть хотя бы один нуль, то переходим к шагу 5. В противном случае переходим к шагу 9. Ш а г 5. Если строка, содержащая невыделенный нуль, содержит также и 0*, то переходим к шагу 6. В противном случае переходим к шагу 7. Шаг 6. Найденный невыделенный нуль обозначаем через 0~, содержащую его строку отмечаем знаком „+" и все ее элементы называем выделенными. Снимаем знак „+" со столбца, в котором расположен 0" из выделенной строки, и переходим к шагу 4. Ш аг 7. Найденный невыделенный нуль обозначаем через 0' и, начиная с него, строим так называемую й-ч4епочку по следующему правилу: исходный 0', далее 0*, расположенный с ним в одном столбце (если такой найдется); затем 0', расположенный в одной строке с предшествующим 0*; далее О, расположенный в одном столбце с предшествующим 0' (если такой найдется) и т.д.
Переходим к шагу 8. Замечание П1.1. Построение Ь-цепочки осуществляется однозначно. Действительно, в каждом столбце не может быть' более одного 0*, а в каждой строке не может быть более одного 0' (после того как в строке один нуль выделен штрихом, зту строку выделяют и никакие другие ее нули не могут быть выделены). Замечание П1.2.
Ь-цепочка всегда начинается с 0' и заканчивается 0'. Принципиальная схема построения Ь-цепочки представлена на рис. П1.1. Рис. П1.1 Действительно, пусть С = (с; ) Е М (я1) и существует Ь-цепочка вида А=~с с с ... с с. .) которзл не может быть продолжена, причем с,„„отмечен как 0', с;„, „отмечен как 0*. В этом случае в матрице С столбец с номером 11 не выделен знаком „+", так как в этом столбце есть элемент с типа 0'. В то же время этот столбец содержит 0* чм (так отмечен элемент с. ). Следовательно, знак выделения ч+~1ь столбца с номером 11 был снят и строка с номером 11+~ содержит 0', так как на шаге 6 она была выделена.
Таким образом, Ь-цепочка может быть продолжена, что противоречит сделанному предположению. Замечание П1.3. Число элементов в Ь-цепочке является нечетным. При этом Ь-цепочка может состоять из одного элемента, если в одном столбце с рассматриваемым 0' нет 0'. Ш аг 8. В А-цепочке все 0' заменяем нулями, а все 0'— символами 0*, в результате чего в эквивалентной матрице стоимости С получаем новую систему независимых нулей, 401 + + 0' 2 4 0' 5 0" 3 6 3 1 0' 4 6 0 5 6 + + + 0* 2 4 0 5 0" 3 6 3 1 0* 4 6 0 5 6 + + 0* 5 7 0' 2 0* 3 3 0 1 0* 1 3 0 5 3 Переходим к шагу 4. Переходим к шагу 5.
400 пРилОжение ь ВенГеРский метОд число элементов которой на единицу больше числа элементов в предыдущей системе независимых нулей 1согласно замечаниям П1.2 и П1.3, в А-цепочке число элементов 0' всегда на единицу больше числа элементов 0*). Вне 5-цепочки все 0' заменяем нулями и снимаем все выделения строк и столбцов матрицы С . Переходим к шагу 1. Ш а г 9. Среди невыделенных элементов матрицы С находим минимальный элемент Ь 1Ь > 0 в силу неотрицательности элементов эквивалентной матрицы стоимости С и отсутствия невыделенных нулей).
Значение Ь вычитаем из элементов невыделенных строк и прибавляем к элементам выделенных столбцов. Вновь полученную эквивалентную матрицу стоимости с неотрицательными элементами, в которой по меньшей мере один из невыделенных элементов является нулем, обозначаем через С и переходим к шагу 5. Пример П1.2. Вернемся к задаче о назначениях, для которой в примере П1.1 выполнен подготовительный этап венгерского метода и получена эквивалентная матрица стоимости Се. Рассмотрим итерационный процесс венгерского метода решения этой задачи. Первая итерация Шаг 1. Число Ь элементов в системе независимых нулей матрицы Се равно трем 1см. пример П1.1).
А так как п = 4 и й < п, переходим к шагу 3. Ш аг 3. Выделяем столбцы матрицы Со, содержащие 0'. Шаг 4. Один из элементов невыделенного четвертого столбца матрицы Се является нулевым 1в первой строке). Переходим к шагу 5. Шаг 5. В первой строке матрицы Со наряду с невыделенным нулем 1с~4 — — 0) есть элемент се„, выделенный как 0*. Переходим к шагу 6. Шаг 6. Найденный невыделенный нуль обозначаем через 0' и выделяем содержащую его первую строку. Снимаем знак выделения с первого столбца, в котором расположен 0* из первой строки: Переходим к шагу 4. Шаг 4.
Среди невыделенных элементов матрицы Со нет нулей. Переходим к шагу 9. Шаг 9. Среди невыделенных элементов матрицы Се находим минимальный элемент Ь = ш1п15, 3, 6, 6, 4, 61 = 3. Значение Ь = 3 вычитаем из элементов невыделенных строк с номерами 2, 3, 4 и прибавляем к элементам выделенных столбцов с номерами 2, 3. Вновь полученную эквивалентную матрицу стоимости обозначаем через Со.' ПРИЛОЖЕНИЕ ь ВЕНГЕРСКИЙ МЕТОД 402 403 Шаг ° 5.
В третьей строке, содержащей невыделенный нуль (стзт — — 0), есть и выделенный нуль (стзз — — О'). Переходим к шагу 6. Ш а г 6. Найденный невыделенный нуль обозначаем через 0', содержащую его третью строку выделяем. Снимаем знак выделения с третьего столбца, в котором расположен 0' из третьей строки: + + 0* 5 7 0' 2 0" 3 3 + 0' 1 0' 1 3 0 5 3 Переходим к шагу 4.
Шаг 4. Среди невыделенных элементов матрицы Со нет нулей. Переходим к шагу 9. Шаг 9, Среди невыделенных элементов матрицы Со находим минимальный элемент 6 =ш1п(2, 3, 3, 3, 5, 3) = 2. Значение 1О = 2 вычитаем из элементов невыделенных строк с номерами 2 и 4 и прибавляем к элементам выделенного второго столбца. Вновь полученную эквивалентную матрицу стоимости обозначаем через Со..
+ + 0' 7 7 0' 0 0' 1 1 + 0 3 0 1 1 0 3 1 Переходим к шагу 5. Шаг 5. Во второй строке, содержащей невыделенный нУль (сз~4 — — 0), есть выДеленный нУль (сиз — — 0'). ПеРехоДвм к шагу 6. Ш а г 6. Найденный невыделенный нуль обозначаем через О', содержащую его вторую строку выделяем. Снимаем знак выделения со второго столбца, в котором расположен 0" из второй строки: + 0" 7 7 0' С = + 0' 3 0* 1 1 0 3 1 Переходим к шагу 4.
Шаг 4. Среди невыделенных элементов матрицы Со есть нуль (сиз = 0). Переходим к шагу 5. Шаг 5. Так как четвертая строка, содержащая невыделенный нуль, не содержит 0*, то переходим к шагу 7. Ш а г 7 . Найденный невыделенный нуль обозначаем символом 0 и стРоим Ь-цепочкУ (с, со, сзм сы, ст4): то о о аТ. О' Т Т О' + О.' 0* 1 1 + 0' 3 0 1 1 0' 3 1 Переходим к шагу 8. Шаг 8. В Ь-цепочке все символы 0* заменяем нулями, а символы 0' заменяем на 0'. Вне 7,-цепочки все 0' заменяем нулями и снимаем все выделения строк и столбцов. Полученную матрицу стоимости обозначаем через Ст. 0 7 7 0* 0' 0 1 1 0 3 0' 1 1 0' 3 1 Переходим к шагу 1 следующей итерации (ттО = 2).
Вторая итерация Ш аг 1. Число элементов й в системе независимых нулей матрицы Ст равно четырем. А так как 14 = 4 = в, то переходим к шагу 2. 405 404 В этом случае 1з = шах(6, 7, 10, 41 = 10, 14 = шах (9, 3, 5, 2) = 9 11 = 1пах(10, 5, 7, 3) = 10, 1з — — шах(7, 9, 8, 8) = 9, 0 2 4 0 5 0 3 6 3 1 0 4 7 1 6 7 1 = шах сб, 7'= 1,п, 1=1,и 10 7 6 9 5 9 7 3 7 8 10 5 3 8 4 2 ПРИЛОЖЕНИЕ 1. ВЕНГЕРСКИЙ МЕТОД Ш аг, 2 . В соответствии с эквивалентной матрицей стоимости С' = С1 выписываем оптимальное решение рассматриваемой задачи, представленное в виде матрицы ее переменных О 0 0 1 1 О О 0 Хо=(х; )= ° Ф 0 1 0 О Выше при анализе задачи о назначениях было отмечено (см.
5.3), что на практике встречаются задачи, для которых параметр с, имеет смысл эффективности выполнения 4чй работы 1'-м исполнителем, 1, 1' =1, и. В таких задачах суммарная эффективность выполнения всех работ должна быть максимальной, что приводит к задаче (5.12). Для преобразования задачи (5.12) к стандартной задаче (5.11) можно воспользоваться приемом, рассмотренным в 5.3, или изменить первый шаг подготовительного этапа венгерского метода, который в этом случае принимает следующий вид. Шаг 1.
Для каждого столбца матрицы С=(с,") Е М (К) задачи о назначениях (5.12) находим максимальный элемент и формируем эквивалентную матрицу стоимости С' = (с',"), в которой с'; =1 — с,, 4,7 =1,н. Пример П1.3. Рассмотрим задачу о назначениях вида (5.12) с матрицей и эквивалентная матрица стоимости имеет вид Заметим, что зта матрица совпадает с матрицен С', полученной на первом шаге подготовительного этапа венгерского метода в примере П!.1 (задача минимизации затрат). А так как последующие шаги подготовительного этапа не изменятся, то понятно, что решение Хо, полученное в примере П1.2, будет оптимальным решением и для рассматриваемой задачи о назначениях (задача максимизации суммарной эффективности). 407 Приложение 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
