--- title: "Linjär programmering" source: "https://systems-analysis.info/int/Linj%C3%A4r_programmering" wiki: "systems-analysis.info/int" article: "Linjär_programmering" language: "sv" categories: - "Category:Mathematical modeling" - "Category:Operations research" - "Category:Swedish" revision_id: 3877 wiki_created_at: 2026-09-06T23:27:24Z wiki_modified_at: 2026-09-06T23:27:24Z downloaded_at: 2026-09-07T22:59:32Z --- # Linjär programmering **Linjär programmering** är en gren inom matematisk programmering och en allmänt använd metod inom operations research, som ägnas åt att utveckla teorier och metoder för att lösa problem om att finna ett extremvärde (maximum eller minimum) för en linjär funktion under linjära bivillkor. Linjär programmering (LP) är ett av de kraftfullaste och mest tillämpade verktygen för att lösa optimeringsproblem inom ekonomi, ledning, planering, logistik och andra områden. ## Ämne och syfte **Grundproblemet inom linjär programmering** är att hitta det bästa (optimala) sättet att fördela begränsade resurser för att uppnå ett visst mål, när såväl målet som bivillkoren för resursanvändningen kan uttryckas som linjära samband. - Linjär programmering gör det möjligt att lösa sådana praktiska problem som: - Optimal produktionsplanering. - Optimering av transportflöden (transportproblemet). - Optimal fördelning av investeringar. - Optimal skärning av material. Tilldelningsproblemet. ## Matematisk formulering av LP-problemet Standardproblemet inom linjär programmering formuleras på följande sätt: Man söker värden på beslutsvariablerna som maximerar eller minimerar en linjär målfunktion. Beslutsvariablerna är underkastade bivillkor i form av ett system av linjära likheter och/eller linjära olikheter. I regel tillkommer ett icke-negativitetskrav på beslutsvariablerna (deras värden ska vara större än eller lika med noll), vilket ofta dikteras av problemets fysikaliska eller ekonomiska innebörd. Matematiskt innebär detta att man arbetar med linjära funktioner och system av linjära ekvationer/olikheter. ## Grundläggande begrepp inom LP - Beslutsvariabler (styrvariabler): Storheter vars värden ska bestämmas i lösningsprocessen (till exempel produktionsvolymer för olika produkter, mängden resurser som riktas mot olika mål). - Målfunktion: En linjär funktion av beslutsvariablerna vars värde ska maximeras eller minimeras. Den kvantifierar problemets mål (till exempel total vinst, sammanlagda kostnader). - Bivillkor: Ett system av linjära likheter och/eller olikheter som beslutsvariablerna måste uppfylla. Bivillkoren återspeglar resursbegränsningar, teknologiska krav, planeringsmål och andra förutsättningar. - Tillåtet område (feasible region): Mängden av alla kombinationer av värden på beslutsvariablerna som uppfyller samtliga bivillkor. Geometriskt utgör det tillåtna området i ett flerdimensionellt rum en konvex polytop (polyeder), möjligen obegränsad eller tom. - Tillåten lösning: Varje kombination av variabelvärden som tillhör det tillåtna området. - Optimal lösning: En tillåten lösning vid vilken målfunktionen uppnår sitt extremvärde (maximum eller minimum). Om en optimal lösning existerar befinner den sig alltid på gränsen av det tillåtna området, i minst ett av hörnen på den konvexa polytopen (LP:s grundsats). ## Metoder för att lösa LP-problem Det finns flera grundläggande metoder för att lösa problem inom linjär programmering: - Grafisk metod: Används för problem med två beslutsvariabler. Gör det möjligt att åskådligt avbilda det tillåtna området och målfunktionen i ett plan och finna den optimala lösningen genom analys av hörnen i det tillåtna området eller förflyttning av målfunktionens nivålinje. - Simplexmetoden: En universell iterativ algoritm, utvecklad av George Dantzig. Metoden rör sig stegvis från ett hörn i det tillåtna området till ett angränsande, och förbättrar målfunktionens värde vid varje steg tills en optimal lösning hittas. Det är den klassiska och mest kända metoden för att lösa LP-problem. - Inrepunktsmetoder: En alternativ klass av algoritmer som uppkom senare än simplexmetoden. De rör sig mot den optimala lösningen inuti det tillåtna området snarare än längs dess gränser. Dessa metoder är särskilt effektiva för att lösa LP-problem av mycket stor storlek. ## Dualitet inom linjär programmering Till varje LP-problem (kallat primalt) kan man koppla ett annat LP-problem, kallat dualt. Det primala och det duala problemet är nära relaterade till varandra: Lösningen av det ena problemet ger information om lösningen av det andra. De optimala värdena på målfunktionerna i båda problemen sammanfaller (om de existerar). Variablerna i det duala problemet har en viktig ekonomisk tolkning — de motsvarar skuggpriser (eller duala värden) för resurserna och visar hur mycket det optimala värdet på det primala problemets målfunktion förändras vid en liten förändring av bivillkoret för den motsvarande resursen. ## Tillämpningar av LP Linjär programmering tillämpas i stor utsträckning inom: - Ekonomi och näringsliv (produktionsplanering, logistik, finans, marknadsföring). - Industri (optimering av teknologiska processer, lagerhantering, skärning av material). - Transport (optimering av rutter och tidtabeller). Jordbruk (optimering av odlingsarealer och foderransoner). - Energisektorn (optimering av belastningen på produktionskapacitet). ## Litteratur - *Dantzig, G.* Linjär programmering, dess tillämpningar och generaliseringar. — Moskva: Progress, 1966. - *Judin, D. B.; Goldstein, E. G.* Linjär programmering (teori, metoder och tillämpningar). — Moskva: Nauka, 1969. - *Taha, Hamdy A.* Operations Research: An Introduction. — Pearson. (10th ed., 2017) - *Hillier, Frederick S.; Lieberman, Gerald J.* Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021) ## Se även - Operations research - Optimering - Målfunktion - Bivillkor - Tillåtet område - Optimal lösning