Đạ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
CỘNG HOÀ XÃ HỘI CHỦ NGHIÃ VIỆT NAM
Độc Lập - Tự Do - Hạnh Phúc ---oOo--- Tp. HCM, ngày . .30. . tháng . .06. . năm .2008. ĐẠI HỌC QUỐC GIA TP. HCM TRƯỜNG ĐẠI HỌC BÁCH KHOA ----------------
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(cid:133) / Nữ (cid:59)
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
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.
Phan Thị Ngọc Mai
Trang i
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
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.
Phan Thị Ngọc Mai
Trang ii
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
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.
Phan Thị Ngọc Mai
Trang iii
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
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 Giới thiệu ..............................................................................................................1 Sơ lược về việc phân phối độ tin cậy phần mềm ...............................................2 Kết cấu của luận văn ...........................................................................................4
1.1. 1.2. 1.3.
2.3.1. 2.3.2. 2.3.3.
2.1. 2.2. 2.3.
Chương 2. Các Mô Hình Phân Phối Chi Phí Cho Độ Tin Cậy Phần Mềm .............6 Giới thiệu ..............................................................................................................6 Phân loại các module trong phần mềm..............................................................6 Mô hình quyết định trước ...................................................................................7 Độ tin cậy của một module đơn phát triển trong công ty............................................7 Độ tin cậy của một module mua .................................................................................8 Độ tin cậy của một module tích hợp ...........................................................................9 Mô hình tổng quát .............................................................................................14
2.4.
Chương 3. Phương Pháp Giải Bài Toán Quy Hoạch Nguyên.................................15 Giới thiệu ............................................................................................................15 Sự cần thiết của bài toán quy hoạch nguyên ...................................................15 Phương pháp giải quyết bài toán quy hoạch nguyên .....................................16 Phương pháp giải quyết bài toán quy hoạch nguyên nhị phân ..................... 19
3.1. 3.2. 3.3. 3.4.
4.3.1. 4.3.2. 4.3.3.
4.1. 4.2. 4.3.
4.4.
Chương 4. Phương Pháp Giải Bài Toán Quy Hoạch Phi Tuyến ...........................23 Giới thiệu ............................................................................................................23 Những điều kiện tối ưu......................................................................................25 Tính lồi của hàm nhiều biến .............................................................................26 Tập lồi .......................................................................................................................26 Định nghĩa hàm lồi ...................................................................................................26 Đặc trưng của hàm lồi...............................................................................................26 Các phương pháp giải bài toán quy hoạch phi tuyến.....................................27 Giải bài toán tối ưu không có điều kiện ràng buộc ...................................................27 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 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 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
4.4.1. 4.4.2. 4.4.3. 4.4.4.
Chương 5. Giải Quyết Bài Toán ................................................................................36 Phân hoạch bài toán ..........................................................................................36 Bài toán tối ưu hóa các module mua ................................................................37 Bài toán tối ưu hóa các module phát triển trong công ty...............................39
Phan Thị Ngọc Mai
Trang iv
5.1. 5.2. 5.3.
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
5.4.1. 5.4.2.
5.4.
Sự kết hợp module mua và module phát triển trong công ty ........................40 Bài toán A .................................................................................................................41 Bài toán B .................................................................................................................46
6.2.1. 6.2.2. 6.2.3. 6.2.4. 6.2.5. 6.2.6. 6.2.7. 6.2.8.
6.1. 6.2.
Chương 6. Một số kết quả, kết luận...........................................................................51 Sơ lược về chương trình ....................................................................................51 Một số kết quả chạy chương trình ................................................................... 51 Bài toán trong ví dụ 3.4 ............................................................................................51 Bài toán trong ví dụ 4.1.1 .........................................................................................51 Bài toán trong ví dụ 4.3.1 .........................................................................................52 Bài toán trong ví dụ 4.3.4 .........................................................................................52 Bài toán cho một phần mềm gồm có 6 module.........................................................54 Bài toán cho một phần mềm gồm có 11 module.......................................................56 Bài toán cho một phần mềm gồm có 22 module.......................................................61 Bài toán cho một phần mềm gồm có 37 module.......................................................67 Kết luận...............................................................................................................74
6.3.
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
Phan Thị Ngọc Mai
Trang v
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
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
Phan Thị Ngọc Mai
Trang vi
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
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
Phan Thị Ngọc Mai
Trang vii
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
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:
(cid:131) 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.
(cid:131) 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 đó.
(cid:131) 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.
Phan Thị Ngọc Mai
Trang 1
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
(cid:131) 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ả:
(cid:131) 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.
(cid:131) 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.
(cid:131) 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.
(cid:131) 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:
(cid:131) Đố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.
(cid:131) Đố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
Phan Thị Ngọc Mai
Trang 2
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
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 đó.
(cid:131) Đố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.
(cid:131) Đố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
Phan Thị Ngọc Mai
Trang 3
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
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:
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.
(cid:131) Đối với các module mua các verion của các module mua có độ tin cậy và
để 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.
(cid:131) Đối với các module phát triển trong công ty, qua việc tìm chi phí nhỏ nhất
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
Phan Thị Ngọc Mai
Trang 4
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
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.
Phan Thị Ngọc Mai
Trang 5
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
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.
(cid:131) 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.
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.
(cid:131) 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ể
Phan Thị Ngọc Mai
Trang 6
(cid:131) Module tích hợp là một module được phát triển trong công ty. Module tích
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
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.
(cid:131) 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.
(cid:131) 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:
(cid:131) 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.
(cid:131) 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
Giả sử
là chi phí khởi tạo cho việc phát triển module i trong công ty, và ứng
)0( ix
)0(
với chi phí này ta có độ tin cậy khởi tạo
. Nếu chúng ta cung cấp chi phí nhỏ hơn
ir
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ể
(max)
1
(max) =
đạt được cho module i là
. Thường chúng ta cho rằng độ tin cậy
. Nhưng
ir
ir
(max)
với mức độ đúng đắn 100% rất khó xẩy ra, do đó
là một giá trị nhỏ hơn hoặc
ir
bằng 1.
Phan Thị Ngọc Mai
Trang 7
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
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
.
100
∞→ix
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ó
in version trên thị
).
trường (
Phan Thị Ngọc Mai
Trang 8
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
Cho
ijy là một biến nhị phân biểu thị cho việc mua hay không mua version thứ j
thì version j của module i được mua, ngược lại
thì
của module i . Nếu
1=ijy
0=ijy
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
in
1
, với bất kỳ mudule mua. Khi đó ta có độ tin cậy của
cần điều kiện sau
j
1 =
module mua i là ir :
in
=∑ ijy
(2.2)
r i
yr ij ij
∑
j
1 =
và chi phí để mua module i là:
in
=
c i
yc ij ij
∑
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
là độ tin cậy lớn nhất có thể đạt được của module tích hợp
iT . Giả sử
(m r Ti
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
iT được tính theo
s
=
công thức
. Tuy nhiên, trong quá trình tích hợp các module con có thể
r i
(max) r T i
k
1
∏ =
)0(
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
iTr
(max)
). Cho
là độ tin cậy nhỏ nhất có thể có của module
iT (có thể nhỏ hơn hoặc bằng
iTr
0(
)1
là một hệ số phản ánh sự tương thích giữa các module. Vì vậy
q T i
q T i
s
(max)
=
.
r i
)0( r T i
q T i
rq TT i i
k
1
= ∏ =
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à:
Phan Thị Ngọc Mai
Trang 9
< ≤
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
(
)
x
x
−
α − i
i
)0( i
≥
((
)
e
−
(max) r T i
(max) r T i
)0( r T i
=
(2.3)
R T i
<
− 0
x i x i
)0( x i )0( x i
⎫ ⎪ ⎬ ⎪⎭
⎧ ⎪ ⎨ ⎪⎩
đã được định nghĩa trong phần trước.
trong đó
iα ,
ix và
)0( ix
) phụ thuộc vào cấu trúc của phần mềm:
Công thức độ tin cậy phần mềm (
là bằng độ tin cậy của
(cid:131) Nếu phần mềm chỉ là một module đơn thì
module đó.
(cid:131) 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).
(cid:131) 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).
(cid:131) 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).
Phan Thị Ngọc Mai
Trang 10
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
Database-indexing (6)
Keyword (5)
Index-generator (3)
Parser (1)
Version 11
Analyzer (4)
Stemmer (2)
Version 12
Module tích hợp
Version 21
Module mua
Version 22
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:
(P1)
Max
S.T.
n
m
n
i
B
(P2)
≤
yc ij ij
∑∑
+ ∑
i
j
x i 1
1 =
1 =
+
mi = 1
in
1
=∑ ijy
j
1 =
với i=1,2, . . . ,m
(P3)
với i=m +1, . . . ,n và
x ≥ i
)0( x i
(P4)
yij =0,1 với i=1, . . . ,m và j=1, . . . ,ni
(cid:131) Mục tiêu (P1) là cực đại hoá độ tin cậy của hệ thống
.
(cid:131) (P2) đảm bảo tổng chi phí sử dụng không vượt quá ngân sách cho phép.
(cid:131) P(3) chắc chắn sẽ có duy nhất một version được module i mua, với
,...,2,1
m .
i =
(cid:131) (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
Phan Thị Ngọc Mai
Trang 11
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
được phát triển trong công ty sẽ lớn hơn không nếu
. Vì vậy, để độ tin cậy
x ≥ i
)0( x 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(
i
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):
(cid:131) Parser(1) và Stemmer(2) là các module mua. Mỗi module mua có 2
version.
(cid:131) Index-generator(3) và Analyzer(4) là hai module đơn.
(cid:131) Keyword(5) là module tích hợp từ hai module Analyzer(4) và Stemmer(2).
(cid:131) 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ụ:
,7.0 5 = =
,9.0 6 = =
,87.0 7 = =
m
)
,95.0 8 = =
)0( x 3
)
m
,83.0 ,53.0 ,3.0 2 = = = = r 11 r 12 r 21 r 22 ( r 3 c 11 c 12 c 21 c 22 )0( r 3 α 3
( r 0
)0( r 4
)0( x 4
,9.0 ,5.0 ,4.0 5.3 = = = = α 4
)0( x 5
0
,7.0 ,25.0 4 = = = q 5 α 5
)0( x 6
Để 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).
=
+
r 1
yr 11
11
yr 12
12
=
+
r 2
yr 21
yr 22
22
21
x
(3.0
)2
−
−
3
2
83.0(
)53.0
e
−
−
x 3
=
r 3
≥ Otherwise
0
(4.0
)5.3
x
−
−
4
e
−
−
x 4
=
r 4
5.3 ≥ Otherwise
0
⎧ 83.0 ⎨ ⎩ ⎧ )5.09.0(9.0 ⎨ ⎩
Độ tin cậy của module tích hợp Keyword(5) là:
Phan Thị Ngọc Mai
Trang 12
,8.0 ,3.0 3 = = = q 6 α 6
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
(25.0
)3
x
−
−
)
)
m
m
6
4
e
(
)
−
−
x 5
( r 5
( r 5
m
=
r 5
≥ Otherwise
)0( r 5 0
⎧ ⎨ ⎩
)
8.0
=
trong đó
và
) ( r m = 5
rr 42
)0( r 5
mr ( 5
là độ tin cậy của module tích hợp Database-indexing (6)
(3.0
)3
x
−
−
)
)
m
m
6
4
e
(
)
−
x 6
( r 6
( r 6
)0( r 6
m
=
r 6
≥ Otherwise
− 0
⎧ ⎨ ⎩
)
khi đó
và
8.0
=
) ( r m = 6
rrr 351
)0( r 6
mr ( 6
Bài toán là:
max
S.T.
B
+
+
+
+
+
+
+
≤
yc 11
11
yc 12
12
yc 21
21
yc 22
22
x 3
x 4
x 5
x 6
1
+
=
y 11 y
y 12 y
1
+
=
21
22
,
,
y
,
1,0
i
6,5,4,3
≥
=
,
y 11
y 12
21
=y 22
x i
,)0( x i
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
4 4 5.6183 6.9833 7.9627 8.9325 9.8958
4 4 4 4.7556 6.2414 7.7371 9.2410
1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1 1 1 1 1 1 1
3 2 3 2 3 3.3816 4.1441 5.1168 5.4115 6.3842 6.6785 7.6511 8.9178 9.9452 10.1842 10.8547 10.7494 9.2116 11.4505 11.8105 12.2610 10.4778 13.9826 13.7167 15.2906 13.0099 16.5145 15.6189 18.3246 15.5418 21.5779 19.4188 24.3978 20.6053 34.2205 28.9238 39.5821 33.2734 46.7863 37.8185 56.3336 45.0614
Độ tin cậy Tối ưu 0.11826 0.15205 0.2518 0.3491 0.4269 0.4870 0.5316 0.5639 0.5868 0.6140 0.6270 0.6361 0.63863 0.63868
25 26 30 35 40 45 50 55 60 70 80 100 150 200
Bảng 2.1: Giải pháp cho những nguồn ngân sách khác nhau
Phan Thị Ngọc Mai
Trang 13
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.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
in
=1. Gọi ri là độ tin cậy của module i được phát triển trong
ijy
j
1
thị trường, ta có zi + ∑ =
là độ tin cậy và chi phí của một version j của module i. Do
công ty với chi chí xi,
ij cr , ij
đó, đố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:
in
=
+
R i
zr i
i
yr ij ij
∑
j
1 =
Tương tự, gọi
iC là chi phí để thực hiện một module module i:
in
=
+
C i
zx i
i
yc ij ij
∑
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
n
n
i
B
(GP2)
≤
yc ij ij
zx i
i
∑∑
+ ∑
i
j
i
1 =
1 =
1 =
in
1
z
i
n
với
,
(GP3)
=
,2,1 …=
i
y ij
+ ∑
j
1 =
i
n
j
1,0
với
,
;
,
(GP4)
,1 …=
,1 …=
in
, i yz
=ij
trong đó:
(cid:131) (GP1) cực đại hoá độ tin cậy.
(cid:131) (GP2) đảm bảo tổng các khoảng chi tiêu là không vượt ngân sách.
(cid:131) (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
là các biến nhị phân.
ij zy ,
i
Phan Thị Ngọc Mai
Trang 14
(cid:131)
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
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
=
1 5x x + 2
với các điều kiện ràng buộc:
20
10
≤
+
x 2
2
≤
,
0
và
là các biến nhị phân.
x 1 x 1 ≥xx 2 1
1, xx
2
Phan Thị Ngọc Mai
Trang 15
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
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á
8.1
=
=
. Theo huynh hướng tự nhiên bạn sẽ làm tròn
trị tối ưu Z=11 với
x 1
x ,2 2
2x để
2
nó tiến về giá trị nguyên. Trong trường hợp này ta có thể làm tròn
. Tuy nhiên,
2 =x
2
=
=
khi ta làm tròn như vậy ta thu được cặp nghiệm
không thoả mãn điều kiện
x 1
x ,2 2
ràng buộc đầu tiên. Tất nhiên khi đó nếu chúng là làm tròn
2x theo chiều ngược lại
1
1
=
=
7=Z
ta được:
, và
thoả các điều kiện ràng buộc, nhưng không là
2 =x
x 1
x ,2 2
2
=
=
10=Z
nghiệm tối ưu. Nghiệm tối ưu khi
và hàm mục tiêu
. Hình 3.1 trình
x 1
x ,0 2
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à
có giá trị nguyên.
1, xx
2
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
1x và
hai biến nhị phân
2x và
3x với các ràng buộc:
1
3
≤
≤
x 1 x
0
1
≤
≤
2
0
1
≤
≤
x 3
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
Phan Thị Ngọc Mai
Trang 16
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
chúng ta có 12 giải pháp trong đó có: (3 giá trị có thể thực hiện được cho
1x )*(2 giá trị
có thể thực hiện được cho
2x )*(2 giá trị có thể thực hiện được cho
3x )
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ó
576,048,1
220 =
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
30
100 2
.1
268
10 x
=
biến nhị phân khi đó chúng ta cần đến
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 đủ
Phan Thị Ngọc Mai
Trang 17
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
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:
(cid:131) 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.
(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.
Phan Thị Ngọc Mai
Trang 18
(cid:131) Bài toán quy hoạch nguyên số lượng biến và các cấu trúc đặc biệt
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 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
xf
cx
=)(
(3.1)
với các điều kiện ràng buộc có dạng:
b
xA ≤.
(3.1a)
10or
x =
(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à
0
S
Ax
b
:{ x
=
≤
và x là biến nhị phân. Ta cho một đường
kP đi từ
kv . Tại
kv được
0v đến
xác định bằng việc lựa chọn một biến tự do
jx sao cho:
k
k
∩
∩
S
:{ xx
},0
:{ xx
=
=
(3.2)
{ S
}}1
j
j
Mỗi đường
kP 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
NWk ⊆ và giả sử
S
:{ j
và
}1=jx
=+ k
Wj ∈ k
S
:{ j
và
=− k
Wj ∈ k
}0=jx
S
:{ j
}
=
0 k
Wj ∉ k
Một sự hoàn thành
kW là một sự ấn định của những biến nhị phân đến những
0
biến tự do được chỉ rõ bởi chỉ số được đặt trong
kS .
Bounds: Bài toán được xét tại
kv :
c
min
)( xf
=
+
xc j
j
j
∑
∑
Sj ∈
0 k
∈ + Sj k
điều kiện ràng buộc:
m
,1
,
≤
−
=
=
(3.3)
xa ij
j
b i
a ij
is i
∑
∑
Sj ∈
0 k
∈ + Sj k
x
or
j
S
0
,1
=
∈
j
0 k
Phan Thị Ngọc Mai
Trang 19
…
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
k
T
or
j
S
0
,1
=
=
∈
Giả sử
, giải pháp nới lỏng
kx đạt được
{ : xx
} . Vì
j
0 k
0≥jc
k
x
j
S
f
c
,0
=
∈
=
. Như vậy
. Hơn nữa, nếu
bằng việc
thiết
lập
j
j
0 k
∑ +∈
kSj
k
f
f
c
s
,
)
0
=
=
=
≥
thì
kx thỏa mãn (3.3) và
.
k IP
j
( 1 s
ms
∑ +∈
kSj
… ,
Fathoming: node k có thể được thăm dò nếu:
k
f
k f =
(a)
0
f
f k ≥
(b)
Điều kiện (a) xẩy ra khi
kx thỏa mãn (3.3). Một điều kiện đủ để đánh giá (b) giả
sử cho một số i thỏa:
t
,0min{
}
>
i
a ij
s i
= ∑
∈ 0 Sj k
Trong trường hợp không có sự hoàn thành của
kW có thể thỏa mãn ràng buộc i, vì
∞=kf
, và
vậy
kv được thăm dò. Ví dụ, xét ràng buộc:
4
2
3
11
5 −=
+
+
−
−≤
=
x 1
x 2
x 3
x 4
xa ij
j
s i
∑
0 kSj ∈
t
11
8 >−=
−=
Tính toán cho
vì vậy node k được thăm dò.
i
s i
Partitioning and Branching: chúng ta muốn xác định tập con của những biến tự
}0
=
<
do tại
.
kv của nó ít nhất phải bằng 1 trong một sự khả thi của
kW . Cho
Q k
:{ si i
, thì
kx khả thi. Nếu
, cho
Nếu
kv được thăm dò vì
j
S
:{ j
=
∈
và
với
0 }kQi ∈ R
k 0
k Có ít nhất một biến có chỉ số là một phần tử của kR bằng 1 trong bất kỳ sự khả x ∈, thi của , và sau đó phân Rj
k j kW . Vì vậy, chúng ta có thể phân chia trên một số nhánh nút kế tiếp tương ứng . Quy tắc sau đây lựa chọn một kRj ∈ trong một sự 1=jx m I ,0max{ } = − −= không thoả k s
i s
i nỗ lực để di chuyển về phía khả thi. Định nghĩa ∑ ∑ i 1
= Qi
∈ k khả thi cho bài (3.3). Việc chọn thừa không khả thi jx node kế m I )(
j ,0max{ } = k s
+−
i a
ij ∑ i 1
= và px được lựa chọn như sau: Phan Thị Ngọc Mai Trang 20 φ=kQ φ≠kQ 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 ) )(
j = (
pI
k k min
Rj
k∈ Ví dụ nếu các ràng buộc tại kv là 2 2 6 − + 3
−≤ − x
2 3 4 x
3
2
−≤ + − − x
3 7 5 5 4 x
1
x
1
+ x
2
− ≤ x
1 x
2 x
3 },2,1{ I I )2( 2 = ,3)1(
= = thì vì vậy R
k k k 2x được chọn là biến được phân chia. Giải thuật: 0 0 … f ,1{ },
fn , = −∞= −∞= . Di chuyển sang bước 2. ,
Sv
0 0
0 k f c = . Nếu với mọi i cho j kv cho 0≥is ∑ +∈ kSj 0 k k k f f f min{ f , f } = = 0
f = và cho . Di chuyển sang bước 3. k
IP k 0 f f f k ≥ k
f = hoặc nếu thăm t > for mọi i hoặc nếu
i s
i dò kv và di chuyển sang bước 4. Nếu có kv thì di chuyển sang bước 5. Ngược lại chọn nhánh gần nhất và di chuyển sang bước 2. px như trong công thức (3.2), ) min I j
)( = trong đó . Phân nhánh về phía pI
(
k k px . Di chuyển sang bước 2. Rj
k∈ 0 0 f f ∞< ∞= thì không có giải pháp khả thi. Nếu thì có 0 f một giải pháp khả thì và là giá trị tối ưu. Hàm mục tiêu: min f 5 7 x 10 3 x = + + + + x
1 2 x
3 4 x
5 với điều kiện ràng buộc: 3 5 4 − + − − 2
−≤ + x
1 x
2 x
3 2 6 3 2 0 2 − + + ≤ − x
5
x
5 2 3 x
1
− x
2
+ x
3
+ x
4
x
4
1
−≤ x
4
or , 0 x
5
1 = x
2
,
x
1 x
3
x
5 0 0 … S S S f f ,1{ },5, , );1,0,2( ,3 = = = −∞= ,
s
−=∞= − ,
φ … và 0 =I 0
0 +
0 −
0 }4,3,1{ .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 0 =R Phan Thị Ngọc Mai Trang 21 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 I I )1( ,4 = ,3)3(
= 5)4(
= 3=p giá . Cực tiểu được tìm thấy liên quan đến vì vậy chúng 0 0 0 . Cây tôi lựa chọn 3x cho vùng phân chia con và nhánh trong phương hướng của 13 =x được trình bày trong hình 3.3. 0 x3=1 x3=0 1 4 x2=1 x2=0 2 3 2 f s ),3( ,10 },5,2{ )2( ,0 )5( 2 = = = ),1,3,3(
− = = = Tại , vì vậy chúng ta ,
Pv
1
1 R
1 I
1 I
1 0 f ∞= chọn . Tại 2x cho việc phân chia. Không có giải pháp khả thi vì vậy 0 2 1 )0,3,0(=s f f ),2,3( 17 .17 17 = = 2
=f = f = và , vì vậy Chúng ta đưa vào và ,
Pv
2
2 s ),2,3( }5{ = = )1,3,3(
− thăm dò và . Nhưng do 2v . Tại bước 4, tính toán tại 3v với P
3 3 =R 3−= t s 2
>−= nên thăm dò và chúng ta quay về 2 2 3v được 4v . Tại 4v , s ),3( )1,0,2( }4,1{ = −= − t 1 0
>= −= và . Nhưng do P
4 4 =R cho nên 4v được thăm dò. Ở s
3 3 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 x )0,0,1,1,0(*,17 = = thúc giải thuật. Giải pháp tối ưu . f IP Phan Thị Ngọc Mai Trang 22 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 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]. 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 )(
xf với các điều kiện ràng buộc: ,0 i ,..,1 m = = (4.1) j ,..1
q ,0)(
≤ = trong đó: )(
xh
i
xg
j
Dx
∈ (cid:131) : là hàm mục tiêu. (cid:131) , các điều kiện ràng buộc là các bất đẳng thức, và các đẳng )(xf thức. (cid:131) nRD ⊂ : miền xác định. (cid:131) Dx ∈ : 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. )(xhi )(xg j 2Rx ∈ : Hàm mục tiêu: 2 2 với các điều kiện ràng buộc: , 03 ) ≤− = − , ) = x
2
01
≤− 2 2
x
1
2
x
2 , ) 0 = ≥ xxg
(
1
2
1
xxg
(
2
1
xxg
(
2
1 3 x
1 Phan Thị Ngọc Mai Trang 23 min ( ) ( )3 ( )2 = − + − xxf
,
2
1 x
1 x
2 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 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ả ) ( ) đạt giá trị nhỏ nhất. Chú ý rằng điểm thỏa mãn thi sao cho ,
(
1 xxf
2 ,
1 xx
2 2 2 ( )3 ( x )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). x
1 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 f )1,2( 2 = là giá trị tương ứng của đ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. Phan Thị Ngọc Mai Trang 24 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 Hàm mục tiêu: min ( , ) |2 | |2 |
= − + − xxf
2
1 x
1 x
2 với các điều kiện ràng buộc: , ) 01 = + =− 2
x
2 , ) 0 = − ≥ xxh
(
1
1
2
(
xxg
1
1 2 2
x
1
x
1 2
x
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 ) đạt giá trị nhỏ nhất. Trong trường hợp một điểm trong vùng khả thi sao cho (
,
1 xxf
2 này, không có điểm nào để cho hàm mục tiêu đạt giá trị nhỏ nhất. D x ∈* được gọi là cực tiểu địa phương của f qua xf
)( xf
( *) ≥ D . Nếu có một lân cận 0>ε sao cho với mọi Dx ∈ trong khoảng εcủa Phan Thị Ngọc Mai Trang 25 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 *x x ≠ x − *x ε< *x (đó là Dx ∈ và ) và thì *x được gọi là điểm cực tiểu địa phương của f qua D . nRD ⊂ 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ỳ Một tập hợp của tập đó. Vậy tập lồi được định nghĩa [4]: X D 1(),1,0( ⇔ − + ∈ α )
α X
α D là tập lồi ,
DXX
∈∀∈
2 ,
1 1 2 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. Đố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 )(xf định trên một tập lồi. Hàm nhiều biến xác định trên tập lồi D được gọi là một hàm )1,0(∈α lồi nếu với mọi M, N thuộc D và M ≠ N, với mọi thì ta đều có: 1( Mf
( ) Nf
( ) f 1(( ) − )
α + α ≥ − )
α NM
−
α )(xf )(xf xác định trên một tập lồi D. Giả sử có các đạo hàm Hàm nhiều biến riêng cấp 2 liên tục. ( ) , , xd , , Nếu tại mọi điểm nx ndx xx … thuộc D, với mọi
,
1 2 1 … không đồng thời
, dx
2 bằng 0: 2 )(xf , …
, , 0) (cid:131) thì là hàm lồi trên D. xxfd
(
2 1 ≥nx 2 , …
, , 0 )(xf (cid:131) thì là hàm lồi ngặt D. xxfd
(
2 1 >nx
) 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 fd 2 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. )(xf xác định trên miền lồi D. Giả sử hàm )(xf D*∈x có các đạo hàm riêng cấp hai liên tục. là một điểm dừng. Phan Thị Ngọc Mai Trang 26 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 (xF *) D*∈x Với mỗi , gọi ma trận Hessian tại *x , ký hiệu là ma trận vuông cấp . n có thành phần dòng i cột j là ∂ 2
f
i xx
∂∂ j *) là định thức ma trận con có được từ ma trận Với mỗi k từ 1 đến n, gọi (xFk *) (xH 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 )(xf )(xf )(xf của hàm trên X nếu là hàm lồi trên D. Điều kiện để lồi trên D là với D x ∈* D*∈x *) (xF mọi , ma trận xác định dương. Tức là với mọi , với mọi k từ 1 đến 0 . n, ta đều có >xFk
*)
( 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: Đâ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{ :)( } xf nRx
∈ Rf
: 1
R trong đó n → . Cho *x được xem như một điểm và giả sử f hai lần đạo *) *) xf
)( xf
( *) ≥ của *x , trong đó với . Giả sử hàm liên tục trong lân cận (xNε (xNx
ε∈ 1=v tồn tại một vectơ v , sao cho , ta có: *( *) xf (
xf + − 0 ( *) *)
vxf ( ≤ = ∇= xfD
v lim
0
t
→ )
tv
t v = v −= và nghĩa là Tiếp theo chúng ta xem xét những trường hợp je je *) 0 = . Chúng ta có điều kiện cần thứ nhất: xf
(
∂
jx
∂ *) 0 ∇ xf
( = (4.6) x tv *) = *
x + có thể được mô tả dưới dạng (xNε 0>t ε<< t0 * * t x tv x x = + = − ε≤ trong đó ( vì ). Chúng ta được: 2 (
xf *) )(
xf xf *( tv ) (
xf *) *)
vxf ( T
xFv *( )
vtv ≤ = + = t
∇+ + α+ (4.7) t
2 Phan Thị Ngọc Mai Trang 27 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 ]1,0[∈α Gọi ma trận Hessian, ký hiệu F là ma trận vuông cấp n của f và . Nhưng 2 *) 0 ∇ xf
( = 0 > và 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à t
2 0 xFvT *( )
vtv ≤ α+ (4.8) Rf
: 1
R n → hai lần đạo hàm liên tục xung quanh một lân cận của *x . Nếu f có một cực tiểu tại *x thì: *) 0 ∇ xf
( = (i) (xF *) (ii) là một đại lượng xác định dương Rf
: 1
R n → hai lần đạo hàm liên tục xung quanh một lân cận )(xf *) 0 ∇ xf
( = của *x . Khi đó một điều kiện đủ để cho có một cực tiểu tại *x , là và (xF *) là một đại lượng xác định dương. 2 Rf
: 1
R xf 9 4 3)(
= + − + → được định nghĩa bởi . Tìm 3
x
1 2
x
2 x
1 x
2 giá trị cực trị của hàm này. 0 ∇ xf
)( = xf
)( 0[ ]0 9[ 29 ]4 ∇ = = − + Ta được 2
x
1 x
2 2 Giải hệ phương trình trên thu được và . 1 ±=x
1 −=x
2 )2,1( =x )2,1( − F =− (cid:131) ta được là đại lượng xác định 0
2 0
2 18
1x
⎡
⎢
0
⎣ ⎤
=⎥
⎦ 18
⎡
⎢
0
⎣ ⎤
⎥
⎦ FvT v v 0 )2,1(
− = + > . Như vậy tại điểm (1, -2) là một điểm dương vì 2
v
18
1 2
2 cực tiểu. 1x )2,1(
=−− F )2,1( −−=x (cid:131) ta được và khi đó 18
0 0
2 18
0 0
2 ⎡−
⎢
⎣ ⎤
=⎥
⎦ ⎡−
⎢
⎣ ⎤
⎥
⎦ FvT v 0≠v )2,1(
−− −= có thể bằng 0 khi . Do đó điểm (-1,-2) 2
v
118 2
2v+ 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. Xét bài toán có dạng sau: Phan Thị Ngọc Mai Trang 28 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 min }0 xf
:)({ ≥x (4.9) 0* ≥x Giả thiết rằng f có một cực tiểu *x , trong đó . Khi đó sẽ tồn tại một lân *) *) xf
)( xf
( *). 0≥x ≥ của *x , do đó với bất kỳ có , thì Ta có thể cận (xNε (xNx
ε∈ x tv = *
x + 0>t viết , trong đó v là một vector và . Giả sử f hai lần đạo hàm qua *) . Từ (4.7) ta có: (xNε 0 *)
vxf ( T
xFv *( )
vtv ∇≤ + α+ t
2 Các điều kiện cần để f có một cực tiểu tại *x : *) 0 0 = nếu * >jx xf
(
∂
jx
∂ *) 0 0 ≥ nếu * =jx xf
(
∂
jx
∂ Chúng được tổng kết trong mệnh đề sau đây: trong bài toán (4.9) bao gồm: 0 xf
( ∇ (4.10) *)
≥
xxf
0**) ( = ∇
x
0*
≥ Hàm mục tiêu: Minimize xf x 2 2 2 3)(
= + + − − − 2
x
1 2
2 2
x
3 xx
1 2 xx
3
1 x
1 với các điều kiện ràng buộc: 3,2,1 ≥ i ,0 = xi tiểu: 0 6 2 2 2 ≤ = − − − (1) x
1 x
2 x
3 f
∂
x
∂
1 0 6( 2 2 )2 = = − − − (2) x
1 x
1 x
1 x
2 x
3 f
∂
x
∂
1 0 2 x 2 ≤ = − (3) 2 x
1 f
∂
x
∂ 2 Phan Thị Ngọc Mai Trang 29 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 0 x 2( x x = − = (4) 2 2 2 x
)2
1 f
∂
x
∂ 2 0 2 2 = − ≤ (5) x
3 x
1 f
∂
x
∂
3 0 2( ≤ = − (6) x
3 x
3 x
3 x
)2
1 f
∂
x
∂
3 ,0 x ,0 0 ≥ ≥ ≥ (7) x
1 2 x
3 x = = )1,1,1(* =x Ta tìm được 1 điểm dừng . Ma trận Hessian ở : x
1 2 x
13
= 6 2 2 là một đại lượng xác định dương. Do đó ta có một cực )1,1,1(F = −
−
022
202 −
− ⎤
⎥
⎥
⎥
⎦ ⎡
⎢
⎢
⎢
⎣
tiểu tại điểm *x . Rf
: 1
R Cho n → và xét bài toán sau: Hàm mục tiêu: với các điều kiện ràng buộc: Minimize )(xf (4.11) n xh
)( ( ),.., )) = , mỗi 1
→ , và
R 0 =xh
)( Trong đó xh
(
m xh
(
1 Rh
:
i xf
)( xf
( *) ≥ *x . Khi đó phải tồn tại một 0>ε sao cho với mỗi một cực tiểu tại 0 =xh
)( *) *) /)( và . Giả sử 2Cf ∈ tại mọi , và giả sử rằng mỗi đạo xh
∂
i x
∂
i (xNx
ε∈ (xNε 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: *) *) (cid:34) *) (cid:37) = (4.12) (
xh
∂
x
∂ *) *) (cid:34) (
xh
∂
1
x
∂
1
(cid:35)
(
xh
∂
m
x
∂
1 (
xh
∂
1
x
∂
n
(cid:35)
(
xh
∂
m
x
∂
n ⎤
⎥
⎥
⎥
⎥
⎥
⎦ ⎡
⎢
⎢
⎢
⎢
⎢
⎣ Điều này tương ứng với việc cho rằng *x là điểm dừng. nm < . Để bài toán (4.11) có ( 0 *),.., xh
( *) =xh
*) ∇ được gọi là một điểm dừng, nếu các vector là độc lập xh
(1 m∇ tuyến tính. Phan Thị Ngọc Mai Trang 30 *x thỏa mãn các điều kiện ràng buộc 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 S :{ xhx
)( }0 = = tiếp xúc với T y
:{ yxh
)( }0 = ∇ = . Để đơ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, *x của mặt 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 *x dưới dạng còn lại n - m biến; ví dụ: ( ,.., ) i m ,..,1= với . Hơn nữa, các hàm x
i =φ
i x
m x
n 1 iφlà duy nhất và khả thi trong lân cận + ( ,.., ) x
" ( ,.., ) x ' x
"( ),.., x
))"( x =
' = và , ta có được ký hiệu của *x . Cho x
1 mx x
m x
n (
φ=
1 mφ 1
+ )"(xφ . Công thức (4.11) được viết lại như sau: nm < , với ma trận Jacobi có rank là m, = = Φ (4.13) Tx
)" ),"((
x
φ x
)"(
φ = . Vì thế bài toán ( 4.13) phải có một cực tiểu trong đó 0)"( Φ∇ x = x
"* ( ,.., ) = . Được tạo ra bởi định lý 4.2.1 là . *
x
m *
x
n 1
+ j n m = + ,.., = + Nhưng ∑ ∑ Φ∂
∂
x x
∂
i
x
∂ ∂
φ
i
x
∂ f
∂
x
∂ i 1 mi
+= 1
= j f
∂
x
∂
i j f
∂
x
∂
i f
∂
x
∂
1 j j f
∂
x
∂
m ⎡
⎢
⎣ ⎤
⎥
⎦ ∂
φ
x
∂
(cid:35)
∂
φ
x
∂
m ⎤
⎥
⎥
⎥
⎥
⎥
⎦ ⎡
⎢
⎢
⎢
⎢
⎢
⎣ xf )'( / ,.., / ], xf )"( / ,.., / ] ∇ f
[
∂= f
∂ ∇ [
f
∂= f
∂ ∂φ / x∂
" Do đó và là một x
∂
1 x
∂
m x
∂
m 1 x
∂
n + )1 [ / ,.., −nm
(* min xxf
)",'({ min f x
)" min x
)"( ),"((
x
φ bao gồm những cột có dạng . Từ ma trận có kích thước ∂φ
1 jx∂ ∂φ
m T
x ]
j đó ta được: xf xf 0 x
)"( )"( )"( Φ∇= ∇= ∇+ (4.14) φ
∂
"
x
∂ 0 xh
)( x
),"(( x
)" = h
φ= . Vì thế: Ngoài ra 0 + = (4.15) h
∂
x
'
∂ h
∂
x
"
∂ h
∂
x
"
∂ / ∂ và là những matrận con đầu tiên có m hàng và n-1 cột của trong đó công thức (4.12). Từ công thức (4.16) ta có: 1 − = h
∂
x
"
∂ ∂
φ
x
"
∂ h
∂
x
'
∂ ⎛
⎜
⎝ ⎞
⎟
⎠ Vì thế được tạo ra từ (4.14) điều đó: Phan Thị Ngọc Mai Trang 31 ' h ∂
/ x
∂ h ∂
/ x
"
∂ 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 )"( 0 xf ∇ T λ
T
− = h
∂
x
"
∂ trong đó: 1
− xf Tλ ∇= h
∂
'
x
∂ ⎛
)'(
⎜
⎝ ⎞
⎟
⎠ tại "*x . Sắp xếp lại: )'( 0 xf Tλ ∇ − = (4.17) h
∂
x
'
∂ Kết hợp hai công thức (4.16) và (4.17) và xem lại các ràng buộc bang đầu của bài toán (4.11). Chúng ta có được các điều kiện cần: *) 0 (
xh = Tλ
∇−
0 (
xf
∇
xh
*)
( *)
= *) (xh∇ là một matrận cấp có m hàng và n cột. cho một cực tiểu tại *x , trong đó xL
,( xf
)( xh
)( )
λ Tλ = − , những điều kiện cần này có thể được phát biểu bằng một Cho định lý như sau: thành phần ih của h hai lần đạo hàm liên tục trong một lân cận của *x , và nếu ma trận mR∈*λ Jacobi có đầy đủ m hàng, khi đó tồn tại một sao cho: (4.18) *) λ *) *) 0 (
xf (
xh *
λ ∇= − ∇ = Hàm L là Lagrangian và các thành phần iλcủa λlà khác nhau được gọi là Lagrangian multipliers. *) λ *) 0 (
xh −= = *,
(
xL
∂
x
∂
*,
(
xL
∂
λ
∂ = với điều kiện ràng buộc: ( , ) 2 xxf
1
2 xx
21 2
x
1 2
+ x
2 Lời giải: .1 = . Ta có: 2
x
1 2
x
2 Theo công thức (4,17) ta có: Phan Thị Ngọc Mai Trang 32 ( , , 2 )1 )
λ = − (
λ + − xxL
2
1 xx
21 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 0 = − = x
2 x
2
λ
1 2 0 = − = x
1 x
2
λ
2 2
x
1 2
x
2 01 = + =− L
∂
x
∂
1
L
∂
x
∂
2
L
∂
∂
λ , Giải hệ 3 phương trình trên ta được các điểm dừng như sau: )1,2/2,2/2(A , , . Những kết quả trên chỉ là điều kiện cần. Vì vậy, nếu có những giải pháp tối ưu tồn tại, thì phải xuất hiện tại một hoặc nhiều điểm. Vì vùng ràng buộc ,2/2 )1,2/2 )1,2/2,2/2 D ,2/2( )1,2/2 −B
( − (−C − là bị đóng và chặn, theo định lý Weierstrass ngụ ý f có cả một 2
x
1 2
x
2 cực đại lẫn cực tiểu trong S . Vì khi kiểm tra, chúng ta thấy giá trị cực tiểu của f là -1 S {( :) }1 = + = xx
,
1
1 xuất hiện tại 2 điểm , . Tương tự , cực đại cũng )1,2/2,2/2 D ,2/2( )1,2/2 −C
( − − − xuất hiện tại hai điểm , có giá trị 1. Sử dụng lý luận cho phép tính cổ điển, chúng ta sẽ dẫn xuất ra những điều kiện cần và đủ thứ hai cho *x là một cực tiểu của bài toán ( 4.11). )1,2/2,2/2(A ,2/2 )1,2/2 −B
( − với điều kiện )(xf mR∈λ . Khi đó tồn tại một vectơ có dạng sau: ràng buộc 0 =xh
)( Tλ
∇− (4.20) xf
( *) xh
( *) 0 ∇ = T
*) Nếu chúng ta chứng tỏ T là mặt phẳng tiếp xúc , khi đó ma T y
:{ xh
( y }0 = ∇ = Tλ− Δ
= là xác định dương trên T ; đó là với mọi trận xL
( *) xF
( *) xH
( *) xLyT
( *) 0 ≥y .Ty ∈ ( 0 =xh
*) và một Tλ
∇− Tλ− mR∈λ sao cho và ma trận là một đại xf
( *) xh
( *) 0 xL
( *) xF
( *) xH
( *) ∇ = = lượng xác định dương trên với . Ta có . T y
:{ xh
( *) y }0 0 xLyT
( *) 0 = ∇ = ∈ yTy , ≠ >y Khi đó *x là một cực tiểu của f với điều kiện ràng buộc . Xét tiếp ví dụ 4.2.3, chúng ta có ma trận: 0 =xh
)( Ngoài ra ta cũng có: Phan Thị Ngọc Mai Trang 33 xL
( *) = 0
2 2
0 0
2 2
0 ⎡
λ
⎢
⎣ ⎤
⎥
⎦ ⎡
⎢
⎣ ⎤
−⎥
⎦ 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 *
yx
1
1 *
yx
2 2 T {( :) }0 = + = yy
,
1 Xét hai điểm , ta có : )1,2/2,2/2 D ,2/2( )1,2/2 1−=λ −C
( − − − và 2 2 2 2
y
1 2 nó thỏa mãn hai cả hai điều kiện cần và đủ cho một cực tiểu. 22 y
1 L , T {( :) y } = = = ( ) 8 0 yT Ly ≥ = yy
,
1 y
1 ,
yy
1 y 22
22 22 ⎡
⎢
⎣ ⎤
⎥
⎦ ⎡
⎢
⎣ ⎤
⎥
⎦ ⎞
=⎟⎟
⎠ ⎛
⎜⎜
⎝ tương tự tại hai điểm , ta có 1=λ : )1,2/2,2/2(A ,2/2 )1,2/2 −B
( − và 2 2 Vậy ta có L xác định âm cho nên đây là một cực đại. L , T {( :) y } yT Ly 0 = −= −= = 8 2
y
1 ≤ yy
,
1 y
1 2
−
2 2
2 − ⎡
⎢
⎣ ⎤
⎥
⎦ Mô hình tổng quát NLP mà chúng ta xem xét bao gồm cả các ràng buộc tuyến tính và phi tuyến. Hàm mục tiêu: với các điều kiện ràng buộc: Minimize )(xf (4.24) xh
)( 0 = 1 n n m n q xg
)( 0 ≥ và toàn bộ các hàm đều trong 2C . trong đó: xh
( *) ,0 xg
( *) 0 = ≥ :
Rf ,
RhR : ,
RgR : R → → → và với 0 J j ∈ . Khi đó *x được gọi là một điểm dừng của các ràng buộc nếu các =xg j
(
*) véctơ với và là độc lập tuyến tính. *) *) mi ≤≤1 (xhi∇ (xg j∇ mR∈λ toán (4.24) và giả sử rằng *x là một điểm dừng. Khi đó tồn tại một vector và qR∈μ sao cho: một vector T
λ
∇− T
μ
∇− (4.25a) xf
( *) xh
( *) xg
( *) 0 ∇ = (4.25b) (4.25c) *) 0 =xgTμ
( 0≥μ (4.25d) Phan Thị Ngọc Mai Trang 34 xh
( *) ,0 xg
( *) 0 = ≥ 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 Cghf
,
, mR∈λ và một vector dừng. Nếu *x là một cực tiểu của (4.24) thì tồn tại một vector ∈ và *x là một điểm Tλ− từ (4.25a) – (4.25d), ta có là xác định dương tại *x . 2 0 xL
( *) xF
( *) xH
( *) *) μ qR ∈ μ , ≥ = (xGT∇− μ Cghf
,
, qR∈μ mR∈λ và thoả các ràng buộc từ (4.25a – 4.25d) và ma trận tiểu là tồn tại ∈ . Điều kiện để điểm *x là một cực Tλ− Hessian xác định dương trong mặt phẳng xL
( *) xF
( *) xH
( *) *) = (xGT∇− μ với mọi , trong đó j xgj
( T xh
( *) y ,0 *) y 0 }'J J *) ,0 }0 y
:{'
= ∇ = ∇ = j ∈ :{'
= = > xg j
( μ
j Hàm mục tiêu: 2
x
1 2
x
2 2
x
3 Các điều kiện ràng buộc: 3 + = = 0 x
1
−= x
2
− + ≥ 2
x
2 h
1
g
1
g 2 16 − −≥ 2 x
3
x
3 g x
2
g g ,0 ,0 0 2
x
1
x
−−=
1
≥ = = ≥ = ≥ 3 x
1 x
2 x
3 5 4 Điều kiện cần bao gồm các ràng buộc: min f 2 = + + + + + − xx
3
1 xx
2
1 x
1 x
3 1
5 1
2 + 4 1 2 − 1 − 1 0 x x 0 −+
x
3 x
1 1
2 2 2
x
1 2 − 1 − 2 − − 1 − − 0 1 x − 0 − − = μ
1 μ
2 μ
3 μ
4 μ
5 3 ( ) 0 − − + = 2
x
2 x ( 2 )16 0 − + = j 2
x
1
x
−−
1
) ( ( x
3
x
3
) ,0 ( ) ,0 ,0 5,..,1 = = = ≥ = 0 x
1 2 − 0 0 0
1 ⎛
⎜
λ
⎜
⎜
⎝ ⎞
⎟
⎟
⎟
⎠ ⎛
⎜
⎜
⎜
⎝ ⎞
⎟
⎟
⎟
⎠ ⎛
⎜
⎜
⎜
⎝ ⎞
⎟
⎟
⎟
⎠ ⎛
⎜
⎜
⎜
⎝ ⎞
⎟
⎟
⎟
⎠ ⎛
⎜
⎜
⎜
⎝ ⎞
⎟
⎟
⎟
⎠ ⎛
⎜
⎜
⎜
⎝ ⎞
⎟
⎟
⎟
⎠ + − x x
1 2
3 1
2 ⎛
⎜
⎜
⎜
⎜
⎜
⎝ ⎞
⎟
1
⎟
⎟
⎟
⎟
⎠ x
1 2
,0
μ
4 x
2 x
3 jμ ,2/5 13 μ
1
μ
2
μ
3 μ
5 = Giải hệ phương trình trên ta được )5,2,1(*x μ
=
1 λ
1 Bước kế tiếp chúng ta kiểm tra ma trận 4 1 1 002 9 1 1 − = + là đại lượng xác định 5
2 1
−
1 −
2
0 0
5/2 020
000 1
−
1 0
5/2 7
0 ⎡
⎢
⎢
⎢
⎣ ⎤
⎥
⎥
⎥
⎦ ⎡
⎢
⎢
⎢
⎣ ⎤
⎥
⎥
⎥
⎦ ⎡
⎢
⎢
⎢
⎣ ⎤
⎥
⎥
⎥
⎦ )5,2,1(*x dương. Do đó là một điểm cực tiểu. Phan Thị Ngọc Mai Trang 35 (xL *) 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 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 (chi phí được tính theo đơn vị triệu đồng, độ tin cậy được tính theo phần trăm). Thông qua việc giải quyết bài toán tìm độ tin cậy lớn nhất không vượt quá giới hạn chi phí đã cho, và ngược lại, tìm khoảng chi phi nhỏ nhất để phần mềm có độ tin cậy là một hằng số xác định trước. Trong giai đoạn thiết kế phần mềm, những nhà quản lý sẽ ước lượng độ tin cậy của phần mềm dựa vào chi phí đã cho. Với mục tiêu làm thế nào để phân phối chi phí giữa việc mua và phát triển các module một cách hợp lý để tạo ra phần mềm có độ tin cậy mong muốn. Để giải quyết bài toán, tôi xin đề xuất một giải pháp chia bài toán thành hai bước: (cid:131) Bước một, phân hoạch bài toán thành hai phần: phần các module mua và phần các module phát triển trong công ty. (cid:131) Bước hai, kết hợp hai bài toán lại thông qua đó tìm độ tin cậy lớn nhất có thể đạt được của phần mềm sao cho không vượt quá giới hạn ngân sách đã cho. Database indexing (6) Index generator (3) Keyword (5) Parser (1) Version 11 Analyzer (4) Stemmer (2) Version 12 Version 21 Version 22 Phan Thị Ngọc Mai Trang 36 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 Lý do để phân hoạch bài toán thành hai phần: (cid:131) Phần module mua: các biến trong phần module mua là các biến nguyên nhị phân (chỉ nhận giá trị: 0 hoặc 1). Hơn nữa theo cơ sở lý thuyết đã trình bày trong bài toán quy hoạch nguyên có thể dễ dàng thực hiện cho phần module mua. (cid:131) Phần module phát triển trong công ty: các biến trong phần module phát triển trong công ty là các biến thực. Hàm mục tiêu là một hàm nhiều biến, các điều kiện ràng buộc là các phương trình phi tuyến. Trong bài toán quy hoạch phi tuyến cũng có thể dễ dàng thực hiện cho phần module phát triển trong công ty. Do vấn đề đặc biệt này, ta có thể phân hoạch bài toán thành hai bài toán con để giải quyết. Giả sử kinh phí cung cấp cho dự án phần mềm này là B. Ta sẽ trích ra phần B’ để mua các module, phần còn lại B-B’ sẽ được dùng vào việc phát triển các module trong công ty. Nhiệm vụ của bài toán tối ưu hóa các module mua là với chi phí đã cho để mua các module mua cần phải đảm bảo: (cid:131) Các module là các module đơn. (cid:131) Mỗi module phải có ít nhất một version trên thị trường. (cid:131) Mỗi module phải mua duy nhất một version trong số các version đã có trên thị trường. m m (cid:131) Tổng chi phí để mua các module thoả điều kiện (max)
c
i (min)
c
i ∑ ∑ i i 1
= 1
= là chí phí của version rẻ và đắt tiền nhất của module i . (min),
c
i (max)
c
i Ta có thể xây dựng bài toán tối ưu hóa các module mua như sau: Hàm mục tiêu m n
i (P11) B ' ≤ ≤ , Maximize ∑∑ i j 1
= 1
= với các ràng buộc sau: n m i yr
ij
ij (P12) ∑∑ i j 1
= 1
= Phan Thị Ngọc Mai Trang 37 B ≤ ' yc
ij
ij 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 in j 1
= 1 (P13) =∑
ijy (P14) trong đó: (cid:131) : hằng số độ tin cậy và chi phí của version cần mua. ij cr ,
ij (cid:131) : biến nguyên nhị phân (chỉ nhận giá trị 0 hoặc 1). ijy (cid:131) m : số lượng các module mua. (cid:131) : số lượng version của module i. in (cid:131) (P11) : cực đại hoá tổng độ tin cậy của các module mua. (cid:131) (P12) : đảm bảo tổng các khoảng chi tiêu nằm trong phạm vi ngân sách phần mua. (cid:131) (P13) : đảm bảo mỗi module chỉ mua duy nhất một version. (cid:131) (P14) : đảm bảo các biến đều là biến nhị phân. 0or 1 yij = 6 = module một có hai version trên thị trường có chi phí và độ tin cậy tương c
11 = c
,5 12 ,7.0 9.0 = = ứng là , tương tự như vậy module hai có hai version trên thị trường với r
11 r
12 8 95.0 = c = = = chi phí và độ tin cậy tương ứng như sau: , . Tổng chi phí c
21 ,7 22 r
21 r
,87 22 nhà quản lý cung cấp để mua hai module là B. Với mục tiêu đưa ra mỗi module mua chỉ được mua duy nhất một version trên thị trường, làm thế nào đó để nhà quản lý có thể phân phối chi phí cho việc mua các module mua sao cho có độ tin cậy lớn nhất mà không vượt quá giới hạn ngân sách đã cho. Dựa vào những dữ kiện đã cho ta xây dựng được bài toán như sau: Hàm mục tiêu Maximize Z = + + + yr
11 11 yr
12 12 yy
21 21 yr
22 22 với các ràng buộc sau: 22 22 B ' + + ≤ yc
21 yc
22 13
1
,
1 ijy là biến nguyên nhị phân 22 21 +
11
+ y
12
+ y yc
12
=
= Phan Thị Ngọc Mai Trang 38 yc
11
y
11
y 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 Đặc tính của module phát triển trong công ty: (cid:131) Các module phát triển trong công ty có thể là các module đơn cũng có thể là module tích hợp. (cid:131) Module đơn là những module mua, cũng có thể là các module được phát triển trong công ty. (cid:131) Module tích hợp được tích hợp từ các module đơn hoặc từ các module tích hợp khác. Dựa vào các đặc tính này kết hợp với các công thức (2.1) và (2.3), và những yêu cầu đặt ra là tổng chi phí dùng cho việc phát triển phần mềm không vượt quá giới hạn ngân sách đã cho. Ta có thể xây dựng bài toán tối ưu hóa các module tự phát triển trong công ty như sau: (P21) Max n S.T. (P22) mi
= (P23) x ≥
i )0(
x
i trong đó: (cid:131) Mục tiêu (P21) là cực đại hoá độ tin cậy của hệ thống . (cid:131) (P22) đảm bảo tổng chi phí sử dụng không vượt quá ngân sách cho phép. (cid:131) (P23) đảm bảo tất cả các module phát triển trong công ty đều có độ tin cậy lớn hơn 0. ' BB
− ≤∑
x
i
1
+ tin cậy của chúng được tính như sau: x x ( ) − m m ) ) α
−
3 3 )0(
3 (cid:131) Hai module (3) và (4) là được phát triển trong công ty. Do đó công thức độ )0(
x
3 (
r
3 (
r
3 )0(
r
3
0 x x ( ) − m m ) ) α
−
3 4 )0(
4 ( ) e − − = r
3 x
≥
3
Otherwise )0(
x
4 (
r
4 (
r
4 )0(
r
4
0 Phan Thị Ngọc Mai Trang 39 ( ) e − − = r
4 x
≥
4
Otherwise ⎧
⎪
⎨
⎪⎩
⎧
⎪
⎨
⎪⎩ 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 trong đó: m ) ,83.0 ,53.0 ,3.0 2 = = = = )0(
r
3 m ) ,9.0 ,5.0 ,4.0 5.3 = = α
3
= )0(
x
3
= (
r
3
(
r
4 )0(
r
4 α
4 )0(
x
4 tích hợp từ hai module (2) và (4) ( ) x x − ) ) m m −α
5 5 )0(
5 ( ) e − − )0(
x
5 (
r
5 (
r
5 = r
5 x
≥
5
Otherwise )0(
r
5
0 ⎧
⎪
⎨
⎪⎩ ) ) m m , q ,8.0 ,4 25.0 = = = = = trong đó: (
r
5 )0(
rrr
,
42
5 (
rq
55 )0(
x
5 α
5 còn module (6) được tích hợp từ module (1), (3), (5). Và công thức tính độ tin cậy của module này cũng là hàm mục tiêu của bài toán phân phối chi phí cho độ tin cậy phần mềm. Chúng được thực hiện như sau: Hàm mục tiêu: ( x x ) − m ) m ) α
−
6 6 )0(
6 Maximize ( ) e = − − r
6 (
r
6 (
r
6 )0(
r
6 với các điều kiện ràng buộc: 6 ' BB
− ≤∑
x
i , i 6,5,4,3 3
≥ = i
=
x
i )0(
x
i m ) m ) , , q ,8.0 ,3.0 x 3 = = = = = trong đó:
(
r
6 )0(
rrrr
351
6 (
rq
66 6 α
6 )0(
6 (cid:131) là các giá trị được tìm thấy trong bài toán tối ưu hóa các module mua. 1, rr
2 , , (cid:131) là các chi phí cần thiết để phát triển các module (3), (4), (5), (6) xxxx
,
6
4
3 5 sao cho phần mềm có độ tin cậy lớn nhất ( 6r đạt giá trị lớn nhất). 'BB − (cid:131) là chi phí dùng cho các module phát triển trong công ty. (cid:131) Còn module (5) và (6) là hai module tích hợp, trong đó module (5) được Vấn đề phân phối chi phí giữa module mua và module phát triển trong công ty là một vấn đề rất quan trọng trong việc giải quyết bài toán tối ưu hóa việc phân phối chi phí cho độ tin cậy phần mềm. Đây là hai vấn đề được thực hiện việc tối ưu hoá bài toán: (cid:131) Một là tìm ra độ tin cậy lớn nhất có thể có mà không vượt quá giới hạn ngân sách đã cho. Phan Thị Ngọc Mai Trang 40 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 (cid:131) Hai là tìm ra chi phí nhỏ nhất để phần mềm có độ tin cậy là một hằng số cho trước. Để thực hiện được hai vấn đề đã nêu trên, chúng ta cần thực hiện hai bài toán sau: Việc tìm ra giải pháp phân phối chi phí để phần mềm có độ tin cậy lớn nhất mà không vượt quá giới hạn ngân sách đã cho, chúng ta cần giải quyết các vấn đề sau: Độ tin cậy của phần mềm bằng độ tin cậy của module đó, có hai trường hợp để giải quyết: là công thức (2.2). Ứng với công thức này ta xây dựng bài toán A có dạng sau: Hàm mục tiêu: n m i Maximize yr
ij
ij ∑∑ j i 1
= 1
=
Điều kiện ràng buộc: n m i B ≤ yc
ij
ij ∑∑ i j 1
= 1
= n i m ,1 ,1 1,0 = = y
ij =∑
y
ij j 1
= Trong đó: in là số version của module, B là chi phí đã cho để phát triển phần mềm, các thông các thông số được định nghĩa giống như trong công thức (2.2). (cid:131) Nếu module đơn là một module được phát triển trong công ty: công thức tính độ tin cậy phần mềm là công thức (2.1). Ứng với công thức này, ta xây dựng bài toán có dạng sau: Hàm mục tiêu: ( x x ) − (max) (max) )0( α
−
i i )0(
i e )(
xf ( ) = − − r
i r
i Maximize
r
i
Các điều kiện ràng buộc: B ≤ ≥ x
i
x
i )0(
x
i Phan Thị Ngọc Mai Trang 41 (cid:131) Nếu module đơn là một mudule mua: công thức tính độ tin cậy phần mềm 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 B ,1= Trong đó là chi phí đã cho để phát triển phần mềm, các thông số được định nghĩa giống như trong công thức (2.1). Khi phần mềm có nhiều module thì module gốc phải là một module tích hợp. Module tích hợp được tích hợp từ các module con, và các module con có thể là module đơn hoặc cũng có thể là module tích hợp. Độ tin cậy của module tích hợp phụ thuộc vào module con. Đối với module đơn có hai loại: module mua và module đơn được phát triển trong công ty. Do đó, công việc thực hiện tính độ tin cậy phần mềm sẽ được thực hiện cho các module đơn trước sau đó sẽ tính cho các module tích hợp. Việc giải quyết bài toán tối ưu hóa độ tin cậy của các module mua trước đã góp phần hạn chế được số biến của chương trình. Công thức tính độ tin cậy phần mềm là công thức tính độ tin cậy của module gốc. Để giải quyết bài toán này, chúng ta cần chú ý những vấn đề sau: b) Nếu phần mềm có nhiều hơn một module: m n m B ≥ + (min)
c
i (min) là tổng chi phí nhỏ nhất của các
ic . Trong đó ∑ ∑ ∑ i i )0(
x
i
1 1
= 1
= mi
+= n là tổng chi phí nhỏ nhất để phát triển các module module mua, ∑ )0(
ix
1 mi
+= trong công ty. Điều kiện này đảm bảo cho mỗi module trong phần mềm đều có độ tin cậy. (cid:131) Chi phí đã cho ( B ) để phát triển phần mềm phải thỏa mãn điều kiện 'B ) phải thỏa mãn điều kiện m n m m B ' và ' ≤ ≤ BB
− ≥ (min)
c
i (max)
c
i (max) là tổng chi phí
ic ∑ . Trong đó ∑ ∑ ∑ i i )0(
ix
1 i 1
= mi
+= 1
= 1
= lớn nhất để các module mua i có thể mua version có độ tin cậy lớn nhất. m m B ' ≤ ≤ (cid:131) Chi phí để mua các module ( đảm bảo các module mua đều có độ tin (min)
c
i (max)
c
i ∑ ∑ i i 1
= 1
= cậy và nguồn ngân sách cung cấp cho các module mua không bị dư thừa. n ' BB
− ≥ (cid:57) Điều kiện đảm bảo với việc phân phối này các module ∑ )0(
ix
1 mi
+= phát triển trong công ty đều có độ tin cậy. Bài toán tối ưu hoá các module mua được thực hiện trước (xem phần 5.2): Phan Thị Ngọc Mai Trang 42 (cid:57) Điều kiệ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 Hàm mục tiêu n m i Maximize yr
ij
ij ∑∑ i j 1
= 1
= với các ràng buộc: n m i B ≤ ' yc
ij
ij ∑∑ i j 1
= 1
= in 1 j 1
= =∑
ijy với i=1, . . . ,m và j=1, . . . ,ni 0or 1 yij = Sau khi thực hiện xong bài toán, độ tin cậy và chi phí của m module mua sẽ tìm được. Kết quả sẽ được đưa vào trong bài toán tối ưu hoá các module phát triển trong công ty (xem phần 5.3). Max S.T. n ' BB
− mi
= ≤∑
x
i
1
+ với i=m +1, . . . ,n x ≥
i )0(
x
i yêu cầu của nhà quản lý. Do ảnh hưởng của các vấn đề sau: công ty. (cid:131) Việc phân phối chi phí giữa các module mua và module phát triển trong (cid:131) Chi phí cung cấp cho phần mềm quá nhỏ, hoặc Do đó, chúng ta cần phải hiệu chỉnh lại một trong các vấn đề vừa được nêu trên, để phần mềm có thể có độ tin cậy thoả mãn yêu cầu của nhà quản lý. Các bước để thực hiện bài toán: (cid:131) Các thông số đã cho của module phần mềm. (cid:131) Số module phần mềm, số module mua, số module đơn phát triển trong công ty. (cid:131) Số version của mỗi module mua, chi phí và độ tin cậy của từng version. Phan Thị Ngọc Mai Trang 43 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 (cid:131) Chi phí khởi tạo, độ tin cậy lớn nhất, độ tin cậy nhỏ nhất, thông số phản ánh độ nhạy của module đơn phát triển trong công ty. (cid:131) Chi phí khởi tạo, thông số phản ánh sự tương thích của các module con, thông số phản ánh độ nhạy của module tích hợp, các module con của module tích hợp, chuyển sang bước 2. m n B ≥ + thì (min)
c
i ∑ i )0(
x
i
1 1
= mi
+= yêu cầu nhập lại B , ngược lại chuyển sang bước 3. 'B . Nếu tổng chi phí để mua các module mua m m n B ' ' ≤ ≤ BB
− ≥ và thì yêu cầu nhập lại 'B , ngược lại chuyển sang (min)
c
i (max)
c
i ∑ ∑ ∑ i i )0(
ix
1 1
= 1
= mi
+= bước 4. và module tích hợp và chuyển sang bước 6. từng module ứng với độ tin cậy đó. Nếu độ tin cậy không thỏa mãn yêu cầu thì chuyển sang bước 7, ngược lại chuyển sang bước 8. lại bài toán, khi Y=1 thì chuyển sang bước 2, khi Y=2 thì chuyển sang bước 3. chi phí của các module. Phan Thị Ngọc Mai Trang 44 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 Sơ đồ giải thuật: 0 Nhập các thông số của module phần mềm 1 Nhập tổng chi phí để phát triển phần mềm (B) m n − B c x ≥ + (min)
i )0(
i ∑ ∑ i 1 1 = mi
= + 2 + Y=0,1,2 Nhập tổng chi phí để mua các module mua (B’) m m c B ' c and ≤ ≤ (max)
i (min)
i ∑ ∑ − 1 1 i i = = n B B ' − ≥ )0(
i ∑ x
1 mi
= + + Nhập giai đoạn
hiệu chỉnh (Y) Tính độ tin cậy, chi phí của các module mua Thiết lập mối quan hệ, các điều kiện ràng buộc giữa
các module đơn và module tích hợp Tính độ tin cậy module đơn và module tích hợp + Độ tin cậy không thỏa mãn yêu cầu của nhà cung cấp − Xuất: độ tin cậy phần mềm, độ tin cậy của các
module, chi phí của các module Phan Thị Ngọc Mai Trang 45 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 Bài toán tìm chi phí nhỏ nhất để phần mềm có độ tin cậy lớn hơn hoặc bằng độ tin cậy đã định sẳn, là một vấn đề các nhà quản lý dự án rất quan tâm. Tuy nhiêu, công việc tìm một giá trị chi phí thoả mãn điều kiện ràng buộc về độ tin cậy ta có thể tìm được một tập các giá trị thoả mãn các điều kiện ràng buộc. Do đó, giới hạn trong bài toán này 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 (R . Và đây cũng là một bài toán ngược với bài toán A. Để thực vấn đề này chúng ta cần giải quyết các vấn đề sau: Độ tin cậy phần mềm bằng độ tin cậy của module đơn đó. là công thức (2.2). Ứng với công thức này ta xây dựng bài toán B có dạng sau: Hàm mục tiêu: n m i Minimize yc
ij
ij ∑∑ j i 1
= 1
=
Điều kiện ràng buộc: m n
i R = yr
ij
ij ∑∑ i j 1
= 1
= n i m ,1 ,1 1,0 = = y
ij =∑
y
ij j 1
= (cid:131) Nếu module đơn là một mudule mua: công thức tính độ tin cậy phần mềm phần mềm cũng là một hằng số khó có khả năng xẩy ra. Do đó, đối với trường hợp này ta thực hiện bằng cách lựa chọn một version trong số các version của module. (cid:131) Nếu module đơn là một module được phát triển trong công ty: công thức tính độ tin cậy phần mềm là công thức (2.1). Ứng với công thức này, ta xây dựng bài toán B có dạng sau: Hàm mục tiêu: xg =)( Minimize
ix
Các điều kiện ràng buộc: ( ) x x − (max) (max) )0( −α
i i )0(
i e R ( ) − − = r
i r
i ≥ r
i
x
i )0(
x
i Phan Thị Ngọc Mai Trang 46 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 (max) )0( i R ,1= , Trong đó là một hằng số cho trước, các thông số được r
i r
i α
,
,
i )0(
,
i xx
i định nghĩa giống như trong công thức (2.1). Do các module mua độc lập với nhau, việc tìm độ tin cậy của các module mua thoả mãn một hằng số là rất khó thực hiện. Một phương án đề xuất, trong trường hợp này phần module mua được thực hiện giống như bài toán A. Phần module phát triển trong công ty sẽ giải quyết việc 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. Để giải bài toán này, chúng ta cần xác định chi phí cần tìm của phần mềm. Giả sử để phần mềm có độ tin cậy là một hằng số xác định trước R ta cần '' ' BBB
+= . chi phí (cid:131) 'B : chi phí được dùng cho việc mua các module, cách tính chi phí và độ tin cậy của các module mua tương tự với bài toán A và m m B ' ≤ ≤ , với điều kiện này đảm bảo chi phí cung cấp để mua (min)
c
i (max)
c
i ∑ ∑ i i 1
= 1
= các module là vừa đủ. n B '' = (cid:131) : chi phí nhỏ nhất để phần mềm có độ tin cậy R cho trước. ∑ ix
1 mi
+= Bài toán tối ưu hoá các module mua: Hàm mục tiêu m n
i Maximize yr
ij ij ∑∑ i j 1
= 1
= với các ràng buộc: n m i B ≤ ' yc
ij
ij ∑∑ i j 1
= 1
= in 1 j 1
= =∑
ijy 0or 1 yij = Sau khi thực hiện xong bài toán được độ tin cậy và chi phí của m module mua sẽ được tìm thấy. Kết quả sẽ được đưa vào trong bài toán tối ưu hoá các module phát triển trong công ty. Phan Thị Ngọc Mai Trang 47 b) Nếu phần mềm có nhiều hơn một module: 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 Hàm mục tiêu n Minimize )(
xg = ∑ ix
1 mi
+= với các ràng buộc: ( ) x x − n )0(
n −α
iT ( ) e R − − = (max)
r
T (max)
r
T )0(
r
T n n n ≥ x
i )0(
x
i Trong đó: (cid:131) nT là module gốc. , , (cid:131) Cách xác định các thông số tương tự như công thức (max)
r
T )0(
r
T ,
α
T )0(
xx
,
n
i n n n (2.3) trước đôi khi không tìm ra được lời giải. Do ảnh hưởng của các vấn đề sau: (cid:131) Chi phí cung cấp cho các module mua quá ít làm cho độ tin cậy của các module mua quá nhỏ, vấn đề này ảnh hưởng đến độ tin cậy của các module phát triển trong công ty (module tích hợp có một trong các module con là module mua). (cid:131) Các thông số của các module phần mềm đã cho đôi khi làm cho phần mềm không có khả năng đạt đến độ tin cậy đã cho. Do đó, chúng ta cần phải hiệu chỉnh các thông số này để phần mềm tìm ra được chi phí thoả mãn độ tin cậy đã cho. Các bước để thực hiện bài toán: (cid:131) Số module phần mềm, số module mua, số module đơn phát triển trong công ty. (cid:131) Số version của mỗi module mua, chi phí và độ tin cậy của từng version. (cid:131) Chi phí khởi tạo, độ tin cậy lớn nhất, độ tin cậy nhỏ nhất, thông số phản ánh độ nhạy của module đơn phát triển trong công ty. (cid:131) Chi phí khởi tạo, thông số phản ánh sự tương thích của các module con, thông số phản ánh độ nhạy của module tích hợp, các module con của module tích hợp, chuyển sang bước 2. Phan Thị Ngọc Mai Trang 48 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 m m B ' < < 'B ). Nếu (min)
c
i (max)
c
i ∑ ∑ i i 1
= 1
= thì chuyển sang bước 4, ngược lại yêu cầu nhập lại. tích hợp, chuyển sang bước 6. các module ứng với chi phí đó. Nếu tìm ra chi phí thỏa mãn điều kiện thì chuyển sang bước 8, ngược lại chuyển sang bước 7. lại bài toán, khi Y=1 thì chuyển sang bước 2, khi Y=2 thì chuyển sang bước 3. chi phí của các module. Phan Thị Ngọc Mai Trang 49 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
Sơ đồ giải thuật 0 Nhập các thông số của module chương trình 1 Nhập chi phí để mua các module (B’) m m _ c B c ' ≤ ≤ (min)
i (max)
i ∑ ∑ i i 1
= 1
= 2 + Y=0,1,2 Nhập độ tin cậy của phần mềm (R) Tính chi phí và độ tin cậy của các module mua Yêu cầu chỉnh
sửa (Y) Thiết lập mối quan hệ, các điều kiện ràng buộc giữa các
module đơn và module tích hợp Tìm chi phí nhỏ nhất và độ tin cậy của các module
trong phần mềm _ Chi phí cung cấp thỏa mãn yêu
cầu + Xuất: Tổng chi phí phần mềm, chi phí và độ
tin cậy của các module Phan Thị Ngọc Mai Trang 50 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 Chương này trình bày một số kết quả đạt được của phần mềm trên 6 module, 11 module, 22 module, 37 module. Bài toán được chia thành nhiều bài toán nhỏ để giải quyết. Vì thế để chọn một ngôn ngữ lập trình phù hợp cũng cần được tính đến. Trong luận văn này ngôn ngữ được chọn để viết và kiểm nghiệm đó là ngôn ngữ MATLAB (xem phần phụ lục 3). MATLAB cung cấp một công cụ tính toán toán học và lập trình bậc cao dễ sử dụng, hiệu quả và thân thiện với người dùng. 6.2.1. Bài toán trong ví dụ 3.4 Trong phần 3.4 chúng ta đã trình bày các bước để tìm lời giải cho ví dụ 3.4. Trong phần này xin trình bày cách thức để giải bài toán trong Matlab cho ví dụ 3.4 như sau: function vidu3_4 f = [5; 7; 10; 3; 1]; A = [-1 3 -5 -1 4; 2 -6 3 2 -2;0 1 -2 3 1]; b = [-2;0;-1]; [x, fval] = bintprog(f,A,b) Ta thu được kết quả như sau: x = 0 1 1 0 0, fval = 17. Trùng với kết quả đạt được trong phần 3.4. 6.2.2. Bài toán trong ví dụ 4.1.1 Tương tự như trên, trong phần 4.1 chúng ta đã trình bày các bước để tìm lời giải cho ví dụ 4.1.1 Trong phần này xin trình bày chương trình cho ví dụ 4.1.1 như sau: lb=[0 0 0];
ub=[];
x0=[0;0;0];
[x,fval] = fmincon(@myfun,x0,[],[],[],[],lb,ub,@fun) function Vidu4_1_1
function f=myfun(x) f = (x(1)-3)^2+(x(2)-2)^2; Phan Thị Ngọc Mai Trang 51 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 c(1)=x(1)^2-x(2)-3;
c(2)=x(2)^2-1;
ceq=[]; end
function [c, ceq]=fun(x)
end
end Ta thu được kết quả như sau: x = (2.0000,1.0000), và hàm mục tiêu đạt giá trị fval = 2.0000. Trùng với kết quả đạt được trong ví dụ 4.1.1. 6.2.3. Bài toán trong ví dụ 4.3.1 Ta có thể xây dựng một chương trình giải bài toán quy hoạch phi tuyến của hàm nhiều biến trong Matlab cho bài toán trong ví dụ 4.3.1 như sau: A=[-1 0 0;0 -1 0;0 0 -1]; b=[0;0;0]; x0=[0;0;0]; [x,fval,exitflag]=fmincon(@myfun,x0,A,b) f = 3*x(1)^2+x(2)^2+x(3)^2-2*x(1)*x(2)-2*x(1)*x(3)-2*x(1); Ta thu được kết quả như sau: x = 1.0000 1.0000 1.0000, và hàm mục tiêu đạt giá trị fval = -1.0000. Trùng với kết quả đạt được trong ví dụ 4.3.1. 6.2.4. Bài toán trong ví dụ 4.3.4 Ta xây dựng chương trình cho ví dụ 4.3.4 như sau A=[1 1 2];
b=[16];
Aeq=[1 1 0];
beq=[3];
lb=[0 0 0];
ub=[];
x0=[0;0;0];
[x,fval] = fmincon(@myfun,x0,A,b,Aeq,beq,lb,ub,@fun) f = 2*x(1)^2+x(2)^2+0.2*x(3)^2+x(1)*x(3)-x(1)*x(2)+x(1)-0.5*x(3); Phan Thị Ngọc Mai Trang 52 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 c=x(1)^2+x(2)^2-x(3);
ceq=[]; Sau khi chạy chương trình ta thu được nghiệm của bài toán: x =(1.0000, 2.0000, 5.0000) và hàm mục tiêu đạt giá trị fval = 12.5000. Kết quả này trùng với kết quả đạt được trong ví dụ 4.3.4. Phan Thị Ngọc Mai Trang 53 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 6.2.5. Bài toán cho một phần mềm gồm có 6 module Như đã trình bày trong ví dụ 5.1 và 5.2, trong phần này sẽ chạy phần mềm có 6 module, ta thu được các kết quả sau: Độ tin
cậy [ [ B B’ r …
]
r
5
3 x …
]
x
6
3 yy
11
12
yy
21 22 tối ưu
( 6r ) 25 12 1010 [2, 4, 4, 3] 0.5300, 0.5725, 0.3985 0.1183 26 13 0110 2, 4, 4, 3 0.5300, 0.5725, 0.3985 0.1521 30 14 0101 [3.3822, 5.6178, 4, 3] 0.6318, 0.7285, 0.5537 0.2519 35 14 0101 [5.0354, 6.9367, 4.8520, 4.1759] 0.7093, 0.7988,0.6362 0.3491 40 14 0101 [6.1630, 7.9788, 6.3025, 5.5557] 0.7093, 0.7988, 0.6362 0.4267 45 14 0101 [7.0692, 9.0706, 7.9018, 6.9584] 0.7093, 0.7988, 0.6362 0.4863 50 14 0101 [8.9192, 9.8961, 9.2542, 7.9305] 0.7924, 0.8690 0.7812 0.5317 [10.186, 10.8559, 10.8019, 0.8043, 0.8789 0.8045 0.5639 55 14 0101 9.1562] [11.4559, 11.8187, 12.3789, 0.8124, 0.8856, 0.8206 0.5868 60 14 0101 10.3465] [16.6108, 15.6124, 18.6015, 0.8263, 0.8969, 0.8476 0.6270 80 14 0101 15.1754] [16.0927, 30.7139, 23.2710, 0.8256, 0.9000, 0.8536 0.6317 100 14 0101 15.9224] [35.6548, 65.0458, 16.9591, 0.8300, 0.9000, 0.8483 0.6324 150 14 0101 18.3404] [49.2676, 89.9183, 22.2423, 0.8300, 0.9000, 0.8532 0.6372 200 14 0101 24.5718] Phan Thị Ngọc Mai Trang 54 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 [ [ B’ r …
]
r
5
3 x …
]
x
3
6 Tổng chi
phí (B) yy
11
12
yy
21 22 Độ tin cậy
phần mềm
( 6r ) [2.0000, 4.0013, 0.1183 12 1010 [0.5300, 0.5727, 0.3986] 25.0013 4.0000, 3.0000] [4.0674, 6.1620, 0.2 12 1010 [0.6687, 0.7621, 0.5304,] 29.3241 4.0000, 3.0947] [3.9086, 6.0367, 29.9453 0.25 13 0110 [0.6608, 0.7550, 0.5255] 4.0000, 3.0000] [4.4172, 6.4370, 32.2987 0.3 14 0101 [0.6847, 0.7764, 0.5901] 4.0000, 3.4445] [5.1295, 6.9932, 35.0502 0.35 14 0101 [0.7127, 0.8011, 0.6355] 4.7705, 4.1570] [5.9117, 7.5989, 38.1356 0.4 14 0101 [0.7372, 0.8224, 0.6787] 5.6860, 4.9391 [6.8300, 8.3047, 41.7582 0.45 14 0101 [0.7596, 0.8415, 0.7193] 6.7667, 5.8568] [7.9797, 9.1827 0.5 14 0101 [0.7801, 0.8588, 0.7577] 46.2957 8.1267, 7.0065] [9.5842, 10.4007 0.55 14 0101 [0.7992, 0.8747, 0.7942] 52.6301 10.0340, 8.6112] [12.4556, 12.5681, 63.9701 0.6 14 0101 [0.8170, 0.8894, 0.8290] 13.4632, 11.4833] Phan Thị Ngọc Mai Trang 55 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 6.2.6. Bài toán cho một phần mềm gồm có 11 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ó 11 module có cấu trúc như hình 6.1: Module (11) Module (6) Module (7) Module (10) Module (9) Module (5) Module (2) Version 21 Module (8) Module (3) Version 22 Version 31 Module (1) Module (4) Version 32 Version 32 Version 11 Version 12 Version 13 Version 14 Các thông số ngẫu nhiên được chọn cho bài toán: ,75.0 ,7.0 ;5 ;6 ,8.0 ;7 ,9.0 8 = = = = = = = = c
13 r
14 c
14 r
12
;5.5 c
12
,92.0 = = r
13
;8
= = c
11
c
,77.0
21 c
22 ,75.0 ;5.6 ,79.0 ;7 ,93.0 8 = = = = = = c
33 c
31
,97.0 r
22
r
32
,55.0 c
32
,4.0 = = = r
33
5
= )0(
r
4 α
4 )0(
x
4 r
11
r
21
r
31
(max)
r
4 ,98.0 ,47.0 ,35.0 5.4 = = = = )0(
r
5 ,45.0 5.3 ,4.0 ,9.0 α
5
= )0(
x
5
= = = ,3.0 5.5 = = = = )0(
x
6
)0(
x
7 )0(
r
6
)0(
r
,97.0
7
,35.0 α
6
α
,35.0
7
5.6 ,9.0 = = = ,95.0 ,4.0 6 = = = ,97.0 )0(
x
8
)0(
x
9
,33.0 7 = = = )0(
x
10 ,98.0 ,3.0 8 = = = (max)
r
5
(max)
r
6
(max)
r
7
q
8
q
9
q
10
q
11 α
8
α
9
α
10
α
11 )0(
x
11 Phan Thị Ngọc Mai Trang 56 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 Trong đó module 11 là module gốc, độ tin cậy phần mềm cũng là độ tin cậy của module gốc. Đối với các module mua: Hàm mục tiêu: max + + + + + + + + yr
11 11 yr
12 12 yr
13 13 yr
14 14 yr
21 21 yr
22 22 yr
31 31 yr
32 32 yr
33 33 Các điều kiện ràng buộc: a) Bài toán A 14 21 22 31 32 33 B ' + ≤ + + + + + + + yc
14 yc
21 yc
22 yc
31 yc
32 yc
33 11
+ 13
= 1 yc
12
+ + yc
13
y
14 12
y
13
1 21 22 yc
11
y
11
y y
12
y + = 1 + = Đối với các module phát triển trong công ty: Hàm mục tiêu: ( ) − α
−
11 x
11 )0(
x
11 y
32
or 0 y
33
1 y
+
31
y
ij = (max)
r
11 (min)
r
11 Các điều kiện ràng buộc: 11 ' BB
− ≤∑
x
i 4 ; = = i
=
(max)
r
11 rrr
1076 )0(
r
11 (max)
rq
11
11 ( ) x x − α
−
6 6 )0(
6 e ( ) = − (max)
r
6 )0(
r
6 r
6 ( ) x x − α
−
7 7 )0(
7 ( ) e = − (max)
r
7 )0(
r
7 r
7 − ( ) α
−
10 x
10 )0(
x
10 (max ) e − (max)
r
10 )0(
r
10 (max)
r
10 )0(
r
10 (max)
rq
10
10 x x − ( ) α
−
5 5 )0(
5 ( e
) , ; = − = = r
10 rrr
952 (max)
r
5 )0(
r
5 x x ( ) − (max) α
−
9 9 )0(
9 ( e
) = − r
5 (max)
r
9 )0(
r
9 (max)
r
9 )0(
r
9 x x ( ) − (max) α
−
8 8 )0(
8 e ( ) , ; = − = = rr
83 rq
99 r
9 (max)
r
8 )0(
r
8 (max)
r
8 )0(
r
8 ( ) x x − α
−
4 4 )0(
4 e ( ) , ; = − = = rr
41 rq
41 r
8 )0(
r
4 e ) ( − = (max)
r
4
)0(
x
i ≥ r
4
x
i Đối với module mua cách xây dựng giống như bài toán A Hàm mục tiêu: 11 12 13 14 21 22 31 32 33 Các điều kiện ràng buộc: Phan Thị Ngọc Mai Trang 57 max + + + + + + + + yr
11 yr
12 yr
13 yr
14 yr
21 yr
22 yr
31 yr
32 yr
33 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 B ' + ≤ + + + + + + + yc
14 14 yc
21 21 yc
22 22 yc
31 31 yc
32 32 yc
33 33 1 yc
12
+ 11
+ + 13
= yc
13
y
14 yc
11
y
11
y y
12
y 12
y
13
1 + = 21 22 1 + = y
32
or 0 y
33
1 y
+
31
y
ij = Đối với các module phát triển trong công ty: Hàm mục tiêu: 11 Minimize ix ∑ 4i
= Các điều kiện ràng buộc: ( ) − α
−
11 x
11 )0(
x
11 (max)
r
11 ( ) e R − = (max)
r
11 (min)
r
11
rrr
76
10 )0(
r
11 (max)
rq
11
11 x x ( ) − α
−
6 6 )0(
6 ; = = (max)
r
6 )0(
r
6 x x ( ) − α
−
7 7 )0(
7 ( ) e = − r
6 (max)
r
7 )0(
r
7 ( ) − α
−
10 x
10 )0(
x
10 ( ) e = − r
7 (max)
r
10 )0(
r
10 (max)
r
10 )0(
r
10 (max)
rq
10
10 x x ( ) − α
−
5 5 )0(
5 ( ) e , ; = − = = r
10 rrr
952 (max)
r
5 )0(
r
5 x x ( ) − (max) α
−
9 9 )0(
9 ( ) e = − r
5 (max)
r
9 )0(
r
9 (max)
r
9 )0(
r
9 ( ) x x − (max) α
−
8 8 )0(
8 ( ) , ; e = − = = r
9 rr
83 rq
99 (max)
r
8 )0(
r
8 (max)
r
8 )0(
r
8 ( ) x x − α
−
4 4 )0(
4 ( ) , ; e = − = = r
8 rr
41 rq
41 (max)
r
4 )0(
r
4 ( ) e = − )0(
x
i Phan Thị Ngọc Mai Trang 58 ≥ r
4
x
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 , r … ]
,
4 r
10 ijy [ , [ B B’ x … ]
,
4 x
11 Độ tin
cậy
tối ưu
( 11r ) 1000 0.0119 10 63 17 [0.5500, 0.4700,
0.4000, 0.3500, 0.3465,
0.2469, 0.0867] [5.0000, 4.5000, 3.5000,
5.5000, 6.5000, 6.0000,
7.0000, 8.0000] 100 0 0 0 1
1 0 0.0569 70 20 [0.6292, 0.6056,
0.6074, 0.5631, 0.5266,
0.3752, 0.1697] [5.5223, 5.3832, 4.6907,
6.9038, 6.5000, 6.0000,
7.0000, 8.0000] 1 0 0 0 0 0 1
0 1 0.0861 74 24 [0.6292, 0.6056,
0.6074, 0.5631, 0.5266,
0.4753, 0.2568] [5.5222, 5.3830, 4.6909,
6.9039, 6.5000, 6.0000,
7.0000, 8.0000] 0 0 1 0 0 0 1
0 1 100 24 0.4906 [0.9310, 0.9354,
0.8676, 0.9182, 0.8260,
0.7529, 0.6285] [10.9424, 11.4615, 9.5807,
13.7723, 8.7156, 6.5276,
7.0000, 8.0000] 0 0 1 0.6492 150 24 0 0 0 1
0 1 0 0
1 [17.5120, 16.5985, 19.3349,
19.8284, 15.0859, 11.8486,
12.9279, 12.8637] [0.9672, 0.9726,
0.8996, 0.9616, 0.8950,
0.8462,0.7539] [21.2336, 20.7994, 29.8264, 0 0 0 1
0 1 0.6700 200 24 [0.9694, 0.9783,
0.9000, 0.9692, 0.9000,
0.8549, 0.7685] 0 0 1 27.5359, 18.1905, 20.7486,
16.7201, 20.9455] [22.0069, 29.0034, 52.0196, 0 0 0 1
0 1 0.6729 300 24 [0.9695, 0.9799,
0.9000, 0.9700, 0.9017,
0.8566, 0.7721] 0 0 1 43.1512, 36.0382, 54.5076,
23.1430, 16.1301] 0 0 0 1
0 1 0.6738 350 24 [ 0.9698, 0.9800,
0.9000, 0.9700, 0.9019,
0.8568, 0.7725] [24.0681, 32.3711, 60.4994,
48.7129, 42.4632, 70.6509,
28.4370, 18.7973] 0 0 1 0 0 0 1
0 1 0.6745 500 24 [0.9700, 0.9800,
0.9000, 0.9700, 0.9021,
0.8570, 0.7727] [30.3506, 42.4782, 85.3626,
65.2857, 56.4704, 122.4443,
45.4385, 27.3941] 0 0 1 Phan Thị Ngọc Mai Trang 59 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 , ijy r … ]
,
4 r
10 [ , [ B’ x … ]
,
4 x
11 Tổng chi
phí (B) Độ tin
cậy
phần
mềm
( 11r ) 1 0 0 0
1 0 63.0014 0.0119 17 [0.5500, 0.4700,
0.4003,0.3500, 0.3465,
0.2469, 0.0867] [5.0000, 4.5000, 3.5014,
5.5000,6.5000,6.0000,7.0000,
8.0000] 1 0 0 0 0 0 1
1 0 70.0008 0.0569 20 [0.6292, 0.6054, 0.6076,
0.5633, 0.5267, 0.3752,
0.1697] [5.5226, 5.3812, 4.6918,
6.9052, 6.5000, 6.0000,
7.0000, 8.0000] 1 0 0 0 0 0 1
0 1 74.0001 0.0861 24 [0.6292, 0.6053, 0.6075,
0.5632, 0.5266, 0.4753,
0.2568] [5.5224, 5.3811, 4.6917,
6.9050, 6.5000, 6.0000,
7.0000 8.0000] 0 0 1 0 0 0 1 [0.6520, 0.6292, 0.6278, 0 1 0.5877, 0.5457, 0.4925 0.1 24 74.7280 [5.6953, 5.5693, 4.8513,
7.1121, 6.5000, 6.0000,
7.0000, 8.0000] 0.2765] 0 0 1 0 0 0 1
0 1 0.4 24 91.2089 [0.8984, 0.8982, 0.8404,
0.8768, 0.7657, 0.6911,
0.5539] [9.4220, 9.7276, 8.2280,
11.8163, 7.0149, 6.0000,
7.0000, 8.0000] 0 0 1 0 0 0 1
0 1 0.5 24 101.1662 [0.9335, 0.9381, 0.8698,
0.9220, 0.8311, 0.7599,
0.6362] [11.1105, 11.6428,
9.7386,14.0293, 8.9305,
6.7146,7.0000 8.0000] 0 0 1 0 0 0 1
0 1 121.0829 0.6 24 [ 0.9575, 0.9656,
0.8897, 0.9534, 0.8774,
0.8228, 0.7196] [13.7900, 14.6956,12.1266,
17.5757,11.9833, 9.3944,
8.9911, 8.5262] 0 0 1 0 0 0 1
0 1 147.0098 0.65 24 [0.9660, 0.9754, 0.8967,
0.9647, 0.8942, 0.8460,
0.7555] [16.6578, 17.9688, 14.6775,
21.3879, 15.2558, 12.2612,
12.4612, 12.3396] 0 0 1 Phan Thị Ngọc Mai Trang 60 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 6.2.7. Bài toán cho một phần mềm gồm có 22 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ó 22 module có cấu trúc như hình 6.2 Module (22) Module (21) Module (20) Module (11) Module (12) Module (19) Module (18) Module (10) Module (9) Module (16) Module (17) Module (8) Module (15) Module (7) Module (6) Module (4) Module (14) Module (2) Version 21 Module (13) Module (3) Version 22 Version 41 Version 31 Module (1) Module (5) Version 42 Version 32 Version 42 Version 32 Version 11 Version 42 Version 12 Version 13 Version 14 Các thông số ngẫu nhiên được chọn cho bài toán: ,77.0 ;8 ,8.0 ;5.8 ,85.0 ;9 ,9.0 10 = = = = = = = = c
13 r
14 c
14 22 Phan Thị Ngọc Mai Trang 61 ,75.0 c
12
,89.0 r
13
;8 c = = = = r
11
r
21 c
11
c
11 r
12
;5.5
r
22 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 ,95.0 8 ,65.0 ;5.6 ,79.0 ;7 = = = = = = ;7 ,9.0 9 ,87.0 ,55.0 ;6 ,82.0 ;5.6 = = = = = = r
12
= c
12
= c
13
c
43 r
44 c
44 c
21
c
41
,97.0 r
42
,37.0 c
42
,3.0 = = = r
13
r
43
4
= ,96.0 ,56.0 ,4.0 3 = = = = )0(
x
5
)0(
x
6
)0(
x
7 ,99.0 ,49.0 ,5.0 5 = = = = α
5
α
6
α
7
= ,95.0 ,5.0 7 ,4.0 = = = )0(
x
8
,35.0 ,97.0 ,35.0 8 = = = = ,98.0 ,55.0 ,25.0 6 = = = = )0(
x
9
)0(
x
10
)0(
x
11 α
8
α
9
α
10
α
11 )0(
r
5
)0(
r
6
)0(
r
7
)0(
r
8
)0(
r
9
)0(
r
10
)0(
r
11 ,99.0 ,46.0 ,45.0 5 = = = = r
31
r
41
(max)
r
5
(max)
r
6
(max)
r
7
(max)
r
8
(max)
r
9
(max)
r
10
(max)
r
11 )0(
x
12 5.7 ,97.0 ,35.0 ,4.0 = = = = )0(
r
12
= α
12
5.6
= ,25.0 ,9.0 = )0(
x
13
)0(
x
14 ,35.0 6 ,95.0 = = = ,3.0 5.6 ,97.0 = = = )0(
x
15
)0(
x
16 ,23.0 8 ,98.0 = = = α
13
α
14
α
15
α
16
= ,34.0 5.6 ,9.0 = = ,33.0 6 ,95.0 = = = ,31.0 8 ,97.0 = = = )0(
x
17
)0(
x
18
)0(
x
19
)0(
x
20 7 ,96.0 ,34.0 = = = 9 ,98.0 ,35.0 = = = (max)
r
12
q
13
q
14
q
15
q
16
q
17
q
18
q
19
q
20
q
21
q
22 )0(
x
21
)0(
x
22 α
17
α
18
α
19
α
20
α
21
α
22 Trong đó module 22 là module gốc, độ tin cậy phần mềm cũng là độ tin cậy của module gốc. ,99.0 ,37.0 10 = = = Đối với các module mua: Hàm mục tiêu: 21 22 31 32 33 max + + + + + + + + + yr
21 yr
22 yr
31 yr
32 yr
33 yr
11 yr
12 yr
13 yr
14 14
+ 11
yr
41 41 12
yr
42 42 13
yr
+
43 43 44 Các điều kiện ràng buộc: + + + + + + + + + yc
22 22 yc
31 31 yc
32 32 yc
33 33 21
' + + yc
21
B
≤ yc
13
13
yc
43 43
,1 y 44
y 1 41
+ yc
12
12
yc
42
+ 412
+ = yc
14
14
yc
+
44
+ = y
14
y
,1 21
y 22
y y ,1 0 or 1 + = + + + + = yc
11
11
yc
41
y
11
y
31 y
13
y
33 41 42 43 y
12
y
32 44 y
ij = Phan Thị Ngọc Mai Trang 62 + yr
44 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 với các module phát triển trong công ty: Hàm mục tiêu: ( x x ) α
− − 22 22 )0(
22 Maximize ( ) e − (max)
r
22 (min)
r
22 Các điều kiện ràng buộc: 22 ∑ 5 ' ≤ BB
− x
i i
=
(max)
r
22 )0(
r
22 (max)
rq
22
22 x x ( ) α
− − 20 20 )0(
20 , = = rr
20
20 (max)
r
20 )0(
r
20 (max)
r
20 )0(
r
20 (max)
rq
20
20 x ( ) α
− − 21 x
13 )0(
21 ( e
) , , = − = = r
20 rr
18
17 (max)
r
21 )0(
r
21 (max)
r
19 )0(
r
21 (max)
rq
21
21 ( ) − α
−
19 x
19 )0(
x
19 ( e
) , , = − = = r
21 rr
19
11 (max)
rq
17
19 (max)
r
19 )0(
r
19 (max)
r
19 )0(
r
19 ( ) − α
−
18 x
18 )0(
x
18 ( e
) , , = − = = r
19 rr
179 (max)
r
18 )0(
r
18 (max)
r
18 )0(
r
18 (max)
rq
18
18 ( ) − α
−
17 x
17 )0(
x
17 ( ) e , , = − = = r
18 rr
16
10 (max)
r
17 )0(
r
17 (max)
r
17 )0(
rrr
,
17
85 (max)
rq
17
17 ( ) − α
−
16 x
16 )0(
x
16 ( ) e , = − = = r
17 (max)
r
16 )0(
r
16 (max)
r
16 )0(
rrr
,
16
76 (max)
rq
16
16 ( ) − α
−
15 x
15 )0(
x
15 ( ) e , = − = = r
16 (max)
r
15 )0(
r
15 (max)
r
15 )0(
r
15 (max)
rq
15
15 ( ) − α
−
14 x
14 )0(
x
14 ( ) e , , = − = = r
15 rrr
1442 (max)
rq
14
14 (max)
r
14 )0(
r
14 (max)
r
14 )0(
r
14 ( ) α
− − 13 x
13 )0(
x
13 ( ) e , , = − = = r
14 rr
133 (max)
r
13 )0(
r
13 (max)
r
13 )0(
rrr
,
13
51 (max)
rq
13
13 ( ) x x − ( ) x x − α
−
6 6 α
−
5 5 )0(
5 )0(
6 ( ) e , = − = = r
13 (max)
r
5 )0(
r
5 (max)
r
6 )0(
r
6 ( ) x x − ( ) x x − α
−
8 8 α
−
7 7 )0(
7 )0(
8 ( ) e , ( ) e = − = − r
6 r
5 (max)
r
7 )0(
r
7 (max)
r
8 )0(
r
8 ( ) ( ) x x − − α
−
9 9 α
−
10 x
10 )0(
9 )0(
x
10 ( ) e , ( ) e = − = − r
7 r
8 (max)
r
9 )0(
r
9 (max)
r
10 )0(
r
10 ( ) ( ) − − α
−
11 x
11 α
−
12 x
12 )0(
x
11 )0(
x
12 ( ) e , ( ) e = − = − r
9 r
10 (max)
r
12 )0(
r
12 (max)
r
11 , ( ) e ( ) e = − = − r
12 )0(
r
11
…=
,5 )0(
x
i Phan Thị Ngọc Mai Trang 63 , i 22 ≥ r
11
x
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 Đối với các module mua giống như bài toán A Đối với các module phát triển trong công ty: Hàm mục tiêu: 22 Minimize ix ∑ 5i
= Các điều kiện ràng buộc: ( ) x x α
− − 22 22 )0(
22 ( ) R e = − (max)
r
22 , = = (max)
r
22 (min)
r
22
rr
20
20 )0(
r
22 (max)
rq
22
22 ( ) x x α
− − 20 20 )0(
20 ( ) e = − )0(
r
20 , = r
20
(max)
r
20 (max)
r
20
rr
=
18
17 )0(
r
20 (max)
rq
20
20 ( ) x α
− − 21 x
13 )0(
21 ( ) e = − )0(
r
21 , = r
21
(max)
r
19 (max)
r
21
rr
=
19
11 )0(
r
21 (max)
rq
21
21 ( ) α
− − 19 x
19 )0(
x
19 ( ) , , e = − = = r
19 (max)
r
19 )0(
r
19 (max)
rq
17
19 (max)
r
19 rr
179 )0(
r
19 ( ) − α
−
18 x
18 )0(
x
18 ( ) e , , = − = = r
18 (max)
r
18 )0(
r
18 (max)
r
18 rr
16
10 )0(
r
18 (max)
rq
18
18 ( ) − α
−
17 x
17 )0(
x
17 ( ) e , = − = = r
17 (max)
r
17 )0(
r
17 (max)
r
17 )0(
rrr
,
17
85 (max)
rq
17
17 ( ) α
− − 16 x
16 )0(
x
16 ( ) e , = − = = r
16 (max)
r
16 )0(
r
16 (max)
r
16 )0(
rrr
,
16
76 (max)
rq
16
16 ( ) − α
−
15 x
15 )0(
x
15 ( ) e , , = − = = r
15 (max)
r
15 )0(
r
15 (max)
r
15 rrr
1442 )0(
r
15 (max)
rq
15
15 ( ) α
− − 14 x
14 )0(
x
14 ( ) e , , = − = = (max)
rq
14
14 (max)
r
14 rr
133 )0(
r
14 r
14 (max)
r
14 )0(
r
14 ( ) − α
−
13 x
13 )0(
x
13 ( ) e , = − = = r
13 (max)
r
13 )0(
r
13 (max)
r
13 )0(
rrr
,
13
51 (max)
rq
13
13 ( ) x x − ( ) x x − α
−
6 6 α
−
5 5 )0(
5 )0(
6 ( ) e , ( ) e = − = − (max)
r
5 )0(
r
5 r
6 (max)
r
6 )0(
r
6 r
5 ( ) x x − ( ) x x − α
−
8 8 α
−
7 7 )0(
7 )0(
8 ( ) e , ( ) e = − = − (max)
r
7 )0(
r
7 r
8 (max)
r
8 )0(
r
8 r
7 ( ) ( ) x x − − α
−
9 9 α
−
10 x
10 )0(
9 )0(
x
10 ( ) e , ( ) e = − = − (max)
r
9 )0(
r
9 r
10 (max)
r
10 )0(
r
10 r
9 ( ) ( ) − − α
−
11 x
11 α
−
12 x
12 )0(
x
11 )0(
x
12 , ( ) e ( e ) = − = − r
12 (max)
r
12 )0(
r
12 (max)
r
11 , i 22, ≥ )0(
r
11
…=
,6,5 )0(
x
i r
11
x
i Phan Thị Ngọc Mai Trang 64 b) Bài toán B 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 Độ tin
cậy [ , [ , B B’ ijy r …
,
]
r
5
21 x …
,
]
5 x
22 tối ưu
( 22r ) 1 0 0 0
1 0 0.0035 145 26 1 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] 1 0 0 0 [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] 0 0 0 1
0 1 0.55 200 35 0 0 1 [4.00, 9.52, 12.40,7.00, 16.20,
14.37, 11.67, 15.16, 6.50, 6.00,
6.50, 8.00, 6.50, 6.90, 8.00,
7.28, 9.00, 10.00] 0 0 0 1 [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 0 0 1
0 1 250 35 0.71 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 0 0 1
0 1 300 35 0.77 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 0 0 1
0 1 400 35 0.7856 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 0 0 0 1 [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] 18.97] 0 0 0 1
0 1 500 35 0.7882 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] Phan Thị Ngọc Mai Trang 65 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 [ , [ , B’ ijy r …
,
]
r
5
21 x …
]
,
5 x
22 Tổng
chi phí
(B) Độ tin
cậy
phần
mềm
( 22r ) 1 0 0 0 1 0 0.0035 26 135.00 1 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] 1 0 0 0 0 0 0 1 0 1 0.1 35 154.78 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] 0 0 0 1 0 0 0 1 0 1 0.2 35 161.19 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] 0 0 0 1 0 0 0 1 0 1 0.3 35 167.23 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] 0 0 0 1 0 0 0 1 0 1 0.5 35 182.78 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] 0 0 0 1 [4.00, 12.54 0 0 0 1 0 1 0.7 35 222.50 0 0 1 [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] 0 0 0 1 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] Phan Thị Ngọc Mai Trang 66 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 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_33 M_34 M_19 M_20 M_21 M_22 M_29 M_30 M_31 M_16 M_17 M_15 M_18 M_26 M_27 M_28 M_14 M_11 M_12 M_13 M_10 M_25 M_23 M_24 M_4 M_1 M_9 M_5 M_6 M_2 M_3 M_7 M_8 V 51 V 51 V 21 V 31 V 11 V 52 V 52 V 22 V 32 V 12 V 53 V 33 V 23 V 13 V 34 Các thông số ngẫu nhiên được chọn cho bài toán: ,77.0 ;8 ,8.0 ;5.8 ,85.0 ;9 = = = = = = ,76.0 c
12
,89.0 ;9 = = = = = = ,8.0 ;7 ,89.0 ;9 ,95.0 ;10 = c
11
c
11
= r
12
;5.5
r
22
,84.0
= c
22
;5.8
= r
13
;8
r
23
= c
13
,94.0
c
23
= = = r
11
r
21
r
31 c
31 r
32 c
32 r
33 c
33 r
34 c
34 Phan Thị Ngọc Mai Trang 67 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 ,9.0 ;9 ,81.0 ;6 ,86.0 ;7 c c c = = = = = = 43 41 ,83.0 r
43
;8 c 42
,96.0
c = = = = 41
,95.0 r
42
;6.6
r
52
,5.0 52
,35.0 4 x = = = = )0(
6 ,98.0 ,3.0 ,4.0 5 x = = = = )0(
7 ,93.0 ,4.0 ,3.0 7 x = = = = ,97.0 ,3.0 ,35.0 6 )0(
8
x = = = = ,98.0 ,33.0 8 = = = = r
41
r
51
(max)
r
6
(max)
r
7
(max)
r
8
(max)
r
9
(max)
r
10 )0(
9
)0(
,25.0
x
10 )0(
r
6
)0(
r
7
)0(
r
8
)0(
r
9
)0(
r
10 α
6
α
7
α
8
α
9
α
10 ,4.0 ,35.0 6 ,96.0 = = = = )0(
x
11
)0(
x
12 ,98.0 ,5.0 ,35.0 9 = = = = ,95.0 ,4.0 ,3.0 7 = = = = )0(
x
13
)0(
x
14 ,96.0 ,45.0 ,4.0 8 = = = = ,96.0 ,4.0 ,3.0 6 α
11
α
12
α
13
α
14
= = = = )0(
x
15
,36.0 )0(
x
16 ,97.0 ,35.0 9 = = = = ,96.0 ,4.0 ,34.0 5 α
15
α
16
= = = = )0(
r
11
)0(
r
12
)0(
r
13
)0(
r
14
)0(
r
15
)0(
r
16
)0(
r
17
)0(
r
18 ,95.0 ,45.0 ,35.0 8 = = = = )0(
x
17
)0(
x
18
= ,5.0 ,4.0 5.7 ,9.0 α
17
α
18
= = = )0(
x
19
,3.0 )0(
20 x 5.8 = = = = )0(
21 x ,3.0 ,35.0 9 ,96.0 α
19
,55.0
α
20
= = = = (max)
r
11
(max)
r
12
(max)
r
13
(max)
r
14
(max)
r
15
(max)
r
16
(max)
r
17
(max)
r
18
(max)
r
19
(max)
r
20
(max)
r
21
(max)
r
22
q x ,4.0 ,4.0 10 ,97.0 = = = = α
21
α
22 )0(
r
19
)0(
r
,95.0
20
)0(
r
21
)0(
r
22
= )0(
22
= 23 )0(
23 x q x ,98.0 ,32.0 ,10 ,95.0 ,33.0 9 = = = = 24
= )0(
24
= 25 q x q x ,91.0 ,35.0 ,8 ,99.0 ,4.0 5 = = = α
24
= )0(
25
x 26
q )0(
26
x 27 )0(
27 28 )0(
28 ,7 ,94.0 ,37.0 6 q ,97.0 ,35.0 = = = = = = 29 )0(
29 ,9 ,98.0 ,33.0 ,94.0 ,32.0 5.7 q x = = = = = = ,93.0 ,34.0 ,6.8 ,96.0 ,36.0 8 = = = = = = )0(
x
30
)0(
x
32
= )0(
x
34 ,9 11 ,93.0 ,39.0 ,95.0 ,38.0 q
30
q
32
= = α
26
α
28
α
30
α
32
= = = q
31
q
33 )0(
x
36 ,7 ,98.0 ,3.0 9 ,97.0 ,33.0 = = = = = = q
34
q
36 α
34
α
36 )0(
x
31
)0(
x
33
)0(
x
35
)0(
x
37 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. 15 ,99.0 ,33.0 = = = q
35
q
37 α
23
α
25
α
27
α
29
α
31
α
33
α
35
α
37 Đối với các module mua: Hàm mục tiêu: 31 32 33 yrMax + + + + + + + + + yr
31 yr
32 yr
33 11
11
yr
34 34 41 42 43 52 52 Phan Thị Ngọc Mai Trang 68 + + + + + yr
12
12
yr
41 yr
13
13
yr
42 yr
21
21
yr
43 yr
22
22
yr
52 yr
23
23
yr
52 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 Các điều kiện ràng buộc: 31 32 34 34 23
B
' + + + + + + + + yc
31 yc
32 ycyc
33
33 41 12
yc
42 42 13
yc
43 21
yc
52 43 22
yc
52 52 52 1 = + + 1 y
11
y y
12
y y
13
y = + + 21 22 23 1 + = + + y
34 1 y
31
y y
32
y y
33
y = + + 41 42 43 1 = y
52
or 0 1 y
+
51
y
ij = Đối với các module phát triển trong công ty: Hàm mục tiêu: ( ) − α
−
11 x
37 )0(
x
37 yc
12
+ yc
13
+ yc
21
+ yc
22
+ yc
23
≤ yc
11
11
yc
+
41 (max)
r
37 (min)
r
37 Các điều kiện ràng buộc: 37 ' ≤ BB
− x
i ∑ 6 , = = =
i
(max)
r
37 rr
35
36 )0(
r
37 (max)
rq
37
37 ( ) x x α
− − 36 36 )0(
36 ( e
) ; , = − = = r
36 (max)
r
36 )0(
r
36 (max)
r
36 rrr
21
34
22 )0(
r
36 (max)
rq
36
36 ( ) x x α
− − 35 35 )0(
35 e ( ) ; , = − = = r
35 (max)
r
35 )0(
r
35 (max)
r
35 rrrr
20
19
33
32 )0(
r
35 (max)
rq
35
35 ( ) x x α
− − 34 34 )0(
34 e ( ) ; , = − = = r
34 (max)
r
34 )0(
r
34 (max)
r
34 rr
31
18 )0(
r
34 (max)
rq
34
34 ( ) x x α
− − 33 33 )0(
33 e ( ) ; , = − = = r
33 (max)
r
33 )0(
r
33 (max)
r
33 rr
30
17 )0(
r
33 (max)
rq
33
33 ( ) x x α
− − 32 32 )0(
32 ( e
) ; , = − = = (max)
r
32 )0(
r
32 (max)
r
32 rrr
16
15
29 )0(
r
32 (max)
rq
32
32 r
32 ( ) x x α
− − 31 31 )0(
31 ( ) e ; , = − = = r
31 (max)
r
31 )0(
r
31 (max)
r
31 rr
28
14 )0(
r
31 (max)
rq
31
31 ( ) x x α
− − 30 30 )0(
30 ( e
) ; , = − = = r
30 (max)
r
30 )0(
r
30 (max)
r
30 rrr
13
12
27 )0(
r
30 (max)
rq
30
30 ( ) x x α
− − 29 29 )0(
29 ( ) e ; , = − = = r
29 (max)
r
29 )0(
r
29 (max)
r
29 rr
26
11 )0(
r
29 (max)
rq
29
29 ( ) x x α
− − 28 28 )0(
28 ( ) e ; , = − = = (max)
r
28 rr
25
4 )0(
r
28 (max)
rq
28
28 r
28 (max)
r
28 )0(
r
28 ( ) x x α
− − 27 27 )0(
27 ( ) e ; , = − = = (max)
r
27 rr
10
24 )0(
r
27 (max)
rq
27
27 r
27 (max)
r
27 )0(
r
27 ( ) x x α
− − 26 26 )0(
26 ( ) e ; , = − = = r
26 (max)
r
26 )0(
r
26 (max)
r
26 rrr
91
23 )0(
r
26 (max)
rq
26
26 ( ) x x α
− − 25 25 )0(
25 ( ) e ; = − = = r
25 (max)
r
25 )0(
r
25 (max)
r
25 )0(
rrr
,
85
25 (max)
rq
25
25 x x ( ) α
− − 24 24 )0(
24 ( ) e ; = − = = r
24 (max)
r
24 )0(
r
24 (max)
r
24 )0(
rrr
,
73
24 (max)
rq
24
24 ( ) x x α
− − 23 23 )0(
23 ( ) e ; = − = = (max)
r
23 )0(
rrr
,
62
23 (max)
rq
23
23 r
23 (max)
r
23 )0(
r
23 Phan Thị Ngọc Mai Trang 69 (max ) e − 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 ( ) x x α
− − 27 27 )0(
27 (max)
r
27 )0(
r
27 (max)
r
27 )0(
r
27 (max)
rq
27
27 ( ) x x α
− − 26 26 )0(
26 ( ) ; , e = − = = r
27 rr
10
24 (max)
r
26 )0(
r
26 (max)
r
26 )0(
r
26 (max)
rq
26
26 ( ) x x α
− − 25 25 )0(
25 ( ) ; , e = − = = r
26 rrr
91
23 (max)
r
25 )0(
r
25 (max)
r
25 )0(
25 (max)
25 ( ) x x α
− − 24 24 )0(
24 ( ) ; e = − = = r
25 rrr
,
85 rq
25 )0(
r
24 (max)
r
24 )0(
24 (max)
24 (max)
r
24 ( ) x x α
− − 23 23 )0(
23 ( ) e ; = − = = rrr
,
73 rq
24 r
24 (max)
r
23 )0(
r
23 (max)
r
23 )0(
23 (max)
23 ( ) x x − ( ) x x − α
−
6 6 α
−
5 5 )0(
5 )0(
6 ( ) e ; = − = = r
23 rrr
,
62 rq
23 (max)
r
5 )0(
r
5 (max)
r
6 )0(
r
6 ( ) x x − ( ) x x − α
−
8 8 α
−
7 7 )0(
7 )0(
8 ( ) e , ( ) e = − = − r
5 r
6 (max)
r
7 )0(
r
7 (max)
r
8 )0(
r
8 ( ) ( ) x x − − α
−
9 9 α
−
10 x
10 )0(
9 )0(
x
10 ( ) e , ( ) e = − = − r
8 r
7 (max)
r
9 )0(
r
9 (max)
r
10 )0(
r
10 ( ) ( ) − − α
−
11 x
11 α
−
12 x
12 )0(
x
11 )0(
x
12 ( ) e , ( ) e = − = − r
10 r
9 (max)
r
11 )0(
r
11 (max)
r
12 )0(
r
12 ( ) − ( ) − α
−
13 x
13 α
−
14 x
14 )0(
x
13 )0(
x
14 ( ) e , ( ) e = − = − r
11 r
12 (max)
r
13 )0(
r
13 (max)
r
14 )0(
r
14 ( ) ( ) − − α
−
15 x
15 α
−
16 x
16 )0(
x
15 )0(
x
16 ( ) e , ( ) e = − = − r
13 r
14 (max)
r
15 )0(
r
15 (max)
r
16 )0(
r
16 ( ) ( ) − − α
−
17 x
17 α
−
18 x
18 )0(
x
17 )0(
x
18 ( ) e , ( ) e = − = − r
15 r
16 (max)
r
17 )0(
r
17 (max)
r
18 )0(
r
18 ( ) ( ) x x α
− − α
− − 19 x
19 20 20 )0(
x
19 )0(
20 ( ) e , ( ) e = − = − r
17 r
18 (max)
r
19 )0(
r
19 (max)
r
20 )0(
r
20 x x ( ) α
− − ( ) x x α
− − 23 23 21 21 )0(
23 )0(
21 ( ) e , ( ) e = − = − r
19 r
20 (max)
r
23 )0(
r
23 (max)
r
21
, ( ) e , ( ) e = − = − r
23 )0(
r
21
…=
,6 )0(
x
i 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. i 37, ≥ r
21
x
i Đối với các module mua tương tự như bài toán A: Hàm mục tiêu: a) Đối với bài toán B 13 21 22 31 32 33 23 + + + + + + + + + yr
31 yr
32 yr
33 12
+ 34 41 42 43 52 52 Các điều kiện ràng buộc: y
11
+ + + + Maximizer
11
yr
34 yr
12
yr
41 yr
13
yr
42 yr
21
yr
43 yr
22
yr
52 yr
23
yr
52 31 32 34 34 23
B
' + + + + + + + + yc
31 yc
32 ycyc
33
33 41 12
yc
42 42 13
yc
43 21
yc
52 43 22
yc
52 52 52 1 = + + 1 y
11
y y
12
y y
13
y = + + 21 22 23 1 + = + + y
34 1 y
31
y y
32
y y
33
y = + + 41 42 43 1 = y
52
or 0 1 y
+
51
y
ij = Đối với các module phát triển trong công ty: Phan Thị Ngọc Mai Trang 70 yc
12
+ yc
13
+ yc
21
+ yc
22
+ yc
23
≤ yc
11
11
yc
+
41 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 Hàm mục tiêu: 37 ix ∑ 6i
= Các điều kiện ràng buộc: ( ) x x − α
−
11 37 )0(
37 R ( ) e = − (max)
r
37 , = = (max)
r
37 (min)
r
37
rr
35
36 )0(
r
37 (max)
rq
37
37 ( ) x x α
− − 36 36 )0(
36 ( ) e ; , = − = = r
36 (max)
r
36 )0(
r
36 (max)
r
36 rrr
21
34
22 )0(
r
36 (max)
rq
36
36 ( ) x x α
− − 35 35 )0(
35 ( ) e ; , = − = = r
35 (max)
r
35 )0(
r
35 (max)
r
35 rrrr
20
19
33
32 )0(
r
35 (max)
rq
35
35 x x ( ) α
− − 34 34 )0(
34 Min (max)
r
34 )0(
r
34 (max)
rq
34
34 (max)
r
34 )0(
r
34 x x ( ) α
− − 33 33 )0(
33 ( ) ; , e = − = = rr
31
18 r
34 (max)
r
33 )0(
r
33 (max)
r
33 )0(
r
33 (max)
rq
33
33 x x ( ) α
− − 32 32 )0(
32 ( ) ; , e = − = = r
33 rr
30
17 (max)
r
32 )0(
r
32 (max)
r
32 29 )0(
r
32 (max)
rq
32
32 x x ( ) α
− − 31 31 )0(
31 ( ) ; , e = − = = r
32 rrr
16
15 (max)
r
31 )0(
r
31 (max)
r
31 )0(
r
31 (max)
rq
31
31 x x ( ) α
− − 30 30 )0(
30 ( ) ; , e = − = = r
31 rr
28
14 (max)
r
30 )0(
r
30 (max)
rq
30
30 (max)
r
30 )0(
r
30 x x ( ) α
− − 29 29 )0(
29 ( ) ; , e = − = = rrr
13
12
27 r
30 (max)
r
29 )0(
r
29 (max)
rq
29
29 )0(
r
29 (max)
r
29 x x ( ) α
− − 28 28 )0(
28 ( ) ; , e = − = = rr
26
11 r
29 (max)
r
28 )0(
r
28 (max)
rq
28
28 (max)
r
28 )0(
r
28 x x ( ) α
− − 27 27 )0(
27 ( ) ; , e = − = = rr
25
4 r
28 (max)
r
27 )0(
r
27 (max)
r
27 )0(
r
27 (max)
rq
27
27 x x ( ) α
− − 26 26 )0(
26 ( ) ; , e = − = = r
27 rr
10
24 (max)
r
26 )0(
r
26 (max)
r
26 )0(
r
26 (max)
rq
26
26 x x ( ) α
− − 25 25 )0(
25 ( ) ; , e = − = = r
26 rrr
91
23 (max)
r
25 )0(
25 (max)
25 (max)
r
25 )0(
r
25 x x ( ) α
− − 24 24 )0(
24 ( ) ; e = − = = rrr
,
85 rq
25 r
25 (max)
r
24 )0(
r
24 (max)
r
24 )0(
24 (max)
24 x x ( ) α
− − 23 23 )0(
23 ( ) e ; = − = = r
24 rrr
,
73 rq
24 (max)
r
23 )0(
23 (max)
23 (max)
r
23 )0(
r
23 x x ( ) − x x ( ) − α
−
6 6 α
−
5 5 )0(
5 )0(
6 ( ) e ; = − = = rrr
,
62 rq
23 r
23 (max)
r
5 )0(
r
5 (max)
r
6 )0(
r
6 x x ( ) − x x ( ) − α
−
8 8 α
−
7 7 )0(
7 )0(
8 ( ) e , ( ) e = − = − r
6 r
5 (max)
r
7 )0(
r
7 (max)
r
8 )0(
r
8 x x ( ) ( ) − − α
−
10 x
10 α
−
9 9 )0(
x
10 )0(
9 ( ) e , ( ) e = − = − r
8 r
7 (max)
r
9 )0(
r
9 (max)
r
10 )0(
r
10 ( ) ( ) − α
− − 12 x
12 α
−
11 x
11 )0(
x
12 )0(
x
11 ( ) e , ( ) e = − = − r
10 r
9 (max)
r
11 )0(
r
11 (max)
r
12 )0(
r
12 ( ) − ( ) − α
−
13 x
13 α
−
14 x
14 )0(
x
13 )0(
x
14 ( ) e , ( ) e = − = − r
11 r
12 (max)
r
13 )0(
r
13 (max)
r
14 )0(
r
14 ( ) ( ) − − α
−
15 x
15 α
−
16 x
16 )0(
x
15 )0(
x
16 ( ) e , ( ) e = − = − r
13 r
14 (max)
r
15 )0(
r
15 (max)
r
16 )0(
r
16 ( ) ( ) − − α
−
18 x
18 α
−
17 x
17 )0(
x
18 )0(
x
17 ( ) e , ( ) e = − = − r
15 r
16 (max)
r
17 )0(
r
17 (max)
r
18 )0(
r
18 ( ) ( ) x x α
− − α
− − 20 20 19 x
19 )0(
20 )0(
x
19 ( ) e , ( ) e = − = − r
17 r
18 (max)
r
19 )0(
r
19 (max)
r
20 )0(
r
20 ( ) x x α
− − ( ) x x α
− − 23 23 21 21 )0(
23 )0(
21 ( ) e , ( ) e = − = − r
19 r
20 (max)
r
23 )0(
r
23 (max)
r
21
, , ( ) e ( ) e = − = − r
23 )0(
r
21
…=
,6 )0(
x
i Phan Thị Ngọc Mai Trang 71 i 37, ≥ r
21
x
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 [ , Đối với bài toán A: ijy r …
,
]
6 r
36 [ , B B’ x …
,
]
6 x
37 Độ tin
cậy
tối ưu
( 37r ) 0.0014 288 33 100
1000
100
100
10 [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.0054 299 44 001
0001
001
001
01 [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] 500 44 0.5574 001
0001
001
001
01 [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 600 44 001
0001
001
001
01 [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] [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]
[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]
[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]
[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]
[9.00, 5.00, 90.95, 1000 44 0.5647 001
0001
001
001
01 [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] 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] Phan Thị Ngọc Mai Trang 72 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 [ , ijy r …
]
,
6 r
36 [ , B’ x …
,
]
6 x
37 Chi
phí
phần
mềm
(B) Độ tin
cậy
phần
mềm
( 37r ) 100 1000 0.0014 33 287 100 100 [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] 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] 001 0001 324.68 001 0.2 44 001 01 [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] [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] 001 0001 340.77 001 0.3 44 001 01 [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] [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] 001 0001 378.91 001 0.5 44 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] Phan Thị Ngọc Mai Trang 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 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ế: (cid:131) 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. (cid:131) 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. (cid:131) 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ó. (cid:131) 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: (cid:131) 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í. Phan Thị Ngọc Mai Trang 74 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 (cid:131) 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. (cid:131) 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. (cid:131) 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. Phan Thị Ngọc Mai Trang 75 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 Springer 1999, ISBN 0-7923-5458-3 [1] Jonathan F.Bard “Practical Bilevel Optimization Algorithms and Applications” Computer Engineering Carleton University Ottawa, Ontario K1S 5B6 Canada 74Hhttp://www.sce.carleton.ca/faculty/chinneck/po.html. [2] John W. Chinneck “Practical Optimization: A Gentle Introduction” Systems and [3] Hoang Pham, “Software Reliability” Springer – Verlag Singapore Pte.Ltd.2000 bản thống kê. [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 Đại học Quốc gia Tp.HCM. [5] Nguyễn Đức Thành, “MATLAB và ứng dụng trong điều khiển” Nhà xuất bản 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. [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 Advances in Reliability and Quality Engineering”, Vol.2, Series on Quality, Reliability & Engineering Statistisc, Editor Hoang Pham, Word Scientific, 2001 0.2, 1.1 Phan Thị Ngọc Mai Trang 76 [7] O.Berman and M.Cutler, “Cost Allocation for Software Reliability, Recent 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 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 Phan Thị Ngọc Mai Trang 77 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 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 )(
tm )(
s ds λ ∫= 0 Hàm độ tin cậy của phần mềm là: t )(
s ds − λ )(
tm − 0 ∫ )(
tR e e = = bt − Loại mô Tên mô hình MVF (m(t)) hình 1( ) a e = − a = Goel-Okumoto (G-O) Concave bt − )(
tm
)(
ta
)(
tb b = 1(1( )
ebt ) +− )(
tm
)(
ta a
a =
= Delayed S-shaped S-shaped 2
tb
bt
+ bt − )(
tb = 1 bt − ) )(
tm = e
−
e
β )(
ta 1(
a
1
+
a = Inflection S-shaped Concave bt − ( ) − t
β 1( ) e − r
α − )(
tb = 1 b
e
β + 1( e ) − − t
β )(
tm
)(
ta a
a =
= Yamade exponential Concave Phan Thị Ngọc Mai Trang 78 )(
tb = te
r
αβ 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/2 − t
β 1( e ) − r
α − tm
)( a 1( e ) = − ta
)( a = 2 2/ − t
β tb
)( = te
r
αβ bt − tm
)( t
α
e ( e ) = − b Yamada Rayleigh S-shaped ab
+
α
t
α
ae )(
ta = )(
tb b = bt − )(
tm 1[
a e 1][ at = − − + α α
]
b Yamada imperfect debugging model (1) S-shaped t
α )(
ta ae = )(
tb b = bt − Yamada imperfect debugging model (2) S-shaped −
β 1][ 1[
a e at − − + α )(
tm = α
]
b
bt S-shaped + )(
ta a 1( 1
) = t
α và Pham-Nordmann bt − bt − concave )(
tb = 1 +
b
e
β + bt bt − t
−
α e tm
)( [( 1)( ) = ac
+ − 1 + 1
−
β S-shaped ( e e )] − − t
−
α bt − Phan Thị Ngọc Mai Trang 79 và Pham-Zhang )(
ta ) a
b
−
α
1(
e
ac
− += concave )(
tb = 1 b
e
β + 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 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ỉ 7www.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]. dạng: Hàm mục tiêu: Minimize . yf các điều kiện ràng buộc: 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ó b .
yA trong đó: ≤
.
Aeq
y beq = (cid:131) : các vector ,
bf , beq (cid:131) : các ma trận (cid:131) 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: (cid:131) y = bintprog(f) (cid:131) y = bintprog(f, A, b) (cid:131) y = bintprog(f, A, b, Aeq, beq) (cid:131) [y, fval] = bintprog(...) (cid:131) [y,fval, exitflag] = bintprog(...) (cid:131) [y, fval, exitflag, output] = bintprog(...) Phan Thị Ngọc Mai Trang 80 A, Aeq 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 Mô tả: (cid:131) 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 . yf (cid:131) 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: yfMin . với điều kiện ràng buộc: (cid:131) 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 . yf với điều kiện ràng buộc: b yA ≤. b .
yA (cid:131) [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 đó. (cid:131) [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. (cid:57) Exitflag =1 : hàm hội tụ đến 1 giải pháp y. (cid:57) Exitflag =0 : số lượng lần lặp đi lặp lại vượt quá Options.MaxIter (cid:57) Exitflag =-2 : bài toán không thể làm được. (cid:57) Exitflag =-4 : số lượng node vượt quá số lần lặp cực đại được cho phép (Options.MaxIter). ≤
.
Aeq
y beq = (cid:57) Exitflag =-5 : thời gian tìm kiếm vượt quá Options.Maxtime. Hàm mục tiêu: min xf
)( Phan Thị Ngọc Mai Trang 81 b) Hàm fmincon: tìm nghiệm tối ưu của hàm nhiều biến có dạng: 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 Các điều kiện ràng buộc: 0 0)(
xc
≤
)(
x ceq beq =
*
bxA
≤
Aeq
*
x
=
ub lb x
≤≤ Trong đó (cid:131) là các vector ,
bx
, beq , lb , ub (cid:131) là các ma trận. A, Aeq (cid:131) là các hàm trả về các vertor xc
( ), ceq x
)( (cid:131) có thể là các phương trình phi tuyến. Cú pháp: (cid:131) x = fmincon(fun,x0,A,b) (cid:131) x = fmincon(fun,x0,A,b,Aeq,beq) (cid:131) x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub) (cid:131) x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon) (cid:131) x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options) (cid:131) [x,fval] = fmincon(...) (cid:131) [x,fval,exitflag] = fmincon(...) (cid:131) [x,fval,exitflag,output] = fmincon(...) (cid:131) [x,fval,exitflag,output,lambda] = fmincon(...) (cid:131) [x,fval,exitflag,output,lambda,grad] = fmincon(...) (cid:131) [x,fval,exitflag,output,lambda,grad,hessian] = fmincon(...) Mô tả: (cid:131) 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. Phan Thị Ngọc Mai Trang 82 xcxf
), ( ( ), ceq x
)( 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 (cid:131) 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. (cid:131) 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. (cid:131) 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. (cid:131) 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. (cid:131) [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 đó. (cid:131) [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. (cid:131) [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á. (cid:131) [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. (cid:131) [x,fval,exitflag,output,lambda,grad] = fmincon(...) trả về giá trị gradient của fun tại giải pháp x. (cid:131) [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. Phan Thị Ngọc Mai Trang 83 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 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 Biến nhị phân, 9, 14, 15, 16, 17, 19, 39
Branch and bound, 5, 18, 78 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 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 Ngân sách, 1, 9, 11, 13, 14, 39, 40 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 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 Quy hoạch nguyên, 2, 5, 15, 16, 18, 38, 75 Đ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, Quy hoạch phi tuyến 5, 27, 53, 75, 76 41, 57, 62, 68, 79, 81 Độ tin cậy tối đa, 7, 9
Độ tin cậy tối thiểu, 7, 9 Số lượng biến, 18 Giải pháp, 22, 78
Giải thuật, 5, 15, 18, 19, 22, 23, 76 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 Hàm lồi, 26
Hàm mục tiêu, 15, 19, 21, 23, 25, 27, Tổng chi phí, 38 29, 30, 34, 35, 38, 39, 41, 44, 48, 49,
58, 59, 63, 64, 65, 69, 70, 71, 72 Hessian, 28, 30, 35 Vector, 29, 31, 34, 35
Version, 7, 8, 9, 11, 14, 38, 39 Lagrangian, 32 Xác định dương, 27, 28, 30, 33, 35, 36 Ma trận, 28, 30, 31, 32, 33, 35, 36 Phan Thị Ngọc Mai Trang 84Bước 1: (Khởi tạo) Tại
Bước 2: (Tính toán bounds) Tại
Bước 3: (Thăm dò) Nếu
Bước 4: (Backtracking) nếu không có node nào tồn tại thì di chuyển sang bước 6.
Bước 5: (Phân chia và phân nhánh) Phân chia trên
Bước 6: (Kết thúc) Nếu
Ví dụ 3.4: Xét bài toán sau:
Bước 1: Ta có
Hình 3.3 : Cây tìm kiếm cho ví dụ 3.2
Chương 4. Phương Pháp Giải Bài Toán Quy Hoạch
Phi Tuyến
4.1. Giới thiệu
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
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ì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
4.3. Tính lồi của hàm nhiều biến
4.3.1. Tập lồi
4.3.2. Định nghĩa hàm lồi
4.3.3. Đặc trưng của hàm lồi
Định lý 4.3.1: Xét hàm n biến
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
Chú ý: với mọi điểm x trong
Định lý 4.4.1 Cho
Định lý 4.4.2 Cho
Ví dụ 4.4.1 Cho
Lời giải:
Bước 1: Tính
Bước 2: Thực hiện kiểm tra từng trường hợp:
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
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
Ví dụ 4.4.2: Xét bài toán
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
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
Định nghĩa 4.4.3: Cho một điểm
Định
lý 4.4.3: Tại điểm
Định lý 4.4.4: Trong bài toán (4.11), cho f có một cực tiểu tại *x . Nếu f và mỗi
Ví dụ 4.4.3: Tìm cực trị của hàm số
Định lý 4.4.5: (điều kiện cần) Giả sử *x là một cực tiểu của
Định lý 4.4.6: (điều kiện đủ) Giả sử điểm *x thỏa mãn điều kiện
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
Định nghĩa 4.4.4: Cho *x là một điểm thỏa mãn điều kiện
Định lý 4.4.7 (Kuhn – Tucker Conditions): Cho *x là một điểm cực tiểu của bài
Định lý 4.4.8: (điều kiện cần) Giả sử các hàm
Định lý 4.4.9: (điều kiện đủ) Cho
Ví dụ 4.4.4: Xét bài toán
Chương 5. Giải Quyết Bài Toán
5.1. Phân hoạch bài toán
Hình 5.1: Sự phân hoạch bài toán
5.2. Bài toán tối ưu hóa các module mua
Ví dụ 5.1: Dựa vào ví dụ 2.1, giả sử phần mềm có hai module mua. Trong đó,
5.3. Bài toán tối ưu hóa các module phát triển trong công ty
Ví dụ 5.2: Dựa vào ví dụ 2.1 chúng được thể hiện rõ qua hình 5.1, ta nhận thấy:
5.4. Sự kết hợp module mua và module phát triển trong công ty
5.4.1. Bài toán A
a) Nếu phần mềm có một module:
Chú ý: việc tìm ra độ tin cậy phần mềm quá nhỏ nhiều lúc lại không thỏa mãn
Bước 1: (Khởi tạo) nhập vào các thông số của module phần mềm:
Bước 2: Nhập chi phí để phát triển phần mềm ( B ). Nếu ∑
Bước 3: Nhập
Bước 4: Tính độ tin cậy và chi phí cho từng module mua, chuyển sang bước 5.
Bước 5: Thiết lập mối quan hệ, những điều kiện ràng buộc giữa các module đơn
Bước 6: Tìm độ tin cậy lớn nhất của các module trong phần mềm và chi phí của
Bước 7: Nhập giai đoạn hiệu chỉnh. Khi Y=0 thì chuyển sang bước 1 và thực hiện
Bước 8: (Kết thúc) Xuất độ tin cậy của phần mềm, độ tin cậy của các module,
Begin
End
Hình 5.2: Sơ đồ giải thuật cho bài toán A
5.4.2. Bài toán B
a) Nếu phần mềm là một module:
Nhận xét: Việc tìm một version có độ tin cậy là một hằng số bằng độ tin cậy
Chú ý: việc tìm chi phí nhỏ nhất để phần mềm có độ tin cậy là một hằng số cho
Bước 1: (Khởi tạo) nhập vào các thông số:
Bước 2: Nhập tổng chi phí để mua các module (
Bước 3: Nhập độ tin cậy phần mềm, chuyển sang bước 4
Bước 4: Tính ra độ tin cậy và chi phí cho từng module mua, chuyển sang bước 5.
Bước 5: Thiết lập mối quan hệ và các ràng buộc giữa các module đơn và module
Bước 6: Tìm chi phí nhỏ nhất của các module trong phần mềm và độ tin cậy của
Bước 7: Nhập giai đoạn hiệu chỉnh. Khi Y=0 thì chuyển sang bước 1 và thực hiện
Bước 8: (Kết thúc) Xuất tổng chi phí của phần mềm, độ tin cậy của các module,
Begin
End
Hình 5.3: Sơ đồ giải thuật cho bài toán B
Chương 6. Một số kết quả, kết luận
6.1. Sơ lược về chương trình
6.2. Một số kết quả chạy chương trình
function Vidu4_3_2
function f=myfun(x)
end
end
function Vidu4_3_4
function f=myfun(x)
end
function [c, ceq]=fun(x)
end
end
Đối với bài toán A:
Bảng 6.1: Kết quả chạy phần mềm có 6 module cho bài toán A
Đối với bài toán B:
Bảng 6.2: Kết quả chạy phần mềm có 6 module cho bài toán B
Hình 6.1: Mô hình một phần mềm có 11 module
b) Bài toán B
Đối với bài toán A:
Bảng 6.3: Kết quả chạy phần mềm có 11 module cho bài toán A
Đối với bài toán B:
Bảng 6.4: Kết quả chạy phần mềm có 11 module cho bài toán B
Hình 6.2: Mô hình một phần mềm có 22 module
a) Bài toán A
Đối với bài toán A:
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:
Bảng 6.6: Kết quả chạy phần mềm có 22 module cho bài toán B
Hình 6.3: Mô hình một phần mềm có 37 module
a) Đối với bài toán A
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:
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ài Liệu Tham Khảo
Phụ lục 1. Bảng đối chiếu Thuật ngữ
Anh - Việt
Phụ lục 2. Bảng tóm tắt các mô hình đánh giá
độ tin cậy phần mềm
Phụ lục 3. Sơ lược về MATLAB
Tham khảo Chỉ Mục
B
C
N
P
D
Q
S
G
T
H
V
L
X
M
