Задача о распределении капиталовложений

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

Северный (Арктический) федеральный университет

Информационных технологий

(наименование кафедры)

Забродин Алексей Александрович

(фамилия, имя, отчество студента)

КТИТ

курс

4

группа

2381

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

По дисциплине

Математические методы

На тему

Задача о распределении капиталовложений

(наименование темы)

Работа допущена к защите

(подпись руководителя)

Признать, что работа

выполнена и защищена с оценкой

Руководитель

(должность)

(подпись)

(дата)

Архангельск - 2011

 

ЛИСТ ЗАМЕЧАНИЙ

 

ОГЛАВЛЕНИЕ

1 ПОСТАНОВКА ЗАДАЧИ	4
2 ОПИСАНИЕ ИСПОЛЬЗУЕМЫХ АЛГОРИТМОВ	6
3 ОПИСАНИЕ ПРОГРАММЫ	10
4 ТЕСТИРОВАНИЕ ПРОГРАММЫ	13
ЗАКЛЮЧЕНИЕ	16
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ	17
ПРИЛОЖЕНИЕ А – Листинг основных компонентов	18

 

 

 

 

 

 

1 ПОСТАНОВКА  ЗАДАЧИ

 

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

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

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

 

Таблица 1 –  Пример значений целевой функции для управлений

Ui	Z1(Ui)	Z2(Ui)	Z3(Ui)	Z4(Ui)	Z5(Ui)
0	0	0	0	0	0
30	23	21	80	23	80
60	71	12	78	73	21
90	23	23	78	78	78
120	76	23	87	34	23
150	34	23	53	23	23

 

Таблица 2 –  Пример других исходных данных

Количество предприятий	5
Распределяемая сумма	150
Кратность суммы	5

 

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

 

 

 

 

 

 

2 ОПИСАНИЕ  ИСПОЛЬЗУЕМЫХ АЛГОРИТМОВ

 

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

В общей постановке задача динамического программирования формулируется следующим образом. Имеется некоторая управляемая  физическая система S, характеризующаяся определенным набором параметров. В этой системе происходят какие-то процессы (экономические, производственные, технологические и т. п.), которые можно представить как многошаговые. На каждом шаге процессам в системе соответствуют определенные значения параметров, описывающих состояние системы. Заданы условия, позволяющие определять или начальное, или конечное состояние системы, или оба этих состояния. Иногда задаются области начальных и конечных состояний. Поскольку управление системой осуществляется для достижения конкретной цели, то указан показатель эффективности управления, называемый целевой функцией, численно выражающий эффект («выигрыш»), получаемый при том или ином управлении из множества допустимых управлений. В экономических системах целевая функция может определять прибыль, затраты, рентабельность, объем производства и т. п. Задача динамического программирования состоит в выборе из множества допустимых управлений такого, которое переводит систему из начального состояния в конечное, обеспечивая при этом целевой функции экстремум (минимум или максимум в зависимости от ее экономической сути). Упомянутое управление называют оптимальным.

В основе вычислительных алгоритмов динамического программирования лежит следующий принцип оптимальности, сформулированный Р. Беллманом: каково бы ни было состояние системы S в результате i — 1 шагов, управление на i-м шаге должно выбираться так, чтобы оно в совокупности с управлениями на всех последующих шагах с (i+1)-го до N-гoвключительно доставляло экстремум целевой функции.

Введем следующие  обозначения: — множество состояний, в которых система S может находиться перед i-м шагом; элементы этого множества находятся из условий конкретной задачи. При i=l получается множество начальных состояний, которое может состоять из одного или нескольких элементов; то же самое можно сказать и о множестве конечных состояний; — множество состояний в конце i-гo шага; — множество управлений, которые могут быть выбраны на i-м шаге и под воздействием каждого из которых система S переходит в одно из состояний множества . Элементы множества определяются условиями конкретной задачи; — условно-оптимальное значение целевой функции на интервале от i-гo до N-гoшага включительно при условии, что перед i-м шагом система S находилась в одном из состояний множества , а на i-м шаге было выбрано такое управление из множества , которое обеспечило целевой функции условно-оптимальное значение; — значения целевой функции на i-м шаге для всех управлений из множества при условии, что перед i-м шагом система S находилась в одном из состояний множества ; — условно-оптимальное значение целевой функции на интервале от (i+1)-гo шага до N-гoвключительно при условии, что в результате воздействия управления, выбранного из множества , система S на i-м шаге перейдет к концу шага из состояния, принадлежащего множеству , в состояние из множества

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

Равенство называют основным функциональным уравнением динамического программирования.

 

Для последнего (N-гo) шага уравнение принимает вид

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

Если рассматривается  система без последействия, то ее состояние в конце i-гo шага будет отвечать одному из элементов множества и зависит как от состояния системы S на начало шага, которое характеризовалось соответствующим элементом множества , так и от управления, выбранного из множества . Эту зависимость символически можно записать в следующей форме: На основании уравнений и с учетом множеств и строится вычислительная процедура метода динамического программирования, распадающаяся на два этапа: условную и безусловную оптимизацию.

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

Для определения безусловно-оптимального управления системой S при заданном ее начальном состоянии анализируем выполненные расчеты, перемещаясь по оптимизируемому N-шаговому процессу в прямом направлении: от первого шага к последнему. Эта часть рассуждений называется безусловной оптимизацией. Для начального состояния находим в множестве условно-оптимальных управлений для первого шага с учетом условно-оптимального значения целевой функции на этом шаге безусловно-оптимальное управление и состояние в множестве системы S перед вторым шагом. С этими данными входим во второе множество управлений для второго шага и определяем и т. д.

Безусловно-оптимальное значение целевой функции для всего N-шагового процесса

Искомое оптимальное  управление можно записать в виде вектора

 

 

 

 

 

3 ОПИСАНИЕ  ПРОГРАММЫ

 

3.1 Описание  данных

 

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

 

Таблица 3 –  Введённые типы данных и их предназначение

Тип	Назначение
Int	Хранение числовой информации
String	Хранение текстовой информации
Table	Хранение таблиц

 

В программе  используются переменные, приведённые  в таблице 4.

 

Таблица 4 –  Введённые переменные и их предназначение

Переменная	Тип	Назначение
M	int	Количество предприятий
summa	int	Распределяемая сумма
CN	int	Кратность суммы
infoData	List<List<int>>	Значения целевой функции для  управлений
fT	Table	Первая таблица
Tables	List<Table>	Промежуточные таблицы
lT	Table	Последняя таблица

 

 

3.2 Описание основных методов

 

privatevoidbtnn1_Click(objectsender, EventArgse)

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

privateintXETz(List<List<int>> date, int Value, int Number)

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 1 – Блок-схема метода определения  значения целевой функции

 

 

 

 

 

 

4 ТЕСТИРОВАНИЕ  ПРОГРАММЫ

 

4.1 Описание  интерфейса

 

При запуске  программы появляется экранная форма (рисунок 2)

Рисунок 2 – Главное окно приложения

Данная форма  содержит следующие элементы:

<