Một bài toán quy hoạch tuyến tính là một bài toán tối ưu có hữu hạn biến, hàm mục tiêu tuyến tính và
miền chấp nhận được được định nghĩa bởi hữu hạn các đẳng thức hay bất đẳng thức tuyến tính.
Hàm số tuyến tính của các biến x 1 , x 2 , . . . , x n x_1, x_2, ..., x_n x 1 , x 2 , ... , x n
f ( x ) = c 1 x 1 + c 2 x 2 + … + c n x n f(x) = c_1x_1 + c_2x_2 + \ldots + c_nx_n f ( x ) = c 1 x 1 + c 2 x 2 + … + c n x n với hằng số c i ∈ R , i = 1 , 2 , . . . , n c_i \in \mathbb{R}, i = 1, 2, ..., n c i ∈ R , i = 1 , 2 , ... , n
Một điều kiện đẳng thức tuyến tính có dạng:
a 1 x 1 + a 2 x 2 + … + a n x n = α a_1x_1 + a_2x_2 + \ldots + a_nx_n = \alpha a 1 x 1 + a 2 x 2 + … + a n x n = α với α , a 1 , a 2 , . . . , a n ∈ R \alpha, a_1, a_2, ..., a_n \in \mathbb{R} α , a 1 , a 2 , ... , a n ∈ R
Một điều kiện bất đẳng thức tuyến tính có dạng:
a 1 x 1 + a 2 x 2 + … + a n x n ≤ α a_1x_1 + a_2x_2 + \ldots + a_nx_n \leq \alpha a 1 x 1 + a 2 x 2 + … + a n x n ≤ α hoặc
a 1 x 1 + a 2 x 2 + … + a n x n ≥ α a_1x_1 + a_2x_2 + \ldots + a_nx_n \geq \alpha a 1 x 1 + a 2 x 2 + … + a n x n ≥ α với α , a 1 , a 2 , . . . , a n ∈ R \alpha, a_1, a_2, ..., a_n \in \mathbb{R} α , a 1 , a 2 , ... , a n ∈ R
Dạng thông thường của bài toán quy hoạch tuyến tính tối đa hóa :
maximize c 1 x 1 + c 2 x 2 + … + c n x n subject to a i 1 x 1 + a i 2 x 2 + … + a i n x n ≤ α i , i = 1 , . . . , s . b j 1 x 1 + b j 2 x 2 + … + b j n x n = β j , j = 1 , . . . , r . \begin{align*}
\text{maximize} & \ \ c_1x_1 + c_2x_2 + \ldots + c_nx_n \\
\text{subject to} & \ \ a_{i1}x_1 + a_{i2}x_2 + \ldots + a_{in}x_n \leq \alpha_i, \ i = 1, ..., s. \\
& \ \ b_{j1}x_1 + b_{j2}x_2 + \ldots + b_{jn}x_n = \beta_j, \ j = 1, ..., r.
\end{align*} maximize subject to c 1 x 1 + c 2 x 2 + … + c n x n a i 1 x 1 + a i 2 x 2 + … + a in x n ≤ α i , i = 1 , ... , s . b j 1 x 1 + b j 2 x 2 + … + b j n x n = β j , j = 1 , ... , r . Bài toán trên có s s s r r r
Biểu diễn bài toán trên dưới dạng ma trận, ta có:
maximize c ⊤ x subject to A x ≤ a B x = b \begin{align*}
\text{maximize} & \ \ c^\top x \\
\text{subject to} & \ \ Ax \leq a \\
& \ \ Bx = b
\end{align*} maximize subject to c ⊤ x A x ≤ a B x = b trong đó:
c = [ c 1 ⋮ c n ] , a = [ α 1 ⋮ α n ] , b = [ β 1 ⋮ β n ] c =
\begin{bmatrix}
c_1 \\
\vdots \\
c_n
\end{bmatrix}
, \ \
a =
\begin{bmatrix}
\alpha_1 \\
\vdots \\
\alpha_n
\end{bmatrix}
, \ \
b =
\begin{bmatrix}
\beta_1 \\
\vdots \\
\beta_n
\end{bmatrix} c = c 1 ⋮ c n , a = α 1 ⋮ α n , b = β 1 ⋮ β n A = [ a 11 … a 1 n ⋮ ⋱ ⋮ a s 1 … a s n ] , B = [ b 11 … b 1 n ⋮ ⋱ ⋮ b r 1 … b r n ] A =
\begin{bmatrix}
a_{11} & \ldots & a_{1n} \\
\vdots & \ddots & \vdots \\
a_{s1} & \ldots & a_{sn}
\end{bmatrix}
, \ \
B =
\begin{bmatrix}
b_{11} & \ldots & b_{1n} \\
\vdots & \ddots & \vdots \\
b_{r1} & \ldots & b_{rn}
\end{bmatrix} A = a 11 ⋮ a s 1 … ⋱ … a 1 n ⋮ a s n , B = b 11 ⋮ b r 1 … ⋱ … b 1 n ⋮ b r n Tương tự, ở bài toán quy hoạch tuyến tính tối thiểu hóa , ta chỉ cần đảo dấu ≤ \leq ≤ ≥ \geq ≥