Bài giảng Quy hoạch tuyến tính: Chương 1 - ĐH Tôn Đức Thắng

Bài giảng Quy hoạch tuyến tính Chương 1: Bài toán quy hoạch tuyến tính trình bày về bài toán quy hoạch tuyến tính tổng quát, các dạng của bài toán quy hoạch tuyến tính, các tính chất của bài toán quy hoạch tuyến tính, phương pháp hình học và phương pháp đơn hình.
Nội dung trích xuất từ tài liệu:
Bài giảng Quy hoạch tuyến tính: Chương 1 - ĐH Tôn Đức Thắng Chương 1 BÀI TOÁN QUY HOẠCH TUYẾN TÍNH20/6/2012 MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 1 NỘI DUNG1. Bài toán QHTT tổng quát2. Các dạng của bài toán QHTT3. Các tính chất của bài toán QHTT4. Phương pháp hình học5. Phương pháp đơn hình20/6/2012 MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 2 Bài toán QHTT tổng quátLà bài toán có dạng: n f ( x ) = ∑ c j x j → max(min) j =1 n ∑ aij x j ≤ bi , i = 1,..., p (1)  j =1 n  a x = b , i = p + 1,..., m ∑ ij j i (2)  j =1  x j ≥ 0, j = 1,..., q (3)   x j ∈ ℝ, j = q + 1,..., n  (4)20/6/2012 MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 3 Bài toán QHTT tổng quáttrong đó: x j , j = 1,..., n là n biến cần tìm ;các số c j , j = 1,..., n; aij , bi , i = 1,..., m được cho sẵn.biểu thức (1),(2) gọi là các ràng buộc(RB) của bài toán;biểu thức (3), (4) gọi là RB (điều kiện) về dấu của biến. 20/6/2012 MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 4 Bài toán QHTT tổng quát• Gọi D:= {x : thỏa mãn các ràng buộc (1) – (4)} làtập ràng buộc (hay miền chấp nhận được (cnđ))của bt.• Mỗi x ∈ D gọi là phương án (PA) cnđ.• PA cnđ x * thỏa mãn f ( x * ) ≤ f ( x ), ∀x ∈ D (đ/v bài toán min) được gọi là PA tối ưu (PATƯ).• Giá trị f ( x * ) được gọi là giá trị (mục tiêu) tối ưu.20/6/2012 MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 5 Bài toán QHTT tổng quátVí dụ 1 [1] Công ty RM sản xuất hai loại nước sơn:s.nội thất và s.ngoài trời. Nguyên liệu gồm A (có 6tấn) và B (có 8 tấn). Biết rằng:• 1 tấn s.nội thất cần: 2 tấn A , 1 tấn B;• 1 tấn s.ngoài trời cần: 1 tấn A, 2 tấn B.Qua tiếp thị, được biết nhu cầu thị trường là như sau(cho 1 ngày): 20/6/2012 MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 6 Bài toán QHTT tổng quát• Nhu cầu s.nội thất không hơn nhu cầu s. ngoài trờiquá 1 tấn;• Nhu cầu cực đại của s.nội thất là 2 tấn.Vấn đề: Cty cần phải sx mỗi ngày như thế nào đểdoanh thu là lơn nhất?Biết rằng: 1 tấn s.nội thất giá 2000USD; 1 tấn s.ngoài trời giá 3000 USD. 20/6/2012 MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 7 Bài toán QHTT tổng quátGọi x, y là số tấn s.nội thất và s.ngoài trời được sxra trong ngày.Mô hình bài toán: f ( x, y ) = 2 x + 3 y → max 2 x + y ≤ 6  x + 2y ≤ 8   x − y ≤ 1 x ≤ 2   x, y ≥ 0 20/6/2012 MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 8 Các dạng của bài toán QHTT1. Dạng tổng quát n f ( x ) = ∑ c j x j → max(min) j =1 n ∑ aij x j ≤ bi , i = 1,..., p  j =1 n  a x = b , i = p + 1,..., m ∑ ij j i  j =1  x j ≥ 0, j = 1,..., q   x j ∈ ℝ, j = q + 1,..., n 20/6/2012 MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 9 Các dạng của bài toán QHTT2. Dạng chính tắc n f ( x ) = ∑ c j x j → max(min) j =1 n ∑ aij x j = bi , i = 1,..., m  j =1  x ≥ 0, j = 1,..., n  j20/6/2012 MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 10 Các dạng của bài toán QHTT3. Dạng chuẩn tắc n f ( x ) = ∑ c j x j → max(min) j =1 n ∑ aij x j ≤ (≥ ) bi , i = 1,..., m  j =1  x ≥ 0, j = 1,..., n  j20/6/2012 MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 11 Các tính chất của bài toán QHTTXét 2 tính chất cơ bản:• Tập hợp D các PA của bài toán QHTT (dạng bấtkỳ) là một tập lồi.• Nếu một QHTT có ít nhất một PA và hàm mụctiêu bị chặn dưới trong miền ràng buộc (đ/v bàitoán min) thì bài toán chắc chắn có PATƯ.20/6/2012 MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 12 Phương pháp hình học (pp đồ thị)Thường dùng để giải bài toán QHTT có 2 biến.Xét bài toán có dạng:Tìm x1, x2 sao cho: f ( x1 ...