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

QUY HOẠCH RỜI RẠC - CHƯƠNG 5

THUẬT TOÁN GOMORY THỨ BA Chương này trình bày thuật toán Gomory thứ ba nhằm xây dựng các lát cắt đảm bảo tất cả các Bảng đơn hình ở mỗi bước đều có tất cả các phần tử là nguyên 1. ẢNH HƯỞNG CỦA SAI SỐ LÀM TRÒN VÀ TƯ TƯỞNG CỦA THUẬT TOÁN GOMORY THỨ BA 1.1. Ả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...



Đánh giá tài liệu

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


QUY HOẠCH RỜI RẠC - CHƯƠNG 5 QUY HOẠCH RỜI RẠC - CHƯƠNG 5 chứng minh tính hữu hạn, thuật toán Gomory, lập trình bằng ngôn ngữ C, quy hoạch tuyến tính, phương pháp đơn hình
4.8 5 2324
  • 5 - Rất hữu ích 1.927

  • 4 - Tốt 397

  • 3 - Trung bình 0

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

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

Mô tả

  1. V.1 Bùi Thế Tâm Quy hoạch rời rạc Chương 5 THUẬT TOÁN GOMORY THỨ BA Chương này trình bày thuật toán Gomory thứ ba nhằm xây dựng các lát cắt đảm bảo tất cả các Bảng đơn hình ở mỗi bước đều có tất cả các phần tử là nguyên 1. ẢNH HƯỞNG CỦA SAI SỐ LÀM TRÒN VÀ TƯ TƯỞNG CỦA THUẬT TOÁN GOMORY THỨ BA 1.1. Ả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 do các nguyên nhân sau : - Tăng khối lượng tính toán vì dùng nhiều lần l - phương pháp. - Khả năng mắc sai khi xử lý các số kiểu phần thập phân 0,999999 ≈ 1,000000 - Khả năng nhận lời giải không đúng vì số nguyên có thể nhận là không nguyên. Để tránh sai số làm tròn, Gomory đưa ra thuật toán thứ ba để giải bài toán quy hoạch tuyến tính nguyên toàn phần : n max x0 ≡ ∑ c j x j (1) j =1 n ∑a x j = bi , i = 1, 2,..., m (2) ij j=1 xj ≥ 0 , j = 1, 2,..., n (3) x j − nguyên , j = 1, 2,..., n (4) 1.2. Tư tưởng của thuật toán Gomory thứ ba Giả sử bài toán (L,C) ≡ (L0,C) viết ở dạng bảng T0 , l - chuẩn (phần tử khác không đầu tiên ở mỗi cột là số dương). Dùng l - phương pháp, ta nhận được dãy hữu hạn các bảng l - chuẩn T0 , T1 , ... , Ts mà cái cuối cùng là chấp nhận được. Giả sử bảng xuất phát T0 là nguyên hoàn toàn (tất cả các phần tử là số nguyên). Các bảng tiếp theo có thể không nguyên là do: ngoài các phép toán + , - , * khi chuyển từ Tν sang Tν+1 , ta còn dùng phép tính chia trên phần tử quay. Nếu phần tử quay trên tất cả các bước là (-1) thì các bảng T1 , T2 , ... vẫn là nguyên khi T0 - nguyên, cuối cùng phương án tối ưu Xs của bài toán (Ls,C) ứng với Ts cũng là nguyên. Vậy Xs là phương án tối ưu của bài toán quy hoạch tuyến tính nguyên gốc (LN,C). Vì vậy, ta sẽ cải tiến định nghĩa lát cắt đúng sao cho nếu dòng tương ứng với nó chọn làm dòng quay thì phần tử quay bằng (-1). Chính xác hơn, bài toán tìm lát cắt đúng nguyên được phát biểu như sau: có bài toán (L,C), các điều kiện của nó viết dưới dạng bảng nguyên, không chấp nhận được, l - chuẩn T ' = xij 0 , vì vậy l - giả phương án mở rộng : n i∈Q , j∈N X ' = ( x0 , x1' ,..., xn ) = ( x00 , x10 ,..., xn 0 ) ' ' http://www.ebook.edu.vn
  2. V.2 Bùi Thế Tâm Quy hoạch rời rạc ứng với T' không là phương án mở rộng. Cần xây dựng một hàm tuyến tính : Z ( X ) = r0 + ∑ rj (− x j ) (5) j∈N thỏa mãn các điều kiện sau : I. Điều kiện nguyên : rj - nguyên , ∀j ∈ N 0 (6) II. Điều kiện cắt : ( ) Z(X') = r0 < 0 , X ' = x1 ,..., x n ' ' (7) III. Điều kiện đúng: với mọi phương án X của bài toán ( LN , C ) thì Z(X) ≥ 0. (8) ( j∈N) IV. Điều kiện giữ gìn tính nguyên. Nếu trong các số rj có số âm ,  x0 j   x1 j R j =   với j ∈ N là cột của ma trận T' và   x   nj  R Rl = lex min j (9) rl j∈N,rj < 0 rj thì rl = −1 (10) Điều kiện (9) - (10) có nghĩa là nếu dòng Z(X) chọn làm dòng quay thì phần tử quay là (-1). 1.3. Lược đồ logic của thuật toán Gomory thứ ba Nếu thành công xây dựng lát cắt đúng nguyên thỏa mãn (5) - (10) thì lược đồ logic của thuật toán như sau. Bắt đầu từ bảng không chấp nhận được xuất phát T0 , xây dựng dãy các bảng T0 , T1 , ... , Tr , Tr+1 , ... mà mỗi bảng đều là nguyên và l - chuẩn. Nếu Tr là chấp nhận được thì l - giả phương án ứng với nó Xr đồng thời là phương án tối ưu của bài toán (LN,C). Nếu Tr là không chấp nhận được thì xây dựng lát cắt đúng nguyên thỏa mãn (5) - (10). Viết dòng tương ứng ngay dưới bảng Tr và lấy nó làm dòng quay. Sau đó, thực hiện một bước lặp của l - phương pháp để nhận được bảng mới Tr+1 nguyên và l - chuẩn. http://www.ebook.edu.vn
  3. V.3 Bùi Thế Tâm Quy hoạch rời rạc 2. XÂY DỰNG LÁT CẮT ĐÚNG NGUYÊN, THUẬT TOÁN GOMORY THỨ BA 2.1. Cơ sở xây dựng lát cắt đúng nguyên : Định lý 1. Giả sử λ > 0 y0 = d 0 + ∑ d j (− y j ) , trong đó T là tập hữu hạn; j∈T dj  d  z =  0  + ∑   ( − y j ) , trong đó [x] - phần nguyên của x;  λ  j∈T  λ  j ∈ {0} ∪ T , yj ≥ 0 , yj - nguyên , j ∈ T . Khi đó : z ≥ 0 z - nguyên. Chứng minh. Tính nguyên của z trực tiếp suy ra từ định nghĩa phần nguyên và tính nguyên của yj ( j ∈ T ). Để chứng minh z ≥ 0 ta dùng phản chứng, giả sử z < 0. Từ tính nguyên của z suy ra z ≤ -1. (11) dj y0 d0 +∑ = (− y j ) , như vậy Mặt khác: λ λ λ j∈T d  d  d  d  y0 =  0  + ∑  j (− y j ) +  0  + ∑  j  (− y j ) λ  λ  j∈T  λ   λ  j∈T  λ  d  d  z =  0  + ∑  j  (− y j ) Theo giả thiết  λ  j∈T  λ  d j  d  y0 =  0  + ∑   (− y j ) + z , hay suy ra λ  λ  j∈T  λ  d  d  y0 + ∑ j  yj =  0  + z (12) λ j∈T  λ  λ  d  ≤  0  − 1 < 0. (do (11)) λ  j ∈ {0} ∪ T (theo giả thiết), λ > 0 yj ≥ 0 , Điều này không thể sảy ra vì d  và định nghĩa phần lẻ  j  , j ∈ T . Do vậy , z ≥ 0 . Định lý được chứng minh. λ  http://www.ebook.edu.vn
  4. V.4 Bùi Thế Tâm Quy hoạch rời rạc 2.2. Từ định lý trên ta xây dựng lát cắt đúng nguyên thỏa mãn (5) - (10). Giả sử cho bảng T = xij nguyên, không chấp nhận được, l - chuẩn và giả sử đối với k i∈Q n , j∈N 0 (1 ≤ k ≤ n): xk 0 < 0, xk = xk 0 + ∑ xkj (− x j ) j∈N Đặt: T=N d j = xkj ( j ∈ N0) y0 = xk yj = xj ( j ∈ N) λ = max d j = max xkj j∈N 0 j∈N 0  d j  0 , d j ≥ 0    =  −1 , d < 0 , Như vậy: λ   j và ta nhận được lát cắt đúng nguyên :  z = zk (λ ; X ) = −1 + ∑ (−1)(− x j )  j∈N  xkj < 0  z ≥ 0  z − nguyên    2.3. Trong phần này ta sẽ chỉ ra trong một số trường hợp cụ thể nhận được bảng T0 nguyên, l - chuẩn : Xét bài toán : n x0 ≡ ∑ c j x j max (13) j =1 n ∑a x j ≤ bi , i = 1, 2,..., m (14) ij j=1 xj ≥ 0 , j = 1, 2,..., n (15) x j − nguyên , j = 1, 2,..., n (16) trong đó cj , aij , bi nguyên ( i = 1,..., m ; j = 1,..., n ) . Đưa vào các biến mới, bài toán trên được viết lại như sau : http://www.ebook.edu.vn
  5. V.5 Bùi Thế Tâm Quy hoạch rời rạc n max x0 ≡ ∑ (−c j )(− x j ) j =1 n xn +i = bi + ∑ a ij (− x j ), i = 1, 2,...., m j=1 x j ≥ 0, j = 1, 2,..., n, n + 1,..., n + m x j − nguyên , j = 1, 2,..., n, n + 1,..., n + m Ta có các biến x1 , ... , xn là biến phi cơ sở , viết bảng T0' (chưa l - chuẩn). 1 -x 1 -x2 ... -xj ... -xn x0 0 -c1 -c2 ... -cj ... -cn x1 0 -1 0 ... 0 ... 0 x2 0 0 -1 ... 0 ... 0 ... ... xn 0 0 0 ... 0 ... -1 xn+1 b1 a11 a12 ... a1j ... a1n xn+2 b2 a21 a22 ... a2j ... a2n ... ... xn+i bi ai1 ai2 ... aij ... ain ... ... xn+m bm an1 am2 ... amj ... amn (Bảng T0' ) a) Nếu bảng T0' là l - chuẩn (ví dụ khi cj < 0 , j = 1,..., n ) thì xem nó là bảng xuất phát T0 (lấy T0' làm T0 xuất phát). b) Nếu T0' không là l - chuẩn, nhưng tập các phương án của bài toán (13)-(15) là n ∑x bị chặn thì ta giải bài toán quy hoạch tuyến tính với hàm mục tiêu với ràng buộc j j=1 (14)-(15) và tìm được: n max ∑ x j = M ' j=1 Rõ ràng, với mọi phương án của bài toán (13) - (16) ta đều có : n ∑ x ≤ [ M '] ≡ M j j=1 Vì vậy, từ bài toán này ta có thể đưa vào biến mới : http://www.ebook.edu.vn
  6. V.6 Bùi Thế Tâm Quy hoạch rời rạc n xn + m +1 = M + ∑1.(-x j ) (17) j=1 xn + m +1 ≥ 0 (18) xn + m +1 − nguyên (19) Viết dòng (17) xuống dưới bảng T0' và chọn nó làm dòng quay. Cột quay chọn theo tiêu chuẩn: Rl' = lex min R 'j j∈{1,..., n} ( R 'j - là cột của T0' ứng với biến phi cơ sở x j ( j = 1,..., n) ). Thực hiện một bước lặp của l - phương pháp, xóa dòng xn+m+1 (dòng cuối của bảng T0' ) và nhận được bảng T0 nguyên, l - chuẩn. Nếu sau này biến xn+m+1 đưa vào cơ sở thì dòng tương ứng không được phục hồi. 2.4. Thuật toán Gomory thứ ba Bước lặp 0.: Xây dựng bảng xuất phát T0 = xij 0 - nguyên , l - chuẩn. Nếu i∈Q n , j∈N 0 T0 là chấp nhận được thì l - giả phương án mở rộng : X 0 = ( x0 , x10 ,..., xn ) = ( x00 , x10 ,..., xn 0 ) 0 0 0 0 0 là phương án tối ưu mở rộng của bài toán (LN,C) và thuật toán dừng. Nếu T0 không chấp nhận được thì chuyển tới bước lặp đầu tiên. Bước lặp p (p ≥ 1). Cho bảng TP −1 = xij P-1 - nguyên , l - chuẩn nhưng i∈Q n , j∈N P−1 0 không chấp nhận được. Chọn k là chỉ số đầu tiên vi phạm tính chấp nhận được k = min {i | i ∈ {1, 2,..., n} , xiP −1 < 0} 0 Nếu xkj −1 ≥ 0 , ∀j ∈ N P −1 thì bài toán (LN,C) không giải được. P Nếu ∃xkj −1 < 0 thì ta chọn cột cột quay l theo công thức : P RlP −1 = lex min R P −1 (20) j j∈N P −1 , xkj < 0 và xây dựng lát cắt đúng nguyên (dòng quay) :  xkj −1  P  x P −1  ∑ xn + P =  k 0  +  (− x j ) (21)  λ j∈N P−1  λ    xn + P ≥ 0 (22) xn + P − nguyên (23) Quy tắc chọn λ như thế nào ta sẽ trình bày trong Mục 2.5. Viết dòng (21) vào cuối bảng TP-1 và lấy làm dòng quay. Thực hiện một bước lặp của l - phương pháp (loại xn+P khỏi cơ sở, đưa xl vào cơ sở), xóa dòng xn+P. Nếu l ≥ n+1 thì dòng xl không khôi phục nữa, ta sẽ nhận được bảng http://www.ebook.edu.vn
  7. V.7 Bùi Thế Tâm Quy hoạch rời rạc TP = xij P i∈Q n , j∈N P 0 là nguyên và l - chuẩn, trong đó : N P = ( N P −1 \ {l} ) ∪ {n + p} Nếu TP là chấp nhận được thì X P = ( x0 , x1P ,..., xn ) = ( x00 , x10 ,..., xn 0 ) là phương án P P P P P tối ưu mở rộng của bài toán (LN,C) . Nếu TP không châp nhận được thì chuyển tới bước (p+1). 2.5. Quy tắc chọn số λ . Số λ được chọn theo ba điều kiện sau I. Phần tử quay bằng (-1) :  xkl −1  P  = −1 (24)  λ II. Bảng TP phải là l - chuẩn :  x P −1  R P = R P −1 +  kj  RlP −1 > 0 , (25) λ j j   ( ∀j ∈ N P \ {n + p} = N P−1 \{l}) III. Cột R0P phải là lexmin :  x P −1  R0P = R0P −1 +  k 0  RlP −1 → lex min (26) λ Chú ý : − RlP −1 = RlP −1 > 0 suy ra bất đẳng thức (25) đúng với j = n + p rồi. 1) RnP+ P = −1 2) Từ (24) và xkl −1 < 0 (do(20)) suy ra λ > 0 P 2.6. Xác định λ thỏa mãn (24) - (26) a) Điều kiện (24) có thể viết thành : xkl −1 P −1 ≤ 0 nên ta có : λ ≥ − xkl −1 P (24') b) Điều kiện (25) có thể đơn giản hóa bằng cách sau.  x P −1  Nếu xkj −1 ≥ 0 thì  kj  RlP −1 ≥ 0 và điều kiện (25) đúng với bất kỳ λ > 0 . Do P λ   vậy, chỉ cần xét điều kiện (25) với : j ∈ N P −1 \{l} mà xkj −1 < 0 . P http://www.ebook.edu.vn
  8. V.8 Bùi Thế Tâm Quy hoạch rời rạc Với mỗi j ∈ N P −1 , ta đặt : { } h( j ) = min i | xij > 0 . p-1 h(l ) = max{h(j)|j ∈ N P-1 , x kj-1 0 λ j j   Do đó, trường hợp này (25) cũng đúng. Như vậy, chỉ cần xét (25) với : j ∈ N P −1 \{l} mà xkj −1 < 0 và h(j) = h(l). P Khi đó, điều kiện (25) được viết lại là :  x P −1  R P = R P −1 +  kj  RlP −1 > 0 , ∀j ∈ N P −1 ' (25') λ j j   N P −1 = { j | j ∈ N P −1 \{l} , x P-1 < 0 , h( j ) = h(l )} ' kj Nếu N P −1 = ∅ thì (25') không cần thêm bất cứ điều kiện nào trên số λ > 0 . Bây ' giờ giả sử N P −1 ≠ ∅ . Khi đó đối với mỗi j ∈ N P −1 ta có thể tìm được số tự nhiên zj sao ' ' cho : R P −1 − ( z j + 1) RlP −1 < 0 < R P −1 − z j RlP −1 (27) j j Chú ý rằng R P −1 ≠ zRlP −1 với z bất kỳ, vì nếu R P −1 = zRlP −1 thì j j R P −1 và RlP −1 là không tỉ lệ với = 0 , điều này là không thể. Do đó P-1 det xij j i∈N 0 , j∈N P−1 nhau. Có 4 khả năng : 1) xh (−1 j = xh (−1l . Khi đó nếu chọn zj = 1 thì (27) thỏa mãn. P P l) l) 2) xh (−1 j = qxh (−1l + r trong đó q, r là các số tự nhiên, r < xh (−1l . Khi đó nếu chọn P P P l) l) l) chọn zj = q thì (27) được thỏa mãn. 3) xij −1 = qxil −1 , i = h(l) , h(l) + 1 , ... , h(l) + t ≡ s - 1, và P P xsPj −1 > qxsl −1 trong đó q là số tự nhiên ≥2. P Khi đó, nếu ta chọn zj = q thì (27) đúng. 4) xij −1 = qxil −1 , i = h(l) , h(l) + 1 , ... , h(l) + t ≡ s - 1, và P P xsPj −1 < qxsl −1 , trong đó q là số tự nhiên ≥ 2. P Khi đó, ta chọn zj = q - 1 thì (27) đúng. http://www.ebook.edu.vn
  9. V.9 Bùi Thế Tâm Quy hoạch rời rạc  xkj −1  P Từ (27) và (25') suy ra cần chọn số λ thỏa mãn: −   ≤ zj , ∀j ∈ N P −1 , hay ' λ   xkj −1 xkj −1 P P ≥ − z j , suy ra λ ≥ − . Vậy điều kiện (25') chuyển thành điều kiện sau: λ zj  x P-1   kj  λ ≥ θ ≡ max - j ∈ N P −1  ' (25'')  zj    trong đó zj - được chọn theo 4 khả năng đã trình bày ở trên. c) Xét điều kiện (26). Vì λ > 0 , xkP0−1 < 0, RlP −1 > 0 nên điều kiện (26) được viết lại như sau : λ → min (26') Cuối cùng từ (24') , (25'') , (26') ta có : λ = max {-x P-1 , θ } (28) kl 2.7. Giải ví dụ bằng số Giải bài toán quy hoạch nguyên sau: Max x0 = 3 x1 + 6 x2 − 6 x3 − 3 x4 4 x1 − 2 x2 − 2 x3 − 9 x4 ≤ 5 2 x1 + 7 x2 + 6 x3 + 6 x4 ≥ 9 − 4 x1 + 8 x2 − 9 x3 ≤8 - 4 x4 ≤ 3 - 8 x1 x1 , x2 , x3 , x4 nguyên. Sau khi thêm biến bù bài toán viết lại thành Max x0 = 3 x1 + 6 x2 − 6 x3 − 3 x4 x5 = 5 − 4 x1 + 2 x2 + 2 x3 + 9 x4 x6 = −9 + 2 x1 + 7 x2 + 6 x3 + 6 x4 x7 = 8 + 4 x1 − 8 x2 + 9 x3 x8 = 3 + 8 x1 + 4 x4 x0 , x1 , x2 , x3 , x4 , x5 , x6 , x7 , x8 nguyên http://www.ebook.edu.vn
  10. V.10 Bùi Thế Tâm Quy hoạch rời rạc Từ đây ta có bảng đơn hình xuất phát (Bảng 1). Vì bảng đơn hình không là l- x1 + x2 + x3 + x4 ≤ gz = 100 hay chuẩn nên ta phải thêm ràng buộc phụ x9 = 100 − x1 − x2 − x3 − x4 - và x9 ≥ 0 và viết vào phía dưới bảng 1. Chọn dòng x9 làm dòng quay. 1 -x 1 -x2 -x3 -x4 x0 0 -3 -6 6 3 x1 0 -1 0 0 0 x2 0 0 -1 0 0 x3 0 0 0 -1 0 x4 0 0 0 0 -1 x5 5 4 -2 -2 -9 x6 -9 -2 -7 -6 -6 x7 8 -4 8 -9 0 x8 3 -8 0 0 -4 Bảng 1 x9 100 1 1* 1 1 Thực hiện một bước của đơn hình đối ngẫu từ vựng ta được bảng 2 là l-chuẩn. Vì x7
  11. V.11 Bùi Thế Tâm Quy hoạch rời rạc 1 -x10 -x9 -x3 -x4 x0 402 3 3 6 6 x1 66 -1 1 2 1 x2 34 1 0 -1 0 x3 0 0 0 -1 0 x4 0 0 0 0 -1 x5 -191 6 -4 -12 -13 x6 361 5 2 -9 -4 x7 0 -12 4 7 4 x8 531 -8 8 16 4 Bảng 3 x11 -15 0 -1* -1 -1 Tiếp tục dùng thuật toán đơn hình đối ngẫu từ vựng ta được bảng 4 là l- chuẩn và không chấp nhận được. Vì x7
  12. V.12 Bùi Thế Tâm Quy hoạch rời rạc 1 -x10 -x11 -x3 -x12 x0 312 3 0 0 3 x1 51 -1 1 1 0 x2 34 1 0 -1 0 x3 0 0 0 -1 0 x4 15 0 1 1 -1 x5 4 6 5 1 -9 x6 421 5 8 -5 -6 x7 -60 -12 4 3 0 x8 471 -8 12 12 -4 Bảng 5 x13 -5 -1* 0 0 0 Tiếp tục dùng thuật toán đơn hình đối ngẫu từ vựng ta được bảng 6 là l- chuẩn và không chấp nhận được. Vì x5
  13. V.13 Bùi Thế Tâm Quy hoạch rời rạc 1 -x13 -x11 -x3 -x14 x0 288 3 0 0 3 x1 56 -1 1 1 0 x2 29 1 0 -1 0 x3 0 0 0 -1 0 x4 18 0 1 1 -1 x5 1 6 5 1 -9 x6 414 5 8 -5 -6 x7 0 -12 4 3 0 x8 523 -8 12 12 -4 Bảng 7 λ ở mỗi bước) Bảng tổng hợp :(Phương án và giá trị λ P p p p p p p p p p x0 x1 x2 x3 x4 x5 x6 x7 x8 1 600 0 100 0 0 205 691 -792 3 12 2 402 66 34 0 0 -191 361 0 531 13 3 357 51 34 0 0 -131 331 -60 411 9 4 312 51 34 0 15 4 421 -60 471 12 5 297 56 29 0 15 -26 396 0 511 9 6 288 56 29 0 18 1 414 0 523 Vậy phương án tối ưu là (56, 29, 0, 18, 1, 414, 0, 523) với trị hàm mục tiêu là x[0]=288. 3. CHƯƠNG TRÌNH MÁY TÍNH • Thuật toán này dùng để giải bài toán quy hoạch tuyến tính nguyên hoàn toàn , có dạng: m x0 = ∑ c j x j → max j =1 m ∑ aij x j ≤ bi , i = 1,..., p j =1 xj ≥ 0, j = 1,2,..., m xj nguyên. http://www.ebook.edu.vn
  14. V.14 Bùi Thế Tâm Quy hoạch rời rạc các b[i] có thể dương và âm, phương án xuất phát không đối ngẫu chấp nhận được. m ∑ aij xi = bi thì ta thay thế bằng hai Nếu bài toán có ràng buộc đẳng thức dạng: j =1 bất đẳng thức: m m ∑ aij xi ≤ bi và ∑ aij xi ≥ bi . j =1 j =1 Sau khi thêm biến bù bài toán trên có thể viết ở dạng: m x0 = ∑ (−c j )(− x j ) → max j =1 x j = (−1)(− x j ) j = 1,2,..., m m xm+i = bi + ∑ (− aij )(− x j ) i = 1,2,..., p. j =1 xj ≥ 0 j = 1,2,..., m + p. j = 1,2,..., m + p. x j nguyên. • Trong chương trình sử dụng các biến và mảng sau: - m: số biến chính, n: số biến chính và biến bù của bài toán (n=m+p), gz là một số dương đủ lớn và thường lấy bằng max { aij , bi , c j } . - ss = 1 nếu bảng đơn hình s ban đầu là l- chuẩn, =2 nếu bảng không là l - chuẩn - Mảng s gồm n + 2 dòng và m+1 cột lúc đầu ghi dữ liệu của bài toán sau đó lưu bảng đơn hình ở mỗi bước. Dòng n+1 để chứa ràng buộc phụ. - s[0][0] hàm mục tiêu, cột 0 là cột phương án, dòng 0 là các ước lượng - cs : các biến ở bên trái bảng đơn hình, nc : các biến phi cơ sở • Cách nhập dữ liệu Dữ liệu ban đầu của bài toán được ghi trong một tệp văn bản, gồm có: - n, m, gz, ss. - Mảng s dữ liệu ban đầu bố trí dạng (ở dưới) và được ghi vào tệp dữ liệu theo từng dòng : http://www.ebook.edu.vn
  15. V.15 Bùi Thế Tâm Quy hoạch rời rạc -x1 -x2 . . . . . . . . . –xm x0 0 -c1 -c2 . . . . . . . . –cm x1 0 -1 0 .......... 0 x2 0 0 -1 . . . . . . . . . 0 xm 0 0 0 . . . . . . . . . . -1 xm+1 b1 -a11 . . . . . . . . . - a1m xn bp -ap1 . . . . . . . . . .-ap,m - Tiếp đến là mảng cs: nhập các số từ 0, 1, 2,…, n - Cuối cùng là mảng nc: nhập các số từ 1, 2,…, m • Với dữ liệu bài toán trên thì ta có tệp dữ liệu VDG3.CPPcó dạng: 8 4 100 2 0 -3 -6 6 3 0 -1 0 0 0 0 0 -1 0 0 0 0 0 -1 0 0 0 0 0 -1 5 4 -2 -2 -9 -9 -2 -7 -6 -6 8 -4 8 -9 0 3 -8 0 0 -4 012345678 1234 • Văn bản chương trình #include #include #include http://www.ebook.edu.vn
  16. V.16 Bùi Thế Tâm Quy hoạch rời rạc #include #define M 30 #define N 30 long int s[N+2][M+1],gz,t1,t2,lamda; double r; int sb,cmin,m,n,i,j,k,l,lc,tg,cs[N+2],nc[M+1], np[M+1]; int ka,blap,hl,hj,trong,zj[M+1],q,is,ss; unsigned long far *t; char *s1,*s2; FILE *f1,*f2; void biendoi(); void inbang(int cuoi); void main() { clrscr(); t= (unsigned long far *)MK_FP(0,0X46C); t1=*t; printf("\nCo in trung gian hay khong 1/0 ? "); scanf("%d%*c",&tg); // Nhap du lieu ban dau printf("\nVao ten tep so lieu : "); gets(s1); f1= fopen(s1,"r"); fscanf(f1,"%d%d%ld%d",&n,&m,&gz,&ss); for(i=0;i
  17. V.17 Bùi Thế Tâm Quy hoạch rời rạc fprintf(f2,"\nBang 1, so lieu ban dau, l- chuan"); lc = n; goto Lap1;} // Them rang buoc phu, tim bang l- chuan cs[n+1]=n+1; s[n+1][0]=gz; for (j=1;j
  18. V.18 Bùi Thế Tâm Quy hoạch rời rạc printf("\nPhan tu am cua phuong an ung voi dong %d",ka); if (tg==1) fprintf(f2,"\nPhan tu am cua phuong an ung voi dong %d",ka); // Bang don hinh la toi uu if (ka==-1) { printf("\nPHUONG AN TOI UU QHTT NGUYEN: "); if (tg==1) fprintf(f2,"\nPHUONG AN TOI UU QHTT NGUYEN: "); for (i=0; i
  19. V.19 Bùi Thế Tâm Quy hoạch rời rạc cmin=k; for (j=k+1;j
  20. V.20 Bùi Thế Tâm Quy hoạch rời rạc printf("\nMang NP : "); for (j=1;j

Tài liệu cùng danh mục Toán học

Đề thi cao học viện toán học 2009

Đề thi cao học viện toán học 2009 Các đề thi được xây dựng với nội dung đa dạng phong phú với hàm lượng kiến thức hoàn toàn nằm trong chương trình theo qui định của Bộ Giáo dục và Đào tạo.Tài liệu dùng làm tham khảo rất hay.


Lectures Applied statistics for business: Chapter 5 - ThS. Nguyễn Tiến Dũng

Lectures "Applied statistics for business - Chapter 5: Discrete probability distributions" provides students with the knowledge: Random variables, developing discrete probability distributions, expected value and variance, expected value and variance financial portfolios,... Invite you to refer to the disclosures.


TOÁN RỜI RẠC - CÂY – PHẦN 3

Tham khảo tài liệu 'toán rời rạc - cây – phần 3', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả


Complex Functions c-1 Examples concerning Complex Numbers

This is the first book containing examples from the Theory of Complex Functions. All the following books will have this book as their background. Even if I have tried to be careful about this text, it is impossible to avoid errors, in particular in the first edition. It is my hope that the reader will show some understanding of my situation.


Đề thi môn: Lý thuyết xác suất thống kê

Tài liệu trên đây dành cho các bạn sinh viên chuyên ngành Khoa học tự nhiên muốn ôn thi cuối kỳ môn "Lý thuyết xác suất thống kê" là một môn bắt buộc trong chương trình học. Đề thi gồm 4 câu tự luận. Chia sẻ cùng các bạn tham khảo để củng cố lại kiến thức và rèn luyện kỹ năng làm bài tập.


Giáo trình toán học Tập 5 P14

Các định thức đựoc dùng để kiểm tra các ma trận có ma trận nghịch đảo không (các ma trận khả nghịch và chỉ chúng là các ma trận có định thức khác 0) và để biểu diễn nghiệm của một hệ phương trình tuyến tính qua định lý Cramer. chúng được dùng để tìm các vector riêng của ma trận A qua đa thức đặc trưng


PROBLEMS AND THEOREMS IN LINEAR ALGEBRA

There are many books on linear algebra, in which many people are really great ones (see for example the list of recommended literature). One might think that one does no books on this subject. Choose a person's words more carefully, it can deduce that this book contains everything needed and the best possible, and so any new book, just repeat the old ones. This idea is evident wrong, but almost everywhere. New results in linear algebra and are constantly appearing so refreshing, simple and neater proof of the famous theorem. In addition, more than a few years interesting results are ignored, so far, the text books. In this book,...


LÝ THUYẾT XÁC SUẤT PHẦN 1 - TRẦN DIÊN HIỂN - 1

THÔNG TIN CƠ BẢN Ta xét bài toán: “Gieo một đồng tiền xu và một con xúc xắc. Tìm xác suất để xuất hiện mặt ngửa trên đồng tiền và mặt có số chấm là bội của 3 trên con xúc xắc". Mỗi biến cố trong phép thử này có dạng: N ∩ Qk = "Trên đồng tiền xuất hiện mặt ngửa và con xúc xắc xuất hiện mặt k chấm", k = 1, 2, ..., 6 hoặc S ∩ Qk = "Trên đồng tiền xuất hiện mặt sấp và con xúc xắc xuất hiện mặt k chấm", k = 1,...


Giải tích 2 – Đề số 7

Tài liệu tham khảo đề giải tích số 7, kèm theo lời giải cụ thể, giúp các bạn dễ dàng hơn trong việc ôn tập môn toán giải tích.


Đề thi môn Xác suất thống kê: Đề số 03

Đề thi môn Xác suất thống kê: Đề số 03 của trường Đại học Đông Á bao gồm 4 câu hỏi tự luận với các nội dung chính về biến ngẫu nhiên rời rạc; xác suất thống kê; biến chuẩn;... Cùng tìm hiểu để nắm bắt nội dung thông tin tài liệu.


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

Modern Algebra With Applications 2nd
  • 31/10/2012
  • 34.300
  • 558
Chương 6: Lập trình Hàm
  • 25/10/2012
  • 36.225
  • 283
Số học thuật toán P1
  • 24/08/2010
  • 41.895
  • 510
Ebook Phương trình vi phân
  • 13/09/2016
  • 33.275
  • 213
Bài 14 Chuỗi lũy thừa
  • 25/05/2013
  • 76.250
  • 514

Bộ sưu tập

Danh mục tài liệu