Giải bài toán quy hoạch tuyến tính bằng phương pháp đơn hình

bài toán đối ngẫu, bài toán đơn hình, bài toán khẩu phần thức ăn, bài toán lập kế hoạch sản xuất, phân công lao động:

BÀI TOÁN QUY HOẠCH TUYẾN TÍNH.
PHƯƠNG PHÁP ĐƠN HÌNH

Bài toán quy hoạch tuyến tính

 Bài toán lập kế hoạch sản xuất:

Một cơ sở có thể sản xuất hai loại sản phẩm A và B, từ các nguyên liệu I, II, III.Chi phí từng loại nguyên liệu và tiền lãi của một đơn vị sản phẩm, cũng như dự trữ nguyên liệu cho trong bảng sau đây:Nguyên liệuSản phẩm. I II III Lãi A 2 0 1 3.B 1 1 0 5. Dự trữ 8 4 3. Hãy lập bài toán thể hiện kế hoạch sản xuất sao cho có tổng số lãi lớn nhất, trên cơ sở dự trữ nguyên liệu đã có. Lập bài toán: Gọi x, y lần lượt là số sản phẩm A và B được sản xuất [ x, y ≥ 0 , đơn vị sản phẩm].

Khi đó ta cần tìm x, y ≥ 0 sao cho đạt lãi lớn nhất.f []3 5 X xy =+→max với điều kiện nguyên liệu:

 Bài toán phân công lao động:

Một lớp học cần tổ chức lao động với hai loại công việc: xúc đất và chuyển đất.Lao động của lớp được chia làm 3 loại A, B, C, với số lượng lần lượt là 10, 20, 12.Năng suất của từng loại lao động trên từng công việc cho trong bảng dưới đây

Lao động. Công việc. A[10] B[20] C[12]. Xúc đất 6 5 4. Chuyển đất 4 3 2. Hãy tổ chức lao động sao cho có tổng năng suất lớn nhất.

Lập bài toán:
Gọi xij là số lao động loại j làm công việc i[j=1,2;xij , nguyên]. Khi đó, năng suất lao động của công việc đào đất sẽ là: ≥ 0. 11 12 13 654 x + + x x ;còn chuyển đất sẽ là : 21 22 23 432 x + x x + ;Ta thấy rằng để có năng suất lớn nhất thì không thể có lao động dư thừa, tức là phải cân bằng giữa hai công việc. Vì vậy ta có bài toán sau:

Bài toán khẩu phần thức ăn:

Một khẩu phần thức ăn có khối lượng P, có thể cấu tạo từ n loại thức ăn. Gía mua
một đơn vị thức ăn loại j là cj. Để đảm bảo cơ thể phát triển bình thường thì khẩu phần
cần m loại chất dinh dưỡng. Chất dinh dưỡng thứ i cần tối thiểu cho khẩu phần là bi và
có trong một đơn vị thức ăn loại j là aij.Hỏi nên cấu tạo một khẩu phần thức ăn như thế nào để ăn đủ no, đủ chất dinh. dưỡng mà có giá thành rẻ nhất.
Lập bài toán:
Gọi xj [xj ] là số đơn vị thức ăn loại j được cấu tạo trong khẩu phần. Khi đó,
giá thành của khẩu phần là:≥ 0
Vì phải đảm bảo thoả mãn điều kiện đủ no và đủ chất, tức là: P ax b i m1, . = =∑ ∑ = ≥=Ta có bài toán sau: 1với điều kiện. Ta thấy rằng ba bài toán trên đều thuộc bài toán tổng quát.

Bài toán quy hoạch tuyến tính tổng quát

Bài toán tổng quát của QHTT có dạng :với điều kiện. Để phân biệt tính chất của các ràng buộc đối với một phương án, ta làm quen với. hai khái niệm : ràng buộc chặt và ràng buộc lỏng.

Phương án x thỏa mãn ràng buộc i

Định nghĩa 1: Nếu đối với phương án x mà ràng buộc i thỏa mãn với dấu đẳng. thức, nghĩa là thì ta nói phương án x thỏa mãn chặt ràng buộc i. Nếu đối với phương án x mà ràng buộc i thỏa mãn với dấu bất đẳng thức thực sự. nghĩa là thì ta nói phương án x thỏa mãn lỏng ràng buộc i

phương án thỏa mãn chặt n ràng buộc độc lập tuyến tính

Định nghĩa 2 : Ta gọi một phương án thỏa mãn chặt n ràng buộc độc lập tuyến tính là phương án cực biên. Một phương án cực biên thỏa mãn chặt đúng n ràng buộc. gọi là phương án cực biên không suy biến, thỏa mãn chặt hơn n ràng buộc gọi là phương án cực biên suy biến.. 

Phương án tối ưu

Định nghĩa 3: Một phương án mà tại đó hàm mục tiêu đạt cực tiểu [ cực đại ] gọi là phương án tối ưu. Bài toán có ít nhất một phương án tối ưu gọi là bài toán giải được, bài toán không có phương án hoặc có phương án nhưng hàm mục tiêu không bị chặn dưới [ trên ] trên tập phương án gọi là không giải được.. Để nhất quán trong lập luận, ta xét bài toán tìm cực tiểu, sau đó ta xét cách đưa bài toán tìm cực đại về bài toán tìm cực tiểu.

* Chuyển bài toán tìm cực đại về bài toán tìm cực tiểu :

Nếu gặp bài toán tìm max, tức là :thì giữ nguyên ràng buộc, ta đưa nó về dạng bài toán tìm min :
Chứng minh :Nếu bài toán tìm min có phương án tối ưu là X* thì bài toán tìm max cũng có phương án tối ưu là X*
và g[X]= – f[X].. Thật vậy, X* là phương án tối ưu của bài toán tìm min, tức là  phương án tối ưu của bài toán max và

 Dạng chính tắc của bài toán quy hoạch tuyến tính

Người ta thường xét bài toán QHTT dưới dạng sau:: Bài toán [1.1], [1.2], [1.3] được gọi là Bài toán Quy hoạch tuyến tính dạng chính tắc. Kí hiệu ma trận hàng 12 1 [ , ,…, ]n n c cc c = × và các ma trận :

Dạng chuẩn tắc của bài toán tối ưu:

Đối với bài toán dạng chính tắc ta có một số tính chất và khái niệm quan trọng của phương án cực biên như sau :

Phương pháp đơn hình-các bài toán quy hoạch tuyến tính

Xem file PDF 

Tags: quy hoạch tuyến tính

Tài liệu Giáo án môn toán - Chương 2 : Phương pháp đơn hình: Chương 2 : PHƯƠNG PHÁP ĐƠN HÌNH Phương pháp đơn hình do G.B. Dantzig đề xuất năm 1947 cho đến hiện nay vẫn là phương pháp được sử dụng nhiều nhất trong việc giải các bài toán qui hoạch tuyến tính. Đối với các bài toán cỡ lớn [có thể đến hàng nghìn biến và hàng trăm ràng buộc] phải dùng đến máy tính, phương pháp đơn hình cũng đã được kiểm nghiệm qua mấy chục năm áp dụng là rất hiệu quả, với thời gian tính toán khá ngắn. §1. CƠ SỞ CỦA PHƯƠNG PHÁP ĐƠN HÌNH Phương pháp đơn hình giải bài toán QHTT dựa trên hai tính chất quan trọng sau đây của bài toán QHTT: a] Nếu bài toán qui hoạch tuyến tính chính tắc có phương án tối ưu thì cũng có phương án cực biên tối ưu, nghĩa là có ít nhất một đỉnh của miền ràng buộc là lời giải của bài toán. b] Mỗi điểm cực tiểu địa phương của hàm tuyến tính trên miền ràng buộc D [một tập hợp lồi] là một điểm cực tiểu tuyệt đối. Tính chất a] cho phép tìm phương án tối ưu trong số các ...

Bạn đang xem nội dung tài liệu Giáo án môn toán - Chương 2 : Phương pháp đơn hình, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên

Chương 2 : PHƯƠNG PHÁP ĐƠN HÌNH Phương pháp đơn hình do G.B. Dantzig đề xuất năm 1947 cho đến hiện nay vẫn là phương pháp được sử dụng nhiều nhất trong việc giải các bài toán qui hoạch tuyến tính. Đối với các bài toán cỡ lớn [có thể đến hàng nghìn biến và hàng trăm ràng buộc] phải dùng đến máy tính, phương pháp đơn hình cũng đã được kiểm nghiệm qua mấy chục năm áp dụng là rất hiệu quả, với thời gian tính toán khá ngắn. §1. CƠ SỞ CỦA PHƯƠNG PHÁP ĐƠN HÌNH Phương pháp đơn hình giải bài toán QHTT dựa trên hai tính chất quan trọng sau đây của bài toán QHTT: a] Nếu bài toán qui hoạch tuyến tính chính tắc có phương án tối ưu thì cũng có phương án cực biên tối ưu, nghĩa là có ít nhất một đỉnh của miền ràng buộc là lời giải của bài toán. b] Mỗi điểm cực tiểu địa phương của hàm tuyến tính trên miền ràng buộc D [một tập hợp lồi] là một điểm cực tiểu tuyệt đối. Tính chất a] cho phép tìm phương án tối ưu trong số các phương án cực biên của bài toán [số này là hữu hạn]. Tính chất b] cho phép khi kiểm tra tối ưu đối với một phương án cực biên [đỉnh] chỉ cần so sánh nó với các đỉnh lân cận [đỉnh kề] là đủ. Vì thế, phương pháp đơn hình bắt đầu từ một phương án cực biên nào đó [tuỳ ý] của bài toán [tức là một đỉnh của miền ràng buộc]. Tiếp đó kiểm tra xem phương án hiện có đã phải là phương án tối ưu hay chưa, bằng cách so sánh giá trị hàm mục tiêu tại đỉnh đó với giá trị hàm mục tiêu tại các đỉnh kề với nó. Nếu đúng thì dừng quá trình tính toán. Trái lại, phương pháp sẽ cho cách tìm một phương án cực biên mới tốt hơn [với giá trị hàm mục tiêu nhỏ hơn] mà nó là một đỉnh kề với đỉnh trước đó. Quá trình này tiến hành cho tới khi tìm được phương án tối ưu hoặc phát hiện bài toán đã cho không có lời giải. Như vậy, phương pháp đơn hình tiến hành khảo sát các đỉnh của miền ràng buộc để tìm ra đỉnh tối ưu. Mặc dù số đỉnh của bài toán nói chung rất lớn, nhưng trên thực tế phương pháp này chỉ đòi hỏi kiểm tra một phần tương đối nhỏ các đỉnh. Chính điều đó thể hiện hiệu quả thực tế của phương pháp đơn hình. §2. THUẬT TOÁN ĐƠN HÌNH Để giải bìa toán QHTT [G] bằng phương pháp đơn hình ta thực hiện các bước dưới đây. Bước chuẩn bị: Đưa [G] về dạng chính tắc chuẩn [N] nếu cần. Bước 1: Xác định PACB xo xuất phát, chỉ ra các biến và các hệ số cơ sở. [Nếu bài toán dạng [N] thì một PACB được tìm dễ dàng từ ma trận con sơ cấp của A – trong bảng đơn hình ở bước 2, ma trận con sơ cấp được giả định là ma trận đơn vị cấp m tạo thành từ m dòng và m cột đầu tiên, khi đó PACB xuất phát chính là x0 = [b1, b2, , bm, 0, , 0]]. Bước 2: Lập bảng đơn hình, tính giá trị của hàm mục tiêu và các số ước lượng Dj. Hệ số cơ sở Biến cơ sở PA CB x1 x2 xm xm+1 xn c1 c2 cm cm+1 cn c1 c2 . . . cm x1 x2 . . . xm b1 b2 . . . bm 1 0 0 a1,m+1 a1n 0 1 0 a2,m+1 a2n . . . . . . . . . . . . . . . 0 0 1 am,m+1 amn Bảng 1 f [x0] 0 0 0 Dm+1 Dn Ở đây f[x0] = c1b1 + c2b2 + + cmbm; Dj = 0 [j=1,, m]; Dj = . Bước 3: Kiểm tra điều kiện tối ưu [Đối với bài toán MIN] Nếu mọi phương án đang xét tối ưu ® STOP. Nếu tồn tại mà mọi thì hàm mục tiêu không bị chặn, do đó bài toán đã cho vô nghiệm ® STOP. Nếu tồn tại và với mỗi đều có ít nhất một thì phương án đang xét chưa tối ưu ® Làm tiếp bước 4. Bước 4: Cải tiến PACB đang xét để được PACB tốt hơn [Đối với bài toán MIN] Chọn biến cơ bản mới sao cho để đưa vào. Chọn biến cơ bản cũ sao cho để đưa ra. Tiếp theo chọn dòng thứ r làm dòng xoay, cột thứ v làm cột xoay, phần tử làm phần tử xoay rồi biến đổi sơ cấp để được bảng đơn hình mới với PACB mới tốt hơn. Cách biến đổi bảng đơn hình để nhận được bảng mới và PACB mới tốt hơn Đổi cột biến cơ sở: biến cơ sở mới là xv thay cho biến cơ sở cũ là xr ở dòng r. Đổi cột hệ số cơ sở: hệ số cv thay cho hệ số cr ở dòng r. Biến đổi dòng xoay: Dòng mới = dòng cũ / phần tử xoay, Nghĩa là chia mỗi phần tử ở dòng xoay cho phần tử xoay [arv > 0]. Kết quả nhận được gọi là dòng chính [số 1 xuất hiện ở vị trí của arv cũ]. Biến đổi các dòng khác theo qui tắc hình chữ nhật: Dòng mới = dòng cũ tương ứng - phần tử của nó trên cột xoay × dòng chính, nghĩa là Cột ≠ cột xoay Cột xoay [cột v] Dòng ≠ dòng xoay : a b a’ = a – bc Dòng chính [dòng r mới] : c 1 Sau đó lặp lại các bước 2, 3, 4 cho đến khi được P.A.C.B tối ưu thì dừng và kết luận về đáp số của bài toán đã cho Chú ý Ở bước 3 khi kiểm tra điều kiện tối ưu đối với bài toán MAX, ta làm như sau: Nếu mọi phương án đang xét tối ưu ® STOP. Nếu tồn tại mà mọi thì hàm mục tiêu không bị chặn, do đó bài toán đã cho vô nghiệm ® STOP. Nếu tồn tại mà với mỗi đều có ít nhất một thì phương án đang xét chưa tối ưu ® Làm tiếp bước 4. Còn ở bước 4 khi cải tiến PACB đối với bài toán MAX, ta làm như sau: Chọn biến cơ bản mới sao cho để đưa vào. Chọn biến cơ bản cũ sao cho để đưa ra. Tiếp theo chọn dòng thứ r làm dòng xoay, phần tử làm phần tử xoay rồi biến đổi sơ cấp để được bảng đơn hình mới. Cũng có thể quy bài toán MAX về bài toán MIN hoặc ngược lại bằng cách đối dấu hàm mục tiêu. Dấu hiệu bài toán vô số nghiệm: Khi kiểm tra điều kiện tối ưu ở bước 3, nếu mọi [đối với bài toán MIN] hoặc [đối với bài toán MAX] đồng thời tồn tại một ứng với biến phi cơ sở thì bài toán có vô số nghiệm. Cách tìm hết tất cả các PATU của bài toán QHTT: Giả sử đã tìm ra một PATU . Khi đó giải hệ gồm phương trình và các ràng buộc ta sẽ được tất cả các PATU của bài toán đã cho. Ví dụ 1. Giải bài toán qui hoạch tuyến tính [N] sau đây f = x1 – x2 – 2x4 + 2x5 – 3x6 → min, với các điều kiện x1 + x4 + x5 - x6 = 2, x2 + x4 + x6 = 12, x3 + 2x4 + 4x5 + 3x6 = 9, xj ≥ 0, j = 1, 2, ... , 6. Cho x4 = x5 = x6 = 0 ta được phương án cực biên ban đầu x0 = [2; 12; 9; 0; 0; 0] với trị mục tiêu f0 = -10. Cơ sở của x0 là {A1, A2, A3}, tức là J0 = {1, 2, 3}. Các biến cơ sở là x1, x2, x3. Các biến phi cơ sở là x4, x5, x6. Các hệ số cơ sở c1= 1, c2 = – 1, c3 = 0. Bảng đơn hình đầu tiên như sau: Hệ số cơ sở Biến cơ sở PACB x1 x2 x3 x4 x5 x6 1 -1 0 -2 2 -3 1 x1 2 1 0 0 1 1 –1 2 –1 x2 12 0 1 0 1 0 1 12 0 x3 9 0 0 1 2 4 3 9/2 Bảng 1 -10 0 0 0 2 –1 1 Trong dòng mục tiêu [dòng cuối] còn = 2 > 0, = 1> 0 và trên mỗi cột chứa mỗi số ước lượn dương đó đều có những hệ số dương nên phương án x0 ở bảng này chưa tối ưu. Ta cần biến đổi bảng để dược PACB mới tốt hơn. Biến cơ sở mới cần đưa vào là x4 [ứng với = 2 lớn nhất]. Biến loại khỏi cơ sở là x1 [ứng với = min{2, 12, 9/2} = 2 nhỏ nhất]. Phần tử xoay là a14 = 1 [trong ô được tô bóng mờ]. Biến đổi bảng 1 theo các qui tắc đã nêu ta nhận được bảng 2 dưới đây. Hệ số cơ sở Biến cơ sở PACB x1 x2 x3 x4 x5 x6 1 –1 0 –2 2 –3 –2 x4 2 1 0 0 1 1 –1 –1 x2 10 –1 1 0 0 –1 2 5 0 x3 5 –2 0 1 0 2 5 1 Bảng 2 –14 –2 0 0 0 –3 3 Trong dòng cuối của bảng này còn phần tử D6 = 3 > 0 và trên cột chứa nó có hai hệ số dương nên phương án ở bảng này vẫn chưa tối ưu. Ta cần biến đổi bảng để dược PACB mới tốt hơn. Biến cơ sở mới cần đưa vào x6 [ứng với = 3 lớn nhất]. Biến loại khỏi cơ sở là x3 [ứng với tỉ số nhỏ nhất = min{5, 1} = 1]. Phần tử xoay là a36 = 5. Biến đổi bảng 2 ta nhận được bảng 3 dưới đây. Hệ số cơ sở Biến cơ sở PACB x1 x2 x3 x4 x5 x6 1 –1 0 –2 2 –3 –2 x4 3 3/5 0 1/5 1 7/5 0 –1 x2 8 –1/5 1 –2/5 0 –9/5 0 –3 x6 1 –2/5 0 1/5 0 2/5 1 Bảng 3 –17 –4/5 0 –3/5 0 –21/5 0 Trong bảng này mọi ≤ 0, nên phương án x* = [0; 8; 0; 3; 0; 1] là PATU với fmin = f[x*] = – 17. Ví dụ 2. Ví dụ sau cho thấy bài toán không có phương án tối ưu f = x2 – 3x3 + 2x5 → min, x1 + x2 – x3 + x5 = 7, – 4x2 + 4x3 + x4 = 12, –5x2 + 3x3 + x5 + x6 = 10, xj ≥ 0, j = 1, 2, ... , 6. Ta giải bài toán trên bằng phương pháp đơn hình, xuất phát từ phương án cực biên x0 = [7, 0, 0, 12, 0, 10] với cơ sở là các véctơ cột đơn vị A1, A4, A6, tức là J0 = {1, 4, 6}. Lập bảng đơn hình rồi thự hiện các tính toán biến đổi theo thuật toán đơn hình ta được: Biến cơ sở Hệ số CB Phương án x1 x2 x3 x4 x5 x6 0 1 -3 0 2 0 x1 0 7 1 1 -1 0 1 0 x4 0 12 0 -4 4 1 0 0 3 x6 0 10 0 -5 3 0 1 1 10/3 Bảng 1 0 0 -1 3 0 -2 0 x1 0 10 1 0 0 1/4 1 0 x3 -3 3 0 -1 1 1/4 0 0 x6 0 1 0 -2 0 -3/4 1 1 Bảng 2 -9 0 2 0 -3/4 -2 0 Trong bảng 2 có = 2 > 0 nhưng mọi phần tử ai2 ≤ 0 [i = 1, 2, 3] nên bài toán trên không có PATU [vì hàm mục tiêu của bài toán giảm vô hạn trong miền ràng buộc của nó]. Nói cách khác, bài toán QHTT đã cho không có lời giải. Chú ý: Bài toán tìm g → max được thay bằng bài toán tìm f = – g → min. Ví dụ 3. Giải bài toán qui hoạch tuyến tính sau. f = 3x1 – x2 – 2x3 → max, –x1 + 3x2 + x3 + x4 = 7, 3x1 – 4x2 + 8x3 + x5 = 10, 4x1 – 2x2 + x6 = 12, xj ≥ 0, j = 1, 2, ... , 6. Ta thay f bằng g = – f = – 3x1 + x2 + 2x3 → min với cùng các điều kiện như trên. Xuất phát từ phương án cực biên x0 = [0, 0, 0, 7, 10, 12], ta giải bài toán bằng phương pháp đơn hình [các Bảng 1 - 3]. Lời giải thu được là x* = [5, 4, 0, 0, 11, 0] với gmin = –11. Từ đó fmax = 11. Biến cơ sở Hệ số CB Phương án x1 x2 x3 x4 x5 x6 -3 1 2 0 0 0 x4 0 7 -1 3 1 1 0 0 x5 0 10 3 -4 8 0 1 0 10/3 x6 0 12 4 -2 0 0 0 1 3 Bảng 1 0 3 -1 -2 0 0 0 x4 0 10 0 5/2 1 1 0 1/4 4 x5 0 1 0 -5/2 8 0 1 -3/4 x1 -3 3 1 -1/2 0 0 0 1/4 Bảng 2 -9 0 1/2 -2 0 0 -3/4 x2 1 4 0 1 2/5 2/5 0 1/10 x5 0 11 0 0 9 1 1 -1/2 x1 -3 5 1 0 1/5 1/5 0 3/10 Bảng 3 -11 0 0 -11/5 -1/5 0 -4/5 Ví dụ 4. Giả bài toán [C] : f[x] = 3x1 – 3x2 + x3 – x4 → min, –x1 + x2 + 2x3 + x4 = 2, x1 + x2 – x3 – x4 = 6, 3x1 + 2x2 – 6x3 + 3x4 = 9, x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0. Đưa vào ba biến giả x5, x6, x7 ≥ 0 với hệ số giả M > 0 [đủ lớn] ta được bài toán [N] F = 3x1 – 3x2 + x3 – x4 + M [x5 + x6 + x7] → min, –x1 + x2 + 2x3 + x4 + x5 = 2, x1 + x2 – x3 – x4 + x6 = 6, 3x1 + 2x2 – 6x3 + 3x4 + x7 = 9, xj ≥ 0 [j = 1, 2, 3, 4, 5, 6, 7]. Ta giải bài toán [N] bằng phương pháp đơn hình, xuất phát từ phương án cực biên x0 = [0, 0, 0, 0, 2, 6, 9]. Quá trình giải bài toán [N] được ghi tóm tắt trong các bảng sau [Bảng 1 - 4]. Biến cơ sở CB Phương án x1 x2 x3 x4 x5 x6 x7 θ 3 -3 1 -1 M M M x5 M 2 -1 1 2 1 1 0 0 2 x6 M 6 1 1 -1 -1 0 1 0 6 x7 M 9 3 2 -6 3 0 0 1 4.5 Bảng 1 17M 3M-3 4M+3 < 0 3M+1 0 0 0 x2 -3 2 -1 1 2 1 0 0 x6 M 4 2 0 -3 -2 1 0 2 x7 M 5 5 0 -10 1 0 1 1 Bảng 2 9M-6 7M 0 < 0 < 0 0 0 x2 -3 3 0 1 0 6/5 0 x6 M 2 0 0 1 -12/5 1 2 x1 3 1 1 0 -2 1/5 0 Bảng 3 2M-6 0 0 M-7 < 0 0 x2 -3 3 0 1 0 6/5 x3 1 2 0 0 1 -12/5 x1 3 5 1 0 0 -23/5 Bảng 4 8 0 0 0 -94/5 Ở Bảng 4 ta thấy ∆k ≤ 0 với mọi k = 1, 2, 3, 4, nên phương án cho ở bảng này x = [5, 3, 2, 0, 0, 0, 0] là phương án tối ưu của bài toán [M]. Vậy x* = [5, 3, 2, 0] là phương án tối ưu của bài toán ban đầu với fmin = 8. §4. VÍ DỤ GIẢI BÀI TOÁN QHTT DẠNG TỎNG QUÁT [G] Ví dụ 1. Giải bài toán sau bằng phương pháp đơn hình. f = 5x1 + 8x2 → max, x1 + 2x2 ≤ 1, x1 + x2 ≤ 2, x1 ≥ 0, x2 ≥ 0. Trước hết ta chuyển bài toán trên về bài toán tìm min và có dạng [N] bằng cách đưa vào các biến phụ x3, x4 ≥ 0. Ta được bài toán g = – 5x1 – 8x2 → min, x1 + 2x2 + x3 = 1, x1 + x2 + x4 = 2, xj ≥ 0, j = 1, 2, 3, 4. Ta giải bài toán này bằng phương pháp đơn hình, xuất phát từ phương án cực biên x0 = [0, 0, 1, 2]. Cơ sở của x0 là {A3, A4}. Quá trình giải như sau [Bảng 1 - 3]. Biến cơ sở CB Phương án x1 x2 x3 x4 -5 -8 0 0 x3 0 1 1 2 1 0 ½ x4 0 2 1 1 0 1 2 Bảng 1 0 5 8 0 0 x2 -8 1/2 1/2 1 1/2 0 1 x4 0 3/2 1/2 0 -1/2 1 3 Bảng 2 -4 1 0 -4 0 x1 -5 1 1 2 1 0 x4 0 1 0 -1 -1 1 Bảng 3 -5 0 -2 -5 0 Ở Bảng 3 mọi ∆k ≤ 0 nên x*N = [1, 0, 0, 1] là phương án tối ưu của bài toán chính tắc với gmin = – 5. Từ đó suy ra lời giải bài toán ban đầu là x* = [1, 0] với fmax = – gmin= 5. Ví dụ 2. Giải bài toán sau f = – 3x1 + x2 – 2x3 → min, 2x1 + 4x2 – x3 ≤ 10, 3x1 + x2 + x3 ≥ 4, x1 – x2 + x3 = 2, xj ≥ 0, j = 1, 2, 3. Trước hết ta thêm vào hai biến phụ x4, x5 ≥ 0 để đưa bài toán về dạng chính tắc [C]. Tiếp đó ta đưa vào hai biến giả x6, x7 ≥ 0 để được bài toán [N] như sau. fM = - 3x1 + x2 - 2x3 + M[x6 + x7] → min, 2x1 + 4x2 - x3 + x4 = 10, 3x1 + x2 + x3 - x5 + x6 = 4, x1 - x2 + x3 + x7 = 2, xj ≥ 0, j = 1, 2, ... , 7. Ta giải bài toán [N] bằng phương pháp đơn hình với M > 0 [đủ lớn]. Quá trình giải ghi ở các bảng sau [bỏ qua hai cột biến giả]. Biến cơ sở CB Phương án x1 x2 x3 x4 x5 -3 1 -2 0 0 x4 0 10 2 4 -1 1 0 5 x6 M 4 3 1 1 0 -1 4/3 x7 M 2 1 -1 1 0 0 2 Bảng 1 60 4M+3 – 1 2M +2 0 – M x4 0 22/3 0 10/3 -5/3 1 2/3 x1 -3 4/3 1 1/3 1/3 0 -1/3 4 x7 M 2/3 0 -4/3 2/3 0 1/3 1 Bảng 2 2M/3- 4 0 < 0 2M/3+1 0 M/3+1 x4 0 9 0 0 0 1 3/2 6 x1 -3 1 1 1 0 0 -1/2 x3 -2 1 0 -2 1 0 1/2 2 Bảng 3 -5 0 0 0 0 1/2 x4 0 6 0 6 -3 1 0 1 x1 -3 2 1 -1 1 0 0 x5 0 2 0 -4 2 0 1 Bảng 4 -6 0 2 -1 0 0 x2 1 1 0 1 -1/2 1/6 0 x1 -3 3 1 0 1/2 1/6 0 x5 0 6 0 0 0 2/3 1 Bảng 5 -8 0 0 0 -1/3 0 Ở Bảng 5 mọi ∆k ≤ 0 nên x = [3, 1, 0, 0, 6, 0, 0] là phương án tối ưu của bài toán [N]. Từ đó suy ra lời giải bài toán ban đầu là x* = [3, 1, 0] với fmin = – 8. BÀI TẬP 1. Dùng phương pháp đơn hình giải các bài toán dưới đây a] f = – 50x1 – 60x2 ® min, x1 + 2x2 £ 8, x1 + x2 £ 5, 9x1 + 4x2 £ 36, x1 ³ 0, x2 ³ 0. b] f = 2x1 + 5x2 + 4x3 + x4 – 5x5 ® min, x1 + 2x2 + 4x3 – 3x5 = 152, 4x2 + 2x3 + x4 + 3x5 = 60, 3x2 + x5 £ 36, xj ³ 0 [j = 1,2,...,5]. c] f = 6x1 + x2 + x3 + 3x4 + x5 – 7x6 + 6x7 ® min, –x1 + x2 – x4 + x6 + x7 = 15, 2x1 – x3 + 2x6 + x7 = –9, 4x1 + 2x4 + x5 – 3x6 = 2, xj ³ 0 [j = 1,...,7]. f = x1 – x2 ® min, x1 – x2 ³ –1, 3x1 + 2x2 £ 6, –3x1 – x2 ³ –9, x1³ 0, x2 ³ 0. e] f = 2x1 + x2 + x3 → min, x1 + x2 + x3 + x4 + x5 = 5, x1 + x2 + 2x3 + 2x4 + 2x5 = 8, x1 + x2 = 2, x3 + x4 + x5 = 3, xj ³ 0 [j = 1,...,4]. f]] f = – x1 – 2x2 – 3x3 + x4 ® min, x1 + 2x2 + 3x3 = 15, 2x1 + x2 + 5x3 = 20, x1 + 2x2 + x3 + x4 = 10, xj ³ 0 [j = 1,...,4]. g] f = x1 + 2x2 – x3 ® max, – x1 + 4x2 – 2x3 £ 6, x1 + x2 + 2x3 ³ 6, 2x1 – x2 + 2x3 = 4, x1³ 0, x2 ³ 0, x3 ³ 0. . h] f = – x1 –x2 + 1 ® max, x1 – x2 ³ –1, 3x1 + 2x2 ³ 6, –3x1 – x2 ³ –9, x1³ 0, x2 ³ 0. 2. Giải các bài toán thực tế cho ở bài tập 1], 2] và 5] Chương 1.

Các file đính kèm theo tài liệu này:

• tailieu.doc