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. 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 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. 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Ụ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 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 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 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 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. ƒ 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 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 module mua và phần module phát triển trong công ty, chi phí để phát triển phần mềm cũng được phân hoạch thành hai phần ứng với hai sự phân hoạch đó. ƒ Đối với bài toán module mua, cấu trúc bài toán giống như một bài toán quy hoạch tuyến tính, tuy nhiên các biến trong bài toán đều là các biến nguyên nhị phân, nếu chúng ta giải quyết bài toán theo phương pháp quy hoạch tuyến tính để tìm ra nghiệm, sau đó làm tròn các nghiệm để được giá trị nguyên, phương pháp làm tròn tìm ra lời giải rất xa so với lời giải thực tế, còn dùng phương pháp liệt kê tất cả các lời giải sau đó tìm ra lời giải tối ưu nhất thì dẫn đến việc bùng nổ tổ hợp. Một giải pháp được đề xuất là sử dụng giải thuật Branch and Bound để giải quyết bài toán, bước đầu đã đạt được những kết quả. Do module mua cũng là một module đơn trong phần mềm, và các module tích hợp được tích hợp từ các module đơn. Do đó, với việc giải quyết bài toán tối ưu hoá các module mua, chúng ta đã tìm được độ tin cậy và chi phí cho các module mua. Kết quả sẽ được đưa vào để giải quyết bài toán tối ưu hoá các module phát triển trong công ty. ƒ Đối với bài toán các module phát triển trong công ty, do cấu trúc bài toán hàm mục tiêu là một hàm nhiều biến, lại liên quan đến hàm số mũ. Cho nên để thực hiện được bài toán ta sử dụng phương pháp quy hoạch phi tuyến để giải quyết, thông qua đây ta cũng tìm được độ tin cậy và chi phí cho từng module trong phần mềm cũng như độ tin cậy của phần mềm. Tuy nhiên, để đảm bảo bài toán tìm được lời giải tối ưu nhất, chúng ta cần phải xem xét nguồn chi phí cung cấp có đủ để phát triển phần mềm chưa, cũng như việc phân chia chi phí giữa các module mua và module phát triển trong công ty có hợp lý chưa, và các thông số nhập vào có đảm bảo phần mềm có độ tin cậy thoả mãn không. Đây là các vấn đề bài toán A trong chương 5 sẽ giải quyết. Một vấn đề khác nhà quản lý đặc ra, với độ tin cậy độ đã định trước, tìm chi phí nhỏ nhất ứng với độ tin cậy đã cho. Đây là một bài toán ngược với bài toán A. Để thực hiện được vấn đề này, các công việc sau đây cần giải quyết: ƒ Đối với các module mua các verion của các module mua có độ tin cậy và chi phí là một hằng số xác định trước. Vì vậy, công việc tìm độ tin cậy của các module này cũng được thực hiện giống như bài toán A. Nghĩa là ta sẽ cho trước chi phí để mua các module và từ đó tìm ra độ tin cậy ứng với chi phí đó. Tương tự như trên kết quả độ tin cậy của các module mua sẽ được đưa vào để giải quyết bài toán tối ưu hoá các module phát triển trong công ty. ƒ Đối với các module phát triển trong công ty, qua việc tìm chi phí nhỏ nhất để phần mềm có độ tin cậy là một hằng số cho trước ta cũng dùng phương pháp quy hoạch phi tuyến để giải quyết. Trong trường hợp này hàm mục tiêu là hàm chi phí và điều kiện ràng buộc là hàm độ tin cậy của phần mềm phải bằng một hằng số cho trước. Qua đây, chúng ta có thể tìm ra được chi phí nhỏ nhất của phần mềm, cũng như độ tin cậy và chi phí của từng module trong phần mềm. Tuy nhiên, công việc này nhiều lúc không dễ dàng thực hiện, do khi chúng ta phân phối chi phí cho các module mua quá ít, làm cho độ tin cậy của các module này cũng nhỏ theo, kết quả làm ảnh hưởng đến độ tin cậy phần mềm, hoặc các thông số đầu vào của các module phần mềm cũng gây ảnh hưởng không nhỏ đến quá trình xác định này. Đây là một vấn đề cũng không kém phần quan trọng, và sẽ được giải quyết trong bài toán B của chương 5. 1.3. Kết cấu của luận văn Luận văn bao gồm 6 chương. Chương 1. Giới thiệu Chương này trình bày bối cảnh, mục tiêu và kết quả thu được của luận văn. Chương 2. Các mô hình phân phối chi phí cho độ tin cậy phần mềm Chương này trình bày các khái niệm cơ bản về độ tin cậy phần mềm, cách tính độ tin của từng loại module trong phần mềm dựa vào chi phí, các phương pháp giải quyết bài toán phân phối chi phí cho độ tin cậy phần mềm. Chương 3. Phương pháp giải bài toán quy hoạch nguyên Chương này giới thiệu việc dùng giải thuật Branch and Bound để giải quyết bài toán quy hoạch nguyên. Chương 4. Phương pháp giải bài toán quy hoạch phi tuyến Chương này trình bày các định lý và giải thuật cho bài toán quy hoạch phi tuyến của hàm nhiều biến. Chương 5. Giải quyết bài toán Trên cơ sở lý thuyết đã trình bày về các phương pháp giải quyết bài toán quy hoạch nguyên và quy hoạch phi tuyến. Trong chương này sẽ trình giải pháp tiếp cận cũng như cách thực hiện bài toán phân phối chi phí cho độ tin cậy phần mềm. Thông qua việc giải quyết bài toán tìm độ tin cậy lớn nhất mà không vượt quá giới hạn ngân sách đã cho, và ngược lại, tìm chi phí nhỏ nhất để phần mềm có độ tin cậy là một hằng số cho trước. Chương 6. Kết quả, kết luận Chương này trình bày các kết quả đạt được của bài toán, đề cập lại những việc đã thực hiện được của đề tài. Nêu lên hướng mở rộng và phát triển tiếp theo cho đề tài. Chương 2. Các Mô Hình Phân Phối Chi Phí Cho Độ Tin Cậy Phần Mềm Chương này trình bày định nghĩa về độ tin cậy phần mềm, cách tính độ tin cậy của các module trong phần mềm, các mô hình phân phối chi phí cho độ tin cậy phần mềm [7]. 2.1. Giới thiệu Độ tin cậy [3] của một hệ thống phần mềm được định nghĩa là xác suất của sự thành công. Được thực hiện bằng cách đo hoạt động phần mềm trong một đơn vị thời gian, trong một môi trường nhất định. Đây là một thuộc tính của chất lượng phần mềm, bao gồm các nhân tố như: sự toại nguyện của khách hàng, tính tiện lợi, sự thực thi phần mềm, tính có ích, khả năng công việc . . 2.2. Phân loại các module trong phần mềm Trong nghiên cứu này, chúng ta xem cấu trúc của một phần mềm được tổ chức các module theo cấu trúc cây phân cấp và chúng ta sẽ tính toán độ tin cậy của phần mềm theo cấu trúc cây phân cấp. Chúng ta giả định các module trong phần mềm được tồn tại dưới hai dạng: module đơn và module tích hợp. ƒ Module đơn là module được tạo ra từ chính nó. Module này có thể được module mua từ bên ngoài thị trường và cũng có thể module được phát triển trong công ty. ƒ Module tích hợp là một module được phát triển trong công ty. Module tích hợp được tạo thành từ nhiều module đơn, hoặc có thể từ các module đơn và module tích hợp khác. Với lý do phân bổ nguồn tài nguyên hợp lý để tạo ra phần mềm có tính tin cậy cao mà tiết kiệm được chi phí. Dựa vào nguồn lực hiện có của công ty, nhà quản lý quyết định phần module nào sẽ được phát triển trong công ty, phần nào sẽ mua, và phần nào sẽ dùng lại. ƒ Một module được xem thích hợp để phát triển trong công ty khi trong công ty có đầy đủ điều kiện để phát triển và việc triển trong công ty có thể sẽ tiết kiện hơn so với việc mua từ bên ngoài. Loại module này bao gồm module đơn và module tích hợp. ƒ Một module được xem thích hợp để mua khi có nhiều version trên thị trường và trong công ty có thể không có đầy đủ điều kiện để phát triển hoặc chi phí để mua có thể tiết kiệm hơn so với việc phát triển trong công ty. Loại module này là module đơn. ƒ Một module được xem thích hợp dùng lại khi trong công ty đã có sẳn (do trong công ty phát triển hoặc đã mua trước đó) và việc dùng lại này rõ ràng không tốn chi phí nào. Vấn đề chính trong bài toán này là phân phối chi phí cho độ tin cậy phần mềm. Do đó, chúng ta chỉ xem xét các mô hình phát triển phần mềm chỉ bao gồm các module mua và các module phát triển trong công ty, còn phần module dùng lại do không có sự tham gia của nhân tố chi phí cho nên chúng ta sẽ không được xét đến. 2.3. Mô hình quyết định trước Nhiệm vụ của mô hình quyết định trước là xác định trước một module sẽ được mua hoặc được phát triển trong công ty. Giả sử trong phần mềm có n module chúng ta có thể phân theo các dạng sau: ƒ Các module từ 1, 2, . . m1 là các module đơn và các module từ m1+1, . . . , n là các tích hợp. ƒ Các module từ 1, 2, . . , m là các module mua và còn lại m+ 1, . . . , n là được phát triển trong công ty. 2.3.1. Độ tin cậy của một module đơn phát triển trong công ty i Giả sử x(0) là chi phí khởi tạo cho việc phát triển module i trong công ty, và ứng i với chi phí này ta có độ tin cậy khởi tạo r (0) . Nếu chúng ta cung cấp chi phí nhỏ hơn chi phí khởi tạo thì độ tin cậy của module được xem bằng không. Độ tin cậy của một module sẽ tăng dần và tỷ lệ thuận với việc phân phối chi phí. Độ tin cậy tối đa có thể đạt được cho module i là  i r (max) . Thường chúng ta cho rằng độ tin cậy  i r (max) = 1 . Nhưng với mức độ đúng đắn 100% rất khó xẩy ra, do đó bằng 1. (max) r i là một giá trị nhỏ hơn hoặc Dựa vào các nhận định trên, chúng ta chọn cách mô tả độ tin cậy của một module đơn được phát triển trong công ty với hàm số mũ âm, vì với hàm này phù hợp với mô hình tăng tưởng độ tin cậy dựa vào việc phân phối chi phí (xem hình 2.1). Mô hình độ tin cậy của một module đơn như sau: Độ tin cậy của một module i là ri: (2.1) trong đó là một thông số phản ảnh độ nhạy của độ tin cậy của module mỗi khi có sự thay đổi chi phí. Giá trị lớn sẽ tác động đến việc thay đổi chi phí . Do đó khi thì và khi thì . Hình 2.1 dưới đây biểu diễn hàm độ tin cậy của công thức (2.1). Cho , , và . Trong trường hợp này, độ tin cậy là 0 khi chi phí nhỏ hơn 100, và 0.3 khi chi phí bằng 100. Độ tin cậy khi đó tăng lên cho đến khi đạt giá trị lớn nhất là 0.9 khi  xi → ∞ . 100 Hình 2.1: Độ tin cậy của một module phần mềm 2.3.2. Độ tin cậy của một module mua Mỗi module i trong tập hợp các module mua được giả định có ni trường ().  version trên thị Cho yij là một biến nhị phân biểu thị cho việc mua hay không mua version thứ j của module i . Nếu yij = 1 thì version j của module i được mua, ngược lại yij = 0 thì version j của module i không được mua. Với mục tiêu của mô hình là cực đại hóa độ tin cậy của phần mềm được ràng buộc trên tổng ngân sách đã cho (B). Do đó, để tiết kiệm chi phí mỗi module mua chỉ mua duy nhất một version trên thị trường, chúng ta cần điều kiện sau ni ∑ yij = 1, với bất kỳ mudule mua. Khi đó ta có độ tin cậy của j =1 module mua i là ri : ni ri = ∑ rij yij j =1 và chi phí để mua module i là:  (2.2) ni ci = ∑ cij yij j =1 2.3.3. Độ tin cậy của một module tích hợp Cho các module i1, i2, . . . , is là các module tạo thành module Ti. Ta gọi module Ti là một module tích hợp. Độ tin cậy của một module tích hợp Ti phụ thuộc vào độ tin cậy của các module con của Ti. Cho  ( m ) r Ti  là độ tin cậy lớn nhất có thể đạt được của module tích hợp  Ti . Giả sử việc thực thi chương trình của các module con là theo một trình tự và không có sự phụ thuộc lẫn nhau. Do đó độ tin cậy tối đa có thể đạt được của module Ti  được tính theo s công thức (max) r Ti = ∏k =1 ri . Tuy nhiên, trong quá trình tích hợp các module con có thể xẩy ra những lỗi do có sự không tương thích giữa các module với nhau. Do đó, gọi ( 0) r Ti là độ tin cậy nhỏ nhất có thể có của module Ti (có thể nhỏ hơn hoặc bằng r (max) ). Cho T i q (0 < q ≤ 1) là một hệ số phản ánh sự tương thích giữa các module. Vì vậy Ti Ti T ∏ i T T ( 0) s (max) T r = q r = q r . i i k =1 i i Tương tự như một module đơn được phát triển trong công ty. Ta có thể sử dụng hàm số mũ để mô tả độ tin cậy của một module tích hợp. Độ tin cậy của một module tích hợp Ti là: r (max) R = T  − ((r (max)  − r (0) )e−á ( x − x ( 0 ) ) x ≥ x( 0)  (2.3) T ⎨ i i ⎪⎩ i i i T T i i i i i i 0 x < x(0) ⎪⎬⎭ trong đó ái , xi và (0) x i đã được định nghĩa trong phần trước. Công thức độ tin cậy phần mềm () phụ thuộc vào cấu trúc của phần mềm: ƒ Nếu phần mềm chỉ là một module đơn thì là bằng độ tin cậy của module đó. ƒ Nếu phần mềm chỉ là một module được phát triển trong công ty thì công thức độ tin cậy là công thức (2.1). ƒ Nếu phần mềm chỉ là một mudule mua thì công thức độ tin cậy là công thức (2.2). ƒ Nếu phần mềm là một hệ thống có nhiều hơn một module thì module gốc phải là một module tích hợp và độ tin cậy phần mềm phụ thuộc vào độ tin cậy của các module con. Công thức tính đ._.ộ tin cậy phần mềm là công thức (2.3). Khi một số module con là các module tích hợp, công thức độ tin cậy của các con phải được tính trước. Một thủ tục đệ quy có thể sử dụng để tính toán . Hình 2.2 biểu diễn một hệ thống phần mềm chứa 6 module. Index-generator(3) và Analyzer(4) là 2 module được phát triển trong công ty và công thức độ tin cậy là công thức (2.1) (xem r3 và r4 trong phần 5). Parse(1) và Stemmer(2) là 2 module mua và công thức độ tin cậy là công thức (2.2) (xem r1 và r2 trong phần 5). Công thức độ tin cậy của module tích hợp (công thức (2.3)) được sử dụng cho Keyword(5) (xem r5 trong phần 5). Một công thức cho mọi module con của module gốc Database-index(6) được xác định trước thông qua công thức (2.3) và đây cũng là công thức tính độ tin cậy phần mềm () (xem r6 trong phần ví dụ 2.1). Database-indexing (6) Parser (1) Keyword (5) Index-generator (3) Version 11 Analyzer (4) Stemmer (2) Version 12  Version 21 Version 22  Module tích hợp Module mua Module phát triển Hình 2.2: Một hệ thống databate-indexing Bài toán (P) có thể viết: Max (P1) S.T. m ni n ∑∑ cij yij + ∑ xi ≤ B (P2) i =1 j =1 i = m1 +1 ni ∑ yij = 1 j =1  với i=1,2, . . . ,m (P3) i i x ≥ x(0)  với i=m +1, . . . ,n và yij =0,1 với i=1, . . . ,m và j=1, . . . ,ni (P4) ƒ Mục tiêu (P1) là cực đại hoá độ tin cậy của hệ thống . ƒ (P2) đảm bảo tổng chi phí sử dụng không vượt quá ngân sách cho phép. ƒ P(3) chắc chắn sẽ có duy nhất một version được module i mua, với i = 1,2,..., m. ƒ (P4) bảo đảm các module phát triển trong công ty đều có độ tin cậy lớn hơn không và toàn bộ yij là nhị phân. Công thức phụ thuộc vào độ tin cậy của hầu hết các module và bằng không nếu có bất kỳ một module nào trong phần mềm có độ tin cậy bằng không. Độ tin cậy của một modude mua là độ tin cậy của version được lựa chọn. Độ tin cậy của module i được phát triển trong công ty sẽ lớn hơn không nếu x ≥ x( 0) . Vì vậy, để độ tin cậy i i i phần mềm lớn hơn không thì mỗi module mua phải lựa chọn mua một version và chi phí cung cấp cho các module phát triển trong công ty phải thoả mãn điều kiện xi > x (0) . Ví dụ 2.1: Trong ví dụ này, chúng ta sẽ làm sáng tỏ những vấn đề được nêu ở trên. Sự thực hiện đầy đủ của một database-indexing bao gồm các module (xem hình 2.2): ƒ Parser(1) và Stemmer(2) là các module mua. Mỗi module mua có 2 version. ƒ Index-generator(3) và Analyzer(4) là hai module đơn. ƒ Keyword(5) là module tích hợp từ hai module Analyzer(4) và Stemmer(2). ƒ Database-indexing task(6) là module tích hợp từ ba module Keywork(5) với Index-generator(3) và Parter(1). Các số ngẫu nhiên được chọn cho ví dụ: r11 = 0.7, c11 = 5 r12 = 0.9, c12 = 6 r21 = 0.87, c21 = 7 r22 = 0.95, c22 = 8 r ( m ) = 0.83, r ( 0) = 0.53,á = 0.3, x(0) = 2 3 3 3 3 r ( m ) = 0.9, r ( 0) = 0.5,á  = 0.4, x(0) = 3.5 0 4 q5 = 0.7,á5 q6 = 0.8,á6 4 4 5 = 0.25, x( 0) = 4 0 6 = 0.3, x(0) = 3 Để tính toán độ tin cậy của hệ thống, đầu tiên chúng ta tính độ tin cậy của các module mua (1) và (2) và các module đơn (3) và (4). r1 = r11 y11+r12 y12 r2 = r21 y 21+r22 y22 ⎧0.83 − (0.83 − 0.53)e− 0.3( x3 − 2) 3 r = ⎨ x3 ≥ 2 ⎩ 0 Otherwise ⎧0.9 − (0.9 − 0.5)e− 0.4( x4 −3.5) r = ⎨ x4 ≥ 3.5 4 ⎩ 0 Otherwise Độ tin cậy của module tích hợp Keyword(5) là: ⎧r ( m ) − (r ( m ) − r (0) )e−0.25( x6 −3) x ≥ 4 5 r = ⎨ 5 m 5 5 ⎩ 0 5 Otherwise r trong đó  ( m ) 5  = r2 r4  r 5 và (0)  5 = 0.8r ( m ) là độ tin cậy của module tích hợp Database-indexing (6) ⎧r ( m ) − (r ( m ) − r (0) )e−0.3( x6 − 3) x ≥ 4 6 r = ⎨ 6 m 6 6 ⎩ 0 6 Otherwise 6 khi đó r ( m )  1 5 3 6 = r r r và r (0)  6 = 0.8r ( m ) Bài toán là: max S.T. c11 y11 + c12 y12 + c21 y21 + c22 y22 + x3 + x4 + x5 + x6 ≤ B y11 + y12 = 1 y21 + y22 = 1 i i x ≥ x(0) , i = 3,4,5,6 , y11 , y12 , y21 , y22 = 0,1 Thông qua việc sử dụng hàm Solver của phần mềm Microsoft Excel. Sau khi giải bài toán ta thu được các kết quả sau: B y11 y12 y21 y22 x3 x4 x5 x6 Độ tin cậy Tối ưu 25 1 0 1 0 2 4 4 3 0.11826 26 0 1 1 0 2 4 4 3 0.15205 30 0 1 0 1 3.3816 5.6183 4 3 0.2518 35 0 1 0 1 5.1168 6.9833 4.7556 4.1441 0.3491 40 0 1 0 1 6.3842 7.9627 6.2414 5.4115 0.4269 45 0 1 0 1 7.6511 8.9325 7.7371 6.6785 0.4870 50 0 1 0 1 8.9178 9.8958 9.2410 9.9452 0.5316 55 0 1 0 1 10.1842 10.8547 10.7494 9.2116 0.5639 60 0 1 0 1 11.4505 11.8105 12.2610 10.4778 0.5868 70 0 1 0 1 13.9826 13.7167 15.2906 13.0099 0.6140 80 0 1 0 1 16.5145 15.6189 18.3246 15.5418 0.6270 100 0 1 0 1 21.5779 19.4188 24.3978 20.6053 0.6361 150 0 1 0 1 34.2205 28.9238 39.5821 33.2734 0.63863 200 0 1 0 1 46.7863 37.8185 56.3336 45.0614 0.63868 Bảng 2.1: Giải pháp cho những nguồn ngân sách khác nhau 2.4. Mô hình tổng quát Giả sử trong phần mềm tồn tại n module và các module này có thể được mua ở bên ngoài thị trường hoặc được phát triển trong công ty. Cho zi là một biến nhị phân, khi zi = 1 thì module i là được phát triển trong công ty, ngược lại nếu zi = 0 thì module i được mua từ bên ngoài. Số version của những module i được mua bên ngoài thị trường là ni và mỗi module mua chỉ mua một version trong số các version của module đó. Từ một module có thể được phát triển trong công ty hoặc được mua từ bên ngoài i ∑ ij i thị trường, ta có z + ni y =1. Gọi r là độ tin cậy của module i được phát triển trong j =1 công ty với chi chí xi, rij , cij là độ tin cậy và chi phí của một version j của module i. Do đó, đối với bất kỳ một module phần mềm i nào có độ tin cậy Ri được cho bởi: ni Ri = ri zi + ∑ rij yij j =1 Tương tự, gọi Ci là chi phí để thực hiện một module module i: ni Ci = xi zi + ∑ cij yij j =1 Trong trường hợp này bài toán được phát biểu như sau: Max (GP1) S.T. n ni n ∑∑ cij yij + ∑ xi zi ≤ B (GP2) i =1 j =1 i =1 ni zi + ∑ yij = 1 với i = 1,2,…, n j =1  (GP3) trong đó: zi , yij = 0,1 với i = 1,…, n ; j = 1,…, ni (GP4) ƒ (GP1) cực đại hoá độ tin cậy. ƒ (GP2) đảm bảo tổng các khoảng chi tiêu là không vượt ngân sách. ƒ (GP3) đảm bảo có đúng một module i được phát triển trong công ty hoặc có duy nhất một version được mua trên thị trường cho module i. ƒ (GP4) đảm bảo các biến  yij , zi là các biến nhị phân. Chương 3. Phương Pháp Giải Bài Toán Quy Hoạch Nguyên Chương này giới thiệu các lý do để thực hiện bài toán quy hoạch nguyên, các phương pháp để giải quyết bài toán quy hoạch nguyên, giải thuật để thực hiện cho bài toán nguyên nhị phân. 3.1. Giới thiệu Bài toán quy hoạch nguyên [2] là một bài toán quy hoạch tuyến tính mà ràng buộc thêm điều kiện các biến có giá trị nguyên. Biến nhị phân cũng là một tập con của biến nguyên. Trong đó, biến nhị phân chỉ nhận giá trị nguyên: 0 hoặc 1. Biến nhị phân thường được sử dụng trong các bài toán ra quyết định, dùng để quyết định thực hiện hay không thực hiện một công việc nào đó. Bài toán quy hoạch nguyên chứa các biến nhị phân được gọi là Binary integer programming (BIP). 3.2. Sự cần thiết của bài toán quy hoạch nguyên Giả sử có một bài toán phân công công việc của các nhân viên trong một tổ dự án. Lời giải có nghiệm tối ưu nhất là 7.3 người. Tuy nhiên, bạn không thể phân công xé lẻ số người trong một dự án được. Bạn chỉ có thể phân công 6 hoặc 7 hoặc 8 người. Có một sự ràng buộc mà bạn không thể giải quyết bài toán theo phương pháp quy hoạch tuyến tính là làm tròn bất kỳ giá trị nào để nó tiến đến giá trị nguyên. Ví dụ sau trình bày lý do tại sao bạn không thể làm tròn các biến: Ví dụ 3.1: Xét bài toán sau: Hàm mục tiêu: Maximize Z = x1 + 5x2 với các điều kiện ràng buộc: x1 + 10x2 ≤ 20 x1 ≤ 2 x1 , x2 ≥ 0 và x1 , x2 là các biến nhị phân. 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 Nếu giải bài toán bằng phương pháp quy hoạch tuyến tính, bạn sẽ nhận được giá trị tối ưu Z=11 với  x1 = 2, x2 = 1.8 . Theo huynh hướng tự nhiên bạn sẽ làm tròn  x2 để nó tiến về giá trị nguyên. Trong trường hợp này ta có thể làm tròn x2 = 2 . Tuy nhiên, khi ta làm tròn như vậy ta thu được cặp nghiệm  x1 = 2, x2 = 2 không thoả mãn điều kiện ràng buộc đầu tiên. Tất nhiên khi đó nếu chúng là làm tròn  x2 theo chiều ngược lại x2 = 1ta được:  Z = 7 , và  x1 = 2, x2 = 1  thoả các điều kiện ràng buộc, nhưng không là nghiệm tối ưu. Nghiệm tối ưu khi  x1 = 0, x2 = 2 và hàm mục tiêu  Z = 10 . Hình 3.1 trình bày bản tóm tắt của bài toán. Các dấu chấm trong hình 3.1 trình bày các điểm mà x1 , x2 có giá trị nguyên. 3.3. Phương pháp giải quyết bài toán quy hoạch nguyên Đầu tiên bạn nghĩ ngay một cách đơn giải để giải bài toán này là liệt kê toàn bộ các lời giải và sau đó là lựa chọn lời giải có nghiệm tối ưu nhất. Công việc này chỉ được thực hiện cho những bài toán nhỏ, nhưng điều đó rất nhanh chóng không thực hiện được cho những bài toán có kích thước từ trung bình hoặc lớn. Ví dụ 3.2: xét liệt kê đầy đủ của một mô hình tổng quát có một biến nguyên  x1 và hai biến nhị phân  x2 và  x3 với các ràng buộc: 1 ≤ x1 ≤ 3 0 ≤ x2 ≤ 1 0 ≤ x3 ≤ 1 Cấu trúc trong hình 3.2 là một cây với nút gốc bên trái, được gán nhãn “all solution” và các nút lá nằm bên phải. Các nút lá mô tả các giải pháp có được, vì vậy chúng ta có 12 giải pháp trong đó có: (3 giá trị có thể thực hiện được cho x1 )*(2 giá trị có thể thực hiện được cho  x2 )*(2 giá trị có thể thực hiện được cho  x3 ) Tương tự, nếu xét bài toán nhị phân có 20 biến. Điều đó có nghĩa là sẽ có 220 = 1,048,576  giải pháp được thực hiện bằng phương pháp liệt kê, công việc này phải được thực hiện bằng máy tính. Nhưng nếu chúng ta xét một trường hợp giải sử có 100 biến nhị phân khi đó chúng ta cần đến  2100 = 1.268x1030  giải pháp được thực hiện bằng phương pháp liệt kê. Do do, nếu ta đưa ra bài toán có n biến theo lý thuyết sẽ có 2n phương pháp có thể được xét đến. Vấn đề là khi n chỉ cần tăng 1 thì số phương pháp tăng lên gấp đôi, như vậy độ phức tạp là tăng tưởng theo hàm số mũ, vấn đề này là bất khả thi đối với máy tính. Sự bùng nổ tổ hợp sẽ xấu hơn cho các biến nguyên có thể nhận nhiều giá trị hơn biến nhị phân (chỉ có 2 giá trị 0/1). Điều này xét về mặt tính toán là bất khả thi với máy tính. Trong thực tế, số biến của một bài toán có thể là rất lớn. Do đó, phương pháp liệt kê sẽ không được thực hiện cho các bài toán có kích thước đủ lớn. Vì vậy, chúng ta cần một phương pháp tối ưu nhất giải quyết việc bùng nổ tổ hợp này. Hình 3.2: Một cây liệt kê đầy đủ Chúng ta nhận thấy, khác với bài toán quy hoạch tuyến tính, bài toán IP có thể chỉ có vài đáp án khả thi khi các biến buộc phải có giá trị nguyên, do đó độ phức tạp khi giải quyết bài toán này có khả năng rất lớn khi mà số đáp án là hữu hạn trong một vùng khả thi nào đó. Điểm khác biệt quan trọng giữa bài toán quy hoạch tuyến tính và bài toán quy hoạch nguyên: ƒ Bài toán quy hoạch tuyến tính số lượng hàm ràng buộc là chính yếu quyết định độ phức tạp của bài toán. ƒ Bài toán quy hoạch nguyên số lượng biến và các cấu trúc đặc biệt (special structure). Chính các cấu trúc đặc biệt này có thể là chìa khóa để đơn giản hóa vấn đề. Bài toán IP thường có kích thước rất lớn và phương pháp đã được đề nghị để giải quyết là giải thuật branch and bound (B&B). Điều này đã được chứng minh là rất hiệu quả với các bài toán lớn dù không phải lúc nào thuật toán này cũng cho ra lời giải tối ưu. Ý tưởng cơ bản trong phương pháp B&B là ngăn ngừa khả năng tăng tưởng trên toàn bộ cây. Bởi vì, việc tăng tưởng trên toàn bộ cây là quá lớn so với bài toán thực tế. Thay vì vậy, B&B sẽ giải quyết bài toán tăng tưởng theo từng giai đoạn và sự tăng tưởng này chỉ được quan tâm đến những nút nào có đầy hứa hẹn ở bất kỳ giai đoạn nào. Nó được xác định bởi nút có nhiều hứa hẹn bằng cách đánh giá một bound trên giá trị tốt nhất của hàm mục tiêu mà có thể đạt được bằng việc tăng tưởng các nút ở giai đoạn sau đó. Tên phương pháp bắt nguồn từ việc phân nhánh (branching) xẩy ra, khi một nút được lựa chọn để phát triển xa hơn và sự phát sinh các con của nút đó. Sự giới hạn (bounding) căn cứ vào giá trị tốt nhất đạt được bằng cách tăng tưởng một nút đã được đánh giá. Chúng ta hi vọng rằng cuối cùng sẽ có một sự tăng tưởng nhỏ nhất trên toàn bộ cây liệt kê. Thêm một điều quan trọng nữa là hướng của phương pháp là pruning, trong đó bạn sẽ loại bỏ và thường xuyên loại bỏ các nút sẽ không bao giờ thoả mãn hoặc cho nghiệm tối ưu. Quan điểm này xuất phát từ nghề làm vườn, trong đó pruning nghĩa là cắt bỏ nhánh trên một cây. Pruning là một vấn đề quan trọng của B&B từ đó nó cẩn thận ngăn ngừa sự tăng tưởng của cây trong vấn đề tìm kiếm. 3.4. Phương pháp giải quyết bài toán quy hoạch nguyên nhị phân Trong bài toán nhị phân, mỗi biến chỉ có thể nhận giá trị 0 hoặc 1. Điều đó có thể mô tả sự chọn lọc hay loại bỏ một vật nào đó, bật hoặc tắc một công tắc điện, quyết định thực hiện hay không thực hiện một công việc nào đó .v.v. Chúng ta sẽ nghiên cứu một giải thuật B&B để giải quyết bài toán này [1]. Yêu cầu bài toán cụ thể như sau: Hàm mục tiêu có dạng: Minimize f ( x) = cx với các điều kiện ràng buộc có dạng: A.x ≤ b x = 0or1  (3.1) (3.1a) (3.1b) Từ các điều kiện ràng buộc (3.1a,b), vùng khả thi ban đầu của hàm mục tiêu là S 0 = {x : Ax ≤ b và x là biến nhị phân. Ta cho một đường  Pk đi từ  v0 đến  vk . Tại  vk được xác định bằng việc lựa chọn một biến tự do x j sao cho: j {S k ∩ {x : x  j = 0}, S k ∩ {x : x = 1}}  (3.2) Mỗi đường Pk tương ứng với một sự ấn định của những giá trị nhị phân đến một tập con của những biến. Sự ấn định này được gọi là một nghiệm riêng. Chúng ta biểu thị sự ràng buộc các chỉ số của những biến được gán bởi Wk ⊆ N  và giả sử S + k = { j : j ∈Wk và x j = 1} S − k = { j : j ∈Wk và x j = 0} S 0 = { j : j ∉W } k k Một sự hoàn thành Wk  là một sự ấn định của những biến nhị phân đến những k biến tự do được chỉ rõ bởi chỉ số được đặt trong Bounds: Bài toán được xét tại vk : min f ( x) = ∑ c j x j + ∑ c j S 0 . k k j∈S 0 j∈S + điều kiện ràng buộc: ∑ aij x j ≤ bi − ∑ aij = si i = 1,…, m  (3.3) k j∈S 0 j∈S + k k x j = 0 or1, j ∈ S 0 j Giả sử T k = {x : x  = 0 or1,  k 0 k j ∈ S 0 }. Vì  c IP c j ≥ 0 , giải pháp nới lỏng  xk đạt được bằng việc thiết lập x j = 0, j ∈ Sk . Như vậy k . Hơn nữa, nếu =f = ∑ j∈S + j k s = (s1 ,…, sm ) ≥ 0 thì xk thỏa mãn (3.3) và f = f k = ∑ j∈S + c j . Fathoming: node k có thể được thăm dò nếu: f k = f k (a) 0 f k ≥ f  k (b) Điều kiện (a) xẩy ra khi sử cho một số i thỏa: xk thỏa mãn (3.3). Một điều kiện đủ để đánh giá (b) giả vậy  k ti = ∑ min{0, aij } > si j∈S 0 Trong trường hợp không có sự hoàn thành của Wk có thể thỏa mãn ràng buộc i, vì k f k = ∞ , và v được thăm dò. Ví dụ, xét ràng buộc: ∑ aij x j = −5x1 + 4 x2 + 2 x3 − 3x4 ≤ −11 = si ∈ 0 j S k Tính toán cho ti = −8 > si = −11 vì vậy node k được thăm dò. Partitioning and Branching: chúng ta muốn xác định tập con của những biến tự do tại vk của nó ít nhất phải bằng 1 trong một sự khả thi của Wk . Cho Qk = {i : si < 0} . k Nếu Qk = ö , thì vk được thăm dò vì xk khả thi. Nếu Q ≠ ö , cho k k R = { j : j ∈ S 0 và aij < 0 với i ∈ Qk } Có ít nhất một biến có chỉ số là một phần tử của Rk bằng 1 trong bất kỳ sự khả thi của Wk . Vì vậy, chúng ta có thể phân chia trên một số x j , j ∈ Rk , và sau đó phân nhánh nút kế tiếp tương ứng x j = 1. Quy tắc sau đây lựa chọn một j ∈ Rk trong một sự nỗ lực để di chuyển về phía khả thi. Định nghĩa m i =1 i∈Qk khả thi cho bài (3.3). Việc chọn x j node kế thừa không khả thi I k = ∑ max{0,−si } = − ∑ si  không thoả m Ik ( j) = ∑ max{0,−si + aij } i =1 và xp được lựa chọn như sau: I k ( p) = min Ik ( j) j∈Rk Ví dụ nếu các ràng buộc tại vk là − 6 x1 − 2x2 + 2x3 ≤ −3 − 3x1 − 4x2 + x3 ≤ −2 7 x1 + 5x2 − 5x3 ≤ 4 thì Rk = {1,2}, I k (1) = 3, Ik (2) = 2 vì vậy x2 được chọn là biến được phân chia. Giải thuật: 0 0 Bước 1: (Khởi tạo) Tại v , S 0  = {1,…n}, f 0  0 k = −∞, f  0 = −∞ . Di chuyển sang bước 2. Bước 2: (Tính toán bounds) Tại vk cho =f = ∑ ∈ + c . Nếu si ≥ 0 với mọi i cho k j S k j 0 0 k k f = f k = f k và cho f = min{ f , f } . Di chuyển sang bước 3. IP Bước 3: (Thăm dò) Nếu ti > si for mọi i hoặc nếu f k = f hoặc nếu f k ≥ f thăm dò vk và di chuyển sang bước 4. Nếu có vk thì di chuyển sang bước 5. Bước 4: (Backtracking) nếu không có node nào tồn tại thì di chuyển sang bước 6. Ngược lại chọn nhánh gần nhất và di chuyển sang bước 2. Bước 5: (Phân chia và phân nhánh) Phân chia trên  x p như trong công thức (3.2), k trong đó I k ( p) = min j∈R Ik ( j) . Phân nhánh về phía x p . Di chuyển sang bước 2. Bước 6: (Kết thúc) Nếu 0 f = ∞  thì không có giải pháp khả thi. Nếu 0 f < ∞  thì có 0 một giải pháp khả thì và f là giá trị tối ưu. Ví dụ 3.4: Xét bài toán sau: Hàm mục tiêu: min f = 5 x1 + 7 x2 + 10 x3 + 3x4 + x5 với điều kiện ràng buộc: − x1 + 3x2 − 5x3 − x4 + 4 x5 ≤ −2 2 x1 − 6x2 + 3x3 + 2 x4 − 2 x5 ≤ 0 x2 − 2 x3 + 3x4 + x5 ≤ −1 x1,…, x5 = 0 or 1 0 + − 0 0 Bước 1: Ta có S0 = {1,…,5}, S0 = S0 = ö , f = −∞, f = ∞, s = (−2,0,−1); I0 = 3, và R0 = {1,3,4} .Vì toàn bộ các biến là tự do, chúng ta có thể di chuyển đến bước 5 và đánh giá I0 (1) = 4, I0 (3) = 3, I0 (4) = 5 . Cực tiểu được tìm thấy liên quan đến p = 3 vì vậy chúng tôi lựa chọn x3 cho vùng phân chia con và nhánh trong phương hướng của x3 = 1 . Cây được trình bày trong hình 3.3. 0 x3=1  x3=0 1 4 x2=1 x2=0 2 3 2 0 Hình 3.3 : Cây tìm kiếm cho ví dụ 3.2 Tại v1 , P1 = (3), f = 10, s = (3,−3,1), R1 = {2,5}, I1 (2) = 0, I1 (5) = 2 , vì vậy chúng ta chọn x2 cho việc phân chia. Không có giải pháp khả thi vì vậy f = ∞ . Tại v , P = (3,2), f 1 = 17 và s = (0,3,0) , vì vậy 2 0 2 f = 17. Chúng ta đưa vào f = f = 17 và 2 2 thăm dò v2 . Tại bước 4, tính toán tại v3 với P3 = (3,2), s = (3,−3,1) và R3 = {5} . Nhưng do t2 = −2 > s2 = −3 nên v3 được thăm dò và chúng ta quay về v4 . Tại v4 , P4 = (3), s = (−2,0,−1) và R4 = {1,4} . Nhưng do t3 = 0 > s3 = −1 cho nên v4 được thăm dò. Ở quan điểm này, không còn node nào cho nên chúng ta di chuyển sag bước 6 và kết thúc giải thuật. Giải pháp tối ưu  f IP = 17, x* = (0,1,1,0,0) . Chương 4. Phương Pháp Giải Bài Toán Quy Hoạch Phi Tuyến Chương này giới thiệu các lý thuyết cho các bài toán tối ưu hóa hàm nhiều biến với các dạng: không có điều kiện ràng buộc, các biến trong chương trình đều không âm, các điều kiện ràng buộc là các ràng buộc tuyến tính và phi tuyến [1][4]. 4.1. Giới thiệu Chúng ta sẽ nguyên cứu lý thuyết cho các chương trình toán học có dạng sau: Hàm mục tiêu: min f ( x) với các điều kiện ràng buộc: hi ( x) = 0, i = 1,.., m g j ( x) ≤ 0, j = 1,..q x ∈ D  (4.1) trong đó: ƒ f ( x) : là hàm mục tiêu. ƒ g j ( x) , thức. ƒ D ⊂ Rn hi ( x) các điều kiện ràng buộc là các bất đẳng thức, và các đẳng : miền xác định. ƒ x ∈ D  : thỏa mãn tất cả các ràng buộc gọi là nghiệm chấp nhận được. Nhiệm vụ của bài toán tìm một cực tiểu x để hàm mục tiêu đạt giá trị nhỏ nhất thỏa mãn điều kiện ràng buộc. Ví dụ 4.1.1: Những khái niệm cơ bản trên được minh họa bởi bài toán sao cho x ∈ R2 : Hàm mục tiêu: 2 min f ( x1, x2 ) = ( x1 − 3) với các điều kiện ràng buộc:  2 + ( x2 − 2) 1 1 2 1 2 g ( x , x ) = x2 − x − 3 ≤ 0 g ( x , x ) = x2 − 1 ≤ 0 2 1 2 2 g3 ( x1 , x2 ) = x1 ≥ 0 Vùng khả thi được mô tả trong hình 4.1. Bài toán tìm một điểm trong vùng khả thi sao cho f ( x1 , x2 ) đạt giá trị nhỏ nhất. Chú ý rằng điểm ( x1 , x2 ) thỏa mãn 2 2 ( x1 − 3) + ( x2 −2) =c đại diện cho một đường tròn với bán kính c và tâm là điểm (3,2). Vì chúng ta kỳ vọng giá trị nhỏ nhất là c, ta thấy đường tròn bán kính lớn cắt ngang vùng khả thi. Đường tròn thỏa mãn điều kiện có c= 2, chúng giao với vùng khả thi tại điểm (2,1) và đây là điểm cho lời giải tối ưu. Giá trị hàm mục tiêu.  f (2,1) = 2  là giá trị tương ứng của Hình 4.1: Một giải pháp hình học cho ví dụ 4.1.1 Ví dụ 4.1.2: Xét bài toán: Hàm mục tiêu: min f ( x1, x2 ) =| x1 − 2 | + | x2 − 2 | với các điều kiện ràng buộc: h ( x , x ) = x2 + x2 − 1 = 0 1 1 2 1 2 g ( x , x ) = x − x2 ≥ 0 1 1 2 1 2 Vùng khả thi là một cung của đường tròn nằm bên trong parabola. Bài toán tìm một điểm trong vùng khả thi sao cho f ( x1 , x2 ) đạt giá trị nhỏ nhất. Trong trường hợp này, không có điểm nào để cho hàm mục tiêu đạt giá trị nhỏ nhất. Hình 4.2: Một giải pháp hình học cho ví dụ 4.1.2 4.2. Những điều kiện tối ưu Định nghĩa 4.2.1: Một điểm x* ∈ D được gọi là cực tiểu địa phương của f qua D . Nếu có một lân cận å > 0 sao cho f ( x) ≥ f ( x*) với mọi x ∈ D trong khoảng å của x * (đó là x ∈ D và x − x * < å ) và x ≠ x * thì x * được gọi là điểm cực tiểu địa phương của f qua D . 4.3. Tính lồi của hàm nhiều biến 4.3.1. Tập lồi Một tập hợp  D ⊂ Rn là tập lồi nếu tập D chứa mọi đoạn thẳng nối hai điểm bất kỳ của tập đó. Vậy tập lồi được định nghĩa [4]: D là tập lồi  ⇔ X 1, X 2∈ D, ∀á ∈ (0,1), (1 − á ) X1 + áX 2 ∈ D Tập lồi nhỏ nhất chứa 3 điểm, A, B, C là tam giác đặc ABC. Trong không gian, tập lồi nhỏ nhất chứa 4 điểm A, B, C, D là tứ diện đặc ABCD. Các đa giác lồi, trong mặt phẳng, các đa diện trong không gian là các ví dụ về tập lồi. Các nửa mặt phẳng, các nửa không gian cũng là các tập lồi. 4.3.2. Định nghĩa hàm lồi Đối với hàm nhiều biến, lưu ý rằng ta chỉ có khái niệm lồi của hàm khi hàm xác định trên một tập lồi. Hàm nhiều biến  f ( x) xác định trên tập lồi D được gọi là một hàm lồi nếu với mọi M, N thuộc D và M ≠ N, với mọi á ∈ (0,1) thì ta đều có: (1 − á ) f (M ) + áf ( N ) ≥ f ((1 − á )M − áN ) 4.3.3. Đặc trưng của hàm lồi Hàm nhiều biến riêng cấp 2 liên tục.  f ( x)  xác định trên một tập lồi D. Giả sử  f ( x)  có các đạo hàm Nếu tại mọi điểm bằng 0:  ( x1, x2 ,…, xn ) thuộc D, với mọi  dx1, dx2 ,…, dxn không đồng thời ƒ d 2  f ( x1 , x2 ,…, xn ) ≥ 0 thì  f ( x) là hàm lồi trên D. ƒ d 2 f ( x1 , x2 ,…, xn ) > 0 thì f ( x) là hàm lồi ngặt D. Việc phân tích trực tiếp trên biểu thức vi phân cấp 2 để chứng minh d 2 f không đổi dấu là khó khả thi. Do đó phải dùng đến công cụ của đại số tuyến tính mà ta sẽ đề cập đến trong định lý sau. Định lý 4.3.1: Xét hàm n biến  f ( x)  xác định trên miền lồi D. Giả sử hàm f ( x) có các đạo hàm riêng cấp hai liên tục. x* ∈ D là một điểm dừng. Với mỗi x* ∈ D , gọi ma trận Hessian tại x * , ký hiệu F ( x*) là ma trận vuông cấp n có thành phần dòng i cột j là ∂ 2 f . ∂xi ∂x j Với mỗi k từ 1 đến n, gọi Fk ( x*) là định thức ma trận con có được từ ma trận H ( x*) bằng các lấy các phần tử ở k dòng đầu và k cột đầu. Ta có điểm x * là cực tiểu của hàm f ( x) trên X nếu f ( x) là hàm lồi trên D. Điều kiện để f ( x) lồi trên D là với mọi x* ∈ D , ma trận F ( x*) xác định dương. Tức là với mọi x* ∈ D , với mọi k từ 1 đến n, ta đều có Fk ( x*) > 0 . Sau đây chúng ta sẽ nghiên cứu một số trường hợp cho bài toán tối ưu: 4.4. Các phương pháp giải bài toán quy hoạch phi tuyến 4.4.1. Giải bài toán tối ưu không có điều kiện ràng buộc Đây là trường hợp đơn giản nhất của bài toán tối ưu là không có điều kiện ràng buộc, có dạng sau: Hàm mục tiêu: min{ f ( x) :  x ∈ Rn } trong đó f : Rn → R1 . Cho x * được xem như một điểm và giả sử f hai lần đạo hàm liên tục trong lân cận Nå ( x*) của x * , trong đó x ∈ Nå ( x*) với f ( x) ≥ f ( x*) . Giả sử tồn tại một vectơ v , sao cho v = 1, ta có: 0 ≤ D f ( x*) = lim f ( x * +tv) − f ( x*) = ∇f ( x*)v v t →0 t Tiếp theo chúng ta xem xét những trường hợp ∂f ( x*) = 0 . Chúng ta có điều kiện cần thứ nhất: ∂x j  v = e j  và v = −e j nghĩa là ∇f ( x*) = 0 Chú ý: với mọi điểm x trong (4.6) Nå ( x*) có thể được mô tả dưới dạng  x = x * +tv trong đó t > 0 ( 0 < t < å vì t = x * +tv = x − x * ≤ å ). Chúng ta được: f ( x*) ≤  f ( x) =  f ( x * +tv) = f ( x*) + t∇f ( x*)v + t  vT F ( x * +átv)v  2 (4.7) 2 Gọi ma trận Hessian, ký hiệu F là ma trận vuông cấp n của f và á ∈ [0,1] . Nhưng ∇f ( x*) = 0 và t > 0 vì thế một điều kiện cần thứ hai cho f để có một cực tiểu tại  x * là 2 0 ≤ vT F ( x * +átv)v  (4.8) Định lý 4.4.1 Cho f : Rn → R1 hai lần đạo hàm liên tục xung quanh một lân cận 2 của x * . Nếu f có một cực tiểu tại x * thì: (i) (ii) ∇f ( x*) = 0 F ( x*) là một đại lượng xác định dương Định lý 4.4.2 Cho f : Rn → R1 hai lần đạo hàm liên tục xung quanh một lân cận của x * . Khi đó một điều kiện đủ để cho f ( x) có một cực tiểu tại x * , là ∇f ( x*) = 0 và F ( x*) là một đại lượng xác định dương. Ví dụ 4.4.1 Cho f : R2 → R1 được định nghĩa bởi f ( x) = 3x3 + x2 − 9 x + 4x . Tìm giá trị cực trị của hàm này. Lời giải: Bước 1: Tính ∇f ( x) = 0 1 2 1 2 Ta được ∇f ( x) = [0 0] = [9x2 − 9 2x2 + 4] Giải hệ phương trình trên thu được  1 x1 = ±1 và  x2 = −2 . Bước 2: Thực hiện kiểm tra từng trường hợp: ⎡18x1 0⎤ ⎡18 0⎤ ƒ x = (1,−2) ta được F (1,−2) = ⎢ 0 2⎥ = ⎢ 0 2⎥ là đại lượng xác định ⎣ ⎦ ⎣ ⎦ dương vì vT F (1,−2)v = 18v2 + v2 > 0 . Như vậy tại điểm (1, -2) là một điểm cực tiểu. 1 2 ⎡− 18x1 0⎤  ⎡− 18 0⎤ ƒ x = (−1,−2) ta được F (−1,−2) = ⎢ 0 2⎥ = ⎢ 0 2⎥ và khi đó ⎣ ⎦ ⎣ ⎦ 1 2 vT F (−1,−2)v = −18v2 + v2 có thể bằng 0 khi v ≠ 0 . Do đó điểm (-1,-2) không thỏa mãn điều kiện. Vậy điểm (1,-2) là một cực tiểu cần tìm. 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 Xét bài toán có dạng sau: min { f ( x) : x ≥ 0} (4.9) Giả thiết rằng f có một cực tiểu x * , trong đó x* ≥ 0 . Khi đó sẽ tồn tại một lân cận Nå ( x*) của x * , do đó với bất kỳ x ∈N å ( x*) có x ≥ 0 , thì f ( x) ≥ f ( x*). Ta có thể viết x = x * +tv , trong đó v là một vector và t > 0 . Giả sử f hai lần đạo hàm qua Nå ( x*) . Từ (4.7) ta có: 0 ≤ ∇f ( x*)v + t vT F ( x * +átv)v 2 Các điều kiện cần để f có một cực tiểu tại  x * : ∂f ( x*) = 0 nếu ∂x j ∂f ( x*) ≥ 0 nếu ∂x j  j x* > 0 j x* = 0 Chúng được tổng kết trong mệnh đề sau đây: Mệnh đề 4.4.1: Những điều kiện cần để hàm f có một cực tiểu tại điểm x * trong bài toán (4.9) bao gồm: ∇f ( x*) ≥ 0 ∇f ( x*)x* = 0 x* ≥ 0 Ví dụ 4.4.2: Xét bài toán Hàm mục tiêu: (4.10) 2 2 2 tiểu: Minimize f ( x) = 3x1 + x2 + x3 − 2x1 x2 − 2x1 x3 − 2x1 với các điều kiện ràng buộc: xi ≥ 0, i = 1,2,3 Lời giải: Từ công thức (4.10) chúng ta có những điều kiện cần thiết cho một cực ∂f (1) 0 ≤ ∂x1 = 6x1 − 2x2 − 2x3 − 2 (2) 0 = x ∂f 1 1 ∂x  = x1 (6x1 − 2x2 − 2x3 − 2) (3) 0 ≤ ∂f ∂x2  = 2x2 − 2 x1 (4) 0 = x2 ∂f ∂f ∂x2  = x2 (2x2 − 2x1 ) (5) 0 ≤  ∂x3 = 2 x3 − 2 x1 ∂f (6) 0 ≤ x3  ∂x3 = x3 (2x3 − 2 x1 ) (7) x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 Ta tìm được 1 điểm dừng x1 = x2 = x3 = 1 . Ma trận Hessian ở x* = (1,1,1) : ⎡6 − 2 − 2⎤ ⎢ ⎥ F (1,1,1) = ⎢ − 2 2 0 ⎥ là một đại lượng xác định dương. Do đó ta có một cực tiểu tại điểm x * . − 2 0 2 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 Cho  f : Rn → R1 và xét bài toán sau: Hàm mục tiêu:  Minimize f ( x) với các điều kiện ràng buộc: n h( x) = 0  (4.11) Trong đó h( x) = (h1 ( x),.., hm ( x)) , mỗi hi : R → R1 , và m < n . Để bài toán (4.11) có một cực tiểu tại x * . Khi đó phải tồn tại một å > 0 sao cho f ( x) ≥ f ( x*) với mỗi x ∈ Nå ( x*) và h( x) = 0 . Giả sử f ∈ C 2 tại mọi Nå ( x*) , và giả sử rằng mỗi ∂hi ( x) / ∂xi đạo hàm liên tục trong lân cận của x * . Tiếp theo, xây dựng một ma trận Jacobi có m hàng: ⎡ ∂h1 ( x*) ∂h1 ( x*) ⎤ ⎢ = ∂h( x*) ⎢ ∂x ⎢  ∂x1 # " ⎥ ∂xn ⎥ % # ⎥  (4.12) ⎢ ∂hm ( x*) " ∂hm ( x*) ⎥ 1 ⎢ ∂x ⎣ ∂x ⎥ n ⎦ Điều này tương ứng với việc cho rằng Định nghĩa 4.4.3: Cho một điểm x * là điểm dừng. x * thỏa mãn các điều kiện ràng buộc h( x*) = 0 được gọi là một điểm dừng, nếu các vector tuyến tính.  ∇h1 ( x*),..,∇hm ( x*)  là độc lập Định lý 4.4.3: Tại điểm T = { y : ∇h( x) y = 0} . x * của mặt S = {x : h( x) = 0} tiếp xúc với Để đơn giản quá cho các đối số sau đây chúng ta giả sử rằng đầu tiên m cột của công thức (4.12) là độc lập tuyến tính. Theo định lý hàm ẩn trong phần 4.1.3 m hàm, mỗi hàm có n biến đạo hàm liên tục, trong đó có thể giải cho m biến trong một lân cận của  m < n , với ma trận Jacobi có rank là m, x * dưới dạng còn lại n - m biến; ví dụ: xi = öi ( xm +1 ,.., xn ) với i = 1,.., m . Hơn nữa, các hàm öi là duy nhất và khả thi trong lân cận của x * . Cho x' = ( x1 ,.., xm ) và x" = ( xm +1 ,.., xn ) , ta có x' = (ö1 ( x" ),..,öm ( x" )) được ký hiệu ö ( x") . Công thức (4.11) được viết lại như sau: min { f ( x', x") = min f (ö ( x"), x") = min Ö( x") (4.13) trong đó ö ( x") = (ö ( x"), x")T . Vì thế bài toán ( 4.13) phải có một cực tiểu x"* = ( x* ,.., x* ) . Được tạo ra bởi định lý 4.2.1 là ∇Ö( x" ) = 0 . m +1 n  ⎡ ∂ö ⎤ n ∂Ö ∑ ∂f ∂x  m ∑ ∂f ∂ö  ∂f ⎡ ∂f ⎢ ∂x ⎥ ∂f ⎤ ⎢ j ⎥ Nhưng = i + i = + ⎢ ,.., ⎥ ⎢ # ⎥ ∂x j i = m +1 ∂xi ∂x j i =1 ∂xi ∂x j ∂x j ⎣ ∂x1 ∂xm ⎦ ⎢= ∂ö ⎥ 1 j m j ⎢ ∂x ⎥ ⎣ m ⎦ Do đó ∇f ( x' ) = [∂f / ∂x1 ,.., ∂f / ∂xm ], ∇f ( x") = [∂f / ∂xm +1 ,.., ∂f / ∂xn ] và ∂ö / ∂x" là một ma trận có kích thước đó ta được: m * (n − 1) bao gồm những cột có dạng [∂ö / ∂x ,.., ∂ö / ∂x ]T . Từ 0 = ∇Ö( x" ) = ∇f ( x" ) + ∇f ( x" ) ∂ö (4.14) ∂x" Ngoài ra 0 = h( x) = h(ö ( x"), x") . Vì thế: 0 = ∂h + ∂h ∂h  (4.15) ∂x" ∂x' ∂x" trong đó  ∂h / ∂x' và  ∂h / ∂x" là những matrận con đầu tiên có m hàng và n-1 cột của công thức (4.12). Từ công thức (4.16) ta có: −1 ∂ö ⎛ ∂h ⎞ ∂h = ⎜ ⎟ ∂x" ⎝ ∂x' ⎠ ∂x" Vì thế được tạo ra từ (4.14) điều đó: ∇f ( x" )T − ._., 15.16, 6.50, 6.00, 6.50, 8.00, 6.50, 6.90, 8.00, 7.28, 9.00, 10.00] [0.30, 0.93, 0.98, 0.50, 0.93, 0.86, 0.96, 0.94, 0.24, 0.22, 0.17, 0.89, 0.08, 0.80, 0.81, 0.75, 0.75] 0.55 250 35 0 0 0 1 0 1 0 0 1 0 0 0 1 [4.00, 16.23, 24.49, 7.00, 19.06, 20.23, 14.21, 18.50, 6.50, 6.00, 6.50, 9.31, 6.50, 11.09, 11.54, 11.67, 11.53, 10.64] [0.30, 0.96, 0.99, 0.50, 0.96, 0.89, 0.98, 0.96, 0.24, 0.22, 0.17, 0.93, 0.08, 0.89, 0.87, 0.86, 0.83] 0.71 300 35 0 0 0 1 0 1 0 0 1 0 0 0 1 [4.00, 17.80, 28.33, 7.00, 23.14, 26.21, 21.02, 20.11, 6.50, 6.00, 6.50, 16.52, 6.50,14.53, 15.69, 14.51, 5.29, 15.35] [0.30, 0.96, 0.99, 0.50, 0.97, 0.90, 0.99, 0.97, 0.24, 0.22, 0.17, 0.95, 0.08, 0.91, 0.89, 0.90, 0.85] 0.77 400 35 0 0 0 1 0 1 0 0 1 0 0 0 1 [4.00, 34.63, 49.65, 7.00, 29.58, 34.46, 19.64, 31.98, 6.50, 6.00, 6.50, 20.00, 6.50, 21.01, 23.57, 22.67, 22.33 18.97] [0.30, 0.96, 0.99, 0.50, 0.97, 0.90, 0.99, 0.97, 0.24, 0.22, 0.17, 0.95, 0.08, 0.92, 0.89, 0.91, 0.86] 0.7856 500 35 0 0 0 1 0 1 0 0 1 0 0 0 1 [4.00, 46.04, 62.22, 7.00, 35.48, 41.33, 23.38, 38.70, 6.50, 6.00, 6.50, 37.30, 6.50, 20.67, 32.59, 24.98, 33.11, 32.70] [0.30, 0.96, 0.99, 0.50, 0.97, 0.90, 0.99, 0.97, 0.24, 0.22, 0.17, 0.95, 0.08, 0.92, 0.89, 0.91, 0.86] 0.7882 Bảng 6.5: Kết quả chạy phần mềm có 22 module cho bài toán A Đối với bài toán B: Độ tin cậy phần mềm ( r22 ) B’ yij [ x5 ,…, x22 ] [r5 ,…, r21 ] Tổng chi phí (B) 0.0035 26 1 0 0 0 1 0 1 0 0 1 0 0 0 [4.00, 3.00, 5.00, 7.00, 8.00, 6.00, 5.00, 7.50, 6.50, 6.00, 6.50, 8.00, 6.50, 6.00, 8.00, 7.00, 9.00,10.00] [0.30, 0.56, 0.49, 0.50, 0.35, 0.55, 0.46, 0.35, 0.21, 0.13, 0.05, 0.27, 0.02, 0.09, 0.26, 0.04, 0.09] 135.00 0.1 35 0 0 0 1 0 1 0 0 1 0 0 0 1 [4.00, 4.20, 7.84, 7.00, 10.32, 6.34, 6.82, 9.77, 6.50, 6.00, 6.50, 8.00, 6.50, 6.00, 8.00, 7.00, 9.00, 30.33] [0.30, 0.71, 0.87, 0.50, 0.69, 0.58, 0.76, 0.72, 0.24, 0.22, 0.17, 0.61, 0.08, 0.40, 0.49, 0.29, 0.34] 154.78 0.2 35 0 0 0 1 0 1 0 0 1 0 0 0 1 [4.00, 5.21, 8.76, 7.00, 11.43, 7.77, 7.74, 10.78, 6.50, 6.00, 6.50, 8.00, 6.50, 6.00, 8.00, 7.00, 9.00, 38.21] [0.30, 0.79, 0.91, 0.50, 0.78, 0.68, 0.84, 0.80, 0.24, 0.22, 0.17, 0.71, 0.08, 0.53, 0.60, 0.42, 0.47] 161.19 0.3 35 0 0 0 1 0 1 0 0 1 0 0 0 1 [4.00, 6.15, 9.59, 7.00, 12.49, 9.17, 8.59, 11.72, 6.50, 6.00, 6.50, 8.00, 6.50, 6.00, 8.00, 7.00, 9.00, 38.66] [0.30, 0.85, 0.94, 0.50, 0.84, 0.74, 0.88, 0.86, 0.24, 0.22, 0.17, 0.78, 0.08, 0.62, 0.68, 0.53, 0.57] 167.23 0.5 35 0 0 0 1 0 1 0 0 1 0 0 0 1 [4.00, 8.59, 11.63, 7.00, 15.24, 12.89, 10.77, 14.16, 6.50, 6.00, 6.50, 8.00, 6.50, 6.00, 8.00, 7.00, 9.00, 43.05] [0.30, 0.92, 0.97, 0.50, 0.92, 0.84, 0.95, 0.93, 0.24, 0.22, 0.17, 0.87, 0.08, 0.76, 0.79, 0.70, 0.72] 182.78 0.7 35 0 0 0 1 0 1 0 0 1 0 0 0 1 [4.00, 12.54 14.84, 7.00, 19.75, 19.14, 14.30, 18.11, 6.50, 6.00, 6.50, 9.02, 6.50, 10.57, 11.01, 10.86, 10.85, 47.95] [0.30, 0.95, 0.98, 0.50, 0.96, 0.88, 0.98, 0.96, 0.24, 0.22, 0.17, 0.92, 0.08, 0.87, 0.86, 0.85, 0.82] 222.50 Bảng 6.6: Kết quả chạy phần mềm có 22 module cho bài toán B 6.2.8. Bài toán cho một phần mềm gồm có 37 module Giả sử ta cần phân phối chi phí cho độ tin cậy phần mềm của một bài toán có 30 module có cấu trúc như hình 6.3 M_3 M_35 M_36 M_32 M_19 M_20 M_33 M_21 M_34 M_22 M_29 M_15 M_16 M_30 M_17 M_31 M_18 M_11 M_26 M_12 M_27 M_13 M_14 M_28 M_1 M_23 M_9 M_24 M_10 M_4 M_25 M_2 M_6 M_3 M_7 M_8 M_5 V 11 V 12 V 13  V 21 V 22 V 23  V 31 V 32 V 33 V 34 V 51 V 51 V 52 V 52 V 53 Hình 6.3: Mô hình một phần mềm có 37 module Các thông số ngẫu nhiên được chọn cho bài toán: r11 = 0.77, c11 = 8; r12 = 0.8, c12 = 8.5; r13 = 0.85, c13 = 9; r21 = 0.76, c11 = 5.5; r22 = 0.89, c22 = 8; r23 = 0.94, c23 = 9; r31 = 0.8, c31 = 7; r32 = 0.84, c32 = 8.5; r33 = 0.89, c33 = 9; r34 = 0.95, c34 = 10; r41 = 0.81, c41 = 6; r42 = 0.86, c42 = 7; r43 = 0.9, c43 = 9; r51 = 0.83, c41 = 6.6; r52 = 0.96, c52 = 8; r (max) = 0.95, r (0) = 0.5,á = 0.35, x ( 0) = 4 6 6 6 6 r (max) = 0.98, r (0) = 0.3,á = 0.4, x ( 0) = 5 7 7 7 7 r (max) = 0.93, r (0) = 0.4,á = 0.3, x (0) = 7 8 8 8 8 r (max) = 0.97, r (0) = 0.3,á = 0.35, x (0) = 6 9 9 9 9 r (max) = 0.98, r (0) = 0.33,á = 0.25, x (0) = 8 10 10 10 10 r (max) = 0.96, r (0) = 0.4,á = 0.35, x(0) = 6 11 11 11 11 r (max) = 0.98, r ( 0) = 0.5,á = 0.35, x( 0) = 9 12 12 12 12 r (max) = 0.95, r ( 0) = 0.4,á = 0.3, x( 0) = 7 13 13 13 13 r (max) = 0.96, r (0) = 0.45,á = 0.4, x(0) = 8 14 14 14 14 r (max) = 0.96, r (0) = 0.4,á = 0.3, x(0) = 6 15 15 15 15 r (max) = 0.97, r (0) = 0.35,á = 0.36, x(0) = 9 16 16 16 16 r (max) = 0.96, r (0) = 0.4,á = 0.34, x(0) = 5 17 17 17 17 r (max) = 0.95, r ( 0) = 0.45,á = 0.35, x(0) = 8 18 18 18 18 r (max) = 0.9, r (0) = 0.5,á = 0.4, x(0) = 7.5 19 19 19 19 r (max) = 0.95, r ( 0) = 0.55,á = 0.3, x( 0) = 8.5 20 20 20 20 r (max) = 0.96, r (0) = 0.3,á = 0.35, x(0) = 9 21 21 21 21 r (max) = 0.97, r (0) = 0.4,á = 0.4, x( 0) = 10 22 22 22 22 24 q23 = 0.98,á 23 = 0.32, x( 0) = 10, q = 0.95,á 24 = 0.33, x(0) = 9 26 q25 = 0.91,á 25 = 0.35, x( 0) = 8, q = 0.99,á 26 = 0.4, x( 0) = 5 q27 q = 0.97,á 27 = 0.98,á = 0.35, x(0) = 7, q = 0.33, x(0) = 9, q = 0.94,á 28 23 25 27 28 = 0.94,á = 0.37, x(0) = 6 24 26 28 = 0.32, x( 0) = 7.5 29 29 29 30 30 30 q = 0.93,á = 0.34, x(0) = 8.6, q = 0.96,á = 0.36, x(0) = 8 31 31 31 32 32 32 q = 0.95,á = 0.38, x(0) = 9, q = 0.93,á = 0.39, x(0) = 11 33 33 33 34 34 34 q = 0.97,á = 0.33, x( 0) = 7, q = 0.98,á = 0.3, x( 0) = 9 35 q37 35 = 0.99,á37 35 36 37 = 0.33, x( 0) = 15 36 36 Trong đó module 37 là module gốc, độ tin cậy phần mềm cũng là độ tin cậy của module gốc. a) Đối với bài toán A Đối với các module mua: Hàm mục tiêu: Max r11 y11 + r12 y12 + r13 y13 + r21 y21 + r22 y22 + r23 y23 + r31 y31 + r32 y32 + r33 y33 + r34 y34 + r41 y41 + r42 y42 + r43 y43 + r52 y52 + r52 y52 Các điều kiện ràng buộc: c11 y11 + c12 y12 + c13 y13 + c21 y21 + c22 y22 + c23 y23 + c31 y31 + c32 y32 + c33 y33c34 y34 + c41 y41 + c42 y42 + c43 y43 + c52 y52 + c52 y52 ≤ B' y11 + y12 + y13 = 1 y21 + y22 + y23 = 1 y31 + y32 + y33 + y34 = 1 y41 + y42 + y43 = 1 y51 + y52 = 1 yij = 0 or 1 Đối với các module phát triển trong công ty: Hàm mục tiêu: max (r  (max)  − r (min)  )e−á11  ( x37  37 − x( 0 ) ) 37 37 Các điều kiện ràng buộc: 37 ∑ xi ≤ B − B' i = 6 r (max) = r r , r (0) = q r (max) 37 35 36 37 37 37  ( 0 ) r = (r (max) − r ( 0) )e−á 36 ( x36 − x36 ) ; r (max) = r r r , r ( 0) = q r (max) 36 36 36 36 ( 0 ) 21 22 34 36 36 36 r = (r (max) − r (0) )e−á 35 ( x35 − x35 ) ; r (max) = r r r r , r (0) = q r (max) 35 35 35 35 ( 0 ) 19 20 32 33 35 35 35 r = (r (max) − r ( 0) )e−á 34 ( x34 − x34 ) ; r (max) = r r , r ( 0) = q r (max) 34 34 34 34 ( 0 ) 18 31 34 34 34 r = (r (max) − r (0) )e−á 33 ( x33 − x33 ) ; r (max) = r r , r (0) = q r (max) 33 33 33 33 ( 0 ) 17 30 33 33 33 r = (r (max) − r ( 0) )e−á 32 ( x32 − x32 ) ; r (max) = r r r , r ( 0) = q r (max) 32 32 32 32 ( 0 ) 15 16 29 32 32 32 r = (r (max) − r ( 0) )e−á 31 ( x31 − x31 ) ; r (max) = r r , r (0) = q r (max) 31 31 31 31 ( 0 ) 14 28 31 31 31 r = (r (max) − r ( 0) )e−á 30 ( x30 − x30 ) ; r (max) = r r r , r ( 0) = q r (max) 30 30 30 30 ( 0 ) 12 13 27 30 30 30 r = (r (max) − r (0) )e−á 29 ( x29 − x29 ) ; r (max) = r r , r ( 0) = q r (max) 29 29 29 29 ( 0 ) 11 26 29 29 29 r = (r (max) − r ( 0) )e−á 28 ( x 28 − x28 ) ; r (max) = r r , r (0) = q r (max) 28 28 28 28 ( 0 ) 4 25 28 28 28 r = (r (max) − r (0) )e−á 27 ( x27 − x27 ) ; r (max) = r r , r (0) = q r (max) 27 27 27 27 ( 0 ) 10 24 27 27 27 r = (r (max) − r (0) )e−á 26 ( x26 − x26 ) ; r (max) = r r r , r (0) = q r (max) 26 26 26 26 ( 0 ) 1 9 23 26 26 26 r = (r (max) − r ( 0) )e−á 25 ( x 25 − x25 ) ; r (max) = r r , r (0) = q r (max) 25 25 25 25 ( 0 ) 5 8 25 25 25 r = (r (max) − r (0) )e−á 24 ( x24 − x24 ) ; r (max) = r r , r ( 0) = q r (max) 24 24 24 24 ( 0 ) 3 7 24 24 24 r = (r (max) − r ( 0) )e−á 23 ( x23 − x23 ) ; r (max) = r r , r (0) = q r (max) 23 23 23 23 2 6 23 23 23 ( 0 ) r = (r (max) − r ( 0) )e−á 27 ( x 27 − x 27 ) ; r (max) = r r  , r ( 0) = q  r (max) 27 27 27 27 ( 0 ) 10 24 27 27 27 r = (r (max) − r ( 0) )e−á 26 ( x26 − x26 ) ; r (max) = r r r , r (0) = q r (max) 26 26 26 26 ( 0 ) 1 9 23 26 26 26 r = (r (max) − r (0) )e−á 25 ( x25 − x 25 ) ; r (max) = r r , r ( 0) = q r (max) 25 25 25 25 ( 0 ) 5 8 25 25 25 r = (r (max) − r ( 0) )e−á 24 ( x24 − x24 ) ; r (max) = r r , r ( 0) = q r (max) 24 24 24 24 ( 0 ) 3 7 24 24 24 r = (r (max) − r (0) )e−á 23 ( x 23 − x 23 ) ; r (max) = r r , r (0) = q r (max) 23 23 23 23 ( 0 ) 2 6 23 23 23  ( 0 ) r = (r (max) − r (0) )e−á 5 ( x5 − x5 ) , r = (r (max) − r (0) )e−á 6 ( x6 − x6 ) 5 5 5 6 6 6 ( 0 )  ( 0 ) r = (r (max) − r (0) )e−á 7 ( x7 − x7 ) , r = (r (max) − r ( 0) )e−á 8 ( x8 − x8 ) 7 7 7 8 8 8 ( 0 )  ( 0 ) r = (r (max) − r ( 0) )e−á 9 ( x9 − x9 ) , r = (r (max) − r (0) )e−á10 ( x10 − x10 ) 9 9 9 10 10 10 ( 0 )  ( 0 ) r = (r (max) − r ( 0) )e−á11 ( x11 − x11 ) , r = (r (max) − r ( 0) )e−á12 ( x12 − x12 ) 11 11 11 12 12 12 ( 0 )  ( 0 ) r = (r (max) − r (0) )e−á13 ( x13 − x13 ) , r = (r (max) − r (0) )e−á14 ( x14 − x14 ) 13 13 13 14 14 14 ( 0 )  ( 0 ) r = (r (max) − r (0) )e−á15 ( x15 − x15 ) , r = (r (max) − r (0) )e−á16 ( x16 − x16 ) 15 15 15 16 16 16 ( 0 )  ( 0 ) r = (r (max) − r ( 0) )e−á17 ( x17 − x17 ) , r = (r (max) − r ( 0) )e−á18 ( x18 − x18 ) 17 17 17 18 18 18 ( 0 )  ( 0 ) r = (r (max) − r ( 0) )e−á19 ( x19 − x19 ) , r = (r (max) − r (0) )e−á 20 ( x20 − x20 ) 19 19 19 20 20 20 ( 0 )  ( 0 ) r = (r (max) − r ( 0) )e−á 21 ( x 21 − x21 ) , r = (r (max) − r (0) )e−á 23 ( x23 − x23 ) 21 21 21 23 23 23 i i x ≥ x(0) , i = 6,…,37 Trong đó module 37 là module gốc, độ tin cậy của module này cũng là độ tin cậy của phần mềm. a) Đối với bài toán B Đối với các module mua tương tự như bài toán A: Hàm mục tiêu: Maximizer11 y11 + r12 y12 + r13 y13 + r21 y21 + r22 y22 + r23 y23 + r31 y31 + r32 y32 + r33 y33 + r34 y34 + r41 y41 + r42 y42 + r43 y43 + r52 y52 + r52 y52 Các điều kiện ràng buộc: c11 y11 + c12 y12 + c13 y13 + c21 y21 + c22 y22 + c23 y23 + c31 y31 + c32 y32 + c33 y33c34 y34 + c41 y41 + c42 y42 + c43 y43 + c52 y52 + c52 y52 ≤ B' y11 + y12 + y13 = 1 y21 + y22 + y23 = 1 y31 + y32 + y33 + y34 = 1 y41 + y42 + y43 = 1 y51 + y52 = 1 yij = 0 or 1 Đối với các module phát triển trong công ty: Hàm mục tiêu: 37 Min∑ xi i = 6 Các điều kiện ràng buộc: ( 0 ) (r (max) − r (min) )e−á11 ( x37 − x37 ) = R 37 37 r (max) = r r  , r (0) = q  r (max) 37 35 36 37 37 37  ( 0 ) r = (r (max) − r ( 0) )e−á 36 ( x36 − x36 ) ; r (max) = r r r , r (0) = q r (max) 36 36 36 36 ( 0 ) 21 22 34 36 36 36 r = (r (max) − r (0) )e−á 35 ( x35 − x35 ) ; r (max) = r r r r , r ( 0) = q r (max) 35 35 35 35 19 20 32 33 35 35 35 ( 0 ) r = (r (max) − r (0) )e−á 34 ( x34 − x34 ) ; r (max) = r r , r ( 0) = q r (max) 34 34 34 34 ( 0 ) 18 31 34 34 34 r = (r (max) − r ( 0) )e−á 33 ( x33 − x33 ) ; r (max) = r r , r ( 0) = q r (max) 33 33 33 33 ( 0 ) 17 30 33 33 33 r = (r (max) − r (0) )e−á 32 ( x32 − x32 ) ; r (max) = r r r , r ( 0) = q r (max) 32 32 32 32 ( 0 ) 15 16 29 32 32 32 r = (r (max) − r ( 0) )e−á 31 ( x31 − x31 ) ; r (max) = r r , r ( 0) = q r (max) 31 31 31 31 ( 0 ) 14 28 31 31 31 r = (r (max) − r (0) )e−á 30 ( x30 − x30 ) ; r (max) = r r r , r (0) = q r (max) 30 30 30 30 ( 0 ) 12 13 27 30 30 30 r = (r (max) − r (0) )e−á 29 ( x29 − x29 ) ; r (max) = r r , r ( 0) = q r (max) 29 29 29 29 ( 0 ) 11 26 29 29 29 r = (r (max) − r ( 0) )e−á 28 ( x28 − x28 ) ; r (max) = r r , r (0) = q r (max) 28 28 28 28 ( 0 ) 4 25 28 28 28 r = (r (max) − r ( 0) )e−á 27 ( x27 − x27 ) ; r (max) = r r , r (0) = q r (max) 27 27 27 27 ( 0 ) 10 24 27 27 27 r = (r (max) − r (0) )e−á 26 ( x26 − x26 ) ; r (max) = r r r , r (0) = q r (max) 26 26 26 26 ( 0 ) 1 9 23 26 26 26 r = (r (max) − r ( 0) )e−á 25 ( x25 − x 25 ) ; r (max) = r r , r ( 0) = q r (max) 25 25 25 25 ( 0 ) 5 8 25 25 25 r = (r (max) − r (0) )e−á 24 ( x24 − x24 ) ; r (max) = r r , r (0) = q r (max) 24 24 24 24 ( 0 ) 3 7 24 24 24 r = (r (max) − r (0) )e−á 23 ( x 23 − x 23 ) ; r (max) = r r , r (0) = q r (max) 23 23 23 23 ( 0 ) 2 6 23 23 23  ( 0 ) r = (r (max) − r ( 0) )e−á 5 ( x5 − x5 ) , r = (r (max) − r ( 0) )e−á 6 ( x6 − x6 ) 5 5 5 6 6 6 ( 0 )  ( 0 ) r = (r (max) − r (0) )e−á 7 ( x7 − x7 ) , r = (r (max) − r (0) )e−á 8 ( x8 − x8 ) 7 7 7 8 8 8 ( 0 )  ( 0 ) r = (r (max) − r (0) )e−á 9 ( x9 − x9 ) , r = (r (max) − r ( 0) )e−á10 ( x10 − x10 ) 9 9 9 10 10 10 ( 0 )  ( 0 ) r = (r (max) − r (0) )e−á11 ( x11 − x11 ) , r = (r (max) − r (0) )e−á12 ( x12 − x12 ) 11 11 11 12 12 12 ( 0 )  ( 0 ) r = (r (max) − r (0) )e−á13 ( x13 − x13 ) , r = (r (max) − r ( 0) )e−á14 ( x14 − x14 ) 13 13 13 14 14 14 ( 0 )  ( 0 ) r = (r (max) − r ( 0) )e−á15 ( x15 − x15 ) , r = (r (max) − r ( 0) )e−á16 ( x16 − x16 ) 15 15 15 16 16 16 ( 0 )  ( 0 ) r = (r (max) − r ( 0) )e−á17 ( x17 − x17 ) , r = (r (max) − r ( 0) )e−á18 ( x18 − x18 ) 17 17 17 18 18 18 ( 0 )  ( 0 ) r = (r (max) − r (0) )e−á19 ( x19 − x19 ) , r = (r (max) − r ( 0) )e−á 20 ( x20 − x20 ) 19 19 19 20 20 20 ( 0 )  ( 0 ) r = (r (max) − r (0) )e−á 21 ( x21 − x21 ) , r = (r (max) − r (0) )e−á 23 ( x23 − x23 ) 21 21 21 23 23 23 i i x ≥ x(0) , i = 6,…,37 Đối với bài toán A: B B’ yij [ x6 ,…, x37 ] [r6 ,…, r36 ] Độ tin cậy tối ưu ( r37 ) 288 33 100 1000 100 100 10 [9.00, 5.00, 7.00, 6.00, 8.00, 6.00, 9.00, 7.00, 8.00, 6.00, 9.00, 5.00, 8.00, 7.50, 8.50, 9.00, 10.00, 10.00, 9.00, 8.00, 5.00, 7.00, 6.00, 9.00, 7.50, 6.50, 8.00, 9.00, 11.00, 7.00, 9.00, 15.00] [0.30, 0.50, 0.40, 0.30, 0.64, 0.40, 0.50, 0.40, 0.45, 0.40, 0.35, 0.40, 0.45, 0.50, 0.55, 0.30, 0.40, 0.22, 0.38, 0.30, 0.05, 0.19, 0.23, 0.02, 0.04, 0.09, 0.003, 0.01, 0.04, 0.32] 0.0014 299 44 001 0001 001 001 01 [9.00, 5.00, 7.00, 6.00, 8.00, 6.00, 9.00, 7.00, 8.00, 6.00, 9.00, 5.00, 8.00, 7.50, 8.50, 9.00, 10.00, 10.00, 9.00, 8.00, 5.00, 7.00, 6.00, 9.00, 7.50, 6.50, 8.00, 9.00, 11.00, 7.00, 9.00, 15.00] [0.30 0.50, 0.40, 0.30, 0.64, 0.40, 0.50, 0.40, 0.45, 0.40, 0.35, 0.40, 0.45, 0.50, 0.55, 0.30, 0.40, 0.28, 0.45, 0.35, 0.07, 0.19, 0.28, 0.03, 0.04, 0.11, 0.004, 0.01, 0.05, 0.37] 0.0054 500 44 001 0001 001 001 01 [9.00, 5.00, 45.76, 6.00, 8.00, 6.00, 9.00, 7.00, 24.55, 6.00, 9.00, 5.00, 24.64,7.50, 8.50, 31.15, 28.09, 10.00, 9.00, 25.14, 5.00, 7.00, 17.78, 9.00, 7.50, 38.53, 8.00, 9.00, 31.37, 7.00, 13.70, 17.79] [0.30, 0.50, 0.93, 0.30, 0.64, 0.40, 0.50, 0.40, 0.96, 0.40, 0.35, 0.40, 0.95, 0.50, 0.55, 0.96, 0.97, 0.28, 0.45, 0.89, 0.07, 0.60, 0.77, 0.03, 0.11, 0.74, 0.004, 0.04, 0.70, 0.87] 0.5574 600 44 001 0001 001 001 01 [9.00, 5.00, 56.17, 6.00, 8.00, 6.00, 9.00, 7.00, 28.18, 6.00, 9.00, 5.00, 28.74, 7.50, 8.50, 34.89, 31.53, 10.00, 9.00, 37.78, 5.00, 7.00, 26.99, 9.00, 7.50, 66.35, 8.00, 9.00, 49.74, 7.00, 17.88, 20.24] [0.30, 0.50, 0.93, 0.30, 0.64, 0.40, 0.50, 0.40, 0.96, 0.40, 0.35, 0.40, 0.95, 0.50, 0.55, 0.96, 0.97, 0.28, 0.45, 0.89, 0.07, 0.60, 0.77, 0.03, 0.11, 0.74, 0.004, 0.04, 0.70, 0.87] 0.5625 1000 44 001 0001 001 001 01 [9.00, 5.00, 90.95, 6.00, 8.00, 6.00, 9.00, 7.00, 40.04, 6.00, 9.00, 5.00, 42.30,7.50, 8.50, 46.64, 42.57, 10.00, 9.00, 83.81, 5.00, 7.00, 62.63, 9.00, 7.50, 158.31, 8.00, 9.00, 115.17, 7.00, 35.90, 30.82] [0.30, 0.50, 0.93, 0.30, 0.64, 0.40, 0.50, 0.40, 0.96, 0.40, 0.35, 0.40, 0.95, 0.50, 0.55, 0.96, 0.97, 0.28, 0.45, 0.89, 0.07, 0.60, 0.77, 0.03, 0.11, 0.74, 0.004, 0.04, 0.70, 0.87] 0.5647 Bảng 6.7: Kết quả chạy phần mềm có 37 module cho bài toán A Đối với bài toán B: Độ tin cậy phần mềm ( r37 ) B’ yij [ x6 ,…, x37 ] [r6 ,…, r36 ] Chi phí phần mềm (B) 0.0014 33 100 1000 100 100 10 [9.00, 5.00, 7.00, 6.00, 8.00, 6.00, 9.00, 7.00, 8.00, 6.00, 9.00, 5.00, 8.00, 7.50, 8.50, 9.00, 10.00, 10.00, 9.00, 8.00, 5.00, 7.00, 6.00, 9.00, 7.50, 6.50, 8.00, 9.00, 11.00, 7.00, 9.00, 15.00] [0.30, 0.50, 0.40, 0.30, 0.64, 0.40, 0.50, 0.40, 0.45, 0.40, 0.35, 0.40, 0.45, 0.50, 0.55, 0.30, 0.40, 0.22, 0.38, 0.30, 0.05, 0.19, 0.23, 0.02, 0.04, 0.09, 0.003, 0.01, 0.04, 0.32] 287 0.2 44 001 0001 001 001 01 [9.00, 5.00, 15.36, 6.00, 8.00, 6.00, 9.00, 7.00, 10.48, 6.00, 9.00, 5.00, 12.30, 7.50, 8.50,14.82, 15.67, 10.00, 9.00, 8.25, 5.00, 7.00, 6.00, 9.00, 7.50, 8.16, 8.00, 9.00, 23.63, 7.62, 9.00,15.00] [0.30, 0.50, 0.89, 0.30, 0.64, 0.40, 0.50, 0.40, 0.77, 0.40, 0.35, 0.4, 0.84, 0.50, 0.55, 0.87, 0.91, 0.28, 0.45, 0.78, 0.07, 0.54, 0.63, 0.03, 0.10, 0.45, 0.004, 0.04, 0.38, 0.67, 0.29] 324.68 0.3 44 001 0001 001 001 01 [9.00, 5.00, 16.66, 6.00, 8.00, 6.00, 9.00, 7.00, 15.32, 6.00, 9.00, 5.00, 14.85, 7.50, 8.50, 17.60, 16.81, 10.00, 9.00, 8.10, 5.00, 7.00, 7.70, 9.00, 7.50, 9.68, 8.00, 9.00, 40.89, 8.05, 9.00, 15.00] [0.30, 0.50, 0.90, 0.30, 0.64, 0.40, 0.50, 0.40, 0.93, 0.40, 0.35, 0.40, 0.90, 0.50, 0.55, 0.93, 0.93, 0.28, 0.45, 0.79, 0.07, 0.58, 0.66, 0.03, 0.11, 0.58, 0.004 0.04, 0.53, 0.59 0.45] 340.77 0.5 44 001 0001 001 001 01 [9.00, 5.00, 18.47, 6.00, 8.00, 6.00, 9.00, 7.00, 16.47, 6.00, 9.00, 5.00, 15.76, 7.50, 8.50, 19.32, 17.39, 10.00, 9.00, 11.03, 5.00, 7.00, 8.27, 9.00, 7.50, 11.21, 8.00, 9.00, 47.29, 7.02, 9.05,15.00] [0.30, 0.50, 0.91, 0.30, 0.64, 0.40, 0.50, 0.40, 0.94, 0.40, 0.35, 0.40, 0.91, 0.50, 0.55, 0.94, 0.94, 0.27, 0.45, 0.84, 0.07, 0.58, 0.71, 0.03, 0.11, 0.65, 0.004 0.042, 0.59, 0.84, 0.5187] 378.91 Bảng 6.8: Kết quả chạy phần mềm có 37 module cho bài toán B 6.3. Kết luận Tự động hóa quá trình phân phối chi phí để đánh giá độ tin cậy phần mềm là một bài toán mở, nhiều phương pháp đã được đưa ra để giải quyết bài toán. Phương pháp kết hợp quy hoạch nguyên và quy hoạch phi tuyến của hàm nhiều biến là một giải pháp được đề xuất để giải quyết vấn đề này. Đứng trên góc độ của một công trình nghiên cứu, luận văn cố gắng đưa ra hai giải pháp nhằm cung cấp thêm một cách thức để giải quyết bài toán này. Mô hình đã tính toán độ tin cậy của phần mềm dựa vào phân phối chi phí. Bằng việc sử dụng phương pháp 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, kết hợp với phương pháp quy hoạch phi tuyến để giải quyết hàm số mũ nhiều biến, để thực hiệc việc phân phối chi phí cho các module phát triển. Thông qua việc kết hợp này, luận văn đã dùng các hàm trong Matlab để xây dựng được hai giải pháp cho phép kết hợp giữa bài toán quy hoạch nguyên và quy hoạch phi tuyến một cách tự động. Chương trình hiện thực đã cung cấp được giải với độ chính xác tương đối cho một số minh họa cụ thể. Tuy nhiên, chương trình cũng có một vài hạn chế: ƒ Hiện tại mô hình chỉ được thực hiện hàm phân phối mũ để tính độ tin cậy của các module. ƒ Việc phân phối chi phí giữa module mua và module phát triển trong công ty còn mang tính cảm tính, đều này làm cho lời giải của bài toán có thể chưa được tối ưu. ƒ Chương trình chỉ sử dụng các hàm trong Matlab để thực việc tối ưu hóa, mà chúng ta không can thiệp vào bên trong nó. ƒ Do số liệu trong chương trình là tự tạo cho nên kết quả của chương trình có thể chưa xác thực tế. Đây là những hạn chế mà trong phạm vi luận văn này chưa thể giải quyết trọn vẹn. Một số đề xuất và hướng mở rộng dựa vào những hạn chế vừa nêu: ƒ Xây dựng các mô hình khác mô hình số mũ để giải quyết việc phân phối chi phí. ƒ Xây dựng một giải thuật thực hiện việc phân phối chi phí giữa các module mua và module phát triển một cách tối ưu nhất. ƒ Xây dựng một hàm quy hoạch phi tuyến tồn tại cả biến nguyên và biến thực để giải quyết bài toán một cách tối ưu nhất. ƒ Lấy dữ liệu thực từ các hãng phần mềm ứng dụng vào mô hình này. Với những sự mở rộng này chúng ta có thể xây dựng một giải pháp hữu hiệu hơn cho bài toán. Đây chính là hướng phát triển của luận văn. Tài Liệu Tham Khảo [1] Jonathan F.Bard “Practical Bilevel Optimization Algorithms and Applications” Springer 1999, ISBN 0-7923-5458-3 [2] John W. Chinneck “Practical Optimization: A Gentle Introduction” Systems and Computer Engineering Carleton University Ottawa, Ontario K1S 5B6 Canada 74H [3] Hoang Pham, “Software Reliability” Springer – Verlag Singapore Pte.Ltd.2000 [4] Lê Quang Hoàng Nhân, “Giáo trình Toán Cao Cấp – Phần Giải Tích” Nhà xuất bản thống kê. [5] Nguyễn Đức Thành, “MATLAB và ứng dụng trong điều khiển” Nhà xuất bản Đại học Quốc gia Tp.HCM. [6] Nguyễn Nhật Lệ - Phan Mạnh Dần “Giải bài toán tối ưu hoá ứng dụng bằng MATLAB-MAPLE tối ưu hoá tĩnh và điều khiển tối ưu” Nhà xuất bản Khoa học Kỹ thuật Hà Nội. [7] O.Berman and M.Cutler, “Cost Allocation for Software Reliability, Recent Advances in Reliability and Quality Engineering”, Vol.2, Series on Quality, Reliability & Engineering Statistisc, Editor Hoang Pham, Word Scientific, 2001 0.2, 1.1 Phụ lục 1. Bảng đối chiếu Thuật ngữ Anh - Việt Thuật ngữ Tiếng Anh Thuật ngữ Tiếng Việt Algorithm Giải thuật Bartitioning Sự phân chia Binary Integer Programming Quy hoạch nguyên nhị phân Branch and bound Nhánh và cận Branching Sự phân nhánh Bounding Sự giới hạn Cost Allocation Phân phối chi phí Branching Sự phân nhánh In-house Developed module Module tự phát triển trong công ty Integation module Module tích hợp Fathoming Sự thăm dò Linear Programming Quy hoạch tuyến tính Mathematical Toán học Mean Value Function Hàm giá trị trung bình Nonlinear Programming Quy hoạch phi tuyến Optimization Tối ưu Pruning Sự loại bỏ Purchased module Module mua Resource Allocation Phân phối tài nguyên Software system Hệ thống phần mềm Software Reliability Độ tin cậy phần mềm Solution Giải pháp Phụ lục 2. Bảng tóm tắt các mô hình đánh giá độ tin cậy phần mềm Một vài mô hình đánh giá độ tin cậy phần mềm dựa vào quá trình phân phối Poisson không đồng nhất (Non-homogeneous Poisson Process - NHPP). NHPP là nhóm các mô hình cung cấp một quá trình phân tích, mô tả hiện tượng lỗi phần mềm trong quá trình kiểm tra. Điểm chính của mô hình NHPP là đánh giá hàm giá trị trung bình (Mean Value Function – MVF) số lượng lỗi được tích lũy trong một khoảng thời gian [3]. t m(t ) = ∫ ë (s)ds 0 Hàm độ tin cậy của phần mềm là: R(t ) = e− m (t ) = e  t − ∫ ë ( s ) ds 0 Tên mô hình Loại mô hình MVF (m(t)) Goel-Okumoto (G-O) Concave m(t) = a(1 − e−bt ) a(t) = a b(t) = b Delayed S-shaped S-shaped m(t ) = a(1 − (1 + bt )e−bt ) a(t) = a b 2t b(t ) = 1 + bt Inflection S-shaped Concave a(1 − e−bt ) m(t) = 1 + âe−bt a(t) = a b(t) = b 1 + âe−bt Yamade exponential Concave ( − ât ) m(t ) = a(1 − e− rá (1−e ) ) a(t ) = a b(t ) = ráâte −ât Yamada Rayleigh S-shaped ( − ât 2 / 2 ) m(t ) = a(1 − e −rá (1−e ) ) a(t ) = a b(t ) = ráâte −ât 2 / 2 Yamada imperfect debugging model (1) S-shaped m(t ) = ab (eát − e−bt ) á + b a(t ) = aeát b(t) = b Yamada imperfect debugging model (2) S-shaped m(t ) = a[1 − e−bt ][1 − á ] + áat b a(t ) = aeát b(t ) = b Pham-Nordmann S-shaped và concave a[1 − e−bt ][1 − á ] + áat m(t) = b 1 + â −bt a(t ) = a(1 + át) b(t) = b 1 + âe −bt Pham-Zhang S-shaped và concave m(t ) = 1 [(c + a)(1 − e −bt ) 1 + â −bt − a (e−át − e −bt )] b − á a(t ) = c + a(1 − e −át ) b(t ) = b 1 + âe−bt Phụ lục 3. Sơ lược về MATLAB MATLAB [4] có ngồn gốc từ chữ matrix laboratory, là ngôn ngữ máy tính dùng để tính toán kỹ thuật. MATLAB là sản phẩm của công ty The Mathworks Inc, với địa chỉ www.mathworks.com và sử dụng MATLAB phải có bản quyền. Tuy nhiên, có rất nhiều hàm MATLAB được viết bởi người sử dụng và phổ biến miễn phí trên mạng giúp cho MATLAB ngày càng phong phú hơn. Dưới đây trích các hàm sử dụng trong chương trình [5][6]. a) Hàm bintprog: tìm nghiệm tối ưu của bài toán lập trình số nguyên nhị phân có dạng: Hàm mục tiêu: Minimize f .y các điều kiện ràng buộc: A.y ≤ b Aeq.y = beq trong đó: ƒ f , b, beq : các vector ƒ A, Aeq : các ma trận ƒ Các biến y bắt buộc phải là các biến nhị phân, nghĩa là chúng chỉ nhận các giá trị: 0 hoặc 1. Cú pháp: ƒ y = bintprog(f) ƒ y = bintprog(f, A, b) ƒ y = bintprog(f, A, b, Aeq, beq) ƒ [y, fval] = bintprog(...) ƒ [y,fval, exitflag] = bintprog(...) ƒ [y, fval, exitflag, output] = bintprog(...) Mô tả: ƒ y = bintprog(f): giải quyết bài toán lập trình số nguyên nhị phân có dạng: Minimize f .y ƒ y = bintprog(f, A, b): tìm nghiệm tối ưu của bài toán lập trình số nguyên nhị phân có dạng: Min f .y với điều kiện ràng buộc: A.y ≤ b ƒ y = bintprog(f, A, b , Aeq, beq): tìm nghiệm tối ưu của bài toán lập trình số nguyên nhị phân có dạng: Minimize f .y với điều kiện ràng buộc: A. y ≤ b Aeq.y = beq ƒ [y, fval] = bintprog(...) trả về giá trị hàm mục tiêu fval , và nghiệm tối ưu y ứng với hàm mục tiêu đó. ƒ [y,fval, exitflag] = bintprog(...) tương tự như trên, cộng thêm exitflag mô trả trạng thái của bài toán bintprog. 9 Exitflag =1 : hàm hội tụ đến 1 giải pháp y. 9 Exitflag =0 : số lượng lần lặp đi lặp lại vượt quá Options.MaxIter 9 Exitflag =-2 : bài toán không thể làm được. 9 Exitflag =-4 : số lượng node vượt quá số lần lặp cực đại được cho phép (Options.MaxIter). 9 Exitflag =-5 : thời gian tìm kiếm vượt quá Options.Maxtime. b) Hàm fmincon: tìm nghiệm tối ưu của hàm nhiều biến có dạng: Hàm mục tiêu: min f ( x) Các điều kiện ràng buộc: c( x) ≤ 0 ceq( x) = 0 A * x ≤ b Aeq * x = beq lb ≤ x ≤ ub Trong đó ƒ x, b, beq, lb, ub là các vector ƒ A, Aeq là các ma trận. ƒ c( x), ceq( x) là các hàm trả về các vertor ƒ f ( x), c( x), ceq( x) có thể là các phương trình phi tuyến. Cú pháp: ƒ x = fmincon(fun,x0,A,b) ƒ x = fmincon(fun,x0,A,b,Aeq,beq) ƒ x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub) ƒ x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon) ƒ x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options) ƒ [x,fval] = fmincon(...) ƒ [x,fval,exitflag] = fmincon(...) ƒ [x,fval,exitflag,output] = fmincon(...) ƒ [x,fval,exitflag,output,lambda] = fmincon(...) ƒ [x,fval,exitflag,output,lambda,grad] = fmincon(...) ƒ [x,fval,exitflag,output,lambda,grad,hessian] = fmincon(...) Mô tả: ƒ fmincon: cố gắng tìm một cực tiểu thỏa mãn các điều kiện ràng buộc phi tuyến hoặc tuyến tính. ƒ x = fmincon(fun,x0,A,b): bắt đầu tìm kiếm tại x0 và cố gắng tìm một cực tiểu x để hàm mục tiêu đạt giá trị nhỏ nhất thỏa mãn điều kiện ràng buộc A*x <= b, trong đó x0 có thể là một vector hoặc matrix. ƒ x = fmincon(fun,x0,A,b,Aeq,beq) tương tự như trên, thiết lập thêm điều kiện ràng buộc Aeq*x = beq và A*x <= b. Có thể thiết lập A=[] và b=[] khi không tồn tại các ràng buộc phi tuyến. ƒ x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub) tương tự như trên, thiết lập thêm một tập điều kiện lb <= x <= ub. Có thể thiết lập Aeq=[] và beq=[] khi không tồn tại các ràng buộc tuyến tính. ƒ x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon) tương tự như trên, thiết lập thêm một tập điều kiện các phương trình tuyến tính c(x) or hoặc phi tuyến ceq(x) được định nghĩa trong nonlcon. Có thể thiết lập lb=[] and/or ub=[] nếu không tồn tại. ƒ [x,fval] = fmincon(...) trả về giá trị hàm mục tiêu và giá trị của các biến ứng với hàm mục tiêu đó. ƒ [x,fval,exitflag] = fmincon(...) tương tự như trên, thêm một giá trị exitflag cho biết trạng thái của hàm fmincon. ƒ [x,fval,exitflag,output] = fmincon(...) trả về một cấu trúc output với thông tin về sự tối ưu hoá. ƒ [x,fval,exitflag,output,lambda] = fmincon(...) trả về một cấu trúc lambda trong Lagrange multipliers tại giải pháp tìm ra giá trị x. ƒ [x,fval,exitflag,output,lambda,grad] = fmincon(...) trả về giá trị gradient của fun tại giải pháp x. ƒ [x,fval,exitflag,output,lambda,grad,hessian] = fmincon(...)trả về giá trị của ma trận Hessian tại giải pháp x. Tham khảo Chỉ Mục B Biến nhị phân, 9, 14, 15, 16, 17, 19, 39 Branch and bound, 5, 18, 78 C Cấu trúc đặc biệt, 18 Chi phí, 1, 5, 7, 8, 9, 11, 14, 37, 38, 39, 40, 41, 44, 45, 49, 50, 75 Chi phí khởi tạo, 7 Cực tiểu cục bộ, 25 Cực tiểu toàn cục, 30 Cực trị, 28, 32 D Điểm dừng, 27, 30, 31, 33, 34, 35 Điều kiện ràng buộc, 15, 16, 19, 21, 23, 25, 27, 29, 30, 31, 32, 33, 34, 35, 38, 41, 58, 59, 63, 64, 65, 70, 71, 72 Độ tin cậy phần mềm, 1, 2, 5, 6, 7, 37, 41, 57, 62, 68, 79, 81 Độ tin cậy tối đa, 7, 9 Độ tin cậy tối thiểu, 7, 9 G Giải pháp, 22, 78 Giải thuật, 5, 15, 18, 19, 22, 23, 76 H Hàm lồi, 26 Hàm mục tiêu, 15, 19, 21, 23, 25, 27, 29, 30, 34, 35, 38, 39, 41, 44, 48, 49, 58, 59, 63, 64, 65, 69, 70, 71, 72 Hessian, 28, 30, 35 L Lagrangian, 32 M Ma trận, 28, 30, 31, 32, 33, 35, 36 Module đơn, 6, 7, 8, 9, 10, 12, 38, 40 Module mua, 2, 6, 7, 8, 9, 10, 12, 37, 38, 39, 40, 41, 58, 63, 65, 69, 71, 75, 76 Module phát triển, 2, 5, 7, 37, 38, 40, 41, 58, 59, 64, 65, 70, 71, 75, 76 Module tích hợp, 6, 7, 9, 10, 12, 13, 40, 41, 43 N Ngân sách, 1, 9, 11, 13, 14, 39, 40 P Phân hoạch, 37, 38 Phân phối chi phí, 2, 5, 6, 7, 8, 37, 39, 41, 57, 62, 68, 75, 76 Q Quy hoạch nguyên, 2, 5, 15, 16, 18, 38, 75 Quy hoạch phi tuyến 5, 27, 53, 75, 76 S Số lượng biến, 18 T Tập lồi, 26 Tối ưu, 2, 15, 16, 17, 18, 21, 22, 23, 24, 25, 27, 29, 30, 33, 34, 38, 40, 41, 55, 56, 60, 61, 75, 76 Tổng chi phí, 38 V Vector, 29, 31, 34, 35 Version, 7, 8, 9, 11, 14, 38, 39 X Xác định dương, 27, 28, 30, 33, 35, 36 ._.