Реферат: Прикладная математика
--PAGE_BREAK-- Таблица 1
36 14 25 50 0 0 0
Пояснения
<img width=«25» height=«28» src=«ref-1_296634549-222.coolpic» v:shapes="_x0000_i1097">
Базис
Н
x1 x2 x3 x4 x5 x6 x7
<img width=«271» height=«108» src=«ref-1_296634771-1303.coolpic» v:shapes="_x0000_s1529 _x0000_s1530 _x0000_s1531 _x0000_s1532 _x0000_s1533">
х5
208
4 3 4 5 1 0
z0= <img width=«17» height=«21» src=«ref-1_296636074-199.coolpic» v:shapes="_x0000_i1091">H
х6
107
2 5 0 2 0 1
<img width=«161» height=«30» src=«ref-1_296636273-378.coolpic» v:shapes="_x0000_i1092">
х7
181
3 1 2 5 0 0 1
<img width=«117» height=«25» src=«ref-1_296636651-302.coolpic» v:shapes="_x0000_i1093">
z -z
0 — z
-36 -14 -25 -50 0 0
<img width=«125» height=«33» src=«ref-1_296636953-347.coolpic» v:shapes="_x0000_i1094">
<img width=«271» height=«137» src=«ref-1_296637300-1087.coolpic» v:shapes="_x0000_s1534 _x0000_s1535 _x0000_s1536 _x0000_s1537">
х5
27
1 2 2 0 1 0 -1
<img width=«137» height=«20» src=«ref-1_296638387-338.coolpic» v:shapes="_x0000_i1098">
х6
173/5
4/5 23/5 -4/5 0 0 1 -2/5
50
х4
181/5
3/5 1/5 2/5 1 0 0 1/5
<img width=«160» height=«43» src=«ref-1_296638725-475.coolpic» v:shapes="_x0000_i1099">
z -z
1810-z
-6 -4 -5 0 0 0 10
<img width=«63» height=«35» src=«ref-1_296639200-226.coolpic» v:shapes="_x0000_i1100">
36
х1
27
1 2 2 0 1 0 -1
х6
13
0 3 -12/5 0 -4/5 1 2/5
все Dj ³
50
х4
20
0 -1/5 -4/5 1 -3/5 0 4/5
z -z
1972-z
0 8 7 0 6 0 4
где представлены расширенные матрицы вспомогательных систем уравнений (22) ® (24) ® (25). Эти таблицы принято называть симплексными.
Следует обратить внимание на экономический смысл элементов последней строки последней симплексной таблицы. Например, коэффициент D3=7 при переменной х3 показывает, что если произвести одну единицу продукции третьего вида (она не входит в оптимальную производственную программу), то прибыль уменьшится на 7 единиц.
В заключение заметим, что в рассматриваемом простейшем примере линейной производственной задачи возможна самопроверка результата.
Воспользуемся тем, что в оптимальной производственной программе х2=0, х3=0. Предположим, что вторую и третью продукции мы не намеревались выпускать с самого начала. Рассмотрим задачу с оставшимися двумя переменными, сохранив их нумерацию. Математическая модель задачи будет выглядеть следующим образом:
<img width=«156» height=«187» src=«ref-1_296639426-932.coolpic» v:shapes="_x0000_i1095">
Студенту не составит труда решить эту задачу графически и убедиться, что результаты совпадают.
Следует при этом обратить внимание на то, что последовательное улучшение производственной программы
(x1=0, x4=0) ®(x1=0, x4=<img width=«29» height=«41» src=«ref-1_296623144-227.coolpic» v:shapes="_x0000_i1096">) ®(x1=27, x4=20)
на графике означает движение от одной вершины многогранника допустимых решений к другой вершине по связывающей их стороне многоугольника (в случае трех переменных это будет «езда» по ребрам многогранника допустимых решений от одной вершины к другой до достижения оптимальной вершины).
§5. Двойственная задача
Ранее мы рассмотрели конкретную линейную производственную задачу по выпуску четырех видов продукции с использованием трех видов ресурсов по заданным технологиям.
Теперь представим себе, что возникла новая ситуация. Знакомый предприниматель П (Петров), занимающийся производством каких-то других видов продукции, но с использованием трех таких же видов ресурсов, какие имеются у нас, предлагает нам «уступить» по определенным ценам все имеющиеся у нас ресурсы и обещает платить у1 рублей за каждую единицу первого ресурса, у2 руб – второго, у3 руб – третьего. Возникает вопрос: при каких ценах у1, у2, у3 мы можем согласиться с предложением П.
Величины у1, у2, у3 принято называть расчетными, или двойственными, оценками ресурсов. Они прямо зависят от условий, в которых действует наше предприятие.
Напомним, что в нашей задаче технологическая матрица А, вектор объемов ресурсов В и вектор удельной прибыли С имели вид
<img width=«336» height=«76» src=«ref-1_296619231-760.coolpic» v:shapes="_x0000_i1101">
Для производства единицы продукции первого вида мы должны затратить, как видно из матрицы А, 4 единицы ресурса первого вида, 2 единицы ресурса второго вида и 3 единицы третьего (элементы первого столбца матрицы). В ценах у1, у2, у3 наши затраты составят 4у1 + 2у2 + 3у3, т.е. столько заплатит предприниматель П за все ресурсы, идущие на производство единицы первой продукции. На рынке за единицу первой продукции мы получили бы прибыль 36 руб. Следовательно, мы можем согласиться с предложением П только в том случае, если он заплатит не меньше
4у1 + 2у2 + 3у3 ³ 36.
Аналогично, во втором столбце матрицы А указаны затраты различных ресурсов на производство единицы продукции второго вида. В ценах П эти затраты составят 3у1 + 5у2 + у3, а на рынке за единицу продукции второго вида мы получили бы прибыль 14 рублей. Поэтому перед предпринимателем П мы ставим условие
3у1 + 5у2 + у3 ³ 14
и т.д. по всем видам продукции.
Учтем, что за все имеющиеся у нас ресурсы нам должны заплатить 208у1 + 107у2 + 181у3 рублей. При поставленных нами условиях предприниматель П будет искать такие значения величин у1, у2, у3, чтобы эта сумма была как можно меньше. Подчеркнем, что здесь речь идет не о ценах, по которым мы когда-то приобретали эти ресурсы, а об этих ценах, которые существенно зависят от применяемых нами технологий, объемов ресурсов и от ситуации на рынке.
Таким образом, проблема определения расчетных оценок ресурсов приводит к задаче линейного программирования: найти вектор двойственных оценок
у(у1, y2, y3)
минимизирующий общую оценку всех ресурсов
f = 208y1 + 107y2 +181y3 (1)
при условии, что по каждому виду продукции суммарная оценка всех ресурсов, затрачиваемых на производство единицы продукции, не меньше прибыли, получаемой от реализации единицы этой продукции
<img width=«21» height=«107» src=«ref-1_296641345-763.coolpic» v:shapes="_x0000_s1060 _x0000_s1061 _x0000_s1062"> 4y1 + 2y2 + 3y3³36
3y1 + 5y2 + y3 ³14
4y1 + 2y3 ³25
5y1 + 2y2 + 5y3 ³50
причем оценки ресурсов не могут быть отрицательными
y1<img width=«13» height=«16» src=«ref-1_296642108-191.coolpic» v:shapes="_x0000_i1102">0, y2<img width=«13» height=«16» src=«ref-1_296642108-191.coolpic» v:shapes="_x0000_i1103">0, y3<img width=«13» height=«16» src=«ref-1_296642108-191.coolpic» v:shapes="_x0000_i1104">0. (3)
Решение полученной задачи легко найти с помощью второй основной теоремы двойственности, согласно которой для оптимальных решений <img width=«16» height=«21» src=«ref-1_296642681-201.coolpic» v:shapes="_x0000_i1105">(х1, х2, х3, х4) и <img width=«17» height=«24» src=«ref-1_296642882-204.coolpic» v:shapes="_x0000_i1106">(y1, y2, y3) пары двойственных задач необходимо и достаточно выполнение условий
<img width=«22» height=«107» src=«ref-1_296643086-752.coolpic» v:shapes="_x0000_s1071 _x0000_s1072 _x0000_s1073"> <img width=«21» height=«88» src=«ref-1_296643838-705.coolpic» v:shapes="_x0000_s1081 _x0000_s1082 _x0000_s1083">
x 1 (4y1 + 2y2 + 3y3 — 36) = 0 y1 (4x1 +3x2 + 4x3 + 5x4 — 208) = 0
x 2 (3y1 + 5y2 + y3 — 14) = 0 y2 (2x1 +5x2 + 2x4 — 107) = 0
x 3 (4y1 + 2y3 — 25) = 0 y3 (3x1 + x2 + 2x3 + 5x4 — 181) = 0 .
x 4(5y1 + 2y2 + 5y3 — 50) = 0
Ранее было найдено, что в решении исходной задачи х1>0, x4>0. Поэтому
<img width=«21» height=«60» src=«ref-1_296644543-601.coolpic» v:shapes="_x0000_s1098 _x0000_s1099 _x0000_s1100">
4y1 + 2y2 + 3y3 — 36 = 0
5y1 + 2y2 + 5y3 — 50 = 0
Если же учесть, что второй ресурс был избыточным и, согласно той же теореме двойственности, ее двойственная оценка равна нулю
у2=0,
то приходим к системе уравнений
<img width=«21» height=«59» src=«ref-1_296645144-298.coolpic» v:shapes="_x0000_s1122 _x0000_s1123 _x0000_s1124">4y1 + 3y3 — 36 = 0
5y1 + 5y3 — 50 = 0
откуда следует
у1=6, у3=4.
Таким образом, получили двойственные оценки ресурсов
у1=6; у2=0; у3=4, (4)
причем общая оценка всех ресурсов равна 1972.
Заметим, что решение (4) содержалось в последней строке последней симплексной таблицы исходной задачи. Важен экономический смысл двойственных оценок. Например, двойственная оценка третьего ресурса у3=4 показывает, что добавление одной единицы третьего ресурса обеспечит прирост прибыли в 4 единицы.
§6.Задача о "расшивке узких мест производства"
При выполнении оптимальной производственной программы первый и третий ресурсы используются полностью, т.е. образуют ²узкие места производства². Будем их заказывать дополнительно. Пусть T(t1,t2,t3)- вектор дополнительных объемов ресурсов. Так как мы будем использовать найденные двойственные оценки ресурсов, то должно выполняться условие
H + Q-1T <img width=«13» height=«16» src=«ref-1_296642108-191.coolpic» v:shapes="_x0000_i1113"> 0.
Задача состоит в том, чтобы найти вектор
T (t1, 0, t3),
максимизирующий суммарный прирост прибыли
W = 6t1 + 4t3 (1)
при условии сохранения двойственных оценок ресурсов (и, следовательно, структуры производственной программы)
<img width=«249» height=«65» src=«ref-1_296645633-623.coolpic» v:shapes="_x0000_i1107">
предполагая, что можно надеяться получить дополнительно не более 1/3 первоначального объема ресурса каждого вида
<img width=«298» height=«311» src=«ref-1_296646256-7504.coolpic» v:shapes="_x0000_s1206 _x0000_s1207 _x0000_s1208 _x0000_s1209 _x0000_s1210 _x0000_s1211 _x0000_s1212 _x0000_s1213 _x0000_s1214 _x0000_s1215 _x0000_s1216 _x0000_s1217 _x0000_s1218 _x0000_s1219 _x0000_s1220 _x0000_s1221 _x0000_s1222 _x0000_s1223 _x0000_s1224 _x0000_s1225 _x0000_s1226 _x0000_s1227 _x0000_s1228 _x0000_s1229 _x0000_s1230 _x0000_s1231 _x0000_s1232 _x0000_s1233 _x0000_s1234 _x0000_s1235 _x0000_s1236 _x0000_s1237 _x0000_s1238 _x0000_s1239 _x0000_s1240 _x0000_s1241 _x0000_s1242 _x0000_s1243 _x0000_s1244 _x0000_s1245 _x0000_s1246 _x0000_s1247 _x0000_s1248 _x0000_s1249 _x0000_s1250 _x0000_s1251 _x0000_s1252 _x0000_s1253 _x0000_s1254 _x0000_s1255 _x0000_s1256 _x0000_s1257 _x0000_s1258 _x0000_s1259 _x0000_s1260"> <img width=«31» height=«76» src=«ref-1_296653760-273.coolpic» v:shapes="_x0000_i1114"> <img width=«13» height=«16» src=«ref-1_296654033-194.coolpic» v:shapes="_x0000_i1115"> <img width=«55» height=«76» src=«ref-1_296654227-347.coolpic» v:shapes="_x0000_i1116"> (3)
причем по смыслу задачи
t1<img width=«13» height=«16» src=«ref-1_296642108-191.coolpic» v:shapes="_x0000_i1117"> 0, t3 <img width=«13» height=«16» src=«ref-1_296642108-191.coolpic» v:shapes="_x0000_i1118"> 0. (4)
<img width=«32» height=«28» src=«ref-1_296654956-391.coolpic» v:shapes="_x0000_s1274">Переписав неравенства (2) и (3) в виде:
<img width=«182» height=«24» src=«ref-1_296655347-364.coolpic» v:shapes="_x0000_s1273">
<img width=«209» height=«135» src=«ref-1_296655711-704.coolpic» v:shapes="_x0000_i1108">
приходим к задаче ЛП: максимизировать (1) при условиях (5), (6) и (4).
Эту задачу легко решить графически: см. рис. 1. Программа ²расшивки²имеет вид
t1=<img width=«40» height=«41» src=«ref-1_296656415-255.coolpic» v:shapes="_x0000_i1119">, t2=0, t3=<img width=«32» height=«41» src=«ref-1_296656670-237.coolpic» v:shapes="_x0000_i1120">
и прирост прибыли составит 519<img width=«16» height=«41» src=«ref-1_296656907-222.coolpic» v:shapes="_x0000_i1121">.
Сводка результатов приведена в таблице
Таблица 1
сj
36
14
25
50
b
x4+i
yi
ti
4
3
4
5
208
6
46 5/12
aij
2
5
2
107
13
3
1
2
5
181
4
60 1/3
xj
27
20
1972
519 2/3
Dj
8
7
§7. Транспортная задача линейного программирования
Транспортная задача формулируется следующим образом. Однородный продукт, сосредоточенный в m
пунктах производства (хранения) в количествах а1, а2,..., аmединиц, необходимо распределить между nпунктами потребления, которым необходимо соответственно b1, b2,..., bnединиц. Стоимость перевозки единицы продукта из i-го пункта отправления в j-ый пункт назначения равна сij и известна для всех маршрутов. Необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы по доставке продуктов были минимальными.
Обозначим через хijколичество груза, планируемого к перевозке от i-го поставщика j-му потребителю. При наличии баланса производства и потребления
<img width=«89» height=«47» src=«ref-1_296657129-386.coolpic» v:shapes="_x0000_i1109"> (1)
математическая модель транспортной задачи будет выглядеть так:
найти план перевозок
<img width=«31» height=«2» src=«ref-1_296657515-153.coolpic» v:shapes="_x0000_s1548"><img width=«26» height=«2» src=«ref-1_296657668-159.coolpic» v:shapes="_x0000_s1542"> Х = (хij), i = 1,m; j = 1,n
минимизирующий общую стоимость всех перевозок
<img width=«101» height=«47» src=«ref-1_296657827-387.coolpic» v:shapes="_x0000_i1110"> (2)
при условии, что из любого пункта производства вывозится весь продукт
<img width=«132» height=«47» src=«ref-1_296658214-381.coolpic» v:shapes="_x0000_i1111"> (3)
и любому потребителю доставляется необходимое количество груза
<img width=«129» height=«45» src=«ref-1_296658595-382.coolpic» v:shapes="_x0000_i1112"> (4)
причем по смыслу задачи
х11> 0 ,… ., xmn > 0. (5)
Для решения транспортной задачи чаще всего применяется метод потенциалов. Пусть исходные данные задачи имеют вид
А(а1, а2, а3) = (54; 60; 63); В(b1, b2, b3, b4)= (41; 50; 44; 30); С = <img width=«20» height=«75» src=«ref-1_296658977-248.coolpic» v:shapes="_x0000_i1122"> <img width=«13» height=«67» src=«ref-1_296659225-231.coolpic» v:shapes="_x0000_i1123"> <img width=«13» height=«67» src=«ref-1_296659456-231.coolpic» v:shapes="_x0000_i1124"><img width=«12» height=«21» src=«ref-1_296608571-169.coolpic» v:shapes="_x0000_i1130"><img width=«20» height=«75» src=«ref-1_296659856-248.coolpic» v:shapes="_x0000_i1125">
Общий объем производства åаi = 55+60+63 = 178больше, требуется всем потребителям åbi = 42+50+44+30 = 166, т.е. имеем открытую модель транспортной задачи. Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления 178-166 = 12 единиц, причем тарифы на перевозку в этот пункт условимся считать равными нулю, помня, что переменные, добавляемые к левым частям неравенств для превращения их в уравнения, входят в функцию цели с нулевыми коэффициентами.
Первое базисное допустимое решение легко построить по правилу ²северо-западного угла².
<img width=«137» height=«40» src=«ref-1_296660104-396.coolpic» v:shapes="_x0000_s1550"> Потребление
b1 =41
b2 =50
b3 =44
b4 =30
b5 =12
<img width=«339» height=«91» src=«ref-1_296660500-965.coolpic» v:shapes="_x0000_s1672 _x0000_s1557 _x0000_s1560 _x0000_s1564 _x0000_s1572 _x0000_s1573 _x0000_s1574 _x0000_s1575 _x0000_s1576 _x0000_s1577 _x0000_s1578 _x0000_s1579 _x0000_s1580 _x0000_s1581 _x0000_s1582 _x0000_s1583 _x0000_s1584 _x0000_s1585 _x0000_s1589 _x0000_s1643 _x0000_s1644 _x0000_s1645 _x0000_s1646 _x0000_s1647 _x0000_s1648 _x0000_s1649 _x0000_s1650 _x0000_s1651 _x0000_s1652 _x0000_s1653 _x0000_s1654 _x0000_s1655 _x0000_s1656">Производство
а1 =54
41
13
p1 =0
a2 =60
37
23
p2 =
a3 =63
*
21
30
12
p3 =
q1 =
q2 =
q3 =
q4 =
q5 =
Следует иметь в виду, что по любой транспортной таблице можно восстановить соответствующий предпочитаемый эквивалент системы уравнений (3), (4), а в таблице записаны лишь правые части уравнений, причем номер клетки показывает, какая неизвестная в соответствующем уравнении является базисной. Так как в системе (3), (4) ровно m + n — 1 линейно независимых уравнений, то в любой транспортной таблице должно быть m + n — 1занятых клеток.
Обозначим через
m<img width=«224» height=«20» src=«ref-1_296661465-394.coolpic» v:shapes="_x0000_i1126">)
<img width=«28» height=«2» src=«ref-1_296661859-156.coolpic» v:shapes="_x0000_s1545"><img width=«28» height=«2» src=«ref-1_296661859-156.coolpic» v:shapes="_x0000_s1544">вектор симплексных множителей или потенциалов. Тогда
Dij= mAij — сij i = 1,m; j = 1,n
откуда следует
<img width=«27» height=«3» src=«ref-1_296662171-160.coolpic» v:shapes="_x0000_s1547"><img width=«27» height=«3» src=«ref-1_296662331-159.coolpic» v:shapes="_x0000_s1546">Dij= pi + qj — cij i = 1,m; j = 1,n (6)
Один из потенциалов можно выбрать произвольно, так как в системе (3), (4) одно уравнение линейно зависит от остальных. Положим, что р1 = 0. Остальные потенциалы находим из условия, что для базисных клеток <img width=«70» height=«21» src=«ref-1_296662490-224.coolpic» v:shapes="_x0000_i1127">. В данном случае получаем
D11= 0, p1 + q1 — c11= 0, 0+q1 -1 = 0, q1 = 1
D12= 0, p1 + q2 — c12= 0, 0+q2 -4 = 0, q2 = 4
D22= 0, p2 + q2 — c22= 0, р2+4-6 = 0, р2 = 2
и т.д., получим: q3=0, p3=6, q4= 1, q5= -6.
Затем по формуле (6) вычисляем оценки всех свободных клеток:
D21= p2 + q5 — c21= 2+1-3 = 0
D31= p3 + q1 — c31= 6+1-2 = 5
D32= 5; D13= -3; D14= -1; D24= -2; D15= -6; D25= -4.
Находим наибольшую положительную оценку
max (<img width=«70» height=«27» src=«ref-1_296662714-251.coolpic» v:shapes="_x0000_i1128">) = 5 = <img width=«28» height=«24» src=«ref-1_296662965-206.coolpic» v:shapes="_x0000_i1129">
Для найденной свободной клетки 31 строим цикл пересчета — замкнутую ломаную линию, соседние звенья которой взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы, одна из вершин находится в данной свободной клетке, а все остальные — в занятых клетках. Это будет 31-11-12-22-23-33. Производим перераспределение поставок вдоль цикла пересчета
41
13
41-r
13+r
20
34
<img width=«32» height=«12» src=«ref-1_296663171-216.coolpic» v:shapes="_x0000_s1640"><img width=«42» height=«12» src=«ref-1_296663387-218.coolpic» v:shapes="_x0000_s1639">
37
23
37-r
23+r
16
44
21
r
21-r
21
<img width=«46» height=«33» src=«ref-1_296663605-229.coolpic» v:shapes="_x0000_i1131">= 21
Получаем второе базисное допустимое решение:
bj
b1 =41
b2 =5
b3 =44
b4 =30
b5=12
ai
а1 =54
20
34
*
p1 =0
a2 =60
16
44
p2 =2
a3 =63
21
30
12
p3 =1
q1 =1
q2 =4
q3 =
q4 =6
q5= -1
Находим новые потенциалы, новые оценки. Наибольшую положительную оценку будет иметь свободная клетка 14. Для нее строим цикл пересчета 14-11-31-34 производим перераспределение
20
20-r
r
20
<img width=«61» height=«12» src=«ref-1_296663834-218.coolpic» v:shapes="_x0000_s1638"><img width=«60» height=«12» src=«ref-1_296664052-218.coolpic» v:shapes="_x0000_s1637">21
30
21+r
30-r
42
10
rmax= 20
и получаем третье базисное допустимое решение. Продолжаем процесс до те пор, пока не придем к таблице, для которой все
<img width=«27» height=«2» src=«ref-1_296664270-155.coolpic» v:shapes="_x0000_s1543"> <img width=«28» height=«2» src=«ref-1_296664425-153.coolpic» v:shapes="_x0000_s1549">
Dij£0 i = 1,m; j = 1,n
Читателю не составит труда проверить, что будет оптимальным базисное допустимое решение
<img width=«57» height=«75» src=«ref-1_296664578-285.coolpic» v:shapes="_x0000_i1132"> <img width=«21» height=«65» src=«ref-1_296664863-259.coolpic» v:shapes="_x0000_i1133"> <img width=«21» height=«67» src=«ref-1_296665122-218.coolpic» v:shapes="_x0000_i1134"> <img width=«28» height=«75» src=«ref-1_296665340-250.coolpic» v:shapes="_x0000_i1135">
§8.Динамическое программирование.
Распределение капитальных вложений
Динамическое программирование — это вычислительный метод для решения задач управления определенной структуры. Данная задача с 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) мы считаем заданными, заметив, что их определение — довольно трудоемкая экономическая задача.
Воспользуемся методом динамического программирования для решения этой задачи.
Введем параметр состояния и определим функцию состояния. За параметр состояния xпримем количество рублей, выделяемых нескольким предприятиям, а функцию состояния Fk(x) определим как максимальную прибыль на первых k предприятиях, если они вместе получают xрублей. Параметр xможет изменяться от 0 до b. Если из x рублей k-е предприятие получит xk рублей, то каково бы ни было это значение, остальные x— xk рублей естественно распределить между предприятиями от первого до (К-1)-го так, чтобы была получена максимальная прибыль Fk-1(x— xk). Тогда прибыль k предприятий будет равна fk(xk) + Fk-1(x— xk). Надо выбрать такое значение xk между 0 и x, чтобы эта сумма была максимальной, и мы приходим к рекуррентному соотношению
Fk(x)=max{fk(xk) + Fk-1(x-xk)}
0 £xk £x
для k = 2, 3, 4,…, n. Если же k=1, то
F1(x) = f1(x)
Рассмотрим конкретный пример. Пусть производственное объединение состоит из четырех предприятий (n=4). Общая сумма капитальных вложений равна 700 тыс. рублей (b=700), выделяемые предприятиям суммы кратны 100 тыс. рублей. Значения функций fj(xj) приведены в таблице 1, где, например, число 88 означает, что если третье предприятие получит 600 тыс. руб. капитальных вложений, то прирост прибыли на этом предприятии составит 88 тыс. руб.
Таблица I
<img width=«570» height=«120» src=«ref-1_296665590-1722.coolpic» v:shapes="_x0000_i1136">
Прежде всего заполняем табл. 2. Значения f2(x2) складываем со значениями F1(x— x2) = f1(x— x2) и на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение <img width=«39» height=«23» src=«ref-1_296667312-245.coolpic» v:shapes="_x0000_i1137">. Заполняем таблицу 3.
Продолжая процесс, табулируем функции F3(x), <img width=«20» height=«27» src=«ref-1_296667557-221.coolpic» v:shapes="_x0000_i1138">(x) и т.д. В табл. 6 заполняем только одну диагональ для значения x= 700. Наибольшее число на этой диагонали:
Zmax = 155 тыс. руб.,
причем четвертому предприятию должно быть выделено
х*4 = <img width=«16» height=«23» src=«ref-1_296667778-207.coolpic» v:shapes="_x0000_i1139">4 (700) = 300 тыс. руб.
На долю остальных трех предприятий остается 400 тыс. руб. Из табл. 5 видно, что третьему предприятию должно быть выделено
x*3 = <img width=«16» height=«23» src=«ref-1_296667778-207.coolpic» v:shapes="_x0000_i1140">3 (700-x*4) = <img width=«16» height=«23» src=«ref-1_296667778-207.coolpic» v:shapes="_x0000_i1141">3 (400) = 200 тыс. руб.
Продолжая обратный процесс, находим
x*2 = <img width=«16» height=«23» src=«ref-1_296667778-207.coolpic» v:shapes="_x0000_i1142">2 (700 — x*4 — x*3) = <img width=«16» height=«23» src=«ref-1_296667778-207.coolpic» v:shapes="_x0000_i1143">2 (200) = 100 тыс. руб.
На долю первого предприятия остается
x*1 = 700 — x*4 — x*3 — x*2 = 100 тыс. руб.
Таким образом, наилучшим является следующее распределение капитальных вложений по предприятиям:
x*1 =100; x*2 =100; x*3 = 200; x*4 = 300.
Оно обеспечивает производственному объединению наибольший воможный прирост прибыли 155 тыс. руб.
Студенту рекомендуется проверить выполнение равенства
f1(x*1) + f2(x*2) + f3(x*3) + f4(x*4) = z max
продолжение
--PAGE_BREAK--<img width=«186» height=«65» src=«ref-1_296668813-716.coolpic» v:shapes="_x0000_s1026">Таблица 2
x— x2
0 100 200 300 400 500 600 700
x2
F1(x— x2)
f2(x2)
0 20 34 46 53 55 60 60
0 20* 34 46 53 55 60 60
100
18
18 38* 52* 64 71 73 78
200
29
29 49 63 75 82 84
300
45
45 65* 79 91 98
400
62
62 82* 96 108
500
78
78 98* 112*
600
90
90 110
700
98
98 .
Таблица 3
x
0 100 200 300 400 500 600 700
F2(x)
0 20 38 52 65 82 98 112
`<img width=«25» height=«28» src=«ref-1_296669529-225.coolpic» v:shapes="_x0000_i1144">(x)
0 0 100 100 300 400 500 500
<img width=«191» height=«64» src=«ref-1_296669754-792.coolpic» v:shapes="_x0000_s1201"> Таблица 4
x— x3
0 100 200 300 400 500 600 700
x3
F2(x— x3)
f3(x3)
0 20 38 52 65 82 98 112
<img width=«290» height=«166» src=«ref-1_296670546-1307.coolpic» v:shapes="_x0000_s1731 _x0000_s1703 _x0000_s1704 _x0000_s1705 _x0000_s1706 _x0000_s1707 _x0000_s1708 _x0000_s1709 _x0000_s1710 _x0000_s1711 _x0000_s1712 _x0000_s1713 _x0000_s1714 _x0000_s1715 _x0000_s1716 _x0000_s1717 _x0000_s1718 _x0000_s1719 _x0000_s1720 _x0000_s1721 _x0000_s1722 _x0000_s1723 _x0000_s1724 _x0000_s1725 _x0000_s1726 _x0000_s1727 _x0000_s1728 _x0000_s1729 _x0000_s1730">
0 20 38 52 65 82 98 112
100
25
25* 45* 63* 77 90 107 123
200
41
41 61 79* 93 106 123
300
52
52 72 94* 112 126
400
74
74 94* 112* 126*
500
82
82 102 120
600
88
88 106
700
90
90 .
Таблица 5
x
0 100 200 300 400 500 600 700
F3(x)
0 25 45 63 79 94 112 126
<img width=«20» height=«27» src=«ref-1_296667557-221.coolpic» v:shapes="_x0000_i1145">(x)
0 100 100 100 200 400 400 400
Таблица 6
<img width=«190» height=«61» src=«ref-1_296672074-869.coolpic» v:shapes="_x0000_s1203">
x— x4
0 100 200 300 400 500 600 700
x4
F3(x— x4)
f4(x4)
0 25 45 63 79 94 112 126
126
100
30
142
200
52
146
300
76
155*
400
90
153
500
104
149
600
116
141
700
125
125 .
§9. Динамическая задача управления производством
и запасами
Предприятие производит партиями некоторые изделия. Предположим, что оно получило заказы на n месяцев. Размеры заказов значительно меняются от месяца к месяцу. Поэтому иногда лучше выполнять одной партией заказы нескольких месяцев, а затем хранить изделия, пока они не потребуются, чем выполнять заказ в тот именно месяц, когда этот заказ должен быть отправлен. Необходимо составить план производства на указанные n месяцев с учетом затрат на производство и хранение изделий. Обозначим:
xj — число изделий, производимых в j -й месяц;
yj — величина запаса к началу j го месяца (это число не содержит изделий, произведенных в j -м месяце);
dj — число изделий, которые должны быть отгружены в j -й месяц;
fj (xj,yj+1) — затраты на хранение и производство изделий в j -м месяце.
Будем считать, что величины запасов к началу первого месяца y1 и к концу последнего yn+1 заданы.
Задача состоит в том, чтобы найти план производства
(x1, x2, ..., xn) (1)
компоненты которого удовлетворяют условиям материального баланса
<img width=«22» height=«2» src=«ref-1_296672943-158.coolpic» v:shapes="_x0000_s1086"> xj + yj — dj = yj+1 j = 1,n (2)
и минимизируют суммарные затраты за весь планируемый период
<img width=«143» height=«56» src=«ref-1_296673101-431.coolpic» v:shapes="_x0000_i1148"> (3)
причем по смыслу задачи
<img width=«20» height=«2» src=«ref-1_296673532-160.coolpic» v:shapes="_x0000_s1103">
xj³0, yj³0, j = 1,n (4)
Прежде чем приступить к решению поставленной задачи, заметим, что для любого месяца j величина yj+1 запаса к концу месяца должна удовлетворять ограничениям
0 £yj+1£dj+1 + dj+2 +… + dn (5)
т.е. объем производимой продукции xj на этапе j может быть настолько велик, что запас yj+1 удовлетворяет спрос на всех последующих этапах, но не
имеет смысла иметь yj+1 больше суммарного спроса на всех последующих этапах. Кроме того, из соотношений (2) и (4) непосредственно следует, что переменная xj должна удовлетворять ограничениям
0 £xj£dj + yj+1 (6)
Следует также заметить, что переменные xj, yj могут принимать только целые неотрицательные значения, т.е. мы получили задачу целочисленного нелинейного программирования.
Будем решать задачу (1)-(6) методом динамического программирования.
Введем параметр состояния и составим функцию состояния.
За параметр состояния xпримем наличный запас в конце k -го месяца
x= yk+1 (7)
а функцию состояния Fk(x) определим как минимальные затраты за первые k месяцев при выполнении условия (5)
<img width=«236» height=«67» src=«ref-1_296673692-670.coolpic» v:shapes="_x0000_i1149"> (8)
где минимум берется по неотрицательным целым значениям x1,...,xk, удовлетворяющим условиям
<img width=«44» height=«2» src=«ref-1_296674362-153.coolpic» v:shapes="_x0000_s1087"> xj + yj — dj = yj+1 j = 1, k-1 (9)
xk + yk — dk = x (10)
Учитывая, что
<img width=«444» height=«65» src=«ref-1_296674515-1001.coolpic» v:shapes="_x0000_i1146"> (11)
и величина запаса yk к концу (k-1) периода, как видно из уравнения (10), равна
yk = x+ dk — xk (12)
приходим к рекуррентному соотношению
<img width=«378» height=«67» src=«ref-1_296675516-780.coolpic» v:shapes="_x0000_i1147"> (13)
где минимум берется по единственной переменной xk, которая, согласно (6) может изменяться в пределах
0 £xk£dk + x (14)
принимая целые значения, причем верхняя граница зависит от значений параметра состояния, изменяющегося в пределах
0 £x£dk+1 + dk+2 +… + dn (15)
а индекс k может принимать значения
k = 2, 3, 4,…, n (16)
Если k=1, то
F1(x= y2) = min f1(x1, x) (17)
x1
где
x1 = x+ d1 — y1 (18)
0£x£d2 + d3 +… + dn (19)
т.е. на начальном этапе при фиксированном уровне y1 исходного запаса каждому значению параметра x отвечает только одно значение переменной x1, что несколько уменьшает объем вычислений.
Применив известную вычислительную процедуру динамического программирования, на последнем шаге (при k = n) находим значение последней компоненты xn* оптимального решения, а остальные компоненты определяем как
<img width=«305» height=«64» src=«ref-1_296676296-740.coolpic» v:shapes="_x0000_i1154"> (20)
Рассмотрим более подробно функции затрат fj(xj, yj+1) и рекуррентные соотношения. Пусть
jj(xj) = axj2 + bxj + c
jj(xj) — затраты на производство (закупку) xj единиц продукции на этапе j;
hj — затраты на хранение единицы запаса, переходящей из этапа j в этап j+1.
Тогда затраты на производство и хранение на этапе j равны
fj(xj, yj+1) = jj(xj) + hj yj+1= axj2 + bxj + c + hj yj+1. (21)
Выведенные ранее рекуррентные соотношения динамического программирования для решения задачи управления производством и запасами в нашем случае принимают вид:
<img width=«414» height=«42» src=«ref-1_296677036-819.coolpic» v:shapes="_x0000_i1150"> (22)
где
k = 2, 3,…, n (23)
0 £yk+1£dk+1 + dk+1 +… + dn (24)
0 £xk£dk + yk+1 (25)
yk = yk+1 + dk — xk (26)
Если же k=1, то
<img width=«288» height=«113» src=«ref-1_296677855-1034.coolpic» v:shapes="_x0000_i1151">
Остается заметить, что полезно обозначить выражение в фигурных скобках через
Wk(xk, yk+1) = axj2 + bxj + c + hkyk+1 + Fk-1(yk) (31)
и записать рекуррентное соотношение (22) в виде
Fk(x=yk+1) = min Wk(xk, yk+1) (32)
xk
где минимум берется по целочисленной переменной xk, удовлетворяющей условию (25).
Пример.Рассмотрим трехэтапную систему управления запасами с дискретной продукцией и динамическим детерминированным спросом.
Пусть спрос (заявки) потребителей на нашу продукцию составляют: на первый этап d1=3единицы, на второй – d2=2, на третий - d3=4единицы. К началу первого этапа на складе имеется только 2 единицы продукции, т.е. начальный уровень запаса равен y1=2. Затраты на хранение единицы продукции на разных этапах различны и составляют соответственно h1=1, h2=3, h3=2. Затраты на производство xjединиц продукции на j-м этапе определяются функцией
jj(xj) = xj2 + 5xj + 2 <img width=«45» height=«25» src=«ref-1_296678889-233.coolpic» v:shapes="_x0000_i1152"> (33)
т.е. а=1; b=5; с=2. Требуется указать, сколько единиц продукции на отдельных этапах следует производить, чтобы заявки потребителей были удовлетворены, а наши общие затраты на производство и хранение за все три этапа были наименьшими.
Исходные данные задачи можно кратко записать одной строкой:
d1 d2 d3 a b c h1 h2 h3 y1
1 2 4 1 5 2 1 3 2 2
Воспользовавшись рекуррентными соотношениями, последовательно вычисляем
F1 (x= y2), F2 (x= y3), ..., Fk (x= yk+1), ... и соответственно находим <img width=«16» height=«23» src=«ref-1_296667778-207.coolpic» v:shapes="_x0000_i1155">1 (x= y2), <img width=«16» height=«23» src=«ref-1_296667778-207.coolpic» v:shapes="_x0000_i1156">2 (x= y3 ), ..., `<img width=«16» height=«23» src=«ref-1_296667778-207.coolpic» v:shapes="_x0000_i1157">k (x= yk+1),…
Положим k = 1. Согласно (27) имеем
<img width=«239» height=«33» src=«ref-1_296679743-495.coolpic» v:shapes="_x0000_i1153"> (34)
Учтем, что согласно (28) параметр состояния x= у2 может принимать целые значения на отрезке
0 <img width=«13» height=«16» src=«ref-1_296654033-194.coolpic» v:shapes="_x0000_i1160"> у2<img width=«13» height=«16» src=«ref-1_296654033-194.coolpic» v:shapes="_x0000_i1161"> d2 + d3
0 <img width=«13» height=«16» src=«ref-1_296654033-194.coolpic» v:shapes="_x0000_i1162"> y2<img width=«13» height=«16» src=«ref-1_296654033-194.coolpic» v:shapes="_x0000_i1163"> 2 + 4
т.е.
у2 = 0, 1, 2, 3, 4, 5, 6.
При этом, вообще говоря, каждому значению параметра состояния должна отвечать определенная область изменения переменной x1, характеризуемая условием (29)
0 <img width=«13» height=«16» src=«ref-1_296654033-194.coolpic» v:shapes="_x0000_i1164"> х1<img width=«13» height=«16» src=«ref-1_296654033-194.coolpic» v:shapes="_x0000_i1165"> 3 + у2
Однако, на первом этапе объем производства х1 не может быть меньше единицы, так как спрос d1 = 3, а исходный запас у1 = 2. Более того, из балансового уравнения
х1 + у1 — d1 = у2
непосредственно следует, что объем производства связан со значением параметра состояния x= у2 соотношением
x1 = y2 + d1 — y1 = y2 + 3 — 2 = y2 +1 (35)
В этом и состоит особенность первого этапа. Если задан уровень запаса к началу первого этапа, то каждому значению у2 отвечает единственное значение х1 и потому
F1(x= y2) = W1(x1, y2)
Придавая у2 различные целые значения от 0 до 6 и учитывая (35), находим
y2 = 0, x1 = 0+1 = 1, W1(1;0) = 12 + 5×1 + 2 + 1×0 = 8
y2 = 1, x1 = 1+1 = 2, W1(2;1) = 22 + 5×2 + 2 + 1×1 = 17
и т.д. Значения функции состояния F1(x) представлены в табл. 1
Таблица 1
x= y2
1
2
3
4
5
6
<img width=«24» height=«10» src=«ref-1_296681402-286.coolpic» v:shapes="_x0000_s1272">F1 (x= y2)
8
17
28
41
56
73
92
x1(x=y2)
1
2
3
4
5
6
7
Переходим ко второму этапу. Полагаем k = 2 и табулируем функцию
F2(x= y3) с помощью соотношения (32)
<img width=«448» height=«71» src=«ref-1_296681688-1066.coolpic» v:shapes="_x0000_i1158"> (37)
Здесь минимум берется по единственной переменной х2, которая может изменяться, согласно (25), в пределах
0 £x2£d2 + y3 или 0 £x2£2 + y3 (38)
где верхняя граница зависит от параметра состояния x= у3, который, согласно (15), принимает значения на отрезке
0 £y3£d3 , т.е. 0 £y3£4 (39)
а аргумент у2 в последнем слагаемом справа в соотношении (37) связан с х2 и у3 балансовым уравнением
x2 + y2 — d2 = y3
откуда следует
y2 = y3 + d2 — x2 = y3 + 2 — x2 (40)
Придавая параметру состояния различные значения от 0 до 4, будем последовательно вычислять W2 (x2, x), а затем определять F2(x) и <img width=«16» height=«23» src=«ref-1_296667778-207.coolpic» v:shapes="_x0000_i1166">2(x).
Положим, например x= у3 = 2. Тогда, согласно (38),
0 £x2£4,
т.е. переменная х2 может принимать значения: 0, 1, 2, 3, 4, а каждому значению х2 отвечает определенное значение у2, вычисляемое по формуле (40):
у2 = 4 — х2
Последовательно находим:
если x2 = 0, то y2 = 4-0 = 4, W2 (0,2) = 02 + 5×0 + 2 + 3×2 +F1(4) = 8 + 56 = 64,
x2 = 1, y2 = 4-1 = 3, W2 (1,2) = 12 + 5×1 + 2 + 3×2 + F1(3) = 14 + 41 = 55,
x2 = 2, y2 = 4-2 =2, W2 (2,2) = 22 + 5×2 + 2 + 3×2 + F1(2) = 22 + 28 = 50,
x2 = 3, y2 = 4-3 = 1, W2 (3,2) = 32 + 5×3 + 2 + 3×2 + F1(1) = 32 + 17 = 49*,
x2 = 4, y2 = 4-4 = 0, W2 (3,2) = 42 + 5×4 + 2 + 3×2 + F1(0) = 44 + 8 = 52.
Наименьшее из полученных значений W2 есть F2 (2), т.е.
F2 (x= y3 = 2) = min W2(x2,2) = min (64, 55, 50, 49, 52) = 49,
x2
причем минимум достигается при значении х2, равном
`<img width=«16» height=«23» src=«ref-1_296667778-207.coolpic» v:shapes="_x0000_i1167">2 (x= y3 = 2) = 3
Аналогично для значения параметра x= у3 = 3, проведя необходимые вычисления, найдем
F2 (x= y3 = 3) = 63; `<img width=«16» height=«23» src=«ref-1_296667778-207.coolpic» v:shapes="_x0000_i1168">2 (x= y3 = 3) = 3.
Процесс табулирования функции F2 (x= y3) приведен в табл. 2, а результаты табулирования сведены в табл. 3.
продолжение
--PAGE_BREAK--Таблица 3
x= у3
1
2
3
4
F2 (x= y3)
24
36
49
63
78
<img width=«24» height=«23» src=«ref-1_296683375-218.coolpic» v:shapes="_x0000_i1175">(x= y3)
2
2
3
3
4
Переходим к следующему этапу. Полагаем k=3 и табулируем функцию F3 (x= y4):
<img width=«370» height=«43» src=«ref-1_296683593-768.coolpic» v:shapes="_x0000_i1159">
Вычисляем значение функции состояния только для одного значения аргумента x= у4 = 0, так как не хотим оставлять продукцию в запас в конце исследуемого периода. Процесс вычислений приведен в табл. 4. Получаем
F3 (x= y4) = min W3(x3,0) = min (80, 71, 65, 62, 62) = 62,
x3
причем минимум достигается при двух значениях переменной х3, равных
`<img width=«16» height=«23» src=«ref-1_296667778-207.coolpic» v:shapes="_x0000_i1176">3 (x= y4 = 0) = 3 или `<img width=«16» height=«23» src=«ref-1_296667778-207.coolpic» v:shapes="_x0000_i1177">3 (x= y4 = 0) = 4.
Таким образом, мы получили не только минимальные общие затраты на производство и хранение продукции, но и последнюю компоненту оптимального решения. Она равна
<img width=«21» height=«31» src=«ref-1_296684775-220.coolpic» v:shapes="_x0000_i1178">= 3 или <img width=«28» height=«31» src=«ref-1_296684995-226.coolpic» v:shapes="_x0000_i1169">= 4.
Рассмотрим случай, когда на последнем этапе планируем выпускать три единицы продукции
<img width=«21» height=«31» src=«ref-1_296684775-220.coolpic» v:shapes="_x0000_i1179">= 3.
Остальные компоненты оптимального решения найдем по обычным правилам метода динамического программирования. Чтобы найти предпоследнюю компоненту, учтем, что
х3 + у3 — d3 = y4
или
3 + у3 — 4 = 0,
откуда
у3 = 1.
Из таблицы (3) значений <img width=«47» height=«28» src=«ref-1_296685441-289.coolpic» v:shapes="_x0000_i1180"> находим
<img width=«160» height=«28» src=«ref-1_296685730-398.coolpic» v:shapes="_x0000_i1170">
Аналогично, продолжая двигаться в обратном направлении и учтя, что
х2 + у2 — d2 = y3
--PAGE_BREAK--Предположим сначала, что игроки озабочены только максимизацией среднего дохода за партию игры – обычная цель в таких играх. Тогда игроки будут играть со своими оптимальными стратегиями: <img width=«105» height=«25» src=«ref-1_296694445-315.coolpic» v:shapes="_x0000_i1206"> – Первый игрок и <img width=«100» height=«25» src=«ref-1_296694760-317.coolpic» v:shapes="_x0000_i1207"> – Второй.
Математическое ожидание с. в. <img width=«59» height=«21» src=«ref-1_296690638-272.coolpic» v:shapes="_x0000_i1208"> называется ценой игры, обозначим ее <img width=«13» height=«15» src=«ref-1_296695349-189.coolpic» v:shapes="_x0000_i1209">.
Но что же назвать риском всей игры?
Вычислим дисперсию выигрыша Первого при оптимальных стратегиях игроков.
<img width=«371» height=«55» src=«ref-1_296695538-877.coolpic» v:shapes="_x0000_i1210">.
Так как <img width=«136» height=«47» src=«ref-1_296696415-437.coolpic» v:shapes="_x0000_i1211">, а через <img width=«17» height=«25» src=«ref-1_296696852-207.coolpic» v:shapes="_x0000_i1212"> сумма обозначена <img width=«64» height=«45» src=«ref-1_296697059-329.coolpic» v:shapes="_x0000_i1213">.
Заметим, что в сумме <img width=«60» height=«47» src=«ref-1_296697388-322.coolpic» v:shapes="_x0000_i1214"> можно оставить лишь те слагаемые, у которых <img width=«47» height=«27» src=«ref-1_296697710-244.coolpic» v:shapes="_x0000_i1215">
Заметим теперь, что если Первый играет со стратегией <img width=«20» height=«20» src=«ref-1_296697954-202.coolpic» v:shapes="_x0000_i1216">, а Второй отвечает <img width=«13» height=«20» src=«ref-1_296698156-189.coolpic» v:shapes="_x0000_i1217">-й чистой стратегией, то выигрыш первого есть с.в. с рядом распределения:
<img width=«60» height=«24» src=«ref-1_296690910-273.coolpic» v:shapes="_x0000_i1218">
<img width=«23» height=«25» src=«ref-1_296691183-210.coolpic» v:shapes="_x0000_i1219">
…
<img width=«19» height=«25» src=«ref-1_296691393-206.coolpic» v:shapes="_x0000_i1220">
…
<img width=«24» height=«25» src=«ref-1_296691599-212.coolpic» v:shapes="_x0000_i1221">
<img width=«23» height=«25» src=«ref-1_296691811-212.coolpic» v:shapes="_x0000_i1222">
…
<img width=«23» height=«27» src=«ref-1_296692023-214.coolpic» v:shapes="_x0000_i1223">
…
<img width=«27» height=«27» src=«ref-1_296692237-219.coolpic» v:shapes="_x0000_i1224">
продолжение
--PAGE_BREAK--Если <img width=«21» height=«27» src=«ref-1_296699891-205.coolpic» v:shapes="_x0000_i1225"> есть оптимальная стратегия Первого, а <img width=«45» height=«27» src=«ref-1_296700096-242.coolpic» v:shapes="_x0000_i1226">, то из теории матричных игр с нулевой суммой известно, что выигрыш Первого при таких стратегиях по-прежнему равен цене игры <img width=«13» height=«15» src=«ref-1_296695349-189.coolpic» v:shapes="_x0000_i1227">, а дисперсия выигрыша Первого при этом равна <img width=«124» height=«45» src=«ref-1_296700527-383.coolpic» v:shapes="_x0000_i1228">, то есть равна <img width=«49» height=«27» src=«ref-1_296700910-244.coolpic» v:shapes="_x0000_i1229">. Таким образом, что происходит с риском выигрыша Первого, можно понять, сравнив дисперсию при оптимальных стратегиях <img width=«121» height=«47» src=«ref-1_296701154-394.coolpic» v:shapes="_x0000_i1230"> и дисперсию <img width=«85» height=«27» src=«ref-1_296701548-279.coolpic» v:shapes="_x0000_i1231"> или величины <img width=«87» height=«47» src=«ref-1_296701827-356.coolpic» v:shapes="_x0000_i1232"> и <img width=«55» height=«25» src=«ref-1_296702183-246.coolpic» v:shapes="_x0000_i1233">. Пусть <img width=«147» height=«27» src=«ref-1_296702429-379.coolpic» v:shapes="_x0000_i1234"> Как легко понять, если среди <img width=«79» height=«27» src=«ref-1_296702808-301.coolpic» v:shapes="_x0000_i1235"> есть разные числа, то <img width=«63» height=«19» src=«ref-1_296703109-258.coolpic» v:shapes="_x0000_i1236">
Теперь можно сделать следующий вывод:
Чуть-чуть отойдя от своей оптимальной стратегии (смотрите ниже Пример) и таким образом почти не уменьшив свой выигрыш, Первый может значительно уменьшить свой риск. При этом уменьшается и риск Второго, что отвечает и его интересам.
Чисто математически можно сказать, что в описанной ситуации риск выигрыша Первого не зависит от его стратегии непрерывно.
Рассмотрим подробно пример матричной игры с матрицей <img width=«33» height=«17» src=«ref-1_296703367-230.coolpic» v:shapes="_x0000_i1237">. Как известно, общий случай в окрестности оптимальных стратегий игроков сводится к анализу такой игры.
Пример. Пусть матрица игры есть <img width=«63» height=«48» src=«ref-1_296703597-291.coolpic» v:shapes="_x0000_i1238">. Графическое решение этой игры показано на рисунке 1. <img width=«12» height=«23» src=«ref-1_296608233-169.coolpic» v:shapes="_x0000_i1239">
<img width=«630» height=«201» src=«ref-1_296704057-4297.coolpic» v:shapes="_x0000_s1780 _x0000_s1754 _x0000_s1745 _x0000_s1746 _x0000_s1747 _x0000_s1748 _x0000_s1749 _x0000_s1750 _x0000_s1751 _x0000_s1752 _x0000_s1753 _x0000_s1778">
Цена игры <img width=«56» height=«19» src=«ref-1_296708354-239.coolpic» v:shapes="_x0000_i1240">, оптимальные стратегии игроков есть <img width=«104» height=«24» src=«ref-1_296708593-299.coolpic» v:shapes="_x0000_i1241">, <img width=«103» height=«24» src=«ref-1_296708892-304.coolpic» v:shapes="_x0000_i1242">. Дисперсия выигрыша Первого при оптимальных стратегиях <img width=«76» height=«19» src=«ref-1_296709196-273.coolpic» v:shapes="_x0000_i1243">, т. е. риск игры равен примерно 1. Далее вычисления дают <img width=«80» height=«23» src=«ref-1_296709469-283.coolpic» v:shapes="_x0000_i1244">, <img width=«51» height=«24» src=«ref-1_296709752-249.coolpic» v:shapes="_x0000_i1245">; <img width=«75» height=«23» src=«ref-1_296710001-271.coolpic» v:shapes="_x0000_i1246">,<img width=«71» height=«24» src=«ref-1_296710272-272.coolpic» v:shapes="_x0000_i1247"> Примерная, но достаточно точная зависимость риска Первого в малой окрестности его оптимальной стратегии показана на рис. 2.
<img width=«560» height=«117» src=«ref-1_296710544-2215.coolpic» v:shapes="_x0000_s1782 _x0000_s1755 _x0000_s1756 _x0000_s1757 _x0000_s1759 _x0000_s1760 _x0000_s1761 _x0000_s1762 _x0000_s1763 _x0000_s1764 _x0000_s1765 _x0000_s1766 _x0000_s1767 _x0000_s1768 _x0000_s1811">
Как видно из рис. 2 при отходе Первого от своей оптимальной стратегии вправо, т. е. при увеличении вероятности x выбора им 1-й строки. Второй начинает отвечать 1-й чистой стратегией и риск Первого скачком увеличивается до <img width=«51» height=«24» src=«ref-1_296709752-249.coolpic» v:shapes="_x0000_i1248">, а при отходе Первого от своей оптимальной стратегии влево Второй переходит на свою 2-ю чистую стратегию и риск Первого скачком снижается до <img width=«71» height=«24» src=«ref-1_296710272-272.coolpic» v:shapes="_x0000_i1249">
<img width=«611» height=«137» src=«ref-1_296713280-2486.coolpic» v:shapes="_x0000_s1783 _x0000_s1740 _x0000_s1744 _x0000_s1735 _x0000_s1736 _x0000_s1737 _x0000_s1738 _x0000_s1739 _x0000_s1741 _x0000_s1742 _x0000_s1769 _x0000_s1770 _x0000_s1734 _x0000_s1743">
Аналогичное верно и в отношении Второго. Кратко повторим. Примерная, но достаточно точная зависимость риска Второго в малой окрестности его оптимальной стратегии показана на рис. 3. Как видно из рис. 3 при отходе второго от своей оптимальной стратегии вправо, т. е. при увеличении вероятности у выбора им 1-й строки Первый начинает отвечать 2-й чистой стратегией и риск Второго скачком уменьшается до <img width=«73» height=«24» src=«ref-1_296715766-284.coolpic» v:shapes="_x0000_i1250">, а при отходе второго от своей оптимальной стратегии влево Первый переходит на свою 1-ю чистую стратегию и риск Второго скачком увеличивается до <img width=«67» height=«24» src=«ref-1_296716050-268.coolpic» v:shapes="_x0000_i1251">
Пусть <img width=«168» height=«24» src=«ref-1_296716318-411.coolpic» v:shapes="_x0000_i1252">. Эту величину и можно назвать риском всей игры. Однако играть с таким риском можно лишь при согласии обеих сторон. Для анализируемой игры <img width=«59» height=«21» src=«ref-1_296716729-242.coolpic» v:shapes="_x0000_i1253"> и игроки для достижения такого риска должны играть так: Первый играет со своей оптимальной стратегией <img width=«73» height=«24» src=«ref-1_296716971-271.coolpic» v:shapes="_x0000_i1254"> 3,5), а Второй должен использовать 2-ю чистую стратегию.
§12.Анализ доходности и риска финансовых операций
Финансовой называется операция, начальное и конечное состояния которой имеют денежную оценку и цель проведения которой заключается в максимизации дохода — разности между конечной и начальной оценками.
Почти всегда финансовые операции проводятся в условиях неопределенности и потому их результат невозможно предсказать заранее. Поэтому финансовые операции рискованны, т.е. при их проведении возможны как прибыль так и убыток (или не очень большая прибыль по сравнению с той, на что надеялись проводившие эту операцию).
Как оценить операцию с точки зрения ее доходности и риска?
Существует несколько разных способов. Наиболее распространенным является представление дохода операции как случайной величины и оценка риска операции как среднего квадратического отклонения этого случайного дохода.
Рассмотрим какую-нибудь операцию, доход которой есть случайная величина Q. Средний ожидаемый доход `Q — это математическое ожидание с.в. Q: <img width=«83» height=«29» src=«ref-1_296717242-305.coolpic» v:shapes="_x0000_i1259">, где pi есть вероятность получить доход qi. А среднее квадратическое отклонение (СКО) <img width=«79» height=«27» src=«ref-1_296717547-301.coolpic» v:shapes="_x0000_i1260"> — это мера разбросанности возможных значений дохода вокруг среднего ожидаемого дохода. Вполне разумно считать sколичественной мерой риска операции и обозначить r. Напомним, что дисперсия
D[Q] = M [(Q — `Q)2] = M [Q2] — `Q2.
Рассмотрим четыре операции Q1, Q2, Q3, Q,4. Найдем средние ожидаемые доходы `Qi и риски ri операций.
Ряды распределения, средние ожидаемые доходы и риски:
Q1
:
5
2
8
4
`Q1 = 29/6 »4.81
r1 »1.77
1/2
1/6
1/6
1/6
Q2
:
2
3
4
12
`Q2 = 25/6 »4.16
r2 »3.57
1/2
1/6
1/6
1/6
Q3
:
8
5
3
10
`Q3 = 7
r3 »2.30
1/2
1/6
1/6
1/6
Q4
:
1
4
2
8
`Q4 = 17/6 »2.81
r4 »2.54
1/2
1/6
1/6
1/6
Напомним, как находить `Q и r.
`Q1 =åqipi = 5*1/2+2*1/6+8*1/6+4*1/6=29/6
j
<img width=«11» height=«3» src=«ref-1_296717848-154.coolpic» v:shapes="_x0000_s1140">r1 = M [Q21 ] — (Q1)2; M [Q21] = 25*1/2+4*1/6+64*1/6+16*1/6=159/6;
Q21 = 841/36; D [Q1] = (159*6-841)/36 = 113/36; <img width=«136» height=«25» src=«ref-1_296718002-334.coolpic» v:shapes="_x0000_i1261">
<img width=«226» height=«129» src=«ref-1_296718336-794.coolpic» v:shapes="_x0000_s1128 _x0000_s1129 _x0000_s1130 _x0000_s1131 _x0000_s1132 _x0000_s1133 _x0000_s1134 _x0000_s1135">Нанесем средние ожидаемые доходы `Q и риски r на плоскость — доход откладываем по горизонтали, а риски по вертикали (см. рис.):
Получили 4 точки. Чем правее точка (`Q, r), тем более доходная операция, чем точка выше — тем более она рисковая. Значит, нужно выбирать точку правее и ниже. Точка (`Q¢, r¢) доминирует точку (`Q, r) если `Q¢³`Q и r¢£ r. В нашем случае 1-я операция доминирует 2-ю, 3-я доминирует 2-ю и 3-я доминирует 4-ю. Но 1-я и 3-я операции несравнимы — доходность 3-й больше, но и риск ее тоже больше.
Точка, не доминируемая никакой другой называется оптимальной по Парето, а множество всех таких точек называется множеством оптимальности по Парето. Легко видеть, что если из рассмотренных операций надо выбирать лучшую, то ее обязательно надо выбрать из операций, оптимальных по Парето.
Для нахождения лучшей операции иногда применяют подходящую взвешивающую формулу, которая для пар (`Q, r) дает одно число, по которому и определяют лучшую операцию. Например, пусть взвешивающая формула есть j(Q)= 2×Q — r. Тогда получаем:
j(Q1)= 2*4.81-1.77 = 7.85; j(Q2)= 4.75; j(Q3)= 11.70; j(Q4)= 3.08
Видно, что 3-я операция — лучшая, а 4-я — худшая.
§13. Задача формирования оптимального
портфеля ценных бумаг.
На финансовом рынке обращается, как правило, множество ценных бумаг: государственные ценные бумаги, акции частных фирм, векселя и т.п. Ценная бумага удостоверяет возможность получения некоторого дохода. В общем случае владелец получит некоторый случайный доход.
Из характеристик ценных бумаг наиболее значимы две: эффективность и рискованность. Эффективность E есть некоторый обобщенный показатель дохода или прибыли. Будем считать E случайной величиной, ее математическое ожидание есть mЕ.
При исследовании финансового рынка дисперсию обычно называют вариацией V и рискованность обычно отождествляется со Средним Квадратическим Отклонением. Таким образом, V=D[E]= M[( E- mЕ )2 ] и s =<img width=«28» height=«23» src=«ref-1_296719130-223.coolpic» v:shapes="_x0000_i1262">.
Рассмотрим общую задачу распределения капитала, который участник рынка хочет потратить на покупку ценных бумаг, по различным видам ценных бумаг.
Пусть xi — доля капитала, потраченная на закупку ценных бумаг i-го вида. Пусть Ei — эффективность (можно считать, доход за некоторый период времени) ценных бумаг i-го вида, стоящих одну денежную единицу. Через Vij будем обозначать ковариацию ценных бумаг i-го и j -го видов (или корреляционный момент Kij). Пусть mi — математическое ожидание эффективности Ei и si= <img width=«33» height=«27» src=«ref-1_296719353-239.coolpic» v:shapes="_x0000_i1263">, где Vii — вариация или дисперсия этой эффективности Ei. Рискованность ценной бумаги i-го вида отождествим со средним квадратическим отклонением si.
Набор ценных бумаг, находящихся у участника рынка, называется его портфелем. Эффективность портфеля ( в простейшем случае это доход, приносимый ценными бумагами портфеля за какой-нибудь промежуток времени), вообще говоря, есть случайная величина, обозначим ее через Ep, тогда ожидаемое значение этой эффективности mp =M[Ep]=<img width=«60» height=«40» src=«ref-1_296719592-294.coolpic» v:shapes="_x0000_i1264">. Дисперсия портфеля есть D[Ep ]= <img width=«75» height=«43» src=«ref-1_296719886-344.coolpic» v:shapes="_x0000_i1265">. Величина <img width=«91» height=«29» src=«ref-1_296720230-310.coolpic» v:shapes="_x0000_i1266"> может быть названа риском портфеля. Обычно D[Ep] обозначается Vp. Итак, мы выразили эффективность и риск портфеля через эффективности составляющих его ценных бумаг и их ковариации.
Каждый владелец портфеля ценных бумаг сталкивается с дилеммой: хочется иметь эффективность побольше, а риск поменьше. Однако поскольку «нельзя поймать двух зайцев сразу», необходимо сделать определенный выбор между эффективностью и риском.
Математическая формализация задачи формирования оптимального
портфеля такова:
Найти xi, минимизирующие вариацию эффективности портфеля
Vp = <img width=«75» height=«43» src=«ref-1_296719886-344.coolpic» v:shapes="_x0000_i1267">,
при условии, что обеспечивается заданное значение ожидаемой
эффективности портфеля mp, т.е.
mp =<img width=«60» height=«40» src=«ref-1_296719592-294.coolpic» v:shapes="_x0000_i1268">.
поскольку xi — доли, то в сумме они должны составлять единицу:
<img width=«40» height=«39» src=«ref-1_296721178-265.coolpic» v:shapes="_x0000_i1269">=1 .
Решение (оптимальное) этой задачи обозначим *. Если x*i >0, то это означает рекомендацию вложить долю x*i наличного капитала в ценные бумаги i-го вида. Если же x*i <0, то содержательно это означает провести операцию «short sale». Если такие операции невозможны, значит необходимо ввести ограничения xi ³0. Что такое операция «short sale» ?
Если x*i < 0, то инвестор, формирующий портфель, обязуется через какое-то время поставить ценные бумаги i-го вида (вместе с доходом, какой они бы принесли их владельцу за это время). За это сейчас он получает их денежный эквивалент. На эти деньги он покупает более доходные ценные бумаги и получает по ним доход и оказывается в выигрыше!
Если на рынке есть безрисковые бумаги (к таким можно с некоторой натяжкой отнести государственные ценные бумаги), то решение задачи об оптимальном портфеле сильно упрощается и приобретает замечательное новое качество.
Пусть m0 — эффективность безрисковых бумаг, а x0 — доля капитала в них вложенного. Пусть mr — средняя ожидаемая эффективность и Vr, sr — вариация (дисперсия), СКО эффективности рисковой части портфеля, в рисковую часть портфеля вложено (1-x0) часть всего капитала. Тогда ожидаемая эффективность всего портфеля mp =x0m0+(1-x0)mr, вариация портфеля Vp =(1-x0)2 Vr и риск портфеля sp=(1-x0) sr (считается, что безрисковые бумаги некоррелированы с остальными). Исключая x0, получим
mp = m0+sp(m -m0)/ sr,
т.е. ожидаемая эффективность портфеля линейно зависит от его риска.
Рассмотрим задачу об оптимальном портфеле в этом случае. Рисковые виды ценных бумаг будем нумеровать числами от 1 до n .
<img width=«125» height=«52» src=«ref-1_296721443-404.coolpic» v:shapes="_x0000_i1288">
x0m0 + <img width=«53» height=«49» src=«ref-1_296721847-311.coolpic» v:shapes="_x0000_i1289"> = mp
x0+ <img width=«43» height=«51» src=«ref-1_296722158-295.coolpic» v:shapes="_x0000_i1290"> = 1
Изложим теперь окончательное решение этой задачи.
Пусть V — матрица ковариаций рисковых видов ценных бумаг, X=(xi), M=(mi) — векторы-столбцы долей xi капитала, вкладываемых в i-й вид рисковых ценных бумаг и ожидаемых эффективностей этого вида, i=1,.., n. Пусть также I — n-мерный вектор-столбец, компоненты которого есть 1. Тогда оптимальное значение долей xi есть
<img width=«337» height=«50» src=«ref-1_296722453-702.coolpic» v:shapes="_x0000_i1270">.
Здесь V-1 — матрица, обратная к V. В числителе дроби стоит число, в знаменателе, если выполнить все действия (верхний индекс Т означает транспонирование вектора-столбца), тоже получится число, причем константа, определяемая рынком и не зависящая от инвестора, V-1(M-m0I) — вектор-столбец размерности n . Видно, что этот вектор не зависит от эффективности портфеля mp. Таким образом, вектор долей рисковых видов ценных бумаг пропорциональный этому вектору также не зависит от mp. Следовательно, структура рисковой части портфеля не зависит от mp. Однако сумма компонент вектора X* зависит от mp, именно, компоненты вектора X* пропорционально увеличиваются с ростом mp, поэтому доля x0 безрисковых вложений будет при этом сокращаться.
Пример. Сформировать оптимальный портфель заданной эффективности из трех видов ценных бумаг: безрисковых эффективности 2 и некоррелированных рисковых ожидаемой эффективности 4 и 10 и рисками 2 и 4. Как устроена рисковая часть оптимального портфеля? При какой ожидаемой эффективности портфеля возникает необходимость в операции «short sale» и с какими ценными бумагами?
Решение. Итак, m0 =2, M=<img width=«35» height=«49» src=«ref-1_296723155-255.coolpic» v:shapes="_x0000_i1291">, V=<img width=«57» height=«49» src=«ref-1_296723410-289.coolpic» v:shapes="_x0000_i1292">. Зададимся эффективностью портфеля mp. Теперь надо найти обратную матрицу к матрице V. Это просто: V-1 = <img width=«91» height=«49» src=«ref-1_296723699-307.coolpic» v:shapes="_x0000_i1293">. Вычислим знаменатель:
<img width=«595» height=«49» src=«ref-1_296724006-988.coolpic» v:shapes="_x0000_i1294">.
Итак, вектор долей рисковых бумаг есть X* =((mз-2)/5)<img width=«45» height=«49» src=«ref-1_296724994-279.coolpic» v:shapes="_x0000_i1295">.Таким образом, рисковые доли должны быть одинаковы и каждая из них равна (mз-2)/10. Следовательно, x*0 =1-(mр-2)/5. Понятно, что необходимость в операции «short sale» возникнет, если x*0< 0, т.е. когда mр > 7 .
Можно доказать, что риск оптимального портфеля в зависимости от его доходности при наличии безрисковых бумаг равен <img width=«87» height=«25» src=«ref-1_296725273-305.coolpic» v:shapes="_x0000_i1271">,где <img width=«259» height=«31» src=«ref-1_296725578-506.coolpic» v:shapes="_x0000_i1272">
Постановку задачи формирования оптимального портфеля(1) можно словами сформулировать так:
Сформировать портфель минимального риска из всех имеющих эффективность не менее заданной.
Но столь же естественна и задача формирования портфеля максимальной эффективности из всех имеющих риск не более заданного, т.е. найти <img width=«16» height=«24» src=«ref-1_296726084-198.coolpic» v:shapes="_x0000_i1273">,максимизирующие ожидаемую эффективность портфеля
<img width=«147» height=«36» src=«ref-1_296726282-376.coolpic» v:shapes="_x0000_i1274">
при условии, что обеспечивается значение риска портфеля не более заданного, т.е.
<img width=«113» height=«37» src=«ref-1_296726658-363.coolpic» v:shapes="_x0000_i1275">
поскольку <img width=«21» height=«24» src=«ref-1_296727021-198.coolpic» v:shapes="_x0000_i1276"> – доли, то в сумме они должны составлять единицу:<img width=«63» height=«36» src=«ref-1_296727219-269.coolpic» v:shapes="_x0000_i1277">
Если на рынке есть безрисковые бумаги, то в такой постановке задача формирования такого оптимального портфеля имеет решение, очень похожее на(2): Оптимальное значение долей <img width=«17» height=«21» src=«ref-1_296727488-198.coolpic» v:shapes="_x0000_i1278"> рисковых бумаг есть
<img width=«359» height=«47» src=«ref-1_296727686-678.coolpic» v:shapes="_x0000_i1279"> (3)
Можно доказать, что эффективность портфеля максимальной эффективности в зависимости от заданного его риска <img width=«16» height=«25» src=«ref-1_296728364-206.coolpic» v:shapes="_x0000_i1280"> равна <img width=«67» height=«25» src=«ref-1_296728570-267.coolpic» v:shapes="_x0000_i1281">.
§14. Принятие решений в условиях неопределенности
Предположим, что ЛПР (Лицо, Принимающее Решения) рассматривает несколько возможных решений <img width=«65» height=«20» src=«ref-1_296728837-236.coolpic» v:shapes="_x0000_i1282">. Ситуация неопределенна, понятно лишь, что наличествует какой-то из вариантов <img width=«67» height=«21» src=«ref-1_296729073-236.coolpic» v:shapes="_x0000_i1283">. Если будет принято <img width=«9» height=«17» src=«ref-1_296729309-185.coolpic» v:shapes="_x0000_i1284">-e решение, а ситуация есть<img width=«13» height=«20» src=«ref-1_296698156-189.coolpic» v:shapes="_x0000_i1285">-я , то фирма, возглавляемая ЛПР, получит доход <img width=«19» height=«25» src=«ref-1_296729683-215.coolpic» v:shapes="_x0000_i1286">. Матрица <img width=«58» height=«25» src=«ref-1_296729898-276.coolpic» v:shapes="_x0000_i1287"> называется матрицей последствий (возможных решений). Какое же решение нужно принять ЛПР? В этой ситуации полной неопределенности могут быть высказаны лишь некоторые рекомендации предварительного характера. Они не обязательно будут приняты ЛПР. Многое будет зависеть, например, от его склонности к риску. Но как оценить риск в данной схеме?
Допустим, мы хотим оценить риск, который несет<img width=«9» height=«17» src=«ref-1_296729309-185.coolpic» v:shapes="_x0000_i1296">-e решение. Нам неизвестна реальная ситуация. Но если бы ее знали, то выбрали бы наилучшее решение, т.е. приносящее наибольший доход. Т.е. если ситуация есть<img width=«13» height=«20» src=«ref-1_296698156-189.coolpic» v:shapes="_x0000_i1297">-я, то было бы принято решение, дающее доход <img width=«81» height=«29» src=«ref-1_296730548-289.coolpic» v:shapes="_x0000_i1298">.
Значит, принимая<img width=«9» height=«17» src=«ref-1_296729309-185.coolpic» v:shapes="_x0000_i1299">-e решение мы рискуем получить не <img width=«19» height=«25» src=«ref-1_296731022-214.coolpic» v:shapes="_x0000_i1300">, а только <img width=«19» height=«25» src=«ref-1_296729683-215.coolpic» v:shapes="_x0000_i1301">, значит принятие<img width=«9» height=«17» src=«ref-1_296729309-185.coolpic» v:shapes="_x0000_i1302">-го решения несет риск недобрать <img width=«75» height=«25» src=«ref-1_296731636-286.coolpic» v:shapes="_x0000_i1303">.Матрица <img width=«55» height=«25» src=«ref-1_296731922-264.coolpic» v:shapes="_x0000_i1304"> называется матрицей рисков.
Пример1. Пусть матрица последствий есть <img width=«135» height=«96» src=«ref-1_296732186-523.coolpic» v:shapes="_x0000_i1305">
продолжение
--PAGE_BREAK--Составим матрицу рисков. Имеем <img width=«243» height=«29» src=«ref-1_296732709-475.coolpic» v:shapes="_x0000_i1306"> Следовательно, матрица рисков есть
<img width=«127» height=«96» src=«ref-1_296733184-491.coolpic» v:shapes="_x0000_i1307">
А. Принятие решений в условиях полной неопределенности.
Не все случайное можно «измерить» вероятностью. Неопределенность– более широкое понятие. Неопределенность того, какой цифрой вверх ляжет игральный кубик отличается от неопределенности того, каково будет состояние российской экономики через15 лет. Кратко говоря, уникальные единичные случайные явления связаны с неопределенностью, массовые случайные явления обязательно допускают некоторые закономерности вероятностного характера.
Ситуация полной неопределенности характеризуется отсутствием какой бы то ни было дополнительной информации. Какие же существуют правила-рекомендации по принятию решений в этой ситуации?
Правило Вальда (правило крайнего пессимизма). Рассматривая <img width=«9» height=«17» src=«ref-1_296729309-185.coolpic» v:shapes="_x0000_i1308">-e решение будем полагать, что на самом деле ситуация складывается самая плохая, т.е. приносящая самый малый доход <img width=«77» height=«31» src=«ref-1_296733860-284.coolpic» v:shapes="_x0000_i1309">.
Но теперь уж выберем решение <img width=«13» height=«24» src=«ref-1_296734144-194.coolpic» v:shapes="_x0000_i1310"> с наибольшим <img width=«21» height=«24» src=«ref-1_296734338-202.coolpic» v:shapes="_x0000_i1311">. Итак, правило Вальда рекомендует принять решение <img width=«13» height=«24» src=«ref-1_296734144-194.coolpic» v:shapes="_x0000_i1312">,такое что
<img width=«191» height=«40» src=«ref-1_296734734-466.coolpic» v:shapes="_x0000_i1313">
Так, в вышеуказанном примере, имеем <img width=«176» height=«24» src=«ref-1_296735200-375.coolpic» v:shapes="_x0000_i1314">Теперь из чисел 2,2,3,1 находим максимальное. Это– 3 . Значит, правило Вальда рекомендует принять 3-е решение.
Правило Сэвиджа (правило минимального риска). При применении этого правила анализируется матрица рисков <img width=«55» height=«25» src=«ref-1_296731922-264.coolpic» v:shapes="_x0000_i1315">. Рассматривая<img width=«9» height=«17» src=«ref-1_296729309-185.coolpic» v:shapes="_x0000_i1316">-e решение будем полагать, что на самом деле складывается ситуация максимального риска <img width=«81» height=«31» src=«ref-1_296736024-288.coolpic» v:shapes="_x0000_i1317">
Но теперь уж выберем решение <img width=«13» height=«24» src=«ref-1_296734144-194.coolpic» v:shapes="_x0000_i1318"> с наименьшим <img width=«20» height=«24» src=«ref-1_296736506-206.coolpic» v:shapes="_x0000_i1319">. Итак, правило Сэвиджа рекомендует принять решение <img width=«13» height=«24» src=«ref-1_296734144-194.coolpic» v:shapes="_x0000_i1320">, такое что
<img width=«181» height=«40» src=«ref-1_296736906-427.coolpic» v:shapes="_x0000_i1321">
Так, в вышеуказанном примере, имеем <img width=«171» height=«24» src=«ref-1_296737333-382.coolpic» v:shapes="_x0000_i1322"> Теперь из чисел 8,6,5,7 находим минимальное. Это– 5. Значит правило Сэвиджа рекомендует принять 3-е решение.
Правило Гурвица (взвешивающее пессимистический и оптимистический подходы к ситуации). Принимается решение <img width=«9» height=«17» src=«ref-1_296729309-185.coolpic» v:shapes="_x0000_i1323">, на котором достигается максимум
<img width=«179» height=«30» src=«ref-1_296737900-424.coolpic» v:shapes="_x0000_i1324">
где<img width=«61» height=«19» src=«ref-1_296738324-248.coolpic» v:shapes="_x0000_i1325">. Значение <img width=«15» height=«19» src=«ref-1_296738572-198.coolpic» v:shapes="_x0000_i1326"> выбирается из субъективных соображений. Если <img width=«15» height=«19» src=«ref-1_296738572-198.coolpic» v:shapes="_x0000_i1327"> приближается к1, то правило Гурвица приближается к правилу Вальда, при приближении<img width=«15» height=«19» src=«ref-1_296738572-198.coolpic» v:shapes="_x0000_i1328"> к0, правило Гурвица приближается к правилу «розового оптимизма»(догадайтесь сами, что это значит). В вышеуказанном примере при<img width=«56» height=«19» src=«ref-1_296739166-241.coolpic» v:shapes="_x0000_i1329"> правило Гурвица рекомендует 2-е решение.
В. Принятие решений в условиях частичной неопределенности.
Предположим, что в рассматриваемой схеме известны вероятности <img width=«20» height=«25» src=«ref-1_296739407-212.coolpic» v:shapes="_x0000_i1330"> того, что реальная ситуация развивается по варианту <img width=«13» height=«20» src=«ref-1_296698156-189.coolpic» v:shapes="_x0000_i1331">. Именно такое положение называется частичной неопределенностью. Как здесь принимать решение? Можно выбрать одно из следующих правил.
Правило максимизации среднего ожидаемого дохода. Доход, получаемый фирмой при реализации<img width=«9» height=«17» src=«ref-1_296729309-185.coolpic» v:shapes="_x0000_i1332">-го решения, является случайной величиной <img width=«19» height=«24» src=«ref-1_296739993-215.coolpic» v:shapes="_x0000_i1333"> с рядом распределения
<img width=«20» height=«24» src=«ref-1_296740208-207.coolpic» v:shapes="_x0000_i1334">
…
<img width=«21» height=«24» src=«ref-1_296740415-209.coolpic» v:shapes="_x0000_i1335">
<img width=«19» height=«23» src=«ref-1_296740624-205.coolpic» v:shapes="_x0000_i1336">
…
<img width=«20» height=«24» src=«ref-1_296740829-211.coolpic» v:shapes="_x0000_i1337">
Математическое ожидание <img width=«47» height=«24» src=«ref-1_296741040-252.coolpic» v:shapes="_x0000_i1338"> и есть средний ожидаемый доход, обозначаемый также <img width=«19» height=«25» src=«ref-1_296741292-219.coolpic» v:shapes="_x0000_i1339">.Итак, правило рекомендует принять решение, приносящее максимальный средний ожидаемый доход.
Предположим, что в схеме из предыдущего п. вероятности есть(1/2, 1/6, 1/6, 1/6). Тогда <img width=«261» height=«25» src=«ref-1_296741511-489.coolpic» v:shapes="_x0000_i1340">
Максимальный средний ожидаемый доход равен7, соответствует 3-у решению.
Правило минимизации среднего ожидаемого риска. Риск фирмы при реализации<img width=«9» height=«17» src=«ref-1_296729309-185.coolpic» v:shapes="_x0000_i1341">-го решения, является случайной величиной <img width=«17» height=«24» src=«ref-1_296742185-211.coolpic» v:shapes="_x0000_i1342"> с рядом распределения
<img width=«16» height=«24» src=«ref-1_296742396-200.coolpic» v:shapes="_x0000_i1343">
…
<img width=«17» height=«24» src=«ref-1_296742596-202.coolpic» v:shapes="_x0000_i1344">
<img width=«19» height=«23» src=«ref-1_296740624-205.coolpic» v:shapes="_x0000_i1345">
…
<img width=«20» height=«24» src=«ref-1_296740829-211.coolpic» v:shapes="_x0000_i1346">
Математическое ожидание <img width=«45» height=«24» src=«ref-1_296743214-247.coolpic» v:shapes="_x0000_i1347"> и есть средний ожидаемый риск, обозначаемый также <img width=«17» height=«25» src=«ref-1_296743461-215.coolpic» v:shapes="_x0000_i1348">.Правило рекомендует принять решение, влекущее минимальный средний ожидаемый риск.
Вычислим средние ожидаемые риски при указанных выше вероятностях. Получаем <img width=«261» height=«25» src=«ref-1_296743676-456.coolpic» v:shapes="_x0000_i1349"> Минимальный средний ожидаемый риск равен7/6, соответствует 3-у решению.
Нанесем средние ожидаемые доходы <img width=«19» height=«24» src=«ref-1_296744132-215.coolpic» v:shapes="_x0000_i1350">и средние ожидаемые риски <img width=«17» height=«20» src=«ref-1_296744347-203.coolpic» v:shapes="_x0000_i1351"> на плоскость– доход откладываем по вертикали, а риски по горизонтали (см.рис.):
<img width=«12» height=«176» src=«ref-1_296744550-261.coolpic» v:shapes="_x0000_s1784">Получили4 точки. Чем выше точка <img width=«19» height=«24» src=«ref-1_296744132-215.coolpic» v:shapes="_x0000_i1352">
<img width=«47» height=«24» src=«ref-1_296745026-257.coolpic» v:shapes="_x0000_i1353">, тем более доходная операция, .Q3
чем точка правее– тем более она
рисковая. Значит, нужно выбирать
точку выше и левее. Точка <img width=«56» height=«24» src=«ref-1_296745283-265.coolpic» v:shapes="_x0000_i1354"> .Q1
доминирует точку <img width=«47» height=«24» src=«ref-1_296745026-257.coolpic» v:shapes="_x0000_i1355">, если <img width=«51» height=«24» src=«ref-1_296745805-249.coolpic» v:shapes="_x0000_i1356"> .Q2
и <img width=«47» height=«20» src=«ref-1_296746054-246.coolpic» v:shapes="_x0000_i1357"> и хотя бы одно из этих .Q4
неравенств строгое. В нашем случае
<img width=«223» height=«12» src=«ref-1_296746300-257.coolpic» v:shapes="_x0000_s1785">3-я операция доминирует все остальные. <img width=«17» height=«20» src=«ref-1_296744347-203.coolpic» v:shapes="_x0000_i1358">
Точка, не доминируемая никакой другой называется оптимальной по Парето, а множество всех таких точек называется множеством оптимальности по Парето. Легко видеть, что если из рассмотренных операций надо выбрать лучшую, то ее обязательно надо выбрать из операций, оптимальных по Парето. В нашем случае, множество Парето, т.е. оптимальных по Парето операций, состоит только из одной3-й операции.
Для нахождения лучшей операции иногда применяют подходящую взвешивающую формулу, которая для пар <img width=«47» height=«24» src=«ref-1_296745026-257.coolpic» v:shapes="_x0000_i1359"> дает одно число, по которому и определяют лучшую операцию. Например, пусть взвешивающая формула есть <img width=«105» height=«24» src=«ref-1_296747017-326.coolpic» v:shapes="_x0000_i1360">. Тогда получаем: <img width=«209» height=«23» src=«ref-1_296747343-419.coolpic» v:shapes="_x0000_i1361">
<img width=«287» height=«24» src=«ref-1_296747762-524.coolpic» v:shapes="_x0000_i1362">. Видно, что 3-я операция– лучшая, а 4-я– худшая.
С. Правило Лапласа.
Иногда в условиях полной неопределенности применяют правило Лапласа равновозможности, когда все вероятности <img width=«20» height=«25» src=«ref-1_296739407-212.coolpic» v:shapes="_x0000_i1363"> считают равными. После этого можно выбрать какое-нибудь из двух приведенных выше правил-рекомендаций принятия решений.
продолжение
--PAGE_BREAK--
еще рефераты
Еще работы по математике
Реферат по математике
Формирование понятия цилиндра
3 Сентября 2013
Реферат по математике
Контрольная по статистике
3 Сентября 2013
Реферат по математике
Статистичні методи оцінки вимірів в експериментальних дослідженнях
3 Сентября 2013
Реферат по математике
Оптимальные методы в совершенствовании планирования и управления производством
3 Сентября 2013