Đồ án Về bài toán quy hoạch nguyên tuyến tính

- 1 - Mục Lục Nội dung Trang Mở đầu 2 Ch−ơng 1: Các kiến thức bổ trợ 1.1. Bài toán quy hoạch tuyến tính tổng quát 5 1.2. Thuật toán đơn hình giải bài toán quy hoạch tuyến tính 7 1.3. Thuật toán đơn hình đối ngẫu giải bài toán quy hoạch tuyến tính chính tắc 9 Ch−ơng 2: Bài toán quy hoạch nguyên tuyến tính 2.1. Bài toán tối −u rời rạc 19 2.2. Một số thuật toán giải bài toán quy hoạch nguyên tuyến tính 26 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 50 3.2. Bài tập vận dụng thuật toán Land - Doig 58 3.3. Bài tập đ−a bài toán về bài toán cái túi để giải 64 Tài liệu tham khảo 74 - 2 - Lời Nói đầu 1. Lí do chọn đề tài Tối −u hoá là một lĩnh vực toán học nghiên cứu lý thuyết về thuật toán giải các bài toán cực trị. Nó là một phần kiến thức không thể thiếu đ−ợc cho những ng−ời làm việc trong các lĩnh vực ứng dụng của khoa học và kỹ thuật. Trong lý thuyết tối −u, một trong những lớp bài toán đầu tiên đ−ợc nghiên cứu trọn vẹn cả về ph−ơng diện lý thuyết lẫn thuật toán là bài toán quy hoạch tuyến tính. Ngay từ khi ra đời, quy hoạch tuyến tính đQ chiếm một vị trí hết sức quan trọng; nó là môn toán ứng dụng rất cần thiết đối với sinh viên thuộc nhiều ngành học khác nhau. Các thuật toán giải bài toán quy hoạch tuyến tính không những giúp giải quyết các bài toán quy hoạch tuyến tính tổng quát cỡ lớn mà nó còn là điểm xuất phát quan trọng trong việc nghiên cứu lý thuyết giải các bài toán tối −u tổng quát. Trong lý thuyết tối −u ta gặp một lớp bài toán mà đối t−ợng của nó không thể chia cắt nhỏ tuỳ ý, trong lớp bài toán này tất cả (hoặc một bộ phận) các biến chỉ nhận giá trị nguyên, đó là bài toán quy hoạch nguyên. Trong bài toán quy hoạch nguyên, nếu hàm mục tiêu và hệ ràng buộc là các hàm tuyến tính thì ta có bài toán quy hoạch nguyên tuyến tính. Đối với các bài toán quy hoạch nguyên tuyến tính, các thuật toán giải bài toán quy hoạch tuyến tính tổng quát cơ bản hầu hết không thể sử dụng đ−ợc nữa do yêu cầu về tính nguyên của các biến số. Năm 1958 Gomory (nhà toán học ng−ời mỹ) đQ công bố thuật toán cắt nối tiếng để giải bài toán quy hoạch nguyên tuyến tính mở đầu cho sự ra đời và phát triển của lý thuyết bài toán quy hoạch nguyên. Tiếp đó, một số kết quả nghiên cứu về tập nghiệm và lời giải cho lớp bài toán này lần l−ợt đ−ợc ra đời. Tuy xuất hiện sau thuật toán đơn hình giải bài toán quy hoạch tuyến tính gần ba thập kỷ nh−ng các thuật toán giải bài toán quy hoạch nguyên tuyến tính đQ có những đóng góp không nhỏ cho lĩnh vực nghiên cứu lý thuyết tối −u tổng quát. Bài toán quy hoạch nguyên tuyến tính là phần kiến thức khá mới mẻ đối với sinh viên s− phạm toán. Với mong muốn khai thác sâu kiến thức môn quy hoạch tuyến tính nói riêng; mở rộng tầm hiểu biết của bản thân về tri thức toán - 3 - nói chung, việc nghiên cứu lý thuyết bài toán quy hoạch nguyên tuyến tính là hết sức cần thiết. Vì những lý do trên chúng tôi chọn "Về bài toán quy hoạch nguyên tuyến tính" làm đề tài nghiên cứu. 2. Mục đích nghiên cứu Hệ thống lại một cách chi tiết các vấn đề lý thuyết về bài toán quy hoạch nguyên tuyến tính; xây dựng hệ thống bài tập vận dụng, để từ đó thấy đ−ợc tầm quan trọng và 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. 3. Nhiệm vụ nghiên cứu • Nghiên cứu 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. • Nghiên cứu các ph−ơng pháp giải bài toán quy hoạch nguyên tuyến tính. • Nghiên cứu một số bài tập vận dụng ph−ơng pháp giải bài toán quy hoạch nguyên tuyến tính. 4. Đối t−ợng và phạm vi nghiên cứu Đối t−ợng nghiên cứu: Lý thuyết tối −u hoá. Phạm vi nghiên cứu: Nghiên cứu lý thuyết bài toán quy hoạch nguyên tuyến tính. 5. Ph−ơng pháp nghiên cứu • Ph−ơng pháp nghiên cứu lý luận: Đọc các tài liệu về môn quy hoạch tuyến tính, các tài liệu liên quan đến tối −u hoá, các khoá luận tốt nghiệp về quy hoạch tuyến tính của các khoá tr−ớc ở tr−ờng Đại học Hùng V−ơng. • Ph−ơng pháp lấy ý kiến chuyên gia: Tham khảo ý kiến của giảng viên h−ớng dẫn và các giảng viên dạy tối −u hoá; quy hoạch tuyến tính của tr−ờng. • Ph−ơng pháp tổng kết kinh nghiệm: Tổng kết kinh nghiệm của bản thân qua quá trình học học phần quy hoạch tuyến tính và của các bạn sinh viên đQ học tối −u hóa của các lớp s− phạm và các lớp quản trị kinh doanh trong tr−ờng. - 4 - 6. ý nghĩa khoa học và thực tiễn Sản phẩm khoa học: Hệ thống lại một số kiến thức của lý thuyết tối −u tuyến tính, giới thiệu một số thuật toán giải bài toán quy hoạch nguyên tuyến tính, xây dựng hệ thống bài tập vận dụng lý thuyết đQ xây dựng. Sản phẩm thực tiễn: Khóa luận là tài liệu tham khảo cho sinh viên toán, tin học và sinh viên các ngành kinh tế, quản trị kinh doanh. 7. Bố cục khoá luận Khóa luận gồm 74 trang, ngoài phần mục lục, mở đầu, kết luận và tài liệu tham khảo nội dung chính của khoá luận bao gồm 3 ch−ơng Ch−ơng 1. Các kiến thức bổ trợ 1.1. Bài toán quy hoạch nguyên tuyến tính tổng quát 1.2. Thuật toán đơn hình giải bài toán quy hoạch tuyến tính 1.3. Thuật toán đơn hình đối ngẫu giải bài toán quy hoạch tuyến tính chính tắc Ch−ơng 2. Bài toán quy hoạch nguyên tuyến tính 2.1. Bài toán tối −u rời rạc 2.2. Một số 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 • Ph−ơng pháp nhánh cận (Thuật toán Land - Doig) • 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 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 của Gomory 3.2. Bài tập vận dụng thuật toán Land - Doig 3.3. Bài tập đ−a bài toán về bài toán cái túi để giải - 5 - CHƯƠNG 1 CáC KIếN THứC Bổ TRợ 1.1. Bài toán quy hoạch tuyến tính tổng quát 1.1.1. Bài toán quy hoạch tuyến tính tổng quát Tìm vectơ 1 2( , ,...., )nx x x x= sao cho hàm f(x) = 1 n j j j c x = ∑ → min với các điều kiện: 1 1 2 1 3 1 1 2 3 , (1.1) , (1.2) , (1.3) 0, (1.4) , (1.5) 0, (1.6) n ij j i j n ij j i j n ij j i j j j j a x b i I a x b i I a x b i I x j J x R j J x j J = = =   ≤ ∈    = ∈    ≥ ∈   ≥ ∈  ∈ ∈   ≤ ∈ ∑ ∑ ∑ Với I1 ⊂ I; I2 ⊂ I; I3 ⊂ I; I={ 1,.., m}; I1∪ I2 ∪I3 = I; Ii ∩ Ik =ỉ; i ≠ k; i, k = 1,2,3. J1⊂ J; J2 ⊂ J; J3 ⊂ J; J = { 1,.., n}; J = J1 ∪ J2 ∪J3, Ji ∩Jk = ỉ; I ≠ k; i,k = 1,2,3. bi, cj, aij là các hằng số cho tr−ớc. Trong bài toán trên: • f đ−ợc gọi là hàm mục tiêu. • Mỗi hệ thức ở (1.1), (1.2), (1.3), (1.4), (1.5), (1.6) gọi là một ràng buộc. • Mỗi ràng buộc (1.1), (1.2), (1.3) gọi là ràng buộc c−ỡng bức (hay cơ bản). • Ràng buộc (1.4), (1.5), (1.6) gọi là ràng buộc tự do (hay ràng buộc dấu). + Mỗi vectơ 1 2( , ,...., )nx x x x= ∈ Rn thoả mQn mọi ràng buộc của bài toán gọi là một ph−ơng án. Tập hợp tất cả các ph−ơng án (ký hiệu D) gọi là miền ràng - 6 - buộc hay miền chấp nhận đ−ợc. Ph−ơng án làm cho hàm mục tiêu đạt cực tiểu hoặc cực đại đ−ợc gọi là ph−ơng án tối −u hay một lời giải của bài toán đQ cho. + Giải bài toán quy hoạch tuyến tính là tìm ph−ơng án tối −u của bài toán (có thể là ph−ơng án tối −u duy nhất hoặc vô số ph−ơng án tối −u) hoặc chứng tỏ bài toán vô nghiệm. 1.1.2. Một số kí hiệu quy −ớc a) Nếu A là ma trận cỡ (m,n) thì Ai =(ai1,ai2,...,ain) là vectơ dòng (ma trận dòng) thứ i (i = 1,2,...., m) của A; Aj = (a1j, a2j,..,amj) là vectơ cột (ma trận cột) thứ j (j = 1,2,...,n) của A. b) At là ma trận chuyển vị của A. c) Nếu A = (aij) và B = (bij) là hai ma trận cùng kiểu thì bất đẳng thức ma trận A ≥ B đ−ợc hiểu là aij ≥ bij với ∀ i,j. Đặc biệt với vectơ (ma trận) 1 2( , ,...., )nx x x x= thì x ≥ 0 đ−ợc hiểu là xj ≥ 0 ∀ j. d) Mỗi vectơ đ−ợc xem nh− ma trận cột trong các phép tính ma trận ( nếu không nói gì thêm hoặc không có quy −ớc gì khác). e) Biểu thức tích vô h−ớng của hai vectơ 1 2( , ,...., )nx x x x= ; y = (y1, y2, ..., yn) đ−ợc viết: (x, y) = 1 n j j j x y = ∑ g) Nếu xem c và x là hai ma trận cột thì ctx = 1 n j j j c x = ∑ là ma trận cấp 1 ( ct là ma trận chuyển vị của c). Với những quy −ớc nh− trên bài toán quy hoạch tuyến tính tổng quát đ−ợc viết gọn nh− sau: Tìm vectơ 1 2( , ,...., )nx x x x= ∈ Rn thoả mQn: f(x) = ctx → min. - 7 - 1 2 1 2 , , 0, , i i j j A x b i I A x b i I x j J x R j J ≥ ∈  = ∈  ≥ ∈  ∈ ∈ Trong đó A = (aij) là hai ma trận cỡ (m,n). 1.1.3. Dạng chính tắc và dạng chuẩn tắc của bài toán quy hoạch tuyến tính Dạng chuẩn tắc: f(x) = ctx→min 0,j Ax b x j J ≥  ≥ ∈ Dạng chính tắc: f(x) = ctx → min 0,j Ax b x j J =  ≥ ∈ 1.2. Thuật toán đơn hình giải bài toán quy hoạch tuyến tính Xét bài toán quy hoạch tuyến tính chính tắc (bài toán I) 1 ( ) min n j j j f x c x = = →∑ 1 0, 1, n ij j i j j a x b x j n =  =   ≥ = ∑ (I) - 8 - • B−ớc xuất phát: Tìm một ph−ơng án cực biên 0x và cơ sở { };j BB A j J= ∈ t−ơng ứng, trong đó { }/ jBJ j J A B= ∈ ∈ . Tìm các hệ số khai triển ija và các −ớc l−ợng j∆ ( ija : hệ số khai triển vectơ Ai qua các vectơ Aj). • B−ớc 1:Kiểm tra dấu hiệu tối −u: a) Nếu 0j∆ ≤ ∀ j ∈ J thì 0x là ph−ơng án tối −u. Thuật toán kết thúc. b) Nếu ∃ j∆ > 0 thì chuyển sang b−ớc hai. • B−ớc 2: Kiểm tra dấu hiệu hàm mục tiêu giảm vô hạn. Với mỗi j ∉ BJ mà j∆ > 0 thì kiểm các hệ số khai triển ija của cột jA t−ơng ứng. a) Nếu tồn tại j∆ > 0 mà tất cả ija ≤ 0 ∀ j ∈ J thì kết luận hàm mục tiêu giảm vô hạn trên miền ràng buộc. Bài toán không có lời giải hữu hạn. Thuật toán kết thúc. b) Nếu với mỗi j ∉ BJ mà j∆ > 0 đều tồn tại ít nhất một hệ số 0ija > thì tiến hành tìm ph−ơng án cực biên mới tốt hơn với cơ sở 1 ( \ )BJ J r s= ∪ theo quy tắc sau: • B−ớc 3: - Tìm cột xoay: Tìm { }0,s j Bmax j J∆ = ∆ > ∉ Cột sA gọi là cột xoay (cột đ−a vào cơ sở ). - Tìm dòng xoay: tìm 0 0 min , 0r i ij rs ij x x a a a θ    = = >     Dòng r A gọi là dòng xoay. - 9 - Phần tử nằm trên giao của dòng xoay và cột xoay của bảng đơn hình đ−ợc gọi là phần tử xoay. • B−ớc 4: Thực hiện phép biến đổi đơn hình chuyển từ ph−ơng án cơ sở chấp nhận đ−ợc x sang ph−ơng án cơ sở chấp nhận đ−ợc x : Bảng đơn hình t−ơng ứng với x (gọi tắt là bảng mới) có thể thu đ−ợc từ bảng đơn hình t−ơng ứng với x (gọi tắt là bảng cũ) theo các quy tắc biến đổi sau đây: a) Các phần tử ở vị trí dòng xoay trong bảng mới ( rja ) bằng các phần tử t−ơng ứng trong bảng cũ chia cho phần tử xoay: , rj rj rs a a j J a = ∈ b) Các phần tử ở vị trí cột xoay trong bảng mới, ngoại trừ phần tử nằm trên vị trí phần tử xoay bằng 1, còn tất cả là bằng 0. c) Các phần tử cần tính còn lại trong bảng mới ( , )jija ∆ đ−ợc tính từ các phần tử t−ơng ứng trong bảng cũ theo các công thức sau: rj ij ij is rs a a a a a = − , ( )Bi J i r∈ ≠ , ( )Bj J j s∉ ≠ rj s j j rs a a ∆ ∆ = ∆ − 1.3. Thuật toán đơn hình đối ngẫu giải bài toán quy hoạch tuyến tính chính tắc 1.3.1. Cơ sở chấp nhận đ−ợc đối ngẫu Xét bài toán quy hoạch tuyến tính dạng chính tắc (P) và bài toán đối ngẫu (Q). (P) ( ) mintf x c x= → (Q) ( )g y by max= → 0 Ax b x =  ≥ tA y c y  ≤  ∈ R Giả thiết rằng rankA = m. Giả sử { };jB A j J= ∈ là một hệ gồm m vectơ cột độc lập tuyến tính của ma trận A. Ta gọi hệ vectơ này là cơ sở của ma trận A. - 10 - Ký hiệu { }1 2, ,..., nN A A A= \ B. Ph−ơng án cơ sở (xB, xN) của bài toán (P) t−ơng ứng với cơ sở B thu đ−ợc bằng cách giải hệ ph−ơng trình tuyến tính xN = 0, ABxB = b. Định nghĩa : Ta gọi B là cơ sở chấp nhận đ−ợc gốc nếu ph−ơng án cơ sở t−ơng ứng với nó là ph−ơng án chấp nhận đ−ợc của bài toán gốc, (tức là nếu 1 0B Bx A b − = ≥ ). Ta gọi ph−ơng án cơ sở đối ngẫu t−ơng ứng với cơ sở B là vectơ y thu đ−ợc bằng cách giải hệ ph−ơng trình tuyến tính t B BA y c= (tức là 1( )tB By A c−= ) Cơ sở B đ−ợc gọi là cơ sở chấp nhận đ−ợc đối ngẫu nếu ph−ơng án cơ sở đối ngẫu ứng với nó là ph−ơng án chấp nhận đ−ợc của bài toán đối ngẫu. Nếu ph−ơng án cơ sở t−ơng ứng với B là ph−ơng án tối −u thì B sẽ đ−ợc gọi là cơ sở tối −u. Nh− vậy nếu B là cơ sở chấp nhận đ−ợc đối ngẫu thì ph−ơng án cơ sở đối ngẫu t−ơng ứng với nó 1( )tB By A c−= phải thoả mQn tất cả các ràng buộc của bài toán đối ngẫu tA y c≤ hay 1( ) 0t tB BA A c c− − ≤ (1.7) Dễ thấy nếu B là cơ sở chấp nhận đ−ợc gốc, thì điều kiện (1.7) chính là tiêu chuẩn tối −u. Nh− vậy, cơ sở B sẽ là tối −u nếu nh− nó vừa là chấp nhận đ−ợc gốc vừa là chấp nhận đ−ợc đối ngẫu. Nhận xét • Thuật toán đơn hình gốc là bắt đầu từ một cơ sở chấp nhận đ−ợc gốc, sau một số hữu hạn lần chuyển cơ sở sẽ đi đến cơ sở tối −u. • Thuật toán đơn hình đối ngẫu lại bắt đầu từ một cơ sở chấp nhận đối ngẫu nh−ng ch−a phải chấp nhận đ−ợc gốc, ta tiến hành dịch chuyển sang các cơ sở chấp nhận đ−ợc đối ngẫu mới cho đến khi gặp đ−ợc cơ sở tối −u thì dừng lại. 1.3.2. Thuật toán đơn hình đối ngẫu khi đã biết cơ sở chấp nhận đ−ợc đối ngẫu - 11 - Xét bài toán quy hoạch tuyến tính dạng chính tắc. f(x) = ctx→ min 0 A x b x =  ≥ Giả sử B là cơ sở chấp nhận đ−ợc đối ngẫu. Không giảm tổng quát ta coi B = (A1,A2,....,Am). Ta lập bảng đơn hình ứng với cơ sở B của bài toán gốc. Cơ sở cj cơ sở Giả ph−ơng án c1 A1 ...... ...... cj Aj ..... ..... cn An A1 A2 ..... Am c1 c2 ..... cm 1b 2b ..... mb 1 ja 2 ja ...... mja ∆ j∆ Bảng 1 Trong đó: 1 1 2( , ,..., )'mb b b b B b−= = 1 1 , 2( ,...., ) , 1,j jj j mjA a a a B A j n−= = = 1 jj B jc B A c −∆ = − ; 1,j n= Cột giả ph−ơng án có thể chứa các thành phần âm vì B ch−a chắc đQ là một cơ sở chấp nhận đ−ợc gốc. - 12 - Do B là một cơ sở chấp nhận đ−ợc đối ngẫu nên 0j∆ ≤ ∀ 1,j n= Các b−ớc của thủ tục đơn hình đối ngẫu. B−ớc 1: Kiểm tra tiêu chuẩn tối −u. Cơ sở đang xét sẽ là tối −u nếu mọi thành phần ib , 1,i m= của cột giả ph−ơng án đều không âm vì khi đó cơ sở đang xét sẽ chấp nhận đ−ợc gốc và vì thế nó là tối −u. • Nếu 0ib ≥ ∀ 1,i m= thì giả ph−ơng án (xB, xN) là một ph−ơng án tối −u. Thuật toán kết thúc. • Nếu ∃ i, 1,i m= mà ib < 0 thì ta tìm rb = min{ ib , 1,i m= }. Nếu có nhiều chỉ số cùng đạt cực tiểu thì chọn r là một chỉ số tuỳ ý trong số đó. B−ớc 2: Kiểm tra điều kiện để tập ph−ơng án của bài toán là không rỗng: nếu có 1,i m= mà ib < 0 thì trên dòng i phải tồn tại ít nhất một phần tử 0ija < . • Nếu có dòng ứng với ib < 0 (i = 1,2,...,m) mà ija ≥ 0 ∀ 1,j n= . Khi đó bài toán gốc (P) không có ph−ơng án. Thật vậy. Giả sử (P) có ph−ơng án, tức là ∃ x ∈ Rn thoả mQn Ax = b, x≥ 0 hay 1 , ( 1, ) n i j j i j a x b i m = = =∑ (*) (*) không thể xảy ra vì ija ≥ 0, xj ≥ 0 ( 1,j n= ) còn bi < 0. Vậy bài toán (P) không có ph−ơng án. • Nếu trên mỗi dòng ứng với ib < 0 đều tồn tại ít nhất một phần tử 0ija ≤ . Khi đó ta tiến hành một b−ớc lặp đơn hình đối ngẫu để chuyển sang một cơ sở chấp nhận đ−ợc đối ngẫu mới. Giả sử đQ chọn dòng xoay r. Ta tìm cột đ−a vào cơ sở thay cho cột Ar. Cột đ−a vào thay cho Ar phải đảm bảo sao cho cơ sở mới vẫn là cơ sở chấp nhận - 13 - đ−ợc đối ngẫu. Giả sử cột As đ−ợc đ−a vào thay cho cột Ar, khi đó phần tử trục ars và sau khi thực hiện tính toán đổi cơ sở thì các phần tử ở dòng −ớc l−ợng ứng với cơ sở mới sẽ là ( )rjj s rs a a ∆ − ∆ Do đó muốn cơ sở mới vẫn là chấp nhận đ−ợc đối ngẫu ta phải chọn chỉ số s ứng với min ; 0js rj rs rj a a a ∆ ∆ = <    . Cột As gọi là cột xoay. Sau khi đQ xác định đ−ợc dòng xoay, cột xoay ta tiến hành các tính toán trong phép biến đổi đơn hình giống nh− đQ làm trong bài toán gốc. 1.3.3. Thuật toán đơn hình đối ngẫu khi ch−a biết cơ sở xuất phát chấp nhận đ−ợc đối ngẫu Xét bài toán quy hoạch tuyến tính dạng chính tắc sau: f(x) = ctx → min 0 A x b x =  ≥ Giả sử cơ sở chấp nhận đ−ợc đối ngẫu là ch−a biết. Tuy vậy ta có thể tìm đ−ợc cơ sở B của ma trận A. Không giảm tổng quát ta coi rằng B = {A1, A2,..., Am}. Giả sử cơ sở B không phải là cơ sở chấp nhận đ−ợc đối ngẫu (có thể nó cũng không chấp nhận đ−ợc gốc). Đ−a thêm vào một biến giả x0 ≥ 0 với hệ số hàm mục tiêu c0 = 0, và thêm vào hệ ràng buộc của bài toán xuất phát một ràng buộc giả sau: x0 + xm +1 + ...........+ xn = M trong đó (xm+1,......, xn) là vectơ các biến phi cơ sở, còn M là một số d−ơng lớn hơn bất kỳ một số cụ thể nào cần so sánh với nó. Bài toán thu đ−ợc ta sẽ gọi là - 14 - bài toán mở rộng. Đối với bài toán mở rộng ta có một cơ sở của nó là 0 1( , ,...., )mB A A A= ⌢ ⌢ ⌢⌢ Ta xây dựng bảng đơn hình t−ơng ứng với cơ sở B ⌢ của bài toán mở rộng. Ph−ơng án c0 c1 ....... cj ....... cn Cơ sở B ⌢ cj cơ sở M 0A ⌢ 1A ⌢ ....... jA ⌢ ....... mA ⌢ 0A ⌢ 1A ⌢ ..... mA ⌢ c0 c1 ..... cm 0 1b ..... mb 1 0 ..... 0 1 1ja ..... mja 1 1na ...... mna 0∆ 1∆ ...... j∆ n∆ Chú ý rằng, khi tính giá trị các thành phần của cột ph−ơng án ta viết nó d−ới dạng i ib b M+ ⌢ ⌢ . Khi đó trong bảng đơn hình cột ph−ơng án đ−ợc tách ra làm hai cột, một cột ghi hệ số ib ⌢ của M, còn cột kia ghi hệ số tự do ib ⌢ . Giả sử s∆ = max { j∆ ; 1,j n= }. Do B ⌢ không phải là cơ sở chấp nhận đ−ợc đối ngẫu của bài toán nên s∆ > 0. Thực hiện một phép biến đổi đơn hình với phần tử xoay a0s (nghĩa là đ−a biến xs vào cơ sở còn đ−a x0 ra khỏi cơ sở) ta sẽ đi đến bảng đơn hình mới mà trong đó tất cả các phần tử của dòng −ớc l−ợng j∆ ; 1,j n= đều là không d−ơng tức là thu đ−ợc bảng đơn hình đối ngẫu với cơ sở chấp nhận đ−ợc đối ngẫu nên ta có thể tiến hành thủ tục đơn hình đối ngẫu với cơ sở chấp nhận đ−ợc đối ngẫu để giải bài toán mở rộng. Thuật toán đơn hình đối ngẫu giải bài toán mở rộng sẽ kết thúc ở một trong các tr−ờng hợp sau. - 15 - 1) Bài toán mở rộng không có ph−ơng án. Khi đó bài toán xuất phát cũng không có ph−ơng án. Thật vậy, nếu bài toán xuất phát có ph−ơng án chấp nhận đ−ợc x = (x1, x2,...., xn) thì rõ ràng x = (x0, x1,...., xn) với x0 = M - xm+1 -..........- xn cũng là một ph−ơng án của bài toán mở rộng. 2) Bài toán mở rộng có ph−ơng án tối −u 0 1( , ,...., )nx x x x= và x0 là biến cơ sở. Trong tr−ờng hợp này hàm mục tiêu của bài toán không phụ thuộc vào M, do đó 1( ,...., )nx x là ph−ơng án tối −u của bài toán ban đầu. 3) Bài toán mở rộng có ph−ơng án tối −u 0 1( , ,...., )nx x x x= và x0 không là biến cơ sở. Trong tr−ờng hợp này các biến cơ sở sẽ phụ thuộc vào M. Có hai khả năng xảy ra • Nếu giá trị hàm mục tiêu của bài toán mở rộng phụ thuộc vào M thì khi M → ∞ giá trị hàm mục tiêu sẽ dần đến ∞.Trong tr−ờng hợp này bài toán xuất phát có ph−ơng án chấp nhận đ−ợc nh−ng hàm mục tiêu không bị chặn d−ới nên bài toán không có lời giải. • Nếu giá trị hàm mục tiêu của bài toán mở rộng không phụ thuộc vào M thì bài toán xuất phát có ph−ơng án tối −u và có thể chấp nhận đ−ợc nó bằng cách bỏ 0x và giảm dần giá trị M cho đến khi có một trong các 1x , 2x ,...., nx trở thành 0. 1.3.4. áp dụng thuật toán đơn hình đối ngẫu để giải bài toán quy hoạch tuyến tính với số ràng buộc tăng dần Xét bài toán quy hoạch tuyến tính (I): Giả sử ta đQ giải bài toán (I) bằng thuật toán đơn hình và thu đ−ợc ph−ơng án tối −u cơ sở *x với cơ sở tối −u B. Không giảm tổng quát ta có thể coi rằng { }1 2, ,..., mB A A A= . Ta có bảng đơn hình tối −u là bảng 1 phần 1.3.2. - 16 - Bây giờ bổ sung vào hệ ràng buộc của bài toán một ph−ơng trình: 1, 1 1 (1.8) n m j j m j a x b+ + = ≤∑ Nếu *x thoả mQn ràng buộc ( 1.8) thì nó vẫn là ph−ơng án tối −u của bài toán có ràng buộc bổ sung này. Giả sử *x không thoả mQn ràng buộc bổ sung, tức là: * 1, 1 1 n m j mj j a bx+ + = >∑ (1.9) Vấn đề đặt ra: Liệu ta có thể sử dụng ph−ơng án tối −