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

Chia sẻ: Nguyen Nhi | Ngày: | Loại File: PDF | Số trang:23

Thêm vào BST

Báo xấu

208
lượt xem 39
download

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

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...

Chủ đề:

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

Lưu

Nội dung Text: QUY HOẠCH RỜI RẠC - CHƯƠNG 5

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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
V.19 Bùi Thế Tâm Quy hoạch rời rạc cmin=k; for (j=k+1;j
V.20 Bùi Thế Tâm Quy hoạch rời rạc printf("\nMang NP : "); for (j=1;j