मिक्स्ड इंटेजर लीनियर प्रोग्रामिंग (MILP)

Python में Optimization परिचय

Jasmin Ludolf

Content Developer

मिक्स्ड इंटेजर लीनियर प्रोग्रामिंग

MILP
जब constraint वैरिएबल्स discrete हों, तब प्रयोग होने वाली optimization technique

गाउन या टक्सीडो

Demand:
- Gowns: अधिकतम $20$ @ $\$ 1000$
- Tuxedos: अधिकतम $12$ @ $\$ 600$
Gown production:
- फ़ैब्रिक $\$ 110$
- Mr. S 6 घंटे @ $\$40/h$
- Ms. T 3 घंटे @ $\$35/h$
Tuxedo production:
- फ़ैब्रिक $\$ 75$
- Mr. S 4 घंटे @ $\$40/h$
- Ms. T 1 घंटा @ $\$35/h$

गाउन और टक्सीडो पहने एक जोड़ा

गाउन या टक्सीडो

Constraints:
- Mr. S अधिकतम 40 घंटे
- Ms. T अधिकतम 20 घंटे

लाभ अधिकतम करने के लिए गाउन और टक्सीडो की सर्वोत्तम संख्या निकालें

एक व्यक्ति लाल कपड़ा थामकर मैनिकिन पर ड्रेस बना रहा/रही है

Objective और constraints

$g$: एक सप्ताह में गाउन की संख्या
$t$: एक सप्ताह में टक्सीडो की संख्या
$C$: फ़ैब्रिक लागत + Mr. S वेतन + Mr. T अवसर लागत
अवसर लागत: सिलाई चुनने की कीमत बनाम अन्य जिम्मेदारियाँ

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

$C=455g+270t$

लागत	फ़ैब्रिक	Mr. S	Ms. T
Gown	$\$110$	$\$40/h \times 6h = \$240$	$\$35/h \times 3h = \$105$
Tuxedo	$\$75$	$\$40/h \times 4h = \$160$	$\$35/h \times 1h = \$35$

Objective और constraints

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

Constraints:
- Demand: $g\leq20$, $t\leq12$
- Supply: $6g+4t\leq40$, $3g+t\leq20$

SciPy में MILP

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]))

SciPy में MILP

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

Integrality

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

Integrality छोड़ने के परिणाम

प्रस्तावित समाधान 6.67 gowns और 0.00 tuxedos $\rightarrow$
- Round करके 7 gowns और 0 tuxedos
  - Mr. S: $6g+4t=6\times7 + 4\times0 = 42$
  - $42 \gt 40$
- Truncate करके 6 gowns और 0 tuxedos
  - 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$
  - लाभ में $330$ (लगभग 10%) छूट गया!

अभ्यास करते हैं!

Python में Optimization परिचय