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

n=2 a1x1+a2x2<=b (n-кол-во переменных , m число неравенств )

Из математики знаем что геометрическим образом уравнение а1х1+а2х2=b – прямая на плоскости х1 х2 Прямая разбивает плоскость на две полуплоскости . а1х1+а2х2<=b и >= , т.е. одно из плоскостей является решением. Чтобы определить какая четверть является решением данного неравенства нужно взять любую точку M и подставить в данное неравенство. И если не равенство удовлетворяется, то точка эта принадлежит той полуплоскости в которая является решением . И наоборот.

Геометрическая интерпретация системы линейны неравенств.

n =2 . a1x1+a1x2<=b1 ГИСЛН – является пересечение всех полуплоскостей соответству

a2x1+a2x2<=b2 ющих каждому неравенству системы , таким образом нашли ОДР.

am1x1+am2x2<=bm

Возможные случаи ОДР.

1. ОДР является точка.

2. ОДР выпуклый многоугольник.

3. ОДР выпуклая многоугольная область.

4. ОДР – пустая область

Графический метод .

ГМ состоит из двух этапов.

1. ОДР.

2. Среди всех решений необходимо найти такое решение при котором Z достигает своего либо max или min.

Grad показывает наискорейшее возрастание функции. (С – коэффициент) (линии уровня)

Возможные случаи

1. задача имеет единственное решение.

2. Задача имеет – бесконечно много решений.

3. Задача не имеет решений а) нет ОДР б) в случаи когда zmax - ф-ия не ограниченной сверху линией уровня и наоборот.

Графический метод можно применять если имеется только две переменные или задача может быть приведена с помощью эквивалентных преобразований к задаче с двумя переменными.

Опорный план. Свойства допустимых планов.

1. Выпуклая линейная комбинация точек . х1 х2 …хk сумма вида α1х1+ α2х2+ ...+ αkxk , где αi =1 (αi>=0 αi – коэффициент линейной комбинации).

2. Выпуклым множеством называется такое множество т. Д на плоскости , когда вместе с любыми двумя точками Х1є Д ; Х2 є Д принадлежащим множеству Д. Ему принадлежит и их выпуклая Л.К. х=tx1+(1-t)x2 є Д 0<=t<=1

3. Крайняя точка – т.Х выпуклого множества называется крайней если она не может быть представлена в виде выпуклой Л.К. любых двух точек этого множества (n=2)

Опорное решение – это допустимое базисное решение имеющая не более чем m положительных элементов , и причем векторы столбца матрицы соответственно положительны координатам вектора линейны независимы.

Свойства допустимых планов.

Теорема №1

Множество допустимых планов З.Л.П. выпукла если оно не пусто.

Дано: Д- не является пустым множеством – ОДР

Доказать Ж Д- выпуклое множество.

Док-во :

Х1 єД; Х2 єД,то оно удовлетворяет системе ограничений в З.Л.П. Z=cx->max Ax=b X>=0

Ax1=b 0<=t<=1

Ax2=b (1-t) => tAx1+(1-t)Ax2=bt+b(1-t) = A[tx1+(1-t)x2]=b

t>=0

x1; x2>=0 => x>=0

1-t>=0

Ax=b X- решение задачи.

Х = tx1+(1-t)x2 0<=t<=1, согласно опр. Имеем выпуклое множество – Д, т.к. с любыми двумя точками ему принадлежит и их выпуклая Л.К.

Теорема № 2

Если целевая функция имеет максимум на выпуклом многограннике решений, то это максимум достигается в вершине многогранника..

Дано: Zmax->X₀ Док-ть X_0- вершина.

Zmax=C X₀

Док-во: Дан многогранник. А,В,С,Д,Е – вершины. (Док-во проведем от противного)

X₀ – не вершина , тогда согласно опр. Крайней точки , X₀ – не крайняя точка , и может быть представлена в виде выпуклой Л.К. точек хi є ОДР

C X₀>Cxi (т.к. С X₀ ->max)

X₀ = αiXi αi=1 αi>=0

Найдем значение функции Z=C X₀=C αiXi= αiCXi< αiCX₀=CX₀ αi=CX₀

В каждом слагаемом сменим Xi на Х₀

СХ₀<CX₀ – противоречие.

Теорема №3

Об альтернативном оптимуме.

Если целвевая функция достигает своего оптимального значения в нескольких вершинах (т)х1 х2 хk , то она достигает оптимального значения в их выпуклой линейной комбинации.

Дано : Док-ть: х= αiXi

Xi , i:=1,k αi=1 αi>=0 CX=d

Zmax=C{i=d

Док-во

Найдем Z=СХ=C αiXi= αiCXi= αid=d αi=d

Теорема № 4

Вектор Х является опорным решением тогда и только тогда , если он является вершиной многогранника.

Если переменных n>3 то говорят гиперплоскость, положение точек в т – мерном пространстве.