Đại Học Quốc Gia Thành Phố Hồ Chí Minh
Trường Đại Học Bách Khoa
PHAN THỊ NGỌC MAI

MỘT GIẢI PHÁP TOÁN HỌC CHO VIỆC PHÂN PHỐI
TÀI NGUYÊN TRONG ĐỘ TIN CẬY PHẦN MỀM
Chuyên ngành: Khoa học Máy tính
LUẬN VĂN THẠC SĨ
TP. HỒ CHÍ MINH, tháng 06 năm 2008 ĐẠI HỌC QUỐC GIA TP. HCM CỘNG HOÀ XÃ HỘI CHỦ NGHIÃ VIỆT NAM

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ấp ở trường này hoặc trường khác.

Ngày 30 tháng 06 năm 2008
Phan Thị Ngọc Mai
Một giải pháp toán học cho việc phân phối chi phí trong độ tin cậy phần mềm
Phan Thị Ngọc Mai Trang ii
LỜI CẢM ƠN

Tôi xin gởi lời cảm ơn chân thành nhất đến TS. Nguyễn Văn Minh Mẫn, người
đã tận tình hướng dẫn, giúp đỡ tôi trong suốt quá trình thực hiện luận văn và tạo điều
kiện để tôi có thể hoàn thành luận văn này.
Xin gởi lời cảm ơn đến các Thầy Cô đã dạy tôi trong thời gian qua. Tôi xin cảm
ơn các bạn đồng môn và đồng nghiệp đã quan tâm, chia sẽ trong suốt quá trình học và
làm luận vă
n.
Xin cảm ơn gia đình đã dành cho tôi tình thương yêu và sự hỗ trợ tốt nhất. Một giải pháp toán học cho việc phân phối chi phí trong độ tin cậy phần mềm
Phan Thị Ngọc Mai Trang iii
TÓM TẮT LUẬN VĂN

Đánh giá độ tin cậy phần mềm là một vấn đề quan trọng trong việc đánh giá chất
lượng của một phần mềm. Quá trình này thường được thực hiện trong các giai đoạn
thiết kế phần mềm, kiểm tra lỗi phần mềm.
Công việc kiểm tra lỗi phần mềm được triển khai xuyên suốt các giai đoạn phát
triển phần mềm, công việc này giúp giảm chi phí và nâng cao chất lượng phầ

MỤC LỤC
LỜI CAM ĐOAN ...........................................................................................................i

LỜI CẢM ƠN ............................................................................................................... ii

TÓM TẮT LUẬN VĂN .............................................................................................. iii

DANH MỤC HÌNH ..................................................................................................... vi

DANH MỤC BẢNG ................................................................................................... vii

Chương 1.

GIỚI THIỆU...............................................................................................1

1.1. Giới thiệu ..............................................................................................................1
1.2. Sơ lược về việc phân phối độ tin cậy phần mềm...............................................2
1.3. Kết cấu của luận văn ...........................................................................................4
Chương 2.

Các Mô Hình Phân Phối Chi Phí Cho Độ Tin Cậy Phần Mềm .............6

2.1. Giới thiệu ..............................................................................................................6
2.2. Phân loại các module trong phần mềm..............................................................6
2.3. Mô hình quyết định trước...................................................................................7
2.3.1.

Độ tin cậy của một module đơn phát triển trong công ty............................................7

2.3.2.


4.3.3.

Đặc trưng của hàm lồi...............................................................................................26

4.4. Các phương pháp giải bài toán quy hoạch phi tuyến.....................................27
4.4.1.

Giải bài toán tối ưu không có điều kiện ràng buộc ...................................................27

4.4.2.

Giải bài toán tối ưu với điều kiện ràng buộc các biến lớn hơn 0 ..............................28

4.4.3.

Giải bài toán tối ưu với điều kiện ràng buộc là các phương trình tuyến tính............30

4.4.4.

Giải bài toán tối ưu với điều kiện ràng buộc là các phương trình phi tuyến.............34

Chương 5.

Giải Quyết Bài Toán ................................................................................36

5.1. Phân hoạch bài toán ..........................................................................................36
5.2. Bài toán tối ưu hóa các module mua................................................................37
5.3. Bài toán tối ưu hóa các module phát triển trong công ty...............................39
Một giải pháp toán học cho việc phân phối chi phí trong độ tin cậy phần mềm

Bài toán trong ví dụ 4.3.4 .........................................................................................52

6.2.5.

Bài toán cho một phần mềm gồm có 6 module.........................................................54

6.2.6.

Bài toán cho một phần mềm gồm có 11 module.......................................................56

6.2.7.

Bài toán cho một phần mềm gồm có 22 module.......................................................61

6.2.8.

Bài toán cho một phần mềm gồm có 37 module.......................................................67

6.3. Kết luận...............................................................................................................74
Tài Liệu Tham Khảo...................................................................................................76

Phụ lục 1. Bảng đối chiếu Thuật ngữ Anh - Việt......................................................77

Phụ lục 2. Bảng tóm tắt các mô hình đánh giá độ tin cậy phần mềm ....................78

Phụ lục 3. Sơ lược về MATLAB.................................................................................80

Tham khảo Chỉ Mục ...................................................................................................84
DANH MỤC BẢNG Bảng 2.1: Giải pháp cho những nguồn ngân sách khác nhau .................................13

Bảng 6.1: Kết quả chạy phần mềm có 6 module cho bài toán A.............................54

Bảng 6.2: Kết quả chạy phần mềm có 6 module cho bài toán B.............................55

Bảng 6.3: Kết quả chạy phần mềm có 11 module cho bài toán A...........................59

Bảng 6.4: Kết quả chạy phần mềm có 11 module cho bài toán B...........................60

Bảng 6.5: Kết quả chạy phần mềm có 22 module cho bài toán A...........................65

Bảng 6.6: Kết quả chạy phần mềm có 22 module cho bài toán B...........................66

Bảng 6.7: Kết quả chạy phần mềm có 37 module cho bài toán A...........................72

Bảng 6.8: Kết quả chạy phần mềm có 37 module cho bài toán B...........................73
Một giải pháp toán học cho việc phân phối tài nguyên trong độ tin cậy phần mềm

Phan Thị Ngọc Mai Trang 1
Chương 1. GIỚI THIỆU
1.1.
Giới thiệu
Trong vài thập niên gần đây, cùng với sự xuất hiện của máy tính, các phần mềm


Phan Thị Ngọc Mai Trang 2
 Tìm chi phí nhỏ nhất để phần mềm có độ tin cậy là một hằng số xác định
trước.
Với những mục tiêu này đề tài đã thu được một số kết quả:
 Xây dựng được mô hình tổng quát cho bài toán quy hoạch nguyên dạng
nhị phân, trên cơ sở đó áp dụng cho bài toán tối ưu hóa các module mua.
 Xây dựng được mô hình tổng quát cho bài toán quy hoạch phi tuyến, trên
cơ sở đó áp dụng cho bài toán tối
ưu hóa các module phát triển trong công
ty.
 Xây dựng được một mô hình phân phối chi phí để phần mềm có độ tin cậy
lớn nhất.
 Xây dựng được một mô hình phân phối chi phí nhỏ nhất để phần mềm có
độ tin cậy là một hằng số cho trước.
1.2.
Sơ lược về việc phân phối độ tin cậy phần mềm
Quá trình phân phối chi phí cho độ tin cậy phần mềm được thực hiện như sau:
Đầu tiên, xác định các module trong phần mềm module nào là module đơn và
module nào là module tích hợp. Module đơn nào được phát triển trong công ty và
module đơn nào sẽ được mua bên ngoài thị trường.
Tiếp theo, xác định công thức tính độ tin cậy cho từng loại module:
 Đối với module mua, mỗi module mua có nhiều version trên thị trường,
ứng với mỗi version đều có độ tin cậy và chi phí khác nhau. Độ tin cậy và
chi phí của một module bằng
độ tin cậy và chi phí của version mà chúng ta
lựa chọn mua. Với lý do tiết kiệm chi phí, do đó chúng ta phải lựa chọn
duy nhất một trong số các version đã cho. Do đó để thực hiện được vấn đề
này, chúng ta đưa một biến thực hiện công việc lựa chọn mua hay không
mua một version nào đó. Đó là các biến nguyên nhị phân.

. Do module mua cũng là một module đơn
trong phần mềm, và các module tích hợp được tích hợp từ các module
đơn. Do đó, với việc giải quyết bài toán tối ưu hoá các module mua, chúng
ta đã tìm được độ tin cậy và chi phí cho các module mua. Kết quả sẽ được
đưa vào để giải quyết bài toán tối ưu hoá các module phát triển trong công
ty.
 Đối với bài toán các module phát triển trong công ty, do cấu trúc bài toán
hàm mục tiêu là một hàm nhiều biến, lại liên quan đến hàm số mũ. Cho
nên để thực hiệ
n được bài toán ta sử dụng phương pháp quy hoạch phi
tuyến để giải quyết, thông qua đây ta cũng tìm được độ tin cậy và chi phí
cho từng module trong phần mềm cũng như độ tin cậy của phần mềm. Tuy
nhiên, để đảm bảo bài toán tìm được lời giải tối ưu nhất, chúng ta cần phải
xem xét nguồn chi phí cung cấp có đủ để phát triển phần mềm chưa, cũng
như việc phân chia chi phí giữa các module mua và module phát triể
n
Một giải pháp toán học cho việc phân phối tài nguyên trong độ tin cậy phần mềm Phan Thị Ngọc Mai Trang 4
trong công ty có hợp lý chưa, và các thông số nhập vào có đảm bảo phần
mềm có độ tin cậy thoả mãn không. Đây là các vấn đề bài toán A trong
chương 5 sẽ giải quyết.
Một vấn đề khác nhà quản lý đặc ra, với độ tin cậy độ đã định trước, tìm chi phí
nhỏ nhất ứng với độ tin cậy đã cho. Đây là một bài toán ngược với bài toán A. Để thực
hiện được vấn đề này, các công việ
c sau đây cần giải quyết:

Đối với các module mua các verion của các module mua có độ tin cậy và
chi phí là một hằng số xác định trước. Vì vậy, công việc tìm độ tin cậy của


Phan Thị Ngọc Mai Trang 5
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.

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ới lý do phân bổ nguồn tài nguyên hợp lý để tạo ra phần mềm có tính tin cậy
cao mà tiết kiệm được chi phí. Dựa vào nguồn lực hiện có của công ty, nhà quản lý
quyết định phần module nào sẽ được phát triển trong công ty, phần nào sẽ mua, và
phần nào sẽ dùng lại.

 Một module được xem thích hợp để phát triển trong công ty khi trong
công ty có đầy đủ điều kiện để phát triển và việc triển trong công ty có thể
Một giải pháp toán học cho việc phân phối tài nguyên trong độ tin cậy phần mềm Phan Thị Ngọc Mai Trang 7
sẽ tiết kiện hơn so với việc mua từ bên ngoài. Loại module này bao gồm
module đơn và module tích hợp.
 Một module được xem thích hợp để mua khi có nhiều version trên thị
trường và trong công ty có thể không có đầy đủ điều kiện để phát triển
hoặc chi phí để mua có thể tiết kiệm hơn so với việc phát triển trong công
ty. Loại module này là module đơn.
 Một module được xem thích hợp dùng lại khi trong công ty đã có sẳn (do
trong công ty phát triển hoặ
c đã mua trước đó) và việc dùng lại này rõ
ràng không tốn chi phí nào.
Vấn đề chính trong bài toán này là phân phối chi phí cho độ tin cậy phần mềm.
Do đó, chúng ta chỉ xem xét các mô hình phát triển phần mềm chỉ bao gồm các
module mua và các module phát triển trong công ty, còn phần module dùng lại do
không có sự tham gia của nhân tố chi phí cho nên chúng ta sẽ không được xét đến.
2.3. Mô hình quyết định trước
Nhiệm vụ của mô hình quyết định trước là xác định trước một module sẽ được
mua hoặc được phát triể
n trong công ty.

i
r
. Nhưng
với mức độ đúng đắn 100% rất khó xẩy ra, do đó
(max)
i
r
là một giá trị nhỏ hơn hoặc
bằng 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 Phan Thị Ngọc Mai Trang 8
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à r
i
:

(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í

=
ij
y
thì version
j
của module
i
được mua, ngược lại
0
=
ij
y
thì
version
j
của module
i
không được mua. Với mục tiêu của mô hình là cực đại hóa độ
tin cậy của phần mềm được ràng buộc trên tổng ngân sách đã cho (B). Do đó, để tiết
kiệm chi phí mỗi module mua chỉ mua duy nhất một version trên thị trường, chúng ta
cần điều kiện sau
1
1
=
∑
=
i
n
j
ij

i
2,
. . . , i
s
là các module tạo thành module T
i
. Ta gọi
module
T
i
là một module tích hợp. Độ tin cậy của một module tích hợp T
i
phụ thuộc vào độ tin
cậy của các module con của T
i
.
Cho
)(m
T
i
r
là độ tin cậy lớn nhất có thể đạt được của module tích hợp
i
T
. Giả sử
việc thực thi chương trình của các module con là theo một trình tự và không có sự phụ
thuộc lẫn nhau. Do đó độ tin cậy tối đa có thể đạt được của module
i
T
được tính theo

TT
qq
là một hệ số phản ánh sự tương thích giữa các module. Vì vậy
(max)
1
)0(
iiii
TT
s
k
iTT
rqrqr ==
∏
=
.
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 T
i
là:
Một giải pháp toán học cho việc phân phối tài nguyên trong độ tin cậy phần mềm Phan Thị Ngọc Mai Trang 10
⎪
⎭
⎪
⎬
⎫
⎪

(2.3)
trong
đó

i
α
,
i
x
và
)0(
i
x
đã được định nghĩa trong phần trước.
Công thức độ tin cậy phần mềm (
) phụ thuộc vào cấu trúc của phần mềm
:
 Nếu phần
mềm
chỉ là một module đơn thì là bằng độ tin cậy của
module đó.
 Nếu phần mềm chỉ là một module được phát triển trong công ty thì công
thức độ tin cậy là công thức (2.1).
 Nếu phần mềm chỉ là một mudule mua thì công thức độ tin cậy là công
thức (2.2).
 Nếu phần mềm là một hệ thống có nhiều hơn một module thì module gốc
phải là một module tích hợp và độ tin cậy phần mề
m phụ thuộc vào độ tin
cậy của các module con. Công thức tính độ tin cậy phần mềm là công thức
(2.3). Khi một số module con là các module tích hợp, công thức độ tin cậy

Bài toán (P) có
thể
viết:
Max
(P1)
S.T.
Bxyc
n
mi
iij
m
i
n
j
ij
i
≤+
∑∑∑
+=== 111
1
(P2)
1
1
=
∑
=
i
n
j
ij

 (P2) đảm
bảo
tổng chi phí sử dụng không vượt quá ngân sách cho phép.
 P(3) chắc chắn sẽ có duy nhất một version được module i mua, với
.,...,2,1 mi =

 (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ộ y
ij
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

Database-indexing (6)

Parser (1)

Keyword (5)

Index-generator (3)

Version 11

Version 12

Analyzer (4)

Stemmer (2)

trên. Sự thực hiện đầy đủ của một database-indexing bao gồm các module (xem hình
2.2):
 Parser(1)
và
Stemmer(2) là các module mua. Mỗi module mua có 2
version.
 Index-
generator
(3) và Analyzer(4) là hai module đơn.
 Keyword(5) là
module
tích hợp từ hai module Analyzer(4) và Stemmer(2).
 Database-indexing task(6) là module tích hợp từ ba module Keywork(5)
với Index-generator(3) và Parter(1).
Các số ngẫu nhiên được chọn cho ví dụ
:
3,3.0,8.0
4,25.0,7.0
5.3,4.0,5.0,9.0
2,3.0,53.0,83.0
8,95.0
7,87.0
6,9.0
5,7.0
)0(
666
)0(
555
)0(
44

cr
cr
m
m
α
α
α
α

Để 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).
Otherwise
x
e
r
x
e
r
yryrr
yryrr
x
x
5.3
0
)5.09.0(9.0
Otherwise
2
0
)53.083.0(83.0
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 Phan Thị Ngọc Mai Trang 13
Otherwise
x
errr
r
x
mm
m
4
0
)(
5
)3(25.0
)0(
5
)(
5
)(
5
5
6
≥
⎩
⎨
⎧
−−

0
)(
6
)3(3.0
)0(
6
)(
6
)(
6
6
6
≥
⎩
⎨
⎧
−−
=
−−

khi đó
351
)(
6
rrrr
m
= và
)(
6
)0(

bài toán ta thu được các kết quả sau:
B y
11
y
12
y
21
y
22
x
3
x
4
x
5
x
6

Độ tin cậy
Tối ưu
25 1 0 1 0 2 4 4 3 0.11826
26 0 1 1 0 2 4 4 3 0.15205
30 0 1 0 1 3.3816 5.6183 4 3 0.2518
35 0 1 0 1 5.1168 6.9833 4.7556 4.1441 0.3491
40 0 1 0 1 6.3842 7.9627 6.2414 5.4115 0.4269
45 0 1 0 1 7.6511 8.9325 7.7371 6.6785 0.4870
50 0 1 0 1 8.9178 9.8958 9.2410 9.9452 0.5316
55 0 1 0 1 10.1842 10.8547 10.7494 9.2116 0.5639
60 0 1 0 1 11.4505 11.8105 12.2610 10.4778 0.5868
70 0 1 0 1 13.9826 13.7167 15.2906 13.0099 0.6140

∑
=
i
n
j
ij
y
1
=1. Gọi r
i
là độ tin cậy của module i được phát triển trong
công ty với chi chí x
i
,
ijij
cr
,
là độ tin cậy và chi phí của một version j của module i. Do
đó, đối với bất kỳ một module phần mềm i nào có độ tin cậy R
i
được cho bởi:
∑
=
+=
i
n
j
ijijiii
yrzrR
1

∑∑∑
===
111
(GP2)
1
1
=+
∑
=
i
n
j
iji
yz
với
ni
,,2,1
…
=
(GP3)
1,0,
=
iji
yz
với
ni
,,1
…
=
;

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:
21
5xxZMaximize +=

với
các
điều kiện ràng buộc:
2
2010
1
21
≤
≤+
x
xx