lineáris programozás

Magyar

Kiejtés

• IPA: [ ˈlinɛaːriʃproɡrɒmozaːʃ]

Főnév

lineáris programozás

1. (matematika, lineáris algebra, operációkutatás)

   Szinonima: lineáris optimalizálás

A lineáris programozás (Linear Programming, LP) egy matematikai optimalizálási módszer, amelynek célja egy lineáris célfüggvény optimalizálása (maximalizálása vagy minimalizálása) adott lineáris egyenlőtlenségek és egyenletek formájában megadott korlátok mellett.

Lineáris programozás alapfogalmai

1. Célfüggvény (Objective Function):

Az a függvény, amelyet maximalizálni vagy minimalizálni szeretnénk, például: $Z=c_{1}x_{1}+c_{2}x_{2}+\ldots +c_{n}x_{n}$

1. Korlátok (Constraints):

Egyenletek vagy egyenlőtlenségek, amelyek a változók értékét meghatározzák, például: $a_{1}x_{1}+a_{2}x_{2}\leq b$

1. Nemnegativitási feltétel:

Minden változó nemnegatív: $x_{1},x_{2},\ldots ,x_{n}\geq 0$

1. Döntési változók (Decision Variables):

Azok a változók, amelyeket optimalizálni szeretnénk, például $x_{1},x_{2},\ldots ,x_{n}$.

Egyszerű példa: Termelési optimalizálás

Egy gyár kétféle terméket állít elő: $x_{1}$ és $x_{2}$. A cél a profit maximalizálása.

Probléma megfogalmazása

• Célfüggvény:

Maximalizáljuk a profitot: $Z=40x_{1}+30x_{2}$, ahol $x_{1}$ az 1-es termék, $x_{2}$ a 2-es termék darabszámát jelenti.

• Korlátok:

Az erőforrások korlátozottak:

1. Gyártási idő:

$2x_{1}+x_{2}\leq 100$

1. Anyaghasználat:

$x_{1}+2x_{2}\leq 80$

1. Nemnegativitási feltétel:

$x_{1},x_{2}\geq 0$

Grafikus megoldás

1. Határozzuk meg a korlátok által definiált tartományt:

Az $x_{1}$ és $x_{2}$ értékek legyenek olyanok, hogy minden korlátnak megfeleljenek. Ezeket a korlátokat egy koordináta-rendszerben ábrázoljuk.

1. Határozzuk meg a metszéspontokat:

• $2x_{1}+x_{2}=100$: Ez egy egyenes, amelyet a tengelymetszetek $x_{1}=50$ ($x_{2}=0$) és $x_{2}=100$ ($x_{1}=0$) adnak meg.
• $x_{1}+2x_{2}=80$: Itt a tengelymetszetek $x_{1}=80$ ($x_{2}=0$) és $x_{2}=40$ ($x_{1}=0$).

1. Keressük a célfüggvény optimumát:

A célfüggvény $Z=40x_{1}+30x_{2}$ értéke a lehetséges tartomány szélein lesz maximális. Az ilyen metszéspontok közül válasszuk ki a legnagyobb $Z$-értéket.

Másik példa: Szállítási probléma

Egy vállalat három raktárból ($A$, $B$, $C$) szeretne termékeket szállítani két vevőhöz ($X$, $Y$). A szállítási költségek:

• $A\to X=5$, $A\to Y=6$
• $B\to X=4$, $B\to Y=3$
• $C\to X=8$, $C\to Y=7$

Probléma megfogalmazása

• Célfüggvény:

Minimalizáljuk a szállítási költséget: $Z=5x_{AX}+6x_{AY}+4x_{BX}+3x_{BY}+8x_{CX}+7x_{CY}$

• Korlátok:

1. A raktárak kapacitása:

$x_{AX}+x_{AY}\leq 100$, $x_{BX}+x_{BY}\leq 120$, $x_{CX}+x_{CY}\leq 80$

1. A vevők igényei:

$x_{AX}+x_{BX}+x_{CX}\geq 150$, $x_{AY}+x_{BY}+x_{CY}\geq 120$

1. Nemnegativitási feltétel:

$x_{AX},x_{AY},x_{BX},x_{BY},x_{CX},x_{CY}\geq 0$

Fordítások

• angol: linear programming (en), linear optimization (en)
• német: lineare Programmierung (de), lineare Optimierung (de)
• orosz: линейное программирование (ru) (linejnoje programmirovanije)

További információk

• lineáris programozás - Értelmező szótár (MEK)
• lineáris programozás - Etimológiai szótár (UMIL)
• lineáris programozás - Szótár.net (hu-hu)
• lineáris programozás - DeepL (hu-de)
• lineáris programozás - Яндекс (hu-ru)
• lineáris programozás - Google (hu-en)
• lineáris programozás - Helyesírási szótár (MTA)
• lineáris programozás - Wikidata
• lineáris programozás - Wikipédia (magyar)