---

Tartalom

1. Előszó

2. A lineáris programozási feladat
2.1. A lineáris programozási feladat
2.2. A duális feladat
2.3. Konvex halmazok az euklideszi térben
2.4. Az LP feladat megoldásairól

3. Dualitás, optimalitás
3.1. Dualitás, optimalitás

4. A lineáris programozási feladat megoldása
4.1. A szimplex módszer
4.2. A szimplex módszer megalapozása
4.3. Kiinduló lehetséges bázis előállítása
4.4. A duális megoldás a szimplex táblában
4.5. Számpélda a szimplex módszer alkalmazására

5. Lineáris programozáshoz vezető feladatok
5.1. A döntési alapprobléma
5.2. Hiperbolikus vagy törtprogramozás
5.3. Valószínűséggel korlátozott lineáris programozási modell
5.4. Többcélú programozás
5.5. Célprogramozás
5.6. Kétlépcsős programozási modell

6. Történet, ajánlott könyvek

---

Előszó

E jegyzet célja az, hogy a lineáris programozás elméletét belehelyezze abba a gondolatkörbe, amelyhez a Budapesti Közgazdaságtudományi és Államigazgatási Egyetem hallgatói az első szemeszterekben hozzászoktak, és amelyre szükségük lesz különösen azoknak a hallgatóknak, akik a közgazdaságtant elméleti igénnyel készülnek művelni. A tárgyalásmód nem lesz éppen változatos, főként állítások és bizonyítások sorozatából áll, amelyeket példák és gyakorlatok ritkán illusztrálnak. Bár számítunk az olvasó lineáris algebrai tájékozottságára, összefoglaljuk mindazokat (de csak azokat) a fogalmakat és állításokat, többségükben bizonyításaikkal együtt, amelyeket a lineáris programozási feladat vizsgálatánál igénybe veszünk.

Először bemutatjuk az LP feladatot, majd származtatunk egy másik lineáris programozási feladatot, amelyet duális feladatnak nevezünk, a kiinduló feladatot pedig ebben az összefüggésben primál feladatnak. Célunk az, hogy bemutassuk a lineáris programozási feladat szerkezetét, tulajdonságait, a primál-duál feladatpár kapcsolatát, és a két feladat együttes megoldására szolgáló sok módszer közül a legismertebbet: a szimplex módszert.

A tárgyalás középpontjában a primál-duál feladatpár tanulmányozása és a dualitási tétel áll. A dualitási tétel kimondásához, bizonyításához szükségünk lesz a Farkas tételre, annak bizonyításához pedig a konvex halmazok elméletében központi jelentőséggel bíró szeparációs tételre, amelynek azonban csak azt a változatát mondjuk ki és bizonyítjuk itt, amelyet a Farkas tétel bizonyításához felhasználunk. Ennek megfelelően a tárgyalás felépítése a következő. A duális feladat bevezetése után néhány halmazelméleti illetve konvexitással kapcsolatos fogalom, a szeparációs tétel és a Farkas tétel következik. Ezután az LP feladat megoldásainak elhelyezkedéséről lesz szó és bizonyítjuk a dualitási tételt. A dualitási tétel folyománya a nagyjelentőségű komplementaritási tétel, amely rávilágít az LP feladat optimális megoldásainak jellegére is. Ezzel teljes egészében előkészítettük a szimplex módszert, amelynek ezután csak a leírása marad hátra. Végül sor kerül a szimplex tábla szerkezetének a tanulmányozására abból a célból, hogy lássuk, hogyan befolyásolják a feladat paraméterei az optimális megoldást és az optimális célfüggvényértéket. A szimplex módszer alkalmazását, a lehetséges kimeneteleket és a feladat paraméterei változásának a következményeit számpélda illusztrálja.

Az utolsó fejezetben lineáris programozási feladatra visszavezethető nemlineáris programozási feladatok közül bemutatunk néhányat, azzal a céllal is, hogy az olvasó érdeklődését felkeltsük a matematikai programozás néhány más ága, pl. a sztochasztikus programozás és a hiperbolikus programozás, és a döntéselméletben fontos szerepet játszó célprogramozás illetve többcélú programozás iránt.

Az ajánlott irodalommal zárul a jegyzet. Néhány mérföldkőnek tekinthető könyvet sorolunk itt fel és néhány jellemző adatot, magyar vonatkozást a lineáris programozást is magában foglaló operációkutatás történetéből.

---