1.2 Математическая постановка задачи
2 Алгоритмизация решения задачи управления запасами
2.2 Описание метода динамического программирования. 3
2.3 Применение метода динамического программирования к задаче оптимального управления запасами
Пример разработанной программы (Pascal)
Научно-технический прогресс создает предпосылки для
повышения качества управления за счет использования вычислительной техники,
математических методов, теории управления, автоматизации управления . Все это
нашло конкретную реализацию в автоматизированных
системах управления .
Управление
заключается в сборе информации, ее переработке и выводе управляющей информации
для изменения хода процесса .
Основным
путем повышения качества управления является автоматизация управления
производством, при которой данные задачи решаются средствами вычислительной
техники.
Одной из задач управления предприятием является
задача определения оптимального плана производства изделий, обеспечивающего
заданный спрос продукции при минимизации затрат на производство и хранение
продукции. Это задача оптимального управления запасами. Теория управления
запасами позволяет определять уровни запасов материалов, полуфабрикатов,
производственных мощностей и других ресурсов в зависимости от спроса на них.
Проблема управления запасами является одной из наиболее важных в
организационном правлении. Но, как
правило, не существует типовых решений – условия на каждом предприятии или
фирме уникальны и включают множество ограничений и различных особенностей. С
этим связаны и проблемы, возникающие при разработке математической модели и
определении оптимальной стратегии управления запасами.
В данной работе сделана попытка реализовать решение задачи управления запасами методом
динамического программирования.
Предприятие
разрабатывает календарный план выпуска изделий на плановый период, состоящий из
нескольких этапов. Текущая деятельность предприятия характеризуется следующими
параметрами:
1) длительность
одного этапа планового периода;
2)
выпуск продукции в течение этапа;
3)
спрос на продукцию в конце этапа;
4)
уровень запасов изделий на конец этапа;
5)
максимально возможный выпуск изделий на одном этапе;
6)
максимально возможный уровень запасов на одном этапе;
Известны
затраты на каждом этапе планового периода, связанные с выпуском изделий
и хранением запасов изделий. Так же известны затраты на формирование
начального запаса.
Необходимо
определить план производства изделий, чтобы обоеспечить заданный спрос продукции при минимальных
затратах.
Введем следующие обозначения:
N – число календарных этапов из которых состоит плановый период;
При этом каждый n-й этап (n=1,N) характеризуется параметрами:
in-1 – запас, оставшийся после окончания n-1-го этапа;
хn – объем производства предприятия на n-м этапе;
dn – величина спроса на продукцию предприятия на n-м этапе;
xmax – максимальный объем производства на одном этапе;
imax – максимальный объем запасов на одном этапе;
Сn(xn,in-1) – затраты на n-м этапе функционирования, связанные с выпуском хn деталей и хранением in-1 запасов деталей.
Тогда критерий оптимизации имеет вид:
N
F=∑ Сn(xn,in-1) ® min (12.1)
n=1
при
ограничениях:
1) ограничение на удовлетворение спроса на каждом этапе:
dn £ in-1 + xn , n=1,N ; (12.2)
2) установление объема запаса в конце n-го периода:
in = in-1 + xn
– dn , n=1,N , xn
= 0,xmax , in
= 0,imax ; (12.3)
В изложенной задаче необходимо учитывать изменение моделируемого процесса во времени и влияние времени на критерий оптимальности. Для решения таких задач используется метод динамического планирования (динамическое программирование).
Динамическое программирование—это метод оптимизации многошаговых или многоэтапных процессов, критерий эффективности которых обладает свойством аддитивности (т.е. общий доход процесса равен сумме локальных доходов на отдельных этапах). В задачах динамического программирования критерий эффективности называется доходом. Данные процессы управляемые, и от правильного выбора управления зависит величина дохода.
Показатель эффективности задачи в целом обозначим через W, а показатели эффективности на отдельных шагах—через φi, i=1..m. Если W обладает свойством аддитивности, т.е.
W=∑ φi , (22.1)
Переменная Xi, от которой зависят выигрыши на i-м шаге и, следовательно, выигрыш в целом, называется шаговым управлением, i=1..m.
Управлением процесса в целом (x) называется последовательность шаговых управлений (вектор управлений) x=(x1, x2,…, xi,…, xm).
Оптимальное управление x—это значение управления x, при котором значение W(x*) является максимальным (или минимальным, если требуется уменьшить проигрыш).
W*=W(x*)=max{W(x)}, x € X, (22.2)
где X—область допустимых управлений.
Оптимальное
управление x* определяется последовательностью оптимальных шаговых управлений
x*=(x2*, x2*,…, xi*,…, xm*).
В
основе метода динамического программирования лежит принцип оптимальности
Беллмана, формулирующийся следующим образом: управление на каждом шаге надо
выбрать так, чтобы оптимальной была сумма выигрышей на всех оставшихся до конца
процесса шагах, включая выигрыш на данном шаге. Объясняется это правило так:
при решении задачи динамического программирования на каждом шаге выбирается
управление, которое должно привести к оптимальному выигрышу. Если считать все
шаги независимыми друг от друга, то оптимальным шаговым управлением будет то
управление, которое приносит максимальный выигрыш именно на данном шаге. Но,
например, при покупке новой техники в замен устаревшей на ее приобретение
затрачиваются определенные средства. Поэтому прибыль от ее эксплуатации вначале
может быть небольшой. Однако в следующие годы новая техника будет приносить
большую прибыль. И наоборот, если руководитель примет решение оставить старую
технику для получения прибыли в текущем году, то в дальнейшем это приведет к
значительным убыткам. Данный пример демонстрирует следующий факт: в
многошаговых процессах все шаги зависят друг от друга, и, следовательно,
управление на каждом конкретном шаге надо выбирать с учетом его будущих
воздействий на этот процесс.
Другой
момент, который следует учитывать при выборе управления на данном шаге,—это
возможные варианты окончания предыдущего шага. Эти варианты определяют
состояние процесса. Например, при определении количества средств, вкладываемых
в предприятие в i-м году, необходимо знать, какая прибыль получена в предыдущем
(i-1)-м году. Таким образом, при выборе шагового управления необходимо
учитывать:
1)
возможные
исходы предыдущего шага;
2)
влияние
управления на все оставшиеся до конца процесса шаги.
В
задачах динамического программирования первый пункт учитывают, делая на каждом
шаге условные предположения о возможных вариантах окончания предыдущего шага и
приводя для каждого из вариантов условную оптимизацию. Выполнение второго
пункта обеспечивается тем, что в задачах динамического программирования
условная оптимизация проводится от конца процесса к началу. Сперва
оптимизируется последний m-й шаг, на котором не надо учитывать возможные
воздействия выбранного управления xm на все последующие шаги, так как эти шаги
просто отсутствуют. Делая предположения об условиях окончания (m-1)- го шага,
делая предположения об исходах окончания (m-2)-го шага и определяя условное
оптимальное управление на (m-1)-м шаге, приносящее оптимальный выигрыш на двух
последних шагах—(m-1)-м и m-м. Так же действуют на всех остальных шагах до
первого. На первом шаге, как правило, не надо делать условных предположений,
так как состояние системы перед первым шагом обычно известно. Для этого
состояния выбирают оптимальное шаговое управление, обеспечивающее оптимальный
выигрыш на первом и всех последующих шагах. Это управление является безусловным
оптимальным управлением на первом шаге и, зная его, определяются оптимальное
значение выигрыша и безусловные оптимальные управления на всех шагах.
Понятия
этапа(шага), состояния, управления, дохода(выигрыша) целиком зависит от
предметной ориентации исследуемой системы. Для организационно-экономической
системы (к которой и относится наша задача)
эти понятия имеют вид:
1)
этап –
некий календарный интервал (месяц, квартал, год и т.д.);
2)
состояние –
наличие финансовых/производственных средств, свободной продукции и т. п.;
3)
управление
– возможные варианты использования имеющихся средств;
4)
локальный
доход – прибыль (или затраты) получаемая на отдельном этапе;
5)
суммарный
доход – прибыль (или затраты) получаемая по окончании планового периода.
Дополнительно введем следующие условные обозначения:
s—состояние
процесса;
Si—множество возможных состояний процесса перед i-м шагом;
Wi—выигрыш с i-го шага до конца процесса, i=1..m.
Можно определить следующие основные этапы составления
математической модели задачи динамического программирования.
1)
Разбиение
задачи на шаги (этапы). Шаг не должен быть слишком мелким, чтобы не проводить
лишних расчетов и не должен быть слишком большим, усложняющим процесс шаговой
оптимизации.
2)
Выбор
переменных, характеризующих состояние s моделируемого процесса перед каждым
шагом, и выявление налагаемых на них ограничений. В качестве таких переменных
следует брать факторы, представляющие интерес для исследователя, например
годовую прибыль при планировании деятельности предприятия.
3)
Определение
множества шаговых управлений xi, i=1..m и налагаемых на них ограничений, т.е.
области допустимых управлений X.
4)
Определение
выигрыша φ(s, xi), который принесет на i-м шаге управление xi,
если система перед этим находилась в состоянии s.
5)
Определение
состояния s’, в которое переходит система из состояния s под
влиянием
управления xi : s’=fi(s, xi,), где
fi—функция перехода на i-м шаге из состояния s в состояние s’.
6) Составление
уравнения, определяющего условный оптимальный выигрыш на
последнем шаге, для состояния s моделируемого процесса
Wm(S)=max{φm(s, xm)}. (2.2.3)
xm€X
7)
Составление основного функционального уравнения динамического программирования,
определяющего условный оптимальный выигрыш для данного состояния s с i-го шага и до конца
процесса через уже известный оптимальный выигрыш с (i+1)-го шага и до
конца:
Wi(S)=max{φi(s,
xi)+Wi=1(fi(s, xi))}.
(2.2.4)
xm€X
В
уравнении (22.4) в уже известную функцию Wi+1(s), характеризующую условный
оптимальный выигрыш с (i+1)-го шага до конца процесса, вместо состояния s
подставлено новое состояние s’=fi(s, xi), в которое система переходит на i-м
шаге под влиянием управления xi.
После
того как выполнены пункты 1—7, и математическая модель составлена, приступают к
ее расчету. Укажем основные этапы решения задачи динамического
программирования.
1)
Определение
множества возможных состояний Sm для последнего шага.
2)
Проведение
условной оптимизации для каждого состояния s, принадлежащей Sm на последнем m-м
шаге по формуле (22.3) и определение условного оптимального управления x(s), s
принадлежит Sm.
3)
Определение
множества возможных состояний Si для i-го шага, i=2, 3,…m-1.
4)
Проведение
условной оптимизации для i-го шага, i=2, 3,…m-1 для каждого состояния s, принадлежащей Si,, по формуле (22.4) и
определение условного оптимального управления xi(s), s принадлежит Si, i=2,
3,…m-1.
5)
Определение
начального состояния системы s1, оптимального выигрыша W1(S1) и оптимального
управления x1(S1) по формуле (22.4) при i=1. Это есть оптимальный выигрыш для
всей задачи W*=W1(x1*).
6)
Проведение
безусловной оптимизации управления. Для проведения безусловной оптимизации
необходимо найденное на первом шаге оптимальное управление x1*=x1(s1)
подставить в формулу (22.2) и определить следующее состояние системы s2=f2(s1,
x1). Для измененного состояния найти оптимальное управление x2*=x2(s2),
подставить в формулу (22.21) и т.д. Для i-го состояния si найти
si+1=fi+1(si,xi*) и x*i+1(si+1) и т.д.
Определим
основные компоненты:
1) этап - календарный период деятельности предприятия, n=1,N;
2) состояние – объем запасов in в конце n периода;
3) управление – планируемый объем производства xn на n-м периоде;
4) локальный доход – затраты на n-м этапе, связанные с хранением запасов и производством новой продукции Сn(xn,in-1);
5) оператор перехода – устанавливает связь между объемом запасов в конце n – 1-го и n-го этапов: in = in-1 + xn – dn .
Введем функцию:
fn(in) =
min∑ Сn(xn,in-1) (2.3.1) .
Функциональное уравнение Беллмана для такой задачи:
fn(in) = min(fn(in-1)
+ Сn(xn,in-1)). (2.3.2)
Если
Сn(xn,in-1) = cn(xn)
+ h*in-1
(2.3.4),
где cn(xn) – затраты на производство продукции на n-ном этапе в xn объеме;
h*in-1 – затраты на хранение продукции на n-ном этапе в объеме i0.
Известно c0(x0) - затраты на формирование начального запаса.
Тогда на шаге 1 принятия решения уравнение Беллмана (2.3.2) примет вид:
f1(i1) = min(f1(i0) + С1(x1,i0)) = min(f1(i0) + c0(x0)
+ h*i0) (2.3.5)
все переменные в уравнении известны, а значит его можно решить.
На шаге n уравнение (23.2) имеет вид:
fn(in) = min(fn(in-1)
+ cn(x) + h*in-1) (2.3.6)
Для получения оптимального решения нам необходимо разработать алгоритм решения уравнения Беллмана (2.3.6) на произвольном шаге принятия решения n.
Для этого целесообразно воспользоваться 2-мя таблицами. Заполнение таблицы 1 проводится так: столбцы – величина запаса с предыдущего шага, строки – объем производства на текущем этапе. Число столбцов ограничивается imax, а число строк xmax. Клетка таблицы делится на 2 части. В одной части записываются значения состояния в конце текущего этапа (in = in-1 + xn – dn ). Если in < 0 ,то это недопустимое состояние, клетка вычеркивается из рассмотрения. Во второй части клетки записывается значение функции
fn(in) = cn-1(xn-1)
+ cn(xn) + h*in-1 (2.4.1)
Среди допустимых клеток находятся клетки с одинаковыми значениями состояний, и выбирается клетка, для которой функция fn(in) минимальна, для нее фиксируется оптимальный объем производства. Эти результаты записываются в таблицу 2.
Такие шаги повторяются N раз.
Для нахождения оптимальных объемов производства xn и оптимальных уровней запасов in производится решение задачи в обратном порядке. На последнем этапе (n = N) из таблицы 2 выбирается xn и in , соответствующие оптимальной (минимальной) функции затрат fn(in). На этапах n < N из таблицы 2 выбираются строки для которых xn и in такие, что бы |dn – xn+1 | = in . Обратное решение задачи производится до n = 1 этапа.
1) Черноморов Г. А. Теория принятия решений – Южно-Российский Государственный Технический университет. Новочеркасск: редакция журнала "Изв. Вузов. Электромеханика", 2002.
2) Павлов В.Н. Математическая экономика – Новосибирск, ЭФ НГУ 2000.
3) Домбовский В.В., Чаусова Е.В. Математическая модель управления запасами при случайном сезонном спросе и ненадежных поставщиках.
4) Динамическое программирование http://www.karelia.ru/psu/Faculties/Forest/courses/decision/chap5_a.htm .
5) ::Bolshe.ru:: Методология и методы принятия решения. http://www.bolshe.ru/unit/109/books/297/s/1 .
type
TData = record
N: integer; //кол-во интервалов планирования
d: array of integer; //спрос
Xmax: integer; //производственные мощности
Imax: integer; //предел запасов
C1: integer; //конст1 (формир. начальн. запасов)
C2: integer; //2
C3:
integer; //3
h: integer; //зататы на хран
end;
type
TTab1 =
record
f: integer;
i: integer;
end;
type
TTab2 =
record
i: integer;
x: integer;
f: integer;
end;
procedure TFormMain.ButtonRestartClick(Sender:
TObject);
var f: textfile;
i,x,step,ii: integer;
str: string;
begin
///предполагается,
что исходные данные занесены в текстовый файл 001.TMP
AssignFile (f,'001.tmp');
Reset(f);
ReadLn(f, Data.N);
ReadLn(f, Data.H);
ReadLn(f, Data.Imax);
ReadLn(f, Data.Xmax);
ReadLn(f, Data.C1);
ReadLn(f, Data.C2);
ReadLn(f, Data.C3);
SetLength (Data.D, Data.N);
for i:=0 to Data.N-1 do ReadLn(f, Data.D[i]);
CloseFile(f);
SetLength (Tab1,Data.Xmax+1,Data.Imax+1);
SetLength (Tab2,Data.N+1,Data.Imax+1);
///результаты
расчетов будем выводить в Memo список
MemoMain.Lines.Clear;
///выведем
исходные данные:
MemoMain.Lines.Add('******************************************');
MemoMain.Lines.Add('Исходные
данные: ');
MemoMain.Lines.Add('');
MemoMain.Lines.Add('Количество
интервалов планирования: '
+floattostr(Data.N));
MemoMain.Lines.Add('Ограничение
на производственные мощности: '
+inttostr(Data.Xmax));
MemoMain.Lines.Add('Предельный
уровень запасов: '
+inttostr(Data.Imax));
MemoMain.Lines.Add('Величина
спроса: ');
MemoMain.Lines.Add('№
этапа | спрос ');
for i:=0 to Data.N-1 do
MemoMain.Lines.Add(inttostr(i)+' '+inttostr(Data.D[i]));
MemoMain.Lines.Add('Затраты
на формирование начального спроса: ');
MemoMain.Lines.Add(floattostr(Data.C1)+'*i');
MemoMain.Lines.Add('Затраты
на производство и хранение: ');
MemoMain.Lines.Add(floattostr(Data.C2)+'+'+
floattostr(Data.C3)+'*Xn+'+floattostr(Data.H)+'*i');
MemoMain.Lines.Add('******************************************');
///проверяем
корректность входных данных
for i:=0 to Data.N-1 do
if
((Data.Xmax+Data.Imax)<=Data.d[i]) then
begin
MemoMain.Lines.Add('Спрос превышает
производственные возможности.');
MemoMain.Lines.Add('Расчет
невозможен.');
Exit;
end;
///Формируем
начальный запас
for i:=0 to Data.Imax do
Tab2[0,i].f:=Data.C1*i;
///Пошли шагать
for step:=0 to Data.N-1 do
begin
MemoMain.Lines.Add(' ');
MemoMain.Lines.Add(' ');
MemoMain.Lines.Add('Этап № '+inttostr(step));
///Заполняем первую таблицу
MemoMain.Lines.Add('Таблица '+inttostr(step)+'.1');
MemoMain.Lines.Add('');
for i:=0 to Data.Imax do
MemoMain.Lines.Text:=MemoMain.Lines.Text+' i'+(inttostr(i));
for x:=0 to Data.Xmax do
begin
MemoMain.Lines.Add('x'+inttostr(x)+ '
');
for i:=0 to
Data.Imax do
begin
Tab1[x,i].i:=i+x-Data.d[step];
if
(Tab1[x,i].i<=-1) or (Tab1[x,i].i>Data.Imax) then
begin
MemoMain.Lines.Text:=MemoMain.Lines.Text+('****** ');
continue;
end
else
if x>0
then
Tab1[x,i].f:=Tab2[step,i].f+Data.C2+Data.C3*x+Data.h*i
else
Tab1[x,i].f:=Tab2[step,i].f+Data.h*i;
MemoMain.Lines.Text:=MemoMain.Lines.Text+(inttostr(Tab1[x,i].f)+'/'
+inttostr(Tab1[x,i].i)+' ');
end;
///end i tabl1
end; ///end x
tabl1
///Заполняем
вторую таблицу
MemoMain.Lines.Add(' ');
MemoMain.Lines.Add('Таблица '+inttostr(step)+'.2');
for i:=0 to Data.Imax do
Tab2[step+1,i].f:=10000000;
for ii:=0 to Data.Imax do
for x:=0 to Data.Xmax do
begin
for i:=0 to
Data.Imax do
begin
if
(ii=Tab1[x,i].i) then
if
Tab1[x,i].f<=Tab2[step+1,ii].f then
begin
Tab2[step+1,ii].f:=Tab1[x,i].f;
Tab2[step+1,ii].i:=ii;
Tab2[step+1,ii].x:=x;
end;
end;
end;
for i:=0 to Data.Imax do
MemoMain.Lines.Add('i='+inttostr(Tab2[step+1,i].i)+' '+
'x='+inttostr(Tab2[step+1,i].x)+' '+
'f='+inttostr(Tab2[step+1,i].f)+' ');
end;
///end step
///Обратный
ход, во время его выводим результат
MemoMain.Lines.Add('');
MemoMain.Lines.Add('');
MemoMain.Lines.Add('Оптимальное
решение: ');
MemoMain.Lines.Add('Общие затраты (F) = '+inttostr(ii));
for i:=0 to Data.Imax do
if
Tab2[Data.N,i].f=ii then
begin
MemoMain.Lines.Add('На
'+inttostr(Data.N)+' этапе'+':
запас
(i) = '+
inttostr(Tab2[Data.N,i].i)+', '+
' производство (x) = '+inttostr(Tab2[Data.N,i].x)+';');
x:=Tab2[Data.N,i].i;
end;
for ii:=Data.N-1 downto 1 do
begin
for i:=0
to Data.Imax do
begin
if
power(Data.d[ii]-Tab2[ii+1,x].x,2)=power(Tab2[ii,i].i,2)
then
begin
MemoMain.Lines.Add('На
'+inttostr(ii)+
' этапе'+': запас (i) = '+
inttostr(Tab2[ii,i].i)+',
'+
' производство (x) =
'+inttostr(Tab2[ii,i].x)+';');
x:=Tab2[ii,i].i;
end;
end;
end;
Tab1:=nil;
Tab2:=nil;
end;
(с)
МорокЪ 2004