GIẢI THUẬT RẼ NHÁNH & CHẬN BBA

Nguyễn Như Phong

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

Đại học Bách Khoa TPHCM

a. Bài toán cực đại

Giải thuật rẽ nhánh và chận cho bài toán QHN thuần túy dạng cực đại bao gồm các bước sau:

Bước 0:

• Đặt cận dưới của giá trị hàm mục tiêu tối ưu z = -∞
• Đặt i=1

Bước 1: Khảo sát bài toán con và chận.

• Chọn khảo sát bài toán QHN_i
• Xác định và giải bài toán QHTT_i tương ứng.
• Bài toán QHN_i được xem là đã khảo sát xong khi thỏa 1 trong 3 điều kiện sau:
  • QHTT_i không có lời giải khả thi. QHN_i không có lời giải.
  • QHTT_i có lời giải tối ưu với giá trị hàm mục tiêu thấp hơn cận dưới hiện tại. Không tìm được lời giải tốt hơn ở  bài toán QHN_i
  • QHTT_i cho lời giải nguyên tối ưu lớn hơn cận dưới hiện tại. Lời giải của QHN_i là lời giải tối ưu hiện tại, cận dưới của của giá trị hàm mục tiêu tối ưu được cập nhật theo lời giải này.
• Nếu khảo sát xong QHN_i:
  • Nếu mọi bài toán con đã được khảo sát. Dừng
  • Nếu vẫn còn bài toán con chưa được khảo sát.
    • Đặt i=i+1
    • Quay lại bước 1
• Nếu chưa khảo sát xong QHN_i, sang bước 2

Bước 2: Rẽ nhánh

• Chọn 1 biến nguyên x_k có giá trị không nguyên x_k* ở lời giải tối ưu của QHTT_i
• Xây dựng 2 bài toán con QHN từ bài toán QHN_i bằng cách thêm vào bài toán QHN_i một trong hai ràng buộc sau:
  • x_k £ [x_k*], Với [x_k*] là giá trị nguyên lớn nhất, nhỏ hơn x_k*
  • x_j ³ [x_k*] + 1
• Đặt i=i+1, quay lại bước 1

a. Bài toán cực tiểu

Giải thuật Rẽ nhánh và chận cho bài toán QHN thuần túy dạng cực tiểu bao gồm các bước sau:

Bước 0:

• Đặt cận trên của giá trị hàm mục tiêu tối ưu z = +∞
• Đặt i=1

Bước 1: Khảo sát bài toán con và chận.

• Chọn khảo sát bài toán QHN_i
• Xác định và giải bài toán QHTT_i tương ứng.
• Bài toán QHN_i được xem là đã khảo sát xong khi thỏa 1 trong 3 điều kiện sau:
  • QHTT_i không có lời giải khả thi. QHN_i không có lời giải.
  • QHTT_i có lời giải tối ưu với giá trị hàm mục tiêu cao hơn cận trên hiện tại. Không tìm được lời giải tốt hơn ở  bài toán QHN_i
  • QHTT_i cho lời giải nguyên tối ưu nhỏ hơn cận trên hiện tại. Lời giải của QHN_i là lời giải tối ưu hiện tại, cận trên của của giá trị hàm mục tiêu tối ưu được cập nhật theo lời giải này.
• Nếu khảo sát xong QHN_i:
  • Nếu mọi bài toán con đã được khảo sát. Dừng
  • Nếu vẫn còn bài toán con chưa được khảo sát.
    • Đặt i=i+1
    • Quay lại bước 1
• Nếu chưa khảo sát xong QHN_i, sang bước 2

Bước 2: Rẻ nhánh

• Chọn 1 biến nguyên x_k có giá trị không nguyên x_k* ở lời giải tối ưu của QHTT_i
• Xây dựng hai bài toán con QHN từ bài toán QHN_i bằng cách thêm vào bài toán QHN_i một trong hai ràng buộc sau:
  • x_k £ [x_k*], Với [x_k*] là giá trị nguyên lớn nhất, nhỏ hơn x_k*
  • x_j ³ [x_k*] + 1
• Đặt i=i+1, quay lại bước 1

c. Bài toán hỗn hợp

Giải thuật Rẽ nhánh và chận trên vẫn áp dụng cho bài toán QHN hỗn hợp có biến không nguyên, trong trường hợp này ta sẽ khi chọn biến rẻ nhánh, ta không chọn các biến không nguyên.

TLTK

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