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

§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 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. Và giá trị đó của m là giá trị tối ưu của 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 = 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 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ên Ví dụ: Cho bài toán QHTT: f(x) = 2x1 – x2 + x4  Min 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. 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: 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 Bài tập Bài 1: Giải bài toán QHTT: f(x) = - 2x1 + x2  min Bài tập Bài 2: Giải bài toán QHTT: f(x) = x - y  min (max)