Luận văn Quy hoạch nguyên với mô hình tuyến tính bất kỳ

tiểu từ vựng của các vectơ 1,..., kx x nếu s l ix x≤ với mọi 1,i k∈ . Kí hiệu { }min : 1,s ix lex x i k= = . 3.2.2. Các tính chất cơ bản + Nếu lx x′≤ và ly y′< thì lx y x y′ ′+ < + . + Nếu 0lx và 0lax > nếu 0a < . 3.2.3. Tối ưu theo nghĩa từ vựng + Phương án ( )1,.... nu u u= của ( )P gọi là phương án tối ưu từ vựng nếu với mọi phương án ( )1,.... nx x x= của ( )P , ta có ( ) ( )1 1, , ,..., , , ,...,n l nc u u u c x x x≥ . + ( )1, , ,..., nc x x x được gọi là phương án mở rộng ứng với phương án ( )1,.... nx x của ( )P . Nhận xét: + Phương án tối ưu từ vựng là phương án tối ưu. + Phương án tối ưu từ vựng nếu có thì là duy nhất. Định lý 3.1: ( )P có phương án tối ưu từ vựng khi và chỉ khi tập các phương án tối ưu của ( )P khác rỗng và bị chặn. Chứng minh: )⇐ Đặt 0x là giá trị tối ưu của ( )P . Khi đó tập các phương án tối ưu của ( )P { }0: ,nD D x c x x= ∈ =  cũng là tập lồi đa diện và bị chặn. Đặt ( )1,iu i k= là các điểm cực biên của D .Vậy theo định lý 1.11, với mỗi x D∈ tồn tại 1 2 1 , ,..., 1, 0, 1, k k i i i i kλ λ λ λ λ =   = ≥ ∀ =    ∑ sao cho 1 1 2 2 ... k kx u u uλ λ λ= + + + Đặt { }0 max : 1,iu lex u i k= = .Ta có 1 1 2 2 1 0 2 0 0 0... ...k k l kx u u u u u u uλ λ λ λ λ λ= + + + ≤ + + + = . Vậy ( )P có phương án tối ưu từ vựng là 0u . )⇒ Giả sử ( )P có phương án tối ưu từ vựng 0u và tập các phương án tối ưu của ( )P – D không bị chặn. Vì phương án tối ưu từ vựng cũng là phương án tối ưu nên 0u D∈ . D là tập lồi đa diện không bị chặn nên có phương vô tận v . Vì các thành phần của một phương án của D là không âm nên 0v ≥ và 0v ≠ . Vậy 0lv > . Đặt 1 0u u v= + . Ta có 1u D∈ và 1 0lu u> . Điều này mâu thuẫn với 0u là phương án tối ưu từ vựng của ( )P . Vậy tập các phương án tối ưu của ( )P khác rỗng và bị chặn. Định lý 3.2: Phương án tối ưu từ vựng của ( )P (nếu có) là phương án cực biên của ( )P . Chứng minh: Giả sử ngược lại ( )P có phương án tối ưu từ vựng x và x không phải là điểm cực biên của D . Khi đó tồn tại , ,y z D y z∈ ≠ và ( )0;1λ∈ sao cho (1 )x y zλ λ= + − Không mất tính tổng quát ta giả sử ly z< . Khi đó, ta có (1 ) (1 )lx y z z z zλ λ λ λ= + − < + − = . Điều này mâu thuẫn với x là phương án tối ưu từ vựng của ( )P . Vậy phương án tối ưu từ vựng của ( )P (nếu có) là phương án cực biên của ( )P . 3.3. Bảng đơn hình l-chuẩn Bảng đơn hình { } { }0,... , 0ij i n j N T x ∈ ∈ ∪  =   gọi là l-chuẩn nếu 0 0 j j l nj x R x     = >       với mọi j N∈ . Nhận xét: Nếu T là l-chuẩn thì T là chuẩn. Định lý 3.3: ( )P có phương án tối ưu từ vựng khi và chỉ khi tồn tại cơ sở sao cho bảng đơn hình ứng với cơ sở đó là l-chuẩn và chấp nhận được. Chứng minh: )⇐ Giả sử ta có bảng đơn hình T ứng với B là l-chuẩn và chấp nhận được. Biểu diễn hàm mục tiêu và các biến qua các biến phi cơ sở: ( ) 000 101 0 j j j N n n xx xx R x x x ∈          = + −           ∑   . Do T là chấp nhận được nên 0j lR > với mọi j N∈ . Ta có ( ) 00 000 10 101 0 0 j j l j N n n n x xx x xx R x x x x ∈                = + − ≤                 ∑    . Vậy ( )10 0,..., nx x là phương án tối ưu từ vựng của ( )P . )⇒ Giả sử ( )P có phương án tối ưu từ vựng x . Theo định lý, x cũng là phương án cực biên tức là phương án cơ sở. Ta chứng minh cho trường hợp x là phương án cơ sở không thoái hóa nghĩa là 0x > . Xét T là bảng đơn hình ứng với x . T là chấp nhận được vì x là phương án cơ sở. Ta chứng minh T cũng là l-chuẩn. Giả sử ngược lại tồn tại l N∈ sao cho 0l lR vì nếu ngược lại thì hàm mục tiêu không bị chặn trên, mâu thuẫn với ( )P có phương án tối ưu [3, tr.28-29]. Thực hiện phép biến đổi cơ bản của bảng đơn hình : đưa lx vào tập các biến cơ sở, đưa kx ra theo tiêu chuẩn 0 0min : 1, , 0k i il kl il x x i n x x x   = = >    (cách chọn k đảm bảo bảng đơn hình mới vẫn là chuẩn). Ta có 00 0 0k l l kl xR R R R x ′ = − > vì 0 , 0, 0k kl l lx x R> < . Điều này mâu thuẫn với x là phương án tối ưu từ vựng của ( )P . 3.4. Thuật toán đơn hình đối ngẫu từ vựng tìm phương án tối ưu từ vựng + Trường hợp bảng đơn hình xuất phát là l-chuẩn: Ý tưởng của thuật toán: Bắt đầu từ một cơ sở mà bảng đơn hình tương ứng là l-chuẩn, nếu bảng đơn hình chưa là chấp nhận được thì ta tiến hành dịch chuyển sang cơ sở mới mà bảng đơn hình ứng với cơ sở mới cũng là l-chuẩn cho đến khi gặp bảng đơn hình là chấp nhận được thì dừng. Khi đó phương án cơ sở ứng với bảng đơn hình cuối là phương án tối ưu từ vựng. Thuật toán: Giả sử tồn tại cơ sở B sao cho bảng đơn hình T ứng với B là l-chuẩn. Bước 1 Nếu T là chấp nhận được thì phương án cơ sở ứng với B là phương án tối ưu từ vựng. Thuật toán kết thúc. Ngược lại, ta chuyển sang bước 2. Bước 2 Nếu tồn tại 1,i n∈ sao cho 0 0ix < và 0,ijx j N≥ ∀ ∈ thì ( )P không có phương án ( vì ( )0 0i i ij j j N x x x x ∈ = + − <∑ ). Vậy ( )P không có phương án tối ưu từ vựng. Thuật toán kết thúc. Ngược lại: + Đặt { }0min : 0ik i x= < . + Chọn l thỏa min : , 0jl kj kl kj RR lex j N x x x   = ∈ <     . + Thực hiện phép biến đổi cơ bản của bảng đơn hình : đưa kx ra khỏi tập các biến cơ sở, đưa lx vào . Quay trở lại bước 1. Nhận xét: Nếu bảng đơn hình xuất phát là l-chuẩn thì chỉ có hai khả năng có thể xảy ra: + ( )P không có phương án. + ( )P có phương án tối ưu từ vựng. Định lý 3.4: Khi sử dụng thuật toán đơn hình đối ngẫu từ vựng thì các bảng đơn hình đều là l- chuẩn. Chứng minh: Với cách chọn dòng và cột xoay như trong thuật toán đơn hình đối ngẫu thì nếu bảng đơn hình trước là l-chuẩn thì bảng đơn hình sau cũng là l- chuẩn. Thật vậy, thực hiện phép biến đổi cơ bản của bảng đơn hình : đưa kx ra khỏi tập các biến cơ sở, đưa lx vào. Ta có bảng đơn hình mới được tính lại theo công thức { }( ) { }, 0 \ l k kl kj j j l kl RR x x R R R j N l x  ′ = −    ′ = − ∈ ∪  Giả sử bảng đơn hình trước là l-chuẩn tức là 0j lR > với mọi j N∈ . Vì l thỏa min : , 0jl kj kl kj RR lex j N x x x   = ∈ <     nên 0klx < . Do đó 0lk l kl RR x ′ = − > . Nếu 0kjx ≥ thì 0 0 0 kj j j l l kl x R R R x ′ = − > + = . Ngược lại, nếu 0kjx < thì 0 kj j l j j l kj l kl klkj x R RR R R x x xx   ′  = − = − >     ( vì l thỏa min : , 0jl kj kl kj RR lex j N x x x   = ∈ <     và cách chọn l là duy nhất ). Vậy bảng đơn hình sau cũng là l-chuẩn tức là 0j lR′ > với mọi j N ′∈ . Mặt khác, bảng đơn hình xuất phát là l-chuẩn. Vậy khi sử dụng thuật toán đơn hình đối ngẫu từ vựng thì các bảng đơn hình đều là l-chuẩn. Định lý 3.5: Khi sử dụng thuật toán đơn hình đối ngẫu từ vựng thì dãy cột đầu tiên của bảng đơn hình là giảm từ vựng. Chứng minh: Ta có 00 0 0k l l kl xR R R R x ′ = − . Cơ sở lí luận của thuật toán: Do định lý 3.5 ta sẽ tránh được hiện tượng xoay vòng tức là thuật toán lại quay trở về một cơ sở mà trước đó đã xét qua và vì ( )P chỉ có hữu hạn các cơ sở nên thuật toán sẽ dừng sau một số hữu hạn các bước lặp. + Trường hợp bảng đơn hình xuất phát không là l-chuẩn: Ý tưởng: Bắt đầu từ một bảng đơn hình không là l-chuẩn, ta thêm vào một ràng buộc giả tạo được bảng đơn hình mới. Sau đó chuyển đổi bảng đơn hình này thành l-chuẩn và từ đó áp dụng thuật toán đơn hình đối ngẫu từ vựng cho cho bảng đơn hình này. Sử dụng kết quả của bài toán mới để đưa ra kết quả cho bài toán ban đầu. Thuật toán: Giả sử ( )P có cơ sở B mà bảng đơn hình tương ứng không là l-chuẩn. Ta thêm ràng buộc giả tạo vào bài toán: j j N x M ∈ ≤∑ . Đặt biến phụ 1 0nx + ≥ với hệ số hàm mục tiêu bằng 0 , chuyển ràng buộc về dạng đẳng thức ( )1n j j N x M x+ ∈ = + −∑ . Viết dòng trên vào cuối bảng đơn hình ta thu được bảng đơn hình mới ứng với bài toán mở rộng ( )MP . ( )MP có cơ sở là { }1B n + . Thực hiện phép biến đổi cơ bản của bảng đơn hình: đưa 1nx + ra khỏi tập các biến cơ sở, đưa lx vào theo quy tắc từ vựng: { }min :l jR lex R j N= ∈ . Khi đó, ta nhận được bảng đơn hình mới là l-chuẩn. Thật vậy, theo công thức biến đổi bảng đơn hình ta có { }( ) { } 1 , 0 \ n l j j l R R R R R j N l +′ = −  ′ = − ∈ ∪ . Vì bảng đơn hình xuất phát không là l-chuẩn và { }min :l jR lex R j N= ∈ nên 0l lR . Vì { }min :l jR lex R j N= ∈ và cách xác định l là duy nhất nên { }( ) { }0, 0 \j j l lR R R j N l′ = − > ∀ ∈ ∪ . Từ bảng đơn hình l-chuẩn này ta có thể tiến hành thuật toán đơn hình đối ngẫu từ vựng cho bài toán mở rộng ( )MP . Chú ý rằng trong quá trình tiến hành thuật toán ta luôn xem M là số lớn hơn bất kì số nào cần so sánh với nó và chỉ có cột đầu tiên phụ thuộc vào M . Thuật toán sẽ dừng ở một trong những trường hợp sau: + ( )MP không có phương án thì ( )P không có phương án. Vậy ( )P không có phương án tối ưu từ vựng. + ( )MP có phương án tối ưu từ vựng Mx . Ta kiểm tra - Nếu giá trị tối ưu của ( )MP phụ thuộc vào M thì ( )P không có phương án tối ưu. Vậy ( )P không có phương án tối ưu từ vựng. - Nếu giá trị tối ưu của ( )MP không phụ thuộc vào M (là hằng số). Xét Mx′ nhận được từ Mx bằng cách loại bỏ thành phần thứ 1n + ( bỏ biến phụ 1nx + ). Ta kiểm tra: * Nếu Mx′ phụ thuộc vào M thì ( )P có tập các phương án tối ưu không bị chặn.Vậy ( )P không có phương án tối ưu từ vựng. * Nếu Mx′ không phụ thuộc vào M thì Mx′ là phương án tối ưu từ vựng của ( )P . Xóa bỏ dòng cuối (dòng chứa biến phụ 1nx + ) ta nhận được bảng đơn hình là l-chuẩn và chấp nhận được ứng với Mx′ của ( )P . Chú ý : Kiểm tra giá trị tối ưu của ( )MP và Mx′ tức là kiểm tra cột đầu tiên của bảng đơn hình bỏ đi thành phần cuối. Cơ sở lí luận của thuật toán: Định lý 3.6: Nếu ( )P có phương án thì tồn tại 0M sao cho với mọi 0M M≥ ta có ( )MP có phương án. Chứng minh: Giả sử ( )P có phương án ( )1 ,..., nx x x∗ ∗ ∗= . Chọn 0M sao cho 0j j N x M∗ ∈ ≤∑ . Với 0M M≥ , đặt ( )1 1,..., ,M n nx x x x∗ ∗ ∗ ∗+= trong đó ( )1n j j N x M x∗ ∗+ ∈ = + −∑ . Khi ấy ( )MP có phương án Mx ∗ với mọi 0M M≥ . Định lý 3.7: Nếu ( )P có phương án tối ưu thì tồn tại 0M sao cho với mọi 0M M≥ ta có ( )MP có giá trị tối ưu không phụ thuộc vào M (là hằng số). Chứng minh: Giả sử ( )P có phương án tối ưu ( )1 ,..., nx x x∗ ∗ ∗= . Chọn 0M sao cho 0j j N x M∗ ∈ ≤∑ . Với 0M M≥ , đặt ( )1 1,..., ,M n nx x x x∗ ∗ ∗ ∗+= trong đó ( )1n j j N x M x∗ ∗+ ∈ = + −∑ . Khi ấy Mx∗ phương án tối ưu của ( )MP với mọi 0M M≥ . Thậy vậy, xét ( )1 1,..., ,n nx x x + là phương án của ( )MP thì ( )1,..., nx x x= là phương án của ( )P . Do ( )1 ,..., nx x x∗ ∗ ∗= là phương án tối ưu của ( )P nên , ,c x c x∗≤ . Tức là giá trị hàm mục tiêu của ( )MP tại phương án ( )1 1,..., ,n nx x x + không lớn hơn tại Mx∗ .Vậy nếu 0M M≥ thì ( )1 1,..., ,M n nx x x x∗ ∗ ∗ ∗+= là phương án nên là phương án tối ưu của ( )MP và giá trị tối ưu của ( )MP là ,c x∗ ( giá trị tối ưu của ( )P ) không phụ thuộc vào M . Giả sử ( )MP có phương án tối ưu từ vựng Mx và giá trị tối ưu không phụ thuộc vào M . Xét Mx′ nhận được từ Mx bằng cách loại bỏ thành phần thứ 1n + ( bỏ biến phụ 1nx + ). Khi ấy ta có hai kết quả sau: Định lý 3.8: Nếu Mx′ phụ thuộc vào M thì tập các phương án tối ưu của ( )P không bị chặn. Chứng minh: Ta có Mx có dạng Mα β+ trong đó 1, , 0nα β β+∈ > . Chọn 0M sao cho 0 0 0Mx Mα β= + ≥ . Khi ấy 0Mx Mα β= + ≥ với mọi 0M M≥ . Do đó Mx′ là phương án của ( )P với mọi 0M M≥ . Ta có Mx′ có dạng Mα β′ ′+ trong đó ,α β′ ′ nhận được từ ,α β bằng cách bỏ đi thành phần cuối .Vì Mx′ phụ thuộc vào M nên 0β ′ > . Đặt 0x là giá trị tối ưu của ( )MP . Ta chứng minh ( )P cũng có giá trị tối ưu là 0x . Thật vậy, xét ( )1,..., nx x là phương án của ( )P . Chọn M sao cho j j N x M ∈ ≤∑ . Đặt ( )1 1,..., ,M n nx x x x += trong đó ( )1n j j N x M x+ ∈ = + −∑ . Khi ấy ( )MP có phương án Mx . Vì 0x là giá trị tối ưu của ( )MP nên giá trị hàm mục tiêu của ( )MP tại Mx : 0,c x x≤ . Vậy ( )P cũng có giá trị tối ưu là 0x và tập các phương án tối ưu của ( )P chứa { }0:Mx M M′ ≥ . Mà { } { }0 0: :Mx M M M M Mα β′ ′ ′≥ = + ≥ với 0β ′ > là tập không bị chặn. Vậy tập các phương án tối ưu của ( )P không bị chặn. Định lý 3.9: Nếu Mx′ không phụ thuộc vào M thì Mx′ là phương án tối ưu từ vựng của ( )P . Xóa bỏ dòng cuối (dòng chứa biến phụ 1nx + ) ta sẽ nhận được bảng đơn hình là l-chuẩn và chấp nhận được ứng với Mx′ của ( )P . Chứng minh: Giả sử Mx′ không phụ thuộc vào M . Khi ấy 1nx + phải là biến cơ sở. Thật vậy, giả sử ngược lại 1nx + là biến phi cơ sở thì do Mx′ không phụ thuộc vào M nên 1nx + không phụ thuộc vào M . Điều này mâu thuẫn với ( )1n j j N x M x+ ∈ = + −∑ . Do bảng đơn hình cuối là l-chuẩn và chấp nhận được nên khi ta xóa bỏ dòng cuối (dòng chứa biến phụ 1nx + ) ta vẫn sẽ nhận được bảng đơn hình là l-chuẩn và chấp nhận được và do 1nx + là biến cơ sở nên bảng đơn hình mới không chứa biến 1nx + . Vậy ta có bảng đơn hình là l-chuẩn và chấp nhận được ứng với Mx′ của ( )P . Nhận xét: Nếu bảng đơn hình xuất phát không là l-chuẩn thì có các khả năng có thể xảy ra khi tiến hành thuật toán: + ( )P không có phương án. + ( )P có phương án nhưng không có phương án tối ưu. + ( )P có tập các phương án tối ưu không bị chặn. + ( )P có phương án tối ưu từ vựng. Ví dụ 3.10: Tìm phương án tối ưu từ vựng của bài toán quy hoạch tuyến tính 1 2 1 2 3 1 2 4 2 min 2 3 7 3 0, 1, 4i x x x x x x x x x i + →  + − =  + + =  ≥ ∀ = Viết lại bài toán dưới dạng 0 1 2 3 1 2 4 1 2 2 max 7 2 3 3 0, 1, 4i x x x x x x x x x x i = − − →  = − + +  = − −  ≥ ∀ = Khi ấy ta có bảng đơn hình xuất phát là l-chuẩn 1x− 2x− 0x 0 1 2 1x 0 -1 0 2x 0 0 -1 3x -7 -2 -3 4x 3 1 1 Đưa 3x ra khỏi tập các biến cơ sở, đưa vào 1x 3x− 2x− 0x 7 2 − 1 2 1 2 1x 7 2 1 2 − 3 2 2x 0 0 -1 3x 0 -1 0 4x 1 2 − 1 2 1 2 − Đưa 4x ra khỏi tập các biến cơ sở, đưa vào 2x ` 4x− 2x− 0x -4 1 1 1x 2 1 3 2x 1 -1 -2 3x 0 -1 0 4x 0 0 -1 Bảng đơn hình cuối là l-chuẩn và chấp nhận được. Ta nhận được phương án tối ưu từ vựng của bài toán ( )2,1x∗ = . Ví dụ 3.11: Tìm phương án tối ưu từ vựng của bài toán quy hoạch tuyến tính 0 1 2 1 2 3 1 2 4 4 max 2 4 7 10 3 15 0, 1,4i x x x x x x x x x x i = + →  + + =  + + =  ≥ ∀ = Viết lại bài toán dưới dạng 0 1 2 3 1 2 4 1 2 4 max 7 2 4 15 10 3 0, 1,4i x x x x x x x x x x i = + →  = − −  = − −  ≥ ∀ = Khi ấy ta có bảng đơn hình xuất phát 1x− 2x− 0x 0 -1 -4 1x 0 -1 0 2x 0 0 -1 3x 7 2 4 4x 15 10 3 Bảng đơn hình xuất phát không là l-chuẩn. Ta thêm vào ràng buộc giả tạo 1 2 x x M+ ≤ Đặt biến phụ 5 0x ≥ với hệ số hàm mục tiêu bằng 0 , chuyển ràng buộc về dạng đẳng thức 5 1 2 x M x x= − − . Ta có bảng đơn hình mở rộng 1x− 2x− 0x 0 -1 -4 1x 0 -1 0 2x 0 0 -1 3x 7 2 4 4x 15 10 3 5x M 1 1 Đưa 5x ra khỏi tập các biến cơ sở, đưa vào 2x 1x− 5x− 0x 4M 3 4 1x 0 -1 0 2x M 1 1 3x 7 4M− -2 -4 4x 15 3M− 7 -3 5x 0 0 -1 Đưa 3x ra khỏi tập các biến cơ sở, đưa vào 5x 1x− 3x− 0x 7 3 4 1x 0 -1 0 2x 7 4 1 1 3x 0 -2 -4 4x 39 4 7 -3 5x 7 4 M− + 0 -1 Bảng đơn hình trên là l-chuẩn và chấp nhận được và cột đầu tiên của bảng không phụ thuộc vào M (không kể thành phần cuối). Vậy bài toán đã cho có phương án tối ưu từ vựng 7 397,0, ,0, 4 4 x∗  =     . Xóa bỏ dòng cuối (dòng chứa biến phụ 5x ) ta nhận được bảng đơn hình là l-chuẩn và chấp nhận được ứng với phương án tối ưu từ vựng x∗ của bài toán 1x− 3x− 0x 7 3 4 1x 0 -1 0 2x 7 4 1 1 3x 0 -2 -4 4x 39 4 7 -3 1. Lát cắt đúng Giả sử bài toán quy hoạch tuyến tính ( )P có phương án tối ưu là ( )1 ,..., nx x x∗ ∗ ∗= . Khi ấy ràng buộc tuyến tính 1 n i i i a x α = ≤∑ được gọi là một lát cắt đúng của ( )P nếu như nó thỏa hai điều kiện sau: + Ràng buộc tuyến tính cắt bỏ đi phương án tối ưu của ( )P tức là 1 n i i i a x α∗ = >∑ . + Ràng buộc tuyến tính không làm mất đi phương án nguyên nào của ( )P tức là nếu ( )1,..., nx x x= là phương án nguyên của ( )P thì 1 n i i i a x α = ≤∑ . 3.5. Thuật toán cắt Gomory 3.5.1. Điều kiện để sử dụng thuật toán Gomory Để sử dụng thuật toán Gomory ta cần có điều kiện ( )i Tập các phương án tối ưu của ( )P bị chặn và một trong hai điều kiện sau ( )ii Hàm mục tiêu bị chặn dưới trên tập các phương án của ( )P , hoặc ( )iii ( )P có phương án nguyên. Chú ý: + Điều kiện ( )i để tránh rơi vào trường hợp ( )P có phương án tối ưu nhưng không có phương án tối ưu từ vựng. Ở bước đầu tiên trong thuật toán Gomory là sử dụng thuật toán đơn hình đối ngẫu từ vựng để tìm phương án tối ưu từ vựng của ( )P và với điều kiện ( )i thì khi tiến hành thuật toán chỉ có thể xảy ra hai khả năng hoặc ( )P không có phương án tối ưu hoặc ( )P có phương án tối ưu từ vựng. + Điều kiện ( )ii hoặc ( )iii để đảm bảo thuật toán có thể kết thúc sau hữu hạn các bước lặp. + Nếu ( )P có bảng đơn hình xuất phát là l-chuẩn thì điều kiện ( )i được thỏa mãn. + Nếu tập các phương án của ( )P bị chặn thì điều kiện ( )i và ( )ii được thỏa mãn. Khi đó ta có thể tiến hành thuật toán Gomory để giải ( )P′ . 3.5.2. Thuật toán cắt Gomory Ý tưởng: Bước chuẩn bị: Đặt ( ) ( )0P P= . Bước lặp 0,1,...k = Sử dụng thuật toán đơn hình đối ngẫu từ vựng để tìm phương án tối ưu từ vựng của ( )kP . Nếu ( )kP không có phương án tối ưu thì ( )P′ cũng không có phương án tối ưu. Ngược lại, ( )kP có phương án tối ưu từ vựng kx . Nếu kx nguyên thì kx là phương án tối ưu của ( )P′ . Ngược lại bổ sung thêm vào hệ ràng buộc của ( )kP một lát cắt đúng loại bỏ phương án tối ưu kx nhưng không làm mất đi phương án nguyên nào của ( )P . Đặt ( )1kP + là bài toán ( )kP có bổ sung thêm lát cắt đúng. Chuyển sang bước 1k + . Thuật toán: Bước 0: Sử dụng thuật toán đơn hình đối ngẫu từ vựng để tìm phương án tối ưu từ vựng của ( )P . Do điều kiện ( )i nên chỉ có thể xảy ra một trong hai khả năng: + ( )P không có phương án tối ưu. Theo định lý 2.4 thì ( )P′ cũng không có phương án tối ưu. Thuật toán kết thúc. + ( )P có phương án tối ưu từ vựng 0x . Ta kiểm tra: - Nếu 0x là phương án nguyên của ( )P thì 0x là phương án tối ưu của ( )P′ . Thuật toán kết thúc. - Ngược lại, nếu 0x là không phải là phương án nguyên thì kí hiệu 0T là bảng đơn hình ứng với 0x và chuyển sang bước lặp thứ 0r = . Bước lặp thứ ( )0r r ≥ : Đặt rx là phương án cơ sở ứng với bảng đơn hình rT ( rT là l-chuẩn và chấp nhận được). Đặt { }0min : 0, , rik i i n x= = ∉ . Xây dựng lát cắt đúng { }( )( ) { }0 r r r kj j k j N x x x ∈ − − ≥∑ { } [ ]( )x x x= − . Đặt biến phụ 1 0n rx + + ≥ , đưa về dạng đẳng thức { } { }( )( ) ( )1 0 1 r r r n r k kj j j N x x x x+ + ∈ = − + − −∑ Viết dòng ( )1 vào cuối bảng đơn hình. Ta nhận được bảng đơn hình mới vẫn là l- chuẩn và không chấp nhận được (tính chấp nhận được chỉ bị vi phạm đối với 1n rx + + ). Áp dụng thuật toán đơn hình đối ngẫu với bảng đơn hình này, đồng thời sau khi đưa 1n rx + + ra khỏi tập các biến cơ sở thì xóa dòng ( )1 và nếu đưa vào biến phụ ( )1lx l n≥ + thì ta loại bỏ dòng của bảng đơn hình ứng với nó. Nếu cuối cùng nhận được bảng đơn hình ứng với bài toán quy hoạch tuyến tính không có phương án thì ( )P′ không có phương án tối ưu. Thuật toán kết thúc. Ngược lại, nhận được bảng đơn hình l-chuẩn và chấp nhận được 1rT + . Đặt 1rx + là phương án cơ sở ứng với bảng đơn hình 1rT + . Nếu 1rx + có các thành phần nguyên thì 1rx + là phương án tối ưu của ( )P′ . Thuật toán kết thúc. Ngược lại, chuyển sang bước lặp 1r + . Nhận xét: Mỗi khi biến phụ ( )1lx l n≥ + bị đưa vào tập các biến cơ sở, ta loại bỏ dòng chứa nó ( lx không tham gian vào các tính toán tiếp theo). Điều này khiến mở rộng tập ràng buộc của bài toán quy hoạch tuyến tính tương ứng làm giảm hiệu quả của thuật toán nhưng bù lại nó giúp bảng đơn hình khỏi có số dòng không xác định (sau mỗi bước lặp lại có thêm một biến phụ). Như vậy, trong quá trình thực hiện thuật toán Gomory, bảng đơn hình không có quá 2n + dòng và có số cột không thay đổi, 1n m− + cột. 3.5.3. Cơ sở lí luận của thuật toán Định lý 3.12: Giả sử ( )1 ,...,r r rnx x x= là phương án cơ sở ứng với bảng đơn hình rT và Nếu ( )0 0,rkx k n∉ ∈ thì { }( )( ) { }0 r r r kj j k j N x x x ∈ − − ≥∑ ( )∗ là lát cắt đúng của bài toán quy hoạch ứng với rT . Chứng minh: Đặt ( )1 ,...,r r rnx x x= là phương án cơ sở ứng với bảng đơn hình rT . Vì 0rkx ∉ nên { }0 0rkx > . Vì 0rjx = với mọi rj N∈ nên { }( )( ) { }00 r r r r kj j k j N x x x ∈ − − = <∑ . Tức là ( )∗ thỏa điều kiện thứ nhất của một lát cắt đúng. Xét ( )1,..., nx x x′ ′ ′= là phương án nguyên của bài toán quy hoạch ứng với rT và ( )0 1, ..., nx x x′ ′ ′ là phương án mở rộng của x′ thì ( )0 1, ..., nx x x′ ′ ′ có cũng có các thành phần nguyên. Ta có ( ) ( ) { } { }( )0 0 0 r r r r r r r r r k k kj j k kj j k kj j j N j N j N x x x x x x x x x x ∈ ∈ ∈ ′ ′ ′ ′   = + − = + − + + −   ∑ ∑ ∑ . Đặt { } { }( )( )0 r r r k kj j j N z x x x ∈ ′= − + − −∑ . Ta có ( )0 r r r k kj j k j N z x x x x ∈ ′ ′   = + − − ∈   ∑  . Vì { } { }0 1, 0, 0r rk j kjx x x− > − ≥ ≥ nên { } { }( )( )0 1 0 1 r r r r k kj j j N z x x x ∈ = − + − − > − + = −∑ . Vậy 1z > − và z∈ nên 0z ≥ . Tức là ( )∗ thỏa điều kiện thứ hai của một lát cắt đúng. Vậy ( )∗ là lát cắt đúng. Định lý 3.13: Nếu trong quá trình thực hiện thuật toán ta nhận được bảng đơn hình ứng với bài toán quy hoạch tuyến tính không có phương án thì bài toán ( )P′ không có phương án. Chứng minh: Lát cắt đúng không làm mất đi một phương án nguyên nào của ( )P . Vì vậy tập ràng buộc của bài toán quy hoạch tuyến tính ứng với một bảng đơn hình trong quá trình tiến hành thuật toán luôn chứa tất cả các phương án của ( )P′ .Vậy nếu nó không có phương án thì ( )P′ cũng không có phương án. Định lý 3.14: Nếu rx có các thành phần nguyên thì rx là phương án tối ưu của ( )P′ . Chứng minh: Gọi rD là tập ràng buộc của bài toán quy hoạch tuyến tính ứng với bảng đơn hình rT , D′ là tập ràng buộc của ( )P′ . Ta có , , ,r rc x c x x D≥ ∀ ∈ . Vì rD D′ ⊂ nên , , ,rc x c x x D′≥ ∀ ∈ . Vậy , , ,rc x c x x D′≥ ∀ ∈ và rx D′∈ nên rx là phương án tối ưu của ( )P′ . Giả sử ( )1 ,...,r r rnx x x= là phương án cơ sở ứng với bảng đơn hình rT , ( )0 1, ,...,r r r rnx x x x= là phương án mở rộng của rx , ( )0 1, ,...,r r r rny y y y= là giả phương án mở rộng nhận được từ bảng đơn hình rT sau khi đưa 1n rx + + ra khỏi tập các biến cơ sở và xóa dòng ( )1 . Bổ đề 3.15: Ta có 1r r rx y x +> ≥ với mọi r∈ . Chứng minh: Kết quả này là hệ quả của định lý vì khi áp dụng thuật toán đơn hình đối ngẫu từ vựng, dãy cột đầu tiên của bảng đơn hình là giảm từ vựng và 1, ,r r rx y x + nhận được bằng cách chuyển vị cột đầu tiên của bảng đơn hình tương ứng. Bổ đề 3.16: Tập hợp { }: 0, ,rix i n r= ∈ bị chặn dưới. Chứng minh: Vì ( )1 ,...,r r rnx x x= là phương án nên 0rix ≥ với mọi 1, ,i n r= ∈ . Nếu hàm mục tiêu bị chặn dưới thì tồn tại m sao cho 0 ,r rx c x m= ≥ với mọi r∈ . Vậy tập hợp { }: 0, ,rix i n r= ∈ bị chặn dưới bởi { }min 0,m . Nếu ( )P có phương án nguyên. Xét x′ là một trong những phương án nguyên của ( )P . Vì lát cắt đúng không làm mất đi phương án nguyên nào của ( )P nên ta có 0 , , r rx c x c x′= ≥ . Vậy tập hợp { }: 0, ,rix i n r= ∈ bị chặn dưới bởi { }min 0, ,c x′ . Bổ đề 3.17: Nếu r nx ∉ và ( )0 0,r rp px x p n= ∉ ∈ thì ( ) ( )0 1 0 1, ,..., , ,...,r r r r r rp l px x x y y y  ≥  . Chứng minh: Đặt { }0min : 0, , rik i i n x= ∈ ∉ . Ta có k p≤ . Đặt { } { } { } min : , 0 rr jl kj kl kj RR lex j N x x x   = ∈ ≠     ( dòng quay là lát cắt mới thêm vào). Đặt { }min : 0, , 0rilh i i n x= ∈ ≠ (hàng đầu tiên của cột lR có hệ số khác 0). Vì rT l-chuẩn nên 0rlR > . Do đó 0rhlx > . Vì 0rkx ∉ nên 0 0rkx ≠ . Vậy h k p≤ ≤ . Ta có { } { } 0 , 0, r kr r r i i ilr kl x y x x i n x = − ∀ = . Vì { }min : 0, , 0rilh i i n x= ∈ ≠ nên 0,rilx i h= ∀ < . Do đó ,r ri iy x i h= ∀ < . Ta xét hai khả năng có thể xảy ra Trường hợp 1: h p< Ta có { } { } 0 r kr r r r h h hl hr kl x y x x x x = − ≠ Tóm lại, ta có ,r ri iy x i h= ∀ < ; r rh hy x< và h p< nên ( ) ( )0 1 0 1, ,..., , ,...,r r r r r rp l px x x y y y  ≥  . Trường hợp 2: h k p= = . Vì ,r ri iy x i h= ∀ < và h p= nên ,r ri iy x i p= ∀ < . Vì rklx ∉ và 0rklx > nên { }r rkl klx x≥ . Do đó ta có { } { } { } { } 0 0 r kr r r r r r r r k k kl k k k k kr kl x y x x x x x x x x  = − ≤ − = − =   . Vì k p= nên r rp py x ≤   . Vậy ta có ,r ri iy x i p= ∀ < và r rp py x ≤   nên ( ) ( )0 1 0 1, ,..., , ,...,r r r r r rp l px x x y y y  ≥  . Định lý 3.18: Thuật toán Gomory kết thúc sau một số hữu hạn các bước lặp. Chứng minh: Phản chứng. Giả sử thuật toán có vô hạn các bước lặp. Theo bổ đề 3.15 ta có dãy vô hạn { } 0 r r x ≥ là giảm từ vựng. Ta chứng minh các kết quả sau: + Tồn tại 0r để { } 0 0 r r r x ≥ là dãy hằng. ( )1 + Nếu với mỗi k m< tồn tại kr sao cho { } k r k r r x ≥ là dãy hằng thì tồn tại mr để { } m r m r r x ≥ cũng là dãy hằng. ( )2 Chứng minh ( )2 : Đặt { }max : 0, 1kr r k m= = − . Ta có { }rk r rx ≥ là dãy hằng với mọi k m< và do dãy { } 0 r r x ≥ là giảm từ vựng giảm nên { }rm r rx ≥ là dãy giảm. Phản chứng. Giả sử ngược lại không tồn tại mr để { } m r m r r x ≥ là dãy hằng. Khi ấy dãy{ }rm r rx ≥ chứa dãy con giảm ngặt { }v r m v x . Theo bổ đề 3.16, tập hợp { }: 0, ,rix i n r= ∈ bị chặn dưới. Vậy { }vrm vx là dãy giảm và bị chặn dưới nên hội tụ. Đặt lim v r mv a x →+∞ = . Do { }vrm vx là dãy giảm ngặt và hội tụ về a nên vrmx a> với mọi v +∈ . Lại do lim v r mv a x →+∞ = nên tồn tại 0v sao cho [ ] [ ] 01,vrma x a v v< < + ∀ ≥ . Vậy 0,v r mx v v∉ ∀ ≥ . Theo bổ đề 3.17, ta có ( ) ( )0 1 0 1, ,..., , ,...,v v v v v vr r r r r rm l mx x x y y y  ≥  . Theo bổ đề 3.15, ta có ( ) ( ) ( )1 1 11 1 10 1 0 1 0 1, ,..., , ,..., , ,...,v v v v v v v v vr r r r r r r r rm l m l my y y x x x x x x+ + ++ + +≤ + ≤ + . Vậy ( ) ( ) ( )1 1 10 1 0 1 0 1, ,..., , ,..., , ,...,v v v v v v v v vr r r r r r r r rm l m l mx x x y y y x x x+ + +  ≥ ≥ +  . Vì { }rk r rx ≥ là dãy hằng với k m< nên 10 0 , 0, 1v v r rx x k m+= ∀ = − . Do đó ta có 10 0 0 , 0, 1v v v r r rx y x k m+= = ∀ = − và 1v v vr r r m m mx y x +  ≥ ≥  . Điều này vô lý vì [ ] [ ] [ ]( )1v vr rm mx a a x a  = . ( )2 được chứng minh. ( )1 được chứng minh tương tự ( )2 . Từ ( )1 và ( )2 , ta có với mỗi 0,k n∈ đều tồn tại kr sao cho { } k r k r r x ≥ là dãy hằng. Đặt { }max : 0,ks r k n= = . Ta có { }rk r sx ≥ là dãy hằng với mọi 0,k n∈ . Điều này dẫn đến { }r r sx ≥ là dãy hằng, mâu thuẫn với dãy vô hạn { } 0 r r x ≥ là giảm từ vựng. Vậy thuật toán Gomory kết thúc sau một số hữu hạn các bước lặp. 3.5.4. Ví dụ Ví dụ 3.18: Giải bài toán 1 2 1 2 1 2 min 3 3 5 2 0, , 1, 2i i x x x x x x x x i + →  − ≤  + ≥  ≥ ∈ ∀ =  Xét bài toán phụ 0 1 2 3 1 2 4 1 2 max 3 2 3 5 0, , 1, 4i i x x x x x x x x x x x i = − − →  = − +  = − + +  ≥ ∈ ∀ =  Bài toán phụ có phương án ( )1,1,3,6 và bảng đơn hình xuất phát là l-chuẩn. Vậy điều kiện ( )i và ( )iii để sử dụng thuật toán Gomory được thỏa. Ta áp dụng thuật toán Gomory để giải bài toán phụ. Ta có bảng đơn hình xuất phát của bài toán phụ: 1x− 2x− 0x 0 1 1 1x 0 -1 0 2x 0 0 -1 3x 3 1 -1 4x -2 -3 -5 Đưa 4x ra khỏi tập các biến cơ sở, đưa vào 2x 1x− 4x− 0x 2 5 − 2 5 1 5 1x 0 -1 0 2x 2 5 3 5 1 5 − 3x 17 5 8 5 1 5 − 4x 0 0 -1 Ta nhận được bảng đơn hình l-chuẩn và chấp nhận được. Vì 0 2 5 x = − ∉ nên ta bổ sung thêm lát cắt đúng ( ) ( )1 4 2 1 2 5 5 5 x x     − − − − ≥ −            . Đặt biến phụ 5 0x ≥ , đưa về dạng đẳng thức ( ) ( )5 1 4 2 2 1 5 5 5 x x x     = − − − − − −            hay ( ) ( )5 1 4 3 2 1 5 5 5 x x x= − + − + − . Thêm dòng này vào cuối bảng, ta có bảng đơn hình mới 1x− 4x− 0x 2 5 − 2 5 1 5 1x 0 -1 0 2x 2 5 3 5 1 5 − 3x 17 5 8 5 1 5 − 4x 0 0 -1 5x 3 5 − 2 5 1 5 Đưa 5x ra khỏi tập các biến cơ sở, đưa vào 1x và xóa bỏ dòng cuối 5x− 4x− 0x -1 1 0 1x 3 2 5 2 − 1 2 2x 1 2 − 3 2 1 2 − 3x 1 4 -1 4x 0 0 -1 Đưa 4x ra khỏi tập các biến cơ sở, đưa vào 2x 5x− 2x− 0x -1 1 0 1x 1 -1 1 2x 0 0 -1 3x 2 1 -2 4x 1 -3 -2 Ta nhận được bảng đơn hình l-chuẩn, chấp nhận được và cột đầu tiên có các thành phần là các số nguyên. Thuật toán kết thúc. Bài toán phụ có phương án tối ưu ( )1,0,2,1 . Vậy bài toán đã cho có phương án tối ưu ( )1,0 . Chương 4: THUẬT TOÁN NHÁNH CẬNGIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH NGUYÊN Phương pháp nhánh cận ra đời năm 1960 áp dụng cho các bài toán tối ưu rời rạc trên cơ sở hầu hết các bài toán trên thực tế có tập ràng buộc hữu hạn và như vậy về nguyên tắc có thể điểm diện tất cả các phương án để chọn ra phương án tối ưu. Như vậy thuật toán nhánh cận có thể áp dụng cho bài toán quy hoạch tuyến tính nguyên với mô hình bị chặn ( tập ràng buộc của bài toán quy hoạch tuyến tính tương ứng là tập bị chặn). Một câu hỏi đặt ra là liệu với mô hình không bị chặn thì thuật toán có còn sử dụng được hay không ? Trong chương này ta sẽ đề cập đến vấn đề đó. Trong chương này ta sẽ nghiên cứu thuật toán nhánh cận và cơ sở lí luận của nó sử dụng để giải bài toán quy hoạch tuyến tính nguyên dạng chính tắc: ( ) , max , 0, n c x P Ax b x x  →′  = ≥ ∈  trong đó A là ma trận cấp m n× và rankA m= ; các ma trận ,A b , vectơ c có các thành phần là các số nguyên. Bài toán quy hoạch tuyến tính tương ứng với ( )P′ là bài toán ( ) , max , 0 c x P Ax b x  →  = ≥ . 4.1. Thuật toán đơn hình đối ngẫu giải bài toán quy hoạch tuyến tính Thuật toán đơn hình đối ngẫu khi có bảng đơn hình xuất phát là chuẩn: Ý tưởng của thuật toán: Bắt đầu từ một cơ sở mà bảng đơn hình tương ứng là chuẩn, nếu bảng đơn hình chưa là chấp nhận được thì ta tiến hành dịch chuyển sang cơ sở mới mà bảng đơn hình ứng với cơ sở mới cũng là chuẩn cho đến khi gặp bảng đơn hình là chấp nhận được thì dừng. Khi đó phương án cơ sở ứng với bảng đơn hình cuối là phương án tối ưu . Thuật toán: Giả sử tồn tại cơ sở B sao cho bảng đơn hình T ứng với B là chuẩn. Bước 1 Nếu T là chấp nhận được thì phương án cơ sở ứng với B là phương án tối ưu . Thuật toán kết thúc. Ngược lại, ta chuyển sang bước 2. Bước 2 Nếu tồn tại 1,i n∈ sao cho 0 0ix < và 0,ijx j N≥ ∀ ∈ thì ( )P không có phương án ( vì ( )0 0i i ij j j N x x x x ∈ = + − <∑ ). Vậy ( )P không có phương án tối ưu .Thuật toán kết thúc. Ngược lại: + Chọn k thỏa { }0 0min : 1,k ix x i n= = . + Chọn l thỏa 00 min : , 0jl kj kl kj xx j N x x x   = ∈ <     . + Thực hiện phép biến đổi cơ bản của bảng đơn hình : đưa kx ra khỏi tập các biến cơ sở, đưa lx vào. Quay trở lại bước 1. Nhận xét: + Trong quá trình sử dụng thuật toán đơn hình đối ngẫu thì bảng đơn hình luôn là chuẩn và hàm mục tiêu không tăng. + Trong trường hợp bảng đơn hình xuất phát không là chuẩn thì có thể tiến hành thuật toán như thuật toán đơn hình đối ngẫu từ vựng với trường hợp bảng đơn hình xuất phát không là l-chuẩn [3, tr.77-81]. 4.2. Kỹ thuật tái tối ưu hóa Giả sử ( )P có phương án tối ưu. Sử dụng thuật toán đơn hình đối ngẫu tìm phương án tối ưu của ( )P ta thu được bảng đơn hình T là chuẩn và chấp nhận được và cơ sở tương ứng B . Xét bài toán ( )Q là bài toán ( )P có bổ sung thêm ràng buộc 1 n i i i a x α = ≤∑ . Câu hỏi đặt ra: Liệu có thể thể tận dụng những thông tin đã có khi tìm phương án tối ưu của ( )P để tìm phương án tối ưu của ( )Q hay không? Trong mục này ta sẽ nghiên cứu vấn đề đó. Đưa thêm biến phụ 1 0nx + ≥ với hệ số hàm mục tiêu bằng 0 , chuyển ràng buộc về dạng đẳng thức 1 1 n n i i i x a xα+ = = + −∑ . Do ( )0 , 0,i i ij j j N x x x x i n ∈ = + − ∀ =∑ nên ( )1 0 1 1 n n n i i i ij j i j N i x a x a x xα+ = ∈ =     = − + − −        ∑ ∑ ∑ . Viết dòng trên vào cuối bảng đơn hình T ta thu được bảng đơn hình mới T ′ ứng với cơ sở mới { }1B B n′ = + . T là chuẩn nên T ′ cũng là chuẩn. Vậy ta có thể áp dụng thuật toán đơn hình đối ngẫu bắt đầu từ bảng đơn hình T ′ để tìm phương án tối ưu của ( )Q . Thủ tục vừa mô tả ở trên được gọi là “ kĩ thuật tái tối ưu hóa” trong quy hoạch tuyến tính. Kỹ thuật này được áp dụng khi gặp các bài toán quy hoạch tuyến tính với số ràng buộc tăng dần, giúp tiết kiệm thời gian so với việc giải lại từ đầu bài toán với ràng buộc thêm vào. 4.3. Thuật toán nhánh cận 4.3.1. Điều kiện để sử dụng thuật toán nhánh cận Điều kiện để sử dụng thuật toán nhánh cận giống như điều kiện để sử dụng thuật toán Gomory tức là cần có điều kiện ( )i Tập các phương án tối ưu của ( )P bị chặn và một trong hai điều kiện sau ( )ii Hàm mục tiêu bị chặn dưới trên tập các phương án của ( )P , hoặc ( )iii ( )P có phương án nguyên. 4.3.2. Thuật toán nhánh cận Bước 0: Sử dụng thuật toán đơn hình đối ngẫu để tìm phương án tối ưu của ( )P . Nếu ( )P không có phương án tối ưu thì ( )P′ cũng không có phương án tối ưu. Thuật toán kết thúc. Ngược lại, nếu ( )P có phương án tối ưu 0x . Ta kiểm tra: + Nếu 0x là phương án nguyên của ( )P thì 0x là phương án tối ưu của ( )P′ . Thuật toán kết thúc. + Ngược lại, nếu 0x là không phải là phương án nguyên thì ta tiến hành: - Đưa ( )P′ vào danh mục các bài toán cần xét: ( ){ }P′Ω = . - Đặt cận trên của ( )P′ là giá trị tối ưu của bài toán quy hoạch tương ứng ( )P . - Nếu biết y′ là một phương án của ( )P′ thì : • Gán giá trị kỉ lục 0 : ,x c y′= ( giá trị tốt nhất mà ta biết), • Gán phương án kỉ lục :x y∗ ′= ( phương án tốt nhất mà ta biết). Ngược lại, gán giá trị kỉ lục 0 :x = −∞ . - Chuyển sang bước lặp thứ 1r = . Bước lặp thứ ( )1r r ≥ : + Nếu Ω ≠∅ thì chọn ( )Q′ là bài toán trong Ω có cận trên lớn nhất. Đặt ( )1 ,...,Q Q Qnx x x= là phương án tối ưu của bài toán quy hoạch tương ứng ( )Q . Đặt { }min : Qik i x= ∉ . Tách ( )Q′ thành hai bài toán con ( ) ( )1 2,Q Q′ ′ trong đó ( )1Q′ là ( )Q′ có bổ sung thêm ràng buộc Qk kx x ≤   và ( )2Q′ là ( )Q′ có bổ sung thêm ràng buộc 1 Q k kx x ≥ +  . Lần lượt tìm phương án tối ưu của các bài toán quy hoạch tương ứng ( ) ( )1 2,Q Q . Ta gặp phải các trường hợp: - ( )iQ không có phương án. Khi đó loại bỏ ( )iQ′ khỏi việc xem xét tiếp theo. - ( )iQ có phương án tối ưu nguyên iQx . Khi đó nếu 0, iQc x x> thì xác định lại giá trị kỉ lục 0 : , i Qx c x= và phương án kỉ lục : iQx x∗ = . - ( )iQ có phương án tối ưu không nguyên iQx . Trong trường hợp này, đặt cận trên của ( )iQ′ là , iQc x và kết nạp ( )iQ′ vào danh mục các bài toán cần xét: ( ){ }: iQ′Ω = Ω∪ . Loại bỏ khỏi Ω bài toán ( )Q′ và những bài toán có cận trên nhỏ hơn hay bằng giá trị kỉ lục. Chuyển sang bước lặp 1r + . + Nếu Ω =∅ , ta xét : - Nếu 0x > −∞ thì ( )P′ có phương án tối ưu là x∗ và giá trị tối ưu là 0x . Thuật toán kết thúc. - Nếu 0x = −∞ thì ( )P′ không có phương án. Vậy ( )P′ không có phương án tối ưu. Thuật toán kết thúc. 4.3.3. Cơ sở lí luận của thuật toán Gọi 0rx là giá trị kỉ lục sau khi kết thúc bước lặp thứ r trong thuật toán. Theo cách thức vận hành thuật toán, dãy { }0 0 r r x ≥ là dãy không giảm. Vậy khi thuật toán kết thúc nếu ta nhận được giá trị kỉ lục 0x thì 0 0 , 1rx x r≤ ∀ ≥ . Định lý 4.1: Nếu Ω =∅ và ta nhận được 0x > −∞ thì ( )P′ có phương án tối ưu là x∗ và giá trị tối ưu là 0x . Chứng minh: Trước hết, tập các phương án của ( )P′ là khác rỗng ( x∗ là phương án của ( )P′ ). Xét x′ là phương án của ( )P′ . Khi đó x′ là phương án của bài toán ( )Q′ bị loại bỏ trong một bước lặp r nào đó ( bị loại bỏ nhưng không bị tách thành hai bài toán con). Gọi ( )Q là bài toán quy hoạch tương ứng với ( )Q′ .Vì ( )Q′ bị loại bỏ nên chỉ có các khả năng sau: + ( )Q có phương án tối ưu nguyên Qx . Khi đó, ta có 0 0, , ,Q rc x c x x x c x∗′ ≤ ≤ ≤ = . + ( )Q có phương án tối ưu không nguyên Qx và cận trên nhỏ hơn hoặc bằng giá trị kỉ lục: 1 0 0, , Q rc x x x c x− ∗≤ ≤ = . Do đó 0, , ,Qc x c x x c x∗′ ≤ ≤ = . Vậy trong cả hai khả năng , ta đều có 0, ,c x x c x∗′ ≤ = . Điều đó có nghĩa là ( )P′ có phương án tối ưu là x∗ và giá trị tối ưu là 0x . Định lý 4.2: Nếu Ω =∅ và ta nhận được 0x = −∞ thì ( )P′ không có phương án. Chứng minh: Phản chứng. Giả sử ( )P′ có phương án x′ . Khi đó x′ là phương án của bài toán ( )Q′ bị loại bỏ trong một bước lặp r nào đó (bị loại bỏ nhưng không bị tách thành hai bài toán con). Gọi ( )Q là bài toán quy hoạch tuyến tính tương ứng với ( )Q′ .Vì ( )Q′ bị loại bỏ nên chỉ có các khả năng sau: + ( )Q có phương án tối ưu nguyên Qx . Khi đó, ta có 0 0, , Q rc x c x x x′ ≤ ≤ ≤ . + ( )Q có phương án tối ưu không nguyên Qx và cận trên nhỏ hơn hoặc bằng giá trị kỉ lục: 1 0 0, Q rc x x x−≤ ≤ . Trong hai khả năng , ta đều có 0x > −∞ . Điều này mâu thuẫn với giả thiết 0x = −∞ . Vậy nếu 0x = −∞ thì ( )P′ không có phương án. Giả sử ,D D là các tập lồi đa diện không chứa đường thẳng trong n và D D⊂ . Khi ấy ta có hai định lý sau Định lý 4.3: Nếu bài toán { }( )max , : 1c x x D∈ có phương án tối ưu thì bài toán { }( )max , : 2c x x D∈ cũng có phương án tối ưu nếu tập phương án D khác rỗng. Chứng minh: Giả sử bài toán ( )1 có giá trị tối ưu là 0x . Khi ấy, ta có 0, , .c x x x D≤ ∀ ∈ Mà do D D⊂ nên 0, , .c x x x D≤ ∀ ∈ Vậy hàm mục tiêu ,c x bị chặn trên trên D nên bài toán ( )2 có phương án tối ưu nếu D ≠ ∅ . Nhận xét: Nếu bài toán { }max , :c x x D∈ có phương án tối ưu thì bài toán { }max , :c x x D∈ hoặc không có phương án hoặc có phương án tối ưu. Định lý 4.4: Nếu tập các phương án tối ưu của bài toán { }( )max , : 1c x x D∈ khác rỗng và bị chặn thì tập các phương án tối ưu của bài toán { }( )max , : 2c x x D∈ cũng bị chặn. Chứng minh: Giả sử tập các phương án tối ưu của bài toán ( )2 không bị chặn. Đặt 0x là giá trị tối ưu của bài toán ( )2 . Khi đó tập các phương án tối ưu của nó { }0: ,nD D x c x x= ∈ =  cũng là tập lồi đa diện. Vì D không bị chặn nên D có phương vô tận v . Lấy cố định x D∗ ∈ . Ta có 0,c x v x∗ + = nên , 0.c v = Do v là phương vô tận của D và D D⊂ nên v cũng là phương vô tận của D . Lấy cố định x∗ là phương án tối ưu của bài toán ( )1 . Khi đó x vλ∗ + là phương án tối ưu của bài toán ( )1 với mọi 0λ > . Điều này mâu thuẫn với tập các phương án tối ưu của bài toán ( )1 bị chặn. Vậy nếu tập các phương án tối ưu của bài toán ( )1 khác rỗng và bị chặn thì tập các phương án tối ưu của bài toán ( )2 cũng bị chặn. Định lý 4.5: Nếu tập các phương án của ( )P bị chặn thì thuật toán nhánh cận kết thúc sau một số hữu hạn các bước lặp. Chứng minh: Giả sử thuật toán có vô hạn các bước lặp. Vậy trong thuật toán sẽ tồn tại dãy vô hạn các bài toán ( ){ } 1r rP ≥′ bị chia tách sao cho ( )1rP +′ nhận được từ ( )rP′ sau một số bước lặp nào đó. Vì một phương án của ( )P′ chỉ có hữu hạn thành phần ( n thành phần) nên không giảm tổng quát ta giả sử ( )rP′ bị chia tách do thành phần thứ nhất không nguyên với mọi 1r ≥ . Đặt ( )1 ,...,r r rP P Pnx x x= là phương án tối ưu của ( )rP ( bài toán quy hoạch tương ứng với ( )rP′ ). Do tập các phương án của ( )P bị chặn nên tồn tại 1 1,a b ∈ sao cho [ ]1 1 1 1,x A a b∈ = với mọi phương án ( )1,..., nx x của ( )1P . Giả sử 1 rx A∈ với mọi phương án ( )1,..., nx x của ( )rP . Do ( )1rP +′ nhận được từ ( )rP′ sau một số bước lặp nào đó nên 1 1 rPx x ≤   hoặc 1 1 1r Px x ≥ +  với mọi phương án ( )1,..., nx x của ( )1rP + và nếu ( )1,..., nx x là phương án của ( )1rP + thì cũng là phương án của ( )rP . Vậy ( )1 1 1 1\ , 1r rP Pr rx A A x x+    ∈ = +    với mọi phương án ( )1,..., nx x của ( )1rP + . Như vậy ta đã xây dựng được dãy vô hạn các tập hợp { } 1r rA ≥ . Do 1 1,a b ∈ nên với cách xây dựng các tập hợp rA như vậy ta thấy rA có các điểm biên đều là các số nguyên. Vậy từ 1 r P rx A∈ và 1 r Px ∉ , ta có ( )1 1, 1r rP P rx x A    + ⊂    . Vậy, ta có ( ) ( ) ( )( ) ( )1 1 1, 1 1, 1r rP Pr r rA A x x A rµ µ µ µ+    = − + = − ∀ ≥    trong đó ( )Aµ là độ đo Lebesgue của A . Điều này dẫn đến ( ) ( )1 1 11 1 , 1rA A r b a r rµ µ= − + = − + − ∀ ≥ . Do đó ( )lim rr Aµ→+∞ = −∞ (vô lý vì độ đo Lebesgue là độ đo dương). Vậy thuật toán nhánh cận kết thúc sau một số hữu hạn các bước lặp. Định lý 4.6: Nếu các điều kiện giống như các điều kiện để sử dụng thuật toán Gomory được thỏa thì thuật toán nhánh cận kết thúc sau một số hữu hạn các bước lặp. Chứng minh: Giả sử thuật toán có vô hạn các bước lặp. Vậy trong thuật toán sẽ tồn tại dãy vô hạn các bài toán ( ){ } 1r rP ≥′ bị chia tách tại bước lặp rn sao cho ( )1rP +′ nhận được từ ( )rP′ sau một số bước lặp nào đó. Vì một phương án của ( )P′ chỉ có hữu hạn thành phần ( n thành phần) nên không giảm tổng quát ta giả sử ( )rP′ bị chia tách do thành phần thứ nhất không nguyên với mọi 1r ≥ . Đặt 0 r Px là giá trị tối ưu của ( )rP ( bài toán quy hoạch tuyến tính tương ứng với ( )rP′ ). Ta chứng minh dãy{ }0 1r P r x ≥ bị chặn dưới. Thậy vậy, nếu điều kiện ( )ii được thỏa tức là hàm mục tiêu bị chặn dưới trên tập các phương án của ( )P thì ta có điều phải chứng minh còn nếu điều kiện ( )iii được thỏa tức là ( )P có phương án nguyên x′ thì ta xét: + Nếu tại một bước lặp 0r n nào đó giá trị kỉ lục 00 0 r nx x= > −∞ thì theo cách thức tiến hành thuật toán ta loại bỏ tất cả những bài toán trong danh mục các bài toán cần xét mà có cận trên nhỏ hơn hay bằng giá trị kỉ lục nên 00 0 rr nPx x≥ với mọi 0r r> . Vậy dãy{ }0 1r P r x ≥ bị chặn dưới. + Ngược lại, giá trị kỉ lục 00 0 r nx x= = −∞ tại mọi bước lặp rn . Khi ấy x′ phải là phương án của một bài toán nào đó trong danh mục các bài toán cần xét tại bất kỳ bước lặp rn nào và vì 0 r Px là cận trên lớn nhất trong các cận trên của các bài toán trong danh mục các bài toán cần xét ở bước lặp rn nên 0 ,r Px c x′≥ với mọi 1r ≥ . Vậy trong mọi trường hợp ta đều có dãy{ }0 1r P r x ≥ bị chặn dưới. Đặt { }0 1inf r P r xα ≥ = và ( )1 ,...,r r rP P Pnx x x= là phương án tối ưu của ( )rP . Vì 0, r r P Pc x x= nên ta có { } { } 1 : ,rP n r x x c x α ≥ ⊂ ∈ ≥ . Đặt 1D là tập các phương án của ( )1P . Vì ( )rP nhận được từ ( )1P sau một số bước lặp nên phương án của ( )rP thì cũng là phương án của ( )1P . Do đó dãy { } 1 rP r r x ≥ nằm trong 1D . Vậy ta có { } { } 1 1 1 : ,r P n r r x D D x c x α ≥ ⊂ = ∈ ≥  . Ta chứng minh 1D là tập bị chặn. Thật vậy giả sử ngược lại 1D không bị chặn thì 1D có phương vô tận v . Vì ( )1P có phương án tối ưu nên hàm mục tiêu ,c x bị chặn trên trên 1D . Mà 1 1D D⊂ nên hàm mục tiêu ,c x cũng bị chặn trên trên 1D . Do vậy, ta phải có , 0c v ≤ . Lại có { }1 : ,nD x c x α⊂ ∈ ≥ nên , 0c v ≥ . Vậy phải có , 0c v = . Do v là phương vô tận của 1D và 1 1D D⊂ nên v cũng là phương vô tận của 1D . Vậy ta có 1 Px vλ+ là phương án tối ưu của ( )1P với mọi 0λ > .Điều này dẫn đến ( )1P có tập các phương án tối ưu không bị chặn. Ta gặp mâu thuẫn vì theo điều kiện ( )i , tập các phương án tối ưu của ( )P bị chặn nên do định lý 4.4 ta có tập các phương án tối ưu của ( )1P bị chặn. Vậy 1D là tập bị chặn. Ta chứng minh dãy { } 1 rP r x ≥ là dãy không bị chặn. Do ( )1rP +′ nhận được từ ( )rP′ sau một số bước lặp nào đó nên 1 1 r Px x ≤   với mọi phương án ( )1,..., nx x của ( )1rP + hoặc 1 1 1r Px x ≥ +  với mọi phương án ( )1,..., nx x của ( )1rP + . Nếu tồn tại 1r sao cho 11 1 rPx x ≤   với mọi phương án ( )1,..., nx x của ( )1 1rP + . Khi đó, ta có 11 10; r Px x  ∈    với mọi phương án ( )1,..., nx x của ( )1 1rP + . Tới đây hoàn toàn tương tự chứng minh trong trường hợp tập các phương án của ( )P bị chặn ta dẫn đến điều vô lý. Vậy ta có với mọi 1r ≥ , 1 1 1rPx x ≥ +  với mọi phương án ( )1,..., nx x của ( )1rP + . Do đó 11 1 1r rP Px x+  ≥ +  với mọi 1r ≥ . Điều này dẫn đến dãy số { }1 1r P r x ≥ không bị chặn. Vậy dãy { } 1 rP r x ≥ là dãy không bị chặn. Ta có { } 11r P r x D ≥ ⊂ và dãy { } 1 rP r x ≥ không bị chặn nên 1D không bị chặn. Điều này mâu thuẫn với 1D là tập bị chặn. Vậy thuật toán nhánh cận kết thúc sau một số hữu hạn các bước lặp. 4.3.4. Ví dụ Ví dụ 4.7: Ta xét lại ví dụ đã minh họa cho phương pháp cắt Gomory. Bây giờ ta giải bài toán đó bằng phương pháp nhánh cận. Giải bài toán 1 2 1 2 1 2 min 3 3 5 2 0, , 1, 2i i x x x x x x x x i + →  − ≤  + ≥  ≥ ∈ ∀ =  . Xét bài toán phụ 0 1 2 3 1 2 4 1 2 max 3 2 3 5 0, , 1, 4i i x x x x x x x x x x x i = − − →  = − +  = − + +  ≥ ∈ ∀ =  Bài toán phụ có phương án ( )1,1,3,6 và bảng đơn hình xuất phát là l-chuẩn. Vậy điều kiện ( )iii và ( )i được thỏa. Ta áp dụng thuật toán nhánh cận để giải bài toán phụ: + Đặt bài toán phụ là ( )P′ . Sử dụng phương pháp đơn hình đối ngẫu xác định phương án tối ưu của bài toán quy hoạch tuyến tính tương ứng với ( )P′ là 2 170, , ,0 5 5       . Thành phần thứ hai của phương án tối ưu chưa nguyên nên ta gán: - Danh mục các bài toán cần xét ( ){ }: P′Ω = - Phương án kỉ lục ( ): 1,1,3,6x∗ = - Giá trị kỉ lục 0 : 2x = − . Chuyển qua bước lặp 1r = . + Bước lặp 1r = : Chia ( )P′ thành hai bài toán con ( ) ( )1 2,P P′ ′ trong đó ( )1P′ là ( )P′ có bổ sung thêm ràng buộc 2 0x ≤ và ( )2P′ là ( )P′ có bổ sung thêm ràng buộc 2 1x ≥ . Giải ( )1P′ tìm được phương án tối ưu chưa nguyên 2 7,0, ,0 3 3       và giá trị tối ưu tương ứng là 2 3 − . Giải ( )2P′ tìm được phương án tối ưu nguyên ( )0,1, 4,3 và giá trị tối ưu tương ứng là ( )01 x− > . Xác định lại phương án kỉ lục ( ): 0,1, 4,3x∗ = và giá trị kỉ lục 0 : 1x = − . Gán: Danh mục các bài toán cần xét ( ){ }1: P′Ω = Chuyển qua bước lặp 2r = . + Bước lặp 2r = : Chia ( )1P′ thành hai bài toán con ( ) ( )3 4,P P′ ′ trong đó ( )3P′ là ( )P′ có bổ sung thêm ràng buộc 1 0x ≤ và ( )4P′ là ( )P′ có bổ sung thêm ràng buộc 1 1x ≥ . Giải ( )3P′ . ( )3P′ không có phương án. Giải ( )4P′ tìm được phương án tối ưu nguyên ( )1,0,2,1 và giá trị tối ưu tương ứng là ( )01 x− = . Gán: :Ω =∅ . Kết luận: Vì giá trị kỉ lục 0 1x = − < +∞ nên bài toán phụ ( )P′ có phương án tối ưu là ( ): 0,1, 4,3x∗ = . Vậy bài toán đã cho có phương án tối ưu là ( )0,1 . Nếu bài toán quy hoạch tuyến tính không thỏa điều kiện Gomory thì khi tiến hành thuật toán nhánh cận có thể xảy ra vô hạn các bước lặp ( thuật toán không thể kết thúc). Các ví dụ sau sẽ đề cập đến vấn đề này. Ví dụ 4.8: Giải bài toán 1 1 2 max 2 2 1 0, , 1, 2i i x x x x x i − →  − =  ≥ ∈ ∀ =  Bài toán quy hoạch tuyến tính tương ứng có phương án tối ưu duy nhất 1 ,0 2       nên bài toán thỏa điều kiện (i). Vì không có cặp số nguyên 1 2,x x nào thỏa điều kiện 1 22 2 1x x− = nên tập phương án của bài toán là tập rỗng và hàm mục tiêu 1x− không bị chặn dưới trên tập các phương án của bài toán quy hoạch tuyến tính tương ứng ( 21 2 1 2 xx +− = − → −∞ khi 2x →+∞ ). Vậy bài toán không thỏa điều kiện (ii) và (iii) nên bài toán không thỏa điều kiện Gomory. Thuật toán nhánh cận khi áp dụng cho bài toán có vô hạn các bước lặp. Ở mỗi bước lặp thứ r có đúng 2 bài toán đươc xem xét: một bài toán có tập phương án rỗng, bài toán còn lại có phương án tối ưu 21 , 2 2 r r+ ∉     . Ví dụ 4.9: Giải bài toán 1 2 1 2 3 1 4 max 2 2 1 1 0, , 1, 4i i x x x x x x x x x i − →  − + =  − =  ≥ ∈ ∀ =  Bài toán có phương án ( )1,1,0,0 . Vậy bài toán thỏa điều kiện (iii). Tuy nhiên tập các phương án tối ưu của bài toán quy hoạch tương ứng ( )1 2 1 2 2 1, ,0,0 : , 0 2 x x x x x − = ≥    là tập không bị chặn nên bài toán không thỏa điều kiện (i). Vậy bài toán không thỏa điều kiện Gomory. Thuật toán nhánh cận khi áp dụng cho bài toán có vô hạn các bước lặp. Ở mỗi bước lặp thứ r có đúng 2 bài toán được xem xét: một bài toán có tập phương án rỗng ( nếu r lẻ) hoặc có phương án tối ưu nguyên , ,0,0 2 2 r r      ứng với giá trị tối ưu là 0 ( nếu r chẵn) , bài toán còn lại có phương án tối ưu 41 , ,0,0 2 2 r r+ ∉     . Kết luận Luận văn đã trình bày chi tiết một số kết quả đã có của quy hoạch tuyến tính nguyên và cũng thu được một số kết quả mới trong việc nghiên cứu quy hoạch nguyên với mô hình tuyến tính bất kỳ. Bài toán quy hoạch nguyên với mô hình tuyến tính bất kỳ chưa được giải quyết một cách trọn vẹn. Như các ví dụ 4.8,4.9 cho thấy thuật toán nhánh cận đã khảo sát không thể giải quyết các bài toán như vậy. Điều này đòi hỏi phải có sự cải tiến thuật toán đó hoặc nghiên cứu một thuật toán hoàn toàn mới. Đó là vấn đề mà tác giả sẽ tiếp tục nghiên cứu. Tài liệu tham khảo [1] R. Tyrrell Rockafellar, Convex analysis . [2] Bùi Thế Tâm (2008), Quy hoạch rời rạc (Bài giảng cao học), Hà Nội. [3] Nguyễn Đức Nghĩa (1998), Tối ưu hóa ( Quy hoạch tuyến tính và rời rạc), Nhà xuất bản Giáo dục. [4] Hoàng Tụy (1968), Lý thuyết quy hoạch, Nhà xuất bản Khoa học.