Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
§1. ЦЕЛИ И ЗАДАЧИ КУРСОВОГО ПРОЕКТА
Выполнение курсового проекта по прикладной математике направлено на усиление связи обучения студентов с практикой совершенствования управления, организации современного производства, всего механизма хозяйствования.
В процессе работы над курсовым проектом студент не только закрепляет и углубляет теоретические знания, полученные на лекциях и на практических занятиях, но и учится применять методы исследования операций при постановке и решении конкретных экономических задач.
Цель курсового проекта - подготовить студента к самостоятельному проведению операционного исследования, основными этапами которого являются построение математической модели, решение управленческой задачи при помощи модели и анализ полученных результатов.
1. Линейная производственная задача
Задача о рациональном использовании производственных мощностей является одной из первых задач, для решения которой были применены методы линейного программирования. В общем виде математическая модель задачи об использовании производственных мощностей может быть получена следующим образом.
Предположим, что предприятие или цех выпускает n видов изделий, имея m групп оборудования. Известны нормы времени на обработку каждого изделия на каждой группе оборудования, например, в минутах или часах и фонд времени работы каждой группы оборудования. Пусть, кроме того, известно, что из всех n видов изделий наибольшим спросом пользуются k видов. Требуется составить план производства, при котором выпуск дефицитных изделий будет наибольшим возможным.
Примем следующие обозначения:
i – номер группы оборудования (i=1,2, … , m);
j – номер вида изделия (j=1,2, … , n);
aij – норма времени на обработку единицы i-го изделия на j-ой группе оборудования;
bi – действительный фонд времени работы i-й группы оборудования;
xi – планируемое количество единиц j-го изделия;
(x1, x2, … , xn) – искомый план производства.
Исходные параметры задачи представлены в виде технологической матрицы A затрат ресурсов на единицу продукции каждого вида, вектора B объемов ресурсов и вектора C удельной прибыли:
2 3 0 4 148
A = 4 1 5 0 B= 116 C=(30 25 14 12)
0 2 4 3 90
x1,x2,x3,x4>=0
Составим функция прибыли (целевую функцию):
Z=30x1+25x2+14x3+12x4
Необходимо составить производственную программу (х1, х2, …, хn) так, чтобы функция Z приняла наибольшее значение при выполнении всех других условий:
2x1+3x2+ 4x4<=148 1 вид ресурса
4x1+ x2+5x3 <=116 2 вид ресурса (1)
2x2+4x3+3x4<=90 3 вид ресурса
Неравенства (1) нужно превратить в равенства. Для этого вводим дополнительные неотрицательные неизвестные x5, x6, x7≥0.
Решим задачу с помощью симплексной таблицы:
|
Ć |
Базис |
Н |
X1=30 |
X2=25 |
X3=14 |
X4=12 |
X5 |
X6 |
X7 |
α |
β |
Пояснения |
|
0 |
X5 |
148 |
2 |
3 |
0 |
4 |
1 |
0 |
0 |
74 |
1/2 |
Z0=Ć*H j=Ć*Gj-Cj min(j<0)= -30 min(α)=29 |
|
0 |
X6 |
116 |
4 |
1 |
5 |
0 |
0 |
1 |
0 |
29 |
1 |
|
|
0 |
X7 |
90 |
0 |
2 |
4 |
3 |
0 |
0 |
1 |
∞ |
0 |
|
|
Z0-Z |
0-Z |
-30 |
-25 |
-14 |
-12 |
0 |
0 |
0 |
-15/2 |
|||
|
0 |
X5 |
90 |
0 |
5/2 |
-5/2 |
4 |
1 |
-1/2 |
0 |
36 |
1 |
min(j<0)= -35/2 min(α)=36 |
|
30 |
X1 |
29 |
1 |
1/4 |
5/4 |
0 |
0 |
1/4 |
0 |
116 |
1/10 |
|
|
0 |
X7 |
90 |
0 |
2 |
4 |
3 |
0 |
0 |
1 |
45 |
4/5 |
|
|
Z0-Z |
870-Z |
0 |
-35/2 |
47/2 |
-12 |
0 |
15/2 |
0 |
-7 |
|||
|
25 |
X2 |
36 |
0 |
1 |
-1 |
8/5 |
2/5 |
-1/5 |
0 |
Все j≥0 |
||
|
30 |
X1 |
20 |
1 |
0 |
3/2 |
-2/5 |
-1/10 |
3/10 |
0 |
|||
|
0 |
X7 |
18 |
0 |
0 |
6 |
-1/5 |
-4/5 |
2/5 |
1 |
|||
|
Z0-Z |
1500-Z |
0 |
0 |
6 |
16 |
7 |
4 |
0 |
Формулы расчета:
|
α1=148/2=74 α2=116/4=29 α3=0/90=∞ |
β1=2/4=1/2 β2=4/4=1 β3=0/4=0 β4=-30/4=-15/2 |
α1′=90*2/5=36 α2′=29*4=116 α3′=90/2=45 |
β1′=5/2*2/5=1 β2′=1/4*2/5=1/10 β3′=2*2/5=4/5 β4′=-35/2*2/5= -7 |
|
A1j′= A1j – β1* A2j A2j′= A2j/4 A3j′= A3j – β3* A2j A4j′= A4j – β4* A2j |
A1j′′= A1j′/4 A2j′′= A2j′ – β2′* A1j′ A3j′′= A3j′ – β3′* A1j′ A4j′′= A4j′ – β4′* A1j′ |
||
|
B1′= B1– β1* B2=148–116/2=90 B2′= B2/4=116/4=29 B3′= B3– β3* B2=90–0*116=90 B4′= B4– β4* B2=0+116*15/2=870 |
B1′′= B1′*2/5=90*2/5=36 B2′′= B2′– β2′* B1′=29-90/10=20 B3′′= B3′– β3′* B1′=90-90*4/5=18 B4′′= B4′– β4′* B1′=870+7*90=1500 |
Рассчитываем таблицу до тех пор пока все j не станут неотрицательными. Экономический смысл последней строки: например, 3=6 – если произвести одну единицу продукции 3-го вида (она не входит в оптимальную производственную программу), то прибыль уменьшится на 6 единиц. Вектор Н(36,20,18) показывает, что надо произвести 36 единиц 1-го продукта, 20 единицы 2-его продукта, 3-ий и 4-ый продукт вообще не производить; при этом остатки ресурсов:
Первого вида x5=0
Второго вида x6= 0
Третьего вида x7=18
…и прибыль будет равна Z=30*20 + 25*36= 1500.
Обращенный базис
2/5 -1/5 0
Q-1 = -1/10 3/10 0
-4/5 2/5 1
проверить, что
Н= Q-1*B
36 148 2/5 -1/5 0 36
H= 20 B 116 * Q-1 -1/10 3/10 0 =H 20
18 90 -4/5 2/5 1 18
Двойственная задача
Ранее мы рассмотрели конкретную линейную производственную задачу по выпуску четырех видов продукции с использованием трех видов ресурсов по заданным технологиям.
Теперь представим себе, что возникла новая ситуация. Знакомый предприниматель П (Петров), занимающийся производством каких-то других видов продукции, но с использованием трех таких же видов ресурсов, какие имеются у нас, предлагает нам "уступить" по определенным ценам все имеющиеся у нас ресурсы и обещает платить у1 рублей за каждую единицу первого ресурса, у2 руб – второго, у3 руб – третьего. Возникает вопрос: при каких ценах у1, у2, у3 мы можем согласиться с предложением П.
Величины у1, у2, у3 принято называть расчетными, или двойственными, оценками ресурсов. Они прямо зависят от условий, в которых действует наше предприятие.
Напомним, что в нашей задаче технологическая матрица А, вектор объемов ресурсов В и вектор удельной прибыли С имели вид
2 3 0 4 148
A = 4 1 5 0 B= 116 C=(30 25 14 12)
0 2 4 3 90
Для производства единицы продукции первого вида мы должны затратить, как видно из матрицы А, 3 единицы ресурса первого вида, 6 единицы ресурса второго вида и 2 единицы третьего (элементы первого столбца матрицы). В ценах у1, у2, у3 наши затраты составят 2у1 + 4у2 + 0у3, т.е. столько заплатит предприниматель П за все ресурсы, идущие на производство единицы первой продукции. На рынке за единицу первой продукции мы получили бы прибыль 30 руб. Следовательно, мы можем согласиться с предложением П только в том случае, если он заплатит не меньше
2у1 + 4у2 + 0у3 30.
Аналогично, во втором столбце матрицы А указаны затраты различных ресурсов на производство единицы продукции второго вида. В ценах П эти затраты составят 3у1 + 1у2 + 2у3, а на рынке за единицу продукции второго вида мы получили бы прибыль 25 рублей. Поэтому перед предпринимателем П мы ставим условие
3у1 + 1у2 + 2у3 25
и т.д. по всем видам продукции.
Учтем, что за все имеющиеся у нас ресурсы нам должны заплатить
148у1 + 116у2 + 90у3 рублей. При поставленных нами условиях предприниматель П будет искать такие значения величин у1, у2, у3, чтобы эта сумма была как можно меньше. Подчеркнем, что здесь речь идет не о ценах, по которым мы когда-то приобретали эти ресурсы, а об этих ценах, которые существенно зависят от применяемых нами технологий, объемов ресурсов и от ситуации на рынке.
Таким образом, проблема определения расчетных оценок ресурсов приводит к задаче линейного программирования: найти вектор двойственных оценок
у(у1, y2, y3)
минимизирующий общую оценку всех ресурсов
W= 148y1 + 116y2 + 90y3 (1)
при условии, что по каждому виду продукции суммарная оценка всех ресурсов, затрачиваемых на производство единицы продукции, не меньше прибыли, получаемой от реализации единицы этой продукции
2у1 + 4у2 30
3у1 + 1у2 + 2у3 25
5у2 + 4у3 14 (2)
4y1 + 3y3 12
причем оценки ресурсов не могут быть отрицательными
y10, y20, y30. (3)
Решение полученной задачи легко найти с помощью второй основной теоремы двойственности, согласно которой для оптимальных решений (х1, х2, х3, х4) и (y1, y2, y3) пары двойственных задач необходимо и достаточно выполнение условий
х1 (2у1 + 4у2 -30) = 0 y1 (2x1+3x2+ 4x4-148) = 0
х2 (3у1 + 1у2 + 2у3- 25) = 0 y2 (4x1+ x2+5x3 -116) = 0
х3 ( 5у2 + 4у3- 14) = 0 y3 ( 2x2+4x3+3x4- 90) = 0 .
х4 (4y1 + 3y3 - 12) = 0
Ранее было найдено, что в решении исходной задачи x1>0, x2>0. Поэтому
2у1 + 4у2 -30= 0
3у1 + 1у2 + 2у3- 25 = 0
Если же учесть, что третий ресурс был избыточным и, согласно той же теореме двойственности, ее двойственная оценка равна нулю
y3=0,
то приходим к системе уравнений
2y1+4y2=30
3y1+y2=25
откуда следует
y1=7,y2=4
Таким образом, получили двойственные оценки ресурсов
у1=7; у2=4; у3=0, (4)
причем общая оценка всех ресурсов равна
W= 148y1 + 116y2 +90y3=1036+464+0=1500.
Заметим, что решение (4) содержалось в последней строке последней симплексной таблицы исходной задачи. Важен экономический смысл двойственных оценок. Например, двойственная оценка второго ресурса у1=7 показывает, что добавление одной единицы первого ресурса обеспечит прирост прибыли в 7 единиц.
Задача о "расшивке узких мест производства"
При выполнении оптимальной производственной программы первый и второй ресурсы используются полностью, т.е. образуют узкие места производства. Будем их заказывать дополнительно. Пусть T(t1,t2,t3)- вектор дополнительных объемов ресурсов. Так как мы будем использовать найденные двойственные оценки ресурсов, то должно выполняться условие
H + Q-1T 0.
Задача состоит в том, чтобы найти вектор
T (t1, t2, 0),
максимизирующий суммарный прирост прибыли
W = 7t1 + 4t2 (1)
при условии сохранения двойственных оценок ресурсов (и, следовательно, структуры производственной программы)
36 2/5 -1/5 0 t1
20 + -1/10 3/10 0 t2 ≥0 (2)
18 -4/5 2/5 1 0
предполагая, что можно надеяться получить дополнительно не более 1/3 первоначального объема ресурса каждого вида
t1 148
t2 ≤1/3* 116 (3)
0 90
причем по смыслу задачи t1,t2≥0. (4)
Переписав неравенства (2) и (3) в виде:
-2/5*t1 +1/5*t2<=36
1/10*t1-3/10*t2<=20 (5)
4/5*t1-2/5*t2<=18
t1<=148/3 ; t2<=116/3 (6)
приходим к задаче ЛП: максимизировать (1) при условиях (5), (6) и (4). Эту задачу решаем графически
|
I |
|||||||||||||||||||||||||||||||||||
|
III |
|||||||||||||||||||||||||||||||||||
|
II |
|||||||||||||||||||||||||||||||||||
Программа «расшивки» имеет вид:
t1=41 5/6 , t2= 38 2/3 , t3=0 и прирост прибыли составит W = 7t1 + 4t2 = 447 ½ .
Сводка результатов приведена в таблице:
|
Cj |
30 |
25 |
14 |
12 |
b |
x4+i |
yi |
ti |
|
2 |
3 |
0 |
4 |
148 |
0 |
7 |
41 5/6 |
|
|
aij |
4 |
1 |
5 |
0 |
116 |
0 |
4 |
38 2/3 |
|
0 |
2 |
4 |
3 |
90 |
18 |
0 |
0 |
|
|
xj |
20 |
36 |
0 |
0 |
1500 |
447 ½ |
||
|
Δj |
0 |
0 |
6 |
16 |
Транспортная задача линейного программирования
Транспортная задача формулируется следующим образом. Однородный продукт, сосредоточенный в m пунктах производства (хранения) в количествах а1, а2,..., аm единиц, необходимо распределить между n пунктами потребления, которым необходимо соответственно b1, b2,..., bn единиц. Стоимость перевозки единицы продукта из i-го пункта отправления в j-ый пункт назначения равна сij и известна для всех маршрутов. Необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы по доставке продуктов были минимальными.
Обозначим через хij количество груза, планируемого к перевозке от i-го поставщика j-му потребителю. При наличии баланса производства и потребления (1)
математическая модель транспортной задачи будет выглядеть так: найти план перевозок
Х = (хij), i = 1,m; j = 1,n
минимизирующий общую стоимость всех перевозок
(2)
при условии, что из любого пункта производства вывозится весь продукт
(3)
и любому потребителю доставляется необходимое количество груза (4)
причем по смыслу задачи х11 > 0 ,. . . ., xmn > 0. (5)
Для решения транспортной задачи чаще всего применяется метод потенциалов. Пусть исходные данные задачи имеют вид
А(а1, а2, а3) = (80; 50; 45); В(b1, b2, b3, b4) = (21; 43; 46; 59);
2 1 6 12
C = 9 3 5 4
1 4 8 7
Общий объем производства аi = 80+50+45= 175 больше, требуется всем потребителям bi = 21+43+46+59= 169, т.е. имеем открытую модель транспортной задачи. Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления 175-169 = 6 единиц, причем тарифы на перевозку в этот пункт условимся считать равными нулю, помня, что переменные, добавляемые к левым частям неравенств для превращения их в уравнения, входят в функцию цели с нулевыми коэффициентами.
Первое базисное допустимое решение легко построить по правилу северо-западного угла.
|
Потребление |
b1 =21 |
b2 =43 |
b3 =46 |
b4 =59 |
b5 =6 |
|
|
Производство |
||||||
|
a1= 80 |
21 |
43 |
16 |
p1= |
||
|
a2= 50 |
30 |
20 |
p2= |
|||
|
a3= 45 |
* |
39 |
6 |
P3= |
||
|
q1= |
q2= |
q3= |
q4= |
q5= |
Следует иметь в виду, что по любой транспортной таблице можно восстановить соответствующий предпочитаемый эквивалент системы уравнений (3), (4), а в таблице записаны лишь правые части уравнений, причем номер клетки показывает, какая неизвестная в соответствующем уравнении является базисной. Так как в системе (3), (4) ровно m + n - 1 линейно независимых уравнений, то в любой транспортной таблице должно быть m + n - 1 занятых клеток.
Обозначим через )
вектор симплексных множителей или потенциалов. Тогда
ij = Aij - сij i = 1,m; j = 1,n
откуда следует ij = pi + qj - cij i = 1,m; j = 1,n (6)
Один из потенциалов можно выбрать произвольно, так как в системе (3), (4) одно уравнение линейно зависит от остальных. Положим, что р1 = 0. Остальные потенциалы находим из условия, что для базисных клеток . В данном случае получаем
11 = 0, p1 + q1 - c11 = 0, 0+q1 –2 = 0, q1 = 2
12 = 0, p1 + q2 - c12 = 0, 0+q2 –1 = 0, q2 = 1
13 = 0, p1 + q3 - c13 = 0, 0+q3 –6 = 0, q2 = 6
23 = 0, p2 + q3 - c23 = 0, р2 +6–5 = 0, р2 = -1
и т.д., получим: p3=2, q4= 5, q5= -2.
Затем по формуле (6) вычисляем оценки всех свободных клеток:
21 = p2 + q1 - c21 = -1+2-9 = -8
31 = p3 + q1 - c31 = 2+2-1 = 3
22 = p2 + q2 – c22 = -1+1-3 = -3
32 = p3 + q2 - c32 = 2+1-4 = -1
33 = p3 + q3 - c33 = 2+6-8 = 0
14 = p1 + q4 – c14 = 0+5-12 = -7
15 = p1 + q5 – c15 = 0-2-0 = -2
25 = p2 + q5 – c15 = -1-2-0 = -3
Находим наибольшую положительную оценку max () = 3 =
Для найденной свободной клетки 31 строим цикл пересчета - замкнутую ломаную линию, соседние звенья которой взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы, одна из вершин находится в данной свободной клетке, а все остальные - в занятых клетках. Это будет 31-11-12-13-24-34. Производим перераспределение поставок вдоль цикла пересчета
|
21 |
43 |
16 |
21- |
43 |
16+ |
43 |
37 |
||||||
|
30 |
20 |
30- |
20+ |
9 |
41 |
||||||||
|
39 |
|
39- |
21 |
18 |
= 21
Получаем второе базисное допустимое решение:
|
Потребление |
b1 =21 |
b2 =43 |
b3 =46 |
b4 =59 |
b5 =6 |
|
|
Производство |
||||||
|
a1= 80 |
43 |
37 |
p1= 0 |
|||
|
a2= 50 |
9 |
41 |
p2= -1 |
|||
|
a3= 45 |
21 |
18 |
6 |
p3=2 |
||
|
q1= -1 |
q2= 1 |
q3= 6 |
q4= 5 |
q5= -2 |
Находим новые потенциалы, новые оценки. Оценки всех свободных клеток:
Находим новые потенциалы, новые оценки.
12 = 0, p1 + q2 - c12 = 0, 0+q2 -1 = 0, q2 = 1
13 = 0, p1 + q3 - c13 = 0, 0+q3 -6 = 0, q3 = 6
23 = 0, p2 + q3 – c23 = 0, p2+6 -5 = 0, p2 = -1
24 = 0, p2 + q4 – c24 = 0, -1+ q4-4 = 0, q4 = 5
34 = 0, p3 + q4 – c34 = 0, р3 +5-7 = 0, р3 = 2
35 = 0, p3 + q5 – c35 = 0, 2 + q5-0 = 0, q5 = -2
11 = p1 + q1 – c11 = 0+-1-2 = -3
21 = p2 + q1 - c21 = -1-1-9 = -11
22 = p2 + q2 – c22 = -1+1-3 = -3
32 = p3 + q2 – c32 = 2+1- 4= -1
33 = p3 + q3 – c33 = 2+6-8 = 0
14 = p1 + q4 – c14 = 0+5-12 = -7
15 = p1 + q5 – c15 = 0-2-0 = -2
25 = p2 + q5 – c25 = -1-2-0 = -3
Пришли к таблице, для которой все ij 0 i = 1,m; j = 1,n
Оценки удовлетворяют условию оптимальности, следовательно решение….
0 43 37 0
X= 0 0 9 41
21 0 0 18 …оптимально.
Общая стоимость перевозок = 43*1+37*6+9*5+41*4+21*1+18*7= 621 ед.
Динамическое программирование.
распределение капитальных вложений
Динамическое программирование - это вычислительный метод для решения задач управления определенной структуры. Данная задача с n переменными представляется как многошаговый процесс принятия решений. На каждом шаге определяется экстремум функции только от одной переменной.
Знакомство с методом динамического программирования проще всего начать с рассмотрения нелинейной задачи распределения ресурсов между предприятиями одного производственного объединения или отрасли. Для определенности можно считать, что речь идет о распределении капитальных вложений.
Предположим, что указано n пунктов, где требуется построить или реконструировать предприятия одной отрасли, для чего выделено b рублей. Обозначим через fi(xi) прирост мощности или прибыли на j-м предприятии, если оно получит xi рублей капитальных вложений. Требуется найти такое распределение (x1,x2, ... , xn) капитальных вложений между предприятиями, которое максимизирует суммарный прирост мощности или прибыли
z = f1(x1) + f2(х2) + ... + fn(xn)
при ограничении по общей сумме капитальных вложений
x1 + x2 + ... + xn = b
причем будем считать, что все переменные xj принимают только целые неотрицательные значения
xj = 0, или 1, или 2, или 3, ...
Функции fj(xj) мы считаем заданными, заметив, что их определение - довольно трудоемкая экономическая задача.
Воспользуемся методом динамического программирования для решения этой задачи.
Производственное объединение состоит из четырех предприятий (n=4). Общая сумма капитальных вложений равна 700 тыс. рублей (b=700), выделяемые предприятиям суммы кратны 100 тыс. рублей. Значения функций fj(xj) приведены в таблице 1, где, например, число 92 означает, что если третье предприятие получит 400 тыс. руб. капитальных вложений, то прирост прибыли на этом предприятии составит 92 тыс. руб.
Таблица I
|
xj |
0 |
100 |
200 |
300 |
400 |
500 |
600 |
700 |
|
f1(x1) |
0 |
5 |
8 |
10 |
12 |
13 |
14 |
15 |
|
f2(x2) |
0 |
5 |
10 |
14 |
17 |
19 |
21 |
22 |
|
f3(x3) |
0 |
8 |
13 |
18 |
21 |
23 |
25 |
27 |
|
f4(x4) |
0 |
6 |
13 |
20 |
27 |
33 |
38 |
41 |
Прежде всего заполняем табл. 2. Значения f2(x2) складываем со значениями F1( - x2) = f1(- x2) и на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение . Заполняем таблицу 3.
Продолжая процесс, табулируем функции F3(), () и т.д. В табл. 6 заполняем только одну диагональ для значения = 700. Наибольшее число на этой диагонали:
Zmax = 46 тыс. руб.,
но четвертому предприятию не может быть выделено
х*4 = 4 (700) = 600 тыс. руб. или 500 тыс. руб. Можно только выделить 400 тыс. руб.
На долю остальных трех предприятий остается 300 тыс. руб. Из табл. 5 видно, что третьему предприятию должно быть выделено
x*3 = 3 (700-x*4) = 3 (300) = 100 тыс. руб.
Продолжая обратный процесс, находим
x*2 = 2 (700 - x*4 - x*3) = 2 (200) = 100 тыс. руб.
На долю первого предприятия остается
x*1 = 700 - x*4 - x*3 - x*2 = 100 тыс. руб.
Таким образом, наилучшим является следующее распределение капитальных вложений по предприятиям:
x*1 =100; x*2 =100; x*3 = 100; x*4 = 400.
Оно обеспечивает производственному объединению наибольший возможный прирост прибыли 45 тыс. руб.
Рекомендуется проверить выполнение равенства
f1(x*1) + f2(x*2) + f3(x*3) + f4(x*4) = z max
27+8+5+5=45
|
- x2 |
0 100 200 300 400 500 600 700 |
|
|
x2 |
F1( - x2) f2(x2) |
0 5 8 10 12 13 14 15 |
|
0 |
0 |
0 5* 8 10 12 13 14 15 |
|
100 |
5 |
5 10* 13 15 17 18 19 |
|
200 |
10 |
10 15* 18 20 22 23 |
|
300 |
14 |
14 19* 22* 24 26 |
|
400 |
17 |
17 22 25* 27* |
|
500 |
19 |
19 24 27 |
|
600 |
21 |
21 26 |
|
700 |
22 |
22 . |
Таблица 3
|
|
0 100 200 300 400 500 600 700 |
|
F2() |
0 5 10 15 19 22 25 27 |
|
() |
0 0 100 200 300 300 400 400 |
Таблица 4
|
- x3 |
0 100 200 300 400 500 600 700 |
|
|
x3 |
F2( - x3) f3(x3) |
0 5 10 15 19 22 25 27 |
|
0 |
0 |
0 5 10 15 19 22 25 27 |
|
100 |
8 |
8* 13* 18* 23* 27 30 33 |
|
200 |
13 |
13 18 23 28* 32 35 |
|
300 |
18 |
18 23 28 33* 37* |
|
400 |
21 |
21 26 31 36 |
|
500 |
23 |
23 28 33 |
|
600 |
25 |
25 30 |
|
700 |
27 |
27 |
Таблица 5
|
|
0 100 200 300 400 500 600 700 |
|
F3() |
0 8 13 18 23 28 33 37 |
|
() |
0 100 100 100 100 200 300 300 |
Таблица 6
|
- x4 |
0 100 200 300 400 500 600 700 |
|
|
x4 |
F3( - x4) f4(x4) |
0 8 13 18 23 28 33 37 |
|
0 |
0 |
37 |
|
100 |
6 |
39 |
|
200 |
13 |
41 |
|
300 |
20 |
43 |
|
400 |
27 |
45 |
|
500 |
33 |
46* |
|
600 |
38 |
46* |
|
700 |
41 |
41 . |
Матричная игра как модель конкуренции
и сотрудничества
Теория игр: совокупность математических методов, анализа и оценки поведения в конфликтных ситуациях, когда сталкиваются интересы двух или более сторон, преследующие различные, иногда противоположные цели. Противоречащие друг другу интересы наблюдаются в области экономики, военном деле, спорте, иногда противоречат интересы различных ступеней иерархии в СУ. Теория игр представляет собой математическую теорию конфликтных ситуаций. Ее цель-выработка рекомендаций по разумному поведению участников конфликта. Рассмотрим матричную игру двух лиц с нулевой суммой. Задана матрица:
1 2 2 5
3 3 -4 -2
Участвуют 2 игрока. 1-ый выбирает номер строки, а 2-ой независимо от 1-го выбирает номер столбца. Если 1-ый загадал 2-ую строку, а второй – 3-ий столбец, то выигрыш второго составляет 4 рубля.
Для второго игрока 2-ый столбец является доминируемым по сравнению с 1-ым, т.к. в первом случае он проигрывает 1 рубль, а во втором проигрывает 2 рубля, и, при этом ,проигрывает 2 и 3 рубля соответственно, если 1-ый игрок выбирает 2-ую строку. Вычеркиваем его
1 2 2 5
3 3 -4 -2
Построим график, образованный пересечением следующих линий:
Так, как если второй игрок выберет свою первую стратегию, то он его выигрыш будет задан уравнением:
V1=p+3*(1-p)=3-2р
То же для 3-ей и 4-ой стратегий
V3=2p-4(1-p)=2p-4+4p=6р-4
V4=5р-2(1-p)=7p-2
Как видно из графика, идя по нижней границе, образуются две точки, мы выбираем верхнюю, образованную пересечением 2-х прямых (1 и 3). 4-ю следует исключить.
Получаем матрицу:
1 2
3 -4
Или:
Найдем оптимальные стратегии игроков.
Пусть стратегия Первого есть (p1,p2), а Второго – (q1,0,q3,0).
Обозначим: p1=x, p2=1-x
q1=y, q3=1-y
Выразим математическое ожидание выигрыша первого игрока (цена игры):
M(P,Q)= xy+2x(1-y)+3y(1-x) -4(1-x)(1-y)= xy+2x-2xy+3y-3xy-4+4y+4x-4xy = -8xy+7y+6x-4
= -8y(x-7/8)+6(x-7/8)+10/8 = -8(x-7/8)(y-6/8)+10/8
Допустим, 1-ый игрок решил придерживаться P(x=7/8,1-x=1/8), тогда, как бы ни старался 2, не менял y выигрыш первого всегда (10/8). Представим, что первый отклонится от х=7/10, взяв х=6/8, тогда 2-ой игрок может взять y=5/8 и выигрыш первого будет лишь 9/8. Значит, оптимальная стратегия первого P (7/8,1/8), аналогично для второго Q(6/8,0,2/8,0). При этом при достаточно большом числе игр проигрыш первого будет составлять в среднем 10/8 руб. за партию.
Цена игры ν=M(P,Q)= 7/8*6/8+2*7/8*2/8+3*6/8*1/8-4*1/8*2/8=80/64=5/4
Найдем дисперсию (риск):
1)Пусть игроки применяют свои оптимальные стратегии:
ν=M(P,Q)= 7/8*6/8+2*7/8*2/8+3*6/8*1/8-4*1/8*2/8=80/64=5/4
D(P,Q)=(-1)2*7/8*6/8+22*7/8*2/8+32*6/8*1/8+42*1/8*2/8- (5/4) 2 = =42/64+56/64+54/64+32/64- (5/4) 2 =21/16
Риск r=D1,15
2)Пусть, 1-ый игрок применяет свою оптимальную стратегию P(7/8,1/8), а 2-ой– 1-ую чистую стратегию Q1(1,0), тогда риск будет равен:
ν=M(P,Q1)= 1*7/8+3*1/8= 5/4
D(P,Q1)=12 *7/8+32*1/8- 25/16=7/16
Риск r=D0,66
3)Пусть, 1-ый игрок применяет свою оптимальную стратегию P(7/8,1/8), а 2-ой– 2-ую чистую стратегию Q2(0,1), тогда риск будет равен:
ν=M(P,Q2)= 2*7/8- 4*1/8=5/4
D(P,Q2)=22*7/8+42*1/8 – 25/16=63/16
Риск r=D1,98
4)Пусть, 2-ой игрок применяет свою оптимальную стратегию Q(6/8,2/8), а 1-ый– 1-ую чистую стратегию P1(1,0), тогда риск будет равен:
ν=M(P1,Q)= 1*6/8+2*2/8= 5/4
D(P1,Q)= 1 2*6/8 +22*2/8 – 25/16=3/16
Риск r=D0,43
5)Пусть, 2-ой игрок применяет свою оптимальную стратегию Q(6/8,2/8), а 1-ый– 2-ую чистую стратегию P2(0,1), тогда риск будет равен:
ν=M(P2,Q)= 3*6/8 – 4*2/8= 5/4
D(P2,Q)=32*6/8+42*2/8 – 25/16=147/16
Риск r=D3,03
Из всех возможных рисков наименьший будет, если 2-ой игрок применяет свою оптимальную стратегию Q(6/8,2/8), а 1-ый– 1-ую чистую стратегию P1(1,0), тогда риск будет равен 0,43; цена игры ν=M(P1,Q)= 5/4.
Анализ доходности и риска финансовых операций
Финансовой называется операция, начальное и конечное состояния которой имеют денежную оценку и цель проведения которой заключается в максимизации дохода - разности между конечной и начальной оценками.
Почти всегда финансовые операции проводятся в условиях неопределенности и потому их результат невозможно предсказать заранее. Поэтому финансовые операции рискованны, т.е. при их проведении возможны как прибыль так и убыток (или не очень большая прибыль по сравнению с той, на что надеялись проводившие эту операцию).
Как оценить операцию с точки зрения ее доходности и риска?
Существует несколько разных способов. Наиболее распространенным является представление дохода операции как случайной величины и оценка риска операции как среднего квадратического отклонения этого случайного дохода.
Рассмотрим какую-нибудь операцию, доход которой есть случайная величина Q. Средний ожидаемый доход Q - это математическое ожидание с.в. Q: , где pi есть вероятность получить доход qi. А среднее квадратическое отклонение (СКО) - это мера разбросанности возможных значений дохода вокруг среднего ожидаемого дохода. Вполне разумно считать количественной мерой риска операции и обозначить r. Напомним, что дисперсия
D[Q] = M [(Q - Q)2] = M [Q2] - Q2.
Рассмотрим четыре операции Q1, Q2, Q3, Q,4. Найдем средние ожидаемые доходы Qi и риски ri операций.
Ряды распределения, средние ожидаемые доходы и риски:
|
Q1 |
: |
0 |
8 |
12 |
24 |
Q1 = 0*1/4+8*1/4+12*1/3+24*1/6=10 |
r1 = √ D 7,75 |
|
1/4 |
1/4 |
1/3 |
1/6 |
D[Q] =0*1/4+64*1/4+144*1/3+576*1/6 -10²=60 |
|||
|
Q2 |
: |
-6 |
-2 |
0 |
-6 |
Q2 = -6*1/4-2*1/4+0*1/3-6*1/6=-3 |
r2 = √ D 2,65 |
|
1/4 |
1/4 |
1/3 |
1/6 |
D[Q] =36*1/4+4*1/4+0*1/3+36*1/6- (-3) ²=7 |
|||
|
Q3 |
: |
0 |
2 |
4 |
16 |
Q3 =0*1/3+2*1/3+4*1/6+16*1/6=4 |
r3 = √ D 5,54 |
|
1/3 |
1/3 |
1/6 |
1/6 |
D[Q] =0*1/3+4*1/3+16*1/6+256*1/6- 4²=92/3 |
|||
|
Q4 |
: |
-6 |
-5 |
-4 |
3 |
Q4 = -6*1/3-5*1/3-4*1/6+3*1/6=-23/6 ( -3,83) |
r4 = √ D 3,13 |
|
1/3 |
1/3 |
1/6 |
1/6 |
D[Q] =36*1/3+25*1/3+16*1/6+9*1/6- (-23/6)²=353/36 |
Нанесем средние ожидаемые доходы Q и риски r на плоскость - доход откладываем по горизонтали, а риски
по вертикали (см. рис.):
Получили 4 точки. Чем правее точка (Q, r), тем более доходная операция, чем точка выше - тем более она рисковая. Значит, нужно выбирать точку правее и ниже. Точка (Q, r) доминирует точку (Q, r) если Q Q и r r. В нашем случае 4-я и 3-я операция доминирует 1-ую и 2-ую.
Точка, не доминируемая никакой другой называется оптимальной по Парето, а множество всех таких точек называется множеством оптимальности по Парето. Легко видеть, что если из рассмотренных операций надо выбирать лучшую, то ее обязательно надо выбрать из операций, оптимальных по Парето.
Для нахождения лучшей операции иногда применяют подходящую взвешивающую формулу (в нашем случае это необязательно), которая для пар (Q, r) дает одно число, по которому и определяют лучшую операцию. Например, пусть взвешивающая формула есть (Q)= 2Q - r . Тогда получаем:
(Q1)=2*10-7,75=12,25;
(Q2)=2*(-3)-2,65= -8,65;
(Q3)=2*4-5,54=2,46;
(Q4)= 2*(-23/6)-3,13≈ -10,8
Видно, что 1-ая операция – лучшая, а 4-ая – худшая.
Принятие решений в условиях неопределенности
Предположим, что ЛПР (Лицо, Принимающее Решения) рассматривает несколько возможных решений . Ситуация неопределенна, понятно лишь, что наличествует какой-то из вариантов . Если будет принято -e решение, а ситуация есть -я , то фирма, возглавляемая ЛПР, получит доход . Матрица называется матрицей последствий (возможных решений). Какое же решение нужно принять ЛПР? В этой ситуации полной неопределенности могут быть высказаны лишь некоторые рекомендации предварительного характера. Они не обязательно будут приняты ЛПР. Многое будет зависеть, например, от его склонности к риску. Но как оценить риск в данной схеме?
Допустим, мы хотим оценить риск, который несет -e решение. Нам неизвестна реальная ситуация. Но если бы ее знали, то выбрали бы наилучшее решение, т.е. приносящее наибольший доход. Т.е. если ситуация есть -я , то было бы принято решение, дающее доход .
Значит, принимая -e решение мы рискуем получить не , а только , значит принятие -го решения несет риск недобрать . Матрица называется матрицей рисков.
Матрица последствий есть
0 8 12 24
-6 -2 0 -6
Q= 0 2 4 16
-6 -5 -4 3
0 0 0 0
6 10 12 30
R= 0 6 8 8
6 13 16 21
А. Принятие решений в условиях полной неопределенности.
Не все случайное можно "измерить" вероятностью. Неопределенность – более широкое понятие. Неопределенность того, какой цифрой вверх ляжет игральный кубик отличается от неопределенности того, каково будет состояние российской экономики через 15 лет. Кратко говоря, уникальные единичные случайные явления связаны с неопределенностью, массовые случайные явления обязательно допускают некоторые закономерности вероятностного характера.
Ситуация полной неопределенности характеризуется отсутствием какой бы то ни было дополнительной информации. Какие же существуют правила-рекомендации по принятию решений в этой ситуации?
Правило Вальда (правило крайнего пессимизма). Рассматривая -e решение будем полагать, что на самом деле ситуация складывается самая плохая, т.е. приносящая самый малый доход .
Но теперь уж выберем решение с наибольшим . Итак, правило Вальда рекомендует принять решение , такое что
Так, в вышеуказанном примере, имеем a1=0; a2=-6; a3=0; a4=-6. Теперь из этих чисел находим максимальное. Это – 0 . Значит, правило Вальда рекомендует принять 1-ое или 3-е решение.
Правило Сэвиджа (правило минимального риска). При применении этого правила анализируется матрица рисков . Рассматривая -e решение будем полагать, что на самом деле складывается ситуация максимального риска
Но теперь уж выберем решение с наименьшим . Итак, правило Сэвиджа рекомендует принять решение , такое что
Так, в вышеуказанном примере, имеем b1=0; b2=30; b3=8; b4=21. Теперь из этих чисел находим минимальное. Это – 0. Значит правило Сэвиджа рекомендует принять 1-ое решение.
Правило Гурвица (взвешивающее пессимистический и оптимистический подходы к ситуации). Принимается решение , на котором достигается максимум
где . Значение выбирается из субъективных соображений. Если приближается к 1, то правило Гурвица приближается к правилу Вальда, при приближении к 0, правило Гурвица приближается к правилу "розового оптимизма". При правило Гурвица рекомендует:
½(0)+1/2*24= 12
½(-6)+1/2*0= -3
½(0)+1/2*16= 8
½(-6)+1/2*3= -3/2
1-е решение.
В. Принятие решений в условиях частичной неопределенности.
Предположим, что в рассматриваемой схеме известны вероятности того, что реальная ситуация развивается по варианту . Именно такое положение называется частичной неопределенностью. Как здесь принимать решение? Можно выбрать одно из следующих правил.
Правило максимизации среднего ожидаемого дохода. Доход, получаемый фирмой при реализации -го решения, является случайной величиной с рядом распределения
|
… |
||||
|
… |
Математическое ожидание и есть средний ожидаемый доход, обозначаемый также . Итак, правило рекомендует принять решение, приносящее максимальный средний ожидаемый доход.
В схеме из предыдущего п. вероятности есть (1/4,1/4,1/3,1/6). Тогда
Q1= 0*1/4+8*1/4+12*1/3+24*1/6=10
Q2= -6*1/4-2*1/4+0*1/3-6*1/6= -3
Q3= 0*1/4+2*1/4+4*1/3+16*1/6= 4,5
Q4= -6*1/4-5*1/4-4*1/3+3*1/6= -43/12≈ -3,58
Максимальный средний ожидаемый доход равен 10, что соответствует 1-му решению.
Правило минимизации среднего ожидаемого риска. Риск фирмы при реализации -го решения, является случайной величиной с рядом распределения
|
… |
||||
|
… |
Математическое ожидание и есть средний ожидаемый риск, обозначаемый также . Правило рекомендует принять решение, влекущее минимальный средний ожидаемый риск.
Вычислим средние ожидаемые риски при указанных выше вероятностях. Получаем
R1=0*1/4+0*1/4+0*1/3+0*1/6=0
R2=6*1/4+10*1/4+12*1/3+30*1/6=13
R3=0*1/4+6*1/4+8*1/3+8*1/6=11/2=5,5
R4=6*1/4+13*1/4+16*1/3+21*1/6=163/12≈13,58
Минимальный средний ожидаемый риск равен 0, что соответствует 1-му решению.
Нанесем средние ожидаемые доходы и средние ожидаемые риски на плоскость – доход откладываем по вертикали, а риски по горизонтали (см.рис.):
Получили 4 точки. Чем выше точка
, тем более доходная операция, Q1
чем точка правее – тем более она
рисковая. Значит, нужно выбирать
точку выше и левее. Точка
доминирует точку , если Q3
и и хотя бы одно из этих
неравенств строгое. В нашем случае
1-ая операция доминирует все остальные.
Q2
Q4
Точка, не доминируемая никакой другой называется оптимальной по Парето, а множество всех таких точек называется множеством оптимальности по Парето. Легко видеть, что если из рассмотренных операций надо выбрать лучшую, то ее обязательно надо выбрать из операций, оптимальных по Парето. В нашем случае, множество Парето, т.е. оптимальных по Парето операций, состоит только из одной 1-ой операции.
Для нахождения лучшей операции иногда применяют подходящую взвешивающую формулу, которая для пар дает одно число, по которому и определяют лучшую операцию. Например, пусть взвешивающая формула есть . Тогда получаем:
f(Q1)=2*10-0 =20
f(Q2)=2*(-3)-13= -19
f(Q3)=2*4,5-5,5=3,5
f(Q4)=2*(-43/12)-163/12= -83/4= -20,75
Видно, что 1-ая операция – лучшая, а 4-ая – худшая.