автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.02, диссертация на тему:Исследование многокритериальных задач наилучшего выбора

ВВЕДЕНИЕ

1. ОДНОКРИТЕРИАЛЬНЫЕ ЗАДАЧИ НАИЛУЧШЕГО ВЫБОРА

1.1. Введение.

1.2. Задачи с различной априорной информацией об оценках.J

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. Остановка на парето-оптимальном варианте

3.5. Остановка на недоминируемом варианте

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

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

Исходной для рассматриваемого круга задач послужила классическая задача наилучшего выбора, формулируемая следующим образом. Предположим, что имеется N вариантов, сравниваемых друг с другом по какому-то критерию, из которых требуется выбрать всего один вариант. Ознакомление с вариантами производится в случайном порядке, а на процесс выбора наложены такие ограничения: в каждый момент может быть выбран только непосредственно наблюдаемый вариант, и ничего не известно о том, каковы последующие варианты. Требуется так остановить процесс выбора, чтобы выбранный вариант с максимальной вероятностью оказался наилучшим среди всех вариантов.

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

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

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

Коротко изложим содержание работы.

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

Во второй главе рассматриваются многокритериальные ранговые задачи, постановка которых предложена Стадье [8l] . Предполагается, что N обследуемых в случайном порядке вариантов сравниваются по т. независимым критериям. При обследовании очередного варианта становится известным вектор его относительных рангов, который содержит вместе с предыдущими относительными рангами всю информацию о результатах сравнения уже обследованных вариантов. Потери предполагаются заданными монотонной функцией вектора абсолютных рангов выбранного варианта. Требуется минимизировать средние потери по классу правил остановки последовательности наблюдений векторных относительных рангов.

Основные полученные результаты обобщают относящиеся к случаю одного критерия результаты Муцци [56,5?] , Лдианини и Саму-эльса [41,42] . При цена продолжения (решение уравнения обратной индукции) аппроксимируется решением определенного дифференциального уравнения, которое является ценой продолжения в предельной задаче оптимальной остановки с непрерывным временем. Предельная задача естественно интерпретируется как задача наилучшего выбора с бесконечным числом вариантов. Неожиданной оказывается форма предельной задачи, выражающая асимптотический эффект "расслоения" множества вариантов на in групп вариантов с "конечным" рангом по одному из критериев и "бесконечно большими" рангами по остальным критериям.

В третьей главе изучаются задачи максимизации вероятности остановки на лучшем варианте, которые включают некоторые известные постановки Джилберта и Мостеллера [44] , Гусейна-Заде [14] Березовского, Генинсона и Рубчинского [б] , Стадье [во] и автора [12] . Предполагается, что множество лучших вариантов определяется посредством заданной функции выбора, и за критерий эффективности правил остановки принимается вероятность остановки на одном из лучших вариантов. Решается в определенном смысле обратная с точки зрения теории оптимальной остановки задача: задавшись пороговыми правилами остановки вида "пропустить фиксированное число вариантов, и затем остановиться на первом же относительно лучшем варианте", мы находим класс функций выбора, для которых указанные правила оказываются достаточно эффективными. Показано, что в двухкритериальной задаче остановки на па-рето-оптимальном варианте (изучавшейся ранее в работе [б] ) класс пороговых правил является асимптотически оптимальным, причем предельное значение его эффективности равно единице. Исследуется задача оптимальной остановки на недоминируемом варианте с полной информацией, когда функция распределения вектора критериальных оценок считается известной.

В заключении приводятся выводы.

Диссертация выполнена в соответствии с плановой работой Института проблем управления (номер государственной регистрации 01828052892). Результаты работы использовались для решения задачи выбора плана технической подготовки производства новой модели автомобиля на Волжском автомобильном заводе.

Результаты автора, составляющие основное содержание диссертации, опубликованы в работах Гб-10,12, 1з]] .

ЗАКЛЮЧЕНИЕ

Перечислим основные результаты диссертации.

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

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

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

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

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

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

7. Получена нижняя оценка эффективности пороговых правил остановки для функций выбора, обладающих свойствами наследования и отбрасывания.

8. Для случая двух независимых критериев доказана асимптотическая оптимальность пороговых правил в задаче остановки на парето-оптимальном варианте. Приведены асимптотически оптимальные правила остановки и в случае большего числа критериев.

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

1. Айзерман М.А., Малишевский А.В. Некоторые аспекты общей теории выбора лучших вариантов: Щ)епр. Ин-та проблем управления АН СССР. М., 1980.,

2. Аркин В.И, Пресман Э.Л., Сонин И.М. Оптимальный выбор в условиях неполноты информации. Экономика и матем. методы, 1975, т. II, 3.

3. Барндорф-Нильсон 0., Соболь М. О распределении числа элементов многомерной выборки, принадлежащих заданному слою. Теория вероятностей и ее применения, 1966, т. II, Ik 2.

4. Березовский Б.А., Борзенко В.И., Кемпнер Л.М. Бинарные отношения в многокритериальной оптимизации. М.: Наука, I98I.

5. Березовский Б.А., Генинсон Б.А., Рубчинский А.А. Задача об оптимальной остановке на частично упорядоченных объектах. Автоматика и телемеханика, 1980, II.

6. Березовский Б.А., Генинсон Б.А., Гнедин А.В. Многокритериальная задача о выборе наилучшего объекта. В кн.: Тезисы докладов 7111 Всесоюзного совещания по проблемам управления, ч.

7. Москва-Таллин: Ин-т проблем управления, 1980.

8. Березовский Б.А., Гнедин А.В. Теория выбора и задача об оптимальной остановке на лучшем объекте. Автоматика и телемеханика, I98I, W 9.

9. Березовский Б.А., Гнедин А.В. Задача наилучшего выбора. М.: Наука, 1984.

10. Березовский Б.А., Гнедин А.В. Оптимизация последовательного выбора. В кн.: Тезисы докладов конференции "Проблемы и методы принятия решений в организационных системах управления". Москва-Звенигород: ВНИИ системных исследований, I98I.

11. Блекуэлл Д., Гиршик М.А. Теория игр и статистических решений. М.: Изд-во иностр. лит., 1958.

12. Гнедин А.В. Многокритериальная задача об оптимальной остановке процесса выбора. Автоматика и телемеханика, I98I, 7.

13. Гнедин А.В. Эффективная остановка на парето-оптимальном варианте. Автоматика и телемеханика, 1983, U 3. 14. 1сейн-3аде С М Задача выбора и оптимальное правило остановки последовательности независимых испытаний. Теория вероятностей и ее применения, 1966, т. II, 1 3 15. Де Гроот М. Оптимальные статистические решения. М.: Мир, 1974.

14. Дынкин Е.Б. Оптимальный выбор момента остановки марковского процесса. ДАН СССР, 1963, т. 150, J 2.

15. Закс Ш. Теория статистических выводов. М.: Ш р 1975.

16. Кован Р., Забжик Е. Задача об оптимальном выборе, связанная с пуассоновским процессом. Теория вероятностей и ее применения, 1978, т. 23, 3.

17. Липцер Р.Ш., Ширяев А.Н. Статистика случайных процессов. М.: Наука, 1974.

18. Миркин Б.Г. Проблема группового выбора. М.: Наука, 1974.

19. Николаев М.Л. Об одном обобщении задачи наилучшего выбора. Теория вероятностей и ее применения, 1977, т. 22, J I.

20. Петровский И.Г. Лекции по теории обыкновенных дифференци21. Пресман Э.Л., Сонин И.М. Игровые задачи оптимальной остановки. Существование и единственность точек равновесия. В кн.: Вероятностные проблемы управления в экономике. М.: Наука, 1977.

22. Пресман Э.Л., Сонин И.М. Задача наилучшего выбора при случайном числе объектов. Теория вероятностей и ее примененЕЯ, 1972, т. 17, 4.

23. Пресман Э.Л,, Сонин И.М. Точки равновесия в обобщенной игровой задаче наилучшего выбора. Теория вероятностей и ее применения, 1975, т. 20, J 4. 26.,Роббинс Г., Сигмунд Д., Чао И. Теория оптимальных правил остановки. М.: Наука, 1977.

24. Сонин И.М. Игровые задачи, связанные с наилучшим выбором, Кибернетика, 1976, 1 2.

25. Справочник по специальным функциям. М.: Наука, 1979.

26. Ширяев А.Н. Статистический последовательный анализ. М.: Наука, 1969.

27. Abdel-Hamid A,E., Bather J.A., Trustrum G.B., The secretary problem with an unknown number of candidates. J. Appl. Probab., 1982, vol. 19, N 3, p. 619-630.

28. Bartoszynski R., Govindarayjulu Z. The secretary problem with interview cost. Sankhya ser. B40, 1978, N 1-2, p.11-28.

29. Bojdecki T. On optimal stopping of a sequence of independent random variables probability maximizing approach. Stochast. Proc. Appl., 1978, vol. 6, H 2, p. 153-163. 33» Campbell G. The maximum of a sequence with prior information. Purdue Univ. Dep. Statist. Mimeograph Ser., 1977, N 485.

30. Campbell G. The secretary problem with the Dirichlet process. Inst. Math. Statist. Bull., 1978, vol. 7, p. 290 (abstr.). 35» Campbell G. Samuels S. Choosing the best of the current crop. Adv. Appl. Probab., I98I, vol. I3, N 3, p. 510-532.

31. Chow y.S., Moriguti S., Bobbins H., Samuels S. Optimum selection based on relative rank (the "secretary problems"). Isr, J. Math., 1964, vol. 2, N 1, p. 81-90. 37» Ciesielski Z., Zabczyk J. A note on a selection problem. Probab. theory. Banach Center Publ,, 1979, vol. 5, P.47-51.

32. Gorbin R. The secretary problem as a model of choice. J. Math. Psychol., I98O, vol. 1, N 1, p. 1-29. 39» Frank A., Samuels S. On an optimal stopping problem of Gusein-Zade. Stochast. Process and Appl., 1980, vol. 10, N 3, p. 299-311.

33. Gaver D.P. Random record models. J. Appli Probab., I976, vol. 13, N 3, p. 5З8-547. 41, Gianini J. The infinite secretary problem as the limit of the finite problem. Ann. Probab., 1977, vol. 5, N 4, p. 636-644.

34. Gianini-Pettitt J, Optimal selection based on relative ranks with a random number of individuals. Adv. in Appl, Probab., 1979, V. 11, pp. 720-736.

35. Gilbert J., Mosteller F. Recognizing the maximum of a sequence. J. Amer. Stat. Assoc, 1966, vol. 61, N 313, p. 35-73.

36. Glasser K. The d-choice secretary problem. Center for Naval Analyses. Professional paper N 253, 1979»

37. Grant P. Secretary problems with inspection cost as a game. Metrica, 1982, vol. 29, N 2, p. 87-93.

38. Haggstrom G. Optimal sequential procedures when more than one stop is required. Ann Math. Stat., 1967, v. 38, N 6.

39. Henke M. Expectations and variances of stopping variables in sequential selection processes. J, Appl. Probab., 1973, v. 10, N 4, p. 786-806.

40. Henke M. Sequentialle Auhswahl probleme bei Unsicherheit, Meisenheim: Anton Hain Verlag, 1970.

41. Irle A. On the best choice problem with random population size. Z. Oper. Res., I98O, v. A24, N 5, p. 177-190.

42. Kurano M., Yasuda M., Nakagami J, Multi-variate stopping problem with a majority rule. J. Oper. Res. Soc. Jap., 1980, V, 23, N 3, p. 205-223.

43. Lindley D. Dynamic programming and decision theory. Appl. Stat., 1961, V. 10, N 1, p. 39-52.

44. Lorentzen T, Towards a more realistic formulation of the secretary problem. Purdue Univ. Department of Stat.Mimeograph series, N. 427, 1977»

45. Mucci A, Differential equations and optimal choice problems. Ann, Statist., 1973, vol. 1, N 1, p. 104-113.

46. Mucci A. On a class of secretaiy problems. Ann. Probab., 1973, vol. 1, Ж 3, p. 417-427.

47. Petrucelli J. On the best-choice problem when the number of observations is random. J. Appl. Probab., 1983, vol, 20, N 3, p. 165-171.

48. Petrucelli J. On a bestschoice problem with partial information. Ann. Statist., 1980, vol. 8, p. II7I-II74.

49. Petruccelli J. Pull=information best=choice problems with recall of observations and uncertainty of selection depending on the observation. Adv. Appl. Probab,, 1982, vol. 14, N 2.

50. Petruccelli J. Best=choice problems involving uncertainty of selection and recall of observations. J. Appl. Probab,, 1981, vol. 18, N 2.

51. Platen E. About secretary problems. Banach Center Publ., 1980, vol. 6, p. 257-266. 63» Platen E. Sequentielle Rangauhswaklproblemeeine Erweiterung des "Secretary problems". Z. Angev/. Math. Mech., 1977, vol. 31, p. 31\-377. 64, Rasmussen W. A generalized choice problem, J. Optim. Theory and Appl., 1975, vol, 15, N 3, p. 311-325.

52. Rasmussen W., Pliska S. Choosing the maximim from a sequence with a discount function. Appl. Math, and Optim., 1976, vol. 2, p. 279-289.

53. Rasmussen W,, Bobbins H. The candidate problem vdth unknown population size. J, Appl. Probab., 1975, vol. 12, N 4, p. 692-701.

54. Rubin H. The "secretary" problem. -Ann. Math. Statist., 1966, vol. 37, N 2, p. 544 (abstr.).

55. Rubin H., Samuels S. The finite=memory secretary problem, Ann. Probab., 1977, vol. 5, N 4, p. 627-635.

56. Sakaguchi M. Dowry problems and OLA policies, Repts Statist, Appl. Res. Union Jap. Sci. and Eng., 1978, vol, 25, p. 124-128

57. Sakaguchi M. A note on the dowry problem, Rept. Stat. Appl. Res. JTJSE, 1973, v. 20, N 1, p. 11-17,

58. Sakaguchi M. A generalized secretary problem with uncertain employment. -Math. Jap., 1978, v. 23, p. 647-653.

59. Sakaguchi M. Non-zero-sum games related to the secretary problem. J. Oper Res. Soc. Jap., 1980, v. 23, N 3, p.287293.

60. Sakaguchi M, Optimal stopping problems for randomly arriving offers. Math. Jap., 1976, v. 21, p. 201-217.

61. Sakaguchi M., Tamaki M. Optimal stopping problems associated with a nonhomogeneous Markov process. Math. Lap., 1980, V. 25, N 6,

62. Samuels S. On explicit formula for limiting optimal success probability in the full information best-choice problem, Purdue Univ. Department Stat. Mimeograph series, 1980,

63. Samuels S. Minimax stopping rules when the underlying distribution is uniform, J. Amer. Stat, Assoc, 1981, v, 76, p, 188-197.

64. Schmitz I. Minimax strategies for discounted "secretary prob- lems". Oper.Res.-Verfahren, 1980, v. 30, N 1, p. 77-86.

65. Sierocinski A. On the optimal choice from a sample drawn from a known distribution. Demonstratio Math., I98I,

66. Tamaki M. Recognizing both the maximum and the second maximum of a sequence, J. Appl. Probab,, 1979, vol, 16, N 4, p. 803 812. 85* Tamaki M, OLA policy and the best=choice problem with random number of objects, Math, Jap., 1979, vol, 24, p. 451-457.

67. Tamaki M, A secretary problem with double choices. J, Oper, Res, Soc, Jap., 1979, vol. 22, p. 257-265.

68. Tamaki M. A secretary problem with ucertain employment when backward solicitation is permitted. Math. Jap,, 1979, vol. 24, p, 439-50.

69. Vanderbey R. The optimal choice of a subset of population. Math. Oper, Res,, I98O, vol. 5, N 4.

70. Yang M. Recognizing the maximum of a random sequence based on relative rank with backward solicitation. J. Appl, Probab., 1974, vol. 11, N 3, p. 504-512.

71. Zabczyk J. A selection problem associated to a renewal process. Lect. Notes Oontr. Inform. Sci., 1977, v. 2, p.508-515.