--- title: "Heltalsoptimering" source: "https://systems-analysis.info/int/Heltalsoptimering" wiki: "systems-analysis.info/int" article: "Heltalsoptimering" language: "sv" categories: - "Category:Operations research" - "Category:Swedish" revision_id: 2858 wiki_created_at: 2026-09-06T23:12:04Z wiki_modified_at: 2026-09-06T23:12:04Z downloaded_at: 2026-09-07T22:53:45Z --- # Heltalsoptimering **Heltalsoptimering** (**HO**; eng. *integer programming, IP*) — är en gren inom matematisk optimering där man studerar problem i vilka några eller alla variabler måste anta enbart heltalsvärden[\[1\]](https://systems-analysis.info/int/Heltalsoptimering#cite_note-ru-wiki-ip-1). Det mest välstuderade specialfallet är **heltalslinjär programmering** (**HLP**; eng. *integer linear programming, ILP*), där målfunktionen och bivillkoren är linjära. Till skillnad från linjär programmering, där variablerna kan anta godtyckliga reella värden, gör heltalsvillkoret HO-problem avsevärt svårare att lösa[\[2\]](https://systems-analysis.info/int/Heltalsoptimering#cite_note-wolsey-book-2). Heltalsoptimering har bred tillämpning inom ekonomi, logistik, produktionsplanering och andra områden där variablerna till sin natur är diskreta (exempelvis antal producerade enheter eller antal anställda)[\[3\]](https://systems-analysis.info/int/Heltalsoptimering#cite_note-pisaruk-book-3). ## Definition och terminologi Det allmänna problemet inom heltalslinjär programmering kan formuleras på följande sätt: Hitta vektorn $x$ som: maximerar (eller minimerar) $c^{T}x$ med bivillkoren: $Ax \leq b$ $x \geq 0$ $x \in {\mathbb{Z}}^{n}$ (alla komponenter i vektorn $x$ är heltal) där $x$ är variabelvektorn, $c$ och $b$ är vektorer, och $A$ är en koefficientsmatris[\[4\]](https://systems-analysis.info/int/Heltalsoptimering#cite_note-conforti-book-4). Beroende på kraven på variablerna skiljer man på följande typer av problem: - **Rent heltals­programmering**: alla variabler måste vara heltal. - **Blandad heltalsprogrammering** (eng. *mixed-integer programming, MIP*): endast en del av variablerna måste vara heltal. - **Boolesk (0-1) programmering**: variablerna antar enbart värdena 0 eller 1, vilket möjliggör modellering av logiska ja/nej-beslut. ## Centrala egenskaper och komplexitet ### Beräkningskomplexitet Problemet med heltalslinjär programmering är i det allmänna fallet NP-svårt[\[5\]](https://systems-analysis.info/int/Heltalsoptimering#cite_note-karp-1972-5). Det innebär att det inte finns något känt algoritm som kan hitta en exakt optimal lösning för ett godtyckligt HO-problem på polynomiell tid. Komplexiteten beror på problemets kombinatoriska natur, eftersom antalet möjliga heltalslösningar kan växa exponentiellt med antalet variabler. ### Samband med linjär programmering (LP-relaxation) För varje HO-problem kan man formulera dess **linjära relaxation** — ett linjärprogrammeringsproblem (LP) där heltalsvillkoret för variablerna tas bort. Lösningen av LP-relaxationen har två viktiga egenskaper: 1. Den kan hittas avsevärt snabbare (på polynomiell tid). 2. Det optimala värdet av målfunktionen för LP-relaxationen ger en uppskattning (övre gräns vid maximering och undre gräns vid minimering) för det optimala värdet av det ursprungliga heltalsproblemet[\[2\]](https://systems-analysis.info/int/Heltalsoptimering#cite_note-wolsey-book-2). Dock leder enkel avrundning av den bråktalslösning som LP-relaxationen ger till närmaste heltal i allmänhet inte till en optimal eller ens tillåten lösning av heltalsproblemet[\[1\]](https://systems-analysis.info/int/Heltalsoptimering#cite_note-ru-wiki-ip-1). ### Egenskapen total unimodularitet Det finns en viktig klass av HLP-problem som löses lika enkelt som deras LP-relaxationer. Det gäller problem där bivillkorsmatrisen $A$ är **totalt unimodulär** (det vill säga att determinanten av varje kvadratisk undermatris är 0, +1 eller −1). Om matrisen $A$ är totalt unimodulär och vektorn $b$ är heltalsvärd, kommer alla hörn i polyedern av tillåtna lösningar för LP-relaxationen automatiskt att vara heltalsvärda. Följaktligen kommer lösningen som simplex­metoden finner att vara heltalsvärd[\[4\]](https://systems-analysis.info/int/Heltalsoptimering#cite_note-conforti-book-4). Exempel på sådana problem är transportproblemet och tilldelningsproblemet. ## Lösningsmetoder För att lösa allmänna HO-problem som saknar egenskapen total unimodularitet har exakta metoder baserade på idén om implicit uppräkning utvecklats. - **Branch and Bound-metoden** (eng. *Branch and Bound*) — den primära exakta metoden, baserad på systematisk uppdelning av mängden tillåtna lösningar i delmängder (förgrening) och bortsållning av de delmängder som uppenbarligen inte innehåller den optimala lösningen. LP-relaxation används för att bedöma delmängdernas potential[\[6\]](https://systems-analysis.info/int/Heltalsoptimering#cite_note-en-wiki-ip-6). - **Snittsplansmetoden** (Gomorys metod; eng. *Cutting Plane Method*) — ett iterativt tillvägagångssätt som successivt lägger till nya linjära bivillkor ("snitt") till problemet. Dessa snitt "skär bort" bråktalslösningar från LP-relaxationen utan att beröra någon tillåten heltalslösning, och approximerar därigenom gradvis det tillåtna området för LP-relaxationen mot det konvexa höljet av heltalslösningarna[\[6\]](https://systems-analysis.info/int/Heltalsoptimering#cite_note-en-wiki-ip-6). Moderna lösare använder i regel hybridalgoritmer, såsom **Branch and Cut-metoden** (eng. *Branch and Cut*), som kombinerar fördelarna med båda tillvägagångssätten. ## Exempel och tillämpningsområden Heltalsoptimering möjliggör modellering av många klassiska problem inom kombinatorisk optimering. - *Ryggsäcksproblemet*: ett klassiskt 0-1-programmeringsproblem där man ska välja en uppsättning föremål med maximalt totalt värde utan att överskrida en begränsning på den totala vikten. - *Handelsresandeproblemet*: problemet att hitta den kortaste rutten som passerar genom en given uppsättning städer. Det kan formuleras som ett heltalsprogrammeringsproblem där variablerna anger om kanter i grafen inkluderas i den slutliga rutten. Tack vare sin flexibilitet är HO ett av de mest efterfrågade verktygen inom operations research och tillämpas inom sådana områden som: - **Logistik och hantering av leveranskedjor**: optimering av transportrutter, lokalisering av lager, lagerhantering. - **Produktionsplanering**: utformning av produktionsscheman, resursfördelning, kapacitetsutnyttjande. - **Finans och ekonomi**: sammansättning av investeringsportföljer, kapitalbudgetering. - **Telekommunikation och energi**: nätverksdesign, planering av kraftverks­drift. ## Se även - Linjär programmering - Branch and Bound-metoden ## Noter [\[1\]](https://systems-analysis.info/int/Heltalsoptimering#cite_note-ru-wiki-ip-1) [\[2\]](https://systems-analysis.info/int/Heltalsoptimering#cite_note-wolsey-book-2) [\[3\]](https://systems-analysis.info/int/Heltalsoptimering#cite_note-pisaruk-book-3) [\[4\]](https://systems-analysis.info/int/Heltalsoptimering#cite_note-conforti-book-4) [\[5\]](https://systems-analysis.info/int/Heltalsoptimering#cite_note-karp-1972-5) [\[6\]](https://systems-analysis.info/int/Heltalsoptimering#cite_note-en-wiki-ip-6) \ 1. ↑ [1.0](https://systems-analysis.info/int/Heltalsoptimering#cite_ref-ru-wiki-ip_1-0) [1.1](https://systems-analysis.info/int/Heltalsoptimering#cite_ref-ru-wiki-ip_1-1) [1.2](https://systems-analysis.info/int/Heltalsoptimering#cite_ref-ru-wiki-ip_1-2) "Целочисленное программирование". *Википедия*. [1] 2. ↑ [2.0](https://systems-analysis.info/int/Heltalsoptimering#cite_ref-wolsey-book_2-0) [2.1](https://systems-analysis.info/int/Heltalsoptimering#cite_ref-wolsey-book_2-1) [2.2](https://systems-analysis.info/int/Heltalsoptimering#cite_ref-wolsey-book_2-2) Wolsey, Laurence A. (2020). *Integer Programming* (2nd ed.). John Wiley & Sons. 3. ↑ [3.0](https://systems-analysis.info/int/Heltalsoptimering#cite_ref-pisaruk-book_3-0) [3.1](https://systems-analysis.info/int/Heltalsoptimering#cite_ref-pisaruk-book_3-1) Писарук Н.Н. (2010). *Модели и методы смешанного целочисленного программирования*. Минск: БГУ. 4. ↑ [4.0](https://systems-analysis.info/int/Heltalsoptimering#cite_ref-conforti-book_4-0) [4.1](https://systems-analysis.info/int/Heltalsoptimering#cite_ref-conforti-book_4-1) [4.2](https://systems-analysis.info/int/Heltalsoptimering#cite_ref-conforti-book_4-2) Conforti, M., Cornuéjols, G., & Zambelli, G. (2014). *Integer Programming*. Springer. 5. ↑ [5.0](https://systems-analysis.info/int/Heltalsoptimering#cite_ref-karp-1972_5-0) [5.1](https://systems-analysis.info/int/Heltalsoptimering#cite_ref-karp-1972_5-1) Karp, Richard M. (1972). "Reducibility among Combinatorial Problems". In: *Complexity of Computer Computations*. Springer. 6. ↑ [6.0](https://systems-analysis.info/int/Heltalsoptimering#cite_ref-en-wiki-ip_6-0) [6.1](https://systems-analysis.info/int/Heltalsoptimering#cite_ref-en-wiki-ip_6-1) [6.2](https://systems-analysis.info/int/Heltalsoptimering#cite_ref-en-wiki-ip_6-2) "Integer programming". *Wikipedia*. [2]