Tiểu luận: Thuật toán Gomory

Chia sẻ: Văn Hiệp | Ngày: | Loại File: PDF | Số trang:26

Thêm vào BST

Báo xấu

196
lượt xem 43
download

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

Ảnh hưởng của sai số làm tròn có thể dẫn đến lời giải sai khi dùng phương pháp đơn hình giải bài toán quy hoạch tuyến tính. Khi giải bài toán quy hoạch tuyến tính nguyên ảnh hưởng sai số làm tròn tăng mạnh

Chủ đề:

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

Lưu

Nội dung Text: Tiểu luận: Thuật toán Gomory

TRƯ NG Đ I H C BÁCH KHOA HÀ N I VI N TOÁN NG D NG VÀ TIN H C ------------------------- THU T TOÁN GOMORY T I ƯU T H PI Chuyên ngành : TOÁN TIN NG D NG Th y hư ng d n: TS. NGUY N QUANG THU N Sinh viên th c hi n: GIÁP VĂN HI P L p: TOÁN TIN 2 - K54 HÀ N I - 2012
T i ưu t h p I Giáp Văn Hi p M cl c 1 L i nói đ u 3 2 Nh c l i m t s ki n th c trong quy ho ch tuy n tính 4 2.1 Đi u ki n t i ưu . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Thu t toán đơn hình gi i bài toán quy ho ch tuy n tính chính t c . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.3 B ng đơn hình . . . . . . . . . . . . . . . . . . . . . . . . 6 2.4 Thu t toán đơn hình d ng b ng . . . . . . . . . . . . . . . 7 2.5 Thu t toán đơn hình hai pha . . . . . . . . . . . . . . . . 8 3 Thu t toán Gomory 8 3.1 Bài toán quy ho ch nguyên . . . . . . . . . . . . . . . . . 8 3.2 Ý tư ng c a thu t toán Gomory . . . . . . . . . . . . . . . 9 3.3 Áp d ng thu t toán Gomory đ gi i bài toán quy ho ch tuy n tính nguyên . . . . . . . . . . . . . . . . . . . . . . . 13 3.3.1 Thu t toán Gomory . . . . . . . . . . . . . . . . . 14 3.3.2 Ví d . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.4 Cài đ t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4 K t lu n 25 5 Tài li u tham kh o 26 2
T i ưu t h p I Giáp Văn Hi p 1 L i nói đ u Quy ho ch nguyên là mô hình toán h c c a r t nhi u bài toán n y sinh trong th c t như bài toán pha c t v t li u, bài toán v i đi u ki n không chia c t đư c, các bài toán v i đi u ki n logic. Khác v i bài toán quy ho ch tuy n tính thông thư ng, bài toán quy ho ch nguyên r t kh gi i. Th c t chưa có m t thu t toán nào h u hi u đ gi i t t c các bài toán quy ho ch nguyên. 3
T i ưu t h p I Giáp Văn Hi p 2 Nh c l i m t s ki n th c trong quy ho ch tuy n tính Xét bài toán quy ho ch tuy n tính d ng chính t c không suy bi n min{ c, x |x ∈ D} (P 1) trong đó c ∈ Rn \ {0}, và t p ch p nh n đư c D = {x ∈ Rn |Ax = b, x ≥ 0}, trong đó b = (b1 , · · · , bm )T ≥ 0, A là ma tr n c p m × n v i các c t A1 , · · · , Am . Gi s ta đã bi t phương án c c biên không suy bi n x0 = (x0 , · · · , xn )T ∈ D. Ký hi u 1 1 J(x0 ) = {j ∈ {1, · · · , n}|x0 > 0} j là t p ch s cơ s c a ma tr n A ng v i phương án c c biên không suy bi n x0 . Do h véc tơ {Aj |j ∈ J(x0 )} đ c l p tuy n tính nên v i m i k ∈ {1, · · · , n} ta có Ak = zjk Aj (1) j∈J(x0 ) Đ nh nghĩa 2.1. Ta g i ∆k = zjk cj − ck k ∈ {1, · · · , n}, j∈J(x0 ) đư c g i là ư c lư ng c a bi n xk . 2.1 Đi u ki n t i ưu Đ nh lý 2.1. N u phương án c c biên x0 th a mãn ∆k ≤ 0 v i m i k ∈ J(x0 ) / thì phương án x0 là m t phương án t i ưu c a bài toán quy ho ch tuy n tính chính t c (P 1). H qu 2.1. Gi s x0 là phương án t i ưu c a bài toán quy ho ch tuy n tinh (P 1). i) N u ∆k < 0 v i m i k ∈ J(x0 ) thì x0 là phương án t i ưu duy nh t. / ii) N u t n t i k ∈ J(x0 ) sao cho ∆k = 0 thì x0 không là phương án t i / ưu duy nh t. 4
T i ưu t h p I Giáp Văn Hi p Đ nh lý 2.2. Cho x0 là m t phương án c c biên c a bài toán quy ho ch tuy n tính d ng chính t c (P 1). Khi đó, i) N u t n t i k ∈ J(x0 ) sao cho / ∆k > 0 và zjk ≤ 0 ∀j ∈ J(x0 ) thì hàm m c tiêu gi m vô h n trên t p ch p nh n đư c và bài toán không có l i gi i, ii) N u t n t i k ∈ J(x0 ) sao cho / ∆k > 0 và ∃j ∈ J(x0 ) sao cho zjk > 0 thì ta có th chuy n đư c t i phương án c c biên x1 t t hơn phương án c c biên x0 . 2.2 Thu t toán đơn hình gi i bài toán quy ho ch tuy n tính chính t c Thu t toán đơn hình đ gi i bài toán quy ho ch tuy n tính d ng chính t c khi đã bi t m t phương án c c biên x0 . Bư c kh i t o: Xu t phát t m t phương án c c biên x0 và cơ s Aj , j ∈ J(x0 ) tương ng. Tính • Tính giá tr hàm m c tiêu f (x0 ) = cj x0 j j∈J(x0 ) • Vơi m i k ∈ J(x0 ), xác đ nh zjk b ng cách gi i h / zjk Aj = Ak j∈J(x0 ) và tính ư c lư ng ∆k = zjk cj − ck j∈J(x0 ) Thu t toán 2.1 Bư c 1: Ki m tra t i ưu If ∆k ≤ 0 v i m i k ∈ J(x0 ) Then D ng thu t toán (x0 là nghi m t i / ưu) Else Chuy n sang Bư c 2. Bư c 2: Ki m tra hàm m c tiêu c a bài toán không b ch n 5
T i ưu t h p I Giáp Văn Hi p If T n t i k ∈ J(x0 ) sao cho ∆k > 0 và zjk ≤ 0, ∀j ∈ J(x0 ) / Then D ng thu t toán (Bài toán không có nghi m t i ưu.) Else Chuy n sang Bư c 3. Bư c 3: Xâu d ng phương án c c biên m i • Tìm véc tơ As đ đưa vào cơ s m i, trong đó ch s s đư c ch n theo tiêu chu n ∆s = max{∆k |∆k > 0}. • Tìm véc tơ Ar đ đưa ra kh i cơ s cũ v i ch s r đư c xác đ nh b i công th c (2.8) x0j x0 θ0 = min |zjs > 0 = r . zjs zrs • Xây d ng phương án c c biên m i là x1 theo công th c x0   x0 − z r zjs ,  j ∀j ∈ J(x0 )(trong đó x1 = 0) r rs x1 = j 0, / 0 ∀j ∈ J(x ) và j = s  x0  r, zrs j=s v i t p ch s cơ s m i là J(x1 ) = J(x0 ) \ {r} ∪ {s}. • Đ t x0 := x1 và quay l i Bư c kh i t o. 2.3 B ng đơn hình Thu t toán đơn hình thư ng đư c bi u di n dư i d ng b ng. M i bư c ng v i m t phương án c c biên là m t b ng đơn hình. Gi s x0 = (x0 , x0 , · · · , x0 )T là m t phương án c c biên ng v i b ch s cơ s JB = 1 2 n 0 J(x ) = {j1 , j2 , · · · , jm } và cơ s đơn v B = {Aj1 , Aj2 , · · · , Ajm }. Các thông tin v x0 đư c ghi b ng dư i đây. H s Cơ s Phương c1 · · · ck · · · cn θ CB B án A1 · · · Ak · · · An cj1 Aj1 x01 j zj1 1 · · · zj1 k · · · zj1 n θj1 . . . . . . . . . . . . . . . . . . . . . cj Aj x0j zj · · · zjk · · · zjn θj . . . . . . . . . . . . . . . . . . . . . 0 cjm Ajm xjm zjm 1 · · · zjm k · · · zjm n θjm f (x0 ) ∆1 · · · ∆k · · · ∆n 6
T i ưu t h p I Giáp Văn Hi p 2.4 Thu t toán đơn hình d ng b ng Thu t toán 2.2 Bư c 1: Bư c chu n b Xây d ng b ng đơn hình xu t phát tương ng v i phương án c c biên xu t phát x0 . Bư c 2: Ki m tra đi u ki n t i ưu Xét dòng cu i c a b ng đơn hình IF ∆k ≤ 0 v i m i k = 1, 2, · · · , n Then D ng thu t toán , k t lu n nghi m t i ưu là phương án c c biên ng v i b ng này ELSE chuy n sang Bư c 3. Bư c 3: Ki m tra bài toán không có l i gi i IF T i t i k ∈ JB sao cho ∆k > 0 và zjk ≤ 0 v i m i j ∈ JB Then D ng / thu t toán, k t lu n bài toán không có l i gi i ELSE chuy n sang bư c 4. Bư c 4: Th c hi n: • Tìm c t xoay. Tìm ch s s th a mãn ∆s = max{∆k |∆k > 0}. Khi đó c t tương ng v i véc tơ As s đưa vào cơ s m i. • Tìm dòng xoay. Tính các θj , j ∈ JB , như sau zj zjs n u zjs > 0, j ∈ JB θj = +∞ n u zjs ≤ 0, j ∈ JB và xác đ nh ch s r th a mãn θr = min{θj |j ∈ JB } khi đó dòng r g i là dòng xoay. Ph n t zjs n m trên dòng xoay và c t xoay đư c g i là ph n t chính c a phép quay. Các ph n t zjs , (j = r) đư c g i là các ph n t xoay. Bư c 5: Chuy n b ng đơn hình tương ng v i phương án c c biên m i • Trong c t h s CB thay giá tr cr b i cs . Trong c t h s cơ s thay tên Ar b i As . • Dòng xoay m i đư c tính theo quy t c là Dòng quay (cũ) Dòng chính (m i) := ; ph n t chính • Các dòng còn l i đư c tính như sau Dòng m i := Dòng cũ tương ng − Dòng chính × Ph n t quay tương ng. 7
T i ưu t h p I Giáp Văn Hi p • Quay l i Bư c 1. 2.5 Thu t toán đơn hình hai pha Xét bài toán ph min g(x, u) = u1 + u2 + · · · + un v.đ.k x ∈ D (P 2) trong đó D = {(x, u) ∈ Rn+m |Ax + u = b, (x, u) ≥ 0}. Pha 1. Gi i bài toán quy ho ch tuy n tính ph (P 2) nh n đư c phương án t i ưu là (x0 , u0 ). IF g(x0 , u0 ) > 0 Then D = ∅, D ng thu t toán ELSE x0 là phương án c c biên c a bài toán (P 1). Chuy n sang Pha 2. Pha 2. Gi i bài toán (P 1) b ng phương pháp đơn hình v i phương án c c biên x0 v i b ng đơn hình Pha 2 thay b ng b ng đơn hình Pha 1 nhưng có m t s bi n đ i sau: • Xóa t t c các c t tương ng v i bi n gi ; • Thay c t CB b i h s s m c tiêu cơ s tương ng vơi bài toán g c. • Thay các h s m c tiêu c a bài toán ph dòng 1 b ng h s m c tiêu c a bài toán g c; 3 Thu t toán Gomory 3.1 Bài toán quy ho ch nguyên Xét bài toán quy ho ch nguyên đư c phát bi u như sau min f (x) = f (x1 , · · · , xn ) v.đ.k x = (x1 , · · · , xn ) ∈ D, (P 3) trong đó D ∈ Rn là t p các véc tơ x = (x1 , · · · , xn )T mà m t s ho c t t c các thành ph n c a x ch nh n giá tr nguyên. i) N u mà t t c các thành ph n c a bi n x nh n giá tr nguyên thì ngư i ta g i là bài toán (P 2) là bài toán quy ho ch nguyên hoàn toàn. ii) N u ch có m t s thành ph n c a bi n x nh n giá tr nguyên thì ngư i ta g i bài toán (P 2) là bài toán quy ho ch nguyên b phân. Ta s đi gi i bài toán quy ho ch nguyên hoàn toàn. n min cj xj (P 4) j=1 8
T i ưu t h p I Giáp Văn Hi p v.đ.k n zjk xj = bj (i = 1, · · · , m) j=1 xj ≥ 0 (j = 1, · · · , n) xj nguyên (j = 1, · · · , n) Ví d 1. Xét bài toán quy ho ch tuy n tính nguyên sau min x1 + 4x2 v i các ràng bu c    2x1 +4x2 +x3 =7 10x1 +3x2 +x4 = 15   x1 , x2 ≥ 0  x1 , x2 nguyên  3.2 Ý tư ng c a thu t toán Gomory Hình 1: (a) T p ch p nh n đư c c a bài toán g c; (b) Sau khi s d ng Gomory Ý tư ng c a thu t toán Gomory là ta c t t p ch p nh n đư c b i các đư ng th ng mà không c t đi m t đi m nguyên nào c a nó. Như minh h a Hình 1. Đ nh nghĩa 3.1. Gi s t p các đi m nguyên c a m t t p đa di n ký hi u là D = {x ∈ Zn : Ax ≤ b}. Khi đó ta g i ràng bu c αx ≤ β là lát c t đúng + c at pDn u αx ≤ b ∀x ∈ D, t c là lát c t đúng s không c t m t đi m t đi m nguyên nào c a t p đa di n D. 9
T i ưu t h p I Giáp Văn Hi p Hình 2: (a) T p ch p nh n đư c c a bài toán g c; (b) Sau khi s d ng Gomory M nh đ 3.1. Gi s αx ≤ β là m t lát c t đúng c a P = {x ∈ Zn : + Ax ≤ b}. Khi đó ta có n αi xi ≤ β i=1 cũng là m t lát c t đúng c a D. Ch ng minh. Vì xi ≤ xi và xi ≥ 0 v i m i i, nên v i m i x ∈ D ta có n n αi x i ≤ αi xi i=1 i=1 và n αi xi ≤ β i=1 n m t khác vì αi xi nguyên nên ta có i=1 n αi x i ≤ β ∀x ∈ D i=1 M nh đ ti p theo là trư ng h p t ng quát c a M nh đ 3.1. M nh đ 3.2. Gi s t p các đi m nguyên c a t p đa di n là t p D = {x ∈ Zn : Ax ≤ b}, v i A = (aij ) ∈ Rm×n và u ∈ Rm . Khi đó ta có ràng + + 10
T i ưu t h p I Giáp Văn Hi p bu c n n n ui aij xj ≤ ui bi j=1 i=1 i=1 là m t lát c t đúng c a D. Ch ng minh. T các ràng bu c n aij xj ≤ bi ∀i = 1, · · · , m, ∀x ∈ D j=1 Gi s là ui ≥ 0, khi đó n ui aij xj ≤ ui bi ∀i, ∀x ∈ P j=1 m n m ui ( aij xj ) ≤ ui bi ∀x ∈ D i=1 j=1 i=1 n m m ( ui aij )xj ≤ ui bi ∀x ∈ D j=1 i=1 i=1 n m m ( ui aij ) xj ≤ ui bi ∀x ∈ D j=1 i=1 i=1 (suy ra t M nh đ 3.1). Ví d 2. Cho t p ràng bu c D:   −x1 +3x2  ≤6 7x1 +x2 ≤ 35   −x1  ≤0 −x2 ≤0  7 1 N u t đi m u = ( 12 , 22 , 0, 0)T thì 7 1 7 1 7 1 (−1) + (7) x1 + (3) + (1) x2 ≤ (6) + (35) 22 22 22 22 22 22 ⇒ x2 ≤ 3.5 ⇒ x2 ≤ 3 là m t lát c t đúng c a D. N u t đi m u = ( 1 , 21 , 0, 0)T thì 3 4 1 4 1 4 1 4 (−1) + (7) x1 + (3) + (1) x2 ≤ (6) + (35) 3 21 3 21 3 21 11
T i ưu t h p I Giáp Văn Hi p ⇒ 1 x1 + 21 x2 ≤ 26 25 3 ⇒ x1 + x2 ≤ 8 là m t lát c t c a D. Minh h a hai lát căt trên Hình 2. Hình 3: Lát c t đúng theo Gomory Ví d 3. Cho mi n ràng bu c P như sau   10x1 +3x2 ≤ 45 4x1 +20x2 ≤ 65 x1 , x2 ∈ Zn  + Ta có ràng bu c 10x1 + 3x2 ≤ 45 là m t lát c t đúng. Khi đó ta có x1 + 10 x2 ≤ 45 cũng là lát c t đúng 3 10 ⇒ x1 + 10 x2 ≤ 45 cũng là lát c t đúng. 3 10 T đó ta tìm đư c m t lát c t đúng là x1 ≤ 4 Tương t ta xét ràng bu c th 2 4x1 + 20x2 ≤ 65 ⇒ x1 + 5x2 ≤ 65 4 ⇒ x1 + 5x2 ≤ 65 4 ⇒ x1 + 5x2 ≤ 16 là m t lát c t đúng. Minh h a như Hình 3. 12
T i ưu t h p I Giáp Văn Hi p Hình 4: Lát c t đúng theo Gomory M nh đ 3.3. Gi s r ng ràng bu c αx = β là m t lát c t đúng c a D, khi đó n (αi − αi )xi ≥ β − β i=1 t c là n {αi }xi ≥ {β} i=1 cũng là m t lát c t đúng c a D. Ch ng minh. D th y αx ≤ β là m t lát c t đúng c a D, theo M nh đ 3.1 n có ta αi xi ≤ βi , ∀x ∈ P i=1 n n ⇔ αi xi − αi xi ≥ β − βi , ∀x ∈ D i=1 i=1 n n αi xi − αi xi ≥ β − βi , ∀x ∈ D i=1 i=1 3.3 Áp d ng thu t toán Gomory đ gi i bài toán quy ho ch tuy n tính nguyên Ý tư ng: Đ u tiên ta đi gi i bài toán quy ho ch tuy n tính v i đi u ki n không nguyên ta đư c nghi m là x0 . Khi đó ta có th bi u di n các 13
T i ưu t h p I Giáp Văn Hi p bi n trong cơ s qua các bi n phi cơ s . x0 = x0 + i0 i zji xj i = 1, · · · , n (1) j ∈J(x0 ) / Gi s ak = ak + {ak }. Khi đó (1) đư c vi t l i dư i d ng x0 + {x0 } = xi 0 + i0 i0 ( zji + {zji })xj i = 1, · · · , n j ∈J(x0 ) / − x0 + xi 0 + i0 zji xj = {x0 } − i0 {zji }xj (2) j ∈J(x0 ) / j ∈J(x0 ) / Đ ý là VT c a (2) là b t bu c ph i nguyên VP c a (2) cũng ph i là s nguyên nh hơn 1 (vì {x0 } < 1 ) i0 ⇒ VP c a (2) luôn nh hơn ho c b ng 0. Đ t −xk b ng VP c a (2). {x0 } − i0 {zji }xj = −xk j ∈J(x0 ) / (v i đi u ki n xk nguyên và không âm.) ⇒− {zji }xj + xk = −{x0 } i0 (3) j ∈J(x0 ) / Theo M nh đ 3.3 thì (3) xác đ nh m t lát c t đúng. Nh n xét 3.1. Khi thêm vào các ràng bu c (3), mi n phương án c a bài toán quy ho ch tuy n tính nguyên (P 4) v n gi nguyên, vì (3) là h qu c a các đi u ki n ràng bu c c a bài toán (P 4). 3.3.1 Thu t toán Gomory Bư c kh i t o Gi i bài toán quy ho ch tuy n tính không nguyên min c, x v.đ.k. x ∈ D đư c nghi m t i ưu x1 . Đ t k := 1 và D1 = D. Bư c l p k Bư c 1: N u xk có các t a đ nguyên thì chuy n sang Bư c k t thúc. 14
T i ưu t h p I Giáp Văn Hi p Bư c 2: Ngư c l i xk có ít nh t m t t a đ không nguyên thì c n ch n ra m t bi n cơ s có giá tr không nguyên đ xây d ng ràng bu c b sung (lát c t th k) − {zji }xj + xk = −{x0 }. i0 j ∈J(x0 ) / Bư c 3: Gi i bài toán thu đư c b ng phương pháp đơn hình đ i ng u (hai pha) đ tìm phương án tôi ưu. Đ t k := k + 1 và chuyên v Bư c 1. Bư c k t thúc D ng và đưa ra k t qu . 3.3.2 Ví d Gi i bài toán quy ho ch tuy n tính nguyên sau: max x1 + 4x2 v.đ.k. 2x1 +4x2 +x3 =7 10x1 +3x2 +x4 = 15 x1 , x2 , x3 , x4 ≥= 0 xi nguyên i = 1, · · · , 5 15
T i ưu t h p I Giáp Văn Hi p Gi i bài toán chính t c trên b đi đi u ki n nguyên c a các bi n. Các bư c gi i trình bày b ng dư c đây. 1 4 0 0 H s Cơ s Phương án θ A1 A2 A3 A4 0 x3 7 2 [4] 1 0 [7/4] 0 x4 15 10 3 0 1 5 B ng 1 0 −1 [−4] 0 0 4 x2 7/4 1/2 1 1/4 0 0 x4 39/4 17/2 0 −3/4 1 B ng 2 7 1 0 1 0 Như v y phương án t i ưu c a B ng 2 có x2 = 7 không nguyên. Xét 4 phương trình 1 1 7 x2 + x1 + x3 = 2 4 4 Theo Gomory, ta s đưa thêm m t lát c t đúng vào t p ch p nh n đư c c a bài toán 1 1 3 − x1 − x2 + x5 = − 2 4 4 v i x5 ≥ 0 và nguyên. Ta l i ti p t c đi gi i bài toán khi thêm lát c t vào 1 4 0 0 0 H s Cơ s Phương án θ A1 A2 A3 A4 A5 4 x2 7/4 1/2 1 1/4 0 0 7/2 0 x4 39/4 17/2 0 −3/4 1 0 39/34 0 x5 −3/4 [−1/2] 0 −1/4 0 1 [3/2] B ng 3 7 [1] 0 1 0 0 4 x2 1 0 1 0 0 1 ∞ 0 x4 −3 0 0 [−5] 1 17 [3/5] 1 x1 3/2 1 0 1/2 0 −2 3 B ng 4 11/2 0 0 [1/2] 0 −2 16
T i ưu t h p I Giáp Văn Hi p 1 4 0 0 0 H s Cơ s Phương án θ A1 A2 A3 A4 A5 4 x2 1 0 1 0 0 1 0 x3 3/5 0 0 1 −1/5 −17/5 1 x1 6/5 1 0 0 1/10 −3/10 B ng 5 26/5 0 0 0 1/10 37/10 Ta th y B ng 5 cho ta nghi m nhưng v n chưa nguyên.Xét phương trình th 3 B ng 5 đ làm cơ s đưa thêm m t lát c t đúng n a vào. 1 7 1 − x4 − x5 + x6 = − 10 10 5 v i đi u ki n x6 ≥ 0 và x6 nguyên. Ta l i ti p t c gi i b ng thu t toán đơn hình. 1 4 0 0 0 0 H s Cơ s Phương án θ A1 A2 A3 A4 A5 A6 4 x2 1 0 1 0 0 1 0 ∞ 0 x3 3/5 0 0 1 −1/5 −17/5 0 ∞ 1 x1 6/5 1 0 0 1/10 −3/10 0 12 0 x6 −1/5 0 0 0 [−1/10] −7/10 1 [2] B ng 6 26/5 0 0 0 [1/10] 37/10 0 4 x2 1 0 1 0 0 1 0 0 x3 1 0 0 1 0 −2 −2 1 x1 1 1 0 0 0 −1 1 0 x4 2 0 0 0 1 7 −10 B ng 7 5 0 0 0 0 3 1 Phương án t i ưu B ng 7 nguyên, v y nghi m c a bài toán quy ho ch tuy n tính nguyên là (1, 1) và giá tr t i ưu là 5. 17
T i ưu t h p I Giáp Văn Hi p 3.4 Cài đ t using System ; using System . C o l l e c t i o n s . G e n e r i c ; using System . Linq ; using System . Text ; using System . IO ; namespace Gomory { c l a s s Program { s t a t i c f l o a t ABSA( f l o a t a ) { return ( a >0)? a : −a ; } s t a t i c void D i s p l a y M a t r i x ( f l o a t [ , ] A, i n t m, i n t n ) { C o n s o l e . WriteLine ( ) ; f o r ( i n t i = 0 ; i < m; i ++) { i f ( i == 1 | | i== m−1) C o n s o l e . WriteLine ( "−−−−−−−−−−−−−−− −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−" ) ; f o r ( i n t j = 0 ; j < n ; j ++) { C o n s o l e . Write ( S t r i n g . Format ( " { 0 , 5 } " , A[ i , j ] ) ) ; i f ( j == 2 ) C o n s o l e . Write ( " | " ) ; i f ( j == n − 2 ) C o n s o l e . Write ( " | " ) ; } C o n s o l e . WriteLine ( ) ; } } s t a t i c void D i s p l a y M a t r i x ( i n t [ , ] A, i n t m, i n t n ) { C o n s o l e . WriteLine ( ) ; f o r ( i n t i = 0 ; i < m; i ++) { f o r ( i n t j = 0 ; j < n ; j ++) { C o n s o l e . Write ( S t r i n g . Format ( " { 0 , 7 } " , A[ i , j ] ) ) ; } C o n s o l e . WriteLine ( ) ; } } s t a t i c void D i s p l a y M a t r i x ( f l o a t [ , ] A, i n t m, i n t n , s t r i n g path ) { return ; StreamWriter w r i t e r = new StreamWriter ( path , true ) ; s t r i n g strW ; f o r ( i n t i = 0 ; i < 5 ; i ++) { f o r ( i n t j = 0 ; j < 1 0 ; j ++) { strW = " " + A[ i , j ] . T o S t r i n g ( " 0 0 0 . 0 " ) ; w r i t e r . Write ( strW ) ; } w r i t e r . WriteLine ( ) ; } w r i t e r . WriteLine ( ) ; writer . Close ( ) ; } s t a t i c f l o a t BienDoiMaTran ( f l o a t [ , ] A, i n t m, i n t n ) { while ( true ) 18
T i ưu t h p I Giáp Văn Hi p { int i , j ; // Buoc1 f o r ( i = 3 ; i < n − 1 ; i ++) // t i n h d e l t a cho t u n g c o t { f l o a t tong = 0 ; f o r ( j = 1 ; j < m − 1 ; j ++) tong = tong + A[ j , 0 ] ∗ A[ j , i ] ; A[m − 1 , i ] = tong − A[ 0 , i ] ; } D i s p l a y M a t r i x (A, m, n , "C: \ \ Output . t x t " ) ; // kiem t r a dong c u o i cung cua bang ( Dong d e l t a ) f o r ( i = 3 ; i < n − 1 ; i ++) { i f (A[m − 1 , i ] > 0 ) break ; } i f ( i == n − 1 ) { float f = 0; f o r ( j = 1 ; j < m − 1 ; j ++) f += A[ j , 0 ] ∗ A[ j , 2 ] ; A[m − 1 , 2 ] = f ; return f ; //Dung bang don h i n h v i da t i n h ra nghiem } // Buoc 2 f o r ( i = 3 ; i < n − 1 ; i ++) // kiem t r a b a i toan khong l o i g i a i // x e t moi d e l t a >0 neu co c o t t h u i ma moi z 0 ) { f o r ( j = 1 ; j < m − 1 ; j ++) i f (A[ j , i ] > 0 ) break ; //Dung bang don h i n h v i vo nghiem i f ( j == m − 1 ) throw new E x c e p t i o n ( "Vo nghiem " ) ; } // Buoc 3 tim c o t quay dong quay i n t indexMax = 3 ; // c h i so c o t max cua d e l t a f l o a t maxTemplate = A[m − 1 , indexMax ] ; f o r ( i = 3 ; i < n − 1 ; i ++) i f (A[m − 1 , i ] > maxTemplate ) { maxTemplate = A[m − 1 , i ] ; indexMax = i ; } i n t columnRound = indexMax ; // t h o n g so ve phan t u quay f o r ( j = 1 ; j < m − 1 ; j ++) // t i n h cac t h e t a A[ j , n − 1]=(A[ j , indexMax ]
T i ưu t h p I Giáp Văn Hi p } f o r ( j = 1 ; j < m − 1 ; j ++) // t i n h cac dong con l a i { i f ( j == rowRound ) continue ; f l o a t templeItem1 = A[ j , columnRound ] ; f o r ( i = 2 ; i < n − 1 ; i ++) A[ j , i ] = A[ j , i ] − templeItem1 ∗ A[ rowRound , i ] ; } D i s p l a y M a t r i x (A, m, n , "C: \ \ Output . t x t " ) ; } } //ham dung b i e n d o i 1 bang don h i n h chua A // de t i n h g i a cuc b i e n x u a t p h a t va v e c t o xua p h a t s t a t i c f l o a t DonHinh2Pha ( f l o a t [ , ] SimpleTableTemplete , i n t mA, i n t nA) { int i , j ; f l o a t [ , ] SimplexTable = new f l o a t [ 1 0 0 0 , 1 0 0 0 ] ; f o r ( i = 0 ; i < mA; i ++) f o r ( j = 0 ; j < nA ; j ++) SimplexTable [ i , j ] = SimpleTableTemplete [ i , j ] ; i n t numberRow = mA; // hang dau t i e n chua cac he so c // them mA b i e n g i a va 4 c o t l a n l u o t l a c , A, x , t h e t h a i n t numberColum = nA + mA − 2 ; // t i n h hang dau t i e n f o r ( j = 0 ; j < 3 ; j ++) SimplexTable [ 0 , j ] = 1 0 0 ; f o r ( j = 3 ; j < 3 + nA ; j ++) SimplexTable [ 0 , j ] = 0 ; f o r ( j = 3 + nA ; j < numberColum − 1 ; j ++) SimplexTable [ 0 , j ] = 1 ; f o r ( i = 0 ; i < numberRow ; i ++) // hang c u o i cung cho bang 100 SimplexTable [ i , numberColum − 1 ] = 1 0 0 ; f o r ( i = 0 ; i < numberRow − 1 ; i ++) SimplexTable [ i , 0 ] = 1 ; // Cot dau t i e n gan = 1 f o r ( i = 0 ; i < numberRow ; i ++) // Cot t i e p t h e o cho toan bo = 100 SimplexTable [ i , 1 ] = 1 0 0 ; f o r ( j = 0 ; j < numberColum − 1 ; j ++) // hang c u o i cung =100 SimplexTable [ numberRow − 1 , j ] = 1 0 0 ; f o r ( i = 1 ; i < numberRow − 1 ; i ++) f o r ( j = nA−1; j < numberColum − 1 ; j ++) SimplexTable [ i , j ] = ( i − 1 == j − nA+1) ? 1 : 0 ; f o r ( i = 1 ; i < numberRow − 1 ; i ++) SimplexTable [ i , 1 ] = nA + i − 1 ; C o n s o l e . WriteLine ( " \nBang don hinh pha 1 : " ) ; D i s p l a y M a t r i x ( SimplexTable , numberRow , numberColum ) ; C o n s o l e . WriteLine ( ) ; //Dua vao don h i n h de t i n h BienDoiMaTran ( SimplexTable , numberRow , numberColum ) ; C o n s o l e . WriteLine ( " \nKet qua pha 1 : " ) ; D i s p l a y M a t r i x ( SimplexTable , numberRow , numberColum ) ; C o n s o l e . WriteLine ( ) ; f o r ( i = 1 ; i < numberRow − 1 ; i ++) f o r ( j = 2 ; j < numberColum − 1 ; j ++) SimpleTableTemplete [ i , j ] = SimplexTable [ i , j ] ; return 0 ; } s t a t i c i n t GiaiBT ( i n t [ ] c , i n t [ , ] matrixA , i n t mA, i n t nA , i n t [ ] b ) { C o n s o l e . WriteLine ( " Matrix A: " ) ; D i s p l a y M a t r i x ( matrixA , mA, nA ) ; 20