3. Двокрокова лінійна модель

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

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

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

Максимізувати (9.5)

при обмеженнях

(9.6)

(9.7)

Припустимо тепер, що коефіцієнти у виразі для цільової функції є випадковими величинами, причому значення всіх керованих перемінних потрібно визначити в умовах відсутності інформації про те, які значення будуть у дійсності приймати . Така ситуація може виникнути, наприклад, при рішенні задачі планування, коли майбутні ринкові ціни на вироблені товари і „майбутня” вартість робочої сили у момент розробки плану точно не відомі. Оскільки всі коефіцієнти a_іj, а також константи b_i визначені однозначно, вибір допустимих значень х_j не представляє ніяких труднощів.

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

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

Максимізувати (9.8)

при обмеженнях (9.6) та (9.7) задається значеннями перемінних х_j, що задовольняють умові

Максимізувати (9.9)

при обмеженнях (9.6) та (9.7).

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

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

х₁ – кількість лісу в тоннах, призначеного для одержання пиломатеріалів;

х₂ – кількість лісу в тоннах, призначеного для виготовлення фанери;

х₃ – кількість лісу в тоннах, що не підлягає переробці.

Допустимо, що до кінця місяця з х₁ тонн лісу буде зроблене a₁х₁ кубометрів пиломатеріалів, а з х₂ тонн лісу вийде а₂х₂ тисяч листів фанери. Позначимо через D₁ максимальна кількість пиломатеріалів, а через D₂ максимальна кількість фанери, що фірма може продати до кінця місяця. Нехай ринкова ціна 1 м³ пиломатеріалів (продукту 1) дорівнює r₁, а ринкова ціна тисячі аркушів фанери (продукту 2) дорівнює r₂; тоді величина являє собою повну виручку, отриману фірмою при реалізації продукту . Допустимо далі, що вартість переробки 1 т лісу в продукт j дорівнює е_j; таким чином, є сумарні витрати, зв’язані з виробництвом продукту j. Отже, якщо покласти , то величина буде являти собою сумарний прибуток, одержуваний за рахунок продукту . Крім того, фірма отримує прибуток у розмірі , реалізувавши невикористаний ліс на ринку; при цьому ринкова ціна 1 т лісу передбачається не залежною від х₃ (вона залишається на колишньому рівні навіть у тому випадку, коли х₃ = Т).

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

Максимізувати (9.10)

при обмеженнях

(наявний у наявності ліс), (9.11)

(попит на пиломатеріали), (9.12)

(попит на фанеру), (9.13)

(9.14)

де s_i – незадоволений попит на продукт i.

На практиці, однак, частіше зіштовхуються із ситуаціями, коли ринкові ціни на кожний з видів продукції, що випускаються, коливаються в часі (наприклад, змінюються щотижня) у залежності від рівнів запасів (або постачань) сировини та рівнів попиту. Отже, фірма буде мати у своєму розпорядженні точні дані про ціни r₁ та r₂ (а значить, і про с₁ та с₂) лише кілька тижнів після ухвалення рішення щодо значень x₁, х₂ та х₃. Крім того, піддані випадковим коливанням значення a₁ та а₂, а також потенційні рівні ринкового попиту D₁ та D₂. Тому s₁ та s₂ будуть практично визначені лише після того, як стануть відомими a_j та D_j). І нарешті, якщо перевищить максимальний рівень попиту, частина продукції фірми залишиться нереалізованою. Таким чином, очевидно, що у випадку, коли величини a_j та D_j є випадковими, структура обмежень моделі (9.11) — (9.13) виявляється недовизначеною.

Для повноти представлення оптимізаційної моделі припустимо, що фірма повинна позбутися від надлишку продукції, реалізуючи її за зниженими цінами. Щоб відобразити цю обставину, додамо (– t₁) до лівої частини співвідношення (9.12), (–t₂) до лівої частини співвідношення (9.13) і (–f₁t₁ –f₂t₂) до виразу для цільової функції (9.10), інтерпретуючи як надлишок продукту і, а ( ) як втрату прибутку у випадку збуту одиниць продукції за зниженими цінами.

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

Підводячи підсумки проведеного вище аналізу, вкажемо основні етапи рішення задачі:

1. Перший крок. Фірма підбирає значення , розташовуючи точними даними лише щодо значень .

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

3. Другий крок. Фірма визначає значення . При наявності зазначеної вище інформації фірма вибирає значення , що максимізує очікуваний прибуток.

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

(9.15)

Щоб звести задачу до стандартної задачі лінійного програмування, приймемо ще один постулат щодо характеру невизначеності: будемо припускати, що можливо лише кінцеве число Q станів, що характеризуються сукупністю показників ( ). Покладемо для приклада Q = 3, тобто допустимо, що можливі лише наступні комбінації для елемента ( ):

( ) з імовірністю ,

( ) з імовірністю , (9.16)

( ) з імовірністю ,

причому . За допомогою (9.16) легко обчислити

а знаючи та , визначити з (9.15) . Отже формулювання розглянутої двокрокової моделі виглядає так:

Максимізувати

(9.17)

при обмеженнях

(наявний у запасі ліс), (9.18)

(попит на пиломатеріали при q = 1), (9.19)

(попит на фанеру при q = 1), (9.20)

(попит на пиломатеріали при q = 2), (9.21)

(попит на фанеру при q = 2), (9.22)

(попит на пиломатеріали при q = 3), (9.23)

(попит на фанеру при q = 3), (9.24)

(9.25)

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

1. Детерміноване обмеження на обсяг наявного лісу, що враховується на першому кроці, представлено співвідношенням (9.18).

2. Є три групи (Q = 3) обмежень, кожна з яких визначає можливий набір значень випадкових величин, а саме [(9.19), (9.20)], [(9.21), (9.22)] і [(9.23), (9.24)].

3. Керовані перемінні першого кроку фігурують у кожній із груп обмежень, зазначених у п. 2. Коефіцієнтами при цих перемінних є числа, обумовлені допустимими значеннями відповідних випадкових величин при q = 1, 2, 3.

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

5. У вираз для цільової функції входять безумовні математичні чекання питомих прибутків, пов’язаних з відповідними керованими перемінними першого кроку.

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

Висновок. Нижче приводиться загальний опис двокрокової лінійної моделі. Використовуючи позначення, прийняті для детерміністського аналога стохастичної моделі [див. (9.5) – (9.7)], приймемо щодо останньої наступні припущення:

1) Значення випадкових величин не залежать від x_j (j = 1, 2, ...).

2) Значення x_j (j = 1, 2, ..., k ≤ n) повинні фіксуватися на першому кроці до того, як стануть відомими фактичні значення, що приймають випадкові величини.

3) Обмеження i = 1, 2, ..., g містять тільки перемінні першого кроку, причому відповідні значення та є відомими.

4) Завжди існують допустимі значення інших перемінних (що обираються на другому кроці) x_j (j = k + 1, ..., n). Значення цих перемінних підлягають визначенню після того, як стають відомими фактичні значення всіх випадкових величин.

5) Існує кінцеве число Q можливих комбінацій значень с_j (j = k + 1, ..., n), а_ij (i = g + 1, ..., m; j = k + 1, ... , n) та b_i (i = g + 1, ..., m); обумовлені ними стани прийнято позначати через (c_qi, a_qij, b_qi), а імовірності їхньої появи – через p_q (q = 1, 2, ..., Q).

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

Максимізувати (9.26)

при обмеженнях

(перший крок), (9.27)

(правило для ухвалення

рішення на другому кроці), (9.28)

. (9.29)

Якщо якіcь з коефіцієнтів

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