Quy hoạch tuyến tính - hàm mục tiêu, ràng buộc, capacity planning

Giới thiệu

Bài này học mô tả bài toán bằng hàm mục tiêu và ràng buộc. Bạn dùng nó để tính sản lượng lãi nhất cho xưởng.

Kiến thức cần nhớ

Ý tưởng chính

• Không thiết kế bước đi, chỉ mô tả cái gì tốt và cái gì cấm.
• Giao cho bộ giải tìm nghiệm tốt nhất.
• Ví dụ đời thường: như nói muốn lãi nhất trong giới hạn nguyên liệu, để máy tính chia việc.
• Họ hàng: chia để trị, quy hoạch động, tham lam.

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

• Biến quyết định: ví dụ sản lượng từng sản phẩm.
• Hàm mục tiêu: ví dụ tổng lợi nhuận cần cực đại.
• Ràng buộc: giới hạn giờ máy, nguyên liệu, không âm.
• Giao các ràng buộc tạo đa diện lồi, nghiệm tốt nhất nằm ở 1 đỉnh.

# Ví dụ: A lãi 3, B lãi 5; máy 8h, liệu 8kg
# max 3*A + 5*B với A + 2*B <= 8, 2*A + B <= 8
# thử từng đỉnh miền khả thi là ra đáp án

Ví dụ xưởng sản xuất

• Mỗi sản phẩm tốn định mức máy và liệu khác nhau.
• Đọc nghiệm còn đọc giá bóng: nới 1 giờ máy thì lãi thêm bao nhiêu.
• Ràng buộc nào đang thắt thì đầu tư vào đó.
• Đây là cầu nối giữa toán tối ưu và quyết định kinh doanh.

Khi nào dùng

• Hợp khi chi phí và tiêu hao xấp xỉ tuyến tính.
• Biến nhận giá trị lẻ được như số giờ, số kg.
• Không hợp khi biến phải nguyên như số xe, số người.
• Viết sai hàm mục tiêu là lỗi nguy hiểm nhất.

Ví dụ

• Input: xưởng A lãi 3, B lãi 5, máy và liệu đều 8. Output: sản lượng tối ưu ở 1 đỉnh.
• Giải thích: nghiệm tuyến tính trên đa diện lồi luôn ở đỉnh.
• Input: nới ràng buộc đang thắt thêm 1 đơn vị. Output: lợi nhuận không giảm.
• Giải thích: nới chỗ thắt thì miền rộng ra, nghiệm chỉ tốt hơn.

💻 Bài tập

Ngôn ngữ: Python 3. Bài 2-3 dùng scipy.optimize.linprog hoặc PuLP. Nộp vào day-076/.

Bài 1: Giải bằng đỉnh (2 biến)

Viết solve_2d(c, A, b) cho bài: cực đại $c^T x$ với $Ax \le b$, $x \ge 0$, đúng 2 biến.

1. Tìm mọi giao điểm của từng cặp đường biên (kể cả trục tọa độ).
2. Giữ các điểm thỏa mọi ràng buộc.
3. Trả điểm có giá trị mục tiêu lớn nhất. Miền rỗng thì báo infeasible.

max 3A + 5B, A + 2B <= 8, 2A + B <= 8 -> A = B = 8/3, giá trị 21.33
Đỉnh khả thi: (0,0), (4,0), (0,4), (8/3, 8/3)
A + B <= 1, A + B >= 3                -> infeasible

Vẽ miền khả thi và đường mức hàm mục tiêu bằng matplotlib.

Bài 2: Lập kế hoạch sản xuất

Xưởng làm 3 sản phẩm bàn, ghế, tủ:

            gỗ(m3)   giờ_máy   giờ_công   lãi(triệu)
bàn         0.5      2         3          1.2
ghế         0.2      1         1          0.5
tủ          1.0      3         4          2.0
Giới hạn:   40       120       150
Ghế ít nhất 2 lần số bàn (bộ bàn ghế).

1. Viết mô hình: biến, hàm mục tiêu, ràng buộc (dạng toán trong README.md).
2. Giải bằng linprog. In sản lượng tối ưu và lãi.
3. In giá bóng (dual value) của 3 tài nguyên. Nếu được mua thêm 10 giờ máy giá 0.3 triệu/giờ thì có nên mua không?

Bài 3: Capacity planning và số nguyên (nâng cao)

Công ty chọn thuê máy chủ 3 loại để phục vụ tải 2000 req/s, bộ nhớ ít nhất 512 GB:

loại    req/s   RAM(GB)   giá/tháng
small   150     16        40
medium  400     64        110
large   900     128       230

1. Giải LP thường (cho phép số máy lẻ). In chi phí.
2. Giải bài số nguyên (ILP) bằng PuLP hoặc scipy.optimize.milp. So chi phí.
3. Làm tròn lên nghiệm LP. So với ILP. Viết 2 câu vì sao làm tròn không luôn tối ưu.

✅ Tiêu chí hoàn thành

• solve_2d khớp linprog trên 20 bài 2 biến ngẫu nhiên.
• Bài 2 có mô hình toán, nghiệm và quyết định mua giờ máy dựa trên giá bóng.
• Bài 3 có bảng LP, làm tròn, ILP.
• Có hình miền khả thi.

❓ Câu hỏi ôn tập

• Hàm mục tiêu và ràng buộc là gì?
• Vì sao nghiệm tối ưu nằm ở đỉnh?
• Giá bóng của ràng buộc nghĩa là gì?
• Khi nào không nên ép bài toán thành tuyến tính?

🌕 Bạn đã hoàn thành ngày 76. Làm hết bài tập phía trên rồi sang ngày tiếp theo.