Bài giảng Quy hoạch rời rạc

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 0ij ,ni Q j NT x ∈ ∈= nguyên, không chấp nhận được, l - chuẩn và giả sử đối với k (1 ≤ k ≤ n): 0 0 0, ( ) k k k kj j j N x x x x x ∈ < = + −∑ Đặt: T = N 0 0 0 0 j N j N ( ) ( ) ax ax j kj k j j j kj d x j N y x y x j N m d m xλ ∈ ∈ = ∈ = = ∈ = = Như vậy: 0 , 0 1 , 0 jj j dd dλ ≥  =   − <   , và ta nhận được lát cắt đúng nguyên : 0 ( ; ) 1 ( 1)( ) 0 ên kj k j j N x z z X x z z nguy λ ∈<  = = − + − − ≥ − ∑ 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 : 0 1 n ij j=1 ax (13) a , 1, 2,..., (14) 0 , 1, 2,..., (15) ên , 1,2,..., (16) n j j j j i j j m x c x x b i m x j n x nguy j n = ≡ ≤ = ≥ = − = ∑ ∑ trong đó cj , aij , bi nguyên ( )1,..., ; 1,...,i m j n= = . Đưa vào các biến mới, bài toán trên được viết lại như sau : Bùi Thế Tâm V.5 Quy hoạch rời rạc 0 1 n ij j=1 ax ( )( ) a ( ), 1,2,...., 0, 1, 2,..., , 1,..., ên , 1, 2,..., , 1,..., n j j j n i i j j j m x c x x b x i m x j n n n m x nguy j n n n m = + ≡ − − = + − = ≥ = + + − = + + ∑ ∑ Ta có các biến x1 , ... , xn là biến phi cơ sở , viết bảng '0T (chưa l - chuẩn). 1 -x1 -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 '0T ) a) Nếu bảng '0T là l - chuẩn (ví dụ khi cj < 0 , 1,...,j n= ) thì xem nó là bảng xuất phát T0 (lấy '0T làm T0 xuất phát). b) Nếu '0T không là l - chuẩn, nhưng tập các phương án của bài toán (13)-(15) là 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 n j j=1 x∑ với ràng buộc (14)-(15) và tìm được: n j j=1 ax x 'm M=∑ Rõ ràng, với mọi phương án của bài toán (13) - (16) ta đều có : [ ]n j j=1 x 'M M≤ ≡∑ Vì vậy, từ bài toán này ta có thể đưa vào biến mới : Bùi Thế Tâm V.6 Quy hoạch rời rạc n 1 j j=1 1 1 1.(-x ) (17) 0 (18) ên (19) n m n m n m x M x x nguy + + + + + + = + ≥ − ∑ Viết dòng (17) xuống dưới bảng '0T và chọn nó làm dòng quay. Cột quay chọn theo tiêu chuẩn: { } ' ' 1,..., ex minl j j n R l R ∈ = ( 'jR - là cột của ' 0T ứng với biến phi cơ sở ( 1,..., )jx j 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 '0T ) 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 000 ij ,ni Q j NT x ∈ ∈= - nguyên , l - chuẩn. Nếu T0 là chấp nhận được thì l - giả phương án mở rộng : ( ) ( )0 0 0 0 0 0 00 1 00 10 0, ,..., , ,...,n nX x x x x x x= = 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 0 1 P-1 1 ij ,n P P i Q j N T x −− ∈ ∈ = - nguyên , l - chuẩn nhưng 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 { }{ }10min | 1,2,..., , 0Pik i i n x −= ∈ < Nếu 1 10 , P kj Px j N − −≥ ∀ ∈ thì bài toán (LN,C) không giải được. Nếu 1 0Pkjx −∃ < thì ta chọn cột cột quay l theo công thức : 1 1 1 , 0 ex min P kj P P l j j N x R l R − − − ∈ < = (20) và xây dựng lát cắt đúng nguyên (dòng quay) : 1 11 0 ( ) (21) 0 (22) ên P PP kjk n P j j N n P n P xxx x x x nguy λ λ− −− + ∈ + +   = + −        ≥ − ∑ (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 Bùi Thế Tâm V.7 Quy hoạch rời rạc 0 P ij ,n P P i Q j N T x ∈ ∈= là nguyên và l - chuẩn, trong đó : { }( ) { }1 \P PN N l n p−= ∪ + Nếu TP là chấp nhận được thì ( ) ( )0 1 00 10 0, ,..., , ,...,P P P P P P Pn nX x x x x x x= = là phương án 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) : 1 1 P klx λ −  = −   (24) II. Bảng TP phải là l - chuẩn : 1 1 1 0 P kjP P P j j l x R R Rλ − − − = + >    , (25) { }( )1\ \{ }P Pj N n p N l−∀ ∈ + = III. Cột 0 PR phải là lexmin : 1 1 10 0 0 ex min P P P Pk l xR R R lλ − − − = + →   (26) Chú ý : 1) 1 1 0 1 P P Pl n P l RR R − − + −= = >− suy ra bất đẳng thức (25) đúng với j = n + p rồi. 2) Từ (24) và 1 0Pklx − 2.6. Xác định λ thỏa mãn (24) - (26) a) Điều kiện (24) có thể viết thành : 1 1 0 P klx λ − − ≤ < , do 0λ > nên ta có : 1Pklxλ −≥ − (24') b) Điều kiện (25) có thể đơn giản hóa bằng cách sau. Nếu 1 0Pkjx − ≥ thì 1 1 0 P kj P l x Rλ − −  ≥    và điều kiện (25) đúng với bất kỳ 0λ > . Do vậy, chỉ cần xét điều kiện (25) với : 1 \{ }Pj N l−∈ mà 1 0Pkjx − < . Bùi Thế Tâm V.8 Quy hoạch rời rạc Với mỗi 1Pj N −∈ , ta đặt : { }( ) min | 0 .p-1ijh j i x= > Từ (20) suy ra P-1P-1 kj( ) ax{h(j)|j N , x <0}h l m= ∈ . Rõ ràng, nếu h(j) < h(l) thì với bất kỳλ ta có : 1 1 1 0 P kjP P P j j l x R R Rλ − − − = + >    Do đó, trường hợp này (25) cũng đúng. Như vậy, chỉ cần xét (25) với : 1 \{ }Pj N l−∈ mà 1 0Pkjx − < và h(j) = h(l). Khi đó, điều kiện (25) được viết lại là : 1 1 1 ' 10 , P kjP P P j j l P x R R R j Nλ − − − −  = + > ∀ ∈    (25') { }' P-11 1 kj| \{ } , x 0 , ( ) ( )P PN j j N l h j h l− −= ∈ < = Nếu ' 1PN − = ∅ 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ử ' 1PN − ≠ ∅ . Khi đó đối với mỗi ' 1Pj N −∈ ta có thể tìm được số tự nhiên zj sao cho : 1 1 1 1( 1) 0P P P Pj j l j j lR z R R z R − − − −− + < < − (27) Chú ý rằng 1 1P Pj lR zR − −≠ với z bất kỳ, vì nếu 1 1P Pj lR zR− −= thì 0 1 P-1 ij , det 0 Pi N j N x −∈ ∈ = , điều này là không thể. Do đó 1 1à P Pj lR v R− − là không tỉ lệ với nhau. Có 4 khả năng : 1) 1 1( ) ( ) P P h l j h l lx x − −= . Khi đó nếu chọn zj = 1 thì (27) thỏa mãn. 2) 1 1( ) ( ) P P h l j h l lx qx r − −= + trong đó q, r là các số tự nhiên, 1( )Ph l lr x −< . Khi đó nếu chọn chọn zj = q thì (27) được thỏa mãn. 3) 1 1P Pij ilx qx − −= , i = h(l) , h(l) + 1 , ... , h(l) + t ≡ s - 1, và 1 1P Psj slx qx − −> trong đó q là số tự nhiên ≥2. Khi đó, nếu ta chọn zj = q thì (27) đúng. 4) 1 1P Pij ilx qx − −= , i = h(l) , h(l) + 1 , ... , h(l) + t ≡ s - 1, và 1 1P P sj slx qx − −< , trong đó q là số tự nhiên ≥ 2. Khi đó, ta chọn zj = q - 1 thì (27) đúng. Bùi Thế Tâm V.9 Quy hoạch rời rạc Từ (27) và (25') suy ra cần chọn số λ thỏa mãn: 1 ' 1, P kj j P x z j Nλ − −  − ≤ ∀ ∈    , hay 1P kj j x zλ − ≥ − , suy ra 1P kj j x z λ − ≥ − . Vậy điều kiện (25') chuyển thành điều kiện sau: P-1 kj ' 1 j x ax - z P m j Nλ θ −   ≥ ≡ ∈    (25'') 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 , 1 10 0, 0 P P k lx R − − 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ó : { }P-1klax -x ,mλ θ= (28) 2.7. Giải ví dụ bằng số Giải bài toán quy hoạch nguyên sau: Max 43210 3663 xxxxx −−+= 3 984 96672 59224 41 321 4321 4321 ≤ ≤−+− ≥+++ ≤−−− xx xxx xxxx xxxx 4- 8- 8 4321 ,,, xxxx nguyên. Sau khi thêm biến bù bài toán viết lại thành Max 43210 3663 xxxxx −−+= 43215 92245 xxxxx +++−= 43216 66729 xxxxx ++++−= 3217 9848 xxxx +−+= 418 483 xxx ++= 876543210 ,,,,,,,, xxxxxxxxx nguyên Bùi Thế Tâm V.10 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- chuẩn nên ta phải thêm ràng buộc phụ 1004321 =≤+++ gzxxxx hay 43219 100 xxxxx −−−−= - và 09 ≥x và viết vào phía dưới bảng 1. Chọn dòng x9 làm dòng quay. 1 -x1 -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 <0 nên sinh ra lát cắt x10 và chọn nó làm dòng quay. Bảng 2 x10 -66 -1* -1 -2 -1 Tiếp tục dùng thuật toán đơn hình đối ngẫu từ vựng ta được bảng 3 là l- chuẩn và không chấp nhận được. Vì x5 <0 nên sinh ra lát cắt x11 và chọn nó làm dòng quay. 1 -x1 -x9 -x3 -x4 x0 600 3 6 12 9 x1 0 -1 0 0 0 x2 100 1 1 1 1 x3 0 0 0 -1 0 x4 0 0 0 0 -1 x5 205 6 2 0 -7 x6 691 5 7 1 1 x7 -792 -12 -8 -17 -8 x8 3 -8 0 0 -4 Bùi Thế Tâm V.11 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 <0 nên sinh ra lát cắt x12 và chọn nó làm dòng quay. 1 -x10 -x11 -x3 -x4 x0 357 3 3 3 3 x1 51 -1 1 1 0 x2 34 1 0 -1 0 x3 0 0 0 -1 0 x4 0 0 0 0 -1 x5 131 6 -4 -8 -9 x6 331 5 2 -11 -6 x7 -60 -12 4 3 0 x8 441 -8 8 8 -4 Bảng 4 x12 -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 5 là l- chuẩn và không chấp nhận được. Vì x7 <0 nên sinh ra lát cắt x13 và chọn nó làm dòng quay. Bùi Thế Tâm V.12 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 <0 nên sinh ra lát cắt x14 và chọn nó làm dòng quay. 1 -x13 -x11 -x3 -x12 x0 297 3 0 0 3 x1 56 -1 1 1 0 x2 29 1 0 -1 0 x3 0 0 0 -1 0 x4 15 0 1 1 -1 x5 -26 6 5 1 -9 x6 396 5 8 -5 -6 x7 0 -12 4 3 0 x8 511 -8 12 12 -4 Bảng 6 x14 -3 0 0 0 -1* 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 l- chuẩn chấp nhận được có cột phương án là nguyên và quá trình lặp kết thúc. Bùi Thế Tâm V.13 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 Bảng tổng hợp :(Phương án và giá trị λ ở mỗi bước) P x p0 x p 1 x p 2 x p 3 x p 4 x p 5 x p 6 x p 7 x p 8 λ 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: max 1 0 →=∑ = j m j j xcx ij m j ij bxa ≤∑ =1 , pi ,...,1= 0≥jx , mj ,...,2,1= jx nguyên. Bùi Thế Tâm V.14 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. Nếu bài toán có ràng buộc đẳng thức dạng: ii m j ij bxa =∑ =1 thì ta thay thế bằng hai bất đẳng thức: ii m j ij bxa ≤∑ =1 và ii m j ij bxa ≥∑ =1 . Sau khi thêm biến bù bài toán trên có thể viết ở dạng: max))(( 1 0 →−−=∑ = m j jj xcx mjxx jj ,...,2,1))(1( =−−= .,...,2,1))(( 1 pixabx j m j ijiim =−−+= ∑ = + .,...,2,10 pmjx j +=≥ jx nguyên. .,...,2,1 pmj += • 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 jiij cba . - 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 : Bùi Thế Tâm V.15 Quy hoạch rời rạc - 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 0 1 2 3 4 5 6 7 8 1 2 3 4 •Văn bản chương trình #include #include #include -x1 -x2 . . . . . . . . . –xm 0 -c1 -c2 . . . . . . . . –cm x0 x1 x2 # xm 0 0 # 0 -1 0 . . . . . . . . . . 0 0 -1 . . . . . . . . . 0 # # % # 0 0 . . . . . . . . . . -1 xm+1 # xn b1 # bp -a11 . . . . . . . . . - a1m # # # -ap1 . . . . . . . . . .-ap,m Bùi Thế Tâm V.16 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<=n;i++)for(j=0;j<=m;j++) fscanf(f1,"%ld",&s[i][j]); for (i=0; i<=n;i++) fscanf(f1,"%d",&cs[i]) ; for (j=1; j<=m; j++) fscanf(f1,"%d",&nc[j]); fclose(f1); sb=1; blap=0; // In kiem tra ket qua nhap printf("\n n,m,gz,ss = %d %d %10ld %d",n,m,gz,ss); if (tg==1){ printf("\nVao ten tep chua ket qua : "); gets(s2); f2=fopen(s2,"w"); fprintf(f2,"\n n,m,gz,ss = %d %d %10ld %d",n,m,gz,ss); } printf("\nBang 1, so lieu ban dau:"); if (tg==1) fprintf(f2,"\nBang 1, so lieu ban dau:"); inbang(0); // Kiem tra l- chuan if (ss==1){ printf("\nBang 1, so lieu ban dau, l- chuan"); if (tg==1) Bùi Thế Tâm V.17 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<=m; j++) s[n+1][j]=1; printf("\nBang %d, sau khi them rang buoc phu",sb); if (tg==1) fprintf(f2,"\nBang %d, sau khi them rang buoc phu",sb); inbang(1); l=n+1; printf("\nDong quay = %d",l); if (tg==1) fprintf(f2,"\nDong quay = %d",l); cmin=1; for (j=2;j<=m;j++) { for (i=0; i<=n;i++) { if (s[i][cmin] > s[i][j]) {cmin=j; break;} if (s[i][cmin] < s[i][j]) break; } } printf("\nCot quay= %d Phan tu quay= %10ld",cmin,s[l][cmin]); if (tg==1) fprintf(f2,"\nCot quay= %d Phan tu quay= %10ld", cmin,s[l][cmin]); biendoi();sb++; printf("\nBang %d, khong ke dong n+1, l - chuan",sb); if (tg==1) fprintf(f2,"\nBang %d, khong ke dong n+1, l- chuan",sb); inbang(0); lc=n+1; //Bat dau buoc lap lon, da tim duoc bang xuat phat l- chuan Lap1: blap++; 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 cot phuong an con thanh phan am khong ka=-1; for (i=1; i<=n; i++) if (s[i][0]<0) {ka = i; break; } Bùi Thế Tâm V.18 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<=n;i++) printf("\nx[%2d] = %13ld",cs[i],s[i][0]); printf("\nSo luong lat cat: %d lat cat",blap-1); printf("\nSo bang da lap : %d bang",sb); if (tg==1) { for (i=0; i<=n;i++) fprintf(f2,"\nx[%2d] = %13ld",cs[i],s[i][0]); fprintf(f2,"\nSo luong lat cat: %d lat cat",blap-1); fprintf(f2,"\nSo bang 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; } // Kiem tra tinh khong giai duoc k=0; for (j=1; j<=m; j++) if (s[ka][j]< 0) { k=j; break;} if (k==0) { printf("\n \nBai toan QHTT nguyen khong giai duoc, STOP"); if (tg==1) fprintf(f2,"\n\nBai toan QHTT nguyen khong giai duoc, STOP"); getch(); getch(); getch(); return; } // Tim cot quay Bùi Thế Tâm V.19 Quy hoạch rời rạc cmin=k; for (j=k+1;j<=m;j++) if (s[ka][j]< 0) { for (i=0; i<=n;i++) { if (s[i][cmin] > s[i][j]) {cmin=j; break;} if (s[i][cmin] < s[i][j]) break; } } printf("\nCot quay = %d",cmin); if (tg==1) fprintf(f2,"\nCot quay = %d ",cmin); // Xay dung lat cat lamda = -s[ka][cmin]; printf("\nlamda = %10ld",lamda); if (tg==1) fprintf(f2,"\nlamda = %10ld",lamda); for (j=1;j<=m;j++) np[j]=0; for (j=1;j<=m; j++) if (s[ka][j]<0) np[j]=1; np[cmin]=0; printf("\nMang NP : "); for (j=1;j<=m;j++) printf("%d ",np[j]); printf("\n"); if (tg==1) { fprintf(f2,"\nMang NP : "); for(j=1;j<=m;j++) fprintf(f2,"%d ",np[j]); fprintf(f2,"\n"); } // Xet np co trong hay khong trong=1; for (j=1; j<=m; j++) if (np[j]==1) {trong=0; break;} if (trong==1) goto L2; // Truong hop np khac trong, tim hl for (i=0;i0) {hl=i; break;} printf("\nh[%d] = %d",cmin,hl); if (tg==1) fprintf(f2,"\nh[%d] = %d",cmin,hl); // Tim cac hj ung voi cac cot ma np[j]=1 for (j=1;j<=m;j++) if (np[j]==1) { for (i=0;i0) {hj=i; break;} printf("\nh[%d] = %d",j,hj); if (tg==1) fprintf(f2,"\nh[%d] = %d",j,hj); if (hj != hl) np[j]=0; // np chi xet voi j ma hj=hl } Bùi Thế Tâm V.20 Quy hoạch rời rạc printf("\nMang NP : "); for (j=1;j<=m;j++) printf("%d ",np[j]); printf("\n"); if (tg==1) { fprintf(f2,"\nMang NP : "); for(j=1;j<=m;j++) fprintf(f2,"%d ",np[j]); fprintf(f2,"\n"); } // Kiem tra tap np khac trong hay khong trong=1; for (j=1; j<=m; j++) if (np[j]==1) {trong=0; break;} if (trong==1) goto L2; // Tinh cac zj for (j=1;j<=m;j++) zj[j]=0; for (j=1;j<=m;j++) if (np[j]==1) { if (s[hl][j]==s[hl][cmin]) zj[j]=1; // kha nang 1 else {if (s[hl][j]%s[hl][cmin]>0) zj[j]=s[hl][j]/s[hl][cmin]; // kha nang 2 else { q = s[hl][j]/s[hl][cmin]; is = hl; while (s[is][j]== q* s[is][cmin]) is++; if (s[is][j]> q* s[is][cmin]) zj[j]=q; // kha nang 3 else zj[j]=q-1; // kha nang 4 } } } // In mang ZJ printf("\nMang ZJ : "); for (j=1;j<=m;j++) printf("%d ",zj[j]); printf("\n"); if (tg==1) { fprintf(f2,"\nMang ZJ : "); for(j=1;j<=m;j++) fprintf(f2,"%d ",zj[j]); fprintf(f2,"\n"); } // Tinh lai lamda for (j=1;j<=m;j++) if (np[j]==1) { if ((-s[ka][j])%zj[j]==0) q= (-s[ka][j])/zj[j]; else q= (-s[ka][j])/zj[j]+1; if (q>lamda) lamda=q; } // Da tinh xong lamda, xay dung lat cat L2: printf("\nlamda cuoi cung = %ld",lamda); if (tg==1) fprintf(f2,"\nlamda cuoi cung = %ld",lamda); Bùi Thế Tâm V.21 Quy hoạch rời rạc lc++; cs[n+1]=lc; for (j=0; j<=m; j++) { if (s[ka][j]>=0) s[n+1][j]=s[ka][j]/lamda; else { if ((-s[ka][j])%lamda==0) s[n+1][j]=s[ka][j]/lamda; else s[n+1][j]=s[ka][j]/lamda-1; } } printf("\nBang %d, sau khi them lat cat moi",sb); if (tg==1) fprintf(f2,"\nBang %d, sau khi them lat cat moi",sb); inbang(1); // Bien doi bang don hinh l=n+1 ; printf("\nDong quay = %d",l); if (tg==1) fprintf(f2,"\nDong quay = %d",l); biendoi(); sb++; printf("\nBang %d, khong ke dong n+1",sb); if (tg==1) fprintf(f2,"\nBang %d, khong ke dong n+1",sb); inbang(0); goto Lap1; } void biendoi() { for (j=0;j<=m;j++) if (j!= cmin) { for (i=0;i<=n;i++) if (i!=l) s[i][j]=s[i][j]-(s[l][j]/s[l][cmin])*s[i][cmin]; s[l][j]=0; } for(i=0;i<=n;i++)if (i!=l) s[i][cmin]=-s[i][cmin]/s[l][cmin]; s[l][cmin]=-1; nc[cmin]=cs[l]; } void inbang(int cuoi) { int n1; if (cuoi==1) n1=n+1; else n1=n; printf("\nCo so : "); for (i=0; i<=n1;i++) printf("%d ",cs[i]) ; printf("\n"); printf("Phi co so : "); for (j=1; j<=m; j++) printf("%d ",nc[j]);printf("\n"); for (i=0;i<=n1;i++) { for (j=0; j<=m;j++) Bùi Thế Tâm V.22 Quy hoạch rời rạc printf(" %10ld ",s[i][j]); printf("\n"); } if (tg==1) { fprintf(f2,"\nCo so : "); for(i=0; i<=n1;i++) fprintf(f2,"%d",cs[i]); fprintf(f2,"\n"); fprintf(f2,"Phi co so : "); for(j=1;j<=m;j++) fprintf(f2,"%d ",nc[j]);fprintf(f2,"\n"); for (i=0;i<=n1;i++) { for (j=0; j<=m;j++) fprintf(f2," %10ld ",s[i][j]); fprintf(f2,"\n"); } } getch(); } • 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] = 288 x[ 1] = 56 x[ 2] = 29 x[ 3] = 0 x[ 4] = 18 x[ 5] = 1 x[ 6] = 414 x[ 7] = 0 x[ 8] = 523 Số lượng lát cắt: 5 lát cắt Số bảng đã lập : 7 bảng BÀI TẬP Giải các bài toán quy hoạch tuyến tính nguyên sau bằng thuật toán Gomory thứ ba: Bài 1. Max x0 = x1 + x2 3 * x1 + 2 * x2 <= 5 x2 <= 2 x1, x2 => 0 và nguyên Đáp số : (x0, x1, x2, x3, x4) = (2; 1; 1; 0; 1) Bài 2. Max x0 = 3 * x1 – 4 * x2 - 2 * x1 + x2 <= 3 x1 – 2 * x2 <= 3 2 * x1 + x2 <= 10 Bùi Thế Tâm V.23 Quy hoạch rời rạc x1, x2 => 0 và nguyên Đáp số : (x0, x1, x2, x3, x4, x5) = (9; 3; 0; 9; 0; 4) Bài 3. Max x0 = x1 – x2 - 2 * x1 + 2 * x2 + x3 = 2 x1 – 2 * x2 + x4 = 3 x1 + x2 + x5 = 6 x1, x2, x3, x4, x5 => 0 và nguyên Đáp số : (x0, x1, x2, x3, x4, x5) = ( 4; 5; 1; 10; 0; 0) Bài 4. Max x0 = x1 – 2 * x2 5 * x1 – 2 * x2 <= 3 x1 + x2 => 1 -3 * x1 + x2 <= 3 x1, x2, x3 => 0 và nguyên Đáp số : ( x0, x1, x2, x3, x4, x5) = ( -1; 1; 1; 0; 1; 5) Bài 5. ( )0 1 2 1 2 3 1 2 4 1 2 5 ax 9 4 7 4 5 6 6 0, 1,...,5 ªn, j=1,...,5 j j m x x x x x x x x x x x x x j x nguy ≡ + + + = − + + = − + = ≥ = − Đáp số : ( x0, x1, x2, x3, x4, x5) = (5; 3; 2; 4; 2; 3) Bài 6. Max 43210 252 xxxxx ++−= 6557 4321 ≤−+−− xxxx 493765 4321 ≤+−− xxxx 24642 4321 −≤−+− xxxx -3 ≤+++ 4321 89 xxxx 16827 4321 ≤+−−− xxxx 43210 ,,,, xxxxx nguyên. Đáp số: phương án tối ưu mở rộng (294, 26, 0, 40, 34, 10, 1, 192, 655, 26) 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 0G G≡ . Bằng một cách nào đó 0G được chia thành một số hữu hạn các tập con ( thường là không giao nhau) 1 1 1 1 1 2, ,...., rG G G . Bước 1k ≥ . Có tập 1 2, ,...., kk k krG G G cần chia nhánh. Ta chọn tập ( )k kGϑ theo một qui tắc nào đó và chia thành một số hữu hạn các tập con : ( ) ( ) ( ),1 ,2 , ( ), ,....,k k kk k k s kG G Gϑ ϑ ϑ , gồm có ( )s k tập. Khi đó, tập cần chia nhánh tiếp theo là 1 2 1 1, ,...., , ,...,k k k k k k k k rG G G G Gϑ ϑ− + , ( ) ( ) ( ) ( ),1 ,2 ,, ,....,k k kk k k s kG G Gϑ ϑ ϑ Ta đánh số lại là 1 1 1 1 1 2, ,...., k k k k rG G G + + + + . 3. Tính lại đánh giá Nếu tập 1 2G G⊂ thì ( ) ( ) 1 2 min min X G X G f X f X∈ ∈≥ . Vì vậy khi chia tập G′ thành 1 2, ,...., sG G G′ ′ ′ sao cho 1 ' s i i G G = ′=∪ thì cận của bất kì tập iG′ đều có ( ) ( ) ( ), 1,..,iG G i 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 đó ( ) ( ).iG Gζ ζ′ ′; 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 đó. 5. Tiêu chuẩn tối ưu. Giả sử 1 s i i G G = =∪ và phương án X Gϑ∈ thỏa mãn điều kiện: ( ) ( ) ( ) , 1,..,if X G G i sϑζ ζ= ≤ ∀ = thì X là phương án tối ưu của bài toá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ử ( ) 1,..,1 , min s i ii si G G Gζ ζ== = =∪ . Nếu X là một phương án của bài toán xuất phát thì ( ) ( )min x G f X f Xζ ∈≤ ≤ . Nếu ( )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 ( ) ( )0G Gζ ζ= . 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 0G = 11 1 11 2 .... rG G G∪ ∪ ∪ , tức là chia thành các tập con (thường là không giao nhau). Bước 1k ≥ . Tính các đánh giá ( ) , 1,..,ki kG i rζ = . Nếu tìm được phương án X , k rX G∈ sao cho ( ) ( ) ( ) ,k kr if X G Gζ ζ= ≤ với 1,2,.., ki r∀ = , thì X là phương án tối ưu, quá trình kết thúc. Ngược lại, chọn ( )k kGϑ để chia, theo tiêu chuẩn ( )( ) ( )1,..,minkk kik i rG Gϑζ ζ== . Ta chia tập ( )k kGϑ thành một số tập con ( ) ( ) ( ) ( ) ( ),1 ,2 ,....k k k kk k k k s kG G G Gϑ ϑ ϑ ϑ= ∪ ∪ ∪ . Tập cần chia tiếp theo là 1 2 1 1, ,...., , ,...,k k k k k k k k rG G G G Gϑ ϑ− + , ( ) ( ) ( ),1 ,2 ,, ,...., kk k kk k k sG G Gϑ ϑ ϑ Sau đó ta đánh số lại là 1 1 1 1 1 2, ,...., k k k k rG G G + + + + và sang bước k+1. 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: ( ) 1 min n j j j Z f X c x = = =∑ (3) với các điều kiện ràng buộc ij j=1 , 1,.., n j i ia x R b i m=∑ (quan hệ thứ tự { }, ,iR ∈ ≤ ≥ = ) (4) 0 , 1,.., .j jx d j n≤ ≤ = (5) jx nguyên 11,..,j n= 1n n≤ (6) trong đó jd là cận trên của biến jx (có thể jd = +∞ ). 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 1n n= , ta có bài toán qui hoạch nguyên hoàn toàn, còn nếu 1n 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 0G G≡ xác định bởi (4) - (6). 2. Cho các tập ( )k kGϑ , 1,.., ,krϑ = và 1,2,....k = . xác định bởi (4),(6) và ràng buộc bổ sung: , 1,..,j j j k k h x d j nϑ ϑ    ≤ ≤ =       . (7) 3. Tính cận. Đối với 0G ước lượng ( ) ( )00G f Xζ = với 0X là lời giải của bài toán qui hoạch tuyến tính (3)-(5). Đối với kGϑ thì ( )k kG f Xϑζ ϑ  =      , trong đó kX ϑ    là lời giải của bài toán qui hoạch tuyến tính (3),(4) và (7). Nếu ( )kGϑ = ∅ thì ( )kGϑζ = +∞ . 4. Tính phương án. Nếu 0X thỏa mãn điều kiện nguyên (6), thì 0X là nghiệm tối ưu của bài toán ban đầu, thuật toán dừng. Bùi Thế Tâm VI.4 Quy hoạch rời rạc Nếu k 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 (3), (4), (7), (6) và nó cũng là một phương án của bài toán ban đầu. Lấy k X ϑ     để cải tiến cận trên. 5. Chia nhánh. Cần chia nhánh khi ( ) k X kϑ     không thỏa mãn điều kiện nguyên (6). Giả sử ( ) 1,1r k x r n kϑ   ≤ ≤   là một thành phần không nguyên của phương án này, khi đó tập hợp ( )k kGϑ chia thành hai tập hợp ( ) ( ) ( ),1 ,2k k kk k kG G Gϑ ϑ ϑ= ∪ , trong đó ( ) ( ) ( ) ( ) ( ) ( ) ,1 ,2 | , | , 1 k k r rk k k k r rk k k G X X G x x k k G X X G x x k ϑ ϑ ϑ ϑ ϑ ϑ     = ∈ ≤              = ∈ ≥ +         Chú ý rằng nếu tất cả jc trong (3) là nguyên với 1j n≤ và 10jc khi j n= ≥ thì cận dưới ( )kGϑζ có thể dùng đánh giá mạnh hơn ( ) ( )k kG f Xϑ ϑζ  ′ =   , ở đây kí hiệu ] [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) Bước 0. Giải bài toán (8)-(10), tìm được nghiệm 0 4 54 ,2 9 9 X  =    . Cận dưới ( ) ( ) ] [0 0 7 7G f Xζ  ′ = = − = −  . Phương án 0X không thỏa mãn điều kiện nguyên (11). Chúng ta chia 0G thành hai tập hợp 0 1 11 2G G G= ∪ , trong đó { } { } 1 0 1 1 1 0 2 1 | , 4 | , 5 G X X G x G X X G x = ∈ ≤ = ∈ ≥ Bùi Thế Tâm VI.5 Quy hoạch rời rạc 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 11G và 12G . Trong bài toán đầu tiên cực tiểu trên miền 1 1G đạt tại điểm 84,2 11     , do đó ( )11 86 611Gζ  ′ = − = −   . Tập 12G là trống nên ( )12Gς = +∞ . Chọn 11G để chia nhánh ta được: { } { } 1 1 2 1,1 1 2 1 1 1 2 1,2 1 2 2 | , 2 | , 3 G X X G x G G X X G x G = ∈ ≤ ≡ = ∈ ≥ ≡ 1 22 3G G= =∅ Bước 2. Giải các bài toán qui hoạch tuyến tính: 1) Tìm cực tiểu (8) trên 21G được ( )212 3 33 , 2 5 51 4 4X Gζ     ′= ⇒ = − = −          2) Tìm cực tiểu (8) trên 22G được ( )222 1 12 ,3 5 52 2 2X Gζ     ′= ⇒ = − = −          3) 1 22 3G G= =∅ , ( )23Gζ ′ = +∞ Chọn 21G để chia nhánh : { } { } 2 2 3 1,1 1 1 1 2 2 3 1,2 1 1 2 | , 3 | , 4 G X X G x G G X X G x G = ∈ ≤ ≡ = ∈ ≥ ≡ Đánh số lại 2 3 2 3 2 3 2 31,1 1 1,2 2 2 3 3 4, , ,G G G G G G G G≡ ≡ = ≡ Bước 3. Giải các bài toán qui hoạch tuyến tính: 1) Tìm cực tiểu (8) trên 31G được ( ) ( ) ] [313 3, 2 5 51X Gζ  ′= ⇒ = − = −   2) 32G =∅ ( )32Gζ ′⇒ = +∞ 3) Tìm cực tiểu (8) trên 33G được ( )333 2 1 12 ,3 5 53 2 2 2X X Gζ       ′= = ⇒ = − = −              4) 3 24 3G G= =∅ ( )34Gζ ′⇒ = +∞ Bùi Thế Tâm VI.6 Quy hoạch rời rạc Phương án ( )3 3, 2 1 X X  = =   thỏa mãn điều kịên nguyên (11). Đồng thời ( ) ( ) ( ) ( ){ } { } ( )3 3 3 31 2 3 4min , , , min 5, , 5, 5G G G G f Xζ ζ ζ ζ ζ′ ′ ′ ′ ′= = − ∞ − ∞ ≤ = − . Vậy phương án tối ưu của bài toán ban đầu là ( )3, 2X = . Ta có cây phân nhánh sau: 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 ijc là chi phí (hoặc là khoảng cách) đi từ thành phố i đến thành phố j . Giả thiết 0, ,ij iic i j c> ∀ ≠ = ∞ , với mọi i ( có thể ij jic c≠ ). Hãy tìm hành trình với tổng chi phí nhỏ nhất? Ký hiệu ma trận , 1,....,ij i j n C c == , 1ijx = hoặc 0 tùy thuộc người du lịch có đi từ 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: 1 1 6 G ζ ′ = − 0 7 G ζ ′ = − 1 2 3 2 3 4G G G ζ ≡ ≡ ′ = +∞ 1 2 1,1 1 5 G G ζ ≡ ′ = − 1 2 3 1,2 2 3 5 G G G ζ ≡ ≡ ′ = − 2 3 1,1 1 5 G G ζ ≡ ′ = − 2 3 1,2 2G G ζ = =∅ ′ = +∞ Bùi Thế Tâm VI.7 Quy hoạch rời rạc 1 1 min ij ij n n i j c x = = ∑∑ (12) { } ij 1 ij 1 ij ij 1, 1, 2,..., (13) 1, 1, 2,..., (14) 0;1 , , 1,2,..., (15) 1, 2 i j n (16) n j m i i j x i n x j n x i j n u u nx n = = = = = = ∈ = − + ≤ − ≤ ≠ ≤ ∑ ∑ trong đó iu 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 0S )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 kS 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 kS sẽ được chọn để chia nhỏ tiếp (phân nhánh). Khi phân nhánh 1 2k k kS S S= ∪ sao cho một tập 2kS bắt buộc đi qua thêm một cặp thành phố rsx nào đó (cách chọn xem ở phần tiếp theo), một tập 1kS không được đi qua cặp thành phố rsx . 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 0S . 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 , ( , 1, 2,.., )ij ij i jc c i j 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 *ij ij 1 1 1 1 n n n n ij ij i j i j c x c x = = = = ≤∑∑ ∑∑ Từ các hệ thức (12) và (17) ta có: Bùi Thế Tâm VI.8 Quy hoạch rời rạc ( )* * *ij ij ij 1 1 1 1 1 1 1 1 ij ij 1 1 1 1 1 1 n n n n n n n n ij i j ij ij i j i j i j i j i j n n n n n n ij i j ij i j i i i j c x c x c x c x c x α β α β α β = = = = = = = = = = = = = = ′ = − − = − − ′≤ − − = ∑∑ ∑∑ ∑∑ ∑ ∑ ∑∑ ∑ ∑ ∑∑ đ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 ij 0, ,c 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ố 1 1 n n i j i i γ α β = = = +∑ ∑ được gọi là hằng số rút gọn và đó chính là một cận dưới cho giá trị 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à pS thu được từ tập ban đầu 0S bằng cách cố định một số biến ijx ở 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 pS 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 pS . Thủ tục phân nhánh Giả sử ta cần phân nhánh tập 0pS S⊂ . Cách hay dùng là phân chia tập này thành hai tập con rời nhau ,p pS S′ ′′ với { } { } | , 0 , | , 1 p p rs p p rs S x x S x S x x S x ′ = ∈ = ′′ = ∈ = . trong đó, rsx là biến chưa cố định ở giá trị 0 hay 1 trong tập pS . Cặp ( ),r s dùng để phân nhánh được chọn sao cho tập pS ′′ có nhiều khả năng chứa phương án tối ưu, còn tập pS ′ thì không. Nói cách khác, ( ),r s được chọn sao cho hiệu số các cận dưới của pS ′′ và pS ′ là lớn nhất có thể được. Để giải quyết vấn đề này, ta chỉ cần xét tập các phương án ban đầu 0S , 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à 0, ,ijc 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 0S được chia thành hai tập rời nhau 1S và 2S với Bùi Thế Tâm VI.9 Quy hoạch rời rạc { } { } 1 0 2 0 | , 0 , | , 1 rs rs S x x S x S x x S x = ∈ = = ∈ = Trong tập 2S 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 2S một cận dưới đối với giá trị hàm mục tiêu tăng thêm là ( )2 rsS cγ = . Trong tập 1S do cố định 0rsx = nên từ các điều kiện (14), (15) suy ra phải có một ( )1rjx j s= ≠ và một ( )1isx i r= ≠ . Vì thế ( )1 min minrj isj s i rS c cγ ≠ ≠= + là một cận dưới đối với giá trị mục tiêu tăng thêm. Ta sẽ chọn biến rsx sao cho hiệu giữa các cận dưới này là lớn nhất, nghĩa là đạt ( ) ( ){ }1 2 ( , ) max r s S Sγ γ− (18) Nếu 0rsc > thì ( )1 0Sγ = (do trên hàng r và cột s của C đều chứa số 0), còn ( )2 0rsS cγ = > , từ đó ( ) ( )1 2 0S Sγ γ− < . Vì thế để có (18) ta chỉ cần xét các cặp ( ),r s với 0.rsc = Trong trường hợp này ( )2 0Sγ = và ( )1 0Sγ ≥ . Điều này có nghĩa là thay cho (18) ta có thể chọn biến rsx để phân nhánh theo qui tắc ( ) ( ) 0 , max , min min pq pj iqj q i pc r s p q c cθ θ ≠ ≠=  = = +   . Lập luận trên đây cũng đúng cả khi các tập phương án iS về sau được chia thành các tập 1,r rS S + , nhưng thay cho mức tăng của các cận dưới ( )2Sγ và ( )1Sγ ta xét mức tăng của các cận dưới ( )rSγ và ( )1rSγ + 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à 0S mà là { }1 1 2 20 1 2| , , ,....., k kp i j i j i j kS x x S x x xδ δ δ= ∈ = = = , 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 0, 1,.., 1, 1,..,ujx j v v n= = − + thì tất nhiên phải có 1uvx = . 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 1rsx = thì phải có 0srx = bằng cách đặt src = ∞ . Hơn nữa, nếu đường đi dài nhất trong pS chứa cạnh ( ),r s gồm ít nhất 2 và nhiều nhất 2n − cạnh ( ) 1 2 1 1 ... ... 1 1 3 u u v vi i i r rs si i ix x x x x v n + −= = = = = = = ≤ ≤ − Bùi Thế Tâm VI.10 Quy hoạch rời rạc (không có cạnh nào có dạng 1 1kix = hay 1vi jx = ), thì để ngăn cấm tạo chu trình con dạng ( )1 2 1, ,...., , , ,ui i i r s i ta đặt 1sic = ∞ , còn để ngăn cấm tạo chu trình con dạng ( )1 2, , , ,...., ,u u vr s i i i r+ + ta đặt vi rc = ∞ . Hơn nữa, ta cần có 1 0vi ix = bằng cách đặt 1vi ic = ∞ . Để tìm 1i ta có thể đi ngược từ r và để tìm vi ta có thể đi xuôi từ s theo danh sách các biến đã cố định ở giá trị 1 trong tập pS . Ở 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 2 4 77 42 21 16 3 47 17 36 16 28 4 39 90 80 56 7 5 28 46 88 33 25 6 3 88 18 46 92 ∞ ∞ ∞ ∞ ∞ ∞ Bước lặp 0. Tập đầu tiên 0S 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 0S . 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). y y y y y i1 i2 r s i3 i4 (19) Bùi Thế Tâm VI.11 Quy hoạch rời rạc 3 12 18 32 2 0 0 48 1 2 3 4 5 6 0 75 2 30 61 0 58 30 17 122 3 31 1 12 0 12 4 32 83 58 49 0 5 3 21 48 0 0 6 0 85 0 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 0S 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ó 0S nên ta chọn 0S để 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ố ( ), min minpj iqj q i pp q c cθ ≠ ≠= + và ghi ở phía trên bên phải của số 0, chẳng hạn ( ) ( )2,1 12, 6,3 48,....θ θ= = Ta thấy số 0 ở ô (6,3) có số mũ lớn nhất, nghĩa là ( ) ( ) 0 6,3 max , pqc p qθ θ = = . Vì thế ta chọn cặp (6,3) để phân nhánh. Khi đó, tập tất cả các hành trình được phân thành hai tập con: tập 1S gồm các hành trình chứa cạnh (6,3), tập 2S gồm các hành trình không chứa cạnh (6,3). Tính cận cho tập 2S 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 63c = ∞ ở 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 2S là: 2( )Sζ = 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 2 0 10 30 17 12 3 31 1 12 0 12 4 32 83 10 49 0 5 3 21 0 0 0 6 0 85 35 89 ∞ ∞ ∞ ∞ ∞ ∞ ∞ Tính cận cho tập 1S 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 36c = ∞ . Từ ma trận (20) ta thu được ma trận tương ứng với tập 1S (chưa kể các số mũ trên các số 0) (20) Bùi Thế Tâm VI.12 Quy hoạch rời rạc 3 15 18 32 2 0 1 2 4 5 6 2 30 61 0 30 17 122 0 31 1 123 0 32 83 494 0 3 215 0 0 ∞ ∞ ∞ ∞ ∞ Cận dưới 1( ) 81.Sζ = Bước lặp 2. Các tập cần xét tiếp là 1S và 2S với cận dưới tương ứng là 81 và 129. Tập 1S 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 1S sẽ được phân thành hai tập: tập 3S gồm các hành trình đi qua cạnh (6,3) và cạnh (4,6), tập 4S 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 4S . 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 4S 1 2 4 5 6 1 0 2 30 6 2 0 30 17 12 3 31 1 12 0 4 0 51 17 5 3 21 0 0 ∞ ∞ ∞ ∞ ∞ ∞ Cận dưới của tập 4S là 4 1( ) ( ) 32S Sζ ζ= + = 81 + 32 = 113. Tính cận dưới của tập 3S . 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ị 34c = ∞ và được ma trận (không kể số mũ trên các số 0): 3 20 18 5 1 2 4 5 1 0 2 30 2 0 30 17 3 31 1 0 5 3 21 0 ∞ ∞ ∞ ∞ Cận dưới của tập 3S vẫn là 81. (21) (22) 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à 2S , 3S , 4S với cận dưới tương ứng là 129, 81, 113. Tập 3S 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 3S được chia thành hai tập: - Tập 5S gồm các hành trình đi qua cung (6,3), (4,6), (2,1) - Tập 6S 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 6S . 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 6S 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): 3 13 1 28 2 1 2 4 5 0 2 301 2 13 0 3 28 1 0 5 0 21 0 ∞ ∞ ∞ ∞ ∞ Tính cận dưới cho tập 5S . Từ ma trận (22) xoá hàng 2 cột 1, cấm cung (1,2) bằng cách cho 12c = ∞ đượ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 5S 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): 28 20 28 20 2 4 5 0 281 3 0 0 5 20 0 ∞ ∞ ∞ Bước lặp 4. Các tập cần xét là 2S , 4S , 5S , 6S với cận dưới tương ứng là 129, 113, 84, 101. Tập 5S 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 5S được chia thành hai tập: - Tập 7S gồm các hành trình đi qua cung (6,3), (4,6), (2,1), (1,4) - Tập 8S 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 7S . 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 32c = ∞ vì ta đã chọn các cung đi qua các đỉnh 2, 1, 4, 6, (23) (24) 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 7S là 84 + 20 = 104 và ma trận tương ứng là 2 5 3 0 5 0 ∞ ∞ 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 8S . 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 8S là 84 + 28 = 112. Loại các tập. Vì các cận dưới 7 8 4 2( ) 104 , ( ) 112 , ( ) 113 , ( ) 129S S S Sζ β ζ β ζ β ζ β= = = = =; ; ; nên các tập 7 8 4 2, , ,S S S S có thể loại khỏi việc xét về sau, ta chỉ cần xét tập 6S . Bước lặp 5. Các tập cần xét chỉ còn 6S . 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 6S được chia thành hai tập: - Tập 9S 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 10S 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 10S . 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 10S là 101 + 28 = 129. Cận dưới này lớn hơn cận trên 104 nên tập 10S bị loại không cần xét về sau. Tính cận dưới cho tập 9S . 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 15c = ∞ , cột thứ 2 trừ đi số 2 ta được cận dưới 9( ) 101 2 103Sζ = + = và ma trận tương ứng (chưa kể số mũ trên các số phần tử 0) 1 11 11 1 2 4 5 0 01 2 11 0 3 1 0 ∞ ∞ ∞ Bước lặp 6. Các tập cần xét chỉ còn 9S . 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 9S được chia thành hai tập: (25) Bùi Thế Tâm VI.15 Quy hoạch rời rạc - Tập 11S 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 12S 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 11S . 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à 11( ) 103 1 104Sζ = + = . Tập 11S 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 12S . 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 12S là 103 + 11 = 114. Tập 12S 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. 0S , 81 1S , (6,3), 81 2 , (6,3)S , 129 3S , (4,6), 81 4 , (4,6)S , 113 5S , (2,1), 84 6 , (2,1)S , 101 7S , (1,4), 104 8 , (1,4)S , 112 9S , (5,1), 103 10 , (5,1)S , 129 11S , (1,4), 104 12 , (1,4)S , 114 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 2 3 4 5 6 1 27 43 16 30 26 2 7 16 1 30 25 3 20 13 35 5 0 4 21 16 25 18 18 5 12 46 27 48 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 2 3 4 5 6 1 31 15 23 10 17 2 16 24 7 12 12 3 34 3 25 54 25 4 15 20 33 50 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