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

Chia sẻ: Trần Bảo Quyên Quyên | Ngày: | Loại File: PDF | Số trang:22

Thêm vào BST

Báo xấu

5.443
lượt xem 1.254
download

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

Bài toán về quy hoạch tuyến tính giúp bạn ôn tập, hệ thống và nắm vững kiến thức, áp dụng chúng vào giải bài tập, chuẩn bị cho kì thi sắp tới đạt kết quả cao. Tài liệu đi kèm đáp án giúp bạn so sánh kết quả và tham khảo giải bài tập theo những cách khác nhau. Mời các bạn cùng tham khảo. Chúc các bạn thành công!

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 quy hoạch tuyến tính

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.
+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
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
.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 .
∑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.
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.
ð 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
.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 ñó
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 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.
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
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.
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:
~ 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:
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
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
=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
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
.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.
- 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:
~ 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: