- •7.Формы записи задачи лп
- •8.Переход к канон.Ф.:
- •10.Геом. Интерпретация цф и ограничений задачи.
- •12. Геоминтерпр-ия задачи лп с несколькими переменными.
- •13Основная теорема лп
- •15. Построение начальн. Опорн. Плана
- •17.Переход к нехудшему опорному плану
- •18. Правила пересчёта
- •20.Призн.Неогр-ти цф на множ-ве планов.Геом.Интрепр.
- •21Прямая и двойственная задача
- •22.Основное неравенство теории двойственности и его экон. Содерж.
- •23.Критерий оптимальности Канторовича
- •27. Постановка тз по критерию стоимости.
- •28.Трансп-ная табл. Теорема о сущ-нии допуст плана.
- •29. Тз с закр. И откр.Моделью.
- •31. Правило «северо-западного угла»
- •32.Прав «миним эл-та» (наим стоим»)
- •33. Теор о потенц. Алг теор
- •35. Усложненные постановки тз.
- •41.Постр-е прав-го отсечения. Теорема о прав отсеч
- •42.Метод ветвей и границ.
- •43. Понят о дп. Принц оптим Беллмана
- •44. Вычисл схема реш задач методом дп
- •47. Задача оптим. Планирования вып-ка, сод-я и хран-я пр-ции и решение ее методом дин-го рогр-я
- •48. Задача замены оборуд
- •50.Метод множ Ланг-жа реш задач нп.Эк смысл множ Ланг-жа.
- •51.Градиент.Метод решения задачНп
12. Геоминтерпр-ия задачи лп с несколькими переменными.
Перейдем к геометрической интерпретации задачи ЛП с несколькими переменными.
max F = , (1)
bi, (i= ), (2)
xj 0, (j= ). (3)
Множ-во реш Х = (х1,х2,…,хn), компоненты кот удовл-ют огранич-ю- равенству ai1x1 + ai2x2 +… + ainxin = bi, (i= ), геом-ски пред-ют собой гиперплоскость n-мерного пространства. Это выпуклое множ-во.
Множ-во реш Х = (х1,х2,…,хn), компонентыты кот удовл-ют нерав--вуai1x1 + ai2x2 +… + ainxin bi, (i= ),образ полупрос-во n-мерного простр-ва, кот также явл выпуклым множ-вом.
Множ-во реш, удовл-их системе огранич задачи ЛП (2), (3) предст собой пересечение конечного числа полупространств и поэтому явл выпуклым. Теорема:Множ-ворешзадача ЛП выпукло (если оно не пусто). Множ-во реш задачи ЛП в практически важных случаях чаще всего предст-ет собой либо выпуклый многогранник, либо выпуклую многогранную область. ЦФ (1) геом-ки можно рассм как семейство паралл гиперплоскостей с1x1 + с2x2 +… + сnxn =F, каждой из кот соот етопредзнач параметра F. Вектор = (с1; с2; …;сn), перпенд-ый к гиперплоскости F=const, указ направл наискорейшего возраст функции F. С учетом сказанного, задача (1)-(3) геом-ки свод. к нахождению точки Х* = (х1*,х2*,…,хn*) многогранника, опреднерав-ми (2), (3), через кот проход гиперплоскость семейства (1), соот-щая наиб значF. Граф методом можно решить задачу ЛП с n>2 перем, если в ее канон-ой записи число неизвn и число линейно-независ векторов mсвязсоотнош-ем n-m 2.
13Основная теорема лп
Если ЗЛП имеет решение, то ЦФ достигает экстрем.знач хотя бы в одной из крайних точек многогр.решений.
Если же ЦФ достигает экстрем.знач более чем в одной крайней точке, явл-ся их выпуклой лин.комбинаций.
Док-во: Пусть Х*-допуст.реш., для кот.ЦФ достигает своего maxзначmaxF=f(X*),тогда
f(X*) (1)
Если Х*совп с одной из крайних точек, то перв часть теор док-на.
Предпол, что Х* не явл.крайнейточ, то первмногогрреш. Тогда Х* можно в виде выпуклой линейной комбин точек Х1, Х2,…,Хк:
Х*=
В силу лин-тиf(X) имеем
f(X*)= 1f(X1)+ 2f(X2)+ …+ f(Xk)
Обозн через М maxзнач ЦФ среди всех крайних точек, т.е.
M=max(f(X1), f(X2),…,f(Xk)).
f(X*) 1M+ 2M+…+ kM=MИли f(X*) M (2)
Из нер-в 1 и 2 вывод f(X*)= M
Но М-знач ЦФ в одной из крайн точек, поэтому Х*совп с одной из них.
Допуст, что f(X)достиг макс знач более чем в одн точке
f(X1)=f(X2)= …=f(Xр)=M
Х= , i 0,(i= ,
f(X)= 1f(X1)+ 2f(X2)+…+ pf(Xp)= 1M+ 2M+…+ pM=M,
т.елин ф-я Fприним макс знач в произв точке Х, явл-ся выпукл линкомбин-ей точек Х1,Х2,…,Хр, в которой ЦФ F принимает макс знач
15. Построение начальн. Опорн. Плана
Пусть з-ча ЛП представлена с мат огранич в канонич виде
Огранич-рав-во имеет предпочтит вид, если при неотриц прав части лев часть содержперемен-ю с коэф-том=1, а в остальн ограничения эта перемен-я входит с коэф-том=0
Сис-маогранич имеет предпочтительн вид, если каждогранич-рав-во имеет предпочтит вид. В этом случае легко найти опорнреш( - это базисное с положит координатами)
Для этого все СП надо принять =0, а БП = свободным членам Пусть сис-маосногранич имеет вид:
С пом-ю добавления клев частям дополн неотриц перемен-х дан сис-му можно привести к канонич виду: аijхj+ хn+i = bi, bi≥0, i=1;m
Дан сис-маимеетпредпочтит вид и следоват-но начопорн план можно записать в виде:
Х0=(0, 0, 0, … , 0, b1, b2, … , bm).
16.Признак оптим опорн плана. Симплексн таблица Люб з-чу ЛП можно свести к виду:
Max(min)F=∆0 - ∑(n,j=m+1)∆jxj
xi+∑(n,j=m+1)αijxj = bi, i=1;m
xj≥ 0, j=1;n
Для реш з-чи запис в симплексн таблицу
Посл строку наз-ют индексн строкой или строкой ЦФ. ∆0= Сбβ=F(X0) – значение ЦФ для нач опорн плана Х0; ∆j=СбAj-Cj, j=m+1;n–оценки СП
Реш з-чи:1) Если з-ча на max, то план оптимальн, если ∆j≥0, j=1;n; Док-во:т.к. F=∆0-∑(n,j=m+1) ∆jxj, ∆j≥0,j=1,n, то F достиг max знач при ∑(n,j=m+1) ∆jxj т =0.Это возможно при x(m+1)=x(m+2)=…=x(n)=0.2) Если з-ча на min, то план оптимальн, если ∆j≤0, j=1;n