ДИСКРЕТНОЕ ПРОГРАММИРОВАНИЕ

ДИСКРЕТНОЕ ПРОГРАММИРОВАНИЕ

- область математики, занимающаяся исследованием и решением экстремальных задач на конечных множествах. Пусть М=1, а 2, ..., а п}и f - числовая функция, определенная на элементах множества М. Требуется найти элемент на к-ром достигается абсолютный минимум (или абсолютный максимум) f на М. Сокращенно такие задачи записываются:

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

1. Число п=|М| должно быть достаточно большим настолько, чтобы задача не решалась непосредственным просмотром значений f( а i) вручную или на ЭВМ. Так, в задаче коммивояжера, к-рая является типичной задачей Д. п., число вариантов Qпри обходе тпунктов равно

В задачах минимизации булевых функций (см. Булевых функций минимизация, Булевых функций метрическая теория) |М|>22n.

2. Задача не должна быть регулярной. Задача наз. регулярной, если: а) для каждого определена непустая окрестность S( а i, М), и

б) локальный экстремум f, т. е. точка а;такая, что f(ai) = extr f(x),. определяется при помощи простого алгоритма, в) локальный экстремум совпадает хотя бы с одним глобальным.

Таким образом, Д. п. рассматривает задачи, имеющие, вообще говоря, несколько локальных экстремумов. В типичных случаях число локальных экстремумов весьма велико. Напр., в задачах целочисленного линейного программирования с булевыми переменными, в к-рых функционал и ограничения зависят от переменных х 1, . . . , xk число элементов в Мне больше 2k, а число локальных экстремумов может быть равным const. (см. [2]). Трудность решения задач Д. п. и определяется наличием большого числа локальных экстремумов. Универсальных эффективных методов решения задач Д. п. не создано (1978). Как показывают исследования по минимизации булевых функций - хорошо исследованной модельной задаче Д. п. (см. также Алгоритм локальный), создание таких методов, по-видимому, невозможно. Методы, в достаточной степени универсальные, такие, как метод ветвей и границ (см. [1]) и его различные модификации, являются методами направленного перебора. Они эффективно применяются для решения специализированных задач Д. п. Однако для каждого из таких методов существуют обширные классы задач, для к-рых методы направленного перебора мало отличаются по сложности от методов полного перебора. Другой источник математич, трудностей в задачах Д. п. состоит в том, что множество М, на к-ром ищется экстремум f, часто задается в неявной форме. Так, в задачах целочисленного линейного программирования множество Мопределяется как совокупность целочисленных решений системы линейных неравенств. При таком и более сложных способах задания Мнетривиальной становится не только задача полного перечисления М, но и указания хотя бы одного элемента из М. В силу изложенного, основные результаты Д. п. получены при решении и исследовании более узких классов задач. К таким классам относятся транспортная задача, задача о коммивояжере и нескольких коммивояжерах, линейное целочисленное программирование, задача о расписаниях (см. Расписаний теория), экстремальные задачи на графах (см. Графов теория), задачи минимального представления булевых функций и функций k-значной логики и т. д.

Другое направление в теории дискретных экстремальных задач состоит в развитии приближенных методов, обычно применяемых при решении практич. задач большой размерности. Принципиально эти методы не отличаются от соответствующих методов поиска экстремумов непрерывных функций и функционалов. В Д. п. используются аналоги алгоритмов локальной оптимизации, алгоритмов спуска, случайного поиска и т. п. (см. обзор приближенных методов решения задач Д. п. в [3]).

Интересным как с теоретич. точки зрения, так н в решении прикладных задач является статистический подход к задачам Д. п. Пусть совокупность задач {Z} можно представить в виде где |{Z}i|>|{Z}j| при i>j и при Говорят, что подмножество

составляет почти все задачи Z, если

Для различных классов задач Д. п. имеет место следующий факт: существует (а часто и эффективно описывается) совокупность {Z' } почти всех задач {Z}, для к-рых нахождение экстремума или хорошего приближения к экстремуму возможно в классе простых алгоритмов. Это было замечено впервые при решении задач синтеза оптимальных управляющих систем, напр, в минимизации булевых функций в классе дизъюнктивных нормальных форм, см. Булевых функций нормальные формы, а также [4]. Напр., задача выделения экстремальных конъюнкций, входящих хотя бы в одну минимальную дизъюнктивную нормальную форму булевой функции f(x1, . . . , х n), неразрешима в классе локальных алгоритмов при где k- индекс локального алгоритма, l- величина памяти. В то же время задача выделения элементарных конъюнкций, входящих хотя бы в одну "почти минимальную" дизъюнктивную нормальную форму для почти всех булевых функций, разрешима в классе локальных алгоритмов при k =2, l=1 (см. [5]). Столь же значительное сокращение трудоемкости при переходе к почти всем задачам получается для экстремальных задач на графах, в за-, даче о построении оптимальных покрытий и т. д.

Лит.:[1] Корбут А. А., Финкельштейн Ю. Ю., Дискретное программирование, М., 1969; [2] Коробков В. К., "Проблемы кибернетики", 1965, в. 14, с. 297 - 99; [3] Финкельштейн Ю. Ю., Приближенные методы и прикладные задачи дискретного программирования, М., 1976; [4] Дискретная математика и математические вопросы кибернетики, т. 1, М., 1974; [5] Журавлев Ю. И., "Дискретный анализ", 1964, № 3, с. 41-77.

Ю. И. Журавлев.


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Игры ⚽ Нужен реферат?

Полезное


Смотреть что такое "ДИСКРЕТНОЕ ПРОГРАММИРОВАНИЕ" в других словарях:

  • Дискретное программирование — [discrete programming] раздел оптимального программирования, изучающий экстремальные задачи, в которых на искомые переменные накладывается условие целочисленности, а область допустимых решений конечна. Таким образом, здесь используется модель… …   Экономико-математический словарь

  • дискретное программирование — Раздел оптимального программирования, изучающий экстремальные задачи, в которых на искомые переменные накладывается условие целочисленности, а область допустимых решений конечна. Таким образом, здесь используется модель общей задачи… …   Справочник технического переводчика

  • дискретное программирование выборочных величин — — [http://slovarionline.ru/anglo russkiy slovar neftegazovoy promyishlennosti/] Тематики нефтегазовая промышленность EN discrete programming …   Справочник технического переводчика

  • Дискретное программирование — (дискретная оптимизация) раздел математического программирования. В противоположность задачам оптимизации с непрерывными переменными, переменные в задачах дискретного программирования принимают только дискретные значения, например, целочисленные …   Википедия

  • Математическое программирование —         математическая дисциплина, посвященная теории и методам решения задач о нахождении экстремумов функций на множествах, определяемых линейными и нелинейными ограничениями (равенствами и неравенствами).          М. п. раздел науки об… …   Большая советская энциклопедия

  • МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ — математическая дисциплина, посвященная теории и методам решения задач о нахождении экстремумов функций на множествах конечномерного векторного пространства, определяемых линейными и нелинейными ограничениями (равенствами и неравенствами). М. п.… …   Математическая энциклопедия

  • ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ — раздел математического программирования, в к ром исследуется задача оптимизации (максимизации пли минимизации) функции нескольких переменных, связанных рядом уравнений и (или) неравенств и удовлетворяющих условию целочисленности (используются… …   Математическая энциклопедия

  • Целочисленное программирование — [integer programming] см. Дискретное программирование …   Экономико-математический словарь

  • Сигал, Израиль Хаимович — В Википедии есть статьи о других людях с такой фамилией, см. Сигал. Израиль Хаимович Сигал Дата рождения: 17 апреля 1938(1938 04 17) (74 года) Место рождения: Херсон, СССР Страна …   Википедия

  • МАКСИМИЗАЦИЯ И МИНИМИЗАЦИЯ ФУНКЦИЙ — конечного числа переменных задача поиска экстремума функции под этой задачей понимается: 1) нахождение 2) отыскание точек максимума или минимума, если достигаются на допустимом множестве (см. Максимум и минимум функции). 3) построение… …   Математическая энциклопедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»