Bài toán giải thuật đơn hình

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

Không thể tạo bản xem trước, hãy bấm tải xuống
TÀI LIỆU MỚI ĐĂNG
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.