Wyk. 2.pdf

Zastosowaniaprogramowanialiniowego

Zagadnienie(problem)diety

Jednymzzastosowa«problemuprogramowanialiniowegojestproblemdiety.Szukamy

minimalnegokosztudietysk“adaj¡cejsiƒznprodukt ó wF 1 ;:::;F n ,kt ó remusz¡za-

spokoi¢minimalnedziennezapotrzebowanienamsubstancjiod»ywczychN 1 ;:::;N m .

Problemdietymaposta¢ 8

> > > <

cx !min

przyograniczeniach

Ax b;

x 0;

> > > :

gdzie

c j koszt100gram ó wj-tegoproduktuF j ; j=1;:::;n;

b i minimalnedziennezapotrzebowanie(wmiligramach)nai-t¡

substancjƒod»ywcz¡N i ; i=1;:::;m;

a ij ilo–¢miligram ó wN i substancjiod»ywczejw100gramachF j produktu;

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

x j ilo–¢gram ó wF j produktu; j=1;:::;n:

Zagadnienieplanowaniaprodukcjiikontrolizapas ó w

Dyskusjƒotymzagadnieniurozpoczniemyod

Przyk“ad1.Rozwa»mysytuacjƒproducentatowar ó w(kt ó regozapotrzebowanieza-

le»yodporyroku),kt ó rymusiokre–li¢wielko–¢produkcjina12miesiƒcy.Zapotrze-

bowanie(wjednostkachtowaru)naproduktzmieniasiƒjakwponi»szejtabeli

miesi¡czapotrzebowaniemiesi¡czapotrzebowanie

1 900 7 2000

2 1000 8 1500

3 2000 9 1200

4 3000 10 2000

5 4000 11 1800

6 3700 12 1800

Producentmusizapewni¢takpoda»,abyzaspokoi¢popyt.Poszczeg ó lnezapotrze-

bowaniamo»ezaspokoi¢produkuj¡cwymagan¡ilo–¢wci¡gumiesi¡ca,b¡d„produku-

j¡cczƒ–¢zapotrzebowania,aresztƒuzupe“nia¢zapas ó w.Opodej–ciuproducentawiem

napewno,»echceonminimalizowa¢koszt.Zak“adamy,»ekosztproducentaza-

le»yodwzrostuprodukcjiikoszt ó wmagazynowania.

Przejd„mydozbudowaniamodelumatematycznego.Producentchceopracowa¢wielko–¢

produkcjinanokres ó w,zak“adaj¡c,»eznazapotrzebowaniewka»dymzokres ó w.Za-

czynamyodokresu0,gdy»zak“adamy,»eproducentposiadawmagazyniepewn¡ilo–¢

towarus 0 zpoprzedniejprodukcji(s 0 0).Zak“adamywtymmodelu,»es 0 jestdan¡

(Uwaga:winnymsformu“owaniutegozagadnieniamo»etoby¢r ó wnie»zmienna).

Je»elis 0 =0,tooznacza,»eproducentwytwarzanowyprodukt.Wnaszymmodelu

mamy,wiƒcnastƒpuj¡cedane:

-s 0 ,(s 0 0)-zapaspocz¡tkowy;

-r t ,(r t 0)-zapotrzebowaniewokresiet,t=1;:::;n.

Wrozwa»anymzagadnieniuszukanymis¡:

-x t ,(x t 0)-ilo–¢jednostekprodukcjitowaruwokresiet,t=1;:::;n;

-s t ,(s t 0)-zapaswokresiet,t=1;:::;n.

Otrzymujemynr ó wna«

s t1 +x t s t =r t ; t=1;:::;n: (1)

Warunek(1)opisujepierwszytypogranicze«wrozwa»anymmodelu(zwi¡zanyzza-

pewnieniemzaopatrzenianadanyokres).Wpostawionymzagadnieniuinteresujenas

minimalizacjakosztumagazynowaniaiwzrostuprodukcji.Zauwa»my,»e

x t x t1 ; t=1;:::;n (x 0 :=s 0 )

opisujewzrostlubspadekprodukcjiitƒliczbƒ,jakka»d¡liczb¡mo»nazapisa¢jako

r ó »nicƒdw ó chliczbnieujemnych,czyli

x t x t1 =y t z t ; y t ;z t 0; t=1;:::;n; (2)

gdzie

-y t ,(y t 0)-wzrostprodukcjiwokresiet,t=1;:::;n;

-z t ,(z t 0)-spadekprodukcjiwokresiet,t=1;:::;n.

Napodstawieanalizykoszt ó wzlatpoprzednichproducentwiejakijestkosztwzrostu

produkcjiojednostkƒwokresiet1wstosunkudookresut.Zak“adamy,»ejestto

sta“awarto–¢(tzn.,»eniezale»yodokresu)iwynosia,a >0.Ponadto,producentzna

kosztmagazynowaniajednostkitowaru.Tenkosztr ó wnie»jeststa“yiwynosi b,b >0.

Uwaga1.Mo»nabyrozwa»a¢r ó wnie»sytuacjƒ,»ekosztmagazynowaniaiwzrostu

produkcjizale»yodokresu,ale»ebymodelpozosta“liniowywarto–ciobukoszt ó ww

danymokresiemusz¡by¢znane.

Wprezentowanymmodeluproducentchcezminimalizowa¢funkcjƒ

y t +b

s t !min:

t=1

K“ad¡c= a b >0producentchcerozwi¡za¢zagadnienie

> > > > > > > > <

y t +

s t !min

t=1

przyograniczeniach

s t1 +x t s t =r t ; t=1;:::;n;

x t x t1 y t +z t =0; t=1;:::;n;

x t ;y t ;z t ;s t 0 t=1;:::;n:

> > > > > > > > :

(3)

Uwaga2.Wproblemie(3)jest4nzmiennychi2nogranicze«.

Lemat1.Je»eliistniejerozwi¡zanieoptymalne(3),toniemo»eby¢jednocze–nie

y t >0iz t >0,t=1;:::;n,gdziey t ;z t s¡elementamirozwi¡zaniaoptymalnego.

Dow ó d.Dow ó dprzeprowadzonynawyk“adzie.

Abyrozwi¡zywa¢zagadnienie(3)metod¡sympleks,torz¡dmacierzywsp ó “czyn-

nik ó wr ó wna«ograniczaj¡cychmusiby¢r ó wnyilo–cir ó wna«.Zauwa»my,»ewtym

przypadkunogranicze«mo»nawyelimininowa¢.

> <

x t =r t +s t s t1

x t1 =r t1 +s t1 s t2

x t x t1 =y t z t

> :

) r t s t1 +s t r t1 +s t2 s t1 =y t z t

y t z t +2s t1 s t s t2 =r t r t1 ; t=1;:::;ngdzies 1 :=0;r 0 :=0:

Wtenspos ó bwyeliminowali–mynzmiennychx t ,t=1;:::;ninr ó wna«.Mamyzatem

dorozwi¡zaniazagadnieniedladanychs 0 ,r t ,t=1;:::;n

> > > > > > <

y t +

s t !min

t=1

przyograniczeniach

y t z t +2s t1 s t s t2 =r t r t1 ;

y t ;z t ;s t 0 t=1;:::;n:

;gdzies 1 :=0;r 0 :=0: (4)

> > > > > > :

Uwaga3.Zauwa»my,»e(4)jestzagadnieniemprogramowanialiniowego,dlakt ó rego

rz¡dmacierzywsp ó “czynnik ó wwynosinijestr ó wnyilo–ciogranicze«.Zmiennychw

tymzagadnieniujest3n.

Lemat2.Redukcjauk“adur ó wna«ograniczaj¡cychjestpoprawna.

Dow ó d.Dow ó dprzeprowadzonynawyk“adzie.

Uwaga4.Zmieniaj¡cza“o»eniamodelumo»emyuzyskiwa¢r ó »nemody kacjemodelu

np.:

-Producentchceponokresachzako«czy¢produkcjƒ,w ó wczaswprowadzamydo

modeludodatkow¡dan¡s n =0.Wtedyte»producentmo»echcie¢uczyni¢

zmienn¡s 0 oczywi–ciekosztmagazynowanias 0 mo»eby¢r ó »nyodkosztumag-

azynowanias t ,t=1;:::;n.

-Producentwswoimkoszciemo»euwzglƒdnia¢nietylkowzrostprodukcji,ale

r ó wnie»kosztspadkuprodukcji.W ó wczasfunkcjaceluwzagadnieniu(4)ma

posta¢

y t +b

s t +c

z t !min;

t=1

gdziec >0-kosztspadkuprodukcjiojednostkƒzokresut1wstosunkudo

okresut.Ograniczeniapozostaj¡tesame.

Zagadnienieprzep“yw ó wmiƒdzyga“ƒziowych

Przyk“ad2.Rozwa»mymodelekonomicznysk“adaj¡cysiƒztrzechpodstawowych

ga“ƒzigospodarki:kolei,hutnictwa,g ó rnictwaorazzczwartejga“ƒziobejmuj¡cejpo-

zosta“ega“ƒzieprzemys“u.Przeanalizujmyprzep“ywd ó brmiƒdzytymiga“ƒziamigospo-

darkiwci¡gujednegoroku.Analizƒprzeprowadzimywoparciuotablicƒnadk“ad ó wi

wynik ó wprodukcji(ang.input-outputanalysis).

producenci# kolejhutnictwog ó rnictwoinniproduktko«cowyprodukcja

kolej x 11 x 12 x 13 x 14 y 1 x 1

hutnictwo x 21 x 22 x 23 x 24 y 2 x 2

g ó rnictwo x 31 x 32 x 33 x 34 y 3 x 3

inni x 41 x 42 x 43 x 44 y 4 x 4

Interpretacjaelement ó wmacierzy

-x 12 -warto–¢us“ug–wiadczonychprzezkoleinarzeczhutnictwa;

-y 1 -produktko«cowykoleinarzeczodbiorc ó wko«cowych.Odbiorcamiko«-

cowymis¡,ciuczestnicygospodarki,kt ó rzykonsumuj¡bezwytwarzania(wtym

ludno–¢,eksport).

Przyjmujemynastepujaceza“o»eniawzagadnieniuprzep“yw ó wmiƒdzyga“ƒziowych

-m-ilo–¢ga“ƒzigospodarki;

-x i , x i >0,-warto–¢produkcjiglobalnejwytworzon¡przezi-t¡ga“¡„, i=

1;:::;m;

-x ij ,x ij 0,-warto–¢przep“ywud ó brzi-tejga“ƒzidoj-tejga“ƒziprzemys“u,

i;j=1;:::;m;

-y i ,y i 0,-warto–¢produktuko«cowegoi-tejga“ƒzi,i=1;:::;m.

odbiorcy!

Zak“adaj¡c,»eproduktyko«cowes¡zaspokojoneotrzymujemynastƒpuj¡cyuk“adr ó w-

na«liniowych

x i

x ij =y i ; i=1;:::;m: (5)

j=1

x j oznaczmynak“ad

i-tegoprzemys“ukoniecznydowytworzeniajednostki j-tegoproduktuinazywamy

wsp ó “czynnikaminak“ad ó wiwynik ó wprodukcji.W ó wczas(5)maposta¢

x i

a ij x j =y i ; i=1;:::;m:

j=1

como»nazapisa¢wpostacimacierzowej

(I A)X=Y ;gdzieA=[a ij ]; X=[x 1 ;:::;x m ] T ; Y=[y 1 ;:::;y m ] T :

MacierzIAnazywamymacierz¡Leontiewa.Przyza“o»eniu,»eliniowastruktura

gospodarkitj.wsp ó “czynnikinak“ad ó wiwynik ó wprodukcji,opisujedzia“alno–¢gospo-

darcz¡nietylkodlapodstawowegookresuczasu,leczr ó wnie»dlaprzysz“ychokres ó w,

mo»emywyznaczy¢wektorprodukcji X,kt ó rydajeza“o»onywektorproduktuko«-

cowegoY.Zatemog ó lnezagadnieniegospodarkinak“ad ó wiwynik ó wprodukcjipolega

naznalezieniuwektoraX,kt ó ryspe“niaograniczenia

X 0; (I A)X=Y; (6)

gdzieYjestdanym,nieujemnyminiezerowymwektoremproduktuko«cowego, Adan¡

macierz¡wsp ó “czynnik ó wnak“ad ó wiwynik ó wprodukcji.

Uwaga5.Wrozpatrywanymprzyk“adzie,wkt ó rymwektorproduktuko«cowegoY 6=

0Morgensternpokaza“,»enietylkoa ij 0,aler ó wnie»

a ij <1; j=1;:::;m:

i=1

Morgenstrenpokaza“r ó wnie»,»eje»eli P m i=1 ja ij j <1,j=1;:::;m,tomacierz

I Ajestnieosobliwa,czylir ó wnanie(I A)X=Ymadok“adniejednorozwi¡zanie

postaciX=(I A) 1 Y.

Zatemje»eliY 6=0,tozbi ó rrozwi¡za«dopuszczalnychfX 0:(I A)X=Yg

jestjednopunktowy.Jakkolwiekokre–limyfunkcjƒcelu,torozwi¡zaniemoptymalnym

jesttojednerozwi¡zaniedopuszczlane.

W1930Leontiewm ó g“zgromadzi¢niezbƒdnedaneinapisa¢macierzdla45dzia“ ó w

przemys“uzlat1919i1929.Ponadto,niezak“ada“onspe“nianiawymaga«produktu

ko«cowego,czylirozwa»a“

(I A)X Y;

Leontiewza“o»y“,»eliniowymodelgospodarkidladanegookresupodstawowegom ó g“by

by¢zastosowanydoanalizystrukturyg os p o darkiwprzysz“ychokresach.Znanedla

danegookresux i ,x ij oznaczamyprzezx i ,x ij .Przez0 a ij = x ij

Takastrukturanazywasiƒmodelemotwartym.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: