Лінійне програмування 2 лютого

Зміст

Зміст

1. Пояснювальна записка

1.1.Введеніе

2. Теоретична частина

2.1 Елементи теорії матричних ігор

2.2 Рішення матричних ігор у чистих стратегіях

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

3. Практична частина

3.1 Побудова математичної моделі задачі

3.2 Вибір методу рішення і привиди завдання до канонічного вигляду

3.3 Рішення задачі шляхом зведення до задачі лінійного програмування

- Блок схема до поставленого завдання

- Програма до поставленого завдання (програмний код)

3.4 Аналіз результату вирішення поставленого завдання

4. Висновок курсового проектування

Висновок

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

1. Пояснювальна записка курсового проектування

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

1. КОРОТКИЙ ОГЛЯД АЛГОРИТМІВ РІШЕННЯ ЗАДАЧ ЦЬОГО ТИПУ 1.1 Математичне програмування.

Математичне програмування займається вивчення екстремальних завдань і пошуком методів їх вирішення. Завдання математичного програмування формулюються наступним чином: знайти екстремум деякої функції багатьох змінних f (x1, x2, ..., xn) при обмеженнях gi (x1, x2, ..., xn) (bi, де gi - функція, що описує обмеження, (- один з наступних знаків (, (, (, а bi - дійсне число, i = 1, ..., m. f називається функцією цілі (цільова функція). Лінійне програмування - це розділ математичного програмування, в якому розглядаються методи рішення екстремальних задач з лінійним функціоналом і лінійними обмеженнями, яким повинні задовольняти шукані змінні. Задачу лінійного програмування можна сформулювати так. Знайти max [pic] за умови: a11 x1 + a12 x2 +... + a1n xn (b1; a21 x1 + a22 x2 +... + a2n xn (b2;............................ am1 x1 + am2 x2 +... + amn xn (bm; x1 (0, x2 (0,..., xn (0. Ці обмеження називаються умовами не заперечності. Якщо всі обмеження задані у вигляді строгих рівностей, то дана форма називається канонічною. У матричній формі задачу лінійного програмування, записують наступним чином. Знайти max cT x за умови A x (b; x (0, де А - матриця обмежень розміром (m (n), b (m (1) - вектор-стовпець вільних членів, x (n (1) - вектор змінних, ст = [c1, c2, ..., cn] - вектор-рядок коефіцієнтів цільової функції. Рішення х0 називається оптимальним, якщо для нього виконується умова ст х0 (СТ х, для всіх х (R (x). Оскільки min f (x) еквівалентний max [- f (x)], то завдання лінійного програмування завжди можна звести до еквівалентної задачі максимізації. Для вирішення завдань цього типу застосовуються методи:

1) графічний;

2) табличний (прямий, простий) симплекс - метод;

3) метод штучного базису;

4) модифікований симплекс - метод;

5) двоїстий симплекс - метод.

1.2 Табличний симплекс - метод Для його застосування необхідно, щоб знаки в обмеженнях мали вигляд "менше або дорівнює", а компоненти вектора b - позитивні. Алгоритм рішення зводиться до наступного:

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

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

3. Формується симплекс-таблиця.

4. Розраховуються симплекс-різниці.

5. Приймається рішення про закінчення або продовження рахунку.

6. При необхідності виконуються ітерації.

7. На кожній ітерації визначається вектор, що вводиться в базис, і вектор, що виводиться з базису. Таблиця перераховується за методом Жордана Гауса або яким-небудь іншим способом.

1.3 Метод штучного базису. Даний метод рішення застосовується при наявності в обмеженні знаків "дорівнює", "більше або дорівнює", "менше або дорівнює" і є модифікацією табличного методу. Рішення системи виробляється шляхом введення штучних змінних зі знаком, що залежать від типу оптимуму, тобто для виключення з базису цих змінних останні вводяться в цільову функцію з великими негативними коефіцієнтами, а в завдання мінімізації з позитивними. Таким чином, з вихідної виходить нове завдання. Якщо в оптимальному вирішенні завдання немає штучних змінних, це рішення є оптимальне рішення вихідної задачі. Якщо ж в оптимальному вирішенні завдання хоч одна з штучних змінних буде відмінна від нуля, то система обмежень вихідної задачі несовместна і вихідна задача нерозв'язна.

1.4 Модифікований симплекс-метод. В основу даного різновиду симплекс-методу покладені такі особливості лінійної алгебри, які дозволяють у ході виконання завдання працювати з частиною матриці обмежень. Іноді метод називають методом зворотної матриці. У процесі роботи алгоритму відбувається спонтанне звернення матриці обмежень по частинах, відповідними поточними базисним векторам. Зазначена здатність робить вельми привабливою машинну реалізацію обчислень внаслідок економії пам'яті під проміжні змінні і значного скорочення часу рахунку. Хороший для ситуацій, коли число змінних n значно перевищує число обмежень m. У цілому, метод відображає традиційні риси загального підходу до вирішення завдань лінійного програмування, що включає в себе канонізацію умов завдання, розрахунок симплекс-різниць, перевірку умов оптимальності, прийняття рішень про корекцію базису і виключення Жордана Гаусса. Особливості полягають у наявності двох таблиць - основний і допоміжної, порядок їх заповнення та деякою специфічності розрахункових формул.

ПОСТАНОВКА ЗАДАЧІ:

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

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

Відповідно:

1. Перше з чого починаємо, це будуємо математичну модель задачі;

2. Вибираємо метод рішення задачі і наводимо завдання до канонічного вигляду;

3. Вирішуємо задачу шляхом зведення до задачі лінійного програмування;

4. Потім будуємо блок схему до завдання з написанням програми на мові С + + Builder 6.;

5. Подальшим етапом моєї роботи буде аналіз результату рішення виконаної мною завдання.

1.1 Введення

1 Математичні методи

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

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

Загальне в моделях те, що у всіх випадках модель у певному сенсі заміняла сам досліджуваний об'єкт. Замість вихідного об'єкта (оригіналу) використовувалася його модель, модель була поданням об'єкта в певній формі, відмінній від форми його реального існування.

Модель - це матеріальний або ідеальний об'єкт, який будується для вивчення вихідного об'єкта (оригіналу) і який відображає найбільш важливі якості і параметри оригіналу.

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

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

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

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

Практично у всіх науках побудова і використання моделей є потужним знаряддям пізнання.

У моделюванні існує два шляхи:

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

Модель може відображати реальність більш абстрактно - словесним описом формалізованим з яких - то правилами, співвідношенням.

Існує наступна класифікація абстрактних моделей:

Вербальні

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

Математичні

Це дуже широкий клас знакових моделей, заснованих на формальних мовах над кінцевими алфавітами, що широко використовують ті чи інші математичні методи.

Інформаційні

Це клас знакових моделей описують інформаційні процеси в системах найрізноманітнішої природи.

Кордон між вербальними, математичними та інформаційними моделями може бути проведена досить умовно; можна вважати інформаційні методики підкласом математичних моделей.

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

Поняття «аналітичне» рішення і «комп'ютерне» рішення не протистоять один одному, тому що:

Все частіше комп'ютери при математичному моделюванні використовуються не тільки для чисельних розрахунків, але і для аналітичних перетворень.

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

2 Симплекс метод рішення завдань лінійного програмування

Симплекс метод - універсальний метод для розв'язання лінійної системи рівнянь або нерівностей і лінійного функціоналу.

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

1. Обмеження виду «» - ресурсні обмеження. Справа знаходиться те що ми використовуємо на виробництві, зліва - то що отримуємо. За таких обмеження вводять додаткові змінні з коефіцієнтом «+1», утворюють одиничний базис. У цільову функцію ці змінні увійдуть з коефіцієнтом «0».

2. Обмеження виду «=». Часто буває, що незважаючи на те що обмеження мають вигляд рівності, одиничний базис не виділяється або важко виділяється. У цьому випадку вводяться штучні змінні для створення одиничного базису - Yi. У систему обмежень вони входять з коефіцієнтом «1», а в цільову функцію з коефіцієнтом «M», що прагнуть до нескінченності (при Fmin - «+ M», при Fmax - «- M»).

3. Обмеження виду «» - Планові обмеження. Додаткові змінні (X), що несуть певний економічний зміст - перевитрата ресурсів або перевиконання плану, перевиробництво, додаються з коефіцієнтом «-1», в цільову функцію - з коефіцієнтом «0». А штучні змінні (Y) як у попередньому випадку.

Алгоритм симплекс методу.

(Перша симплекс таблиця)

Нехай система приведена до канонічного вигляду.

X 1 + q 1, m +1 Xm +1 + .... + Q 1, m + n Xm + n = h 1

X 2 + q 1, m +1 Xm +1 + .... + Q 1, m + n Xm + n = h 1

X 3 + q 1, m +1 Xm +1 + .... + Q 1, m + n Xm + n = h 1

... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ....

Xm + qm, m +1 Xm +1 + .... + Qm, m + n Xm + n = hm

У ній m базисних змінних, k вільних змінних. M + k = n - всього змінних.

Fmin = C 1 X 1 + C 2 X 2 + C 3 X 3 +....+ CnXn

Всі hi повинні бути більше або дорівнюють нулю, де i = 1,2 ... m. На першому кроці як допустимого рішення приймаємо всі Xj = 0 (j = m +1, m +2 ,..., m + k). При цьому всі базисні змінні Xi = Hi.

Для подальших міркувань обчислень будемо користуватися першою симплекс таблицею (таблиця 3.1).

Таблиця 1.

Перший стовпець-коефіцієнти в цільової функції при базисних змінних.

Другий стовпець - базисні змінні.

Третій стовпець - вільні члени (hi  0).

Сама верхня рядок - коефіцієнти при цільової функції.

Друга верхній рядок - самі змінні, що входять в цільову функцію і в систему обмежень.

Основне поле симплекс методу - система коефіцієнтів з рівняння.

Останній рядок - служить для того, щоб відповісти на запитання: «оптимальний план чи ні».

Для першої ітерації F 0 =   ci * hi.

                 m - оцінки вони розраховуються за формулою:

  j =  ciqij - cj.

Індексна рядок дозволяє нам судити про оптимальність плану:

1. При знаходженні Fmin в індексному рядку повинні бути негативні і нульові оцінки.

2. При знаходженні Fmax в індексному рядку повинні бути нульові і позитивні оцінки.

Перехід до другої ітерації:

Для цього відшукуємо ключовий (головний) стовпець і ключову (головну) рядок.

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

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

На перетині рядка і стовпця знаходиться дозволяє елемент.

На цьому етапі здійснюється до переходу до подальших итерациям.

Перехід до итерациям:

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

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

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

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

5. Інші елементи переносяться за формулою:

Метод штучного базису. (Друга симплекс таблиця)

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

1. Побудова штучного базису і оптимізація функції суми штучних змінних, тобто F 0 = Y 1 + Y 2 + ... + Yn = 0 (F  min). Якщо при цьому F 0 = 0, то штучний базис ми вивели зі складу змінних, переходимо до другої фази - вирішуємо завдання по першій симплекс таблиці з дійсними змінними. Якщо ж F 0  0, тобто штучний базис не виведений зі складу змінних - ОЗЛП рішень не має.

2. Рішення перетвореної системи обмежень з заданою цільовою функцією і дійсними змінними. При цьому стовпцями штучних змінних в симплекс методі нехтуємо.

Зауваження:

1. При вирішенні завдань на max зі штучним базисом слід переходити до вирішення на min, змінюючи лише тільки цільову функцію:

Fmax = - Fmin.

2. При вирішенні ЗЛП зі штучним базисом особливу увагу слід звернути на обчислення елементів індексних рядків.

a) Для стовпців X обчислення елементів йде за формулами:

  j =  qij.

 yi = y 1 + y 2 + ... + yR.

 Hi = F 0.

Примітка: тільки для рядків Y.

б) Для стовпців Y працює стара формула:

  j =  ciqij - cj.

2. Теоретична частина

Математичні моделі

Математична модель - наближений опис об'єкта моделювання, вираженої з допомогою математичної символіки.

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

Етапи комп'ютерного математичного моделювання зображені на малюнку (1). Перший етап - Визначення цілей моделювання. Ці цілі можуть бути різними:

1. модель потрібна для того, щоб зрозуміти, як влаштований конкретний об'єкт, яка його структура, основні властивості, закони розвитку і взаємодії з навколишнім світом (розуміння);

2. модель потрібна для того, щоб навчитися управляти об'єктом (або процесом) і визначити найкращі способи управління при заданих цілях і критеріях (управління);

3. модель потрібна для того, щоб прогнозувати прямі і непрямі наслідки реалізації заданих способів і форм впливу на об'єкт (прогнозування).

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

Класифікація математичних моделей

В основу класифікації математичних моделей можна покласти різні принципи. Можна класифікувати моделі за галузями наук (математичні моделі у фізиці, біології, соціології тощо). Можна класифікувати за вживаним математичному апарату (моделі, засновані на застосуванні звичайних диференціальних рівнянь, диференціальних рівнянь в приватних похідних, стохастичних методів, дискретних алгебраїчних перетворень і т.д.).

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

● дескриптивні (описові) моделі;

● оптимізаційні моделі;

● багатокритеріальні моделі;

● ігрові моделі.

Рис. (1). Блок схема математичного моделювання.

2.1 Елементи теорії матричних ігор

ЗВЕДЕННЯ матричної гри до задачі лінійного програмування

Припустимо, що ціна гри позитивна (u > 0). Якщо це не так, то відповідно до властивості 6 завжди можна підібрати таке число с, додаток якого до всіх елементів матриці виграшів дає матрицю з позитивними елементами, і отже, з позитивним значенням ціни гри. При цьому оптимальні змішані стратегії обох гравців не змінюються.

Отже, нехай дана матрична гра з матрицею А порядку m х n. Відповідно до властивості 7 оптимальні змішані стратегії х = (Х1, ..., хm), y = (Y1, ..., yn) відповідно гравців 1 і 2 та ціна гри u повинні задовольняти співвідношенням.

Розділимо всі рівняння і нерівності в (1) і (2) на u (Це можна зробити, тому що за припущенням u > 0) і введемо позначення:

, ,

Тоді (1) і (2) перепишеться у вигляді:

, , , ,

, , , .

Оскільки перший гравець прагне знайти такі значення хi і, отже, pi , Щоб ціна гри u була максимальною, то рішення першої задачі зводиться до знаходження таких невід'ємних значень pi , При яких

, .

Оскільки другий гравець прагне знайти такі значення yj і, отже, qj, щоб ціна гри u була найменшою, то рішення другого завдання зводиться до знаходження таких невід'ємних значень qj, , При яких

, .

Формули (3) і (4) висловлюють двоїсті одна одній задачі лінійного програмування (ЛП).

Вирішивши ці завдання, отримаємо значення pi , Qj і u. Тоді змішані стратегії, тобто xi і yj виходять за формулами:

Приклад. Знайти рішення гри, яка визначається матрицею.

Рішення. При вирішенні цієї гри до кожного елементу матриці А додамо 1 і отримаємо наступну матрицю

Складемо тепер пару взаємно-двоїстих задач:

Вирішимо другу з них

З оптимальної симплекс-таблиці випливає, що

(Q1, q2, q3) = (0; ; 1),

а з співвідношень подвійності випливає, що

( p1, p2, p3) = ( ; 1; 0).

Отже, ціна гри з платіжною матрицею А1 дорівнює

. ,

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

.

При цьому оптимальні стратегії гравців мають вигляд:

Х = (Х1, х2, х3) = (uр1; uр2; uр3) = =

Y = (Y1, y2, y3) = (uq1; uq2; uq3) = = .

2.2 Рішення матричних ігор у чистих стратегіях

Матрична гра двох гравців з нульовою сумою може розглядатися як наступна абстрактна гра двох гравців.

Перший гравець має m стратегій i = 1,2 ,..., m, другий має n стратегій j = 1,2 ,..., n. Кожній парі стратегій (i, j) поставлено у відповідність число аij, виражає виграш гравця 1 за рахунок гравця 2, якщо перший гравець візьме свою i-ю стратегію, а 2 - свою j-у стратегію.

Кожен з гравців робить один хід: гравець 1 вибирає свою i-ю стратегію (i = ), 2 - свою j-у стратегію (j = ), Після чого гравець 1 отримує виграш аij за рахунок гравця 2 (якщо аij < 0, то це означає, що гравець 1 платить другий суму | аij |). На цьому гра закінчується.

Кожна стратегія гравця i = ; J = часто називається чистою стратегією.

Якщо розглянути матрицю

А =

то проведення кожної партії матричної гри з матрицею А зводиться до вибору гравцем 1 i-го рядка, а гравцем 2 j-го стовпця і одержання гравцем 1 (за рахунок гравця 2) виграшу аij.

Головним у дослідженні ігор є поняття оптимальних стратегій гравців. У це поняття інтуїтивно вкладається такий зміст: стратегія гравця є оптимальною, якщо застосування цієї стратегії забезпечує йому найбільший гарантований виграш при всіляких стратегіях іншого гравця. Виходячи з цих позицій, гравець 1 досліджує матрицю виграшів А наступним чином: для кожного значення i (i = ) Визначається мінімальне значення виграшу в залежності від застосовуваних стратегій гравця 2

аij (i = )

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

аij = = (1).

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

Гравець 2 при оптимальному своїй поведінці повинен прагне по можливості за рахунок своїх стратегій максимально зменшити виграш гравця 1. Тому для гравця 2 відшукується

аij, тобто визначається max виграш гравця 1, за умови, що гравець 2 застосує свою j-у чисту стратегію,

потім гравець 2 відшукує таку свою j = j1 стратегію, при якій гравець 1 отримає min виграш, тобто знаходить

aij = = (2).

Визначення. Число , Що визначається за формулою (2), називається чистої верхній ціною ігри і показує, який максимальний виграш за рахунок своїх стратегій може собі гарантувати гравець 1.

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

Визначення. Якщо в грі з матрицею А = , То говорять, що ця гра має сідловий точку в чистих стратегіях і чисту ціну ігри

u = = .

Сідлова точка - Це пара чистих стратегій (iо, jо) відповідно гравців 1 і 2, при яких досягається рівність = . У це поняття вкладено наступний зміст: якщо один з гравців дотримується стратегії, відповідної сідлової точці, то інший гравець не зможе вступити краще, ніж дотримуватися стратегії, відповідної сідлової точці. Математично це можна записати й інакше:

де i, j - Будь-які чисті стратегії відповідно гравців 1 і 2; (Iо, jо) - Стратегії, що утворюють сідлової крапку.

Таким чином, виходячи з (3), сідловий елемент є мінімальним в iо-му рядку і максимальним в jо-му стовпці у матриці А. Відшукання сідлової точки матриці А відбувається наступним чином: в матриці А послідовно в кожній рядку знаходять мінімальний елемент і перевіряють, чи є цей елемент максимальним у своєму стовпці. Якщо так, то він і є сідлової елемент, а пара стратегій, йому відповідна, утворює сідлової крапку. Пара чистих стратегій (Iо, jо) гравців 1 і 2, утворює сідлові точки і сідлової елемент , Називається рішенням гри. При цьому iо і jо називаються оптимальними чистими стратегіями відповідно гравців 1 і 2.

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

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

Визначення. Змішаною стратегією гравця називається повний набір ймовірностей застосування його чистих стратегій.

Таким чином, якщо гравець 1 має m чистих стратегій 1,2 ,..., m, то його змішана стратегія x - Це набір чисел x = (x1, ..., xm) задовольняють співвідношенням

xi > = 0 (i = 1, m), = 1.

Аналогічно для гравця 2, який має n чистих стратегій, змішана стратегія y - Це набір чисел

y = (y1, ..., yn), yj > = 0, (j = 1, n), = 1.

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

Чистий стратегія є окремий випадок змішаної стратегії. Дійсно, якщо у змішаній стратегії будь-яка i-а чиста стратегія застосовується з вірогідністю 1, то всі інші чисті стратегії не застосовуються. І ця i-я чиста стратегія є окремим випадком змішаної стратегії. Для дотримання секретності кожен гравець застосовує свої стратегії незалежно від вибору іншого гравця.

Визначення. Середній виграш гравця 1 в матричній грі з матрицею А виражається у вигляді математичного очікування його виграшів

E (A, x, y) = = x A yT

Перший гравець має на меті за рахунок зміни своїх змішаних стратегій х максимально збільшити свій середній виграш Е (А, х, y), а другий - за рахунок своїх змішаних стратегій прагне зробити Е (А, х, y) мінімальним, тобто для вирішення гри необхідно знайти такі х і y, при яких досягається верхня ціна гри

Е (А, х, y).

Аналогічної повинна бути ситуація і для гравця 2, тобто нижня ціна гри повинна бути

Е (А, х, y).

Подібно ігор, що мають сідлові точки в чистих стратегіях, вводиться таке визначення: оптимальними змішаними стратегіями гравців 1 і 2 називаються такі набори хо, уо відповідно, які задовольняють рівності

Е (А, х, y) = Е (А, х, y) = Е (А, хо, уо).

Величина Е (А, хо, уо) називається при цьому ціною гри і позначається через u.

Є й інше визначення оптимальних змішаних стратегій: хо, уо називаються оптимальними змішаними стратегіями відповідно гравців 1 і 2, якщо вони утворюють сідлової точку:

Е (А, х, уо) <= Е (А, хо, уо) <= Е (А, хо, у)

Оптимальні змішані стратегії і ціна гри називаються рішенням матричної гри.

Основна теорема матричних ігор має вигляд:

Теорема (Про Мінімакс). Для матричної гри з будь-якою матрицею А величини

Е (А, х, y) і Е (А, х, y) існують і рівні між собою.

Гра m × n у загальному випадку не має наочної геометричної інтерпретації. Її рішення досить трудомістким при великих m і n, однак принципових труднощів не має, оскільки може бути зведене до вирішення завдання лінійного програмування.

Хай гра m × n задана платіжної матрицею p = (a _ij), i = 1, 2, ..., m; j = 1, 2, ..., n. Гравець А має стратегіями A _1, A _2, ..., A _m, гравець В - стратегіями B _1, B _2, ..., B _m. Необхідно визначити оптимальні стратегії S * _A = (p * _1, p * _2, ... , P * _m) та S * _B = (q * _1, q * _2, ... , Q * _n), де p * _i, q * _j - ймовірності застосування відповідних чистих стратегій A _i, B _j, p * ₁ + p * ₂ +...+ p * _m = 1, q * ₁ + q * ₂ +...+ q * _n = 1.

Оптимальна стратегія S * _A задовольняє наступній вимозі. Вона забезпечує гравцю А середній виграш, не менший, ніж ціна гри v, за будь-якої стратегії гравця В і виграш, рівний ціні гри v, при оптимальній стратегії гравця B. Без обмеження спільності вважаємо v> 0: цього можна домогтися, зробивши всі елементи a _ij ≥ 0. Якщо гравець А застосовує змішану стратегію S * _A = (p * _1, p * _2, ... , P * _m) проти будь-якої чистої стратегії B _j гравця В, то він отримує середній виграш, або математичне очікування виграшу a _j = a _1j p ₁ + a _2j p ₂ +...+ a _mj p _m, о = 1, 2, ..., n (тобто елементи j-го стовпця платіжної матриці почленно множаться на відповідні ймовірності стратегій A _1, A _2, ..., A _m і результати складаються).

Для оптимальної стратегії S * _A всі середні виграші не менше ціни гри v, тому отримуємо систему нерівностей:

(2.3.1)

Кожне з нерівностей можна розділити на число v> 0. Введемо нові змінні:

x ₁ = p ₁ / v, x ₂ = p ₂ / v, ..., p _m / v (2.3.2)

Тоді система (2.3.1) набуде вигляду:

(2.3.3)

Мета гравця А - максимізувати свій гарантований виграш, тобто ціну гри v.

Розділивши на v ≠ 0 рівність p ₁ + p ₂ + ... + p _m = 1, отримуємо, що змінні x ₁ (i = 1, 2, ..., m) задовольняють умові: x ₁ + x ₂ +. .. + x _m = 1 / v. Максимізація ціни гри v еквівалентна мінімізації велічіни1 / v, тому завдання може бути сформульована таким чином: визначити значення змінних x _i ≥ 0, i = 1, 2, ..., m, так, щоб вони задовольняли лінійним обмеженням (2.3.3) і при цьому лінійна функція

Z = x ₁ + x ₂ + ... + x _m, (2.3.4)

зверталася до мініму м. Це завдання лінійного програмування. Вирішуючи завдання (2.3.3) - (2.3.4), отримуємо оптимальне рішення p * ₁ + p * ₂ + ... + p * _m і оптимальну стратегію S _A .

Для визначення оптимальної стратегії S * _B = (Q * ₁ + q * ₂ + ... + q * _n) слід врахувати, що гравець В прагне мінімізувати гарантований виграш, тобто знайти . Змінні q _1, q _2, ..., q _n задовольняють нерівності:

(2.3.5)

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

y _j = q _j / v, j = 1, 2, ..., n, (2.3.6)

отримуємо систему нерівностей:

(2.3.7)

Змінні y _j (1, 2, ..., n) задовольняють умові .

Гра звелася до наступної задачі

Визначити значення змінних y _j ≥ 0, j = 1, 2, ..., n, які задовольняють системі нерівностей (2.3.7) і максимізують лінійну функцію

Z '= y ₁ + y ₂ + ... + y _n, (2.3.8)

Рішення задачі лінійного програмування (2.3.6), (2.3.7) визначає оптимальну стратегію S * _B = (q * ₁ + q * ₂ + ... + q * _n). При цьому ціна гри

v = 1 / max, Z '= 1 / min Z (2.3.9)

Склавши розширені матриці для задач (2.3.3), (2.3.4) і (2.3.7), (2.3.8), переконуємося, що одна матриця вийшла з іншої транспонування:

Таким чином, завдання лінійного програмування (2.3.3), (2.3.4) і (2.3.7), (2.3.8) є взаємно-подвійними. Очевидно, при визначенні оптимальних стратегій в конкретних завданнях слід вибрати ту з взаємно-двоїстих задач, рішення якої менш трудомістким, а рішення іншої задачі знайти за допомогою теорем подвійності.

3. Практична частина

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

Продукція / сировина	А	У	З	Запаси сировини, од.
I	4	2	0	≤ 19
II	0	1	1	= 8
III	1	2	0	≤ 24
Прибуток, ден. од.	3	7	2	≥ max

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

Вид таблиці за завданням поставленого завдання:

Рішення поставленого завдання:

Припустимо, що виробляється x ₁ виробів А, виробів У і виробів С. Для визначення оптимального плану виробництва потрібно вирішити завдання, що складається в максимізації цільової функції

3.1.Построім математичну модель задачі:

тоді функція мети:

Z -0 = 3 X ₁ + 7 X ₂ + ₂ X ₃ - сукупний прибуток від продажу виробленої продукції, яку потрібно максимізувати.

Підрахуємо витрати сировини:

Сировина 1-го типу: 4 х1 + 2 х2 + 0 х3, за умовою витрати не перевершують 19,

Сировина 2-го типу: 0 х1 + 1 х2 + 1 х3, за умовою витрати не перевершують 8,

Сировина 3-го типу: 1 x 1 + 2 x 2 + 0 x 3, за умовою витрати не перевершують 24.

при наступних умовах:

4	X 1	+	2	X 2	+	0	X 3	+	X 4	≤	19
0	X 1	+	1	X 2	+	1	X 3	+	X 5	=	8
1	X 1	+	2	X 2	+	0	X 3	+	X 6