Библиографическое описание:

Имомов А. И., Бокиев Э. Р. Организация решения задач динамического программирования // Молодой ученый. — 2015. — №12. — С. 1-6.

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

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

 

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

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-му предприятию - функция полезности, в данном случае это величина дохода от использования ресурса xi, полученного i-м предприятием; -наибольший доход, который можно получить при использовании ресурсов х от первых k различных предприятий.

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

.                                                         (5)

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

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

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

 ,                                                                                                (6)

.                                                                  (7)

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

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

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

Таблица 4

Фирмы

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

20

40

60

80

100

120

Фирма№ 1

8

16

25

36

44

62

Фирма№ 2

10

20

28

40

48

62

Фирма№ 3

12

21

27

38

50

63

Фирма№ 4

11

23

30

37

51

63

 

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

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

,                                                                                                (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.

Обсуждение

Социальные комментарии Cackle