Quy hoạch tuyến tính (Linear programming) là dạng bài toán cơ bản nhất trong tối ưu hóa. Trong phần 3, chúng ta đã biết cách dùng bảng để áp dụng thuật toán đơn hình (simplex algorithm). Tuy nhiên, vẫn còn một số vấn đề chưa được giải quyết như:
Để giải quyết những câu hỏi trên, trong phần này, chúng ta sẽ mở rộng thuật toán trong phần 3 thành thuật toán đơn hình hai pha (two-phase simplex method). Các bài khác trong loạt bài: Trong phần 3, chúng ta may mắn vì bài toán ví dụ chỉ chứa toàn những bất đẳng thức. Do đó, khi thêm biến bù (slack variable), tập hợp các biến bù đã trở thành cơ sở ban đầu. Tuy nhiên, nếu bài toán có những ràng buộc dạng đẳng thức như: Bài toán này tuy giống với bài toán ví dụ sử dụng trong ba phần trước, ràng buộc thứ ba đã thay thế dấu thành dấu . Ràng buộc đó đại diện cho số lượng nhím biển. Sử dụng dấu bằng thay cho dấu tức chúng ta phải sử dụng đúng 18 con nhím biển, không dư không thiếu. Chúng ta có nhiều cách để xử lý dấu bằng này:
Trong thuật toán đơn hình hai pha, chúng ta sẽ giải bài toán trong hai bước, mỗi bước đều sử dụng lại thuật toán đơn hình trong phần 3. Trong pha 1 (phase 1), chúng ta đổi bài toán sang dạng chuẩn và thêm một biến ảo (artificial variable) không âm vào mỗi ràng buộc. Đồng thời, hàm mục tiêu sẽ tạm thay bằng tổng của các biến ảo đó. Chúng ta có là các biến bù như trong các phần trước, là các biến ảo mới được thêm vào. Hàm mục tiêu trở thành tổng của 3 biến ảo. Lưu ý, lần này chúng ta không có biến bù do chúng ta đã thay dấu bằng vào (biến bù chỉ dùng để bù vào phần thiếu trong bất đẳng thức). Chúng ta cũng đã thay bằng để phân biệt pha 1 và pha 2 ( sẽ được dùng trong pha 2 để biểu diễn giá trị của bài toán gốc). Trong bài toán mới này, ta chú ý rằng nếu bài toán gốc có nghiệm, thì các biến ảo đều phải bằng 0. Điều này có nghĩa là nếu có giá trị tối ưu bằng 0 thì bài toán có nghiệm, lớn hơn 0 thì bài toán vô nghiệm. không thể âm hay không có cận (unbounded), bởi vì mỗi biến ảo đều không âm nên tổng của chúng cũng không âm. Chúng ta có thể đặt cơ sở ban đầu cho bài toán pha 1 này là , tuy nhiên, chúng ta có thể bỏ và đi bởi vì và có thể được sử dụng như các biến cơ sở như ở phần trước. Như vậy, ta có cơ sở ban đầu là và bài toán pha 1 trở thành: Lưu ý: Mặc dù bài toán này trông có vẻ giống bài toán ở phần 3 (thay thành ), tuy nhiên hàm mục tiêu của bài toán này là thay vì nên kết quả sẽ khác nhau. Ở dạng bảng: Chúng ta sử dụng thuật toán đơn hình ở phần 3 để giải bài toán này. Bước 0: khử hệ số hàng cuối của biến cơ sở thành 0. Ta sẽ lấy hàng trừ đi hàng để khử hệ số này (lưu ý, không làm ngược lại, phải luôn lấy hàng cần khử cộng hay trừ đi bội của hàng khác): Trong hàng cuối, có hệ số âm nhất (-3) nên sẽ trở thành biến vào cơ sở. có tỉ số giữa vế phải và cột nhỏ nhất (18/3 = 6) nên sẽ trở thành biến rời cơ sở. Xoay bảng quanh hàng và cột , ta có: Khi tất cả các biến ảo trở thành biến ngoài cơ sở (bằng 0), ta kết thúc pha 1. Sau pha 1, chúng ta đã có một cơ sở ban đầu là . Trong pha 2, chúng ta sẽ giải bài toán gốc sử dụng cơ sở ban đầu này. Ta sẽ tái sử dụng bảng trên vào pha 2. Đầu tiên, ta bỏ cột của các biến ảo đi (cột ). Sau đó, ta thay hàng cuối bằng hàm mục tiêu gốc để có được: Một lần nữa, ta cần khử hệ số hàng cuối của các biến cơ sở thành 0 (hệ số của ). Chúng ta sẽ cộng hàng với 6 lần hàng để có: Biến vào cơ sở sẽ là , biến rời cơ sở là (tỉ số 12/4 = 3 nhỏ nhất). Xoay quanh cột và hàng , ta được: Như vậy, chúng ta có đáp án là , và số nhím biển sử dụng là đúng bằng 18. Tuy đáp án này giống đáp án trong phần trước, tuy nhiên hai bài toán là hoàn toán khác nhau. Bài toán phần 3 có thể sử dụng số nhím biển ít hơn 18, trong khi bài toán phần này bắt buộc phải đúng 18. Miền khả thi (feasible region) của bài toán này chỉ là đoạn thẳng nối từ (0,6) tới (3,5) thay vì nguyên hình hình tứ giác như ở phần 1. Sử dụng thuật toán đơn hình hai pha, chúng ta có thể biết được liệu một bài toán có vô nghiệm hay không (có miền khả thi rỗng). Chúng ta sẽ sử dụng lại bài toán ở phần trên nhưng thay bất đẳng thức thứ hai thành đẳng thức (tức chúng ta phải sử dụng đúng 24 con tôm. Chúng ta có thể kiểm tra nhanh rằng bài toán này là vô nghiệm: đường thẳng và chỉ cắt nhau tại một điểm duy nhất nhưng nếu chúng ta thay điểm này vào ràng buộc đầu tiên, ta thấy . Không phải mọi bài toán có thể kiểm tra bằng cách này, do đó chúng ta phải sử dụng thuật toán đơn hình hai pha. Trong pha 1, chúng ta bắt đầu với việc thêm các biến ảo cho ràng buộc 2 và 3: Lưu ý: không nằm trong hàm mục tiêu bởi vì là biến phụ để chuyển bất đẳng thức thành đẳng thức, không phải là biến ảo (chỉ dùng trong pha 1). Dạng bảng của bài toán: Cơ sở ban đầu là . Chúng ta phải khử hệ số hàng cuối của các biến cơ sở thành 0: là biến vào cơ sở, là biến rời cơ sở. Ta xoay cột và hàng để có: là biến vào cơ sở, là biến rời cơ sở. Ta xoay cột và hàng : Hàng cuối không có hệ số âm, pha 1 kết thúc với và hàm mục tiêu . Mỗi khi pha 1 kết thúc với , bài toán đó vô nghiệm. Nếu bài toán đó có nghiệm, nó phải có ít nhất một nghiệm cơ bản và do đó, . Ta tổng hợp lại phương pháp giải bài toán quy hoạch tuyến tính như sau:
Một bài toán quy hoạch tuyến tính chỉ có 3 kết luận: có nghiệm tối ưu, không có cận, hoặc vô nghiệm. Ngoài ra, pha 1 không thể kết thúc mà không có cận, bởi vì là tổng các biến ảo đều không âm nên 0 là giá trị nhỏ nhất mà có thể đạt được. Trong phần này, chúng ta đã biết được làm thế nào để tìm ra cơ sở ban đầu và kiểm tra nếu một bài toán có vô nghiệm hay không. Sử dụng thuật toán đơn hình 2 pha, các bạn có thể giải bất kỳ một bài toán quy hoạch tuyến tính nào. Trong các phần tiếp theo, chúng ta sẽ khám phá về những tính chất quan trọng của bài toán quy hoạch tuyến tính: đối ngẫu và tính chất bù bổ sung. Cảm ơn bạn đã theo dõi. Sách tham khảo: Luenberger, David G., and Yinyu Ye. Linear and Nonlinear Programming. Springer, 2008. |
