Описание презентации по отдельным слайдам:
Линейное программирование
Линейное программирование Термин «линейное программирование» характеризует определение программы работы конкретного экономического объекта на основе выявления линейных связей между его элементами
Задачи линейного программирования Нахождение оптимального плана выпуска продукции (оптимальное распределение ресурсов) Оптимизация межотраслевых потоков (планирование производства различных видов продукции по отраслям) Определение оптимального рациона (оптимизация состава химической смеси) Транспортная задача (оптимальное распределение потоков товарных поставок по транспортной сети) Задача о размещении производства (планирование с учетом затрат на производство и транспортировку продукции) Задача о назначениях (оптимальное распределение различных видов транспортных средств) И др.
Линейное программирование Задача линейного программирования заключается в изучении способов отыскания наибольшего или наименьшего значения линейной функции при наличии линейных ограничений.
Линейное программирование Решение экстремальных задач можно разбить на 3 этапа: Построение экономико-математической модели Нахождение оптимального решения одним из математических методов Практическое внедрение
Линейное программирование Любая задача линейного программирования включает следующие 3 элемента: Переменные; Целевая функция (функция подлежащая минимизации или максимизации); Ограничения, которым переменные должны удовлетворять
Основная задача линейного программирования Дана линейная форма (целевая функция) Z = C1X1 + C2X2 + . . . + CnXn и задана система линейных неравенств (ограничений) a11x1 + a12x2 + . . . + a1nxn ≤ b1 a21x1 + a22x2 + . . . + a2nxn ≤ b2 . . . . . . . . . . . . . . . . . . . . . . . . am1x1 + am2x2 + . . . + amnxn ≤ bm причем Xj ≥ 0 (j = 1,n) Найти максимальное (минимальное) значение функции Z при выполнении условий
Основная задача линейного программирования Этапы графического метода решения ЗЛП: 1. Построение области допустимых решений. Ограничения ЗЛП в виде неравенств задают выпуклую многогранную область, которая носит название «область допустимых решений». В силу условия неотрицательности переменных x1 и x2 область располагается в первой четверти координатной плоскости (x1 ≥ 0, x2 ≥ 0). Область допустимых решений может иметь вид выпуклого многогранника или выпуклого многогранного неограниченного множества (рис.1). а) выпуклый многогранник; б) выпуклое многогранное неограниченное множество
Основная задача линейного программирования Графический метод решения В С А D 0 c Z=0
Основная задача линейного программирования 2. Исследование поведения целевой функции на области допустимых решений при помощи линий уровня. Линия уровня С — линия, на которой значение целевой функции равно С (то есть график F(x) = C). Рисуем линии уровня при разных значения С и определяем направление движения по линиям уровня (переход от одной линии уровня к другой) при увеличении значения С. Таким образом, с помощью линий уровня можно определить направление возрастания (убывания) значения целевой функции. 3. Нахождение решения. Продвигаем линии уровня в направлении возрастания значения целевой функции, если в задаче требуется найти ее максимум (в направлении убывания, если требуется найти минимум), до достижения последнего касания с областью допустимых решений. Эта линия уровня является «экстремальной».
Основная задача линейного программирования Пример. Найти графическое оптимальное решение системы неравенств 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
Основная задача линейного программирования X1 X2 1 2 3 4 5 C(1;2) А В С D Е
Основная задача линейного программирования 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
Основная задача линейного программирования Задача Z = 3x + 2y max 2x – 3y ≤ 12 -x +2y ≤ 6 x ≤ 6 2x + 5y ≤ 10 x≥0 y ≥0
Вам будут интересны эти курсы:
