33. Дискретное программирование в принятии решений.
Дискретное программирование (сокращено ДП, часто называется также целочисленным и комбинаторным программированием) сформировалось как самостоятельная и важная часть математического программирования в конце 60-х годов XX века. Основная цель дискретного программирования – выбор наилучшего варианта из конечного, возможно, очень большого их числа. Возникающие при этом экстремальные задачи имеют ряд особенностей, которые не встречаются в стандартных задачах математического программирования.
Под задачей дискретного программирования понимается целочисленная задача, в которой все или некоторые переменные должны принимать не любые целые значения.
В общем виде задачи дискретного программирования записывается следующим образом:
Пусть 𝑀={𝑎1, 𝑎2 … 𝑎𝑛 }и f – числовая функция, определенная на элементах множества М. Требуется найти элемент 𝑎j, на котором достигается абсолютный максимум (или минимум) функции f.
Особенности задач ДП.
Нерегулярность. Дискретные задачи математического программирования входят в класс нерегулярных задач. В них локальный экстремум может не совпадать с глобальным, а область допустимых решений невыпуклая и несвязная, что делает невозможным решение их с помощью стандартных методов, применяемых для решения регулярных задач математического программирования.
Трудности при определении окрестности.
Невозможность выполнения большого перебора на ЭВМ.
Методы решения задач ДП.
Метод отсечения. Метод основан на идее сведения решения нерегулярной задачи к решению конечной последовательности регулярных задач. Эта идея регуляризации позволяет свести решение этой задачи к решению последовательности линейных задач. Если полученное решение удовлетворяет условию целочисленности, то процесс окончен. В противном случае к ограничениям исходной задачи добавляется новое линейное ограничение. Помимо отсечения выделяют так же комбинаторные методы и приближенные методы.
34. Стохастическое программирование в принятии решений
Стохастическое программирование — раздел математического программирования, совокупность методов решения оптимизационных задач вероятностного характера. Это означает, что, либо параметры ограничений (условий) задачи, либо параметры целевой функции, либо и те и другие являются случайными величинами (содержат случайные компоненты).
Тем не менее, стохастическое оптимальное программирование является весьма важной и перспективной ветвью прикладной математики уже хотя бы потому, что на практике принятие решений всегда происходит в условиях той или иной неопределенности. Ясно также, что задачи стохастического программирования оказываются существенно сложнее соответствующих детермированных вариантов.
Задачи, в которых сj, аij,,bi — случайные величины, относят к задачам стохастического программирования
Переход от чистых стратегий к смешанным расширяет область определения задачи. Достижимый максимум целевой функции может при этом только увеличиться, а достижимый минимум — только уменьшиться. Вычисление оптимальной смешанной стратегии иногда называют определением решающего распределения стохастической задачи.
Задача стохастического программирования предусматривает стохастическую постановку и целевой функции, и ограничений.
Стохастическое программирование позволяет по-новому подойти к решению задач, информационная структура которых известна заранее. Процесс решения задачи стохастического программирования может быть разделен на два этапа. На первом этапе строится закон управления — решающие правила или решающие распределения, связывающие решение или механизм формирования решения с реализованными значениями и заданными статистическими характеристиками случайных параметров условий задачи.
Предварительный этап не требует знания конкретных реализаций значений параметров целевой функции и ограничений. Построение решающих правил или распределений требует лишь информации о структуре задачи и о некоторых статистических характеристиках случайных исходных данных.
На втором этапе анализа стохастической модели решающие правила или распределения используются для оперативного решения задачи. Второй этап естественно называть оперативным этапом анализа стохастической модели.
При этом формирование законов управления — решающих правил или решающих распределений — связывается не с оперативной работой, а с этапом проектирования управляющей системы. Стохастическое программирование и, в частности, стохастическое расширение открывают, таким образом, путь оперативного анализа сложных задач, альтернативой которому являются экспертные оценки и волевые решения.