lineáris programozás

• IPA:

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.

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

Az a függvény, amelyet maximalizálni vagy minimalizálni szeretnénk, például: ${\displaystyle 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: ${\displaystyle a_{1}x_{1}+a_{2}x_{2}\leq b}$

1. Nemnegativitási feltétel:

Minden változó nemnegatív: ${\displaystyle 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 ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$.

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

• Célfüggvény:

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

• Korlátok:

Az erőforrások korlátozottak:

1. Gyártási idő:

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

1. Anyaghasználat:

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

1. Nemnegativitási feltétel:

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

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

Az ${\displaystyle x_{1}}$ és ${\displaystyle 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:

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

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

A célfüggvény ${\displaystyle 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 ${\displaystyle Z}$-értéket.

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

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

• Célfüggvény:

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

• Korlátok:

1. A raktárak kapacitása:

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

1. A vevők igényei:

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

1. Nemnegativitási feltétel:

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

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

• 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)