Download miễn phí Luận văn Một giải pháp toán học cho việc phân phối tài nguyên trong độ tin cậy phần mềm
MỤC LỤC
LỜI CAM ĐOAN .i
LỜI CẢM ƠN .ii
TÓM TẮT LUẬN VĂN .iii
DANH MỤC HÌNH .vi
DANH MỤC BẢNG .vii
Chương 1. GIỚI THIỆU.1
1.1. Giới thiệu .1
1.2. Sơlược vềviệc phân phối độtin cậy phần mềm .2
1.3. Kết cấu của luận văn .4
Chương 2. Các Mô Hình Phân Phối Chi Phí Cho ĐộTin Cậy Phần Mềm .6
2.1. Giới thiệu .6
2.2. Phân loại các module trong phần mềm.6
2.3. Mô hình quyết định trước .7
2.3.1. Độtin cậy của một module đơn phát triển trong công ty.7
2.3.2. Độtin cậy của một module mua .8
2.3.3. Độtin cậy của một module tích hợp .9
2.4. Mô hình tổng quát .14
Chương 3. Phương Pháp Giải Bài Toán Quy Hoạch Nguyên.15
3.1. Giới thiệu .15
3.2. Sựcần thiết của bài toán quy hoạch nguyên .15
3.3. Phương pháp giải quyết bài toán quy hoạch nguyên .16
3.4. Phương pháp giải quyết bài toán quy hoạch nguyên nhịphân .19
Chương 4. Phương Pháp Giải Bài Toán Quy Hoạch Phi Tuyến .23
4.1. Giới thiệu .23
4.2. Những điều kiện tối ưu .25
4.3. Tính lồi của hàm nhiều biến .26
4.3.1. Tập lồi .26
4.3.2. Định nghĩa hàm lồi .26
4.3.3. Đặc trưng của hàm lồi.26
4.4. Các phương pháp giải bài toán quy hoạch phi tuyến.27
4.4.1. Giải bài toán tối ưu không có điều kiện ràng buộc .27
4.4.2. Giải bài toán tối ưu với điều kiện ràng buộc các biến lớn hơn 0 .28
4.4.3. Giải bài toán tối ưu với điều kiện ràng buộc là các phương trình tuyến tính.30
4.4.4. Giải bài toán tối ưu với điều kiện ràng buộc là các phương trình phi tuyến.34
Chương 5. Giải Quyết Bài Toán .36
5.1. Phân hoạch bài toán .36
5.2. Bài toán tối ưu hóa các module mua .37
5.3. Bài toán tối ưu hóa các module phát triển trong công ty .39
Một giải pháp toán học cho việc phân phối chi phí trong độtin cậy phần mềm
Phan ThịNgọc Mai Trang v
5.4. Sựkết hợp module mua và module phát triển trong công ty .40
5.4.1. Bài toán A .41
5.4.2. Bài toán B .46
Chương 6. Một sốkết quả, kết luận.51
6.1. Sơlược vềchương trình .51
6.2. Một sốkết quảchạy chương trình .51
6.2.1. Bài toán trong ví dụ3.4 .51
6.2.2. Bài toán trong ví dụ4.1.1 .51
6.2.3. Bài toán trong ví dụ4.3.1 .52
6.2.4. Bài toán trong ví dụ4.3.4 .52
6.2.5. Bài toán cho một phần mềm gồm có 6 module.54
6.2.6. Bài toán cho một phần mềm gồm có 11 module.56
6.2.7. Bài toán cho một phần mềm gồm có 22 module.61
6.2.8. Bài toán cho một phần mềm gồm có 37 module.67
6.3. Kết luận.74
Tài Liệu Tham Khảo .76
Phụlục 1. Bảng đối chiếu Thuật ngữAnh - Việt.77
Phụlục 2. Bảng tóm tắt các mô hình đánh giá độtin cậy phần mềm .78
Phụlục 3. Sơlược vềMATLAB.80
Tham khảo ChỉMục .84
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
20
0
18
)2,1( 1
x
F là đại lượng xác định
dương vì 018)2,1( 2221 >+=− vvvFvT . Như vậy tại điểm (1, -2) là một điểm
cực tiểu.
)2,1( −−=x ta được ⎥⎦
⎤⎢⎣
⎡−=⎥⎦
⎤⎢⎣
⎡−=−−
2
0
0
18
2
0
0
18
)2,1( 1
x
F và khi đó
2
118)2,1( vvFv
T −=−− 22v+ có thể bằng 0 khi 0≠v . Do đó điểm (-1,-2)
không thỏa mãn điều kiện.
Vậy điểm (1,-2) là một cực tiểu cần tìm.
4.4.2. Giải bài toán tối ưu với điều kiện ràng buộc các biến lớn hơn 0
Xét bài toán có dạng sau:
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 29
}0
({min ≥xxf (4.9) Giả thiết rằng f có một cực tiểu *x , trong đó 0* ≥x . Khi đó sẽ tồn tại một lân
cận *)(xNε của *x , do đó với bất kỳ *)(xNx ε∈ có 0≥x , thì *).()( xfxf ≥ Ta có thể
viết tvxx += * , trong đó v là một vector và 0>t . Giả sử f hai lần đạo hàm qua
*)(xNε . Từ (4.7) ta có:
vtvxFvtvxf T )*(
2
*)(0 α++∇≤
Các điều kiện cần để f có một cực tiểu tại *x :
0*)( =∂
∂
jx
xf nếu 0* >jx
0*)( ≥∂
∂
jx
xf nếu 0* =jx
Chúng được tổng kết trong mệnh đề sau đây:
Mệnh đề 4.4.1: Những điều kiện cần để hàm f có một cực tiểu tại điểm *x
trong bài toán (4.9) bao gồm:
0*
0**)(
0*)(
≥
=∇
≥∇
x
xxf
xf
(4.10)
Ví dụ 4.4.2: Xét bài toán
Hàm mục tiêu:
13121
2
3
2
2
2
1 2223)( xxxxxxxxxfMinimize −−−++=
với các điều kiện ràng buộc:
3,2,1,0 =≥ ixi
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
tiểu:
(1) 22260 321
1
−−−=∂
∂≤ xxx
x
f
(2) )2226(0 3211
1
1 −−−=∂
∂= xxxx
x
fx
(3) 12
2
220 xx
x
f −=∂
∂≤
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 30
(4) )22(0 122
2
2 xxxx
fx −=∂
∂=
(5) 13
3
220 xx
x
f −=∂
∂≤
(6) )22(0 133
3
3 xxxx
fx −=∂
∂≤
(7) 0,0,0 321 ≥≥≥ xxx
Ta tìm được 1 điểm dừng 1321 === xxx . Ma trận Hessian ở )1,1,1(* =x :
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−
−
−−
=
202
022
226
)1,1,1(F là một đại lượng xác định dương. Do đó ta có một cực
tiểu tại điểm *x .
4.4.3. Giải bài toán tối ưu với điều kiện ràng buộc là các phương trình tuyến tính
Cho 1: RRf n → và xét bài toán sau:
Hàm mục tiêu:
)(xfMinimize
với các điều kiện ràng buộc:
0)( =xh (4.11)
Trong đó ))(),..,(()( 1 xhxhxh m= , mỗi 1: RRh ni → , và nm < . Để bài toán (4.11) có
một cực tiểu tại *x . Khi đó phải tồn tại một 0>ε sao cho *)()( xfxf ≥ với mỗi
*)(xNx ε∈ và 0)( =xh . Giả sử 2Cf ∈ tại mọi *)(xNε , và giả sử rằng mỗi ii xxh ∂∂ /)( đạo
hàm liên tục trong lân cận của *x . Tiếp theo, xây dựng một ma trận Jacobi có m hàng:
⎥⎥
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢⎢
⎢
⎣
⎡
∂
∂
∂
∂
∂
∂
∂
∂
=∂
∂
n
mm
n
x
xh
x
xh
x
xh
x
xh
x
xh
*)(*)(
*)(*)(
*)(
1
1
1
1
"
#%#
"
(4.12)
Điều này tương ứng với việc cho rằng *x là điểm dừng.
Định nghĩa 4.4.3: Cho một điểm *x thỏa mãn các điều kiện ràng buộc
0*)( =xh được gọi là một điểm dừng, nếu các vector *)(*),..,(1 xhxh m∇∇ là độc lập
tuyến tính.
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 31
Định lý 4.4.3: Tại điểm *x của mặt }0)
{ == xhxS tiếp xúc với }0)
{ =∇= yxhyT . Để đơn giản quá cho các đối số sau đây chúng ta giả sử rằng đầu tiên m cột của
công thức (4.12) là độc lập tuyến tính. Theo định lý hàm ẩn trong phần 4.1.3 m hàm,
mỗi hàm có n biến đạo hàm liên tục, trong đó nm < , với ma trận Jacobi có rank là m,
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ụ:
),..,( 1 nmii xxx += φ với mi ,..,1= . Hơn nữa, các hàm iφ là duy nhất và khả thi trong lân cận
của *x . Cho ),..,(' 1 mxxx = và ),..,(" 1 nm xxx += , ta có ))"(),..,"((' 1 xxx mφφ= được ký hiệu
)"(xφ . Công thức (4.11) được viết lại như sau:
)"(min)"),"((min)",'({min xxxfxxf Φ== φ (4.13)
trong đó Txxx )"),"(()"( φφ = . Vì thế bài toán ( 4.13) phải có một cực tiểu
),..,("* ** 1 nm xxx += . Được tạo ra bởi định lý 4.2.1 là 0)"( =Φ∇ x .
Nhưng
⎥⎥
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢⎢
⎢
⎣
⎡
∂
∂
∂
∂
⎥⎦
⎤⎢⎣
⎡
∂
∂
∂
∂+∂
∂=∂
∂
∂
∂+∂
∂
∂
∂=∂
Φ∂ ∑∑
=+=
m
j
mjj
i
m
i ij
i
n
mi ij
x
x
x
f
x
f
x
f
xx
f
x
x
x
f
x φ
φ
φ #,..,
111
Do đó ]/,..,/[)"(],/,..,/[)'( 11 nmm xfxfxfxfxfxf ∂∂∂∂=∇∂∂∂∂=∇ + và "/ x∂∂φ là một
ma trận có kích thước )1(* −nm bao gồm những cột có dạng ,..,/[ 1 jx∂∂φ Tjm x ]/∂∂φ . Từ
đó ta được:
"
)"()"()"(0
x
xfxfx ∂
∂∇+∇=Φ∇= φ (4.14)
Ngoài ra )"),"(()(0 xxhxh φ== . Vì thế:
"'"
0
x
h
x
h
x
h
∂
∂
∂
∂+∂
∂= (4.15)
trong đó '/ xh ∂∂ và "/ xh ∂∂ là những matrận con đầu tiên có m hàng và n-1 cột của
công thức (4.12). Từ công thức (4.16) ta có:
"'"
1
x
h
x
h
x ∂
∂⎟⎠
⎞⎜⎝
⎛
∂
∂=∂
∂ −φ
Vì thế được tạo ra từ (4.14) điều đó:
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 32
0
"
)"( =∂
∂−∇
x
hxf TT λ
trong đó:
1
'
)'(
−
⎟⎠
⎞⎜⎝
⎛
∂
∂∇=
x
hxfTλ
tại "*x . Sắp xếp lại:
0
'
)'( =∂
∂−∇
x
hxf Tλ (4.17)
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*)(
0*)(*)(
=
=∇−∇
xh
xhxf Tλ
cho một cực tiểu tại *x , trong đó *)(xh∇ là một matrận cấp có m hàng và n cột.
Cho )()(),( xhxfxL Tλλ −= , những điều kiện cần này có thể được phát biểu bằng một
định lý như sau:
Đị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
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
Jacobi có đầy đủ m hàng, khi đó tồn tại một mR∈*λ sao cho:
0*)(*)*,(
0*)(**)(*)*,(
=−=∂
∂
=∇−∇=∂
∂
xhxL
xhxf
x
xL
λ
λ
λλ
(4.18)
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.
Ví dụ 4.4.3: Tìm cực trị của hàm số 2121 2),( xxxxf = với điều kiện ràng buộc:
.122
2
1 =+ xx
Lời giải:
Ta có: )1(2),,( 22212121 −+−= xxxxxxL λλ .
Theo công thức (4,17) ta 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
Phan Thị Ngọc Mai Trang 33
01
022
022
2
2
2
1
21
2
12
1
=−+=∂
∂
=−=∂
∂
=−=∂
∂
xxL
xx
x
L
xx
x
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 ,
)1,2/2,2/2( −−B , )1,2/2,2/2(−C , )1,2/2,2/2( −D .
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 hay nhiều điểm. Vì vùng ràng buộc
}1
,{( 222
111 =+= xxxxS là bị đóng và chặn, theo định lý Weierstrass ngụ ý f có cả một
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
xuất hiện tại 2 điểm )1,2/2,2/2( −−C , )1,2/2,2/2( −−D . Tương tự , cực đại cũng
xuất hiện tại hai điểm )1,2/2,2/2(A , )1,2/2,2/2( −−B 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