Báo cáo quy hoạch toán học

Chia sẻ: Nguyễn Thảo | Ngày: | Loại File: DOC | Số trang:18

Thêm vào BST

Báo xấu

268
lượt xem 49
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chất liệu bài báo cáo được tham khảo từ nguồn internet và giáo trình Quy hoạch toán học của Ks.Ngô Hữu Tâm. Do lịch học của mỗi thành viên trong nhóm khác nhau nên thời gian làm nhóm ít. Tuy nhiên do phân công phần bài tập hợp lý, bài làm hoàn thành đúng thời gian. Tuy rất cố gắng trong việc trình bày và sử dụng ngôn từ, nhưng có thể bài làm chưa được tốt, còn nhiều hạn chế. Mong muốn nhận được phản hồi của thầy cho những khuyết điểm này....

Chủ đề:

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

Lưu

Nội dung Text: Báo cáo quy hoạch toán học

Bài báo cáo Quy hoạch toán học Trường Đại Học Sư Phạm Kỹ Thuật TP.Hồ Chí Minh KHOA KHOA HỌC CƠ BẢN BỘ MÔN TOÁN ------------ BÀI BÁO CÁO Quy hoạch tuyến tính -1-
Bài báo cáo Quy hoạch toán học Tự nhận xét đánh giá : Chất liệu bài báo cáo được tham khảo từ nguồn internet và giáo trình Quy hoạch toán học của Ks.Ngô Hữu Tâm. Do lịch học của mỗi thành viên trong nhóm khác nhau nên thời gian làm nhóm ít. Tuy nhiên do phân công phần bài tập hợp lý, bài làm hoàn thành đúng thời gian. Tuy rất cố gắng trong việc trình bày và sử dụng ngôn từ, nhưng có thể bài làm chưa được tốt, còn nhiều hạn chế. Mong muốn nhận được phản hồi của thầy cho những khuyết điểm này. Giáo viên: Ngô Hữu Tâm Trình bày: Nhóm 11 Nguyễn Thị Diệu Thảo 08109038 ( lớp sáng thứ 3, tiết 1) Đỗ Thị Liên 08109022 Lê Thị Ý Nhi 06109076 Sđt liên lạc : 01669139182 ( Thảo) – 0979975711(Liên) Tp HCM, ngày 16 tháng 11 năm 2009 PHẦN I a. Kì vọng và phương sai cho các đại lượng ngẫu nhiên biểu thị thời gian hoàn thành công việc : 2 a  4m  b ba 2 E(T)= ; Var(T)=   = 6  6  Thời gian cần (tuần) Công E(T)=t Var(T) Trình tự tiến hành việc a m b -2-
Bài báo cáo Quy hoạch toán học Y1 2 4 6 4 4/9 Bắt đầu ngay Y2 4 5.5 8 5.8 4/9 Bắt đầu ngay Y3 1.5 2 2.5 2 1/36 Bắt đầu ngay Y4 6 7 8 7 1/9 Sau Y3 Y5 2 4 6 4 4/9 Sau Y2 và Y4 Y6 6 10 14 10 16/9 Sau Y1 và Y5 Y7 2 2.5 6 3 4/9 Sau Y1 và Y5 Y8 3 6 9 6 1 Sau Y6 Y9 10 11 12 11 1/9 Sau Y7 Y10 5.5 7 8.5 7 1/4 Sau Y3 Y11 3 7.75 9 7.2 1 Sau Y6, Y10, Y12 Y12 1.25 2.5 2.75 2.4 1/16 Sau Y2 và Y4 Y13 1.5 1.75 2.5 2 1/36 Sau Y8 và Y9 Dựa vào bảng này và xem thời gian hoàn thành mỗi công việc là t, ta lập sơ đồ PERT, xác định đường găng và công việc găng, tính chỉ tiêu thời gian cho các công việc. Kì vọng được làm tròn số thập phân như sau : Khoảng (0 ;0.2] (0.2 ;0.4] (0.4 ;0.6] (0.6 ;0.8] (0.8 ;1) Làm tròn thành 0.2 0.4 0.6 0.8 1 b. Lập sơ đồ PERT, xác định đường găng, ước tính thời gian trung bình để hoàn thành dự án. Tính xác suất để toàn bộ dự án được hoàn thành với thời gian không quá 39 tuần. Lập bảng chỉ tiêu thời gian cho các công việc và dựng sơ đồ PERT ngang với điều kiện nguồn nhân lực của công ty không thể thực hiện 4 công việc cùng một thời điểm. SƠ ĐỒ PERT -3-
Bài báo cáo Quy hoạch toán học Đường găng đi qua các đỉnh 1, 2, 3, 4, 6, 8, 9 và có chiều dài là 31 Thời gian trung bình hoàn thành dự án là kì vọng E(T) và bằng với độ dài đường găng : E(T)=31 1 1 4 16 1 61 Phương sai : Var(T)= Var (T ( i , j )G ij )=    1 36 9 9 9  36 18 61 Độ lệch chuẩn  (T )  Var (T )   1.84 18 Xác suất để toàn bộ dự án được hoàn thành với thời gian không quá 39 tuần là :  Tqđ  E (T )   E (T )  P (T  Tqđ )      (T )      (T )                 P(T  39)    39  31     31  =  (4.35)   (16.84)  0.99  61   61       18   18  Bảng chỉ tiêu thời gian : tksij = tsi thmij = tmj thsij = tksij + tij tkmij = thmij – tij dcij = tmj –tsi –tij dđlij = max{ 0, tsj – tmi – tij } -4-
Bài báo cáo Quy hoạch toán học Công việc tksij thsij thm ij tkmij dcij dđlij Y1 (1,4) 0 4 13 9 9 9 Y2 (1,3) 0 5.8 9 3.2 3.2 3.2 Y3 (1,2) 0 2 2 0 0 0 Y4 (2,3) 2 9 9 2 0 0 Y5 (3,4) 9 13 13 9 0 0 Y6 (4,6) 13 23 23 13 0 0 Y7 (4,5) 13 16 18 15 2 0 Y8 (6,8) 23 29 29 23 0 0 Y9 (5,8) 16 27 29 18 2 0 Y10 (2,7) 2 9 23.8 16.8 14.8 14 Y11 (7,9) 23 30.2 31 23.8 0.8 0 Y12 (3,7) 9 11.4 23.8 21.4 12.4 11.6 Y13 (8,9) 29 31 31 29 0 0 Sơ đồ pert ngang -5-
Bài báo cáo Quy hoạch toán học c. Bảng chi phí( triệu đồng) C k   .k 2 Tuần 1 2 3 4 Công việc Y1 4 16 36 64 Y2 7 28 63 112 Y3 4 16 36 64 Y4 5 20 45 80 Y5 3 12 27 48 Y6 7 28 63 112 Y7 2 8 18 32 Y8 5 20 45 80 Y9 2 8 18 32 Y10 9 36 81 144 Y11 4 16 36 64 Y12 2 8 18 Y13 3 12 27 Công việc trên đường găng có chi phí nhỏ nhất là Y5 và Y13 (3 triệu đồng/ tuần 1). Ta rút ngắn Y5 xuống còn 3 tuần, Y13 xuống còn 1 tuần. Tính lại tất cả các chỉ tiêu trên đỉnh ta được sơ đồ PERT sau đây: Chi phí là 3+3 = 6 (triệu đồng) -6-
Bài báo cáo Quy hoạch toán học Sơ đồ trên có đường găng mới đi qua các đỉnh 1, 2, 3, 4, 5, 6, 7, 9. Tuy nhiên chỉ tiêu rút ngắn xuống còn 29 tuần chưa đạt được. Công việc trên đường găng mới có chi phí nhỏ nhất là Y3 và Y11 (4 triệu đồng/ tuần 1). Ta rút ngắn Y11 xuống còn 7 tuần với chi phí là 4*12*0.2 = 0.8 ( triệu đồng) Tính lại tất cả các chỉ tiêu trên đỉnh ta được sơ đồ PERT sau : Sơ đồ này có 2 đường găng như hình vẽ đi qua các đỉnh 1, 2, 3, 4, 6, 7, 8, 9. Tổng chi phí rút ngắn = 3+3+0.8 = 6.8 ( triệu đồng) Bảng chi tiêu thời gian : Công việc tksij thsij thm ij tkmij dcij dđlij Y1 (1,4) 0 4 12 8 8 8 Y2 (1,3) 0 5.8 9 3.2 3.2 3.2 Y3 (1,2) 0 2 2 0 0 0 Y4 (2,3) 2 9 9 2 0 0 Y5 (3,4) 9 12 12 9 0 0 Y6 (4,6) 12 22 22 12 0 0 Y7 (4,5) 12 15 17 14 2 0 Y8 (6,8) 22 28 28 22 0 0 Y9 (5,8) 15 26 28 17 2 0 Y10 (2,7) 2 9 22 15 13 13 Y11 (7,9) 22 29 29 18 0 0 Y12 (3,7) 9 11.4 22 19.6 10.6 10.6 Y13 (8,9) 28 29 29 28 0 0 -7-
Bài báo cáo Quy hoạch toán học d. Khi sự cố xảy ra ở tuần 6 có : - Hai công việc đả hoàn thành là Y1 và Y3 - Ba công việc đang được tiến hành là Y2, Y4, và Y10 Ta coi như thời gian để hoàn thành công việc Y2, Y4, Y10 tăng thêm 1 tuần : Y2 cần 5.8+1=6.8 tuần Y4 cần 7 + 1 = 8 tuần Y10 cần 7+1 = 8 tuần Các công việc còn lại tiến hành bình thường Ta có sơ đồ PERT sau : -8-
Bài báo cáo Quy hoạch toán học Sơ đồ này có 2 đường găng đi qua các đỉnh 1, 2, 3, 4, 6, 7, 8, 9. Cần điều chỉnh kế hoạch sao cho thời gian trung bình hoàn thành dự án không quá 29 tuần với chi phí thấp nhất. Công việc trên đường găng có chi phí thấp nhất là Y11(4 triệu đồng/ tuần 1). Y4 và Y8 ( 5 triệu đồng/ tuần 1) Để chi phí nhỏ nhât, rút Y4 xuống còn 7 tuần ( rút sau tuần 6). Tính lại tất cả các chỉ tiêu trên đỉnh, ta được sơ đồ PERT sau : Bảng chỉ tiêu thời gian Công việc tksij thsij thm ij tkmij dcij dđlij Y1 (1,4) 0 4 12 8 8 8 Y2 (1,3) 0 6.8 9 2.2 2.2 2.2 Y3 (1,2) 0 2 2 0 0 0 Y4 (2,3) 2 9 9 2 0 0 Y5 (3,4) 9 12 12 9 0 0 Y6 (4,6) 12 22 22 12 0 0 Y7 (4,5) 12 15 17 14 2 0 Y8 (6,8) 22 28 28 22 0 0 Y9 (5,8) 15 26 28 17 2 0 Y10 (2,7) 2 10 22 14 12 12 Y11 (7,9) 22 29 29 22 0 0 Y12 (3,7) 9 11.4 22 19.6 10.6 10.6 Y13 (8,9) 28 29 29 28 0 0 -9-
Bài báo cáo Quy hoạch toán học PHẦN II Bài 1: Giải bài toán QHTT: (1) F ( x )  x1  2 x2  x3  max  x1  2 x2  3 x3  10 (2)   x1  3 x 2  x3  5 (3) xj  0 j  1,3 (Giải bằng excel) Để giải quyết các bài toán QHTT, phần mềm Excel cung cấp cho ta một công cụ hữu ích là Solver. 1. Cài thêm công cụ Add-ins Solver Vào menu Tools / Solver. Nếu chưa thấy chức năng Solver, ta cần bổ sung chức năng này vào Excel. Ta tiến hành như sau: Vào menu Tools / Add-Ins, xuất hiện cửa sổ: - 10 -
Bài báo cáo Quy hoạch toán học Chọn Solver Add-Ins và chọn OK 2. Tổ chức dữ liệu bài toán trên bảng tính: Việc xây dựng bài toán trong Excel cũng tương tự như việc xây dựng bài toán khi chúng ta tiến hành giải thủ thông thường. Sau khi phân tích bài toán chúng ta cần xác định hàm mục tiêu và các ràng buộc của bài toán rồi tiến hành tổ chức dữ liệu vào bảng tính. Ta tổ chức dữ liệu như bảng:  Biến quyết định: được nhập tại các ô B2:D2. Cho các giá trị khởi đầu là 0  Hệ số hàm mục tiêu: được nhập tại các ô B3:D3  Hàm mục tiêu: có giá trị căn cứ vào giá trị khởi động của các biến. Có công thức tại ô B9  Các ràng buộc: nhập giá trị các hệ số của các quan hệ ràng buộc tại các ô B5:D6. Tính vế trái của các ràng buộc theo công thức tại các ô B10:B11. Nhập giá trị vế phải của các ràng buộc tại các ô F5:F6 - 11 -
Bài báo cáo Quy hoạch toán học Sau khi nhập xong dữ liệu vào bảng tính, ta tiến hành giải bài toán. 3. Tiến hành giải bài toán (1) Chọn ô E3 và chọn Tools / Solver. Bảng hộp thoại Solver Parameters xuất hiện gồm các thông số sau: Set Target Cell: Nhập ô chứa địa chỉ tuyệt đối của hàm mục tiêu. Địa chỉ ô E3 được đưa vào. Equal To: Xác định giới hạn cho hàm mục tiêu hoặc giá trị cần đạt đến của hàm mục tiêu. Max, min, hay value of tùy yêu cầu bài toán. Ta chọn Max để Solver tìm lời giải cực đại cho hàm mục tiêu. By Changing Cells: Nhập địa chỉ tuyệt đối của các ô ghi giá trị ban đầu của các biến. Ta nhập địa chỉ của các biến quyết định B2:D2 tại đây. - 12 -
Bài báo cáo Quy hoạch toán học Subject To the Constraints: Nhập các ràng buộc của bài toán. Cách làm của Solver là thay đổi giá trị của các biến tại By Changing Cells cho đến lúc giá trị của các hàm mục tiêu tại Set Target Cell đạt một giá trị quy định tại Equal To và đồng thời thỏa mãn tập các ràng buộc tại Subject To the Constraints. Thêm các ràng buộc vào Subject To the Constraints : Nhấp nút Add. Bảng Add Constraints xuất hiện gồm các thông số sau: Cell Reference: ô hoặc vùng ô chứa công thức của các ràng buộc Ô dấu: Cho phép ta lựa chọn dấu của các ràng buộc tương ứng. Constraints: Ô chứa giá trị vế phải của các ràng buộc tưowng ứng ( ta cũng có thể nhập trực tiếp giá trị vế phải của các ràng buộc tương ứng) Các ràng buộc về dấu do X j  0 , j  1,3 (các ràng buộc đều có dạng  0) nên ta chọn vùng địa chỉ chứa biến B2:D2 vào Cell Reference, chọn dấu >= và nhập 0 vào Constraint: - 13 -
Bài báo cáo Quy hoạch toán học Tiếp tục chọn Add để nhập tiếp các ràng buộc phương trình và bất phương trình: E5=F6 Chọn OK để kết thúc việc khai báo các ràng buộc. Tuy nhiên, muốn hiệu chỉnh ràng buộc ta chọn ràng buộc và chọn change, xóa ràng buộc từ danh sách Subject To the Constraints và nhấp Delete. Các thông số bài toán sau khi khai báo hoàn chỉnh: Trong hộp thoại Options phải chọn Assume Linear Model (khẳng định mô hình của ta là tuyến tính). Sau khi hoàn tất ta chọn Solve để chạy Solver, hộp thoại kết quả xuất hiện và cho ta hai sự lựa chọn sau: Keep Solver Solution: Giữ kết quả và in ra bảng tính Restore Original Values: Hủy kết quả vừa tìm được và trả các biến về tình trạng ban đầu. Save Scenario: Lưu kết quả vừa tìm được thành một tình huống để có thể xem lại sau này. Ngoài ra có 3 loại báo cáo là Answer, Sensitivty, Limits Ta chọn Keep Solver Solution, OK. Bảng kết quả nhận được như sau : - 14 -
Bài báo cáo Quy hoạch toán học Như vậy phương án cực biên tìm được là x = (0;5;0 )và giá trị cực đại của hàm mục tiêu f(x) là 10. Bài 2: Giải bài toán vận tải ( f  max) cân bằng thu phát sau: Thu B1 B2 B3 B4 Phát 40 60 30 70 A1:50 8 5 5 3 A2:70 6 9 8 7 A3:80 4 6 6 5 3 4 Ta có : A i 1 i  50  70  80   B j  40  60  30  70  200 j 1 Ta xét bài toán vận tải 3 điểm phát và 4 điểm thu được nhập vào bảng tính: - 15 -
Bài báo cáo Quy hoạch toán học  Khối A2:D4 là ma trận chi phí vận chuyển, khối A7:D9 là phương án vận chuyển ( giá trị ban đầu cho tất cả bằng 1), khối F7:F9 là khả năng của 3 điểm phát, khối A11:D11 là nhu cầu của 4 điểm thu, khối E7:E9 là lượng hàng phát đi từ mọi điểm i theo phương án X đã chọn, khối A10:D10 là lương hàng nhận được từ mọi điểm thu j theo phương án X.  Quá trình dùng slover để giải bài toán vận tải theo các bước:  Bước 1: Nhập chi phí vận chuyển vào các ô A2:D4, nhập khả năng các điểm phát vào F7:F9, nhu cầu điểm thu vào A11:D11, phương án ban đầu vào A7:D9.  Bước 2: Tính giá trị hàm mục tiêu ô F3 theo công thức F3=Sumproduct(A2:D4, A7:D9) hàm này tính tổng các tích của từng cặp phần tử trong hai khối ô. Tính lượng hàng phát của điểm phát 1 tại ô E7 theo công thức E7=Sum(A7:D7), sao chép công thức này vào các ô E8:E9. Tính lượng hàng nhận được của điểm thu 1 tại ô A10 theo công thức A10=sum(A7:A9), sao chép công thức này vào các ô B10:D10.  Bước 3: Dùng lệnh Tools/Slover với các lựa chọn hàm mục tiêu và các ràng buộc. - 16 -
Bài báo cáo Quy hoạch toán học Trong hộp thoại Slover Options phải chọn Assume Linear Model (khẳng định mô hình của ta là tuyến tính). Sau khi hoàn tất ta chọn solve để chạy solver,hộp thoại kết quả xuất hiện và cho ta hai sự lựa chọn sau: - Keep Solver Solution: giữ kết quả và in ra bảng tính. - Restore Original Values: hủy kết quả vừa tìm được và trả các biến về tình trạng ban đầu. - Save Scenario: lưu kết quả vừa tìm được thành một tình huống để có thể xem lại sau này. Ta chọn Keep Solver Solution, Ok. Bảng kết quả nhận được như sau: - 17 -
Bài báo cáo Quy hoạch toán học Vậy đáp án tìm được là: X11=40, X21=0, X31=0 X12=0, X22=60,X32=0 X13=10, X23=10, X33=10 X14=0, X24=0, X34=70 Cuối cùng ta nhận được giá trị tối ưu hàm mục tiêu bằng : Fmin =40*8+60*9+10*5+10*8+10*6+70*5=1400 Hoàn tất !!!! oh Yeah ^^! - 18 -