Gemengd geheelgetal-lineair programmeren (MILP)

Introductie tot optimalisatie in Python

Jasmin Ludolf

Content Developer

Gemengd geheelgetal-lineair programmeren

  • MILP
  • Optimalisatietechniek wanneer beslissingsvariabelen discreet zijn
Introductie tot optimalisatie in Python

Jurken of smokings

  • Vraag:

    • Jurken: Maximaal $20$ à $\$ 1000$
    • Smokings: Maximaal $12$ à $\$ 600$

  • Productie jurk:

    • Stof $\$ 110$
    • Mr. S 6 uur à $\$40/u$
    • Ms. T 3 uur à $\$35/u$
  • Productie smoking:
    • Stof $\$ 75$
    • Mr. S 4 uur à $\$40/u$
    • Ms. T 1 uur à $\$35/u$

Een koppel in een jurk en een smoking

Introductie tot optimalisatie in Python

Jurken of smokings

  • Randvoorwaarden:
    • Mr. S max. 40 uur
    • Ms. T max. 20 uur

 

  • Vind het optimale aantal jurken en smokings om de winst te maximaliseren

Iemand houdt een rode lap stof vast en legt die op een paspop om een jurk te maken

Introductie tot optimalisatie in Python

Doel en randvoorwaarden

  • $g$: aantal jurken per week
  • $t$: aantal smokings per week

  • $C$: stofkosten + loon Mr. S + opportuniteitskost Ms. T

  • Opportuniteitskost: kost van kiezen voor naaien i.p.v. andere taken

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

$C=455g+270t$

Kosten Stof Mr. S Ms. T
Jurk $\$110$ $\$40/u \times 6u = \$240$ $\$35/u \times 3u = \$105$
Smoking $\$75$ $\$40/u \times 4u = \$160$ $\$35/u \times 1u = \$35$
Introductie tot optimalisatie in Python

Doel en randvoorwaarden

  • Omzet: $R=1000g+600t$
  • Kosten: $C=455g+270t$
  • Winst: $\Pi=R-C=(1000g+600t)-(455g+270t)=545g+330t$

 

  • Randvoorwaarden:

    • Vraag: $g\leq20$, $t\leq12$

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

Introductie tot optimalisatie in Python

MILP in 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]))
Introductie tot optimalisatie in Python

MILP in 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
Introductie tot optimalisatie in Python

Integraliteit

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
Introductie tot optimalisatie in Python

Gevolgen van integraliteit overslaan

  • Voorgestelde oplossing 6,67 jurken en 0,00 smokings $\rightarrow$

    • Afronden naar 7 jurken en 0 smokings

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

    • Afkappen naar 6 jurken en 0 smokings

      • Mr. S: $6g+4t=6\times6 + 4\times0 = 36$
      • Ms. T: $3g+1t=3\times6 + 1\times0 = 18$
      • $\Pi=545g+330t=545\times 6+330 \times 0=3270$
      • Gemiste winst $330 (bijna 10%)!
Introductie tot optimalisatie in Python

Laten we oefenen!

Introductie tot optimalisatie in Python

Preparing Video For Download...