intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

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 (ĐH Tôn Đức Thắng)

Chia sẻ: Minh Vũ | Ngày: | Loại File: PDF | Số trang:44

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

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" cung cấp cho người học các kiến thức: Bài toán QHTT tổng quát, các dạng của bài toán QHTT, các tính chất của bài QHTT, phương pháp hình học, phương pháp đơn hình. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:
Lưu

Nội dung Text: 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 (ĐH Tôn Đức Thắng)

  1. Chương 1 BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 20/6/2012 MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 1
  2. NỘI DUNG 1. Bài toán QHTT tổng quát 2. Các dạng của bài toán QHTT 3. Các tính chất của bài toán QHTT 4. Phương pháp hình học 5. Phương pháp đơn hình 20/6/2012 MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 2
  3. Bài toán QHTT tổng quát Là 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 ∑ aij x j = bi , i = p + 1,..., m (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
  4. Bài toán QHTT tổng quát trong đó: 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
  5. 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đ. thỏa mãn f ( x ) ≤ f ( x ), ∀x ∈ D * * • PA cnđ x (đ/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
  6. Bài toán QHTT tổng quát Ví 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ó 6 tấ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
  7. 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ời quá 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
  8. Bài toán QHTT tổng quát Gọi x, y là số tấn s.nội thất và s.ngoài trời được sx ra 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
  9. Các dạng của bài toán QHTT 1. 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 ∑ aij x j = bi , i = p + 1,..., m  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
  10. Các dạng của bài toán QHTT 2. 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  j 20/6/2012 MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 10
  11. Các dạng của bài toán QHTT 3. 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  j 20/6/2012 MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 11
  12. Các tính chất của bài toán QHTT Xé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ất kỳ) là một tập lồi. • Nếu một QHTT có ít nhất một PA và hàm mục tiêu bị chặn dưới trong miền ràng buộc (đ/v bài toá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
  13. 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, x2 ) = c1x1 + c2 x2 → min ai 1x1 + ai 2 x2 ≥ bi , i = 1, m ( x1 ≥ 0, x2 ≥ 0) 20/6/2012 MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 13
  14. Phương pháp hình học • Mỗi bpt tuyến tính ai 1x1 + ai 2 x2 ≥ bi xác định một nửa mặt phẳng. { • Tập D = x = (x1, x2 ) :ai 1x1 + ai 2 x2 ≥ bi ,i = 1, m là } giao của m nửa mặt phẳng. 20/6/2012 MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 14
  15. x2 (2) (3) (1) D O x1 7/27/2012 MaMH 501014 Chương 1 Bài toán Quy hoạch tuyến tính 15
  16. Phương pháp hình học D 20/6/2012 MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 16
  17. Phương pháp hình học Phương trình c1x1 + c2 x2 = α khi α thay đổi sẽ xác định trên mặt phẳng các đường thẳng song song với nhau (gọi là đường mức), với giá trị mức α . Bài toán: Trong số các đường mức cắt D, hãy tìm đường mức với giá trị mức α nhỏ nhất. 20/6/2012 MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 17
  18. Phương pháp hình học Phương pháp: • Xác định D. • Vẽ véctơ c = (c1, c2 ) , rồi vẽ đường mức qua gốc tọa độ và vuông với véctơ c = (c1, c2 ). • Đ/v bt min, tịnh tiến đường mức ngược hướng với véctơ c = (c1, c2 ) đến mức thấp nhất mà vẫn còn cắt miền D (đường min). Khi đó, “đường min” tiếp xúc với D và đặt D về cùng một phía. Tiếp điểm tương ứng chính là PATƯ. 20/6/2012 MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 18
  19. Phương pháp hình học • Đối với bài toán max, thì làm ngược lại. •Tịnh tiến mãi mà không tìm được điểm tiếp xúc → bài toán không có PATƯ. 20/6/2012 MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 19
  20. Phương pháp hình học Ví dụ 2 Giải bài toán sau bằng pp hình học f ( x, y ) = 2 x + 3 y → max 2 x + y ≤ 6 (1)  x + 2y ≤ 8 (2)  x − y ≤ 1 (3) x ≤ 2 (4)   x, y ≥ 0. 20/6/2012 MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2