Стохастичне програмування.

Лекція 11

9.Стохастичне програмування.

10.Основи теорії графів і галузь її застосування.

11.Суть теорії ігор і її застосування.

12.Застосування апарату теорії ігор для аналізу проблем мікроекономіки

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

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

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

При розв'язанні завдань в стохастйчній постановці зазвичай використовують два підходи.

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

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

Таких ступенів (етапів) може бути декілька. Стільки, скільки необхідно для досягення оптимального рішення. Таким чином, наприклад, діють при необхідності досягнення оптимального розподілу ресурсів з врахуванням ймовірних умов розв'язання завдання. При такому підході так само успішно розв'язуються транспортні завдання при невизначеному попиті на розподілену продукцію, сировину, матеріали і т.п.

Як відомо, загальну постановку завдання лінійного програмування можна показати у вигляді:

де задані величини c_j, a_ij, b_i d_j, D_j:. Часто на практиці величини c_j, a_i_j, b_i можуть бути випадковими. Якщо b_i — ресурс, то він залежить від ряду факторів. Аналогічно с_i — ціни — будуть залежати від попиту і пропозицій а_ij — розхідні коефіцієнти — від рівня техніки і технології.

Завдання, в яких c_j, а_ij, b_i — випадкові величини, відносять до завдань стохастичного програмування. Випадковий характер величин виявляють ріними способами: 1) реалізацією випадкових величин; 2) законом розподілу випадкових величин.

Стохастична постановка цільової функції може бути двох видів: М-постановка і Р-постановка.

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

де c_j — математичне очікування випадкової величини с_j.

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

При Р-постановці цільова функція буде мати вигляд:

• максимізація цільової функції

означає максимізацію можливості того, що випадкова величина

буде не менше деякого значення r;

мінімізація цільової функції буде не менше деякого значення r;

мінімізація цільової функції

означає максимізацію можливості того, що випадкова величина

буде не більше деякого значення r.

Математичний опис обмежувальних умов спирається на оцінки ймовірності їх виконання:

Аналогічний зміст мають й інші обмеження.

Приклад розв'язання завдання методом стохастичного програмування наведений в додатку 2.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Динамічне програмування.	\|	Основи теорії графів і галузь її застосування.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.003 сек.