Quy hoạch tuyến tính


Chương 1. Bài toán quy hoạch tuyến tính

Từ một số mô hình thực tế, chúng tôi đưa ra định nghĩa của bài toán quy hoạch tuyến tính tổng quát và một số dạng thông dụng của nó. Để sinh viên tiếp thu được một cách dễ dàng, chúng tôi đưa ra phương pháp đồ thị để giải bài toán quy hoạch tuyến tính hai biến, đây là phương pháp đơn giản nhất để giải bài toán ở dạng hai biến.

Chương 2. Tính chất của tập phương án, của tập phương án tối ưu

Để sinh viên có thể tiếp cận dễ dàng với các kiến thức ở các chương kế tiếp, cho nên, trong chương này chúng tôi trình bày các tính chất của bài toán quy hoạch tuyến tính và của tập phương án, tập phương án tối ưu, mà cụ thể là xuất phát từ tập hợp lồi mà ta đã gặp trong một số trường hợp ở phổ thông.

Chương 3. Phương pháp đơn hình và các thuật toán của nó

Xuất phát từ các kién thức ở chương 2, chương này tiến hành xây dựng phương pháp đơn hình. Đây là phương pháp cơ bản nhất  để giải bài toán quy hoạch tuyến tính trong mọi trường hợp chứ không đơn thuần chỉ là bài toán hai biến nữa.

Chương 4. Bài toán quy hoạch tuyến tính đối ngẫu và thuật toán đơn hình đối ngẫu

Chương này, chúng ta đi nghiên cứu một dạng bài toán quy hoạch tuyến tính đó là bài toán quy hoạch tuyến tính đối ngẫu. Đây là bài toán có liên quan mật thiết đến bài toán quy hoạch tuyến tính ban đầu. Đồng thời xuất phát từ mối liên hệ của hai bài toán mà ta có một phương pháp để giải bài toán quy hoạch tuyến tính đó là thuật toán đơn hình đối ngẫu. Đây là một phương pháp giải khá đơn giản mà nếu dùng thuật toán đơn hình thì lại rất phức tạp. 

Chương 5. Bài toán vận tải và thuật toán thế vị

Xuất phát từ bài toán vận chuyển hàng hóa trong thực tế, mà người ta đư ra một bài toán tổng quat đó là bài toán vận tải. Đây cũng là một bài toán quy hoạch tuyến tính nhưng với số biến khá lớn.  Vì số biến khá lớn nên nếu giải bằng thuật toán đơn hình thì sẽ rất phức tạp, chính vì vậy trong chương này ta sẽ nghiên cứu một thuật toán mới đó là thuật toán thế vị, nó khá đơn giản nhưng lại rất hữu hiệu khi giải bài toán này.

%d bloggers like this: