Пряма задача

, x_j ≥ 0 (j=1, 2…..n)

де А – матриця системи обмежень задачі розміром m x n;

В – вектор стовпець;

С – вектор строка;

АХ≤ В;

Z → max.

Двоїста задача

tr = , y_i ≥ 0 (i=1, 2…..m)

де trA – транспонована матриця А;

trС – транспонований вектор С;

trB - транспонований вектор В;

AY ≥ trC;

F → min.

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

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

Математична модель прямої задачі мішаної пари двоїстих задач містить обмеження, записані як рівняння, так і нерівності, причому знаків різних, за виглядом. Для складання двоїстої задачі необхідно привести всі нерівності системи обмежень прямої задачі до одного вигляду: якщо пряма задача на максимум, то всі нерівності обмежень приводимо до вигляду «≤», якщо на мінімум до вигляду «≥». Нерівності, для яких дані вимоги не виконуються, домножимо на (-1).

2. Основні теореми двоїстості.

Розглянемо пару даоїстих задач, утворену канонічною задачею ЛП і двоїстої до неї:

Пряма:

Z=∑ c_ix_i → max/min

за умов

∑ a_ijx_j =b_i, (i=1, 2…..m)

x_j ≥ 0 (j=1, 2…..n)

Двоїста:

F=∑ b_iy_i → min/max

за умов

∑ a_ijy_i≥ /≤ c_j, (j=1, 2…..n)

y_i є(-∞, ∞) (i=1, 2…..m)

Між прямою і двоїстою задачами ЛП існує тісний взаємозв’язок, який видно з наведених далі лем та теорем.

Лема 1. Якщо Х – деякий план прямої задачі, Y – довільний план двоїстої задачі, то значення цільової функції прямої задачі при плані Х не перевищує значення цільової функції двоїстої задачі при плані Y, тобто

Z(X)≤ F(Y)

Лема 2. Якщо Z(X*)=F(Y*), та X* - оптимальний план прямої задачі, то Y* - оптимальний план двоїстої задачі.

Теорема 1. (перша теорема двоїстості). Якщо одна із пар двоїстих задач має оптимальний план, то і друга задача має оптимальний план і значення цільової функції при їх оптимальних планах рівні між собою, тобто Z(X*)=F(Y*).

Якщо ж цільова функція однієї із двоїстих задач необмежена (для прямої задачі - зверху, а для двоїстої з низу), то множина планів двоїстої задачі є порожньою.

Теорема 2. (друга теорема двоїстості). Для того щоб плани Х* і Y* відповідно до задач (1) – (3) і (1*) – (3*) були оптимальними планами цих задач, необхідно і достатньо, щоб для кожного j (j=1, 2…..n) виконувалась рівність:

(a_1j(y₁)* + a_2j(y₂)* + ……. + a_mj(y_m)* - c_j)(x_j)* = 0

Економічну інтерпретацію двоїстої задачі розглянемо на прикладі задачі про оптимальне використання ресурсів, математична модель якої має вигляд:

Z=∑ c_ix_i → max

за умов

∑ a_ijx_j =b_i, (i=1, 2…..m)

x_j ≥ 0 (j=1, 2…..n)

Двоїста задача до неї буде така:

F=∑ b_iy_i → min

за умов

∑ a_ijy_i≥ c_j, (j=1, 2…..n)

y_i ≥ 0 i=1, 2…..m

Приклад. Підприємство виготовляє три види продукції А, В, С.

Дані задачі приведені у таблиці:

Знайти такий план випуску продукції, щоб прибуток від їх реалізації був максимальним.

3 Взаємозв’язок розв’язків прямої та двоїстої задач.

Розглянемо пару двоїстих задач ЛП (1) – (3) і (1)* - (3)*, пряма задача якої записана у канонічному вигляді. Наступна теорема встановлює взаємозв’язок між розв’язками прямої і двоїстої задачами.

Теорема 3. Якщо пряма задача ЛП має оптимальний план Х*, отриманий симплекс методом, то оптимальний план Y* двоїстої задачі визначається за формулою:

Y*=C_базР^-1 (4)

де C_баз – вектор рядок, що складається з коефіцієнтів цільової функції прямої задачі при невідомих, які є базисними в оптимальному плані; Р^-1 – матриця, обернена до матриці Р, складеної з компонент базисних векторів оптимального плану задачі.

Таким чином, якщо знайти симплекс методом оптимальний план задачі (1) –(3), то використовуючи останню симплекс таблицю, можна визначити C_баз і Р^-1 та за допомогою співвідношення (5.4), знайти план двоїстої задачі.

Відмітимо, що існує взаємно-однозначна відповідність між змінними: основним змінним прямої задачі відповідають додаткові змінні двоїстої задачі і навпаки:

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

Двоїстий симплекс метод використовується для знаходження розв’язку задачі ЛП, записаної у канонічному вигляді, для якої серед векторів Р_j, складених з коефіцієнтів при невідомих у системі рівнянь, є рівно m одиничних.

Також цей метод можна використовувати для знаходження розв’язку задач ЛП, коли вільні члени системи рівнянь є довільними числами (для розв’язування задач симплекс методом числа b_i припускались невід’ємними).

Питання для самоконтролю.

1. Нехай є задача про оптимальне використання ресурсів. Дайте економічну інтерпретацію двоїстої задачі.

2. Сформулюйте першу теорему двоїстості.

3. Сформулюйте другу теорему двоїстості.

4. Перечисліть ознаки взаємно двоїстих задач.

5. Як по рішенню прямої задачі знайти рішення двоїстої задачі.

6. В чому полягає ідея двоїстого симплекс методу.

7. Який економічний зміст основних змінних двоїстої задачі?

8. Який економічний зміст додаткових змінних двоїстої задачі?

9. Який економічний зміст перевірки системи обмежень прямої задачі для знайденого оптимального плану?

10. Що дає перевірка обмежень двоїстої задачі?

11. Як проводиться аналіз стовбців останньої симплекс таблиці, для яких Δ _i> 0?

Тема 5. Цілочислові задачі лінійного програмування

Тема 6. Елементи нелінійного програмування

Лекція 6.

Тема лекції: Задачі нелінійного програмування

Мета: ознайомити студентів з методами розв’язання задач цілочислового програмування методом Гоморі та з основними методами розв’язування задач нелінійного програмування.

План лекції

1. Задачі дробово-лінійного програмування.

2. Задачі цілочислового програмування.

3. Класичні методи розв’язування задач нелінійного програмування.

4. Метод множників Лагранжа.

5. Задачі опуклого прогрмування.

Література:

1. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1993. – 336 с.

2. Іванюта І.Д. Практикум з математичного програмування: Навчальний посібник/ І.Д. Іванюта, В.І. Рибалка, І.А. Рудоміра – Дусятська. – К.: «Слово», 2008. – 296 с.

3. Кучма М.І. Математичне програмування: приклади і задачі: Навчальний посібник/ М.І. Кучма. - Львів: «Новий Світ - 2000», 2006. – 344 с.

4. А. Черемис, Р. Юринець, О. Мищишин. Методи оптимізації в економіці. Навчальний посібник. – К.: Центр навчальної літератури, 2006. – 152 с.

1. Задачі дробово-лінійного програмування.

Математична модель задачі дробово-лінійного програмування записується так:

Z= (1)

за умов

(2)

x_ij≥ 0, (j= ), (3)

де c_j, d_j, b_i, a_ij, (j= ), (i= ) – сталі величини, 0.

Умови обмежень (1) – (3) даної задачі є лінійними, тому ОДР є опуклою множиною, і цільова функція (1) досягає екстремального значення в одній з вершин цієї області.

Задачу дробово-лінійного прогамування можна звести до задачі ЛП за попомогою стандартного перетворення до задачі ЛП і розв’язати її симплекс-методом:

y₀=

y_i=y₀x_i, i= .

2. Задачі цілочислового програмування.

Задача цілочислового програмування формулюється так:

Z= (4)

за умов

, = b_i, i= , (5)

x_j≥ 0, (j= ), (6)

x_j - цілі, (j= ), (7)

умова цілочисельності (7), яка додається до звичайної задачі ЛП, суттєво ускладнює її розв’язання.

Метод Гоморі. Сутність методу Гоморі (метод відтинання) полягає у тому, що спочатку розв’язується звичайна задача ЛП без урахування вимог цілочисельності змінних. Якщо отриманий оптимальний план задачі цілочисловий, то задача розв’язана. У протилежному випадку у модель вводиться спеціальне додаткове обмеження, що враховує цілочисельність змінних і володіє такими властивостями;

- вона повинна бути лінійною;

- вона повинна відтинати знайдений оптимальний нецілочисловий план задачі;

- не повинна відтинати ні одного цілочислового плану.

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

Це додаткове обмеження вводиться до оптимального плану якщо серед компонент оптимального розв’язку яка має найбільшу дробову частину. На базі цієї змінної будується додаткове обмеження Р.Гоморі:

де - дробова частина числа,

=а-[a].

3. Класичні методи розв’язання задач нелінійного програмування.

Загальна задача нелінійного програмування полягає у знаходженні максимального(мінімального) значення функції

Z=f(x₁, x₂, ….. x_n) → max/ min (8)

за умов

g_i(x₁, x₂, ….. x_n) { ≤ =≥ }b_i, i=1, 2…..m (9)

де всі функції (або їх частина) нелінійні.

Функція f з (8) – цільова функція, а умови g_i з (9) - умовами обмеження.

Сукупність змінних, що задовольняють обмеженням (9) задачі називається допустимим розв’язком або планом. Кожному допустимому розв ’ язкувідповідає певне значення цільової функції.

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

Лише для небагатьох типів задач НП розроблені обчислювальні методи їх розв’язання.

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

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

- Задачі дробово-лінійного програмування

Z=(∑ c_ix_i)/(∑ d_ix_i) → max/ min

за умов

∑ a_ijx_j =b_i, (i=1, 2…..m)

x_j ≥ 0 (j=1, 2…..n)

- Сеперабельна задача НП

f(x₁, x₂, ….. x_n) =∑ f_i(x_i) → max/ min

за умов

∑ a_ijx_j{ ≤ =≥ }b_i, (i=1, 2…..m)

x_j ≥ 0 (j=1, 2…..n)

- Квадратична задача НП

f(x₁, x₂, ….. x_n) =∑ c_jx_j +∑ ∑ d_jix_ix_j → max/ min

за умов

∑ a_ijx_j{ ≤ =≥ }b_i, (i=1, 2…..m)

x_j ≥ 0 (j=1, 2…..n)

- Задача опуклого програмування

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

Розглянемо задачу (8), якщо на змінні не накладаються умови обмежень.

Така задача вирішується класичними методами дифереціального числення.

Нехай Z=f(x₁, x₂, ….. x_n) неприривно – диференційована функція в своїй області визначення. Необхідною умовою екстремуму в точці Х₀ функції Z=f(x₁, x₂, ….. x_n) є рівність нулю градієнта функції Z(X₀)=0.Для функції Z=f(x₁, x₂, ….. x_n) запишемо матрицю Гессе:

Н=

яка складається з частинних похідних другого порядку.

Головні мінори матриці Гессе позначимо:

M₁= _{‌ ‌} , M₂= , …………., M_n=H,

де f_ij= – значення частинної похідної другого порядку функції Z в точці X₀.

Якщо всі головні мінори M₁, M₂, M₃, …… M_n> 0, то Х₀ – точка локального мінімуму. Якщо головні мінори почергово міняють знак, починаючи з мінуса, то точка Х₀ – точка локального максимуму. Проаналізувавши всю область допустимих розв’язків, можна виділити серед локальних екстремумів найбільший і найменший, які і будуть глобальними.

4. Метод множників Лагранжа.

Розглянемо задачу НП з обмеженнями – рівностями:

Z=f(x₁, x₂, ….. x_n) → max/ min (10)

за умов

g_i(x₁, x₂, ….. x_n)=b_i, i=1, 2…..m (11)

в якій f і g_i двічі неперервно диференційовані функції.

Для визначення оптимальних точок цієї задачі, введемо набір змінних λ _i (i=1, 2, ….m), які називаються множниками Лагранжа, і побудуємо функцію Лагранжа

L(x₁, x₂, ….. x_n, λ ₁,, λ ₂,...., λ _m)= f(x₁, x₂, ….. x_n) + ∑ λ _i(b_i - g_i(x₁, x₂, ….. x_n)) (12)

Відшукання умовного екстремуму задачі зводиться до знаходження безумовного екстремуму функції Лагранжа (12). Характер оптимальності з’ясовується аналогічно, як і у випадку безумовного екстремуму.

5. Задачі опуклого програмування.

Означення 1. Функція f(x₁, x₂, ….. x_n), що задана на опуклій множені Х, називається опуклою, якщо для будь – яких двох крапок Х₁, Х₂ є Х і довільного µє[0; 1] виконується співвідношення:

f(µX₁+(1-µ) X₂) ≤ µ f(X₁) +(1-µ) f(X₂)

Означення 2. Функція f(x₁, x₂, ….. x_n), що задана на опуклій множині Х, називається вгнутою, якщо для будь яких двох крапок Х₁, Х₂ є Х і довільного µє[0; 1] виконується співвідношення

f(µX₁+(1-µ) X₂) ≥ µ f(X₁) +(1-µ) f(X₂).

Якщо f(x₁, x₂, ….. x_n) – опукла, то - f(x₁, x₂, ….. x_n) – вгнута.

Загальна постановка задачі опуклого програмування:

Z=f(x₁, x₂, ….. x_n) → max (13)

за умов

g_i(x₁, x₂, ….. x_n) ≤ b_i, i=1, 2…..m (14)

x_j ≥ 0 j=1, 2, …..n (15)

де f – вгнута і g_i - опуклі функції

Надалі припустимо, що ОДР задачі (13) – (15) не порожня й обмежена.

Теорема 3. Довільний локальний максимум (мінімум) задачі опуклого програмування є глобальним максимумом (мінімумом).

Означення 3. Говорять, що множина ОДР задовольняє умову регулярності, якщо існує хоча б одна крапка

Означення 4. Говорять, що множина допустимих планів (13) – (15) задовольняє умові регулярності, якщо існує хоча б одна крапка х _i з області допустимих розв’язків така, що g_i(x_i)< b_i (i=1, 2, ….m).

Означення 5. Крапка (Х^*, Λ ^*) називається сідловою крапкою функції Лагранжа, якщо L(Х, Λ ^*) ≤ L(Х^*, Λ ^*)≤ L(Х^*, Λ) для всіх x_j ≥ 0 (j=1, 2, …n) і λ _i≥ 0 (i=1, 2, ….m).

Теорема 4. (Куна-Такера). Нехай для ОДР задачі опуклого програмування (13) – (15) виконується умова регулярності. План Х^*буде оптимальним планом цієї задачі тоді і тільки тоді, коли існує такий вектор Λ ^*, λ _i≥ 0 (i=1, 2, ….m), що пара (Х^*, Λ ^*) – сідлова крапка функції Лагранжа.

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

5. Задачі опуклого програмування.

Розглянемо задачу квадратичного програмування, яка є окремим випадком задач опуклого програмування.

Означення 6. Квадратичною формою відносно змінних x₁, x₂, ….. x_n називається функція Z, яка має вигляд Z=∑ ∑ с_jix_ix_j.

Означення 7. Квадратична форма Z називається додатньо (від’ємно) – визначеною, якщо Z(Х)> 0 (Z(Х)< 0) для всіх значень змінних Х, окрім крапки Х=(0, 0, ……0).

Означення 8. Квадратична форма Z називається додатньо (від’ємно) – напіввизначеною, якщо Z(Х) ≥ 0 (Z(Х) ≤ 0) для будь якого набору значень змінних Х =(x₁, x₂, ….. x_n) і, крім того, існує такий набір змінних Х^*, де не всі змінні одночасно рівні нулю, що Z(Х) =0.

Теорема 5. Квадратична форма є опуклою функцією, якщо вона додатньо-напіввизначена.

Постановка задачі квадратичного програмування має вигляд:

Z=∑ ∑ с_jix_ix_j.+ ∑ d_jx_j→ max/ min (16)

за умов

∑ a_ijx_j ≤ b_i, (i=1, 2…..m),

x_j ≥ 0 (j=1, 2…..n),

де ∑ ∑ с_jix_ix_j - від’ємно (додатньо) – напіввизначена квадратична форма.

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

1. Складаємо функцію Лагранжа.

2. Записуємо необхідні і достатні умови існування сідловок точки для функції Лагранжа.

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

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

Питання для самоконтролю.

1. Сформулюйте задачу дробово-лінійного програмування.

2. Сформулюйте задачу цілочисельного програмування.

3. Напішить рівняння Гоморі.

4. Сформулюйте загальну задачу НП.

5. Сформулюйте задачу сепарабельного програмування.

6. Сформулюйте задачу квадратичного програмування.

7. Сформулюйте задачу опуклого програмування.

8. Поясніть метод множників Лагранжа.

9. Сформулюйте означення сідловок точки функції Лагранжа.

10. Сформулюйте теорему Куна-Такера.

11. Сформулюйте означення додатньо-визначеної квадратичної форми.

12. Сформулюйте означення додатньо-напіввизначеної квадратичної форми.

Тема 7. Елементи теорії ігор

Лекція 7.

Тема лекції: Матричні ігри

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

План лекції

1. Постановка задач теорії ігор з нульовою сумою.

2. Задачі з сідловою точкою. Задачі в чистих стратегіях.

3. Ігри в мішаних стратегіях.

4. Зведення задач теорії ігор до задач ЛП.

Література:

1. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1993. – 336 с.

2. Іванюта І.Д. Практикум з математичного програмування: Навчальний посібник/ І.Д. Іванюта, В.І. Рибалка, І.А. Рудоміра – Дусятська. – К.: «Слово», 2008. – 296 с.

3. Катренко А. В. Дослідження операцій: Підручник / А. В. Катренко. -Львів: Магнолія Плюс, 2004. -549 с.

1. Постановка задач теорії ігор з нульовою сумою.

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

В 1944 році з’явилася математична дисципліна – теорія ігор, основою для якої стала монографія американського економіста Неймана.

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

Результат гри є виграшем для одних і програшем для других.

Означення 1. Модель любої конфліктної ситуації зветься грою.

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

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

Означення 4. Кількісна оцінка результатів гри зветься платою.

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

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

2. Задачі з сідловою точкою. Задачі в чистих стратегіях.

Розглянемо парну гру:

Приклад 1. Задана платіжна матриця А парної гри з нульовою сумою: А= . Знайти ціну гри, сідлову точку гри.

Приклад 2..Задана платіжна матриця А парної гри з нульовою сумою: А= . Знайти верхнью та нижню ціну гри.

3. Ігри в мішаних стратегіях. Основна теорема теорії ігор.

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

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

Нехай х₁ – ймовірність вибору 1-ої стратегії;

х₂ - ймовірність вибору 2-ої стратегії;

…………………………………………………

x_m - ймовірність вибору m-ої стратегії.

Означення 1. Мішаною стратегією гравця А називається упорядкований набір m чисел х₁, х₂, ….., x_m, які задовольняють умовам: 0≤ x_i≤ 1, i= =1.

Мішані стратегії гравців А та В позначають =(x₁, x₂, …, x_m), =(y₁, y₂, …, y_n).

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

Теорема. О методі знаходження рішення.

Для того, щоб число ν було ціною гри, а Х^* та Y^* - оптимальними стратегіями, необхідно та достатньо, щоб виконувались умови:

j=

i=

Визначення оптимальних стратегій та ціни гри створюють процес знаходження рішення гри.

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

Розглянемо гру з платіжною матрицею 2х2: A= .

Якщо сідлової точки нема, рішення гри є мішані стратегії =(х₁, х₂) та =(y₁, y₂) стратегії гравців А та В, для котрих ймовірністі x_i y_i відмінні від нуля, звуться активними.

Стратегію гравця А шукаємо по формулі ХА= , де Х=(х₁, х₂), =(ν, ν).

До даної системи рівнянь додаємо норміровочне рівняння х₁+х₂=1.

Для гравця В:

де Y= , = .

Розв’язавши систему рівнянь знайдемо оптимальні стратегії гравців та ціну гри ν.

Наслідок. Для того, щоб х^*, була оптимальною мішаною стратегією матричнох гри з матрицею А та ціною гри ν, необхідно та достатньо, щоб виконувались наступні нерівності:

j=

Аналогічно для гравця В: Для того, щоб у^* булла оптимальною мішаною стратегією матричної гри з матрицею А та ціною гри ν, необхідно та достатньо, щоб виконувались наступні нерівності:

i=

Таким чином, для розв’язування гри необхідно визначити стратегії, що задовольняють вишенаведані системи обмежень та умови нормування:

0, =1, i= , , =1, j= .

Цей наслідок дозволяє сформулювати для розв’язання гри пару задач лінійного програмування.

4. Зведення задач теорії ігор до задач ЛП.

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

j= , x_i≥ 0, =1, i= за умов ν → Мах.

Перетворимо цю задачу, здійснивши підстановку p_i= , і отримаємо

→ Min, тому що ν → Мах.

Таким чином, маємо задачу ЛП, розв’язуючи яку, отримаємо значення p_i, за допомогою яких шляхом оберної підстановки визначимо оптимальні значення ймовірностей, що складають оптимальну мішану стратегію.

А здійснивши підстановку q_j= і враховуючи, що гравець В прагне мінімізувати програш, отримаємо пару двоїстих задач ЛП, розв’язання яких дозволить визначити оптимальні стратегії гравців А та В:

.

Таким чином, процедура розв’язування гри двох осіб є наступною:

1. Розраховуємо нижню та верхню ціну гри; якщо вони рівні між собою, то гра розв’язана.

2. Спрощуємо гру шляхом виключення домінованих стратегій.

3. Формулюємо пару задач ЛП, розв’язавши одну з яких, встановлюємо оптимальну мішану стратегію одного з гравців (зручніше гравця В).

4. За розв’язком прямої задачі знаходимо розвязок двоїстої.

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

Питання для самоконтролю.

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

2. Дайте визначення сідловок точки.

3. Дайте визначення середнього виграшу.

4. Що таке чиста стратегія?

5. що таке мішана стратегія?

6. Що таке домінована стратегія?

7. Сформулюйте основну теорему теорії ігор для двох осіб.

8. Як звести задачу теорії ігор до задачі ЛП?

Тема 8. Аналіз та управління ризиком в економіці

Тема 8. Система показників кількісного оцінювання ступеня ризику

Лекція 8.

Тема лекції: Ризики. Оцінка ризиків.

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

План лекції

1. Поняття ризику. Причини виникнення, класифікація ризику.

2. Політика управління ризиком.

3. Методи оцінки ризику.

Література:

1. Вітлинський В.В. Аналіз, оцінка і моделювання економічного ризику. - К: ДЕМІУР, 1996, – 212 с.

2. Івченко І.Ю. Економічні ризики: Навчальний посібник.- К: «Центр навчальної літератури», 2004. – 304с.

3. Камінський А.Б. Економічний ризик та методи його вимірювання. - К: Козаки, 2002. – 120с.

4. Нейман фон Дж., Моргенштерн О. Теория игр и экономическое поведение. - М: Наука, 1970. – 338с.

5. Трояновский В.М. Математическое моделирование в менеджменте. - М: РДЛ., 2000. – 252с.

6. О.І. Ястремський. Моделювання економічного ризику. - К: Либідь, 1992. – 176с.

1. Поняття ризику. Причини виникнення, класифікація.

Підприємництво завжди поєднане з невизначеністю, яка виникає, наприклад, у таких випадках:

· Невизначеність зовнішнього середовища;

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

· Невизначеність у багатоваріантності сфер застосування капіталу;

· Невизначеність у різноманітності критеріїв надання переваги інвестування коштів;

· Невизначеність, пов’язана з обмеженнями знання про предметну галузь бізнесу і т.п.

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

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

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

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

Ризик є моделлю зняття суб’єктом невизначеності, адже прагнучи «зняти» ризиковану ситуацію, суб’єкт робить вибір і прагне реалізувати його. Таким чином, ризик виникає за таких умов:

1. наявність невизначеності;

2. необхідність вибору альтернативних рішень;

3. можливість оцінити ймовірність здійснення цих рішень

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

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

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

Найбільш розповсюджені визначення ризику:

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

Оскільки ризик може відбутися, а може і не відбутися, то можливі три результати:

«-» - збиток, «0», «+» - прибуток.

Для розуміння природи підприємницького ризику фундаментальне значення має зв'язок ризику і прибутку.

Особливо цікавим є розгляд класичної та неокласичної теорії.

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

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

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

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

Під кваліфікацією ризиків слід розуміти поділ на окремі групи за певними ознаками для досягнення певних цілей.

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

У залежності від можливого результату (ризикованої події) ризики можна поділити на дві великі групи: чисті і спекулятивні.

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

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

До них відносяться фінансові ризики, які є частиною комерційних ризиків.

2. Політика управління ризиками.

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

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

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

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

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

- об’єкт керування;

- суб’єкт керування.

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

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

Для успішного володіння ризиковими ситуаціями підприємцям слід дотримуватися основних принципів керування ризиками:

1. Не можна ризикувати більше, ніж дозволяє власний капітал.

2. Не можна ризикувати великим за ради малого.

3. Необхідно думати про наслідки ризику.

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

А) визначити максимально можливий обсяг збитків у випадку настання ризикової події;

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

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

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

3. Методи оцінки ризику.

Кількісні методи оцінки ризиків

Для прийняття рішення потрібно знати величину (ступінь) ризику, що вимірюється двома критеріями:

1.середне очікуване значення МХ= Σ Р_i х_i

2. коливання (мінливість) можливого результату σ (х)= D^1/2(x)=(MX²- (Mx)²)^1/2

Приклад. Якщо відомо, що при вкладенні капіталу у захід А із 120 випадків прибуток у 12, 5 тис. був отриманий 48 випадках (ймовірність 0, 4=48/120), прибуток у 20 тис. у 42 випадках (ймовірність 0, 35=42/120), і прибуток у 12 тис. у 30 випадках (ймовірність 0, 25=30/120), то середне очікуване значення виразиться в 15тис.

МХ= Σ Р_i х_i= 15.

Аналогічно буде знайдено, що при вкладенні капіталу в захід В середній прибуток становив 20 тис. (15х0, 3+20х0, 5+27, 5х0, 2=20).

Порівнюючи дві суми очікуваного прибутку при вкладенні капіталу у заходи А і В можна зробити висновки, що при вкладенні в захід А величина прибутку коливається від 12, 5 до 20 тис. і середня величина становить 15 тис.

При вкладенні капіталу у захід В величина одержаного прибутку коливається від 15 тис. до 27, 5 тис. і середня величина становить 20 тис.

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

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

Для цього на практиці звичайно застосовують σ (х).

Коефіцієнт варіації γ =(σ /М)х100%.

Коефіцієнт варіації відносна величина. Чим більше коефіцієнт, тим сильніше коливання.

В економічній статистиці встановлена така оцінка різних значень коефіцієнта варіації:

до 10% - слабке коливання;

10-25% - помірне коливання;

понад 25% - високе коливання.

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

Можливі такі випадки:

- M_a=M_b, σ _a< σ _b, слід обрати проект А

- M_a> M_b, σ _a< σ _b, слід обрати проект А

- M_a> M_b, σ _a= σ _b, слід обрати проект А

- M_a> M_b, σ _a> σ _b

- M_a< M_b, σ _a< σ _b.

В останніх двох випадках рішення про вибір проекту А чи в залежатиме від становлення до ризику, особи яка приймає рішення (ОПР).

Приклад.

Х_а=320, Х_в=320, σ _a=127, σ _b=185.

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

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

Означення 1. Статистична гра – це матрична гра, один із гравців якої є природа.

Дії природи не носять характер свідомості проти водії. Природа розглядається як деяка незацікавлена сторона, стан якої заздалегідь невідомий. Гравцю необхідно прийняти рішення в умовах невизначеності. Ця невизначеність обумовлена відсутністю інформації о можливих станах природи. Аналіз статичної гри починається з формування платіжної матриці, в котрій з одного боку гравець А виступає як активна сторона, а гравцем В є природа. Тоді елемент платіжної матриці a_ij – це виграш гравця А при використанні їм стратегії A_i, коли природа знаходиться в стані S_j.

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

В деяких випадках від матриці виграшем слід переходити до матриці ризиків.

Означення 2. Ризик r_ij гравця А при використанні стратегії A_j, при умовах знаходження природи у стані S_j є різниця між виграшем котрий він би отримав якби він знав стан природи S_j та виграшем, котрий він отримає застосувавши стратегію A_j в умовах відсутності інформації о стані природи:

r_ij = β _j- a_ij, r_ij≥ 0,

де β _j=max a_ij

_{1 ≤ i≤ m}

Матриця ризиків дає більш наглядову картину невизначеності ситуації, так як із матриці ризиків R=(r_ij) видно, чим ризикує гравець А прийнявши ту чи іншу стратегію. Інакше, величина ризику – це розмір платні за відсутність інформації о стані природи.

Можливі три ступені невизначеності стану природи:

1. Задані q_j (j=1, 2, 3, …., n) ймовірності знаходження природи в кожному стані

2. Ймовірності станів природи q_j невідомі, однак можливо зробити припущення відносно іх значень.

3. Ймовірності q_j невідомі і зробити припущення відносно іх розподілу немає можливості.

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

S_ср=max () – максимальний середній виграш (1)

R_ср=min() – мінімальний середній ризик (2)

Умова (1) еквівалентна умові (2).

Приклад. Сільське господарче підприємство має можливість вирощувати одну з трьох культур: картоплю, буряк, кукурудзу. Прибуток від врожаю залежить від стану природи. Можливі слідуючи стани природи:

S₁ – літо жарке та сухе;

S₂ – літо жарке, але з прохолодою;

S₃ – літо жарке, але з дощем;

S₄ – літо прохолодне, але з дощем.

Підприємство може вибрати одну із стратегій:

А₁ – вирощувати картоплю;

А₂ – вирощувати буряк;

А₃ – вирощувати кукурудзу.

Прибуток з одного гектара для кожної із стратегії А = { А₁, А₂, А₃} та можливих погодних умов представлені у таблиці 9.1.

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

Згідно даних метеослужби за 10 років в цій місцевості стани погоди були такими:

S₁ – 1 раз; S₂ – 2 рази; S₃ – 5 разів; S₄- 2 рази.

На основі цих даних знаходимо оцінки ймовірностей для кожного стану природи: q₁ = 0, 1; q₂ = 0.2; q₃ = 0.5; q₄ = 0.2. тоді розрахуємо середній максимальний виграш:

S_{1, ср} = 1*0.1 +4*0.2+5*0.5+9*0.2=5.2.

S_{2, ср} = 3*0.1 +8*0.2+4*0.5*9*0.2=4.5.

S_{3, ср} = 4*0.1+6*0.2+6*0.5+2*0.2= 5.

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

Побудуємо матрицю ризиків (таблиця 2).

Таблиця 2

Тоді

R_{1, ср} = 0.1*3+0.2*4+0.5*1+0*0.2=1.6

R_{2, ср} = 0.1*1+0.2*0+0.5*2+0.2*6=2.3

R_{3, ср} = 0.1*0+0.2*2+0.5*0+0.2*7=1.8.

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

Випадок 2. Включає три підходи.

1 підхід. Всі стани рівно ймовірні q₁ = q₂ = q₃ = q₄= …… =q_n

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

Наприклад, можна назначити ймовірності станів природи пропорційно членам убутної арифметичної послідовності: q_j = , де n – максимальний індекс стану.

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

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

Дамо декілька критеріїв оптимальності при виборі стратегії: максімакса, максимальний критерій Вальда, критерій мінімального ризику Севіджа, компромісний критерій Гурвіца.

Критерій максімакса:

: W()= maxmax a_ij

A_i S_j

Це критерій крайнього оптимізму.

Критерій Вальда:

: W()= maxmin a_ij

A_i S_j

Це критерій крайнього песимізму.

Критерій мінімального ризику Севіджа:

: R()= minmax a_ij

A_i S_j

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

Критерій песимізму – оптимізму Гурвіца:

: H()= max{α min a_ij + (1-α)max a_ij},

A_i S_j S_j

де 0≤ α ≤ 1. α - вибирається суб’єктивно в залежності від лиця, що приймає рішення (від його відношення до ризику). Чим блище α до 1, тим менший ризик, тобто α – міра песимізму.

При α =1 критерій Гурвіца співпадає з критерієм Вальда, при α =0 з критерієм крайнього оптимізму.

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

Приклад.

Є можливість побудувати 4 типа електростанцій:

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

Платіжна матриця для задачі вибору типу електростанції. Таблиця 3.

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

=A₂: W(A₂)= max{8, 12, 10, 8}=12 –критерій максімакса

=A₃: W(A₃)= max{2, 2, 3, 1}=3 – критерій Вальда

=A₃: R(A₃)= min{8, 6, 5, 7}=5 – критерій Севіджа

=A₂: H(A₂)= max{0.5(8+2); 0.5(2+12); 0.5(3+10); 0.5(1+8)} – критерій Гурвіца при α =0, 5.

Матриця ризиків для задачі вибору типу електростанції. Таблиця 4.

Питання для самоконтролю.

1. Що таке невизначеність?

2. Що таке ризик?

3. Класифікація ризику.

4. Стратегія керування ризиком

5. Тактика керування ризиком.

6. Основні принципи керування ризиком.

7. Зв'язок ризику і прибутку.

8. Зв'язок ризику і втрати.

9. статистичне визначення ризику.

10. Які класи математичних моделей використовують при моделюванні ризику?