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

ДИСКРЕТНЫЕ МОДЕЛИ, модели, переменные и параметры которых являются дискретными величинами, т. е. величинами, принимающими конечное или счётное число значений; в задачах, связанных с такими моделями, множество допустимых решений также дискретно. При построении и анализе дискретных моделей используются математические методы дискретной математики, алгебраические и другие известные математические методы, а иногда требуется разработка новых.

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

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

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

Лит.: Лихтенштейн В. Е. Модели дискретного программирования. М., 1971; Вагнер Г. Основы исследований операций: В 3 т. М., 1972-1973; Пропой А. И. Элементы теории оптимальных дискретных процессов. М., 1973; Финкельштейн Ю. Ю. Приближенные методы и прикладные задачи дискретного программирования. М., 1976; Моисеев Н. Н. Математические задачи системного анализа. М., 1981; Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности. М., 2000; Сигал И. Х., Иванова А. П. Введение в прикладное дискретное программирование: Модели и вычислительные алгоритмы. М., 2002.