рус eng
«ИЗВЕСТИЯ ИРКУТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА». СЕРИЯ «МАТЕМАТИКА»
«IZVESTIYA IRKUTSKOGO GOSUDARSTVENNOGO UNIVERSITETA». SERIYA «MATEMATIKA»
«THE BULLETIN OF IRKUTSK STATE UNIVERSITY». SERIES «MATHEMATICS»
ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

Список выпусков > Серия «Математика». 2024. Том 48

Алгоритм решения задачи первой фазы в игровой задаче с произвольными ситуациями

Автор(ы)
А. Р. Маматов1

1Самаркандский государственный университет им. Ш. Рашидова, Самарканд, Узбекистан

Аннотация
Рассматривается игровая задача двух лиц (игроков). Два игрока поочередно выбирают свои стратегии из соответствующих множеств. Сначала первый игрок выбирает свою стратегию, затем, зная стратегию первого игрока, второй игрок выбирает свою стратегию. Множество стратегий второго игрока зависит от стратегии первого игрока. Требуется определить: существует ли для любой стратегии первого игрока соответствующая стратегия второго игрока? Данная задача решается с помощью специальной линейной максиминной задачи со связанными переменными, решение которой сводится к определению максимального значения целевой функции двойственной к ней задачи на специальных стратегиях. Приведен алгоритм решения рассматриваемой задачи, два примера, иллюстрирующие работу алгоритма, а также результаты численных экспериментов.
Об авторах
Маматов Акмал Равшанович, канд. физ.-мат. наук, ст. науч. сотр., Самаркандский государственный университет им. Ш. Рашидова, Самарканд, 140104, Узбекистан, akmm1964@rambler.ru
Ссылка для цитирования
Mamatov A. R. Algorithm for Solving the Problem of the First Phase in a Game Problem with Arbitrary Situations // Известия Иркутского государственного университета. Серия Математика. 2024. Т. 48. C. 3–20. https://doi.org/10.26516/1997-7670.2024.48.3
Ключевые слова
игровая задача, задача первой фазы, двойственная задача, опора, алгоритм
УДК
519.6, 519.83
MSC
49M05, 91A05
DOI
https://doi.org/10.26516/1997-7670.2024.48.3
Литература
  1. Азизов И. Алгоритм вычисления 𝜖 - оптимального решения линейной максиминной задачи со связанными переменными // Весцi АН БССР. Сер. фiз.-мат. навук. 1986. № 1. С. 14–18.
  2. Falk J. E. Linear maxmin problem// Math. Program. 1973. Vol. 5, N 2. P.169–188.
  3. Федоров В. В. Численные методы максимина. М. : Наука, 1979. 280 c.
  4. Габасов Р. Методы оптимизации. Минск : Четыре четверти, 2011. 472 c.
  5. Габасов Р., Кириллова Ф. М., Тятюшкин А. И. Конструктивные методы оптимизации. Ч. 1. Линейные задачи. Минск : Университетское, 1984. 214 c.
  6. Габасов Р., Кириллова Ф. М. Методы линейного программирования. Минск : Изд. БГУ, 1977. Ч. 1. 176 с.; 1980. Ч. 3. 368 с.
  7. Иванилов Ю. П. Двойственные полуигры // Известия АН СССР. Серия техническая кибернетика. 1972. № 4. С. 3-9.
  8. Липский В. Комбинаторика для программистов. М. : Мир, 1988. 200 c.
  9. Liu June, Hong Yunfei, Zheng Yue. A New Variant of Penalty Method for Weak Linear Bilevel Programming Problems // Wuhan University Journal of Natural Sciences. 2018.Vol.23, N 4. P. 328–332. https://doi.org/10.1007/s11859-018-1330-1
  10. Liu June, Hong Yunfei, Zheng Yue. A Branch and Bound-Based Algorithm for the Weak Linear Bilevel Programming Problems // Wuhan University Journal of Natural Sciences. 2018. Vol. 23, N 6. P. 480–486. https://doi.org/10.1007/s11859-018-1352-8
  11. Маматов А. Р. Необходимые условия оптимальности «высокого порядка» в линейной максиминной задаче со связанными переменными // Журнал вычислительной математики и математической физики. 2010. Т. 50, № 6. С. 963–968.
  12. Маматов А. Р. Алгоритм решения одной игры двух лиц с передачей информации // Журнал вычислительной математики и математической физики. 2006. Т. 46, № 10. С. 1784–1789.
  13. Маматов А. Р. Алгоритм решения линейной максиминной задачи со связанными переменными // Журнал вычислительной математики и математической физики. 2005. Т. 45, № 6. С. 1044–1047.
  14. Маматов А. Р. К теории двойственности линейных максиминных задач со связанными переменными // Сибирский журнал вычислительной математики. 2007. Т. 10, №2. С.187–193.
  15. An exact penalty method for weak linear bilevel programming problem / Y. Zheng, Z. Wan, K. Sun, T. Zhang // Journal of Applied Mathematics and Computing. 2013. N 3. P. 41–49. https://doi.org/10.1007/s12190-012-0620-6
  16. Zheng Y., Fang D., Wan Z. A solution approach to the weak linear bilevel programming problems // Optimization. 2016. N 7. P. 1437–1449. https://doi.org/10.1080/02331934.2016.1154553

Полная версия (english)