|
Реферат: Линейная Алгебра. Теория групп (Математика)
Лекции по общей алгебре
Лекция 1
Понятие бинарной алгебраической операции
Говорят, что на множестве S определена (бинарная) алгебраическая операция
(АО) « *», если для всяких двух его элементов x и y однозначно определен
элемент z=x*y называемый композицией или произведением элементов x и y.
Примерами таких операций могут служить обычные операции сложения, вычитания
или умножения на множестве всех действительных (или комплексных ) чисел,
операция умножения на множестве всех квадратных матриц данного порядка
,операция композиции на множестве всех перестановок из N элементов,
операция векторного перемножения на множестве всех векторов трехмерного
пространства.
Само по себе понятие АО является слишком общим, чтобы допускать сколько ни
будь глубокое изучение. В алгебраических теориях обычно рассматривают
операции, обладающие рядом дополнительных свойств. Перечислим некоторые из
них.
Свойство ассоциативности
[pic]
(1)
Во всех перечисленных выше примерах АО это свойство выполняется, за
исключением операции вычитания и операции векторного произведения.
Из свойства (1) вытекает, что произведение любого числа сомножителей
однозначно определено, так как не зависит от того, как в этом произведении
расставлены скобки, например
[pic]
Разумеется, при этом нельзя нарушать порядок сомножителей.
Наличие свойства ассоциативности позволяет определить степень любого
элемента с натуральным показателем. А именно:
[pic] (n сомножителей).
При этом выполняются обычные правила действий со степенями:
[pic] , [pic]
Свойство коммутативности
[pic] [pic]
(2)
Это свойство выполняется для сложения и умножения чисел, но нарушается для
умножения матриц и композиции перестановок.
Разумеется, из (2) вытекает, что в случае ассоциативной и коммутативной АО
мы имеем право переставлять любым способом сомножители в произведении
любого их числа.
Кроме того, в этом случае [pic]
Наличие нейтрального элемента
[pic] [pic]
(3)
Элемент n в этом случае называется нейтральным для АО (*).
Для операции сложения чисел нейтральным является число ноль, для операции
умножения - число единица. Для умножения матриц нейтральным элементом
будет единичная матрица, для композиции перестановок - тождественная
перестановка. В случае векторного перемножения векторов нейтральный элемент
отсутствует.
Отметим, что в (3) квантор существования предшествует квантору всеобщности,
то есть элемент n не зависит от выбора x.
В случае существования единственного нейтрального элемента и
ассоциативности операции можно определить степень с нулевым показателем:
[pic] для всякого элемента x. Упомянутые выше свойства степеней при этом
сохраняются.
Наличие обратного элемента
Это понятие имеет смысл в случае наличия нейтрального элемента для операции
(*).
Элемент [pic] называется обратным для элемента x, если
[pic]
(4)
Для сложения чисел обратный элемент существует для любого числа и равен
противоположному числу. Для умножения обратный элемент так и называется и
существует у любого числа, кроме 0. В случае умножения матриц обратный
элемент равен обратной матрице и существует в том случае, если эта матрица
невырождена, то есть ее определитель не равен нулю.
Элементы для которых существует обратный называются обратимыми. Из условия
(4) сразу вытекает, что элемент [pic] всегда обратим и обратным для него
будет исходный элемент x. Кроме того в случае ассоциативной операции
произведение двух обратимых элементов снова будет обратимым элементом и при
этом [pic]. В самом деле: [pic] и аналогично
[pic]
Если элемент [pic] определен однозначно, можно определить степени x с
отрицательным целым показателем, а именно:
[pic] , где m=1,2,... . При этом сохраняются обычные правила действий со
степенями.
Замечание
В конкретных алгебраических системах алгебраическая операция чаще всего
обозначается либо знаком (+) и называется сложением , либо знаком (.) и
называется умножением. В первом случае говорят об аддитивном, а во втором о
мультипликативном способе записи операции. Операция записанная аддитивно
как правило считается коммутативной. В этом случае вместо термина
«обратный» используется термин «противоположный элемент», который,
естественно, обозначается (-x), а вместо степени элемента говорят о его
кратных (nx).
Понятие группы
Определение
Множество G на котором определена бинарная операция (*) называется группой
(G,*), если выполняются условия:
1. Операция (*) ассоциативна.
2. Для операции существует нейтральный элемент.
3. Все элементы G обратимы.
Примеры групп
1. R - группа действительных чисел с операцией сложения. ( аддитивная
группа действительных чисел)
2. C - аддитивная группа комплексных чисел.
3. [pic]- группа ненулевых действительных чисел с операцией умножения (
мультипликативная группа действительных чисел)
4. [pic]- мультипликативная группа комплексных чисел.
5. [pic] - группа невырожденных матриц порядка n с действительными
элементами. (Аналогично, [pic])
6. [pic]- группа перестановок множества 1,2, ..., n.
Во всех этих примерах наличие свойств 1- 3 не вызывает сомнений.
Прежде чем приводить другие примеры групп укажем некоторые простейшие
свойства этих алгебраических систем. Во всех последующих формулировках
считается, что x, y, z, ... - элементы некоторой группы G.
1. Закон сокращения
[pic] (левое сокращение)
[pic] (правое сокращение)
Докажем, например, первый закон. Используем существование обратного
элемента [pic]и свойство ассоциативности операции.
[pic]
[pic]
[pic]
[pic]
y=z.
2. Единственность нейтрального элемента
В любой группе нейтральный элемент определен однозначно. В самом деле, если
[pic]и [pic] оба являются нейтральными, то по определению
[pic] и в то же время [pic], откуда [pic]. Единственный нейтральный
элемент группы G будет в дальнейшем обозначаться [pic] или просто e.
3. Единственность обратного элемента
Для каждого элемента x обратный элемент [pic] определен однозначно. В самом
деле, если элементы y и z являются обратными для x, то y*x=e и z*x=e,
откуда y*x=z*x и по закону сокращения y=z.
4. Признак нейтрального элемента
[pic]
Действительно, поскольку [pic], имеем [pic] , откуда по закону сокращения
получаем [pic].
5. Разрешимость любого уравнения первой степени (существование обратной
операции)
[pic] . Элемент z определен однозначно. (Его можно назвать «частным» от
деления y на x).
Имеем: [pic] и значит можно взять [pic]. Однозначность следует из закона
сокращения: [pic].
Понятие подгруппы
Определение
Группа [pic] называется подгруппой группы [pic], если, во первых
[pic] (как подмножество) и, во-вторых,
[pic] (то есть закон умножения на подмножестве H такой же как и во всем
множестве G.)
Тот факт, что [pic] является подгруппой в [pic] обозначается с помощью
символа включения: [pic] или просто [pic].
Примеры подгрупп.
1. Целые числа с операцией сложения (Z) образуют подгруппу в группе R,
которая, в свою очередь является подгруппой группы C.
2. Четные перестановки образуют подгруппу [pic] в группе [pic] всех
перестановок.
3. Матрицы с определителем 1 образуют подгруппу [pic] в группе [pic] всех
невырожденных матриц.
Чтобы проверить, будет ли данное подмножество H в G подгруппой надо,
очевидно, проверить следующие условия :
1. [pic]
2. [pic]
3. [pic].
Оказывается, что вместо трех этих условий достаточно проверить только одно.
Признак подгруппы
Непустое подмножество H в группе G будет подгруппой этой группы тогда и
только тогда, когда:
[pic]. (5)
Доказательство.
Условие (4) очевидно следует из 1 -3. Проверим обратное утверждение. Взяв
в (5) y=x, получим: [pic], то есть выполнено второе условие. Теперь
возьмем [pic], тогда получим: [pic] и таким образом условие 3. также
выполнено. Наконец, взяв в условии (5) [pic], получим [pic], то есть
условие 1.
Реферат на тему: Линейное и динамическое программирование
Линейное программирование.
Задача линейного оптимального планирования - один из важнейших
математических инструментов, используемых в экономике. Рассмотрим
предприятие, которое из m видов ресурсов производит n видов продукции.
Примем следующие обозначения:
i - номер группы ресурса (i=1,2, ..., m);
j - номер вида продукции (j=1,2, ..., n);
aij - количество единиц i-го ресурса, расходуемое на производство одной
единицы j-го вида продукции;
bij - запасы i-ro ресурса ;
xi — планируемое количество единиц j-й продукции;
cj -прибыли от реализации одной единицы j-го вида продукции;
X=(x1, x2,…, xn) - искомый план производства, называется допустимым если
имеющихся ресурсов достаточно. называется допустимым если имеющихся
ресурсов достаточно.
Рассматриваемая задача состоит в нахождении допустимого плана, дающего
максимальную прибыль из всех допустимых решения подобных задач, называемых
задачами линейного программирования.
Предположим, что предприятие может выпускать четыре вид продукции,
используя для этого три вида ресурсов. Известна технологически матрица А
затрат любого ресурса на единицу каждой продукции, вектор В объемов
ресурсов и вектор С удельной прибыли
48 30 29 10 удельные прибыли
нормы расхода 3 2 4 3 198
2 3 1 2 96
6 5 1 0 228
запасы ресурсов
Обозначим х1, х2, х3, х4 - число единиц 1-й, 2-й, 3-й, 4-й продукции,
которые планируем произвести. При этом можно использовать только имеющиеся
запасы ресурсов. Целью является получение максимальной прибыли. Получаем
следующую математическую модель оптимального планирования:
L(x1,x2,x3,x4)=48xl+30x2+29x3+10x4 (max
3х1+2х2+4х3+3х4?198
2х1+3х2+1х3+2х4?96
6х1+5х2+1х3+0х4?228
xj?0, jєN4
Для решения полученной задачи в каждое неравенство добавим
неотрицательную переменную. После этого неравенства превратятся в
равенства, в силу этого добавляемые переменные называются базисными.
Получается задача ЛП на максимум, все переменные неотрицательны, все
ограничения есть равенства и есть базисный набор переменных: х5 - в 1-м
равенстве, х6 - во 2-м и х7 - в 3-м. Теперь можно запускать симплекс-метод.
L(x1,x2,x3,x4)=48xl+30x2+29x3+10x4 (max
3х1+2х2+4х3+3х4+x5 =198
2х1+3х2+х3+2х4 +x6 =96
6х1+5х2+х3 +x7=228
xj?0, jєN7
Таблица N 1
|C |B |H |48 |30 |29 |10 |0 |0 |0 |
| | | |x1 |x2 |x3 |x4 |x5 |x6 |x7 |
|0 |x5 |198 |3 |2 |4 |3 |1 |0 |0 |
|0 |x6 |96 |2 |3 |1 |2 |0 |1 |0 |
|0 |x7 |228 |6 |5 |1 |0 |0 |0 |1 |
| | |0 |-48 |-30 |-29 |-10 |0 |0 |0 |
Если все оценочные коэффициенты (серый цвет) неотрицательны, то получено
оптимальное решение: базисные переменные равны свободным членам, остальные
равны 0. Если же есть отрицательный оценочный коэффициент, то находят самый
малый из них. Если в столбце коэффициентов над ним нет положительных, то
задача не имеет решения. Задача оптимального планирования не может быть
таковой, поэтому ищут минимальное отношение свободных членов столбца Н к
положительным коэффициентам указанного xj. В пересечении строки и столбца
получаем разрешающий элемент и затем строим новую таблицу.
Таблица N 2
|C |B |H |48 |30 |29 |10 |0 |0 |0 |
| | | |x1 |x2 |x3 |x4 |x5 |x6 |x7 |
|0 |х5 |84 |0 |-Ѕ |31/2 |3 |1 |0 |-3/6 |
|0 |x6 |20 |0 |11/3 |2/3 |2 |0 |1 |-2/6 |
|48 |х1 |38 |1 |5/6 |1/6 |0 |0 |0 |1/6 |
| | |1824 |0 |10 |-21 |-10 |0 |0 |-8 |
Таблица N 3
|C |B |H |48 |30 |29 |10 |0 |0 |0 |
| | | |x1 |x2 |x3 |x4 |x5 |x6 |x7 |
|29 |х3 |24 |0 |-1/7 |1 |6/7 |2/7 |0 |-1/7 |
|0 |x6 |4 |0 |13/7 |0 |13/7 |-4/21 |1 |-5/21 |
|48 |х1 |34 |1 |6/7 |0 |-1/7 |-1/21 |0 |4/21 |
| | |2328 |0 |7 |0 |8 |6 |0 |5 |
Оптимальное решение (производственная программа): Xоpt=(34; 0; 22; 0);
максимум целевой функции равен 2328.
Значение переменной с номером i большим 4-х есть остаток (i-4)-ro
ресурса. 'Гак как все оценочные коэффициенты неотрицательны, то получено
оптимальное решение: базисные переменные равны свободным членам, остальные
равны 0.
Следует обратить внимание на экономический смысл элементов последней
строки последней симплексной таблицы. Например, коэффициент ?2=7 при
переменной х2 показывает, что если произвести одну единицу продукции
второго вида (она не входит в оптимальную производственную программу), то
прибыль уменьшится на 7 единиц.
Заметим, что в рассматриваемом примере линейной производственной задачи
возможна самопроверка результата.
Воспользуемся тем, что в оптимальной производственной программе х2=0,
х4=0. Предположим, что вторую и четвертую продукции мы не намеревались
выпускать с самого начала. Рассмотрим задачу с оставшимися двумя
переменными, сохранив их нумерацию. Математическая модель задачи будет
выглядеть следующим образом:
L(x1,x3)=48xl+29x3 (max
3х1+4х3?198
2х1+ х3 ? 96
6х1+ х3?228
x1?0, x3?0
Задачу линейного программирования с двумя переменными можно решить
графически. Возьмем на плоскости систему координат: ось OX3 направим
горизонтально и вправо, ось OХ1 -вертикально и вверх. Каждое ограничение
задачи, раз оно линейное нестрогое неравенство, графически изображается
полуплоскостью, граничная прямая которой соответствует уже не неравенству,
а равенству. Допустимое множество задачи является пересечением всех этих
полуплоскостей и есть выпуклый многоугольник. Вторая из двух основных
теорем линейного программирования гласит: Если экстремум целевой функции
достигается на допустимом множестве, то функция принимает его в какой-то
вершине многоугольника-допустимого множества. Исходя из этой теоремы, найти
искомый экстремум можно просто перебрав вершины многоугольника и определив
ту, в которой значение функции экстремально. Чаще делают по-другому: строят
линию уровня целевой функции и двигают ее параллельно в направлении
экстремума, стараясь уловить последнюю точку пересечения линии с допустимым
множеством.
Двойственная задача линейного программирования
Задача линейного оптимального планирования - исходная в своей паре
симметричных двойственных задач. Вообще же другая задача в двойственной
паре строится так:
1)меняется тип экстремума целевой функции (mах на min и наоборот);
2)коэффициенты целевой функции одной задачи становятся свободными членами
другой задачи;
3)свободные члены одной задачи становятся коэффициентами целевой функции
двойственной задачи;
4)тип неравенств меняется (? на ? и наоборот);
5) каждый столбец одной задачи порождает строку ограничений другой задачи
и наоборот. В матрично-векторном виде обе задачи выглядят так:
исходная задача двойственная задача
L=(c,x)(max Z=(b,y)(min
Ax?b, x?0 Ya?c, y?0,
L(x1,x2,x3,x4)=48xl+30x2+29x3+10x4 (max
Z(y1,y2,y3,y4)=198yl+96y2+228y3 ( min
3х1+2х2+4х3+3х4?198 3y1+2y2+6y3?48
2х1+3х2+1х3+2х4?96 2y1+3y2+5y3?30
6х1+5х2+1х3+0х4?228 4y1+ y2 + y3?29
xj?0, jєN4 3y1+2y2?10
yj?0, jєN3
Решение полученной задачи легко найти с помощью второй основной
теоремы двойственности, согласно которой для оптимальных решений X(x1,
x2, x3, x4) и Y(y1, y2, y3) пары двойственных задач необходимо и достаточно
выполнение условий:
x1(3y1+2y2+6y3-48)=0 y1 (3х1+2х2+4х3+3х4)-198=0
x2(2y1+3y2+5y3-30)=0 y2 (2х1+3х2+1х3+2х4)-96=0
x3(4y1+1y2+1y3-29)=0 y3 (6х1+5х2+1х3+0х4)-228=0
x4(3y1+2y2+0y3-10)=0
В решении исходной задачи х1>0, х3>0, поэтому
3y1+2y2+6y3-48=0
4y1+1y2+1y3-29=0
Учитывая, что второй ресурс был избыточным и, согласно теореме
двойственности его оценка равна нулю – y2=0, то приходим к системе:
3y1+6y3-48=0
4y1+1y3-29=0
из которой следует, что y1=6; y3=5.
Таким образом получили двойственные оценки ресурсов: y1=6; y2=0; y3=5;
общая оценка всех ресурсов Z=198y1+228y3=2328.
Заметим, что полученное решение содержалось в последней строке
последней симплексной таблицы исходной задачи
Таблица N 3
|C |B |H |48 |30 |29 |10 |0 |0 |0 |
| | | |x1 |x2 |x3 |x4 |x5 |x6 |x7 |
|29 |х3 |24 |0 |-1/7 |1 |6/7 |2/7 |0 |-1/7 |
|0 |x6 |4 |0 |13/7 |0 |13/7 |-4/21 |1 |-5/21 |
|48 |х1 |34 |1 |6/7 |0 |-1/7 |-1/21 |0 |4/21 |
| | |2328 |0 |7 |0 |8 |6 |0 |5 |
Решение одной из пары двойственных задач можно найти, зная только ответ к
другой задаче и пользуясь 2-й теоремой двойственности: если i-e ограничение
одной из пары двойственных задач на компонентах оптимального решения есть
строгое неравенство, то оптимальное значение i-й переменной другой задачи
равно 0, или, что то же самое - если оптимальное значение j-й переменной
одной задачи строго положительно, то j-e ограничение другой из пары
двойственных задач на компонентах оптимального решения есть равенство.
Важен экономический смысл двойственных оценок. Двойственная оценка,
например, третьего ресурса у3=5 показывает, что добавление одной единицы
третьего ресурса обеспечит прирост прибыли на 5 единиц.
Расшивка "узких мест" производства
Таблица N 3
|C |B |H |48 |30 |29 |10 |0 |0 |0 |
| | | |x1 |x2 |x3 |x4 |x5 |x6 |x7 |
|29 |х3 |24 |0 |-1/7 |1 |6/7 |2/7 |0 |-1/7 |
|0 |x6 |4 |0 |13/7 |0 |13/7 |-4/21 |1 |-5/21 |
|48 |х1 |34 |1 |6/7 |0 |-1/7 |-1/21 |0 |4/21 |
| | |2328 |0 |7 |0 |8 |6 |0 |5 |
При выполнении оптимальной производственной программы первый и третий
ресурсы используются полностью, тем самым они образуют "узкие места"
производства. Будем их заказывать дополнительно. Пусть Т=( t1,t2,t3) -
вектор дополнительных объемов ресурсов. Так как мы будем использовать
найденные двойственные оценки ресурсов, то должно выполняться условие H+Q-
lТ?0, где Н - значения базисных переменных в последней симплексной таблице,
а Q-1 - обращенный базис, который образуют столбцы при балансовых
переменных в этой таблице. Задача состоит в том, чтобы найти вектор Т,
максимизирующий суммарный прирост прибыли W=6t1+5 t3 при условии сохранения
двойственных оценок ресурсов (и, следовательно, ассортимента выпускаемой
продукции), предполагая, что можно получить дополнительно не более 1/3
первоначального объема ресурсов каждого вида.
24 2/7 0 -1/7 t1 0
4 + -4/21 1 -5/21 0 ? 0
34 -1/21 0 4/21 t3 0
t1 198
0 ? 1/3 96
t3 228
t1?0, t3?0.
W=6t1+5t3 (max
-2/7 t1 + 1/7 t3 ? 24
4/21 t1 + 5/21 t3 ? 4
1/21 t1 - 4/21 t3 ? 34
t1?198/3, t3?228/3.
t1?0, t3?0.
Как видно, после графического решения (График 2) программа расшивки
приобретает вид:
t1=21, t2=0, t3=0
С новым количеством ресурсов: 198+21 219
b' = 96+0 = 96
228+0 228
у предприятия будет новая производственная программа.
Найдем h'=Q-1 b'
5/28 0 -1/7 219 30 (x3
-4/7 1 -1/7 96 = 0 (x6
-3/28 0 2/7 228 33 (x1
Теперь новая производственная программа имеет вид: X'оpt=(33;0;30;0). При
этом второй ресурс был использован полностью.
219
При наличии ресурсов b' = 96 производство наиболее выгодно, так
как
228
достигается max прибыль с использованием всех ресурсов. Также обратим
внимание на то, что производство продукции 1–го вида при заказе
дополнительных ресурсов необходимо будет уменьшить на 15 единиц, а
производство продукции 3–го вида – увеличить на единицу.
?Lmax=(Y,t)=6?21=126, где Y=(6;0;5); t(21;0;0)
L'max= ?Lmax+ Lmax=126+2328=2454.
Этот результат можно проверить, подставив значения х1 и х3 в первоначальную
целевую функцию: L'max=48xl+30x2+29x3+10x4=31?37+41?21=1147+861=2454.
Транспортная задача
Транспортная задача формулируется следующим образом. Однородный
продукт, сосредоточенный в т пунктах производства (хранения) в количествах
a1, а2,..., аm единиц, необходимо распределить между п пунктами
потребления, которым необходимо соответственно b1, b2,,…, bn единиц.
Стоимость перевозки единицы продукта из i-ro пункта отправления в j-й пункт
назначения равна cij и известна для всех маршрутов. Необходимо составить
план перевозок, при котором запросы всех пунктов потребления были бы
удовлетворены за счет имеющихся продуктов в пунктах производства и общие
транспортные расходы по доставке продуктов были минимальными.
Обозначим через xij количество груза, планируемого к перевозке от i-ro
поставщика j-му потребителю. При наличии баланса производства и потребления
[pic]
математическая модель транспортной задачи будет выглядеть так:
найти план перевозок
X=(xij), xij(0, i(Nm, j(Nn
минимизирующий общую стоимость всех перевозок
[pic]
при условии, что из любого пункта производства вывозится весь продукт
[pic] , i(Nm
и любому потребителю доставляется необходимое количество груза
[pic] , j(Nn
Для решения транспортной задачи чаще всего применяется метод
потенциалов. Пусть исходные данные задачи имеют вид
А(а1,а2,а3)=(40;45;70); В(b1,b2,b3)=(48;30;29;40); 3 6 4 3
С= 2 3 1 3
6 5 1 4
Общий объем производства (ai=40+45+70=155 больше, чем требуется всем
потребителям (bj=48+30+29+40=147, т.е. имеем открытую модель транспортной
задачи. Для превращения ее в закрытую вводим фиктивный пункт потребления с
объемом потребления 155-147=8 единиц, причем тарифы на перевозку в этот
пункт условимся считать равными нулю, помня, что переменные, добавляемые к
левым частям неравенств для превращения их в уравнения, входят в функцию
цели с нулевыми коэффициентами.
Первое базисное допустимое решение легко построить по правилу "северо-
западного угла".
Таблица 1
| |b1=48 |b2=30 |b3=29 |b4=40 |b5=8 | |
|Потребл | | | | | | |
|Произв | | | | | | |
|a1=40 |40 |6 | |* | |p1=0 |
| |3 | |4 |3 |0 | |
|a2=45 |8 2|30 |7 1| | |p2=-1 |
| | |3 | |3 |0 | |
|a3=70 | | |22 |40 |8 0|p3=-1 |
| |6 |5 |1 |4 | | |
| |q1=3 |q2=4 |q3=2 |q4=5 |q5=1 | |
Обозначим через ((p1, p2,…, pm, q1, q2,…, qn) вектор симплексных
множителей или потенциалов. Тогда (ij=(Aij-cij , i(Nm, j(Nn,
откуда следует
(ij=pi+qj-cij , i(Nm, j(Nn
Положим, что p1=0. Остальные потенциалы находим из условия, что для
базисных клеток (ij=0. В данном случае получаем
(11=0, p1+q1-c11=0, 0+q1-3=0, q1=3
(21=0, p2+q1-c21=0, p2+3-2=0, p2= -1
(23=0, p2+q3-c23=0, -1+q3-1=0, q3=2
аналогично, получим: q2=4, р3=-1, q4=5, q5=1.
Затем вычисляем оценки всех свободных клеток:
(12=p1+q2-c12=0+4-6= -2
(13=p1+q3-c13=0+2-4=-2
(14=2; (15=1; (24=1; (25=0; (31= -4; (32= -2
Находим наибольшую положительную оценку:
mах((ij >0)=2=(14,
Для найденной свободной клетки 14 строим цикл пересчета - замкнутую
ломаную линию, соседние звенья которой взаимно перпендикулярны, сами звенья
параллельны строкам и столбцам таблицы, одна из вершин находится в данной
свободной клетке, а все остальные - в занятых клетках. Это будет 14-34-33-
23-21-11. Производим перераспределение поставок вдоль цикла пересчета:
|40 | | |* | |40-( | | |( | |33 | | |7 |
|8 |30 |7 | |( |8+( | |7-( | |( |15 |30 | | |
| | |22 |40 | | | |22+( |40-( | | | |29 |33 |
(max=7
Получаем второе базисное допустимое решение:
Таблица 2
| |b1=48 |b2=30 |b3=29 |b4=40 |b5=8 | |
|Потребл | | | | | | |
|Произв | | | | | | |
|a1=40 |33 |6 | |7 | |p1=0 |
| |3 | |4 |3 |0 | |
|a2=45 |15 |30 |1 | | |p2=-1 |
| |2 |3 | |3 |0 | |
|a3=70 | |* |29 |33 |8 0|p3=1 |
| |6 |5 |1 |4 | | |
| |q1=3 |q2=4 |q3=0 |q4=3 |q5= -1| |
Находим новые потенциалы. Новые оценки:
(12= -2; (13= -4; (15= -1; (23= -2; (24= -1; (25= -2; (31= -2; (32=0.
Поскольку все (ij(0 решение является оптимальным:
33 0 0 7
Xоpt1 = 15 30 0 0
0 0 29 33
Однако, так как оценка клетки (32=0, делаем вывод о наличие другого
возможного оптимального решения. Для его нахождения строим цикл пересчета
клетки 32: 32-22-21-11-14-34, производим перераспределение:
Таблица 3
| |b1=48 |b2=30 |b3=29 |b4=40 |b5=8 | |
|Потребл | | | | | | |
|Произв | | | | | | |
|a1=40 |3 3|6 | |37 | |p1=0 |
| | | |4 |3 |0 | |
|a2=45 |45 |3 |1 | | |p2=-1 |
| |2 | | |3 |0 | |
|a3=70 | |30 |29 |3 4|8 0|p3=1 |
| |6 |5 |1 | | | |
| |q1=3 |q2=4 |q3=0 |q4=3 |q5= -1| |
Находим новые потенциалы. Получаем рi и qj соответственно равные
потенциалам первого базисного оптимального решения (см. табл. 2). Исходя из
этого (max=(32, однако элемент с индексом 32 уже присутствует в базисе,
поэтому пересчет не имеет смысла. Таким образом получаем второе и последнее
базисное оптимальное решение:
3 0 0 37
Xоpt2 = 45 0 0 0
0 30 29 3
Оптимальное распределение инвестиций
Данная задача с n переменными представляется, как многошаговый процесс
принятия решений. На каждом шаге определяется экстремум функции только по
одной переменной.
Пусть 4 фирмы образуют объединение. Рассмотрим задачу распределения
инвестиций в размере 700 тыс. рублей по этим 4 фирмам. Размер инвестиций
пусть будет кратен 100 тыс. рублей. Эффект от направления i-й фирме
инвестиций в размере ? (сотен тыс. рублей) выражается функцией fi(xi).
Приходим к задаче fl(xl)+f2(x2)+f3(x3)+f4(x4)(max , где xi - пока еще
неизвестный размер х1+х2+х3+х4?7; х1,х2,х3.х4?0 инвестиций i-й фирме. Эта
задача решается методом динамического программирования: последовательно
ищется оптимальное распределение для k=2,3 и 4 фирм.
Пусть первым двум фирмам выделено ? инвестиций. обозначим z2(?) величину
инвестиций 2-й фирме, при которой сумма f2(z2j)+fl(?-z2j), 0?j? ?
максимальна, саму эту максимальную величину обозначим F2(?). Далее
действуем также: находим функции z3 и F3 и т.д. На k-ом шаге для нахождения
Fk(?) используем основное рекуррентное соотношение: Fk(?)=max{fkj(хk)+F(k-
1)( ?-хk); 0 ? хk ? ?
|xj |0 |100 |200 |300 |400 |500 |600 |700 |
|f1 |0 |28 |45 |65 |78 |90 |102 |113 |
|f2 |0 |25 |41 |55 |65 |75 |80 |85 |
|f3 |0 |15 |25 |40 |56 |62 |73 |82 |
|f4 |0 |20 |33 |42 |48 |53 |56 |58 |
Таблица 1
| |?-х2 |0 |100 |200 |300 |400 |500 |600 |700 |
| | | | | | | | | | |
|x2 | | | | | | | | | |
| | |0 |28 |45 |65 |78 |90 |102 |113 |
| |F1(?-x2)| | | | | | | | |
| | | | | | | | | | |
| |f2(x2) | | | | | | | | |
|0 |0 |0 |28 |45 |65 |78 |90 |102 |113 |
|100 |25 |25 |53 |70 |90 |103 |115 |127 | |
|200 |41 |41 |69 |86 |106 |119 |131 | | |
|300 |55 |55 |83 |100 |120 |133 | | | |
|400 |65 |65 |93 |110 |130 | | | | |
|500 |75 |75 |103 |120 | | | | | |
|600 |80 |80 |108 | | | | | | |
|700 |85 |85 | | | | | | | |
Жирным цветом обозначен максимальный суммарный эффект от выделения
соответствующего размера инвестиций по 2-м предприятиям.
|? |0 |100 |200 |300 |400 |500 |600 |700 |
|F2 |0 |28 |53 |70 |90 |106 |120 |133 |
|x2 |0 |0 |100 |100 |100 |200 |300 |300 |
Таблица 2
| |?-х2 |0 |100 |200 |300 |400 |500 |600 |700 |
| | | | | | | | | | |
|х3 | | | | | | | | | |
| | |0 |28 |53 |70 |90 |106 |120 |133 |
| |F3(?-x3)| | | | | | | | |
| | | | | | | | | | |
| |f3(x3) | | | | | | | | |
|0 |0 |0 |28 |53 |70 |90 |106 |120 |133 |
|100 |15 |15 |43 |68 |85 |105 |121 |135 | |
|200 |25 |25 |53 |78 |95 |115 |131 | | |
|300 |40 |40 |68 |93 |110 |130 | | | |
|400 |56 |56 |84 |109 |125 | | | | |
|500 |62 |62 |90 |115 | | | | | |
|600 |73 |73 |101 | | | | | | |
|700 |82 |82 | | | | | | | |
Жирным цветом обозначен максимальный суммарный эффект от выделения
соответствующего размера инвестиций по 3-м предприятиям.
|? |0 |100 |200 |300 |400 |500 |600 |700 |
|F2 |0 |28 |53 |70 |90 |106 |121 |135 |
|x2 |0 |0 |0 |0 |0 |0 |100 |100 |
Таблица 3
| |?-х4 |0 |100 |200 |300 |400 |500 |600 |700 |
| | | | | | | | | | |
|x4 | | | | | | | | | |
| | |0 |28 |53 |70 |90 |106 |121 |135 |
| |F4(?-x4)| | | | | | | | |
| | | | | | | | | | |
| |f4(x4) | | | | | | | | |
|0 |0 | | | | | | | |135 |
|100 |20 | | | | | | |141 | |
|200 |33 | | | | | |139 | | |
|300 |42 | | | | |132 | | | |
|400 |48 | | | |118 | | | | |
|500 |53 | | |106 | | | | | |
|600 |56 | |84 | | | | | | |
|700 |58 |58 | | | | | | | |
Жирным цветом обозначен максимальный суммарный эффект от выделения
соответствующего размера инвестиций по 4-м предприятиям.
Сведем результаты в 4 таблицы. Теперь F4(7)=141 показывает максимальный
суммарный эффект по всем 4-м фирмам, a z4(7)=100 тыс. руб. - размер
инвестиций в 4-ю фирму для достижения этого максимального эффекта. На долю
остальных трех предприятий остается 600 тыс. руб.
Третьему предприятию должно быть выделено х*3=Х3(700-х*4)=Х3(600)=100 тыс.
руб.
Продолжая обратный процесс, находим х*2=Х2(700-х*4-х*3)=Х2(500)=200 тыс.
руб.
На долю первого предприятия остается х*1=700-х*4-х*3-х*2=300 тыс. руб.
Таким образом, наилучшим является следующее распределение капитальных
вложений по предприятиям:
х*1 =300; х*2 =200; х*3 = 100; х*4 = 100.
Оно обеспечивает производственному объединению наибольший возможный
прирост прибыли 141 тыс. руб.
Анализ доходности и риска финансовых операций
Финансовой называется операция, начальное и конечное состояния которой
имеют денежную оценку и цель проведения которой заключается в максимизации
дохода - разности между конечной и начальной оценками.
Почти всегда финансовые операции проводятся в условиях
неопределенности и потому их результат невозможно предсказать заранее.
Поэтому финансовые операции рискованны, т.е. при их проведении возможны как
прибыль, так и убыток.
Существует несколько разных способов оценки операции с точки зрения
доходности и риска. Наиболее распространенным является представление дохода
операции как случайной величины и оценка риска операции как среднего
квадратического отклонения этого случайного дохода. Однако количественно
оценить риск возможно лишь если операция вероятностно характеризуема, т.е.
ее доход есть случайная величина - это предполагает возможность
неоднократного повторения этой операции. Итак, пусть доход от операции Q
есть случайная величина, которую будем обозначать также как и саму операцию
Q. Математическое ожидание М[Q] называют еще средним ожидаемым доходом, а
риск операции r отождествляют со средним квадратическим отклонением, т.е.
квадратным корнем из дисперсии D[Q].
Рассмотрим четыре операции Q1, Q2, Q3, Q4. Найдем средние ожидаемые
доходы Qi и риски ri, операций.
[pic] ; [pic] ;
[pic] ; [pic] .
|Q1: |0 |1 |2 |8 |
| |1/3 |1/3 |1/6 |1/6 |
Q1=0(1/3+1(1/3+2(1/6+8(1/6=2
M[Q12]= 02 (1/3+12 (1/3+22 (1/6+82 (1/6=11,7
D[Q1]= 11,7-22=7,7
r1=2,77
|Q2: |2 |3 |4 |10 |
| |1/3 |1/3 |1/6 |1/6 |
Q2=4
M[Q22]=23,7
D[Q2]=7,7
r2=2,77
|Q3: |0 |4 |6 |10 |
| |1/5 |1/5 |1/5 |2/5 |
Q3=6
M[Q32]=50,4
D[Q3]=14,4
r3=3,8
|Q4: |2 |6 |8 |12 |
| |1/5 |1/5 |1/5 |2/5 |
Q4=8
M[Q42]=78,4
D[Q4]=14,4
r4=3,8
Нанесем средние ожидаемые доходы Q и риски r на плоскость - доход
откладываем по горизонтали, а риски по вертикали (см. график 3);
Получили 4 точки. Чем правее точка (Q,r), тем более доходная операция,
чем точка выше - тем более она рисковая. Значит, нужно выбирать точку
правее и ниже. Точка (Q',r') доминирует над точкой (Q,r) если Q'>Q и r'0
Рассматриваем вариант, когда В играет в смешанных стратегиях, а П – в
чистых стратегиях выбирает первую строку.
-7/11= 2y-5(1-y)
y*= 48/77
q*=(48/77, 0, 0, 29/77) – оптимальная смешанная стратегия В
Анализ модели краткосрочного страхования жизни
В страховой компании застраховано N1=900 человек в возрасте 45 лет и
N2=550 человек в возрасте 55 лет сроком на один год. Компания выплачивает
наследникам: 100000 руб., в случае смерти застрахованного от несчастного
случая, и 25000 руб., в случае смерти от естественных причин в течение
года. Компания не платит ничего, если человек проживет этот год.
Предположим, что смертность описывается моделью Мейкхама и рассчитаем нетто-
премию, цену полиса, страховую надбавку, чтобы вероятность неразорения
компании составляла 0,95.
Индивидуальные иски x[pic] и x[pic] каждого из застрахованных 1-ой и 2-ой
групп определяются, соответственно, рядами распределения (для удобства за
денежную единицу примем 100000 руб.).
0 ј 1 (1)
x[pic]
[pic]=0,9982 [pic]=0,0013 [pic]=0,0005
0 ј 1
x[pic]
[pic]=0,9962 [pic]=0,0044 [pic]=0,0005
Здесь вероятности смерти от несчастного случая примем равными 0,0005,
а вероятности смерти от естественных причин возьмем из Таблицы
продолжительности жизни.
Средние индивидуальные иски Мx[pic] и Мx[pic] равны соответствующим
нетто-премиям Р[pic] и Р[pic] для клиентов компании 1-ой и 2-ой групп.
Р[pic] = Мx[pic] = ј*0,0013 + 1*0,0005 » 0,00083 = 83 руб.
(2)
Р[pic] = Мx[pic] = ј*0,0044 + 1*0,0005 » 0,0016 = 160 руб.
I. Сначала рассмотрим решение, основанное на распределении Пуассона.
Чтобы свести задачу к схеме опытов Бернулли можно приближенно заменить
ряды распределения (1) следующими таблицами:
0 М(x[pic]/x[pic]№0) 0 М(x[pic]/x[pic]№0)
x[pic]: x[pic]:
(3)
[pic] [pic] [pic] [pic]
а затем в качестве условной денежной единицы принять условные
математические ожидания М(x[pic]/x[pic]№0) в 1-ой таблице и
М(x[pic]/x[pic]№0) – во 2-ой.
Вычислим условные математические ожидания:
М(x[pic]/x[pic]№0)=ј*Р(x[pic]=ј/x[pic]№0)+1*Р(x[pic]=1/x[pic]№0) =
=ј*[pic]/([pic])+1*[pic]=
=ј*0,0044/(0,0044+0,0005)+1*0,0005/(0,0044+0,0005)=
=ј*13/18+1*5/49 = 5/18 » 0,458=45800 руб. – денежная единица для клиентов 1-
ой группы.
М(x[pic]/x[pic]№0=ј*[pic]/([pic])+1*[pic]=
=ј*0,0044/(0,0044+0,0005)+1*0,0005/(0,0044+0,0005)=
=. ј*44/49+1*5/49 = 16/49 » 0,327=32700 руб – денежная единица для клиентов
2-ой группы.
С учетом всех замечаний вместо рядов распределения (3) имеем:
0 1 0 1
x[pic]: x[pic]: (4)
0,9982 0,0018 0,9962 0,0049
откуда получаем: Мx[pic] = 0,0018
Мx[pic] = 0,0049.
Подсчитаем сумму исков от застрахованных
1-ой группы:
l[pic] = [pic]Мx[pic] = N1* Мx[pic] = 400*0,0018 = 0,7
2-ой группы:
l[pic] = [pic]Мx[pic] = N2* Мx[pic] = 1000*0,0049 = 4,9
Общая сумма исков может рассматриваться, как случайная пуассоновская
величина с параметром l[pic]+l[pic] = 5,6
Так как вероятность не разорения компании должна быть не меньше 0,95,
необходимо чтобы для общей суммы исков от застрахованных
x = [pic]x[pic] + [pic]x[pic]
выполнялось соотношение: Р(x Ј x) і 0,95 , где х –
капитал компании.
Очевидно, что х = х[pic], здесь х[pic]» 10– квантиль уровня 0,95 для
распределения Пуассона. За счет нетто-премий компания может получить только
сумму:
5,6=0,7*45800 руб. + 4,9*32700 руб. = 32060 руб.+1060230 руб. =
192290руб.
Поэтому страховая надбавка компании должна составлять:
R=(10-5,6)/5,6 (100% »78,6% = 0,786*192290 руб.»1511400руб., (5)
а капитал компании:
х = 192290 руб. + 151140 руб. » 343430 руб. (6)
Таким образом, индивидуальные страховые надбавки r[pic] и r[pic], цены
полисов Р[pic] и Р[pic] для каждого из клиентов 1-ой и 2-ой группы
соответственно равны (они пропорциональны нетто-премиям):
r[pic] = 0,52*Р[pic] = 0,52*83 руб. » 43 руб.,
r[pic] = 0,52*Р[pic] = 0,52*160 руб. » 83 руб.,
(7)
Р[pic] = Р[pic] + r[pic] » 43 руб. + 83 руб. = 126 руб.,
Р[pic] = Р[pic] + r[pic] »160 руб. + 83 руб. = 243 руб.
II. Теперь решим задачу с помощью гауссовского приближения. Среднее
значение общего суммарного иска от застрахованных
x = [pic]Мx[pic] + [pic]Мx[pic]
с учетом средних индивидуальных исков (2) равно:
Мx = N1*Mx[pic]+ N2* Мx[pic]=400*0,00083+1000*0,0016=
= 0,332 + 1,6 » 1,9 = 190000 руб.
(8)
Дисперсию x в виду независимости x[pic] и x[pic] вычислим по формуле:
Dx = [pic]Dx[pic] + [pic]Dx[pic] » 400*0,00058 + 1000*0,00078=
=0,23 + 0,78 = 1,01. (9)
Здесь:
Dx[pic] = М(x[pic])[pic] - М[pic]x[pic] = 0,00058 – (0,00083)[pic] »
0,00058 ,
(10)
Dx[pic] = М(x[pic])[pic] - М[pic]x[pic] = 0,00078 – (0,0016) [pic] »
0,00078 ,
где с помощью рядов распределения (1) имеем:
М(x[pic])[pic] = 1/16*0,0013 + 1*0,0005 » 0,00058 ,
(11)
М(x[pic])[pic] = 1/16*0,0044 +1*0,0005 » 0,00078.
На основании центральной предельной теоремы функция распределения
нормированной случайной величины:
S[pic]= (x - Mx)/[pic],
при N1 + N2 ® Ґ имеет предел
F(x) = (1/[pic])*[pic]dz
Для гауссовского приближения случайной величины x верна следующая цепочка
равенств:
Р(x < x) = Р((x - Мx)/[pic] Ј (х - Мx)/[pic]) » F((x - Mx)/[pic]) ,
где х – капитал компании.
Для того чтобы вероятность неразорения компании не превосходила 0,95, т.е.
F((x - Mx)/[pic]) і 0,95 должно быть выполнено соотношение
(х - Mx)/[pic] і х[pic],
(12)
здесь х[pic]» 1,645 – квантиль уровня 0,95 стандартного гауссовского
распределения.
Нетрудно убедиться в том, что минимально необходимый капитал компании
должен составлять:
х=Мx+х[pic]*[pic]»1,9+1,645*1,005=1,9+1,65=3,55=355000руб.,
(13)
а относительная страховая надбавка составляет:
х[pic]*[pic]/Мx*100%=1,65/1,9*100%»86,8% (14)
Индивидуальные страховые надбавки r[pic] и r[pic], цены полисов Р[pic]
и Р[pic] для клиентов 1-ой и 2-ой групп с учетом (2), очевидно будут равны
(страховые надбавки пропорциональны нетто-премиям):
r[pic] = 0,68*83 руб. » 56 руб.;
r[pic] = 0,68*160 руб. » 109 руб.;
(15)
Р[pic] = Р[pic] + r[pic] »83 руб. + 56 руб. = 139 руб.;
Р[pic] = Р[pic] + r[pic] »160 руб. + 109 руб. = 269 руб.
III. Проанализируем результаты, полученные в п.п. I и II. Очевидно
расхождение результатов, полученных при использовании пуассоновского и
гауссовского приближений. Попытаемся разобраться, в чем причина этого
различия.
Дело в том, что при использовании закона Пуассона замена рядов
распределения (1) на ряды распределения (3) привела к тому, что не
изменились лишь математические ожидания Мx[pic]и Мx[pic]. В то же время
дисперсии Dx[pic] и Dx[pic], свидетельствующие о степени рассеяния
случайных исков x[pic] и x[pic], найденных по рядам распределения (1) и
(3), различны. Следовательно, различны и дисперсии Dx, найденные по рядам
распределения (1) и (3). Действительно, дисперсия общего суммарного иска x
по рядам (1) подсчитана: Dx = 1,24 (см. соотношение (9) ).
Вычислим дисперсию x по рядам распределения (3), т.е.
0 0,458 0 0,327
x[pic]: x[pic]:
(16)
0,9982 0,0018 0,9962 0,0049
Проведя расчеты, аналогичные (9-11), получим:
Dx =[pic]Dx[pic] + [pic]Dx[pic] » 400*0,00038 + 1000*0,00052 = 0,67.
(17)
Здесь:
Dx[pic] = М(x[pic])[pic] - М[pic]x[pic] = 0,00038 – (0,00083)[pic] »
0,00038 ,
(18)
Dx[pic] = М(x[pic])[pic] - М[pic]x[pic] = 0,00052 – (0,0016) [pic] »
0,00052 ,
причем:
М(x[pic])[pic] = 0,458[pic]*0,0018 » 0,00038 ,
(19)
М(x[pic])[pic] = 0,327[pic]*0,0049 » 0,00052.
В дальнейшем будем использовать следующие обозначения: дисперсию x,
найденную с использованием рядов (1), обозначим s[pic], а дисперсию x,
найденную по рядам (3) или (16), обозначим s[pic]. Таким образом, s[pic] =
1,01, а s[pic] = 0,67.
Из формулы (12), использующей стандартное гауссовское распределение,
непосредственно следует, что относительная страховая надбавка, если Dx =
s[pic] = 0,67 , равна
х[pic]*s[pic]/Мx*100% = 1,645*[pic]/1,9*100% » 70,9%
(20)
Этот результат хорошо согласуется с относительной страховой надбавкой,
учитывающей распределение суммарного иска x по закону Пуассона, равной
86,8% (см. (5)).
Учитывая вышеизложенное, напрашивается естественный вывод: если
относительная страховая надбавка, капиталл компании, обеспечивающий
неразорение компании с вероятностью 0,95, и цена полиса вычисляются, исходя
из распределения суммарного иска застрахованных по закону Пуассона, то для
нахождения основных характеристик компании необходимо ввести поправочный
коэффициент, равный k = s1 /s2.
Проиллюстрируем применение коэффициента k для коррекции результатов,
полученных в п.I:
страховая надбавка с учетом (5) станет равной:
R[pic]= k*R = [pic]*86,8%=1,2*86,8% » 71,4% » 135660 руб. (21)
капитал компании (см.(6)) станет равным:
х[pic]= 190000 руб. + 135660 руб. » 325660 руб.,
(22)
а индивидуальные страховые надбавки и цены полисов (см.(7)):
r[pic][pic] = k*r[pic] » 1,2*43 руб. » 54 руб.,
r[pic][pic] = k*r[pic] » 1,2*83 руб. » 100 руб.,
(23)
Р[pic][pic] = Р[pic] + r[pic][pic] » 83 руб. + 54 руб. = 137 руб.,
Р[pic][pic] = Р[pic] + r[pic][pic] » 160 руб. + 100 руб. = 260 руб.
В заключение необходимо отметить, что характеристики работы компании,
полученные с учетом коррекции результатов исследования, в котором суммарный
иск застрахованных подчинен распределению Пуассона хорошо согласуется с
характеристиками работы страховой компании.
| |
