Đề tài Nghiên cứu về bài toán quy hoạch nguyên tuyến tính

hoạch tập 0 ( )k iD rất có thể chúng sẽ tìm đ−ợc các ph−ơng án chấp nhận đ−ợc của bài toán. Kí hiệu x là ph−ơng án chấp nhận đ−ợc tìm đ−ợc. Ta sẽ gọi x là lời giải tốt nhất hiện có hay gọi vắn tắt là kỉ lục, còn giá - 35 - trị ( )f f x= sẽ gọi là giá trị kỉ lục. Giả sử ở b−ớc k ta đQ có kỉ lục x, khi đó ta có thể loại khỏi quá trình điểm diện tất cả các tập ( )kiD có giá trị cận d−ới là lớn hơn hoặc bằng giá trị kỉ lục. Khi áp dụng sơ đồ vừa trình bày đối với một bài toán tối −u rời rạc cụ thể ta cần phải xây dựng đ−ợc hai thủ tục chính sau: • Thủ tục phân hoạch tập 0 ( )k iD ra thành các tập con (còn gọi là thủ tục phân nhánh); • Thủ tục tính cận d−ới ( )Aγ . 2.2.2.2. Một áp dụng của l−ợc đồ nhánh cận vào việc giải bài toán quy hoạch nguyên tuyến tính là thuật toán Land - Doig. Sơ đồ của thuật toán Giả sử ta cần giải bài toán QHTT nguyên (P): ( ) 1 min n t j j j f x c x c x = = = →∑ D ={ mibxa i n j jij ,1, 1 =≤∑ = ; 0jx ≥ , nguyên, nj ,1= } Ta kí hiệu ( )′P là bài toán: ( ) 1 min n j j j f x c x = = →∑ D′={ mibxa i n j jij ,1, 1 =≤∑ = ; 0≥jx , nj ,1= } B−ớc chuẩn bị: Giải bài toán ( )′P có hai khả năng: Nếu φ=′D thì φ=D . Bài toán không có ph−ơng án. Nếu tìm đ−ợc ph−ơng án tối −u 0x thì: • Nếu 0x là nguyên thì 0x cũng là ph−ơng án tối −u của (P). • Nếu 0x không nguyên thì đặt: m(D) = [ min f(x)] = [f (x0)] (số nguyên nhỏ nhất không bé hơn f(x0)) Giả sử 0 rx là thành phần không nguyên nào đó của 0x ; ta chia D thành hai tập bằng cách đ−a vào các ràng buộc loại trừ nhau nh− sau: - 36 - { }1 01 : r rD x D x x = ∈ ≤   { }1 02 : 1r rD x D x x = ∈ ≥ +  Khi đó: 12 1 1 DDD ∪= và φ=∩ 1211 DD . Kí hiệu 1 1( )P là bài toán: ( ) 11 1 min, DxxcxcxF t n j jj ∈→== ∑ = 1 2( )P là bài toán: ( ) 12 1 min, DxxcxcxF t n j jj ∈→== ∑ = 1 1 1 2( ), ( )P P là các bài toán QHTT nguyên. Giải các bài toán ( )11P ′và ( )12P ′ , đó là các bài toán QHTT t−ơng ứng với 11( )P và ( )12P bỏ đi điều kiện jx nguyên, Để tìm ( )11Dm và ( )12Dm ta có thể gặp phải các tình huống sau đây: 1. Phát hiện ( ) { }1 , 1,2iD i′ = ∅ ∈ thì loại 1iD khỏi quá trình tiếp theo vì φ=1iD . 2. Tìm đ−ợc ph−ơng án tối −u ix nguyên, khi đó ix cũng là ph−ơng án tối −u của bài toán ( )1iP . Ta tính ( )if x , gọi đó là một kỷ lục và loại nó khỏi quá trình tiếp theo. Nếu tìm đ−ợc kỷ lục của cả hai bài toán ( )11P và ( )12P thì chỉ việc so sánh chúng để tìm ra ph−ơng án tối −u. 3. Tìm đ−ợc ph−ơng án tối −u ix không nguyên thì cận d−ới ( )1 ( )iim D f x =   (số nguyên nhỏ nhất không bé hơn ( )if x ). Quá trình cứ thế tiếp tục. B−ớc k: Giả sử b−ớc (k - 1) ta đQ tìm đ−ợc một phân hoạch của D gồm k tập: - 37 - 1 1 −kD , 12 −kD , 13 −kD ,..., 1−kkD và đQ giải các bài toán QHTT (bỏ đi điều kiện x nguyên) t−ơng ứng là: ( )'11kP − , ( )'12kP − ,..., ( )'1kkP − và thu đ−ợc kết quả là: 1. Phát hiện một số tập 1−k jD là rỗng, j = {1,2,...,k}; ta coi ( ) +∞=−1kjDm . 2. Tìm đ−ợc một số kỷ lục (ph−ơng án tối −u nguyên). 3. Tìm đ−ợc cận d−ới của các tập 1−kjD còn lại. Thuật toán ở b−ớc k thực hiện nh− sau: Tìm kỷ lục nhỏ nhất, giả sử đó là: ( )* * 1, ksf x x D −∈ Loại bỏ tất cả các tập rỗng và các tập có cận d−ới lớn hơn ( )*f x . Nếu không còn tập nào có cận d−ới nhỏ hơn ( )*f x thì *x là ph−ơng án tối −u của bài toán (P). Thuật toán kết thúc. Nếu có những tập có cận d−ới nhỏ hơn ( )*f x thì ta phân nhánh tại đỉnh nào có cận d−ới nhỏ nhất. Vì bản số của D là hữu hạn nên thuật toán kết thúc sau một số hữu hạn b−ớc. Ví dụ: Giải bài toán quy hoạch nguyên tuyến tính (P) sau đây bằng thuật toán Land - Doig: f(x) = -x1 - x2 → min. 1 2 1 2 1 4 2 1 4 2 11 1 / 2 x x x x x − + ≤ −  + ≤  − ≤ − 1 2, 0x x ≥ , nguyên. B−ớc chuẩn bị. Giải bài toán ( )′P bỏ đi điều kiện nguyên của các biến số ta đ−ợc ph−ơng án tối −u: x0 = (3/2, 5/2). [ ] 0 3 5( ) min ( ) ( ) 4 2 2 m D f x f x − = = = − = −   . B−ớc 1. Vì 0x không nguyên và có: 0 0 1 1 3 3 1 2 2 x x   = ⇒ = =     . Ta chia D thành 2 tập: - 38 - { }11 1/ 1D x D x= ∈ ≤ { }12 1/ 2D x D x= ∈ ≥ Giải bài toán ( )11P ′ ta đ−ợc ph−ơng án tối −u: 1 31, 2 x   =     và tìm đ−ợc ( )1 11 3( ) 1 22m D f x   = = − − = −     . Giải bài toán ( )12P ′ ta đ−ợc ph−ơng án tối −u: 1 3(2, ) 2 x = và tìm đ−ợc 11 2 3( ) ( ) 2 3 2 m D f x   = = − − = −      Do 1 12 1( ) ( )m D m D< . Nên ta phân nhánh tại 12D B−ớc 2. Do 1 2 3 2 x = không nguyên nên ta phân hoạch tập 12D thành 2 tập: { }2 11 2 2/ 1D x D x= ∈ ≤ { }2 12 2 2/ 2D x D x= ∈ ≥ Giải bài toán 2 1( )P ′ ta thu đ−ợc ph−ơng án tối −u: 2 9( ,1) 4 x = và tìm đ−ợc [ ]21 2 9( ) ( ) 1 34m D f x   = = − − = −   . Giải bài toán 22( )P ′ ta thấy 2 2( )D =∅ và 22( )m D =+∞ Do 2 1 1 1( ) ( )m D m D< nên ta phân nhánh tại 21D . B−ớc 3 :Do 21 9 4 x = không nguyên nên ta phân hoạch tập 2 1D thành hai tập: { } { } 3 2 1 1 1 3 2 2 1 1 ; 2 ; 3 D x D x D x D x = ∈ ≤ = ∈ ≥ Giải bài toán 31( )P ′ ta thu đ−ợc ph−ơng án tối −u: 3 ( 2 ,1)x = và tìm đ−ợc [ ]3 31( ) ( ) 2 1 3m D f x = = − − = −  . Giải bài toán 32( )P ′ ta thấy 32( )m D = ∅ . - 39 - Tại 31D ta ghi đ−ợc kỷ lục: ( ) ( )3 31 3m D f x= = − . ( )3 2,1x = thoả mQn điều kiện nguyên nên nó là ph−ơng án tối −u của bài toán đQ cho, thuật toán kết thúc. ( ) ( )* *2,1 ; 3x f x= = − . 2.2.3. Bài toán cái túi và ph−ơng pháp ph−ơng trình truy toán của quy hoạch động giải bài toán cái túi Bài toán cái túi là bài toán tìm cực đại (cực tiểu) của hàm mục tiêu tuyến tính trong số nguyên không âm với một ràng buộc tuyến tính dạng đẳng thức hoặc bất đẳng thức. Nội dung thực tế của bài toán đ−ợc mô tả nh− sau: 2.2.3.1.Nội dung thực tế của bài toán cái túi Một nhà thám hiểm cần đem theo một cái túi có trọng l−ợng không quá b. Có n loại đồ vật có thể đem theo. Đồ vật thứ j có trọng l−ợng là aj và giá trị sử dụng là cj ( 1,j n= ). Hỏi rằng nhà thám hiểm cần đem theo các loại đồ vật nào và với số l−ợng là bao nhiêu để cho tổng giá trị sử dụng của các đồ đem theo là lớn nhất. Mô hình toán học của bài toán. Gọi jx là số l−ợng đồ vật loại ),1( njj = mà nhà thám hiểm sẽ đem theo. Khi đó, mô hình toán học của bài toán có dạng sau: 1 1 0; , 1, . n j j j n j j j j j c x max a x b x x nguyen j n = =  →   ≤   ≥ − =  ∑ ∑ Bài toán cái túi còn đ−ợc phát biểu từ một tình huống thực tế khác nh− sau Một nhà thám hiểm s−u tầm đ−ợc n mẫu quặng từ một vùng xa xôi và phải đem theo chúng về nhà. Mẫu quặng thứ i có trọng l−ợng là ai và giá trị là ci. Hỏi nhà thám hiểm phải đem về những mẫu quặng nào để có tổng giá trị của chúng là lớn nhất, biết rằng nhà thám hiểm đó có mang theo một cái túi và anh ta chỉ mang đ−ợc trọng l−ợng không quá b. - 40 - Bài toán cái túi đóng vai trò hết sức quan trọng trong lý thuyết tối −u bởi vì: thứ nhất, mọi bài toán quy hoạch nguyên tuyến tính với biến số giới nội đều có thể đ−a về bài toán cái túi; thứ hai, để giải bài toán cái túi có thể sử dụng những thuật toán t−ơng đối hữu hiệu. 2.2.3.2. Đ−a bài toán quy hoạch nguyên tuyến tính về bài toán cái túi . Các ph−ơng pháp hợp nhất hoá Định lý 1: Nếu nh− t1, t2 là hai số nguyên nguyên tố cùng nhau (t1, t2) = 1 thì mọi nghiệm nguyên của ph−ơng trình 1 1 2 2 0t y t y+ = (2.26) đều có thể biểu diễn d−ới dạng 1 2 2 1,y qt y qt= − = , trong đó q là một số nguyên tuỳ ý. Chứng minh: Giả sử y1, y2 là nghiệm nguyên của ph−ơng trình (2.26). Khi đó 21 2 1 ty y t − = mà 1y ∈ Z (t1, t2) = 1. Nên y2 phải chia hết t1 tức là y2 = qt trong đó q ∈Z .Từ (1.1) suy ra y1 = - qt2. Định lý 2: Nếu nh− t1, t2 là hai số nguyên d−ơng thoả mQn: 1) (t1, t2) = 1. 2) t2 không chia hết b1, t1 không chia hết b2. 3) t1 > b2 – amin; t2 > b1 – amin. trong đó amin = min{ ai j; aij > 0; i = 1,2; 1,j n= } Khi đó tập các nghiệm nguyên không âm của hệ 1 1 1 2 2 1 (2.27) n j j j n j j j a x b a x b = =  =    =  ∑ ∑ trong đó aij ≥ 0, bi > 0 là các số nguyên ( 1, , 1,i m j n= = ) là trùng với tập nghiệm nguyên không âm của ph−ơng trình: 1 1 2 2 1 1 2 2 1 ( ) n j j j j t a t a x t b t b = + = +∑ (2.28). Chứng minh: Chứng minh (2.27) ⇒ (2.28). - 41 - Giả sử * * * * 1 2( , ,...., )nx x x x= là nghiệm nguyên không âm của hệ (2.27) Khi đó ta có: * 1 1 1 * 2 2 1 n j j j n j j j a x b a x b = =  =    =  ∑ ∑ Do t1, t2 là hai số nguyên d−ơng thoả mQn điều kiện 1), 2), 3), ta có * 1 1 1 1 1 * 2 2 2 2 n j j j n j j j t a x t b t a x t b = =  =    =  ∑ ∑ Cộng hai vế của hệ trên ⇒ * * 1 1 2 2 1 1 2 2 1 n n j j j j j j t a x t a x t b t b = = + = +∑ ∑ ⇒ * 1 1 2 2 1 1 2 2 1 ( ) n j j j j t a t a x t b t b = + = +∑ Chứng minh (2.28) ⇒ (2.27) Giả sử * * * * 1 2( , ,...., )nx x x x= là nghiệm nguyên không âm của (2.28). Đặt * * 1 n i ij j i j y a x b = = −∑ ; 1,2i = . Khi đó * *1 2,y y là các số nguyên.Vậy * *1 2,y y là nghiệm nguyên của ph−ơng trình 1 1 2 2 0t y t y+ = . Từ điều kiện 1) và định lý 1 ta có * 2 1y t q= ; * 1 2y t q= − ; q – nguyên. Ta chứng minh q = 0. • Thật vậy giả sử q > 0 thì q ≥ 1 (do q nguyên) ⇒ - t2 ≥ -t2q = * 1y Hay t2 ≤ * * 1 1 1 n i j j j y b a x = − = −∑ (2.29) Từ điều kiện 2) ta có 0 ≠ b1 – t2q = b1 + * * 1 1 n i j j j y a x = =∑ Mặt ≠ * 0jx ≥ , *jx - nguyên cho nên * 1 min 1 n j j j a x a = ≥∑ (2.30) - 42 - Từ (2.29) và (2.30) suy ra * 2 1 1 1 min 1 n j j j t b a x b a = ≤ − ≤ −∑ (trái với giả thiết 3). • T−ơng tự với q < 0 thì t1 ≤ - qt1 = - * 2y dẫn đến t1 ≤ b2 – amin (trái với giả thiết 3). Vậy q = 0 ⇒ * 1y = 0, *2y = 0 hay * 1 1 n j j i j a x b = =∑ , i = 1,2. Tức là *x là nghiệm của (2.27). Hệ quả: Đối với hệ * 1 n ij j i j a x b = =∑ ; 1,i m= (2.31) trong đó aij là các số nguyên không âm, bi > 0 ( 1,i m= ), luôn tìm đ−ợc các số nguyên t1, t2,...., tm sao cho tập nghiệm nguyên không âm của hệ (2.31) là trùng với tập các nghiệm nguyên không âm của ph−ơng trình 1 1 1 ( ) n m m i ij j i i j i i t a x t b = = = =∑ ∑ ∑ Ví dụ: Đ−a về một ph−ơng trình t−ơng đ−ơng với hệ sau đây: 1 2 1 2 1 2 1 2 3 2 10 4 11 3 3 13 , 0, x x x x x x x x nguyen + ≤  + ≤  + ≤  ≥ H−ớng dẫn: Đ−a vào các biến phụ 3x , 4x , 5x biến đổi các bất ph−ơng trình về ph−ơng trình ta thu đ−ợc hệ sau: 1 2 3 1 2 4 1 2 5 3 2 10 4 11 3 3 13 x x x x x x x x x + + =  + + =  + + = jx ≥ 0 , jx - nguyên, 1,5j = Hợp nhất hoá hai ph−ơng trình đầu của hệ trên: Tìm hai số (t1, t2) = 1, t1 không chia hết 11, t2 không chia hết 12. t1> 11- 1= 10, t2 > 10- 1 = 9. - 43 - Vậy t1 = 12, t2 = 11. Khi đó ta thu đ−ợc ph−ơng trình; 47x1 + 68x2 + 12x3 + 11x4 = 241. Hợp nhất hoá ph−ơng trình thu đ−ợc với ph−ơng trình thứ ba của hệ ban đầu : tìm đ−ợc t3 = 15, t4 = 242 thu đ−ợc ph−ơng trình sau: 1431x1 + 1746x2 + 180x3 + 165x4 242x5 = 6761. Điểm hạn chế của định lý 2 đòi hỏi không âm đối với tất cả các hệ số. Định lý d−ới đây khắc phục nh−ợc điểm đó nh−ng lại đòi hỏi các biến số phải giới nội. Định lý 3: Xét hệ ph−ơng trình: 1 , 1,2 (2.32) 0 , , 1, n ij j i j j j j a x b i x d x nguyen j n =  = =   ≤ ≤ − = ∑ trong đó ( , , , 1, 2, 1,ij i ja b d i j n= = ) là các số nguyên. Khi đó nếu t1, t2 là các số nguyên d−ơng, nguyên tố cùng nhau thoả mQn các điều kiện : 1. (t2, -t1) ∉ S. 2. (-t2, t1) ∉ S. trong đó S = {(y1,y2); i i iy y y − +≤ ≤ , iy - nguyên, i = 1,2} { }, : 0, 1, , 1,2 i i ij j i i ij j J y a d b J j a j n i − − − ∈ = − = < = =∑ { }, : 0, 1, , 1,2 i i ij j i i ij j J y a d b J j a j n i + + + ∈ = − = > = =∑ thì tập các lời giải của (2.32) sẽ trùng với tập các lời giải của hệ 1 1 2 2 1 1 2 2 1 ( ) n j j j j t a t a x t b t b = + = +∑ (2.33) 0 j jx d≤ ≤ , jx - nguyên, 1,j n= . Chứng minh. Tr−ớc hết ta nhận thấy rằng nếu (2.32) có nghiệm thì ta phải có - 44 - 1 0 , 1,2 i i i i n i ij j i ij j i ij j i ij j i jj J j J j J ij j i i j J y a d b a x b a x b a x b a d b y i + + − − + =∈ ∈ ∈ − ∈ = − ≥ − ≥ − = ≥ − ≥ − = = ∑ ∑ ∑ ∑ ∑ Vậy điều kiện cần để cho hệ (2.32) có nghiệm là: 0i iy y − +≤ ≤ (2.34) Giả sử * * * * 1 2( , ,...., )nx x x x= là nghiệm của (2.32) khi đó *x là nghiệm của (2.33) • Chứng minh (2.33) ⇒ (2.32) Giả sử * * * * 1 2( , ,...., )nx x x x= là nghiệm nguyên không âm của (2.33). Đặt * * 1 ; 1,2 n i ij j i j y a x b i = = − =∑ Khi đó * * 1 2,y y là các số nguyên. Vậy * * 1 2,y y là nghiệm nguyên của ph−ơng trình 1 1 2 2 0t y t y+ = .Từ định lý 1 ta có * 2 1y t q= ; * 1 2y t q= − ; q – nguyên và do * * 1 , 1,2 i i n ij j ij j i ij j i jj J j J a d a x b a x b i − + =∈ ∈ ≤ − ≤ − =∑ ∑ ∑ Hay * i ij j j J a d y −∈ ≤∑ * i ij j i j J a x b +∈ ≤ −∑ , 1,2i = . Nên * *1 2( , )y y S∈ ta chứng minh q = 0 • Thật vậy nếu q > 0 thì từ (-qt2, qt1) = * * 1 2( , )y y S∈ ta suy ra 1 2 2 10y qt t y − +≤ − ≤ − ≤ ≤ 2 1 1 20y t qt y − +≤ ≤ ≤ ≤ Tức là (-t2, t1) ∈ S (trái với điều kiện 2) • T−ơng tự nếu q < 0 thì từ * * 2 1 1 2( , ) ( , )qt qt y y S− = ∈ ta suy ra (t2, - t1)∈ S (trái với điều kiện 1). Vậy q = 0 ⇒ *1y = 0, * 2y = 0. Tức *x là nghiệm của hệ (2.32). Chú ý: Điều kiện của định lý 3 sẽ đ−ợc thoả mQn nếu ta chọn t1, t2 là hai số nguyên d−ơng, nguyên tố cùng nhau thoả mQn một trong số các điều kiện sau: • 1 2 2 11, 1t y t y + +≥ + ≥ + - 45 - ( ){ }kkkkkXx xayFxckk −+= −∈ 1max Trong đó, kí hiệu [ ]{ }kk ayX ,..,1,0= còn +Z là tập các số nguyên không âm. Nếu đặt: 0 ( ) 0, 0,F y y b= = (2.36) thì ta sẽ có công thức truy toán sau đây: ( ) ( ){ }kkkkkXxk xayFxcyF kk −+= −∈ 1max , 1, , 0,k n y b= = (2.37) Đối với bài toán cái túi ràng buộc đẳng thức 1 n j j j a x b = =∑ trong đó , ,j ja c b là nguyên d−ơng, hệ thức (2.37) vẫn đúng nếu ta thay đổi điều kiện đầu (2.36) bởi điều kiện sau 0 0(0) 0, ( ) , 0F F y y= = −∞ ≠ (2.38) Chúng ta có thể dẫn ra những hệ thức truy toán khác để tính Fk(y). Hệ thức Dantzig. { }1 1 ( ), ( ) ;( ) ( ) ; k k k k k k k k max F y c F y a y a F y F y y a − −  + − ≥ =  < Với điều kiện đầu (2.36) hoặc (2.38) Để giải bài toán cái túi bằng cách dùng hệ thức Dantzig nói trên ta cần tính Fk(y) với ∀ k, y, sau đó xét cách thu đ−ợc Fn(b). Để tìm các giá trị của các thành phần * jx trong ph−ơng án tối −u * * * * 1 2( , ,..., )j nx x x x= . Ta xét quá trình này nh− sau: Lập bảng 1: Với các giá trị Fk(y) ( 0 , , 0 , )k n y b= = . Lập bảng 2: Với các giá trị jk(y) đ−ợc xác định nh− sau: 11 1 0 , ( ) 0( ) 1, ( ) 0 k h i F yj y k h i F y = =  ≠ 1 1 1 ( ), ( ) ( )( ) ( ) ( ) k k k k k k j y khi F y F yj y k khi F y F y − − −  = =  ≠ - 46 - Bảng 2 sẽ cho phép xác định các giá trị của các biến số * jx trong ph−ơng án tối −u. Giá trị jn(b) bằng chỉ số lớn nhất của biến số d−ơng trong ph−ơng án tối −u. Vì vậy đặt: 0, : ( ) 1, ( ) n j n j j b j n x j j b ∀ < ≤ =  = Xác định ( )( )nn j bj b a δ− = . Nếu ( )nj bδ = thì ( ) ( ) 1n nj b j bx x= + . Ng−ợc lại, đặt ( ) ( ) 0, : ( ) ( ) 1; ( ) n n n j b n j n j b j j b a j j b x j j b a ∀ − < < =  = − Tiếp tục thủ tục trên cho đến khi gặp jn(0). Ví dụ: Giải bài toán cái túi sau: 1 2 3 4( ) 3 5 9F x x x x x max= + + + → 1 2 3 4 52 3 4 7 10x x x x x+ + + + = 0jx ≥ , jx - nguyên, 1,5j = . Ta có: 0(0) 0F = , 0( ) , 0F y y= −∞ ≠ Khi k = 1 ta có: 1 00 : (0) 1 0 2 y F  = = =   1 0 11: (1) 1 (1) 2 y F F = = + = −∞   1 0 22: (2) 1 (0) 1 2 y F F = = + =   1 0 33: (3) 1 (1) 2 y F F = = + = −∞   1 0 44: (4) 1 (0) 2 2 y F F = = + =   1 0 55: (5) 1 (1) 2 y F F = = + = −∞   - 47 - 1 0 66 : (6) 1 (0) 3 2 y F F = = + =   1 0 77 : (7) 1 (1) 2 y F F = = + = −∞   1 0 88 : (8) 1 (0) 4 2 y F F = = + =   1 0 99 : (9) 1 (1) 2 y F F = = + = −∞   1 0 1010 : (10) 1 (0) 5 2 y F F = = + =   Khi k = 2 ta có: { }2 10 : (0) 3.0 (0) 0y F max F= = + = { }2 11: (1) 3.0 (1)y F max F= = + = −∞ { }2 12 : (2) 3.0 (2) 1y F max F= = + = { } { }2 1 13: (3) 3.0 (3);3.1 (0) ;3 3y F max F F max= = + + = −∞ = { } { }2 1 14 : (4) 3.0 (4);3.1 (1) 2, 2y F max F F max= = + + = −∞ = { } { }2 1 15 : (5) 3.0 (5);3.1 (2) ,4 4y F max F F max= = + + = −∞ = { } { }2 1 1 16 : (6) 3.0 (6);3.1 (3);3.2 (0) 3, ,6 6y F max F F F max= = + + + = −∞ = { } { }2 1 1 17 : (7) 3.0 (7);3.1 (4);3.2 (1) ,5, 5y F max F F F max= = + + + = −∞ −∞ = { } { }2 1 1 18 : (8) 3.0 (8);3.1 (5);3.2 (2) 4, ,7 7y F max F F F max= = + + + = −∞ = { } { }2 1 1 1 19 : (9) 3.0 (9);3.1 (6);3.2 (3);3.3 (0) ,6, ,9 9y F max F F F F max= = + + + + = −∞ −∞ = { } { }2 1 1 1 110 : (10) 3.0 (10);3.1 (7);3.2 (4);3.3 (1) 5, ,8, 8y F max F F F F max= = + + + + = −∞ −∞ = Khi k = 3 ta có: { }3 20 : (0) 5.0 (0) 0y F max F= = + = { }3 21: (1) 5.0 (1)y F max F= = + = −∞ { }3 22 : (2) 5.0 (2) 1y F max F= = + = { }3 23: (3) 5.0 (3) 3y F max F= = + = { } { }3 2 24 : (4) 5.0 (4);5.1 (0) 2,5 5y F max F F max= = + + = = { } { }3 2 25 : (5) 5.0 (5);5.1 (1) 4, 4y F max F F max= = + + = −∞ = - 48 - { } { }3 2 26 : (6) 5.0 (6);5.1 (2) 6;6 6y F max F F max= = + + = = { } { }3 2 27 : (7) 5.0 (7);5.1 (3) 5,8 8y F max F F max= = + + = = { } { }3 2 2 28 : (8) 5.0 (8);5.1 (4);5.2 (0) 7,7,10 10y F max F F F max= = + + + = = { } { }3 2 2 29 : (9) 5.0 (9);5.1 (5);5.2 (1) 9,9, 9y F max F F F max= = + + + = −∞ = { } { }3 2 2 210 : (10) 5.0 (10);5.1 (6);5.2 (2) 8,11,11 11y F max F F F max= = + + + = = Khi k = 4 ta có: { }4 30 : (0) 9.0 (0) 0y F max F= = + = { }4 31: (1) 9.0 (1)y F max F= = + = −∞ { }4 32 : (2) 9.0 (2) 1y F max F= = + = { }4 33: (3) 9.0 (3) 3y F max F= = + = { }4 34 : (4) 9.0 (4) 5y F max F= = + = { }4 35 : (5) 9.0 (5) 4y F max F= = + = { }4 36 : (6) 9.0 (6) 6y F max F= = + = { } { }4 3 37 : (7) 9.0 (7);9.1 (0) 8,9 9y F max F F max= = + + = = { } { }4 3 38 : (8) 9.0 (8);9.1 (1) 10, 10y F max F F max= = + + = −∞ = { } { }4 3 39 : (9) 9.0 (9);9.1 (2) 9,10 10y F max F F max= = + + = = { } { }4 3 310 : (10) 9.0 (10);9.1 (3) 11,12 12y F max F F max= = + + = = Khi k = 5 ta xét ngay y = 10 vì không cần tính các giá trị trung gian 5 ( )F y ,y <1 0 { { } 5 4 4 4 4 4 4 4 4 4 4 410: (10) (10); (9); (8); (7); (6); (5); (4); (3); (2); (1); (0) 12,10,10,9,6,4,5,3,1, ,0 12 y F max F F F F F F F F F F F max = = = = −∞ = Tìm ph−ơng án tối −u: 5(10) 12F = với 5 0x = và 4(10) 12F = 4(10) 12F = với 4 1x = và 3(3) 3F = 3(3) 3F = với 3 0x = và 2(3) 3F = 2(3) 3F = với 2 1x = và 1(0) 0F = 1(0) 0F = với 1 0x = - 49 - Vậy ph−ơng án tối −u: * (0,1,0,1,0)x = , *( ) 12F x = . Kết luận ch−ơng 2: Một trong những thành tựu nổi bật của lý thuyết tối −u tổng quát vào những năm 70 của thập kỷ 20 là việc xây dựng lý thuyết giải lớp bài toán quy hoạch nguyên tuyến tính. Các nhà khoa học đi tiên phong trong lĩnh vực này là Gomory, Land, Doig.... Các vấn đề lý thuyết đ−ợc trình bày ở ch−ơng 2 là thành tựu mới nhất, cập nhật nhất của lý thuyết tối −u tuyến tính nói riêng; lý thuyết quy hoạch nguyên tuyến tính nói chung. Trong quá trình trình bày các kết quả nghiên cứu chúng tôi đQ cố gắng đảm bảo tính chi tiết, tính cụ thể của các định lý các thuật toán mà các tài liệu tham khảo chỉ trình bày khát quát, vắn tắt nhằm giúp ng−ời đọc hiểu một cách đầy đủ và sâu sắc nhất các vấn đề khi đọc tài liệu - 50 - Ch−ơng 3 Bài tập vận dụng 3.1. Bài tập vận dụng thuật toán cắt Gomory Bài tập 1: Giải bài toán sau Một nhà máy sản xuất xe máy cần sản xuất hai dòng xe Hon Đa và Yamaha. Biết nguyên liệu nhà máy sử dụng để sản xuất hai dòng xe trên là không quá 38 đơn vị nguyên liệu loại 1 và không quá 7 đơn vị nguyên liệu loại 2. Để sản xuất một chiếc xe dòng Hon Đa cần tốn 2 đơn vị nguyên liệu loại 1; 1 đơn vị nguyên liệu loại 2 và tiền lQi thu đ−ợc khi bán một chiếc xe dòng Hon Đa là 1 đơn vị tiền, để sản xuất một chiếc xe máy dòng Yamaha cần tốn 11 đơn vị nguyên liệu loại 1; 1 đơn vị nguyên liệu loại 2 và tiền lQi thu đ−ợc khi bán một chiếc xe dòng Yamaha là 2 đơn vị tiền. HQy giúp nhà máy lựa chọn sản xuất dòng xe máy nào; với số l−ợng là bao nhiêu để thu đ−ợc lợi nhụân cao nhất. Lời giải Mô hình toán học của bài toán nh− sau 1 2( ) 2 maxf x x x= + → 1 2 1 2 2 11 38 7 x x x x + ≤  + ≤ 0jx ≥ , jx - nguyên, j =1,2 Đ−a bài toán về dạng chính tắc và giải bài toán bỏ qua điều kiện jx - nguyên. 1 2( ) 2f x x x− = − − → min 1 2 3 1 2 4 2 11 38 7 x x x x x x + + =  + + = 0, 1,4jx j≥ = Ta có bảng đơn hình d−ới đây: - 51 - Cơ sở jc cơ sở Ph. án -1 A1 -2 A2 0 A3 0 A4 A3 A4 0 0 38 7 2 1 [11] 1 1 0 0 1 j∆ 1 2 0 0 A2 A4 -2 0 38/11 39/11 2/11 [9/11] 1 0 1/11 -1/11 0 1 j∆ 7/11 0 -2/11 0 A2 A1 -2 -1 8/3 13/3 0 1 1 0 1/9 -1/9 -2/9 11/9 j∆ 0 0 -1/9 -7/9 Trong ph−ơng án tối −u các biến cơ sở đều không nguyên. Chọn biến cơ sở 2x và xây dựng đ−ợc lát cắt (theo công thức (2.16)): 3 4 2 1 2 2( ) ( ) ( ) 0 3 9 9 9 L x x x− −  = − − − − − − ≥     ( )L x = 3 4 2 1 7( ) ( ) 0 3 9 9 x x− − − − − ≥ Đ−a vào biến 5 0x ≥ và chuyển ràng buộc về đẳng thức 5 3 4 2 1 7( ) ( ) 3 9 9 x x x= − − − − − . Viết ràng buộc này vào cuối bảng sau. Cơ sở jc cơ sở Ph. án -1 A1 -2 A2 0 A3 0 A4 0 A5 A2 A1 A5 -2 -1 0 8/3 13/3 -2/3 0 1 0 1 0 0 1/9 -1/9 [-1/9] -2/9 11/9 -7/9 0 0 1 j∆ 0 0 -1/9 -7/9 0 A2 A1 A3 -2 -1 0 2 5 6 0 1 0 1 0 0 0 0 1 1 2 7 1 -1 -9 j∆ 0 0 0 -4 -1 - 52 - Vậy nhà máy nên sản xuất 5 chiếc xe dòng Hon Đa, 2 chiếc xe dòng Yamaha thì tiễn lQi thu đ−ợc là lớn nhất ( là 9 đơn vị tiền). Bài tập 2: 1 2( ) 2f x x x max= + → 1 2 1 2 1 2 4 5 22 9 3 33 1 0, 1, 2j x x x x x x x j + ≤  + ≤  − + ≤  ≥ = jx , jx - nguyên, j = 1,2. Lời giải Đ−a bài toán về dạng chính tắc và giải bài toán bỏ qua điều kiện jx - nguyên ta có bảng đơn hình tối −u sau: Cơ sở jc c. s Ph. án -1 A1 -2 A2 0 A3 0 A4 0 A5 A1 A4 A2 -1 0 -2 17/9 22/3 26/9 1 0 0 0 0 1 1/9 -4/3 1/9 0 1 0 -5/9 11/3 4/9 j∆ 0 0 -1/3 0 -1/3 Trong ph−ơng án tối −u các biến cơ sở đều không nguyên. Chọn biến cơ sở 1x xây dựng lát cắt vì 1 2 4 8 1 9 3 b b b   = = > =        3 5 8 1 4( ) ( ) ( ) 0 9 9 9 L x x x−= − − − − ≥ Đ−a vào biến 6x ≥ 0 và chuyển ràng buộc về dạng đẳng thức: 6 3 5 8 1 4( ) ( ) 9 9 9 x x x − = − − − − . Viết ràng buộc này vào cuối của bảng sau. Cơ sở cj cơ sở Ph−ơng án -1 A1 -2 A2 0 A3 0 A4 0 A5 0 A6 - 53 - A1 A4 A2 -1 0 -2 17/9 22/3 26/9 1 0 0 0 0 1 1/9 -4/3 1/9 0 1 0 -5/9 11/3 4/9 0 0 0 A6 0 -8/9 0 0 -1/9 0 [-4/9] 1 j∆ 0 0 -1/3 0 -1/3 0 A1 A4 A2 A5 -1 0 -2 0 3 0 2 2 1 0 0 0 0 0 1 0 1/4 -9/4 0 1/4 0 1 0 0 0 0 0 1 -5/4 33/4 1 -9/4 j∆ 0 0 -1/4 0 0 -3/4 Ph−ơng án tối −u * (3,2)x = , *( ) 7f x = Bài tập 3: 1 2 3 4 5( ) 2 6 4 2 3 minf x x x x x x= − + + − + → 1 2 3 2 3 4 2 5 2 4 52 4 2 6 3 36 x x x x x x x x + + =  + + =  + = 0jx ≥ , nguyên, 1,5j = Lời giải Giải bài toán quy hoạch tuyến tính bỏ qua điều kiện jx - nguyên, 1,5j = ta thu đ−ợc bảng đơn hình tối −u sau: Cơ sở cj cơ sở Ph. án 2 A1 -6 A2 -4 A3 2 A4 -3 A5 A1 A4 A5 2 2 -3 52 60 36 1 0 0 2 4 3 [4] 2 0 0 1 0 0 0 1 j∆ 0 9 16 0 0 A3 A4 A5 -4 2 -3 13 34 36 1/4 -1/2 0 1/2 [3] 3 1 0 0 0 1 0 0 0 1 j∆ -4 1 0 0 0 - 54 - A3 A2 A5 -4 -6 -3 22/3 34/3 2 1/3 -1/6 1/2 0 1 0 1 0 0 -1/6 1/3 -1 0 0 1 j∆ -23/6 0 0 -1/3 0 Trong ph−ơng án tối −u các biến cơ sở đều không nguyên. Chọn biến cơ sở 2x và xây dựng lát cắt theo (2.16) 1 4 1 5 1( ) ( ) ( ) 0 3 6 3 L x x x−= − − − − ≥ Đ−a vào biến 6x ≥ 0 và chuyển ràng buộc về dạng đẳng thức: 6 1 4 1 5 1( ) ( ) 3 6 3 x x x − = − − − − . Viết ràng buộc này vào cuối bảng sau. Cơ sở jc cơ sở Ph. án 2 A1 -6 A2 -4 A3 2 A4 -3 A5 0 A6 A3 A2 A5 - 4 - 6 - 3 22/3 34/3 2 1/3 -1/6 1/2 0 1 0 1 0 0 -1/6 1/3 -1 0 0 1 0 0 0 A6 0 -1/3 5/6 0 0 [-1/3] 0 1 j∆ -23/6 0 0 -1/3 0 0 A3 A2 A5 A4 - 4 - 6 - 3 2 15/2 11 3 1 -1/12 2/3 -2 -5/2 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 - 1/2 1 -3 - 3 j∆ - 8/3 0 0 0 0 - 1 Trong ph−ơng án tối −u 3 15 2 b = không nguyên, chọn biến cơ sở 3x để xây dựng lát cắt. 1 6 1 11 1( ) ( ) ( ) 0 2 12 2 L x x x−= − − − − ≥ Đ−a vào biến 7 0x ≥ và chuyển ràng buộc về dạng đẳng thức: - 55 - 7 1 6 1 11 1( ) ( ) 2 12 2 x x x − = − − − − . Viết ràng buộc này vào cuối bảng sau. Cơ sở jc cơ sở Ph. án 2 A1 -6 A2 - 4 A3 2 A4 -3 A5 0 A6 0 A7 A3 A2 A5 A4 - 4 - 6 - 3 2 15/2 11 3 1 -1/12 2/3 -2 -5/2 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 - 1/2 1 -3 - 3 0 0 0 0 A7 0 -1/2 -11/12 0 0 0 0 [- 1/2] 1 j∆ - 8/3 0 0 0 0 - 1 0 A3 A2 A5 A4 A6 - 4 - 6 - 3 2 0 8 10 6 4 1 5/6 -7/6 7/2 3 11/6 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 2 -6 -6 -2 j∆ -5/6 0 0 0 0 0 -10 Ph−ơng án tối −u * (0,10,8,4,6)x = , *( ) 102f x =− . Bài tập 4 1 2 3( ) 10 14 21 minf x x x x= + + → 1 2 3 1 2 3 1 2 3 2 2 7 14 8 11 9 12 9 6 3 10 x x x x x x x x x + + ≥  + + ≥  + + ≥ 0jx ≥ jx - nguyên, 1,3j = Lời giải Đ−a bài toán về dạng chính tắc, ta có: 1 2 3( ) 10 14 21 minf x x x x= + + → 1 2 3 4 1 2 3 5 1 2 3 6 2 2 7 14 8 11 9 12 9 6 3 10 x x x x x x x x x x x x + + − =  + + − =  + + − = - 56 - 0jx ≥ , jx - nguyên, 1,6j = Giải bài toán trên với điều kiện bỏ đi điều kiện jx nguyên ta có bảng đơn hình tối −u sau đây: Cơ sở cj c.s Ph−ơng án 10 A1 14 A2 21 A3 0 A4 0 A5 0 A6 A1 A5 A3 10 0 21 28/57 26/3 106/57 1 0 0 12/19 -5 2/19 0 0 1 1/19 -1 -3/19 0 1 0 -7/57 -2/3 2/57 j∆ 0 -104/19 0 -53/19 0 -28/57 Trong ph−ơng án tối −u các biến { }3,5,1, ∈jx j đều không nguyên. Chọn biến cơ sở 5x và xây dựng đ−ợc lát cắt: ( ) 62 1( ) 03 3L x x= − − − ≥ Đ−a vào biến 07 ≥x và chuyển ràng buộc trên về dạng đẳng thức ta thu đ−ợc: 7 6 2 1 ( ) 3 3 x x= − − − . Viết ràng buộc này vào dòng cuối cùng của bảng sau ta thu đ−ợc bảng mới: Cơ sở jc c.s Ph. án 10 A1 14 A2 21 A3 0 A4 0 A5 0 A6 0 A7 A1 A5 A3 10 0 21 28/57 26/3 106/57 1 0 0 12/19 -5 2/19 0 0 1 1/19 -1 -3/19 0 1 0 -7/57 -2/3 2/57 0 0 0 A7 0 -2/3 0 0 0 0 0 [-1/3] 1 j∆ 0 -104/19 0 -53/19 0 -28/57 0 - 57 - Giải bài toán bằng thuật toán đơn hình đối ngẫu. Ph−ơng án tìm đ−ợc 14 102( ,0, ,0,10, 2) 19 57 x = ch−a nguyên. Chọn biến cơ sở 1x để xây dựng lát cắt, đ−a vào biến 8x , các tính toán đ−ợc thể hiện trong bảng sau: Cơ sở cj c.s Ph. án 10 A1 14 A2 21 A3 0 A4 0 A5 0 A6 0 A7 0 A8 A1 A5 A3 10 0 21 14/19 10 102/57 1 0 0 12/19 -5 2/19 0 0 1 1/19 -1 -3/19 0 1 0 0 0 0 -7/19 - 2 2/19 0 0 0 A6 0 2 0 0 0 0 0 0 - 3 0 A8 0 - 14/19 0 -12/19 0 -1 /19 0 1 [-12/19] 1 j∆ 0 -104/19 0 -53/19 0 0 -28/ 19 0 Giải bài toán bằng thuật toán đơn hình đối ngẫu. Ph−ơng án tìm đ−ợc 7 5 37 11 7( ,0, ,0, , , ) 6 3 3 2 6 x = ch−a nguyên. Chọn biến cơ sở 3x để xây dựng lát cắt, đ−a vào biến 9x , các tính toán đ−ợc thể hiện trong bảng: Cơ sở cj c.s Ph. án 10 A1 14 A2 21 A3 0 A4 0 A5 0 A6 0 A7 0 A8 0 A9 A1 A5 A3 10 0 21 7/6 37/3 5/3 1 0 0 1 -3 0 0 0 1 1/12 - 5/6 - 1/6 0 1 0 0 0 0 0 0 0 - 7/12 -19/6 1/6 0 0 0 A6 0 11/2 0 3 0 1/4 0 1 0 -19/4 0 A7 0 7/6 0 1 0 1/12 0 0 1 - 19/12 0 A9 0 - 2/3 0 0 0 [-5/6] 0 0 0 - 1/6 1 j∆ 0 - 4 0 - 46/57 0 0 0 - 7/3 0 Giải bài toán bằng thuật toán đơn hình đối ngẫu. Ph−ơng án tìm đ−ợc 11 9 4 53 11 ,0, , ,13, , 10 5 5 10 10 x   =     ch−a nguyên. Chọn biến cơ sở 3x để xây dựng lát cắt, đ−a vào biến 10x , các tính toán đ−ợc thể hiện trong bảng: - 58 - Cơ sở cj c.s Ph. án 10 A1 14 A2 21 A3 0 A4 0 A5 0 A6 0 A7 0 A8 0 A9 0 A10 A1 A5 A3 10 0 21 11/10 13 9/5 1 0 0 1 -3 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 - 3/5 - 3 1/5 1/10 -1 -1/5 0 0 0 A6 0 53/10 0 3 0 0 0 1 0 - 24/5 3 /10 0 A7 0 11/10 0 1 0 1 0 0 1 - 8/5 1 /10 0 A4 0 4/5 0 0 0 0 0 0 0 1/5 - 6/5 0 A10 0 - 4/5 0 0 0 0 0 0 0 - 1/5 [-4/5] 1 j∆ 0 - 4 0 0 0 0 0 - 9/5 - 16/5 0 A1 A5 A3 10 0 21 1 14 2 1 0 0 1 -3 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 - 5/8 - 11/4 1/4 0 0 0 1/8 - 5/4 - 1/4 A6 0 5 0 3 0 0 0 1 0 - 39/8 0 3/8 A7 0 1 0 1 0 1 0 0 1 13/8 0 1/8 A4 0 2 0 0 0 0 0 0 0 1/2 0 - 3/2 A9 0 1 0 0 0 0 0 0 0 1/4 1 - 5/4 j∆ 0 - 4 0 0 0 0 0 -1 0 - 4 Ph−ơng án tối −u ( )* 1,0,2,2,14,5x = , *( ) 52f x = 3.2. Bài tập vận dụng thuật toán Land - Doig Giải các bài toán quy hoạch nguyên sau bằng ph−ơng pháp nhánh và cận của Land-Doig Bài tập 5: ( ) 1 23 minf x x x= − + → 1 2 1 2 1 2 3 2 3 5 4 10 2 5 x x x x x x − ≤  + ≥  + ≤ - 59 - 0jx ≥ , jx - nguyên, Lời giải B−ớc chuẩn bị: Giải bài toán ( )P ′ bỏ qua điều kiện jx - nguyên ta thu đ−ợc ph−ơng án tối −u: 0 13 9( , ) 7 7 x = , 13 9( ) 3 5 7 7 m D  = − ì + = −   . B−ớc 1: Vì 0x không nguyên và có: 0 1 13 7 x = không nguyên ⇒ 0 1 13 1 7 x    = =     . Ta chia tập D thành hai tập : { }11 1/ 1D x D x= ∈ ≤ { }12 1/ 2D x D x= ∈ ≥ Giải bài toán ( )11P ′ ta đ−ợc ph−ơng án tối −u: 1 5(1, )4x = và tìm đ−ợc 1 1 1 5( ) ( ) 3 1 4 m D f x   = = − + = −     Giải bài toán 12( )P ′ thấy φ=12D nên ( ) +∞=12Dm . B−ớc 2: Ta phân nhánh 11D thành 2 tập: { }2 11 1 2/ 1D x D x= ∈ ≤ { }2/ 21122 ≥∈= xDxD Vì 12 5 14x    = =     Giải bài toán 21( )P ′ thấy 21D =∅ nên 21( )m D =+∞ Giải bài toán 22( )P ′ ta đ−ợc ph−ơng án tối −u 2 (1,2)x = và tìm đ−ợc kỷ lục 2 2 2( ) ( ) 1m D f x= =− . Sơ đồ phân nhánh đến b−ớc này nh− sau: - 60 - m= -5 m= -1 m =+∞ m = ∞+ m = -1 Ta thấy cận d−ới nhỏ nhất của các đỉnh treo là: 1 21 2( ) ( ) 1m D m D= = − . Tại 22D ta ghi đ−ợc kỷ lục 2 2 2( ) ( ) 1m D f x= = − . 2 (1,2)x = thoả mQn điều kiện nguyên nên nó là ph−ơng án tối −u của bài toán đQ cho, thuật toán kết thúc ( ) ( )* *1,2 ; 1x f x= = − . Bài tập 6 ( ) 1 2 minf x x x=− − → 1 2 1 2 1 2 2 11 38 7 4 5 5 x x x x x x + ≤  + ≤  − ≤ Lời giải B−ớc chuẩn bị. Giải bài toán ( )P ′ bỏ đi điều kiện nguyên của các biến số ta đ− ợc ph−ơng án tối −u:       = 9 23 , 9 400x ; ( ) 0 40 23( ) 79 9m D f x   = = − − = −     B−ớc 1. Vì 0x không nguyên và có: [ ] 49 40 9 40 0 1 0 1 =    =⇒= xx .Ta chia D thành 2 tập: { }4/ 111 ≤∈= xDxD { }5/ 112 ≥∈= xDxD Giải bài toán ( )11P ′ ta đ−ợc ph−ơng án tối −u: D 1 1D 2 1D 1 2D 2 2D - 61 -       = 11 30 ,41x và tìm đ−ợc ( )1 11 74( ) 611m D f x   = = − = −     . Giải bài toán( )12P ′ thấy φ=12D nên ( ) +∞=12Dm B−ớc 2. Ta phân nhánh 11D thành 2 tập: { }2/ 21121 ≤∈= xDxD { }2 12 1 2/ 3D x D x= ∈ ≥ vì [ ] 211 301 2 =    =x Giải bài toán( )21P ′ ta đ−ợc ph−ơng án tối −u:       = 2, 4 152x và tìm đ−ợc ( )2 21 23( ) 54m D f x   = = − = −     . Giải bài toán ( )22P ′ ta đ−ợc ph−ơng án tối −u:       = 3, 2 52 x và tìm đ−ợc ( ) 222 11( ) 52m D f x   = = − = −      . Vì ( ) =22Dm ( )21Dm nên ta phân nhánh tại đâu cũng đ−ợc. B−ớc 3: Chia 21D thành hai tập: { }3/ 12131 ≤∈= xDxD { }4/ 12232 ≥∈= xDxD vì [ ] 341521 ==x Giải bài toán ( )31P ′ ta đ−ợc ph−ơng án tối −u: ( )2,33 =x và tìm đ−ợc kỷ lục: ( ) ( )3 31 5m D f x= = − . Giải bài toán ( )32P ′ ta thấy φ=32D nên ( ) +∞=32Dm . Ta thấy ( ) ( )3 21 2 5m D m D= = − . Tại 31D ta ghi đ−ợc kỷ lục: ( ) ( )3 31 5m D f x= = − . ( )2,33 =x thoả mQn điều kiện nguyên nên nó là ph−ơng án tối −u của bài toán đQ cho, thuật toán kết thúc * (3,2)x = , *( ) 5f x =− Bài tập 7 ( ) 1 2 33 3f x x x x max= − + → - 62 - 1 2 3 1 2 1 2 3 2 4 4 3 2 3 2 3 x x x x x x x x + − ≤  − ≤  − + + ≤ 0,j jx x≥ - nguyên, 1,3j = Lời giải B−ớc chuẩn bị: Giải bài toán ( )P ′ bỏ đi điều kiện nguyên của các biến số ta đ− ợc ph−ơng án tối −u: 0 1 9( ,0, ) 2 2 x = , 0 1 9( ) ( ) 3 14 2 2 m D f x   = = + ì =     B−ớc 1. Vì 0x không nguyên và có: 0 3 9 2 x = ⇒ 03 9 4 2 x    = =     . Ta chia D thành hai tập: { }11 3/ 4D x D x= ∈ ≤ { }12 3/ 5D x D x= ∈ ≥ Giải bài toán ( )11P ′ ta đ−ợc ph−ơng án tối −u: 1 1( ,0,4)2x = và tìm đ−ợc 1 1 1 1( ) ( ) 3 4 12 2 m D f x   = = + ì =     . Giải bài toán ( )12P ′ ta đ−ợc ph−ơng án tối −u 1 (2,2,5)x = và tìm đ−ợc 11 2( ) ( ) 11m D f x = =   . Ta thấy 12( )m D = 11 < 11( )m D =12 nên ta phân nhánh tại 11D . B−ớc 2: Chia tập 11D thành hai tập: { }2 11 1 1/ 0D x D x= ∈ ≤ ; Vì 11 12x = ⇒ 11 1 0 2 x    = =     { }2 12 1 1/ 1D x D x= ∈ ≥ ; Giải bài toán ( )21P ′ thấy 21D = ∅ nên 21( )m D = +∞ . Giải bài toán 22( )P ′ ta đ−ợc ph−ơng án tối −u 2 2(1, , 4)3x = và tìm đ−ợc 2 2( ) 11m D = - 63 - Ta thấy 12( )m D = 22( ) 11m D = mà tại 12D có 1 (2,2,5)x = thoả mQn điều kiên nguyên của bài toán đQ cho. Vậy tại 12D ta ghi đ−ợc kỷ lục 11 2( ) ( ) 11m D f x = =   và 1 (2,2,5)x = là ph−ơng án tối −u của bài toán đQ cho, thuật toán kết thúc * *(2, 2,5), ( ) 11x f x= = . Bài tập 8 1 2( ) 2f x x x max= + → 1 2 1 2 1 2 4 5 22 3 11 1 x x x x x x + ≤  + ≤  − + ≤ 0jx ≥ , jx - nguyên, 1, 2j = Lời giải B−ớc chuẩn bị: Giải bài toán ( )P ′ bỏ đi điều kiện nguyên của các biến số ta có bảng đơn hình tối −u sau: Cơ sở jc c.s Ph−ơng án - 1 A1 -2 A2 0 A3 0 A4 0 A5 A1 A4 A2 -1 0 -2 17/9 22/3 26/9 1 0 0 0 0 1 1/9 - 4/3 1/9 0 1 0 - 5/9 11/3 4/9 j∆ 0 0 - 1/3 0 - 1/3 Ph−ơng án tối −u: 0 17 26( , ) 9 9 x = . 0 17 26( ) ( ) 2 7 9 9 m D f x   = = − − ì = −     B−ớc 1. Vì 0x không nguyên và có 01 17 1 9 x    = =     .Ta chia D thành hai tập: { }11 1/ 1D x D x= ∈ ≤ { }12 1/ 2D x D x= ∈ ≥ Giải bài toán ( )11P ′ ta đ−ợc ph−ơng án tối −u: 1 (1,2)x = và tìm đ−ợc 1 11( ) ( ) 5m D f x = =  . - 64 - Giải bài toán 12( )P ′ ta đ−ợc ph−ơng án tối −u: 1 14(2, ) 5 x = và tìm đ−ợc 1 2 2 14( ) ( ) 2 2 7 5 m D f x   = = + ì =     . Vì 1 12 1( ) 7 ( ) 5m D m D= > = nên ta phân nhánh tại 12D . B−ớc 2: Ta phân nhánh 12D thành hai tập: { }2 11 2 2/ 2D x D x= ∈ ≤ { }2 12 2 2/ 3D x D x= ∈ ≥ Giải bài toán 21( )P ′ ta đ−ợc ph−ơng án tối −u: 2 (3,2)x = và tìm đ−ợc 2 21( ) ( ) 7m D f x = =  . Giải bài toán 22( )P ′ ta thấy 22D = ∅ và 22( )m D = +∞ . Đến b−ớc này ta thấy 2 1 2 1( ) 7 ( ) 5m D m D= > = .Vậy tại 22D ta ghi đ−ợc kỷ lục 2 2( ) 7m D = và 2 (3,2)x = thoả mQn điều kiện nguyên nên nó là ph−ơng án tối −u của bài toán đQ cho, thuật toán kết thúc * (3,2)x = , *( ) 7f x = . 3.3. Bài tập đ−a bài toán về bài toán cái túi để giải Bài tập 9: Giải bài toán sau Một nhà máy sản xuất vật liệu xây dựng cần sản xuất 4 loại vật liệu xây dựng. Biết nguyên liệu nhà máy sử dụng cần để sản xuất 4 loại nguyên liệu trên là không quá 20 tấn. Nguyên liệu nhà máy sử dụng để sản xuất một vật liệu xây dựng loại 1 là 6 tấn và lợi nhuận mà nhà máy thu đ−ợc từ một vật liệu loại 1 là 2 đơn vị tiền, nguyên liệu nhà máy sử dụng để sản xuất một vật liệu xây dựng loại 2 là 3 tấn và lợi nhuận nhà máy thu đ−ợc từ một vật liệu loại 2 là 7 đơn vị tiền, nguyên liệu nhà máy sử dụng để sản xuất một vật liệu loại 3 là 2 tấn và lợi nhuận nhà máy thu đ−ợc từ một vật liệu loại 3 là 3 đơn vị tiền, nguyên liệu nhà máy sử dụng để sản xuất một vật liệu xây dụng loại 4 là 1 tấn và lợi nhuận thu đ−ợc từ một vật liệu loại 4 là 1 đơn vị tiền. HQy giúp nhà máy lựa chọn sản xuất loại vật liệu nào và với số l−ợng là bao nhiêu để nhà máy thu đ−ợc lợi nhuận lớn nhất. Lời giải Mô hình toán học của bài toán trên nh− sau: - 65 - 1 2 3 4( ) 2 7 3F x x x x x max= + + + → 1 2 3 46 3 2 20x x x x+ + + ≤ 0jx ≥ , jx - nguyên, 1, 4j = Vận dụng ph−ơng pháp giải bài toán cái túi để giải bài toán trên. Khi k = 1 ta có: ( ) 00:0 1 == Fy ( ) 00.2 6 121:1 1 ==    == Fy ( ) 00.2 6 222:2 1 ==    == Fy ( ) 00.2 6 323:3 1 ==    == Fy ( ) 00..2 6 424:4 1 ==    == Fy ( ) 00.2 6 525:5 1 ==    == Fy ( ) 21.2 6 626:6 1 ==    == Fy ( ) 21.2 6 727:7 1 ==    == Fy ( ) 21.2 6 828:8 1 ==    == Fy ( ) 21.2 6 929:9 1 ==    == Fy ( ) 21.2 6 10210:10 1 ==    == Fy ( ) 21.2 6 11211:11 1 ==    == Fy ( ) 42.2 6 12212:12 1 ==    == Fy - 66 - ( ) 42.2 6 13213:13 1 ==    == Fy ( ) 42.26 14214:14 1 ==    == Fy ( ) 42.2 6 15215:15 1 ==    == Fy ( ) 42.2 6 16216:16 1 ==    == Fy ( ) 42.2 6 17217:17 1 ==    == Fy ( ) 63.2 6 18218:18 1 ==    == Fy ( ) 63.2 6 19219:19 1 ==    == Fy ( ) 63.2 6 20220:20 1 ==    == Fy Khi k = 2 ta có: ( ) 00:0 2 == Fy ( ) ( ){ } 010.7max1:1 12 =+== FFy ( ) ( ){ } 020.7max2:2 12 =+== FFy ( ) ( ) ( ){ } 701.7;30.7max3:3 112 =++== FFFy ( ) ( ) ( ){ } 711.7;40.7max4:4 112 =++== FFFy ( ) ( ) ( ){ } 721.7;50.7max5:5 112 =++== FFFy ( ) ( ) ( ) ( ){ }=+++== 02.7;31.7;60.7max6:6 1112 FFFFy { } 14014;07;20max =+++ ( ) ( ) ( ) ( ){ }=+++== 12.7;41.7;70.7max7:7 1112 FFFFy { }max 0 2;7 0;14 0 14= + + + = ( ) ( ) ( ) ( ){ }=+++== 22.7;51.7;80.7max8:8 1112 FFFFy { }max 0 2;7 0;14 0 14= + + + = - 67 - ( ) ( ) ( ) ( ) ( ){ } =++++== 03.7;32.7;61.7;90.7max9:9 11112 FFFFFy { } 21021;014;07;20max =++++= ( ) ( ) ( ) ( ) ( )2 1 1 1 110: 10 max{7.0 10 ;7.1 7 ;7.2 4 ;7.3 1 }y F F F F F= = + + + + = max{0 2;7 2;14 0;21 0} 21= + + + + = ( ) ( ) ( ) ( ) ( )2 1 1 1 111: 11 max{7.0 11 ;7.1 8 ;7.2 5 ;7.3 2 }y F F F F F= = + + + + = max{0 2;7 2;14 0;21 0} 21= + + + + = ( ) ( ) ( ) ( ) ( ) ( )2 1 1 1 1 112: 12 max{7.0 12 ;7.1 9 ;7.2 6 ;7.3 3 ;7.4 0}y F F F F F F= = + + + + + max{0 2;7 2;14 0;21 0;28 0} 28= + + + + + = ( ) ( ) ( ) ( ) ( ) ( )2 1 1 1 1 113: 13 max{7.0 13 ;7.1 10 ;7.2 7 ;7.3 4 ;7.4 1 }y F F F F F F= = + + + + + max{0 2;7 2;14 2;21 0;28 0} 28= + + + + + = ( ) ( ) ( ) ( ) ( ) ( )2 1 1 1 1 114: 14 max{7.0 14 ;7.1 11 ;7.2 8 ;7.3 5 ;7.4 2 }y F F F F F F= = + + + + + max{0 4;7 2;14 2;21 0;28 0} 28= + + + + + = ( ) ( ) ( ) ( ) ( ) ( ) ( ) 35}035;028;221;214;47;40max{}05.7 ;34.7;63.7;92.7;121.7;150.7max{15:15 1 111112 =++++++=+ +++++== F FFFFFFy ( ) ( ) ( ) ( ) ( ) ( ) ( ) 35}035;028;221;214;47;40max{}15.7 ;44.7;73.7;102.7;131.7;160.7max{16:16 1 111112 =++++++=+ +++++== F FFFFFFy ( ) ( ) ( ) ( ) ( ) ( ) ( ) 35}035;028;221;214;47;40max{}25.7;54.7 ;83.7;112.7;141.7;170.7max{17:17 11 11112 =++++++=++ ++++== FF FFFFFy ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 42}042;035;228;221;414;47;60max{}06.7;35.7 ;64.7;93.7;122.7;151.7;180.7max{18:18 11 111112 =+++++++=++ +++++== FF FFFFFFy ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 42}042;035;228;221;414;47;60max{}16.7;45.7 ;74.7;103.7;132.7;161.7;190.7max{19:19 11 111112 =+++++++=++ +++++== FF FFFFFFy ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 42}042;035 ;228;221;414;47;60max{}26.7;55.7;84.7 ;113.7;142.7;171.7;200.7max{20:20 111 11112 =++ +++++=+++ ++++== FFF FFFFFy Khi k = 3 ta có: ( ) 00:0 3 == Fy ( ) ( ){ } 010.3max1:1 23 =+== FFy ( ) ( ) ( ){ } 301.3;20.3max2:2 223 =++== FFFy - 68 - ( ) ( ) ( ){ }11.3;30.3max3:3 223 FFFy ++== { } 703;70max =++= 4y = : ( ) ( ) ( ) ( ){ }3 2 2 24 max 3.0 4 ;3.1 2 ;3.2 0F F F F= + + + = { }max 0 7;3 0;6 0 7+ + + = 5y = : ( ) ( ) ( ) ( ){ }3 2 2 25 max 3.0 5 ;3.1 3 ;3.2 1F F F F= + + + = { }max 0 7;3 7;6 0 10+ + + = 6y = : ( ) ( ) ( ) ( ) ( )3 2 2 2 26 max{3.0 6 ;3.1 4 ;3.2 2 ;3.3 0 }F F F F F= + + + + = max{0 14;3 7;6 0;9 0} 14+ + + + = 7y = : ( ) ( ) ( ) ( ) ( )3 2 2 2 27 max{3.0 7 ;3.1 5 ;3.2 3 ;3.3 1 }F F F F F= + + + + = max{0 14;3 7;6 7;9 0} 14+ + + + = 8y = : ( ) ( ) ( ) ( ) ( ) ( )3 2 2 2 2 28 max{3.0 8 ;3.1 6 ;3.2 4 ;3.3 2 ;3.4 2 }F F F F F F= + + + + + = = max{0 14;3 14;6 7;9 0;12 0} 17+ + + + + = 9y = : ( ) ( ) ( ) ( ) ( ) ( )3 2 2 2 2 29 max{3.0 9 ;3.1 7 ;3.2 5 ;3.3 3 ;3.4 1}F F F F F F= + + + + + = = max{0 21;3 14;6 7;9 7;12 0} 21+ + + + + = ( ) ( ) ( ) ( ) ( ) ( ) ( ) 21}015;012;79;146;143;210max{}05.3 ;24.3;43.3;62.3;81.3;100.3max{10:10 2 222223 =++++++=+ +++++== F FFFFFFy ( ) ( ) ( ) ( ) ( ) ( ) ( ) 24}015;712;79;146;213;210max{}15.3 ;34.3;53.3;72.3;91.3;110.3max{11:11 2 222223 =++++++=+ +++++== F FFFFFFy ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 28}018;015;712;149;146;213;280max{}06.3;25.3 ;44.3;63.3;82.3;101.3;120.3max{12:12 22 222223 =+++++++=++ +++++== FF FFFFFFy ( ) ( ) ( ) ( ) ( ) ( )3 2 2 2 2 213: 13 max{3.0 13 ;3.1 11 ;3.2 9 ;3.3 7 ;3.4 5y F F F F F F= = + + + + + 2 23.5 (3);3.6 (1)}F F+ + = { }max 0 28;3 21;6 21;9 14;12 7;15 7;18 0 28+ + + + + + + = ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 31}21;018 ;715;1412;149;216;283;280max{}07.3;26.3;45.3 ;64.3;83.3;102.3;121.3;140.3max{14:14 222 222223 =+ ++++++=+++ +++++== FFF FFFFFFy ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 3 2 2 2 2 2 2 2 2 15: 15 max{3.0 15 ;3.1 13 ;3.2 11 ;3.3 9 ;3.4 7 ; 3.5 5 ;3.6 3 ;3.7 1 } max{0 35;3 28;6 21;9 21;12 14;15 7; 18 7;21} 35 y F F F F F F F F F = = + + + + + + + + = + + + + + + + = - 69 - ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 35}024;021 ;718;1415;1412;219;286;283;350max{}08.3;27.3;46.3 ;65.3;84.3;103.3;122.3;141.3;160.3max{16:16 222 2222223 =++ +++++++=+++ ++++++== FFF FFFFFFFy ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 38}024;721;718;1415 ;2112;219;286;353;350max{}18.3;37.3;56.3;75.3 ;94.3;113.3;132.3;151.3;170.3max{17:17 2222 222223 =++++ +++++=++++ +++++== FFFF FFFFFFy ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 42}27;024;721;1418;1415;2112;289 ;286;353;420max{}09.3;28.3;47.3;66.3;85.3 ;104.3;123.3;142.3;161.3;180.3max{18:18 22222 222223 =++++++ +++=+++++ +++++== FFFFF FFFFFFy ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 42}027;724;721;1418;2115;2112;289 ;356;353;420max{}19.3;38.3;57.3;76.3;95.3 ;114.3;133.3;152.3;171.3;190.3max{19:19 22222 222223 =+++++++ +++=+++++ +++++== FFFFF FFFFFFy ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 45}030;027;724;1421;1418;2115;2812;289;356;423 ;420max{}010.3;29.3;48.3;67.3;86.3;105.3 ;124.3;143.3;162.3;181.3;200.3max{20:20 222222 222223 =++++++++++ +=++++++ +++++== FFFFFF FFFFFFy Khi k = 4 t−ơng tự ta có: 4 4 4 4 4 4 4 4 4 4 4 0 : ( 0 ) 0 1 : ( 0 ) 1 2 : ( 2 ) 3 3 : ( 3 ) 7 4 : ( 4 ) 8 5 : ( 5 ) 1 0 6 : ( 6 ) 1 4 7 : ( 7 ) 1 5 8 : ( 8 ) 1 7 9 : ( 9 ) 2 1 1 0 : (1 0 ) 2 2 y F y F y F y F y F y F y F y F y F y F y F = = = = = = = = = = = = = = = = = = = = = = 4 4 4 4 4 4 4 4 4 4 1 1 : (1 1 ) 2 4 1 2 : (1 2 ) 2 8 1 3 : (1 3 ) 2 9 1 4 : (1 4 ) 3 1 1 5 : (1 5 ) 3 5 1 6 : (1 6 ) 3 6 1 7 : (1 7 ) 3 8 1 8 : (1 8 ) 4 2 1 9 : (1 9 ) 4 3 2 0 : ( 2 0 ) 4 5 y F y F y F y F y F y F y F y F y F y F = = = = = = = = = = = = = = = = = = = = Ta thấy: ( ) ( ) 4520;04520 344 ==⇒= FxF ( ) ( ) 4218;14520 233 ==⇒= FxF ( ) ( ) 00;64218 122 ==⇒= FxF - 70 - ( ) 000 11 =⇒= xF Ph−ơng án tối −u: ( ) ( ) 45;0,1,6,0 ** == xFx . Bài tập 10: Giải bài toán cái túi sau. 1 2 3( ) 11 7 5F x x x x max= + + → 1 2 36 4 3 20x x x+ + ≤ 0jx ≥ , jx - nguyên, 1,3j = Lời giải Giải bài toán cái túi trên bằng cách dùng hệ thức Dantzig: y 0 ( )F y 1( )F y 1( )j y 2 ( )F y 2 ( )j y 3( )F y 3 ( )j y 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 3 0 0 0 0 0 5 3 4 0 0 0 7 2 7 2 5 0 0 0 7 2 7 2 6 0 11 1 11 1 11 1 7 0 11 1 11 1 12 3 8 0 11 1 14 2 14 2 9 0 11 1 14 2 16 3 10 0 11 1 18 2 18 2 11 0 11 1 18 2 19 3 12 0 22 1 22 1 22 1 13 0 22 1 22 1 23 3 14 0 22 1 25 2 25 2 15 0 22 1 25 2 27 3 - 71 - 16 0 22 1 29 2 29 2 17 0 22 1 29 2 30 3 18 0 33 1 33 1 33 1 19 0 33 1 33 1 34 3 20 0 33 1 36 1 36 2 Ta thu đ−ợc giá trị tối −u 3(20) 36F = . Tìm ph−ơng án tối −u của bài toán: 3(20) 2j = ⇒ * 3 0x = , * 2 1x = . Tiếp tục: 3 2 3 3(20 ) (20 4) (16) 2j a j j− = − = = ⇒ *2 1 1 2x = + = 3 3(16 4) (12) 1j j− = = ⇒ *1 1x = 3 1 3 3(12 ) (12 6) (6) 1j a j j− = − = = ⇒ *1 1 1 2x = + = . 3 1 3 3(6 ) (6 6) (0) 0j a j j− = − = = . Ph−ơng án tối −u: * (2,2,0)x = , *( ) 36F x = Bài tập 11: Giải bài toán cái túi sau: 1 2 3 1 2 3 8 5 3 2 13 x x x max x x x + + →  + + ≤ 0jx ≥ , nguyên, 1,3j = Lời giải Ta giải bài toán trên theo hệ thức Dantzig: y F0(y) F1(y) j1(y) F2(y) j2(y) F3(y) j3(y) 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 3 2 0 0 0 5 2 5 2 3 0 8 1 8 1 8 1 4 0 8 1 10 2 10 2 5 0 8 1 13 2 13 2 6 0 16 1 16 1 16 1 - 72 - 7 0 16 1 18 2 18 2 8 0 16 1 21 2 21 2 9 0 24 1 24 1 24 1 10 0 24 1 26 2 26 2 11 0 24 1 29 2 29 2 12 0 32 1 32 1 32 1 13 0 32 1 34 2 34 2 Ta thu đ−ợc giá trị tối −u của bài toán là F3(13) = 34. Tìm ph−ơng án tối −u của bài toán j3(13) = 2 ⇒ * * 2 31, 0x x= = . Tiếp tục do * 3 2 3 3 2(13 ) (13 2) (11) 2 1 1 2j a j j x− = − = = → = + = * 3 2 3 3 1(11 ) (11 2) (9) 1 1.j a j j x− = − = = → = * 3 1 3 3 1(9 ) (9 3) (6) 1 1 1 2j a j j x− = − = = → = + = . 3 1 3(6 ) (6 3)j a j− = − 3(3) 1j= = *1 2 1 3.x→ = + = 3 1 3 3(3 ) (3 3) (0)j a j j− = − = chấm dứt. Vậy ph−ơng án tối −u của bài toán là * (3,2,0)x = . Kết luận ch−ơng 3: Ch−ơng 3 đQ trình bày các bài tập vận dụng lý thuyết quy hoạch nguyên tuyến tính tổng quát; các thuật toán giải bài toán quy hoạch nguyên tuyến tính: thuật toán cắt của Gomory, thuật toán Land – Doig, đ−a bài toán quy hoạch nguyên về bài toán cái túi để giải bằng ph−ơng pháp truy toán của quy hoạch động giải bài toán cái túi. Kết quả trình bày ở ch−ơng 3 cho thấy tầm quan trọng , tính thiết thực của lý thuyết bài toán quy hoạch nguyên tuyến tính đối với các lĩnh vực khoa học kỹ thuật, các hoạt động thực tiễn của đời sống xQ hội. - 73 - Kết luận Theo h−ớng đi sâu nghiên cứu bài toán quy hoạch nguyên tuyến tính khoá luận đQ thu đ−ợc những kết quả chính sau: • Hệ thống hoá các kiến thức liên quan đến bài toán quy hoạch tuyến tính tổng quát, một số thuật toán giải bài toán quy hoạch tuyến tính • Trình bày tổng quát lý thuyết xây dựng các thuật toán giải các bài toán quy hoạch nguyên tuyến tính: thuật toán cắt Gomory, thuật toán Land – Doig, ph−ơng pháp truy toán của quy hoạch động giải bài toán cái túi. • Xây dựng hệ thống các bài tập vận dụng các thuật toán trên để giải. Khoá luận có thể phát triển theo các h−ớng sau • Xây dựng các biện pháp chống xoay vòng trong giải bài toán quy hoạch nguyên (theo thuật toán cắt Gomory) • Nghiên cứu, vận dụng lý thuyết giải bài toán quy hoạch nguyên tuyến tính cho bài toán quy hoạch nguyên tổng quát Căn cứ vào mục tiêu, nội dung nghiên cứu đQ đề ra trong đề c−ơng nghiên cứu và sử dụng hợp lý các ph−ơng pháp nghiên cứu, tôi đQ tiến hành nghiên cứu đúng h−ớng và hoàn thành khoá luận. Mặc dù bản thân tôi đQ rất cố gắng, song do điều kiện về thời gian, trình độ chuyên môn có hạn nên khoá luận không tránh khỏi những thiếu sót, tôi rất mong nhận đ−ợc sự chỉ bảo tận tình của các thầy giáo, cô giáo và sự góp ý của các bạn sinh viên để khoá luận đ−ợc hoàn chỉnh hơn. - 74 - Tài liệu tham khảo 1. Trần Đình ánh - Bài tập quy hoạch tuyến tính. 2. Phí Mạnh Ban - Quy hoạch tuyến tính cao đẳng s− phạm - NXB ĐHSP 2004. 3. Phí Mạnh Ban - Bài tập quy hoạch tuyến tính - NXB ĐHSP 2004. 4. Nguyễn Đức Nghĩa - Tối −u hoá quy hoạch tuyến tính và rời rạc - NXBGD 1996. 5. Bùi Minh Trí - Tối −u hóa - NXB khoa học kỹ thuật - 2006. 6. Bùi Minh Trí - Bài tập tối −u hoá - NXB Khoa học và kỹ thuật - 2006. 7. Bùi Thế Tâm - Nguyễn Vũ Tiến. Các thuật toán tối −u hoá (Quy hoạch tuyến tính). NXB Giao thông vận tải Hà Nội 2000. 8. Nguyễn Địch. Lý thuyết tối −u hoá (tài liệu dùng cho sinh viên đại học mở Hà Nội, 2004.) 9. Nguyễn Ngọc Thắng – Nguyễn Đình Hoá. Quy hoạch tuyến tính. NXB Đại học quốc gia Hà Nội 2004. 10. Đặng Văn Uyên. Quy hoạch tuyến tính. Sách Đại học S− phạm – NXBGD 1998. - 75 -