3.6Задачаоназначениях

Задачаоназначенияхможетбытьсформулированаследующимобразом.Имеетсяnра-бочихиmработизаданастоимостьназначениярабочегоiнаработуjдлявсехiиj.Каждыйрабочийможетбытьназначеннеболее,чемнаоднуработу,икаждаяработамо-жетвыполнятьсянеболее,чемоднимрабочим.Требуетсянайтидопустимоеназначение,прикоторомсуммарнаястоимостьFминимальна.

Еслирабочийнеможетвыполнятькакую-тоработу,соответствующаястоимостьравнабесконечности.Неограничиваяобщности,можносчитать,чтоn=m.Иначеможноввестификтивныхрабочихилификтивныеработыснулевымистоимостями.

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

Рассмотримзадачуоназначениях,заданнуюследующейматрицейстоимостейназначе-

ния.

1	4	6	3
9	7	10	9
4	5	11	7
8	7	8	5

Вначалевычтемизкаждогоэлементастрокинаименьшийэлементэтойстрокиповсемстрокам.Получимматрицу

0	3	5	2
2	0	3	2
0	1	7	3
3	2	3	0

Найдемсуммувычтенныхчисел∆=17.Далеевычтемизкаждогоэлементастолбца

наименьшийэлементэтогостолбцаповсемстолбцам.Получимматрицу

0	3	2	2
2	0	0	2
0	1	4	3
3	2	0	0

Найдемновуюсумму∆=20.Задачаоназначенияхсполученнойматрицейстоимостейэквивалентнаисходнойзадачеоназначениях.Дляполучениястоимостиоптимальногона-значенияисходнойзадачинеобходимокстоимостиоптимальногоназначенияновойзадачиприбавитьсуммувычтенныхчисел:F=F+∆.

Последняяполученнаяматрицаназываетсяприведенной.

Общийшаг.Есливприведеннойматрицеможновыбратьnнулевыхэлементовтак,чтовсеонирасположенывразныхстрокахистолбцах,тотакойвыборопределяетоп-тимальноеназначение.Иначе,находимминимальноечислолиний-строкистолбцов,покрывающихвсенули.Внашемслучаетакихлиний3-этостолбец1истроки2и4.Средиэлементов,непокрытыхэтимилиниями,находимнаименьшийэлемент.Вычитаемегоизнепокрытыхэлементовиприбавляемкдваждыпокрытым(строкойистолбцом).Получаемматрицу

0	2	1	1
3	0	0	2
0	0	3	2
4	2	0	0

ПовторяемОбщийшаг.Наэтотразсуществуютnнулевыхэлементоввразныхстрокахи

столбцах:

0	2	1	1
3	0	0	2
0	0	3	2
4	2	0	0

Онииопределяютоптимальноеназначение:рабочий1наработу1,рабочий2наработу

3ит.д.Стоимостьназначенияравна21.

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

Алгоритмрешенияупрощеннойзадачионазначениях

Шаг0.Строимлюбоедопустимоеназначение.Например,вкаждойстрокеотмечаемнольвстолбцеснаименьшимномером,несодержащемотмеченныйноль.

	1 2 3 4
1 2 3 4	0 3 2 2 2 0 0 2 0 1 4 3 3 2 0 0

Шаг1.Помечаемзнаком“-”всестроки,несодержащиеотмеченныхнулей.

	3
	1 2 3 4
1 2 3 4	0 3 2 2 2 0 0 2 0 1 4 3 3 2 0 0	1 -

а)Вкаждойпомеченнойстроке,напримерi,находимнеотмеченныенули.Столбцы,со-ответствующиеэтимнулям,отмечаемномеромстроки(i).Однаждыпомеченныйстолбецдалеенепомечается.Просматриваемвсепомеченныестроки.

б)Вкаждомпомеченномстолбце,напримерj,отыскиваемотмеченныйнуль.Еслионнайден,помечаемстроку,гдеонрасположен,номеромстолбца(j).Просматриваемвсепомеченныестолбцы.Возвращаемсяка),таккакпоявилисьновыепомеченныестроки.Шаг1завершается,когдапомеченстолбец,несодержащийотмеченногонуля.Вэтомслучаеколичествоотмеченныхнулейможетбытьувеличеноследующимобразом.Впоме-ченномстолбце,несодержащемотмеченногонуля,отмечаемнольвстроке,указываемойпометкойэтогостолбца.Затемвэтойстрокеделаемнеотмеченнымнульвстолбце,ука-зываемымпометкойэтойстроки.Процессповторяетсядотехпор,поканеотметимнульвстроке,первоначальнопомеченнойзнаком“-”(несодержащейотмеченныхнулей).ПовторяемШаг1.Алгоритмзавершается,когданевозможносделатьниоднойпометки.Помеченныестолбцыинепомеченныестрокиобразуютминимальноеколиче-

стволиний,покрывающийвсенули.