egészértékű programozás

• IPA:

egészértékű programozás

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

Az egészértékű programozás az optimalizálási problémák egy speciális esete, ahol a döntési változók csak egész számok lehetnek. Ez különbözik a lineáris programozástól, amely lehetővé teszi a folyamatos értékeket.

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

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

1. Korlátok (Constraints):

A változók értékét korlátozó lineáris egyenletek vagy egyenlőtlenségek: ${\displaystyle a_{1}x_{1}+a_{2}x_{2}\leq b}$

1. Egészértékűségi feltétel:

Minden döntési változó (${\displaystyle x_{i}}$) egész szám: ${\displaystyle x_{1},x_{2},\ldots ,x_{n}\in \mathbb {Z} }$

1. Tiszta egészértékű programozás (Pure Integer Programming):

Minden változó egész szám.

1. Vegyes egészértékű programozás (Mixed Integer Programming, MIP):

Csak néhány változó egész, mások folyamatosak lehetnek.

1. Bináris programozás (Binary Programming):

A változók értéke csak ${\displaystyle 0}$ vagy ${\displaystyle 1}$ lehet.

Egy gyár kétféle terméket gyárt: ${\displaystyle x_{1}}$ és ${\displaystyle x_{2}}$. Minden termék értéket és időt igényel a gyártáshoz. A cél a profit maximalizálása az alábbi korlátok mellett:

• Célfüggvény:

${\displaystyle Z=40x_{1}+30x_{2}}$

1. Korlátok:
2. Gyártási idő korlát:

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

1. Anyaghasználat:

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

1. Nemnegativitási és egészértékűségi feltétel:

${\displaystyle x_{1},x_{2}\geq 0,\quad x_{1},x_{2}\in \mathbb {Z} }$

from pulp import LpMaximize, LpProblem, LpVariable, lpSum

# Probléma definiálása
problem = LpProblem("Gyártási_Optimalizáció", LpMaximize)

# Döntési változók definiálása
x1 = LpVariable("x1", lowBound=0, cat="Integer")  # Egészértékű változó
x2 = LpVariable("x2", lowBound=0, cat="Integer")  # Egészértékű változó

# Célfüggvény hozzáadása
problem += 40 * x1 + 30 * x2, "Profit"

# Korlátok hozzáadása
problem += 2 * x1 + x2 <= 100, "Gyártási_idő_korlát"
problem += x1 + 2 * x2 <= 80, "Anyaghasználati_korlát"

# Probléma megoldása
status = problem.solve()

# Eredmények kiíratása
print("Optimalizáció állapota:", problem.status)
print("Maximális profit:", problem.objective.value())
print(f"x1 (Termék 1): {x1.value()}")
print(f"x2 (Termék 2): {x2.value()}")

Adott bemenet mellett:

Optimalizáció állapota: Optimal
Maximális profit: 1600.0
x1 (Termék 1): 20.0
x2 (Termék 2): 30.0

Ha egy probléma bináris döntési változókat igényel, például egy adott termék gyártása történjen-e vagy sem (${\displaystyle x_{i}\in \{0,1\}}$), azt a PuLP könyvtárban egyszerűen implementálhatjuk.

# Döntési változók definiálása (bináris változók)
x1 = LpVariable("x1", cat="Binary")
x2 = LpVariable("x2", cat="Binary")

# Célfüggvény és korlátok hasonlóak a korábbi példához
problem += 40 * x1 + 30 * x2, "Profit"
problem += 2 * x1 + x2 <= 1, "Korlát"

# Probléma megoldása
status = problem.solve()

# Kimenet
print("Optimalizáció állapota:", problem.status)
print("Maximális profit:", problem.objective.value())
print(f"x1: {x1.value()}")
print(f"x2: {x2.value()}")

1. Gyártási és logisztikai problémák:
   • Erőforrás-elosztás, gyártási ütemezés.
2. Pénzügyi tervezés:
   • Befektetési portfólió optimalizálása.
3. Ellátási lánc problémák:
   • Szállítási útvonalak tervezése.
4. Projektmenedzsment:
   • Feladatok ütemezése korlátok mellett.

• Pontos megoldásokat nyújt, ha egyértelműen definiált célfüggvénnyel és korlátokkal rendelkezünk.
• Kezeli az egészértékűségi és bináris feltételeket.

• Az egészértékűség kikényszerítése NP-teljes problémát eredményez, ami nagy számítási idővel járhat.
• Nagy méretű problémák esetén gyakran szükséges heurisztikus vagy közelítő módszerek használata.

Az egészértékű programozás hatékony eszköz az optimalizálási problémák széles skálájának megoldására, ahol a döntési változók egész vagy bináris értékűek. Pythonban a PuLP könyvtár egyszerűen használható, és számos alkalmazási területen hasznosítható.

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