Алгоритмы максимизации супермодулярных функций и их применение в задачах оптимального распределения инвестиций в регионах

• Автор: Хачатуров, Роман Владимирович
• Шифр специальности: 08.00.13
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Москва
• Количество страниц: 95 с.

СОДЕРЖАНИЕ
Введение

Глава I. Задачи оптимизации супермодулярных функций

на булевой рештке.

1.1. Необходимые понятия и определения из теории решток.

общая постановка задачи

1.2. Краткий обзор результатов для задачи минимизации супермодулярных функций на булевой рештке.

1.3. Классы экономикоматематических моделей с

супермолулирными функционалами.

Глава 2. Комбинаторные алгоритмы максимизации

супермодулярных функций на булевой рештке2Я

2.1. Взаимосвязь задач максимизации и минимизации супермодулярных функций на булевой рештке.
2.2. Правила отбраковки неопгимальных решений
2.3. Квадратичный алгоритм поиска приближенного
решения задачи максимизации супсрмодулнрной функции
2.4. Алгоритм поиска точного решения задачи максимизации супермодулярной функции с использованием схемы перебора метода последовательных
расчтов.
Глава З. Модели взаимодействия инвестора с регионами при решении задач опти.иального распределения
инвестиции
3.1. Общая постановка задачи
3.2. Задача оптимального размещении инвестируемого
капитала в зависимости от потенциалов регионов
3.3. Задачи размещения инвестируемого капитала в проекты регионального развития
3.4. Некоторые задачи оптимального использования топливноэнергетических ресурсов в регионе
3.5. Анализ вычислительных экспериментов
Основные выводы.
Литература


Глава I. Необходимые понятия и определения из теории решток. Краткий обзор результатов для задачи минимизации супермодулярных функций на булевой рештке. Глава 2. Взаимосвязь задач максимизации и минимизации супермодулярных функций на булевой рештке. Глава З. Модели взаимодействия инвестора с регионами при решении задач опти. Основные выводы. Задачи оптимизации супермодулярных функций начали активно изучаться в е годы прошлого столетия в Вычислительном центре АН СССР иод руководством В. П.Черенина . Однако, нужно отметить, что первая работа В. П.Черенина, которую можно отнести к этой тематике, вышла ещ в году. Эта работа была посвящена задаче составления оптимального плана формирования поездов. Правда, им не использовалась терминология теории решток и понятия супермодулярности, субмодулярности и модулярности функций. Однако, поставленная им задача, пользуясь современной терминологией, свелась к максимизации субмодулярной функции на булевой рештке. Для е решения В. П.Черении предложил метод последовательных расчтов. Затем им и В. Р.Хачатуровым была показана применимость этою метода к решению некоторых многоэкстремальных задач размещения предприятий. Впоследствии сотрудниками и аспирантами ВЦ РАН В. Р.Хачату ровым, И. Д.Астаховым, В. Е.Веселовским, В. Э.Лорером, А. Л.Шахазизяном, В. М.Монтлсвичсм и др. Они были основными при разработке генеральных схем развития и размещения производства как отдельных регионов, так и всей страны в целом. В плановой экономике критерий максимизации функционала был востребован значительно меньше. Хотя этому были и другие причины. Вопервых, в задачах максимизации может не выполняться свойство унимодальности супермодулярной функции на всех цепях булевой рештки, содержащих локальные максимумы, в то время, как для цепей, содержащих локальные минимумы, это свойство выполняется см. Эго создало дополнительные трудности при построении алгоритмов их решения. Вовторых, ЛЛовасом в м году было доказано, что задача максимизации супер. С переходом к рыночной экономике при решении задач оптимального размещения предприятий, требующего, как правило, привлечения средств инвестора, большое значение начал приобретать критерий максимизации прибыли. В связи с этим стали актуальными задачи максимизации супсрмодулярных функций, к которым сводились задачи максимизации прибыли инвестора. В любом случае решение этих двух задач полезно для выявления наименее перспективных проектов, а также для определения полного интервала изменения значений прибыли и затрат на множествах всех возможных проектов, намеченных к реализации. Вышеизложенное говорит об актуальности рассматриваемых задач. Алгоритмы максимизации супермодулярных функций относятся к классу комбинаторных. Известны различные типы комбинаторных алгоритмов методов. Комбинаторные методы различаются способами разбиения и оценивания. Разработанные в диссертации комбинаторные алгоритмы используют схему перебора метода последовательных расчтов и новые правила отбраковки неоптнмальных решений, приведнные в главе 2. Нужно отмстить, что для решения задач конкретного вида с супермодулярными функционалами, рассматриваемых в главе 3, можно использовать метод ветвей и границ, и к решению некоторых из них он применялся другими авторами ,,. Однако использование этого метода будет менее эффективным, чем применение алгоритмов, основанных на методе последовательных расчтов, так как последние существенно используют свойство суиермодулярности функционала в правилах отбраковки подмножеств неоптимальиых решений. В методе ветвей и границ отбраковка неоптнмальных решений реализуется с применением оценок, получаемых в результате решения оценочных задач.