Tối ưu hóa được áp dụng trong nhiều lĩnh vực như sản xuất, kinh tế, tài chính, điều khiển, thống kê, giao thông, v.v…. Phần này xin giới thiệu về bài toán quy hoạch tuyến tính, một lĩnh vực quan trọng của tối ưu hóa.

Bài toán quy hoạch tuyến tính

Bài toán tối ưu tổng quát có dạng như sau: \[\begin{aligned}
\rm{minimize}~ & f_0(x)\\
\rm{subject~to}~ &f_i(x) \leq b_i ,i=1,…,m.\end{aligned}\] Trong đó, vector \(x=(x_1,\ldots,x_n)\in \mathbf{R}^n\) là biến số. Hàm \(f_0(x)\) được gọi là hàm mục tiêu. Có \(m\) ràng buộc trong bài toán tối ưu trên. Ràng buộc thứ \(i\) là \(f_i(x) \leq b_i\).

Bạn đang xem: giải bài toán quy hoạch tuyến tính bằng phương pháp hình học

Ta có thể đưa một bài toán tối ưu bất kỳ về dạng như trên. Nếu bài toán tối ưu là tối đa hóa hàm mục tiêu \(f_0(x)\), ví dụ tối đa hóa lợi nhuận, thì ta có thể thay hàm mục tiêu bằng \(min. -f_0(x)\). Các ràng buộc cũng có thể đưa về dạng như trên.

Ta cần một số định nghĩa sau trước khi giới thiệu về bài toán quy hoạch tuyến tính:

• Siêu phẳng (hyperplane) là tập hợp những điểm thỏa mãn \(a^T x = b\).
• Nửa không gian (half space) định nghĩa bởi siêu phẳng \(a^T x \leq b\), \(x \in \mathbf{R}^n\) (xem Hình 1. Như vậy siêu phẳng \(a^T x = b\) sẽ chia không gian \(\mathbf{R}^n\) ra thành hai nửa không gian \(a^T x \leq b\) và \(a^T x \geq b\)
  

  

• Đa điện (polyhedron) được định nghĩa là tập hợp giao bởi các nửa không gian và siêu phẳng là tập lồi \[\begin{aligned}
  \mathbf{P} = \{x | A x \leq b, C x = d \}.\end{aligned}\]

Bài toán quy hoạch tuyến tính là một bài toán tối ưu trong đó các hàm mục tiêu và hàm ràng buộc \(f_i(x),\ i=0,\ldots,m\) đều có dạng tuyến tính: \[\begin{aligned}
\rm{minimize}~ &c^Tx \qquad \qquad \qquad \qquad  (1)\\
\rm{subject~to}~ &a_i^Tx \leq b_i ,i=1,\ldots,\ m.\end{aligned}\] Ta cũng có thể biểu diễn ràng buộc dạng ma trận \(Ax \leq b\), trong đó \(c,a_1,\ldots,a_m \in \mathbf{R}^n\), \(A=\left[\begin{matrix}a_1^T\\
\ldots\\a_m^T
\end{matrix}\right]\), và \(b=\left[\begin{matrix}b_1\\
\ldots\\
b_m
\end{matrix}\right]\).

Sau đây là vài ví dụ về bài toán quy hoạch tuyến tính.

Ví dụ 1

\[\begin{aligned}
\mathrm{min.}~ & f = x_1+x_2 \qquad \qquad \qquad \qquad  (2)\label{eq:chap1_ex1}\\
\mathrm{s.t.}~ & x_1+2x_2\geq 2,\nonumber\\
& 3x_1+x_2\geq 2,\nonumber\\
& x_1 \geq 0,\nonumber\\
& x_2 \geq 0. \nonumber \end{aligned}\]

Hình 2 mô tả hàm mục tiêu và miền khả thi (feasible region) của bài toán trên giúp bạn đọc có cảm giác về nghiệm của bài toán tối ưu. Miền khả thi tức là tập hợp các điểm thỏa mãn các ràng buộc. Miền khả thi của một bài toán quy hoạch tuyến tính là một đa diện (polyhedron).

Trong các sách về quy hoạch tuyến tính truyền thống mà giải thuật đơn hình (simplex) được giới thiệu như một phương pháp chính để giải bài toán, bài toán LP được giới thiệu ở dạng chính tắc như sau: \[\begin{aligned}
\rm{maximize}~ &c^Tx \qquad \qquad \qquad \qquad  (2)\\
\rm{subject~to}~ &a_i^Tx \leq b_i ,i=1,\ldots,\ m\\
& x \geq 0.
\label{eq-standardLP}\end{aligned}\] Bài toán dạng chính tắc là đầu vào của giải thuật đơn hình.

Thực ra, ta có thể biến đổi một bài toán LP bất kỳ về dạng chính tắc (2), ví dụ như:

• Nếu hàm mục tiêu là \(\rm{min.}~c^Tx\) thì có thể thay bằng \(\rm{max.}~ -c^Tx\).
• Nếu ràng buộc là \(a_i^Tx \geq b_i\) thì có thể thay bằng \(-a_i^Tx \leq -b_i\).
• Nếu ràng buộc là \(a_i^Tx = b_i\) thì có thể thay bằng hai ràng buộc tương đương: \(a_i^Tx \geq b_i\) và \(a_i^Tx \leq b_i\).
• Nếu không có ràng buộc \(x_i \geq 0\) thì có thể thay biến \(x_i = x_i^+ – x_i^-\), trong đó \(x_i^+, x_i^- \geq 0\).

Ví dụ 2 – Bài toán dinh dưỡng

Để đảm bảo được dinh dưỡng, một người trung bình cần cho mỗi ngày:

• Không ít hơn 200 gam chất bột đường (carbohydrate)
• Không ít hơn 20 gam chất đạm (protein)

Hàm lượng dinh dưỡng các chất này trong 04 loại lương thực hiện có trong một cửa hàng trong 1000 gram được liệt kê ở bảng sau:

Ghi chú: các số liệu trên chỉ dùng để minh họa cho ví dụ.

Như vậy người đó cần tối thiểu là bao nhiêu tiền đề đảm bảo được dinh dưỡng cho bữa ăn. Bài toán dinh dưỡng được mô hình dưới dạng bài toán quy doạch tuyến tính như sau: Gọi \(x_c, x_g, x_k, x_b\) là số gram cà rốt, gạo, khoai tây và bột mì cần mua. Hàm mục tiêu là tổng số tiền: \[\begin{aligned}
50x_c+20x_g+10x_k+30x_b\end{aligned}\] Các ràng buộc bao gồm:

• Đảm bảo về hàm lượng bột đường: \[\begin{aligned}
  300x_c+400x_g+400x_k+500x_b \geq 200\end{aligned}\]
• Đảm bảo về hàm lượng đạm: \[\begin{aligned}
  30x_c+10x_g+20x_k+50x_b\geq20\end{aligned}\]
• Ngoài ra còn có ràng buộc không âm cho các biến: \(x_c\geq0,\ x_g \geq 0,x_k \geq 0,x_b\geq0\).

Như vậy, bài toán quy hoạch tuyến tính cho dinh dưỡng sẽ là: \[\begin{aligned}
\mathrm{min.~}& 50x_c+20x_g+10x_k+30x_b \qquad \qquad \qquad \qquad  (3)\\
\mathrm{s.t.~} & 300x_c+400x_g+400x_k+500x_b\geq200,\nonumber\\
& 30x_c+10x_g+20x_k+50x_b\geq20,\nonumber\\
& x_c\geq0,\ x_g\geq0,x_k\geq0,x_b\geq0. \nonumber \end{aligned}\]

Giải bài toán quy hoạch tuyến tính bằng CVXPY solver

Có nhiều thư viện cho phép giải một bài toán quy hoạch tuyến tính. Sách này xin giới thiệu thư viện CVXPY dùng trong ngôn ngữ Python.

Xem thêm: disclosure là gì

import cvxpy as cp
import numpy as np

c = np.array([50, 20, 10, 30])
A = np.array([[300, 400, 400, 500],[30, 10, 20, 50]])
b = np.array([200, 20])

x = cp.Variable(4)
constraint = [A@x >= b, x >=0]
prob = cp.Problem(cp.Minimize(c.T@x), constraint)
prob.solve()

# Print result.
print("\nThe optimal value is", prob.value)
print("A solution x is")
print(x.value)

Sau khi chạy chương trình trên, kết quả là

The optimal value is 10.00000000258857
A solution x is
[-3.91830413e-11  1.48147374e-11  9.99999999e-01  5.39124665e-10]

Như vậy để đảm bảo dinh dưỡng, mua 1 kg khoai tây là tiết kiệm nhất (10 ngàn).

Bạn đọc nên tìm hiểu thêm cách sử dụng CVXPY tại https://www.cvxpy.org/tutorial/.

Nghiệm của bài toán LP

Một bài toán LP có thể có 3 loại nghiệm:

• Bài toán có nghiệm hữu hạn: ví dụ như bài toán được cho trong hai ví dụ trên.
• Bài toán vô nghiệm: Một bài toán LP là vô nghiệm khi miền khả thi không tồn tại. Ví dụ bài toán sau là vô nghiệm \[\begin{aligned}
  \rm{min.}~ & x_1+x_2 \\
  \rm{s.t.}~ & x_1-2x_2 \geq 2,\\
  & x_1 \geq 0,\\
  & x_1 \leq -3.
  \end{aligned}\] Không tồn tại miền khả thi đồng thời thỏa cả hai ràng buộc \(x_1 >=0\) và \(x_1 <= -3\).
• Bài toán có nghiệm vô cực: Ví dụ bài toán sau là vô nghiệm \[\begin{aligned}
  \rm{min.}~ & -x_1+2x_2 \\
  \rm{s.t.}~ & x_1 \leq 3,\\
  & x_2 \geq 7,\\
  & -x_1+2x_2 \leq -5.
  \end{aligned}\]

Bài toán LP đối ngẫu

Bài toán đối ngẫu là một chủ đề rất quan trọng trong tối ưu. Nhiều lúc thay vì giải bài toán gốc, xem xét bài toán đối ngẫu giúp ta hiểu được bản chất đằng sau của hàm mục tiêu và các ràng buộc. Ví dụ trong phương pháp dual decomposition, thay vì giải bài toán gốc là bài toán lớn, không thể giải được thì phương pháp này phân rã bài toán đối ngẫu ra thành nhiều bài toán con với kích thước nhỏ hơn và giải song song đồng thời. Trong phần này, bài toán đối ngẫu của LP được giới thiệu sơ lược để giúp bạn đọc có một cái nhìn trực quan. Lý thuyết đối ngẫu sẽ được giới thiệu kỹ sau này trong phần tối ưu lồi.

Xét bài toán LP sau \[\begin{aligned}
\rm{min.}~ & f(x_1, x_2) = x_1 + x_2 \qquad \qquad \qquad \qquad  (4)\label{eq-ex13-obj}\\
\rm{s.t.}~ & x_1 – 2x_2 \geq -1,\label{eq-ex13-c1}\\
& – 2x_1 + x_2 \geq 1,\label{eq-ex13-c2}\\
& x_1 + 4x_2 \geq 6 \label{eq-ex13-c3}\\
& x_1 \geq 0, x_2 \geq 0. \end{aligned}\] Bây giờ ta tìm hiểu chặn trên và chặn dưới của nghiệm bài toán. Đối với bài toán tìm cực tiểu, chặn trên là bất cứ điểm nào thuộc miền khả thi. Gọi \(x_1, x_2\) là một điểm thỏa mãn các ràng buộc, ta luôn có \(f(x_1, x_2) \leq f(x_1^*, x_2^*)\).

Bây giờ để tìm chặn dưới của nghiệm, ta nhân hai vế của ba điều kiện đầu tiên của bài toán (4) với ba số không âm tương ứng là \(\lambda_1\), \(\lambda_2\), và \(\lambda_3\), ta được các ràng buộc mới tương đương. \[\begin{aligned}
\lambda_1 x_1 – 2\lambda_1 x_2 &\geq -\lambda_1,\\
– 2\lambda_2 x_1 + \lambda_2 x_2 &\geq \lambda_2,\\
\lambda_3 x_1 + 4\lambda_3 x_2 &\geq 6\lambda_3.\\\end{aligned}\]

Cộng ba ràng buộc mới với nhau vế theo vế, ta được \[\begin{aligned}
(\lambda_1 -2 \lambda_2 + \lambda_3)x_1 + (- 2 \lambda_1 + \lambda_2 + \lambda_3)x_2 \geq -\lambda_1 + \lambda_2 + 6\lambda_3.\end{aligned}\] Nếu tồn tại \(\lambda_1, \lambda_2 \geq 0\) sao cho \[\begin{aligned}
\lambda_1 -2 \lambda_2 + \lambda_3 &\leq 1 \\
– 2 \lambda_1 + \lambda_2 + \lambda_3 &\leq 1.\end{aligned}\] thì ta có \[\begin{aligned}
-\lambda_1 + \lambda_2 + 6\lambda_3 & \geq (\lambda_1 -2 \lambda_2 + \lambda_3)x_1 + (- 2 \lambda_1 + \lambda_2 + \lambda_3)x_2 \\
& \geq x_1+ x_2 = f.\end{aligned}\] Như vậy, \(-\lambda_1 + \lambda_2 + 6\lambda_3\) là một chặn dưới của bài toán.

Một câu hỏi được đặt ra là với những giá trị \(\lambda_1, \lambda_2, \lambda_3\) nào thì ta có chặn dưới là tốt nhất. Đó chính là bài toán đối ngẫu của bài toán (4): \[\begin{aligned}
\rm{min.}~ & -\lambda_1 + \lambda_2 + 6\lambda_3 \qquad \qquad \qquad \qquad  (5)\\
\rm{s.t.}~ & \lambda_1 -2 \lambda_2 + \lambda_3 \geq 1 \\
& – 2 \lambda_1 + \lambda_2 + \lambda_3 \geq 1,\\
& \lambda_1, \lambda_2, \lambda_3 \geq 0. \end{aligned}\]

Đối với bài toán LP tổng quát \[\begin{aligned}
\rm{min.}~ & c^Tx = c_1 x_1 + \ldots + c_2 x_2 \\
\rm{s.t.}~ & a_{j1}x_1+ \ldots + a_{jn}x_n \geq b_j, j=1,\ldots, m \\
& x_1, \ldots, x_n \geq 0.\end{aligned}\] thì bài toán đối ngẫu sẽ có dạng \[\begin{aligned}
\rm{max.}~ & b^T \lambda = b_1 \lambda_1 + \ldots + b_m \lambda_m \\
\rm{s.t.}~ & a_{1j}\lambda_1+ \ldots + a_{nj}\lambda_n \leq c_j, j=1,\ldots, m\\
& \lambda_1, \ldots, \lambda_m \geq 0.\end{aligned}\]

Một tính chất đối ngẫu quan trọng là nghiệm của bài toán LP đối ngẫu cũng là nghiệm của bài toán LP gốc. Do đó, thay vì giải bài toán gốc, ta có thể giải bài toán đối ngẫu. Lý thuyết đối ngẫu cho một bài toán tối ưu dạng tổng quát trong các phần sau.

Ghi chú

Thuật ngữ tuyến tính được dịch từ chữ linear hoặc affine trong tiếng Anh. Thực ra có sự khác nhau nhỏ giữa linear và affine. Một hàm \(f(x) = a^Tx+b\) được gọi là affine, trong khi hàm \(f(x) = a^Tx\) được gọi linear. Một hàm linear là affine, nhưng ngược lại thì không đúng. Sách này đề cập hàm tuyến tính tức là hàm affine.

Có nhiều nguồn tài liệu cho phép người học làm quen với ngôn ngữ Python, ví dụ . Các bài tập trong chương này được tham khảo từ các sách

Xem thêm: my đọc tiếng anh là gì

Boyd, Stephen, Stephen P. Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.

Vanderbei, Robert J. Linear programming: foundations and extensions. Vol. 285. Springer Nature, 2020.

Wentworth, Peter, Jeffrey Elkner, Allen B. Downey, and Chris Meyer. How to think like a computer scientist: Learning with Python 3. (2015).