Bài giảng Phương pháp định lượng trong quản lý - Chương 2: Quy hoạch tuyến tính - Nguyễn Thống

Nội dung text: Bài giảng Phương pháp định lượng trong quản lý - Chương 2: Quy hoạch tuyến tính - Nguyễn Thống

1. TRƯỜNGPHÖÔNG PHAÙP ĐẠI ÑÒNHHỌC BÁCHLÖÔÏNG KHOA TRONG TP. QUAÛN HCM LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính Khoa KTXD - Bộ môn KTTNN NỘI DUNG MÔN HỌC Chương 1: Giới thiệu PPĐL trong quản lý Chương 2: Quy hoạch tuyến tính. Chương 3: Cơ sở lý thuyết RQĐ Chương 4: Bài toán vận tải. Chương 5: Quản lý kho. Giảng viên: PGS. TS. NGUYỄN THỐNG E-mail: nguyenthong@hcmut.edu.vn or nthong56@yahoo.fr Chương 6: Ra quyết định đ mục tiêu. Web: Chương 7: Lý thuyết sắp hàng. 1 11/26/20132 Tél. (08) 38 691 592 - 098 99 66 719 PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP PHAÙP ÑÒNH ÑÒNH LÖÔÏNG LÖÔÏNG TRONG QUAÛNTRONG LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính QUAÛN LYÙ NỘI DUNG MÔN HỌC (tt) TÀI LIỆU THAM KHẢO Chương 8: Phân tích thành phần chính (PCA). 1. Phương pháp định lượng trong quản lý. Chương 9: Kiểm định Cronbach’s Alpha & NXB Trẻ 1999. Tác giả PGS. Dr. Nguyễn KMO Thống & Dr. Cao Hào Thi. Chương 10: Phương pháp AHP Chương 11: Qui hoạch động 2. Phân tích số liệu và áp dụng vào dự báo. Chương 12: Hoạch định dự án NXB Thanh Niên 2000. Tác giả PGS. Dr. Chương 13: Xích Markov Nguyễn Thống Chương 14: Lý thuyết trò chơi. 3. Phần mềm: SPSS, QSB, Crystal Ball Chương 15: Mô phỏng Monte Carlo. 11/26/20133 11/26/2013 4 PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính NỘI DUNG GIỚI THIỆU Quy hoạch tuyến tính (QHTT) là một kỹ - Giôùi thieäu vaán ñeà. thuật toán học nhằm xác định gía trị của - Phöông phaùp ñoà thò. các biến x1,x2,x3, ,xn (biến quyết định) sao cho : - Phöông phaùp ñôn hình. - Làm cực đại hoặc cực tiểu gía trị của hàm - Quy hoïach nguyeân. mục tiêu (HMT) Z : Z =f(x ,x ,x , ,x ) - Quy hoïach nhò nguyeân. 1 2 3 n - Các biến x1,x2,x3, ,xn thỏa mãn các ràng - Giaûi baøi toaùn quy hoaïch vôùi Solver buộc : (Excel). 11/26/2013 5 11/26/2013 R i = ri(x1,x2,x3, ,xn ) 6 PGS. Dr. Nguyễn Thống 1
2. PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính GIỚI THIỆU CÁC BƯỚC CƠ BẢN BÀI TOÁN QHTT - Trong quy hoạch tuyến tính, hàm mục Định nghĩa biến quyết định tiêu f và các ràng buộc ri là những biểu thức tuyến tính (bậc nhất) đối với các Thiết lập HMT biến quyết định x1,x2,x3, ,xn . - Trong tröôøng hôïp khaùc quy hoïach phi Thiết lập các ràng buộc với tuyeán. biến quyết định. Giải để xác định biến quyết định 11/26/2013 7 11/26/2013 8 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính Ví dụ: Một nhà sản xuất gỗ sản xuất hai loại Trong một tuần, do giới hạn về mặt điều bàn : bàn tròn (x1) và bàn chữ nhật (x2). động nhân sự, xưởng chỉ có thể bố trí: Mỗi bàn tròn cần: - 20 giờ để lắp ghép - 2,5 giờ để lắp ghép - 30 giờ để đánh bóng - 3 giờ để đánh bóng - 1 giờ để vào thùng. - 16 giờ để vào thùng. Một bàn chữ nhật cần : Lợi nhuận cho mỗi bàn tròn là 3000$ và - 1 giờ để lắp ghép 4000$ cho mỗi bàn chữ nhật. - 3 giờ để đánh bóng Tìm phương án sản xuất tối ưu (xác định - 2 giờ để vào thùng. x1, x2) để mang về cho nhà sản xuất lợi nhuận cao nhất. 11/26/2013 9 11/26/2013 10 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính Gọi x1 và x2 là số lượng lần lượt của bàn tròn • Ví dụ: Một nông dân mong muốn đàn cừu và bàn chữ nhật (biến quyết định). của nông trại tiêu thụ các loại sản phẩm Hàm mục tiêu : Max F = 1000( 3x1 + 4x2 ) [1] thức ăn có các loại chất dinh dưỡng là Các ràng buộc : A,B,C với khẩu phần hàng ngày ít nhất, • Ràng buộc về thời gian ghép thô : nhưng phải đảm bảo về mặt dinh dưỡng 2,5x1 + x2 =0 [5] 11 11/26/2013 12 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống 2
3. PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính Trên thị trường có loại sản phẩm y1 và y2. Gọi y1 và y2 là số lượng sản phẩm được mua (là biến quyết định). • Sản phẩm y1 cung cấp : Hàm mục tiêu : Min F = 1000(2y1 + 4y2) 2 đơn vị A và 1 đơn vị B và 1 đơn vị C. Ràng buộc: - Về chất dinh dưỡng loại A : • Sản phẩm y2 cung cấp : 2y1 + y2>=14 1 đơn vị A và 1 đơn vị B và 3 đơn vị C. - Về chất dinh dưỡng loại B : Biết rằng giá đơn vị sản phẩm y1, y2 lần lượt y1 + y2 >=12 là 2000$ và 4000$. - Về chất dinh dưỡng loại C : y1 + 3y2 >=18 Xác định số lượng y1 và y2 để chi phí ít nhất. - Về ý nghĩa vật lý ta phải có : y1,y2 >=0 11/26/2013 13 11/26/2013 14 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính PHƯƠNG PHÁP GIẢI BÀI TOÁN QHTT PHƯƠNG PHÁP ĐỒ THỊ Phương pháp đồ thị (chỉ có 2 (CHỈ CÓ 2 BIẾN QUYẾT ĐỊNH) biến quyết định). Bài toán Max Phương pháp đơn hình (phương pháp tổng quát có số Bài toán Min lượng biến quyết định bất kỳ). 11/26/2013 15 11/26/2013 16 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính BÀI TOÁN MAX Hàm mục tiêu : Max F = 1000( 3x1 + 4x2 ) [1] Giải hệ bất phương trình ràng Các ràng buộc : buộc bằng đồ thị Xác định 2,5x1 + x2 =0 Xác định nghiệm. 11/26/2013 17 11/26/2013 18 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống 3
4. PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính PHƯƠNG PHÁP ĐỒ THỊ BÀI TOÁN MAX Duøng trong tröôøng hôïp chæ coù 2 bieán quyeát ñònh: Vuøng nghieäm coù theå BÀI TOÁN MIN y2 20 [2] F=haèng soá [3] C(4,6) Fmax =36000 10 [1] 8 C 6 D B y O A 1 4 11/26/2013 8 10 16 19 11/26/2013 20 PGS. Dr. Nguyễn Thống [4] PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính Hàm mục tiêu : PHƯƠNG PHÁP ĐỒ THỊ BÀI TOÁN MIN y2 Min F = 1000(2y1 + 4y2) [1] Vuøng nghieäm coù theå Ràng buộc: D 14 [3] [2] F=haèng soá 2y1 + y2>=14 [2] 12 y1 + y2 >=12 [3] C [4] B(9,3) Fmin =44000 6 y1 + 3y2 >=18 [4] [1] B O y1 11/26/2013 21 11/26/2013 7 12 18 A 22 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính Nhaän xeùt: Baøi taäp 1: Moät xöôûng saûn xuaát hai loaïi theùp ñaëc bieät g1 vaø g2. Loaïi g1 caàn 2h ñeå naáu - Nghieäm luoân luoân naèm treân ñöôøng “ranh chaûy, 4h ñeå luyeän, 10h ñeå caét ñònh hình. giôùi” (ABCD). Loaïi g2 caàn 5h ñeå naáu chaûy, 1h ñeå luyeän, - Seõ coù nhieàu nghieäm trong tröôøng hôïp 5h ñeå caét ñònh hình. ñöôøng thaúng bieåu thò HMT gaëp “ña giaùc Lôïi nhuaän mang ñeán bôûi loaïi g1 laø 24$ vaø nghieäm” treân 1 ñoïan thaúng treân bieân. loaïi g2 laø 8$. Khaû naêng cuûa xöôûng coù theå boá trí 40h ñeå naáu chaûy, 20h ñeå luyeän vaø - Ñöôøng thaúng nghieäm bieåu thò giaù trò HMT 60h ñeå caét ñònh hình. laø haèng soá. Xaùc ñònh phöông aùn saûn xuaát ñeå nhaø saûn xuaát coù lôïi nhuaän cao nhaát. Ñaùp soá : g1 = 4 , g2 = 4 vaø Fmax = 128$ 11/26/2013 23 11/26/2013 24 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống 4
5. PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính Baøi taäp 2: Moät nhaø saûn xuaát hai loaïi ñaù xaây döïng : Baøi taäp 3: Moät nhaø laøm vöôøn muoán taïo moät loaïi lôùn (x1) , loaïi beù (x2). Loaïi x1 caàn 2h ñeå hoãn hôïp phaân boùn töø hai loaïi saûn phaåm cô nghieàn, 5h ñeå phaân loaïi, 8h ñeå laøm saïch. Loaïi x2 baûn, sao cho toái thieåu nhaän ñöôïc 15 ñôn vò caàn 6h ñeå nghieàn, 3h ñeå phaân loaïi, 2h ñeå laøm potasse, 20 ñôn vò nitrate vaø 3 ñôn vò saïch. Lôïi nhuaän mang laïi töø loaïi x1 vaø x2 laàn löôït phosphate. Loaïi x1 coù giaù laø 120$ cung caáp laø 40$ vaø 50$. Khaû naêng thieát bò cho pheùp söû duïng ñöôïc 3 ñôn vò potasse, 1 ñôn vò nitrate, 3 ñôn trong moät tuaàn laø : 36h ñeå nghieàn, 30h ñeå phaân vò phosphate. Loaïi x2 coù giaù laø 60$ cung caáp loaïi vaø 40h ñeå laøm saïch. ñöôïc 1 ñôn vò potasse, 5 ñôn vò nitrate, 2 ñôn a. Xaùc ñònh phöông aùn saûn xuaát x1, x2 ñeå nhaø saûn vò phosphate. Xaùc ñònh phöông aùn choïn löïa xuaát coù lôïi nhuaän cao nhaát. ñeå cöïc tieåu hoùa chi phí cuûa nhaø laøm vöôøn. b. Xaùc ñònh lôøi giaûi neáu lôïi nhuaän x2 laø 160$. 11/26/2013 25 Ñaùp11/26/2013 soá : x1 = 2 , x2 = 9 vaø Fmin = 780$ 26 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống Ñaùp soá : x1 = 3 , x2 = 5 vaø Fmax = 370$ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính Baøi taäp 5: Tìm lôøi giaûi toái öu cho baøi toaùn sau: Baøi taäp 4: Moät ngheä só raát quan taâm ñeán söùc khoeû Haøm muïc tieâu : Max F = 20x1+10x2 mong muoán moãi ngaøy coù ñöôïc toái thieåu 36 ñôn vò Caùc raøng buoäc : 4x1+3x2 =0 vaø 8 ñôn vò vitamin D. Loaïi thuoác thöù 2 giaù laø Ñaùp soá : x1 = 9, x2 = 4 vaø F = 220 4$US coù theå cung caáp 3 ñôn vò vitamin A, 2 ñôn vò max Baøi taäp 6: Haøm muïc tieâu : Min F = 30x1+50x2 vitamin C vaø 2 ñôn vò vitamin D. Xaùc ñònh löôïng Caùc raøng buoäc : 6x1+2x2 >=3 thuoác söû duïng ñeå chi phí cuûa ngheä só naøy laø beù 3x1+2x2 >=24 nhaát. 5x1+10x2 >=60 Ñaùp soá : y1 = 6 , y2 = 8 vaø Fmin = 50 $US x1, x2 >=0 11/26/2013 27 Ñaùp11/26/2013 soá : x1= 6 , x2=3 vaø Fmin = 330 28 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính NGUYÊN TẮC PHƯƠNG PHÁP Thử và so sánh kết quả của tất cả các điểm nằm trên “ranh ĐƠN HÌNH giới” của VÙNG ĐA GIÁC (Phương pháp tổng quát) NGHIỆM. 11/26/2013 29 11/26/2013 30 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống 5
6. PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính PHÖÔNG PHAÙP ÑÔN HÌNH Phöông phaùp ñôn hình cho pheùp xaùc ñònh lôøi giaûi PHƯƠNG PHÁP cô baûn cuûa moät heä thoáng phöông trình vaø kieåm ĐƠN HÌNH tra xem lôøi giaûi ñoù coù toái öu hay chöa. Ñeå coù lôøi giaûi cô baûn, phaûi gaùn cho (n-m) bieán giaù trò baèng khoâng vaø giaûi heä m phöông trình vaø m Bài toán Max HMT aån soá coøn laïi. Phöông phaùp naày cho pheùp chuyeån töø lôøi giaûi cô baûn naøy sang moät lôøi giaûi cô baûn khaùc, toát hôn lôøi giaûi tröôùc, cho ñeán khi ñaït ñeán lôøi giaûi toái öu. 11/26/2013 31 11/26/2013 32 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính PHÖÔNG PHAÙP ÑÔN HÌNH NGUYÊN LÝ ƯU TIÊN CHỌN Nhöõng bieán coù giaù trò laø 0 ôû moãi TỔ HỢP NGHIỆM böôùc laëp thì khoâng keå trong lôøi giaûi cô baûn. Nhöõng bieán khoâng F a1X1 a2X2 anXn Max ñöôïc laáy giaù trò 0 seõ ñöôïc xem ôû trong lôøi giaûi cô baûn cuûa baøi toaùn. Sẽ ưu tiên đưa nghiệm Xi nào có hệ số ai LỚN ! 11/26/2013 33 11/26/2013 34 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính Ví duï: Söû duïng phöông phaùp ñôn hình ñeå 1. Laäp baûng ban ñaàu cho phöông phaùp ñôn hình. giaûi. a.Theâm caùc bieán buø s1,s2,s3>0 ñeå bieán ñoåi caùc baát phöông trình treân thaønh phöông trình : Haøm muïc tieâu : Max F = 5x1 + 3x2 [1] 6x1 + 2x2 + s1 = 36 [2] Vôùi caùc raøng buoäc : 5x1 + 5x2 + s2 = 40 [3] 6x1 + 2x2 =0 5 5 0 1 0 * 1 40 2 4 0 0 1 s2 28 (Ghi chuù: trong tröôøng hôïp naøy duøng p/p ñoà thò) 11/26/2013 35 11/26/2013 s 36 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống 3 6
7. PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính c. Baûng ban ñaàu cuûa phöông phaùp ñôn hình : HÀM MỤC TIÊU x1 x2 s1 s2 s3 Haèng soá MỘT CÁCH “HÌNH THỨC” SAU KHI BỔ 6 2 1 0 0 36 SUNG CÁC BIẾN “BÙ” THÌ HMT SẼ 5 5 0 1 0 40 BIẾN THÀNH: 2 4 0 0 1 28 Max F = 5x1 + 3x2 +0.s1+0.s2+0.s3 -5 -3 0 0 0 0 Heä soá HMT ñoåi daáu – Haøng tham khaûo Nghieäm: x1=0, x2=0, s1=36,s2=40, s3=28, HMT=0 !!! Treân 1 coät, neáu heä soá khoâng coù daïng (0 ,1, 0, ) 11/26/2013 37 Bieán11/26/2013 töông öùng =0 38 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính Choïn giaù trò “xoay” vaø thay ñoåi heä cô baûn. Nguyeân taéc thay ñoåi nhö sau : Ñeå ñaït ñeán giaù trò toái öu cuûa haøm muïc tieâu, a. Giaù trò tham khaûo aâm coù giaù trò tuyeät ñoái lôùn chuùng ta xem xeùt moät lôøi giaûi cô baûn môùi. nhaát xaùc ñònh bieán môùi ñöa vaøo lôøi giaûi cô baûn. Ñeå ñaït ñöôïc vaán ñeà ñoù, chuùng ta phaûi ñöa Trong tröôøng hôïp naøy, ñoù laø giaù trò -5 vaø naèm ôû vaøo moät bieán môùi trong lôøi giaûi cô baûn vaø coät ñaàu tieân (x1), do ñoù x1 seõ ñöôïc ñöa vaøo lôøi ñoàng thôøi phaûi loaïi boû moät trong nhöõng giaûi cô baûn. Coät chöùa x1 seõ trôû thaønh coät xoay vaø bieán trong lôøi giaûi cuõ. ñaùnh daáu muõi teân . Ta goïi söï thay ñoåi heä cô baûn laø quaù trình b. Haøng xoay seõ ñöôïc xaùc ñònh bôûi tyû soá nhoû nhaát choïn bieán môùi ñeå ñöa vaøo vaø ñoàng thôøi giöõa coät haèng soá vaø caùc phaàn töû cuûa coät xoay choïn bieán cuõ ñeå loaïi ra. töông öùng. Trong tröôøng hôïp naøy laø haøng thöù nhaát bôûi vì (36/6<40/5<28/2). 11/26/2013 39 11/26/2013 40 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính KHÖÛ x1 x2 s1 s2 s3 Haèng soá • Ñaây laø böôùc cho pheùp giaûi heä m phöông trình vaø 1 1/3 1/6 0 0 36/6 coù m aån soá coøn laïi trong lôøi giaûi cô baûn. Bôûi vì chæ 5 5 0 1 0 40 coù duy nhaát moät bieán môùi ñöa vaøo lôøi giaûi cô baûn vaø böôùc tính luoân luoân taïo ra moät ma traän ñôn 2 4 0 0 1 28 vò, trong böôùc naøy ta seõ bieán ñoåi sao cho giaù trò -5 -3 0 0 0 0 xoay baèng 1 (chöùa taát caû caùc soá haïng cuûa haøng x1 x2 s1 s2 s3 Haèng soá naøy cho giaù trò xoay) vaø taïo ra caùc giaù trò baèng 0 cho caùc soá haïng khaùc trong phaàn coät xoay coøn 1 1/3 1/6 0 0 6 laïi, baèng caùch thay noù bôûi moät toå hôïp tuyeán tính 0 10/3 -5/6 1 0 10 cuûa haøng ñang xeùt vaø haøng xoay (gioáng nhö 0 10/3 -1/3 0 1 16 trong phöông phaùp khöû Gauss) . 0 -4/3 5/6 0 0 30 11/26/2013 41 Nghieäm: x1=6, 42x2=0, s1=0,s2=10, s3=16,HMT=30 PGS. Dr. Nguyễn Thống 7
8. PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính TOÁI ÖU HOÙA x1 x2 s1 s2 s3 Haèng soá HMT seõ cöïc ñaïi khi ta khoâng coøn giaù trò 1 1/3 1/6 0 0 6 tham khaûo naøo aâm ôû haøng cuoái. 0 1 -0.25 3/10 0 3 Chuùng ta tieáp tuïc söï thay ñoåi lôøi giaûi cô baûn 0 10/3 -0.33 0 1 16 vaø söï khöû vôùi nguyeân taéc nhö trình baøy ôû 0 -1.33 5/6 0 0 30 böôùc treân. x1 x2 s1 s2 s3 Haèng soá Coät x2 seõ ñöôïc choïn laø coät xoay vaø haøng 2 seõ 1 0 1/4 -0.1 0 5 ñöôïc choïn laø haøng xoay, do ñoù 10/3 seõ laø giaù trò xoay, khi ñoù ôû böôùc naøy thì s1 vaø s2 0 1 -0.25 3/10 0 3 seõ bò loaïi ra khoûi lôøi giaûi cô baûn. 0 0 1/2 -1 1 6 0 0 1/2 2/5 0 34 11/26/2013 43 Nghieäm: x1=5, 44x2=3, s1=0,s2=0, s3=6,HMT=34 PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính Bài tập: Dùng phương pháp đơn hình giải: MỘT SỐ LƯU Ý Hàm mục tiêu : Max F = 1000( 3x1 + 4x2 ) [1] Biến bù s=0 Bất phương trình ràng Các ràng buộc : buộc đã đạt tối đa biến thành • Ràng buộc về thời gian ghép thô : phương trình. 2,5x1 + x2 0 Bất phương trình • Ràng buộc về thời gian đánh bóng : ràng buộc tương ứng chưa đạt tối đa 3x1 + 3x2 =0 [5] đạt11/26/2013 tối đa, ràng buộc [4] còn 6 đơn vị45. 11/26/2013 46 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính PHÖÔNG PHAÙP ÑÔN HÌNH Söû duïng phöông phaùp ñôn hình ñeå giaûi baøi BAØI TOAÙN CÖÏC TIEÅU toaùn sau : Khi chuùng ta söû duïng phöông phaùp ñôn hình ñeå Haøm muïc tieâu : Min F = 2x1 + 4x2 tìm moät giaù trò cöïc tieåu, nhöõng bieán buø theâm vôùi caùc raøng buoäc : vaøo mang tröôùc noù daáu tröø seõ ñöa ñeán moät 2x1 + x2 >= 14 daïng baøi toaùn ñaëc bieät. x1 + x2 >= 12 Trong thöïc teá, ngöôøi ta coù theå giaûi baøi toaùn cöïc tieåu baèng caùch thay noù baèng baøi toaùn ñoái x1 + 3x2 >= 18 ngaãu ñeå trôû thaønh baøi toaùn cöïc ñaïi. vôùi x1, x2 >=0 11/26/2013 47 11/26/2013 48 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống 8
9. PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính Baûng ban ñaàu cho phöông phaùp ñôn hình (coù moät ít TöØ ma traän naøy ta thaáy raèng neáu x1=x2=0, lôøi giaûi thay ñoåi so vôùi baøi toaùn tröôùc). cô baûn khoâng theå chaáp nhaän vì s1=-14, s2=-12, a. Phöông trình vôùi caùc bieán buø : s3=-18 (giaù trò aâm). Ñeå giaûi quyeát vaán ñeà naøy ta 2x1 + x2 - s1 = 14 seõ ñöa vaøo caùc bieán nhaân taïo Ai. x1 + x2 - s2 = 12 Bieán nhaân taïo (Ai) laø moät bieán aûo ñöôïc ñöa vaøo moät caùch ñaëc bieät ñeå taïo neân moät lôøi giaûi cô baûn x1 + 3x2 - s3 = 18 x1 chaáp nhaän ñöôïc, do ñoù noù khoâng coù yù nghóa veà maët kinh teá. Ta ñöa vaøo moãi baát phöông trình 2 1 1 0 0 x2 14 ban ñaàu moät bieán nhaân taïo : s 1 1 0 1 0 * 1 12 1 3 0 0 1 s2 18 11/26/2013 49 11/26/2013 50 PGS. Dr. Nguyễn Thống s3 PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính x1 x 2 QUY HOAÏCH NGUYEÂN s1 2 1 1 0 0 1 0 0 14 s2 • Ñaây laø moät tröôøng hôïp ñaëc bieät cuûa 1 1 0 1 0 0 1 0 * 12 s3 1 3 0 0 1 0 0 1 18 baøi toaùn quy hoaïch tuyeán tính, ôû ñoù ta A1 x1 x2 s1 s2 s3 A1 A2 A3 Haèng soá A chæ chaáp nhaän bieán quyeát ñònh coù giaù 2 A3 trò nguyeân. 2 1 -1 0 0 1 0 0 14 Choïn soá löôïng thieát bò saûn xuaát, soá 1 1 0 -1 0 0 1 0 12 löôïng saûn phaåm, 1 3 0 0 -1 0 0 1 18 -2 -3 0 0 0 -M -M -M 0 11/26/2013 51 11/26/2013 52 PGS. Dr. Nguyễn ThốngM>0 ñuû lôùn ñeå Ai bò loaò ra khoûi p/t HMT PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính QUY HOAÏCH NGUYEÂN Ví duï: Moät Xí nghieäp cheá taïo hai loaïi radio A vaø B . Moät phöông phaùp giaûi cô baûn cho quy hoaïch - Lôïi nhuaän thu ñöôïc töø A vaø B laàn löôït laø 100 $US nguyeân thöôøng goïi laø “cutting plane“. vaø 200 $US. Ñaàu tieân xaùc ñònh bieán quyeát ñònh baèng phöông - Moät ngöôøi thôï caàn 1 h vaø 4 h ñeå laép raùp A vaø B. phaùp quy hoaïch tuyeán tính. Moãi ngaøy ngöôøi thôï chæ coù theå laøm vieäc 12 h. Tröôøng hôïp bieán keát quaû khoâng nguyeân thieát - Ngoaøi ra theo keát quaû cuûa phoøng nghieân cöùu tieáp laäp raøng buoäc môùi töø baûn tính QHTT. thò thì khaû naêng tieâu thuï cuûa thò tröôøng toái ña laø 4 saûn phaåm/ngaøy, khoâng phaân bieät loaïi radio Giaûi heä p/t QHTT vôùi raøng buoäc môùi. naøo. Quy trình seõ keát thuùc khi chuùng ta ñaõ nhaän caùc bieán quyeát ñònh hoaøn toaøn nguyeân. 11/26/2013 53 11/26/2013 54 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống 9
10. PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính - Veà khaû naêng coâng ngheä, xöôûng caàn 3 h vaø 1 Goïi x1 = Soá löôïng radio A cheá taïo (nguyeân). h ñeå cheá taïo caùc linh kieän cho A vaø B. x2 = Soá löôïng radio B cheá taïo (nguyeân). s1,s2,s3 : caùc bieán buø - Xöôûng naøy hoaït ñoäng toái ña 10 h/ngaøy. Haøm muïc tieâu : Xaùc ñònh chieán löôïc saûn xuaát A vaø B ñeå cöïc Max F = 100 (x1 + 2x2) ñaïi hoùa lôïi nhuaän cho Xí nghieäp, chuù yù laø Giaûi baèng phöông phaùp ñôn hình. Sau khi theâm caùc bieán buø s vaøo caùc raøng buoäc ta coù : vieäc cheá taïo moät soá leõ radio A vaø B laø i x1 + x2 +s1 = 4 khoâng coù nghóa thöïc teá. 3x1 + x2 + s2 = 10 x1 + 4x2 + s3 = 12 Laäp baûng ñaàu tieân cuûa phöông phaùp ñôn hình : 11/26/2013 55 11/26/2013 56 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính x1 x2 s1 s2 s3 Haèng soá x1 x2 s1 s2 s3 Haèng soá 1 1 1 0 0 4 1 0 4/3 0 -1/3 4/3 3 1 0 1 0 10 0 0 -11/3 1 2/3 10/3 1 4 0 0 1 12 0 1 -1/3 0 1/3 8/3 -1 -2 0 0 0 0 0 0 2/3 0 1/3 20/3 x1 x2 s1 s2 s3 Haèng soá Keát quaû: x1 = 4/3 ,x2 =8/3, s1=s3=0,s2=10/3 vaø F = 3/4 0 1 1 -1/4 1 max 20/3. (x100) 11/4 0 0 1 -1/4 7 Do keát quaû cho bieán quyeát ñònh x1 & x2 khoâng phaûi laø 1/4 1 0 0 1/4 3 soá nguyeân -1/2 0 0 0 1/2 6 ta khoâng chaáp nhaän tieáp tuïc giaûi vôùi Cuting plane. 11/26/2013 57 11/26/2013 58 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính • Phöông phaùp sau ñaây goïi laø phöông phaùp Gomory Moãi soáõ haïng trong phöông trình treân seõ ñöôïc cho pheùp taïo ra caùc raøng buoäc boå sung töø baûng phaân tích thaønh toång cuûa moät soá nguyeân vaø cuoái cuøng cuûa phöông phaùp ñôn hình ôû treân. Caùc moät phaàn leõ theo nguyeân taéc sau : cöôûng böùc boå sung naøy seõ giôùi haïn theâm phaàn mieàn 2 2 1 2 x ( 1 )s (0 )s nghieäm coù theå. 3 2 3 1 3 3 • (Chuù yù: neân choïn raøng buoäc coù bieán buø =0 2s1 s3 Goïi: k vì si>=0 k>=0 !!!) 3 3 • Raøng buoäc thöù 3 trong baûng cuoái cuøng cuûa phöông Tröø hai phöông trình treân vaø chuyeån giaù trò 2 ra phaùp ñôn hình cho ta : veá sau 8 S S 2 x 1 3 k 2 2 3 x2 s1 11/26/2013 3 3 3 59 11/26/2013 60 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống 10
11. PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính Bôûi vì (x2-s1-2) laø soá nguyeân, do ñoù ñieàu kieän caàn cho k Töø p/trình tröôùc (caùc raøng buoäc ñaõ theâm bieán laø k>=2/3. Ngöôïc laïi thì neáu: buø): 2 s1 = 4 - x1 -x2 0 k s3 = 12 - x1 - 4x2 3 Thay theá s1 vaø s3 vaøo phöông trình raøng (2/3-k) laø soá leõ, ñieàu naày khoâng chaáp nhaän ñöôïc. buoäc: 2S S 2 Toùm laïi: 1 3 2S S 2 3 3 3 k  1 3 Do ñoù : x1+2x2 6 Raøng buoäc môùi vaø seõ 3 3 3 ñöa vaøo p/t QHTT ñeå giaûi laïi. 11/26/2013 61 11/26/2013 62 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính Ñaây laø raøng buoäc môùi boå sung, noù cho pheùp giôùi Baøi taäp: Moät xí nghieäp cheá taïo hai loaïi radio A vaø haïn mieàn nghieäm coù theå. Ta laïi baét ñaàu giaûi baøi B . toaùn vôùi raøng buoäc boå sung naøy baèng phöông - Lôïi nhuaän thu ñöôïc töø A vaø B laàn löôït laø 100 phaùp ñôn hình. Quy trình naøy seõ chaám döùt khi $US vaø 200 $US. bieán quyeát ñònh nhaän laáy lôøi giaûi nguyeân ôû lôøi giaûi toái öu. Lôøi giaûi cho baøi toaùn naày seõ laø : - Moät ngöôøi thôï caàn 1 h vaø 4 h ñeå laép raùp A vaø B. 0 2 - Moãi ngaøy ngöôøi thôï chæ coù theå laøm vieäc 12 h. x1 x1 & 3 2 - Ngoaøi ra theo keát quaû cuûa phoøng nghieân cöùu tieáp x2 x2 thò thì khaû naêng tieâu thuï cuûa thò tröôøng toái ña laø 4 Vaø Fmax = 600 $ ( < nghieäm baøi toaùn QHTT) saûn phaåm/ngaøy, khoâng phaân bieät loaïi radio naøo. Chuù yù ta coù 2 lôøi giaûi toái öu cho baøi toaùn naøy. 11/26/2013 63 11/26/2013 64 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính - Veà khaû naêng coâng ngheä, xöôûng caàn 3 Höôùng daãn: h vaø 1 h ñeå cheá taïo caùc linh kieän cho Goïi x1 = Soá löôïng radio A cheá taïo (nguyeân) x2 = Soá löôïng radio B cheá taïo (nguyeân) A vaø B. • Haøm muïc tieâu : - Xöôûng naøy hoaït ñoäng toái ña 10 Max F = 100 (x1 + 2x2) h/ngaøy. • Raøng buoäc: Xaùc ñònh chieán löôïc saûn xuaát A vaø B x1 + x2 < = 4 3x1 + x2 < = 10 ñeå cöïc ñaïi hoùa lôïi nhuaän cho xí x1 + 4x2 < = 12 nghieäp. 11/26/2013 65 11/26/2013 66 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống 11
12. PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính QUY HOAÏCH NHI NGUYEÂN Trong tröôøng hôïp baøi toaùn QHTT ôû ñoù QUY HOẠCH nghieäm chæ coù hai khaû naêng löïa choïn 0 hoaëc 1, ta goïi quy hoaïch nhò nguyeân. NHỊ NGUYÊN (Binary) 11/26/2013 67 11/26/2013 68 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính Baøi taäp (Quy hoaïch nhò nguyeân). Gọi x1, x2, x3, x4 là biến quyết định (x1=0 không Moät Nhaø ñaàu tö coù 4 döï aùn löïa choïn sao cho lôïi chọn p/a 1 và x1=1 chọn phương án 1, ). nhuaän kyø voïng lôùn nhaát. Soá lieäu nhö sau: Hàm mục tiêu: Döï aùn Ñaàu tö naêm 1 Ñaàu tö naêm 2 Lôïi nhuaän F =x1 +0.9x2+0.7x3+1.1x4 Max 1 2 4 1 RÀNG BUỘC: Năm 1: 2x1+3x2+2x3+3x4 <=7 [1] 2 3 2 0.9 Năm 2: 4x1+2x2+2x3+3x4 <=9 [2] 3 2 2 0.7 x1+x3 <=1 [3] 4 3 3 1.1 x1,x2,x3,x4 : binary [4] Bieát raèng khaû naêng huy ñoäng voán naêm 1 laø 7tyû, naêm (Dùng Solver trong Excel giải) 2 laø 9 tyû. Do yeâu caàu kyõ thuaät, döï aùn 1 vaø 3 khoâng Xem SolVer_ViDu_QHNguyen.xls ñöôïc choïn ñoàng thôøi. Thieát laäp HMT & raøng buoäc. 11/26/2013 69 11/26/2013 70 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính • Baøi taäp: Coâng ty loïc hoùa daàu Z coù caùc phöông aùn Khaû naêng giaûi ngaân cuûa Coâng ty ñeå ñaàu tö nhö sau: ñaàu tö (tr.$) nhö sau: • Naêm 1 : toái ña laø 14 tr.$ Döï aùn Phöông aùn Voán ñaàu Voán ñaàu Lôïi nhuaän • Naêm 2: toái ña laø 11 tr.$ tö naêm 1 tö naêm 2 roøng quy ñoåi 1 Xaây döïng NM loïc daàu môùi. 5 7 1 • Bieát raèng neáu phöông aùn 1 ñöôïc choïn thì p/a 2 khoâng choïn vaø ngöôïc laïi. Töông töï cho 2 p/a aùn 4 2 Naâng caáp NM cuõ. 3 2 0.6 vaø 5. Phöông aùn 3 chæ ñöôïc xem xeùt khi coù p/a 1. 3 Xaây döïng ñöôøng oáng daãn 1 1.5 0.3 phuïc vuï p/a 1. YÊU CẦU 4 Xaây döïng NM cung caáp hoùa 3 3 0.8 Thieát laäp HMT & caùc raøng buoäc. chaát coâng nghieäp loïc daàu. Söû duïng phöông phaùp Quy Hoaïch Nhò Nguyeân ñeå 5 Xaây döïng NM ñieän noäi boä. 4.5 3 0.9 tìm toå hôïp caùc phöông aùn ñaàu tö lôïi nhuaän cöïc ñaïi (Xem SolVer_ViDu_QHNguyen.xls) 11/26/2013 71 11/26/2013 72 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống 12
13. PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính Ví duï: Lôïi nhuaän roøng kyø voïng töø kinh doanh cuûa caùc QUY HOAÏCH NHÒ NGUYEÂN p/a (Fi) theo voán ñaàu tö (0 10 tr.$) nhö sau Yeâu caàu: Thieát laäp heä phöông trình quy (Excel file Solver_QHTT1). hoaïch nhò nguyeân vôùi muïc tieâu laø cöïc ñaïi (tr.USD) F1 F2 F3 F4 0 0.00 0.00 0.00 0.00 lôïi nhuaän vôùi giaù trò voán cho bieát tröôùc. 1 0.28 0.25 0.15 0.20 2 0.45 0.41 0.25 0.33 3 0.65 0.55 0.40 0.42 Höôùng daãn: 4 0.78 0.65 0.50 0.48 5 0.90 0.75 0.62 0.53 - Thieát laäp haøm muïc tieâu cuûa baøi toaùn. 6 1.02 0.80 0.73 0.56 7 1.13 0.85 0.82 0.58 - Thieát laäp caùc raøng buoäc. 8 1.23 0.88 0.90 0.60 9 1.32 0.90 0.96 0.60 11/26/201310 1.38 0.99 1.00 0.60 73 11/26/2013 74 PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính • Xaùc ñònh phöông aùn kinh doanh coù hieäu quaû nhaát SÖÛ DUÏNG EXCEL VỚI COÂNG CUÏ theo caùc giaù trò voán ban ñaàu laø 10 tr.$. F1 F2 F3 F4 SOLVER ÑEÅ GIAÛI 0 0 0 0 0 1 0 0 1 0 CAÙC BAØI TOAÙN 2 0 0 0 1 - QUY HOAÏCH TUYEÁN TÍNH; 3 0 1 4E-16 0 4 1 0 0 0 - QUY HOAÏCH NGUYEÂN; 5 0 0 0 0 6 0 0 0 0 - QUY HOAÏCH NHÒ NGUYEÂN; 7 0 0 0 0 - QUY HOAÏCH PHI TUYEÁN. 8 0 0 0 0 9 0 0 0 0 10 0 0 0 0 11/26/2013 75 11/26/2013 76 PGS. Dr.Sum Nguyễn Thống 1 1 1 1 PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính Ví duï: Duøng Solver giaûi baøi toaùn QHTT sau: Ñòa chæ HMT Max Z = x1 + 2x2 + x3 trong file Excel Vôùi raøng buoäc : 2x1 + 3x2 +3x3 =0 Ñòa chæ cac bieán trong file Excel P/t caùc raøng buoäc 11/26/2013 77 11/26/2013 78 PGS. Dr. Nguyễn Thống EXCEL VÔÙI SOLVER PGS. Dr. Nguyễn Thống 13
14. PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính 11/26/2013 79 11/26/2013 80 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính 11/26/2013 81 11/26/2013 82 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính Baøi taäp QUY HOAïCH NGUYEÂN Laáy ví duï treân vôùi lôøi giaûi nguyeân. 11/26/2013 83 11/26/2013 84 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống 14
15. PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính Baøi taäp (Quy hoaïch nhò nguyeân). Moät Nhaø ñaàu tö coù 4 döï aùn löïa choïn sao cho Lôïi nhaän kyø voïng lôùn nhaát. Soá lieäu nhö sau: Döï aùn Ñaàu tö naêm 1 Ñaàu tö naêm 2 Lôïi nhuaän 1 2 4 1 2 3 2 0.9 3 2 2 0.7 4 3 3 1.1 Bieát raèng khaû naêng huy ñoäng voán naêm 1 laø 7tyû, naêm 2 laø 9 tyû. Do yeâu caàu kyõ thuaät, döï aùn 1 vaø 3 khoâng ñöôïc choïn ñoàng thôøi. 11/26/2013 85 11/26/2013 86 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính Tìm lôøi giaûi trong tröôøng hôïp khoâng coù raøng buoäc giöõa hai döï aùn 1 vaø 3. 11/26/2013 87 11/26/2013 88 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính Chương 2: Quy hoạch tuyến tính Baøi taäp: Söû duïng Solver ñeå giaûi caùc baøi taäp ôû treân. 11/26/2013 89 11/26/2013 90 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống 15
16. PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chương 2: Quy hoạch tuyến tính HẾT CHƯƠNG 11/26/2013 91 PGS. Dr. Nguyễn Thống 16