Лекции по "Экономике"

ДИНАМИЧЕСКОЕ  ПРОГРАММИРОВАНИЕ 

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

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

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

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

     Рассмотрим, например, разработку оптимального плана обновления производственного оборудования, рассчитанного на пятилетний период. Исходные условия таковы.

     Предприятие первоначально (в начале 1-го года) выделяет для замены устаревшего оборудования более совершенным и производительным некоторую сумму средств, составляющую S руб. Затраты, связанные с заменой единицы старого оборудования новым, в среднем равняются 1500 руб. Внедрение в производство единицы нового оборудования обеспечивает предприятию дополнительную прибыль в расчете на год в сумме 600 руб. В дальнейшем, начиная со 2-го года пятилетки, предполагается замену старого оборудования новым производить за счет некоторой доли дополнительной прибыли от внедрения нового оборудования. Перед нами стоит задача спланировать замену устаревшего оборудования новым таким образом, чтобы суммарная дополнительная прибыль за 5 лет была максимальной. Формально условие задачи можно записать так.

     В 1-й год выделенная предприятием сумма средств позволит заменить n₁ единиц старого оборудования новым. Это число составит

     n₁ = S/1500      (7.7)

     Если  каждая единица нового оборудования обеспечивает получение прибыли 600 руб., то годовая сумма прибыли  будет равна 600 n₁ руб. По условию задачи некоторая доля этой прибыли х₁, принимающая значение 0≤ х₁≤1, будет использована для замены старого оборудования во 2-м году пятилетки, тогда оставшаяся доля прибыли будет равна 1 — х₁. Обозначив через w₁ оставшуюся неиспользованной к началу 2-го года сумму прибыли, можем записать: 
 

     Начиная со 2-го года замену старого оборудования новым можно производить за счет дополнительной прибыли, полученной в предшествующем году. Так как при этом может быть использована доля прибыли, равная х₁, то ее сумма составит 600 n₁x₁. За счет этой суммы во 2-м году можно заменить какое-то число единиц старого оборудования новым

     600 n₁x₁/1500=0.4 n₁x₁

     Именно  на это число во 2-м году будет  больше новых единиц оборудования, чем в 1-м году. Следовательно, 
 

     Если  для дальнейшей замены будет использована доля прибыли x₂, то оставшаяся сумма прибыли для этого года будет составлять: 

     Аналогично  записываются величины для 3-го и 4-го годов: 
 
 
 
 
 

     Для 5-го года показатель числа единиц нового оборудования рассчитывается так же, как и для предыдущих периодов, 

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

     Суммарная прибыль   (целевая функция)  за пятилетний период 

     Из  выражений (7.7) — (7.11) видно, что суммарная  прибыль, записанная уравнением (7.12), зависит  от значений переменных x₁ x₂ x₃ x₄ В данном случае задача заключается в выборе таких значений указанных неизвестных, чтобы суммарная прибыль (целевая функция) от замены старого оборудования новым была наибольшей. Другими словами, требуется получить решение задачи, в которой отыскивается максимум функции нескольких переменных 

     Для решения поставленной задачи используем принцип последовательного, поэтапного определения значения переменных. С этой целью обозначим через F₁ F₂, F₃, F₄, F₅ суммарную дополнительную прибыль, получаемую предприятием в нарастающем порядке соответственно за 1-й год, за 2, 3, 4 года и за 5 лет. Решение начнем с последнего года и будем двигаться в обратном направлении от каждого последующего периода к предыдущему.

     Как видно из выражения, сумма прибыли в 5-м году планового периода w₅ = 600n₅- Приняв суммарную прибыль за предшествующие 4 года за F₄, суммарную прибыль за пятилетний период можно выразить так:

     F₅ = F₄ + w₅ = F₄ + 600n₅

     Подставив  из  уравнения   значение n₅, запишем:

     F₅ = F₄ + 600n₄(1 + 0,4x₄)

     Рассмотрим  теперь суммарную прибыль F₄ за 4 года. Она складывается из прибыли F₃ за предшествующие 3 года и прибыли 4-го года, равной w₄,

т. е.

     F₄ = F₃ + w₄.

     Подставив значение w₄ из выражения, имеем

     F₄ = F₃ + 600n₄(1-x₄).

     Подставив полученное  выражение F₄ в выражение, получим:

     F₅=F₃ +600n₄(1-x₄)+ 600n₄(1+0.4x₄)=F₃+1200n₄-360n₄x₄

     Па  данном этапе решения  можно определить значение переменной х₄-  Как было принято, переменная х₄ означает некою долю прибыли 4-го года, которую можно использовать замены   старого  оборудования   новым  в   следующем,   5-м году. Из уравнения (7'. 16)  видно, что чем меньше будет значение х₄, тем больше будет величина целевой функции F₅. Следовательно,  наилучшее решение на этом этапе будет получено а,   когда   переменная х₄ будет  иметь  наименьшее значение. Так как переменная х₄. имеет   область    допустимых значений            , то можно принять х₄=0

     В этом случае общая сумма прибыли 
 

     Переходим к следующему периоду, т. е. к определению  прибыли за 3 года. Она складывается из прибыли предшествующих двух лет (F₂) и прибыли 3-го года: 

     или, подставляя значение w₃ из уравнения  (7.9), имеем 

     Выразив значение F₃ через полученное в уравнении (7.18') и подставив его в выражение (7.17), получим: 

     После подстановки значения п₄ из выражения  (7.10)  
 

     Анализ  уравнения (7.20) убеждает в том, что  наибольшее значение целевая функция  будет иметь тогда, когда переменная х₃ будет равна нулю. Значит, на этом этапе решения следует принять л:₃ = 0.

     Тогда суммарная прибыль

      
 

     суммарная

 

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

     из  уравнения 

     Затем, подставив в уравнение (7.21) значение F₂ из выражения (7.23) и значение п₃ из выражения (7.9), получим: 
 

     Так же, как и в предыдущих случаях, отыскиваем значение переменной х₂. Как видно из выражения (7.24), суммарная прибыль F₅ будет тем-выше, чем больше значение х₂. Значит, наилучшее решение на этом этапе будет получено при наибольшем значении х₂ из области допустимых 0^х₂г^1. Исходя из этого, принимаем х₂=\.

     Подставив в выражение (7.24) принятое значение переменной х₂, получим: 

     На  последнем этапе рассматривается  суммарная прибыль 
за 1-й год планируемого периода, которая выражена целевой 
функцией fi. Из уравнения (7.7') видно, каким выражением 
характеризуется прибыль, получаемая к концу 1-го (или на 
чалу 2-го) года, поэтому записываем: 

     Подставляя  в формулу (7.25) значение fi из выражения (7.26) и п₂ из выражения (7.8), получаем 

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

     На  этом решение задачи можно считать  законченным, так как значения искомых  переменных Xi (i= I, 2, 3, 4) определены:

     Значение  целевой функции 

     Если  вместо    подставим ее значение из выражения (7.7), получим окончательный результат: 

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

     = 10584 руб.

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

     в начале 1-го года реконструкция осуществляется за счет средств, специально выделенных для замены единиц старого оборудования новым;

     в начале 2-го года для замены оборудования используется вся дополнительная прибыль (прибыль от замены старого оборудования новым), полученная в конце 1-го года;

     в начале 3-го года для замены единиц старого  оборудования используется вся дополнительная прибыль, полученная в конце 2-го года;

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

     Анализ  решения задачи позволяет получить, если это потребуется, дополнительную информацию. В частности, можно установить, какая суммарная прибыль была бы получена, если бы для реконструкции использовалась прибыль не только первых двух, но и последующих лет. В этом случае значения всех переменных равнялись бы единицам, т. е. x_t= I (i=l, 2, 3, 4). Тогда, подставляя последовательно эти значения переменных, получим: 
 

     (Напоминаем, что нижний индекс при функции  означает суммарную прибыль за пятилетний период). Окончательный результат в этом случае составит: 

     Сравнивая результаты в выражениях (7.30) и (7.32), убеждаемся, что если дополнительная прибыль будет использоваться на реконструкцию предприятия ежегодно (в течение 4 лет), то суммарная дополнительная прибыль за весь планируемый период будет почти на 82% (2,352—1,53664 = 0,81536) ниже, чем по оптимальному плану реконструкции.

     Аналогично  можно определить величину суммарной  прибыли, если значения всех переменных будут равны нулю, т е л', = 0 (i=l, 2, 3, 4).

     Результаты  по этапам в этом случае будут такими: 
 

     рую оказывали влияние изменяющиеся условия в течение всего планируемого периода.

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