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

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 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 | QUY HOẠCH TUYẾN TÍNH Tháng 3 - 2008 LÊ HUỲNH TUYẾT ANH 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 buộc a11x1 + a12x2 + . + a1nxn (≤, =, ≥) b1 a21x1 + a22x2 + . + a2nxn (≤, =, ≥) b2 : am1x1 + am2x2 + . + amnxn (≤, =, ≥) bm 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Ị 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 BÀI TOÁN PHÁT BIỂU BÀI TOÁN TỐI ƯU ymax = Max 40 x1 + 50 x2 Đ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Ị Xác định nghiệm tối ưu bài toán trên biên miền xác định Vẽ hệ trục tọa độ x1Ox2 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 ĐỊ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Ị 4 x1 + 3 x2 120 4 x1 + 3 x2 = 120 50 – 40 – 30 – 20 – 10 – 0 – | 10 | 60 | 50 | 20 | 30 | 40 x1 x2 GIẢI BẰNG PHƯƠNG PHÁP ĐỒ THỊ 4 x1 + 3 x2 120 x1 + 2 x2 40 Miền xác định 50 – 40 – 30 – 20 – 10 – 0 – | 10 | 60 | 50 | 20 | 30 | 40 x1 x2 TÍNH GIÁ TRỊ TỐI ƯU Miền xác định OABC 40 – 30 – 20 – 10 – 0 – | 10 | 20 | 30 | 40 x1 x2 24 8 A B C TÍNH GIÁ TRỊ TỐI ƯU x1 + 2x2 = 40 4x1 + 3x2 = 120 4x1 + 8x2 = 160 -4x1 - 3x2 = -120 5x2 = 40 x2 = 8 x1 + 2(8) = 40 x1 = 24 4 x1 + 3 x2 . | QUY HOẠCH TUYẾN TÍNH Tháng 3 - 2008 LÊ HUỲNH TUYẾT ANH 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 buộc a11x1 + a12x2 + . + a1nxn (≤, =, ≥) b1 a21x1 + a22x2 + . + a2nxn (≤, =, ≥) b2 : am1x1 + am2x2 + . + amnxn (≤, =, ≥) bm 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Ị 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 BÀI TOÁN PHÁT BIỂU BÀI TOÁN TỐI ƯU ymax = Max 40 x1 + 50 x2 Điều kiện ràng buộc x1 + 2x2 40 (ràng buộc về .