3.2. Các thuật giải cho quy hoạch tuyến tính
3.2.3. Thuật giải cho các bài toán quy hoạch tuyến tính
ở mục này ba tính chất quan trọng của điểm cực trị khả thi thảo luận trước đây sẽ được ứng dụng vào một bài toán QHTT và một thuật giải sẽ
được thiết kế để giải bài toán QHTT này. Chúng ta quay lại bài toán sản xuất, xử lí chất thải trước đây. Như được mô tả ở hình 3.2.1, mô hình QHTT có bốn điểm cực trị khả thi. Đầu tiên, ta phải xác định điểm xuất phát cho việc tìm kiếm nghiệm tối ưu. Hiển nhiên là nếu điểm xuất phát gần với
điểm tối ưu, ta có thể hy vọng việc tìm kiếm nghiệm sẽ nhanh hơn. Tuy nhiên, nhìn chung là rất khó có thể xác định ngay từ đầu một điểm xuất phát tốt, đặc biệt là cho các bài toán nhiều chiều. Do vậy, sẽ là hợp lý nếu bắt đầu việc tìm kiếm từ điểm ở gốc tọa độ (x1, x2) = (0,0) vì điểm gốc là một điểm cực trị khả thi, chú ý rằng trong công việc tìm kiếm nghiệm tối
ưu, luôn cần thiết bắt đầu với một nghiệm khả thi.
Khi đã xác định được điểm xuất phát cực trị khả thi, giá trị của hàm mục tiêu tương ứng x0 sẽ được tính để làm cơ sở cho các bước so sánh tiếp theo.
Trong trường hợp này, tại điểm (0,0), giá trị x0 tương ứng bằng 0, Bước tiếp theo là tìm một nghiệm tốt hơn bằng cách so sánh các giá trị của các hàm mục tiêu tại các điểm cực trị khả thi bên cạnh. Hai điểm cực trị khả thi bên cạnh điểm (0, 6) là B (2, 4) và D (5, 0) với các giá trị tương ứng của hàm mục tiêu lần lượt là 6 và 25. Kết quả này chỉ ra rằng sự dịch chuyển từ điểm A đến D đạt được sự cải thiệt tốt hơn so với từ A đến B. Do vậy, điểm D trở thành điểm cực trị khả thi cơ sở.
Tại điểm D, quá trình so sánh được lập lại bằng cách xác định các điểm cực trị khả thi nằm bên cạnh điểm D. Trong trường hợp này, hai điểm A và C là hai điểm tiếp giáp. Tuy nhiên từ so sánh trước đây, giá trị hàm mục tiêu tại A không tốt hơn giá trị tại điểm hiện tại D. Do vậy điểm C là điểm cực trị khả thi cần được so sánh với điểm D. Tại điểm C (6, 2) giá trị x0 bằng 5(6) - 1(2)=28. Do giá trị này lớn hơn 25 tại điểm D, điểm cực trị khả
thi cơ sở được thay bằng điểm C. Tại điểm cực trị khả thi cơ sở C, không còn điểm cực trị khả thi tiếp giáp nào để so sánh (điểm B đã được so sánh và loại bỏ bởi điểm D trong bước trước đây). Giá trị của x0 tại điểm C là tốt hơn so với tất cả các điểm CTKT bên cạnh (điểm B và D). Từ tính chất thứ ba của các điểm CTKT thảo luận trước đây, ta có thể kết luận rằng nghiệm
tối ưu của ví dụ sản xuất, xử lí chất thải là sản xuất 6 đơn vị thành phẩm và
đổ trược tiếp hai đơn vị chất thải ra sông mà không qua xử lí. Điều đó cũng có nghĩa là có 2(6) - 2=10 đơn vị chất thải đi qua nhà máy xử lí. Giá trị lãi ròng tương ứng là 28 nghìn đô la.
Các bước được mô tả trên đây (sử dụng 3 tính chất của các điểm CTKT
để giải một mô hình QHTT) hình thành khái niệm về một thuật giả nổi tiếng được gọi là Phương pháp đơn hình (Simplex method). Phương pháp này là một quy trình tổng quát để giải các bài toán QHTT. Nó là một phương pháp rất hiệu quả đã được áp dụng để giải các bài toán lớn hơn liên quan đến hàng trăm các biến quyết định và ràng buộc trên máy tính điện tử.
Các chương trình máy tính dựa trên phương pháp đơn hình có mặt rộng rãi
để sử dụng.
Ví dụ 3.2.2. Giải bằng phương pháp đại số bài toán sản xuất, xử lí chất thải của ví dụ 3.2.1.
Lời giải. Hàm mục tiêu và các ràng buộc có thể được viết như sau:
Hàm mục tiêu: x0 - 5x1 + x2 + 0s1 + 0s2 + 0s3 = 0 Ràng buộc 1: 2x1 - x2 + s1 + 0s2 + 0s3 = 10 Ràng buộc 2: 0,4x1 +0,8x2 + 0s1 + s2 + 0s3 = 4 Ràng buộc 3: -2x1 + x2 + 0s1 + 0s2 + s3 = 0 Bước đầu tiên bắt đầu với điểm CTKT (x1= 0 và x2 = 0) Bước lặp 1
Bước lặp bắt đầu bằng việc lựa chọn hoặc biến x1 hoặc biến x2 nên tăng giá từ giá trị 0, Do x1 có hệ số
âm lớn nhất (-5) nên nó sẽ có tác động lớn nhất cho việc làm tăng hàm mục tiêu. Quyết định tiếp theo là cần tăng x1 lên bao nhiêu. Cần nhớ rằng các biến ảo không bao giờ có giá trị âm. Đầu tiên kiểm tra ràng buộc 1 bằng cách tìm giá trị x1 với s1 = 0 và x2 = 0,
2 1
1
10 5
2 2 2
x s x
Sau đó thay x1 = 5 vào các ràng buộc còn lại và tìm giá trị các biến ảo.
Ràng buộc 2: 0,4 (5) + 0,8 (0) + 0s1 + s2 + 0s3 = 4 s2 = 2 Ràng buộc 3: -2(5) + 0 + 0s1 + 0s2 + s3 = 0 s3 = 10
Vì các biến ảo vẫn giữ giá trị dương với x1 = 5. Ta xét ràng buộc 2 và tìm giá trị của x1 với x2 = 0 và s2 = 0,
Ràng buộc 2: 0,4x1 + 0,8 (0) + 0s1 + 0 + s3 = 4 x1 = 10 Bây giờ chúng ta đi kiểm tra ràng buộc 1 và 3
Ràng buộc 1: 2(10) - 0 + s1 + 0s2 + 0s3 = 10 s1 = -10 Ràng buộc 3: -2(10) + 0 + 0s1 + 0s2 + s3 = 0 s3 = 20
Đối với ràng buộc 1, x1 = 10 là quá lớn vì biến ảo s1 mang giá trị âm (s1 = -10). Tiếp theo, xét ràng buộc 2 và tìm giá trị x1 với x2 = 0 và s3 = 0,
Ràng buộc 3: -2x1 + 0s1 + 0s2 + 0 = 0 x1 = 0
Điều này nói lên rằng nó không di chuyển khỏi vị trí xuất phát.
Kết quả của sự phân tích trên cho ta thấy giá trị lớn nhất của x1 có thể tăng được là x1 = 5, với x2 = 0, s2 = 2, s3 = 10, Nhìn lại hình 3.2.2, điểm này chính là điểm D. Giá trị hàm mục tiêu x0 tương ứng với nghiệm khả thi tại điểm D là:
x0 - 5(5) + 0 + 0s1 + 0s2 + 0s3 = 0 x0 = 25 Tiếp đến,
2 1
1 5
2 2
x s x
được thay thế vào hàm mục tiêu và các ràng buộc.
Hàm mục tiêu:
2 1
0 5(5 2 01 0 2 0 3 0
2 2
x s
x x s s s
0 2 1 2 3
3 5
0 0 25
2 2
x x s s s
Ràng buộc 1: 1 2 1 2 3
1 1
0 0 5
2 2
x x s s s
Ràng buộc 2: 0, 4(5 2 1) 0, 8 2 0 1 2 0 3 4
2 2
x s
x s s s
1 2 1 2 3
0x s 0.2s s 0s 2
Ràng buộc 3:
2 1
2 1 2 3
2(5 ) 0 0 0
2 2
x s
x s s s
1 2 1 2 3
0x 0x s 0s s 10 Bước lặp 2.
Bước lặp thứ 2 này bắt đầu bằng việc định nghĩa xem biến nào nên được tăng lên từ giá trị 0, Hàm mục tiêu từ trên có dạng:
0 2 1 2 3
3 5
0 0 25
2 2
x x s s s
Hệ số âm lớn nhất là -3/2 của x2. Do đó x2nên tăng từ 0 để làm tăng giá trị hàm mục tiêu.
Câu hỏi tiếp theo là cần tăng x2bao nhiêu.
Ràng buộc 1: x2= 2x1-10 Nếu x1và x2>0 thì s1=0 Ràng buộc 2: x2
= 2 + 0,2s1-s2 Nếu x1và x2>0 thì s2=0 x2
= 2
Ràng buộc 3: 0x1+ 0x2+ 0 +0s2 + s3 = 10, do đó s3 = 10
Thay x2=2 từ ràng buộc 2 vào ràng buộc 1, x2= 2x1-10, ta có x1=6. Đối với hàm mục tiêu ta thay
2 2
x vào, có:
0 1 2 1 2 3
0 1 2 1 2 3
0 1 2 3
0 1 2 1 2 3
3 5
(2 0, 2 ) 0 0 25
2 2
3 5
3 0, 3 0 0 25
2 2
2, 2 3 0 28
2
0 0 2, 2 1, 5 0 25
x s s s s s
x s s s s s
x s s s
x x x s s s
Cả x1và x2có hệ số 0, do vậy không thể thay đổi giá trị x1và x2 thêm nữa để tăng giá trị hàm mục tiêu.