Стохастическая транспортная задача

Обычная транспортная задача имеет целевую функцию и ограничения в виде

.

Будем рассматривать задачу при различном характере спроса, который является случайной величиной, т. е. зависит от случайных параметров w,

b_j = b_j^¢(w). (10.8)

При этом возможны два варианта формулировки модели задачи.

Вариант 1. Пусть спрос b_j непрерывно распределен с плотностью вероятности . Примем – это общий объем продукта, предназначенный в соответствии с планом, составленным до реализации b_j (w), для j- го пункта потребления.

После определения спроса может оказаться, что y_j < b_j(w), тогда спрос не будет удовлетворен, и ущерб за невыполнение потребности будет пропорционален величине невыполнения с некоторым коэффициентом q_j, где q_j - штраф за невыполнение заявки за каждую единицу недовезенного продукта. Общий ущерб определяется как

(10.9)

В случае избытка, аналогично, возрастают затраты на хранение пропорционально величине избытка с коэффициентом (коэффициент штрафа за избыток). Общий ущерб от избытка при будет

. (10.10)

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

, (10.11) где пределы интегрирования очевидны и определяются на рис. 10.1 избыточным (1) или недовезенным грузом (2) функции плотности распределения j_j (b_j).

 

В общем виде целевая функция может быть представлена как

(10.12)

Продифференцируем дважды по ,

Это означает, что , а вместе с ней и F (x,y) будут функцией, выпуклой вниз относительно .

Таким образом, детерминированный эквивалент стохастической транспортной задачи с непрерывно распределенным спросом представляет собой задачу выпуклого программирования с нелинейной целевой функцией и линейной системой ограничений.

Вариант 2. Пусть спрос b_j(w) распределен дискретно и в j -м пункте потребления принимает значения b_ik с вероятностями: p_jk (k= 1… s). Аналогично ранее рассмотренной задаче , - коэффициенты штрафа за дефицит и издержки хранения единицы продукции.

Введем вспомогательные переменные v_jk, и_jk - величины избытка и дефицита в j- м пункте потребления при реализации k- го варианта спроса, т.е. при b_j(w)=b_jk. Целевая функция – математическое ожидание суммарных затрат – будет включать общую стоимость перевозок и штрафы за дефицит и избыток:

(10.13)

Всегда имеет место равенство , которое означает, что спрос b_jk удовлетворяется привезенным продуктом и дефицитом и_jk за вычетом избытка v_ik. Подставляя полученное значение b_jk в целевую функцию после преобразования, получаем:

. (10.14)

Второе слагаемое не содержит параметра управления, поэтому формально в модели может не учитываться.

Таким образом, детерминированный эквивалент стохастической транспортной задачи с дискретно распределенным спросом представляется моделью линейного программирования с целевой функцией f _d и линейными ограничениями:

,

 

 

 

 

(10.15)

 

Последнее ограничение означает, что разница между запасами и удовлетворенным спросом определяется дефицитом или избытками.

Аналогично могут быть сформулированы и другие стохастические транспортные задачи, у которых случайным может быть, например, объем производства а_i = a_i(w).

Эти задачи могут быть также сведены к задачам выпуклого или линейного программирования.