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

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

0
1.525
lượt xem
542
download

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

Mô tả tài liệu
  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ủ đề:
Lưu

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

  1. LÊ HUỲNH TUYẾT ANH Tháng 3 - 2008
  2. 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
  3. Đ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
  4. 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
  5. 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
  6. 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
  7. ĐỊ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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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ý
  14. 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)
  15.             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
  16.             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
  17. 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
  18. 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
  19. XÁC ĐỊNH ĐẠI LƯỢNG

CÓ THỂ BẠN MUỐN DOWNLOAD

Đồng bộ tài khoản