Реферат: Задача о распределении средств между предприятиями

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

АЛТАЙСКИЙ ПРОМЫШЛЕННО-ЭКОНОМИЧЕСКИИ КОЛЛЕДЖ

Специальность программное обеспечение вычислительной техники и
автоматизированных систем

Группа 11По071

КУРСОВАЯ РАБОТА

На тему

Задача о распределении средств между предприятиями

Студент:

Консультанты: Любицкая О.Н, Захарова О.А

“__” Мая 2009г.

БАРНАУЛ
Оглавление

Введение. 3

Сущность математического метода… 5

1.1 Характеристика математического метода, применимого для решения задачи 5

1.2 Аналитическое решение задачи… 11

Решение задачи в среде визуального программирования Delphi15

2.1 Анализ процесса обработки информации и выбор структур данных для ее хранения… 15

2.2 Разработка основных алгоритмов решения задачи… 17

2.3 Построение графа состояний интерфейса… 19

2.3 Разработка форм ввода-вывода информации… 20

2.5 Контрольный пример. 23

Заключение. 30

Список использованных источников… 32

ПриложениеА… 33

Введение

Тема курсовой работы: задача о распределении средств между предприятиями.

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

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

Из всего вышесказанного легко понять актуальность данной темы в современном мире, особенно во времена мирового экономического кризиса, когда нужен четкий план развития предприятий и жесткий контроль за выполнением найденного оптимального плана распределения средств между предприятиями.

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

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

7 на языке программирования ObjectPascal(Delphi начиная с Delphi 7). А также закрепление материала по дисциплине «Математические методы» и закрепление полученных навыков программирования в среде программирования Delphi.

Разработанный программный продукт является эргономичным, что позволит использовать его даже на малопроизводительных персональных компьютерах. Так же интерфейс программного продукта является интуитивным, гармоничным и привлекательным, благодаря этому им может пользоваться даже начинающий пользователь. Ещё одой особенностью данного программного продукта является высокое быстродействие. Так же в программе имеется множество подсказок, которые позволят пользователю с легкостью пользоваться программным продуктом и легко его освоить.

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

Сущность математического метода1.1 Характеристика математического метода, применимого для решения
задачи

Данный математический метод изложен во многих литературных источниках, но наиболее подробно он описан в учебном материале “Математическое программирование в примерах и задачах” автор И.Л. Акулич. Весь дальнейший материал взят из указанного источника.

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

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

Ставится вопрос: как распределять имеющиеся средства между предприятиями, чтобы суммарный доход от всех предприятий был максимальным?

Перед нами типичная задача динамического программирования, в которой рассматривается управляемый процесс – функционирование группы предприятий. Управление процессом состоит в распределении (и перераспределении) средств. Управляющим воздействием (УВ) является выделение каких-то средств каждому из предприятий в начале года.

УВ на каждом шаге должно выбираться с учетом всех его последствий в дальнейшем. УВ должно быть дальновидным, с учетом перспективы. Нет смысла выбирать на рассматриваемом шаге наилучшее УВ, если в дальнейшем это помешает получить наилучшие результаты других шагов. УВ на каждом шаге надо выбирать “c

заглядыванием в будущее”, иначе возможны серьезные ошибки.

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

В формализме решения задач методом динамического программирования будут использоваться следующие обозначения:

N

– число шагов.

/>

– вектор, описывающий состояние системы на k-м шаге.

/>

– начальное состояние, т. е. состояние на 1-м шаге.

/>

– конечное состояние, т. е. состояние на последнем шаге.

Xk

– область допустимых состояний на k-ом шаге.

/>

– вектор УВ на k-ом шаге, обеспечивающий переход системы из состояния xk-1 в состояние xk.

Uk – область допустимых УВ на

k-ом шаге.

Wk

– величина выигрыша, полученного в результате реализации k-го шага.

S

– общий выигрыш за Nшагов.

/>– вектор оптимальной стратегии управления или ОУВ за

Nшагов.

Sk

+1(/>) – максимальный выигрыш, получаемый при переходе из любого состояния />/>в конечное состояние /> при оптимальной стратегии управления начиная с (k+1)-го шага.

S

1(/>) – максимальный выигрыш, получаемый за Nшагов при переходе системы из начального состояния /> в конечное /> при реализации оптимальной стратегии управления />. Очевидно, что S = S1(/>), если /> – фиксировано.

Метод динамического программирования опирается на условие отсутствия последействия и условие аддитивности целевой функции.

Условие отсутствия последействия. Состояние />, в которое перешла система за один k

-й шаг, зависит от состояния /> и выбранного УВ /> и не зависит от того, каким образом система пришла в состояние />, то есть

/>

Аналогично, величина выигрыша Wk

зависит от состояния /> и выбранного УВ />, то есть

/>

Условие аддитивности целевой функции.Общий выигрыш за N

шагов вычисляется по формуле

Определение. Оптимальной стратегией управления /> называется совокупность УВ />, то есть

/>, в результате реализации которых система за Nшагов переходит из начального состояния /> в конечное /> и при этом общий выигрыш S принимает наибольшее значение.

Условие отсутствия последствий позволяет сформулировать принцип оптимальности Беллмана.

Принцип оптимальности. Каково бы ни было допустимое состояние системы/>/>/>
перед очередным i

-м шагом, надо выбрать допустимое УВ /> на этом шаге так, чтобы выигрыш Wi на i-м шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным.

В качестве примера постановки задачи оптимального управления продолжим рассмотрение задачи управления финансированием группы предприятий. Пусть группе предприятий />

выделяются соответственно средства: />/>совокупность этих значений можно считать управлением на i-м шаге, то есть />. Управление /> процессом в целом представляет собой совокупность всех шаговых управлений, то есть />.

Управление может быть хорошим или плохим, эффективным или неэффективным. Эффективность управления />

оценивается показателем S. Возникает вопрос: как выбрать шаговые управления />, чтобы величина S обратилась в максимум?

Поставленная задача является задачей оптимального управления, а управление, при котором показатель S

достигает максимума, называется оптимальным. Оптимальное управление /> многошаговым процессом состоит из совокупности оптимальных шаговых управлений:

/>

Таким образом, перед нами стоит задача: определить оптимальное управление на каждом шаге />(i=1,2,...N) и, значит, оптимальное управление всем процессом />.

Мы отметили, что планируя многошаговый процесс, необходимо выбирать УВ на каждом шаге с учетом его дальнейших последствий на еще предстоящих шагах. Однако, из этого правила есть исключение. Среди всех шагов существует один, который может планироваться без «заглядывания в будущее». Какой это шаг? Очевидно, последний — после него других шагов нет. Этот шаг, единственный из всех, можно планировать так, чтобы он как таковой принес наибольшую выгоду. Спланировав оптимально этот последний шаг, можно к нему пристраивать предпоследний, к предпоследнему — предпредпоследний и т.д.

Поэтому процесс динамического программирования на 1-м этапе разворачивается от конца к началу, то есть раньше всех планируется последний, N-й шаг. А как его спланировать, если мы не знаем, чем кончился предпоследний? Очевидно, нужно сделать все возможные предположения о том, чем кончился предпоследний, (N — 1)-й шаг, и для каждого из них найти такое управление, при котором выигрыш (доход) на последнем шаге был бы максимален. Решив эту задачу, мы найдем условно оптимальное управление (УОУ) на N-м шаге, т.е. управление, которое надо применить, если (N — 1)-й шаг закончился определенным образом.

Предположим, что эта процедура выполнена, то есть для каждого исхода (N — 1)-го шага мы знаем УОУ на N-м шаге и соответствующий ему условно оптимальный выигрыш (УОВ). Теперь мы можем оптимизировать управление на предпоследнем, (N — 1)-м шаге. Сделаем все возможные предположения о том, чем кончился предпредпоследний, то есть (N — 2)-й шаг, и для каждого из этих предположений найдем такое управление на (N — 1)-м шаге, чтобы выигрыш за последние два шага (из которых последний уже оптимизирован) был максимален. Далее оптимизируется управление на (N — 2)-м шаге, и т.д.

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

Теперь предположим, что УОУ на каждом шаге нам известно: мы знаем, что делать дальше, в каком бы состоянии ни был процесс к началу каждого шага. Тогда мы можем найти уже не «условное», а действительно оптимальное управление на каждом шаге.

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

Таким образом, в процессе оптимизации управления методом динамического программирования многошаговый процесс «проходится» дважды: первый раз — от конца к началу, в результате чего находятся УОУ на каждом шаге и оптимальный выигрыш (тоже условный) на всех шагах, начиная с данного и до конца процесса; второй раз — от начала к концу, в результате чего находятся оптимальные управления на всех шагах процесса.

Можно сказать, что процедура построения оптимального управления методом динамического программирования распадается на две стадии: предварительную и окончательную. На предварительной стадии для каждого шага определяется УОУ зависящее от состояния системы (достигнутого в результате предыдущих шагов), и условно оптимальный выигрыш на всех оставшихся шагах, начиная с данного, также зависящий от состояния. На окончательной стадии определяется (безусловное) оптимальное управление для каждого шага. Предварительная (условная) оптимизация производится по шагам в обратном порядке: от последнего шага к первому; окончательная (безусловная) оптимизация — также по шагам, но в естественном порядке: от первого шага к последнему. Из двух стадий оптимизации несравненно более важной и трудоемкой является первая. После окончания первой стадии выполнение второй трудности не представляет: остается только «прочесть» рекомендации, уже заготовленные на первой стадии.

1.2 Аналитическое решение задачи

Рассмотрим задачу, когда инвестор выделяет средства в размере 5 условных единиц, которые должны быть распределены между тремя предприятиями.

Требуется, используя принцип оптимальности Беллмана, построить план распределения инвестиций между предприятиями, обеспечивающий наибольшую общую прибыль, если каждое предприятие при инвестировании в него средств X

у.е. приносит прибыль Pi (x) у.е. (i = l, 2 и 3) последующим данным, приведённым в таблице 1.

Таблица 1 – Исходные данные.

Инвестируемые средства (у.е.)

Общая прибыль (у.е.)

P1(x)

P2(x)

P3(x)

3,22

3,33

4,27

<span style=«font-size: 12