РОЗВ’ЯЗУВАННЯ ІГРОВИХ ЗАДАЧ З ОБМЕЖЕННЯМИ-ПОЛІРОЗМІЩЕННЯМИ НА СТРАТЕГІЇ ОДНОГО ГРАВЦЯ: ІТЕРАЦІЙНИЙ МЕТОД ТИПУ БРАУНА-РОБІНСОН
Анотація
У статті розглядається така ігрова задача. У регіоні існують і працюють два конкуренти – великі виробники хлібної продукції. Є певна кількість населе- них пунктів регіону, де є фірмові магазини 1-го виробника, і певна кількість населених пунктів, де є фірмові магазини 2-го виробника. Продукція вва- жається швидкореалізовуваною. Тому проблема визначення кількості про- дукції, що розвозиться, виникає щоденно. Першому виробнику в певному місті потрібна відома кількість автомобілів, якими продукція щоранку буде розвозитися в таку ж кількість фірмових магазинів. Автомобілі пропону- ється вибрати з деякою більшої, ніж потрібно, кількості в цьому місті. Ува- жається, що вчорашня продукція або реалізована, або непридатна для вжи- вання. Будемо вважати, що другий виробник може розвозити у свої фірмові магазини (які розташовуються в регіоні) таку кількість продукції, яку вважає за потрібне. Прибуток обох підприємців залежить від обсягу хлібної про- дукції, що завозиться, у кожний фірмовий магазин. Обидва виробники праг- нуть отримати якомога більший прибуток, тому вони прагнуть максимально збільшити різницю між своїм прибутком і прибутком конкурента. У статті для задачі побудована ігрова модель комбінаторного типу з вико- ристанням множини полірозміщень, якими є стратегії першого гравця. Для першого гравця його задача є задачею комбінаторної оптимізації на полірозміщеннях. Для другого гравця його задача схожа на задачу гравця у звичайних матричних іграх. Розглядається випадок наявності й відсутності сідлової точки в ігровій моделі. У разі відсутності сідлової точки шука- ються мішані стратегії гравців. Для цього запропоновано метод типу Брауна-Робінсон. При цьому розі- грується гра. Один гравець має звичайні мішані стратегії, а інший гравець як стратегії має вибір з елементу з множини полірозміщень. Кроки гравці роблять один за одним. Розраховуються накопичені платежі, за якими й визначається наближений розв’язок гри. Алгоритм цього методу викладено як у табличній формі, зручній для сприйняття, так і у формі, зручній для програмування. Цей метод ілюструється числовим прикладом.
Посилання
2. Korte B., Vygen J. Combinatorial optimization: Theory and algorithms. Berlin ; Heidelberg ; New York : Springer, 2012. 660 p.
3. Pardalos P.M., Du D-Z., Graham R.L. (Eds.) Handbook of combinatorial optimization. New York : Springer, 2013. 3399 p.
4. Papadimitriou C.H., Steiglitz K. Combinatorial optimization: Algorithms and complexity. Mineola (NY) : Dover Publications, 2013. 528 p.
5. Сергиенко И.В., Шило В.П. Современные подходы к решению сложных задач дискретной оптимизации. Проблемы управления и информатики. 2016. Вып. 48. № 1. С. 15–24.
6. Гуляницький Л.Ф., Рясна І.І. До формалізації задач комбінаторної оптимізації на нечітких множинах. Теорія оптимальних рішень : збірник наукових праць. 2017. Вип. 130. С. 239–250.
7. Стоян Ю.Г., Ємець О.О. Теорія і методи евклідової комбінаторної оптимізації. Київ : Ін-т системн. досліджень освіти, 1993. 188 с. URL: http://dspace.uccu.org.ua/handle/123456789/487.
8. Стоян Ю.Г., Яковлев С.В. Теория и методы евклидовой комбинаторной оптимизации: современное состояние и перспективы. Кибернетика и системный анализ. 2020. Вып. 56. № 3. С. 366–379.
9. Емец О.А., Устьян Н.Ю. Решение некоторых задач комбинаторной оптимизации на размещениях и перестановках игрового типа. Проблемы управления и информатики. 2006. Вып. 38 № 5. С. 34–45.
10. Емец О.А., Ольховская Е.В. Итерационный метод решения комбинаторных задач игрового типа на размещениях. Проблемы управления и информатики. 2011. Вып. 43. № 5. С. 52–63.
11. Морозов В.В., Шалбузов К.Д. О численном решении матричных игр специального вида. Журнал вычислительной математики и математической физики. 2014. Вып. 54. № 10. С. 1499–1504.
12. Емец О.А. Решение линейной задачи евклидовой комбинаторной оптимизации на размещениях с условием постоянства сумы элементов размещения. Кибернетика и системный анализ. 2012. Вып. 48. № 4. С. 547–557.
ISSN 
