reduced cost

Angol

Főnév

reduced cost (tsz. reduced costs)

(informatika) A reduced cost (magyarul: csökkentett költség vagy korlátozó költség) egy kulcsfogalom a lineáris programozásban, különösen a szimplex algoritmus alkalmazása során. A reduced cost megmutatja, hogy egy változó egységnyi növelése mennyivel változtatná meg a célfüggvény értékét, ha az adott változó nincs a bázisban (azaz jelenleg nulla értéken van).

Ez a fogalom segít eldönteni, hogy mely változók belépése a bázisba segítene javítani az optimális megoldást – azaz milyen irányban érdemes haladni az optimalizációban.

1. Mi a reduced cost?

Tegyük fel, hogy egy lineáris programozási probléma célja egy célfüggvény maximalizálása:

${\text{Maximalizáljuk: }}Z=c_{1}x_{1}+c_{2}x_{2}+\dots +c_{n}x_{n}$

A reduced cost egy változóhoz tartozó érték, amely azt mutatja, hogy ha ez a változó belépne a bázisba, akkor mekkora lenne az egységnyi hatása a célértékre.

Maximalizálás esetén:
- Ha ${\textstyle {\text{reduced cost}}>0}$ , akkor nem érdemes beléptetni
- Ha ${\textstyle {\text{reduced cost}}<0}$ , akkor érdemes beléptetni (javítja a célfüggvényt)
Minimalizálás esetén:
- Ha ${\textstyle {\text{reduced cost}}<0}$ : nem jó, ne léptessük be
- Ha ${\textstyle {\text{reduced cost}}>0}$ : javítaná a célt

2. Matematikai definíció

Legyen:

${\textstyle c_{j}}$ : az eredeti költségtényező a nem bázisban lévő ${\textstyle x_{j}}$ -re
${\textstyle y}$ : a duális változók (árnyékárak, simplex multiplikátorok)
${\textstyle A_{j}}$ : a ${\textstyle x_{j}}$ változóhoz tartozó oszlop a korlátegyelet mátrixban

A reduced cost képlete:

${\bar {c}}_{j}=c_{j}-y^{T}A_{j}$

Ez azt mutatja meg, hogy a jelenlegi árstruktúra és korlátok mellett a változó valódi „hatása” mennyi lenne.

3. Egyszerű példa

Tegyük fel, hogy van egy termékgyártási feladat:

Termék A: 3 egység haszon
Termék B: 5 egység haszon

A megoldásban jelenleg csak termék A szerepel, termék B értéke nulla (nincs a bázisban). Ha a termék B reduced cost-ja: ${\textstyle -2}$ , akkor azt jelenti:

➡ Ha elkezdünk gyártani termék B-t, 2 egységgel nőne a haszon termelésenként. ➡ Tehát érdemes lenne beléptetni.

4. Grafikus értelmezés

Képzeljünk el egy megengedett tartományt (sokszög) és a célfüggvény szintvonalait.

A reduced cost mutatja, melyik irányban tudjuk “mozgatni” a célfüggvényt, hogy ne hagyjuk el a sokszöget, de javítsuk az értékét.

5. Kapcsolat a duálissal

A reduced cost összeköti a primál és duális problémát.

Ha egy változó duálisan nem korlátozó (azaz nem javít a célnál), akkor reduced cost = 0
A duál megoldás árnyékárainak segítségével számíthatjuk ki

6. Optimális megoldás és reduced cost

A szimplex algoritmus során:

Egy változó akkor része az optimális bázisnak, ha:
- Értéke pozitív, és
- Reduced cost-ja 0
Ha reduced cost ≠ 0 → a változó nincs a bázisban, és:
- Maximalizálásnál pozitív: nem léphet be
- Maximalizálásnál negatív: érdemes beléptetni

7. Mi történik a szimplex tábla során?

Minden szimplex iterációban kiszámoljuk a reduced costokat (pl. az alsó sorban a „Z - C” értékek), és megvizsgáljuk, van-e negatív érték (maximalizálásnál).

Ha van: → beléptetés szükséges, továbblépünk.

Ha nincs: → optimális megoldás megvan, nincs tovább javulás.

8. C++ jellegű logika (szövegesen)

Tegyük fel, van egy szimplex táblánk, és van egy nem bázisban lévő változó ${\textstyle x_{j}}$ .

A reduced cost számításához:

double reduced_cost = cj - dotProduct(dual_values, Aj);

cj: eredeti célfüggvény-együttható
dual_values: aktuális árnyékárak
Aj: korlátmátrix megfelelő oszlopa

9. Fontos megjegyzés

A reduced cost nem csak „szám”, hanem döntési információ:

Érdemes-e beléptetni a változót a megoldásba?
Segíti-e az optimalizációt?
Hoz-e jobb célértéket?

10. Összefoglalás

Fogalom	Jelentés
Reduced cost	Azt mutatja meg, hogy egy nem bázisban lévő változó egységnyi növelése hogyan hatna a célfüggvény értékére
Maximalizálásnál	Ha ${\textstyle {\bar {c}}_{j}<0}$ : érdemes beléptetni
Minimalizálásnál	Ha ${\textstyle {\bar {c}}_{j}>0}$ : érdemes beléptetni
Kapcsolat	A duál árnyékáraival számítható
Szerepe	Optimalizálási irány meghatározása a szimplex algoritmusban