Курсовая работа - Решение матричных игр + исходник Delphi + Презентация (ukr) - файл KURSOVA_ROBOTA_MATRIChNI_IGRI_36_zelens'kyj.docx

Курсовая работа - Решение матричных игр + исходник Delphi + Презентация (ukr)
скачать (644.4 kb.)
Доступные файлы (18):
KURSOVA_ROBOTA_MATRIChNI_IGRI_36_zelens'kyj.docx265kb.15.06.2011 15:47скачать
n2.cfg
n3.dof
n4.dpr
n5.exe
n6.res
n7.~dpr
n8.dcu
n9.dfm
n10.pas
n11.dcu
n12.ddp
n13.dfm
n14.pas
n15.~ddp
n16.~dfm
n17.~pas
n18.208kb.14.06.2011 11:07скачать

KURSOVA_ROBOTA_MATRIChNI_IGRI_36_zelens'kyj.docx

МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
КІРОВОГРАДСЬКИЙ ДЕРЖАВНИЙ ПЕДАГОГІЧНИЙ УНІВЕРСИТЕТ
ім. ВОЛОДИМИРА ВИННИЧЕНКА
Кафедра прикладної математики, статистики та економіки

Знаходження розв’язку матричних ігор

Курсова робота з прикладної математики

Зеленського Вадима Сергійовича

студента 36 групи

фізико-математичного факультету

Спеціальність: 6.040302 «Інформатика»
Науковий керівник:

Ізюмченко Л.В.

кандидат фізико-математичних наук, доцент


Кіровоград – 2011 р.

Зміст

ВСТУП. 3

1.Основні теоретичні поняття про матричні ігри 5

1.1.Поняття матричної гри. Задача теорії ігор. 5

1.2.Запис матричної гри у вигляді платіжної матриці 6

1.3.Поняття про нижню і верхню ціну гри. Розв’язок гри в чистих стратегіях. 6

1.4.Поняття про матричні ігри із змішаним розширенням 7

2.Методи розв’язання матричних ігор 8

1.1Розв’язання гри 22. 9

1.2Розв’язання ігор . 9

1.3Розв’язання гри m n 11

1.4Розв’язання матричних ігор із змішаним розширенням методами лінійного програмування 12

3.Про програму для розв’язання матричної гри. 15

ВИСНОВКИ 17

Список використаних джерел 18

Додаток 1. Тестування програми. 20

Додаток 2. Програмний код. 22

ВСТУП.


У процесі цілеспрямованої людської діяльності виникають ситуації, в яких інтереси окремих осіб (учасників, груп, сторін) або прямо протилежні, або, не будучи безкомпромісними, все ж таки не збігаються. Найпростішими і найбільш наочними прикладами таких ситуацій є спортивні ігри, арбітражні спори, військові навчання (маневри), боротьба між блоками виборців за своїх кандидатів, у міжнародних відносинах – відстоювання інтересів своєї держави і т. п. Тут кожний з учасників свідомо прагне домогтися найкращого результату за рахунок іншого учасника. Подібного роду ситуації зустрічаються і в різних сферах виробничої діяльності.

Гра (в математиці) – це ідеалізована математична модель колективної поведінки: кілька гравців впливають на результат гри, причому їх інтереси різні [8].

На сьогоднішній день в силу молодості теорії ігор, не існує чіткої класифікації ігор, однак можна відмітити основні напрямки, за якими здійснюватиметься класифікація ігор: кількість гравців, кількість стратегій, характер взаємовідносин, характер виграшів, вид функції виграшів тощо.

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

За видами функцій виграшів ігри поділяються на: матричні, біматричні, неперервні, сепарабельні та інші.

Одним з найпростіших, але водночас і найбільш вивчених класів ігор, є так звані матричні ігри. Матрична гра – це скінченна гра двох гравців з нульовою сумою, в якій виграші першого гравця задаються у вигляді матриці. Дослідження матричних ігор цікаве тому, що до них можуть бути наближено зведені багато ігор більш загального вигляду [3].

Актуальність: Актуальність обраної теми зумовлена широтою сфер її застосування. Теорія ігор відіграє центральну роль у теорії галузевої організації, теорії контрактів, теорії корпоративних фінансів та багатьох інших областях. Область застосування матричних ігор включає не тільки економічні дисципліни, а й біологію, політологію, військову справу та ін.

Об’єкт дослідження: Матричні ігри.

Предмет дослідження: Методи розв’язання матричних ігор. Знаходження розв’язку матричної гри методами лінійного програмування.

Мета: Дослідити методи знаходження розв’язку матричних ігор. Створити програмний додаток, який знаходить оптимальні стратегії гравців та ціну гри, заданої платіжною матрицею.



1.Основні теоретичні поняття про матричні ігри

1.1.Поняття матричної гри. Задача теорії ігор.



Регулярна дія, що виконується гравцем під час гри, називається ходом. Сукупність ходів гравця, що здійснюються ним для досягнення мети гри, називається стратегією.

Під матричною грою розуміється така гра двох гравців, при якій кожен гравець має скінчене число можливих ходів – чистих стратегій. При цьому виграш одного гравця й програш іншого при застосуванні ними визначених чистих стратегій виражається числом. Перераховані умови дозволяють записати стратегії в матрицю:

(1.1)

де – дорівнює виграшу першого (будемо позначати його А) і програшу другого (гравця В) при застосуванні ними i-тої і j-тої чистих стратегій відповідно.

Задачею теорії ігор є визначення оптимальних стратегій гравців. У матричній грі оптимальною для гравця А називається стратегія, що при багаторазовому повторенні гри забезпечує максимально можливий середній виграш, а для гравця В під оптимальною розуміється стратегія, що забезпечує йому мінімальний середній програш. При цьому передбачається, що супротивник є щонайменше таким же розумним і робить усе для того, щоб перешкодити нам домогтися своєї мети [2].



1.2.Запис матричної гри у вигляді платіжної матриці



У загальному вигляді матрична гра може бути записана наступною платіжною матрицею (рис. 1.1)





B1

B2



Bn

A1

A11

A12

...

A1n

A2

A21

A22

...

A2n



...

...

...

...

Am

Аm1

Аm2

...

Аmn


Рис. 1.1. Загальний вигляд платіжної матриці матричної гри.

де Aiназви стратегій гравця A, Bj – назви стратегій гравця B, aij– значення виграшів гравця A при виборі ним i-тої стратегії, а гравцем В – j-тої стратегії. Оскільки дана гра є грою з нульовою сумою, значення виграшу для гравця В є величиною, протилежною по знаку значенню виграшу гравця А.

1.3.Поняття про нижню і верхню ціну гри. Розв’язок гри в чистих стратегіях.



Кожен з гравців прагне максимізувати свій виграш з урахуванням поведінки протидіючого йому гравця. Тому для гравця А необхідно визначити мінімальні значення виграшів в кожній із стратегій, а потім знайти максимум з цих значень, тобто визначити величину:

Vн = maxi minjaij , (1.2)

або знайти мінімальні значення по кожному з рядків платіжної матриці, а потім визначити максимальне з цих значень. Величина Vн називається максиміном матриці або нижньою ціною гри.

Величина виграшу гравця А рівна, за означенням матричної гри, величині програшу гравця В. Тому для гравця В необхідно визначити значення:

Vв = minj maxi aij, (1.3)

або знайти максимальні значення по кожному із стовпців платіжної матриці, а потім визначити мінімальне з цих значень. Величина Vв називається мінімаксом матриці або верхньою ціною гри.

У випадку, якщо значення Vн і Vв не співпадають, при збереженні правил гри (коефіцієнтів aij ) в тривалій перспективі, вибір стратегій кожним з гравців виявляється нестійким. Стійкості він набуває лише при Vн = Vв = V. У цьому випадку говорять, що гра має розв’язок в чистих стратегіях, а стратегії, в яких досягається V, – оптимальними чистими стратегіями. Величина V називається чистою ціною гри. Ситуація (a*, b*) в антагоністичних іграх з функцією виграшу H(a, b), для якої виконується подвійна нерівність: H(a, b*) ? H(a*, b*) ? H(a*, b) для всіх стратегій a гравця A, і для всіх стратегій b для гравця B називається сідловою точкою [1].

1.4.Поняття про матричні ігри із змішаним розширенням



Дослідження в матричних іграх починається із знаходження її чистої ціни. Якщо матрична гра має розв’язок в чистих стратегіях, то знаходженням чистої ціни закінчується дослідження гри. Якщо ж в грі немає розв’язку в чистих стратегіях, то можна знайти нижню і верхню ціни цієї гри, які вказують, що гравець А не повинен сподіватися на виграш більший, ніж верхня ціна гри, і може бути упевнений в отриманні виграшу не менше нижньої ціни гри. Покращення розв’язків матричних ігор слід шукати у використанні секретності застосування чистих стратегій і можливості багатократного повторення ігор у вигляді партії. Цей результат досягається шляхом застосування чистих стратегій випадково, з певною ймовірністю.

Змішаною стратегією гравця називається певний набір чистих стратегій, застосованих відповідно до встановленого розподілу ймовірності. Матрична гра, що вирішується з використанням змішаних стратегій, називається грою із змішаним розширенням [3].

Стратегії, застосовані з ймовірністю, відмінною від нуля, називаються активними стратегіями.

Основна теорема теорії ігор (доведена фон Нейманом в 1928 році) стверджує:

Кожна матрична гра з нульовою сумою має принаймні один розв’язок, можливо в області змішаних стратегій, тобто існують стратегії й , оптимальні для обох гравців, причому

(1.4)

Число називають ціною гри.

З основної теореми випливає, що кожна скінченна гра має ціну й вона лежить між нижньою й верхньою цінами гри: Vн  V  Vв .

Крім того, якщо один з гравців дотримується своєї оптимальної змішаної стратегії, то виграш залишається незмінним і рівним ціні гри V, незалежно від того, яких стратегій дотримується інший гравець, якщо тільки він не виходить за межі своїх активних стратегій. Тому, для досягнення найбільшого гарантованого виграшу другому гравцеві також необхідно дотримуватися своєї оптимальної змішаної стратегії [2].

2.Методи розв’язання матричних ігор


Порівняно просто вирішуються ігри, у яких хоча б один гравець має всього дві чистих стратегії: гри 22, 2n, mn. Коли m, n>2 теорія ігор не має власного точного методу. Такі ігри зводяться до задач лінійного програмування й вирішуються методом симплекс-таблиць. Застосування симплекс-методу приводить до громіздких обчислень уже для гри 3x3. Для ігор більших розмірів застосовуються наближені чисельні методи.
    1. Розв’язання гри 22.


У загальному випадку гра 22 визначається матрицею

. (2.1)

Насамперед, необхідно перевірити, чи є в даної гри сідлова точка. Якщо так, то гра має розв’язок в чистих стратегіях, причому оптимальними стратегіями гравців A й B відповідно будуть чиста максимінна й чиста мінімаксна стратегії. Якщо ж гра з матрицею виграшів А не має розв’язку в чистих стратегіях, то обидва гравця мають тільки такі оптимальні стратегії, які використають всі свої чисті стратегії з додатними ймовірностями.

Нехай U = (, 1  ) – оптимальна стратегія гравця A. Тоді

; (2.2)

. (2.3)

Аналогічно, якщо = (, 1 – ) – оптимальна стратегія гравця B, то

. (2.4)
    1. Розв’язання ігор .


Для побудови розв’язків ігор 2 існує ефективний метод, що ґрунтується на простих геометричних міркуваннях. Цей метод називають графічним.

Розглянемо гру 2n: . (2.5)

Задача гравця A складається в максимізації функції

. (2.6)

Якщо, ми маємо

. (2.7)

Таким чином,v є мінімумом n лінійних функцій однієї змінної ; можна накреслити графіки цих функцій і потім максимізувати їхній мінімум g() графічними методами [7].

Приклад 1.Нехай гра задана матрицею

.

Будуємо прямі, що відповідають стратегіям гравця В мал. 2.3.

Ламана відповідає нижній границі виграшу, точка D0 на ній дає розв’язок гри: , , . (2.8)

У цьому випадку оптимальна стратегія супротивника виходить застосуванням суміші двох корисних стратегій й , що перетинаються в крапці К. Стратегія є свідомо вигідною при оптимальних стратегіях.

, (2.9)

. (2.10)
Рис. 2.1. Ілюстрація Рис. 2.2. Ілюстрація

розв’язку гри . розв’язку гри .

Укажемо основні етапи знаходження розв’язку гри 2n (m2):

1) Будуємо прямі, що відповідають стратегіям другого (першого) гравця.

2) Визначаємо нижню (верхню) огинаючу графіків, що відповідають стовпцям (рядкам).

3) Знаходимо дві стратегії другого (першого) гравця, яким відповідають дві прямі, що перетинаються в точці з максимальною (мінімальною) ординатою.

4) Визначаємо ціну гри й оптимальні стратегії гравців.

    1. Розв’язання гри m n


У деяких випадках ігри більших розмірів можна спростити й привести до малих розмірів. В основі такого перетворення лежить поняття домінування стратегій.

Нехай дана m n – гра А. Говорять, що i-а стратегія гравця A домінує над його k-ю стратегією, якщо для всіх j = 1,2,…,n... Говорять, що j-та стратегія гравця B домінує над його l-ту стратегією, якщо для всіх i=1,2,…,m....
      З означення видно, що домінуюча стратегія дає гравцеві виграш не менший, ніж недомінуюча. Звідси випливає, що гравець завжди може обійтися без домінуючих стратегій, зокрема, якщо є однакові стратегії, то він може застосовувати тільки одну з них. Тому в матриці А домінуючі стратегії (рядки або стовпці) можуть бути відкинуті, а це приводить до матриці малих розмірів. У результаті виконання домінування виходить гра, еквівалентна первинній [7].

Теорема. Нехай (x,y) – сідлова точка m n - гри А, а () – сідлова точка - гри A' (), отриманої з А в результаті виключення домінуючих стратегій. Тоді , для всіх недомінуючихi, j: =0,, для всіх домінуючихi:

Приклад 2. Розглянемо спрощення гри А:



Рис.2.3. Спрощення гри А.

Стрілками показані домінуючі стратегії. Одержали 2х2-гру, у якій всі стратегії недомінуючі. Гра еквівалентна первісній грі А, тобто оптимальні стратегії в грі А мають вигляд x=(0,), .

У результаті замість гри А ми можемо розв’язати більш просту гру .

Тепер ми можемо вказати загальний порядок розв’язання матричної гри:

  1. перевірити, чи існує розв’язок в чистих стратегіях; якщо так, то гра вирішена;

  2. якщо немає розв’язку в чистих стратегіях, то виконати домінування;

  3. знайти розв’язок в змішаних стратегіях.
    1. Розв’язання матричних ігор із змішаним розширенням методами лінійного програмування



Розв’язання матричної гри із змішаним розширенням – це визначення оптимальних змішаних стратегій, тобто знаходження таких значень ймовірності вибору чистих стратегій для обох гравців, при яких вони досягають найбільшого виграшу.




1

2

.

n

A1

A11

A12

...

A1n

A2

A21

A22

...

A2n



...

...

...

...

Am

Аm1

Аm2

...

Аmn


Рис. 2.4. Загальний вид платіжної матриці матричної гри.

Для матричної гри, платіжна матриця якої показана на рис. 2.4,

VнVв, визначимо такі значення ймовірності вибору стратегій для гравця А (p1, p2, ..., pm) і для гравця В (q1, q2, ..., qn), при яких гравці досягали б свого максимально гарантованого виграшу.

Якщо один з гравців дотримується своєї оптимальної стратегії, то, за умовою задачі, його виграш не може бути менше ціни гри V. Тому дана задача може бути представлена для гравців у вигляді наступних систем лінійних нерівностей:

Для першого гравця:

Для другого гравця:



Щоб визначити значення V, розділимо обидві частини кожного з рівнянь на V. Величину pi/V позначимо через xi, а qj/V – через yj.

Для гравця А отримаємо таку систему нерівностей, з якої знайдемо значення 1/v.

Для гравця А необхідно знайти максимальну ціну гри (V). Отже, значення 1/V повинне прямувати до мінімуму.

Цільова функція задачі матиме наступний вигляд:

min Z = min 1/V = min (x1 + x2 + … + xm)

Для гравця В отримаємо наступну систему нерівностей, з якої знайдемо значення 1/v:



Для гравця В необхідно знайти мінімальну ціну гри (V). Отже, значення 1/V повинне прямувати до максимуму.

Цільова функція задачі матиме наступний вигляд:

max Z = max 1/V = max (y1+ y2 + ... + yn)

Всі змінні в даних системах лінійних нерівностей повинні бути невід’ємними: xi = pi/V, а yi = qj/V. Значення pi і qj не можуть бути від’ємними, оскільки є значеннями ймовірності вибору стратегій гравців. Тому необхідно, щоб значення ціни гри V не було від’ємним. Ціна гри обчислюється на основі коефіцієнтів виграшів платіжної матриці. Тому, для того, щоб гарантувати умову додатності для всіх змінних, необхідно, щоб всі коефіцієнти матриці були невід’ємними. Цього можна добитися, додавши перед початком розв’язання задачі до кожного коефіцієнта матриці число K, відповідне модулю найменшого від’ємного коефіцієнта матриці. Тоді в ході розв’язання задачі буде визначена не ціна гри, а величина

V* = V + K.

Для розв’язання задач лінійного програмування використовується симплекс-метод. У результаті розв’язку визначаються значення цільових функцій (для обох гравців ці значення співпадають), а також значення змінних xi і yj.

Величина V* визначається по формулі: V* = 1/z. (2.18)

Значення ймовірності вибору стратегій визначаються: для гравця А:

Pi = xiV*,

і для гравця В: qi = yiV*. (2.19)

Для визначення ціни гри V від величини V* необхідно відняти число K [6].

3.Про програму для розв’язання матричної гри.


Написана мною програма знаходить ціну та оптимальні стратегії гравців матричної гри, заданої платіжною матрицею m х n.

Вхідні данні: m – кількість рядків матриці, n – кількість стовпців матриці, платіжна матриця розмірністю m х n. Є можливість авто заповнення випадковими числами від -10 до 10;

Вихідні данні: верхня й нижня ціна гри, загальна ціна гри v, ймовірності застосування кожної стратегії гравця А, для одержання ним максимального виграшу, ймовірності застосування кожної стратегії гравця В, для одержання ним мінімального програшу.

Алгоритм роботи програми:

  1. Знаходимо верхню та нижню ціни гри (мінімакс і максимін) [п. 1.2].

  2. Якщо верхня та нижня ціна гри рівні, то існує сідлова точка Aij, тоді стратегії Аі та Bj будуть чистими оптимальними стратегіями гри, переходимо до пункту 7;

  3. Якщо сідлової точки не існує, то виконуємо виключення не вигідних стратегій, в результаті чого зменшується розмірність матриці [п. 2.3].

  4. Знаходимо мінімальний елемент матриці. Якщо він від’ємний, то почергово додаємо його абсолютне значення до кожного елемента матриці.

  5. Розглядаємо отриману матрицю, як матрицю коефіцієнтів системи обмежень задачі лінійного програмування та знаходимо розв’язок цієї задачі та двоїстої до неї за допомогою симплекс-методу [п. 2.4].

  6. Знаходимо ціну матричної гри та ймовірності застосування кожної стратегії.

  7. Виводимо результат.

Програма написана на об’єктно-орієнтовній мові Delphi в середовищі Delphi 7.0. У програмі є візуальна оболонка, яка нам надає зручний інтерфейс користувача.


ВИСНОВКИ


Матричні ігри широко використовуються в системах прийняття рішень. Вони можуть служити математичними моделями багатьох найпростіших конфліктних ситуацій з галузі економіки, математичної статистики, військового справи, біології. Нерідко в якості одного із гравців розглядають «природу», під якою розуміється вся сукупність зовнішніх обставин, невідомих іншому гравцеві.

У своїй курсовій роботі я розглянув методи знаходження розв’язків матричних ігор та процес зведення матричної гри до задачі лінійного програмування, знаходження розв’язків симплекс-методом. Розглянув стан досліджуваної проблеми в літературі. Написав програму, яка знаходить ціну гри та оптимальні стратегії гравців матричної гри, заданої платіжною матрицею n x m. Програма реалізує розглянуті мною методи для розв’язання матричних ігор. Головне – жоден із цих методів не виключає необхідності думати. Але не просто думати, а користуватися при цьому математичними розрахунками, пам'ятаючи слова Хеммінга, – «головна мета розрахунків – не цифри, а розуміння».

Отримані результати курсової роботи можуть бути використані в навчальному процесі студентів під час вивчення курсу «Методи оптимізації та дослідження операцій».

Список використаних джерел


  1. Шишкин Е.В., Чхартишвили А.Г. Математические методы и модели в управлении: Учеб. пособие. – М.: Дело, 2000.– 768 с.

  2. Лапшин К.А. Методические указания для студентов экономического факультета «Игровые модели и принятие решений». – М. 2001.– 452 с.

  3. Зайченко Ю.П. Исследование операций. – К.: Слово, 2003. – 688 с.

  4. Гольштейн Е.Г., Юдин Д.Б. Нове направления в линейном программировании и ёё приложение. – М.: Наука, 1966. – 351 с.

  5. Давыдов Э.Г. Исследование операций. – М.: Высш. шк., 1990. – 383 с.

  6. Лэдсон Л. Оптимизация больших систем. – М.: Наука, 1975. – 431 с.

  7. Цукров В.И. Декомпозиционные методы решения задач большой размерности. – М.: Наука, 1981. – 234 с.

  8. Чеснокова О. В. Delphi 7. Алгоритмы и програмы. – М. : Пресс, 2008. – 368 с.

  9. http://www.math.kemsu.ru

  10. http://www.sosh.ru

  11. Федоренко І.К., Черняк О.І., Карагодова О.О., Чорноус Г.О., Горбунов О.В. Дослідження операцій в економіці: Підручник / За ред.. І.К. Федоренко, О.І. Черняка. – К.: Знання, 2007. – 558 с.

  12. Боровик О.В., Боровик Л.В. Дослідження операцій в економіці. Навч.посіб. – К.: Центр учбової літератури, 2007. – 424 с.

  13. Охріменко М.Г., Дзюбан І.Ю. Дослідження операцій. Навч.посіб. – К.: Центр учбової літератури, 2006. – 184 с.

  14. Ржевський С.В., Александрова В.М. Дослідження операцій. Підручник. – К.: Академвидав, 2006. – 558 с.

  15. Ляпин Е.С., Евсеев А.Е. Алгебра и теория чисел. Ч. ІІ. Учеб.пособие для студентов физ.-мат.фак.пед.ин-тов. – М.: Просвещение, 1978. – 448 с.

  16. Лященко М.Я., Головань М.С. Чисельні методи: Підручник. – К.: Либідь, 1996. – 288 с.

  17. Овчинников П.П., Михайленко В.М. Вища математика: Підручник. Ч. 2. – К.: Техніка, 2004. – 792 с.

  18. Солодовников А.С. Системы линейных неравенств. – М.: Наука, 1977. – 112 с.



Додаток 1. Тестування програми.


Для тестування програмо візьмемо розв’язаний приклад матричної гри із підручника [14] і розв’яжемо його за допомогою нашої програми, потім порівняємо результати.

Гра задана платіжною матрицею:




Стратегії гравця В

В1

В2

В3

В4

В5

В6


Стратегії гравця А

А1

4

-2

5

1

2

7

А2

1

2

4

3

0

10

А3

3

5

6

7

1

9

А4

1

2

4

3

0

10

А5

2

1

3

6

5

4



1.Введемо цю матрицю в нашу програму:




  1. Натиснемо кнопку «Порахувати» і зліва отримаємо результат.



Перевірка отриманих результатів

Отримані результати зійшлися з результатами в підручнику, робимо висновок, що програма працює правильно.

Також для перевірки результату можна використати вбудовані функції табличного процесору MS Excel.


Додаток 2. Програмний код.


unit Unit2;
interface
uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, Grids, ComCtrls, Buttons, XPMan;
type

matrix = array[1..550, 1..550] of double;

TForm2 = class(TForm)

Label1: TLabel;

SG: TStringGrid;

Edit1: TEdit;

Label2: TLabel;

Label3: TLabel;

Edit2: TEdit;

Button1: TButton;

UpDown1: TUpDown;

UpDown2: TUpDown;

Button2: TButton;

ListBox1: TListBox;

XPManifest1: TXPManifest;

Label4: TLabel;

CheckBox1: TCheckBox;

Button3: TButton;

procedure Button1Click(Sender: TObject);

procedure UpDown2Click(Sender: TObject; Button: TUDBtnType);

procedure minimax();

procedure Button2Click(Sender: TObject);

procedure optR(Var a1: matrix; var n1, m1:integer;var flag:boolean);

procedure optS(Var a1: matrix; var n1, m1:integer;var flag:boolean);

Procedure DelR(Var X : matrix; Var nn, mm : integer; k1 : integer);

// procedure printA;

Procedure DelS(Var X : matrix; Var nn, mm : integer; k1 : integer);

procedure UpDown1Click(Sender: TObject; Button: TUDBtnType);

procedure Dsimpl;

procedure simplM;

procedure Edit1Change(Sender: TObject);

procedure Edit2Change(Sender: TObject);

procedure FormCreate(Sender: TObject);

procedure Button3Click(Sender: TObject);

procedure FormKeyPress(Sender: TObject; var Key: Char);
private

{ Private declarations }

public
{ Public declarations }

end;

const mm = 550; nn = 550;

var

A : matrix;

Form2: TForm2;

n,m,i,j,pn,qm,maxj,mini:integer;

min,max,minA,v:real;

fun : array[1..nn] of integer;

basis : array[1..nn] of integer;

xx,yy,p,q : array[1..nn] of double;

Ad : matrix;

implementation
{$R *.dfm}
{//------------------PRINT--------

procedure Tform2.printA;

begin

stringgrid1.RowCount:=n+4;

stringgrid1.colCount:=m+4;

for i:=1 to n+4 do

for j:=1 to m+4 do

stringgrid1.Cells[j-1,i-1]:=floattostr(ad[i,j]);

end;}

//----------Реалізація алгоритму----------------

procedure TForm2.Button1Click(Sender: TObject);

var flg,sid:boolean;

begin
n:=SG.RowCount-1;

m:=sg.ColCount-1;

flg:=true;

sid:=false;

pn:=0; qm:=0;
for i:=1 to pn do //

p[i]:=0;

xx[i]:=0; // Обнуляємо масиви

for i:=1 to qm do

yy[i]:=0; //

q[i]:=0 ; //
try

for i:=1 to n do //

for j:=1 to m do // Зчитування даних

A[i,j]:=strtofloat(sg.cells[j,i]); //

except

on Exception : EConvertError do

begin

ShowMessage('Помилка чтиання. Перевірте правильнысть введених данних');

Exit;

end;

end;
minimax; // Мінімакс
if checkbox1.Checked then

begin

listbox1.Items.Add('Нижня ціна = '+floattostr(min)); // виводимо верхню й

listbox1.Items.Add('Верхня ціна = '+floattostr(max)); // нижню ціну гри

end;

if max=min then begin //перевіряємо існування сідлової точки

v:=a[mini,maxj];

p[mini]:=1;

q[maxj]:=1;

listbox1.Items.Add('Гра має розвязок в чистих стратегіях:');

listbox1.Items.Add('ціна гри = '+floattostr(min));

listbox1.Items.Add('Оптимальна стратегія гравця А - A'+inttostr(mini));

listbox1.Items.Add('Оптимальна стратегія гравця B - A'+inttostr(maxj));
end

else //сідлової точки не існує

begin

listbox1.Items.Add('Гра не має розвязку в чистих стратегіях');

if checkbox1.Checked then

listbox1.Items.Add('Шукаємо розвязок в змішаних стратегіях.');

for i:=1 to n do

a[i,m+1]:=i;
for j:=1 to m do

a[n+1,j]:=j;
while flg do //

begin // Виключення невигыдних стратегій

optR(a,n,m,flg); // (якщо є домінуюча, то виключаємо)

optS(a,n,m,flg); //

end;
for i:=1 to n do

p[round(a[i,m+qm+1])]:=1;

for i:=1 to m do

q[round(a[n+pn+1,i])]:=1 ;


minA:=a[1,1];

for i:=1 to n do //

for j:=1 to m do // Пошук мін. елемента матриці

if minA>a[i,j] then minA:=a[i,j]; //
for i:=1 to n do //

for j:=1 to m do // a[i,j]>=0, i=1..n,j=1..m;

a[i,j]:=a[i,j]+abs(minA); //
// form2.printA;
//for i:=1 to n do

//a[i,m+1]:=0;
//for j:=1 to m do

//a[n+1,j]:=0;

form2.simplM;

// симплекс метод

j:=1;

for i:=1 to sg.RowCount do

if p[i]=1 then

begin

p[i]:=yy[j]*v;

inc(j);

end;
j:=1;

for i:=1 to sg.colCount do

if q[i]=1 then

begin

q[i]:=xx[j]*v;

inc(j);

end;
v:=v-abs(minA);

with listbox1.Items do

begin

if checkbox1.Checked then

begin//---Вивод результатів----

Add('Гра зводиться до двоїстої задачі ЛП:');

Add('MaxZ = x1 ');

for i:=2 to m do

Strings[Count-1]:=Strings[Count-1]+'+ x'+inttostr(i);

Add('__');

for i:=1 to n do

begin

Add('| '+floattostr(a[i,1])+'*x1');

for j:=2 to m do

Strings[Count-1]:=Strings[Count-1]+' + '+floattostr(a[i,j])+'*x'+inttostr(j);

Strings[Count-1]:=Strings[Count-1]+' >= 1';

end;

Add('__');
Add('Двоїста:');

Add('MaxL = y1 ');

for i:=1 to n do

Strings[Count-1]:=Strings[Count-1]+'+ y'+inttostr(i);

Add('__');

for j:=1 to m do

begin

Add('| '+floattostr(a[1,j])+'*y1');

for i:=2 to n do

Strings[Count-1]:=Strings[Count-1]+' + '+floattostr(a[i,j])+'*Y'+inttostr(i);

Strings[Count-1]:=Strings[Count-1]+' <= 1';

end;

Add('__');
Add('Рзвязок задчі ЛП:');

for i := 1 to m do

Add('x['+inttostr(i)+'] = '+floattostr(xx[i]));

for i := 1 to n do

Add('y['+inttostr(i)+'] = '+floattostr(yy[i]));

Add('MaxZ = MaxL = '+floattostr(Ad[n+1, m+n+1]));

end;///

Add('Розвязок матричної гри:');

Add('Ціна гри = '+floattostr(v));

Add('Оптимальна стратегія гравця А:');

for i := 1 to sg.RowCount-2 do

Add('A['+inttostr(i)+'] з ймовірністю '+floattostr(p[i]));

listbox1.Items.Add('Оптимальна стратегія гравця B:');

for i := 1 to sg.colCount-2 do

Add('B['+inttostr(i)+'] з ймовірністю '+floattostr(q[i]));
if (m>5) or (n>5) then listbox1.Width:=listbox1.Width+round(m/5)*listbox1.Width;

end;
end;//---

end;

procedure TForm2.UpDown2Click(Sender: TObject; Button: TUDBtnType);

begin

edit2.Text:=inttostr(updown2.Position);

end;

//---------------ДОМІНУВАННЯ ПО РЯДКАХ---------

procedure tform2.optR(Var a1: matrix; var n1, m1:integer; var flag:boolean);

label start;

var i1, j1,k : integer;

//del:array[1..100] of integer;
begin

flag:=false;

start:

for k:=1 to n1 do

begin;

for i1:=1 to n1 do

begin

for j1:=1 to m1 do

begin

if a1[k,j1]>a1[i1,j1] then break;

if (k<>i1) and (j1=m1) then

begin

form2.DelR(a1,n1,m1,k); inc(pn);flag:=true; goto start;

end;

end;

end;
end;

end;
//---------------ДОМІНУВАННЯ СТОВПЦІВ---------

procedure tform2.optS(Var a1: matrix; var n1, m1:integer;var flag:boolean);

label start;

var i1, j1,k : integer;

//del:array[1..100] of integer;

begin

flag:=false;

start:

for k:=1 to m1 do

begin;

for j1:=1 to m1 do

begin

for i1:=1 to n1 do

begin

if a1[i1,k]
if (k<>j1) and (i1=n1) then

begin

form2.DelS(a1,n1,m1,k);

inc(qm);

flag:=true; goto start;

end;

end;

end;
end;

end;

//----------DELETEr------------

Procedure tform2.DelR(Var X : matrix; Var nn, mm : integer; k1 : integer);

Var

ii, jj : integer;

Begin

for ii := k1 to nn+pn do

for jj := 1 to mm+qm+1 do

X[ii, jj] := X[ii+1, jj];

//for jj := 1 to mm do

//X[nn, jj] := 0;

Dec(nn);

End;

//---------------------------
//----------DELETEs------------

Procedure tform2.DelS(Var X : matrix; Var nn, mm : integer; k1 : integer);

Var

ii, jj : integer;

Begin

for jj := k1 to mm+qm do

for ii := 1 to nn+pn+1 do

X[ii, jj] := X[ii, jj+1];

//for ii := 1 to nn do

// X[nn, jj] := 0;

Dec(mm);

End;

//------------------------------

procedure tform2.minimax();
begin

with form2 do

begin
SG.RowCount:=SG.rowCount+1;

SG.colCount:=SG.colCount+1;

sg.Cells[SG.colCount-1,0]:='minA';

sg.Cells[0,SG.RowCount-1]:='maxB';

//_______МАКСІМІН

for i:=1 to n do

begin

min:=a[i,1];

for j:=1 to m do

begin

if a[i,j]
min:=a[i,j];

end;

a[i,m+1]:=min;

SG.Cells[SG.colcount-1,i]:=floattostr(min);

end;

min:=a[1,m+1];
mini:=1;

for i:=1 to n do

if min
min:=a[i,m+1];

mini:=i;

end;
//_______МІНІМАКС

for j:=1 to m do

begin

max:=a[1,j];

for i:=1 to n do

begin

if a[i,j]>max then

max:=a[i,j];

end;

a[n+1,j]:=max;

SG.Cells[j,SG.rowcount-1]:=floattostr(max);

end;

//--------------

maxj:=1;

max:=a[n+1,1];

for j:=1 to m do

if max>a[n+1,j] then begin

max:=a[n+1,j];

maxj:=j;

end;

//-------------

end;

end;

////////////////////////////////////////////////


procedure TForm2.Button2Click(Sender: TObject);

begin

randomize;

for i:=1 to sg.RowCount-1 do

for j:=1 to sg.ColCount-1 do

sg.Cells[j,i]:=floattostr((random(100)-50)/8);

end;
procedure TForm2.UpDown1Click(Sender: TObject; Button: TUDBtnType);

begin

edit1.Text:=inttostr(updown1.Position);

end;
procedure TForm2.Dsimpl;
var i0, j0 : integer;

tmp : double;

opt : boolean;

begin
opt := false;

repeat

j0 := 1; i0 := 0;

while (j0 < m+n+1) and (Ad[m+1, j0] >= 0) do inc(j0);

if Ad[m+1, j0] >= 0 then opt := true;
if not opt then begin

tmp := 10000;

for i := 1 to m do

if (Ad[i, j0] > 0) and (Ad[i, m+n+1] / Ad[i, j0] < tmp) then

begin

tmp := Ad[i, m+n+1] / Ad[i, j0]; i0 := i

end;

// i0 - виводимо, j0 - додаємо

basis[i0] := j0; //дбавлення нового элемента в базис

// [i0, j0] - розвязуючий елемент:

for i := 1 to m + 1 do

if i <> i0 then

begin

tmp := Ad[i, j0];

for j := 1 to m + n + 1 do

Ad[i,j] := Ad[i,j] - Ad[i0,j]*tmp/Ad[i0,j0];

end;

tmp := Ad[i0, j0];

for j := 1 to m + n + 1 do

Ad[i0, j] := Ad[i0, j] / tmp;

end;

until opt;

end;
//---------------------------

procedure tform2.simplm;

var tk:integer;

begin

for i := 1 to n do

for j := 1 to m do

ad[i,j]:=a[i,j];
tk:=n;

n:=m;

m:=tk;

for i := 1 to n do fun[i]:=1; //заповняємо z
for i := 1 to m do

Ad[i, n+m+1]:=1;

for i := 1 to m do // Ljgjvs;ys pvsyys

Ad[i, n+i] := 1;

fillchar(Ad[m+1], sizeof(Ad[m+1]), 0);
// базис

for i := 1 to m do

basis[i] := n + i;

for j := 1 to n do

Ad[m+1,j] := -fun[j]; // для небаз. = -fun[j], для базисних - 0

form2.Dsimpl; // DO IT! +)
// -- базис --

for i := 1 to m+5 do

if basis[i] <= n then

xx[basis[i]] := Ad[i, m+n+1];
for j := 1 to n+5 do

//if basis[i] <= n then

yy[j] := Ad[m+1, n+j];


v:=exp(-1*ln(Ad[m+1, m+n+1]));//-minA;

tk:=n;

n:=m;

m:=tk;
end;
procedure TForm2.Edit1Change(Sender: TObject);

var x:integer;

begin

x:=strtoint(edit1.Text);

sg.RowCount:=x+1;

for i:=1 to SG.RowCount do

sg.Cells[0,i]:='A'+IntToStr(i);

end;

procedure TForm2.Edit2Change(Sender: TObject);

var x:integer;

begin

x:=strtoint(edit2.Text);

sg.colCount:=x+1;

for i:=1 to SG.colCount do

sg.Cells[i,0]:='B'+IntToStr(i);

end;

procedure TForm2.FormCreate(Sender: TObject);

begin

form2.Edit1Change(application);

form2.Edit2Change(application);

end;
procedure TForm2.Button3Click(Sender: TObject);

begin

with Sg do

for i:=0 to ColCount-1 do

Cols[i].Clear;

for i:=1 to n+m+2 do

for j:=1 to m+m+2 do

ad[i,j]:=0;

form2.Edit1Change(application);

form2.Edit2Change(application);

listbox1.Width:=361;

listbox1.Clear;
end;
procedure TForm2.FormKeyPress(Sender: TObject; var Key: Char);

begin

if not (Key in ['0'..'9'] + ['-',',']) then Key:=#0;

end;




Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации