Programare liniară în numere întregi mixte (MILP)

Introducere în optimizare în Python

Jasmin Ludolf

Content Developer

Programare liniară în numere întregi mixte

  • MILP
  • Tehnică de optimizare utilizată când variabilele sunt discrete
Introducere în optimizare în Python

Rochii sau smokinguri

  • Cerere:

    • Rochii: Cel mult $20$ la $\$ 1000$
    • Smokinguri: Cel mult $12$ la $\$ 600$

  • Producție rochii:

    • Material $\$ 110$
    • Dl. S 6 ore la $\$40/h$
    • Dna. T 3 ore la $\$35/h$
  • Producție smokinguri:
    • Material $\$ 75$
    • Dl. S 4 ore la $\$40/h$
    • Dna. T 1 oră la $\$35/h$

Un cuplu îmbrăcat în rochie de seară și smoking

Introducere în optimizare în Python

Rochii sau smokinguri

  • Constrângeri:
    • Dl. S cel mult 40 de ore
    • Dna. T cel mult 20 de ore

 

  • Găsiți numărul optim de rochii și smokinguri pentru a maximiza profitul

O persoană care ține o bucată de material roșu și o așază pe un manechin pentru a crea o rochie

Introducere în optimizare în Python

Funcție obiectiv și constrângeri

  • $g$: numărul de rochii pe săptămână
  • $t$: numărul de smokinguri pe săptămână

  • $C$: cost material + salariu Dl. S + cost de oportunitate Dna. T

  • Cost de oportunitate: costul alegerii de a coase față de alte activități

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

$C=455g+270t$

Cost Material Dl. S Dna. T
Rochie $\$110$ $\$40/h \times 6h = \$240$ $\$35/h \times 3h = \$105$
Smoking $\$75$ $\$40/h \times 4h = \$160$ $\$35/h \times 1h = \$35$
Introducere în optimizare în Python

Funcție obiectiv și constrângeri

  • Venit: $R=1000g+600t$
  • Cost: $C=455g+270t$
  • Profit: $\Pi=R-C=(1000g+600t)-(455g+270t)=545g+330t$

 

  • Constrângeri:

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

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

Introducere în optimizare în Python

MILP în 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]))
Introducere în optimizare în Python

MILP în 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
Introducere în optimizare în Python

Integralitate

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
Introducere în optimizare în Python

Consecințele omiterii integralității

  • Soluție propusă: 6,67 rochii și 0,00 smokinguri $\rightarrow$

    • Rotunjire la 7 rochii și 0 smokinguri

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

    • Trunchiere la 6 rochii și 0 smokinguri

      • Dl. S: $6g+4t=6\times6 + 4\times0 = 36$
      • Dna. T: $3g+1t=3\times6 + 1\times0 = 18$
      • $\Pi=545g+330t=545\times 6+330 \times 0=3270$
      • Pierdere de $330 (aproape 10%) din profit!
Introducere în optimizare în Python

Să exersăm!

Introducere în optimizare în Python

Preparing Video For Download...