YOMEDIA
Chương I BÀI TOÁN QUY HOẠCH TUYẾN TÍNH - Bài 2. BÀI TOÁN QHTT VÀ Ý NGHĨA HÌNH HỌC
Chia sẻ: Nguyễn Văn Quân
| Ngày:
| Loại File: PPT
| Số trang:16
838
lượt xem
223
download
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
1. Dạng tổng quát của bài toán Quy
hoạch tuyến tính.
Bài toán Quy hoạch tuyến tính tổng
quát có dạng sau đây
Tìm giá trị lớn nhất hay nhỏ nhất của hàm
AMBIENT/
Chủ đề:
Nội dung Text: Chương I BÀI TOÁN QUY HOẠCH TUYẾN TÍNH - Bài 2. BÀI TOÁN QHTT VÀ Ý NGHĨA HÌNH HỌC
- Chương I
BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
Bài 2. BÀI TOÁN QHTT VÀ Ý NGHĨA
HÌNH HỌC .
1. Dạng tổng quát của bài toán Quy
hoạch tuyến tính.
Bài toán Quy hoạch tuyến tính tổng
quát có dạng sau đây
Tìm giá trị lớn nhất hay nhỏ nhất của hàm
- f ( x) = c1 x1 + c2 x2 + .. + cn xn
với các ràng buộc:
ai1 x1 + ai2 x2 + .. + ain xn bi ; i I1 (1)
ai1 x1 + ai2 x2 + .. + ain xn bi ; i I 2 (2)
ai1 x1 + ai2 x2 + .. + ain xn = bi ; i I 3 (3)
Σ j J1 ,
x j �0 ;��� x j 0 ; j J2, x j R ; j J 3.
Trong đó I1 , I 2 , I 3 rời nhau và I1 �I 2 �I3 = { 1, 2,.., m}
, J1 , J 2 , J 3 rời nhau và J1 �J 2 �J 3 = { 1, 2,.., n} .
- Ví dụ 1: f ( x) = 4 x1 + x2 − x3 + x4 min
2 x1 + x2 1
− x3 − 4 x4 −2
x1
x1 + x2 + x3 0
x1 + 4 x2 − 5 x3 + 5 x4 = 17
x1 ; x3 0
x2 R
x4 0.
Ở đây là bài toán Quy hoạch tuyến tính
dạng tổng quát, và
I1 = { 1, 2} , I 2 = { 3} , I 3 = { 4} , J1 = { 1,3} , J 2 = { 4} , J 3 = { 2}
- Ví dụ f ( x) = 4 x1 + x2 − x3 + x4 max
2: 2 x1 + x2 + 6 x5 1
− x3 − 4 x4 − 4 x5 −2
x1
x1 + x2 + x3 + 16 x5 2
x1 + 4 x2 − 5 x3 + 5 x4 + x5 = 17
9 x1 + x2 + 5 x3 + 2 x4 11
x1 ; x5 �Σ x2 ; x3
0, R, x4 0.
Ở đây là bài toán Quy hoạch tuyến tính
dạng tổng quát, và
I1 = { 1,3} , I 2 = { 2,5} , I 3 = { 4} , J1 = { 1,5} , J 2 = { 4} , J 3 = { 2,3}
- 2. Một số khái niệm của bài toán Quy
hoạch tuyến tính:
Hàm mục tiêu: Là hàm
n
f ( x) = c j x j =�
c,�
x
j=1
Phương án: Véctơ x = ( x1 , x2 ,.., xn )
thỏa tất cả các ràng buộc gọi là một
phương án.
- Tập phương án:
Tập hợp tất cả các véctơ x thỏa các
ràng buộc gọi là tập phương án.
Phương án tối ưu:
Phương án x làm cho giá trị hàm mục
tiêu đạt giá trị nhỏ nhất (nếu là bài toán
min), hoặc hàm mục tiêu lớn nhất (nếu là
bài toán max) được gọi là phương án tối
ưu của bài toán QHTT.
- 3. Dạng chính tắc của bài toán Quy
hoạch tuyến tính:
Bài toán Quy hoạch tuyến tính có
dạng sau đây, gọi là dạng chính tắc
n
f ( x) = = ��
cjxj c, x max (min)
j =1
n
aij x j = bi i = 1, m
j =1
j = 1, n.
xj 0
f ( x) = ��
c, x max (min)
Ax = b
x0
- Trong đó A = ( aij ) ij==1,1,mn là một ma trận mn
cấp , a a ... a �
� 11 12 1n
� �
a a22 ... a2 n �
� 21
A=
� ... ... �
... ...
� �
a am 2 ... amn �
�m1
x1 b1
�� �� a
�1 j �
�� �� ��
x2 � b2 a
� , b =� � �2 j �
x= A=
j
��
�� �� ...
.. .. ��
�� �� ��
a
�mj �
x bm
�n � ��
Ax = x1 A + x2 A + .. + xn A
1 2 n
- Nhận xét: Mọi bài tóan QHTT đều có
thể đưa về bài tóan QHTT dạng chính tắc.
- 4.Ý nghĩa hình học và phương pháp đồ
thị:
Xét bài toán Quy hoạch tuyến tính
f ( x ) = 4 x1 + x2 max
x1 + x2 5
2 x1 + 3 x2 12
x1 ; x2 0.
Biểu diễn tập phương án trên mặt
phẳng x0y, ta được tứ giác OABC.
- A
B
O
C
O(0,0); A(0,4); B(3,2); C(5,0). Hàm mục tiêu có dạng
của một đường thẳng: f=4x1 + x2. Cho f=0 ta có
đường thẳng đi qua gốc tọa độ.
- Tịnh tiến đường thằng (d) theo một
hướng nào đó sẽ làm cho giá trị hàm mục
tiêu tăng, ngược lại sẽ làm hàm mục tiêu
giảm. Ở bài toán này ta cần làm cho hàm
mục tiêu tăng. Rõ ràng đi theo hướng mũi
tên sẽ làm cho hàm mục tiêu tăng.
f (O) = f (0;0) = 0; f ( A) = f (0; 4) = 4;
f ( B ) = f (3; 2) = 14; f (C ) = f (5;0) = 20
Hàm mục tiêu đạt giá trị max là 20 tại
điểm C(5;0).
- Bài tập:
1. Đưa các bài toán sau đây về
dạng chính tắc= 3x1 − x2 + 3x3 − 5x4 min
f ( x)
x1 − 2 x2 + 3 x3 + x4 7
x1 + 5 x2 + x4 9
2 x1 − 5 x2 + 3 x3 + 2 x4 12
x1 − 2 x2 = 13
0, j = 1, 4
xj
- f ( x) = x1 + 5 x2 − 3x3 max
x1 − 2 x2 + x4 7
x1 + 5 x2 + x3 + x4 = 9
x1 − 2 x2 + x3 6
x1 − 2 x2 =4
x1 0, x2 0, x3 ; x4 ᄀ
- 2. Bằng phương pháp hình học, giải
các bài toán sau
f ( x) = − 4 x1 + 3x2 min
1)
x1 + x2 6
2 x1 + 3x2 6
x1 − x2 2
0, j = 1, 2
xj
2) Một công ty sản xuất hai loại sơn nội
thất và sơn ngoài trời. Nguyên liệu để sản
xuất gồm hai loại A, B với trữ lượng là 6
- sơn nội thất cần 2 tấn nguyên liệu A và 1
tấn nguyên liệu B. Để sản xuất một tấn
sơn ngoài trời cần 1 tấn nguyên liệu A và
2 tấn nguyên liệu B. Qua điều tra thị
trường công ty biết rằng nhu cầu sơn nội
thất không hơn sơn ngoài trời quá 1 tấn,
nhu cầu cực đại của sơn nội thất là 2 tấn.
Giá bán một tấn sơn nội thất là 2000
USD, giá bán một tấn sơn ngoài trời là
3000 USD. Hỏi cần sản xuất mỗi loại sơn
bao nhiêu tấn để có doanh thu lớn nhất ?
Thêm tài liệu vào bộ sưu tập có sẵn:
Báo xấu
LAVA
ERROR:connection to 10.20.1.100:9315 failed (errno=111, msg=Connection refused)
ERROR:connection to 10.20.1.100:9315 failed (errno=111, msg=Connection refused)
Đang xử lý...