§ 3. Классификация прикладных задач

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

3.2. Из комбинаторных задач, сводящихся к моделям дискретного программирования и имеющих большое прикладное значение, отметим прежде всего задачу о коммивояжере (бродячем торговце) и задачу теории расписаний. Обе эти задачи являются предметом обширной литературы; однако детальное их рассмотрение выходит за рамки настоящей книги. Мы ограничимся поэтому описанием соответствующих дискретных моделей.

Задача о коммивояжере описывает класс моделей нахождения маршрутов развозки груза, минимизирующих суммарный пробег. Что же касается задачи теории расписаний, то она является моделью основной массы задач организации производства.

3.3. К числу других комбинаторных задач, важных в прикладном отношении, относятся также задачи о покрытии, привлекшие к себе большое внимание в самые последние годы. Эти задачи касаются нахождения минимального подмножества множества ребер данного графа, содержащего все вершины графа. Они находят применение в вопросах синтеза логических сетей и в других близких задачах.

К указанным задачам примыкают также задачи типа задач о двойном назначении (минимальные связи на радиотехнических платах, кратчайшие технологические маршруты).

3.4. Упомянем также о весьма важном и широком классе задач оптимального размещения производства, специализации, кооперирования и пр., в которых различными путями возникает дискретность.

3.5. Итак, мы можем выделить следующие основные типы прикладных задач дискретного программирования:

1. Задачи с неделимостями.

2. Комбинаторные задачи.

3. Задачи о покрытии и другие задачи дискретной оптимизации сетей.

4. Задачи размещения.

Отметим, что всякая классификация прикладных задач дискретного программирования неизбежно оказывается неполной, ибо среди этих моделей мы находим и задачи сельскохозяйственного производства, и задачу оптимальной синхронизации сигналов при регулировании уличного движения и пр.