Lineær programmering

Matematik A (HHX) · HHX · A-niveau · Erhvervsøkonomisk modellering

🧮 Lineær programmering

Lineær programmering (LP) = optimering af lineær funktion (mål-funktion) med lineære bibetingelser.

Standard-form: maksimér Z = c₁x₁ + c₂x₂ + ... + cₙxₙ, underlagt: a₁₁x₁ + a₁₂x₂ + ... ≤ b₁, ..., x_i ≥ 0.

Klassisk eksempel — produktions-planlægning: virksomhed producerer produkt A og B. A giver 30 kr. profit/enhed, B giver 50 kr. Hver enhed A kræver 2 timers arbejde og 1 kg materiale. Hver enhed B kræver 4 timer og 1 kg. Totalt 100 timer arbejde og 30 kg materiale tilgængelig. Maksimér profit.

Modellering: Maksimér Z = 30x_A + 50x_B. Underlagt: 2x_A + 4x_B ≤ 100 (arbejde), x_A + x_B ≤ 30 (materiale), x_A ≥ 0, x_B ≥ 0.

Grafisk løsning (kun 2 variabler): tegn bibetingelser som linjer, find polygonen af tilladte løsninger. Optimum ligger ALTID i et hjørne. Beregn Z i hvert hjørne, vælg højeste.

Hjørner i eksemplet: (0,0) → Z=0. (30,0) → Z=900. (0,25) → Z=1250. Skæring 2x+4y=100 og x+y=30 → x=10, y=20 → Z=300+1000=1300. Maksimum: produkter A=10, B=20, profit=1300 kr.

Algebraisk løsning — simplex-metoden (George Dantzig 1947): iterativ algoritme der bevæger sig fra hjørne til hjørne. Polynomial tid. Bruges af alle CAS-værktøjer.

Excel Solver: Data → Solver → angiv mål, ændr-celler, bibetingelser. Vælg "Simplex LP".

Anvendelser

produktion, transport (transportproblem), portfolio-optimering, kost-minimering, blanding-problemer (raffinaderi).

Heltals-LP (IP): når variabler skal være hele tal (kan ikke have 2,5 fly i en flåde). Sværere — branch

Læringsmål

• Opstille et lineært programmeringsproblem med restriktioner
• Bestemme den optimale løsning grafisk eller ved beregning
• Tolke løsningen i en erhvervsøkonomisk kontekst

Sådan kan du arbejde med emnet

• En virksomhed producerer to produkter med profit 400 og 600 kr. pr. enhed og begrænsede ressourcer — opstil LP-problemet og find det optimale produktionsmix
• Tegn feasible region for systemet x + 2y <= 16 og 3x + y <= 18 med x,y >= 0 og identificer hjørnepunkterne grafisk og algebraisk
• Forklar begrebet skyggepriser (shadow prices) i lineær programmering og diskuter, hvad de siger om værdien af at slappe ressourcebegrænsningerne

Brug formelsamling og gennemarbejdede opgaver. Stil spørgsmål om bevisførelse og udregningstrin.