Математические методы в производственном и операционном менеджменте. Сухарев Н.О - 29 стр.

     Глава 4

     ЗАДАЧА О НАЗНАЧЕНИЯХ

     4.1. Пример
     Для выполнения четырех видов работ выделено четыре человека.
Время выполнения каждой работы каждым исполнителем задано матри-
цей, номер строки которой соответствует номеру исполнителя, а номер
столбца — номеру работы:
                                            ⎛3   6 7 10 ⎞
                                            ⎜           ⎟
                                            ⎜5   6 3 8 ⎟
                                            ⎜2   8 4 8 ⎟
                                            ⎜           ⎟
                                            ⎜8   6 5 9 ⎟⎠
                                            ⎝
     Необходимо так распределить исполнителей по работам, чтобы об-
щие затраты времени были минимальны.
     Пусть переменная xij = 1, если i-й исполнитель назначен на j-ю рабо-
ту, и xij = 0 в противном случае. Обозначив целевую функцию (общие за-
траты времени) через F, построим математическую модель задачи:
           F = 3 x11 + 6 x12 + 7 x13 + 10 x14 + 5 x 21 + 6 x 22 + 3 x 23 + 8 x 24 +
           + 2 x31 + 8 x32 + 4 x33 + 16 x34 + 8 x 41 + 6 x 42 + 5 x 43 + 9 x 44 → min,
           x11 + x12 + x13 + x14 = 1,                     x11 + x 21 + x31 + x 41 = 1,
           x 21 + x 22 + x 23 + x 24 = 1,                  x12 + x 22 + x32 + x 42 = 1,
            x31 + x32 + x33 + x34 = 1                     x13 + x 23 + x33 + x 43 = 1,
           x 41 + x 42 + x 43 + x 44 = 1,                   x14 + x 24 + x34 + x 44 = 1,
                                  xij ∈ [0,1], где i ∈ [1,4], j ∈ [1,4].



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




                                                  29