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

На правах рукописи

□□3493321

ПОЛУШИНА Татьяна Владимировна

ОПТИМАЛЬНЫЕ ПОСЛЕДОВАТЕЛЬНЫЕ ПРОЦЕДУРЫ В ЗАДАЧЕ МНОГОКРАТНОГО НАИЛУЧШЕГО ВЫБОРА

Специальность: 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Казань-2010

1 1 МАР 2010

003493321

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования "Марийский государственный университет".

Научный руководитель: кандидат физико-математических наук

Софронов Георгий Юрьевич,

Официальные оппоненты: доктор физико-математических наук,

профессор

Володин Игорь Николаевич,

доктор технических наук, профессор

Галиев Шамиль Ибрагимович,

Ведущая организация: ФГОУ ВПО "Южный федеральный

университет"

Защита диссертации состоится "¿LQ.fi2010 года в 144)0

часов на заседании диссертационного совета Д 212.079.01 в Казанском государственном техническом университете им. А.Н.Туполева по адресу: 420111, г. Казань, ул. К.Маркса, д. 10, зал заседаний Ученого Совета. Автореферат диссертации размещен на сайте КГТУ им. А.Н.Туполева www.kai.ru "Ц" "мврсаХ' 2010 г.

С диссертацией можно ознакомиться в библиотеке Казанского государственного технического университета им. А.Н. Туполева. Автореферат разослан 2010 г.

Ученый секретарь диссертационного совета, доктор

физико-математических наук, профессор П.Г. Данилаев

Общая характеристика работы

Актуальность темы

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

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

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

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

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

Сформулируем задачу однократного наилучшего выбора. Пусть имеется N объектов, упорядоченных по качеству. Занумеруем объекты в таком порядке, как мы знакомимся с ними. Все объекты поступают в случайном порядке, то есть все ЛП перестановок равновероятны. В некоторый момент Ь известны сравнительные качества объектов а[, аг,..., о(, но ничего неизвестно о качестве остальных N — t объектов. После ознакомления с очередным объектом й( можно его либо принять (в этом случае выбор объекта сделан), либо отвергнуть и продолжить наблюдения (при этом вернуться к отвергнутому объекту невозможно). Необходимо найти оптимальную стратегию, обеспечивающую наибольшую вероятность выбора

лучшего объекта.

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

Подробные обзоры истории развития задачи наилучшего выбора и ее обобщений приводятся в работах Фергисона1, Самуельса2. Различные методологические подходы к решению классической задачи наилучшего выбора можно найти в книгах Роббинса, Сигмунда и Чао3, Березовского и Гнедина4, Ширяева5.

Дальнейшие исследования развивались в нескольких направлениях. Одно из них - выбор нескольких объектов. Николаев6 отказался от необходимости выбирать единственный объект и рассмотрел обобщение классической задачи — задачу многократного наилучшего выбора. При этом необходимо найти стратегию, максимизирующую вероятность выбора к, к > 2 лучших объектов. Продолженные Николаевым7 исследования задачи о многократной оптимальной остановке привели к решению более широкой задачи — задачи об оптимальной остановке случайной последовательности. Многократный выбор рассматривался в работах Ано8, Преатера9, Тамаки10, Вилсона11. Софронов и Полушина рассмотрели задачу наилучшего многократного выбора с заданным распределением для перестановок. Николаев, Софронов, Полушииа рассмотрели другое обобщение задачи многократного наилучшего выбора — задачу многократного наилучшего выбора с заданными раигами. В данной постановке требуется выбрать несколько объектов с заранее заданными рангами Г\,Г2,... ,Г£.

Другое обобщение задачи наилучшего выбора — выбор одного объекта из нескольких лучших, так как на практике может быть достаточно обладать вторым по качеству объектом, третьим по качеству и так далее. Гусейн-Заде12 решил задачу, в которой успехом считался выбор любого из I лучших

'Ferguson T.S. Who solved the secretary problem? // Stat.Sci. 1989. V.4. N 3. P. 282-289.

'Samuels M. Who solved the secretary problem? comment: Who will solve the secretary problem? // Stat.Sci. 1989. V. 4. N 3. P. 289-291.

3Роббинс Г., Сигмунд Д., Чао И. Теория оптимальных правил остановки. М.: Наука, 1977.

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

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

"Николаев МЛ. Об одном обобщении задачи наилучшего выбора Ц Теор. вер. и ее прим. 1977. Т. 22. В. 1.С. 191-194.

'Николаев М.Л. Оптимальные правила многократной остановки // Обоз, прикл. и пром. матем. 1998. Т. 5. В. 2. С. 309-348.

•Апо К. Multiple selection problem and ola stopping rule // Sci. Math.Jap. 2001. V. 51. N 1. P. 335-346.

'Preater J. On multiple choice secretary problems // Math.of Oper.Research. 1994. V. 19. N 3. P. 597-602.

'"Tamakj M. A generalized problem of the optimal selection and assignment // Oper.Reseach. 1986. V. 34. N 3. P. 486-493.

"Wilson J. Optimal choice and assignmentof the best m of n randomly arriving items // Stoch.Proc.and Appl. 1991. V. 39. P. 325-343.

пГусейн-Заде C.M, Задача выбора и оптимальное правило остановки последовательности независимых испытаний // Теор. вер. и ее прим. 1966. Т. 11. В. 3. С. 534-537.

объектов. В дальнейшем изучение этой постановки продолжали Кавай и Тамаки13, Порошински14, Сушвалко и Шайовски10.

В классической задаче наилучшего выбора предполагается, что объекты поступают один за другим в случайном порядке. Таким образом, все N\ возможных порядков появления объектов равновероятны. Этот случай принято называть случаем отсутствия информации. Если поступающие объекты обладают какой-то количественной характеристикой их качества (например, ценой), то рассматриваются поступающие случайные величины. Это задача об остановке случайной последовательности. В простейшем случае естественно считать, что поступающие объекты являются независимыми случайными величинами с равномерным распределением. В той ситуации, когда априорно или в результате некоторых предварительных исследований, стало известно, какому семейству распределений принадлежит распределение, поступающих объектов, но неизвестны параметры, задача называется задачей с частичной информацией. Когда наблюдателю точно известно распределение, в этом случае задача называется задачей с полной информацией. Бойдецки16 рассмотрел задачу оптимальной остановки последовательности случайных величин, имеющих пуассоновское распределение. К задачам с частичной информацией относятся работы Петручелли17. Случай полной информации рассматривается в статьях Неймана, Порошински и Шайовски18, Николаева и Софронова19. Софронов и Полушина рассматривали задачу наилучшего выбора с неравиовероятными перестановками. Позднее авторы обобщили эту задачу на случай многократного выбора.

Можно рассмотреть еще одно обобщение классической задачи. Пусть наблюдатель получает возможность возвращаться к просмотренным ранее объектам, но каждый пропущенный объект с некоторой вероятностью может быть уже недоступен. Такие задачи с памятью рассматривались в статьях Роуза20, Сайто21.

13Kawai М., ТашаЫ М. Choosing either the best or the second best when the number of applicants is random // Сотр. and Math, with Appl. 2003. V. 46. P. 1065-107.

"Porosinski Z. On optimal choosing of one of the k best objects // Stat, and Prob. Letters. 2003. V. 65. Р.419-Ч32.

ISSuchwalko A., Szajowski K. Non standard, no information secretary problems // Sci. Math. Jap. 2002. V. 56. P. 443~456.

leBojdecki T. On optimal stopping of a sequence of independent random variables - probability maximizing approach // Stoch. An. Int. J.of Prob. and Stoch.Proc. 1979. V. 3. N 1. P. 61 - 71.

"Petruccelli J. On a best choice problem with partial information // The Ann.of Stat. 1980. V. 8. N 5. P. 1171-1174.

18Neumann P., Porosinski Z., Szajowski K. On two person full-information best choice problem with imperfect observation // Game Theory and Appl. 1996. V. 2. P. 21-25.

1вНиколаев M.Jl., Софронов Г.Ю. Многократные оптимальные правила остановки для суммы независимых случайных величин // Дискретная математика. 2007. Т. 19. В. 4. С. 42-51.

20Rose J. Optimal sequential based on relative ranks with renewable call options // J.of the Am.Stat.Ass. 1984. V. 79. N 386. P. 430-435.

"Saito T. Optimal stopping problem with controlled recall // Prob. Eng. and Inf. Sci. 1998. V. 12. N 11. P. 91-108.

Кроме того, существуют и другие различные обобщения задачи наилучшего выбора: случайное число наблюдаемых объектов (Пресман и Сонин22), несколько наблюдателей (Гликман23), плата за наблюдения (Лоренсен21), задача, в которой максимизируется время обладания относительно лучшим объектом (Тамаки, Пирс, Шайовски20), задача о минимизации ожидаемого ранга (Чао, Моригути, Роббинс и Самуэльс26) и суммарного ожидаемого ранга (Николаев).

В настоящей работе исследуются обобщения задачи многократного наилучшего выбора — важного класса задач теории оптимальных правил многократной остановки. Для некоторых из исследуемых обобщений оптимальные правила получены в явном виде. Проблема состоит в том, что в отдельных случаях структура остановочных множеств существенным образом зависит от конкретной задачи (например, определенного набора рангов J"i,... ,rjt). В этой ситуации необходимо прибегнуть к прямым вычислениям. Непосредственные рекурсивные вычисления методом индукции назад приводят к значительным временным затратам. Для задач, в которых N велико, их применение крайне затруднительно. В то же время метод Монте-Карло не дает достаточной точности и устойчивости результатов. Для отыскания наборов, характеризующих структуру остановочных множеств, и цены игры в программном комплексе реализуется метод последовательной минимизации расстояния Кульбака-Лейблера. Используемый алгоритм позволяет оценить оптимальное правило и цену игры даже при незначительных объемах выборок.

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

Цель работы

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

"Прес.мал Э.Л., Сонин U.M. Задача наилучшего выбора при случайном числе объектов //' Теор. вер. и ее прим. 1972. Т. 17. В. 4. С. 695-706.

23GHckraan Н. A best-choice problem with multiple selectors // J.Appl.Prob. 2000. V. 37. P. 71S-735.

24Lorenzen T. Optima! stopping with sampling cost: the secretary problem // The Ann. of Prob. 1981. V. 9. N 1. P. 167-172.

25Tamaki M., Pearce C., Szajowski K. Multiple choice problems related to the duration of the secretary problem // RIMS Kokyuroku. 1998. V. 1068. P. 75-86.

29Chow Y.S., Moriguti S., Robbiris H., Samuels S. Optimal selection based on relative rank // Israel J.Math. 1964. V. 2. P. 81-90.

Методика исследований

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

Для реализации программного комплекса основным алгоритмическим языком был выбран объектно-ориентированный язык С++.

Научная новизна .

Основные результаты диссертации являются новыми и состоят в следующем:

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

2. Найдены оптимальные правила многократной остановки в задачах многократного наилучшего выбора с заданными рангами, Гусейн-Заде и в задаче с конечной памятью.

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

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

Теоретическая и практическая значимость

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

Достоверность результатов работы подтверждается

— математическими доказательствами, результатами моделирования и обработки данных;

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

Апробация работы

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

(1) Студенческой конференции МарГУ (г. Йошкар-Ола, 2005 г.);

(2) Девятых Вавиловских чтениях (г. Йошкар-Ола, 2005 г.);

(3) Международной конференции "Оптимальная остановка и стохастическое управление" (г. Петрозаводск, 2005 г.);

(4) Всероссийской школе-коллоквиуме по стохастическим методам (г. Йошкар-Ола, 2006 г.);

(5) Шестой молодежной школе-конференции "Лобачевские чтения — 2007" (г. Казань. 2007 г.);

(6) Пятнадцатой международной конференции ''Математика. Компьютер. Образование" (г. Дубна, 2008 г.);

(7) Седьмой молодежной школе-конференции "Лобачевские чтения — 2008" (г. Казань, 2008 г.);

(8) кафедральном семинаре "Теория оптимальных правил многократной остановки" при кафедре математического анализа и теории функций (рук. — проф. Николаев М.Л., доц. Софронов Г.Ю.).

Ряд исследований, приводимых в диссертационной работе, выполнялись в рамках проекта, поддержанного грантом Министерства образования и науки Российской Федерации "Развитие научного потенциала высшей школы" (проект 34173). Автор награжден именной стипендией Президента Республики Марий Эл.

Публикации По теме диссертации опубликовано 13 печатных работ. Из них — 5 статей в российских реферируемых журналах, входящих в список ВАК, 2 — в тезисах докладов всероссийских симпозиумов и конференций.'

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, списка литературы (94 наименования), приложения. Каждая глава разбита на параграфы. Работа проиллюстрирована 26 рисунками и изложена на 108 страницах.

Краткое содержание работы

Во введении обоснована актуальность темы исследования, приведены цели работы и обзор литературы, дано краткое описание результатов диссертации.

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

В параграфе 1.1 рассматривается применение обобщения задачи многократного наилучшего выбора к анализу поведения животных. Идея подхода основана на теории естественного отбора: эволюционный отбор проходят стереотипы поведения организмов, которые позволяют обеспечить максимальное воспроизводство себе подобных. Иначе говоря, максимизируется передаваемое из поколения в поколение число генов-носителей данного типа поведения. Некоторые типы поведения животных, то есть процесс принятия решений в условиях неполной информации, приводят к задаче оптимальной остановки. К их числу относится оптимальный выбор места питания и оптимальный выбор партнера для воспроизводства. При выборе места питания организм движется через последовательность "пищевых" пятен, — разделенных пространственно участков, характеризующихся разной концентрацией пищи, — и должен остановиться на одном из них. Чем лучше будет его выбор, тем выше шансы на выживание потомства.

Другая важная задача в исследованиях экологии поведения — это процесс

выбора партнера для воспроизводства. Животные обладают критериями оценки качества партнера с точки зрения его репродуктивной ценности по внешним признакам. В природе один из полов осуществляет выбор, сам процесс выбора осуществляется по схеме оптимальной остановки. В работах21,28 для решения указанных задач используется теория оптимальных правил остановки, но рассматривается случай, когда требуется выбрать один объект (партнера или место питания). Однако представители некоторых видов животных могут последовательно выбирать больше одного партнера для воспроизводства29 или места питания. Математическая модель однократного выбора предложена в работе Мазалова, Домбровского и Перрина30.

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

Из анализа работ экономистов31,32 и психологов33 следует, что лица, принимающие решения, склонны останавливаться слишком рано. Чтобы ослабить условия проведения психологических экспериментов, предложено рассмотреть возможность возвращаться назад на некоторое небольшое число шагов. Рассматриваемая постановка описывается задачей наилучшего выбора с конечной памятью.

Параграф .1.3 призван исследовать вопрос о том, какими свойствами должны обладать объекты, подвергающие статистическим исследованиям. Поскольку наблюдение генеральной совокупности объектов слишком затратно, то статистики исследуют выборочные совокупности, состоящие из небольшого числа объектов. Так в случае последовательного наблюдения

27Hutchinson J.M.C., lialupka К. Mate choice when males are in patches: optimal strategies and good rules of thumb // J. Theor. Biol. 2004. V. 231. P. 129-151.

28Real L. Search theory and mate choice, i. models of single sex-discrimination// Am. Nat. 1990. V. 136. P. 376-405.

29Gabor C., Halliday T. Sequential mate choice by multiply mating smooth newts: females become more choosy // Behav. Ecol. 1997. V. 8. P. 162-166.

30Мазалоа B.B., Домбровский Ю.А., Перрин H. Теория оптимальной остановки: приложения к экологии поведения // Обоз, прикл. и пром. матем., 1994. Т. 1. В. 6. С. 893-900.

31Неу J. Still searching // Jour, of econ.behav. and organ. 1987. V. 8. P. 137-144.

32Zwick R.( Rapoport A., Lo A., Muthukrishnan A. Consumer sequential search: not enough or too much? Ц Mark, scien. 2003. V. 22. P. 503-519.

33Bearden J. A new secretary problem with rank-based selection and cardinal payoffs // J .of Math.Psych. 2006. V. 50. P. 58-59.

объектов необходимо решить, какие объекты должны попасть в выборку. Например, в случае монографического наблюдения естественным является требование, чтобы исследуемый объект являлся бы "средним" по изучаемым свойствам. Для способа основного массива необходимо отбирать группу лучших или худших объектов из совокупности, упорядоченной по данному признаку. Наконец, в случае выборочного наблюдения в итоговую выборку должны быть включены, как лучшие, так и худшие объекты. Именно рассмотрение некоторых крайних возможных состояний позволит точно исследовать свойства исследуемой совокупности. С математической точки зрения, поскольку выбор объектов проходит в условиях неполной информации, это приводит к задаче наилучшего выбора с заданными рангами.

В следующем параграфе рассматривается обобщение изложенных задач на случай многократного выбора и математическая модель многократного выбора. Пусть имеется N объектов, которые определенным образом упорядочены по качеству, т.е. можно сказать, какой из них самый лучший, какой второй по качеству и т.д. Занумеруем объекты в том порядке, как мы знакомимся с ними. Объекты поступают к нам в случайном порядке, т.е. все N1 перестановок равновероятны. В момент £ нам известны сравнительные качества объектов а^аг, ■.., а^ но мы ничего не знаем о качестве остальных N — £ объектов. После ознакомления с а( мы можем его либо принять (и тогда выбор одного объекта сделан), либо отвергнуть и продолжить наблюдения (тогда вернуться к отвергнутому объекту невозможно). Требуется найти оптимальную стратегию, максимизирующую некоторую целевую функцию. Например, вероятность выбора к объектов, лучших по качеству, или вероятность выбора к объектов с заданными рангами.

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

Задача состоит в том, чтобы отыскать правило, которое позволило бы находить к объектов, отвечающих заданному условию с максимальной вероятностью.

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

Ключевое отличие классической задачи однократного наилучшего выбора от задачи многократного выбора заключается в том, что наблюдатель делает выбор один раз (рисунок 1). Необходимо найти оптимальную стратегию, обеспечивающую наибольшую вероятность выбора лучшего объекта.

Рис. 1. Задача однократного наилучшего выбора

Оптимальная стратегия имеет вид: существует номер к*у такой, что первые (к'у — 1) объектов следует пропустить, а затем остановиться на первом объекте, который лучше всех предыдущих.

В §2.2 изложены основные определения из теории многократной оптимальной остановки, а также подробно рассматривается классическая постановка задачи многократного наилучшего выбора.

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

Поясним структуру оптимальной стратегии на примере выбора двух объектов. Существует набор 7Г* = (7Г[,7г£), 1 < тг{ < тг^ < N такой, что:

• необходимо пропустить первые — 1 объектов, и затем остановиться на первом объекте, который лучше всех предыдущих, или на (ЛГ— 1)-ом объекте, если лучший объект не появился до момента N — 1;

• во второй раз мы останавливаемся на первом объекте, который лучше, чем все предыдущие или хуже, чем один (если просмотрены уже 7Г2 — 1 объектов), в противном случае И-ом объекте.

Параграф 2.3 преследует цель рассмотреть обобщение сформулированной задачи — задачи многократного наилучшего выбора с заданными рангами.

Пусть имеется N объектов, проранжированных по качеству. Все объекты поступают в случайном порядке, то есть все N1 перестановок равновероятны. В некоторый момент £ известны сравнительные качества объектов а,1,а.2,. ■. но ничего неизвестно о качестве остальных И—Ь объектов. После

ознакомления с очередным объектом а, можно его либо принять (в этом случае выбор одного объекта из к сделан), либо отвергнуть и продолжить наблюдения (при этом вернуться к отвергнутому объекту невозможно). Стратегию, обеспечивающую максимальную вероятность выбора к, к > 2 объектов с заданными рангами г1,...,г>, 1 < Г\ < ••• < < М, назовем оптимальной.

Дадим более формальное определение. Пусть (1)к = (¿ъ---Л-) — произвольная перестановка чисел т"1,г2,... Стратегию выбора т" = (т\*,... 1 < Т[ < < • ■ • < т£ < N назовем оптимальной, если

= supР< (J{aTl = lu...,Cr, = 1к} i = p;v,

W J

где t = (ti, ... ,Tfc). Рассматриваемая задача состоит в отыскании оптимальной стратегии т* = (т*,..., Для первой остановки имеем:

т" = min{mi : ymi 6 Г^,}, Ti = (riib ..., rliA'_v+1), (1)

Г1..С {l,...,e}n{l,...,rt-fc+l}1 s = l,...,N-k, rllW_fc+i = {1,2,...,JV - fc + l>,

где r^j — определяемое заранее остановочное множество.

Оптимальная стратегия находится из следующих соотношений. Чтобы определить вид т*, i = заметим, что наше решение остановиться

или нет в момент времени тщ зависит не только от значения ymt, но и от просмотренных до момента тп{ относительных рангов. Поэтому остановочное множество зависит от значений ymi, ymi+1,..., ут,-ь Тогда

т* = min{m; > m,-_i : ym, € Гг,т< (?/„„, Ут1+1, ■ ■ •, Ут-ОЬ (2)

Г,- = (r.-.j,..., rV_ft+i), = {1,2,..., N - к + г},

Г;,5 С {l,...,s}n{l,...,rA. - k + i}, s = г,. ,.,N -k + i - 1.

Наборы множеств Гь...,Г^ определяются индукцией назад. Следует заметить, что структура остановочных множеств существенным образом зависит от значений г\,.г¡¡, поэтому нахождение оптимальной стратегии в каждом конкретном случае представляет собой вполне обособленную задачу. Рассматриваются два примера — оптимальная стратегия для выбора к лучших объектов и оптимальная стратегия для выбора к худших объектов.

Параграф 2.4 посвящен обобщению задачи Гусейн-Заде на случай многократного выбора. В постановке, приведенной в работе Гусейн-Заде,

успешным считался выбор одного из I лучших объектов. Рассмотрим задачу наилучшего выбора к объектов из I лучших по качеству (к < I). В данном случае стратегия является оптимальной, если она максимизирует вероятность выбора к объектов нз I лучших по качеству. Задача наилучшего выбора состоит в нахождении оптимальной стратегии г*.

Показано, что оптимальная стратегия для данной задачи может быть описана следующим образом: существуют гг'1^ = (т}1', л^1',..., Я/.!'^). =

I (2) (2) (2) ч (1.\ , (*) (А') (ПК

(тг; 7г;_'а.+2), ..., тг ' = (я"! ',1Х\ тг) ') такие, что

• необходимо пропустить первые тг}1' — 1 объектои, затем остановиться на первом объекте, который лучше всех предыдущих, или па втором

(О 1 г

по качеству, если уже просмотрено 7г2 — 1, и так далее, пли на объекте.

который хуже, чем 1—к предыдущих, если мы уже просмотрели — 1, в противном случае па {И — к 4- 1)-ом объекте;

• во второй раз следует остановиться:

на первом объекте, который лучше всех предыдущих, если просмотрено тг|2^ — 1 объектов,

или объекте, который хуже ровно одного, если уже просмотрено т^2' -1 объектов,

так далее, или па объекте, который хуже, чем / — к + 1 предыдущих, (2) ,

если мы просмотрели щ_к+,2 ~ 1,

или в противном случае на (./V — к + 2)-ом объекте; и так далее,

• наконец, в к-ый раз останавливаемся:

на первом объекте, который лучше всех предыдущих, если просмотрено тг^ — 1 объектов,

или на объекте, который хуже ровно одного из предыдущих, если уже просмотрено тт^ — 1 объектов,

или на объекте, который хуже ровно двух объектов, если уже просмотрено тг^ — 1 объектов,

и так далее, или на объекте, который хуже, чем I — 1 предыдущих, если просмотрено — 1 объектов, в противном случае па Л^ом объекте.

Поясним стратегию на примере выбора двух объектов из трех лучших: существуют наборы х(1) = (тг^^, тг^1'), тг(2) = (я-{2), тг^) такие, что:

• для первой остановки:

необходимо пропустить первые я^1' - 1 объектов, затем остановиться на первом объекте, лучшем предыдущих, или на втором по качеству, если уже просмотрено — 1, в противном случае на (И — 1)-ом объекте;

• во второй раз останавливаемся: на первом объекте, который лучше всех предыдущих, если просмотрено 7г|2' — 1 объектов,

или на объекте, который хуже ровно одного из предыдущих, если уже просмотрено Ti*2 — 1 объектов,

или на объекте, который хуже ровно двух объектов, если уже (2)

просмотрено 7Г3 — 1 объектов, в противном случае на N-ом объекте.

В § 2.5 изложена задача многократного наилучшего выбора с конечной памятью М. Основным отличием данной постановки является то, что наблюдатель в момент t может выбрать не только объект, появившийся в этот момент, а любой объект, появившийся в момент s, s Е [t — M,t],

Определим А4. = Л (a), s = 1 , ...,/V — последовательность векторов. Перестановка чисел l,2,...,s соответствует относительному качеству объектов, просмотренных к моменту s. Обозначим qk(As) — номер элемента к в перестановке (1,2,..., s), к < s. Тогда оптимальное правило имеет вид:'

г,* = mir^m! : yqi(Ann) € I\mi}, П = (Ги,..., Ti^-t+i), Fi,s € {l},s= l,...,N-k, ri,w-fe+i = {1.2.....JV-fc + 1},

где Г^,- — определяемое заранее остановочное множество.

Чтобы определить вид т*, г = 2,..., к отметим, что решение остановиться в момент времени rrii зависит от значения целого набора векторов (Ль ..., AmJ. Таким образом,

т* = min{m; > тгц_1 : у^.) € Ъ.тХУчЧК,)* ■ • • .Уд'-ЧЧ-')^' Г,- = (ГУ)..., Ti.jv-fc+j), Vijt-k+i = {1,2.....N-k + i},

Г;,, С {1,2.....s}n{l,...,i}, з= 1,2.....iV — A; + г + 1.

Наборы множеств Г],..., 1\- определяются индукцией назад.

В шестом параграфе рассматривается задача многократного наилучшего выбора в случае неравновероятных перестановок. Ранее всюду полагалось, что объекты поступают в случайном порядке так, что все iV! перестановок равновероятны. Пусть известна априорная информация о поле перестановок. Заданы веса перестановок:

№

РМ =Prn, m = l,N\, ^pm = l.

т=1

Обозначим (г ь...,/л.) некоторую перестановку чисел 1.2, ...Д\ Стратегию выбора т* = (т{, ■ ■., тЦ). 1 ^ т( < т{ < ■ ■ ■ < ^ N. для которой

р| U W = ч) [

Чь-...¡о J

= sup Р И {Or, = ¿1, • ■ •, ап = П-} [ = Рд-.

.....1(.......и) J

назовем оптимальной.

Используя метод индукции назад, запишем общую формулу:

т* = mf{m, > m,_i : Z(m)i > (¿(,„),_bm,+i}> где Щт), выражается из соотношений:

= u(ni)i' li(ra), = Ет,-1 ma-xlZ^,),, u(m).+ l}'

Таким образом, выражение для т' дает общую структуру оптимальной последовательной процедуры выбора к объектов.

Третья глава посвящена численному решению поставленных задач. В § 3.1 приводятся прямые методы вычисления цены игры в классической задаче многократного наилучшего выбора, такие как индукция назад и метод Монте-Карло. Показано, что эти методы требуют значительных временных затрат и погрешности вычислений значительны.

Поэтому предложено находить искомые значения с помощью метода последовательной минимизации расстояний Кульбака-Лейблера. Во втором параграфе приводится подробное описание этого метода. Первоначальной задачей при использовании данного метода является связать задачу оценки параметра с некоторой задачей оптимизации. Для этого определим последовательность индикаторных функций {^{S(x)>-y}} иа % Для различных 7 € К. Пусть {¡(-,и)} — семейство функций распределения на X с действительным параметром и. Для некоторого и задача оптимизации связана с задачей оценки параметра

l{l) = Рu{S(X) > 7) = ]Г/№)>7}/(х,и) = Eu/{S(a')>-,}>

где Ри — вероятностная мера, 7 — некоторый параметр.

Метод состоит из двух шагов:

1. Обновление 7¿. Для фиксированного ut-1, пусть 7t — это (1 — р)-квантиль S(X) при и4-1- Оценкой % Для 71 является

7i = %i-„)wsl),

Рис. 2. Цена игры V для различных N для выбора двух лучших объектов.

Рис. 3. Цена игры V для различных N для выбора двух худших объектов.

где для случайной выборки ... из /(-;и<-1) Б^) является г-ой порядковой статистикой представления ¿'(Лл), •. •,

2. Обновление г^. Для фиксированных и щ есть решеиие задачи минимизации расстояния Кульбака-Лейблера,

тахБ(и) - тахЕи,.,/^^^.^ 1п/(X; и).

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

Таблица 1. Минимальная, максимальная, средняя цена игры V и стандартная ошибка для различных N.

N V тах V тт V станд.ошиб. СРи «ше

10 0.2960 0.2962 0.2959 0.0009 79.7438

20 0.2587 0.2589 0.2585 0.0007 133.7234

30 0.2573 0.2579 0.2571 0.0011 314.5612

40 0.2540 0.2546 0.2438 0.0014 597.4312

50 0.2520 0.2525 0.2517 0.0012 1121.6892

На рисунке 2 изображена цена игры в задаче выбора двух лучших объектов для N = 2,..., 50. На примере классической задачи многократного наилучшего выбора показано, что метод последовательной минимизации расстояния Кульбака-Лейблера находит решения эффективнее, чем метод индукции назад или метод Монте-Карло.

Предметом параграфа 3.3 является применение метода последовательной минимизации расстояния Кульбака-Лейблера к задаче многократного наилучшего выбора с заданными рангами. Рассматривается задача

оптимизации _

maxESfx, R).

16ДГ

где X = {i = (xi,.... xA.) : условия (1). (2) выполняются}. R = (Ль.... /?.%■) -случайная перестановка чисел 1,2,..., TV, 5(х) — несмещенная оценка Я),

1 Nl

^^ = ж .....л^-iij.

71=1

(Дпь ..., R,in) — n-ая копия случайной перестановки R, (¿ь ..., гА.) — любая

из перестановок чисел 7"i, Гг.....

Пусть и = {ujji} — матрица параметров

utji=P{X,j = г}. i =

j = г,..., TV — fc + г - 1; I — 0,..., min{j, 7> — fc + г}.

Тогда

N-1 1=0

Следовательно,

t x), но)

= »=1 1{S(Xn)>w^-') _

, _ w((-i) . ' ~<t-i) ' ¿-,n=i J{S(x„)>7,r V; "¡Ai,

где Xn — [Xnij], Xnij случайная величина с плотностью f(Xij\ut-1).

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

Наконец, в четвертом и пятом параграфах изложенная выше схема применяется для задачи Гусейн-Заде в случае многократного выбора и в задаче с конечной памятью. Для всех рассмотренных постановок получены формулы вычисления, оценивается цена игры и моделируются остановочные множества. В качестве примера подробно рассмотрены задача выбора двух объектов из трех лучших и задача с конечной памятью. Оказалось, что в данных задачах остановочные множества также имеют пороговую структуру. Информация об этом существенно упрощает их применение и позволяет использовать простые наглядные правила остановки. Кроме того, из рисунков 4, 5 видно, что вклад памяти наиболее значим при небольших значениях N. Это связано с тем, что используемые при моделировании значения памяти М — 1,2,... невелики и мало отличаются

Рис. 4. Цена игры в задаче с памятью (М = 1)

Рис. 5. Цена игры в задаче с памятью {М — 2)

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

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

Положения, выносимые на защиту

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

2. Найдены оптимальные правила многократной остановки в задачах многократного наилучшего выбора с заданными рангами, Гусейн-Заде и в задаче с конечной памятью.

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

Список работ по теме диссертации

Научные статьи, опубликованные в изданиях, рекомендованных

1. Полушина Т.В., Софронов Г.Ю. Задача наилучшего выбора в случае иеравновероятных перестановок // Обозрение прикладной и промышленной математики. 2004. Т. 11. В. 3. С. 661-663.

2. Полушииа Т.В. Оптимальные двукратные правила остановки для задачи наилучшего выбора с неравновероятными перестановками // Обозрение прикладной и промышленной математики. 2005. Т. 12. В. 2. С. 449450.

3. Полушина Т.В. Оптимальная процедура в задаче последовательного выбора двух объектов с заданными рангами // Обозрение прикладной и промышленной математики. 2006. Т. 13. В. 4. С. 221-222.

4. Полушина Т.В. Оптимальная последовательная процедура в задаче выбора лучшего и худшего объектов // Обозрение прикладной и промышленной математики. 2007. Т. 14. В. 1. С. 77-78.

5. Полушина Т.В. Об одном обобщении задачи Гусейн-Заде // Обозрение

ВАК:

прикладной и промышленной математики. 2007. Т. 14. В. 2. С. 225-229.

Работы, опубликованные в других изданиях:

6. Polushina Т. V., Sofronov G.Yu. Optimal multiple stopping rules for the best choices problem with nonuniform permutations //In extended abstracts International Workshop " Optimal Stopping and Stochastic Control". Petrozavodsk, 2005. P. 58-59.

7. Полушина T.B. Оптимальная последовательная процедура в задаче многократного наилучшего выбора в случае циклических перестановок // Материалы конференции "Девятые Вавилонские чтения". Йошкар-Ола, 2005. Ч. 2. С. 359-361.

8. Николаев M.JI., Софронов Г.Ю., Полушина Т.В. Задача последовательного выбора нескольких объектов с заданными рангами. // Известия ВУЗов. Северо-Кавказский регион. Естественные науки. 2007. Т. 4. С. 11-15.

9. Полушина Т.В., Софронов Г.Ю. Об одном способе моделирования в задаче многократного наилучшего выбора с заданными рангами // Труды Математического центра им. Н.И. Лобачевского, 2007. Т. 36. С. 171-173.

10. Полушина Т.В. О применении задачи многократного наилучшего выбора в экологии поведения // Сборник научных трудов "Математика. Компьютер. Образование". Москва-Ижевск, 2008. Т.З. С.149-154.

11. Полушина Т.В. О моделировании в задаче многократного наилучшего выбора с минимальным ожидаемым суммарным рангом // Труды Математического центра им. Н.И. Лобачевского, 2008. Т. 37. С. 141-143.

12. Nikolaev M.L., Sofronov G.Yu., Polushina T.V. Multiple Best Choice Problems //In Proceedings of The Second International Workshop on Sequential Methodologies. Troyes, France, 2009. P. 1-6.

13. Polushina T.V. Estimating optimal stopping rules in the multiple best choice problem with minimal summarized rank via the cross-entropy method // In Proceedings of the Eleventh conference on Congress on Evolutionary Computation. Trondheim, Norway, 2009. P. 1668-1674.

Вклад автора в совместных публикациях. В работе [1] автору принадлежит построение оптимальной последовательной процедуры в задаче однократного наилучшего выбора на пространстве неравновероятных перестановок, в работе [6] — получение оптимального правила в задаче многократного наилучшего выбора в случае неравновероятных перестановок. Автор внес вклад в работу [8], получив оптимальные правила для некоторых определенных наборов рангов. В работе [9] автор разработал программу, позволяющую методами математического моделирования проводить вычисления для указанной задачи. Автору принадлежит рассмотрение задачи Гусейн-Заде в случае многократного выбора, изложенное в [12].

Автор выражает глубокую благодарность профессору Михаилу Леонидовичу Николаеву за постоянное внимание к работе и полезные обсуждения результатов.

Лицензия ИД№ 6434 от 10 декабря 2001 г.

Подписано в печать 19.02.2010г. Формат 60x84/16. Усл. печ. л. 1,0. Тираж 100. Заказ № 3906.

Отпечатано в ООП ГОУВПО «Марийский государственный университет» 424001, г. Йошкар-Ола, пл. Ленина, 1.

Введение

1 Математические модели задач последовательного выбора

1.1 Последовательный выбор в задачах экологии поведения

1.2 Выбор объектов в экономических задачах.

1.3 Нахождение объектов выборочной совокупности

1.4 Математическая модель многократного выбора

2 Теория задач наилучшего выбора

2.1 Выбор лучшего объекта.

2.2 Многократный выбор

2.3 Последовательный выбор нескольких объектов с заданными рангами

2.4 Задача Гусейн-Заде

2.5 Конечная память в задаче многократного наилучшего выбора.

2.6 Задача наилучшего выбора в случае неравновероятпых перестановок

3 Численные методы

3.1 Индукция назад

3.2 Метод последовательной минимизации расстояния Кульбака-Лейблера.

3.3 Выбор к объектов с заданными рангами.

3.4 Выбор двух объектов из трех лучших по качеству

3.5 Задача наилучшего выбора с конечной памятью

Общая характеристика работы

Актуальность темы

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

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

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

Так, например, животное, двигаясь в ареале обитания, последовательно выбирает наилучшее место питания [35, 83] или партнера для воспроизводства [42, 59]. Покупатель ищет продукт, наиболее соотвествующий его запросам, последовательно рассматривая различные предложения, или работодатель проводит собеседование для отыскания наилучшего кандидата па вакантную должность [31, 79, 82].

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

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

Сформулируем задачу однократного наилучшего выбора. Пусть имеется N объектов, упорядоченных по качеству. Занумеруем объекты в таком порядке, как мы знакомимся с ними. Все объекты поступают в случайном порядке, то есть все N1 перестановок равновероятны. В некоторый момент t известны сравнительные качества объектов ai, cío,. ■ ■ , a¿, но ничего неизвестно о качестве остальных N — t объектов. После ознакомления с очередным объектом a¿ можно его либо принять (в этом случае выбор объекта сделай), либо отвергнуть и продолжить наблюдения (при этом вернуться к отвергнутому объекту невозможно). Необходимо найти оптимальную стратегию, обеспечивающую наибольшую вероятность выбора лучшего объекта.

Оптимальная стратегия имеет вид: нужно пропустить к]у — 1 вариантов, а затем остановиться на первом же объекте, который окажется лучше всех предыдущих [44].

Подробные обзоры истории развития задачи наилучшего выбора и ее обобщений приводятся в работах Фримана [40, 411, Фергисона (39], Роббинса [71], Самуельса [78]. Различные методологические подходы к решению классической задачи наилучшего выбора можно найти в книгах Де Гроота [4], Дынкина и Юшкевича [5], Роббинса, Сигмунда и Чао |24], Мостеллера [9], Березовского и Гнедина [1], Ширяева [26, 27|.

Дальнейшие исследования развивались в нескольких направлениях. Одно из них - выбор нескольких объектов. Николаев [10] отказался от необходимости выбирать единственный объект и рассмотрел обобщение классической задачи — задачу многократного наилучшего выбора. При этом необходимо найти стратегию, максимизирующую вероятность выбора к, к > 2 лучших объектов. Продолженные Николаевым исследования привели к решению более широкой задачи — задачи об оптимальной остановке случайной последовательности [11]. Многократный выбор рассматривался в работах Николаева и Софронова, Ано, Преатера, Тамаки, Вилсона, Вандербрея (13, 29, 56, 68, 87, 90, 91]. Софропов и Полушина рассмотрели задачу наилучшего многократного выбора с заданным распределением для перестановок [64]. Николаев, Софронов, Полу шина рассмотрели другое обобщение задачи многократного наилучшего выбора — задачу многократного наилучшего выбора с заданными рангами [14]. В данной постановке требуется выбрать несколько объектов с заранее заданными рангами гх, г2, ■ . . , г к

Другое обобщение задачи наилучшего выбора — выбор одного объекта из нескольких лучших, так как на практике может быть достаточно обладать вторым по качеству объектом, третьим по качеству и так далее. Гуссйн-Заде решил задачу, в которой успехом считался выбор любого из I лучших объектов [3]. В дальнейшем изучение этой постановки продолжали Кавай и Тамаки, Порошински, Сушвалко и Шайовски [52, 66, 85, 88].

Пресман и Сонин [23] отказались от условия о том, что число объектов известно. В своей статье авторы предположили, что число наблюдаемых объектов случайно. Известно лишь распределение числа наблюдаемых объектов N. При этом оказалось, что структура оптимального правила значительно сложнее. Дальнейшее развитие данное обобщение получило в исследованиях Пстручелли, Лехтинсна, Порошински, Ясудзы [53, 61, 66, 93].

В классической задаче наилучшего выбора предполагается, что объекты поступают один за другим в случайном порядке. Таким образом, все АЛ возможных порядков появления объектов равновероятны. Этот случай принято называть случаем отсутствия информации. Если поступающие объекты обладают какой-то количественной характеристикой их качества (например, ценой), то рассматриваются поступающие случайные величины. Это задача об остановке случайной последовательности. В простейшем случае естественно считать, что поступающие объекты являются независимыми случайными величинами с равномерным распределением. В той ситуации, когда априорно или в результате некоторых предварительных исследований стало известно, какому семейству распределений принадлежит распределение, поступающих объектов, по неизвестны параметры, задача называется задачей с частичной информацией. Когда наблюдателю точно известно распределение, в этом случае задача называется задачей с полной информацией. Бойдецки рассмотрел за,дачу оптимальной остановки последовательности случайных величин, имеющих пуассоновское распределение [33]. К задачам с частичной информацией относятся работы [34, 61]. Случай полной информации рассматривается в статьях [57, 62, 67, 84]. Софронов и Полушина рассматривали задачу наилучшего выбора с неравновероятными перестановками [15]. Позднее авторы обобщили эту задачу на случай многократного выбора [64].

Можно рассмотреть еще одно обобщение классической задачи. Пусть наблюдатель получает возможность возвращаться к просмотренным ранее объектам, но каждый пропущенный объект с некоторой вероятностью может быть уже недоступен [92]. Такие задачи с памятью рассматривались в статьях Роуза, Рубенса и Самульэса., Сайто [73, 74, 77].

Кроме того, существуют и другие различные обобщения задачи наилучшего выбора: несколько наблюдателей (Гликман [45], Роуз [721, Шайовски [86]), ПЛЕТЯ 38 наблюдения (Лорепсен [55], Роуз [73]), задача, в которой максимизируется время обладания относительно лучшим объектом (Тамаки, Пирс, Шайовски [87]), задача о минимизации ожидаемого ранга (Чао, Моригути, Роббинс и Самуэльс [36], Хилл и Кеннеди [49], Джианини-Петитт [43]) и суммарного ожидаемого ранга (Николаев [11]).

В настоящей работе исследуются обобщения задачи многократного наилучшего выбора — важного класса задач теории оптимальных правил многократной остановки. Для некоторых из исследуемых обобщений оптимальные правила получены в явном виде. Проблема состоит в том, что в отдельных случаях структура остановочных множеств существенным образом зависит от конкретной задачи (например, определенного набора рангов ?'],.,'/>). В этой ситуации необходимо прибегнуть к прямым вычислениям. Непосредственные рекурсивные вычисления методом индукции назад приводят к значительным временным затратам. Для задач, в которых N велико, их применение крайне затруднительно. В то же время метод Монте-Карло не дает достаточной точности и устойчивости результатов. Для отыскания наборов, характеризующих структуру остановочных множеств, и цены игры в программном комплексе реализуется метод последовательной минимизации расстояния Кульбака-Лейблера. Используемый алгоритм позволяет оценить оптимальное правило и цену игры даже при незначительных объемах выборок.

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

Цель работы

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

Научная новизна

Основные результаты диссертации являются новыми и состоят в следующем:

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

2. Найдены оптимальные правила многократной остановки в задачах многократного наилучшего выбора с заданными рангами, Гусейн-Заде и в задаче с конечной памятью.

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

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

Методы исследования

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

Для реализации программного комплекса основным алгоритмическим языком был выбран объектно-ориентироваипый язык С+ + .

Теоретическая и практическая значимость

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

Достоверность результатов работы подтверждается

• математическими доказательствами, результатами моделирования и обработки данных:

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

Апробация работы

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

1) Студенческой конференции МарГУ (г. Йошкар-Ола, 2005 г.);

2) Девятых Вавиловских чтениях (г. Йошкар-Ола, 2005 г.);

3) Международной конференции "Оптимальная остановка и стохастическое управление" (г. Петрозаводск, 2005 г.);

4) Всероссийской школе-коллоквиуме по стохастическим методам (г. Йошкар-Ола, 2006 г.);

5) Шестой молодежной школе-конференции "Лобачевские чтения — 2007" ( г. Казань, 2007 г.);

6) Пятнадцатой международной конференции "Математика. Компьютер. Образование" (г. Дубна, 2008 г.);

7) Седьмой молодежной школе-конференции "Лобачевские чтения - 2008" ( г. Казань, 2008 г.);

8) кафедральном семинаре "Теория оптимальных правил многократной остановки" при кафедре математического анализа и теории функций Марийского государственного университета (рук. — проф. Николаев М.Л., доц. Софронов Г.Ю.).

Ряд исследований, приводимых в диссертационной работе, выполнялись в рамках проекта, поддержанного грантом Министерства образования и науки Российской Федерации "Развитие научного потенциала высшей школы" (проект 34173). Автор награжден именной стипендией Президента Республики Марий Эл.

Публикации По теме диссертации опубликовано 13 печатных работ. Из них - 5 статей в российских реферируемых журналах, входящих в список ВАК, 2 — в тезисах докладов всероссийских симпозиумов и конференций.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, списка литературы (94 наименования), приложения. Каждая глава разбита на параграфы. Работа проиллюстрирована 26 рисунками и изложена на 108 страницах.

Заключение

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

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

Положения, выносимые на защиту

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

2. Получены оптимальные правила многократной остановки в задачах многократного наилучшего выбора с заданными рангами, Гусейн-Заде и в задаче с конечной памятью.

3. Найдены формулы для вычисления цены игры методом последовательной минимизации расстояния Кульбака-Лейблера. Решение каждой из указанных постановок связано с рассмотрением отдельной задачи оптимизации и требует специального подхода.

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

2. Вальд А. Последовательный анализ. М.: Физматгиз, 1960.

3. Гусейн-Заде С.М. Задана выбора и оптимальное правило остановки последовательности независимых испытаний // Теор. вер. и ее прим. 1966. Т. 11, вып. 3. С. 534-537.

4. Де Гроот М. Оптимальны,е статистические решения. М.: Мир, 1974.

5. Дынкин Е.Б, Юшкевич A.A. Теоремы и задачи о процессах Маркова. М.: Наука, 1967.

6. Мазалов В.В., Фалько A.A. Задача наилучшего выбора и ее применение в рекламных кампаниях поисковой системы Яндекс // Материалы конкурса 'Интернет-Математика 2007. Яндекс1. 2007. С. 126-134.

7. Мостеллер Ф. Пятьдесят занимательных вероятностных задач с решениями. М.: Наука, 1975.

8. Николаев M.JI. Об одном обобщении задачи наилучшего выбора // Теор. вер. и ее прим. 1977. Т. 22, вып. 1. С. 191-194.

9. Николаев М.Л. Оптимальные правила многократной остановки // Обоз, прикл. и пром. лштем. 1998. Т. 5, вып. 2. С. 309-348.

10. Николаев М.Л., Софронов Г.Ю. Оптимальная последовательная процедура в задаче "купли-продажи" с детерминированным трендом // Обоз, прикл. и пром. матем,. 2005. Т. 12, вып. 1. С. 167-168.

11. Николаев М.Л., Софронов Г.Ю. Многократные оптимальные правила для суммы независимых случайных величин // Дискретная математика. 2007. Т. 19, вып. 4. С. 42-51.

12. Николаев М.Л., Софронов Г.Ю., Полушина Т.В. Задача последовательного выбора нескольких объектов с заданными рангами // Изв. ВУЗов. Сев.-Кав.регион. Ест.науки. 2007. Т.4. С. 11-14.

13. Полушина Т.В., Софронов Г.Ю. Задача наилучшего выбора в случае неравновероятных перестановок // Обоз, прикл. и пром. матем. 2004. Т. 11, вып. 3. С. 661-663.

14. Полушина Т.В. Оптимальные двукратные правила остановки для задачи наилучшего выбора с неравновероятными перестановками // Обоз, прикл. и пром. матем. 2005. Т. 12, вып. 2. С. 449-450.

15. Полушина Т.В. Оптимальная процедура в задаче последовательного выбора двух объектов с заданными рангами // Обоз, приклад, и пром. матем. 2006. Т. 13, вып. 4. С.221-222.

16. Полу шина Т.В. Оптимальная последовательная процедура в задаче выбора лучшего и худшего объектов // Обозрениеприкладной и промышленной математики 2007. Т. 14, вып. 1. С. 77-78.

17. Полушина Т.В. Об одном обобщении задачи Гусейн-Заде // Обоз, прикл. и пром. матем. 2007. Т. 14, вып. 2. С. 225-229.

18. Полушина Т.В., Софронов Г.Ю. Об одном способе моделирования в задаче многократного наилучшего выбора с заданными рангами // Труды Математического центра им. Н.И. Лобачевского. 2007. Т. 36. С. 171-173.

19. Полушина Т.В. О применении задачи многократного наилучшего выбора в экологии поведения // М.-Ижевск: Математика. Компьютер. Образование. Сборник научных трудов. 2008. Т. 3. С. 149-154.

20. Полушина Т.В. О моделировании в задаче многократного наилучшего выбора с минимальным ожидаемым суммарным рангом //Труды Математ'ического центра им,. Н.И. Лобачевского. 2008. Т. 37. С. 141-143.

21. Пресман Э.Л., Сонин И.М. Задача наилучшего выбора при случайном числе объектов // Тсор. вер. и ее прим. 1972. Т. 17, вып. 4. С. 695-706.

22. Роббинс Г., Сигмунд Д., Чао И. Теория оптимальных правил остановки. М.: Наука, 1977.

23. Софронов Г.Ю., Крузе Д., Киф Дж., Николаев М.Л. Об одном способе моделирования порогов в задаче многократного наилучшего выбора // Обозр. прикл. и промышл. математ. 2006. Т. 13, вып. 6. С. 975-983.

24. Ширяев A.PI. Статистический последовательный анализ. М.: Наука, 1976.

25. Ширяев А.Н. Вероятность. М.: Наука, 1989.

26. Amrhein V., Кипе Н., Naguib М. Non-territorial nightingales prospect territories during the dawn chorus // Proc.R.Soc.Lond B. 2004. V. 271. P. 167-169.

27. J29. Ano K. Multiple selection problem and ola stopping rule // Sci. Math. Jap. 2001. V. 53, N 2. P. 335-346.

28. Bakker T.C.M., Milinski M. Sequential female choice and the previous male effect in sticklebacks // Behav.Ecol.Sociobiol. 1991. V. 29. P. 205-210.

29. Bearden J. A new secretary problem with rank-based selection and, cardinal payoffs // J.of Math.Psych. 2006. V. 50. P. 58-59.

30. Bearden J., Murphy R., Rapoport A. Sequential observation and selection with rank-dependent payoffs: An experimental test // Manag. Sci. 2006. V. 52. P. 1437-1449.

31. Bojdecki T. On optimal stopping of a sequence of independent random variables probability maximizing approach // Stoch. An Int. J. of P'i'ob. and Stoch.Proc. 1979. V. 3 N 1. P. 61-71.

32. Campbell G., Samuels S. Choosing the best of the current crop // Adv.Appl.Prob. 1981. V. 13 N 3. P. 510-532.

33. Charnov E.L. Optimal foraging: the marginal value theorem // Theor.Popul.Biol. 1976. V. 9. P. 129-136.

34. Chow Y.S., Moriguti S., Robbins H., Samuels S. Optimal selection based on relative rank // Israel J.Math. 1964. V. 2. P. 81-90.

35. Dombrovsky Y., Perrin N. On adaptive search and optimal stopping mate choice //Am. Nat. V. 114. P. 355-361.

36. Dudey T., Todd P. Making good decisions with minimal information: simultaneous and sequenntial choice // Jour, of Bioecon. 2001. V. 3. P. 195-215.

37. Ferguson T.S. Who solved the secretary problem? // Stat.Sci. 1989. V. 4 N 3. P. 282-289.

38. Freeman P.R. The secretary problem and its extensions: a review // Int.Stat.review. 1983. V. 51, N 2. P. 189-206.

39. Freeman P.R. Who solved the secretary problem?: comment // Stat.Sci. 1989. V. 4, N 3. P. 294.

40. Gabor C., Halliday T. Sequential mate choice by multiply mating smooth newts: females become more choosy // Dehav. Ecol. 1997. V. 8. P. 162-166.

41. Gianini-Petitt J. Optimal selection based on relative ranks with a random number of individuals // Adv.Appl.Prob. 1979. V. 11. P. 720-736.

42. Gilbert J., Mosteller F. Recognizing the maximum of a sequence // J.of the Am.Stat.Ass. 1966. V. 61, N 313. P. 35-73.

43. Glickman H. A best-choice problem with multiple selectors // J.Appl.Prob. 2000. V. 37. P. 718-735.

44. Halliday T., Verrell P. Sperm competition and the evolution of animal mating systems, chapter Sperm competition in amphibians. New York: Academ Press, 1984. P. 487-508.

45. Hanski I., Gilpin M. Metapopulation Biology: Ecology, Genetics and Evolution. New York: Academic Press, 1999.

46. Hey J. Still searching // Jour, of econ.behav. and organ. 1987. V. 8. P. 137-144.

47. Hill T., Kennedy D. Minimax-optimal stragies for best-choice problem when a bound is known for the expected number of objects // Siam J. control and opt.im. 1994. V. 32, N 4. P. 937-951.

48. Hutchinson J.M.C., Halupka K. Mate choice when males are in patches: optimal strategies and good rules of thumb // J. Theor. Biol. 2004. V. 231. P. 129-151.

49. Janetos A. Strategies of female mate choice: a theoretical analysis // Behav.Ecol.Sociobiol. 1980. V. 7. P. 107-112.

50. Kawai M., Tamaki M. Choosing either the best or the second best when the number of applicants is random // Comp. a/nd Math, with Appl. 2003. V. 46. P. 1065-1071.

51. Lehtinen A. The best choice problem with an unknown number of objects // Math.Mcth. of Op.Res. 1993. V. 37, N 1. P. 97-106.54| Lippman S., McCall J. The economics of job search: a survey // Econ.Inq. 1976. V. 14. P. 155-189.

52. Lorenzen T. Optimal stopping with sampling cost: the secretary problem // The Ann. of Prob. 1981. V. 9, N 1. P. 167-172.

53. Mehrez A., Rabinowitz G. A note on the rule for sequential selection // Eur. J.of Oper.research. 1995. V. 81. P. 166-175.

54. Neumann P., Porosinski Z., Szajowski K. On two person full-information best choice problem with imperfect observation // Game Theory and Appl. 1996. P. 21-25.

55. Nikolaev M.L., Sofronov G.Yu., Polushina T.V. Multiple Best Choice Problems // Proceedings of The Second International Workshop on Sequential Methodologies. University of Technology of Troyes, Troyes, France. P. 1--6.

56. Parker G.A. Mate choice, chapter Mate quality and mating decisions. Cambridge: Cambridge University Press, 1983. P. 141-165.

57. Parker G.A. Sexual selection and reproductive competition in the insects, chapter Sexual selection and sexual confict. New York: Academic Press, 1979. P. 123-166.

58. Petruccelli J. On a best choice problem with partial information // The Ann.of Stat. 1980. V. 8, N 5. P. 1171-1174.

59. Petruccelli J. Full-information best-choice problems with recall of observations and uncertainty of selection depending on the observation // Adv.Appl.Prob. 1982. V. 14. P. 340-358.

60. Pitcher T.E., NeffB.D., Rodd F.H., Rowe L. Multiple mating and sequential mate choice in guppies: females trade up // Proc. R. Soc. Lond. B. 2003. V. 270. P. 1623-1629.

61. Polushina T.V., Sofronov G.Yu. Optimal multiple stopping rules for the best choice problem with nonuniform permutations // In Abstract of Workshop Optimal stopping and stochastic control. P. 5859. Petrozavodsk, 2005.

62. Porosinski Z. On optimal choosing of one of the k best objects // Stat, and Prob. Letters. 2003. V. 65. P. 419^432.

63. Porosinski Z., Szajowski K. Full-information best choice problem with random starting point // Math. J. 2000. V. 52. P. 57-63.

64. Preater J. On multiple choice secretary problems // Math.of Op-er.Research. 1994. V. 19, N 3. P. 597-602.

65. Real L. Search theory and mate choice, i. models of single sex-discrimination // Am. Nat. 1990. V. 136. P. 376 405.

66. Real L. Search theory and mate choice. II. mutual interaction, assortative mating, and equilibrium variation in male and female fitness // Am. Nat. 1991. V. 138. P. 901-917.

67. Robbins H. Who solved the secretary problem?: comment // Stat.Sci. 1989. V. 4, N 3. P. 291.

68. Rose J. Selection of nonextremal candidates from a random sequence // J. of Opt, Theory and Appl. 1982. V. 38, N 2. P. 207-219.

69. Rose J. Optimal sequential based on relative ranks with renewable call options // J. of the Am.Stat.Ass. 1984. V. 79, N 386. P. 430-435.

70. Rubin H., Samuels S.M. The finite-memory secretary problem // The Ann. of Prob. 1977. V. 5, N 4. P. 627-635.

71. Rubinstein R., Kroese D. Simulation and the Monte Carlo method. Wiley-Interscience, 2007.

72. Rubinstein R., Kroese D. The Cross-Entropy Method: A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation and Machine Learning. New York: Springer-Verlag, 2004.

73. Saito T. Optimal stopping problem with controlled recall // Prob. Eng and Inf. Sei. 1998. V. 12, N 11. P. 91-108.

74. Samuels M. Who solved the secretary problem? Who will solve the secretary problem? // Stat.Sei. 1989. V. 4 N 3. P. 289-291.

75. Seale D., Rapoport A. Sequential decision making with relative ranks: An experimental investigation of the 'secretary problem' // Organiz. Beh. and Human Decision Proc. 1997. V. 69. P. 221-236.

76. Smith M., Deely J. A secretary problem with finite memory // J. of the Am.Stat. Ass. 1975. V. 70, N 350. P. 357-361.

77. Sofronov G., Keith J.M., Kroese D.P. An Optimal Sequential Procedure for a Buying-Selling Problem with Independent Observations // J. Appl. Prob. 2006. V. 43. P. 454-462.

78. Stein W., Seale D., Rapoport A. Analysis of heuristic solutions to the best choice problem // Eur. J.of Op.Research. 2002. V. 151. P. 140-152.

79. Stephens D., Krebs J. Foraging theory. Princeton, N.J.: Princeton University Press, 1986.

80. Stewart T. The secretary problem with an unknown number of option // Oper.Res. 1981. V. 29, N 1. P. 130-145.

81. Suchwalko A,, Szajowski K. Non standard, no information secretary problems // Sei. Math. Jap. 2002. V. 56. P. 443-456.

82. Szajowski K. On stopping games when more than one stop is possible //In Probability Methods in Discrete Mathematics. Proc. of the Fifth Int. Petrozavodsk Conf. 2000. P. 57-72.

83. Tamaki M., Pearce C., Szajowski K. Multiple choice problems related to the duration of the secretary problem // RIMS Kokyuroku. 1998. V. 1068. P.75- 86.

84. Tamaki M., Shanthikumar J. A full-information best-choice problem with allowance // Prob. in the Eng. and Inf.Scien. 1996. V. 10. P. 41-56.

85. Uy J., Patricelli G., Borgin G. Complex mate searching in the satin bowerbird ptilonorhynchus violaceus // Am.Nat. 2001. V. 158. P. 530-542.

86. Vanderbrei R. The optimal choice of a subset of a population // Math.of Oper.Research. 1980. V. 5, N 4. P. 481-486.

87. Wilson J. Optimal choice and assignmentof the best m of n randomly arriving items // Stoch.Proc. and Appl. 1991. V. 39. P. 325-343.

88. Yang M. Recognizing the maximum of a random sequence based on relative rank with backward solicitation // J. of Appl.Prob. 1974. V. 11, N 3. P. 504-512.

89. Yasuda M. Asymptotic results for the best-choice problem with a random number of objects // J. Appl.Prob. 1984. V. 21. P. 521536.

90. Zwick R., Rapoport A., Lo A., Muthukrishnan A. Consumer sequential search: not enough or too much? // Mark, scien. 2003. V. 22. P. 503-519.