Шпаргалка по "Математике"

Если из занятых клеток образ.цикл, то план перевозок не явл. опорным, цикл строится только для свободных клеток.

Алгоритм решения  ТЗ методом потенциалов

1. Построить опорный план  по 1 из правил 

2. Вычислить потенциалы  поставщиков и потребителей: ui(i=1,m) –поставщик, потребитель - vj(j=1,n). ui+ vj=Сij

3. Вычислить оценки Sij=Cij-(ui+vj)

Если все оценки Sij≥0, то полученный план явл. лптимальным,

Если все Sij>0, то получ. оптим. план единственный.

Если хотя бы 1 оценка Sij=0, имеем бесчисленное множество оптимальных планов с 1 и тем же значение целевой функции.

 

 

 

 

 

 

27. Матричные игры  с нулевой суммой 

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

Совокупность правил однозначно определяющей последовательность действий стороны в конфликтной ситуации есть стратегия.

Игра – совокупность предварительно оговоренных правил и условий.

Если n партнеров в данной игре, то осн. содержание теории игр состоит в как должен вести партию j (j=1.k), для достижения благоприятного исхода.

Предполагается, что в  конце партии каждой игры получим  сумму – vj (j=1,n) – выигрыш.

vj (j=1,n) могут быть положительными, отрицательными, =0.

В большинстве случаев  имеются игры с 0 суммой, v1+v2+…. +vn=0. Сумма выигрыша от одного партнера переходит к другому не поступая из внешних источников.

Игра с нулевой суммой предполагает, что сумма выигрыша каждой партии равна 0.

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

Принятие игроком того или иного решения и его  реализация наз.-  ходом.

В зависимости от количества стратегий игры делятся на конечные и бесконечные.

В зависимости от взаимоотношения  игроков игры делятся на кооперативные, коалиционные и бескоалиционные.

Если игроки не имеют право  вступать в соглашения, такая игра относится к бескоалиционным.

Если вступают в соглашения – коалиционной.

Кооперативная игра – заранее  определяют коалиции.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

28 Чистые и смешанные  стратегии и их свойства

Если в игре каждый из противников применяет только одну и ту же стратегию, то про саму игру в этом случае говорят, что она  происходит в чистых стратегиях, а используемые игроком А и игрокомВ пара стратегий называются чистыми стратегиями. 
Определение. В антогонистической игре пара стратегий (А_i, В_j) называется равновесной или устойчивой, если ни одному из игроков не выгодно отходить от своей стратегии. 
Применять чистые стратегии имеет смысл тогда, когда игроки А и В располагают сведениями о действиях друг друга и достигнутых результатах. Если допустим, что хотя бы одна из сторон не знает о поведении противника, то идея равновесия нарушается, и игра ведется бессистемно. 
Определение. Случайная величина, значениями которой являются чистые стратегии игрока, называется его смешанной стратегией. 
Таким образом, задание смешанной стратегии игрока состоит в указании тех вероятностей, с которыми выбираются его чистые стратегии. 
 
Будем обозначать смешанные стратегии игроков А и В соответственно 
 
S_A=||p₁,p₂,...,p_m||, S_B=||q₁,q₂,...,q_n||, где p_i - вероятность применения игроком А чистойстратегии А_і;  ,q_j - вероятность применения игроком В чистой стратегии B_j;   
 
В часном случае, когда все вероятности, кроме одной, равны нулю, а эта одна - единице, смешанная стратегия превращается в чистую. 
 
Применение смешанных стратегий осуществляется, например, таким образом: игра повторяется много раз, но в каждом партии игрок применяет различные чистые стратегии, но с относительными частотами их применения, равными p_i и q_j. 
Смешанные стратегии в теории игр представляют собой модель изменчивой, гибкой тактики, когда ни один из игроков не знает, какую чистую стратегию выберет противник в данной партии. Если игрок А применяет смешанную стратегию S_A=||p₁, p₂, ..., p_m||, а игрок В смешанную стратегию S_B=||q₁, q₂, ..., q_n||, то средний выигрыш (математическое ожидание) игрока А определяется соотношением  .Естественно, что ожидаемый проигрыш игрока В равен такой же величине. 
Итак, если матричная игра не имеет седловой точки, то игрок должен использовать оптимальную смешанную стратегию, которая обеспечит максимальныйвыигрыш .nЕстественно возникает вопрос: какими соображениями нужно руководствоватся при выборе смешанных стратегий? Оказывается принцип минимакса сохраняет свое значение и в этом случае. Кроме того важное значение для понимания решения игр, играют основные теоремы теории игр.

29. Приведение матричной игры к задаче ЛП.

Игра m × n в общем случае не имеет наглядной геометрической интерпретации. Ее решение достаточно трудоемко при больших m и n, однако принципиальных трудностей не имеет, поскольку может быть сведено к решению задачи линейного программирования. Покажем это. Пусть игра m × n задана платежной матрицей p = (a_ij ), i = 1, 2, ..., m; j = 1, 2, ..., n. Игрок А обладает стратегиями A₁ , A₂ , ..., A_m , игрок В — стратегиями B₁ , B₂, ..., B_m . Необходимо определить оптимальные стратегии S*_A = ( p*₁ ,  p*₂ , ... ,  p*_m ) и S*_B = ( q*₁ , q*₂ , ... ,  q*_n ), где p*_i, q*_j — вероятности применения соответствующих чистых стратегий A_i , B_j,   p*₁  + p*₂ +...+ p*_m =1,q*₁ + q*₂ +...+ q*_n = 1.

Оптимальная стратегия S*_A удовлетворяет следующему требованию. Она обеспечивает игроку А средний выигрыш, не меньший, чем цена игры v, при любой стратегии игрока В и выигрыш, равный цене игры v, при оптимальной стратегии игрока B. Без ограничения общности полагаем v > 0: этого можно добиться, сделав все элементы a_ij ≥ 0. Если игрок А применяет смешанную стратегию S*_A = ( p*₁ ,  p*₂ , ... ,  p*_m ) против любой чистой стратегии B_j игрока В, то он получает средний выигрыш, или математическое ожидание выигрыша a_j = a_1j p₁ + a_2j p₂ +...+ a_m j p_m , о = 1, 2, ..., n (т.е. элементы j-го столбца платежной матрицы почленно умножаются на соответствующие вероятности стратегий A₁ , A₂ , ..., A_m и результаты складываются).

Для оптимальной  стратегии S*_A все средние выигрыши не меньше цены игры v, поэтому получаем систему неравенств:

(3.11)

Каждое из неравенств можно разделить на число v > 0. Введем новые переменные:

x1 =  p1/v, x2 = p2/v , ...,  pm/v

(3.12)

Тогда система (11) примет вид:

(3.13)

Цель игрока А — максимизировать свой гарантированный выигрыш, т.е. цену игры v.  
Разделив на v ≠ 0 равенство p₁ + p₂ + ...+ p_m = 1 , получаем, что переменные x₁ (i = 1, 2, ..., m) удовлетворяют условию: x₁ + x₂ + ...+ x_m = 1/v. Максимизация цены игры v эквивалентна минимизации величины 1/v, поэтому задача может быть сформулирована следующим образом: определить значения переменных x_i ≥ 0, i = 1, 2, ..., m, так, чтобы они удовлетворяли линейным ограничениям (13) и при этом линейная функция

Z = x1 + x2 + ...+ xm,

(3.14)

обращалась  в минимум. Это задача линейного программирования. Решая задачу (3.13)—(3.14), получаем оптимальное решение p*₁ + p*₂ + ...+ p*_m и оптимальную стратегию S_A .  
Для определения оптимальной стратегии S*_B = (q*₁ + q*₂ + ...+ q*_n) следует учесть, что игрок В стремится минимизировать гарантированный выигрыш, т.е. найти  . Переменные q₁ , q₂ , ..., q_n удовлетворяют неравенствам:

(3.15)

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

yj =  qj/v, j = 1, 2, ..., n,

(3.16)

то получим систему  неравенств:

(3.17)

Переменные y_j (1, 2, ..., n) удовлетворяют условию  .  
Игра свелась к следующей задаче  
Определить значения переменных y_j ≥ 0, j = 1, 2, ..., n,  которые удовлетворяют системе неравенств (3.17) и максимизируют линейную функцию

Z' = y1 + y2 + ...+ yn,

(3.18)

Решение задачи линейного  программирования (3.16), (3.17) определяет оптимальную стратегию S*_B = (q*₁ + q*₂ + ...+ q*_n) . При этом цена игры

v =  1 / max, Z' = 1 / min Z

(3.19)

Составив расширенные  матрицы для задач (3.13), (3.14) и (3.17), (3.18), убеждаемся, что одна матрица  получилась из другой транспонированием:

Таким образом, задачи линейного программирования (3.13), (3.14) и (3.17), (3.18) являются взаимно-двойственными. Очевидно, при определении оптимальных  стратегий в конкретных задачах  следует выбрать ту из взаимно-двойственных задач, решение которой менее  трудоемко, а решение другой задачи найти с помощью теорем двойственности. Приведем примеры экономических  задач, которые описываются игровыми моделями т х п и могут быть решены методами линейного программирования.

 

 

Пример 1

Обозначив x_i =  p_i/v, i = 1, 2, 3 и y_j = q_j/v , j = 1, 2, 3, составим две взаимно-двойственные задачи линейного программирования (см. (3.13)-(3.14) и (3.17)-(3.18)).

Пример 2

При решении произвольной конечной игры размера m × n рекомендуется придерживаться следующей схемы:

1. Исключить из платежной матрицы заведомо невыгодные стратегии по сравнению с другими стратегиями. Такими стратегиями для игрока А (игрока В) являются те, которым соответствуют строки (столбцы) с элементами, заведомо меньшими (большими) по сравнению с элементами других строк (столбцов).
2. Определить верхнюю и нижнюю цены игры и проверить, имеет ли игра седловую точку. Если седловая точка есть, то соответствующие ей стратегии игроков будут оптимальными, а цена совпадает с верхней (нижней) ценой.
3. Если седловая точка отсутствует, то решение следует искать в смешанных стратегиях. Для игр размера m × n рекомендуется симплексный метод, для игр размера 2×2, 2×n, n×2 возможно геометрическое решение.

На практике реализация оптимального решения   в смешанных стратегиях может происходить несколькими путями. Первый состоит в физическом смешении чистых стратегий A_i  - в пропорциях, заданных вероятностями p_i .  
Другой путь — при многократном повторении игры — в каждой партии чистые стратегии применяются в виде случайной последовательности, причем каждая из них — с частотой, равной ее вероятности в оптимальном решении.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

30 Типовые задачи  дискретного программирования (задача  о рюкзаке, о назначении, задача  коммивояжера).

задачи дискретного  программирования

Под задачей дискретного программирования (дискретной оптимизации) понимается задача математического программирования  
F(x0) = min f(x), x є G,  
множество допустимых решений которой конечно, т.е. О ≤ |G| = N < ∞, где |G| — число элементов множества G. В силу конечности G все допустимые решения можно пронумеровать: x1, x2, . . . . ., xN, вычислить f(xi), i= 1,2,..., N, и найти наименьшее значение.  
Во многих задачах условия дискретности отделены от других условий, т.е. если х = (х1, х2, ... ,хn), то xj є Gj = (х j 1, хj2, ...,хjki), kj > 2. Поэтому N = = =   > 2n, отсюда видно, что с ростом числа переменных объем вычислительной работы резко возрастает. 

Задача о рюкзаке. Контейнер оборудован m отсеками вместимостью    для перевозки n видов продукции    . Виды продукции характеризуются свойством неделимости, т.е. их можно брать в количестве 0, 1, 2, ... единиц. Пусть   - расход i-го отсека для перевозки единицы j-ой продукции. Обозначим через   полезность единицы j-ой продукции. Требуется найти план   перевозки, при котором максимизируется общая полезность рейса.

Модель задачи примет вид: при ограничениях на вместимости отсеков   условии неотрицательности

  условии целочисленности  - целые  .

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

                                     . 

 

Задача о назначении.Имеет n исполнителей, которые могут выполнять n различных работ. Известна полезность  , связанная с выполнением i-м исполнителем j-й работы  . Необходимо назначить исполнителей на работы так, чтобы добиться максимальной полезности, при условии, что каждый исполнитель может быть назначен только на одну работу и за каждой работой должне быть закреплен только один исполнитель.

Математическая модель задачи примет вид: Каждый исполнитель назначается только на одну работу:

На каждую работу назначается только один исполнитель:

Условия неотрицательности и целочисленности , . 

Задача коммивояжера

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

Математическая модель задачи:    

Условия неотрицательности и целочисленности

, .

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

31 Классификация  математических моделей дискретного  программирования. Сущность методов  дискретной оптимизации

Под задачей дискретного  программирования (дискретной оптимизации) понимается задача математического  программирования

 
F(x0) = min f(x), x є G,

 
множество допустимых решений которой конечно, т.е. О ≤ |G| = N < ∞, где |G| — число элементов множества G. В силу конечности G все допустимые решения можно пронумеровать: x1, x2, . . . . ., xN, вычислить f(xi), i= 1,2,..., N, и найти наименьшее значение.

Во многих задачах условия  дискретности отделены от других условий, т.е. если х = (х1, х2, ... ,хn),

то xj є Gj = (х j 1, хj2, ...,хjki), kj > 2. Поэтому N = =  =   > 2n, отсюда видно, что с ростом числа переменных объем вычислительной работы резко возрастает.

 

Дискретные оптимизационные  задачи

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