Luận văn Phương pháp nhánh – cận cho bài toán quy hoạch nguyên

affine. (ii) Hệ vectơ 2 1 1,..., n kv v v v− − ∈ là độc lập tuyến tính. (iii) Hệ vectơ 1 1,..., 1 1 k nvv +   ∈        là độc lập tuyến tính. Định nghĩa 1.2.11. Vectơ ( , )x P P A b∈ = được gọi là điểm trong tương đối của tập lồi đa diện nếu nó không thuộc bất kỳ diện không tầm thường nào của đa diện P . Bổ đề 1.2.12. Cho F là một diện của tập lồi đa diện ( , )P A b và x F∈ . Khi đó x là điểm trong tương đối của F khi và chỉ khi ({ }) ( )eq x eq F= . Chứng minh Gọi G là diện nhỏ nhất của F chứa x . Khi đó, x là điểm trong tương đối của F khi và chỉ khi F G= . Theo mệnh đề 1.2.7 ta có ( ({ }))G fa eq x= . Vậy x là điểm trong tương đối của F khi và chỉ khi ( ({ }))fa eq x F= . Suy ra x là điểm trong tương đối của F khi và chỉ khi ({ }) ( )eq x eq F= .  13 Do đó, ta có định nghĩa tương đương với định nghĩa 1.2.11 là : ( , )x P P A b∈ = là điểm trong tương đối của P nếu ({ }) ( )eq x eq P= . Bổ đề 1.2.13. Cho ( , )P P A b= là tập lồi đa diện khác rỗng. Khi đó, tập hợp các điểm trong tương đối của P cũng khác rỗng. Chứng minh Đặt {1,..., }M m= là tập chỉ số các dòng của A . : ( )I eq P= và : \J M I= . Khi đó, nếu J = ∅ thì I M= . Theo hệ quả 1.2.8 (i) ta có tập lồi đa diện P không có bất kỳ diện không tầm thường nào. Do đó, bất kỳ điểm nào của P cũng là điểm trong tương đối. Nếu J ≠ ∅ thì với mỗi j J∈ ta tìm được jx P∈ sao cho jAx b≤ và jj jA x b< . Do P là tập lồi nên 1: | | j j J y x J ∈ = ∑ (trong đó | |J là số phần tử của J ) cũng thuộc P . Do đó, J JA y b< và I IA y b= suy ra ({ }) ( )eq y eq P= . Ta được đpcm.  Định nghĩa 1.2.14. Số chiều của tập lồi đa diện nP ⊆  (kí hiệu là dim P ) là số bé hơn một đơn vị so với số lớn nhất các vectơ độc lập affine trong P . Ta có dim 1∅ = − . Định lý 1.2.15. (Định lý về số chiều) Cho F ≠ ∅ là một diện của tập lồi đa diện ( , ) nP A b ⊆  . Khi đó, ta có ( )dim eq FF n rankA= − . Chứng minh Theo kết quả của Đại số tuyến tính, ta có ( ) ( )dim kereq F eq Fn rankA A= + , trong đó ( )ker eq FA là không gian nghiệm của hệ phương trình thuần nhất có ma trận hệ số là ( )eq FA . Do đó, ta chỉ cần chứng minh ( )dim ker dimeq FA F= . Để cho gọn ta đặt : ( ); : dim ker ; : dimII eq F r A s F= = = . 14 “ r s≥ ”: Chọn 1s + vectơ độc lập affine 0 1, ,..., sx x x F∈ . Suy ra theo bổ đề 1.2.10 hệ vectơ 1 0 0,..., sx x x x− − là độc lập tuyến tính và 0( ) 0 , 1,...,jI I IA x x b b j s− = − = = . Suy ra r s≥ . “ r s≤ ”: Vì F ≠ ∅ nên 0s ≥ . Do đó ta cũng giả thiết 0r ≥ . Do F ≠ ∅ Theo bổ đề 1.2.13 tồn tại một điểm trong tương đối x F∈ mà theo bổ đề 1.2.12 ta có ({ }) ( )eq x eq F I= = . Vậy với : \J M I= ta có I IA x b= và J JA x b< . Đặt 1{ ,..., }rx x là cơ sở của ker IA . Khi đó, do J JA x b< ta có thể tìm được 0ε > sao cho ( )kJ JA x x bε+ < và ( ) k I IA x x bε+ = với 1,...,k r= . Suy ra kx x Fε+ ∈ với 1,...,k r= . Các vectơ 1,..., rx xε ε là độc lập tuyến tính , theo bổ đề 1.2.10 1, ,..., rx x x x xε ε+ + là những vectơ độc lập affine trong F . Suy ra r s≤ .  Định lý 1.2.16. (Hoffman - Kruskal) Cho ( , ) nP P A b= ⊆  là tập lồi đa diện. Khi đó, tập khác rỗng F P⊆ là diện nhỏ nhất của P khi và chỉ khi { : }I IF x A x b= = với I M⊆ ( M là tập chỉ số các dòng của A) và Irank A rank A= . Chứng minh “⇒”: Gọi F diện khác rỗng nhỏ nhất của P . Khi đó, theo định lý 1.2.5 và mệnh đề 1.2.7 ta có ( )F fa I= , trong đó ( )I eq F= . Đặt : \J M I= , ta có { : , } (1.12)I I J JF x A x b A x b= = ≤ . Ta cần chứng minh F G= , trong đó { : } (1.13)I IG x A x b= = . Theo (1.12) ta có F G⊆ . Giả sử tồn tại \y G F∈ . Khi đó, tồn tại j J∈ sao cho , (1.14)I I j jA y b A y b= > . Do F ≠ ∅ nên theo bổ đề 1.2.13 tồn tại điểm trong tương đối của F , ta gọi điểm đó là x . Ta xét điểm ( ) ( ) (1 )z x y x x yτ τ τ τ= + − = − + . 15 Ta thấy rằng ( ) (1 ) (1 )I I I I I IA z A x A y b b bτ τ τ τ τ= − + = − + = , vì x F∈ và y thỏa (1.14). Hơn nữa, (0)J J JA z A x b= < , vì \J M I⊆ . Vì .J jA y b> nên ta có thể tìm được τ ∈ và 0j J∈ sao cho 0 0( )j jA z bτ = và ( )J JA z bτ ≤ . Suy ra, 0τ ≠ và 0 0' { : , }I I j jF x P A x b A x b= ∈ = = là là một diện chứa trong F (vì \ 'x F F∈ ). Điều này mâu thuẫn với cách chọn F . Suy ra F G= . Ta cần chứng minh thêm Irank A rank A= . Thật vậy, nếu Irank A rank A< , thì tồn tại \j J M I∈ = sao cho jA không là tổ hợp tuyến tính của các dòng trong IA . Suy ra , ta có thể tìm được vectơ 0w ≠ sao cho 0IA w = và 0jA w > . Với 0θ > thích hợp ta có :y x wθ= + thỏa (1.14) và theo như trên ta có thể xây dựng được 'F F⊂ và 'F F≠ . Điều này mâu thuẫn. “⇐”: Nếu { : }I IF x A x b= = theo hệ quả 1.2.8 thì F không có bất kỳ diện không tầm thường nào. Và do F P⊆ nên { : , }I I J jF x A x b A x b= = ≤ là diện nhỏ nhất của P .  Hệ quả 1.2.17. Tất cả các diện nhỏ nhất của tập lồi đa diện ( , )P P A b= đều có cùng số chiều là n rank A− . 1.3.Điểm cực biên. Tia cực biên Định nghĩa 1.3.1. Điểm ( , )x P P A b∈ = được gọi là điểm cực biên của P nếu (1 )x x yλ λ= + − với ,x y P∈ và 0 1λ< < ta suy ra x y x= = . Định lý 1.3.2. Cho ( , ) nP P A b= ⊆  là tập lồi đa diện và x P∈ . Khi đó các mệnh đề sau là tương đương: (i) { }x là 0-diện của P (diện có số chiều là 0). (ii) Tồn tại một vectơ nc∈ sao cho x là nghiệm tối ưu duy nhất của quy hoạch tuyến tính min{ , : }c x x P ∈ . (iii) x là điểm cực biên của P . (iv) ({ })eq xrank A n= . Chứng minh 16 “(i) ⇒ (ii)”: Vì x là diện của P nên tồn tại bất phương trình ,w x t≥ sao cho { : , }P x w x t⊆ ≥ và { } { : , } { : , }x P x w x t x P w x t= ∩ ≥ = ∈ = . Do đó, x là nghiệm duy nhất của quy hoạch tuyến tính min{ , : }c x x P ∈ với :c w= . “(ii) ⇒ (iii)”: Cho x là nghiệm duy nhất của quy hoạch tuyến tính min{ , : }c x x P ∈ . Nếu (1 )x x yλ λ= + − với ,x y P∈ và 0 1λ< < thì ta có , , (1 ) , , (1 ) , ,c x c x c y c x c x c xλ λ λ λ= + − ≥ + − = . Suy ra , , ,c x c y c x== . Vì x là nghiệm duy nhất nên x y x= = . “(iii) ⇒ (iv)”: Đặt : ({ })I eq x= . Nếu Irank A n< thì tồn tại \{0} ny∈ sao cho 0IA y = . Khi đó, với 0ε > đủ nhỏ ta có :x x y Pε= + ∈ và :y x y Pε= − ∈ (vì ,j jA x b j I< ∀ ∉ ). Nhưng 1 1 2 2 x x y= + , điều này mâu thuẩn với giả thiết x là điểm cực biên của P . “(iv) ⇒ (i)”: Đặt : ({ })I eq x= . Theo (iv) ta có I IA x b= phải có nghiệm duy nhất lá x . Do đó, { } { : } { : }I I I Ix x A x b x P A x b= = = ∈ = . Theo định lý 1.2.5 ta có { }x là 0-diện của P .  Hệ quả 1.3.3. Tập lồi đa diện khác rỗng ( , ) nP P A b= ⊆  có ít nhất một điểm cực biên khi và chỉ khi rank A n= . Chứng minh Theo hệ quả 1.2.17 diện khác rỗng nhỏ nhất của P có số chiều là 0 khi và chỉ khi rank A n= .  Định nghĩa 1.3.4. Cho P là tập lồi đa diện. Khi đó, nón lùi xa . ( )char cone P được định nghĩa là: . ( ) : { : , }char cone P r x r P x P= + ∈ ∀ ∈ . Mỗi . ( )r char cone P∈ được gọi là tia của P . Tia r của P được gọi là tia cực biên nếu không tồn tại tia 1 2,r r của P sao cho 1 2 ,r rθ θ +≠ ∀ ∈ 1 2(1 ) , [0,1]r r rλ λ λ= + − ∈ . 17 Nhận xét: ta thấy rằng nếu P ≠ ∅ thì 0 . ( )char cone P∈ , và nếu P = ∅ thì . ( )char cone P = ∅ . Vậy ta có . ( )char cone P = ∅ khi và chỉ khi P = ∅ . Bổ đề 1.3.5. Cho ( , )P P A b= là tập lồi đa diện khác rỗng. Khi đó, . ( ) { : 0}char cone P x Ax= ≤ . Chứng minh Nếu 0Ay ≤ thì x P∀ ∈ , ta có ( )A x y Ax Ay Ax b+ = + ≤ ≤ . Do đó, x y P+ ∈ . Vậy . ( )y char cone P∈ . Đảo lại, với . ( )y char cone P∈ , ta có 0iA y ≤ nếu tồn tại x P∈ sao cho i iA x b= . Đặt { : , }j jJ j A x b x P= < ∀ ∈ . Ta cần chỉ ra rằng 0J JA y ≤ . Thật vậy, giả sử 0 ,jA y j J> ∈ , lấy một điểm trong tương đối x P∈ và ta xét , 0z x yλ λ= + ≥ . Khi đó, chọn 0λ > một cách hợp lý ta có thể tìm được 'j P∈ sao cho ' ' ,j j J JA z b A z b= ≤ và I IA z b≤ . Điều này mâu thuẫn với 'j J∈ .  Nhận xét: Ta thấy rằng nón lùi xa của P cũng là một tập lồi đa diện và nó có một điểm cực biên đó là vectơ 0. Thậy vậy, giả sử 0r ≠ là điểm cực biên của . ( )char cone P . Khi đó, . 0A r ≤ và từ 0r ≠ ta có 1 . ( ) 2 r r char cone P≠ ∈ và 3 . ( ) 2 r r char cone P≠ ∈ . Nhưng 1 1 1 3( ) ( ) 2 2 2 2 r r r= + , điều này mâu thuẫn với giả thiết r là điểm cực biên của . ( )char cone P . Do đó, cùng với hệ quả 1.3.3 ta có mệnh đề sau: Mệnh đề 1.3.6: Cho tập lồi đa diện ( , )P P A b= ≠ ∅ . Vectơ không là điểm cực biên của . ( )char cone P khi và chỉ khi rank A n= . Định lý 1.3.7: Cho ( , ) nP P A b= ⊂  là một tập lồi đa diện khác rỗng. Khi đó các mệnh đề sau là tương đương: (i) r là tia cực biên của P . (ii) { : }rθ θ +∈ là 1-diện của . ( ) { : 0}char cone P x Ax= ≤ . (iii) . ( ) \{0}r char cone P∈ và với : { : 0}iI i A r= = ta có 1Irank A n= − . 18 Chứng minh Đặt : { : 0}iI i A r= = . “(i)⇒(ii)”: Gọi F là diện nhỏ nhất của . ( )char cone P chứa tập { : }rθ θ +∈ . Theo mệnh đề 1.2.7 ta có { . ( ) : 0 }I IF x char cone P A x= ∈ = và ( )eq F I= . Nếu dim 1F > , thì theo định lý về số chiều 1.2.15 ta có 1Irank A n< − . Do đó, Tập nghiệm của hệ 0I IA x = chứa vectơ 1r độc lập tuyến tính với r . Với 0ε > đủ nhỏ ta có 1 . ( )r r char cone Pε± ∈ , vì 10, 0I IA r A r= = và \ 0M IA r < . Nhưng ta có 1 11 1( ) ( ) 2 2 r r r r rε ε= + + − , điều này mâu thuẫn với giả thiết r là tia cực biên. Do đó, dim 1F = . Vì 0r ≠ , tập không bị chặn { : }rθ θ +∈ chứa trong F cũng có số chiều bằng 1. Vậy { : }F rθ θ += ∈ là 1-diện của . ( )char cone P . “(ii)⇒(iii)”: Áp dụng định lý số chiều 1.2.15 cho . ( )char cone P ta suy ra 1Irank A n= − . Do { : }rθ θ +∈ có số chiều là 1 nên 0r ≠ . “(iii)⇒(i)”: Theo kết quả của đại số tuyến tính ta có tập nghiệm của hệ 0I IA x = có số chiều bằng 1. Do 0IA r = và 0r ≠ nên với y thỏa 0IA y = ta có ,y rθ θ= ∈ . Giả sử 1 2(1 )r r rλ λ= + − với 1 2, . ( )r r char cone P∈ . Khi đó,   1 2 0 0 0 (1 ) 0 I I I I I I IA r A r A rλ λ ≤ ≤ = = + − ≤ Suy ra 0 , 1,2jIA r j= = . Do đó 1 2r rθ= . Vậy r là tia cực biên. Định lý 1.3.8. Cho ( , )P P A b= là một tập lồi đa diện khác rỗng có ít nhất một điểm cực biên. Nếu bài toán quy hoạch tuyến tính min{ , : }c x x P ∈ có hàm mục tiêu không bị chặn dưới trên P thì tồn tại một tia cực biên r của P sao cho , 0c r < . Chứng minh Xét bài toán max{ , : }c x x P− ∈ . 19 Theo định lý đối ngẫu của quy hoạch tuyến tính thì tập hợp { : , 0}Ty A y c y= − ≥ phải là tập rỗng. Theo bổ đề Farkas, tồn tại r sao cho 0Ar ≥ và , 0c r− < . Đặt ' :r r= − suy ra ' 0Ar ≤ và , ' 0c r < Xét bài toán quy hoạch tuyến tính max{ , : 0, , 1} max{ , : '} (1.15)c x Ax c x c x x P− ≤ − ≤ = − ∈ . Vì rank A n= nên 'P cũng là tập lồi đa diện có ít nhất một điểm cực biên. Thêm nữa là 'P ≠ ∅ vì ' ' , ' r P c r ∈ − . Do ràng buộc , 1c x− ≤ suy ra (1.15) có nghiệm tối ưu. Dễ dàng suy ra được giá trị tối ưu của (1.15) là 1 đạt được tại ' , ' rx c r = − . Do nghiệm tối ưu của bài toán (1.15) đạt được tại điểm cực biên của ' . ( )P char cone P⊆ nên '* : . ( ) , ' rr char cone P c r = ∈ − . Suy ra , * 1 (1.16)c r= − . Đặt { : * 0}iI i A r= = . Theo định lý số chiều 1.2.15 ta có IArank n c   =    (vì theo định lý 1.3.2 { *}r là 0-diện của tập lồi đa diện 'P ). Nếu 1Irank A n= − , thì theo định lý 1.3.7 ta có *r là tia cực biên của P . Nếu Irank A n= , thì theo định lý 1.3.2 ta có *r là điểm cực biên của . ( )char cone P , mâu thuẫn với mệnh đề 1.3.6.  Định lý 1.3.9. Cho ( , )P P A b= là tập lồi đa diện khác rỗng và rank A n= (tức là P có ít nhất một điểm cực biên). Khi đó, { : , 1, 0, 0} (1.17)n k jk j k k j k K j J k K P x x x rλ µ λ λ µ ∈ ∈ ∈ = ∈ = + = ≥ ≥∑ ∑ ∑ trong đó, ,kx k K∈ là các điểm cực biên của P và ,jr j J∈ là các tia cực biên của P . 20 Chứng minh Đặt Q là tập hợp bên vế phải của (1.17). Vì kx P∈ với k K∈ và P là tập lồi, nên ta có bao lồi kk k K xλ ∈ ∑ cũng thuộc P . Hơn nữa, do jr là tia của P nên ta có j j j J x r Pµ ∈ + ∈∑ với 0jµ ≥ . Suy ra Q P⊆ . Giả sử Q P≠ . Khi đó, tồn tại \v P Q∈ , tức là không tồn tại nghiệm ,λ µ của hệ phương trình sau: (1.18 ) 1 (1.18 ) , 0 (1.18 ) k j k j k K j J k k K x r v a b c λ µ λ λ µ ∈ ∈ ∈  + =  − = −   ≥  ∑ ∑ ∑ Ta có thể viết tập nghiệm của hệ (1.18) dưới dạng : , 0x A b λ λ µ µ      = ≥          , trong đó 1 2 1 2... ... , 11 1 ... 0 0 ... vx x r r A b     = =   −− −    . Theo bổ đề Farkas, tồn tại 1( , ) ny t +∈ sao cho 0T y A t   ≤    và 0T y b t   >    . Điều này tương đương với: , 0 , (1.19 ) , 0 , (1.19 ) , 0 (1.19 ) k j y x t k K a y r j J b y v t c  − ≤ ∀ ∈  ≤ ∀ ∈  − > . Xét bài toán quy hoạch tuyến tính max{ , : } (1.20)y x x P ∈ . Do rank A n= nên P là tập lồi đa diện có ít nhất một điểm cực biên. Khi đó, nếu (1.20) có nghiệm tối ưu, thì tồn tại nghiệm tối ưu của (1.20) cũng là điểm cực biên của P . Nhưng , ky x t ≤ và ,y v t > với \v P Q∈ , mâu thuẫn. 21 Nếu (1.20) không bị chặn, thì theo định lý 1.3.8, tồn tại tia cực biên jr sao cho , 0jy r > , mâu thuẫn với (1.19b).  Nhận xét: Ta có thể biểu diễn một tập lồi đa diện theo các điểm cực biên và tia cực biên của nó. Nếu tập lồi đa diện P có ít nhất một điểm cực biên là tập lồi đa diện hữu tỉ. Theo định lý 1.3.2 mỗi điểm cực biên của P là 0-diện của P . Theo định lý Hoffmann – Kruskal, mỗi điểm cực biên { }x là nghiệm duy nhất của hệ phương trình I IA x b= . Vì các số hạng trong ma trận A và các thành phần của vectơ b đều là số hữu tỉ nên mỗi điểm cực biên cũng có thành phần là hữu tỉ (vì áp dụng phép biến đổi Gaussian để giải hệ phương trình I IA x b= cho ta nghiệm hữu tỉ). Tương tự, theo định lý 1.3.7 một tia cực biên được xác định bởi hệ phương trình 0IA r = , trong đó 1rank A n= − . Do đó, r cũng có thành phần là hữu tỉ. Do đó, ta có mệnh đề sau: Mệnh đề 1.3.10. Điểm cực biên và tia cực biên của tập lồi đa diện hữu tỉ là những vectơ có các thành phần là các số hữu tỉ. 22 Chương 2 Thuật toán nhánh – cận giải bài toán quy hoạch tuyến tính nguyên bộ phận 2.1. Bài toán quy hoạch tuyến tính nguyên bộ phận (Mixed Integer Linear Programming). Định nghĩa 2.1.1. Một bài toán quy hoạch tuyến tính nguyên được viết dưới dạng: ( , ) ( ) ( ) min{ , , : ( , ) } x y MIP Z X c x d y x y X= + ∈ với ,n pc d∈ ∈  , {( , ) : }n pX x y Ax By b+ += ∈ × + ≤  trong đó, A là ma trận cấp ( )m n× . B là ma trận cấp ( )m p× . { : 0}x x+ = ∈ ≥  . { : 0}y y+ = ∈ ≥  . mb∈ . Nhận xét: Trong bài toán trên ta thấy có biến lấy giá trị là số thực tùy ý, có biến lấy giá trị trong tập số nguyên. Đôi khi người ta còn gọi bài toán (MIP) là bài toán quy hoạch tuyến tính nguyên bộ phận. Một trường hợp đặc biệt là: 0 , 0c A= = nghĩa là bài toán có dạng: ( ) min{ , : }Z X d y x X= ∈ với { : }pX y By b+= ∈ ≤ . 23 Ta gọi bài toán Quy hoạch nguyên trong trường hợp này là Quy hoạch nguyên toàn phần. Định nghĩa 2.1.2. Bài toán quy hoạch tuyến tính nguyên bộ phận được định nghĩa như định nghĩa 2.1.1 nhưng trong đó y chỉ nhận hai giá trị 0;1 được gọi là bài toán quy hoạch tuyến tính nguyên nhị phân bộ phận (MBP). Điều này có nghĩa là tập nghiệm chấp nhận được của MBP được định nghĩa: {( , ) {0,1} : }n pX x y Ax By b+= ∈ × + ≤ . Định nghĩa 2.1.3. Bài toán quy hoạch tuyến tính nới lỏng (LR) của ( , ) ( ) ( ) min{ , , : ( , ) } x y MIP Z X c x d y x y X= + ∈ là bài toán quy hoạch tuyến tính được định nghĩa: ( , ) ( ) ( ) min{ , , : ( , ) }X Xx yLR Z P c x d y x y P= + ∈ trong đó, {( , ) : }n pXP x y Ax By b+ += ∈ × + ≤  . Rõ ràng, ( )n pXX P= ∩ ×  (tức là XP X⊇ ) Do đó, ta có mệnh đề sau: Mệnh đề 2.1.4. Cho bài toán quy hoạch tuyến tính nguyên bộ phận MIP với hàm mục tiêu min . Khi đó, Bài toán quy hoạch tuyến tính nới lỏng xác định cho ta cận dưới của giá trị tối ưu ( ( ) ( )XZ P Z X≤ ). Cận trên của giá trị mục tiêu tối ưu là giá trị mục tiêu của một nghiệm chấp nhận được . Ta có mệnh đề sau: Mệnh đề 2.1.5. Bài toán MIP với hàm mục tiêu min ( , ) ( ) ( ) min{ , , : ( , ) } x y MIP Z X c x d y x y X= + ∈ . Khi đó, ( )Z X Z≤ trong đó Z là giá trị mục tiêu của một nghiệm chấp nhận được. Những cận trên, cận dưới này góp phần quan trọng trong việc giải bài toán MIP bằng phương pháp nhánh cận. Điều này sẽ được thấy rõ ở mục 2.2. Để minh họa cho bài toán quy hoạch tuyến tính nguyên bộ phận ta xét ví dụ sau: 24 1 2 1 2( ) min{ 2 : ( , ) } (2.1)yZ X y y y y y X= − − = ∈ trong đó, 2 1 2{ ( , ) : }X y y y By b+= = ∈ ≥ với 1 0 1 0 1 0.8 1 0.8 1 8 B    −   = − −   −   − −  và 1 5 5.8 0.2 26 b    −   = −      −  . Theo định nghĩa 1.1, ta có 0, 5, 2, ( 1, 2)n A c m p d= = = = = = − − .  Bài toán thực tế dẫn đến Quy hoạch nguyên bộ phận: Vấn đề thực tiễn dẫn đến quy hoạch tuyến tính nguyên: Bài toán (Bài toán xếp hàng lên tàu): Hình 1. Miền nghiệm chấp nhận X được của bài toán (2.1) và miền nghiệm chấp nhận được XP của bài toán nới lỏng của nó. 25 Một tàu chở hàng có trọng tải T và thể tích K, tàu chở n loại hàng, hàng loai j có số lượng sj. Mỗi đơn vị hàng loại j có trọng lượng là aj, thể tích bj và giá trị sử dụng là cj. Bài toán đặt ra là cần xác định xj (j=1,,n) là số lượng hàng loại j cần xếp lên tàu sao cho tổng giá trị hàng hóa trên tàu là lớn nhất. Dạng toán học của bài toán: 1 , max, n j j j c x = →∑ với hệ ràng buộc là: 1 1 {0,1,2,..., }, 1,2,..., n j j j n j j j j j a x T b x K x s j n = =  ≤   ≤   ∈ =   ∑ ∑ 2.2. Thuật toán nhánh – cận giải bài toán quy hoạch tuyến tính nguyên bộ phận 2.2.1. Cơ sở lý luận của thuật toán Cho bài toán quy hoạch tuyến tính nguyên bộ phận ( , ) ( ) ( ) min{ , , : ( , ) } x y MIP Z X c x d y x y X= + ∈ trong đó {( , ) : }n pX x y Ax By b+ += ∈ × + ≤  với 1,..., 1,..., 1,..., 1,..., 1 [ ] , , , . [ ] , , , . ( ,..., ) , , 1,..., . ij i m ij j n ij i m ij j p m i A a a i j B b b i j b b b b i m = = = = = ∈ ∀ ∀ = ∈ ∀ ∀ = ∈ =    Ta có bài toán quy hoạch tuyến tính nới lỏng tương ứng là 26 ( , ) ( ) ( ) min{ , , : ( , ) }X Xx yLR Z P c x d y x y P= + ∈ trong đó {( , ) : }n pXP x y Ax By b+ += ∈ × + ≤  . Ta nhắc lại mệnh đề cơ bản về cận dưới và cận trên là: ( ) ( )XZ P Z X Z≤ ≤ trong đó Z là giá trị mục tiêu tại phương án chấp nhận được đã biết. Địnhl lý 2.2.1. Nếu bài toán quy hoạch tuyến tính nới lỏng (LR) không có nghiệm thì bài toán (MIP) hoặc là có hàm mục tiêu không bị chặn dưới trên tập các phương án chấp nhận được hoặc là không có phương án chấp nhận được. Chứng minh TH1: Nếu XP = ∅ thì n p XX P= ∩ × =∅  . Suy ra bài toán (MIP) không có phương án chấp nhận được. TH2: Nếu XP ≠ ∅ Do bài toán nới lỏng (LR) có hàm mục tiêu không bị chặn dưới trên tập phương án chấp nhận được XP nên theo định lý 1.3.8 tồn tại tia cực biên ( , )x yr r của XP sao cho , , 0x yc r d r + < . Do XP là tập lồi đa diện hữu tỉ nên không mất tính tổng quát ta giả sử ( , )x yr r có thành phần đều là số nguyên. Ta xét các trường hợp sau:  Nếu n pXX P= ∩ × =∅  thì bài toán (MIP) không có phương án chấp nhận được.  Nếu n pXX P= ∩ × ≠ ∅  . Ta có ( , )x yr r là tia cực biên của XP . Khi đó, với mỗi 0 0( , )x y X∈ ta có 0 0( , ) ( , ) , 0x y Xx y r r Pµ µ+ ∈ ∀ ≥ , suy ra 0 0( , ) ( , ) ,x yx y r r Xµ µ+ ∈ ∀ ∈ . Và ta có 0 0 0 0 0 0 0 , , ( , , ) ( , , ) , , . x y x y c x r d y r c x d y c r d r c x d y µ µ µ < + = = + + + +  27 Do đó, bài toán (MIP) có hàm mục tiêu không bị chặn dưới.  Nhận xét: Từ định lý 2.2.1 ta chỉ cần giả thiết bài toán LR là có hàm mục tiêu là bị chặn dưới trên tập phương án chấp nhận được XP (tức là ( )XZ P > −∞ ). Ngược lại, nếu bài toán LR không có nghiệm thì bài toán MIP có hàm mục tiêu không bị chặn trên tập phương án hoặc không có phương án chấp nhận được. Để phân biệt hai trường hợp này , ta cho các biến những biên đủ lớn để đạt được bài toán MIP và chạy thuật toán nhánh – cận trên bài toán cải biên này. Nếu nó có nghiệm tối ưu thì bài toán ban đầu có hàm mục tiêu không bị chặn dưới, ngược lại là không có phương án chấp nhận được. Phương pháp nhánh – cận được trình bày từ (i) đến (v) như sau: (i) Cận dưới lúc đầu của ( )Z X là giá trị tối ưu ( )XZ P của bài toán quy hoạch tuyến tính nới lỏng LR. Đặt ( *, *)x y là nghiệm tối ưu của LR. - Nhận xét: Giải bài toán MIP có thể xem như tìm nghiệm tốt nhất ( , )x y trên XP với py∈ .  Quy tắc: Ta giải bài toán MIP bằng cách giải một dãy các bài toán quy hoạch tuyến tính. (ii) Nếu * py ∈ thì ( *, *)x y X∈ là nghiệm chấp nhận được của MIP và nó cũng là cận dưới của ( )Z X . Do đó ( *, *)x y là một nghiệm tối ưu của bài toán MIP. Vì , * , * ( ) ( ) , * , * .Xc x d y Z P Z X Z c x d y + = ≤ ≤ = + (iii) Ngược lại, * py ∉ và ( *, *)x y không là nghiệm chấp nhận được của MIP. Ta cố gắng loại bỏ nghiệm này ra khỏi XP bằng cách thêm vào những ràng buộc tuyến tính. Ta được các bài toán quy hoạch tuyến tính mới. Đặt jy với {1,..., }j p∈ là biến ứng với thành phần không nguyên * jy của nghiệm ( *, *)x y của LR. 28 - Nhận xét: ( , )x y X∈ tùy ý, ta có *j jy y ≤   hoặc * 1j jy y ≥ +  trong đó * jy   là phần nguyên của * jy .  Bước phân nhánh: Để loại bỏ nghiệm ( *, *)x y cùng với những nghiệm thỏa * * 1j j jy y y   < < +    , ta thay thế tập XP bởi hai tập rời nhau 0 XP và 1 XP trong đó 0 *{( , ) : }n pX X j jP P x y y y+ +  = ∩ ∈ × ≤    1 *{( , ) : 1}n pX X j jP P x y y y+ +  = ∩ ∈ × ≥ +   - Nhận xét: Bây giờ ta có thể thay việc tìm nghiệm tốt nhất trên XP bằng việc tìm nghiệm tốt nhất trên 0 1X XP P∪ . Khó khăn ở chỗ là tăng số lượng bài toán lên từ 1 bài toán thành 2 bài toán quy hoạch tuyến tính lần lượt được xác định trên 0XP và 1XP . Ví dụ: Theo bài toán (2.1) trong ví dụ ở trên, ta có 32 101, 9 36 a  =     là nghiệm tối ưu ( *, *)x y của bài toán quy hoạch tuyến tính nới lỏng (LR), và hai miền phân hoạch 0XP và 1 XP được thể hiện trong hình vẽ sau: (iv) Bây giờ ta tìm nghiệm nguyên tốt nhất nằm trong một trong những tập Hình 2. Miền phân hoạch của bài toán quy hoạch (2.1) trong thuật toán nhánh – cận. 29 lồi đa diện 0 1{ , }X XL P P= bằng cách tương tự như trên XP .  Bước lặp: Ta tìm được danh sách L các tập lồi đa diện và giá trị mục tiêu Z của phương án tốt nhất tìm được. Z được gọi là giá trị kỉ lục và phương án tốt nhất tìm được gọi là một kỉ lục. Nếu không có phương án chấp nhận được nào được biết thì : .Z = +∞ - Chọn và giải nghiệm: Ta lấy một tập lồi đa diện V bất kỳ từ danh sách L và giải bài toán quy hoạch tuyến tính tương ứng tìm được nghiệm tối ưu ( , )V Vx y và giá trị tối ưu ( )Z V . - Cắt giảm: Một số khả năng có thề xảy ra sau: a) Nếu ( )Z V Z≥ thì nghiệm nguyên tốt nhất không thể nhỏ hơn Z , vì ( )Z V là cận dưới của tập giá trị mục tiêu của những nghiệm nguyên trong V . Do đó ta không cần quan tâm đến những nghiệm nguyên trong V nữa và loại V ra khỏi danh sách L . Đây gọi là cắt giảm bởi cận . b) V = ∅ , ta có ( )Z V Z= +∞ ≥ và ta loại V ra khỏi danh sách L . Đây gọi là cắt giảm bởi sự không chấp nhận được. c) Nếu ( )Z V Z< và V py ∈ , thì ( , )V Vx y là nghiệm nguyên tốt nhất trong V . Ta lưu lại giá trị kỉ lục ( )Z Z V= và loại V ra khỏi danh sách L . Đây gọi là cắt giảm bởi sự nguyên hóa. d) Nếu ( )Z V Z< và V py ∉ thì giá trị mục tiêu của nghiệm nguyên tốt nhất trong V vẫn có thể tốt hơn Z . Ta loại V ra khỏi danh sách L và thêm vào V hai tập 0V và 1V đạt được bằng cách phân nhánh được miêu tả ở trên. Đây gọi là sự phân nhánh. (v) Kết thúc: Thuật toán kết thúc khi danh sách L = ∅ . Điều này được đảm bảo xảy ra sau hữu hạn bước, nếu những biến nguyên y là bị chặn. Điều này được thể hiện rõ qua định lý sau. 30 Định lí 2.2.2. Nếu mọi điểm của tập phương án chấp nhận được XP của bài toán quy hoạch tuyến tính nới lỏng có thành phần biến nguyên y bị chặn thì thuật toán sẽ kết thúc sau một số hữu hạn các bước. Chứng minh. Giả sử thuật toán có vô hạn bước . Vậy trong thuật toán sẽ tồn tại dãy vô hạn các tập 1{ } r X rP ≥ bị tách sao cho 1r XP + nhận được từ rXP sau một số bước lặp nào đó. Vì một điểm của tập phương án chấp nhận được XP chỉ có hữu hạn thành phần biến nguyên nên không giảm tính tổng quát ta giả sử rXP bị chia tách do thành phần thứ nhất không nguyên với mọi 1r ≥ . Đặt 1 1( , ) ( ,..., , ,..., ) r r r r r X X X X XP P P P P n px y x x y y= là phương án tối ưu của bài toán quy hoạch tuyến tính nới lỏng trên rXP . Do các điểm của XP có thành phần nguyên y bị chặn nên tồn tại 1 1,a b ∈ sao cho 1 1 1 1[ , ]y A a b∈ =