zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

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

Chia sẻ: Tran Xuan Trung | Ngày: | Loại File: PDF | Số trang:16

Báo xấu

1.578
lượt xem 145
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đâ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

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 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.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 = 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
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
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
Phương pháp hình học C 24 M 12 A 6 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 = 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
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.
y =6 C 2y -x+ 3 B 2A 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 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
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
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
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.
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
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
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

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

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