Ví dụ 1(Bài toán khẩu phần ăn). Chuyên gia dinh dưỡng định thành lập một thực đơn gồm 2 loại thực phẩm chính A và B. Cứ một (trăm gram): Show Thực phẩm A chứa 2 đơn vị chất béo, 1 đơn vị carbohydrate và 4 đơn vị protein. Thực phẩm B chứa 3 đơn vị chất béo, 3 đơn vị carbohydrate và 3 đơn vị protein. Nếu một (trăm gram) thực phẩm A giá 20 (ngàn đồng) và một (trăm gram) thực phẩm B giá 25 (ngàn đồng). Nhà dinh dưỡng muốn thức ăn phảicung cấp ít nhất 18 đơn vị chất béo, 12 đơn vị carbohydrate và 24 đơn vị protein. Bao nhiêu (trăm gram) thực phẩm mỗi loại để có giá nhỏ nhất nhưng vẫn cung cấp đủ dinh dưỡng? Giải. 1 Một số ví dụ dẫn đến bài toán quy hoạch tuyến tính 3 Ví dụ 1 (Bài toán vận tải). Một nhà sản xuất có 2 nhà máy: Một nhà máy ở Vĩnh Phúc và một nhà máy ở Bình Dương. Có 3 kho hàng phân phối sản phẩm đặt ở Hà Nội, TP. HCM và Cần Thơ. Nhà máy ở Vĩnh phúc; Bình Dương, có khả năng cung cấp tối đa 100; 140 tấn mỗi tuần. Lượng cầu của các kho ở Hà Nội, TP. HCM và Cần Thơ lần lượt từ 100; 60 và 80 tấn trở lên. Chi phí vận chuyển (trăm ngàn) mỗi tấn cho như bảng bên dưới. Hỏi cần vận chuyển bao nhiêu tấn hàng hóa từ nhà sản xuất đến các khohàng ở Hà Nội, TP. HCM và ở cần thơ để chi phí nhỏ nhất nhưng vẫn đáp ứng đủ nhu cầu? Giải. 1 Các dạng của bài toán quy hoạch tuyến tính 5 1 Các dạng của bài toán quy hoạch tuyến tính 1.2 Bài toán quy hoạch tuyến tính dạng tổng quát Từ các ví dụ mục 1, bài toán quy hoạch tuyến tính tổng quát được phát biểu như sau: Tìmx 1 ; x 2 ; : : : ; xnsao cho zDc 1 x 1 Cc 2 x 2 CCcnxn!max min/ (1) Với các ràng buộc 8 ˆˆˆ < ˆˆ ˆ: a 11 x 1 C a 12 x 2 C C a1nxn .// b 1 a 21 x 1 C a 22 x 2 C C a2nxn .// b 2 ::: ::: ::: ::: am1x 1 C am2x 2 C C amnxn .// bm (1)Hàm tuyến tính (1) gọi là hàm mục tiêu. Hệ bất phương trình tuyến tính (1) gọi là các ràng buộc. Vế trái của các ràng buộc là các hàm tuyến tính vớix 1 ; x 2 ; : : : ; xnlà các biến số. 1.2 Bài toán quy hoạch tuyến tính dạng chuẩn Chúng ta nói bài toán quy hoạch tuyến tính códạng chuẩn nếu nó có dạng như sau: Tìmx 1 ; x 2 ; : : : ; xnsao cho zDc 1 x 1 Cc 2 x 2 CCcnxn!max; .hay min/ (1) Với các ràng buộc 8 ˆˆ ˆ< ˆˆ ˆ: a 11 x 1 C a 12 x 2 C C a1nxn b 1 a 21 x 1 C a 22 x 2 C C a2nxn b 2 ::: ::: ::: ::: am1x 1 C am2x 2 C C amnxn bm (1)xj 0; j D1; 2; : : : ; n (1) 1 Các dạng của bài toán quy hoạch tuyến tính 6 1.2 Bài toán quy hoạch tuyến tính dạng chính tắc Chúng ta nói bài toán quy hoạch tuyến tính có dạng chính tắcnếu nó có dạng như sau: Tìmx 1 ; x 2 ; : : : ; nsao cho zDc 1 x 1 Cc 2 x 2 CCcnxn!max; .hay min/ (1) Với các ràng buộc 8 ˆˆ ˆ< ˆˆ ˆ: a 11 x 1 C a 12 x 2 C C a1nxn D b 1 a 21 x 1 C a 22 x 2 C C a2nxn D b 2 ::: ::: ::: ::: am1x 1 C am2x 2 C C amnxn D bm (1)xj 0; j D1; 2; : : : ; n (1) Ví dụ 1. Cho biết dạng của các bài toán quy hoạch tuyến tính sau:
3x 1 C 2x 2 3x 3 4 2x 1 C 3x 2 C 2x 3 6 3x 1 x 2 C 2x 3 8 x 1 0; x 2 0; x 3 0 c 1 C2x 2 C3x 3 2x 4 !max Với các ràng buộc 8 < : 2x 1 C 6x 2 C 2x 3 4x 4 D 7 3x 1 C 2x 2 5x 3 C x 4 D 8 6x 1 C 7x 2 C 2x 3 C 5x 4 4 x 1 0; x 2 0; x 3 0; x 4 0 d. zD2x 1 C5x 2 Cx 3 Cx 4 C4x 5 !min Một số sách có định nghĩa khác về dạng chuẩn và dạng chính tắc. Các bạn cần đọc kỹ định nghĩa khi tham khảo các tài liệu khác. 1 Quan hệ dạng chuẩn và chính tắc 8
Giải. 1 Quan hệ dạng chuẩn và chính tắc 1.3 Đổi chiều bất đẳng thức của các ràng buộc Nếu ta nhân hai vế của bất phương trình k 1 x 1 Ck 2 x 2 CCknxnb với 1 ta được bất phương trình k 1 x 1 k 2 x 2 knxnb 1 Quan hệ dạng chuẩn và chính tắc 9 Ví dụ 1. Chuyển bài toán quy hoạch tuyến tính sau sang dạng chuẩn: zD2x 1 C3x 2 C4x 3 !max Với các ràng buộc 8 < : 3x 1 C 2x 2 3x 3 4 2x 1 C 3x 2 C 2x 3 6 3x 1 x 2 C 2x 3 8 x 1 0; x 2 0; x 3 0 Giải. 1.3 Biến không ràng buộc Giả sửxj không có ràng buộc, chúng ta có thể thayxj bằng hai biếnxjC và xj xj DxjCxj trong đóxjC 0 vàxj0:Điều này có nghĩa là một số bất kỳ chính là hiệu của hai số không âm. Với cách này chúng ta có thể chuyển bài toánkhông có ràng buộc về biến thành bài toán có ràng buộc về biến. Ví dụ 1. Chuyển bài toán quy hoạch tuyến tính sau sang dạng chuẩn zD2x 1 C5x 2 !max (1) Với các ràng buộc 3x 1 C 2x 2 6 2x 1 C 9x 2 8 (1)x 1 0 (1) 1 Quan hệ dạng chuẩn và chính tắc 11 Ví dụ 1. Chuyển bài toán quy hoạch tuyến tính sau sang dạng chính tắc zD120x 1 C100x 2 !max Với các ràng buộc 2x 1 C 3x 2 8 5x 1 C 3x 2 15 x 1 0; x 2 0 Giải. Ví dụ 1. Chuyển các bài toán quy hoạch tuyến tính sau sang dạng chính tắc
1 Quan hệ dạng chuẩn và chính tắc 12
3x 1 C 2x 2 3x 3 4 2x 1 C 3x 2 C 2x 3 6 3x 1 x 2 C 2x 3 8 x 1 0; x 2 0; x 3 0 c 1 C2x 2 C3x 3 2x 4 !max Với các ràng buộc 8 < : 2x 1 C 6x 2 C 2x 3 4x 4 D 7 3x 1 C 2x 2 5x 3 C x 4 D 8 6x 1 C 7x 2 C 2x 3 C 5x 4 4 x 1 0; x 2 0; x 3 0; x 4 0
1 Phương án chấp nhận được 14 Đặt AD0BBB@a 11 a 12 a1n a 21 a 22 a2n ::: ::: ::: am1 am2 amn 1CCCA; xD 0BBB@x 1 x 2 ::: xn 1CCCA; bD 0BBB@b 1 b 2 ::: bm 1CCCA; cD 0BBB@c 1 c 2 ::: cn 1CCCAChúng ta có thể viết bài toán quy hoạch trên thành dạng ma trận: Tìm x 2 Rnsao cho zDcTx!max Với các ràng buộc Axb x 0 Ví dụ 1. Viết bài toán quy hoạch tuyến tính sau dưới dạng ma trận. zD120x 1 C100x 2 !max Với các ràng buộc 2x 1 C 3x 2 8 5x 1 C 3x 2 15 x 1 0; x 2 0 Giải. 1 Phương án chấp nhận được Định nghĩa 1 (Phương án chấp nhận được). Véctơ x 2 Rn thỏa tất cả các ràng buộc của bài toán quy hoạch tuyến tính được gọi là phương án chấp nhận được. 1 Phương án chấp nhận được 15 Ví dụ 1. Cho bài toán quy hoạch tuyến tính: zD120x 1 C100x 2 !max Với các ràng buộc 2x 1 C 3x 2 8 5x 1 C 3x 2 15 x 1 0; x 2 0 và các phương án: x 1 D 12; x 2 D 21; x 3 D 13; x 4 D 22Phương án nào là phương án chấp nhận được? Giải. Định nghĩa 1 (Phương án tối ưu). Phương án chấp nhận được làm cho hàm mục tiêu có giá trị lớn nhất (nếu là bài toánmax) hay nhỏ nhất (nếu là bài toánmin) thì được gọi là phương án tối ưu. |
