Курсовая работа
Классификацияматематических моделей, используемых в экономике и менеджменте
Содержание
Введение
1. Математические модели вэкономике и менеджменте
1.1Классификация экономико-математических моделей
2. Оптимизационное моделирование
2.1Линейное программирование
2.1.1 Линейное программирование как инструментматематического моделирования экономики
2.1.2 Примеры моделей линейного программирования
2.2Динамическое программирование
2.2.1 Модель динамического программирования
2.2.2 Принцип оптимальности и уравнение Беллмана
2.2.3 Общее описание процесса моделирования и построениявычислительной схемы динамического программирования
2.2.4 Оптимальное распределение ресурсов
2.2.5 Оптимальное управление запасами
2.2.6 Задача о замене
Заключение
/>/>Введение
Современная математикахарактеризуется интенсивным проникновением в другие науки, во многом этотпроцесс происходит благодаря разделению математики на ряд самостоятельныхобластей. Математика стала для многих отраслей знаний не только орудиемколичественного расчёта, но также методом точного исследования и средствомпредельно чёткой формулировки понятий и проблем. Без современной математики сеё развитым логическим и вычислительным аппаратом был бы не возможен прогресс вразличных областях человеческой деятельности.
Экономика как наука об объективныхпричинах функционирования и развития общества пользуется разнообразнымиколичественными характеристиками, а поэтому вобрала в себя большое числоматематических методов.
Актуальность данной темы состоит втом, что в современной экономике используются оптимизационные методы, которыесоставляют основу математического программирования, теории игр, сетевогопланирования, теории массового обслуживания и других прикладных наук.
Изучение экономических приложенийматематических дисциплин, составляющих основу актуальной экономическойматематики, позволяет приобрести некоторые навыки решения экономических задач ирасширить знания в этой области.
Целью данной работы являетсяизучение некоторых оптимизационных методов, применяемых при решенииэкономической задач.
1. Математическиемодели в экономике и менеджменте
Математическиемодели в экономике. Широкое использование математических моделей являетсяважным направлением совершенствования экономического анализа. Конкретизацияданных или представление их в виде математической модели помогает выбратьнаименее трудоёмкий путь решения, повышает эффективность анализа.
Всеэкономические задачи, решаемые с применением линейного программированияотличаются альтернативностью решения и определенными ограничивающими условиями.Решить такую задачу — значит выбрать из всех допустимо возможных(альтернативных) вариантов лучший, оптимальный. Важность и ценностьиспользования в экономике метода линейного программирования состоят в том, чтооптимальный вариант выбирается из достаточно значительного количестваальтернативных вариантов.
Самымисущественными моментами при постановке и решении экономических задачах в видематематической модели являются:
· адекватностьэкономико-математической модели действительности;
· анализзакономерностей, соответствующих данному процессу;
· определениеметодов, с помощью которых можно решить задачу;
· анализполученных результатов или подведение итога.
Подэкономическим анализом понимается прежде всего факторный анализ.
Пустьy=f(xi)- некоторая функция, характеризующая изменение показателя или процесса; x1,x2,…,xn-факторы, от которых зависит функция y=f(xi).Задана функциональная детерминированная связь показателя yс набором факторов. Пусть показатель yизменился за анализируемый период. Требуется определить, какой частью численноеприращение функции y=f(x1,x2,…,xn)обязано приращению каждого фактора.
Можновыделить в экономическом анализе — анализ влияния производительности труда ичисленности работающих на объем произведенной продукции; анализ влияниявеличины прибыли основных производственных фондов и нормируемых оборотныхсредств на уровень рентабельности; анализ влияния заемных средств наманевренность и независимость предприятия и т. п..
Вэкономическом анализе, кроме задач, сводящихся к разбиению его на составляющиечасти, существует группа задач, где требуется функционально увязать рядэкономических характеристик, т.е. построить функцию, содержащую в себе основноекачество всех рассматриваемых экономических показателей.
Вэтом случае ставится обратная задача- так называемая задача обратногофакторного анализа.
Пустьимеется набор показателей x1,x2,…,xn,характеризующих некоторый экономический процесс F.Каждый из показателей характеризует этот процесс. Требуется построить функцию f(xi)изменения процесса F, содержащуюосновные характеристики всех показателей x1,x2,…,xn
Главныймомент в экономическом анализе — определение критерия, по которому будутсравниваться различные варианты решения.
Математические модели вменеджменте. Во всех сферах человеческой деятельности большую роль играетпринятие решений. Для постановки задачи принятия решения необходимо выполнитьдва условия:
· наличие выбора;
· выбор варианта по определенному принципу.
Известны два принципавыбора решения: волевой и критериальный.
Волевой выбор, наиболеечасто используемый, применяют при отсутствии формализованных моделей какединственно возможный.
Критериальный выборзаключается в принятии некоторого критерия и сравнении возможных вариантов поэтому критерию, Вариант, для которого принятый критерий принимает наилучшеерешение, называют оптимальным, а задачу принятия наилучшего решения – задачейоптимизации.
Критерий оптимизацииназывают целевой функцией.
Любую задачу, решениекоторой сводится к нахождению максимума или минимума целевой функции, называютэкстремальной задачей.
Задачи менеджментасвязаны с нахождением условного экстремума целевой функции при известныхограничениях, накладываемых на ее переменные.
В качестве целевойфункции при решении различных оптимизационных задач принимают количество илистоимость выпускаемой продукции, затрат на производство, сумму прибыли и т.п.Ограничения обычно касаются людских материальных, денежных ресурсов.
Оптимизационные задачименеджмента, различные по своему содержанию и реализуемые с использованиемстандартных программных продуктов, соответствуют тому или иному классуэкономико-математических моделей.
Рассмотримклассификацию некоторых основных задач оптимизации, реализуемых менеджментом напроизводстве.
Классификация задачоптимизации по функции управления:Функция управления Задачи оптимизации Класс экономико-математических моделей Техническая и организационная подготовка производства
Моделирование состава изделий;
Оптимизация состава марок, шихты, смесей;
Оптимизация раскроя листового материала, проката;
Оптимизация распределения ресурсов в сетевых моделях комплексов работ;
Оптимизация планировок предприятий, производств и оборудования;
Оптимизация маршрута изготовления изделий;
Оптимизация технологий и технологических режимов.
Теория графов
Целочисленное программирование
Дискретное программирование
Линейное программирование
Сетевое планирование и управление
Имитационное моделирование
Динамическое программирование
Нелинейное программирование Технико-экономическое планирование
Построение сводного плана и прогнозирование показателей развития предприятия;
Оптимизация портфеля заказов и производственной программы;
Оптимизация распределения производственной программы по плановым периодам.
Матричные балансовые модели “Затраты-выпуск”
Корреляционно-
регрессионный анализ
Экстраполяция тенденций
Линейное программирование Оперативное управление основным производством
Оптимизация календарно-плановых нормативов;
Календарные задачи;
Оптимизация стандарт-планов;
Оптимизация краткосрочных планов производств.
Нелинейное программирование
Имитационное моделирование
Линейное программирование
Целочисленное программирование
Сочетание различныхэлементов модели приводит к различным классам задач оптимизации:Исходные данные Переменные Зависимости Задача Детерминированные Непрерывные Линейные Линейного программирования Целочисленные Линейные Целочисленного программирования Непрерывные, целочисленные Нелинейные Нелинейного программирования Случайные Непрерывные Линейные Стохастического программирования 1.1 Классификация экономико-математических моделей
Существует значительноеразнообразие видов, типов экономико-математических моделей, необходимых дляиспользования в управлении экономическими объектами и процессами.Экономико-математические модели подразделяются на макроэкономические имикроэкономические в зависимости от уровня моделируемого объекта управления,динамические, которые характеризуют изменения объекта управления во времени, истатические, которые описывают взаимосвязи между разными параметрами,показателями объекта именно в то время. Дискретные модели отображают состояниеобъекта управления в отдельные, фиксированные моменты времени. Имитационныминазывают экономико-математические модели, используемые с целью имитацииуправляемых экономических объектов и процессов с применением средствинформационной и вычислительной техники. По типу математического аппарата,применяемого в моделях, выделяются экономико-статистические, модели линейного инелинейного программирования, матричные модели, сетевые модели.
Факторные модели. В группуэкономико-математических факторных моделей входят модели, которые с однойстороны включают экономические факторы, от которых зависит состояниеуправляемого экономического объекта, а с другой – зависимые от этих факторовпараметры состояния объекта. Если факторы известны, то модель позволяетопределить искомые параметры. Факторные модели чаще всего предоставленыпростыми в математическом отношении линейными или статическими функциями,которые характеризуют связь между факторами и зависимыми от них параметрамиэкономического объекта.
Балансовые модели. Балансовыемодели как статистические, так и динамические широко применяются вэкономико-математическом моделировании. В основе создания этих моделей лежитбалансовый метод – метод взаимного сопоставления материальных, трудовых ифинансовых ресурсов и потребностей в них. Описывая экономическую систему вцелом, под её балансовой моделью понимают систему уравнений, каждое из которыхвыражает потребность баланса между изготовленными отдельными экономическими объектамиколичества продукции и совокупной потребностью в этой продукции. При такомподходе экономическая система состоит из экономических объектов, каждый изкоторых выпускает некоторый продукт. Если вместо понятия «продукт» ввестипонятие «ресурс», то под балансовой моделью необходимо понимать системууравнений, которые удовлетворяют требования между определенным ресурсом и егоиспользованием.
Наиболее важные виды балансовыхмоделей:
· Материальные,трудовые и финансовые балансы для экономики в целом и отдельных ее отраслей;
· Межотраслевыебалансы;
· Матричныебалансы предприятий и фирм.
Оптимизационные модели. Большойкласс экономико-математических моделей образуют оптимизационные модели, которыепозволяют выбрать из всех решений наилучший оптимальный вариант. Вматематическом содержании оптимальность понимается как достижение экстремумакритерия оптимальности, называемой также целевой функцией. Оптимизационныемодели чаще всего используются в задачах нахождения лучшего способаиспользования экономических ресурсов, что позволяет достичь максимальногоцелевого эффекта. Математическое программирование образовалось на основерешения задачи про оптимальный раскрой листов фанеры, что обеспечивает наиболееполное использование материала. Поставив такую задачу, известный российскийматематик и экономист академик Л.В.Канторович был признан достойным Нобелевскойпремии в экономике.
2. Оптимизационноемоделирование 2.1 Линейное программирование 2.1.1 Линейное программирование как инструментматематического моделирования экономики
Исследование свойств общей системылинейных неравенств ведется с XIX в., а первая оптимизационная задача слинейной целевой функцией и линейными ограничениями была сформулирована в З0-егоды XX в. Одним из первых зарубежных ученых, заложивших основы линейногопрограммирования, является Джон фон Нейман, широко известный математик и физик,доказавший основную теорему о матричных играх. Среди отечественных ученых большойвклад в теорию линейной оптимизации внесли лауреат Нобелевской премии Л.В.Канторович, Н.Н. Моисеев, Е.Г. Гольштейн, Д.Б. Юдин и многие другие.
Линейное программированиетрадиционно считается одним из разделов исследования операций, который изучаетметоды нахождения условного экстремума функций многих переменных.
В классическом математическоманализе исследуется общая постановка задачи определения условного экстремума,однако в связи с развитием промышленного производства, транспорта,агропромышленного комплекса, банковского сектора традиционных результатовматематического анализа оказалось недостаточно. Потребности практики и развитиевычислительной техники привели к необходимости определения оптимальных решенийпри анализе сложных экономических систем. Главным инструментом для решениятаких задач является математическое моделирование, т.е. формализованноеописание изучаемого процесса и исследование его с помощью математическогоаппарата.
Искусство математическогомоделирования состоит в том, чтобы учесть как можно более широкий спектрфакторов, влияющих на поведение объекта, используя при этом по возможностинесложные соотношения. Именно в связи с этим процесс моделирования часто носитмногоэтапный характер. Сначала строится относительно простая модель, затемпроводится ее исследование, позволяющее понять, какие из интегрирующих свойствобъекта не улавливаются данной формальной схемой, после чего за счет усложнениямодели обеспечивается большая ее адекватность реальности. При этом во многихслучаях первым приближением к действительности является модель, в которой всезависимости между переменными, характеризующими состояние объекта, являютсялинейными. Практика показывает, что значительное количество экономическихпроцессов достаточно полно описывается линейными моделями, а следовательно,линейное программирование как аппарат, позволяющий отыскивать условныйэкстремум на множестве, заданном линейными уравнениями и неравенствами, играетважную роль при анализе этих процессов.2.1.2 Примеры моделейлинейного программирования
Ниже будут рассмотрены несколькоситуаций, исследование которых возможно с применением средств линейногопрограммирования. Так как основным показателем в этих ситуациях являетсяэкономический— стоимость, то соответствующие модели являютсяэкономико-математическими.
Задача о раскрое материалов. Наобработку поступает материал одного образца в количестве d единиц. Требуетсяизготовить из него к разных комплектующих изделий в количествах,пропорциональных числам а1,..., ак. Каждая единицаматериала может быть раскроена n различными способами, при этом использованиеi-го способа (i=1,…,n) дает bij, единиц j-го изделия (j = 1,...,k).
Требуется найти план раскроя,обеспечивающий максимальное число комплектов.
Экономико-математическая модельэтой задачи может быть сформулирована следующим образом. Обозначим xi—число единиц материалов, раскраиваемых i-м способом, и x — числоизготавливаемых комплектов изделий.
Учитывая, что общее количествоматериала равно сумме его единиц, раскраиваемых различными способами, получим:
/>(1)
Условие комплектности выразитсяуравнениями:
/> (j=1,…,k)(2)
Очевидно, что
xi/>0 (i=1,…,n)(3)
Целью является определить такоерешение Х= (x1,…,xn), удовлетворяющее ограничениям(1)-(3), при котором функция F = x принимает максимальное значение.Проиллюстрируем рассмотренную задачу следующим примером Для изготовлениябрусьев длиной 1,5 м, 3 м и 5 м в соотношении 2:1:3 на распил поступают 200бревен длиной 6 м. Определить план распила, обеспечивающий максимальное числокомплектов. Чтобы сформулировать соответствующую оптимизационную задачулинейного программирования, определим все возможные способы распила бревен,указав соответствующее число получаемых при этом брусьев (табл. 1).
Таблица 1Способ распила i Число получаемых брусьев различной длины 1,5 3,0 5,0 1 4 - - 2 2 1 - 3 - 2 - 4 - - 1
Обозначим через xi—число бревен, распиленных i-м способом (i = 1.2, 3, 4); х —число комплектовбрусьев.
С учетом того, что все бревнадолжны быть распилены, а число брусьев каждого размера должно удовлетворятьусловию комплектности, оптимизационная экономико-математическая модель приметследующий вид
х → max
при ограничениях:
x1+x2+x3+x4=200
4x1+2x2=2x
x2+2x3=x
x4=2x
xi/>0 (i=1,2,3,4)
Задача выбора оптимальнойпроизводственной программы предприятия. Пусть предприятие может выпускать nразличных видов продукции. Для выпуска этих видов продукции предприятиеиспользует М видов материально-сырьевых ресурсов и N видов оборудования.Необходимо определить объемы производства предприятия (т.е. егопроизводственную программу) на заданном интервале планирования [0, Т], чтобы максимизироватьваловую прибыль предприятия.
Далее будем полагать, что валоваяприбыль есть выручка, полученная от реализации продукции за вычетомусловно-постоянных и переменных затрат. Иными словами, необходимомаксимизировать целевую функцию вида:
/>(4)
где ai — цена реализациипродукции вида i;
bi — переменные затратына выпуск одной единицы продукции вида i;
Zp — условно постоянные затраты,которые будем предполагать независимыми от вектора х = (x1,..., xn).
При этом должны быть выполненыограничения на объемы используемых материально-сырьевых ресурсов и времяиспользования оборудования на интервале [0,T].
Обозначим через Lj(j = l,...,M)объем запасов материально-сырьевых ресурсов вида j, а через τk(k = 1,..., N) — время, в течение которого может быть использовано оборудованиевида k. Известно потребление материально-сырьевых ресурсов вида j на выпускодной единицы продукции вида i, которое обозначим через lij (i =1,..., n; j = 1,..., М). Известно также tik — время загрузки однойединицы оборудования вида k изготовления одной единицы продукции вида i (i =1,..., n; k = 1,..., N). Через mk обозначим количество единицоборудования вида k (k=l,...,N).
При введенных обозначенияхограничения на объем потребляемых материально-сырьевых ресурсов могут бытьзаданы таким образом:
/> (j=1,…,M)(5)
Ограничения на производственныемощности задаются следующими неравенствами
/> k=1,…,N(6)
Кроме того, переменные
xi≥0 i=1,…,n (7)
Таким образом, задача выборапроизводственной программы, максимизирующей прибыль, заключается в выборетакого плана выпуск х = (х1..., хn), который удовлетворялбы ограничениям (5)-(7) и максимизировал бы функцию (4).
В некоторых случаях предприятиедолжно поставить заранее оговоренные объемы продукции Vt другим хозяйствующимсубъектам и тогда в рассматриваемой модели вместо ограничения (1.7) может бытьвключено ограничение вида:
xt> Vt i= 1, ...,n.
Задача о диете. Рассмотрим задачусоставления душевого рациона питания минимальной стоимости, которое бысодержало определенные питательные вещества в необходимых объемах. Будемпредполагать, что имеется известный перечень продуктов из n наименований (хлеб,сахар, масло, молоко, мясо и т.д.), которые мы будем обозначать буквами F1,...,Fn.Кроме того, рассматриваются такие характеристики продуктов (питательныевещества), как белки, жиры, витамины, минеральные вещества и другие. Обозначимэти компоненты буквами N1,...,Nm. Предположим, что длякаждого продукта Fi известно (i = 1,...,n) количественное содержаниев одной единице продукта указанных выше компонент. В этом случае можносоставить таблицу, содержащую характеристику продуктов:
F1,F2,…Fj…Fn
_____________
N1a11a12…a1j…a1N
N2a21a22…a2j…a2N
Niai1ai2…aij…aiN
Nmam1am2…amj…amN
Элементы этой таблицы образуютматрицу, имеющую m строк и n столбцов. Обозначим ее через A и назовем матрицейпитательности. Предположим, что мы составили рацион х = (х1,x2,..., хn)на некоторый период (например, месяц). Иными словами, мы планируем каждомучеловеку на месяц х, единиц (килограммов) продукта F1,x2единиц продукта F2 и т.д. Нетрудно вычислить, какое количествовитаминов, жиров, белков и прочих питательных веществ получит человек за этотпериод. Например, компонента N1 присутствует в этом рационе вколичестве
a11x1+ a12x2+…+a1nxn
поскольку согласно условию в x1единицах продукта F1 согласно матрице питательности содержится a11x1единиц компоненты N1; к этому количеству добавляется порция а12x2вещества N1 из х2 единиц продукта F2 и т.д.Аналогично можно определить и количество всех остальных веществ Ni всоставляемом рационе (х1,..., хn).
Допустим, что имеются определенныефизиологические требования, касающиеся необходимого количества питательныхвеществ в Ni (i/ = 1,..., N) в планируемый срок. Пусть этитребования заданы вектором b = (b1...,bn), i-я компонентакоторого bi указывает минимально необходимое содержание компонента Niв рационе. Это означает, что коэффициенты xi вектора х должныудовлетворять следующей системе ограничений:
a11x1+a12x2+…+ a1nxn≥b1
a21x1+a22x2+…+ a2nxn≥b2 (8)
am1x1+ am2x2+…+amnxn≥bm
Кроме того, из содержательногосмысла задачи очевидно, что все переменные х1,..., хnнеотрицательны и поэтому к ограничениям (8) добавляются еще неравенства
x1≥0; x2≥0;…xn≥0; (9)
Учитывая, что в большинстве случаевограничениям (8) и (9) удовлетворяет бесконечно много рационов, выберем тот изних, стоимость которого минимальна.
Пусть цены на продукты F1,...,Fnравны соответственно с1,…,cn
Следовательно, стоимость всегорациона х = (х1..., хn) может быть записана в виде
c1x1+ c2x2+…+cnxn→min (10)
Окончательно формулировка задачи одиете заключается в том, чтобы среди всех векторов х = (x1,..., хn)удовлетворяющих ограничениям (8) и (9) выбрать такой, для которого целеваяфункция (10) принимает минимальное значение.
Транспортная задача. Имеется mпунктов S1,..., Sm производства однородного продукта(угля, цемента, нефти и т.п.), при этом объем производства в пункте Siравен ai единиц. Произведенный продукт потребляется в пунктах Q1...Qnи потребность в нем в пункте Qj составляет kj единиц (j =1,...,n). Требуется составить план перевозок из пунктов Si (i =1,...,m) в пункты Qj(j = 1,..., n), чтобы удовлетворить потребностив продукте bj, минимизировав транспортные расходы.
Пусть стоимость перевозок однойединицы продукта из пункта Si в пункт Qi равна cij.Будем далее предполагать, что при перевозке хij единиц продукта из Siв Qj транспортные расходы равны cijxij.
Назовем планом перевозок наборчисел хij ci = 1,..., m; j = 1,..., n, удовлетворяющийограничениям:
/>
xij≥0, i=1,2,…,m; j=1,…,n(11)
Содержательный смысл уравнений (11)состоит в том, что из пункта Si при плане хij вывозитсяво все пункты Qj объем />,который должен быть равен запасу ai. В пункт Qj поступаетиз всех пунктов Si суммарное количество />продукта,которое в точности должно быть равно потребности bj.
При плане перевозок (хij)транспортные расходы составят величину
/>(12)
Окончательное формированиетранспортной задачи таково: среди всех наборов чисел (хij),удовлетворяющих ограничениям (11), найти набор, минимизирующий (12).
2.2 Динамическое программирование 2.2.1 Модель динамического программирования
Динамическое программирование –метод оптимизации, приспособленный к операциям, в которых процесс принятиярешений может быть разбит на отдельные этапы (шаги). Такие операции называютмногошаговыми.
В основе метода динамическогопрограммирования лежит принцип оптимальности, сформулированный Беллманом. Этотпринцип и идея включения конкретной задачи оптимизации в семейство аналогичныхмногошаговых задач приводят к рекуррентным соотношениям – функциональнымуравнениям – относительно оптимального значения целевой функции. Их решениепозволяет последовательно получить оптимальное управление для исходной задачиоптимизации.
/>
Дадим общее описание моделидинамического программирования.
Рассматривается управляемаясистема, которая под влиянием управления переходит из начального состояния /> в конечное состояние />. Предположим, что процессуправления системой можно разбить на n шагов. Пусть/>,/>,…,/> - состояния системы послепервого, второго,…, n-го шага. Схематически это показано на рис. 1.
Состояние /> системы после k-го шага(k=1,2,…,n) характеризуется параметрами />,которые называют фазовыми координатами. Состояние /> можноизобразить точкой s-мерного пространства, называемого фазовым пространством.Последовательное преобразование системы (по шагам) достигается с помощьюнекоторых мероприятий />, которыесоставляют управление системой U=/>,
где /> -управление на k-м шаге, переводящее систему из состояния /> в состояние /> (рис.1). Управление /> на k-м шаге заключается ввыборе значений определенных управляющих переменных />.
Предполагаем впредь, что состояниесистемы в конце k-го шага зависит только от предшествующего состояния системы /> и управления /> на данном шаге (рис.1).Такое свойство получило название отсутствия последствия. Обозначим этузависимость в виде
/>(1.1)
Равенства (1.1) получили названиеуравнений состояний. Функции /> полагаем заданными.
Варьируя управления U, получимразличную «эффективность» процесса, которую будем оценивать количественноцелевой функцией Z, зависящей от начального состояния системы /> и от выбранного управленияU:
/>(1.2)
Показатель эффективности k-го шагапроцесса управления, который зависит от состояния /> вначалеэтого шага и управления />,выбранного на этом шаге, обозначим через /> (рис. 1). В рассматриваемойзадаче пошаговой оптимизации целевая функция (1.2) должна быть аддитивной, т.е.
/>(1.3)
Обычно условиями процесса науправление на каждом шаге /> накладываютсянекоторые ограничения. Управления, удовлетворяющие этим ограничениям,называются допустимыми.
Задачу пошаговой оптимизации можносформулировать так: определить совокупность допустимых управлений />, переводящих систему изначального состояния />в конечноесостояние /> и максимизирующих(минимизирующих) показатель эффективности (1.3).
Для единообразия формулировок (ноне вычислительных процедур!) в дальнейшем будем говорить только о задачемаксимизации, имея в виду, что если необходимо минимизировать Z, то заменив Zна Z’=-Z перейдем к максимизации Z’.
Начальное состояние />и конечное состояние /> могут быть заданыоднозначно или могут быть указаны множество /> начальныхсостояний и множество />конечных состояний так, что />.В последнем случае в задаче пошаговой оптимизации требуется определитьсовокупность допустимых управлений, переводящих систему из начального состояния/> в конечное /> имаксимизирующих целевую функцию (1.3). Управление, при котором достигаетсямаксимум целевой функции (1.3) называется оптимальным управлением и обозначаетсячерез U*=/>.
Если переменные управления /> принимают дискретныезначения, то модель ДП называется дискретной. Если же указанные переменныеизменяются непрерывно, то модель ДП называется непрерывной. В зависимости отчисла параметров состояний (s) и числа управляющих переменных на каждом шаге(r) различают одномерные и многомерные модели ДП. Число шагов в задаче можетбыть либо конечным, либо бесконечным.
ДП применяется при оптимизации какдетерминированных, так и стохастических процессов.
В некоторых задачах, решаемыхметодом ДП, процесс управления естественно разбивается на шаги. Например, прираспределении на несколько лет ресурсов деятельности предприятия шагоместественно считать временной период; при распределении средств между nпредприятиями номером шага естественно шага номер очередного предприятия. Вдругих задачах разбиение на шаги вводится искусственно. Например, непрерывныйуправляемый процесс можно рассматривать как дискретный, условно разбив его на некоторыевременные отрезки – шаги. Исходя из условий каждой конкретной задачи, длинушага выбирают таким образом, чтобы на каждом шаге получить простую задачуоптимизации и обеспечить требуемую точность вычислений.2.2.2 Принципоптимальности и уравнение Беллмана
Метод динамическогопрограммирования состоит в том, что оптимальное управление строится постепенно,шаг за шагом. На каждом шаге оптимизируется управление только этого шага.Вместе с тем на каждом шаге управление выбирается с учетом последствий, так какуправление, оптимизирующее целевую функцию только для данного шага, можетпривести к неоптимальному эффекту всего процесса. Управление на каждом шагедолжно быть оптимальным с точки зрения процесса в целом.
Иллюстрацией к сказанному вышеможет служить задача о выборе кратчайшего пути для перехода их точки A в точкуВ, если маршрут должен пройти через некоторые пункты. На рис. 2 эти пунктыобозначены кружками, а соединяющие их дороги – отрезками, рядом с которымипроставлены соответствующие расстояния.
С точки зрения интересовоптимизации только каждого ближайшего шага – выбора кратчайшего пути из даннойточки в соседнюю – следует двигаться по маршруту, проходящему через точки А, А1,А3, А2, А4, В. Длина этого маршрута равна 34.Такой путь из А в В не является кратчайшим. Например, маршрут, проходящий черезточки А, А3, А4, В имеет меньшую длину, равную 25. Решивэту задачу, мы убедимся, что второй путь также не является оптимальным.
/>
Приведенный пример многошаговойоперации показывает, что управление в каждом шаге надо выбирать с учетом егопоследствий на предстоящих шагах. Это основное правило ДП, сформулированное Р.Беллманом называется принципом оптимальности.
Оптимальное управление обладаеттаким свойством, что каково бы ни было начальное состояние на любом шаге иуправление, выбранное на этом шаге, последующие управления должны выбиратьсяоптимальными относительно состояния, к которому придет система в конце данногошага.
Использование этого принципагарантирует, что управление, выбранное на любом шаге, является не локальнолучшим, а лучшим с точки зрения процесса в целом.
Так, если система в начале k-гошага находится в состоянии />и мывыбираем произвольное управление />, тосистема придет в новое состояние />, и дальнейшие управления /> должнывыбираться оптимальными относительно состояния />.Последнее означает, что при этих управлениях максимизируется показательэффективности на последующих до конца процесса шагах k+1,…,n, т.е. величина /> Показатель,характеризующий суммарную эффективность от данного k-го до последнего n-гошага, будем обозначать через Zk, т.е. /> Задачаоптимизации процесса, начиная с k-го до последнего n-го шага (рис.3), похожа наисходную при начальном состоянии системы />,управлении /> и показателе эффективности />(аналогично(2)). Выбрав оптимальное управление Uk* на оставшихся n-k+1 шагах,получим величину />, которая зависит только от />, т.е.
/>(2.1)
Назовем величину /> условныммаксимумом. Если теперь мы выберем на k-м шаге некоторое произвольноеуправление />, то система придет всостояние />. Согласно принципуоптимальности, какое бы /> мы невыбрали, на последующих шагах управление /> должно выбрать так, чтобыпоказатель эффективности Zk+1 достигал максимального значения,равного />. Остается выбрать управление />. Его нельзя выбирать изусловия локальной максимизации показателя эффективности на данном k-м шаге,лишь бы получить />. Такой подход был бынедальновидным, поскольку от выбора /> зависитновое состояние />, а от последнего– максимально возможная эффективность, которая может быть достигнута вдальнейшем, т.е. величина />. Поэтому необходимо выбиратьуправление /> так, чтобы оно всовокупности с оптимальным управлением на последующих шагах (начиная с (k+1) –го) приводило бы к общему максимуму показателя эффективности на n-k+1 шагах,начиная с k-го до конца. Это положение в аналитической форме можно записать ввиде следующего соотношения:
/>(2.2)
Получившего название основногофункционального уравнения ДП, или уравнения Беллмана.
Из уравнения (5) может бытьполучена функция />, если известна функция />;аналогично можно получить />, если найдена />, ит.д., пока не будет определена величина />, представляющая по определениюмаксимальное значение показателя эффективности процесса в целом:
/>
Соотношения (5) для определенияпоследовательности функций /> через /> (k=n, n-1,…,1)получили название основных рекуррентных уравнений Беллмана.
Решая уравнения (2.2) дляопределения условного максимума показателя эффективности за n-k+1 шагов,начиная с k-го шага, определяем соответствующее оптимальное управление />, при котором этот максимумдостигается. Это управление также зависит от />.Будем обозначать такое управление через /> и называть условным оптимальнымуправлением на k-м шаге.
Основное значение уравнения (2.2, вкотором реализована идея динамического программирования, заключается в том, чторешение исходной задачи определения максимума функции (1.2) n переменных /> сводится к решениюпоследовательности n задач, задаваемых соотношениями (2.2), каждое из которыхявляется задачей максимизации функции одной переменной />. Эти задачи оказываютсявзаимосвязанными, так как в соотношении (2.2) при определении /> учитываетсянайденная при решении предыдущей задачи функция />.2.2.3 Общее описаниепроцесса моделирования и построения вычислительной схемы динамическогопрограммирования
Общая задачаоптимизации, чтобы ее можно было описать моделью ДП должна удовлетворять следующим условиям :
1. Задача можетинтерпретироваться как n-шаговыйпроцесс управления, а показатель эффективности процесса может быть представленв аддитивной форме, т.е. как суммапоказателей эффективности на каждом шаге.
2. Структуразадачи инвариантна относительно числа шагов п, т. е. должна быть определена длялюбого n и не зависеть от этого числа.
3. На каждомшаге состояние системы определяется конечным числом s параметровсостояния и управляется конечным числом rпеременных управления, причем s и r не зависят отчисла шагов п.
4. Выборуправления на k-м шаге не влияет на предшествующиешаги, а состояние в начале этого шага есть функция только предшествующегосостояния и выбранного на немуправления (отсутствие последействия).
Построениемодели ДП сводится к следующим основным моментам:
1) выбираютспособ деления процесса на шаги;
2) вводятпараметры состояния /> и переменные управления /> на каждомшаге процесса;
3) записываютуравнение состояния
/>(3.1)
4) вводятпоказатели эффективности на k-мшаге /> и суммарный показатель – целевуюфункцию
/>(3.2)
5) вводятв рассмотрение условные максимумы/>показателя эффективности от k-гo шага (включительно) до конца процессаи условные оптимальныеуправления на k-мшаге />
6) изограничений задачи определяют для каждого шага множества Dk допустимых управлений на этом шаге;
7) записываютосновные для вычислительной схемы ДП функциональные уравнения Беллмана
/>(3.3)
/>(3.4)
Несмотря наединообразие в общем построении модели ДП, приведенном выше, вычислительнаясхема строится в зависимости от размерности задачи, характера модели(дискретной или непрерывной), вида функций (3.1), (3.2) и других характеристикмодели. При всем разнообразии вычислительных схем ДП можно отметить в нихнекоторые общие черты.
1. Решениеуравнений (3.3) проводят последовательно, начиная с (3.4). Этот этап получилназвание условной оптимизации.
2. В результатепоследовательного решения пчастных задач на условный максимум определяют двепоследовательности функций: /> —условные максимумы исоответствующие им /> —условные оптимальныеуправления.
3. Указанныепоследовательности функций в дискретных задачах получают в табличной форме, а внепрерывных моделях их можно получить аналитически.
4. Послевыполнения первого этапа (условной оптимизации) приступают ко второму этапу —безусловной оптимизации.
а) Еслиначальное состояние /> задано />,
то непосредственно определяют максимум целевой
функции
/>(3.5)
а затем —искомое безусловное оптимальное управление по цепочке
/>(3.6)
В этойцепочке переход, указанный сплошной линией, проводят по последовательности />, апунктирной — с помощью уравнений состояний.
б) Еслизадано множество /> начальныхсостояний,
/>, тодополнительно решают еще одну задачу на максимум:
/>(3.7)
откуданаходят />, а затем,как и в п. а), по цепочке (3.6) —безусловное оптимальное управление.
Иногда наэтапе условной оптимизации вычислительный процесс удобно строить в направлении,обратном описанному выше, т. е. от 1-го шага к л-му. Этот способ получилназвание прямого хода вычислений вотличие от вышеизложенного, который называется обратным ходом. Уравнения состояний для прямого ходаудобно записывать в виде
/>(3.8)
Они могутбыть получены решением уравнений (1.1) относительно />. Введем врассмотрение условные максимумы показателя эффективности за k шагов, от 1-го до k-говключительно — величины />.Повторив рассуждения п. 2.2.2., придем к следующей формеуравнений Беллмана:
/>(3.9)
/>(3.10)
В результатерешения этих уравнений получим последовательности
/>(3.11)
Этапбезусловной оптимизации не отличается принципиально от аналогичного этапа вобратном ходе вычислений: />,если /> задано, или
/>(3.12)
если указаномножество /> возможныхконечных состояний. Далее, определяем безусловное оптимальное управление поцепочке
/>(3.13)2.2.4 Оптимальноераспределение ресурсов
Класс задач,рассматриваемый в данной главе, имеет многочисленные практические приложения.
В общем видеэти задачи могут быть описаны следующим образом. Имеется некоторое количестворесурсов, под которыми можно понимать денежные средства, материальные ресурсы(например, сырье, полуфабрикаты, трудовые ресурсы, различные виды оборудованияи т. п.). Эти ресурсы необходимо распределить между различными объектами ихиспользования по отдельным промежуткам планового периода или по различнымпромежутками по различным объектам так, чтобы получить максимальную суммарнуюэффективность от выбранного способа распределения. Показателем эффективностиможет служить, например, прибыль, товарная продукция, фондоотдача (задачимаксимизации) или суммарные затраты, себестоимость, время выполнения данногообъема работ и т. п. (задачи минимизации).
Вообще говоря, подавляющее числозадач математического программирования вписывается в общую постановку задачиоптимального распределения ресурсов. Естественно, что при рассмотрении моделейи вычислительных схем решения подобных задач методом ДП необходимоконкретизировать общую форму задачи распределения ресурсов.
В дальнейшембудем предполагать, что условия, необходимые для построения модели ДП, в задачевыполняются. Опишем типичную задачу распределения ресурсов в общем виде.
Задача 1.Имеется начальное количество средств />, которое необходимо распределить втечение п лет между sпредприятиями. Средства /> (k=1,2,…,n; i=1,…, s),выделенные в k-мгоду i-мупредприятию, приносят доход в размере /> и к концу года возвращаются вколичестве />. Впоследующем распреелении доход может либо участвовать (частично или полностью),либо не участвовать.
Требуетсяопределить такой способ распределения ресурсов (количество средств, выделяемыхкаждому предприятию в каждом плановом году), чтобы суммарный доход от s предприятийза п лет былмаксимальным.
Следовательно,в качестве показателя эффективности процесса распределения ресурсов за п лет принимается суммарный доход,полученный от sпредприятий:
/>(4.1)
Количестворесурсов в начале k-го года будем характеризовать величиной /> (параметрсостояния). Управление на k-мшаге состоит в выборе переменных /> /> обозначающихресурсы, выделяемые в k-м году i-мупредприятию.
Еслипредположить, что доход в дальнейшем распределении не участвует, то уравнениесостояния процесса имеет вид
/>(4.2)
Если женекоторая часть дохода участвует в дальнейшем распределении в каком-нибудьгоду, то к правой части равенства (4.2) прибавляется соответствующая величина.
Требуетсяопределить ns неотрицательных переменных />, удовлетворяющих условиям (4.2) имаксимизирующих функцию (4.1).
Вычислительнаяпроцедура ДП начинается с введения функции />,обозначающей доход, полученный за п—k+1лет, начиная с k-гогода до конца рассматриваемого периода, при оптимальномраспределении средств между s предприятиями,если в k-м году распределялось />средств.Функции /> для k=1,2, ...n-1удовлетворяют функциональным уравнениям (2.2), которые запишутся в виде:
/>(4.3)
При k=n согласно(2.2) получаем
/>(4.4)
Далеенеобходимо последовательно решить уравнения (4.4) и (4.3) для всех возможных /> (k = n—1, п—2, 1). Каждое из этих уравненийпредставляет собой задачу на оптимизацию функции, зависящей от s переменных.Таким образом, задача с nsпеременными сведена к последовательности п задач, каждая из которых содержит s переменных.В этой общей постановке задача по-прежнему сложна (из-за многомерности) иупростить ее, рассматривая как ns-шаговуюзадачу, в данном случае нельзя. В самом деле, попробуем это сделать.Пронумеруем шаги по номерам предприятий сначала в 1-м году, затем во 2-м и т.д.:
/>
и будемпользоваться одним параметром /> для характристики остатка средств.
В течение k-гогода состояние />' к началу любого шага s(k-1)_+i (i=1,2,…,s) определится по предыдущему состоянию /> с помощью простого уравнения />/>. Однако поистечении года, т.е. к началу следующего года, к наличным средствам необходимобудет добавить />средств и,следовательно, состояние /> в начале (ks+1)-гo шага будет зависеть не только отпредшествующего ks-гoсостояния, но и от всех s состояний иуправлений за прошлый год. В результате мы получим процесс с последействием.Чтобы исключить последействие, приходится вводить несколько параметровсостояний; задача на каждом шаге остается по-прежнему сложной из-замногомерности.
Задача 2. Планируется деятельность двух предприятий (s=2) втечение п лет.Начальные средства составляют />. Средства х, вложенные впредприятие I, приносят к концу года доход f1(x) ивозвращаются в размере /> аналогично, средства х, вложенные впредприятие II, дают доход f2(x) и возвращаются в размере />. Поистечении года все оставшиеся средства заново перераспределяются междупредприятиями I и II, новых средств не поступает и доход в производство невкладывается.
Требуетсянайти оптимальный способ распределения имеющихся средств.
Будемрассматривать процесс распределения средств как n-шаговый, вкотором номер шага соответствует номеру года. Управляемая система — двапредприятия с вложенными в них средствами. Система характеризуется однимпараметром состояния /> —количеством средств, которые следуетперераспределить в начале k-гo года. Переменных управления на каждомшаге две: /> — количествосредств, выделенных соответственно предприятию I и II. Так как средстваежегодно перераспределяются полностью, то /> />). Для каждогошага задача становится одномерной. Обозначим /> через />, тогда />
Показательэффективности k-гoшага равен /> />. Это — доход, полученный от двухпредприятий в течение k-гoгода.
Показательэффективности задачи — доход, полученный от двух предприятий в течение п лет —составляет
/>(4.5)
Уравнениесостояния выражает остаток средств /> после k-гo шага и имеет вид
/>(4.6)
Пусть />—условныйоптимальный доход, полученный от распределения средств /> между двумяпредприятиями за n—k+1 лет, начинаяс k-гo года доконца рассматриваемого периода. Запишем рекуррентные соотношения для этихфункций:
/>(4.7)
/>
где /> -определяется из уравнения состояния (4.6).
Придискретном вложении ресурсов может возникнуть вопрос о выборе шага Δх визменении переменных управления. Этот шаг может быть задан или определяетсяисходя из требуемой точности вычислений и точности исходных данных. В общемслучае эта задача сложна, требует интерполирования по таблицам /> на предыдущих шагах вычисления.Иногда предварительный анализ уравнения состояния позволяет выбрать подходящийшаг Δх, а также установить предельные значения />, длякоторых на каждом шаге нужно выполнить табулирование.
Рассмотримдвумерную задачу, аналогичную предыдущей, в которой строится дискретная модельДП процесса распределения ресурсов.
Задача 3. Составить оптимальный планежегодного распределения средств между двумя предприятиями в течениетрехлетнего планового периода при следующихусловиях:
1) начальная сумма составляет 400;
2) вложенные средства в размере х приносят на предприятии I доход f1(x) и возвращаются в размере 60% от х, а на предприятии II — соответственно f2(x) и 20%;
3) ежегодно распределяются всеналичные средства, получаемые из возвращенных средств:
4) функции f1(x) и f2(x)заданы втабл. 1:
/>
Модельдинамического программирования данной задачи аналогична модели, составленной взадаче 1.
Процессуправления является трехшаговым. Параметр /> — средства,подлежащие распределению в k-мгоду (k=l,2, 3). Переменная управления /> — средства, вложенные в предприятие Iв k-м году. Средства, вложенные впредприятие II в k-м году, составляют /> Следовательно, процесс управления на k-мшаге зависит от одного параметра /> (модель одномерная). Уравнениесостояния запишется в виде
/>(4.8)
Афункциональные уравнения в виде
/>(4.9)
/>(4.10)
Попытаемсяопределить максимально возможные значения, для которых необходимо проводитьтабулирование на k-мшаге (k=l, 2, 3). При />=400 изуравнения (4.8) определяем максимально возможное значение /> имеем /> = 0,6*400=2400 (все средства вкладываются в предприятие I).Аналогично, для /> получаемпредельное значение 0,6*240 = 144. Пусть интервал изменения /> совпадает стабличным, т. е. Δх =50. Составим таблицу суммарной прибыли на данномшаге:
/>
Это облегчитдальнейшие расчеты. Так как /> то клетки, расположенные подиагонали таблицы, отвечают одному и тому же значению />, указанномув 1-й строке (в 1-м столбце) табл. 2. Во 2-й строке таблицы записаны значения f1(x), а во 2-м столбце — значения f2(у)взятые изтабл. 1.Значения в остальных клетках таблицы получены сложением чисел f1(x) и f2(у), стоящих во2-й строке и во 2-м столбце и соответствующих столбцу и строке, на пересечениикоторых находится данная клетка. Например, для />=150получаем ряд чисел: 20 —для х = 0,у=150; 18 —для х=50, у=100; 18— для х—100, у=50; 15 — для х= 150, у=0.
Проведемусловную оптимизацию по обычной схеме. 3-й шаг. Основное уравнение (4.9)
/>
Какуказывалось выше, />. Просмотримчисла на диагоналях, соответствующих />=0; 50; 100; 150 и на каждойдиагонали выберем наибольшее. Это и есть /> В 1-й строке находим соответствующееусловное оптимальное управление. Данные оптимизации на 3-м шаге поместим восновную таблицу (табл. 4). В ней введен столбец Δх, который вдальнейшем используется при интерполяции.
Оптимизация2-го шага проведена в табл. 5 согласно уравнению вида (4.10):
/>
При этомможет быть получен максимальный доход, равный Zmax=99,l. Прямойподсчет дохода по табл. 2 для найденного оптимального управления дает 97,2.Расхождение в результатах на 1,9 (около 2%) объясняется ошибкой линейнойинтерполяции.
Мырассмотрели несколько вариантов задачи оптимального распределения ресурсов.Существуют другие варианты этой задачи, особенности которых учитываютсясоответствующей динамической моделью.
2.2.5 Оптимальноеуправление запасами
Класс задач,в которых рассматривается оптимальное управление Запасами, является наиболеехарактерным для динамического программирования. Это обусловлено тем, что взадачах управления запасами процесс естественно разворачивается во времени,причем управление как раз и заключается в том, что решение на данном промежуткевремени принимается с учетом того состояния, к которому пришла система запредшествующие периоды времени. Кроме того, эти задачи связаны, как правило, сдискретным характером переменных и, следовательно, решаются довольно сложнодругими методами. Наконец, весьма важным обстоятельством является то, что формазависимостей задачи для каждого периода времени является довольно простой(часто — линейной), что облегчает решение частной задачи оптимизации на каждомшаге, в то время как единовременное решение общей задачи с большим числомпеременных (для многих промежутков времени и кусочно-линейной или нелинейнойцелевой функцией для всего процесса) является достаточно сложным.
Проблемауправления запасами является одной из важнейших областей практическогоприложения экономико-математических методов, в том числе методовматематического программирования. Мы ограничимся анализом некоторых простейшихзадач с целью иллюстрации их решения методами динамического программирования.
Приформулировке задач управления запасами используют такие понятия.
Запасы — этолюбые денежные или материальные ценности, которые периодически пополняются(производятся, доставляются и т. д.) и некоторое время сохраняются с цельюрасходования их в последующие промежутки времени. Уровень запасов в любоймомент времени определяется начальным уровнем запасов плюс пополнение и минусрасход за промежуток времени от начального момента до данного.
Управлениезапасами в общем случае состоит в воздействии на соотношение между двумяосновными факторами— пополнением и расходом. Цель управления — оптимизациянекоторого критерия, зависящего от расходов на хранение запасов, стоимостипоставок, затрат, связанных с пополнением, штрафов и т. д.
В такойобщей постановке подобные задачи могут иметь самое разнообразное практическоеприменение. Например, под запасами можно понимать продукцию предприятия,которая производится непрерывно (пополнение) и отгружается потребителямопределенными дискретными партиями (расход). При этом спрос на продукциюпредполагается наперед заданным (детерминированный спрос) или подверженнымслучайным колебаниям (стохастическая задача). Управление запасами состоит вопределении, размеров необходимого выпуска продукции для удовлетворениязаданного спроса. Цель — минимизация суммарных затрат на хранение и пополнениезапасов. Под запасами можно понимать запасы сырья или других материалов,поставляемых дискретными партиями (пополнение) и должных обеспечить непрерывноепотребление в процессе производства (расход). Критерием оптимальности могутслужить суммарные затраты на хранение запасов, замораживание оборотных средстви поставки запасов.
Запасамимогут быть товары, поставляемые в магазин определенными партиями ипредназначенные для удовлетворения непрерывного, но подверженного случайнымколебаниям покупательского спроса. Критерий оптимальности — суммарные затратына поставки, хранение запасов и изменение производственного ритма в связи свариациями спроса.
Запасамимогут быть и сезонные товары, сохраняющиеся на складе ограниченной емкости.Товары можно покупать и продавать в различных количествах по ценам, меняющимсяво времени. Задача состоит в определении политики покупок и продаж, обеспечивающихмаксимум суммарной прибыли, и является примером задачи складирования.
Число такихпримеров можно было бы умножить. Однако в настоящем параграфе мы рассмотримлишь некоторые простейшие динамические модели задач управления запасами.
Если в задачеисходные данные определены однозначно, то задачи называются детерминированными; если же хотябы часть данных носит случайный характер и заданы распределения вероятностей,то соответствующие задачи называются стохастическими.В этой главе мы ограничимся примерами детерминированных задачуправления запасами.
Рассмотриммодель задачи управления запасами при заданном расходе. Управление в этихзадачах будет сводиться к пополнению.
Задача 1.Планируемый период разделен на n промежутков времени (дни, месяцы, кварталыи т. д.), в которых задан расход dk (k=l,2, ..., п), производимый в конце каждого изпромежутков. Известны начальный уровень запасов и зависимость суммарных затратна хранение и пополнение запасов в данном периоде от среднего уровня хранимыхзапасов и их пополнения.
Требуетсяопределить размеры пополнения запасов в каждом промежутке времени дляудовлетворения заданного расхода из условия минимизации суммарных затрат завесь планируемый период времени.
Составимматематическую модель задачи. Обозначим размер пополнения запасов в k-м промежуткевремени через xk, а уровень запасов в начале этогопромежутка (после произведенного расхода) — через />-Согласноусловию, суммарные затраты в k-м промежутке зависят от xk и /> — среднегоуровня запасов в k-м промежутке, равного
/>(5.1)
Следовательно,затраты в k-м промежутке можно рассматривать какфункцию />
Целеваяфункция задачи — суммарные затраты — запишется в виде
/>(5.2)
Требуетсяопределить переменные xk,которые связаны с переменными /> балансовымиуравнениями
/>(5.3)
выражающимиуровень запаса в начале (k+1)-гo промежутка через сумму уровня запасовв начале k-гoпромежутка />и пополнения запасов в этомпромежутке xk минус расход dk.
Ставитсязадача — найти совокупность ппеременных xk,удовлетворяющих ограничениям (5.3) — (5.5) и минимизирующих функцию (5.2).
Подобныезадачи при большом числе переменных и нелинейности функций /> другими методами математическогопрограммирования решаются сложно. Особенно сложным становится решение, когда напеременные xk налагаются условия целочисленности(или в общем случае — дискретности), как это часто бывает.
Дадимописание динамической модели задачи. Будем рассматривать n-шаговыйпроцесс оптимизации с параметрами состояния /> и переменными управлениями xk. Тогда равенство (5.3) представляетсобой уравнение состояния. Здесь удобнее использовать прямую схему расчета, таккак задано конечное состояние.
В задачахуправления запасами чаще всего возникает именно такая ситуация, поэтомупродемонстрируем построение прямой схемы вычислений.
Обозначимчерез />) условныеоптимальные затраты за промежутки, начиная с 1-го до k-гo включительно, если в конце k-гo промежутка уровень запасов равен />.
Начинаем сусловной оптимизации 1-го шага в предположении, что к концу этого шага системаокажется в состоянии
/>(5.6)
На k-м шагеполучим соответственно
/>(5.7)
Всоответствии с формой рекуррентных соотношений удобно и уравнение состояния(5.3) записать в виде
/>(5.8)
При решениилокальных задач в соответствии с уравнениями (5.6) и (5.7) будем считать, чтосостояние /> в конце шага известно. Поэтому и неравенство (5.4) удобнозаписать для />т. е. в виде/>, откуда следуют ограничения на xh:
/>(5.9)
Функциюзатрат также удобно привести к зависимости от состояния в конце шага, используяуравнение (5.8):
/>
Выполнивусловную оптимизацию, получим последовательно
/>
Далее(безусловная оптимизация), находим Zmax =/>призаданном конечном состоянии, или Zmax = />и />, есликонечное состояние не задано. Затем последовательно определяем
/>
Даннаязадача является примером общего случая, когда функции />) — затратына производство и /> — затратына хранение — являются вогнутыми (Функция f(x),определенная в промежутке X, называетсявогнутой, если для любых точек x1/>X, x2/>X (x1/>x2)выполняется неравенство f(t1x1+t2x2)≥t1f(x1)+t2f(x2) при любых t1≥0, t2≥0таких, что t1+t2=1). Тогдасуммарные затраты /> и целевая функция /> также вогнутые функции от переменных />
Если /> общая суммазатрат, то вогнутость функций Z означает,что каждая дополнительная единица продукции (производимая, хранимая) стоит небольше предыдущей. Подобная ситуация чаще всего встречается в производстве.
Модельзадачи с вогнутыми функциями затрат на производство и хранение называется динамической моделью экономически выгодного размерапартии .
Вогнутостьфункции производственных затрат встречается, например, в случае, если выпускпродукции связан с затратами на дополнительную операцию, переналадкуоборудования или освоение нового оборудования. После этой подготовительнойстадии процесса производства (больших единовременных затрат) выпуску каждойдополнительной единицы продукции соответствуют не меняющиеся пропорциональныезатраты.
Другимпримером может служить модель задачи пополнения запасов у внешнего поставщика,который нередко делает скидки в зависимости от размера закупаемой партии,назначает ступенчатые цены.
Например,функция
/>
являетсявогнутой, так как коэффициент при xh убывает сростом xh
Известно,что глобальный минимум вогнутой функции достигается по крайней мере в одной изугловых точек области. В рассмотренном выше случае область задана системой п линейныхуравнений (5.3). и условиями неотрицательности (5.4) и (5.5). Угловым точкамобласти соответствуют опорные решения системы (5.3); в каждом из которых неболее чем п переменных xk и />положительны,а остальные равны нулю. Предположим, что все />. Тогда, прилюбом k, если />, то />, а если />, то />, иначенечем будет обеспечить расход dk к концу k-гo периода.Одновременно невозможно, чтобы />,так как при этом в опорном решении системы (5.3) оказалось быболее чем п положительныхсоставляющих.
Изуравнения состояния (5.8) получим
/>
Припроведении условной оптимизации на k-м шагесогласно уравнению (5.7) достаточно сравнить и выбрать наименьшее из двухзначений в указанных двух точках, которые принимает выражение, содержащееся вфигурных скобках:
/>
Для 1-гошага (k=1) имеем /> и,следовательно,
/>
Оптимальноеуправление пополнением запасов xk на любом k-м шагеимеет следующий вид: />
/>
Задача 2.Определить оптимальное пополнение запасов в течение четырех периодов приследующих условиях: /> пополнениезапасов может производиться партиями, кратными 50; функции затрат на хранение /> и напополнение />, одинаковые для всех периодов времени,заданы в табл. 2:
/>
Задача носитдискретный характер. Для упрощения, поскольку расход и пополнение кратны 50,расчеты будем вести в целых партиях. Таким образом, d1 = 3, d2=l, d3 = 2, d4 = 2, переменные xh и параметры /> меняются сшагом в единицу. Вычисления выполняем в соответствии с моделью, приведенной взадаче 1. Как обычно, при выполнении первого этапа расчеты производим втаблицах: основной (табл. 3) и вспомогательных (табл. 4—7).
Для 1-гошага имеем единственное значение /> />. Поэтому
/>
Прежде чемперейти к табулированию, определим предельные значения для параметровсостояния. Так как />, то даже при /> должно быть/>,следовательно, />.Соответственно />
В заключениенастоящей главы рассмотрим тип задач, названных выше задачами складирования.
Особенностьюэтих задач является наличие двух переменных управления (двумерная модель).Однако решение этих задач значительно упрощается благодаря линейности целевойфункции.
Задача 3. Емкость склада по хранению запасов ограничена некоторойвеличиной с. В каждом из п промежутковвремени запасы могут пополняться с затратами /> на единицупродукции и расходоваться с получением дохода /> за единицупродукции, причем решение о пополнении или расходовании запасов принимаетсяоднократно в каждом промежутке времени. Определить оптимальную стратегию вуправлении запасами из условия максимизации суммарной прибыли при заданномначальном уровне запасов.
Уточнимпостановку задачи. Возможны три варианта в очередности пополнения ирасходования запасов в каждом из промежутков времени: I вариант — пополнениепредшествует расходу; II вариант — расход предшествует пополнению и III вариант— очередность любая.
В IIIварианте выбор оптимальной стратегии означает не только определение размерапополнения и расхода, но и выбор оптимальной очередности в каждом изпромежутков времени.
Указанныеварианты условия отразятся на форме ограничений модели задачи.
Составимдинамическую модель задачи. Рассмотрим n-шаговыйпроцесс, понимая под k-м шагом промежуток времени, в которомпринимается решение о пополнении или расходовании запасов (k= 1, 2,..., п).
В качествепараметров состояния /> примем запастоваров в начале k-гoшага. Переменными управления служат размеры пополнения (хк) и расхода (ук) запасов на k-мшаге. Тогда уравнение состояния, выражающее материальныйбаланс запасов, запишется в виде
/>(5.11)
Будем решатьзадачу с помощью обратной вычислительной схемы, т. е. используя рекуррентныесоотношения в виде
/>(5.12)
/>(5.13)
Переменныезадачи должны удовлетворять условиям неотрицательности:
/>(5.14)
идополнительным ограничениям для всех k,зависящих от варианта постановки задачи:
/>(5.15)
/>(5.15’)
III вариант:или (5.15), или (5.15').
Первыенеравенства в (5.15) и (5.15') диктуются ограниченной емкостью склада, вторые —условием, согласно которому расход не может превышать наличные запасы. Для III вариантаальтернативные условия означают, что если будет принято решение сначалапополнить запасы, а затем их расходовать, то должны выполняться условия (5.15);если же будет принят противоположный порядок, то должны выполняться условия(5.15').
Решениезадач условной максимизации по двум переменным согласно рекуррентнымсоотношениям (5.12) и (5.13) в общем случае представляет собой сложную задачу,однако линейность функций
/>и />
максимумыкоторых определяются на каждом шаге, а также ограничений, налагаемых напеременные, позволяет значительно упростить решение всех этих частных задач.
Рассмотримподробнее решение задачи в I варианте постановки. Ограничения (5.14) и (5.15)определяют при данном значении параметра /> область допустимых значений Хk и Ук в виде выпуклого четырехугольника ABCD, изображенную на рис. 6. Так как вэтой области максимизируется линейная функция, то получается задача линейногопрограммирования, оптимальное решение которой достигается, по крайней мере, водной из вершин области. На рис. 6 находим координаты всех четырех вершин: /> />. Поэтому вместо нахождения максимумапо соотношениям (3.12) и (3.13) при произвольных изменениях />достаточновычислить значения выражений, содержащихся в фигурных скобках, во всех четырехвершинах и путем сравнения выбрать среди них наибольшее.
При этом дляпоследнего (n-го) шагаможно ограничиться выбором из двух альтернатив, так как значение /> в точках А и D дает заведомо меньшее число, чем соответственнов точках В ч С.
Итак, для n-го шагаполучаем
/>(5.12’)
Длявыполнения оптимизации на последующих шагах предварительно найдем из уравнения(5.11) значение /> для каждойточки. Тогда получим: /> в точке А; /> в точке />в точке /> в точке D.Вместо соотношения (5.13) получаем
/>(5.13’)
Привыполнении практических расчетов оказывается достаточным не табулироватьфункции /> Для всех значений />, аограничиться вычислением этих функций лишь для крайних значений /> т. е. для /> />
В случае IIварианта исходной постановки задачи получим область, изображенную на рис. 7. Вновой области изменятся лишь координаты вершины С; находим />. Аналогичнопредыдущему получим следующие формулы для выполнения условной максимизации:
/>(5.12’’)
/>(5.13’’)
Наконец, приIII варианте постановки задачи на каждом шаге мы должны выбрать наибольшеечисло по формулам (3.12'), (3.13') и сравнить его с наибольшим числом,найденным по формулам (3.12"), (3.13"). Сопоставив полученные такимобразом два значения /> выбираем из них наибольшее. Это иесть окончательное выражение для /> Одновременно, в зависимости от того,к какому из вариантов относится найденный максимум, устанавливается выгодная наданном шаге очередность пополнения и расхода запасов.
Посколькувыражение (3.12") содержится среди альтернатив выбора по формуле (3.12'),для k-го шагадостаточно производить выбор только по соотношению (3.12').
Аналогично,так как среди четырех альтернатив в формуле (3.13") только третьяальтернатива отличается от выбираемых по формуле (3.13'), то достаточнопроизводить выбор по формуле (3.13'), добавив пятую альтернативу.2.2.6 Задача о замене
Одной изважных экономических проблем, с которыми приходится встречаться на практике,является определение оптимальной стратегии в замене старых станков,производственных зданий, агрегатов, машин и т. д., другими словами, старогооборудования — на новое.
Старениеоборудования включает его физический и моральный износ, в результате чегорастут производственные затраты по выпуску продукции на старом оборудовании,увеличиваются затраты на его ремонт и обслуживание, а вместе с тем снижаютсяпроизводительность и так называемая ликвидная стоимость.
Наступаетмомент, когда старое оборудование более выгодно продать, заменить новым, чемэксплуатировать ценой больших затрат. При этом оборудование можно заменить либоновым оборудованием того же вида, либо новым, более совершенным в техническомотношении, с учетом технического прогресса.
Оптимальнаястратегия замены оборудования состоит в определении оптимальных сроков замены.Критерием оптимальности при определении сроков замены может служить либоприбыль от эксплуатации оборудования, которую следует максимизировать, либосуммарные затраты на эксплуатацию в течение рассматриваемого промежуткавремени, подлежащие минимизации. Известно, что при заданном плане выпускапродукции максимизация прибыли эквивалентна минимизации затрат. Практическиудобнее пользоваться вторым критерием, вводя для учета сниженияпроизводительности условно приведенные затраты.
Условимсясчитать, что решения о замене оборудования принимаются периодически в началекаждого промежутка (года, месяца, недели и т. д.), на которые разбит плановыйпериод. Предположим также, что оборудование может использоваться неограниченнодолго, если тратить достаточные суммы на его ремонт.
Основнойхарактеристикой оборудования является его возраст. От возраста оборудованиязависят эксплуатационные расходы, затраты на производство, производительность иликвидная стоимость. Эти показатели изменяются, если учитывать техническийпрогресс, не только при замене старого оборудования новым, с новымитехнико-экономическими характеристиками, но и новым того же типа, еще неиспользованным. В последнем случае изменение вызвано моральным износом.
Метод ДПобеспечивает единый подход к решению всех видов задач о замене.
Присоставлении модели ДП мы рассматриваем процесс замены как n-шаговый,разбив весь плановый период на ппромежутков. Так как в начале каждого из этих промежутковпринимается решение либо о сохранении оборудования, либо о его замене, тоуправление на k-м шаге (k=l,..., п)содержит всего лишь две альтернативные переменные. Обозначимчерез ис решение,состоящее в сохранении старого оборудования, а через и3 — решение, состоящее в замене старогооборудования новым. Функциональные уравнения, благодаря наличию двухальтернативных управлений на каждом шаге, содержат лишь две величины: однавыражает условную прибыль (условные затраты) при управлении uс, другая —тот же показатель при управлении из.Условная оптимизация на каждом шаге состоит в вычислении двухвеличин и в выборе из них наибольшей (наименьшей). Это значительно упрощаетрасчеты на стадии условной оптимизации и позволяет решать вручную задачи озамене с большим числом шагов.
Рассмотримдве модели ДП задачи о замене оборудования. В одной из них в качествепоказателя эффективности выберем прибыль, которую следует максимизировать, вдругой — суммарные затраты на эксплуатацию, которые следует минимизировать.
Задача 1.Определить оптимальные сроки замены оборудования в течение п лет, при которых прибыль отэксплуатации оборудования максимальна, если известны: р — начальная стоимость оборудования; f(t)—стоимость производимой продукции на оборудовании возраста t лет; r(t)—ежегодные затраты на эксплуатацию оборудования возраста t лет; />—ликвиднаястоимость оборудования возраста tлет. .
Рассмотрим n-шаговыйпроцесс, считая k-м шагомномер k-гoгода от начала эксплуатации (k=l, 2, ..., п). Выше указывалось, что управление на k-м шагевыбирается из двух возможных решений: uс — сохранитьи продолжать использование старого оборудования или и3 — заменить оборудование новым.
Будемсчитать, что в начале планового периода возраст оборудования равен t0. Состояние /> -системы (оборудования) в начале k-ro шага характеризуется одним параметром/> — возрастомоборудования. Для k-ro шагапараметр состояния t может принимать значения 0,1, 2, ...,k—1, т. е. t≤k-1
Если кначалу k-гoшага система находилась в состоянии />, то подвлиянием управления исв конце k-гo шага она перейдет в состояние /> возрастоборудования увеличится на один год. Под влиянием управления и3, принятого на k-мшаге, система перейдет в состояние /> (заменупроизвели в начале k-гoгода; в конце k-го годавозраст нового оборудования равен одному году).
Уравнениесостояния (1.2) для данного процесса имеет вид
/>(6.1)
Определимприбыль на k-м шаге (показатель эффективности k-гo шага), соответствующую каждому изальтернативных управлений иси и3.Выбирая на k-мшаге управление ис,мы сможем произвести продукции стоимостью f(t)на старом оборудовании, что потребует затрат r(t),поэтому прибыль равна f(t)—r(t).Обозначим ее через
/>(6.2)
Приуправлении и3 получимдоход /> от продажистарого оборудования (ликвидную стоимость) и f(0) отпроизведенной на новом оборудовании продукции, затратив р на приобретение нового оборудования иr(0) на содержание новогооборудования. В этом случае прибыль (обозначим ее через />) составляет
/>(6.3)
Построимобратную вычислительную схему решения данной задачи методом ДП.
Обозначимчерез /> условную максимальную прибыль,полученную за n—k+l шагов использования оборудования с k-гo по n-й шагвключительно, если к k-му шагу возраст оборудования составлял /> лет, приусловии, что был выбран оптимальный режим эксплуатации. Соответствующееусловное оптимальное управление на k-мшаге обозначим через />.Условный максимальный доход за последний n-йпромежуток составляет
/>(6.4)
Сравнив этидве величины для всех возможных значений t и соответствующие значения />. Предположим, что для всех значений /> известна максимальная прибыль,полученная за n—k шагов с (k+1)-гo по n-йвключительно. Поэтому основные рекуррентные соотношения можно записать в виде
/>(6.5)
В уравнении(6.5) величина />—условнаямаксимальная прибыль, полученная за n—k шагов, если к началу (k+l)-гo шага система находилась в состоянии /> (возрастоборудования составлял один год).
•Процессусловной оптимизации на каждом шаге, начиная с n-го,сводится к сравнению двух величин в уравнениях (6.4) и (6.5) и выборунаибольшей из них. Этап условной оптимизации заканчивается, как обычно,получением последовательностей функций />
На этапебезусловной оптимизации для /> (возраст оборудования в началепроцесса) получаем /> />, а далее поцепочке: />, из (6.1) находим />,, откуда />, и т. д.Оптимальное управление /> представляетсобой набор управлений uс и и3.
Замечание. Взадаче 1 не рассматривался вопрос о том, чтопроисходит с оборудованием после п лет его эксплуатации. Можнопредположить, что п неограниченно велико и, рассматриваяпроцесс для достаточно большого значения п, получитьзакономерность в оптимальном управлении в виде периодически повторяющихсяциклов замены и использования старого оборудования, (такой пример будетрассмотрен ниже). Можно также предположить, что после л лет использованияоборудование продается и ликвидная стоимость присоединяется к общей прибыли. Вовтором случае уравнения (6.4) принимают вид
/>(6.6)
Рассмотримнекоторую модификацию задачи 1.
Задача 2. Взадаче 1 предположим, что ежегодные затраты наэксплуатацию, ликвидная и начальная стоимость зависят не только от возрастаоборудования t, но и от времени, прошедшего с началапроцесса. Пусть rh{t)—затраты на эксплуатацию в течение k-гo года, еслисо времени последней замены прошло t лет; />—ликвиднаястоимость оборудования возрастав лет, если оно продается в начале k-гo года; рk — начальнаястоимость оборудования, если оно куплено в начале k-гo года.
Требуетсяопределить оптимальные сроки замены старого оборудования новым в течение п лет с тем,чтобы минимизировать затраты на его содержание.
Показательэффективности в данной задаче — суммарные затраты на эксплуатацию оборудования.Затраты на k-м шаге, как и прежде, зависят отвыбранного управления. При управлении иk= ис эти затраты равны />, а приуправлении иk =u3 составляют /> />
Пусть Zk*{t)—условные минимальныезатраты за n—k+1 шагов с k-гo по n-йвключительно, если к началу k-гo шага возраст оборудования составлял t лет, приусловии, что был выбран оптимальный режим эксплуатации.
Рекуррентныесоотношения для Zk*{t)имеют вид
/>(6.7)
Для n-го шагасоответственно получим
/>(6.8)
Вычислительныйпроцесс строится как и в предыдущей задаче.
Введение вусловие задачи функций, оценивающих затраты, выпуск продукции и стоимость,зависящие не только от возраста t,но и непосредственно от k,т. е. от времени, прошедшего с начала процесса, являетсякосвенным способом учета технического прогресса.
Как ужеотмечалось неоднократно, модели ДП очень гибки и в смысле возможностей анализачувствительности к вариации исходных данных, и в смысле возможностей включенияв модель различных модификаций задачи. Так, например, аналогичная модель можетбыть построена для задач, в которых ежегодно рассматривается более двухвариантов управления («сохранение», «замена», «реконструкция» и т. д.). Можнорассматривать задачи, в которых затраты или прибыль зависят не только отвозраста оборудования, но и еще от одного параметра, например, времени,прошедшего после восстановительного ремонта, и т. д.
Замечание.Если функции затрат, ликвидная и начальная стоимости в задаче 2 зависят отвремени τ, прошедшегос начала эксплуатационного периода, и τ несовпадает с k, то состояние системы следуетхарактеризовать двумя параметрами τ и t.
В заключениеглавы рассмотрим задачу определения оптимальной стратегии замены оборудованияпри бесконечном плановом периоде.
Задача 3.Определить оптимальные сроки замены оборудования при неограниченном времени егоиспользования, если известны: р— начальная стоимость; r(t)— эксплуатационные затраты на содержание оборудования возраста t лет в течение ближайшего года; /> —ликвиднаястоимость оборудования возраста tлет.
В задачебудем минимизировать затраты. Параметр состояния есть время: />. Процесс, является бесконечным,поэтому условные минимальные затраты /> за все последующее время, начиная с k-гo года, зависят только от /> и не зависятот k.
Прирассмотрении бесконечного процесса необходимо ввести так называемый дисконтирующий множитель 0 руб.Наоборот, конечную сумму аруб. через плет можно получить от первоначальной суммы />руб.Множитель />называется коэффициентом дисконтирования.
Учитываяэтот множитель и повторяя весь ход рассуждений, изложенный в предыдущих задачах,получим следующие функциональные уравнения:
/>(6.9)
Посколькуконечного шага нет, обратный ход выпол-. нить нельзя, поэтому решим уравненияявно следующим образом.
Для1-го шага имеем />, поэтому
/>
Так как /> товыражение, стоящее в первой строке, всегда не больше выражения во второйстроке. Поэтому />, что соответствует сохранениюоборудования.
Пустьоптимальным является решение о сохранении для первых N шагов и о замене на (N+1)-м шаге. Задача состоит в определенииэтого числа N. Запишемпоследовательность рекуррентных соотношений для этих N шагов:
/>
Исключив изэтих равенств последовательно Z*(2),Z*(3), …получим
/>(6.10)
Но для (N+ 1)-го шагапо предположению оптимальным является решение о замене оборудования,следовательно,
/>
Подставляязначение Z*(N) в равенство (6.10) и разрешаяполученное при этом уравнение относительно Z*(0), найдем
/>(6.11)
Величина Z*(0) равна необходимому минимумузатрат на весь процесс. Теперь, полагая последовательно N = 1, 2, 3,… вычисляем значение Z*(0) инаходим среди них наименьшее.
Заключение
В данной курсовой работерассмотрены виды математических моделей, используемых в экономике именеджменте, а также их классификация.
Особое внимание в курсовой работеуделено оптимизационному моделированию.
Изучен принцип построения моделейлинейного программирования, также приведены модели следующих задач:
· Задачао раскрое материалов;
· Задачавыбора оптимальной производственной программы предприятия;
· Задачао диете;
· Транспортнаязадача.
В работе представлены общиехарактеристики задач дискретного программирования, описан принцип оптимальностии уравнение Беллмана, приведено общее описание процесса моделирования.
Для построения моделей выбраны тризадачи:
· Задачаоптимального распределения ресурсов;
· Задачаоб оптимальном управлении запасами;
· Задачао замене.
В свою очередь для каждой из задачпостроены различные модели динамического программирования. Для отдельных задачприведены числовые расчеты, в соответствии с построенными моделями.
Список литературы:
1. ВавиловВ.А., Змеев О.А., Змеева Е.Е. Электронное пособие “Исследование операций”
2. КалихманИ.Л., Войтенко М.А. “Динамическое программирование в примерах и задачах”,Москва ”Высшая школа”, 1979
3. КосоруковО.А., Мищенко А.В. “Исследование операций”, Москва, 2003
4. Материалыиз сети Internet.