Bài giảng Quy hoạch tuyến tính - Nguyễn Thanh Lâm

Quy hoạch tuyến tính Trang 1 Trường ĐH Lạc Hồng/ Khoa Quản trị- Kinh tế quốc tế Nguyễn Thanh Lâm- 2009 CHƯƠNG I BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 1. MỘT SỐ BÀI TOÁN DẪN ĐẾN BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 1. Bài toán cái túi Giả sử, một cái túi có thể chứa tối đa b kg (bỏ qua yếu tố thể tích). Có n loại đồ vật ),1( niTi = có thể được đưa vào trong túi với khối lượng & giá trị tương ứng là ia và ic . Yêu cầu đặt ra: Cần đặt vào trong túi bao nhiêu đồ vật mỗi loại để cái túi có giá trị lớn nhất. Gọi ix là số đồ vật ),1( niTi = cần đặt vào túi; với điều kiện 0≥ix và ix nguyên. Khi đó, mô hình toán cần lập có dạng như sau: max)( 1 →=∑ = n i ii xcxf ⎪⎩ ⎪⎨ ⎧ =≥ ≤∑ = nguyennix bxa i n i ii ),,1(0 1 Đây là một bài toán quy hoạch tuyến tính. 2. Bài toán lập kế hoạch sản xuất tối ưu Một doanh nghiệp cần sản xuất n loại sản phẩm nPP ,...,1 từ m loại nguyên liệu mMM ,...,1 . Giá xuất xưởng sản phẩm, trữ lượng nguyên liệu hiện có và định mức sử dụng nguyên liệu để sản xuất các loại sản phẩm được cho ở bảng sau: Sản phẩm Tên nguyên liệu Trữ lượng nguyên liệu 1P 2P … nP 1M 2M … mM 1b 2b … mb 11a 21a … 1ma 12a 22a … 2ma … … … … na1 na2 … mna Giá xuất xưởng 1c 2c … nc Để không bị động trong quá trình sản xuất, doanh nghiệp cần xác định số lượng sản phẩm cần sản xuất mỗi loại sao cho tổng trị giá xuất xưởng là lớn nhất trong phạm vi trữ lượng nguyên liệu hiện có của doanh nghiệp. Hãy lập mô hình toán để xác định số sản phẩm đó. Gọi ix là số sản phẩm iP ),1( ni = cần phải sản xuất; với điều kiện 0≥ix . Khi đó: + Trị giá xuất xưởng của doanh nghiệp được xác định bằng: ∑ = = n i ii xcR 1 ; + Tổng lượng nguyên liệu loại jM ),1( mj = dùng để sản xuất số sản phẩm trên là: ∑ = = n i iijj xaw 1 ; Trong phạm vi trữ lượng nguyên liệu hiện có của doanh nghiệp, ta cần Quy hoạch tuyến tính Trang 2 Trường ĐH Lạc Hồng/ Khoa Quản trị- Kinh tế quốc tế Nguyễn Thanh Lâm- 2009 xác định ix ),1( ni = sao cho jj bw ≤ ),1( mj = ; Do đó, mô hình toán để xác định số sản phẩm cần sản xuất của doanh nghiệp được viết như sau: max 1 →=∑ = n i ii xcR ⎪⎩ ⎪⎨ ⎧ =≥ =≤∑ = ),1(0 ),1( 1 nix mjbxa i n i jiij Đây là một bài toán quy hoạch tuyến tính. 3. Bài toán xác định khẩu phần thức ăn tối ưu Theo lời khuyên của chuyên gia dinh dưỡng, để đảm bảo sức khoẻ và sự phát triển tốt của một loại gia súc L nào đó, hằng ngày, chủ chăn nuôi cần cung cấp đủ các loại chất dinh dưỡng nNN ,...,1 với khối lượng tối thiểu tương ứng nbb ,...,1 . Giả sử trên thị trường có m loại thức ăn mFF ,...,1 với hàm lượng chất dinh dưỡng trong từng loại và giá mua mỗi loại được cho qua bảng sau: Loại thức ăn Tên chất dinh dưỡng Lượng tối thiểu 1F 2F … mF 1N 2N … nN 1b 2b … nb 11a 21a … 1na 12a 22a … 2na … … … … ma1 ma2 … nma Giá mua 1c 2c … mc Yêu cầu được đặt ra là: Chủ chăn nuôi cần phải mua mỗi loại thức ăn bao nhiêu đơn vị để khoản chi mua thức ăn thấp nhất nhưng vẫn đảm bảo chất dinh dưỡng cho gia súc đó theo hướng dẫn của chuyên gia. Hãy lập mô hình toán để xác định khối lượng cần mua mỗi loại thức ăn. Gọi ix ),1( mi = là số đơn vị cần mua của loại thức ăn iF ; với điều kiện 0≥ix . Khi đó: + Tổng chi phí mua thức ăn được xác định bằng: ∑ = = m i ii xcC 1 ; + Tổng lượng chất dinh dưỡng jN ),1( nj = có trong thức ăn cần mua là: ∑ = = m i iijj xaw 1 ; Do yêu cầu về lượng tối thiểu chất dinh dưỡng cần cung cấp cho gia súc, chủ chăn nuôi cần đảm bảo rằng: ),1( 1 njbxaw j m i iijj =≥=∑ = . Và mô hình bài toán được viết như sau: min 1 →=∑ = m i ii xcC ⎪⎩ ⎪⎨ ⎧ =≥ =≥∑ = ),1(0 ),1( 1 mix njbxa i j m i iij Đây là một bài toán quy hoạch tuyến tính. Quy hoạch tuyến tính Trang 3 Trường ĐH Lạc Hồng/ Khoa Quản trị- Kinh tế quốc tế Nguyễn Thanh Lâm- 2009 4. Bài toán vận tải đóng (Bài toán vận tải cân bằng thu- phát) Giả sử, có n kho hàng (trạm phát) nAA ,...,1 cùng chứa một loại hàng với lượng hàng chứa tương ứng là ),1( niai = và có m đại lý tiêu thụ (trạm thu) mBB ,...,1 với nhu cầu tương ứng là ),1( mjbj = . Chi phí vận chuyển một đơn vị hàng hoá từ trạm iA đến trạm jB là ijc . Hãy lập kế hoạch vận chuyển hết hàng hoá từ các trạm phát đến giao hết tại các trạm thu sao cho chi phí vận chuyển là thấp nhất. Gọi ijx là lượng hàng cần vận chuyển từ trạm iA đến jB ),1,,1( mjni == . Khi đó: + Tổng chi phí vận chuyển được xác định bằng: ∑∑ = = = n i m j ijij xcxf 1 1 )( ; + Tổng lượng hàng phát đi từ trạm iA là: ∑ = m j ijx 1 ),1( ni = ; + Tổng lượng hàng thu tại trạm jB là: ∑ = n i ijx 1 ),1( mj = ; Khi đó, mô hình toán cần lập như sau: min)( 1 1 →=∑∑ = = n i m j ijij xcxf ⎪⎪ ⎪⎪ ⎩ ⎪⎪ ⎪⎪ ⎨ ⎧ ==≥ = = = ∑∑ ∑ ∑ == = = ),1,,1(,0 11 1 1 mjnix xx bx ax ij n i ij m j ij j n i ij i m j ij Đây là một bài toán quy hoạch tuyến tính. 5. Bài toán lập kế hoạch đầu tư vốn cho sản xuất Một doanh nghiệp cần đầu tư vốn vào n nhà máy khác nhau để sản xuất ra m loại sản phẩm với sản lượng tối thiểu từng loại là ),1( mjQj = . Do trang bị kỹ thuật- công nghệ và trình độ tổ chức sản xuất của các nhà máy khác nhau nên hiệu quả của vốn đầu tư vào các nhà máy khác nhau sẽ khác nhau. Qua khảo sát & phân tích, sau khoảng thời gian nhất định, một đơn vị tiền đầu tư vào nhà máy i sẽ thu được ),1,,1( mjniaij == sản xuất sản phẩm j . Tổng lượng nguyên liệu và tổng lao động mà doanh nghiệp có thể cung cấp trong thời gian đó lần lượt là M (đơn vị) và L (đơn vị). Biết rằng mức hao phí về nguyên liệu và lao động tại nhà máy i khi sản xuất sản phẩm j lần lượt là ),1,,1(& mjnicb ijij == . Hãy lập kế hoạch đầu tư sao cho tổng vốn đầu tư là nhỏ nhất. Gọi ix là số vốn đầu tư vào nhà máy i; với điều kiện ),1(0 nixi =≥ . Khi đó: + Số lượng sản phẩm j được sản xuất tại nhà máy i là iij xa (đơn vị); + Lượng nguyên liệu sử dụng để sản xuất sản phẩm j tại nhà máy i là ijiij bxa ; Quy hoạch tuyến tính Trang 4 Trường ĐH Lạc Hồng/ Khoa Quản trị- Kinh tế quốc tế Nguyễn Thanh Lâm- 2009 + Lượng nguyên liệu sử dụng để sản xuất m loại sản phẩm tại nhà máy i là ∑ = m j ijiij bxa 1 ; + Tổng nguyên liệu sử dụng để sản xuất m loại sản phẩm tại n nhà máy là ∑∑ = = n i m j ijiij bxa 1 1 ; + Tương tự, tổng lao động sử dụng để sản xuất m loại sản phẩm tại n nhà máy là ∑∑ = = n i m j ijiij cxa 1 1 ; + Tổng lượng sản phẩm j được sản xuất từ n nhà máy được tính bằng: ∑ = n i iij xa 1 ; Do đó, mô hình toán được viết như sau: min)( 1 →=∑ = n i ixxf ⎪⎪ ⎪⎪ ⎩ ⎪⎪ ⎪⎪ ⎨ ⎧ =≥ =≥ ≤ ≤ ∑ ∑∑ ∑∑ = = = = = ),1(0 ),1( 1 1 1 1 1 nix mjQxa Lcxa Mbxa i j n i iij n i m j ijiij n i m j ijiij Đây là một bài toán quy hoạch tuyến tính. Quy hoạch tuyến tính Trang 5 Trường ĐH Lạc Hồng/ Khoa Quản trị- Kinh tế quốc tế Nguyễn Thanh Lâm- 2009 BÀI 2. CÁC KHÁI NIỆM CƠ BẢN VỀ BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 1. Định nghĩa bài toán quy hoạch tuyến tính Bài toán quy hoạch tuyến tính dạng tổng quát (G) là bài toán có dạng sau: )1((min)max)( 1 →=∑ = n i ii xcxf ⎪⎪ ⎪⎪ ⎩ ⎪⎪ ⎪⎪ ⎨ ⎧ = ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ ≥ ≤ = ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ = ≥ ≤ ∑ = )3(),1(0 0 )2(),1( 1 ni ytuy x mjbxa i j n i iij Trong đó: + (1) được gọi là hàm mục tiêu của bài toán và )(xf là một hàm bậc nhất theo các ẩn của bài toán. Nếu max)( →xf thì bài toán đó được gọi là bài toán cực đại; còn nếu min)( →xf thì bài toán đó được gọi là bài toán cực tiểu; + (2) là một hệ gồm các phương trình hay bất phương trình bậc nhất theo các ẩn của bài toán và được gọi là hệ ràng buộc chính của bài toán. + (3) là các điều kiện về dấu của các ẩn và được gọi là hệ ràng buộc dấu của bài toán. Nếu ẩn có dấu tuỳ ý thì có thể không đưa vào hệ (3); Nếu bài toán không có hệ (3) thì ta hiểu rằng toàn bộ ẩn đều có dấu tuỳ ý. + Hệ (2) và (3) được gọi là chung là hệ ràng buộc của bài toán. 2. Các khái niệm liên quan + Đối với bài toán quy hoạch tuyến tính (G) n ẩn như trên, nếu tồn tại một vector n- chiều ),...,,( 21 nxxxx = thoả mãn hệ ràng buộc của bài toán (G) thì vector đó được gọi là một phương án của bài toán hay là một lời giải chấp nhận được. + Tập hợp tất cả các phương án của bài toán (G) được gọi là tập phương án của (G) và được ký hiệu là tập X. Tập X có thể là tập rỗng hay có 1 phần tử hay có vô số phần tử. + Phương án x* thoả mãn đẳng thức “=” một ràng buộc nào đó trong hệ ràng buộc thì ta nói phương án x* thoả mãn chặt ràng buộc đó. + Phương án x thoả mãn bất đẳng thức “>” hoặc “<” một ràng buộc nào đó trong hệ ràng buộc thì ta nói phương án x thoả mãn lỏng ràng buộc đó. + Phương án cơ bản (phương án cực biên) là một phương án thoả mãn chặt ít nhất n ràng buộc độc lập tuyến tính của bài toán (G). Một phương án thoả mãn chặt đúng n ràng buộc độc lập tuyến tính của bài toán thì được gọi là phương án cơ bản không suy biến; còn nếu nó thoả mãn chặt hơn n ràng buộc độc lập tuyến tính của bài toán thì được gọi là phương án cơ bản suy biến. + Phương án x0 được gọi là phương án tối ưu của bài toán (G) nếu f(x0) là giá trị lớn Quy hoạch tuyến tính Trang 6 Trường ĐH Lạc Hồng/ Khoa Quản trị- Kinh tế quốc tế Nguyễn Thanh Lâm- 2009 nhất (giá trị nhỏ nhất) trên tập phương án X của bài toán (G). Khi đó, f(x0) được gọi là giá trị tối ưu của bài toán. Nếu phương án tối ưu x0 là một phương án cơ bản thì x0 được gọi là phương án cơ bản tối ưu. + Bài toán quy hoạch tuyến tính có ít nhất một phương án tối ưu được gọi là bài toán giải được. + Bài toán quy hoạch tuyến tính không có phương án hoặc có phương án mà hàm mục tiêu không bị chặn trên (đối với bài toán cực đại) hay không chặn dưới (đối với bài toán cực tiểu) trên tập phương án của bài toán thì được gọi là bài toán không giải được. + Giải một bài toán quy hoạch tuyến tính là việc đi tìm lời giải tối ưu (phương án tối ưu và giá trị tối ưu) của bài toán hay chứng minh bài toán không giải được. Ví dụ 1: Xét bài toán quy hoạch tuyến tính (F) như sau: max32)( 4321 →+−+= xxxxxf ⎪⎪⎩ ⎪⎪⎨ ⎧ ≥ =−+ =+− =−+ 0,,, 12 432 42 4321 432 421 321 xxxx xxx xxx xxx Giải hệ ràng buộc của bài toán, ta có tập phương án: ⎪⎭ ⎪⎬ ⎫ ⎪⎩ ⎪⎨ ⎧ ⎥⎦ ⎤⎢⎣ ⎡∈⎟⎠ ⎞⎜⎝ ⎛ ++−= 14 29,0, 612 1, 3 2 6 5, 6 7 12 29 αααααX • Với 0=α , ta có phương án ⎟⎠ ⎞⎜⎝ ⎛= 0, 12 1, 6 5, 12 290x thoả mãn chặt 3 ràng buộc chính và một ràng buộc về dấu của x4 nên x0 là một phương án cơ bản của bài toán (F). Đồng thời x0 là một phương án cơ bản không suy biến. • Với 2=α , ta có phương án ⎟⎠ ⎞⎜⎝ ⎛= 2, 12 5, 6 13, 12 1*x thoả mãn chặt 3 ràng buộc chính và thoả mãn lỏng 4 ràng buộc về dấu cho nên x* không phải là một phương án cơ bản của bài toán (F). • Với tập phương án X, ta có hàm mục tiêu như sau: ⎟⎟⎠ ⎞⎜⎜⎝ ⎛ ⎥⎦ ⎤⎢⎣ ⎡∈→−= 14 29,0max 6 7 12 65)( ααxf Ta có ⎥⎦ ⎤⎢⎣ ⎡∈∀=≤−= 12 29,0)( 12 65 6 7 12 65)( 0 αα xfxf ; do đó, x0 là phương án cơ bản tối ưu và giá trị 12 65)( 0 =xf là giá trị tối ưu của bài toán (F). Ví dụ 2: Xét bài toán (F) trên nhưng không có hệ ràng buộc dấu, tức là các ẩn có dấu tuỳ ý. Khi đó, tập phương án của bài toán sẽ là: ⎭⎬ ⎫ ⎩⎨ ⎧ ⎟⎠ ⎞⎜⎝ ⎛ ++−= αααα , 612 1, 3 2 6 5, 6 7 12 29X và hàm mục tiêu max 6 7 12 65)( →−= αxf ; Khi −∞→α thì +∞→)(xf ; tức là f(x) không bị chặn trên trên tập phương án của bài toán; do đó, bài toán không có phương án tối ưu hay bài toán không giải được. Quy hoạch tuyến tính Trang 7 Trường ĐH Lạc Hồng/ Khoa Quản trị- Kinh tế quốc tế Nguyễn Thanh Lâm- 2009 3. Tính chất của bài toán quy hoạch tuyến tính Tính chất 1: Nếu một bài toán quy hoạch tuyến tính có phương án thì nó sẽ có phương án cơ bản và số phương án cơ bản của bài toán luôn hữu hạn. (Điều này được rút ra từ cơ sở: trong hệ ràng buộc chính của bài toán, ta chỉ có thể rút ra một số hữu hạn vectơ độc lập tuyến tính mà thôi). Tính chất 2: Nếu bài toán cực đại (cực tiểu) có phương án và hàm mục tiêu bị chặn trên (chặn dưới) trên tập phương án thì bài toán đó có phương án tối ưu. Tính chất 3: Nếu bài toán có phương án tối ưu thì nó có phương án cơ bản tối ưu. Tính chất 4: Nếu bài toán quy hoạch tuyến tính có hơn 1 phương án tối ưu thì bài toán sẽ có vô số phương án tối ưu. Giả sử bài toán có 2 phương án tối ưu là x0 và x* thì mọi vectơ x có dạng sau đều là phương án tối ưu của bài toán: [ ]( )1,0;)1( *0 ∈−+= ααα xxx Quy hoạch tuyến tính Trang 8 Trường ĐH Lạc Hồng/ Khoa Quản trị- Kinh tế quốc tế Nguyễn Thanh Lâm- 2009 BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 1. Bài toán quy hoạch tuyến tính dạng chính tắc a) Định nghĩa: Bài toán quy hoạch tuyến tính dạng chính tắc là bài toán quy hoạch tuyến tính có các ràng buộc chính là các phương trình và các ẩn đều không âm. b) Dạng chính tắc: (min)max...)( 2211 →+++= nn xcxcxcxf (min)max)( 1 →=∑ = n i ii xcxf ⎪⎪ ⎪ ⎩ ⎪⎪ ⎪ ⎨ ⎧ =≥ =+++ =+++ =+++ ),1(0 ... ................... ... ... 2211 22222121 11212111 nix bxaxaxa bxaxaxa bxaxaxa i mnmnmm nn nn ⎪⎩ ⎪⎨ ⎧ =≥ ==∑ = ),1(0 ),1( 1 nix mjbxa i j n i iji c) Ma trận điều kiện & Vector điều kiện Ma trận các hệ số của ràng buộc chính trong bài toán quy hoạch tuyến tính chính tắc được gọi là ma trận điều kiện, được ký hiệu là A. Cột hệ số của ẩn xi trong ma trận điều kiện A được gọi là cột điều kiện (vector điều kiện) của ẩn xi và ký hiệu là Ai. ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎣ ⎡ = mnmm n n aaa aaa aaa A ... ............................. ... ... 21 22221 11211 ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎣ ⎡ = mi i i i a a a A ... 2 1 d) Định lý Cho bài toán quy hoạch tuyến tính dạng chính tắc như sau: (min)max)( 1 →=∑ = n i ii xcxf ⎪⎩ ⎪⎨ ⎧ =≥ ==∑ = ),1(0 ),1( 1 nix mjbxa i j n i iji Điều kiện cần và đủ để phương án ),...,,( **2*1* nxxxx = là một phương án cơ bản của bài toán là hệ vector điều kiện { }0* >ii xA độc lập tuyến tính. Một hệ các vector {v1, v2, …, vn} trong không gian vector V được gọi là độc lập tuyến tính khi và chỉ khi phương trình vector 0 1 =∑ = n i iivk chỉ có nghiệm duy nhất: k1 = k2 = ... = kn = 0. e. Biến đổi bài toán về dạng chính tắc Mọi bài toán quy hoạch tuyến tính đều có thể được đưa về dạng chính tắc bằng các biện pháp sau: @ Hệ ràng buộc chính có bất phương trình: ta thêm vào những ràng buộc bất phương trình đó các ẩn phụ không âm để đưa ràng buộc đó về phương trình; nguyên tắc thêm ẩn phụ như sau: Dạng rút gọn Quy hoạch tuyến tính Trang 9 Trường ĐH Lạc Hồng/ Khoa Quản trị- Kinh tế quốc tế Nguyễn Thanh Lâm- 2009 + Nếu ràng buộc chính có dạng j n i iji bxa ≤∑ =1 thì ta cộng vào vế trái của ràng buộc này một ẩn không âm knx + để ràng buộc chính trở thành jkn n i iji bxxa =+ + = ∑ 1 . + Nếu ràng buộc chính có dạng j n i iji bxa ≥∑ =1 thì ta trừ vào vế trái của ràng buộc này một ẩn không âm knx + để ràng buộc chính trở thành jkn n i iji bxxa =− + = ∑ 1 . + Nếu số hạng tự do ở ràng buộc j âm )0( <jb thì ta tiến hành đổi dấu hai vế sao số hạng tự do này không âm trước khi tiến hành thêm ẩn phụ (đối với ràng buộc bất phương trình). Các biến phụ chỉ là những đại lượng giúp ta biến các ràng buộc dạng bất đẳng thức thành đẳng thức, nó phải không ảnh hưởng gì đến hàm mục tiêu nên không xuất hiện trong hàm mục tiêu. @ Ràng buộc về dấu không thoả điều kiện không âm (ẩn có dấu tuỳ ý hay 0≤ ) + Nếu ẩn 0≤ix thì ta thực hiện phép đổi biến số 'ii xx −= với điều kiện 0' ≥ix . + Nếu ẩn ix có dấu tuỳ ý thì ta thực hiện phép đổi biến ''' iii xxx −= với điều kiện 0, ''' ≥ii xx . * Ghi chú: - Bài toán đã cho được gọi là bài toán gốc. Bài toán sau khi biến đổi được gọi là bài toán phụ. - Bài toán phụ có hay không có phương án tối ưu thì bài toán gốc cũng có hay không có phương án tối ưu tương ứng. Nếu có phương án tối ưu, phương án tối ưu của bài toán gốc được rút ra từ bài toán phụ bằng cách bỏ đi phần ẩn phụ và đổi các trị số của biến mới về biến cũ theo các công thức đổi biến đã dùng. ** Ví dụ 1: Biến đổi bài toán sau về dạng chính tắc min222)( 54321 →−++−= xxxxxxf ⎪⎪ ⎪⎪ ⎩ ⎪⎪ ⎪⎪ ⎨ ⎧ ≤ ≥ =+−+ ≥++ −≥++ ≤+++− 0 0, 202 1032 12 722 4 51 4321 543 432 54321 x xx xxxx xxx xxx xxxxx Giải: Đặt ⎪⎪⎩ ⎪⎪⎨ ⎧ ≥ −= −= −= 0,,,, '4 '' 3 ' 3 '' 2 ' 2 '' 3 ' 33 '' 2 ' 22 ' 44 xxxxx xxx xxx xx Khi đó ⎪⎪ ⎪ ⎩ ⎪⎪ ⎪ ⎨ ⎧ ≥ =−−−−+ =−+−− =++−−−− =++−−+−− →−−−+−−= 0,,,,,,,,, 20)(2)( 103)(2 1)(2)( 72)()(2 min2)(2)(2)( 8765 ' 4 '' 3 ' 3 '' 2 ' 21 ' 4 '' 3 ' 3 '' 2 ' 21 85 ' 4 '' 3 ' 3 7 ' 4 '' 3 ' 3 '' 2 ' 2 65 ' 4 '' 3 ' 3 '' 2 ' 21 5 ' 4 '' 3 ' 3 '' 2 ' 21 xxxxxxxxxx xxxxxx xxxxx xxxxxx xxxxxxxx xxxxxxxxf Quy hoạch tuyến tính Trang 10 Trường ĐH Lạc Hồng/ Khoa Quản trị- Kinh tế quốc tế Nguyễn Thanh Lâm- 2009 ** Ví dụ 2: Đưa bài toán quy hoạch tuyến tính sau về dạng chính tắc ⎪⎪⎩ ⎪⎪⎨ ⎧ ≥ −≥−− ≤+− ≥++− →−+−+= 0, 232 952 4232 max832)( 31 432 321 4321 4321 xx xxx xxx xxxx xxxxxf (Sinh viên tự giải) 2. Bài toán quy hoạch tuyến tính dạng chuẩn tắc a) Định nghĩa: Bài toán quy hoạch tuyến tính dạng chuẩn tắc là một bài toán quy hoạch tuyến tính dạng chính tắc trong đó hệ ràng buộc chính có các số hạng tự do đều không âm và mỗi ràng buộc chính đều có một ẩn cơ bản. Đó là ẩn có hệ số là 1 ở một ràng buộc chính và có hệ số là 0 ở các ràng buộc còn lại. Ẩn cơ bản nằm ở ràng buộc thứ i được gọi là ẩn cơ bản thứ i, các ẩn còn lại của bài toán được gọi là ẩn tự do. b) Dạng của bài toán: ⎪