3.2. Các thuật giải cho quy hoạch tuyến tính
3.2.2. Các điểm cực trị (điểm góc) khả thi
Trong ví dụ minh họa vừa rồi, nghiệm tối ưu của bài toán QHTT tìm
được khi sử dụng phương pháp đồ nằm tại một điểm góc của miền nghiệm (gọi là điểm khả thi cực trị). Cần nhấn mạnh rằng, không có gì là đặc biệt
và trùng hợp về ví dụ này và dẫn đến một kết quả như vậy. Thực tế, đối với tất cả các bài toán QHTT nghiệm tối ưu luôn rơi vào biên của miền nghiệm.
Các điểm cực trị khả thi trong một bài toán QHTT có ba tính chất quan trọng. ý nghĩa của nó đối với kỹ thuật giải đại số sẽ được mô tả ở phần sau.
Những tính chất sau đây được đưa ra không kèm với chứng minh toán học.
Những chứng minh này có thể tìm thấy ở các sách QHTT hay sách quy hoạch toán (Dantzig, 1963, Bradley, Hax và Magrati, 1977; và Taha, 1987).
Tính chất 1a: Nếu mô hình QHTT chỉ có duy nhất một nghiệm tối ưu, nghiệm này phải nằm tại một điểm cực trị khả thi. Tính chất 1b. Nếu bài toán có nhiều nghiệm tối ưu, ít nhất hai trong số các nghiệm tối ưu nằm tại hai điểm cực trị khả thi cạnh nhau.
Như đã được minh hoạ trong hướng tiếp cận đồ giải, mỗi bài toán chỉ có một nghiệm tối ưu duy nhất, chúng ta luôn có thể nâng lên hay hạ xuống
đường hàm mục tiêu (hay mặt đa diện) cho đến khi nó tiếp xúc với điểm đó,
điểm tối ưu, tại một góc của miền nghiệm. Có thể tưởng tượng ra rằng các nghiệm tối ưu đa nghiệm xảy ra khi đường thẳng hàm mục tiêu (hay mặt đa diện) song song với một trong số các biên của miền nghiệm. Đối với bài toán hai chiều, nếu đa nghiệm xảy ra, hai điểm cực trị khả thi tối ưu nằm cạnh nhau. Đối với các bài toán nhiều chiều hơn, có nhiều hơn hai điểm cực trị khả thi tối ưu nằm cạnh nhau. ý nghĩa của tính chất này là, trong khi đi tìm nghiệm tối ưu cho một bài toán QHTT, sự chú ý có thể tập trung vào các điểm cực trị khả thi, chứ không phải là vùng bên trong của miền nghiệm.
H×nh 3.2
Một miền nghiệm của ví dụ sản xuất – xử lí nước thải.
Tính chất 2: Chỉ có một số hữu hạn các điểm khả thi cực trị.
Xét một mô hình QHTT có dạng chính tắc với m phương trình và n biến quyết định chưa biết (n>m). Đối với hệ các phương trình trên, số các
nghiệm có thể là
nCm = n!(n-m)! và là hữu hạn. Tuy nhiên, số nghiệm này cung cấp giới hạn trên của số các điểm khả thi cực trị bởi vì rất nhiều trong số các nghiệm này là không khả thi hay không tồn tại. Tính chất này có thể gợi ý rằng nghiệm tối ưu có thể thu được bằng cách liệt kê và xem xét tất cả các điểm cực trị khả thi. Tuy nhiên, điều này thường là không khả thi vì số các điểm khả thi có thể rất lớn để có thể liệt kê và xem xét một cách hiệu quả. Hơn thế nữa, nghiệm tối ưu không thể xác định được trước khi tất cả các điểm cực trị khả
thi được liệt kê và xem xét.
Tính chất 3: Nếu một điểm cực trị khả thi tốt hơn (đánh giá với x0) tất cả các điểm khả thi bên cạnh nó thì nó cũng tốt hơn tất cả các điểm cực trị khả thi còn lại (có nghĩa là nó là một điểm tối ưu toàn cục.)
Từ tính chất này ta không phải đi liệt kê và xem xét tất cả các điểm cực trị khả thi để tìm được nghiệm tối ưu của bài toán. Thay vào đó, vị trí của một điểm cực trị khả thi đang xem xét có thể được khẳng định đơn giản bằng việc so sánh nó với các điểm cạnh nó. Nếu tính chất 3 được thỏa mãn,
điểm cực trị khả thi mà ta đang xét là nghiệm tối ưu toàn cục của bài toán QHTT.
Nên nhấn mạnh rằng yêu cầu cơ bản cho tính chất này tồn tại là miền nghiệm là lồi. Nếu không, nghiệm tối ưu thu được sẽ không được đảm bảo là nghiệm tối ưu toàn cục mà chỉ là nghiệm tối ưu cục bộ. Hiện tượng này
đặc biệt thường xuyên xảy ra trong các bài toán quy hoach phi tuyết tính.
May mắn là miền nghiệm của các bài toán QHTT hầu như là luôn luôn lồi.