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

Пример

Для выполнения четырех видов работ выделено четыре человека. Каждый из ннх может быть назначен на выполнение только одной работы. (Исполните­ли должны быть «неделимы», то есть не могут одновременно выполнять не­сколько работ — важное требование задачи о назначениях.) Стоимость назна­чений задана матрицей, номер строки которой соответствует номеру исполни­теля, а номер столбца — номеру работы:

'3 6 7 10'

5 6 3 8 2 8 4 16,8 6 5 9 _/

Пусть, например, в нашей задаче стоимость назначения — это время вы­полнения работы. Если квалификация работника ей соответствует, она будет выполнена быстрее. Необходимо так распределить исполнителей по работам, чтобы общие затраты времени были минимальны. (На каждую работу— по возможности, лучшего работника!).

Пусть переменная *,у = 1, если /-й исполнитель назначен на /-го работу, и *j = 0 в противном случае. Обозначив целевую функцию (общие затраты времени) через F, построим математическую модель задачи:

F = Зл'п + 6.Y12 + 7.V13 + 1 0-Y14 + 5.\'21 + 6.\*22 + 3*23 + 8.Y24 + 2Хз| + 8*32 + 4*33 ■*" 16.V34 + + 8д-₄| + 6.Y42 + 5.Y43 + 9л*44 —> min,

Л'п + *|₂+*13 +.YI4 <1,.Yu + *21 +*31 +*41 >1,

*21 + *22 + *23 + *24 < 1 > *12 + *22 + *32 + *42 > 1,

*31 + *32 + *33 + *34 < 1, *13 + *23 + *33 + *43 > •,

*41 + *42 + *43 + *44 ^ 1 > *14 + *24 + *34 + *44 > 1.

*,_у> 0, где / £ [1, 4], / 6 [1, 4].

Знаки < в ограничениях означают, что каждый человек может быть назна­чен не более чем на одну работу, а знаки >— что каждую работу должен вы-поднять, по крайней мере, один работник. Эти знаки справедливы, когда работ не больше, чем исполнителей.

Если исполнителей на все работы не хватает, используются специальные приемы, позволяющие решить задачу в Excel. Поскольку задача о назначени­ях — частный случай транспортной задачи (когда все запасы и потребности равны 1), эти приемы аналогичны описанным в разделе 3.3 (см. «Варианты транспортной задачи»). В WinQSB эти приемы не нужны, так как там знаки не­равенств не задаются и все варианты задачи о назначениях вводятся одинаково.

Внимание! Условие целочнсленности переменных в задаче о назначениях задавать не нужно. Так же, как и в транспортной задаче при целочисленных за­пасах и потребностях, решение автоматически получается целым.

Решение с помощью пакета WinQSB

Задача о назначениях является частным случаем транспортной задачи. По­этому для ее решения воспользуемся той же самой программой Network Mod­eling, которую использовалась в разделе 3.2.

Задание параметров задачи

Для ввода новой задачи выберите команду File ► New Problem и дей­ствуйте далее подобно тому, как описано в разделе 3.2. Но теперь при задании параметров следует выбрать другой тип задачи — задача о назначениях (As­signment Problem) (рис, 4.1). При этом количество исполнителен вводится в поле Number of Objects, а количество работ— в поле Number of Assignments.