Геометрическая интерпретация ЗЛП. (Тема 4)

1. Геометрическая интерпретация ЗЛП

2. Основные определения

Точка А называется линейной выпуклой комбинацией точек
A1 , A2 ,
если
A 1 A1 2 A2 , 1 2 1, 1, 2 0.
Множество называется выпуклым, если с любыми своими
двумя точками оно содержит их произвольную линейную
выпуклую комбинацию.
выпуклое множество
не выпуклое множество
Граничной точкой множества называется точка, для
которой верно: любой шар со сколь угодно малым радиусом
содержит точки как принадлежащие, так и не принадлежащие
множеству.

3.

Множество называется замкнутым, если оно содержит
все свои граничные точки.
Множество называется ограниченным, если существует
шар, радиусом R, содержащий в себе всё множество.
Точка называется угловой, если она не может быть
представлена в виде выпуклой линейной комбинации двух
различных точек этого множества.
Ограниченное выпуклое замкнутое множество на плоскости
с конечным числом вершин называется выпуклым
многоугольником.
Теорема Выпуклый замкнутый ограниченный многогранник
является выпуклой линейной комбинацией своих угловых точек.
Лемма Пересечение любого количества выпуклых множеств
является выпуклым множеством.

4. Геометрическая интерпретация задач линейного программирования

z c1 x1 c2 x2 min(max)
z (c1, c2 )
a11x1 a12 x2 b1
a x a x b
21 1 22 2
2
..........
..........
........
am1 x1 am 2 x2 bm
x1 , x2 0

5.

Различные виды ОДЗ:
1) X
2)
2
X2
X1
3)
X1
4)
5)
X
2
X2
X2
X*
X1
X1
X1

6.

c1 x1 c2 x2 const -
семейство прямых – линии уровня
целевой функции. Линии уровня в пространстве параллельны.
X2
k2
k1
k2
……
kn
X1
(градиент) f = grad(f) – вектор из частных производных =
f f
,
, ... .
x1 x2
Градиент всегда показывает направление возрастания
функции. Вектор градиент функции в точке всегда
перпендикулярен касательной.

7. Геометрический способ решения ЗЛП

2 случая:
n=2,m – любое
n - m=2
1) n=2,m – любое
z 3x1 5x2 min, max .
2 x1 4 x2 8
2 x1 6 x2 12
x 10
1

8.

2)n - m=2
3 x1 4 x2 5 x3 4 x4 min(max) В системе ограничений надо
x1 3 x3 2 x4 10
x2 5 x3 6 x4 6
x1 , x2 , x3 , x4 0
выделить исходный базис.
1 0 3 2 10
0 1 5 6 6
x1 10 3x3 2 x4 0
x 2 6 5 x3 6 x 4 0
3x3 2 x4 10
5x3 6 x4 6
x3 , x 4 0
3(10 3x3 2 x4 ) 4(6 5x3 6 x4 ) 5x3 4 x4 min

9.

Свойства решений ЗЛП
Теорема 1 ОДЗ ЗЛП выпукла.
Теорема 2 Целевая функция ЗЛП достигает своего
минимального (максимального) значения в угловой точке
многогранника решений. Если целевая функция достигает
своего экстремального значения более чем в одной угловой
точке многогранника решений, то она достигает того же
значения в любой линейной выпуклой комбинации этих
угловых точек.