Прикладная математика 2 - курсовая работа

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

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

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

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

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

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

Выполнила:

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

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

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

Курс: 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^-1 B

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

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

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

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 -го вида питания; b_i – запас i -ого ресурса; с _j – прибыль на единицу j -го вида питания; x_j – количество выпускаемого питания j - ого вида.

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

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

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

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

(1)

Требуется найти производственную программу X ^* = ( x ₁ , x ₂ , x ₃ , x ₄ ), реализация которой обеспечит компании получение наибольшей прибыли:

,

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

Решение:

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

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

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

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

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

В качестве базисных неизвестных могут быть приняты неизвестные х₅ , х₆ , х₇ , так как каждый из них входит только в одно уравнение системы и не входит в другие уравнения. Приравняв к нулю свободные переменные х₁ , х₂ , х₃ , х₄ , получаем базисное неотрицательное решение:

х₁ =0, х₂ =0, х₃ =0, х₄ =0, х₅ =148, х₆ =116, х₇ =90

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

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

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

0 – Z = -30 x₁ -25x₂ -14x₃ -12x₄

x ₁ =20, x ₂ =36, x ₃ =0, x ₄ =0, x ₅ =0, x ₆ =0, x ₇ =18 определяют производственную программуx ₁ =20, x ₂ =36, x ₃ =0, x ₄ =0

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

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

2-ого вида x ₆ =0

3-ого вида x ₇ =18

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

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

; ; ;

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

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

; ;

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

- ?

Z = 30 x ₁ + 25 x ₂ → max

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

Задание:

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

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

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

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

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

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

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

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

2 3 0 4 148

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

0 2 4 3 90

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

2у₁ + 4у₂ ³ 30

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

3у₁ + 1у₂ + 2у₃ ³ 25 и т.д.

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

148у₁ + 116у₂ + 90у₃ рублей

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

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

_, (1)

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

(2)

Решение:

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

Согласно второй основной теореме двойственности для оптимальных решений X ^* =(х₁ , х₂ , х₃ , х₄ ) и Y ^* =(y₁ , y₂ , y₃ ) пары двойственных задач необходимо и достаточно выполнение условий:

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

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

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

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

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

(3)

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

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

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

Продолжаем рассмотрение задачи планирования производства. При выполнении оптимальной производственной программы первый и второй ресурсы используются полностью, т.е. образуют «узкие места производства» x ₅ =0, x ₆ =0. Будем «расшивать узкие места производства» т.е. заказывать дополнительно дефицитные ресурсы. Обозначим через t ₁ иt ₂ искомое дополнительное количество единиц первого и второго вида ресурсов. T(t₁ , t₂ , 0) - вектор дополнительных объемов ресурсов. Согласно третьей основной теореме двойственности, увеличение первого вида ресурса на единицу обеспечивает прирост прибыли, равный двойственной оценке y ₁ =7 , второго вида – y ₂ =4.

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

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

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

, (2)

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

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

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

(3)

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

(4)

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

(5)

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

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

Решение:

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

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

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

При этом прирост прибыли составит: W = 7t₁ + 4t₂ =447 ½ .

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

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

Задание:

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

; ;

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

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

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

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

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

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

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

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

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

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

;

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

(1)

Решение:

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

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

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

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

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

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

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

D ₁₁ = 0, p ₁ + q ₁ - c ₁₁ = 0, q ₁ = 2

D ₁₄ = 0, p ₁ + q ₄ - c ₁₄ = 0, q ₄ = 4

D ₃₄ = 0, p₃ + q₄ – c₃₄ = 0, p₃ = -1

D ₃₃ = 0, p₃ + q₃ – c₃₃ = 0, q₃ = 4

D ₂₁ = 0, p₂ + q₁ – c₂₁ = 0, p₂ = 2

D ₂₂ = 0, p ₂ + q ₂ – c ₂₂ = 0, q ₂ = -1

D ₄₄ = 0, p ₄ + q ₄ – c ₄₄ = 0, p ₄ =-4

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

D ₁₂ = p₁ + q₂ – c₁₂ = 0-1-3=-4

D ₁₃ = p₁ + q₃ – c₁₃ = 0+4-6 =-2

D ₂₃ = p₂ + q₃ – c₂₃ = 2+4-5 = 1 - max

D ₂₄ = p₂ + q₄ – c₂₄ = 2+4-7 = -1

D ₃₁ = p₃ + q₁ - c₃₁ = -1+2-5 = -4

D ₃₂ = p₃ + q₂ – c₃₂ = -1-1-2 = -4

D ₄₁ = p₄ + q₁ – c₄₁ = -4+2-0 = -2

D ₄₂ = p₄ + q₂ – c₄₂ = -4-1-0 = -5

D ₄₃ = p ₄ + q ₃ – c ₄₃ = -4-4-0 = -8

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

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

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

min =0

D ₁₄ = 0, p₁ + q ₄ - c_{1 4} = 0, q ₄ = 4

D ₃₄ = 0, p₃ + q₄ – c₃₄ = 0, p₃ = -1

D ₃₃ = 0, p₃ + q₃ – c₃₃ = 0, q₃ = 4

D _{2 3} = 0, p₂ + q ₃ – c_{2 3} = 0, p₂ = 1

D ₂₂ = 0, p₂ + q₂ – c₂₂ = 0, q₂ = 0

D ₄₄ = 0, p₄ + q₄ – c₄₄ = 0, p₄ =-4

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

D ₁₂ = p₁ + q₂ – c₁₂ = 0-3=-3

D ₁₃ = p₁ + q₃ – c₁₃ = 0+4-6 =-2

D ₂₁ = p₂ + q₃ – c₂₃ = 1+2-4 = -1

D ₂₄ = p₂ + q₄ – c₂₄ = 1+4-7=-2

D ₃₁ = p₃ + q₁ - c₃₁ = -1+2-5 = -4

D ₃₂ = p₃ + q₂ – c₃₂ = -1+0-2=-3

D ₄₁ = p₄ + q₁ – c₄₁ = -4+2=-2

D ₄₂ = p₄ + q₂ – c₄₂ = -4+0=-4

D ₄₃ = p ₄ + q ₃ – c ₄₃ = -4+4-0 = 0

Итак, , при

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

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

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

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

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

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

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

min =3

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

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

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

min =30

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

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

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

min =5

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

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

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

Задание:

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

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

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

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

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

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

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

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

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

.

Решение:

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

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

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

Табл. 2.