<< Пред.           стр. 12 (из 13)           След. >>

Список литературы по разделу

  Особый интерес представляет частный случай задачи (5.24)- (5.25), при котором предполагается, что функции затрат на пополнение запаса ck(xk) являются вогнутыми по xk, a функции затрат на хранение sk(?k) являются линейными относительно объема хранимого запаса, т. е. . Параллельно заметим, что обе предпосылки являются достаточно реалистичными.
  Обозначим функцию затрат в течение k-го периода через
 
  (5.30)
 
 или, что то же самое,
 
  (5.31)
 
  В силу сделанных предположений все функции затрат fk(xk, yk+l) являются вогнутыми (как суммы вогнутой и линейной функций). Данное свойство значительно упрощает процесс решения, так как для поиска минимума вогнутых функций fk(xk, yk+l) достаточно рассмотреть только две крайние точки множества, на котором отыскивается минимум. С учетом введенного обозначения задачу (5.24)-(5.25) можно записать в виде:
 
  (5.32)
 
 при условиях
 
  (5.33)
 
  Рассмотрим процедуру решения (5.32)-(5.33). Так как ищется минимум суммы вогнутых функций fk(xk, yk+l), то решение будет достигаться на одной из крайних точек множества, определяемого условиями (5.33). Общее число переменных xk и yk в системе (5.33) равно 2п. Однако, учитывая то, что в ней только п уравнений, в оптимальном плане будет не более п ненулевых компонент, причем для каждого периода k значения xk и yk не могут равняться нулю одновременно (в силу необходимости удовлетворения спроса либо за счет заказа, либо за счет запаса). Формально это утверждение можно представить в виде условия дополняющей нежесткости:
 
  (5.34)
 
 где
 
  (5.35)
 
  С точки зрения содержательной интерпретации условия (5.34)-(5.35) означают, что при оптимальном управлении заказ поставщику на новую партию не должен поступать, если в начале периода имеется ненулевой запас, или размер заказа должен равняться величине спроса за целое число периодов. Отсюда следует, что запас на конец последнего периода должен равняться нулю: yn+1 =0. Последнее позволяет решать задачу в прямом направлении, применяя рекуррентное соотношение
 
  (5.36)
 где .
  Учитывая (5.34)-(5.35) и вогнутость fk(xk,?) , заключаем, что минимум (5.36) достигается в одной из крайних точек xk = 0 или xk=? + dk, поэтому
 
  (5.37)
 
  тогда для предыдущего периода функция состояния может быть выражена как
 
  (5.38)
 
 на основе чего в общем виде получаем модифицированную форму для рекуррентного соотношения
 
  (5.39)
 
  При дальнейших конкретизирующих предположениях о виде функций fk(xk, уk+1) можно получить еще более компактные формы для рекуррентных соотношений. Однако эти вопросы носят достаточно частный характер, и мы их рассматривать не будем. Отметим лишь, что приведенные в данном пункте преобразования неплохо иллюстрируют общие подходы, применяемые в динамическом программировании, а также те свойства задач, которые открывают возможности для эффективного и плодотворного использования соответствующих методов.
 
  КЛЮЧЕВЫЕ ПОНЯТИЯ
 
  > Аддитивная и мультипликативная функция.
  > Рекуррентное соотношения.
  > Принцип оптимальности Беллмана.
  > Отсутствие последействия.
  > Задача о найме работников.
  > Динамическая задача управления запасами.
 
  КОНТРОЛЬНЫЕ ВОПРОСЫ
 
 5.1. Для решения каких задач предназначен метод динамического программирования?
 5.2. В чем заключена суть метода динамического программирования?
 5.3. Каким условиям должна удовлетворять задача, чтобы для ее решения мог быть применен алгоритм динамического программирования?
 5.4. Какие трудности связаны с вычислительными алгоритмами динамического программирования?
 5.5. Что определяет направление решения задачи в алгоритмах динамического программирования?
 5.6. Сформулируйте математическую модель для задачи о найме работников.
 5.7. Выпишите основное рекуррентное соотношение, используемое при решении задачи о найме работников.
 5.8. С какими особенностями задач управления запасами связано применение при их решении аппарата динамического программирования?
 5.9. Какой вид имеет целевая функция в динамической задаче управления запасами?
 5.10. Выпишите основное рекуррентное соотношение, используемое при решении динамической задачи управления запасами.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
  ГЛАВА 6. КРАТКИЙ ОБЗОР ДРУГИХ РАЗДЕЛОВ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ
 
  Данная глава занимает особое положение среди остальных. Ее цель - представить читателю предельно краткую характеристику так называемых дополнительных разделов исследования операций. Поясним несколько смысл слова "дополнительный". Дело в том, что существуют различные подходы к классификации этих научных отраслей: иногда их считают составными частями исследования операций, а иногда рассматривают как самостоятельные дисциплины. Обе точки зрения имеют право на существование, но даже если придерживаться второй, разделы, о которых пойдет речь в настоящей главе, можно трактовать как смежные области знания, аппарат которых применим для решения задач исследования операций. Еще раз подчеркнем, что каждый параграф настоящей главы лишь обзорно затрагивает общие вопросы соответствующих тем, а полные учебные курсы по ним существенно превышают объем данной книги.
 
  6.1. ТЕОРИЯ ИГР
 
  6.1.1. Предмет теории игры. Задачи, рассмотренные в предыдущих главах, формулировались для ситуаций индивидуального выбора оптимальных решений, т. е. для случаев, когда решение принимает отдельно взятый субъект, обладающий единственной целью.
  Принципиально иная ситуация возникает при изучении процессов принятия решений несколькими субъектами, интересы которых могут не совпадать. При этом возникают задачи со многими целевыми функциями (критериями). Область математики, изучающая данные проблемы, получила название теории игр. Задачи теории игр относятся к области принятия решений в условиях неопределенности, а их специфика состоит в том, что, как правило, подразумевается неопределенность, возникающая в результате действий двух или более "разумных" противников, способных оптимизировать свое поведение за счет других. Среди типичных примеров такого поведения могут быть названы действия конкурирующих фирм на одном рынке или планирование военных операций.
  Одним из основных вопросов в задачах с коллективным выбором решений является вопрос об определении оптимальности, т. е. вопрос, какие решения следует признавать наилучшими в ситуации оптимизации по нескольким критериям, отражающим различные интересы. Многие методы решения проблем теории игр основываются на сведении их к задачам математического программирования. На наиболее простых из них мы остановимся в настоящей главе.
  - Теория игр берет начало от работ Э. Бореля (1921 г.), а принципиальным этапом в ее становлении как самостоятельного научного направления стала монография Дж. Неймана, вышедшая в 1944 г. [25].
  6.1.2. Терминология и классификация игр. Особенностью теории игр как научной дисциплины стала употребляемая в ней специфическая терминология. Термин "игра" применяется для обозначения совокупности правил и соглашений, которыми руководствуются субъекты, поведение которых мы изучаем. Каждый такой субъект k, где k ? 1: К, или игрок, характеризуется наличием индивидуальной системы целевых установок и стратегий ,т. е. возможных вариантов действий в игре.
  Достаточно распространенный способ математического описания игры основан на задании функций , каждая из которых определяет результат (платеж, выигрыш), получаемый k-м игроком в зависимости от набора стратегий , примененного всеми участниками игры. Функции fk,k?1:K также называют функциями выигрыша, или платежными функциями. В том случае, если для любых S
 
 
 
 игра называется игрой с нулевой суммой. Игру с двумя участниками и нулевой суммой называют антагонистической. Антагонистические игры, т. е. игры, в которых выигрыш одного участника равен проигрышу другого, в силу относительно простой постановки задачи являются наиболее изученным разделом теории игр. Однако содержание теории игр, безусловно, не исчерпывается ими. В классификации игровых моделей выделяют игры с конечными и бесконечными наборами стратегий у игроков, выделяют игры по возможным количествам ходов у участников. Также игры делят на некооперативные и кооперативные, т. е. те, в которых функции выигрыша участников зависят от образуемых ими коалиций. Помимо этого игры можно различать по объему информации, имеющейся у игроков относительно прошлых ходов. В этой связи они делятся на игры с полной и неполной информацией. Заинтересованный читатель может обратиться к таким источникам, как [17, 23].
  6.1.3. Матричные игры и понятие седловой точки. Рассмотрим более подробно антагонистические игры и их основные свойства. Удобным способом задания игры двух участников с нулевой суммой является платежная матрица. Отсюда, кстати, происходит еще одно их название - матричные игры. Каждый элемент платежной матрицы аij содержит числовое значение выигрыша игрока I (проигрыша игрока II), если первый применяет стратегию i, а второй - стратегию j. Термины выигрыш и проигрыш следует понимать в широком смысле, т. к. они могут принимать отрицательные значения и с житейской точки зрения означать противоположное. Нетривиальность задачи, прежде всего, заключается в том, что каждый из игроков делает свой выбор, не зная о выборе другого, что существенно осложняет процесс оптимизации выбираемой стратегии.
  Классическим примером антагонистической игры является игра с двумя участниками, загадывающими независимо друг от друга числа. Предполагается, что если их сумма оказывается четной, то выигрыш, равный 1, достается первому игроку, а если нечетной, то второму. Положив, что для обоих игроков загадывание нечетного числа является первой стратегией, а четного - второй, можем записать платежную матрицу данной игры:
 
 
  н/ч ч н/ч 1 -1 ч -1 1 (6.1)
 
  Строки матрицы (6.1) соответствуют стратегиям игрока I, столбцы - стратегиям игрока II, а ее элементы - результатам первого игрока. Также из определения игры следует, что элементы данной матрицы, взятые с обратным знаком, соответствуют выигрышам второго игрока.
  Более сложная и содержательная платежная матрица может быть получена, если несколько модифицировать предложенную игру. Допустим, что оба участника имеют право загадывать числа от 1 до 4, что составляет их соответствующие стратегии. В случае, если результат сложения задуманных чисел будет четным, то второй игрок выплачивает первому получившуюся сумму, а если нечетным, то первый - второму. Запишем платежную матрицу для такой игры:
 
  (6.2)
 
  Некоторая условность и искусственность в постановке проблемы не должны в данном случае нас смущать, так как к подобной форме может быть сведена модель, описывающая, например, соревнование двух фирм за вновь открывшийся рынок сбыта продукции и т. п.
  Как уже отмечалось, важнейшим в теории игр является вопрос об оптимальности решения (выбора стратегии) для каждого из игроков. Проанализируем с этой точки зрения некоторую матричную игру, для которой задана платежная матрица . При выборе игроком I стратегии i его гарантированный доход независимо от действий игрока II составит . Поскольку он может выбирать i самостоятельно, то целесообразно этот выбор сделать таким, чтобы он при любой стратегии противника максимизировал величину гарантированного дохода, т. е. обеспечивал получение , Такой принцип выбора стратегии получил название "принцип максимина". С другой стороны, аналогичные рассуждения могут быть проведены по поводу действий второго игрока. Его наибольший проигрыш при выборе стратегии j составит , и, следовательно, ему следует выбирать стратегию так, чтобы минимизировать величину проигрыша при любых действиях соперника, т. е. обеспечить . В этом суть принципа минимакса.
  Можно доказать справедливость следующего соотношения:
 
 ? (6.3)
 
  Однако очевидный интерес представляет ситуация, при которой значение выигрыша (платежа), получаемого игроком I при выборе им максиминной стратегии, равно платежу (проигрышу) II-го игрока при минимаксной стратегии
 
  = (6.4)
  В этом случае говорят, что игра имеет седловую точку. Совпадение значений гарантированных выигрышей игроков при максиминной и минимаксной стратегии означает возможность достижения в игре некоторого оптимального (стабильного, равновесного) состояния, от которого невыгодно отклоняться ни одному из участников. Понятие "оптимальность" здесь означает, что ни один разумный (осторожный) игрок не стремится изменить свою стратегию, так как его противник, в принципе, сможет выбрать такую стратегию, которая даст худший для первого результат. Стратегии и , образующие седловую точку, называются оптимальными, а значение . называют ценой игры. Тройка считается решением матричной игры с седловой точкой.
  Нетрудно заметить, что не всякая игра обладает седловой точкой. В частности, как игра (6.1), так и игра (6.2) седловой точки не имеют. Примером игры, имеющей седловую точку, является игра с платежной матрицей (6.5).
 
  (6.5)
  В данной матрице минимальные (гарантированные) выигрыши первого игрока по строкам равны 1, 5 и (-3). Следовательно, его максиминному выбору будет отвечать стратегия 2, гарантирующая выигрыш 5. Для второго игрока максимальные проигрыши по столбцам матрицы составят 8, 10, 5, 17, поэтому имеет смысл остановиться на стратегии 3, при которой он проиграет только 5. Таким образом, вторая стратегия первого игрока и третья стратегия второго образуют седловую точку со значением 5, т. е. для игры с матрицей (6.5) имеет решение (2; 3; 5).
  6.1.4. Смешанные стратегии. Дальнейшее развитие теории матричных игр основывается на исследовании игры как некоторого повторяющегося процесса. Действительно, вряд ли можно дать содержательные рекомендации по такому вопросу, как следует поступать участникам однократно проводимой игры, не имеющей седловой точки. В случае же ее многократных повторов естественной и плодотворной представляется идея рандомизации выбора стратегий игроками, т. е. внесение в процесс выбора элемента случайности. Действительно, систематическое отклонение, например, игрока I от максиминной стратегии с целью увеличения выигрыша может быть зафиксировано вторым игроком и наказано. В то же время абсолютно хаотичный выбор стратегий не принесет в среднем наилучшего результата.
  >Смешанной стратегией игрока I в игре с матрицей называется упорядоченный набор действительных чисел xi, i?1:m , удовлетворяющих условиям
 
  (6.6)
  Числа интерпретируются как вероятности применения игроком I стратегий 1,2,..., т, которые, в отличие от смешанных, также называют чистыми стратегиями.
  Аналогично вводится понятие смешанных стратегий игрока II, которые определяются как набор чисел уj, j?l:n, удовлетворяющих условиям
 
  (6.7)
 
  Тогда, если игрок I применяет смешанную стратегию х=(х1, х2, ..., хт), а игрок II смешанную стратегию у = (у1, у2,...,yn), то математическое ожидание выигрыша игрока I (проигрыша игрока II) определяется соотношением
  11 (6.8)
  В дальнейшем через X будем обозначать множество допустимых смешанных стратегий игрока I, определяемое условием 6.7, а через Y - определяемое условием 6.8 множество допустимых смешанных стратегий игрока П.
  К поиску решения игры в смешанных стратегиях, так же как и в п. 6.1.3, могут быть применены критерии максимина-минимакса. В соответствии с ними игрок I будет выбирать свою смешанную стратегию x=(xl, х2, ..., хт) таким образом, чтобы максимизировать наименьший средний выигрыш:
 
  (6.9)
 
 который, как можно доказать, равен
 
  (6.10)
 
 а игрок II - свою смешанную стратегию так, чтобы минимизировать наибольший средний проигрыш:
  (6.11)
 
 также равный
 
  (6.12)
  По аналогии с (6.3) для любых х е X и г/ € У справедливо неравенство
 
  ? (6.13)
 
  >Стратегии и называют оптимальными смешанными стратегиями, если для любых х?Х и y?Y справедливо равенство
 
  = (6.14)
 
  называют ценой игры, и если х* и у* существуют, то говорят, что игра имеет решение в смешанных стратегиях (х* , у*, v) .
  Справедлива фундаментальная теорема Дж. Неймана, которую мы приведем без доказательства.
 
  Теорема 6.1 (основная теорема матричных игр). Любая матричная игра имеет решение в смешанных стратегиях.
 
  Значение и нетривиальность теоремы (6.1) обусловлены прежде всего тем, что, как было показано в п. 6.1.3, в общем случае матричные игры в чистых стратегиях решения не имеют.
  6.1.5. Решение матричных игр методами линейного программирования. Рассмотрим некоторые способы решения матричных игр. Задача, решаемая первым игроком, (6.10) была сформулирована как максимизация наименьшей из сумм
 
 
 
 но если определить некоторое хт+1 , для которого выполняется
 
  (6.15)
 
 то она может быть сведена к задаче линейного программирования:
 
  (6.16)
 
 при ограничениях
 
  (6.17)
 
  Проведя аналогичные рассуждения, приходим к тому, что задача минимизации наибольшего ожидаемого проигрыша, решаемая игроком II (6.12), сводится к задаче линейного программирования
 
  (6.18)
 
 
  (6.19)
  Таким образом, мы получаем возможность применять все возможности аппарата линейного программирования для поиска оптимальных стратегий обоих игроков.
  Достаточно легко проверить, что задачи (6.16)-(6.17) и (6.18)-(6.19) образуют двойственную пару. Здесь в определенном смысле мы вернулись к проблемам, уже рассматривавшимся во второй главе, а именно к взаимосвязи между наличием решения у некоторой оптимизационной задачи и существованием седловой точки у соответствующей функции Лагранжа. В данном случае аналогичная связь прослеживается между седловой точкой игры и решением пары задач оптимизации.
  6.1.6. Графические методы решения игр. Следует отметить, что применение для решения задач (6.16)-(6.17), (6.18)-(6.19) стандартных алгоритмов линейного программирования далеко не всегда является рациональным. Помимо этого существуют иные методы, которые основываются на использовании специфики данных задач. В настоящем пункте мы остановимся на очень простом классическом способе поиска оптимальных смешанных стратегий в матричных играх, где один из участников имеет только две стратегии (это так называемые 2 ? п и т ? 2 игры).
  Для определенности положим, что игрок I имеет возможность выбирать между двумя стратегиями с вероятностями х1 и , тогда его ожидаемые выигрыши, соответствующие чистым стратегиям игрока II, примут вид
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
  Рис. 6.1
 или
 
 
 
 
 т. е. ожидаемые выигрыши могут быть представлены в виде графиков линейных функций, зависящих от переменной (рис. 6.1, где предполагается, что игрок II имеет три стратегии).
  Линии, изображенные на рис. 6.1, задают зависимости среднего выигрыша игрока I от значения вероятности х1, с которой он выбирает свою первую стратегию, для случаев, когда его противник выбирает первую, вторую или третью чистую стратегию. Тогда значениям минимального гарантированного дохода первого игрока соответствует нижняя огибающая всех трех прямых. Согласно принципу максимина, оптимальному выбору игрока I будет соответствовать наивысшая точка, лежащая на данной огибающей, отмеченная на рисунке как . Зная ее, можно определить оптимальную смешанную стратегию первого игрока и цену игры, равную z.
  Исходя из отношения двойственности, которым, как было установлено в п. 6.1.5, связаны задачи обоих игроков, по оптимальной стратегии первого участника х* однозначно определяется оптимальная стратегия его противника у*. Поскольку у* является результатом решения задачи линейного программирования, то он обладает всеми свойствами допустимого базисного плана, т. е. в случае 2 ? п игры имеет не более чем две ненулевых компоненты и не менее чем (n - 2) нулевых. Номера ненулевых элементов у* определяются номерами линий, пересечение которых определило оптимальную стратегию первого игрока. Действительно, игрок II знает оптимальную стратегию соперника, и применение им стратегий, соответствующих прямым, проходящим выше точки , только увеличило бы его проигрыш. В рассматриваемом примере это линии z2 и z3, и, следовательно, в своей оптимальной стратегии второй игрок должен с ненулевыми вероятностями применять вторую и третью чистые стратегии (у2>0, у3>0). На основе этого, а также учитывая условие нормировки
 
 
 
 можем выразить: у3=1-у2, тогда оптимальное значение может быть найдено из условия
 
 
 
  или
 
 
 
  В результате получаем оптимальную стратегию игрока .
  Очевидно, что поиск решения в игре т ? 2 осуществляется аналогичным образом с точностью до наоборот: строятся графики, ожидаемого проигрыша игрока II, находится их верхняя огибающая и т. д.
  Безусловно, графический способ в силу ограниченности круга задач, к которым он может быть применен, имеет скорее теоретическое, чем практическое значение. Однако он хорошо иллюстрирует содержательную сторону процесса поиска решения в игре.
 
 
  6.2. ТЕОРИЯ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ
 
  6.2.1. Постановка и классификация задач теории оптимального управления. В подавляющем большинстве рассмотренных нами задач факторы, связанные с изменением изучаемых объектов и систем в течение времени, выносились за скобки. Возможно, при выполнении определенных предпосылок такой подход является конструктивным и правомерным. Однако очевидно и то, что это допустимо далеко не всегда. Существует обширный класс задач, в которых необходимо найти '' оптимальные действия объекта, учитывающие динамику его состояний во времени и пространстве. Методы их решения составляют предмет математической теории оптимального управления.
  В весьма общем виде задача оптимального управления может быть сформулирована следующим образом:
  Имеется некоторый объект, состояние которого характеризуется двумя видами параметров - параметрами состояния и параметрами управления, причем в зависимости от выбора последних процесс управления объектом протекает тем или иным образом. Качество процесса управления оценивается с помощью некоторого функционала 12, на основе чего ставится задача: найти такую последовательность значений управляющих параметров, для которой данный функционал принимает экстремальное значение.
  С формальной точки зрения многие проблемы оптимального управления могут быть сведены к задачам линейного или нелинейного программирования большой размерности, так как каждой точке пространства состояний соответствует свой вектор неизвестных переменных. Все же, как правило, движение в данном направлении без учета специфики соответствующих задач не приводит к рациональным и эффективным алгоритмам их решения. Поэтому методы решения задач оптимального управления традиционно связаны с другим математическим аппаратом, берущим свое начало от вариационного исчисления и теории интегральных уравнений. Следует также заметить, что опять-таки в силу исторических причин теория оптимального управления была ориентирована на физические и технические приложения, и ее применение для решения экономических задач носит в определенном смысле вторичный характер. В то же время в целом ряде случаев модели исследования, применяющие аппарат теории оптимального управления, могут привести к содержательным и интересным результатам.
  К сказанному выше необходимо добавить замечание о тесной связи, существующей между методами, применяемыми для решения задач оптимального управления, и динамическим программированием. В одних случаях они могут использоваться на альтернативной основе, а в других довольно удачно дополнять друг друга.
  Существуют различные подходы к классификации задач оптимального управления. Прежде всего, их можно классифицировать в зависимости от объекта управления:
  > задачи управления с сосредоточенными параметрами;
  > задачи управления объектами с распределенными параметрами.
  Примером первых является управление самолетом как единым целым, а вторых - управление непрерывным технологическим процессом.
  В зависимости от типа исходов, к которым приводят применяемые управления, выделяют детерминированные и стохастические задачи. В последнем случае результатом управления является множество исходов, описываемых вероятностями их наступления.
  По характеру изменения управляемой системы во времени различают задачи:
 
  > с дискретно изменяющимся временем;
  > с непрерывно изменяющимся временем.
 
  Аналогично классифицируются задачи управления объектами с дискретным или непрерывным множеством возможных состояний. Задачи управления системами, в которых время и состояния меняются дискретно, получили название задач управления конечными автоматами. Наконец, при определенных условиях могут ставиться задачи управления смешанными системами.
  Многие модели управляемых систем основаны на аппарате дифференциальных уравнений, как в обыкновенных, так и в частных производных. При исследовании систем с распределенными параметрами, в зависимости от вида используемых дифференциальных уравнений в частных производных, выделяют такие типы задач оптимального управления, как параболические, эллиптические или гиперболические.
  Рассмотрим два простейших примера задач управления экономическими объектами.
  Задача распределения ресурсов. Имеется т складов с номерами i (i?1:m), предназначенных для хранения однородного продукта. В дискретные моменты времени t?0:(T-1) происходит его распределение между объектами-потребителями (клиентами) с номерами j, j ? 1:п. Пополнение запаса в пунктах хранения продукта в t-й момент времени определяется величинами , I ? 1:m, а потребности клиентов в нем равняются , j ? 1: п. Обозначим через - затраты на доставку единицы продукта из i-го склада j-му потребителю в момент времени t. Также предполагается, что продукт, поступивший на склад в момент t, может быть использован, начиная со следующего момента (t+1). Для сформулированной модели ставится задача найти такой план распределения ресурсов , который минимизирует суммарные расходы на доставку потребителям продукции со складов в течение полного периода функционирования системы.
  Обозначив через количество продукта, поставляемое j-му клиенту с i-ro склада в t-й момент времени, а через - общее количество продукта на i-м складе, описанную выше проблему можно представить как задачу нахождения таких совокупностей переменных
 
  и
 
 которые обращают в минимум функцию
 
  (6.20)
 
 при условиях
 
  (6.21)
 
  (6.22)
 
  (6.23)
 
 где объемы начальных запасов продукта на складах предполагаются заданными.
  Задачу (6.20)-(6.23) называют динамической транспортной задачей линейного программирования. С точки зрения приведенный выше терминологии независимые переменные представляют собой параметры управления системой, а зависящие от них переменные - совокупность параметров состояния системы в каждый момент времени t. Ограничения гарантируют, что в любой момент времени с любого склада не может быть вывезен объем продукта, превышающий его фактическое количество, а ограничения (6.21) задают правила изменения этого количества при переходе от одного периода к другому. Ограничения данного вида, которые задают условия на значения параметров состояния системы, принято называть фазовыми.
  Отметим также, что условие (6.21) служит простейшим примером фазовых ограничений, поскольку связываются значения параметров состояния для двух смежных периодов t и t + 1. В общем случае может устанавливаться зависимость для группы параметров, принадлежащих нескольким, возможно несмежным, этапам. Такая потребность может возникнуть, например, при учете в моделях фактора запаздывания поставок.
  Простейшая динамическая модель макроэкономики. Представим экономику некоторого региона как совокупность п отраслей (j ? 1: n), валовой продукт которых в денежном выражении на некоторый момент t может быть представлен в виде вектора , где . Обозначим через Аt матрицу прямых затрат, элементы которой отражают затраты продукции i-й отрасли (в денежном выражении) на изготовление единицы продукции j-й отрасли в t-й момент времени. Если - матрица, задающая удельные нормы продукции i-й отрасли, идущей на расширение производства в j-й отрасли, а - вектор объемов продукции отраслей потребления, идущей на потребление, то условие расширенного воспроизводства можно записать как
 
  (6.24)
 
 где - исходный запас продукции отраслей предполагается заданным и
 
  (6.25)
 
  В рассматриваемой модели величины являются параметрами состояния системы, а Xt - управляющими параметрами. На ее базе могут быть поставлены различные задачи, типичным представителем которых является задача оптимального вывода экономики на момент Т к некоторому заданному состоянию . Данная задача сводится к отысканию последовательности управляющих параметров

<< Пред.           стр. 12 (из 13)           След. >>

Список литературы по разделу