Quy hoạch tuyến tính

Quy hoạch tuyến tính — là một nhánh của quy hoạch toán học và là phương pháp nghiên cứu vận trù học được sử dụng rộng rãi, chuyên về phát triển lý thuyết và các phương pháp giải bài toán tìm cực trị (cực đại hoặc cực tiểu) của hàm tuyến tính khi có các ràng buộc tuyến tính.

Quy hoạch tuyến tính là một trong những công cụ mạnh mẽ và được áp dụng phổ biến nhất để giải các bài toán tối ưu hóa trong kinh tế, quản lý, lập kế hoạch, logistics và các lĩnh vực khác.

Đối tượng và mục đích

Bài toán cơ bản của quy hoạch tuyến tính — tìm cách phân bổ tối ưu các nguồn lực hạn chế để đạt được một mục tiêu nhất định, khi cả mục tiêu lẫn các ràng buộc về việc sử dụng nguồn lực đều có thể được biểu diễn bằng các quan hệ tuyến tính.

• Quy hoạch tuyến tính cho phép giải quyết các bài toán thực tiễn như:
• Lập kế hoạch sản xuất tối ưu.
• Tối ưu hóa luồng vận chuyển (bài toán vận tải).
• Phân bổ đầu tư tối ưu.
• Cắt nguyên liệu tối ưu. Bài toán phân công.

Phát biểu toán học của bài toán quy hoạch tuyến tính

Bài toán quy hoạch tuyến tính dạng chuẩn được phát biểu như sau:

Cần tìm các giá trị của biến quyết định sao cho cực đại hóa hoặc cực tiểu hóa hàm mục tiêu tuyến tính. Đồng thời, các biến quyết định phải thỏa mãn hệ ràng buộc gồm các phương trình tuyến tính và/hoặc bất phương trình tuyến tính. Thông thường, điều kiện không âm của các biến quyết định được bổ sung (giá trị của chúng phải lớn hơn hoặc bằng không), điều này thường được quy định bởi ý nghĩa vật lý hoặc kinh tế của bài toán.

Về mặt toán học, điều này có nghĩa là làm việc với các hàm tuyến tính và hệ phương trình/bất phương trình tuyến tính.

Các khái niệm cơ bản của quy hoạch tuyến tính

• Biến quyết định (Biến điều khiển): Các đại lượng mà giá trị của chúng cần được xác định trong quá trình giải bài toán (ví dụ: khối lượng sản xuất các sản phẩm khác nhau, số lượng nguồn lực phân bổ cho các mục tiêu khác nhau).
• Hàm mục tiêu: Hàm tuyến tính của các biến quyết định mà giá trị của nó cần được cực đại hóa hoặc cực tiểu hóa. Hàm này biểu diễn định lượng mục tiêu của bài toán (ví dụ: tổng lợi nhuận, tổng chi phí).
• Ràng buộc: Hệ phương trình tuyến tính và/hoặc bất phương trình tuyến tính mà các biến quyết định phải thỏa mãn. Các ràng buộc phản ánh giới hạn nguồn lực, yêu cầu công nghệ, chỉ tiêu kế hoạch và các điều kiện khác của bài toán.
• Miền chấp nhận được (MCD): Tập hợp tất cả các bộ giá trị của biến quyết định thỏa mãn mọi ràng buộc của bài toán. Về mặt hình học trong không gian nhiều chiều, MCD là một đa diện lồi (polyhedron), có thể không bị chặn hoặc rỗng.
• Nghiệm chấp nhận được: Bất kỳ bộ giá trị biến nào thuộc MCD.
• Nghiệm tối ưu: Nghiệm chấp nhận được mà tại đó hàm mục tiêu đạt giá trị cực trị (cực đại hoặc cực tiểu). Nếu nghiệm tối ưu tồn tại, nó luôn nằm trên biên của MCD, ít nhất tại một trong các đỉnh của đa diện lồi MCD (định lý cơ bản của quy hoạch tuyến tính).

Các phương pháp giải bài toán quy hoạch tuyến tính

Có một số phương pháp cơ bản để giải các bài toán quy hoạch tuyến tính:

• Phương pháp đồ thị: Được áp dụng cho các bài toán có hai biến quyết định. Cho phép biểu diễn trực quan MCD và hàm mục tiêu trên mặt phẳng, tìm nghiệm tối ưu bằng cách phân tích các đỉnh của MCD hoặc dịch chuyển đường đồng mức của hàm mục tiêu.
• Phương pháp đơn hình (Simplex): Thuật toán lặp đa năng do George Dantzig phát triển. Phương pháp lần lượt chuyển từ đỉnh này sang đỉnh kề của MCD, cải thiện giá trị hàm mục tiêu ở mỗi bước cho đến khi tìm được nghiệm tối ưu. Đây là phương pháp kinh điển và nổi tiếng nhất để giải các bài toán quy hoạch tuyến tính.
• Các phương pháp điểm nội: Lớp thuật toán thay thế xuất hiện sau phương pháp đơn hình. Chúng tiếp cận nghiệm tối ưu từ bên trong MCD, chứ không đi theo biên của nó. Các phương pháp này đặc biệt hiệu quả để giải các bài toán quy hoạch tuyến tính có kích thước rất lớn.

Tính đối ngẫu trong quy hoạch tuyến tính

Mỗi bài toán quy hoạch tuyến tính (gọi là bài toán gốc) đều có thể gắn với một bài toán quy hoạch tuyến tính khác gọi là bài toán đối ngẫu. Bài toán gốc và bài toán đối ngẫu liên hệ chặt chẽ với nhau:

Nghiệm của bài toán này cung cấp thông tin về nghiệm của bài toán kia. Giá trị tối ưu của hàm mục tiêu trong cả hai bài toán trùng nhau (nếu chúng tồn tại). Các biến của bài toán đối ngẫu có ý nghĩa kinh tế quan trọng — chúng tương ứng với giá bóng (hay định giá đối ngẫu) của các nguồn lực, cho thấy giá trị tối ưu của hàm mục tiêu bài toán gốc thay đổi bao nhiêu khi ràng buộc đối với nguồn lực tương ứng thay đổi một lượng nhỏ.

Ứng dụng của quy hoạch tuyến tính

Quy hoạch tuyến tính được ứng dụng rộng rãi trong:

• Kinh tế và kinh doanh (lập kế hoạch sản xuất, logistics, tài chính, marketing).
• Công nghiệp (tối ưu hóa quy trình công nghệ, quản lý tồn kho, cắt nguyên liệu).
• Giao thông vận tải (tối ưu hóa tuyến đường, lịch trình). Nông nghiệp (tối ưu hóa diện tích gieo trồng, khẩu phần thức ăn chăn nuôi).
• Năng lượng (tối ưu hóa tải của các công suất phát điện).

Tài liệu tham khảo

• Dantzig G. Линейное программирование, его применения и обобщения. — М.: Прогресс, 1966.
• Yudin D. B., Goldstein E. G. Линейное программирование (теория, методы и приложения). — М.: Наука, 1969.
• Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
• Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)

Xem thêm

• Nghiên cứu vận trù
• Tối ưu hóa
• Hàm mục tiêu
• Ràng buộc
• Miền chấp nhận được
• Nghiệm tối ưu