Phương pháp biến giả cải biên
Cải biên bài toán quy hoạch tuyến tính Người ta có thể biến đổi một bài toán quy hoạch tuyến tính chính tắc thành dạng chuẩn bằng cách cộng một cách phù hợp vào vế trái của ràng buộc i một biến giả x n+i ≥ 0 để làm ...
Cải biên bài toán quy hoạch tuyến tính
Người ta có thể biến đổi một bài toán quy hoạch tuyến tính chính tắc thành dạng chuẩn bằng cách cộng một cách phù hợp vào vế trái của ràng buộc i một biến giả xn+i ≥ 0 để làm xuất hiện ma trận đơn vị. Vì các biến giả cải biên có ảnh hưởng đến hàm mục tiêu nên cũng sẽ có sự cải biên hàm mục tiêu.
Vậy, người ta có thể biến đổi bài toán quy hoạch tuyến tính tổng quát, gọi là bài toán xuất phát, thành bài toán dạng chuẩn, gọi là bài toán cải biên (mở rộng)
Ví dụ :
Biến đổi bài toán quy hoạch tuyến tính sau đây thành dạng chuẩn
Bài toán xuất phát có các biến, ma trận ràng buộc và chi phí :
Bằng cách thêm biến giả x5, x6 lần lượt vào ràng buộc 2 và 3 . Ta được bài toán cải biên :
z'(x) size 12{ { {z}} sup { ' } ( x ) } {} là hàm mục tiêu cải biên sẽ được giải thích trong phần tiếp theo.
Các biến, ma trận ràng buộc các hệ số và chi phí của bài toán cải biên là
Quan hệ giữa bài toán xuất phát và bài toán cải biên
Người ta kiểm chứng rằng :
- Nếu xT=[x1x2...xn] size 12{x rSup { size 8{T} } = [ x rSub { size 8{1} } " "x rSub { size 8{2} } " " "." "." "." " "x rSub { size 8{n} } ] } {} là phương án (tối ưu) của bài toán xuất phát thì x¯T=[x1x2...xn 0 0 ... 0] size 12{ {overline {x}} rSup { size 8{T} } = [ x rSub { size 8{1} } " "x rSub { size 8{2} } " " "." "." "." " "x rSub { size 8{n} } " 0 0 " "." "." "." " 0" ] } {} là phương án (tối ưu) của bài toán cải biên tương ứng.
Vậy nếu bài toán cải biên không có phương án tối ưu thì bài toán xuất phát cũng sẽ không có phương án tối ưu.
- Nếu x¯T=[x1x2...xn 0 0 ... 0] size 12{ {overline {x}} rSup { size 8{T} } = [ x rSub { size 8{1} } " "x rSub { size 8{2} } " " "." "." "." " "x rSub { size 8{n} } " 0 0 " "." "." "." " 0" ] } {} là phương án tối ưu của bài toán cải biên thì xT=[x1x2...xn] size 12{x rSup { size 8{T} } = [ x rSub { size 8{1} } " "x rSub { size 8{2} } " " "." "." "." " "x rSub { size 8{n} } ] } {} là phương án tối ưu của bài toán xuất phát
- Nếu bài toán cải biên có một phương án tối ưu mà trong đó có ít nhất một biến giả có giá trị dương thì bài toán xuất phát không có phương án tối ưu.
- Nếu bài toán cải biên (dạng chuẩn) có phương án tối ưu thì cũng sẽ phương án cơ sở tối ưu.
Ví dụ
1- Xét bài toán :
Bài toán cải biên không có phương án tối ưu nên bài toán xuất phát cũng không có phương án tối ưu .
2- Xét bài toán :
Phương án tối ưu của bài toán cải biên :
Phương án tối ưu của bài toán xuất phát :
3- Xét bài toán :
Phương án tối ưu của bài toán cải biên :
Bài toán xuất phát không có phương án tối ưu .
Hai phương pháp biến giả cải biên thương dùng là phương pháp hai pha và phương pháp M vô cùng lớn .
Pha 1
Tìm phương án tối ưu cho bài toán cải biên với hàm mục tiêu cải biên là :
min (tổng tất cả biến giả cải biên)
Pha 2
Tìm phương án tối ưu cho bài toán xuất phát với phương án cơ sở khả thi xuất phát là phương án tối ưu tìm được ở pha 1. Ở pha 2 này các biến giả cải biên bị loại ra khỏi ma trận các hệ số ràng buộc, và vectơ chi phí được cập nhật lại, do đó dấu hiệu tối ưu cũng được cập nhật lại
Đây là phương pháp thuận lợi cho việc lập trình ứng dụng giải thuật đơn hình cải tiến.
Ví dụ : Xét bài toán quy hoạch tuyến tính
Đưa bài toán về dạng chính tắc bằng cách thêm biến phụ x4 , x5 ta được
Pha 1
Thêm biến giả (cải biên ) x6 ≥ 0 vào ràng buộc thứ hai để được ma trận đơn vị . Khi đó bài toán cải biên có dạng :
Pha 2
Loại bỏ biến giả cải biên x6 ≥ 0
Khởi tạo
Kết quả của bài toán đã cho :
. Phương án tối ưu 
. Giá trị hàm mục tiêu z(x)=z(x3)= 8
Phương pháp M vô cùng lớn ( M là số vô cùng lớn ) tương tự như phương pháp hai pha, ngoại trừ ở pha 1 hàm mục tiêu cải biên có dạng sau đây cho bài toán max/min
max [z(x) - M*( tổng các biến giả cải biên) ]
min [z(x) + M*( tổng các biến giả cải biên) ]
Bằng phương pháp này, trong quá trình tối ưu, các biến giả cải biên sẽ được loại dần ra khỏi ma trận cơ sở : tất cả đều bằng 0. Nếu trong quá trình tìm phương án tối ưu mà không loại bỏ được các biến giả cải biên ra khỏi cơ sở thì bài toán vô nghiệm.
So với phương pháp hai pha thì phương pháp này tránh được việc phải cập nhật lại dữ liệu cho bài toán gốc nhưng không tiện lợi bằng trong lập trình ứng dụng.
Ví dụ : Xét bài toán tương tự như trên
Tìm phương án tối ưu cho bài toán cải biên này bằng phương pháp đơn hình cải tiến
Khởi tạo
Do x6 = 0 (vì ngoài cơ sở) nên bị loại ra khỏi bảng và ta tiếp tục tìm phương án tối ưu cho bài toán gốc đã cho có phương án cơ sở khả thi được khởi tạo như sau :
Các bước tiếp theo được thực hiện giống như phương pháp hai pha.
