Решение задачи распределения капиталовложений (стр. 1 из 3)
Министерство образования РФ
Южный Федеральный университет
Факультет математики, механики и компьютерных наук
Кафедра Исследования операций
Курсовая работа на тему:
«Решение задачи распределения капиталовложений»
Выполнил студент 4к 6гр
Семенюк Игорь
Научный руководитель:
Землянухина Л.Д.
Ростов-на-Дону, 2010г
Содержание
1. Введение……………………………………………………………………………3
2. DCP-модель задачи распределения капиталовложений………………………...5
3. Алгоритм решения задачи………………………………………………………...7
4. Реализация алгоритма ……………………………………………………………..10
5. Пример……………………………………………………………………………....12
6. Литература…………………………………………………………………………..13
7. Приложение…………………………………………………………………………14
Введение
В реальных системах принятия решений, действующих в сложной стохастической обстановке, приходится иметь дело с многочисленными событиями. В ряде случаев лицу, принимающему решение, требуется максимизировать вероятностные функции этих событий. Для моделирования стохастических систем принятия решений такого типа предложено новое направление в стохастическом программировании, получившее наименование «стохастическое событийное программирование» (depended-chanceprogramming - DCP). Основная идея данного направления состоит в выборе решения с максимальной вероятностью наступления требуемого события.
Теория событийного программирования отказывается от понятия «допустимое множество» и заменяет его понятием «неопределенная среда». Упрощенно говоря, DCP-модель связана с максимизацией функции шансов событий в неопределенной среде. Детерминированная модель, модель ожидаемых значений и модель программирования с ограничениями на шансы существенно основываются на предположении о том, что допустимая область после завершения моделирования становится детерминированной, т.е. в этих моделях неопределенность связана с тем, что заранее неизвестно, какие значения примут неопределенные функции, входящие в описание области допустимых решений. После того, как в ходе имитационного моделирования получены реализации этих функций, данная неопределенность устраняется и область допустимых решений становится детерминированной. Это значит, что оптимальное решение предполагается существующим независимого от того, может ли оно быть практически реализовано. Может оказаться так, однако, что решения реализовать невозможно, поскольку требуемое значение неопределенного параметра по каким-либо причинам является неблагоприятным. В силу этого в теории событийного программирования нигде не используется предположение о детерминированности допустимого множества решений, взамен введено понятие неопределенной среды. Эта специфическая особенность событийного программирования значительно отличает его от других направлений стохастического программирования. Реальный мир дает достаточное число примеров задач, отвечающих идее событийного программирования.
Для решения задач, описываемых DCP-моделями, формируется разновидность гибридного алгоритма, объединяющего средства статического моделирования с нейронной сетью и генетическим алгоритмом.
Поскольку сложная система принятия решений обычно имеет дело с многочисленными событиями, будет иметь место, несомненно, и случай нескольких потенциально возможных целевых функций (некоторые из них будут вероятностными функциями), вовлеченных в процесс решения. Типичную формулировку задачи многокритериального событийного программирования, можно представить как задачу максимизации нескольких вероятностных функций с учетом неопределенной среды:
Из принципа неопределенности следует, что можно построить зависимость между векторами решений и вероятностными функциями событий, вычисляя вероятностные функции с помощью метода статистического моделирования или традиционными методами. Если лицом, принимающим решения, задана полная информация о функции предпочтения, то теперь можно решать многокритериальную событийную задачу, используя методы теории полезности. При отсутствии такой информации производится поиск всех эффективных решений. На практике лицо, принимающее решения, может дать только частичную информацию. В этом случае следует применять интерактивные методы.
Целевое событийное программирование может рассматриваться как расширение целевого программирования в сложных стохастических системах принятия решений. Когда заданы некоторые назначаемые цели, целевая функция может минимизировать положительное или отрицательное отклонение от цели или и то и другое вместе с определенной структурой приоритетов, заданных лицом, принимающим решения. Тогда можно сформулировать стохастическую систему принятия решений как следующую целевую DCP-модель:
где Pj – коэффициент преимущественного приоритета,
– весовой коэффициент, соответствующий положительному отклонению от 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 в зависимости от сложности задачи). Здесь в качестве хромосомы принимается вектор решений исходной задачи. Затем случайным образом генерировать хромосомы так, чтобы они удовлетворяли условиям нашей задачи (ограничениям на площадь и затраты).