Задача о замене оборудования

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

Основная характеристика оборудования — параметр состоя­ния — его возраст Г

При составлении динамической модели замены процесс заме­ны рассматривают как «-шаговый, разбивая весь период эксплуа­тации на я шагов. Возможное управление на каждом шаге харак­теризуется качественными признаками, например, Xе (сохранить оборудование), X3 (заменить) и Хр (сделать ремонт).

Рассмотрим конкретный пример.

^ 12.3. Оборудование эксплуатируется в течение 5 лет, после этого продается. В начале каждого года можно принять решение сохра­нить оборудование или заменить его новым. Стоимость нового оборудования р0=4000 руб.[34] После / лет эксплуатации (1^ Г^5) оборудование можно продать за g ((]—рй2~( рублей (ликвидная стоимость). Затраты на содержание в течение года зависят от воз­раста г оборудования и равны г (/)=600(Н-1). Определить опти­мальную стратегию эксплуатации оборудования, чтобы суммар­ные затраты с учетом начальной покупки и заключительной про­дажи были минимальны.

Решение. Способ деления управления на шаги естествен­ный, по годам, п — 5. Параметр состояния — возраст машины — 5о=0 — машина новая в начале первого года эксплуа­

тации.

Уравнения состояний зависят от управления:

* ' А> ССЛИ Л Ь ~ 21 , /1 'Э 'Э'Ъч

/ „з , (12.22)

В самом деле, если к к-му шагу т*- 1=7, то при сохранении ма­шины (Хк~Хс) через год возраст машины увеличится на 1. Если машина заменяется новой (Хк=Х3), то это означает, что к началу к-то шага ее возраст ? = 0, а после года эксплуатации / = 1, т.е. 5*=1.

Показатель эффективности &-го шага:

/кНХь /)=|460о0°4000)Г'еСЛИ ХУ = ХХ*' *=1’ 2’ 3’ 4- (12-23) [4600 - 4000 ■ 2 , если Хк = Х\

(При Xе затраты только на эксплуатацию машины возраста ?, при X3 машина продается (-4000-2'0, покупается новая (4000) и эксплуатируется в течение первого года (600), общие затраты рав­ны (-4000-2~'+4000+600)).

Пусть 2'к (?) — условные оптимальные затраты на эксплуата­цию машины, начиная с к-то шага до конца, при условии, что к началу к-то шага машина имеет возраст I лет. Запишем для функ­ций Х'к (0 уравнения Веллмана (12.5) и (12.8), заменив задачу максимизации на задачу минимизации:

2\ = тт{600(/ +1} ~ 400°' 2"(,+1) ’ если 2

5 [4600 - 4000 ■ 2 - 4000 ■ 2'( }, если Х5=Х\

Величина 4000-2_(н"О — стоимость машины возраста / лет (по. условию машина после 5 лет эксплуатации продается).

2\ = пйп{600(/ +1} + + если дг*=лг‘» (12.25)

[4600-4000-2-' + гк+1(1), если

к=4, 3, 2, 1.

Из определения функций Z*k (() следует

(0).

Дадим геометрическое решение этой задачи. На оси абсцисс будем откладывать номер шага к, на оси ординат — возраст / ма­шины. Точка (к— 1, /) на плоскости соответствует началу к-го года эксплуатации машины возраста {лет. Перемещение на графике в зависимости от принятого управления на к-м шаге показано на рис. 12.7.

Состояние начала эксплуатации машины соответствует точке $о (0; 0), конец — точкам 5 (6; /). Любая траектория, переводящая точку $(&— 1; 0 из в £ , состоит из отрезков — шагов, соответст­вующих годам эксплуатации.

Над каждым отрезком, соединяющим точки (к-1; /) и (к\ /+1), запишем соответствующие управлению Xе затраты, найденные из (12.23): 600(М-1), а над отрезком, соединяющим точки (к-1; /) и {к\ /), запишем затраты, соответствующие управлению Xі, т.е. 4600-4000-2~(. Таким образом мы разметим все отрезки, соеди­няющие точки на графике, соответствующие переходам из любого состояния в состояние я* (рис. 12.8). Например, над отрезка­ми, соединяющими точки (к] 2) и (£+1; 3), стоит число 1800[35], что соответствует затратам на эксплуатацию в течение каждого года

Рис. 12.8

Машины возраста г = 2 лет, а над отрезками, соединяющими (к\ 2) и (£+1; 1), стоит число 3600 — это сумма затрат на покупку ма­шины и эксплуатацию новой машины в течение года без “затрат” (выручки) за проданную машину возраста / лет. Следует учесть, что 0 ^ ^ к.

Проведем на размеченном графе состояний (см. рис. 12.8) ус­ловную оптимизацию.

V шаг. Начальные состояния — точки (4; /), конечные (5; /). В состояниях (5; 0 машина продается, условный оптимальный доход от продажи равен 4000-2"', но поскольку целевая функция связана с затратами, то в кружках точек (5; І) поставим величину дохода со знаком минус.

Анализируем, как можно попасть из каждого начального со­стояния в конечное на V шаге.

Состояние (4; 1). Из него можно попасть в состояние (5; 2), за­тратив на эксплуатацию машины 1200 и выручив затем от прода­жи 1000, т.е. суммарные затраты равны 200, и в состояние (5; 1) с затратами 2600-2000=600. Значит, если к последнему шагу систе­ма находилась в точке (4; 1), то следует идти в точку (5; 2) (укажем это направление двойной стрелкой), а неизбежные ми­нимальные затраты, соответствующие этому переходу, равны 200 (поместим эту величину (1)=200 в кружке точки (4; 1).

Состояние (4; 2). Из него можно попасть в точку (5; 3) с затра­тами 1800-500=1300 и в точку (5; 1) с затратами 3600-2000=1600. Выбираем первое управление, отмечаем его двойной стрелкой, а

(2)= 1300 проставляем в кружке точки (4; 2).

Рассуждая таким же образом для каждой точки предпоследнего шага, мы найдем для любого исхода IV шага оптимальное управ­ление на V шаге, отметим его на рис. 12.8 двойной стрелкой. Да­лее планируем IV шаг, анализируя каждое состояние, в котором может оказаться система в конце III шага с учетом оптимального продолжения до конца процесса, т.е. решаем для всех 0 ^ ґ ^ 4 при к—4 уравнения (12.22). Например, если начало IV шага соот­ветствует состоянию (3; 1), то при управлении Xе система перехо­дит в точку (4; 2), затраты на этом шаге 1200, а суммарные затра­ты за два последних шага равны 1200+1300=2500. При управлении X3 затраты за два шага равны 2600+200=2800. Выбираем мини­мальные затраты 2500, ставим их в кружок точки (3; 1), а соответ­ствующие управления на этом шаге помечаем дво’йной стрелкой,

270___________________________________________ '_____ Глава 12;

I

ведущей из состояния (3; 1), в состояние (4; 2). Так поступаем для каждого состояния (3; Г) {см. рис. 12.8).

Продолжая условную оптимизацию III, II и I шагов, мы полу­чим на рис. 12.8 следующую ситуацию: из каждой точки (состояния) выходит стрелка, указывающая, куда следует переме­щаться в данном шаге, если система оказалась в этой точке, а в кружках записаны минимальные затраты на переход из этой точ­ки в конечное состояние. На каждом шаге графически решались уравнения (12.22).

После проведения условной оптимизации получим в точке (0; 0) минимальные затраты на эксплуатацию машины в течение 5 лет с последующей продажей: = 11900. Далее строим опти­

мальную траекторию, перемещаясь из точки ,у0(0; 0) по двойным стрелкам в 5 . Получаем набор точек:

{(0; 0), (1; 1), (2; 2), (3; 1), (4; 2), (5; 3)},

который соответствует оптимальному управлению X* {Xе, Xе, X3, Xе, Xе).

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

Как уже отмечалось, модели и вычислительная схема ДП очень гибки в смысле возможностей включения в модель раз­личных модификаций задачи. Например, аналогичная задача может быть рассмотрена для большого числа вариантов управ­ления, “ремонт”, “капитальный ремонт” и т. д. Можно рассмат­ривать замену оборудования новым с учетом технического про­гресса, можно учесть изменения в затратах на эксплуатацию оборудования после его ремонта, в зависимости от года эксплуа­тации (дороже, дешевле). Все эти факторы можно учитывать вычислительной схемой ДП.

УПРАЖНЕНИЯ

В задачах 12.4—12.5 найти оптимальное распределение средств между п предприятиями при условии, что прибыль Дх), получен­ная от каждого предприятия, является функцией от вложенных в него средств х. Вложения кратны Ах, а функции Дх) заданы таб­лично.

12.2. В условиях задачи 12.4 найти оптимальное распределение средств ^0=8.

12.3. В условиях задачи 12.4 найти оптимальное распределение средств 50=9 между четырьмя предприятиями, если функция при­были для четвертого предприятия задана следующей таблицей:

12.4. В условиях задачи 12.5 найти оптимальное распределение средств 50~6 между четырьмя предприятиями.

12.5. В условиях задачи 12.6 найти оптимальное распределение средств между 2-, 3- и 4-м предприятиями (1-е предприятие ис­ключить).

В задачах 12.10—12.11 найти оптимальное распределение ре­сурсов 50 между двумя отраслями производств I и II в течение п лет, если даны функции доходов /\{х) и /^{х) для каждой отрасли, функции возврата ф)(х) и фг(х). По истечении года только все возвращенные средства перераспределяются, доход в производст­во не вкладывается.

12.6. ^0=40000 ед.; я=4; /1(х)=0,4х; ^(х)=0,3х; ф](х)=0,5х; Ф2(х)=0,8х.

12.7. 50= 10000 ед.; и=4; /1(х)=0,1х2; /2(х)=0,5х; ф1(х)=0,75х; ф2(х)=0,3х.

12.8. Решить задачу 12.10 при условии, что в начале каждого : года дополнительно поступают средства в размерах As = 10000. i

В задачах 12.13—12.15 составить математическую модель, запи-/ сать уравнения Веллмана и решить графически следующие задачи на определение оптимальных сроков замены оборудования. Даны: первоначальная стоимость оборудования р0, его ликвидная стои­мость ф(г), стоимость содержания tit) в течение года оборудования возраста t лет, п — срок эксплуатации, в конце которого оборудо­вание продается. Критерий оптимальности — суммарные затраты на эксплуатацию оборудования в течение п лет с учетом первона­чальной покупки и последующей продажи.

12.9. />о=8000; ф0)“а2"'; /0=(Н-1); и=5.

12.10. и=5. Стоимость нового оборудования зависит от года по­купки />*=5000+500(£-1); (Л=1, 2,..., 5); q(t)=pk2~,\ r^t)=0,lpk{e-\).

12.11. />0=8000; л=5, каждом (л-м) шаге алгоритма получая вектор Х„

так, что Хп-*Х*. Таким образом, алгоритм решения оптимизаци­онных задач — это последовательность формул:

*l=V|/l(*o),

Х2=у2(Х0, Хг),

..................................................... (13.1)

Xn~Vn(Xo, хи ..., Х„_\).

Такая последовательность может быть и бесконечной; в этом случае работа программы заканчивается, когда получается реше­ние, достаточно близкое к точному. Обычно на практике это вы­глядит следующим образом. Компьютер распечатывает не только величины Хп, но и значения целевой функции F(Xn). В какой-то момент значения стабилизируются — каждое следующее значение с большой точностью повторяет предыдущее. Это значит, что оптимальное решение X* практически достигнуто, и вычисли­тельный процесс можно остановить.

Для того чтобы формулы (13.1) представляли собой действи­тельно алгоритм, необходимо, чтобы действия, выражающие ре­зультат (и-И)-го шага — Х„+\ — через результаты предыдущих шагов (Ло, Х\, ..., Х„) были доступны компьютеру. Это условие выполняется, например, если ц>„ — элементарная функция от ЛЬ, Х\, ..., Х„, т.е. получается из основных элементарных функций с помощью конечного числа алгебраических операций и операции взятия функции от функции. В данном случае любой квалифици­рованный математик-программист способен по алгоритму напи­сать текст программы, реализуемой на компьютере.

Наиболее полные и законченные результаты получены для ли­нейных задач. Развитие теории линейного программирования совпа­ло по времени с развитием ЭВМ. Такое совпадение не случайно: без ЭВМ эта теория имела бы весьма узкую область применения.

Математическим методом решения задачи линейного программи­рования служит симплексный метод, описанный в гл. 5. Напомним, что суть его заключается в том, что на каждом шаге одно допустимое базисное решение заменяется другим, улучшающим значение целе­вой функции. Таким образом, формулы (13.1) имеют вид

Хп+\=Уп(Х„), где Х„ и X„+i — допустимые базисные решения.

Рис. 13.1

Фактически явное описание функций ц/„ приведено в разд. 5.6 — алгоритм составления симплексных таблиц и есть по сути пошаго­вый алгоритм симплексного метода. Текст программы, реализую­щей приведенный в разд. 5.6 алгоритм, можно найти в [2]. Соответ­ствующая программа написана на языке Бейсик и является доста­точно простой: вместе с комментариями она содержит 120 строк.

На рис. 13.1 представлена схема этой программы (рассматри­вается задача минимизации целевой функции).

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

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

Приведем некоторые примеры алгоритмов решения задач ма­тематического программирования.

Сначала рассмотрим задачу безусловной оптимизации, т.е. нахо­ждение минимума нелинейной функции в отсутствие каких-либо ограничений: ДЛ)->тіп, где X — и-мерный вектор.

Основная идея алгоритма состоит В использовании следующего свойства функций нескольких переменных. Пусть X не является точкой экстремума функции ДА). Тогда наибольшая скорость изменения функции достигается в направлении градиента (см. разд. 11.4), т.е. чтобы “быстрее” продвинуться от значения X к оптимальному Л*, следует двигаться в направлении градиента.

Алгоритм решения задачи [9] имеет следующий вид:

а) выбрать произвольный вектор Ао; /3о=_УДАо);

б) если УДАо)=0, то процесс останавливается.

В противном случае

■^я+1 Рп,

Здесь Х„ — первый неотрицательный корень уравнения

=0. (13.3)

Формулы (13.2) задают простые вычислительные процедуры. Кроме того, на каждом шаге алгоритма требуется получить корень уравнения (13.3). Такая процедура сама требует алгоритмизации, однако во многих случаях уравнение (13.3) оказывается достаточ­но простым.

Теперь рассмотрим задачу математического программирования в обшей постановке: найти минимум целевой функции F{X), т.е.

/(*)-> min (13.4)

при ограничениях

ШХ)> 0 / = 1,2,...,/я, (13.5)

\ 0 при X е X.

Например, если система ограничений состоит только из од­них неравенств (уравнения (13.6) отсутствуют), в качестве штрафной функции может быть выбрана функция вида

п 2

0)] . Рассмотрим теперь целевую функцию 1=1

F (X), зависящую также от параметра а, и задачу безусловной оптимизации:

^(А)=ДА)+-фШ->тт. (13.7)

а

Можно показать, что во многих случаях решение задачи (13.7) при 0 сходится к решению задачи (13.4)—(13.6). Поэтому для решения рассматриваемой задачи (13.4)—(13.6) целесообразно задать последовательность а„-»0 и рассмотреть последователь-

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

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

13.1.