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

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

Thêm vào BST

Báo xấu

199
lượt xem 53
download

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

THUẬT TOÁN NHÁNH CẬN 1. TƯ TƯỞNG CỦA THUẬT TOÁN NHÁNH CẬN 1.1. Trong các phương pháp giải bài toán qui hoạch nguyên, phương pháp nhánh cận là một trong các phương pháp có hiệu quả. Phương pháp nhánh cận được Land A.H và Doig A.G xây dựng năm 1960 giải bài toán qui hoạch nguyên (trình bày Tiết 2), đến 1963 được Little J.D, Murty K.G, Sweeney D.W và Karen C sử dụng thành công giải bài toán người du lịch (trình bày trong Tiết 3). ...

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 6

Bùi Thế Tâm VI.1 Quy hoạch rời rạc Chương 6 THUẬT TOÁN NHÁNH CẬN 1. TƯ TƯỞNG CỦA THUẬT TOÁN NHÁNH CẬN 1.1. Trong các phương pháp giải bài toán qui hoạch nguyên, phương pháp nhánh cận là một trong các phương pháp có hiệu quả. Phương pháp nhánh cận được Land A.H và Doig A.G xây dựng năm 1960 giải bài toán qui hoạch nguyên (trình bày Tiết 2), đến 1963 được Little J.D, Murty K.G, Sweeney D.W và Karen C sử dụng thành công giải bài toán người du lịch (trình bày trong Tiết 3). Năm 1979 Giáo sư Hoàng Tụy đã ứng dụng thành công phương pháp này vào giải bài toán qui hoạch lõm. Đây là thuật toán ứng dụng rộng rãi để giải các bài toán tối ưu khó. Xét bài toán qui hoạch rời rạc min Z = f ( X ) , (1) X ∈ G ( G là tập hữu hạn ) (2) 1.2. Tư tưởng của phương pháp nhánh cận gồm các phép xây dựng sau cho phép giảm bớt khối lượng lựa chọn. 1. Tính cận dưới. Tìm cận dưới của hàm mục tiêu f ( x ) trên tập các phương án G (hoặc trên tập con G′ nào đó của G ) tức là số ζ ( G ) hay ζ ( G′ ) sao cho: f ( x ) ≥ ζ ( G ) với ∀x ∈ G ( hay f ( x ) ≥ ζ ( G′ ) với ∀x ∈ G ′ ). 2. Chia thành các tập con (rẽ nhánh ). Chia dần dần tập phương án G thành cây các tập con (các nhánh). Việc chia nhánh thực hiện theo sơ đồ nhiều bước sau: Bước 0. Đặt G 0 ≡ G . Bằng một cách nào đó G 0 được chia thành một số hữu 11 1 hạn các tập con ( thường là không giao nhau) G1 , G2 ,...., Gr1 . k k k k Bước k ≥ 1 . Có tập G1 , G2 ,...., Grk cần chia nhánh. Ta chọn tập Gϑ ( k ) theo một k k k qui tắc nào đó và chia thành một số hữu hạn các tập con : Gϑ ( k ),1 , Gϑ ( k ),2 ,...., Gϑ ( k ),s ( k ) , gồm có s ( k ) tập. Khi đó, tập cần chia nhánh tiếp theo là k k k k k k k k G1 , G2 ,...., Gϑk −1 , Gϑk +1 ,..., Grk , Gϑ ( k ),1 , Gϑ ( k ),2 ,...., Gϑ ( k ),s( k ) Ta đánh số lại là G1 +1 , G2 +1 ,...., Grk+1 . k k k1 + 3. Tính lại đánh giá thì min f ( X ) ≥ min f ( X ) . Nếu tập G1 ⊂ G2 X ∈G1 X ∈G2 s sao cho G ' = ∪ Gi′ thì cận của bất ′ ′ ′ Vì vậy khi chia tập G ′ thành G1 , G2 ,...., Gs i =1 kì tập Gi′ đều có ζ ( Gi′ ) ≥ ζ ( G′ ) , ( i = 1,.., s ) . Trong các tình huống cụ thể ta thường nhận được các đánh giá tốt , tức là đối với một i nào đó ζ ( Gi′ ) ζ ( G′ ) . http://www.ebook.edu.vn
Bùi Thế Tâm VI.2 Quy hoạch rời rạc 4. Tính phương án Đối với các bài toán cụ thể có thể chỉ ra các phương pháp khác nhau để tìm ra các phương án trong các tập con được chia liên tiếp. Phương pháp này dựa trên đặc thù của mỗi bài toán cụ thể. Nhờ phương án mới tìm được ở mỗi bước ta có thể cải tiến cận trên (ban đầu gán cho cận trên giá trị là +∞ ) bằng cách gán cho cận trên giá trị hàm mục tiêu tốt nhất tại thời điểm đó. s 5. Tiêu chuẩn tối ưu. Giả sử G = ∪ Gi và phương án X ∈ Gϑ thỏa mãn điều i =1 () f X = ζ ( Gϑ ) ≤ ζ ( Gi ) , ∀ i = 1,.., s thì X là phương án tối ưu của bài toán kiện: (1)-(2). Qui tắc này được ứng dụng ở giai đoạn chia nhánh . 6. Đánh giá độ chính xác của lời giải xấp xỉ. Giả sử s ζ = min ζ ( Gi ) . G = ∪ Gi , i =1,.., s i =1 () Nếu X là một phương án của bài toán xuất phát thì ζ ≤ min f ( X ) ≤ f X . Nếu x∈G () f X − ζ đủ nhỏ thì X có thể lấy làm lời giải xấp xỉ với đánh giá độ xấp xỉ là ∆ = f ( X ) −ζ . 1.3. Lược đồ tổng quát của phương pháp nhánh cận. Chia tập phương án G thành cây tập con. () Bước 0. Tính ζ ( G ) = ζ G 0 . Nếu tìm được phương án X sao cho () f X = ζ ( G ) thì X là phương án tối ưu. Ngược lại, chia G 0 = G1 ∪ G2 ∪ .... ∪ G1 , 1 1 r1 tức là chia thành các tập con (thường là không giao nhau). () Bước k ≥ 1 . Tính các đánh giá ζ Gik , i = 1,.., rk . Nếu tìm được phương án X , f ( X ) = ζ ( G ) ≤ ζ ( G ) , với ∀i = 1, 2,.., r k k k X ∈ Gr sao cho , thì X là phương án k r i k tối ưu, quá trình kết thúc. Ngược lại, chọn để chia, theo tiêu chuẩn Gϑ ( k ) ( ) () ζ Gϑ ( k ) = min ζ Gik . Ta chia tập Gϑ ( k ) thành một số tập con k k i =1,..,r k k k k k Gϑ ( k ) = Gϑ ( k ),1 ∪ Gϑ ( k ),2 ∪ .... ∪ Gϑ ( k ),s( k ) . Tập cần chia tiếp theo là k k k k k k k k G1 , G2 ,...., Gϑk −1 , Gϑk +1 ,..., Grk , Gϑ ( k ),1, Gϑ ( k ),2 ,...., Gϑ ( k ),s k Sau đó ta đánh số lại là G1 +1 , G2 +1 ,...., Grk+1 và sang bước k+1. k k k1 + http://www.ebook.edu.vn
Bùi Thế Tâm VI.3 Quy hoạch rời rạc 2. PHƯƠNG PHÁP LAND VÀ DOIG GIẢI BÀI TOÁN QUI HOẠCH NGUYÊN 2.1. Xét bài toán qui hoạch nguyên tuyến tính sau: n min Z = f ( X ) = ∑ c j x j (3) j =1 với các điều kiện ràng buộc n ∑ aij x j Ribi , (quan hệ thứ tự Ri ∈ {≤, ≥, =} ) i = 1,.., m (4) j=1 0 ≤ xj ≤ d j, j = 1,.., n. (5) j = 1,.., n1 n1 ≤ n x j nguyên (6) trong đó d j là cận trên của biến x j (có thể d j = +∞ ). Giả thiết tập tất cả các điểm x thỏa mãn (4)-(5) là bị chặn. Nếu n1 = n , ta có bài toán qui hoạch nguyên hoàn toàn, còn nếu n1 < n thì có bài toán qui hoạch nguyên bộ phận. Ngoài ra, bài toán tìm max có thể qui về bài toán tìm min bằng cách đổi dấu hàm mục tiêu. Có nhiều phương pháp giải bài toán qui hoạch nguyên tuyến tính, trong đó có phương pháp nhánh cận. A.H Land và A.G Doig (1960) là những người đầu tiên áp dụng phương pháp nhánh cận để giải bài toán qui hoạch tuyến tính nguyên. 2.2. Nội dung phương pháp 1. Cho tập G 0 ≡ G xác định bởi (4) - (6). k 2. Cho các tập Gϑ ( k ) , ϑ = 1,.., rk , và k = 1, 2,.... . xác định bởi (4),(6) và ràng buộc bổ sung: k  k  hj   ≤ x j ≤ d j  , j = 1,.., n . (7) ϑ  ϑ  () 3. Tính cận. Đối với G 0 ước lượng ζ ( G0 ) = f X 0 với X 0 là lời giải của bài toán qui hoạch tuyến tính (3)-(5).  k  () k  k k Đối với Gϑ thì ζ Gϑ = f  X    , trong đó X   là lời giải của bài toán qui ϑ   ϑ   hoạch tuyến tính (3),(4) và (7). () () k k Nếu Gϑ = ∅ thì ζ Gϑ = +∞ . 4. Tính phương án. Nếu X 0 thỏa mãn điều kiện nguyên (6), thì X 0 là nghiệm tối ưu của bài toán ban đầu, thuật toán dừng. http://www.ebook.edu.vn
Bùi Thế Tâm VI.4 Quy hoạch rời rạc k  Nếu X   thỏa mãn điều kiện nguyên (6) thì nó là phương án tối ưu của bài toán ϑ  k  (3), (4), (7), (6) và nó cũng là một phương án của bài toán ban đầu. Lấy X   để cải ϑ  tiến cận trên. k  5. Chia nhánh. Cần chia nhánh khi X   không thỏa mãn điều kiện nguyên ϑ (k )  k   ,1 ≤ r ≤ n1 là một thành phần không nguyên của phương án này, (6). Giả sử xr  ϑ ( k )  k k k k khi đó tập hợp Gϑ ( k ) chia thành hai tập hợp Gϑ ( k ) = Gϑ ( k ),1 ∪ Gϑ ( k ),2 , trong đó     k   k k Gϑ ( k ),1 =  X | X ∈ Gϑ ( k ) , xr ≤  xr     ϑ ( k )           k   k k Gϑ ( k ),2 =  X | X ∈ Gϑ ( k ) , xr ≥  xr    + 1  ϑ ( k )       Chú ý rằng nếu tất cả c j trong (3) là nguyên với j ≤ n1 và c j = 0 khi j ≥ n1 thì ( ) có thể dùng đánh giá mạnh hơn ζ ′ (Gϑk ) =  f ( Xϑk ) , ở đây kí hiệu k cận dưới ζ Gϑ   ] f [ là số nguyên nhỏ nhất mà lớn hơn hay bằng f. 2.3. Giải ví dụ bằng số Xét bài toán qui hoạch nguyên tuyến tính sau: min -x1 -x2 (8) 2x1 + 11 x2 ≤ 38 x1 + x2 ≤ 7 (9) 4 x1 - 5x2 ≤ 5 x1, x2 ≥ 0 (10) x1, x2 nguyên (11)  4 5 Bước 0. Giải bài toán (8)-(10), tìm được nghiệm X 0 =  4 , 2  . Cận dưới  9 9 () () ζ ′ G 0 =  f X 0  = ]−7[ = −7 . Phương án X 0 không thỏa mãn điều kiện nguyên   (11). Chúng ta chia G 0 thành hai tập hợp G 0 = G1 ∪ G2 , trong đó 1 1 { } G1 = X | X ∈ G 0 , x1 ≤ 4 1 = { X | X ∈ G , x ≥ 5} G1 0 2 1 http://www.ebook.edu.vn
VI.5 Bùi Thế Tâm Quy hoạch rời rạc 1 Bước 1. Giải hai bài toán quy hoạch tuyến tính: cực tiểu (8) trên hai tập hợp G1  8 1 1 và G2 . Trong bài toán đầu tiên cực tiểu trên miền G1 đạt tại điểm  4, 2  , do đó 11   () ()  8 1 1 1 ζ ′ G1 =  −6  = −6 . Tập G2 là trống nên ς G2 = +∞ . 11   1 Chọn G1 để chia nhánh ta được: { } 1 1 2 G1,1 = X | X ∈ G1 , x2 ≤ 2 ≡ G1 = { X | X ∈ G , x ≥ 3} ≡ G 1 1 2 G1,2 1 2 2 1 2 G2 = G3 = ∅ Bước 2. Giải các bài toán qui hoạch tuyến tính: ()  2  3   3 2 2 ⇒ ζ ′ G1 =  −5  = −5 1) Tìm cực tiểu (8) trên G1 được X   =  3 , 2  1   4   4 ()  2  1   1 2 2 ⇒ ζ ′ G2 =  −5  = −5 2) Tìm cực tiểu (8) trên G2 được X   =  2 ,3   2  2   2 () 1 2 2 ζ ′ G3 = +∞ 3) G2 = G3 = ∅ , 2 Chọn G1 để chia nhánh : { } 2 2 3 G1,1 = X | X ∈ G1 , x1 ≤ 3 ≡ G1 = { X | X ∈ G , x ≥ 4} ≡ G 2 2 3 G1,2 1 1 2 2 3 2 3 2 3 2 3 Đánh số lại G1,1 ≡ G1 , G1,2 ≡ G2 , G2 = G3 , G3 ≡ G4 Bước 3. Giải các bài toán qui hoạch tuyến tính: ()  3 ⇒ ζ ′ G1 = ]−5[ = −5 1) Tìm cực tiểu (8) trên G1 được X   = ( 3, 2 ) 3 3 1  () 3 3 ⇒ ζ ′ G2 = +∞ 2) G2 = ∅ 3 3) Tìm cực tiểu (8) trên G3 được ()  3  2  1   1 3 ⇒ ζ ′ G3 =  −5  = −5 X   = X   =  2 ,3   3  2  2   2 () 3 2 3 ⇒ ζ ′ G4 = +∞ 4) G4 = G3 = ∅ http://www.ebook.edu.vn
VI.6 Bùi Thế Tâm Quy hoạch rời rạc  3 Phương án X = X   = ( 3, 2 ) thỏa mãn điều kịên nguyên (11). Đồng thời 1  { ( ) ( ) ( ) ( )} = min {−5, ∞, −5, ∞} ≤ f ( X ) = −5 . 3 3 3 3 ζ ′ = min ζ ′ G1 , ζ ′ G2 , ζ ′ G3 , ζ ′ G4 Vậy phương án tối ưu của bài toán ban đầu là X = ( 3, 2 ) . Ta có cây phân nhánh sau: G0 ζ ′ = −7 G1 ≡ G3 ≡ G4 2 3 1 G1 2 ζ ′ = +∞ ζ ′ = −6 1 2 1 2 3 G1,1 ≡ G1 G1,2 ≡ G2 ≡ G3 ζ ′ = −5 ζ ′ = −5 2 3 2 3 G1,1 ≡ G1 G1,2 = G2 = ∅ ζ ′ = −5 ζ ′ = +∞ 3. PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN NGƯỜI DU LỊCH 3.1. Phát biểu bài toán. Có n thành phố, đánh số từ 1 đến n . Xuất phát từ một trong n thành phố này, chẳng hạn thành phố 1, một người du lịch muốn tới thăm n -1 thành phố còn lại, mỗi thành phố đúng một lần, rồi trở về thành phố xuất phát. Cho biết cij là chi phí (hoặc là khoảng cách) đi từ thành phố i đến thành phố j . Giả thiết cij > 0, ∀i ≠ j , cii = ∞ , với mọi i ( có thể cij ≠ c ji ). Hãy tìm hành trình với tổng chi phí nhỏ nhất? Ký hiệu ma trận C = cij , xij = 1 hoặc 0 tùy thuộc người du lịch có đi từ i , j =1,....,n thành phố i tới thành j hay không. Khi đó bài toán người du lịch có thể viết dưới dạng: http://www.ebook.edu.vn
VI.7 Bùi Thế Tâm Quy hoạch rời rạc n n min ∑∑ cij xij (12) i =1 j =1 n ∑x = 1, i = 1, 2,..., n (13) ij j =1 m ∑x = 1, j = 1, 2,..., n (14) ij i =1 xij ∈ {0;1} , i, j = 1, 2,..., n (15) ui − u j + nxij ≤ n − 1, 2 ≤ i ≠ j ≤ n (16) trong đó ui nhận giá trị nguyên hay thực. 3.2. Thuật toán nhánh cận Tập tất cả các phương án của bài toán (tập S0 )sẽ được chia nhỏ dần thành nhiều tập con rời nhau, mỗi tập con bao gồm những phương án đi qua và không đi qua một số cặp thành phố nhất định sẽ được ấn định dần trong quá trình giải bài toán. Mỗi tập con này được gắn với một số thực không âm (cách tìm số này xem ở phần tiếp theo), biểu thị cận dưới của chi phí đối với mọi phương án thuộc tập này. Tập con S k có cận dưới nhỏ nhất sẽ có nhiều khả năng chứa phương án tối ưu, vì thế tập S k sẽ được chọn để chia nhỏ tiếp (phân nhánh). Khi phân nhánh S k = Sk1 ∪ Sk 2 sao cho một tập S k 2 bắt buộc đi qua thêm một cặp thành phố xrs nào đó (cách chọn xem ở phần tiếp theo), một tập S k1 không được đi qua cặp thành phố xrs . Khi một tập con nào đó chỉ gồm một phương án duy nhất thì ta sẽ tính được chi phí C của phương án này và nhờ đó có thể cải tiến được phương án tốt nhất hiện biết, giá trị hàm mục tiêu của bài toán ứng với phương án tốt nhất hiện biết gọi là giá trị kỷ lục. Tập con nào có cận dưới lớn hơn hay bằng giá trị kỷ lục sẽ bị loại (không cần xem xét tiếp nữa), vì chắc chắn tập này không chứa phương án nào tốt hơn phương án tốt nhất hiện biết. Quá trình giải kết thúc khi không còn tập con nào cần xem xét tiếp. Khi đó, phương án tốt nhất hiện biết sẽ là phương án tối ưu của bài toán. Tính hữu hạn của thuật toán được suy ra từ tính hữu hạn của tập S0 . Thủ tục tính cận Bổ đề. Phương án tối ưu x * vẫn còn là tối ưu nếu ma trận chi phí C được thay bởi ma trận C ′ với ′ cij = cij − α i − β j , (i, j = 1, 2,.., n) (17) trong đó α i , β j là các số thực bất kỳ. Chứng minh. Xét một phương án bất kỳ x của bài toán. Do x * là phương án tối ưu nên n n n n ∑∑ cij xij ≤∑∑ cij xij * i =1 j =1 i =1 j =1 Từ các hệ thức (12) và (17) ta có: http://www.ebook.edu.vn
Bùi Thế Tâm VI.8 Quy hoạch rời rạc n n n n n n n n ∑∑ cij xij =∑∑ ( cij − αi − β j ) xij = ∑∑ cij xij − ∑ α i − ∑ β j ′* * * i =1 j =1 i =1 j =1 i =1 j =1 i =1 j =1 n n n n n n ∑∑ cij xij − ∑ αi − ∑ β j = ∑∑ cij xij ′ ≤ i =1 j =1 i =1 i =1 i =1 j =1 điều này chứng tỏ x * vẫn còn là phương án tối ưu. Các số α i , β j cần được chọn sao cho ci′j ≥ 0, ∀i, j và trên mỗi hàng, mỗi cột của ma trận C ′ có ít nhất một số 0. Chẳng hạn có thể chọn α i là số nhỏ nhất trong hàng i của C và β j là số nhỏ nhất trong cột j của ma trận thu được từ C bằng cách trừ các phần tử trên hàng i cho α i , trừ các phần tử trên cột j cho β j . Phép toán (17) được gọi là phép rút gọn ma trận hay thủ tục rút gọn và hằng số n n γ = ∑ α i + ∑ β j được gọi là hằng số rút gọn và đó chính là một cận dưới cho giá trị i =1 i =1 hàm mục tiêu của bài toán, vì mỗi phương án của người du lịch sẽ chứa đúng một phần tử của mỗi hàng và đúng một phần tử của mỗi cột trong ma trận chi phí . Tương tự, nếu tập con các phương án, ký hiệu là S p thu được từ tập ban đầu S0 bằng cách cố định một số biến xij ở giá trị 1 hay 0 (nghĩa là cho phép đi qua hay cấm không được đi qua một số cặp thành phố nào đó) thì để tính cận dưới cho S p ta chỉ việc tiến hành thủ tục rút gọn trên ma trận tương ứng với S p . Thủ tục phân nhánh Giả sử ta cần phân nhánh tập S p ⊂ S0 . Cách hay dùng là phân chia tập này thành hai tập con rời nhau S ′ , S ′′ với pp { } S ′ = x | x ∈ S p , xrs = 0 , p . S ′′ = { x | x ∈ S p , xrs = 1} p trong đó, xrs là biến chưa cố định ở giá trị 0 hay 1 trong tập S p . Cặp ( r , s ) dùng để phân nhánh được chọn sao cho tập S ′′ có nhiều khả năng p chứa phương án tối ưu, còn tập S ′ thì không. Nói cách khác, ( r , s ) được chọn sao cho p hiệu số các cận dưới của S ′′ và S ′ là lớn nhất có thể được. p p Để giải quyết vấn đề này, ta chỉ cần xét tập các phương án ban đầu S0 , vì mọi bài toán con nhận được về sau có cùng cấu trúc như đối với bài toán ban đầu. Giả sử ma trận chi phí C đã được rút gọn , nghĩa là cij ≥ 0, ∀i, j và trên mỗi hàng , mỗi cột của C có ít nhất một số 0. Tập S0 được chia thành hai tập rời nhau S1 và S 2 với http://www.ebook.edu.vn
Bùi Thế Tâm VI.9 Quy hoạch rời rạc S1 = { x | x ∈ S0 , xrs = 0} , S 2 = { x | x ∈ S0 , xrs = 1} Trong tập S 2 cấu trúc bài toán không thay đổi, trừ ra hàng r và cột s bị loại, bởi vì đã đi từ r đến s thì không thể đi từ r đến bất cứ nơi nào khác, và cũng không được phép đi từ bất cứ đâu vào s . Các hàng và cột còn lại chỉ chứa các phần tử không âm, vì thế ứng với S 2 một cận dưới đối với giá trị hàm mục tiêu tăng thêm là γ ( S 2 ) = crs . Trong tập S1 do cố định xrs = 0 nên từ các điều kiện (14), (15) suy ra phải có một xrj = 1( j ≠ s ) và một xis = 1( i ≠ r ) . Vì thế γ ( S1 ) = min crj + min cis là một cận dưới j≠s i≠r đối với giá trị mục tiêu tăng thêm. Ta sẽ chọn biến xrs sao cho hiệu giữa các cận dưới này là lớn nhất, nghĩa là đạt max {γ ( S1 ) − γ ( S2 )} (18) ( r ,s ) Nếu crs > 0 thì γ ( S1 ) = 0 (do trên hàng r và cột s của C đều chứa số 0), còn γ ( S2 ) = crs > 0 , từ đó γ ( S1 ) − γ ( S 2 ) < 0 . Vì thế để có (18) ta chỉ cần xét các cặp ( r, s ) với crs = 0. Trong trường hợp này γ ( S 2 ) = 0 và γ ( S1 ) ≥ 0 . Điều này có nghĩa là thay cho (18) ta có thể chọn biến xrs để phân nhánh theo qui tắc   θ ( r , s ) = max θ ( p, q ) = min c pj + min ciq  . c pq =0   j≠q i≠ p Lập luận trên đây cũng đúng cả khi các tập phương án Si về sau được chia thành các tập Sr , Sr +1 , nhưng thay cho mức tăng của các cận dưới γ ( S2 ) và γ ( S1 ) ta xét mức tăng của các cận dưới γ ( S r ) và γ ( Sr +1 ) tương ứng. Ngăn cấm tạo các chu trình con Nếu tập được xét không phải là S0 mà là { } S p = x | x ∈ S0 , xi1 j1 = δ1, xi2 j2 = δ 2 ,....., xik jk = δ k , thì qui tắc chọn biến để phân nhánh về cơ bản vẫn như trước, tuy nhiên cần tiến hành một số thay đổi . Trước hết, đó là việc thực hiện các lựa chọn bắt buộc. Chẳng hạn, nếu xuj = 0, j = 1,.., v − 1, v + 1,.., n thì tất nhiên phải có xuv = 1 . Cũng làm vậy đối với các cột . Một số loại lựa chọn bắt buộc khác: khi đã cố định xrs = 1 thì phải có xsr = 0 bằng cách đặt csr = ∞ . Hơn nữa, nếu đường đi dài nhất trong S p chứa cạnh ( r , s ) gồm ít nhất 2 và nhiều nhất n − 2 cạnh xi1i2 = ... = xiu r = xrs = xsiu +1 = ... = xiv −1iv = 1 (1 ≤ v ≤ n − 3) http://www.ebook.edu.vn
VI.10 Bùi Thế Tâm Quy hoạch rời rạc (không có cạnh nào có dạng xki1 = 1 hay xiv j = 1 ), thì để ngăn cấm tạo chu trình con dạng ( i1, i2 ,...., iu , r , s, i1 ) ta đặt csi1 = ∞ , còn để ngăn cấm tạo chu trình con dạng ( r , s, iu +1, iu + 2 ,...., iv , r ) ta đặt civ r = ∞ . Hơn nữa, ta cần có xivi1 = 0 bằng cách đặt civi1 = ∞ . r s i2 i3 i4 i1 Để tìm i1 ta có thể đi ngược từ r và để tìm iv ta có thể đi xuôi từ s theo danh sách các biến đã cố định ở giá trị 1 trong tập S p . Ở mỗi bước lặp, trước khi tính các cận dưới cho các tập mới, cần thực hiện những lựa chọn bắt buộc nêu trên. Có như vậy mới thu được những cận dưới chính xác và tránh được những phân nhánh vô ích. 3.3. Giải ví dụ bằng số Giải bài toán người du lịch với ma trận chi phí ( không đối xứng ) như sau(n=6) 1 2 3 4 5 6 ∞ 1 3 93 13 33 9 4∞ 2 77 42 21 16 ∞ 36 16 28 3 47 17 (19) 39 90 80 ∞ 56 7 4 28 46 88 33 ∞ 25 5 3 88 18 46 92 ∞ 6 Bước lặp 0. Tập đầu tiên S0 là tập hợp tất cả các hành trình có thể. Vì ban đầu chưa biết một phương án nào nên cận trên β = +∞ . Tính cận dưới cho S0 . Từ ma trận (19) trừ mỗi phần tử của các hàng 1, 2, 3, 4, 5, 6 cho số nhỏ nhất trên hàng tương ứng là 3, 4, 16, 7, 25, 3 ta được một ma trận mới. Tiếp theo, trừ mỗi phần tử của các cột 3, 4 của ma trận mới cho số nhỏ nhất trên cột tương ứng là 15, 8 ta được ma trận rút gọn (20) (chưa kể các số mũ ở trên các phần tử bằng 0). http://www.ebook.edu.vn
Bùi Thế Tâm VI.11 Quy hoạch rời rạc 1 2 3 4 5 6 03 ∞ 75 2 30 6 1 12 ∞ 20 58 30 17 12 ∞ 12 018 3 31 1 12 (20) 4 32 49 032 ∞ 83 58 5 48 02 00 ∞ 3 21 6 00 85 048 ∞ 35 89 Tổng các hằng số rút gọn là 3 + 4 + 16 + 7 + 25 + 3 + 15 + 8 = 81. Vì vậy, cận dưới cho tất cả các hành trình thuộc tập S0 là 81. Điều này có nghĩa là không thể tìm được hành trình có tổng chi phí nhỏ hơn 81. Bước lặp 1. Vì các tập cần xét chỉ có S0 nên ta chọn S0 để phân nhánh. Chọn cung để phân nhánh. Với mỗi số 0 trong ma trận (20) ta tính số θ ( p, q ) = min c pj + min ciq và ghi ở phía trên bên phải của số 0, chẳng hạn j ≠q i≠ p θ ( 2,1) = 12, θ ( 6,3) = 48,.... Ta thấy số 0 ở ô (6,3) có số mũ lớn nhất, nghĩa là θ ( 6,3) = max θ ( p, q ) . Vì thế ta chọn cặp (6,3) để phân nhánh. Khi đó, tập tất cả các c pq =0 hành trình được phân thành hai tập con: tập S1 gồm các hành trình chứa cạnh (6,3), tập S2 gồm các hành trình không chứa cạnh (6,3). Tính cận cho tập S 2 không chứa cạnh (6,3). Vì cạnh (6,3) không có mặt trong hành trình, nên ta có thể cấm việc đi theo cạnh này bằng cách đặt c63 = ∞ ở ma trận (20), tiếp theo trừ cột thứ 3 cho 48. Kết quả ta nhận được cận dưới cho tập S 2 là: ζ ( S 2 ) = 81 + 48 = 129 và ma trận tương ứng với tập này là 1 2 3 4 5 6 ∞ 1 0 27 2 30 6 0 ∞ 10 30 17 12 2 31 1 ∞ 12 0 12 3 32 83 10 ∞ 49 0 4 00∞ 5 3 21 0 ∞ 35 89 ∞ 6 0 85 Tính cận cho tập S1 chứa cạnh (6,3). Ta phải loại hàng 6 cột 3 khỏi ma trận (20), bởi vì đã đi theo cạnh (6,3) thì không thể đi từ 6 tới bất cứ nơi nào khác và cũng không được phép đi từ đâu vào 3. Hơn nữa, đã đi theo cạnh (6,3) thì không được đi từ 3 đến 6 nữa, vì vậy ta cần cấm cạnh (3,6) bằng cách đặt c36 = ∞ . Từ ma trận (20) ta thu được ma trận tương ứng với tập S1 (chưa kể các số mũ trên các số 0) http://www.ebook.edu.vn
Bùi Thế Tâm VI.12 Quy hoạch rời rạc 1 2 4 5 6 1∞ 2 30 6 03 ∞ 30 17 12 2 015 (21) ∞ 3 31 1 12 018 ∞ 49 032 4 32 83 ∞ 00 3 21 5 02 Cận dưới ζ ( S1 ) = 81. Bước lặp 2. Các tập cần xét tiếp là S1 và S2 với cận dưới tương ứng là 81 và 129. Tập S1 có cận dưới nhỏ nhất sẽ được chọn để phân nhánh tiếp. Chọn cung để phân nhánh. Với mỗi số 0 trong ma trận (21) ta tính số θ ( p, q) . Ta thấy θ (4, 6) = 32 có giá trị lớn nhất nên cạnh (4, 6) sẽ được chọn để phân nhánh tiếp. Tập S1 sẽ được phân thành hai tập: tập S3 gồm các hành trình đi qua cạnh (6,3) và cạnh (4,6), tập S 4 gồm các hành trình đi qua cạnh (6,3) và không đi qua cạnh (4,6). Tính cận dưới của tập S4 . Từ ma trận (21) sau khi thay 0 ở vị trí (4,6) bởi ∞ , rút gọn đi 32 đối với hàng 4 ta được ma trận ứng với tập S 4 1 2 4 5 6 ∞0 1 2 30 6 ∞ 30 17 12 2 0 ∞ 3 31 1 12 0 ∞ 17 ∞ 4 0 51 ∞0 5 3 21 0 Cận dưới của tập S 4 là ζ ( S 4 ) = ζ ( S1 ) + 32 = 81 + 32 = 113. Tính cận dưới của tập S3 . Từ ma trận (21) loại bỏ hàng ứng với đỉnh 4 và cột ứng với đỉnh 6. Các cạnh (6,3) và (4,6) đã nằm trong hành trình, cho nên cạnh (3,4) không thể đi qua nữa (nếu không sẽ tạo thành chu trình con). Để ngăn ngừa việc tạo ra chu trình con , ta gán cho phần tử ở vị trí (3,4) giá trị c34 = ∞ và được ma trận (không kể số mũ trên các số 0): 1 2 4 5 03 ∞ 1 2 30 020 ∞ 2 30 17 (22) 18 ∞ 3 31 1 0 05 ∞ 5 3 21 Cận dưới của tập S3 vẫn là 81. http://www.ebook.edu.vn
Bùi Thế Tâm VI.13 Quy hoạch rời rạc Bước lặp 3. Các tập cần xét là S2 , S3 , S4 với cận dưới tương ứng là 129, 81, 113. Tập S3 có cận dưới nhỏ nhất sẽ được chọn để chia nhánh. Chọn cung để phân nhánh. Với mỗi số 0 trong ma trận (22) ta tính số θ ( p, q ) . Cạnh (2,1) sẽ được chọn để phân nhánh. Tập S3 được chia thành hai tập: - Tập S5 gồm các hành trình đi qua cung (6,3), (4,6), (2,1) - Tập S6 gồm các hành trình đi qua cung (6,3), (4,6) và không đi qua cung (2,1). Tính cận dưới cho tập S6 . Từ ma trân (22) thay 0 ở hàng 2 cột 1 bằng ∞ , trừ hàng 2 cho 17, trừ cột 1 cho 3 ta được cận dưới của S6 là 81 + 17 + 3 = 101 và ma trận tương ứng (chưa có số mũ trên các phần tử 0): 1 2 4 5 03 ∞ 2 30 1 13 013 ∞ ∞ 2 (23) 3 28 01 ∞ 1 5 28 02 ∞ 0 21 Tính cận dưới cho tập S5 . Từ ma trận (22) xoá hàng 2 cột 1, cấm cung (1,2) bằng cách cho c12 = ∞ được ma trận 3 x 3. Từ ma trận này trừ hàng 1 cho 2, trừ cột 1 cho 1 ta được cận dưới của S5 là 81 + 2 + 1 = 84 và ma trận tương ứng (chưa kể các số mũ trên các số 0): 2 4 5 ∞ 028 28 1 3 020 ∞ 028 (24) 5 20 020 ∞ Bước lặp 4. Các tập cần xét là S2 , S4 , S5 , S6 với cận dưới tương ứng là 129, 113, 84, 101. Tập S5 có cận dưới nhỏ nhất sẽ được chọn để chia nhánh. Chọn cung để phân nhánh. Với mỗi số 0 trong ma trận (24) ta tính số θ ( p, q ) . Cạnh (1,4) sẽ được chọn để phân nhánh. Tập S5 được chia thành hai tập: - Tập S7 gồm các hành trình đi qua cung (6,3), (4,6), (2,1), (1,4) - Tập S8 gồm các hành trình đi qua cung (6,3), (4,6), (2,1) và không đi qua cung (1,4). Tính cận dưới cho tập S7 . Từ ma trận (24) xoá dòng ứng với đỉnh 1 và cột ứng với đỉnh 4 được ma trận 2 x 2, trong ma trận này ta phải cấm cung (3,2) để không tạo thành chu trình bằng cách đặt c32 = ∞ vì ta đã chọn các cung đi qua các đỉnh 2, 1, 4, 6, http://www.ebook.edu.vn
Bùi Thế Tâm VI.14 Quy hoạch rời rạc 3. Từ ma trận này ta trừ cột 1 đi số 20 ta được cận dưới của tập S7 là 84 + 20 = 104 và ma trận tương ứng là 25 3∞ 0 50∞ Chọn hai cung cuối cùng (3,5) và (5,2) ta được một hành trình của người du lịch là (1,4), (4,6), (6,3), (3,5), (5,2), (2,1) (phương án tốt nhất hiện biết) với giá trị hàm mục tiêu là 13 + 7 + 18 + 16 + 46 + 4 = 104. Do đó cận trên được thay bởi β = 104 . Tính cận dưới cho tập S8 . Từ ma trận (24) thay 0 ở dòng thứ nhất và cột thứ 2 bằng + ∞ và trừ dòng thứ nhất cho 28 ta được cận dưới của tập S8 là 84 + 28 = 112. Loại các tập. Vì các cận dưới ζ ( S7 ) = 104 = β , ζ ( S8 ) = 112 β , ζ ( S 4 ) = 113 β , ζ ( S 2 ) = 129 β nên các tập S7 , S8 , S 4 , S 2 có thể loại khỏi việc xét về sau, ta chỉ cần xét tập S6 . Bước lặp 5. Các tập cần xét chỉ còn S6 . Chọn cung để phân nhánh. Với mỗi số 0 trong ma trận (23) ta tính số θ ( p, q) . Cạnh (5,1) sẽ được chọn để phân nhánh. Tập S6 được chia thành hai tập: - Tập S9 gồm các hành trình đi qua cung (6,3), (4,6), (5,1) và không đi qua cung (2,1) - Tập S10 gồm các hành trình đi qua cung (6,3), (4,6) và không đi qua cung (2,1), (5,1). Tính cận dưới cho tập S10 . Từ ma trận (23) thay số 0 ở hàng ứng với đỉnh 5 và cột ứng với đỉnh 1 bởi ∞ , trừ cột 1 đi số 28 ta được cận dưới của tập S10 là 101 + 28 = 129. Cận dưới này lớn hơn cận trên 104 nên tập S10 bị loại không cần xét về sau. Tính cận dưới cho tập S9 . Từ ma trận (23) xoá hàng ứng với đỉnh 5 và cột ứng với đỉnh 1, cấm cung (1,5) bằng cách đặt c15 = ∞ , cột thứ 2 trừ đi số 2 ta được cận dưới ζ ( S9 ) = 101 + 2 = 103 và ma trận tương ứng (chưa kể số mũ trên các số phần tử 0) 2 4 5 1 11 ∞ 10 0 (25) 2 ∞ 11 011 3 1 ∞ 01 Bước lặp 6. Các tập cần xét chỉ còn S9 . Chọn cung để phân nhánh. Với mỗi số 0 trong ma trận (25) ta tính số θ ( p, q ) . Cạnh (1,4) sẽ được chọn để phân nhánh. Tập S9 được chia thành hai tập: http://www.ebook.edu.vn
Bùi Thế Tâm VI.15 Quy hoạch rời rạc - Tập S11 gồm các hành trình đi qua cung (6,3), (4,6), (5,1), (1,4) và không đi qua cung (2,1) - Tập S12 gồm các hành trình đi qua cung (6,3), (4,6), (5,1) và không đi qua cung (2,1), (1,4). Tính cận dưới cho tập S11 . Từ ma trận (25) xoá hàng ứng với đỉnh 1 và cột ứng với đỉnh 4, trừ cột thứ nhất cho 1 ta được ma trận cỡ 2 x 2 và ζ ( S11 ) = 103 + 1 = 104 . Tập S11 có cận dưới bằng cận trên nên bị loại. Tính cận dưới cho tập S12 . Từ ma trận (25) thay số 0 ở dòng thứ 1 cột thứ 2 bằng ∞ và trừ cột thứ 2 đi 11 ta được cận dưới của S12 là 103 + 11 = 114. Tập S12 có cận dưới bằng cận trên nên bị loại. Đến đây các tập cần xét là trống nên phương án tìm được ở Bước lặp 4 là hành trình tối ưu. Quá trình phân nhánh cho trong hình dưới. S0 , 81 S1 , (6,3), 81 S 2 , (6,3) , 129 S3 , (4,6), 81 S 4 , (4, 6) , 113 S5 , (2,1), 84 S6 , (2,1) , 101 S7 , (1,4), 104 S8 , (1, 4) , 112 S9 , (5,1), 103 S10 , (5,1) , 129 S11 , (1,4), 104 S12 , (1, 4) , 114 http://www.ebook.edu.vn
Bùi Thế Tâm VI.16 Quy hoạch rời rạc BÀI TẬP Bài 1. Tìm phương án tối ưu cho bài toán người du lịch với ma trận chi phí 1 2345 6 ∞ 1 27 43 16 30 26 ∞ 16 1 2 7 30 25 20 13 ∞ 35 5 3 0 21 16 25 ∞ 18 4 18 12 46 27 48 ∞ 5 5 ∞ 6 23 5 5 9 5 Đáp số: hành trình tối ưu là 1 – 4 – 3 – 5 – 6 – 2 – 1, trị tối ưu là 63 Bài 2. Tìm phương án tối ưu cho bài toán người du lịch với ma trận chi phí 1 2345 6 ∞ 31 15 23 10 1 17 16 ∞ 24 7 12 2 12 ∞ 3 34 3 25 54 25 ∞ 50 4 15 20 33 40 ∞ 5 16 10 32 3 23 6 18 20 13 28 21 ∞ Đáp số: hành trình tối ưu là 1 – 6 – 3 – 2 – 5 – 4 – 1, trị tối ưu là 63 http://www.ebook.edu.vn