Особые случаи решения ЗЛП графическим методом

Автор работы: Пользователь скрыл имя, 12 Января 2011 в 21:09, контрольная работа

Краткое описание

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

Вложенные файлы: 1 файл

К.Р.по ЭММ.doc

— 275.50 Кб (Скачать файл)

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

ГОУ ВПО

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

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

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

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

по  дисциплине ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МЕТОДЫ 

      И ПРИКЛАДНЫЕ МОДЕЛИ 

вариант №   4  
 
 

                                            Выполнил: 

                            Студент        Ачичаева А.А. 

      Курс                                     3 

         Личное дело № 08ФЛБ02594 

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

                    доц. Филонова Е.С. 
 

  
 
 
 
 

Орел 2010

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

      Проиллюстрировать теоретические 

      положения примерами 

Особые  случаи решения ЗЛП  графическим методом. 

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

    Если  область допустимых решений является незамкнутым выпуклым многоугольником в направлении оптимизации целевой функции, то целевая функция будет неограниченной и ЗЛП не будет иметь решений; в этом случае можно записать, что, например, max f( ) = +∞ (пример 1.2.).

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

    Пример 1.1. Найти максимум и минимум f( ):

          f( ) = 3x1 + 3x2

при ограничениях

      x1 + x2 ≤ 8,    (1)

          2x1x2 ≥ 1,   (2)

          x1 – 2x2 ≤ 2,   (3)

           x1,2  ≥ 0.

    Решение. При решении данного примера на максимум возникает ситуация, когда линия уровня 3x1 + 3x2 = a параллельна первому ограничению: x1 + x2 ≤ 8. Целевая функция достигает максимального значения в двух точках: A (3; 5) и В (6; 2) – и принимает на отрезке АВ одно и тоже значение, равное 24:

                    f( ) = 3x1 + 3x2 = 3 * 3 + 3 * 5 = 3 * 6 + 3 * 2 = 24.

     При решении данного примера на минимум  целевой функции линию уровня 3x1 + 3x2 = a следует двигать в направлении, обратном направлению вектора-градиента. Целевая функция достигает минимального значения в точке D (0,5; 0):

          f( ) = 3x1 + 3x2 = 3 * 0,5 + 3 * 0 = 1,5.

    Графическое решение примера приведено на рис. 1.1. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    Рис.1.1. Решение примера 1.1.

    Ответ: max f( ) = 24; min f( ) = 1,5.

    Пример 1.2. Найти максимум f( ):

          f( ) = 3x1 + 3x2

при ограничениях

      2x2x2 ≥ 1,   (1) 
 x1 – 2x2 ≤ 2,   (2)

      x1,2 ≥ 0.

    Решение. Задача не имеет решения, так как ЦФ не ограничена сверху на ОДР (рис. 1.2.).  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

      Рис.1.2. Решение примера 1.2.

    Ответ. max f( ) = +∞.

    Пример 1.3. Найти максимум f( ):

          f( ) = 3x1 + 3x2

при ограничениях

      x1 + x2 ≤ 0,25,    (1)

          2x1x2 ≥ 1,      (2)

          x1 – 2x2 ≤ 2,      (3)

           x1,2  ≥ 0.

    Решение. Задача не имеет решения, система ограничений несовместна (рис. 1.3.). 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Рис.1.3. Решение примера 1.3.

    Ответ: Множество планов пусто.

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

                    оптимизации          

    На  имеющихся у фермера 400 га земли  он планирует посеять кукурузу и  сою. Сев и уборка кукурузы требуют на каждый гектар 200 ден. ед. затрат, а сои – 100 ден. ед. На покрытие расходов, связанных с севом и уборкой, фермер получил ссуду в 60 тыс. ден. ед. Каждый гектар, засеянный кукурузой, принесет 30 центнеров, а каждый гектар, засеянный соей – 60 центнеров. Фермер заключил договор на продажу, по которому каждый центнер кукурузы принесет ему 3 ден. ед., а каждый центнер сои – 6 ден. ед. Однако согласно этому договору фермер обязан хранить убранное зерно в течение нескольких месяцев на складе, максимальная вместимость которого равна 21 тыс. центнеров.

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

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

    Решение.

    Обозначим через х1 сколько гектаров нужно засеять кукурузы, через х2 – сои. Так как у фермера всего имеется 400 га земли, то первое ограничение задачи имеет вид:   х1+ х2 ≤ 400. Найдем общие затраты на сев и уборку кукурузы и сои: (200х1+100х2) ден. ед. Фермер получил на расходы ссуду в 60 тыс. ден. ед., поэтому следующее ограничение имеет вид: 200х1+100х2 ≤ 60 000. Найдем, сколько центнеров зерна соберет фермер: (30х1+ 60х2) ц. Вместимость склада составляет 21 тыс. центнеров, поэтому следующее ограничение имеет вид: 30х1+60х2 ≤ 21 000. Выясним сколько ден. ед. получит фермер по договору за собранное зерно: (30х1*3 + 60х2*6) ден. ед. 

    Построим  экономико-математическую модель задачи:

                                F = 90x1+360x → max

                                х1+ х2 ≤ 400  (I)

                                200х1+100х2 ≤ 60 000  (II)

                                30х1+60х2 ≤ 21 000      (III)

                                x1,2 ³ 0

  Решим задачу графическим методом.

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

  Определим множество решений первого неравенства. Оно состоит из решения уравнения и строгого неравенства. Решением уравнения служат точки прямой x1 + x2 – 400 = 0. Построим прямую по двум точкам (0; 400) и (400; 0), которые легко получить в результате последовательного обнуления одной из переменных. На рис. 2. обозначим ее цифрой I.

  Множество решений строгого неравенства —  одна из полуплоскостей, на которую делит плоскость построенная прямая. Какая из них является искомой, можно выяснить при помощи одной контрольной точки. Если в произвольно взятой точке, не принадлежащей прямой, неравенство выполняется, то оно выполняется и во всех точках той полуплоскости, которой принадлежит контрольная точка, и не выполняется во всех точках другой полуплоскости. В качестве такой точки удобно брать начало координат. Подставим координаты (0; 0) в неравенство x1 + x2 – 400 < 0, получим -400 < 0, т.е. оно выполняется. Следовательно, областью решения неравенства служит нижняя полуплоскость.

  Аналогичным образом построим области решения  двух других неравенств

                            200x1 + 100x2 - 60 000 = 0; x1 = 0, x2 = 600

                            x1 = 300, x2 = 0.      (на рис.2. прямая II);

   200x1 + 100x2 - 60 000 < 0 при x1 = x2 = 0, -60 000 < 0 выполняется, берется левая полуплоскость.

                            30x1 + 60х2 - 21 000 = 0;    x1 = 0, x2 = 350

                            x1 = 700, x2 = 0.    (на рис.2. прямая III);

   30x1 + 60x2 - 21 000 < 0 при x1 = x2 = 0, -21 000 < 0 выполняется, берется нижняя полуплоскость.

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

         x1 + x2 = 400,         x1 = 100; x2 = 300,

        30x1 + 60х2 = 21 000.

   Вычислим  значение целевой функции в этой точке:

                f(Х) = 90x1+360x2=90*100 + 360*300 = 117000.

  Аналогично  поступим для других точек, являющихся вершинами области АВСDO, представляющей собой область допустимых решений рассматриваемой ЗЛП. Координаты этих вершин имеют следующие значения: т. А(0;350), т. В(100;300), т. С(200;200), т. D(300;0), т. О(0;0).

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

   Линия уровня – это прямая заданная уравнением F = c1x1 + c2x2 = a, в каждой точке которой, целевая функция принимает одно и то же значение а.

  Для определения направления движения к оптимуму построим вектор-градиент , координаты которого являются частными производными функции f(X), т.е. =(90; 360) Чтобы построить этот вектор, нужно соединить точку (90; 360) с началом координат. При максимизации целевой функции необходимо двигаться в направлении вектора-градиента, а при минимизации — в противоположном направлении.

  В нашем случае движение линии уровня будем осуществлять до ее пересечения с точкой А. Следовательно, именно в этой точке достигается максимум целевой функции. Отсюда легко записать решение исходной ЗЛП: max f( ) = 126000 и достигается при x1 = 0, x2=350.

   Также мы можем найти, сколько гектаров земли, и какой культурой надо засеять фермеру для получения максимальной прибыли с помощью надстройки EXCEL Поиск решения, которая позволяет решать оптимизационные задачи:

Информация о работе Особые случаи решения ЗЛП графическим методом