Bài giảng Quy hoạch tuyến tính

Chia sẻ: PhamDuc Tuan | Ngày: | Loại File: PPT | Số trang:58

Thêm vào BST

Báo xấu

1.612
lượt xem 551
download

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

Vẽ hệ trục tọa độ x1 Ox 2 Xác định miền giới hạn của bài toán trên hình vẽ Vẽ hàm mục tiêu sao cho đi qua trục tọa độ Tịnh tiến đường thẳng này trong miền giới hạn bài toán.Vẽ hệ trục tọa độ x 1 Ox 2 Xác định miền giới hạn của bài toán trên hình vẽ Vẽ hàm mục tiêu sao cho đi qua trục tọa độ Tịnh tiến đường thẳng này trong miền giới hạn bài toán

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Quy hoạch tuyến tính

LÊ HUỲNH TUYẾT ANH Tháng 3 - 2008
QUY HOẠCH TUYẾN TÍNH PHÁT BIỂU BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ymax = max c1x1 + c2x2 + ... + cnxn ymin = min c1x1 + c2x2 + ... + cnxn ộ Ràng bua c x + a x + ... + a x (≤, =, ≥) b Bài toán quy hoạch tuyến tính thuộc loại bài toán tối ưu thực định
ĐIỀU KIỆN ĐỂ BÀI TOÁN TỐI ƯU THUỘC DẠNG BÀI TOÁN QUY HOẠCH TUYẾN TÍNH HÀM MỤC TIÊU là hàm bậc nhất đối với các biến CÁC ĐIỀU KIỆN RÀNG BUỘC phải được thể hiện qua các hàm toán học bậc nhất tuyến tính
PHƯƠNG PHÁP ĐỒ THỊ BÀI TOÁN Thời gian làm việc Đất sét Doanh thu Sản phẩm (giờ/đơn vị) (kg/đơn vị) (1000$/đơn vị) Tô 1 4 40 Bình 2 3 50 Trong một xưởng mỗi ngày, có tối đa 40 giờ làm việc và 120 kg đất sét để sản xuất tô và bình. Với x1 = số tô được sản xuất trong ngày x2 = số bình được sản xuất trong ngày
PHÁT BIỂU BÀI TOÁN TỐI ƯU max 1 2 y = Max 40 x + 50 x Điều kiện ràng buộc x1 + 2x2 ≤ 40 (ràng buộc về giờ làm việc) 4x1 + 3x2 ≤ 120 (ràng buộc về đất sét) x1 , x2 ≥ 0
GIẢI BẰNG PHƯƠNG PHÁP ĐỒ THỊ 1 2 Vẽ hệ trục tọa độ x Ox Xác định miền giới hạn của bài toán trên hình vẽ Vẽ hàm mục tiêu sao cho đi qua trục tọa độ Tịnh tiến đường thẳng này trong miền giới hạn bài toán Xác định nghiệm tối ưu bài toán trên biên miền xác định
ĐỊNH LÝ VỀ ĐIỂM CỰC BIÊN Đối với bài toán quy hoạch tuyến tính thì cực trị nằm trên biên của miền xác định và thường nằm trên đỉnh gọi là các điểm cực biên
GIẢI BẰNG PHƯƠNG PHÁP ĐỒ THỊ x2 50 – 40 – 4 x1 + 3 x2 = 120 30 – 20 – 4 x1 + 3 x2 < 120 10 – 4 x1 + 3 x2 > 120 0– | | | | | | 10 20 30 40 50 60 x1
GIẢI BẰNG PHƯƠNG PHÁP ĐỒ THỊ x2 50 – 40 – 30 – 4 x1 + 3 x2 ≤ 120 20 – Miền xác định 10 – 0– x1 + 2 x2 ≤ 40 | | | | | | 10 20 30 40 50 60 x1
TÍNH GIÁ TRỊ TỐI ƯU x2 40 – 30 – Miền xác định OABC 20 – A 10 – B 0– 8 | | 24 | | x1 10 20 30 C 40
TÍNH GIÁ TRỊ TỐI ƯU x2 x1 + 2x2 = 40 40 – 4x1 + 3x2 = 120 4 x1 + 3 x2 ≤ 120 30 – 4x1 + 8x2 = 160 20 – -4x1 - 3x2 = -120 5x2 = 40 10 – x1 + 2 x2 ≤ 40 x2 = 8 0– 8 | | 24 | | x1 x1 + 2(8) = 40 10 20 30 40 x1 = 24 y = 40(24) + 50(8) = 1,360
TÍNH TOÁN ĐIỂM CỰC BIÊN x1 = 0 x2 x1 = 24 x2 = 20 x2 = 8 40 – y = 1,000 x1 = 30 y = 1,360 x2 = 0 30 – y = 1,200 20 – A 10 – B | | | C| 0– 10 20 30 40 x1
PHƯƠNG PHÁP ĐỒ THỊ BÀI TOÁN A B Điều kiện lưu trữ Dầu thô (tấn) (tấn) (tấn) Xăng 0.2 0.4 1200 DO 0.2 0.2 1200 FO 0.4 0.4 1400 Hiệu quả kinh tế 140 150 (USD/tấn) Một nhà máy lọc dầu xử lý hai loại dầu thô 1 và 2 để sản xuất xăng, DO, FO. Với: x1 = số lượng dầu thô A cần xử lý x2 = số lượng dầu thô B cần xử lý
PHÁT BIỂU BÀI TOÁN TỐI ƯU max 1 2 y = Max 140 x + 150 x Điều kiện ràng buộc 0.2x1+0.4x2 ≤ 1200 (ràng buộc về xăng) (1) 0.4x1+0.2x2 ≤ 1200 (ràng buộc về DO) (2) 0.4x1+0.4x2 ≤ ≤ 1400 (ràng buộc về FO) (3) x1 , x2 ≥ 0 (4)
5. Giaûi baøi toaùn baèng phöông phaùp ñoà thò: A(2,3 B(8,0 D x2 ) ) (2) 1 0.4 C(4,6) x D(8,8 C (4) + 0 2 B .4x ) (1 A (3 = 1 40 ) ) 002x . 1 A C + 0.4 x2 = 120 0 Z=0 B O D x1 Zmin
5. Giaûi baøi toaùn baèng phöông phaùp ñoà thò: A(2,3 B(8,0 D x2 0.4) x1 ) (2) + C(4,6)0.4 x2 D(8,8 C A (0,3000) (4) Mi ền xác định OABCD = 1 40 ) B B (1000,2500) 0 (1 (3 ) ) 0.2x 1 + 0 A C .4x2 = 12 C (2500,1000) 00 Z=0 D (3000,0) B O x1 Zmin
PHÁT BIỂU BÀI TOÁN TỐI ƯU Tại điểm B, hàm mục tiêu đạt giá trị cao nhất. Giá trị lớn nhất tại B(1000,2500) : max y = 1000x140 + 2500x150 = 515000 Kết luận: Ta cần xử lý 1000 tấn dầu thô A và 2500 tấn dầu thô B để đạt lợi nhuận là 515000 USD
PHÁT BIỂU BÀI TOÁN TỐI ƯU Lập phương án phân bổ lượng chất thải hàng
XÁC ĐỊNH ĐẠI LƯỢNG