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

Tham khảo tài liệu chương 1: bài toán quy hoạch tuyến tính - bài 5, 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 5 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH Nội dung cơ bản của PP đơn hình 1 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNHXét BT QHTT dạng chuẩn tắc như sau: n f ( x)   ci xi  max (min) i 1  n m xk  akmj x j  bk (k  1, m; j  1, n  m)  j 1 x  0, b  0 (i  1, n; k  1, m; m  n) i k 2 1 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH1. Ước lượng của ẩn: PACB XP: x0 (x10, x20,, xm0 , 0,, 0) hay x0  (b1, b2 ,, bm, 0,, 0) Với hệ ẩn CB: x1, x2, …, xm m  l   ck akl  cl (l  m  1, n) k 1 Được gọi là hệ số ước lượng của ẩn xl. 3 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH2. Dấu hiệu tối ưu của bài toán n n l f ( x )   ci xi  max f ( x)   ci xi  min i 1 i 1  l  0 l  m  1, n Có PATU l  0 l m 1, n Có PATU** Chú ý: Khi có dấu hiệu tối ưu mà tồn tại ít nhất 1hệ số ước lượng bằng 0 của ẩn không cơ bản thìbài toán có thể có nhiều hơn 1 phương án tối ưu. 4 2 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 3. Định lý cơ bản Nếu trong 1 phương án cơ bản của bài toán mà l 0 (đối với bài toán cực đại) hay l  0(đối với bài toán cực tiểu) của ẩn không cơ bản thì sẽ xảy ra 1 trong hai trường hợp sau: a) Nếu có một hệ số ước lượng mà mọi kl a 0 thì bài toán không giải được. b) Nếu với mỗi hệ số ước lượng mà tồn tại ít nhất mộtakl  0 thì bài toán có phương án cơ bản mới tốt hơn. 5 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 4. Thuật toán đơn hình giải BTQHTT dạng chuẩn tắc A. Giải BT cực đại a) Bước lặp thứ nhất a.1) Xác định ẩn CB, PACB xuất phát x0 và giá trị f(x0) của hàm mục tiêu tại PACB này. a.2) Lập bảng đơn hình (BDH) xuất phát như sau: 6 3 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 4. Thuật toán đơn hình giải BTQHTT dạng chuẩn tắc A. Giải BT cực đạia) Bước lặp thứ nhấtCác thành phần của BDH bao gồm:+ Cột B: Ghi lần lượt theo thứ tự các ẩn CB của BT.+ Cột A: Ghi tương ứng các hệ số của các ẩn CB trong HMT.+ Cột C: Ghi các số hạng tự do tương ứng với các ẩn CB.+ Cột D: Ghi ma trận điều kiện của hệ ràng buộc chính.+ Hàng E: Ghi toàn bộ các ẩn của BT trong HMT.+ Hàng F: Ghi hệ số tương ứng của các ẩn trong HMT. 7 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 4. Thuật toán đơn hình giải BTQHTT dạng chuẩn tắc A. Giải BT cực đạia) Bước lặp thứ nhất Các thành phần của BDH bao gồm: + Hàng G: Tính trị số của các hệ số ước lượng (HSUL) các ẩn và trị số của HMT: m (Tổng của tích cột A với cột j rồi trừ đi  j   ci xi  c j hệ số của ẩn xj tại hàng F) và được ghi tương ứng ở hàng G của cột D. i 1 (Hệ số ước lượng của các ẩn cơ bản luôn bằng 0) m f ( x )   ci xi + N số 0 (Tổng của tích cột A với cột C) và hạng tự do (nếu có) và được i 1 ghi ở hàng G của cột C. 8 4 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 4. Thuật toán đơn hình giải BTQHTT dạng chuẩn tắc A. Giải BT cực đạia) Bước lặp thứ nh ...