Quy hoạch tuyến tính

Bách khoa toàn thư mở Wikipedia

Trong toán học, quy hoạch tuyến tính(QHTT) (tiếng Anh: linear programming - LP) là bài toán tối ưu hóa, trong đó hàm mục tiêu (objective function) và các điều kiện ràng buộc đều là tuyến tính.

Trong bài toán này, cho một đa tạp (polytope) (chẳng hạn một đa giác hoặc một đa diện), và một hàm tuyến tính (affine) nhận giá trị thực

$f(x_1, x_2, \dots, x_n)=a_1x_1+a_2x_2+\cdots +a_nx_n+b\,$

xác định trên đa tạp đó, mục đích là tìm một điểm trên đa tạp tại đó hàm có giá trị nhỏ nhất (hoặc lớn nhất). Các điểm như vậy có thể không tồn tại, nhưng nếu chúng tồn tại phải tìm được ít nhất một điểm.

Mục lục

1 Dạng chuẩn tắc
- 1.1 ví dụ
2 Dạng gia tố (Augmented form)
- 2.1 Ví dụ
3 Các dạng đặc biệt

[sửa] Dạng chuẩn tắc

Dạng chuẩn tắc là dạng trực quan nhất của bài toán QHTT. Nó gồm ba thành phần sau:

1. Một hàm tuyến tính cần đạt max

nghĩa là cần tìm maximize $c_1 x_1 + c_2 x_2\,$

2. Các ràng buộc của bài toán dưới dạng các bất đẳng thức tuyến tính

$a_{11} x_1 + a_{12} x_2 \le b_1$

$a_{21} x_1 + a_{22} x_2 \le b_2$

$a_{31} x_1 + a_{32} x_2 \le b_3$

3. Các biến là không âm

$x_1 \ge 0$

$x_2 \ge 0$

Bài toán cũng thường được biểu diễn dưới dạng ma trận, khi đó ta có:

Tìm cực đại hàm $\mathbf{c}^T \mathbf{x}$

với ràng buộc $\mathbf{A}\mathbf{x} \le \mathbf{b}, \, \mathbf{x} \ge 0$

Một dạng khác là bài toán cực tiểu .

[sửa] ví dụ

Chẳng hạn một nông đan có A sào đất để canh tác, ông ta dự định trồng khoai tây và lúa. Ông ta cũng có một số giới hạn phân bón cuẩn bị sẵn là F và một số tiền vốn để mua giống là P. Chi phí tương ứng cho hai loại cây trông trên là (F₁, P₁) cho khoai tây và (F₂, P₂) cho lúa. Giả sử thu hoạc quy ra tiền cho mỗi sào khoai tây là S₁ , cho mỗi sào lúa làS₂. Nếu dành để trồng khoai tây x₁ sào và lúa x₂ sào, thì bài toán chọn số sào tồng khai tây và trồng lúa là bài toán QHTT sau đây:

Cực đại hóa hàm $S_1 x_1 + S_2 x_2 \,$		(hàm mục tiêu cực đại)
với các ràng buộc
	$x_1 + x_2 \le A$	(giới hạn đất trồng)
	$F_1 x_1 + F_2 x_2 \le F$	(giới hạn phân bón)
	$P_1 x_1 + P_2 x_2 \le P$	(giới hạn tiền vốn mua giống)
	$x_1 \ge 0,\, x_2 \ge 0$	(giá trị không âm)

Còn dưới dạng ma trận:

maximize $\begin{bmatrix} S_1 & S_2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$

ràng buộc $\begin{bmatrix} 1 & 1 \\ F_1 & F_2 \\ P_1 & P_2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \le \begin{bmatrix} A \\ F \\ P \end{bmatrix}, \, \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \ge 0$

[sửa] Dạng gia tố (Augmented form)

(Các tài liệu trong nước gọi là đưa về dạng chính tắc)

Bài toán QHTT được biến đổi về dạng gia tố trước khi trước khi giải bằng thuật toán đơn hình (simplex algorithm). Trong dạng này có bổ xung một số "biến bù" không âm để biến các bất đẳng thức thành các đẳng thức. Khi đó bài toán viết dưới dạng:

Cực đại hóa Z trong:

$\begin{bmatrix} 1 & -\mathbf{c}^T & 0 \\ 0 & \mathbf{A} & \mathbf{I} \end{bmatrix} \begin{bmatrix} Z \\ \mathbf{x} \\ \mathbf{x}_s \end{bmatrix} = \begin{bmatrix} 0 \\ \mathbf{b} \end{bmatrix}$

$\mathbf{x}, \, \mathbf{x}_s \ge 0$

trong đó x_s là các biến bù , còn Z là biến cần cực đại.

[sửa] Ví dụ

Bài toán trong ví dụ trên sau khi biến đổi có dạng:

Cực đại hóa	$S_1 x_1 + S_2 x_2\,$ =Z	(hàm mục tiêu)
với các ràng buộc
	$x_1 + x_2 + x_3 = A\,$	(ràng buộc gia tố)
	$F_1 x_1 + F_2 x_2 + x_4 = F\,$	(ràng buộc gia tố)
	$P_1 x_1 + P_2 x_2 + x_5 = P\,$	(ràng buộc gia tố)
	$x_1,x_2,x_3,x_4,x_5 \ge 0$

trong đó $x_3,x_4,x_5\,$ là các biến bù không âm.

Nó có thể viết dưới dạng ma trận:

Cực đại hóa Z trong:

$\begin{bmatrix} 1 & -S_1 & -S_2 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & F_1 & F_2 & 0 & 1 & 0 \\ 0 & P_1 & P_2 & 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} Z \\ x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{bmatrix} = \begin{bmatrix} 0 \\ A \\ F \\ P \end{bmatrix}, \, \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{bmatrix} \ge 0$