Геометрическая интерпретация ЦФ и ограничений задачи

max(min)F=c₁x₁+c₂x₂, (1)

a_i1x₁+a_i2x₂{<,=,>}b_i, i=1,m (2)

x_j>=0, j=1,n (3)

Дадим геометрическую интерпретацию элементов этой задачи.Каждое из ограничений 2 и 3 задает на плоскости х1Ох2 некоторую полуплоскость.Полуплоскость-выпуклое множество. Каждое из ограничений задаём на плоскости.Предположим, что ОДР-многогранник. Если считать F=0, то прямая c1x1+c2x2=0 будет проходить через начало координат. Для того чтобы определить направ-ние, в кот. ЦФ возрастает(убывает) с наибол. скоростью небх-о определить частные произв. ЦФ по неизвес. параметрам:

Вектор С(С1,С2) наз. градиентом и указывает нправл-е найсорейшего возрастания ЦФ. –С(-С1,-С2) наз. антиградиентом.

Графич. метод решения задачи ЛП с двумя переменными

Рассмотрим задачу ЛП с 2-мя переменными

Каждое из ограничений задаём на плоскости.Предположим, что ОДР-многогранник. Если считать F=0, то прямая c1x1+c2x2=0 будет проходить через начало координат. Для того чтобы определить направ-ние, в кот. ЦФ возрастает(убывает) с наибол. скоростью небх-о определить частные произв. ЦФ по неизвес. параметрам:

Вектор С(С1,С2) наз. градиентом и указывает нправл-е найсорейшего возрастания ЦФ. –С(-С1,-С2) наз. антиградиентом.

Графический метод решения: 1.с учётом осн.и прямых ограничений строим ОДР 2.строим вектор градиент 3.строим прямую F=0 перпендик. С в начале координат 4.если задача реш-ся на max, то перемещаем прямую F=0 в направл-ии С до дальней точки ОДР, если на min, то пр. F=0 перемещаем до первой точки ОДР 5.находим оптимал. реш-е Х* и экстр. значение ЦФ F*

19.Теор:Если в идек-й строке после симплек-ой табл сод-щий опт план имеется хотя бы 1 нулевая оценка соот-я СП,то задача ЛП имеет бескон-е мн-во опт-х планов.

След-е:Если в индекс-й строке симпл-ой табл сод-я опти-й план все оценки СП полож-ны, то найд-й оптим-й план единст-й

Осн теорема ЛП.

Если задача ЛП имеет реш, то ЦФ достигает экстрем знач хотя бы в 1 из крайн точек многогранника решений. Если же ЦФ достиг экстрем знач более, чем в 1 крайн точке, то она достиг этого же знач в люб точке, явл-ся их выпукл лин комбинацией.

Док-во: Пусть Х* - допуст реш, в кот-м ЦФ достиг своего max. Это значит, что f(X*)=maxF

Тогда f(X*)≥f(X), Xпринадлежит ОДР (1) Если Х* совпадает с 1 из крайн точек, то 1-я часть теоремы доказана. Предпол, что Х* не явл-ся крайн точкой. Следоват-но ее можно представить в виде выпукл лин комбинации крайн точек Х₁, Х₂, … ,Х_k; Х*=∑ƛ _ix_i , ƛ_i>0, i=1;k, ∑ƛ_i =1 В силу линейности ЦФ имеем: f(X*)=ƛ₁f(X₁)+ƛ₂(X₂)+ … +ƛ_kf(X_k) (2) Обозначим через М макс значение ЦФ среди всех точек М=max(f(X₁), f(X₂), … , f(X_k)) (3) Тогда из равенства (2) с условием (3) получим: f(X*) ≤ ƛ₁M+ƛ₂M+ … ƛ_kM=M→ f(X*) ≤ M (4) Из (1) и (4) можно сделать след вывод: f(X*)=М, но М – значение ЦФ в 1 из крайн точек, значит Х* совпадает с 1 из них.

15) Построение начальнопорн плана

Пусть з-ча ЛП представлена с мат огранич в канонич виде ∑а_ijх_j =b_i , b_i ≥0, i=1;m

Огранич-рав-во имеет предпочтит вид, если при неотриц прав части лев часть содерж перемен-ю с коэф-том=1, а в остальн ограничения эта перемен-я входит с коэф-том=0

Сис-ма огранич имеет предпочтительн вид, если кажд огранич-рав-во имеет предпочтит вид. В этом случае легко найти опорн реш( - это базисное с положит координатами)

Для этого все СП надо принять =0, а БП = свободным членам Пусть сис-ма осн огранич имеет вид: ∑а_ijх_j≤b_i , b_i ≥0, i=1;m

С пом-ю добавления клев частям дополн неотриц перемен-х дан сис-му можно привести к канонич виду: ∑а_ijх_j+ х_n+i = b_i , b_i ≥0, i=1;m

Дан сис-ма имеетпредпочтит вид и следоват-но начопорн план можно записать в виде:

Х₀=(0, 0, 0, … , 0, b₁, b₂, … , b_m)

16) Признак оптим опорн плана. Симплексн таблицаЛюб з-чу ЛП можно свести к виду:

maxF=∆₀ - ∑∆_jx_j

x_i+∑α_ijx_j = b_i, i=1;m

x_j≥ 0, j=1;m

Для реш з-чи запис в симплексн таблицу

Посл строку наз-ют индексн строкой или строкой ЦФ. ∆₀= С_бβ=F(X₀) – значение ЦФ для нач опорн плана Х₀; ∆_j=С_бA_j-C_j, j=m+1;n–оценки СП

Реш з-чи:1) Если з-ча на max, то план оптимальн, если ∆_j≥0, j=1;n; 2) Если з-ча на min, то план оптимальн, если ∆_j≤0, j=1;n

17. (2- альфа, В – бета, u(U) – дельта)

Сист. Осн-х огран-й имеет вид:

Х_i +Z2_ijX_j=B_i, i=1,m

Тогда нач. опорный план:

X_o=(B₁, B₂, … B_m, 0, … 0) ; U₀= F(X₀

Если u >= 0 , то Х₀ – оптим-й

Если есть j₀ , u_j<0, то Аj_{0 –} разреш-й столбец, Хj₀- перспект. Перем-я, Xi₀ – неперсп. Перем., 2i₀ j₀ – разреш-ий эл-т.

Наим-ее симпл-ое отнош-е: Q= min(B_i / 2ij₀) = Bi₀ / 2i₀ j₀ = Xj₀

Xj₀ введем в базис, Xi₀ выведем из базиса.

F(X₁) = u₀ – uj₀Q=> F(X₁) > F(X_o)

20.Теор:Если в индеек-й строке симплек-й табл задачи ЛП на max содер-я отриц оценки,а в соот-ем столбце нет ниодного полож-о эл-та,то ЦФ на мн-ве допуст-х планов задачи неогран-на сверху.

Теор: Если в индеек-й строке симплек-й табл задачи ЛП на min содер-я полож-е оценки,а в соот-ем столбце нет ниодного полож-о эл-та,то ЦФ на мн-ве допуст-х планов задачи неогран-на снизу.

Двойст и прям зад-ча

Рассм задачу ЛП вида:

max F=c1x1+c2x2+…+cnxn

а₁₁ х₁ +а₁₂х₂+…+а_1nх_n≤ b₁

а₂₁х₁+а₂₂х₂+…+а_2nх_n≤ b₂

_……..

a_m1х₁+а_m2х₂+…+а_mnх_n≤ b_m

Xj 0 j=1.n₁

двойс к данной задаче назыв-ся задача

min =b₁y₁+b₂y₂+…+b_my_m

а₁₁y₁+а₂₁y₂+…+а_m1y_m≥ c₁

а₂₁y₁+а₂₂ y₂+…+а_2ny_n≥ c₂

_{……………/}

a_1ny₁+а_2ny₂+…+а_mny_n= c_n/ ;yi 0 ;i=1,m_1; yi-любого знака

Правила постр двойств. задачи: 1)Если в прямой задаче ЦФ на мах, то в двойств. будет на мин. И наоборот. 2)Число перем исход задачи = числу основн огранич двойств. задачи и наоборот. 3)Коэфф. При неизв в ЦФ двойств. задачи явл-ся свободн чл прям задачи и наоборот. 4)Матрица, сост-я из коэфф. при неизв в системе осн огранич прям задачи и аналогичная матрица двойств задачи получ-ся друг из д транспонированием.. 5)Если перем прям задачи , то соот-щее огранич в системе основ огранич двойств. задачи явл-ся нерав-во, а если переменная прям задачи может приним любые знач, то соотв огранич явл-ся уравнением.