Giải bài toán quy hoạch tuyến tính bằng đồ thị

  -  

Trong các phương pháp giải bài toán qui hoạch tuyến tính, phương pháp đồ thị (Phương pháp hình học) thường được sử dụng. Phương pháp này có ưu điểm là trực quan, dễ hiểu. Tuy nhiên, phương pháp này chỉ dùng để giải những bài toán hai biến quyết định. Về cơ bản phương pháp này gồm hai bước sau: Xác định miền phương án chấp nhận được; Từ đó tìm phương án tối ưu trên miền chất nhận đó. a. Xác định miền chấp nhận bằng đồ...




Bạn đang xem: Giải bài toán quy hoạch tuyến tính bằng đồ thị

*

2.3. Những phương pháp giải bài toán QHTT 502.3.1. Phương pháp đồ thị a. Xác định miền chấp nhận được b. Tìm giá trị của hàm mục tiêu trên miền chấp nhận2.3.2. Phương pháp đơn hình a. Thuật toán đơn hình giải bài toán dạng chuẩn b. Thuật toán đơn hình giải bài toán mở rộng c. Giải bằng máy tính 2.3.1. Phương pháp đồ thị 51Trong các phương pháp giải bài toán qui hoạch tuyến tính,phương pháp đồ thị (Phương pháp hình học) thường được sửdụng. Phương pháp này có ưu điểm là trực quan, dễ hiểu. Tuynhiên, phương pháp này chỉ dùng để giải những bài toán haibiến quyết định.Về cơ bản phương pháp này gồm hai bước sau: Xác định miền phương án chấp nhận được; Từ đó tìm phương án tối ưu trên miền chất nhận đó. a. Xác định miền chấp nhận bằng đồ thị 52Mỗi trục thể hiện một biến quyết định;Mỗi ràng buộc vẽ một đường thẳng để xác định miền chấpnhận: Mỗi đường thẳng chỉ cần vẽ 2 điểm và nối chúng với nhau; Chọn một điểm bất kỳ thoả mãn ràng buộc, miền chứa điểm đó sẽ là miền chấp nhận thỏa mãn ràng buộc đang xét; Giao tất cả các miền chấp nhận của các ràng buộc hình thành vùng chấp nhận của bài toán.Bất cứ điểm nào nằm trên đường biên của vùng chấp nhận hoặctrong vùng chấp nhận được gọi là điểm phương án chấp nhận đượcđối với bài toán qui hoạch. a. Tiếp 53 70 Nguyên liệu 3Số tấn chất bazơ hoà tan 60 50 40 30 Nguyên liệu 2 20 Vùng chấp nhận Nguyên liệu 1 10 0 0 10 20 30 40 50 Số tấn chất phụ gia b. Tìm giá trị của hàm mục tiêu trên miền chấp nhận 54 70Số tấn chất bazơ hoà tan Phương án tối ưu 60 F=25, B=20 50 40 30 20 10 0 0 10 20 30 40 50 Số tấn chất phụ gia Tóm tắt về phương pháp đồ thị 55Vẽ đồ thị các ràng buộc: Mỗi ràng buộc vẽ một đường thẳng và xác định miền chấp nhận được của mỗi ràng buộc;Xác định vùng chấp nhận được: Giao của các miền chấp nhận của tất cả những ràng buộc của bài toán;Vẽ đường mục tiêu Cho hàm mục tiêu bằng một giá trị bất kỳ và vẽ đường mục tiêu. Đối với bài toán cực đại, tịnh tiến đường mục tiêu trong vùng chấp nhận theo hướng làm giá trị của hàm mục tiêu lớn hơn cho đến khi giá trị của hàm mục tiêu lớn nhất (đối với bài toán cực tiểu thì ngược lại);Bất kỳ phương án trên đường mục tiêu với giá trị lớn nhất(đối với bài toán cực đại) là phương án tối ưu. 2.3.2. Phương pháp đơn hình 56 Cơ sở toán học của phương phápa. Thuật toán đơn hình giải bài toán dạng chuẩnb. Thuật toán đơn hình giải bài toán mở rộngc. Giải bằng máy tínhd. Cơ sở toán của phương pháp 57Tính chất 1: Nếu bài toán có phương án tối ưu thì cũng cóphương án cơ bản tối ưu.Tính chất 2: Số phương án cơ bản là hữu hạn.Tính chất 3: Điều kiện cần và đủ để bài toán có phương ántối ưu là hàm mục tiêu của nó bị chặn dưới khi f(x)→min vàbị chặn trên khi f(x)→max trên tập phương án. Thuật toán bài toán Min 58 Bước 1: Chuyển bài toán về dạng chuẩn Bước 2: Lập bảng đơn hình đầu tiênBiến x1 x2 … xr … xm xm+1 … xv … xn Tỷ số cơ H ệ P.án λibản số c1 c2 ... cr cm cm+1 cv ... cnx1 c1 1 0 ... 0 ... 0 a1(m+1) ... a1v ... a1n b1x2 c2 0 1 ... 0 ... 0 a2(m+1) ... a2v ... a2n b2… … ... ... ... ... ... ...

Xem thêm: Quy Hoạch Chất Thải Rắn - Quy Hoạch Điểm Thu Gom, Xử Lý Chất Thải Rắn



Xem thêm: Physical Memory Usage Là Gì, Ý Nghĩa Của Các Thông Số Trong Cpanel Hosting

... ... ... ... ... ...xr cr 0 0 ... 1 ... 0 ar(m+1) ... arv ... arn br… ... ... ... ... ... ... ... ... ... ... ... ... ...xm cm 0 0 ... 0 ... 1 am(m+1) ... amv ... amn bm Δm+1 Δv Δn 0 0 ... 0 ... 0 ... ... f0 m m f 0 = ∑ ci b i & Δ j = ∑ ci a ij − c j i =1 i =1 Thuật toán bài toán Min 59 Bước 3: Kiểm tra tính tối ưu Nếu Δj ≤0 ∀j phương án đang xét là tối ưu và giá trị hàm mục tiêu là f(x)=f0. Nếu ∃Δj > 0 mà aij ≤0 ∀i không có phương án tối ưu.Nếu cả 2 trường hợp trên không xảy ra thì chuyển sang bước 3. Bước 4: Tìm biến đưa vào Nếu Δv=max(Δj) thì xv được đưa vào, cột v là cột chủ yếu. Bước 5: Tìm biến đưa ra Tính λi = bi/aiv ứng với các aiv > 0 Nếu λr=minλi thì xr là biến đưa ra. Hàng r là hàng chủ yếu, phần tử arv là phần tử trục xoay. Thuật toán bài toán Min 60Bước 6: Biến đổi bảng như sau : Thay xr bằng xv và cr bằng cv. Các biến cơ bản khác và hệ số tương ứng để nguyên. Chia hàng chủ yếu (hàng r) cho phần tử trục xoay arv, chúng ta được hàng r mới gọi là hàng chuẩn. Muốn có hàng i mới (i≠r), lấy –aiv nhân với hàng chuẩn rồi cộng vào hàng i cũ. Muốn có hàng cuối mới, lấy -Δv nhân với hàng chuẩn rồi cộng vào hàng cuối cũ. Hàng cuối (gồm f và Δj) cũng có thể tính trực tiếp như ở bước 1 với bảng mới vừa được tạo.Quay lại bước 2 Ví dụ 61Hàm mục tiêu Min(6x1+x2+x3+3x4+x5-7x6)Ràng buộc -x1+x2 - x4 + x6 = 15 -2x1 + x3 - 2x6 = 9 4x1 + 2x4 + x5-3x6 = 2Ràng buộc dấu xj ≥0 (mọi j) Giải 62Bài toán này có dạng chuẩn, vậy có thể lập bảng như sau :Biến x1 x2 x3 x4 x5 x6 Hệ λi cơ P.án số 6 1 1 3 1 -7bản x2 1 -1 1 0 -1 0 1 15 15 x3 1 -2 0 1 0 0 -2 9 x5 1 4 0 0 2 1 -3 2 -5 0 0 -2 0 3 26 Lời giải 63Bảng 2Biến x1 x2 x3 x4 x5 x6 Hệ λi cơ P.án số 6 1 1 3 1 -7bản x6 -7 -1 1 0 -1 0 1 15 x3 1 -4 2 1 -2 0 0 39 x5 1 1 3 0 -1 1 0 47 -2 -3 0 1 0 0 -19 Không có phương án tối ưu Thuật toán bài toán Max 64So với bài toán Min, bài toán Max có các thay đổi sau:1. Ở bước 3: Kiểm tra tính tối ưu + Phương án tối ưu khi Δj≥0 ∀j + Nếu ∃Δj Ví dụ 2: Bài toán ABC 65Vì trong các ràng buộc có các bất đẳng thức ≤ nên đưa thêm cácbiến phụ (Slack) vào các ràng buộc như sau :Hàm mục tiêu Max 40F+30BRàng buộc 0,4F + 0,5B +1S1 = 20 Nguyên liệu 1 0,2B + 1S2 =5 Nguyên liệu 2 0,6F + 0,3B + 1S3 = 21 Nguyên liệu 3Ràng buộc dấu F, B, S1, S2, S3 ≥0 Ví dụ 2: Bài toán ABC 66 Thành lập bảng đơn hình đầu tiên F B S1 S2 S3 Biến λi Hệ s ố bicơ bản 40 30 0 0 0 S1 0 0,4 0,5 1 0 0 20 50 S2 0 0 0,2 0 1 0 5 S3 0 0,3 0 0 1 21 0,6 35 0 -40 -30 0 0 0 0 Ví dụ 2: Bài toán ABC 67 Bảng 2Biến F B S1 S2 S3 Hệ λi P.án cơ số 40 30 0 0 0bảnS1 0 0 1 0 -2/3 6 0,3 20S2 0 0 0,2 0 1 0 5 25 F 40 1 0,5 0 0 10/6 35 70 0 -10 0 0 200/3 1400 Ví dụ 2: Bài toán ABC 68Bảng 3Biến F B S1 S2 S3 λi c ơ Hệ s ố P.án 40 30 0 0 0bản B 30 0 1 10/3 0 -20/9 20S2 0 0 0 -2/3 1 4/9 1 F 40 1 0 -5/3 0 25/9 25 0 0 100/3 0 400/9 1600 b. Thuật toán đơn hình giải bài toán mở rộng 69Dùng biến giả đưa bài toán dạng chính tắc về dạng chuẩn vàgiải bài toán ấy theo như đã trình bày.Nhận xét: Nếu bài toán mở rộng không có phương án tối ưu thì bài toán xuất phát cũng không có phương án tối ưu. Nếu bài toán mở rộng có phương án tối ưu mà các biến giả đều bằng 0 thì bỏ biến giả đi, chúng ta được phương án tối ưu của bài toán xuất phát. Nếu bài toán mở rộng có phương án tối ưu mà trong đó có ít nhất một biến giả dương thì bài toán xuất phát không có phương án tối ưu.