Thuật toán Simplex và các điểm cực trị
Đối với câu hỏi này ngắn gọn của tôi là LP = chương trình tuyến tính, BFS = giải pháp khả thi cơ bản, SEF = dạng bình đẳng tiêu chuẩn.
Vì thuật toán Simplex lặp lại từ điểm cực trị đến điểm cực trị (tương ứng với thực tế là Simplex lặp lại từ BFS sang BFS khi LP ở SEF), thuật toán Simplex hoạt động như thế nào về mặt hình học khi vùng khả thi là một khối đa diện không thể nhận ra trong SEF (ví dụ: một nửa không gian)? Giả sử chúng ta có LP mà vùng khả thi không có điểm cực trị. Sau đó, chúng tôi có thể viết một LP 'tương đương' trong SEF và chạy thuật toán Simplex trên đó. Nhưng có những điểm cực trị cho hình đa diện mới này, trong khi không có điểm nào cho hình ban đầu, theo giả thiết. Ban đầu tôi nghĩ rằng các điểm cực trị của một LP tương ứng một cách khách quan với các điểm cực trị của LP kia, nhưng rõ ràng là không phải vậy.
Vậy khi nào các điểm cực trị của phiên bản SEF của LP tương ứng một cách khách quan với các điểm cực trị của phiên bản gốc? Và xa hơn nữa, khi sự phân biệt như vậy không được giữ vững, làm thế nào chúng ta có thể giải thích một cách hình học thuật toán Simplex đang làm gì về LP ban đầu?
Trả lời
thuật toán Simplex lặp lại từ điểm cực trị đến điểm cực trị
Về mặt kỹ thuật, không. Thuật toán simplex lặp lại từ cơ sở này sang cơ sở khác . Nó chỉ xảy ra rằng các giải pháp cơ bản khả thi tương ứng với các điểm cực trị. (ví dụ, đơn giản kép lặp lại qua các giải pháp cơ bản khả thi kép, không phải là các điểm cực trị của vùng khả thi ban đầu).
Hãy xem xét một LP ở dạng chuẩn, viết \begin{align} \min \ \ \ & c^{T}x\\ \text{s.t.} \ \ \ & Ax = b\\ &x \geq 0 \end{align}Vùng khả thi của LP đó luôn là vùng đa diện. Nếu nó không có điểm cực trị, thì nó trống (và không có giải pháp khả thi cơ bản nào) hoặc là một không gian con affine của$\mathbb{R}^{n}$. Bây giờ, trường hợp thứ hai không thể xảy ra, bởi vì không có không gian con affine nào có thể là tập con của$\mathbb{R}_{+}^{n}$.
Bây giờ, quay trở lại (những gì tôi nghĩ là) câu hỏi ban đầu của bạn: cho một đa diện ban đầu và một biểu diễn SEF cho nó, biểu diễn đó có các điểm cực trị không và chúng có tương ứng với các điểm cực trị của đa diện ban đầu không? Câu trả lời là: có, SEF sẽ có các điểm cực trị và không, chúng có thể không phải lúc nào cũng tương ứng với các điểm cực trị của hình đa diện ban đầu của bạn.
Đây là một ví dụ đơn giản: lấy $\mathcal{P} = \{x \in \mathbb{R}\}$, là một hình đa diện 1 chiều. Công thức của nó có một biến tự do và không có ràng buộc.
Để xây dựng một biểu diễn SEF, hãy thay thế $x$ bởi $x^{+} - x^{-}$ với $x^{\pm} \geq 0$. Hiện nay,$(0, 0)$ là một điểm cực trị của SEF đó, tương ứng với $x=0$, đó không phải là một điểm cực đoan của $\mathcal{P}$.
Không chắc tôi hoàn toàn hiểu câu hỏi của bạn, nhưng tôi đoán sự nhầm lẫn của bạn bắt nguồn từ giả định rằng một giải pháp cơ bản là một "điểm cực hạn". Một giải pháp cơ bản (không nhất thiết là nguyên thủy hoặc khả thi kép) chỉ là giao điểm của các ràng buộc về số hàng (một số trong số đó có thể là giới hạn). Có thể một vấn đề không có giải pháp khả thi sơ cấp hoặc kép, do đó, kết quả là không khả thi hoặc không khả thi. Các thuật toán simplex trong sách giáo khoa đôi khi bỏ qua thực tế là cần có một số dạng của phương pháp tiếp cận giai đoạn 1 để thiết lập BFS để thực sự bắt đầu thuật toán. Có thể giai đoạn sơ khai 1 nhận thấy vấn đề sơ khai là không khả thi và cũng có thể giai đoạn kép 1 nhận thấy vấn đề không bị ràng buộc.
Cập nhật: Câu trả lời của mtanneau có lẽ nói lên tất cả những gì cần nói, đối với một ràng buộc duy nhất với các biến tự do cũng áp dụng như vậy. Tôi chỉ muốn thêm rằng các triển khai simplex hoạt động trực tiếp với các biến tự do và không chuyển đổi chúng thành hai biến bị giới hạn bởi 0. Nhưng điều tương tự, thuật toán lặp lại các giải pháp cơ bản và quy ước được thực hiện rằng các biến tự do không cơ bản nhận giá trị 0. Cũng cần lưu ý rằng đối với khối đa diện có giới hạn, các nghiệm cơ bản tương ứng với các điểm cực trị.