Моделирование сложных вертикально-интегрированных производственных систем в нефтегазовой отрасли

Баев В.А.

Сформулированная задача относится к классу задач следующего вида :

Ф=r(t) y(t) c(t) dt+ K (t ) Q (T-t ) min(= Ф*) (2.1)

по у(t), t при

Ay(t) £ a(t) + D Q (t-t );

Bq (t-t ) £ b(t), у(t)Î R ₊^m , t = (t _i )Î R ₊ⁿ;

t _i Î {[ D _i ,T ], +¥ }, i=1, 2, …, n,

где c(t) – вектор функция (строка) размерностью m;

r(t) – скалярная функция;

K (t ) – вектор-строка, каждая компонента которой является функцией соответствующей компоненты вектора t ;

а(t), b(t) – вектор функции (столбцы );

A, B, D – постоянные матрицы.

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

Все функции заданы на [0; T], при этом a(t)=a(T), b(t)=b(T) при t>T;
r(t) >0 и непрерывная;
с(t) ³ 0 и непрерывная;
K_i (t _i ) >0 , производные Kґ_i (t _i ) £ 0 и непрерывные (i=1, 2, …, n)
a(t) – непрерывная;
b(t) – непрерывная справа, неотрицательная и неубывающая;
A, B, D ³ 0 и не имеют нулевых столбцов;

[0; T](i=1, 2, …, n).

Данная задача относится к классу нелинейных невыпуклых многоэкстримальных задач.

Исключаем из (2.1) вектор-функцию y(t). Рассмотрим функцию

(t,t )= [ c(t)y Ay(t) £ a(t) + D Q (t-t ), y ³ 0]. (2.2)

Функция (t,t ) — оптимальное значение целевой функции для задачи параметрического линейного программирования с параметрами t, t . В соответствии с леммой Минковского-Фаркаша, необходимым и достаточным условием существования неотрицательного вектора y, удовлетворяющего ограничениям в (2.2), является выполнение неравенства

u[a(t) + D Q (t-t )] ³ 0, (2.3)

для всех вектор-строк u, принадлежащих выпуклому многогранному конусу

U = { u uA ³ 0, u³ 0 }. (2.4)

Конус U не зависит от времени t. Поэтому, вводя образующие векторы конуса , N (конечное множество индексов образующих векторов), представляем (2.3) в эквивалентной форме:

a(t) + D Q (t-t ) ³ 0, N.

Определим следующие множества в пространстве векторов t :

⁰ = {t Bq (t-t ) £ b(t), t[0; T], t _i Î {[ D _i ,T ], +¥ }, i=1, 2, …, n,} (2.5)

¹= {t a(t) + D Q (t-t ) ³ 0, N, t[0; T] }.

Множество ⁰ включает в себя все векторы t , для которых удовлетворяются условия задачи (2.1), накладываемые только на t . Множество ¹ включает в себя все векторы t , для которых параметрическая задача линейного программирования (2.2) имеет решение при всех t[0; T]. Обозначим =⁰ ¹. Очевидно, что исходная задача (2.1) имеет решение тогда и только тогда, когда Æ . При этом, в силу положительности r(t) оптимальное решение определяется следующими формулами:

t * = arg [r(t) (t,t ) dt+ K (t ) Q (T-t ) t ] (2.6)

y*(t) = arg [ c(t)y Ay(t) £ a(t) + D Q (t-t *), y ³ 0], t[0; T] (2.7)

Таким образом, решение задачи (2.1) сводится к решению задачи нелинейного программирования (2.6) и решению задачи параметрического линейного программирования (2.7) с одним скалярным параметром t.

Для решения параметрической задачи имеется ряд разработанных численных методов [52, 53]. При этом потребуется аппроксимация вектор-функций c(t), a(t) кусочно-линейными.

Сложность решения нелинейной задачи (2.6) связана с ее невыпуклостью и многоэкстремальностью. Существует достаточное условие неразрешимости задачи (2.6):

Если существует t’[0;T], для которого задача линейного программирования

[ c(t’)y Ay £ a(t’) + De, y ³ 0] (2.8)

(e — единичный вектор)

не имеет решения, то задача (2.6) не имеет решения.

Рассмотрим задачу (2.6) подробнее:

r(t) (t,t ) dt+ K (t ) Q (T-t ) minпо t . (2.9)

Область допустимости имеет достаточно сложный вид и непосредственный анализ ее затруднителен. Разобьем это множество на отдельные подмножества, соответствующие добавлению в условия цепочки неравенств t _i¹ £ t _i^2£ …... £ t _iⁿ, где ={i¹, i², ... , iⁿ} — некоторая перестановка индексов i{1, 2, …, n }.

Обозначим

() = {t t , t _i^k £ t _i^k+1, k=1, 2, …, n-1 }.

Тогда

= (),

где – множество всех перестановок элементов {1, 2, …, n}.

Поставим в соответствие элементам i^k перестановки ={i¹, i², ... , iⁿ} следующие числа:

t ^k() = [ t b_{j i}l £ b_j(t), T t max _il,]. (2.10)

` t ^k() = [ t ( D)_il (t), t 0]. (2.11)

где

(t) = [-a(t’) 0 £ t’£ t ], N , t[0;T],

b_{j i}– элементы матрицы В.

Для динамической задачи размещения t ^k() является наиболее ранним моментом реализации проекта i^k, который обеспечен ресурсами, а ` t ^k() — наиболее поздний момент реализации этого проекта, к которому иссякают производственные мощности по какому-либо проекту или пропускные способности не позволяют получить необходимые потоки перевозок (при этом считаются реализованными проекты i¹, i², ... , i^k-1). Нахождение сводится к решению h одномерных задач минимизации (для каждого j). Будем считать, что функции b_j(t) таковы, что решение каждой задачи не вызывает затруднений (например, b_j(t) – кусочно-линейные).

Определение ` t ^k() эквивалентно поиску максимальной длительности интервала [0, t], для которого разрешима параметрическая задача линейного программирования

[ c(t’)y Ay £ a(t’) + D_il, y ³ 0], t’[0; t],

где D_il – i^l-й столбец матрицы D. При разрешимости этой задачи для всех t’[0; T] она разрешима для всех t’ ³ 0 (т.к. a(t’)= a(Т) при t’> T ) и следует положить ` t ^k()=+.

Для сформулированных правил определения ` t ^k() и t ^k() доказано утверждение, что выполняются следующие неравенства:

0 £ t ^k() £ t ^k+1(), k= 1, 2, …, n-1 (2.12)

0 £ ` t ^k() £ ` t ^k+1(), k= 1, 2, …, n-1 (2.13)

При этом, если задача (2.8) разрешима при любом t’ [0; Т], то множество () представимо в виде :

() = {t t _i^k £ t _i^k+1, (k= 1, 2, …, n-1) ;

t ^k() £ t _i^k £ ` t ^k(), t _i^k {[0;T], +} (k= 1, 2, …, n)} (2.14)

Из этих утверждений вытекает достаточное условие, что () = Æ , тогда и только тогда, когда существует такое k , при котором t ^k() >` t ^k().

Рассмотрим вместо задачи (2.9) задачу , отличающуюся от (2.9) тем, что множество допустимости заменено на ():

r(t) (t,t ) dt+ K (t ) Q (T-t ) min (2.15)

по t при

t _i^k £ t _i^k+1, (k= 1, 2, …, n-1) ;

t ^k() £ t _i^k £ ` t ^k(), t _i^k {[0;T], +} (k= 1, 2, …, n)

Пусть Ф*() оптимальное значение целевой функции в (2.15), а t *() – соответствующее оптимальное решение. При () = Æ будем считать Ф*()=+.

Из равенства = () следует, что при выполнении условий

разрешимости задачи (2.9), то ее решение сводится к решению всех задач при . При этом, если min Ф*()=+ (по ), то задача (2.9) не имеет решения.

7.2. Решение подзадачи нелинейного программирования

Полагаем, что

() ¹ Æ , т.е. t ^k() £ ` t ^k(), ( k = 1, 2, …, n ).

Обозначаем через I_k() – множество, содержащее начальные k элементов перестановки , т.е. I_k()={i¹, i², ... , i^k}. Введем в рассмотрение функцию

(2.21)

где, D_i — i-й столбец матрицы D.

При этом, если k=0, то под суммой по пустому множеству I₀() будем понимать нулевой вектор соответствующей размерности. По начальным предположениям с(t) и a(t) непрерывны, с(t)³ 0, поэтому P_k(t;p ) определена и непрерывна, если tÎ [ 0,` t _k+1(p )] (при t=` t _k+1(p ) — непрерывна справа). Определенность P_k(t;p ) в указанном интервале следует из выполнения условия разрешимости задачи линейного программирования и ограниченности целевой функции снизу (c(t)y³ 0). Непрерывность следует из теоремы о непрерывной зависимости оптимального значения целевой функции задачи линейного программирования от параметра.

Если t Î W (p ), то выполняется цепочка неравенств t _i¹ £ t _i^2£ …... £ t _iⁿ . Поэтому, используя (2.2) и (2.21), получаем

(2.22)

Введем в рассмотрение индексы

, (2.23)

Из (2.14) следует q(p )£ n (p ), так как W (p )¹ Æ . Если n(p )<n, то

(2.24)

если q(p )< n(p ), то

(2.25)

Вводя постоянную t ⁰_i=0 и используя (2.22), (2.24), (2.25), представим задачу Рp в следующем виде:

(2.26)

по при выполнении условий

Отметим, что по определению (2.23) t ^k_i = +¥ при k > n(p ) и поэтому такие t ^k_i не входят в (2.26).

Разделим множество допустимости в (2.26) на два непересекающихся подмножества:для первого – выполняется условие для второго — .

При этом для первого подмножества если поскольку значение +¥ при k<n(p ) запрещается конечным значением и неравенствами

Аналогичным образом разделим второе подмножество, выбирая в качестве индекса “переменной разделения” последний элемент в перестановке p , для которого значение переменной не фиксировано на +¥ , а область допустимости для нее содержит +¥ и т.д. Такое последовательное разбиение на подмножества заканчивается на “переменной разделения” . В результате множество допустимости в (2.26) разделяется на n(p )-q(p )+1 непересекающихся подмножеств и решение (2.26) сводится к решению n(p )-q(p )+1 задач следующего вида:

(2.27)

при

где значения параметра q последовательно принимают значения от q(p ) до n(p ) , ` t _k(p )=T (вместо +¥ ) при k= q(p )+1,¼ ,q. При этом остальные переменные (k= q+1, ¼ , n).

Решение задачи Рp вида (2.26) соответствует решению (2.27) при значении параметра

(2.28)

Рассмотрим задачу (2.27) при некотором значении параметра q. Удобно при выявлении локальных минимумов этой задачи рассматривать вместо (2.27) последовательность вспомогательных задач.

Первая вспомогательная задача формируется из (2.27) при отбрасывании неравенств Для нахождения ее решения следует вычислить частные производные целевой функции в (2.27) по t ^k_i , которые обозначим через :

(2.29)

и исследовать поведение каждой в соответствующем интервале .Отметим, что непрерывна в силу свойств функций Р_k(t;p ) и предположений о функциях K_i (t _i).

Решение сформированной вспомогательной задачи для переменной t ^k_i легко находится в следующих случаях:

³ 0 при t ^k_i Î , тогда ;
£ 0 при t ^k_i Î , тогда

При этом мы полагаем, что случай º 0 при t ^k_i Î не встречается, тогда - любое число из указанного интервала.

Если эти случаи не имеют места, то следует найти стационарные точки целевой функции для переменной t ^k_i в из уравнения

= 0 (2.30)

и выделить среди них точки локальных минимумов. Кроме того к точкам локальных минимумов следует отнести , если >0, и , если <0. Будем предполагать, что точки локальных минимумов по переменной t ^k_i образуют конечное множество . Среди найденных точек локальных минимумов вспомогательной задачи надо отобрать такие, для которых выполняются условия Если при этом пришлось отсеять некоторую последовательность локальных минимумов, так как , то следует рассмотреть другую вспомогательную задачу, добавив условие .

Таким образом можно найти решение задачи нелинейного программирования (2.6). Однако для этого требуется решить задачу для всех перестановок индексов переменных 1, 2, …, n. Число таких перестановок n! обычно велико, поэтому полный перебор нецелесообразен. Следует организовать ограниченный перебор с отсечением множества перестановок, используя схему последовательной декомпозиции. Применим эту схему для решения исходной задачи (2.6). С точки зрения последовательной декомпозиции, разделение исходной задачи на задачи () вида (2.15) представляет собой разделение на концевые задачи, так как для каждой задачи можно организовать процесс решения. Понятно, что такое конечное разделение не следует делать сразу.

В качестве задач, получающихся при разделении исходной задачи вида (2.6) будем рассматривать более широкий класс задач Р_S, где S = (i₁, i₂, ... , i_l ) представляет собой последовательность различных индексов переменных и символ S указывает на объединение всех перестановок , первые l элементов которых образуют последовательность S. Если S=Æ , то такой символ указывает на объединение всех перестановок , т.е. РÆ – исходная задача (2.6). Если l=n, то S – некоторая перестановка индексов переменных.

Задача Р_S имеет вид (при l ³ 1)

 T

Ф = r(t) (t,t ) dt+ K (t ) Q (T-t ) min(= Ф* (S)) (2.31)

по t при

t Î W ;

t _i¹ £ t _i² £ … £ t _i^l,^t_i^l £ t _i(iÏ { i¹ , i², …, i^l }.

Множество допустимостизадачи Р_S является объединением всех множеств допустимости W (p ) для перестановок p , первые l элементов которых образуют последовательность S.

Поэтому можно представить в следующем эквивалентном виде:

Ф = r(t) (t,t ) dt+ K (t ) Q (T-t ) min(= Ф* (S)) (2.31’)

по t Î W при

t _i^k Î [] Ç {[0, T], +¥ },k = 1, …, l,

t _i¹ £ t _i² £ … £ t _i^l,^t_i^l £ t _i(iÏ { i¹ , i², …, }).

Правило разделения задачи Р_S при l¹ n формулируется следующим образом: Р_S разделяется на n-l задач Р_{S°
i} , где iÏ { i¹ , i², …, i^l }, S° i =(i¹,i²,…,i^l,i).

При l = n-2 разделяется на две концевые задачи: Р_{(S°
i’)°
i’} и Р_{(S°
i’)°
‘i’} , где {i’,i’} = I\{i¹ , i², …, i^l}.

При разделении Р_S в соответствии (2.14) и следствием из него, можно выявить неразрешимость задачи Р_{(S°
i)} , если выполняется неравенство:

(2.32)

Такие задачи следует сразу отсеять, не помещая их в список задач.

Может оказаться, что все непосредственные потомки задачи Р_S неразрешимы. Тогда Р_S является концевой задачей, причем она тоже неразрешима и должна быть отсеяна из списка. Следует считать концевой и задачу Р_S, если (т.к. ее оптимальное решение находится прямым методом, описанным выше), а также если l=n.

Задача Р_S является полуконцевой, если. Ее допустимое решение можно найти, положив t _i =+¥ приiÏ { i¹ , i², …, i^l } и используя прямой метод решения.

Чтобы перейти к построению оценочной задачи для неконцевой задачи Р_S представим (2.31) как задачу с явным фигурированием нецелочисленной переменной y(t). Для этого в (2.1) добавим условия

t _i^k Î [] Ç {[0, T], +¥ },k = 1, …, l, (2.33)

t _i¹ £ t _i² £ … £ t _i^l,^t_i^l £ t _i(iÏ { i¹ , i², …, i^l }.

Если переписать в виде целочисленной динамической задачи оптимизации используя новые переменные, условия (2.33) принимают вид:

q [t-] £ x_i^k(t) £ q [t-],k = 1, …, l, (2.34)

x_i¹(t) ³ x_i²(t) ³ … ³ x_i^l(t)^,^x_i^l(t) ³ x_i(t)_(iÏ { i¹ , i², …, i^l }.

Тогда задача Р_S примет вид :

Ф=r(t) [y(t) c(t) dt — (t) x(t)/r(t)]+ K (T) x(T) Þ min(= Ф*)

по у(t), x(t)при (2.35)

Ay(t) £ a(t) + Dx (t), у(t) ³ 0 ,

Bx(t) £ b(t), x(t) £ Q [t-D ],

q [t-] £ x_i^k(t) £ q [t-],k = 1, …, l,

x_i¹(t) ³ x_i²(t) ³ … ³ x_i^l(t)^,^x_i^l(t) ³ x_i(t)_(iÏ { i¹ , i², …, i^l }.

x_i(t) Î {0, 1} неубывающаяi = 1, …, n.

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