Heltalsprogrammering

Fra Wikipedia, den frie encyklopædi
Spring til navigation Spring til søgning

Et heltalsprogram eller heltalsprogrammerings-problem er et matematisk optimeringsproblem hvor alle variablene kræves at være heltallige. Hvis kun nogle af variablene kræves at være heltallige (dvs. resten er kontinuerte) haves et såkaldt blandet heltalsprogram. Ofte når der tales om heltalsprogrammer (og blandede heltalsprogrammer) antages det, at både begrænsningerne og objektfunktionen er lineære, hvilket vil sige, at man har et lineært heltalsprogram.

Generelle heltalsprogrammer er NP-hårde. Det specielle tilfælde hvor alle heltalsvariable skal være enten 0 eller 1 og hvor problemet er lineært er blandt Karps 21 NP-komplette problemer. Man børe notere sig, at et heltalsprogram er et særtilfælde af et blandet heltalsprogram hvor antallet af kontinuerte variable er nul. Det vil sige, at blandede heltalsprogrammer er en generalisering af heltalsprogrammer, og derfor mindst lige så svære at løse.

Lineære blandede heltalsprogrammer[redigér | redigér wikikode]

I dette afsnit er fokus på blandede heltalsprogrammer. Et generelt blandet heltalsprogram kan opskrives på følgende vis:
Lad og , , og være helholdvis rationelle matricer og vektorer og lad og være rationelle tal. Da er et generelt blandet heltasprogram givet ved:

Som med lineære programmer, kan man opskrive dette problem i standard from ved at tilføje slack variable

Disse to optimeringsproblemer er matematisk ækvivalente og har samme optimale løsningsværdi.

Konvertering til 0-1 programmerings problem[redigér | redigér wikikode]

Man kan her notere sig, at ethvert begrænset blandet heltsprogram kan omskrives til et blandet 0-1 program. Det vil sige, at de variable som skal være heltallige alle er binære. For eksempel kan en heltalsvariabel omskrives ved hjælp af binære variable:

Det vil sige, at ethvert begrænset blandet heltalsprogram er et specialtilfælde af et blandet 0-1 program, hvorfor et blandet 0-1 også er NP-komplet. Faktisk behøver man ikke gøre sig antagelsen om begrænsethed, men det gør matematikken noget nemmere (for flere detaljer henvises til "Nemhauser & Wolsey"[1])


Man kan notere sig, at (næsten) alle praktisk forekomne optimeringsproblemer er begrænsede i den forstand, at der vil være en øvre og en nedre grænse for alle variable. Hvis for eksempel en variabel angiver forbruget af en given råvare, da vil der være en (måske meget stor) øvre grænse for hvor meget af denne råvare man kan forbruge.

Løsningsmetoder for blandede heltalsprogrammer[redigér | redigér wikikode]

Blandede heltalsprogrammer er et særdeles velstuderet område inden for både operationsanalyse, datalogi og matematik. En lang række algoritmer og metoder er derfor udviklet. Nedenfor er listet en række af de mest benyttede eksakte metoder:

Det er dog ikke alle blandede heltalsprogrammer hvor det er praktisk muligt at finde en optimal løsning, grundet for eksempel begrænset tid eller hukommelse. I stedet benytter man sig således ofte af heuristikker til at finde en løsning, som er bedst mulig. Nedenfor er listet nogle af de mest kendte heuristikker og meta-heuristikker:

Noter[redigér | redigér wikikode]

  1. ^ Nemhauser, G.; Wolsey, L. (1988). Integer and Combinatorial Optimization.  kapitel I.5 afsnit 4.