Поиск глобального решения в задачах обратно-выпуклого программирования

• Автор: Яковлева, Татьяна Владимировна
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Иркутск
• Количество страниц: 146 с.

Оглавление
Введение

1 Глобальный поиск в обратновыпуклых задачах

1.1 Некоторые сведения об обратновыпуклых задачах

ф 1.2 Методы локального поиска.

1.2.1 Специальный метод локального поиска

1.2.2 Модифицированный метод Розена

1.3 Условия глобальной оптимальности.

1.4 Минимизирующие последовательности

1.5 Стратегия глобального поиска

1.6 Сходимость стратегии глобального поиска

2 Численное решение задач обратновыпуклого программирования
2.1 Постановка задач
2.2 О методах локального поиска
2.3 Специальный алгоритм глобального поиска
2.4 Численное решение задач с ограничением типа нормы
2.4.1 Выбор начального приближения.
2.4.2 Аппроксимация поверхности уровня
2.4.3 Результаты численного эксперимента
2.5 Численное решение задач с квадратичным ограничением общего вида .
2.6 Численное решение задач с другими нелинейными ограничениями .
2.7 Анализ вычислительного эксперимента
3 Численное решение задачи о многомерном рюкзаке
3.1 Постановки задач
3.2 Практические приложения.
3.3 О стратегии глобального поиска для задачи о рюкзаке
3.4 Построение аппроксимации поверхности уровня.
3.5 Построение оценок
3.6 Численный эксперимент по решению задачи о рюкзаке .
3.6.1 Алгоритм глобального поиска для решения задачи о рюкзаке . .
3.6.2 О решении линеаризованной задачи
3.6.3 Локальный поиск для задач о рюкзаке.
3.6.4 Результаты численного эксперимента
3.7 Метод исключения координат
3.8 Численное решение задачи о многомерном рюкзаке
Заключение
Библиография


Эго гармоничное взаимоотношение между постановками задач и условиями глобальной оптимальности, думается, подчеркивает естественность предложенного подхода. D работах A. C. Стрекаловского и его учеников [, , 5] на основе условий глобальной оптимальности (2) предложены алгоритмы глобального поиска для задачи выпуклой максимизации (СМ), а также приведены результаты его тестирования на некоторых прикладных задачах. Впоследствии подобные алгоритмы были предложены и для задач обратно-выпуклого программирования (, , 7), и, наконец, для общих задач d. X min, х G S, д(х) > 0. Когда функция /i(-) и множество S выпуклы, основные трудности ее решения связывают с ограничением д(х) > 0, которое и создает базовую нсвыпуклость в задаче (RC). Напомним кратко несколько практических задач, которые могут быть сформулированы в виде задачи обратно-выпуклого программирования {КС). Задача целочисленного программирования. Это весьма многочисленный класс задач, возникающих на практике [3, ], например, задачи планирования производства |], размещение предприятий и распределение капиталовложений |]. В качестве примера здесь рассмотрим задачу транспортного обслуживания []. Пусть из некоторого пункта необходимо доставить 6 человек. Транспортное агентство располагает автобусами п типов, вместимостью а* (г = 1,. В зависимости от типа автобуса установлены тарифы на проезд с,. Необходимо определить, какого типа автобусы и в каком количестве следует использовать так, чтобы суммарные издержки были минимальными. Пусть Xi — количество автобусов г-го типа. G Z+, г = 1 ,. Z+ — множество неотрицательных целых чисел. Л(у) = XIе* ? П = {у Є В? Кі, і = l,. Задача о дополнительности. Qxyx) + (с,х) 4- min, Ах > 6, х > 0. Если квадратная матрица <2 положительно определена, то целевая функция в задаче (5) выпукла, и условия Куна-Таккера являются достаточными условиями оптимальности в задаче (5). Ах — 6, А) = 0, А > 0, х? А Є Ет. Полученная задача (6) называется задачей о дополнительности [5, 9, 0, 5). Задача размещения. В j-ыt пункт потребления, Ху - объем перевозок, у, - объем производства в г-ом пункте, /,(у») - функциональная зависимость стоимости производства одной единицы продукции от объема производства в г-ом пункте производства, bj -объем потребления в . Именно эти слагаемые и создают специфику ограничения ? Разнообразие таких систем необычайно широко и включает в себя, в частности, игры типа центр и т подчиненных производителей (например, федерация — регионы, или регион — муниципалитеты и т. Рассмотрим простейшую из подобных игр: центр (I игрок) — один производитель (II игрок) (]. Каждый из участников имеет свой критерий эффективности и связанные ресурсы, но преимущество хода у I игрока. При выборе "центром" управления х игрок II выбирает свое управление у с целью оптимизировать свой критерий эффективности д(у) на множестве ограничений У(х) С Мп, зависящим от х. Р С тпу (7 : Л1т+п —> М — непрерывная функция. Иерархические системы управления (Многоуровневое программирование). Y(x). Естественно предположить, что у лица, принимающего решение на верхнем уровне, имеется свой взгляд на оценку принятия решений, следовательно, свой критерий эффективности, который оценивает и свою стратегию, и стратегию игрока II. Y{x), у ? S = {(х, у): АХ + Biy < bu х ? Y(х) = {v : Л2х + B2v ^(х), y? Y(x). Довольно часто целевая функция игрока II вогнута, как в линейном случае. Тогда и функция оптимального значения 1/(-) тоже оказывается вогнутой |1). При этом ограничение-неравенство в (9) оказывается обратно-выпуклым относительно х. В работах (, ] показано, что при описании задачи инженерного дизайна участвуют обратно-выпуклые ограничения. В [1] описано, как проблема расширения потока но сетям формалиризуется в виде задачи линейного программирования с одним дополнительным обратно-выпуклым ограничением. Другие интересные практические применения решения исследуемой задачи можно найти в работах [9, 3), где рассмотрена проблема огранения ценных камней, и в статье (), посвященной формализации экономической задачи о переоборудовании предприятия.