korobov

273

274

Для принятия оптимального решения, соответствующего максимальному доходу f1(4)=430 денежных единиц, надо просмотреть все таблицы (7.7) — (7.12) в обратном направлении.

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

r1(0)-u1(0)-c(4)=190-10-130=50.

Из этой же формулы, заключенной в рамку, мы видим, что максимальный доход f1(4) связан с условным максимальным доходом f2(1). Теперь обращаемся к табл. 7.11, из которой мы видим, что f2(1) получено при сохранении нового оборудования. При этом по формуле в рамке мы получим за второй год доход

r1(1)-u1(1)=90-15=75.

Из той же формулы в рамке мы видим, что доход f2(1) связан с условным доходом

f3(2).

Теперь аналогичным образом из табл.7.10 в строке f3(2) видим, что новое оборудование сохраняется. Доход за третий год будет равен

r1(2)-u1(2)=80-15=65.

Доход f3(2) связан с условным максимальным доходом f4(3).

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

r4(0)-u4(0)-с1(3)=140-5-130=5.

Из формулы в рамке для f4(3) видно, что этот доход связан с условным максимальным доходом f5(1).

По табл. 7.8 видно, что при f5(1) новое оборудование сохраняется, доход за пятый год составляет

r4(1)-u4(1)=135-10=125

и f5(l) связан с условным максимальным доходом f6(2).

Наконец, по последней рассматриваемой таблице (7.7) мы видим, что при f6(2) новое оборудование сохраняется и доход за шестой год составит по формуле в рамке

r4(2)-u4(2)=130-20=110

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

50+ 75 + 65+5+125 + 110 = 430.

Мы видим, что суммарный доход действительно совпадает с максимальным доходом за весь период, полученным на последнем шаге (см. табл. 7.12).

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

Усложненная постановка и э.-м. модели задачи оптимизации технического перевооружения предприятий

275

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

Рассмотрим два более сложных варианта.

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

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

Составим функциональные уравнения (рекуррентные соотношения) для первого

усложненного варианта, учитывающего три возможности решения.

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

Для составления функциональных уравнений примем следующие обозначения: R(t1;t2) - стоимость продукции, выработанной за один год машиной возраста t1 лет,

если последний капитальный ремонт ее проводился в начале t2-го года (при этом, время, необходимое для проведения капитального ремонта, считается пренебрежительно малым); S(t1;t2) - ожидаемые годовые эксплуатационные затраты на содержание машины

возраста t1 лет, если последний капитальный ремонт ее проводился в начале t2-го года; Н(t1;t2) - затраты на капитальный ремонт (или модернизации) машины возраста t1

лет, если последний капитальный ремонт был в начале t2- года;

С(t1;t2) - затраты по замене машины возраста t1-лет; они включают в себя затраты на приобретение, установку и наладку машины за вычетом возможной выручки от реализации старой машины;

N - длительность рассматриваемого периода времени в годах.

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

Функции состояния Fk(t1;t2) выражают в этом случае суммарный доход на планируемый период, приведенный к началу k-го периода, если начиная с k-го периода принимаются оптимальные решения, используемая машина имеет возраст t1 лет, а последний капремонт ее проводился в начале t2-го периода (года).

Рекуррентные соотношения для этих функций определения условного максимального дохода при сохранении старой машины, проведении капитального ремонта, установке новой машины в k-й год и во все последующее время до N-го года, и определения соответствующей ему политики отношения к оборудованию имеют следующий вид:

276

Из-за наличия двух параметров состояния (t1 и t2) эта задача значительно труднее чем та, которая нами рассмотрена ранее. Однако, так как максимум вычисляется довольно просто и значения t2 никогда не бывают слишком большими, подобные задачи без особого труда могут решаться на ПЭВМ. При этом, к трем рассмотренным возможностям отношения к оборудованию может быть добавлена четвертая возможность - произвести модернизацию машины.

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

Второй вариант усложненной постановки задачи о замене оборудования заключается в следующем.

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

Пусть функции Rku(j); Sku(j) и Cku(j) имеют ранее введенный смысл в j-й период, а дополнительный индекс u определяет тип машины.

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

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

Пусть вновь Fk(t1;t2) выражает суммарный доход от эксплуатации машины (в течение года и последующий период), приведенный к началу k-го периода, если в конце предыдущего (k-1) периода имелась машина данного возраста и данного типа, а решения, принимаемые в начале k-го периода и во все последующие, были оптимальны.

Если в конце первого периода имеется машина первого типа, то параметр t1 определяет ее возраст, а параметр t2 полагается равным нулю. Наоборот, если имеется машина второго типа, то t2 определяет ее возраст, а t1=0. Отметим, что для этой задачи, если t1 и t2 могут принимать n значений, функция Fn(t1;t2) принимает только 2n-1 значение, а не n2, как в случаях, когда приходится рассматривать все комбинации t1 и t2.

Рекуррентные соотношения для функций состояния (функциональные уравнения) в предположении, что (k-1)-й период закончился и имеется машина возраста t1 первого типа, имеют следующий вид:

Если все расчеты выполняются с помощью ПЭВМ, то без особого труда задача может быть решена с пятью и более типами машин.

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

Рассмотрим еще одну очень важную задачу из области оптимального управления производством, - задачу управления запасами.

277

7.5. Задача управления запасами

Необходимость решения этой задачи в реальных производственных условиях вызвана тем, что зачастую предприятиям выгодно изготовлять в течение некоторого периода времени продукцию в объеме, превышающем спрос в пределах этого периода и хранить излишки, используя их для удовлетворения последующего спроса. Вместе с тем, хранение возникающих при этом запасов связано с определенными затратами. В зависимости от обстоятельств затраты обусловлены такими факторами, как арендная плата за складские помещения, страховые взносы и расходы по содержанию запасов. Эти затраты необходимо учитывать при установлении программы выпуска. Цель предприятия, в данном случае, разработать такую производственную программу, при которой общая сумма затрат на производство запасов была бы минимальной при условии полного и своевременного удовлетворения спроса на продукцию. Рассмотрим решение задачи в простейшей ее постановке.

Введем переменные:

хп — выпуск продукции в течение отрезка п некоторого планового периода; yn— уровень запасов на конец отрезка п.

Спрос на продукцию для отрезка п обозначен Pn. Предполагается, что величины Pn для всех п отображены неотрицательными целыми числами, а все Pn известны. Предполагается также, что для каждого отрезка п затраты зависят от выпуска продукции хп и уровня запасов yn на конец отрезка п. Затраты на отрезке п обозначены сп (хп, yn).

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

Xn = 0, 1, 2, 3... (n=1, 2, ..., N).

Во-вторых, предполагается, что предприятию желателен нулевой уровень запасов на конец отрезка N:

YN = 0.

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

Первое состоит в том, что уровень запасов на конец отрезка n (yn) складывается из уровня запасов на начало отрезка n (zn) и объема выпуска продукции на отрезке n(хп) за вычетом объема реализации (спроса) на этом отрезке:

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

yп =0,1,2,3... (n=1,2, ...,N-1).

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

Состояние системы в начале любого отрезка определяет уровень запасов на начало отрезка. Для принятия решения об объеме выпуска нет необходимости знать, каким образом достигнут начальный уровень. Обозначив затраты, соответствующие оптимальной стратегии в течение п последних отрезков планового периода при начальном уровне запасов. zn - fn(zn), можно составить функциональные уравнения, описывающие поиск решения задачи:

Начальный уровень запасов zn рассматривается как переменная величина, полностью характеризующая состояние системы.

Рассмотрим числовой пример. Мебельная фабрика функционирует таким образом, что в течение одного квартала не может производить более 5 партий мебели. Максимальный объем хранения на складе — 4 партии.

xn = 0,1,...,5 zn = 0,1,...,4

Спрос на мебель, выпускаемую фабрикой, составляет 3 партии в квартал, т. е. Pn =3. Затраты фабрики складываются из затрат на производство с(х) и стоимости содержания запасов, которая является линейной функцией объема запасов, g(y)=2y. В свою очередь, производственные затраты с(х) можно рассматривать как сумму условнопостоянных затрат на операции по переналадке— 13 млн. руб. и пропорциональных затрат — 3 млн. руб. на каждую партию мебели. Значения функции производственных затрат представлены во вспомогательной табл. 7.13.

Определим оптимальную стратегию выпуска продукции и управления ее запасами

на год.

Учитывая исходные данные и формулы (7.66), (7.67), функциональные уравнения задачи будут выглядеть следующим образом:

Ограниченность производственных мощностей не позволяет превысить 5, а ограниченность уравнения запасов на конец отрезка не позволяет превысить (7 -zn).

Начнем рассматривать процесс с последнего квартала года, обозначив его как I

этап.

I этап. Значения f1(zn) представлены в табл. 7.14. Они получены из следующих соображений. Так как на конец года предприятие не желает иметь запасы продукции, а спрос на продукцию в каждом квартале равен 3, то запасы на начало последнего (четвертого) квартала могут меняться от 0 до 3. Соответственно, если запас на начало квартала (z1) равен 0, то, чтобы удовлетворить спрос, предприятие должно произвести 3 партии мебели (x1 = 3). Если запас был равен 1 партии (z1=l), то объем производства

составит 2 партии (x1' = 2) и т. д. Суммарные затраты для каждого из возможных

состояний определятся в соответствии с формулой (7.68) только значениями с (х), (см. табл. 7.13), т. к. ввиду отсутствия запасов на конец квартала, затраты на хранение равны

0(2z1+x1-P1)=0).

Т а б л. 7.14

279

Задача управления запасами (n=1)

для каждого возможного значения начального уровня запасов zn и по одному столбцу для каждого значения выпуска продукции хп. Каждое из представленных в клетке таблицы чисел представляет собой сумму затрат для рассматриваемого квартала и оптимальных затрат для всех последующих кварталов. Клетки, соответствующие некоторым недопустимым сочетаниям zn и хп, выделяют из рассмотрения. Например, если z2=1, то спрос, равный 3 партиям, удастся удовлетворить только при условии х2≥2. Если z2 = 4, то x2≤2, иначе нарушится условие нулевогоуровня запасов наконец года,т.к.P1 =P2=3 и т. п.

Для клеток, участвующих в решении, расчеты проводятся в соответствии с формулой (7.68). Например, при z2 = 0 и х2 = 3 затраты на производство равны 22 (см. табл. 7.13), затраты на хранение: 2 (0 + 3 -3)=0. Так как запасы на конец третьего квартала (начало четвертого квартала) составят: 0 + 3 - 3 = 0, то из табл. 7.14 находим f1(0)=22. В итоге, для такого сочетания z2 и х2 получим величину суммарных затрат: 22 + 0 + 22=44.

Еще пример. При z2=1 и x2 = 4 затраты на производство:

280

с(4)=25,затратынахранение:2(1+4-3)=4,f1(1+4-3)= f1(2)=16.Суммарныезатратысоставят:25+4+16=45. Для каждого фиксированного z2 значение функции f2(z2) представляет собой минимальную величину из всех значений суммарных затрат в клетках данной строки, а х2

—соответствующий объем производства продукции.

III этап. Данные, полученные в результате расчетов на основе выражения (7.68) для второго квартала представлены в табл. 7.16.

В рассмотрении вновь не участвуют некоторые сочетания z3 и xз, т. к. x3 может принимать значения лишь в соответствии с неравенствами (7.70). Величины суммарных затрат в клетках таблицы получены так же, как и на предыдущем этапе.

Например, при z3=3 и х3=4 производственные затраты: с(4)=25, затраты на хранение: 2(3 + 4 - 3)=8, величина f2 (3 + 4 - 3), т. е. f2(4) получена на II этапе и равна 21. Суммарные затраты составят: 25 + 8 + 21 = 54. В каждой строке выбраны минимальные из всех значений суммарных затрат. Они составляют величину f3(z3) для каждого z3.

IV этап. Аналогично II и III этапам получены значения f4(z4) (см. табл. 7.17). Отметим, что для z4 = 0 оптимальным являются два значения выпуска: 3 партии и

4 партии.