Lineáris programozás

Angol megnevezés: ...

Történeti modul

• 1939: "A lineáris programozási feladatot Kantorovics szovjet matematikus már 1939-ben tárgyalta, de akkor még nem ismerték fel a téma fontosságát."

• 1947: "A lineáris programozást és a szimplex módszert Dantzig fedezte fel 1947-ben, utána az operációkutatás és a matematikai programozás rohamos fejlődésnek indult."

Ontológiai modul

• ...

Ellentmondások és vitatott kijelentések modulja

• ...

Definíciós modul

• ...

Tesztkérdések modul

• Adott egy G páros gráf. Mi a legnagyobb párosításának mérete?

(Minden e élre vezessünk be egy új változót (egy új betűt) xe-t. Ezen változóknak 0-1 értékeket adva kódolhatunk egy kiválasztott élhalmazt. kiválasztott e élre xe=1, míg e ki nem választása esetén xe=0. Egy kiválasztott élhalmaz akkor és csak akkor lesz párosítás, ha egyik csúcsnál sem fut össze kettő vagy több kiválasztott él. Ez algebrai módon is megfogalmazható. Az egy csúcsban összefügő élekhez rendelt változók összege nem haladja meg 1-et. Az összes csúcsra felírva ezt lineáris egyenlőtlenségek egy rendszerét kapjuk, amelynek 0-1 megoldásai pontosan a párosításokat kódoló értékelések. Ha ezen feltétel mellett a változók összegét (ami a kódolt élhalmaz elemszáma) maximálizáljuk, akkor a fenti párosítási problémát oldjuk meg. )

• ...

Ajánlott irodalmak modulja

• Monhor Davaadorzsín: Valós lineáris algebra és lineáris programozás, Műszaki Könyvkiadó, Budapest, 2001. [1]
• Rapcsák Tamás: Az operációkutatás kialakulásáról és hazai helyzetéről [2]
• lineáris programozás: [3]
• Páros gráfok párosításai és lineáris programozás: [4]
• Operáció kutatás: http://www.mgk.gau.hu/dokumentumok/Matematika/TANTARGYAK-PDF/TANTARGYAK-2005-06-1/MAT-3/