2015-07-14
1610
Если мы столкнулись с проблемой назначения, в которой надо получить максимум целевой функции, то алгоритм венгерского метода имеет некоторые особенности. Прежде всего заметим, что венгерский метод позволяет решить задачи о назначениях на минимум. Для того, чтобы применить этот метод, нужно каким-то образом свести данную задачу на максимум к задаче на минимум целевой функции. В задаче на максимум предпочтительнее выбирать клетки с наибольшими Сij, в то время как в задаче на минимум — клетки с наименьшими Сij. Оптимальное решение получалось в нулевых клетках последней преобразованной матрицы. Рассмотрим особенности этой задачи на конкретном примере.
Пусть Сij — числа, характеризующие прибыль, которую приносит каждый i-ый рабочий, если он работает на j-ом месте. Матрица такой задачи имеет вид:
Таблица 2.8.8
| Исполнители | ||||
| Задача | ||||
Принципиальное отличие задачи на максимум от задачи на минимум заключается в этапе 1. Здесь выбирается наибольший элемент в каждой строке и от него отнимаются все остальные элементы соответствующих строк.
|
|
|
Таблица 2.8.9
| Исполнители | ||||
| Задача | ||||
Элементы таблицы III. 24 уже имеют другой смысл. Это не чистые прибыли, а потери прибыли от максимально возможной. Ясно, что для того, чтобы достичь наибольшей прибыли, необходимо избежать потерь прибыли или, если это не удается, иметь их как можно меньшими. А это значит, что мы от задачи на максимум (таблица III. 23) перешли к задаче на минимум (таблица III. 24).
В итоге, оптимальное решение данной задачи будет:
x11= x23 = x34 =x42 = 1
