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

0
822
lượt xem
252
download

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

Mô tả tài liệu
  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ủ đề:
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

  1. 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
  2. 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
  3. Ðị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 ) .
  4. Hệ quả
  5. 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 )

CÓ THỂ BẠN MUỐN DOWNLOAD

Đồng bộ tài khoản