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

2 0 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 hoặc nhiều điểm. Vì vùng ràng buộc }1:),{( 22 2 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án ( 4.11). Định lý 4.4.5: (điều kiện cần) Giả sử *x là một cực tiểu của )(xf với điều kiện ràng buộc 0)( =xh . Khi đó tồn tại một vectơ mR∈λ có dạng sau: 0*)(*)( =∇−∇ xhxf Tλ (4.20) Nếu chúng ta chứng tỏ T là mặt phẳng tiếp xúc }0*)(:{ =∇= yxhyT T , khi đó ma trận *)(*)(*)( xHxFxL Tλ−=Δ là xác định dương trên T ; đó là 0*)( ≥yxLyT với mọi .Ty∈ Định lý 4.4.6: (điều kiện đủ) Giả sử điểm *x thỏa mãn điều kiện 0*)( =xh và một mR∈λ sao cho 0*)(*)( =∇−∇ xhxf Tλ và ma trận *)(*)(*)( xHxFxL Tλ−= là một đại lượng xác định dương trên }0*)(:{ =∇= yxhyT với 0, ≠∈ yTy . Ta có 0*)( >yxLyT . Khi đó *x là một cực tiểu của f với điều kiện ràng buộc 0)( =xh . Xét tiếp ví dụ 4.2.3, chúng ta có ma trận: ⎥⎦ ⎤⎢⎣ ⎡−⎥⎦ ⎤⎢⎣ ⎡= 0 2 2 0 0 2 2 0 *)( λxL Ngoài ra ta cũng 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 34 }0:),{( 2 * 21 * 121 =+= yxyxyyT Xét hai điểm )1,2/2,2/2( −−C , )1,2/2,2/2( −−D ta có 1−=λ : }:),{(, 22 22 2121 yyyyTL ==⎥⎦ ⎤⎢⎣ ⎡= và 08 22 22 ),( 21 2 1 21 ≥=⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛⎥⎦ ⎤⎢⎣ ⎡= y y y yyLyyT nó thỏa mãn hai cả hai điều kiện cần và đủ cho một cực tiểu. tương tự tại hai điểm )1,2/2,2/2(A , )1,2/2,2/2( −−B ta có 1=λ : }:),{(, 22 22 2121 yyyyTL −==⎥⎦ ⎤⎢⎣ ⎡ − −= và 08 21 ≤−= yLyyT Vậy ta có L xác định âm cho nên đây là một cực đại. 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 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: )(xfMinimize với các điều kiện ràng buộc: 0)( 0)( ≥ = xg xh (4.24) trong đó: qnmnn RRgRRhRRf →→→ :,:,: 1 và toàn bộ các hàm đều trong 2C . Định nghĩa 4.4.4: Cho *x là một điểm thỏa mãn điều kiện 0*)(,0*)( ≥= xgxh và 0*)( =xg j với Jj∈ . Khi đó *x được gọi là một điểm dừng của các ràng buộc nếu các véctơ *)(xhi∇ với mi ≤≤1 và *)(xg j∇ là độc lập tuyến tính. Định lý 4.4.7 (Kuhn – Tucker Conditions): Cho *x là một điểm cực tiểu của bài 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 mR∈λ và một vector qR∈μ sao cho: 0*)(*)(*)( =∇−∇−∇ xgxhxf TT μλ (4.25a) 0*)( =xgTμ (4.25b) 0≥μ (4.25c) 0*)(,0*)( ≥= xgxh (4.25d) 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 35 Định lý 4.4.8: (điều kiện cần) Giả sử các hàm 2,, Cghf ∈ và *x là một điểm dừng. Nếu *x là một cực tiểu của (4.24) thì tồn tại một vector mR∈λ và một vector 0, ≥∈ μμ qR từ (4.25a) – (4.25d), ta có *)(*)(*)( xHxFxL Tλ−= *)(xGT∇− μ là xác định dương tại *x . Định lý 4.4.9: (điều kiện đủ) Cho 2,, Cghf ∈ . Điều kiện để điểm *x là một cực tiểu là tồn tại mR∈λ và qR∈μ thoả các ràng buộc từ (4.25a – 4.25d) và ma trận Hessian *)(*)(*)( xHxFxL Tλ−= *)(xGT∇− μ xác định dương trong mặt phẳng ,0*)(:{' =∇= yxhyT 0*)( =∇ yxg j với mọi }'Jj∈ , trong đó }0,0*)(:{' >== jj xgjJ μ Ví dụ 4.4.4: Xét bài toán Hàm mục tiêu: 312131232221 2 1 5 12min xxxxxxxxxf −+++++= Các điều kiện ràng buộc: 0,0,0 162 0 3 352413 3212 3 2 2 2 11 211 ≥=≥=≥= −≥−−−= ≥+−−= =+= xgxgxg xxxg xxxg xxh Điều kiện cần bao gồm các ràng buộc: 0 1 0 0 0 1 0 0 0 1 2 1 1 1 2 2 0 1 1 2 1 3 2 2 14 54322 1 1 13 12 231 = ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ − ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ − ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ − ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ − − − − ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ − − − ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ − ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ −+ − +−+ μμμμμλ x x xx xx xxx 5,..,1,0,0)(,0)(,0)( 0)162( 0)( 352413 3212 3 2 2 2 11 =≥=== =+−−− =+−− jxxx xxx xxx jμμμμ μ μ Giải hệ phương trình trên ta được )5,2,1(*x 13,2/5 11 == λμ Bước kế tiếp chúng ta kiểm tra ma trận *)(xL ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ − − = ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ + ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ − − 5/201 071 119 000 020 002 2 5 5/201 021 114 là đại lượng xác định dương. Do đó )5,2,1(*x là một điểm cực tiể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 36 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 (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. 5.1. Phân hoạch bài toán 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: ƒ 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. ƒ 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. Hình 5.1: Sự phân hoạch bài toán Database indexing (6) Parser (1) Keyword (5) Index generator (3) Version 11 Version 12 Analyzer (4) Stemmer (2) Version 21 Version 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 Phan Thị Ngọc Mai Trang 37 Lý do để phân hoạch bài toán thành hai phần: ƒ 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. ƒ 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. 5.2. Bài toán tối ưu hóa các module mua 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: ƒ Các module là các module đơn. ƒ Mỗi module phải có ít nhất một version trên thị trường. ƒ Mỗi module phải mua duy nhất một version trong số các version đã có trên thị trường. ƒ Tổng chi phí để mua các module thoả điều kiện ∑∑ == ≤≤ m i i m i i cBc 1 (max) 1 (min) ' , (max)(min) , ii cc là chí phí của version rẻ và đắt tiền nhất của module 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 Maximize ∑∑ = = m i n j ijij i yr 1 1 (P11) với các ràng buộc sau: ∑∑ = = ≤ m i n j ijij Byc i 1 1 ' (P12) 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 38 1 1 =∑ = in j ijy (P13) 10oryij = (P14) trong đó: ƒ ijij cr , : hằng số độ tin cậy và chi phí của version cần mua. ƒ ijy : biến nguyên nhị phân (chỉ nhận giá trị 0 hoặc 1). ƒ m : số lượng các module mua. ƒ in : số lượng version của module i. ƒ (P11) : cực đại hoá tổng độ tin cậy của các module mua. ƒ (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. ƒ (P13) : đảm bảo mỗi module chỉ mua duy nhất một version. ƒ (P14) : đảm bảo các biến đều là biến nhị phân. Ví dụ 5.1: Dựa vào ví dụ 2.1, giả sử phần mềm có hai module mua. Trong đó, module một có hai version trên thị trường có chi phí 6,5 1211 == cc và độ tin cậy tương ứng là 9.0,7.0 1211 == rr , tương tự như vậy module hai có hai version trên thị trường với chi phí và độ tin cậy tương ứng như sau: 8,7 2221 == cc , 95.0,87 2221 == rr . Tổng chi phí 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 2222212112121111 yryyyryrZMaximize +++= với các ràng buộc sau: '2222222113121111 Bycycycyc ≤+++ 11211 =+ yy 12221 =+ yy , ijy là biến nguyên nhị phâ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 39 5.3. Bài toán tối ưu hóa các module phát triển trong công ty Đặc tính của module phát triển trong công ty: ƒ 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. ƒ Module đơn là những module mua, cũng có thể là các module được phát triển trong công ty. ƒ 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: Max (P21) S.T. ' 1 BBx n mi i −≤∑ += (P22) )0(ii xx ≥ (P23) trong đó: ƒ Mục tiêu (P21) là cực đại hoá độ tin cậy của hệ thống . ƒ (P22) đảm bảo tổng chi phí sử dụng không vượt quá ngân sách cho phép. ƒ (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. 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: ƒ Hai module (3) và (4) là được phát triển trong công ty. Do đó công thức độ tin cậy của chúng được tính như sau: Otherwise xxerrrr xxerrrr xxmm xxmm )0( 44 )()0( 4 )( 4 )( 4 4 )0( 33 )()0( 3 )( 3 )( 3 3 0 )( Otherwise0 )( )0( 443 )0( 333 ≥ ⎪⎩ ⎪⎨⎧ −−= ≥ ⎪⎩ ⎪⎨⎧ −−= −− −− α α 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 40 trong đó: 5.3,4.0,5.0,9.0 2,3.0,53.0,83.0 )0( 44 )0( 4 )( 4 )0( 33 )0( 3 )( 3 ==== ==== xrr xrr m m α α ƒ Còn module (5) và (6) là hai module tích hợp, trong đó module (5) được tích hợp từ hai module (2) và (4) Otherwise xxerrrr xxmm )0( 55 )()0( 5 )( 5 )( 5 5 0 )( )0( 555 ≥ ⎪⎩ ⎪⎨⎧ −−= −−α trong đó: 25.0,4,8.0,, 5)0(5)(55)0(542)(5 ===== αxqrqrrrr mm 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: )()0( 6 )( 6 )( 66 )0( 666)( xxmm errrrMaximize −−−−= α với các điều kiện ràng buộc: 6,5,4,3, ' )0( 6 3 =≥ −≤∑ = ixx BBx ii i i trong đó: ƒ 21,rr là các giá trị được tìm thấy trong bài toán tối ưu hóa các module mua. ƒ 6543 ,,, xxxx là các chi phí cần thiết để phát triển các module (3), (4), (5), (6) sao cho phần mềm có độ tin cậy lớn nhất ( 6r đạt giá trị lớn nhất). ƒ 'BB − là chi phí dùng cho các module phát triển trong công ty. 5.4. Sự kết hợp module mua và module phát triển trong công ty 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: ƒ 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. 3,3.0,8.0,, )0(666 )( 66 )0( 6351 )( 6 ===== xqrqrrrrr mm α 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 41 ƒ 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: 5.4.1. Bài toán A 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: a) Nếu phần mềm có một module: Độ 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: ƒ Nếu module đơn là một mudule mua: công thức tính độ tin cậy phần mềm 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: ∑∑ = = m i n j ijij i yrMaximize 1 1 Điều kiện ràng buộc: ∑∑ = = ≤ m i n j ijij i Byc 1 1 1,0,1,1 1 ===∑ = ij n j ij ymy i 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). ƒ 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: )()0((max)(max) )0()()( iii xxiii errrxfMaximize −−−−= α Các điều kiện ràng buộc: )0( ii i xx Bx ≥ ≤ 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 42 Trong đó Bi ,1= 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). b) Nếu phần mềm có nhiều hơn một module: 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: ƒ Chi phí đã cho ( B ) để phát triển phần mềm phải thỏa mãn điều kiện ∑ ∑ = += +≥ m i n mi ii xcB 1 1 )0((min) . Trong đó ∑ = m i ic 1 (min) là tổng chi phí nhỏ nhất của các module mua, ∑ += n mi ix 1 )0( là tổng chi phí nhỏ nhất để phát triển các module 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. ƒ Chi phí để mua các module ( 'B ) phải thỏa mãn điều kiện ∑∑ == ≤≤ m i i m i i cBc 1 (max) 1 (min) ' và ∑ += ≥− n mi ixBB 1 )0(' . Trong đó ∑ = m i ic 1 (max) là tổng chi phí lớn nhất để các module mua i có thể mua version có độ tin cậy lớn nhất. 9 Điều kiện ∑∑ == ≤≤ m i i m i i cBc 1 (max) 1 (min) ' đảm bảo các module mua đều có độ tin cậy và nguồn ngân sách cung cấp cho các module mua không bị dư thừa. 9 Điều kiện ∑ += ≥− n mi ixBB 1 )0(' đảm bảo với việc phân phối này các module 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): 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 43 Hàm mục tiêu ∑∑ = = m i n j ijij i yrMaximize 1 1 với các ràng buộc: ∑∑ = = ≤ m i n j ijij Byc i 1 1 ' 1 1 =∑ = in j ijy với i=1, . . . ,m và j=1, . . . ,ni 10oryij = 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. ' 1 BBx n mi i −≤∑ += )0(ii xx ≥ với i=m +1, . . . ,n 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 yêu cầu của nhà quản lý. Do ảnh hưởng của các vấn đề sau: ƒ Việc phân phối chi phí giữa các module mua và module phát triển trong công ty. ƒ Chi phí cung cấp cho phần mềm quá nhỏ, hoặc ƒ Các thông số đã cho của module phần mềm. 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: Bước 1: (Khởi tạo) nhập vào các thông số của module phần mềm: ƒ Số module phần mềm, số module mua, số module đơn phát triển trong công ty. ƒ Số version của mỗi module mua, chi phí và độ tin cậy của từng version. 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 44 ƒ 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. ƒ 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. Bước 2: Nhập chi phí để phát triển phần mềm ( B ). Nếu ∑ ∑ = += +≥ m i n mi ii xcB 1 1 )0((min) thì yêu cầu nhập lại B , ngược lại chuyển sang bước 3. Bước 3: Nhập tổng chi phí để mua các module mua 'B . Nếu ∑∑ == ≤≤ m i i m i i cBc 1 (max) 1 (min) ' và ∑ += ≥− n mi ixBB 1 )0(' thì yêu cầu nhập lại 'B , ngược lại chuyển sang bước 4. 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 và module tích hợp và chuyển sang bước 6. 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 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. Bước 7: Nh