Luận văn Điều hành dự án bằng phương pháp sơ đồ mạng lưới (phương pháp pert-Cpm)

1 ĐẠI HỌC QUỐC GIA TP.HCM TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN PHAN NGUYỄN VIỄN DI ĐIỀU HÀNH DỰ ÁN BẰNG PHƯƠNG PHÁP SƠ ĐỒ MẠNG LƯỚI (PHƯƠNG PHÁP PERT-CPM). LUẬN VĂN THẠC SĨ TOÁN HỌC Tp.HCM-2009 2 ĐẠI HỌC QUỐC GIA TP.HCM TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN Họ tên học viên cao học: PHAN NGUYỄN VIỄN DI LUẬN VĂN THẠC SĨ Tên đề tài: ĐIỀU HÀNH DỰ ÁN BẰNG PHƯƠNG PHÁP SƠ ĐỒ MẠNG LƯỚI (PHƯƠNG PHÁP PERT-CPM). Chuyên ngành: LÍ THUYẾT TỐI ƯU VÀ HỆ THỐNG. Mã số: 60 46 20 Cán bộ hướng dẫn: PGS TS.TRẦN THỊ HUỆ NƯƠNG. Tp.HCM-2009 3 LỜI MỞ ĐẦU Lí thuyết toán học về tối ưu được hình thành và phát triển mạnh như một lĩnh vực khoa học quan trọng từ khoảng giữa thế kỉ thứ hai mươi. Tùy theo dạng các bài toán được nghiên cứu, đặc điểm của mô hình toán học và công cụ xét chúng hoặc phạm vi áp dụng…, nhiều lĩnh vực khá gần nhau và đan xen với nhau của lí thuyết được hình thành với các tên gọi khác nhau như : - Tối ưu hóa (Optimization). - Qui hoạch toán học ( Mathematical Programming). - Vận trù học (Operations Research). - Điều khiển tối ưu (Optimal Control). - Lí thuyết các bài toán cực trị (Theory of Extremal Problems). - Phép tính biến phân (Variational Calculus). - …. GS.Hoàng Tùy là người chọn thuật ngữ tiếng Việt Vận trù (Operations Research) từ đầu thập niên 60 của thế kỉ hai mươi. Theo đó, Vận trù có nghĩa là vận dụng khoa học mà nền tảng là Toán học để trù tính mọi việc. Phát triển và ứng dụng thật sự Vận trù đầu tiên là ở nước Anh trong việc dùng ra-đa phòng không chống tàu ngầm (thời kì chiến tranh thế giới thứ hai). Sau chiến tranh, Vận trù càng phát triển rộng rãi trong các lĩnh vực rất đa dạng như kinh doanh, quản lí hành chính, xây dựng, quân sự, chính trị, giáo dục đào tạo,… Vận trù đôi khi được dùng gần như đồng nghĩa với khoa học quản trị (Management Science) và chọn quyết định (Decision Making). Điểm nổi bật của bài toán Vận trù là thường nhằm tìm nghiệm tối ưu, tức là chọn quyết định tốt nhất theo một mục tiêu nào đó. Do đó, Vận trù rất gần với tối ưu hóa, nhưng lại có liên quan đến rất nhiều lĩnh vực khoa học khác như lí thuyết kinh tế, xác suất thống kê, công nghệ thông tin… Dù vậy, vẫn khẳng định đây là bộ phận của Toán ứng dụng vì phương pháp và ngôn ngữ Toán học là chủ đạo. Người viết đã chọn đề tài làm luận văn là Vận trù trong điều hành dự án bằng phương pháp PERT – CPM. Phương pháp PERT-CPM gồm có ba pha (phase): lập dự án bằng sơ đồ mạng lưới; điều hành dự án thông qua các chỉ tiêu về thời gian, tài nguyên, chi phí; kiểm tra điều chỉnh dự án so với điều kiện thực tế. Luận văn gồm ba chương, trong đó chương cuối là giao diện chương trình điều hành dự án bằng phần mềm Microsoft Project 2007 với đầy đủ các tính năng cần thiết, có tính trực quan cao, dễ sử dụng. 4 Người viết xin gửi lời biết ơn chân thành đến quí Thầy Cô ở khoa Toán – Tin học, Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia thành phố Hồ Chí Minh đã tận tình giảng dạy và hướng dẫn tôi trong quá trình ba năm học tập ở bậc cao học. Xin gửi lời biết ơn sâu sắc đến Phó Giáo sư Tiến sĩ Trần Thị Huệ Nương đã tận tình hướng dẫn tôi trong suốt quá trình làm luận văn. Nhờ đó, tôi đã bổ sung thêm rất nhiều kiến thức hữu ích cho mình. Xin cám ơn các bạn đồng nghiệp, các bạn học khóa 16 đã cùng học tập và làm việc trong suốt ba năm qua. Cuối cùng, người viết rất mong nhận được những góp ý sửa đổi cho các thiếu sót khó tránh khỏi của luận văn này. 5 CHƯƠNG 1: LÍ THUYẾT ĐỒ THỊ VÀ LÍ THUYẾT XÁC SUẤT CƠ BẢN. 1.1. Lí thuyết đồ thị: Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó. Người ta phân loại đồ thị tuỳ theo đặc tính và số các cạnh nối các cặp đỉnh của đồ thị. Nhiều bài toán thuộc những lĩnh vực rất khác nhau có thể giải được bằng mô hình đồ thị. Chẳng hạn người ta có thể dùng đồ thị để biểu diễn sự cạnh tranh các loài trong một môi trường tự nhiên, dùng đồ thị để biểu diễn ai có ảnh hưởng lên ai trong một tổ chức nào đó, và cũng có thể dùng đồ thị biểu diễn các kết cục của cuộc thi đấu thể thao.Hoặc chúng ta cũng sẽ chỉ ra có thể dùng đồ thị để giải các bài toán như bài toán tính số các tổ hợp khác nhau giữa các chuyến bay giữa hai thành phố trong một mạng hàng không, hay để giải bài toán đi tham quan tất cả các phố của một thành phố sao cho mỗi phố đi qua đúng một lần, hoặc bài toán tìm số các màu cần thiết để tô các vùng khác nhau của một bản đồ. 1.1.1. Các loại đồ thị : c a b d e a b a b c f g i h j d c f e Đơn đồ thị Đa đồ thị Giả đồ thị H.1.1.1.a Định nghĩa 1.1.1.1 : Một đơn đồ thị G = (V, E) gồm một tập không rỗng V mà các phần tử của nó gọi là các đỉnh và một tập E mà các phần tử của nó gọi là các cạnh (cung), đó là các cặp không thứ tự của các đỉnh phân biệt . Đôi khi có nhiều đường điện thoại giữa các máy tính trong mạng. Đó là khi có sự truyền thông với cường độ cao giữa các máy tính. Mạng với nhiều đường thoại. Đơn đồ thị không thể mô hình các mạng như thế này được . Thay vào đó người ta dùng đa đồ thị. Đó là đồ thị gồm các đỉnh và các cạnh vô hướng, nhưng có thể có nhiều cạnh nối mỗi cặp đỉnh. Đơn đồ thị là một trường hợp riêng của đa đồ thị. 6 Ta không thể dùng một cặp đỉnh để xác định một cạnh trong đa đồ thị. Định nghĩa đa đồ thị vì vậy phức tạp hơn một chút. Định nghĩa 1.1.1.2: Một đa đồ thị G = (V, E) gồm một tập các đỉnh V, một tập các cạnh(cung) E và một hàm f từ E tới {{u, v}│u, v € V, u ≠ v }. Các cạnh e1 và e2 được gọi là song song hay cạnh bội nếu f(e1) = f(e2). Ta không thể dùng đa đồ thị để mô hình các mạng như thế được vì đa đồ thị không chứa các khuyên, đó là các cạnh nối một đỉnh với chính nó. Khi đó ta phải dùng một loại đồ thị tổng quát hơn, gọi là giả đồ thị . Định nghĩa 1.1.1.3 : Một giả đồ thị G = (V, E) gồm một tập các đỉnh V, một tập các cạnh(cung) E và một hàm f từ E tới {{u, v}│u, v € V }. Một cạnh là một khuyên nếu f(e) = {u } với một đỉnh u nào đó. Tóm lại : Giả đồ thị là loại đồ thị vô hướng tổng quát nhất vì nó các khuyên và các cạnh bội. Đa đồ thị là loại đồ thị vô hướng có thể chứa cạnh bội nhưng không thể có các khuyên, còn đồ thị đơn là loại đồ thị vô hướng không chứa cạnh bội hoặc các khuyên. Định nghĩa 1.1.1.4 : Một đồ thị có hướng G = (V, E) gồm tập các đỉnh V và tập các cạnh (cung có hướng) E là các cặp có thứ tự của các phần tử thuộc V. Định nghĩa 1.1.1.5 : Một đa đồ thị có hướng G = (V, E) gồm tập các đỉnh V và tập các cạnh (cung có hướng) E và một hàm f từ E tới {{u, v}│u, v € V }. Các cạnh e1 và e2 được gọi là song song hay cạnh bội nếu f(e1) = f(e2). a b h a b c g d f d c e Đồ thị có hướng Đa đồ thị có hướng H.1.1.1b 7 Bảng thuật ngữ đồ thị Loại Cạnh Có cạnh bội không ? Có khuyên không ? Đơn đồ thị Đa đồ thị Giả đồ thị Đồ thị có hướng Đa đồ thị có hướng Vô hướng Vô hướng Vô hướng Có hướng Có hướng Không Có Có Không Có Không Không Có Có Có 1.1.2. Thuật ngữ cơ sở : Định nghĩa 1.1.2.1 : Hai đỉnh u và v trong một đồ thị vô hướng G được gọi là liền kề (hay láng giềng ) nếu {u , v} là một cạnh của G. Nếu e = {u, v} thì e gọi là cạnh liên thuộc với các đỉnh u và v. Cạnh e cũng được gọi là cạnh nối các đỉnh u và v. Các đỉnh u và v gọi là các điểm đầu mút của cạnh {u, v}. Định nghĩa 1.1.2.2 : Bậc của một đỉnh trong đồ thị vô hướng là số các cạnh liên thuộc với nó, riêng khuyên tại một đỉnh được tính hai lần cho bậc của nó. Người ta ký hiệu bậc của đỉnh v là deg(v). Ví dụ 1 : Đồ thị G : b c d a f e ● g Ta có : deg(a) = 4, deg(b) = 3, deg(c) = 3, deg(d) = 1, deg(e) = 2, deg(f) = 3, deg(g) = 0. Đỉnh bậc 0 được gọi là đỉnh cô lập. Từ đó suy ra đỉnh cô lập không nối với bất kỳ đỉnh nào. Đỉnh g trên đồ thị G trong Ví dụ 1 là cô lập. Một đỉnh gọi là treo (móc) nếu và chỉ nếu có bậc bằng 1. Do vậy đỉnh treo liên kề (nối) với đúng một đỉnh khác, đỉnh d trên đồ thị G trong Ví dụ 1 là một đỉnh treo. 8 Định lý 1.1.2.1 : (Định lý bắt tay) Cho G = (V, E) là một đồ thị vô hướng có e cạnh. Khi đó: 2 deg( ) v V e v ∈ = Σ (Định lý này đúng cả khi đồ thị có cạnh bội hoặc các khuyên ) Định lý 1.1.2.2 : Một đồ thị vô hướng có một số chẵn các đỉnh bậc lẻ. Định nghĩa 1.1.2.3 : Khi (u, v) là cạnh của đồ thị có hướng G, thì u được gọi là nối tới v, và v được gọi là được nối từ u. Đỉnh u gọi là đỉnh đầu, đỉnh v gọi là đỉnh cuối của cạnh (u, v). Đỉnh đầu và đỉnh cuối của khuyên là trùng nhau. Định nghĩa 1.1.2.4 : Trong đồ thị có hướng bậc – vào của đỉnh v ký hiệu là deg - (v) là số các cạnh có đỉnh cuối là v. Bậc – ra của đỉnh v ký hiệu là deg +(v) là số các cạnh có đỉnh đầu là v. (chú ý: một khuyên tại một đỉnh sẽ góp thêm 1 đơn vị vào bậc – vào và 1 đơn vị vào bậc – ra của đỉnh này). Ví dụ 2 : Đồ thị H dưới đây có : deg – (a) = 2, deg – (b) = 2, deg – (c) = 3, deg – (d) = 2, deg – (e) = 3, deg – (f) = 0. deg+ (a) = 4, deg+ (b) = 1, deg+ (c) = 2, deg + (d) = 2, deg+ (e) = 3, deg+(f) = 0. a b c e d ● f Định lý 1.1.2.3 : Gọi G = (V, E) là một đồ thị có hướng. Khi đó deg ( ) deg ( ) v V v V v v E− + ∈ ∈ Σ = Σ = Một số tính chất của đồ thị có hướng không phụ thuộc vào hướng của các cạnh của nó. Do đó, sẽ có lợi hơn khi ta lờ đi các hướng này. Đồ thị vô hướng nhận được bằng cách này được gọi là đồ thị vô hướng nền. Đồ thị có hướng và đồ thị vô hướng nền của nó có cùng số cạnh. Định nghĩa 1.1.2.6 : Đồ thị con của đồ thị G = (V, E) là đồ thị H = (W, F) trong đó W⊂ V,F⊂ E. Định nghĩa 1.1.2.7 : Hợp của hai đồ thị đơn G1 = (V1, E1) và G2 = (V2, E2 ) là một đồ thị đơn có tập các đỉnh là V1∪ V2 là tập các cạnh là E1∪ E2 . Ta ký hiệu hợp của các đồ thị G1 và G2 là G1∪ G2. 9 1.1.3. Tính liên thông: Định nghĩa 1.1.3.1: Đường đi độ dài n từ u tới v, với n là một số nguyên dương, trong một đồ thị vô hướng là một dãy các cạnh e1, e2, ..., en của đồ thị sao cho f(e1) = {x0, x1 }, f(e2) = {x1, x2 },…, f(en) = {xn-1 , xn }, với x0 = u và xn =v. Khi đồ thị là đơn ta ký hiệu đường đi này bằng dãy các đỉnh x0 , x1 , …., xn-1. Đường đi hay chu trình gọi là đơn nếu nó không chứa cùng một cạnh quá một lần. Định nghĩa 1.1.3.2: Đường đi độ dài n , với n nguyên dương , từ u với v trong đa đồ thị có hướng là dãy các cạnh e1, e2,…, en của đồ thị sao cho (e1) = {x0 , x1 }, f(e2) = {x1 , x2 },…, f(en) = {xn-p , xn },với x0 = u và xn = v. Khi không có cạnh bội trong đồ thị ta ký hiệu đường đi này bằng dãy các đỉnh x0 , x1 , …., xn. Đường đi bắt đầu và kết thúc tại cùng một đỉnh được gọi là một chu trình. Đường đi hay chu trình gọi là đơn nếu nó không chứa cùng một cạnh quá một lần. Định nghĩa 1.1.3.3: Một đồ thị vô hướng được gọi là liên thông nếu có đường đi giữa mọi cặp đỉnh phân biệt của đồ thị. Ví dụ 3: a b a b Đồ thị G e Đồ thị H liên thông c c không liên thông. f d d f g h Định lý 1.1.3.1: Giữa mọi cặp đỉnh phân biệt của một đồ thị vô hướng liên thông luôn có đường đi đơn. Đôi khi, việc xoá đi một đỉnh và tất cả các cạnh liên thuộc với nó sẽ tạo ra một đồ thị con mới có nhiều thành phần liên thông hơn đồ thị xuất phát. Các đỉnh như thế gọi là các đỉnh cắt hay các điểm khớp. Việc xoá đỉnh cắt khỏi một đồ thị liên thông sẽ tạo ra một đồ thị con không liên thông. Hoàn toàn tương tự, một cạnh mà khi ta bỏ nó đi sẽ tạo ra một đồ thị có nhiều thành phần liên thông hơn so với đồ thị xuất phát được gọi là một cạnh cắt hay một cầu. Ví dụ 4: a d f g Đồ thị G b c e h 10 Đỉnh cắt của đồ thị G là : đỉnh b, c ,e . Khi xóa một trong 3 đỉnh này (và các cạnh nối với nó ) sẽ làm mất tính liên thông của đồ thị G . Các cạnh cầu là : {a,b}, {c,e} vì khi xóa một trong 2 cầu này sẽ làm đồ thị G mất tính liên thông. Định nghĩa 1.1.3.4 : Đồ thị có hướng gọi là liên thông mạnh nếu có đường đi từ a tới b và từ b tới a với mọi đỉnh của a và b của đồ thị. Trong đồ thị có hướng liên thông mạnh luôn tồn tại dãy các cạnh có hướng từ một đỉnh bất kì đến một đỉnh bất kỳ khác của đồ thị. Đồ thị có hướng có thể không là liên thông mạnh nhưng vẫn còn liên thông theo một nghĩa nào đó. Để xác định chính xác điều này, ta có định nghĩa 5 sau: Định nghĩa 1.1.3.5 : Đồ thị có hướng gọi là liên thông yếu nếu có đường đi giữa hai đỉnh bất kỳ của đồ thị vô hướng nền. Do vậy đồ thị có hướng là liên thông yếu nếu và chỉ nếu luôn tồn tại đường đi giữa hai đỉnh khi ta không quan tâm tới hướng của các cạnh. Rõ ràng mọi đồ thị có hướng liên thông mạnh cũng là đồ thị liên thông yếu. Ví dụ 4 : a b a b c c e d e d Đồ thị có hướng G Đồ thị có hướng H liên thông mạnh không liên thông mạnh (nhưng liên thông yếu ) 1.2. Lí thuyết xác suất : 1.2.1.Các khái niệm cơ bản: 1.2.1.1.Đại số các biến cố ngẫu nhiên: Trong các hiện tượng xảy ra xung quanh, ta có thể phân thành hai loại : + Hiện tượng tất yếu: có tính chất đặc trưng là nếu xảy ra trong cùng điều kiện thì chúng cho các kết quả giống nhau. + Hiện tượng ngẫu nhiên: có tính chất đặc trưng là dù có xảy ra trong cùng điều kiện thì chúng vẫn có thể cho kết quả khác nhau. Ví dụ : Gieo hạt xúc xắc, số nút xuất hiện ( từ 1 đến 6) là ngẫu nhiên (còn gọi là biến cố ngẫu nhiên). Các biến cố (ngẫu nhiên) luôn liên quan đến 1 phép thử nào đó. Mỗi phép thử lại liên quan đến một tập hợp các kết quả có thể xảy ra. Khi xét một biến cố nào đó, ta cần quan tâm: với kết quả nào của phép thử thì biến cố xảy ra (hoặc không xảy ra). 11 Ta trang bị một cấu trúc đại số cho các biến cố ngẫu nhiên như sau: Cho A,B,C là các biến cố ngẫu nhiên liên quan đến một phép thử F.Ta có các định nghĩa : i) A = B (A, B đồng nhất) : A và B cùng xảy ra (hoặc cùng không xảy ra), với mỗi kết quả của phép thử F. ii) Biến cố đối của A, kí hiệu là Ac, được đặc trưng bởi tính chất sau: trong phép thử F, A và Ac không cùng xảy ra. iii) A∩B (hay AB): biến cố chỉ sự đồng thời xuất hiện của A và B. iv) ∅ : là biến cố chỉ sự không thể xuất hiện trong F. v) AB = ∅ : A và B gọi là xung khắc. vi) A∪B : là biến cố chỉ sự xuất hiện ít nhất của 1 trong 2 biến cố A, B.(Khi A.B =∅ thì ta viết A+B thay A∪B.) vii) Ω : là biến cố chỉ sự chắc chắn xuất hiện trong F. viii) A⊂B: nếu sự xuất hiện của A luôn kéo theo sự xuất hiện của B. ix) A \ B = ABc. x) Họ biến cố { B1,B2…,Bn} là đầy đủ, nếu chúng xung khắc đôi một và 1 n i i B = = ΩΣ . Các tính chất : C ) suy ra B=A. A.A=A ii)AB=BA (AB)C=A(BC) iii)A . (A ) ( ) ) A \ ) ) . )A ( ) ( )(A ) )A(B ) )( ) (A ) ) C C C C C C C C C i A B B B A B C A B C iv A A A A B vi A B B A vii A B B A viii BC A B C ix C AB AC x AB A B B A B xi A B = ∪ = ∪ ∪ ∪ = ∪ ∪ + = Ω = Ω ⊂ = ⇔  ⊂ ⊂ ⇔ ⊂ ∪ = ∪ ∪ ∪ = ∪ = ∪ ∪ = ∪ = CA BA+ 12 1.2.1.2.Định nghĩa đại số và σ - đại số: Tập A gọi là đại số Boole (hay trường), nếu thỏa điều kiện sau : i) A,B ⊂ A tồn tại AB ⊂ A gọi là tích của A và B, tồn tại A ∪B ⊂A gọi là hợp của Avà B. ii) Với mỗi A ⊂A tồn tại Ac ⊂A, gọi là đối của A. iii) ,Ω ∅ ⊂A. iv) Với mọi A,B,C ⊂A, các phép toán sau thỏa : iv.1) AA=A, AB=BA, (AB)C=A(BC). iv.2) A∪A=A, A∪B=B ∪A, (A ∪B)∪C=A∪ (B∪C). iv.3) A(B∪C)=AB∪AC, A∪BC=(A∪B)(A∪C). iv.4) A.AC = ∅ , A ∪AC=Ω iv.5) AΩ =A, A∪ Ω = Ω iv.6) A∅=∅ , A∪ ∅ = A . Đại số Boole được gọi là σ -đại số nếu nó đóng kín với phép lấy hợp đếm được hay với phép giao đếm được. 1.2.1.3.Liên hệ giữa đại số các biến cố và đại số các tập hợp : Định lí 1.2.1.3: (định lí Stone) Mỗi đại số các biến cố có một đại số các tập hợp đẳng cấu với nó. Ví dụ 1: Cho phép thử F : gieo hai xúc xắc đồng chất .Khi đó Ω ={(ei,ej), i= 1,6 }, với (ei,ej) là biến cố :” xúc xắc 1 xuất hiện nút i, xúc xắc 2 xuất hiện nút j ”. Ta xét biến cố A:” tổng số nút của 2 xúc xắc xuất hiện là 7 “, thì A có dạng : A = {(e1,e6), (e2,e5), (e3,e4), (e4,e3), (e5,e2), (e6,e1)} hay A= (e1,e6)+(e2,e5)+(e3,e4)+(e4,e3)+(e5,e2)+(e6,e1) Các biến cố (ei, ej), i= 1,6 , gọi là các biến cố sơ cấp Biến cố A gọi là biến cố phức hợp. 1.2.2.Hệ tiên đề Kolmogorov: i) Tồn tại tập Ω ≠∅ gọi là không gian biến cố sơ cấp.Mỗi ω∈Ω được gọi là biến cố sơ cấp. ii) Tồn tại σ -đại số A các tập con của Ω . Mỗi A thuộc A được gọi là một biến cố ngẫu nhiên. iii) Mỗi A thuộc A có một số thực P(A) ≥0 gọi là xác suất của A. iv)P(Ω )=1. v)Nếu {Ai , i ≥ 1} là họ vô hạn các biến cố ngẫu nhiên từng đôi một xung khắc thì : 1 1 ( ) ( )i i i i P A P A ∞ ∞ = = =Σ Σ (tiên đề σ -cộng tính) 13 Bộ ba (Ω ,A,P) được gọi là không gian xác suất. 1.2.3.Tính chất của xác suất: *Định lí 1.2.3.1: Trong không gian xác suất (Ω ,A,P), ta có : i) P(∅ )=0 ii) Nếu {Ai , i = 1,n } là họ hữu hạn các biến cố ngẫu nhiên từng đôi một xung khắc thì : 1 1 ( ) ( ) n n i i i i P A P A = = =Σ Σ (tính cộng tính) Chứng minh: i)Vì ∅∈A , nên ( ) 0P ∅ ≥ (theo tiên đề Kolmogorov). Xét họ {Ai = ∅ ,i=1,2…,n,…}, thì : 1 ( ) ( )i i P A P ∞ = = ∅Σ Vậy ( ) 0P ∅ = . ii)Xét họ biến cố {A1, A2,…, An, An+1=∅ , An+2=∅ ,…}từng đôi một xung khắc, thì : 1 1 1 1 ( ) ( ) ( ) ( ) 0 n n i i i i i i i i P A P A P A P A ∞ ∞ = = = = = = = +Σ Σ Σ Σ (đpcm) *Định lí 1.2.3.2: Cho A,B là các biến cố ngẫu nhiên bất kì .Khi đó : C ) ( ) ( ) ( ) ( ) ) A B P(A) P(B) iii)0 P(A) 1 P(A ) 1 ( ) i P A B P A P B P AB ii P A ∪ = + − ⊂ ⇒ ≤ ≤ ≤ = − Chứng minh : i)A,B∈A , nên A∪B∈A, ta có : A∪B=A+BAc , suy ra : P(A∪B)= P(A)+P(BAc). Mặt khác : B=AB+AcB , suy ra : P(AcB)= P(B) – P(AB). Do đó : P(A∪B)= P(A)+ P(B) – P(AB). ii)A⊂B,suy ra: B = A + BAc. Do đó : P(B) = P(A) + P(BAc) ≥P(A). iii)Ta có : 0 ( ) ( )P A P≤ ≤ Ω (theo ii)). 14 Mà : ( )P Ω =1 ( tiên đề Kolmogorov). Và : A + Ac = Ω . Vậy: P(Ac) = 1 – P(A). (đpcm) *Định lí 1.2.3.3: Trong không gian xác suất (Ω ,A,P), cho biến cố ngẫu nhiên {Ai , i ≥ 1} thỏa : 1 2 1 ) ... ... ) n k k i A A A ii A ∞ = ⊃ ⊃ ⊃ =∅  Khi đó : ( ) (n )nP A O→ →∞ . Chứng minh: Ta có : 1 ( )( ) (theo i),ii))k k k k k k n k n k n A A A A ∞ = < ≥ ≥ = = =∅     Mà : 1 c n k k k k nk n A A A A + ≥≥ = +∑ Suy ra : 1 1( ) ( ) ( ) 0 ( ) c c n k k k k k k n k nk n P A P A P A A P A A+ + ≥ ≥≥ = + = +∑ ∑ Khi n →∞ thì 1( ) c k k k n P A A + ≥ ∑ 0→ vì là phần dư của chuỗi hội tụ. Vậy: ( ) (n )nP A O→ →∞ (đpcm). *Hệ quả 1.2.3.4: i) Nếu {Bn, n ≥ 1} là họ các biến cố thỏa 1 1 .1) .... .2) n n n n i B B i B B + ∞ = ⊂ ⊂ =  thì: ( ) ( ) (n )nP B P B→ →∞ . ii) Họ biến cố ngẫu nhiên {Cn, n ≥ 1} thỏa: 1 2 1 .1) ... ... .2) n n n ii C C C ii C C ∞ = ⊃ ⊃ ⊃ =  Khi đó : ( ) ( ) (n )nP C P C→ →∞ Định lí 1.2.3.3, và hệ quả 1.2.3.4 chỉ ra tính liên tục của độ đo xác suất . 15 1.2.4.Sự độc lập ngẫu nhiên: Giả sử B là lớp tùy ý các biến cố ngẫu nhiên (B ⊂ A).Ta nói lớp B độc lập nếu xác suất của một giao hữu hạn bất kì các biến cố trong B bằng tích xác suất của các biến cố đó. Ví dụ 2: i) B1={A,B} độc lập ⇔ P(AB)=P(A).P(B) ii) B2={A,B,C} độc lập ⇔ ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) P AB P A P B P AC P A P C P BC P B P C P ABC P A P B P C =  =  =  = 1.2.5.Phân phối xác suất: 1.2.5.1.Biến ngẫu nhiên : Trong không gian xác suất (Ω , A, P), R= ( , )−∞ +∞ là đường thẳng thực với σ -đại số các tập Borel B. Ánh xạ X: Ω→ℜ được gọi là biến ngẫu nhiên nếu B∀ ∈B, X-1(B) ∈A. Ví dụ 3: Xét phép thử F gieo 3 lần ngẫu nhiên đồng xu cân đối, đồng chất. Gọi X là số lần sấp trong 3 lần gieo. Khi đó X là biến ngẫu nhiên. Ta xác định X như sau : Kí hiệu : S:” đồng xu xuất hiện mặt sấp” N:” đồng xu xuất hiện mặt ngửa” Khi đó các biến cố sơ cấp trong Ω : Ω ={SSS, SSN, SNS, NSS, NNS, NSN, SNN, NNN}={w1, w2…,w8} : ( )i i X w X w Ω→ℜ  Với X(wi) bằng số lần xuất hiện chữ S trong wi. (i=1, 2.., 8) Khi đó: 8 8 7 6 5 1 , x 0 {w } , 0<x 1 [ ] { , , , } , 1<x 2 \{ } , 2<x 3 , x>3 X x w w w w w ∅ ≤  ≤< = ≤