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

0
725
lượt xem
175
download

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

Mô tả tài liệu
  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ủ đề:
Lưu

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

  1. 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
  2. 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
  3. 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’) <= f(x) L p b ng ơn hình m i t b ng ơn hình cũ như sau a) Ch n n ưa vào h n cơ b n Ch n s sao cho ∆ v = max {∆ k ∆ k > 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
  4. *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
  5. 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
Đồng bộ tài khoản