Luận văn Một giải pháp toán học cho việc phân phối tài nguyên trong độ tin cậy phần mềm

Đại Học Quốc Gia Thành Phố Hồ Chí Minh Trường Đại Học Bách Khoa PHAN THỊ NGỌC MAI MỘT GIẢI PHÁP TOÁN HỌC CHO VIỆC PHÂN PHỐI TÀI NGUYÊN TRONG ĐỘ TIN CẬY PHẦN MỀM Chuyên ngành: Khoa học Máy tính LUẬN VĂN THẠC SĨ TP. HỒ CHÍ MINH, tháng 06 năm 2008 ĐẠI HỌC QUỐC GIA TP. HCM CỘNG HOÀ Xà HỘI CHỦ NGHIà VIỆT NAM TRƯỜNG ĐẠI HỌC BÁCH KHOA Độc Lập - Tự Do - Hạnh Phúc ---------------- ---oOo--- Tp. HCM, ngày . .30. . tháng . .06. . năm .2008. NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ và tên học viên : Phan Thị Ngọc Mai ...........................Giới tính : Nam… / Nữ ; Ngày, tháng, năm sinh : 1978............................................Nơi sinh : Bến Tre .................... Chuyên ngành : Khoa học Máy tính...................................................................................... Khoá : 15 .............................................................................................................................. 1- TÊN ĐỀ TÀI : ............................................................................................................... MỘT GIẢI PHÁP TOÁN HỌC CHO VIỆC PHÂN PHỐI TÀI NGUYÊN TRONG ĐỘ TIN CẬY PHẦN MỀM ........................................................................................................................................... ........................................................................................................................................... 2- NHIỆM VỤ LUẬN VĂN : .............................................................................................. ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... 3- NGÀY GIAO NHIỆM VỤ : ........................................................................................... 4- NGÀY HOÀN THÀNH NHIỆM VỤ : .......................................................................... 5- HỌ VÀ TÊN CÁN BỘ HƯỚNG DẪN : TS. Nguyễn Văn Minh Mẫn .......................... Nội dung và đề cương Luận văn thạc sĩ đã được Hội Đồng Chuyên Ngành thông qua. CÁN BỘ HƯỚNG DẪN CHỦ NHIỆM BỘ MÔN (Họ tên và chữ ký) QUẢN LÝ CHUYÊN NGÀNH (Họ tên và chữ ký) TS. Nguyễn Văn Minh Mẫn TS. Đinh Đức Anh Vũ CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH Cán bộ hướng dẫn khoa học : TS. Nguyễn Văn Minh Mẫn ........................................ Cán bộ chấm nhận xét 1 : ............................................................................................ Cán bộ chấm nhận xét 2 : ............................................................................................ Luận văn thạc sĩ được bảo vệ tại HỘI ĐỒNG CHẤM BẢO VỆ LUẬN VĂN THẠC SĨ TRƯỜNG ĐẠI HỌC BÁCH KHOA, ngày . . . . tháng . . . . năm . 2008. Một giải pháp toán học cho việc phân phối chi phí trong độ tin cậy phần mềm Phan Thị Ngọc Mai Trang i LỜI CAM ĐOAN Tôi cam đoan rằng, ngoại trừ các kết quả tham khảo từ các công trình khác như đã ghi rõ trong luận văn, các công việc trình bày trong luận văn này là do chính tôi thực hiện và chưa có phần nội dung nào của luận văn này được nộp để lấy một bằng cấp ở trường này hoặc trường khác. Ngày 30 tháng 06 năm 2008 Phan Thị Ngọc Mai Một giải pháp toán học cho việc phân phối chi phí trong độ tin cậy phần mềm Phan Thị Ngọc Mai Trang ii LỜI CẢM ƠN Tôi xin gởi lời cảm ơn chân thành nhất đến TS. Nguyễn Văn Minh Mẫn, người đã tận tình hướng dẫn, giúp đỡ tôi trong suốt quá trình thực hiện luận văn và tạo điều kiện để tôi có thể hoàn thành luận văn này. Xin gởi lời cảm ơn đến các Thầy Cô đã dạy tôi trong thời gian qua. Tôi xin cảm ơn các bạn đồng môn và đồng nghiệp đã quan tâm, chia sẽ trong suốt quá trình học và làm luận văn. Xin cảm ơn gia đình đã dành cho tôi tình thương yêu và sự hỗ trợ tốt nhất. Một giải pháp toán học cho việc phân phối chi phí trong độ tin cậy phần mềm Phan Thị Ngọc Mai Trang iii TÓM TẮT LUẬN VĂN Đánh giá độ tin cậy phần mềm là một vấn đề quan trọng trong việc đánh giá chất lượng của một phần mềm. Quá trình này thường được thực hiện trong các giai đoạn thiết kế phần mềm, kiểm tra lỗi phần mềm. Công việc kiểm tra lỗi phần mềm được triển khai xuyên suốt các giai đoạn phát triển phần mềm, công việc này giúp giảm chi phí và nâng cao chất lượng phần mềm khi triển khai cho khách hàng. Trong thời gian hệ thống kiểm tra, việc đo lường độ tin cậy phần mềm là tiêu chuẩn quan trọng có tác dụng quyết định có nên công bố phần mềm phần này hay không. Ngoài ra, một vấn đề rất quan trọng quyết định sự thành bại của phần mềm và đang làm đau đầu các nhà quản lý dự án. Đó là làm thế nào để phân phối chi phí một cách hiệu quả nhằm tạo ra một phần mềm có tính tin cậy cao. Đã có một số phương pháp giải quyết bài toán được hiện thực theo một số mô hình toán học. Phương pháp kết hợp quy hoạch nguyên và quy hoạch phi tuyến là một giải pháp hữu hiệu để giải quyết vấn đề này. Đề tài này trình bày một giải pháp toán học đa bước để phân phối tài nguyên cho độ tin cậy phần mềm. Sử dụng quy hoạch nguyên nhị phân để thực hiện việc phân phối chi phí cho các module mua. Sử dụng quy hoạch phi tuyến để thực hiệc việc phân phối chi phí cho các module phát triển trong công ty. Thông qua việc kết hợp này, luận văn đã xây dựng được giải pháp cho phép giải quyết bài toán theo hai hướng: tìm độ tin cậy lớn nhất có thể có của phần mềm mà không vượt quá giới hạn chi phí đã cho và ngược lại tìm chi phí nhỏ nhất để phần mềm có độ tin cậy là một giá trị xác định trước. Chương trình hiện thực đã cung cấp được một lời giải với độ chính xác tương đối cho một số minh họa cụ thể. Từ khoá: Algorithm, Binary Integer Programming, Branch and Bound, Developed module, In-house Integration module, Nonlinear programming, Resource allocation, Programming modules, Purchased module, Software reliability. Một giải pháp toán học cho việc phân phối chi phí trong độ tin cậy phần mềm Phan Thị Ngọc Mai Trang iv MỤC LỤC LỜI CAM ĐOAN ...........................................................................................................i LỜI CẢM ƠN ............................................................................................................... ii TÓM TẮT LUẬN VĂN .............................................................................................. iii DANH MỤC HÌNH ..................................................................................................... vi DANH MỤC BẢNG ................................................................................................... vii Chương 1. GIỚI THIỆU...............................................................................................1 1.1. Giới thiệu ..............................................................................................................1 1.2. Sơ lược về việc phân phối độ tin cậy phần mềm...............................................2 1.3. Kết cấu của luận văn ...........................................................................................4 Chương 2. Các Mô Hình Phân Phối Chi Phí Cho Độ Tin Cậy Phần Mềm .............6 2.1. Giới thiệu ..............................................................................................................6 2.2. Phân loại các module trong phần mềm..............................................................6 2.3. Mô hình quyết định trước ...................................................................................7 2.3.1. Độ tin cậy của một module đơn phát triển trong công ty............................................7 2.3.2. Độ tin cậy của một module mua .................................................................................8 2.3.3. Độ tin cậy của một module tích hợp ...........................................................................9 2.4. Mô hình tổng quát .............................................................................................14 Chương 3. Phương Pháp Giải Bài Toán Quy Hoạch Nguyên.................................15 3.1. Giới thiệu ............................................................................................................15 3.2. Sự cần thiết của bài toán quy hoạch nguyên...................................................15 3.3. Phương pháp giải quyết bài toán quy hoạch nguyên .....................................16 3.4. Phương pháp giải quyết bài toán quy hoạch nguyên nhị phân .....................19 Chương 4. Phương Pháp Giải Bài Toán Quy Hoạch Phi Tuyến ...........................23 4.1. Giới thiệu ............................................................................................................23 4.2. Những điều kiện tối ưu......................................................................................25 4.3. Tính lồi của hàm nhiều biến .............................................................................26 4.3.1. Tập lồi .......................................................................................................................26 4.3.2. Định nghĩa hàm lồi ...................................................................................................26 4.3.3. Đặc trưng của hàm lồi...............................................................................................26 4.4. Các phương pháp giải bài toán quy hoạch phi tuyến.....................................27 4.4.1. Giải bài toán tối ưu không có điều kiện ràng buộc ...................................................27 4.4.2. Giải bài toán tối ưu với điều kiện ràng buộc các biến lớn hơn 0 ..............................28 4.4.3. Giải bài toán tối ưu với điều kiện ràng buộc là các phương trình tuyến tính............30 4.4.4. Giải bài toán tối ưu với điều kiện ràng buộc là các phương trình phi tuyến.............34 Chương 5. Giải Quyết Bài Toán ................................................................................36 5.1. Phân hoạch bài toán ..........................................................................................36 5.2. Bài toán tối ưu hóa các module mua................................................................37 5.3. Bài toán tối ưu hóa các module phát triển trong công ty...............................39 Một giải pháp toán học cho việc phân phối chi phí trong độ tin cậy phần mềm Phan Thị Ngọc Mai Trang v 5.4. Sự kết hợp module mua và module phát triển trong công ty ........................40 5.4.1. Bài toán A .................................................................................................................41 5.4.2. Bài toán B .................................................................................................................46 Chương 6. Một số kết quả, kết luận...........................................................................51 6.1. Sơ lược về chương trình ....................................................................................51 6.2. Một số kết quả chạy chương trình ...................................................................51 6.2.1. Bài toán trong ví dụ 3.4 ............................................................................................51 6.2.2. Bài toán trong ví dụ 4.1.1 .........................................................................................51 6.2.3. Bài toán trong ví dụ 4.3.1 .........................................................................................52 6.2.4. Bài toán trong ví dụ 4.3.4 .........................................................................................52 6.2.5. Bài toán cho một phần mềm gồm có 6 module.........................................................54 6.2.6. Bài toán cho một phần mềm gồm có 11 module.......................................................56 6.2.7. Bài toán cho một phần mềm gồm có 22 module.......................................................61 6.2.8. Bài toán cho một phần mềm gồm có 37 module.......................................................67 6.3. Kết luận...............................................................................................................74 Tài Liệu Tham Khảo ...................................................................................................76 Phụ lục 1. Bảng đối chiếu Thuật ngữ Anh - Việt......................................................77 Phụ lục 2. Bảng tóm tắt các mô hình đánh giá độ tin cậy phần mềm ....................78 Phụ lục 3. Sơ lược về MATLAB.................................................................................80 Tham khảo Chỉ Mục ...................................................................................................84 Một giải pháp toán học cho việc phân phối chi phí trong độ tin cậy phần mềm Phan Thị Ngọc Mai Trang vi DANH MỤC HÌNH Hình 2.1: Độ tin cậy của một module phần mềm .......................................................8 Hình 2.2: Một hệ thống databate-indexing ...............................................................11 Hình 3.1: Giá trị tối ưu LP khi làm tròn xa với giá trị tối ưu của IP problem......16 Hình 3.2: Một cây liệt kê đầy đủ ................................................................................17 Hình 3.3 : Cây tìm kiếm cho ví dụ 3.2 .......................................................................22 Hình 4.1: Một giải pháp hình học cho ví dụ 4.1.1.....................................................24 Hình 4.2: Một giải pháp hình học cho ví dụ 4.1.2.....................................................25 Hình 5.1: Sự phân hoạch bài toán..............................................................................36 Hình 6.1: Mô hình một phần mềm có 11 module .....................................................56 Hình 6.2: Mô hình một phần mềm có 22 module .....................................................61 Hình 6.3: Mô hình một phần mềm có 37 module .....................................................67 Một giải pháp toán học cho việc phân phối chi phí trong độ tin cậy phần mềm Phan Thị Ngọc Mai Trang vii DANH MỤC BẢNG Bảng 2.1: Giải pháp cho những nguồn ngân sách khác nhau .................................13 Bảng 6.1: Kết quả chạy phần mềm có 6 module cho bài toán A.............................54 Bảng 6.2: Kết quả chạy phần mềm có 6 module cho bài toán B.............................55 Bảng 6.3: Kết quả chạy phần mềm có 11 module cho bài toán A...........................59 Bảng 6.4: Kết quả chạy phần mềm có 11 module cho bài toán B...........................60 Bảng 6.5: Kết quả chạy phần mềm có 22 module cho bài toán A...........................65 Bảng 6.6: Kết quả chạy phần mềm có 22 module cho bài toán B...........................66 Bảng 6.7: Kết quả chạy phần mềm có 37 module cho bài toán A...........................72 Bảng 6.8: Kết quả chạy phần mềm có 37 module cho bài toán B...........................73 Một giải pháp toán học cho việc phân phối tài nguyên trong độ tin cậy phần mềm Phan Thị Ngọc Mai Trang 1 Chương 1. GIỚI THIỆU 1.1. Giới thiệu Trong vài thập niên gần đây, cùng với sự xuất hiện của máy tính, các phần mềm hỗ trợ xử lý công việc cho người sử dụng cũng gia tăng theo cả về số lượng cũng như chất lượng. Trong công việc hàng ngày, hầu như ai cũng dựa vào máy tính để gia tăng hiệu suất công việc. Nhu cầu người sử dụng ngày càng tăng cao, đòi hỏi công nghệ và các phần mềm phục vụ cho con người cũng phát triển không ngừng. Ngày nay, máy tính đã được con người sử dụng trong mọi thiết bị từ đồng hồ đeo tay, điện thoại, các thiết bị trong nhà, xe mô tô .v.v. Khoa học kỹ thuật đòi hỏi tốc độ tính toán cũng như độ chính xác, vấn đề đó đồng nghĩa với việc phát triển khả năng xử lý của phần cứng và chất lượng của phần mềm. Một vấn đề đang làm đau đầu các nhà quản lý đó là bằng cách nào đó họ có thể phân bổ tài nguyên một cách hợp lý để tạo ra phần mềm với lợi nhuận và chất lượng cao. Đề tài nghiên cứu việc phân phối tài nguyên cho độ tin cậy phần mềm này giúp chúng ta có thể quản lý và phân bổ tài nguyên cho việc xây dựng phần mềm có chất lượng cao. Dựa vào các yếu tố hiện có của công ty, chúng ta có thể chủ động xây dựng kế hoạch phân bổ tài nguyên để có thể giảm thiểu được các nguy cơ rủi ro đến mức thấp nhất, nhằm tạo ra phần mềm có tính tin cậy nhất. Để tiếp cận và tìm ra giải pháp để giải quyết bài toán nhằm tạo ra được một phần mềm chắc chắn đáng tin cậy theo yêu cầu, đề tài này cố gắng tập trung vào giải quyết một số vấn đề sau: ƒ Xác định các mudule phần mềm: phần module nào sẽ được phát triển tại công ty và phần module nào sẽ được mua, phần module nào sẽ dùng lại. ƒ Dự đoán tài nguyên (chi phí) cần thiết cho từng module và tính toán độ tin cậy mong đợi với tài nguyên đó. ƒ Tính độ tin cậy lớn nhất có thể đạt được của hệ thống phần mềm không vượt quá giới hạn ngân sách đã cho. Một giải pháp toán học cho việc phân phối tài nguyên trong độ tin cậy phần mềm Phan Thị Ngọc Mai Trang 2 ƒ Tìm chi phí nhỏ nhất để phần mềm có độ tin cậy là một hằng số xác định trước. Với những mục tiêu này đề tài đã thu được một số kết quả: ƒ Xây dựng được mô hình tổng quát cho bài toán quy hoạch nguyên dạng nhị phân, trên cơ sở đó áp dụng cho bài toán tối ưu hóa các module mua. ƒ Xây dựng được mô hình tổng quát cho bài toán quy hoạch phi tuyến, trên cơ sở đó áp dụng cho bài toán tối ưu hóa các module phát triển trong công ty. ƒ Xây dựng được một mô hình phân phối chi phí để phần mềm có độ tin cậy lớn nhất. ƒ Xây dựng được một mô hình phân phối chi phí nhỏ nhất để phần mềm có độ tin cậy là một hằng số cho trước. 1.2. Sơ lược về việc phân phối độ tin cậy phần mềm Quá trình phân phối chi phí cho độ tin cậy phần mềm được thực hiện như sau: Đầu tiên, xác định các module trong phần mềm module nào là module đơn và module nào là module tích hợp. Module đơn nào được phát triển trong công ty và module đơn nào sẽ được mua bên ngoài thị trường. Tiếp theo, xác định công thức tính độ tin cậy cho từng loại module: ƒ Đối với module mua, mỗi module mua có nhiều version trên thị trường, ứng với mỗi version đều có độ tin cậy và chi phí khác nhau. Độ tin cậy và chi phí của một module bằng độ tin cậy và chi phí của version mà chúng ta lựa chọn mua. Với lý do tiết kiệm chi phí, do đó chúng ta phải lựa chọn duy nhất một trong số các version đã cho. Do đó để thực hiện được vấn đề này, chúng ta đưa một biến thực hiện công việc lựa chọn mua hay không mua một version nào đó. Đó là các biến nguyên nhị phân. ƒ Đối với các module phát triển trong công ty, độ tin cậy của một module sẽ phụ thuộc vào chi phí. Khi chi phí tăng thì độ tin cậy cũng tăng theo. Tuy nhiên, độ tin cậy sẽ tăng đến một mức độ nào đó thì sẽ tăng chậm lại, cho dù ta có tăng chi phí nhiều thì độ tin cậy cũng tăng chậm. Qua việc khảo Một giải pháp toán học cho việc phân phối tài nguyên trong độ tin cậy phần mềm Phan Thị Ngọc Mai Trang 3 sát hàm số mũ âm, ta nhận thấy cách đo độ tin cậy phần mềm rất giống với hàm số mũ âm. Do đó ta chọn hàm số mũ âm để mô tả độ tin cậy của các module phát triển trong công ty và các biến trong các module phát triển trong công ty là các biến thực. Việc giải quyết bài toán tối ưu hoá phân phối chi phí cho độ tin cậy phần mềm tồn tại cả hai loại biến nguyên nhị phân và biến thực rất khó giải quyết. Một phương án đề xuất phân hoạch bài toán thành hai phần: phần