Programowanie całkowitoliczbowe

Programowanie całkowitoliczbowe – programowanie liniowe, w którym na zmienne decyzyjne (niektóre lub wszystkie) nałożono dodatkowe warunki, że muszą przyjmować wartości całkowite dodatnie, ponieważ rozwiązania z wartościami ułamkowymi nie miałyby sensu rzeczywistego (np. określenia ⅔ osoby lub ¾ samochodu).

W zagadnieniach programowania liniowego z reguły nie jest możliwe stosowanie zaokrągleń rozwiązań z wartościami ułamkowymi do najbliższych liczb całkowitych, gdyż wynik takiego postępowania może być daleki od rozwiązania optymalnego; może też nie spełniać warunków ograniczających^[1]. Przy programowaniu całkowitoliczbowym zachodzi więc potrzeba stosowania metod uwzględniających te warunki.

Problemy programowania całkowitoliczbowego należą do klasy NP-zupełnej.

Jeśli liczba zmiennych decyzyjnych jest mała i przyjmują one niewielkie wartości to zagadnienie można przekształcić w programowanie zero-jedynkowe^[a]^[2].

Uwagi edytuj

↑ Nieujemną zmienną $y\leq 2^{p}$ można wyrazić jako $y=\sum _{i=0}^{p}{2^{i}x_{i}}$

Bibliografia edytuj

Maciej MarekM.M. Sysło Maciej MarekM.M., NarsinghN. Deo NarsinghN., Janusz S.J.S. Kowalik Janusz S.J.S., Algorytmy optymalizacji dyskretnej, Janusz E.J.E. Roguski (red.), wyd. drugie, Warszawa: Wydawnictwo Naukowe PWN, 1995, ISBN 83-01-11818-0 .

[2] Nieujemną zmienną $y\leq 2^{p}$ można wyrazić jako $y=\sum _{i=0}^{p}{2^{i}x_{i}}$

[CITEREFSysłoDeoKowalik199571-1] Sysło, Deo i Kowalik 1995 ↓, s. 71.

[CITEREFSysłoDeoKowalik199592-3] Sysło, Deo i Kowalik 1995 ↓, s. 92.

[1]

[a]

[2]