Реферат: Прикладная математика 2 - Refy.ru - Сайт рефератов, докладов, сочинений, дипломных и курсовых работ

Прикладная математика 2

Рефераты по математике » Прикладная математика 2

Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования


ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ УПРАВЛЕНИЯ



Кафедра прикладной математики


КУРСОВАЯ РАБОТА

по дисциплине "Прикладная математика"


Выполнила:

Институт: ИУХМП

Специальность: Менеджмент организации

Отделение (д/о, в/о): дневное отделение

Курс: II

Группа: М/О II-1

Руководитель: Чистяков В.С.

Дата сдачи на проверку : ...………………………..

Дата защиты: .........................................

Оценка: .........................................

Подпись руководителя: ..........................................


Москва - 2006

Содержание


Цели и задачи курсового проекта…………………………………. ...3

Линейная производственная задача………………………………… ..3

Двойственная задача…………………………………………………… 6

Транспортная задача линейного программирования……………….12

Динамическое программирование. Распределение капитальных вложений…………………………………………………………………19

Задача формирования оптимального портфеля ценных бумаг……22

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

Анализ доходности и риска финансовых операций…………… ….33

Принятие решений в условиях неопределенности………………. ..35


ЦЕЛИ И ЗАДАЧИ КУРСОВОГО ПРОЕКТА


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

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

Цель курсового проекта - подготовить студента к самостоятельному проведению операционного исследования, основными этапами которого являются построение математической модели, решение управленческой задачи при помощи модели и анализ полученных результатов.


1. Линейная производственная задача


Задание:

Сформулировать линейную производственную задачу и составить ее математическую модель, где заданы технологическая матрица А затрат различных ресурсов на единицу каждой продукции, вектор объемов ресурсов В и вектор удельной прибыли С при возможном выпуске четырех видов продукции с использованием трех видов ресурсов

Преобразовать данную задачу к виду основной задачи линейного программирования, решить ее, найти оптимальную производственную программу, максимальную прибыль, остатки ресурсов различных видов и указать узкие места производства.

В последней симплексной таблице указать обращенный базис Q-1, соответствующий оптимальному набору базисных неизвестных. Проверить выполнение соотношения

H = Q-1B


Если по оптимальной производственной программе какие-то два вида продукции не должны выпускаться, то в таблице исходных данных вычеркнуть соответствующие два столбца, составить математическую модель задачи оптимизации производственной программы с двумя оставшимися переменными, сохранив прежнюю нумерацию переменных и решить графически.


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

Компания «Малыш» выпускает четыре вида детского питания, используя для этого сухое молоко, сою и фруктовое пюре. Известна технологическая матрица А затрат любого вида ресурса на единицу каждого вида питания, вектор В объемов имеющихся ресурсов и вектор С стоимости каждого вида питания.


2 3 0 4 148

A = 4 1 5 0 B= 116 C=(30 25 14 12)

0 2 4 3 90


Примем следующие обозначения: аi j – расход i-ого ресурса на единицу j-го вида питания; bi – запас i-ого ресурса; сj – прибыль на единицу j-го вида питания; xj – количество выпускаемого питания j-ого вида.

На производство x1 питания 1-го вида

x2 питания 2-го вида

x3 питания 3-го вида

x4 питания 4-го вида компания затратит следующее количество ресурсов:

(1)

Требуется найти производственную программу X* = (x1, x2, x3, x4), реализация которой обеспечит компании получение наибольшей прибыли:

,

при линейных ограничениях неравенства (1).


Решение:

Приведем задачу к основной задаче линейного программирования. Для этого добавим в левую часть системы ограничений (1) дополнительные неотрицательные неизвестные x5, x6, x7, которые по физическому смыслу будут представлять собой:

x5 – остаток ресурса 1-го вида,

x6 – остаток ресурса 2-го вида,

x7 – остаток ресурса 3-го вида.

Строим симплексную таблицу.

В качестве базисных неизвестных могут быть приняты неизвестные х5, х6, х7 , так как каждый из них входит только в одно уравнение системы и не входит в другие уравнения. Приравняв к нулю свободные переменные х1, х2, х3, х4 , получаем базисное неотрицательное решение:

х1=0, х2=0, х3=0, х4=0, х5=148, х6=116, х7=90

Из уравнения целевой функции видно, что наиболее выгодно начинать производить продукцию 1-ого вида, так как прибыль здесь будет наибольшая.

Выясним, до каких пор наши ресурсы позволяют увеличить выпуск этой продукции:

Так как, в целевой функции нет базисных переменных, то можно её представить в виде:

0 – Z = -30x1-25x2-14x3-12x4

Ć

Б

Н

X1

X2

X3

X4

X5

X6

X7

α

Пояснения

0

X5

148

2

3 0 4 1 0 0 74

min(j<0)= -30

min(α)=29,

x1 в базис, x6 из базиса

0

X6

116

4

1

5

0

0

1

0

29
0

X7

90

0

2 4 3 0 0 1


0-Z

-30

-25 -14 -12 0 0 0
0

X5

90

0

5/2

-5/2

4

1

-1/2

0

36

min(j<0)= -35/2

min(α)=36,

x2 в базис, x5 из базиса

30

X1

29 1

1/4

5/4 0 0 1/4 0 116
0

X7

90 0

2

4 3 0 0 1 45


870-Z 0

-35/2

47/2 -12 0 15/2 0
25

X2

36 0 1 -1 8/5 2/5 -1/5 0

решения оптимальны

30

X1

20 1 0 3/2 -2/5 -1/10 3/10 0
0

X7

18 0 0 6 -1/5 -4/5 2/5 1


1500-Z 0 0 6 16 7 4 0

x1=20, x2=36, x3=0, x4=0, x5=0, x6=0, x7=18 определяют производственную программу x1=20, x2=36, x3=0, x4=0

Прибыль будет наибольшей когда , при этом

остатки ресурсов: 1-ого вида x5=0

2-ого вида x6=0

3-ого вида x7=18

Также надо обратить внимание на экономический смысл элементов последней строки последней симплексной таблицы. Коэффициенты ∆3 =6 при переменной Х3, ∆4 =16 при переменной Х4 показывают, что если произвести одну единицу продукции 3-ого или 4-ого видов, то прибыль уменьшится на 6 или 16 единиц соответственно.

Проверим выполнение соотношения H=Q-1B:

; ; ;

Равенство выполняется.


Итак, по оптимальной производственной программе у нас получилось, что третий и четвертый вид детского питания не должны выпускаться. В таблице исходных данных вычеркнем соответствующие два столбца и составим математическую модель задачи оптимизации производственной программы с двумя оставшимися переменными, сохранив прежнюю нумерацию переменных и решим эту задачу графически.


; ;

Математическая модель будет выглядеть так:

- ?

Z = 30x1 + 25x2→ max






2. Двойственная задача

Задание:

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

Применить найденные двойственные оценки ресурсов к решению следующей задачи.

Сформулировать задачу о "расшивке узких мест производства" и составить математическую модель. Определить область устойчивости двойственных оценок, где сохраняется структура программы производства. Решить задачу о расшивке узких мест производства при условии, что дополнительно можно получить от поставщиков не более одной трети первоначально выделенного объема ресурса любого вида (если задача окажется с двумя переменными, то только графически); найти план приобретения дополнительных объемов ресурсов, дополнительную возможную прибыль, составить сводку результатов.


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

Ранее мы рассмотрели конкретную линейную производственную задачу по выпуску четырех видов детского питания с использованием трех видов ресурсов Технологическая матрица А затрат любого вида ресурса на единицу каждого вида питания была известна.

Теперь представим себе, что возникла новая ситуация. предприниматель П. (Петров), занимающийся производством каких-то других видов продукции, но с использованием трех таких же видов ресурсов, какие имеются у компании «Малыш», предлагает ей "уступить" по определенным ценам все имеющиеся у «Малыша» ресурсы и обещает платить у1 рублей за каждую единицу первого ресурса, у2 руб. – второго, у3 руб. – третьего. Возникает вопрос: при каких ценах у1, у2, у3 компания «Малыш» может согласиться с предложением П.

Величины у1, у2, у3 это двойственные оценки ресурсов. Они прямо зависят от условий, в которых действует компания «Малыш».

В нашей задаче технологическая матрица А, вектор объемов ресурсов В и вектор удельной прибыли С имели вид:


2 3 0 4 148

A = 4 1 5 0 B= 116 C=(30 25 14 12)

0 2 4 3 90

Для производства единицы первого вида питания компания должна затратить, как видно из матрицы А, 2 единицы ресурса первого вида и 4 единицы ресурса второго вида (элементы первого столбца матрицы). В ценах у1, у2, у3 затраты компании составят 2у1 + 4у2 руб., т.е. столько заплатит предприниматель П. за все ресурсы, идущие на производство единицы первой продукции. На рынке за единицу первого вида питания компания получила бы прибыль 30 руб. Следовательно, компания «Малыш» может согласиться с предложением П. только в том случае, если он заплатит не меньше 30 руб.:

2у1 + 4у2  30

Аналогично, во втором столбце матрицы А указаны затраты различных ресурсов на производство единицы детского питания второго вида. В ценах П. эти затраты составят 3у1 + 1у2 + 2у3, а на рынке за единицу питания второго вида «Малыш» получил бы прибыль 25 рублей. Поэтому перед предпринимателем П нужно поставить условие:

3у1 + 1у2 + 2у3 25 и т.д.

За все, имеющиеся у «Малыша» ресурсы П. должен заплатить:

148у1 + 116у2 + 90у3 рублей

При поставленных «Малышом» условиях предприниматель П. будет искать такие значения величин у1, у2, у3, чтобы эта сумма была как можно меньше. Подчеркнем, что здесь речь идет не о ценах, по которым компания когда-то приобретала эти ресурсы, а о ценах, которые существенно зависят от применяемых «Малышом» технологий, объемов ресурсов и от ситуации на рынке.

Таким образом, проблема определения расчетных оценок ресурсов приводит к задаче линейного программирования: найти вектор двойственных оценок У*(у1, y2, y3), минимизирующий общую оценку всех ресурсов:

, (1)

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


(2)


Решение:

Решение полученной задачи легко найти с помощью второй основной теоремы двойственности.


Прямая задача: Двойственная задача:





Согласно второй основной теореме двойственности для оптимальных решений X*=(х1, х2, х3, х4) и Y*=(y1, y2, y3) пары двойственных задач необходимо и достаточно выполнение условий:

При решении прямой задачи было получено, что x1 >0, x2 >0. Поэтому:

Если же учесть, что третий ресурс был избыточным и, согласно той же теореме двойственности, его двойственная оценка равна нулю т.е. y3=0, то приходим к системе уравнений:

, откуда следует

Решение двойственной задачи Y*=(7, 4, 0)

Тогда общая оценка всех ресурсов равна

(3)

Заметим, что решение (3) содержалось в последней строке последней симплексной таблицы исходной задачи. Важен экономический смысл двойственных оценок. Например, двойственная оценка второго ресурса у2=4 показывает, что добавление одной единицы второго ресурса обеспечит прирост прибыли в 4 единицы.


Задача о "расшивке узких мест производства"


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

Продолжаем рассмотрение задачи планирования производства. При выполнении оптимальной производственной программы первый и второй ресурсы используются полностью, т.е. образуют «узкие места производства» x5=0, x6=0. Будем «расшивать узкие места производства» т.е. заказывать дополнительно дефицитные ресурсы. Обозначим через t1 и t2 искомое дополнительное количество единиц первого и второго вида ресурсов. T(t1, t2, 0)- вектор дополнительных объемов ресурсов. Согласно третьей основной теореме двойственности, увеличение первого вида ресурса на единицу обеспечивает прирост прибыли, равный двойственной оценке y1=7, второго вида – y2=4.

При этом, для сохранения структуры плана производства величины t1, t2, t3 должны изменяться лишь в области устойчивости двойственных оценок, т.е. должно выполняться условие:

H + Q-1T 0, причем, по смыслу задачи t1 >0, t2 >0. (1)

Таким образом, проблема «расшивки узких мест производства» представляет собой задачу линейного программирования: найти план расшивки - вектор T (t1, t2, 0), максимизирующий суммарный прирост прибыли:

, (2)

при условии сохранения двойственных оценок ресурсов (и, следовательно, структуры производственной программы).

Обращенный базис был найден при решении задачи симплексным методом:

Условия (1) запишутся в виде:

(3)

Предположим также, что поставщики сырья могут выделить компании не более 1/3 первоначального объема ресурса каждого вида:

(4)

Перепишем неравенства (3) и (4) в виде:


(5)


Задача оптимизации плана «расшивки узких мест» производства принимает вид: найти переменные t1 и t2, которые обеспечивают максимум линейной форме:

, при ограничениях (5).


Решение:

Сформулированная задача линейного программирования с двумя переменными может быть решена графически.


Строим график и ищем точки пересечения:



, откуда оптимальный план «расшивки»:

При этом прирост прибыли составит: W = 7t1 + 4t2=447 Ѕ .

Сводка результатов приведена в таблице:


Cj

30

25

14

12

b

x4+i

yi

ti


2 3 0 4 148 0 7 41 5/6
aij 4 1 5 0 116 0 4 38 2/3

0 2 4 3 90 18 0 0
xj 20 36 0 0 1500
447 Ѕ
Δj 0 0 6 16


3. Транспортная задача линейного программирования


Задание:

Составить математическую модель транспортной задачи по исходным данным:

; ;

Если полученная модель окажется открытой, то свести ее к замкнутой и найти оптимальное решение транспортной задачи методом потенциалов.


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

Однородный продукт, сосредоточенный в трех пунктах производства (хранения) в количествах 35, 55 и 80 единиц, необходимо распределить между n-четырьмя пунктами потребления, которым необходимо соответственно 30, 55, 44, 42 единиц. Стоимость перевозки единицы продукта из i-го пункта отправления () в j-ый пункт назначения () равна сij и известна для всех маршрутов. Она задана матрицей С:

Необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы по доставке продуктов были минимальными.

Обозначим через хij количество груза, планируемого к перевозке от i-го поставщика () j-му () потребителю. При наличии баланса производства и потребления (1)

Общий объем производства аi = 80+50+35= 170 меньше , требуется всем потребителям bi = 30+55+44+42=171.

Таким образом, имеет место дисбаланс между запасами и запросами. В математическом плане это означает, что наша задача – это задача открытого типа. Для устранения дисбаланса (приведения задачи к закрытому типу), введем фиктивный пункт производства с объемом производства, равным указанному дисбалансу т.е. единице, причем тарифы на перевозку из этого пункта условимся считать равными нулю ().

Четырьмя условиями того, что из каждого пункта хранения вывозится весь продукт, являются:

Четырьмя условиями того, что каждому потребителю доставляется затребованное им количество продукта являются:


B

A

b1=30 b2=55 b3=44 b4=42
a1=35 x11 2 x12 3 x13 6 x14 4




a2=55 x21 4 x22 1 x23 5 x24 7




a3=80 x31 5 x32 2 x33 3 x34 3




a4=1 x41 0 x42 0 x43 0 x44 0





В качестве показателя эффективности выступает суммарная стоимость перевозок (L):

;

В качестве критерия эффективности правомерно считать принцип минимизации результата т.к. на лицо стремление уменьшить стоимость перевозок. Приходим к следующей математической постановке задачи: найти план перевозок x, компоненты которого обеспечивают минимизацию линейной формы L, при следующих ограничениях на эти компоненты:


(1)


Решение:

Сформулированная задача является задачей линейного программирования, которая обладает двумя особенностями, а именно

коэффициент при каждой из неизвестных в системе ограничений (1) равен 1;

одно из уравнений системы ограничений линейно зависит от других, в силу чего число базисных неизвестных в системе равно .

Эти особенности позволяют решить задачу специально разработанными методами: методом северо-западного угла или методом наименьших затрат. Мы решим ее двумя способами.


Метод наименьших затрат


потреб


произв

b1=30 b2=55 b3=44 b4=42
a1=35

30

2
3
6

5

4 p1=0




a2=55

0

4 55 1

*

5
7 p2=2




a3=80
5
2

44

3 36 3 p3=-1




a4=1
0
0
0 1 0 p4=-4





q1=2 q2=-1 q3=4 q4=4

Обозначим через ) вектор симплексных множителей или потенциалов. Тогда .

Один из потенциалов можно выбрать произвольно, так как в системе (1) одно уравнение линейно зависит от остальных. Положим, что р1 = 0. Остальные потенциалы находим из условия, что для базисных клеток . В данном случае получаем:

11 = 0, p1 + q1 - c11 = 0, q1 = 2

14 = 0, p1 + q4 - c14 = 0, q4 = 4

34 = 0, p3 + q4 – c34 = 0, p3 = -1

33 = 0, p3 + q3 – c33 = 0, q3= 4

21 = 0, p2 + q1 – c21 = 0, p2 = 2

22 = 0, p2 + q2 – c22 = 0, q2 = -1

44 = 0, p4 + q4 – c44 = 0, p4=-4

Теперь по формуле вычисляем оценки всех свободных клеток:

12 = p1 + q2 – c12 = 0-1-3=-4

13 = p1 + q3 – c13 = 0+4-6 =-2

23 = p2 + q3 – c23 = 2+4-5 = 1 - max

24 = p2 + q4 – c24 = 2+4-7 = -1

31 = p3 + q1 - c31 = -1+2-5 = -4

32 = p3 + q2 – c32 = -1-1-2 = -4

41 = p4 + q1 – c41 = -4+2-0 = -2

42 = p4 + q2 – c42 = -4-1-0 = -5

43 = p4 + q3 – c43 = -4-4-0 = -8

Находим наибольшую положительную оценку max () = 1 = 23

Для найденной свободной клетки 23 строим цикл пересчета - замкнутую ломаную линию, соседние звенья которой взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы, одна из вершин находится в данной свободной клетке, а все остальные - в занятых клетках.

Это будет 23-21-11-14-34-33-23:

30
5

30+


5-


30
5
0 *

0-



0

44 36

44-

36+



44 36

min =0


потреб


произв

b1=30 b2=55 b3=44 b4=42
a1=35

30

2
3
6 5 4 p1=0




a2=55
4 55 1 0 5
7 p2=1




a3=80
5
2 44 3 36 3 p3=-1




a4=1
0
0
0 1 0 p4=-4





q1=2 q2=0 q3=4 q4=4

14 = 0, p1 + q4 - c14 = 0, q4 =4

34 = 0, p3 + q4 – c34 = 0, p3 = -1

33 = 0, p3 + q3 – c33 = 0, q3= 4

23 = 0, p2 + q3 – c23 = 0, p2 = 1

22 = 0, p2 + q2 – c22 = 0, q2 = 0

44 = 0, p4 + q4 – c44 = 0, p4=-4


Теперь по формуле вычисляем оценки всех свободных клеток:


12 = p1 + q2 – c12 = 0-3=-3

13 = p1 + q3 – c13 = 0+4-6 =-2

21 = p2 + q3 – c23 = 1+2-4 = -1

24 = p2 + q4 – c24 = 1+4-7=-2

31 = p3 + q1 - c31 = -1+2-5 = -4

32 = p3 + q2 – c32 = -1+0-2=-3

41 = p4 + q1 – c41 = -4+2=-2

42 = p4 + q2 – c42 = -4+0=-4

43 = p4 + q3 – c43 = -4+4-0 = 0

Итак, , при

Таким образом, пришли к оптимальному решению


Общая стоимость перевозок: денежных единиц.

Для проверки полученного результата теперь решим задачу методом северо-западного угла.

Метод Северо-западного угла


потреб


произв

b1=30 b2=55 b3=44 b4=42
a1=35


30

2


5

3
6
4 p1=0




a2=55
4

50

1

5

5
7 p2=-2




a3=80

*

5
2 39 3 41 3 p3=-4




a4=1
0
0
0 1 0 p4=-7





q1=2 q2=3 q3=7 q4=7

денежных единиц


11 = 0, p1 + q1 - c11 = 0, q1 = 2

12 = 0, p1 + q2 - c12 = 0, q2 =-3

22 = 0, p2 + q2 – c22 = 0, p2 = -2

33 = 0, p3 + q3 – c33 = 0, q3= 7

34 = 0, p3 + q4 – c34 = 0, q4 =7

44 = 0, p4 + q4 – c44 = 0, p4=-7


Теперь по формуле вычисляем оценки всех свободных клеток:

13 = p1 + q3 – c13 = 0+7-6=1

14 = p1 + q4 – c14 = 0+7-4=3

21 = p2 + q1 – c21 = -2+2-1 =-1

24 = p2 + q4 – c24 = -2+7-7 = -2

31 = p3 + q1 - c31 = -4+2-5=7 ( max)

32 = p3 + q2 – c32 = -4+3-2=-3

41 = p4 + q1 – c41 = -7+2-0=-5

42 = p4 + q2 – c42 = -7+3=-4

43 = p4 + q3 – c43 = -7+7=0



Находим наибольшую положительную оценку max () = 7 = 31


Для найденной свободной клетки 31 строим цикл пересчета:


30 5

30-

5+




35

50 5


50-

5+


20 35
*
39


39-


30
9

min =3


потреб


произв

b1=30 b2=55 b3=44 b4=42
a1=35

*


2


35

3
6
4 p1=0




a2=55
4

20

1

35

5
7 p2=-2




a3=80

30

5
2 9 3 41 3 p3=-4




a4=1
0
0
0 1 0 p4=-7





q1=9 q2=3 q3=7 q4=7

денежных единиц


12 = 0, p1 + q2 - c12 = 0, q2 =3

22 = 0, p2 + q2 – c22 = 0, p2 = -2

23 = 0, p2 + q3 – c23 = 0, q3 = 7

33 = 0, p3 + q3 – c33 = 0, p3= -4

31 = 0, p3 + q1 – c31 = 0, q1 =9

34 = 0, p3 + q4 – c34 = 0, q4=7


Теперь по формуле вычисляем оценки всех свободных клеток:

11 = p1 + q1 – c11 = 0+9-2=7(max)

13 = p1 + q3 – c13 = 0+7-6=1

14 = p1 + q4 – c14 = 0+7-4=3

21 = p2 + q1 – c21 = -2+9-4 =3

24 = p2 + q4 – c24 = -2+7-7 = -2

32 = p3 + q2 – c32 = -4+3-2=-3

41 = p4 + q1 – c41 = -7+9=2

42 = p4 + q2 – c42 = -7+3=-4

43 = p4 + q3 – c43 = -7+7=0



Находим наибольшую положительную оценку max () = 7 = 11

Для найденной свободной клетки 11 строим цикл пересчета:


* 35

*

35-



30 5

20 35


20+

35-


50 5
30
9

30-


9+




39

min =30


потреб


произв

b1=30 b2=55 b3=44 b4=42
a1=35 30 2


5

3
6

*

4 p1=0




a2=55
4

50

1

5

5
7 p2=-2




a3=80
5
2 39 3 41 3 p3=-4




a4=1
0
0
0 1 0 p4=-7





q1=2 q2=3 q3=7 q4=7

денежных единиц


11 = 0, p1 + q1 - c11 = 0, q1 =2

12 = 0, p1 + q2 - c12 = 0, q2 =3

22 = 0, p2 + q2 – c22 = 0, p2 = -2

23 = 0, p2 + q3 – c23 = 0, q3 = 7

33 = 0, p3 + q3 – c33 = 0, p3= -4

34 = 0, p3 + q4 – c34 = 0, q4=7


Теперь по формуле вычисляем оценки всех свободных клеток:

13 = p1 + q3 – c13 = 0+7-6=1

14 = p1 + q4 – c14 = 0+7-4=3(max)

21 = p2 + q1 – c21 = -2+2-4=-4

24 = p2 + q4 – c24 = -2+7-7 = -2

31 = p3 + q1 – c31 = -4+2-5=-7

32 = p3 + q2 – c32 = -4+3-2=-3

41 = p4 + q1 – c41 = -7+2=-5

42 = p4 + q2 – c42 = -7+3=-4

43 = p4 + q3 – c43 = -7+7=0


Находим наибольшую положительную оценку max () = 3= 14

Для найденной свободной клетки 14 строим цикл пересчета:


5
*

5-





5
50 5

50+

5-


55


39 41

39+

41-



44 36

min =5


потреб


произв

b1=30 b2=55 b3=44 b4=42
a1=35 30 2 0 3
6 5 4 p1=0




a2=55
4 55 1
5
7 p2=-2




a3=80
5
2 44 3 36 3 p3=-1




a4=1
0
0
0 1 0 p4=-4





q1=2 q2=3 q3=4 q4=4

11 = 0, p1 + q1 - c11 = 0, q1 =2

14 = 0, p1 + q4 – c14 = 0, q4 = 4

34 = 0, p3 + q4 – c34 = 0, p3= -1

12 = 0, p1 + q2 – c12 = 0, q2 =3

22 = 0, p2 + q2 – c22 = 0, p2=-2

33 = 0, p3 + q3 – c33 = 0, q3= 4

44 = 0, p4 + q4 – c44 = 0, p4= -4


Теперь по формуле вычисляем оценки всех свободных клеток:

13 = p1 + q3 – c13 = 4-6=-2

21 = p2 + q1 – c21 = -2+2-4 =-4

24 = p2 + q4 – c24 = -2+4-7=-5

31 = p3 + q1 – c31 = -1+2-5=-4

32 = p3 + q2 – c32 = -1+3-2=0

41 = p4 + q1 – c41 = -4+2=-2

42 = p4 + q2 – c42 = -4+3=-1

43 = p4 + q3 – c43 = -4+4=0




Таким образом, пришли к оптимальному решению


денежных единиц.


4. Динамическое программирование. Распределение капитальных вложений


Задание:

Методом динамического программирования решить задачу распределения капитальных вложений между четырьмя предприятиями производственного объединения, располагающего суммой в 700 млн. руб., учесть, что выделяемые суммы кратны 100 млн.


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

Динамическое программирование – вычислительный метод, который позволяет решить управленческую задачу как многошаговую оптимизационную задачу, причём многошаговость может быть как естественно, так и искусственно. Процесс решения разворачивается от конца к началу.

Предположим, что имеется 4 пункта, где требуется построить или реконструировать предприятие одной отрасли. Планируется, что после реконструкции экономическая деятельность предприятия принесет прирост прибыли. На реконструкцию всех четырех предприятий выделяется 700 млн. руб. Суммы, выделяемые каждому предприятию, кратны 100 млн. руб. Ожидаемые прибыли каждого предприятия при вложении в них суммы от 0 до 700 млн. руб. известны и заданы следующей таблицей (Табл. 1.):


Табл. 1. Ожидаемые прибыли предприятий.

xj

0

100

200

300

400

500

600

700

f1(x1)

0 5 8 10 12 13 14 15

f2(x2)

0 5 10 14 17 19 21 22

f3(x3)

0 8 13 18 21 23 25 27

f4(x4)

0 6 13 20 27 33 38 41

Где, - прирост мощности или прибыли на j–ом предприятии, если оно получит xi млн. руб. капитальных вложений. При этом ; .

Например, число 25 означает, что если третье предприятие получит 600 млн. руб., то прирост прибыли на этом предприятии составит 25 млн. руб.

Необходимо так распределить , капитальных вложений в предприятия, чтобы суммарный прирост прибыли был бы максимальным:

При ограничениях по общей сумме капитальных вложений:

.


Решение:

Введем параметр состояния t - количество рублей, которое суммарно выделяется сразу k предприятиям и функцию состояния Fk(t) – прибыль, получаемую от k предприятий пи выделении им совместно t млн. рублей. Если k предприятиям выделено t млн. руб., а из них последнее k-ое предприятие получит xk млн. руб., то остальные t-xk млн. руб. должны быть распределены между предприятиями от первого до k-1 - го с таким расчетом, чтобы обеспечить максимальную прибыль . Таким образом, приходим к следующему критерию эффективности:



Используем этот критерий для табулирования функций прибыли и соответствующих им распределений капитальных вложений.

Заполняем табл. 2. Значения f2(x2) складываем со значениями F1(t - x2) = f1(t- x2) и на каждой северо-западной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение.


Табл. 2.


t - x2 0 100 200 300 400 500 600 700
x2

F1(t- x2)

f2(x2)

0 5 8 10 12 13 14 15
0 0 0* 5* 8 10 12 13 14 15
100 5 5 10* 13 15 17 18 19
200 10 10 15* 18 20 22 23
300 14 14 19* 22* 24 26
400 17 17 22 25* 27*
500 19 19 24 27
600 21 21 26
700 22 22

Табл. 3.

t 0

100

200 300 400 500 600 700

0 5 10 15 19 22 25 27
x2 0 0 100 200 300 300 400 400

Продолжая процесс, табулируем функции F3(t):

Табл. 4.


t – x3 0 100 200 300 400 500 600 700
x3

F2(t- x3)

f3(x3)

0 5 10 15 19 22 25 27
0 0 0* 5 10 15 19 22 25 27
100 8 8* 13* 18* 23* 27 30 33
200 13 13 18 23 28* 32 35
300 18 18 23 28 33* 37*
400 21 21 26 31 36
500 23 23 28 33
600 25 25 30
700 27 27

Табл. 5.

t 0 100

200

300 400 500 600 700

0 8 13 18 23 28 33 37
x3 0 100 100 100 100 200 300 300

Теперь табулируем F4(t), заполняем только последнюю диагональ:

Табл. 6.


t – x4 0 100 200 300 400 500 600 700
x4

F3(t- x4)

f4(x4)

0 8 13 18 23 28 33 37
0 0






37
100 6





39
200 13




41
300 20



43
400 27


45
500 33

46*
600 38
46
700 41 41

Наибольшее число на этой диагонали равно 46, Это означает, что максимальный суммарный прирост прибыли, приносимой предприятиями после реконструкции, составит 46 млн. руб.:

Zmax = 46 млн. руб.,

х*4 = 500 млн. руб.

х*3 = х3(700-500)= х3(200)=100 млн. руб.

х*2 = х2(700-500-100)= х2(100)=0 млн. руб.

х*1 = 700-500-100-0=100 млн. руб.

Таким образом, оптимальное распределение капитальных вложений в предприятия будет выглядеть следующим образом:

X*=(100, 0, 100, 500).

Проверим выполнение равенства:

млн. руб.


5. Задача формирования оптимального портфеля ценных бумаг


Задание:

Решить задачу формирования оптимального портфеля ценных бумаг: бумаги первого вида - безрисковые ожидаемой эффективности m0, а второго и третьего вида - некоррелированные рисковые ожидаемых эффективностей m1, m2 c рисками 1, 2.


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

Участник рынка имеет возможность приобретать Ц.Б. На рынке имеется три вида ценных бумаг: государственные безрисковые и два вида рисковых ценных бумаг.

Пусть xi – доля ценных бумаг i-го вида, которые имеет участник рынка (). Каждая из бумаг i-го вида приносит определённый доход Еi, который в общем случае случаен. Обозначим:

mi – математическое ожидание дохода от i-ой ценной бумаги,

ri - среднее квадратичное отклонение дохода от i-ой ценной бумаги.

В общем случае, случайные доходы одного типа ценных бумаг зависят от дохода, получаемому по другому типу ценных бумаг.

Обозначим Vij – ковариация (корреляционный момент связи) между случайными величинами: доходом от ценной бумаги i-го и j-го видов.

Пакет ценных бумаг, находящихся у участников рынка, принято называть портфелем ценных бумаг. Поскольку, доход от каждого типа Ц.Б. является случайной величиной, то общий доход от общего портфеля в целом также является случайной величиной:

А общая дисперсия дохода составит:

Риск от реализации одной ценной бумаги отождествляется с «разбросом» дохода, т.е. со средним квадратичным отклонением.

Если , то существует две постановки задачи формирования оптимального портфеля ценных бумаг:

портфель минимального риска;

портфель максимального дохода;

Рассмотрим математическую постановку задачи портфеля минимального риска: найти значения неизвестных xi, которые обеспечивают минимизацию функции общего риска портфеля:


, при следующих ограничениях:


- обеспечивается заданное значение ожидаемой эффективности портфеля mp;

- сумма долей всех бумаг равна единице;

Математическая постановка задачи портфеля максимизации дохода: найти значения xi, которые обеспечивают максимизацию общего дохода портфеля:

, при ограничениях:


Решение:

Доход одной денежной единицы на каждую из бумаг задан: mo=2 m1=4 m2=9. Известны также риски рисковых бумаг: r1=8 r2=10.

Обозначим:

z – доли государственных ценных бумаг;

х – долю рисковых бумаг 1-ого вида;

у – долю рисковых бумаг 2-ого вида;

Тогда доход всего портфеля можно представить в следующем виде:

mp = 2z + 4x + 9y денежных единиц, а дисперсию этого портфеля в виде:

Так как x + y + z=1, то z= 1 – x – y

Подставим в mp: mp=2(1 – x - y) + 4x + 9y=2 + 2x+ 7y;

Найдем значения x, y, при которых функция , при следующих ограничениях:

Для этого составим функцию Лагранжа и найдём её частные производные.


L(x; y) = 64x2 + 100y2 + λ(2+2x + 7y - mp)

Приравняв производные к нулю, получим систему:

Решая полученную систему:

Докажем что это min. Для этого найдем вторые частные производные


Δ = AC - B2 = 128200-0 > 0 => экстремум есть, т.к. А и С > 0, это min.


Найдем интервал mр, подставив найденные значения x, y в систему ограничений:


Проведем анализ результатов с помощью таблицы:


mp

2

3

4

5

6

7

z


1

0
x 0

y 0

0 1,35 2,7 4,04 5,38 6,73 7,34

Расчеты:


При mp=3:

При mp=4:


При mp=5


При mp=6


При mp=7


При mp=

Строим график зависимости ожидаемого дохода от риска:

mp

6. Матричная игра как модель конкуренции

и сотрудничества


Теория игр: совокупность математических методов, анализа и оценки поведения в конфликтных ситуациях, когда сталкиваются интересы двух или более сторон, преследующие различные, иногда противоположные цели. Противоречащие друг другу интересы наблюдаются в области экономики, военном деле, спорте, иногда противоречат интересы различных ступеней иерархии в СУ. Теория игр представляет собой математическую теорию конфликтных ситуаций. Ее цель-выработка рекомендаций по разумному поведению участников конфликта.


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

Рассмотрим матричную игру двух лиц с нулевой суммой.

Задана матрица:

Участвуют 2 игрока. 1-ый выбирает номер строки, а 2-ой независимо от 1-го выбирает номер столбца. Если 1-ый загадал 2-ую строку, а второй – 2-ой столбец, то выигрыш второго составляет 8 рублей.

Вначале проведем анализ на доминирование. Так как строки выбирает первый игрок, то мы исключаем из платежной матрицы доминируемые строки. Первая строка доминирует третью. В результате исключения третьей строки получаем:

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

Далее проведем анализ игры на седловую точку. Найдем минимумы по строкам и максимумы по столбцам :



Нижняя цена игры будет равна: верхняя цена игры равна: .

Поскольку , то решения игры в чистых стратегиях нет. Будем искать решение в смешанных стратегиях. Чтобы сделать все элементы платежной матрицы положительными, прибавим к каждому ее элементу константу, равную 10, при этом решение игры не изменится, а цена игры возрастет на 10 и будет больше нуля. Матрица игры примет следующий вид:

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

Проигрыш Второго игрока будет не больше, чем цена игры :

Разделим каждое из неравенств на и введем обозначения , получим:

Поскольку , то переменные x1, x2, x3, x4 удовлетворяют условию:

, но v есть проигрыш второго игрока, который он стремится сделать минимальным. Следовательно, величина должна быть максимальна. Таким образом, имеем следующую задачу линейного программирования:

Найти вектор , который обеспечивает максимум целевой функции , при следующих линейных ограничениях:


Решение:

Найдем ее оптимальное решение симплексным методом.

Итак, , при

Сначала приведем эту задачу к основной задаче линейного программирования:

Превратим неравенства в равенства, ля этого добавим к каждому неравенству дополнительные неотрицательные неизвестные x5, x6, x7. Вспомогательная задача будет иметь вид:


, при ограничениях:


Откуда: ;


Составляем симплексную таблицу:


Ć

Б

Н

X1

X2

X3

X4

X5

X6

X7

Пояснения

0

X5

1 10 5

13

9 1 0 0

max(j>0)= 31

min(α)=1/17,

x3 в базис, x6 из базиса

0

X6

1

14

2

17

0

0

1

0

0

X7

1 4 12

1

15 0 0 1


3-S 28 19

31

13 0 0 0
0

X5

4/17

-12/17

59/17

0

9

1


0

max(j>0)= 24

min(α)=,x4 в базис, x5 - из

-1

X3

1/17 14/17 2/17 1

0

0 0
0

X7

16/17 54/17 202/17 0

15

0 1


20/17 -S 42/17 261/17 0

24

0 0
-1

X4

4/153

-12/153

59/153

0

1



0

max(j>0)= 933/153

min(α)=4/59, x2 в базис, x4 - из

-1

X3

1/17 14/17

2/17

1 0 0
0

X7

84/153 666/153

933/153

0 0 1


84/153-S 666/153

933/153

0 0 0
-1

X2

4/59

-12/59

1 0 153/59

0

max(j>0)= 330/59

min(α)=8/330, x1 в базис, x7 - из

-1

X3

3/59

50/59

0 1 -18/59 0
0

X7

8/59

330/59

0

0

-933/59

1



8/59-S

330/59

0 0 -933/59 0
-1

X2

24/330 0 1 0 666/330


-1

X3

10/330 0 0 1 690/330
-1

X1

8/330 1 0 0 -933/330


0-S 0 0 0 0

;

Вернемся теперь к решению основной задачи, в целевую функцию входят решения:

Ć

Б

Н

X1

X2

X3

X4

Пояснения

-1

X2

24/330 0 1 0 666/330

-1

X3

10/330 0 0 1 690/330
-1

X1

8/330 1 0 0 -933/330


-42/330-K 0 0

0

-423/330

, тогда ;

Цена игры равна ;

Найдем теперь оптимальную стратегию P* первого игрока. Выигрыш первого игрока будет не меньше, чем цена игры:

Разделим каждое из этих неравенств на и введем обозначения . Получим:

Поскольку , то

Но есть выигрыш Первого игрока, который стремиться его максимизировать. Следовательно, величина должна быть минимальна. Таким образом, имеем следующую задачу линейного программирования:

Найти вектор , который обеспечивает минимум целевой функции , при следующих ограничениях:

Эта задача является двойственной по отношению к рассмотренной выше задаче.

Прямая задача: Двойственная задача:




; ;

;

Т.к. x1, x2, x3 отличны от нуля:

;

, а цена игры по-прежнему равна ;

;

Теперь возвращаемся к исходной матрице игры . Решение игры принимает вид:

; ; ;



q1=4/21

q2=12/21

q3=5/21

q4=0

p1=2/7

0 -5 3 -1

P2=3/14

4 -8 7 -10

P3=7/14

-6 2 -9 5

Найдем риск игры при использовании игроками своих оптимальных стратегий:

;

А также риск при использовании одним из игроков своей чистой, а другим – своей оптимальной стратегии (нижний индекс – Первого игрока, верхний – Второго):

; ;

; ;

; ;

; ;

; ;

; ;

; ;

Минимальное значение риска равно и меньше . Этот риск соответствует ситуации, когда первый игрок играет по своей чистой первой стратегии P1, а второй игрок использует оптимальную стратегию Q*. Однако, играть с таким риском можно только с согласия обеих игроков, т.е. при их сотрудничестве друг с другом.


7. Анализ доходности и риска финансовых операций


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

В реальной жизни мы имеем дело с финансовыми операциями. Финансовой называется операция, начальное и конечное состояния которой имеют денежную оценку и цель проведения которой заключается в максимизации дохода - разности между конечной и начальной оценками.

Почти всегда финансовые операции проводятся в условиях неопределенности и потому их результат невозможно предсказать заранее. Поэтому финансовые операции рискованны, т.е. при их проведении возможны как прибыль так и убыток (или не очень большая прибыль по сравнению с той, на что надеялись проводившие эту операцию).

Таким образом, любая финансовая операция должна быть оценена, по крайней мере, по двум показателям, а именно: доход – риск.

Предположим, что имеется несколько таких операций, каждая из которых характеризуется случайным доходом Q.

Средний ожидаемый доход Q - это математическое ожидание с.в. Q: , где pi есть вероятность получить доход qi. А среднее квадратическое отклонение - это мера разбросанности возможных значений дохода вокруг среднего ожидаемого дохода. Вполне разумно считать  количественной мерой риска операции и обозначить r. Дисперсия

D[Q] = M [(Q - Q)2] = M [Q2] - Q2.

Рассмотрим четыре операции Q1, Q2, Q3, Q,4. Найдем средние ожидаемые доходы Qi и риски ri операций.

Ряды распределения, средние ожидаемые доходы и риски:

0 8 12 24
1/4 1/4 1/3 1/6


-6 -2 0 -6
1/4 1/4 1/3 1/6


0 2 4 16
1/3 1/3 1/6 1/6


-6 -5 -4 3
1/3 1/3 1/6 1/6


; ; ;


; ; ;


; ; ;


; ; ;


Нанесем средние ожидаемые доходы Q и риски r на плоскость - доход откладываем по горизонтали, а риски п

r

о вертикали (см. рис.):




Получили 4 точки. Чем правее точка (Q, r), тем более доходная операция, чем точка выше - тем более она рисковая. Значит, нужно выбирать точку правее и ниже. Точка (Q, r) доминирует точку (Q, r) если Q Q и r  r. В нашем случае точка 2 доминирует точку 4.

Точка, не доминируемая никакой другой, называется оптимальной по Парето, а множество всех таких точек называется множеством оптимальности по Парето. Легко видеть, что если из рассмотренных операций надо выбирать лучшую, то ее обязательно надо выбрать из операций, оптимальных по Парето.

Найдем лучшею операцию по формуле:  (Q)= 2Q - r , критерием оптимальности будет являться принцип максимизации результата для этого показателя, получаем:

 (Q1)=2·10-7,75=12,25;

 (Q2)=2· (-3)-2,65= -8,65;

 (Q3)=2·4-5,54=2,46;

 (Q4)= 2· (-23/6)-3,13≈ -10,8

Видно, что 1-ая операция – лучшая, а 4-ая – худшая. Таким образом точками, оптимальными по Парето являются точки: 1 и 3.


8. Принятие решений в условиях неопределенности


Задание:

Рассмотреть задачу принятия решений в условиях неопределенности, исходные данные:

0 8 12 24
1/4 1/4 1/3 1/6
0 2 4 16
1/3 1/3 1/6 1/6



-6 -2 0 -6
1/4 1/4 1/3 1/6
-6 -5 -4 3
1/3 1/3 1/6 1/6


Решение:

Предположим, что ЛПР (Лицо, Принимающее Решения) рассматривает четыре возможных решения. . Ситуация неопределенна, наличествует какой-то из вариантов . Если будет принято -e решение, а ситуация есть -я , то фирма, возглавляемая ЛПР, получит доход . Матрица - матрица последствий (возможных решений) задана:

Для того, чтобы оценить риск, который несет -e решение, задана матрица рисков

Составим матрицу рисков. Имеем q1=0; q2=8; q3=12; q4=24. Следовательно, матрица рисков есть:

Ситуация полной неопределенности характеризуется отсутствием какой бы то ни было дополнительной информации. Существуют правила-рекомендации по принятию решений в этой ситуации:

Правило Вальда (правило крайнего пессимизма). Рассматривая -e решение будем полагать, что на самом деле ситуация складывается самая плохая, т.е. приносящая самый малый доход .

Но теперь уж выберем решение с наибольшим . Итак, правило Вальда рекомендует принять решение , такое что

Так, в нашей задаче, имеем a1=0; a2=-6; a3=0; a4=-6. Теперь из этих чисел находим максимальное. Это – 0 . Значит, правило Вальда рекомендует принять 1-ое или 3-е решение.

Правило Сэвиджа (правило минимального риска). При применении этого правила анализируется матрица рисков . Рассматривая -e решение будем полагать, что на самом деле складывается ситуация максимального риска

Но теперь уж выберем решение с наименьшим . Итак, правило Сэвиджа рекомендует принять решение , такое что

Так, в нашей задаче , имеем b1=0; b2=30; b3=8; b4=21. Теперь из этих чисел находим минимальное. Это – 0. Значит правило Сэвиджа рекомендует принять 1-ое решение.

Правило Гурвица (взвешивающее пессимистический и оптимистический подходы к ситуации). Принимается решение , на котором достигается максимум

где . Значение выбирается из субъективных соображений. Если приближается к 1, то правило Гурвица приближается к правилу Вальда, при приближении к 0, правило Гурвица приближается к правилу "розового оптимизма". При правило Гурвица рекомендует 1-ое решение:


1/2·(0)+1/2·24= 12

1/2· (-6)+1/2·0= -3

1/2· (0)+1/2·16= 8

1/2· (-6)+1/2·3= -3/2


Предположим, что в рассматриваемой схеме известны вероятности того, что реальная ситуация развивается по варианту . Именно такое положение называется частичной неопределенностью. Как здесь принимать решение? Можно выбрать одно из следующих правил.

Правило максимизации среднего ожидаемого дохода. Доход, получаемый фирмой при реализации -го решения, является случайной величиной с рядом распределения






Математическое ожидание и есть средний ожидаемый доход, обозначаемый также . Итак, правило рекомендует принять решение, приносящее максимальный средний ожидаемый доход.

В схеме из предыдущего п. вероятности есть (1/4, 1/4, 1/3, 1/6). Тогда

Q1= 0*1/4+8*1/4+12*1/3+24*1/6=10

Q2= -6*1/4-2*1/4+0*1/3-6*1/6= -3

Q3= 0*1/4+2*1/4+4*1/3+16*1/6= 4,5

Q4= -6*1/4-5*1/4-4*1/3+3*1/6= -43/12≈ -3,58

Максимальный средний ожидаемый доход равен 10, что соответствует 1-му решению.

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







Математическое ожидание и есть средний ожидаемый риск, обозначаемый также . Правило рекомендует принять решение, влекущее минимальный средний ожидаемый риск.

Вычислим средние ожидаемые риски при указанных выше вероятностях. Получаем:

R1=0*1/4+0*1/4+0*1/3+0*1/6=0

R2=6*1/4+10*1/4+12*1/3+30*1/6=13

R3=0*1/4+6*1/4+8*1/3+8*1/6=11/2=5,5

R4=6*1/4+13*1/4+16*1/3+21*1/6=163/12≈13,58

Минимальный средний ожидаемый риск равен 0, что соответствует 1-му решению.

Нанесем средние ожидаемые доходы и средние ожидаемые риски на плоскость – доход откладываем по вертикали, а риски по горизонтали (см. рис.):


Получили 4 точки. Чем выше точка , тем более доходная операция, чем точка правее – тем более она рисковая. Значит, нужно выбирать точку выше и левее. Точка доминирует точку , если и и хотя бы одно из этих неравенств строгое. В нашем случае 1-ая операция доминирует все остальные.

Точка, не доминируемая никакой другой называется оптимальной по Парето, а множество всех таких точек называется множеством оптимальности по Парето. Легко видеть, что если из рассмотренных операций надо выбрать лучшую, то ее обязательно надо выбрать из операций, оптимальных по Парето. В нашем случае, множество Парето, т.е. оптимальных по Парето операций, состоит только из одной 1-ой операции.

ж) Для нахождения лучшей операции иногда применяют подходящую взвешивающую формулу, которая для пар дает одно число, по которому и определяют лучшую операцию. Например, пусть взвешивающая формула есть . Тогда получаем:

f(Q1)=2*10-0 =20

f(Q2)=2*(-3)-13= -19

f(Q3)=2*4,5-5,5=3,5

f(Q4)=2*(-43/12)-163/12= -83/4= -20,75

Видно, что 1-ая операция – лучшая, а 4-ая – худшая.