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

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

Thêm vào BST

Báo xấu

211
lượt xem 46
download

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

THUẬT TOÁN GOMORY THỨ NHẤT Trong chương này sẽ trình bày thuật toán Gomory thứ nhất và chứng minh sự hội tụ của nó. 1. TƯ TƯỞNG PHƯƠNG PHÁP CẮT 1.1. Việc giải bài toán quy hoạch tuyến tính nguyên (LN ,C ) có dẫn tới việc giải một bài toán quy hoạch tuyến tính (A,C ) không ? Định lý 1. Giả sử L là một đa diện lồi, LN là tập các điểm nguyên của nó, R ≡ V (LN ) là bao lồi tuyến tính của tập các điểm nguyên LN . Khi đó: 1) R ≡ V (LN ) là một...

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 3

Bùi Thế Tâm III.1 Quy hoạch rời rạc Chương 3 THUẬT TOÁN GOMORY THỨ NHẤT Trong chương này sẽ trình bày thuật toán Gomory thứ nhất và chứng minh sự hội tụ của nó. 1. TƯ TƯỞNG PHƯƠNG PHÁP CẮT 1.1. Việc giải bài toán quy hoạch tuyến tính nguyên (LN ,C ) có dẫn tới việc giải một bài toán quy hoạch tuyến tính (A,C ) không ? Định lý 1. Giả sử L là một đa diện lồi, LN là tập các điểm nguyên của nó, R ≡ V (LN ) là bao lồi tuyến tính của tập các điểm nguyên LN . Khi đó: 1) R ≡ V (LN ) là một đa diện nguyên (các đỉnh đều là nguyên) 2) RN = LN (1) 3) Tập R* các phương án tựa của đa diện R chứa trong RN : R* ⊆ RN (2) Chứng minh 1) Chứng minh R là một đa diện nguyên ? Vì L là một đa diện lồi nên LN là tập hữu hạn ⇒ R ≡ V (LN ) là tổ hợp lồi tuyến tính của một tập hữu hạn . Vì vậy, R là một đa diện , đồng thời R* ⊆ LN (3) (tức là R là đa diện nguyên). 2) Chứng minh RN = LN ? Từ định nghĩa bao lồi tuyến tính suy ra LN ⊆ V (LN ) ≡ R ⇒ LN ⊆ RN . (4) Ta phải chứng minh: RN ⊆ LN ? (5) Thật vậy, giả sử lấy x ∈ RN , (6) vì LN ⊆ L nên R = V (LN ) ⊆ V (L) = L . Vì vậy x ∈ RN ⊆ R ⊆ L (7) Từ (6) và (7) suy ra x ∈ LN (vì x là nguyên thuộc L), vậy (5) được chứng minh. Từ (4) và (5) suy ra đẳng thức (1) đúng. 3) Chứng minh R* ⊆ R N ? Từ (3) và (1) suy ra (2) đúng. http://www.ebook.edu.vn
Bùi Thế Tâm III.2 Quy hoạch rời rạc Hệ quả 1. Giả sử X (R,C ) là phương án tựa tối ưu của bài toán (R,C ) , khi đó X (R,C ) cũng là phương án tối ưu của bài toán (LN ,C ) . Vì vậy để giải bài toán quy hoạch tuyến tính nguyên (LN ,C ) ta đi giải bài toán (R,C ) . 1.2. Ta sẽ chứng minh: R = V (LN ) là đa diện nguyên duy nhất mà tập các điểm nguyên của nó trùng với LN . Định lý 2. Giả sử L là một đa diện lồi, U là một đa diện lồi nguyên và U N = LN (8) Khi đó U = R = V (LN ) (9) Chứng minh. Từ (8) trực tiếp suy ra R ⊆U (10) ( vì R = V ( LN ) = V (U N ) ⊆ U ) Ta phải chứng minh: U ⊆R ? (11) Vì U là đa diện nguyên (tất cả các đỉnh của nó là nguyên) và (8) nên U * ⊆ U N = LN , suy ra U =V (U * ) ⊆ V (LN ) ≡ R . Vậy (11) là đúng.. Từ (10) và (11) ta có điều cần chứng minh (9). 1.3.Ví dụ http://www.ebook.edu.vn
Bùi Thế Tâm III.3 Quy hoạch rời rạc BÀI TOÁN (LN ,C ) BÀI TOÁN (L,C ) BÀI TOÁN R ≡ V (LN ,C ) Max x1 + x 2 Max( x1 + x 2 ) Max( x1 + x 2 ) 2x1 + 11x 2 ≤ 38 (a) x 2 ≤ 3 2x1 + 11x 2 ≤ 38 (b) x1 + x 2 ≤ 5 x1 + x 2 ≤ 7 x1 + x 2 ≤ 7 (c) x1 − x 2 ≤ 1 4x1 − 5x 2 ≤ 5 4x1 − 5x 2 ≤ 5 xj ≥ 0 xj ≥ 0 xj ≥ 0 x j nguyên Max=5. Max=7 Max=5 Tối ưu là 2 điểm Tối ưu là một đoạn Tối ưu là đoạn 13 8 40 23 (2,3); (3,2) [( ; ); ( ; )] [(2,3);(3,2) ] 33 99 1.4. Từ Hệ quả 1 chỉ ra khả năng xấp xỉ đúng bài toán (LN ,C ) bằng bài toán quy hoạch tuyến tính (R,C ) nhưng không cho phương pháp xác định bài toán R = V (LN ) . Do đó xuất hiện vấn đề: cho một đa diện lồi L , tìm bao lồi V (LN ) các điểm nguyên của nó ? Vấn đề này nói chung cũng khó như chính việc giải bài toán quy hoạch tuyến tính nguyên. 1.5. Khi xây dựng V (LN ) ta đã không sử dụng thông tin về hàm mục tiêu CX của bài toán quy hoạch tuyến tính nguyên. Vậy có nên tìm một bài toán quy hoạch tuyến tính (A,C ) theo bài toán (LN ,C ) sao cho thoả mãn 3 điều kiện: 1) CX (LN ,C ) = CX (A,C ) (các trị tối ưu trùng nhau) (12) http://www.ebook.edu.vn
Bùi Thế Tâm III.4 Quy hoạch rời rạc 2) AN = LN ( tập các điểm nguyên bằng nhau ) (11) 3) Tất cả các phương án tựa tối ưu của bài toán quy hoạch tuyến tính (A,C ) đều thoả mãn điều kiện nguyên: Ac ∩ A* ⊆ AN (14) (tong đó Ac là tập hợp các phương án tối ưu của bài toán (A,C); A* là tập hợp các đỉnh của đa diện lồi A) Nói chung, việc xây dựng đa diện lồi A thoả mãn (12) – (14) cũng rất phức tạp và chưa có thuật toán hữu hiệu. 1.6. Khái niệm lát cắt đúng Giả sử bài toán (LN ,C ) là bài toán quy hoạch nguyên nào đó và phương án tựa tối ưu của bài toán quy hoạch tuyến tính tương ứng X (L,C ) không thoả mãn điều kiện nguyên, tức là X (L,C ) ∉ LN . Khi đó bất đẳng thức: ∑ajx j ≤ β hay aX ≤ β (15) j gọi là lát cắt đúng nếu thoả mãn 2 điều kiện: - Điều kiện cắt: X (L,C ) không thoả mãn (15), tức là aX (L,C ) > β - Điều kiện đúng: nếu X là phương án của (LN ,C ) thì X thoả mãn (15) , tức là LN ⊂ { X aX ≤ β } . Nói cách khác, ràng buộc thêm không cắt đi một phương án nguyên nào của bài toán (LN ,C ) . http://www.ebook.edu.vn
Bùi Thế Tâm III.5 Quy hoạch rời rạc 1.7. Tư tưởng phương pháp cắt của Danzig 1. Việc giải (LN ,C ) là một quá trình gồm nhiều bước: a) Ở bước thứ r giải bài toán bài toán quy hoạch tuyến tính phụ (Lr ,C ) , r = 0, 1, … với L0 = L b) Tập các điểm nguyên của tất cả các đa diện lồi là như nhau L0N = L1N = …= Lr N = ............. Do đó, nếu phương án tối ưu X (Lr ,C ) của bài toán (Lr ,C ) thoả mãn điều kiện nguyên thì nó cũng là phương án tối ưu X (L0N ,C ) của bài toán xuất phát (L0N ,C ) và quá trình kết thúc. c) Nếu X (Lr ,C ) không thoả mãn điều kiện nguyên thì X (Lr ,C ) không phải là phương án của bài toán (Lr +1,C ) , tức là X (Lr ,C ) ∉ Lr +1 2. Chuyển từ bước r sang bước r + 1 , tức là chuyển từ bài toán (Lr ,C ) sang (Lr +1,C ) khi X (Lr ,C ) không nguyên được thực hiện nhờ một lát cắt đúng ar x ≤ βr . Việc bổ sung lát cắt này vào ràng buộc của bài toán (Lr ,C ) sẽ chuyển đa diện lồi Lr thành Lr +1 . Như vậy, phương pháp cắt có hai việc: xấp xỉ tuyến tính nhiều bước đối với bài toán (LN ,C ) , chuyển từ bước này sang bước khác nhờ một lát cắt đúng. Có ba vấn đề tồn tại cần giải quyết: xây dựng lát cắt đúng, đảm bảo tính hữu hạn của quá trình giải, số lượng lát cắt đúng không được tăng mãi. Thuật toán Gomory thứ nhất sẽ giải quyết được cả ba vấn đề này một cách hiệu quả. 2. THUẬT TOÁN GOMORY THỨ NHẤT Thuật toán Gomory lần đầu tiên thực hiện phương pháp cắt để giải bài toán quy hoạch tuyến tính nguyên mà đối với nó việc xây dựng lát cắt đúng được tiến hành một cách thuật toán, việc chứng minh tính hữu hạn của thuật toán cũng dễ dàng hơn. 2.1. Xét bài toán quy hoạch tuyến tính nguyên hoàn toàn http://www.ebook.edu.vn
Bùi Thế Tâm III.6 Quy hoạch rời rạc n Max x 0 = ∑ c j x j (16) j =1 n ∑ aij x j (i = 1,..., m ) = bi (17) j =1 xj ≥ 0 (j=1,...,n) (18) x j nguyên (j=1,...,n) (19) Giả sử X (L,C ) là phương án tựa tối ưu của bài toán (L,C ) , từ đó ta có thể biểu diễn các biến qua các biến phi cơ sở : ∑ x ij(−x j ) , (i = 0,..., n) xi = xi 0 + (20) j ∈N Giả sử x là một số thực, ký hiệu [ x ] là phần nguyên (số nguyên lớn nhất không vượt quá x), { x } = x − [ x ] là phần lẻ. Ví dụ [-1.3] = -2, {-1.3} = 0.7, {1.3} = 0.3. Định lý 3. Giả sử X(L,C) có xi 0 không nguyên với 1 ≤ i ≤ n và: ∑ (− { x ij })(−x j ) , (i = 1, 2,...., n ) 1) zi ≡ zi (X ) = − { x i 0 } + (21) j ∈N 2) X là phương án của bài toán (LN ,C ) Khi đó: a) zi nguyên (22) b) zi ≥ 0 . (23) Chứng minh. a) Chứng minh zi nguyên ? Từ (20) ta có: ∑ ([ x ij ] + { x ij })(−x j ) xi = [ xi 0 ] + { xi 0 } + j ∈N ∑ [ x ij ](−x j ) . Do giả thiết 2) ta có xi , x j Kết hợp với (21) suy ra zi = −x i + [ x i 0 ] + j ∈N nguyên, nên từ biểu thức trên suy ra zi nguyên. b) Chứng minh zi ≥ 0. Giả sử phản chứng zi < 0 , từ (21) ta có: ∑ (− { x ij })(−x j ) < 0 zi ≡ zi (x ) = − { x i 0 } + j ∈N Vì − { xi 0 } > -1 ; x j ≥ 0 và { x ij } ∈ [ 0,1 ) nên −1 < zi < 0 , tức là zi không nguyên. Điều này mâu thuẫn với chứng minh câu a), do đó zi ≥ 0 . Chú ý, nếu x 0 được đảm bảo tính nguyên (chẳng hạn mọi c j đều là nguyên) thì Định lý 3 cũng đúng với i = 0 . http://www.ebook.edu.vn
Bùi Thế Tâm III.7 Quy hoạch rời rạc Hệ quả 2. Giả sử X (L,C ) không thoả mãn điều kiện nguyên (19), như vậy đối với i nào đó (1 ≤ i ≤ n) xi 0 không nguyên . Khi đó các hệ thức (21) và (23) xác định một lát cắt đúng. Chứng minh. a) Mọi phương án của bài toán (LN ,C ) đều thoả mãn (21) và (23) (trong chứng minh định lý), do đó điều kiện đúng của lát cắt được thoả mãn. b) Đặt vào (21) phương án tối ưu không nguyên X (L,C ) . Do x j (L,C ) =0, j ∈ N , suy ra zi (X (L,C )) = − { x i 0 } + 0 < 0 , trái với (23), tức là điều kiện cắt thoả mãn. 2.2. Trong lược đồ phương pháp cắt ở trên, vì bài toán (Lr ,C ) có thể có nhiều lời giải nên X (Lr ,C ) không duy nhất. Gomory giải bài toán (Lr ,C ) thay cho bài toán (Lr ,C ) , do đó phương án l - tối ưu X (Lr ,C ) là tựa và xác định duy nhất, các tính toán trên tiến hành nhờ l - phương pháp. 2.3. Trong phương pháp cắt vấn đề quan trọng là việc tăng số lượng ràng buộc. Gomory đặt kích thước hạn chế cho bảng đơn hình mở rộng bằng số (n+2) x (k+1). Các ràng buộc ar X ≤ βr chỉ là phương pháp để cắt phương án tối ưu không nguyên X (Lr ,C ) và chuyển từ bài toán (Lr ,C ) sang bài toán (Lr +1,C ) . Chú ý rằng biến x n +r +1 ( r ≥ 0 ) lập tức đưa ra khỏi cơ sở sau khi đưa vào ràng buộc :  xn +r +1 = βr − ar X     xn +r +1 ≥ 0   Tư tưởng của Gomory như sau: - Ngay sau khi x n +r +1 đưa ra khỏi cơ sở dòng tương ứng xoá khỏi bảng đơn hình mở rộng. - Nếu trong qúa trình tính toán tiếp theo xn +r +1 lại đưa vào cơ sở thì dòng tương ứng trong bảng đơn hình không được khôi phục và xn +r +1 không tham gia vào các tính toán tiếp theo. Như vậy ở bước lặp bất kỳ của tính toán, bảng đơn hình bao gồm (k+1) cột như bảng đơn hình xuất phát, số lượng các dòng không vượt quá n+2. Suy ra cỡ của bảng không vượt quá (n+2) x (k+1). 2.4. Nếu bài toán (L,C ) không có lời giải vì hàm mục tiêu x 0 = CX không bị chặn trên khúc lồi L thì thuật toán Gomory thứ nhất không áp dụng được. Thuật toán Gomory cũng không áp dụng được trong trường hợp bài toán (L,C ) có lời giải nhưng l - bài toán (L,C ) không có lời giải. Điều đó dường như là tập hợp các phương án tối ưu của bài toán (L,C ) khác trống nhưng không bị chặn . http://www.ebook.edu.vn
Bùi Thế Tâm III.8 Quy hoạch rời rạc Về sau ta sẽ giả thiết : 1) x 0 ≡ CX bị chặn trên trên L (L,C ) khác trống 2) Nếu tập hợp các phương án tối ưu của thì nó phải bị chặn, tức là nếu bài toán (L,C ) giải được thì bài toán (L,C ) cũng giải được 2.5. Thuật toán Gomory thứ nhất Bước lặp ban đầu. Giải bài toán (L,C ) ≡ (L0,C ) nhờ l - phương pháp, nếu nó không giải được thì bài toán (LN ,C ) cũng không giải được . 0 Nếu bài toán (L0,C ) giải được và X (L0,C ) thoả mãn điều kiện nguyên thì X (L0,C ) là phương án tối ưu của bài toán nguyên ban đầu (LN ,C ) . Nếu không thoả 0 mãn điều kiện nguyên thì chuyển sang bước r = 0 . Bước lặp r ≥ 0 . Giả sử X (Lr ,C ) không thoả mãn điều kiện nguyên thì ta biểu diễn x 0 ≡ CX và x1, x 2,..., xn qua các biến phi cơ sở x j ( j ∈ N r ) . Ta có: ∑ x ij(−x j ) , i = 0,1,..., n r r x i = x io + . j ∈N r r Ta nhận được bảng đơn hình: Tr = x ij là chấp nhận được và l - chuẩn. i ∈Q n , j ∈N r 0 Chọn dòng đầu tiên ứng với thành phần không nguyên: r k = min { i i ∈ {1..n } , x io không nguyên } và xây dựng lát cắt đúng: ∑ ( − { x kj } )( −x j )  x n +r +1 = − { x r } + r   k0   j ∈Nr  x  n +r +1 ≥ 0 (24)    x n +r +1 nguyên     http://www.ebook.edu.vn
Bùi Thế Tâm III.9 Quy hoạch rời rạc Viết dòng thứ nhất của (24) vào cuối bảng đơn hình Tr . Ta được bảng đơn hình không chấp nhận được (chỉ với xn +r +1 ) và l - chuẩn. Dùng l -phương pháp đối với bảng này, đồng thời sau khi đưa khỏi cơ sở xn +r +1 thì dòng tương ứng n + r + 1 bị xoá, sau khi đưa vào cơ sở xl ( l ≥ r + 1 ) thì dòng tương ứng không được khôi phục. Nếu cuối cùng ta nhận được bảng đơn hình ứng với bài toán quy hoạch tuyến tính không giải được thì bài toán (L0N ,C ) cũng không giải được . Nếu ta nhận được bảng Tr +1 chấp nhận được và l - chuẩn thì kiểm tra tính nguyên của X (Lr +1,C ) . Nếu X (Lr +1,C ) thoả mãn điều kiện nguyên thì nó đồng thời là phương án tối ưu của bài toán (L0N ,C ) , nếu không thoả mãn thì chuyển sang bước r+1. 3. TÍNH HỮU HẠN CỦA THUẬT TOÁN GOMORY THỨ NHẤT Giả sử tập các phương án tối ưu của bài toán (L0,C ) là bị chặn. Định lý 4. Giả sử có các điều kiện sau: 1) Tính nguyên của hàm mục tiêu x 0 ≡ CX được đảm bảo và x 0 được xét khi chọn dòng xây dựng lát cắt đúng. 2) Một trong các khẳng định sau là đúng: i) Hàm mục tiêu x 0 bị chặn dưới trên L0 . ii) Bài toán (LN ,C ) có ít nhất một phương án X ' . 0 Khi đó thuật toán Gomory thứ nhất kết thúc sau một số hữu hạn bước lặp lớn. Trước khi chứng minh định lý ta cần chứng minh ba bổ đề. Giả sử r X (Lr ,C ) ≡ X r ≡ (x 0 , x1 ,..., x n ) . Kí hiệu X là giả phương án ứng với bảng Tr nhận rr r được từ bảng Tr sau khi loại khỏi cơ sở x n +r +1 và xoá dòng tương ứng . r Bổ đề 1. Ta có: X r > X ≥ X r +1 . Bất đẳng thức đầu tiên suy ra từ công thức biến đổi bảng đơn hình và tính l - chuẩn của bảng đơn hình (cột đầu tiên của Tr được tính theo công thức (− { xkr 0 }) R−r .Rlr , Rlr có số đầu tiên khác 0 là dương). Bất đẳng thức thứ hai là do cột (− { xkl }) 0 r 0 giảm khi dùng phương pháp đơn hình đối ngẫu từ vựng. Bổ đề 2. Các số xir (i = 0,1,..., n ) bị chặn dưới. Chứng minh. Với i = 1, ..., n điều đó suy ra từ điều kiện không âm x j ≥ 0 ( j = 1,..., n ) . Với i = 0 điều đó suy ra từ điều kiện 2) của định lý 4. Thật vậy, nếu i) là đúng thì bổ đề 2 là hiển nhiên đúng. Nếu điều kiện ii) được thoả mãn thì r X r ≥ X ' suy ra x 0 ≥ x 0 . ' Bổ đề 3. Nếu X r không thoả mãn điều kiện nguyên và x p ≡ x p 0 không nguyên r r thì: http://www.ebook.edu.vn
Bùi Thế Tâm III.10 Quy hoạch rời rạc (x 0 , x1 ,..., x p −1, [ x p ]) ≥ (x r ,..., x r ) . rr r r p 0 Chứng minh r Giả sử k = min { i i ∈ { 0,1,..., n }, x io không nguyên } , suy ra k ≤ p . Giả sử  Rr  j  Rlr = lex min  r j ∈ N r , { x kj } ≠ 0  r    { x kj } r { xkl }      (dòng quay là lát cắt mới thêm) và h(Rlr ) = min { i i ∈ { 0,1,...n } ; x il ≠ 0 } ( hàng đầu r tiên của cột Rl có hệ số ≠ 0 , cụ thể là xhl > 0 do Rlr > 0 ). r Vì { x kl } ≠ 0 ⇒ x kl ≠ 0 ⇒ h(Rlr ) ≤ k ≤ p . Có hai khả năng xảy ra: r r 1) h(Rlr ) ≡ q < p . 2) h(Rlr ) ≡ q = p . r r Trong trường hợp 1) theo quy tắc của l -phương pháp x q < xq vì r { xk 0 } r r r r r x q = xq − x < xq (do xql > 0) , và bổ đề được chứng minh. r { xkl } ql Trong trường hợp 2) ta có h(Rlr ) = k = p . Vì vậy x r0 = x ir0 với i < k = h(Rlr ) i r { xk 0 } r r (h là chỉ số đầu tiên xhl khác không) và x r 0 = xk 0 − r xkl . r k { x kl } r r r r Vì x kl = x hl > 0 , nên x kl ≥ { x kl } . Từ đó ta có : r r r x r 0 ≤ xk 0 − { xk 0 } = [ xk 0 ] . k Do k = p nên bổ đề được chứng minh. Chứng minh định lý 4 Giả sử dãy : X 0, X 1,..., X r ,... vô hạn (25) Khi đó theo Bổ đề 1 và Bổ đề 2 tồn tại i0 , 0 ≤ i0 ≤ n ; tồn tại r0 ≥ 0 và một dãy vô hạn : r1 < r2 < ... < rν < ...(r1 ≥ r0 ) (26) sao cho ta có : x ir +1 = x ir ; r ≥ r0 ; 0 ≤ i ≤ i0 − 1 (27) xir0ν +1 < xir0ν , (ν = 1,2,...) (28) Từ Bổ đề 1 và (27) ta có x ir0+1 ≤ x ir0 , r ≥ r0 (29) http://www.ebook.edu.vn
III.11 Bùi Thế Tâm Quy hoạch rời rạc Từ (28), (29) và bổ đề 2 suy ra tồn tại số r ' > r0 và các số nguyên z 0 và z 0 +1 sao cho: z 0 < xir0 < z 0 + 1 , (r ≥ r ' ) (30) Từ (27), (30) và Bổ đề 3 suy ra: x ir0+1 ≤ x i0 ≤ [ x ir0 ] = z 0 . Điều này là mâu thuẫn r với (30), định lý được chứng minh. 4. GIẢI VÍ DỤ SỐ Giải bài toán sau bằng thuật toán Gomory thứ nhất: Max x0 = x1 + 2 x2 − x3 2 x1 + x2 − x3 ≤8 x1 + 4 x2 + x3 ≤9 (31) − x1 − 2 x2 + 2 x3 ≤ 3 3 x1 − x2 − x3 ≤6 x1 ≥ 0 , x2 ≥ 0 , x3 ≥ 0 x1 , x2 , x3 nguyên. Sau khi thêm biến bù bài toán viết lại thành: Max x0 = x1 + 2 x2 − x3 x4 = 8 − 2 x1 − x2 + x3 x5 = 9 − x1 − 4 x2 − x3 (32) x6 = 3 + x1 + 2 x2 − 2 x3 x7 = 6 − 3x1 + x2 + x3 x1 , x2 , x3 , x4 , x5 , x6 , x7 ≥ 0 ; x1 , x2 , x3 , x4 x5 , x6 , x7 nguyên. Từ đây ta có bảng đơn hình xuất phát. Vì bảng đơn hình xuất phát không là l- chuẩn ta phải thêm ràng buộc phụ: x1 + x2 + x3 ≤ gz = 100 hay x8 = 100 − x1 − x2 − x3 ≥ 0 và x8 ≥ 0 và viết vào phía dưới bảng 1. Bảng đơn hình xuất phát sau khi thêm ràng buộc phụ: http://www.ebook.edu.vn
III.12 Bùi Thế Tâm Quy hoạch rời rạc 1 - x1 -x2 -x3 x0 0.00000 -1.00000 -2.00000 1.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 8.00000 2.00000 1.00000 -1.00000 x5 9.00000 1.00000 4.00000 1.00000 x6 3.00000 -1.00000 -2.00000 2.00000 x7 6.00000 3.00000 -1.00000 -1.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. 1 - x1 -x8 -x3 x0 200.00000 1.00000 2.00000 3.00000 x1 0.00000 -1.00000 - 0.00001 0.00000 x2 100.00000 1.00000 1.00000 1.00000 x3 0.00000 0.00000 -0.00001 -1.00000 x4 -92.00000 1.00000 -1.00000 -2.00000* x5 -391.00000 -3.00000 -4.00000 -3.00000 x6 203.00000 1.00000 2.00000 4.00000 x7 106.00000 4.00000 1.00000 0.00000 Bảng 2 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 phụ quy hoạch tuyến tính cho đến tối ưu ta được các bảng 3, bảng 4, bảng 5, bảng 6. 1 - x1 -x8 -x4 x0 62.00000 2.50000 0.50000 1.50000 x1 0.00000 -1.00000 - 0.00001 0.00000 x2 54.00000 1.50000 0.50000 0.50000 x3 46.00000 -0.50000 0.50000 -0.50000 x4 0.00000 0.00000 0.00000 -1.00000 x5 -253.00000 -4.50000 -2.50000* -1.50000 x6 19.00000 3.00000 0.00000 2.00000 x7 106.00000 4.00000 1.00000 0.00000 Bảng 3 http://www.ebook.edu.vn
III.13 Bùi Thế Tâm Quy hoạch rời rạc 1 - x1 -x5 -x4 x0 11.40000 1.60000 0.20000 1.20000 x1 0.00000 -1.00000 - 0.00001 0.00000 x2 3.40000 0.60000 0.20000 0.20000 x3 -4.60000 -1.40000* 0.20000 - 0.80000 x4 0.00000 -0.00001 0.00000 -1.00000 x5 0.00000 0.00000 -1.00000 0.00000 x6 19.00000 3.00000 0.00000 2.00000 x7 4.80000 2.20000 0.40000 -0.60000 Bảng 4 1 - x3 -x5 -x4 x0 6.14286 1.14286 0.42857 0.28571 x1 3.28571 -0.71429 -0.14286 0.57143 x2 1.42857 0.42857 0.28571 -0.14286 x3 0.00000 -1.00000 0.00000 0.00000 x4 0.00000 0.00000 0.00000 -1.00000 x5 0.00000 0.00000 -1.00000 0.00000 x6 9.14286 2.14286 0.42875 0.28571 x7 -2.42857 1.57143 0.71429 -1.85714* Bảng 5 Tám dòng đầu của bảng 6 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 lát cắt ở dòng x9 theo công thức (24) và ta được bảng 6. Chọn dòng x9 làm dòng quay 1 - x3 -x5 -x7 x0 5.76923 1.38462 0.53846 0.15385 x1 2.53846 -0.23077 0.07692 0.30769 x2 1.61538 0.30769 0.23077 -0.07692 x3 0.00000 -1.00000 0.00000 0.00000 x4 1.30769 -0.84615 -0.38462 -0.53846 x5 0.00000 0.00000 -1.00000 0.00000 x6 8.76923 2.38462 0.53846 0.15385 x7 0.00000 0.00000 0.00000 -1.00000 Bảng 6 x9 -0.76923 -0.38462 -0.53846 * -0.15385 http://www.ebook.edu.vn
III.14 Bùi Thế Tâm Quy hoạch rời rạc 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 đơ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 - x3 -x9 -x7 x0 5.00000 1.00000 1.00000 0.00000 x1 2.42857 -0.28571 0.14286 0.28571 x2 1.28571 0.14286 0.42857 -0.14286 x3 0.00000 -1.00000 0.00000 0.00000 x4 1.85714 -0.57143 -0.71429 -0.42857 x5 1.42857 0.71429 -1.85714 0.28571 x6 8.00000 2.00000 1.00000 0.00000 x7 0.00000 0.00000 0.00000 -1.00000 Bảng 7 x10 -0.42857 -0.71429 -0.14286 -0.28571 * 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 đơn hình l- chuẩn và chấp nhận được. Biến x2 lẻ nên từ dòng x2 sinh ra lát cắt ở dòng x11 . 1 - x3 -x9 -x10 x0 5.00000 1.00000 1.00000 0.00000 x1 2.00000 -1.00000 0.00000 1.00000 x2 1.50000 0.50000 0.50000 -0.50000 x3 0.00000 -1.00000 0.00000 0.00000 x4 2.50000 0.50000 -0.50000 -1.50000 x5 1.00000 0.00000 -2.00000 1.00000 x6 8.00000 2.00000 1.00000 0.00000 x7 1.50000 2.50000 0.50000 -3.50000 Bảng 8 x11 -0.50000 -0.50000 -0.50000 -0.50000* 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 đơ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. http://www.ebook.edu.vn
III.15 Bùi Thế Tâm Quy hoạch rời rạc 1 - x3 -x9 -x11 x0 5.00000 1.00000 1.00000 0.00000 x1 1.00000 -2.00000 -1.00000 2.00000 x2 2.00000 1.00000 1.00000 -1.00000 x3 0.00000 -1.00000 0.00000 0.00000 x4 4.00000 2.00000 1.00000 -3.00000 x5 0.00000 -1.00000 -3.00000 2.00000 x6 8.00000 2.00000 1.00000 0.00000 x7 5.00000 6.00000 4.00000 -7.00000 Bảng 9 Vậy phương án tối ưu là ( 1; 2; 0; 4; 0; 8; 5) với trị hàm mục tiêu x[0]=5 5. 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 x j ≥ 0 và nguyên , j = 1,2,..., m các b[i] có thể dương và âm, phương án xuất phát có thể không đối ngẫu chấp nhận m ∑ aij xi = bi thì ta thay thế bằng được. Nếu 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 . 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 http://www.ebook.edu.vn
III.16 Bùi Thế Tâm Quy hoạch rời rạc 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 } . - x0 =0 nếu có kể x0 nguyên và bằng 1 nếu x0 không cần nguyên. - ss = 1 nếu bảng đơn hình s ban đầu 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 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, 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 (31) thì tệp dữ liệu VDG1.sli, có dạng: http://www.ebook.edu.vn
III.17 Bùi Thế Tâm Quy hoạch rời rạc 7 3 100 0 3 0 -1 -2 1 0 -1 0 0 0 0 -1 0 0 0 0 -1 8 2 1 -1 9 1 4 1 3 -1 -2 2 6 3 -1 -1 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; int kgd,kgd2,blap,blap2,sb,cmin,x0,ss; int m,n,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); http://www.ebook.edu.vn
III.18 Bùi Thế Tâm Quy hoạch rời rạc f1= fopen(s1,"r"); fscanf(f1,"%d%d%lf%d%d",&n,&m,&gz,&x0,&ss); for (i=0;i
III.19 Bùi Thế Tâm Quy hoạch rời rạc { for (i=0; i s[i][j]) {cmin=j; break;} if (s[i][cmin] < s[i][j]) break; } } 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); 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; } lc=n+1; // 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
III.20 Bùi Thế Tâm Quy hoạch rời rạc printf("\nx[%2d] = %13.5lf",cs[i],s[i][0]); printf("\nSo luong lat cat: %d lat cat",blap-1); printf("\nSo bang don hinh da lap : %d bang",sb); if (tg==1){ for (i=0; i