Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Динамическое программирование
Постановка задачи
Динамическое программирование — один из разделов оптимального программирования, в котором процесс принятия решения и управления может быть разбит на отдельные этапы (шаги).
Экономический процесс является управляемым, если можно влиять на ход его развития. Под управлением понимается совокупность решений, принимаемых на каждом этапе для влияния на ход развития процесса. Например, выпуск продукции предприятием — управляемый процесс. Совокупность решений, принимаемых в начале года (квартала и т.д.) по обеспечению предприятия сырьем, замене оборудования, финансированию и т.д., является управлением. Необходимо организовать выпуск продукции так, чтобы принятые решения на отдельных этапах способствовали получению максимально возможного объема продукции или прибыли.
Динамическое программирование позволяет свести одну сложную задачу со многими переменными ко многим задачам с малым числом переменных. Это значительно сокращает объем вычислений и ускоряет процесс принятия управленческого решения. Свойства степенных рядов. Ряды Тейлора и Маклорена
В отличие от линейного программирования, в котором симплексный метод является универсальным методом решения, в динамическом программировании такого универсального метода не существует. Одним из основных методов динамического программирования является метод рекуррентных соотношений, который основывается на использовании принципа оптимальности, pазработанного американским математиком Р. Беллманом. Принцип состоит в том, что, каковы бы ни были начальное состояние на любом шаге и управление, выбранное на этом шаге, последующие управления должны выбираться оптимальными относительно состояния, к которому придет система в конце данного шага. Использование данного принципа гарантирует, что управление, выбранное на любом шаге, не локально лучше, а лучше с точки зрения процесса в целом.
В некоторых задачах, решаемых методом динамического программирования, процесс управления разбивается на шаги. При распределении на несколько лет ресурсов деятельности предприятия шагом целесообразно считать временной период; при распределении средств между предприятиями — номер очередного предприятия. В других задачах разбиение на шаги вводится искусственно. Например, непрерывный управляемый процесс можно рассматривать как дискретный, условно разбив его на временные отрезки (шаги). Исходя из условий каждой конкретной задачи, длину шага выбирают таким образом, чтобы на каждом шаге получить простую задачу оптимизации и обеспечить требуемую точность вычислений.
Некоторые экономические задачи, решаемые методами динамического программирования
Оптимальная стратегия замены оборудования
Одной из важных экономических проблем является определение оптимальной стратегии в замене старых станков, агрегатов, машин на новые.
Старение оборудования включает его физический и моральный износ, в результате чего растут производственные затраты по выпуску продукции на старом оборудовании, увеличиваются затраты на его ремонт и обслуживание, снижаются производительность и ликвидная стоимость.
Наступает время, когда старое оборудование выгоднее продать, заменить новым, чем эксплуатировать ценой больших затрат; причем его можно заменить новым оборудованием того же вида или новым, более совершенным.
Оптимальная стратегия замены оборудования состоит в определении оптимальных сроков замены. Критерием оптимальности при этом может служить прибыль от эксплуатации оборудования, которую следует оптимизировать, или суммарные затраты на эксплуатацию в течение рассматриваемого промежутка времени, подлежащие минимизации.
Введем обозначения: r(t) — стоимость продукции, производимой за один год на единице оборудования возраста t лет;
u(t) — ежегодные затраты на обслуживание оборудования возраста t лет;
s(t) — остаточная стоимость оборудования возраста t лет;
Р — покупная цена оборудования.
Рассмотрим период N лет, в пределах которого требуется определить оптимальный цикл замены оборудования.
Обозначим через fN(t) максимальный доход, получаемый от оборудования возраста t лет за оставшиеся N лет цикла использования оборудования при условии оптимальной стратегии.
Возраст оборудования отсчитывается в направлении течения процесса. Так, t = 0 соответствует случаю использования нового оборудования. Временные же стадии процесса нумеруются в обратном направлении по отношению к ходу процесса. Так, N = 1 относится к одной временной стадии, остающейся до завершения процесса, а N = N — к началу процесса (рис. 29.1).
На каждом этапе N-стадийного процесса должно быть принято решение о сохранении или замене оборудования. Выбранный вариант должен обеспечивать получение максимальной прибыли.
Функциональные уравнения, основанные на принципе оптимальности, имеют вид:
Уравнение (29.1) описывает N-стадийный процесс, а (29.2) — одностадийный. Оба уравнения состоят из двух частей: верхняя строка определяет доход, получаемый при сохранении оборудования; нижняя — доход, получаемый при замене оборудования и продолжении процесса работы на новом оборудовании.
В уравнении (29.1) функция r(t) — u(t) есть разность между стоимостью произведенной продукции и эксплуатационными издержками на N-й стадии процесса.
Функция fN-1 (t + 1) характеризует суммарную прибыль от (N — 1) оставшихся стадий для оборудования, возраст которого в начале осуществления этих стадий составляет (t + 1) лет.
Нижняя строка (29.1) характеризуется следующим образом: функция s(t) — Р представляет чистые издержки по замене оборудования, возраст которого t лет.
Функция r(0) выражает доход, получаемый от нового оборудования возраста 0 лет. Предполагается, что переход от работы на оборудовании возраста t лет к работе на новом оборудовании совершается мгновенно, т.е. период замены старого оборудования и переход на работу на новом оборудовании укладываются в одну и ту же стадию.
Последняя функция fN-1 в (29.1) представляет собой доход от оставшихся N — 1 стадий, до начала осуществления которых возраст оборудования составляет один год.
Аналогичная интерпретация может быть дана уравнению для одностадийного процесса. Здесь нет слагаемого вида f0(t + 1), так как N принимает значение 1, 2,..., N. Равенство f0(t) = 0 следует из определения функции fN(t).
Уравнения (29.1) и (29.2) являются рекуррентными соотношениями, которые позволяют определить величину fN(t) в зависимости от fN-1(t + 1). Структура этих уравнений показывает, что при переходе от одной стадии процесса к следующей возраст оборудования увеличивается с t до (t + 1) лет, а число оставшихся стадий уменьшается с N до (N — 1).
Расчет начинают с использования уравнения (29.1). Уравнения (29.1) и (29.2) позволяют оценить варианты замены и сохранения оборудования, с тем чтобы принять тот из них, который предполагает больший доход. Эти соотношения дают возможность не только выбрать линию поведения при решении вопроса о сохранении или замене оборудования, но и определить прибыль, получаемую при принятии каждого из этих решений.
Пример 1. Определить оптимальный цикл замены оборудования при следующих исходных данных: Р = 10, S(t) = 0, f(t) = r(t) — u(t), представленных в табл. 29.1.
Решение. Уравнения (29.1) и (29.2) запишем в следующем виде:
Для N = 1
Для N = 2
Вычисления продолжаем до тех пор, пока не будет выполнено условие f1(1) > f2(2), т.е. в данный момент оборудование необходимо заменить, так как величина прибыли, получаемая в результате замены оборудования, больше, чем в случае использования старого. Результаты расчетов помещаем в таблицу, момент замены отмечаем звездочкой, после чего дальнейшие вычисления по строчке прекращаем (табл. 29.2).
Можно не решать каждый раз уравнение (29.3), а вычисления проводить в таблице. Например, вычислим f4(t):
Дальнейшие расчеты для f4(t) прекращаем, так как f4(4) = 23 < f3(1) = 24.
По результатам вычислений и по линии, разграничивающей области решений сохранения и замены оборудования, находим оптимальный цикл замены оборудования. Для данной задачи он составляет 4 года.
Ответ. Для получения максимальной прибыли от использования оборудования в двенадцатиэтапном процессе оптимальный цикл состоит в замене оборудования через каждые 4 года.
Рассмотрим вначале метод динамического программирования для решения следующей задачи. Совет директоров фирмы рассматривает предложения относительно прироста производственных мощностей для увеличения выпуска однородной продукции на четырех предприятиях, принадлежащих фирме. Для модернизации предприятий предложено инвестировать средства в объеме 250 усл.ден.ед. с дискретностью 50 усл.ден.ед. Прирост выпуска продукции зависит от выделенной суммы ,а его значения даны предприятиями и содержатся в таблице. Найти распределение инвестиций между предприятиями, обеспечивающее фирме максимальный прирост продукции, при чем на одно предприятие можно осуществить только одну инвестицию.
|
Инвестиции, усл.ден.ед. |
Прирост выпуска продукции, усл.ден.ед. |
|||
|
g1(x) |
g2(x) |
g3(x) |
g4(x) |
|
|
50 |
8 |
10 |
12 |
11 |
|
100 |
16 |
20 |
21 |
23 |
|
150 |
25 |
28 |
27 |
30 |
|
200 |
36 |
40 |
38 |
37 |
|
250 |
44 |
48 |
50 |
51 |
Запишем уравнение Беллмана для метода обратной прогонки и разобьем решение задачи на 4 этапа.
Этап 4. F5(C5)=0
|
C4 |
F4(C4)=g4(x4) |
оптимум |
||||||
|
X4=0 |
X4=50 |
X4=100 |
X4=150 |
X4=200 |
X4=250 |
F4(C4) |
X4* |
|
|
0 |
0 |
- |
- |
- |
- |
- |
0 |
0 |
|
50 |
- |
11 |
- |
- |
- |
- |
11 |
50 |
|
100 |
- |
- |
23 |
- |
- |
- |
23 |
100 |
|
150 |
- |
- |
- |
30 |
- |
- |
30 |
150 |
|
200 |
- |
- |
- |
- |
37 |
- |
37 |
200 |
|
250 |
- |
- |
- |
- |
- |
51 |
51 |
250 |
Этап 3.
|
C3 |
F3(C3)=g3(x3)+ F4(C3-x3) |
оптимум |
||||||
|
X3=0 |
X3=50 |
X3=100 |
X3=150 |
X3=200 |
X3=250 |
F3(C3) |
X3* |
|
|
0 |
0+0=0 |
- |
- |
- |
- |
- |
0 |
0 |
|
50 |
0+11=11 |
12+0=12 |
- |
- |
- |
- |
12 |
50 |
|
100 |
0+23=23 |
12+11=23 |
21+0=21 |
- |
- |
- |
23 |
0,50 |
|
150 |
0+30=30 |
12+23=35 |
21+11=33 |
27+0=27 |
- |
- |
35 |
50 |
|
200 |
0+37=37 |
12+30=42 |
21+23=44 |
27+11=38 |
38+0=38 |
- |
44 |
100 |
|
250 |
0+51=51 |
12+37=49 |
21+30=51 |
27+23=50 |
38+11=49 |
50+0=50 |
51 |
0,100 |
Этап 2.
|
C2 |
F2(C2)=g2(x2)+ F3(C2-x2) |
оптимум |
||||||
|
X2=0 |
X2=50 |
X2=100 |
X2=150 |
X2=200 |
X2=250 |
F2(C2) |
X2* |
|
|
0 |
0+0=0 |
- |
- |
- |
- |
- |
0 |
0 |
|
50 |
0+12=12 |
10+0=10 |
- |
- |
- |
- |
12 |
0 |
|
100 |
0+23=23 |
10+12=22 |
20+0=20 |
- |
- |
- |
23 |
0 |
|
150 |
0+35=35 |
10+23=33 |
20+12=32 |
28+0=28 |
- |
- |
35 |
0 |
|
200 |
0+44=44 |
10+35=45 |
20+23=43 |
28+12=40 |
40+0=40 |
- |
45 |
50 |
|
250 |
0+51=51 |
10+44=54 |
20+35=55 |
28+23=51 |
40+12=52 |
48+0=48 |
55 |
100 |
Этап 1.
|
C1 |
F1(C1)=g1(x1)+ F2(C1-x1) |
оптимум |
||||||
|
X1=0 |
X1=50 |
X1=100 |
X1=150 |
X1=200 |
X1=250 |
F1(C1) |
X1* |
|
|
0 |
0+0=0 |
- |
- |
- |
- |
- |
0 |
0 |
|
50 |
0+12=12 |
8+0=8 |
- |
- |
- |
- |
12 |
0 |
|
100 |
0+23=23 |
8+12=20 |
16+0=16 |
- |
- |
- |
23 |
0 |
|
150 |
0+35=35 |
8+23=31 |
16+12=28 |
25+0=25 |
- |
- |
35 |
0 |
|
200 |
0+45=45 |
8+35=43 |
16+23=39 |
25+12=37 |
36+0=36 |
- |
45 |
0 |
|
250 |
0+55=55 |
8+45=53 |
16+35=51 |
25+23=48 |
36+12=48 |
44+0=44 |
55 |
0 |
Из таблицы этапа 1 находим оптимальное значение целевой функции при распределении между предприятиями всей суммы С1=250: F1(250)=55. При этом первому предприятию должно быть выделено x1*=0 ден.ед. Тогда остальным трем предприятиям остается распределить С2=С1-x1*=250-0=250 ден.ед. Из таблицы этапа 2 выделению суммы С2=250 соответствует значение x2*=100, тогда С3=С2- x2*=250-100=150 ден.ед. Из таблицы этапа 3 выделению суммы С3=150 соответствует значение x3*=50, тогда С4=С3- x3*=150-50=100 ден.ед. На последнем этапе 4 определяем x4*=100.
Таким образом, оптимальный план инвестирования предприятий:
X*= (0,100,50,100), который обеспечит максимальный доход, равный
F(250)=g1(0)+g2(100)+g3(50)+g4(100)=0+20+12+23=55 усл.ден.ед.
Вторая задача имеет похожую постановку, но функции дохода являются нелинейными. Для модернизации трех предприятий совет директоров инвестирует средства в объеме 150 денежных единиц. Пусть приросты выпуска продукции, а значит и общего дохода, зависят от выделенной суммы для i-го предприятия и выражаются соответствующими квадратичными зависимостями:
Найдем методом множителей Лагранжа распределение инвестиций между предприятиями, которое обеспечит фирме максимальный прирост продукции.
Перед тем, как составить функцию Лагранжа, запишем функцию суммарного дохода предприятий:
Тогда функция Лагранжа имеет вид:
Точку условного экстремума определим из необходимого условия экстремума функции многих переменных:
Таким образом, координаты искомой точки экстремума имеют вид: .
Отметим, что решение аналогичных практических задач данными методами является наглядной иллюстрацией методов оптимизации непрерывных и дискретных функций дохода предприятия. Отметим также, что данные примеры позволят будущим специалистам в дальнейшем правильно анализировать экономико-математические производственные модели и подбирать соответствующий эффективный метод для их решения.
PAGE 5