Реализация на ЭВМ решения задачи оптимальной политики замены оборудования
Министерство образования республики Беларусь
Учреждение образования
"Брестский государственный университет имени А. С. Пушкина"
Математический факультет
Кафедра математического моделирования
Курсовая работа
Реализация на ЭВМ решения задачи оптимальной политики замены оборудования
Брест 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) < 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 нового оборудования (сюда же включены затраты, связанные с установкой, запуском оборудования). Данные задачи приведены в таблице.
|
Возраст оборудования |
|||||||||||
|
0 |
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
|
т |
0 |
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;
{----------------------------------------------------------------------------}
procedure ReadData(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;
while not 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;
while not 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;
{----------------------------------------------------------------------------}
procedure WriteData;
var
i : word;
q : array[0..1] of string;
begin
Writeln('Решение:');
q[0] := 'заменить';
q[1] := 'сохранить';
for i := 1 to optimalPlan.size do
Writeln(i, ' year -> ', q[optimalPlan.items[i]]);
end;
{----------------------------------------------------------------------------}
function S(t : word) : real;
begin
S := 2;
end;
{----------------------------------------------------------------------------}
function P(t : word) : real;
begin
P := 15;
end;
{----------------------------------------------------------------------------}
function U(t : word) : real;
begin
U := vectorU.items[t];
end;
{----------------------------------------------------------------------------}
function R(t : word) : real;
begin
R := vectorR.items[t];
end;
{----------------------------------------------------------------------------}
function F(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;
{----------------------------------------------------------------------------}
procedure BuildOutMatrix;
var
i : word;
j : word;
action : byte;
begin
outMatrix.rows := vectorR.size - 1;
outMatrix.cols := vectorR.size;
for i := 1 to outMatrix.rows do
for j := 0 to outMatrix.cols do
begin
outMatrix.items[i, j].value := F(j, i, action);
outMatrix.items[i, j].action := action;
end;
end;
{----------------------------------------------------------------------------}
procedure GetOptimalPlan(startTime : word; count : byte);
var
i : word;
currTime : word;
begin
currTime := startTime;
optimalPlan.size := count;
for i := 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.