|
==Általános optimalizációs feladatok==
Az általános optimalizációs feladat tipikus példájakéntpéldája egyaz '''ellátási problémát''' tárgyalunkprobléma.
===A feladat kitűzése===
Egy mezőgazdasági üzemben a sertéseket burgonyával és répával hizlalják. A burgonya 3% fehérjét és 15% szénhidrátot, a répa 1% fehérjét és 10% szénhidrátot, és mind a kettő 2% ásványi sót tartalmaz. A sertéseknek naponta legalább 0,3 t fehérjét és 2,25 t szénhidrátot kell fogyasztani, de a táplálékban nem szabad 0,5 t-nál több ásványi sónak lennie. 1 t burgonya 100 márkába kerül, 1 t répa 50 márkába. Milyen <math>x</math> burgonya-és <math>y</math> répamennyiség használható fel, hogy a hizlalás a legolcsóbb legyen?
===Megoldás===
Először is felírjuk az adatokat egyenletek, illetve egyenlőtlenségek formájában. A hizlalás napi összköltsége ''K'', <math>x</math> és <math>y</math> függvénye. <math>K</math>-t '''célfüggvénynek''' nevezzük: <br /> <math>K=K(x;y)=100x+50y</math>. <br /> <math>K</math>-nak lehetőleg kicsinek kell lennie. Emellett azonban be kell tartani a mellékfeltételeket: a táplálékban legalább 0,3 t fehérjének és 2,25 t szénhidrátnak kell lennie, és nem szabad túl sok sót tartalmaznia. A százalékos adatokból tehát adódnak a '''mellékfeltételek''':<br />
<math>0,03x+0,01y \ge0,3</math> <br />
<math>0,15x+0,10y \ge2,25</math> <br />
<math>0,02x+0,02y \le0,5</math> <br />
Az <math>x</math> és <math>y</math> változók nemnegatívak,<br />
''(-negatív érték esetén a változó főegyütthatójának a negáltját kell venni-)''<br />
tehát érvényes a '''nemnegativitási feltétel''': <math>x \ge0</math>, <math>y \ge0</math>.
Mivel a feladat csak két ismeretlen mennyiséget: <math>x</math>-et és <math>y</math>-t tartalmaz, '''grafikusan is megoldható'''. Ehhez <math>x</math>-et és <math>y</math>-t egy pont derékszögű koordinátáinak tekintjük, és az <math>(x; y)</math> síkban azt a <math>G</math> tartományt keressük, amelynek pontjai kielégítik a mellékfeltételeket és a nemnegativitási feltételt. Ez a '''megengedhető''' tartomány, mert a megoldáshoz csak olyan <math>(x; y)</math> pontok jönnek számításba, amelyek a <math>G</math> határán vagy a belsejében vannak.
<math>G</math> meghatározását például a következőképpen végezhetjük: felrajzoljuk a <math>0,03x+0,01y=0,3</math>, illetve <math>3x+y=30</math> egyenletű egyenest úgy, hogy két pontját, például a (0; 30) és a (10; 0) pontokat berajzoljuk és összekötjük egymással. Most megnézzük, hogy a (0; 0) pont kielégíti-e az eredeti egyenlőtlenséget. Itt az egyenlőtlenséget annak a félsíknak a pontjai elégítik ki, amely nem tartalmazza (0; 0) pontot. így egymás után végigmegyünk az összes feltételen, és <math>G</math> az a tartomány, amelynek belsejében vagy határán egyidejűleg minden feltétel kielégül.
Végül még egy, <math>K=100x+50y=c</math> egyenest rajzolunk be, ahol <math>c</math> tetszés szerinti szám (például <math>c=500</math>). Majd meghatározzuk <math>c</math> legkisebb értékét úgy, hogy ezt az egyenest addig toljuk el önmagával párhuzamosan, amíg <math>G</math>-t érinti. A <math>c</math> mennyiség a legkisebb értékét tehát vagy a <math>G</math> egyik csúcspontjában veszi fel, vagy a <math>G</math> egy határoló egyenesén. Az alábbi táblázatban, ahol <math>G</math> mindegyik csúcspontjának koordinátái, és a <math>K(x y)</math> célfüggvény ezekhez tartozó értékei vannak feltüntetve, megtalálható a megoldás: <math>K=1250</math>, ha <math>x=5</math>, <math>y=15</math>.
Naponta tehát 5 t burgonyát és 15 t répát kell a sertéseknek adni; ez adja a minimális 1250 márka költséget.
{| border="1" cellspacing="0"
| <math>G</math> csúcspontjai
| <math>x</math>
| <math>y</math>
| '''<math>K(x; y</math>'''
|-
| <math>P_1</math>
| 15
| 0
| '''1500'''
|-
| <math>P_2</math>
| 25
| 0
| '''2500'''
|-
| <math>P_3</math>
| 2,5
| 22,5
| '''1375'''
|-
| <math>P_4</math>
| 5
| 15
| '''1250'''
|}
===Egy probléma általános megfogalmazása===
Az előbb kifejtett ellátási probléma általánosítható, ha a három táplálékféleségen kívül még tekintetbe kell venni például zsírt, vitaminokat. Ha ezenkívül még egyéb táplálékot is bevonunk, akkor általános lineáris optimalizációs problémát kapunk.
A lineáris optimalizáció minden feladata a következő '''normálalakba''' írható: adva van a <math>'''c'''=(c_1, c_2,..., c_n)</math> sorvektor, az '''A''' mátrix és az '''a''' oszlopvektor:<br />
<math>A=\left( \frac{a_{11}...a_{1n}}{a_{m1}...a_{mn}} \right)</math>, <math>a=\left( \frac{a_1}{a_m} \right)</math>.<br />
Keressük az <br />
<math>x=\left( \frac{x_1}{x_n} \right)</math> oszlopvektort a következő feltételek mellett:
''<math>K=K(x_1, x_2, ..., x_n)=cx</math> <math>\rightarrow</math> minimum, <math>Ax \le a</math> és <math>x \ge 0</math>.''
A fenti példában ez így alakul: <br />
c=(100,50), <math>A=\begin{pmatrix} -0,03 & -0,01 \\ -0,15 & -0,10 \\ 0,02 & 0,02 \end{pmatrix}</math>, <math>a=\begin{pmatrix} -0,3 \\ -2,25 \\ 0,5 \end{pmatrix}</math>, <math>x=\begin{pmatrix} x \\ y \end{pmatrix}</math>.
==Szállítási problémák==
| 