Классические кооперативные игры.

Игра называется кооперативной, или коалиционной, если игроки могут объединяться в группы, беря на себя некоторые обязательства перед другими игроками и координируя свои действия. Этим она отличается от некооперативных игр, в которых каждый обязан играть за себя.

Кооперативные игры получаются в тех случаях, когда, в игре n игроков разрешается образовывать определённые коалиции. Обозначим через N множество всех игроков, N ={1, 2,..., n}, а через K - любое его подмножество. Пусть игроки из K договариваются между собой о совместных действиях и, таким образом, образуют одну коалицию. Очевидно, что число таких коалиций, состоящих из r игроков, равно числу сочетаний из n по r, то есть а число всевозможных коалиций равно .

Из этой формулы видно, что число всевозможных коалиций значительно растёт в зависимости от числа всех игроков в данной игре. Для исследования этих игр необходимо учитывать все возможные коалиции, и поэтому трудности исследований возрастают с ростом n. Образовав коалицию, множество игроков K действует как один игрок против остальных игроков, и выигрыш этой коалиции зависит от применяемых стратегий каждым из n игроков.

Кооперативные игры.

Игра называется кооперативной, если в ней игрокам разрешается обсуждать перед игрой свои стратегии и договариваться о совместных действиях (добровольный обмен между игроками информацией, совместный выбор стратегий, передача игроками части выигрыша друг другу и т.п.); иначе говоря, игроки могут образовывать коалиции. Теория кооперативных игр исследует типы коалиций, образующихся в процессе игры и условия, необходимые для их устойчивого существования.

Обозначим через N множество всех игроков, причем игроков принято различать по их номерам, т.е. N={1,2,...,n}, а через S – любое его подмножество, которое является коалицией. Очевидно, что число коалиций, состоящих из k игроков, равно числу сочетаний из n по k, то есть , а число всевозможных коалиций равно

Из этой формулы видно, что число всевозможных коалиций значительно растёт в зависимости от количества n всех игроков в данной игре. Образовав коалицию, множество игроков S действует как один игрок против остальных игроков, и выигрыш этой коалиции зависит от применяемых стратегий каждым из n игроков. Общность интересов игроков из S означает, что выигрыш объединенного игрока есть сумма выигрышей составляющих его игроков из S.

Пусть игроки из N, образуя различные коалиции, могут получать некоторые сравнимые между собой выигрыши. Обозначим выигрыш, который может уверенно обеспечить себе коалиция S ⊂ N, через V(S). Функция V, ставящая в соответствие каждой коалиции S наибольший уверенно получаемый ею выигрыш V(S), называется характеристической функцией.

Если для всех непересекающихся подмножеств А и В выполняется неравенство V(A ∪ B) ≥ V(A) + V(B) (1), то характеристическая функция является супераддитивной. Свойство супераддитивности означает, что если нет ни одного игрока, который входил бы одновременно в обе коалиции А и В, то коалиция, составленная как объединение этих двух подмножеств, будет иметь выигрыш не меньший, чем сумма выигрышей А и В. Предположение о супераддитивности является вполне логичным, т.к. создание коалиций было бы бессмысленным, если бы величина выигрыша уменьшалась с увеличением числа участников коалиции.

Игра называется существенной в том случае, если

Содержательно выполнение этого неравенства означает, что если игра является существенной, то при объединении всех участников конфликта возникает дополнительный выигрыш:

который может быть распределен между всеми игроками, в результате чего выигрыш каждого из них может стать больше, чем в том случае, когда каждый из игроков действует самостоятельно.

Игра называется несущественной в том случае, если вместо этого неравенства выполняется равенство:

Содержательно это означает, что дополнительного выигрыша от объединения всех участников конфликта в коалицию не возникает.

Одним из ключевых понятий в теории кооперативных игр является понятие дележа.

16.Линейное программирование как метод оптимального планирования.

В настоящее время для решения оптимальных задач применяют в основном следующие методы:

· методы исследования функций классического анализа;

· методы, основанные на использовании неопределенных множителей Лагранжа;

· вариационное исчисление;

· динамическое программирование;

· принцип максимума;

· линейное программирование;

· нелинейное программирование.

Линейное программирование представляет собой математический аппарат, разработанный для решения оптимальных задач с линейными выражениями для критерия оптимальности и линейными ограничениями на область изменения переменных. Такие задачи обычно встречаются при решении вопросов оптимального планирования производства с ограниченным количеством ресурсов, при определении оптимального плана перевозок (транспортные задачи) и т. д.

Для решения большого круга задач линейного программирования имеется практически универсальный алгоритм - симплексный метод, позволяющий за конечное число итераций находить оптимальное решение подавляющего большинства задач. Тип используемых ограничений (равенства или неравенства) не сказывается на возможности применения указанного алгоритма. Дополнительной проверки на оптимальность для получаемых решений не требуется. Как правило, практические задачи линейного программирования отличаются весьма значительным числом независимых переменных. Поэтому для их решения обычно используют вычислительные машины, необходимая мощность которых определяется размерностью решаемой задачи.

17.Метод наименьшей стоимости, распределительный метод оптимального планирования.

При использование метода наименьших затрат, выбирается клетка с наименьшими затратами на транспортировку единицы товара. Если такие клеток несколько, то из них необходимо выбрать ту, которая соответствует наименьшей поставке. Заполняем эту клетку, вписав в нее требуемое значение единиц товара.

При этом один столбец или одно строка выпадает из рассмотрения. По аналогии заполняем следующие клетки. При заполнении последней выподает сразу строка и столбец.

Метод потенциалов.

Существующий алгоритм решения транспортных задач (метод потенциалов) предполагает, что ЦФ стремится к минимуму. Однако существуют ситуации, когда в рамках транспортной модели требуется максимизировать ЦФ, например, общий доход, объем продаж, прибыль, качество выполняемых работ и т.д. В этом случае в модель вместо искомой ЦФ L(X) водится ЦФ L1(X)= −L(X,) в которой тарифы умножаются на (-1). Таким образом, максимизация L(X) будет соответствовать минимизации L1 (X).