Задание: составить модель задачи и на примере ее решения проиллюстрировать свойства двойственных оценок. Рассмотреть задачу по определению оптимального плана выпуска продукции, максимизирующего выручку при известных нормах расхода ресурсов, объемах ресурсов и ценах реализации продукции.
Ниже представлены таблицы, включающие условия и результаты решения задач по вариантам (по аналогии с рис.2.1), в которые включены исходные данные. В строке Maximize даны цены реализации единицы продукции, в строках Constraint 1,2,3,4 записаны нормы расхода ресурсов на производство единицы каждой продукции, в столбце RHS записаны запасы ресурсов (см. таблицу решения примера). Задания выполнять по аналогии рассмотренного примера.
Вариант 1
Вариант 2
Вариант 3
Вариант 4
Вариант 5
Вариант 6
Вариант 7
Вариант 8
Вариант 9
Вариант 10
Задание 3. Элементы теории игр
Краткие теоретические сведения
Теория игр – это теория математических моделей, интересы участников которых различны, причём они достигают своей цели различными путями.
Задачей теории игр является выработка рекомендаций по рациональному образу действий участников игры.
Виды игр: – комбинаторные (например, шахматы),
– азартные (кости, рулетка),
– стратегические (отсутствие информации о действиях противника).
Рассмотрим стратегические игры. Они бывают парными (2 игрока) и множественными (более двух игроков). Наиболее практическое значение имеют парные игры. Обозначим участников игры через А и В.
Под игрой понимается последовательность действий (ходов) игроков А и В, которая осуществляется в соответствии с чётко сформулированными правилами. Правила определяют возможные варианты действий игроков, объём информации каждой стороны о действиях другой, результат игры, к которому приводит соответствующая последовательность ходов.
Результат игры (выигрыш) определяется некоторым числом.
Ходом в теории игр называется выбор одного из предположенных правилами игры действий и его осуществления.
Стратегией игрока называется план, по которому он совершает выбор в любой возможной ситуации и при любой возможной фактической информации. Игрок принимает решения по ходу игры. Теоретически можно предположить, что эти решения приняты игроком заранее. Стратегия игрока – это совокупность этих решений. В зависимости от числа возможных стратегий игры делятся на конечные и бесконечные.
Задачей теории игр является выработка рекомендаций для игроков, т.е. определение для них оптимальной стратегии.
Оптимальной называется стратегия, которая при многократном повторении игры обеспечивает данному игроку максимально возможный выигрыш.
Простейший вид стратегической игры – игра двух лиц с нулевой суммой (сумма выигрышей сторон равна нулю).
Рассмотрим матрицу игры А (платежная матрица)
Строки матрицы соответствуют стратегиям Аi, столбцы – стратегиям Вj
Элемент аij матрицы А – выигрыш игрока А, если он выбрал стратегию Аi, а игрок В выбрал стратегию Вj.
Пусть игрок А выбирает некоторую стратегию Аi, тогда в наихудшем случае (если выбор станет известен игроку В) он получит наименьший выигрыш, равный  аij. Предвидя такую возможность, игрок А должен выбрать такую стратегию, чтобы максимизировать свой минимальный выигрыш.
 . (3.1)
Величина α – гарантированный выигрыш игрока А называется нижней ценой игры. Стратегия Аi0, обеспечивающая получение α, называется максиминной.
Игрок В, выбирая стратегию, исходит из следующего принципа: при выборе некоторой стратегии Вj, его проигрыш не превысит максимума из значений элементов j-го столбца матрицы, т.е. ≤  аij.
Рассматривая множество аij для различных значений j игрок В выберет такое значение j, при котором его максимальный проигрыш β минимизируется.
 (3.2)
Величина β называется верхней ценой игры, а соответствующая выигрышу β стратегия Вjо – минимаксной. Фактический выигрыш игрока А при разумных действиях партнёров ограничен нижней и верхней ценой игры. Если же эти выражения равны, т.е.
 (3.3)
то выигрыш игрока А – вполне определённое число, игра называется вполне определённой, а выигрыш V (3.3) называется значением игры и равен элементу матрицы аi0j0. Вполне определённые игры называются играми с седловой точкой. Элемент аi0j0 в матрице такой игры является одновременно минимальным в строке i0, максимальным в столбце j0 и называется седловой точкой.
Седловой точке соответствуют оптимальные стратегии игроков, их совокупность является решением игры.
Пример. Определить нижнюю и верхнюю цены для игр, заданных платёжными матрицами А1 и А2
 ,  .
Решение. Минимальные значения аij в строках матрицы А1 равны соответственно 2, 3, 1. Максимальное значение из них равно 3. Следовательно, α1 = 3 – нижняя цена игры, которой соответствует матрица А1.
Для определения верхней цены матрица найдём максимальные значения элементов в столбцах матрицы. По столбцам имеем (4, 5, 6, 5). Следовательно, β1 = 4.
Для матрицы А2
α2 = max (0, 2, – 1) = 2,
β2 = min (3, 2, 4, 5) = 2.
Таким образом, α2 = β2 = V = 2 – цена игры. Решение данной игры состоит в выборе игроком А стратегии А2, при этом его выигрыш не меньше 2; для игрока В оптимальной является стратегия В2, позволяющая ограничит его проигрыш этим же числом. А2 и В2 в этом случае называются чистыми стратегиями, а22 – седловая точка матрицы А2.
Для матриц, которые не содержат седловой точки α < β. В этом случае игроки применяют не одну, а несколько стратегий. Выбор стратегий осуществляется случайным образом. Случайный выбор игроком своих стратегий называется смешанной стратегией.
Применение игроком А оптимальной стратегии Х* должно обеспечить ему при любых действиях игрока В выигрыш, не меньший цены игры V. Поэтому выполняются соотношения
 . (3.4)
Аналогично для игрока В оптимальная стратегия У* должна обеспечит при любых стратегиях игрока А проигрыш, не превышающий величину V, т.е. справедливо соотношение
 (3.5)
В дальнейшем соотношения (3.4) и (3.5) используются для решения игры.
Рассмотрим сведение матричной игры к задаче линейного программирования.
Пусть платёжная матрица игры
Матрица не содержит седловой точки, поэтому решение игры представлено в смешанных стратегиях х = (х1, х2, …, хm), у = (у1, у2, …, уn). При оптимальной стратегии игрока А выполняется условие (3.4), а оптимальной стратегии игрока В удовлетворяет условие (3.5). Таким образом, можно рассматривать задачу отыскания оптимальной стратегии игрока А, для которой выполняются следующий ограничения:
 (3.6)
Величина V (цена игры) неизвестна, однако можно считать, что V > 0. Последнее условие выполняется всегда, если элементы матрицы неотрицательны, а этого можно достигнуть, прибавляя ко всем элементам матрицы некоторое положительное число.
Преобразуем систему ограничений, разделив все члены неравенств на V. В результате получим
 (3.7)
где ti = xi / V, 
Из условия x1 + x2 + …+xm = 1 следует
 (3.8)
Решение игры должно максимизировать значение V, следовательно функция 
Таким образом, получена задача линейного программирования.
 при ограничениях (3.7) и дополнительных условиях ti ≥ 0. Решая её, находим ti и величину  далее получаем значение xi = Vti.
Для определения стратегии игрока В запишем следующие условия:
 (3.9)
Разделив все члены неравенств на V, получим
 (3.10)
где uj = yj / V,  . Переменные u1, u2, …, un должны быть выбраны так, чтобы выполнялись условия (3.10) и достигался максимум функции
 (3.11)
Таким образом, для решения игры имеет пару двойственных симметричных задач линейного программирования. Используя свойство симметричности, можно решить одну из них, требующую меньших вычислений, а решение второй задачи найти на основании оптимального плана двойственной.
Пример. Найти решение игры, заданной матрицей
Решение. Для матрицы А α = 1, β = 3. Матрица не имеет седловой точки.
Составим симметричные двойственные задачи
Задача 1 Задача 2
min Z = t1 + t2 max W = u1 + u2
 
Задачу 2 приведём к канонической и решим симплексным методом.
-
Сi
|
Баз
|
аi 0
|
u1
|
u2
|
u3
|
u4
|
θ
|
0
|
u3
|
1
|
1
|
3
|
1
|
0
|
1
|
0
|
u4
|
1
|
2
|
1
|
0
|
1
|
½
|
|
W
|
0
|
–1
|
– 1
|
0
|
0
|
|
0
|
u3
|
½
|
0
|
5/2
|
1
|
–½
|
1/5
|
1
|
u1
|
½
|
1
|
½
|
0
|
½
|
1
|
|
W
|
½
|
0
|
–1/2
|
0
|
½
|
|
1
|
u2
|
1/5
|
0
|
1
|
2/5
|
–1/5
|
|
1
|
u1
|
2/5
|
1
|
0
|
–1/5
|
3/5
|
|
|
W
|
3/5
|
0
|
0
|
1/5
|
2/5
|
≥ 0 вып
|
|
|
|
|
|
t1
|
t2
|
|
 ,  ,
uj = yj / V, yj = uj · V,  , 
ti = xi / V, xi = ti · V, 
3.1. Варианты заданий к задаче 3
1. А= . 6. А= .
 
 
 
 
Задание 4. Корреляционно–регрессионный анализ
Краткие теоретические сведения
Значения социально–экономических показателей формируются под влиянием различных факторов, главных и второстепенных, взаимосвязанных между собой и действующих нередко в разных направлениях. Поэтому, кроме локального изучения таких показателей (их уровней, характера изменчивости, распределения и т.д.), важной задачей при принятии решений является изучение связей между различными показателями.
Одним из методов изучения таких взаимосвязей является корреляционный и регрессионный анализ.
Корреляционным анализом называется совокупность приемов, с помощью которых исследуются и обобщаются взаимосвязи корреляционно связанных величин. Мерой тесноты линейной корреляционной связи служит коэффициент корреляции Пирсона. Оценкой коэффициента парной (простой) линейной корреляции служит выборочный коэффициент парной корреляции:
 ,
где  – выборочные средние величины для x и y, а суммирование ведется по всем элементам выборки.
Известно, что –1 rxy 1.
При rxy > 0 имеем прямую корреляционную связь, т. е. с ростом значения одной переменной растет среднее значение другой, а при rxy < 0 – обратную – с ростом значения одной переменной среднее значение другой убывает. Если rxy = 0, то это означает отсутствие линейной корреляционной связи, а если rxy = 1, то это означает наличие между переменными линейной, функциональной связи (прямой в случае rxy = +1 и обратной в случае rxy = – 1).
Оценивая значение коэффициента корреляции по выборочным данным, мы должны быть уверены в надежности такой оценки. Обычно это осуществляется с помощью проверки гипотезы H0:  = 0 на основе критерия Стьюдента:  с n – 2 степенями свободы (– теоретическое значение коэффициента корреляции, вычисленное по всем элементам генеральной совокупности). Если расчетное значение этого критерия окажется больше критического (определяемого по таблице значений t-статистики), то нулевая гипотеза о равенстве нулю теоретического значения коэффициента корреляции отклоняется. При компьютерных расчетах вместе с оценками коэффициентов корреляции обычно рассчитываются и выборочные уровни значимости для статистик Стьюдента. Если расчетное значение уровня значимости (по-другому – р-величина) для какого-либо выборочного коэффициента корреляции окажется больше фиксированного уровня значимости, например 0,05, то гипотеза Ho не отклоняется, и в этом случае говорят, что коэффициент корреляции не значимо отличен от нуля, и, следовательно, линейная корреляционная связь между соответствующими переменными отсутствует. В противном случае говорят, что коэффициент корреляции значимо отличен от нуля, что означает наличие линейной корреляционной связи между соответствующими переменными.
4.1. Задача анализа матрицы парных коэффициентов корреляции
Количественное описание связи корреляционно связанных величин осуществляется на основе регрессионного анализа. Одной из предпосылок регрессионного анализа является предпосылка независимости объясняющих переменных. Ясно, что это практически не выполнимо, но уж совсем нежелательно, чтобы между независимыми переменными наблюдалась тесная корреляционная взаимосвязь. В этом случае говорят о коллинеарности переменных. Считается, что две случайные переменные коллинеарные, если коэффициент корреляции между ними не менее 0,7. Если таких переменных несколько, то говорят о мультиколлинеарности. Мультиколлинеарность – нежелательное явление в регрессионном анализе, и ее выявление является одной из задач анализа матрицы парных коэффициентов корреляции.
Матрица парных коэффициентов корреляции состоит из коэффициентов корреляции, рассчитанных для набора переменных y, x1, x2,…, xm и размещенных в виде матрицы. В дальнейшем переменную y будем называть зависимой, а остальные – независимыми. Поскольку rxy = ryx, то корреляционная матрица симметрична относительно главной диагонали. Поэтому естественно анализировать только одну из частей корреляционной матрицы (верхнюю или нижнюю относительно главной диагонали). Пусть корреляционная матрица R имеет вид:
y x1 x2 … xm
 .
Договоримся в дальнейшем анализировать верхнюю часть матрицы. Первая строка матрицы содержит коэффициенты корреляции между зависимой переменной y и независимыми переменными х1, х2, …, xm. Коэффициенты этой строки анализируют с целью выявления значимых и незначимых независимых переменных. Значимость независимой переменной здесь понимается с точки зрения влияния ее на зависимую переменную. Если проверка гипотезы Н0:  = 0 покажет, что коэффициент корреляции незначимо отличен от нуля, то это означает, что соответствующая независимая переменная не значимо влияет на зависимую переменную, т.е. незначима, и является кандидатом на исключение из регрессии. Второй этап анализа матрицы парных коэффициентов корреляции заключается в выявлении мультиколлинеарности среди независимых переменных. Для этого просматривается оставшаяся часть матрицы R (кроме первой строки) и выделяются коэффициенты, по величине 0,7. Они и укажут на коллинеарные переменные. Обычно в уравнение регрессии коллинеарные переменные не включаются.
4.2. Уравнение линейной регрессии
Если в регрессионном анализе рассматривается пара переменных, одна зависимая и одна независимая, то говорят о простой (парной) регрессии. Если независимых переменных более одной, то говорят о множественной регрессии.
В дальнейшем будем рассматривать только линейную регрессию. Пусть рассматривается совокупность переменных y, x1, x2, … , xm, причем, будем считать, что y – зависимая переменная, а x1, x2, … , xm – независимые. Для этих переменных уравнение множественной линейной регрессии (как оценка модели) может быть записано так:
y = a + b1x1 + b2x2 + …+ bmxm + е,
где а – оценка свободного члена уравнения регрессии;
bk – оценки коэффициентов регрессии при переменных xk;
е – отклонения фактических значений зависимой переменной от расчетных.
Если расчетные значения обозначить через  , то
= a + b1x1 + … + bmxm .
Тогда: y = + е или е = y – . В дальнейшем е будем называть остатками.
Итак, а и bk (k =  ) – оценки параметров уравнения регрессии, получаемые обычно на основе метода наименьших квадратов (МНК).
Свободный член уравнения регрессии обычно не интерпретируется. Коэффициенты уравнения регрессии показывают, на сколько в среднем изменится значение зависимой переменной (в своих единицах измерения), если значение соответствующих независимых переменных изменится на единицу (в своих единицах измерения) при фиксированных значениях других независимых переменных. Но это так, если выполняется основная предпосылка регрессионного анализа, т.е. если объясняющие переменные не зависят между собой. Иначе, смысл этих коэффициентов искажается. В случае же мультиколлинеарности коэффициенты уравнения регрессии вообще теряют какой-либо смысл.
Сопоставимость коэффициентов уравнения регрессии в случае разных единиц измерения достигается при рассмотрении стандартизованного уравнения регрессии:
y0 = 1x10 + 2x20 + … + mxm0 + е ,
где y0 и x0k – стандартизованные значения переменных y и xk:
где Sy и S – стандартные отклонения переменных y и xk, а k – –коэффициенты уравнения регрессии. -коэффициенты показывают, на какую часть своего стандартного отклонения Sy в среднем изменится зависимая переменная y, если независимая переменная xk изменится на величину своего стандартного отклонения S (при прочих равных условиях). Оценки параметров уравнения регрессии в абсолютных показателях (bk) и β-коэффициентов связаны соотношениями:
 .
При анализе воздействия на моделируемый признак показателей, включенных в уравнение регрессии, наравне с -коэффициентами используются также коэффициенты эластичности:
которые показывают, на сколько процентов в среднем изменится зависимая переменная, если соответствующая независимая переменная изменится на один процент (при прочих равных условиях).
4.3. Оценка точности уравнения регрессии
Как уже отмечалось, оценки параметров уравнения регрессии вычисляются по выборочным данным и лишь приближенно оценивают эти параметры. В связи с этим появляется необходимость оценить точность как уравнения регрессии в целом, так и его параметров в отдельности. При решении первой задачи используют процедуру дисперсионного анализа, основанную на разложении общей суммы квадратов отклонений зависимой переменной:  на две составляющие, источниками которых являются отклонения за счет регрессионной зависимости (SSR) и за счет случайных ошибок (SSE), причем
 Как известно, SST = SSR + SSE или
Аналогичное разложение имеет место и для степеней свободы соответствующих сумм:
dfT = dfR + dfE ,
где dfT = n – 1 – общее число степеней свободы;
dfR = m – число степеней свободы, соответствующее регрессии (m – число независимых переменных в уравнении регрессии);
dfE = n – m – 1 – число степеней свободы, соответствующее остаткам.
Разделив соответствующие суммы квадратов на степени свободы, получим средние квадраты или оценки дисперсии  , которые сравниваются по критерию Фишера ( ). При этом проверяется гипотеза о равенстве нулю одновременно всех коэффициентов регрессии против альтернативной гипотезы: не все коэффициенты регрессии равны нулю. Если F /2,m,n-m-1 > F, т. е. табличное значение критерия больше расчетного, то уравнение регрессии значимо, т.е. не все коэффициенты уравнения регрессии равны нулю, в противном случае уравнение регрессии не значимо. В этом случае уравнение регрессии ничего не дает для предсказания зависимой переменной и не может быть использовано в анализе.
При компьютерных расчетах вместе со статистикой Фишера рассчитывается р-величина, которую сравнивают с фиксированным уровнем значимости и на этой основе делают вывод о значимости уравнения регрессии. Если р-величина меньше фиксированного уровня значимости, то уравнение регрессии значимо.
Дисперсионный анализ регрессии проводится в таблице вида:
Таблица 4.1.
|
