LINEÁRIS PROGRAMOZÁS: MIRE SZOLGÁL, MODELLEK, KORLÁTOZÁSOK, ALKALMAZÁSOK - MATEMATIKA - 2026

A lineáris programozás egy matematikai módszer, amelyet olyan funkció optimalizálására (maximalizálására vagy minimalizálására használunk), amelynek változói korlátozottak, mindaddig, amíg a függvény és a korlátozások lineárisan függő változók.

Általában az optimalizálható funkció modellezi a gyakorlati helyzetet, például egy olyan gyártó nyereségét, amelynek bemenete, munkaerő vagy gépek korlátozottak.

1. ábra. A lineáris programozást széles körben használják a profit optimalizálására. Forrás: Piqsels.

Az egyik legegyszerűbb eset a maximálisan lineáris függvény, amely csak két változótól függ, úgynevezett döntési változót. A következő lehet:

Z = k ₁ x + k ₂ y

K ₁ és k ₂ állandóval. Ezt a funkciót objektív funkciónak nevezik. Természetesen vannak olyan helyzetek, amelyeknél kettőnél több változó érdemel megvizsgálást, és ezek összetettebbek:

Z = k ₁ x ₁ + k ₂ x ₂ + k ₃ x ₃ +….

A korlátokat matematikailag modellezi egy egyenletrendszer vagy egyenlőtlenségek rendszere is, amelyek x-ben és y-ben egyaránt egyenesek.

Ebben a rendszerben a megoldások halmazát megvalósítható megoldásoknak vagy megvalósítható pontoknak nevezzük. És a megvalósítható pontok között van legalább egy, amely optimalizálja a célfüggvényt.

A lineáris programozást függetlenül az amerikai fizikus és matematikus George Dantzig (1914-2005), valamint az orosz matematikus és közgazdász, Leonid Kantorovich (1912-1986) dolgozta ki röviddel a második világháború után.

A simplex módszerként ismert problémamegoldó módszer Dantzig agyalapja, aki az amerikai légierőnél, a Berkeley Egyetemen és a Stanfordi Egyetemen dolgozott.

2. ábra: George Dantzig (balra) és Leonid Kantorovich (jobbra) matematikusok. Forrás: F. Zapata.

Lineáris programozási modellek

A gyakorlati helyzethez igazodó lineáris programozási modell létrehozásához szükséges elemek:

-Objektív funkció

-Döntési változók

-Restrictions

A célfüggvényben meghatározza, mit akar elérni. Tegyük fel például, hogy maximalizálni szeretné egyes termékek gyártásából származó profitot. Ezután létrejön a "profit" függvény a termékek eladási árának függvényében.

Matematikai szempontból ezt a függvényt az összegző jelöléssel rövidíthetjük:

Z = ∑k _i x _i

Ebben az egyenletben k _i együtthatók és x _i a döntési változók.

A döntési változók a rendszer azon elemei, amelyek ellenőrzését elvégezték, és értékeik pozitív valós számok. A javasolt példában a döntési változók az egyes termékek mennyisége, amelyeket el kell gyártani a maximális profit elérése érdekében.

Végül vannak olyan korlátok, amelyek lineáris egyenletek vagy egyenlőtlenségek a döntési változók szempontjából. Leírják a probléma korlátozásait, amelyek ismertek és lehetnek például a gyártás során rendelkezésre álló nyersanyagmennyiségek.

A korlátozások típusai

Számos M korlátozással rendelkezhet, kezdve j = 1-től j = M-ig. Matematikailag a korlátozások háromféleek:

1. A _j = ∑ a _ij. x _i
2. B _j ≥ ∑ b _ij. x _i
3. C _j ≤ ∑ c _ij. x _i

Az első korlátozás lineáris egyenlet típusú, és azt jelenti, hogy tiszteletben kell tartani az ismert A _j értéket.

A fennmaradó két korlátozás lineáris egyenlőtlenségek, és ez azt jelenti, hogy az ismert B _j és C _j értékeket be lehet tartani vagy túllépni, ha a megjelenő szimbólum ≥ (nagyobb vagy egyenlő), vagy tiszteletben tartja vagy nem haladja meg, ha a szimbólum ≤ (kevesebb vagy egyenlő).

Modell példa

Az alkalmazási területek nagyon változatosak, az üzleti adminisztrációtól a táplálkozásig, de a módszer megértése érdekében az alábbiakban kétféle változóval ellátott, a gyakorlati helyzet egyszerű modelljét javasoljuk.

A helyi cukrászda két különlegességről ismert: fekete erdei sütemény és szacripantine sütemény.

Előkészítéséhez tojásra és cukorra van szükségük. A fekete erdőhöz 9 tojásra és 500 g cukorra van szükség, míg a szacripantinra 8 tojásra és 800 g cukorra van szükség. A vonatkozó eladási árak 8 USD és 10 USD.

A probléma az, hogy hány tortát kell készíteni a pékségnek a profit maximalizálása érdekében, tudva, hogy 10 kiló cukrot és 144 tojást tartalmaz?

Döntési változók

A döntési változók "x" és "y", amelyek valós értékeket vesznek fel:

-x: a fekete erdei sütemények száma

-y: szacripantine típusú sütemények.

korlátozások

A korlátozásokat az a tény adja, hogy a sütemények száma pozitív mennyiség, és korlátozott mennyiségű alapanyag van azok elkészítéséhez.

Ezért matematikai formában ezek a korlátozások a következőképpen alakulnak:

1. x ≥ 0
2. és ≥0
3. 9x + 8y ≤ 144
4. 0,5 x + 0,8y ≤ 10

Az 1. és 2. kényszer képezi a korábban kitett nem-negativitás feltételeit, és az összes felvetett egyenlőtlenség lineáris. A 3. és a 4. korlátozás olyan értékeket tartalmaz, amelyeket nem szabad túllépni: 144 tojás és 10 kg cukor.

Objektív funkció

Végül, a célfüggvény a „x” mennyiségű fekete erdei sütemény plusz „y” mennyiségű szacripantinek előállítása során nyert profit. Az ár úgy szorozzuk meg, hogy megszorozzuk az árat az elkészített sütemények mennyiségével, és hozzáadjuk az egyes típusokhoz. Ez egy lineáris függvény, amelyet G (x, y) -nek hívunk:

G = 8x + 10y

Megoldási módszerek

A különféle megoldási módszerek a grafikus módszereket, a szimplex algoritmust és a belső pont módszerét tartalmazzák.

- Grafikus vagy geometriai módszer

Ha olyan kétváltozós probléma merül fel, mint az előző szakaszban, akkor a kényszerek meghatározják a xy síkban lévő sokszögű régiót, amelyet megvalósítható vagy életképességi régiónak hívnak.

3. ábra: A megvalósítható régió, ahol az optimalizálási probléma megoldása található. Forrás: Wikimedia Commons.

Ezt a régiót a restrikciós vonalakkal építik fel, amelyek a korlátozások egyenlőtlenségeiből nyert vonalak, és csak az egyenlőségjel segítségével működnek.

A pékség esetében, amely optimalizálni akarja a profitot, a kényszervonalak a következők:

1. x = 0
2. y = 0
3. 9x + 8y = 144
4. 0,5 x + 0,8y = 10

A vonalak által határolt régió összes pontja lehetséges megoldás, tehát végtelenül sok ilyen. Kivéve azt az esetet, amikor a megvalósítható terület üresnek bizonyul, ebben az esetben a felvetett problémának nincs megoldása.

Szerencsére a sütemény-probléma megoldásához a megvalósítható régió nem üres, az alábbiakban olvashatjuk.

4. ábra: A tésztaprobléma megvalósítható területe. A 0 erősítésű vonal keresztezi az eredetét. Forrás: F. Zapata a Geogebrával.

Az optimális megoldást, ha létezik, a célfüggvény segítségével találjuk meg. Például, amikor megpróbáljuk megtalálni a maximális G nyereséget, a következő sorral állunk rendelkezésünkre, amelyet iso-profit sornak hívunk:

G = k ₁ x + k ₂ y → y = -k ₁ x / k ₂ + G / k ₂

Ezzel a vonallal megkapjuk az összes olyan párt (x, y), amelyek egy adott G nyereséget adnak, tehát van egy vonalcsalád a G érték szerint, de mindegyik azonos -k ₁ / k ₂ meredekségű, tehát párhuzamos vonalak.

Az optimális megoldás

Most bebizonyíthatjuk, hogy a lineáris probléma optimális megoldása mindig a megvalósítható régió szélső pontja vagy csúcsa. Így:

Ha az eredethez legközelebb eső vonalnak egy teljes szegmense van a megvalósítható régióval, akkor azt mondják, hogy végtelen megoldások vannak. Ez az eset akkor fordul elő, ha az izgalmas profit vonalának meredeksége megegyezik a régiót korlátozó többi vonal lejtésével.

Tésztánkban a jelölt csúcsok A, B és C.

- Dantzig simplex módszere

A grafikus vagy a geometriai módszer két változóra alkalmazható. Bonyolultabb azonban, ha három változó létezik, és nagyobb számú változó esetében lehetetlen használni.

Kétnél több változóval kapcsolatos problémák kezelésekor a simplex módszert alkalmazzák, amely algoritmusok sorozatából áll a célfüggvények optimalizálása érdekében. A mátrixokat és az egyszerű számtani módszert gyakran használják a számítások elvégzéséhez.

A simplex módszer a megvalósítható megoldás kiválasztásával és annak optimális ellenőrzésével kezdődik. Ha igen, akkor már megoldottuk a problémát, de ha nem, folytatjuk az optimalizáláshoz közelebbi megoldást. Ha a megoldás létezik, akkor az algoritmus néhány próbálkozáson belül megtalálja.

Alkalmazások

A lineáris és a nemlineáris programozást számos területen alkalmazzák a legjobb döntések meghozatala érdekében a költségek csökkentése és a profit növelése szempontjából, amelyek nem mindig monetárisak, mivel időben mérhetők, például ha minimalizálni akarják a szükséges időt egy sor művelet végrehajtására.

Íme néhány mező:

-A marketingben arra használják, hogy megtalálják a média (szociális hálózatok, televízió, sajtó és mások) legjobb kombinációját egy adott termék reklámozására.

-A megfelelő feladatok kiosztása a vállalat vagy a gyár személyzete számára, vagy az ütemterv hozzárendelése.

-A leg táplálóbb élelmiszerek kiválasztásakor és a legalacsonyabb költséggel az állattenyésztés és a baromfi ágazatban.

Megoldott gyakorlatok

- 1. Feladat

Grafikusan oldja meg az előző szakaszokban felvetett lineáris programozási modellt.

Megoldás

Ábrázolni kell a problémában megadott korlátozások rendszere által meghatározott értékkészletet:

1. x ≥ 0
2. és ≥0
3. 9x + 8y ≤ 144
4. 0,5 x + 0,8y ≤ 10

Az 1. és 2. egyenlőtlenség által megadott terület megegyezik a derékszög síkjának első negyedével. A 3. és a 4. egyenlőtlenség vonatkozásában a korlátozási vonalak megkeresésével kezdjük:

9x + 8y = 144

0,5 x + 0,8y = 10 → 5x + 8y = 100

A megvalósítható terület egy négyszög, amelynek csúcsai A, B, C és D pontok.

A minimális nyereség 0, ezért a 8x + 10y = 0 sor az alsó határ, és az iso-profit sorok lejtője -8/10 = - 0,8.

Ez az érték különbözik a többi korlátozási vonal lejtéseitől, és mivel a megvalósítható terület korlátozott, az egyedi megoldás létezik.

5. ábra: Az 1. gyakorlat grafikus megoldása, amely bemutatja a megvalósítható régiót és a C megoldási pontot az említett régió egyik csúcsán. Forrás: F. Zapata.

Ez a megoldás egy -0,8 lejtővonalnak felel meg, amely áthalad az A, B vagy C ponton, amelynek koordinátái:

A (11; 5.625)

B (0; 12,5)

C (16,0)

Optimális megoldás

Kiszámoljuk a G értékét ezen pontok mindegyikére:

- (11; 5,625): G _A = 8 x 11 + 10 x 5,625 = 144,25

- (0; 12,5): G _B = 8 x 0 + 10 x 12,5 = 125

- (16, 0): G _C = 8 x 16 + 10 x 0 = 128

A legnagyobb nyereséget 11 fekete erdei sütemény és 5 625 szacripantin sütemény gyártása jelenti. Ez a megoldás megegyezik a szoftverben talált megoldással.

- 2. gyakorlat

Ellenőrizze az előző gyakorlat eredményét a legtöbb táblázatban, például az Excel vagy a LibreOffice Calc rendelkezésre álló Solver funkcióval, amely tartalmazza a Simplex algoritmust a lineáris programozás optimalizálásához.

Megoldás

6. ábra: Az 1. gyakorlatból származó megoldás részletei a Libre Office Calc táblán keresztül. Forrás: F. Zapata.

7. ábra: Az 1. gyakorlatból származó megoldás részletei a Libre Office Calc táblán keresztül. Forrás: F. Zapata.

Irodalom

1. Ragyogó. Lineáris programozás. Helyreállítva: brilliant.org.
2. Eppen, G. 2000. Működési kutatás az adminisztráció tudományában. 5.. Kiadás. Prentice Hall.
3. Haeussler, E. 1992. Matematika a menedzsment és a közgazdaságtan számára. 2.. Kiadás. Grupo Editorial Iberoamericana.
4. Hiru.eus. Lineáris programozás. Helyreállítva: hiru.eus.
5. Wikipedia. Lineáris programozás. Helyrehozva: es. wikipedia.org.