7.1. Bài toán dạng tổng quát¶

Bài toán tối ưu dạng tổng quát:

\[\begin{split} \begin{eqnarray} \mathbf{x}^* &=& \arg\min_{\mathbf{x}} f_0(\mathbf{x}) \\ \text{subject to:}~ && f_i(\mathbf{x}) \leq 0, ~~ i = 1, 2, \dots, m\\ && h_j(\mathbf{x}) = 0, ~~ j = 1, 2, \dots, p \tag{1} \end{eqnarray} \end{split}\]

Phát biểu bằng lời: Tìm giá trị của \(\mathbf{x}\) để tối thiểu hàm mục tiêu \(f_0(\mathbf{x})\) thoả mãn hệ điều kiện ràng buộc đẳng thức và bất đẳng thức.

Các định nghĩa:

\(\mathbf{x} \in \mathbb{R}^{n}\) là biến tối ưu (optimization variable)
\(f_0(\mathbf{x})\) là hàm mục tiêu (objective/cost/lost function)
\(f_i(\mathbf{x}) : \mathbb{R}^{n} \mapsto \mathbb{R}\) ràng buộc dạng bất đẳng thức (inequality constraint function). Trong đó \(i = 1, 2, \dots, m\).
\(h_j(\mathbf{x})=0: \mathbb{R}^n \mapsto \mathbb{R}\) ràng buộc dạng đẳng thức (equality constraint function). Trong đó \(j = 1, 2, \dots, p\).
Tập hợp tất cả các điểm mà các hàm mục tiêu và \(\mathcal{D} = \bigcap_{i=0}^m \text{dom}f_i \cap \bigcap_{pj=1}^p \text{dom}h_i\): tập xác định (domain).

Một điểm \(\mathbf{x} \in \mathcal{D}\) là feasible nếu như nó thoả mãn các ràng buộc \(f_i(\mathbf{x}) \geq 0\), \(i = 1, \dots, m\) và \(h_{i}(\mathbf{x}) = 0\), \(j = 1, 2, \dots, p\). Bài toán tối ưu \((1)\) được gọi là feasible nếu như tồn tại ít nhất một điểm feasible point. Trong trường hợp không tồn tại bất kì một điểm feasible nào thì ta nói rằng bài toán là infeasible. Tập hợp tất cả các điểm feasible points được gọi là feasible set hoặc constraint set.

Nghiệm tối ưu (optimal value) \(p^*\) của bài toán còn được định nghĩa theo infimum là:

\[p^* = \inf \{ f_0(\mathbf{x}) | f_{i}(\mathbf{x}) \leq 0, ~ i = 1, \dots, m, h_i(\mathbf{x}) = 0, i = 1, \dots, p \}\]

7.2. Các bài toán tối ưu thực tiễn.¶

7.2.1. Bài toán vận chuyển¶

Tối ưu kho vận là bài toán có tính ứng dụng rất cao trong lớp các bài toán tối ưu. Vấn đề mà bài toán giải quyết liên là vấn đề mà nhiều doanh nghiệp đang gặp phải. Bài toán này sẽ giúp cho các doanh nghiệp tiết kiệm được chi phí vận chuyển hàng hoá nhờ phân bổ nguồn lực ở các kho một cách hợp lý đến các cửa hàng. Không chỉ giúp tối ưu về chi phí, bài toán vận chuyển còn có thể chuyển sang mục tiêu khác đó là tối ưu thời gian vận chuyển. Hãy cùng tìm hiểu bài toán này qua ví dụ bên dưới.

Bài toán¶

Một công ty sản xuất sữa cần giao sản phẩm tới các các cửa hàng tại Hà Nội (1800 thùng) và TP. HCM (2000 thùng). Công ty có sẵn trong kho tại Thái Bình (1000 thùng) và Khánh Hoà (3000) thùng. Chi phí vận chuyển từ kho tới của hàng được cho như bảng bên dưới:

Hỏi công ty cần phân bổ hàng tại kho như thế nào để chi phí giao hàng là thấp nhất.

Lời giải:

Giả định số lượng giao hàng là các biến được thể hiện trong ma trận:

\[\begin{split}\begin{bmatrix} x_{11} & x_{12} \\ x_{21} & x_{22} \end{bmatrix}\end{split}\]

Bài toán tối ưu với hàm mục tiêu là chi phí giao hàng tối thiểu:

\[\mathbf{x}^{*} = \arg \min_{\mathbf{x}} f(\mathbf{x}) = \arg \min_{\mathbf{x}}50 x_{11} + 120 x_{12} + 150 x_{21} + 40 x_{22}\]

Ràng buộc về số lượng:

Tại Hà Nội: \(x_{11}+x_{21} = 1800\)

Tại TP.HCM: \(x_{12} + x_{22} = 2000\)

Ràng buộc số lượng hàng tại kho:

Tại Thái Bình: \(x_{11}+x_{12} \leq 1000\)

Tại Khánh Hoà: \(x_{21} + x_{22} \leq 3000\)

Ràng buộc về số lượng dương: \(x_{11}, x_{12}, x_{21}, x_{22} \geq 0\). Trên thực tế chúng ta cần các giá trị \(x_{ij}\) phải là số nguyên không âm nhưng sẽ khiến cho bài toán khó giải. Để đơn giản hoá chúng ta chuyển sang \(x_{ij} \geq 0\).

Phát biểu bài toán:

Bài toán trên có thể viết như sau:

\[\begin{split} \begin{eqnarray} \mathbf{x}^* &=& \arg\min_{\mathbf{x}} f(\mathbf{x}) = \arg \min_{\mathbf{x}}50 x_{11} + 120 x_{12} + 150 x_{21} + 40 x_{22}\\ \text{subject to:}~ && x_{11} + x_{12} \leq 1000\\ && x_{21} + x_{22} \leq 3000\\ && x_{11} + x_{21} = 1800\\ && x_{12} + x_{22} = 2000\\ && x_{11}, x_{12}, x_{21}, x_{22} \geq 0 \end{eqnarray} \end{split}\]

Lưu ý: Bài toán có cả hàm mục tiêu và điều kiện ràng buộc là những hàm tuyến tính thì được gọi là bài toán qui hoạch tuyến tính (Linear Program - LP). Phát biểu và lời giải của bài toán này sẽ được trình bày ở phần tiếp theo.

Bài toán qui hoạch tuyến tính (Linear Programming LP)¶

Dạng tổng quát của bài toán vận chuyển là bài toán qui hoạch tuyến tính có dạng như sau:

\[\begin{split}\begin{eqnarray} \mathbf{x}^* &=& \arg\min_{\mathbf{x}} \mathbf{c}^{\intercal}\mathbf{x} + d \\ \text{subject to:}~ && \mathbf{Gx} \preceq \mathbf{h} \\ && \mathbf{Ax} = \mathbf{b} \end{eqnarray} \end{split}\]

Ta nhận thấy hàm mục tiêu của bài toán qui hoạch tuyến tính là một hàm có dạng tuyến tính. Ở điều kiện ràng buộc thì \(\mathbf{G} \in \mathbb{R}^{m \times n}, \mathbf{A} \in \mathbb{R}^{p \times n}, \mathbf{h} \in \mathbb{R}^{m}, \mathbf{b} \in \mathbb{R}^{p}\). Dòng thứ \(i\) của ma trận \(\mathbf{G}\) là \(\mathbf{g}_i\) được xem như hệ số của điều kiện ràng buộc dạng bất đẳng thức \(g_i(\mathbf{x}) = \mathbf{g}_{i}\mathbf{x} \leq h_i\). \(h_i\) là giá trị phần tử thứ \(i\) của véc tơ \(\mathbf{h}\). Tương tự dòng thứ \(i\) của ma trận \(\mathbf{A}\) cũng là hệ số của hệ điều kiện ràng buộc dạng đẳng thức. Một điều kiện đẳng thức cũng có thể được chuyển hoá sang điều kiện bất đẳng thức nếu như chúng ta thay chúng bằng hai điều kiện: \(\mathbf{a}_i \mathbf{x} \leq b_i\) và \(\mathbf{a}_i \mathbf{x} \geq b_i\). Do đó một số tài liệu người ta chỉ có điều kiện bất đẳng thức.

Một số bài toán thực tế sẽ xuất hiện thêm điều kiện \(x_{ij} \geq 0\). Khi đó chúng ta có thể đổi dấu của \(x_{ij}\) để chuyển về điều kiện \(-x_{ij} \leq 0\).

Đối với hàm mục tiêu thì véc tơ \(\mathbf{c}\) được xem như véc tơ trọng số của biến mục tiêu \(\mathbf{x}\). \(d\) là một đại lượng vô hướng và không ảnh hưởng tới nghiệm.

Lời giải của bài toán qui hoạch tuyến tính (LP) có thể được giải qua cxopt như sau:

Note

solver.lp(c, G, h, A, b)

Quay trở lại bài toán vận chuyển:

\[\mathbf{c} = [50, 150, 120, 40]^{\intercal}\]

\[\mathbf{x} = [x_{11}, x_{12}, x_{21}, x_{22}]^{\intercal}\]

\[\begin{split}\mathbf{G} = \begin{bmatrix} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1\\ -1 & 0 & 0 & 0 \\ 0 & -1 & 0 & 0 \\ 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & -1 \\ \end{bmatrix} \end{split}\]

\[\begin{split}\mathbf{A} = \begin{bmatrix} 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 \end{bmatrix}\end{split}\]

\[\mathbf{h} = [1000, 3000, 0, 0, 0, 0]^{\intercal}\]

\[\mathbf{b} = [1800, 2000]^{\intercal}\]

Note

Lưu ý ở code bên dưới khi sử dụng ma trận được khởi tạo từ hàm cvxopt.matrix thì chúng ta khai báo một list bao gồm các list bên trong mà mỗi một list bên trong là 1 véc tơ cột. Xem thêm tại create matrices - cvopt. Như vậy các ma trận và véc tơ được tạo thành từ cvxopt.matrix phải là transpose của numpy.

import pprint
from cvxopt import matrix, solvers
c = matrix([50., 150., 120., 40.])

# moi dong cua matrix la 1 list va list nay phai la 1 vec to cot 
G = matrix([[1., 0., -1., 0., 0., 0.],
            [1., 0., 0., -1., 0., 0.],
            [0., 1., 0., 0., -1., 0.],
            [0., 1., 0., 0., 0., -1.]])

h = matrix([1000., 3000., 0., 0., 0., 0.])

A = matrix([[1., 0.],
            [0., 1.],
            [1., 0.],
            [0., 1.]])

b = matrix([1800., 2000.])

solvers.options['show_progress'] = True
sol = solvers.lp(c, G, h, A, b)

print('Solution"')
print(sol['x'])

---------------------------------------------------------------------------
ModuleNotFoundError                       Traceback (most recent call last)
/tmp/ipykernel_42718/1023612750.py in <module>
      1 import pprint
----> 2 from cvxopt import matrix, solvers
      3 c = matrix([50., 150., 120., 40.])
      4 
      5 # moi dong cua matrix la 1 list va list nay phai la 1 vec to cot

ModuleNotFoundError: No module named 'cvxopt'

Lưu ý: ở trên chúng ta sử dụng hàm matrix của cvxopt để khởi tạo ma trận. Bên trong chúng ta khai báo một list bao gồm các list con mà mỗi một list con sẽ đại diện cho một véc tơ cột của ma trận (khác với numpy là mỗi một list là một véc tơ dòng).

Như vậy lời giải của bài toán là giao 1000 cuốn từ Thái Bình đi Hà Nội, giao 2000 cuốn từ Khánh Hoà đi Hồ Chí Minh và 800 cuốn từ Khánh Hoà đi Hà Nội. Ta có thể dễ dàng suy luận ra điều này trên thực tế.

7.2.2. Bài toán chi phí sản xuất¶

Bài toán chi phí sản xuất là một bài toán có tính ứng dụng cao thường được ứng dụng vào quá trình sản xuất của các nhà máy. Bài toán này giúp cho nhà quản lý có thể tối đa hoá nguồn lực đầu vào để mang lại lợi nhuận là lớn nhất cho doanh nghiệp. Sau khi đọc xong mục này, bạn cũng có thể ứng dụng được bài toán chi phí sản xuất vào quản lý công xưởng và doanh nghiệp của mình.

Bài toán¶

Một nhà máy sản xuất ra 4 loại sản phẩm là:

Đũa tre (5 triệu/tấn)
Tăm tre (6 triệu/tấn)
Chân hương (4.5 triệu/tấn)
Xiên thịt (5.5 triệu/tấn)

Biết rằng để sản xuất được 1 tấn của lần lượt các loại sản phẩm trên thì nhà máy cần tiêu tốn nguyên liệu và nhân công như sau:

Nguyên liệu và chi phí nguyên liệu:

Số giờ làm việc của nhân công:

Lợi nhuận bán ra của từng loại:

Kế hoạch trong tháng tới nhà máy có 1000 giờ làm việc và tối đa 5 tấn tre, 0.2 tấn hương liệu và 10 tấn than sấy. Hỏi nhà máy cần lập kết hoạch sản xuất như thế nào để tối đa lợi nhuận.

Lời giải¶

Giả định sản lượng sản xuất của mỗi loại lần lượt là \(x_1, x_2, x_3, x_4\). Bài toán tối ưu lợi nhuận:

\[\mathbf{x} = \arg \max_{\mathbf{x}} f(\mathbf{x}) = 18 x_1 + 30 x_2 + 22 x_3 + 25 x_4\]

Tương đương với bài toán:

\[\mathbf{x} = \arg \min_{\mathbf{x}} f(\mathbf{x}) = -18 x_1 -30 x_2 -22 x_3 -25 x_4\]

Ràng buộc về nguyên liệu:

Đối với Tre: \(1.1 x_1 + 1.5 x_2 + 1.4 x_3 + 1.2 x_2 \leq 5\)

Đối với Hương liệu: \(0.03 x_1 + 0.06 x_2 + 0.04 x_3 + 0.04 x_4 \leq 0.2\)

Đối với than sấy: \(x_1 + 2 x_2 + 2.2 x_3 + 2.1 x_4 \leq 10\)

Ràng buộc về số giờ làm việc:

\(200 x_1 + 300 x_2 + 220 x_3+ 240 x_4 \leq 1000\)

Ràng buộc về số lượng \(x_1 , x_2, x_3, x_4 \geq 0\)

Như vậy:

\[\mathbf{c} = [-18, -30, -22, -25]^{\intercal}\]

\[\begin{split}\mathbf{G} = \begin{bmatrix} 1.1 & 1.5 & 1.4 & 1.2 \\ 0.03 & 0.06 & 0.04 & 0.04 \\ 1 & 2 & 2.2 & 2.1 \\ -1 & 0 & 0 & 0 \\ 0 & -1 & 0 & 0 \\ 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & -1 \\ \end{bmatrix}\end{split}\]

\[\mathbf{h} = [5, 0.2, 10, 0, 0, 0, 0]^{\intercal}\]

import pprint
from cvxopt import matrix, solvers
c = matrix([-18., -30., -22., -25.])

# We have to transpose G
G = matrix([[1.1, 0.03, 1., -1., 0., 0., 0.],
            [1.5, 0.06, 2., 0., -1., 0., 0.],
            [1.4, 0.04, 2.2, 0., 0., -1., 0.],
            [1.2, 0.04, 2.1, 0., 0., 0., -1.]])

h = matrix([5., 0.2, 10., 0., 0., 0., 0.])

solvers.options['show_progress'] = True
sol = solvers.lp(c, G, h)

print('Solution"')
print(sol['x'])

Như vậy để tối đa hoá lợi nhuận chúng ta cần tập trung vào sản xuất toàn bộ là xiên thịt với số lượng tối đa là \(4.17\) tấn.

7.2.3. Bài toán đóng thùng¶

Bài toán¶

Một người cần chở 100 \(m^3\) hàng hoá về kho. Mỗi một lượt vận chuyển tốn 100 USD cả chiều đi lẫn về. Để vận chuyển thì người đó đóng một chiếc thùng chở hàng với chi phí để đóng là 20 USD/\(m^2\). Hỏi người đó cần đóng thùng hàng với kích thước các cạnh như thế nào để tối ưu hoá chi phí vận chuyển. Trên thực tế có thể có thêm ràng buộc về chiều dài, rộng, cao của thùng chở hàng nhưng ở đây chúng ta để đơn giản chúng ta giả định rằng thùng chở hàng có thể có kích thước tuỳ ý.

Lời giải¶

Chúng ta giả định kích thước dài, rộng, cao của thùng hàng lần lượt là \(x, y, z\) m. Như vậy thể tích của thùng hàng là \(xyz\). Chúng ta có hai loại chi phí phải chi trả:

Chi phí chuyên chở: Số lượt cần chuyên chở là \(\frac{100}{xyz}\). Như vậy chi phí tổng cộng sẽ là: \(\frac{100}{xyz}\times 100 = \frac{10000}{xyz}\).
Chi phí đóng thùng: \(20(xy + yz+ zx)\).

Tổng chi phí người đó phải trả:

\[\frac{10000}{xyz} + 20(xy + yz + zx)\]

Áp dụng BĐT cauchuy ta dễ dàng suy ra chi phí tốt thiểu mà người đó cần chuyên chở là:

\[\begin{split}\begin{eqnarray}\frac{10000}{xyz} + 20(xy + yz + zx) & = & 20 (\frac{250}{xyz} + \frac{250}{xyz} + xy + yz + zx) \\ & \geq & 20 (5 (\frac{250}{xyz}.\frac{250}{xyz} xy.yz.zx)^{\frac{1}{5}}) \\ & = & 100.250^{2/5}& \end{eqnarray}\end{split}\]

Đẳng thức xảy ra khi \(x = y = z = 250^{1/5}\).

Lời giải trên là khá đơn giản và thực tế dường như việc giải bài toán đó là không dễ dàng. Sẽ như thế nào nếu chúng ta đưa thêm các điều kiện ràng buộc về các chiều \(x, y, z\) của thùng container? Liệu có tồn tại lời giải dạng tổng quát cho bài toán trên không? Chúng ta cùng tìm hiểu bài toán dạng tổng quát của bài toán trên là Geometric Programming.

7.3. Bài toán Geometric Programming GP¶

Trong phần này, chúng ta mô tả một nhóm các bài toán tối ưu hóa không lồi ở dạng tự nhiên của chúng. Tuy nhiên, những bài toán này có thể được chuyển đổi thành bài toán tối ưu lồi, bằng cách thay đổi các biến số và chuyển đổi mục tiêu và các chức năng ràng buộc.

7.3.1. Đơn thức (monomials) và đa thức (posynomials)¶

Một hàm \(f: \mathbb{R}^n \mapsto \mathbb{R}\) với miền xác định \(\text{dom} g = \mathbb{R}^{n}_{++}\) được định nghĩa là:

\[f(x) = c x_1^{a_1}x_2^{a_2}\dots x_n^{a_n}\]

với \(c > 0\) và \(a_i \in \mathbb{R}\) được gọi là hàm đơn thức (monomial funciton). Số mũ \(a_i\) của đơn thức có thể là bất kì giá trị thực nào, bao gồm cả phân số và số âm, nhưng hệ số \(c\) chỉ có thể dương (khái niệm monomial ở đây có thể khác biệt so với định nghĩa trong đại số , khi mà số mũ bắt buộc phải là một số nguyên không âm). Tổng của các đơn thức là một hàm có dạng như bên dưới:

\[f(x) = \sum_{i=1}^K c_k x_1^{a_{1k}}x_2^{a_{2k}}\dots x_n^{a_{nk}}\]

ở đây \(k > 0\), được gọi là (đa thức) posynomial function với \(K\) phần tử.

7.3.2. Bài toán tối ưu dạng đa thức¶

Một bài toán tối ưu có dạng:

\[\begin{split}\begin{eqnarray} \mathbf{x} &=& \arg\min_{\mathbf{x}} f_0(\mathbf{x}) \\ \text{subject to:}~ && f_i(x) \leq 1, ~~ i = 1, 2, \dots, m \\ && h_j(x) = 1, ~~ j = 1, 2, \dots, p \end{eqnarray} \end{split}\]

Trong đó \(f_0, f_1, \dots, f_m\) là các đa thức và \(h_1, h_2, \dots, h_p\) là các đơn thức được gọi là bài toán Geometric Programming (GP). Điều kiện \(\mathbf{x} \succeq 0\) được ẩn đi.

Ví dụ:

\[\begin{split} \begin{eqnarray} (x, y, z) &=& \arg\min_{x, y, z} xz/y \\ \text{subject to:}~ && 1 \leq x \leq 3 \\ && x^2 + 3y/z \leq \sqrt{y} \\ && z/y^2 = x \end{eqnarray} \end{split}\]

Có thể được viết thành dưới dạng GP

\[\begin{split}\begin{eqnarray} (x, y, z) &=& \arg\min_{x, y, z} xy ^{-1}z \\ \text{subject to:}~ && x^{-1} \leq 1 \\ && (1/3)x \leq 1 \\ && x^2y^{-1/2} + 3y^{1/2}z^{-1} \leq 1 \\ && x^{-1}y^{-2}z = 1 \end{eqnarray}\end{split}\]

Bài toán này là non-convex vì hàm mục tiêu và các điều kiện ràng buộc đều không lồi

7.3.3. Biến đổi GP về đạng convex¶

Nếu giữ nguyên các đơn thức thì rõ ràng điều kiện ràng buộc là không lồi. Nhưng nếu chúng ta đặt \(y_k = log(x_k)\)? Khi đó \(f_k(\mathbf{x})\) trở thành:

\[\begin{split}\begin{eqnarray}f_k(\mathbf{x}) & = & \exp(\log c)\exp(a_{1k}\log(x_1)) \dots \exp(a_{nk} \log x_n)\\ & = & \exp(\mathbf{a}^{\intercal}\mathbf{y} + b) \end{eqnarray}\end{split}\]

Ở đây \(b = \log c\). Lúc này ta thu được hàm \(l(\mathbf{y}) = \exp(\mathbf{a}^{\intercal}\mathbf{y} + b)\) là một hàm lồi theo \(\mathbf{y}\). Thật vậy:

\[\frac{\partial^{2}l(\mathbf{y})}{\partial^{2} y_i} = a_{ik}^2\exp(\mathbf{a}^{\intercal}\mathbf{y}+b) > 0\]

Hàm \(\mathbf{a}^{\intercal}\mathbf{y} + \mathbf{b}\) còn được gọi là hàm affine, đây đồng thời cũng là một hàm lồi.

Như vậy hàm mục tiêu của bài toán tối ưu GP có thể được viết lại thành:

\[f_k(\mathbf{x}) = g(\mathbf{y}) = \sum_{k = 1}^K \exp(\mathbf{a}_k^{\intercal}\mathbf{y} + b_k)\]

Trong đó \(\mathbf{a}_k = [a_{1k}, a_{2k}, \dots, a_{nk}]^{\intercal}\) chính là các véc tơ số mũ của đơn thức và \(b_k = \log c_k\).

Như vậy lúc này hàm mục tiêu đã được biến đổi thành tổng của \(\exp\) của các hàm affine. Do các hàm thành phần đều lồi nên tổng này là một hàm lồi.

Bài toán GP được viết lại thành:

\[\begin{split} \begin{eqnarray} \mathbf{y} &=& \arg\min_{\mathbf{y}} \sum_{k=1}^{K} \exp(\mathbf{a}_{0k}^{\intercal}\mathbf{y} + b_{k}) \\ \text{subject to:}~ && \sum_{k=1}^{K_i} \exp(\mathbf{a}_{ik}^{\intercal}\mathbf{y} + b_{ik}) \leq 1, ~~, i = 1, \dots, m \\ && \exp(\mathbf{g}_j^{\intercal}\mathbf{y} + h_j) = 1, ~ j= 1, \dots, p \end{eqnarray} \end{split}\]

Tron đó \(\mathbf{a}_{ik} \in \mathbb{R}^{n}, ~ \forall i = \overline{1, m}\) và \(\mathbf{g}_j \in \mathbb{R}^{n}\).

Đây là có các hàm mục tiêu là lồi và các điều kiện ràng buộc cũng là lồi. Chúng ta có thể chuyển chúng sang bài toán dạng lồi bằng cách lấy logarith như sau:

GP convex form:

\[\begin{split}\begin{eqnarray} \text{minimize}_{\mathbf{y}} \tilde f(\mathbf{y}) & = & \log[\sum_{i=1}^{K} \exp(\mathbf{a}_{0k}^{\intercal} \mathbf{y} + b_{0k})]\\ \text{subject to:}~ && \log \sum_{k=1}^{K_i} \exp(\mathbf{a}_{ik}^{\intercal}\mathbf{y} + b_{ik}) \leq 0, ~~, i = 1, \dots, m \\ && \tilde {h}(\mathbf{y}) = \mathbf{g}_j^{\intercal}\mathbf{y} + h_j = 0, ~ j= 1, \dots, p \end{eqnarray}\end{split}\]

7.3.4. Giải bài toán đóng thùng bằng CVXOPT¶

Quay trở lại bài toán đóng thùng, đây là một bài toán có hàm mục tiêu dạng đa thức:

\[\begin{split}\begin{eqnarray}f(x, y, z) & = & \frac{10000}{xyz} + 20(xy + yz + zx) \\ & = & 10000 x^{-1}y^{-1}z^{-1} + 20xyz^{0} + 20 x^{0}yz + 20 xy^{0}z \\ \rightarrow \tilde f(x, y, z) & = & \log [ \exp(\log10000 - \log{x} - \log{y} - \log{z}) \\ & + & \exp(\log 20 + \log x + \log y) \\ & + & \exp(\log 20 + \log{y} + \log{z}) \\ & + & \exp(\log{20} + \log{x} + \log{z})] \end{eqnarray}\end{split}\]

và đồng thời bài toán này không có điều kiện ràng buộc. Chúng ta có thể tìm kiếm optimal point bằng package CVXOPT theo hướng dẫn:

Trong đó \(F\) là ma trận hệ số của \(\log{x}, \log{y}, \log{z}\). Ta sẽ có:

\[\begin{split}F = \begin{bmatrix} -1 & -1 & -1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{bmatrix}\end{split}\]

và

\[\mathbf{g} = [\log 10000, \log 20, \log 20, \log 20]^{\intercal}\]

Thế vào hàm solvers.gp() bên dưới ta được:

from cvxopt import matrix, solvers
from math import log, exp# gp
from numpy import array
import numpy as np

K = [4]
F = matrix([[-1., 1., 1., 0.],
            [-1., 1., 0., 1.],
            [-1., 0., 1., 1.]])

g = matrix([log(10000.), log(20.), log(20.), log(20.)])
solvers.options['show_progress'] = True
sol = solvers.gp(K, F, g)

print('Solution:')
print(np.exp(np.array(sol['x'])))

print('\nchecking sol^5')
print(np.exp(np.array(sol['x']))**5)

Ta nhận thấy nghiệm của bài toán thu được là \(x = y = z = (250)^{1/5}\)

7.4. Bài toán Quadratic Programming (QP)¶

Quadratic Programming là một bài toán tối ưu mà bạn sẽ bắt gặp khá nhiều trong machine learning. Chẳng hạn như bài toán tối ưu trong mô hình SVM có thể chuyển về dạng Quadratic Programming hoặc bài toán hồi qui tuyến tính. Để hình dung trực quan về bài toán Quadratic Programming chúng ta cùng lấy một ví dụ về bài toán tìm bờ gần nhất.

Bài toán tìm bờ: Một con thuyền đang đậu tại 1 điểm \(\mathbf{x}\) ở ngoài khơi của một hòn đảo mà có các cạnh dạng đa giác lồi (polygon). Tìm toạ độ của điểm gần nhất trên hòn đảo để tàu cập bến.

7.4.1. Dạng Quadratic Programming - QP¶

Bài toán \((1)\) được gọi là quadratic program (QP) nếu như hàm mục tiêu là (convex) quadratic và các hàm ràng buộc là những hàm affine. Một bài toán QP có thể được biểu diễn dưới dạng:

\[\begin{split}\begin{eqnarray} && \text{minimize}_{\mathbf{x}} ~~ \frac{1}{2} \mathbf{x}^{\intercal}\mathbf{P}\mathbf{x} + \mathbf{q}^{\intercal}\mathbf{x} + r \\ && \text{subject to:}~ \mathbf{G}\mathbf{x} \preceq \mathbf{h}\\ && ~~~~~~~~~~~~~~~~~~~\mathbf{A}\mathbf{x} = \mathbf{b} \end{eqnarray}\end{split}\]

Ở đây \(\mathbf{P} \in \mathbf{S}^{n}_{+}\) là một ma trận bán xác định dương, \(\mathbf{G} \in \mathbb{R}^{m \times n}\), \(\mathbf{A} \in \mathbb{R}^{p \times n}\), \(\mathbf{h} \in \mathbb{R}^{m}\), \(\mathbf{b} \in \mathbb{R}^{p}\). Trong bài toán QP, chúng ta tối thiểu hoá một convex quadratic function trên một đa diện lồi polyhedron.

Hình 1: Hình ảnh mô phỏng QP. Tập feasible set là \(\mathcal{P}\), đây là một hình đa diện lồi được đổ bóng. Các đường đồng mức (contour lines) là tập hợp những giá trị của \(x\) trả về cùng một giá trị hàm mục tiêu, chúng là một hàm lồi convex quadratic được thể hiện bằng đường nét đứt. Điểm tối ưu \(x^*\) là điểm tiếp xúc giữa đường đồng mức có giá trị nhỏ nhất với tập feasible set \(\mathcal{P}\).

7.4.2.Giải bài toán QP trên CVXOPT¶

Hình 2: Đồ thị minh hoạ cho bài toán tìm điểm cập bến gần nhất.

Quay trở lại bài toán tìm điểm cập bến, để cụ thể hoá chúng ta giả định rằng vị trí của tàu có toạ độ là \((6, 3)\) hòn đảo chính là tập feasible set \(\mathcal{P}\) được gạch chéo. Khi đó mục tiêu của chúng ta là tìm điểm \((x, y) \in \mathcal{P}\) sao cho khoảng cách từ điểm đó tới tàu là nhỏ nhất. Tức là tương đương với bài toán tối ưu:

\[\begin{split}\begin{eqnarray} & \text{minimize}_{x, y} & ~~ (x - 6)^2 + (y-3)^2 \\ \text{subject to:} & 2x + y & \leq 8 \\ & x + 4y & \leq 16 \\ & x + y & \leq 5 \\ & x, y & \geq 0 \end{eqnarray}\end{split}\]

Hàm mục tiêu của bài toán trên tương đương với:

\[f(x, y) = x^2 + y^2 - 12x - 6 y + 45\]

Như vậy:

\[\begin{split}\mathbf{P} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\end{split}\]

\[\mathbf{q} = [-12, -6]^{\intercal}\]

\(r = 45\)

\[\begin{split}\mathbf{G} = \begin{bmatrix} 2 & 1 \\ 1 & 4 \\ 1 & 1 \\ -1 & 0 \\ 0 & -1 \end{bmatrix}\end{split}\]

\[\mathbf{h} = [8, 16, 5, 0, 0]^{\intercal}\]

Chúng ta giải bài toán QP trên CVXOPT như sau:

from cvxopt import matrix, solvers
P = matrix([[1., 0.], 
            [0., 1.]])
q = matrix([-12., -16.])
G = matrix([[2., 1., 1., -1., 0.], [1., 4., 1., 0., -1.]])
h = matrix([8., 16., 5., 0., 0])

solvers.options['show_progress'] = False
sol = solvers.qp(P, q, G, h)

print('Solution:')
print(sol['x'])

7.5. Tổng kết¶

Như vậy ở chương này chúng ta đã tìm hiểu về 3 dạng bài toán phổ biến trong tối ưu đó là bài toán: Linear Programming, Geometric Programming và Quadratic Programming kèm theo cách giải chúng trên package CVXOPT. Những lớp bài toán này không chỉ tồn tại trên lý thuyết mà trên thực tế chúng còn được áp dụng giải quyết các vấn đề trong tối ưu vận chuyển, tối ưu chi phí sản xuất. Khi nắm được những công cụ này, bạn có thể áp dụng chúng một cách hiệu quả vào các vấn đề của doanh nghiệp.

7.6. Bài tập¶

Một doanh nghiệp sản xuất trứng gà có 2 kho hàng tại Cần Thơ (2 triệu quả) và Hà Nội (3 triệu quả). Doanh nghiệp cần giao trứng gà của mình đến các cửa hàng tại các tỉnh Khánh Hoà (0.5 triệu quả), Bình Dương (1.2 triệu quả) và Thanh Hoá (3.2 triệu quả) với chi phí vận chuyển (VNĐ/triệu quả) được cho ở bảng sau: Hỏi doanh nghiệp này cần giao hàng như thế nào để chi phí là thấp nhất mà vẫn đảm bảo giao đủ hàng.
Cần giao hàng với số lượng yêu cầu tương tự như bài toán trên nhưng mục tiêu là tối ưu chi phí thời gian. Biết mỗi container chỉ chở được 0.1 triệu quả/ chuyến và thời gian của các chuyến hàng cả đi lẫn về là:
Một doanh nghiệp sản xuất bánh với các loại bánh bao gồm A, B, C, D và chi phí nguyên liệu, số giờ lao động để sản xuất 1 tấn bánh và nguồn lực sẵn có như bên dưới: Hỏi doanh nghiệp này cần phải sản xuất mỗi loại bánh với số lượng bao nhiêu để tối đa hoá lợi nhuận.
Một người nông dân có một khu đất 20 ha và số ngày công làm việc sẵn có là 30 ngày. Hỏi người đó nên trồng loại rau, củ, quả nào để tối đa hoá lợi nhuận. Biết chi phí, lợi nhuận và nguồn lực được cho như bảng bên dưới:

7.7. Tài liệu tham khảo¶

7. Giới thiệu chung về optimization

1. Đại số tuyến tính

Deep AI KhanhBlog

7.1. Bài toán dạng tổng quát¶

7.2. Các bài toán tối ưu thực tiễn.¶

7.2.1. Bài toán vận chuyển¶

Bài toán¶

Bài toán qui hoạch tuyến tính (Linear Programming LP)¶

7.2.2. Bài toán chi phí sản xuất¶

Bài toán¶

Lời giải¶

7.2.3. Bài toán đóng thùng¶

Bài toán¶

Lời giải¶

7.3. Bài toán Geometric Programming GP¶

7.3.1. Đơn thức (monomials) và đa thức (posynomials)¶

7.3.2. Bài toán tối ưu dạng đa thức¶

7.3.3. Biến đổi GP về đạng convex¶

7.3.4. Giải bài toán đóng thùng bằng CVXOPT¶

7.4. Bài toán Quadratic Programming (QP)¶

7.4.1. Dạng Quadratic Programming - QP¶

7.4.2.Giải bài toán QP trên CVXOPT¶

7.5. Tổng kết¶

7.6. Bài tập¶

7.7. Tài liệu tham khảo¶