Исследование базовой стохастической транспортной задачи

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

Действительно, цена перевозки единицы продукции может варьироваться в зависимости от объема перевозки, конъюнктуры цен, стоимости горючего и просто внешних по отношению к объекту управления обстоятельств. Еще хуже дело обстоит с объемами производства и потребления продукции, которые могут в еще большей степени зависеть от выполнения производственного плана, в условиях предприятий ЛПК – от погодных условий и пр. [5].

Рассмотрим классическую сетевую транспортную задачу [1], [3], заданную на сети G = {V,E } с параметрами c [ E ] - ценами перевозки, b [ V ] – мощностями узлов графа, потоками x [ E ] и A [ V , E ] – матрицей инцидентности графа G :

T : cx ^ min, Ax = b, x >  0 . (1)

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

Таким образом, возникает стохастическая ТЗ, численные компоненты которой являются случайными значениями, распределенными по определенным законам [4]. Фактически все важные ТЗ относятся к классу стохастических транспортных задач (СТЗ), поскольку их численные параметры не могут быть определены точно. Однако на практике решаются только ТЗ. Основная причина тому – отсутствие необходимого математического аппарата как средств постановки, так и решения подобных задач.

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

Действительно, требование сбалансированности:

Е b = ⁰ (2)

ieV равенства нулю суммы нескольких случайных значений, противоречит природе рассматриваемого класса задач.

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

Кроме того, возникает проблема определения оптимальности детерминированного решения транспортной задачи в условиях меняющихся правых частей задачи: действительно, вектор x >  0, который является решением системы Ax = b , чаще всего не будет являться решением системы линейных уравнений Ax = b .

Итак, исходная задача для дальнейшего исследования может быть сформулирована следующим образом. Пусть T_b - транспортная задача, вектор мощностей вершин которой b[V ] является случайным вектором, заданным на множестве векторов B с индексным множеством V , причем для любого b e B сумма

Е b = 0. i e V

Требуется построить оптимальное решение x * = x * [V ], обеспечивающее наименьшее значение математического ожидания функции цели, которой соответствуют вектора правых частей уравнений баланса, распределенных с заданной плотностью p_B на множестве правых частей B .

Прежде всего обеспечим существование решений задачи (1). Для этого напомним, что граф G является сильно связным, если для любой пары его вершин i , j e V существует путь из i в j , и докажем теорему 1.

Теорема 1. Транспортная задача (1) в сетевой постановке имеет оптимальное решение при любом векторе правых частей b , удовлетворяющем условию (2) тогда и только тогда, когда граф G - сильно связен.

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

Достаточность. Установим что О _b * 0 при любом b с условием (2), если G сильно связен. Это очевидно, если b = 0 . Первоначально определим вектор b [ V ] равным вектору мощностей вершин - b [ V ] = b [ V ]. Пусть V с V - множество вершин i e V , для которых b [ i ] Ф 0. Тогда, по условиям теоремы, первоначально имеет место условие:

Е b > 0. (*) i e V

Построим допустимое решение (1) редукцией V ' . Найдем вершину i e V ' , для которой 5 = b [ i ] >  0 принимает наименьшее значение. В силу условия (*) имеется вершина i ' e V ' : b [ i ] >  5 ., b ' [ i ] • b [ i ' ] <  0. Но в силу сильной связности графа существует путь из i в i ' , следовательно, существует поток величины 5 из i в i, и мощности этих двух вершин можно согласованно уменьшить на величину 5 , причем условие (*) продолжит выполняться.

Необходимость. Пусть G не является сильно связным. Тогда имеется пара вершин i ' , i ' e V , такая, что путь из i ' в i ’^ в графе G отсутствует. Положим b [ i ] = 1, b [ i ] = - 1, остальные значения b [ i ] = 0 ( i Ф i ' , i ). Очевидно, что такая задача допустимого решения не имеет. На этом доказательство теоремы 1 закончено.

С целью установления понятия оптимальности логично ввести базовую, простейшую задачу рассматриваемого класса. С этой целью выберем некоторый числовой вектор b ⁰ :

Еь 0 = 0, ieV два элемента i-, i+ e V, и определим множество B как пару векторов b0 и b1 = b0 + Ab, где Ab[i+ ] = а > 0, Ab[i- ] = -а < 0, Ab[i] = 0, если i Ф i-,i+ , и плотностью 0 < p < 1 для b0 и 1 - p для b1 .

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

Пусть x ⁰, z ⁰ - оптимальное решение и значение функции цели задачи (1) для правых частей b ⁰ и x ¹, z ¹ - для правых частей b ¹. Тогда взвешенная сумма с весами p и 1 - p обеспечивает ожидаемое значение функции цели Z * = pz ⁰ + (1 - p ) z ¹ для плана X = px ⁰ + (1 - p ) x ¹, однако этот план не является допустимым ни для одной из этих задач.

Чтобы снять эту проблему, введем систему компенсаций за неполноту поставок. С этой целью модифицируем задачу (1) следующим образом:

T : cx + dy + Dw ^ min, Ax + y - w = b , x , y , w >  0.

Задачу (3) назовем транспортной задачей с компенсированными мощностями вершин. В условиях y , w >  0 все уравнения баланса Ax + y - w = b соблюдаются, следовательно, x ⁰ и x ¹ являются допустимыми решениями задачи (3). В такой ситуации возникает вопрос оптимальности решения X относительно вновь введенной компенсированной целевой функции.

С этой целью вычислим математическое ожидание функции цели для произвольного X >  0 решения базовой задачи. Действительно, в случае b = b ⁰ векторы у ⁰ и w ⁰ определяются соотношениями Ax + у ⁰ - w ⁰ = b ⁰ и с вероятностью p обеспечивают значение целевой функции z ⁰ = cX + dy ⁰ + Dw ⁰. В случае b = b ¹ векторы y ¹ и w ¹ определяются соотношениями Ax + y ¹ - w ¹ = b ¹ и с вероятностью 1 - p обеспечивают значение целевой функции z ¹ = cX + dy ¹ + Dw ¹. Таким образом, математическое ожидание этого значения составляет:

E_z = ( cX + dy ⁰ + Dw ⁰) p + ( cX + dy ¹ + Dw ¹ )(1 - p ) = = cX + d ( py ⁰ + (1 - p ) y 1 ) + D ( pw ⁰ + (1 - p ) w ¹).

Учитывая, что векторы y ⁰ , w ⁰ и y ¹ , w ¹ определяются соотношениями: y ⁰ = max{ b ⁰ - AX ,0}, w ⁰ = max{ - b ⁰ + AX ,0} и y ¹ = max{ b ¹ - AX ,0}, w ¹ = max{ - b ¹ + AX ,0}, причем y ⁰[ i ] = y 1 [ i ] и w ⁰[ i ] = w 1 [ i ] для всех i * i ₀, получим:

Ez = cX + ^ (d [ i ] y 0[ i ] + D[ i ] w 0[ i ]) + pd max{ b 0[ i0] - i * i0

- A[ i, E ] X [ E ],0} + (1 - p) d max{ b 1[ i0 ] - A[ i0, E ] X [ E ], 0} + +pD max {b 0[ i0 ] - A[ i0, E ] X [ E ], 0} + (1 - p) D max {b 1[ i 0 ] -- A[ i0, E ] X [ E ],0} = cX + ^ (d [ i ] y 0[ i ] + D [ i ] w 0[ i ]) + ф i * i0

Здесь ф = -(1 - p)aD[i], если y0[i] > 0, ф = pad[i], если y0[i] > -a, n Ф = -(1 -p)у0[i"^ad[i] + p(у0[i0] + a)D[i], если y0[i] < 0 < y0[i] + a .

На практике величина этой функции – плата за отклонение мощности вершины от требуемой величины – измеряется в тех же денежных единицах, что и затраты на перевозку продукции. Будет также естественно предположить, что в практически востребованных случаях эта функция является кусочно-линейной, выпуклой и ф _i (0) = 0.

В таком случае СТЗ приобретает содержание поиска детерминированного потока в заданной транспортной сети, для которого сумма затрат на перевозку продукта, увеличенная на математическое ожидание суммарного штрафа за отклонение мощностей вершин, составляет наименьшее возможное значение.

Значение целевой функции СТЗ для заданного детерминированного плана x также можно истолковать как среднее значение затрат на перевозку продукции и выплату штрафных значений за отклонения требуемых поставок по всем вершинам транспортной сети с учетом распределения ожидаемых мощностей вершин.

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

Тем не менее в некоторых, достаточно общих случаях практическое решение СТЗ сводится к решению обычной сетевой ТЗ специального вида с некоторым расширением размерности исходной задачи и не требует специальных методов решения [2].

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

Оптимизация в планировании предприятиями регионального лесопромышленного комплекса. Петрозаводск: Изд-во ПетрГУ, 2001. 217 с.