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.
AMBIENT/
Chủ đề:
Nội dung Text: 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ÍNH
20/6/2012 MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 1
- 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
- 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
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á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
- 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á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
- 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
- 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
- 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
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 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
