Gyakran olvassuk, hogy egy üzemben, építkezésnél vagy közlekedési vállalatnál a munka jobb megszervezése, felesleges szállítások megszüntetése útján minden befektetés nélkül megtakarítást értek el, néha nem is kicsit. Nyilvánvaló, hogy ezeket gondos vizsgálatok és számítások előzték meg. Felvetődik a kérdés, milyen matematikai módszerek segítségével lehet ilyen bonyolult kérdéseket egyáltalában matematikai formába önteni, majd megoldani? A legegyszerűbb, és éppen ezért a legelterjedtebben használt matematikai módszer, amely tervező és közgazdász szakemberek rendelkezésére áll ilyen problémák megoldására, a lineáris programozás. Ennek a köréből mutatunk be egy példát, amely középiskolai ismeretekkel is megoldható.

présgép:2y≦180,csiszológép:2x+y≦100,festőműhely:5x+5y≦300.

 

A feltételek matematikai modellje tehát egy kétismeretlenes egyenlőtlenségrendszer.
Az üzemrész annyiféle termelési programot készíthet a két termék gyártására, ahány e négy korlátnak, illetve egyenlőtlenségnek eleget tevő számpárt tudunk az $x$ és $y$ lehetséges értékeiből összeállítani. Magától értetődik, hogy $x$ és $y$ pozitívok. Ez két újabb egyenlőtlenséget jelent:

$\begin{array}{c}{\displaystyle x>\mathrm{0,}y>\mathrm{0,}}\end{array}$

és így egyenlőtlenségrendszerünk végül is 6 egyenlőtlenségből áll.
Az egyenlőtlenségrendszert derékszögű koordinátarendszerben ábrázolva, grafikus úton fogjuk megoldani.

 

2. Kétismeretlenes elsőfokú egyenlőtlenség rendszerek grafikus megoldása. Az $x>0$ egyenlőtlenség megoldásait azok a pontok ábrázolják, amelyeknek az abszcisszája pozitív, ordinátája tetszőleges, vagyis az $Y$-tengelytől (az $x=0$ egyenlettel jellemzett egyenestől) jobbra levő pontok (félsík). Hasonlóan az $y>0$ egyenlőtlenségnek eleget tevő pontok az $X$-tengely (az $y=0$ egyenes) felett helyezkednek el. A két feltételnek egyszerre az $X$- és $Y$-tengely pozitív fele által határolt síkrész (az első síknegyed) pontjai tesznek eleget.
Hasonlóan a feladat első egyenlőtlenségének, amely

$\begin{array}{c}{\displaystyle x\leqq 45}\end{array}$

alakban irható, az $Y$-tengellyel párhuzamos $x=45$ egyenestől ,,balra'' levő félsík pontjai felelnek meg, de most hozzászámítva a határegyenest is, annak megfelelően, hogy a kisebb jel mellett most az egyenlőség is meg van engedve.
A második egyenlőtlenséget

$\begin{array}{c}{\displaystyle Y\leqq 40}\end{array}$

alakban írva, ennek az $X$-tengellyel párhuzamos $y=40$ egyenes és az alatta levő félsík pontjai tesznek eleget.

 

 

1. ábra

 

Vizsgáljuk most a csiszológép szolgáltatta

$\begin{array}{c}{\displaystyle 2x+y\leqq 100}\end{array}$

(1)

egyenlőtlenséget. Az egyenlőség jelének ismét a

$\begin{array}{c}{\displaystyle 2x+y=100}\end{array}$

(2)

egyenes pontjai felelnek meg (1. ábra). Válasszunk ezen egy pontot, pl. $x_0=35$ abszcisszával, így ordinátája $y_0=100-2x_0=30$. Ekkor az (1) egyenlőtlenségnek az $x_0$ abszcisszájú pontok közül azok tesznek eleget, amelyeknek az ordinátáira

$\begin{array}{c}{\displaystyle y\leqq 100-2x_0=y_0=30.}\end{array}$

Az $x_0=35$ egyenes pontjai közül az (1) egyenlőtlenségnek tehát a (2) egyenes alatti félegyenesen levők felelnek meg, és ugyanez áll minden más $x_0$, értékre is. Az (1) egyenlőtlenségnek tehát a (2) egyenes és az alatta levő félsík pontjainak koordinátái tesznek eleget. (Ugyanígy $y_0$ értékét rögzítve és a megfelelő $x$ értékeket keresve fogalmazhattuk volna állításunkat úgy is, hogy a (2) egyenes és a tőle balra eső félsík pontjai ábrázolják (1) megoldásait.)
A negyedik egyenlőtlenség így írható:

$\begin{array}{c}{\displaystyle x+y\leqq \mathrm{60,}y\leqq 60-x\mathrm{.}}\end{array}$

Az előbbihez hasonlóan ennek az

$\begin{array}{c}{\displaystyle x+y=60}\end{array}$

egyenes és az alatta levő félsík pontjai tesznek eleget.
Ezzel a feladatban szereplő egyes egyenlőtlenségek geometriai tartalmát külön‐külön megállapítottuk. Mielőtt eredményeinket összegezzük, nézzünk még egy példát kétismeretlenes elsőfokú egyenlőtlenség ábrázolására, hogy a negatív együttható szerepét is lássuk.

 

 

2. ábra

 

Keressük pl. a

$\begin{array}{c}{\displaystyle 3x-4y<12}\end{array}$

(3)

egyenlőtlenség megoldásait ábrázoló pontokat. Az előzőkhöz hasonlóan járva el a

$\begin{array}{c}{\displaystyle 3x-4y=12}\end{array}$

(4)

egyenesen (2. ábra) pl. az $x_0=5$ abszcisszájú pont ordinátája $y_0=\frac{12-4\cdot 5}{-4}=\frac{4}{3}$. Az egyenlőtlenségnek eleget tevő $x_0$ abszcisszájú pontokra

$\begin{array}{c}{\displaystyle 3x_0-4y<\mathrm{12,}-4y<12-3x_0=-3.}\end{array}$

Most ‐4-gyel kellene elosztani az egyenlőtlenséget. Szorozzunk először $-1$-gyel, utána a 4-gyel való osztás már nem okoz problémát. Az egyenlőtlenség teljesülése azt jelenti, hogy $-4y$ negatív és abszolút értéke (tehát $4y$) nagyobb mint 3:

$\begin{array}{c}{\displaystyle 4y>3.}\end{array}$

Amit itt láttunk, minden esetre érvényes: ha egy egyenlőtlenséget $-1$-gyel, általában egy negatív számmal megszorzunk vagy elosztunk, akkor az egyenlőtlenség jele az ellenkezővel helyettesítendő.¹
A (3)-nak eleget tevő $x_0$ abszcisszájú pontokra így $y>3/4$ adódik, vagyis az $x_0=5$ egyenesnek a (4) egyenes fölötti része, és ismét ugyanez áll minden más $x_0$ értékre is. A (3) egyenlőtlenséget tehát a (4) egyenes fölötti félsík pontjainak a koordinátái elégítik ki, az egyenes pontjait ezúttal már nem véve hozzá, mivel (3)-ban az egyenlőség már nincs megengedve.
A fentiekben látott módon minden kétismeretlenes elsőfokú egyenlőtlenség geometriai jelentését meg tudjuk állapítani. Térjünk ezután vissza eredeti feladatunk megoldásához.

 

3. A célszerű munkaprogramok megkeresése. Az

${\displaystyle \begin{array}{cccc}\hfill {\displaystyle x}& {\displaystyle >\mathrm{0,}}\hfill & {\displaystyle y}\hfill & \hfill {\displaystyle >\mathrm{0,}}\\ \hfill {\displaystyle x}& {\displaystyle \leqq \mathrm{45,}}\hfill & {\displaystyle y}\hfill & \hfill {\displaystyle \leqq \mathrm{40,}}\\ \hfill {\displaystyle 2x+y}& {\displaystyle \leqq \mathrm{100,}}\hfill & {\displaystyle x+y}\hfill & \hfill {\displaystyle \leqq 60}\end{array}}$

egyenlőtlenségek mindegyikének azon pontok koordinátái tesznek eleget, amely pontok mindegyik egyenlőtlenségnek megfelelő félsíkon rajta vannak, vagyis a félsíkok közös részeinek a pontjai. Ez a közös rész egy konvex hatszög (3. ábra), jelöljük $H$-val. $H$ minden pontja egy lehetséges munkaprogramot képvisel, azaz végtelen sokféleképpen lehet az adott határok között a gépeket üzemeltetni (vagy esetleg állni hagyni). Mivel azonban példánkban a termékek előállítási ideje csekély, nem érdemes félig kész munkadarabokat az egyik műszakból a másikba átvinni. Ezért indokolt, hogy csak a pozitív egész megoldásokat keressük.

 

 

3. ábra

 

Ezzel sem válik azonban a munkaprogram egyértelművé, mert $H$-ban és határának a tengelydaraboktól különböző részén több egész koordinátájú pont van. A tulajdonképpeni kérdés éppen az, hogy e sokféle program közül melyik lesz a legjobb, az ún. optimális program? Ennek eldöntése csak akkor lehetséges, ha megadjuk, hogy milyen szempontból keressük az optimális programot. Lehet, hogy ‐ például ‐ a maximális számú terméket biztosító programot tekintjük a legjobbnak, vagy a maximális termelési érték elérése a célunk, vagy maximális nyereségre törekszünk, stb. Erre 3 példát mutatunk be. Tegyük fel, hogy

 

 

a) Vizsgáljuk meg először azt, milyen program mellett lesz a termelési érték maximális. A mondott feltételek mellett egy bizonyos $T$ termelési érték a

$\begin{array}{c}{\displaystyle T=2x+5y}\end{array}$

összefüggés alapján számítható ki. Egy adott $T$ érték sokféle $x$ és $y$ darabszám mellett állhat elő, és az ($x$, $y$) pontok a $2x+5y=T$ egyenesen helyezkednek el. Különböző $T$ értékeket választva egymással párhuzamos egyeneseket kapunk. A 4. ábrán a 160, 200, 240 és 280 Ft termelési értékhez tartozó egyeneseket rajzoltuk meg.

 

 

4. ábra

 

 

5. ábra

 

A 4. ábrát $H$-ra ráhelyezve (5. ábra) látszik, hogy a 200 Ft érték sokféle programmal is elérhető, ugyanis a $T=200$ értékhez tartozó egyenesnek egy egész szakasza esik bele $H$-ba. A 280 Ft-os érték viszont sehogy sem érhető el, mert a megfelelő egyenesnek nincs közös pontja $H$-val. Az optimális megoldást szolgáltató egyenesnek e két egyenes közé kell esnie. A vonalzó párhuzamos eltolásával könnyen megállapítható, hogy a $T=240$ Ft termelési értékhez tartozó

$\begin{array}{c}{\displaystyle 2x+5y=240}\end{array}$

egyenes szolgáltatja az optimális megoldást, mert ez a legnagyobb $T$, amelyhez tartozó egyenesnek van közös pontja $H$-val. És mivel ennek az egyenesnek $H$-val csak egy közös pontja van, a (20; 40) pont, ezért csak egyetlen optimális megoldás van: az üzemrész az adott feltételek mellett egy műszak alatt akkor állítja elő a legnagyobb termelési értéket (240 Ft-ot), ha az I. termékből 20, a II-ból pedig 40 darabot készít.

 

 

6. ábra

 

 

7. ábra

 

b) Milyen programot kell készítenünk, ha a maximális nyereség a cél? Egy adott $N$ nyereség olyan $x$ és $y$ termékszámok mellett érhető el, amelyekre

$\begin{array}{c}{\displaystyle 0\mathrm{,}72x+0\mathrm{,}35y=N\mathrm{.}}\end{array}$

Néhány $N$ értékhez tartozó egyenest és az egyetlen optimális pontot szolgáltató, az $N=35\mathrm{,}90$-hez tartozó egyenest a 6. ábrán tüntettük fel. Az üzemrész tehát akkor hozza a legnagyobb hasznot, ha az I. termékből 45, a II.-ból 10 darabot gyárt műszakonként.
c) Keressük meg azt a programot, amely a maximális darabszámot biztosítja. Az előzőekhez hasonlóan most a különböző $D$ darabszámokhoz tartozó

$\begin{array}{c}{\displaystyle x+y=D}\end{array}$

párhuzamos egyeneseket kell hozzárajzolnunk a 3. ábrához. A 7. ábrán a $D=40$, $D=60$ és a $D=80$ értékhez tartozó egyeneseket látjuk. Itt ‐ az eddigi esetektől eltérően ‐ az optimális megoldást szolgáltató $D=60$ értékhez tartozó egyenesnek és $H$-nak több közös pontja van: a vastagon kihúzott szakasz, mert a darabszámra jellemző egyenesek párhuzamosak $H$ egyik határoló egyenesével. Ez azt jelenti, hegy a gépek kapacitása egy műszakban maximálisan 60 db termék elkészítését teszi lehetővé, de ez többféle módon is lehetséges: mindkét termékből legalább 20 darabot kell, és legfeljebb 40 darabot lehet gyártani, mert a vastagon kihúzott szakasz a (20; 40) ponttól a (40; 20) pontig terjed.
Foglaljuk táblázatba eddigi eredményeinket:

A tervezés során természetesen sok más szempont is felmerülhet (önköltség, energiafelhasználás stb.). Ezek alapján tovább lehetne bővíteni ezt a táblázatot. De már az eddigi eredmények is választ adnak néhány, a termelés megszervezése szempontjából fontos kérdésre. A táblázat megmutatja a különféle optimális pontokat ‐ ha ilyenek vannak ‐, vagy optimális határokat ‐ példánkban a c) eset ‐, amelyeken belül, esetleg még más szempontokat is figyelembe véve, a szervezők a legmegfelelőbb programot választhatják ki. Esetünkben pl. a maximális termelési értéket és a maximális darabszámot egyszerre is elérheti az üzemrész, ha az I. termékből 20, a II-ból pedig 40 darabot termel.
Az ábrákról az is megállapítható, hogy adott esetben meddig lehet észszerű engedményt tenni valamely szempont szerinti optimális program rovására. Leolvasható pl., hogy ha a maximális termelési érték elérése a cél, akkor csak a présgép és a festőműhely kapacitását használjuk ki teljesen, mert ez az optimális pont éppen a présgép és a festőműhely miatti korlátozást ábrázoló egyenesek metszéspontja. Ekkor a többi gép bizonyos ideig állni kénytelen. Viszont ha a maximális nyereség elérésére törekszünk, a marógép és a csiszológép dolgozik teljes kapacitással és a többi számára tervezhetünk más munkát is.

 

 

8. ábra

 

4. Megjegyzés. A tárgyalt feladatban láttuk, hogy bizonyos szempont szerint (termelési érték, nyereség) egyetlen optimális program létezik, más szempont szerint (darabszám) több (végtelen sok) optimális program is lehetséges. Előfordulhat azonban természetesen az az eset is, hogy a feladat egyáltalában nem oldható meg, mert a feltételi egyenlőtlenségek ellentmondanak egymásnak. Ilyen p1. az alábbi egyenlőtlenségrendszer:

${\displaystyle \begin{array}{cc}\hfill {\displaystyle 5x+6}& {\displaystyle y>\mathrm{30,}}\hfill \\ \hfill {\displaystyle 2x+\phantom{6}}& {\displaystyle y<\mathrm{4,}}\hfill \\ \hfill {\displaystyle }& {\displaystyle x\geqq \mathrm{0,}}\hfill \\ \hfill {\displaystyle }& {\displaystyle y\geqq 0.}\hfill \end{array}}$

Lásd a 8. ábrát.

 

5. A lineáris programozás feladata általában. A föntiekben egy nagyon egyszerű példával igyekeztünk illusztrálni a lineáris programozást. Általában egy üzem munkáját nem két, hanem sokkal több adattal lehet leírni. Ezek megválasztására a termelés külső feltételei (a fenti példában a gépek kapacitása) általában csak tág feltételeket szabnak. A feladat ezek közt a feltételek közt olyan munkaprogramot találni, amely mellett valamilyen, a termelést leíró adatoktól függő mennyiség a lehető legnagyobb vagy a lehető legkisebb lesz.
A termelési feltételek adta korlátozásokat általában egyenlőtlenségekkel lehet leírni, és azt kell megállapítanunk, hogy egy további megadott függvény az egyenlőtlenségrendszert kielégítő értékrendszerek közül melyikre vagy melyekre veszi fel a legnagyobb, vagy melyikre a legkisebb értéket.
A tárgyalt példát két körülmény tette egyszerűvé, az, hogy a változóknak csak elsőfokú kifejezései léptek fel és hogy csak két változó szerepelt.
Az, hogy csak elsőfokú (latin szakkifejezéssel lineáris) kifejezések lépnek fel, azt eredményezi, hogy számítások közben csak a négy alapműveletre van szükség. Az ilyen számítások igen könnyen végezhetők gépekkel. Ezeknek a fontosságát növeli az is, hogy a gyakorlati problémáknál igen gyakran lépnek fel egyenes arányosságban levő mennyiségek (tehát elsőfokú kifejezéssel jellemezhető összefüggések), vagy legalábbis jó közelítésben arányosnak tekinthetők. Az ilyen esetekkel foglalkozik a lineáris programozás.
Általánosan tehát így fogalmazható a probléma: valamilyen $x_1$, $x_2$, $\text{...}$, $x_n$ mennyiségre teljesülnie kell bizonyos²
${\displaystyle \begin{array}{c}\hfill {\displaystyle a_{11}{x}_1+a_{12}{x}_2+\text{...}+a_{1n}{x}_n\leqq b_1\mathrm{,}}\hfill \\ \hfill {\displaystyle a_{21}{x}_1+a_{22}{x}_2+\text{...}+a_{2n}{x}_n\leqq b_2\mathrm{,}}\hfill \\ \hfill {\displaystyle \text{...}\text{...}\text{...}\text{...}\text{...}\text{...}\text{...}\text{...}\text{...}\text{...}\text{...}}\hfill \\ \hfill {\displaystyle a_{k1}{x}_1+a_{k2}{x}_2+\text{...}+a_{kn}{x}_n\leqq b_k}\hfill \end{array}}$

egyenlőtlenségeknek, és kérdezzük, hogy ezen feltételek mellett egy

$\begin{array}{c}{\displaystyle f=c_1{x}_1+c_2{x}_2+\text{...}+c_n{x}_n}\end{array}$

kifejezés mely $x_1$, $x_2$, $\text{...}$, $x_n$ értékrendszerre veszi fel a maximális értékét és mi ez a maximális érték.
A két változó annyiban jelentett könnyebbséget, hogy a matematikai feladatot geometriailag tudtuk szemléltetni, és egyenesek húzásával, főleg pedig egyenesek párhuzamos elmozgatásával megoldani. Ez a lehetőség elvben 3 változó esetén a térben még rendelkezésre áll (bár gyakorlatban nehéz megvalósítani), több változó esetén azonban a geometriai szemléltetést nem tudjuk felhasználni. Ilyen esetben ‐ és a gyakorlatban ez fordul elő a legtöbbször ‐ algebrai jellegű megoldást kell keresnünk. Többféle ilyen megoldási módszer is ismeretes. Bár ezek elvileg mind elemiek, azonban nagy mennyiségű számítást igényelnek.³

 

6. A szállítási probléma. A lineáris programozás körébe tartozó egyik jellegzetes feladattípus az ún. szállítási probléma. Bizonyos anyagot több ismert telephely használ fel és több gyár állít elő (p1. téglát építkezéshez). Ismerjük az egyes gyárak termelési kapacitását, az egyes telephelyek igényét, és ismerjük a szállítási költségeket, amelyek különböző gyárak és telephelyek között különbözők lehetnek (pl. más szállítási eszközök, terepviszonyok, egyéb miatt). Találomra kialakult megoldásnál előfordul az is, hogy két távoli felvevőhely kölcsönösen a másikhoz közeli gyárból szállít (keresztszállítás). Az ilyeneket könnyű megszüntetni, a leggazdaságosabb megoldást azonban találgatás útján nem lehet megtalálni. A lineáris programozás módszereivel megkereshető a szállítások olyan elosztása, amely mellett a szállítási költség minimális. Ha a felvevőhelyek igényének összege egyenlő a gyárak együttes termelésével, akkor a feltételeket ‐ az előző feladattól eltérően ‐ nem egyenlőtlenségek, hanem egyenletek segítségével írhatjuk fel. Ezen feltételi egyenletrendszer általában több ismeretlent tartalmaz, mint egyenletet, ennek teljesülése mellett keressük a költségek minimumát. Az optimális megoldás meghatározása és gyakorlati megvalósítása ilyen feladatoknál néhány esetben váratlanul nagy mérvű megtakarítást tett lehetővé.

 

7. Történeti megjegyzések. Közgazdasági problémák megoldására matematikai módszerek alkalmazását már két évszázaddal ezelőtt elkezdték, de az első, gyakorlatilag is jól használható eredmények csak a XX. század első harmadában váltak ismeretessé. Ezek W. W. Leontiff orosz, valamint Neumann János magyar származású amerikai matematikusok nevéhez fűződnek.
Az egyre magasabb fokú szervezettséget követelő ipari fejlődés nyomán mind a Szovjetunióban, mind a kapitalista államokban (főleg az Egyesült Államokban) a második világháború előtt és alatt csaknem egy időben jelentek meg a lineáris programozás alkalmazásait bemutató, majd a második világháború után a lineáris programozás elméletét megalapozó és továbbfejlesztő munkák.
Az első olyan mű, amely lineáris programozással old meg feladatokat, L. V. Kantorovics szovjet matematikus 1939-ben megjelent cikke. Vele csaknem egy időben, 1941-ben F. L. Hitchook amerikai matematikus közölt egy megoldást a szállítási problémára. Megemlítjük, hogy a szállítási probléma egy másik megoldása, az ún. ,,magyar módszer'' Kőnig Dénes, Egerváry Jenő magyar és H. W. Kuhn amerikai matematikusok nevéhez fűződik.
A lineáris programozási feladatok megoldására szolgáló egy általános módszer, az ún. szimplex módszer, 1947-ben alakult ki G. B. Dantzig amerikai matematikus munkássága nyomán.
Azóta már több olyan módszert is kidolgoztak, amely nem csupa elsőfokú összefüggés esetén is alkalmazható.
 Scharnitzky Viktor, Surányi János

---

¹Az olvasóra bízzuk annak átgondolását, hogy ez akkor is helyes, ha a nagyobb oldalon pozitív szám áll. (A kisebb oldalon ez esetben állhat pozitív szám is, negatív is.)

²Célszerű volt két indexes jelölést használni ($a_{11}\mathrm{,}{a}_{12}\mathrm{,}\text{...}\mathrm{,}{a}_{ij}$, olv. ,,á egy, egy'', ,,á egy, kettő'', általában ,,á i, jé''). Az első index jelöli, hogy hányadik egyenlőtlenségről van szó, a második, hogy abban hányadik ismeretlen együtthatójáról.

³Az érdeklődő olvasó részletes ismertetésüket megtalálhatja Krekó Béla Lineáris programozás című könyvében (Budapest, Közgazdasági és Jogi Kiadó, 1962).