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

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

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

"Вероятность неисчерпания" - это вероятность того, что спрос не превысит уровень запаса.

В однопериодной модели оптимальным  считается такой уровень запаса, при котором "вероятность неисчерпания" равна соотношению:

P =             ,

(1.5.1)

где P - "вероятность неисчерпания запаса";

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

C_e - издержки, связанные с избыточным запасом, на единицу продукции.

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

 

Рисунок 1.5.1 – "Вероятность неисчерпания" и оптимальный объем партии в однопериодной модели

 

Если фактический спрос  превышает q^*, то возникает нехватка, отсюда C_s - на правом конце распределения. Аналогично, если спрос меньше, чем q^*, то возникает избыток, отсюда C_e - на левой стороне распределения. Когда    С_s = С_e, оптимальный уровень запаса находится ровно посередине между двумя концами распределения. Если же один показатель больше другого, то q^* для "поддержания равновесия" располагается ближе к большему показателю.

Подход, применяемый при  нормальном распределении спроса, аналогичен описанному.

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

 

Глава II. Метод динамического программирования в задаче управления запасами и его реализация.

2.1 Метод динамического программирования.

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

Показатель эффективности  задачи в целом обозначим через W, а показатели эффективности на отдельных шагах—через φ_i, i=1..m. Если W обладает свойством аддитивности, т.е.

                                                      m

                                                W=∑ φ_i ,                                             (2.1.1)

                                                      i=1

Переменная Xi, от которой  зависят выигрыши на i-м шаге и, следовательно, выигрыш в целом, называется шаговым  управлением, i=1..m.

Управлением процесса в целом (x) называется последовательность шаговых  управлений (вектор управлений) x=(x₁, x₂,…, x_i,…, x_m).

Оптимальное управление x—это значение управления x, при котором  значение W(x*) является максимальным (или  минимальным, если требуется уменьшить  проигрыш).  

W*=W(x*)=max{W(x)}, x € X,                          (2.1.2) 

 где X—область допустимых управлений.

Оптимальное управление x* определяется последовательностью оптимальных шаговых управлений x*=(x₁*, x₂*,…, x_i*,…, x_m*).  

В основе метода динамического  программирования лежит принцип  оптимальности Беллмана, формулирующийся  следующим образом: управление на каждом шаге надо выбрать так, чтобы оптимальной  была сумма выигрышей на всех оставшихся до конца процесса шагах, включая выигрыш на данном шаге. Объясняется это правило так: при решении задачи динамического программирования на каждом шаге выбирается управление, которое должно привести к оптимальному выигрышу. Если считать все шаги независимыми друг от друга, то оптимальным шаговым управлением будет то управление, которое приносит максимальный выигрыш именно на данном шаге. Но, например, при покупке новой техники в замен устаревшей на ее приобретение затрачиваются определенные средства. Поэтому прибыль от ее эксплуатации вначале может быть небольшой. Однако в следующие годы новая техника будет приносить большую прибыль. И наоборот, если руководитель примет решение оставить старую технику для получения прибыли в текущем году, то в дальнейшем это приведет к значительным убыткам. Данный пример демонстрирует следующий факт: в многошаговых процессах все шаги зависят друг от друга, и, следовательно, управление на каждом конкретном шаге надо выбирать с учетом его будущих воздействий на этот процесс.

Другой момент, который  следует учитывать при выборе управления на данном шаге,—это возможные  варианты окончания предыдущего  шага. Эти варианты определяют состояние  процесса. Например, при определении  количества средств, вкладываемых в  предприятие в 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. Определение множества шаговых управлений x_i, i=1..m и налагаемых на них ограничений, т.е. области допустимых управлений X.
4. Определение выигрыша   φ(s, x_i),  который принесет на i-м шаге управление xi, если система перед этим находилась в состоянии s.
5. Определение состояния s’, в которое переходит система из состояния s под влиянием управления x_i :   s’=f_i(s, x_i,), где f_i—функция перехода на i-м шаге из состояния s в состояние s’.
6. Составление уравнения, определяющего условный оптимальный выигрыш                                                                                                              на последнем шаге, для состояния s моделируемого процесса

                                                       W_m(S) = max{φ_m(s, x_m)}.                                    (2.1.3) 

                                                                  x_m€X

7. Составление основного функционального уравнения динамического                           программирования, определяющего условный оптимальный выигрыш для                             данного состояния s с i-го шага и до конца процесса через уже известный                           оптимальный выигрыш с (i+1)-го шага и до конца:

                                                Wi(S) = max{φi(s, xi)+W_i+1(fi(s’, xi))}.                     (2.1.4)    

                                                            x_m€X                                                                                                                               

В уравнении (2.1.4) в уже известную функцию W_i+1(s), характеризующую условный оптимальный выигрыш с (i+1)-го шага до конца процесса, вместо состояния s подставлено новое состояние s’=f_i(s, x_i), в которое система переходит на i-м шаге под влиянием управления x_i.

После того как выполнены  пункты 1—7, и математическая модель составлена, приступают к ее расчету. Укажем основные этапы решения задачи динамического программирования.

1. Определение множества возможных состояний S_m для последнего шага.
2. Проведение условной оптимизации для каждого состояния s, принадлежащей S_m на последнем m-м шаге по формуле (2.1.3) и определение условного оптимального управления x(s), s принадлежит S_m.
3. Определение множества возможных состояний S_i для i-го шага, i=2, 3,…m-1.
4. Проведение условной оптимизации для i-го шага, i=2, 3,…m-1 для каждого состояния  s, принадлежащей S_i,, по формуле (2.1.4) и определение условного оптимального управления x_i(s), s принадлежит S_i, i=2, 3,…m-1.
5. Определение начального состояния системы s1, оптимального выигрыша W1(S1) и оптимального управления x₁(S₁) по формуле (2.1.4) при i=1. Это есть оптимальный выигрыш для всей задачи W*=W₁(x₁*).
6. Проведение безусловной оптимизации управления. Для проведения безусловной оптимизации необходимо найденное на первом шаге оптимальное управление x₁*=x₁(s₁) подставить в формулу (2.1.2) и определить следующее состояние системы s₂=f₂(s₁, x₁). Для измененного состояния найти оптимальное управление x₂*=x₂(s₂), подставить в формулу (2.1.2) и т.д. Для i-го состояния si найти s_i+1=f_i+1(s_i,x_i*) и x*_i+1(s_i+1) и т.д.

 

2.2 Метод динамического  программирования в задаче управления  запасами и его реализация

Определим основные компоненты:

• этап - календарный период деятельности предприятия, j=        ;
• y_j - объем запасов в конце j периода (состояние);
• h_j - затраты на хранение единицы товара в j-ом периоде
• x_j  - планируемый объем заказа в j-ом периоде (управление);
• c(x_j) – затраты на доставку товара в j-ом периоде
• d_j  - объём реализованной продукции в  j-ом периоде;
• с(x_j,y_j-1) – затраты на j-ом этапе, связанные с хранением запасов и заказом новой продукции (локальный доход )
• f_j – общие затраты за j периодов (суммарный доход)

 Введем целевую функцию:

 (2.2.1)

 

И ограничения:

• ограничение на удовлетворение спроса

d_j £ i_j-1 + x_j - 56 ,    j  =                 (2.2.2)

• установление объема запаса в конце j-го периода

y_j = y_j-1 + x_j – d_j ,   j =                  (2.2.3)

 Функциональное уравнение Беллмана для такой задачи:

f_j(y_j-1)=min{c(x_j)+h_j*(y_j-1+x_j-d_j)+f_j+1(y_j-1+x_j-d_j)},   ,   j =            (2.2.4)  

Тогда на последнем шаге принятия решения уравнение Беллмана (2.2.4) примет вид:

f₃₉(y₃₈)=min{c(x₃₉)+h₃₉*(y₃₈+x₃₉-d₃₉)}  (2.2.5)

Далее решаем уравнение для  следующих этапов по формуле 2.2.4.

Входные данные – спрос  на каждом этапе и затраты на доставку и хранение единицы лекарственного средства Linex (Таблицы 2.2.1 и 2.2.2):

Таблица 2.2.1. Спрос на лекарственное  средство Linex

t	d	t	d
1	15	21	53
2	63	22	32
3	31	23	25
4	74	24	28
5	16	25	39
6	45	26	26
7	50	27	45
8	101	28	64
9	71	29	44
10	109	30	68
11	79	31	119
12	14	32	130
13	77	33	118
14	34	34	74
15	37	35	43
16	42	36	45
17	25	37	53
18	40	38	50
19	57	39	61
20	72