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

Đâ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
Nội dung trích xuất từ tài liệu:
Phương pháp hình học để giải bài toán quy hoạch tuyến tính 2016§3 PHƯƠNG PHÁP HÌNH HỌC ĐỂ GIẢI BÀI TOÁN QHTT1. Phương pháp hình học2. Tập lồi, điểm cực biên, phương án cực biên Phương pháp hình học Phương pháp hình học chỉ áp dụng cho bàitoán QHTT có 2 biến x1, x2 Để giải bài toán ta biễu diễn miền ràngbuộc D trong mặt phẳng x1Ox2 Cho hàm mục tiêu nhận giá trị thay đổi theotham 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ƯLưu ý:Trong mặt phẳng thì đường thẳng: ax1 + bx2 = cchia 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 < cVí dụ 1: Hai phân xưởng của 1 nhà máy cùng sảnxuấ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 40Chi phí (Ngàn) 200 400 Phương pháp hình học Biết nhà máy nhận được đơn đặt hàng 240sản phẩm A và 270 sản phẩm B. Hãy tìm cáchphân phối thời gian cho mỗi phân xưởng thõa mãnsao cho thõa mãn yêu cầu đặt hàng và chi phí ítnhất. Phân xưởng 1 Phân xưởng 2 A 60 10 B 10 40 Chi phí (Ngàn) 200 400 Phương pháp hình họcGiải: Gọi x1, x2 lần lượt là số giờ hoạt động củaphâ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 → minRà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 Phương pháp hình học C24 M12 A6 B 3 6 27 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 = mnhỏ 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 để chiphí 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 Phương pháp hình họcVí 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 0Giải: Vẽ miền ràng buộc của bài toán lên hệ trụcXOY.y =6 C 2y -x+3 B2A x5 – 51 = y E D 1 3 x 2x + y = 2 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 songsong với AE. Giá trị nhỏ nhất của m để (d) cắtmiề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 2song với AE. Giá trị lớn nhất của m để (d) cắtmiền D khi (d) đi qua C(4, 5) khi đó PATƯ là C(4,5) và fmax = 2.4 + 5 = 13 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ếuvới 2 điểm A, B thuộc G bất kì thì đoạn thẳng ABthuộ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ẳngnà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ộccủ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 áncực biên 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 áncự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 QHTTdạng chính tắc là phương án cực biên khi và chikhi hệ vectơ cột {Aj = {aij}}j ứng với thành phầnxj > 0 là độc lập tuyến tính Tập lồi, điểm cực biên, phương án cực biênVí 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ựcbiên. 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ằngkhô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ựcbiên của bài toán Bài tậpBài 1: Giải bài toán QHTT: f(x) = - 2x1 + x2 → min ...