Hogyan kell lineáris programozással célfüggvényt maximalizálni?

Ja igazad van, elírtam. De akkor meg pláne nincs probléma.

[link]

Van 3 egyenesed. Ezek:

2x + y = 600

x + 2y = 600

0x + 5y = 1200

Berajzolod őket egy koordináta rendszerbe, és mivel <=-ről van szó, ezért az egyenesek alatti területet kell színezni.

(Nem kell pontosan berajzolni, de valami sematikus ábra kell, hogy lásd hol vannak az extremális pontok.

Például a linkelt oldal erre jó, hogy megcsinálja helyetted az ábrát. )

Extremális pont: Na ezt illene tudnod, hogy mi :P Ez az egész LP alapja...

Tömören a berajzolt tartománynak a csúcsai.

Ránézel a rajzra és látod, hogy 2 csúcsa van.

1. csúcs

Ránézek a rajzra. Az ábra "széle" a 3 egyenes. A rajz nem mutatja, hogy melyik melyik, azt neked kell kitalálni.

De ha érted, mi az, hogy x+2y=600 egyenes, akkor nem túl nehéz beazonosítani őket.

Szóval a rajz alapján az első extremális pont az alábbi két egyenes metszéspontja:

5y=1200 és x+2y=600

(A rajzon látszik is, hogy kb 100,250 a metszéspont)

A metszéspont meghatározása úgy megy, hogy megoldod ezt az egyenletrendszert.

5y=1200

x+2y=600

Elsőből: y=240,

Másodikba beírva: x+2*240=600 -->x=120

(120;240) pont az extremális pont.

2. extremális pont

2x+y=600

x+2y=600 egyenesek metszéspontja

(200;200)-nál van.

Következő lépés:

célfüggvény kiértékelése.

Ki kell számolni az extremális pontban az értékeit.

cf1=200*120+340*240=105600

cf1=200*200+340*200=108000

Maximum (200;200) pontban van, 108.000 a maximum érték.

cf2 ugyanez.

Annak meg (120;240)-nél van maximuma. cf2=58080

A csúcsokat kell kiszámolni.

x+2y=600

5y=0

Megoldásából nem kapunk csúcsot.

A csúcsok mindig 2 egyenes metszéspontjai.

Ezért kell a rajz, hogy tudjad, melyik KÉT egyenes metszi ott egymást.

Ha nincs rajz és van mondjuk 5 egyenesed, akkor megteheted, hogy kiszámolod páronként a metszéspontokat.

Lesz összesen 10.

De ebből csak azok a jók, amik beleesnek a színezett részbe. És mondjuk olyanból csak 5 van, te meg 10-et számoltál, aminek a fele fölösleges.

Senki sem ismeri a szimplex algoritmust??

[link]