Задача о закреплении работников на должности, при котором суммарная стоимость назначений будет максимальной

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

Пусть имеется m работников А₁, А₂, ..., А_m и п должностей В₁, В₂, ..., B_n. Известна мера c_ij полезности (эффективности, цен­ности, стоимости) работника A_i, на должности В_j . Требуется организовать такое закрепление работников на должности, при котором суммарная стоимость назначений будет максимальной.

Если c_ij интерпретировать как издержки назначения A_i, на В_j, то естественно решать задачу закрепления работников на должности, при котором минимизируются общие затраты.

     Построим математическую модель этой задачи.

     Пусть .

Рассмотрим булеву матрицу (x_ij) размера т х п, такую, что:

,             (1)

При этих условиях (x_ij) называется планом или матрицей на­значений. Среди планов выделяют такие, для которых в (1) дости­гается равенство. Они называются насыщенными.

Стоимость любого плана (x_ij) выражается суммой .

Окончательно математическая модель задачи будет такой.

Найти матрицу X=(x_ij) , такую, что:

                           (2)

при условиях

;                                     (3)

                                         (4)

                                      (5)

Другими словами, ищется насыщенная матрица назначений, оптимизирующая форму F.

Фактически мы получили задачу линейного программирования, но с булевыми переменными. Однако если отбросить ограничение (5), заменив его более простым условием неотрицательности x_ij, то за­дача о назначениях превращается в частный случай транспорт­ной задачи, где все запасы a_i  и потребности b_j равны единице. Если решать эту задачу любым методом, приводя­щим при целых a_i и b_j к целочисленному оптимальному решению, то неучтенные условия (5) удовлетворяются автоматически. Таким образом, для решения задачи о назначениях оказывается пригод­ным рассмотренный ранее метод потенциалов. Необходимо лишь положить там a_i =1, b_j=1.

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

                         =====================================

                  Таблица - Контрольный пример

               ============================================================

               |     Наименование показателя                |  Величина   |

               |==========================================================|

               |     ВХОДНЫЕ ДАННЫЕ                         |             |

               | Целевая функция                            |Максимальная |

               | Количество должностей                      |           5 |

               | Количество работников                      |           5 |

               ============================================================

     Т а б л и ц а  -  Ц е н а  н а з н а ч е н и й

=========================================================

|  №  |    1    |    2    |    3    |    4    |    5    |

=========================================================

   1        3.0       2.0       5.0       4.0       5.0

   2        5.0       3.0       2.0       1.0       4.0

   3        1.0       2.0       6.0       3.0       2.0

   4        4.0       3.0       5.0       4.0       1.0

   5        1.0       2.0       2.0       1.0       5.0

=========================================================

Таблица - Задача о назначениях

 ============================

 |  Работник  |  Должность  |

 |==========================|

 |      1     |      4      |

 |      2     |      1      |

 |      3     |      3      |

 |      4     |      2      |

 |      5     |      5      |

 ============================

 | Max F:            23.00  |

 ============================