книги / Математические методы в системах поддержки принятия решений

/

На рис. 7, в представлена геометрическая интерпретация этой функции. Видно, что искомое значение р(2) > 0 определяется из условия пересечения, например, /j(p) и /2(р)

301

Выпуклая оболочка L(3c<2)) представляет собой симплекс, натянутый на концы векторов (-1,1), (-1 ,-2 ) и (2,0). При этом необходимое условие для минимаксной стратегии вы­ полнено: 0 е L(xP>) (см. рис. 7, г). Учитывая, что функции / ( Зс), / = 1, 2, 3. выпуклые, по­ следнее условие является и достаточным для оптимальности решения JC<2\

Задача 2. В условиях задачи 1 рассмотрим другое множество допустимых альтернатив М0 = {дс|, х2 е Е 2,х \й 0}. Требуется найти такую альтернативу х *, чтобы выполнялось ус­ ловие

ф(**) = min m ax /}(*,,х2),* = (*, ,х2).

ДС€Л/01</^3

Р е ш е н и е . Эта задача является задачей поиска минимаксной стратегии при нали­ чии ограничений, ее решение начнем с задания начального приближения (3^°>).

Пусть Зс° (—1, —1). Далее действуем, как в задаче 1, получим приближение х*1) (-1/2, 0). Однако при поиске следующего приближения хР> ограничение задачи стано­ вится активным: нельзя выходить за пределы области А = {(хь x2)^j й 0}, значит, должно

Проверим выполнение в точке *<2' необходимого условия оптимальности для мини­ максных задач с ограничениями

Д £2))пЫГ(х<2>))*0,

где /Г*(5с<2)) — сопряженный конус к множеству А в точке Зс<2) (0, 0). На рис. 8 ЦхФ ) пред­ ставляется отрезком GH и

-ЛГV 2)) = {(*,, лг2): х2 = 0, х, £ 0};

видно, что пересечение Множеств не пусто.

302

Итак, в точке х® —(0, 0) выполнено необходимое условие оптимальности и оно для рассмотренной задачи является достаточным, так как функцииf,{xb х2), i = 1, 2, 3, выпук­ лы. Следовательно, стратегия х * = х<2' (0,0) является искомой — оптимальной.

Сравнивая полученный результат с результатом задачи 1, можно заметить, что нали­ чие ограничения привело в задаче 2 к увеличению минимакса с 1 до 2.

9.5. Решение минимаксной задачи как задачи математического программирования

Согласно известному [8] приему, решение негладкой минимаксной задачи может бьггь найдено при ее сведении к задаче математического программирования. Действительно, например, задача

найти решение х° = arg min max/ (дс),

хеЕ " 1

где/(я) — гладкие функции для каждого / е [1: т]9эквивалентна задаче

найти minxw+1, при ограничениях f ( x ) £ x m+l9 х, xm+l е £*+1.

Так, рассмотренная в п. 9.4 задача преобразуется к следующей.

Х|,Х2,хзб£3

чения х* + х§ - х3 £ 0, 2 - х х - 2х2 - х3 < 0, 2 - Х| + х2 —х3 £ 0 .

Р е ш е н и е . Это задача нелинейного программирования. Она удовлетворяет условию Слейтера [20]: отсутствуют ограничения равенства. Поэтому для отыскания реше­ ниях0 = (Х|°, х2°) запишем регулярную функцию Лагранжа:

А(х,, х2, х3, X,, Х2, Х3) - х3 + Х,(х,2 + х22 - *3)+

+ ^ ( 2 - х1- 2 х2 - х 3) + Х3(2 - Х| + х2 - х3) -» min

и согласно теореме Куна—Таккера составим систему, характеризующую стационарные точки — искомое решение:

| ^ . = 2 Х, х, - Х2 - Х 3 = 0, | ^ - = 2 Х2х2 - 2 Х2 + Х3 = 0, — = 1-Х, - Х 2 - Х 3 = 0,

Теперь воспользуемся принципиальной особенностью: для рассматриваемой мини­ максной задачи все сформированные относительно у$(х), / = 1, 2, 3, ограничения в точ­ ке х° = (Х|°, х2°, х3°) е Е? как оптимальном решении должны быть активными, т.е. в этой точке должно выполняться условие равенства значений функций /i(x°) = / 2(х°) = / 3(х°).

303

Это условие имело место и в градиентном методе, когдахе Р ; оно следует и из условий дополняющей нежесткости (*) при X, * О, Х2 * ^з * О- Поэтому для отыскания реше­ ния х° = (х,°, х2°, х3°) составим систему

х ,2 + х22 - x 3 = 2 - x l - 2 x 2 - x h 2 - х, + х2 - х3 = 2 - х, - 2х2 - х3,

из которой получаем, что (х,° = 1, х2° = 0); при этом х3° = 1, X, - 1/3, Х2 = 4/9, Х3 = 2/9.

Решим рассмотренную минимаксную задачу другими методами.

и необходимые условия оптимальности решения

i*=o, i*=o, » . а

ЙХ| Эх2 Эх3

В результате получим систему

С

Из третьего уравнения системы имеем

2—*i + х2 - х3= >/с,

из первого и третьего следует, что

1= — - — - ----------— - и JT|° = ±а,

(*1 - а)2 <—•*! - а)2

а из второго и третьего — находим х2° = ±Ь.

304

при таких вариантах решения проявляется свойство оптимальности — «слипание» функ­ ций /(х ), / = 1, 2, 3.

j = 1, 2,..., /я, но такие, чтобы множество й было выпуклым. На множестве С1определены те же функции/!,>2.Уз» что были выписаны в начале настоящего пункта. Рассматриваемая за­ дача очевидным образом преобразуется в задачу выпуклого программирования:

найти min х3 при ограничениях

Xj2 + х22 - х3 й 0, 2 - Х| - 2х 2 - х3 £ 0, 2 - Х| + х2 - х3 ^ 0, -Xj < 0, -х 2 £ 0.

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

найти minx3 при ограничениях

/|(^°>) + О /,(*«»), х - х<°>) 5 х3, / 2(х«» + (Э/2(х<0>), х - х<°>) S х3,

/з(х<°>) + (Э/3(0°)), х - х«») £ х3,

gj (*<0)) + (dg/x<% X - х<°>) £ О,j = 1, 2,..., т,

где Э/,(дг<0)), d/2(xW), Э/3(х«»), dg,(xЩ — субградиенты указанных функций в точке х<°>; они для рассматриваемых функции легко вычисляются, так как совпадают с градиентами .

Это задача линейного программирования; в условиях заданных исходных данных она записывается в виде:

Ее решение отыскивается симплекс-методом (п. 6.4 и 6.6), которое затем принимается в качестве очередного приближения х^1' к искомому решению. Приближение х*2) будет также решением задачи линейного программирования;

305

Литература

анализа и процедуры принятия решений. — М.: «Мир», 1976.

4.О р л о в с к и й С.А. Проблемы принятия решений при нечеткой исходной инфор­ мации. — М.: «Наука», 1981.

5.Н е г о й ц э К . Применение теории систем к проблемам управления. — М.: «Мир»,

1981.

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

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

П . Ф и ш б е р н П . Теория полезности для принятия решений. — М.: «Наука», 1978. 12. Ю д и н Д.Б. Вычислительные методы теории принятия решений. — М.: «Наука»,

1989.

13. К а т у л е в А.Н., М и х н о В.Н. Современный синтез критериев в задачах приня­ тия решений. — М.: «Радио и связь», 1992.

14. Ф и х т е н г о л ь ц Г.М. Курс дифференциального и интегрального исчисления:

В3-х т. Т. 1. — М.: Изд-во физ.-мат. лит., 1958.

15.Д е н н и с Д.Б. Математическое программирование и электрические цепи. М.: Изд-во иностр. лит., 1961.

16.Ш и л о в Г.Е. Математический анализ. — М.: «Наука», 1960.

17.Эл ь с г о л ьц Л.Э. Дифференциальные уравнения и вариационное исчисление. — М.: «Наука», 1969.

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

23.Р о к а ф е л л а р Р . Выпуклый анализ. — М.: «Мир», 1973.

24. З у х о в и ц к и й С.И., А в д е е в а Л.И. Линейное и выпуклое программирова­ ние. — М.: «Наука», 1967.

25.Б р а й с о н А., Хо Ю-Ши. Прикладная теория оптимального управления. — М.: «Мир», 1972.

26.Х о ф е р Э . , Л у н д е р ш т е д т Р . Численные методы оптимизации. — М.: «Маши­ ностроение», 1981.

307

29. А ф а н а с ь е в В.И., К о л м а н о в с к и й В.Б., Н о с о в В.Р. Математическая тео­ рия конструирования систем управления. — М.: «Высшая школа», 1998.

30. В ай с б о р д Э.М., Ж у к о в с к и й В.И. Введение в дифференциальные игры не­ скольких лиц и их приложения. — М.: «Сов. Радио», 1980.

31.И о ф ф е А.Д., Т и х о м и р о в В.М. Теория экстремальных задач. — М.: «Наука»,

1974.

32.К р о т о в В.Ф., Л а гош а Б.А., Л о б а н о в С.М. и др. Основы теории оптималь­ ного управления. — М.: «Высшая школа», 1990.

41.Современное состояние теории исследования операций / Под ред. Н.Н. Моисее­ ва. — М.: «Наука», 1979.

42.Е ф и м о в А.В. Математический анализ (специальные разделы) — М.: «Высшая школа», 1980.

М.: «Твема», 1996.

49.П о д и н о в с к и й В.В., Г а в р и л о в В.М. Оптимизация по последовательно при­ меняемым критериям. — М.: «Сов. Радио», 1975.

50.М у л е н Э. Кооперативное принятие решений: аксиомы и модели. — М.: «Мир»,

1991.

51.М о и с е е в Н.Н. Численные методы в теории оптимальных систем. — М.: «Нау­ ка», 1971.

52. Г н о е н с к и й Л.С., К а м е н с к и й Г.А., Э л ь с г о л ь ц Л.А. Математические ос­ новы теории управляемых систем. — М.: «Наука», 1969.

53.Б е л л м а н Р. Динамическое программирование. — М.: Изд-во иностр. лит., 1960.

54.К у д р я в ц е в Л.Д. Курс математического анализа. — М.: «Высшая школа», 1981.

55.М и д д л т о н Д. Введение в статистическую теорию связи. В 2-х т., М.: «Сов. Ра­ дио», 1962. Т. 2.

56.Ус А.А., К о с е н к о Г.Г. Последовательное правило выбора решения, основанное

58.В а л ь д А. Статистические решающие функции / / Позиционные игры. — М.: «Наука», 1967.

59.Х а р к е в и ч А.А. Борьба с помехами. — М.: «Наука», 1965.

60.У и л к с С. Математическая статистика. — М.: «Наука», 1967.

61.С о с у л и н Ю.Г. Теория обнаружения и оценивания стохастических сигналов. — М.: «Наука», 1978.

62.Р ы ж и к о в Ю.И. Управление запасами. — М.: «Наука», 1969.

308

64.Обнаружение радиосигналов / Под ред. А.А. Колосова. — М.: «Радио и связь»,

1989.

65.Б о л ь ш е е Л.Н., С м и р н о в Н.В. Таблицы математической статистики. — М.: «Наука», ФМЛ, 1983.

обеспечение безопасности: Прикладные задачи. Тверь, 2001.

75.А б у с е в Р.А. Групповая классификация. Решающие правила и их характеристи­ ки. Пермь, 1992.

76.Ж у к о в с к и й В.И. Кооперативные игры при неопределенности и их приложе­ ния. — М.: Эдиториал УРСС, 1999.

81.Л е в и н Б.Р. Теоретические основы статистической радиотехники: В 3 кн. — М.: «Сов. Радио», 1976. Кн 3.

82.Ф у Ф. Последовательные методы в распознавании образов и обучении машин. — М.: «Наука», 1971.

83. К о к с Д., Х и н к л и Д. Теоретическая статистика. — М.: «Мир», 1978.

84.Б о р о в к о в А.А. Математическая статистика. Оценка параметров, проверка ги­ потез. — М.: «Наука», 1984.

85.Н и к а й д о X., И с од а К. Заметка о бескоалиционных выпуклых играх / / Беско­ нечные антагонистичекие игры / Под ред. Н.Н. Воробьёва. — М.: Физматгиз, 1963.

86. П ш е н и ч н ы й Б.Н., Д а н и л и н Ю.М. Численные методы в экстремальных за­ дачах. — М.: «Наука», 1975.

91.Ми ел е А. Определение экстремумов криволинейных интегралов по теореме Грина / / Методы оптимизации с приложениями к механике космического полета. — М.: «Наука», 1963.

92.В у к о л о в Э.А., Е ф и м о в А.В., 3 е м с к о в В.Н. и др. Сборник задач по матема­ тике для втузов. — М.: «Наука», 1990. Ч. 4.

управления / / ЖВМ и МФ. 1962. №2.

309

98.Б а т и щ е в Д.И. Методы оптимального проектирования. — М.: «Радио и связь»,

1984.

99.Л от о в А.В. Введение в экономико-математическое моделирование. — М.: «Нау­ ка», 1984.

100.Современное состояние теории исследования операций. — М.: «Наука», 1979.

кладная статистика: В 3-х т. Т. 3 Классификация и снижение размерности. — М.: «Фи­ нансы и статистика», 1989.

106.К у ш н е р Г.Дж. Стохастическая устойчивость и управление. — М.: «Мир», 1969.

107.Г н е д е н к о Б.В. Курс теории вероятностей. — М.: «Наука», 1969.

ного анализа и их приложения. — М.: «Сов. Радио», 1962.

113.Л е в и н В.И. Бесконечнозначная логика в задачах кибернетики. — М.: «Радио и связь», 1982.

114.С а а т и Т. Принятие решений. Метод анализа иерархий. — М.: «Радио и связь»,

1993.

118.С т р а т о н о в и ч Р.Л. Условные марковские процессы и их применение в теории» оптимального управления. — М.: МГУ, 1966.

119.С т р а т о н о в и ч Р.Л. К теории оптимального управления. Достаточные коорди­ наты / / А и Т. 1962. т. 23, № 7.

124.К а т у л е в А.Н., М а л е в и н с к и й М.Ф. и др. Идентификация каналов передачи информации. — М.: «Радио и связь», 1996.

125.Л и Р. Оптимальные оценки, определение характеристик и управление. — М.: «Наука», 1966.

126.К е н д а л л М. Дж., С т ь ю а р т А. Статистические выводы и связи. — М.: «Нау­ ка», 1973.

127. Т у р б о в и ч И.Т. Об оптимальном методе опознания образов при взаимно­ коррелированных признаках / / Опознание образов. Теория передачи информации. — М.: «Наука», 1965.

310