Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
1.Основные понятия ИСО. Операция.Эффективность операции. Опер-любое мероприятие(система действий), объединенное единым замыслом и направленное к достижению определенной сферы. Прим:размещение заказов на произ-во оборуд. Оптимальные решения-реш,кот. Предпочтительнее других. Основная задача ИС-предварительное колич.обоснован.оптимал решений. Размышляя над организ-ей операции, мы стремимся сделать ее эффективнее. Под эффективн.разумеется степень ее приспособл. к выполн. Стоящей перед ней задачи. Чем лучше организована операция, тем она «эффективнее». Численный показатель оценки W. Многие операции выполн в условиях случайности. тогда в качестве показателя выбирается не просто характеристика исхода операции, а ее среднее значение(матем. ожидание).В других случаях выбирается вероятность события.Правильный выбор показ зффект необх условие полезности исслед.Когда показатель эффекитивности надо обратить в min,задача сводится к максимилизации.Но, во многих задачах ИСО разумно обеспечить не max,а min некоторого показателя.
2.Осн.пон.ИСО.Матем.модель операции. Чем удачнее подобрана матмодель, тем лучше она отражает характ.черты явления, тем успешнее будет исследование и полезнее-вытекающие из него рекомендации.Модель не должна быть «засорена» множеством мелких,второстепенных факторов –их учет усложняет матем.анализ и делает результаты исследования трудно обозримыми.Построение мат.модели-наиболее важное и ответственная часть исслед, требующая глубоких знаний не ток в мат-ке,а больше в моделируемых явлениях.Матем.модели:аналити(характерно устан.формульных,аналит зависимостей) и статистич(процесс операц. Как бы копируется на вычислительной машине).Статистические модели имеют преимущество перед аналитическими,они позволяют учесть больше факторов и не требуют рубых упрощений и допущений.Зато результаты даются труднее осмыслению и анализу.Наилуч резул получ при совместномприменении моделей.
3. Общая постановка задачи ИСО-детерминированный случай;оптимизация решения в условиях неопределнности. Рассмотрим задачу исследования операций в общей постановке, без- относительно к виду и цели операции. Пусть имеется некоторая опе- рация O, т. е. управляемое мероприятие, на исход которого мы мо- жем в какой-то мере влиять, выбирая тем или другим способом зависящие от нас параметры. Эффективность операции характеризуется показателем W, который требуется обратить в максимум (случай, когда его требуется обратить в минимум, сводится к предыдущему и отдельно не рассматривается). Предположим, что математическая модель операции построена; она позволяет вычислить показатель эффективности W при любом принятом решении, для любой совокупности условий, в которых выполняется операция. Рассмотрим сначала наиболее простой случай: все факторы, от которых зависит успех операции, делятся на две группы: — заданные, заранее известные факторы (условия проведения операции) α1, α2, . . . , на которые мы влиять не можем; — зависящие от нас факторы (элементы решения) x1, x2, . . . , которые мы, в известных пределах, можем выбирать по своему усмотрению. Этот случай, в котором факторы, влияющие на исход операции, либо заранее известны, либо зависят от нас, называться детерминированным. детерминированная задача отыскания оптимального решения сводится к математической задаче отыскания экстремума функции W; эта задача может быть весьма сложной (особенно при многих аргументах), но является вычислительной задачей, Трудности, возникающие при этом, являются расчетными, а не принципиальными.
К сожалению, этот простейший случай не так уж часто встречается на практике. Гораздо более типичен случай, когда не все условия, в которых будет проводиться операция, известны заранее, а некоторые из них содержат элемент неопределенности. Пусть эффективность операции характеризуется некоторым по-
казателем W, зависящим от всех трех групп факторов. Это мы запишем в виде общей формулы: W = W(α1, α2, . . . ; Y1, Y2, . . . ; x1, x2, . . .).Если бы условия Y1, Y2, . . . были известны, мы могли бы заранее подсчитать показатель W и выбрать такое решение x1, x2, при котором он максимизируется. Беда в том, что параметры Y1, Y2 нам неизвестны, а значит, неизвестен и зависящий от них показатель эффективности W при любом решении. Ее можно сформулировать так:
При заданных условиях α1, α2, с учетом неизвестных факто- ров Y1, Y2,найти такие элементы решения x1, x2 которые по возможности обращали бы в максимум показатель эффективности W. Наконец, сделаем одно общее замечание. При обосновании ре- шения в условиях неопределенности, что бы мы ни делали, эле- мент неопределенности остается. Поэтому неразумно предъявлять к точности таких -решений слишком высокие требования. Вместо того, чтобы после скрупулезных расчетов однозначно указать одно- единственное, в точности оптимальное (в каком-то смысле) решение, всегда лучше выделить область приемлемых решений, которые ока- зываются несущественно хуже других, какой бы точкой зрения мы ни пользовались. В пределах этой области могут произвести свой окончательный выбор ответственные за него лица.
4.Линейное программирование. Задачи ЛП. Во многих областях практики возникают своеобразные задачи опти- мизации решений, для которых характерны следующие черты:1)показатель эффективности W представляет собой линейную функцию от элементов решения x1, x2.2) ограничительные условия, налагаемые на возможные реше- ния, имеют вид линейных равенств или неравенств.Такие задачи принято называть задачами линейного программи- рования (в данном случае подразумевается планирование).
Задача о пищевом рационе. Имеется четыре вида продуктов питания:F1, F2, F3, F4.Известна стоимость единицы каждого продукта:c1, c2, c3, c4.Из этих продуктов необходимо составить пищевой рацион, который должен содержать:белков не менее b1 единиц.Единица продукта Fi содержит ai1 единиц белков. Требуется так составить пищевой рацион, чтобы обеспечить за- данные условия при минимальной стоимости рациона. Запишем сфор- мулированные словесно условия задачи в виде математических фор- мул. Обозначим x1, x2, x3, x4количества продуктов F1, F2, F3, F4, входящих в рацион. Очевидно, общая стоимость рациона будет L = c1x1 + c2x2 + c3x3 + c4x4 Запишем математически условия задачи. В одной единице продукта F1 содержится a11 единиц белка, значит, в x1 единицах a11 · x1 Общее количество белков, содержащееся в рационе, не должно быть меньше b1 отсюда получаем первое условие-неравенство:a11 · x1 + a21x2 + a31x3 + a41x4 “ b1. Эти условия представляют собой ограничения, накладываемые на решение. Возникает следующая задача:Выбрать такие неотрицательные значения переменных x1, x2, x3, x4, удовлетворяющие линейным неравенствам, при которых линейная функция этих переменных L = c1x1 + c2x2 + c3x3 + c4x4 обращалась бы в минимум.Задача о загрузке станков.Ткацкая фабрика располагает N1 станками типа 1 и N2 станками типа 2. Станки могут производить четыре вида тканей: T1, T2, T3, T4. Каждый тип станка может производить любой из видов тканей, но в неодинаковом количестве. Станок типа 1 производит в месяц a11 метров ткани T1, a12 метров ткани T2. Соответствующие числа для станка типа 2 будут a21, a22, a23, a24. Производство ткани T1 на одном станке типа 1 в течение месяца приносит фабрике доход c11, ткани T2 - доход c12. Фабрике предписан план, согласно которому она обязана произвести за месяц: не менее b1 метров ткани T1, не менее b2 метров ткани T2. Требуется так распределить загрузку станков производством тканей различного вида, чтобы план был вы- полнен и при этом месячная прибыль была максимальна. Запишем условия задачи математически. Обозначим x11 - число станков типа 1, занятых производством ткани T1, x12 — число станков типа 1, за- нятых производством ткани T2, и вообще xij — число станков типа i, занятых производством ткани Tj . Первый индекс соответствует типу станка, второй — виду ткани (i = 1, 2, j = 1, 2, 3, 4). . Общая прибыль будет равна: L = c11x11 + c21x21 + c12x12 + c22x22 + c13x13 + c23x23 + c14x14 + c24x24. Выбрать такие неотрицательные значения переменных x11, x12, x24,удовлетворяющие линейным неравенствам, при которых линейная функция этих переменных обращалась бы в максимум.
5. ЛП.Осн.задача ЛП.ЛП с огран-нерав.Связь с ОЗЛП. рассмотрим задачу линейного программирвания с ограничениями - равенствами — так называемую основную задачу линейного программирования (ОЗЛП). Основная задача линейного программирования ставится следующим образом.Имеется ряд переменных x1, x2, xn Требуется найти такие неотрицательные значения этих переменных, которые удовлетворяли бы системе линейных уравнений: a11x1 + a12x2 + . . . + a1nxn = b1 и, кроме того, обращали бы в минимум линейную функцию L = c1x1 + c2x2 + . . . + cnxn Очевидно, случай, когда линейную функцию нужно обратить не в минимум, а в максимум, легко сводится к предыдущему, если изменить знак функции и рассмотреть вместо нее функцию Lr = −L = −c1x1 − c2x2 Оптимальным решением будем называть то из допустимых решений, при котором линейная функция обращается в минимум. На практике ограничения в задаче линейного программирования ча- сто задаются не уравнениями, а неравенствами. Покажем, как можно перейти от задачи с ограничениями-неравенствами к основной задаче линейного программирования. Пусть имеется задача линейного программирования с n переменными x1, x2, xn, в которой ограни- чения, наложенные на переменные, имеют вид линейных неравенств. ограничения-неравенства в стандартной форме a11x1 + a12x2 + . . . + a1nxn + b1<0 Требуется найти такую совокупность неотрицательных зна- чений x1, x2, . . . , xn, которая удовлетворяла бы неравенствам кроме того, обращала бы в минимум линейную функцию L = c1x1 + c2x2 + . . . + cnxn От поставленной таким образом задачи легко перейти к основной задаче линейного программирования.Действительно, введем обозначения y1 = a11x1 + a12x2 + . . . + a1nxn + b1. Таким образом, задача линейного программирования с ограничениями-неравенствами сведена нами к основной задаче линейного программирования, но с большим числом переменных, чем первоначально было в задаче
6. ЛП. Симплекс-метод решения задачи ЛП. Для нахождения решения задачи линейного программирования в об- щем случае (при произвольном числе свободных переменных) при- меняются вычислительные методы. Из них наиболее универсальным является так называемый симплекс-метод. Идея симплекс-метода относительно проста. Пусть в задаче ли- нейного программирования имеется n переменных и m независимых линейных ограничений, заданных в форме уравнений. Мы знаем, что оптимальное решение (если оно существует) достигается в одной из опорных точек (вершин ОДР), где по крайней мере k = n − m из пе- ременных равны нулю. Выберем какие-то k переменных в качестве свободных и выразим через них остальные m базисных переменных. например, в качестве свободных выбраны первые k = n − m переменных x1, x2, xk , а остальные m выражены через них xk+1=αk+1,1x1 + αk+1,2x2 + . . . + αk+1,k xk + βk+1 Попробуем, что будет, если положить все свободные переменные x1, x2, xk равными нулю x1 = 0, x2 = 0, xk = 0 Получим xk+1 = βk+1, xk+2 = βk+2, . . . , xn = βn Это решение может быть допустимым или недопустимым. Оно допу- стимо, если все свободные члены βk+1, βk+2, . . . , βn неотрицательны. Предположим, что это условие выполнено. Тогда мы получили опор- ное решение. Но является ли оно оптимальным? Может быть да, а может быть и нет. Чтобы проверить это, выразим минимизируемую линейную функцию L через свободные переменные x1, x2 L = γ0 + γ1x1 + γ2x2 + . . . + γk xk Очевидно, что при x1 = x2 = . . . = xk = 0 L = γ0.Посмотрим, не
можем ли мы улучшить решение, т. е. уменьшить функцию L, увеличивая какие-нибудь из переменных x1, x2 Предположим, что уравнения типа для нового набора базисных и свободных переменных составлены. Тогда можно выразить через новые свободные переменные и линейную функцию L. Если все коэффициенты при переменных в этой формуле положительны, то мы нашли оптимальное решение: оно получится, если все свободные переменные положить равными нулю. Если среди коэффициентов при переменных есть отрицательные, то процедура улучшения решения продолжается: система вновь переразрешается относительно других базисных переменных, и так далее, пока не будет найдено оптимальное решение, обращающее функцию L в минимум
7. Лп.Табличный алгоритм замены базисных переменных.
Процедура «переразрешения» системы уравнений-ограничений ОЗЛП относительно новых базисных переменных может быть существенно упрощена, если ее формализовать и свести к заполнению стандарт- ных таблиц по определенной системе правил (короче, алгоритму). Этот алгоритм мы продемонстрируем на конкретном примере (в его справедливости для любого общего случая читатель сможет убедить- ся самостоятельно).Рассмотрим систему пяти уравнений-ограничений:y1= a11x1 + a12x2 + a13x3 + a14x4 + b1 с четырьмя свободными переменными: x1, x2, x3, x4. Пусть нам тре- буется вывести из числа свободных какую-нибудь переменную, на- пример x2, и перевести ее в базисные, а взамен ее ввести в число свободных какую-то базисную переменную, скажем y3; короче, мы хотим обменять местами переменные x2 и y3 алгоритм преобразования коэффициентов стандартной таблицы. Разрешающий элемент заменяется на обратную ему величину. Все остальные элементы разрешающей строки делятся на разрешающий элемент. Все элементы разрешающего столбца (кроме самого разреша- ющего элемента) меняют знак и делятся на разрешающий элемент. Каждый из остальных элементов подвергается следующему пре- образованию: к нему прибавляется произведение элемента, сто- явшего в прежней разрешающей строке на том же месте по по- рядку (т. е. в том же столбце), на элемент, стоящий в новом разрешающем столбце на соответствующем месте (т. е. в той же строке, что и наш элемент).
8. ЛП.Отыскание ДОР ОЗЛП. Отыскание оптимал решен ОЗЛП.
Теперь мы займемся оптимизацией решения, т. е. отысканием такого опорного решения, которое обращает в минимум линейную функцию L = c0 − (γ1x1 + γ2x2 + + γnxn). Здесь мыпокажем, как эта оптимизация может быть проведена с помощью табличного алгоритма замены xj ↔ yi. сформулируем правила нахождения оптимального реше- ния ОЗЛП симплекс-методом. Если все свободные члены (не считая строки L) в симплекс- таблице неотрицательны, а в строке L (не считая свободного члена) нет ни одного положительного элемента, то оптимальное решение достигнуто. Если в строке L есть положительный элемент, а в столбце, соответствующем ему, нет ни одного положительного элемента, то линейная функция L не ограничена снизу, и оптимального решения не существует. Если в этом столбце есть положительные элементы, то следует произвести замену одной из свободных переменных на одну из базисных, причем в качестве разрешающего надо взять тот элемент этого столбца, для которого отношение к нему соот- ветствующего свободного члена минимально.
9. ЛП. Понятие двойственности.Решение.Рассмотрим две следующие задачи линейного программирова- ния: c1x1 + c2x2 + . . . + cnxn → min aij xj “ bi (i = 1, 2, . . . , m) xj “ 0 (j = 1, 2, . . . , n) и b1y1 + b2y2 + . . . + bnym → max aij yi ™ cj (i = 1, 2, . . . , m), yi “ 0 (i = 1, 2, . . . , m) Теорема двойственности а) Если и основная и двойственная ей задачи имеют допустимые решения, то существует оптимальное решение x∗(j = 1, 2..) исходной задачи;
i
существует оптимальное решение y∗(i = 1, 2) двойственной задачи. имеет место следующее соотношение cj xj = biyi Если исходная (двойственная) задача допускает оптимальное решение, для которого значение целевой функции ограничено, то соответствующая ей двойственная (исходная) задача допус- кает оптимальное решение при том же значении целевой функции. Таким образом, симплексный метод мож- но рассматривать как способ получения пробных решений двойственной задачи путем определения допустимых решений исходной задачи.
11. Транспортная задача ЛП.Нахождение опорного плана. существуют некоторые частные типы задач линейного программирования, которые, в силу некоторых особенностей своей структуры, допускают реше- ние более простыми методами. К ним относится, в частности, так называемая транспортная задача. Имеется m пунктов отправления: A1, A2, . . . , Am, в которых со- средоточены запасы какого-то однородного товара (груза) в коли- честве соответственно a1, a2, . . . , am единиц. Кроме того, имеется n пунктов назначения: Bl, B2, . . . , Bn, подавших заявки соответственно на b1, b2, . . . , bn единиц товара. Предполагается, что сумма всех заявок равна сумме всех запасов ai = bj Известна стоимость cij перевозки единицы товара от каждого пункта отправления Ai до каждого пункта назначения Bj . Таблица (матрица) стоимостей перевозки cij задана: c11c12c1n Требуется составить такой план перевозок, при котором все заяв- ки были бы выполнены, и при этом общая стоимость всех перевозок была минимальна. При такой постановке задачи показателем эффективности плана перевозок является стоимость; поэтому поставленную задачу точнее называют транспортной задачей по критерию стоимости.Дадим этой задаче математическую формулировку. Обозначим xij - количество груза, отправляемого из i-го пункта отправления Ai в j-й пункт назначения Bj (i = 1, . . . , m; j = 1, . . . , n) все коэффициенты при переменных в уравнениях равны единице. ранг системы уравнений r = m + n − 1. В транспортной таблице записываются пункты отправления и назначения; запасы, имеющиеся в пунктах отправления; заявки, поданные пунктами назначения; стоимости перевозок из каждого пункта отправления в каждый пункт назначения. . Среди допустимых планов непременно имеется оптимальный (может быть, не один), потому что линейная функция L — стоимость перевозок заведомо неотрицательна (ограничена снизу нулем).
12.Решение трансп.задачи методом потенциалов.ТЗ с неправильным балансом.Распределительный метод решения ТЗ, с которым мы познакоми- лись в предыдущем параграфе, обладает одним недостатком: нужно отыскивать циклы для всех свободных клеток и находить их цены. От этой трудоемкой работы нас избавляет специальный метод решения ТЗ, который называется методом потенциалов. Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены. Пусть имеется транспортная задача с балансовыми условиями xij = ai (i = 1, . . . , m); xij = bj (j = 1, . . . , n) Требуется найти план перевозок (xij ), который удовлетворял бы балансовым условиям(3.1), и при этом стоимость всех перевозок бы- ла минимальна L = . . cij xij → min Идея метода потенциалов для решения ТЗ сводится к следующе- му. Представим себе, что каждый из пунктов отправления Ai вносит за перевозку единицы груза (все равно, куда) какую-то сумму бi; в свою очередь, каждый из пунктов назначения Bj также вносит за перевозку единицы груза (куда угодно) сумму вj ; эти платежи пе- редаются некоторому третьему лицу ( перевозчику.алгоритму решения транспортной задачи методом потенциалов: Взять любой опорный план перевозок, в котором отмечены m+ n − 1 базисных клеток (остальные клетки свободные). Определить для этого плана платежи (αi, βj ) исходя из усло- вия, чтобы в любой базисной клетке псевдостоимости были рав- ны стоимостям. Подсчитать псевдостоимости c˜ij = αi + βj для всех свободных клеток. Если окажется, что все они не превышают стоимостей, то план оптимален. Если бы хотя в одной свободной клетке псевдостоимость пре- вышает стоимость, следует приступить к улучшению плана пу- тем переброски перевозок по циклу, соответствующему любой свободной клетке с отрицательной ценой (для которой псевдо- стоимость больше стоимости). После этого заново подсчитываются платежи и псевдостоимо- сти, и, если план все еще не оптимален, процедура улучшения продолжается до тех пор,пока не будет найден оптимальный план. классическая транспортная задача, иначе называемая транспортной задачей с правильным балансом . Встречаются такие варианты ТЗ, где условие (3.19) нарушено. В этих услучаях говорят о ТЗ с неправильным балансом. Баланс ТЗ может нарушаться в двух направлениях: ai = . bj Сумма запасов в пунктах отправления превышает сумму по- данных заявок. Сумма поданных заявок превышает наличные запасы.
13. Элементы теории игр.Основн понят, классиф,описан игр. В теории игр лиц, принимающих решения , называют игроками, а целевую функцию платежной функцией. Каждый игрок распо- лагает конечным или бесконечным набором допустимых решений, называемых стратегиями. Выигрыш каждого игрока определяется его платежной функцией, значения которой зависят от стратегий всех участников игры. Фактически игра представляет собой сово- купность правил, известных всем игрокам. Эти правила, с одной стороны, определяют множества стратегий игроков, а с другой последствия и выигрыши в результате выбора каждой из стратегий. Заметим, что в теории игр понятие стратегии является одним из центральных. Классификацию игр проводят по различным признакам: по числу игроков;по числу стратегий;по свойствам платежной функции; по характеру предварител. договоренности м/у игроками. Игру, в которой участвует n игроков, называют игрой с n участни- ками. Количество n участников может быть равным 2, 3 и т.д. При наличии двух игроков могут возникать и конфликтные ситуации, и необходимость в координированных действиях (кооперация). Если в игре участвует не менее трех игроков, то могут создаваться коали- ции, т.е. группы из двух или более игроков, имеющих общую цель и координирующих свои стратегии. По количеству стратегий различают игры конечные и бесконечные. Если хотя бы один из игроков располагает бесконечным множеством стратегий, то игру называ- ют бесконечной. Если же каждый из игроков располагает конечным множеством стратегий, то игру называют конечной. Еще один способ классификации игр по свойствам платежной функции. В игре с нулевой суммой общая сумма выигрышей всех игроков равна нулю. В игре с нулевой суммой и двумя участниками выигрыш одного из них равен проигрышу другого. Таким образом, в играх с нулевой суммой существует конфликт между игроками, и поэтому их называют также антагонистическими играми. В общем случае в игре с нулевой суммой, как правило, имеют место и конфликты, и согласованные действия игроков. Прямой противоположностью иг- рам с нулевой суммой являются игры двух игроков с постоянной разностью, в которых оба игрока выигрывают или проигрывают од- новременно. Поэтому игрокам выгодно действовать согласованно. В зависимости от характера предварительной договоренности между игроками различают кооперативные и некооперативные игры. Игра кооперативная, если до ее начала игроки образуют коали- ции и принимают взаимообязывающие соглашения о координации своих стратегий. В противном случае игра будет некооперативной. Прежде чем переходить к рассмотрению основных способов описа- ния и анализа любой конкретной игры, введем еще два понятия, широко используемых в теории игр. Ход это момент игры, когда игроки должны выбрать один из возможных вариантов действий, т.е. принять одно из допустимых решений. Партия игры это определенная совокупность ходов и выборов возможных вариантов действий. Существуют два основных способа описания и анализа любой конкретной игры. Первый способ предполагает следующее: перечисление ходов, которые могут делать игроки; определение информации, которой располагают игроки в процессе игры; определение возможных вариантов действий игроков; указание предельных размеров платежей в конце игры.
14. Игры двух участников с нулевой суммой. Игры двух участников с нулевой суммой представляют собой наи- более разработанный раздел теории игр. Если игра двух участников с нулевой суммой представлена в нормальной форме, то для всех i = 1, . . . , m; и j = 1, . . . , n i + Πj = 0 где Р1 и Р2 выигрыши первого и второго игроковпри выборе ими стратегий X1 и X2 соответственно. При этом первый игрок располагает m стратегиями, а второй n стратегиями. Поэтому в данном случае вместо единой платежной матрицы используют пла- тежную матрицу первого игрока. В играх двух участников с нулевой суммой выигрыш одного из них равен проигрышу другого. Поэтому, если целью одного из иг- роков является максимизация своего выигрыша, то целью другого игрока является минимизация своего проигрыша. Если фиксирован- ная стратегия одного из игроков (допустим, первого) не обладает свойством устойчивости, то она не может быть оптимальной, так как в этом случае второй игрок может улучшить свое положение (увеличить свой выигрыш или уменьшить свой проигрыш) за счет улучшения положения первого игрока. Итак, среди игр двух лиц с нулевой суммой существуют игры без седловых точек. В таких играх нижняя цена игры строго меньше ее верхней цены, а минимаксные и максиминные стратегии не являют- ся оптимальными, т.е. их совокупность не является решением игры.
15.Решение игр 2 участников с нулевой суммой в смешанных стратегиях..Аналит.метод для игр с платежной матрицей 2 порядка. На практике в играх двух участников с нулевой суммой гораздо чаще встречается случай, когдаседловых точек нет, т.е. верхняя Π∗ и нижняя Π∗ цены игры различаются. Если искать решения подобных задач в чистых стратегиях, то в расчете на разумного противника мы должны воспользоваться минимаксным (максиминным) крите- рием. В этом случае первый игрок гарантирует себе выигрыш, рав- ный нижней цене игры Π∗. При этом естественное желание первого игрока гарантировать себе выигрыш больше чем Π∗ и естественное желание второго игрока гарантировать себе проигрыш меньше чем Π∗ при использовании чистых стратегий приводят к нарушению ста- бильности игры. Для преодоления нестабильности игры используют смешанные стратегии, которые заключаются в случайном чередовании чистых стратегий. Аналитический метод для игр с платежной матрицей второго порядка. В дальнейших рассуждениях под активными стратегиями игрока будем понимать те чистые стратегии, которые с ненулевыми веро- ятностями содержатся в его оптимальной смешанной стратегии. играх двух участников с нулевой суммой, каждый из которых имее две чистые стратегии, платежная матрица имеет порядок два. При отсутствии седловой точки решение может быть найдено в смешан- ных стратегиях и обе чистые стратегии каждого игрока являются активными.
16. Решение игр 2 участников с нулевой суммой в смешанных стратегиях. Метод ЛП. Использование линейного программирования наиболее эффек- тивно для игр двух участников с нулевой суммой без седловых точек и большим количеством стратегий у обоих игроков. В прин- ципе любая конечная игра двух участников с нулевой суммой может быть преобразована в соответствующую задачу линейного програм- мирования и, наоборот, каждую задачу линейного программирова- ния можно интерпретировать как конечную игру двух участников с нулевой суммой. что в этой задаче отсутствует ограничение типа равен- ства, связывающее вероятности выбора первым игроком своих чи- стых стратегий. Данное обстоятельство обусловлено наличием функ- циональной зависимости между координатами x∗ оптимального ре- шения рассматриваемой задачи линейного программирования, ко- ординатами p1∗ оптимальной смешанной стратегии первого игрока и ожидаемой ценой игры.Замечания:
ij
Если н < 0, то ко всем элементам платежной матрицы (Рij ) можно прибавить настолько большое положительное число K > max Рij , что все элементы платежной матрицы станутположительными. В этом случае цена игры увеличится на K, а решение не изменится. Двойственность задач линейного программирования для пер- вого и второго игроков приводит к тому, что решение одной из них автоматически приводит к решению другой. Учитывая это, как правило, решают задачу, имеющую меньшее число ограни- чений. А это, в свою очередь, зависит от числа чистых страте- гий, находящихся в расположенных каждого игрока.
17. Игры двух участников с ненулевой суммой. В играх двух участников с нулевой суммой интересы игроков яв- ляются диаметрально противоположными и им невыгодно информи- ровать друг друга о своих предполагаемых действиях. Иная картина может наблюдаться в играх двух участников с ненулевой суммой. В частности, совершенно очевидна необходимость координированных действий игроков в игре с постоянной разностью. когда они выигрывают и проигрывают одновременно. При этом
ij
(Πk ) - платежная матрица k-ro игрока, k = 1, 2.Таким образом, как и в играх двух участников с нулевой суммой, в рассматриваемом подходе к решению некооперативных игр опти- мальность решения связывают с состоянием равновесия игры, т.е. с ситуацией, в которой ни одному из игроков невыгодно изменять свою стратегию. Следует отметить, что в некооперативной игре может быть несколько точек равновесия и различным парам смешанных оптимальных стратегий игроков могут соответствовать различные значения ожидаемых выигрышей.