Мъж продаваше крава на пазара (изчислително решение)
Нека сега преминем към времево-дискретния аналог. За да получим добро приближение, разделяме времевата ос на толкова малки равни интервали, че тяхната стойност да не надвишава 1/10 от времето на доставка на крави от селото и в същото време вероятността да се появи поне един купувач, независимо от класа, не надвишава същата 1/10 през такъв период. Възниква друго условие, което по някакъв начин трябва да ограничи размера на грешката при дискретизация на разходите за сравнително скъпи фуражи, като например в случай на много богат и рядко появяващ се купувач и винаги налична възможност, ако желаете, да продадете крава много бързо на покупната цена. Въпреки това, условието за избор на толкова малък интервал, че средно 1/10 от купувача се появява през него, ограничава бързината на реакцията към допълнителна крава, което прави по-нататъшното намаляване на интервала от време нецелесъобразно.
Време е да опишем процеса на действие на дискретния пазар. Нека времето за доставка T е разделено на r интервала. Следва редът на действията в рамките на всеки интервал на разделяне, които се наричат обиколки или ходове по-долу. В началото на всеки тур мъжът получава заявените за това време крави и заплаща изхранването на всичкия добитък, който има, след което по описаните по-горе проби се установява дали купувачът е дошъл и каква е възможната печалба от него. В края на рунда мъжът трябва да извърши две действия: да продаде кравата или да откаже сделката и да поръча необходимия брой крави, които ще му бъдат доставени след точно r хода. В този момент ходът приключва и започва нов.
В описаната схема на функциониране на пазара, състоянието на мъжа към момента на решението е напълно описано
1) броя на кравите, които има в бокса, 2) разпределението на всички крави, подредени от него спореднай-близките r ходове, 3) присъствие и клас на купувача на текущия ход.
Тук трябва специално да подчертая, че при 2) е важен не само общият брой крави в подредбата, но и разпределението им по най-близките ходове, за които подреждането вече не е възможно.
Хипотетично Човекът има изброим брой възможни състояния, но изглежда съвсем очевидно, че има такъв брой крави M, които да има в реда, извън който не е изгодно, независимо от разпределението на доставката им върху r най-близки ходове. В резултат на това броят на държавите, които реално участват в играта с всяка оптимална стратегия, се оказва краен.
Друго почти очевидно твърдение, използвано по-долу, е следното: нека разширим класа на допустимите стратегии, като позволим на човека да действа и въз основа на случайни експерименти, като хвърляне на монета. Такива стратегии в теорията на игрите се наричат смесени и ви позволяват да попречите на опонента си да научи вашия стил на игра достатъчно добре, за да направи стратегията ви по-ефективна. Изглежда достатъчно правдоподобно, тъй като в описания експеримент няма противник, замяната на всички резултати от хвърляне на монета с „глава“ в която и да е оптимална стратегия няма да влоши самата стратегия.
Накрая се обръщам към описанието на алгоритъма. Нека начертаем на хартия поотделно всички допустими състояния на Човека в началото на обиколката, когато кравите вече са пристигнали, и в края му, преди да вземем решение, като общият брой на наличните и поръчани крави не надвишава M. Нашата цел ще бъде да дефинираме насочени ръбове между тези състояния с умело подбрани разходи, така че да можем да приложим алгоритъма за намиране на затворен поток от единичен капацитет за решаване на проблема (потокът, влизащ във всеки връх, е равен на потока изходящ ing от него, сумата надвсички върхове на интензитетите на входящите потоци е равно на 1). Така че, помислете за някакво състояние в началото на движението. От него рисуваме насочени ръбове към възможните състояния в края му. Всеки такъв ръб съответства на класа на входящия клиент или пълното им отсъствие. Нека присвоим на тези ръбове тегла, равни на техните вероятности, и разходи, равни на разходите за хранене. Сега помислете за състоянията, съответстващи на момента преди решението за продажба и поръчка. За всяка двойка (стойност на поръчката, продажба/не) нарисувайте стрелка към състоянието, до което тези действия ще доведат. Ние няма да присвоим фиксирано тегло на тези стрелки, но ще зададем тяхната стойност, равна на стойността на цената на поръчката минус стойността на стойността на поръчката. За повечето практически приложения изглежда, че не може да се поръча повече от една крава наведнъж.
Нека сведем проблема до анализа на веригите на Марков. Изборът на стратегия при този подход съответства на присвояване на всеки връх, съответстващ на състоянието в края на хода, вероятностно тегло на всички излизащи от него ребра. След като намерихме ограничаващото вероятностно разпределение (в неизродени случаи всички върхове са достижими и непериодични), ние определяме ограничаващия вероятностен поток и от него мощността на дохода или загубата. Стратегията ще бъде оптимална, ако максимизира силата на дохода.
Препоръчително е търсенето на ограничаващия поток и максимизирането на печалбата да се решава едновременно чрез метода на линейното програмиране, който по отношение на средната изчислителна сложност в експериментите е значително по-добър от метода на директно изброяване, който също е приложим за решаване на дискретен проблем, поне теоретично.
Сега, по отношение на приложението на метода за решаване на проблем с линейно програмиране: ако вероятностният поток върху построената графика на състоянието е даден от неговите стойности на всеки ръб, тогава тезиколичества се налагат единствените ограничения под формата на неравенства, състоящи се в това, че всички те не са по-малки от нула. Що се отнася до линейните връзки, те са както следва:
1) общият входящ поток към всеки връх, съответстващ на състоянието в началото на хода, се преразпределя по изходящите ръбове, съответстващи на вероятността за пристигане на купувач от даден клас, пропорционално на вероятностите за този клас или същото, както е посочено в текста по-горе, спрямо теглото на ръба; 2) потоците по протежение на ръбовете, произтичащи от върховете, обозначаващи състоянията в края на хода, могат да бъдат избрани от всеки, стига тяхната сума да е равна на сумата от потоците, влизащи в техния връх; 3) сумата от всички компоненти на потока е равна на 1.
По-горе беше даден метод за присвояване на всички ръбове на техните разходи. Целевата функция на задачата за линейно програмиране е скаларното произведение на вектора на потока и вектора на разходите.
Можете да помогнете и да прехвърлите средства за развитието на сайта