Lập trình tuyến tính nguyên (Integer Linear Programming) là gì?
Là phương pháp toán học gồm các biến nguyên, hàm mục tiêu tuyến tính và ràng buộc tuyến tính. Giúp tìm kết quả tối thiểu/tối đa trong điều kiện nhất định, phân bổ nguồn lực hạn chế tối ưu. 3 thành phần chính:
- Biến quyết định (Decision Variables): Biến cần xác định để tối ưu hàm mục tiêu.
- Hàm mục tiêu (Objective Function): Biểu thức mối quan hệ giữa kết quả và biến.
- Ràng buộc (Constraints): Điều kiện giới hạn các nghiệm khả thi.
Bài viết cũng bao gồm ví dụ Lập trình tuyến tính nguyên hỗn hợp (Mixed-Integer) (biến liên tục + nguyên).
Các bước giải Integer Linear Programming trong Excel
Ví dụ: Máy sản xuất 2 sản phẩm thay thế. Thiết lập 1: max 20 sp1, 10 sp2/ngày. Thiết lập 2: max 12 sp1, 25 sp2/ngày. Nhu cầu tối đa 35 sp/ngày. Lợi nhuận: sp1=$10, sp2=$12. Chọn thiết lập nào?
BƯỚC 1: Phân tích đề bài & tạo bộ dữ liệu
- Biến quyết định: X1 (sản lượng sp1), X2 (sản lượng sp2), Y (1 nếu chọn thiết lập 1, 0 nếu chọn thiết lập 2).
- Hàm mục tiêu: Max Z = 10X1 + 12X2.
- Ràng buộc:
- X1 + X2 ≤ 35 (nhu cầu)
- X1 - 8Y ≤ 12 (sp1)
- X2 + 15Y ≤ 25 (sp2)
- Y ∈ {0,1}
- X1, X2 ≥ 0
- Tạo bảng tính chứa hệ số ràng buộc, hàm mục tiêu, biến quyết định.
BƯỚC 2: Nạp Solver Add-in
- File → Options → Add-ins → Manage: Excel Add-ins → Go.
- Tích Solver Add-in → OK.
- Solver xuất hiện ở tab Data → nhóm Analysis.
BƯỚC 3: Nhập hệ số ràng buộc & hàm mục tiêu
- Điền hệ số của 3 ràng buộc vào bảng (cột X1, X2, Y, dấu, RHS).
- Ô Total (cột E): công thức
=SUMPRODUCT($B$6:$D$6,B10:D10)(biến quyết định × hệ số ràng buộc) → kéo xuống. - Điền hệ số hàm mục tiêu (10, 12, 0) → ô E16:
=SUMPRODUCT($B$6:$D$6,B16:D16).
BƯỚC 4: Thiết lập Solver Parameters
- Data → Solver → hộp thoại Solver Parameters.
- Set Objective: $E$16 (giá trị hàm mục tiêu).
- Chọn Max.
- By Changing Variable Cells: $B$6:$D$6 (X1, X2, Y).
BƯỚC 5: Thêm ràng buộc (Subject to Constraints)
- Click Add → Cell Reference: $D$6 (ô Y) → chọn bin (nhị phân 0/1) → OK.
- Click Add → Cell Reference: $E$10:$E$12 (Total ràng buộc) → ≤ → Constraint: =$G$10:$G$12 (RHS) → OK.
- Click Add → Cell Reference: $B$6:$C$6 (X1, X2) → chọn int (nguyên) → OK.
BƯỚC 6: Chọn phương pháp giải
- Select a Solving Method: Simplex LP.
- Tích Make Unconstrained Variables Non-Negative.
- Nhấn Solve → chọn Keep Solver Solution → OK.
BƯỚC 7: Kết quả
Giải pháp tối ưu: chọn thiết lập máy 2 (Y=0), X1=12, X2=23, Z=$396.
BƯỚC 8: Tạo báo cáo Answer Report
- Trong Solver Results → Reports chọn Answer → OK → báo cáo trên sheet mới.
Ví dụ Mixed Integer Linear Programming
Hàm mục tiêu: Min Z = 2.39X1 + 1.99X2 + 2.99X3 + 300Y1 + 250Y2 + 400Y3
Ràng buộc:
- X1 + X2 + X3 = 1000
- X1 - 400Y1 ≤ 0
- X2 - 550Y2 ≤ 0
- X3 - 600Y3 ≤ 0
X1, X2, X3 nguyên; Y1, Y2, Y3 nhị phân. Tìm Min Z.
Thực hiện tương tự: tạo bảng hệ số, SUMPRODUCT, Solver Parameters (Min), thêm ràng buộc (bin cho Y, int cho X), Simplex LP, Solve.
Kết quả: X1=400, X2=550, X3=50, Y1=1, Y2=1, Y3=1, Min Z = $3.445,00.
Kết luận
Bài viết đã trình bày quy trình từng bước giải Integer Linear Programming và Mixed-Integer trong Excel bằng Solver. File thực hành đính kèm đầu bài. Ghé ExcelDemy để xem thêm. Mọi thắc mắc hãy comment bên dưới!