Сайт студентов математиков для студентов математиков!
Главная Учебные материалы по математике Геометрическая интерпретация цф

Геометрическая интерпретация цф

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

max(min)F=c1x1+c2x2, (1)

ai1x1+ai2x2{<,=,>}bi, i=1,m (2)

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

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

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

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

Рассмотрим задачу ЛП с 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 нулевая оценка соот-я СП, то задача ЛП имеет бескон-е мн-во опт-х планов.

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

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

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

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

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

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

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

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

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

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

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

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

Х0=(0, 0, 0, … , 0, b1, b2, … , bm)

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

maxF=∆0 — ∑∆jxj

xi+∑αijxj = bi, i=1;m

xj≥ 0, j=1;m

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

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

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

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

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

Хi +Z2ijXj=Bi, i=1,m

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

Xo=(B1, B2, … Bm, 0, … 0) ; U0= F(X0

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

Если есть j0 , uj<0, то Аj0 – разреш-й столбец, Хj0- перспект. Перем-я, Xi0 – неперсп. Перем., 2i0 j0 – разреш-ий эл-т.

Наим-ее симпл-ое отнош-е: Q= min(Bi / 2ij0) = Bi0 / 2i0 j0 = Xj0

Xj0 введем в базис, Xi0 выведем из базиса.

F(X1) = u0 – uj0Q=> F(X1) > F(Xo)

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

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

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

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

max F=c1x1+c2x2+…+cnxn

а11 х1 +а12х2+…+а1nхn≤ b1

а21х1+а22х2+…+а2nхn≤ b2

……..

am1х1+аm2х2+…+аmnхn≤ bm

Xj 0 j=1.n1

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

min =b1y1+b2y2+…+bmym

а11y1+а21y2+…+аm1ym≥ c1

а21y1+а22 y2+…+а2nyn≥ c2

……………/

a1ny1+а2ny2+…+аmnyn= cn/ ;yi 0 ;i=1,m1; yi-любого знака

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

22.Теория двойст. Эк сдерж

Рассм пару симм-ых двойств задач:

Max F = ,(1)

Теорема: для любых допуст планов Х=(х1,х2…….хn) и У=(у1,у2,…..уm) прям и двойств задач справедливо нерав-во F(x) (y) т. е.

(7)

Доказ: учитывая неравенства 2 и 5, получаем:

F(x)==

Эк. содерж: Для любого допуст плана произв-ва Х и любого допуст-го вектора оценок рес-ов У общсозданная стоим-ть не превосходит сумм оценке рес-сов.

23 Критерий оптим-ти Канторовича

Теорема. Если для некот допус-ых планов Х* и У* пары дв-ных задач выполняется рав-во F(X*)=α(Y*),то Х* и У*- оптим-ые планы соотв-но. Доказ-во: согласно осн-му нер-ву теорем дв-ти для любого допус-го плана Х прям задачи и любого допуст плана У* дв-ной задачи выпол-ся нер-во F(X)≤ φ (Y*),но по условию теоремы F(X*)= φ (Y*).В силу транзитивности отнош«≤» и (=) имеем F(X)≤F(X*),но т. к. Х-произв-ый допуст план, то тогда F(X*)=maxF. Значит, Х*-оптим. план прям задачи. Аналогично доказ-ся, что У* явл-ся оптим для дв-ной задачи. Эк. содержание: план произв-ва Х* и вектор оценок рес-ов У* явл-ся оптим тогда, когда цена всей произве-ой продукции и сумм оценка рес-ов совпадает.

24. Перв теорема двойств и ее эк содерж. Теорема: Если 1 из пары двойст задач имеет оптим реш, то другая имеет оптим решение, причем экстрем знач ЦФ совпад: F (X*)=φ(Y*). Если одна из пары дв-х задач неразреш вследствие неогранич-ти ЦФ на множ. доп-х реш, то система огранич другой задачи противоречива.

Док-во:

махF =c1x1+c2x2+…+cnxn

a11x1+a12 x2+…+a1nxn ≤ b1+ xn+1 am1x1+am2x2+…amnxn≤ b +xn+m

xj≥0, j=1,n

minφ= b1y1+ b2y2+…+ bmym

a11y1+a21 y2+…+am1ym ≥c1 — ym+1

a1ny1+a2ny2+…amnyn≥cm — yn+m

yi≥0, i=1,m

Введ дополн-х неотриц-х перем хn+1 >=0,i=1,m прям задачу сведем к кононич-ой форме записи. Аналог-о введ дополн-х неотриц-х перем ym+j >=0,j=1,n, двойств задачу также можно свести к конон-му виду. Соответствие м. перем. дв-х задач: x1 x2 …xn — ym+1, ym+2,…, ym+n-СП, xn+1, xn+2,…, xn+M — y1, y2,…,ym – БП. Реш двойств задачи нах. в индексной строке посл. симпл. табл, содер. оптим. план прям задачи. Эк содерж: если разреш задача опред-ия оптим-го плана максим-го выпуск прод-ии, то разр-ма и задача опр-ия оценок ресурсов. Причем цена пр-ва прод-ии и сумм-ая оценка сов-т.

26. теорема об оценках.Теорема: двойств-е оценки показ-ют приращение ЦФ, вызванное измен-ем св. члена соотв. ограни. ∂F(X*)/∂bi=y*, i=1,m. (1). Эк. содерж-е: для этого в выраж-ии (1) дифференциалы заменим приращениями, т. е. ∂bi≈∆bi, ∂z(x*)≈∆z(x*). Получим ∆z(x*)=уi*∆bi; при ∆bi=1 имеем ∆z(x*)≈yi*. Отсюда двойств оценка числ-но равна измен-ю ЦФ при измен-ии соотв-го рес-са на ед-цу. Двойств оценки уi часто наз-ют скрытыми, теневыми или маргинальными оценками рес-сов.

25. теор о недоп-ей нежесткости и ее эк сод-ие. Теорема: для того, чтобы планы Х*, У* пары двойст-х задач были оптим-ми необх и достат вып-ие след-х усл-ий: хj*(∑аijyi*- сj)=0, j=1,n (1), yi*(∑аijxi*- bi)=0, i=1,m (2). Док-во: необходть махF =∑cjxj, ∑аijxi*= bi, i=1,m, xj≥0, j=1,n.(3) minφ= ∑biyi ∑аijyi* ≥сj, j=1,n yi≥0, i=1,m. F (X*)=φ(Y*)т. е∑cjxj,* = ∑biyi *(4). Подставим в 4 bi из 3: ∑cjxj,* =(∑аijxi*) yi*= ∑хj*∑аijyi*→ ∑хj*(∑аijyi*- сj)=0 (5). Т. к хj*≥0, и ∑аijyi*- сj ≥0, j=1,n. След-но из рав-ва 5 след-т условие 1, усл 2 док-ся аналогично. Достат-ть: ∑хj*(∑аijyi*- сj)= ∑хj*∑аijyi*-∑cjxj,*= ∑yi*∑аijxi* — ∑cjxj,*= ∑biyi *- ∑cjxj,*→ F (X*)=φ(Y*). Эк содерж: Двойствоценки могут служ мерой дефицитности ресурсов (ДР).ДР, т. е ресурс по опт-му плану пр-ва исп-ся полностью имеет полож-ю оценку, а избыт-й имеет нулевую оценку.

27. Постановка ТЗ по критерию стоимости.

Пусть имеется mпост-вок А1, А2, А3,…, Аm, у кот сосредоточен груз в кол-ве aii=1,m. Груз необход доставить n потр-лям В1, В2,…,Вn, потребность в грузе кот равна соотв-но bj, j=1,n. Известны тарифы сij, i=1,m; j=1,n, т. е. стоим-ть перевозки ед груза от i-ого пост-ка к j-ому потр-лю. Треб-ся сост-ть по ан перевоза груза от пост. к потреб-лю, при кот-м сумм трансп затраты будут миним. .x*= [xij]mxn. Сост. ЭММ данной задачи. Цель – миним-ть общ затраты на реализ плана перевоза, кот можно предст-ть след-щей ф-цией: minF= c11x11 + c12x12+…+c1nx1n + c21x21 + c22x22 + c2nx2n + cm1xm1 + cm2xm2 +…+ cmnxmn = ∑(m иi=1)∑(nи j=1)сijxij(1) Неизвестные xijдолжны удовл-ть огран-ям по запасам, огр-ям по потребн-тям и усл-ям неотрицат-ти. Посл-ее искл-ют обратные перевозки.

∑ (n, j=1) xij= ai, i=1,m(2) огранич по запасам

∑(m, i=1) xij=bj, j=1,n(3) -\- по потр-тям

xij≥0, i=1,m; j=1,n (4) 1-4 ЭММТЗ. Матем-ки ТЗ ставится след. обр.: даны система ограничений 2,3 при усл-иинеотриц-ти 4. Треб-ся среди множ-ва реш 2,3 найти такое неотриц. реш, при кот-м лин-я ф-ция 1 примет min знач.

28.Трансп-ная табл. Теорема о сущ-нии допуст плана.

Для реш усл ТЗ запис-ют в распр-нуютабл-цу, кот. иногда назыа табл. или матричной моделью ТЗ.

Bj

b1

b2

bn

a1

c11

x11

c12

x12

c1n

x1n

a2

c21

x21

c22

x22

c2n

x2n

am

cm1

xm1

cm2

xm2

cmn

xmn

Теорема о сущ-нии допуст плана:

Для того, чтобы ТЗ имела допуст планы, необх. И достат-но выполн рав-в: ∑ai=∑bj (там где сумм m, i=1 иn, j=1)(5) Доказ-во. Необход-сть:Докажем, что для допуст плана вып-ется рав-во (5), т. к. план допуст., то по опред-ю он удовл. осн приемлемым огран-ям задачи: ∑xij= ai, i=1,m (там где сумма n, j=1), а отсюда видно∑xij=bj, j=1,n (там где сумма m, i=1) Все элементы xij суммир. как по строкам, так и по столбцам, однако, от перестановки мест слагаемых ∑ не меняется, поэтому: ∑ai=∑bi (там где суммы: m, i=1; n, j=1). Дост-сть:Пусть выполн усл (5). Док-жем, что всегда имеется дополнит план. Обозн. ∑ai=∑bj=A. Переменные xij выразим через данные задачи след. обр.: xij=aibi/A, i=1,m; j=1,n. (6) Докажем, что (6) сост. допуст. план, т.к. ai≥0, bj≥0, то A>0, поэтому xij≥0. Набор чисел (6) будет сост. доп. план, если он будет удовлетв. Огр-ям 2,3. Просуммируем (6) по индексу j, и получим, что ∑ (n, j=1) xij= ∑ (m, i=1)*aibj/A, j=1,m = ai/A *∑(n, j=1) bj= ai/A *A= ai, i=1,m. Аналогично можно просумм 6 по индексу i, тогда получим вып-е 3. Получим, что 6удет огр-ям 2-4. Значит и явл. дополн планом.

29. Модель ТЗ – закрытая, если сумм объем груза у поставщиков=сумм. спросу потр-лей

(∑ai=∑bj). В данном случае груз полностью развозится поставщиками и все потребности потр-лей удовл. В противном случае модель ТЗ – открытая(ОМ), т. е. выполн-ся одно из усл: ∑ai>∑bi или ∑ai<∑bi. В случае ОМ либо все потреб-ти удовл, но у некот поставщиков остаются излишки груза (а), либо наоборот (б). Согласно теореме о существ. ДП для разрешимости ТЗ с ОМ ее необходимо преобразовать в ЗМ. При (а) вводится фиктивный потр-ль Bn+1, потр-ть в грузе у него Bn+1=∑ai-∑bj, при (б) вводится фиктивный поставщик, запас груза у него Am+1=∑bj-∑ai. При этом тарифы фектив. потр-ля (пост-ка) = 0.

36.ТЗ с макс-ей ЦФ

1.Нач. опор. план строится методом max тарифа

2.план перевозок – оптим-ый, кот-ым соотв-ет своб. клетки с оценками <=0

3.выбор перспект-ой клетки, кот-ый подлежит заполн-ю, должен произв-ся по полож. оценке

30. Теорема о ранге матрицы: ранг матрицы системы ограничительных уравнений ТЗ ∑nj=1 xij=ai, ∑mi=1 xij=bj, xij≥0 на единицу меньше числа уравнений (rang A= m+n-1).

Прикладное значение теоремы о ранге матрицы: кол-во занятых опорным планом клеток должно быть =m+n-1. Опорным решение ТЗ будет тогда и только тогда, когда из занятых m+n-1 клеток нельзя образовать цикл.

31. Правило «северо-западного угла»

Груз распредел. с загрузки левой верхней, условно назыв-й северо-зап., Если а1>b1, то х11=b и первый потреб-ль будет полностью удовл. В дальн первый столбец табл в расчет не приним, в нем перем xi1=0(i=). Двигаясь вправо по перв строке табл, заносим в кл-ку (1;2) меньш из чисел a1 –b1,b2, т. е. х12=min(a1 –b1,b2). Если a1 –b1<b2, то х12=a1 –b1и запасы перв пост-ка исчерп, перв строка табл в дальн в расчет не приним. Если а1<b1, то х11=a1и запас перв пост-ка будет исчерп. В дальн перв строка табл в расчет не приним, в нем перем x1j=0(j=). Двиг вниз по перв столбцу табл, заносим в кл-ку (2;1) меньш из чисел a2,b1–a1, т. е. х21=min(a2,b1–a1). Если b1–a1<a2, тох21=b1–a1 перв потреб-ль будет полн удовл, перв столбец табл в дальн в расчет не приним. Далее аналог. В проц заполн табл могут быть одновр исключ строка и столбец. Так бывает, когда полн исчерп запас груза и полн удовл спрос (вырожд-ная задача). В этом случ в св клетке надо запис число 0 – «нуль-загр-ку», усл счит такую клетку занят.

32.Прав «миним эл-та» (наим стоим»)

Просматр тарифы в распред-ной табл и в перв очередь заполн-ся клетка с миним знач тарифа. При этом в клетку запис-ся макс возмож знач поставки. Затем из рассмотрения исключ строку, соотв пост-ку, запасы которого полностью израсходованы, или столбец, соответствующий потребителю, спрос кот полн удовл. После этого из остав-ся клеток табл снова выбирают клетку с наим тарифом. Процесс распред закан-ся, когда все запасы пост-ков исчерп, а спрос потреб-ей полн удовл. В рез-те получ опорн план, кот должен содерж m=n-1клеток.

33. Теор о потенц. Алг теор

План ТЗ Х* явл. Оптим-м, если ему соотв-т система из m+n чисел Ui и Vj, кот. удовл-т след. Усл-м: 1) Ui+Vj=Cij, X*ij≠0; 2) ∆ij=cij-(Ui+Vj)≥0, X*ij=0 Док-во: ТЗ можно рассматр-ть как двойств. задачу к некот. исх. задачи, реш-ой на max. Каждому i-му огранич-ю ТЗ в исх. задаче соотв-т перемен. Ui, i=1,m, а j-му огранич-ю x1j+x2j+…+xmj=bj перем. Vj, j=1,n. Тогда задача имеет вид: maxφ=+, Ui+Vj≤Cij i=1,m, j=1,n Обозн. ч/з X*,Y*(Ui, Vj)-ОП двойств. исх. з-чи. На основ-ии 1-й теор. двойственности равенство: minF=maxφ. А на основании 2-й теор. двойств. выполн. усл.: 1)Ui+Vj=Cij, xij>0; 2)Ui+Vj≤Cij, xij=0, i=1,m j=1,n Из теор. след., что для ОП ТЗ необх. выполн-е усл-й: 1)кажд. занятой кл-ке в распред. табл. соотв. ∑ потенциалов, ровная тарифу этой клетки; 2)кажд. своб. кл-ке соотв-т ∑ потенц-в, не превыш-я тарифа этой кл-ке. Эк-ки оценка показ-т на сколько ден. ед. уменьш. трансп. издержки от загрузки данной кл-ки ед. груза. Алгоритм реш. ТЗ мет. потенциалов. 1)Усл. ТЗ записать в форме распред-й табл., но снач. провер. закр. или откр. модель ТЗ. 2) по 1-му из правил строим ОП. 3)Опред-м пот-лы поставщ-в и потреб-й, для этого реш-ся сист. ур-ний Ui+Vj=Cij для занятых кл-к. 4) Опред-ем оценки своб. кл-к ∆ij>0, то получим ОП единствен-й, если хотя бы 1 из оценок ∆ij=0, то имеем бесчислен. мн-во оптим. пл-в.