Giới thiệu tài liệu
Quy hoạch tuyến tính là một trong những bài toán tối ưu hóa quan trọng và được ứng dụng rộng rãi. Thuật toán đơn hình, do Dantzig đề xuất, dù hiệu quả trong thực tiễn nhưng về mặt lý thuyết lại có thời gian tính mũ, thúc đẩy nhiều nghiên cứu nhằm cải tiến. Luận văn này tập trung tìm hiểu và giới thiệu các thuật toán mới nhằm nâng cao hiệu quả tính toán cho phương pháp đơn hình trong quy hoạch tuyến tính.
Đối tượng sử dụng
Các nhà nghiên cứu, sinh viên, giảng viên và kỹ sư trong lĩnh vực tối ưu hóa, toán ứng dụng và quy hoạch tuyến tính.
Nội dung tóm tắt
Luận văn này tổng hợp các kiến thức cơ bản về quy hoạch tuyến tính (LP), bài toán đối ngẫu (DP), và các phương pháp đơn hình truyền thống (gốc và đối ngẫu). Đặc biệt, luận văn giới thiệu chi tiết ba phương pháp cải tiến thuật toán đơn hình nhằm nâng cao hiệu quả tính toán. Cụ thể, phương pháp đơn hình gốc – đối ngẫu cải biên (RPDSA) giải quy hoạch tuyến tính chính tắc bằng cách tạo ra dãy nghiệm cơ sở hội tụ về nghiệm tối ưu, có thể xem là cải biên của phương pháp đơn hình đối ngẫu hoặc dạng của phương pháp đơn hình điểm ngoài (EPSA). Hai phương pháp cải tiến khác là phương pháp góc nghiêng nhỏ nhất và phương pháp côsin đơn hình, đều dựa trên nhận xét rằng đỉnh tối ưu thường gần với đỉnh được tạo bởi các ràng buộc có góc giữa vectơ gradian và vectơ hệ số mục tiêu nhỏ nhất. Phương pháp góc nghiêng nhỏ nhất chọn các ràng buộc đó làm cơ sở xuất phát, trong khi phương pháp côsin đơn hình đưa dần các ràng buộc vào bài toán nới lỏng để giải. Luận văn cũng đề xuất hướng nghiên cứu tiếp theo là ứng dụng các thuật toán này vào các bài toán tối ưu cụ thể.
