Lập trình tuyến tính nguyên hỗn hợp (MILP)

Nhập môn Tối ưu hóa với Python

Jasmin Ludolf

Content Developer

Lập trình tuyến tính nguyên hỗn hợp

  • MILP
  • Kỹ thuật tối ưu khi biến ràng buộc là biến rời rạc
Nhập môn Tối ưu hóa với Python

Váy hay lễ phục

  • Nhu cầu:

    • Váy dạ hội: Tối đa $20$ tại $\$ 1000$
    • Lễ phục: Tối đa $12$ tại $\$ 600$

  • Sản xuất váy:

    • Vải $\$ 110$
    • Ông S 6 giờ với $\$40/giờ$
    • Bà T 3 giờ với $\$35/giờ$
  • Sản xuất lễ phục:
    • Vải $\$ 75$
    • Ông S 4 giờ với $\$40/giờ$
    • Bà T 1 giờ với $\$35/giờ$

Một cặp đôi mặc váy dạ hội và lễ phục

Nhập môn Tối ưu hóa với Python

Váy hay lễ phục

  • Ràng buộc:
    • Ông S tối đa 40 giờ
    • Bà T tối đa 20 giờ

 

  • Tìm số váy và lễ phục tối ưu để tối đa hóa lợi nhuận

Một người cầm vải đỏ phủ lên ma-nơ-canh để may váy

Nhập môn Tối ưu hóa với Python

Hàm mục tiêu và ràng buộc

  • $g$: số váy mỗi tuần
  • $t$: số lễ phục mỗi tuần

  • $C$: chi phí vải + lương Ông S + chi phí cơ hội Bà T

  • Chi phí cơ hội: chi phí chọn may thay vì công việc khác

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

$C=455g+270t$

Chi phí Vải Ông S Bà T
Váy $\$110$ $\$40/giờ \times 6h = \$240$ $\$35/giờ \times 3h = \$105$
Lễ phục $\$75$ $\$40/giờ \times 4h = \$160$ $\$35/giờ \times 1h = \$35$
Nhập môn Tối ưu hóa với Python

Hàm mục tiêu và ràng buộc

  • Doanh thu: $R=1000g+600t$
  • Chi phí: $C=455g+270t$
  • Lợi nhuận: $\Pi=R-C=(1000g+600t)-(455g+270t)=545g+330t$

 

  • Ràng buộc:

    • Nhu cầu: $g\leq20$, $t\leq12$

    • Nguồn lực: $6g+4t\leq40$, $3g+t\leq20$

Nhập môn Tối ưu hóa với Python

MILP trong 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]))
Nhập môn Tối ưu hóa với Python

MILP trong SciPy

print(result.message)
print(f'Số váy dạ hội tối ưu là: {result.x[0]:.2f}')
print(f'Số lễ phục tối ưu là: {result.x[1]:.2f}') 

Tối ưu hóa kết thúc thành công. (HiGHS Status 7: Optimal)
Số váy dạ hội tối ưu là: 6.00
Số lễ phục tối ưu là: 1.00
Nhập môn Tối ưu hóa với Python

Tính nguyên

result = milp([-545, -330],  
              bounds=Bounds([0, 0], [20, 12]), 
              constraints=LinearConstraint([[6, 4], [3, 1]], ub=[40, 20]))
...

Số váy dạ hội tối ưu là: 6.67
Số lễ phục tối ưu là: 0.00
Nhập môn Tối ưu hóa với Python

Hệ quả khi bỏ qua tính nguyên

  • Lời giải đề xuất 6.67 váy và 0.00 lễ phục $\rightarrow$

    • Làm tròn thành 7 váy và 0 lễ phục

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

    • Cắt bớt thành 6 váy và 0 lễ phục

      • Ông S: $6g+4t=6\times6 + 4\times0 = 36$
      • Bà T: $3g+1t=3\times6 + 1\times0 = 18$
      • $\Pi=545g+330t=545\times 6+330 \times 0=3270$
      • Mất $330 (gần 10%) lợi nhuận!
Nhập môn Tối ưu hóa với Python

Ayo berlatih!

Nhập môn Tối ưu hóa với Python

Preparing Video For Download...