Алгоритмы максимизации супермодулярных функций и их применение в задачах оптимального распределения инвестиций в регионах тема диссертации и автореферата по ВАК РФ 08.00.13, кандидат физико-математических наук Хачатуров, Роман Владимирович

• Хачатуров, Роман Владимирович
• кандидат физико-математических наук
• 2002

Оглавление диссертации кандидат физико-математических наук Хачатуров, Роман Владимирович

Введение.

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

1.1. Необходимые понятия и определения из теории решёток, общая постановка задачи.

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

1.3. Классы экономико-математических моделей с супермодулярными функционалами.

Глава 2. Комбинаторные алгоритмы максимизации супермодулярных функций на булевой решётке.

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

2.2. Правила отбраковки неоптимальных решений.

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

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

Глава 3. Модели взаимодействия инвестора с регионами при решении задач оптимального распределения инвестиций.

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

3.2. Задача оптимального размещения инвестируемого капитала в зависимости от потенциалов регионов.

3.3. Задачи размещения инвестируемого капитала в проекты регионального развития.

3.4. Некоторые задачи оптимального использования топливно-энергетических ресурсов в регионе.

3.5. Анализ вычислительных экспериментов.

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

Задачи оптимизации супермодулярных функций начали активно изучаться в 60-е годы прошлого столетия в Вычислительном центре АН СССР под руководством В.П.Черенина [44]. Однако, нужно отметить, что первая работа В.П.Черенина, которую можно отнести к этой тематике, вышла ещё в 1948 году. Эта работа была посвящена задаче составления оптимального плана формирования поездов. Правда, им не использовалась терминология теории решёток и понятия супермодулярности, субмодулярности и модулярности функций. Однако, поставленная им задача, пользуясь современной терминологией, свелась к максимизации субмодулярной функции на булевой решётке. Для её решения В.П.Черенин предложил метод последовательных расчётов. Затем им и В.Р.Хачатуровым [45] была показана применимость этого метода к решению некоторых многоэкстремальных задач размещения предприятий. Впоследствии сотрудниками и аспирантами ВЦ РАН (В.Р.Хачатуровым, Н.Д.Астаховым, В.Е.Веселовским, В.Э.Лорером, А.Л.Шахазизяном, В.М.Монтлевичем и др.) был расширен класс конкретных экономико-математических задач, решение которых сводилось к минимизации супермодулярных функций на решётках различного типа [34-42,47]. Эти задачи были исключительно актуальными в плановой экономике, так как в них, как правило, требовалось минимизировать суммарные (капитальные, эксплуатационные, транспортные) затраты при решении задач оптимального размещения предприятий для различных отраслей народного хозяйства. Они были основными при разработке генеральных схем развития и размещения производства как отдельных регионов, так и всей страны в целом. В плановой экономике критерий максимизации функционала был востребован значительно меньше, задачи максимизации супермодулярных функционалов, означающих прибыль, не представляли интереса. Хотя этому были и другие причины.

Во-первых, в задачах максимизации может не выполняться свойство унимодальности супермодулярной функции на всех цепях булевой решётки, содержащих локальные максимумы, в то время, как для цепей, содержащих локальные минимумы, это свойство выполняется (см. главу 2). Это создало дополнительные трудности при построении алгоритмов их решения.

Во-вторых, Л.Ловасом в 1982-м году [50] было доказано, что задача максимизации супермодулярной функции является полиномиально разрешимой (в отличие от задачи минимизации), что способствовало ослаблению интереса к ней (хотя, до сих пор не известны эффективные вычислительные алгоритмы её решения).

С переходом к рыночной экономике при решении задач оптимального размещения предприятий, требующего, как правило, привлечения средств инвестора, большое значение начал приобретать критерий максимизации прибыли. В связи с этим стали актуальными задачи максимизации супермодулярных функций, к которым сводились задачи максимизации прибыли инвестора. Задачи максимизации и минимизации супермодулярных функций в некотором смысле дополняют друг друга: наименьшее значение прибыли, которое определяется решением задачи минимизации супермодулярного функционала, означает гарантированную прибыль, которая может быть получена при наихудшем распределении средств инвестора, а наибольшее значение затрат, определяемое решением задачи максимизации супермодулярного функционала, означает суммарные затраты, которые могут быть при наихудшем выборе мест размещения предприятий. В любом случае решение этих двух задач полезно для выявления наименее перспективных проектов, а также для определения полного интервала изменения значений прибыли и затрат на множествах всех возможных проектов, намеченных к реализации.

Вышеизложенное говорит об актуальности рассматриваемых задач.

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

Комбинаторные методы содержат, как правило, два основных элемента:

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

- оценивание наименьшего (или наибольшего) значения оптимизируемого функционала на получаемых подмножествах с целью выявления среди них заведомо не содержащие оптимальное решение исходной задачи.

Комбинаторные методы различаются способами разбиения и оценивания. Приведём наиболее часто применяемые при решении оптимизационных задач комбинаторные методы:

- метод последовательных расчётов [34,35,38,42,43,44,45,47,48].

- метод последовательного анализа вариантов [26];

- метод динамического программирования [4,14,34,38];

- методы упорядоченного перебора [12,16,20,21,24];

- метод ветвей и границ [17,18,19,22-25,38,46,49];

- аппроксимационно-комбинаторный метод [33,34];

- метод узловых векторов [31].

Разработанные в диссертации комбинаторные алгоритмы используют схему перебора метода последовательных расчётов и новые правила отбраковки неоптимальных решений, приведённые в главе 2.

Нужно отметить, что для решения задач конкретного вида с супермодулярными функционалами, рассматриваемых в главе 3, можно использовать метод ветвей и границ, и к решению некоторых из них он применялся другими авторами [23,31,46]. Однако использование этого метода будет менее эффективным, чем применение алгоритмов, основанных на методе последовательных расчётов, так как последние существенно используют свойство супермодулярности функционала в правилах отбраковки подмножеств неоптимальных решений. В методе ветвей и границ отбраковка неоптимальных решений реализуется с применением оценок, получаемых в результате решения оценочных задач. Заметим, что схемы перебора вариантов метода последовательных расчётов позволяют также применять для отбраковки оценки, используемые в методе ветвей и границ, наряду с использованием 3-го правило отбраковки (см. главу 2 диссертации).

При решении задач размещения интересные результаты были получены Лебедевым С.С. [23,31]. С помощью множителей Лагранжа получаются нижние оценки целевой функции на множестве допустимых решений. Эти оценки используются в схеме метода ветвей и границ, и они также могут быть использованы в схемах метода последовательных расчётов.

В настоящее время перспективным является направление в решении задач дискретного программирования, развиваемое Лебедевым С.С. и его учениками [31]. Развиваемый ими метод узловых векторов продемонстрировал высокую эффективность при решении задач размещения с ограниченными объёмами производства. Увеличение размерности решаемых задач достигается путём нетрудоёмкого построения оценочных функций, с помощью которых отбраковываются неперспективные варианты, для которых, в противном случае, пришлось бы решать большое количество задач линейного программирования транспортного типа. Этот метод также может быть использован в схемах метода последовательных расчётов.

Для решения задач используются также приближённые методы (например, методы локального спуска, методы случайного поиска и др.), имеющие большое значение для практики. Основным их недостатком является, как правило, невозможность получения достаточно точных оценок, позволяющих судить о близости получаемых решений к оптимальному. При нахождении приближённых решений важную роль играют эвристические алгоритмы, основанные на правдоподобных, но не обоснованных строго предположениях о свойствах оптимального решения задач. Для поиска приближённого решения иногда оказывается эффективным определение так называемого е-оптимального решения. Идея заключается в том, что постулируется желание определить не оптимальное решение, а решение, отличающееся от оптимального не более, чем на заданную величину s>0. Это позволяет, например, в методе ветвей и границ ввести правило s -отсева, что уменьшает объём перебора [17,18,19,24]. Для определения приближённого решения применяется также метод линейного программирования [1,6,8,9,10,15]. В этом случае исходная задача нелинейной оптимизации различными способами аппроксимируется задачей линейного программирования, с помощью которой определяется приближённое решение. Иногда удаётся определить погрешность приближённого решения, которая зависит от точности аппроксимации.

Диссертация состоит из трёх глав и основных выводов.

Заключение диссертации по теме «Математические и инструментальные методы экономики», Хачатуров, Роман Владимирович

Основные выводы

В диссертационной работе получены следующие основные результаты.

1. Сформулированы и доказаны теоремы (и следствия из них) о взаимосвязи задач максимизации и минимизации супермодулярных функций на булевой решётке.

2. Установлено, что в отличие от задачи минимизации, в задаче максимизации супермодулярная функция может не быть унимодальной на всех цепях, содержащих локальный максимум, и определено необходимое и достаточное условие, при выполнении которого она будет строго унимодальной.

3. Для случая строгой унимодальности всех максимальных цепей, содержащих локальный максимум, доказана теорема о том, что объединение глобальных максимума и минимума равно наибольшему элементу решётки, а их пересечение - наименьшему.

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

5. Для задачи максимизации супермодулярной функции на булевой решётке разработан комбинаторный алгоритм поиска точного решения, использующий схему перебора метода последовательных расчётов.

6. Разработан комбинаторный квадратичный алгоритм поиска приближённого решения задачи с оценкой погрешности найденного решения, который рекомендуется использовать для задач большой размерности (га>60).

7. Разработана общая структура экономико-математической модели взаимодействия инвестора с несколькими регионами при решении задач оптимального распределения инвестиций, которая позволяет формировать различные задачи оптимального размещения инвестируемого капитала. В рамках этой структуры были сформированы: задача оптимального размещения инвестируемого капитала в зависимости от потенциалов регионов, для которой была доказана супермодулярность оптимизируемого функционала, тем самым был получен новый класс задач с супермодулярным функционалом; задачи оптимального размещения инвестируемого капитала в проекты регионального развития, и показано, что они сводятся к одному из классов задач с супермодулярными функционалами.

8. Исследованы задачи оптимального использования топливно-энергетических ресурсов в регионе, сводящихся к задачам с супермодулярными функционалами.

9. На реальной информации проведён анализ вычислительных экспериментов, подтвердивший эффективность разработанных алгоритмов.

Список литературы диссертационного исследования кандидат физико-математических наук Хачатуров, Роман Владимирович, 2002 год

1. Багриновский К.А. О математических методах решения задачи оптимального размещения производства// Сб. Модели и методы оптимального развития и размещения производства. Научные труды НГУ, серия экономическая, вып. 8, Новосибирск, 1965.

2. Бекларян Л.А., Хачатуров Р.В. Задача оптимизации размещения инвестируемого капитала с учётом инвестиционно-финансовой политики регионов. /Препр. # WP/2001/132. -М.: ЦЭМИ РАН, 2001.-24 с. (Рус.).

3. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. М.: Наука, 1965. -458 с.

4. БиркгофГ. Теория структур. М.: Издательство иностранной литературы, 1952.408 с.

5. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. -М.: Изд-во «Факториал», 1998. 176 с.

6. Вотяков А.А., Фридман А.А. Дискретные задачи и метод ветвей и границ. Экономика и мат. методы 10 (1974) 3, 611-620.

7. Голыитейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа. -М.: Наука, 1969.

8. Гольштейн Е.Г., ЮдинД.Б. Новые направления в линейном программировании. -М.: Советское радио, 1966. 524 с.

9. Ю.Гранберг А.Г. Основы региональной экономики: Учебник для вузов. -М.: ГУ ВШЕ, 2000. -495 с.11 .Гретцер Г. Общая теория решеток. М.: Мир, 1982. 452 с.

10. Емеличев В.А., Комлик В.И. Метод построения последовательных планов для решения задач дискретной оптимизации. -М.: Наука, 1981.

11. ХА.Калихман И.Л., Войтенко М.А. Динамическое программирование в примерах и задачах. -М.: Высшая школа, 1979.

12. Карманов В.Г. Математическое программирование: Учеб. пособие. -4-е изд., перераб. и доп. -М.: ФИЗМАТ ЛИТ, 2000, 264 с.

13. Ковалёв М.М. Дискретная оптимизация. -Минск: Изд-во БГУ, 1977.

14. S.Kop6ym А.А., Сигал И.X., Финкельштейн Ю.Ю. Метод ветвей и границ. Обзор теории, алгоритмов, программ и приложений. Math operation forsch. Statist. Ser. Optimization, vol. 8(1977), N2, S.253-280.

15. Корбут A.A., Финкельштейн Ю.Ю. Дискретное программирование М.: Наука, 1969.

16. Лебедев С. С. Целочисленное программирование и множители Лагранжа // Экономика и мат. методы. 1974. Т. 10, №3. с. 593-610.

17. Лебедев С. С., Ковалевская М.И. Множители Лагранжа в простейшей задаче размещения: (Теория и вычислительный эксперимент)// Исследования по дискретной оптимизации: Сборник/ АН СССР. ЦЭМИ АН СССР. -М.: Наука, 1976.

18. Лебедев С.С., Финкельштейн Ю.Ю. Дискретное программирование // Сб. Математическое программирование. Вып.5 // Всесоюзная летняя школа по математическому программированию в Алма-Ате, 1968. Алма-Ата: Институт экономики АН Каз.ССР, 1969. -119 с.

19. Леонтьев В.К. Комбинаторика: ретроспектива и перспективы // Компьютер и задачи выбора. -М: Наука, 1989. -с. 49-88.

20. Михалевич B.C. Последовательные алгоритмы оптимизации и их применение. 1,11 // Кибернетика. 1965. - №1,2.

21. Региональное развитие: опыт России и Европейского Союза / Рук. авт. колл. и отв. ред. А.Г.Гранберг. -М.: ЗАО Изд-во «Экономика», 2000. -435 с.

22. Регионы России: Стат. сб. В 2 т. Т.1/ Госкомстат России. -М., 1999. -532 с.

23. Регионы России: Стат. сб. В 2 т. Т.2/ Госкомстат России. -М., 1999. -861 с.

24. Российские регионы после выборов-96. М.: Юридич. лит., 1997.

25. Седова С.В., Лебедев С. С. Решение одной задачи размещения методом узловых векторов// Экономикам мат. методы. 1999. Т. 35, №3. с.174-179.

26. Хачатуров В.Р. Математические методы региональногопрограммирования. -М.: Наука, 1989.

27. Хачатуров В.Р. Развитие энергетики и пути устойчивого развития мира. М.: Нефть и газ, 1997. (Акад. чтения; Вып. 11).

28. Хачатуров В.Р., Лорер В.Э. Исследование и минимизация супермодулярных функций на атомарных решётках. М.: ВЦ АН СССР, 1987,47 с.40Хачатуров В.Р., Монтлевич В.М. Минимизация супермодулярных функций на дистрибутивных решётках. М.: ВЦ РАН, 1999, 49 с.

29. Хачатуров В.Р., Шахазизян А.Л. Исследование свойств и минимизация супермодулярных функций на решётке, являющейся прямым произведением цепей. М.: ВЦ АН СССР, 1986, 30 с.

30. Хачатуров Р. В. Алгоритмы максимизации супермодулярных функций и их применение для оптимизации группирования областей в регионе. Журнал вычислительной математики и математической физики, 1999, том 39, № 1, с. 33-44.

31. Черенин В.П. Решение некоторых комбинаторных задач оптимального планирования методом последовательных расчетов//Научно-методические материалы экономико-математического семинара. ЛЭММ АН СССР. М.: Гипромез, 1962. Вып. 2. 44 с.

32. Черенин В.П., Хачатуров В.Р. Решение методом последовательных расчётов одного класса задач о размещении производства // Экономико-математические методы. М.: Наука, 1965.

33. Efroymson М.А., Ray T.L. A branch-bound algorithm for plant location// Operation Res. 1966. Vol. 14, N 3.

34. Khachaturov Vladimir R., Khachaturov Roman V., Khachaturov Ruben V. Supermodular Programming. First Conference of the Mathematical Society of the Republic of Moldova, Chisinau, August, 16-18, 2001, pp. 84-86.