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

Thêm vào BST

Báo xấu

842
lượt xem 224
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

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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 ?