criss-cross algorithm

Angol

Főnév

criss-cross algorithm (tsz. criss-cross algorithms)

1. (informatika) A Criss-Cross algoritmus egy iteratív módszer a lineáris programozási feladatok megoldására, amely nem igényel kezdeti megengedett (feasible) megoldást. Ez szemben áll a klasszikus szimplex módszerrel, amely csak megengedett bázisok mentén halad. A Criss-Cross algoritmus azonban megengedett és nem-megengedett bázisokat is bejárhat.

---

📐 Cél és alkalmazás

A Criss-Cross algoritmus célja:

• Lineáris programozási (LP), kvadratikus programozási (QP), vagy általános lineáris egyenletrendszerek megoldása.
• Nem szükséges, hogy a kiindulási pont megfeleljen az egyenlőségeknek vagy az egyenlőtlenségeknek.
• Különösen hasznos degenerált eseteknél, ahol a szimplex módszer beleragadhat.

---

🔄 Működési elv

1. Kezdeti bázis (nem feltétlenül megengedett) kiválasztása.
2. Ellenőrizd:
   • Megfelelnek-e a feltételek? (Primal/dual feasibility)
3. Ha nem:
   • válassz egy megsértett feltételt, és válts ki egy új bázist pivotálással.
4. Ismételd, amíg:
   • elérjük a primal-dual feasible állapotot → megoldás kész
   • vagy az algoritmus kimutatja, hogy a feladat nem megoldható

A pivotálási szabályokat úgy választjuk meg, hogy az algoritmus végül konvergáljon, bár a bejárás nem feltétlenül monoton javuló.

---

🔍 Példahelyzet

A következő LP feladatot szeretnénk megoldani:

$${\text{Minimize }}c^{T}x\quad {\text{subject to }}Ax=b,\quad x\geq 0$$

A szimplex módszer csak akkor indulhat, ha van megengedett ${\textstyle x}$, ami kielégíti ${\textstyle Ax=b,x\geq 0}$-t.

A Criss-Cross ezzel szemben bármelyik bázisból el tud indulni, és megengedett és nem megengedett pontokon is lépegethet.

---

🧠 Előnyök

Előny	Leírás
❌ Nem kell feasible kiinduló megoldás	Bármely bázisból indulhat
🔄 Pivotálás dual/primal síkon	Tetszőleges irányba haladhat
📦 Kombinálható más módszerekkel	Használható QP, LCP feladatokban is
💡 Egyszerűbb implementáció	Nincs szükség mesterséges változókra (mint pl. a kétfázisú szimplexnél)

---

❗ Hátrányok

• Nem garantált a monoton célfüggvény-javulás
• Gyakran több lépést tesz, mint a szimplex
• Általában nem praktikus ipari méretű problémákra

---

📚 Történeti háttér

• Eredetileg Tamas Terlaky és más kutatók fejlesztették ki az 1980-as években.
• A szimplexhez hasonlóan pivot alapú módszer, de relaxált szabályokkal.

---

🧠 TL;DR

A Criss-Cross algoritmus egy olyan pivotálási eljárás lineáris programozásra, amely nem igényel kezdeti megengedett megoldást, és megengedett és nem-megengedett bázisokat is bejárhat. Rugalmas, de ritkán használják gyakorlatban – inkább elméleti célokra és alternatív elemzésekhez hasznos.

További információk

• criss-cross algorithm - Szótár.net (en-hu)
• criss-cross algorithm - Sztaki (en-hu)
• criss-cross algorithm - Merriam–Webster
• criss-cross algorithm - Cambridge
• criss-cross algorithm - WordNet
• criss-cross algorithm - Яндекс (en-ru)
• criss-cross algorithm - Google (en-hu)
• criss-cross algorithm - Wikidata
• criss-cross algorithm - Wikipédia (angol)