Bài toán quy hoạch tuyến tính

Chia sẻ: tranbaoquyen

Bài toán về quy hoạch tuyến tính

Bạn đang xem 10 trang mẫu tài liệu này, vui lòng download file gốc để xem toàn bộ.

Nội dung Text: Bài toán quy hoạch tuyến tính

 

  1. 2.Bài toán quy ho ch tuy n tính (QHTT) Tình hu ng: M t công ty c n lên m t k ho ch qu ng cáo cho s n ph m c mình trên sóng phát thanh và sóng truy n hình. Chi phí cho 1 phút qu ng cáo trên sóng phát thành là 80.000 ñ, trên sóng truy n hình là 400.000 ñ. ðài phát thanh ch nh n qu ng cáo các chương trình dài ít nh t 5 phút. Còn ñài truy n hình ch nh n phát các chương trình t i ña 4 phút. Theo các phân tích xã h i hoc, cùng m t th i lư ng 1 phút qu ng cáo trên truy n hình s có hi u qu g p 6 l n trên sóng phát thanh. Công ty d ñ nh ch chi t i ña là 1.600.000 ñ cho qu ng cáo. H i c n ñ t th i lư ng qu ng có trên sóng phát thanh và sóng truy n hình như th nào cho ñ t hi u qu nh t? Mô hình hóa: G i th i lư ng công ty ñ t qu ng cáo trên sóng phát thanh là a phút. Trên sóng truy n hình là b phút . chi phí cho vi c này là 80.000*a + 400.000*b ≤ 1.600.000 ñ. Trong ñó; a ≥ 5; b ≤ 4; a ≥ 0; b ≥ 0. Hi u qu chung c a qu ng cáo là a + 6.b Bài toán: Xác ñinh a; b sao cho a + 6b Max V i ñi u ki n : 80.000*a + 400.000*b ≤ 1.600.000 ñ. a ≥ 5; b ≤ 4 và: a ≥ 0; b ≥ 0. Bài toán có c u trúc như trên là m t ví d v bài toán QHTT. Chú ý : do Maxf(x) = -Minf(x) nên t nay v sau ta ch nói t i bài toán tìm Minf(x) 2.1Các ñ nh nghĩa: Bài toán: Xác ñ nh véc tơ x = ( x1; x2 ;...; xn ) sao cho Trong ñó I1; I 2 ; I 3 là t p các ch s không giao nhau kí hi u i = I1 ∪ I 2 ∪ I 3 ; a ii ; b ii ; c j là các h s ; xj j:=1,2,…,n là các bi n. +Hàm f(x) g i là hàm m c tiêu +H (1.1) ñ n (1.4) g i là h ràng bu c ( h ñi u ki n) c a bài toán . V i m i ch s i ta có m t phương trình ho c b t phương trình tương ng và ñư c g i là ràng bu c th i.Các h s v trái trong m i ràng bu c th i là m t véc tơ dòng A * =(ai1; ai2;….;ain) . M t nhóm ràng bu c có h véc tơ Ai* ñ c l p tuy n tính ñư c g i là các i ràng bu c ñ c l p tuy n tính. xj ≥ 0; xj ≤ 0 g i là các ràng bu c v d u ñ i v i xj + Trong h t (1.1) ñ n (1.4) xét các ràng bu c không ph i là ràng bu c v d u các h s v trái tương ng v i m i ràng bu c này là m t ma tr n, ký hi u là A. Ma tr n A có n c t, m i c t này là m t véc tơ, ký hi u là Aj – chính là véc tơ các h s c a bi n xj Aj g i là véc tơ ñi u ki n ng v i bi n xj + Phương án: m t véc tơ x th a mãn h ràng bu c c a bài toán g i là m t phương án c a bài toán. Trong ràng bu c th i n u d u “=” x y ra thì ta nói phương án x th a mãn ch t ñ i v i ràng bu c th i; còn n u x y ra d u ≤ ho c (≥ ) thì phương án x là l ng ñ i v i ràng bu c th i + Phương án t i ưu: là phương án mà hàm m c tiêu ñ t ñư c Min + Phương án t t hơn N u f(x1) ≤ f(x2) thì phương án x1 g i là t t hơn phương án x2 M t bài toán t n t i phương án t i ưu g i là bài toán gi i ñư c, n u không có phương án t i ưu g i là bài toán không gi i ñư c.
  2. +Phương án c c biên: M t phương án th a mãn ch t n ràng bu c ñ c l p tuy n tính ñư c g i là phương án c c biên (PACB) * phương án c c biên th a mãn ch t ñúng n ràng bu c g i là phương án c c biên không suy bi n, th a mãn ch t hơn n ràng bu c g i là phương án c c biên suy bi n. Thí d 1: Cho .f(x) = x1 + x2 – 2x3 + x4 + x5 Min .x1 + x2 + x3 - x5 ≤ 40 (1) .-2x1 – 2x2 + 5x3 + 2x5 = 65 (2) .x2 + x3 +x4 + 2x5 ≥ 12 (3) .xj ≥ 0 v i j:=1,2,..,5 A1* = (1;1;1;0;−1) 1 1  1  0  − 1      * Ta có: A = (−2;−2;5;0;2) A1 =  − 2  ; A2 =  − 2 ; A3 =  5 ; A4 =  0 ; A5 =  2  2 0 1  1 1 2 * A3 = (0;1;1;1;2)      1 1 1 0 − 1 − 2 − 2 5 0 2  Ma tr n A =   0 1 1 1 2   V i x1 = ( 0; 0; 13; 0; 0) ; x2 = ( 0; 0; 1; 0; 30) ñây là hai phương án c a bài toán. Phương án x1 th a mãn ch t ñ i v i ràng bu c (2) và là l ng ñ i v i (1) và (3) và x3 ≥ 0 Phương án x2 th a mãn ch t ñ i v i (2) và l ng ñ i v i (1); (3) và x3 ≥ 0; x5 ≥ 0 Do f(x1) < f(x2) nên phương án x1 t t hơn th c s phương án x2 Thí d 2: f(x) = - x1 - 6x2 Min 80.000.x1 + 400.000x2 ≤ 1.600.000 .x1 ≥ 5; x2 ≤ 4 .x1 ≥ 0; x2 ≥ 0 Các phương án x1 = ( 5;3); x2 = ( 0;4); x3 = (20;0) là các phương án c c biên c a bài toán N u t t c các phương án c c biên c a bài toán ñ u không suy bi n thì bài toán g i là • không suy bi n; trái l i, g i là bài toán suy bi n. 2.2.Các d ng ñ c bi t c a bài toán QHTT a. D ng chính t c: n f ( x ) = ∑ c j x j ⇒ Min j =1 n ∑a x i = 1,2,..., m = bi ij j j =1 xj ≥ 0 j = 1,2,.., n * Nh n xét : M i bài toán QHTT ñ u có th ñưa v bài toán QHTT d ng chính t c tương ñương ( b ng cách thêm, b t m t lư ng không âm vào m i ràng bu c ñ có d u “ =” trong
  3. ràng bu c ñó). Khi y tr t i ưu c a hàm m c tiêu trong hai bài toán là trùng nhau, t phương án, phương án t i ưu c a bài toán này suy ra phương án, phương án t i ưu c a bài toán kia. Thí d 3: Bài toán thí d 1 tương ñương v i bài toán chính t c sau: f(x) = - x1 - 6x2 Min 80.000.x1 + 400.000x2 + x3 = 1.600.000 .x1 - x4 =5 .x2 + x5 = 4 .xj ≥ 0; j =1,2,..,5 b.ð c ñi m c a phương án c c biên c a bài toán d ng chính t c ð nh lý 1: Phương án x c a bài toán d ng chính t c là c c biên khi và ch khi h th ng các véc tơ {Aj } tương ng v i các thành ph n dương c a phương án là ñ c l p tuy n tính. ( Hi n nhiên vì khi ñó h các ràng bu c là h Crame nên có nghiêm duy nh t, hay nghi m ñó chính là m t phương án c c biên c a bài toán)  80.000   400.000  0      1 Trong thí d 3 phương án x = ( 5;3;0;0;1) có A1 =  1 ; A2 =  0  ; A5 =  0  là ba 0 1 1      véc tơ ñ c l p tuy n tính nên x1 là phương án c c biên. c. Cơ s c a phương án c c biên: ( v i bài toán d ng chính t c) M t h g m m véc tơ {Aj} ñ c l p tuy n tính bao hàm h th ng các véc tơ tương ng v i các thành ph n dương c a phương án c c biên x là cơ s c a phương án c c biên y, ký hi u m t cách quy ư c là j, trong ñó J = {J: Aj thu c cơ s } + V i phương án x = (x1;x2;,…,xn) g i thành ph n xj ( j ∈ J ) là thành ph n cơ s ; xk ( k ∉ J ) là thành ph n phi cơ s .D nh n th y các thành ph n phi cơ s c a phương án c c biên luôn b ng 0. M t phương án c c biên không suy bi n thì m i thành ph n cơ s ñ u dương, còn phương án c c biên suy bi n thì có ít nh t m t thành ph n cơ s b ng 0 trên phương án x1 là phương án c c biên (PACB) không suy bi n Trong thí d 3 d. Bài toán d ng chu n: N u bài toán dang chính t c trong ñó bi ≥ 0 v i m i i:=1,2,…,m và m i phương trình trong h ràng bu c ñ u có m t bi n s v i h s b ng 1 ñ ng th i bi n này khôn gcos trong các phương trình khác g i là bài toán có d ng chu n. 2.3. Các tính ch t c a bài toán QHTT Tính ch t 1: N u bài toán có phương án và h ng c a ma trân h ràng bu c b ng n ( n là s bi n s ) thì bài toán có phương án c c biên. Thí d 1: Cho bài toán QHTT: .f(x) = 3x1 + x2 + 2x3 + 6x4 Min -3x1 + 2x2 + 5x3 – x4 ≥ -16 3x2 + 2x3 + 7x4 =0 .x1 – 4x2 + 3x4 – x5 ≤ 34 2x1 - 6x3 + 2x4 ≥ -2
  4. .x1 ≥0 .x2 ≥0 .x3 ≥0 .x4 ≥0 .x5 ≥ 0 Ch ng t r ng bài toán có PACB. Gi i: D th y h ng c a ma trân h ràng bu c b ng 5, thêm n a x = ( 0; 0;0;0;0) là m t phương án v y theo tính ch t 1 suy ra bài toán có PACB. Tính ch t 2: N u bài toán có phương án và tr s c a hàm m c tiêu b ch n dư i khi f(x) Min trên t p phương án thì bài toán có phương án t i ưu. Thí du 2. Ch ng t bài toán trong thí d 1 có PACB t i ưu. Gi i: theo thí d 1 ta ñã ch ng t bài toán có PACB thêm n a do ràng bu c v d u ta suy ra f(x) ≥ 0 trên tâp phương án. V y theo tính ch t 2 ch ng t bài toán có PACB t i ưu. Tính ch t 3: S phương án c c biên c a bài toán QHTT là h u h n. 3. Phương pháp ñơn hình gi i bài toán QHTT 3.1.N i dung c a phương pháp. Xu t phát t m t PACB, ta tìm cách ñánh giá PACB ñó, n u nó chưa t i ưu thì tìm cách di chuy n sang m t phương án c c biên m i t t hơn, quá trình này ñư c ti p t c l p. Vì s phương án c c biên là h u h n, nên sau m t s h u h n bư c l p, ho c ta tìm ñư c phương án c c biên t i ưu, ho c là ta k t lu n bài toán không gi i ñư c vì hàm m c tiêu khôn gbij ch n. ðó là n i dung cơ b n c a phương pháp ñơn hình. 3.2. ð c ñi m c a phương án c c biên c a bài toán d ng chính t c. a. Quan h gi a phương án c c biên và phương án c a bài toán: Xét bài toán d ng chính t c n f ( x) = ∑ c j x j ⇒ Min j =1 n ∑a x i := 1,.., m = bi ij j j =1 xj ≥ 0 j := 1,2,..., n Và cho x0 là PACB v i cơ s J0 Ta ký hi u véc tơ g m các thành ph n cơ s c a PACB x0 là X j 0 (vi t theo c t) và ma trân các véc tơ cơ s là Aj 0 = [ Aj : j ∈ J 0 ] khi ñó x0 = 0 (∀k ∉ J 0 ) Do ñó : Aj0 X j0 = b → X j0 = A−01b k j Các véc tơ phi cơ s Ak v i k ∉ J 0 cũng phân tích ñư c qua cơ s J0 G i các h s phân tích ∑x c a Ak là xjk véc tơ h s phân tích tương ng là Xk như v y: Ak = Aj = AJ 0 X k jk j∈J 0 do ñó Xk = AJ−01 Ak .
  5. ∑c x Ư c lư ng c a bi n xk theo cơ s J0 ký hi u và ñư c xác ñ nh b i: ∆ k = v i: − ck j jk j∈ J 0 cj = {c j : j ∈ J 0 } V i nh ng xj ( j ∈ J 0 ) thì ư c lư ng c a nó ∆ j = 0 ð i v i cơ s J0 n u phương án ñang xét không là PACB t i ưu thì b ng phép ñ i cơ s ta s ñi t i m t phương án x biên t t hơn. 3.3.D u hi u t i ưu và các ñ nh lý cơ b n. ð nh lý 2: D u hi u t i ưu c a phương án c c biên N u ñ i v i PACB x0 v i cơ s J0 c a bài toán d ng chính t c mà: Min thì x0 là phương án t i ưu. ∆ k ≤ 0 (∀k ∉ J 0 ) v i bài toán f(x) Chú ý : ð nh lý 2 là ñi u ki n ñ , tuy nhiên n u x0 là PACB không suy bi n thì ñó cũng là ñi u ki n c n ñ x0 là phương án t i ưu. ð nh lý 3: D u hi u bài toán không gi i ñư c N u ñ i v i phương án c c biên x0 v i cơ s J0 c a bài toán d ng chính t c mà: T n t i ∆ k > 0 mà x jk ≤ 0 ∀k ∉ J 0 v i bài toán f(x) Min Thì bài toán không gi i ñư c ( Hàm m c tiêu không b ch n dư i) ð nh lý 4: D u hi u ñi u ch nh phương án c c biên. N u ñ i v i m t phương án c c biên x0 v i cơc s J0 c a bài toán d ng chính t c mà : v i m i ∆ k > 0 ñ u t n t i xjk > 0 v i bài toán f(x) Min thì ta có th ñi u ch nh phương án 0 c c biên x chuy n sang m t phương án c c biên t t hơn. 3.4.Công th c ñ i cơ s : Trong không gian Rn cho véc tơ x0 cho hai cơ s r r r α 1; α 2;….; α n (1) β 1; β 2;….; β n (2) n n x 0 = ∑ xiα i x0 = ∑ y j β j Gi s Tìm m i liên h gi a các t a ñ xj ; yj i =1 j =1 n G i T = (tij) là ma tr n chuy n t cơ s (1) sang cơ s (2) khi y β j = ∑ tijα i j = 1,2,.., n i =1 n n n n n n n Do ñó x 0 = ∑ xiα i = ∑ y j β j = ∑ y j ∑ tijα i = ∑ (∑ tij y j )α i V y: xi = ∑ tij y j i =1 j =1 j =1 i =1 i =1 j =1 j =1 3.4.Thu t toán c a phương pháp ñơn hình: Gi s bài toán ph i gi i là bài toán QHTT d ng chính t c, ñã bi t m t phương án c c biên x0 và cơ s J0 . không m t tính t ng quát ta gi s J0 g m m véc tơ ñ u tiên, t là cơ s g m m véc tơ A1,A2,…..,Am.
  6. Bư c 1: L p b ng ñơn hình ng v i phương án c c biên x0 H Cơ Phương .c1 c2………cr………..cm cm+1 cm+2 … ..ck……..cs……....cn S S án .x1 x2………xr…….xm xm+1 xm+2…….xk……..xs………xn cj J0 .c1 .x1 1 0 …… 0……..0 x1m+1 x1m+2……x1k…….x1s……..x1n x10 .c2 .x2 0 1………..0……..0 x2m+1 x2m+2……x2k…….x2s……..x2n 0 x2 … … …. ……………… …… ..……………………………. . cr .xr 0 0………..1……..0 xrm+1 xrm+2……xrk……..xrs……...xrn x r0 … … …. ………………………… ………………………………………. .cm .xm 0 0………..0…… 1 xmm+1 xmm+2 …….xmk…….xms……..xmn 0 x m .f(x) .f(x0) 0 0 ……….0……...0 ∆ m +1 ∆m+2 ∆k ∆s ∆n - Dòng cj là các h s c a các bi n trong hàm m c tiêu f(x) - C t cj là h s c a bi n xj ng v i véc tơ cơ s Ajx ∑c x - − ck thí d ∆ s = (c1.x1s + c2 x2 s + ... + cr xrs + ... + cm xms ) − cs ∆k = j jk j∈ J 0 Bư c 2: Ki m tra d u hi u t i ưu c a PACB Min thì x0 là phương án t i ưu - N u ∆k ≤ 0 ∀k ∉ J 0 v i bài toán f(x) N u ∃∆ k > 0 thì x0 không là phương án t i ưu, chuy n sang bư c 3 - Bư c 3: ki m tra tính không gi i ñư c c a bài toán. - N u ∃∆ k > 0 mà xjk ≤ 0 v i m i j ∈ J 0 v i bài toán f(x) min thì bài toán không gi i ñư c vì hàm m c tiêu có tr không b ch n dư i - N u v i m i ∆ k > 0 ñ u có ít nh t xjk > 0 thì chuy n sang bư c 4 Bư c 4: ði u ch nh PACB và l p b ng ñơn hình m i. - Ch n phương án ñưa vào cơ s : Tìm max ∆ k ∀∆ k > 0 gi s max ∆ k = ∆ s thì véc tơ As ñư c ñưa vào cơ s x0 x0 x0 - Tìm Min v i m i xjs > 0 ; j ∈ J 0 gi i s Min j = r khi y véc tơ Ar b lo i kh i j x js x js xrs cơ s . ph n t xrs g i là ph n t tr c và ñư c ñóng khung trong b ng - Bi n ñ i b ng: + L p b ng ñơn hình m i. thay véc tơ cơ s v a l a chon trên cs thay cho cr trong c t cj .xs thay cho xr trong c t cơ s + Tính các dòng m i ( b t ñ u t c t th 3 tr ñi) ð tính dòng ng v i dòng có véc tơ .xs m i ñưa vào trong b ng m i ta l y dòng ng v i véc tơ l y ra xr trong b ng cũ chia cho ph n t tr c. Dòng này g i là dòng chu n.
  7. ð tính dòng xj trong b ng m i ta l y dòng xj trong b ng cũ tr ñi dòng chu n sau khi ñã nhân dòng nó ( dòng chu n) v i xjs ð tính dòng cu i c a b ng m i, ta l y dòng cu i c a b ng cũ tr ñi dòng chu n sau khi nhân nó (dòng chu n) v i ∆ s Ti n trình trên ñư c l p l i sau h u h n bư c ta có k t lu n v l i gi i c a bài toán ñang xét. Thí d 1: Gi i bài toán QHTT sau: ⇒ min f ( x) = 4.x1 − 2.x2 + x3 − 3 x4 + x3 + x4 + 3 x5 = 16 x1 2 x1 − 3 x2 − 2 x3 + 2 x5 + x6 = 52 − 2 x5 = 24 x2 + x3 + x7 x j ≥ 0, j = 1,2,3,...,7 Bài toán ñã cho có d ng chu n, các bi n cô l p là x4;x6;x7 nên phương án c c biên là x0=(0;0;0;16;0;52;24) cơ s J0 là A4; A6; A7 ta l p ngay ñư c b ng ñơn hình sau B ng ñơn hình x0 0 0 0 16 0 52 24 x0' 4 -2 1 -3 0 0 0 Cj J Xj x1 x2 x3 x4 x5 x6 x7 -3 x4 16 1 0 1 1 3 0 0 0 x6 52 2 -3 -2 0 2 1 0 0 x7 24 0 [1] 1 0 -2 0 1 f(x) -48 -7 2 -4 0 -9 0 0 -3 x4 16 1 0 1 1 3 0 0 0 x6 52 2 0 1 0 -4 1 3 -2 x2 24 0 1 1 0 -2 0 1 f(x) -96 -7 0 -6 0 -5 0 -2 Phương án m i .x1= (0; 24; 0; 16; 0; 52) Sau khi k t thúc b ng 1 t dòng cu i ta th y phương án x0 chưa t i ưu do có ∆2 > 0 véc tơ A2 ñư c ñưa vào cơ s x7 Thêm n a Min{ } =24/1 nên véc tơ A7 ñư c ñưa ra kh i cơ s ph n t tr c là [1] trong x72 b ng 1 Note: Th c ch t trong b ng 1 các c t xj là t a ñ c a véc tơ Aj ñ i v i cơ s chính t c khi chuy n sang b ng 2 ta ñã ñ i cơ s {A4;A6;A2} trong b ng 2 các c t xj là t a ñ c a véc tơ Aj qua cơ s m i. Do ñó mu n tìm t a ñ c a các Aj qua cơ s m i ta ch vi c.Tìm ma tr n chuy n t cơ s m i sang cơ s chính t c ( bi u th tuy n tính các véc tơ chính t c qua cơ s m i r i l y ma tr n chuy n v c a ma trân các h s trong s bi u th trên), g i nó là ma trân T=(tij) ; khi y T.Aj =A’j trong ñó A’j là t a ñ c a Aj ñ i v i cơ s m i. T b ng 2 ta th y ∆k <0 v i m i k ∉ J 0 nên phương án x1 là t i ưu duy nh t. f(x1) = -96 Thí d 2: Gi i bài toán sau b ng phương pháp ñơn hình
  8. .f(x) = 2x1-3x2-x3 Min 2x1 – x2 + x3 ≤ 18 3x1 + x2 -2x3 ≤ 20 .x1 +2x2 ≤ 12 .x1≥ 0; .x2 ≥ 0; x3 ≥ 0 f ( x) = 2 x1 − 3 x2 − x3 ⇒ Min Ta ñưa v bài toán chính t c sau: 2 x1 − x2 + x3 + x4 = 18 3 x1 + x2 − 2 x3 + x5 = 20 x1 + 2 x2 + x6 = 12 x j ≥ 0 ∀j : 1,2,...,6 Bài toán có d ng chu n, các bi n cô l p x4; x5; x6 nên phương án c c biên x0 = ( 0;0;0;18;20;12) cơ s J0={A4;A5;A6} B ng ñơn hình H I J K L M N O P x0 0 0 0 18 20 12 26 2 -3 -1 0 0 0 27 Cj J Xj x1 x2 x3 x4 x5 x6 28 0 x4 18 2 -1 1 1 0 0 29 0 x5 20 3 1 -2 0 1 0 30 0 x6 12 1 [2] 0 0 0 1 31 f(x) 0 -2 3 1 0 0 0 32 0 x4 18 2.5 0 [1] 1 0 0.5 33 0 x5 20 2.5 0 -2 0 1 -0.5 34 -3 x2 -18 0.5 1 0 0 0 0.5 35 f(x) -18 -3.5 0 1 0 0 -1.5 36 -1 x3 24 2.5 0 1 1 0 0.5 37 0 x5 62 7.5 0 0 2 1 0.5 38 -3 x2 6 0.5 1 0 0 0 0.5 39 f(x) -42 -6 0 0 -1 0 -2 Phương án x2 =( 0;6;24;0;62;0) là phương án t i ưu duy nh t. Trên b ng tính Excel: dòng 34(dòng chu n) t c t K tr ñi ñư c thi t l p nh công th c K34= K30/$L$30 rê chu t tuy n tính theo dòng K34 ta có k t qu L34;M34:…P34. Dòng 32 :K32 = K28 –K34*$L$28 rê chu t như trên ñ có các k t qu c a các c t cùng dòng Dòng 33 Tương t như trên Dòng 35: K35 = K31-K34*$L$31 ð tính x2;x3;x5 ph i gi i h phương trình tương ng h ràng bu c ( các bi n khác ñ u b ng 0) 3.5.Các chú ý khi áp d ng thu t toán: + khi c n gi i bài toán f(x) Max thì ta gi i bài toán –f(x) Min + n u khi chon vecto ñưa vào cơ s ho c ñưa ra kh i cơ s có nhi u véc tơ thu c di n l a ch n thì tùy ch n m t trong s ñó
  9. x0 +Trư ng h p bài toán suy bi n có th d n t i min j = 0 v i m i xjs > 0 ; j ∈ J 0 v n th c hi n x js thu t toán m t cách bình thư ng + Khi áp d ng thu t toán c n lưu ý: Phương án x0 có cơ sơt J0 là cơ s ñơn v ( còn g i là cơ s chính t c), ma tr n i) các h s v trái trong h ràng bu c có các c t tương ng là t a ñ c a vecto Aj theo cơ s ñó. Ta l p ngay ñư c b ng ñơn hình. ðây là bài toán d ng chu n ii) Khi J0 không ph i là cơ s chính t c ta ph i tìm ma tr n các h s trong h ràng bu c phân tích qua cơ s chính t c J0 b ng cách bi n ñ i các dòng c a ma tr n b sung c a h ràng bu c làm xu t hi n cơ s J0. 4. Phương pháp tìm phương án c c biên: Có nh ng bài toán có d ng chính t c, nhưng không ph i d ng chu n, ñ ng th i ta chưa bi t PACB, do ñó mu n áp d ng thu n toán ñơn hình ta ph i tìm ñư c m t PACB c a nó. Xét bài toán d ng chính t c: n f ( x) = ∑ c j x j ⇒ Min j =1 n ∑a x i := 1,.., m (I) = bi ij j j =1 xj ≥ 0 j := 1,2,..., n Không m t tính t ng quát gi s bi ≥ 0 m i i = 1,2,…,m.(n u bi <0, nhân hai v v i -1) Xây d ng bài toán ph P b ng cách c ng vào v trái phương trình ràng bu c i m t bi n gi x ig ≥ 0 (i=1,2,..,m) v i hàm m c tiêu là t ng các bi n gi ñã thêm vào và hàm m c tiêu này ph i ñ t c c ti u. Ký hi u véc tơ các bi n gi là xg = ( x1g , x2 ,..., xm ) và hàm m c tiêu là P(x;xg) Ta có g g bài toán ph : m P( x; x g ) = ∑ xig ⇒ Min i =1 n ∑a x + xig = bi i = 1,2,..., m Bài toán này có d ng chu n và hàm m c tiêu luôn ij j j =1 xj ≥ 0 ∀j = 1,2,..., n x ≥0 ∀i = 1,2,...., m g i b ch n dư i nên luôn gi i ñư c b ng phương pháp ñơn hình, gi s ( x ; x g ) là phương án t i ưu c a bài toán ph và P ( x ; x g ) =Pmin i). n u Pmin > 0 Khi ñó bài toán (I) không có phương án. ii) n u Pmin = 0 khi ñó x là phương án c biên c a bài toán (I). ð áp d ng thu t toán cho bài toán (I) ta c n bi t cơ s J0 c a nó. Có hai trư ng h p sau: a).Trong cơ s c a phương án c c biên ( x ; x g = 0) không có các vectơ tương ng v i các bi n gi , khi ñó cơ s này cũng là cơ s c a phương án c c biên x . Ti n hành thu t toán bình thư ng.
  10. b). Trong cơ s c a phương án c c biên ( x ; x g = 0) có ít nh t m t vectơ tương ng v i các bi n gi , lúc này PACB là suy bi n. ð ti p t c gi i bài toán (I) ta lo i các c t ng v i ∆ j ( P) < 0 và các c t xig phi cơ s ra kh i b ng, sau ñó tính l i các ư c lư ng ∆k theo hàm f và ti p t c thu t toán. Chú ý: - Khi xây d ng bài toán ph ta ch c ng thêm bi n gi vào nh ng phương trình ràng bu c c n thi t ñ t o ra cơ s ñơn v trong ma tr n ñi u ki n. - N u trong quá trình gi i bài toán P, m t bư c ñi u ch nh nào ñó mà t t c các bi n gi ñ u b lo i ra kh i cơ s thì k t thúc vi c gi i bài toán ph P ( vì PACB bài toán (I) ñã tìm ñư c). Ti p t c gi i bài toán (I) v i PACB v a có. Thí d 1: Gi i bài toán sau b ng phương pháp ñơn hình: .f(x) = 3x1 +4x2 +2x3 + 2x4 Min 2x1 + 2x2 + x4 = 28 .x1 +5x2 + 3x3 – 2x4 ≤ 31 2x1 – 2x2 +2x3 + x4 = 16 .xj ≥ 0 ( j=1,..,4) Gi i: ðưa bài toán ñã cho v d ng chính t c: . f(x) = 3x1 +4x2 +2x3 + 2x4 Min 2x1 + 2x2 + x4 = 28 .x1 +5x2 + 3x3 – 2x4 + x5 = 31 2x1 – 2x2 +2x3 + x4 = 16 .xj ≥ 0 ( j=1,..,5) Bài toán không có d ng chu n nên ta ñưa ra bài toán ph (P) P(x,xg) = xg1 + xg3 Min + xg1 2x1 + 2x2 + x4 = 28 .x1 +5x2 + 3x3 – 2x4 + x5 = 31 xg3 2x1 – 2x2 +2x3 + x4 = 16 .xj ≥ 0 ( j=1,..,5) xg1≥ 0; xg2 ≥ 0 B ng ñơn hình hai pha
  11. H I J K L M N O P Q 46 f 3 4 2 2 0 47 P 0 0 0 0 0 1 1 48 Cj J Xj x1 x2 x3 x4 x5 xg1 xg3 49 1 xg1 28 2 2 0 1 0 1 0 50 0 x5 31 1 5 3 -2 1 0 0 51 1 xg3 16 [2] -2 2 1 0 0 1 52 P 44 4 0 2 2 0 0 0 53 1 xg1 12 0 [4] -2 0 0 1 54 0 x5 23 0 6 2 -2.5 1 0 55 0 x1 8 1 -1 1 0.5 0 0 56 P 12 0 4 -2 0 0 0 57 4 x2 3 0 1 -0.5 0 0 58 0 x5 5 0 0 5 -2.5 1 59 3 x1 11 1 0 0.5 0.5 0 60 f 45 0 0 -2.5 -0.5 0 M t bi n gi b lo i kh i cơ s ta b qua nó b ng ñơn hình ti p theo. Dòng 60 do không còn ph thu c bi n gi ta tính ∆k theo hàm f ( ch ng h n K60 = ($h$57*k57+$h$58*k58+$h$59*k59)-k46) tương t cho các c t còn l i c a dòng 60.
  12. CHƯƠNG VI: BÀI TOÁN ð I NG U (3) Trong th c t có nh ng c p bài toán QHTT có m i quan h m t thi t v i nhau, do v y t các k t qu nghiên c u ñư c c a bài toán này có th suy ra các k t qu tương ng c a bài toán kia và ngư c l i. ngư i ta g i c c c p bài toán như th là c p các bài toán ñ i ng u nhau. ð c bi t các c p bài toán ñ i ng u có n i dung th c t , vi c phân tích m i quan h gi a bài toán ban ñ u và bài toán ñ i ng u còn ñem l i nh ng thông tin có ý nghĩa lý lu n và th c hành. 1.Cách thành l p bài toán ñ i ng u: Bài toán ban ñ u Bài toán ñ i ng u ~ n m f ( x) = ∑ c j x j ⇒ Min( Max) f ( y ) = ∑ bi yi ⇒ Max( Min) j =1 i =1 .yi không có ràng bu c v d u n ∑a x = bi i ∈ I1 ij j i =1 n ∑a x ≥ (≤)bi i ∈ I2 yi ≥ 0 i ∈ I2 ij j i =1 n ∑a x ≤ (≥)bi i ∈ I3 yi ≤ 0 i ∈ I3 ij j i =1 m ∑a .xj không ràng bu c v d u j ∈ J1 yi = c j j ∈ J1 ij i =1 m xj ≥ 0 j ∈ J2 ∑a yi ≤ (≥)c j j ∈ J2 ij i =1 xj ≤ 0 m j ∈ J3 ∑a yi ≥ (≤)c j j ∈ J3 ij i =1 Thí d 1: Vi t bài toán ñ i ng u c a bài toán sau và ch ra các c p ràng bu c ñ i ng u: .f(x) = -4x1 + x2 + 5x3 + 3x5 Min 3x1 – 6x2 – x3 + 2x4 – 4x5 ≥ -15 (1) -2x1 +3x2 +4x3 +5x4 – x5 ≤8 (2) -6x2 + 3x3 +8x4 - 4x5 =9 3x1+2x2 -3x4 + x5 ≥ 24 (3) .x1 ≥ 0 (4); x3 ≤ 0 (5) x5 ≥ 0 (6) Gi i: Bài toán ñ i ng u:
  13. ~ f ( y ) = −15 y1 + 8 y2 + 9 y3 + 24 y4 ⇒ Max 3 y1 − 2 y2 + 3 y 4 ≤ −4 (7 ) − 6 y1 + 3 y2 − 6 y3 + 2 y4 = 1 − y1 + 4 y2 + 3 y3 ≥ 5 (8) 2 y1 + 5 y2 + 8 y3 − 3 y4 = 0 − 4 y1 − y2 − 4 y3 + y4 ≤ 3 (9) ≤0 (10) − y1 ≤0 (11) y2 y4 ≥ 0 (12) Các c p ràng bu c ñ i ng u là: (1-10);(2-11); (3-12);(4-7);(5-8);(6-9) Thí d 2: Vi t bài toán ñ i ng u c a bài toán sau: .f(x) = -3x1 +5 x2 + 4x3 -2x4 + x5 Max 2x1 – 3x2 – x3 + 6x4 – 2x5 +2x6 = -14 -x1 + 2x2 + 5x3 + 3x5 – 4x6 = 8 6x1- 3x2 + 2x3 - x4 + x5 + 3x6 = 12 3x1+2x2 -3x4 + x5 ≥ 24 .xj ≥ 0 j=1,2,…,6 2. Các tính ch t và ñ nh lý ñ i ng u: 2.1.Xét c p bài toán ñ i ng u v i các hàm m c tiêu: ~ f ( x ) ⇒ Min( Max) f ( y ) ⇒ Max( Min) Tính ch t 1: V i m i c p phương án x và y c a hai bài toán ñ i ng u ta luôn có ~ f ( x ) ≤ (≥ ) f ( y ) Tính ch t 2: N u ñ i v i hai phương án x* và y* c a m t c p bài toán ñ i ng u mà: ~ f ( x* ) = f ( y * )thì x*và y * tương ng là hai phương án t i ưu. ð nh lý 1: N u m t trong hai bài toán ñ i ng u mà gi i ñư c thì bài toán kia cũng gi i ñư c ~ và khi ñó v i m i phương án t i ưu x* , y* ta luôn có: f ( x* ) = f ( y* ) H qu 1: ði u ki n c n và ñ ñ hai bài toán ñ i ng u gi i ñư c là m i bài toán có ít nh t m t phương án. H qu 2: ði u ki n c n và ñ ñ m t bài toán có phương án còn m t bài toán không có phương án là tr s c a hàm m c tiêu c a bài toán có phương án không b ch n trên t p các phương án c a nó. ð nh ly 2: ði u ki n c n và ñ ñ hai phương án x và y c a m t c p bài toán ñ i ng u t i ưu là trong các c p ràng bu c ñ i ng u n u m t ràng bu c th a mãn v i d u b t ñ ng th c th c s (l ng) thì ràng bu c kia ph i th a mãn v i d u b ng (ch t) H qu 1: N u m t ràng bu c là l ng v i m t phương án t i ưu c a bài toán này thì ràng bu c ñ i ng u c a nó ph i là ch t ñ i v i phương án t i ưu c a bài toán kia. 2.2. M t s ng d ng c a tính ch t và các ñ nh lý ñ i ng u:
  14. a) Kh o sát s t n t i phương án, phương án t i ưu: Thí d 1: Cho bài toán QHTT .f(x) = 2x1 – x2 + 3x3 – 2x4 Min .x1 – x2 = 15 .x3 – x4 =8 .xj ≥ 0 m i j=1,2,3,4 Hãy vi t bài toán ñ i ng u và ch ng t nó có phương án t i ưu. Gi i: Bài toán ñ i ng u: ~ f ( y ) = 15 y1 + 8 y2 ⇒ Max ≤2 y1 ≤ −1 − y1 ≤3 y3 − y 4 ≤ −2 Ta nh n th y x* = ( 15;0;8;0) là m t phương án c a bài toán g c .y* = ( 1;2 ) là m t phương án c a bài toán ñ i ng u . V y theo h qu 1 ñ nh lý 1 suy ra hai bài toán này là gi i ñư c, hay c p bài toán có phương án t i ưu. Thêm n a h ng c a ma tr n h ràng bu c trong bài toán ñ i ng u b ng 2 nên nó có PACB t i ưu. Thí d 2: Cho bài toán QHTT .f(x) = x1 +2x2 + px3 – 2x4 + x5 Max 2x1 – x2 + x4 – x5 ≥ 4p +1 . x2 - x3 + 2x4 – x5 ≤ 32 .x1 - x2 + x3 + x5 = 18 .x3 ≥ 0; x4 ≥ 0 v i p là tham s . Hãy vi t bài toán ñ i ng u và d a vào bài toán này ñ bi n lu n theo tham s p v s t n t i phương án t i ưu c a bài toán g c. Gi i: Bài toán ñ i ng u: ~ f ( y ) = (4 p + 1) y1 + 32 y2 + 18 y3 ⇒ Min 2 y1 + y3 = 1 (1) − y1 + y2 − y3 = 2 (2) (3) − y2 + y3 ≥p y1 + 2 y2 ≥ −2 (4) − y1 − y2 + y3 = 1 (5) y1 ≤ 0; (6) y2 ≥ 0 (7 ) H phương trình t o b i các ràng bu c (1-2-5) cho ta h phương trình có nghi m duy nh t .y0 =( 0;3;1) nghi m này th a mãn các ràng bu c (4-6-7 ) cho nên nó tr thành m t phương án duy nh t n u th a mãn ràng bu c (3) và ta có ñó là phương án t i ưu. Thay vào (3) suy ra : p ≤ -2
  15. b)Phân tích tính ch t t i ưu c a m t phương án và xác ñ nh t p phương án t i ưu: Gi s v i m t phương án x c a bài toán g c, ta c n phân tích xem ñó có ph i là phương án t i ưu không? Gi s x là phương án t i ưu. v y theo ñ nh lý 2 (ñ i ng u) m i phương án t i ưu y c a bài toán ñ i ng u ph i th a mãn ch t các ràng bu c ñ i ng u v i các ràng bu c l ng c a phương án x bài toán g c. T p h p các ràng bu c ch t này t o thành m t h phương trình ñ i v i y. gi i h này, n u h vô nghi m thì x không th là phương án t i ưu. N u h có nghi m thì ph i th các nghi m này vào các ràng bu c còn l i c a bài toán ñ i ng u, n u m i nghi m ñ u không ph i là phương án thì x không là phương án t i ưu. N u có m t nghiêm y c a h là phương án c a bài toán ñ i ng u thì x là phương án t i ưu, ñ ng th i phương án y cũng t i ưu. Thí du 3: Cho bài toán: f(x) = 7x1 + 6x2 – 12x3 + x4 Max. 2x1 – 2x2 - 3x3 +2x4 = 8 (1) 3x2 + 2x3 – 2x4 ≤ -1 (2) 2x1 - 3x3 + x4 = 10 (3) .x1 ≥ 0 j=1,2,3,4 (4) Và vecto x = ( 0;6;0;10) Vi t bài toán ñ i ng u. phân tích các tính ch t c a x0 ñ i v i bài 0 toán ñã cho. Xác ñ nh t p phương án t i ưu c a bài toán. Ch ra m t phương án t i ưu không c c biên c bài toán g c. Gi i: Bài toán ñ i ng u ~ f ( y ) = 8 y1 − y2 + 10 y3 ⇒ Min 2 y1 + 2 y3 ≥ 7 (5) − 2 y1 + 3 y2 ≥ 6 (6) − 3 y1 + 2 y2 − 3 y3 ≥ −12 (7 ) 2 y1 − 2 y2 + y3 ≥ 1 (8) y2 ≥ 0 (9) .x0 th a mãn các ràng bu c c a bài toán g c, nên nó là m t phương án, thêm n a x0 th a mãn ch t các rang bu c(1-3) và hai ràng bu c d u ( x1=0; x3 = 0) , x0 th a mãn ch t 4 ràng bu c và nh ng ràng bu c này ñ c l p tuy n tính nên x0 là PACB không suy bi n. phương án x0 th a mãn lòng ràng bu c (2) và hai ràng bu c d u ( x2; x4). Gi s x0 là phương án t i ưu theo ñ nh lý 2 m i phương án t i ưu c a bài toán ñ i ng u ph i th o mãn: (chú ý: các c p ràng bu c ñ i ng u là (2-9);(d u x2--6) ;( d u x4- 8)) -2y1 + 3y2 =0 2y1 - 2y2 + y3 = 0 .y2 = 0 h có nghi m duy nh t y0 = ( -3;0;7) th y0 vào ràng bu c (5-7) ta th y nó th a mãn, y0 là phương án suy ra x0 là phương án t i ưu ñ ng th i y0 là phương án t i ưu và hơn n a là phương án t i ưu duy nh t. Phương án y0 ch th a mãn l ng ràng bu c 5 nên m i phương án t i ưu x ph i th a mãn
  16. =0 x1 − 2 x1 − 3 x2 + 2 x3 = 8 gán cho x4 tham s và gi i h có − 3 x3 + x4 = 10 1 10 1 .x = (0;1 + ; x4 ) Th x vào ràng bu c (2) còn l i: ;− + 2 x4 3 3 x4 3x2 +2x3 -2x4 ≤ -1 suy ra 3 +3/2.x4 -20/3 +2/3.x4 -2x4 ≤ -1 hay x4 ≤ 16 Thêm n a x2 = 1 +1/2.x4 ≥ 0 suy ra x4 ≥ -2; x3 = -10/3 +1/3.x4 ≥ 0 suy ra x4 ≥ 10 Tóm l i : 10 ≤ x4 ≤ 16. V i ñi u ki n này x là phương án ñ ng th i là phương án t i ưu c a bài toán g c. M t phương án t i ưu không c c biên c a bài toán g c là PACB mà các véc tơ c t trong h ràng bu c tương ng v i các thành ph n dương c a phương án không ñ c l p tuy n tính. ch ng h n; x = (0;15/2;1;13) .x4 = 0;16 có hai PACB t i ưu tương ng
  17. CHƯƠNG VII: BÀI TOÁN V N T I (9+2+1) 1.N i dung và các ñ c ñi m: 1.1.N i dung kinh t và d ng toán h c: a)Bài toán: Gi s ta c n v n chuy n m t lo i hàng hóa thu n nh t t m ñ a ñi m nào ñó t i n v trí khác nhau có nhu c u v lo i hàng hóa ñó ( ta hi u hàng hóa ñây có th là các d ng v t ch t thông thư ng, cũng có th là lo i ñ c thù như v n, lao ñ ng, thông tin,…). Ta ký hi u nơi cung c p hàng là Ai ( i=1,2,…,m) và g i chúng là các tr m phát, n nơi có nhu c u là Bj j=1,2,…,n và g i chúng là các tr m thu. Lư ng hàng hóa cung ng tr m phát Ai là ai ñơn v , lư ng hàng hóa yêu c u tr m thu Bj là bj ñơn v . Gi s chi phí v n chuy n m t ñơn v hàng hóa t tr m phát Ai t i tr m thu Bj là cij ≥ 0 ( khái ni m chi phí hi u theo nghĩa r ng có th là chi phí th c, có th là ñ dài quãng ñư ng t Ai ñ n Bj , ho c s hao phí nhiên li u, ho c th i gian c n thi t ñ v n chuy n,…. Bài toán ñ t ra là tìm phương án th c hi n vi c v n chuy n hàng hóa nói trên sao cho chi phí là nh nh t. G i xij là lư ng hàng hóa chuy n t tr m phát Ai ñ n tr m thu Bj ( xij ≥ 0). Yêu c u m ∑x c a tr m thu ñ u th a mãn ñ y ñ nghĩa là j = 1,2,.., n ; hàng hóa t t c các = bj ij i =1 tr m phát ñ u ñư c s d ng h t ñ ñáp ng yêu c u c a các tr m thu nên n m n ∑ xij = ai i = 1,2,.., m . Khi ñó t ng chi phí v n chuy n s là : ∑∑ cij xij Bài toán có mô j =1 i =1 j =1 hình như sau g i là bài toán v n t i: Tìm h th ng {xij} ( i=1,2,..,m; j=1,2,…,n) sao cho: m n f ( x) = ∑ ∑ cij xij ⇒ Min (1) i =1 j =1 n ∑x i = 1,2,.., m (2) = ai ij j =1 m ∑x (3) j = 1,2,.., n = bj ij i =1 .xij ≥ 0 m i i;j (4) n m ∑b = ∑ ai N u: Ta có bài toán cân b ng thu phát (bài toán có d ng chính t c) j j =1 i =1 n n m > ∑ b j Thì (2) thay b i: ∑x ∑ ai i = 1,2,.., m Nu ≤ ai ij j =1 j =1 i =1 n m m < ∑ b j Thì (3) thay b i ∑ ai ∑x Nu j = 1,2,.., n ≤ bj ij j =1 i =1 i =1 B ng cách thêm bi n ph m i bài toán ñ u có th ñưa v bài toán cân b ng thu phát. ( có th dùng thu t toán ñơn hình ñ gi i, song do có nhi u bi n nên ph c t p.) b. Các ñ c ñi m c a bài toán: * Bài toán cân b ng thu phát luôn có phương án c c biên t i ưu * Mô t bài toán dư i d ng b ng: Thu .b1 .b2 ………………….. .bn Phát .a1 .c11 .c12 ……………….. .c1n
  18. .a2 .c21 .c22 …………………. .c2n …………. …… ……. ………………… ….. .am .cm1 .cm2 ………………. .cmn Cho x ={xij} ( i=1,2,…,m; j=1,2,…,n) là phương án c a bài toán. N u xij > 0 thì ta gi giá tr này vào góc dư i phía ph i c a ô (i;j); n u xij = 0 thì không ghi. V y ng v i m t phương án ta có m t t p h p các ô tương ng v i các thành ph n dương c a phương án. N u phương án x là c c biên thì h véc tơ ñi u ki n {Aij } tương ng v i thành ph n xij >0 s ñ c l p tuy n tính. Ta g i là vòng m t t p h p ô trên b ng mà trong ñó m i ô ñ u n m cùng hàng (cùng c t) ch v i m t ô ñ ng trư c ñó, ñ ng th i n m cùng c t ( cùng hàng) ch v i m t ô ñ ng sau nó. Như v y m t hàng ho c m t c t mà vòng ñi qua thì ph i ch qua hai ô, do ñó t ng s ô trong vòng là m t s ch n ( ít nh t là 4 ô) .M t t p h p ô không ch a vòng g i là t p ô không t o thành vòng. Ngư i ta ch ng minh ñư c r ng: ð nh lý : ð c ñi m c a phương án c biên Phương án x={xij} ( i=1,2,…,m; j=1,2,…,n) là phương án c c biên khi và ch khi t p h p các ô (i;j) tương ng v i xiJ > 0 không t o thành vòng. Do h ng c a ma tr n h ràng bu c là m + n -1nên m t phương án c c biên t i ưu có t i ña m +n -1 thành ph n dương và do ñó s t i ña các ô trong b ng không t o thành vòng cũng b ng m +n -1. N u x là phương án c c biên ta g i m +n -1 ô không t o thành vòng là t p h p ô cơ s ( ô ch n), các ô còn l i g i là ô phi cơ s ( ô lo i) c a phương án c biên x. 2. Xây d ng phương án c c biên: 2.1. Nguyên t c phân ph i t i ña: Khi xây d ng PACB ng v i m t ô ij nào ñó ta gán cho xil = α . ta nói ñã phân ph i cho ô (i,j) m t lư ng hàng hóa là α và gi α vào ô này. - L y m t ô (i,j) tùy ý và phân ph i cho nó lư ng hàng hóa t i ña có th , t c là α = min{ai;bj}. khi ñó : + N u xiJ = α = ai yêu c u c a tr m phát Ai ñư c th a mãn, lo i hàng i ra kh i b ng, s a l i yêu c u c a tram thu b’j = bj – α + N u xij = α = bj yêu c u c a tr m thu Bj ñư c th a mãn, lo i c t j ra kh i b ng, s a l i yêu c u c a tr m phát a’i = ai – α + N u xij = α =ai = bj thì yêu c u c a tr m phát và thu ñ u th a mãn, lo i hàng i c t j ra kh i b ng. Ti p t c như trên cho t i khi yêu c u c a m i tr m thu, phát ñ u th a mãn. Các ô ñư c phân ph i có xij > 0 khi ñó t p h p x ={xij} ( i=1,2,…,m; j=1,2,…,n) là m t phương án c a bài toán vì chúng th a mãn m i ràng bu c. hơn n a nó còn là phương án c c biên, t p h p các ô ñư c phân ph i chính là t p h p ô cơ s . N u phân ph i ñư c ñúng m +n - 1 ô thì PACB tương ng không suy bi n, n u ít hơn m+n-1 ô thì ñó là PACB suy bi n, ñ có ñư c t p h p ô cơ s c n b sung s ô cho t i khi ñ m+n-1 ô, ô b sung có xij =0 và không t o thành vòng v i nh ng ô cơ s ñã có. 2.2.Các phương pháp xây dưng phương án c c biên: S d ng nguyên t c phân ph i t i ña, tùy thu c vào cách ưu tiên phân ph i ta có nh ng phương pháp khác nhau ñ xây d ng phương án c c biên.
  19. - phương pháp góc tây – b c: Luôn ưu tiên phân ph i cho ô n m góc tây-b c c a b ng ( góc trên bên trái b ng). Phương pháp này không quan tâm t i chi phí mà th c hi n máy móc theo s phân b c a các tr m trên b ng. - Phương pháp chi phí nh nh t (ñư ng g n) Luôn ưu tiên phân ph i cho ô có ciJ nh nh t trong b ng ñang xét. Phương án c c biên thu ñư c t phương pháp này g n v i phương án t i ưu hơn. Thí d 2: Thu 30 20 25 35 40 Phát 30 13 7 6 2 12 [30] 20 5 1 10 5 11 [20] 40 10 5 3 7 14 [0] [5] [35] 60 6 3 2 11 10 [30] [25] [5] Ô (2;2) có cư c phí c22 =1 nh nh t nên ưu tiên phân ph i th a yêu c u thu và phát, lo i dòng 2, c t 2 . Ô (1;4) có c14 = 2 ñư c ưu tiên th hai l y c a tr m phát A1 là a1 = 30 , tr m thu B4 còn c n lư ng hàng là 35 -30 =5 Ch có th l y t các tr m phát còn hàng do ô (3;4) có cư c phí nh nh t trong các ô cùng c t, l y 5 ñơn v hàng hóa t tr m phát A3,…… K t qu trên ñã phân ph i cho 7 ô ta ñư c m t phương án c c biên suy bi n. ð có t p ô là cơ s c n b sung thêm m t ô v i x j = 0 ch ng h n ô (3;2) 3. Phương pháp th v gi i bài toán v n t i. 3.1. Bài toán ñ i ng u và tiêu chu n t i ưu: Xét bài toán v n t i: m n f ( x) = ∑ ∑ cij xij ⇒ Min (1) i =1 j =1 n ∑x i = 1,2,.., m (2) = ai ij j =1 m ∑x (3) j = 1,2,.., n = bj ij i =1 .xij ≥ 0 m i i;j (4) Ký hi u ui; vj là các bi n ñ i ng u ñ i v i h ràng bu c (2) và (3); u = {ui}; v = {vj}; ~ f (u; v ) là hàm m c tiêu c a bài toán ñ i ng u, ñ ti n cho vi c gi i thích ý nghĩa kinh t ta ñ i d u h ràng bu c (2). Khi ñó bài toán ñ i ng u có d ng:
  20. ~ n m f (u; v) = ∑ b j v j − ∑ aiui ⇒ Max j =1 i =1 v j − ui ≤ cij ∀i; j Trong c p bài toán ñ i ng u này có m*n c p ràng bu c ñ i ng u: xij ≥ 0 và vj – ui ≤ cij i=1,2,..,m; j =1,2,..,n ð nh lý: Tiêu chu n t i ưu ði u ki n c n và ñ ñ phương án x = {xij} c a bài toán v n t i t i ưu là t n t i h th ng {ui;vj} th a mãn ñi u ki n: i) vj – ui ≤ cij ( v i m i i, j) ii) vj –ui = cij n u xij > 0 Tr s c a các ui; vj trong tiêu chu n g i là các th v hàng và c t Bài toán ñ i ng u có ý nghĩa kinh t hi u như sau: xem th v hàng ui là giá tr m t ñơn v hàng hóa t i nơi s n xu t Ai , còn th v vj là giá tr m t ñơn v hàng hóa t i nơi tiêu th Bj . ði u ki n ii) cho th y trong m t phương án v n chuy n t i ưu m t ñơn v hàng hóa t i nơi tiêu th có giá tr b ng giá tr m t ñơn v hàng hóa t i nơi s n xu t c ng thêm chi phí v n chuy n c j. ði u ki n i) cho th y chênh l ch v giá tr hàng hóa gi a nơi tiêu th và nơi s n xu t b t kỳ ñ u không vư t quá chi phí v n chuy n gi a hai nơi y. 3.2. Thu t toán c a phương pháp th v : Bư c 1: xây d ng phương án c c biên S d ng m t trong các phương pháp xây d ng phương án c c biên ñã bi t ( ch ng h n phương án chi phí nh nh t) ký hi u phương án là x0 ( có ñ m + n -1 thành ph n cơ s ) Bư c 2: Xây d ng h th ng th v {ui, vi}: -L y m t hàng i b t kỳ, cho nó m t th v tùy ý ( thư ng là ui = 0 ). Các th v hàng, c t còn l i xác ñ nh theo công th c: vj = ui + ciJ ; ui ñã bi t và (i,j) ∈ S 0 .ui = vj – cij , vj ñã bi t và (i,j) ∈ S0 Bư c 3: ki m tra tiêu chu n t i ưu Theo cách xây d ng, h th ng th v {ui, vj } th a mãn ñi u ki n ii) ñ i v i các ô cơ s (i,j) ∈ S0 do ñó ch c n ki m tra ñi u ki n i) ñ i v i các ô phi cơ s (i,j) ∉ S 0 n u chúng th a mãn ñi u ki n i) thì phương án x0 tương ng là phương án t i ưu. N u có m t ô phi cơ s (i,j) ∉ S 0 mà vj – ui > cij thì hi n nhiên x0 chưa là phương án t i ưu. G i nh ng ô này là ô vi ph m. Tính ñ i lư ng: ∆ ij = v j − ui − uij . Bư c 4: ði u ch nh phương án. Gi s Max ∆ ij = ∆ rk (r , k ) ∉ S0 ô (r,k) ñư c ch n làm ô ñi u ch nh , ô (r,k) s t o ∆ ij > 0 thành vòng duy nh t v i m t s ô thu c S0. Tìm vòng này và ký hi u là V . Trên vòng ñánh d u ô l , ch n sen k nhau b t ñ u t ô (r,k) là ô l . ký hi u là Vl; Vc 0 0 0 -Tìm Min xij ; (i, j ) ∈ Vc Gi s Min xiJ = xst = q (i, j ) ∈ Vc rõ ràng q ≥ 0 và q g i là lư ng ñi u ch nh. -Th c hi n phép bi n ñ i trên vòng V theo công th c:
Theo dõi chúng tôi
Đồng bộ tài khoản