3.3. Phương pháp đơn hình
3.3.2. Dạng đại số của phương pháp đơn hình
Phương pháp đơn hình giải một mô hình QHTT bằng cách lợi dụng 3 tính chất của điểm cực trị khả thi đã được thảo luận trước đó. Thuật toán tìm kiếm sự tối ưu của một mô hình QHTT luôn tuân theo 2 điều kiện cơ
bản: (1) Điều kiện tối ưu và (2) Điều kiện khả thi.
Điều kiện tối ưu đảm bảo rằng không gặp các điểm suy giảm (đối với
điểm nghiệm đang xét). Điều kiện khả thi đảm bảo rằng, bắt đầu với một nghiệm khả thi cơ sở, chỉ có các nghiệm khả thi cơ sở được xem xét trong suốt quá trình tính toán.
Bảng 3.3.1
Các điểm cực trị khả thi của bài toán sản xuất và xử lí chất thải
(x1 x2 s1 s2 s3)
A (0, 0, 10, 4, 0)
B (2, 4, 10, 0, 0)
C (6, 2, 0, 0, 10)
D (5, 0, 0, 2, 10)
Bảng 3.3.2
Bảng đơn hình của bài toán sản xuất và xử lí chất thải Cơ sở x0 x1 x2 s1 s2 s3 Nghiệm
x0 1 -5 1 0 0 0 0
s1 0 2 -1 1 0 0 10
s2 0 0,4 0,8 0 1 0 4
s3 0 -2 1 0 0 1 0
Để giải đại số mô hình QHTT, dạng chính tắc của mô hình có thể được
đặt vào dạng bảng như trong bảng 3.3.2, trong đó hàm mục tiêu được diễn tả như sau:
x0 - 5x1 + x2 - 0s1 - 0s2 -0s3 = 0
Bây giờ bài toán QHTT có thể được giải theo 3 bước của thuật giải đã
được trình bầy trong Mục 3.2.4.
Bước khởi động- phương pháp đơn hình bắt đầu từ một nghiệm khả thi cơ sở bất kỳ. Các biến ảo cho ta một nghiệm xuất phát khả thi bởi vì từ bảng 3.3.2 ta thấy (a) các hệ số ràng buộc của chúng tạo nên một ma trận
đơn vị; và (b) toàn bộ các hệ số vế phải đều không âm (tính chất của dạng chính tắc).
Bước lặp- bước này liên quan đến hai quy trình tính toán dựa trên điều kiện tối ưu và điều kiện khả thi. Quy trình thứ nhất xác định ra một biến khả thi cơ sở mới làm cho giá trị hàm mục tiêu được cải thiện. Phương pháp
đơn hình thực hiện điều này bằng cách lựa chọn một trong số các biến không cơ sở hiện thời để tăng lên trên giá trị 0, biết trước rằng hệ số của nó trong hàm mục tiêu có khả năng cải thiện giá trị hiện thời của x0, Do một
điểm cực trị khả thi trong mô hình QHTT phải có (n-m) các biến không cơ
sở bằng 0, một biến cơ sở hiện thời phải được biến đổi thành không cơ sở, biết trước nghiệm là khả thi. Biến không cơ sở hiện thời bị biến đổi thành cơ sở được gọi là biến vào trong khi biến cơ sở hiện thời bị biến đổi thành không cơ sở được gọi là biến ra.
Đối với một bài toán tối đa hoá, biến vào được lựa chọn dựa trên điều kiện tối ưu, vì biến không cơ sở có hệ số âm lớn nhất trong phương trình x0 ở bảng đơn hình. Điều này là tương đương với việc lựa chọn một biến với hệ số dương lớn nhất trong hàm mục tiêu gốc bởi vì độ lớn của hệ số hàm mục tiêu diễn tả tốc độ thay đổi của hàm mục tiêu do thay đổi một đơn vị giá trị của biến quyết định.
Hệ số có giá trị âm lớn nhất được chọn bởi vì nó có tiềm năng lớn nhất trong việc cải thiện giá trị hàm mục tiêu. Mặt khác, việc lựa chọn biến vào cho bài toán cực tiểu hoá tuân theo quy luật ngược lại. Đó là, lựa chọn biến không cơ sở với hệ số dương lớn nhất trong hàng của hàm mục tiêu trong bảng đơn hình như là biến vào. Khi mà biến vào đã được xác định, một trong số các biến cơ sở hiện thời phải được chọn để trở thành biến không cơ
sở. Sự lựa chọn biến đi ra được thực hiện bằng điều kiện khả thi để chắc chắn rằng chỉ có các nghiệm khả thi được liệt kễ xem xét trong suốt các bước lặp. Biến ra được lựa chọn sử dụng tiêu chuẩn sau:
i i
ik
b
a với mọi aik >0
với aik là các hệ số của các ràng buộc liên quan đến các biến vào xk Biến cơ sở hiện thời nằm trong hàng hàng có θ = min (i) được lựa chọn như là biến ra.
Ví dụ 3.3.1. Dựa trên bảng 3.3.1. lựa chọn biến vào, biến ra cho bước lặp đầu tiên.
Lời giải. Xem xét bảng đơn hình 3.3.2, biến quyết định x1 có thể được lựa chọn như là biến vào.
Hướng liên quan tới biến vào chỉ ra hướng mà theo đó nghiệm tốt hơn có thể tìm được. Xem hình 3.2.1, nó diễn tả sự di chuyển từ nghiệm khả thi cơ sở hiện thời tại điểm A dọc theo chiều dương của trục x1. Di chuyển dọc theo chiều dương của trục x1, có thể tìm thấy hai điểm cực trị D(5,0) và E (10,0). Thực tế, 5 và 10 là giao điểm của hai phương trình ràng buộc thứ nhất và thứ hai với trục x1 dương. hình 3.2.1. cũng chỉ ra rằng điểm E(10,0) là không khả thi cho bài toán. Do vậy, từ điều này thấy rằng di chuyển dọc theo chiều dương của trục x1 từ điểm A chỉ có thể tới điểm D mà không phá hoại các điều kiện khả thi. Các giao điểm của các phương trình ràng buộc với trục chỉ ra hướng tìm kiếm có thể thu được từ bảng đơn hình bằng cách tính tỷ số của các phần tử trong cột nghiệm với các phần tử ràng buộc nằm trong cột tương ứng với biến vào. Xem xét ví dụ được minh họa trong bảng 3.3.2, hai cột được sử dụng để tính toán giao điểm được chỉ ra bên dưới trong bảng 3.3.3 và theo:
1 1
11 2 2
21
10 5 2
4 10
0, 4 b a b a
Tỷ số nhỏ nhất là = min (1, 2) = min (5,10) = 5
Chú ý rằng tỷ số cho ràng buộc cuối cùng không được xác định bởi vì hệ số -2 của cột x1 chỉ ra hướng tìm kiếm theo chiều âm trên trục x1, nó không khả thi bởi vì các biến quyết định yêu cầu không âm. So sánh các giá trị của các giao điểm dương, biến cơ sở có liên quan tới giá trị giao điểm nhỏ nhất, đó là min(5,10) =5, là s1. s1 này sẽ được chọn như là biến ra và trở thành biến không cơ sở
để cho điều kiện khả thi được thỏa mãn. Cho mục đích thảo luận, nếu s2 được chọn là biến ra, sự quyết định sẽ dẫn chúng ta đến điểm E nằm bên ngoài miền nghiệm và nghiệm trở nên không khả
thi.
Khi mà biến vào đã được lựa chọn dựa trên điều kiện tối ưu và biến ra
được lựa chọn theo điều kiện khả thi, trạng thái của các biến trong danh sách biến cơ sở
Bảng 3.3.3
Tính toán giá trị của cho bước lặp 1
TT các ràng buộc x1 Nghiệm
1 2 10 5
2 0,4 4 10
3 -2 0 -
và không cơ sở phải được cập nhất. Sử dụng danh sách các biến mới, các tính toán đưa ra một bảng đơn hình mới. Trong tính toán, chỉ ra trong bảng 3.3.2, nên chú ý rằng các phần tử trong mỗi cột dưới từng biến cơ sở hiện thời có giá trị bằng 1 tại các điểm giao của hàng chứa biến ra và toàn bộ các phần tử khác đều bằng 0, Các biến đổi đại số sau đây được thực hiện để thỏa mãn yêu cầu này.
Các giá trị của các phần tử trong bảng đơn hình liên quan tới các biến cơ
sở và không cơ sở mới có thể được tính toán theo các biến đổi hàng (hay phương pháp giải triệt tiêu Gauss-Jordan). Hàng ràng buộc có liên quan tới biến ra được gọi là phương trình chính và làm cơ sở cho biến đổi hàng này.
Các phần tử nằm tại điểm giao giữa cột đi vào và hàng chính được gọi là phần tử chính. Phương trình chính và phần tử chính đóng vai trò trung tâm trong tính toán. Trong biến đổi hàng, mục tiêu là biến đổi bảng sang dạng
có các phần tử chính bằng một và các phần tử khác bằng không tại bất kỳ
đâu trong cột liên quan tới biến cơ sở mới.
Ví dụ 3.3.2. Xem bảng 3.3.2. thực hiện phép biến đổi chính để cập nhật bảng đơn hình sau khi x1 và s1 được lựa chọn tương ứng là biến vào và biến ra.
Lời giải. Biết rằng x1 là biến vào và s1 là biến ra, phần tử chính trong bảng 3.3.4 là 2, nó được khoanh tròn. Hàng tương ứng với điểm chính này là hàng chính. Biến đổi chính bằng phương pháp triệt tiêu Gauss-Jordan, xem bảng 3.3.4, bao gồm 2 bước sau:
Chia toàn bộ các phần tử trong phương trình chính liên quan tới s2 bởi giá trị của phần tử chính.
áp dụng các phép nhân thích hợp vào hàng chính vừa được sửa đổi ở bước (1) và các hàng khác trong bảng này (xem bảng 3.3.4) sao cho toàn bộ các phần tử khác với phần tử chính trong cột đi vào có giá
trị bằng không.
Bảng đơn hình mới thu được sau các biến đổi trên thể hiện trong Bảng 3.3.5 trong đó danh sách thành viên được cập nhật, s1 được thay thế bởi x1. Các giá trị trong cột nghiệm liên quan tới ba ràng buộc là các giá trị tương ứng với các biến ởc bản hiện thời. Giá trị trong cột nghiệm ở hàng x0 là giá trị của hàm mục tiêu tại điểm nghiệm hiện thời. Với bảng đơn hình hiện thời, nghiệm mới là x1 = 5 và x2 = 0 (do trạng thái không cơ
sở của nó) với giá gị hàm mục tiêu tương ứng x0 = 25. Các giá trị của các biến ảo là không quan trọng trong hoàn cảnh hiện thời vì chúng không có ảnh hưởng tới giá trị của hàm mục tiêu.
Bảng 3.3.4
Minh hoạ các biến đổi hàng
x0 x1 x2 s1 s2 s3 Nghiệm Biến đổi hàng 1 -5 1 0 0 0 0 (+)(x)(5) 0 2 -1 1 0 0 10 (÷)(2) 0 0,4 0,8 0 1 0 4 (+)(x)(-.4) 0 -2 1 0 0 1 0 (+)(x)(2)
Bảng 3.3.5
Kết quả của bước lặp 1
Cơ sở x0 x1 X2 s1 s2 s3 Nghiệm
x0 1 0 -1,5 2,5 0 0 25
s1 0 1 -0,5 0,5 0 0 5
s2 0 0 1 -0,2 1 0 2
s3 0 0 0 1 0 1 10
Trong tính toán thực tế, không cần tính toán các phần tử trong cột chưa các biến cơ sở. Thực ra không phải tất cả các phần tử trong bảng cần tính toán ở mỗi bước lặp. Biến đối hàng được mô tả ở phần trên có thể được sửa
đổi làm tăng tính mềm dẻo để có thể tính toán các giá trị của bất kỳ phần tử nào trong bảng. Giả thiết rằng trong bất kỳ vòng lặp nào của phương pháp
đơn hình, phần tử aij ở hàng i cột j là phần tử chính. Giá trị của phân tử tại giao của hàng k cột l, akl, có thể được tình toán theo:
A’kl = (akl . aij - akj . ail)/ aij (3.3.1) trong đó a’kl là giá trị mới thay thê giá trị cũ akl trong bảng đơn hình trước.
Thông tìn cần được sử dụng trong phương trình (3.3.1) được thể hiện trên h×nh 3.3.1.
Khi một bảng đơn hình mới được tạo ra, cần phải xem xét xem nghiệm tối ưu đã có thể tìm được chưa. Điều này được thực hiện bằng cách kiểm tra các giá trị của các biến không cơ sở hiện thời trong hàng của hàm mục tiêu trong bảng đơn hình. Sử dụng lập luận giống như đã sử dụng ở bước lặp thứ nhất, chúng ra xem xem có các biến không cơ sở còn lại nào có tiềm năng làm tăng thêm giá trị hiện thời của x0, Đối với các bài toán tối đa hoá, bất kỳ một biến không cơ sở nào liên quan đến một hệ số âm trong hàng x0 của bảng đơn hình đều có thể là ứng cử cho biến vào trong vòng lặp tiếp sau.
Nếu trường hợp này xảy ra, bảng đơn hình hiện thời được tối ưu hoá lại sử dụng một quy trình giống như được mô tả ở trên. Nếu tất cả các hệ số mục tiêu ở hàng x0 của bảng đơn hình là không âm, nghiệm tối ưu đã đạt được bởi vì không còn biến nào có tiềm năng làm tăng thêm giá trị của x0,
Xem xét bảng đơn hình hiện thời ta thấy rằng hệ số mục tiêu liên quan tới x2 (một biến không cở sở) trong hàng x0 là -1,5. Điều này chỉ ra rằng nếu tăng giá trị của x2 từ mức không có thể tiếp tục làm tăng giá trị hiện thời của x0 = 25. Do đó x2 được lựa chọn làm biến vào. Để lựa chọn biến ra, các tỷ số giữa các nghiệm của các biến cơ sở hiện thời (x1, s2, s3) với các thành phần trong bảng ở các cột đi vào được tính toán. Biến cơ sở hiện thời liên quan tới tỷ số dương nhỏ nhất được lựa chọn làm biến ra. Có nghĩa là, biến cơ sở hiện thời, tương ứng với min(-,2/1,10/0) = min(-,2,∞) = 2 là biến ra trong vòng lặp thứ hai của phương pháp đơn hình.
Hàng chính là hàng s2 và phần tử chính là 1. Sau các biến đổi hàng, bảng
đơn hình mới được cập nhật trên bảng 3.3.6. Điểm cực trị khả thi liên quan tới bảng này là (x1, x2) = (6, 2) và giá trị của hàm mục tiêu tương ứng, x0, là 28, và lớn hơn giá trị trước đó bằng 25. Xem xét các hệ số mục tiêu ở hàng x0 của bảng ta thấy tất cả các hệ số là không âm. Đối với bài toán cực đại hoá, là trường hợp bài toán sản xuất và xử lí chất thải, nó chỉ ra rằng không có các biến không cơ sở (s1, s2) nào tồn tại có tiềm năng làm tăng tiếp giá trị của hàm mục tiêu.
H×nh 3.3.1
Các biến đổi hàng các phần tử.
Với điều này chúng ra có thể kết luận rằng nghiệm hiện thời (x*1, x*2) = (6, 2), là nghiệm tối ưu và lãi thực tối đa có thể thu được cho người sản xuất x*0 = 28 nghìn đô la.