Организация решения задач динамического программирования

Выделяемые средства в млн. рублях

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

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

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

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

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

Одним из основных методов динамического программирования является метод функциональных уравнений Р.Беллмана [1–4], который основывается на использовании его же принципа оптимальности. Принцип состоит в том, что, каковы бы ни были начальное состояние на любом шаге и управление, выбранное на этом шаге, последующие управления должны выбираться оптимальными относительно состояния, к которому придет система в конце данного шага. Использование данного принципа гарантирует, что управление, выбранное на любом шаге, не локально лучше, а лучше с точки зрения процесса в целом.

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

В данной статье решаются три задачи динамического программирования из книги [1].

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

2.1. Оптимальная стратегия замены оборудования.

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

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

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

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

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

Таблица 1

Возраст оборудования (t)	0	1	2	3	…	t-1	t
Этапы (k)	n	n-1	n-2	n-3	…	1	0

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

Функциональные уравнения, основанные на принципе оптимальности, имеют вид:

(1)

(2)

Уравнение (1) описывает одноэтапный процесс, а (2) n- этапный. Оба уравнения состоят из двух частей: первая часть определяет доход, получаемый при сохранении оборудования; вторая часть — доход, получаемый при замене оборудования на новое.

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

Аналогичная интерпретация может быть дана уравнению для одноэтапного процесса. Здесь нет слагаемого вида , так как k принимает значение 1, 2,…, n.

Уравнения (1) и (2) являются рекуррентными соотношениями — функциональными уравнениями, которые позволяют определить величину в зависимости от .

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

Пример 1 [1]. Определить оптимальный цикл замены оборудования при следующих исходных данных: , представленных в табл. 2.

Таблица 2

N	0	1	2	3	4	5	6	7	8	9	10	11	12
f(t)	10	9	8	7	6	5	4	3	2	1	0	0	0

Решение. Уравнения (1) и (2) запишем в следующем виде:

(3)

(4)

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

program zamena_oborudovaniya;

const p=10;

var i,j,k,n:integer; g:array[0..100] of integer; f:array[0..100,0..100] of integer;

function max(a,b:integer):integer;begin if a>b then max:=a else max:=b; end;

begin write('n=?'); readln(n);

for j:=0 to n do

begin write('g[',j,']='); readln(g[j]);end;

for j:=0 to n do f[0,j]:=g[j];

for j:=0 to n do f[1,j]:=max(g[j],-p+g[0]);

for i:=2 to n do for j:=0 to n-1 do

begin f[i,j]:=max(g[j]+f[i-1,j+1],-p+g[0]+f[i-1,1]);end;

for i:=0 to n do begin

for j:=0 to n do

begin write(f[i,j],' '); end;

writeln;end;

end.

Результаты расчетов помещаем в таблицу (табл.3).

Таблица 3

10 9 8 7 6 5 4 3 2 1 0 0 0

19 17 15 13 11 9 9 9 9 9 9 9 0

27 24 21 18 17 17 17 17 17 17 17 17 0

34 30 26 24 24 24 24 24 24 24 24 24 0

40 35 32 31 30 30 30 30 30 30 30 30 0

45 41 39 37 36 35 35 35 35 35 35 35 0

51 48 45 43 41 41 41 41 41 41 41 41 0

58 54 51 48 48 48 48 48 48 48 48 48 0

64 60 56 55 54 54 54 54 54 54 54 54 0

70 65 63 61 60 60 60 60 60 60 60 60 0

75 72 69 67 66 65 65 65 65 65 65 65 0

82 78 75 73 72 72 72 72 72 72 72 72 0

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

2.2.Оптимальное распределение ресурсов.

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

Введем обозначения:-количество ресурсов, выделенных i-му предприятию - функция полезности, в данном случае это величина дохода от использования ресурса x_i, полученного i-м предприятием; -наибольший доход, который можно получить при использовании ресурсов х от первых k различных предприятий.

Сформулированную задачу можно записать в математической форме:

. (5)

Для решения задачи необходимо получить рекуррентные — уравнения Беллмана, связывающее и .

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

Для максимизации суммарного дохода от го и первых способов необходимо выбрать таким образом, чтобы выполнялись рекуррентные — уравнения Беллмана

, (6)

. (7)

Рассмотрим конкретную задачу по распределению средств между фирмами.

Пример 2 [1]. Совет директоров рассматривает предложения для увеличения выпуска однородной продукции на четырех фирмах по наращиванию производственных мощностей.

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

Таблица 4

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

Рекуррентные соотношения для фирм будут иметь вид:

, (8)

. (9)

Решение будем проводить согласно рекуррентным соотношениям (8),(9).

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

{Optimalnoe_raspredeleniye_resursov}

var maxx,i,j,k,l,n,m:integer;

a,b:array[0..100,0..100] of integer;

function max(a,b:integer):integer;

begin if a>b then max:=a else max:=b;end;

begin write('n,m=');readln(n,m);

for i:=1 to m do

for j:=1 to n do

begin write('g[',i,',',j,'] = ');readln(a[i,j]); end;

for i:=0 to m do a[i,0]:=0; for j:=0 to n do a[0,j]:=0;

for i:=0 to 1 do

for j:=0 to n do b[i,j]:=a[i,j];

for k:=2 to m do

for j:=1 to n do

begin maxx:=a[k,0]+b[1,j];

for i:=1 to j do

begin maxx:=max(maxx,a[k,i]+b[k-1,j-i]); end;

b[k,j]:=maxx;

end;

for i:=1 to m do

begin for j:=1 to n do write(b[i,j],' '); writeln;end;

end.

8 16 25 36 44 62

10 20 28 40 48 62

12 22 32 41 52 63

11 23 35 45 55 64

Получены условия управления от 1-го до 4-го этапа. Вернемся от 4-го к 1-му этапу. Максимальный прирост выпуска продукции в 64 млн.р. (миллион рублей.) получен на 4-м этапе как 41 + 23, т. е. 23 млн.р. соответствуют выделению 40 млн.р. четвертой фирме. Согласно 3-му этапу 41 млн. р. получено как 20 + 21, т. е. 21 млн.р. соответствует выделение 40 млн.р. третьей фирме. Согласно 2-этапу 20 млн.р. получено при выделении 40 млн. р. второй фирме. И так, инвестиции в объеме 120 млн.р. целесообразно выделить второй, третьей и четвертой фирмам по 40 млн.р. каждой, при этом прирост продукции будет максимальным и составит 64 млн.р.

2.3. Минимизация затрат на строительство и эксплуатацию предприятий.

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

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

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

Введем обозначения: х-количество распределяемого ресурса, которое можно использовать различными способами; - количество ресурса, используемого по i-му способу -функция расходов, равная, например, величине затрат на производство при использовании ресурса по -му способу; - наименьшие затраты, которые нужно произвести при использовании ресурса х первыми k способами.

Минимизировать общую величину затрат при освоении ресурса x всеми способами:

(10)

Экономический смысл переменных состоит в нахождении количества предприятий, рекомендуемого для строительства в i-м пункте. Для удобства расчетов будем считать, что планируется строительство предприятий одинаковой мощности.

Рассмотрим конкретную задачу по размещению предприятий.

Пример 3 [1]. В трех районах города предприниматель планирует построить пять фирм одинаковой мощности по выпуску хлебобулочных изделий, пользующихся спросом.

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

Таблица 5

1	2	3	4	5
11	18	35	51	76
10	19	34	53	75
9	20	36	54	74

Здесь -функция расходов, определяющая величину затрат на строительство и эксплуатацию в зависимости от количества размещаемых предприятий в i-м районе;

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

Решение. Решим задачу с использованием рекуррентных соотношений по районам (11)

. (12)

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

{Minimizatsiya rasxodov}

var minn,i,j,k,l,n,m:integer;a,b:array[0..100,0..100] of integer;

function min(a,b:integer):integer;begin if a<b then min:=a else min:=b; end;

begin write('n,m=');readln(n,m);

for i:=1 to m do for j:=1 to n do

begin write('g[',i,',',j,'] = ');readln(a[i,j]);end;

for i:=0 to m do a[i,0]:=0; for j:=0 to n do a[0,j]:=0;

for i:=0 to 1 do for j:=0 to n do b[i,j]:=a[i,j];

for k:=2 to m do for j:=1 to n do

begin minn:=a[k,0]+b[1,j];

for i:=1 to j do

begin minn:=min(minn,a[k,i]+b[k-1,j-i]); end;

b[k,j]:=minn;

end;

for i:=1 to m do

begin for j:=1 to n do write(b[i,j],' ');writeln; end;

end.

11 18 35 51 76

10 18 28 37 52

9 18 27 37 46

Минимально возможные затраты при х = 5 составляют 46 млн. р. Определены затраты на строительство предприятий от 1-го до 3-го этапа. Вернемся 3-го к 1-му этапу. Минимальные затраты в 46 млн. р. на 3-м этапе получены как 9 + 37, т. е. 9 млн. р. соответствуют строительству одного предприятия в третьем районе. Согласно 2-му этапу 37 млн. р. получены как 19 + 18, т. е. 19 млн. р. соответствуют строительству двух предприятий во втором районе. Согласно 1-му этапу 18 млн. р. соответствуют строительству двух предприятий в первом районе.

Итак, оптимальная стратегия состоит в строительстве одного предприятия в третьем районе, по два предприятия во втором и первом районах, при этом минимальная стоимость строительства и эксплуатации составит 46 ден. ед.

Литература:

1. Красс М. С., Чупрынов Б. П. Основы математики и ее приложения в экономическом образовании: Учеб. — 2-е изд., испр. — М.: Дело, 2001. — 688 с.

2. Таха Х. А. Введение в исследование операций, — М.: «Вильямс», 2005. — 912 с..

3. Охорзин В. А. Прикладная математика в системе MathCAD. -СПб, Лань.2008.-352 с.

4. Писарук, Н. Н. Исследование операций. — Минск: БГУ, 2014. —289 c.

5. Имомов А., Эргашев Б. С. Организация решения задач исследования операций в MATHCAD,. Молодой учёный, 8 (88), 2015 г.-с.5–9.