[ Лінійне програмування 2 лютого ]! | ≤ | 24 |
X 1, X 2, X 3 ≥ 0.
4X 1 +2 X 2 + X 4 ≤ 19
X 2 + X 3 + X 5 = 8
X 1 + 2 X 2 + X 6 ≤ 24
3.2 Вибираємо метод рішення і наводимо завдання до канонічного вигляду:
Прийшли до задачі лінійного програмування:
припишемо кожному з видів сировини, використовуваних для виробництва продукції. Тоді загальна оцінка сировини, використовуваного на виробництво продукції, складе:
Отримали математичну модель. Необхідно максимізувати функцію мети ↓
Z-0 (x1, x2, x3) = 3X 1 + 7X 2 + 2X 3 → max
Введемо додаткові змінні X 4, X 5, X 6.
Z-0 = | 3 | X 1 | + | 7 | X 2 | + | 2 | X 3 | à (max) |
при системі обмежень: |
Перетворимо перше обмеження:
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 | = | 24 |
Отримали завдання:
4X 1 +2 X 2 + X 4 = 19
X 2 + X 3 + X 5 = 8
X 1 +2 X 2 + X 6 = 24
3.3 Вирішуємо задачу шляхом зведення до задачі лінійного програмування:
X i ≥ 0; 0 - Z =-3X 1 --7X 2 --2X 3
Наведемо завдання до канонічної форми.
Завдання лінійного програмування записана в канонічній формі, якщо вона формулюється наступним чином.
Потрібно знайти вектор , Який доставляє максимум лінійної формі
за умов
де
Вирішимо задачу симплекс-методом
Будуємо початкову симплекс-таблицю:
Базисні перемінні | X 1 | X 2 | X 3 | X 4 | X 5 | X 6 | Вільні члени | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
X 4 | 4 | 2 | 0 | 1 | 0 | 0 | 19
Так як у стовпці вільних членів немає негативних елементів, то знайдено допустиме рішення. Так як у рядку 0 - Z є негативні елементи, то отримане рішення не оптимально. Для визначення ведучого шпальти знайдемо максимальний по модулю негативний елемент у рядку 0 - Z (-7). А ведуча рядок та, у якої найменше позитивне відношення вільного члена до відповідного елементу ведучого шпальти. Перерахуємо таблицю:
Так як у стовпці вільних членів немає негативних елементів, то знайдено допустиме рішення. Так як у рядку 0 - Z є негативні елементи, то отримане рішення не оптимально. Для визначення ведучого шпальти знайдемо максимальний по модулю негативний елемент у рядку 0 - Z (-3). А ведуча рядок та, у якої найменше позитивне відношення вільного члена до відповідного елементу ведучого шпальти. Тоді канонічну форму завдання ЛП можна представити в наступному матричному вигляді еквівалентному початкового: Z = CX → max, AX = B, X ≥ 0. де 0 - нульова матриця-стовпець тієї ж розмірності, що й матриця X. зауваження. Не обмежуючи спільності, можна вважати, що вільні члени ненегативні, тобто bi ≥ 0, де i = ¯ 1, m (інакше обмежувальні рівняння можна помножити на (-1)). Перерахуємо таблицю:
Ця таблиця є останньою, по ній читаємо відповідь завдання. Знайдено оптимальне базисне рішення: При якому Z max = 233 / 4 = 58,25 ден. од. План виробництва: X 1 = 3 / 4 = 0,75; X 2 = 0; X 3 = 0; X 4 = 3; X 5 = 0; X 6 = 29 / 4 = 7,25 Відповідно за рішенням, обчислюємо: Z = 3 * 0,75 +7 * 0 +2 * 0 +3 +7,25 = 24 Z = 24 Відповідь поставленого завдання: План випуску продукції (Z) для отримання максимального прибутку, при тому, що сировина IIвіда було витрачено повністю дорівнює 24 (Z = 24). З ходу рішення задачі за умовою ми бачимо, що оцінений кожен з видів сировини, використовуваних для виробництва продукції. Блок-схеми основних процедур при вирішенні і програмуючи Алгоритм програми → Рис. 1. ↓ Малюнок 1-Алгоритм програми для вирішення ЗЛП (окремий випадок) Програма до поставленого завдання (код програми) Програма - реалізує рішення задачі для виробництва всіх видів продукції з використанням всіх видів сировини. Норми витрат кожного з видів сировини на одиницю продукції даного виду, запаси сировини, а також прибуток з одиниці продукції. Програма визначає: План випуску продукції для отримання максимального прибутку. 1. Опис роботи програми, лістинг програми 1.1 Обгрунтування вибору мови Програма для вирішення даного завдання складена на мові C + +. C + + являє собою систему програмування. Як будь-яка подібна система, C + + призначена для розробки програм і має дві характерні особливості: що створюються з її допомогою програми можуть працювати не тільки під управлінням Windows, але і в системі MS - DOS. C + + являє собою найбільш повний пакет об'єктно-орієнтованого програмування. Мова простий у застосуванні і базується на C #, що спрощує створення програм, людям, знайомим з цією мовою. 1.2 Опис роботи програми Програма складена для загального випадку. У першу матрицю вводяться її члени в звичайних дробах. Програма переводить ці дробу в десяткові і становить канонічну форму. Потім відбувається процес формування першої симплекс таблиці. Наступним етапом програма починає складати ітерації, до тих пір поки не буде знайдено оптимальне рішення (у даному випадку складено 2 ітерації). Програма виводить дані в рядок F /
//------------------------------------------------ ------------------------------------------- # Include <stdio. H> # Include <string.h> # Include <math.h> # Define PRECISION "% 6.2 f" / / формат виведення дробових чисел # Define PRECISION 2 "% .2 f" / / він же тільки ціла частина будь-якої довжини # Define MAXDIGIT 1000000 / / повинен бути дуже велике число (більше за всіх) typedef enum { NEXT _ ITERATION, / / потрібно продовжувати ітерації PLAN _ OPTIMAL, / / знайдений оптимальний опорний план ODR _ BREAK, / / ОДР розімкнута ODR _ EMPTY, / / ОДР порожня DUAL _ DONE / * перший етап (побудова опорного плану) закінчено, переходимо до пошуку оптім.оп.плана (звичайний Симплекс) * / } Plan _ t; int cn = 0; / / довжина вектора вихідного ур-я int cnr = 0; / * cn, тільки без членів == 0 (cnr == cn _ real) потрібно тільки для виводу скороченою таблиці * / float * c = NULL; / / вихідне ур-е int m = 0, n = 0; / / розміри матриці умов float ** a = NULL; / / матриця умов float * b = NULL; / / стовпчик вільних членів матриці умов int * base = NULL; / / базові змінні float zb = 0; / / оцінки оптимальності b float * za = NULL; / / оцінки оптимальності a int base _ column = -1; / / дозволяє стовпець int base _ row = -1; / / роздільна рядок bool full _ table = true; / / вид виведеної таблиці: true == повна, false == стисла void FreeMem () { delete [] za; delete [] base; delete [] b; for (int i = 0; i <m; i + +) delete [] a [i]; delete [] a; delete [] c; } bool ReadInput (char * filename) { int i, j; FILE * f = fopen (filename, "r"); if (NULL == f) return false; / / Вихідне ур-е fscanf (f, "% i", & cn); c = new float [cn]; cnr = cn; for (i = 0; i <cn; i + +) { fscanf (f, "% f", & c [i]); if (0 == c [i]) cnr -; } / / Матриця умов fscanf (f, "% i% i", & n, & m); a = new float * [m]; for (i = 0; i <m; i + +) a [i] = new float [n]; b = new float [m]; for (j = 0; j <m; j + +) { for (i = 0; i <n; i + +) fscanf (f, "% f", & a [j] [i]); fscanf (f, "% f", & b [j]); } / / Базові змінні base = new int [m]; for (j = 0; j <m; j + +) { fscanf (f, "% i", & base [j]); - Base [j]; } / / Прапор - повну або стислу таблицю виводити? int flag = 1; fscanf (f, "% i", & flag); full_table = flag? true: false; fclose (f); za = new float [n]; / / For (i = 0; i <n; i + +) za [i] = 0; / /! лише для налагодження! return true; } / / Обчислення оцінок оптимальності {za == delta _ j [] and zb == Z} void EvaluationOptimal () { int i, j; zb = 0; for (i = 0; i <n; i + +) za [i] = 0; for (j = 0; j <m; j + +) { for (i = 0; i <n; i + +) za [i] + = c [base [j]] * a [j] [i]; zb + = c [base [j]] * b [j]; } for (i = 0; i <n; i + +) za [i] -= c [i]; } / / Побудова опорного плану (цей етап тільки в двоїстому симплекс-методі) plan_t BuildPsevdoPlan () { int i, j; base _ column = -1; / / дозволяє стовпець base _ row = -1; / / роздільна рядок float acc; / / тимчасово: акумулятор - буде зберігати min, max, etc. acc = 0; / / min від'ємне значення b for (j = 0; j <m; j + +) if (b [j] <acc) { acc = b [j]; base_row = j; } if (-1 == base_row) return DUAL_DONE; acc =-MAXDIGIT; / / max ставлення za до отріцат. ел - там в рядку base_row for (i = 0; i <n; i + +) { float temp; if (a [base_row] [i] <0 & & (temp = za [i] / a [base_row] [i])> acc) { acc = temp; base_column = i; } } if (-1 == base_column) return ODR_EMPTY; return NEXT _ ITERATION; } / / Перевірка опорного плану на оптимальність plan_t CheckStrongPlan () { int i, j; float za_min = 0; base_column = -1; / / дозволяє стовпець base _ row = -1; / / роздільна рядок / / Вибір дозволяє стовпця for (i = 0; i <n; i + +) { if (za [i]> = 0) continue; else if (za [i] <za_min) { za_min = za [i]; base_column = i; } } if (-1 == base_column) return PLAN_OPTIMAL; za _ min = MAXDIGIT; / / Вибір роздільної рядки for (j = 0; j <m; j + +) { if (a [j] [base_column]> 0) { float t = b [j] / a [j] [base_column]; if (t <za_min) { za_min = t; base_row = j; } } } if (-1 == base_row) return ODR_BREAK; return NEXT_ITERATION; } / / Перетворення таблиці за ф-лам Жордана-Гаусса void JGTransformation (int base_row, int base_column) { / / Перевірка на всяк випадок: щоб не було поділу на нуль if (0 == a [base_row] [base_column]) return; base [base_row] = base_column; int i, j; float ** a2 = new float * [m]; / / матриця умов float * b 2 = new float [m]; / / стовпчик вільних членів матриці умов memcpy (b2, b, m * sizeof (float)); for (j = 0; j <m; j + +) { a2 [j] = new float [n]; memcpy (a2 [j], a [j], n * sizeof (float)); } for (j = 0; j <m; j + +) { for (i = 0; i <n; i + +) { if (i == base_column) { a2 [j] [i] = (float) (j == base_row? 1: 0); } else { if (j == base_row) a2 [j] [i] = a [j] [i] / a [base_row] [base_column]; else a2 [j] [i] = a [j] [i] - a [base_row] [i] * a [j] [base_column] / a [base_row] [base_column]; } } if (j == base_row) b2 [j] = b [j] / a [base_row] [base_column]; else b2 [j] = b [j] - b [base_row] * a [j] [base_column] / a [base_row] [base_column]; } memcpy (b, b2, m * sizeof (float)); delete [] b2; for (j = 0; j <m; j + +) { memcpy (a [j], a2 [j], n * sizeof (float)); delete [] a2 [j]; } delete [] a2; } / / Перевірка: чи входить номер стовпця в число базисних змінних bool InBase (int num) { for (int j = 0; j <m; j + +) if (num == base [j]) return true; return false; } / / Вивід лінії символів void Rule (char c, int amount = full_table? 5 + (n +2) * 8: 5 + (cnr +1) * 8) { for (int i = 0; i <amount; i + +) printf ("% c", c); printf ("\ n"); } / / Вивід Симплекс - таблиці void ShowTable () { int i, j; static int iteration = 0; printf ("[% i] \ n", iteration + +); if (full_table) / / Повна таблиця { Rule ('='); printf ("Баз. | | |"); for (i = 0; i <cn; i + +) printf (PRECISION "|", c [i]); printf ("\ nпер. | Ci | Bi |"); Rule ('-', n * 8); printf ("| | |"); for (i = 0; i <cn; i + +) printf ("x% i |", i +1); printf ("\ n"); Rule ('='); for (j = 0; j <m; j + +) { printf ("x% i |" PRECISION "|" PRECISION "|", base [j] +1, c [base [j]], b [j]); for (i = 0; i <n; i + +) printf (PRECISION "% c |", a [j] [i], base_column == i & & base_row == j ?'*':' '); printf ("\ n"); } Rule ('='); printf ("Z | --- |" PRECISION "|", zb); for (i = 0; i <n; i + +) printf (PRECISION "|", za [i]); printf ("\ n"); Rule ('-'); } else / / Стисла таблиця { Rule ('='); printf ("БvС >|"); for (i = 0; i <cn; i + +) { if (! InBase (i)) printf ("x% i |", i +1); } printf ("Bi | \ n"); Rule ('='); for (j = 0; j <m; j + +) { printf ("x% i |", base [j] +1); for (i = 0; i <n; i + +) { if (! InBase (i)) printf (PRECISION "% c |", a [j] [i], base_column == i & & base_row == j ?'*':' '); } printf (PRECISION "| \ n", b [j]); } Rule ('='); printf ("Z |"); for (i = 0; i <n; i + +) { if (! InBase (i)) printf (PRECISION "|", za [i]); } printf (PRECISION "| \ n", zb); Rule ('-'); } if (base_column> -1 & & base_row> -1) printf ("Дозволяючий стовпець:% 2 i \ n Роздільна рядок:% 2 i \ n \ nX = (", base_column +1, base_row +1); else printf ("\ nX =("); for (i = 0; i <n; i + +) { int basen = -1; for (j = 0; j <m; j + +) if (base [j] == i) {basen = j; break;} printf (PRECISION2 "% c", -1 == basen? 0: b [basen], i! = n-1 ?',':')'); } printf ("\ nZ =" PRECISION2 "\ n \ n \ n", zb); } int main (int argc, char * argv []) { if (argc <2) { printf ("Missing argument \ n"); return -1; } if (! ReadInput (argv [1])) { printf ("Error open file% s. \ n", argv [1]); return -1; } printf ("*** Двоїстий симплекс-метод *** \ n \ n "); plan_t plan; bool dual_done = false; for (int k = 0; k <2 * m +1; k + +) { if (k) JGTransformation (base_row, base_column); EvaluationOptimal (); if (dual_done) { plan = CheckStrongPlan (); } else { plan = BuildPsevdoPlan (); / / only in dual-simplex if (DUAL_DONE == plan) { dual_done = true; plan = CheckStrongPlan (); } } ShowTable (); if (NEXT_ITERATION! = plan) { char * s; switch (plan) { case PLAN_OPTIMAL: s = "Опорний план оптимальний"; break; case ODR _ BREAK: s = "Область допустимих рішень розімкнена"; break; case ODR _ EMPTY: s = "Область допустимих рішень порожня"; break; } printf ("\ n% s. \ n", s); break; } } FreeMem (); return 0; } //------------------------------------------------ ----------------------------------------- Результат роботи програми Роботу програми ми можемо проаналізувати по результату. Тут ми бачимо первісну матрицю, яка представлена у вигляді симплекс таблиці і результат перетворення таблиці. Результат перетворення таблиці представлений у вигляді симплекс таблиці, подібної початкової. Проаналізувавши дані отримані за допомогою програми і порівнявши їх з результатами обчислень можна зробити висновок, що отримані результати рівні між собою, а це означає що програма працює правильно. 3.4. Аналіз результату вирішення поставленого завдання 1. Завдання аналізу, джерела інформації Необхідною умовою виконання планів по виробництву продукції, зниження її собівартості, зростанню прибутку, рентабельності є повне і своєчасне забезпечення підприємства сировиною і матеріалами необхідного асортименту і якості. Зростання потреби підприємства в матеріальних ресурсах може бути задоволений екстенсивним шляхом (придбанням або виготовленням більшої кількості матеріалів і енергії) або інтенсивним (більш економним використанням наявних запасів в процесі виробництва продукції). Перший шлях веде до зростання питомих матеріальних витрат на одиницю продукції, хоча собівартість її може при цьому і знизитися за рахунок збільшення обсягу виробництва та зменшення частки постійних витрат. Другий шлях забезпечує скорочення питомих матеріальних витрат і зниження собівартості одиниці продукції. Економне використання сировини, матеріалів та енергії рівнозначно збільшенню їх виробництва. Завдання аналізу забезпеченості та використання матеріальних ресурсів: а) оцінка реальності планів матеріально-технічного постачання, ступеня їх виконання та впливу на обсяг виробництва продукції, її собівартість і інші показники; б) оцінка рівня ефективності використання матеріальних ресурсів; в) виявлення внутрішньовиробничих резервів економії матеріальних ресурсів та розробка конкретних заходів щодо їх використання. Джерелами інформації для аналізу матеріальних ресурсів є план матеріально-технічного постачання, заявки, договори на постачання сировини і матеріалів, форми статистичної звітності про наявність і використання матеріальних ресурсів і про витрати на виробництво, оперативні дані відділу матеріально-технічного постачання, відомості аналітичного бухгалтерського - обліку про надходження, витрату та залишках матеріальних ресурсів та ін 2. Аналіз забезпеченості підприємства матеріальними ресурсами При аналізі забезпеченості підприємства матеріальними ресурсами в першу чергу перевіряють якість плану матеріально-технічного постачання. Перевірку реальності плану починають з вивчення норм і нормативів, які покладені в основу розрахунку потреби підприємства в матеріальних ресурсах. Потім перевіряється відповідність плану постачання потребам виробництва продукції і утворення необхідних запасів виходячи з прогресивних норм витрати матеріалів. Важливою умовою безперебійної роботи підприємства є повна забезпеченість потреби в матеріальних ресурсах джерелами покриття. Очі можуть бути зовнішніми і внутрішніми. До зовнішніх джерел відносяться матеріальні ресурси, що надходять від постачальників відповідно до укладених договорів. Внутрішні джерела - це скорочення відходів сировини, використання вторинної сировини, власне виготовлення матеріалів і напівфабрикатів, економія матеріалів внаслідок впровадження досягнень науково-технічного прогресу. Реальна потреба в завезенні матеріальних ресурсів з боку - це різниця між загальною потребою у певному виді матеріалу і сумою власних внутрішніх джерел її покриття. За заданою завдання ми бачимо, що: Для виробництва трьох видів продукції використовується три види сировини. Норми витрат кожного з видів сировини на одиницю продукції даного виду, запаси сировини, а також прибуток з одиниці продукції.
1. Перше, що я зробив, це визначив план випуску продукції для отримання максимального прибутку, з урахуванням того що б сировину IIвіда було витрачено повністю. Z -0 = 3 X 1 + 7 X 2 + 2 X 3
| 8 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
1 | X 1 | + | 2 | X 2 | + | 0 | X 3 | + | X 6 | ≤ | 24 |
X 1, X 2, X 3 ≥ 0.
4X 1 +2 X 2 + X 4 ≤ 19
X 2 + X 3 + X 5 = 8
X 1 + 2 X 2 + X 6 ≤ 24
Друге, оцінив кожен з видів сировини, використовуваних для виробництва продукції.
Z -0 = 3 X 1 + 7 X 2 + 2 X 3 → max
Ввів додаткові змінні X 4, X 5, X 6.
Z-0 = | 3 | X 1 | + | 7 | X 2 | + | 2 | X 3 | à (max) |
Обмеження:
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 | = | 24 |
3. Побудував математичну модель задачі;
4X 1 +2 X 2 + X 4 = 19
X 2 + X 3 + X 5 = 8
X 1 +2 X 2 + X 6 = 24
4. Вибрав метод рішення задачі і привів завдання до канонічного вигляду;
X i ≥ 0; 0 - Z =-3X 1 --7X 2 --2X 3
5. Вирішив завдання шляхом зведення до задачі лінійного програмування;
Базісниепеременние | X 1 | X 2 | X 3 | X 4 | X 5 | X 6 | Свободниечлени | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
X 4 | 4 | 2 | 0 | 1 | 0 | 0 | 19 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
X 5 | 0 | 1 | 1 | 0 | 1 | 0 | 8 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
X 6 | 1 | 2 | 0 | 0 | 0 | 1 | 24 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
0-Z | -3
Перерахував таблицю:
Перерахував таблицю:
Знайшов оптимальне базисне рішення
Порядок роботи з симплекс таблицею Перша симплекс-таблиця піддається перетворенню, суть якого полягає в переході до нового опорного рішення. Алгоритм переходу до наступної таблиці такий: Проглядається останній рядок (індексна) таблиці і серед коефіцієнтів цього рядка (виключаючи стовпець вільних членів) вибирається найменший негативний число при знаходженні max, або найбільший позитивний при завдання на min. Якщо такого немає, то початковий базисне рішення є оптимальним і дана таблиця є останньою; проглядається стовпець таблиці, що відповідає обраному негативному (позитивному) коефіцієнта в останньому рядку - ключовий стовпець, і в цьому стовпці вибираються позитивні коефіцієнти. Якщо таких немає, то цільова функція необмежена на області допустимих значень змінних і завдання рішень не має, серед вибраних коефіцієнтів стовпця вибирається той, для якого абсолютна величина відносини відповідного вільного члена (що знаходиться у стовпці вільних членів) до цього елемента мінімальна. Цей коефіцієнт називається що дозволяє, а рядок у якій він знаходиться ключовою; надалі базисна змінна, що відповідає рядку дозволяє елемента, повинна бути переведена в розряд вільних, а вільна змінна, що відповідає стовпцю дозволяє елемента, вводиться до числа базисних. Будується нова таблиця, яка містить нові назви базисних змінних: поділяємо кожен елемент ключовий рядка (виключаючи стовпець вільних членів) на дозволяючий елемент і отримані значення записуємо в рядок зі зміненою базисної змінної нової симплекс таблиці .. Рядок дозволяє елемента ділиться на цей елемент і отриманий рядок записується в нову таблицю на те ж місце в новій таблиці всі елементи ключового стовпця = 0, крім розрізає, він завжди дорівнює 1. Стовпець, у якого в ключовий рядку є 0, в новій таблиці буде таким же рядок, у якої в ключовому стовпці є 0, в новій таблиці буде такий же в інші клітини нової таблиці записується результат перетворення елементів старої таблиці: В результаті отримуємо нову симплекс- таблицю, що відповідає новому базисному рішенням. Тепер слід переглянути рядок цільової функції (індексний), якщо в ній немає негативних значень (в завдання на знаходження максимального значення), яких позитивних (в завдання на знаходження мінімального значення) крім стоїть на місці (вільного стовпця), то значить, що оптимальне рішення отримано. В іншому випадку, переходимо до нової симплекс таблиці по вище описаним алгоритмом. 4. ВИСНОВКИ ТА РЕКОМЕНДАЦІЇ ЩОДО ПРАКТИЧНОГО ВИКОРИСТАННЯ Метою курсового проекту було рішення задач лінійного програмування симплекс-методом, складання алгоритму, складання програми за алгоритмом і вивід результату на екран. Для знаходження оптимального рішення можна піти найпростішим способом з точки зору особи, яка безпосередньо проводить вирішення завдання. Для більш швидкого вирішення завдання можна скористатися мовами програмування, що призведе до більш швидкого вирішення завдання. Він заснований на перерахунку коефіцієнтів у системі рівнянь і цільової функції при зміні місць вільної та базисної змінних можна формалізувати і звести до перетворення симплекс-таблиці. Симплекс-метод є обчислювальної процедурою представленої в алгебраїчній формі. Він безпосередньо застосовується до загальної задачі лінійного програмування в стандартній формі. У даному проекті був складений оптимальний план випуску продукції кожного виду, що забезпечує максимальний прибуток. У висновку свого проектування хочу підвести підсумок в цілому "Рішенню матричних ігор у змішаних стратегіях". Класифікацію ігор можна проводити: за кількістю гравців, кількістю стратегій, характером взаємодії гравців, характером виграшу, кількості ходів, станом інформації і т.д. Залежно від кількості гравців розрізняють гри двох і n гравців. Перші з них найбільш вивчені. Ігри трьох і більше гравців менш досліджені через що виникають принципових труднощів і технічних можливостей одержання рішення. Чим більше гравців - тим більше проблем. За кількістю стратегій гри діляться на кінцеві і нескінченні. Якщо в грі всі гравці мають кінцеве число можливих стратегій, то вона називається кінцевої. Якщо ж хоча б один з гравців має нескінченну кількість можливих стратегій гра називається нескінченною. За характером взаємодії ігри поділяються на: 1) безкоаліційний: гравці не мають права брати участь в угодах, утворювати коаліції; 2) коаліційні (Кооперативні) - можуть вступати в коаліції. У кооперативних іграх коаліції наперед визначені. За характером виграшів ігри поділяються на: ігри з нульовою сумою (Загальний капітал усіх гравців не змінюється, а перерозподіляється між гравцями; сума виграшів всіх гравців дорівнює нулю) та ігри з ненульовий сумою. По виду функцій виграшу ігри поділяються на: матричні, біматрічние, безперервні, опуклі, сепарабельним, типу дуелей і ін Матрична гра - це кінцева гра двох гравців з нульовою сумою, в якій задається виграш гравця 1 у вигляді матриці (рядок матриці відповідає номеру застосовуваної стратегії гравця 2, стовпець - номеру застосовуваної стратегії гравця 2; на перетині рядка і стовпця матриці знаходиться виграш гравця 1, відповідний застосовуваним стратегіям). Для матричних ігор доведено, що будь-яка з них має рішення і воно може бути легко знайдено шляхом зведення гри до задачі лінійного програмування. Біматрічная гра - це кінцева гра двох гравців з ненульовою сумою, в якій виграші кожного гравця задаються матрицями окремо для відповідного гравця (у кожній матриці рядок відповідає стратегії гравця 1, стовпець - стратегії гравця 2, на перетині рядка і стовпця в першій матриці знаходиться виграш гравця 1 , у другій матриці - виграш гравця 2.) Для біматрічних ігор також розроблена теорія оптимальної поведінки гравців, однак вирішувати такі ігри складніше, ніж звичайні матричні. Безперервної вважається гра, в якій функція виграшів кожного гравця є безперервною в залежності від стратегій. Доведено, що ігри цього класу мають рішення, однак не розроблено практично прийнятних методів їх знаходження. Якщо функція виграшів є опуклою, то така гра називається опуклою. Для них розроблено прийнятні методи рішення, що складаються в знаходженні чистої оптимальної стратегії (певного числа) для одного гравця і ймовірностей застосування чистих оптимальних стратегій іншого гравця. Таке завдання вирішується порівняно легко. Висновок курсового проектування по темі завдання "Рішення матричної гри в змішаних стратегіях" Щоб описати гру, необхідно спочатку виявити її учасників. Ця умова легко здійсненно, коли мова йде про звичайні іграх типу шахів, канасти і т.п. Інакше йде справа з "ринковими іграми". Тут не завжди просто розпізнати всіх гравців, тобто діючих або потенційних конкурентів. Практика показує, що не обов'язково ідентифікувати всіх гравців, треба виявити найбільш важливих. Ігри охоплюють, як правило, кілька періодів, протягом яких гравці роблять послідовні чи одночасні дії. Ці дії позначаються терміном "хід". Дії можуть бути пов'язані з цінами, обсягами продажів, витратами на наукові дослідження та розробки і т.д. Періоди, протягом яких гравці роблять свої ходи, називаються етапами гри. Вибрані на кожному етапі ходи в кінцевому рахунку визначають "платежі" (виграш або збиток) кожного гравця, які можуть виражатися в матеріальних цінностях або грошах (переважно дисконтована прибуток). Ще одним основним поняттям даної теорії є стратегія гравця. Під нею розуміються можливі дії, що дозволяють гравцеві на кожному етапі гри вибирати з певної кількості альтернативних варіантів такий хід, який представляється йому "найкращою відповіддю" на дії інших гравців. Щодо концепції стратегії слід зауважити, що гравець визначає свої дії не тільки для етапів, яких фактично досягла конкретна гра, але і для всіх ситуацій, включаючи і ті, які можуть і не виникнути в ході даної гри. Важлива і форма надання гри. Зазвичай виділяють нормальну, або матричну, форму і розгорнуту, задану у вигляді дерева. Щоб встановити першу зв'язок зі сферою управління, гру можна описати таким чином. Два підприємства, що виробляють однорідну продукцію, стоять перед вибором. В одному випадку вони можуть закріпитися на ринку завдяки встановленню високої ціни, яка забезпечить їм середню картельну прибуток ПK. При вступі в жорстку конкурентну боротьбу обидва отримують прибуток ПW. Якщо один з конкурентів встановлює високу ціну, а другий - низьку, то останній реалізує монопольний прибуток ПM, іншого ж зазнає збитків ПG. Подібна ситуація може, наприклад, виникнути коли обидві фірми повинні оголосити свою ціну, яка згодом не може бути переглянута. При відсутності жорстких умов обом підприємствам вигідно призначити низьку ціну. Стратегія "низької ціни" є домінуючою для будь-якої фірми: незалежно від того, яку ціну вибирає конкуруюча фірма, самої завжди краще встановлювати низьку ціну. Але в такому випадку перед фірмами виникає дилема, оскільки прибуток ПK (яка для обох гравців вище, ніж прибуток ПW) не досягається. Стратегічна комбінація "низькі ціни / низькі ціни" з відповідними платежами представляє собою рівновагу Неша, при якому жодному з гравців невигідно сепаратно відходити від обраної стратегії. Подібна концепція рівноваги є принциповою при вирішенні стратегічних ситуацій, але за певних обставин вона все ж таки потребує вдосконалення. Що стосується зазначеної вище дилеми, то її дозвіл залежить, зокрема, від оригінальності ходів гравців. Список основних джерел опорної літератури 1. Б. Банді, Основи лінійного програмування. М: Вища мат., 1989р. 2. Б.Т Кузнєцов Математичні методи та моделі дослідження операцій. М: Юніті, 2005р. 3. В.Н. Ашихміна та ін Введення в математичне моделювання, М: Логос, 2005р. 4. Т.Л. Партико, І.І. Попов. Математичні методи, М: Форум, 2003. 5. В.В. Фаронов. Програмування на мові С + +, СПб.: Пітер, 2006р. |