Lineáris programozás

1. Sablon:Label

   Sablon:Syn

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+\dots +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\le b$

1. Nemnegativitási feltétel:

Minden változó nemnegatív: $x_1,x_2,\dots ,x_n\ge 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,\dots ,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\le 100$

1. Anyaghasználat:

$x_1+2x_2\le 80$

1. Nemnegativitási feltétel:

$x_1,x_2\ge 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}\le 100$, $x_{BX}+x_{BY}\le 120$, $x_{CX}+x_{CY}\le 80$

1. A vevők igényei:

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

1. Nemnegativitási feltétel:

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

• Sablon:En: Sablon:T, Sablon:T
• Sablon:De: Sablon:T, Sablon:T
• Sablon:Ru: Sablon:T