назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [ 70 ] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]


70

Общая задача назначения п работников на п работ представлена в табл. 5.31. Таблица 5.31

Работы

Работники

Коэффициент сц равен стоимости назначения работника i на работу j (i,j= 1, 2, n). То, что количество работников равно количеству работ, не является ограничением общности, поскольку всегда можно ввести в модель фиктивных работников или фиктивные работы.

Задача о назначениях является частным случаем транспортной задачи, в которой работники соответствуют пунктам отправления, а работы - пунктам назначения. В данном случае все величины спроса и предложения равны 1. Стоимость "транспортировки" рабочего i на работу равна cv. Задачу о назначениях можно эффективно решить точно так же, как и транспортную задачу. Вместе с тем тот факт, что все величины спроса и предложения равны 1, привел к разработке упрощенного алгоритма решения, названного венгерским методом. Хотя этот метод не имеет никакого отношения к транспортной задаче, он, как и метод потенциалов, все равно основан на симплекс-методе.

5.4.1. Венгерский метод7

Для представления этого метода используем два примера. Интерпретация венгерского метода как симплекс-метода будет рассмотрена в следующем разделе.

Пример 5.4.1

Трое детей Джоя Клини - Джон, Карен и Терри - желают подзаработать немного денег на школьную экскурсию в местный зоопарк. М-р Клини выбрал три вида работ, которые дети выполнить могут за определенную плату: стрижка газона, уборка гаража и мойка семейного автомобиля. Чтобы избежать ненужных споров между детьми, он опросил каждого (конечно, по секрету), сколько за каждый вид работ они хотят получить. Результаты опроса (в долл.) представлены в табл. 5.32.

Таблица 5.32

Стрижка газона

Уборка гаража

Мойка машины

Джон

Карен

Терри

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



Основываясь на этой информации, как распределить работы между детьми с минимальными (денежными) потерями для м-ра Клини?

Решим эту задачу о назначениях венгерским методом.

Этап 1. В исходной матрице стоимостей определим в каждой строке минимальную стоимость и отнимем ее от других элементов строки.

Этап 2. В матрице, полученной на первом этапе, найдем в каждом столбце минимальную стоимость и отнимем ее от других элементов столбца.

Этап 3. Оптимальным назначениям будут соответствовать нулевые элементы, полученные на предыдущем этапе.

Обозначим через pt и qt минимальные стоимости соответственно в строке / и столбце у, определенные на первом и втором этапах описанного выше алгоритма. Минимальные стоимости по строкам находятся по исходной матрице стоимостей, как показано в табл. 5.33.

Таблица 5.33

Стрижка газона Уборка гаража Мойка машины Минимумы по строкам

Джон

Pi =9

Карен

Д2 = 9

Терри

Рз = 8

Теперь вычтем минимальные стоимости из элементов соответствующих строк, и в результате получим следующую матрицу.

Таблица 5.34

Стрижка газона

Уборка гаража

Мойка машины

Джон

Карен

Терри

Минимумы по столбцам

Oi =0

02=1

9з = 0

На втором этапе алгоритма находим минимальные значения по столбцам и вычитаем их из элементов соответствующих столбцов. В результате получим матрицу, представленную в виде табл. 5.35.

Таблица 5.35

Стрижка газона

Уборка гаража

Мойка машины

Джон

Карен

Терри

В последней матрице подчеркнутые нулевые элементы определяют оптимальное решение: Джон будет убирать в гараже, Карен подстригать газон, а Терри достанется мойка машины. Эти работы обойдутся м-ру Клини в 9 + 10 + 8 = 27 долл. Отметим, что эта сумма всегда равна (р, + р2 + р3) + (<?, + q2 + q3) = (9 + 9 + 8) + + (0 + 1 + 0) = 27 долл. (Доказательство этого приведено в следующем разделе.)



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

Пример 5.4.2

Предположим, что в примере 5.4.1 представлено четыре ребенка и четыре вида работ. Таблица 5.36 соответствует матрице стоимостей для этой задачи (данные представлены в долл.).

Таблица 5.36

Виды работ

Дети 2

Применение первого и второго этапов алгоритма к исходной матрице (при этом рх =1, рг = 7, р3 = 4, р4 = 5, <?, = 0, q2 = 0, <?3 = 3 и <?4 = 0) приводит к следующей матрице (проверьте!).

Таблица 5.37

Виды работ 2 3

Дети

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

Этап 2.1. Если после выполнения первого и второго этапов описанного алгоритма не получено допустимое решение, выполните следующие действия.

i) В последней матрице проведите минимальное число горизонтальных и вертикальных прямых по строкам и столбцам, чтобы вычеркнуть в матрице все нулевые элементы.

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [ 70 ] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]