Задачи линейного программирования. Задача об оптимальном составе смеси. Транспортная задача

, Кафедра информационных систем и технологий Е. П. Богданов КУРС ЛЕКЦИЙ по дисциплине ПРИКЛАДНЫЕ МЕТОДЫ ОПТИМИЗАЦИИ для специальности 080800.62 «Прикладная информатика в экономике» бакалавриат Волгоград 2009 Лекция №1 ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Задачей линейного программирования (ЛП) называется задача оп­тимизации линейной функции при наличии линейных ограничений: при условии где х - вектор неизвестных управляемых переменных; с - постоянный вектор, часто трактуемый как цены; b- постоянный вектор, обычно трактуемый как ресурсы; - прямоугольная матрица размера тхп. В этой задаче число неизвестных п должно быть больше числа условий т, иначе будет нарушено условие единственности реше­ния, выполняющееся в оптимизационной задаче. 1.1. Основные свойства задачи ЛП Справедливы следующие две теоремы. Теорема 1. Оптимальное решение в задаче ЛП находится в крайней точке множества допустимых решений. Вообще говоря, оптимальное решение может быть на ребре или грани множества допустимых решений. Однако в этом случае значения функции одинаковы соответственно во всех точках ребра или грани, поэтому имеет место неединственность оптимального решения со значением функции в крайней точке. Теорема 2. Крайняя точка множества допустимых решений определяется таким решением системы (1.2), в котором только т переменных (образующих так называемый базис) могут быть отличны от нуля. Вырожденный случай, в котором некоторые компоненты базиса нулевые, будет рассмотрен в разд. 1.5. Важное значение имеет двойственная задача ЛП, которая будет рассмотрена в разд. 1.4. Одна из процедур, определяющих такой базис, при котором зна­чение критерия эффективности минимально, называется симплекс-методом. Рассмотрим эту процедуру на основе примера о составе смеси. 1.2. Задача об оптимальном составе смеси Цель решения - подобрать оптимальный состав коктейля из трех компонентов: коньяка, шампанского и сока. Обозначим стоимости ингредиентов смеси соответственно содержание в них алкоголя а вкусовые качества в баллах Обозначим также через хi i =1,2,3, долю каждого компонента в коктейле (все расчеты ведем на единицу объема). Теперь стоимость коктейля определится функцией Аналогично крепость и вкус коктейля в предположении линей­ности дадут функции F2и F3. Естественно желание получить коктейль минимальной стои­мости, максимальной крепости и максимального вкуса. Однако легко видеть, что это противоречивые критерии. Действительно, коктейль максимальной крепости должен состоять только из конья­ка, но тогда он будет самый дорогой. Это обычная ситуация при проектировании сложных систем - необходимость учитывать противоречивые критерии, связанные, например, с противоборством между стоимостью и качеством. При решении подобных задач ча­сто используют метод удовлетворительных требований. Для этого выбирают главный критерий, который и оптимизируют, а осталь­ные критерии ограничивают на требуемом уровне. Пусть такой критерий - стоимость, крепость ограничим долей алкоголя в 0,2, а вкус - 8 баллами. Теперь будем иметь следующую задачу ЛП: при условиях Предпоследнее условие отражает наличие в составе смеси толь­ко Трех компонентов. Выразив из него переменную xi и исключая эту переменную из функции и остальных условий, получим плоскую задачу: Теперь задачу ЛП можно изобразить на плоскости. Каждое из ограничений в этой задаче делит плоскость на две полуплоскости: допустимую и недопустимую (рис. 1.1). Минимум функции будет в такой точке границы области допустимых стратегий, где уровень функции минимален, так как градиент линейной функции постоянен. Эта точка определяется пересечением пересечением двух прямых: 4х2 + 6хз = 4 и -0,1x2 + 0,4хз = 0,2, отсюда получаем оптимальный состав смеси х2 = 2/11, х3 = 6/11, x1 = 3/11. Стоимость смеси минимальна и равна 470/11, крепость составляет 0,2 и вкус - 8 баллов. Рис. 1.1. Область допустимых решений: —> - градиент функции Рассмотрим теперь формализованное решение задачи симплекс-методом. Ограничения в этой задаче с учетом введения дополни­тельных переменных имеют следующий вид В этой системе линейных уравнений только три базисные пере­менные должны быть отличны от нуля. Выбор конкретного базиса приводит к квадратной матрице А в (1.2). Если ее определитель не равен нулю, то система имеет единственное решение, которое может удовлетворять системе ограничений, а может и не удовлетво­рять (например, некоторые компоненты вектора Ах могут оказаться отрицательными). Если решение допустимо, его дальнейшее улуч­шение осуществляется симплекс-методом. Примем следующий базис: х1 х3, х5, т.е. положим х2=х4 = 0. Система уравнений примет вид Лекция № 2 1.3 Задача об оптимальной производственной программе Аналогично поступают с обратными неравенствами - в этом случае вычитают дополнительную переменную, преобразуя нера­венство в равенство. Теперь любой вектор х, удовлетворяющий уравнению (1.12), представляет собой допустимую стратегию, а поскольку такая стра­тегия не единственная (число неизвестных больше числа уравне­ний), то актуальной задачей является отыскание наилучшей страте­гии, обеспечивающей максимальную прибыль от реализации всего объема выпускаемой продукции. Для этого нужно максимизировать критерий эффективности Где сi – прибыль от единицы продукции вида i. 1.4 Двойственная задача ЛП Обратимся к вопросу использования ресурсов в предыдущей задаче. Как можно видеть из примера ее решения, часть ресурсов использована полностью, т.е. часть ограничений (1.11) выполняется как равенства, дополнительные переменные для этих ограничений paвны нулю, они являются небазисными. Часть ресурсов (в примере это последнее ограничение в (1.11)) использована не полностью. Тогда ценность этого ресурса для предприятия оказывается более низкой по сравнению с ресурсами, ограничивающими выпуск про­дукции, и предприятие готово заплатить более высокую цену за приобретение ресурсов, позволяющих увеличить прибыль. Если считать, что каждый вид ресурса bj,j =1,m, обладает неко­торой «теневой» ценой uj, определяющей ценность данного ресурса для предприятия в отношении прибыли от реализации выпускаемой продукции, можно прийти к формулировке двойственной задачи ЛП, тесно связанной с прямой задачей ЛП (1.11)—(1.13). Величины uj должны быть такими, чтобы затраты на производство по теневым ценам были не меньше получаемого дохода, т.е. Введение дополнительных переменных, представляющих пре­вышение «теневой» цены единицы продукции над доходами от ее реализации, позволяет представить ограничения двойственной за­дачи в виде системы равенств: Оптимальные теневые цены должны минимизировать стоимость ресурсов, т.е. Сравнивая с соответствующими соотношениями в предыдущем подразделе, можно видеть, что прямая и двойственная задачи тесно ни чаны. Эта связь заключается в следующем: • если прямая задача является задачей максимизации, то двойственная - задачей минимизации, и наоборот; • коэффициенты функции в прямой задаче являются ограничениями в двойственной задаче; • ограничения в прямой задаче становятся коэффициентами функции; • знаки неравенств в ограничениях меняются на противоположные; • матрица системы равенств (1.12) транспонируется. можно сформулировать в следующем виде: найти при условии Решение двойственной задачи по отношению к ранее рассмот­ренной прямой задаче оптимизации производственной программы будет рассмотрено в лабораторной работе. . Следует обратить внимание на то обстоятельство, что значения критериев в прямой и двойственной задачах совпадают. Это основное свойство двой­ственных задач. Лекция № 3 1.5 Транспортная задача Есть п пунктов отправления, в которых имеются запасы произведенной продукции в количествах аi, i=1, т, есть m пунктов назначения с заявками на произведённую продукцию в количествах b, j=. Если то имеем задачу с правильным базисом. При невыполнении этого условия вводим дополнительный фиктивный пункт отправления или назначения, емкость которого равна поло­жительной разности между этими суммами. Стоимость доставки единицы грузов из i-го пункта отправления в j-й пункт назначения составляет величину сij, причем затраты, связанные с фиктивными пунктами, должны быть нулевыми. Тогда минимальные затраты на выполнение плана перевозок определятся минимизацией суммарных затрат на перевозки При условиях: В (1.20) п первых условий предусматривают, что все грузы из всех пунктов отправления должны быть вывезены, а последние т условий - что все заявки во всех пунктах назначения должны быть выполнены. Матрица ограничений в транспортной задаче состоит только из нулей и единиц. Это обстоятельство позволяет модифицировать Симплекс-метод к более экономному алгоритму решения, получив­шему название метод потенциалов. Суть этого метода рассмотрим на простых примерах. Представим исходные данные в виде табл. 1.1. В первом столбце этой таблицы отражены запасы в пунктах отправления, в первой строке - потребности пунктов назначения, остальные клетки таблицы содержат путь из пункта i в пункт j, стоимость транспортировки задана в правом верхнем углу каждой клетки. Первый этап решения состоит в генерации допустимого ре­шения. Число неизвестных тп =3 • 3 = 9, число условий в огра­ничениях т + п— 1=3 + 3 — 1=5. В соответствии с теоремой 2 число небазисных переменных, т.е. переменных, заведомо равных нулю, составляет 4. Допустимое решение наиболее часто генерируют, максимально загружая в первую очередь наиболее дешевые пути. Стоимость c11 — 2 минимальна. Перевезем по этому пути самое большое количество груза единиц. Заявку первого пункта мы удовлетворили не полностью, осталось еще 2 единицы. Следующее минимальное значение в мат­рице с13 = 3, но из первого пункта мы уже все вывезли, поэтому перевезем из пункта а3 в пункт b12 17 единиц со стоимостью с32 =3, тем самым удовлетворяя заявку второго пункта. Таблица 1.1 Исходные данные к транспортной задаче Последовательно определяя все базисные переменные, получим допустимое решение, претендующее на оптимальность (табл. 1.2). В этом решении все грузы вывезены и все заявки выполнены, однако решение получено попыткой минимизировать каждое слагаемое в критерии, что не может гарантировать минимальную величину всей суммы. Для проверки оптимальности используется метод потенциалов, позволяющий определит возможность улучшения решения. Для этого определяются числа (потенциалы) аi, иiиз условия аi + i= сij для хij > 0. Таких чисел т + п = 6, а базисных переменных на единицу меньше, поэтому значение одного из потенциалов выбирают произвольно. Пусть i = 0, тогда i + i= =c11, отсюда i = 2. Последовательно используя условие, в котором один из потенциалов уже определен, получим табл. 1.3. Таблица 1.2 Допустимое решение Таблица 1.3 Потенциалы и псевдостоимости Далее вычисляются псевдостоимости = i + i для xij = 0. Псевдостоимости отражены в левом углу каждой пустой клетки. Если выполняется условие сij, решение оптимально. Так как это условие выполнено, план перевозок, отраженный в табл. 1.4 оптимален. Таблица 1.4 Проверка оптимальности для задачи с правильным балансом В этом алгоритме предполагается, что все базисные переменные отличны от нуля. Однако в процессе расчетов может оказаться, что некоторые переменные в базисе нулевые. В этом случае имеем дело с вырожденным решением. Если , то это задача с неправильным балансом. Свести ее к задаче с правильным балансом можно введением фиктивного пункта отправления или фиктивного пункта назначения Эrи величины характеризуют количество невывезенного груза или неудовлетворенной заявки. В матрице затрат добавляется нулевая строка или столбец в соответ­ствии с добавленным пунктом. Рассмотрим следующий пример, заданный в таблице с исходными данными матрицей затрат Допустимое решение при введении фиктивного пункта b4 = 1 и нулевых затратах в 4-м столбце дано в табл. 1.5. Таблица 1.5 Проверка вырожденного решения на оптимальность Число базисных переменных в этом случае т + п = 6, а число ненулевых клеток равно 5 вследствие того, что при генерации допу­стимого решения одновременно удовлетворился спрос и предложе­ние, тогда как в предыдущем случае на каждом шаге удовлетворялся либо спрос, либо предложение. Решение вырождено на этом этапе, необходимо в базис ввести одну из пустых клеток. Теперь мож­но определить потенциалы и проверить решение на оптимальность (табл. 1.5). Обозначим через Е бесконечно малую положительную величину и положим х13 = Е. Проверка оптимальности методом потенциалов показывает, что решение не оптимально, так как в четырех пустых клетках псевдостоимости превышают стоимости. Для того чтобы ввести какую-либо из этих переменных в базис, необходимо выполнить циклическую перестановку перевозок. Она осуществляется таким образом, чтобы сохранялись балансные со­отношения (1.20) и какая-либо базисная (ненулевая) переменная вышла из базиса. Пример введения в базис переменной х32 дан в табл. 1.6. Таблица 1.6 Циклическая перестановка Для ввода этой переменной в базис необходимо добавить в пу­стую клетку, помеченную точкой, некоторый пока не определенный объем перевозок х32 = А > 0. Для сохранения баланса в третьей строке величину х33 нужно уменьшить на указанную величину. Это приводит к необходимости откорректировать баланс по третьему столбцу. Продолжая до замыкания цикла, выделенного в таблице стрелками, определяем максимально возможную величину А =9, позволяющую вывести из базиса переменную х11. Опуская проме­жуточные шаги, приведем решение на последнем шаге (табл. 1.7). Таблица 1.7 Оптимальное решение Проверка решения методом потенциалов показывает, что все псевдостоимости не превышают стоимости, решение не может быть улучшено. Значение критерия эффективности в первоначальном допустимом решении F(x) = 290, в оптимальном F(x°) = 277 Резюме Многие экономические задачи формулируются в терминах линей­ного программирования, поскольку функции прибыли, стоимости, затрат суть линейные функции переменных, связанных с объемами выпуска, продаж и других подобных факторов. Градиент функ­ции (вектор цен) не может быть нулевым, что вынуждает искать решение на границе области допустимых решений. Используе­мый с этой целью симплекс-метод позволяет перебирать крайние точки множества допустимых решений с монотонно улучшаемым значением критерия оптимальности. Программная реализация симплекс-метода имеется в большинстве пакетов прикладных программ. Лекция № 4 Решение нелинейных оптимизационных задач Решение нелинейных задач оптимизации в Mathcad мало чем отличается от решения линейных. Точно гак же надо определить функцию цели, в решаются блоке указать ограничения и обратиться к функциям Minimize или Maximize. С помощью функции Minimize пользователь Mathcad получает еще один способ решения систем нелинейных уравнений. Пусть задана система из п алгебраических уравнений с п неизвестными: ЗАДАЧИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ Задача динамического программирования (ДП) формулируется следующим образом: найти минимум (максимум) функции Резюме Динамическое программирование является эффективным способом решения задач оптимального управления. В непрерывном случае оно используется сравнительно редко ввиду сложности решения уравнения Беллмана в частных производных, осложненных опе­рацией максимизации. Применительно к дискретным многошаго­вым процессам уравнение Беллмана позволяет вместо оптимизации функции по всем переменным оптимизировать по шагам функцию одной переменной. Это требует меньшего количества операций по сравнению с прямой оптимизацией функции, но расходует больше памяти ЭВМ для хранения промежуточных результатов - функций Беллмана. Лекция № 5 КОМБИНАТОРНЫЕ ЗАДАЧИ. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ Сложность вычислений минимума функции от п переменных f(x1,x2,..,xn) оценивают как сn3. Такая оценка связана с тем, что для решения эквивалентной задачи - решения уравнения f(x1,x2,..-,xn) = 0 требуется именно это количество операций. Од­нако если вектор x может принимать только целочисленные значе­ния, то для функции отсутствует понятие градиента и основанные на нем методы оптимизации не работают. Можно попытаться погрузить дискретную задачу в непрерывную с некоторым прибли­жением и полученное решение округлить до ближайшего целого. Однако функция при этом подходе может не принимать оптималь­ного значения, а вектор х - не удовлетворять ограничениям. В общем случае приходится прибегать к перебору вариантов, слож­ность решения подобных задач растет экспоненциально с ростом размерности вектора х, и такие задачи называют неполиномиально сложными задачами. Примером является задача коммивояжера. 3.1.Постановка задачи коммивояжера Имеется п городов а1, ..., аn . Задана матрица затрат с = {сij}, i,j =[1, п]. Коммивояжеру нужно выехать из города a1,объехать все пункты и вернуться в начальный город так, чтобы где xij в неизвестные величины, формирующие маршрут Геометрическая интерпретация задачи коммивояжера дана на рис. 3.1. Рис. 3.1. Графическое представление задачи коммивояжера Здесь по оси у - номера городов, по оси х - номера шагов коммивояжера. Так же как в задаче ДП об инвестициях, в зада­че коммивояжера необходимо найти ломаную оптимальной длины, соединяющую точку на начальной прямой с заданной точкой на конечной прямой. Однако применить метод последовательного ана­лиза вариантов здесь невозможно. Пусть коммивояжер находится в 4-м городе. Его дальнейшее поведение зависит от способа, которым он попал в данный город. Если из города 1 в город 3 он двигался по сплошной линии, ему запрещено в дальнейшем заходить в 3-й город, если по пунктирной линии, то во 2-й город. Таким образом, путь коммивояжера зависит не только от текущего состояния, как в задаче динамического программирования, но и от предыстории то­го, каким образом он попал в это состояние. Подсчитаем количество вариантов при прямом переборе. Если рассматривать конкретную задачу, проще будет подсчитать, сколько требуется операций: на 1 -м шаге существует п — 1 вариантов перехода в остальные города, на первых двух шагах количество вариантов равно (п — 1)(n — 2), а на п шагах получаем (n — 1)! вариантов. Для таких задач используется метод ветвей и границ (попытка упорядочить перебор). 3.2. Метод ветвей и границ Пусть M0 - множество всех вариантов решения задачи перебо­ра. Разобьем это множество на подмножества Мi- так, чтобы эти подмножества охватывали все варианты, и чтобы каждый вари­ант входил только в одно подмножество, т.е. чтобы выполнялись условия . Если продолжить такое разбиение для каждого из подмножеств, то в итоге построим дерево, корень которого содержит все варианты, а конечные ветви содержат единственный вариант. Если можно оценить снизу или сверху решения, содержащиеся в каждом подмножестве (определить функцию оценки т(М) или (М) соответственно), то для сокращения перебора можно применить метод ветвей и границ. Метод содержит три этапа: ветвление, оценку и отбрасывание вариантов. Если удалось ввести функцию оценки, то после ветвления множества Мо оцениваем решения во множествах Мi, и дальнейшее ветвление производится для наиболее перспективного множества с максимальной или минимальной оценкой в надежде, что именно там содержится . оптимальное решение. Так продолжаем до тех пор, пока в множестве не окажется единственное решение (рис. 3.2). Процедура отбрасывания вариантов в задаче минимизации основана на следующих принципах. 1. По уже достигнутому значению функции f0, полученному на некотором этапе расчетов. Пусть имеем вариант решения со значением функции f =f°. Тогда все множества, для которых оценка т(М) >=f° не могут содержать лучших значений функции и должны быть отброшены. 2. По предельному значению функции. В этом случае если достигнута граница значений функции, например, нулевая ошибка, то лучшего решения не может быть. Часто отбрасывают остальные решения, если полученное решение удовлетворяет ЛПР. 3. По сравнению оценок. Пусть для двух множеств М1 и М2 получены оценки т(М1) и т(М2). Если выполняется неравенство т(М2)< =т(М1), то во множестве М1 нет лучших решений, чем во множестве М2. Рассмотрим применение метода ветвей и границ для задачи коммивояжера на конкретном примере. 3.3. Решение задачи коммивояжера Коммивояжеру нужно посетить 5 городов, затраты на переход из города i в город j заданы матрицей, изображенной на рис. 3.3 (знак # означает запрещение перехода). Рис. 3.3. Матрица затрат в задаче коммивояжера Алгоритм метода ветвей и границ применительно к задаче коммивояжера 1. Оценка вариантов. Пусть G(0)- множество всех вариантов задачи. Вычислим оценку этого множества. Рассмотрим конкрет­ный цикл с номерами городов i1, i2,. . ., in . Затраты в таком цикле будут следующими: 2. Определим числа hi = . Эти числа представляют собой минимальные затраты на переход из города i во все другие города (рис. 3.4). Рис. 3.4. Минимальные затраты на выход из каждого города В группу 1 включаем такой переход, который характеризуется минимальными (нулевыми) затратами. Поскольку таких переходов несколько (в данном случае 8), то среди нулевых элементов приведенной матрицы затрат выбираем такой путь, чтобы в группу 2 попали варианты с наибольшими затратами. Тогда для этих двух множеств будут получены оценки, максимально отличающие­ся друг от друга. затраты на выход из города r (переход из r в т запрещен), второе слагаемое - минимальные затраты на вход в город т при этом же условии. Сумма этих чисел дает минимальные затраты для множества маршрутов, не содержащих переход из r в т. Приведем результаты вычислений этих затрат (рис. 3.8). Для каждого нулевого члена в строке находим минимальное значение в этой строке (получаем Аналогично для каждого нулевого элемента в столбце находим минимум (получаем . При этом сами нулевые элементы, для которых проводим рассмотрение не учитываем. Поэтому ноль может получиться только в том случае, когда в строке или столбце имеются два нуля. Максимизация затрат по парам городов с нулевыми затратами дает в результате переход из 5-го города в 1-й город (максимальные затраты равны 4), как показано на рис. 3.9. Для заполнения рисунка 3.9 для каждого нулевого элемента на рис 3.8 находим максимальное  или  Приведем дерево вариантов после первого шага алгоритма с оценками снизу множества решений (рис. 3.10). Рис. 3. 10 Дерево вариантов после первого шага. На втором шаге рассматриваем варианты множества G1(i) , имеющие наименьшую оценку. На следующем шаге вычеркиваем из матрицы затрат 5-ю строку и 1-й столбец, делая невозможным обратный переход (1,5), т.е. с15 = бесконечности (рис. 3.11). Повторяем определение оценки для новой матрицы (рис. 3.12-3.14). Вычеркиваем 1-ю строку и 2-й столбец, запрещаем переход 2 —5, в результате получаем матрицу затрат после второго шага (рис. 3.15). На рис. 3.16 показано полученное дерево вариантов. Рис. 3.14. Минимальные затраты для маршрутов, не содержащих переход из r в m. Рис. 3.15. Матрица затрат после второго шага Рис. 3.16. Дерево вариантов после второго шага Снова определяем оценку для матрицы затрат (рис. 3.17 и 3.18). Рис. 3.18 (а) Рис. 3.18(б) Вычеркиваем 2-ю строку, 4-й столбец, запрещаем переход 4  5 и получаем матрицу затрат на последнем шаге (рис. 3.19). ..Остается единственный вариант 4  3  5. Полный замкнутый путь: 51 24 3  5 с затратами 3+3 + 4 + 5 + 10 = 25. Сравнивая полученное решение с оценками множеств G2(v) приходим к выводу, что лучшего решения в этих множествах нет, и они могут быть отброшены (рис. 3.20). 3. Отбрасывание вариантов. Если стоимость найденного варианта (25) оказалась бы выше стоимости какого-нибудь из «отвергнутых» вариантов (из множеств G2(i)), то пришлось бы раскрывать другой вариант. В данном случае задача решена. Резюме Задача коммивояжера относится к классу неполиномиально слож­ных, или комбинаторных задач. Точное решение задачи может быть найдено только перебором вариантов. Метод ветвей и границ позволяет оценить решения, содержащиеся в некоторых подмноже­ствах вариантов и выбрать для развития такое подмножество, для которого оценка вариантов наилучшая. Отбрасывание вариантов осуществляется по сравнению оценок или по достижению предель­ного или приемлемого решения. Лекция № 6 МАТРИЧНЫЕ ИГРЫ И АНАЛИЗ КОНФЛИКТНЫХ СИТУАЦИЙ Анализ конфликтных ситуаций можно описать с помощью теории игр. В этом случае критерий эффективности для принятия реше­ний будет зависеть не только от действий оперирующей стороны (переменных х € X), но и от неуправляемых переменных у Y. Оптимизировать этот критерий Эти переменные могут принимать случайные значения, и если известна информация о вероятностях их появления pi), i = 1, т, то го­ворят о статистических играх или об игре с природой. Если вектор у находится в распоряжении противника или конкурента, то гово- рого игрока, конечны, то такая конечная игра называется матричной игрой двух лиц. Критерий эффективности может зависеть и от слу­чайностей F(xi,yj,Zk), где z = (z1, ..., zl) Z-случайные параметры с известными вероятностными характеристиками р. Критерий эффективности в теории игр представляет собой функцию выигрыша. Пусть F1(x,y,z) - функция выигрыша первого игрока, F2{x,y,z) - функция выигрыша второго игрока. Если F1(x,y,z) + F2(x,y,z) = 0, то говорят об игре с нулевой суммой. В этом случае выигрыш первого игрока равен проигрышу второго игрока. Тогда достаточно рассмотреть только функцию выигрыша первого игрока, и задача сводится к максимизации выигрыша первого игрока в предположении, что второй игрок стремится минимизировать свой проигрыш: Реализация конкретных стратегий двух игроков хi и yj (личные ходы) называется партией. Если в игре есть случайные ходы zk , функция выигрыша F(xi, yj, zk) принимает случайные значения. Усреднением игры называется математическое ожидание функции выигрыша L(x,y) = *pk , эту величину выигрыша можно к рассматривать как средний выигрыш при реализации достаточно большого числа партий. 4.1. Пример игры Игра состоит из четырех ходов: 1) х = {1, 2} - личный ход первого игрока - выбирает одно из двух чисел; 2) z1 = {решка, герб} - случайный ход с равными вероятностями (Р(р) = 0,5; Р(г) = 0,5) - бросается монета, и если выпадает герб, ход первого игрока известен второму игроку; 3)у= {3, 4} - личный ход второго игрока - выбор одного из двух чисел; 4) z2 = {I, 2, 3} (Р(1) = 0,4, Р(2) = 0,2, Р(3) = 0,4) - случайный ход. Функция выигрыша: Составим «дерево» игры - возможные варианты развития игры (рис. 4.1). После первого случайного хода второй игрок может находиться в одном из трех состояний информированности: 1) знает, что первый игрок выбрал 1; 2) знает, что первый игрок выбрал 2; 3) находится в состоянии неопределенности относительно хода первого игрока. Конечные вершины этого дерева представляют собой результат игры (функцию выигрыша первого игрока) при различных реализациях игры в каждой партии. Результат игры в каждой партии носит случайный характер в зависимости от сочетания случайных ходов. Рис. 4.1. Дерево игры Возможные сочетания случайных ходов z1, z2 и их вероятности (эти ходы независимы) представлены в следующем виде: Для первого игрока возможны только две стратегии: x1 = 1 и x2 = 2. Выбор второго игрока богаче: он может выбирать между числами 3 и 4, не зная выбора первого игрока или обладая информацией о его выборе. Возможные стратегии обозначим тройкой чисел. Так, стратегия (3, 4, 3) означает, что второй игрок выбирает 3, если знает, что первый игрок выбрал 1; 4 - если нет информации о выборе первого игрока; 3 - если первый игрок выбрал 2. Средний выигрыш первого игрока в зависимости от принятых стратегий представлен в табл. 4.1. Так, если первый игрок все время выбирает 1, а второй игрок всегда выбирает 3, то средний выигрыш (элемент матрицы выигрышей l11) составит l 11 = (—5* 0,2 + 6 *0,1 —7 *0,2)+ (—5 *0,2 + + 6*0,1 — 7 • 0,2) = —3,6. Здесь первая группа слагаемых соответ­ствует случайному ходу - выпадению герба, вторая - выпадению решки. Аналогично вычисляются и остальные элементы матрицы выигрышей. 4.2 Пример принятия решения в условиях неопределенности Рассмотрим основные подходы принятия решений в условиях неопределенности на простом примере. Оборудование (станок, компьютер и т.п.) после некоторого периода эксплуатации может находиться в одном из трех состояний: у1 - исправен, у2 - работает неустойчиво, у3 - сломан. Решение может быть принято ко всей партии оборудования: x1 - профилактика, x2 - текущий ремонт, х3 -капитальный ремонт. Затраты на проведение операции даны в мат­рице (табл. 4.2), р(у) - вероятно­сти нахождения оборудования в состоянии у . Здесь возможны три различных подхода. 1. Принцип максимального правдоподобия. В соответствии с этим принципом выбирается такое состояние «природы», которое наиболее вероятно, т.е. из вектора р выбирается максимальная компонента и считается, что «природа» будет находиться в этом состоянии. Для данного примера наиболее вероятное состояние -оборудование исправно с вероятностью р\ = 0,6. Функция затрат должна быть минимизирована: оптимальная стратегия - выполнить профилактический ремонт. На практике выбирают этот принцип, если максимальная вероятность значительно больше вероятности других состояний. 2. Принцип Байеса состоит в том, что оперирующая сторона рассчитывает на минимум средних затрат. В этом случае при применении стратегии х\ средние затраты составят Соответственно для других стратегии оперирующей стороны имеем Минимизация средних затрат даёт и оптимальную стратегию - текущий ремонт. 3. Если неприемлемы по тем или иным причинам предыдущие подходы, например «природа» может находиться в равновероятных состояниях, то можно применить гарантированную оценку. В этом случае считается, что «природа» будет реализовывать такой век­тор р, чтобы принести возможно больший вред, максимизировав функцию потерь, т.е. «природа» рассматривается как противник, реализующий наиболее выгодную для себя стратегию. Рассмот­рим поведение оперирующей стороны с точки зрения противника. Если будет реализована стратегия х\, то противник должен при­менить стратегию, максимизирующую затраты (усреднение снизу): Соответственно F(x2) = 8F(x3)=9. Оперирующая сторона выбирает свою стратегию как минимальную из оценок что соответствует стратегии х1. Подводя итог, видим, что при различных принципах принятия решений оптимальные из них могут быть различны, и результат зависит от психологии лица, принимающего решение. Первый подход отражает оптимистическую точку зрения на развитие собы­тий, ей соответствуют минимальные затраты, которые могут быть существенно превышены при неблагоприятном стечении обстоя­тельств. Третий подход характерен для осторожного человека, он гарантирует, что затраты не превысят расчетного значения в самом неблагоприятном случае, однако в реальности могут оказаться существенно меньше. Наконец, второй подход занимает среднее положение и рассчитан на средний результат при проведении боль­шого количества подобных операций. Лекция № 7 4.3 Чистые и смешанные стратегии Пусть известна матрица конечной игры размером п* т например, приведенная в табл. 4.3. Определим наилучшие стратегии второго игрока, стремящегося ми­нимизировать выигрыш первого игрока, если первый игрок приме­няет стратегию х. Так, если пер­вый игрок будет все время делать ход x1, то второй игрок, то второй игрок, минимизируя свой проигрыш, должен выбрать стратегию y4 с результатом игры В общем случае - наилучшая стратегия второго игрока. Аналогично - наилучшая стратегия первого игрока при применении вторым игроком стратегии у.Вычислим нижнюю цену игры и верхнюю цену игры Нижняя цена игры гарантирует выигрыш первого игрока при оптимальной стратегии не менее чем а, верхняя цена игры гаран­тирует проигрыш второго игрока не более чем р. Если а = р = с, то игра с седловой точкой, с - цена игры. Если с — О, то игра справедливая. В силу определения функций А(х) и В(у) Если  то говорят, что игра имеет седловую точку, и функция выигрыша имеет конфигурацию седла для первого и второго игрока (рис. 4.2). Рис. 4.2. График функции с седловой точкой Для этой функции безразличен порядок выполнения операций минимизации и максимизации, общий минимакс или максимин все равно будет в седловой точке, т.е. если сначала определить опти­мальную стратегию первого игрока, потом оптимальную стратегию второго, то они совпадут - игра с результатом с = а = р. Опти­мальные стратегии обоих игроков и результат игры в разобранном примере выделены курсивом. Такие стратегии, выбранные игро­ком, называются чистыми стратегиями. Если верхняя цена игры не совпа­дает с нижней, определение опти­мальных стратегий становится бо­лее сложным. Рассмотрим следу­ющий пример игры без седловой точки (табл. 4.4). Если первый игрок применяет стра­тегию x2 , то его выигрыш  = 4 единиц при наилучшей стратегии (у2) второго игрока. Гарантированный проигрыш второго игрока равен  = 5 - при правильном выборе стратегии (у1) больше 5 он не проиграет. Таким образом, верхняя цена игры не равна нижней цене игры и образуется ничейная зона (рис. 4.3). Рис. 4.3. Верхняя и нижняя цены игры без седловой точки Борьба за ничейную зону состоит в продвижении вправо для первого игрока и влево для второго игрока соответственно. И в результате этой борьбы устанавливается некое равновесие. Если кто-либо из игроков будет обладать информацией о ходе соперника, он получит преимущество и может закончить игру с лучшим для себя результатом, чем гарантированная оценка. Так, в примере если второй игрок знает, что будет сделан ход х2, он может выбрать ход y2 и проиграть всего 4 единицы. Однако, если первый игрок догадается, что будет сделан ход y2, он может при­менить стратегию х1 и выиграть уже 6 единиц. Отсюда следует, что каждому игроку нужно сохранять свой ход в тайне от соперни­ка. Однако единственный способ надежно сохранить секрет - не знать его. Для этого при выборе хода нужно включить механизм случайного выбора. Рассмотрим вероятности р = (р1, р2, ..., pn), pi = 1 и q = = (q1 ,q2,,.....qm) = qi=1 которыми случайным образом будут выбираться стратегии x и y. Чистая стратегия - когда какая-либо из вероятностей хода равна единице, тогда остальные вероятности равны нулю и игрок точно знает свой ход. Смешанная стратегия - в выборе хода присутствует элемент случайности. Вероятность ни одного хода не равна единице. Игрок сам не знает, какой ход будет сделан. Поскольку в поведении любого игрока при выборе определенной стратегии присутствует какая-либо закономерность, которая может быть замечена соперником, лучшая стратегия - не знать заранее своего хода, тогда игрок просто не сможет выдать себя. Теперь в распоряжении игроков вмеcто выбора чистой страте­гии х и у имеется выбор вероятностей р и q. Функция выигрыша будет иметь случайные значения с математическим ожиданием в задачу первого игрока входит максимизация этой функции по р, в задачу второго - минимизация этой функции по q: Лекция № 8 4.4 S-игра и доминирующие стратегии Представим стратегии второго игрока как т точек С1 ,C2, ..., Ст в ++-мерном пространстве выигрышей первого игрока. Тогда игра состоит в выборе вторым игроком точки С, и в выборе первым игроком проекции этой точки на ось Игру 2хm можно изобразить на плоскости (рис. 4.4). Рис. 4.4. S-игра на плоскости У первого игрока два возможных варианта хода, две стратегии. Второй игрок имеет в своем распоряжении т стратегий. Чистая стратегия соответствует тому, что один игрок определяет номер точки, а другой игрок выбирает ось, на которую будет осуществляться проекция: абсцисс или ординат. Тем самым он определяет ход, результат партии становится определенным. Будем рассматривать положительные элементы матрицы, но это несущественно, так как всегда можно прибавить ко всем элементам матрицы положительную константу и перейти в положительную четверть плоскости. Следует иметь в виду, что цена игры также увеличится на эту константу. Натянем на множество точек С выпуклую оболочку. Пусть точ­ка s - какая-то точка, принадлежащая этому выпуклому множеству. Эту точку можно представить в виде линейной комбинации векто­ров - координат точек S-игры: С другой стороны, если второй игрок выбрал в (4.10) конкретный вектор вероятностей q = то математическое ожидание функции выигрыша будет Сравнивая два последних выражения, видим, что любая сме­шанная стратегия представляет собой точку выпуклой оболочки S-игры. В частности, если одна из вероятностей qj= 1, то и вес j = 1, и это соответствует чистой стратегии уj, а значит, выбору точки Cj. Можно утверждать, что выбор смешанной стратегии вто­рого игрока - выбор точки из этого множества. Рассмотрим внутреннюю точку множества S, например точку S1 на рис. 4.5. Рис. 4.5. К определению доминирующих стратегий В случае использования первым игроком стратегии x1 будет получен результат игры l11, стратегии x2 - результат l12. Рассмотрим точку S2, соответствующую некоторой другой сме­шанной стратегии второго игрока. Результат игры при любой стратегии первого игрока будет лучше, так как обе координаты имеют большее значение в точке S1. Тогда говорят, что страте­гия S2 доминирует над стратегией S1 , и стратегия S1 может быть отброшена как заведомо невыгодная. В общем случае стратегия S2 доминирует над стратегией S1 с точки зрения второго игрока, если выполняются такие неравенства для всех компонент векторов. С другой стороны, стратегии S1 и S3 не доминируют одна над другой. Очевидно, что для любой внутренней точки множества S всегда найдется точка, лежащая левее и ниже этой точки. Таким образом, в качестве оптимальных стратегий второго игрока могут рассмат­риваться только точки множества S, лежащие на «юго-западной» границе множества, т.е. отрезки, соединяющие точки С1, С2, C3, C4. Это позволяет во многих случаях резко сократить размерность мат­рицы игры, в данном случае с т до 4, так как остальные стратегии могут быть отброшены. Рассмотрим «юго-западную» границу некоторого множества S - множество недоминирующих страте­гий, состоящее из отрезков, соединя­ющих точки С1, С2, C3, (рис. 4.6). Будем выдвигать квадратный клин со стороной , одна из вершин которого расположена в начале координат. Если сторона клина  достаточно мала (к чему стремится второй игрок, уменьшая свой проигрыш), нет ни одной стратегии с проигрышем . Если сторона клина слишком велика: (к чему стремится первый игрок, увеличивая свой выигрыш), величина выигрыша недостижима для первого игрока, так как вершина клина попадает во внутреннюю область множества S и второй игрок может уменьшить этот выигрыш, выбрав доминирующую стратегию. Равновесие наступает, если клин касается границы мно­жества. Тогда в точке  касания клином отрезка [С2, C3] достигается оптимальная стратегия второго игрока, выигрыш первого игрока гарантированно составляет величину  вне зависимости от выбора проекции этой точки. Вероятности q1 и q2 пропорциональны величинам разбиения отрезка [С2 , С3] на две части. Из этого примера видно, что ненулевых вероятностей q в задаче 2хm не может быть больше двух. Стратегии, вероятности применения которых больше нуля, называются полезными стратегиями. В общем случае, как это будет следовать из свойств задачи линейного программирова­ния, число полезных стратегий не превышает min {п, т}. Если клин касается границы множества S в точке С, как изобра­жено на рис. 4.7, то задача имеет седловую точку, полезная стратегия одна, вероятность ее применения равна единице, оптимальной яв­ляется чистая стратегия. Рис. 4.7. Оптимальная чистая стратегия 4.5. Решение игр Предположим, что первый игрок выбрал оптимальные стратегии с - средний выигрыш первого игрока, когда второй игрок применяет стратегию у1, но если x1 не оптимальная, то цена игры. Для всех стратегии первого игрока получаем систему из т уравнений: Предположим, что цена игры больше 0, с > 0; для этого необходимо, чтобы все элементы матрицы L были больше нуля. Вспоминая определение двойственной задачи из разд. 1.3, ви­дим, что задача (4.14) является двойственной по отношению к задаче максимизации прибыли первого игрока. Прямая задача бу­дет соответствовать минимизации прибыли первого игрока, откуда определятся наилучшие стратегии qj второго игрока. В соответ­ствии с основным свойством двойственных задач значения крите­риев будут совпадать, верхняя цена игры равна нижней, или просто цене игры. Пример. Пусть дана матрица L, имеющая вид: Прибавим к матрице число, такое, чтобы все элементы матрицы были неотрицательные: Составим систему уравнений В задаче ЛП, чтобы перейти от системы неравенств к системе равенств, надо ввести новые переменные zi: Из 6 переменных  ,z1, z2, z3 только 3 должны составлять базис, остальные равны нулю. Примем z1 = z2 = z3 = 0, тогда система уравнений преобразуется к виду Решив данную систему, получим  = 0,05,  = 0,1,  = 0,05. Цена игры с = 1 )= 5, а вероятности оптимальных стратегий P1 =  c= 0,25, р2 = c = 0,5, рз = c = 0,25. Аналогично вычисляются вероятности q1, q2, q3 оптимальных стратегий второго игрока. Система уравнений для второго игрока имеет вид: Решая систему, находим q1 = q3 = 0,25, q2 = 0,5. В измененной матрице с = 5, в исходной с = 0, т.е. при разыгрывании большого числа партий, если ни один из игроков не ошибся, выигрыш каждого игрока будет равен нулю. Оптимальные стратегии: первый игрок должен применять стра­тегию х1 с вероятностью 0,607, стратегию х2 - с вероятностью 0,393 (при удалении стратегий строки и столбцы могут быть переставле­ны); второй игрок должен применять стратегию у2 с вероятностью 0,536, стратегию у4 - с вероятностью 0,464. Цена игры составит —2,068, игра несправедлива. Чтобы сделать игру справедливой, нужно значения функции выигрыша сместить на эту величину. Лекция № 9 4.6. Поведение двух конкурентов на рынке Рассмотрим модель поведения на рынке двух конкурирующих фирм, выпускающих аналогичный товар в объемах х и у, поль­зующийся неограниченным спросом. Цена на предлагаемый товар характеризуется убывающей функцией f(q) от объема продавае­мого товара q = x+y (рис. 4.10). Пусть издержки производства одинаковы для обеих фирм и представляют собой возрастающую функцию (1(x) = 2(у) =(х), показанную на том же рисунке. В этих условиях прибыль каждой фирмы определится следую­щими функциями: Рис. 4.10. Исходные данные к игре двух конкурентов Рассмотрим различные варианты поведения конкурентов с точ­ки зрения теории игр. А. Пусть будет игра с нулевой суммой с выигрышем первого игрока: Сведем игру к матричной, представив стратегии обоих игроков в дискретном виде: xi = ih1, yj =jh2, i,j =[1...N]. Ее решение приведено в документе Mathcad (рис. 4.11). В соответствии с этим решением второй игрок Должен поддерживать максимальный объем продаж с целью снизить цены и минимизировать прибыль первого игрока. Первый игрок находит оптимальный объем производства в этих условиях, однако получает меньшую прибыль, чем второй игрок. Б. Если первого игрока не устраивает подобная ситуация, он мо­жет также поставить своей целью разорение второго игрока. Если они меняются местами, то в силу симметрии функций оптимальная стратегия первого игрока становится оптимальной для второго игрока, и наоборот. Если же каждый стремится разорить конку­рента, он должен максимизировать выпуск своего товара, и тогда они получат прибыль каждый в размере L1 =0,353, что меньше для каждого игрока, чем в случае А. В. Если конкуренты смогут договориться о разделе рынка, то они могут достичь наиболее выгодного для каждого из них результата с прибылью 2,236 единиц. Этот вариант рассматривается в лабораторной работе. Выводы Принятие решений в условиях неопределенности может быть основано на принципах максимального правдоподобия, Байеса или гарантированных оценок. В первом случае за состояние «природы» принимается наиболее вероятное состояние. Во втором случае (статистическая игра, или игра с «природой») усредняется значение критерия эффективности в соответствии с известными ве­роятностями их появления. В третьем случае (стратегическая игра) оперирующая сторона рассчитывает на самый неблагоприятный для себя случай, что сводится к вычислению операций минимакса и максимина. Если минимакс равен максимину - игра с седловой точкой, и решение может быть принято оперирующей стороной. В про­тивном случае решение находится в классе смешанных стратегий и представляет собой случайный выбор с вероятностями, подлежа­щими определению. Решение матричных игр двух лиц сводится к решению задачи линейного программирования. Лекция№9 Оптимизация эконом. статики. Функции полезности и производственные функции В данной главе будут рассмотрены простые статические модели, связанные с принятием решения в задаче потребительского выбора и оптимизации производственных функций. Первая группа задач связана с понятием функции полезности, которая отражает предпочтения потребителя. Естественно, у раз­ных потребителей и предпочтения могут быть разными. Функция полезности является попыткой формализовать эту неформальную задачу. Вид этой функции и ее параметры (коэффициенты важно­сти) характеризуют предпочтения конкретного потребителя. Построить адекватную модель производства на основе законов физики, химии, балансовых и подобных законов пока еще, как правило, невыполнимая задача. В этих условиях часто прибега­ют к эмпирическому построению модели производства. Для этого собирают статистику о функционировании производства за опреде­ленный период и пытаются подобрать производственную функцию, задавая ее подходящий вид и определяя значения ее параметров из условия наилучшего соответствия экспериментальным данным. С точки зрения методов оптимизации рассматриваемые задачи относятся к задачам нелинейного программирования с ограничени­ями, как правило, в виде неравенств. 5.1. Оптимизация функции полезности В данном разделе рассматриваются некоторые модели потребитель­ского выбора и задача максимизации полезности. Пусть потребитель располагает некоторой суммой средств I, которые он может потратить на приобретение благ. Решается статическая задача, т.е. отсутствует возможность делать накопления и уровень цен остается фиксированным. Как наилучшим способом подойти к распределению доходов, зная функцию полезности f(х), где вектор х = (х1,,х2, ..., хn) - расход на приобретение соответ­ствующих благ? Функции полезности f(х1,х2) соответствует оценка потребителем набора (х1, х2,). Причем, если набор а предпочтительнее набора b, то f(a) > f(b). Постулируют следующие свойства функции полезности. Если х1> хi то f(х1,хi ..., хn) >f(х1,хi ..., хn) - возрастание потребления любого продукта при сохранении потребления всех других продуктов ведет к возрастанию полезности, т.е. Эти частные производные называются предельной полезностью каждого продукта Предельные полезности убывают с ростом потребления, т.е. Предельная полезность каждого продукта увеличивается, если растет объем потребления любого другого продукта, т.е Линии равного уровня функции полезности f(х) = const именуют линиями безразличия. Задачей потребительского выбора (оптимального поведения на i рынке) называют задачу максимизации полезности при условии бюджетных ограничений: Набор х°, являющийся решением данной задачи, называют ло­кальным рыночным равновесием. Это задача нелинейного програм­мирования, но ее решение, учитывая свойства функции полезности, имеет простой геометрический смысл. Вначале рассмотрим потребительский набор из двух благ, на­пример x1 -сумма, потраченная на питание, х2- сумма, потраченная на приобретение одежды. Пусть функция полезности имеет следу­ющий вид: минимально необходимый уровень затрат на питание и одежду; Оптимальному потребительскому набору будет соответствовать точка касания бюджетного ограничения одной из линий безразли­чия, соответствующей максимально достижимой полезности, так, как изображено на рис. 5.2. Для оптимизации полезности функции многих переменных можно использовать следующую программу (рис. 5.3), исходными данными в которой служат функции полезности. Рис. 5.3. Оптимизация функции полезности Производственные функции. Оптимизация производственных функций Производственная функция - это неотрицательная функция, определяющая значения объемов выпускаемой продукции (дохода) в зависимости от объема затрачиваемых ресурсов х. На микроэкономическом уровне ПФ определяет зависимость между объемом выпускаемой продукции и затратами фирмы (пред­приятия), на макроэкономическом уровне - подобную зависимость в масштабах региона или страны. Часто используют производственную функцию Кобба - Дугласа Здесь К - затраты на капитал, L - затраты на труд. Параметры аi и график функции приведены в документе Mathcad (рис. 5.4), где Рис. 5.4. Графики производственной функции Очевидно, что значения ПФ расположены в положительной части пространства х, функция выпукла вверх и монотонно уве­личивается с ростом аргументов. Для учета научно-технического прогресса в функцию часто вводят дополнительный экспоненциальный множитель: Для экономики бывшего СССР = 0,0294. Максимизация функции полезности без ограничений не имеет решения: функция неограниченно возрастает. Если ввести цену В документе Mathcad (рис. 5.5) представлены результаты реше­ния этой задачи для приведенной ПФ. Рис. 5.5. Оптимизация производственной функции Аналогичная задача может быть представлена для предприятия несколько по-другому. Пусть произведенная продукция, определя­емая производственной функцией f(x1,x2), имеет цену со, а затра­чиваемые ресурсы - цены с1 и с2 соответственно. Тогда нужно максимизировать прибыль - разницу между доходом и затратами: при условии Решение этой задачи при той же производственной функции дано в документе Mathcad на рис. 5.6. Рис. 5.6. Оптимизация прибыли с использованием производственных функций Более содержательной представляется задача распределения указанных ресурсов между несколькими предприятиями в задаче микроэкономики или несколькими отраслями в задаче макроэконо­мики со своими производственными функциями: причем по каждому виду ресурсах, имеется ограничение Требуется максимизировать суммарный доход при указанных ограничениях. Решение этой задачи приведено в документе Mathcad (рис. 5.7) для трех секторов экономики со своими произ­водственными функциями и оптимальными вложениями капитала в эти секторы. Рис. 5.7. Оптимизация в трехсекторной экономике Резюме Представленные статические экономические модели позволяют на основе предпочтений ЛПР оптимизировать задачу потребительско­го выбора или на основе статистики построить производственную функцию экономической единицы (предприятия, отрасли) и выяс­нить действие факторов, влияющих на экономический рост. Лекция №10. ОПТИМИЗАЦИЯ ЭКОНОМИЧЕСКОЙ ДИНАМИКИ Экономические задачи могут рассматриваться в статике, без учета изменений их параметров во времени. В динамических задачах ана­лизируется изменение основных экономических параметров в их взаимосвязи и в зависимости от времени. Время в динамических задачах может рассматриваться как дискретное, так и непрерыв­ное. В первом случае исследуется изменение параметров скачком за фиксированное время, например за год, и аппаратом для их ана­лиза служат разностные уравнения. Во втором случае параметры изменяются непрерывно, и их изменение описывается дифферен­циальными уравнениями. Так как одним из методов решения дифференциальных уравнений выступает метод конечных разно­стей, уровень сложности моделей примерно одинаков, результаты моделирования сопоставимы. Основными показателями экономической динамики являются Темпы прироста для дискретного случая определяются как аппроксимация производной конечной разностью 6.1. Стационарные точки и устойчивость динамических моделей Напомним некоторые сведения о дифференциальных уравнениях. Задачей Коши называется решение системы уравнений первого с известными начальными условиями Аналитическое решение этой задачи возможно лишь в частных случаях. Численное решение можно выполнять различными мето­дами. Мы используем простейший метод Эйлера Если шаг интегрирования совпадает с периодом дискретной модели, это соотношение и есть дискретная модель. Однако следует иметь в виду, что между дискретной и непрерывной моделью есть соответствие с точностью порядка ch при условии устойчивости разностной схемы. Стационарной точкой называется решение алгебраического уравнения Вопрос об устойчивости стационарного состояния решается на основе линейного приближения - линейного дифференциального уравнения в отклонениях от стационарной точки: Вопрос об устойчивости равновесного состояния решается в связи с собственными числами матрицы частных производных А. Если все действительные части собственных чисел матрицы А отрицательны, точка х устойчива. Для линейного уравнения справедлива формула Коши В этой формуле первое слагаемое описывает поведение системы при нулевых начальных условиях, второе - влияние на решение возмущающих или управляющих переменных и. Отрицательность собственных чисел обусловливает стремление первого слагаемого к нулю и тем самым возврат решения к стационарной точке при отсутствии возмущений. 6.2. Простейшие модели экономической динамики Паутинообразная модель динамики. Эта модель позволяет ис­следовать устойчивость цен и объемов производства на рынке, описываемом кривыми спроса и предложения некоторого товара. характеризует объем предложения товара в зависимости от его це­ны. Равновесная цена pi рынка определяется равенством спроса и Пусть производитель товара определяет объем предлагаемого товара на основе спроса и цен, установившихся в предшествующем периоде: Схема решения этого уравнения проста: через объем Qo в начальный период определяем Объем производства товара в следующий период определится спросом так далее. Если кривые спроса и предложения не меняются, то колебания цен будут определяться только начальным отклонением цены от равновесной. Динамику цен и объемов производства в этом случае иллюстрирует документ Mathcad на рис. 6.1. Модель Калдора. Рассмотрим вопрос об устойчивости ре­шения обыкновенного дифференциального уравнения (ОДУ) на примере модели Калдора, пытающейся объяснить циклические ко­лебания экономической активности факторами формирования сбе сбережений и инвестиций являются не линейными, а логистически­ми (.S-образными) функциями. Пример таких функций приведен в документе Mathcad на рис. 6.2. Равновесие достигается при такой величине дохода у, когда S(y) = I(у). Таких точек три, однако устойчивых только две: у1 и уз, так как именно в них производная функции f{y) = I(y) — S(y) отрицательна. Изменение дохода в такой системе можно представить в виде дифференциального уравнения с начальным условием Если величина дохода соответствует одному из равновесных состоянии, он может сохраняться неограниченно долго. Однако любые изменения в экономической ситуации приведут при неустойчивом равновесии (в точке у2) к переходу в одну из устойчивых точек у1 или у3 в зависимости от ухода влево или вправо от положения равновесия. Для устойчивых точек при малых отклонениях от положения равновесия произой­дет возврат к этому же состоянию. Однако это справедливо при постоянных функциях инвестиций и сбережений. Периодические изменения деловой активности приведут к деформации этих функций, что и объясняет циклический характер развития. Документ Mathcad на рис. 6.3 иллюстрирует эти случаи. Рис. 6.2. Модель Калдора Рис. 6.3. Устойчивые точки равновесия Модель Самуэльсона - Хикса. В этой модели представлены два субъекта хозяйствования: домашние хозяйства и фирмы. Объем потребления в текущем периоде определяется величиной дохода предыдущего периода: Объем инвестиций зависит от прироста дохода предшествую­щего периода: Если обозначить через Bt внешние инвестиции, получим раз­ностное уравнение этой модели: Непрерывный аналог этой модели представлен следующим дифференциальным уравнением второго порядка: В матричном виде эту систему можно записать так: В документе Mathcad на рис. 6.4 дано сравнение решений дискретной и непрерывной модели с постоянным значением В. Стационарная точка модели определяется из (6.12) при равен­стве производных нулю: устойчивость этой точки - собственными числами  матрицы А. Если действительные части собственных чисел отрицательны, си­стема устойчива. Отметим, что в случае комплексно-сопряженных корней характеристического уравнения в системе присутствует колебательное движение. Так, в данном примере система колеба­тельная и устойчивая. На графике приведено разбиение области изменения параметров задачи на области монотонного (выше и сле­ва от разделяющей область кривой) и колебательного движений. Лекция №11 6.3. Динамика несвязанных секторов экономики Для примера рассмотрим динамику несвязанной трехсекторной эко­номики - производство средств производства с производственной капитала и труда соответственно в каждом секторе. Если через i обозначить долю произведенного продукта, идущего на накопление капитала, через i - долю выбытия капитала в каждом из секторов, то для изменения капитала во времени имеем следующую систему дифференциальных уравнений: ние дифференциального уравнения покажет изменение капитала, следовательно, и производства во времени. Эти изменения иллю­стрирует документ Mathcad на рис. 6.5. Из приведенных графиков видно, что с течением времени капи­тал и остальные показатели стабилизируются. Стационарная точка определится как решение системы алгебраических уравнений, при­чем эта точка не зависит от начальных условий - первоначального вложения капитала: Поскольку эти уравнения не связаны, их можно решать каждое в отдельности. Решение для одного из уравнений (первого) при­ведено в документе Mathcad на рис. 6.6. Устойчивость этой точки можно определить по знаку производной. Так как производная от­рицательна, стационарная точка устойчива. Рис. 6.5. Динамика несвязанных секторов экономики 6.4. Динамика связанных секторов экономики Рассмотрим модель трехсекторной экономики, охватывающей про­изводство средств производства, производство предметов потреб­ления и производство культурных ценностей с производственными Рис. 6.6. Определение стационарной точки и устойчивости Тогда динамику экономики можно описать векторным дифференциальным уравнением где К, Y,L— векторные функции соответствующей размерности, в данном случае 3. Это уравнение должно быть дополнено начальными условия­ми - распределением капитала в начальный момент времени К(0) = — К0, Если трудозатраты считаются постоянными, то L = L°. Рассмотрим конкретный пример развития экономики для матрицы инвестиций Такая матрица означает, что капитальные вложения в первый сектор составляют 10% его дохода, во второй - равны 10% до­хода первого сектора и 20% дохода второго, в третий сектор -10% дохода второго сектора экономики. Задавая конкретный вид производственных функций, доли выбытия капитала и начальные условия, получим развитие экономики, представленное в документе Mathcad на рис. 6.7. Рис. 6.7. Динамика связанных секторов экономики Лекция № 12. Принцип максимума Понтрягина и его применение в задачах динамики 6.5. Формулировка принципа максимума Понтрягина Рассматривается управляемая система с ОДУ с начальными и конечными условиями и критерием эффективности Введем дополнительную переменную хо, подчиняющуюся дифференциаль­ному уравнению Эта переменная представляет собой значение критерия в теку­щий момент времени Теперь будем рассматривать расширенную систему ОДУ Введем гамильтониан Н и вектор сопряженных переменных p: или, в скалярной форме: соответствующая ему траектория x(t), выходящая из точки х(0), проходит в момент времени Т через точку х(Т). Для оптимальности управления u(t), траектории x(t) необходимо существование такой б) в конечный момент времени t = Т выполняется соотношение Таким образом, принцип максимума требует решения краевой двухточечной задачи для решения которой необходимо задать 2т начальных условий. В задаче с фиксированным временем и закрепленными концами содержится необходимое число констант для определения решения. Исключая из дифференциальных уравнений неизвестных вектор-функции х и р. Принцип максимума дает необходимые условия минимума интеграла (6.21) и основан на игольчатой вариации функционала. Достаточность принципа требует анализа второй вариации. От­метим только, что для линейных дифференциальных уравнений условия принципа максимума необходимы и достаточны. Наибольшую трудность в случае применения принципа макси­мума вызывает решение двухточечной краевой задачи. Кроме того, решение ищется в виде программного управления, т.е. функция u(t) является функцией времени. Динамическое программирование дает решение задачи в виде синтеза, управление и(х) является функцией координат динами­ческой системы, однако в непрерывной постановке приводит к решению задачи Коши, но для нелинейных уравнений в частных производных. Эта задача более сложная, чем решение обыкновен­ных дифференциальных уравнений, ее, как правило, решают на некоторой сетке, заменяя непрерывное время дискретными значе­ниями. 6.6. Задача с фиксированными концами (увеличение капитала до заданного значения) Применим принцип максимума для решения задачи оптимального накопления капитала от начального значения К(0) = К0 до конеч­ного значения К(Т) = К1 за фиксированное время Т. Уравнения движения имеют следующий вид: критерий оптимальности Гамильтониан сопряженная переменная на управление L наложены ограничения О < L < Lm. Решение этой задачи иллюстрирует документ Mathcad на рис. 6.8. В данном случае ограничение на предельные затраты на труд Lm = 5 оказалось неактивным. Если эти затраты не могут превы­шать 2,3 единицы, ограничение станет активным, решение задачи для этого случая показано на рис. 6.9. Рис. 6.8. Оптимальное увеличение капитала до заданного значения Рис. 6.9. Решение задачи с ограничениями на труд 6.7. Условия трансверсальности В общем случае конечное состояние системы (для простоты рас­смотрим этот случай, все рассуждения справедливы и для началь­ного состояния) задается на некотором множестве М\ (плоскости, линии и т.п.), а не в виде фиксированной точки пространства со­стояний. Пусть S1, S2,..., Sk, k =