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

Государственное образовательное  учреждение

высшего профессионального  образования

Государственный Университет Управления

 

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

 

 

 

Курсовая работа

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

 

 

 

 

 

 

 

 

Выполнил
Институт	Мировой и Национальной Экономики
Специальность	Менеджмент организации
Специализация	Предпринимательство
Отделение	д/о
Курс	II
Группа
Руководитель	Курочкин А.П.
Дата сдачи  на проверку
Дата защиты
Оценка
Подпись руководителя

 

 

 

 

 

 

Москва 2002

 

Оглавление
	Стр.
1. Линейная производственная задача…………………………………..	3-6
2. Двойственная задача…………………………………………………...	7-8
3. Задача о «расшивке  узких мест производства»……………………...	9-10
4. Транспортная задача линейного  программирования………………..	11-13
5. Динамическое программирование. Распределение капитальных вложений…………………………………………………………………...	14-16
6. Матричная игра как модель  конкуренции и сотрудничества……….	17-18
7. Анализ доходности и риска  финансовых операций…………………	19-20
8. Задача формирования оптимального  портфеля ценных бумаг……..	21
Использованная литература……………………………………………...	22

 

 

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

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

Технологическая матрица A, в которой  каждый элемент a_ij означает необходимое количество i-го ресурса для выпуска j-го вида продукции:

Вектор B объемов ресурсов, каждый элемент которого b_i означает предельное количество i-го ресурса для выпуска всего объема продукции:

Вектор удельной прибыли C, элементы которого c_j означают прибыль от производства единицы продукции j-го вида:

Количество каждого из товаров  задаётся с помощью производственной программы:

, где

x1, x2, x3, x4  - кол-во 1-ой, 2-ой, 3-ей и  4-ой продукции соответственно.

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

Каждый элемент полученного  вектора равен расходу соответствующего ресурса при заданной производственной программе, т.е. при x1, x2, x3, x4 . Так как  матрица А указывает на необходимое  количество определённого ресурса  для производства 1 единицы продукции, то умножая это число на общее  количество продукции данного вида мы получим расход данного ресурса  для производства заданного количества определённого вида продукции. Сложив расход ресурса по всем видам продукции, мы получим общий расход ресурса.

Вектор В указывает на располагаемое  количество ресурсов. Каждый элемент  соответствует одному виду ресурса. Таким образом, при производстве при заданной производственной программе X и объеме располагаемых ресурсов B должны выполняться неравенства  для каждого ресурса:

_{5x1 + 4x2 + 6x3 + 7x4 # 275;  2x1 + 4x3 + 2x4 # 100;   3x1 + 2x2 + x4 # 85}

Вектор С указывает на прибыль  от продажи 1 единицы продукции каждого  вида. Каждый элемент вектора соответствует  одному виду продукции. Чтобы найти  прибыль от каждого вида продукции  следует помножить вектор производственной программу X на вектор удельной прибыли  С:

Сложив элементы полученного вектора  мы получим совокупную прибыль от продажи всей продукции при заданном векторе производственной программы X. Так как x₁, x₂, x₃, x₄ – неизвестные запишем полученное выражение в виде функции:

_{Z = 50x1 + 27x2 + 34x3 + 54x4}

Для достижения максимальной прибыли  требуется найти максимум полученной функции Z. При этом x₁, x₂, x₃, x₄ по смыслу ³ 0. Учитывая условия ограничения по ресурсам, получим задачу на условный экстремум:

_{Z = 50x1 + 27x2 + 34x3 + 54x4 Y max}

_{x1$ 0, x2 $ 0, x3 $ 0, x4 $ 0}   

Для ее решения систему неравенств при помощи дополнительных неизвестных  х₅, х₆, х₇ заменим системой линейных алгебраических уравнений

_{Z = 50x1 + 27x2 + 34x3 + 54x4 Y max}

_{x1$ 0, x2 $ 0, x3 $ 0, x4 $ 0}   

 

где дополнительные переменные имеют смысл остатков соответствующих  ресурсов, а именно

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

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

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

Решаем полученную задачу симплексным  методом (методом направленного  перебора базисных допустимых решений):

			50	27	34	54	0	0	0
C	Базис	Hi	х1	х2	х3	х4	х5	х6	х7	α
0	Х5	275	5	4	6	7	1	0	0	39,3
0	Х6	100	2	0	4	2	0	1	0	50
0	Х7	85	3	2	0	1	0	0	1	85
	Z – Z0	0	-50	-27	-34	-54	0	0	0
54	X4	275/7	5/7	4/7	6/7	1	1/7	0	0	55
0	Х6	150/7	4/7	-8/7	16/7	0	-2/7	1	0	37,5
0	Х7	320/7	16/7	10/7	-6/7	0	-1/7	0	1	20
	Z – Z0	14850/7	-80/7	27/7	86/7	0	54/7	0	0
54	Х4	25	0	1/8	9/8	1	3/16	0	-5/16
0	Х6	10	0	-3/2	5/2	0	-1/4	1	-1/4
50	Х1	20	1	5/8	-3/8	0	-1/16	0	7/16
	Z – Z0	2350	0	11	8	0	7	0	5

Как видно из последней симплексной  таблицы, оптимальная производственная программа имеет вид

х₁ = 20, х₂ = 0, х₃ = 0, х₄ = 25,

а максимальная прибыль равна

Z_max = 2350

При этом 1-й и 3-й ресурсы будут  исчерпаны полностью (х₅=0, х₇=0), а 2-й ресурс будет иметь остаток х₆ = 10 единиц.

При выполнении производственной программы 2-й и 3-ий ресурсы используются полностью, то есть образуют  “узкие места производства”.

Проверим получившийся результат.

Воспользуемся тем, что в оптимальной  производственной программе x₂ = 0 и    x₃ = 0. Предположим, что вторую и третью продукции мы не намеревались выпускать с самого начала. Рассмотрим задачу с оставшимися двумя переменными. Математическая модель будет выглядеть следующим образом:

_{Z = 50x1 + 54x4 ® max}

            x₁ ³ 0, x₄ ³ 0

Графическое решение этой задачи представлено на Рис. 1.

Из графика видно, что результаты совпадают.

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

Для того, чтобы убедиться в правильности полученного решения, следует проверить  отношение Н = Q^-1 * В:

 

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

Некое предприятие, использующее те же ресурсы что и предприятие  из предыдущей задачи, желает приобрести все эти ресурсы. Оно желает приобрести их по ценам y₁, y₂ и y₃ соответственно за единицу каждого из трёх ресурсов. Из условий предыдущей задачи нам известны затраты всех 3-х ресурсов для производства для каждого из 4-х видов продукции, количество ресурсов на производстве и прибыль от единицы каждой продукции:

    

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

Для производства продукции 1-ого вида требуется 5 единиц 1-ого ресурса, 2 единицы 2-ого ресурса и 3 единицы 3-его  ресурса, что соответствует элементам 1-ого столбца матрица А. Прибыль  от продажи продукции 1-ого вида равна 50. Следовательно, для целесообразности продажи ресурсов прибыль от продажи 5 единиц 1-ого ресурса, 2-х единиц 2-ого ресурса и 3-х единиц 3-его  ресурса должна быть больше, либо равна 50, т.е. прибыли от продажи продукции 1-ого вида:

Соответственные условия должны выполняться  и для продукции других видов. Им соответствуют 2-ой, 3-ий и 4-ый столбцы  матрицы А, а также 2-ой, 3-ий и 4-ый элементы матрицы-строки прибыли С:

Но при продаже требуется  учитывать и интересы покупателя. Естественным желанием покупателя является снижение расходов. Так как предприятие  желает закупить весь объём имеющихся  ресурсов, то его затраты при ценах  y₁, y₂ и y₃ составят , где коэффициенты при y₁, y₂ и y₃ - количество имеющихся ресурсов. Таким образом:

Y min

 

Кроме того, так  как цены не могут быть отрицательными, то .

Решение полученной задачи легко найти  с помощью второй основной теоремы  двойственности, согласно которой для  оптимальных решений х(х₁,х₂,х₃) и у(у₁,у₂,у₃) пары двойственных задач необходимо и достаточно выполнение условий:

и

Ранее (см. Задачу 1) было найдено, что  в решении исходной  задачи х₁>0 и х₄>0. Поэтому

Учитывая, что 2-ой ресурс был избыточным, то, согласно теореме двойственности, его двойственная оценка , получим систему:

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

у₁ = 7,

у₃ = 5.

Таким образом, получили двойственные оценки ресурсов:

у₁ = 7, у₂ = 0, у₃ = 5,

причем общая оценка всех ресурсов равна

f_min = 2350

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

Данные значения y₁, y₂ и y₃ являются двойственными оценками соответствующих ресурсов, т.е. оценка единицы 1-ого ресурса равна 7, оценка единицы 2-ого ресурса равна 0, а оценка 3-его ресурса равна 5. Эти оценки являются «теневыми» ценами ресурсов. Экономически они указывают, на сколько увеличится прибыль при выполнении оптимальной производственной программы, если количество соответствующего ресурса увеличить на единицу, при неизменном количестве остальных ресурсов.

Используя задачу 1, мы можем найти оценку технологии, т.е. на сколько уменьшится прибыль, если будет произведена 1 единица  продукции не по оптимальной программе. Оценки технологий получились в конечной симплексной таблице как коэффициенты при соответствующих x в целевой функции. Таким образом, при производстве единицы 2-ой продукции прибыль упадёт на 11, а для 3-ей продукции падение составит 8.

 

3. Задача о «расшивке  узких мест производства»

При выполнении оптимальной  производственной программ второй и  третий  ресурсы используются полностью, то есть образуют “узкие места производства”. Будем заказывать их дополнительно. T = (t₁, t₂, t₃) – вектор дополнительных объёмов ресурсов.

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

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

H + Q^-1T ³ 0

Задача состоит в том, чтобы найти вектор Т(t₁;0;t₂), максимизирующий суммарный прирост прибыли W = 7t₁ + 5t₃ при условии сохранения двойственных оценок ресурсов (и, следовательно, структуры производственной программы).

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

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

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

 

причём по смыслу задачи t₂  ³ 0, t₃ ³ 0. Перепишем неравенства в другом виде. Получим:

W = 7t₁ + 5t₃ Y max

   t₁ # 275/3, t₃ # 85/3    t₁ # 275/3, t₃ # 85/3

По графику видно, что  решение данной задачи находится  в точке А(11,3;28,3). Таким образом, программа «Расшивки узких мест производства» имеет вид: t₁=11,3, t₂=0, t₃=28,3 и прирост прибыли составит W = 7*11,3 + 5*28,3 = 220,6

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

Cj	50	27	34	54	Bi	X4+i	Yi	Ti
	5	4	6	7	275	0	7	11,3
aij	2	0	4	2	100	10	0	0
	3	2	0	1	85	0	5	28,3
Xj	20	0	0	25	2350			220,6
Dj	0	11	8	0

 

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

Имеется 3 производителя  однородной продукции, имеющие запасы этой продукции 70, 50 и 54 единицы соответственно. Также имеется 4 потребителя данной продукции. Их потребность составляет 50, 27, 34 и 54 единицы соответственно. Транспортная компания заключила контракт с поставщиками и потребителями на вывоз и  поставку данной продукции от производителей к потребителям. При перевозке  продукции от каждого производителя  к каждому потребителю транспортная компания имеет определённые издержки на единицу продукции: 5 у.е. при перевозке  от 1-ого производителя к 1-ому  потребителю, 4 у.е. - от 1–ого производителя  ко 2-ому потребителю, 6 у.е. – от 1-ого  к 3-ему, 7 у.е. – от 1-ого к 4-ому, 7 у.е. – от 2-ого к 1-ому, 3 у.е. – от 2-ого  ко 2-ому, 4 у.е. – от 2-ого к 3-ему, 2 у.е. – от 2-ого к 4-ому, 3 у.е. – от 3-его  к 1-ому, 2 у.е. – от 3-его ко 2-ому, 5 у.е. – от 3-его к 3-ему, 1 у.е. – от 3-его  к 4-ому. Так как естественным стремлением  транспортной компании является максимизация прибыли, то требуется составить  такой план перевозок, чтобы издержки были минимальными.

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

Предложение производителей и спрос потребителей можно записать в виде векторов А и B соответственно:

 и 

Требуется найти  план перевозок

X = (x_ij), i = 1,m; j = 1,n,

минимизирующий  общую стоимость всех перевозок

L = 33c_ijx_ij

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

3x_ij = a_i, i = 1,m

И любому потребителю доставляется необходимое  количество груза

3x_ij = b_j, j = 1,n

Причём  по смыслу задачи

x₁₁ > 0,…, x_mn > 0

В нашей задаче 4 потребителя и 3 поставщика, причём суммарный объем производства Sa_i = 70 + 50 + 54 = 174 больше, чем требуется всем потребителям            Sb_i = 50 + 27 + 34 + 54 = 165. Суммарное предложение не больше суммарного спроса. Для того, чтобы они были равны введём фиктивного потребителя с потреблением равным разнице между предложением и спросом.. Фактически эта потребность будет указывать на количество продукции, которая не будет вывозиться от производителя. Для того, чтобы введение фиктивного потребителя не повлияло на решение, затраты на перевозку единицы продукции к фиктивному потребителю приравняем к 0. В действительности это будет также, так как транспортная компания не будет нести издержки за товар, который она никуда не возит. Тогда вектор В и матрица С будут выглядеть так:

 и 

50 + 27 + 34 + 54 + 9 = 70 + 50 + 54

ПН ПО	50		27		34		54		9		αi
70	5	5	4	4	5	6	3	7	2	0	α1 = 0
	50		20
	0		0		-1		-4		2
50	4	7	3	3	4	4	2	2	1	0	α2 = -1
			7		34		9
	-3		0		0		0		1
54	3	3	2	2	3	5	1	1	0	0	α3 = -2
							45		9
	0		0		-2		0		0
βj	β1 = 5		β2 = 4		β3 = 5		β4 = 3		β5 = 2

Z_опор = 250 + 80 + 21 + 136 + 18 + 45 = 550

Для заполненных  клеток α _i + β _j = C_ij, для них D_ij = 0

Для незаполненных  клеток  D_ij= α _i + β _j - c_ij

Так как не все характеристики отрицательны (например, D₁₅ = 2), то для найденной свободной клетки строим цикл пересчёта. Производим перераспределение поставок вдоль цикла пересчета:

ПН ПО	50		27		34		54		9		αi
70	5	5	4	4	5	6	3	7	0	0	α1 = 0
	50		11						9
	0		0		-1		-4		0
50	4	7	3	3	4	4	2	2	-1	0	α2 = -1
			16		34		0
	-3		0		0		0		-1
54	3	3	2	2	3	5	1	1	0	0	α3 = -2
							54
	0		0		-2		0		0
βi	β1 = 5		β2 = 4		β3 = 5		β4 = 3		β5 = 0

Решение оптимально, так как все D # 0.

Ответ: При этом 9 единиц продукции остаются у 1-ого производителя.

Z_опт = 250 + 44 + 48 + 136 + 54 = 532

DZ = Z_опор – Z_опт = 550 – 532 = 18

 

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

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

Рассмотрим нелинейную задачу распределения  ресурсов между предприятиями отрасли. Предположим, что указано n пунктов, где требуется построить или реконструировать предприятия одной отрасли, для чего выделено b рублей. Обозначим через f_j(x_j) прирост мощности  или прибыли на  j-том предприятии, если оно получит x_j рублей капвложений. Требуется найти такое распределение (х₁, х₂, ..., х_n) капвложений между предприятиями, которое максимизирует суммарный прирост мощности или прибыли

Z=f₁(x₁)+f₂(x₂)+...+f_n(x_n)

при ограничении по общей сумме капвложений х₁ + х₂ +...+х_n = b, причём будем считать, что все переменные x_j принимают только целые значения x_j =1,2,...

Функции f_j(x_j) мы считаем заданными, заметив, что их определение -довольно трудоёмкая экономическая задача.

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

Введём параметр состояния и  определим функцию состояния. За параметр состояния x  примем количество рублей, выделяемых нескольким предприятиям, а функцию состояния F_k(x) определим как максимальную прибыль на первых  k  предприятиях, если они вместе получат x рублей. Параметр x может меняться от 0 до b. Если из x рублей k-ое предприятие получит Х_к  рублей, то каково бы ни было это значение, остальные x-Х_к  рублей естественно распределить между предприятиями от 10-го до (к-1)-го предприятия, чтобы была получен максимальная прибыль F_k-1(x-x_k). Тогда прибыль k предприятий будет равна f_k(x_k) + F_k-1(x-x_k). Надо выбрать такое значение x_k между 0 и x, чтобы эта сумма была максимальной, и мы приходим к рекуррентному соотношению:

F_k(x) = max {f_k(x_k) + F_k-1(x-x_k)}

         0 £ X £ x

для k=2,3,....,n .Если же k=1 ,то

F₁(x)=f₁(x).

В нашем случае производственное объединение  состоит из 4-х предприятий (k=4).Общая сумма капвложений равна 700 тыс. рублей (b=700) , выделяемые предприятиям суммы кратны 100 тыс. рублей.

Значения функций f_j(x_j) приведены в таблице 1.

Таблица 1

xj	0	100	200	300	400	500	600	700
f1(xj)	0	15	26	37	46	53	59	63
f2(xj)	0	15	24	30	36	40	43	45
f3(xj)	0	9	30	33	31	39	45	49
f4(xj)	0	24	36	42	46	48	49	49

 

Прежде всего заполняем таблице2. Значения f₂(x₂) складываем со значениями F₁(x-x₂)=f₁(x-x₂) и на каждой побочной диагонали находим наибольшее число, которое помечаем звёздочкой. Продолжая процесс табулируем функции F₃(x), x₃(x) и т.д. В таблице 6 заполняем только одну диагональ для значения x=700.

Таблица 2

x-х2		0	100	200	300	400	500	600	700
X2	F(x-x2) f2(x2)	0	15	26	37	46	53	59	63
0	0	0	15*	26	37	46	53	59	63
100	15	15*	30*	41*	52*	61*	68	74	---
200	24	24	39	50	61*	70*	77*	---	---
300	30	30	45	56	67	76	---	---	---
400	36	36	51	62	73	---	---	---	---
500	40	40	55	66	---	---	---	---	---
600	43	43	58	---	---	---	---	---	---
700	45	45	---	---	---	---	---	---	---