Курсовая работа - Построение модели динамического программирования - файл n1.doc

Курсовая работа - Построение модели динамического программирования
скачать (212 kb.)
Доступные файлы (1):
n1.doc212kb.01.06.2012 08:39скачать

n1.doc



Министерство образования и науки Российской Федерации
Государственное образовательное учреждение

высшего профессионального образования

КУРСОВАЯ РАБОТА
на тему: «Построение модели динамического

программирования»
.


Иваново 2010 год
СОДЕРЖАНИЕ
Введение______________________________________________________3

  1. Анализ задания_________________________________________________4

  2. Понятие и общая постановка задачи динамического программирования_5

  3. Принцип оптимальности_________________________________________7

  4. Основные этапы составления математической модели задачи динамического программирования________________________________8

  5. Задачи динамического программирования_________________________10

5.1. Оптимальное распределение инвестиций как задача динамического программирования_______________________________________________10

5.2. Задача планирования рабочей силы___________________________11

5.3. Задача замены оборудования_________________________________12

6. Описание решения задачи______________________________________13

7. Описание интерфейса___________________________________________18

8. Текст программы создания файла_________________________________19

Список использованной литературы_______________________________22

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

Динамическое программирование — это метод нахождения оптимальных решений в задачах с многоэтапной структурой. В курсовой работе рассматривается нахождение оптимального решения при помощи динамического программирования. Условия: для разработки программы применяется среда программирования Visual C++.

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

Цель работы – построение модели динамического программирования оптимального распределения инвестиций.

Для этого необходимо решить следующие задачи:

1. рассмотреть методы и модели динамического программирования, используемые при решении задач;

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


1.АНАЛИЗ ЗАДАНИЯ
Модель – это изображение существенных элементов исследуемого объекта или процесса, которое характеризуется однозначной связью соответствующих знаний с этими элементами. Модель наглядна, если сочетание элементов и пространственно-временные отношения учитываются таким образом, что возникает определенная похожесть, позволяющая по модели узнать оригинал.

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

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

2.ПОНЯТИЕ И ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ

ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
Динамическое программирование (ДП) представляет собой математический метод, заслуга создания и развития которого принадлежит, прежде всего, Беллману. Характерным для динамического программирования является подход к решению задачи по этапам, с каждым из которых ассоциирована одна управляемая переменная. Набор рекуррентных вычислительных процедур, связывающих различные этапы, обеспечивает получение допустимого оптимального решения задачи в целом при достижении последнего этапа.

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

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

Приведем общую постановку задачи ДП. Рассматривается управляемый процесс, например, экономический процесс распре­деления средств между предприятиями, использования ресурсов в течение ряда лет, замены оборудования, пополнения запасов и т. п. В результате управления система (объект управления) S пере­водится из начального состояния s состояние ŝ . Предположим, что управление можно разбить на п шагов, т.е. решение принима­ется последовательно на каждом шаге, а управление, переводящее систему S из начального состояния в конечное, представляет собой совокупность п пошаговых управлений.

Обозначим через X управление на kшаге (k=1, 2, ..., п). Пе­ременные Х удовлетворяют некоторым ограничениям и в этом смысле называются допустимыми (X может быть числом, точкой в n-мерном пространстве, качественным признаком).

Пусть Х(Х1 , Х2 , ..., Хп) — управление, переводящее систему S из состояния s в состояние S . Обозначим через s состояние сис­темы после k-го шага управления. Получаем последовательность состояний s , s ,…, s , s , …, s , s =ŝ.

Показатель эффективности рассматриваемой управляемой опе­рации — целевая функция — зависит от начального состояния и управления:

Z=F(s ,Х) (1)

Сделаем несколько предположений.

1. Состояние s системы в конце k-го шага зависит только от предшествующего состояния s и управления на kшаге X (и не зависит от предшествующих состояний и управлений). Это требование называется "отсутствием последействия". Сформули­рованное положение записывается в виде уравнений

s = ? (s , X ), k=1,2,…,n (2)

которые называются уравнениями состояний.

2. Целевая функция (1) является аддитивной от показателя эффективности каждого шага. Обозначим показатель эффек­тивности каждого шага через

Z = ѓ (s , X ), k=1,2,…,n, (3)

тогда

Z= ? ѓ (s ,X ) (4)

Задача пошаговой оптимизации (задача ДП) формулируется так: определить такое допустимое управление X, переводящее сис­тему S из состояния s0 в состояние ŝ, при котором целевая функция (4) принимает наибольшее (наименьшее) значение.

Выделим особенности модели ДП:

1. Задача оптимизации интерпретируется как п-шаговый процесс управления.

2. Целевая функция равна сумме целевых функций каждого шага.

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

4. Состояние sn после каждого шага управления зависит только от предшествующего состояния sn-1 и управления X (отсутствие по­следействия).

5. На каждом шаге управление Х зависит от конечного числа управляющих переменных, а состояние s — от конечного числа па­раметров (смысл замечания S станет ясным из рассмотренных ниже примеров).

Следует отметить, что существуют различные способы реше­ния подобных задач, применяемые в зависимости от вида функций, ограничений, размерности и т. п. Рассмотрим вычислитель­ную схему ДП, которая окажется безразличной к способам зада­ния функций и ограничений. Вычислительная схема связана с принципом оптимальности и использует рекуррентные соотношения.
3.ПРИНЦИП ОПТИМАЛЬНОСТИ
Принцип оптимальности впервые был сформулирован Р. Беллманом в 1953 г. Каково бы ни было состояние s системы в резуль­тате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управле­нием на всех последующих шагах приводило к оптимальному выигры­шу на всех оставшихся шагах, включая данный. Беллманом четко были сформулированы и условия, при которых принцип верен. Основное требование — процесс управления должен быть без обратной связи, т.е. управление на данном шаге не должно ока­зывать влияния на предшествующие шаги.

Принцип оптимальности утверждает, что для любого процесса без обратной связи оптимальное управление таково, что оно явля­ется оптимальным для любого подпроцесса по отношению к ис­ходному состоянию этого подпроцесса. Поэтому решение на каж­дом шаге оказывается наилучшим с точки зрения управления в целом. Если изобразить геометрически оптимальную траекторию в виде ломаной линии, то любая часть этой ломаной будет яв­ляться оптимальной траекторией относительно начала и конца.
4. ОСНОВНЫЕ ЭТАПЫ СОСТАВЛЕНИЯ МАТЕМАТИЧЕСКОЙ

МОДЕЛИ ЗАДАЧИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
1. Разбиение задачи на шаги (этапы). Шаг не должен быть слишком мелким, чтобы не проводить лишних расчетов и не должен быть слишком большим, усложняющим процесс шаговой оптимизации.

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

3. Определение множества шаговых управлений xi, i=1..m и налагаемых на них ограничений, т.е. области допустимых управлений X.

4. Определение выигрыша 

?(s, xi), (3)

который принесет на i-м шаге управление xi, если система перед этим находилась в состоянии s.

5. Определение состояния s, в которое переходит система из состояния s под влиянием управления xi

s’=fi(s, xi,), (4)

где fi—функция перехода на i-м шаге из состояния s в состояние s.

6. Составление уравнения, определяющего условный оптимальный выигрыш на последнем шаге, для состояния s моделируемого процесса

Wm(S)=max{?m(s,xm)} (5)

xmЂX

7. Составление основного функционального уравнения динамического программирования, определяющего условный оптимальный выигрыш для данного состояния s с i-го шага и до конца процесса через уже известный оптимальный выигрыш с (i+1)-го шага и до конца:

Wi(S)=max{?i(s, xi)+Wi=1(fi(s, xi))} (6)

xmЂX

В уравнении (6) в уже известную функцию Wi+1(s), характеризующую условный оптимальный выигрыш с (i+1)-го шага до конца процесса, вместо состояния s подставлено новое состояние s’=fi(s, xi), в которое система переходит на i-м шаге под влиянием управления xi.

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


5.ЗАДАЧИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
5.1 Оптимальное распределение инвестиций как задача

динамического программирования
Инвестор выделяет средства в размере D условных единиц, которые должны быть распределены между m-предприятиями. Каждое i-е предприятие при инвестировании в него средств x приносит прибыль qi(x) условных единиц, i=1..m. Нужно выбрать оптимальное распределение инвестиций между предприятиями, обеспечивающее максимальную прибыль.

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

1. Определение числа шагов. Число шагов m равно числу предприятий, в которые осуществляется инвестирование.

2. Определение состояний системы. Состояние системы на каждом шаге характеризуется количеством средств si, имеющихся в наличии перед данным шагом,

s?D.

3 Выбор шаговых управлений. Управлением на i-м шаге xi, x=1..m является количество средств, инвестируемых в i-е предприятие.

4. Функция выигрыша на i-м шаге

qi(xi) (7)

- это прибыль, которую приносит i-е предприятие при инвестировании в него средств

m

W=?qixi,

i=1

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

5. Определение функции перехода в новое состояние.

fi(s,x)=s-x (8)

Таким образом, если на i-м шаге система находилась в состоянии s, а выбрано управление x, то на i+1-м шаге система будет находиться в состоянии s-x. Другими словами, если в наличии имеются средства в размере s у.е., и в i-е предприятие инвестируется x у.е., то для дальнейшего инвестирования остается (s-x) у.е.

6. Составление функционального уравнения для i=m.

Wm(s)=qm(s) (9)

xm(s)=s (10)

На последнем шаге, т.е. перед инвестированием средств в последнее предприятие, условное оптимальное управление соответствует количеству средств, имеющихся в наличии; т.е. сколько средств осталось, столько и надо вложить в последнее предприятие. Условный оптимальный выигрыш равен доходу, приносимому последним предприятием.

7. Составление основного функционального уравнения.

Подставив в формулу (6) выражения (7) и (8), получим следующее функциональное уравнение

Wi(s)=max{qi(x)+Wi+1(s-x)} (11)

Пусть перед i-м шагом у инвестора остались средства в размере s у.е. Тогда х у.е. он может вложить в i-е предприятие, при этом оно принесет доход qi(x), а оставшиеся s-x у.е.—в остальные предприятия с i+1-го до m-го. Условный оптимальный выигрыш от такого вложения Wi+1(s-x). Оптимальным будет то условное управление x, при котором сумма qi(x) и Wi+1(s-x) максимальна.
5.2 Задача планирования рабочей силы

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

Предположим, что проект будет выполняться в течение n недель и минимальная потребность в рабочей силе на протяжении i-й недели составит bi рабочих. При идеальных условиях хотелось бы на протяжении i-й недели иметь в точности bi рабочих. Однако в зависимости от стоимостных показателей может быть более выгодным отклонение численности рабочей силы как в одну, так и в другую сторону от минимальных потребностей.

Если xi – количество работающих на протяжении i-й недели, то возможны затраты двух видов: 1) С1(xi- bi)-затраты, связанные с необходимостью содержать избыток xi - bi рабочей силы и 2) С2(xi- xi-1)-затраты, связанные с необходимостью дополнительного найма (xi- xi-1) рабочих.

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

1.Этап і представляется порядковым номером недели і,

і=1,2,…n.

2.Вариантами решения на і-ом этапе являются значения xi

количество работающих на протяжении і-й недели.

3.Состоянием на і-м этапе является xi-1 – количество

работающих на протяжении (і-1) –й недели (этапа).

Рекуррентное уравнение динамического программирования представляется в виде



где

Вычисления начинаются с этапа n при xn=bn и заканчиваются на этапе 1.
5.3 Задача замены оборудования

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

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

Обозначим через r(t) и c(t) прибыль от эксплуатации t-летнего механизма на протяжении года и затраты на его обслуживание за этот же период. Далее пусть s(t) – стоимость продажи механизма, который эксплуатировался t лет. Стоимость приобретения нового механизма остается неизменной на протяжении всех лет и равна I.

Элементы модели динамического программирования таковы:

Этап і представляется порядковым номером года і, і=1,2,...n.

Вариантами решения на і-м этапе (т.е. для і-ого года) являются альтернативы: продолжить эксплуатацию или заменить механизм в начале і-ого года.

Состоянием на і-м этапе является срок эксплуатации t (возраст) механизма к началу і-ого года.

Пусть fi(t)-максимальная прибыль, получаемая за годы от і до n при условии, что в начале і-ого года имеется механизм t-летнего возраста.

Рекуррентное уравнение имеет следующий вид:



(1)-если эксплуатировать механизм,

(2)-если заменить механизм.
6. ОПИСАНИЕ РЕШЕНИЯ ЗАДАЧИ

В работе рассматривается задача динамического программирования – оптимальное распределение инвестиций.

Инвестор выделяет средства в размере N условных единиц, которые должны быть распределены между m-предприятиями. Каждое i-е предприятие при инвестировании в него средств x приносит прибыль Zi(x) условных единиц, i=1..m. Нужно выбрать оптимальное распределение инвестиций между предприятиями, обеспечивающее максимальную прибыль.

N=5000 (кратно 1000)

m=3

Значения Zi(x), i=1..3 заданы в таблице


Выделяемые средства

Предприятие

№1

№2

№3

Прирост Zi(Ui)

Z1(Ui)

Z2(Ui)

Z3(Ui)

1

1

2

3

2

4

5

6

3

8

9

8

4

10

12

11

5

14

15

16


Шаг 3

F3(X2,U3)=max(Z3(X2,U3))


X2

U3

X3

F3

0

0

0

0

1

1

3

3

2

2

6

6

3

3

8

8

4

4

11

11

5

5

16

16


Шаг 2

F2(X1,U2)=max(Z2(X1,U2)+F3(X2))



X1

U2

X2

Z2

F3

Z2+F3

F2

0

0

0

0

0

0

0

1

0

1

1

0

0

2

3

0

3

2

3

2

0

1

2

2

1

0

0

2

5

6

3

0

6

5

5

6

3

0

1

2

3

3

2

1

0

0

2

5

9

8

6

3

0

8

8

8

9

9

4

0

1

2

3

4

4

3

2

1

0

0

2

5

9

12

11

8

6

3

0

11

10

11

12

12

12

5

0

1

2

3

4

5

5

4

3

2

1

0

0

2

5

9

12

15

16

11

8

6

3

0

16

13

13

15

15

15

16


Шаг 1

F1(X0,U1)=max(Z1(X0,U1)+F2(X1))


X0

U1

X1

Z1

F2

Z1+F2

F1

0

0

0

0

0

0

0

1

0

1

1

0

0

1

3

0

3

1

3

2

0

1

2

2

1

0

0

1

4

6

3

0

6

4

4

6

3

0

1

2

3

3

2

1

0

0

1

4

8

9

6

3

0

9

7

7

8

9

4

0

1

2

3

4

4

3

2

1

0

0

1

4

8

10

12

9

6

3

0

12

10

10

11

10

12

5

0

1

2

3

4

5

5

4

3

2

1

0

0

1

4

8

10

14

16

12

9

6

3

0

16

13

13

14

13

14

16


Прибыль =16 ден. ед.


8. ОПИСАНИЕ ИНТЕРФЕЙСА





9. ТЕКСТ ПРОГРАММЫ СОЗДАНИЯ ФАЙЛА
void CAboutDlg::OnButton1()

{

int i,x,s;

int q1_n[5] = {EDQ11, EDQ12, EDQ13, EDQ14, EDQ15};

int q2_n[5] = {EDQ21, EDQ22, EDQ23, EDQ24, EDQ25};

int q3_n[5] = {EDQ31, EDQ32, EDQ33, EDQ34, EDQ35};

double q1[6],q2[6],q3[6],w2[6],x2[6],w1,w1max,w1t,w2max,w2t,x2max,x1max;

// char *tempbuf;

q1[0] = 0;

q2[0] = 0;

q3[0] = 0;

x2[0] = 0;

w2[0] = 0;

x = 0;

s = 0;

i = 0;

char tempbuf[100];

for (i=1;i<=5;i++)

{

::GetDlgItemText(CWnd::m_hWnd, q1_n[i-1], tempbuf, 100);

q1[i] = atof(tempbuf);

}

for (i=1;i<=5;i++)

{

::GetDlgItemText(CWnd::m_hWnd, q2_n[i-1], tempbuf, 100);

q2[i] = atof(tempbuf);

}

for (i=1;i<=5;i++)

{

::GetDlgItemText(CWnd::m_hWnd, q3_n[i-1], tempbuf, 100);

q3[i] = atof(tempbuf);

}
//i=2

for (s=1;s<=5;s++)

{

w2max = 0;

for (x=0;x<=s;x++)

{

w2t = q2[x]+q3[s-x];

if (w2t > w2max)

{

w2max = w2t;

x2max = x;

}

}

w2[s] = w2max;

}

//i=3

w1max = 0;

s = 5;

for (x=0;x<=5;x++)

{

w1t = q1[x]+w2[s-x];

if (w1t > w1max)

{

w1max = w1t;

x1max = x;

}

}

w1=w1max;

char buf[10];

double otvet = w1;

gcvt(otvet, 7, buf);

MessageBox(buf, "Максимальная прибыль", MB_OK);

}


СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ:
1.Акоф Р., Сасиени М. Основы исследования операций. –М.: Мир,1971.

2.Аоки М. Введение в методы оптимизации. –М.: Наука,1977.

3.Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. –М.: Наука,1965.

4.Вентцель Е. С. Элементы динамического программирования. –М.: Наука,1987.

5.Вентцель Е. С. Исследование операций: задачи, принципы, методология. –М.: Наука,1988.

6. Динамическое программирование// http://www.karelia.ru/psu/Faculties/Forest/courses/decision/chap5_a.htm .

7.Зайченко Ю. П. Исследование операций. –К.: Высшая школа,1985.

8.::Bolshe.ru:: Методология и методы принятия решения// http://www.bolshe.ru/unit/109/books/297/s/1.

9. Кузнецов А.В., Холод Н.И., Костевич Л.С. «руководство к решению задач по математическому программированию: Учебное пособие».- Мн.: Высш.шк.,2001.

10.Муну М. Математическое программирование. Теория алгоритмов. –М.: Наука,1990.

11.Экономико-математические методы и прикладные модели: Учеб. пособие для вузов / Федосеев В.В., Гармаш А.Н., Дайитбегов Д.М. и др.; Под ред. В.В. Федосеева. - М.: ЮНИТИ, 2002. - 391с.



Министерство образования и науки Российской Федерации
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации