Sách - Quy Hoạch Tuyến Tính Với Phương Pháp Nón Xoay

Giới thiệu Sách - Quy Hoạch Tuyến Tính Với Phương Pháp Nón Xoay

Quy hoạch tuyến tính là một bộ phận có thể nói là quan trọng bậc nhất của Quy hoạch toán học. Nhiều vấn đề thực tế có thể mô tả dưới dạng bài toán quy hoạch tuyến tính. Hơn nữa, các bài toán phi tuyến cũng thường được giải quyết một cách hiệu quả bằng cách xấp xi thông qua quy hoạch tuyến tính.

Một phương pháp quan trọng và rất hiệu quả để giải bài toán

quy hoạch tuyến tính là phương pháp đơn hình, do George Dantzig đề

xuất từ những năm của Thế chiến thứ hai khi giải quyết các bài toán

trong quân đội Mỹ, được mô tả dưới dạng bài toán quy hoạch tuyến tính.

Sau đó vài năm, một phương pháp khác do C.E. Lemke đưa ra, được gọi

là phương pháp đơn hình đối ngẫu, vì phương pháp này thực chất là

phương pháp đơn hình áp dụng trên bài toán đối ngẫu.

Qua nhiều thử nghiệm tính toán, người ta nhận thấy các phương pháp đơn hình và đơn hình đối ngẫu rất có hiệu quả, mặc dù về mặt lý thuyết, các phương pháp này có độ phức tạp mũ. Đến những năm 80 của thế kỷ XX, nhà toán học Nga là Leonid Khachian, và sau đó là nhà toán học Mỹ gốc Ấn Độ là Narendra Karmarkar, đã đưa ra các phương pháp giải bài toán quy hoạch tuyến tính với độ phức tạp đa thức. Gần đây, các phương pháp điểm trong có độ phức tạp đa thức có thể giải được các bài toán quy hoạch tuyến tính cỡ rất lớn. Tuy nhiên, các loại phương pháp đơn hình vẫn được tru dùng do tính hiệu quả và đặc biệt là sự ổn định của loại phương pháp này.

Hiện nay, ở hầu hết các nước trên thế giới cũng như ở Việt Nam, môn Quy hoạch tuyến tính đều được dạy, không những cho sinh viên chuyên ngành Toán, mà cả sinh viên ở các chuyên ngành khác, như kỹ thuật, công nghệ, kinh tế, y khoa... Kinh nghiệm cho thấy, dạy và học