Решение задачи распределения капиталовложений

Министерство  образования РФ

Южный Федеральный университет

Факультет математики, механики и компьютерных наук

Кафедра Исследования операций 
 
 

Курсовая  работа на тему:

«Решение задачи распределения капиталовложений» 
 
 

Выполнил  студент 4к 6гр

Семенюк Игорь

Научный руководитель:

Землянухина Л.Д. 
 

Ростов-на-Дону, 2010г

Содержание

1. Введение……………………………………………………………………………3
2. DCP-модель задачи распределения капиталовложений………………………...5
3. Алгоритм решения задачи………………………………………………………...7
4. Реализация алгоритма ……………………………………………………………..10
5. Пример……………………………………………………………………………....12
6. Литература…………………………………………………………………………..13
7. Приложение…………………………………………………………………………14

 
 
 
 
 
 
 
 
 
 
 
 
 

Введение

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

Теория событийного  программирования отказывается от понятия «допустимое множество» и заменяет его понятием «неопределенная среда». Упрощенно говоря, DCP-модель связана с максимизацией функции шансов событий в неопределенной среде. Детерминированная модель, модель ожидаемых значений и модель программирования с ограничениями на шансы существенно основываются на предположении о том, что допустимая область после завершения моделирования становится детерминированной, т.е. в этих моделях неопределенность связана с тем, что заранее неизвестно, какие значения примут неопределенные функции, входящие в описание области допустимых решений. После того, как в ходе имитационного моделирования получены реализации этих функций, данная неопределенность устраняется и область допустимых решений становится детерминированной. Это значит, что оптимальное решение предполагается существующим независимого от того, может ли оно быть практически реализовано. Может оказаться так, однако, что решения реализовать невозможно, поскольку требуемое значение неопределенного параметра по каким-либо причинам является неблагоприятным. В силу этого в теории событийного программирования нигде не используется предположение о детерминированности допустимого множества решений, взамен введено понятие неопределенной среды. Эта специфическая особенность событийного программирования значительно отличает его от других направлений стохастического программирования. Реальный мир дает достаточное число примеров задач, отвечающих идее событийного программирования.

Для решения  задач, описываемых DCP-моделями, формируется разновидность гибридного алгоритма, объединяющего средства статического моделирования с нейронной сетью и генетическим алгоритмом.

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

Из принципа неопределенности следует, что можно  построить зависимость между  векторами решений и вероятностными функциями событий, вычисляя вероятностные  функции с помощью метода статистического  моделирования или традиционными  методами. Если лицом, принимающим решения, задана полная информация о функции  предпочтения, то теперь можно решать многокритериальную событийную задачу, используя методы теории полезности. При отсутствии такой информации производится поиск всех эффективных решений. На практике лицо, принимающее решения, может дать только частичную информацию. В этом случае следует применять интерактивные методы.

Целевое событийное программирование может рассматриваться  как расширение целевого программирования в сложных стохастических системах принятия решений. Когда заданы некоторые  назначаемые цели, целевая функция  может минимизировать положительное  или отрицательное отклонение от цели или и то и другое вместе с определенной структурой приоритетов, заданных лицом, принимающим решения. Тогда можно сформулировать стохастическую систему принятия решений как следующую целевую DCP-модель:

где P_j – коэффициент преимущественного приоритета, – весовой коэффициент, соответствующий положительному отклонению от i-ой цели с присвоенной ему j-ым приоритетом, – весовой коэффициент, соответствующий отрицательному отклонению. - положительное отклонение от назначенного уровня i-ой цели, - отрицательное отклонение, – назначенный уровень i-ой цели, l – число приоритетов и m – число целевых ограничений.

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

DCP-модель задачи распределения капиталовложений

Предположим, что  имеется n типов машин, производящих n различных видов продукции. Случайные величины, соответствующие производственным мощностям этих n типов машин, предполагаются распределенными по логнормальному закону. Принимается так же, что спрос на указанные n видов продукции, представлен в виде случайных величин, распределенных по экспоненциальному закону.

Уровни затрат, необходимые для приобретения машин i-ого типа, составляют , а суммарный объем средств, выделяемый для покупки машин, равен α. Кроме того, площади, требуемые для размещения машин i-ого типа, принимаются равными , а общая доступная площадь составляет b.

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

Затем ограничение  на предельную стоимость закупки: 

В соответствии с первым уровнем приоритета, уровень  вероятности удовлетворения потребности  ε1 должен достигать p1, т.е. 

где должно быть минимизированно.

Согласно второму  уровню приоритета, вероятность удовлетворения потребности ε2 должна достигать  p2, т.е. 

где должно быть минимизированно.

И так далее. В общем виде мы можем записать это так: 

Где m это количество ограничений задачи, а уровень приоритета удовлетворения ограничений уменьшается с ростом i.

В соответствии с приведенной выше структурой приоритетов  и целевыми уровнями можно сформулировать следующую целевую DCP – модель: 

Алгоритм  решения

Для решения  задач, основанных на DCP-моделях имеем  гибридный алгоритм, основанный на объединении средств статического моделирования и генетического алгоритма.

1. Сформировать обучающий набор вход-выходных данных с помощью статистического моделирования для неопределенных функций вида:

 

Для этого:

• положить =0;
• получить u в соответствии с функцией распределения;
• если для i=1,..,m тогда увеличить на единицу;
• повторить второй и третий шаги N раз
• вычислить и выдать результат:

2. Инициализировать pop_size хромосом для генетического алгоритма с помощью статического моделирования (пункт 1):

Для этого  потребуется определить размер популяции (от 10 до 100 в зависимости от сложности задачи). Здесь в качестве хромосомы принимается вектор решений исходной задачи. Затем случайным образом генерировать хромосомы так, чтобы они удовлетворяли условиям нашей задачи (ограничениям на площадь и затраты).

3. Модифицировать хромосомы с помощью операций кроссинговера и мутации.

Это выглядит следующим образом:

     Модификация кроссинговером:

• Определяем параметр как вероятность этой модификации;
• Выявить родительские хромосомы. Для этого формируем случайное число r  из  (0,1), и если , то данная хромосома выбирается как родительская. Процедуру повторяем pop_size раз для каждой хромосомы;
• В итоге имеем m родительских хромосом, если m нечетное, то m=m-1. И разбиваем их на пары: ;
• Затем для каждой пары формируется случайное число с из (0,1), и оператор кроссинговера действует следующим образом на родительскую пару: , где X и Y – потомки, которые заменят своих родителей, если будут удовлетворять условиям задачи (если допустимое множество выпуклое, то это будет выполнено однозначно)

Модификация мутацией:

• Определяем параметр как вероятность этой модификации;
• Как и в процессе отбора родительских хромосом для кроссинговера, выбираем родителей для мутации;
• Мутация производится следующим образом: пусть M – некоторое положительное число, выбираем направление мутации случайным образом. Далее модифицируем хромосому , где X – потомок. Если он удовлетворяет условию задачи, тогда проводится замена предка потомком, если же нет, то M выбирается случайным образом из (0,M), и операция повторяется, пока не будет достигнута допустимость

4. Вычислить целевые функции для всех хромосом с помощью статистического моделирования. Т.е зная нашу популяцию хромосом (вектор решений) мы можем вычислить значение каждого из отрицательных отклонений в нашем условии и проверить на допустимость ограничений.

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

• Для этого мы должны расположить хромосомы начиная с наилучшей, зная значение lexmin(отрицательных отклонений), полученное на предыдущем шаге.
• Приспособленность каждой хромосомы вычисляется с помощью функции оценки, основанной на ранжировании;
• Каждой хромосоме ставим в соответствии значение функции:

 

6. Произвести  селекцию хромосом, использую случайный выбор:

• Вычислить кумулятивную вероятность для каждой хромосомы :
 

• Сформировать  случайное число r в интервале
• Выбрать i-ую хромосому так, чтобы
• Повторить 2 и 3 шаги pop_size раз и получить pop_size экземпляров хромосом

7. Повторить шаги с 3 по 6 для заданного числа циклов.

8. Выбрать наилучшую хромосому как оптимальное решение.

Реализация  алгоритма

Статистическое  моделирование

1. Repeat                                                //Внешний цикл
2. for i:=1 to n do
3.      x[i]:=round(random);            //Заполнение вектора решений
4. if odz(x) then                                  //Если удовлетворяет условию, то
5.      for i:=1 to m do                           //m-количество вероятностных ограничений
6.           N1:=0;
7.    for k:=1 to max_st_m do       //max_st_m – количество циклов стат.модел.
8.          if LogN(a,b)*x>=Expa(c) then N1:=N1+1;  //a,b,c-коэф. распределения
9.    Pr[i]:=N1/max_st_m;            //Вычисления значения вероятности
10. until odz(x);                                    //пока вектор решений не удовлетворит одз