Công cụ Giải Quy hoạch Tuyến tính

Giới thiệu về Công cụ Giải Quy hoạch Tuyến tính

Công cụ Giải Quy hoạch Tuyến tính là một máy tính trực tuyến tìm kiếm giá trị cực đại hoặc cực tiểu của một hàm mục tiêu tuyến tính tùy thuộc vào hệ các bất phương trình hoặc phương trình tuyến tính. Nó sử dụng phương pháp đơn hình (biến thể Big-M) để các ràng buộc <=, >= và = có thể được kết hợp tự do, và đối với các bài toán 2 biến, nó sẽ vẽ biểu đồ vùng khả thi tương tác với mọi đỉnh và điểm tối ưu được làm nổi bật.

Quy hoạch Tuyến tính là gì?

Một bài toán quy hoạch tuyến tính (LP) yêu cầu:

Tập hợp các điểm thỏa mãn mọi ràng buộc được gọi là vùng khả thi, một đa diện lồi. Định lý Cơ bản của Quy hoạch Tuyến tính phát biểu rằng nếu bài toán LP có tối ưu hữu hạn, nó sẽ đạt được tại một đỉnh (điểm cực biên) của đa diện này. Đây là lý do tại sao phương pháp đơn hình — di chuyển từ đỉnh này sang đỉnh khác — lại hiệu quả đến vậy.

Phương pháp Đơn hình Hoạt động như thế nào

Bắt đầu từ một đỉnh khả thi, phương pháp đơn hình liên tục cải thiện hàm mục tiêu bằng cách xoay sang một đỉnh lân cận có giá trị tốt hơn. Cơ chế:

1. Dạng chuẩn: chuyển đổi bài toán LP sang dạng cực đại hóa c^Tx với điều kiện Ax = b, x ≥ 0. Đối với các ràng buộc <=, thêm biến bù (slack); đối với >=, trừ biến dư (surplus) và thêm biến giả (artificial) với hình phạt lớn −M; đối với đẳng thức, thêm biến giả.
2. Bảng khởi tạo: cơ sở bao gồm các biến bù và biến giả, tạo ra một đỉnh bắt đầu rõ ràng.
3. Biến đi vào: chọn biến không cơ bản có chi phí rút gọn dương nhất \( c_j - z_j \). Nếu không có biến nào như vậy, lời giải hiện tại là tối ưu.
4. Biến rời khỏi: từ cột đi vào, thực hiện kiểm tra tỷ lệ tối thiểu — chia RHS của mỗi hàng cho phần tử dương của nó trong cột đi vào, và chọn hàng có tỷ lệ nhỏ nhất. Nếu không có phần tử dương nào, bài toán LP là không giới hạn.
5. Phép xoay: sử dụng phép khử Gauss để biến cột đi vào thành một vectơ đơn vị, với giá trị 1 ở hàng rời khỏi.
6. Lặp lại cho đến khi đáp ứng tiêu chí dừng.

Nếu bất kỳ biến giả nào vẫn còn trong cơ sở với giá trị dương khi kết thúc, bài toán LP ban đầu là không khả thi.

Phương pháp Đồ thị (cho 2 Biến)

Đối với các bài toán hai biến, vùng khả thi là một đa giác lồi 2D. Vì tối ưu luôn nằm ở một đỉnh, việc liệt kê mọi đỉnh và đánh giá hàm mục tiêu tại đó là đủ để giải quyết bài toán. Máy tính này thực hiện việc liệt kê đó bằng cách giao nhau giữa mọi cặp đường biên ràng buộc, chỉ giữ lại các giao điểm thỏa mãn tất cả các ràng buộc khác và sắp xếp chúng ngược chiều kim đồng hồ để trực quan hóa.

Cú pháp Nhập liệu

Viết hàm mục tiêu trên dòng đầu tiên, sau đó là mỗi ràng buộc trên một dòng. Tên biến có thể là bất kỳ mã định danh nào (x, y, x1, profit…). Các toán tử là <=, >= và =. Điều kiện không âm có thể được viết là x, y >= 0 như một lối tắt.

Các dòng trống và nhận xét bắt đầu bằng # sẽ bị bỏ qua. Trình giải chấp nhận tối đa 8 biến quyết định và 20 ràng buộc.

Ví dụ Thực tế

Hãy xem xét một xưởng đồ nội thất đóng bàn và ghế. Mỗi chiếc bàn mang lại lợi nhuận $3 và cần 1 đơn vị gỗ và 2 đơn vị nhân công. Mỗi chiếc ghế mang lại lợi nhuận $5 và cần 1 đơn vị gỗ, 1 đơn vị nhân công và 3 đơn vị vecni. Hiện có: 10 gỗ, 16 nhân công, 18 vecni. Với x = số bàn và y = số ghế, bài toán LP là:

Vùng khả thi là một hình ngũ giác. Đánh giá Z tại mỗi đỉnh:

Vì vậy, xưởng nên đóng 6 chiếc bàn và 4 chiếc ghế để đạt lợi nhuận tối đa là $38. Các ràng buộc về gỗ và nhân công là ràng buộc chặt (chúng bằng RHS tại điểm tối ưu); vecni có biến bù bằng 0 (cũng chặt trong trường hợp này), nghĩa là cả ba nguồn lực đều được sử dụng hết.

Các Lỗi Thường gặp & Những gì Trình giải Phát hiện

Ứng dụng

• Phối hợp sản phẩm & lập kế hoạch sản xuất — nên sản xuất bao nhiêu mỗi loại sản phẩm để có lợi nhuận tối đa trong giới hạn nguồn lực.
• Bài toán ăn kiêng & phối trộn — tối thiểu hóa chi phí khẩu phần ăn hoặc thức ăn chăn nuôi mà vẫn đáp ứng các mức tối thiểu về dinh dưỡng.
• Vận tải & phân công — tối thiểu hóa chi phí vận chuyển khi cung và cầu phải cân bằng.
• Tối ưu hóa danh mục đầu tư — tối đa hóa lợi nhuận kỳ vọng dưới các ràng buộc về rủi ro (đã tuyến tính hóa).
• Luồng mạng — luồng cực đại và luồng chi phí cực tiểu được quy về LP với ma trận hệ số đơn mô-đun hoàn toàn.
• Lập lịch — phân bổ nhân lực với yêu cầu ca trực và giới hạn tổng số giờ làm việc.

Cách sử dụng Máy tính này

1. Nhập bài toán LP của bạn vào hộp văn bản. Dòng đầu tiên phải bắt đầu bằng Maximize hoặc Minimize. Mỗi dòng tiếp theo là một ràng buộc.
2. Sử dụng lối tắt x, y >= 0 để khai báo điều kiện không âm cho tất cả các biến được liệt kê cùng một lúc.
3. Nhấp vào Giải Bài toán LP. Trình giải sẽ báo cáo giá trị tối ưu Z, giá trị tối ưu của từng biến quyết định, danh sách các ràng buộc chặt và đối với bài toán LP 2 biến là một biểu đồ vùng khả thi tương tác.
4. Di chuột qua một đỉnh trên biểu đồ để xem tọa độ và giá trị Z của nó. Điểm tối ưu được đánh dấu bằng một ngôi sao.
5. Xem lại các bảng đơn hình để thấy từng bước xoay và theo dõi cách phương pháp cải thiện giá trị Z. Cột đi vào được tô màu vàng; hàng rời khỏi được tô màu đỏ.

Câu hỏi Thường gặp

Bài toán quy hoạch tuyến tính là gì?

Một bài toán quy hoạch tuyến tính (LP) tìm kiếm giá trị cực đại hoặc cực tiểu của một hàm mục tiêu tuyến tính trên một tập hợp các biến quyết định thỏa mãn một hệ phương trình hoặc bất phương trình tuyến tính. Tập khả thi là một đa diện lồi, và tối ưu luôn đạt được tại một trong các đỉnh của nó — đây là sự thật mấu chốt mà phương pháp đơn hình khai thác.

Phương pháp đơn hình hoạt động như thế nào?

Phương pháp đơn hình di chuyển dọc theo các đỉnh của đa diện khả thi. Mỗi bước (một "phép xoay") hoán đổi một biến trong cơ sở cho một biến khác, di chuyển đến một đỉnh lân cận có hàm mục tiêu tốt hơn hẳn. Thuật toán dừng lại khi không có phép xoay nào có thể cải thiện Z — đỉnh hiện tại khi đó là tối ưu. Công cụ này sử dụng biến thể Big-M để có thể kết hợp các ràng buộc <=, >= và =.

Vùng khả thi là gì?

Vùng khả thi là tập hợp tất cả các giá trị biến thỏa mãn đồng thời mọi ràng buộc. Đối với 2 biến, nó là một đa giác lồi 2D; đối với n biến, nó là một đa diện n chiều. Đa diện trống có nghĩa là bài toán LP không khả thi; đa diện kéo dài vô hạn theo hướng cải thiện có nghĩa là bài toán LP không giới hạn.

"Không giới hạn" có nghĩa là gì trong quy hoạch tuyến tính?

Một bài toán LP là không giới hạn khi vùng khả thi kéo dài đến vô tận theo hướng mà hàm mục tiêu tiếp tục được cải thiện. Ví dụ, Maximize x với điều kiện x ≥ 0 không có cực đại hữu hạn. Các bài toán LP thực tế trả về kết quả không giới hạn thường cho thấy một ràng buộc bị thiếu — thường là chặn trên của một nguồn lực hoặc biến số.

"Đa tối ưu" có nghĩa là gì?

Đa tối ưu xảy ra khi có nhiều hơn một điểm đạt được cùng một giá trị hàm mục tiêu tốt nhất. Về mặt hình học, hàm mục tiêu song song với một cạnh ràng buộc chặt của đa giác, vì vậy mọi điểm dọc theo cạnh đó — và mọi tổ hợp lồi của các điểm mút của nó — đều là tối ưu. Trình giải sẽ gắn cờ này khi bất kỳ biến quyết định không cơ bản nào có chi phí rút gọn bằng không khi kết thúc.

Trình giải chấp nhận bao nhiêu biến và ràng buộc?

Tối đa 8 biến quyết định và 20 ràng buộc. Biểu đồ vùng khả thi tương tác chỉ được vẽ cho các bài toán 2 biến; với 3 biến trở lên, bạn vẫn nhận được lời giải đơn hình đầy đủ, các bảng đơn hình từng bước và báo cáo ràng buộc chặt.

Đọc thêm

• Quy hoạch tuyến tính — Wikipedia
• Thuật toán đơn hình — Wikipedia (Tiếng Anh)
• Phương pháp Big M — Wikipedia (Tiếng Anh)
• Đối ngẫu trong tối ưu hóa — Wikipedia

Các công cụ liên quan khác:

Phép toán toán học nâng cao:

• Máy Tính Antilog
• Máy tính hàm Beta
• Máy tính hệ số nhị thức
• Máy tính phân phối xác suất nhị thức
• Máy tính Bitwise
• Máy tính Định lý Giới hạn Trung tâm
• Máy tính kết hợp
• Máy tính hàm lỗi bổ sung
• Máy tính số phức
• Máy tính Entropy
• Máy tính chức năng lỗi
• Máy tính giảm dần theo cấp số nhân
• Máy tính tăng trưởng theo cấp số nhân
• Máy tính Tích phân Lũy thừa
• máy-tính-số-mũ-độ-chính-xác-cao Nổi bật
• Máy tính giai thừa Nổi bật
• Máy tính Hàm Gamma
• Máy tính tỷ lệ vàng
• Máy tính Nửa đời
• Máy tính phần trăm tăng trưởng
• Máy tính hoán vị
• Máy tính Phân phối Poisson
• Máy tính căn bậc của đa thức với các bước chi tiết
• Máy tính xác suất
• Máy tính phân bố xác suất
• Máy tính Tỷ lệ
• Máy tính công thức bậc hai
• Máy Tính Khoa Học
• Máy tính ký hiệu khoa học
• Máy Tính Chữ Số Có Nghĩa Mới
• Máy tính tổng khối
• Máy tính tổng các số liên tiếp
• Máy tính Tổng Bình phương
• Công cụ tạo bảng chân trị
• Máy tính lý thuyết tập hợp
• Công cụ tạo Biểu đồ Venn (3 Tập hợp)
• Máy tính Định lý Số dư Trung Quốc
• Máy tính Hàm Phi Euler
• Máy tính Thuật toán Euclid Mở rộng
• Máy tính Nghịch đảo Nhân theo Mô-đun
• Máy tính Phân số liên tục
• Máy tính Đường đi Ngắn nhất Dijkstra
• Máy tính Cây khung nhỏ nhất
• Trình xác thực dãy bậc đồ thị
• Máy tính Hoán vị lệch (Giai thừa phụ)
• Máy tính số Stirling
• Máy tính Nguyên lý Chuồng bồ câu
• Máy tính Phân phối Dừng Chuỗi Markov
• Máy Tính Làm Tròn Mới
• Máy Tính Phân Phối Nhị Thức Âm Mới
• Máy tính Hoán vị Có lặp Mới
• Máy Tính Lũy Thừa Modular Mới
• Máy Tính Căn Nguyên Thủy
• Công Cụ Rút Gọn Đại Số Boolean Mới
• Công cụ Giải Bản đồ Karnaugh (K-Map) Mới
• Máy Tính Tô Màu Đồ Thị Mới
• Máy Tính Sắp Xếp Topo Mới
• Máy Tính Ma Trận Kề Mới
• Máy tính Bao hàm - Loại trừ Mới
• Công cụ Giải Quy hoạch Tuyến tính Mới
• Trình Giải Bài Toán Người Du Hành (TSP) Mới
• Công cụ Kiểm tra Đường đi Hamilton Mới
• Trình Kiểm Tra Đồ Thị Phẳng Mới
• Máy Tính Luồng Mạng (Luồng Cực Đại) Mới
• Trình giải Bài toán Hôn nhân Ổn định Mới
• Máy Tính Bậc Lý Thuyết Nhóm Mới
• Máy tính Vành và Trường Mới