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

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

 

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

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

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

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

n{16;12}

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

2х₁+14х₂=112                 2х₁+14х₂ – 112=0

6х₁+4х₂=80                     6х₁+4х₂ – 80=0 

2х₁+14х₂ – 112

2х₁+14х₂=112      

2х₁ =         

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

256 – 38х₂=0

-38х₂= - 256

 х₂= 6,7 

6х₁= 4* = = =-

 х₁= 8,8

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

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

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

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

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

ƒ = 16х₁ + 12х₂ — › max

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

2х₁ + 14х₂ ≤ 112

4х₁ + 6х₂ ≤ 70

6х₁ + 4х₂ ≤ 80

х₁, х₂ ≥ 0 

1. Ввод условий (создание модели) задачи состоит из следующих шагов:

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

Ввод исходных данных:

• в ячейки А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),

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

 
 
 

 

Рис1. 

4. В группе Равной установите направление целевой функции: Максимальному значению.
5. Поместив курсор в поле Изменяемые ячейки, наберите с клавиатуры А2:С2 или выделите эти ячейки, протащив указатель мыши по диагонали диапазона.
6. Установите курсор поля Ограничения и нажмите кнопку Добавить. На экране увидите диалоговое окно Добавление ограничений (Рис. № 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х₁+12х₂→max

         2х₁+14х₂≤112

         4х₁+6х₂≤70

         6х₁+4х₂≤80

         х₁≤12

         х₂≤7,5

      х₁,х₂≥0

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

Заключение 

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

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

     Z(х) =16х₁+12х₂→max

         2х₁+14х₂≤112

         4х₁+6х₂≤70

         6х₁+4х₂≤80

         х₁≤12

         х₂≤7,5

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

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

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

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

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

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

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

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