для студентов экономических специальностей

Камский государственный политехнический институт

ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МОДЕЛИ и МЕТОДЫ

Динамическое программирование

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

для студентов экономических специальностей

Набережные Челны

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

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

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

Составители: Смирнов Ю.Н., Шибанова Е.В.

Набережные Челны: Изд-во КамПИ, 2004, 38 с.

Рецензент: доцент, кандидат физико-математических наук Углов А.Н.

Печатается по решению научно-методического совета Камского государственного политехнического института от 24.03.03 г.

Камский государственный

политехнический институт,

Содержание

Введение. 4

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

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

3. Общая схема применения метода ДП.. 9

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

5. Задача стратегического планирования. 15

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

7. Указания к выполнению курсовой работы.. 29

8. Задания для самостоятельной работы.. 32

Литература. 38

Введение

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

К задачам, решаемым методами динамического программирования, относятся:

ü стратегическое планирование предприятия на несколько лет;

ü распределение дефицитных капитальных вложе­ний между возможными направлениями их использова­ния (между предприятиями, проектами и т.д.);

ü разработка правил управления запасами, устанавливающими мо­мент пополнения запасов и размер пополняющего заказа;

ü календарное планирования производства;

ü календарное планирование текущего и капиталь­ного ремонта оборудования и его замены, основных производственных фондов и т. п.

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

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

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

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

Пусть - управление, переводящее систему S из состояния s₀ в состояние . Обозначим через состояние сис­темы после k -го шага управления. Получаем последовательность состояний , которую изобразим кружками (рис.1).

Показатель эффективности рассматриваемой управляемой опе­рации - целевая функция - зависит от начального состояния и управления: . На каждом шаге определяется объединённый (агрегированный) показатель эффективности на множестве всевозможных управлений.

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

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

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

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

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

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

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

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

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

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

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

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

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

Уравнения Беллмана.

Нахождение оптимального решения управляемого процесса можно произвести на основе рекуррентных соотношений Беллмана. Пусть - показатель эффективности k – ого шага при всевозможных управлениях . Выделяют обратную и прямую схемы Беллмана.

Схема нахождения оптимального решения по обратной схеме.

На каждом шаге любого состояния системы решение нужно выбирать " с оглядкой", так как этот выбор влияет на по­следующее состояние и дальнейший процесс управления, зави­сящий от . Это следует из принципа оптимальности.

Но есть один шаг, последний, который можно для любого со­стояния планировать локально оптимально, исходя только из соображений этого шага.

Рассмотрим n -й шаг: - состояние системы к началу n -го шага, - конечное состояние, - управление на n -м шаге, - целевая функция (выигрыш) n -го шага.

Показатель эффективности n – ого шага

Агрегированный показатель эффективности (n-1) – ого шага .

Агрегированный показатель эффективности первого шага .

В результате будут найдены следующие последовательности значений:

Схема нахождения оптимального решения по прямой схеме.

Показатель эффективности первого шага

Агрегированный показатель эффективности второго шага .

Агрегированный показатель эффективности k – ого шага .

Агрегированный показатель эффективности всего процесса управления (n-ого шага)

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

3. Общая схема применения метода ДП

Построение модели ДП и применение метода ДП решения сводится к следующим моментам:

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

2. Определяют параметры состояния и переменные управления на каждом шаге.

3. Записывают уравнения состояний.

4. Вводят целевые функции k-го шага и суммарную целевую функцию.

5. Вводят в рассмотрение условные максимумы (минимумы) и условное оптимальное управление на k -м шаге: (в случае использования обратной схемы Беллмана);

6. Записывают основные для вычислительной схемы ДП урав­нения Беллмана для и .

7. Решают последовательно уравнения Беллмана (условная оп­тимизация) и получают две последовательности функций: и .

8. После выполнения условной оптимизации получают опти­мальное решение для конкретного начального состояния s₀:

a) и по цепочке

b) оптимальное управление: .

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

Рассмотрим предложенную выше схему на конкретной задаче распределения средств между предприятиями.

Планируется деятельность 4 промышленных предприятий на очередной год. Необходимо между ними распределить 400 единиц ограниченного ресурса (Q). Каждое предприятие i в зависимости от объема выделенных средств x получает дополнительный доход f_i(x). Объемы получаемых дополнительных доходов в зависимости от выделенных ресурсов x представлены в таблице 1.

Таблица 1

Необходимо определить оптимальное распределение средств, обеспечивающее максимальную эффективность (доход) деятельности всех предприятий.

Показатель эффективности каждого предприятия может определяться в результате решения задачи использования ресурсов (планирования производства), математическая модель которой имеет вид:

Целевая функция при ограничениях:

-?

Условные обозначения:

- прибыль от реализации единицы продукции каждого вида;

- объем закупаемых ресурсов;

- складские запасы ресурсов;

- план производства продукции каждого вида;

- нормы затрат ресурсов для производства единицы продукции каждого вида;

- цены на ресурсы;

- объем выделенных ресурсов;

и - соответственно минимальный (обязательства предприятия) и максимальный объем (ёмкость рынка) выпуска продукции;

k – номер предприятия.

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

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

Предполагается, что:

1. дополнительный доход f(х) не зависит от вложения средств в другие предприятия;

2. дополнительный доход f(х) каждого предприятия выражается в одних ус­ловных единицах;

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

При решении задачи распределения ресурсов между проектами методами динамического программирования следует учесть взаимозаменяемость ресурсов при реализации проектов (т.е. могут использоваться одни и те же сырьевые ресурсы при реализации проектов).

Задача распределения ресурсов между предприятиями является задачей динамического программирования. Её решение содержит следующие этапы:

1. интервал изменения выделяемых средств разбивается на элементарные отрезки;

2. для заданных значений выделяемых средств определяются показатели эффективности для всех предприятий;

3. по обратной (прямой) схеме используются уравнения Беллмана;

4. в обратной (прямой) последовательности, начиная от находят оптимальные значения выделяемых средств .

Рассмотрим обратную схему Беллмана. Рекуррентные соотношения имеют вид:

Распределение ресурсов будем производить с точностью 80 единиц.

Согласно обратной схеме Беллмана показатель эффективности 4-ого шага:

;

- показатель эффективности деятельности 1 предприятия.

- объединённый показатель эффективности деятельности 2 предприятий.

Произведем вычисления значений функции и представим их в таблице 2.

Таблица 2.

Объединённый показатель эффективности деятельности 3 предприятий - . Произведем вычисления значений функции и представим их в таблице 2.

Объединённый показатель эффективности деятельности 4 предприятий - . Произведем вычисления значений функции и представим их в таблице 2.

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

Таким образом, в результате решения задачи распределения средств между предприятиями получили, что для обеспечения максимальной эффективности деятельности (прибыли) всех предприятий, равной 203 у.е., первому и второму предприятиям согласно оптимальному распределению следует не выделять ресурсов, третьему предприятию необходимо выделить 240 единиц ресурса, четвертому – 260 единиц.

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

Предложенная схема применения методов динамического программирования также применима при решении задачи стратегического планирования предприятия.

Рассматривается задача планирования производства предприятия в течение T периодов (лет). Предприятию на планируемый период выделяют дополнительные средства. Предполагается, что технология производства в планируемом периоде не меняется. Необходимо определить план производства на каждый год, объёмы закупаемых ресурсов, оптимальный план распределения финансовых средств P по годам деятельности для получения максимального дополнительного дохода.

Введем обозначения:

- объем закупаемых ресурсов;

- складские запасы ресурсов в первый год деятельности;

- план производства продукции каждого вида;

- нормы затрат ресурсов для производства единицы продукции каждого вида ();

- цены на ресурсы;

- объем выделенных ресурсов;

и - соответственно минимальный (обязательства предприятия) и максимальный объем (ёмкость рынка) производства продукции;

k – номер периода (года) деятельности предприятия.

Задача стратегического планирования состоит из 2 этапов:

1. Находят показатели эффективности каждого периода в зависимости от объема выделенных ресурсов Q (в результате решения задачи линейного программирования – задачи использования ресурсов).

Математическая модель:

2. Определяют оптимальное распределение всех финансов P по периодам (годам) деятельности (методом динамического программирования).

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

Если P распределяется с точностью , то , можно сформировать следующую таблицу (таблица 3):

Таблица 3

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

Замечание: Финансовые результаты первого года деятельности должны повлиять на финансовые результаты в последующие годы. Для этого в соотношение добавляется величина , где - норма затрат финансовых результатов на производство, т.е. .

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

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

Поэтому в определенный момент времени возникает необходимость (экономическая целесообразность) замены старого оборудования на новое. Критерием оптимальности являются, как пра­вило, либо прибыль от эксплуатации оборудования (задача мак­симизации), либо суммарные затраты на эксплуатацию в течение планируемого периода (задача минимизации).

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

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

Основная характеристика оборудования - параметр состоя­ния - его возраст t.

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

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

- период планирования;

- ликвидная стоимость оборудования ();

- стоимость содержания оборудования ();

- первоначальная стоимость оборудования ().

Уравнения состояний системы зависят от управления:

В самом деле, если к k – ому шагу , то при сохранении оборудования через год возраст оборудования увеличится на 1. Если оборудование заменяется новым , то это означает, что к началу k – ого шага её возраст t=0, а после года эксплуатации t=1, т.е. .

Показатель эффективности k - ого шага:

.

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

Тогда уравнения Беллмана будут иметь вид:

Геометрическое решение задачи замены оборудования. Схема расчетов при решении задачи замены оборудования может быть представлена в виде двухкоординатной диаграммы (графа). На оси абсцисс будем откладывать номер шага k, на оси ординат — возраст оборудования t. Точка (k-1, t) на плоскости соответствует началу k -го года эксплуатации оборудования возраста t лет. Перемещение на графике в зависимости от принятого управления на k -м шаге показано на рисунке.

Над каждым отрезком, соединяющим точки (k-1; t) и (k; t+1), записываются соответствующие управлению затраты на сохранение оборудования, а над отрезком, соединяющим точки (k-1; t) и (k; 1), запишем затраты, соответствующие замене оборудования - управлению . Таким образом, будут размечены все отрезки, соеди­няющие точки на графике, соответствующие переходам из любого состояния в состояние .

Пример.

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

Данные о затратах на содержание оборудования и ликвидной стоимости приведены в таблице 4.

Таблица 4.

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

Проведем на размеченном графе условную оптимизацию.

5 шаг. В состояниях (5, t) оборудование продается, условный оптимальный доход от продажи равен ликвидной стоимости j(t), но поскольку целевая функция связана с затратами, то в кружках точек (5, t) ставим величину дохода со знаком «-».

4 шаг.

Состояние (4, 1).

Таким образом, если система к последнему шагу находилась в точке (4, 1), то следует идти в точку (5, 1) (укажем это направление пунктирной линией), т.к. затраты в этом случае будут минимальными (8000+600-6000=2600< 800).

Состояние (4, 2).

Состояние (4, 3).

Состояние (4, 4).

3 шаг.

Состояние (3, 1).

В данном случае, находясь в точке (3, 1), оптимально идти как в точку (4, 2), так и в точку (4, 1) (в обоих случаях затраты будут одинаковыми (-1600), возникает альтернативность решения).

Состояние (3, 2).

Состояние (3, 3).

2 шаг.

Состояние (2, 1).

Состояние (2, 2).

1 шаг.

Состояние (1, 1).

В данном случае, находясь в точке (1, 1), оптимально идти как в точку (2, 1), так и в точку (2, 2) (в обоих случаях затраты будут одинаковыми (2800), возникает альтернативность решения).

После проведения условной оптимизации в точке (0, 0) получим минимальные затраты на эксплуатацию оборудования в течение 5 лет с последующей продажей: руб.

Строим оптимальные траектории, перемещаясь из точки (0, 0) по пунктирным линиям в конечное состояние .

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

1. (0, 0); (1, 1); (2, 2); (3, 1); (4, 2); (5, 1) - ;

2. (0, 0); (1, 1); (2, 1); (3, 2); (4, 1); (5, 2) -

3. (0, 0); (1, 1); (2, 2); (3, 1); (4, 1); (5, 2) - .

Согласно первой стратегии эксплуатации оборудования следует заменить в начале 3-его и 5-ого годов, согласно второй – в начале 2-ого и 4-ого годов, согласно третьей - в начале 3-его и 4-ого годов.

Замечания:

1. Стоимость приобретения оборудование зависит от года в силу изменения рыночных цен;

2. Затраты на содержание оборудования зависят не только от возраста оборудования, но и от года обслуживания;

3. Ликвидная стоимость оборудования зависит от стоимости нового оборудования в момент продажи;

4. Приобретаемое оборудование может иметь иные технологические характеристики, чем заменяемое оборудование, поэтому после замены оборудования изменяются экономические показатели производства (прибыль, рентабельность и др.).

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

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

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

1. при сохранении оборудования (значения норм затрат ресурсов ) и

2. при замене оборудования (нормы затрат равны ). При этом выполняется условие .

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

При замене оборудования модель принимает вид:

,

где p(k) – стоимость оборудования в период t;

r (k) – затраты на эксплуатацию оборудования в период t.

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

При этом здесь, как и в задаче замены оборудования с критерием минимизации затрат, в состояниях системы, соответствующих последнему шагу, оборудование продается, и условный оптимальный доход от продажи равен ликвидной стоимости j(t). Но в отличие от неё целевая функция связана уже не с затратами, а с прибылью, поэтому в кружках точек последнего шага (n, t) ставим величину дохода со знаком «+» (в задаче замены оборудования с критерием минимизации затрат на эксплуатацию необходимо ставить «-»).

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

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

Уравнения Беллмана (в случае обратной схемы) будут иметь вид:

7. Указания к выполнению курсовой работы

Темы и постановка курсовых работ:

1. Распределение ресурсов между предприятиями

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

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

Замечание: Вместо предприятий можно рассматривать проекты.

2. Стратегическое финансовое и производственное планирования

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

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

3. Замена оборудования

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

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

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

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

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

Содержание курсовой работы:

Введение

1. Постановка задачи

2. Математическая модель задачи

3. Теоретическая часть (методы решения):

a) Линейное программирование

b) Динамическое программирование

4. Практическая часть (расчеты)

Заключение (результаты решений, выводы, рекомендации)

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

8. Задания для самостоятельной работы

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

Для увеличения объёмов выпуска пользующейся повышенным спросом продукции, изготавливаемой 4 предприятиями города, выделены средства в размере 100 млн. руб. Использование i -ым предприятием x млн. руб. из указанных средств обеспечивает прирост выпуска продукции, определяемый значением f_i(x).

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

Варианты индивидуальных заданий для решения задачи распределения ресурсов между предприятиями представлены в таблице 5.

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

Оборудование эксплуатируется в течение 5 лет, после чего продается. В начале каждого года принимается решение сохранить оборудование или заменить его новым. Известны первоначальная стоимость нового оборудования p(t)= p₀ =const, затраты на содержание оборудования r(t ) и ликвидная стоимость оборудования j(t ). Необходимо определить оптимальную стратегию эксплуатации оборудования, обеспечивающую минимальные суммарные затраты на эксплуатацию в течение 5 лет. Исходные данные для решения задачи замены оборудования (по вариантам):

Вариант 1.

Вариант 2.

Вариант 3.

Вариант 4.

Вариант 5.

Вариант 6.

Вариант 7.

Вариант 8.

Вариант 9.

Вариант 10.

Вариант 11.

Вариант 12.

Вариант 13.

Вариант 14.

Вариант 15.

Вариант 16.

Вариант 17.

Вариант 18.

Вариант 19.

Вариант 20.