Tài liệu Tính chất của tập phương án và tập phương án tối ưu của bài toán quy hoạch tuyến tính

ĐỀ TÀI: Tính chất của tập phương án và tập phương án tối ưu của bài toán quy hoạch tuyến tính

§3. TÍNH CHẤT CỦA TẬP PHƯƠNG ÁN VÀ TẬP PHƯƠNG ÁN TỐI ƯU CỦA BÀI TOÁN QUY HOẠCH TUYẾN TÍNH

1. Tập hợp lồi. 1.1. Định nghĩa 1 (Định nghĩa tổ hợp lồi): Giả sử . Điểm được gọi là tổ hợp lồi của các điểm nếu tồn tại sao cho: Một tổ hợp lồi của hai điểm được gọi đoạn thẳng nối hai điểm đó. 1.2. Định nghĩa 2 (Định nghĩa tập lồi): Tập được gọi là tập lồi, nếu . Nói cách khác, tập L là tập lồi, nếu đoạn thẳng nối hai điểm trong L nằm gọn trong L. Ví dụ : Trong , đoạn thẳng, đường thẳng, tia, toàn bộ , nửa mặt phẳng, đa giác lồi, tam giác, hình tròn, hình elip đều là các tập lồi. Trong , đoạn thẳng, đường thẳng, mặt phẳng, đa diện lồi là các tập lồi. 1.3. Định nghĩa 3 (Định nghĩa điểm cực biên của một tập lồi): Điểm được gọi là điểm cực biên của tập lồi L, nếu . Ví dụ : Trong , đoạn thẳng, thì hai đầu mút là các điểm cực biên. Hình tam giác, thì các đỉnh là các điểm cực biên. 1.4. Định nghĩa 4 (Định nghĩa đa diện lồi): Ta gọi một đa diện lồi với các đỉnh là tập , trong đó . Nhận xét: L là một tập lồi và các điểm là các điểm cực biên, sau khi đã loại đi các điểm là tổ hợp lồi của các điểm còn lại. Ví dụ: Trong , đa diện lồi sinh bởi hai điểm là đoạn thẳng nối hai điểm đó, đa giác lồi là đa diện lồi sinh bởi các đỉnh của nó. 2. Tính chất của bài toán Quy hoạch tuyến tính: 2.1. Định lý 1: Tập hợp các phương án của bài toán Quy hoạch tuyến tính là một tập lồi. 2.2. Định lý 2: Tập hợp các phương án tối ưu của bài toán Quy hoạch tuyến tính là một tập lồi. 3. Tính chất của bài toán Quy hoạch tuyến tính dạng chính tắc: Xét bài toán Quy hoạch tuyến tính dạng chính tắc Trong đó A là ma trận cấp . Ta ký hiệu các cột của ma trận A là các véctơ Khi đó phương trình Ax=b có thề viết lại . 3.1. Định nghĩa 5: Giả sử là một phương án của bài toán Quy hoạch tuyến tính dạng chính tắc. Khi đó . Ứng với những hệ được gọi là hệ véctơ liên kết với . Ví dụ: Xét bài toán Quy hoạch tuyến tính có tập phương án là Với tập phương án này ta có , trong đó . Ta có là một phương án của bài toán (vì thỏa hệ phương trình), và . Vậy là hệ véctơ liên kết của . Lại có là một phương án của bài toán , và . Vậy là hệ véctơ liên kết của . 3.2. Định lý 3: Giả sử là một phương án khác không của bài toán Quy hoạch tuyến tính dạng chính tắc. Khi đó nếu là phương án cực biên của tập phương án thì hệ véctơ liên kết với nó độc lập tuyến tính. Ngược lại, nếu là một phương án có hệ véctơ liên kết với nó độc lập tuyến tính thì là một phương án cực biên. Ghi chú: Vì tập hợp các phương án của bài toán Quy hoạch tuyến tính là một tập lồi, nên có khái niệm phương án cực biên tức là các điểm cực biên của tập lồi. 3.3. Hệ quả 1: Số phương án cực biên của bài toán Quy hoạch tuyến tính dạng chính tắc là hữu hạn. 3.4. Định nghĩa 6: Một phương án cực biên của bài toán Quy hoạch tuyến tính dạng chính tắc được gọi là không suy biến nếu số thành phần dương của nó bằng m. Nếu số thành phần dương ít hơn m thì phương án cực biên này gọi là suy biến. Ví dụ: Xét bài toán Quy hoạch tuyến tính có tập phương án là Ta có là một phương án cực biên của bài toán, vì hệ véctơ liên kết với nó là , hai véctơ này độc lập tuyến tính. Hơn nữa đây là phương án cực biên không suy biến vì số thành phần dương của nó là 2 bằng số dòng của ma trận A. là một phương án cực biên của bài toán, vì hệ véctơ liên kết với nó là , hệ một véctơ này độc lập tuyến tính. Nhưng đây không phải là phương án cực biên không suy biến vì số thành phần dương của nó là 1. Ta có là một phương án của bài toán. Nhưng không phải là phương án cực biên, vì hệ véctơ liên kết với nó là, hệ véctơ này phụ thuộc tuyến tính. 3.5. Hệ quả 2: Số thành phần dương của một phương án cực biên của bài toán Quy hoạch tuyến tính dạng chính tắc tối đa là bằng m ( m là số dòng của ma trận A). 3.6. Định lý 4: Nếu bài toán Quy hoạch tuyến tính dạng chính tắc có tập phương án khác rỗng thì nó có ít nhất một phương án cực biên. Các định lý trên đây đã chỉ ra cho chúng ta cách thành lập một phương án cực biên của bài toán Quy hoạch tuyến tính dạng chính tắc là: Xác định các hệ gồm m véctơ độc lập tuyến tính của hệ véctơ Hệ này hữu hạn và tối đa là hệ con. Biểu diễn véctơ b theo các hệ con ở trên, ta được các hệ số biểu diễn. Thành lập véctơ x có các thành phần là hệ số biểu diễn. Khi đó x là một phương án. Loại đi những véctơ x có thành phần âm, các véctơ cón lại là các phương án cực biên. Ví dụ: Tìm tất cả các phương án cực biên của tập phương án của bài toán Giải: Có tất cả 4 véctơ hai chiều là . Từ đó lấy được hệ con độc lập tuyến tính là , ( đây cũng là các cơ sở trong ) . Biểu diễn véctơ theo các hệ độc lập tuyến tính này, ta có , , , , , . Từ đây ta có các véctơ thỏa hệ phương trình trên là , , , , , . Loại bỏ các véctơ có thành phần âm ta được 4 phương án cực biên là , , , . 3.7. Định lý 5: Nếu bài toán Quy hoạch tuyến tính dạng chính tắc có phương án tối ưu thì nó sẽ có ít nhất một phương án cực biên là phương án tối ưu. Nhận xét: Nhờ định lý này, nếu ta chứng minh được bài toán Quy hoạch tuyến tính dạng chính tắc có phương án tối ưu, thì nó sẽ có phương án cực biên là tối ưu . Trên đây chúng ta có thể tìm được tất cả các phương án cực biên (vì số phương án cực biên là hữu hạn; hệ qủa 1). Do đó trong số các phương án cực biên vừa chỉ ra, lần lượt thử từng phương án ta được phương án tối ưu. 3.8. Định lý 6: Nếu tập phương án của bài toán Quy hoạch tuyến tính ( bài toán Quy hoạch tuyến tính dạng tổng quát) không rỗng và là một đa diện lồi thì bài toán sẽ có ít nhất một phương án tối ưu là phương án cực biên. 3.9. Định lý 7: Điều kiện cần và đủ để bài toán Quy hoạch tuyến tính có phương án tối ưu là tập phương án không rỗng và hàm mục tiêu bị chặn dưới (nếu là bài toán min) hoặc bị chặn trên ( nếu là bài toán max). Ví dụ 1: Giải bài toán Quy hoạch tuyến tính Giải: Trước tiên ta tìm các phương án cực biên. Kế thừa ví dụ ở trên . Có 4 véctơ cột . Từc các véctơ này ta thu được các hệ con độc lập tuyến tính và các phương án tương ứng có phương án tương ứng , có phương án tương ứng , có phương án tương ứng , có phương án tương ứng , có phương án tương ứng , có phương án tương ứng . Từ đây ta có các phương án cực biên , , , . Hiển nhiên hàm mục tiêu của bài toán bị chặn dưới bởi 0, do đó theo định lý 7 bài toán có phương án tối ưu là phương án cực biên. T a có , , 35, 13. Vậy là phương án tối ưu của bài toán, và giá trị tối ưu là 10. Ví dụ 2: Giải bài toán Quy hoạch tuyến tính Giải: Tập hương án của bài toán là một tập lồi đa diện, cụ thể đó là tứ giác ABCD (hình ). Trong đó , đây cũng là các phương án cực biên, do đó theo định lý 6 bài toán có phương án tối ưu là phương án cực biên. Bằng cách thử các phương án cực biên ta được , , , . Vậy phương án tối ưu là B(0;4) , và giá trị tối ưu là 8. Bài tập Trong cho hai điểm . Tìm tổ hợp lồi sinh bởi hai điểm A, B. Tìm các điểm cực biên của tập lồi . Tìm các điểm cực biên của tập lồi . Cho A, B là hai tập lồi. Chứng minh rằng là một tập lồi, nhưng có thể không là tập lồi. Chứng minh các tập sau đây là các tập lồi: a) . b) . Chứng minh Định lý 1: Tập hợp các phương án của bài toán Quy hoạch tuyến tính là một tập lồi. Chứng minh Định lý 2: Tập hợp các phương án tối ưu của bài toán Quy hoạch tuyến tính là một tập lồi. Chứng minh Định lý 3: Giả sử là một phương án khác không của bài toán Quy hoạch tuyến tính dạng chính tắc. Khi đó nếu là phương án cực biên của tập phương án thì hệ véctơ liên kết với nó độc lập tuyến tính. Ngược lại, nếu là một phương án có hệ véctơ liên kết với nó độc lập tuyến tính thì là một phương án cực biên. Chứng minh Hệ quả 1: Số phương án cực biên của bài toán Quy hoạch tuyến tính dạng chính tắc là hữu hạn. Chứng minh Hệ quả 2: Số thành phần dương của một phương án cực biên của bài toán Quy hoạch tuyến tính dạng chính tắc tối đa là bằng m ( giả sử m là số dòng của ma trận A và cũng là hạng của A). Chứng minh Định lý 4: Nếu bài toán Quy hoạch tuyến tính dạng chính tắc có tập phương án khác rỗng thì nó có ít nhất một phương án cực biên. Chứng minh Định lý 5: Nếu bài toán Quy hoạch tuyến tính dạng chính tắc có phương án tối ưu thì nó sẽ có ít nhất một phương án cực biên là phương án tối ưu. Chứng minh Định lý 6: Nếu tập phương án của bài toán Quy hoạch tuyến tính không rỗng và là một đa diện lồi thì bài toán sẽ có ít nhất một phương án tối ưu là phương án cực biên. Chứng minh Định lý 7: Điều kiện cần và đủ để bài toán Quy hoạch tuyến tính có phương án tối ưu là tập phương án không rỗng và hàm mục tiêu bị chặn dưới (nếu là bài toán min) hoặc bị chặn trên ( nếu là bài toán max). Giải bài toán Giải bài toán Giải bài toán Giải bài toán Lời giải hoặc hướng dẫn Tổ hợp lồi sinh bởi hai điểm A(1;1) và B(3;1) là tập hợp các điểm Đây chính là một đoạn thẳng. Hai điểm cực biên là x=2 và x=5. Thật vậy vì nên tâp L chín là đoạn thẳng [2;5]. Từ đó thì . Vì . Hai điểm cực biên là (1;-1) và (2;1). Chứng minh tương tự bài 2. Dùng định nghĩa tập lồi thấy ngay giao của hai hay nhiều tập lồi là một tập lồi. Nhưng hợp của hai tập lồi có thể không lồi. Chẳng hạn Sau khi vẽ hình ta thấy ngay A hợp B không lồi. Đây là phần lõm bên trong của parapol nên thấy ngay đây là tập lồi. Nhưng có thể chứng minh trực tiếp bằng định nghĩa như sau: .Ta chứng minh . Thật vậy .Vì nên . Ta có vì Từ đó . Đó chính là đpcm. Trước tiên ta chứng minh tập hợp các phương án của bài toán Quy hoạch tuyến tính dạng chính tắc là tập lồi. Thật vậy, nếu x, y hai phương án thì Ax=b, Ay=b . Khi đó . Chứng tỏ là một phương án. Trong trường hợp bài toán tổng quát, ta thay các dấu đẳng thức bởi bất đẳng thức. Giả sử là hai phương án tối ưu của bài toán Quy hoạch tuyến tính. Khi đó (hoặc min), D là tập phương án. Xét , ta chứng minh y cũng là phương án tối ưu. (Vì hàm mục tiêu f là hàm tuyến tính). Giả sử phản chứng có r thành phần đầu dương là phương án cực biên mà hệ véctơ liên kết với nó lại phụ thuộc tuyến tính. Từ hệ phụ thuộc tuyến tính ta tìm được các số không đồng thời bằng 0 thỏa . Với tùy ý ta có (*). là một phương án nên (**). Từ (*) và (**) suy ra . Xét hai véctơ Do nên có thể chọn đủ nhỏ sao cho (tức là tất cả các thành phần của nó đều không âm). Khi đó hiển nhiên là các phương án khác nhau và ta có . Chứng tỏ không phải là phương án cực biên. Vậy hệ véctơ liên kết với nó độc lập tuyến tính. Ngược lại, giả sử phương án có r thành phần đầu dương, các thành phần còn lại đều bằng không, nghĩa là nó có dạng . Khi đó hay , trong đó là các véctơ cột của A. Giả thiết độc lập tuyến tính ta chứng minhlà phương án cực biên. Giả sử (với là hai phương án). Khi đó với là các thành phần thứ j của . Do nên thì và , có thể giả sử Ta có hay là Vì hệ độc lập tuyến tính nên từ ba đẳng thức trên suy ra với mọi . Vậy , nghĩa là là phương án cực biên. Theo bài 8 nếu là phương án cực biên thì hệ véctơ liên kết với nó độc lập tuyến tính. Ma trận A có tất cả là n véctơ cột nên số hệ véctơ con độc lập tuyến tính phài hữu hạn, dẫn đến số phương án cực biên cũng hữu hạn. Giả sử có r thành phần đầu dương, khi đó hệ véctơ liên kết với nó là . Theo bài 8 hệ này độc lập tuyến tính, ma trận A có hạng bằng m do đó r không vượt quá m. là một phương án của bài toán. Nếu thì nó là phương án cực biên. Nếu ta có thể giả thiết nó có dạng với r thành phần đầu dương. Khi đó . Nếu không phải là phương án cực biên thì hệ phụ thuộc tuyến tính. Ta tìm được các số không đồng thời bằng 0 thỏa , trong các số có thể giả sử có ít nhất một số dương. Với tùy ý ta có . Suy ra . Do nên có thể chọn đủ nhỏ sao cho . Có thể chọn , thì véctơ có thành phần thứ s là . Lúc này véctơ có số thành phần dương ít hơn , nếu chưa phải là phương án cực biên thì làm tương tự ta xây dựng phương án có số thành phần dương ít hơn . Quá trình này phải dừng, tức là ta tìm được phương án cực biên. 12.Chứng minh Định lý 5: Nếu bài toán Quy hoạch tuyến tính dạng chính tắc có phương án tối ưu thì nó sẽ có ít nhất một phương án cực biên là phương án tối ưu. Trước tiên ta chứng minh mệnh đề: Nếu là một phương án tối ưu của bài toán Quy hoạch tuyến tính thì cũng là phương án tối ưu. Thật vậy, (giả sử đây là bài toán min). Vì , nên bất đẳng thức trên chứng tỏ . Trở lại bài toán 12, giả sử là một phương án tối ưu của bài toán. Nếu thì đó là phương án cực biên, ngược lại theo cách chứng minh bài 8 và bài 10 ở trên ta xây dựng được , trong đó có số thành phần dương ít hơn so với . Theo mệnh đề vừa chứng minh cũng là phương án tối ưu. Nếu là phương án tối ưu thì xong, nếu không ta xây dựng được là phương án tối ưu có số thành phần dương ít hơn . Quá trình này phải dừng. Khi đó ta thu được phương án tối ưu là phương án cực biên, hoặc phương án tối ưu 0. Trường hợp nào đi nữa ta cũng có phương án tối ưu là phương án cực biên. Ta xét bài toán min. Giả sử x là một phương án bất kỳ, ta có trong đó là các phương án cực biên, . Giả sử (f là hàm mục tiêu). Vì f tuyến tính nên ta có . Điều này đúng cho mọi phương án x nên là phương án tối ưu. 15. Ta có ( dùng (1)). Vậy hàm mục tiêu bị chặn dưới. Dễ thấy tập phương án không rỗng, do đó bài toán có phương án tối ưu và do đó sẽ có ít nhất một phương án cực biên là phương án tối ưu. Có 4 véctơ cột . Từ các véctơ này ta thu được các hệ con độc lập tuyến tính và các phương án tương ứng có phương án tương ứng , có phương án tương ứng , có phương án tương ứng , có phương án tương ứng , có phương án tương ứng , có phương án tương ứng . Từ đây ta có các phương án cực biên , , . T a có , , . Vậy là phương án tối ưu của bài toán, và giá trị tối ưu là . 16. Phương án tối ưu là , và giá trị tối ưu là f(x)=3. 17. Phương án tối ưu là , và giá trị tối ưu là f(x)=1. 18. Phương án tối ưu là , và giá trị tối ưu là f(x)=-2.