Теоретические вопросы двухэтапной векторной оптимизации тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение

Глава 1. Неопределенность в многокритериальной оптимизации

§1. Векторная оптимизация.

§2. Векторная оптимизация в условиях объективной неопределенности.

§3. Оптимумы точечно-множественных отображений.

§4. Определение многокритериального максиминимакса.

Глава 2. Обратная логическая свертка в задаче поиска векторного максиминимакса

§1. Параметризация слейтеровского значения многокритериального максминимакса с помощью ОЛС.

§2. Параметризация с помощью обратной логической свертки в нерегулярном случае

§3. Аппроксимационные свойства ОЛС.

§4. Задача повышения живучести многопродуктовых сетей

Задачи принятия решений с многими критериями возникают в исследовании операций при моделировании сложных систем, эффективность функционирования которых не удается заранее описать одним показателем. Но кроме этого, функционирование сложных систем, как правило, происходит в условиях объективной неопределенности — незнания ряда внешних факторов, влияющих на эффективность [56, 12, 15, 28, 48, 10, 13, 26]. Для того чтобы получить в таких условиях наилучшие гарантированные оценки эффективности, ставят минимаксные или максиминные задачи векторной оптимизации [41, 19, 63, 20, 6]. Множество, определяющее гарантированное значение соответствующего векторного мини-макса или максимина, характеризует живучесть исследуемой системы (при адекватной корректировке формальных определений).

Принятие управляющих решений в сложных системах в условиях неопределенности зачастую оказывается двухэтапным. Ряд параметров приходится фиксировать a priori, — до поступления информации о значениях неопределенных факторов, а часть (корректирующее управление) можно выбрать потом. И те, и другие суть стратегии оперирующей стороны. Предположив, что оперирующая сторона интересуется максимизацией векторного критерия, придем к задаче на векторный макси-минимакс и к проблеме формализации ее решения на основе принципа наилучшего гарантированного результата [67, 68].

Задачи такого типа возникают, в частности, при исследовании живучести сетевых систем и при синтезе многопродуктовых сетей по критерию живучести. Действительно, качество функционирования многопользовательской сетевой системы определяется мультипотоком — вектором 2 одновременно пропускаемых по сети потоков заявок пользователей (тяготеющих пар, или видов продуктов). С целью повышения качества функционирования сети с заданным вектором и пропускной способности ребер ставят задачу векторной максимизации 2 [32]. При исследовании живучести сетевой системы учитывается, что исходный вектор и пропускной способности может неконтролируемо уменьшаться в известных пределах. Обозначим результирующий вектор через w. Тогда гарантированная оценка качества функционирования сети определяется (см. [5]) как гарантированное значение векторного минимакса

Min Max z. weW(u) zeZ(w)

Этот минимакс зависит от и, и в предположении, что и £ U выбирается с целью повышения живучести, приходим к проблеме максимизации векторного минимакса, т.е. к поиску

Мах Min Мах ueu weW(u) zez(w)

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

Мах Min Мах (1) u£U weW{u)z<EZ(w) v ; v ' со связными ограничениями. (Для упрощения изложения опускаем зависимость Z от и.) В случае единственного критерия гарантированный подход в двухэтапной максимизации приводит к скалярной задаче на максиминимакс, рассмотренной, в частности, в [50, 14, 60]. Скалярные минимаксные задачи со связными ограничениями исследовались, например, в [36, 21].

Мы видим несколько возможных способов определения значения векторного максиминимакса: последовательное применение операций Мах, Min, Мах к объединению соответствующих множеств, аналогично [19, 20]; применение Мах к значению векторного минимакса, подробно изученного в [4]; обобщение понятия векторного максимина [41] на случай точечно-множественных отображений и применение полученного определения к множеству Мах Ф(г,и),и). z£Z(w)

В Главе 1 будет описан каждый из этих способов. В § 1.1 даны основные определения и рассмотрены особенности векторной оптимизации. В § 1.2 проведено сравнительное исследование минимаксных задач векторной оптимизации с целью выявления соотношений между различными определениями и их связи с наилучшим гарантированным результатом оперирующей стороны. Формализация значения оптимума точечно-множественных отображений предложена в § 1.3, она также позволяет обобщить введенные конструкции на случай многоэтапного принятия решений в условиях неопределенности. Значение векторного максими-нимакса определено в § 1.4, где показано, что все перечисленные способы, когда их применение корректно, приводят к одному и тому же множеству, совпадающему с построенным с позиций принципа гарантированное™ результата в [67]. При условии неотрицательности векторного критерия это множество имеет вид:

Max Min Max $(z,w,u) — МахФ, neu weW{u)zez{w) 4 7 где Ф = [J П U {Ф > ЩФ < ${z,w,u)}. ueu weW{u) zez(w)

Здесь и далее стандартные знаки неравенств для векторов трактуются покомпонентно, Мах понимается в смысле Парето либо Слейтера [12, 41], а 0 обозначает нулевой вектор соответствующей размерности.

Таким образом задача на векторный максиминимакс сводится к задаче на векторный максимум. Методы многокритериальной максимизации широко представлены в научной литературе [41, 18, 16, 29, 53, 31, 44], но для их применения в нашем случае необходимо уметь находить множество Ф, что является совсем не тривиальной проблемой. По этой причине нужны методы непосредственной параметризации и аппроксимации значения векторного максиминимакса, предложенные в Главе 2.

Традиционно для описания множеств Парето и Слейтера используется метод сверток [12, 41]. Сразу заметим, что множество Ф оказывается невыпуклым даже для линейных (сетевых) задач, и применение линейной свертки частных критериев для параметризации и аппроксимации МахФ не оправдано. Мы будем рассматривать обратную логическую свертку, предложенную в [45, 44] на базе логической свертки из [12].

Обратная логическая свертка предполагает замену максимизируемого вектора критериев Ф — ., <£>q) параметрическим семейством скалярных критериев

Г1 min Vi <pi, l>> € M, i(El(n) где M = {¡i > 0| Ef=ißi = 1} — стандартный симплекс в IR^, /(/i) = {i £ I\ ßi 0}, / = {1, 2,., Q}.

Обратная логическая свертка для задач на векторный максимум подробно изучена в [44, 45, 46], для задач на векторный минимакс она исследована в [6], а в [67] предложено определять с ее помощью значение векторного максиминимакса.

Подробно вопрос параметризации МахФ изучен в § 2.1. Показано, что задача на векторный максиминимакс сводится к параметрическому семейству скалярных задач поиска

0[fi]= max min max min ¡ijlipAz, w, u) VfiGM.

U<EU w£W(u) zeZ(w) i<El{[J.)

Отметим, что в предположениях непрерывности всех частных критериев по совокупности переменных, непрерывности по Хаусдорфу отображений И/(-), Z(-) и компактности W(u)} Z(w) все минимумы и максимумы достигаются и являются непрерывными функциями тех векторов 2, w и и, от которых зависят (см. [50] или задачи 4.9, 4.10 из [33]).

Доказано, что при выполнении условия регулярности ф черта над множеством — символ операции замыкания), обобщающего условия регулярности из [45, 6], имеет место представление

Мах Ф = и ем где Мах понимается в смысле Слейтера.

Исследованию нерегулярного случая посвящен § 2.2. Показано, что отсутствие регулярности не исключает возможности использования ОЛС для корректной параметризации. Такая параметризация не приводит к потере эффективных решений, одновременно позволяя избавиться от части заведомо не информативных полуэффективных точек [67].

Аппроксимация значения векторного максиминимакса с помощью метода сверток (§ 2.3) предполагает задание некоторой конечной (5-сети на множестве М параметров и решение соответствующих оптимизационных задач для конечного числа /j Е М. Корректность аппроксимации основана на свойствах функции ß[fi] — доказаны непрерывность в регулярном случае и существование непрерывного продолжения (9[/i] в нерегулярном. Существенное преимущество обратной логической свертки состоит в том, что для линейного случая она позволяет значительно уменьшить число решаемых задач. В [44, 45, 46] получены формулы аналитического пересчета значений Мах вектора линейных критериев для всех точек, принадлежащих одной слейтеровской грани, по значениям в конечном числе точек. Там же разработаны алгоритмы сокращения перебора и выделения паретовских граней. Предложенные алгоритмы модифицированы в [4, 5] для аппроксимации минимакса в сетевом случае. В задаче повышения живучести сети множество Ф является объединением многогранников, так что, несмотря на невыпуклость, аналогичные формулы пересчета значений минимакса свертки в пределах слейтеровских граней сохраняются и для максиминимаксных постановок.

В § 2.4 проводится изучение задачи повышения живучести сетевых систем, для которой

Мах Min Мах 2= II в\и]и — II /i max min max min —. ueu wew(u) zez(w) ueU ^ei-r(u) Zzz(w) iei(ß)

Здесь d[ß] имеет смысл наибольшего гарантированного уровня обеспеченности вектора ¡1 потоковых требований пользователей сетевой системы. Вектор 9[/i]f.i — это вектор потоков, которые будут гарантированно пропущены по сети при любых возможных значениях неконтролируемых факторов. Объединению таких векторов по всем вариантам требований и оказывается равной максимальная гарантированная оценка живучести сети с критерием эффективности — вектором потоков. Тем самым значение векторного максиминимакса для сетевой постановки допускает интерпретацию в содержательных терминах, понятных оперирующей стороне, что способствует принятию более обоснованных решений.

Основные результаты, выносимые на защиту.

1. Проведено детальное исследование и систематизация возможных подходов к формализации решения многокритериальных задач с неопределенными факторами, установлены соотношения между различными определениями векторного минимакса и максимина. Введены и обоснованы понятия максимума и максимина точечно-множественных отображений, изучены их свойства.

2. Исследованы основные способы определения значения векторного максиминимакса как решения задачи двухэтапной векторной максимизации. Показано, что все корректные подходы приводят в качестве слейтеровского значения векторного максиминимакса к множеству, совпадающему с определением, построенным на базе принципа наилучшего гарантированного результата Ю.Б. Гермейера.

3. Обоснована возможность использования обратной логической свертки для параметризации и аппроксимации слейтеровского значения векторного максиминимакса. Изучена проблема корректной параметризации и аппроксимации значения векторного максиминимакса в нерегулярном случае.

4. Разработан математический аппарат исследования проблемы повышения живучести сетевых систем как задачи двухэтапной векторной оптимизации.

Указанные результаты опубликованы в работах [67, 68].

Заключение

1. Абасов Т.М. Некоторые классы невыпуклых задач исследования операций: Автореф. дис. докт. физ.-матем. наук. М.: МГУ, ф.ВМиК, 1993.

2. Ашманов С.А. Линейное программирование. М.: Наука, 1981.

3. Ашманов С.А. Условная устойчивость задач линейного программирования // Программное оборудование и вопросы принятия решений. М.: Изд-во МГУ, 1989. С. 99-105.

4. Воробейчикова O.A. Векторный минимакс со связанными ограничениями: Автореф. дис. канд. физ.-матем. наук. М.: МГУ, ф.ВМиК, 1998.

5. Воробейчикова O.A., Новикова Н.М. Векторный минимакс со связанными ограничениями // Вестн. Моск. ун-та. Сер.15, Вычисл. ма-тем. и киберн. 1996. № 4. С. 45-48.

6. Воробейчикова O.A., Новикова Н.М. Параметризация значения векторного минимакса со связанными ограничениями //Ж. вычисл. матем. и матем. физ. 1997. Т.37. № 12. С. 1467-1477.

7. Воробейчикова O.A., Новикова Н.М. Метод сверток в задаче поиска векторного максимина // Вестн. Моск. ун-та. Сер.15, Вычисл. матем. и киберн. 1998. № 1. С. 24-26.

8. Вязгин В.А., Федоров В.В. Математические методы автоматизированного проектирования. М.: Высшая школа, 1989.

9. Гасанов И. И. Многокритериальная задача стохастического оптимального управления в дискретном времени. М: ВЦ АН СССР, 1989.

10. Гермейер Ю.Б. Приближенное сведение с помощью штрафных функций задачи определения максимина к задаче определения максимума // Ж. вычисл. матем. и матем. физ. 1969. Т.9. № 3. С. 730-731.

11. Гермейер Ю.Б. Введение в теорию исследования операций. М.: Наука, 1971.

12. Давыдов Э.Г. Исследование операций. М.: Высшая школа, 1990.

13. Давыдов Э.Г., Херсонская JI.B. О редукции некоторых задач многократного минимакса со связанными ограничениями // Вестн. Моск. ун-та. Сер.15, Вычисл. матем. и киберн. 1992. № 2. С. 51-54.

14. Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. М.: Наука, 1972.

15. Дубов Ю.А., Травкин С.И., Якимец В.Н. Многокритериальные модели формирования и выбора вариантов систем. М.: Наука, 1986.

16. Дымков М.П. Исследование задач многокритериального линейного программирования // Проблемы оптимального управления. Минск: Наука и техника, 1981. С. 25—42.

17. Емельянов С.В., Ларичев О.И. Многокритериальные методы принятия решений. М.: Знание, 1985 (сер. "Математика, кибернетика", № 10).

18. Жуковский В.И., Салуквадзе М.Е. Многокритериальные задачи управления в условиях неопределенности. Тбилиси: Мецниереба, 1991.

19. Жуковский В.И., Салуквадзе М.Е. Оптимизация гарантий в многокритериальных задачах управления. Тбилиси: Мецниереба, 1996.

20. Завриев С.К., Завриева M.K. Стохастический градиентный алгоритм итерационного метода штрафов для отыскания связанного максимина // М.: Изд-во МГУ, 1988. С. 105-116.

21. Злобин А. С. Параметрические методы решения минимаксных и многокритериальных задач // Автореф. дис. канд. физ.-матем. наук. М.:ВЦ АН СССР, 1984.

22. Ильин В.А., Садовничий В.А., Сеидов Вл.Х. Математический анализ. M : Наука, 1979.

23. Карзанов A.B. Комбинаторные способы решения разрезных задач о мультипотоках // Комбинаторные методы в потоковых задачах. Вып. 3. М.: ВНИИСИ, 1979. С. 6-69.

24. Карлин С. Математические методы в теории игр, программировании и экономике. М.: Мир, 1964.

25. Карманов В.Г., Федоров В.В. Моделирование в исследовании операций. М.: Твема, 1996.

26. Краснощекое П. С., Морозов В.В., Федоров В.В. Декомпозиция в задачах проектирования. I // Изв. АН СССР. Техн. кибернетика. 1979. № 2. С. 7—17.

27. Краснощекое П.С., Петров A.A. Принципы построения моделей. М.: МГУ, 1983.

28. Краснощекое П. С., Петров A.A., Федоров В.В. Информатика и проектирование. М.: Знание, 1986 (сер. "Математика, кибернетика", № 10).

29. Лотов A.B. Введение в экономико-математическое моделирование. М.: Наука, 1984.

30. Лотов A.B., Вушенков В.А., Каменев Г.К., Черных О.Л. Компьютер и поиск компромисса. Метод достижимых целей. М.: Наука, 1997.

31. Малашенко Ю.Е., Новикова Н.М. Модели неопределенности в многопользовательских сетях. М.: Эдиториал УРСС, 1999.

32. Морозов В.В., Сухарев А.Г., Федоров В.В. Исследование операций в задачах и упражнениях. М.: Высшая школа, 1986.

33. Мулен Э. Теория игр с примерами из математической экономики. М.: Мир, 1985.

34. Нейман Дж. Ф., Моргенштерн О. Теория игр и экономическое поведение. М.: Наука, 1970.

35. Новикова Н.М. Метод штрафов в задаче поиска максимина со связанными переменными // Матем. методы в иссл. операций М.: Изд-во МГУ, 1981. С. 83-91.

36. Ногин В.Д. Двойственность в многоцелевом программировании // Ж. вычисл. матем. и матем. физ. 1977. Т.17. № 1. С. 254-258.

37. Ногин В.Д. Определение и общие свойства относительной важности критериев. — В трудах XXIX научной конф. ПМ-ПУ "Процессы управления и устойчивость". СПб.: СпбГУ, 1998. С. 373-381.

38. Нодиновекий В.В. // Ж. вычисл. матем. и матем. физ., 1979. Т.19. № 6.

39. Подиновский В.В. Количественные оценки важности критериев в многокритериальной оптимизации. // НТИ. сер. 2. Информ. процессы и системы, 1999. №5. С. 22-25.

40. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1982.

41. Поляк Б. Т. Введение в оптимизацию. М.: Наука, 1983.

42. Попов Н.М. Об аппроксимации множества Парето методом сверток // ВМК, 1982. №4. С. 35—41.

43. Смирнов М.М. Методы аппроксимации граней множества Парето в линейной многокритериальной задаче // Вестн. МГУ. Вычисл. ма-тем. и киберн. 1996. № 3. С. 37-43.

44. Смирнов М.М. О логической свертке вектора критериев в задаче аппроксимации множества Парето // Ж. вычисл. матем. и матем. физ. 1996. Т.36. № 5. С. 62-74.

45. Смирнов М.М. Метод обратной логической свертки в задачах векторной оптимизации. М.: ВЦ РАН, 1996.

46. Смирнов М.М. Методы аппроксимации множества Парето, основанные на обратной логической свертке, и их использование в сетевой оптимизации: Автореф. дис. канд. физ.-матем. наук. М.: МГУ, ф.ВМиК, 1996.

47. Субботин А.И., Ченцов А.Г. Оптимизация гарантий в задачах управления. М.: Наука, 1983.

48. Сухарев А.Г., Тимохов A.B., Федоров В.В. Курс методов оптимизации. М.: Наука, 1986.

49. Федоров В.В. Численные методы максимина. М.: Наука, 1979.

50. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. М.: Мир, 1984.

51. Форд Д., Фалкерсон Д. Потоки в сетях. М.: Мир, 1966.

52. Штоер Р. Многокритериальная оптимизация. Теория, вычисления и приложения. М.: Радио и связь, 1992.

53. Blackwell D. An analog of the minimax theorem for vector payoffs // Pac. J. of Math. 6. 1956. P. 1-8

54. Chames A., Cooper W. W. Management models and industrial applications of linear programming I. Appendix B: Basic existence theorem and goal programming. Wiley, New York, 1961. P. 299—310.

55. Danskin J.M. The theory of max-min and its applications // SI AM J. on Applied Math. 1966. V.14. P. 641-664.

56. Ecker J.G., Hegner N.S., Kouada I.A. Generating all maximal efficient faces for multiple objective linear programs // J. of Optim. Theory and Appl. 1980. V. 30. №3. P. 353—381.

57. Jentzsch G. Some thoughts on the theory of cooperative games // Advances in game theory. Ann. Math. Studies. 1964. V.52. P. 407-442.

58. Matula D. W. Concurrent flow and concurrent connectivity in graphs // Graph Theory and Its Appl. to Algorithms and Comput. Sci. N.Y.: Wiley-Intersci., 1985.

59. Philip J. Algorithms for the vector maximization problem // Math. Prog. 1972. V. 2. №2. P. 207—229.

60. Robinson S.M. Stability theory for systems of inequalities, Part I: Linear systems // SIAM J. of Numerical Analisys. 1975. V.12. P. 754-769.

61. Zhukovskiy V.I., Salukvadze M.E. The vector-valued maximin. N.Y.: Academic Press, 1994.

62. Yu P.L., Zeleny M. The set of all nondominated solutions in linear cases and a multicriteria simplex method // J. Mathematical Analysis and Applications. 1975. V. 49. №2. P. 430—468.

63. Multiple criteria and game problems under uncertainty. 3-th Intern. Workshop. Orekhovo-Zuevo, Orekhovo-Zuevo Pedagogical Institute, 1994.

64. Multiple criteria and game problems under uncertainty. 4-th Intern. Workshop. Moscow, Russian Correspondence Institute of Textile and Light Industry, 1996.

65. Новикова H.M., Поспелова И.И. Векторный максиминимакс // Вестн. Моск. ун-та. Сер.15, Вычисл. матем. и киберн. 1999. № 4. С. 33-36.

66. Новикова Н.М., Поспелова И.И. Многокритериальные задачи принятия решений в условиях неопределенности. М.: ВЦ РАН, 2000. 64 с.

67. Новикова Н.М., Поспелова И.И. Параметризация значения векторного максиминимакса с помощью обратной логической свертки // Вестн. Моск. ун-та. Сер.15, Вычисл. матем. и киберн. 2000. № 3.

68. Поспелова И.И. Классификация задач векторной оптимизации с неопределенными факторами // Ж. вычисл. матем. и матем. физ. 2000. Т.40. № 6.

69. Новикова Н.М., Поспелова И.И., Семовская A.C. Кратный векторный минимакс // Ж. вычисл. матем. и матем. физ. 2000. (в печати)

70. Поспелова И.И. Векторный минимакс с позиций разных сторон. Прикладная математика и информатика №4, М.: Диалог-МГУ, 2000. (в печати)