Математические методы исследования операций в экономике (стр. 33 из 37)
или, что то же самое,
В силу сделанных предположений все функции затрат fk (xk ,yk+1) являются вогнутыми (как суммы вогнутой и линейной функций). Данное свойство значительно упрощает процесс решения, так как для поиска минимума вогнутых функций fk (xk ,yk+1) достаточно рассмотреть только две крайние точки множества, на котором отыскивается минимум. С учетом введенного обозначения задачу (5.24)-(5.25) можно записать в виде:
при условиях
Рассмотрим процедуру решения (5.32)-(5.33). Так как ищется минимум суммы вогнутых функций fk(xk ,yk+1), то решение будет достигаться на одной из крайних точек множества, определяемого условиями (5.33). Общее число переменных xk и yk в системе (5.33) равно 2п. Однако, учитывая то, что в ней только п уравнений, в оптимальном плане будет не более п ненулевых компонент, причем для каждого периода k значения xk и yk не могут равняться нулю одновременно (в силу необходимостиудовлетворения спроса либо за счет заказа, либо за счет запаса). Формально это утверждение можно представить в виде условия дополняющей нежесткости:
где
С точки зрения содержательной интерпретации условия (5.34)-(5.35) означают, что при оптимальном управлении заказ поставщику на новую партию не должен поступать, если в начале периода имеется ненулевой запас, или размер заказа должен равняться величине спроса за целое число периодов. Отсюда следует, что запас на конец последнего периода должен равняться нулю: у*n+1=0. Последнее позволяет решать задачу в прямом направлении, применяя рекуррентное соотношение
где ξ = уk+1=хk+уk - dk .
Учитывая (5.34)-(5.35) и вогнутость fk(xk, ξ), заключаем, что минимум (5.36) достигается в одной из крайних точек xk =0 или xk = ξ + dk поэтому
тогда для предыдущего периода функция состояния может быть выражена как
на oснове чего в общем виде получаем модифицированную форму для рекуррентного соотношения
При дальнейших конкретизирующих предположениях о виде функций 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.1.1. Предмет теории игры. Задачи, рассмотренные в предыдущих главах, формулировались для ситуаций индивидуального выбора оптимальных решений, т.е. для случаев, когда решение принимает отдельно взятый субъект, обладающий единственнойцелью.
Принципиально иная ситуация возникает при изучении процессов принятия решений несколькими субъектами, интересы которых могут не совпадать. При этом возникают задачисо многими целевыми функциями (критериями). Область математики, изучающая данные проблемы, получила название теории игр. Задачи теории игр относятся к области принятия решений в условиях неопределенности, а их специфика состоит в том, что, как правило, подразумевается неопределенность, возникающая в результате действий двух или более «разумных» противников, способных оптимизировать свое поведение за счет других. Среди типичных примеров такого поведения могут быть названы действия конкурирующих фирм на одном рынке или планирование военных операций.
Одним из основных вопросов в задачах с коллективным выбором решений является вопрос об определении оптимальности, т. е. вопрос, какие решения следует признавать наилучшими в ситуации оптимизации по нескольким критериям, отражающим различные интересы. Многие методы решения проблем теории игр основываются на сведении их к задачам математического программирования. На наиболее простых из них мы остановимся в настоящей главе.
Теория игр берет начало от работ Э. Бореля (1921 г.), а принципиальным этапом в ее становлении как самостоятельного научного направления стала монография Дж. Неймана, вышедшая в 1944 г. [25].
6.1.2. Терминология и классификация игр. Особенностью теории игр как научной дисциплины стала употребляемая в ней специфическая терминология. Термин «игра» применяется для обозначения совокупности правил и соглашений, которыми руководствуются субъекты, поведение которых мы изучаем. Каждый такой субъект k, гдеk∊l:K, или игрок, характеризуется наличием индивидуальной системы целевых установок и стратегийs1k,s2k, ..., smkk, т. е. возможных вариантов действий в игре.
Достаточно распространенный способ математического описания игры основан на задании функцийfk(s1i1 ,s2i2 , ..., skik , ..., sKik), каждая из которых определяет результат (платеж, выигрыш), получаемый k-м игроком в зависимости от набора стратегийS =(s1i1 ,s2i2 , ..., skik , ..., sKik), примененного всеми участниками игры. Функцииfk, k∊l:Kтакже называют функциямивыигрыша, или платежными функциями. В том случае, если для любыхS
игра называется игрой с нулевой суммой. Игру с двумя участниками и нулевой суммой называют антагонистической. Антагонистические игры, т. е. игры, в которых выигрыш одного участника равен проигрышу другого, в силу относительно простой постановки задачи являются наиболее изученным разделом теории игр. Однако содержание теории игр, безусловно, не исчерпывается ими. В классификации игровых моделей выделяют игры с конечными и бесконечными наборами стратегий у игроков, выделяют игры по возможным количествам ходов у участников. Также игры делят на некооперативные и кооперативные, т. е. те, в которых функции выигрыша участников зависят от образуемых ими коалиций. Помимо этого игры можно различать по объему информации, имеющейся у игроков относительно прошлых ходов. В этой связи они делятся на игры с полной и неполной информацией. Заинтересованный читатель может обратиться к таким источникам, как [17, 23].