7. BỐN TRƯỜNG HỢP ĐẶC BIỆT TRONG QUY HOẠCH TUYẾN TÍNH (PHƯƠNG PHÁP ĐỒ THỊ)
7.1. Khơng khả thi (Infeasibility)
Khơng khả thi là 1 tình huống xảy ra khi khơng cĩ lời giải nào của bài tốn QHTT thỏa mãn tất cả các ràng buộc đã cho, kể cả các ràng buộc các biến khơng âm xi≥0. Nghĩa là trên đồ thị sẽ khơng xác định được miền nghiệm khả thi, nĩi cách khác, khơng cĩ điểm nào thỏa mãn tất cả các điều kiện ràng buộc một cách đồng thời. Đây là một tình huống xảy ra nếu bài tốn được thành lập với các ràng buộc mâu thuẫn với nhau. Điều này rất hay xảy ra trong các bài tốn thực tế phức tạp cĩ kích thước lớn, bao gồm hàng trăm đến hàng nghìn ràng buộc.
Khơng khả thi khơng phụ thuộc vào hàm mục tiêu. Vì vậy khi gặp phải trường hợp này, nếu chúng ta thay đổi các hệ số trong hàm mục tiêu thì bài tốn vẫn khơng khả thi.
Ví dụ 1:
+ Nếu 1 ràng buộc cung cấp bởi bộ phận tiếp thị (Giám đốc Marketing) là yêu cầu sản xuất ít nhất 300 cái bàn (x1 ≥ 300) để đáp ứng nhu cầu của thị trường.
+ Trong khi đĩ, 1 ràng buộc khác cung cấp từ bộ phận sản xuất (Giám đốc sản xuất) là chỉ cĩ thể sản xuất nhiều nhất là 220 cái bàn (x1 ≤ 220) do khơng đủ nguyên liệu gỗ.
Trong trường hợp này lời giải khơng khả thi xuất hiện.
Hướng giải quyết:
+ Xem lại đầu vào: Thêm tài nguyên. Ví dụ: Mua thêm gỗ nguyên liệu từ nhà cung cấp khác để đáp ứng nhu cầu sản xuất.
+ Thay đổi đầu ra: Cĩ thể thay đổi cơ cấu sản phẩm. Ví dụ: Cung cấp các loại bàn khác để thay thế.
Ví dụ 2: Xem xét 3 ràng buộc sau: x1 + 2x2 ≤ 6
x1 ≥ 7
Do 3 ràng buộc này mâu thuẫn nhau nên khơng cĩ lời giải khả thi cho bài tốn trên.
Hình 4.11. Khơng cĩ lời giải khả thi 7.2. Lời giải khơng bị chặn (Unboundedness)
Đơi khi, bài tốn QHTT sẽ khơng cho ta lời giải hữu hạn. Điều này cĩ nghĩa là trong bài tốn QHTT cực đại hĩa, gồm cĩ một hay nhiều biến, giá trị của hàm mục tiêu (lợi nhuận) cĩ thể tiến đến lớn vơ cùng mà khơng vi phạm bất cứ ràng buộc nào cả. Nếu chúng ta giải bài tốn loại này bằng phương pháp đồ thị, chúng ta sẽ thấy miền nghiệm khả thi là một miền mở khơng giới hạn (open-ended)→ Bài tốn mở. Ngược lại, trong bài tốn QHTT cực tiểu hĩa, giá trị của hàm mục tiêu (chi phí) cĩ thể tiến đến nhỏ vơ cùng mà khơng vi phạm bất cứ ràng buộc nào cả.
Trường hợp lời giải khơng bị chặn cịn được diễn tả bởi thuật ngữ
quản lý khơng tưởng (managerial utopia), bởi vì nếu nĩ xảy ra, nhà quản lý sẽ thu được lợi nhuận khơng giới hạn hay chi phí khơng đáng kể. Tuy nhiên, trong các mơ hình QHTT thực tế, nếu gặp phải hiện
tượng lời giải khơng bị chặn thì cĩ nghĩa là chúng ta đã thành lập khơng chính xác bài tốn QHTT. Thơng thường nhất là thiếu một hay nhiều ràng buộc khi thành lập mơ hình tốn. Đơi khi, một sự thay đổi hệ số trong hàm mục tiêu cĩ thể làm cho bài tốn QHTT khơng bị chặn trở thành bài tốn QHTT bị chặn và cĩ một lời giải tối ưu. Ví dụ: Hàm mục tiêu: Max Z = 20x1 + 10x2
Ràng buộc: x1≥2 và x2≥5 là mơ hình tốn cĩ lời giải khơng bị chặn Nếu chúng ta thay hàm mục tiêu cũ thành: Max Z = -20x1 - 10x2 thì sẽ thu được lời giải tối ưu là x1 = 2 và x2 = 0 mặc dù khơng làm thay đổi các ràng buộc của bài tốn.
Ví dụ: Một cơng ty thành lập bài tốn QHTT như sau: + Hàm mục tiêu: Max Lợi nhuận = 3x1 + 5x2 (USD) + Ràng buộc (Subject to):
x1 ≥ 5 x2 ≤ 10 x1 + 2 x2 ≥ 10 x1, x2 ≥ 0
Bài tốn này là bài tốn cực đại hĩa và miền ràng buộc mở rộng ra vơ hạn về phía phải. Vấn đề này xuất hiện vì bài tốn khơng được thành lập một cách chính xác. Sẽ là tuyệt vời cho bất kỳ cơng ty nào nếu cĩ khả năng sản xuất khơng giới hạn x1 (cho dù lợi nhuận trên mỗi đơn vị là thấp, chỉ 3 USD/sản phẩm), nhưng sẽ khơng cĩ cơng ty nào cĩ tài nguyên sẵn cĩ là vơ hạn, cũng như khơng cĩ chuyện nhu cầu cho một sản phẩm nào đĩ là vơ hạn.
Hình 4.12. Miền lời giải khơng bị chận về phía phải 7.3. Dư ràng buộc (Redundancy)
Một tình huống thường xảy ra khác khi giải bài tốn QHTT là tình trạng dư ràng buộc. Điều này hay xảy ra trong thực tế khi số ràng buộc và số biến rất lớn. Dư ràng buộc khơng gây khĩ khăn gì trong việc giải bài tốn QHTT bằng phương pháp đồ thị, nhưng bạn cũng cần phải nhận biết sự hiện diện của nĩ.
Một ràng buộc gọi là dư (redundant constraint) khi nĩ khơng làm ảnh hưởng đến miền nghiệm khả thi. Nĩi cách khác, đã cĩ một ràng buộc khác nào đĩ hạn chế hơn nên khơng cần xét đến điều kiện ràng buộc này.
Chú ý: Do các ràng buộc dư khơng làm ảnh hưởng đến miền nghiệm khả thi nên chúng ta cĩ thể gỡ bỏ các ràng buộc này trong mơ hình tốn QHTT mà khơng làm ảnh hưởng đến lời giải tối ưu của bài tốn. Tuy nhiên, trong một số trường hợp cần giải lại bài tốn QHTT sau này, đặc biệt khi cĩ sự thay đổi về dữ liệu đầu vào, cĩ thể sẽ làm các ràng buộc dư trước đây trở thành các ràng buộc cứng (binding
constraint). Vì vậy, tốt hơn hết chúng ta cứ nên giữ lại tất cả các ràng buộc trong mơ hình tốn QHTT.
Chúng ta rất dễ dàng nhận biết ràng buộc dư khi sử dụng phương pháp đồ thị để giải bài tốn cĩ 2 biến, tuy nhiên, đối với bài tốn từ 3 biến trở lên, các ràng buộc dư sẽ khơng dễ dàng nhận thấy.
Ví dụ Xét 1 bài tốn QHTT gồm 3 ràng buộc sau đây:
+ Hàm mục tiêu (Objective Fuction): Max Lợi nhuận Z = 1x1 + 2x2 (USD)
+ Ràng buộc (Subject to): x1 + x2 ≤20 2x1 + x2 ≤30 x1 ≤25 x1, x2 ≥ 0
Ràng buộc thứ 3: x1≤25 là ràng buộc dư và khơng cần thiết vì nĩ khơng ảnh hưởng tới miền nghiệm giới hạn bởi 2 ràng buộc đầu (xem hình 4.13)
Hình 4.13. Bài tốn cĩ ràng buộc dư