Lineáris programozás - PDF ingyenes letöltés

1. FEJEZET Lineáris programozás 1.1. Mi a lineáris programozás 1.1.1. Példa: a Polly-rezsim problémája [1, 3. o.]. Napi követelmények: Energia: 2000 kcal Fehérje: 55 g Kalcium: 800 mg Élelmiszer kapható Rész energia (kcal) Fehérje (g) Kalcium (mg) Ár/adag Gabonafélék 28g 110 4 2 3 Csirke 100g 205 32 12 24 Tojás 2 nagy 160 13 54 13 Teljes tej 237 köbcentis 160 8 285 9 Savanykás 170 g 420 4 22 20 Sertés és bab 260 g 260 14 80 19 Milyen választási lehetőségek vannak a Polly számára? Korlátozások: Gabonafélék: legfeljebb 4 adag naponta Csirke: legfeljebb 3 adag naponta Tojás: legfeljebb 2 adag naponta Tej: legfeljebb 8 adag naponta Pite: legfeljebb 2 adag naponta Sertés és bab: legfeljebb 2 adag naponta 1.1.1. Talál Polly megoldást? Hogyan formalizálják a problémát? (modellezés) Mi teszi a problémát sajátossá? Tudja, hogyan lehet megoldani a hasonló problémákat? 1.1.2. Lineáris programozási probléma standard formája. Probléma. [1, p. 5] 1

lineáris

2 1. VONALOS PROGRAMOZÁS Definíció. Lineáris programozási probléma standard formában: Maximalizálás: Korlátozások alatt: z: = cjxja ij xjbi, i = 1.mxj 0, j = 1. n A változók választását (x 1.xn) nevezzük a feladat megoldásának. Megoldás akkor valósítható meg, ha megfelel a megszorításoknak. z objektív függvénynek nevezzük. Minden megoldáshoz társít egy értéket. A megoldás akkor optimális, ha megvalósítható és maximalizálja a célfüggvényt. 1. gyakorlat Feltehetjük-e az előző példákat szabványos formában? 1.1.3. Optimális megoldások léteznek? 1.1.2. Feladat [1, p. 7] Tekintsük a következő három szokásos lineáris programozási problémát, amelyeket a MuPAD számítógépes algebrai rendszer szintaxisával írunk: Chvatal7a: = [[x1 0. Ha a táblázatban szereplő egyenletek nem szabnak korlátot az X i-re, a rendszer korlátlan: a fele az (0, 0, X, 0, 0) által leírt Xi 0 sor olyan megvalósítható megoldásokból áll, amelyek a kívánt z értéket adják meg.