Bài toán qui hoạch tuyến tính đối ngẫu

Lý thuyết đối ngẫu là một trong những công cụ hữu hiệu của Toán học nói chung . Nhiều mệnh đề Toán học được suy ra từ mệnh đề đã biết nhờ qui tắc đối ngẫu mà không cần chứng minh .
Nội dung trích xuất từ tài liệu:
Bài toán qui hoạch tuyến tính đối ngẫuCHƯƠNG 2 : BÀI TOÁN QUI HOẠCH TUYẾN TÍNH ĐỐI NGẪU BÀI 1: BÀI TOÁN QUI HOẠCH TUYẾN TÍNH ĐỐI NGẪU I. BÀI TOÁN QUI HOẠCH TUYẾN TÍNH ĐỐI NGẪU KHÔNG ĐỐI XỨNG II. BÀI TOÁN QUI HOẠCH TUYẾN TÍNH ĐỐI NGẪU ĐỐI XỨNGIII. BÀI TOÁN QUI HOẠCH TUYẾN TÍNH ĐỐI NGẪU TỔNG QUÁT BÀI 2: CÁC ĐỊNH LÝ ĐỐI NGẪU BÀI 3: ỨNG DỤNG CỦA LÝ THUYẾT ĐỐI NGẪU I. KIỂM TRA TÍNH TỐI ƯU CỦA MỘT PHƯƠNG ÁN II. Ý NGHĨA KINH TẾ CỦA BÀI TOÁN ĐỐI NGẪUBÀI TÂP CHƯƠNG 2 Lý thuyết đối ngẫu là một trong những công cụ hữu hiệu của Toán học nói chung .Nhiều mệnh đề Toán học được suy ra từ mệnh đề đã biết nhờ qui tắc đối ngẫu mà khôngcần chứng minh . Bài toán Qui hoạch tuyến tính đối ngẫu là bài toán được thành lập từ một bài toánQui hoạch tuyến tính gốc cho trước , có mối liên hệ chặt chẽ với bài toán gốc . Nhiều khi, việc giải bài toán gốc được thực hiện dễ dàng thông qua việc giải bài toán đối ngẫu củanó , đặc biệt là đối với các bài toán Qui hoạch tuyến tính có nhiều ẩn số nhưng lại có ítđiều kiện ràng buộc TOP BÀI 1: BÀI TOÁN QUI HOẠCH TUYẾN TÍNH ĐỐI NGẪU Chúng ta sẽ lần lượt xây dựng bài toán đối ngẫu của các bài toán Qui hoạch tuyếntính dạng đặc biệt ( dạng chính tắc , dạng chuẩn tắc ) và cuối cùng là của Qui hoạch tuyếntính tổng quát . TOPI. BÀI TOÁN QUI HOẠCH TUYẾN TÍNH ĐỐI NGẨU KHÔNG ĐỐIXỨNG TOPII. BÀI TOÁN QUI HOẠCH TUYẾN TÍNH ĐỐI NGẨU ĐỐI XỨNG TOPIII. BÀI TOÁN QUI HOẠCH TUYẾN TÍNH ĐỐI NGẨU TỔNG QUÁT Dựa vào qui tắc ( 1-15 ) ta thấy rằng bài toán đối ngẫu của bài toán dạng chuẩntắc cũng là bài toán dạng chuẩn tắc . Vì vậy cặp bài toán dạng chuẩn tắc và bài toán đốingẫu của nó được gọi là cặp bài toán đối ngẫu đối xứng . TOPBÀI 2: CÁC ĐỊNH LÝ ĐỐI NGẪU Mối liên hệ giữa bài toán Qui hoạch tuyến tính gốc và bài toán đối ngẫu của nóđược thể hiện trong các Ðịnh lí đối ngẫu sau đây .Ðịnh lí 1 Cho bài toán Qui hoạch tuyến tính tổng quát ( D , f ) và giả sử bài toáïn Qui hoạch tuyến tính đối ngẫu của nó là (E , g ) . Khi đó, bài toán đối ngẫu của bài toán ( E , g ) là bài toán ( D , f ) . Như vậy , nếu thành lập bài toán đối ngẫu của bài toán đối ngẫu thì được bài toángốc ban đầu . Ðịnh lí 1 được chứng minh đễ dàng dựa vào qui tắc thành lập bài toán đốingẫu và các mũi tên hai chiều trong ( 1-15 ) . Bài toán Qui hoạch tuyến tính tổng quát có thể đưa về dạng chính tắc (Ðịnh lí 1Chương I ) , mặt khác , Ðịnh lí 1 Chương II cho thấy nếu thành lập bài toán đối ngẫu củabài toán đối ngẫu thì được bài toán gốc ban đầu , vì vậy , chỉ cần chứng minh cho trườnghợp bài toán gốc dạng chính tắc . Phần chứng minh chi tiết xem [ 1 ] hoặc [ 3 ] . Có thể viết phương án tối ưu của bài toán đối ngẫu dựa vào bảng đơn hình giải bàitoán gốc dạng chính tắc theo qui tắc thực hành sau đây . BÀI 3: ỨNG DỤNG CỦA LÝ THUYẾT ĐỐI NGẪU TOPI. KIỂM TRA TÍNH TỐI ƯU CỦA MỘT PHƯƠNG ÁN