GIẢI THUẬT QUY HOẠCH MỤC TIÊU

Nguyễn Như Phong

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

Đại học Bách Khoa TPHCM

Mô hình QHMT là mô hình tối ưu đa mục tiêu, các giải thuật QHMT chuyển bài toán đa mục tiêu về bài toán đơn mục tiêu bằng những phương pháp khác nhau.

Các phương pháp thường dùng là:

Phương pháp trọng số
Phương pháp ưu tiên.

Các phương pháp này là khác nhau nên cho lời giải có thể khác nhau. Không phương pháp nào vượt trội phương pháp nào, việc chọn phương pháp phụ thuộc vào ‎người ra quyết định.

1. Phương pháp trọng số

Mô hình QHMT có n mục tiêu:

Min G_i , i = 1,…, n

Phương pháp trọng số tích hợp n mục tiêu trên thành một mục tiêu duy nhất:

Trong đó W_i ³ 0 là trọng số của mục tiêu thứ i. Các trọng số này thường đựơc chọn lựa bởi người ra quyết định theo mức độ quan trọng của mục tiêu. Các trọng số thường được chuẩn hóa:

2. Phương pháp ưu tiên

Phương pháp ưu tiên xếp hạng ưu tiên các mục tiêu theo mức độ quan trong. Với bài toán có n mục tiêu, thứ tự ưu tiên của các mục tiêu được xếp hạng như sau:

Min G₁ – ưu tiên cao nhất

…

Min G_n – ưu tiên thấp nhất

Giải thuật tối ưu mỗi lúc một mục tiêu, bắt đầu từ mục tiêu có độ ưu tiên cao nhất G₁, tiếp theo là các mục tiêu có độ ưu tiên thấp hơn và cuối cùng là mục tiêu có độ ưu tiên thấp nhất G_n. Lời giải từ bài toán tối ưu hóa một mục tiêu sẽ không làm ảnh hưởng lời giải của bài toán tối ưu hóa mục tiêu có múc ưu tiên cao hơn.

a. Phương pháp thêm ràng buộc

Giải thuật ưu tiên gồm các bước sau:

Bước 0:

Xác định mức độ ưu tiên của các mục tiêu,

G₁ > G₂ > … > G_n ( >: ưu tiên hơn).

Đặt i=1

Bước i:

Giải bài toán đơn mục tiêu QHTT thứ i với mục tiêu Min G_i
Xác định kết quả tối ưu G_i*
Nếu i = n . Dừng
Nếu i < n
- Thêm vào ràng buộc G_i = G_i*
- Đặt i = i + 1, quay về bước i.

b. Phương pháp bỏ biến

Khi đã có được kết quả ở 1 bước, ta có thể thay kết quả này vào mô hình để tạo mô hình mới cho bước sau thay vì thêm vào ràng buộc. Giải thuật ưu tiên gồm các bước sau:

Bước 0: