Dụng phương pháp hình học giải bài toán quy hoạch tuyến tính 2 biến

Tóm tắt nội dung tài liệu

1. 2.3. Những phương pháp giải bài toán QHTT 50 2.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ận 2.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. 2.3.1. Phương pháp đồ thị 51 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 đó.
3. a. Xác định miền chấp nhận bằng đồ thị 52 Mỗ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ấp nhậ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ặc trong 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.
4. a. Tiếp 53 70 Nguyên liệu 3 Số 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
5. b. Tìm giá trị của hàm mục tiêu trên miền chấp nhận 54 70 Số 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
6. Tóm tắt về phương pháp đồ thị 55 Vẽ đồ 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.
7. 2.3.2. Phương pháp đơn hình 56 Cơ sở toán học của phương pháp 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 d.
8. Cơ sở toán của phương pháp 57 Tí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 án tố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.
9. 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ên Biến x1 x2 … xr … xm xm+1 … xv … xn Tỷ số cơ H ệ P.án λi bản số c1 c2 ... cr cm cm+1 cv ... cn x1 c1 1 0 ... 0 ... 0 a1(m+1) ... a1v ... a1n b1 x2 c2 0 1 ... 0 ... 0 a2(m+1) ... a2v ... a2n b2 … … ... ... ... ... ... ... ... ... ... ... ... ... 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
10. 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.
11. Thuật toán bài toán Min 60 Bướ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
12. Ví dụ 61 Hà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 = 2 Ràng buộc dấu xj ≥0 (mọi j)
13. Giải 62 Bà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 -7 bả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
14. Lời giải 63 Bảng 2 Biến x1 x2 x3 x4 x5 x6 Hệ λi cơ P.án số 6 1 1 3 1 -7 bả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
15. Thuật toán bài toán Max 64 So 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 < 0 mà aij ≤0 ∀i thì bài toán không có phương án tối ưu. 2. Ở bước 4: Tìm biến đưa vào Biến chọn đưa vào là biến có Δj âm và nhỏ nhất
16. Ví dụ 2: Bài toán ABC 65 Vì trong các ràng buộc có các bất đẳng thức ≤ nên đưa thêm các biến phụ (Slack) vào các ràng buộc như sau : Hàm mục tiêu Max 40F+30B Rà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 3 Ràng buộc dấu F, B, S1, S2, S3 ≥0
17. 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 ố bi cơ 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
18. Ví dụ 2: Bài toán ABC 67 Bảng 2 Biến F B S1 S2 S3 Hệ λi P.án cơ số 40 30 0 0 0 bản S1 0 0 1 0 -2/3 6 0,3 20 S2 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
19. Ví dụ 2: Bài toán ABC 68 Bảng 3 Biến F B S1 S2 S3 λi c ơ Hệ s ố P.án 40 30 0 0 0 bản B 30 0 1 10/3 0 -20/9 20 S2 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
20. b. Thuật toán đơn hình giải bài toán mở rộng 69 Dù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.

Page 2

LAVA

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 đồ...

21-06-2011 3191 390

Download

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2009-2019 TaiLieu.VN. All rights reserved.

popupslide2=3Array ( [0] => Array ( [banner_bg] => [banner_picture] => 742_1662632823.webp [banner_picture2] => [banner_picture3] => [banner_picture4] => [banner_picture5] => [banner_link] => https://kids.hoc247.vn?utm_source=TaiLieuVN&utm_medium=banner&utm_content=bannerlink&utm_campaign=popup&code=trungthu [banner_startdate] => 2022-09-08 00:00:00 [banner_enddate] => 2022-12-31 23:59:59 ) )

Tóm tắt nội dung tài liệu

1. §3 PHƯƠNG PHÁP HÌNH HỌC ĐỂ GIẢI BÀI TOÁN QHTT 1. Phương pháp hình học 2. Tập lồi, điểm cực biên, phương án cực biên
2. Phương pháp hình học Phương pháp hình học chỉ áp dụng cho bài toán QHTT có 2 biến x1, x2 Để giải bài toán ta biễu diễn miền ràng buộc D trong mặt phẳng x1Ox2 Cho hàm mục tiêu nhận giá trị thay đổi theo tham số m: f(x) = c1x1 + c2 x2 = m Xét giao giữa hàm mục tiêu và miền D, tìm giá trị lớn nhất, hoặc nhỏ nhất của m sao cho với giá trị đó hàm mục tiêu vẫn giao với miền D ít nhất là 1 điểm.giá trị đó của m là giá trị tối ưu của Và hàm mục tiêu, và giao điểm của hàm mục tiêu với D chính là PATƯ
3. Lưu ý: Trong mặt phẳng thì đường thẳng: ax1 + bx2 = c chia mặt phẳng làm hai miền M1, M2 với: ∀X(x1, x2) ∈ M1: ax1 + bx2 > c ∀X(x1, x2) ∈ M2: ax1 + bx2 < c Ví dụ 1: Hai phân xưởng của 1 nhà máy cùng sản xuất ra 2 mặt hàng A, B. Năng suất và chi phí trong một giờ của mỗi phân xưởng cho bởi bảng: Phân xưởng 1 Phân xưởng 2 A 60 10 B 10 40 Chi phí (Ngàn) 200 400
4. Phương pháp hình học Biết nhà máy nhận được đơn đặt hàng 240 sản phẩm A và 270 sản phẩm B. Hãy tìm cách phân phối thời gian cho mỗi phân xưởng thõa mãn sao cho thõa mãn yêu cầu đặt hàng và chi phí ít nhất. Phân xưởng 1 Phân xưởng 2 A 60 10 B 10 40 Chi phí (Ngàn) 200 400
5. Phương pháp hình học Giải: Gọi x1, x2 lần lượt là số giờ hoạt động của phân xưởng 1 và phân xưởng 2.Hàm mục tiêu (đv: trăm nghìn): f(x) = 2x1 + 4x2 → min Ràng buộc: 60x1 + 10x 2 240 10x1 + 40x 2 270 x1 0; x 2 0 Miền ràng buộc được biễu diễn như hình vẽ, lấy điểm M(6, 12) ∈ D
6. Phương pháp hình học C 24 M 12 A 6 B 3 6 27
7. Phương pháp hình học Gọi m0 là giá trị để 2x1 + 4x2 = m0 đi qua M. Thì m0 = 2.6 + 4.12= 60. ẽ đường thẳng: V 2x1 + 4x2 = 60 Họ đường thẳng (d): 2x1 + 4x2 = m song song với đường thẳng 2x1 + 4x2 = 60. Ta cần tìm điểm X0 ∈ D sao cho 2x1 + 4x2 = m nhỏ nhất dẫn tới X0 ≡ A, hay X0 = A(3, 6) Vậy phương án tối ưu X0(3, 6), nên để chi phí nhỏ nhất thì phân xưởng 1 hoạt động 3h và phân xưởng 2 hoạt động 6h. Khi đó: fmin = f(3, 6) = 30 (trăm nghìn) = 3 triệu
8. Phương pháp hình học Ví dụ 2: Giải bài toán QHTT: f(x) = 2x + y → min (max) 2x + y 2 -x + 2y 6 5x − y 15 x 0; y 0 Giải: Vẽ miền ràng buộc của bài toán lên hệ trục XOY.
9. y =6 C 2y -x+ 3 B 2A x5 – 51 = y E D 1 3 x 2x + y = 2
10. Phương pháp hình học Miền D của bài toán chính là đa giác ABCDE, hàm mục tiêu là đường thẳng (d): 2x + y = m. Khi m thay đổi ta thấy 2x + y = m luôn song song với AE. Giá trị nhỏ nhất của m để (d) cắt miền D là: m = 2 khi đó một PATƯ là A(0, 2) và fmin =Khi m thay đổi ta thấy 2x + y = m luôn song 2 song với AE. Giá trị lớn nhất của m để (d) cắt miền D khi (d) đi qua C(4, 5) khi đó PATƯ là C(4, 5) và fmax = 2.4 + 5 = 13
11. Tập lồi, điểm cực biên, phương án cực biên Tập lồi: Tập G ⊂ Rn được gọi là tập lồi nếu với 2 điểm A, B thuộc G bất kì thì đoạn thẳng AB thuộc G. Điểm cực biên: Điểm A thuộc G được gọi là điểm cực biên của G nếu không có đoạn thẳng nào trong G nhận A làm điểm giữa Phương án cực biên: D là miền ràng buộc của bài toán QHTT nào đó nếu D là tập lồi và A là điểm cực biên của D thì A được gọi là phương án cực biên
12. Tập lồi, điểm cực biên, phương án cực biên Tính chất 1: Nếu bài toán QHTT có phương án thì sẽ có phương án cực biên và số phương án cực biên là hữu hạn Tính chất 2: Nếu bài toán QHTT có phương án tối ưu thì sẽ có phương án cực biên tối ưu Định lí: (Dấu hiệu để nhận biết 1 phương án là phương án cực biên) X0 là một phương án của bài toán QHTT dạng chính tắc là phương án cực biên khi và chi khi hệ vectơ cột {Aj = {aij}}j ứng với thành phần xj > 0 là độc lập tuyến tính
13. Tập lồi, điểm cực biên, phương án cực biên Ví dụ: Cho bài toán QHTT: f(x) = 2x1 – x2 + x4 → Min x1 + 2x 2 + x4 =2 − x 2 + x 3 + 3x 4 =1 4x 2 − x 4 + x5 = 5 xj 0 j = 1, 5 Tìm PACB bản xuất phát của bài toán và chứng minh rằng PACB cung là phương án cực biên.
14. Tập lồi, điểm cực biên, phương án cực biên Ta có x1, x3, x5 là ẩn cơ sở và x2, x4 không là ẩn cơ sở. Cho ẩn không phải là ẩn cơ sở bằng không ta có phương án: X0 = (2, 0, 1, 0, 5) Hệ vectơ cột Aj ứng với xj > 0 của phương án: 1 �� 0 �� 0 �� A1 = �� 0 �� A 3 = �� 1 �� A 5 = �� 0 �� �� 0 �� �� 0 �� �� 1 �� Vì hệ {A1; A3; A5} là độc lập tuyến tính nên X0 = (2, 0, 1, 0, 5) là một phương án cực biên của bài toán
15. Bài tập Bài 1: Giải bài toán QHTT: f(x) = - 2x1 + x2 → min x1 − x 2 −2 − x1 + 2x 2 −2 x1 0; x 2 0
16. Bài tập Bài 2: Giải bài toán QHTT: f(x) = x - y → min (max) 3x + y 3 x + 2y 4 x− y 1 x1 5; y 5

Page 2

LAVA

Đây là tài liệu cung cấp phương pháp hình học để giải bài toán quan hệ tuyến tính. Giúp bạn đọc nắm rõ phương pháp hình học và ứng dụng các dạng bài tập quy hoạch tuyến tính giải theo phương pháp hình học. Mời các bạn tham khảo

11-10-2013 1403 143

Download

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2009-2019 TaiLieu.VN. All rights reserved.