Линейное і динамічний программирование

Лінійне программирование.

Завдання лінійного оптимального планування — одне з найважливіших математичних інструментів, які у економіці. Розглянемо підприємство, яка з m видів ресурсів виробляє n видів продукції. Приймемо такі позначення: і - номер групи ресурсу (i=1,2, …, m); j — номер виду продукції (j=1,2, …, n); aij — кількість одиниць i-го ресурсу, расходуемое виробництва однієї одиниці j-го виду продукції; bij — запаси i-ro ресурсу; xi — плановане кількість одиниць j-й продукції; cjприбутку від однієї одиниці j-го виду продукції; X=(x1, x2,…, xn) — шуканий план виробництва, називається допустимим якщо наявних досить. називається допустимим якщо наявних ресурсів досить. Вже згадана завдання відшукати припустимого плану, що дає максимальну прибуток із усіх допустимих вирішення аналогічних завдань, званих завданнями лінійного програмування. Припустимо, що це підприємство може випускати чотири такого роду продукцію, використовуючи при цьому три виду ресурсів. Відома технологічно матриця, А витрат будь-якого ресурсу на одиницю кожної продукції, вектор У обсягів ресурсів немає і вектор З удільної прибыли.

48 30 29 10 удільні прибыли.

добові норми витрат 3 2 4 3 198.

2 3 1 2 96.

6 5 1 0 228 запаси ресурсів Означимо х1, х2, х3, х4 — число одиниць 1-ї, 2-ї, 3-й, 4-й продукції, які плануємо зробити. У цьому можна використовувати лише наявні запаси ресурсів. Метою є отримання прибутку. Отримуємо таку математичну модель оптимального планування: L (x1,x2,x3,x4)=48xl+30×2+29×3+10×4 (max.

3х1+2×2+4×3+3×4?198.

2х1+3×2+1×3+2×4?96.

6х1+5×2+1×3+0×4?228 xj?0, jєN4 Аби вирішити отриманої завдання у кожне нерівність додамо неотрицательную зміну. Після цього нерівності перетворяться на рівності, це що додаються перемінні називаються засадничими. Виходить завдання ЛЗ на максимум, все перемінні неотрицательны, все обмеження є рівності це і є базисний набір змінних: х5 — у 1-му рівність, х6 — у 2-му і х7 — 3-му. Нині можна запускати симплекс-метод. L (x1,x2,x3,x4)=48xl+30×2+29×3+10×4 (max.

3х1+2×2+4×3+3×4+x5 =198.

2х1+3×2+х3+2×4 +x6 =96.

6х1+5×2+х3 +x7=228 xj?0, jєN7.

Таблиця N 1 |З |B |H |48 |30 |29 |10 |0 |0 |0 | | | | |x1 |x2 |x3 |x4 |x5 |x6 |x7 | |0 |x5 |198 |3 |2 |4 |3 |1 |0 |0 | |0 |x6 |96 |2 |3 |1 |2 |0 |1 |0 | |0 |x7 |228 |6 |5 |1 |0 |0 |0 |1 | | | |0 |-48 |-30 |-29 |-10 |0 |0 |0 |.

Якщо всі оціночні коефіцієнти (сірого кольору) неотрицательны, то отримано оптимальне рішення: базисні перемінні рівні вільним членам, інші рівні 0. Якщо є негативний оціночний коефіцієнт, то знаходять самий малий їх. Якщо стовпці коефіцієнтів з нього немає позитивних, то завдання має шляхів владнання. Завдання оптимального планування може бути такою, тому шукають мінімальне ставлення вільних членів шпальти М до позитивним коефіцієнтам зазначеного xj. У перетині рядки — і шпальти отримуємо що дозволяє елемент і далі будуємо нову таблицю. Таблиця N 2 |З |B |H |48 |30 |29 |10 |0 |0 |0 | | | | |x1 |x2 |x3 |x4 |x5 |x6 |x7 | |0 |х5 |84 |0 |-Ѕ |31/2 |3 |1 |0 |-3/6 | |0 |x6 |20 |0 |11/3 |2/3 |2 |0 |1 |-2/6 | |48 |х1 |38 |1 |5/6 |1/6 |0 |0 |0 |1/6 | | | |1824 |0 |10 |-21 |-10 |0 |0 |-8 |.

Таблиця N 3.

|C |B |H |48 |30 |29 |10 |0 |0 |0 | | | | |x1 |x2 |x3 |x4 |x5 |x6 |x7 | |29 |х3 |24 |0 |-1/7 |1 |6/7 |2/7 |0 |-1/7 | |0 |x6 |4 |0 |13/7 |0 |13/7 |-4/21 |1 |-5/21 | |48 |х1 |34 |1 |6/7 |0 |-1/7 |-1/21 |0 |4/21 | | | |2328 |0 |7 |0 |8 |6 |0 |5 |.

Оптимальний рішення (виробничу програму): Xоpt=(34; 0; 22; 0); максимум цільової функції дорівнює 2328. Значення перемінної з номером і великим 4-х є залишок (i-4)-ro ресурсу. «Гак й усе оціночні коефіцієнти неотрицательны, то отримано оптимальне рішення: базисні перемінні рівні вільним членам, інші рівні 0.

Слід звернути увагу до економічний сенс елементів останньої рядки останньої симплексной таблиці. Наприклад, коефіцієнт ?2=7 при перемінної х2 показує, що й зробити одну одиницю продукції другого виду (вона входить у оптимальну виробничу програму), то прибуток зменшиться на майже 7 одиниць. Зауважимо, що у аналізованому прикладі лінійної виробничої завдання можлива самоперевірка результату. Скористаємося тим, що у оптимальної виробничої програмі х2=0, х4=0. Припустимо, що другу четверту продукції ми мали намір випускати від початку. Розглянемо завдання за які залишилися двома перемінними, зберігаючи їхню нумерацію. Математична модель завдання буде виглядати наступним образом:

L (x1,x3)=48xl+29×3 (max.

3х1+4×3?198.

2х1+ х3? 96.

6х1+ х3?228×1?0, x3?0 Завдання лінійного програмування з цими двома перемінними можна вирішити графічно. Візьмемо на площині систему координат: вісь OX3 спрямуємо горизонтально і вправо, вісь OХ1 -вертикально і вгору. Кожне обмеження завдання, раз воно лінійне нестрогое нерівність, графічно змальовується полуплоскостью, гранична пряма який відповідає не нерівності, а рівності. Дозволене безліч завдання є перетином всіх таких полуплоскостей це і є опуклий багатокутник. Друга із двох основних теорем лінійного програмування говорить: Якщо екстремум цільової функції досягається на допустимому безлічі, то функція приймає їх у якийсь вершині многоугольника-допустимого безлічі. З цієї теореми, знайти шуканий екстремум можна просто перебравши вершини багатокутника і визначивши ту, у якій значення функції екстремально. Частіше роблять інакше: будують лінію рівня цільової функції і рухають її паралельно у бік экстремума, намагаючись вловити останню крапку перетину лінії з допустимим множеством.

Двоїста завдання лінійного программирования.

Завдання лінійного оптимального планування — вихідна у своїй парі симетричних двоїстих завдань. Взагалі інша завдання в двоїстої парі будується так: 1) меняется тип экстремума цільової функції (mах на min і навпаки); 2) коэффициенты цільової функції одного завдання стають вільними членами інший завдання; 3) свободные члени одного завдання стають коефіцієнтами цільової функції двоїстої завдання; 4) тип нерівностей змінюється (? на? і навпаки); 5) кожен стовпець одного завдання породжує рядок обмежень інший завдання і навпаки. У матрично-векторном вигляді обидва завдання такі: вихідна завдання двоїста завдання L=(c, x)(max Z=(b, y)(min Ax? b, x?0 Ya? c, y?0,.

L (x1,x2,x3,x4)=48xl+30×2+29×3+10×4 (max Z (y1,y2,y3,y4)=198yl+96y2+228y3 (min.

3х1+2×2+4×3+3×4?198 3y1+2y2+6y3?48.

2х1+3×2+1×3+2×4?96 2y1+3y2+5y3?30.

6х1+5×2+1×3+0×4?228 4y1+ y2 + y3?29 xj?0, jєN4 3y1+2y2?10 yj?0, jєN3.

Рішення отриманої завдання легко знайти з допомогою другий основний теореми двоїстості, за якою для оптимальних рішень X (x1, x2, x3, x4) і Y (y1, y2, y3) пари двоїстих завдань необхідне й досить виконання условий:

x1(3y1+2y2+6y3−48)=0 y1 (3×1+2×2+4×3+3×4)-198=0×2(2y1+3y2+5y3−30)=0 y2 (2×1+3×2+1×3+2×4)-96=0×3(4y1+1y2+1y3−29)=0 y3 (6×1+5×2+1×3+0×4)-228=0×4(3y1+2y2+0y3−10)=0 У рішенні вихідної завдання х1>0, х3>0, тому 3y1+2y2+6y3−48=0 4y1+1y2+1y3−29=0 З огляду на, що другий ресурс був надлишковим і, відповідно до теоремі двоїстості його оцінка дорівнює нулю — y2=0, то дійшли системі: 3y1+6y3−48=0 4y1+1y3−29=0 з яка повинна, що y1=6; y3=5. Отже отримали двоїсті оцінки ресурсів: y1=6; y2=0; y3=5; загальна оцінка всіх ресурсів Z=198y1+228y3=2328.

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

Таблиця N 3.

|C |B |H |48 |30 |29 |10 |0 |0 |0 | | | | |x1 |x2 |x3 |x4 |x5 |x6 |x7 | |29 |х3 |24 |0 |-1/7 |1 |6/7 |2/7 |0 |-1/7 | |0 |x6 |4 |0 |13/7 |0 |13/7 |-4/21 |1 |-5/21 | |48 |х1 |34 |1 |6/7 |0 |-1/7 |-1/21 |0 |4/21 | | | |2328 |0 |7 |0 |8 |6 |0 |5 |.

Рішення одній з пари двоїстих завдань можна знайти, знаючи лише відповідь до інший завданню користуючись 2-ї теоремою двоїстості: якщо i-e обмеження одній з пари двоїстих завдань на компонентах оптимального рішення є суворе нерівність, то оптимальне значення i-го перемінної інший завдання одно 0, чи, що таке саме — якщо оптимальне значення j-й перемінної одного завдання суворо позитивно, то j-e обмеження більше з пари двоїстих завдань на компонентах оптимального рішення є рівність. Важливий економічний сенс двоїстих оцінок. Двоїста оцінка, наприклад, третього ресурсу у3=5 показує, що додавання однієї одиниці третього ресурсу забезпечить приріст прибутку п’ять единиц.

Розшивка «вузьких місць «производства.

Таблиця N 3.

|C |B |H |48 |30 |29 |10 |0 |0 |0 | | | | |x1 |x2 |x3 |x4 |x5 |x6 |x7 | |29 |х3 |24 |0 |-1/7 |1 |6/7 |2/7 |0 |-1/7 | |0 |x6 |4 |0 |13/7 |0 |13/7 |-4/21 |1 |-5/21 | |48 |х1 |34 |1 |6/7 |0 |-1/7 |-1/21 |0 |4/21 | | | |2328 |0 |7 |0 |8 |6 |0 |5 |.

За виконання оптимальної виробничої програми не перший і третій ресурси використовуються повністю, цим вони утворюють «вузькі місця «виробництва. Будемо їх замовляти додатково. Нехай Т=(t1,t2,t3) — вектор додаткових обсягів ресурсів. Оскільки ми будемо використовувати знайдені двоїсті оцінки ресурсів, те має виконуватися умова H+QlТ?0, де М — значення базисних змінних у вищій симплексной таблиці, а Q-1 — звернений базис, який утворюють стовпчики при балансових змінних у цій таблиці. Завдання у тому, щоб знайти вектор Т, максимізує сумарний приріст прибутку W=6t1+5 t3 за умови збереження двоїстих оцінок ресурсів (і, отже, асортименту випущеної продукції), припускаючи, які можна отримати додатково трохи більше 1/3 обсягу ресурсів кожного виду. 24 2/7 0 -1/7 t1 0 4 + -4/21 1 -5/21 0? 0 34 -1/21 0 4/21 t3 0.

t1 198 0? 1/3 96 t3 228 t1?0, t3?0.

W=6t1+5t3 (max -2/7 t1 + 1/7 t3? 24.

4/21 t1 + 5/21 t3? 4.

1/21 t1 — 4/21 t3? 34 t1?198/3, t3?228/3. t1?0, t3?0.

Як бачимо, після графічного рішення (Графік 2) програма розшивки набуває вигляду: t1=21, t2=0, t3=0.

С новим кількістю ресурсів: 198+21 219.

b «= 96+0 = 96.

228+0 228 в підприємства буде нова виробничу програму. Знайдемо h «=Q-1 b «.

5/28 0 -1/7 219 30 (x3.

— 4/7 1 -1/7 96 = 0 (x6.

— 3/28 0 2/7 228 33 (x1 Нині нова виробничу програму має вигляд: X «оpt=(33;0;30;0). При цьому другий ресурс використали полностью.

При наявності ресурсів b «= 96 виробництво найвигідніше, так как.

228 досягається max прибуток, із використанням всіх ресурсів. Також звернімо увагу, що виробництво продукції 1-го виду при замовленні додаткових ресурсів потрібно буде зменшити на 15 одиниць, а виробництво продукції 3-го виду — збільшити на одиницю. ?Lmax=(Y, t)=6?21=126, де Y=(6;0;5); t (21;0;0) L «max= ?Lmax+ Lmax=126+2328=2454. Цей результат можна перевірити, підставивши значення х1 і х3 у початкову цільову функцію: L «max=48xl+30×2+29×3+10×4=31?37+41?21=1147+861=2454.

Транспортна задача.

Транспортна завдання формулюється так. Однорідний продукт, зосереджений в т пунктах виробництва (зберігання) у кількості a1, А2,…, аm одиниць, необхідно розподілити між п пунктами споживання, яким необхідно відповідно b1, b2,…, bn одиниць. Вартість перевезення одиниці продукту з i-ro пункту відправлення в j-й пункт призначення дорівнює cij й всім маршрутів. Необхідно скласти план перевезень, у якому запити всіх пунктів споживання було б задоволені з допомогою наявних продуктів в пунктах виробництва та загальні транспортні витрати з доставки продуктів були минимальными.

Означимо через xij кількість вантажу, планованого до перевезення від i-ro постачальника j-му споживачеві. За наявності балансу виробництва та потребления.

[pic].

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

X=(xij), xij (0, i (Nm, j (Nn здатний мінімізувати загальну вартість всіх перевозок.

[pic].

за умови, що із будь-якої пункту виробництва вивозиться весь продукт.

[pic], i (Nm.

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

[pic], j (Nn.

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

А (а1,а2,а3)=(40;45;70); В (b1,b2,b3)=(48;30;29;40); 3 6 4 3.

З= 2 3 1 3.

6 5 1 4.

Загальний обсяги виробництва (ai=40+45+70=155 більше, ніж потрібно всім споживачам (bj=48+30+29+40=147, тобто. маємо відкриту модель транспортної завдання. Для перетворення їх у закриту вводимо фіктивний пункт споживання з обсягом споживання 155−147=8 одиниць, причому тарифи на перевезення у цей пункт умовимося вважати рівними нулю, пам’ятаючи, що перемінні, що додаються до лівим частинам нерівностей для перетворення на рівняння, входить у функцію цілі з нульовими коэффициентами.

Перше базисне дозволене рішення легко побудувати за правилом «северозахідного кута » .

Таблиця 1.

| |b1=48 |b2=30 |b3=29 |b4=40 |b5=8 | | |Потребл | | | | | | | |Произв | | | | | | | |a1=40 |40 |6 | |* | |p1=0 | | |3 | |4 |3 |0 | | |a2=45 |8 2|30 |7 1| | |p2=-1 | | | |3 | |3 |0 | | |a3=70 | | |22 |40 |8 0|p3=-1 | | |6 |5 |1 |4 | | | | |q1=3 |q2=4 |q3=2 |q4=5 |q5=1 | |.

Означимо через ((p1, p2,…, pm, q1, q2,…, qn) вектор симплексных множників чи потенціалів. Тоді (ij=(Aij-cij, i (Nm, j (Nn, звідки следует.

(ij=pi+qj-cij, i (Nm, j (Nn.

Поклавши, що p1=0. Інші потенціали знаходимо з умови, що з базисних клітин (ij=0. У разі получаем.

(11=0, p1+q1-c11=0, 0+q1−3=0, q1=3.

(21=0, p2+q1-c21=0, p2+3−2=0, p2= -1.

(23=0, p2+q3-c23=0, -1+q3−1=0, q3=2 аналогічно, одержимо: q2=4, р3=-1, q4=5, q5=1.

Потім обчислюємо оцінки всіх вільних клеток:

(12=p1+q2-c12=0+4−6= -2.

(13=p1+q3-c13=0+2−4=-2.

(14=2; (15=1; (24=1; (25=0; (31= -4; (32= -2.

Знаходимо найбільшу позитивну оцінку: mах ((ij >0)=2=(14,.

Для знайденою вільної клітини 14 будуємо цикл перерахунку — замкнуту ламану лінію, сусідні ланки якої взаємно перпендикулярні, самі ланки рівнобіжні рядкам і столбцам таблиці, одне з вершин перебуває у даної вільної клітині, проте інші - в зайнятих клітинах. Це буде 14−34−33- 23−21−11. Виконуємо перерозподіл поставок вздовж циклу пересчета:

|40 | | |* | |40-(| | |(| |33 | | |7 | |8 |30 |7 | |(|8+(| |7-(| |(|15 |30 | | | | | |22 |40 | | | |22+(|40-(| | | |29 |33 |.

(max=7.

Отримуємо друге базисне дозволене решение:

Таблиця 2.

| |b1=48 |b2=30 |b3=29 |b4=40 |b5=8 | | |Потребл | | | | | | | |Произв | | | | | | | |a1=40 |33 |6 | |7 | |p1=0 | | |3 | |4 |3 |0 | | |a2=45 |15 |30 |1 | | |p2=-1 | | |2 |3 | |3 |0 | | |a3=70 | |* |29 |33 |8 0|p3=1 | | |6 |5 |1 |4 | | | | |q1=3 |q2=4 |q3=0 |q4=3 |q5= -1| |.

Знаходимо нові потенціали. Нові оценки:

(12= -2; (13= -4; (15= -1; (23= -2; (24= -1; (25= -2; (31= -2; (32=0. Оскільки всі (ij (0 рішення є оптимальным:

33 0 0 7.

Xоpt1 = 15 30 0 0.

0 0 29 33.

Проте, оскільки оцінка клітини (32=0, бачимо про наявність іншого можливого оптимального рішення. На його перебування будуємо цикл перерахунку клітини 32: 32−22−21−11−14−34, виробляємо перераспределение:

Таблиця 3.

| |b1=48 |b2=30 |b3=29 |b4=40 |b5=8 | | |Потребл | | | | | | | |Произв | | | | | | | |a1=40 |3 3|6 | |37 | |p1=0 | | | | |4 |3 |0 | | |a2=45 |45 |3 |1 | | |p2=-1 | | |2 | | |3 |0 | | |a3=70 | |30 |29 |3 4|8 0|p3=1 | | |6 |5 |1 | | | | | |q1=3 |q2=4 |q3=0 |q4=3 |q5= -1| |.

Знаходимо нові потенціали. Отримуємо рi і qj відповідно рівні потенциалам першого базисного оптимального рішення (див. табл. 2). З цього (max=(32, проте елемент з індексом 32 вже є у базисі, тому перерахунок втрачає сенс. Отже отримуємо друге і останнє базисне оптимальне решение:

3 0 0 37.

Xоpt2 = 45 0 0 0.

0 30 29 3.

Оптимальний розподіл инвестиций.

Це завдання з n перемінними представляється, як многошаговый процес прийняття рішень. На кожен крок визначається екстремум функції лише з однієї перемінної. Нехай 4 фірми утворюють об'єднання. Розглянемо завдання розподілу інвестицій у розмірі 700 тис. рублів за цими 4 фірмам. Розмір інвестицій нехай буде кратний 100 тис. рублів. Ефект від напрямку i-го фірмі інвестицій у розмірі? (сотень тис. рублів) виражається функцією fi (xi). Приходимо до завданню fl (xl)+f2(x2)+f3(x3)+f4(x4)(max, де xi — поки що невідомий розмір х1+х2+х3+х4?7; х1, х2,х3.х4?0 інвестицій i-го фірмі. Ця завдання вирішується методом динамічного програмування: послідовно шукається оптимальне розподіл для k=2,3 і 4 фірм. Нехай першим двом фірмам виділено? інвестицій. позначимо z2(?) величину інвестицій 2-ї фірмі, коли він сума f2(z2j)+fl (?-z2j), 0? j?? максимальна, самі цю максимальний розмір позначимо F2(?). Далі діємо також: знаходимо функції z3 і F3 тощо. На k-ом кроці перебування Fk (?) використовуємо основне рекуррентное співвідношення: Fk (?)=max{fkj (хk)+F (k- 1)(?-хk); 0? хk? ?

|xj |0 |100 |200 |300 |400 |500 |600 |700 | |f1 |0 |28 |45 |65 |78 |90 |102 |113 | |f2 |0 |25 |41 |55 |65 |75 |80 |85 | |f3 |0 |15 |25 |40 |56 |62 |73 |82 | |f4 |0 |20 |33 |42 |48 |53 |56 |58 |.

Таблиця 1 | |?-х2 |0 |100 |200 |300 |400 |500 |600 |700 | | | | | | | | | | | | |x2 | | | | | | | | | | | | |0 |28 |45 |65 |78 |90 |102 |113 | | |F1(?-x2)| | | | | | | | | | | | | | | | | | | | | |f2(x2) | | | | | | | | | |0 |0 |0 |28 |45 |65 |78 |90 |102 |113 | |100 |25 |25 |53 |70 |90 |103 |115 |127 | | |200 |41 |41 |69 |86 |106 |119 |131 | | | |300 |55 |55 |83 |100 |120 |133 | | | | |400 |65 |65 |93 |110 |130 | | | | | |500 |75 |75 |103 |120 | | | | | | |600 |80 |80 |108 | | | | | | | |700 |85 |85 | | | | | | | |.

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

|? |0 |100 |200 |300 |400 |500 |600 |700 | |F2 |0 |28 |53 |70 |90 |106 |120 |133 | |x2 |0 |0 |100 |100 |100 |200 |300 |300 |.

Таблиця 2 | |?-х2 |0 |100 |200 |300 |400 |500 |600 |700 | | | | | | | | | | | | |х3 | | | | | | | | | | | | |0 |28 |53 |70 |90 |106 |120 |133 | | |F3(?-x3)| | | | | | | | | | | | | | | | | | | | | |f3(x3) | | | | | | | | | |0 |0 |0 |28 |53 |70 |90 |106 |120 |133 | |100 |15 |15 |43 |68 |85 |105 |121 |135 | | |200 |25 |25 |53 |78 |95 |115 |131 | | | |300 |40 |40 |68 |93 |110 |130 | | | | |400 |56 |56 |84 |109 |125 | | | | | |500 |62 |62 |90 |115 | | | | | | |600 |73 |73 |101 | | | | | | | |700 |82 |82 | | | | | | | |.

Жирним кольором вказано максимальний сумарний ефект від участі виділення відповідного розміру інвестицій по 3-му предприятиям.

|? |0 |100 |200 |300 |400 |500 |600 |700 | |F2 |0 |28 |53 |70 |90 |106 |121 |135 | |x2 |0 |0 |0 |0 |0 |0 |100 |100 |.

Таблиця 3 | |?-х4 |0 |100 |200 |300 |400 |500 |600 |700 | | | | | | | | | | | | |x4 | | | | | | | | | | | | |0 |28 |53 |70 |90 |106 |121 |135 | | |F4(?-x4)| | | | | | | | | | | | | | | | | | | | | |f4(x4) | | | | | | | | | |0 |0 | | | | | | | |135 | |100 |20 | | | | | | |141 | | |200 |33 | | | | | |139 | | | |300 |42 | | | | |132 | | | | |400 |48 | | | |118 | | | | | |500 |53 | | |106 | | | | | | |600 |56 | |84 | | | | | | | |700 |58 |58 | | | | | | | |.

Жирним кольором вказано максимальний сумарний ефект від участі виділення відповідного розміру інвестицій по 4-му предприятиям.

Зведемо результати на чотири таблиці. Тепер F4(7)=141 показує максимальний сумарний ефект за всі 4-му фірмам, a z4(7)=100 тис. крб. — розмір інвестицій у 4-ту фірму задля досягнення цього максимального ефекту. Перед інших трьох підприємств залишається 600 тис. крб. Третьему підприємству має бути виділено х*3=Х3(700-х*4)=Х3(600)=100 тис. крб. Продовжуючи зворотний процес, знаходимо х*2=Х2(700-х*4-х*3)=Х2(500)=200 тис. крб. Перед першого підприємства залишається х*1=700-х*4-х*3-х*2=300 тис. руб.

Отже, найкращим є що розподіл капітальних вкладень на підприємствах: х*1 =300; х*2 =200; х*3 = 100; х*4 = 100. Воно забезпечує виробничому об'єднанню найбільший можливий приріст прибутку 141 тис. руб.

Аналіз дохідності і ризику фінансових операций.

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

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

Є кілька різних способів оцінки операції з погляду дохідності і ризику. Найпоширенішим є уявлення доходу операції як випадкової розміру й оцінка ризику операції як середнього квадратического відхилення цього випадкового доходу. Проте кількісно оцінити ризик можливе лише якщо операція вероятностно характеризуема, тобто. її дохід є випадкова величина — це означатиме можливість кількаразового повторення цієї операції. Отже, нехай прибуток від операції Q є випадкова величина, яку будемо позначати як і саму операцію Q. Математичне очікування М[Q] називають ще середнім очікуваним доходом, а ризик операції r ототожнюють із середнім квадратическим відхиленням, тобто. квадратним коренем з дисперсії D[Q].

Розглянемо чотири операції Q1, Q2, Q3, Q4. Знайдемо середні очікувані доходи Qi й ризики ri, операций.

[pic]; [pic] ;

[pic]; [pic] .

|Q1: |0 |1 |2 |8 | | |1/3 |1/3 |1/6 |1/6 |.

Q1=0(1/3+1(1/3+2(1/6+8(1/6=2 M[Q12]= 02 (1/3+12 (1/3+22 (1/6+82 (1/6=11,7 D[Q1]= 11,7−22=7,7 r1=2,77.

|Q2: |2 |3 |4 |10 | | |1/3 |1/3 |1/6 |1/6 |.

Q2=4 M[Q22]=23,7 D[Q2]=7,7 r2=2,77.

|Q3: |0 |4 |6 |10 | | |1/5 |1/5 |1/5 |2/5 |.

Q3=6 M[Q32]=50,4 D[Q3]=14,4 r3=3,8.

|Q4: |2 |6 |8 |12 | | |1/5 |1/5 |1/5 |2/5 |.

Q4=8 M[Q42]=78,4 D[Q4]=14,4 r4=3,8.

Завдамо середні очікувані доходи Q й ризики r на площину — дохід відкладаємо за горизонталлю, а ризики за вертикаллю (див. графік 3); Отримали 4 точки. Чим правіше точка (Q, r), тим паче дохідна операція, ніж точка вище — тим паче вона ризикована. Отже, потрібно вибирати точку правіше і від. Крапка (Q ", r ") домінує над точкою (Q, r) якщо Q «>Q і r «0.

Розглядаємо варіант, коли У грає у змішаних стратегіях, а П — в чистих стратегіях вибирає першу строку.

— 7/11= 2y-5(1-y) y*= 48/77 q*=(48/77, 0, 0, 29/77) — оптимальна змішана стратегія В.

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

У страхової компанії застраховане N1=900 чоловік віком 45 років і N2=550 чоловік віком 55 років терміном однією рік. Компанія виплачує спадкоємцям: 100 000 крб., разі смерті застрахованої від нещасного випадку, і 25 000 крб., разі смерті природних причин протягом року. Компанія не платить нічого, Якщо людина проживе цього року. Припустимо, що смертність описується моделлю Мейкхама і розрахуємо неттопремію, ціну поліса, страхову надбавку, щоб ймовірність неразорения компанії становила 0,95.

Індивідуальні позови x[pic] і x[pic] кожного з застрахованих 1-ой і 2-ой груп визначаються, відповідно, рядами розподілу (для зручності за грошову одиницю приймемо 100 000 руб.).

0 ј 1 (1) x[pic].

[pic]=0,9982 [pic]=0,0013 [pic]=0,0005.

0 ј 1 x[pic].

[pic]=0,9962 [pic]=0,0044 [pic]=0,0005.

Тут можливості смерті від від нещасного випадку приймемо рівними 0,0005, а можливості смерті природних причин з Таблиці тривалості жизни.

Середні індивідуальні позови Мx[pic] і Мx[pic] рівні відповідним нетто-премиям Р[pic] і Р[pic] клієнтам компанії 1-ой і 2-ой групп.

Р[pic] = Мx[pic] = ј*0,0013 + 1*0,0005 «0,83 = 83 крб. (2).

Р[pic] = Мx[pic] = ј*0,0044 + 1*0,0005 «0,0016 = 160 руб.

I. Спочатку розглянемо рішення, заснований на розподілі Пуассона.

Щоб звести завдання до схемою дослідів Бернуллі можна наближено замінити ряди розподілу (1) такими таблицами:

0 М (x[pic]/x[pic]№ 0) 0 М (x[pic]/x[pic]№ 0) x[pic]: x[pic]: (3).

[pic] [pic] [pic] [pic].

а потім у ролі умовної грошової одиниці прийняти умовні математичні очікування М (x[pic]/x[pic]№ 0) в 1-ой таблиці і М (x[pic]/x[pic]№ 0) — у 2-ой.

Обчислимо умовні математичні ожидания:

М (x[pic]/x[pic]№ 0)=ј*Р (x[pic]=ј/x[pic]№ 0)+1*Р (x[pic]=1/x[pic]№ 0) =.

=ј*[pic]/([pic])+1*[pic]=.

=ј*0,0044/(0,0044+0,0005)+1*0,0005/(0,0044+0,0005)= =ј*13/18+1*5/49 = 5/18 «0,458=45 800 крб. — грошова одиниця клієнтам 1- ой группы.

М (x[pic]/x[pic]№ 0=ј*[pic]/([pic])+1*[pic]=.

=ј*0,0044/(0,0044+0,0005)+1*0,0005/(0,0044+0,0005)= =. ј*44/49+1*5/49 = 16/49 «0,327=32 700 крб — грошова одиниця для клиентов.

2-ой группы.

З урахуванням інтересів усіх зауважень замість рядів розподілу (3) имеем:

0 1 0 1 x[pic]: x[pic]: (4).

0,9982 0,0018 0,9962 0,0049.

откуда отримуємо: Мx[pic] = 0,0018.

Мx[pic] = 0,0049.

Підрахуємо суму позовів від застрахованих 1-ой групи: l[pic] = [pic]Мx[pic] = N1* Мx[pic] = 400*0,0018 = 0,7 2-ой групи: l[pic] = [pic]Мx[pic] = N2* Мx[pic] = 1000*0,0049 = 4,9.

Загальна сума позовів можна розглядати, як випадкова пуассоновская величина з параметром l[pic]+l[pic] = 5,6.

Оскільки ймовірність не руйнування компанії мусить бути незгірш від 0,95, необхідно щоб задля спільної суми позовів від застрахованих x = [pic]x[pic] + [pic]x[pic] виконувалося співвідношення: Р (x Ј x) й 0,95, де x — капітал компанії. Вочевидь, що x = х[pic], тут х[pic]" 10- квантиль рівня 0,95 для розподілу Пуассона. за рахунок нетто-премий компанія може мати простий лише сумму:

5,6=0,7*45 800 крб. + 4,9*32 700 крб. = 32 060 руб.+1 060 230 крб. =.

192 290 руб. Тому страхова надбавка компанії повинна составлять:

R=(10−5,6)/5,6 (100% «78,6% = 0,786*192 290 руб."1 511 400 руб., (5) а капітал компанії: x = 192 290 крб. + 151 140 крб. «343 430 крб. (6).

Отже, індивідуальні страхові надбавки r[pic] і r[pic], ціни полісів Р[pic] і Р[pic] кожного з клієнтів 1-ой і 2-ой групи відповідно рівні (вони пропорційні нетто-премиям):

r[pic] = 0,52*Р[pic] = 0,52*83 крб. «43 крб., r[pic] = 0,52*Р[pic] = 0,52*160 крб. «83 руб.,.

(7).

Р[pic] = Р[pic] + r[pic] «43 крб. + 83 крб. = 126 руб.,.

Р[pic] = Р[pic] + r[pic] «160 крб. + 83 крб. = 243 руб.

II. Тепер вирішимо завдання за допомогою гауссовского наближення. Середнє значення загального сумарного позову від застрахованих x = [pic]Мx[pic] + [pic]Мx[pic] з урахуванням середніх індивідуальних позовів (2) равно:

Мx = N1*Mx[pic]+ N2* Мx[pic]=400*0,83+1000*0,0016=.

= 0,332 + 1,6 «1,9 = 190 000 руб.

(8) Дисперсию x у вигляді незалежності x[pic] і x[pic] обчислимо по формуле:

Dx = [pic]Dx[pic] + [pic]Dx[pic] «400*0,58 + 1000*0,78=.

=0,23 + 0,78 = 1,01. (9) Здесь:

Dx[pic] = М (x[pic])[pic] - М[pic]x[pic] = 0,58 — (0,83)[pic] «0,58 ,.

(10).

Dx[pic] = М (x[pic])[pic] - М[pic]x[pic] = 0,78 — (0,0016) [pic] «0,78 ,.

где з допомогою рядів розподілу (1) имеем:

М (x[pic])[pic] = 1/16*0,0013 + 1*0,0005 «0,58 ,.

(11).

М (x[pic])[pic] = 1/16*0,0044 +1*0,0005 «0,78.

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

S[pic]= (x — Mx)/[pic], при N1 + N2 ® Ґ має предел.

F (x) = (1/[pic])*[pic]dz Для гауссовского наближення випадкової величини x правильна наступна ланцюжок равенств:

Р (x < x) = Р ((x — Мx)/[pic] Ј (x — Мx)/[pic]) «F ((x — Mx)/[pic]), де x — капітал компанії. Щоб ймовірність неразорения компанії не перевершувала 0,95, т. е.

F ((x — Mx)/[pic]) й 0,95 має виконати соотношение.

(x — Mx)/[pic] й х[pic],.

(12) тут х[pic]" 1,645 — квантиль рівня 0,95 стандартного гауссовского распределения.

Неважко переконатися, мінімальна необхідний капітал компанії має становити: х=Мx+х[pic]*[pic]"1,9+1,645*1,005=1,9+1,65=3,55=355 000 руб., (13) а відносна страхова надбавка становить: х[pic]*[pic]/Мx*100%=1,65/1,9*100%"86,8% (14).

Індивідуальні страхові надбавки r[pic] і r[pic], ціни полісів Р[pic] і Р[pic] клієнтам 1-ой і 2-ой груп з урахуванням (2), очевидно дорівнюватимуть (страхові надбавки пропорційні нетто-премиям): r[pic] = 0,68*83 крб. «56 крб.; r[pic] = 0,68*160 крб. «109 руб.;

(15).

Р[pic] = Р[pic] + r[pic] «83 крб. + 56 крб. = 139 руб.;

Р[pic] = Р[pic] + r[pic] «160 крб. + 109 крб. = 269 руб.

III. Проаналізуємо результати, отримані в в.п. I і II. Вочевидь розбіжність результатів, отриманих під час використання пуассоновского і гауссовского наближень. Спробуймо розібратися, у яких причина цього различия.

Річ у тім, що час використання закону Пуассона заміна рядів розподілу (1) на ряди розподілу (3) призвела до того, що ні змінилися лише математичні очікування Мx[pic]и Мx[pic]. У той самий час дисперсії Dx[pic] і Dx[pic], які свідчать про ступеня розсіювання випадкових позовів x[pic] і x[pic], знайдених по рядах розподілу (1) і (3), різні. Отже, різняться дисперсії Dx, знайдені по рядах розподілу (1) і (3). Справді, дисперсія загального сумарного позову x по рядах (1) підрахована: Dx = 1,24 (див. співвідношення (9)).

Обчислимо дисперсию x по рядах розподілу (3), т. е.

0 0,458 0 0,327 x[pic]: x[pic]: (16).

0,9982 0,0018 0,9962 0,0049.

Провівши розрахунки, аналогічні (9−11), одержимо: Dx =[pic]Dx[pic] + [pic]Dx[pic] «400*0,38 + 1000*0,52 = 0,67. (17).

Здесь:

Dx[pic] = М (x[pic])[pic] - М[pic]x[pic] = 0,38 — (0,83)[pic] «0,38 ,.

(18).

Dx[pic] = М (x[pic])[pic] - М[pic]x[pic] = 0,52 — (0,0016) [pic] «0,52 ,.

причем:

М (x[pic])[pic] = 0,458[pic]*0,0018 «0,38 ,.

(19).

М (x[pic])[pic] = 0,327[pic]*0,0049 «0,52.

Надалі використовуватимемо такі позначення: дисперсию x, знайдену з допомогою рядів (1), позначимо s[pic], а дисперсию x, знайдену по рядах (3) чи (16), позначимо s[pic]. Отже, s[pic] = 1,01, а s[pic] = 0,67.

З формули (12), використовує стандартне гауссовское розподіл, безпосередньо слід, що відносна страхова надбавка, якщо Dx = s[pic] = 0,67, дорівнює х[pic]*s[pic]/Мx*100% = 1,645*[pic]/1,9*100% «70,9% (20).

Цей результат добре цілком узгоджується з відносної страхової надбавкою, котра враховує розподіл сумарного позову x згідно із законом Пуассона, рівної 86,8% (див. (5)).

Враховуючи сказане, напрошується природний висновок: якщо відносна страхова надбавка, капиталл компанії, який би неразорение компанії з імовірністю 0,95, і поліса обчислюються, виходячи з розподілу сумарного позову застрахованих згідно із законом Пуассона, то тут для перебування основних характеристик компанії необхідно провести поправочний коефіцієнт, рівний k = s1 /s2.

Проілюструємо застосування коефіцієнта k для корекції результатів, отримані п. I: страхова надбавка з урахуванням (5) стане равной:

R[pic]= k*R = [pic]*86,8%=1,2*86,8% «71,4% «135 660 крб. (21) капітал компанії (см.(6)) стане рівним: х[pic]= 190 000 крб. + 135 660 крб. «325 660 крб., (22) а індивідуальні страхові надбавки і полісів (см.(7)): r[pic][pic] = k*r[pic] «1,2*43 крб. «54 крб., r[pic][pic] = k*r[pic] «1,2*83 крб. «100 руб.,.

(23).

Р[pic][pic] = Р[pic] + r[pic][pic] «83 крб. + 54 крб. = 137 руб.,.

Р[pic][pic] = Р[pic] + r[pic][pic] «160 крб. + 100 крб. = 260 руб.

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