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

Chia sẻ: Nguyễn Thị Giỏi | Ngày: | Loại File: PDF | Số trang:13

Thêm vào BST

Báo xấu

1.018
lượt xem 258
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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à

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

CHƯƠNG 1 : BÀI TOÁN QUI HOẠCH TUYẾN TÍNH VÀ PHƯƠNG PHÁ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ÊN III. Ý 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 TOP I. TẬP HỢP CÁC PHƯƠNG ÁN
TOP II. 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ể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à 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, tuy nhiê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ằng chỉ 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ủa thuậ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 Qui hoạch tuyến tính sau đây . TOP III. Ý 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 )