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

Quy hoạch nguyên hay quy hoạch tuyến tính nguyên là quy hoạch tuyến tính với với một số hay toàn bộ các biến là biến nguyên hay rời rạc.

Nếu biến nguyên là biến chỉ có hai giá trị 0 và 1 thì ta gọi là bài toán QHN nhị phân. Nếu toàn bộ các biến đều là biến nguyên thì ta có bài toán QHN thuần túy. Nếu chỉ một số biến nguyên còn lại là biến không nguyên thì ta gọi là bài toán QHN hỗn hợp.

Ứng dụng quy hoạch nguyên thường ở hai dạng trực tiếp hay chuyển đổi. Dạng trực tiếp ở các bài toán mà bản chất các biến là biến nhị phân như chọn hay không chọn dự án hay biến nguyên như xác định số máy tối ưu.

Dạng chuyển đổi thường gặp ở các bài toán mà ban đầu không có biến nguyên nhưng phải thêm các biến nguyên, thường là biến nhị phân thì mới thiết lập được mô hình, chẳng hạn như các bài toán điều độ công việc, bài toán chọn lựa dịch vụ,...

Giải thuật quy hoạch nguyên thường dùng là:

• Giải thuật rẽ nhánh và chận
• Giải thuật mặt phẳng cắt.

TLTK

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