Các thành phần của bài toán quy hoạch tuyến tính

Các thành phần của bài toán quy hoạch tuyến tính

Loading Preview

Show

Sorry, preview is currently unavailable. You can download the paper by clicking the button above.

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 , … , x n ) = a 1 x 1 + a 2 x 2 + ⋯ + a n x n + b {\displaystyle f(x_{1},x_{2},\dots ,x_{n})=a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}+b\,}
Các thành phần của bài toán quy hoạch tuyến tính

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ột bài toán quy hoạch tuyến tính thường được phát biểu dưới dạng sau:

Tìm cực tiểu của c x {\displaystyle cx}   trên { x ∈ R n | A x ≤ b } {\displaystyle \{x\in \mathbb {R} ^{n}|Ax\leq b\}}  , trong đó A ∈ R m × n {\displaystyle A\in \mathbb {R} ^{m\times n}}  , b ∈ R m {\displaystyle b\in \mathbb {R} ^{m}}  , c ∈ R n {\displaystyle c\in \mathbb {R} ^{n}}  .

Như vậy, một bài toán quy hoạch tuyến tính được cho bởi:

1. Một hàm tuyến tính cần tìm cực tiểu: c x = c 1 x 1 + … + c n x n {\displaystyle cx=c_{1}x_{1}+\ldots +c_{n}x_{n}}  .

Thí dụ: 5 x 1 + 3 x 2 − x 3 {\displaystyle 5x_{1}+3x_{2}-x_{3}}  .

2. Các điều kiện (hay ràng buộc) dưới dạng các bất đẳng thức tuyến tính.

Thí dụ:
  • x ≥ 0 {\displaystyle x\geq 0}   (ứng với A = − I d {\displaystyle A=-Id}  , b = 0 {\displaystyle b=0}  ).
  • { x 1 + x 2 ≤ 1 x 1 ≥ 0 x 2 ≥ 0 {\displaystyle {\begin{cases}x_{1}+x_{2}\leq 1\\x_{1}\geq 0\\x_{2}\geq 0\end{cases}}\quad }   (ứng với A = [ 1 1 − 1 0 0 − 1 ] {\displaystyle A={\begin{bmatrix}1&1\\-1&0\\0&-1\end{bmatrix}}}  , b = [ 1 0 0 ] {\displaystyle b={\begin{bmatrix}1\\0\\0\\\end{bmatrix}}}  ).

Ghi chú: Các tài liệu khác nhau có thể có định nghĩa khác nhau về dạng chuẩn tắc của bài toán. Tuy nhiên, các dạng này là tương đương (xem [1]).

Ví dụ

Chẳng hạn một nông dân 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 lượng phân bó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à (F1, P1) cho khoai tây và (F2, P2) cho lúa. Giả sử thu hoạch quy ra tiền cho mỗi sào khoai tây là S1, cho mỗi sào lúa là S2. Nếu dành để trồng khoai tây x1 sào và lúa x2 sào, thì bài toán chọn số sào trồng khoai 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 {\displaystyle 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 ≤ A {\displaystyle x_{1}+x_{2}\leq A}   (giới hạn đất trồng)
F 1 x 1 + F 2 x 2 ≤ F {\displaystyle F_{1}x_{1}+F_{2}x_{2}\leq F}   (giới hạn phân bón)
P 1 x 1 + P 2 x 2 ≤ P {\displaystyle P_{1}x_{1}+P_{2}x_{2}\leq P}   (giới hạn tiền vốn mua giống)
x 1 ≥ 0 , x 2 ≥ 0 {\displaystyle x_{1}\geq 0,\,x_{2}\geq 0}   (giá trị không âm)

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

maximize [ S 1 S 2 ] [ x 1 x 2 ] {\displaystyle {\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}}   ràng buộc [ 1 1 F 1 F 2 P 1 P 2 ] [ x 1 x 2 ] ≤ [ A F P ] , [ x 1 x 2 ] ≥ 0 {\displaystyle {\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}A\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq 0}  

(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ổ sung 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: [ 1 − c T 0 0 A I ] [ Z x x s ] = [ 0 b ] {\displaystyle {\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}}}   x , x s ≥ 0 {\displaystyle \mathbf {x} ,\,\mathbf {x} _{s}\geq 0}  

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

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 {\displaystyle 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 {\displaystyle x_{1}+x_{2}+x_{3}=A\,}   (ràng buộc gia tố)
F 1 x 1 + F 2 x 2 + x 4 = F {\displaystyle 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 {\displaystyle 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 ≥ 0 {\displaystyle x_{1},x_{2},x_{3},x_{4},x_{5}\geq 0}  

trong đó x 3 , x 4 , x 5 {\displaystyle 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: [ 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 ] [ Z x 1 x 2 x 3 x 4 x 5 ] = [ 0 A F P ] , [ x 1 x 2 x 3 x 4 x 5 ] ≥ 0 {\displaystyle {\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}}\geq 0}  
  • Bài toán vận tải

  1. ^ Allaire 2005, chương 11.

Allaire, Grégoire (2005). Analyse numérique et optimisation (bằng tiếng Pháp). Ellipses. ISBN 9782730212557.

Lấy từ “https://vi.wikipedia.org/w/index.php?title=Quy_hoạch_tuyến_tính&oldid=66249285”