• Задать вопрос менеджеру

Twitter новости

Обучение письменному иноязычному общению на основе ИКТ http://t.co/IK2NAjncrk

Online-опрос

Антиплагиат онлайнДипломант
Яндекс.Метрика

Решение задачи линейного программирования о расшивке узких мест производства

Предмет:Математика
Тип:Курсовая
Объем, листов:27
Word
Получить полную версию работы
Релевантные слова:вида, продукции, ресурса, ресурсов, производственной, задачи, каждого, расход, задача, имеющихся, линейной, запас, модель, количество, вектор
Процент оригинальности:
87 %
Цена:300 руб.
Содержание:

1. ЛИНЕЙНАЯ ПРОИЗВОДСТВЕННАЯ ЗАДАЧА 3

1. 1. Формулировка линейной производственной задачи 3

1. 2. Математическая модель линейной производственной задачи 4

1. 3. Решение линейной производственной задачи симплексным методом 6

1. 4. Проверка полученного решения 8

1. 5. Графическое решение линейной производственной задачи с двумя переменными 9

2. ДВОЙСТВЕННАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ, ЗАДАЧА О «РАСШИВКЕ УЗКИХ МЕСТ ПРОИЗВОДСТВА» 11

2. 1. Двойственная задача линейного программирования 11

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

3. ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 17

3. 1. Математическая модель транспортной задачи 17

3. 2. Решение транспортной задачи методом потенциалов 18

4. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ ЗАДАЧА РАСПРЕДЕЛЕНИЯ КАПИТАЛЬНЫХ ВЛОЖЕНИЙ 21

4. 1. Формулировка задачи распределения капитальных вложений 21

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

5. АНАЛИЗ ДОХОДНОСТИ И РИСКА ФИНАНСОВЫХ ОПЕРАЦИЙ 25

Список использованной литературы 28

Вступление:

Задание

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

Вектор удельной прибыли

Нормы затрат различных ресурсов на производство единицы каждого вида продукции38122821

Вектор

объемов

ресурсов

3033186

2311102

4322196

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

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

H = Q-1B

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

1. 1. Формулировка линейной производственной задачи

Сформулируем линейную производственную задачу.

Предприятие может выпускать четыре вида продукции, используя для этого три вида ресурсов.

Известны:

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

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

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

Требуется:

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

Заключение:

Задание

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

xj0100200300400500600700

f1(x1)0376487105120134145

f2(x2)0487598120132144156

f3(x3)085100111118124129132

f4(x4)047708086919498

4. 1. Формулировка задачи распределения капитальных вложений

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

Пусть 4 фирмы образуют объединение. Рассмотрим задачу распределения инвестиций в размере 700 тыс. рублей по этим 4 фирмам. Размер инвестиций пусть будет кратен 100 тыс. рублей. Эффект от направления i-й фирме инвестиций в размере хj (тыс. рублей) (прирост прибыли на данном предприятии) выражается функцией fi(xi), i = 1, 2, 3, 4. Функции fi(xi) заданы в исходных данных задачи, где, например, число 37 означает, что прирост прибыли на 1-ом предприятии при инвестировании в него 100 тыс. рублей составит 37 тыс. рублей. На практике определение данных функции – довольно трудоемкая экономическая задача.

Приходим к задаче:

Требуется найти такое распределение (х1, х2, х3, х4) капитальных вложений между четырьмя предприятиями, которое максимизирует суммарный прирост мощности или прибыли:

Z = f1(x1) + f2(x2) + f3(x3) + f4(x4) ? max

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

х1 + х2 + х3 + х4 = 700

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

х1, х2, х3, х4 = 0, или 100 000, или 200 000, или 300 000, или 400 000, или 500 000, или 600 000, или 700 000

где xi – пока еще неизвестный размер инвестиций i-й фирме.

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

Динамическое программирование - это вычислительный метод для решения задач управления определённой структуры, когда задача с n переменными представляется как многошаговый процесс принятия решений. На каждом шаге (этапе) определяется экстремум функции только от одной переменной. Состояние исследуемой системы на каждом шаге характеризуется некоторой переменной величиной, которая называется параметром состояния. Эффект от принятия параметром состояния того или иного значения на данном этапе вместе с уже рассмотренными шагами характеризуется функцией состояния. Решение конкретной задачи методом динамического программирования сводится к выбору параметра состояния, составления функции состояния и рекуррентных соотношений, связывающих функции состояния для двух соседних последовательных этапов, и их применению для выбора оптимального управления.

Воспользуемся методом динамического программирования для решения полученной задачи распределения капитальных вложений. Последовательно ищется оптимальное распределение для k = 2, 3 и 4 фирм.

Пусть первым двум фирмам выделено ? тыс. рублей инвестиции (? - параметр состояния, который может изменяться от 0 до 700). Обозначим через F2 (?) максимальный прирост прибыли на первых двух предприятиях.

Если из ? тыс. рублей 2-ая фирма получит х2 тыс. рублей, то максимальный прирост прибыли на 2-ой фирме можно выразить как f2(x2).

На долю 1-ого предприятия останется ? - х2 тыс. рублей, а максимальный прирост прибыли на 1-ом предприятии составит F1 (? - х2).

Тогда максимальный прирост прибыли на двух предприятиях будет равен

F2 (?) = max {f2(x2) + F1 (? - х2)}

0 ? x2 ? 700

Используя исходные данные из задания, строим Таблицу № 1. 1. Значения f2(x2) складываем со значениями F1 (?-x2) = f1(?-x2) и на каждой побочной диагонали находим наибольшее число, которое помечаем звёздочкой.

Таблица № 1. 1

?-х2

0100200300400500600700

X2F1(?-x2)

f2(x2)0376487105120134145

000

376487105120134145

1004848*85*112*135153168182---

2007575

112*139*162*180195------

3009898

135162*185203---------

400120120157184207*------------

500132132169196---------------

600144144181------------------

700156156---------------------

Звездочкой обозначен максимальный суммарный эффект от выделения соответствующего размера инвестиций 2-м предприятиям.

В Таблицу № 1. 2. в графу F2 (?) заносим значения максимального прироста прибыли на первых двух предприятиях, а в графе указываем соответствующий каждому значению F2(?) размер инвестиций 2-ому предприятию.

Таблица № 1. 2.

?0100200300400500600700

F2(?)04885112139162185207

(?)

0100100200200300300400

100200

Далее действуем также: находим функции F3 (?), F4 (?), используя на каждом k-ом шаге основное рекуррентное соотношение:

Fk (?)=max {fk(xk) + Fk-1(? - xk)}

0 ? xk ? 700

для k = 2,3,4

Заполняем Таблицу № 2. 1. , аналогичным способом определяя максимальный прирост прибыли от распределения капитальных вложений между тремя предприятиями (F3 (?)).

Таблица № 2. 1.

?-х3

0100200300400500600700

Х3F2(?-x3)

f3(x3)04885112139162185207

000

4885112139162185207

1008585*133*170*197*224*247*270*---

200100100148185212239262------

300111111159196223250---------

400118118166203230------------

500124124172209---------------

600129129177------------------

700132132

---------------------

Звездочкой обозначен максимальный суммарный эффект от выделения соответствующего размера инвестиций 3-м предприятиям.

В Таблицу № 2. 2. в графу F3 (?) заносим значения максимального прироста прибыли на трех предприятиях, а в графе указываем соответствующий функции F3(?) размер инвестиций 3-ему предприятию.

Таблица № 2. 2.

?0100200300400500600700

F3(?)085133170197224247270

(?)

0100100100100100100100

В Таблице № 3. 1. , определяющей максимальный прирост прибыли от распределения капитальных вложений между четырьмя предприятиями F4(?), заполняем только одну диагональ для значения ? = 700, поскольку данный этап является завершающим, предприятий всего четыре и между ними необходимо распределить именно 700 тыс. рублей.

Таблица № 3. 1.

?-х4

0100200300400500600700

Х4F(?-x4)

f2(x4)085133170197224247270

00270

10047294*---

20070294*------

30080277---------

40086256------------

50091224---------------

60094179------------------

7009898---------------------

Звездочкой обозначен максимальный суммарный эффект от выделения соответствующего размера инвестиций в размере 700 тыс. рублей 4-м предприятиям.

Z max = 294 тыс. рублей,

причем 4-ому предприятию должно быть выделено

х4* = х4 (700) = 200 тыс. рублей

ЛИБО

х4** = х4 (700) = 100 тыс. рублей.

На долю остальных трех предприятий остается в 1-ом случае (х4* = 200) 500 тыс. рублей,

во 2-ом случае (х4** = 100) 600 тыс. рублей.

Из Таблицы № 2. 2. видно, что 3-ему предприятию должно быть выделено

в 1-ом случае (х4* = 200): х3* = х3 (700 – х4*) = х3 (500) = 100 тыс. рублей

во 2-ом случае (х4** = 100): х3** = х3 (700 – х4**) = х3 (600) = 100 тыс. рублей.

Таким образом, х3* = 100 тыс. рублей.

Продолжая обратный процесс, находим:

в 1-ом случае (х4* = 200): х2* = х2 (700 – х4* - х3*) = х2 (400) = 200 тыс. рублей

во 2-ом случае (х4** = 100): х2** = х2 (700 – х4** - х3*) = х2 (500) = 300 тыс. рублей

ЛИБО

х2*** = х2 (500) = 200 тыс. рублей = х2*.

На долю 1-ого предприятия останется:

х1* = 700 – х4* - х3* - х2* = 200 тыс. рублей

х1** = 700 – х4** - х3** - х2*** = 300 тыс. рублей

х1*** = 700 – х4** - х3** - х2** = 200 тыс. рублей = х1*

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

1-ый вариант

х1* = 200;Z max = 294

х2* = 200;

х3* = 100;

х4* = 200

2-ой вариант

х1* = 200;Z max = 294

х2** = 300;

х3* = 100;

х4** = 100

3-ий вариант

х1** = 300;Z max = 294

х2* = 200;

х3* = 100;

х4** = 100

В качестве проверки правильности решения задачи можно использовать равенство:

Z max = f1(x1) + f2(x2) + f3(x3) + f4(x4)

1-ый вариант: 64 + 75 + 85 + 70 = 294 тыс. рублей

2-ой вариант: 64 + 98 + 85 + 47 = 294 тыс. рублей

3-ий вариант: 87 + 75 + 85 + 47 = 294 тыс. рублей

Следовательно, полученные решения верны.

5. АНАЛИЗ ДОХОДНОСТИ И РИСКА ФИНАНСОВЫХ ОПЕРАЦИЙ

Задание

Провести анализ доходности и риска финансовых операций по следующим исходным данным:

Q1:26812

1/51/51/52/5

Q2:01514

1/52/51/51/5

Q3:24618

1/52/51/51/5

Q4:081620

1/21/81/81/4

Рассмотрим финансовые операции в качестве случайных величин

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

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

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

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

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

,

где pi есть вероятность получить доход qi.

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

r = ,

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

Найдем ожидаемые эффективности и риски каждой из 4-х финансовых операций

Рассмотрим четыре финансовых операции , ряды распределения которых указаны в «Задании». Найдем средние ожидаемые доходы и риски каждой из четырех операций:

1). = M [Q1] = ? qj pj = 2*1/5 + 6*1/5 + 8*1/5 + 12*2/5 = 8

j

M [Q1?] = ? qj? pj = 4*1/5 + 36*1/5 + 64*1/5 + 144*2/5 = 392/5 = 78. 4

j

? = 64

D [Q1] = 78. 4 – 64 = 14. 4

r1 = ? 3. 8

Таким образом, = 8,

r1 ? 3. 8

2). = M [Q2] = ? qj pj = 0*1/5 + 1*2/5 + 5*1/5 + 14*1/5 = 21/5 = 4. 2

j

M [Q2?] = ? qj? pj = 0*1/5 + 1*2/5 + 25*1/5 + 196*1/5 = 223/5 = 44. 6

j

? = 17. 64

D [Q2] = 44. 6 – 17. 64 = 26. 96

r2 = ? 5. 2

Таким образом, = 4. 2,

r2 ? 5. 2

3). = M [Q3] = ? qj pj = 2*1/5 + 4*2/5 + 6*1/5 + 18*1/5 = 34/5 = 6. 8

j

M [Q3?] = ? qj? pj = 4*1/5 + 16*2/5 + 36*1/5 + 324*1/5 = 396/5 = 79. 2

j

? = 46. 24

D [Q3] = 79. 2 – 46. 24 = 32. 96

r3 = ? 5. 7

Таким образом, = 6. 8,

r3 ? 5. 7

4) = M [Q4] = ? qj pj = 0*1/2 + 8*1/8 + 16*1/8 + 20*1/4 = 8

j

M [Q4?] = ? qj? pj = 0*1/2 + 64*1/8 + 256*1/8 + 400*1/4 = 8 + 32 + 100 = 140

j

? = 64

D [Q4] = 140 – 64 = 76

r4 = ? 8. 7

Таким образом, = 8,

r4 ? 8. 7

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

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

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

Операция Qi доминирует операцию Qj, если:

М [Qi] ? M [Qj] М [Qi] > M [Qj]

ИЛИ

ri < rj ri ? rj

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

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

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

Например, пусть взвешивающая формула есть ? (Q) = Q – r.

Тогда получаем: ? (Q1) = 8 – 3. 8 = 4. 2

? (Q2) = 4. 2 – 5. 2 = - 1

? (Q3) = 6. 8 – 5. 7 = 1. 1

? (Q4) = 8 – 8. 7 = - 0. 7

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

Список литературы:

1. Соловьев В. И. Прикладная математика: Электронный учебный курс. – М. , 2003.

2. Чернов В. П. и другие. Введение в линейное программирование: Электронный курс: http://ecocyb. narod. ru/217-220/begin. htm

3. Колемаев В. А. и другие. Программа и методические указания к выполнению курсового проекта учебной дисциплины «Прикладная математика» для студентов заочного обучения. – М. , 1999.

Бесплатные работы:

Готовые работы:

Рекомендованные документы: