goiviettel
goiviettel
Trang chủ Uncategorized Quy hoạch tuyến tính – Phần 1

Quy hoạch tuyến tính – Phần 1

Quy hoạch tuyến tính (Linear programming) là 1 trong mỗi dạng vấn đề tối ưu cơ bạn dạng nhất. Dạng vấn đề này đòi hỏi tất cả chúng ta nên tối ưu hóa một hàm tiềm năng tuyến tính và nên thỏa mãn nhu cầu một số trong những buộc ràng tuyến tính. Loạt nội dung bài viết này sẽ hỗ trợ cho tới chúng ta với những nom trực quan lại rộng lớn về chủ thể phổ cập này.

Các bài bác không giống nhập loạt bài:

Bạn đang xem: Quy hoạch tuyến tính – Phần 1

  • Phần 2: Thuật toán đơn hình – Giải vì chưng đại số
  • Phần 3: Thuật toán đơn hình – Giải vì chưng bảng
  • Phần 4: Thuật toán đơn hình nhị pha

Dạng bài bác toán

Quy hoạch tuyến tính thông thường phát hiện trong những vấn đề về tài chính. Ví dụ như vấn đề sau đây:

Một nhà hàng quán ăn với 30 con cái hào, 24 con cái tôm và 18 con cái nhím biển cả. Tuy nhiên, những loại thủy hải sản này nên được chế trở nên theo đòi món:

  • Món A giá chỉ 8 đồng cần thiết 5 con cái hào, 2 con cái tôm và 1 con cái nhím biển cả.
  • Món B giá chỉ 6 đồng cần thiết 3 con cái hào, 3 con cái tôm và 3 con cái nhím biển cả.

Hãy xác lập con số của từng khoản nhằm đem về nhiều ROI nhất.

Đầu tiên, tất cả chúng ta nên xác lập những biến (variable) của vấn đề. Trong vấn đề này, tất cả chúng ta có: x là con số khoản A (8 đồng) và y là con số khoản B (6 đồng).

Thứ nhị, tất cả chúng ta cần thiết xác định hàm mục tiêu (objective function) của vấn đề. Tại trên đây tất cả chúng ta cần thiết tối nhiều hóa (maximize) ROI này đó là 8 đồng * x + 6 đồng * y:

\max\quad 8x + 6y

Thứ thân phụ, tất cả chúng ta cần thiết xác lập những ràng buộc (constraint) của vấn đề. Ràng buộc loại nhất là con số của từng loại thủy hải sản. Số lượng hào cần thiết nhằm nấu nướng là 5 con cái cho từng khoản A và 3 con cái cho từng khoản B, tức 5x + 3y. Số này nên ko to hơn con số hào hiện nay với, tức là 30 con cái. Vậy buộc ràng con cái con số hào là:

5x + 3y \leq 30

Tương tự động với tôm và nhím biển cả, tất cả chúng ta đạt thêm 2 buộc ràng khác:

\begin{aligned} 2x + 3y &\leq 24 \\ x + 3y &\leq 18 \end{aligned}

Chúng tớ đạt thêm 2 buộc ràng nữa này đó là số khoản A và B nên ko âm:

Xem thêm: 8 lợi ích của việc lập Kế hoạch Hành động hàng quý QAP - Quarterly Action Planning là gì?

x,\ hắn \geq 0

Gom toàn bộ lại, tất cả chúng ta với vấn đề sau (s.t. là ghi chép tắt cho tới chữ “such that” (sao cho)):

\begin{aligned} \max\quad&8x + 6y \\ \text{s.t.}\quad&5x + 3y \leq 30\\ &2x + 3y \leq 24\\ &x + 3y \leq 18\\ &x,hắn \geq 0 \end{aligned}

Trong vấn đề bên trên, tất cả chúng ta thấy hàm tiềm năng và những buộc ràng là những hàm tuyến tính theo đòi những trở nên. Do ê, tất cả chúng ta rất có thể vận dụng quy hướng tuyến tính nhằm giải vấn đề này.

Giải vì chưng trang bị thị

Giải vì chưng trang bị thị tuy rằng chỉ rất có thể vận dụng với những vấn đề với 2 hoặc 3 trở nên, tuy nhiên rất có thể cho tới chúng ta thấy phần nào là phía giải của vấn đề này. Chúng tớ sẽ sở hữu một hệ tọa chừng ứng với 2 trở nên x và y của vấn đề. Trong hệ tọa chừng này, tất cả chúng ta tiếp tục theo thứ tự vẽ những đàng 5x + 3y = 30 (xanh dương), 2x + 3y = 24 (đỏ), x + 3y = 18 (xanh lá):

LP1

Một mặt mũi của đường thẳng liền mạch tiếp tục ứng với vệt to hơn và mặt mũi sót lại được xem là nhỏ rộng lớn. Trong hình, mặt mũi tô color ứng với mặt mũi nhỏ rộng lớn (thỏa ràng buộc). Giao của 3 phần tô color và số lượng giới hạn x,hắn \geq 0 bên trên trục tọa chừng tiếp tục tạo ra miền khả thi hay miền xác định (feasible region) của vấn đề, được tế bào mô tả với những đàng đứt đoạn bên trên hình. Điểm ở trong miền khả ganh đua được gọi là một nghiệm (feasible solution). Các điểm không giống ở ngoài miền này sẽ không còn thỏa một trong những buộc ràng của vấn đề, bởi vậy sẽ không còn khả ganh đua (infeasible). Sau ê, tất cả chúng ta vẽ những đàng thể hiện nay hàm tiềm năng z = 8x + 6y với z thay cho thay đổi.

LP1-isocost

Chúng tớ rất có thể thấy, Lúc tăng dần dần hàm tiềm năng của tất cả chúng ta, tất cả chúng ta dịch chuyển đàng z = 8x + 6y kể từ góc bên dưới ngược lên góc bên trên nên. Điểm sau cuối tuy nhiên đường thẳng liền mạch này chạm nhập miền khả ganh đua đó là điểm tuy nhiên tất cả chúng ta cần thiết thám thính. Điểm này được gọi là nghiệm tối ưu (optimal solution) của vấn đề. Trong ví dụ này, điểm này còn có tọa chừng là x = 3,\ y=5, tức 3 khoản A (8 đồng) và 5 khoản B (6 đồng). Tại điểm đó, ROI là cực lớn và có mức giá trị là z = 54. Ta rất có thể ra soát, với nghiệm bên trên, tất cả chúng ta cần thiết 3 * 5 + 5 * 3 = 30 con cái hào, 3 * 2 + 5 * 3 = 21 con cái tôm, 3 * 1 + 5 * 3 = 18 con cái nhím biển cả, và ROI là 3 * 8 + 5 * 6 = 54 đồng.

Xem thêm: Dự án đầu tư xây dựng phải lập Báo cáo nghiên cứu khả thi được pháp luật quy định như thế nào? Nội dung Báo cáo nghiên cứu khả thi đầu tư xây dựng gồm những gì?

Không nên vấn đề quy hướng tuyến tính nào là cũng có thể có nghiệm tối ưu. Bài toán tuy nhiên miền xác lập là trống rỗng được gọi là vô nghiệm (infeasible). Nếu vấn đề ko đầy đủ buộc ràng, hàm tiềm năng rất có thể tăng (khi tối nhiều hóa) hoặc rời (khi ít nhất hóa) tự do không tồn tại số lượng giới hạn, thì vấn đề này được gọi là không với cận (unbounded). Ví dụ, nếu như nhập vấn đề ví dụ bên trên không tồn tại buộc ràng nào là ngoài x, hắn \geq 0 thì z = 8x + 6y rất có thể tăng tự do và bởi vậy, vấn đề không tồn tại cận và không tồn tại nghiệm tối ưu.

Ta xem xét rằng, tiếp tục luôn luôn trực tiếp với cùng một nghiệm tối ưu là đỉnh (vertex) của hình nhiều giác tạo ra vì chưng miền tối ưu. Đây là 1 để ý rất rất cần thiết và là mối cung cấp hứng thú cho tới thuật toán đơn hình (simplex algorithm) dùng để làm giải vấn đề quy hướng tuyến tính. Thuật toán đơn hình sẽ tiến hành nói đến nhập phần sau. Cảm ơn các bạn đang được theo đòi dõi nội dung bài viết này.

Sách tham lam khảo: Luenberger, David G., and Yinyu Ye. Linear and Nonlinear Programming. Springer, 2008.

BÀI VIẾT NỔI BẬT