<<
>>

9.4. Математика элементы векторной оптимизации; элементы сетевого планирования; модели управления запасами; динамическое программирование; оптимальное управление

Описание фиксируемых посредством математического инструментария экономических отношений и процессов иногда осуществляется с использованием элементов векторной алгебры, позволяющих определить совокупность оптимальных параметров, характеризующих экономические отношения и процессы при данном наборе ограничений, накладываемых внешней средой или количественными характеристиками производственных ресурсов субъектов экономики.

Задачи на условный экстремум

В теории безусловного локального экстремума сравнивают частное значение f(x10,x20) функции y=f(x1 ,x2) в точке (x10,x20) с частными значениями f (x1, x2) этой функции во всех точках (x1, x2), близких к точке (x10,x20). Другими словами, в теории локального безусловного экстремума на независимые переменные х1 и х2 не накладываются никакие дополнительные условия, т.е. не требуется, чтобы переменные ^ и х^ удовлетворяли некоторым дополнительным ограничениям.

Рассмотрим теперь другую задачу. Найти локальный максимум (или локальный минимум) функции у •= f(x1, x2) при условии, что независимые переменные х1 и х2 удовлетворяют ограничению g(x1, x2)=0 в виде равенства, т.е.

Задача (9.4.1), (9.4.2) называется задачей на условный локальный максимум (минимум). Термин условный здесь появляется в связи с тем, что независимые переменные x1 и x2 удовлетворяют условию (ограничению) (9.4.2). Вместо двух терминов (максимум и минимум) используется обобщенный термин экстремум. В задаче (9.4.1), (9.4.2) на условный экстремум функцию f(x1, x2) принято называть целевой, ибо ее максимизация (или минимизация) часто есть формальное выражение какой-то цели (например, максимизации объема производства при фиксированных затратах). Функцию g называют функцией, задающей ограничение, или функцией связи.

Уравнение (9.4.2) есть уравнение нулевой линии (точнее множества) уровня функции g(x1, x2), ибо g(x1, x2)=r, где г=0.

Поэтому задачу на условный локальный максимум (минимум) можно еще сформулировать так: среди точек нулевой линии уровня функции У = g(x1, x2) найти точку (х10,х20), в которой частное значение f (x10, x20) функции у -=- f (x1, x2) больше (или меньше) ее частных значений f (x1, x2) в остальных точках (x1, x2) этой линии, близких к точке (x10, x20) (см. рис. 9.4.1). Точка (x10, x20) называется точкой условного локального максимума (минимума) функции f (x1, x2), само частное значение f (x10, x20) — условным локальным максимумом (минимумом) функции f (x1, x2) при наличии ограничения g f (x1, x2) = 0.

Проиллюстрируем задачу на условный максимум в трехмерном пространстве (рис. 9.4.2).

Точка (x1*, x2*) — точка абсолютного локального максимума функции (x1, x2), ибо точка (x1*, x2*; f (x1*, x2*) —локальная (т.е. местная) «макушка» графика Г f этой функции f (x1, x2). Точка f (x10, x20) —точка условного локального максимума функций f (x1, x2), ибо точка (x10, x20 f; (x10, x20) —самая высокая точка «тропинки» L, которая проходит через «перевал» графика Г f На рис. 9.4.2 четко видно, что точка (x10, x20; f (x10, x20)) «макушкой» не является т.е. точка (x10, x20) условного локального максимума может не быть точкой безусловного локального максимума. Линия g(x1, x2)=0 есть проекция «тропинки» L на координатную плоскость Ох1x2.

Отметиим, что если известен график Г f, функции f (x1, x2 двух переменных, x1, и х2, то, глядя на него., можно сразу понять, есть ли точки абсолютного и условного локального экстремума или какие-то из них (а, возможно, все) отсутствуют.

В случае, если графика Гf нет, точки абсолютного локального экстремума отыскиваются с помощью формального анализа функции у == f (x1, x2).

Существует формальный метод отыскания точек условного локального экстремума, для использования которого также не требуется знания графика Гf. .функции y= f (x1, x2) и графика уравнения g (x1, x2) = 0. Этот метод называется методом Лагранжа.

Если значение f (x10, x20) функции f (x1, x2) больше (меньше) значений f (x1, x2) этой функции во всех точках (x1, x2) линии g (x1, x2)=0, то значение f (x10, x20) называется условньм глобальным максимумом (минимумом) функции f (x1, x2) при наличии ограничения g (x1, x2)=0, а точка (x10, x20) — точкой условного глобального максимума (минимума) функции f (x1, x2).

Точка условного глобального максимума (минимума) функции f (x1, x2) является точкой условного локального максимума (минимума) этой функции. Обратное, вообще говоря, неверно,. На рис. 9.4.2 точка (x10, x20) является точкой не только локального, но и глобального условного максимума функции f (x1, x2) при наличии ограничения g (x1, x2)=Q.

В случае функции f (x1…… xn) п независимых переменных х1...хn задача на условный максимум (минимум) формулируется так:

Если частное значение f (x10,.. xn0) сравниваются со значениями f (x1,.. xn) в точках. (х1...xn), удовлетворяющих уравнениям (9.4.4) и близких к точке (х1° ...хn°), то имеем задачу на условный локальный экстремум (максимум или минимум) функции f (x1,.. xn).

Если значение f (x10,.. xn0) сравнивается с значениями во всех точках (x1,.. xn), удовлетворяющих уравнениям (9.4.4), то имеем задачу на условный глобальный экстремум (максимум или минимум) функции f (x1,.. xn).

Теория условного экстремума активно используется в микро- и макроэкономической теории. В задачах этой теории обычно локальный условный экстремум является также и глобальным условным экстремумом.

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

Метод Лагранжа позволяет решать не только задачи вида (9.4.1), (9.4.2), но более общие задачи вида (9.4.3), (9.4.4).l

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

Задачи сетевого планирования

Сетевое планирование применяют для организации и составления календарных планов реализации больших комплексов работ.

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

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

При построении графика каждую операцию изображают в виде ориентированной дуги. Связи между операциями также представляются в виде дуги. Дугу-связь проводят из конца дуги, соответствующей предшествующей операции, в начало следующей операции. Чтобы отличить операции от связей, операции изображают сплошными линиями, а связи — пунктирами. Вершины графа называют событиями. Временем наступления события считают время, когда завершено выполнение всех операций, входящих в соответствующую вершину.

График, представляющий взаимосвязь отдельных работ проекта, называется сетевым графиком. На рис. 9.4.За построен сетевой график для комплекса операций, задаваемых табл. 9.4.1.

Таблица 9.4.1 Операция Предшествующие операции Время А1 — 10 А2 — 15 A3 — 5 A4 А1,а2 18 А5 А2, а3 19 А6 A4, a5 18 Большое количество дуг в сети усложняет решение задачи.

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

Пример. На рис. 9.4.36 изображены сеть G и упрощенная сеть G1. При упрощении выброшены дуги Последовательность выполнения работ при этом не изменилась. Дугу выбросить нельзя, так как после этого дуги — работы а4 и а7 — будут неразличимы.

Сетевой график не может содержать циклов. Если предположить, что имеется некоторый цикл (а1, а2,...,аn-1, аn, а1) то операция а1 может быть выполнена только после завершения операции an , операция an только после завершения операции аn-1,…, операция а2 — только после завершения операции а^. В этом случае проект никогда не может быть выполнен.

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

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

Алгоритм получения правильной нумерации вершин.

1. Нумеруют все начальные вершины.

2. Вычеркивают все дуги, выходящие из начальных вершин. При этом получают новые начальные вершины. Переходят к шагу 1.

Процесс повторяют до тех пор, пока все вершины не будут перенумерованы. Конечная вершина получает при этом наибольший номер.

Временные параметры сетевого графика.

Предположим, что выполнение работы начато в момент времени t = 0. Пусть tij —заданная продолжительность работы (pi, pj). Величины tij. записывают на соответствующих дугах сетевого графика и считают их длинами.

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

Если из вершины рi несколько работ, то ранние сроки начал этих работ совпадают и называются сроком наступления события рi. Ранний срок начала работы (рi, рj) обозначают tijрн, а ранний срок наступления события рi — (pi. pj), Для удобства величины записывают в ранний трети каждой вершины (рис. 9.4.4).

Если работа начата в ранний срок начала, то время ее окончания называется раннимс сроком окончания работы. Ранний срок окончания работы (рi, рj) обозначается tijpo.

Для вычисления ранних сроков наступления событий используют алгоритм Форда. Считают, что нумерация вершин является правильной.

Алгоритм расчета ранних сроков начш и окончаний работ.

1. Полагают Т1р =0.

2. Для i = 2, 3,..., п вычисляют

Критическое время и критический путь.

Ранний срок наступления конечного события называется критическим временем и обозначается Ткр . Весь проект не может быть завершен раньше момента времени Т кр, т.е. критическое время — это минимальный срок окончания всего комплекса работ. На сетевом графике Ткр, — это длина пути наибольшей длины из начальной вершины в конечную.

Всякий путь длины, равной Ткр, из начальной вершины в конечную называется критическим путем.

Алгоритм построения критического пути.

Начинают построение с конечной вершины. В ее левой трети стоит номер той вершины, при движении из которой определялся ранний срок наступления события. Критический путь идет из конечной вершины в вершину с этим номером; затем в вершину, номер которой стоит в левой трети полученной при движении вершины, и так до начальной вершины.

Если в какой-то вершине стоят два номера, то критический путь распадается на два. Таким образом, критических путей может быть несколько.

Для сети, изображенной на рис. 9.4.5, критический путь выделен волнистой линией.

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

Поздние сроки начал и окончаний работ,

Задают время Т выполнения всего комплекса работ. Очевидно, что должно выполняться неравенство Т Ткр , Обычно берут Т = Т'кр .

Поздним сроком окончания работы называется наибольшее допустимое время окончания работы без нарушения срока завершения всего проекта. Поздний срок окончания работы (pi, pj) обозначается tijпн. Можно определить поздний срок начала работы (pi, pj) tijпн по формуле

Поздним сроком Тjп наступления события р. называется наиболее поздний срок окончания всех работ, входящих в соответствующую вершину. Алгоритм вычисления поздних сроков наступления событий.

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

Минимальная из этих разностей и равна Тjп Величину Тjп записывают для удобства вычислений в правой трети вершины рj. (рис. 9.4.4).1

Использование математических моделей управления запасами при отображении экономических отношений и процессов позволяет исследовать процессы хранения, пополнения и расходования запасов различных ресурсов с охватом реальных ситуаций, возникающих в различных областях экономики, организации и планирования производства, где под «запасами» могут пониматься сырье, полуфабрикаты, предметы потребления, любые производственные ресурсы.

Основные понятия

Доходом (выручкой) R фирмы в определенном временном периоде (например, в определенном году) называется произведение р0 у общего объема у выпускаемой фирмой продукции на (рыночную) цену р0 этой продукции.

Издержками С фирмы называют общие выплаты фирмы в определенном временном периоде за все виды затрат С =р1x1+р2x2, где x1 и х2 — объемы затрачиваемых (используемых) фирмой ресурсов (факторов производства), р1 и р2 — рыночные цены на эти ресурсы (факторы производства).

Прибылью PR фирмы в определенном временном периоде называется разность между полученным фирмой доходом R и ее издержками производства:

PR=R-C, (9.4.6)

или

PR(x1, x2)=p0 f(x1, x2)-(p1x1 +р2x2). (9.4.7)

Последнее равенство есть выражение прибыли фирмы в терминах затрачиваемых (используемых) ресурсов. Напомним, что y=f(x1, x2) — производственная функция фирмы, которая выражает общий объем у выпускаемой фирмой продукции через объемы х1 и x2 затрачиваемых (используемых) ресурсов.

В теории фирмы принято считать, что если фирма функционирует в условиях чистой (совершенной) конкуренции, на рыночные цены р0, р1 и р2 она влиять не может. Фирма «соглашается» с ценами р0, р1 и р2. Случаи функционирования фирмы в условиях чистой монополии, монополистической конкуренции и олигополии специально рассматриваются в рамках курса по микроэкономике.

Основная цель деятельности фирмы заключается в максимизации прибыли путем рационального распределения затрачиваемых (используемых) ресурсов. Формально задача максимизации прибыли в определенном временном периоде имеет вид: PR —> max. Такая постановка задачи максимизации зависит от того, какой конкретно временной промежуток (долговременный или краткосрочный) предшествует периоду, в котором фирма максимизирует свою прибыль.

В случае долговременного промежутка фирма может свободно выбирать любой вектор x ==(x1, x2) затрат из пространства затрат (формально из неотрицательного ортанта x1 0, х2 0 плоскости Ох1x2), поэтому задача максимизации прибыли в случае долговременного промежутка имеет следующий вид:

P0 f (x1, x2)-(p1x1+p2x2)=PR(x1, x2) max (9.4.8)

при условии, что

x1 0, х2 0

(постановка задачи в терминах затрачиваемых (используемых.) ресурсов).

В случае краткосрочного промежутка фирма должна учитывать неизбежные лимиты на объемы затрачиваемых (используемых) ею ресурсов, которые формально могут быть записаны в виде нелинейного, вообще говоря, неравенства

g(x1, x2) b (9.4.9)

(ограничений вида g(x1, x2) b может быть несколько). Следовательно, задача максимизации прибыли для краткосрочного промежутка имеет вид задачи математического программирования:

P0 f (x1, x2)-(p1x1+p2x2)=PR(x1, x2) max (9.4.10) .

(постановка задачи в терминах затрачиваемых (используемых) ресурсов).

Линия уровня функции z == p1x1 + р2x2 издержек производства называется изокостой (рис.9.4.6).

В связи с тем, что по экономическому смыслу x1 0, х2 О (ибо x1 и x2 — это объемы затрачиваемых (используемых) ресурсов), строго говоря, изокоста есть отрезок прямой, попадающий в неотрицательный ортант плоскости Ох1x2. Таким образом изокосты—это отрезки А0В0, A1B1, А2В2,... (см. рис. 9.4.6).

Отрезки А0В0, A1B1, А2В2 параллельны. Отрезок A1B1, расположенный «северовосточнее» отрезка А0В0, соответствует большим издержкам производства. Следовательно, если для отрезка А2В2 издержки производства С равны величине С2, т.е. С=С2, для отрезка A1B1, издержки производства C=C1, для отрезка А0В0, издержки производства С==С2, то C0Верно и обратное, т.е. если C0Функции спроса на факторы (ресурсы) в случае долговременного промежутка

В связи с тем, что, как правило, f (x1, 0) = f (0, x2) =0 (т,е. если хотя бы один ресурс не затрачивается (не используется), то объем выпускаемой продукции равен нулю), экономически осмысленными являются векторы (х1, x2) затрат ресурсов, для которых x1 > 0, Х2 > 0.

Поэтому в случае долговременного промежутка задача максимизации прибыли представляет собой обычную задачу на глобальный абсолютный максимум при xi>0, Х2>0. Из математического анализа известно, что точки локального абсолютного максимума следует искать только среди точек (xpJ^)» которые удовлетворяют системе уравнений

то график производственной функции .у == f (х1, х2) в трехмерном пространстве Ох1x2у есть поверхность, выпуклая вверх Следовательно, график прибыли PR(x1, x2), получаемый путем вычитания из графика функции р0 f (х1, х2) плоскости у = р1x1 + р2x2 являющейся графиком издержек ггроизводства, имеет вид «шапочки», у которой есть «макушка». «Макушка» соответствует глобальному максимуму прибыли:

Из этого геометрического следует, что система (9.4.15) единственное решение (х1°, х20), которое точкой не только локального, но и глобального (искомого нами) максимума прибыли PR(х1, х2),. Вектор (х1°, х20), затрат ресурсов, который является решением задачи прибыли pr(х1, х2), = р0 f (х1, х2)-(р1x1+ р2x2), называется локальным (частичным) рыночным равновесием фирмы (в случае долговременного промежутка).

Рисунок графика прибыли PR(x1, x2) в трехмерном пространстве, вообще говоря, достаточно сложен. Поэтому график прибыли представим схематически на плоскости Ozy, где координатная ось Oz изображает плоскость Ох1х2.

На рис. 9.4.7а даны графики производственной функции , f (z), дохода фирмы p0f(z) и издержек производства pz. На рис. 9.4.76 изображен график прибыли PR(z) = Pof(z) - pz, который получен вычитанием из графика дохода фирмы p0 f (z) графика издержек производства pz. Точка (z0, PR(z0)) есть «макушка» «шапочки» — графика функции PR(z) = pof(z) - pz.

т.е. в точке (x10, x20) локального рыночного равновесия фирмы отношение предельной производительности первого ресурса к предельной производительности второго ресурса равно отношению рыночных цен на эти ресурсы.

Проведем через точку (x10, х20) изокванту и изокосту, которые, эту точку содержат. Уравнение изокванты имеет f(x1, x2) = y0, где y0=(x10, х20). Уравнение изокосты имеет вид р1x1+ р2x2 = C0, где C0=p1x10+p2x20. Перепишем уравнение f (х1, х2)=у0, выразив переменную x2 через пременную x1 т.е.в виде х1=-h(x1) (обратим внимание, что уравнения f(x1, .x2)=y0 и x2=h(x1) формально разные, но они аналитически описывают одну и туже изокванту — рис. 9.4.8).

Из математического анализа известно, что для изокосты р1x1 + р2x2 = С0 отношение-p1 /p2 tg . Из (9.4.19), (9.4.20) и (9.4.21) следует, что tg =tg , что означает, что касательная т к изокванте в точке (x10, x20) совпадает с изокостой, т.е. в точке (х10, х20) изокванта обязательно касается изокосты l (см. рис. 9.4.8). Получена важная (подчеркиваем это особо) геометрическая характеристика локального рыночного равновесия (х10, х20) фирмы — касание в этом равновесии изокванты и изокосты.

Отметим, что, приступая к решению задачи максимизации прибыли, мы не имели конкретных изокванты и изокосты, которые касаются друг друга в точке (х10, х20), ибо не имели самой этой точки. Касающиеся друг друга изокванта и изокоста появляются после того, как аналитически найдено локальное рыночное равновесие (х10, х20) путем решения системы уравнений (9.4.15).

Левая («четырехэтажная») дробь в (9.4.19) есть не что иное, как R12(х10, х20) — предельная норма замены первого ресурса вторым в точке (х10, х20).

Равенство (9.4.19) выражает следующий фундаментальный факт теории фирмы: в точке локального рыночного равновесия (х10, х20) предельная норма замены R12(х10, х20) первого ресурса вторым равна отношению p1/p2 рыночных цен на эти ресурсы.

Поскольку х10 и х20 получаются в виде решения системы уравнений (9.4.15), постольку х10 и х20 есть функции цен (po, p1, p2), т.е.

Выражения (9.4.21) называются функциями спроса на ресурсы (затраты). Их значения х10 и х20 выражают оптимальные выборы затрат (использования) ресурсов как функции цены выпускаемой продукции и цен на ресурсы.

Подставив функции (9.4.21) в производственную функцию y=f(x1, x2), получим выражение

которое называется функцией предложения выпуска. Функции спроса на ресурсы и функция предложения выпуска являются однородными нулевой степени по всем своим аргументам р0, р1 и р2-, т.е. d1(tpo, tp1, tp2)=d1(po, p1, p2), d2(tpo, tp1, tp2 )= d2(po, p1, p2), s(tpo, tp1, tp2)=s(po, p1, p2) для любого числа t > 0. Свойство однородности означает, что Р0, P1, р2 в одно и то же число раз t (т.е. при масштаба, но не структуры цен) не меняет х10, х20 и у0, что важно с содержательной точки зрения.

С математической точки зрения однородность нулевой степени функции спроса и функции предложения является простым фактом, ибо максимизация прибыли PR(x1, x2) =tp0 f(x1, x2)-(tp1x1 +tp2x2) сводится к системе уравнений (9.4.18), поскольку намножитель t > 0 можно сократить.

Функции спроса на факторы (ресурсы) в случае краткосрочного промежутка

В случае краткосрочного промежутка рассмотрим конкретный пример, когда второй ресурс фирма может использовать только в объеме, равном х2# > 0. Тогда задача максимизации прибыли превращается в задачу максимизации функции одной переменной:

PR(x1, x2#)= p0 f{x1, x2#)-(p1x1+р2x2#), и вместо системы уравнений (9.4.15) появляется только одно уравнение

Как и в разделе «Функции спроса на факторы (ресурсы) в случае долговременного промежутка», считаем (исходя из содержательных экономических соображений), что уравнение (9.4.23) имеет единственное решение x1# = x1 (x1# зависит от х2#, т.е. x1#=x1(x2#)), следовательно, в случае краткосрочного промежутка локальное рыночное равновесие есть вектор (x1#, x2#). С помощью рис. 9.4.9 дадим ему наглядную геометрическую интерпретацию. Если бы объем x2# второго ресурса не был лимитирован, то, как видно из рис. 9.4.9, локальным рыночным равновесием была бы точка касания (x20, x20) в которой тот же объем выпускаемой продукции (для точек (x1#, x2#) и (x10, x20) изокванта одна и та же) получился бы при меньших издержках производства (изокоста, содержащая точку (x1#, x2#), расположена «северо-восточнее» изокоста, содержащей точку (x10, x20)). В точке (x1#, x2#) локального рыночного равновесия содержащие ее изокванта и изокоста пересекаются, но не касаются. В рассматриваемом случае на самом деле x1# =x1#( x2#,р0, р1, р2), это и есть функция спроса на первый ресурс при фиксированном объеме второго ресурса. Функция предложения (выпуска) имеет вид у = f (x1#( x2#,р0, р1, р2) x2#).. Может случиться так, что точки (x1#, x2#) и (x10, x20) сольются в одну, и тогда получится та ситуация, которая уже была проанализирована в разделе «Функции спроса на факторы (ресурсы) в случае долговременного промежутка».1

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

Основные понятия и постановка задачи динамического программирования. Понятия динамического программирования

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

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

Например, выпуск продукции любым предприятием — управляемый процесс, так как он определяется изменением состава оборудования, объемом поставок сырья, величиной финансирования и т.д. Совокупность решений, принимаемых в начале каждого года планируемого периода по обеспечению предприятия сырьем, замене оборудования, размерам финансирования и т.д., является управлением. Казалось бы, для получения максимального объема выпускаемой продукции проще всего вложить максимально возможное количество средств и использовать на полную мощность оборудование. Но это привело бы к быстрому изнашиванию оборудования и, как следствие, к уменьшению выпуска продукции.

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

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

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

Пример, Пусть планируется деятельность некоторой системы S промышленных предприятий Р1, Р2,…..,Рn на некоторый период времени T, состоящий из k хозяйственных лет ti (t=1,2,...k), причем Т = ti. В начале периода T на развитие предприятий выделены основные средства D. В начале каждого хозяйственного года производится финансирование всей системы предприятий, т.е. выделяется доля основных среден Известны первоначальное состояние системы s0, характеризуемое количеством средств уже вложенных в предприятия, и конечное состояние Sk, характеризуемое все дополнительно вложенной суммой D. Как следует распределить по предприятиям и года! основные средства D, чтобы к концу периода Т суммарный доход W от всей системы предприятий был максимальным?

Решение. Обозначим через Хij суммуу выделяемую в начале i - го года j – м предприятию (i =1, 2,..., k; j==1,2,..., n). Предположим, что средства на i-м этап распределены, т.е. выбрано определенное управление Ui которое состоит в том, что начале i - го года предприятию Pi выделены средства хi1, предприятию Р2 — средства хi2, и т.д. Тогда вектор Ui=(хi1, хi2,.., хin) определяет распределение средств на i-м этапе.

Совокупность выделенных средств (управлений) на k шагах выразится системой векторо n-мерного векторного пространства

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

Примечание. В общем случае начальное s0 и конечное Sk состояния системы точно не задаются, а указывается целая область начальных и конечных состояний.

Сформулированную задачу, на первый взгляд, можно решить непосредственно, объединив все этапы. Действительно, W можно рассматривать как функцию от элементов управлений на каждом этапе:

т.е. как функцию многих переменных. Теперь решение задачи заключается в нахождении такой совокупности значений аргументов xij, при которой функция W достигает максимального значения. Казалось бы, найдя частные производные функции W по всем аргументам, приравняв их к нулю и решив систему уравнений = 0, получим значения хij, при которых функция W имеет локальный максимум.

Однако этот метод имеет существенные недостатки: во-первых, при большом количестве этапов решение полученной системы довольно громоздко; во-вторых, с его помощью можно найти критические точки только внутри области, так как метод не позволяет исследовать граничные точки; в-третьих, метод вообще неприменим, если хij дискретные величины.

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

Однако динамическое программирование имеет и свои недостатки. В отличие от линейного программирования, в котором симплексный метод является универсальным, в динамическом программировании такого метода не существует. Каждая задача имеет свои трудности, и в каждом случае необходимо найти наиболее подходящую методику решения. Недостаток динамического программирования заключается также в трудоемкости решения многомерных задач. При очень большом числе переменных решение задачи даже на современных ЭВМ ограничивается памятью и быстродействием машины. Например, если для исследования каждой переменной одномерной задачи требуется 10 шагов, то в двумерной задаче их количество увеличивается до 100, в трехмерной — до 1000 и т.д.

Общая постановка задачи динамического программирования

Пусть некоторая физическая управляемая система S находится в первоначальном состоянии s0 0. С течением времени ее состояние меняется и система приходит в конечное состояние sk k. С процессом изменения состояния системы связан некоторый численный критерий W. Необходимо так организовать процесс, чтобы критерий достиг оптимального значения.

Обозначим множество возможных управлений через U. Тогда задача состоит в том, чтобы из множества возможных управлений U найти такое управление U*, которое позволит перевести систему S из начального состояния s0 0 в конечное sk k так, что критерий W(U) принимает оптимальное значение W*.

Геометрическая интерпретация задачи динамического программирования. Состояние экономической системы S можно описать числовыми параметрами, например расходом ресурсов, количеством вложенных средств и т.д. Назовем эти параметры координатами системы; тогда состояние системы можно изобразить точкой S, а переход из одного состояния S1 в другое S2 — траекторией точки S. Управление U означает выбор определенной траектории перемещения точки S из S1 в S2, т.е. установление определенного закона движения точки S.

Совокупность состояний, в которые может переходить система, называется областью возможных состояний. В зависимости от числа параметров, характеризующих состояние системы, область возможных состояний системы может быть различной. Пусть, например, состояние системы S характеризуется одним параметром, — координатой х. В этом случае изменение координаты, если на нее наложены некоторые ограничения, изобразится перемещением точки S по оси Ох или по ее участку. Следовательно, областью возможных состояний системы является совокупность значений х, а управлением — закон движения точки S из начального состояния s0 0 в конечное sk k по оси Ох или ее части (рис. 9.4.10).

Если состояние системы S характеризуется двумя параметрами (x1 и х2), то областью возможных состояний системы служит плоскость х1 0х2 или ее часть, а управление изобразится линией на плоскости, по которой точка S перемещается из s0 0 в sk k (рис. 9.4.11).

В общем случае, когда состояние системы описывается п параметрами хi (i =1,2,..., п), областью возможных состояний служит п -мерное пространство, а управление изображается перемещением точки S из какой-то начальной области s0 в конечную Sk по некоторой «траектории» этого пространства.

Таким образом, задаче динамического программирования можно дать следующую геометрическую интерпретацию. Из всех траекторий, принадлежащих области возможных состояний системы и соединяющих области s0 и Sk, необходимо выбрать такую, на которой критерий W принимает оптимальное значение.1

Объекты, с которыми имеет дело экономика, обычно снабжены своеобразными «рулями», с помощью которых осуществляется управление экономическими отношениями и процессами. Математически поведение такого объекта описывается уравнениями, куда входят и управляющие параметры, характеризуюгцие положение «рулей». При этом перед экономистом возникает задача отыскания наилучшего управления экономическими отношениями и процессами. Именно этой проблемой и занимается оптимальное. управление.

Задачи оптимального управления

Оптимизационная задача (v, f, ) называется задачей оптимального управления,если: V — множество пар вектор-функций (t), (t), где функция (t) = [ 1(t), 2(t),…. n(t), ] дифференцируема, а функция (t) == { 1(t), 2(t),..., n(t), } кусочно-непрерывна на отрезке [t0;Т] (t0, T фиксированы);

Целевая функция f имеет вид

допустимое множество с; V удовлетворяет следующим условиям:

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

Рассмотрим некоторую экономическую систему. Предположим, что в каждый момент времени t, t0 t Т, на эту систему можно оказывать управляющие воздействия

которые выбираются из некоторого допустимого множества U.

Вектор-функция (t) == { 1(t), 2(t),..., n(t), }, где t, t0 t Т, называется управлением системой.

Если скорость изменения состояния системы в каждый момент времени t зависит от самого состояния (t) = [ 1(t), 2(t),…. n(t), ], от управления (t) и от момента времени t, то

При заданном управлении (t) решение этой системы дифференциальных уравнений является некоторой траекторией развития экономической системы. Траектория развития системы должна удовлетворять некоторым начальным и конечным условия.

Если (t) — управление, a (t) -— определяемая им траектория развития, то пара[ (t), (t) } называется: управляемым процессом. Будем считать, что затраты f( , ) на. управляемый процесс ( , ) можно вычислить по формуле

Таким образом, оптимального управления (9.4.27) -- (9.4.31) — это задача выбора оптимального управляемого процесса, т.е. управляемого процесса, удовлетворяющего всем условиям, при котором затраты будут наименьшими.

Функция

<< | >>
Источник: В.И.Видяпина. Бакалавр Экономики Том 1. 1999

Еще по теме 9.4. Математика элементы векторной оптимизации; элементы сетевого планирования; модели управления запасами; динамическое программирование; оптимальное управление:

  1. • Принцип оптимальности в планировании и управлении, общая задача оптимального программирования • Формы записи задачи линейного программирования и ее экономическая интерпретация • Математический аппарат • Геометрическая интерпретация задачи • Симплексный метод решения задачи 2.1. Принцип оптимальности в планировании и управлении, общая задача оптимального программирования
  2. 3.6. Модели сетевого планирования и управления
  3. 10.4. Математика элементы теории игр; системы массового обслуживания; элементы теории графов; элементы имитационного моделирования дискретного характера
  4. 8.2. Модели управления запасами Классическая задача управления запасами
  5. 6.4. Математика геометрия Евклида как первая естественно-научная теория; аксиоматический метод; математические доказательства; линейная алгебра с элементами аналитической геометрии; линейное программирование
  6. Стратегическое планирование — составной элемент стратегического управления
  7. Информационное обеспечение управления запасами. Определение оптимального размера заказа
  8. Система управления и ее элементы
  9. Понятие и основные элементы публичного управления
  10. Какие функциональные элементы используются в управлении финансами?
  11. Основные модели управления запасами
  12. элементы теории игр; системы массового обслуживания; элементы теории графов; элементы имитационного моделирования дискретного характера
  13. 3.5 Элементы финансовой математики
- Информатика для экономистов - Антимонопольное право - Бухгалтерский учет и контроль - Бюджетна система України - Бюджетная система России - ВЭД РФ - Господарче право України - Государственное регулирование экономики в России - Державне регулювання економіки в Україні - ЗЕД України - Инновации - Институциональная экономика - История экономических учений - Коммерческая деятельность предприятия - Контроль и ревизия в России - Контроль і ревізія в Україні - Кризисная экономика - Лизинг - Логистика - Математические методы в экономике - Микроэкономика - Мировая экономика - Муніципальне та державне управління в Україні - Налоговое право - Организация производства - Основы экономики - Политическая экономия - Региональная и национальная экономика - Страховое дело - Теория управления экономическими системами - Управление инновациями - Философия экономики - Ценообразование - Экономика и управление народным хозяйством - Экономика отрасли - Экономика предприятия - Экономика природопользования - Экономика труда - Экономическая безопасность - Экономическая география - Экономическая демография - Экономическая статистика - Экономическая теория и история - Экономический анализ -