Tiểu luận Quy hoạch tuyến tính

, Bộ CÔNG THƯƠNG Bộ MÔN QUY HOẠCH TUYÉN TÍNH TIẺU LUẬN ĨHUÍ TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP TP. HÒ CHÍ MINH HO CHI UNH UMVBBITY Cf INDLSTSY KHOA KHOA HỌC cơ BẢN ■d\ Viện Công nghệ Sinh học - Thực phẩm TP. HCM, ngày 25 tháng 4 năm 2009 Lớp : 211301202 GVHD : TS. Võ Văn Tuấn Dũng 1. Nguyễn Trung Nhân 0771637 2. Mai Hạnh Nguyên 0770613 3. Huvnh Thành Trung 0771757 4. Hồ Thị Thanh Hiếu 0771725 5. Dưong Thị Hà Như 0771496 6. Cao Thị Ngọc Tuvền 0770834 7. Mai Nguyễn Thục Hiền 0770770 8. Vũ Kim Hường 0771102 Æ LỜI MỞ ĐẦU 1. Lv do chọn đề tài Trong thực tế ta thường hay gặp các tình huống là phải lựa chọn một trong số những quyết định quan trọng đê đưa ra những phương án hoặc chiến lược tốt nhất trong sản xuất kinh doanh hay trong một trò chơi mà đối thủ là một kẻ thông minh và nguy hiêm...Khi đó ta cần phải lập mô hình toán học quy hoạch tuyến tính đê có được phương án tối ưu cần thiết. Trong đó phương pháp đơn hình được George Bemanrd Dantzig đưa ra năm 1947 cùng lúc với việc khai sinh ra quy hoạch tuyến tính, phương pháp này thực sự có hiệu quả đê giải những bài toán quy hoạch tuyến tính cỡ lớn trong thực tế mà ta thường gặp, như đế vận chuyển hàng hóa đầy đủ nhưng có tong chi phí là nhở nhất - đây chính là bài toán vận tải. Hoặc trong kinh doanh phải lập kế hoạch sản xuất đối với các nguyên liệu và sản phẩm đê thu được tổng lợi nhuận là lớn nhất... Kiến thức sau khi học quy hoạch tuyến tính rất cần thiết, đây là những kiến thức rất quan trọng đê xây dựng một mô hình toán học cho bất kỳ bài toán phức tạp nào trong thực tế, chỉ cần xây dựng các thuật toán đã mô hình hóa ngôn ngữ nhờ việc lập trình trên máy tính ta có thê giải quy hoạch tuyến tính một cách dê dàng nhanh chóng và chính xác. Như vậy việc học quy hoạch tuyến tính rất quan trọng, nó đem lại những hiệu quả kinh tế rất lớn nếu biết lập các mô hình và tính toán đúng quy cách. 2. Đối tượng nghiên cứu và phương pháp nghiên cứu. Quy hoạch tuyến tính là lĩnh vực nghiên cứu các bài toán tối ưu mà hàm mục tiêu là vấn đề được quan tâm nhất và các ràng buộc là các yêu cầu ,điều kiện của kế hoạch đặt ra, đều là hàm và các phương trình, bất phương trình tiiyến tính. Các bước đê nghiên cứu và ứng dụng một bài toán quy hoạch tuyến tính điên hình là: ■ Xác định vấn đề cần giải quyết, thu thập dữ liệu . ịy, 7=1 Với hệ ràng buộc: (3) m ■ Xây dựng các thuật toán đê giải bài toán trên các lập trình máy tính. ■ Tính toán thử và điều chỉnh mô hình nếu cần . ■ Áp dụng đê giải các bài toán thực tế . CHƯƠNG 1: BÀI TOÁN QUY HOẠCH TUYỂN TÍNH A. LÝ THUYẾT 1. ĐỊNH NGHĨA Bài toán quy hoạch tuyến tính (qhtt) tổng quát có dạng: Tìm Xj, j=l,2,...,n sao cho: f=Vớjc. -»min(max) (1) 7=1 bị, i=l,2,...,m (2) >0 <0   tùyỷ (1) được gọi là hàm mục tiêu, nó có thể là cực tiểu (min) hay cực đại (max). (2) được gọi là các ràng buộc chung hay ràng buộc hàm, nó có thế có dạng bất đẳng thức () hoặc có dạng đang thức (=). (3) được gọi là các ràng buộc dấu (của biến), nó có thể không âm (>0), không dương (<0 ) hay tùy ý. Như vậy, bài toán QHTT là bài toán có các biêu thức xác định hàm mục tiêu và các ràng buộc chung đều ở dạng tuyến tính. Véctơ x=(Xị, x2,...,xn) được gọi là phưong án (pa) hay lời giải chấp nhận được của bài toán QHTT nếu nó thoa mãn hệ ràng buộc của bài toán. Phương án x*=(x,\j^,...,j^)rđược gọi là phương án tối ưu (patir) hay lời giải tối ưu, nghiêm tối ưu của bài toán QHTT nếu giá trị hàm mục tiêu tại đó là tốt nhất. ■ Lập mô hình toán học thật chính xác. Æ Tức là: f(x*)=XC,*; f(x) = ỴJCJXJ là giá trị hàm mục tiêu tại phương án 7=1 L-J j=1 x=(xl5x2,...,xn)T bất kỳ. (Dấu ứng với bài toán cực đại). Giải bài toán QHTT tức là tìm phương án tối ưu của nó (nêu có). Hai bài toán QHTT được gọi là tương đương với nhau riếu chúng có chung tập hợp các phương án tối ưu. Mệnh đề: (Quan hệ giữa bài toán cực đại và bài toán cực tiểu) f(x)—» max  íg(x) = ‐f(x) —>• min  0)0 v (2) X G X [xeX (Trong đó: X là tập hợp các phương án) Tức là: nếu đồi dấu hàm mục tiêu và đổi loại hàm mục tiêu thì ta được bài toán tương đương. Vì lí do này mà khi nghiên cứu cách giải bài toán qhtt, người ta chỉ xét bài toán có loại hàm mục tiêu là cực tiểu (hay chỉ xét bài toán có loại hàm mục tiêu là cực đại) 2. PHƯƠNG PHÁP HÌNH HỌC GIẢI BÀI TOÁN QUI HOẠCH TUYÉN TÍNH 2 BIÉN Bài toán có dạng: tìm x=(xi,x2)t sao cho f(x)=cix1+c2x2“^ min (max) Với hệ ràng buộc: ailx1+ai2x2>bi, i=l,2,...,m Chú ý: - Ràng buộc chung có dạng: a-b. - Ràng buộc chung có dạng: a = b thì tương đương với: a>b và -a>-b. - Còn các ràng buộc biến có thê xem là các trường hợp riêng của các ràng buộc chung. Như vậy, hệ ràng buộc của bài toán QHTT có 2 biến luôn luôn có thê giả thiết là có dạng: a¡iXi+ai2X2>b¡; i=l, 2..., m 2.1. Xác định miền phương án Đưa các điểm (xi,x2) lên hệ trục tọa độ vuông góc. Ta xác định được các điểm thỏa mãn phương trình: a¡1x1+ai2x2=b, hình thành nên một đường thẳng chia mặt phang tọa độ thành 2 nửa mặt phăng (mp). Một nửa mp bao gồm các điêm (xi, X-)) thỏa mãn bất phương trình: a¡1 x1 +a¡2 x2 >bi, và nửa kia bao gồm các điêm (X], x2) thỏa mãn bất phương trình: aj|Xi+a¡2X2<bj. 4 n Với hệ ràng buộc: ^a.ịXị = bị, i=l,2,...,m Trong thực hành, đê xác định nửa mp nào ứng với bất phương trình: aj|Xi+ai2 X2>bị. Ta thường lấy một điêm đặc biệt như (0,0); (0,1); (1,0);... thay vào bất phương tình, nếu nó thỏa mãn thì nửa mp chứa điểm đặc biệt đó là nửa mp phải tìm; còn nếu nó không thỏa mãn thì nửa mp phải tìm là nửa mp không chứa điêm đặc biệt đó. Các điêm thỏa mãn hệ ràng buộc của bài toán là các điêm thuộc miền giao của các nửa mp xác định các bất phương trình tương ứng, nó tạo nên một hình đa giác lồi có the bị giới nội hay không bị giới nội; hoặc miền giao là rồng ứng với trường hợp hệ ràng buộc không tương thích. Trường hợp miễn phương án X không rỗng ta thực hiện tiếp bước sau. 2.2. Xác định phưong án tối ưu Một điểm X=(X|,X2)T bất kỳ nằm trong mp tọa độ sẽ cho ta giá trị hàm mục tiêu là: C|X1+C2X2 =f. Tập hợp tất cả các điếm có cùng giá trị hàm mục tiêu là f hình thành nên một đường thẳng vuông góc với véctơ oc với C=(ci,c2)t. Đường thẳng này được gọi là đường thẳng mục tiêu có mức là f. Đặc điểm của các đường thẳng mục tiêu là: nếu tịnh tiến đường thăng mục tiêu theo cùng hưởng vectơ oc thì giá trị hàm mục tiêu sẽ tăng lên. cỏn nếu tịnh tiến theo hưởng ngược với vectơ oc thì giả trị hàm mục tiêu sẽ giảm đi. 3. CÁCH ĐƯA BÀI TOÁN QHTT BÁT KỲ VÈ DẠNG CHÍNH TÁC Bài toán qhtt dạng chỉnh tăc là bài toán qhtt cỏ tất cả các ràng buộc chung đều ở dạng đăng thức và tất cả các biến đều không âm. n  Tức là bài toán có dạng: f=^c -Xj -» min (max) ❖ Trường hợp biến có điều kiện < 0 (hay tùy ý) thì ta thay biến đó bằng “đối” của biến không âm (hay bằng hiệu của biến không âm) Ket luận: Mọi bài toán qhtt đều đưa được về dạng chính tắc và việc giải bài toán qhtt đã cho tương đương với việc giải bài toán qhtt dạng chính tắc tương ứng với nó, theo nghĩa là nếu bài toán dạng chính tắc có patư thì từ đó suy ra được patư của bài toán ban đầu, còn nếu bài toán dạng chính tắc không có phương án tối ưu thì bài toán ban đầu cũng không có patư. Nói cách khác: Bài toán ban đầu có patư khi và chỉ khi bài toán dạng chỉnh tắc tương úvg với nó có patư. Như vậy ta chỉ cần tìm cách giải bài toán qhtt dạng chính tắc. 4. PHƯƠNG PHÁP KHỬ GAUSS-JORDAN. NGHIỆM cơ BẢN CỦA HỆ PHƯƠNG TRÌNH TUYÉN TÍNH 4.1. Phương pháp khử Gauss-Jordan Xét hệ thống gồm m phương trình tuyến tính, n biến: a\\x\ + aì2X2 + •••"*" a\nxn ~ ^1 a 2 ] X , +a 2 2 x 2 + . . . + a ĩ n x n =b 2 +a„2X2+-+am*X*=bn Dạng bảng: b *1 *2 xv xn m Trong đó: ai0 =bj, i=l,2,...,m Phép khử Gauss -Jordan (gọi tắt là phép khử) với phần tử trục (Phần tử giải; Phần tử chủ yếu) là arv^0 (Dòng r được gọi là dòng xoay, cột V được gọi là cột xoav) cho bảng mới tương đương với bảng cũ, theo nghĩa là 2 hệ thống tương ứng với 2 bảng là tương đương với nhau. Quy tắc thực hiện: Các phần tử trên dòng xoay đều chia cho phần tử trục. - Các phần tử còn lại trên cột xoay đều biến thành 0. - Các phần tử khác tính theo qui tắc đường chéo hình chữ nhật rồi chia cho a i j «lv phần tử trục: a„ = ĩí k] = an.  arv  (i= 1,2,... ,m; j=0,1,2,... ,n; #r; #v) Áp dụng giải hệ phương trình tuyến tính: Lần lượt thực hiện các phép khử Gauss- Jordan với các phần tử trục nằm trên các dòng khác nhau, bảng cuối cùng sẽ cho ta lời giải của hệ phương trình (không chọn phần tử trục nằm trên cột b) Lưu ý: - Trong trường hợp có nhiều phần tử có thê được chọn làm phần tử trục, ta nên chọn phần tử sao cho dễ thực hiện phép chia nhất. a10 all a12 alv aln ^20 ^21 &22 &2v &2n 3r0 3-rl ar2 arv <^m ^m0 3-m 1 ^m2 ^mv ^mn a’io a’11 a’i2 0 ã ln a’20 a’21 a’22 0 a’2n ãr()/cirv ^rl/^rv ar2/arv 1 ârr/'^rv & mO a’ml a’m2 0 3 mn - Trên dòng xoay, nếu có phần tử bằng 0 thì cột tương ứng (tức là cột có phần tử =0 này) được giữ nguyên giá trị. - Trên cột xoay, nếu có phần tử bằng 0 thì dòng tương ứng (tức là dòng có phấn tử =0 này) được giữ nguyên giá trị. 4.2. Nghiệm cơ sở của hệ phưong trình tuyến tính Nghiêm cơ sở (nghiệm cơ bản) của 1 hệ phương trình tuyến tính là nghiệm nhận được từ dạng nghiệm tống quát khi có các biến tự do nhận giá trị 0. Biến cơ sở (biến cơ bản) ứng với một phương trình là biến có hệ số là 1 ở phương trình đó và có hệ số là 0 ở các phương tình còn lại (nói cách khác: các hệ số tương ứng với biến cơ sở tạo nên các vectơ đơn vị) Các biến không có đặc điểm trên được gọi là các biến phi cơ sở. Trong dạng nghiệm tổng quát, các biến cơ sở đóng vai trò là các biến phụ thuộc còn các biến phi cơ sở là các biến tự do. Nhận xét: khi thực hiện phép khử với 1 phần tử trục thì biến ở cột xoay sẽ trở thành biến cơ sớ tương ứng với dòng xoay. Ta thấy một nghiệm cơ sở tương ứng với một dạng nghiệm tông quát, mà các dạng nghiệm tổng quát khác nhau là do hệ các biến tự do (hay hệ các biến cơ sở) là khác nhau. Do đó để tìm tất cả nghiệm cơ sở ta đưa vào bảng tính cột XB chứa các biến cơ sở tương ứng với mỗi phương trình và tiến hành thực hiện các phép khử với các phần tử trục được chọn sao cho thu được các hệ biến cơ sở khác nhau. Nghiệm cơ sở tương ứng với mồi bảng sẽ được xác định bằng các cho các biến cơ sở nhận giá trị tương ứng ở cột b, các biến không nằm trong hệ biến cơ sở nhận giá trị 0. - Nghiệm cơ sở suy biến là nghiệm cơ sở tương ứng với nó nhiều hơn 1 hệ biến cơ sở. - Nghiệm cơ sở không suy biến là nghiệm cơ sở có tương ứng với nó đúng 1 hệ biến cơ sở. 5. PHƯƠNG ÁN cực BIÊN Pacb (phương án cơ sở; phương án cơ bản) của bài toán qhtt dạng chính tắc là phương án đồng thời là nghiệm cơ sở của hệ các ràng buộc chung. Nói cách khác, pacb là nghiệm cơ sở của hệ các ràng buộc chung có thỏa điều kiện về dấu của các biến. - Pacb không suy biến là pacb có tương ứng với nó đúng một hệ biến cơ - Pacb suy biến là pacb có tương ứng với nó nhiều hơn một hệ biến cơ sở. Do số nghiệm cơ sở của một hệ phương trình tiiyến tính là hữu hạng nên số pacb là hữu hạng. Số thành phần dương (>()) trong một pacb không vượt quá hạng của hệ ràng buộc chung. Pacb có số thành phần lớn hơn 0 đúng bằng hạng của hệ ràng buộc chung sẽ là pacb không suy biến. Ngược lại, pacb có số thành phần lớn hơn 0 nhở hơn hạng của hệ ràng buộc chung có thê là phương án cực biên suy biến. 6. Cơ SỞ GIẢI TÍCH LỒI Tập họp lồi: Là tập hợp phương án thởa điều kiện: Neu có2 điểm bất kỳ thuộc nó thì cả đoạn thăng nôi 2 điêm cũng thuộc tập hợp đó. Định nghĩa: Điêm cực biên của một tập lồi X là điêm thuộc X, nhưngkhông phải là điêm trong của bất cứ đoạn thắng nào nằm trong X. Đỉnh của 1 tập lồi X là điêm thuộc X và tồn tại 1 siêu phang sao cho X nằm hoàn toàn về 1 phía của nó và siêu phang cắt X chỉ tại điểm đó. Lưu ý: phương trình đoạn thẳng có thê viết dưới dạng: x=x°+az, V (Xe [a,,a2] Đây là đoạn thẳng nằm trên đường thẳng đi qua điểm x° và có vectơ chỉ phương là z. 7. CẮC ĐỊNH LÝ ❖ Định lý 1 (dấu hiệu của pacb): Một phương án của bài toán qhtt dạng chính tắt là pacb khi và chỉ khi hệ véctơ cột tương ứng với các thành phần dương (>0) là độc lập tuyến tính. ❖ Định lý 2 (Điều kiện tồn tại pacb): Bài toán qhtt dạng chính tắc nếu có pa thì sẽ có pacb. ❖ Định lý 3 (ý nghĩa hình học của pacb): một pacb tương ứng với 1 điếm cực biên (đỉnh) của tập phương án. K L ♦♦♦ Định lý 4 (định lý biểu diễn): X X - y^cXịX' + y^/7.z' ;=1 /=1 Trong đó X|,...,XK là các pacb; Zị,...,zL là các vectơ chỉ phương các cạnh vô hạn. Va,. >0, i = l , V / ? , . > 0 , i=l,...,L và ƠỊ+...+ aK=l Æ Tức là pa X được biểu diễn dưới dạng tô hợp lồi của các pacb cộng với tổ hợp không âm của các vectơ chỉ phương các cạnh vô hạn. ❖ Định lý 5 (điều kiện tồn tại pacb): bài toán qhtt có patư khi và chỉ khi nó có phương án và hàm mục tiêu bị chặn dưới đối với bài toán cực tiểu (hay bị chặn trên đối với bài toán cực đại) trên tập phương án. Neu bài toán qhtt dạng chính tắc có patư thì sẽ có 1 pacb là patư. B. BÀI TẬP 1. Lập mô hình toán học các bài toán sau: a. Một xí nghiệp đóng tàu đánh cá cần đóng 2 loại tàu 100 mã lực và 50 mã lực. Trong xí nghiệp có 3 loại thợ chính quyết định sản lượng kế hoạch. Thợ rèn có 2000 công, thợ sắt có 3000 công, thợ mộc có 1500 công. Định mức lao động của mồi loại tàu được cho trong bản: 4 nhất? Điều kiện: < (công/sản phâm) Hỏi xí nghiệp nên đóng tàu mỗi loại bao nhiêu để đạt tổng số mã lực cao Giải Gọi Xị, x2 lần lượt là số tàu 100 mã lực và 50 mã lực cần đóng f(x)=l 00XI+50X2“^ max 150x, +70x2 < 3000 1 20x , + 5 0 X 2 < 2 000 80x,+ 40x2 <1500 Xj > 0,x2 > 0 b. Một xí nghiệp có thê sử dụng tối đa 510 giờ máy cán, 360 giờ máy tiện, 150 giờ máy mài đê chế tạo 3 loại sản phẩm A, B, c. Đê chế tạo một đon vị sản phâm A cần 9 giờ máy cán, 5 giờ máy tiện, 3 giờ máy mài; 1 đơn vị sản phâm B cần 3 giờ máy cán, 4 giờ máy tiện; 1 đơn vị sản phấm c cần 5 giờ máy cán. 3 giờ máy tiện, 2 giờ máy mài. Mồi sản phẩm A trị giá 48 ngàn đồng, mồi sản phẩm B trị giá 16 ngàn đồng, mỗi sản phấm c trị giá 27 ngàn đồng. Vấn đề đặt ra là xí nghiệp cấn chế tạo bao nhiêu đơn vị sản phấm mỗi loại đê tông giá trị sản phấm xí nghiệp thu được là lớn nhất, với điều kiện không dùng quá số giờ hiện có của mỗi loại máy. Giải Ta có bảng tóm tắt như sau: Định mức XLoại tài -^laođộng N. Loại thợ 100 mã lực 50 mã lực Thợ săt (3000) 150 70 Thợ rèn (2000) 120 50 Thợ mộc (1500) 80 40 A (48) B (16) c (27) Thiết bị Loại sp Điều kiện: Gọi Xị, x2, x3 là số đơn vị sản phẩm loại A, B, c f(x)= 48xi+16x2+27x3-> max 9x, + 3X2 + 5X3 <510 5x, +4X2 +3X3 < 360 3x, + 2X3 < 150 Xj >0,j = 1,2,3 c. Một xí nghiệp điện cơ sản xuất quạt điện các loại, cần cắt từ một tấm tôn các cánh quạt điện theo 3 kiêu A, B, c. Có 6 mẫu cắt khác nhau theo bảng sau: Chỉ tiêu sản lượng sản phâm của xí nghiệp phải hoàn thành ít nhất 4000 cánh quạt kiêu A, 5000 cánh quạt kiêu B, 3000 cánh quạt kiểu c. Hỏi xí nghiệp có phương án cắt như thế nào để có phế liệu ít nhất? Giải Gọi Xj là số tấm tôn cắt theo mẫu j f(x)= 2x\ + 2X2 + 2X3 + 2X4 + 3X5 + 3x6 min 2Xị + x2 + x3 > 4000 x2 + 2X4 + x5 > 5000 Điều kiện: < x3 + 2X5 + 3X6 > 3000 Xj > 0, j = 1, 2,3, 4, 5,6 d. Cần vận chuyển 1 loại hàng hóa từ 3 xí nghiệp Al, A2, A3 đến các cửa hàng Bl, B2, B3, B4. lượng hàng có ở mỗi xí nghiệp và chi phí vận chuyên 1 đơn vị hàng được cho ở bảng sau: Máy cán (510) 9 3 5 Máy tiện (360) 5 4 3 Máy mài (150) 3 0 2 Kiêu cánh Mâu căt quạt 1 2 3 4 5 6 A 2 1 1 0 0 0 B 0 1 0 2 1 0 c 0 0 1 0 2 3 Điều kiện: ã Hãy lập kế hoạch vận chuyên sao cho tông chi phí vận chuyên là bé nhất? Giải Gọi Xjj là lượng hàng hóa cần vận chuyển từ xí nghiệp Aj (i = 1, 2, 3) đến cửa hàng Bj(j=l, 2, 3,4). f(x) = 3X|| + 4X|2 + X|4+ x2| + 2x22+ 5x23 + 6x2 4 + x3 1 + 5x3 2 + 8x3 3 + 2x3 4 min xu + x,2 +x]4 < 40 x2\ + x22 + X2Ì + x24 - 30 *3, + *32 +*33 + *34 <30 xu +x2] +x31 = 20 x12 + x22 + *32 = 20 *23 + *33 = X U + X 2 4 + X ì 4 = 1 5 xij - 0, y = 1,2,3,4, ỉ = 1,2,3 e. Công ty may mặc Long Vũ hiện đang lập kế hoạch sản xuất 3 mặt hàng áo Jaket, áo Chemis, áo Bludong. Được biết chi phí giở công sản xuất của từng mặt hàng qua 3 công đoạn cắt, may, hoàn chỉnh như sau: Chemis Bludong Jaket Giờ công bộ phận căt 0.2 0.4 0.3 Giờ công bộ phận may 0.3 0.5 0.4 Giờ công bộ phận hoàn chỉnh 0.1 0.2 0.1 Điều kiện: < m Năng lực tối đa của các bộ phận như sau: Bộ phận cắt: 1250 giờ công Bộ phận may: 1650 giờ công Bộ phận hoàn chỉnh: 540 giờ công Tối thiểu mồi loại phải sản xuất 200 sản phẩm. Hãy tính kế hoạch sản xuất mồi loại sản phẩm bao nhiêu đê đạt tông giá trị sản phẩm lớn nhất và vẫn đảm bảo các điều kiện về năng lực sản phẩm và qui định số lượng sản phẩn tối thiểu. Giải Gọi Xi, x2, x3 là số đơn vị sản phấm Chemis, Bludong, Jaket. f(x)= 2,3xj + 3,6x2+ 2 ,8x3 max 0. 2x + 0.4x, + 0.3.V, < 1250 0. 3Xj + 0.5X2 + 0.4X3 < 1650 o.lx, +0.2X2 + 0.1jc3 < 540 Xj > 200J = 1,2,3 f. Nhà máy sản xuất thiết bị nghe nhìn điện tử Hanel lắp ráp thành phẩm máy thu hình TV, Stereo, loa thùng từ các bộ phận khác nhau. Tên các bộ phận và số lượng còn trong kho của chúng được bộ phận KHO cung cấp trong bản sau: Đơn giá (USD/sp) 2.3 3.6 2.8 Tên bộ phận Kho Sô lượng bộ phận sử dụng khi lăp ráp TV Stereo Loa thùng Khung 450 1 1 0 Đèn hình 250 1 0 0 Loa 800 2 2 1 Nguôn 450 1 1 0 Hệ thông điện 600 2 1 1 4 Điều kiện: Điều kiện: Tìm giải pháp lắp ráp số lượng máy thu hình TV, Stereo, loa thùng từ số bộ phận còn trong kho đê đem lại tông lợi nhuận cao nhất? Giải Gọi X|, x2, x3 là sổ lượng máy thu hình TV, Stereo, loa thùng ■=> f(x) = 75x! + 50x2 + 35x3 -> max Điều kiện: X, +x2 < 450 X, <250 2Xj +2X2 + x3 < 800 X, + x2 < 450 2x, +x2 +x3 < 600 Xj >0 2. Đưa về dạng chuân tắc và chính tắc các bài toán qui hoạch tuyến tính sau: a . f (x ) - 2x / - x2 max X, - 2x2 + x3 3 X, + x2 + x3 = 4 Xj > 0,x3 > 0,x2 tùy ý Giải Dạng chính tắc: thay x2 = x4 - x5 (x4, x5 > 0) và thêm 2 biến phụ x6, x7 > 0. Ta được bài toán: f(x) = 2xr x4+ x5 max X, + x3 - 2x 4 + 2x 5 + x6 = 2 2 jCj - x 3 — 2x 4 + 2x s —x 7 -3 Xj + x3 +x4-x5 -4 x> 0(7 = 1,3,4,5,6,7) Dạng chuẩn tắc: thay x2 = x4 - x5 (x4, x5 > 0). Ta được bài toán: f(x)= 2xi - x4 + x5 max Lợi nhuận đơn vị (S) 75 50 35 4 0 4 x ì + x 3 + x 4 - x 5 < 4 Điều kiện: Điều kiện: < Điều kiện: Điều kiện: < X, + x3 - 2x4 + 2x5 < 2 2x ì -x 3 - 2x4 + 2x5 > 3 X, + x3 + x4 - x5 =4 Xj >0 (7 = 1,3,4,5) X, + x3 — 2x 4 + 2x 5 < 2 -2xì + x3 + 2X4 - 2X5 < -3 -X ị — x3 — x 4 + x 5 < -4 ^ > 0 ( 7 =1,3,4,5) b . f(x) = 3 X ị + X2 m in Xị > 3 xì + x2 < 4 2Xị - x2 = 5 X > 0,x2 > 0 Giải Dạng chính tắc: thêm 2 biến phụ x3, x4 > 0. Ta có: f(x) = 3X| + x2 min — X , = 3 xì + +x4 -- 2x] —x2 =5 X,->0,7 = 1,2,3,4 Dạng chuẩn tắc: f(x) = 3X] + X-) -ỳ min X, > 3 ■ X 2 >-4 Điều kiện: < 2x, - X 2 >5 • 2x, + X 2 > -5 Xj >0,j = l,2,3,4 3. Viết các bài toán quì hoạch tuyến tính sau ở dạng chính tắc: a. f (x) = 4xI + 3x2 - 2X ị min —X, - x2 + 4x3 = 6 2x, + x2 -3x3 3 X, > 0, x2 > 0,x3tùyý Giải Đặt X3=X4-X5 (x4, x5>0), thêm 2 biến phụ x6, x7 >0. Ta có: F(x) = 4xi + 3x2 - 2(x4 - x5) -ỳ min 4 x , + 2 x 2 - x 3 < 1 5 5 x , + 2 x 2 - x3 = 1 0 - 3 x j - 6 x 2 + 2 x 3 > 2 5 X, > 0,x3 > 0, x2 tùy ý Điều kiện: - X , — X2 + 4 x 4 - 4 x 5 = 6   2x! + X2 -3x4 +3x5 + x6 = 8 3 X ị + 4 x 2 - 2 x 4 + 2 x 5 - x 7 = 3 X j > 0, j = 1,2,4,5,6,7 Điều kiện: b. f(x) = 3x/ + x2 min Điều kiện: Giải