9.5. Випадок транспортної мережі

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

Мінімізувати

(9.44)

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

(пропозиція), (9.45)

(попит), (9.46)

для всіх значень i та j, (9.47)

де S_i можна інтерпретувати як наявний обсяг продукції, що очікують навантаження в i-му пункті відправлення, a D_j – як обсяг продукції, необхідний у j-му пункті призначення (j-му споживачу), причому модель побудована у припущенні, що сумарна пропозиція дорівнює сумарному попиту ( ).

Будемо вважати, що основними етапами оптимізаційного процесу є наступні:

1) Перший крок. При наявності точних даних щодо значень S_i, та, можливо, деяких з D_j потрібно вибрати значення всіх керованих перемінних .

2) Одержання інформації відносно часткових наслідків. Стають відомими фактичні значення випадкових величин D_j. Значення D_j виявляються незалежними від вибору значень перемінних .

3. Другий крок. Визначається „фактичний” обсяг незадоволеного попиту або надлишкової продукції.

Помітимо, що в силу п. 3) на другому кроці в моделі (9.44) – (9.47) з’являються п перемінних

(9.48)

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

Мінімізувати (9.49)

при обмеженнях (9.45) та (9.46). Фігурують у (9.49) середні значення випадкових величин, визначені з урахуванням безумовного розподілу імовірностей для .

Відзначимо важливу особливість приведеної вище двокрокової моделі: на другому кроці проблеми оптимізації не існує. Значення перемінних другого кроку за допомогою (9.48) однозначно визначаються значеннями перемінних, обраними на першому кроці, та значеннями, прийнятими випадковими величинами . Ця особливість моделі цілком використовується при рішенні задачі, і, таким чином, на відміну від випадку, розглянутого раніше, відпадає необхідність оперувати детерміністським аналогом вихідної стохастичної моделі. Приймемо ще два постулати, що дозволяють звести двокрокову стохастичну модель (9.45), (9.47) – (9.49) до математично еквівалентній їй звичайній транспортній задачі. По-перше, припустимо, що можливо лише цілочисельні значення (для всіх значень j). Визначимо для кожного значення j

(сумарний обсяг постачань в j-й пункт призначення) (9.50)

та введемо величину

(очікувані втрати, пов’язані з j-м пунктом призначення). (9.51)

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

По-друге, допустимо, що є опукла функція:

(для всіх

цілочисельних значень xj). (9.52)

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

Метод імовірнісних обмежень. Досить повчальним може виявитися порівняння розглянутої двокрокової моделі з варіантом цієї моделі, побудованим методом імовірнісних обмежень, у якому поряд з детермінованою цільовою функцією (9.44) та обмеженнями на пропозицію (9.45) і попит (9.46) для j = 1, 2, а також умовами незаперечності керованих перемінних (9.47) приймаються наступні обмеження:

та (імовірнісні обмеження), (9.53)

де сумарний обсяг постачань в j-й пункт призначення визначається по формулі (9.50). Таким чином, згідно з (9.53), необхідно, щоб імовірність задоволення рівнів попиту (j = 3, 4) була не менше , причому можуть приймати будь-як значення в інтервалі (0, 1). Помітимо, що співвідношення (9.53) орієнтовані на запобігання випадків незадоволення попиту, тоді як співвідношення (9.33) та (9.34) забезпечують усунення ситуацій, при яких обсяг постачань перевищує існуючі рівні попиту.

При заданих значеннях та задача з імовірнісними обмеженнями еквівалентна задачі, в якій замість (9.53) розглядається обмеження

(детерміністський еквівалент), (9.54)

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

. (9.55)

Інші компоненти моделі, тобто цільова функція (9.44) і обмеження (9.45) та (9.46) для j = 1, 2, залишаються без змін.