Ugrás a tartalomhoz

Matematika példatár 7., Lineáris algebra II.

Szerző Csordásné Marton Melinda (2010)

Nyugat-magyarországi Egyetem

7.5 Lineáris programozás

7.5 Lineáris programozás

A lineáris programozás általános feladata lineáris függvény szélsőértékének keresése bizonyos feltételek mellett. A feltételek lineáris egyenletek, vagy egyenlőtlenségek és a változókra vonatkozó nemnegativitási követelmények által meghatározott konvex poliéder. A gyakorlati feladatok általában a következő ún. normál alakban adottak.

Legyen lineáris függvény, azaz adott mellett . Keressük ennek az ún. célfüggvénynek a maximumát az alábbi feltételek mellett:

Az mátrixot technológiai együttható mátrixnak, elemeit technológiai együtthatóknak nevezzük.

A vektor a kapacitásvektor, a vektor elemei a célfüggvény együtthatói.

Ha az ismeretlen kielégíti a feladat és feltételeit, és a cálfüggvény értéke maximális e feltételek mellett, akkor neve optimális megoldás. Előfordulhat, hogy több optimális megoldás is van, akkor alternatív optimumról beszélünk. Természetesen az is előfordulhat, hogy a feladatnak nincs megoldása.

A lineáris programozási feladat grafikus és szimplex módszerrel történő megoldását a mintapéldákon keresztül mutatjuk be.

  1. Példa: Egy magyarországi divatcég külföldi megrendelésre dolgozik. Farmernadrágokat és kabátokat gyártanak. A nadrágok elkészítéséhez egy normaórára, a kabátok elkészítéséhez két normaórára van szükség. A nadrág és a kabát mindegyikéhez két méter anyagra van szükség, de a nadrághoz még 2m szegődíszt is használniuk kell, amit csak importból tudnak beszerezni. Az üzem napi 10 normaórában tud termelni. Alapanyagból napi 12 méter áll rendelkezésre, az import szegőből 8 métert tudnak naponta beszerezni. A nadrágokon darabonként 2000Ft, a kabátokon 3000Ft haszna van a cégnek. Hány nadrágot és kabátot gyártsanak, hogy a nyereség maximális legyen?

A jobb áttekinthetőség kedvéért foglaljuk a feladat adatait egy táblázatba:

17. ábra

A táblázat segítségével a következő matematikai modell írható fel:

Tegyük fel, hogy darab nadrágot, és darab kabátot gyártunk. Mivel negatív számú munkadarabot nem termelünk, ezért feltesszük, hogy

és .

Csak annyi terméket gyárthatunk, amely normaóra, alapanyag és import tekintetében nem lépi túl azt a kapacitást, amely a rendelkezésünkre áll. Ezen feltételek alapján az alábbi egyenlőtlenségeket írhatjuk fel:

normaórára:

alapanyagra:

importra:

A maximalizálandó célfüggvény , amit a következőképpen jelölhetünk: maximális.

Kiemeléssel látható, hogy a maximális feladat megoldásai azonosak az eredetiével.

18. ábra

A feladat grafikus megoldása:

A feltételek a sík egy poligonját jelölik ki. A poligon csúcspontjait extremális pontoknak nevezzük. Ezek a feladatban A poligon minden belső és határoló pontja megoldás, mert kielégíti a feladatban meghatározott feltételeket. E megoldások közül keressük az optimálisakat, vagyis azokat, amelyek az üzem számára a maximális bevételt jelentik. Ezeket a megoldásokat megkapjuk a célfüggvény ábrázolásával. A célfüggvény minimuma az feltételek miatt nyilván nulla. Először ábrázoljuk a célfüggvény zérushelyeit, amelyek a egyenletű egyenes pontjai. A feltételeknek csak felel meg, ami azt jelenti, hogy nem gyártunk semmit. Az egyenest párhuzamosan eltolva a pozitív síknegyedben, az eltolt egyenes szakaszban metszi a poligont, majd csak a csúcspontban. Belátható, hogy ez az optimális megoldás.

Az alábbi táblázatban összefoglaljuk a célfüggvény értékeit az extremális pontokban:

19. ábra

A grafikus megoldásból látható, hogy az az optimális megoldás, ha két farmernadrágot és négy kabátot gyártanak. Ekkor a cég napi nyeresége maximális, 16.000 Ft.

A grafikus megoldás ebben az egyszerű kétváltozós esetben nagyon kedvezőnek tűnik. A gyakorlati életben természetesen több változó és több feltétel esetében kell, hogy a megoldást megadjuk, amelyhez a grafikus megoldás már nem alkalmazható.

Az alábbiakban ismertetett, szimplex módszer számítógépen is jól programozható megoldását adja a feladatnak. A szimplex módszer a grafikus elgondolás átfogalmazása. Már két dimenzióban is látható volt, hogy az egyenesek metszéspontját mindig a két egyenes egyenlete által alkotott lineáris egyenletrendszer megoldásával nyertük. Visszavezethetjük tehát a feladat megoldását a lineáris egyenletrendszerek megoldásának elméletéhez.

A szimplex módszer kezdőtáblája

Az a táblázat, amelynek a bal felső része a technológiai együttható mátrix, a jobb felső része a kapacitásvektor, az alsó sorban a célfüggvény együtthatói szerepelnek.

20. ábra

A szimplex módszer lépései

  1. A generáló elem oszlopának kiválasztása: az alsó (piros) sorban csak nemnegatív elemhez tartozó oszlop választható. Ha az alsó sorban már csak negatív számok találhatóak, akkor az eljárás véget ért.

  2. Egy oszlopban több elem található, de ezek közül nem lehet akármelyik generáló elem. A generáló elemet úgy kell kiválasztani, hogy az

    • csak pozitív lehet;

    • „szűk keresztmetszetet” kell képviselnie, tehát a kapacitásoszlop minden elemét elosztom a kiválasztott oszlop ugyanazon sorában lévő elemével, és ezek közül az lesz a generáló elem, ahol ez a hányados a legkisebb.

  3. A generáló elem helyére annak reciproka kerül.

  4. A generáló elem sorát osztjuk a generáló elemmel.

  5. A generáló elem oszlopát osztjuk a generáló elemmel és szorozzuk -gyel.

  6. A többi hiányzó elemet az elemi bázistranszformációnál tanult lépésekkel számoljuk ki.

A szimplex táblázatok:

1. Példa Kiinduló tábla: A(0,0) pont

Az alsó sor egyetlen eleme sem negatív, tehát bármelyik oszlopot választhatjuk. Érdemes az oszlop választásakor egy másik szempontot is figyelembe venni. Ha az első oszlopot választjuk, akkor az tengely mentén fogunk elindulni az irányban. Ez az induló táblázattal együtt négy szimplex tábla kiszámítását fogja jelenteni. Ha a második oszlopot választjuk, akkor az tengely mentén fogunk elindulni, így pontokon keresztül jutunk el a megoldáshoz, amely az induló táblával együtt csak három szimplex táblázat kiszámítását jelenti. Fontos, hogy megjegyezzük, ez a mérlegelési lehetőség csak most a grafikus megoldás ismeretében lehetséges. Válasszuk a második oszlopot. A generáló elem kiválasztása az ún. „szűk keresztmetszet” szerint történik:

21. ábra

A második táblázatban az egyenes, vagyis az tengely, és az egyenes metszéspontját számítjuk ki.

22. ábra

pont

Nyereség: 15000Ft

Mivel az alsó sorban van nemnegatív elem, az algoritmust tovább folytatjuk, most az és egyenesek metszéspontját számítjuk ki.

22. ábra

pont

Nyereség: 16000Ft

Tehát két nadrágot és négy kabátot kell gyártaniuk naponta.

2. Példa alternatív optimum meghatározásához

Egy üzem kétfajta termék előállítására alkalmas. Készítsük el az üzem maximális nyereséget hozó termelési tervét, és számítsuk ki a nyereséget az alábbi információk alapján.

23. ábra

Matematikai modell:

és

Célfüggvény: maximális.

Grafikus megoldás:

25. ábra

Az ábráról látható, hogy a megoldás nem egy pont, hanem a szakasz. Ilyenkor alternatív optimumról beszélünk, ami azt jelenti, hogy a szakasz bármely egész koordinátájú pontja megoldás.

26. ábra

Az üzem gyárthat az A termékből 6 darabot és a B termékből 2 darabot vagy az A termékből 5 darabot, és a B termékből 4 darabot a maximális nyereség eléréséhez.

Megoldás szimplex módszerrel:

27. ábra

28. ábra

29. ábra

Az első oszlopból ismét választunk generálóelemet.

30. ábra

Ha az első oszlopból megint választanánk generálóelemet, akkor ismét a harmadik táblázatot kapnánk. Az algoritmus véget ért.

Megoldás: alternatív optimum. Az üzem gyárthat az A termékből 6 darabot és a B termékből 2 darabot, vagy az A termékből 5 darabot és a B termékből 4 darabot a maximális nyereség eléréséhez. Lehetséges megoldások még a CD él egész koordinátájú pontjai is.

3. Példa: Oldjuk meg az alábbi normál feladatot!

Megoldás szimplex módszerrel:

31. ábra

32. ábra

33. ábra

A harmadik táblázat utolsó sorában csak negatív elemek vannak, ezért a táblázat optimális, és a feladatnak egyetlen optimális megoldása van.

Az optimális megoldás ,

Nyereség: 10 egység.

7.5.1 Feladatok

  1. Az alábbi gazdasági modellel megadott lineáris programozási feladatban határozzuk meg, hogy az egyes termékekből mennyit kell termelni, hogy a haszon maximális legyen!

    Írja fel a matematikai modellt! Számítsa ki a megoldást

    a) grafikus módszerrel,

    b) szimplex módszerrel!

    34. ábra
    35. ábra

    36. ábra
  2. Oldjuk meg az alábbi normál feladatot!

Megoldások:

1.a) Matematikai modell:

Célfüggvény: maximális.

Megoldás szimplex módszerrel:

37. ábra

Nyereség: 0

38. ábra

Nyereség: 1500

39. ábra

Nyereség: 1700

A táblázat utolsó sorában csak negatív elemek vannak, ezért a táblázat optimális és a feladatnak egyetlen optimális megoldása van.

Az optimális megoldás ,

Nyereség: 3400 egység.

b) Matematikai modell:

Célfüggvény: 1maximális.

Megoldás szimplex módszerrel:

40. ábra

Nyereség: 0

41. ábra

Az optimális megoldás ,

Nyereség: 1000 egység.

c) Matematikai modell:

Célfüggvény: maximális.

42. ábra

Nyereség: 0

43. ábra

Nyereség: 1500

44. árba

Nyereség: 1700

45. ábra

Nyereség: 1700

Alternatív optimum: szakasz minden egész koordinátájú pontja megoldás.

2. Megoldás szimplex módszerrel:

46. ábra
47. ábra
48. ábra

A táblázat utolsó sorában egy pozitív elem található, azonban ez az oszlop nem tartalmaz pozitív elemet, így ebből az oszlopból nem tudunk generáló elemet választani. A feladatnak nincs optimuma. (A célfüggvény nem korlátos a lehetséges megoldások halmazán.)