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

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

ГОУ ВПО 

ВСЕРОССИЙСКИЙ ЗАОЧНЫЙ ФИНАНСОВО-ЭКОНОМИЧЕСКИЙ  ИНСТИТУТ 

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

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

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

По  дисциплине: Экономико-математические методы и прикладные модели

Тема______________________________________________________________ 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Уфа 2011

Вариант №3 

     Задание 1.Изложить материал по теме.

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

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

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

     Наиболее простым и наглядным методом решения задачи линейного программирования (ЗЛП) является графический метод. Он основан на геометрической интерпретации задачи линейного программирования и применяется при решении ЗЛП с двумя неизвестными: 

 f (x_1,х₂) = c₁х_{1 +} c₂х₂ → max (min),

a_i1x₁ +a_i2 x₂ ≤ (≥, =) b_i,    i= 1, m,

x_{1, 2}≥ 0. 

     Каждое из неравенств задачи линейного программирования определяет на координатной плоскости  некоторую полуплоскость, а система неравенств в целом – пересечение соответствующих плоскостей. Каждое неравенство системы функциональных ограничений геометрически определяет полуплоскость с граничной прямой a_i1x₁ +a_i2x₂ ≤ (≥, =) b_i  , i= 1,m.

     Условия не отрицательности определяют полуплоскости с граничными прямыми x₁=0, х₂=0 соответственно. Если система совместна, то полуплоскости, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из этих точек являются решением данной системы. Совокупность этих точек называют многоугольником решений. Он может быть точкой, отрезком, лучом, ограниченным и неограниченным многоугольником.

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

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

     Определим, какую часть плоскости описывает неравенство 2х₁ + 3х₂ ≤ 12.

     Во-первых, построим прямую 2х₁ + 3х₂ = 12. Она проходит через точки

(6; 0) и  (0; 4). Во-вторых, определим, какая  полуплоскость удовлетворяет неравенству.  Для этого выбираем любую точку  на графике, не принадлежащую  прямой, и подставляем ее координаты в неравенство. Если неравенство будет выполняться, то данная точка является допустимым решением и полуплоскость, содержащая точку, удовлетворяет неравенству. Для подстановки в неравенство удобно использовать начало координат. Подставим х₁ = х₂= 0 в неравенство 2х₁ + 3х₂ ≤ 12. Получим 2 * 0 + 3 * 0 ≤ 12. Данное утверждение является верным, следовательно, неравенству

2х₁ + 3х₂ ≤ 12 соответствует нижняя полуплоскость, содержащая точку (0; 0). Это отражено на графике, изображенном на рис. 1. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

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

     Необходимо помнить, что область допустимых решений удовлетворяет условиям не отрицательности (x_j ≥ 0, j = 1,n). Координаты любой точки, принадлежащей области определения, являются допустимым решением задачи.

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

             V =   ( ∂f / ∂x₁ = c₁, ∂f / ∂x₂ =  c₂) 

     Этот вектор показывает направление наискорейшего изменения целевой функции. Прямая c₁х_{1 +} c₂х₂= f(x₀),перпендикулярная вектору-градиенту, является линией уровня целевой функции (рис. 2). В любой точке линии уровня целевая функция принимает одно и то же значение. Приравняем целевую функцию постоянной величине а. Меняя значение а, получим семейство параллельных прямых, каждая из которых является линией уровня целевой функции. 
 
 
 
 
 
 
 
 
 
 
 
 

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

     Графический метод решения ЗЛП состоит из четырех этапов:

1.  Строится  область допустимых решений (ОДР)  ЗЛП.

2.  Строится  вектор-градиент целевой функции  (ЦФ) с началом в точке 

x₀ (0; 0): V= (с₁, с₂).

3.  Линия  уровня c₁х_{1 +} c₂х₂= а (а - постоянная величина) — прямая, перпендикулярная вектору-градиенту V, — передвигается в направлении вектора-градиента в случае максимизации целевой функции f(x_1,х₂)до тех пор, пока не покинет пределов ОДР. При минимизации f(x_1,х₂) линия уровня перемещается в направлении, противоположном вектору-градиенту. Крайняя точка (или точки) ОДР при этом движении и является точкой максимума (минимума) f(x_1,х₂).

     Если прямая, соответствующая линии уровня, при своем движении не покидает ОДР, то минимума (максимума) функции f(x_1,х₂)не существует.

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

4. Определяются  координаты точки максимума (минимума). Для этого достаточно решить  систему уравнений прямых, дающих  в пересечении точку максимума  (минимума). Значение f(x_1,х₂), найденное в полученной точке, является максимальным (минимальным) значением целевой функции.

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

Возможные ситуации графического решения ЗЛП  представлены в табл. 1:

     Рассмотрим решение задач линейного программирования графическим способом в задании 2 (2.3). 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

     2.3 Фирма выпускает два набора удобрений для газонов: обычный и улучшенный. В обычный набор входит 3 кг азотных, 4 кг фосфорных и 1 кг калийных удобрений, а в улучшенный – 2 кг азотных, 6 кг фосфорных и 3 кг калийных удобрений. Известно, что для некоторого газона требуется,  по меньшей мере 10 кг азотных, 20 кг фосфорных и 7 кг калийных удобрений. Обычный набор стоит 3 ден. ед., а улучшенный – 4 ден. ед.  Какие и сколько наборов удобрений нужно купить, чтобы обеспечить эффективное питание почвы и минимизировать стоимость?

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

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

Переменные: x_1,х_{2 –} два набора удобрений для газонов: обычный и улучшенный.

Целевая функция: мы стремимся минимизировать стоимость, поэтому

f (X) = 3 x₁ + 4 x₂ → min.

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

        3 x₁ +2 x₂ ≥ 10,

        4 x₁+6 x₂ ≥ 20,

        1 x₁+3 x₂ ≥ 7,

       x₁ ≥ 0. 

     Первое ограничение по азотным  удобрениям имеет вид: 3 x₁ +2 x₂ ≥ 10. Найдем пересечение с осями координат. В ограничениях задачи заменяем знаки неравенств знаками точных равенств и строим соответствующие прямые. Прямая 3x₁ +2 x₂ = 10 проходит через точки (0;5) и (3,3;0). Второе ограничение по фосфорным удобрениям имеет вид: 4 x₁+6 x₂ ≥ 20. Прямая 4x₁+6 x₂ = 20 проходит через точки (0;3,3) и (5;0).Третье ограничение по калийным удобрениям имеет вид: 1x₁+3 x₂ ≥ 7. Прямая  1 x₁+3 x₂ = 7 проходит через точки (0;2,3) и (7;0). (Рис.1) (полуплоскости обозначены штрихом). 
 
 
 
 
 
 

Рисунок 1 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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