predavanje_matematika_6._26.09.2012

8/19/2019 predavanje_matematika_6._26.09.2012

http://slidepdf.com/reader/full/predavanjematematika626092012 1/4

1

19. Linearno programiranje

Matematičko programiranje: linearno i nelinearnoprogramiranje

Ograničenja u obliku nejedna č ina

19.1 Jednostavni primjeri linearnog programiranja

Problem ishrane

2

Minimizirati

uz uslove (ograničenje za Ca )

(za bjelan č evine )(za vitamin A)

i

Prva j-na – f-ja cilja linearnog programa – f-ja troškovazasnovana na podacima o cijeni (nju treba minimizirati)

Tri sljedeće j-ne – ograni č enja uslovljena dnevnimpotrebama

Dodatne j-ne – uslovi nenegativnosti

0,

1262

2055

20410

6.0

21

21

21

21

21

≥

≥+

≥+

≥+

+=

x x

x x

x x

x x

x xC

3

Grafičko rješavanje

Skup mogu ć ih rješenja

Ekstremne ta č ke – napresjeku dva graničnapravca ili granične prave iose

x2=C-0.6x1

Na slici (b) – 3 linije jednakih troškova

Optimalno rješenje (3,1)

Učinak promjena cijena

–P1 /P2 – nagib linija jednakih troškova 4

Problem proizvodnje

Maksimizirati

uz uslove (ograničenje rezanja )

(ograničenje miješanja )

(ograničenje pakovanja )

i 0,

242

8

16

3040

21

21

2

1

21

≥

≤+

≤

≤

+=

x x

x x

x

x

x xπ

5

Grafičko rješavanje

Problem maksimiziranja

Linije jednakih profita

Optimalno rješenje (16,4) Maksimalni bruto profit

760$ po danu

6

19.2 Opšte formulisanjelinearnih programa

Obični zapis

Zapis pomoću ∑

0

...

...

...

...

...

2211

22222121

11212111

2211

≥

≤+++

≤+++

≤+++

+++=

j

mnmnmm

nn

nn

nn

x

r xa xa xa

r xa xa xa

r xa xa xa

xc xc xcπ

0

...

...

...

...

...

2211

22222121

11212111

2211

≥

≥+++

≥+++

≥+++

+++=

j

mnmnmm

nn

nn

nn

x

r xa xa xa

r xa xa xa

r xa xa xa

xc xc xcC

0

1

1

≥

≤

=

∑

∑

=

=

j

n

j

i jij

n

j

j j

x

r xa

xcπ

0

1

1

≥

≥

=

∑

∑

=

=

j

i

n

j

jij

n

j

j j

x

r xa

xcC



7

Matrični zapis

≡

nc

c

c

c ...

2

1

≡

n x

x

x

x ...

2

1

=

mnmm

n

n

aaa

aaa

aaa

A

...

......

...

...

21

22221

11211

≡

mr

r

r

r ...

2

1

)1()1(

)1()1()(

)1(

'

)1(

0 ××

×××

××

≥

≤

=

nn

mnnm

nn

x

r x A

xcπ

0

'

≥

≤

=

x

r Ax

xcπ

0

'

≥

≥

=

x

r Ax

xcC

8

19.3 Konveksni skupovi ilinearno programiranje

Simbolički, za skup S kažemo da je konveksan ako

Konveksni skupovi se javljaju u većini aspekata linearnih programa

(zadata prava )

(zadata ravan )

(zadata hiperravan )

Hiperravan u n-dimenzionom prostoru je konveksan skup.

)10(,)1(, ≤≤−+≡∈⇒

∈

∈θ θ θ vuwS w

S v

S u

nn xc xc xc

xc xc xc

xc xc

+++=

++=

+=

...22110

3322110

22110

π

π

π

uc '

0 =π vc'

0 =π

[ ]

000

''

''''

)1()1(

)1()1(

π π θ θπ θ θ

θ θ θ θ

=−+=−+=

−+=−+=

vcuc

vcucvucwc

9

Hiperravan uvijek dijeli n-dimenzioni prostorna dva poluprostora .

Zatvoreni (c’x9) i otvoreni poluprostor(c’x<9)

Zatvoreni poluprostor n-dimenzionog prostora je konveksan skup, što se može pokazati.

Skup mogućih rješenja opšteg linearnogprograma sa n varijabli je zatvoren konveksanskup. To je presjek ukupno m+n zatvorenihkonveksnih skupova (m ograničenja + nuslova nenegativnosti)

Teorema: Presjek konačnog brojakonveksnih skupova je konveksan skup; ako je svaki od skupova zatvoren, presjek ćetakođe biti zatvoren.

10

Ekstremne tačke i optimalnorješenje

(1) Za bilo koju zadatu vrijednost od π (ili C), f-ja cilja linearnogprograma sa n varijabli uvijek definiše hiperravan koja je zatvorenkonveksan skup i (2) skup mogućih rješenja koji je presjek od m+nzatvorenih poluprostora takođe je zatvoren koveksan skup F.

Grani č na ta č ka b bilo kojeg skupa S ima svojstvo da svaka, ma kakomala, okolina od b mora sadržati makar jednu tačku koja ne pripadaskupu S. (tačke stranica kvadrata)

Unutrašnja ta č ka i skupa S ima svojstvo da će dovoljno mala okolinatačke i sadržati samo tačke koje pripadaju skupu S. (unutar kvadrata)

Ekstremna ta č ka je granična tačka koja ne leži na dužini što spajabilo koje druge dvije tačke skupa, tj. tačka koja se ne može prikazatikao konveksna kombinacija bilo kojih dviju drugih tačaka skupa.

(tjemena kvadrata)

11

Skup svih ekstremnih ta č aka od S je podskup skupa svih grani č nihta č aka od S; skup svih grani č nih ta č aka je disjunktan sa skupomsvih unutrašnjih ta č aka .

Potporna hiperravan Hp je hiperravan koja ima jednu ili višezajedničkih tačaka s konveksnim skupom F, ali koja je takosmještena da skup F leži isključivo na jednoj strani od Hp.

Samo grani č ne ta č ke skupa F mogu se pojaviti na hiperravnima.

Teorema I Za datu graničnu tačku u zatvorenog konveksnogskupa postoji barem jedna potporna hiperravan u u .

Teorema II Za zatvoreni konveksan skup ograničen odozdo postojibarem jedna ekstremna tačka u svakoj potpornoj hiperravni.

Značaj teorema očigledan: skup mogućih rješenja suziti na skupekstremnih tačaka.

12

Lokalni i globalni optimum

Teorema globalnosti (dovoljan ali ne i nužan uslov da je lokalniujedno i globalni minimum): Ako je skup F mogućih rješenjazatvoren konveksan skup i ako je f–ja cilja neprekidna konkavna(konveksna) f-ja na skupu mogućih rješenja, tada: (a) bilo koji l okalnimaksimum (mimimum) ujedno je i globalni maksimum (mimimum) i(b) tačke od F u kojima f-ja cilja dostiže optimum čine konveksanskup. Ako je f-ja cilja strogo konkavna (konveksna) na skupumogućih rješenja, tada je globalni maksimum (mimimum) jedinstven.

Važno svojstvo L.P. (razlika od klasičnih problema optimizacije)

Višestruki optimumi?



13

Nizovi

Realnu funkciju jedne realne promjenljive čija je oblast definisanosti

skup prirodnih brojeva zovemo nizom. Nezavisnu promjenljivu niza

obično označavamo sa n, a odgovarajuću vrijednost funkcije sa a(n) ili,

češće, sa an. Vrijednost niza za dato n zovemo i članom niza.

Za niz an

kažemo da monotono raste ako je an

< an+1

za svako n ∈ N.

Ako je an ≤ an+1, ∀n ∈ N, kažemo da niz an ne opada. Analogno se

definiše mononotono opadanje odnosno nerašćenje niza an.

Za niz an kažemo da je ograničen ako postoji realan broj M > 0, takav da

je |an| ≤ M, ∀n ∈ N.

14

Primjeri nizova

a nn =

1a

n nan n+ =

+< =1 1

11

1 11

n n= ≤

Primjer 1. Niz monotono opada jer je , ∀n ∈ N.

Ovaj niz je i ograničen jer je , ∀n ∈ N.

Primjer 2. Niz za n = 1,2,... ima vrijednosti

i, očigledno, nije monoton. Kako je , ∀n ∈ N dati

niz je ograničen.

( )− ⋅ +

11n n

n− −2

3

2

4

3

5

4, , , , ...

( )− ⋅ +

= +

≤11 1

2n n

n

n

n

15

ARITMETIČKI NIZ

ARITMETIČKI NIZ ili ARITMETIČKA PROGRESIJA je niz od n

realnih brojeva kod kojih je razlika svaka dva uzastopna člana ovog

konačnog niza (proizvoljnog i njemu prethodnog) konstanta.

Neka je d konstantna razlika odnosno diferencija .

Slijede relacije:

a a d2 1= +

a a d a d3 2 1

2= + = +

a a i d i ni = + − =1

1 1 2( ) , , , ,K

Odnosno

16

ARITMETIČKI NIZ

Primjenjujući poslednju relaciju imamo da je:

a a a n dn1 1

1+ = + −( )

a a a d a n d a n dn2 1 1 1 1

2 1+ = + + + − = + −−

( ) ( )

a a a an n1 2 1+ = +−

Odnosno

Na isti način se provjerava da važi:

K=+=+=+−− 34231 nnn aaaaaa

17

ARITMETIČKI NIZ

Kako je za:

To je

Odnosno:

{ }i k n− ∈ 1 2, , ..., i { }i k n+ ∈ 1 2, , ..., i k N, ∈

a a i k di k −

= + − −1

1( )

a a i k di k +

= + + −1

1( )

[ ]a a a i d a i d ai k i k − +

+ = + − = + − =2 2 1 2 1 21 1 1

( ) ( )

aa a

i

i k i k = +− +

2

Proizvoljni član aritmetičko g n iza je

aritmetička sredina dva u odnosu na

njega simetrična člana.

18

ARITMETIČKI NIZ

Zbir prvih n članova aritmetičkog niza je:

Kako je, takođe:

Slijedi:

a a a ai

i

n

n

=

∑ = + + +1

1 2 K

a a a a ai

i

n

n n

=

−

∑ = + + + +1

1 2 1K

21

1 2 1 1 1a a a a a a a n a a

i

i

n

n n n n

=

−∑ = + + + + + + = ⋅ +( ) ( ) ( ) ( )K

an

a ai

i

n

n

=

∑ = +1

12

( )Odnosno:

predavanje_matematika_6._26.09.2012

Documents

Transcript of predavanje_matematika_6._26.09.2012