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

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

Thêm vào BST

Báo xấu

188
lượt xem 34
download

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

THUẬT TOÁN GOMORY THỨ HAI Chương này trình bày hai thuật toán: thuật toán Gomory thứ hai dùng để giải bài toán quy hoạch tuyến tính nguyên bộ phận, thuật toán Dalton - Llewellyn dùng để giải bài toán quy hoạch tuyến tính với các biến nhận giá trị rời rạc.

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 4

IV.1 Bùi Thế Tâm Quy hoạch rời rạc Chương 4 THUẬT TOÁN GOMORY THỨ HAI Chương này trình bày hai thuật toán: thuật toán Gomory thứ hai dùng để giải bài toán quy hoạch tuyến tính nguyên bộ phận, thuật toán Dalton - Llewellyn dùng để giải bài toán quy hoạch tuyến tính với các biến nhận giá trị rời rạc. 1. LƯỢC ĐỒ LOGIC CHUNG CỦA THUẬT TOÁN Xét bài toán quy hoạch rời rạc: n x0 = ∑ c j x j Max (1) j =1 n ∑a x = bi i = 1,..., m (2) ij j j =1 xj ≥ 0 j = 1,..., n (3) x j ∈ Dj j = 1,..., n1 ; n1 ≤ n (4) D D Bài toán này kí hiệu là (L ,C) =(L0 ,C) LD là miền chấp nhận được của bài toán (LD,C) Dj là các tập rời rạc. Điều kiện rời rạc (4) có thể có các dạng khác nhau trong các trường hợp cụ thể. Ta giả sử rằng: 1) Hàm mục tiêu x0 bị chặn trên trên miền (2)- (3) 2) Nếu tập phương án tối ưu của bài toán (1) – (3) khác rỗng thì nó phải bị chặn Lược đồ logic của thuật toán như sau: ( )( ) Bước lặp ban đầu. Giải l - bài toán L, C ≡ L0 , C xác định bởi (1) – (3). Nếu ( ) nó không giải được thì bài toán ( LD , C ) cũng không giải được. Nếu bài toán L0 , C giải 0 ( ) được và phương án X L0 , C thoả mãn điều kiện rời rạc (4) thì nó đồng thời là phương ( ) án tối ưu của bài toán ( LD , C ) . Nếu X L0 , C không thoả mãn điều kiện rời rạc thì chuyển sang bước lặp thứ r = 0 ( ) Bước lặp thứ r (r ≥ 0). Giả sử X Lr , C không thoả mãn điều kiện rời rạc, ta x0 = CX và x1 ,x2 , …,xn qua các biến phi cơ sở xj (j ∈ N r ) biểu diễn hàm mục tiêu xi = xir0 + ∑ xij ( − x j ) , i = 0,1,..., n r j∈N r và nhận được bảng đơn hình Tr = xij r là chấp nhận được và là l - chuẩn. Chọn k là dòng có chỉ số nhỏ nhất ứng với thành phần không thoả mãn điều kiện rời rạc { } k = min i i ∈ {1,..., n1} ; xir0 ∉ Di http://www.ebook.edu.vn
IV.2 Bùi Thế Tâm Quy hoạch rời rạc và theo một qui tắc nào đó (tùy từng thuật toán) ta xây dựng lát cắt đúng : xn+ r +1 = γ 0 + ∑ γ j ( − x j ) (5) j∈N r xn+ r +1 ≥ 0 (6) Viết dòng (5) vào cuối bảng đơn hình Tr ta được bảng mới là không chấp nhận được (chỉ đối với dòng cuối cùng vừa thêm vào) và là l - chuẩn. Sau khi đưa xn+r+1 ra khỏi cơ sở thì dòng tương ứng sẽ bị xoá, nếu đưa vào cơ sở xl ( l ≥ n + 1 ) thì dòng tương ứng không phục hồi. Nếu nhận được bảng đơn hình ứng với bài toán qui hoạch tuyến tính không giải được thì bài toán ( LD , C ) không giải được. Nếu nhận được bảng 0 đơn hình Tr+1 là chấp nhận được và l - chuẩn thì kiểm tra phương án l - tối ưu ( ) X Lr +1 , C có thoả mãn điều kiện rời rạc (4) hay không, nếu nó thoả mãn thì nó là phương án tối ưu của bài toán ( LD , C ) , nếu không thoả mãn thì chuyển sang bước lặp 0 thứ r+1 2. THUẬT TOÁN GOMORY THỨ HAI 2.1. Thuật toán này cho phép ta giải các bài toán qui hoạch tuyến tính nguyên bộ phận n x0 = ∑ c j x j Max (7) j =1 n ∑a x = bi i = 1,..., m (8) ij j j =1 xj ≥ 0 j = 1,..., n (9) nguyên j = 1,..., n1 ; n1 ≤ n xj (10) 2.2. Định lý 1. Giả sử X ( Lr , C ) ≡ X r là phương án tựa tối ưu của bài toán ( Lr , C ) và Tr là bảng đơn hình tương ứng, xir0 không nguyên với 1 ≤ i ≤ n1 (hoặc 0 ≤ i ≤ n1 nếu hàm mục tiêu cũng yêu cầu đảm bảo tính nguyên). Khi đó bất đẳng thức ∑γ xj ≥ γ0 (11) j j∈N r hoặc nó được viết lại là ∑γ Z = −γ 0 + xj (12) j j∈N r Z ≥0 (13) là một lát cắt đúng, trong đó: http://www.ebook.edu.vn
IV.3 Bùi Thế Tâm Quy hoạch rời rạc γ 0 = { xir0 } { xij} {x } ≤ {x } j ≤ n1 , r r r ij i0   { xir0 } ( ) 1 − { xij} {x } > {x }  j ≤ n1 , r r r 1 − { xi 0 } ij i0 r (14) γj = r j ≥ n1 + 1, xij ≥ 0 r  xij   { xi 0 } r 1 − x r ( − xij ) j ≥ n1 + 1, xij < 0 r r  { i0}  Chứng minh định lý 1. Trước hết điều kiện cắt được thỏa mãn là do x rj = 0 < { xir0 } = γ 0 (vì xir0 không nguyên) ∑γ j j∈N r Kiểm tra điều kiện đúng. Viết khai triển của xi theo các biến phi cơ sở: ∑ x (−x ) . xi = xir0 + r ij j j∈N r Giả sử  xij j ∈ N r , j ≥ n1 + 1 '  x = ' r ij  xij + yij j ∈ N r , j ≤ n1  ở đây yij là số nguyên nào đó chọn sau sao cho các hệ số của lát cắt là nhỏ nhất. Khi đó yi j x j = { xir0 } + ∑ ∑x xi −  xir0  + (− x j ) ≡ Z i ( X ) . '  ij j∈N r , j ≤ n1 j∈N r Nếu X là một phương án của bài toán qui hoạch tuyến tính nguyên thì Z i ( X ) là nguyên. Ta đặt: { } N r+ = j j ∈ N r , − xij > 0 ' ={ j j∈N ≤ 0} N r− , − xij ' r ∑ (−x ) x S+(X ) = ≥0 ' (15) ij j + j∈N r ∑ (−x ) x S−(X ) = ≤0 ' (16) ij j − j∈N r và viết lại {x } S r i0 + (X ) ≥ 0 (17) 1 − {x } r i0 − S−(X ) ≥0 (18) http://www.ebook.edu.vn
IV.4 Bùi Thế Tâm Quy hoạch rời rạc Tiếp tục ta nhận được: {x } + S + ( X ) + S − ( X ) = Z i ( X ) ( Z i ( X ) nguyên). r i0 Ta có hai trường hợp sau: Z i ( X ) ≥ { xir0 } > 0 , và do Trường hợp 1: S + ( X ) + S − ( X ) ≥ 0 . Khi đó Z i ( X ) nguyên nên Z i ( X ) ≥ 1 , suy ra S + ( X ) + S − ( X ) ≥ 1 − { xir0 } , tiếp theo do (18) S + ( X ) ≥ 1 − { xir0 } − S − ( X ) ≥ 1 − { xir0 } . Vì vậy {x } S r ( X ) ≥ { xir0 } i0 + (19) 1 − {x } r i0 {} Trường hợp 2: S + ( X ) + S − ( X ) < 0 . Khi đó Z i ( X ) < xir0 , và do Z i ( X ) nguyên nên Z i ( X ) ≤ 0 . Suy ra {x } + S + ( X ) + S − ( X ) = Zi ( X ) ≤ 0 r i0 − S − ( X ) ≥ { xir0 } + S + ( X ) ≥ { xir0 } (do S + ( X ) ≥ 0) − S − ( X ) ≥ { xir0 } (20) Hợp nhất trong Trường hợp 1 gồm (19) và (18), trong Trường hợp 2 gồm (20) và (17) ta được bất đẳng thức {x } S r ( X ) − S − ( X ) ≥ { xir0 } , i0 + 1 − {x } r i0 hay viết lại là {x } − x x + x x ≥ x r ∑ 1 − {x } ( ) ∑ ( ) { } i0 ' ' r (21) ij j ij j i0 r j∈N r+ j∈N r− i0 Chú ý rằng bất đẳng thức (21) có dạng x j ≥ { xir0 } ∑γ j j∈N r γ j = γ j ( yij ) , j ≤ n1 γ j ≥ 0 và γ 0 = { xir0 } không phụ thuộc vào cách chọn yij . Vì vậy các số yij nên ở đây chọn sao cho γ j ( yij ) là nhỏ nhất, trong trường hợp đó sẽ cắt được phần đa diện Lr nhiều nhất. a) Từ (21) và xij = xij − yij , j ∈ N r , j ≤ n1 ta có ' r http://www.ebook.edu.vn
IV.5 Bùi Thế Tâm Quy hoạch rời rạc  { xir0 } r ( ij y − xij ) khi yij − xij > 0  r r  γ j ( yij ) = 1 − { xi 0 } r  xij − yij khi xij − yij ≥ 0 r  Khi xij nguyên ta có thể đặt yij = xij và ta nhận được γ j = γ j ( yij ) = 0 , đó là cực r r tiểu của γ j ( yij ) (vì γ j ( yij ) ≥ 0 ). r Trường hợp xij không nguyên, khi đó  { xir0 } { xir0} 1 − xr  ( )   r ( ij y − xij ) yij − xij > 0  = { ij} A = min  r r 1 − { xi 0 }  1 − { xi 0 } r   (vì yij − xij = yij −  xij  − { xij} nên A đạt cực tiểu khi ta chọn yij =  xij  + 1 ).  r r r r  { } B = min xij − yij xij − yij ≥ 0 = { xij} r r r {} (vì xij =  xij  + xij nên B đạt cực tiểu khi ta chọn yij =  xij  ). r r r r   Như vậy khi tính đến điều kiện cực tiểu ta nhận được  { xir0 }  ( )  r 1 − { xij} , { xij} γ j = min  r 1 − { xi 0 } r    {x } (1 − x ) với (0 ≤ x ≤ 1) r i0 Đối với hàm tuyến tính Z ( x) = ta có: 1 − {x } r i0 {x } > x r {} i0 Z (0) = r 1 − {x } i0 r i0 Z ({ x } ) = { x } r r i0 i0 Z (1) = 0 < 1. khi x ≤ { xir0 } x  min {Z ( x), x} =  Do đó ta có  Z ( x) khi x > { xi 0 }. r  Áp dụng điều đó để tính hệ số của lát cắt ta nhận được biểu thức: { xij} khi { xij} ≤ { xir0 } r r   γ j =  { xir0 } ( ) 1 − { xij} {x } > {x } j ∈ N r , j ≤ n1 r r r khi  1 − { xi 0 } ij i0 r  b) Còn với j ∈ N r , j ≥ n1 + 1 thì xij = xij . Từ (21) ta có ' r http://www.ebook.edu.vn
IV.6 Bùi Thế Tâm Quy hoạch rời rạc  xij khi j > n1 , xij ≥ 0 r r   γ j =  { xir0 } r( − xij ) khi j > n1 , xij < 0 r r  1 − { xi 0 }  Định lý đã được chứng minh xong. ( ) 2.3. Quy tắc xây dựng lát cắt đúng. Giả sử X Lr , C không thoả mãn điều r kiện nguyên (10) và Tr = xij là bảng đơn hình tương ứng. Chọn { } k = min i i ∈ {1,2,..., n1} ; xir0 không nguyên Nếu hàm mục tiêu x0 cũng thoả mãn điều kiện nguyên thì chọn { } k = min i i ∈ {0,1,2,..., n1} ; xir0 không nguyên và xây dựng lát cắt đúng: xn+ r +1 ≥ 0 ∑ ( −γ )( − x ) xn+ r +1 = −γ 0 + j j j∈N r γ 0 , γ j tính theo (14) với i = k. trong đó 2.4. Tính hữu hạn của thuật toán Gomory thứ 2 chứng minh tương tự như chứng minh tính hữu hạn của thuật toán Gomory thứ nhất. Khi đó đòi hỏi các điều kiện: 1) Hàm mục tiêu x0 thoả mãn điều kiện nguyên, điều đó được tính đến khi chọn dòng k để xây dựng lát cắt đúng. 2) Thực hiện một trong hai điều kiện: - Hàm mục tiêu x0 bị chặn dưới trên tập đa diện lồi L ≡ L0 ( ) N - Bài toán L0 , C có ít nhất một phương án Nhờ thuật toán Gomory thứ 2 (khi n1 = n) ta có thể giải bài toán qui hoạch tuyến tính nguyên toàn phần, nhưng không có cơ sở để so sánh hiệu quả của hai phương pháp 2.5. Giải ví dụ bằng số Giải bài toán quy hoạch tuyến tính nguyên bộ phận sau: Max x0 = 3 x1 − x2 + 4 x3 9 x1 − 5 x2 + 2 x3 ≥ 4 3 x1 + 6 x2 − 2 x3 ≤ 18 7 x1 + 5 x2 + 7 x3 ≥ 2 − 2 x1 + 5 x2 + 10 x3 ≤ 3 xj ≥ 0 , j = 1,2,3. http://www.ebook.edu.vn
IV.7 Bùi Thế Tâm Quy hoạch rời rạc x1 , x2 nguyên x0 nguyên. Sau khi thêm các biến bù bài toán trở thành: Max x0 = 3 x1 − x2 + 4 x3 x4 = −4 + 9 x1 − 5 x2 + 2 x3 x5 = 18 − 3 x1 − 6 x2 + 2 x3 x6 = −2 + 7 x1 + 5 x2 + 7 x3 x7 = 3 + 2 x1 − 5 x2 − 10 x3 x1 , x2 , x3 , x4 , x5 , x6 , x7 ≥ 0 x0 , x1 , x2 nguyên. Vì bảng đơn hình ban đầu không l- chuẩn ta cần thêm ràng buộc phụ: x1 + x2 + x3 ≤ gz = 100 hay x8 = 100 − x1 − x2 − x3 và x8 ≥ 0 và viết vào phía dưới bảng 1.Ta có bảng đơn hình xuất phát sau khi thêm ràng buộc phụ: 1 - x1 -x2 -x3 x0 0.00000 -3.00000 1.00000 -4.00000 x1 0.00000 -1.00000 0.00000 0.00000 x2 0.00000 0.00000 -1.00000 0.00000 x3 0.00000 0.00000 0.00000 -1.00000 x4 -4.00000 -9.00000 5.00000 -2.00000 x5 18.00000 3.00000 6.00000 -2.00000 x6 -2.00000 -7.00000 -5.00000 -7.00000 x7 3.00000 -2.00000 5.00000 10.00000 Bảng 1 x8 100.00000 1.00000 1.00000 1.00000* 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à tiếp tục một bước đơn hình đối ngẫu từ vựng ta được bảng 3 và bảng 4 http://www.ebook.edu.vn
IV.8 Bùi Thế Tâm Quy hoạch rời rạc 1 - x1 -x2 -x8 x0 400.00000 1.00000 5.00000 4.00000 x1 0.00000 -1.00000 0.00000 -0.00001 x2 0.00000 0.00000 -1.00000 -0.00001 x3 100.00000 1.00000 1.00000 1.00000 x4 196.00000 -7.00000 7.00000 2.00000 x5 218.00000 5.00000 8.00000 2.00000 x6 698.00000 0.00000 2.00000 7.00000 x7 -997.00000 -12.00000* -5.00000 -10.00000 Bảng 2 1 - x7 -x2 -x8 x0 316.91667 0.08333 4.58333 3.16667 x1 83.08333 -0.08333 0.41667 0.83333 x2 0.00000 0.00000 -1.00000 -0.00001 x3 16.91667 0.08333 0.58333 0.16667 x4 777.58333 -0.58333 9.91667 7.83333 x5 -197.41667 0.41667 5.91667 -2.16667 * x6 698.00000 0.00000 2.00000 7.00000 x7 0.00000 -1.00000 0.00000 0.00000 Bảng 3 1 - x7 -x2 -x5 x0 28.38462 0.69231 13.23077 1.46154 x1 7.15385 0.07692 2.69231 0.38462 x2 0.00000 0.00000 -1.00000 -0.00001 x3 1.73077 0.11538 1.03846 0.07692 x4 63.84615 0.92308 31.30769 3.61538 x5 0.00000 0.00000 0.00000 -1.00000 x6 60.19231 1.34615 21.11538 3.23077 x7 0.00000 -1.00000 0.00000 0.00000 Bảng 4 x9 -0.38462 -0.69231* -0.23077 -1.46154 http://www.ebook.edu.vn
IV.9 Bùi Thế Tâm Quy hoạch rời rạc Tám dòng đầu của bảng 4 là bảng đơn hình l- chuẩn và chấp nhận được. Do x0 lẻ nên từ dòng 0 sinh ra lát cắt ở dòng x9 theo quy tắc lát cắt đúng và ta được bảng 4. Thực hiện một bước của thuật toán đơn hình đối ngẫu từ vựng ta được bảng 5 là bảng đơn hình l- chuẩn và chấp nhận được. Biến x1 lẻ nên từ dòng x1 sinh ra lát cắt ở dòng x10. 1 - x9 -x2 -x5 x0 28.00000 1.00000 13.00000 0.00000 x1 7.11111 0.11111 2.66667 0.22222 x2 0.00000 0.00000 -1.00000 -0.00000 x3 1.66667 0.16667 1 -0.16667 x4 63.33333 1.33333 31 1.66667 x5 0.00000 0.00000 0.00000 -1.00000 x6 59.44444 1.94444 20.66667 0.38889 x7 0.55556 -1.44444 0.33333 2.11111 Bảng 5 x10 -0.11111 -0.11111 -0.04167 -0.22222* Thực hiện một bước của thuật toán đơn hình đối ngẫu từ vựng ta được bảng 6 là bảng đơn hình l- chuẩn và không chấp nhận được (do x7 nhận giá trị âm). 1 - x9 -x2 -x10 x0 28.00000 1.00000 13.00000 0.00000 x1 7.00000 0.00000 2.625 1.00000 x2 0.00000 0.00000 -1.00000 -0.00001 x3 1.75000 0.25000 1.03125 -0.75000 x4 62.50000 0.50000 30.6875 7.50000 x5 0.50000 0.50000 0.1875 -4.50000 x6 59.25000 1.75000 20.59375 1.75000 x7 -0.50000 -2.50000* -0.0625 9.50000 Bảng 6 Tiếp tục dùng thuật toán đơn hình đối ngẫu từ vựng giải bài toàn quy hoạch tuyến tính phụ ta được bảng 7. Bảy dòng đầu của bảng là bảng đơn hình l- chuẩn và chấp nhận được. Do x0 lẻ nên từ dòng 0 sinh ra lắt cắt ở dòng x11 theo quy tắc . Chọn dòng x11 làm dòng quay. http://www.ebook.edu.vn
IV.10 Bùi Thế Tâm Quy hoạch rời rạc 1 - x7 -x2 -x10 x0 27.80000 0.40000 12.975 3.80000 x1 7.00000 0.00000 2.625 1.00000 x2 0.00000 0.00000 -1.00000 0.00000 x3 1.70000 0.10000 1.025 0.20000 x4 62.40000 0.20000 30.675 9.40000 x5 0.40000 0.20000 0.175 -2.60000 x6 58.90000 0.70000 20.55 8.40000 x7 0.00000 -1.00000 0.00000 0.00000 Bảng 7 x11 -0.80000 -0.40000* -0.1 -3.80000 Thực hiện một bước của thuật toán đơn hình đối ngẫu từ vựng ta được bảng 8 là bảng đơn hình l- chuẩn và không chấp nhận được (do x5 nhận giá trị âm). 1 - x11 -x2 -x10 x0 27.00000 1.00000 12.875 0.00000 x1 7.00000 0.00000 2.625 1.00000 x2 0.00000 0.00000 -1.00000 0.00000 x3 1.50000 0.25000 1 -0.75000 x4 62.00000 0.50000 30.625 7.50000 x5 -0.0000001 0.50000 0.125 -4.50000* x6 57.50000 1.75000 20.375 1.75000 x7 2.00000 -2.50000 0.25 9.50000 Bảng 8 Tiếp tục dùng thuật toán đơn hình đối ngẫu từ vựng giải bài toàn quy hoạch tuyến tính phụ ta được bảng 9 là bảng đơn hình l- chuẩn và chấp nhận được, có cột phương án là nguyên và quá trình lặp kết thúc. 1 - x11 -x2 -x5 x0 27.00000 1.00000 12.875 0.00000 x1 7.00000 0.11111 2.65278 0.22222 x2 0.00000 0.00000 -1.00000 0.00000 x3 1.50000 0.16667 0.97917 -0.16667 x4 62.00000 1.33333 30.83333 1.66667 x5 0.00000 0.00000 0 -1.00000 x6 57.50000 1.94444 20.42361 0.38889 x7 2.00000 -1.44444 0.51389 2.11111 http://www.ebook.edu.vn
IV.11 Bùi Thế Tâm Quy hoạch rời rạc Bảng 9 Vậy phương án tối ưu là (7, 0, 1.5, 62, 0, 57.5, 2) với trị tối ưu là x[ 0] = 27 . 2.6. 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 bộ phậ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 x j ∈ D j , j = 1,2,..., n1 ; n 1 ≤ m 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. Nếu m ∑ aij xi = bi thì ta thay bài toán giải có ràng buộc đẳng thức dạng: j =1 m m ∑ aij xi ≤ bi và ∑ aij xi ≥ bi . thế bằng hai bất đẳng thức: 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. x j ∈ D j , j = 1,2,..., n1 ; n 1 ≤ m • 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 } , http://www.ebook.edu.vn
IV.12 Bùi Thế Tâm Quy hoạch rời rạc - x0 =0 nếu x0 đòi hỏi nguyên và bằng 1 nếu x0 không cần nguyên. - ss = 1 nếu bảng đơn hình xuất phát s là l- chuẩn và chấp nhận được, = 2 nếu bảng là l- chuẩn và không chấp nhận được, =3 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 Các 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, n1, x0, 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 : -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 . . . . . . . . . .-apm - 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ì vào số liệu sau được ghi ở tệp VDG2.CPP 7 3 100 2 0 3 0 -3 1 -4 0 -1 0 0 0 0 -1 0 0 00 -1 http://www.ebook.edu.vn
IV.13 Bùi Thế Tâm Quy hoạch rời rạc -4 -9 5 -2 18 3 6 -2 -2 -7 -5 -7 3 -2 5 10 01234567 123 • Văn bản chương trình #include #include #include #include #define M 30 #define N 30 double s[N+2][M+1],r,gz,t4,t5; int kgd,kgd2,blap,blap2,sb,cmin,x0,ss; int m,n,n1,i,j,k,l,le,lc,tg,cs[N+2],nc[M+1]; unsigned long far *t; long int t1,t2; char *s1,*s2; FILE *f1,*f2; int ktnguyen(double x); int cotquay(); void biendoi(); void inbang(int cuoi); int dhdoingau(); 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 printf("\nVao ten tep so lieu : "); gets(s1); f1=fopen(s1,"r"); fscanf(f1,"%d%d%lf%d%d%d",&n,&m,&gz,&n1,&x0,&ss); for (i=0;i
IV.14 Bùi Thế Tâm Quy hoạch rời rạc for (j=1; j
IV.15 Bùi Thế Tâm Quy hoạch rời rạc } } printf("\nDong quay= %d, Cot quay= %d, Phan tu quay =%13.5lf", l,cmin,s[l][cmin]); if (tg==1) { fprintf(f2,"\nDong quay= %d, Cot quay= %d, Phan tu quay= %13.5lf", l,cmin,s[l][cmin]); } biendoi(); sb++; printf("\nBang %d, l- chuan dau tien",sb); if (tg==1) fprintf(f2,"\nBang %d, l- chuan dau tien",sb); inbang(0); lc = n+1; L1: kgd2= dhdoingau(); if (kgd2==1) { printf("\nBai toan phu khong giai duoc, STOP"); if (tg==1) fprintf(f2,"\nBai toan phu khong giai duoc,STOP"); getch(); getch(); return; } // Tim xong bang l- chuan + chap nhan duoc, sang Buoc lap lon Lap1: blap = blap+1; printf("\n------------------------------------------------"); printf("\n\nBUOC LAP LON THU %d: ",blap); if (tg==1) { fprintf(f2,"\n---------------------------------------"); fprintf(f2,"\n\nBUOC LAP LON THU %d: ",blap);} // Kiem tra loi giai toi uu bai toan phu co nguyen khong le=-1; for(i=x0;i
IV.16 Bùi Thế Tâm Quy hoạch rời rạc fprintf(f2,"\nx[%2d] = %13.5lf",cs[i],s[i][0]); fprintf(f2,"\nSo luong lat cat: %d lat cat",blap-1); fprintf(f2,"\nSo bang don hinh da lap : %d bang",sb); } t= (unsigned long far *)MK_FP(0,0X46C); t2=*t; printf("\nThoi gian chay chuong trinh: %ld giay", (long int)((t2-t1)/18.21)); if (tg==1) fprintf(f2,"\nThoi gian chay chuong trinh:%ld giay", (long int)((t2-t1)/18.21)); fclose(f2); getch(); return; } // Tao lat cat moi va ghi vao cuoi bang lc++; cs[n+1]=lc; s[n+1][0]= -(s[le][0]- floor(s[le][0])); for (j=1; j
IV.17 Bùi Thế Tâm Quy hoạch rời rạc if (tg==1) fprintf(f2,"\nCot quay=%d,Phan tu quay=%13.5lf",cmin,s[l][cmin]); // Bien doi bang don hinh biendoi(); sb++; printf("\nBang %d, bang dau tien bai toan phu",sb); if (tg==1) fprintf(f2,"\nBang %d, bang dau tien bai toan phu",sb); inbang(0); kgd2= dhdoingau(); if (kgd2==1) { printf("\nBai toan phu khong giai duoc"); if (tg==1) fprintf(f2,"\nBai toan phu khong giai duoc, STOP"); getch(); getch(); return; } goto Lap1; } int ktnguyen(double x) { long int h; double z; z=fabs(x); h=(int)(z+0.5); if (fabs(z-h)
IV.18 Bùi Thế Tâm Quy hoạch rời rạc s[l][j]=0; } for (i=0;i
IV.19 Bùi Thế Tâm Quy hoạch rời rạc if (tg==1) fprintf(f2,"\nDong quay = %d",l); if (l==-1) { printf("\nBang tren ung phuong an toi uu cua bai toan phu"); if (tg==1) fprintf(f2,"\nBang tren ung phuong an toi uu bai toan phu"); return 0; } else { kgd=cotquay(); if (kgd==1) return 1; printf("\nCot quay=%d, Phan tu quay=%13lf",cmin,s[l][cmin]); if (tg==1) fprintf(f2,"\nCot quay = %d, Phan tu quay =%13.5lf", cmin,s[l][cmin]); biendoi(); sb++; printf("\nBang %d, DHDN",sb); if (tg==1) fprintf(f2,"\nBang %d, DHDN",sb); inbang(0); goto Lap2; } } • Sau khi chạy chương trình ta nhận được lời giải tối ưu của bài toán trên là: x[ 0] = 27.00000 x[ 1] = 7.00000 x[ 2] = 0.00000 x[ 3] = 1.50000 x[ 4] = 62.00000 x[ 5] = 0.00000 x[ 6] = 57.50000 x[ 7] = 2.00000 Số lượng lát cắt: 3 lát cắt Số bảng đơn hình đã lập : 9 bảng 3. THUẬT TOÁN DALTON VÀ LLEWELLYN 3.1. Dalton cải tiến thuật toán Gomory thứ hai cho bài toán qui hoạch tuyến tính rời rạc bộ phận sau: http://www.ebook.edu.vn
IV.20 Bùi Thế Tâm Quy hoạch rời rạc n x0 = ∑ c j x j Max (22) j =1 n ∑a x = bi i = 1,..., m (23) ij j j =1 xj ≥ 0 j = 1,..., n (24) { } x j ∈ A j ≡ Aj1 , Aj 2 ,... Ajq j , j = 1,..., n1 ; n1 ≤ n (25) 0 = Aj1 < Aj 2 < ... < Ajq j , j = 1,..., n1 Nếu cần ta bổ sung bất đẳng thức x j ≤ Ajq j , j = 1,..., n1 (26) vào điều kiện (23), khi đó phương án X của bài toán (L0,C) (22) – (24) thoả mãn điều kiện 0 ≤ x j ≤ Ajq j , j = 1,..., n1 . 3.2. Định lý 1. Giả sử X ( Lr , C ) ≡ X r là phương án tựa tối ưu của bài toán ( Lr , C ) và Tr = r xij là bảng đơn hình tương ứng, 1 ≤ i ≤ n1 Aiυ < xir0 < Ai ,υ +1 Khi đó bất đẳng thức ∑γ xj ≥ γ0 (27) j j∈N r hay viết lại là ∑γ Z = −γ 0 + xj (28) j j∈N r Z ≥0 (29) là một lát cắt đúng, trong đó: γ 0 = xir0 − Aiυ (30)  xij xij ≥ 0 r r  γ j =  xir0 − Aiυ (31)  A − x r ( − xij ) xij < 0 r r  i ,υ +1 i 0 Chứng minh định lý. Kiểm tra tính cắt: ∑γ x rj = 0 < γ 0 = xir0 − Aiυ (do x rj = 0 ). j j∈N r Kiểm tra tính đúng. Giả sử X là phương án của bài toán rời rạc, với i đã chọn, biểu diễn xi qua các biến phi cơ sở như sau: ∑ (−x ) x xi = xir0 + r (32) ij j j∈N r Có 2 khả năng: http://www.ebook.edu.vn