PHƯƠNG PHÁP HÌNH ĐƠ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ị
Nội dung trích xuất từ tài liệu:
PHƯƠNG PHÁP HÌNH ĐƠN MỞ RỘNGCHƯƠNG 1 : BÀI TOÁN QUI HOẠCH TUYẾN TÍNH VÀ PHƯƠNGPHÁ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 PHABÀ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ệnrà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ấtcủa phương pháp đơn hình hai pha . TOPI. 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ốcthô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 ưuthì 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 Quaylạ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ạibỏ 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ừ đó suyra kết quả cho bài toán gốc : TOPII. BÀI TOÁN QUI HOẠCH TUYẾN TÍNH HAI PHABướ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 trongphươ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 trongcác tình huống sau đây : TOPBÀI TẬP CHƯƠNG 1