Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
PAGE 23
математическое моделирование в экономике
Тема 1. Математические модели в экономике
§1. Общие понятия
Рассмотрим процессы математического моделирования применительно к экономическим объектам и процессам. И в этом случае, естественно, применимы общие подходы (системный подход, кибернетическое моделирование). В то же время при моделировании экономических явлений следует учитывать их специфику, например, при выборе методов моделирования, при формировании информационного обеспечения.
Практическими задачами экономико-математического моделирования являются:
• анализ функционирования и развития экономических объектов и процессов;
• экономическое прогнозирование, предвидение развития экономических процессов;
• выработка управленческих решений на всех уровнях хозяйственной деятельности.
Важнейшим понятием при экономико-математическом моделировании, как и при всяком моделировании, является понятие адекватности модели, т. е. соответствия модели мо делируемому объекту или процессу. Адекватность модели - в какой-то мере условное понятие, так как полного соответствия модели реальному объекту быть не может, что характерно и для экономико-математического моделирования. При моделиро вании имеется в виду не просто адекватность, но соответствие по тем свойствам, которые считаются существенными для ис следования. Проверка адекватности экономико-математиче ских моделей является весьма серьезной проблемой, тем более, что ее осложняет трудность измерения экономических величин. Однако без такой проверки применение результатов модели рования в управленческих решениях может не только ока заться мало полезным, но и принести существенный вред.
Социально-экономические системы относятся, как правило, к так называемым сложным системам. Сложные системы в экономике обладают рядом свойств, которые необходимо учитывать при их моделировании, иначе невозможно гово рить об адекватности построенной экономической модели. Важнейшие из этих свойств:
- эмерджентность;
- массовый характер экономических явлений и процессов;
- динамичность экономических процессов;
- случайность и неопределенность в развитии экономиче ских явлений;
- невозможность изолировать протекающие в экономиче ских системах явления и процессы от окружающей сре ды;
- активная реакция на появляющиеся новые факторы, спо собность социально-экономических систем к активным, не всегда предсказуемым действиям.
Указанные свойства социально-экономических систем усложняют процесс их моделирования, однако их следует постоянно иметь в виду при рассмотрении различных аспектов экономико-математического моделиро вания, начиная с выбора типа модели и кончая вопросами практического использования результатов моделирования. То есть эти свойства диктуют необходимость использования системного подхода при моделировании достаточно сложных экономических явлений.
§2. Этапы экономико-математического моделирования
Перейдем теперь к процессу экономико-математического моделирования, то есть описания экономиче ских и социальных систем и процессов в виде экономико-математических моделей. Эта разновидность моделирования, как уже указывалось, обладает рядом существенных особенностей, связанных как с объектом моделирования, так и с применяемыми аппара том и средствами моделирования. Поэтому проанализируем последовательность и содер жание этапов экономико-математического моделирования, выделив следующие шесть этапов:
- постановка экономиче ской проблемы, ее качественный анализ;
- построение мате матической модели;
- математический анализ модели;
- подго товка исходной информации;
- численное решение;
- анализ численных результатов, их интерпретации и применение.
Рассмотрим перечисленные этапы экономико-математического моделирования подробнее.
1. Постановка экономической проблемы и ее качествен ный анализ.
На этом этапе требуется сформулировать сущность проблемы, принимаемые предпосылки и допу щения. Необходимо выделить важнейшие черты и свой ства моделируемого объекта, изучить его структуру и взаимосвязь его элементов, хотя бы предварительно сформулировать гипотезы, объясняющие поведение и развитие объекта.
2. Построение математической модели.
Это этап формали зации экономической проблемы, т. е. выражения ее в виде конкретных математических зависимостей (функ ций, уравнений, неравенств и др.). Построение модели подразделяется в свою очередь на несколько стадий. Сначала определяется тип экономико-математической модели, изучаются возможности ее применения в данной задаче, уточняются конкретный перечень переменных и параметров и форма связей. Для некоторых сложных объектов целесообразно строить несколько разноаспектных моделей; при этом каждая модель выделяет лишь некоторые стороны объекта, а другие стороны учитыва ются агрегированно и приближенно. Оправдано стремле ние построить модель, относящуюся к хорошо изученному классу математических задач, что может потребовать не которого упрощения исходных предпосылок модели, не искажающего основных черт моделируемого объекта. Однако возможна и такая ситуация, когда формализа ция проблемы приводит к неизвестной ранее математи ческой структуре.
3. Математический анализ модели.
На этом этапе чисто математическими приемами исследования выявляются общие свойства модели и ее решений. В частности, важ ным моментом является доказательство существования решения сформулированной задачи. При аналитическом исследовании выясняется, единственно ли решение, ка кие переменные могут входить в решение, в каких пре делах они изменяются, каковы тенденции их изменения и т. д. Однако модели сложных экономических объек тов с большим трудом поддаются аналитическому ис следованию; в таких случаях переходят к численным методам исследования.
4. Подготовка исходной информации.
В экономических задачах это, как правило, наиболее трудоемкий этап мо делирования, так как дело не сводится к пассивному сбору данных. Математическое моделирование предъявляет жесткие требования к системе информации; при этом надо принимать во внимание не только принципиаль ную возможность подготовки информации требуемого качества, но и затраты на подготовку информационных массивов. В процессе подготовки информации использу ются методы теории вероятностей, теоретической и ма тематической статистики для организации выборочных обследований, оценки достоверности данных и т.д. При системном экономико-математическом моделировании результаты функционирования одних моделей служат исходной информацией для других.
5. Численное решение.
Этот этап включает разработку ал горитмов численного решения задачи, подготовку про грамм на компьютере и непосредственное проведение расчетов; при этом значительные трудности вызываются большой размерностью экономических задач. Обычно расчеты на основе экономико-математической модели носят много вариантный характер. Многочисленные модельные экс перименты, изучение поведения модели при различных условиях возможно проводить благодаря высокому бы стродействию современных вычислительных средств. Численное решение существенно дополняет результаты аналитического ис следования, а для многих моделей является единствен но возможным.
6. Анализ численных результатов, их интерпретация и применение.
На этом этапе, прежде всего, решается важнейший вопрос о правильности и полноте результатов моделирования и применимости их как в практической деятельности, так и в целях усовершенствования модели. Поэтому в первую очередь должна быть проведена проверка адек ватности модели по тем свойствам, которые выбраны в качестве существенных (другими словами, должны быть произведены верификация и валидация модели). Интерпретация и при менение результатов моделирования в эко номике направлено на решение практических задач (анализ экономических объектов, экономическое прогнозирование развития хозяйственных и социальных процессов, выработка управленческих решений на всех уровнях хозяйственной иерархии).
Отметим, что верификация модели – это проверка правильности структуры (логики) модели; валидация модели — проверка соответствия данных, получен ных на основе модели, реальному процессу.
Перечисленные этапы экономико-математического моде лирования находятся в тесной взаимосвязи, в частности, мо гут иметь место возвратные связи этапов. Так, на этапе по строения модели может выясниться, что постановка задачи или противоречива, или приводит к слишком сложной ма тематической модели; в этом случае исходная постановка задачи должна быть скорректирована. Наиболее часто необ ходимость возврата к предшествующим этапам моделирова ния возникает на этапе подготовки исходной информации. Если необходимая информация отсутствует или затраты на ее подготовку слишком велики, приходится возвращаться к этапам постановки задачи и ее формализации, чтобы при способиться к доступной исследователю информации.
Процесс моделирование имеет циклический характер. Недостатки, которые не удается исправить на тех или иных этапах моделирования, устраняются в по следующих циклах. Однако результаты каждого цикла име ют и вполне самостоятельное значение. Начав исследование с построения простой модели, можно получить полезные ре зультаты, а затем перейти к созданию более сложной и более совершенной модели, включающей в себя новые условия и более точные математические зависимости.
Следует иметь в виду, что далеко не во всех слу чаях данные, полученные в результате экономико-математи ческого моделирования, могут использоваться непосредст венно как готовые управленческие решения. Они скорее мо гут быть рассмотрены как «консультирующие» средства. Принятие управленческих решений остается за человеком. Таким образом, экономико-математическое моделирование является лишь одним из компонентов (пусть очень важным) в человеко-машинных системах планирования и управления экономическими системами.
Моделирование представляет собой циклический про цесс, то есть за первым циклом из указанных этапов (всех или части) может после довать второй, третий и т. д. При этом знания об исследуемом экономическом объекте или процессе расширяются и уточняются, а первоначально постро енная модель постепенно совершенствуется. Таким образом, в методологии моделирования заложены большие возможно сти самосовершенствования.
Математическое моделирование сложных экономических систем является весьма сложным и неоднозначным процессом, который требует определенных ресурсов. Тем не менее, его рациональное применение является одним из факторов повышения конкурентоспособности экономических систем, особенно учитывая возможности, предоставляемые современными информационными технологиями.
Тема 2. Моделирование экономической динамики
§1. Экономические ряды динамики
Динамические процессы, происходящие в экономических системах, чаще всего проявляются в виде ряда последова тельно расположенных в хронологическом порядке значе ний того или иного показателя, который в своих изменени ях отражает ход развития изучаемого явления в экономике.
Последователь ность наблюдений одного показателя, упорядо ченных в зависимости от последовательно возрастающих или убывающих значений другого показателя, называют динамическим рядом, или рядом динамики. Если в качестве признака, в зависимости от которого происходит упорядочение, берется время, то такой динамический ряд называется временным рядом.
Так как в экономических процессах, как правило, упорядочение происходит в соответ ствии со временем, то при изучении последовательных наблюдений экономических показателей все три приведенных выше термина используются как равнозначные. Составными элементами рядов динамики являются, таким образом, циф ровые значения показателя, называемые уровнями этих рядов, и моменты или интервалы времени, к которым относятся
уровни.
Временные ряды, образованные показателями, характе ризующими экономическое явление на определенные мо менты времени, называются моментными; если уровни временного ряда образуются путем агреги рования за определенный промежуток (интервал) времени, то такие ряды называются интервальными временными ря дами.
Временные ряды могут быть образованы как из абсолют ных значений экономических показателей, так и из средних или относительных величин.
Под длиной временного ряда понимают время, прошедшее от начального момента наблюдения до конечного. Часто длиной ряда называют ко личество уровней, входящих во временной ряд.
Если во временном ряду проявляется длительная («веко вая») тенденция изменения экономического показателя, то говорят, что имеет место тренд. Таким образом, под трендом понимается изменение, определяющее общее направление развития, основную тенденцию временных рядов. В связи с этим экономико-математическая динамическая модель, в которой развитие моделируемой экономической системы отражается через тренд ее основных показателей, называется трендовой моделью.
Отличие временных экономических рядов от простых статистических совокупностей заключается, прежде всего, в том, что последовательные значения уровней вре менного ряда зависят друг от друга. Поэтому применение выводов и формул теории вероятностей и математической статистики требует известной осторожности при анализе временных рядов, особенно при экономической интерпретации результатов анализа.
Предположим, имеется временной ряд, состоящий из п уровней:
у1, у2,…, yn.
В самом общем случае временной ряд экономических показателей можно разложить на четыре структурно обра зующих элемента:
• тренд, составляющие которого будем обозначать Ut, t = l,2,...,n;
• сезонная компонента, обозначаемая через Vt, t = 1,2,...,n;
• циклическая компонента, обозначаемая через Ct, t= 1,2,..., n;
• случайная компонента, которую будем обозначать εt, t= 1,2,..., n.
Под трендом, как уже отмечалось, понимается ус тойчивое систематическое изменение процесса в течение продолжительного времени.
Во временных рядах экономических процессов могут иметь место более или менее регулярные колебания. Если они носят строго периодический или близкий к нему ха рактер и завершаются в течение одного года, то их называют сезонными колебаниями. В тех случаях, когда период коле баний составляет несколько лет, то говорят, что во времен ном ряде присутствует циклическая компонента.
Тренд, сезонная и циклическая компоненты называются регулярными, или систематическими компонентами времен ного ряда. Составная часть временного ряда, остающаяся по сле выделения из него регулярных компонент, представляет собой случайную, нерегулярную компоненту. Она является обязательной составной частью любого временного ряда в экономике, так как случайные отклонения неизбежно сопут ствуют любому экономическому явлению. Если системати ческие компоненты временного ряда определены правильно, что как раз и составляет одну из главных целей при разра ботке трендовых моделей, то остающаяся после выделения из временного ряда этих компонент так называемая остаточная последовательность (ряд остатков) будет случайной компо нентой ряда, т.е. будет обладать следующими свойствами:
• случайностью колебаний уровней остаточной последова тельности;
• соответствием распределения случайной компоненты нормальному закону распределения;
• равенством математического ожидания случайной ком поненты нулю;
• независимостью значений уровней случайной последо вательности, то есть отсутствием существенной авто корреляции.
Проверка адекватности трендовых моделей основана на проверке выполняемоемости у остаточной последовательности указанных четырех свойств. Если не выполняется хотя бы одно из них, модель признается неадекватной; при выполне нии всех четырех свойств модель адекватна.
Данная проверка осуществляется с использованием ряда статистических критериев.
§2. Предварительный анализ и сглаживание временных рядов экономических показателей
Предварительный анализ временных рядов экономиче ских показателей заключается в основном в выявлении и устранении аномальных значений уровней ряда, а также в определении наличия тренда в исходном временном ряде.
Под аномальным уровнем понимается отдельное значение уровня временного ряда, которое не отвечает потенциаль ным возможностям исследуемой экономической системы и которое, оставаясь в качестве уровня ряда, оказывает суще ственное влияние на значения основных характеристик вре менного ряда, в том числе на соответствующую трендовую модель. Причинами аномальных наблюдений могут быть ошибки технического порядка, или ошибки первого рода: ошибки при агрегировании и дезагрегировании показателей, при передаче информации и другие технические причины. Ошибки первого рода подлежат выявлению и устранению. Кроме того, аномальные уровни во временных рядах могут возникать из-за воздействия факторов, имеющих объектив ный характер, но проявляющихся эпизодически, очень ред ко – ошибки второго рода; они устранению не подлежат.
Для выявления аномальных уровней временных рядов используются специальные методы для статистических со вокупностей.
§3. Расчет показателей динамики развития экономических процессов
Расчет проводится на основе статистического анали за одномерных временных рядов экономической динамики. Для статистического анализа одномерных временных рядов экономических показателей вида
у1, у2,…, yn
абсолютные уровни моментных и интервальных рядов, а также уровни из средних величин должны быть преобразованы в отно сительные величины. Их можно получить соотнесением уровней ряда с одним и тем же уровнем, взятым за базу (за базу сравнения чаще всего принимают начальный уро вень временного ряда ), либо последовательными сопостав лениями с предыдущим уровнем. В первом случае получают базисные показатели, во втором – цепные.
Временной ряд тогда правильно отражает объективный процесс развития экономического явления, когда уровни этого ряда состоят из однородных, сопоставимых величин. Для несопоставимых величин вести расчет рассматриваемых ниже статистических показателей динамики неправомерно. Причины несопоставимости уровней временного ряда могут быть различными. В экономике чаще всего такими причи нами является несопоставимость:
• по территории ввиду изменения границ региона, по кото рому собираются статистические данные;
• по кругу охватываемых объектов по подчинению или форме собственности ввиду перехода, например, части предприятий данного объединения в другое объединение;
• по временным периодам, когда, например, данные за раз личные годы приведены по состоянию на разные даты;
• уровней, вычисленных в различном масштабе измерения;
• уровней ряда из-за различий в структуре совокупности, для которой они вычислены.
Возможны и другие причины несопоставимости.
При анализе временных рядов для определения измене ний, происходящих в данном явлении, прежде всего, вычис ляют скорость развития этого явления во времени. Показа телем скорости служит абсолютный прирост, вычисляемый по формуле
(1)
где yi — i-й уровень временного ряда (i = 2,3, ..., n); индекс k = 1,2, ..., n-1 определяет начальный уровень и может быть выбран любым в зависимости от целей исследования: при k = 1 получаются цепные показатели, при h = i-1 получаются базисные показатели с начальным уровнем ряда в качестве базисного и т. д.
Абсолютный прирост выражает величину изменения по казателя за интервал времени между сравниваемыми перио дами. Если подходить более строго, то скоростью называют прирост в единицу времени; эта величина носит название среднего абсолютного прироста:
(2)
В частности, средний абсолютный прирост за весь период наблюдения для данного временного ряда равен
(3)
и характеризует среднюю скорость изменения временного ряда.
Для определения относительной скорости изменения изу чаемого явления в единицу времени используют относительные показатели: коэффициенты роста и прироста (если эти по казатели выражены в процентах, то их называют соответ ственно темпами роста и прироста). Заметим, что во всех последующих формулах индекс начального уровня, по от ношению к которому осуществляется сопоставление, опреде ляется точно так же с помощью индекса k, как и ранее для показателя абсолютного прироста.
Коэффициент роста для i-го периода вычисляется по формуле
(4)
Коэффициент прироста равен
(5)
На практике чаще применяют показатели темпа роста и темпа прироста:
(6)
(7)
Темп прироста показывает, на сколько процентов уро вень одного периода увеличился (уменьшился) по сравнению с уровнем другого периода, т.е. этот показатель выражает относительную величину прироста в процентах.
Абсолютное значение одного процента прироста опреде ляется как отношение абсолютного прироста Δyi к темпу прироста в процентах .
Среднюю скорость изменения изучаемого явления за рас сматриваемый период характеризует также средний темп роста. Обычно он рассчитывается по формуле средней гео метрической:
(8)
Соответственно средний темп прироста определяется как
(9)
Показатель среднего темпа роста, рассчитываемый по приведенной выше формуле средней геометрической, имеет существенные недостатки, так как основан на сопоставлении конечного и начального уровней временного ряда, промежу точные уровни во внимание не принимаются. В случае силь ной колеблемости уровней использование для статистиче ского анализа среднего геометрического темпа роста может привести к серьезным просчетам в результате искажения реальной тенденции временного ряда.
Важной характеристикой временного ряда является также средний уровень ряда. В интервальном ряду динами ки с равноотстоящими во времени уровнями расчет среднего уровня ряда производится по формуле простой средней арифметической (здесь и далее суммирование ведется по всем периодам наблюдения):
(10)
Если интервальный ряд имеет неравноотстоящие во вре мени уровни, то средний уровень ряда (так называемая средняя хронологическая) вычисляется по формуле взве шенной арифметической средней, где роль весов играет продолжительность времени (например, количество лет), в течение которого уровень постоянен:
(11)
Для моментного ряда с равноотстоящими уровнями сред няя хронологическая рассчитывается по формуле:
(12)
где п — число уровней ряда.
Средняя хронологическая для моментного временного ряда с разноотстоящими во времени уровнями вычисляется по формуле:
(13)
Здесь п – число уровней ряда, a ti — период времени, отде ляющий i-й уровень ряда от (i+1)-го уровня.
§4. Тренд-сезонные экономические процессы и их анализ
Влияние сезонности на экономику вполне очевидно и проявляется в аритмии производственных и других процессов: недогрузка производственных мощностей в одни периоды года и более интенсивное их использование в другие; нерав номерное распределение внутри рамок года объемов грузооборота и товарооборота и т.д. Не во всех случаях сезон ность является следствием действия неуправляемых или почти неуправляемых факторов. Чаще всего они поддаются регулированию. Но даже и в тех случаях, когда прямое воз действие на процессы, вызывающие сезонные колебания, не возможно, необходимо учитывать их действие при совершен ствовании технологических, организационно-экономических процессов и процессов управления.
Под сезонными колебаниями понимают регулярные, пе риодические наступления внутригодовых подъемов и спадов производства, грузооборота и товарооборота и т. д., связан ных со сменой времени года, а под сезонностью – ограни ченность годового периода работ под влиянием того же при родного фактора.
Если процесс подвержен периоди ческим колебаниям, имеющим определенный и постоян ный период, равный годовому промежутку, то мы имеем дело с так называемым тренд-сезонным временным рядом.
Будем рас сматривать тренд-сезонный временной ряд у1,…, уТ по рождаемый аддитивным случайным процессом:
уt=Ut+Vt+εt, (14)
где Ut — тренд;
Vt — сезонная компонента;
εt — случайная компонента;
Т — число уровней наблюдения.
Относительно Ut предполагается, что это некоторая гладкая функция. Сезон ная компонента Vt имеет период То: (То = 12 для ря да месячных данных; То = 4 — для ряда квартальных данных).
Кроме того, известно, что То нацело делит Т, т.е. Т = m·То, m — целое число. Очевидно, если То — число месяцев или кварталов в году, то m — число лет, представленных во вре менном ряду.
Кратко охарактеризуем зада чи, возникающие при исследовании сезонности вообще и се зонных временных рядов в частности. Проблема анализа се зонности заключается в исследовании собственно сезонных колебаний и в изучении того внешнего циклического меха низма, который их вызывает. Для исследования сезонных колебаний вне связи с причинами, их порождающими, оче видно, необходимо отфильтровать из временного ряда сезонную компоненту Vt и затем уже анализировать ее ди намику. Большинство методов фильтрации построено таким образом, что предварительно выделяется тренд, а затем уже сезонная компонента. Тренд в чистом виде необходим и для анализа динамики сезонной волны.
Задачи, возникающие при исследовании сезонных временных рядов:
1) определение наличия во временном ряду тренда;
2) выявление наличия во временном ряду сезонных колебаний;
3) фильтрация компонент ряда;
4) анализ динамики сезонной волны;
5) исследование факторов, определяющих сезонные коле бания;
6) прогнозирование тренд-сезонных процессов.
тЕМА 3. лИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
§1. Понятие линейного программирования
Линейное про граммирование – раздел математического программирования, применяемый при разработке методов отыскания экстремума линейных функций нескольких переменных при линейных ограничениях, налагаемых на переменные. По типу решаемых задач его методы разделяются на уни версальные и специальные. С помощью универсальных методов могут решаться любые задачи линейного про граммирования (ЗЛП). Специальные методы учитывают особенности модели задачи, ее целевой функции и системы ограничений.
Особенностью задач линейного программирования является то, что экстремума целевая функция достигает на границе области допустимых решений.
Формы записи задачи линейного программирования:
Общей задачей линейного программирования называют задачу
(1)
при ограничениях
(2)
(3)
(4)
(5)
- произвольные (6)
где - заданные действительные числа; (1) – целевая функция; (1) – (6) –ограничения;
- план задачи.
§2. Графический способ решения ЗЛП
Геометрическая интерпретация экономических задач дает возможность наглядно представить, их структуру, выявить особенности и открывает пути исследования бо лее сложных свойств. ЗЛП с двумя переменными всегда можно решить графически. Однако уже в трехмерном пространстве такое решение усложняется, а в простран ствах, размерность которых больше трех, графическое решение, вообще говоря, невозможно. Случай двух переменных не имеет особого практиче ского значения, однако его рассмотрение проясняет свой ства ЗЛП, приводит к идее ее решения, делает геомет рически наглядными способы решения и пути их практи ческой реализации.
Пусть дана задача
(7)
(8)
(9)
Дадим геометрическую интерпретацию элементов этой задачи. Каждое из ограничений (8), (9) задает на плоскости некоторую полуплоскость. Полу плоскость – выпуклое множество. Но пересечение любого числа выпуклых множеств является выпуклым множест вом. Отсюда следует, что область допустимых решений задачи (7) - (9) есть выпуклое множество.
Перейдем к геометрической интерпретации целевой функции. Пусть область допустимых решений ЗЛП – не пустое множество, например многоугольник .
Выберем произвольное значение целевой функ ции . Получим . Это уравнение пря мой линии. В точках прямой NМ целевая функция сохра няет одно и то же постоянное значение . Считая в ра венстве (7) параметром, получим уравнение семей ства параллельных прямых, называемых линиями уровня целевой функции (линиями постоянного значения).
Найдём частные производные целевой функции по и
(10)
(11)
Частная производная (10) ((11)) функции пока зывает скорость ее возрастания вдоль данной оси. Следо вательно, и — скорости возрастания соответст венно вдоль осей и . Вектор называ ется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции:
Вектор (- ) указывает направление наискорейшего убывания целевой функции. Его называют антигра диентом.
Вектор перпендикулярен к прямым семейства
Из геометрической интерпретации элементов ЗЛП вы текает следующий порядок ее графического решения.
§3. Симплексный метод
Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП состоит:
Симплексный метод может быть реализован и «вручную», однако лучше воспользоваться компьютерными возможностями, например, возможностями Excel.
§4. Двойственность задач
Понятие двойственности рассмотрим на примере зада чи оптимального использования сырья. Пусть на предпри ятии решили рационально использовать отходы основного производства. В плановом периоде появились отходы сырья m видов в объемах единиц . Из этих отходов, учитывая специализацию предприятия, можно наладить выпуск n видов неосновной продукции. Обозна чим через норму расхода сырья i-го вида на единицу j-й продукции, - цена реализации единицы j-й продукции (реализация обеспечена). Неизвестные величи ны задачи: — объемы выпуска j-й продукции, обеспечи вающие предприятию максимум выручки.
Математическая модель задачи:
(1)
(2)
(3)
Предположим далее, что с самого начала при изучении вопроса об использовании отходов основного производст ва на предприятии появилась возможность реализации их некоторой организации. Необходимо установить прикидочные оценки (цены) на эти отходы. Обозначим их .
Оценки должны быть установлены исходя из следующих требований, отражающих несовпадающие интересы предприятия и организации:
Эти требования форма лизуются в виде следующей ЗЛП.
Требование покупающей организации – минимизация покупки: (4)
Требование предприятия, реализующего отходы сырья, можно сформулировать в виде системы ограничений. Предприятие откажется от выпуска каждой единицы продукции первого вида, если , где левая часть означает выручку за сырьё идущее на единицу продукции первого вида; правая – её цену.
Аналогичные рассуждения логично провести в отношении выпуска продукции каждого вида. Поэтому требование предприятия, реализующего отходы сырья, можно формализовать в виде сл. системы ограничений:
(5)
По смыслу задачи оценки не должны быть отрицательными:
(6)
Переменные называют двойственными оценками или объективно обусловленными оценками.
Задачи (1)-(3) и (4)-(6) называют парой взаимно двойственных ЗПЛ.
Между прямой и двойственной задачами можно установить следующую взаимосвязь:
Теорема 1. Для любых допустимых планов и прямой и двойственной ЗЛП справедливо неравенство , т.е.
(7) – основное неравенство теории двойственности.
Теорема 2. (критерий оптимальности Канторовича)
Если для некоторых допустимых планов и пары двойственных задач выполняется неравенство , то и являются оптимальными планами соответствующих задач.
Теорема 3. (малая теорема двойственности)
Для су ществования оптимального плана любой из пары двойст венных задач необходимо и достаточно существование допустимого плана для каждой из них.
§5. Транспортная задача
Многие прикладные модели в эконо мике сводятся к задачам линейного программирования. Практически все задачи линейного программирования можно решить, используя ту или иную модификацию симплексного метода. Однако существуют более эффективные вычислитель ные процедуры решения некоторых типов задач линейного программирования, основанные на специфике ограничений этих задач. Рассмотрим так называемую транспортную задачу по критерию стоимости, которую можно сформули ровать следующим образом.
В т пунктах отправления А1, А2, ...,Ат, которые в даль нейшем будем называть поставщиками, сосредоточено опре деленное количество единиц некоторого однородного про дукта, которое обозначим ai (i = 1, 2, ..., т). Данный про дукт потребляется в п пунктах В1, В2, ..., Вп, которые будем называть потребителями; объем потребления обозначим bj (j = 1, 2, ..., п). Известны расходы на перевозку единицы продукта из пункта Ai в пункт Bj, которые равны cij и при ведены в матрице транспортных расходов С = (cij).
Требуется составить такой план прикрепления потреби телей к поставщикам, т.е. план перевозок, при котором весь продукт вывозится из пунктов Ai в пункты Bj в соответ ствии с потребностью и общая величина транспортных из держек будет минимальной.
Обозначим количество продукта, перевозимого из пункта Ai в пункт Вj, через xij. Совокупность всех переменных xij для краткости обозначим X , тогда целевая функция задачи будет иметь вид
а ограничения выглядят следующим образом:
Первые условия означают полное удовлетворение спроса во всех пунктах потребления; вторые - определяют полный вывоз продукции от всех поставщиков.
Необходимым и достаточным условием разрешимости транспортной задачи является условие баланса:
Транспортная задача, в которой имеет место это равенство, называется закрытой и может быть решена, как за дача линейного программирования с помощью симплексного метода. Однако благодаря особенностям переменных задачи и системы ограничений разработаны специальные, менее громоздкие методы ее решения. Наиболее применяемым ме тодом является метод потенциалов.
Если же условие баланса не выполняется, то имеет место открытая транспортная задача.
Тема 4. Нелинейное программирование
§1. Задача нелинейного программирования
Задача математического программирования
max (min) z = f(х); (1)
φi(x ){≤,=,≥} bi, (i = l,…, m), (2)
x ≥ 0, x = (x1,... ,xn), (3)
в которой либо целевая функция (1), либо ограничения (2-3), либо и то и другое нелинейны, называется нелинейной. Нелинейные задачи составляют широкий класс настолько сложных задач, что до сих пор невозможно разработать об щие методы, подобные симплекс-методу в линейном программировании, которые позволяли бы решать любые нелинейные задачи. Но, несмотря на отсутствие универсальных методов, разработаны способы решения отдельных специальных клас сов задач, и прежде всего задач с выпуклыми (вогнутыми) функциями f(х) и φi(x ).
В теории выпуклого программирования в качестве основ ной обычно рассматривается задача минимизации выпуклой функции п переменных z = f(х) при ограничениях φi(x ) ≤ 0, (i = l,…, m), x ≥ 0, где функции φi(x ) предполагаются выпук лыми.
§2. Метод множителей Лагранжа
Метод множителей Лагранжа является классическим методом решения задач математического программирования (в частности выпуклого). К сожалению, при практическом применении метода могут встретиться значительные вычис лительные трудности, сужающие область его использования.
Мы рассматриваем метод Лагранжа главным образом потому, что он является аппаратом, активно используемым для обоснования различных современных численных методов, широко применяемых на практике.
Рассмотрим классическую задачу оптимизации
(4)
Эта задача выделяется из задачи (1)- (3) тем, что среди ограничений нет неравенств, нет условий неотрицатель ности переменных, их дискретности, т < п и функции f(х) и φi(x ) непрерывны и имеют частные производные по крайней мере второго порядка.
Классический подход к решению задачи (4) дает систему уравнений (необходимые условия), которым должна удовлетворять точка х*, доставляющая функции f(х) локаль ный экстремум на множестве точек, удовлетворяющих огра ничениям задачи (для задачи выпуклого программирования найденная точка х* будет од новременно и точкой глобального экстремума).
Предположим, что в точке х* функция f(х) имеет ло кальный условный экстремум и ранг матрицы равен т. Тогда необходимые условия запишутся в виде:
(5)
где
(6)
есть функция Лагранжа; λ1,... , λm – множители Лагранжа.
Существуют также и достаточные условия, при выполне нии которых решение системы уравнений (5) определяет точку экстремума функции f(х). Этот вопрос решается на основании исследования знака второго дифференциала функ ции Лагранжа. Однако достаточные условия представляют главным образом теоретический интерес.
Можно указать следующий порядок решения задачи (5) методом множителей Лагранжа:
1) составить функцию Лагранжа (6);
2) найти частные производные функции Лагранжа по всем переменным х1,... , хп, λ1,... , λm и приравнять их нулю. Тем самым будет получена система (5), состоящая из п + т уравнений. Решить полученную систему (если это окажется возможным!) и найти таким образом все стационарные точки функции Лагранжа;
3) из стационарных точек, взятых без координат λ1,... , λm, выбрать точки, в которых функция f(х) имеет услов ные локальные экстремумы при наличии ограничений. Этот выбор осуществляется, например, с применением доста точных условий локального экстремума. Часто исследование упрощается, если использовать конкретные условия задачи.
§3. Градиентные методы
Градиентным методом мож но решать, вообще говоря, любую нелинейную задачу. Одна ко при этом находится лишь локальный экстремум. Поэто му целесообразнее применять этот метод при решении задач выпуклого программирования, в которых любой локальный экстремум является одновременно и глобальным.
Рассмотрим задачу максимизации нелинейной дифференцируемой функции f(х). Суть градиентного поиска точки максимума х* весьма проста: надо взять произвольную точку хо и с помощью градиента , вычисленного в этой точке, определить направление, в котором f(х) возрастает с наибольшей скоростью, а затем, сделав небольшой шаг в найденном направлении, перейти в новую точку x1. По том снова определить наилучшее направление для пе рехода в очередную точку х2 и т. д.
Таким обра зом, надо построить последовательность точек хо, x1,... так, чтобы она сходилась к точке максимума х*.
Градиентные методы, как правило, позволяют получать точное решение за бесконечное число шагов и только в неко торых случаях – за конечное. В связи с этим градиентные методы относят к приближенным методам решения.
Движение из точки xk в новую точку хk+1 осуществляется по прямой, проходящей через точку xk и имеющей уравнение
где λk — числовой параметр, от которого зависит величина шага.
Градиентные методы отличаются друг от друга способом выбора величины шага. Распространенным является вариант градиентного поис ка, называемый методом наискорейшего подъема.
§4. Теорема Куна - Таккера
В теории нелинейного программирования центральное ме сто занимает теорема Куна — Таккера, обобщающая клас сический метод множителей Лагранжа на случай, когда в нелинейной задаче, помимо ограничений-равенств, содержат ся также и неравенства. В частности, для задачи выпуклого программирования: минимизировать z = f(x) при ограниче ниях φi(x ) ≤ 0, (i = l,…, m), x ≥ 0, где все функции вы пуклые, теорема Куна — Таккера устанавливает связь между оптимальным решением задачи и седловой точкой функции Лагранжа для этой задачи:
(7)
Точка (х*, λ* ) называется седловой точкой функции (7), если n-мерная точка х* является точкой минимума функции L(x, λ ), а m-мерная точка λ — точкой максимума функции L(x*, λ* ), так что для всех х и λ выполняется неравенство
(8)
В этом смысл теоремы Куна — Таккера. Сама же теорема формулируется следующим образом.
Теорема (Куна — Таккера). Предположим, что существует вектор х ≥ 0, такой, что φi(x ) ≤ 0, (i = l,…, m). Тогда необходимым и достаточным условием оптимально сти вектора х*, принадлежащего допустимой области, яв ляется существование такого вектора λ* , что для всех х ≥ 0 и λ ≥ 0 имеет место неравенство (8).
ТЕМА 5. дИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
§1. Основные понятия
Динамическое программирование (иначе — динамическое планирование) — это метод нахожде ния оптимальных решений в задачах с многошаговой (мно гоэтапной) структурой. Многие экономические процессы рас членяются на шаги естественным образом. Это все процес сы планирования и управления, развивающиеся во времени. Естественным шагом в них может быть год, квартал, месяц, декада, неделя, день и т. д. Однако метод динамического про граммирования может использоваться при решении задач, где время вообще не фигурирует; разделение на шаги в таких за дачах вводится искусственно. Поэтому "динамика" задач ди намического программирования заключается в методе реше ния.
В экономической практике встречается несколько типов задач, которые по постановке или способу решения относятся к задачам динамического программирования. Это задачи оп тимального перспективного и текущего планирования во вре мени. Их решают либо путем составления комплекса взаимо связанных статических моделей для каждого периода, либо путем составления единой динамической задачи оптимально го программирования с применением многошаговой процеду ры принятия решений. К задачам динамического программи рования следует отнести задачи многошагового нахождения оптимума при размещении производительных сил, а также оптимального быстродействия.
Рассмотрим несколько типичных задач, для решения ко торых естественным является применение метода динамиче ского программирования.
Задача перспективного планирования. Планируется деятельность группы N промышленных предприятий Пi (i = 1,…, N) на период в t (t = 1,…, Т) хозяйственных лет. В начале периода на развитие системы предприятий выделены какие-то средства К, которые должны быть распределены между предприятиями. В процессе деятельности предприятия вло женные в него средства частично амортизируются. Каждое предприятие за год приносит доход, зависящий от вложен ных средств, часть которого отчисляется в фонд предприя тий. В начале каждого хозяйственного года имеющиеся сред ства перераспределяются между предприятиями. Возникает задача определения объема средств в начале каждого года, которые нужно выделить каждому предприятию, чтобы сум марный чистый доход за Т лет был максимальным. Это ти пичная задача динамического программирования. Здесь про цесс принятия решения разбивается на Т шагов. Управле ние им заключается в начальном распределении и последу ющих перераспределениях средств иt = {иit}, где иit — объ ем средств, выделенных i-му предприятию в начале t-гo го да. Для описания динамики системы вводится вектор состо яния хt = {хit}, где хit — состояние i-го предприятия на на чало t-гo года. В свою очередь состояние каждого предпри ятия хit является вектором, компонентами которого служат трудовые ресурсы, основные фонды, финансовое положение и т.д., т.е. хit = { хikt }. Вектор управления — это функция состояния системы на начало соответствующего года: ut = ut(xt-1). Начальное состояние системы х° может быть заданным. Целевой функцией будет суммарная прибыль объединения за Т лет. Если zt — прибыль за t-й год, то полу чим задачу
где Ω — область допустимых управлений, или множество эко номических возможностей, определяемых различными огра ничениями, налагаемыми на состояние системы и вектор управления.
Задача об оптимальном управлении поставками. В различных областях народного хозяйства возникает задача определения момента подачи партии поставки и ее объема. С размещением заказов связаны некоторые фиксированные затраты К, не зависящие от величины заказываемой партии, а зависящие только от факта заказывания. С содержанием материальных ресурсов связаны затраты, пропорциональные остатку нереализованной продукции на конец интервала. Пусть Т — промежуток планирования. Обозначим через νt интенсивность потребления ресурса в t-м интервале. Состо яние системы будем описывать величиной остатка нереали зованной продукции на конец интервала xt. Начальное x0 и конечное xT состояния системы можно считать заданными. Для бесперебойности потребления поставками нужно упра влять. Обозначим через u = {ut} вектор управления, коор динаты которого суть величины поставок в начале соответ ствующих интервалов. Очевидно, что вектор управления есть функция состояния на начало интервала. Из множества воз можных управлений требуется выбрать такое, при котором достигается минимум издержек на заказывание и содержа ние материальных ресурсов. Если St — издержки содержания единицы продукции в t-м интервале, то функция цели примет вид
где
Состояние системы опишется соотношением xt = xt-1+ ut — vt (t =1,…, Т). На состояние системы может быть на ложено ограничение, связанное с надежностью снабжения: , где — величина некоторого страхового запаса, га рантирующего с заданной надежностью от сбоев в системе. Объединение ограничений, налагаемых на состояние системы и вектор управления, обозначим Ω. Получим задачу
§2.Особенности задач динамического программирова ния
1. Рассматривается система, состояние которой на каждом шаге определяется вектором xt. Дальнейшее изменение ее со стояния зависит только от данного состояния xt и не зависит от того, каким путем система пришла в него. Такие процессы называются процессами без последействия.
2. На каждом шаге выбирается одно решение ut, под дей ствием которого система переходит из предыдущего состоя ния xt-1 в новое xt. Это новое состояние является функцией состояния на начало интервала xt-1 и принятого в начале ин тервала решения ut, т.е.
3. Действие на каждом шаге связано с определенным вы игрышем (доходом, прибылью) или потерей (издержками), которые зависят от состояния на начало шага (этапа) и при нятого решения.
4. На векторы состояния и управления могут быть нало жены ограничения, объединение которых составляет область допустимых решений u принадлежит Ω.
5. Требуется найти такое допустимое управление ut для каждого шага t, чтобы получить экстремальное значение функции цели за все Т шагов.
Любую допустимую последовательность действий для каждого шага, переводящую систему из начального состоя ния в конечное, называют стратегией управления. Допусти мая стратегия управления, доставляющая функции цели экс тремальное значение, называется оптимальной.
Управление — это воздей ствие, переводящее систему из начального состояния в конеч ное. Для многих экономических задач не известно начальное либо конечное состояние, а известна область X0 или Хт,, ко торой эти точки принадлежат. Тогда допустимые управления переводят точки из области Хо в ХТ.
Задача динамического программирования геометрически может быть сформулиро вана следующим образом: найти такую фазовую траекторию, начинающуюся в области Хо и оканчивающуюся в области ХТ, для которой функция цели достигает экстремального зна чения. Если в задаче динамического программирования из вестны начальное и конечное состояния, то говорят о задаче с закрепленными концами. Если известны начальные и конеч ные области, то говорят о задаче со свободными концами.
§3. Принципы динамического программирования
Принцип оптимальности и погружения. Любую мно гошаговую задачу можно решать по-разному. Во-первых, можно считать неизвестными величинами ut и находить экс тремум целевой функции одним из существующих методов оптимизации, т. е. искать сразу все элементы решения на всех N шагах. Отметим, что этот путь не всегда приводит к це ли, особенно когда целевая функция задана в виде таблиц или число переменных очень велико.
Второй путь основан на идее проведения оптимизации поэтапно. Поэтапность отнюдь не предполагает изолированности в оптимизации этапов. На оборот, управление на каждом шаге выбирается с учетом всех его последствий. Обычно второй способ оптимизации оказы вается проще, чем первый, особенно при большом числе ша гов. Идея постепенной, пошаговой оптимизации составляет суть метода динамического программирования. Оптимизация одного шага, как правило, проще оптимизации всего процес са в целом. Лучше много раз решать сравнительно простую задачу, чем один раз - сложную.
Таким образом, одним из условий применимости метода динамического программирования является возможность разбиения процесса оптимизации решения на ряд однотип ных шагов (этапов), каждый из которых планируется отдель но, но с учетом состояния системы на начало этапа и послед ствий принятого решения. Однако из этого правила есть ис ключение. Среди всех шагов существует один, который может планироваться без учета последствий. Это последний шаг. Он может быть изучен и спланирован сам по себе наилучшим (в смысле выбранного критерия) образом, поскольку за ним нет больше этапов. Отсюда получаем одну из специфических осо бенностей динамического программирования: всю вычисли тельную процедуру программирования целесообразно разво рачивать от конца к началу. Раньше всех планируется послед ний N-й шаг, за ним (N-1)-й и т. д. Но как найти оптимальное управление иN на N-м шаге, если оно определяется не только целью управления, но и состоянием системы на начало этого шага? Сделать это можно на основе предположений об ожи даемых исходах предшествующего, но еще не исследованного этапа, т.е. о значениях xN-1.
Для каждого возможного исхода xN-1 на (N — 1)-м этапе находим оптимальное управление на N-м этапе. Такой на бор оптимальных управлений, зависящих от возможных ис ходов предыдущего этапа, называется условно-оптимальным решением u*n(xn-i). Завершив анализ конечного этапа, рас сматривают аналогичную задачу для предпоследнего этапа, требуя, чтобы функция цели достигала экстремального зна чения на двух последних этапах вместе. Это дает условно-оптимальное решение на предпоследнем этапе u*n-1(xn-2), т. е. делаются всевозможные предположения о том, чем кон чился предыдущий (N-2)-й шаг, и для каждого из предпо ложений находится такое управление на (N - 1)-м шаге, при котором эффект за последние два шага (из них последний уже оптимизирован) будет максимален. Тем самым мы найдем для каждого исхода (N - 2)-го шага условно-оптимальное управ ление на (N — 1)-м и условно-оптимальное значение функции цели на последних двух шагах. Проделав такой поиск условно-оптимальных управлений для каждого шага от конца к нача лу, найдем последовательность условно-оптимальных управ лений u1*(xo), u2*(x1),... ,u*N(xN-1).
Условно-оптимальные управления дают возможность най ти не условное, а просто оптимальное управление на каждом шаге.
В процессе оптимизации управления ме тодом динамического программирования многошаговый про цесс проходится дважды. Первый раз от конца к началу, в результате чего находятся условно-оптимальные управле ния и условно-оптимальное значение функции цели для каж дого шага, в том числе оптимальное управление для первого шага и оптимальное значение функции цели для всего про цесса. Второй раз - от начала к концу, в результате чего на ходятся уже оптимальные управления на каждом шаге с точ ки зрения всего процесса. Первый этап сложнее и длительнее второго, на втором остается лишь отобрать рекомендации, по лученные на первом. Следует отметить, что понятия "конец" и "начало" можно поменять местами и разворачивать процесс оптимизации в другом направлении. С какого конца начать – диктуется удобством выбора этапов и возможных состояний на их начало.
Из качественного анализа идеи поэтапной оптимиза ции можно сформулировать следующие принципы, лежащие в основе динамического программирования: принцип опти мальности и принцип погружения.
Принцип оптимальности. Оптимальное управление на каждом шаге определяется состоянием системы на начало этого шага и целью управления. Или в развернутой форме: оптимальная стратегия обладает таким свойством, что, како вы бы ни были начальное состояние и начальные решения, последующие решения должны приниматься исходя из опти мальной стратегии с учетом состояния, вытекающего из пер вого решения. Этот принцип имеет довольно простую математическую интерпретацию, выража ющуюся в составлении определенных рекуррентных соотно шений (функциональных уравнений Р. Беллмана).
Принцип погружения. Природа задачи, допускающей использование метода динамического программирования, не меняется при изменении количества шагов N, т. е. форма та кой задачи инвариантна относительно N. В этом смысле вся кий конкретный процесс с заданным числом шагов оказывает ся как бы погруженным в семейство подобных ему процессов и может рассматриваться с позиции более широкого класса задач.
Реализация названных принципов дает гарантию того, что решение, принимаемое на очередном шаге, окажется наилуч шим относительно всего процесса в целом, а не узких интересов данного этапа.
§4. Функциональные уравнения Беллмана
В основе динамического программирования лежит принцип оптимальности, указывающий на процедуру постро ения оптимального управления. Так как оптимальной страте гией может быть только та, которая одновременно оптималь на и для любого количества оставшихся шагов, ее можно стро ить по частям: сначала для последнего этапа, затем для двух последних, для трех и т.д., пока не придем к первому шагу. Отсюда принцип оптимальности связан со вторым принци пом – погружения, согласно которому при решении исходной задачи ее как бы погружают в семейство подобных ей и реша ют для одного последнего этапа, для двух последних и т.д., пока не получат решение исходной задачи.
Дадим математическую формулировку принципа опти мальности для задач с аддитивным критерием оптимальности. Для простоты будем считать, что начальное хо и конечное хТ состояния системы заданы. Обозначим через z1(x0, u1) значение функции цели на первом этапе при начальном состоянии системы хо и при управлении u1, через z2(x1, u2) - соответствующее значение функции це ли только на втором этапе, ..., через zN(xN-1, uN)— на N-м этапе, ..., через zn(xn~i,un) — на N-м этапе. Очевидно, что
(1)
Надо найти оптимальное управление u* = (u1*, ..., u*N), такое, что доставляет экстремум целевой функции (1) при ограничениях u € Ω.
Для решения этой задачи погружаем ее в семейство по добных. Введем обозначения. Пусть ΩN, ΩN-1,N,… ≡ Ω - соответственно области определения для подоб ных задач на последнем этапе, двух последних и т.д.; Ω – область определения исходной задачи. Обозначим через F1(xN-1), F2(xN-2), … , Fk(xN-k), ... , FN(x0) соответ ственно условно-оптимальные значения функции цели на по следнем этапе, двух последних и т.д., на к последних и т.д., на всех N этапах.
Начинаем с последнего этапа. Пусть xN-1 — возможные состояния системы на начало N-гo этапа. Находим:
(2)
Для двух последних этапов получаем
(3)
Аналогично:
(4)
Выражения (2) - (4) называют функциональными уравнениями Беллмана. Отчетливо про сматривается их рекуррентный (возвратный) характер, т. е. для нахождения оптимального управления на N шагах нуж но знать условно-оптимальное управление на предшествую щих N — 1 этапах и т. д. Поэтому функциональные уравнения часто называют рекуррентными (возвратными) соотноше ниями Беллмана.