Programação linear inteira mista (MILP)

Introdução à Otimização em Python

Jasmin Ludolf

Content Developer

Programação linear inteira mista

  • MILP
  • Técnica de otimização usada quando variáveis de restrição são discretas
Introdução à Otimização em Python

Vestidos ou smokings

  • Demanda:

    • Vestidos: No máximo $20$ a $\$ 1000$
    • Smokings: No máximo $12$ a $\$ 600$

  • Produção de vestido:

    • Tecido $\$ 110$
    • Sr. S 6 horas a $\$40/h$
    • Sra. T 3 horas a $\$35/h$
  • Produção de smoking:
    • Tecido $\$ 75$
    • Sr. S 4 horas a $\$40/h$
    • Sra. T 1 hora a $\$35/h$

Um casal vestido com um vestido e um smoking

Introdução à Otimização em Python

Vestidos ou smokings

  • Restrições:
    • Sr. S no máximo 40 horas
    • Sra. T no máximo 20 horas

 

  • Encontre a quantidade ótima de vestidos e smokings para maximizar o lucro

Pessoa segurando um tecido vermelho e colocando-o em um manequim para criar um vestido

Introdução à Otimização em Python

Objetivo e restrições

  • $g$: número de vestidos em uma semana
  • $t$: número de smokings em uma semana

  • $C$: custo do tecido + salário do Sr. S + custo de oportunidade da Sra. T

  • Custo de oportunidade: custo de escolher costurar em vez de outras tarefas

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

$C=455g+270t$

Custo Tecido Sr. S Sra. T
Vestido $\$110$ $\$40/h \times 6h = \$240$ $\$35/h \times 3h = \$105$
Smoking $\$75$ $\$40/h \times 4h = \$160$ $\$35/h \times 1h = \$35$
Introdução à Otimização em Python

Objetivo e restrições

  • Receita: $R=1000g+600t$
  • Custo: $C=455g+270t$
  • Lucro: $\Pi=R-C=(1000g+600t)-(455g+270t)=545g+330t$

 

  • Restrições:

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

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

Introdução à Otimização em Python

MILP no 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]))
Introdução à Otimização em Python

MILP no 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
Introdução à Otimização em Python

Integralidade

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
Introdução à Otimização em Python

Consequências de omitir a integralidade

  • Solução proposta 6.67 vestidos e 0.00 smokings $\rightarrow$

    • Arredonde para 7 vestidos e 0 smokings

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

    • Trunque para 6 vestidos e 0 smokings

      • Sr. S: $6g+4t=6\times6 + 4\times0 = 36$
      • Sra. T: $3g+1t=3\times6 + 1\times0 = 18$
      • $\Pi=545g+330t=545\times 6+330 \times 0=3270$
      • Perda de $330 (quase 10%) no lucro!
Introdução à Otimização em Python

Vamos praticar!

Introdução à Otimização em Python

Preparing Video For Download...