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

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2019
1. Verfasser:	Файнзильберг, Л.С.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2019
Schriftenreihe:	Управляющие системы и машины
Schlagworte:	Фундаментальные и прикладные проблемы Computer Science
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/161572
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Модифицированный метод оптимальной остановки в задаче последовательного анализа альтернатив / Л.С. Файнзильберг // Управляющие системы и машины. — 2019. — № 1. — С. 11-21. — Бібліогр.: 16 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-161572
record_format	dspace
spelling	irk-123456789-1615722019-12-15T01:25:40Z Модифицированный метод оптимальной остановки в задаче последовательного анализа альтернатив Файнзильберг, Л.С. Фундаментальные и прикладные проблемы Computer Science Предложен метод, обобщающий классическую постановку задачи оптимальной остановки принятия решений при последовательном просмотре ранжированных альтернатив в случайном порядке. Отличительная особенность метода состоит в том, что правильным считается решение о появлении претендента, который по некоторому критерию (суперкритерию) отличается от абсолютного лидера не более чем на заданную величину уступки. Ціль статті — дослідити можливості модифікованого методу оптимальної зупинки на основі статистичного експерименту. Методи. Статистичний експеримент, що пропонується, заснований на методі Монте-Карло і передбачає багаторазову генерацію масивів незалежних однаково розподілених випадкових величин, які імітують значення суперкритерію до альтернативи, за якою особа, що приймає рішення, спостерігає на поточному кроці. На основі серії багаторазових випробувань оцінюється ймовірність вибору претендента, який на задану величину поступки відрізняється від абсолютного лідера. Проводиться аналіз залежності ймовірності вірних рішень від величини поступки. Результат. Встановлено, що вже при значенні чотири відсотка поступки необхідний обсяг експериментальної вибірки для прийняття остаточного рішення знижується з 37 (класичний метод) до 15 відсотків. При цьому ймовірність прийняття правильного рішення збільшується і досягає P = 0,68 при поступці в 10 відсотків в порівнянні з ймовірністю правильного рішення P = 0,37, що досягається класичним методом. The purpose of the article is to explore the possibilities of a modified optimal stopping method based on a statistical experiment Methods. The statistical experiment is based on the Monte Carlo method and provides for the multiple generation of arrays of independent identically distributed random variables that mimic the values of the super criterion of the alternative, which the person observes at the current step. On the basis of a series of multiple tests, the probability of selecting an applicant, which differs by a given amount from the absolute leader, is estimated. The analysis of the dependence of the probability of correct decisions on the value of the assignment is done. Result. It has been established that already at a value of 4% assignment, the required amount of experimental sampling for making a final decision decreases from 37% (the classical method) to 15%. At the same time, the probability of right decision increases to P = 0,68 (when is concession of 10%) compared with the probability P = 0,37 of the right decision, achieved by the classical method. 2019 Article Модифицированный метод оптимальной остановки в задаче последовательного анализа альтернатив / Л.С. Файнзильберг // Управляющие системы и машины. — 2019. — № 1. — С. 11-21. — Бібліогр.: 16 назв. — рос. 0130-5395 DOI: https://doi.org/10.15407/usim.2019.01.011 http://dspace.nbuv.gov.ua/handle/123456789/161572 65.01:62-505 ru Управляющие системы и машины Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Фундаментальные и прикладные проблемы Computer Science Фундаментальные и прикладные проблемы Computer Science
spellingShingle	Фундаментальные и прикладные проблемы Computer Science Фундаментальные и прикладные проблемы Computer Science Файнзильберг, Л.С. Модифицированный метод оптимальной остановки в задаче последовательного анализа альтернатив Управляющие системы и машины
description	Предложен метод, обобщающий классическую постановку задачи оптимальной остановки принятия решений при последовательном просмотре ранжированных альтернатив в случайном порядке. Отличительная особенность метода состоит в том, что правильным считается решение о появлении претендента, который по некоторому критерию (суперкритерию) отличается от абсолютного лидера не более чем на заданную величину уступки.
format	Article
author	Файнзильберг, Л.С.
author_facet	Файнзильберг, Л.С.
author_sort	Файнзильберг, Л.С.
title	Модифицированный метод оптимальной остановки в задаче последовательного анализа альтернатив
title_short	Модифицированный метод оптимальной остановки в задаче последовательного анализа альтернатив
title_full	Модифицированный метод оптимальной остановки в задаче последовательного анализа альтернатив
title_fullStr	Модифицированный метод оптимальной остановки в задаче последовательного анализа альтернатив
title_full_unstemmed	Модифицированный метод оптимальной остановки в задаче последовательного анализа альтернатив
title_sort	модифицированный метод оптимальной остановки в задаче последовательного анализа альтернатив
publisher	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
publishDate	2019
topic_facet	Фундаментальные и прикладные проблемы Computer Science
url	http://dspace.nbuv.gov.ua/handle/123456789/161572
citation_txt	Модифицированный метод оптимальной остановки в задаче последовательного анализа альтернатив / Л.С. Файнзильберг // Управляющие системы и машины. — 2019. — № 1. — С. 11-21. — Бібліогр.: 16 назв. — рос.
series	Управляющие системы и машины
work_keys_str_mv	AT fajnzilʹbergls modificirovannyjmetodoptimalʹnojostanovkivzadačeposledovatelʹnogoanalizaalʹternativ
first_indexed	2025-07-14T14:10:56Z
last_indexed	2025-07-14T14:10:56Z
_version_	1837631808341016576
fulltext	iSSN 0130-5395, усим, 2019, № 1 11 doi https://doi.org/10.15407/usim.2019.01.011 удк 65.01:62-505 л.с. ФаЙнЗилЬБерГ, д-р техн. наук, профессор, главный научный сотрудник, международный научно-учебный центр информационных технологий и систем НаН украины и моН украины, просп. академика глушкова, 40, киев 03187, украина, fainzilberg@gmail.com модиФиЦированныЙ метод оптималЬноЙ остановКи в ЗадаЧе последователЬноГо аналиЗа алЬтернатив Предложен метод, обобщающий классическую постановку задачи оптимальной остановки принятия решений при последовательном просмотре ранжированных альтернатив в случайном порядке. Отличительная особенность метода состоит в том, что правильным считается решение о появлении претендента, который по некоторому критерию (суперкритерию) отличается от абсолютного лидера не более чем на заданную величину уступки. Ключевые слова: альтернатива, оптимальная остановка, вероятность правильного решения. введение На современном этапе развития общества по- вышается цена ошибочных решений в различ- ных сферах профессиональной деятельности и в повседневной жизни человека . Неправильно установленный медицинский диагноз, риско- ванное взятие кредитов или вложения инве- стиций, несвоевременно обнаруженное ава- рийное состояние оборудования — это далеко не полный перечень неправильных решений в медицине, экономике и технике, негативные последствия которых хорошо известны . Теория принятия решений обеспечивает научно обоснованный подход к выбору луч- шего, в некотором смысле, варианта пове- дения в условиях неполной информации [1] . Важность научного подхода обусловлена тем, что решения, которые человек принимает лишь на основе своей интуиции, не всегда ра- циональны . Можно сформулировать такие основные принципы теории принятия решений как на- учной дисциплины [2] .  Задача принятия решений возникает в ситуациях, когда есть не менее двух вариан- тов развития событий (альтернатив) .  Идеальных решений не бывает: выбор каждой из возможных альтернатив может приводить к определенным потерям (риску) лица, принимающего решение (ЛПР) .  Теория принятия решений обеспечивает выбор альтернативы, которая минимизирует возможный риск .  Математический метод, реализующий способ минимизации риска, должен соответ- ствовать внешней ситуации, в которой при- нимается решение, и предпочтениям ЛПР, в частности, его склонности рисковать . В одних случаях задача может быть све- дена к поиску лучшей альтернативы по со- вокупности критериев и тогда ее решение основывается на методах многокритериаль- ной оптимизации [3] . В других адекватной моделью задачи является принятие решений в условиях конфликта в предположении ак- тивного противодействия противников, и 12 iSSN 0130-5395, control systems and computers, 2019, № 1 Л.С. Файнзильберг тогда оптимальная стратегия основывается на теории игр [4] . Если же принятие решений осуществляет- ся в так называемой игре с природой, которая равнодушна к последствиям принимаемых решений, то выбор оптимальной альтернати- вы основывается на методах теории статисти- ческих решений (решения в условиях риска и неопределенности) [5] . Существует класс практически важных за- дач, когда ЛПР имеет возможность лишь по- следовательно анализировать возможные аль- тернативы, которые предъявляются в случай- ном порядке . Метод оптимальной остановки [6–9] — один из известных подходов к решению та- ких задач, который позволяет определить наилучший в некотором смысле момент вре- мени, когда следует принять окончательного решение . Такая задача, которая в русскоязычной ли- тературе получила название задача о разборчи- вой невесте [10], а в англоязычной – secretary problem [11], возникает, например, в следую- щих ситуациях:  поиск кандидата на вакантную долж- ность по результатам последовательного кастинга;  выбор места парковки или заправки ав- томобиля на дороге с движением в одном на- правлении;  принятие решения о наиболее привлека- тельном банке для получения кредита, поиск квартиры для аренды в большом городе или отдельного товара на рынке . Список подобных примеров можно было бы продолжить . Оказалось, что оптимальный момент оста- новки для принятия окончательного решения имеет элегантное математическое обоснование [10, 11] — правило тридцать семь процентов. Доказано, что независимо от общего числа претендентов вероятность выбора наилучшего из них будет максимальна, если после просмо- тра 37 процентов общего числа вариантов вы- брать того из кандидатов, который будет лучше предыдущих . постановка задачи Традиционная постановка задачи оптимальной остановки приводит к такому решению в пред- положении, что ЛПР интересует самый луч- ший вариант из всех кандидатов . Возникает вопрос: как изменится оптимальная стратегия принятия решений, если несколько модифи- цировать постановку задачи и допустить за- данную уступку на качество выбираемой аль- тернативы . Иными словами, как изменится момент оптимальной остановки и какая при этом бу- дет вероятность выбора претендента, который по некоторому критерию (суперкритерию) от- личается от абсолютного лидера не более чем на заданную величину . Цель статьи — исследовать возможности модифицированного метода оптимальной остановки на основе статистического экспе- римента . традиционный метод оптимальной остановки Прежде чем непосредственно переходить к ре- шению поставленной задачи напомним неко- торые детали классической постановки метода оптимальной остановки . Пусть D = {d 1 , ..., d N } — конечное мно- жество линейно упорядоченных (ранжи- рованных) альтернатив, для которых вы- полняется традиционное условие транзи- тивности: если i jd d� и j zd d� , то i zd d� , ∀ i, j, z ∈ [1, N], причем двух одинаковых аль- тернатив нет . Допускается, что ЛПР заранее не известны качества альтернатив d 1 ,..., d N , но на основе эксперимента он может в случайном порядке оценивать альтернативы и определить альтер- нативу, которая имеет преимущества перед предыдущими . На каждом n-м шаге последовательного просмотра (n = 1, 2, . . ., N) ЛПР может при- нять одно из двух решений: навсегда откло- нить очередную n-ю альтернативу и перейти к просмотру следующей или же остановиться и принять окончательное решение о выборе iSSN 0130-5395, усим, 2019, № 1 13 Модифицированный метод оптимальной остановки в задаче последовательного анализа альтернатив n-й альтернативы, не просматривая остальные N-n претендентов . Стратегия оптимального решения состоит в том, что ЛПР отклоняет первые r претенден- тов (r < N) независимо от их качеств, а затем в качестве лучшей признает первую из альтерна- тив, которая оказалась лучше просмотренных ранее . Для этого достаточно определить лидера d v на интервале просмотра [1, r] и принять окон- чательное решение, как только на интервале [r + 1, N] найдется альтернатива nd dν� (рис . 1) . Поскольку альтернативы просматривают- ся в случайном порядке, т .е . равновероятны все N! перестановок, которые задают порядок просмотра альтернатив, то на каждом шаге n = 1, . . ., N вероятность появления наилучшей альтернативы равна 0 1P N = . (1) Математическая постановка задачи состоит в определении такого номера шага t∈ [1, N], на котором следует принять окончательное ре- шение, чтобы максимизировать вероятность P > P 0 выбора наилучшей альтернативы из всех N возможных, т .е . 1 arg max ( )t j t N j t t P d d ≤ ≤ ∀ ≠ = � , j = 1,...,N . (2) Интуитивно понятно, что если число r ма- ленькое в сравнении с N, скорее всего наилуч- шая альтернатива появится на интервале [r, N] . Другими словами существует большой риск, что ЛПР еще не встретил лучшую альтернати- ву . Если же останавливаться слишком поздно, отвергая все альтернативы на интервале [1, r], то при слишком большом числе r ЛПР про- должает ждать лучшую альтернативу, которая уже отвергнута . Таким образом, оптимальная стратегия предполагает определенный баланс между не- достаточным и чрезмерным поиском, а значит, вероятность P зависит от выбора числа r: P = P (r) . В работе [11] представлено аналитическое вы- ражение для вероятности P(r) , которое имеет вид 1 1( ) . 1 N n n r rP r N n= − =   −  ∑ (3) Если ввести обозначения lim N rx N→∞ = и lim N nt N→∞ = , (4) то сумма, фигурирующая в (3), представляет собой римманновское приближение интегра- ла, т .е . 1 1( ) log( ) x P r x dt x x t → ==∫ . (5) Значение x, максимизирующее эту величи- ну, легко найти, приравняв к нулю производ- ную P (r) по x и найти корень x* полученного уравнения . Нетрудно убедиться в том, что * 1x e = , (6) где e — 2,71828 — основание натурального ло- гарифма (число Непера) . Отсюда как раз и следует, что момент опти- мальной остановки t, максимизирующий ве- роятность выбора наилучшей альтернативы, приблизительно определяется как 37 про- центов общего числа N альтернатив, а веро- ятность P того, что такое решение будет пра- вильным, равна 0,37P ≈ . (7) Существуют и другие подходы к аналити- ческому определению оптимального шага t остановки, удовлетворяющего условию (2) . Рассмотрим кратко один из таких альтер- нативных методов определения t, несколько упростив схему доказательства, предложенную в работе [10] . Введем обозначение случайных событий: A — ЛПР выбрал наилучшую альтернативу из множества D = {d 1 , ..., d N } возможных; … Альтернативы νd nd Остановка, если νddn  1 n r N Рис. 1. Иллюстрация традиционного метода опти- мальной остановки 14 iSSN 0130-5395, control systems and computers, 2019, № 1 Л.С. Файнзильберг B t — ЛПР выбрал текущую альтернативу на t-м шаге, предполагая, что она останется наи- лучшей далее; tB — ЛПР отверг текущую альтернативу на t-м шаге, предполагая, что наилучшая встре- тится далее . Для определения оптимальной стратегии, которая обеспечивает набольшую вероятность P = P (A) , рассмотрим две условные веро- ятности:  ( \| )t tg P A B= — вероятность того, что теку- щая альтернатива на t-м шаге не только лучше предыдущих, но и лучшая среди всех альтерна- тив множества D = {d 1 , ..., d N };  ( \| )t th P A B= — вероятность выбрать наилуч- шую альтернативу из множества D = {d 1 ,..., d N }, если на t-м шаге ЛПР отвергнет текущую аль- тернативу (хотя она оказалась лучшей среди предыдущих) в предположении, что начиная со следующего t+1-го шага ЛПР будет исполь- зовать оптимальную стратегию . Очевидно, что оптимальная стратегия на t-м шаге предполагает выбор текущей альтернати- вы, если она лучше предыдущих и выполняет- ся условие t tg h≥ . (8) На основе метода динамического програм- мирования нетрудно показать [10], что t tg N = . (9) В самом деле, пусть вначале t = N, т .е . ЛПР находится на последнем N-м шаге, а значит, все предыдущие N —1 альтернативы отвергнуты . В этом случае оптимальная стратегия очевидна:  выбрать N-ю альтернативу, если она лучше предыдущих (цель задачи достигнута);  отвергнуть N-ю альтернативу, если она не лучше предыдущих (цель задачи не до- стигнута) . Понятно, что если на последнем шаге (при t = N ) альтернатива лучше предыдущих, то она и самая лучшая, т .е . вероятность достижения цели равна g t = 1 . Определим теперь значение g t на шаге t = N - 1 . Вероятность g N-1 означает, что аль- тернатива, которую ЛПР признал лучшей на N - 1 шаге, не только лучше предыдущих, но и самая лучшая (случайное событие G N —1 ) . Поскольку анализ альтернатив происходит в случайном порядке, то в соответствии с (1) вероятности появления наилучшей альтерна- тивы на любом шаге одинаковы: 1 1 1( ) ... ( ) ( )N NP G P G P G N−= = = = . Таким образом, вероятность появления наи- лучшей альтернативы на N-м шаге равна 1/N . Отсюда следует, что если на N -1-м шаге аль- тернатива оказалась наилучшей в сравнении со всеми предыдущими, то условная вероят- ность остаться наилучшей и далее (т .е . быть лучше альтернативы на следующем N-м шаге) определяется так: 1 1 11 1N N Ng G N N− − = − = − = . Движемся далее и вычислим значение g t на шаге t = N - 2, т .е . условную вероятность g N - 2 того, что альтернатива, которая на шаге N - 2 признана лучше предыдущих останется луч- шей и на следующих двух шагах . Поскольку случайные события G N -1 и G N не совместны, то по формуле сложения вероятно- стей имеем 2 1 1 1 21 [ ( ) ( )] 1N N N Ng P G P G N N N− − − = − + = − + =   . Продолжая рассуждать аналогичным обра- зом, легко показать, что t tg N = , (10) т .е . вероятность g t линейно возрастает с ростом t . Вернемся теперь к вероятности h t , которая представляет собой вероятность достижения цели (выбрать наилучшую альтернативу), ког- да на t-м шаге альтернатива отвергнута, а далее ЛПР действует по оптимальной стратегии . Используя технику динамического програм- мирования можно показать [10], что 1 1 1... 1 1t th N t t N  = + + + + −  , (11) т .е . величина h t монотонно убывает с ростом t . Из выражений (10) и (11) непосредственно следует, что равенство g t = h t достигается при выполнении условия iSSN 0130-5395, усим, 2019, № 1 15 Модифицированный метод оптимальной остановки в задаче последовательного анализа альтернатив 1 1 1... 1 1 1t t N + + + = + − , (12) которое определяет точку T оптимальной оста- новки (рис . 2) . На основании условия (12) легко показать, что при N ≥ 100 точку оптимальной остановки определяет соотношение NT e = , которое совпадает с ранее полученным выра- жением . Следует обратить внимание на важное свой- ство задачи оптимальной остановки . Здравый смысл наталкивает на мысль, что шансы выбрать самую лучшую альтернативу неизменно умень- шаются при возрастании общего числа претен- дентов N . Этот факт непосредственно следует из формулы (1), в соответствии с которой выбор лидера наугад при N = 100 претендентах дает все- го лишь один шанс угадать, а если N = 1000, этот шанс снижается уже до 0,1 процента . В то же время, примечательно, что исполь- зуя стратегию оптимальной остановки вероят- ность успеха P = 37 процента при выборе луч- шего кандидата из N = 100 претендентов . И эта вероятность остается P = 37 процента и при N = 1000, и при других значениях N . Этот факт еще раз подтверждает крылатую фразу, что «наука начинается там, где заканчи- вается здравый смысл!» модифицированный метод оптимальной остановки В соответствии с (2) классическая постановка задачи оптимальной остановки ставит своей целью максимизировать вероятность P поис- ка самой лучшей альтернативы из конечного множества D = {d 1 ,..., d N } и дает изящное мате- матическое решение этой задачи при последо- вательном просмотре альтернатив в случайном порядке . В то же время в ряде прикладных задач цель выбрать самую лучшую альтернативу может оказаться избыточной . Достаточно предло- жить оптимальную стратегию, которая при по- следовательном просмотре альтернатив в слу- чайном порядке обеспечит выбор альтернати- вы, которая лишь близка к самой лучшей . Предположим, что каждую из альтернатив d 1 , ..., d N характеризует совокупность критери- ев x 1 , ..., x Q . Если допустить, что для критериев выполняется условие независимости по пред- почтениям [12], то для сравнения альтернатив можно перейти от частных критериев x 1 , ..., x Q к суперкритерию в виде аддитивной свертки 0 1 Q k k k x a x = = ∑ , (13) где a k — весовые коэффициенты, характеризу- ющие относительную важность k-го критерия x k в суперкритерии x0 . При отсутствии объективных обоснований об относительной важности критериев x 1 , ..., x Q весовые коэффициенты a k , k = 1, ..., Q мож- но определить на основе метода Саати [13] по таблицам парных сравнений, представленных экспертами . Допустим теперь, что цель ЛПР выбрать аль- тернативу d D∈� , которая по суперкритерию 0 ( )x d� отличается от наилучшей альтернати- вы d ∈ D не больше, чем на заданную уступку ∆ ≥ 0 . Другими словами, поставим задачу най- ти такой оптимальный шаг t последовательно- го просмотра альтернатив d 1 , ..., d N , на котором будет обеспечена максимальная вероятность P выбора альтернативы, которая удовлетворяет условию 0 * 0 ( ) ( )x d x d− ≤ ∆� . (14) Поскольку аналитическое определение опти- мального шага t в такой постановке сталкивается Рис. 2. Определение точки оптимальной остановки по условию g t = h t 16 iSSN 0130-5395, control systems and computers, 2019, № 1 Л.С. Файнзильберг с некоторыми сложностями, вызванными необхо- димостью введения дополнительных ограничений, оценим t* и соответствующую вероятность P�* ме- тодом статистического эксперимента . Правильно организованный статистиче- ский эксперимент — эффективный метод ис- следования поведения объекта в случайных условиях [14], который позволяет на основе компьютерного моделирования оценить ха- рактеристики объекта, аналитическая оценка которых затруднительна или невозможна . Для этого проводятся многократные испытания с разными значениями исходных данных с по- следующей статистической обработкой ре- зультатов наблюдений . Предлагаемый статистический экспери- мент основан на методе Монте-Карло [15], предусматривающий многократную генера- цию массивов 0{ , 1,..., }M nX x n N= = , M=1, . . .,M 0 независимых одинаково распределенных слу- чайных величин 0 nx с заданным законом рас- пределения . Каждое сгенерированное число Рис. 3. Рабочее окно программы iSSN 0130-5395, усим, 2019, № 1 17 Модифицированный метод оптимальной остановки в задаче последовательного анализа альтернатив 0 0 0 min max[ , ]nx x x∈ имитирует значение суперкри- терия для альтернативы d n ∈ {D 1 , ..., D N }, кото- рую ЛПР наблюдает на n-м шаге . В простей- шем случае можно допустить, что величины 0 , 1,...,nх n N= равномерно распределены в ин- тервале значений 0 0 min max[ , ]x x . Очевидно, что наилучшая альтернатива d, соответствующая максимальному значению суперкритерия x max , на каждом отдельном экс- перименте может встретится на произвольном шаге n ∈ [1, . . ., N] сгенерированного массива X M . Аналогично случайными будут и номера шагов, при которых наблюдаются альтернати- вы d� , удовлетворяющие условию (14) . Цель экспериментов – на серии испытаний оценить оптимальный шаг t* ∈ [1, . . ., N], кото- рый обеспечивает максимум вероятности вы- полнения условия (14), когда используется сле- дующая стратегия принятия решений по сге- нерированному массиву 0{ , 1,..., }M nX x n N= = , M = 1, . . ., M 0 значений:  определяют истинного лидера отдельного эксперимента по максимальному значению су- перкритерия * 0 1 max nn N x x ≤ ≤ = ;  определяют условного лидера по максималь- ному значению суперкритерия в интервале ин- дексов [1, t], t < N, т .е . определяют число { }max 0 0 1, 1max ,...,t tx x x= ; (15)  определяют в качестве окончательного ре- шения принимается первая из альтернатив d� в диапазоне индексов [t, N], которую характери- зует суперкритерий, превышающий число max 1,tx . Для определения свойств модифицирован- ного метода оптимальной остановки прово- диться M 0 статистических экспериментов по описанной стратегии и для каждого фикси- рованного t ∈ [1, N] оценивается вероятность правильного решения, т .е . вероятность выбо- ра альтернативы d� ∈ D, которая удовлетворя- ет условие (14) . Вероятность достижения цели (14) оценива- ют частотой 0 ( )( ) m tP t M = , (16) где m(t) — число успехов на t-м шаге в серии из M 0 экспериментов . Таким образом, вместо аналитического определения свойств модифицированного метода оптимальной остановки можно с по- мощью предлагаемой схемы организации вы- числительного эксперимента провести ком- Рис. 4. Зависимости вероятности P� успеха от номера шага t принятия окончательного решения при раз- личных уступках ∆ 18 iSSN 0130-5395, control systems and computers, 2019, № 1 Л.С. Файнзильберг пьютерное моделирование процесса принятия решений при заданных N и M 0 и оценить ве- роятность достижения цели на разных шагах t ∈ [1, N] . В результате по максимуму вычис- ленной вероятности определяют оптимальный момент остановки t при разных значениях уступки ∆ ≥ 0 . Очевидно, что при ∆ = 0 результаты экспери- мента должны совпадать с ранее приведенными результатами аналитического определения момен- та оптимальной остановки традиционной схемы . Для выполнения статистических экспери- ментов разработана программа1, рабочее окно которой показано на рис . 3 . Приведем некоторые результаты проведенных исследований . Вероятности P� оценивались для N = 100 альтернатив в сериях из M 0 = 1000 экс- периментов на последовательностях случайных 1 Программу под руководством автора разработала Ю .С . Яременко — cтудентка Национального техниче- ского университета Украины "Киевский политехниче- ский институт имени Игоря Сикорского" [16] . чисел, которые имитировали значения супер- критерия . На рис . 4 . представлены графики за- висимости оценок вероятностей (16) от номера шага t принятия окончательного решения в со- ответствии с рассматриваемой стратегией при разных значениях величины уступки ∆ (в про- центах от значения суперкритерия для наилуч- шей альтернативы) . Как видно (рис . 4) при увеличении значения уступки ∆ оптимальный шаг t* ∈ [1, . . ., N], на котором следует принимать окончательное ре- шение, уменьшается, а вероятность P� принять правильное решение увеличивается . Для наглядности на рис . 5 представлен гра- фик зависимости вероятности P� принятия окончательного решения на оптимальном шаге от величины уступки ∆, а на рис . 6 — гра- фик зависимости номера оптимального шага от величины уступки ∆ . Как и следовало ожидать, вероятность P� и номер оптимального шага t приближаются к теоретическим значениям, полученным ана- литическим путем для классического метода оптимальной остановки при ∆ → 0 . Следует обратить внимание, что уже при зна- чении уступки ∆ = 4% обеспечивается уменьше- ние оптимальной точки принятия окончатель- ного решения от 37 процентов максимального количества шагов (классический метод) до 15 процентов (рис . 5) . А это значит, что при N = 100 альтернатив для достижения цели модифи- цированного метода оптимальной остановки, анализируемых в случайном порядке, достаточ- но просмотреть всего 15 альтернатив . При этом вероятность принятия правильно- го решения увеличивается (рис . 6) и достига- ет P� = 0,68 при уступке ∆ = 10% в сравнении с вероятностью правильного решения P = 0,37, достигаемой классическим методом . Заключение Традиционная постановка задачи оптимальной остановки ставит своей целью выбрать момент принятия решения о появлении самого лучшего варианта при последовательном просмотре ран- жированных альтернатив в случайном порядке . Рис. 5. Зависимость веротяности P� от величины уступ- ки ∆ Рис. 6. Зависимость номера оптимального шага t* остановки от величины уступки ∆ iSSN 0130-5395, усим, 2019, № 1 19 Модифицированный метод оптимальной остановки в задаче последовательного анализа альтернатив ЛИТЕРАТУРА 1 . Волошин О .Ф ., Мащенко С .О . Моделі та методи прийняття рішень: навч . посіб . К .: Вид-во полігр . центр «Київ . ун-т», 2010 . 336 с . 2 . Файнзільберг Л .С ., Жуковська О .А ., Якимчук В .С . Теорія прийняття рішень: підручник для студентів спеціальності «Комп’ютерні науки та інформаційні технології», спеціалізації «Інформаційні технології в біології та медицині» . Київ : Освіта України, 2018 . 246 с . 3 . Maheswari U .A ., Kumari P .A . Fuzzy Mathematical Model for Multi Criteria Group Decision Making-An Application in Supply Chain Management . Int . J . of Computer Applications, 2012, 54 (7), p . 5–10 . 4 . Rasmusen E . Games and Information: An Introduction to Game Theory, 4th Edition . Oxford: Wiley-Blackwell, 2006 . 445 p . 5 . Де Грот М . Оптимальные статистические решения . М .: Мир, 1974 . 491 с . 6 . Доценко С .И ., Негадайлов П .А . Об оптимальном порядке просмотра групп в задаче выбора наилучше- П .А . Об оптимальном порядке просмотра групп в задаче выбора наилучше-П .А . Об оптимальном порядке просмотра групп в задаче выбора наилучше- го элемента с групповым просмотром кандидатов, Кибернетика и вычислительная техника, 2014, вып . 175, C . 32–9 . 7 . Роббинс Г ., Сигмунд Д ., Чао И . Теория оптимальных правил остановки . Пер . с англ . М .: Наука, 1975 . 188 с . 8 . Гусейн-Заде С .М . Задача выбора и оптимальное правило остановки последовательности независимых ис- пытаний . Теория вероятностей и ее применения, 1966, том XI, № 3, С . 534–537 . 9 . Sakaguchi M . Optimal stopping problems for randomly arriving offers . Math . Japon, 1976, N 21, pp . 201–217 . 10 . Гусейн-Заде С .М . Разборчивая невеста . М .: МЦНМО, 2003, 24 с . 11 . Ferguson T .S . Who Solved the Secretary Problem? Statistical Science, 2003, 4 (3), pp . 282–289 . 12 . Кини Р .Л ., Райфа Х . Принятие решений при многих критериях: предпочтения и замещения . М .: Радио и связь, 1981 . 13 . Саати Т . Принятие решений . Метод анализа иерархий . М .: Радио и связь, 1993 . 14 . Rubinstein R .Y ., Kroese D .P . Simulation and the Monte Carlo Method . New York: John Wiley & Sons, 2016, 432 p . 15 . Robert C .P ., Casella G . Monte Carlo statistical methods . New York: Springer, 2004 . 397 p ., http://dx .doi . org/10 .1007/978-1-4757-4145-2 . 16 . Файнзільберг Л ., Яременко Ю . Комп’ютерне моделювання модифікованого методу оптимальної зупинки, Proceedings of the Int . Sci . Conf . “Information Technologies and Computer Modeling” (2018, May, 14th to 19th, Ivano-Frankivsk) . Івано-Франківськ: Прикарпатський національний університет імені Василя Стефаника, 2018 . С . 270–273 . Поступила 24 .02 .2019 REFERENCES 1 . Voloshin, O .F ., Maschenlo, C .O ., 2010 . Models and Methods of Decision Making: Teach . Manual, Kiev: View- polygraph . center “Kyiv . un-t “, 336 p . (In Ukrainian) . 2 . Fainzilberg, L .S ., Zhukovska, O .A ., Yakumchuk, V .S ., 2018 . Theory of decision-making: a textbook for students of the specialty “Computer Science and Information Technologies”, specialization “Information Technologies in Biology and Medicine” . Kyiv: Education of Ukraine, 246 p . (In Ukrainian) . 3 . Maheswari, U .A ., Kumari, P . A ., 2012 . “Fuzzy Mathematical Model for Multi Criteria Group Decision Making-An Application in Supply Chain Management”, Int . J . of Computer Applications, Vol . 54, No . 7, pp . 5–10 . 4 . Rasmusen, E ., 2006 . Games and Information: An Introduction to Game Theory, 4th Edition . Oxford: Wiley- Blackwell, 445 p . Доказано, что независимо от общего числа пре- тендентов вероятность правильного решения бу- дет максимальна, если после просмотра 37 про- центов общего числа вариантов выбрать того из кандидатов, который будет лучше предыдущих . Отличительная особенность рассматри- ваемого в статье метода состоит в обобщении задачи оптимальной остановки в том смыс- ле, что правильным считается решение о по- явлении претендента, который по некоторому критерию (суперкритерию) отличается от аб- солютного лидера не более чем на заданную величину уступки ∆ ≥ 0 . На основании серии статистических экспе- риментов показано, что такая модификация метода позволяет уменьшить объем экспери- ментальной группы наблюдений и повысить вероятность правильного решения . 20 iSSN 0130-5395, control systems and computers, 2019, № 1 Л.С. Файнзильберг 5 . DeGroot, M ., 1974 . Optimal statistical decision, Moscow: Mir, 491 p . (In Russian) . 6 . Dotcenko, S .I ., Negadaylov, P .A ., 2014 . “The optimal order of viewing groups in the task of choosing the best element with a group view of the cardidates”, Cybernetics and Computer Engineering, Issue 175, pp . 32–39 . (In Ukrainian) . 7 . Robbins, G, Sigmund, D ., Chao, I ., 1975 . The theory of optimal stopping rules, Moscow; Nauka, 188 p . (In Russian) . 8 . Gusein-Zade, S .M ., 1966 . The problem of choice and the optimal stopping rule for the sequence of independent tests . Theory of probabilities and its applications, Vol . 11, No 3, pp . 534–537 . 9 . Sakaguchi, M ., 1976 . “Optimal stopping problems for randomly arriving offers”, Math . Japan, No . 21, pp . 201–217 . 10 . Gusein-Zade, S .M ., 2003 . Clever bride, Moscow: MCNMO, 24 p . (In Russian) . 11 . Ferguson, T .S ., 2003 . “Who Solved the Secretary Problem?”, Statistical Science, Vol . 4, No . 3, pp . 282–289 . 12 . Keeney, R .L ., Raiffa, H ., 1981 . Decisions with Multiple Objectives, Moscow: Radio and communication, 500 p . (In Russian) . 13 . Saati, T ., 1993 . Decision making . Hierarchy analysis method, Moscow: Radio and communication, 278 p . (In Russian) . 14 . Rubinstein, R .Y ., Kroese, D .P ., 2016 . Simulation and the Monte Carlo Method, New York: John Wiley & Sons, 432 p . 15 . Robert, C .P ., Casella, G ., 2004 . Monte Carlo statistical methods . New York: Springer, 2004, 397 p . http://dx .doi .org/10 . 1007/978-1-4757-4145-2 . 16 . Fainzilberg, L ., Yaremenko, Yu ., 2018 . “Computer Modeling of the Modified Method of Optimal Stopping”, Proceedings of the International Scientific Conference “Information Technologies and Computer Modeling” (2018, May, 14th to 19th, Ivano-Frankivsk) . Ivano-Frankivsk, pp . 270–273 . (In Ukrainian) . Received 24 .02 .2019 L.S. Fainzilberg, Doctor of Technical Sciences, professor, head of the department, International Research and Training Center for Information Technologies and Systems of the NAS and MES of Ukraine, Glushkov ave ., 40, Kyiv, 03187, Ukraine, fainzilberg@gmail .com, MODIFIED OPTIMAL STOPING METHOD IN THE PROBLEM OF A SEQUENTIAL ALTERNATIVES ANALYSIS Introduction . The traditional formulation of the optimal stopping problem is aimed at choosing the moment of making a decision about the appearance of the best option during the sequential viewing of ranked alternatives in a random order . A distinctive feature of the proposed generalization of the method is in the sense that the decision on the appearance of an applicant, which by some criterion differs from the absolute leader by no more than a specified amount (assignment), is considered correct . The purpose of the article is to explore the possibilities of a modified optimal stopping method based on a statistical experiment Methods . The statistical experiment is based on the Monte Carlo method and provides for the multiple generation of arrays of independent identically distributed random variables that mimic the values of the super criterion of the alternative, which the person observes at the current step . On the basis of a series of multiple tests, the probability of selecting an ap- plicant, which differs by a given amount from the absolute leader, is estimated . The analysis of the dependence of the prob- ability of correct decisions on the value of the assignment is done . Result . It has been established that already at a value of 4% assignment, the required amount of experimental sampling for making a final decision decreases from 37% (the classical method) to 15% . At the same time, the probability of right decision increases to P� =0,68 (when is concession of 10%) compared with the probability P = 0,37 of the right decision, achieved by the classical method . Conclusion . By introducing an insignificant concession to the deviations of the chosen applicant from the absolute leader, the possibilities of the optimal stopping method are expanded to solve practical problems . Keywords: optimal stopping, alternative, probability of correct decision. iSSN 0130-5395, усим, 2019, № 1 21 Модифицированный метод оптимальной остановки в задаче последовательного анализа альтернатив Л.С. Файнзильберг, д-р техн . наук, професор, головний науковий співробітник, Міжнародний науко-навчальний центр інформаційних технологій та систем НАН України та МОН України, просп . Академіка Глушкова, 40, Київ, 03187, Україна, fainzilberg@gmail .com МОДИФІКОВАНИЙ МЕТОД ОПТИМАЛЬНОЇ ЗУПИНКИ В ЗАДАЧІ ПОСЛІДОВНОГО АНАЛІЗУ АЛЬТЕРНАТИВ Вступ . Традиційна постановка задачі оптимальної зупинки ставить собі за мету вибрати момент прийняття рішення про появу найкращого варіанту при послідовному огляді у випадковому порядку ранжованих альтер- натив . Відмінність пропонованого узагальнення полягає у тому, що правильним вважається рішення про появу претендента, який за деяким критерієм відрізняється від абсолютного лідера не більше ніж на задану величину (поступку) . Ціль статті — дослідити можливості модифікованого методу оптимальної зупинки на основі статистичного експерименту . Методи . Статистичний експеримент, що пропонується, заснований на методі Монте-Карло і передбачає ба- гаторазову генерацію масивів незалежних однаково розподілених випадкових величин, які імітують значення суперкритерію до альтернативи, за якою особа, що приймає рішення, спостерігає на поточному кроці . На основі серії багаторазових випробувань оцінюється ймовірність вибору претендента, який на задану величину поступки відрізняється від абсолютного лідера . Проводиться аналіз залежності ймовірності вірних рішень від величини поступки . Результат . Встановлено, що вже при значенні чотири відсотка поступки необхідний обсяг експериментальної вибірки для прийняття остаточного рішення знижується з 37 (класичний метод) до 15 відсотків . При цьому ймовірність прийняття правильного рішення збільшується і досягає P� =0,68 при поступці в 10 відсотків в порівнянні з ймовірністю правильного рішення P = 0,37, що досягається класичним методом . Висновок . За рахунок введення незначної поступки на відхилення якостей обраного претендента від абсолютного лідера розширюються можливості методу оптимальної зупинки для вирішення практичних завдань . Ключові слова: оптимальна зупинка, альтернатива, ймовірність правильного рішення.

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

Institution

Ähnliche Einträge