Классическая задача о назначениях формулируется так:

Имеется некоторое число работ и некоторое число исполнителей. Любой исполнитель может быть назначен на выполнение любой (но только одной) работы, но с неодинаковыми затратами. Нужно распределить работы так, чтобы выполнить работы с минимальными затратами.

Это задача линейного программирования и решается, например, венгерским алгоритмом.

А как можно решить эту задачу при наличии дополнительных усложнений вносящих нелинейность? Например:

  1. Число работ меньше числа исполнителей. При этом Петя, Вася и Коля так привыкли работать в одной команде, что если вы возьмете на работу всех троих, то каждый согласится работать на 10% дешевле
  2. Возможен и обратный вариант - Саша и Маша терпеть не могут друг друга и согласятся работать в одной компании только за двойную оплату.
  3. Для каждой работы определено рабочее место и рабочие места расположены в ряд. Петя, Вася и Коля хотят не просто работать вместе, а сидеть за соседними столами, иначе скидка отменяется

Очевидно, что задача решается методом полного перебора. Есть ли другие варианты?

задан 5 Мар '17 13:28

Опять же другие варианты NP-трудные либо приводящие к хорошему но неоптимальному решению

(5 Мар '17 16:40) abc
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×981
×11
×2

задан
5 Мар '17 13:28

показан
167 раз

обновлен
5 Мар '17 16:42

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru