На ринку корову мужик продавав (обчислювальне рішення)
Давайте тепер перейдемо до дискретного аналогу за часом. Щоб отримати хороше наближення, розіб'ємо вісь часу на такі малі однакові проміжки, щоб їх величина не перевищувала 1/10 часу доставки корів із села і при цьому ймовірність з'явиться хоча б одному покупцю, не важливо якого класу, за такий проміжок не перевершувала все ту ж 1/10. Напрошується ще умова, яка якимось чином повинна обмежувати розмір помилки дискретизації витрати на відносно дорогу прокорм, як, наприклад, у випадку з дуже багатим і покупцем, що рідко з'являється, і постійно наявної можливості при бажанні дуже швидко продати корову за закупівельною ціною. Проте умова вибору настільки малого проміжку, що його протягом у середньому з'являється 1/10 покупця, обмежує оперативність реакцію зайву корову, роблячи подальше зменшення часового проміжку недоцільним.
Настав час описати процес дій на дискретному ринку. Нехай час доставки T виявився розбитим на інтервалів r. Далі наведено порядок дій усередині кожного інтервалу розбиття, які називають далі турами або ходами. На початку кожного туру Мужик отримує замовлених на цей час корів і оплачує прокорм всієї наявної худоби, потім описаними вище випробуваннями визначається, чи прийшов покупець і який з нього можливий прибуток. Наприкінці туру Мужика має виконати дві дії: продати корову, або відмовити в угоді і замовити необхідну кількість корів, яких йому доставлять рівно через r ходів. На цьому хід закінчено і починається новий.
В описаній схемі функціонування ринку стан Мужика на момент ухвалення рішення повністю описується
1) кількістю наявних у нього в стійлі корів, 2) розподілом усіх замовлених ним корів занайближчим r ходам, 3) наявністю та класом покупця на поточному ходу.
Я повинен тут особливо наголосити, що в 2) важливо не тільки сумарна кількість корів у замовленні, але й їх розподіл по найближчих ходах, на які замовлення вже неможливе.
Гіпотетично Мужик має лічильну кількість можливих станів, проте здається цілком очевидним, що існує така кількість корів M, мати в замовленні, понад яке, не вигідно незалежно від розподілу їх доставки по r найближчим ходам. В результаті кількість станів, які дійсно беруть участь у грі за скільки-небудь оптимальної стратегії, виявляється кінцевою.
Ще одне майже очевидне твердження, яке використовується нижче, полягає в наступному: давайте розширимо клас допустимих стратегій, дозволивши мужику діяти ще й спираючись на випадкові експерименти, на кшталт підкидання монетки. Такі стратегії теорії ігор називаються змішаними і дозволяють не дати можливості опоненту, досить добре вивчивши стиль вашої гри, зробити свою стратегію більш ефективною. Здається досить правдоподібним, що оскільки в описаному експерименті немає опонента, замінивши в будь-якій оптимальній стратегії всі результати підкидання монетки на «орла», ви не погіршите саму стратегію.
Перейду нарешті до опису алгоритму. Викреслимо на папері окремо всі допустимі стани Мужика на початок туру, коли корови вже прибули, і в його кінці перед прийняттям рішення із загальною кількістю наявних та замовлених корів, що не перевищують M. Нашою метою буде довизначити між цими станами спрямовані ребра з хитро підібраними цінами, щоб для вирішення завдання можна було застосувати алгоритм пошуку замкнутого потоку одиничної потужності (потік, що входить у кожну вершину, дорівнює потоку, що виходить з неї, сума повсім вершинам інтенсивностей вхідних потоків дорівнює 1). Отже, розглянемо якийсь стан початку ходу. З нього проведемо спрямовані ребра до станів, можливим у кінці. Кожне таке ребро відповідає класу клієнта, що прийшов, або їх повній відсутності. Припишемо цим ребрам ваги, рівні їхнім ймовірностям і вартості, рівні величині витрат на прокорм. Тепер розглянемо стани, що відповідають моменту перед прийняттям рішення про продаж та замовлення. Для кожної пари (величина замовлення, продати/ні) викреслимо стрілку у стан, до якого приведуть ці дії. Цим стрілкам ми не приписуватимемо фіксовану вагу, а їх вартість покладемо рівною величиною ціни замовлення мінус величина вартості замовлення. Для більшості практичних програм, мабуть, можна замовляти не більше однієї корови за раз.
Зведемо завдання до аналізу марківських кіл. Вибору стратегії при такому підході відповідає приписування в кожній вершині, що відповідає стану на кінець ходу, імовірнісної ваги всім ребрам, що виходять з неї. Знайшовши граничний розподіл ймовірностей (у невироджених випадках всі вершини досяжні та неперіодичні), визначимо граничний ймовірнісний потік і по ньому потужність доходу або збитків. Стратегія буде оптимальною, якщо вона максимізує потужність прибутку.
Пошук граничного потоку і максимізацію прибутку доцільно вирішувати одночасно методом лінійного програмування, який за середньою на дослідах обчислювальної складності відчутно кращий за метод прямого перебору, який також застосовується для вирішення дискретного завдання, принаймні теоретично.
Тепер щодо застосування методу вирішення задачі лінійного програмування: якщо ймовірнісний потік на побудованому графі станів заданий своїми величинами на кожному ребрі, то на цівеличини накладаються єдині як нерівностей обмеження, які у тому, що вони не менше нуля. Що стосується лінійних зв'язків, то вони такі:
1) сумарний вхідний потік у будь-яку вершину, що відповідає стану на початок ходу, перерозподіляється по вихідних ребрах, що відповідають ймовірності приходу покупця заданого класу, пропорційно ймовірностям для цього класу або те саме, як було зазначено в тексті вище, - вазі ребра; 2) потоки вздовж ребер, що виходять з вершин, що позначають стани на кінець ходу, можуть бути обрані будь-якими, аби їх сума дорівнювала сумі потоків, що входять в їх вершину; 3) сума всіх компонентів потоку дорівнює 1.
Вище давався спосіб присвоєння всім ребра їх вартості. Як цільову функцію завдання лінійного програмування виступає скалярний добуток вектора потоку на вектор вартостей.
Ви можете допомогти і перевести небагато коштів на розвиток сайту