Лекция: Решение задач СТП

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

Обозначим

тогда задачу стохастического программирования можно записать в сепарабильной форме:

где

.

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

Функция F(x1, x2,…, xn) называется сепарабильной, если она может быть представлена в виде суммы функций, каждая из которых является функцией одной переменной, то есть если

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

Пример 8.2

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

Решение.

Ее модель:

max L = c1x1 + c2x2;

a11x1 + a12x2 £ b1;

a21x1 + a22x2 £ b2;

d1 £ x1 £ D1;

d2 £ x2 £ D2,

где aij, bi, cj – случайные.

При М–постановке модель запишется:

max L = M [c1x1 + c2x2];

P(a11x1 + a12x2 £ b1) ³ a1;

P(a21x1 + a22x2 £ b2) ³ a2;

d1 £ x1 £ D1;

d2 £ x2 £ D2,

a1, a2 – заданные уровни вероятности соблюдения каждого ограничения.

Для того, чтобы решить задачу в М–постановке необходимо перейти к ее детерминированному эквиваленту:

Исходные данные, необходимые для решения этой задачи, сведены в табл. 9.4 и 9.5.

Таблица 8.4

Таблица 8.5

Если задать уровни вероятности a1,2 = 0,6, для которых ta = 0,25, то получим после подстановки исходных данных детерминированный эквивалент:

Результаты решения этой задачи для детерминированного случая xi = 0 и при ai = 0,6 (табл. 9.6), где

Таблица 8.6

Рассмотрим теперь, как повлияют на результат решения задачи величины, определяющие ее вероятностный характер. К таким величинам относят: заданный уровень вероятности ai и дисперсий sij2 и qi2. Начнем с анализа влияния ai (табл. 9.7).

Таблица 8.7

Из анализа этой решения этой задачи можно сделать следующие выводы: для обеспечения гарантированного (с вероятностью a = 0,6) выполнения плана необходимо иметь дополнительно около 5% каждого вида ресурса. При отсутствии дополнительного ресурса целевой функции может уменьшиться на величину b = 4% вследствие возможного сокращения выпуска продукции x2 от 5,3 до 5,04.

Этот пример подтверждает тот факт, что в реальных условиях для гарантированного выполнения плана необходимы дополнительные ресурсы в размере xi. В противном случае возможно уменьшение выпуска продукции.

При этом можно сделать выводы:

В целях повышения заданного уровня вероятности выполнения плана ai требуется увеличить дополнительные ресурсы gi. Так, для выполнения плана с вероятностью близкой к 1 (a = 0,987), необходим дополнительный ресурс в размере g = 26...33% от величины используемого без учета вероятностных характеристик.

Отсутствие такого увеличения может привести к ухудшению целевой функции на величину b = 33,6%.

Возрастание a отражается на номенклатуре продукции. При этом в интервале a = 0,5...0,77 значение x1 сохраняется неизменным, а x2 – уменьшается. При дальнейшем увеличении a = 0,89...0,987 значение x2 = const, в то время как x1 сначала скачком растет, а затем постепенно уменьшается. Несмотря на то, что при a = 0,89 значения x1, x2 резко изменяются, целевая функция во всем интервале изменения a уменьшается плавно. Таково влияние заданного уровня вероятности соблюдения ограничений a на результат решения задачи.

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