Динамическое программирования для задач коммивояжера с прибылью и условиями предшествования

Среди разновидностей задачи коммивояжера выделяются «задачи сприбылью», имеющих две принципиальных особенности: 1.) В задаче представлены два критерия качества — обычноприсутствуют некоторые «затраты» на перемещения (определены на парах городов — на ребрах графа) и «прибыль», определенная на городах. 2.) Требуется оптимизировать по одному из двух критериев, соблюдая ограничения по второму, откуда допустимость посещения *не всех*городов. Обзор разновидностей смотрите в (Feillet et al. 2005) В докладе будет предложено решение методом динамического программирования задач с прибылью, осложненных условиями предшествования; подобные постановки, насколько известно автору, не рассматривались в литературе, но могут представлять некоторый интерес. Например, можно рассмотреть задачу о демонтаже атомного реактора, где будет ограничение по «затратам» —- дозовой нагрузке на персонал и оптимизация по прибыли — экспертной оценки важнос ти наискорейшего демонтажа объектов; подобная разновидность задач с прибылью называется «задачей об ориентировании» (Orienteering Problem).
Выбор динамического программирования против классически применяемой вещественной релаксации линейного программирования оправдан именно наличием условий предшествования. (Feillet et al. 2005) Feillet D., Dejax P., Gendreau M., Traveling Salesman Problems with Profits // Transportation Science, vol. 396 No.2, 1995, pp. 118–205