Tài liệu tham khảo lập trình - Bài toán giải thuật đơn hình | Bài 1 Dạng tổng quát Dạng bài toán QHTT n 1 f x ị cjxj min max j i 2 n ỵ aijxj bi ie 11 j 1 j bi ie I2 ỵ aijxj bi i e I3 j i 3 xj 0je Ji xj 0je J2 xjtu yy je J3 Trong đó - f x là hàm mục tiêu - I1 I2 I3 là rời nhau và I1 U I2 U I3 1 2 . .mỊ - J1 J2 J3 là rời nhau và J1 U J2 U J3 1 2 . n - A aij mxn Ma trận hệ số ràng buộc - B b1 b2 . bm Vectơ các hệ số tự do - C c1 c2 . . cm Vectơ các hệ số ẩn trong hàm mục tiêu - X x1 x2 . xn Vectơ các ẩn số Dạng chính tắc n 1 f x ị cjxj min max j 1 2 ịa j bi i j 1 3 xj 0j Dạng chuẩn n 1 f x ị cjxj min max j 1 2 ịa j bi i j 1 3 xj 0j Trong đó - Các hệ số tự do b1 b2 . bm đều không âm. - Trong ma trận hệ số ràng buộc A aij mxn có đầy đủ m vectơ cột đơn vị e1 e2 . . em í 1 ì í 0 ì í 0 ì 0 1 0 e1 . e2 . em . 0 0 1J Dạng tổng quát Dạng chính tắc Dạng chuẩn Ths Đức 0972 670 808 1 onthicaohoc_toankinhte @ Bài 2 Phương pháp đơn hình Bước 1 Lập bảng đơn hình xuất phát Xác định pacb ban đầu xuất phát x x1 x2 . xn . Là phương án có các ẩn không cơ bản đều là số 0 ẩn cơ bản có giá trị bằng các hệ số tự do Xác định J x j xj 0 Xác định hệ ẩn cơ bản xj I j e J x Lập bảng đơn hình xuất phát sau __ Ẩn cơ bản Hệ số Phương án c1 c2 cn j x1 x2 xn xj cj bj zj1 zj2 zjn jn f A1 A2 An Trong đó f cjxj f x giá trị hàm mục tiêu tương ứng với x f cột Hệ số cột Phương án jeJ x Ak cjzjk - ck hệ số ước lượng của biến xk k Ak cột Hệ số cột Zjk -ck jeJ x Lưu ý Ak 0 k e J x ứng với các ẩn cơ bản . f x x - 2x 2x - x x - 2x min X 1 2 345 6 2x1 - 5 4 5 x1 - 2x2 2x3 x5 4 -4x x2 x3 x6 2 1236 Ãj 0 j Giải Ta có c 1 -2 2 -1 1 -2 Các biến cơ bản là x4 x5 x6 Các biến không cơ bản x1 x2 x3 x 0 0 0 5 4 2 J x 4 5 6 f 2 -1 -5 1 0 0 ì A 1 -2 2 0 1 0 X -4 1 1 0 0 17 A1 f 2 ì 1 A2 í-1ì 2 A3 f -5 ì 2 . Tương tự cho các biến cơ bản A4 í 1 ì 0 A5 í 0 ì 1 A í 0 ì 0 - 4 X 7 1 X 1 7 1 X 1 7 0 Xu7 0 Xu7 1 XL7 Ths Đức 0972 670 808 2 onthicaohoc_toankinhte@ Ẩn cơ bản Hệ số cj PA 1 -2 2 -1 1 -2 x1 x2 x3
