GIẢI THUẬT QUY HOẠCH NGUYÊN

Nguyễn Như Phong

Kỹ thuật Hệ thống Công nghiệp

Đại học Bách Khoa TPHCM

Giải thuật QHN dựa trên giải thuật QHTT với ba bước như sau:

Bước 1:

Chuyển mô hình QHN thành mô hình QHTT hay chuyển vùng lời giải của bài toán QHN thành vùng lời giải của bài toán QHTT tương ứng bằng cách tháo bỏ các ràng buộc nguyên:

• Với các biến nguyên X, thay các ràng buộc nguyên không âm X Î N⁺ thành các các ràng buộc không âm XÎ R⁺.
• Với các biến nhị phân X, thay các ràng buộc X Î {0,1}thành các ràng buộc XÎ[0,1].

Bước 2:

Giải mô hình QHTT, xác định lời giải tối ưu của mô hình QHTT.

Bước 3:

Từ lời giải tối ưu của mô hình QHTT vừa tìm được, thêm các ràng buộc đặc biệt làm  thay đổi các vùng lời giải của mô hình QHTT nhằm tìm nghiệm nguyên  tối ưu cho bài toán QHN.

Hai phương pháp tạo ra các ràng buộc đặc biệt bao gồm:

• Phương pháp rẽ nhánh và chận
• Phương pháp mặt phẳng cắt

Kinh nghiệm cho thấy phương pháp rẽ nhánh và chận thành công hơn phương pháp mặt phẳng cắt. Phương pháp rẽ nhánh và chận được trình bày ở phần sau.

TLTK

Nguyễn Như Phong. Vận trù xác định. NXBĐHQG. 2010