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

Tiểu luận Cơ sở khoa học của việc cấp GCNQSDĐ ở cho hộ gia đình cá nhân đang sử dụng đất

Tham khảo luận văn - đề án 'tiểu luận cơ sở khoa học của việc cấp gcnqsdđ ở cho hộ gia đình cá nhân đang sử dụng đất', luận văn - báo cáo phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả


Bài thuyết trình Phát triển, duy trì và sản xuất hạt của các giống ngô thụ phấn tự do

Bài thuyết trình Phát triển, duy trì và sản xuất hạt của các giống ngô thụ phấn tự do tập trung tìm hiểu về phát triển giống, đánh giá và đặc điểm, duy trì và sản xuất hạt giống, những vấn đề khác trong kế hoạch sản xuất hạt giống ngô thụ phấn tự do.


Đề tài: Điều tra khảo sát di sản kiến trúc Văn Miếu - Quốc Tử Giám để phục vụ du lịch

Đề tài: Điều tra khảo sát di sản kiến trúc Văn Miếu - Quốc Tử Giám để phục vụ du lịch nghiên cứu với mục đích tìm hiểu một cách rõ nét nhất lối kiến trúc, cách xây dựng để từ đó biết được bố cục, hình, màu sắc của điêu khắc, kiến trúc, trang trí,… trong nghệ thuật truyền thống của mỹ thuật cổ truyền Việt Nam nhằm: Tôn vinh nét đẹp tinh hoa kiến trúc của dân tộc, bảo tồn và phát triển di sản Văn Miếu - Quốc Tử Giám quảng bá hình ảnh, phát triển du lịch cho khu di tích.


Tiểu luận: Vẽ kỹ thuật - 2

Tham khảo tài liệu 'tiểu luận: vẽ kỹ thuật - 2', luận văn - báo cáo phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả


Bài thuyết trình Bộ khuếch đại Raman

Bộ khuếch đại Raman là bộ khuếch đại sử dụng những tính chất bên trong sợi quang để khuyếch đại tín hiệu. Để hiểu rõ hơn về điều này mời các bạn tham khảo bài thuyết trình Bộ khuếch đại Raman sau đây. Với các bạn chuyên ngành Vật lý thì đây là tài liệu hữu ích.


Luận văn Thạc sỹ Toán học: Phương pháp tọa độ trong hình học tổ hợp và số học

Mục đích nghiên cứu: Hệ thống hóa lý thuyết và cách giải các dạng bài tập Hình học tổ hợp và Số học bằng phương pháp tọa độ đồng thời nắm được một số kỹ thuật tính toán liên quan. Mời các bạn tham khảo!


Đề tài: Nghiên cứu bào chế màng mỏng chứa acyclovir và clorhexidin kết dính niêm mạc miệng”

Mục tiêu chính của đề tài là xây dựng được phương pháp định lượng đồng thời acyclovir và clorhexidin trong màng mỏng, bào chế được màng mỏng chứa acyclovir và clorhexidin kết dính niêm mạc miệng bằng phương pháp bốc hơi dung môi, khảo sát ảnh hưởng của tá dược và tỷ lệ dược chất đến khả năng giải phóng dược chất và khả năng kết dính của màng mỏng.


Đề tài: Quy trình công nghệ sản xuất bia tại Công ty TNHH Bia Việt Nam

Tổ chức quản lý của Công ty TNHH Bia Việt Nam, quy trình công nghệ, công nghệ sản xuất là những nội dung chính trong 4 phần của đề tài "Quy trình công nghệ sản xuất bia tại Công ty TNHH Bia Việt Nam". Mời các bạn cùng tham khảo.


PHỤ GIA CÁC SẢN PHẨM DẦU KHÍ

Petroleum Gas là khí thu được từ quá trình chế biến dầu được hóa lỏng. Thành phần hóa học chủ yếu của khí hóa lỏng LPG hỗn hợp gồm Propane C3H8 và Butane C4H10 được nén theo tỷ lệ % Propane / %Butane. Trong thực tế, thành phần hỗn hợp các chất có trong khí hóa lỏng LPG không thống nhất. Tùy theo tiêu chuẩn của các nước, của các khu vực mà tỉ lệ thành phần trong LPG khác nhau, có khi tỉ lệ giữa Propane và Butane là 50/50 hay 30/70 hoặc có thể lên đến 95/5 như tiêu chuẩn của HD-5 của Mỹ.


Luận văn:Nghiên cứu phương pháp ăn mòn laser để chế tạo các hạt nano kim loại

Công nghê vật liệu nano ngày nay đã khẳng định những ứng dụng rộng lớn của nó trong rất nhiều lĩnh vực. Trong các cấu trúc nano, cấu trúc hạt nano kim loại thu hút rất nhiều sự quan tâm của các nhà khoa học trên thế giới do tính chất ưu việt của nó mà khi ở dạng khối kim loại không thể có. Các đặc tính của hạt nano kim loại có thể cho ra những sản phẩm đa năng hoàn toàn mới lạ ứng dụng trong y, dược, bảo vệ môi trường, công nghệ điện tử... [1]....


Tài liệu mới download

tài liệu về diode
  • 05/01/2011
  • 81.055
  • 997
Mẫu Quản lí nghỉ phép năm
  • 02/04/2019
  • 88.493
  • 514

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

CTV FACE

Có thể bạn quan tâm

Bộ sưu tập

Danh mục tài liệu