Теория оптимальной остановки

Размещено на http://www.allbest.ru/

Волжский политехнический институт (филиал) Федерального государственного бюджетного образовательного учреждения высшего образования

"Волгоградский государственный технический университет"

Теория оптимальной остановки

Григорьев М.С., Горбачёв М.В.,

Светличная В.Б., Матвеева Т.А.

г. Волжский, Россия

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

А вы уверены, что выбрали лучший вариант?

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

Разберем теорию оптимальной остановки на практике.

Основанная на теории вероятности, теория оптимальной остановки имеет более интересную родословную, нежели большинство её математических собратьев. Впервые задача оптимальной остановки была предложена Кейли в 1875 году, она применялась для покупки лотерейных билетов. Давайте взглянем, как это работает на нашем примере с покупкой квартиры.

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

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

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

Итак, объявим для начала, что вы имеете 12 квартир (n). Шаг h (h?0). Первое, что вам нужно знать - это вероятность победы в случае выбора квартиры в момент h, при условии, что она лучше всех предыдущих, т. е. вероятность того, что она не только лучше всех предыдущих, а вообще лучше всех. Обозначим эту вероятность за q_h. Кроме того, необходимо знать ещё одну величину - это вероятность того, что вы, в конце концов, получите самую хорошею квартиру, при условии, что вы пропустит первых h квартир и дальше будите пользоваться оптимальной стратегией (здесь подразумевается наше предположение о том, что вы знаете, как себя оптимально вести начиная с шага h+1, это и есть принцип, используемый в динамическом программировании). Обозначим эту вероятность за v_h. Зная эти две величины для любого h, мы можем легко понять оптимальную стратегию поведения для вас: если на шаге h квартира не лучше всех предыдущих, то, ясное дело, её не нужно брать, если же она действительно лучшая среди первых h квартир, то нужно сравнить q_h и v_h, если больше q_h, то нужно остановиться на этой квартире h, если больше v_h, то не нужно её брать и перейти к следующему, такая стратегия следует прямо из определения этих вероятностей. Что же делать в случае равенства? Понятно, что это неважно, так как вероятность победы в каждом из случаев одинакова, поэтому давайте договоримся, что в случае равенства q_h и v_h вы будет, например, всё время останавливаться на текущей квартире.

Рассчитаем возможность того что квартира лучше всех q_h.

Рассчитаем возможность вашей победы v_h

Правильная стратегия состоит в следующем:

1. Делим всех n претендентов на две группы: "экспериментальная" () и "рабочая" (1 ? Размещено на http://www.allbest.ru/

).

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

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

То есть в нашем случае мы должны отказаться сразу от первых 4 квартир и самые лучшие из 4 используем как образцы. При этом вероятность получить, в конце концов, самую лучшею квартиру из всех n квартир равна примерно 4,41%. Если вы не слишком привередливы, то вы можете приобрести не самую лучшую квартиру, а ту, что входит в список "k лучших квартир". Пускай k будет фиксированное количество, к примеру, 2. Исходя из теории оптимального выбора стратегия, способствующая увеличению вероятности вашего выигрыша, выглядит следующим образом.

Вы должны пропустить приблизительно 34,7% квартир, не покупая, из следующих приблизительно 32% (вплоть до 66,7% всех квартир) покупать лишь ту, что лучше всех предыдущих, а из оставшихся 33,3% квартир соглашаться и на вторую по качеству среди уже прошедших. Таким образом, в этом случае ваши шансы на удачный выбор (при оптимальной стратегии) больше 50%.Это подтверждается на примере таблиц, мы видим, что самая большая вероятность нашего успеха находится в пределах с 7 по 10 квартир, а самые выгодные квартиры находятся в пределах 7-11, что соответствует нашей стратегии того, что первые 4 квартиры необходимо откинуть и смотреть следующие по качеству.

Список литературы

остановка вероятность статистический

1. Якушина А.А., Быханов А.В., Елагина А.И., Матвеева Т.А., Агишева Д.К., Светличная В.Б. Одноканальная система массового обслуживания с пуассоновским входным потоком // Материалы VIII Международной студенческой электронной научной конференции "Студенческий научный форум" URL: http://www.scienceforum.ru/2016/1762/22925

2. Горбатов Н.С., Ким В.А., Светличная В.Б., Агишева Д.К., Зотова С.А. теория вероятностей в жизни студентов // Материалы VIII Международной студенческой электронной научной конференции "Студенческий научный форум" URL: http://www.scienceforum.ru/2016/1762/24350

3. [Электронный ресурс] URL: http://my-tribune.blogspot.ru/2009/11/blog-post_11.html

Размещено на Allbest.ru