Курсовая Прикладная математика 2
Работа добавлена на сайт bukvasha.net: 2015-10-25Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
Федеральное агентство по образованию
Государственное образовательное учреждение высшего профессионального образования
ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ УПРАВЛЕНИЯ
Кафедра прикладной математики
КУРСОВАЯ РАБОТА
по дисциплине "Прикладная математика"
Выполнила:
Институт: ИУХМП
Специальность: Менеджмент организации
Отделение (д/о, в/о): дневное отделение
Курс: II
Группа: М/О II-1
Руководитель: Чистяков В.С.
Дата сдачи на проверку : ...………………………..
Дата защиты: .........................................
Оценка: .........................................
Подпись руководителя: ..........................................
Москва - 2006
Содержание
1) Цели и задачи курсового проекта…………………………………. ...3
2) Линейная производственная задача………………………………… ..3
3) Двойственная задача…………………………………………………… 6
4) Транспортная задача линейного программирования……………….12
5) Динамическое программирование. Распределение капитальных вложений…………………………………………………………………19
6) Задача формирования оптимального портфеля ценных бумаг……22
7) Матричная игра как модель конкуренции и сотрудничества… …27
8) Анализ доходности и риска финансовых операций…………… ….33
9) Принятие решений в условиях неопределенности………………. ..35
ЦЕЛИ И ЗАДАЧИ КУРСОВОГО ПРОЕКТА
Выполнение курсового проекта по прикладной математике направлено на усиление связи обучения студентов с практикой совершенствования управления, организации современного производства, всего механизма хозяйствования.
В процессе работы над курсовым проектом студент не только закрепляет и углубляет теоретические знания, полученные на лекциях и на практических занятиях, но и учится применять методы исследования операций при постановке и решении конкретных экономических задач.
Цель курсового проекта - подготовить студента к самостоятельному проведению операционного исследования, основными этапами которого являются построение математической модели, решение управленческой задачи при помощи модели и анализ полученных результатов.
1. Линейная производственная задача
Задание:
Сформулировать линейную производственную задачу и составить ее математическую модель, где заданы технологическая матрица А затрат различных ресурсов на единицу каждой продукции, вектор объемов ресурсов В и вектор удельной прибыли С при возможном выпуске четырех видов продукции с использованием трех видов ресурсов
Преобразовать данную задачу к виду основной задачи линейного программирования, решить ее, найти оптимальную производственную программу, максимальную прибыль, остатки ресурсов различных видов и указать ²узкие места² производства.
В последней симплексной таблице указать обращенный базис Q-1, соответствующий оптимальному набору базисных неизвестных. Проверить выполнение соотношения
H = Q-1B
Если по оптимальной производственной программе какие-то два вида продукции не должны выпускаться, то в таблице исходных данных вычеркнуть соответствующие два столбца, составить математическую модель задачи оптимизации производственной программы с двумя оставшимися переменными, сохранив прежнюю нумерацию переменных и решить графически.
Постановка задачи:
Компания «Малыш» выпускает четыре вида детского питания, используя для этого сухое молоко, сою и фруктовое пюре. Известна технологическая матрица А затрат любого вида ресурса на единицу каждого вида питания, вектор В объемов имеющихся ресурсов и вектор С стоимости каждого вида питания.
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
-ого вида.
На производство x
1 питания 1-го вида
x
2 питания 2-го вида
x
3 питания 3-го вида
x
4 питания 4-го вида компания затратит следующее количество ресурсов:
Требуется найти производственную программу X
*
= (
x
1
,
x
2
,
x
3
,
x
4
), реализация которой обеспечит компании получение наибольшей прибыли:
,
при линейных ограничениях неравенства (1).
Решение:
Приведем задачу к основной задаче линейного программирования. Для этого добавим в левую часть системы ограничений (1) дополнительные неотрицательные неизвестные x
5
,
x
6
,
x
7
, которые по физическому смыслу будут представлять собой:
x
5
– остаток ресурса 1-го вида,
x
6
– остаток ресурса 2-го вида,
x
7
– остаток ресурса 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
= -30
x1-25x2-14x3-12x4
| Ć | Б | Н | X1 | X2 | X3 | X4 | X5 | X6 | X7 | α | Пояснения |
| 0 | X5 | 148 | 2 | 3 | 0 | 4 | 1 | 0 | 0 | 74 | min ( D j <0)= -30 min (α)=29, x 1 в базис, x 6 из базиса |
| 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 ( D j <0)= -35/2 min (α)=36, x 2 в базис, x 5 из базиса |
| 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 | |
x
1
=20,
x
2
=36,
x
3
=0,
x
4
=0,
x
5
=0,
x
6
=0,
x
7
=18 определяют производственную программу x
1
=20,
x
2
=36,
x
3
=0,
x
4
=0
Прибыль будет наибольшей когда
остатки ресурсов: 1-ого вида x
5
=0
2-ого вида x
6
=0
3-ого вида x
7
=18
Также надо обратить внимание на экономический смысл элементов последней строки последней симплексной таблицы. Коэффициенты ∆3 =6 при переменной Х3, ∆4 =16 при переменной Х4 показывают, что если произвести одну единицу продукции 3-ого или 4-ого видов, то прибыль уменьшится на 6 или 16 единиц соответственно.
Проверим выполнение соотношения H=Q-1B:
Равенство выполняется.
Итак, по оптимальной производственной программе у нас получилось, что третий и четвертый вид детского питания не должны выпускаться. В таблице исходных данных вычеркнем соответствующие два столбца и составим математическую модель задачи оптимизации производственной программы с двумя оставшимися переменными, сохранив прежнюю нумерацию переменных и решим эту задачу графически.
Математическая модель будет выглядеть так:
Z
= 30
x
1
+ 25
x
2
→
max
2. Двойственная задача
Задание:
Сформулировать задачу, двойственную линейной производственной задаче, как задачу определения расчетных оценок ресурсов, и найти ее решение, пользуясь второй основной теоремой двойственности. Указать оценку единицы каждого ресурса, минимальную суммарную оценку всех ресурсов, оценки технологий.
Применить найденные двойственные оценки ресурсов к решению следующей задачи.
Сформулировать задачу о "расшивке узких мест производства" и составить математическую модель. Определить область устойчивости двойственных оценок, где сохраняется структура программы производства. Решить задачу о ²расшивке узких мест производства² при условии, что дополнительно можно получить от поставщиков не более одной трети первоначально выделенного объема ресурса любого вида (если задача окажется с двумя переменными, то только графически); найти план приобретения дополнительных объемов ресурсов, дополнительную возможную прибыль, составить сводку результатов.
Постановка задачи:
Ранее мы рассмотрели конкретную линейную производственную задачу по выпуску четырех видов детского питания с использованием трех видов ресурсов Технологическая матрица А затрат любого вида ресурса на единицу каждого вида питания была известна.
Теперь представим себе, что возникла новая ситуация. предприниматель П. (Петров), занимающийся производством каких-то других видов продукции, но с использованием трех таких же видов ресурсов, какие имеются у компании «Малыш», предлагает ей "уступить" по определенным ценам все имеющиеся у «Малыша» ресурсы и обещает платить у1 рублей за каждую единицу первого ресурса, у2 руб. – второго, у3 руб. – третьего. Возникает вопрос: при каких ценах у1, у2, у3 компания «Малыш» может согласиться с предложением П.
Величины у1, у2, у3 это двойственные оценки ресурсов. Они прямо зависят от условий, в которых действует компания «Малыш».
В нашей задаче технологическая матрица А, вектор объемов ресурсов В и вектор удельной прибыли С имели вид:
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, y
2
,
y
3
), минимизирующий общую оценку всех ресурсов:
при условии, что по каждому виду детского питания суммарная оценка всех ресурсов, затрачиваемых на производство единицы детского питания, не меньше прибыли, получаемой от реализации единицы этой вида питания:
Решение:
Решение полученной задачи легко найти с помощью второй основной теоремы двойственности.
| Прямая задача: | Двойственная задача: |
| | |
Согласно второй основной теореме двойственности для оптимальных решений X
*
=(х1, х2, х3, х4) и Y
*
=(y1, y2, y3) пары двойственных задач необходимо и достаточно выполнение условий:
При решении прямой задачи было получено, что x
1
>0,
x
2
>0. Поэтому:
Если же учесть, что третий ресурс был избыточным и, согласно той же теореме двойственности, его двойственная оценка равна нулю т.е. y3=0, то приходим к системе уравнений:
Решение двойственной задачи Y
*
=(7, 4, 0)
Тогда общая оценка всех ресурсов равна
Заметим, что решение (3) содержалось в последней строке последней симплексной таблицы исходной задачи. Важен экономический смысл двойственных оценок. Например, двойственная оценка второго ресурса у2=4 показывает, что добавление одной единицы второго ресурса обеспечит прирост прибыли в 4 единицы.
Задача о "расшивке узких мест производства"
П
остановка задачи:
Продолжаем рассмотрение задачи планирования производства. При выполнении оптимальной производственной программы
5
=0,
x
6
=0. Будем «расшивать узкие места производства» т.е. заказывать дополнительно дефицитные ресурсы. Обозначим через t
1
и t
2 искомое дополнительное количество единиц первого и второго вида ресурсов. T(t1, t2, 0)- вектор дополнительных объемов ресурсов. Согласно третьей основной теореме двойственности, увеличение первого вида ресурса на единицу обеспечивает прирост прибыли, равный двойственной оценке y
1
=7, второго вида – y
2
=4.
При этом, для сохранения структуры плана производства величины t1, t2, t3 должны изменяться лишь в области устойчивости двойственных оценок, т.е. должно выполняться условие:
H + Q-1T
Таким образом, проблема «расшивки узких мест производства» представляет собой задачу линейного программирования: найти план расшивки - вектор T (t1, t2, 0), максимизирующий суммарный прирост прибыли:
при условии сохранения двойственных оценок ресурсов (и, следовательно, структуры производственной программы).
Обращенный базис был найден при решении задачи симплексным методом:
Условия (1) запишутся в виде:
Предположим также, что поставщики сырья могут выделить компании не более 1/3 первоначального объема ресурса каждого вида:
Перепишем неравенства (3) и (4) в виде:
Задача оптимизации плана «расшивки узких мест» производства принимает вид: найти переменные t1 и t2, которые обеспечивают максимум линейной форме:
Решение:
Сформулированная задача линейного программирования с двумя переменными может быть решена графически.
При этом прирост прибыли составит: 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
-го пункта отправления (
Необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы по доставке продуктов были минимальными.
Обозначим через хij количество груза, планируемого к перевозке от i-го поставщика (
Общий объем производства åа
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 | x 14 | 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;
2) одно из уравнений системы ограничений линейно зависит от других, в силу чего число базисных неизвестных в системе равно
Эти особенности позволяют решить задачу специально разработанными методами: методом северо-западного угла или методом наименьших затрат. Мы решим ее двумя способами.
Метод наименьших затрат
| потреб произв | b1=30 | b2=55 | b3=44 | b4=42 | ||||||
| a1=35 | | 2 | | 3 | | 6 | | 4 | p1=0 | |
| | | | | |||||||
| a2=55 | | 4 | 55 | 1 | | 5 | | 7 | p2=2 | |
| | | | | |||||||
| a3=80 | | 5 | | 2 | | 3 | 36 | 3 | p3=-1 | |
| | | | | |||||||
| a4=1 | | 0 | | 0 | | 0 | 1 | 0 | p4=-4 | |
| | | | | |||||||
| q1=2 | q2=-1 | q3=4 | q4=4 | |||||||
Обозначим через m
Один из потенциалов можно выбрать произвольно, так как в системе (1) одно уравнение линейно зависит от остальных. Положим, что р1 = 0. Остальные потенциалы находим из условия, что для базисных клеток
D
11
= 0,
p
1
+
q
1
-
c
11
= 0,
q
1
= 2
D
14
= 0,
p
1
+
q
4
-
c
14
= 0,
q
4
= 4
D
34
= 0, p3 + q4 – c34 = 0, p3 = -1
D
33
= 0, p3 + q3 – c33 = 0, q3= 4
D
21
= 0, p2 + q1 – c21 = 0, p2 = 2
D
22
= 0,
p
2
+
q
2
–
c
22
= 0,
q
2
= -1
D
44
= 0,
p
4
+
q
4
–
c
44
= 0,
p
4
=-4
Теперь по формуле
D
12
= p1 + q2 – c12 = 0-1-3=-4
D
13
= p1 + q3 – c13 = 0+4-6 =-2
D
23
= p2 + q3 – c23 = 2+4-5 = 1
-
max
D
24
= p2 + q4 – c24 = 2+4-7 = -1
D
31
= p3 + q1 - c31 = -1+2-5 = -4
D
32
= p3 + q2 – c32 = -1-1-2 = -4
D
41
= p4 + q1 – c41 = -4+2-0 = -2
D
42
= p4 + q2 – c42 = -4-1-0 = -5
D
43
=
p
4
+
q
3
–
c
43
= -4-4-0 = -8
Находим наибольшую положительную оценку max
(
) = 1 = D
23
Для найденной свободной клетки 23 строим цикл пересчета - замкнутую ломаную линию, соседние звенья которой взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы, одна из вершин находится в данной свободной клетке, а все остальные - в занятых клетках.
Это будет 23-21-11-14-34-33-23:
| 30 | | 5 | | 30+ | | 5- | | 30 | | 5 |
| 0 | * | | | 0- | | | | | 0 | |
| | 44 | 36 | | | 44- | 36+ | | | 44 | 36 |
=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 | |||||||
D
14
= 0, p1 + q
4
- c1
4
= 0,
q
4
=
4
D
34
= 0, p3 + q4 – c34 = 0,
p3 = -1
D
33
= 0, p3 + q3 – c33 = 0, q3= 4
D
2
3
= 0, p2 + q
3
– c2
3
= 0, p2 =
1
D
22
= 0, p2 + q2 – c22 = 0, q2 =
0
D
44
= 0, p4 + q4 – c44 = 0, p4=-4
Теперь по формуле
D
12
= p1 + q2 – c12 = 0-3=-3
D
13
= p1 + q3 – c13 = 0+4-6 =-2
D
21
= p2 + q3 – c23 = 1+2-4 = -1
D
24
= p2 + q4 – c24 = 1+4-7=-2
D
31
= p3 + q1 - c31 = -1+2-5 = -4
D
32
= p3 + q2 – c32 = -1+0-2=-3
D
41
= p4 + q1 – c41 = -4+2=-2
D
42
= p4 + q2 – c42 = -4+0=-4
D
43
=
p
4
+
q
3
–
c
43
= -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 | | 1 | | 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 | |||||||
| D 11 = 0, p1 + q1 - c11 = 0, q1 = 2 D 12 = 0, p1 + q2 - c12 = 0, q2 =-3 D 22 = 0, p2 + q2 – c22 = 0, p2 = -2 D 33 = 0, p3 + q3 – c33 = 0, q3= 7 D 34 = 0, p3 + q4 – c34 = 0, q4 =7 D 44 = 0, p4 + q4 – c44 = 0, p4=-7 | Теперь по формуле D 13 = p1 + q3 – c13 = 0+7-6=1 D 14 = p1 + q4 – c14 = 0+7-4=3 D 21 = p2 + q1 – c21 = -2+2-1 =-1 D 24 = p2 + q4 – c24 = -2+7-7 = -2 D 31 = p3 + q1 - c31 = -4+2-5=7 ( max) D 32 = p3 + q2 – c32 = -4+3-2=-3 D 41 = p4 + q1 – c41 = -7+2-0=-5 D 42 = p4 + q2 – c42 = -7+3=-4 D 43 = p 4 + q 3 – c 43 = -7+7=0 |
Находим наибольшую положительную оценку max
(
) = 7 = D
31
Для найденной свободной клетки 31 строим цикл пересчета:
| 30 | 5 | | | 30 - | 5+ | | | | 35 | |
| | 50 | 5 | | | 50- | 5+ | | | 20 | 35 |
| * | | 39 | | | | 3 9- | | 30 | | 9 |
=3
| потреб произв | b1=30 | b2=55 | b3=44 | b4=42 | ||||||
| a1=35 | | 2 | 3 5 | 3 | | 6 | | 4 | p1=0 | |
| | | | | |||||||
| a2=55 | | 4 | | 1 | 5 | 5 | | 7 | p2= -2 | |
| | | | | |||||||
| a3=80 | | 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 | |||||||
| D 12 = 0, p1 + q2 - c12 = 0, q2 =3 D 22 = 0, p2 + q2 – c22 = 0, p2 = -2 D 23 = 0, p2 + q3 – c23 = 0, q3 = 7 D 33 = 0, p3 + q3 – c33 = 0, p3= -4 D 31 = 0, p3 + q1 – c31 = 0, q1 =9 D 34 = 0, p3 + q4 – c34 = 0, q4=7 | Теперь по формуле D 11 = p1 + q1 – c11 = 0+9-2=7(max) D 13 = p1 + q3 – c13 = 0+7-6=1 D 14 = p1 + q4 – c14 = 0+7-4=3 D 21 = p2 + q1 – c21 = -2+9-4 =3 D 24 = p2 + q4 – c24 = -2+7-7 = -2 D 32 = p3 + q2 – c32 = -4+3-2=-3 D 41 = p4 + q1 – c41 = -7+9=2 D 42 = p4 + q2 – c42 = -7+3=-4 D 43 = p 4 + q 3 – c 43 = -7+7=0 |
Находим наибольшую положительную оценку max
(
) = 7 = D
11
Для найденной свободной клетки 11 строим цикл пересчета:
| * | 35 | | | * | 35- | | | 30 | 5 | |
| | 20 | 35 | | | 20+ | 35- | | | 50 | 5 |
| 30 | | 9 | | 30- | | 9+ | | | | 39 |
=30
| потреб произв | b1=30 | b2=55 | b3=44 | b4=42 | ||||||
| a1=35 | 30 | 2 | 5 | 3 | | 6 | | 4 | p1=0 | |
| | | | | |||||||
| a2=55 | | 4 | | 1 | | 5 | | 7 | p2= -2 | |
| | | | | |||||||
| a3=80 | | 5 | | 2 | 3 9 | 3 | 41 | 3 | p3=- 4 | |
| | | | | |||||||
| a4=1 | | 0 | | 0 | | 0 | 1 | 0 | p4=- 7 | |
| | | | | |||||||
| q1=2 | q2= 3 | q3= 7 | q4= 7 | |||||||
| D 11 = 0, p1 + q1 - c11 = 0, q1 =2 D 12 = 0, p1 + q2 - c12 = 0, q2 =3 D 22 = 0, p2 + q2 – c22 = 0, p2 = -2 D 23 = 0, p2 + q3 – c23 = 0, q3 = 7 D 33 = 0, p3 + q3 – c33 = 0, p3= -4 D 34 = 0, p3 + q4 – c34 = 0, q4=7 | Теперь по формуле D 13 = p1 + q3 – c13 = 0+7-6=1 D 14 = p1 + q4 – c14 = 0+7-4=3(max) D 21 = p2 + q1 – c21 = -2+2-4=-4 D 24 = p2 + q4 – c24 = -2+7-7 = -2 D 31 = p3 + q1 – c31 = -4+2-5=-7 D 32 = p3 + q2 – c32 = -4+3-2=-3 D 41 = p4 + q1 – c41 = -7+2=-5 D 42 = p4 + q2 – c42 = -7+3=-4 D 43 = p 4 + q 3 – c 43 = -7+7=0 |
Находим наибольшую положительную оценку max
(
) = 3= D
14
Для найденной свободной клетки 14 строим цикл пересчета:
| 5 | | * | | 5- | | | | | | 5 |
| 50 | 5 | | | 50+ | 5- | | | 55 | | |
| | 39 | 41 | | | 39+ | 41- | | | 44 | 36 |
=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 | |||||||
| D 11 = 0, p1 + q1 - c11 = 0, q1 =2 D 14 = 0, p1 + q4 – c14 = 0, q4 = 4 D 34 = 0, p3 + q4 – c34 = 0, p3= -1 D 12 = 0, p1 + q2 – c12 = 0, q2 =3 D 22 = 0, p2 + q2 – c22 = 0, p2=-2 D 33 = 0, p3 + q3 – c33 = 0, q3= 4 D 44 = 0, p4 + q4 – c44 = 0, p4= -4 | Теперь по формуле D 13 = p1 + q3 – c13 = 4-6=-2 D 21 = p2 + q1 – c21 = -2+2-4 =-4 D 24 = p2 + q4 – c24 = -2+4-7=-5 D 31 = p3 + q1 – c31 = -1+2-5=-4 D 32 = p3 + q2 – c32 = -1+3-2=0 D 41 = p4 + q1 – c41 = -4+2=-2 D 42 = p4 + q2 – c42 = -4+3=-1 D 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 |
| f 1 ( x 1 ) | 0 | 5 | 8 | 10 | 12 | 13 | 14 | 15 |
| f 2 ( x 2 ) | 0 | 5 | 10 | 14 | 17 | 19 | 21 | 22 |
| f 3 ( x 3 ) | 0 | 8 | 13 | 18 | 21 | 23 | 25 | 27 |
| f 4 ( x4) | 0 | 6 | 13 | 20 | 27 | 33 | 38 | 41 |
Где,
–ом предприятии, если оно получит 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 | | 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 | | 300 | 400 | 500 | 600 | 700 |
| | 0 | 8 | 13 | 18 | 23 | 28 | 33 | 37 |
| x 3 | 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 млн. руб.,
х*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 рисками s
1
,
s
2
.
Постановка задачи:
Участник рынка имеет возможность приобретать Ц.Б. На рынке имеется три вида ценных бумаг: государственные безрисковые и два вида рисковых ценных бумаг.
Пусть xi – доля ценных бумаг i-го вида, которые имеет участник рынка (
-го вида приносит определённый доход Еi, который в общем случае случаен. Обозначим:
mi – математическое ожидание дохода от i-ой ценной бумаги,
ri
- среднее квадратичное отклонение дохода от i-ой ценной бумаги.
В общем случае, случайные доходы одного типа ценных бумаг зависят от дохода, получаемому по другому типу ценных бумаг.
Обозначим Vij – ковариация (корреляционный момент связи) между случайными величинами: доходом от ценной бумаги i-го и j-го видов.
Пакет ценных бумаг, находящихся у участников рынка, принято называть портфелем ценных бумаг. Поскольку, доход от каждого типа Ц.Б. является случайной величиной, то общий доход от общего портфеля в целом также является случайной величиной:
А общая дисперсия дохода составит:
Риск от реализации одной ценной бумаги отождествляется с «разбросом» дохода, т.е. со средним квадратичным отклонением.
Если
1) портфель минимального риска;
2) портфель максимального дохода;
Решение:
Доход одной денежной единицы на каждую из бумаг задан: mo
=2
m
1
=4
m
2
=9. Известны также риски рисковых бумаг: r
1
=8
r
2
=10.
Обозначим:
z – доли государственных ценных бумаг;
х – долю рисковых бумаг 1-ого вида;
у – долю рисковых бумаг 2-ого вида;
Тогда доход всего портфеля можно представить в следующем виде:
mp
= 2
z
+ 4
x
+ 9
y
денежных единиц, а дисперсию этого портфеля в виде:
Так как x
+
y
+
z
=1, то z
= 1 –
x
–
y
Подставим в mp
:
mp
=2(1 –
x
-
y
) + 4
x
+ 9
y
=2 + 2
x
+ 7
y
;
Найдем значения x
,
y
, при которых функция
Для этого составим функцию Лагранжа и найдём её частные производные.
L(x; y) = 64x2 + 100y2 + λ(2+2x + 7y - mp)
Приравняв производные к нулю, получим систему:
Решая полученную систему:
Δ
=
AC
-
B
2
= 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
=
Строим график зависимости ожидаемого дохода от риска:
|
6. Матричная игра как модель конкуренции
и сотрудничества
Теория игр: совокупность математических методов, анализа и оценки поведения в конфликтных ситуациях, когда сталкиваются интересы двух или более сторон, преследующие различные, иногда противоположные цели. Противоречащие друг другу интересы наблюдаются в области экономики, военном деле, спорте, иногда противоречат интересы различных ступеней иерархии в СУ. Теория игр представляет собой математическую теорию конфликтных ситуаций. Ее цель-выработка рекомендаций по разумному поведению участников конфликта.
Постановка задачи:
Рассмотрим матричную игру двух лиц с нулевой суммой.
Задана матрица:
Участвуют 2 игрока. 1-ый выбирает номер строки, а 2-ой независимо от 1-го выбирает номер столбца. Если 1-ый загадал 2-ую строку, а второй – 2-ой столбец, то выигрыш второго составляет 8 рублей.
Вначале проведем анализ на доминирование. Так как строки выбирает первый игрок, то мы исключаем из платежной матрицы доминируемые строки. Первая строка доминирует третью. В результате исключения третьей строки получаем:
Первый и четвертый столбец равнозначны. Исключаем четвертый, у нас получается платежная матрица, которую упростить уже невозможно:
Далее проведем анализ игры на седловую точку. Найдем минимумы по строкам
Нижняя цена игры будет равна:
Поскольку
Решение игры сводится к нахождению решения симметричной пары взаимно двойственных задач линейного программирования. Пусть
Проигрыш Второго игрока будет не больше, чем цена игры
Разделим каждое из неравенств на
Поскольку
1
,
x
2
,
x
3
,
x
4
удовлетворяют условию:
есть проигрыш второго игрока, который он стремится сделать минимальным. Следовательно, величина
Найти вектор
Решение:
Найдем ее оптимальное решение симплексным методом.
Итак,
Сначала приведем эту задачу к основной задаче линейного программирования:
Превратим неравенства в равенства, ля этого добавим к каждому неравенству дополнительные неотрицательные неизвестные x
5
,
x
6
,
x
7
. Вспомогательная задача будет иметь вид:
Откуда:
Составляем симплексную таблицу:
| Ć | Б | Н | X1 | X2 | X3 | X4 | X5 | X6 | X7 | Пояснения |
| 0 | X5 | 1 | 10 | 5 | 13 | 9 | 1 | 0 | 0 | max ( D j >0)= 31 min (α)=1/17, x 3 в базис, x 6 из базиса |
| 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 ( D j >0)= 24 min (α)= x 4 в базис, x 5 - из |
| -1 | X 3 | 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 | X 4 | 4/153 | -12/153 | 59/153 | 0 | 1 | | | 0 | max ( D j >0)= 933/153 min (α)=4/59, x 2 в базис, x 4 - из |
| -1 | X 3 | 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 ( D j >0)= 330/59 min (α)=8/330, x 1 в базис, x 7 - из |
| -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 | X 2 | 24/330 | 0 | 1 | 0 | 666/330 | |
| -1 | X 3 | 10/330 | 0 | 0 | 1 | 690/330 | |
| -1 | X 1 | 8/330 | 1 | 0 | 0 | -933/330 | |
| | | -42/330- K | 0 | 0 | 0 | -423/330 |
Цена игры равна
Найдем теперь оптимальную стратегию P
*
первого игрока. Выигрыш первого игрока будет не меньше, чем цена игры:
Разделим каждое из этих неравенств на
Поскольку
Но
Найти вектор
Эта задача является двойственной по отношению к рассмотренной выше задаче.
| Прямая задача: | Двойственная задача: |
| | |
Т.к. x
1
,
x
2
,
x
3
отличны от нуля:
Теперь возвращаемся к исходной матрице игры
| | 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 |
Найдем риск игры при использовании игроками своих оптимальных стратегий:
А также риск при использовании одним из игроков своей чистой, а другим – своей оптимальной стратегии (нижний индекс – Первого игрока, верхний – Второго):
Минимальное значение риска равно
1, а второй игрок использует оптимальную стратегию Q
*
. Однако,
играть с таким риском можно только с согласия обеих игроков, т.е. при их сотрудничестве друг с другом.
7. Анализ доходности и риска финансовых операций
Постановка задачи:
В реальной жизни мы имеем дело с финансовыми операциями. Финансовой называется операция, начальное и конечное состояния которой имеют денежную оценку и цель проведения которой заключается в максимизации дохода - разности между конечной и начальной оценками.
Почти всегда финансовые операции проводятся в условиях неопределенности и потому их результат невозможно предсказать заранее. Поэтому финансовые операции рискованны, т.е. при их проведении возможны как прибыль так и убыток (или не очень большая прибыль по сравнению с той, на что надеялись проводившие эту операцию).
Таким образом, любая финансовая операция должна быть оценена, по крайней мере, по двум показателям, а именно: доход – риск.
Предположим, что имеется несколько таких операций, каждая из которых характеризуется случайным доходом Q
.
Средний ожидаемый доход `Q - это математическое ожидание с.в. Q:
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 |
