Из комбинаторных задач, сводящихся к моделям дискретно го программирования и имеющих большое прикладное значение, следует выделить задачу о назначениях (задача выбора), задачу о коммивояэ/сере (бродячем торговце) и задачи теории расписаний. Задача о назначениях формулируется обычно следующим образом. Требуется осуществить назначение п кандидатов на заданные п работ, дающее минимальные суммарные затраты (мак симальный эффект); при этом каждого кандидата можно назна чить только на одну работу, а каждая работа может быть выпол нена только одним кандидатом. Задача о коммивояжере описывает класс моделей нахожде ния замкнутых маршрутов, минимизирующих суммарное рассто- 321 яние (время, стоимость переезда) по маршруту из пункта А в этот же пункт А. Задачи теории расписания относятся к оптимизационным моделям планирования и организации дискретного производ ства. Важными в прикладном отношении являются комбинаторные задачи о покрытии. Они служат отысканию минимального под множества множества ребер заданного графа, содержащего все его вершины. К указанным задачам примыкают задачи опреде ления минимальных связей на электронных платах, а также крат чайших технологических маршрутов.
Ви переглядаєте статтю (реферат): «КОМБИНАТОРНЫЕ ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ» з дисципліни «Теорія систем і системний аналіз в управлінні організаціями»
