Реализация на ЭВМ решения задачи оптимальной политики замены оборудования

Министерствообразования республики Беларусь
Учреждениеобразования
«Брестскийгосударственный университет имени А. С. Пушкина»
Математическийфакультет
Кафедраматематического моделирования
Курсовая работа
Реализация наЭВМ решения задачи оптимальной политики замены оборудования
Брест 2009

Содержание
Введение
1.Динамическое программирование
1.1Основные понятия
1.2Принципы динамического программирования. Функциональные уравнения Беллмана
1.3Особенности задач динамического программирования
1.4Примеры задач динамического программирования
2.Задача о замене оборудования
3.Расчет показателей экономико-математической модели
Списокиспользованных источников
Приложение

Введение
Во всем мире существуетмножество предприятий, которые используют для производства своей продукциимашинное оборудование. Поэтому при его внедрении нужно составлять оптимальныйплан использования и замены оборудования. Задачи по замене оборудованиярассматриваются как многоэтапный процесс, который характерен для динамическогопрограммирования. Многие предприятия сохраняют или заменяют оборудование посвоей интуиции, не применяя методы динамического программирования. Применятьэти методы целесообразно, так как это позволяет наиболее четко максимизироватьприбыль или минимизировать затраты. Цель этой курсовой работы изучитьдинамическое программирование для дальнейшего его использования. Задача озамене оборудования состоит в определении оптимальных сроков замены старогооборудования. Старение оборудования включает его физический и моральный износ.В результате чего увеличиваются производственные затраты, растут затраты наобслуживание и ремонт, снижается производительность труда и ликвиднаястоимость. Критерием оптимальности является либо прибыль от эксплуатацииоборудования, либо суммарные затраты на эксплуатацию в течение планируемогопериода.
Задачами даннойкурсовой работы являются:
1) рассмотретьтеоретические аспекты решения задач динамического программирования: реккурентностьприроды задач данного типа; принципы оптимальности Беллмана
2) разработкаалгоритма. Блок-схемы. Структура алгоритма
3) реализация на ЭВМпостроенного алгоритма на выбранном языке программирования

1. Динамическоепрограммирование
1.1 Основные понятия
Динамическоепрограммирование (иначе динамическое планирование) это метод нахожденияоптимальных решений в задачах с многошаговой (многоэтапной) структурой.
В задачах динамическогопрограммирования экономический процесс зависит от времени (от несколькихпериодов (этапов) времени), поэтому находится ряд оптимальных решений(последовательно для каждого этапа), обеспечивающих оптимальное развитие всегопроцесса в целом. Задачи динамического программирования называютсямногоэтапными или многошаговыми. Динамическое программирование представляетсобой математический аппарат, позволяющий осуществлять оптимальное планированиемногошаговых управляемых процессов и процессов, зависящих от времени.Экономический процесс называется управляемым, если можно влиять на ход егоразвития. Управлением называется совокупность решений, принимаемых на каждомэтапе для влияния на ход процесса. В экономических процессах управлениезаключается в распределении и перераспределении средств на каждом этапе.Например, выпуск продукции любым предприятием — управляемый процесс, так как онопределяется изменением состава оборудования, объемом поставок сырья, величинойфинансирования и т.д. Совокупность решений, принимаемых в начале каждого года планируемогопериода по обеспечению предприятия сырьем, замене оборудования, размерамфинансирования и т.д., является управлением. Казалось бы, для получениямаксимального объема выпускаемой продукции проще всего вложить максимальновозможное количество средств и использовать на полную мощность оборудование. Ноэто привело бы к быстрому изнашиванию оборудования и, как следствие, куменьшению выпуска продукции. Следовательно, выпуск продукции надо спланироватьтак, чтобы избежать нежелательных эффектов. Необходимо предусмотретьмероприятия, обеспечивающие пополнение оборудования по мере изнашивания, т.е.по периодам времени. Последнее хотя и приводит к уменьшению первоначальногообъема выпускаемой продукции, но обеспечивает в дальнейшем возможностьрасширения производства. Таким образом, экономический процесс выпуска продукцииможно считать состоящим из нескольких этапов (шагов), на каждом из которыхосуществляется влияние на его развитие.
Началом этапа (шага)управляемого процесса считается момент принятия решения (о величине капитальныхвложений, о замене оборудования определенного вида и т.д.). Под этапом обычнопонимают хозяйственный год.
Динамическоепрограммирование, используя поэтапное планирование, позволяет не толькоупростить решение задачи, но и решить те из них, к которым нельзя применитьметоды математического анализа. Упрощение решения достигается за счетзначительного уменьшения количества исследуемых вариантов, так как вместо того,чтобы один раз решать сложную многовариантную задачу, метод поэтапногопланирования предполагает многократное решение относительно простых задач.
Планируя поэтапныйпроцесс, исходят из интересов всего процесса в целом, т.е. при принятии решенияна отдельном этапе всегда необходимо иметь в виду конечную цель.
Однако динамическоепрограммирование имеет и свои недостатки. В отличие от линейногопрограммирования, в котором симплексный метод является универсальным, вдинамическом программировании такого метода не существует. Каждая задача имеетсвои трудности, и в каждом случае необходимо найти наиболее подходящую методикурешения. Недостаток динамического программирования заключается также втрудоемкости решения многомерных задач. При очень большом числе переменныхрешение задачи даже на современных ЭВМ ограничивается памятью и быстродействиеммашины. Например, если для исследования каждой переменной одномерной задачитребуется 10 шагов, то в двумерной задаче их количество увеличивается до 100, втрехмерной — до 1000 и т.д.
1.2 Принципыдинамического программирования. Функциональные уравнения Беллмана
Принцип оптимальности ипогружения. Любую многошаговую задачу можно решать по-разному. Во-первых, можносчитать неизвестными величинами ut и находить экстремум целевой функции однимиз существующих методов оптимизации, т. е. искать сразу все элементы решения навсех N шагах. Следует заметить, что этот путь не всегда приводит к цели,особенно когда целевая функция задана в виде таблиц или число переменных оченьвелико. Во-вторых, можно проводить оптимизацию поэтапно. Поэтапность отнюдь непредполагает изолированности в оптимизации этапов. Наоборот, управление накаждом шаге выбирается с учетом всех его последствий. Обычно второй способоптимизации оказывается проще, чем первый, особенно при большом числе шагов.Идея постепенной, пошаговой оптимизации составляет суть метода динамическогопрограммирования. Оптимизация одного шага, как правило, проще оптимизации всегопроцесса в целом. Лучше много раз решать простую задачу, чем один раз — сложную.
С первого взгляда идеяможет показаться тривиальной: если трудно оптимизировать сложную задачу, тоследует разбить ее на ряд более простых. На каждом шаге оптимизируется задачамалого размера, что уже нетрудно. При этом принцип динамическогопрограммирования вовсе не предполагает, что каждый шаг оптимизируетсяизолированно, независимо от других. Напротив, пошаговое управление должновыбираться с учетом всех его последствий.
Пусть, например,планируется работа группы промышленных предприятий, из которых одни занятывыпуском предметов потребления, а другие производят для этого машины. Задачейявляется получение за T лет максимального объема выпуска предметов потребления.Пусть планируются капиталовложения на первый год. Исходя из интересов толькоэтого года, мы должны были бы все средства вложить в производство предметовпотребления, пустить имеющиеся машины на полную мощность и добиться к концугода максимального объема выпуска продукции. Однако относительно всего периодапланирования такое решение будет нерациональным. Необходимо выделить часть средствна производство машин. При этом объем продукции за первый год снизится, затобудут созданы условия, позволяющие увеличить его выпуск в последующие годы.
Приведем второй пример.Пусть прокладывается участок железнодорожного пути между пунктами А и В. Различные варианты трассы требуют неодинаковых затрат, связанных с неоднородностьюгрунта, особенностями рельефа, естественными препятствиями и т. д. Требуетсятак провести дорогу из A в В, чтобы суммарные затраты были минимальны.
Заметим, что в даннойзадаче нет естественного деления на шаги, поэтому деление вводитсяискусственно, для чего расстояние между А и В разбивается на N частей и за шагоптимизации принимается каждая такая часть.
Таким образом, одним изусловий применимости метода динамического программирования является возможностьразбиения процесса оптимизации решения на ряд однотипных шагов (этапов), каждыйиз которых планируется отдельно, но с учетом состояния системы на начало этапаи последствий принятого решения. Однако, среди всех шагов существует один,который может планироваться без оглядки на будущее. Это последний шаг,поскольку за ним нет больше этапов. Он может быть изучен и спланирован сам посебе наилучшим. Отсюда получаем одну из специфических особенностейдинамического программирования: всю вычислительную процедуру программированияцелесообразно разворачивать от конца к началу. Раньше всех планируетсяпоследний N-й шаг, за ним (N — 1)-й и т. д. Возникает вопрос, как найтиоптимальное управление uN на N-м шаге, если оно определяется не только цельюуправления, но и состоянием системы на начало этого шага? Сделать это можно наоснове предположений об ожидаемых исходах предшествующего, но еще неисследованного этапа, т. е. о значениях xN-1.
Для каждого возможногоисхода хN-1 на (N — 1)-м этапе находим оптимальное управление на N-м этапе.Такой набор оптимальных управлений, зависящих от возможных исходов предыдущегоэтапа, называется условно-оптимальным решением uN*(xN-1). Завершив анализконечного этапа, рассматривают аналогичную задачу для предпоследнего этапа,требуя, чтобы функция цели достигала экстремального значения на двух последнихэтапах вместе. Это дает условно-оптимальное решение на предпоследнем этапеu*N-1(xN-2), т.е. делаются всевозможные предположения о том, чем кончился предыдущий(N-2)-й шаг, и для каждого из предположений находится такое управление на(N-1)-м шаге, при котором эффект за последние два шага (из них последний ужеоптимизирован) будет максимален. Тем самым мы найдем для каждого исхода(N-2)-го шага условно-оптимальное управление на (N-1)-м и условно-оптимальноезначение функции цели на последних двух шагах. Проделав такой поискусловно-оптимальных управлений для каждого шага от конца к началу, найдемпоследовательность условно-оптимальных управлений (x0), (x1),+, (xN-1).
Условно-оптимальныеуправления дают возможность найти не условное, а просто оптимальное управлениена каждом шаге. В самом деле, пусть начальное состояние x0 известно. Тогда,проделав процедуру движения от конца к началу, находим (х0). Так как начальноесостояние x0 определяется однозначно, это оптимальное управление для первогошага. Вместе с тем находим экстремальное значение целевой функции относительновсего процесса. Зная оптимальное действие (с точки зрения всего процесса) дляпервого шага, выявим, к какому состоянию перейдет система в результате этогодействия, т. е. найдем оптимальное состояние системы на начало второго этапа.Но для всех возможных состояний на начало второго этапа выявлены оптимальныеуправления. Таким образом, зная, установим оптимальное управление для второгоэтапа (x1) и т.д. Проделав обратное движение по условно-оптимальным управлениямот начала к концу, найдем просто оптимальные управления для всех этапов.
Таким образом, впроцессе оптимизации управления методом динамического программированиямногошаговый процесс проходится дважды.
-Первый раз — от концак началу, в результате чего находятся условно-оптимальные управления иусловно-оптимальное значение функции цели для каждого шага, в том числеоптимальное управление для первого шага и оптимальное значение функции цели длявсего процесса.
-Второй раз — от началак концу, в результате чего находятся уже оптимальные управления на каждом шагес точки зрения всего процесса. Первый этап сложнее и длительнее второго, навтором остается лишь отобрать рекомендации, полученные на первом. Следуетотметить, что понятия «конец» и «начало» можно по менятьместами и разворачивать процесс оптимизации в другом направлении. С какогоконца начать — диктуется удобством выбора этапов и возможных состояний на ихначало.
Из анализа идеипоэтапной оптимизации можно сформулировать следующие принципы, лежащие в основединамического программирования: принцип оптимальности и принцип погружения.
Принцип оптимальности.Оптимальное управление на каждом шаге определяется состоянием системы на началоэтого шага и целью управления. Или в развернутой форме: оптимальная стратегияне зависит от начального состояния и начального решения, поэтому последующиерешения должны приниматься с учетом состояния системы в результате первогорешения.
Принцип погружения.Форма задачи, решаемая методом динамического программирования, не меняется приизменении количества шагов N, т.е. форма такой задачи инвариантна относительноN. В этом смысле всякий конкретный процесс с заданным числом шагов оказываетсякак бы погруженным в семейство подобных ему процессов и может рассматриваться спозиции более широкого класса задач.
Реализация названныхпринципов дает гарантию того, что решение, принимаемое на очередном шаге,окажется наилучшим относительно всего процесса в целом, а не узких интересовданного этапа. Последовательность пошаговых решений приводит к решению исходнойN -шаговой задачи.
Функциональныеуравнения Беллмана. Как отмечалось выше, в основе динамического программированиялежит принцип оптимальности, направленный на процедуру построения оптимальногоуправления. Так как оптимальной стратегией может быть только та, котораяодновременно оптимальна и для любого количества оставшихся шагов, ее можностроить по частям: сначала для последнего этапа, затем для двух последних, длятрех и т. д., пока не придем к первому шагу. Отсюда принцип оптимальностисвязан со вторым принципом — принципом погружения, согласно которому прирешении исходной задачи ее как бы погру жают в семейство подобных ей и решаютдля одного последнего этапа, для двух последних и т. д., пока не получатрешение исходной задачи.
Дадим математическуюформулировку принципа оптимальности. Для простоты будем считать, что начальноеx0 и конечное xT состояния системы заданы. Обозначим через z1(х0, u1) значениефункции цели на первом этапе при начальном состоянии системы x0 и приуправлении u1, через z2(х1, u2) — соответствующее значение функции цели толькона втором этапе, ..., через zi(хi-1,ui) — наi-м этапе, ..., через zN(хN-1, uN) на N-м этапе. Очевидно, что
Z = z (x0, u) = (1)

Надо найти оптимальноеуправление u*=(;;...;), такое, что доставляет экстремум целевой функции (1) приограничениях u Ω. Для решения этой задачипогружаем ее в семейство подобных. Введем обозначения. Пусть ΩN,ΩN-1,N, +, Ω1,2,+,N ≡ Ω — соответственно областиопределения для подобных задач на последнем этапе, двух последних и т. д.;Ω — область определения исходной задачи. Обозначим через
F1(xN-1), F2(xN-2), +,Fk(xN-k), +, FN(x0)
соответственноусловно-оптимальные значения функции цели на последнем этапе, двух последних ит. д., на k последних и т. д., на всех N этапах. Начинаемс последнего этапа. Пусть хN-1 — возможные состояния системы на начало N-гоэтапа. Находим:
F1(xN-1) = zN (xN-1,uN). (2)
Для двух последнихэтапов получаем
F2(xN-2) = (ZN-1(xN-2,uN-1)+F1(xN-1)). (3)
Аналогично:
F3(xN-3) = (ZN-2(xN-3,uN-2)+F2(xN-2)). (4)
Fk(xN-k) =(zN-k+1(xN-k, uN-k+1)+Fk-1(xN-k+1)). (5)
FN(x0) = (z1(x0,u1)+FN-1(x1)). (6)
Выражение (6) представляетсобой математическую запись принципа оптимальности. Выражение (5) — общая формазаписи условно-оптимального значения функции цели для k оставшихся этапов.Выражения (2) — (6) называются функциональными уравнениями Беллмана. Отчетливопросматривается их рекуррентный (возвратный) характер, т. е. для нахожденияоптимального управления на N шагах нужно знать условно-оптимальное управлениена предшествующих N — 1 этапах и т. д. Поэтому функциональные уравнения частоназывают рекуррентными (возвратными) соотношениями Беллмана.
1.3 Особенности задачдинамического программирования
На основанииприведенных примеров можно выделить следующие особенности задач динамическогопрограммирования.
— Рассматриваетсясистема, состояние которой на каждом шаге определяется вектором xt. Дальнейшееизменение ее состояния зависит только от данного состояния xt и не зависит оттого, каким путем система пришла в это состояние. Такие процессы называютсяпроцессами без последействия.
— На каждом шагевыбирается одно решение ut, под действием которого система переходит изпредыдущего состояния xt-1 в новое хt. Это новое состояние является функциейсостояния на начало интервала xt-1 и принятого в начале интервала решения ut,т. е. xt = xt(xt-1,ut).
— Действие на каждомшаге связано с определенным выигрышем (доходом, прибылью) или потерей(издержками), которые зависят от состояния на начало шага (этапа) и принятогорешения.
— На векторы состоянияи управления могут быть наложены ограничения, объединение которых составляетобласть допустимых решений u Ω.
— Требуется найти такоедопустимое управление ut для каждого шага t, чтобы получить экстремальноезначение функции цели за все Т шагов.
Любую допустимуюпоследовательность действий для каждого шага, переводящую систему из начальногосостояния в конечное, называют стратегией управления. Стратегия управления, врезультате которой можно получить экстремальное значение функции цели,называется оптимальной.
Геометрическаяинтерпретация задачи динамического программирования состоит в следующем. Пустьn — размерность пространства состояний. В каждый момент времени координатысистемы имеют вполне определенное значение. С изменением времени t могутизменяться значения координат вектора состояния. Назовем переход системы изодного состояния в другое траекторией ее движения в пространстве состояний.Такой переход осуществляется воздействием на координаты состояния.Пространство, в котором координатами служат состояния системы, называетсяфазовым. Особенно наглядно задачу динамического программирования можноинтерпретировать в случае, если пространство состояний двухмерно. Областьвозможных состояний в этом случае изобразится некоторой фигурой Ω,начальное и конечное состояния системы — точками х0, xt Ω. Управление этовоздействие, переводящее систему из начального состояния в конечное. Для многихэкономических задач не известно начальное либо конечное состояние, а известнаобласть X0 или XT, которой эти точки принадлежат. Тогда допустимые управленияпереводят точки из области Х0 в XT. Задача динамического программированиягеометрически может быть сформулирована следующим образом: найти такую фазовуютраекторию, начинающуюся в области Х0 и оканчивающуюся в области ХT, длякоторой функция цели достигает экстремального значения. Если в задаче динамическогопрограммирования известны начальное и конечное состояния, то говорят о задаче сзакрепленными концами. Если известны начальные и конечные области, то говорят озадаче со свободными концами.

1.4 Примеры задачдинамического программирования
Приведем еще несколькотипичных задач, для решения которых необходимым является применение методадинамического программирования. Задачаперспективного планирования. Задача заключается в следующем: пусть планируетсядеятельность группы N промышленных предприятий П, (i=) на период в t (t =)хозяйственных лет. В начале периода на развитие системы предприятий выделеныкакие-то средства, обозначим их К, которые должны быть распределены междупредприятиями. В процессе деятельности предприятия вложенные в него средства частичноамортизируются. Каждое предприятие за год работы приносит доход, которыйзависит от вложенных в процесс производства средств. Часть этих средствотчисляется в фонд предприятий. В начале каждого хозяйственного года имеющиесясредства перераспределяются между предприятиями. Таким образом, возникаетзадача определения объема средств в начале каждого года, которые нужно выделитькаждому предприятию, чтобы суммарный чистый доход за Т лет был максимальным.Это типичная задача динамического программирования. Здесь процесс принятиярешения разбивается на Т шагов. Управление им заключается в начальномраспределении и последующих перераспределениях средств ut ={}, где объемсредств, выделенных i-му предприятию в начале t-го года. Для описания динамикисистемы вводится вектор состояния хt={}, где состояние i-го предприятия наначало t-го года. В свою очередь состояние каждого предприятия являетсявектором, координатами которого служат трудовые ресурсы, основные фонды,финансовое положение и т. д., т. е. =(). Очевидно, что вектор управления этофункция состояния системы на начало соответствующего года: ut = ut(xt-1), приэтом начальное состояние системы x0 может быть заданным. Целевой функцией будетсуммарная прибыль объединения за Т лет, тогда, если zt прибыль за t-й год, тополучим задачу

max Z =, u Ω,
где Ω областьдопустимых управлений, или множество экономических возможностей, определяемыхразличными ограничениями, которые налагаются на состояние системы и векторуправления.
Задача об оптимальномуправлении поставками. В различных областях народного хозяйства возникаетзадача определения момента подачи партии поставки и ее объема. С размещениемзаказов связаны некоторые фиксированные затраты К, не зависящие от величинызаказываемой партии, а зависящие только от факта заказа. С содержаниемматериальных ресурсов связаны затраты, пропорциональные остатку нереализованнойпродукции на конец интервала планирования. Пусть Т — промежуток планирования.Обозначим через vt интенсивность потребления ресурса в t-м интервале. Состояниесистемы будем описывать величиной остатка нереализованной продукции на конецинтервала хt, при этом начальное х0 и конечное хt состояния системы можносчитать заданными. Для обеспечения непрерывности потребления поставками нужноуправлять. Обозначим через u = {ut} вектор управления, координаты котороговеличина поставок в начале соответствующих интервалов планирования. Очевидно,что вектор управления есть функция состояния на начало интервала. Из множествавозможных управлений требуется выбрать такое, при котором достигается минимумиздержек на заказ и содержание материальных ресурсов. Если St издержкисодержания единицы продукции в t-м интервале, то функция цели примет вид:
min Z = ,
Состояние системыопишется соотношением хt = xt-1 + ut — vt (t = ). На состояние системы можетбыть наложено ограничение, связанное с надежностью снабжения: хt ≥ x0,где х0 — величина некоторого страхового запаса, защищающего с заданнойнадежностью от сбоев в системе. Объединение ограничений, налагаемых на состояниесистемы и вектор управления, обозначим через Ω.
Получим задачу:
min Z =, u Ω.

2. Задача о заменеоборудования
Задача о заменеоборудования (обновлении, восстановлении, перестройке) имеет важное значение.Рассмотрим ее в упрощенной постановке Известно, что оборудование со временемизнашивается, стареет физически и морально. В процессе эксплуатации, какправило, падает его производительность и растут эксплуатационные расходы натекущий ремонт. Со временем возникает необходимость замены оборудования, таккак его дальнейшая эксплуатация обходится дороже, чем ремонт или замена. Отсюдазадача о замене может быть сформулирована так: в процессе работы оборудованиедает ежегодно прибыль, требует эксплуатационных затрат и имеет остаточнуюстоимость. Эти характеристики зависят от возраста оборудо вания. В любом годуоборудование можно сохранить, продать по остаточной цене и приобрести новое. Вслучае сохранения оборудования возрастают эксплуатационные расходы и понижаетсяпроизводительность. При замене нужны значительные дополнительные капитальныевложения. Задача состоит в определении оптимальной стратегии замен в плановомпериоде с тем, чтобы суммарная прибыль за этот период была максимальной.
Для количественнойформулировки задачи введем следующие обо значения r(t) стоимость продукции,производимой за год на единице оборудования возраста t лет, u(t) расходы,связанные с эксплуатацией этого оборудования, s(t) остаточная стоимостьоборудования возраста t лет, р покупная цена оборудования, Т — продолжительность планового периода, t = 0, 1, 2,, Т номер текущего года.
Решение
Чтобы решить задачу,применим принцип оптимальности Беллмана. Рассмотрим интервалы (годы) плановогопериода в последовательности от конца к началу. Введем функциюусловно-оптимальных значений функции цели Fk(t). Эта функция показываетмаксимальную прибыль, получаемую от оборудования возраста t лет за последние kлет планового периода. Здесь возраст оборудования рассматривается в направленииестественного хода времени. Например, t = 0 соответствует использованиюсовершенно нового оборудования. Временные же шаги процесса нумеруются вобратном порядке. Например, при k = 1 рассматривается последний год плановогопериода, при k = 2 последние два года и т. д., при k = T последние T лет.
В этой задаче системусоставляет оборудование. Ее состояние характеризуется возрастом. Векторуправления это решение в момент t = 0, 1, 2, +, Т о сохранении или заменеоборудования. Для нахождения оптимальной политики замен следуетпроанализировать, согласно принципу оптимальности, процесс от конца к началу.Для этого сделаем предположение о состоянии оборудования на начало последнегогода (k = 1). Пусть оборудование имеет возраст t лет. В начале T-го годаимеется две возможности: 1) сохранить оборудование на T — й год, тогда прибыльза последний год составит r(t) u(t), 2) продать оборудование по оста точнойстоимости и купить новое, тогда прибыль за последний год будет равна s(t) р + r(0) u(0), где r(0) стоимость продукции, выпущенной на новом оборудовании запервый год его ввода, u(0) эксплуата ционные расходы в этом году. Здесьцелесообразно разворачивать про цесс от конца к началу. Для последнего года(k=1) оптимальной политикой с точки зрения всего процесса будет политика,обеспечивающая максимальную прибыль только за последний год. Учитывая значениеприбыли при различном образе действия (замена сохране ние), приходим к выводу,что решение о замене оборудования возраста t лет следует принять в случае,когда прибыль от нового оборудования на последнем периоде больше, чем отстарого, т. е. при условии
s(t) — p + r(0)- u(0) > r(t) — u(t)
Еслиже

s(t) — p + r(0) — u(0)
то старое оборудованиецелесообразно сохранить. Итак, для последнего года оптимальная политика имаксимальная прибыль F1(t) находятся из условия
Пусть k = 2, т. е.рассмотрим прибыль за два последних года. Де лаем предположение о возможномсостоянии t оборудования на начало предпоследнего года. Если в начале этогогода принять решение о со хранении оборудования, то к концу года будет полученаприбыль r(t) u(t). На начало последнего года оборудование перейдет в состоя ниеt + 1 и при оптимальной политике в последнем году оно принесет прибыль, равнуюF1 (t+1). Значит общая прибыль за два года составит r(t) u(t) + F1(t + 1). Еслиже в начале предпоследнего года будет принято решение о замене оборудования, топрибыль за предпоследий год составит
s(t) p + r(0) — u(0).
Поскольку приобретеноно вое оборудование, на начало последнего года оно будет в состоянии t = 1.Следовательно, общая прибыль за последние два года при оптимальной политике впоследнем году составит
s(t) — p + r(0) — u(0)+ F1(1)
Условно оптимальной впоследние два года будет политика, доставляющая максимальную прибыль
Аналогично находимвыражения для условно оптимальной прибыли за три последних года, четыре и т. д.Приk=T получим max Z = FT (t0).
Таким образом,разворачивая весь процесс от конца к началу, получаем, что максимальная прибыльза плановый период Т составит FT(t0). Так как начальное состояние t0 известно,из выражения для FT(t0) находим оптимальное решение в начале первого года,потом вытекающее из него оптимальное решение для второго года и т. д. Обратимсяк числовому примеру. Практическое применение рассмотренной выше схемыпредставлено в приложении.

3. Расчет показателейэкономико-математической модели
Решим задачу заменыоборудования на плановый период в N = 10 лет, оборудование пятилетнего возраста(T = 5).
В начале плановогопериода продолжительности в N лет имеется оборудование возраста t, известнастоимость r(t) продукции, производимой в течение года с использованием этогооборудования; ежегодные расходы u(t) связанные с эксплуатацией оборудования;его остаточная стоимость s; стоимость p нового оборудования (сюда же включенызатраты, связанные с установкой, запуском оборудования). Данные задачиприведены в таблице. Возраст оборудования 1 2 3 4 5 6 7 8 9 10 r(t) 30 30 29 29 29 28 28 27 27 26 26 u(t) 10 10 12 13 14 15 16 17 18 19 20
Для решения заданияприменим принцип оптимальности Беллмана. Рассмотрим интервалы времени, т.е.годы, планового периода от конца к началу. Обозначим функциюусловно-оптимальных значений функции цели Fk(t) — максимальную прибыль, котораябудет получена от использования оборудования возраста t лет за последние k летпланового периода.
Запишем функциональныеуравнения для последнего года планового периода F1(t) и последних k летпланового периода Fk(t) при исходных числовых значениях параметра:
Пользуясь этимивыражениями, будем последовательно вычислять значения максимальной прибылиFk(t) и записывать их в табл. 1. Первую строку получим, придавая параметру t вравенстве (1) значения 0, 1, 2, +, 10 и используя исходные данные. Например приt = 0: = 20 (сохранение).
Аналогично расчетведется до t = 9: = 7 (сохранение).
Заметим, что еслиприбыль от нового оборудования ровна прибыли от старого, то старое лучшесохранить еще на год. При t = 10= = = 7 (замена).
Из табл.1 видно, чтоr(t) — λ(t) с ростом t убывает. Поэтому при t > 9 оптимальной будетполитика замены оборудования. Чтобы различать, в результате какой политикиполучается условно-оптимальное значение прибыли, будем эти значенияразграничивать (до t = 9 включительно оптимальной является политикасохранения). Для заполнения второй строки табл.1, используем формулу (2) для k= 2:
Придавая параметру tзначения 0, 1, 2,+ ,10, используя исходные данные и значения F1(t+1) из первойстроки таблицы, заполним вторую строку. Например, при t = 4= = =28(сохранение).
Для третьей строкитаблицы используем формулу (2) для k = 3:= = и т.д.
Таблица 1т 1 2 3 4 5 6 7 8 9 10 F1(t) 20 20 17 16 15 13 12 10 9 7 7 F2(t) 40 37 33 31 28 27 27 27 27 27 27 F3(t) 57 53 48 44 44 44 44 44 44 44 44 F4(t) 73 68 61 60 60 60 60 60 60 60 60 F5(t) 88 81 77 76 75 75 75 75 75 75 75 F6(t) 101 97 93 91 90 88 88 88 88 88 88 F7(t) 117 113 108 106 104 104 104 104 104 104 104 F8(t) 133 128 123 120 120 120 120 120 120 120 120 F9(t) 148 143 137 136 135 135 135 135 135 135 135 F10(t) 163 157 153 151 150 150 150 150 150 150 150
Пусть, например, вначале планового периода имелось оборудование возраста T = 5 лет. Разработаемполитику «замен» на десятилетний период доставляющий максимальнуюприбыль. Информация для этого представлена в табл.1 на пересечении столбца t =5 строки F10(t); она составляет 150 единиц.
Значение максимальнойприбыли F10(5) = 150 записано в области «политики замены». Этозначит, что для достижения в течение 10 лет максимальной прибыли в началепервого года оборудование надо заменить. В течение первого года новоеоборудование постареет на год, т.е., заменив оборудование и проработав на немгод, за 9 лет до конца планового периода будем иметь оборудование возраста 1год. Из табл. 1 берем F9(1) = 143. Это значение располагается в области«политики сохранения», т.е. во втором году планового периода надосохранить оборудование возраста 1 год, и, проработав на нем год, за 8 лет доконца планового периода будем иметь оборудование возраста 2 года.
Значение F8(2) = 123помещено в области сохранения. Работаем на оборудовании еще год. Теперь доконца планового периода осталось 7 лет, а возраст оборудования составляет 3года. Находим F7(3) = 106. Это область сохранения. Работаем на оборудовании ещегод. Его возраст становится равным 4 годам. До конца планового периода остается6 лет. Определяем F6(4) = 90. Это область сохранения. Работаем на оборудованииеще год. Его возраст становится равным 5 годам. До конца планового периодаостается 5 лет. Определяем F5(5) = 75. Это область замен. Заменяем оборудованиена новое. Проработаем на нем в течение пятого года. Оно постареет на год. Доконца планового периода остается 4 года. Продолжая подобные рассуждения,получим, что F4(1) = 68, F3(2) = 48, F2(3) = 31, F1(4) = 15 расположены вобласти сохранения. Разработанную политику изобразим следующей цепочкой:
F10(5) F9(1) F8(2) F7(3)F6(4) F5(5) F4(1)
F3(2) F2(3) F1(4)
Из табл.1 можно найтиоптимальную стратегию замены оборудования с любым начальным состоянием от 0 до10 лет и на любой плановый период, не превосходящий 10 лет.
В приложениирассмотрена задача для любого начального возраста оборудования и для любогорасчетного периода.

Список использованныхисточников
1.А.В. Кузнецов, В.А. Сакович, Н.И. Холод Математическое программирование. — М.:Вышэйшая школа,1994.
2.Исследование операций в экономике: Учеб. пособие для вузов / Н.Ш. Кремер, Б.А.Путко, И.М. Тришин, М.Н. Фридман; Под ред. проф. Н.Ш. Кремера. — М.: Банки ибиржи, ЮНИТИ, 1997.
3.Колемаев В.А. Математическая экономика.- М.: Юнити,1998.

Приложение
program Kurs;
uses
Crt;
const
(*ACTIONS CONSTANT *)
SELL= 0;
SAVE= 1;
(*TYPES SIZE CONSTANT *)
MAX_VECTOR_SIZE= 64;
type
TOutMatrixCell= record
action: byte;
value: real;
end;
TOutMatrix= record
rows: word;
cols: word;
items: array[1..MAX_VECTOR_SIZE — 1, 0..MAX_VECTOR_SIZE — 1] of TOutMatrixCell;
end;
TPlanCell= record
year: word;
action: byte;
end;
IVector= record
size: word;
items: array[1..MAX_VECTOR_SIZE — 1] of byte;
end;
DVector= record
size: word;
items: array[0..MAX_VECTOR_SIZE — 1] of real;
end;
var
vectorR: DVector;
vectorU: DVector;
outMatrix: TOutMatrix;
optimalPlan: IVector;
startTime: word;
count: word;
{----------------------------------------------------------------------------}
procedureReadData(path: string);
var
inFile: Text;
i: word;
elem: real;
s: string;
begin
Assign(inFile,path);
Reset(inFile);
Writeln('Условие:');
repeat
Readln(inFile,s);
Writeln(s);
until (s = '');
Writeln('Начальныеданные:');
Write('R(x): ');
i:= 0;
whilenot Eoln(inFile) do
be
Read(inFile,elem);
Write(elem:3:1,' ');
vectorR.items[i]:= elem;
Inc(i);
end;
vectorR.size:= i;
Readln(inFile);
Writeln;
Write('U(x): ');
i:= 0;
whilenot Eof(inFile) do
begin
Read(inFile,elem);
Write(elem:3:1,' ');
vectorU.items[i]:= elem;
Inc(i);
end;
vectorU.size:= i;
Close(inFile);
Writeln;
Write('начальныйвозраст оборудования = ');
Readln(startTime);
Write('расчетныйпериод= ');
Readln(count);
Writeln;
end;
{----------------------------------------------------------------------------}
procedureWriteData;
var
i: word;
q: array[0..1] of string;
begin
Writeln('Решение:');
q[0] := 'заменить';
q[1]:= 'сохранить';
fori := 1 to optimalPlan.size do
Writeln(i,' year -> ', q[optimalPlan.items[i]]);
end;
{----------------------------------------------------------------------------}
functionS(t: word): real;
begin
S:= 2;
end;
{----------------------------------------------------------------------------}
functionP(t: word): real;
begin
P:= 15;
end;
{----------------------------------------------------------------------------}
functionU(t: word): real;
begin
U:= vectorU.items[t];
end;
{----------------------------------------------------------------------------}
functionR(t: word): real;
begin
R:= vectorR.items[t];
end;
{----------------------------------------------------------------------------}
functionF(t: word; order: word; var action: byte): real;
var
a: real;
b: real;
begin
if(order = 1)
then
begin
a:= R(t) — U(t);
b:= S(t) — P(t) + R(0) — U(0);
if(b >= a)
then
begin
F:= b;
action:= SELL;
end
else
begin
F:= a;
action:= SAVE;
end;
exit;
end;
a:= R(T) — U(T) + outMatrix.items[order — 1, t + 1].value;
b:= S(T) — P(T) + R(0) — U(0) + outMatrix.items[order — 1, 1].value;
if(b >= a)
then
begin
F:= b;
action:= SELL;
end
else
begin
F:= a;
action:= SAVE;
end;
end;
{----------------------------------------------------------------------------}
procedureBuildOutMatrix;
var
i: word;
j: word;
action: byte;
begin
outMatrix.rows:= vectorR.size — 1;
outMatrix.cols:= vectorR.size;
fori := 1 to outMatrix.rows do
forj := 0 to outMatrix.cols do
begin
outMatrix.items[i,j].value := F(j, i, action);
outMatrix.items[i,j].action := action;
end;
end;
{----------------------------------------------------------------------------}
procedureGetOptimalPlan(startTime: word; count: byte);
var
i: word;
currTime: word;
begin
currTime:= startTime;
optimalPlan.size:= count;
fori := count downto 1 do
begin
optimalPlan.items[count- i + 1] := outMatrix.items[i, currTime].action;
if(outMatrix.items[i, currTime].action = SELL)
then
currTime:= 1
else
Inc(currTime);
end;
end;
{----------------------------------------------------------------------------}
begin
ClrScr;
ReadData('data.txt');
BuildOutMatrix;
GetOptimalPlan(startTime,count);
WriteData;
Readln;
end.