การโปรแกรมเชิงเส้นจำนวนเต็มผสม (MILP)

การหาค่าที่เหมาะสมที่สุดใน Python เบื้องต้น

Jasmin Ludolf

Content Developer

การโปรแกรมเชิงเส้นจำนวนเต็มผสม

  • MILP
  • เทคนิคการหาค่าที่เหมาะสม เมื่อตัวแปรของข้อจำกัดเป็นตัวแปรแบบไม่ต่อเนื่อง
การหาค่าที่เหมาะสมที่สุดใน Python เบื้องต้น

ชุดราตรีหรือชุดทักซิโด้

  • อุปสงค์:

    • ชุดราตรี: สูงสุด $20$ ชุด ราคา $\$ 1000$
    • ชุดทักซิโด้: สูงสุด $12$ ชุด ราคา $\$ 600$

  • การผลิตชุดราตรี:

    • ผ้า $\$ 110$
    • คุณ S 6 ชั่วโมง ที่ $\$40/h$
    • คุณ T 3 ชั่วโมง ที่ $\$35/h$
  • การผลิตชุดทักซิโด้:
    • ผ้า $\$ 75$
    • คุณ S 4 ชั่วโมง ที่ $\$40/h$
    • คุณ T 1 ชั่วโมง ที่ $\$35/h$

คู่รักสวมชุดราตรีและชุดทักซิโด้

การหาค่าที่เหมาะสมที่สุดใน Python เบื้องต้น

ชุดราตรีหรือชุดทักซิโด้

  • ข้อจำกัด:
    • คุณ S ทำงานได้สูงสุด 40 ชั่วโมง
    • คุณ T ทำงานได้สูงสุด 20 ชั่วโมง

 

  • หาจำนวนชุดราตรีและชุดทักซิโด้ที่เหมาะสมเพื่อให้กำไรสูงสุด

ช่างตัดเย็บกำลังนำผ้าสีแดงมาจัดทรงบนหุ่นเพื่อเย็บชุด

การหาค่าที่เหมาะสมที่สุดใน Python เบื้องต้น

ฟังก์ชันวัตถุประสงค์และข้อจำกัด

  • $g$: จำนวนชุดราตรีต่อสัปดาห์
  • $t$: จำนวนชุดทักซิโด้ต่อสัปดาห์

  • $C$: ต้นทุนผ้า + ค่าแรงคุณ S + ต้นทุนค่าเสียโอกาสของคุณ T

  • ต้นทุนค่าเสียโอกาส: ต้นทุนของการเลือกตัดเย็บแทนที่จะทำงานอื่น

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

$C=455g+270t$

ต้นทุน ผ้า คุณ S คุณ T
ชุดราตรี $\$110$ $\$40/h \times 6h = \$240$ $\$35/h \times 3h = \$105$
ชุดทักซิโด้ $\$75$ $\$40/h \times 4h = \$160$ $\$35/h \times 1h = \$35$
การหาค่าที่เหมาะสมที่สุดใน Python เบื้องต้น

ฟังก์ชันวัตถุประสงค์และข้อจำกัด

  • รายได้: $R=1000g+600t$
  • ต้นทุน: $C=455g+270t$
  • กำไร: $\Pi=R-C=(1000g+600t)-(455g+270t)=545g+330t$

 

  • ข้อจำกัด:

    • อุปสงค์: $g\leq20$, $t\leq12$

    • อุปทาน: $6g+4t\leq40$, $3g+t\leq20$

การหาค่าที่เหมาะสมที่สุดใน Python เบื้องต้น

MILP ใน 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]))
การหาค่าที่เหมาะสมที่สุดใน Python เบื้องต้น

MILP ใน 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
การหาค่าที่เหมาะสมที่สุดใน Python เบื้องต้น

ความเป็นจำนวนเต็ม

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
การหาค่าที่เหมาะสมที่สุดใน Python เบื้องต้น

ผลของการละเว้นเงื่อนไขความเป็นจำนวนเต็ม

  • คำตอบที่ได้คือ 6.67 ชุดราตรี และ 0.00 ชุดทักซิโด้ $\rightarrow$

    • ปัดขึ้น เป็น 7 ชุดราตรี และ 0 ชุดทักซิโด้

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

    • ปัดลง เป็น 6 ชุดราตรี และ 0 ชุดทักซิโด้

      • คุณ S: $6g+4t=6\times6 + 4\times0 = 36$
      • คุณ T: $3g+1t=3\times6 + 1\times0 = 18$
      • $\Pi=545g+330t=545\times 6+330 \times 0=3270$
      • สูญเสียกำไรไป $330 (เกือบ 10%)!
การหาค่าที่เหมาะสมที่สุดใน Python เบื้องต้น

มาฝึกกันเถอะ!

การหาค่าที่เหมาะสมที่สุดใน Python เบื้องต้น

Preparing Video For Download...