Решение задач СТП

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

Обозначим

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

где

.

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

Функция F (x ₁, x ₂,..., x_n) называется сепарабильной, если она может быть представлена в виде суммы функций, каждая из которых является функцией одной переменной, то есть если

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

Пример 8.2

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

Решение.

Ее модель:

max L = c 1 x 1 + c 2 x 2;

a 11 x 1 + a 12 x 2 £ b 1;

a 21 x 1 + a 22 x 2 £ b 2;

d 1 £ x 1 £ D 1;

d 2 £ x 2 £ D 2,

где a_ij, b_i, c_j – случайные.

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

max L = M [ c 1 x 1 + c 2 x 2];

P (a 11 x 1 + a 12 x 2 £ b 1) ³ a1;

P (a 21 x 1 + a 22 x 2 £ b 2) ³ a2;

d 1 £ x 1 £ D 1;

d 2 £ x 2 £ D 2,

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

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

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

Таблица 8.4

Величина	c	d	D
x 1
x 2

Таблица 8.5

Ограничения	Случайные величины
ai 1	ai 2	bi
	s i 1		s i 2		q i

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

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

Таблица 8.6

Величина	x i = 0	a i = 0,6
x 1
x 2	5,3	5,04
L	52,4	50,3
b
x1		4,4
x2		5,8
g1		4,4
g2		5,1

Рассмотрим теперь, как повлияют на результат решения задачи величины, определяющие ее вероятностный характер. К таким величинам относят: заданный уровень вероятности a _i и дисперсий s _ij ² и q _i ². Начнем с анализа влияния a _i (табл. 9.7).

Таблица 8.7

Величина	a1,2
0,5	0,6	0,77	0,89	0,96	0,987
x 1 x 2 L b g1 g2	5,3 52,4	5,04 50,3 4,4 5,1	4,51 46,1 12,3 14,8	3,71 42,6 18,7 17,9 16,5	3,07 39,3 24,3 23,2	2,165 34,8 33,6 33,3

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

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

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

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

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

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

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