Задача о назначениях с вероятностными ограничениями

Задача о назначениях является одной из самых известных задач комбинаторной оптимизации и имеет огромное количество способов применения в реальной жизни. Так, в зависимости от условий, целевой функции и вида оптимизации, задача о назначениях может быть полезна в распределении ресурсов на производствах, логистических задачах, задачах, связанных с человеческими ресурсами, в различных экономических задачах, а также в задачах планирования расписаний. Решение задачи о назначениях является частью оптимизации в условиях неопределенности. Поскольку наша цель - это поиск лучшего решения без знания точных параметров задачи, мы рассматриваем робастную задачу о назначениях с вероятностными ограничениями. Подобная версия задачи может оценить наихудший случай, а также отразить возможные реальные ситуации, когда мы не знаем точного распределения параметров задачи, а можем говорить лишь о некотором семействе распределений. В качестве целевой функции была выбрана мера риска Conditional Value-at-Risk (CVaR), поскольку данная мера риска является когерентной, а значит более надежной для оценки. В ходе работы была сформулирована одноуровневая задача о назначениях с вероятностными ограничениями с помощью теории двойственности, а также были проведены численные эксперименты с помощью программного обеспечения CPLEX. Проведенные эксперименты позволили выявить связь между значением целевой функции построенной модели и параметрами (уровнем доверия, отклонением стоимостей).