Tối ưu hoá 2 — Quy hoạch tuyến tính (LP)

Vì sao LP là "con ngựa thồ" của vận trù học

Trong bài tổng quan chúng ta đã phân loại các bài toán tối ưu theo bản chất biến và hàm mục tiêu. Quy hoạch tuyến tính (Linear Programming — LP) là lớp bài toán được nghiên cứu kỹ nhất, giải nhanh nhất và ứng dụng rộng nhất trong toàn bộ vận trù học (Operations Research — OR). Lý do đơn giản: LP mô tả được một lượng khổng lồ bài toán quyết định kinh doanh thực tế, mà lại có thuật toán giải cực kỳ hiệu quả — bài toán vài chục nghìn biến, vài chục nghìn ràng buộc vẫn giải xong trong vài giây trên máy tính bàn.

LP là bài toán tối ưu trong đó cả hàm mục tiêu lẫn tất cả ràng buộc đều là hàm tuyến tính của các biến quyết định, và biến nhận giá trị liên tục (số thực, không bắt buộc nguyên). Chỉ cần một trong hai điều kiện đó bị phá vỡ — mục tiêu/ràng buộc phi tuyến, hoặc biến buộc nguyên — bài toán không còn là LP nữa và bài toán trở nên khó hơn nhiều (biến nguyên dẫn tới quy hoạch nguyên ở bài 3).

Với cán bộ dữ liệu ngân hàng, LP không phải thứ hàn lâm xa vời: phân bổ ngân sách marketing giữa các kênh, phân bổ vốn giữa các sản phẩm cho vay để tối đa lợi nhuận biên dưới ràng buộc rủi ro/thanh khoản, tối ưu khẩu phần chi phí vận hành — tất cả đều là LP.

1. Dạng chuẩn của bài toán LP

Một bài toán LP luôn quy về được dạng chuẩn. Ví dụ dạng cực đại (maximization):

max   c₁x₁ + c₂x₂ + ... + cₙxₙ        (hàm mục tiêu — objective)
s.t.  a₁₁x₁ + ... + a₁ₙxₙ ≤ b₁        (ràng buộc 1)
      a₂₁x₁ + ... + a₂ₙxₙ ≤ b₂        (ràng buộc 2)
      ...
      x₁, x₂, ..., xₙ ≥ 0            (ràng buộc không âm)

Viết gọn dạng ma trận:

max cᵀx s.t. Ax ≤ b, x ≥ 0

Trong đó:

• x = vector biến quyết định (decision variables) — thứ ta điều khiển được.
• c = vector hệ số mục tiêu (ví dụ: lợi nhuận biên mỗi đơn vị).
• A, b = ma trận và vector định nghĩa các ràng buộc (constraints) về nguồn lực.

Vài lưu ý quy đổi thực dụng:

• Bài toán min đổi thành max bằng cách đổi dấu mục tiêu: min cᵀx ≡ max (−cᵀx).
• Ràng buộc ≥ đổi thành ≤ bằng cách nhân −1 cả hai vế.
• Ràng buộc đẳng thức = tách thành hai bất đẳng thức ≤ và ≥.
• Biến tự do (có thể âm) tách thành hiệu hai biến không âm: x = x⁺ − x⁻.

Điểm mấu chốt: mọi LP đều tương đương một dạng chuẩn, nên thuật toán chỉ cần biết giải một dạng là đủ. Solver lo phần quy đổi.

2. Mô hình hoá — kỹ năng cốt lõi

Giải LP là việc của solver; mô hình hoá (formulation) — dịch một bài toán kinh doanh mù mờ thành LP đúng — mới là kỹ năng thật sự phân biệt người làm được việc. Quy trình gồm ba câu hỏi, luôn theo đúng thứ tự:

1. Biến quyết định là gì? — Ta được phép điều chỉnh những đại lượng nào? Đây là ẩn số. Định nghĩa sai biến thì cả mô hình sai.
2. Mục tiêu là gì? — Tối đa (lợi nhuận, doanh thu, độ phủ) hay tối thiểu (chi phí, rủi ro, lãng phí)? Viết thành biểu thức tuyến tính của biến.
3. Ràng buộc là gì? — Những giới hạn nào bó buộc quyết định: ngân sách, năng lực, tồn kho, quy định, nhu cầu tối thiểu? Mỗi giới hạn thành một bất đẳng thức tuyến tính.

Các họ bài toán LP kinh điển đáng thuộc nằm lòng:

Ví dụ mô hình hoá: product mix

Một xưởng làm hai sản phẩm A, B. Mỗi đơn vị A lời 40, B lời 30. A cần 2 giờ máy + 1 kg vật liệu; B cần 1 giờ máy + 2 kg vật liệu. Có 100 giờ máy và 80 kg vật liệu.

• Biến: x_A, x_B = số đơn vị sản xuất mỗi loại.
• Mục tiêu: max 40·x_A + 30·x_B.
• Ràng buộc: 2·x_A + 1·x_B ≤ 100 (giờ máy); 1·x_A + 2·x_B ≤ 80 (vật liệu); x_A, x_B ≥ 0.

Nghiệm tối ưu: x_A = 40, x_B = 20, lợi nhuận = 40·40 + 30·20 = 2200. Ta sẽ dùng lại ví dụ này ở phần shadow price.

3. Hình học: miền khả thi và nghiệm ở đỉnh

Tập tất cả các điểm x thoả mọi ràng buộc gọi là miền khả thi (feasible region). Với LP, mỗi bất đẳng thức tuyến tính cắt không gian thành một nửa mặt phẳng (half-space); giao của nhiều nửa không gian là một đa diện lồi (convex polytope) — hình có các cạnh phẳng và không có "chỗ lõm".

Định lý nền tảng của LP: nếu có nghiệm tối ưu hữu hạn thì luôn tồn tại một nghiệm tối ưu tại một ĐỈNH (vertex/corner point) của miền khả thi. Trực giác: hàm mục tiêu tuyến tính giống như một mặt phẳng nghiêng; "đẩy" mặt phẳng đó theo hướng tăng giá trị, điểm cuối cùng còn chạm miền khả thi luôn là một đỉnh (hoặc cả một cạnh, khi có nhiều nghiệm).

Hệ quả cực kỳ quan trọng cho thuật toán: không cần dò vô hạn điểm bên trong miền khả thi — chỉ cần xét hữu hạn các đỉnh. Số đỉnh có thể rất lớn nhưng vẫn hữu hạn.

4. Simplex và interior point

4.1 Thuật toán Simplex — trực giác

Simplex (Dantzig, 1947) khai thác đúng định lý "nghiệm ở đỉnh". Ý tưởng, bỏ qua toán nặng:

1. Bắt đầu tại một đỉnh khả thi bất kỳ (thường là gốc toạ độ nếu khả thi).
2. Nhìn các cạnh xuất phát từ đỉnh hiện tại. Nếu đi dọc cạnh nào đó làm mục tiêu cải thiện, di chuyển sang đỉnh kề đầu cạnh ấy.
3. Lặp lại: mỗi bước nhảy sang một đỉnh kề tốt hơn.
4. Khi không còn cạnh nào cải thiện được mục tiêu → đỉnh hiện tại là tối ưu, dừng.

Nói cách khác, Simplex "leo dọc mép" của đa diện, mỗi bước cải thiện mục tiêu, cho tới khi không leo được nữa. Vì đa diện lồi, đỉnh tối ưu cục bộ cũng là toàn cục — không kẹt ở "đỉnh giả".

Về lý thuyết Simplex có thể chạy chậm theo hàm mũ trong các trường hợp bệnh lý dựng riêng, nhưng trong thực tế nó cực nhanh và là mặc định của hầu hết solver.

4.2 Interior point — khái quát

Họ thuật toán điểm trong (interior point) tiếp cận khác hẳn: thay vì leo dọc mép, nó đi xuyên qua bên trong miền khả thi theo một đường cong ("central path"), tiến dần về nghiệm tối ưu ở biên. Ưu điểm: có bảo đảm lý thuyết về số bước (polynomial), và thường nhanh hơn Simplex trên các bài toán rất lớn và thưa (sparse). Solver hiện đại thường có cả hai và tự chọn, hoặc cho người dùng chỉ định — chi tiết công cụ ở bài về solver.

5. Đối ngẫu (duality) và shadow price

Đây là phần "đắt giá" nhất của LP với người làm quyết định. Mỗi bài toán LP (gọi là primal) luôn có một bài toán đối ngẫu (dual) đi kèm. Nếu primal là "tối đa lợi nhuận dưới ràng buộc nguồn lực", thì dual là "định giá các nguồn lực sao cho tối thiểu tổng giá trị nguồn lực mà vẫn đủ bù mọi hoạt động của primal".

Định lý đối ngẫu mạnh (strong duality): tại nghiệm tối ưu, giá trị mục tiêu của primal bằng đúng giá trị mục tiêu của dual. Nghiệm của dual chính là giá bóng (shadow price) của các ràng buộc.

Shadow price — giá bóng

Shadow price của một ràng buộc = mức thay đổi giá trị mục tiêu tối ưu khi nới lỏng ràng buộc đó thêm một đơn vị (giữ nguyên các yếu tố khác). Nói ngôn ngữ ngân hàng: "nếu tôi có thêm một đơn vị nguồn lực này, lợi nhuận tối ưu tăng thêm bao nhiêu?" — chính là giá trị biên của nguồn lực đó với ta.

Quay lại ví dụ product mix (nghiệm x_A=40, x_B=20, lợi nhuận 2200):

• Cả hai ràng buộc (giờ máy và vật liệu) đều chặt (binding) — dùng hết 100 giờ và 80 kg. Ràng buộc chặt thường có shadow price > 0.
• Giả sử shadow price của giờ máy là 16.67 và của vật liệu là 6.67 (minh hoạ, tính từ dual). Nghĩa là: mua thêm 1 giờ máy đáng giá tới 16.67 đơn vị lợi nhuận, còn 1 kg vật liệu chỉ đáng 6.67.

Ứng dụng ra quyết định: nếu thị trường bán 1 giờ máy thuê ngoài giá 10 (< 16.67), thuê thêm là có lời; nếu vật liệu chào giá 8 (> 6.67), mua thêm là lỗ. Shadow price cho ta biết nên đầu tư nới cái gì trước.

Lưu ý: ràng buộc không chặt (slack còn dư) có shadow price = 0 — nới thêm nguồn lực đang thừa thì vô ích (complementary slackness).

6. Phân tích độ nhạy (sensitivity analysis)

Trong thực tế, hệ số c, b, A đều là ước lượng (lợi nhuận biên dự phóng, nguồn lực dự kiến) — có sai số. Phân tích độ nhạy trả lời: nghiệm tối ưu và giá trị mục tiêu thay đổi thế nào khi các con số đầu vào thay đổi? Đây là bước bắt buộc trước khi tin vào nghiệm.

Hai câu hỏi chính solver trả lời sẵn:

• Khoảng ổn định của hệ số mục tiêu (c): hệ số lợi nhuận biên của một sản phẩm được phép dao động trong khoảng nào mà cấu trúc nghiệm (bộ đỉnh tối ưu) không đổi? Nếu lợi nhuận biên A có thể dao động lớn mà vẫn nên sản xuất x_A=40, quyết định robust; nếu chỉ lệch nhẹ đã đổi nghiệm, phải đo lại số cho chắc.
• Khoảng hiệu lực của shadow price (vế phải b): shadow price 16.67/giờ máy chỉ đúng trong một khoảng nới nhất định. Nới quá khoảng đó, một ràng buộc khác trở thành chặt và shadow price nhảy sang giá trị mới. Đừng ngoại suy "thêm 1000 giờ máy × 16.67" cho cả nghìn giờ.

Phân tích độ nhạy đặc biệt quan trọng ở ngân hàng, nơi đầu vào (lãi suất, tỷ lệ vỡ nợ dự phóng, chi phí vốn) luôn không chắc. Khi bất định lớn, cần công cụ mạnh hơn: tối ưu ngẫu nhiên / robust ở bài 7.

7. Các trường hợp đặc biệt

Không phải LP nào cũng có một nghiệm gọn đẹp. Cần nhận ra bốn tình huống:

Trong thực chiến, gặp INFEASIBLE hay UNBOUNDED hầu như luôn là lỗi mô hình hoá, không phải bài toán thật vô nghiệm. Infeasible = ta viết quá nhiều/quá chặt ràng buộc; Unbounded = ta quên một ràng buộc chặn trên. Đọc kỹ lại danh sách ràng buộc.

8. LP relaxation — cầu nối tới quy hoạch nguyên

Nhiều bài toán thực đòi biến nguyên (số hồ sơ duyệt, số ATM đặt, chọn/không chọn dự án 0-1). Đó là quy hoạch nguyên (Integer Programming — IP), khó hơn LP nhiều. Một kỹ thuật nền: LP relaxation — bỏ ràng buộc nguyên, giải bài toán như LP liên tục. Nghiệm LP relaxation cho một cận (bound) trên giá trị tối ưu của IP, và làm điểm khởi đầu cho thuật toán branch-and-bound. Chi tiết ở bài 3 về IP/MILP.

Use case thực tế

Bối cảnh: phân bổ ngân sách vốn cho vay giữa 3 sản phẩm

Khối Kinh doanh NCB có quỹ vốn 500 tỷ để phân bổ cho ba sản phẩm cho vay trong quý: Vay tiêu dùng (TD), Thẻ tín dụng (TTD), Vay mua nhà (MN). Mục tiêu: tối đa lợi nhuận biên kỳ vọng. Dữ liệu (minh hoạ):

Ràng buộc quản trị rủi ro: tổng vốn ≤ 500 tỷ; mỗi sản phẩm ≤ trần hấp thụ; nhóm rủi ro cao (TD) ≤ 40% tổng vốn giải ngân; nhóm an toàn (MN) ≥ 30% tổng vốn giải ngân.

Mô hình LP:

• Biến: x_TD, x_TTD, x_MN (tỷ đồng phân bổ mỗi sản phẩm).
• Mục tiêu: max 0.09·x_TD + 0.07·x_TTD + 0.045·x_MN.
• Ràng buộc:
  • x_TD + x_TTD + x_MN ≤ 500
  • x_TD ≤ 250; x_TTD ≤ 150; x_MN ≤ 400
  • x_TD ≤ 0.40·(x_TD + x_TTD + x_MN) → 0.6·x_TD − 0.4·x_TTD − 0.4·x_MN ≤ 0
  • x_MN ≥ 0.30·(x_TD + x_TTD + x_MN) → −0.3·x_TD − 0.3·x_TTD + 0.7·x_MN ≥ 0
  • x_TD, x_TTD, x_MN ≥ 0

Pseudocode bằng PuLP (Python) minh hoạ cách khai báo — không phải SQL, chỉ để đọc hiểu:

# Minh hoạ mô hình LP bằng PuLP (KHÔNG chạy trên sandbox SQL)
from pulp import LpProblem, LpMaximize, LpVariable, lpSum, value

prob = LpProblem("phan_bo_von", LpMaximize)
x_TD  = LpVariable("TieuDung", lowBound=0, upBound=250)
x_TTD = LpVariable("The",       lowBound=0, upBound=150)
x_MN  = LpVariable("MuaNha",    lowBound=0, upBound=400)
tong  = x_TD + x_TTD + x_MN

prob += 0.09*x_TD + 0.07*x_TTD + 0.045*x_MN     # mục tiêu

prob += tong <= 500                              # trần tổng vốn
prob += x_TD <= 0.40 * tong                      # nhóm rủi ro cao
prob += x_MN >= 0.30 * tong                      # sàn nhóm an toàn

prob.solve()
for v in prob.variables():
    print(v.name, "=", value(v))
print("Loi nhuan =", value(prob.objective))
# Đọc thêm shadow price: [c.pi for c in prob.constraints.values()]

Diễn giải kết quả (định tính): ràng buộc tổng vốn ≤ 500 gần như luôn chặt — shadow price của nó chính là "mỗi tỷ vốn tăng thêm mang lại bao nhiêu lợi nhuận biên", con số này so với chi phí vốn cho Khối Nguồn vốn biết có nên huy động thêm để giải ngân không (liên hệ Treasury/ALM). Ràng buộc trần 40% cho TD nhiều khả năng cũng chặt (TD lời nhất nên LP muốn dồn vào tối đa); shadow price của nó cho biết nới khẩu vị rủi ro thêm 1% đáng giá bao nhiêu lợi nhuận — đầu vào định lượng cho hội đồng rủi ro cân nhắc, thay vì tranh luận cảm tính.

Các hệ số lợi nhuận biên là dự phóng, nên phân tích độ nhạy phải đi kèm: nếu lợi nhuận biên TD (0.09) có thể tụt xuống 0.06 mà cấu trúc phân bổ vẫn tối ưu thì quyết định vững; nếu chỉ tụt nhẹ đã lật nghiệm, cần đo lại rủi ro/lợi nhuận TD cho chắc trước khi cam kết vốn.

Truy vấn dữ liệu đầu vào cho mô hình

Trước khi dựng LP, thường cần lấy số liệu nền như quy mô số dư theo loại tiền để ước lượng nguồn vốn khả dụng. Ví dụ SELECT trên sandbox:

-- ▶ Chạy được
SELECT currency, COUNT(*) AS so_tk, SUM(balance) AS tong_so_du
FROM accounts
GROUP BY currency
ORDER BY tong_so_du DESC;

Kết quả (tổng số dư mỗi loại tiền) là một đầu vào ước lượng cho vế phải b của các ràng buộc nguồn vốn trong mô hình LP.

Ghi nhớ

• LP = tối ưu khi mục tiêu và mọi ràng buộc đều tuyến tính và biến liên tục. Dạng chuẩn: max cᵀx s.t. Ax ≤ b, x ≥ 0; mọi LP quy về được dạng này.
• Mô hình hoá là kỹ năng cốt lõi, theo 3 bước: xác định biến quyết định → hàm mục tiêu → ràng buộc. Định nghĩa sai biến thì sai cả mô hình.
• Miền khả thi là đa diện lồi; nếu có nghiệm tối ưu hữu hạn thì luôn có một nghiệm tại đỉnh → chỉ cần xét hữu hạn đỉnh.
• Simplex leo dọc mép đa diện, mỗi bước nhảy sang đỉnh kề tốt hơn tới khi không cải thiện được; interior point đi xuyên bên trong, mạnh với bài toán rất lớn/thưa.
• Duality: giá trị primal = dual tại tối ưu. Shadow price = lợi nhuận tăng thêm khi nới 1 đơn vị ràng buộc → công cụ ra quyết định "nên đầu tư nới cái gì". Ràng buộc không chặt có shadow price = 0.
• Phân tích độ nhạy cho biết khoảng ổn định của nghiệm khi hệ số/vế phải đổi — bắt buộc khi đầu vào không chắc (lãi suất, tỷ lệ vỡ nợ).
• Bốn trường hợp: nghiệm duy nhất, nhiều nghiệm, vô nghiệm (infeasible), không giới nội (unbounded) — hai cái sau hầu như luôn là lỗi mô hình hoá.
• LP relaxation (bỏ ràng buộc nguyên) cho cận và khởi đầu cho quy hoạch nguyên (bài 3).