„Lineáris programozás” változatai közötti eltérés
(→Tesztkérdések modul) |
(→Tesztkérdések modul) |
||
13. sor: | 13. sor: | ||
* ... | * ... | ||
== Tesztkérdések modul == | == Tesztkérdések modul == | ||
− | *Adott egy G páros gráf. Mi a legnagyobb párosításának mérete? | + | *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. ) | (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. ) | ||
A lap 2005. október 22., 21:42-kori változata
Angol megnevezés: ...
Tartalomjegyzék
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. )
- ...