Контрольная работа по "Экономико-математическому моделированию"

 

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

ГОУ ВПО

ФИНАНСОВЫЙ УНИВЕРСИТЕТ ПРИ  ПРАВИТЕЛЬСТВЕ РОССИЙСКОЙ ФЕДЕРАЦИИ 

Уфимский  филиал

 

 

Кафедра Математики и информатики

 

 

Факультет: финансово-кредитный

Специальность: бакалавр экономики

 

 

 

КОНТРОЛЬНАЯ РАБОТА

по  дисциплине  «ЭММ и ПМ»

 

 

       

    Выполнил:

     Студент Исангулова Айгуль Наиловна

     Курс 3 (2во)

     Группа № 23БЭ

     Личное дело № 12190ФЛ20096

 

                        Преподаватель:

     Фархиева Светлана Анатольевна

 

 

 

Уфа 2012

Задание 1. Изложить материал по выбранной теме.  Проиллюстрировать теоретические положения примерами.

Вариант 1.15.

Метод оптимизации Лагранжа

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

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

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

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

Рассмотрим задачу минимизации  функции n переменных с учетом одного ограничения в виде равенства:  
Минимизировать        f (x₁, x₂, ..., x_n) → min                               (1)  
при ограничениях                 h₁( x₁, x₂, ..., x_n)                                               (2) 

В соответствии с методом множителей Лагранжа эта задача преобразуется  в следующую задачу безусловной  оптимизации:  
минимизировать 

                          L(x,u) = f(x) – u*h(x)                                             (3)

Функция  L(х;u) называется функцией Лагранжа,

u  – неизвестная постоянная, которая носит название множителя Лагранжа. На знак u никаких требований не накладывается.  
 Пусть при заданном значении u=u⁰ безусловный минимум функции L(x,u) по х достигается в точке x = x⁰ и x₀ , x =x⁰ и x⁰  и  удовлетворяет уравнению h₁(x⁰) = 0. Тогда,  x⁰ минимизирует с учетом (2), поскольку для всех значений х, удовлетворяющих (4), h₁(x)=0  и   L(x,u) = min f(x).  
 Разумеется, необходимо подобрать значение u=u⁰ таким образом, чтобы координата точки безусловного минимума х⁰ удовлетворяла равенству (2). Это можно сделать, если, рассматривая u как переменную, найти безусловный минимум функции (3) в виде функции u, а затем выбрать значение u, при котором выполняется равенство (2). Проиллюстрируем это на конкретном примере. 

Пример 1  
 Минимизировать      
 при ограничении    =0  
 Соответствующая задача безусловной оптимизации записывается в следующем виде:  
  минимизировать        L(x,u)=  – u   
 Решение.

Приравняв две компоненты градиента L к нулю, получим  
   
   
 Для того чтобы проверить, соответствует ли стационарная точка х⁰ минимуму, вычислим элементы матрицы Гессе функции L(х;u), рассматриваемой как функция х,  
,  
которая оказывается положительно определенной. Это означает, что L(х,,u) — выпуклая функция х.

Следовательно, координаты    ,   определяют точку глобального минимума. Оптимальное значение u находится путем подстановки значений   и    в уравнение  =2, откуда 2u+u/2=2 или u⁰=4/5 .

Таким образом, условный минимум достигается  при   и    и равен min f(x)=4/5.  
 При решении задачи из примера 1 мы рассматривали L(х;u) как функцию двух переменных   и   и, кроме того, предполагали, что значение параметра u выбрано так, чтобы выполнялось ограничение. Если же решение системы  
,   j=1,2,3,…, n в виде явных функций u получить нельзя, то значения х и u находятся путем решения следующей системы, состоящей из n+1 уравнений с n+1 неизвестными:  
 ,    j=1,2,3,…,n          
 Для нахождения всех возможных решений данной системы можно использовать численные методы поиска (например, метод Ньютона). Для каждого из решений ( x⁰, u⁰) следует вычислить элементы матрицы Гессе функции L, рассматриваемой как функция х, и выяснить, является ли эта матрица положительно определенной (локальный минимум) или отрицательно определенной (локальный максимум).  
 Метод множителей Лагранжа можно распространить на случай, когда задача имеет несколько ограничений в виде равенств. Рассмотрим общую задачу, в которой требуется  минимизировать  f(x)  при ограничениях h_k =0, k=1,2, ...,К.  
 Функция Лагранжа принимает следующий вид:  
     L(x,u) = f(x)-   
 Здесь  множители Лагранжа, т.е. неизвестные параметры, значения которых необходимо определить. Приравнивая частные производные L по х к нулю, получаем следующую систему n уравнении с n неизвестными:  
 
 
………..  
 
 Если найти решение приведенной выше системы в виде функций вектора u оказывается затруднительным, то можно расширить систему путем включения в нее ограничений в виде равенств  
 
 
 
 Решение расширенной системы, состоящей из n+К уравнений с n+К неизвестными, определяет стационарную точку функции L. Затем реализуется процедура проверки на минимум или максимум, которая проводится на основе вычисления элементов матрицы Гессе функции L, рассматриваемой как функция х, подобно тому, как это было проделано в случае задачи с одним ограничением. Для некоторых задач расширенная система n+К уравнений с n+K неизвестными может не иметь решений, и метод множителей Лагранжа оказывается неприменимым. Следует, однако, отметить, что такие задачи на практике встречаются достаточно редко. 

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

 

Задание 2.  Решить графическим методом типовую задачу оптимизации

Вариант 2.5.

Продукция двух видов (краска для внутренних (I) и наружных (Е) работ) поступает  в оптовую продажу. Для производства красок используются два исходных продукта А и В. Максимально возможные  суточные запасы этих продуктов составляют 6 и 8 тонн соответственно. Расходы продуктов  А и В на 1 т соответствующих красок приведены ниже.                                   

Исходный продукт	Расход исходных продуктов  на тонну краски, т		Максимально возможный запас
	Краска Е	Краска I
А	1	2	6
В	2	1	8

Изучение рынка сбыта показало, что суточный спрос на краску I никогда  не превышает спроса на краску Е  более чем на 1 т. Кроме того, установлено, что спрос на краску I никогда  не превышает 2 т в сутки. Оптовые  цены одной тонны красок равны: 3000 ден. ед. для краски Е и 2000 ден. ед. для краски I. Какое количество краски каждого вида должна производить  фабрика, чтобы доход от реализации продукции был максимальным?

Построить экономико-математическую модель задачи, дать необходимые комментарии к ее элементам и получить решение графическим методом. Что произойдет, если решать задачу на минимум, и почему?

 

Решение:

Экономико-математическая модель задачи

1) Пусть:  х₁ – количество краски Е, изготовленной фабрикой за сутки,т

        х₂ – количество краски I, изготовленной фабрикой за сутки,т

2) Сформируем целевую функцию общий доход количества  х₁ краски Е будет 3000х₁, а общий доход х₂ краски I будет 2000х₂

f(x) =3000x₁ + 2000x₂ → max

3000x₁ + 2000x₂  – это выручка от реализации красок обоих видов.

3) На производство количества х₁ краски Е уйдет 1х₁ исходного продукта А, а на производство краски I уйдет 2х₂ исходного продукта В. 6 – запас продукта А.

x₁ + 2x₂ ≤  6

На производство количества х₁ краски Е уйдет 2х₁ исходного продукта В, а на производство краски I уйдет 1х₂ исходного продукта В. 8 – запас продукта В.

2x₁ + x₂ ≤ 8

По условию  сказано, что суточный спрос на краску I никогда не превышает спроса на краску Е более чем на 1 т. Отсюда следует: x₂ – x₁ ≤ 1

Установлено, что спрос на краску I никогда не превышает 2 т в сутки. Отсюда следует: x₂ ≤  2.

Ограничения задачи будет иметь вид:

x₁ + 2x₂ ≤ 6

2x₁ + x₂ ≤ 8

x₂ – x₁ ≤ 1

x₂ ≤  2

x₁ ≥ 0;  x₂ ≥ 0

А) Преобразуем  уравнение x₁ + 2x₂ ≤ 6, т.е. поставим в ограничении знак «=»

x₁ + 2x₂ = 6 – решением уравнения является прямая. Найдем точки, через которые проходит искомая прямая:

Х1	0	6
Х2	3	0

 

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

x₁ + 2x₂ <6 – решением неравенства является полуплоскость. Подставим в неравенство координаты точки О (0; 0)

0 + 2 · 0 < 6 (верно), значит искомая полуплоскость содержит точку О

(рис. 2.1).

рис.2.1

Б) Преобразуем  уравнение 2x₁ + x₂ ≤ 8.

2x₁ + x₂ = 8 – решением уравнения является прямая. Найдем точки, через которые проходит искомая прямая:

Х1	0	4
Х2	8	0

2x₁ + x₂ < 8 –  решением неравенства является полуплоскость. Подставим в неравенство координаты точки О (0; 0)

2 · 0 + 0 < 8  (верно), значит искомая полуплоскость содержит точку О

(рис. 2.2)

рис. 2.2

В) Преобразуем уравнение x₂ – x₁ ≤ 1.

x₂ – x₁ = 1 – решением уравнения является прямая. Найдем точки, через которые проходит прямая:

Х1	0	-1
Х2	1	0

x₂ – x₁ ≤ 1 – решением неравенства является полуплоскость. Подставим координаты точки О (0; 0)

0 – 0 < 1 (верно), следовательно искомая полуплоскость содержит данную точку О (рис. 2.3).

Рис. 2.3

Г) Преобразуем  уравнение x₂ ≤  2

x₂ = 2 –  решением  является прямая, параллельная оси Х₁ 

x₂ < 2 – решением является полуплоскость, содержащая точку О (0; 0).

Д) Преобразуем  уравнение x₁ ≥ 0

x₁ = 0 – решение - прямая, совпадающая с осью Х₂

x₁ > 0  – решение - правая полуплоскость (рис. 2.4)

Рис. 2.4

4) Получим многогранник ОАВСD, который образован всеми 3-мя пересекающимися плоскостями, т.е. любые значения точек внутри этого многогранника и на линиях его ограничивающих являются ОДР (областью допустимых решений) всех неравенств (рис. 2.5).

Рис. 2.5

5) Для определения направлений движения к оптимуму построим вектор-градиент V, координаты которого являются частными производными целевой функции: 

 

Для удобство строим вектор, пропорциональный вектору . В данном случае изобразим вектор: V (c₁; c₂) = (3; 2).

Чтобы построить  такой вектор, нужно соединить  точку (3; 2) с началом координат.

6) Затем строим линию уровня 3000x₁ + 2000x₂ = а. Приравняем целевую функцию постоянной величине а. Меняя значение а, получим семейство параллельных прямых, каждая из которых является линией уровня целевой функции.

Далее будем  передвигать линию уровня до ее выхода из ОДР. В  нашем случае (при максимизации целевой функции) будем осуществлять в направлении градиента. В крайней  угловой точке D достигается максимум целевой функции (рис. 2.6).

Рис. 2.6

7) Для нахождения координат точки D достаточно решить систему из двух уравнений прямых, дающих в пересечении точку максимума. Так как точка D получена в результате пересечения прямых x₁ + 2x₂ = 6 и 2x₁ + x₂ = 8, то ее координаты удовлетворяют уравнениям этих прямых: