Giải Bài Toán Quy Hoạch Tuyến Tính Bằng Phương Pháp Hình Học

Đây là tư liệu cung ứng phương thức hình học để giải bài xích toán quan hệ giới tính con đường tính.

Bạn đang xem: Giải bài toán quy hoạch tuyến tính bằng phương pháp hình học

Giúp độc giả nắm rõ phương thức hình học tập với vận dụng những dạng bài bác tập quy hướng đường tính giải theo cách thức hình học. Mời các bạn tđê mê khảo



§3 PHƯƠNG PHÁPhường 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 rất biên, giải pháp rất biên Phương thơm pháp hình học tập Phương pháp hình học tập chỉ vận dụng mang đến bàitoán thù QHTT gồm 2 trở nên x1, x2 Để giải bài bác toán thù ta biễu diễn miền ràngbuộc D vào khía cạnh phẳng x1Ox2 Cho hàm phương châm thừa nhận cực hiếm biến hóa theotđê mê số m: f(x) = c1x1 + c2 x2 = m Xét giao thân hàm kim chỉ nam và miền D, tra cứu giá trị lớn số 1, hoặc bé dại duy nhất của m sao cho với mức giá trị đó hàm mục tiêu vẫn giao với miền D tối thiểu là 1 trong điểm.giá trị kia của m là giá trị buổi tối ưu của Và hàm phương châm, cùng giao điểm của hàm mục tiêu cùng với D đó là PATƯLưu ý:Trong phương diện phẳng thì đường thẳng: ax1 + bx2 = cchia khía cạnh phẳng làm hai miền M1, M2 với: ∀X(x1, x2) ∈ M1: ax1 + bx2 > c ∀X(x1, x2) ∈ M2: ax1 + bx2 Phương pháp hình học Biết xí nghiệp nhận thấy đơn mua hàng 240thành phầm A cùng 270 thành phầm B. Hãy tìm cáchphân păn năn thời hạn cho mỗi phân xưởng thõa mãnlàm thế nào để cho thõa mãn thử khám phá đặt hàng cùng chi phí ítduy nhất. Phân xưởng 1 Phân xưởng 2 A 60 10 B 10 40 giá thành (Ngàn) 200 400 Pmùi hương pháp hình họcGiải: call x1, x2 lần lượt là số giờ chuyển động củaphân xưởng 1 và phân xưởng 2.Hàm phương châm (đ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ỏng hình vẽ, đem điểm M(6, 12) ∈ D Phương thơm pháp hình học C24 M12 A6 B 3 6 27 Phương pháp hình học tập gọi m0 là cực hiếm để 2x1 + 4x2 = m0 trải qua M.Thì m0 = 2.6 + 4.12= 60.

Xem thêm: Mẫu Đơn Chuyển Sinh Hoạt Đảng Đi Nơi Khác, Đảng Bộ, Mẫu Đơn Xin Chuyển Sinh Hoạt Đảng

ẽ mặt đường thẳng: V 2x1 + 4x2 = 60 Họ con đường trực tiếp (d): 2x1 + 4x2 = m tuy nhiên tuy nhiên cùng với đường thẳng 2x1 + 4x2 = 60. Ta buộc phải tra cứu điểm X0 ∈ D thế nào cho 2x1 + 4x2 = mbé dại duy nhất mang tới X0 ≡ A, tốt X0 = A(3, 6) Vậy cách thực hiện buổi tối ưu X0(3, 6), cần nhằm chigiá tiền nhỏ độc nhất thì phân xưởng 1 vận động 3h vàphân xưởng 2 hoạt động 6h.lúc đó: fmin = f(3, 6) = 30 (trăm nghìn) = 3 triệu Pmùi hương pháp hình họclấy ví dụ như 2: Giải bài bác 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 buộc ràng của bài xích toán thù 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 thơm pháp hình học tập Miền D của bài toán thù chính là đa giác ABCDE, hàm phương châm là mặt đường trực tiếp (d): 2x + y = m. Khi m chuyển đổi ta thấy 2x + y = m luôn songtuy vậy với AE. Giá trị nhỏ tốt nhất của m để (d) cắtmiền D là: m = 2 khi ấy một PATƯ là A(0, 2) vàfmin =lúc m biến hóa ta thấy 2x + y = m luôn luôn tuy nhiên 2tuy vậy với AE. Giá trị lớn nhất của m nhằm (d) cắtmiền D Lúc (d) đi qua C(4, 5) lúc đó PATƯ là C(4,5) và fmax = 2.4 + 5 = 13 Tập lồi, điểm cực biên, phương án rất biên Tập lồi: Tập G ⊂ Rn được Điện thoại tư vấn là tập lồi nếucùng với 2 điểm A, B nằm trong G bất cứ thì đoạn thẳng ABthuộc G. Điểm cực biên: Điểm A ở trong G được gọi làđiểm cực biên của G nếu không tồn tại đoạn thẳngnhư thế nào trong G nhận A làm cho điểm giữa Phương thơm án rất biên: D là miền ràng buộccủa bài xích tân oán QHTT nào kia nếu như D là tập lồi với A làđiểm rất biên của D thì A được điện thoại tư vấn là pmùi hương ánrất biên Tập lồi, điểm cực biên, phương án rất biên Tính chất 1: Nếu bài tân oán QHTT có phươngán thì sẽ sở hữu cách thực hiện cực biên và số phương ánrất biên là hữu hạn Tính hóa học 2: Nếu bài bác toán thù QHTT tất cả phươngán buổi tối ưu thì sẽ sở hữu được cách thực hiện rất biên về tối ưu Định lí: (Dấu hiệu nhằm nhận ra 1 phươngán là phương pháp rất biên) X0 là 1 cách thực hiện của bài xích toán QHTTdạng chính tắc là phương án rất biên khi và chikhi hệ vectơ cột Aj = aijj ứng với thành phầnxj > 0 là tự do đường tính Tập lồi, điểm cực biên, giải pháp rất 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 phiên bản xuất xứ của bài bác toán vàchứng minh rằng PACB cung là cách thực hiện cựcbiên. Tập lồi, điểm rất biên, giải pháp rất biên Ta bao gồm x1, x3, x5 là ẩn đại lý cùng x2, x4 ko làẩn đại lý. Cho ẩn không phải là ẩn cửa hàng bằngko ta bao gồm pmùi hươ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à tự do con đường tính nên X0 = (2, 0, 1, 0, 5) là một trong 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 x1 − x 2 −2 − x1 + 2x 2 −2 x1 0; x 2 0 Bài tậpBài 2: Giải bài toán thù QHTT: f(x) = x - y → min (max) 3x + y 3 x + 2y 4 x− y 1 x1 5; y 5