Линейное программирование и его применение в финансовых задачах

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

«Финансовый университет при правительстве  Российской Федерации» 
 
 
 
Кафедра

«Прикладная математика» 
 
 
 
 
КУРСОВАЯ РАБОТА

на тему: «Линейное программирование и его применение в финансовых задачах» 
 
 
 
 
 
 

Студент факультета

«Математические методы и анализ рисков»,

Группа  
 

Научный руководитель 
к.ф.- м.н., доцент,  
 

 

 

 

 

Москва 2011г.

 

Содержание

 

Введение 3

Линейное программирование 5

Решение задач 15

Заключение.21

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

 

 

Введение

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

Методы линейного программирования оказались весьма эффективными для  решения некоторых задач из области исследования операций. Слово “программирование" мы понимаем как планирование, и это определяет характер рассматриваемых приложений. Основные идеи линейного программирования возникли во время второй мировой войны в связи с поиском оптимальных стратегий при ведении военных операций. С тех пор они нашли широкое применение в промышленности, торговле и управлении - как в местных, так и в государственных масштабах. Этими методами можно решить многие (хотя не все) задачи, связанные с эффективным использованием ограниченных ресурсов.

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

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

      Еще одним пример  практического применения линейного  программирования в финансовой  сфере является транспортная  задача  – задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи). Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку).

    

 

 

  

 

 

Линейное  программирование

В линейном программировании мы рассматриваем оптимизационную модель в пространстве , определенном неравенствами.

Например, неравенства

 

определяют треугольную область  в  с вершинами (0; 0), (0; 10), (10; 0).

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

Цель

Вообще, цель состоит в нахождении экстремумов линейной целевой функции с учетом линейных неравенств. 
То есть,

 

с условиями

 

и

 

Линейные неравенства

Уравнение

 

Определяет гиперплоскость в .

В это прямая:

 

В это плоскость:

 

Неравенство:

 

Определяет все точки, лежащие на одной стороне этой гиперплоскости.

Противоположная сторона соответствует обратному неравенству.

Линейные неравенства (продолжение)

Мы представляем общее линейное неравенство в как

.

Это неравенство называют слабым относительно x, если стоит знак “” .

Его называют связанным относительно x, если стоит знак  “”.

Оно называется невыполнимым относительно x, если оно не верно при x.

Задача оптимизации

В векторном обозначении задачей максимизации является

 

при условии

  и .

Здесь А-матрица и f - вектор .

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

 

называется допустимым множеством.

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

Для решения задачи на максимизацию, мы рассмотрим графический метод.

 

 

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

  при условии

 

 

 

Максимум целевой функции достигается в точке (2;0) и равен 2.

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

Для n=2 мы можем это сделать.

Для n=3 это так же возможно, хотя не так просто.

Для n=4 это становится практически невозможным.

 Графического метод решения задачи линейного программирования.

Графический метод состоит из следующих шагов:

• Сделать график для допустимого множества.
• Построить линии уровня функции
• Найти самый высокий (или самый низкий) уровень, который все еще имеет точку, принадлежащую допустимому множеству

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

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

Замечание.

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

 

 

 

Пример

Пространство А состоит из (), удовлетворяющих

 

Решим следующие задачи в А:

Получается следующий график:

 

 

1.  

f(max)=f(A)=f(1,6)=6

2.

 

f(max)=f(B)=f(7,0)=21

    

 

f(max)=f(B)=f(7,0)=7

 

Еще один пример

 Предположим, что есть два продукта, молоко и хлеб, которые стоят €0.60 и €1 за единицу. Предположим, что содержание питательных веществ в молоке и хлебе:

Вещества	Единица молока	Единица хлеба	Дневная норма
Кальций	10 мг	4 мг	20 мг
Протеин	5 г	5 г	20 г
Витамин В	2 мг	6 мг	12 мг

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

Запишем задачу в виде уравнений:

 

 

 

 

 

 

Проводя линии уровня, перпендикулярные вектору нормали мы получим минимум целевой функции в точке B.

C=

f(min)=f(C)=f(3,1)=2,8€.

Некоторые замечания

I.

Графический метод плохо подходит для того, чтобы решать задачи линейного программирования более чем с 2 переменными.

II.

Задача линейного программирования может не дать нам максимум или минимум. Это может произойти по двум причинам:

1. Допустимое множество пусто;

2. Допустимое множество неограниченно.

III.

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

Пустые и неограниченные допустимые множества 
Пример 
Множество точек, которые удовлетворяют следующим ограничениям пусто

 

Пример (снова молочно-хлебная диета)

Рассмотрим с ограничениями

 

Поскольку допустимое множество неограниченно, то С не имеет максимум.

Стандартная форма симплекс-метода

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

1. Правая сторона ограничений не может быть отрицательной;
2. Всех ограничения должны быть уравнениями;
3. Всех переменные должны быть ограничены неотрицательными значениями.

Если мы переформулируем задачу линейного программирования для удовлетворения этих требований, то мы говорим, что множество ограничений записано в стандартной форме.

 

Требование II.Ограничения как уравнения

Для каждого случая ограничений “меньше или равно”, неотрицательная переменная s,называемая слабой переменной, добавляется к левой части ограничения, превращая его в равенство.

Пример

Ограничение преобразуется в

Для каждого случая ограничений “больше или равно” неотрицательная переменная e, называемая избыточной переменной, вычитается из левой части ограничения. Кроме того, неотрицательная переменная a, называемая искусственной переменной, добавляется к левой части ограничения.

Пример

Ограничение преобразуется в эквивалентное равенство

  с и .

Для каждого случая ограничений “равно” искусственная переменная добавляется к левой части ограничения.

Пример

Преобразовать следующий набор ограничений в стандартную форму:

 

 

 

 

Требования I и III

Требование I симплекс-метода говорит, что правая сторона любого уравнения ограничения должно быть неотрицательным. Если это ограничения имеет отрицательную правую сторону, то мы умножаем на -1.

Пример

Ограничение преобразуется в .

Требование III говорит, что все переменные имеют неотрицательные значения.

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

Пример

Преобразуйте следующий набор ограничений в стандартную форму, добавив дополнительные переменные:

 

 

 

 

 

Замечание

Искусственные переменные, могут оказаться “слишком” искусственными и не иметь реального значения в проблеме.

Однако, мы нуждаемся в них, чтобы  обеспечить удобную отправную точку

(начальное решение) в симплекс-методе.

 

Решение задач

№3.1

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

а)

 

Построим прямые и ;

вектор нормали 

Видно, что проводя линии уровня, перпендикулярные вектору нормали мы получим максимум целевой функции в точке А.

 Из пересечения прямых и мы находим ее координаты: A ().

Теперь находим значение целевой функции:

f(max)=f(A)=f()=3*7,2.

б)

 

 

 

 

 

Делаем все аналогично:

 

  = A ().

f(max)=f(A)=f()=2*

 

в) 8

 

 

 

 

 

f(B)>f(C)>f(A)

B==(5,1)

f(max)=f(B)=f(5,1)=49

 

№3.2 Пространство А содержит все , удовлетворяющие

 

Решите следующие задачи в допустимом пространстве А:

а)

б)

в) 3

г) 2

д) -3

 

 

B=

 

а)

Проводя линии уровня, перпендикулярные оси , мы получаем, что максимум достигается в точке B.

f(max)=f(B)=

б)

f(max)=f(С)=

в)3

 

f(max)=f(C)=3*8+2*0=24

г) 2

 

f(min)=f(A)=0*2-2*2=-4

д) -3

 

f(min)=f(С)=-24

 

№3.3 В данных задачах линейного программирования приведите ограничения в стандартную форму:

а) 5

 

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

1. Правая сторона ограничений не может быть отрицательной;
2. Всех ограничения должны быть уравнениями;
3. Всех переменные должны быть ограничены неотрицательными значениями.

5

 

б) 3

 

Получаем:

3

 

 

Заключение.

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

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

 

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

1. Sander Zwegers. Optimization in Finance, 2010.

2. Б. Банди. Основы линейного программирования – М.: «Радио и связь», 1989.