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

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

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

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

1.1 Постановка задачи и ее редукция

1.2 Локальный поиск

1.3 Тестирование процедур локального поиска

1.4 Алгоритм глобального поиска

1.5 Тестирование алгоритма глобального поиска

1.6 Заключительные замечания.

2 Теоретические основы поиска гарантированных решений

2.1 Постановка задачи и ее взаимосвязь с задачей поиска оптимистического

решения специальной двухуровневой задачи
2.2 Свойства задачи нижнего уровня.
2.3 Редукция к задачам с.с. оптимизации.
2.4 Процедуры локального поиска
2.5 Алгоритм глобального поиска
2.6 Заключительные замечания.
3 Численный поиск гарантированных решений
3.1 Генерация тестовых задач
3.2 Тестирование локального поиска
3.3 Численный поиск гарантированных решений в сгенерированных задачах
3.4 Заключительные замечания
Заключение
Литература


В работах [,] было получено сведение неантагонистической игры двух лице передачей информации (задачи Штакельберга) в гарантированной постановке к семейству вспомогательных задач Штакельберга в оптимистической постановке. К сожалению, в -е годы XX в. В более поздней работе [3] результаты из [] были несколько обобщены. А именно, были ослаблены предположения на функции, входящие в постановку редуцируемой двухуровневой задачи. Единственным известным нам (и авторам публикации [1]) алгоритмом численного решения непрерывной задачи двухуровневой оптимизации в гарантированной постановке является алгоритм поиска гарантированного решения нелинейной задачи Штакельберга, предложенный и протестированный на задачах размерности до 4 в (1]. Этот алгоритм основан на сведении рассматриваемой двухуровневой задачи к так называемой задаче полубесконечного программирования. Некоторые из таких задач могут быть сведены к непрерывным двухуровневым задачам [). Объектом исследования диссертационной работы являются так называемые квадратично-линейные задачи двухуровневой оптимизации, в которых критерий эффективности игрока верхнего уровня — квадратичная функция, критерий эффективности игрока нижнего уровня — линейная функция, и множества допустимых стратегий игроков описываются линейными неравенствами. Основная цель диссертационного исследования состоит в разработке методов поиска оптимистических и гарантированных решений в (непрерывных) квадратично-линейных задачах двухуровневой оптимизации, эффективных с вычислительной точки зрения. Актуальность темы диссертационной работы обусловлена прежде всего широким полем практических приложений двухуровневых задач, а также сложностью исследуемых двухуровневых задач (которые могут быть сведены к невыпуклым задачам оптимизации, трудным с точки зрения поиска в них глобального решения). Приведем примеры практических двухуровневых задач. Определение размеров квот и дотаций производителям сельхозпродукции [,1]. Игроком верхнего уровня в данной задаче является некий орган управления, игроком нижнего уровня — агрегированный производитель сельскохозяйственной продукции. Задача игрока верхнего уровня игрока состоит в оптимальном выборе уровня квот и дотаций с учетом прогнозируемого рационального ответа игрока нижнего уровня на этот выбор. Пусть т — количество видов квот и дотаций, п — количество видов продукции, тогда стратегия игрока верхнего уровня определяется вектором х = (. Т1,. Оуь . Известны ограничения х* на максимальный размер финансировании квоты или дотации вида г, а также общие ограничения х^хти на максимальный суммарный размер финансирования квот или дотаций видов ть. При этом каждый из первых ш критериев отражает стремление к достижению рекомендуемого уровня х, квоты или дотации вида г (например, но экологическим соображениям может быть определен желаемый размер посевных площадей), а максимизация (т + 1)-го критерия {6, х) + (с, у) означает стремление увеличить трудовую занятость населения, где Cj — размер заработной платы, соответствующий количеству рабочих мест, требуемых для производства единицы продукции вида j, bi — размер заработной платы, соответствует количеству рабочих мест, дополнительно возникающих в случае увеличения дотации вида г (такие рабочие места возникают, например, при дотациях на постройку новых ирригационных систем, которые позволяют увеличить посевную площадь; в том случае, когда дополнительных рабочих мест не возникает, 6, = 0). Целыо игрока нижнего уровня является максимизация прибыли (d,y)t где d, — стоимость единицы вида продукции j = 1,. Ву < а + Ах, где Bkj — количество ресурса вида к = 1, требуемого для производства единицы продукции вида j, а* — запас ресурса вида к у производителя, Aki — количество ресурса вида к, соответствую! П2 на максимальный общий спрос на продукцию видов 7гА, . Таким образом, возникает следующая двухуровневая задача. Х)К(®» ~ &)2] - 1«Ь. I = 1,. ЛГ = {(П|,з) | 0 < ! П2 < , ПЬП2 — ЦвЛЫе}. Отметим, что эта задача принадлежит классу квадратично-линейных двухуровневых задач, которые исследуются в диссертационной работе.