Полная версия

Главная arrow Туризм arrow Основы функционирования систем сервиса

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

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

В задаче о назначениях имеются п работников и п видов работ. Каждый работник может выполнять любую работу с разным уровнем мастерства, и стоимость работы зависит от уровня мастерства. Так, если на работу назначается специалист высокой квалификации, то стоимость работ будет выше. Целью задачи является нахождение оптимального плана распределения работников по всем видам работ.

Стоимость работ можно представить в виде таблицы

где /*, обозначает работников, pj — работы, Су — стоимость назначения /-го работника нау'-ю работу, i,j = 1, п. То, что число работников равно числу работ, не является ограничением общности, поскольку всегда можно ввести в модель фиктивных работников или фиктивные работы.

Как видно, задача о назначениях является частным случаем транспортной задачи, в которой работники соответствуют пунктам отправления, а работы — пунктам назначения. Только в данном случае все значения спроса и предложения равны 1.

Задачу о назначениях, так же как и транспортную, можно представить в виде задачи ЛП. Пусть переменная Ху соответствует факту назначения /-го работника нау-ю работу и принимает соответственно значение 1, если работник назначен на эту работу, и 0 в противном случае. Получаем следующую задачу ЛП:

при условиях

К задаче о назначениях можно свести многие задачи сервиса, например задачу распределения средств удовлетворения потребностей, задачу о выполнении услуг и т.п. Для решения подобных задач используется венгерский метод [32], который базируется на симплекс-методе, теории двойственности и позволяет решить данные задачи без решения системы линейных уравнений.

Двойственную задачу о назначениях можно записать так:

где переменные uh i = 1, п, соответствуют ограничениям (9.40), a v,-, у = 1, п, — ограничениям (9.41).

В соответствии с задачами сервиса по оптимизации системы производитель—потребитель будем рассматривать прямую задачу о назначениях как задачу производителя. Согласно смыслу задачи производитель стремится выполнить работы с минимальной стоимостью. Если минимум стоимости обеспечивается путем назначения на работы квалифицированных сотрудников, то в этом заинтересован и потребитель. Например, уменьшение стоимости связано с уменьшением времени выполнения работы. Обычно меньшую стоимость работ обеспечивают неквалифицированные рабочие. Например, время выполнения не важно, а важен факт выполнения. Тогда неквалифицированному работнику можно меньше заплатить.

Будем рассматривать двойственную задачу как задачу потребителя. Тогда переменную и, можно трактовать как стоимость качества работы, выполняемой i-м специалистом. Переменную vy можно трактовать как стоимость качества выполняемой работы, связанную с j-й работой потребителя. Каждый потребитель может иметь свои условия выполнения одной и той же работы. Ясно, что потребители стремятся максимизировать качество выполнения работ данным предприятием. При этом стоимость за качество работ не должна превышать определенной величины.

КОНТРОЛЬНЫЕ ВОПРОСЫ

  • 1. Сформулируйте общие правила составления двойственной задачи.
  • 2. Как составить симплекс-таблицу двойственной задачи?
  • 3. Каков порядок решения двойственной задачи с использованием симплекс-метода?
  • 4. Как можно интерпретировать двойственность с точки зрения задач сервиса? Приведите примеры.
  • 5. Как связаны между собой решения прямой и двойственной задач?
  • 6. Как вычислить оптимальный план двойственной задачи, зная оптимальный план прямой задачи?
  • 7. Как связано решение двойственной задачи с устойчивостью от изменения ограничений прямой задачи?
  • 8. Как изменяются целевые функции производителей и потребителей от изменения цен на продукцию и эффективности производства?
 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>