Проверка полученного результата

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

у₁ + х₁ ³ d₁ у₂ + х₂ ³ d₂ у₃ + х₃ ³ d₃

4 + 1 ³ 5 0 + 1 ³ 1 0 + 2 ³ 2

и что суммарный объем производства и имевшегося к началу первого этапа запаса продукции равен суммарной потребности

у₁ + х₁ + х₂ + х₃ = d₁ + d₂ + d₃

4 + 1 + 1 + 2 = 5 + 1 + 2

8 = 8

причем это достигается при наименьших возможных затратах на производство и хранение продукции

j(х₁) + j(х₂) + j(х₃) + h₁у₂ + h₂у₃ = F₃(y₄=0)

8 + 8 + 14 + 2 * 0 + 1 * 0 = 30

30 = 30

Матричная модель сотрудничества и конкуренции

Постановка задачи

Рассмотреть матричную игру как модель сотрудничества и конкуренции. Найти графическое решение игры. Указать, как проявляется конкуренция между игроками и сотрудничество между ними.

Исходные данные

		-2

Решение

Сведем данный случай матричной игры (2*4) к анализу игры 2*2. Для этого необходимо графическое решение (см. Рисунок 3).

Рисунок 3

Как видно из Рисунка 3, данная матричная игра сводится к варианту

Рассчитаем оптимальные стратегии игроков P* и Q*:

p^*₁ = (a₂₂ - a₂₁) / (a₁₁ + a₂₂ - a₁₂ - a₂₁) = (0 - 3) / (0 + 0 – 2 – 3) = 3/5

p^*₂ = (a₁₁ - a₁₂) / (a₁₁ + a₂₂ - a₁₂ - a₂₁) = (0 - 2) / (0 + 0 – 2 – 3) = 2/5

q^*₁ = (a₂₂ - a₁₂) / (a₁₁ + a₂₂ - a₁₂ - a₂₁) = (0 - 2) / (0 + 0 – 2 – 3) = 2/5

q^*₂ = (a₁₁ - a₂₁) / (a₁₁ + a₂₂ - a₁₂ - a₂₁) = (0 - 3) / (0 + 0 – 2 – 3) = 3/5

P* = (3/5, 2/5)

Q* = (2/5, 3/5)

Рассчитаем цену игры v:

_{n m}

v = S S a_ij * p_i * q_j = 0 * 3/5 * 2/5 + 3 * 2/5 * 2/5 + 2 * 3/5 * 3/5 + 0 * 2/5 * 3/5 = 6/5

^{j=1 i=1}

Рассчитаем среднюю дисперсию и риск:

_{n m n m n m}

D* = S S a_ij² * p^*_i * q^*_j - (S S a_ij * p^*_i * q^*_j)² = S S a_ij² * p^*_i * q^*_j - v² =

^{j=1 i=1 j=1 i=1 j=1 i=1}

= 0 * 3/5 * 2/5 + 9 * 2/5 * 2/5 + 4 * 3/5 * 3/5 + 0 * 2/5 * 3/5 – 36/25 = 36/25

r = Ö D* = Ö 36/25 = 6/5 = 1.2

Рассчитаем риски игры r для Первого и Второго игроков:

_n

D_j = S a_i² * p^*_i - v²

ⁱ⁼¹

D₁ = 0 * 3/5 + 9 * 2/5 – 36/25 = 54/25

D₂ = 4 * 3/5 + 0 * 2/5 – 36/25 = 24/25

r₁⁽¹⁾ = Ö 54/25 = 1.47

r₁⁽²⁾ = Ö 24/25 = 0.98

Зависимость риска Первого в малой окрестности его оптимальной стратегии показана на Рисунке 4.

r₁⁽²⁾ = 0.98 r = 1.2 r₁⁽¹⁾ = 1.47

6/5

Рисунок 4

Как видно из Рисунка 4, при отходе Первого от своей оптимальной стратегии вправо, т.е. при увеличении вероятности выбора им 1-ой строки, Второй отвечает своей 1-ой чистой стратегией и риск Первого скачком увеличивается до r₁⁽¹⁾ = 1.47, а при отходе Первого от своей оптимальной стратегии влево Второй отвечает своей 2-ой чистой стратегией и риск Первого скачком снижается до r₁⁽²⁾ = 0.98.

Аналогично - в отношении второго:

_n

D_i = S a_j² * q^*_j - v²

^j=1

D₁ = 0 * 2/5 + 4 * 3/5 – 36/25 = 24/25

D₂ = 9 * 2/5 + 0 * 3/5 – 36/25 = 54/25

r₂⁽¹⁾ = Ö 24/25 = 0.98

r₂⁽²⁾ = Ö 54/25 = 1.47

Зависимость риска Второго в малой окрестности его оптимальной стратегии показана на Рисунке 5.

r₂⁽¹⁾ = 0.98 r = 1.2 r₂⁽²⁾ = 1.47

6/5

Рисунок 5

Как видно из Рисунка 5, при отходе Второго от своей оптимальной стратегии вправо, т.е. при увеличении вероятности выбора им 1-го столбца, Первый отвечает своей 2-ой чистой стратегией и риск Второго скачком увеличивается до r₂⁽²⁾ = 1.47, а при отходе Второго от своей оптимальной стратегии влево его риск скачком снижается до r₂⁽¹⁾ = 0.98.

Величина r^* = min(r₁⁽¹⁾, r₁⁽²⁾, r₂⁽¹⁾, r₂⁽²⁾) - риск всей игры.

r^* = min(1.47, 0.98, 0.98, 1.47) = 0.98.

С таким риском можно играть только при сотрудничестве обеих сторон. Для достижения такого риска игроки должны играть следующим образом: Первый игрок использует свою оптимальную стратегию P^*(3/5, 2/5), а Второй отвечает своей 2-ой чистой стратегией, либо Второй игрок использует свою оптимальную стратегию Q^*(2/5, 3/5), а Первый отвечает своей 1-й чистой стратегией.

Задача о максимальном потоке в сети

Постановка задачи

Рассмотреть задачу о максимальном потоке в сети. Решить конкретную задачу на сети с 8-9 вершинами.

Исходные данные

Определить максимальный поток в сети, изображенной на Рисунке 6 из вершины x₀ в вершину x₈, где числа на дугах, снабженные стрелками, означают пропускные способности этих дуг в указанных направлениях.

Рисунок 6

Решение

Составим матрицу пропускных способностей дуг данной сети и представим сеть в матричной форме (см. Таблицу 1).

Таблица 1

xj xi	x0	x1	x2	x3	x4	x5	x6	x7
x0				2-
x1
x2
x3	+							6-
x4
x5
x6
x7				+

В качестве начального возьмем нулевой поток z⁰_ij = 0. Найдем какой-нибудь путь, идущий из x₀ в x₇ по ненасыщенным дугам. Для этого в нулевой строке таблицы выберем какой-нибудь элемент c_ij, отличный от нуля, например c₀₃. Из вершины x₀ можно перейти в x₃. Для наглядности дугу (x₀, x₃) проведем прямо в нулевой строке таблицы из нулевого столбца в 3-й. Теперь мы находимся в вершине x₃. Чтобы зафиксировать это, сместимся по пятому столбцу до строки с тем же 3-м номером. В 3-й строке имеется 3 ненулевых элемента соответственно в 4-м, 5-м и 7-м столбцах. Это означает, что из x₃ можно перейти или в x₄, в x₅ или в x₇. Пойдем в сток x₇. Этот переход изображен стрелкой в 3-й строке с началом в 3-м столбце и концом в 7-м. Таким образом, по таблице пропускных способностей дуг сети мы нашли путь, ведущий по ненасыщенным дугам из источника в сток:

m₁ = [x₀, x₃, x₇].

Теперь по таблице надо узнать пропускную способность q₁ найденного пути и уменьшить пропускные способности всех дуг этого пути на q₁, а симметричных им дуг – увеличить на q₁. Для этого отмечаем знаком «-» числа в тех клетках, где находятся концы дуг, а числа в клетках, симметричных указанным относительно главной диагонали, отмечаем знаком «+». Пропускная способность найденного пути, очевидно, равна наименьшему среди чисел, отмеченных знаком «-» (Таблица 1).

q₁ = 2

Из всех чисел, отмеченных знаком «-», вычитаем наименьшую пропускную способность q₁. Получаем Таблицу 2. Это – сеть с измененными пропускными способностями дуг.

Таблица 2

xj xi	x0	x1	x2	x3	x4	x5	x6	x7
x0			4-
x1
x2	+				3-
x3
x4			2+					5-
x5
x6
x7					5+

Ищем новый путь, идущий из источника в сток по ненасыщенным дугам и процедуру повторяем. Получаем путь m₂ и пропускную способность q₂:

m₂ = [x₀, x₂, x₄, x₇]

q₂ = 3

Далее

Таблица 3

xj xi	x0	x1	x2	x3	x4	x5	x6	x7
x0		2-
x1	+					5-
x2
x3
x4
x5		4+					3-
x6						2+		8-
x7							2+

m₃ = [x₀, x₁, x₅, x₆, x₇]

q₃ = 2

Таблица 4

xj xi	x0	x1	x2	x3	x4	x5	x6	x7
x0
x1
x2
x3
x4
x5
x6
x7

Из Таблицы 4 видно, что не существует ни одного пути из источника в сток. (Из x₀ можно перейти только в x₂, а оттуда – обратно в x₀). Следовательно, увеличить поток нельзя.

Для определения величины полученного максимального потока вычитаем из элементов Таблицы 1 соответствующие элементы Таблицы 4. Записывая только положительные из найденных разностей, получаем Таблицу 5, указывающую максимальный поток в заданной сети с величиной

w* = z₃₇ + z₄₇ + z₆₇ = q₁ + q₂ + q₃ = 7

Таблица 5

xj xi	x0	x1	x2	x3	x4	x5	x6	x7
x0
x1
x2
x3
x4
x5
x6
x7

Список литературы

Карандаев И.С. и др. Математические методы исследования операций в примерах и задачах: Учебное пособие / ГАУ. М., 1993, 72 с.

Карандаев И.С., Юнисов Х.Х. Прикладные задачи исследования операций. Учебное пособие для студентов всех специальностей. М.: МИУ имени Серго Орджоникидзе. – 79 с.

Математические методы принятия решений в экономике: Учебник / Под ред. В.А. Колемаева / ГУУ. – М.: ЗАО «Финстатинформ», 1999. – 386 с.

Методические указания к выполнению курсовой работы по дисциплине “Прикладная математика” / Сост.: Колемаев В.А., Карандаев И.С., В.И. Малыхин, Т.М. Гатауллин, Ю.Г. Прохоров, Х.Х. Юнисов; ГУУ, М., 2000. 73 с.