Wyk. 4.pdf

Programowaniedyskretne-metodapodzia“uiogranicze«

De nicja1.Niechdanybƒdziesko«czonyzbi ó rGorazfunkcjaf:G!R.Problem:

znale„¢x ? 2Gtaki,»ef(x ? )=max x 2 G f(x)nazywamyzagadnieniemprogramowa-

niadyskretnego.

Teoretycznierozwi¡zaniezadaniaprogramowaniadyskretnegojesttrywialne,bo

zbi ó rGjestsko«czony.Rozwi¡zywaniepraktycznychproblem ó wjestjednakbardzo

trudne,gdy»zwyklezbi ó rGsk“adasiƒzbardzodu»ejilo–cielement ó w.

Zauwa»my,»e

Stwierdzenie1.Ka»dezagadnienieprogramowaniadyskretnegomo»nasprowadzi¢do

problemuPLC.

Dow ó d.Dow ó dprzeprowadzonynawyk“adzie.

SprowadzanieproblemuprogramowaniadyskretnegodoproblemuPLC,czyliprob-

lemu,kt ó ryumiemyrozwi¡za¢jestjedn¡zmetodrozwi¡zywaniazagadnie«programowa-

niadyskretnego.Opr ó cztegopodej–ciastosujesiƒmetodyspecjalne,dostosowane

dokonkretnegoproblemu.Jednymznajlepszychprzyk“ad ó wwy»szo–cistosowania

specjalnychmetodprogramowaniadyskretnegonadrozwi¡zaniemodpowiadajacychim

problem ó wPLCjestproblemkomiwoja»era.Dwaznanesposobysprowadzeniatego

problemudoproblemuPLCprowadz¡doproblemuzdu»¡ilo–ci¡warunk ó w,kt ó rych

rozwi¡zaniejestbardzo»mudne.Zdrugiejstrony,dlaproblemukomiwoja»eraistnieje

specjalnametodaopracowanaprzezLittle’aiinnych.Jesttonajefektywniejszametoda

podzia“uiogranicze«.

Ideametodypodzia“uiogranicze«

Metodapodzia“uiogranicze«poleganabezpo–rednimlubpo–rdenimbadaniuwszys-

tkichelement ó wzbioruG.Wpraktyceomawianametodapozwalanabadaniewiƒk-

szo–cielement ó wzbioruGwspos ó bpo–redni.Przystososowaniumetodypodzia“ui

ogranicze«zbi ó rGdzielisiƒnacorazmniejszepodzbiory.

Oznaczenia:2 G -rodzinawszystkichpodzbior ó wzbioruG,za–Bpodrodzinarodziny

2 G zawieraj¡cawszystkiemo»liwepodzbiory,jakiemo»nautworzy¢metod¡podzia“ui

ogranicze«.

Po–redniebadaniewieluelement ó wzbioruGjestmo»liwedziƒkifunkcjiograniczaj¡cej.

De nicja2.Funkcjƒ':2 G !Rnazywamyfunkcj¡ograniczaj¡c¡,je–lispe“nione

s¡warunki:

i)G 2 G 1 G)'(G 2 )'(G 1 );

ii)x2G)'(fxg)=f(x).

Zpowy»szejde nicjiotrzymujemynatychmiastowy

Wniosek1.Je»eli':2 G !Rjestfunkcj¡ograniczajac¡,to

i)x2G 1 G)f(x)'(G 1 ).

ii)x2G 2 G 1 G)f(x)'(G 2 )'(G 1 ).

Dow ó d.Dow ó dwniosku-¢wiczenie.

Uwaga1.Warunkizawartewde nicjifunkcjiograniczaj¡cejnieokre–laj¡wspos ó b

jednoznacznyfunkcji'.Przywyborzekonkretnejfunkcjiograniczajacejnale»ybra¢

poduwagƒdwakryteria:“atwo–¢wyznaczeniajejwarto–ciidok“adno–¢,zjak¡warto–ci

funkcji'szacuj¡warto–cifunkcjif.Drugiekryteriumoznacza,»ewarto–cifunkcji'

powinnyby¢jaknajmniejsze.Idea“emby“abyfunkcja'ow“asno–ci:

G 1 G)'(G 1 )=max

x 2 G 1 f(x):

Zwyklekryteriapowy»szedzia“aj¡wprzeciwnychkierunkach.Sukcesmetodypodzi-

a“uiogranicze«poleganatym,czyudajesiƒosi¡gn¡¢w“a–ciwykompromispomiƒdzy

powy»szymiwarunkami.Naog ó “funkcjƒograniczaj¡c¡okre–lasiƒjakowarto–¢maksy-

maln¡funkcjifnapewnymzbiorzeK 1 zawierajacymzbi ó rG 1 .Przyczymzbi ó rK 1

jesttakdobrany,aby“atwowyznacza“osiƒmaksimumfunkcjifnaK 1 .

Wponi»szymog ó lnymopisiemetodyrozwi¡zywaniaproblemuprogramowaniadyskret-

negoniepodajemypostacifunkcjiograniczaj¡cejorazregu“ypodzia“u,gdy»postaci

tychfunkcjizale»¡odspecy kikonkretnegozagadnieniaprogramowaniadyskretnego.

Opismetodypodzia“uiogranicze«

Metodapodzia“uiogranicze«jesttometodaiteracyjna.Przedpostƒpowaniemitera-

cyjnymzak“adamy,»eB 1 =fGg.Je–liG=;,toprzyjmujemy,»e'(G)=1.W

przeciwymprzypadkuznajdujemysko«czon¡warto–¢'(G).Przyjmijmy,»ewk-tejit-

eracji(k=1;2;:::)znanajestsko«czonarodzinaB k =fQ 1 ;Q 2 ;:::;Q n k gpodzbior ó w

1.WyznaczamyQ2D k takie,»e'(Q)=max Q 2 D k '(Q).Je–li'(Q)=1,to

problemmax x 2 G f(x)jestsprzeczny.Je–li'(Q)>1,toprzechodzimydo

punktu2.

2.Badamy,czy Q jestzbioremjednoelementowym.Je»elimo»n a wprostyspos ó b

stwierdzi¢,»eQjestzbioremelementowym,toelementfx ? g=Qjestrozwi¡zaniem

optymalnymmax x 2 G f(x).Wprzeciwnymprzypadkuprzechodzimydopunktu

3.Je–limo»nawprostyspos ó bwyznaczy¢elementbx2Qtaki,»ef(bx)='(Q),to

bxjestrozwi¡zaniemoptymalnymproblemumax x 2 G f(x).Wprzeciwnymprzy-

padkuprzechodzimydopunktu4.

4. Zb i ó rQdzielimyna po dzbiory(zwykleroz“¡ cz ne)Q 1 ;Q 2 ;:::;Q m k ,awiƒc S m k

5.Przyjmujemy:B k+1 =B k [fQ 1 ;:::;Q m k gnfQgiwracamydopunktu1.

zbioruGtaka,»e S n k

i=1 Q i =Gorazdlaka»degopodzbioruQ i ,i=1;:::;n k znanajest

warto–¢funkcji'(Q i ).k-t¡mo»nawyznaczy¢nastƒpuj¡co:

i=1 Q i =

Q.Wyzna cza my'(Q i ),i=:::;m k .Je–liQ i jestzbiorempustym,topr zy jmu-

jemy,»e'(Q i )=1.Wprzeciwnymwypadkuwyznaczamywarto–¢'(Q i ).

Udowodnimy,»eelementx ? wyznaczonyw2.jestrozwi¡zaniemoptymalnymmax x 2 G f(x).

Lemat1.Sumamnogo–ciowazbior ó wrodzinyB k ,k=1;2;:::jestr ó wnaG.

Dow ó d.Dow ó dprzeprowadzonynawyk“adzie.

Twierdzenie1.Elementx ? wyznaczonywpunkcie2jestrozwi¡zaniemoptymalnym

problemumax x 2 G f(x).

Dow ó d.Dow ó dprzeprowadzonynawyk“adzie.

Nakoniecudowodnimytwierdzenieorzekaj¡ceosprzeczno–ciproblemumax x 2 G f(x).

Twierdzenie2.Je»elidlazbioruQwyznaczonegowpunkcie1zachodzi'(Q)=1,

tonieistniejerozwi¡zaniedopuszczalnezagadnieniamax x 2 G f(x).

Dow ó d.Dow ó dprzeprowadzonynawyk“adzie.

Metodapodzia“uiogranicze«dlaPLC

Przypomnijmy,»eczystyproblemprogramowanialiniowegowliczbachca“kowitycho

zmiennejx2R

,tozadaniepostaci

> > > > > > <

cx!max

przyograniczeniach

Ax=b;

x0;

x j 2Zdlaj=1;:::;n:

> > > > > > :

(PLC)

Zak“adamy,»eA=[a ij ],a ij 2Q,b=[b 1 ;:::;b m ] T 2Q m ,ac=[c 1 ;:::;c n ],c j 2R,

i=1;:::;m,j=1;:::;n.

Uwaga2.Gdybya ij lubb i nienale»a“ydoQ,toproblemPLCczƒstoby“obyproble-

memsprzecznym.

Oznaczenia:D C ,D-zbioryrozwi¡za«dopuszczalnychodpowiedniodlaPLC,oraz

problemuPLpowsta“egozPLCprzezpominiƒciewarunk ó wnaca“kowito–¢zmiennych,

D C opt ,D opt -zbioryrozwi¡za«optymalnychodpowiedniodlaPLC,PL.

Wykorzystuj¡czwi¡zkimiƒdzyproblemamiPLCiPLotrzymujemy

Stwierdzenie2. a)D=; )D C =;.

b)D opt =; ^D6=; )D C opt =;.

x 2 D C f(x)[max

x 2 D f(x)],gdzie[a]oznaczaca“o–¢liczbya.

d)D opt \D C 6=; )D C opt =D opt \D C .

e)D opt 6=; ^D C 6=; ^D opt \D C =; )max

x 2 D C f(x)<max

x 2 D f(x).

c)max

Dow ó d.Dow ó dstwierdzenia-¢wiczenie.

Przypomnijmy,»ewdowolnymPL,gdymaksymalizujemyfunkcjƒcelumamytrzy

mo»liwo–ci:zagadnieniejestsprzecznealbofunkcjacelujestnieograniczonazg ó ry

nazbiorzerozwi¡za«dopuszczalnychalboproblemposiadarozwi¡zanieoptymalne.Z

powy»szegostwierdzeniaorazw“asno–cirozwi¡za«PLwynika,»eje»elizagadnieniePL

powsta“ezPLCpoprzezopuszczeniewarunk ó woca“kowito–cijestsprzeczne,tozagad-

nieniePLCjestr ó wnie»sprzeczne(waruneka).Je»elifunkcjaceluwodpowiadaj¡cym

PLjestnieograniczonazg ó rynazbiorzerozwi¡za«dopuszczalnych(warunekb),tojest

onate»takanazbiorzerozwi¡za«dopuszczlanychdlaPLC.Zatempozosta“orozwa»y¢

przypadekkiedyzagadnieniePLodpowiadajacePLCmarozwi¡zanieoptymalne.

Wmetodziepodzia“uiogranicze«dlaPLC,wykorzystamynastƒpuj¡cetwierdzenie

Twierdzenie3.Je»eliD 1 ;:::;D k s¡podzbioramizbioruDtakimi,»eD C D 1 [D 2 [

:::[D k D,to

x 2 D C f(x)[maxfmax

x 2 D 1 f(x);:::;max

x 2 D k f(x)g];

gdzie[a]-oznaczaca“o–¢za.

Je–liponadto[max x 2 D s f(x)]<f(x)dlapewnegos2 f1;:::;kgix2D C ,toD C opt \

D s =;.

Dow ó d.Dow ó dtwierdzenia-¢wiczenie.

x 2 D k f(x),gdzieD k jest

zbioremdopuszczalnymtegozadania.Wtymwypadkufunkcjaograniczaj¡cajest

postaci'(B k )=max x 2 D k f(x),przyczymw»adnymzD k niejestbranypoduwagƒ

warunekca“kowito–cizmiennych,aB k =D C \D k .Schematblokowymetodypodzia“u

iogranicze«mo»naznale„¢w Zbiorzezada«zprogramowaniamatematycznego pod

redakcj¡Nykowskiego.

Uwaga3.W s chemacieblokowymblok0opisujeczynno–ciprzygotowawczedooblicze«.

Je»eliznamyx2D C ,tojakodolneograniczenieoptymalnejwarto–ci f c przyjmujemy

f(x)orazD C 0 =fxg,wprzeciwnymwypadku- f c =1,D C 0 =;.

Uwaga4.Prezentowanyalgorytmpozwalawyznaczy¢pewnerozwi¡zaniaoptymalne

PLCniekonieczniewszystkie.

max

Rozwi¡zaniezadaniaPLCmetod¡podzia“uiogranicze«sprowadzasiƒdorozwi¡za-

niasko«czonejliczbyzada«programowanialiniowegoPL:Z 0 ;Z 1 ;:::;Z p .Liczbapnie

jestdanazg ó ry.Zadaniapomocniczekonstruowanes¡stopniowowtrakcieoblicze«i

wpisywanenalistƒLzada«dorozwi¡zania.ZadanieZ 0 poleganaznalezieniurozwi¡za-

niaoptymalnegox 0 zadaniaPLodpowiadaj¡cegoPLC.ZadaniaZ k ,k=1;:::;p

polegaj¡nawyznaczeniurozwi¡zaniaoptymalnegozadaniamax

De nicja3.NiechdanabƒdzieA=[a ij ]macierzkszta“tumna ij 2R,wektory

b=[b 1 ;:::;b m ] T ,b i 2R,c=[c 1 ;:::;c n ],c j 2Rorazzbi ó r; 6=J c f1;:::;ng.

Zadaniemprogramowaniazero-jedynkowegoPZJnazywamyproblempostaci:

> > > > > > > > <

cx!max

przyograniczeniach

Ax=b;

x 1 ;:::;x n 0;

x j 1;j2J c ;

x j 2Z;j2J c

> > > > > > > > :

: (PZJ)

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: