Giải bài toán bằng phương pháp đơn hình

Trong phần này, nhóm tác giả trình bày cụ thể và chi tiết hơn về FDI tại Việt Nam sau hơn ba thập kỷ dựa trên các tiêu chí bao gồm những sự kiện nổi bật, thực trạng và triển vọng.

TÓM TẮT: Rút gọn thuộc tính là bài toán quan trọng trong bước tiền xử lý dữ liệu của quá trình khai phá dữ liệu và khám phá tri thức. Trong mấy năm gần đây, các nhà nghiên cứu đề xuất các phương pháp rút gọn thuộc tính trực tiếp trên bảng quyết định gốc theo tiếp cận tập thô mờ (Fuzzy Rough Set FRS) nhằm nâng cao độ chính xác mô hình phân lớp. Tuy nhiên, số lượng thuộc tính thu được theo tiếp cận FRS chưa tối ưu do ràng buộc giữa các đối tượng trong bảng quyết định chưa được xem xét đầy đủ. Trong bài báo này, chúng tôi đề xuất phương pháp rút gọn thuộc tính trực tiếp trên bảng quyết định gốc theo tiếp cận tập thô mờ trực cảm (Intuitionistic Fuzzy Rough Set IFRS) dựa trên các đề xuất mới về hàm thành viên và không thành viên. Kết quả thử nghiệm trên các bộ dữ liệu mẫu cho thấy, số lượng thuộc tính của tập rút gọn theo phương pháp đề xuất giảm đáng kể so với các phương pháp FRS và một số phương pháp IFRS khác.

Bài tập toán cao cấp.Tập 3,Phép giải tích nhiều biến số. DSpace/Manakin Repository. ...

Hiện nay, tại chùa Bảo Ninh Sùng Phúc (huyện Chiêm Hóa, Tuyên Quang) còn lưu giữ được tấm bia cổ duy nhất thuộc các tỉnh miền núi phía Bắc nước ta có niên đại từ thời nhà Lý. Nội dung văn bia chép về dòng họ Hà và những đóng góp của dòng họ này đối với vùng đất Vị Long nói riêng và đất nước nói chung ở thế kỷ XI - XII. Trong đó phải kể đến công lao to lớn của nhân vật lịch sử Hà Di Khánh.

Tóm tắt: Lòng trung thành của du khách đối với điểm đến là một yếu tố quan trọng nhằm góp phần thúc đẩy sự phát triển của một điểm đến du lịch. Nghiên cứu này được thực hiện dựa trên cơ sở điều tra khảo sát ý kiến của 231 du khách trong nước và quốc tế đến Hội An. Mục tiêu chính của nghiên cứu nhằm kiểm tra mối quan hệ giữa động cơ đẩy và kéo, sự hài lòng và lòng trung thành của du khách đối với điểm đến Hội An. Kết quả nghiên cứu cho thấy nhân tố đẩy, nhân tố kéo, cùng với sự hài lòng có ảnh hưởng đến lòng trung thành của du khách đối với điểm đến Hội An. Ngoài ra, trong bối cảnh du lịch di sản, du khách có xu hướng trung thành với điểm đến với nhu cầu được tìm hiểu lịch sử, đến thăm những điểm tham quan di sản – văn hóa, gặp gỡ những con người mới và giao lưu với cộng đồng địa phương. Theo đó, tác giả đề xuất một số giải pháp nhằm nâng cao lòng trung thành của du khách, góp phần thu hút du khách quay trở lại điểm đến di sản Hội An, bao gồm định vị và phát triển hình ảnh điểm đến H...

Văn học Việt Nam nửa đầu thế kỉ XX được xem là giai đoạn “giao thời”, với sự đấu tranh giữa thơ Cũ và thơ Mới, giữa truyền thống và cách tân, tồn tại nhiều khuynh hướng, dòng phái khác nhau. Từ góc độ thể loại, không ít người cho đây là thời điểm thơ tự do thắng thế, thơ Đường luật nói chung bị xem là hết mùa, lỗi thời. Song vẫn còn đó một minh chứng hùng hồn cho sự hiện diện của thơ Nôm Đường luật Việt Nam ở nửa đầu thế kỉ XX, đó là Nôm Đường luật Phan Bội Châu. Bài viết trên cơ sở chỉ ra một vài đặc điểm về ngôn ngữ trong thơ Nôm Đường luật Phan Bội Châu thời kỳ ở Huế, từ đó cho thấy những đổi mới, cách tân của Phan Sào Nam trong việc sử dụng thể thơ truyền thống của dân tộc.

Malpera “Amida Kurd” (Swêd) bi Ezîz ê Cewo Mamoyan ra. Yên êzdî û êzdîtî. Li ser rêya hevhatin û yekîtîyê. Gotûbêj. Weşanên “Amida Kurd”, s. 2022. Ev berevoka gotûbêjên malpera “Amida Kurd” bi lêgerîner, nivîskar û rojnamegerê kurd Ezîz ê Cewo ra li ser mijara wan pirsgirêkan e, yên ku li ser rêya hevhatin û yekîtîya civaka netewî-ayînî ya kurdên êzdî dibin asteng. Mamosta Ezîz ê Cewo di nava goveka van gotûbêjan da bingehên wan pêvajoyên dîrokî ravedike, yên ku bûne sedemên bûyerên bobelatî û rojên reş û giran di jîyana êzdîyan da. Wisa jî pêvajoyên îroyîn û rê û rêbazên lêgerandin û berterefkirina wan pirsgirêkan tên govtûgokirin, ên ku hê jî di nava jîyana êzdîyan da rû didin… Ev weşana ji bo govekek a berfireh a xwendevanan hatye armanckirin.

1. hoạch tuyến tính PGS-TS Lê Anh Vũ Chương 2 : PHƯƠNG PHÁP ĐƠN HÌNH Phương pháp đơn hì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 pháp đơn hình giải bài toán QHTT dựa trên hai tính chất quan trọng sau đây của bài toán QHTT: a) Nếu bài toán qui hoạch tuyến tính chính tắc có phương án tối ưu thì cũng có phương án cực biên tối ưu, nghĩa là có ít nhất một đỉnh của miền ràng buộc là lời giải của bài toán. b) Mỗi điểm cực tiểu địa phương của hàm tuyến tính trên miền ràng buộc D (một tập hợp lồi) là một điểm cực tiểu tuyệt đối. Tính chất a) cho phép tìm phương án tối ưu trong số các phương án cực biên của bài toán (số này là hữu hạn). Tính chất b) cho phép khi kiểm tra tối ưu đối với một phương án cực biên (đỉnh) chỉ cần so sánh nó với các đỉnh lân cận (đỉnh kề) là đủ. Vì thế, phương pháp đơn hình bắt đầu từ một phương án cực biên nào đó (tuỳ ý) của bài toán (tức là một đỉnh của miền ràng buộc). Tiếp đó kiểm tra xem phương án hiện có đã phải là phương án tối ưu hay chưa, bằng cách so sánh giá trị hàm mục tiêu tại đỉnh đó với giá trị hàm mục tiêu tại các đỉnh kề với nó. Nếu đúng thì dừng quá trình tính toán. Trái lại, phương pháp sẽ cho cách tìm một phương án cực biên mới tốt hơn (với giá trị hàm mục tiêu nhỏ hơn) mà nó là một đỉnh kề với đỉnh trước đó. Quá trình này tiến hành cho tới khi tìm được phương án tối ưu hoặc phát hiện bài toán đã cho không có lời giải. Như vậy, phương pháp đơn hình tiến hành khảo sát các đỉnh của miền ràng buộc để tìm ra đỉnh tối ưu. Mặc dù số đỉnh của bài toán nói chung rất lớn, nhưng trên thực tế phương pháp này chỉ đòi hỏi kiểm tra một phần tương đối nhỏ các đỉnh. Chính điều đó thể hiện hiệu quả thực tế của phương pháp đơn hì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. 25
2. hoạch tuyến tính PGS-TS Lê Anh Vũ • 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 ∆j. Hệ số cơ sở Biến cơ sở PA CB x1 x2 …… xm xm+1 …… xn iλ 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 ∆m+1 …… ∆n Ở đây f(x0 ) = c1b1 + c2b2 + … + cmbm; ∆j = 0 (j=1,…, m); ∆j = 1 ; 1 m i ij j i c a c m j n = − + ≤ ≤∑ . • Bước 3: Kiểm tra điều kiện tối ưu (Đối với bài toán MIN) a) Nếu mọi 0j∆ ≤ phương án đang xét tối ưu → STOP. b) Nếu tồn tại 0j∆ > mà mọi ij 0a ≤ thì hàm mục tiêu không bị chặn, do đó bài toán đã cho vô nghiệm → STOP. c) Nếu tồn tại 0j∆ > và với mỗi 0j∆ > đều có ít nhất một ij 0a > 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) a) Chọn biến cơ bản mới vx sao cho max{ 0}v j∆ = ∆ > để đưa vào. 26
3. hoạch tuyến tính PGS-TS Lê Anh Vũ b) Chọn biến cơ bản cũ rx sao cho min{ / 0}i r i iv iv b a a λ λ= = > để đưa ra. c) 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ử rva 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 bảng đơn hì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 là xv thay cho biến cơ sở cũ là xr ở dòng r. • Đổi cột hệ số cơ sở: hệ số cv thay cho hệ số cr ở dòng r. • Biến đổi dòng xoay: Dòng mới = dòng cũ / phần tử xoay, Nghĩa là chia mỗi phần tử ở dòng xoay cho phần tử xoay (arv > 0). Kết quả nhận được gọi là dòng chính (số 1 xuất hiện ở vị trí của arv cũ). • Biến đổi các dòng khác theo qui tắc hình chữ nhật: Dòng mới = dòng cũ tương ứng - phần tử của nó trên cột xoay × dòng chính, nghĩa là Cột ≠ cột xoay Cột xoay (cột v) Dòng ≠ dòng xoay : a b a’ = a – b×c Dò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: a) Nếu mọi 0j∆ ≥ phương án đang xét tối ưu → STOP. b) Nếu tồn tại 0j∆ < mà mọi ij 0a ≤ thì hàm mục tiêu không bị chặn, do đó bài toán đã cho vô nghiệm → STOP. c) Nếu tồn tại 0j∆ < mà với mỗi 0j∆ < đều có ít nhất một ij 0a > thì phương án đang xét chưa tối ưu → Làm tiếp bước 4. 27
4. hoạch tuyến tính PGS-TS Lê Anh Vũ • Còn ở bước 4 khi cải tiến PACB đối với bài toán MAX, ta làm như sau: a) Chọn biến cơ bản mới vx sao cho min{ 0}v j∆ = ∆ < để đưa vào. b) Chọn biến cơ bản cũ rx sao cho min{ / 0}i r i iv iv b a a λ λ= = > để đưa ra. c) Tiếp theo chọn dòng thứ r làm dòng xoay, phần tử rva 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 0j∆ ≤ (đối với bài toán MIN) hoặc 0j∆ ≥ (đối với bài toán MAX) đồng thời tồn tại một 0j∆ = ứng với biến phi cơ sở jx 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 0 x . Khi đó giải hệ gồm phương trình 0 ( ) ( )f x f x= và các ràng buộc ta sẽ được tất cả các PATU của bài toán đã cho. Ví dụ 1. Giải bài toán qui hoạch tuyến tính (N) sau đây f = x1 – x2 – 2x4 + 2x5 – 3x6 → min, với cá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 án cực biên ban đầu x0 = (2; 12; 9; 0; 0; 0) với trị mục tiêu f0 = -10. Cơ sở của x0 là {A1, A2, A3}, tức là J0 = {1, 2, 3}. Các biến cơ sở là x1, x2, x3. Các biến phi cơ sở là x4, x5, x6. Các hệ số cơ sở c1= 1, c2 = – 1, c3 = 0. Bảng đơn hình đầu tiên như sau: Hệ số cơ sở Biến cơ sở PACB x1 x2 x3 x4 x5 x6 iλ 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 28
5. hoạch tuyến tính PGS-TS Lê Anh Vũ 0 x3 9 0 0 1 2 4 3 9/2 Bảng 1 -10 0 0 0 2 –1 1 Trong dòng mục tiêu (dòng cuối) còn 4∆ = 2 > 0, 6∆ = 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 án x0 ở bảng nà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 vào là x4 (ứng với 4∆ = 2 lớn nhất). • Biến loại khỏi cơ sở là x1 (ứng với 1λ = min{2, 12, 9/2} = 2 nhỏ nhất). • Phần tử xoay là a14 = 1 (trong ô được tô bóng mờ). Biến đổi bảng 1 theo các qui tắc đã nêu ta nhận được bảng 2 dưới đây. Hệ số cơ sở Biến cơ sở PACB x1 x2 x3 x4 x5 x6 iλ 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 Bảng 2 –14 –2 0 0 0 –3 3 Trong dòng cuối của bảng này còn phần tử ∆6 = 3 > 0 và trên cột chứa nó có hai hệ số dương nên phương án ở bảng nà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 vào x6 (ứng với 6∆ = 3 lớn nhất). • Biến loại khỏi cơ sở là x3 (ứng với tỉ số nhỏ nhất 3λ = min{5, 1} = 1). 29
6. hoạch tuyến tính PGS-TS Lê Anh Vũ • Phần tử xoay là a36 = 5. Biến đổi bảng 2 ta nhận được bảng 3 dưới đây. Hệ số cơ sở Biến cơ sở PACB x1 x2 x3 x4 x5 x6 iλ 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 Bảng 3 –17 –4/5 0 –3/5 0 –21/5 0 Trong bảng này mọi k∆ ≤ 0, nên phương án x* = (0; 8; 0; 3; 0; 1) là PATU với fmin = f(x*) = – 17. Ví dụ 2. Ví dụ sau cho thấy bài toán không có phương á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 giải bài toán trên bằng phương pháp đơn hình, xuất phát từ phương án cực biên x0 = (7, 0, 0, 12, 0, 10) với cơ sở là các véctơ cột đơn vị A1, A4, A6, tức là J0 = {1, 4, 6}. Lập bảng đơn hì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 án x1 x2 x3 x4 x5 x6 iλ 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 Bảng 1 0 0 -1 3 0 -2 0 x1 0 10 1 0 0 1/4 1 0 30
7. hoạch tuyến tính PGS-TS Lê Anh Vũ x3 -3 3 0 -1 1 1/4 0 0 x6 0 1 0 -2 0 -3/4 1 1 Bảng 2 -9 0 2 0 -3/4 -2 0 Trong bảng 2 có 2∆ = 2 > 0 nhưng mọi phần tử ai2 ≤ 0 (i = 1, 2, 3) nên bài toán trên không có PATU (vì hàm mục tiêu của bài toán giảm vô hạn trong miền ràng buộc của nó). Nói cách khác, bài toán QHTT đã cho không có lời giải. Chú ý: Bài toán tìm g → max được thay bằng bài toán tìm f = – g → min. Ví dụ 3. Giải bài toán qui hoạch tuyến tí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 cùng các điều kiện như trên. Xuất phát từ phương án cực biên x0 = (0, 0, 0, 7, 10, 12), ta giải bài toán bằng phương pháp đơn hình (các Bảng 1 - 3). Lời giải thu được là x* = (5, 4, 0, 0, 11, 0) với gmin = –11. Từ đó fmax = 11. Biến cơ sở Hệ số CB Phương án x1 x2 x3 x4 x5 x6 iλ -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 Bả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 Bả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 31
8. hoạch tuyến tính PGS-TS Lê Anh Vũ x1 -3 5 1 0 1/5 1/5 0 3/10 Bảng 3 -11 0 0 -11/5 -1/5 0 -4/5 32
9. hoạch tuyến tính PGS-TS Lê Anh Vũ Ví dụ 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 vào ba biến giả x5, x6, x7 ≥ 0 với hệ số giả M > 0 (đủ lớn) ta được bài toá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 giải bài toán (N) bằng phương pháp đơn hình, xuất phát từ phương án cực biên x0 = (0, 0, 0, 0, 2, 6, 9). Quá trình giải bài toán (N) được ghi tóm tắt trong các bảng sau (Bảng 1 - 4). Biến cơ sở CB Phương á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 Bả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 Bả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 Bả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 Bảng 4 8 0 0 0 -94/5 33
10. hoạch tuyến tính PGS-TS Lê Anh Vũ Ở Bảng 4 ta thấy ∆k ≤ 0 với mọi k = 1, 2, 3, 4, nên phương án cho ở bảng này x = (5, 3, 2, 0, 0, 0, 0) là phương án tối ưu của bài toán (M). Vậy x* = (5, 3, 2, 0) là phương án tối ưu của bài toán ban đầu với fmin = 8. §4. VÍ DỤ GIẢI BÀI TOÁN QHTT DẠNG TỎNG QUÁT (G) Ví dụ 1. Giải bài toán sau bằng phương pháp đơn hình. f = 5x1 + 8x2 → max, x1 + 2x2 ≤ 1, x1 + x2 ≤ 2, x1 ≥ 0, x2 ≥ 0. Trước hết ta chuyển bài toán trên về bài toán tìm min và có dạng (N) bằng cách đưa vào các biến phụ x3, x4 ≥ 0. Ta được bài toán g = – 5x1 – 8x2 → min, x1 + 2x2 + x3 = 1, x1 + x2 + x4 = 2, xj ≥ 0, j = 1, 2, 3, 4. Ta giải bài toán này bằng phương pháp đơn hình, xuất phát từ phương án cực biên x0 = (0, 0, 1, 2). Cơ sở của x0 là {A3, A4}. Quá trình giải như sau (Bảng 1 - 3). Biến cơ sở CB Phương án x1 x2 x3 x4 iλ -5 -8 0 0 x3 0 1 1 2 1 0 ½ x4 0 2 1 1 0 1 2 Bả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 Bảng 2 -4 1 0 -4 0 x1 -5 1 1 2 1 0 x4 0 1 0 -1 -1 1 Bảng 3 -5 0 -2 -5 0 ỞBảng 3 mọi ∆k ≤ 0 nên x*N = (1, 0, 0, 1) là phương án tối ưu của bài toán chính tắc với gmin = – 5. Từ đó suy ra lời giải bài toán ban đầu là x* = (1, 0) với fmax = – gmin= 5. Ví dụ 2. Giải bài toá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. 34
11. hoạch tuyến tính PGS-TS Lê Anh Vũ Trước hết ta thêm vào hai biến phụ x4, x5 ≥ 0 để đưa bài toán về dạng chính tắc (C). Tiếp đó ta đưa vào hai biến giả x6, x7 ≥ 0 để được bài toá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 giải bài toán (N) bằng phương pháp đơn hình với M > 0 (đủ lớn). Quá trình giải ghi ở các bảng sau (bỏ qua hai cột biến giả). Biến cơ sở CB Phương án x1 x2 x3 x4 x5 iλ -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 Bả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 Bả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 Bả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 Bả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 Bảng 5 -8 0 0 0 -1/3 0 ỞBảng 5 mọi ∆k ≤ 0 nên x* N = (3, 1, 0, 0, 6, 0, 0) là phương án tối ưu của bài toán (N). Từ đó suy ra lời giải bài toán ban đầu là x* = (3, 1, 0) với fmin = – 8. 35
12. hoạch tuyến tính PGS-TS Lê Anh Vũ BÀI TẬP 1. Dùng phương pháp đơn hình giải các bài toá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). d) 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). 36
13. hoạch tuyến tính PGS-TS Lê Anh Vũ 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. 37