PHƯƠNG PHÁP HÌNH ĐƠN MỞ RỘNG

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

Thêm vào BST

Báo xấu

435
lượt xem 124
download

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

Bài toán ( 3-12 ) cho thấy rằng , nếu hệ phương trình tuyến tính trong điều kiện ràng buộc của bài toán Qui hoạch tuyến tính dạng chính tắc có đủ m vectơ đơn vị

Chủ đề:

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

Lưu

Nội dung Text: PHƯƠNG PHÁP HÌNH ĐƠN MỞ RỘNG

CHƯƠNG 1 : BÀI TOÁN QUI HOẠCH TUYẾN TÍNH VÀ PHƯƠNG PHÁP ĐƠN HÌNH BÀI 4: PHƯƠNG PHÁP HÌNH ĐƠN MỞ RỘNG I. BÀI TOÁN M II. BÀI TOÁN QUI HOẠCH TUYẾN TÍNH HAI PHA BÀI TẬP CHƯƠNG 1 BÀI 4: PHƯƠNG PHÁP ĐƠN MỞ RỘNG Bài toán ( 3-12 ) cho thấy rằng , nếu hệ phương trình tuyến tính trong điều kiện ràng buộc của bài toán Qui hoạch tuyến tính dạng chính tắc có đủ m vectơ đơn vị
Có hai bài toán mở rộng từ bài toán gốc : bài toán M và bài toán phụ pha thứ nhất của phương pháp đơn hình hai pha . TOP I. BÀI TOÁN M (Phương pháp đánh thuế) Bài toán M được xây dựng từ bài toán gốc như sau :
Qui tắc tính toán các biểu thức chứa M được cho trong bảng ( 4-3 ) với a,b,c,d là các số thực tùy ý :
Từ các kết quả trên , ta có phương pháp đơn hình mở rộng để giải bài toán gốc thông qua bài toán M như sau : Bước 1 - Xây dựng phương án cực biên của bài toán M .
Nếu bảng đơn hình có dấu hiệu vô nghiệm hoặc phương án cực biên đang có tối ưu thì việc giải bài toán M kết thúc . Ngược lại ,chuyển sang bước 3 . Bước 3 - Xây dựng phương án cực biên mới tốt hơn . Cách xác định tâm quay được thực hiên như phương pháp đơn hình đã biết Quay lại bước 2 và tiếp tục cho đến khi kết thúc . Khi cải tiến phương án , nếu một ẩn giả được chuyển lên vị trí biến độc lập thì loại bỏ cột tương ứng ra khỏi bảng đơn hình . Sau khi giaií xong bài toán M , ta có một trong các tình huống sau đây và từ đó suy ra kết quả cho bài toán gốc :
TOP II. BÀI TOÁN QUI HOẠCH TUYẾN TÍNH HAI PHA
Bước 2 - Ðánh giá phương án cực biên đang có của bài toán phụ Sử dụng dấu hiệu tối ưu đối với hàm g để đánh giá phương án cực biên đang có . Nếu bảng đơn hình có dấu hiệu vô nghiệm hoặc phương án cực biên đang có tối ưu thì kết thúc pha thứ nhất . Ngược lại , chuyển sang bước 3 . Bước 3 - Xây dựng phương án cực biên mới tốt hơn phương án đang có Cách xác định tâm quay để thực hiện phép quay biến dạng đã dược trình bày trong phương pháp đơn hình .Thực hiện phép quay biến dạng , thu được PA cực biên mới . Quay lại bước 2 và tiếp tục quá trình cho đến khi kết thúc .
Sau khi giaií xong bài toán phụ , cũng là kết thúc pha thứ nhất , ta được một trong các tình huống sau đây :
TOP BÀI TẬP CHƯƠNG 1