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

Автор работы: Пользователь скрыл имя, 20 Ноября 2011 в 09:14, курсовая работа

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

Исследование операций – это математическая дисциплина, занимающаяся разработкой и применением методов нахождения наилучших решений в различных областях человеческой деятельности.
Термин "Исследование операций" ("Operation Research") заимствован из западной литературы. Сейчас, пожалуй, нельзя точно назвать, ни дату его возникновения, ни автора, да и вряд ли найдется исчерпывающее определение этого понятия.

Содержание работы

Введение…………………………………………………………………………...3
ГЛАВА I. РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ГРАФИЧЕСКИМ МЕТОДОМ
1. Линейное программирование………………………………………............5
2. Основная задача линейного программирования………………….............7
3. Графический метод решения задачи линейного
программирования…………………………………………………………...........9
4. Методика решения задач линейного программирования графическим методом…………………………………………………………...10
5. Сведения о линейном программировании в электронной
таблице Excel…………………………………………………………………….12
ГЛАВА II. ПРИМЕНЕНИЕ ГРАФИЧЕСКОГО МЕТОДА РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ НА ПРАКТИКЕ
1. Построение математической модели……………………………………..14
2. Решение задачи линейного программирования графическим
методам…………………………………………………………………………...16
3. Решение задачи с помощью электронной таблицы Excel………………18
Заключение ………………………………………………………………………23
Список литературы……………………………………

Содержимое работы - 1 файл

Курсач.doc

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

          Изобразим в системе координат  третье неравенство 6х1+4х2≤80. Построим прямую 6х1+4х2=80

Х1 10 8
Х1 5
 

          Изобразим в системе координат  четвертое неравенство х1≤12. Построим прямую х1=12

          Изобразим в системе координат пятое неравенство х2≤7,5. Построим прямую х2=7,5

         Таким образом многоугольник  ABCD является множеством возможных решений (см.рис.1)

         В системе координат построим  нормальный вектор целевой функции 

n{16;12}

         Вычислим координаты точки максимума

1+14х2=112                 2х1+14х2 – 112=0

1+4х2=80                     6х1+4х2 – 80=0 

1+14х2 – 112

1+14х2=112      

1 =         

336 – 42х2 + 4х2 – 80=0

256 – 38х2=0

-38х2= - 256

 х2= 6,7 

1= 4* = = =-

 х1= 8,8

         Вычисляем значение целевой функции  в точке максимума 16*8,8+12*6,7=140,8+80,4=221,2

        Ответ: Максимальную выручку от продажи журналов «Автомеханик» на одну тысячу экземпляров составит 8,8 тысяч экземпляров, «Инструмент» на одну тысячу экземпляров составит 6,7 тысяч экземпляров, что обеспечивает максимальную выручку от продажи 221,2 у.е. 

3. Решение задачи с помощью электронной таблицы Excel 

Пусть имеем  математическую модель ЗЛП в виде:

Найти максимум функции

ƒ = 16х1 + 12х2 — › max

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

1 + 14х2 ≤ 112

1 + 6х2 ≤ 70

1 + 4х2 ≤ 80

х1, х2 ≥ 0 

      1. Ввод условий (создание модели) задачи состоит из следующих шагов:
  1. Создание  формы для ввода условий задачи заключается в           распределение ячеек таблицы  под константы, переменные и формулы.

  • Ввод исходных данных:
      • в ячейки А2:B2 следует ввести начальные числовые значения изменяемых переменных. В линейных моделях они не влияют на результаты и алгоритм поиска последовательных итераций;
      • диапазон ячеек А5:B7 следует заполнить коэффициентами левых частей ограничений;
      • диапазон ячеек D9:D12 надо заполнить граничными значениями, составляющими правые части неравенств;
      • в диапазон ячеек А14:B14 следует записать коэффициенты целевой функции.
    • Ввод зависимостей (формул) математической модели задачи:
      • Для целевой функции в ячейку В16 записываем формулу, начиная со знака равенства = 16*А2 + 12*В2.
      • Для левых частей ограничений в ячейки В9:В11 вводим формулы, начиная со знака равенства:

        =СУММПРОИЗВ($A$2:$B$2;A5:B5),

        =СУММПРОИЗВ($A$2:$B$2;A6:B6),

        =СУММПРОИЗВ($A$2:$B$2;A7:B7),

        1. В созданной модели выделите ячейку В16 с целевой функцией.
        2. Выберете команду Сервис/Поиск решения (Рис. 1)
     
     
     

     

    Рис1. 

        1. В группе Равной установите направление целевой функции: Максимальному значению.
        2. Поместив курсор в поле Изменяемые ячейки, наберите с клавиатуры А2:С2 или выделите эти ячейки, протащив указатель мыши по диагонали диапазона.
        3. Установите курсор поля Ограничения и нажмите кнопку Добавить. На экране увидите диалоговое окно Добавление ограничений (Рис. № 2)

          Для ввода  условий неотрицательности переменных       (А2≥0, В2≥0, С2≥0) выполните действия:

      •   Установив текстовый курсор в поле Ссылка на ячейку, укажите       диапазон А2:B2;
      •    Щелкните курсором по стрелке вниз и выберете из открывшегося списка знак отношения >=;
      • В правое окно Ограничение введите число 0, кнопка Добавить служит для ввода следующих ограничений;
      • Аналогично введите В9 ≥ D9, B10 ≥ D10, B11 ≥ D11, B12 ≥ D12.
     

    Рис2. 

    Кнопка ОК возвращает в диалоговое окно Поиск решений. Оно уже содержит введенный граничные условия.

    Если при вводе  условий задачи возникает необходимость  изменения или удаления внесенных  ограничений или граничных условий, то используется кнопки Изменить…, Удалить.

    Команда Выполнить (см. Рис. 1) при снятом флажке Показывать результаты итерации (Рис. 3) приведет к успешному завершению поиска решения.  

    Рис3. 

    В результате выполнения команды в диапазоне А2:B2 будут находиться значения переменных, а в ячейках В16-значения целевой функции (Рис.4) 
     
     
     
     
     
     
     
     

        Рис4. 
         
         

    Измененная таблица командой Поиск решения (Рис.5) 
     
     

        Рис5. 
         

    Вывод по главе II:

    В ходе решения  задачи оптимизации:

    1) была  получена математическая модель вида:

           Z(х) =16х1+12х2→max

             2х1+14х2≤112

             4х1+6х2≤70

             6х1+4х2≤80

             х1≤12

             х2≤7,5

          х12≥0

    2) Максимальную выручку от продажи журналов «Автомеханик» на одну тысячу экземпляров составит 8,8 тысяч экземпляров, «Инструмент» на одну тысячу экземпляров составит 6,7 тысяч экземпляров, что обеспечивает максимальную выручку от продажи 221,2 у.е.  
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     

    Заключение 

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

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

         Z(х) =16х1+12х2→max

             2х1+14х2≤112

             4х1+6х2≤70

             6х1+4х2≤80

             х1≤12

             х2≤7,5

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

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

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

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

    1. АстафуровВ.Г., Колодникова Н. Компьютерное учебное пособие, Томск, 2002.
    2. Алесинская Т.В. Задачи по исследованию операций с решениями. Москва, Учебное пособие, 2000.
    3. Смородинский С.С., Батин Н.В. Оптимизация решений на основе методов и моделей математического программирования: Москва, Учебное пособие, 2002
    4. Кононов В.А. Исследование операций. Москва, 2000

    5.Филипс Д., Горсия-Диас А. Методы анализа сетей. Москва, Мир, 1984

    6. Морозов  В.В., Сухарев А.Г., Федоров В.В.  Исследование операций в задачах и упражнениях. Москва, Высшая школа, 1986

    7. Ермаков  В.И., Кремер Н.Ш., Савельева Т.И.  Математические методы в экономике.  Москва, 2000           
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     

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