Lineáris programozási feladatok típusai és grafikus megoldása Alkalmazott operációkutatás 2. elıadás 2008/2009. tanév 2008. szeptember 19. Smahó Melinda
Smahó Smahó Melinda
Maximumfeladat grafikus megoldása 2 x 1 + x 2 ≤ 100
(1)
x 1 + x 2 ≤ 80
(2)
x 1 ≤ 40
(3)
x1 ≥ 0 x2 ≥ 0 z = 3 x 1 + 2 x 2 → max lehetséges megoldások
Optimális megoldás:
x1 = 20 x 2 = 60 z = 180 Smahó Smahó Melinda
1
Definíciók I. • Lehetséges megoldások halmaza: az összes olyan pontok halmaza, amelyek kielégítik a lineáris programozási feladat valamennyi feltételét és az összes elıjelkorlátozást. • Optimális megoldás: – Maximalizálási problémában: olyan pont a lehetséges megoldások halmazában, amelyikhez a legnagyobb célfüggvényérték tartozik. – Minimalizálási problémában: olyan pont a lehetséges megoldások halmazában, amelyikhez a legkisebb célfüggvényérték tartozik
Smahó Smahó Melinda
Definíciók II. • Maximum feladat: olyan lineáris programozási feladat, amelyben a feltételek ≤ értelmőek és a célfüggvény maximuma jelenti az optimumot. • Minimum feladat: olyan lineáris programozási feladat, amelyben a feltételek ≥ értelmőek és a célfüggvény minimuma jelenti az optimumot.
Smahó Smahó Melinda
2
Minimumfeladat Egy állattartó telepen az állatok etetésére kétfajta (A és B jelő) tápot használnak. A tápok 4 fajta alapanyagot (vitamin, búza, lucerna, kukorica) tartalmaznak a táblázatban szereplı megoszlásban: A táp összetétele: 1 kg = 0,2 kg vitamin + 0,1 kg lucerna + 0,7 kg kukorica B táp összetétele: 1 kg = 0,2 kg búza + 0,2 kg lucerna + 0,6 kg kukorica Az állatorvos szerint egy állatnak naponta legalább 5,8 kg tápot kell megennie az elıírt összetételben.
A táp
B táp
Elıírt menny
Vitamin
0,2 kg 0 kg
0,2 kg
Búza
0 kg
Lucerna
0,1 kg 0,2 kg 1,0 kg
0,2 kg 0,4 kg
Kukorica 0,7 kg 0,6 kg 4,2 kg 1 kg költsége
30 Ft/kg
40 Ft/kg
5,8 kg
Feladat: Határozzuk meg a gazdaságos tápanyag összetételét, ha ismertek az egyes összetevık elıírt mennyiségei és az A, illetve a B jelő táp kilogrammonkénti költségei. (Raffai, 101. o.) Smahó Smahó Melinda
Minimumfeladat matematikai modellje x1= az A tápból szükséges mennyiség (a keverék elıállításához) x2 = a B tápból szükséges mennyiség (a keverék elıállításához)
0,2 x1 + 0 x 2 ≥ 0,2 0 x1 + 0,2x 2 ≥ 0,4
(vitamin) (búza)
0,1x1 + 0,2 x 2 ≥ 1,0
(lucerna)
0,7 x1 + 0,6x 2 ≥ 4,2
(kukorica)
x1
≥0
(nemnegativitási feltétel)
x2 ≥ 0
(nemnegativitási feltétel)
z = 30x 1 + 40 x 2 → min
Smahó Smahó Melinda
3
Minimumfeladat grafikus megoldása 0,2 x1 + 0 x 2 ≥ 0,2
(V)
0 x1 + 0,2 x 2 ≥ 0,4
(B)
0,1x1 + 0,2 x 2 ≥ 1,0
(L)
0,7 x1 + 0,6 x 2 ≥ 4,2
(K)
x1
≥0
(nemn. felt.)
x2 ≥ 0
(nemn. felt.)
z = 30x1 + 40x 2 → min Optimális megoldás:
x1 = 3 x2 = 3,5 z= 230
Smahó Smahó Melinda
Speciális esetek • Alternatív optimum • Nem megoldható lineáris programozási feladat • A célfüggvény nem korlátos
Smahó Smahó Melinda
4
Alternatív optimum Egy autógyár személyautókat és teherautókat gyárt. A gyártás során minden egyes jármőnek végig kell mennie a festımőhelyen és a karosszéria összeszerelı mőhelyen. Ha a festımőhely csak teherautókat festene, naponta 40 darabot tudna lefesteni. Ha a festımőhely csak személyautókat festene, naponta 60 darabot tudna elkészíteni. Ha a karosszériamőhely csak személyautókat állítana össze, naponta 50 db-ot tudna megcsinálni, míg ha csak teherautókkal foglalkozna, akkor naponta 50 db-ot tudna elkészíteni. Minden teherautó 300 dollárral és minden személyautó 200 dollárral járul hozzá a profithoz. Alkalmazzuk a lineáris programozást a napi termelési terv meghatározásához úgy, hogy a vállalat profitja maximális legyen! (Winston, 68.o.) Smahó Smahó Melinda
Alternatív optimum x1= a naponta gyártott teherautók száma x2 = a naponta gyártott személyautók száma
Matematikai modell:
1 1 x1 + x 2 ≤ 1 40 60 1 1 x1 + x 2 ≤ 1 50 50 x1 , x 2 ≥ 0
(festımőhely felt.)
(karosszériamőhely felt.)
z = 3x1 + 2 x 2 → max (száz dollárban) Smahó Smahó Melinda
5
Alternatív optimum 1 1 x1 + x 2 ≤ 1 40 60 1 1 x1 + x 2 ≤ 1 50 50 x1 , x 2 ≥ 0
(f)
(k)
z = 3x1 + 2 x 2 → max (száz dollárban)
alternatív optimum, a szakasz minden pontja optimális
Smahó Smahó Melinda
Nem megoldható lineáris programozási feladat Az autókereskedık azt szeretnék, hogy az autógyár naponta legalább 30 teherautót és 20 személyautót gyártson.
1 1 x1 + x 2 ≤ 1 40 60 1 1 x1 + x 2 ≤ 1 50 50 x1 ≥ 30 x2
≥ 20
x1 , x 2 ≥ 0 z = 3x1 + 2x 2 → max (száz dollárban) Smahó Smahó Melinda
6
Nem megoldható lineáris programozási feladat 1 1 x1 + x 2 ≤ 1 (f) 40 60 1 1 x1 + x 2 ≤ 1 (k) 50 50 x1 ≥ 30 (t) x2
≥ 20 (sz)
x1 , x 2 ≥ 0 z = 3x1 + 2x 2 → max (száz dollárban)
LEHETSÉGES MEGOLDÁSOK HALMAZA ÜRES! Smahó Smahó Melinda
A célfüggvény nem korlátos x1 − x 2 ≤ 1
(1)
2 x1 + x 2 ≥ 6
(2)
x1 , x 2 ≥ 0 z = 2 x1 − x 2 → max
A CÉLFÜGGVÉNY NEM ÉRINTI, HANEM METSZI A LEHETSÉGES MEGOLDÁSOK HALMAZÁT!
Smahó Smahó Melinda
7
A célfüggvény nem korlátos • Maximum feladat esetén: a lehetséges megoldások halmazában találhatók olyan pontok, amelyekhez tetszılegesen nagy z értékek tartoznak (növekvı z irányába haladva sosem hagyjuk el a lehetséges megoldások halmazát). • Minimum feladat esetén: a lehetséges megoldások halmazában találhatók olyan pontok, amelyekhez tetszılegesen kicsi z érték tartozik (csökkenı z irányába haladva sosem hagyjuk el a lehetséges megoldások halmazát).
Smahó Smahó Melinda
Lineáris programozási feladatok típusai és matematikai modelljei
Smahó Smahó Melinda
8
Maximum feladat Maximum feladat: olyan lineáris programozási feladat, amelyben a feltételek ≤ értelmőek és a célfüggvény maximuma jelenti az optimumot. Alapforma
Kanonikus forma
x≥0
x ≥ 0,u ≥ 0
A⋅x ≤ b
A⋅x + u = b
T
z = c ⋅ x → max
T
z = c ⋅ x → max hiányváltozó
Smahó Smahó Melinda
Minimum feladat Minimum feladat: olyan lineáris programozási feladat, amelyben a feltételek ≥ értelmőek és a célfüggvény minimuma jelenti az optimumot. Alapforma
Kanonikus forma
x≥0 A⋅x ≥ b
x ≥ 0, v ≥ 0 A⋅x − v = b
T
z = c ⋅ x → min
T
z = c ⋅ x → min többletváltozó
Smahó Smahó Melinda
9
Normál feladat Normál feladat: olyan maximumfeladat, amelynél a b ≥ 0 feltétel is teljesül Alapforma
Kanonikus forma
x ≥ 0,b ≥ 0
x ≥ 0,u ≥ 0,b ≥ 0 A⋅x + u = b
A⋅x ≤ b T
z = c ⋅ x → max
T
z = c ⋅ x → max Smahó Smahó Melinda
Módosított normál feladat • Módosított normál feladat: olyan lineáris programozási feladat, amelynek egyenlıtlenségei ≤ értelmőek, tartalmaz egyenleteket és a célfüggvény maximumát keressük, továbbá b1 és b2 vektorok minden koordinátája nemnegatív
Alapforma
Kanonikus forma
x ≥ 0 , b1 ≥ 0 , b 2 ≥ 0
x ≥ 0 , u ≥ 0, b1 ≥ 0 , b 2 ≥ 0
A1 ⋅ x ≤ b1
A1 ⋅ x + u = b1
A2 ⋅ x = b2
A2 ⋅ x = b2
T
z = c ⋅ x → max
T
z = c ⋅ x → max Smahó Smahó Melinda
10
Általános feladat Általános feladat: olyan lineáris programozási feladat, amelynek feltételei között a kapacitások (b) nemnegativitása mellett ≥ relációk is szerepelnek és maximum a cél Alapforma x≥0 A1 ⋅ x ≤ b1 b1 ≥ 0 , A 2 ⋅ x = b2 b2 ≥ 0 A 3 ⋅ x ≥ b 3 b3 ≥ 0 T
z = c ⋅ x → max
Kanonikus forma x ≥ 0,u ≥ 0,v ≥ 0 A1 ⋅ x + u = b1 b1 ≥ 0 , A 2 ⋅ x = b2
b2 ≥ 0
A 3 ⋅ x − v = b3 b3 ≥ 0 T
z = c ⋅ x → max Smahó Smahó Melinda
Köszönöm a figyelmet!
Smahó Smahó Melinda
11
