Стохастическая транспортная задача
Обычная транспортная задача имеет целевую функцию и ограничения в виде
.
Будем рассматривать задачу при различном характере спроса, который является случайной величиной, т. е. зависит от случайных параметров w,
bj=bj¢(w) . (10.8)
При этом возможны два варианта формулировки модели задачи.
Вариант 1. Пусть спрос bj непрерывно распределен с плотностью вероятности . Примем
– это общий объем продукта, предназначенный в соответствии с планом, составленным до реализации bj (w), для j-го пункта потребления.
После определения спроса может оказаться, что yj < bj(w), тогда спрос не будет удовлетворен, и ущерб за невыполнение потребности будет пропорционален величине невыполнения с некоторым коэффициентом qj, где qj - штраф за невыполнение заявки за каждую единицу недовезенного продукта. Общий ущерб определяется как
(10.9)
В случае избытка, аналогично, возрастают затраты на хранение пропорционально величине избытка с коэффициентом (коэффициент штрафа за избыток). Общий ущерб от избытка при
будет
. (10.10)
Математическое ожидание суммарных потерь, связанных с перевозкой продукта, ущерба от неудовлетворенного спроса и затрат на хранение избыточных продуктов определяется следующей целевой функцией
, (10.11) где пределы интегрирования очевидны и определяются на рис. 10.1 избыточным (1) или недовезенным грузом (2) функции плотности распределения jj (bj).
В общем виде целевая функция может быть представлена как
(10.12)
Продифференцируем дважды по
,
Это означает, что , а вместе с ней и F (x,y) будут функцией, выпуклой вниз относительно
.
Таким образом, детерминированный эквивалент стохастической транспортной задачи с непрерывно распределенным спросом представляет собой задачу выпуклого программирования с нелинейной целевой функцией и линейной системой ограничений.
Вариант 2. Пусть спрос bj(w) распределен дискретно и в j-м пункте потребления принимает значения bik с вероятностями: pjk (k=1…s). Аналогично ранее рассмотренной задаче ,
- коэффициенты штрафа за дефицит и издержки хранения единицы продукции.
Введем вспомогательные переменные vjk, иjk - величины избытка и дефицита в j-м пункте потребления при реализации k-го варианта спроса, т.е. при bj(w)=bjk .Целевая функция – математическое ожидание суммарных затрат – будет включать общую стоимость перевозок и штрафы за дефицит и избыток:
(10.13)
Всегда имеет место равенство , которое означает, что спрос bjk удовлетворяется привезенным продуктом
и дефицитом иjk за вычетом избытка vik. Подставляя полученное значение bjk в целевую функцию после преобразования, получаем:
. (10.14)
Второе слагаемое не содержит параметра управления, поэтому формально в модели может не учитываться.
Таким образом, детерминированный эквивалент стохастической транспортной задачи с дискретно распределенным спросом представляется моделью линейного программирования с целевой функцией fd и линейными ограничениями:
,
(10.15)
Последнее ограничение означает, что разница между запасами и удовлетворенным спросом определяется дефицитом или избытками.
Аналогично могут быть сформулированы и другие стохастические транспортные задачи, у которых случайным может быть, например, объем производства аi = ai(w).
Эти задачи могут быть также сведены к задачам выпуклого или линейного программирования.