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

на основе выявления линейных связей между его элементами

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

наименьшего значения линейной функции при наличии линейных ограничений.

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

подлежащая минимизации или максимизации);
Ограничения, которым переменные должны удовлетворять

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

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

а) выпуклый многогранник; б) выпуклое многогранное неограниченное множество

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

x2 ≥ 2
x1 + 3x2 ≥ 3
x1 - x2 ≥ -1
3x1 - x2 ≤ 6
x1 + x2 ≤ 5
x1 ≥ 0
x2 ≥ 0

а) максимизирующее функцию Z = x1 + 2x2
б) минимизирующее функцию Z = x1 + 2x2

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

max
2x – 3y ≤ 12
-x +2y ≤ 6
x ≤ 6
2x + 5y ≤ 10
x≥0
y ≥0