Xem mẫu
- LÊ HUỲNH TUYẾT ANH
Tháng 3 - 2008
- 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
- Đ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Ị
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
- 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
- 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
- ĐỊ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Ị
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
- 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
- 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
- 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
- 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
- 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ý
- 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)
- 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
- 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
- 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
- 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
- XÁC ĐỊNH ĐẠI LƯỢNG
nguon tai.lieu . vn
