Tìm kiếm tài liệu miễn phí

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

Ả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



Đánh giá tài liệu

4.7 Bạn chưa đánh giá, hãy đánh giá cho tài liệu này


Tiểu luận: Thuật toán Gomory Tiểu luận: Thuật toán Gomory Thuật toán Gomory, Tiểu luận toán học, Toán tổ hợp, Toán cao cấp, Toán tin ứng dụng, Toán tối ưu tổ hợp, Quy hoạch tuyến tính
4.7 5 1468
  • 5 - Rất hữu ích 1.090

  • 4 - Tốt 378

  • 3 - Trung bình 0

  • 2 - Tạm chấp nhận 0

  • 1 - Không hữu ích 0

Mô tả

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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
  19. 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 ]
  20. 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

Tài liệu cùng danh mục Khoa học tự nhiên

Phương trình nghiệm nguyên

Phương trình và bài toán với nghiệm nguyên là một đề tài lý thú của Số học và Đại số, từ những bài toán về tính mỗi loại trâu Trăm trâu trăm cỏ đến các chuyên gia toán học lớn với các bài toán như định lý lớn Fecma. Được nghiên cứu từ thời Điôphăng thế kỉ thứ III, phương trình nghiệm nguyên vẫn còn là đối tượng nghiên cứu của toán học. Phương trình nghiệm nguyên vô cùng đa dạng, vì thế nó thường không có quy tắc giải tổng quát. Mỗi bài toán, với số liệu riêng của nó, đòi hỏi một cách giải...


Quá trình hình thành giáo trình nuôi cấy vi khuẩn trong phòng thí nghiệm chế tạo giống p7

Khối so sánh: có nhiệm vụ so sánh tín hiệu đo đ−ợc với tín hiệu chuẩn rồi đ−a ra tín hiệu điền khiển. • Khối tín hiệu chuẩn: nhằm tạo ra tín hiệu chuẩn để so sánh với tín hiệu đo. • Mạch điều khiển: tạo ra tín hiệu điều khiển t−ơng ứng để đ−a ra điều khiển kháng đốt.


Bài tiểu luận: Bao bì kim loại

Sự ra đời và phát triển của bao bì kim loại, đặc tính chung bao bì kim loại, phân loại bao bì kim loại, bao bì sắt tây,... là những nội dung chính trong bài tiểu luận "Bao bì kim loại". Mời các bạn cùng tham khảo.


BÁO CÁO CHUYÊN ĐỀ " TẢO LỤC "

Theo Prescott(1969) có khoảng 20.000 loài phân biệt so với các tảo khác nhờ màu lục của dịp lục tố. Đa dạng về cấu trúc và hình dạng. Phần lớn là những cơ thể quang tự dưỡng. Có màu xanh lục,xanh lá cây. Hình thể:đơn bào,cộng đơn bào,đa bào,1 số ít dạng tập đoàn. Kích thước:rất nhỏ(µm),nhưng cũng có loài đạt đến vài met.


Tiểu luận:Ứng dụng lý thuyết galois trong phép dựng hình

Tham khảo luận văn - đề án 'tiểu luận:ứng dụng lý thuyết galois trong phép dựng hình', luận văn - báo cáo, khoa học tự nhiên phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả


Báo cáo thực hành: Hóa kỹ thuật môi trường

Báo cáo thực hành "Hóa kỹ thuật môi trường" trình bày về một số quy tắc an toàn và kỹ thuật trong phòng thí nghiệm, đo độ đục, hàm lượng photphat, đo nồng độ oxi hòa tan, chất rắn lơ lửng,... Mời các bạn cùng tham khảo nội dung bài báo cáo để nắm bắt nội dung chi tiết.


Đề tài: Quản lý rủi ro các sinh vật biến đổi gen

Trong những năm gần đây, công nghệ sinh học (CNSH) đã phát triển một cách mạnh mẽ và mức độ sử dụng ngành khoa học tiên tiến này cũng đã tăng nhanh chóng. CNSH đã và đang được ứng dụng rộng rãi vào thực tế đời sống và tạo ra những ảnh hưởng sâu sắc ở quy mô toàn cầu.


LUẬN VĂN TÓM TẮT: Một số vấn đề về modun extending và modun lifting trong phạm trù M

Tham khảo luận văn - đề án 'luận văn tóm tắt: một số vấn đề về modun extending và modun lifting trong phạm trù m', luận văn - báo cáo, khoa học tự nhiên phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả


Luận văn tốt nghiệp: Ảnh hưởng của gia vị, chế độ sấy và hóa chất bảo quản đến chất lượng sản phẩm khô cá tra tẩm gia vị chế biến từ vụn cá

Luận văn tốt nghiệp: Ảnh hưởng của gia vị, chế độ sấy và hóa chất bảo quản đến chất lượng sản phẩm khô cá tra tẩm gia vị chế biến từ vụn cá trình bày khảo sát công thức phối trộn gia vị để tìm ra hàm lượng đường và bột ngọt phù họp giúp cho sản phẩm đạt được mùi vị tốt nhất, khảo sát chế độ sấy đế tìm ra nhiệt độ và thòi gian sấy phù hợp nhất đối vói khô cá tra tẩm gia vị dạng miếng, khảo sát ảnh hưởng của hóa chất đến thòi gian bảo quản và chất lượng sản phẩm.


Đề tài: Khảo sát một số đặc điểm của loài Cordyceps sp. được tìm thấy tại Đà Lạt

Đề tài: Khảo sát một số đặc điểm của loài Cordyceps sp. được tìm thấy tại Đà Lạt nhằm mục đích nghiên cứu một số đặc điểm sinh học của loài Cordyceps sp. từ đó tìm hiểu tiềm năng ứng dụng của loài nấm này trong y dược và trong đối kháng sinh học, đồng thời tạo nguồn nguyên liệu ban đầu phục vụ cho các nghiên cứu ứng dụng sau này.


Tài liệu mới download

Đề thi casio môn hóa học
  • 04/10/2011
  • 17.773
  • 156
Luận văn Thiết kế web
  • 07/12/2012
  • 95.266
  • 930
ĐỘT QUỴ (STROKE)
  • 08/07/2011
  • 76.209
  • 901

Từ khóa được quan tâm

CTV FACE

Có thể bạn quan tâm

Vật lý: Tia X
  • 12/05/2013
  • 65.507
  • 404

Bộ sưu tập

Danh mục tài liệu