CÁC TRƯỜNG HỢP ĐẶC BIỆT

Nguyễn Như Phong

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

Đại học Bách Khoa TPHCM

Các trường hợp đặc biệt khi sử dụng giải thuật đơn hình giải bài toán QHTT bao gồm:

Suy biến
Tối ưu đa nghiệm
Lời giải không giới hạn
Lời giải không khả thi

a. Suy biến

Khi dùng điều kiện khả thi để tìm biến ra trong giải thuật đơn hình, có thể không tìm được một tỷ số không âm nhỏ nhất duy nhất, có thể tùy chọn biến ra. Trong trường hợp này, có ít nhất một biến cơ bản sẽ bằng 0 trong lần lặp kế tiếp và lời giải mới được xem là lời giải suy biến.

b. Tối ưu đa nghiệm

Khi đường mục tiêu song song với một đường ràng buộc không thừa thì điểm tối ưu là mọi điểm của đoạn thẳng trong vùng khả thi trên đường ràng buộc này, giá trị hàm mục tiêu là như nhau cho mọi điểm của đoạn thẳng này. Lời giải là tối ưu đa nghiệm.

c. Lời giải không giới hạn

Một số mô hình QHTT, có thể có lời giải không giới hạn, cả vùng lời giải và giá trị hàm mục tiêu tối ưu là không có giới hạn. Trong trường hợp này, các biến có thể tăng vô hạn mà không vi phạm mọi ràng buộc, vùng lời giải khả thi là không giới hạn ở ít nhất 1 biến, giá trị hàm mục tiêu có thể tăng vô hạn ở bài toán cực đại hay giảm vô hạn ở bài toán cực tiểu.

d. Lời giải không khả thi

Ở các mô hình có các ràng buộc mâu thuẫn nhau, sẽ không có lời giải khả thi. Bài toán luôn có lời giải khả thi nếu mọi ràng buộc có dạng “£” với vế phải không âm. Lời giải khả thi sẽ được tạo bởi các biến thiếu. Với các ràng buộc dạng “=” hay “³”, ta thường dùng biến nhân tạo để có lời giải khả thi ban đầu. Các biến nhân tạo sẽ về 0 ở lần lặp cuối với phương pháp số lớn hay ở lần lặp cuối pha 1 với phương pháp 2 pha, nếu như mô hình có lời giải tối ưu. Nếu mô hình không có lời giải khả thi thì có ít nhất 1 biến nhân tạo sẽ không về 0 ở lần lặp tối ưu.

TLTK

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