Smíšené celočíselné lineární programování (MILP)

Introduction to Optimization in Python

Jasmin Ludolf

Content Developer

Smíšené celočíselné lineární programování

  • MILP
  • Optimalizační technika pro diskrétní proměnné omezení
Introduction to Optimization in Python

Šaty nebo smokiny

  • Poptávka:

    • Šaty: nejvýše $20$ za $\$ 1000$
    • Smokiny: nejvýše $12$ za $\$ 600$

  • Výroba šatů:

    • Látka $\$ 110$
    • Pan S 6 hodin za $\$40/h$
    • Paní T 3 hodiny za $\$35/h$
  • Výroba smokinů:
    • Látka $\$ 75$
    • Pan S 4 hodiny za $\$40/h$
    • Paní T 1 hodina za $\$35/h$

Pár oblečený ve svatebních šatech a smokingu

Introduction to Optimization in Python

Šaty nebo smokiny

  • Omezení:
    • Pan S nejvýše 40 hodin
    • Paní T nejvýše 20 hodin

 

  • Najděte optimální počet šatů a smokinů pro maximalizaci zisku

Osoba držící červenou látku a upravující ji na figuríně

Introduction to Optimization in Python

Účelová funkce a omezení

  • $g$: počet šatů za týden
  • $t$: počet smokinů za týden

  • $C$: náklady na látku + mzda pana S + náklady příležitosti paní T

  • Náklady příležitosti: cena volby šití místo jiných povinností

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

$C=455g+270t$

Náklady Látka Pan S Paní T
Šaty $\$110$ $\$40/h \times 6h = \$240$ $\$35/h \times 3h = \$105$
Smoking $\$75$ $\$40/h \times 4h = \$160$ $\$35/h \times 1h = \$35$
Introduction to Optimization in Python

Účelová funkce a omezení

  • Výnosy: $R=1000g+600t$
  • Náklady: $C=455g+270t$
  • Zisk: $\Pi=R-C=(1000g+600t)-(455g+270t)=545g+330t$

 

  • Omezení:

    • Poptávka: $g\leq20$, $t\leq12$

    • Nabídka: $6g+4t\leq40$, $3g+t\leq20$

Introduction to Optimization in Python

MILP v 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]))
Introduction to Optimization in Python

MILP v 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
Introduction to Optimization in Python

Celočíselnost

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
Introduction to Optimization in Python

Důsledky vynechání celočíselnosti

  • Navržené řešení: 6,67 šatů a 0,00 smokinů $\rightarrow$

    • Zaokrouhlit na 7 šatů a 0 smokinů

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

    • Oříznout na 6 šatů a 0 smokinů

      • Pan S: $6g+4t=6\times6 + 4\times0 = 36$
      • Paní T: $3g+1t=3\times6 + 1\times0 = 18$
      • $\Pi=545g+330t=545\times 6+330 \times 0=3270$
      • Ztráta $330 (téměř 10\%)$ na zisku!
Introduction to Optimization in Python

Pojďme cvičit!

Introduction to Optimization in Python

Preparing Video For Download...