Thuật toán đơn hình đối ngẫu và ứng dụng trong tái tối ưu hóa với ràng buộc phụ

Phương pháp đơn hình (do G. B. Dantzig đề  xuất năm 1947) là phương pháp quen thuộc, có hiệu qủa để  giải bài toán qui hoạch tuyến tính.  Phương pháp đơn hình có nhiều biến thể  khác nhau, phù hợp với các dạng cụ  thể  của bài toán qui hoạch tuyến tính như: đơn hình gốc, đơn hình cải biên, đơn hình đối ngẫu, đơn hình gốc - đối ngẫu ... 

Trong  một  số  tình huống  thực tế, sau khi  giải  xong bài toán ta  thấy  cần bổsung thêm một số  ràng buộc vào bài toán. Nếu giải lại bài toán từ  đầu thì sẽ  tốn nhiều thời gian và công sức. Việc tận dụng lời giải đã có để  giải tiếp bài toán mới gọi là  kỹ  thuật tái tối ưu hóa  bài toán. Để  làm việc này, phương pháp đơn hình đối ngẫu rất hữu ích. Vì thế cần đi sâu tìm hiểu về phương pháp này, cùng các dạng thểhiện cụ thể và các ứng dụng của nó trong kỹ thuật tái tối ưu hóa.

Với ý nghĩa đó, chúng tôi chọn đề tài luận văn:

"Thuật toán đơn hình đối ngẫu và ứng dụng trong tái tối ưu hóa với ràng buộc phụ "

Mục đích chính của đề tài là tìm hiểu và trình bày kết quả lý thuyết về bài toán qui hoạch tuyến tính và qui hoạch tuyến tính đối ngẫu, các thuật toán khác nhau của phương pháp đơn hình đối ngẫu và ứng dụng thuật toán đơn hình đối ngẫu trong tái tối ưu hóa khi thêm ràng buộc phụ  vào bài toán.  Luận văn được viết dựa chủ  yếu trên các tài liệu tham khảo [1] - [4]. 

NỘI DUNG:

Chương 1. Kiến thức về qui hoạch tuyến tính 5

1.1. Bài toán qui hoạch tuyến tính và bài toán đối ngẫu 5

1.2. Các định lý đối ngẫu 8

1.3. Phương pháp đơn hình gốc và đơn hình đối ngẫu 10

Chương 2. Thuật toán đơn hình đối ngẫu 14

2.1. Thuật toán đơn hình đối ngẫu dạng đầy đủ 14

2.2. Thuật toán đơn hình đối ngẫu dạng cải biên 19

2.3. Áp dụng giải trò chơi ma trận 24

Chương 3. Kỹ thuật tái tối ưu hóa với ràng buộc phụ 28

3.1. Vấn đề tái tối ưu hóa 28

3.2. Thuật toán đơn hình đối ngẫu trong tái tối ưu hóa 29

3.3. Ví dụ minh họa 30

KẾT LUẬN 34

TÀI LIỆU THAM KHẢO

LƯU Ý:

Tài liệu được chia sẻ bởi CTV EBOOKBKMT "Mân Trần Lê" chỉ được dùng phục vụ mục đích học tập và nghiên cứu.

LINK DOWNLOAD

Phương pháp đơn hình (do G. B. Dantzig đề  xuất năm 1947) là phương pháp quen thuộc, có hiệu qủa để  giải bài toán qui hoạch tuyến tính.  Phương pháp đơn hình có nhiều biến thể  khác nhau, phù hợp với các dạng cụ  thể  của bài toán qui hoạch tuyến tính như: đơn hình gốc, đơn hình cải biên, đơn hình đối ngẫu, đơn hình gốc - đối ngẫu ... 

Trong  một  số  tình huống  thực tế, sau khi  giải  xong bài toán ta  thấy  cần bổsung thêm một số  ràng buộc vào bài toán. Nếu giải lại bài toán từ  đầu thì sẽ  tốn nhiều thời gian và công sức. Việc tận dụng lời giải đã có để  giải tiếp bài toán mới gọi là  kỹ  thuật tái tối ưu hóa  bài toán. Để  làm việc này, phương pháp đơn hình đối ngẫu rất hữu ích. Vì thế cần đi sâu tìm hiểu về phương pháp này, cùng các dạng thểhiện cụ thể và các ứng dụng của nó trong kỹ thuật tái tối ưu hóa.

Với ý nghĩa đó, chúng tôi chọn đề tài luận văn:

"Thuật toán đơn hình đối ngẫu và ứng dụng trong tái tối ưu hóa với ràng buộc phụ "

Mục đích chính của đề tài là tìm hiểu và trình bày kết quả lý thuyết về bài toán qui hoạch tuyến tính và qui hoạch tuyến tính đối ngẫu, các thuật toán khác nhau của phương pháp đơn hình đối ngẫu và ứng dụng thuật toán đơn hình đối ngẫu trong tái tối ưu hóa khi thêm ràng buộc phụ  vào bài toán.  Luận văn được viết dựa chủ  yếu trên các tài liệu tham khảo [1] - [4]. 

NỘI DUNG:

Chương 1. Kiến thức về qui hoạch tuyến tính 5

1.1. Bài toán qui hoạch tuyến tính và bài toán đối ngẫu 5

1.2. Các định lý đối ngẫu 8

1.3. Phương pháp đơn hình gốc và đơn hình đối ngẫu 10

Chương 2. Thuật toán đơn hình đối ngẫu 14

2.1. Thuật toán đơn hình đối ngẫu dạng đầy đủ 14

2.2. Thuật toán đơn hình đối ngẫu dạng cải biên 19

2.3. Áp dụng giải trò chơi ma trận 24

Chương 3. Kỹ thuật tái tối ưu hóa với ràng buộc phụ 28

3.1. Vấn đề tái tối ưu hóa 28

3.2. Thuật toán đơn hình đối ngẫu trong tái tối ưu hóa 29

3.3. Ví dụ minh họa 30

KẾT LUẬN 34

TÀI LIỆU THAM KHẢO

LƯU Ý:

Tài liệu được chia sẻ bởi CTV EBOOKBKMT "Mân Trần Lê" chỉ được dùng phục vụ mục đích học tập và nghiên cứu.

LINK DOWNLOAD

Chuyên mục: D. Luận văn