Метод решения задачи линейного стохастического программирования с несовместными ограничениями

Исследования ученых в области оптимизации производства пилопродукции из пиловочных бревен показали, что объемный выход пиломатериалов из определенного места схемы продольного раскроя бревна является случайной величиной, которая подчиняется нормальному закону распределения [4]. Оценки случайной величины зависят от диаметра бревна, толщины пиломатериала и удаленности внешней пласти пиломатериала от сердцевины. Таким образом, задача оптимального раскроя круглого лесосырья (бревен) является задачей стохастического программирования, где коэффициенты перед переменными являются независимыми нормально распределенными случайными величинами. Как правило, ограничения задачи отражают необходимость выработки некоторого фиксированного объема пиломатериалов каждого сечения, целевая функция выражает цену объема потерь сырья.

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

f ( X ) = L C j X j ^ min

[ L AX j ^ B i , I e ^K '

. j                                            (1)

L AX s B I , i e K ■

K -n K'' = 0, |K 'I + K "| = m.

Более того, на данный момент не существует какого-либо общего подхода для решения задач стохастической линейной оптимизации в случае, когда система ограничений несовместна. Хорошо исследован только метод решения детерминированной задачи линейной оптимизации с несовместными ограничениями [3], на основе которого построен описанный ниже алгоритм.

В случае вероятностных ограничений речь идет о вероятности выполнения, то есть более универсальной оценке, но также возможно совмещение стохастических и детерминированных ограничений. Значения этих вероятностей можно задавать в зависимости от экономических последствий нарушения соответствующих неравенств [1]. Вероятностные условия модели записываются в виде (2):

P У AX B i >  P i ,0 <  p <  1, i g K '

V j

P У iX- B i >  P i ,0 < P i <  1, i g K"

A, ~ N(m,,av), где i - номер ограничения, A, - нормально распределенная случайная величина, Pi - вероятность выполнения соответствующего условия.

Под решением задачи (2) подразумевается вектор X >  0, который обеспечивает выполнение условий с заданными вероятностями. Задача раскроя пиловочного сырья сводится к задаче стохастического программирования с вероятностными ограничениями. Ее детерминированным эквивалентом является задача выпуклого программирования (3), содержащая два вида ограничений, образующих допустимое выпуклое множество:

программирования (3), основанный на неоднократном решении задачи линейного программирования. В качестве нулевого приближения возьмем решение задачи (3) при t i = 0, X ⁰ = ( X 1 ⁰ ,..., X g ) . Введем обозначения (4).

Y i ( X ) = У m ( A , ) X j , ^j

2л

^ (X)=.УИ A,) Xj) j

На ( K + 1)-й итерации работы алгоритма, K >  0, решается задача линейного программирования (5):

f ( X ) = У C j X j ^ min

j

' У m ( A , ) X j > B i + t i H i ( X^K ) , i g K ' ,

У m ( A , ) X j < B, - tH ( X^K ) , i g K '' . j

X , >  0.

Значение функции H i ( X ) зависит от выполнения следующих условий:

H , g k ' ( X ⁰ ) =

/ 0, Y i ( X ⁰) >  b + t i C i ( X ⁰) 1

tiai (X0), иначе f (X) = У (' X > min

j

У m(A)X, -t, ,У(^ аЛх, V > B,i g K' ijji ijji j Ъ___________           (3)

\2

Уm(A,)X,+ t У(СТ(Aij)X,)

I j                             j

X j > 0,

H i g K ' ( X K ) =

' H ( X K ^{- 1}), Y ( X K ) >  b + t a i ( X K )

max { H i ( X K ), t i a i ( X K ) } , иначе

; g k -( x ⁰ ) =

Hgk-(XK ) =

/ 0, Y ( X ⁰) <  b - t i a i ( X ⁰) 1

t i a i ( X ⁰), иначе

'H i (X^K \Y ( X^K ) < b i - t i S i (X^K )

max { H i ( X^K ), t i a i ( X^K ) } , иначе .

где t i - коэффициент доверительности, определяющий вероятность выполнения i -го ограничения задачи.

Коэффициент доверительности вычисляется как обратная функция от функции стандартного нормального распределения N (1, 0), ее значение находится по таблицам. Коэффициенты целевой функции детерминированы и зависят от средних значений случайных величин. Известные методы решения задачи (3) весьма сложны и трудоемки, особенно при большой размерности, поэтому некоторые исследователи разработали альтернативные итеративные способы вычисления, позволяющие эффективно решать подобного рода задачи. М. Я. Бравый и И. В. Соболев [1] предложили следующий метод решения задачи выпуклого

Здесь X^K - решение задачи (5) для K -й итерации алгоритма. Критерием сходимости задачи (3), а следовательно, и исходной задачи, является выполнение условия (7), где £ , - заданная точность для соответствующего ограничения.

I a(XK )-ai(XK-1)|

Для решения задачи линейной оптимизации в стохастической постановке достаточно нескольких итераций, включая получение начального решения; алгоритм сходится даже в случае несовместных ограничений [1]. Важность решения задачи линейной оптимизации в стохастической постановке заключается в устойчивости плана при случайном характере выхода производства, что влечет за собой сокращение корректировочных вычислений в случае нарушения плана.

В реальном производстве плановые выработки продукции достигаются, если позволяет запас времени и сырья. Если же идеальное соответствие фактической выработки плановой по каким-либо причинам невозможно, стараются выбрать такое решение, которое обеспечит наименьшее отклонение объема от плановых показателей по каждому ограничению. Таким образом, за критерий оптимизации в случае несовместных ограничений задачи (5) можно взять минимизацию невязок [3], то есть минимизацию суммы квадратов невязок (8). Выбор функции обусловлен возможностью отсутствия решения промежуточной задачи (5).

F = £ Bi-X m (Aj) Xj ie^K'(<       J

+ Y

+

'1 X m (A) Xj - Bi eK' V j

+ )2

^ min.

Набор ограничений остается прежним и линейным, задача попадает в категорию задач квадратичной оптимизации, ее решение осуществляется методом Франка – Вулфа [3]. Чтобы привести целевую функцию (8) к квадратичной, необходимо ввести в ограничения задачи (5) искусственные переменные pi > 0, 1 < i< m, в результате чего система примет вид (9). Она всегда имеет непустую область решений:

'X^m(Aj)Xj>Bi+ Pi,i e K'

X m (Aj) Xj< Bi- Pi, i e K".

. j

Для применения метода Франка – Вулфа необходимо выполнение свойства знакопеременности главных миноров гессиана целевой функции, что эквивалентно неравенству (10), которое однозначно выполняется только при Aj > 0 .

S²F axi axj

< 0.

Выражения под квадратами в (8) не что иное, как искусственные переменные. Выполнив замену, получим (11). Таким образом, задача

m

F=X Pi²^ min           (ii)

i=1

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

Подход для решения промежуточной задачи (5)

Рассмотрим алгоритм решения задачи стохастического программирования (4–7), состоящий из 8 шагов:

• 1.    Решение X задачи (5), в качестве значений

• 2.    Для каждого ограничения с индексом 1 < i< m вычисляются значения   Yi (X)

• 3.    Вычисляется максимум отклонений значений оi (X) от значений, полученных на предыдущей                   итерации:

• 4.    Алгоритм проверяется на сходимость путем проверки условия Ао < а, где а - заранее заданная точность вычисления;

• 5.    Для каждого ограничения c индексом 1 < i< m вычисляются значения функций и сохраняются полученные на текущем шаге значения Yi (X) и о, (X) в переменных Y^ и о'i соответственно;

• 6.    Вычисляются правые части линейных ограничений задачи (5);

• 7.    Полученная на шаге 6 детерминированная задача линейной оптимизации решается симплекс-методом;

• 8.    Выполняется переход на шаг 2.

Yi' = Yi и о'i = оi, где i - индекс ограничения задачи, принимаются очень большие положительные или отрицательные числа;

и оi (X) по формулам (4);

^А° = 1max {l°i^(X)^-о'i} ;

Проверка на существование решения может проходить только в пунктах 1 и 7. Как правило, за них отвечает один блок программного кода. Отсутствие решения стохастической задачи линейной оптимизации эквивалентно отсутствию решения соответствующей детерминированной задачи линейной оптимизации на некоторой итерации вышеприведенного алгоритма. Но не исключен такой вариант, когда часть генерируемых на этапах 5–6 детерминированных задач линейной оптимизации могут иметь решения, а часть может их не иметь. Также важно заметить, что на этапах 2–5 не требуется информация о полном перечне возможных раскроев сырья, вся необходимая информация генерируется в блоках 1 и 7. Для предотвращения остановки решения при несовместных условиях необходимо заменить пункты 1 и 7 на ветку алгоритма, приведенную на рисунке, где ЗСО – задача стохастической оптимизации, ЗМН – задача минимизации невязок.

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

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

• •    ограничения промежуточных задач (9) совместны;

• •    ограничения промежуточных задач (9) на разных итерациях могут быть как совместны, так и несовместны;

• •    ограничения промежуточных задач (9) несовместны;

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

• 1.    Сумма квадратов значений невязок;

• 2.    Значение целевой функции.

Для задач с несовместными ограничениями среднее значение первого показателя было на 16,4 % меньше аналогичного показателя для задачи, где в качестве случайных коэффициентов были использованы их математические ожидания. Для задач с совместными ограничениями среднее значение второго показателя было ниже на 18,9 % при аналогичных условиях. Отрицательной стороной алгоритма является высокая трудоемко сть решения: для задачи с 15–30 ограничениями время ее решения на ЭВМ с одноядерным процессором частотой 1ГГц в среднем составило 55 секунд, в то время как решение детерминированной задачи линейной оптимизации с несовместными ограничениями с таким же количеством ограничений находится за 8–10 секунд.

ЗАКЛЮЧЕНИЕ

Подход для поиска решения детерминированной задачи линейной оптимизации с несовместными ограничениями был известен давно и успешно применялся для решения промышленных задач [3]. Что касается поиска решения стохастической задачи линейной оптимизации с указанными свойствами случайных коэффициентов с несовместными ограничениями, то общего метода с доказанной схо-димо стью в литературе в явном виде не встречается, за исключением случаев, когда рассматриваются задачи узко специализированного класса.