Tối ưu tuyến tính và mô hình hóa

Tối ưu hóa tuyến tính là một kỹ thuật tìm ra kết quả tối ưu trong một mô hình toán học với hàm mục tiêu và ràng buộc tuyến tính. Một mô hình tối ưu tuyến tính có dạng sau

$$\begin{aligned} \text{min} \quad & c^Tx && \\ \text{s.t} \quad & Ax & \leq & \quad b \\ & x & \geq & \quad 0 \\ \end{aligned}$$

Trong đó $b$, $c$ là các vector cột hằng số, $A$ là ma trận hằng số, $x$ là một vector cột đại diện cho các biến số.

Hiện nay đã có nhiều solver giải mô hình LP rất hiệu quả, tiêu biểu như Gurobi, SCIP hay COIN-OR. Vì vậy nếu ta có thể mô hình hóa được bài toán về một mô hình LP thì bài toán coi như đã được giải quyết. Tuy nhiên mô hình hóa bài toán không phải lúc nào cũng dễ dàng vì một số lý do sau.

• Để mô hình hóa tất cả các điều kiện của một bài toán về dạng tuyến tính không hề đơn giản.
• Có nhiều cách mô hình hóa một bài toán, nhưng không phải mô hình nào cũng hiệu quả. Một mô hình dù mô tả chính xác bài toán nhưng lại quá lớn hoặc các điều kiện không chặt chẽ có thể dẫn đến việc tốn rất rất nhiều thời gian để giải mô hình.
• Đôi khi phải xây dựng nhiều mô hình để giải quyết một bài toán, việc xây dựng từng mô hình và tương tác giữa các mô hình sao cho hiệu quả cũng là một vấn đề.

Trong công việc của mình, tối ưu tuyến tính được sử dụng rất nhiều và cũng không ít lần mình thấy được sự đột phá từ cách mô hình hóa. Vì vậy đối với mình, kỹ năng mô hình hóa là một kỹ năng vô cùng quan trọng và không dễ dàng để thành thạo.

Bạn đọc có thể tham khảo các kỹ thuật mô hình hóa tại MOSEK Modeling Cookbook. Happy learning!