Phương pháp đơn giản là gì? - định nghĩa từ techopedia

Định nghĩa - Phương pháp Simplex có nghĩa là gì?

Phương pháp đơn giản, trong tối ưu hóa toán học, là một thuật toán nổi tiếng được sử dụng cho lập trình tuyến tính. Theo tạp chí Computing in Science & Engineering, phương pháp này được coi là một trong 10 thuật toán hàng đầu có nguồn gốc trong thế kỷ XX.

Phương pháp đơn giản trình bày một chiến lược có tổ chức để đánh giá các đỉnh của khu vực khả thi. Điều này giúp tìm ra giá trị tối ưu của hàm mục tiêu.

George Dantzig đã phát triển phương pháp đơn giản vào năm 1946.

Phương pháp này còn được gọi là thuật toán đơn giản.

Techopedia giải thích Phương pháp Simplex

Phương pháp đơn giản được sử dụng để xóa bỏ các vấn đề trong lập trình tuyến tính. Nó kiểm tra các đỉnh liền kề của bộ khả thi theo trình tự để đảm bảo rằng, ở mỗi đỉnh mới, hàm mục tiêu tăng hoặc không bị ảnh hưởng. Nói chung, phương pháp đơn giản là cực kỳ mạnh mẽ, thường chỉ lặp lại từ 2m đến 3 m (ở đây, m biểu thị phạm vi của các ràng buộc đẳng thức) và nó hội tụ trong thời gian đa thức dự đoán cho các phân phối cụ thể của đầu vào ngẫu nhiên.

Phương pháp đơn giản sử dụng chiến lược có hệ thống để tạo và kiểm tra các giải pháp đỉnh ứng cử viên cho một chương trình tuyến tính. Ở mỗi lần lặp, nó chọn biến có thể thực hiện sửa đổi lớn nhất đối với giải pháp tối thiểu. Biến đó sau đó thay thế một trong các biến số của nó, điều này hạn chế mạnh nhất nó, do đó chuyển phương thức đơn giản sang một phần khác của tập hợp giải pháp và hướng tới giải pháp cuối cùng.

Hơn nữa, phương pháp đơn giản có thể đánh giá liệu không có giải pháp thực sự tồn tại. Có thể thấy rằng thuật toán này rất tham lam vì nó phù hợp với lựa chọn tốt nhất ở mỗi lần lặp, không có nhu cầu về thông tin từ các lần lặp trước hoặc sắp tới.

Đôi khi, cấu trúc dữ liệu chính được áp dụng bởi phương thức đơn giản được gọi là từ điển. Từ điển bao gồm một minh họa của các phương trình được điều chỉnh chính xác đến cơ sở hiện có. Từ điển có thể được sử dụng để cung cấp một sự hiểu biết trực quan về lý do tại sao tất cả các biến nhập và rời khỏi cơ sở.