КОМБИНАТОРНЫЕ МЕТОДЫ

в математическом программировании, точные и приближённые методы решения дискретных экстремальных задач, основанные на идеях комбинаторики, т. е. на переборе в различных сочетаниях элементарных составляющих, из к-рых должно быть сформулировано полное решение (план).
Одним из наиболее важных классов точных методов является метод ветвей и границ. Под этим общим названием объединяются многочисл. методы сокращённого перебора, в к-рых перебор осуществляется путём последоват. дробления множества планов на части с последующим поиском экстремума в каждой из частей. Для сокращения перебора используются различные критерии, позволяющие удалить из рассмотрения нек-рые части. Во мн. методах критерий отсева основан на часто встречающейся возможности оценить снизу минимум целевой функции на группе планов и отбросить эту группу, если оценка оказалась выше, чем значение целевой функции на лучшем из планов, встретившихся к этому моменту. Др. критерий отсева заключается в том, что удаётся сравнить отд. группы планов и сделать заключение о «неперспективности» нек-рых групп. Фактически к К. м. сводятся стандартные методы линейного программирования для нек-рых дискретных задач (связанных с транспортными потоками в сетях).
Из приближённых методов следует отметить эвристические методы, в к-рых имитируется деятельность «диспетчера» (напр., в задачах составления расписаний), т. е. формулируются нек-рые правила выбора решений, основанные на накопленном опыте решения задач данного класса в относительно устойчивой ситуации.
К. м. приспособлены специально для эффективного решения узкого круга задач и могут быть успешно применены в области конкретной экономики. Для их использования не требуется аналитич. описания решаемой математич. задачи, а достаточно описания формальных связей между элементарными составляющими плана на языке, близком к словесному описанию. В настоящее время К. м. широко применяются для отыскания оптимальных решений в экономике энергетики, ж.-д. транспорта, нефтепереработки и др. При этом, чем более специален тот или др. метод, т. е. чем более узкий класс задач он решает, тем он эффективнее в смысле затрат машинного времени ЭВМ и точности получаемых решений. И В. Романовский. Ленинград.