Методы декомпозиции экстремума и некоторые их применения в дискретно-непрерывных задачах оптимизации

• Автор: Маркелова, Елена Юрьевна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 1998
• Место защиты: Екатеринбург
• Количество страниц: 127 с.

СОДЕРЖАНИЕ
Введение
Глава I. Теоретическое обоснование метода декомпозиции
экстремума.
§1. Модельный пример дискретно- непрерывной маршрутной
задачи.
§2. Принцип декомпозиции в моделях со скалярным критерием
§3. Условия декомпозиции в многокритериальных моделях
§4. Условия декомпозиции задач оптимизации по конусу. 1)4
§5. Декомпозиция многокритериальных задач оптимизации в 4*
случае произвольных упорядоченных топологических пространств
Глава II. Модели и алгоритмы получения оптимальных решений маршрутно-распределительных задач дискретно - непрерывного характера.
§6. Исследование моделей распределительных задач на основе 6*
метода декомпозиции экстремума.
§7. Исследование моделей маршрутных задач на основе метода **
декомпозиции экстремума.
§8. Математическая модель задачи маршрутизации с конечным 82-
числом переходов и абстрактной функцией агрегирования затрат.
§9. Математическая модель одной задачи маршрутизации сигнала 9ч .с неаддитивной функцией агрегирования затрат.
§10. Численная реализация решения маршрутно-распределитель- -<Н
ных задач.
Список литературы
Приложение /с<'

Введение
В настоящей работе исследуется возможностиь решения оптимизационных задач на основе процедуры декомпозиции экстремума, суть которой состоит в разделении соответствующей экстремальной операции в задаче со связанными переменными на две компоненты. При этом одна из компонент включается в структуру оптимизируемой функции на основе специальных условий разложимости данной функции (критерия).
Вопросы такого рода могут возникать в различных задачах оптимизации функций многих переменных, включая многокритериальные задачи и задачи оптимизации по конусу. Необходимость таких исследований связана также с появлением большого количества прикладных оптимизационных задач, множество решений которых имеет сложную дискретно - непрерывную структуру. К таковым, в частности, относятся экстремальные задачи, связанные с маршрутизацией и распределением заданий между исполнителями в условиях, когда варианты перехода от одной элементарной задачи к другой составляют бесконечное множество. Сложность их моделирования обусловлена невозможностью разделенйя исходной задачи на дискретную и непрерывную подзадачи в силу связанности дискретных и непрерывных переменных.
Метод декомпозиции экстремума является развитием пошагового метода решения задач применительно к задачам оптимизации. Идея пошагового решения задач анализа, оптимизации, теории дифференциальных уравнений использовалась давно и представлена в работах таких известных математиков как Ферма, Эйлер, Маклорен. Но лишь в 50-х годах нашего столетия Р. Веллман и его ученики создали единообразный математический аппарат для изучения многошаговых оптимизационных процессов, обладающих определенными свойствами инвариантности - динамическое программирование (ДП).
Применению идей ДП для решения задач оптимизации различных классов посвящены многочисленные работы [2, 3, 9, 13, 16, 21, 22, 33, 42, 5]. В работах Р.Калабы, С.Дрейфуса, Р.Карпа, М.Хелда метод ДП применялся к решению задач маршрутизации. Отметим также исследования А.Вальда в области последовательного анализа статистических задач. Методы, использующие динамическое программирование и попятные процедуры, широко применялись в теории оптимального

управления и дифференциальных игр. (см., в частности, исследования Брайсона, Хо, Айзекса, Флеминга,Фридмана, Эллиота, Калтона и целого ряда других специалистов в этой области.)
Большой вклад в развитие конструкций, связанных с динамическим программированием, внесли исследования H.H. Красовского, А.Б. Кур-жанского, Ю.С. Осипова, А.И. Субботина, А.Г. Ченцова. Принцип экстремального прицеливания H.H. Красовского позволил получить эффективный метод решения для широкого класса задач теории конфликтного управления на основе подхода к анализу уравнения Айзекса - Веллмана с использованием программных конструкций, восходящих к принципу максимума Понтрягина. Идеи, связанные с решением уравнения Айзекса - Веллмана с применением конструкций негладкого анализа, получили дальнейшее развитие в работах А.И.Субботина.
В основе ДП лежит частный случай ” принципа инвариантного погружения” - принцип оптимальности Веллмана [3]: оптимальное решение исходной задачи образовано оптимальными решениями частных подзадач. Процедура построения функциональных уравнений Веллмана предполагает возможность декомпозиции экстремума и определяется возможностью внесения оптимума по части переменных под знак функции агрегирования, посредством которой решения частных подзадач образуют решение исходной задачи.
Первоначально Веллманом были сформулированы три условия, при которых справедлив принцип оптимальности.
(1) Частные подзадачи и исходная задача должны принадлежать одному семейству сходных задач. Каждая подзадача характеризуется небольшим количеством переменных, называемых параметрами состояния. На каждом шаге принимаются решения, преобразующие параметры состояния.
(2) Предистория системы не имеет значения для принятия будущих решений (принцип отсутствия последействия). Решение текущей задачи не изменяет решений предыдущих задач.
(3) Решение исходной задачи есть сумма решений частных задач, то есть функция агрегирования является аддитивной.
Однако вскоре появляются задачи с неаддитивными функциями агрегирования, и для них также строятся рекуррентные соотношения Веллмана [4],[57]. Так, в задаче коммивояжера на ”узкие места” функция агрегирования есть максимум между решениями двух соседних частных подзадач; в задаче ’’надежности” [4],[47] используется муль-

Тогда из (3.22), (3.23), (3.25) полупим:
(1°-е А (р(ип,у1п) А сР + €.
Итак, построена последователтность {<р(ип, угп)}г п£дг из Р, сходящаяся к <Р € Рт/(Р>), то есть с?0 является предельной точкой множества Р. В силу произвольности выбора °, имеем, что Pinf(D) С с/(Р).
п.4. Покажем, что Рт/(П) С Рт/(Р). Предположим противное: пусть с?0 € Рт/(Р) и <Р £ Ргп/(Р). Из п.З следует, что <Р € с£(Р). Так как Ргп/(Р) - внешне устойчиво, то существует ж0 £ Рт/(Р)}, такое что т°-<<Р. Так как Рт/(Р) С с/(Р>), то ж0 £ с/(Р), и последнее неравенство противоречит минимальности с?0 в с1(В). Значит с?0 6 Рг'п/(Р) и Рт/(Р) С Рт/(Р). Из пункта 2 и пункта 4 следует утверждение теоремы. Следующий пример показывает существенность условия ограниченности Р по е— конусу (условия 1) теоремы
З.2.).
Пример 3.2. Пусть и = Е, V = К. Определим ]У С и X V следующим образом: У = А[В, где
А = {(а,с)е[/х У|г; = 1пи, и > 0},
В = {(и,«) € и х У|т = и, и > 0},
Заметим, что И7 не является ограниченным по какому-либо £ - конусу (см.рис.3.3).
Пусть Ф : И7 —> К2, а именно:
У(и,ь) £]¥ Ф(м, ь) = (и, г»).
Пусть У гг € И7 : [м] : [м] К25 а именно:
V« 6 И'1т V« е 1УН : >/>[„](«) = (и,«);
Пусть, наконец, <у? : М х М2 —У К2, а именно:
УабК Уе!2: р(а,(3)) = р.
Очевидно, У(гг,г>) € И7 : Ф(«,г>) — ср(и, ф[и}(ь)). Более того, опера-
тор (р непрерывный, монотонно возрастает по второму аргументу и У гг € И7- Уу £ Хщ : К (у) р| Ход - ограничены.
В данном примере Рт/(Р) = {(0,0)}. Однако, множество О имеет следующий вид:
П = {(гг,г))|ц = 1пгг, и > 0}, и Pinf(D) = 0. Значит, Рт{(Р) % Рт/(В).