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

Страницы работы

3 страницы (Word-файл)

Содержание работы

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

Пусть имеется m работников А1, А2, ..., Аm и п должностей В1, В2, ..., Bn. Известна мера cij полезности (эффективности, цен­ности, стоимости) работника Ai, на должности Вj . Требуется организовать такое закрепление работников на должности, при котором суммарная стоимость назначений будет максимальной.

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

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

     Пусть .

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

           (1)

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

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

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

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

                           (2)

при условиях

                                   (3)

                                         (4)

                                      (5)

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

Фактически мы получили задачу линейного программирования, но с булевыми переменными. Однако если отбросить ограничение (5), заменив его более простым условием неотрицательности xij, то за­дача о назначениях превращается в частный случай транспорт­ной задачи, где все запасы ai  и потребности bj равны единице. Если решать эту задачу любым методом, приводя­щим при целых ai и bj к целочисленному оптимальному решению, то неучтенные условия (5) удовлетворяются автоматически. Таким образом, для решения задачи о назначениях оказывается пригод­ным рассмотренный ранее метод потенциалов. Необходимо лишь положить там ai =1, bj=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  |

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

Похожие материалы

Информация о работе