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

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

Задачи для осуществления основных целей:

1. Исследовать теоретические носновы динамического нпрограммирования (в том числе полную постановку, принцип оптимальностия рекурентного уравнения Р.Э. Беллмана)

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

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

4. Осуществить данныен задачи в среде MathCad.

Статистика работы .

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

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

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

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

Развитие динамическогожпрограммирования можно отнести к 50-м годам ХХ в. и тесно связано с именемоРичарда Эрнеста Беллмана.

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

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

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

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

Пусть X=(X₁, X₂, …, X_n) – управление,жкоторый переводит «S» из состояния s₀ в состояние s_n. Обозначим через s_k состояние «S» (который характеризуется определенным набором параметров и определенных их значений) после k-голшага. Причем состояниетсистемы s_k в конце k-го шага зависит только отопредыдущего состояния s_k_-1 и управленческогожрешения на k-ом шаге X_k (т.е. не зависитмнапрямую от предыдущих состояний и управленческих решений). Данноебтребование можно назвать «отсутствием последствия» и можно выразить следующимишуравнениями состояний:

. (1.1)

Далее получаемьпоследовательность состояний s₀, s₁, …, s_k_-1, s_k, …, s_n_-1, s_n. Тогда n-шаговый управленческийьпроцесс схематично можно представить следующим образом:

Пусть показательщэффективности k-го шага представляют некоторой функцией:

, (1.2)

а эффективность рассматриваемогобмногошагового процесса следующей аддитивной функцией:

, (1.3)

или

. (1.4)

Тогда задачу пошаговой оптимизации можно сформулировать следующим образом:топределить такое допустимоеюуправление Х, который меняет систему S изусостояния s₀ в состояние s_n, пригкотором целеваяжфункция Z принимаетьнаибольшее или наименьшее значение.

Задачаюдинамического программированиябможет обладать следующими особенностями:

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

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

3. Выбортуправления на k-ом шагеизависит только от состояния системы к этому шагу. Не влияеттна предыдущие шаги.

4. Состояние s_k послеуk-го шага управлениябзависит от предыдущего состояния s_k_-1 и управления X_k («отсутствие последствия»).

5. На каждомишаге управление X_k зависит отбконечного числа управляющихьпеременных, а состояние s_k – от окончательноготчисла параметров.

1.2. Принцип оптимальности и уравнения Беллмана

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

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

Можно рассмотретььобщую задачу динамическогоьпрограммирования, которуюьпривели выше. На каждом шаге кроме последнегоьдля любого состояния системы s_k_-1 управленческое решение X_k нужноьвыбрать «с оглядкой», так как этот выборьоказывает влияниеьна последующееьсостояние системы s_k.

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

Рассмотрим последний n-й шаг:

s_n_-1 – первоначальноеьсостояние системы n-го шага;

s_n – окончательноеьсостояние системы;

X_n – управлениеьна n-ом шаге;

f_n(s_n_-1, X_n) – целевая функцияьn-го шага.

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

Обозначим через ьоптимум целевой функции, ькоторый показываетьэффективности n-го шага при выполненииьусловии, чтоьк началу последнего шага система S была в произвольномьсостоянии s_n_-1 , а на последнем шаге управление былоьоптимальным.

можно назватььусловным максимумомьцелевой функции на n-ом шаге, и определитььпо формуле ниже:

. (1.5)

Максимизация ведетсяьпо всемьвозмоным управлениям X_n.

Решение X_n, приькотором можноьдостичь , аьтакже зависит от s_n_-1 и называютьусловным оптимальнымьрешением наьn-ом шаге. Обозначимьего через .

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

Исследуемьдвухшаговую задачу: присоединимьк n-му шагу (n–1)-й.

Для всех состояний s_n_-2, произвольныхьуправленческих решений X_n_-1 и оптимальномьуправлении на n-ом шаге значение целевой функции на двух последних шагах вычисляемьпо формуле:

. (1.6)

По принципуьоптимальности Р.Э.Беллманаьдля любых s_n_-2 решение выбираемьтак, чтобы оноьвместе с оптимальнымьуправлением на последнем (n-ом) шаге привелоьбы к оптимумуьцелевой функции наьдвух последних шагах. Таким образом, ьнужно отыскатььоптимум выражения (1.6) по всем возможным управленческимьрешениям X_n_-1:

. (1.7)

– являетсяьусловным максимумомьцелевой функцииьпри оптимальном управлении на двух последних шагах. Отметим то, ьчто выражение в фигурныхьскобках в формуле (1.7), зависит только от s_n_-2 и X_n_-1, так как s_n_-1 можно найти из уравнения состояний (1.1) при :

. (1.8)

Соответствующееьуправление X_n_-1 наь (n–1)-ом шагеьобозначим через и мыьназываемьусловным оптимальнымьуправлением на (n–1)-ом.

Таким же путемьопределяются условныеьоптимумы целевойьфункции при оптимальном управлении на (n–k+1) шагах, начиная с k-го до конца, при условии, что к началу k-го шагаьсистемаьнаходилась в состоянии s_k_-1:

. (1.9)

Управление X_k на k-ом шаге, достигающееьмаксимума по (1.9), обозначим и назовемьусловнымьоптимальным управлением на k-ом шаге.

Уравнения (1.5) и (1.9) называют рекуррентнымиьуравнения Беллмана (обратная схема). Этапыьрешения данных уравнений можно назватььусловной оптимизацией.

В результате условнойьоптимизации получаемьдве последовательности:

, , …, , – условные максимумы целевой функции на последнем, двух последних, …, на n шагах;

, , …, , – условныеьоптимальные управления на n-ом, (n–1)-ом, …, на 1-ом шагах.

Используем данныеьпоследовательности, ьнайдем решение задачиьдинамического программированияьпри данных n и s₀:

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

Такжеьрассуждая, ьвыстроим и прямую схему условной оптимизации:

, (1.10)

. (1.11)

Оптимальное решение задачи в этомьслучае находится поьсхеме:

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

1. Выбираетсяьварианты деления процессаьуправления на шаги.

2. Определяетсяьпараметры состояния s_k и переменныеьуправления X_k на каждом шаге, записываетсяьуравнения состояний.

3. Вводятся целевые функции k-ого шагаьи суммарнуюьцелевую функцию, а также условные оптимумы иьусловное оптимальноеьуправление на k-ом шаге ().

4. Записывается в соответствииьс обратнойьили прямойьсхемой рекуррентные уравнения Беллмана и после вычесленияьусловной оптимизации получаетсяьдве последовательности: {} и {}.

5. Определяетсяьоптимальное значениеьцелевой функции иьоптимальное решение .

1.3. Задача распределения ресурсов

Имеется определенноетколичество ресурсов s₀, которое нужнотраспределить между n хозяйствующимитсубъектами на текущуютдеятельность в течение некотороготпериода (месяц, квартал, тполугодие, год и т.д.) с целью получения совокупнойтмаксимальнойтприбыли. Размеры вложенийтресурсов x_i (;) в деятельностьткаждого хозяйствующеготсубъекта кратны определеннойтвеличине h. Нам известно то, тчто каждый хозяйствующийтсубъект в зависимоститот объема используемыхтсредств x_i за рассматриваемый период приносит доход в размере f_i(x_i), который не зависиттот размеров вложенныхтресурсов в другие хозяйствующие субъекты.

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

Можно представимтпроцесстраспределения ресурсов междутхозяйствующими субъектами как n-шаговыйтпроцесс управления (номертшага совпадает с условнымтномером хозяйствующеготсубъекта). Пусть s_k () – параметр состояния, количествотсвободныхтсредств после k-готшага длятраспределения между оставшимися (n – k) хозяйствующимитсубъектами. Тогда уравнения состояний можем записатьттак:

(1.12)

Введем в рассмотрениетфункцию – условно оптимальный совокупный доход, тполученный от k-го, (k+1)-го, …, n-го хозяйствующихтсубъектов, еслитмежду нимитоптимальным образомтраспределялисьтресурсы в объеме s_k_-1 (). Множествотвозможныхтуправленческих решенийтотносительно размера распределяемыхтресурсов натk-ом шаге представим таким образом: .

Таким образом, трекуррентные уравнениятБеллмана (обратная схема) будут иметь вид:

(1.13)

Далее потрезультатам условнойтоптимизации можемтопределить оптимальное распределениетресурсов тпо следующейтсхеме:

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

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

Известны (таблица 1.1):

· ценаснового оборудования p;

· первоначальныесзатраты по новомусоборудованию r(0), включающие затраты на доставку, смонтаж оборудования, спуско-наладочные работы и др.;

· эксплуатационныесзатраты r(t) (осуществляются всначале каждого периода, зависятсот возраста оборудования t);

· рыночная стоимостьсоборудования, эксплуатировавшегося t лет φ(t),

· примерныесгодовые темпы прироста инфляции R.

Таблица 1.1

Исходные данные


T =7 лет (горизонт планирования)		1	2	3	4	5	6	7
R (% годовых)		8	10	11	11,5	12	13	14
T_a=10 лет		Способ начисления амортизации: уменьшаемого остатка
t (возраст оборудования)	0 (новое)	1	2	3	4	5	6	7
p (усл. ден. ед.)	12500
r(t) (усл. ден. ед.)	1250	1550	1950	2400	2900	3200	4000	–
φ(t)		11250	10125	9112	8201	7381	6643	5979

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

Решение:

Примем способчделения управлениячна шаги – по годам. Исходя из заданной величины горизонта планирования T=7 лет, соответственно k=1, 2, …, 7, где k – рассматриваемый шагчуправления (начало k-го года).

За параметрычсостояния системычпримем возрастчоборудования: – возраст оборудованиячt к концу k-го года ( – начальное состояние системы). При этом зависитчот управленияч (управленческого решения) , принимаемого на k-омчуправленческом шаге (в начале k-го года). Управление в зависимости от возраста оборудованиячможет приниматьчодно из следующих значений , где P – приобрестичоборудование, при k=1; S – сохранить оборудование, при k=2, 3, …, 7; Z – заменить оборудование новым, при k=2, 3, …, 7. Тогда уравнения состоянийчможно записатьчв таком виде:

(1.14)

Показатели эффективности k-го шагачв постоянных ценах:

(1.15)

Показателичэффективности k-го шага вчтекущих ценах:

(1.16)

где – коэффициент, учитывающийчинфляцию (рассчитывается по методу сложных процентовчна конец года):

для 1 года: ;

для 2 года: ;

для n года: .

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

(1.17)

Пусть – условно-оптимальныечзатраты на эксплуатациючоборудования, начиная с k-го шагачдо конца, при том, ччто к началу k-го шагачоборудование имеетчвозраст t лет, т.е. .

Тогда рекуррентныечуравнения Р.Э. Беллмана (обратная схема) будутчиметь вид (в постоянных ценах):

(1.18)

В условияхчтекущих цен рекуррентныечуравнения Р.Э. Беллмана (обратная схема) будут иметь следующий вид:

(1.19)

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

2. Решение задач стратегического планирования деятельности компании методами динамического программирования и реализация задач в среде MathCad.

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

Имеется известноеиколичество ресурсов s₀, котороеинужно распределить между n хозяйствующими субъектамиина данной деятельность в течение рассматриваемогоивремени (месяц, квартал, полугодие, год и т.д.), чтобыиполучить совокупную максимальную прибыль. Объемыивложений ресурсов x_i (;) в деятельностьикаждого хозяйствующего субъекта кратны некоторой величине h. Нам известно, чтоикаждый хозяйствующийисубъект в зависимости от объемаииспользуемых средств x_i за рассматриваемое времяиприносит прибыль в размере f_i(x_i), которыйине зависит от вложения ресурсов в другие хозяйствующие субъекты. Начальныеиданные приведены в таблице 2.1.

Таблица 2.1

Исходные данные (усл. ед.)

s₀=10, h=2
x	f₁(x)	f₂(x)	f₃(x)	f₄(x)
2	9	7	10	8
4	15	21	18	12
6	24	25	30	28
8	33	35	39	37
10	50	51	61	60

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

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

(2.1)

Вводимйв рассмотрение функцию – условнойоптимальная совокупная прибыль, которую можно получитьйот k-го, (k+1)-го, …, n-го хозяйствующих субъектов, еслиймежду ними оптимальнойраспределялись ресурсы в объеме s_k_-1 (). Множествойвозможных управленческих решений относительнойразмера распределяемых ресурсов на k-ом шаге можемйпредставить таким образом: .

Тогда рекуррентные уравнения Р.Э. Беллмана (обратная схема) будут иметь вид:

(2.2)

Пой полученным результатам условной оптимизации можемйопределить оптимальное распределение ресурсов по такоййсхеме:

(2.3)

Определяемйусловные максимумы в соответствии с (2.2), итогийрасчетов представлены в таблице (2.1).

Таблица 2.2

Расчет условных оптимумов

s_k_-1	x_k	s_k	k=3			k=2			k=1
s_k_-1	x_k	s_k
1	2	3	4	5	6	7	8	9	10	11	12
0	0	0	0	0	0	0	0	0	0	0	0
2	0	2	0+8=8	10	2	0+10=10	10	0	0+10=10	10	0
2	2	0	10+0=10	10	2	7+0=7	10	0	9+0=9	10	0
4	0	4	0+12=12	18	(2) 4	0+18=18	21	4	0+21=21	21	0
	2	2	10+8=18			7+10=17			9+10=19
	4	0	18+0=18			21+0=21			15+0=15
6	0	6	0+28=28	30	6	0+30=30	31	4	0+31=31	31	0
	2	4	10+12=22			7+18=25			9+21=30
	4	2	18+8=26			21+10=31			15+10=25
	6	0	30+0=30			25+0=25			24+0=24
8	0	8	0+37=37	39	8	0+39=39	39	0 (4)	0+39=39	40	2
	2	6	10+28=38			7+30=37			9+31=40
	4	4	18+12=30			21+18=39			15+21=36
	6	2	30+8=38			25+10=35			24+10=34
	8	0	39+0=39			35+0=35			33+0=33
10	0	10	0+60=60	61	10	0+61=61	61	0	0+61=61	61	0
	2	8	10+37=47			7+39=46			9+39=48
	4	6	18+28=46			21+30=51			15+31=46
	6	4	30+12=42			25+18=43			24+21=45
	8	2	39+8=47			35+10=45			33+10=43
	10	0	61+0=61			51+0=51			50+0=50

По итогамйусловной оптимизациийопределим оптимальное распределение ресурсов:

Следовательно, йоптимальное распределение ресурсов:

, которое обеспечит наибольшую прибыль в размере 61 усл. ден. ед.

Фрагмент MathCAD-документа, которое реализуетйрешение данной задачи, привела вйприложении 3. На рис. 2.1 представилайблок ввода исходныхйданных. Вектор Q может представитьй множество возможных управленческихйрешений x_i, матрица F может определитьйприбыльность предприятиййв зависимости от выделенных ресурсов (размерности Q и F можно изменять). Особенностью программы является то, что первыейкомпоненты вектора Q и матрицы F должны быть нулевыми, несоблюдение данного условия может привестийк ошибочным итогам.

Рис. 2.1. Фрагмент MathCAD-документа: система исходных данных задачи распределения ресурсов

На рис. 2.2 представлены итогиырешения, в соответствии с которыми оптимальным распределением является: выделение 10 усл. ед. третьему хозяйствующему субъекту и 0 усл. ед. – четвертому. Данное распределение обеспечит максимум прибыли в размере 61 усл. ед.

Рис. 2.2. Фрагмент MathCAD-документа: результаты решения задачи распределения ресурсов

Решим эту чже задачу прямойч схемой чБеллмана:

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

1 шаг.

На данном чшаге состояниеч системы - , предыдущее чсостояние - .

{X_i} –множество чуправлений на чпервом шаге. Показатель чэффективности ч1-го шага - .

(2.4)

2 шаг

(2.5)

……………………………………………………….

k-ый шаг

(2.6)

………………………………………………………..

n-ый шаг

(2.7)

В результате чпрохождения всех чшагов от чпервого к чпоследнему определяется чоптимальное значение чцелевой функции, чкоторое приравнивается оптимальномуч показателю эффективности чn-го шага . Чтобы чнайти оптимальную чстратегию управления, чт.е. определить чрешение задачи{X_k}, необходимо чснова пройти всю чпоследовательность шагов – чот последнего кч первому.

Поиск оптимальной чстратегии можноч представить в чвиде чсхемы:

Таблица 2.3

Расчет условных оптимумов

s_k_-1	x_k	s_k	k=1			k=2			k=3
s_k_-1	x_k	s_k
1	2	3	4	5	6	7	8	9	10	11	12
0	0	0	0	0	0	0	0	0	0	0	0
2	0	2	0+7=7	9	2	0+9=9	10	2	0+10=10	10	0
2	2	0	9+0=9	9	2	10+0=10	10	2	8+0=8	10	0
4	0	4	0+21=21	21	0	0+21=21	21	0	0+21=21	21	0
	2	2	9+7=16			10+9=19			8+10=18
	4	0	15+0=15			18+0=18			12+0=12
6	0	6	0+25=25	30	2	0+30=30	31	2	0+31=31	31	0
	2	4	9+21=30			10+21=31			8+21=29
	4	2	15+7=22			18+9=31			12+10=22
	6	0	24+0=24			30+0=30			28+0=28
8	0	8	0+35=35	36	4	0+36=36	40	2	0+40=40	40	0
	2	6	9+25=34			10+30=40			8+31=39
	4	4	15+21=36			18+21=39			12+21=33
	6	2	24+7=31			30+9=39			28+10=38
	8	0	33+0=33			39+0=39			37+0=37
10	0	10	0+51=51	50	10	0+50=50	61	10	0+61=61	61	0
	2	8	9+35=44			10+36=46			8+40=48
	4	6	15+25=40			18+30=48			12+31=43
	6	4	24+21=45			30+21=51			28+21=49
	8	2	33+7=40			39+9=48			37+10=47
	10	0	50+0=50			61+0=61			60+0=60

По итогамйусловной оптимизациийопределим оптимальное распределение ресурсов:

Следовательно, йоптимальное распределение ресурсов:

, которое обеспечит наибольшую прибыль в размере 61 усл. ден. ед.

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

Известны (таблица 2.4):

· ценаснового оборудования p;

· рыночная стоимостьсоборудования, эксплуатировавшегося t лет φ(t),

· примерныесгодовые темпы прироста инфляции R.

Таблица 2.4

Исходные данные


T =7 лет (горизонт планирования)		1	2	3	4	5	6	7
R (% годовых)		8	10	11	11,5	12	13	14
T_a=10 лет		Способ начисления амортизации: уменьшаемого остатка
t (возраст оборудования)	0 (новое)	1	2	3	4	5	6	7
p (усл. ден. ед.)	12500
r(t) (усл. ден. ед.)	1250	1550	1950	2400	2900	3200	4000	–
φ(t)		11250	10125	9112	8201	7381	6643	5979

(2.8)

Показателиыэффективности k-го шага в постоянных ценах:

(2.9)

Показатели эффективности k-го шага в текущих ценах:

(2.10)

где – коэффициент, ыучитывающий инфляцию (рассчитывается по методу сложных процентов на конец года):

для 1 года: ;

для 2 года: ;

для n года: .

Если темпы инфляцииыпостоянные или приблизительноыпостоянные, то можноывоспользоваться такой формулой:

(2.11)

Пусть – условно-оптимальные затраты наыэксплуатацию оборудования, ыначиная с k-го шага доыконца, при том, что к началу k-го шагаыоборудование имеет возраст t лет, т.е. . Тогда рекуррентныеыуравнения (в соответствии с обратной схемой Р.Э. Беллмана) будутыиметь вид (в постоянных ценах):

(2.12)

В условиях текущихыцен рекуррентные уравнения (в соответствии с обратной схемой Р.Э. Беллмана) будут иметь следующийывид:

(2.13)

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

Для рассматриваемого примера значения коэффициентов, ыкоторый учитывает ыинфляцию и рассчитанных по формуле (2,11), будут следующими:

Таблица 2.5

Коэффициенты, учитывающие инфляцию

T =7лет

(горизонт планирования)

R (% годовых)

11,5

1,08

1,19

1,32

1,48

1,66

1,88

2,14

Таблица 2.6

Остаточная стоимость на конец года.

Год	Остаточная стоимость на начало года (руб.)	Норма амортизации, %	Сумма годовой амортизации (руб.)	Остаточная стоимость на конец года (руб.)
1	12500	10	1250	11250
2	11250	10	1125	10125
3	10125	10	1013	9112
4	9112	10	911	8201
5	8201	10	820	7381
6	7381	10	738	6643
7	6643	10	664	5979

Для рассматриваемогоыпримера значения коэффициентов, ыучитывающих инфляцию и рассчитанныхыпо формуле (2.13), будутыследующими:

Рассмотрим 7-й шаг, т.е. k=7:

Используя формулы (2.13), вычислимыусловно-оптимальные затраты приыразличных состоянияхысистемы на начало седьмого года :

Рассмотрим 6-й шаг, т.е. k=6:

Используя формулы (2.13), вычислимыусловно-оптимальные затраты при различныхысостояниях системыына начало шестогосгода :

Рассмотрим 5-й шаг, т.е. k=5:

Используем формулы (2.13), вычислимыусловно-оптимальные затраты при различных состоянияхысистемы на началоыпятого года :

Рассмотрим 4-й шаг, т.е. k=4:

Используем формулы (2.13), вычислимсусловно-оптимальныесзатраты при различных состоянияхссистемы на начало четвертого года :

Рассмотрим 3-й шаг, т.е. k=3:

Используемсформулы (2.13), вычислимыусловно-оптимальные затраты приыразличных состоянияхысистемы на начало третьего года :

Рассмотрим 2-й шаг, т.е. k=2:

Используемсформулы (2.13), вычислимыусловно-оптимальные затраты при различныхысостоянияхысистемы на начало второго года :

Рассмотрим 1-й шаг, т.е. k=1:

Используемсформулы (2.13), вычислимыусловно-оптимальные затраты при условии, что системаына начало первого года находиласьыв состоянии :

Составим картусуправленческих решений. ыСплошными стрелками отметим условно-оптимальныеырешения.

Рис. 2.3. Карта управленческих решений

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

Фрагмент MathCAD-документа, который реализуетырешение данной задачи, приведен в приложении 4. На рис. 2.4 представлен блок вводаыисходных данных. Программаыпозволяет вестиырасчет в текущих (с учетом инфляции) или постоянных ценах, ызадавать горизонт планирования (в программе эффективный горизонт планирования условноыпринят до 7 лет, приынеобходимости его можно увеличить, изменивыразмерность вектора R и задав соответствующее значение параметру Т), выбирать способы вводаыликвидной стоимостиыоборудования, эксплуатировавшегося t лет (с помощью «жестко» заданногоывектора ликвидной стоимости F, либо (при отсутствии данной информации) использовать остаточную стоимость оборудования, ырассчитанную на основе определенногоыметода (линейного или уменьшаемогоыостатка) начисления амортизации).

$Описание: C:\Users\User\AppData\Roaming\Skype\aisylu182\media_messaging\media_cache\^CE1857DB2E36637A386D63EDD17DED9FA8CCF48683A84DFE56^pimgpsh_fullsize_distr.jpg$

Рис. 2.4. Фрагмент MathCAD-документа: система исходных данных задачи замены оборудования

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

$Описание: C:\Users\User\Desktop\123.jpg$

Рис. 2.5. Фрагмент MathCAD-документа: результаты решения задачи замены оборудования

Заключение

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

В процесселвыполнения курсовой работы былилвыполнены следующиелзадачи.

1. Исследовали теоретические основы динамического программирования (в том числе полную постановку, принцип оптимальностия рекурентного уравнения Р.Э. Беллмана)

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

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

4. Осуществить данные задачи в среде MathCad

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

1. Бережная Е.В., Бережной В.И. Математические методы моделирования экономических систем: Учеб. пособие. – М.: Финансы и статистика, 2013. – 368 с.

2. Дьяконов В.П. Энциклопедия Mathcad 2001i и Mathcad 11. – М.: СОЛОН-Пресс, 2012. – 832 с.

3. Исследование операций в экономике: Учебное пособие для вузов / Н.Ш. Кремер, Б.А.Путко, И.М. Тришин, М.Н. Фридман; Под ред. проф. Н.Ш. Кремера. – М.: ЮНИТИ, 2011. – 407 с.

4. Кирьянов Д.В. Mathcad 12. – СПб.: БХВ–Петербург, 2010. – 576 с.

5. Плис А.И., Сливина Н.А. Mathcad 2000. Математический практикум для экономистов и инженеров: Учеб. пособие. – М.: Финансы и статистика, 2000. – 656 с.

6. Рыхлов В.С., Корнев В.В., Курдюмов В.П. Прикладные методы оптимизации. 2-е издание. 2012

7. Херхагер М., Партолль Х. Mathcad 2000: полное руководство: Пер. с нем. – К.: Издательская группа BHV, 2000. – 416 с.

8. Исследование операции в экономике– Кремер. 2012.-210с.

9. Динамическое программирование - Элементы теории игр. Корнее В.В. 2014.- 312с.

10. Содержание 3 - Лекции - методы и модели в технике и экономике, Кулаго В.М. 2011.-204с.

11. Кузнецов А.В. Руководство к решению задач по математическому программированию / А. В. Кузнецов, Н.И. Холод, Л.С. Костевич. - Минск: Вышэйшая школа, 2012. - 240 с.

12. . Карманов В.Г. Математическое программирование / В. Г. Карманов. - Минск: Наука, 2014. - 74 с.

13. Балдин, К. В. Математическое программирование [: Учебник / К. В. Балдин, Н. А. Брызгалов, А. В. Рукосуев; Под общ. ред. д.э.н., проф. К. В. Балдина. - 2-е изд. - М.: Издательско-торговая корпорация «Дашков и К°», 2013. - 220 с.

14. Математические методы: Учебник / Т.Л. Партыка, И.И. Попов. - 2-e изд., испр. и доп. - М.: ФОРУМ: ИНФРА-М, 2007. - 464 с.

15. Основы алгоритмизации и программирования: Учебное пособие / В.Д. Колдаев; Под ред. Л.Г. Гагариной. - М.: ИД ФОРУМ: ИНФРА-М, 2015. - 416 с.

16. Задачи с решениями по высшей математике, теории вероятностей, математической статистике, математическому программированию: учебное пособие для бакалавров / А. С. Шапкин, В. А. Шапкин. - 8-е изд. - М.: Дашков и Ко, 2012. - 432 с.

17. Программирование на языках высокого уровня: Учебное пособие / О.Л. Голицына, И.И. Попов. - М.: Форум, 2008. - 496 с.

18. Программирование на языке высокого уровня. Программир. на языке С++: Уч. пос. / Т.И.Немцова и др.; Под ред. Л.Г.Гагариной - М.: ИД ФОРУМ: ИНФРА-М, 2012. - 512 с.

19. Полубенцева, М. И. С/С++. Процедурное программирование / М.И. Полубенцева. — СПб.: БХВ-Петербург, 2008. — 414 с.

20. Алгоритмизация и программирование : Учебное пособие / С.А. Канцедал. - М.: ИД ФОРУМ: НИЦ Инфра-М, 2013. - 352 с.

Приложение 1. Глоссарий

Геометрическое программирование. Задачи геометрического программирования-- задачи наиболеекплотного расположения некоторых объектов в заданной двумерной иликтрехмерной области. Эти задачи встречаются вкзадачах раскроя материалакдля производстваккаких-то изделий и т.п. Это - еще недостаточнокразработанная областькматематического программированияки имеющиесякалгоритмы в основномкориентированы на сокращениекперебора вариантовкс поиском локальных минимумов.

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

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

Компьютернаякмодель — этокмодель, реализованнаяксредствами программной среды.

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

Математическая модель любойкзадачи линейного программированияквключает в себя:

максимум или минимумкцелевой функции (критерий оптимальности);
систему ограничений в форме линейныхкуравнений и неравенств;
требование неотрицательности переменных.

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

Модель – материальный или мысленнокпредставляемый объект, который в процессе исследованиякзамещает объект-оригинал так, чтокего непосредственное изучение даеткновые знания обкобъекте-оригинале.

Моделировaние – это изучение объектa путемкпостроения икисследования его модели, косуществляемое скопределенной цельюки состоит в зaмене экспериментa с оригинaлом экспериментомкнaкмодели.

Нелинейное программирование. Целеваякфункцияки ограничениякможет быть нелинейнымикфункциями.

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

Решение – всякийкопределенный наборкзависящих параметров.

Целевая функция - функциякв математическомкпрограммировании, ктребующий найти экстремум.

Элементы решения – параметры, ксовокупность которыхкобразует решение

Приложение 2. Листинг программы задачи распределения ресурсов

$Описание: C:\Users\User\AppData\Roaming\Skype\aisylu182\media_messaging\media_cache\^4461A4DE58D83A082B68749099190526C81B80211E1CCE1ADB^pimgpsh_fullsize_distr.jpg$

Продолжение приложения 2.

$Описание: C:\Users\User\AppData\Roaming\Skype\aisylu182\media_messaging\media_cache\^E81B4DBA5924807876E654E341DCED329671E5D576A23BA95D^pimgpsh_fullsize_distr.jpg$

Приложение 3. Листинг программы замены оборудования

$Описание: C:\Users\User\AppData\Roaming\Skype\aisylu182\media_messaging\media_cache\^CE1857DB2E36637A386D63EDD17DED9FA8CCF48683A84DFE56^pimgpsh_fullsize_distr.jpg$

Продолжение приложения 3.

$Описание: C:\Users\User\AppData\Roaming\Skype\aisylu182\media_messaging\media_cache\^E4C919DE0947C61B34AAEE8EC788AF2ADDD2C3457B71F72B0E^pimgpsh_fullsize_distr.jpg$

Продолжение приложения 3.

$Описание: C:\Users\User\AppData\Roaming\Skype\My Skype Received Files\айс3.jpg$

Продолжение приложения 3.

$Описание: C:\Users\User\Desktop\123.jpg$

Скачать материал

Скачать материал "Курсовая работа на тему «Стратегическое планирование деятельности компании методами динамического программирования»"

Как учитель может зарабатывать на Инфоуроке?

Скачать материал

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

6 672 244 материала в базе

Найти материалы

Скачать материал

Другие материалы

docx

Курсовой проект на тему: «Проектирование и разработка базы данных информационной системы школы»

Рейтинг: 4 из 5

19.01.2017
21179
273

docx

Курсовая работа на тему "Разработка информационно-аналитической системы школы"

Рейтинг: 3 из 5

19.01.2017
6142
83

docx

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

19.01.2017
6261
119

docx

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

19.01.2017
583
0

docx

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

19.01.2017
1346
5

docx

Статья на тему "Развитие творческих способностей у детей с нарушением интеллекта в рамках дистанционного образования"

19.01.2017
644
0

Вам будут интересны эти курсы:

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.

Скачать материал
- 19.01.2017 962
- DOCX 1.8 мбайт
- Оцените материал:
Настоящий материал опубликован пользователем Шарипова Айсылу Амировна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт

Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материал
Автор материала

Шарипова Айсылу Амировна
- На сайте: 7 лет и 6 месяцев
- Подписчики: 0
- Всего просмотров: 42695
- Всего материалов: 12