Розв’язування комбінаторних задач ігрового типу з обмеженнями-переставляннями у обох гравців: ітераційний метод

O. O. Iemets, O. V. Olkhovskaja

Анотація


Розглянуто постановку та математичну модель ігрової задачі сільськогосподарського виробництва з обмеженнями-переставленнями, що накладаються на стратегії обох гравців. Поширено ітераційний метод на задачі комбінаторної оптимізації ігрового типу з обмеженнями, що визначаються переставленнями на стратегії обох гравців. Метод ґрунтується на розігруванні гри, за умови, що кожен гравець прагне досягнути своєї мети. Запропоновано критерії зупинки та процедури визначення результату. На основі розробленого програмного продукту проведено обчислювальні експерименти, які показують наближення платежів до ціни гри, що дає можливість наближеного знаходження мішаних стратегій гравців. Проведено теоретичну та експериментальну оцінку кількості операцій запропонованого ітераційного алгоритму.

Повний текст:

PDF

Посилання


Sergiyenko I.V., Kaspshitskaya M.F. Modeli i metody resheniya na EVM kombinatornykh zadach optimizatsii. — K.: Nauk. dumka, 1981. — 288 s.

Stoyan Yu.H., Yemets' O.O. Teoriya i metody evklidovoyi kombinatornoyi optymizatsiyi. — K.: Instytut systemnykh doslidzhen' osvity, 1993. — 188 s.

Emets O.А., Kolechkina L.N. Zadachi kombinatornoy optimizatsii s drobno-lineynymi tselevymi funktsiyami. — K.: Nauk. dumka, 2005. — 117 s.

Emets O.А., Romanova N.G. Optimizatsiya na poliperestanovkakh. — K.: Nauk. dumka, 2010. — 105 s.

Emets O.А., Barbolina T.N. Kombinatornaya optimizatsiya na razmeshcheniyakh. — K.: Nauk. dumka, 2008. — 159 s.

Pavlov A.A., Pavlova L.А. Osnovy metodologii proyektirovaniya PDS-algoritmov dlya trudnoreshayemykh kombinatornykh zadach // Problema informatiki i upravleniya. — 1995. — № 4. — S. 135–141.

Emets O.А., Ust’yan N.YU. Issledovaniye matematicheskikh modeley i metodov resheniya zadach na perestanovkakh igrovogo tipa // Kibernetika i sist. analiz. — 2007. — № 6. — S. 103–114.

Yemets' O.O., Ust'yan N.Yu. Rozv"yazuvannya ihrovykh zadach na perestavlennyakh // Naukovi visti NTUU "KPI". — 2007. — № 3. — S. 47–52.

Emets O.А., Ust’yan N.YU. Resheniye nekotorykh zadach kombinatornoy optimizatsii na razmeshcheniyakh i perestanovkakh igrovogo tipa // Problemy upravleniya i informatiki. — 2006. — № 3. — S. 37–47.

Emets O.А., Ust’yan N.YU. Issledovaniye zadach kombinatornoy optimizatsii igrovogo tipa na razmeshcheniyakh // Problemy upravleniya i informatiki. — 2007. — № 1. — S. 26–36.

Yemets' O.O., Ust'yan N.Yu. Odyn iteratsiynyy metod rozv"yazuvannya ihrovykh zadach na perestavlennyakh // Nauk. visti NTUU "KPI". — 2008. — № 3. — S. 5–10.

Emets O.А., Ust’yan N.YU. Igry s kombinatornymi ogranicheniyami // Kibernetika i sist. analiz. — 2008. — № 4 . — S. 134–141.

Emets O.А., Ol’khovskaya E.V. Iteratsionnyy metod resheniya kombinatornykh optimizatsionnykh zadach igrovogo tipa na razmeshcheniyakh // Problemy upravleniya i informatiki. — 2011. — № 3. — S. 69–78.

Venttsel’ E.S. Elementy teorii igr. — 2-e izd. stereotip. — M.: Fizmatgiz, 1961. — 68 s.

Hyams Daniel G. Curve Expert Software. — 2011. — http://www.curveexpert.net.

Kormen T.KH., Leyzerson CH.I., Rivest R.L., SHtayn K. Аlgoritmy: postroyeniye i analiz: per. s angl. — 2-e izd. — M.: Vil’yams, 2005. — 1296 s.


Пристатейна бібліографія ГОСТ


1. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации. — К.: Наук. думка, 1981. — 288 с.


2. Стоян Ю.Г., Ємець О.О. Теорія і методи евклідової комбінаторної оптимізації. — К.: Інститут системних досліджень освіти, 1993. — 188 с.


3. Емец О.А., Колечкина Л.Н. Задачи комбинаторной оптимизации с дробно-линейными целевыми функциями. — К.: Наук. думка, 2005. — 117 с.


4. Емец О.А., Романова Н.Г. Оптимизация на полиперестановках. — К.: Наук. думка, 2010. — 105 с.


5. Емец О.А., Барболина Т.Н. Комбинаторная оптимизация на размещениях. — К.: Наук. думка, 2008. — 159 с.


6. Павлов A.A., Павлова Л.А. Основы методологии проектирования ПДС-алгоритмов для труднорешаемых комбинаторных задач // Проблема информатики и управления. — 1995. — № 4. — С. 135–141.


7. Емец О.А., Устьян Н.Ю. Исследование математических моделей и методов решения задач на перестановках игрового типа // Кибернетика и сист. анализ. — 2007. — № 6. — С. 103–114.


8. Ємець О.О., Устьян Н.Ю. Розв’язування ігрових задач на переставленнях // Наукові вісті НТУУ "КПІ". — 2007. — № 3. — С. 47–52.


9. Емец О.А., Устьян Н.Ю. Решение некоторых задач комбинаторной оптимизации на размещениях и перестановках игрового типа // Проблемы управления и информатики. — 2006. — № 3. — С. 37–47.


10. Емец О.А., Устьян Н.Ю. Исследование задач комбинаторной оптимизации игрового типа на размещениях // Проблемы управления и информатики. — 2007. — № 1. — С. 26–36.


11. Ємець О.О., Устьян Н.Ю. Один ітераційний метод розв’язування ігрових задач на переставленнях // Наук. вісті НТУУ "КПІ". — 2008. — № 3. — С. 5–10.


12. Емец О.А., Устьян Н.Ю. Игры с комбинаторными ограничениями // Кибернетика и сист. анализ. — 2008. — № 4 . — С. 134–141.


13. Емец О.А., Ольховская Е.В. Итерационный метод решения комбинаторных оптимизационных задач игрового типа на размещениях // Проблемы управления и информатики. — 2011. — № 3. — С. 69–78.


14. Вентцель Е.С. Элементы теории игр. — 2-е изд. стереотип. — М.: Физматгиз, 1961. — 68 с.


15. Hyams Daniel G. Curve Expert Software. — 2011. — http://www.curveexpert.net.


16. Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ: пер. с англ. — 2-е изд. — М.: Вильямс, 2005. — 1296 с.

 



Посилання

  • Поки немає зовнішніх посилань.