Kế hoạch tuyến tính

Trong toán học, quy hoạch tuyến tính (QHTT) (tiếng Anh: linear programming - LP) là một 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 có dạng tuyến tính.

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

$f(x_1,x_2,\dots <!--\; \dots \; -->,x_n)=a_1{x}_1+a_2{x}_2+\cdots <!--\; \cdots \; -->+a_n{x}_n+b$ +c

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

Lịch sử

Phương pháp giải hệ phương trình tuyến tính đã được phát hiện vào năm 1827 bởi Fourier, và được đặt tên là phương pháp loại bỏ Fourier-Motzkin.

Vào năm 1939, nhà toán học và kinh tế học Leonid Kantorovich đã giới thiệu một dạng bài toán quy hoạch tuyến tính tương đương với bài toán quy hoạch tuyến tính tổng quát và đề xuất phương pháp giải nó. Trong Thế chiến thứ 2, ông được giao nhiệm vụ lập kế hoạch chi tiêu và thu hồi để giảm chi phí quân đội và tăng tổn thất cho đối phương. Công việc của Kantorovich ban đầu đã bị lãng quên. Cùng thời điểm đó, nhà kinh tế học người Mỹ gốc Hà Lan T.C. Koopmans đã trình bày các bài toán kinh tế cổ điển dưới dạng bài toán tuyến tính. Kantorovich và Koopmans sau đó đã cùng nhận giải Nobel Kinh tế năm 1975. Năm 1941, Frank Lauren Hitchcock cũng đưa các bài toán vận tải dưới dạng phương trình tuyến tính và đưa ra một giải pháp tương tự như phương pháp simplex sau này. Hitchcock qua đời năm 1957 và giải Nobel không được truy tặng.

Dạng chuẩn tắc

Dạng chuẩn tắc là hình thức thông dụng và dễ hiểu nhất để mô tả một bài toán quy hoạch tuyến tính.

Một bài toán quy hoạch tuyến tính thường được diễn tả như sau:

Nhắm đến việc tìm giá trị 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}} .

Tóm lại, một bài toán quy hoạch tuyến tính được định nghĩa bởi:

1. Một hàm tuyến tính cần tìm giá trị cực tiểu: $cx=c_1{x}_1+\dots <!--\; \dots \; -->+c_n{x}_n$.

Ví dụ: $5x_1+3x_2-<!--\; -\; -->x_3$.

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

Ví dụ:

• $x\ge <!--\; \ge \; -->0$ (tương ứng với $A=-<!--\; -\; -->Id$, $b=0$).
• (tương ứng với , ).

Chú ý: Các tài liệu khác nhau có thể có các định nghĩa khác nhau về dạng chuẩn tắc của bài toán. Tuy nhiên, những dạng này vẫn có thể được coi là tương đương với nhau (xem thêm).

Ví dụ

Giả sử một nông dân sở hữu A sào đất để canh tác và dự định trồng khoai tây cùng lúa. Ông cũng có một lượng phân bón là F và một khoản tiền vốn để mua giống là P. Chi phí liên quan đến mỗi loại cây trồng là (F₁, P₁) cho khoai tây và (F₂, P₂) cho lúa. Giả sử thu hoạch từ mỗi sào khoai tây mang lại S₁ và từ mỗi sào lúa là S₂. Nếu ông quyết định trồng x₁ sào khoai tây và x₂ sào lúa, thì bài toán lựa chọn số sào trồng khoai tây và lúa có thể được mô tả như sau:

Dưới dạng ma trận, bài toán được thể hiện như sau:

Tối đa hóa

Các điều kiện ràng buộc

Dạng gia tăng (Augmented form)

(Ở các tài liệu trong nước, dạng này còn được gọi là dạng chuẩn)

Để giải bài toán QHTT bằng thuật toán đơn hình, chúng ta cần chuyển đổi nó sang dạng gia tăng. Dạng này thêm vào một số 'biến phụ' không âm để chuyển các bất đẳng thức thành đẳng thức. Vì vậy, bài toán được viết lại như sau:

Tối ưu hóa Z trong:

$x,x_s\ge <!--\; \ge \; -->0$

trong đó xs đại diện cho các biến bù, và Z là biến cần tối ưu hóa.

Ví dụ minh họa

Bài toán trong ví dụ được biến đổi thành dạng sau khi áp dụng các phép biến đổi.

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

Nó có thể được biểu diễn dưới dạng ma trận:

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

Các dạng đặc biệt của bài toán

• Vấn đề vận tải

Ghi chú