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

Chia sẻ: Nguyễn Văn Cường | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST

Báo xấu

921
lượt xem 182
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu tham khảo lập trình - Bài toán giải thuật đơn hình

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài toán giải thuật đơn hình

Bài 1: D ng bài toán QHTT * D ng t ng quát n (1) f (x) = ∑ c j x j → min(max) j=1 n  ∑ a ij x j = bi , i ∈ I1  j=1 n  (2) ∑ a ij x j ≤ bi , i ∈ I 2  j=1 n  ∑ a ij x j ≥ bi , i ∈ I3  j=1  (3) x j ≥ 0 j ∈ J1 , x j ≤ 0 j ∈ J 2 , x j tu`y y ' j ∈ J 3 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) = ∑ c j x j → min(max) j=1 n ∑a x = bi , i = 1..m (2) ij j j=1 (3) x j ≥ 0 j = 1..n * D ng chu n n (1) f (x) = ∑ c j x j → min(max) j=1 n ∑a x = bi , i = 1..m (2) ij j j=1 (3) x j ≥ 0 j = 1..n Trong ó : - Các h s t do b1, b2, …, bm u không âm. m vectơ c t ơn v e1, e2, …,em: - Trong ma tr n h s ràng bu c A = (aij)mxn có y 1 0 0    0 1 0 e1 =   ;e 2 =   ;...; em =    ...   ...   ...     0 0 1 D ng t ng quát D ng chính t c D ng chu n Ths c 0972 670 808 1 onthicaohoc_toankinhte@yahoo.com
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 , x 2 ,..., x n ) . 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/ x j > 0} n cơ b n {x j j ∈ J(x)} * Xác nh h * L p b ng ơn hình xu t phát sau: c1 c2 … cn λj n cơ b n Phương án Hs x1 x2 … xn xj cj bj zj1 zj2 … zjn λ jn f … ∆1 ∆2 ∆n ∑ cx Trong ó: f = = 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) j j j∈J(x ) ∑ cz − c k : h s ư c lư ng c a bi n xk, k=1..n ( ∆ k = c t H s *c t zjk –ck) ∆k = j jk j∈J(x ) Lưu ý: ∆ k = 0, k ∈ J(x) ( ng v i các n cơ b n). f (x) = x1 − 2x 2 + 2x 3 − x 4 + x 5 − 2x 6 → min  2x1 − x 2 − 5x 3 + x 4 = 5   x1 − 2x 2 + 2x 3 + x 5 = 4 −4x + x + x + x = 2  1 2 3 6 x j ≥ 0, j = 1..6 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}  2 −1 −5 1 0 0  A =  1 −2 2 0 1 0     −4 1 1 0 0 1    2  −1  −5  1 0 0  1  , A =  2  , A =  2  . Tương t cho các bi n cơ b n A =  0  , A =  1  , A =  0  A1 =   2   3    5  6  4  −4  1 1 0   0 1     Ths c 0972 670 808 2 onthicaohoc_toankinhte@yahoo.com
n cơ Hs PA 1 -2 2 -1 1 -2 bn x1 x2 x3 x4 x5 x6 cj 2 x4 -1 5 -1 -5 1 0 0 x5 1 4 1 -2 2 0 1 0 x6 -2 2 -4 1 1 0 0 1 (6) -5 -1 3 0 0 0 Bư c 2: Xét d u hi u t i ưu * Xem dòng ghi ∆1 , ∆ 2 ,..., ∆ n - N u có ∆ k ≤ 0, ∀k : phương án ang xét là PATU. Thu t toán k t thúc - N u không: bư c 3 Bư c 3: Xét d u hi u không t i ưu * Xét xem có c t ∆ k sao cho ∆ k > 0 và m i ph n t thu c c t này ( bư c l p ang xét ) u ≤ 0 không?. - N u có : BT không có PATU. Thu t toán k t thúc - N u không bư c 4 Bư c 4: C i ti n PA ( Tìm pacb t t hơn) Tìm pacb x ' = (x '1 , x '2 ,..., x 'n ) t t hơn pacb x: f(x’) 0} . Ch n c t có ∆ k dương l n nh t . Khi ó xv là n mà ta s ưa vào h n cơ b n. b) Ch n n ưa ra kh i h n cơ b n  b j     b Ch n λ r = r = min   j ∈ J(x) và z jv > 0  . Khi ó n xr là n ưa ra kh i h cơ b n. z  z rv  jv     Bư c 5: Tìm ph n t ch t Ph n t ch t là ph n t giao gi a n ưa vào và n ưa ra: zrv Bư c 6: Bi n i b ng • Trong c t n cơ b n ta thay xr b ng xv. Trong c t h s ta thay cr b ng cv. h • Dùng phép bi n i h r = r : nghĩa là hàng r m i = hàng r cũ /ph n t ch t. z rv • V i các hàng i ≠ r ta dùng phép bi n i: z jv * z rk z 'jk = z jk − z rv  z rk   z rv Ph n t ch t chia         nhân      z jk ?   z jv     zrv zrv zrv Bư c 7: Quay v bư c 2 zrv Ths c 0972 670 808 3 onthicaohoc_toankinhte@yahoo.com
*Lưu ý: Quy t c ch s bé nh t c a R.G.Bland *Trong các c t có ∆ dương thì ta ch n c t có ch s nh nh t * N u có nhi u λ r ch n thì ch n dòng có ch s nh nh t. Bài 5: Bài toán i ng u 1. Quy t c thành l p bài toán i ng u * Hàm m c tiêu c a Bài toán (BT) g c → min(max) ⇔ Hàm m c tiêu c a BT i ng u → min(max) * H s c a hàm m c tiêu c a BT g c là h s v ph i c a ràng bu c chung c a BT i ng u. H s v ph i c a ràng bu c chung c a BT g c là h s c a hàm m c tiêu c a BT i ng u * Ma tr n h s c a BT g c l y chuy n v thành ma tr n h s c a BT i ng u. * S ràng bu c chung c a BT g c là s bi n c a BT i ng u *Quy t c v d u như sau: D u m t ràng bu c chung c a bài toán g c quy nh d u c a m t ràng bu c bi n tương ng cùa BT i ng u D u m t ràng bu c bi n c a BT g c quy nh d u c a m t ràng bu c chung tương ng c a BT i ng u. Cách nh : Bài toán g c min: ràng bu c chung cùng d u, ràng bu c bi n trái d u. Bài toán g c max: ràng bu c chung trái d u, ràng bu c bi n cùng d u. Ví d : f (x) = x1 − 2x 2 + 3x 4 → min BT DN g(y) = 7y1 + y 2 − 2y3 → max  x1 + 3x 2 + 4x 3 + x 4 ≥ 7  y1 + 0y 2 + 5y3 ≤ 1  − x + 2x + 6x ≤ 1 3y − y + 5y ≥ −2  1 2 3 4 2 3   , y1 ≥ 0, y 2 ≤ 0, y3 tùy ý 5x1 + 5x 2 + x 3 + 8x 4 = −2 4y1 + 2y 2 + y3 = 0    x1 ≥ 0, x 2 ≤ 0, x 3 , x 4 tùy ý  y1 + 6y 2 + 8y3 = 3    1 0 5 1 3 4 1   3 −1 5    AT =  A =  0 −1 2 6   4 2 1 5 5 1 8      1 6 8 Ths c 0972 670 808 4 onthicaohoc_toankinhte@yahoo.com
2. Cách tìm PATU c a BT i ng u * T PATU c a Bài Toán g c (BT i ng u) x ' = (x '1 , x '2 ,..., x 'n ) ( hoac y ' = (y '1 , y '2 ,..., y 'n ) ) ta th vào các ràng bu c chung c a BT g c ( BT i ng u). * Ki m tra xem trong các ràng bu c chung BT g c n u ràng bu c nào không x y ra d u ‘=’ thì n tương ng trong BT i ng u s ‘=0’ * Ngư c l i n u trong PA x ' = (x '1 , x '2 ,..., x 'n ) c a BT g c, giá tr x i' > 0 thì phương trình th i trong BT i ng u s x y ra d u ‘=’. Ths c 0972 670 808 5 onthicaohoc_toankinhte@yahoo.com