TẬP HỢP CÁC PHƯƠNG ÁN CỦA BÀI TOÁN QUI HOẠCH TUYẾN TÍNH

Nếu X là điểm cực biên của tập các phương án D thì X được gọi là phương án cực biên. Vai trò của phương án cực biên sẽ được trình bày ở Ðịnh lí 5 mục này. Việc kiểm tra một phương án (điểm) có phải là cực biên của tập các phương án D (thường là
Nội dung trích xuất từ tài liệu:
TẬP HỢP CÁC PHƯƠNG ÁN CỦA BÀI TOÁN QUI HOẠCH TUYẾN TÍNHCHƯƠNG 1 : BÀI TOÁN QUI HOẠCH TUYẾN TÍNH VÀ PHƯƠNGPHÁP ĐƠN HÌNH BÀI 2: TẬP HỢP CÁC PHƯƠNG ÁN CỦA BÀI TOÁN QUI HOẠCH TUYẾN TÍNH I. TẬP HỢP CÁC PHƯƠNG ÁN II. PHƯƠNG ÁN CỰC BIÊNIII. Ý NGHĨA HÌNH HỌC CỦA BÀI TOÁN QUI HOẠCH TUYẾN TÍNH BÀI 2: TẬP HỢP CÁC PHƯƠNG ÁN CỦA BÀI TOÁN QUI HOẠCH TUYẾN TÍNH TOPI. TẬP HỢP CÁC PHƯƠNG ÁN TOPII. PHƯƠNG ÁN CỰC BIÊNÐịnh nghĩa Nếu X là điểm cực biên của tập các phương án D thì X được gọi là phươngán cực biên. Vai trò của phương án cực biên sẽ được trình bày ở Ðịnh lí 5 mục này. Việc kiểmtra một phương án (điểm) có phải là cực biên của tập các phương án D (thường là vô hạn) hay không theo định nghĩa là rất khó khăn. Ðịnh lí 4 sau đây cho dấu hiệu cần và đủđơn giản để một phương án là cực biên.Ðịnh lí 4: Xét bài toán Qui hoạch tuyến tính dạng chính tắcÐịnh lí 5 Nếu bài toán Qui hoạch tuyến tính có nghiệm thì có nghiệm cực biên (nghiệm tương ứng là điểm cực biên của tập các phương án D ) .Hệ quả Nếu bài toán Qui hoạch tuyến tính không có nghiệm cực biên thì vô nghiệm. Tập hợp các phương án D của bài toán Qui hoạch tuyến tính thường là vô hạn, tuynhiên số phương án cực biên là hữu hạn ( hệ quả của Ðịnh lí 4 ). Ðịnh líï 5 cho thấy rằngchỉ cần tìm nghiệm trong các điểm cực biên (hữu hạn) của D , suy ra tính hữu hạn củathuật toán đơn hình sau này. Các kết quả về nghiệm , nghiệm cực biên được minh họa trong các hình(2-11 ) , ( 2-12 ) , (2-13 ) và được phân tích ở phần ý nghĩa hình học của bài toán Quihoạch tuyến tính sau đây . TOPIII. Ý NGHĨA HÌNH HỌC CỦA BÀI TOÁN QUI HOẠCH TUYẾN TÍNH ( Giải bài toán Qui hoạch tuyến tính bằng hình học )