Blandad heltalslinjär programmering (MILP)

Introduktion till optimering i Python

Jasmin Ludolf

Content Developer

Blandad heltalslinjär programmering

  • MILP
  • Optimeringsteknik för problem där bivillkorsvariablerna är diskreta
Introduktion till optimering i Python

Klänningar eller smokingar

  • Efterfrågan:

    • Aftonklänningar: Högst $20$ st à $\$ 1000$
    • Smokingar: Högst $12$ st à $\$ 600$

  • Produktion av klänningar:

    • Tyg $\$ 110$
    • Hr S 6 timmar à $\$40/h$
    • Fr T 3 timmar à $\$35/h$
  • Produktion av smokingar:
    • Tyg $\$ 75$
    • Hr S 4 timmar à $\$40/h$
    • Fr T 1 timme à $\$35/h$

Ett par klädda i aftonklänning och smoking

Introduktion till optimering i Python

Klänningar eller smokingar

  • Bivillkor:
    • Hr S högst 40 timmar
    • Fr T högst 20 timmar

 

  • Hitta det optimala antalet klänningar och smokingar för att maximera vinsten

En person som håller i ett rött tyg och fäster det på en provdocka för att skapa en klänning

Introduktion till optimering i Python

Målfunktion och bivillkor

  • $g$: antal klänningar per vecka
  • $t$: antal smokingar per vecka

  • $C$: tygkostnad + Hr S lön + Fr T alternativkostnad

  • Alternativkostnad: kostnaden för att sy i stället för andra arbetsuppgifter

$C=110g+240g+105g+75t+160t+35t$

$C=455g+270t$

Kostnad Tyg Hr S Fr T
Klänning $\$110$ $\$40/h \times 6h = \$240$ $\$35/h \times 3h = \$105$
Smoking $\$75$ $\$40/h \times 4h = \$160$ $\$35/h \times 1h = \$35$
Introduktion till optimering i Python

Målfunktion och bivillkor

  • Intäkt: $R=1000g+600t$
  • Kostnad: $C=455g+270t$
  • Vinst: $\Pi=R-C=(1000g+600t)-(455g+270t)=545g+330t$

 

  • Bivillkor:

    • Efterfrågan: $g\leq20$, $t\leq12$

    • Utbud: $6g+4t\leq40$, $3g+t\leq20$

Introduktion till optimering i Python

MILP i SciPy

from scipy.optimize import milp, Bounds, LinearConstraint


result = milp([-545, -330],

              integrality=[1, 1],

              bounds=Bounds([0, 0], [20, 12]),

              constraints=LinearConstraint([[6, 4], [3, 1]], ub=[40, 20]))
Introduktion till optimering i Python

MILP i SciPy

print(result.message)
print(f'The optimal number of gowns produced is: {result.x[0]:.2f}')
print(f'The optimal number of tuxedos produced is: {result.x[1]:.2f}') 

Optimization terminated successfully. (HiGHS Status 7: Optimal)
The optimal number of gowns produced is: 6.00
The optimal number of tuxedos produced is: 1.00
Introduktion till optimering i Python

Heltalsbegränsning

result = milp([-545, -330],  
              bounds=Bounds([0, 0], [20, 12]), 
              constraints=LinearConstraint([[6, 4], [3, 1]], ub=[40, 20]))
...

The optimal number of gowns produced is: 6.67
The optimal number of tuxedos produced is: 0.00
Introduktion till optimering i Python

Konsekvenser av utelämnad heltalsbegränsning

  • Föreslagen lösning: 6,67 klänningar och 0,00 smokingar $\rightarrow$

    • Avrunda till 7 klänningar och 0 smokingar

      • Hr S: $6g+4t=6\times7 + 4\times0 = 42$
      • $42 \gt 40$

    • Trunkera till 6 klänningar och 0 smokingar

      • Hr S: $6g+4t=6\times6 + 4\times0 = 36$
      • Fr T: $3g+1t=3\times6 + 1\times0 = 18$
      • $\Pi=545g+330t=545\times 6+330 \times 0=3270$
      • Förlorad vinst på $330 (nästan 10%)!
Introduktion till optimering i Python

Nu kör vi en övning!

Introduktion till optimering i Python

Preparing Video For Download...