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

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.Трансп-ная табл. Теорема о сущ-нии допуст плана.

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

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

Для того, чтобы ТЗ имела допуст планы, необх. И достат-но выполн рав-в: ∑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, то имеем бесчислен. мн-во оптим. пл-в.