Презентация по дисциплине "Математическое моделирование" на тему "Линейное программирование"

• 1 слайд

  Линейное программирование
  

• 2 слайд

  Линейное программирование
  Термин «линейное программирование» характеризует определение программы работы конкретного экономического объекта на основе выявления линейных связей между его элементами
  

• 3 слайд

  Задачи линейного программирования
  Нахождение оптимального плана выпуска продукции (оптимальное распределение ресурсов)
  Оптимизация межотраслевых потоков (планирование производства различных видов продукции по отраслям)
  Определение оптимального рациона (оптимизация состава химической смеси)
  Транспортная задача (оптимальное распределение потоков товарных поставок по транспортной сети)
  Задача о размещении производства (планирование с учетом затрат на производство и транспортировку продукции)
  Задача о назначениях (оптимальное распределение различных видов транспортных средств)
  И др.
  
  

• 4 слайд

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

• 5 слайд

  Линейное программирование
  Решение экстремальных задач можно разбить на 3 этапа:
  Построение экономико-математической модели
  Нахождение оптимального решения одним из математических методов
  Практическое внедрение
  

• 6 слайд

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

• 7 слайд

  Основная задача линейного программирования
  Дана линейная форма (целевая функция)
  Z = C1X1 + C2X2 + . . . + CnXn
  и задана система линейных неравенств (ограничений)
  a11x1 + a12x2 + . . . + a1nxn ≤ b1
  a21x1 + a22x2 + . . . + a2nxn ≤ b2
  . . . . . . . . . . . . . . . . . . . . . . . .
  am1x1 + am2x2 + . . . + amnxn ≤ bm
  причем Xj ≥ 0 (j = 1,n)
  Найти максимальное (минимальное) значение функции Z при выполнении условий
  
  

• 8 слайд

  Основная задача линейного программирования
  Этапы графического метода решения ЗЛП:
  1. Построение области допустимых решений. Ограничения ЗЛП в виде неравенств задают выпуклую многогранную область, которая носит название «область допустимых решений».
  В силу условия неотрицательности переменных x1 и x2 область располагается в первой четверти координатной плоскости (x1 ≥ 0, x2 ≥ 0). Область допустимых решений может иметь вид выпуклого многогранника или выпуклого многогранного неограниченного множества (рис.1).
  а) выпуклый многогранник; б) выпуклое многогранное неограниченное множество
  

• 9 слайд

  Основная задача линейного программирования
  Графический метод решения
  
  
  В
  С
  А
  D
  0
  c
  Z=0
  

• 10 слайд

  Основная задача линейного программирования
  2. Исследование поведения целевой функции на области допустимых решений при помощи линий уровня.
  Линия уровня С — линия, на которой значение целевой функции равно С (то есть график F(x) = C). Рисуем линии уровня при разных значения С и определяем направление движения по линиям уровня (переход от одной линии уровня к другой) при увеличении значения С. Таким образом, с помощью линий уровня можно определить направление возрастания (убывания) значения целевой функции.
  3. Нахождение решения. Продвигаем линии уровня в направлении возрастания значения целевой функции, если в задаче требуется найти ее максимум (в направлении убывания, если требуется найти минимум), до достижения последнего касания с областью допустимых решений. Эта линия уровня является «экстремальной».
  
  

• 11 слайд

  Основная задача линейного программирования
  Пример. Найти графическое оптимальное решение системы неравенств
  
  2x1 + x2 ≥ 2
  x1 + 3x2 ≥ 3
  x1 - x2 ≥ -1
  3x1 - x2 ≤ 6
  x1 + x2 ≤ 5
  x1 ≥ 0
  x2 ≥ 0
  
  а) максимизирующее функцию Z = x1 + 2x2
  б) минимизирующее функцию Z = x1 + 2x2
  
  

• 12 слайд

  Основная задача линейного программирования
  X1
  X2
  1
  2
  3
  4
  5
  C(1;2)
  А
  В
  С
  D
  Е
  

• 13 слайд

  Основная задача линейного программирования
  2x1 + x2 = 2
  x1 + 3x2 = 3
  
  x1 - x2 = -1
  x1 + x2 = 5
  D (0,6; 0,8) А (2; 3)
  
  Zmin = 0,6 + 2*0,8 = 2,2
  Zmax = 2 + 2*3 = 8
  

• 14 слайд

  Основная задача линейного программирования
  Задача
  Z = 3x + 2y max
  2x – 3y ≤ 12
  -x +2y ≤ 6
  x ≤ 6
  2x + 5y ≤ 10
  x≥0
  y ≥0
  

Краткое описание документа:

Термин «линейное программирование» характеризует определение программы работы конкретного экономического объекта на основе выявления линейных связей между его элементами.

В презентации представлены задачи линейного программирования, описание и методы решения основной задачи линейного программирования, этапы графического метода решения ЗЛП