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

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

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

3.1

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

3.2

где

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

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

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

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

Решение. Ее модель:

где a i j , bi , cj — случайные.

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

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

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

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

Таблица 3.3

Величина	С	d	D
X1	5	2	6
X2	8	3	9

Таблица 3.4

Ограничения	Случайные величины
	ai1		ai2		bi
1	10	2	15	3	100	9
2	20	6	14	4	150	12

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

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

Таблица 3.5

Величина	ζ i = 0	a i = 0,6	Величина	ζ i = 0	a i = 0,6
x1	2	2	ζ1	0	4,4
x2	5,3	5,04	ζ2	0	5,8
L	52,4	50,3	γ1	0	4,4
β	0	4	γ2	0	5,1

Таблица 3.6

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

Рассмотрим теперь, как повлияют на результат решения задачи величины, определяющие ее вероятностный характер. К таким величинам относят заданный уровень вероятности ai, и дисперсий σij2 и θi2. Начнем с анализа влияния ai (табл. 3.6).

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

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

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

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

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

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

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

Заключение

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

Список литературы

1. « Математические методы в программировании » : / Агальцов В.П., Волдайская И.В. Учебник : – М . : ИД «ФОРУМ» : ИНФРА-М, 2006. – 224с. : ил. –(Профессиональное образование). – (Учимся программировать).

2. Лекции по дисциплине « Математические методы ».

3. «Математические методы: Учебник» / Партика Т.Л., Попов И.И. – М: ФОРУМ: ИНФРА, 2005.

4.Интернет сайт: http://ru.wikipedia.org/wiki/

5.«Математическое программирование» / Костевич Л., издательство «Новое знание», 2003.