Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Линейное программирование (Л.П.) – это наука о методах исследования и отыскания экстремальных (наибольших и наименьших) значений линейной функции, на неизвестные которой наложены линейные ограничения.
Пусть дана система с m неравенств с n неизвестными:
(1)
x1,2…n должно быть всегда ≥ 0 (по смыслу экономических задач)
Z = c1x1 + c2x2 + … + cnxn → max (min)
Систему линейных неравенств (1) называют системой ограничений, а функцию Z – целевой
функцией (или линейной функцией, линейной формой, функцией цели).
Оптимальным решением, или оптимальным планом задачи Л. П. называется решение: X = (x1, x2, …, xn) системы ограничений, при котором линейная функция Z принимает оптимальное значение.
Если система ограничений состоит из одних неравенств, то задача называется стандартной.
Если же из уравнений, то задача называется канонической.
Если из уравнений и неравенств, то неканонической (или общей).
Чтобы перейти от стандартной формы к каноническому виду вводят дополнительные неотрицательные переменные со знаком «+», если знак неравенства «≤» и со знаком «–», если знак неравенства «≥», т.е. неравенство:
можно заменить выражением
Решение экономической задачи можно разбить на два этапа:
1) Построение экономико-математической модели;
2) Нахождение оптимального решения;
Чтобы составить математическую модель задачи Л. П. необходимо:
I) Ввести обозначения переменных.
II) Исходя из цели экономических исследований, составить целевую функцию.
III) Учитывая ограничения в использовании экономических показателей задачи и их количественные ограничения, написать систему ограничений.
Рассмотрим задачу Л. П. в стандартной форме с двумя переменными:
Для нахождения экстремального значения целевой функции при геометрическом методе решения используется ( на плоскости X1O X2 ) вектор который обозначается
Этот вектор показывает направление наискорейшего изменения целевой функции.
Координатами вектора являются коэффициенты при переменных целевой функции Z,
т.е. (c1;c2)
Алгоритм решения задачи:
1) Находим область допустимых решений системы ограничений задачи;
2) Строим радиус-вектор . (c1;c2)
3) Проводим прямую , которая перпендикулярна , и мысленно перемещаем ее в направлении вектора .
Тогда первая точка встречи прямой с областью будет точка минимума целевой функции, а последняя точка - точка максимума.
При построении может получится многоугольник который не ограничен снизу, тогда задача на min решений не имеет, если же будет не ограничен сверху, то задача не имеет решения на max.
Замечания : Если окажется, что прямая при перемещении параллельна одной из сторон многоугольника, то в таком случае экстремум достигается во всех точках соответствующей стороны, а задача будет иметь бесчисленное множество решений, в таком случае говорят, что задача имеет альтернативный оптимум.
Метод является универсальным, т. к. позволяет решить практически любую задачу Л.П., записанную в каноническом виде.
Идея симплексного метода (метода последовательного улучшения плана) заключается в том, что, начиная с некоторого исходного опорного решения, осуществляется последовательно направленное перемещение по опорным решениям задачи к оптимальному.
Этот метод был предложен американским учёным Данцингом и опубликован в 1951 г., хотя идеи этого метода разработал Канторович ещё в 1939 г.
В настоящее время название “симплекс” используется независимо от формы линейных ограничений.
Схема решения задачи симплексным методом:
1) указывается способ вычисления первоначального допустимого решения задачи.
2) при помощи признака оптимальности проверяется не является ли это решение оптимальным.
3) по выбранному начальному решению строятся другие решения, более близкие к оптимальному.
Доказано, что таким путём через конечное число шагов (итераций) можно получить оптимальное решение задачи. В ходе решения задачи симплекс-методом можно установить является ли задача разрешимой.
Если система ограничений задана в стандартной форме, то её переводят в каноническую путём добавления новых переменных.
Пусть дана совместная система уравнений:
++++=
++++=
++++=
Z=++++min
Пусть ранг этой системы равен 3, значит базисных переменных 3. Разрешим систему относительно x1 , x2 , x3 , а x4 , x5 – свободные.
=+)
=+)
=+)
Z=+)
Причём, чтобы начальное решение было допустимым, необходимо чтобы в1 > 0, в2 > 0, в3 > 0.
Рассмотрим элементы последней строки (функция Z) и среди γ4 и γ5 (γ0 не рассматривать) найдём наименьшее положительное.
Пусть это γ4, это означает, что x4 входит в Z со знаком «–», поэтому для уменьшения Z нужно увеличивать x4, но увеличивать x4 можно до тех пор, пока все базисные переменные будут неотрицательными.
Столбец содержащий x4 называется разрешающим.
Если в последней строке нет положительных элементов, то все свободные переменные входят в функцию Z с положительными коэффициентами и Zmin достигается при равенстве 0 всех свободных переменных.
Определение. Элемент стоящий на пересечении разрешающего столбца и разрешающей строки называется разрешающим.
a24 – разрешающий элемент, значит x4 нужно перевести в базисные, а x2 в свободные переменные.
Замечание: если в разрешающем столбце нет положительных коэффициентов, то функция Z минимума не достигнет, т.е. Z не ограничена снизу.
Алгоритм перехода к симплекс-таблице № 2:
1) Неизвестные x2 и x4 меняют местами.
2) Разрешающий элемент a24 заменяют обратной величиной.
3) Остальные элементы разрешающей строки делим на разрешающий элемент.
4) Элементы разрешающего столбца, кроме разрешающего элемента, делят на разрешающий элемент и меняют знаки.
5) Все остальные элементы симплекс–таблицы № 2 получают по правилу прямоугольника:
Из произведения элементов диагонали, содержащей искомый элемент, вычитают произведение элементов противоположной диагонали и делят всё на элемент, противоположный искомому.
Рассмотрим выражение для функции Z.
По условию в1, в2, в3 > 0.
Разрешающий элемент больше 0 (по выбору); γ4 > 0 (по выбору), значит
Следовательно функция Z уменьшилась. Значит, если в последней строке все элементы не положительны, т.е. ≤ 0 , то базисное решение оптимальное и задача решена.
В противоположном случае переходим к симплекс–таблице № 3.
При решении задачи на max:
1) Разрешающий столбец выбирают также, рассматривая строку Z (кроме γ0) и среди γ4 и γ5 находят отрицательный элемент больший по модулю, этому элементу и соответствует разрешающий столбец.
2) Разрешающую строку выбирают по минимуму отношений свободных членов к положительным элементам разрешающего столбца.
3) На их пересечении оказывается разрешающий элемент.
4) Алгоритм перехода к симплекс-таблице №2 тот же, что и для задачи на min.
5) Критерий оптимальности на max: если в последней строке Z нет отрицательных коэффициентов.
Если в задачи Л.П. сразу не получилось допустимое решение (т.е. ≤ 0 или если ограничения системы неравенств ≥ 0), то применяют метод искусственного базиса, т.е. составляется так называемая расширенная задача, которая решается симплексным методом.
На основе результатов решения расширенной задачи либо находится оптимальное решение, либо устанавливается причина его отсутствия.
Алгоритм решения задачи методом искусственного базиса:
1) В каждое уравнение дающее отрицательную компоненту в базисном решении вводят искусственные переменные y1, y2, …, ym прибавляя их к левым частям уравнений.
2) Эти искусственные переменные следует ввести и в целевую функцию Z. В задаче на max с коэффициентом (–M), а в задаче на min с коэффициентом (+M):
M(y1, y2, …, ym), где M – очень большое число.
4) Эти искусственные переменные выводят из базиса делая их свободными и потом назад в базис не возвращают, поэтому эти столбцы в новой симплекс-таблице зачёркивают и не рассчитывают.
5) Чтобы определить разрешающий столбец, находят в строке функции M (m + 2-я строка) наибольший положительные элемент, ему соответствует разрешающий столбец. Разрешающую строку ищут как обычно с помощью минимума отношений и переходят к новой симплекс-таблице по обычному алгоритму.
6) После переноса всех искусственных переменных y1, y2, …, ym в свободные, получают допустимое базисное решение.
Строка M должна получится из нулей и её отбрасывают.
7) И т.к. теперь есть допустимое решение далее задачу можно решать и на max и на min.
8) Все остальные элементы симплекс-таблицы вычисляются по правилу прямоугольника.
Каждой задаче линейного программирования соответствует другая задача, называемая двойственной задачей или сопряженной по отношению к исходной. Теория двойственности оказалась полезной для проведения качественных исследований. Рассмотрим задачу об использовании ресурсов.
Свойства двойственных задач:
1) В одной задаче ищется max Z, во второй min F.
2) Коэффициенты при переменных Z одной задачи являются свободными членами системы ограничений другой задачи.
3) Каждая из задач задана в стандартной форме.
4) Матрицы коэффициентов при переменных в системе ограничений являются транспонированными друг к другу.
5) Число неравенств одной задачи совпадают с числом переменных другой.
6) Условие неотрицательности переменных в обеих задачах
1) Привести все неравенства системы ограничений исходной задачи к одному смыслу. Если на max, то к виду «≤». Если на min, то к виду «≥». Для этого, неравенства у которых данные требования не выполняются, умножают на (–1).
2) Составить расширенную матрицу исходной задачи. В неё входят коэффициенты при переменных, столбец свободных членов системы ограничений, строка коэффициентов при переменных в Z.
3) Составить транспонированную матрицу.
4) Сформировать двойственную задачу на основании составленной транспонированной матрицы и условии не отрицательности переменных.
5) Составляем по числам транспонированной матрицы систему неравенств с новыми переменными для двойственной задачи.
6) Мы имеем теперь две системы неравенств в стандартной форме. Перейдём к канонической форме задания систем ограничений.
Транспортная задача (Т.З.) одна из распространённых задач Л.П.
Её цель – разработка наиболее рациональных путей и способов транспортировки товаров, устранение чрезмерно дальних, встречных и повторных перевозок.
Всё это сокращает время продвижения товаров, уменьшает затраты предприятий связанные с осуществлением процессов снабжения сырьём, материалами, топливом, оборудованием и т.д. Под термином Т.З. понимается широкий круг задач не только транспортного характера.
Наиболее часто встречаются следующие задачи относящиеся к транспортным:
– прикрепление потребителей ресурса к производителям;
– привязка пунктов отправления к пунктам назначения;
– взаимная привязка грузопотоков прямого и обратного направлений;
– отдельные задачи оптимальной загрузки промышленности оборудования;
– оптимальное распределение объёмов выпуска промышленной продукции между заводами-изготовителями.
В общем виде задачу можно представить следующим образом: в m пунктах производства A1, A2, …, Am имеется однородный груз в кол-ве соответственно a1, a2, …, am. Этот груз необходимо доставить в n пунктов назначения B1, B2, …, Bn в кол-ве соответственно в1, в2, …, вn. Стоимость перевозки единицы груза (тариф) из пункта Ai в пункт Bj равна Cij.
Требуется составить план перевозок, позволяющий вывести все грузы и имеющий минимальную стоимость.
В зависимости от соотношения между суммарными запасами груза и суммарными потребностями в нём. Т.З. могут быть закрытыми и открытыми:
1) Если , то задача называется закрытой.
2) Если это равенство не верно, то задача называется открытой.
Поэтому если в исходных условиях дана открытая задача то её необходимо привести к закрытой форме:
а) Если потребности по пунктам назначения превышают запасы пунктов отправления, то вводится фиктивный поставщик с недостающим объёмом отправления.
в) Если запасы поставщиков превышают потребности потребителей, то вводится фиктивный потребитель с необходимым объёмом потребления. Тарифы, связывающие фиктивные пункты с реальными имеют нулевые оценки.
Т.З. присущи следующие особенности:
а) распределению подлежат однородные ресурсы;
в) условия задачи описываются только уравнениями;
с) все переменные выражаются в одинаковых единицах измерения;
d) во всех уравнениях коэффициенты при неизвестных равны единице;
е) каждая неизвестная встречается только в 2-х уравнениях системы ограничений.
Т.З. как задача Л.П. может быть решена симплексным методом, однако наличие большого числа переменных и ограничений делает вычисления громоздкими.
Поэтому для решения Т.З. разработан специальный метод имеющий те же этапы, что и симплексный метод, а именно:
1) Нахождение исходного опорного решения;
2) Проверка этого решения на оптимальность;
3) Переход от одного опорного решения к другому.
Рассмотрим закрытую Т.З. Данные запишем в распределительную таблицу, которую будем использовать для нахождения решения.
xij – количество груза, которое необходимо перевести из пункта Ai в пункт Bj.
cij – тарифы транспортных расходов.
Если m – число пунктов отправления, а n – число пунктов назначения, то уравнений составлено m + n, а переменных – m * n.
Можно также показать, что если одно из уравнений системы лишнее (оно является следствием остальных), то его можно исключить из системы.
Таким образом в общем случае система Т.З. должна иметь m + n – 1 уравнений с m * n – переменными.
Определение. План перевозок обращающий в min суммарные транспортные издержки называется оптимальным разрешением Т.З.
Метод северо-западного угла.
Определение. Алгоритм в соответствии с которым элементы плана xij определяют, начиная с левого верхнего угла таблицы, называется методом северо-западного (С–З) угла (тарифы не учитываются).
Определение. Не нулевые перевозки xij принято называть базисными, а нулевые – свободными.
Начальный план перевозок составленный по методу С–З угла является допустимым.
Определение. План перевозок в которых число базисных переменных равно n + m – 1 называется невырожденным. Если меньше этого числа, то план вырожденный и значит, необходимо ввести перевозку с нулевым тарифом.
Метод минимального элемента.
Для составления первоначального плана перевозок:
1) В плане заполняется клетка, которая соответствует минимальному тарифу.
2) Затем заполняется клетка с минимальным тарифом среди оставшихся и т.д.
3) Если на некотором шаге возникает ситуация, когда несколько минимальных элементов одинаковы, то рассматривается тот где больше груза можно перевезти.
4) В общем случае нельзя сказать какой план перевозок ближе к оптимальному, но чаще оказывается ближе метод минимального элемента.
Метод потенциалов решения Т.З.
Как уже отмечалось ранее математическая модель Т.З. имеет ряд особенностей:
1) все ограничения представлены уравнениями.
2) коэффициенты при неизвестных в ограничениях равны либо 0, либо 1.
Поэтому данные особенности позволили преобразовать симплекс-метод в метод потенциалов и тем самым существенно упростить решение Т.З.
Таким образом найденное исходное опорное решение (методом min элемента либо методом С–З угла) проверяется на оптимальность методом потенциалов по следующему критерию: если опорное решение Т.З. является оптимальным, то ему соответствует система m + n действительных чисел Ui и Vj , удовлетворяющих условиям:
1) Ui + Vj = Cij – для всех заполненных клеток xij.
2) Ui + Vj ≤ Cij – для свободных клеток.
Числа Ui и Vj называются потенциалами. В распределительную таблицу добавляют строку Vj и столбец Ui .
Выбираем из двух опорных решений, то которое имеет минимальные затраты, т.е. метод min элемента и проверяем его на оптимальность, добавив в распределительную таблицу строку Vj и столбец Ui
Классификацию игр можно проводить по: количеству игроков, количеству стратегий, характеру взаимодействия игроков, характеру выигрыша, количеству ходов, состоянию информации и т.д.
В зависимости от количества игроков различают игры двух и п игроков. Первые из них наиболее изучены. Игры трёх и более игроков менее исследованы из-за возникающих принципиальных трудностей. Чем больше игроков - тем больше проблем.
По количеству стратегий игры делятся на конечные и бесконечные. Если в игре все игроки имеют конечное число возможных стратегий, то она называется конечной. Если же хотя бы один из игроков имеет бесконечное количество возможных стратегий игра называется бесконечной.
По характеру взаимодействия игры делятся на:
1) бескоалиционные – игроки не имеют права вступать в соглашения, образовывать коалиции;
2) коалиционные (кооперативные) – игроки могут вступать в коалиции. (в кооперативных играх коалиции наперёд определены)
По характеру выигрышей игры делятся на:
•игры с нулевой суммой (общий капитал всех игроков не меняется, а перераспределяется между игроками; сумма выигрышей всех игроков равна нулю);
•игры с ненулевой суммой.
По виду функций выигрыша игры делятся на:
•матричные,
•биматричные,
•непрерывные,
•выпуклые,
•сепарабельные,
•типа дуэлей
•и др.
Матричная игра - это конечная игра двух игроков с нулевой суммой, в которой задаётся выигрыш игрока 1 в виде матрицы (строка матрицы соответствует номеру применяемой стратегии игрока 1, столбец - номеру применяемой стратегии игрока 2; на пересечении строки и столбца матрицы находится выигрыш игрока 1, соответствующий применяемым стратегиям).
Для матричных игр доказано, что любая из них имеет решение и оно может быть легко найдено путём сведения игры к задаче линейного программирования.
Биматричная игра - это конечная игра двух игроков с ненулевой суммой, в которой выигрыши каждого игрока задаются матрицами отдельно для соответствующего игрока (в каждой матрице строка соответствует стратегии игрока 1, столбец - стратегии игрока 2, на пересечении строки и столбца в первой матрице находится выигрыш игрока 1, во второй матрице - выигрыш игрока 2.)
Для биматричных игр также разработана теория оптимального поведения игроков, однако решать такие игры сложнее, чем обычные матричные.
Непрерывной считается игра, в которой функция выигрышей каждого игрока является непрерывной в зависимости от стратегий. Доказано, что игры этого класса имеют решения, однако не разработано практически приемлемых методов их нахождения.
Стратегией игрока называется совокупность правил, определяющих выбор варианта действий при каждом личном ходе этого игрока в зависимости от ситуации, сложившейся в процессе игры.
Оптимальной стратегией игрока называется такая стратегия, которая при многократном повторении игры, обеспечивает игроку максимально возможный средний выигрыш (минимально возможный средний проигрыш). Очевидно, выбирая ту или иную стратегию, каждый из игроков стремится удовлетворить свои интересы: первый – обеспечить себе максимально возможный выигрыш, а второй – минимально возможный проигрыш.
Стратегия первого игрока называется оптимальной, если при её применении выигрыш первого игрока не может быть уменьшен, какими бы стратегиями ни пользовался второй игрок. Стратегия второго игрока является оптимальной в том случае, если проигрыш второго игрока не может быть увеличен, какими бы стратегиями ни пользовался первый игрок.
Основными вопросами теории игр, которые возникают в коммерческой деятельности, являются:
•В чем состоит оптимальность поведения каждого из игроков в игре, какие свойства стратегий следует считать признаками оптимальности;
•Существуют ли стратегии игроков, которые обладали бы атрибутами оптимальности;
•Если существуют оптимальные стратегии, то как их найти?
Матричная игра двух игроков с нулевой суммой может рассматриваться как следующая абстрактная игра двух игроков.
Первый игрок имеет m стратегий i = 1, 2, ..., m; второй имеет n стратегий j = 1, 2, ..., n. Каждой паре стратегий (i, j) поставлено в соответствие число aij , выражающее выигрыш игрока 1 за счёт игрока 2, если первый игрок примет свою i-ю стратегию, а 2 – свою j-ю стратегию.
Каждый из игроков делает один ход: игрок 1 выбирает свою i-ю стратегию ( i = ), игрок 2 – свою j-ю стратегию ( j = ), после чего игрок 1 получает выигрыш aij за счёт игрока 2 (если aij < 0, то это значит, что игрок 1 платит второму сумму |aij|).
На этом игра заканчивается.
Подобный подход к решению задачи называют принципом гарантированного результата. Выбранную с его использованием стратегию называют максиминной, а полученный в результате её применения выигрыш называют максиминным, или нижней ценой игры, т.е. находится:
Определение. Число , определённое по формуле (1) называется нижней чистой ценой игры и показывает, какой минимальный выигрыш может гарантировать себе игрок 1, применяя свои чистые стратегии при всевозможных действиях игрока 2.
Аналогичные рассуждения можно провести для игрока 2, который при оптимальном своём поведении должен стремится по возможности за счёт своих стратегий максимально уменьшить выигрыш игрока 1. Поэтому для игрока 2 отыскивается
Определение. Число , определяемое по формуле (2), называется чистой верхней ценой игры и показывает, какой максимальный выигрыш за счёт своих стратегий может себе гарантировать игрок 1.
Вывод: применяя свои чистые стратегии, игрок 1 может обеспечить себе выигрыш не меньше , а игрок 2 за счёт применения своих чистых стратегий может не допустить выигрыш игрока 1 больше, чем .
Максиминные стратегии игроков становятся устойчивыми, пока оба игрока их придерживаются и выигрыш одного из них равен проигрышу другого (т.е. нет места риску). Такая игра с матрицей A имеет седловую точку в чистых стратегиях и чистую цену игры: = =
Седловая точка - это пара чистых стратегий (i0 , j0 ) соответственно игроков 1 и 2, при которых достигается равенство = .
В это понятие вложен следующий смысл: если один из игроков придерживается стратегии, соответствующей седловой точке, то другой игрок не сможет поступить лучше, чем придерживаться стратегии, соответствующей седловой точке.
Исследование в матричных играх начинается с нахождения её седловой точки в чистых стратегиях. Если матричная игра имеет седловую точку в чистых стратегиях, то нахождением этой седловой точки заканчивается исследование игры.
Если же в игре нет седловой точки в чистых стратегиях, то можно найти нижнюю и верхнюю чистые цены этой игры, которые указывают, что игрок 1 не должен надеяться на выигрыш больший, чем верхняя цена игры, и может быть уверен в получении выигрыша не меньше нижней цены игры.
Улучшение решений матричных игр следует искать в использовании секретности применения чистых стратегий и возможности многократного повторения игр в виде партии. Этот результат достигается путём применения чистых стратегий случайно, с определённой вероятностью.
Определение. Смешанной стратегией игрока называется полный набор вероятностей применения его чистых стратегий. Таким образом, если игрок 1 имеет m чистых стратегий 1, 2, ..., m, то его смешанная стратегия х - это набор чисел х = (x1, ..., xm) удовлетворяющих соотношениям: xi >= 0 (i = ), = 1.
Аналогично для игрока 2, который имеет n чистых стратегий, смешанная стратегия у – это набор чисел y = ( y1, …, yn ) удовлетворяющих соотношениям: yj >= 0, (j = 1,n), = 1.
Так как каждый раз применение игроком одной чистой стратегии исключает применение другой, то чистые стратегии являются несовместными событиями. Кроме того, они являются единственными возможными событиями.
Чистая стратегия есть частный случай смешанной стратегии. Действительно, если в смешанной стратегии какая-либо i-я чистая стратегия применяется с вероятностью 1, то все остальные чистые стратегии не применяются. И эта i-я чистая стратегия является частным случаем смешанной стратегии. Для соблюдения секретности каждый игрок применяет свои стратегии независимо от выбора другого игрока.
Определение. Средний выигрыш игрока 1 в матричной игре с матрицей А выражается в виде математического ожидания его выигрышей
E (A, x, y) ==
Первый игрок имеет целью за счёт изменения своих смешанных стратегий х максимально увеличить свой средний выигрыш Е(А, х, у), а второй - за счёт своих смешанных стратегий стремится сделать Е(А, х, у) минимальным, т.е. для решения игры необходимо найти такие х и у, при которых достигается верхняя цена игры Е (А, х, y).
Аналогичной должна быть ситуация и для игрока 2, т.е. нижняя цена игры должна быть Е (А, х, y).
Подобно играм, имеющим седловые точки в чистых стратегиях, вводится следующее определение: оптимальными смешанными стратегиями игроков 1 и 2 называются такие наборы , соответственно, которые удовлетворяют равенству
Е (А, х, y) = Е (А, , ).
Величина Е(А, , ) называется при этом ценой игры и обозначается через .
Имеется и другое определение оптимальных смешанных стратегий: , называются оптимальными смешанными стратегиями соответственно игроков 1 и 2, если они образуют седловую точку: Е (А, х, )<= Е (А, , )<= Е (А, , у)
Оптимальные смешанные стратегии и цена игры называются решением матричной игры.
Основная теорема матричных игр
Теорема (о минимаксе). Для матричной игры с любой матрицей А величины
Е (А, х, y) и Е (А, х, y)
Обозначим через G(X, Y, A) игру двух лиц с нулевой суммой, в которой игрок 1 выбирает стратегию х X, игрок 2 - у Y, после чего игрок 1 получает выигрыш А = А(х, у) за счёт игрока 2.
Определение. Стратегия игрока 1 доминирует (строго доминирует) над стратегией , если A(, y) ≥ A(, y) y Y
Определение. Стратегия игрока 2 доминирует (строго доминирует) над стратегией , если A(x, ) ≥ A(x, ) x X
При этом стратегии и называются доминируемыми (строго доминируемыми).
Спектром смешанной стратегии игрока в конечной антагонистической игре называется множество всех его чистых стратегий, вероятность которых согласно этой стратегии положительна.
Свойство 1. Если чистая стратегия одного из игроков содержится в спектре некоторой его оптимальной стратегии, то выигрыш этого игрока в ситуации, образованной данной чистой стратегией и любой оптимальной стратегией другого игрока, равен значению конечной антагонистической игры.
Свойство 2. Ни одна строго доминируемая чистая стратегия игрока не содержится в спектре его оптимальной стратегии.
Игра G' = ( X', Y', А' ) называется подыгрой игры G(X, Y, A), если X' X, Y' Y, а матрица А' является подматрицей матрицы А. Матрица А' при этом строится следующим образом. В матрице А остаются строки и столбцы, соответствующие стратегиям X' и Y', а остальные "вычеркиваются". Всё то что "останется" после этого в матрице А и будет матрицей А'.
Свойство 3. Пусть G = (X, Y, A) – конечная антагонистическая игра, G' = (X \ x', Y, A) – подыгра игры G, а х' - чистая стратегия игрока 1 в игре G, доминируемая некоторой стратегией , спектр которой не содержит х', тогда всякое решение (, ,) игры G' является решением игры G.
Свойство 4. Пусть G = (X, Y, A) – конечная антагонистическая игра, G' = (X, Y \ у', А) - подыгра игры G, а, у' – чистая стратегия игрока 2 в игре G, доминируемая некоторой стратегией , спектр которой не содержит у', тогда всякое решение игры G' является решением G.
Свойство 5. Если для чистой стратегии х' игрока 1 выполнены условия свойства 3, а для чистой стратегии у' игрока 2 выполнены условия свойства 4, то всякое решение игры G' = (X \ x', Y \ у', А) является решением игры G = (X, Y, A).
Свойство 6. Тройка (, ,) является решением игры G = (X, Y, A) тогда и только тогда, когда (, , k + a) является решением игры С(Х, Y, к * А + а), где а - любое вещественное число, k > 0.
Свойство 7. Для того, чтобы = ( , ..., , ..., ) была оптимальной смешанной стратегией матричной игры с матрицей А и ценой игры , необходимо и достаточно выполнение следующих неравенств:
(j = )
Аналогично для игрока 2:
чтобы = ( , ..., , ..., ) была оптимальной смешанной стратегией игрока 2 необходимо и достаточно выполнение следующих неравенств:
(i = )
Из последнего свойства вытекает: чтобы установить, являются ли предполагаемые (х, у) решением матричной игры, достаточно проверить, удовлетворяют ли они предыдущим. С другой стороны, найдя неотрицательные решения этих неравенств совместно со следующими уравнениями , (1 )
получим решение матричной игры.
Таким образом, решение матричной игры сводится к нахождению неотрицательных параметров решений линейных неравенств (*) (**) и линейных уравнений (1 ). Однако это требует большого объёма вычислений, которое растёт с увеличением числа чистых стратегий игроков.
Поэтому в первую очередь следует, по возможности используя свойства 2 и 3, уменьшить число чистых стратегий игроков. Затем следует во всех случаях проверить выполнение неравенства:
= .
Если оно выполняется, то игроки имеют чистые оптимальные стратегии (игрок 1 - чистую максиминная, а игрок 2 - чистую минимаксная). В противном случае хотя бы у одного игрока оптимальные стратегии будут смешанные. Для матричных игр небольшого размера эти решения можно найти, применяя свойства 1-5.
Замечание. Отметим, что исключение доминируемых (не строго) стратегий может привести к потере некоторых решений. Если же исключаются только строго доминируемые стратегии, то множество решений игры не изменится.
Прежде всего необходимо проверить, есть ли у данной игры седловая точка. Если да, то игра имеет решение в чистых стратегиях, причём оптимальными стратегиями игроков 1 и 2 соответственно будут чистая максиминная и чистая минимаксная стратегии. Если же игра с матрицей выигрышей А не имеет чистых стратегий, то оба игрока имеют только такие оптимальные стратегии, которые используют все свои чистые стратегии с положительными вероятностями. В противном случае один из игроков (например 1) имеет чистую оптимальную стратегию, а другой – только смешанные. Не ограничивая общности, можно считать, что оптимальной стратегией игрока 1 является выбор с вероятностью 1 первой строки. Далее, по свойству 1 следует, что а11 = а12 = u и матрица имеет вид
.
Легко видеть, что для матриц такого вида одна из стратегий игрока 2 является доминируемой. Следовательно, по свойству 4 этот игрок имеет чистую стратегию, что противоречит предположению.
Пусть Х = (, 1 - ) – оптимальная стратегия игрока 1. Так как игрок 2 имеет смешанную оптимальную стратегию, из свойства 1 получим, что (см. также свойство 7)
Отсюда следует, что при u 0 столбцы матрицы А не могут быть пропорциональны с коэффициентом пропорциональности, отличным от единицы.
Если же коэффициент пропорциональности равен единице, то матрица А принимает вид
и игрок 1 имеет чистую оптимальную стратегию (он выбирает с вероятностью 1 ту из строк, элементы которой не меньше соответствующих элементов другой), что противоречит предположению.
Следовательно, если u 0 и игроки имеют только смешанные оптимальные стратегии, то определитель матрицы А отличен от нуля. Из этого следует, что последняя система уравнений имеет единственное решение. Решая её, находим
;
.
Аналогичные рассуждения приводят нас к тому, что оптимальная стратегия игрока 2 Y = (, 1 -) удовлетворяет системе уравнений
откуда
.
Рассмотрим игру, заданную платёжной матрицей.
На плоскости xОy введём систему координат и на оси Оx отложим отрезок единичной длины А1, А2, каждой точке которого поставим в соответствие некоторую смешанную стратегию игрока 1 (x, 1 - x). В частности, точке А1 (0;0) отвечает стратегия А1, точке А2 (1;0) – стратегия А2 и т.д.
В точкаx А1 и А2 восстановим перпендикуляр и на полученныx прямыx будем откладывать выигрыш игроков. На первом перпендикуляре (в данном случае он совпадает с осью 0y) отложим выигрыш игрока 1 при стратегии А1, а на втором – при стратегии А2. Если игрок 1 применит стратегию А1, то выиграет при стратегии В1 игрока 2 – 2, при стратегии В2 – 3, а при стратегии В3 – 11. Числам 2, 3, 11 на оси 0x соответствуют точки В1, В2 и В3.
Если же игрок 1 применит стратегию А2, то его выигрыш при стратегии В1 равен 7, при В2 – 5, а при В3 – 2. Эти числа определяют точки В'1, В2', В3' на перпендикуляре, восстановленном в точке А2.Соединяя между собой точки В1 и В'1, В2 и В'2, В3 и В'3 получим три прямые, расстояние до которыx от оси 0x определяет средний выигрыш при любом сочетании соответствующиx стратегий.
Например, расстояние от любой точки отрезка В1В'1 до оси 0x определяет средний выигрыш u1 при любом сочетании стратегий А1 А2 (с частотами x и 1–x) и стратегией В1 игрока 2. Это расстояние равно
2 + 6(1 - ) =
(Вспомните планиметрию и рассмотрите трапецию А1 B1 B'1 A2). Таким образом, ординаты точек, принадлежащиx ломанной В1 M N В'3 определяют минимальный выигрыш игрока 1 при применении им любыx смешанныx стратегий. Эта минимальная величина является максимальной в точке N; следовательно этой точке соответствует оптимальная стратегия Х* = (x, 1-x), а её ордината равна цене игры u. Координаты точки N наxодим как точку пересечения прямыx В2 B'2 и В3 B'3.
Соответствующие два уравнения имеют вид
.
Следовательно Х = (; ), при цене игры u = . Таким образом мы можем найти оптимальную стратегию при помощи матрицы
Оптимальные стратегии для игрока 2 можно найти из системы
и, следовательно, Y = (0; ; ). (Из рисунка видно, что стратегия B1 не войдёт в оптимальную стратегию.
Предположим, что цена игры положительна (u > 0). Если это не так, то согласно свойству 6 всегда можно подобрать такое число с, прибавление которого ко всем элементам матрицы выигрышей даёт матрицу с положительными элементами, и следовательно, с положительным значением цены игры. При этом оптимальные смешанные стратегии обоих игроков не изменяются.
Итак, пусть дана матричная игра с матрицей А порядка m х n. Согласно свойству 7 оптимальные смешанные стратегии х = (х1, ..., хm), y = (y1, ..., yn) соответственно игроков 1 и 2 и цена игры u должны удовлетворять соотношениям.
Разделим все уравнения и неравенства в (1) и (2) на u (это можно сделать, т.к. по предположению u > 0) и введём обозначения :
, ,
Тогда (1) и (2) перепишется в виде :
, , , ,
, , , .
Поскольку первый игрок стремится найти такие значения хi и, следовательно, pi , чтобы цена игры u была максимальной, то решение первой задачи сводится к нахождению таких неотрицательных значений pi , при которых
,
Поскольку второй игрок стремится найти такие значения yj и, следовательно, qj, чтобы цена игры u была наименьшей, то решение второй задачи сводится к нахождению таких неотрицательных значений qj, , при которых
, .
Формулы (3) и (4) выражают двойственные друг другу задачи линейного программирования (ЛП).
Решив эти задачи, получим значения pi , qj и u.Тогда смешанные стратегии, т.е. xi и yj получаются по формулам :
Динамическое программирование — один из разделов оптимального программирования, в котором процесс принятия решения и управления может быть разбит на отдельные этапы (шаги).
Экономический процесс является управляемым, если можно влиять на ход его развития. Под управлением понимается совокупность решений, принимаемых на каждом этапе для влияния на ход развития процесса.
Совокупность решений, принимаемых в начале года (квартала и т.д.) по обеспечению предприятия сырьем, замене оборудования, финансированию и т.д., является управлением.
Необходимо организовать выпуск продукции так, чтобы принятые решения на отдельных этапах способствовали получению максимально возможного объема продукции или прибыли.
Динамическое программирование позволяет свести одну сложную задачу со многими переменными ко многим задачам с малым числом переменных. Это значительно сокращает объем вычислений и ускоряет процесс принятия управленческого решения.
В отличие от линейного программирования, в котором симплексный метод является универсальным методом решения, в динамическом программировании такого универсального метода не существует.
Одним из основных методов динамического программирования является метод рекуррентных соотношений, который основывается на использовании принципа оптимальности, разработанного американским математиком Р.Беллманом. Принцип оптимальности (1953 г.) – каково бы ни было состояние системы в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило бы к оптимальному выигрышу на всех последующих шагах , включая данный.
Пусть X=(X1 , X2 , …, Xn) – управление, переводящее систему S из состояния в состояние :
1. Показатель эффективности- целевая функция - зависит от начального состояния и управления Z=F( ,X) .
2.Состояние системы в конце k-ого шага зависит только от предшествующего состояния и управления на k–м шаге Xk (не зависит от предшествующих состояний и управлений) =(, Xk) .
3. Целевая функция является аддитивной от показателя эффективности каждого шага
Zk =Σ (, Xk) , k=1, 2, …, n.
Задача пошаговой оптимизации (ДП): определить такое допустимое управление , переводящее систему из состояния в состояние , при котором целевая функция п
ринимает наибольшее (наименьшее) значение.
Использование данного принципа гарантирует, что управление, выбранное на любом шаге, не локально лучше, а лучше с точки зрения процесса в целом. Особенности модели ДП:
1.Задача оптимизации интерпретируется как n-шаговый процесс управления
2.Целевая функция на k-ом шаге зависит только от состояния системы к этому шагу и не влияет на предшествующие шаге (нет обратной связи)
3.Состояние после k-ого шага зависит только от предшествующего состояния и управления Xk (отсутствие последействия)
4.На каждом шаге управление Xk зависит от конечного числа управляющих переменных, а состояние от конечного числа параметров
Рассмотрим n-й шаг: — состояние системы к началу n-го шага, — конечное состояние, Xn — управление на n-м шаге, (, Xk) — целевая функция (выигрыш) n-го шага. Согласно принципу оптимальности, Xn нужно выбирать так, чтобы для любых состояний получить максимум (min) целевой функции на этом шаге. Обозначим через *() максимум целевой функции —показателя эффективности n-го шага при условии, что к началу последнего шага система S была в произвольном состоянии , а на последнем шаге управление было оптимальным.
*() называется условным максимумом целевой функции на n-м шаге. Очевидно, что
*()= max/ Xn (, Xn) (1)
Максимизация ведется по всем допустимым управлениям Xn.
Согласно принципу оптимальности для любых sn-2 решение нужно выбирать так, чтобы оно вместе с оптимальным управлением на последнем n-ом шаге приводило бы к max целевой функции на двух последних шагах
*()= max/ Xn-1 ( (, )+*())
В результате максимизации только по одной переменной Xn вновь получаются две функции *()и *()Далее рассматривается трехшаговая задача: к двум последним шагам присоединяется n-2 и т.д.
На произвольном k-ом шаге:
*()= max/ Xk ( (, )+*()) (2)
k=n-1, n-2, …, 2, 1.
Уравнения (1) и (2) называют уравнениями Беллмана. Это рекуррентные соотношения, позволяющие найти предыдущее значение функции, зная последующие.
Процесс решения уравнений (1) и (2) называют условной оптимизацией.
В результате условной оптимизации получают две последовательности:
*(), *(),....,*(),*()
- условные максимумы целевой функции на последнем, на двух последних, на … n шагах и
*(), *(),....,*(),*()
-- условные оптимальные управления на n-м, (n-1), …, 1-м шагах. Используя эти последовательности можно найти решение задачи ДП при данных n и
*=*()
Планируется деятельность четырех предприятий на очередной год. Начальные средства =5 у.е. Размеры вложения в каждое предприятие кратны 1 у.е. Средтва x, выделенные k-му предприятию (k=1, 2, 3, 4), приносят в конце года прибыль (x). Функции (x) заданы таблично, при этом:
a)Прибыль (x) не зависит от вложения средств в другие предприятия
b)Прибыль от каждого предприятия выражается в одних условных единицах
c)Суммарная прибыль равна сумме прибылей, полученных от каждого предприятия
Определить, какое количество средств нужно выделить каждому предприятию, чтобы суммарная прибыль была max.
k - кол-во предприятий; xk – кол-во средств, выделенных k – предприятию; Fk(xk) – прибыль предприятия; s0 – начальные средства. Номер шага k совпадает с № предприятия.
Одной из важных экономических проблем является определение оптимальной стратегии в замене старых станков, агрегатов, машин на новые. Старение оборудования включает его физический и моральный износ, в результате чего растут производственные затраты по выпуску продукции на старом оборудовании, увеличиваются затраты на его ремонт и обслуживание, снижаются производительность и ликвидная стоимость
Рассмотрим конкретный пример. Оборудование эксплуатируется в течение 5 лет, после этого продаётся. В начале каждого года нужно принять решение: сохранить оборудование или заменить его новым. Стоимость нового оборудования = 4000 ед. После t лет эксплуатации оборудование можно продать за g(t)= (ликвидная стоимость).
Затраты на содержание в течение одного года зависят от возраста t оборудования и равны: r(t)=600(t+1) Определить оптимальную стратегию эксплуатации оборудования, чтобы суммарные затраты с учётом начальной покупки и заключительной продажи были минимальны.