Chương 1: Bài toán quy hoạch tuyến tính - bài 3

Tham khảo tài liệu chương 1: bài toán quy hoạch tuyến tính - bài 3, khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Chương 1: Bài toán quy hoạch tuyến tính - bài 3 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT 1. BTQHTT dạng chính tắc (đầy đủ) f ( x)  c1 x1  c2 x2  ...  cn xn  max (min) a 11 x1  a 12 x 2  ...  a 1 n x n  b1 a 21 x1  a 22 x 2  ...  a 2 n x n  b 2 (I) .......... ......... a x  a x  ...  a x  b m1 1 m2 2 mn n m x i  0 ( i  1, n ) 1 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT 1. BTQHTT dạng chính tắc (rút gọn) n f ( x)   ci xi  max (min) i 1  n  a ji xi  b j ( j  1, m) (II)  i 1  x  0 (i  1, n)  i 2 1 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT 1. BTQHTT dạng chính tắc @ Ma trận điều kiện & Vector điều kiện a11 a12 ... a1n  a1i  a a ... a  a A   21 22 2n  Ai   2 i  .............................  ...      am1 am 2 ... amn  ami  3 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT 1. BTQHTT dạng chính tắc @ Định lý: Cho BTQHTT dạng chính tắc như dạng (I) hoặc dạng (II), điều kiện cần & đủ để PA x*  ( x1* , x2* ,..., xn* ) là 1 PACB của  bài toán là hệ vector điều kiện Ai xi  0 *  độc lập tuyến tính. 4 2 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT 1. BTQHTT dạng chính tắc @ Biến đổi bài toán về dạng chính tắc Ràng buộc chính Cách biến đổi n n a i 1 x  bj ji i a i 1 x  xn  k  b j ji i n n a i 1 x  bj ji i a i 1 x  xn  k  b j ji i Điều kiện: xnk  0 5 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT 1. BTQHTT dạng chính tắc @ Biến đổi bài toán về dạng chính tắc Ràng buộc dấu Cách biến đổi bj  0 Nhân 2 vế của ràng buộc chính với -1 & đổi dấu. xi  0 xi   xi ( xi  0) xi  xi  xi  x  0  x  0  xi có dấu tuỳ ý i i 6 3 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT 1. BTQHTT dạng chính tắc*** CHÚ Ý:- Bài toán đã cho được gọi là BT gốc; BT mớibiến đổi (có ẩn phụ) được gọi lài BT phụ.- BT phụ có hay không có PATU thì BT gốccũng có hay không có PATU.- Nếu BT phụ có PATU thì PATU của BT gốc sẽđược rút ra bằng cách bỏ đi phần ẩn phụ vàđổi các trị số của biến mới về các biến cũ theocác công thức biến đổi đã dùng. 7 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT 1. BTQHTT dạng chính tắc Vd1: Biến đổi BT sau về dạng chính tắc: f ( x)  2x1  x2  2x3  x4  2x5  min  x1  2 x2  x3  2 x4  x5  7  x  2 x  x  1  2 3 4 2 x3  x4  3x5  10   x1  x2  2 x3  x4  20 x , x  0  1 5  x4  0 8 4 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT 1. BTQHTT dạng chính tắc Vd1: Biến đổi BT sau về dạng chính tắc:  x4   x4   2 x  x  x Đặt 2 2   3 x  x 3  x 3  x , x , x , x , x  0  2 2 3 3 4 9 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT 1. BTQHTT dạng chính tắc Vd1: Biến đổi BT sau về dạng chính tắc:f (x)  2x1 (x2  x2 )  2(x3  x3 )  x4 2x5  minx1 2(x2  x2 ) (x3  x3 ) 2x4  x5  x6  7 (x2  x2 ) 2(x3  x3 )  x4  x7  1  2(x3  x3 )  x4 3x5  x8  10 x1  ( x 2  x ...