'Không giới hạn' (unbounded) 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 vô hạ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 ràng buộc duy nhất là x >= 0 sẽ không có cực đại hữu hạn. Các bài toán LP thực tế thiếu ràng buộc thường gặp triệu chứng này. Trình giải sẽ gắn cờ nó trong quá trình kiểm tra tỷ lệ đơn hình khi không tồn tại biến rời khỏi cơ sở.

'Đa tối ưu' (alternate optima) có nghĩa là gì?

Đa tối ưu xảy ra khi có nhiều hơn một điểm đạt được giá trị hàm mục tiêu tối ưu. 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 của đa giác, vì vậy mọi điểm dọc theo cạnh đó đều là tối ưu. Trình giải này gắn cờ đa tối ưu bất cứ khi nào một biến quyết định không cơ bản có chi phí rút gọn bằng không tại bảng cuối cùng.

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

Giải bài toán quy hoạch tuyến tính bằng phương pháp đơn hình. Hỗ trợ mục tiêu tối đa hoặc tối thiểu, ràng buộc hỗn hợp và tối đa tám biến quyết định, với bài toán hai biến sẽ vẽ vùng khả thi và đánh dấu điểm tối ưu.

Sử dụng miễn phíKhông cần đăng kýKết quả tức thì

Công cụ Giải Quy hoạch Tuyến tínhDùng thử ngay — miễn phí ▼

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

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:

Maximize (hoặc minimize): Z = c₁ x₁ + c₂ x₂ + … + c_n x_n tùy thuộc vào: a₁₁ x₁ + … + a_1n x_n (≤, ≥, hoặc =) b₁ a₂₁ x₁ + … + a_2n x_n (≤, ≥, hoặc =) b₂ … a_m1 x₁ + … + a_mn x_n (≤, ≥, hoặc =) b_m x₁, x₂, …, x_n ≥ 0

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ế:

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ả.
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.
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.
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.
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.
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.

Maximize 3x + 5y x + y <= 10 2x + y <= 16 x + 3y <= 18 x, y >= 0

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à:

Maximize Z = 3x + 5y x + y <= 10 (gỗ) 2x + y <= 16 (nhân công) x + 3y <= 18 (vecni) x, y >= 0

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

Đỉnh (x, y)	Z = 3x + 5y	Khả thi?
(0, 0)	0	Có
(8, 0)	24	Có
(6, 4)	38 ← tối ưu	Có
(0, 6)	30	Có

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

Tình huống	Triệu chứng	Cách khắc phục
LP không giới hạn	Trình giải báo cáo "Unbounded"	Thêm ràng buộc chặn trên còn thiếu. Hàm mục tiêu có thể tăng không giới hạn vì vùng khả thi kéo dài vô tận theo hướng cải thiện.
LP không khả thi	Trình giải báo cáo "Infeasible"	Các ràng buộc mâu thuẫn lẫn nhau (ví dụ: `x >= 10` và `x <= 5`). Kiểm tra lại mọi cặp biên.
Đa tối ưu	Huy hiệu cảnh báo; đỉnh tối ưu là duy nhất nhưng Z đạt được dọc theo một cạnh	Xảy ra khi vectơ hàm mục tiêu song song với một cạnh ràng buộc chặt. Bất kỳ tổ hợp lồi nào của hai đỉnh trên cạnh đó cũng đều tối ưu.
Thoái hóa / Vòng lặp	Đơn hình lặp lại mà không cải thiện Z	Hiếm gặp trong các bài toán sách giáo khoa; có thể được giải quyết bằng quy tắc Bland. Trình giải này giới hạn số lần lặp để tránh vòng lặp vô hạ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

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.
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.
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.
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.
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

Tham khảo nội dung, trang hoặc công cụ này như sau:

"Công cụ Giải Quy hoạch Tuyến tính" tại https://MiniWebtool.com/vi/cong-cu-giai-quy-hoach-tuyen-tinh/ từ MiniWebtool, https://MiniWebtool.com/

bởi đội ngũ miniwebtool. Cập nhật: 21 tháng 4, 2026

Có API dành cho developer: Chạy công cụ này từ ứng dụng, tự động hóa hoặc agent của bạn bằng một yêu cầu HTTP JSON. Xem tài liệu API

Bạn cũng có thể thử AI Giải Toán GPT của chúng tôi để giải quyết các vấn đề toán học của bạn thông qua câu hỏi và trả lời bằng ngôn ngữ tự nhiên.