Дискретные модели

Дискре́тные моде́ли, модели, переменные и параметры которых являются дискретными величинами, т. е. величинами, принимающими конечное или счётное число значений; в задачах, связанных с такими моделями, множество допустимых решений также дискретно. При построении и анализе дискретных моделей используются математические методы дискретной математики, алгебраические и другие известные математические методы, а иногда требуется разработка новых.

Дискретные модели возникают в связи со многими задачами в экономике, управлении, технике и других прикладных областях. Задачи дискретных моделей, как и алгоритмы их решения, носят, как правило, комбинаторный характер, что обусловлено конечностью множества возможных вариантов решений. Среди разработанных дискретных моделей можно выделить следующие основные классы: дискретные модели транспортного типа и планирования перевозок, сетевые и потоковые дискретные модели, дискретные модели управления запасами, дискретные модели размещения, дискретные модели теории расписаний, дискретные модели логического проектирования, дискретные модели распределения ресурсов, дискретные модели формирования производственных систем, дискретные модели ранжирования и кластеризации. В качестве отдельных классов дискретных моделей рассматриваются стохастические и динамические модели. Большое внимание уделяется разработке дискретных экономико-математических моделей.

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

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