9.7. Квадратична критеріальна функція

(лінійний вид оптимального рішення)

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

(1)

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

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

(2)

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

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

1) Замінимо в (1) і (2) та математичними чеканнями цих величин, обчисленими за допомогою відповідних безумовних розподілів імовірностей.

2) Підставимо , знайдені за допомогою (1), у вираз (2).

3) Зберемо члени з однаковими перемінними .

4) Дорівняємо нулю часткові похідні квадратичної форми по для .

5) Розв’яжемо рівняння, отримані в результаті виконання п. 4), відносно , де .

6) Визначимо за допомогою (1) x_i для i = 1, 2, ..., т.

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

Задача регулювання чисельності обслуговуючого персоналу. Директору ресторану необхідно визначити число офіціанток, потрібних для обслуговування відвідувачів у години „пік” кожен t-й день протягом періоду тривалістю Т днів (тобто t = 1, 2, ..., Т). Щоденна зміна числа офіціанток обходиться ресторанe дорого по цілому ряду причин (зокрема, тут діє психологічний фактор і та обставина, що досвідчені офіціантки є досить дефіцитними). Не вигідно також мати занадто багато або занадто мало офіціанток, оскільки, у першому випадку зростають витрати, пов’язані з виплатою офіціанткам заробітної плати, а в другому випадку виникають втрати за рахунок відходу частини відвідувачів, які не бажають чекати обслуговування занадто довго. Разом з тим, точно визначити число потрібних офіціанток неможливо, тому що щодня флуктує як число відвідувачів, так і обсяг трудових витрат на їх обслуговування.

Позначимо через D_t обсяг трудових витрат (у людино-годинах) на обслуговування майбутніх відвідувачів ресторану в години „пік” t-го дня.

Нехай y_t означає обсяг трудових витрат (у людино-годинах) на обслуговування в t-й день, на який орієнтується директор ресторану при складанні календарного плану. Позначимо через f_t різницю між трудовими витратами в t-й день і трудовими витратами в (t – 1)-й день (тобто флуктуацію обсягу трудових витрат), а через e_t – помилку, що допущена при плануванні трудових витрат для t -го дня; згадані вище величини задовольняють співвідношенням

(флуктуація трудових витрат), (3)

(помилка, допущена при плануванні), (4)

де у₀ – обсяг трудових витрат напередодні 1-го дня. У розглянутому прикладі перемінні f_t та e_t відіграють ту ж роль, що і перемінні , а перемінні y_t – ту ж, що і перемінні , що фігурують в (1).

Нехай задача полягає в тому, щоб мінімізувати очікуване значення квадратичної форми

(5)

при обмеженнях (3) і (4), де – задане число. Помітимо, що якщо , то оптимальним є рішення y_t = y₀ для всіх значень t. Якщо є доволі великим, то оптимальне рішення має вигляд . На першому кроці визначенню підлягає значення y₁.

Виконуючи пп. 1 та 2 зазначеної вище послідовності, замінимо у (4) D_t на Е[D_t] і підставимо у вираз (5) f_t та e_t, що визначаються співвідношеннями (3) та (4). У результаті будемо мати

(6)

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

(7)

(8)

(9)

При заданих значеннях с, Е[D_t] та у₀ система рівнянь (7) – (9) вирішується однозначно. Одержуване в результаті значення y_t є оптимальним для першого кроку прийняття керуючих рішень і лінійно залежить від Е[D_t].

Допустимо, що плановий період практично не обмежений, причому значення перемінної у₁ вибирається таким, щоб воно було оптимальним при як завгодно великій довжині Т. Тоді можна показати, що, вирішивши систему (7) – (9) відносно у₁ при Т→∞, одержимо

(необмежений період планування), (10)

де передбачається, що сума, що стоїть у правій частині, має кінцеве значення. У виразі (10)

і, отже, при , a . Ще раз звернемо увагу на те, що є лінійна функція , що безпосередньо видно з (10). Після одержання зведень про фактичне значення D_t директор ресторану може переглянути свої прогнози щодо наступних значень D_t, так що на наступний день обчислення по формулі (10), можливо, прийдеться виконати заново, замінивши на математичне чекання потреб у трудових витратах для другого дня (знайдене з урахуванням повної інформації про і т.д.). Однак, у тому випадку, коли для всіх t незалежно від того, якими були фактичні значення D_t у попередні дні (тобто якщо розподіл імовірностей очікуваних трудових витрат виявиться стаціонарним), то значення y_t для всіх наступних днів визначаються формулою

(стаціонарні потреби в обслуговуванні) (12)

для , та при .

• Запитання для самоконтролю

1. Що потрібно проаналізувати при розгляді оптимізаційних моделей ?

2. Які шляхи до оптимального рішення ?

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

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

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

6. Як формулюється задача оптимізації на мережах ?

7. Який критерій мінімізації в транспортних мережах ?

8. В чому полягає багатокрокова лінійна модель ?

9. В чому полягає лінійний оптимального рішення ?

178