ĐẠI SỐ TUYẾN TÍNH
Vectơ n chiều và các phép tính
- Véc tơ là một đoạn thẳng được cấu thành bởi 2 yếu tố là độ dài véctơ và hướng.
- Véctơ n chiều là một bộ gồm n số thực được sắp xếp có thứ tự và ký hiệu là
- Mỗi số xj gọi là thành phần hoặc toạ độ thứ j của x. x1 gọi là thành phần thứ 1 x2 gọi là thành phần thứ 2
xn gọi là thành phần thứ n
- Véctơ 0 là véctơ mà tất cả các thành phần đều bằng 0
- Véctơ đối của véctơ X là - X = (- x1, - x2, , - xn )
- Véctơ bằng nhau: 2 véctơ có cùng thành phần được gọi là bằng nhau khi và chỉ khi các thành phần tương ứng của chúng bằng nhau từng đôi một.
Như vậy, 2 véctơ bằng nhau là 2 véctơ có các thành phần giống hệt nhau
- Véctơ hàng là n số thực được sắp xếp theo hàng.
- Véctơ cột là n số thực được sắp xếp theo cột.
- Véctơ đơn vị là véctơ có 1 thành phần bằng 1 còn các thành phần còn lại đều bằng 0.
1.2.1 Phép cộng 2 véctơ có cùng thành phần
Ta gọi tổng của 2 véctơ n chiều X và Y là một véctơ n chiều Z mà các thành phần của nó là tổng các thành phần tương ứng của X và Y, nghĩa là:
Phép cộng chỉ có thể thực hiện trên các véctơ có cùng số chiều, và thực chất nó tương đương với phép cộng các số Do đó, phép cộng véctơ cũng mang đầy đủ các tính chất của phép cộng trong toán học.
1.2.2 Phép nhân vectơ với một số
Tích của một vectơ n chiều X với một hằng số k được ký hiệu là kX, trong đó các thành phần của kX là các thành phần tương ứng của X được nhân với k Cụ thể, kX = {kxj} với j chạy từ 1 đến n.
Thực chất của phép tính này cũng quy về phép tính trên các số.
Các tính chất cơ bản của 2 phép tính trên:
- Luật phân bố: k (X + Y) = kY + kX
1.2.3 Tích vô hướng của hai vectơ
Tích vô hướng của hai vectơ n chiều X và Y là một số thực, được tính bằng cách tổng hợp các tích của các thành phần tương ứng của hai vectơ này, ký hiệu là (X, Y).
1.3 Độc lập và phụ thuộc tuyến tính
Cho một hệ thống m vectơ n chiều X1 , X2 , , Xm (I)
Ta có đẳng thức vectơ: k1 X1 + k2 X2 + + km Xm = 0 (*) xảy ra khi ta tìm được m số thực k1 ,k2 , , km
- Nếu có ít nhất một số k khác 0 thì Hệ (I) được gọi là phụ thuộc tuyến tính.
- Nếu k1 = k2 = = km thì Hệ (I) được gọi là độc lập tuyến tính.
Và tồn tại 4 số thực k1 ,k2 , k3, k4 Hệ độc lập hay phụ thuộc tuyến tính?
Ta thấy, ứng với mỗi một k4 thì cho một k1,k2 ,k3 Do đó, có ít nhất 1 k 0 nên hệ phụ thuộc tuyến tính
Ma trận
2.1 Các khái niệm cơ bản
Bảng m và n số thực được xếp thành m hàng và n cột là ma trận cấp m n
Mỗi phần tử trong ma trận được ký hiệu là aij, trong đó i là chỉ số hàng và j là chỉ số cột Đường chéo của ma trận được gọi là aii, với các phần tử nằm trên đường chéo này có chỉ số hàng và cột bằng nhau.
* Một số ma trận đặc biệt:
- Ma trận 0: Là ma trận mà mọi phần tử đều bằng 0
- Ma trận vuông: Là ma trận có số hàng bằng số cột (m=n) khi đó ta gọi là ma trận vuông cấp n
- Ma trận tam giác: Là ma trận vuông mà mọi phần tử nằm về một phía của đường chéo đều bằng 0
- Ma trận đường chéo: Là ma trận vuông mà mọi phần tử nằm ngoài đường chéo đều bằng 0
- Ma trận đơn vị: Là ma trận đường chéo mà mọi phần tử trên đường chéo đều bằng 1, ký hiệu E
- Ma trận chuyển vị: Nếu ta đổi hàng thành cột và cột thành hàng thì ta dược ma trận chuyển vị của ma trận đã cho.
2.2 Các phép tính ma trận
Cho hai ma trận A và B có cùng kích thước m × n, ma trận tổng C cũng có kích thước m × n Các phần tử của ma trận C được tính bằng cách cộng các phần tử tương ứng của ma trận A và B.
2.2.2 Phép nhân ma trận với một số thực
Tích của ma trận A = (aij)mn với một số thực k tạo ra ma trận k.A có kích thước m n, trong đó các phần tử của ma trận này là kết quả của việc nhân từng phần tử tương ứng của A với k Do đó, ma trận C = (k.A) = (k aij)mn.
* Trường hợp hiệu hai ma trận cùng cấp có thể được coi là phép cộng của một ma trận với ma trận đối của ma trận kia: A - B = A + (-B)
2.2.3 Phép nhân hai ma trận
Phép nhân hai ma trận A và B tạo ra ma trận C = (cik)m×p, trong đó phần tử tại hàng i và cột k của C được tính bằng tổng các tích của các phần tử trên hàng i của ma trận A với các phần tử trên cột k của ma trận B.
Phép nhân ma trận yêu cầu số cột của ma trận đầu tiên phải tương đương với số hàng của ma trận thứ hai Vì vậy, phép nhân hai ma trận không có tính chất giao hoán.
Định thức
3.1 Cách xác định giá trị định thức
+) Xác dịnh giá trị định thức cấp 2
+) Xác định giá trị định thức cấp 3
+) Xác định giá trị định thức cấp n
- Phần bù: Mij là phần bù của A khi ta xoá di dòng i và cột j của A
- Phần bù đại số của phần tử aij của định thức Alà: Aij = (-1) i+j Mij
Phần bù đại số của A là A21
+ Cách 1: Khai triển định thức
Ví dụ: Khai triển định thức A
+ Cách 2: Biến đổi định thức về dạng tam giác
3.2 Tính chất của định thức
- Định thức của một ma trận vuông bằng định thức của ma trận chuyển vị của nó.
- Nếu có một dòng hoặc một cột gồm toàn số 0 thì giá trị định thức bằng 0
- Nếu có hai dòng hoặc hai cột giống nhau thì giá trị định thức bằng 0
- Nếu có hai dòng hoặc hai cột tỷ lệ với nhau thì giá trị định thức bằng 0
- Nhân một dòng hoặc một cột của định thức với k thì giá trị định thức gấp lên k lần.
Nếu hoán đổi hai dòng hoặc hai cột trong một định thức mà không thay đổi vị trí của các dòng và cột khác, giá trị của định thức sẽ bị đổi dấu.
Khi cộng một dòng hoặc một cột của định thức với một dòng hoặc một cột khác đã được nhân với một số, giá trị của định thức sẽ không thay đổi.
Ma trận nghịch đảo
- Cho ma trận A là ma trận vuông cấp n Nếu hạng của ma trận bằng n thì ta nói là ma trận A không suy biến.
- Điều kiện để có ma trận nghịch đảo: Ma trận không suy biến Do đó, ma trận vuông A không suy biến nếu A 0
* Định nghĩa: Ma trận A cấp n không suy biến bao giờ cũng tồn tại một ma trận cùng cấp A -1 sao cho: A.A -1 = A -1 A = E
A -1 được gọi là ma trận nghịch đảo của A và là ma trận nghịch đảo duy nhất.
4.2 Cách tìm ma trận nghịch đảo
- Trên các hàng của ma trận này thực hiện các phép biến đổi sơ cấp 2 và 3 biến đổi sao cho A trở thành E, khi đó E sẽ trở thành A -1
Nếu A không thể biến đổi thành E thì ma trận A suy biến và không tồn tại A -1
Ví dụ: Tìm ma trận nghịch đảo của ma trận:
Thành lập ma trận AE và biến đổi như sau:
Hệ phương trình tuyến tính
Hệ phương trình tuyến tính tổng quát gồm m phương trình và n ẩn có dạng: a11x1+ a12x2 + + a1nxn = b1 a21x1+ a22x2 + + a2nxn = b2 am1x1+ am2x2 +…+ amnxn = bm
+) aij là hệ số của ẩn số xj trong phương trình i (i= 1m; j = 1n)
A = (aij)mn gọi là ma trận hệ số của phương trình
+) B = (b1, b2, …, bm) là vectơ vế phải của hệ phương trình
+) X = (x1, x2, , xn) là vectơ ẩn số của hệ phương trình
+) A = AB là ma trận mở rộng của hệ phương trình
+) Aj là vectơ cột j của ma trận A
Hệ phương trình có thể viết dưới dạng: A.X = B X = A -1 B
- Vectơ X thoả mãn mọi phương trình của hệ gọi là một nghiệm của hệ.
- Một hệ có ít nhất một nghiệm gọi là hệ có nghiệm hay hệ tương thích.
- Một hệ có một nghiệm duy nhất gọi là hệ xác định hay hệ Cramer.
- Một hệ có hơn một nghiệm gọi là hệ vô định hay không xác định.
- Một hệ không có nghiệm gọi là hệ vô nghiệm.
Hệ có n phương trình n ẩn số thì hệ có nghiệm duy nhất gọi là hệ Cramer dj xj = (j = 1n) d
Định thức của ma trận hệ số được ký hiệu là d, trong khi định thức có cột thứ j được gọi là dj, với cột thứ j là cột số hạng tự do và các cột còn lại giống như trong định thức d.
Aj được suy ra từ A bằng cách thay cột j của A bằng B
Ví dụ: Giải hệ phương trình: x + y + 2z = - 1
5.2.2 Dùng phương pháp biến đổi sơ cấp
- Đổi chỗ hai dòng hoặc hai cột cho nhau.
- Nhân tất cả các phần tử của một dòng hoặc một cột của ma trận với một hằng số khác 0.
- Nhân tất cả các phần tử của một dòng (cột) của ma trận với một hằng số khác 0 rồi cộng vào một dòng (cột) khác.
VD1: Giải hệ phương trình:
Thành lập ma trận mở rộng và biến đổi như sau:
Hệ phương trình có nghiệm duy nhất là: x = (1, -1, 2)
VD2: Giải hệ phương trình: x1 + 2 x2 + 3 x3 – x4 = 8
Thành lập ma trận mở rộng và biến đổi như sau:
Như vậy, phương trình (3) bị loại khỏi hệ Từ phương trình (2) giữ lại ẩn x2, chuyển x3 và x4 sang vế phải làm ẩn tự do, ta được: x2 = 5 - 2 x3 + x4 ; x1 = -2 + x3 - x4
Vậy hệ phương trình có nghiệm tổng quát:
Hệ vô định, cho các ẩn tự do những trị số tuỳ ý, ví dụ: x3 = 1 ; x4 = 2 nghiệm cụ thể ( -3, 5, 1, 2)
PHƯƠNG PHÁP ĐƠN HÌNH VÀ BÀI TOÁN ĐỐI NGẪU
Các khái niệm, tính chất chung của bài toán quy hoạch tuyến tính
1.1 Một số ví dụ thực tế dẫn đến bài toán quy hoạch tuyến tính
1.1.1 Bài toán khẩu phần thức ăn
Giả sử có một đội sản xuất chăn nuôi 1 loại gia súc, đội có 2 loại thức ăn I,
II Trong 2 loại thức ăn đều có chứa 3 chất dinh dưỡng A, B, C Số đơn vị chất dinh dưỡng trong khẩu phần thức ăn và nhu cầu tối thiểu về số đơn vị chất dinh dưỡng trong khẩu phần thức ăn được cho trong bảng:
Biết rằng: Giá bán của một đơn vị thức ăn I là 1000 đ
Giá bán của một đơn vị thức ăn II là 2000 đ
Để đảm bảo gia súc phát triển bình thường và tối ưu hóa chi phí thức ăn, cần xác định lượng thức ăn cho từng loại trong khẩu phần hàng ngày, đảm bảo đáp ứng đầy đủ yêu cầu dinh dưỡng.
Gọi X1, X2 lần lượt là số đơn vị thức ăn loại I, II cần cho khẩu phần thức ăn mỗi ngày (X1, X2 0)
Chi phí về khẩu phần thức ăn là: 1 X1 + 2 X2
Yêu cầu về chất dinh dưỡng A: 2 X1 + 7 X2
Yêu cầu về chất dinh dưỡng B: 5 X1 + 3 X2
Yêu cầu về chất dinh dưỡng C: 1 X1 + 4 X2 Điều kiện phải có: Hàm mục tiêu chi phí nhỏ nhất: X1 + 2 X2 Min
Yêu cầu tối thiểu về chất dinh dưỡng: 2 X1 + 7 X2 16
Để giải bài toán, chúng ta cần xác định X1 và X2, đại diện cho khối lượng thức ăn cần sử dụng, nhằm đảm bảo chi phí tối thiểu trong khi vẫn đáp ứng đủ nhu cầu dinh dưỡng cho gia súc phát triển khỏe mạnh.
1.1.2 Bài toán đặt kế hoạch sản xuất
Một nhà máy chuyên sản xuất hai loại sản phẩm A và B, sử dụng ba nguyên liệu I, II và III Số lượng nguyên liệu dự trữ cho từng loại và lượng nguyên liệu cần thiết để sản xuất mỗi sản phẩm được trình bày trong bảng.
Lợi nhuận từ sản phẩm A là 20 và từ sản phẩm B là 30 Để tối đa hóa lợi nhuận, cần xác định số lượng sản phẩm A và B cần sản xuất trong giới hạn nguồn nguyên liệu có sẵn.
Gọi X1, X2 là khối lượng sản phẩm A, B được tạo ra: (X1, X2 0)
Trong khuôn khổ nguyên liệu I: 1 X1 + 3 X2 18
Hai ví dụ đơn giản trên minh họa mô hình toán học cho các vấn đề thực tiễn Những bài toán này có thể được hiểu là bài toán tìm cực trị của một hàm tuyến tính, xác định trên tập hợp nghiệm của một hệ thống hỗn hợp các phương trình và bất phương trình tuyến tính, được gọi là bài toán quy hoạch tuyến tính.
1.2 Bài toán qui hoạch tuyến tính và các dạng đặc biệt
1.2.1 Bài toán qui hoạch tuyến tính và các khái niệm
1.2.1.1 Bài toán qui hoạch tuyến tính
Tìm vectơ X = xj: j = 1n thoả mãn: aijxj = bi (i = 1, m1) aijxj bi (i = m1 + 1, m2) aijxj bi (i = m2 + 1, m) xj 0 (j = 1, p) xj 0 (j = p + 1, q) xj không có điều kiện dấu (j = q + 1, n) Sao cho: f(x) = Cjxj max
- Ràng buộc: Mỗi phương trình hoặc bất phương trình trong hệ điều kiện gọi là một ràng buộc.
- Hàm mục tiêu f(x) thể hiện mục tiêu mình cần đạt được.
- Phương án: Là một vectơ x nào đó thoả mãn mọi ràng buộc của bài toán gọi là một phương án.
Tập phương án là tổng hợp tất cả các phương án khả thi của một bài toán, thường được sử dụng để chỉ miền ràng buộc Ký hiệu của tập phương án là D.
Phương án tối ưu, hay còn gọi là phương án tốt nhất, là giải pháp mang lại giá trị cực trị cho hàm mục tiêu, tức là tại phương án này, giá trị của hàm mục tiêu sẽ đạt cực đại hoặc cực tiểu.
- D = : Bài toán không có phương án nên không có phương án tối ưu.
+ Không có phương án tốt nhất.
+ Có thể tìm được phương án tốt nhất.
Một bài toán được coi là giải được khi tồn tại phương án tốt nhất Ngược lại, nếu không có phương án tối ưu, bài toán sẽ được xem là không giải được, tức là trị số hàm mục tiêu không bị giới hạn trong tập phương án, hoặc trị số hàm mục tiêu có thể giảm (hoặc tăng) vô hạn trong tập phương án đó.
Tìm vectơ X = xj: j = 1n thoả mãn: aijxj = bi (i = 1, m) xj 0 (j = 1, n)
Sao cho: f(x) = Cjxj max (min)
Hay có thể viết dưới dạng ma trận với hệ ràng buộc: A.X = B
Hệ ràng buộc được chia thành hai nhóm chính: nhóm ràng buộc dạng phương trình và nhóm ràng buộc bất phương trình Các ràng buộc bất phương trình sẽ chuyển đổi thành các ràng buộc về dấu, yêu cầu tất cả các biến trong hệ thống phải không âm.
Mọi bài toán quy hoạch tuyến tính có thể chuyển đổi thành bài toán dạng chính tắc tương đương, với giá trị tối ưu của hàm mục tiêu trong cả hai bài toán là giống nhau Từ phương án tối ưu của bài toán này, ta có thể suy ra phương án tối ưu cho bài toán kia.
Từ mệnh đề nhận thấy: Muốn giải được bài toán qui hoạch tuyến tính chỉ cần có một thuật toán giải được bài toán chính tắc là xong.
* Cách đưa bài toán về chính tắc:
Để chuyển đổi ràng buộc i có dạng aijxj bi thành phương trình, ta cần thêm một biến phụ xi p 0 vào vế trái Như vậy, bất phương trình sẽ được thay thế bằng phương trình: aijxj + xi p = bi, với điều kiện xi p 0.
Hệ số của biến xi p trong hàm mục tiêu = 0, tức là f(x) không đổi.
- Nếu ràng buộc i có dạng aijxj bi thì thay bất phương trình bằng: aijxj - xi p = bi với xi p 0
- Nếu xj không có điều kiện dấu thì đặt: xj = xj ’ - xj ’’ với xj ’ ; xj ’’ 0
- Nếu xj 0 thì đổi biến: xj ’ = - xj với xj ’ 0
Ví dụ: Cho qui hoạch tuyến tính sau, hãy đưa bài toán về dạng chính tắc.
Do X3 không có điều kiện dấu nên đặt X3 = X3 ’ - X3 ” với X3 ’, X3 ” 0
Bài toán qui về dạng:
Bài toán quy hoạch tuyến tính chuẩn là một biến thể đặc biệt của bài toán quy hoạch tuyến tính chính tắc, trong đó có sự hiện diện của ma trận đơn vị trong ma trận hệ số các ràng buộc.
Ví dụ: Cho bài toán qui hoạch tuyến tính sau:
X1, X2, X3, X4, X5 0 Hàm mục tiêu: f(x) = 4 X1 + 5 X2 + 0 X3 + 0 X4 + 0 X5 Max Đây là bài toán qui hoạch tuyến tính dạng chuẩn với ma trận hệ số các ràng buộc là:
Biến X3, X4, X5 được gọi là biến cô lập với hệ số bằng 1 Trong bài toán chính tắc, vế phải không âm và mỗi phương trình có một biến số với hệ số bằng 1, đồng thời biến này không xuất hiện trong các phương trình khác.
Phương án cực biên là giải pháp đáp ứng đầy đủ n ràng buộc độc lập tuyến tính Nếu phương án cực biên thỏa mãn chính xác n ràng buộc, nó được gọi là phương án cực biên không suy biến; ngược lại, nếu phương án thỏa mãn nhiều hơn n ràng buộc, nó được gọi là phương án cực biên suy biến.
- Một ràng buộc ở dạng dấu đẳng thức (=) được gọi là ràng buộc chặt.
- Một ràng buộc ở dạng dấu bất đẳng thức thực sự ( ; ) gọi là ràng buộc lỏng.
- Một phương án khi thay vào một ràng buộc mà nó thoả mãn dấu đẳng thức thì ta nói phương án đó thoả mãn chặt ràng buộc đó.
Phương pháp đơn hình
2.1 Nội dung và cơ sở của phương pháp
Trong bài toán chính tắc, nếu tồn tại phương án thì cũng sẽ có phương án cực biên Từ phương án cực biên này, ta cần đánh giá xem liệu nó có phải là phương án cực biên tốt nhất hay không Nếu đúng, thuật toán sẽ kết thúc; nếu không, ta sẽ điều chỉnh để tìm một phương án cực biên mới tốt hơn Vì số lượng phương án cực biên là hữu hạn, nên sau một số bước nhất định, ta sẽ tìm ra phương án tốt nhất hoặc kết luận rằng bài toán không có lời giải do hàm mục tiêu không bị chặn trên tập phương án.
2.1.2 Cơ sở của phương pháp đơn hình
Xét bài toán chính tắc:
Tìm vectơ X = {xj: j = 1 đến n} thỏa mãn các điều kiện aijxj = bi (i = 1, m) và xj ≥ 0 (j = 1, n) Mục tiêu là tối đa hóa (hoặc tối thiểu hóa) hàm f(x) = Cjxj Giả sử hệ phương trình ràng buộc (1) bao gồm m phương trình độc lập và m < n, điều này không làm giảm tính tổng quát của bài toán.
Bằng cách sử dụng các phép biến đổi sơ cấp, chúng ta có thể loại bỏ tổ hợp tuyến tính của các phương trình cùng loại, từ đó hệ phương trình chỉ còn lại những phương trình độc lập.
Nếu m = n, hệ phương trình ràng buộc sẽ có một nghiệm duy nhất Điều này có nghĩa là bài toán chỉ có một phương án hoặc không có phương án nào, do đó việc tìm phương án tối ưu trở nên không cần thiết.
Hạng của ma trận A là m, do đó số vectơ điều kiện Aj độc lập tuyến tính cực đại là m Mỗi phương án cực biên đều tương ứng với ít nhất một hệ vectơ độc lập tuyến tính cực đại Từ đó, cơ sở của phương án cực biên X được định nghĩa là một hệ vectơ {Aj} bao gồm các vectơ có thành phần dương của phương án cực biên x, và được ký hiệu theo quy ước là J.
Như vậy, khi ta nói phương án cực biên x có cơ sở J thì phải hiểu J có 3 nội dung sau (các đặc trưng của một cơ sở J)
J = m, trong đó J là số phần tử của J
Aj: j J) độc lập tuyến tính.
- Phương án cực biên không suy biến chỉ có 1 cơ sở duy nhất, đó là các vectơ tương ứng với các thành phần dương.
- Phương án cực biên suy biến có nhiều cơ sở khác nhau, phần chung của chúng là các vectơ tương ứng với các thành phần dương.
Ký hiệu: Xj (j J) gọi là thành phần cơ sở.
Xk (k J) gọi là thành phần phi cơ sở và Xk = 0.
Aj (j J) gọi là vectơ cơ sở.
Ak (k J) gọi là vectơ phi cơ sở.
Ta có công thức: Ak = xjk AJ (4)
Ký hiệu Xk = {xjk} cho thấy rằng Xk có thể được biểu diễn dưới dạng AJ -1.Ak b = xj Aj = xj Aj + xk Ak = xj Aj Biểu thức này phân tích b qua cơ sở J, thể hiện rằng thành phần cơ sở của phương án cực biên chính là hệ số phân tích vectơ b qua cơ sở của phương án cực biên đó.
b = XJ AJ XJ = AJ -1.b ( vectơ hệ số phân tích b qua cơ sở J)
Ta gọi: k = Cj Xjk - Ck là ước lượng của biến Xk theo cơ sở J
Ký hiệu: CJ = Cj: j J k = (CJ, Xk ) - Ck (6)
j = 0 (j J) là ước lượng của các biến cơ sở.
Dựa vào các ước lượng này ta sẽ đánh giá được phương án cực biên X. Các số liệu trên được thể hiện dưới 1 bảng gọi là bảng đơn hình.
2.2 Thuật toán của phương pháp đơn hình
Giả thiết bài toán đã biết 1 phương án cực biên X (0) , cơ sở J0 = 1, 2, , m
* Cách tính f 0 : Lấy vectơ ở cột hệ số nhân vô hướng với vectơ ở cột phương án được f0.
* Cách tính k : Lấy vectơ ở cột hệ số nhân vô hướng với vectơ hệ số phân tích ở cột k rồi trừ C.
Các bước giải bài toán qui hoạch tuyến tính bằng phương pháp đơn hình:
Bước 1: Kiểm tra dấu hiệu tối ưu của phương án cực biên tương ứng:
- Nếu k 0 (k J0) thì X (0) là phương án cực biên tốt nhất.
- Nếu dù chỉ 1k 0 thì X (0) không phải là phương án tối ưu, chuyển sang bước 2
Bước 2: Kiểm tra tính không giải được của bài toán :
- Nếu dù chỉ 1k 0 mà Xjk 0 (j J0) thì f (x) + - trên tập phương án nên bài toán không có phương án tối ưu Thuật toán kết thúc.
- Nếu mỗi k 0 mà có tương ứng dù chỉ 1 Xjk 0 (j J0), chuyển sang bước 3.
Bước 3: Chọn vectơ đưa vào cơ sở và vectơ loại khỏi cơ sở
- Cách chọn: Tìm max k = s Xs sẽ là ẩn cơ sở mới.
- Chọn ẩn bị loại khỏi cơ sở:
Lập tỉ số: với xjs 0
Chọn Min (xjs 0 ) = 0 = xr loại khỏi cơ sở.
Thành lập mẫu bảng đơn hình mới:
Trong cột cơ sở thay Xr bằng Xs Trong cột hệ số thay Cr bằng Cs
Dòng r gọi là dòng xoay Cột s gọi là cột xoay Phần tử Xrs được ghi trong dấu Xrs gọi là phần tử trục xoay, chuyển sang bước 4.
Để tính toán hàng vectơ đầu vào (Xs) trong bảng mới, chúng ta chia hàng vectơ loại ra (Xr) từ bảng cũ cho phần tử trục xoay (Xrs) Kết quả thu được gọi là dòng chuẩn.
Để biến đổi một dòng trong bảng đơn hình, bạn cần xác định phần tử thuộc cột xoay trên dòng đó Sau đó, đổi dấu phần tử này và nhân với dòng chuẩn Cuối cùng, cộng kết quả với dòng cũ để tạo ra dòng mới trong bảng đơn hình.
Kết quả nhận được một bảng đơn hình mới ứng với phương án cực biên mới Quay trở lại bước 1
Ví dụ: Giải bằng phương pháp đơn hình bài toán qui hoạch tuyến tính sau:
LG: Qui bài toán về chính tắc:
Ta có một phương án cực biên X 0 = (0, 0, 0, 7, 12, 10) với cơ sở J = (A4, A5, A6)Lập bảng đơn hình:
Hệ số Cơ sở PA 1 -3 2 0 0 0 x1 x2 x3 x4 x5 x6
k 0 với k J0, do đó bài toán có phương án cực biên tối ưu X = (4, 5, 0) với fmin = -11
Thuật toán đơn hình có khả năng giải quyết các bài toán không chính tắc Khi chuyển đổi về bài toán chính tắc, chúng ta nhận được bài toán chuẩn, từ đó có thể xác định ngay phương án cực biên xuất phát.
(Thuật toán đơn hình giải bài toán tổng quát)
Thuật toán đơn hình truyền thống chỉ có khả năng giải quyết bài toán chính tắc khi đã xác định được phương án cực biên Tuy nhiên, trong nhiều trường hợp, bài toán chính tắc có thể không có phương án hoặc không có phương án cực biên rõ ràng Do đó, cần mở rộng thuật toán đơn hình để có thể khảo sát bất kỳ bài toán chính tắc nào Thuật toán đơn hình mở rộng không chỉ xác định xem bài toán có phương án hay không, mà còn tìm ra phương án cực biên nếu có, từ đó giúp giải quyết bài toán một cách hiệu quả hơn.
Luôn giả thiết rằng bi 0 (i = 1n) vì có một bi nào đó âm thì chỉ cần nhân 2 vế của phương trình với (-1)
Xét bài toán chính tắc:
Tìm vectơ X = xj: j = 1n thoả mãn: aijxj = bi (i = 1, m) xj 0 (j = 1, n) Sao cho: f (x) = Cjxj min
Xây dựng bài toán phụ có dạng sau: aijxj + xi g = bi (i = 1, m) xj 0 ; xi g 0 (j = 1, n)
Hàm mục tiêu P(x, x g ) = xi g Min xi g : gọi là ẩn giả thứ i.
Bài toán phụ là dạng chuẩn và luôn có thể giải được nhờ hàm mục tiêu bị chặn dưới Bắt đầu với phương pháp đơn hình để giải bài toán phụ, sau một số bước hữu hạn, chúng ta sẽ tìm ra phương án cực biên Trong quá trình này, chỉ có thể xảy ra hai trường hợp.
- TH1: Nếu Pmin 0 thì bài toán xuất phát không có phương án.
Nếu Pmin = 0, bài toán chính tắc có phương án với hai khả năng xảy ra Thứ nhất, nếu trong cơ sở tối ưu của phương án cực biên không có các vectơ ứng với các ẩn giả xi g, ta sẽ đưa f(x) vào và tính toán cho đến khi hoàn tất Kết quả cuối cùng của bảng đơn hình trong bài toán phụ sẽ chính là phương án cực biên của bài toán chính tắc.
Nếu trong cơ sở tối ưu có một ẩn giả xi g với giá trị bằng 0, cần loại bỏ tất cả các cột xj có j < 0 và tiếp tục giải hàm f(x).
Khi xây dựng bài toán phụ, cần chỉ thêm biến giả vào những phương trình thiết yếu để đảm bảo ma trận điều kiện của bài toán phụ có đủ m vectơ đơn vị.
- Một biến giả đã bị loại khỏi cơ sở thì cột tương ứng không cần tính ở các bước tiếp sau.
- Đối với bài toán có f(x) Max thì chuyển bài toán về: g(x) = - f(x) Min
- Đối với bài toán phụ thì hệ số xj bằng 0
Ví dụ: Giải bài toán sau bằng phương pháp đơn hình:
Giải: Đưa bài toán về dạng chính tắc:
Ta thấy bài toán chính tắc không phải dạng chuẩn nên thành lập bài toán phụ:
P (x, x g ) = x1 g + x3 g Min Lập bảng đơn hình giải bài toán phụ như sau:
Hệ số Cơ sở PA 3 4 2 2 0 1 1 x1 x2 x3 x4 x5 x1 g x3 g
k 0 với k J0, bài toán có phương án cực biên tối ưu
Bài toán đối ngẫu
Mỗi bài toán quy hoạch tuyến tính đều có thể được xây dựng một bài toán thứ hai theo một quy tắc xác định, gọi là bài toán đối ngẫu hoặc bài toán liên hợp.
Hai bài toán này liên kết chặt chẽ với nhau, đến mức hành vi của một bài toán có thể suy ra hành vi của bài toán kia và ngược lại Vì vậy, khi việc nghiên cứu một bài toán gặp khó khăn, chúng ta có thể chuyển sang nghiên cứu bài toán đối ngẫu của nó.
Cho bài toán dạng chính tắc: aijxj = bi (i = 1, m) (I) xj 0 (j = 1, n) f (x) = Cjxj min
Xây dựng bài toán qui hoạch tuyến tính khác gọi là bài toán đối ngẫu của (I) là: (ĩ): f (Y) = biyi max aijyj Cj (j = 1, n)
* Qui tắc thành lập bài toán đối ngẫu:
- Nếu f (x) min thì f (Y) max và hệ ràng buộc của bài toán đỗi ngẫu có dạng
- Nếu f (x) max thì f (Y) min và hệ ràng buộc của bài toán đỗi ngẫu có dạng
- Ma trận điều kiện trong 2 bài toán là chuyển vị của nhau.
- Hệ số trong hàm mục tiêu của bài toán này là vế phải của hệ ràng buộc trong bài toán kia.
Trong bài toán này, số ràng buộc (không tính ràng buộc dấu) tương đương với số biến số trong bài toán khác, với mỗi ràng buộc của bài toán này tương ứng với một biến số của bài toán kia.
- Các biến số trong bài toán đối ngẫu không có ràng buộc dấu.
Cặp bất đẳng thức cùng chỉ số trong hai bài toán được gọi là cặp điều kiện đối ngẫu Trong hai bài toán (I) và (ĩ), có n cặp ràng buộc đối ngẫu thể hiện mối quan hệ xj ≥ 0 tương đương với aijyj ≤ Cj (với j = 1, n).
- (I) là bài toán gốc thì (ĩ) là bài toán đối ngẫu.
Bài toán đối ngẫu được chứng minh là tương đương với bài toán gốc, tức là (I) là đối ngẫu của (ĩ) Do đó, (I) và (ĩ) có thể được xem là một cặp quy hoạch đối ngẫu, và việc phân chia thành gốc và đối ngẫu chỉ mang tính chất qui ước.
Để viết bài toán đối ngẫu cho một bài toán quy hoạch tuyến tính, cần chuyển đổi bài toán cần viết đối ngẫu về dạng bài toán chính tắc tương đương Quy ước rằng bài toán đối ngẫu của bài toán chính tắc tương đương sẽ là bài toán đối ngẫu của bài toán ban đầu.
Ví dụ: Cho bài toán : x1 + 2 x2 - x3 + x4 = 1
2 x1 - 2 x2 + 3 x3 + 3 x4 9 x1 - x2 + 3 x3 - x4 1 xj 0 (j = 1, 4) f (x) = 2 x1 - 3 x2 + 3 x3 - 6 x4 Min Hãy viết bài toán đối ngẫu của bài toán đã cho và chỉ ra các cặp ràng buộc đối ngẫu.
LG: đưa bài toán về dạng chính tắc: x1 + 2 x2 - x3 + x4 = 1
Ta có 6 cặp ràng buộc đối ngẫu sau:
3.2 Sơ đồ viết bài toán đối ngẫu
VD: Hãy viết bài toán đối ngẫu của bài toán sau và chỉ ra các cặp điều kiện đối ngẫu: f (x) = 4 x1 - 5 x2 + 6 x3 Min
- x1 + 3 x2 - 4 x3 1 x1 0 x2 0 x3 không có điều kiện về dấu.
LG: đưa bài toán về dạng chính tắc: Đặt x2 = - x2 ’ với x2 ’ 0 Đặt x3 = x3 ’ - x3 ” với x3 ’, x3 ” 0
Bài toán chính tắc tương đương có dạng:
Bài toán đối ngẫu: f (y) = 6 y1 + 4 y2 + y3 Max
Bài toán tối ưu hóa có thể được phân chia thành bài toán gốc và bài toán đối ngẫu Bài toán gốc f(x) nhằm mục tiêu tối thiểu hóa, trong khi bài toán đối ngẫu f(y) hướng tới tối đa hóa Các điều kiện ràng buộc cho các biến xj và yi bao gồm: aij xj = bi, yi không có điều kiện dấu, aij xj ≥ bi, yi ≥ 0, aij xj ≤ bi, yi ≤ 0, xj ≥ 0, aij yi ≤ Cj, xj ≤ 0, aij yi ≥ Cj, và aij yi = Cj Việc hiểu rõ các điều kiện này là rất quan trọng trong việc giải quyết bài toán tối ưu.
VD: Viết bài toán đối ngẫu của bài toán sau: f (x) = - 4 x1 + x2 + 5 x3 + 3 x5 Min
3 x1 + 2 x2 - 3 x4 + x5 24 x1 , x3 , x5 0 Bài toán đối ngẫu có dạng: f (Y) = -15 y1 + 8 y2 + 9 y3 + 24 y4 Max
TOAN XAC SUẤT
Giải tích tổ hợp
1.1.Tính giai thừa, hoán vị
Ta có công thức sau: Pn = n ! ( Đọc là n giai thừa) n! được xác định bằng tích các số tự nhiên từ 1 đến n. n! = n.(n-1) (n-2) 2.1
Ví dụ: Trong giờ học giáo dục quốc phòng, một tiểu đội học sinh bao gồm 10 người xếp thành hàng dọc Hỏi có bao nhiêu cách xếp?
Ta có số cách xếp được tính theo công thức n! = 10! (cách)
Hoán vị là kết quả sắp xếp có thứ tự n phần tử của tập hợp A sao cho n≥1, mỗi kết quả sắp xếp đó được gọi là một hoán vị.
Số các hoán vị được xác định bằng cách liệt kê trong trường hợp số các hoán vị ít.
Số các hoán vị được xác định bằng cách dùng quy tắc nhân.
Trong đó: Pn là số các hoán vị n số các phần tử trong tập hợp A
Ví dụ: Có bao nhiêu cách xếp 4 bạn vào 4 chiếc ghế theo hàng ngang?
Ta sắp xếp thứ tự cho 4 bạn: P 4!
Giả sử tập hợp A có n phần tử (n≥1).Mỗi tập hợp con gồm k phần tử của A được gọi là một tổ hợp chập k của n phần tử đã cho.
Số các tổ hợp được xác định theo công thức sau:
Trong đó: C k n là số các tổ hợp chập k của n phần tử (0≤ k ≤ n)
Ngoài ra ta có công thức liên hệ sau: An k = C k n.k
Ví dụ: 1 tổ có 10 bạn, lấy 4 bạn đi dọn vệ sinh Hỏi có bao nhiêu cách chọn?
Ta lấy từ 10 người ra 4 người và không sắp xếp thứ tự
Chỉnh hợp là quá trình chọn k phần tử khác nhau từ n phần tử của tập hợp A (với n ≥ 1) và sắp xếp chúng theo một thứ tự nhất định Điều này được gọi là chỉnh hợp chập k của n phần tử đã cho.
Số các chỉnh hợp được xác đinh bằng công thức sau đây:
Trong đó A k n là số các chỉnh hợp chập k của n phần tử (1≤ k ≤ n)
Chú ý: - Với quy ước 0! = 1 , ta có A k n = n!/ (n - k)!
Ví dụ: Từ các số 2, 3, 5, 7 có bao nhiêu số tự nhiên có 3 chữ số khác nhau?
Ta lấy từ 4 số (2,3,5,7) ra 3 số và sắp xếp thứ tự:
Phép thử, các loại biến cố và xác suất của biến cố
Phép thử ngẫu nhiên là một loại thử nghiệm mà kết quả không thể được dự đoán trước, mặc dù chúng ta đã biết rõ tập hợp các kết quả có thể xảy ra.
Một thí nghiệm, một phép đo hay sự quan sát nào đó, được hiểu là một phép thử.
Tập hợp các kết quả có thể xảy ra của một phép thử được gọi là không gian mẫu của phép thử và được ký hiệu là Ω (ô mê ga).
Biến cố được hiểu là một tập hợp con của không gian mẫu và nó thường được ký hiệu bằng chữ in hoa A,B,C
Tập rỗng là biến cố không thể xảy ra
Tập Ω (ô mê ga) là biến cố chắc chấn xảy ra.
Khi gieo xúc xắc, biến cố không thể xảy ra là khi xúc xắc xuất hiện mặt 7 chấm, trong khi biến cố chắc chắn xảy ra là khi xúc xắc không vượt quá 6 chấm.
2.3 Xác suất của biến cố
Một đặc trưng quan trọng của biến cố trong một phép thử là khả năng xảy ra của nó Câu hỏi đặt ra là liệu biến cố đó có xảy ra hay không và xác suất xảy ra của nó là bao nhiêu Để đánh giá khả năng xảy ra, cần gán cho biến cố một con số hợp lý, được gọi là xác suất của biến cố.
Đinh nghĩa cổ điển, định nghĩa thống kê của xác suất
3.1 Định lí cộng xác suất Định lý 1 : Xác suất của tổng hai biến cố không xung khắc bằng tổng xác suất của từng biến cố trừ đi xác suất của tích hai biến cố đó
Nếu A, B không xung khắc thì: P(A + B) = P(A) + P(B) – P(A.B)
Trong một tình huống, một người đi chào hàng tại hai địa điểm độc lập, với xác suất nhận đơn đặt hàng tại địa điểm đầu tiên là 0,3 và tại địa điểm thứ hai là 0,4 Để tính xác suất tổng thể mà người đó nhận được ít nhất một đơn đặt hàng, ta cần áp dụng quy tắc xác suất cho các sự kiện độc lập.
- Gọi: C “người đó có nhận được đơn đặt hàng”
A “nơi thứ nhất đặt hàng” P(A) = 0,3
B “nơi thứ hai đặt hàng” P(B) = 0,4
- Ta có: P(A + B) = P(A) + P(B) – P(A.B) (vì A và B không xung khắc)
Mà P(A.B) = P(A).P(B) (vì A và B độc lập)
Thay số P(C) = P(A + B) = 0,3 + 0,4 – 0,3 × 0,4 = 0,58 Định lý 2 : Xác suất của tổng hai biến cố xung khắc bằng tổng hai xác suất của hai biến cố thành phần
Nếu A và B xung khắc thì: P(A + B) = P(A) + P(B)
Ví dụ 2: Gieo một con xúc xắc cân đối và đồng chất một lần Tính xác suất để xuất hiện nhiều nhất là 2 chấm
- Gọi A "xuất hiện nhiều nhất hai chấm”
A1 "xuất hiện mặt một chấm" => P(A1) = 1/6
A2 "xuất hiện mặt hai chấm" => P(A2) = 1/6
- Mở rộng với n biến cố A1, A2,…, An là xung khắc từng đôi thì:
P(A1 + A2 +…+An) = P(A1) + P(A2) + …+ P(An) Định lý 3 : Tổng các xác suất của một nhóm biến cố đầy đủ bằng 1
Nếu A1, A2,…, An tạo thành nhóm đầy đủ thì:
P(A1) + P(A2) +…+ P(An)=1 Định lý 4: Nếu A và Ā là 2 biến cố đối lập thì
Trong ví dụ này, một người chào hàng đến hai địa điểm độc lập Tại địa điểm đầu tiên, xác suất nhận được đơn đặt hàng là 0,3, trong khi tại địa điểm thứ hai, xác suất là 0,4 Để tính xác suất người chào hàng không nhận được đơn đặt hàng từ cả hai nơi, ta cần xác định xác suất không nhận đơn tại mỗi địa điểm, sau đó nhân các xác suất này với nhau.
Gọi A ‘‘người đó không nhận được đơn đặt hàng’’ Ā ‘‘người đó có nhận được đơn đặt hàng’’
Ta thấy Ā = C (Theo ví dụ 1 trong phần định lý 1)
3.2 Định lý nhân xác suất
Xác suất có điều kiện là xác suất xảy ra của biến cố B khi biết rằng biến cố A đã xảy ra, được ký hiệu là P(B | A).
Trong một hộp chứa 10 sản phẩm, bao gồm 6 sản phẩm chính và 4 sản phẩm phế phẩm, ta thực hiện việc rút ra hai sản phẩm theo phương thức không hoàn lại Mục tiêu là xác định xác suất để hai sản phẩm được rút ra đều là sản phẩm chính.
- Lần thứ hai lấy được chính phẩm biết rằng lần thứ nhất lấy được chính phẩm.
- Lần thứ hai lấy được chính phẩm biết rằng lần thứ nhất lấy được phế phẩm Giải: Đặt A “lần thứ nhất lấy được chính phẩm”
B “lần thứ hai lấy được chính phẩm”
Khi tính toán xác suất của tích hai biến cố phụ thuộc, ta có thể sử dụng công thức: P(A ∩ B) = P(A) × P(B|A), trong đó P(A) là xác suất của biến cố A, và P(B|A) là xác suất có điều kiện của biến cố B khi biết rằng A đã xảy ra.
Nếu A và B là phụ thuộc thì: P(A.B) = P(A).P(B|A)
Trong một hộp chứa 10 sản phẩm, bao gồm 6 chính phẩm và 4 phế phẩm, ta sẽ tính xác suất để lấy ra 2 chính phẩm khi thực hiện việc chọn không hoàn lại.
- Gọi C "Lấy được 2 chính phẩm”
A "Lấy được chính phẩm ở lần thứ nhất”
B "Lấy được chính phẩm ở lần thứ hai"
Do phương thức lấy là không hoàn lại nên A và B là phụ thuộc
Mở rộng với n biến cố A1, A2,…, An là phụ thuộc thì:
P(A 1A2…An) = P(A1).P(A2|A1)…P(An|An–1) Định lý 2: Xác suất của tích hai biến cố độc lập bằng tích các xác suất thành phần
Nếu A và B là độc lập thì: P(A.B) = P(A).P(B)
Trong một hộp chứa 10 sản phẩm, bao gồm 6 chính phẩm và 4 phế phẩm, người ta tiến hành lấy ra 2 sản phẩm theo phương thức có hoàn lại Tính xác suất để hai sản phẩm được lấy ra đều là chính phẩm.
- Gọi C "Lấy được 2 chính phẩm”
A "Lấy được chính phẩm ở lần thứ nhất”
B "Lấy được chính phẩm ở lần thứ hai"
- Do phương thức lấy là có hoàn lại nên A và B là độc lập
Mở rộng với n biến cố A1, A2,…, An là độc lập toàn phần thì:
Từ định lý 1 và 2 ta suy ra:
- Nếu P(B) = 0 và P(A) = 0 thì P(A | B) và P( B | A) là không xác định
- Nếu A và B độc lập và P(A) > 0 ; P(B) > 0 thì: P(A) = P(A.B) / P(B) và P(B) = P (A.B) / P(A)
- A và B độc lập khi và chỉ khi: P(A.B) = P(A).P(B)
- Nếu A và B là độc lập thì A và B , Ā và B, Ā và B cũng độc lập
Lược đồ Bernoulli là một mô hình xác suất trong đó thực hiện n phép thử độc lập với xác suất xảy ra của biến cố A là p Định lý Bernoulli cho phép tính xác suất của biến cố A xảy ra đúng x lần trong n phép thử, được ký hiệu là P(x | n, p), thông qua một công thức cụ thể.
Ví dụ: Một người đi chào hàng ở 5 nơi độc lập nhau, xác suất mỗi nơi đặt hàng đều bằng 0,4 Tính xác suất để
- Có đúng 1 nơi đặt hàng
- Có đúng 2 nơi đặt hàng
Coi việc chào hàng ở mỗi nơi là 1 phép thử => n = 5
Gọi A “đặt hàng“ thì P(A) = 0,4 trong mỗi phép thử
=> Bài toán thỏa mãn lược đồ Bernoulli với n = 5 và p = P(A) = 0,4
Xác suất để có đúng 1 nơi đặt hàng là:
Xác suất để có đúng 2 nơi đặt hàng là:
P(x = 2 | n = 5;p = 0,4) = C 2 5 (0,4) 2 (1 - 0,4) 3 = 10 x 0,16 x 0,216 = 0,3456 Đặt C ‘‘có nơi đặt hàng’’ => C ‘‘không nơi nào đặt hàng’’
Chú ý rằng, ngoài việc sử dụng máy tính bấm tay để tính xác suất, bạn có thể tham khảo bảng Phụ lục 1 để tra cứu xác suất cho các bài toán có n lên đến 12 và p là các giá trị lẻ đến 0,5.
3.4 Công thức xác suất đầy đủ và công thức Bayes
Hệ n các biến cố A1,A2, , An được gọi là đầy đủ và xung khắc từng đôi nếu trong phép thử bắt buộc có 1 và chỉ 1 biến cố xảy ra.
Trong một hộp chứa ba màu sắc: xanh, đỏ và vàng, khi chọn ngẫu nhiên một màu, ta có thể định nghĩa các biến cố A, B, C tương ứng với việc chọn màu xanh, đỏ và vàng Các biến cố này tạo thành một hệ đầy đủ và xung khắc từng đôi, nghĩa là chỉ có thể chọn một màu trong ba màu đã cho.
3.4.1 Công thức xác suất đầy đủ
Giả sử A1,A2, ,An Là hệ đầy đủ các biến cố và P(Ai)>0 với mọi i= 1,2 ,n. Khi đó với A là biến cố bất kì với P(A)> 0 ta có:
Trong một xí nghiệp có hai phân xưởng với tỷ lệ phế phẩm lần lượt là 1% và 2%, phân xưởng I sản xuất 40% và phân xưởng II sản xuất 60% tổng sản phẩm Để tính xác suất chọn ngẫu nhiên một phế phẩm từ kho của xí nghiệp, cần xem xét tỷ lệ sản phẩm của từng phân xưởng và tỷ lệ phế phẩm tương ứng.
Gọi A1, A2 là biến cố lấy được 1 sản phẩm của phân xưởng I, II thì A1, A2 là nhóm đầy đủ và xung khắc.
Gọi A: lấy được một phế phẩm
Giả sử A1,A2, ,An Là hệ đầy đủ các biến cố và P(Ai)>0 với mọi i= 1,2 ,n. Khi đó với A là biến cố bất kì với P(A)> 0 ta có:
Giả sử lấy ra được 1 phế phẩm, tìm xác suất để phế phẩm là của phân xưởng I?
Ví dụ 2: Có 3 hộp giống nhau: hộp I chứa 20 bi trắng; hộp II chứa 10 bi trắng và
Trong bài toán này, có hai hộp: hộp I chứa 10 viên bi xanh và hộp III chứa 20 viên bi xanh Khi chọn ngẫu nhiên một hộp và bốc ra một viên bi trắng, chúng ta cần tính xác suất để viên bi đó thuộc về hộp I Để giải quyết, ta áp dụng định lý Bayes để tìm ra xác suất mong muốn.
Gọi Ak: chọn hộp thứ k ( k = 1,2,3)
Suy ra { Ak } đầy đủ và xung khắc.
3.5 Biến ngẫu nhiên và quy luật phân phối xác suất
Biến ngẫu nhiên là những biến có giá trị ngẫu nhiên đại diện cho kết quả của một phép thử Mỗi giá trị x mà biến ngẫu nhiên X nhận được được gọi là một thể hiện của X, đồng thời cũng là kết quả của phép thử, hay còn được hiểu là một sự kiện.
Biến ngẫu nhiên là một hàm ánh xạ từ không gian sự kiện đầy đủ đến một số thực, được ký hiệu là X: Ω↦R.
Biến ngẫu nhiên có 2 dạng:
Rời rạc (discrete): tập giá trị nó là rời rạc, tức là đếm được
Ví dụ như mặt chấm của con xúc xắc.
Liên tục (continous): tập giá trị là liên tục tức là lấp đầy 1 khoảng trục số
Ví dụ như giá thuê nhà ở Hà Nội.
3.5.2 Quy luật phân phối xác suất.
Là phương pháp xác định xác suất của biến ngẫu nhiên được phân phối ra sao.
THỐNG KÊ TOÁN
Cơ sở lý thuyết mẫu
Trong bài viết này, chúng ta sẽ khám phá các khái niệm cơ bản của thống kê toán, cùng với những thuật ngữ và ký hiệu quan trọng Những nội dung này sẽ được áp dụng trong các phần tiếp theo của bài viết.
Thống kê toán đóng vai trò quan trọng trong việc nghiên cứu các hiện tượng kinh tế – xã hội, thông qua việc phân tích thông tin thu thập từ các đối tượng liên quan đến vấn đề nghiên cứu.
Từ vấn đề nghiên cứu, ta sẽ có những khái niệm cơ bản là đối tượng nghiên cứu, dấu hiệu nghiên cứu, đại lượng nghiên cứu
Nghiên cứu sự hài lòng của sinh viên tại Đại học Kinh tế Quốc dân (ĐHKTQD) tập trung vào phương pháp giảng dạy của giảng viên Đối tượng nghiên cứu là sinh viên đang theo học tại trường, với dấu hiệu nghiên cứu chính là mức độ hài lòng Để đo lường sự hài lòng, một khái niệm trừu tượng, cần sử dụng các đại lượng đánh giá cụ thể.
Có hai cách thể hiện đánh giá:
Để thu thập ý kiến, chúng ta chỉ cần hai loại đánh giá: Không hài lòng và Hài lòng Hai kiểu đánh giá này có thể được biểu thị qua một đại lượng số học, trong đó giá trị 0 đại diện cho Không hài lòng và giá trị 1 cho Hài lòng Đại lượng 0 – 1 này sẽ được sử dụng làm cơ sở cho nghiên cứu.
Để đánh giá mức độ hài lòng, bạn có thể sử dụng thang điểm từ 1 đến 5, trong đó số điểm cao hơn thể hiện sự hài lòng lớn hơn Phương pháp này cho phép đánh giá thông qua một đại lượng với các giá trị rời rạc, và mức điểm sẽ trở thành đại lượng nghiên cứu chính.
Người quản lý cửa hàng chú trọng đến số tiền mà khách hàng chi tiêu tại cửa hàng, với đối tượng nghiên cứu là các khách hàng Dấu hiệu nghiên cứu trong trường hợp này là số tiền chi tiêu của khách hàng, được xem như một đại lượng gần như liên tục vì số tiền này có sự khác biệt giữa các khách hàng.
Các vấn đề nghiên cứu có thể được quy về một hoặc nhiều đại lượng số, bao gồm các giá trị như Hài lòng hoặc Không hài lòng Những đại lượng này có thể có số lượng giá trị hữu hạn hoặc vô hạn Trong ngôn ngữ Lý thuyết xác suất, các đại lượng này được gọi là biến ngẫu nhiên, cụ thể là Biến ngẫu nhiên gốc Đối với mỗi vấn đề nghiên cứu, biến ngẫu nhiên gốc chính là đại lượng nghiên cứu, nhận các giá trị ngẫu nhiên tùy thuộc vào từng đối tượng nghiên cứu.
Với ví dụ 1, theo cách đánh giá 1 thì biến ngẫu nhiên gốc X = {0 ; 1}; với cách đánh giá 2 thì biến ngẫu nhiên gốc là X = {1 ; 2 ; 3 ; 4 ; 5}
Với ví dụ 2, biến ngẫu nhiên gốc là số tiền khách hàng chi, do chỉ xét những khách hàng có chi tiền, nên X = (0; +).
1.1.2 Phương pháp nghiên cứu Để có được thông tin về các đối tượng, có hai phương pháp nghiên cứu là nghiên cứu Tổng thể và nghiên cứu Mẫu
Nghiên cứu tổng thể là phương pháp nghiên cứu toàn diện, bao gồm tất cả các đối tượng theo các tiêu chí đã xác định Ưu điểm nổi bật của nghiên cứu tổng thể là cung cấp thông tin đầy đủ, chính xác và trọn vẹn Tuy nhiên, phương pháp này cũng gặp phải một số hạn chế cần được xem xét.
- Phải trả chi phí lớn về kinh tế và thời gian do số lượng các phần tử trong tập hợp toàn bộ có thể rất lớn.
Việc áp dụng phương pháp này có thể dẫn đến việc phá hủy toàn bộ tập hợp nghiên cứu, đặc biệt là trong các nghiên cứu về thời gian hoạt động của thiết bị điện tử và dây chuyền sản xuất đồ hộp Hậu quả là toàn bộ thiết bị điện tử và sản phẩm đồ hộp sẽ bị hủy hoại.
Có những tập hợp thông tin mà chúng ta không thể nghiên cứu một cách toàn diện do thiếu dữ liệu đầy đủ Ví dụ, việc nghiên cứu ô nhiễm nước ở một dòng sông sẽ gặp khó khăn nếu muốn thu thập thông tin về toàn bộ nguồn nước trong dòng sông đó.
Sự hài lòng của sinh viên tại ĐHKTQD có thể được đánh giá thông qua việc thu thập thông tin từ phòng đào tạo và các đơn vị liên quan Tuy nhiên, việc này gặp khó khăn do một số sinh viên xin bảo lưu, không có mặt tại trường, hoặc không muốn tham gia khảo sát, dẫn đến việc thiếu sót thông tin từ toàn bộ sinh viên.
Bên cạnh đó nhiều sinh viên còn không trả lời thật, nên thông tin thu được dù nhiều cũng chưa phải là thông tin tổng thể
Trong việc phân tích mức chi tiêu của khách hàng, nếu chỉ xem xét những khách hàng đã từng mua hàng, hệ thống thanh toán hiện đại có thể cung cấp đầy đủ hóa đơn Tuy nhiên, trong giai đoạn chưa áp dụng công nghệ hiện đại, thông tin có thể không được lưu trữ hoặc bị xóa Để hiểu rõ hơn về mức chi tiêu của khách hàng, cần xem xét không chỉ cách họ đã mua hàng mà còn cả khả năng mua trong tương lai, điều này làm cho việc tổng thể hóa thông tin trở nên khó khăn.
Trên thực tế, đa số các trường hợp nghiên cứu toàn bộ tổng thể là không khả thi Khi đó ta sử dụng phương pháp nghiên cứu mẫu.
Nghiên cứu mẫu là phương pháp nghiên cứu tập trung vào một tập con được chọn từ tổng thể, nhằm phân tích các phần tử trong tập con đó Qua việc nghiên cứu các phần tử này, chúng ta có thể rút ra những kết luận có giá trị cho toàn bộ tập hợp nghiên cứu.
Phương pháp này thường được áp dụng trên thực tế vì các ưu điểm sau:
- Tính khả thi: khi tổng thể là không thể điều tra toàn bộ được thì phải chọn mẫu
- Chi phí ít tốn kém hơn so với điều tra toàn bộ tổng thể.
- Khả năng bị trùng lặp thấp, và vì không phải điều tra toàn bộ nên có thể bỏ qua một số phần tử
- Lượng thông tin thu thêm được trên các phần tử điều tra có tính giảm dần.
- Nếu mẫu được lấy ngẫu nhiên và khoa học thì các thông tin vẫn đảm bảo tính chính xác
Để thu thập thông tin từ sinh viên, có thể xây dựng một mẫu khảo sát dựa trên các lớp chuyên ngành, tín chỉ hoặc cấu trúc môn học Thêm vào đó, thông tin từ ví dụ tình huống ở đầu bài học cũng có thể được sử dụng làm mẫu tham khảo.
Vấn đề chính của thống kê toán là sử dụng thông tin từ mẫu để trả lời các câu hỏi về tổng thể Tổng thể là điều mà chúng ta cần biết, nhưng thường thì thông tin về tổng thể trong các lĩnh vực kinh tế - xã hội là không có hoặc không thể xác định Mặc dù thông tin từ mẫu có thể không đầy đủ và hoàn hảo, nhưng nếu chờ đợi thông tin tổng thể, quyết định có thể không bao giờ được thực hiện Do đó, cần phải sử dụng thông tin từ mẫu để đưa ra quyết định về tổng thể một cách chính xác nhất có thể, và thống kê toán sẽ đáp ứng yêu cầu này.
1.2 Các phương pháp mô tả tổng thể
1.2.1 Định nghĩa Định nghĩa tổng thể: Tổng thể là tập hợp các phần tử đồng nhất theo một dấu hiệu nghiên cứu định tính hoặc định lượng nào đó
Số phần tử trong tổng thể gọi là kích thước của tổng thể, ký hiệu là N; N có thể bằng vô cùng
Tổng thể về đánh giá của sinh viên đại học các hệ đang học tại ĐHKTQD,
N bằng 20 nghìn (số liệu của Phòng Quản lý đào tạo).
Tổng thể về mức chi của khách hàng đã và sẽ mua ở một cửa hàng, N có thể bằng vô cùng
Tổng thể về số vốn đăng ký của các doanh nghiệp thành lập mới trong năm
2013, N bằng 76955 (con số của Tổng cục Thống kê công bố)
Tổng thể về giá vàng bán ra tại các cửa hàng trên địa bàn Hà Nội trong năm
Ước lượng tham số
Để lấy một mẫu kích thước n, cần thực hiện n lần chọn ngẫu nhiên, trong đó mỗi lần chọn một phần tử có đại lượng nghiên cứu là X Đại lượng X là ngẫu nhiên và giống nhau ở mọi lần chọn, từ đó định nghĩa được mẫu ngẫu nhiên Cụ thể, một mẫu ngẫu nhiên kích thước n là tập hợp n biến ngẫu nhiên độc lập X1, X2,…, Xn, được hình thành từ biến ngẫu nhiên X trong tổng thể và có cùng phân phối với biến ngẫu nhiên gốc X.
Ký hiệu mẫu ngẫu nhiên: W = (X1, X2,…,Xn)
Do mỗi lần lấy phần tử cho mẫu, biến ngẫu nhiên X đều là như nhau, do đó kỳ vọng và phương sai của chúng đều bằng nhau
Mẫu ngẫu nhiên là khái niệm trừu tượng, chưa được thực hiện Khi tiến hành chọn n phần tử thực tế, ta nhận được một bộ số cụ thể Nếu lần chọn đầu tiên là X1 = x1, lần chọn thứ hai là X2 = x2, và tiếp tục cho đến Xn = xn, thì ta có một mẫu điều tra với n con số, gọi là mẫu cụ thể Mẫu cụ thể được định nghĩa là bộ n số thực (x1, x2,…, xn), là kết quả của phép thử từ mẫu ngẫu nhiên (X1, X2, …, Xn).
Ký hiệu mẫu cụ thể là w = (x1, x2, … , xn)
Mỗi con số gọi là một quan sát Do đó mẫu kích thước n sẽ có n quan sát. Như vậy:
- Mẫu ngẫu nhiên là một bộ n biến ngẫu nhiên, ký hiệu viết hoa
- Mẫu cụ thể là một bộ số liệu gồm n con số cụ thể, ký hiệu viết thường
2.1 Ước lượng điểm cho kỳ vọng, phương sai và xác suất
2.1.1 Ước lượng điểm : Giả sử tổng thể có tham số Θ, sau khi khảo sát mẫu ta tính được các thống kê, dựa vào các thống kê để đưa ra 1 số T thay thế Θ gọi là ước lượng điểm của Θ.
Không chệch có thể được hiểu đơn giản là ước lượng không chứa sai số hệ thống, tức là không thiên về việc đưa ra các giá trị nhỏ hơn Θ cũng như không thiên về việc đưa ra các giá trị lớn hơn Θ.
- Hiệu quả: trong các ước lượng có cùng tính chất, chọn ước lượng có phương sai nhỏ nhất.
- Vững: khi tăng dung lượng mẫu n lên vô hạn thì ước lượng sẽ dần đến Θ (dần đến theo xác suất).
- Chắc hay bền: không thay đổi nhiều khi trong mẫu có các số liệu quá nhỏ hay quá lớn.
Nếu không thể đưa ra ước lượng chính xác trên tất cả các khía cạnh, bạn có thể lựa chọn ước lượng đáp ứng một số tiêu chí nhất định, tùy thuộc vào mục đích sử dụng.
- Khi có phân phối chuẩn N(μ;σ 2 ) thì ước lượng trên nhiều mặt là trung bình cộng và phương sai mẫu σ 2
- Khi có phân phối nhị thức B(n,p) thì ước lượng tốt của tham số p là tần suất
2.1.2 Ước lượng khoảng Đây là cách tiếp cận có nhiều ứng dụng trong các ngành khoa học đòi hỏi phải thường xuyên xử lí số liệu như sinh học, y học, hóa học, kinh tế… Theo cách tiếp cận này sau khi tính các thống kê của mẫu quan sát, ta đưa ra khoảng [a;b] chứa tham số Θ Cận dưới a và cận trên b tính theo 1 quy tắc cụ thể dựa trên các thống kê và dựa trên mức độ tin cậy P.
Sau khi chọn mẫu, chúng ta xác định khoảng tin cậy [a; b] Nếu tham số Θ nằm trong khoảng này, khoảng tin cậy được coi là chính xác; ngược lại, nếu Θ nằm ngoài, khoảng tin cậy là sai Mỗi khoảng tin cậy chỉ có thể đúng hoặc sai, với xác suất đúng là P và xác suất sai là a = 1 – P Điều này có nghĩa là, theo quy tắc đã nêu, trung bình trong 100 trường hợp, sẽ có P * 100 trường hợp có khoảng tin cậy chính xác Chúng ta sẽ không đi sâu vào lý thuyết mà chỉ đưa ra quy tắc ước lượng tham số cho ba trường hợp.
- Ước lượng kỳ vọng μ của phân phối chuẩn khi biết phương sai σ 2 Các bước cần làm để ước lượng μ:
+ Chọn mẫu kích thước n, tính trung bình cộng Chọn mức tin cậy γ (α = 1 – γ gọi là mức sai cho phép hay mức ý nghĩa).
+ Dùng bảng tích phân hàm Laplace để tính giá trị tới hạn , tức là giá trị u sao cho:
+ Ước lượng m theo bất đẳng thức kép:
Lưu ý: nếu hàm phân phối chuẩn là thì tính , tức là giá trị u sao cho: Giá trị này ở 1 số sách còn được cho bởi bảng phân vị chuẩn
2.2 Ước lượng khoảng tin cậy cho tham số P của biến ngẫu nhiên phân phối theo quy luật không – một
TH1: Khi n đủ lớn (n>30): thay σ ở công thức (1) bằng độ lệch chuẩn hiệu chỉnh s. TH2: Khi n < 30
Các bước cần làm để ước lượng m:
+ Chọn mẫu kích thước n, tính trung bình cộng Tính phương sai mẫu
+ Dùng bảng phân phối Student, tính giá trị tới hạn , tức là giá trị t ở cột α, dòng n – 1
+ Ước lượng m theo bất đẳng thức kép:
Để ước lượng năng suất của một giống ngô, nghiên cứu được thực hiện trên 25 mảnh ruộng và kết quả thu hoạch được tính bằng đơn vị tạ/ha Giả thiết năng suất ngô tuân theo phân phối chuẩn với mức tin cậy P = 0,95.
Tra bảng phân phối Student ta được: t(24; 0,05) = 2,064
Vậy khoảng ước lượng năng suất trung bình của giống ngô:
2.3 Ước lượng kỳ vọng của biến ngẫu nhiên phân phối theo quy luật chuẩn
Trong một tổng thể gồm hai loại cá thể với số lượng lớn, tỷ lệ của loại A được ký hiệu là p (chưa xác định) Khi lấy ngẫu nhiên một cá thể, xác suất để chọn được cá thể loại A là p Nếu tiến hành lấy ngẫu nhiên n cá thể, trong số đó có m cá thể thuộc loại A, điều này sẽ giúp chúng ta phân tích và tính toán xác suất cũng như tỷ lệ của các loại cá thể trong tổng thể.
+ Lấy mẫu kích thước n, đếm tần số (m) xuất hiện cá thể loại A, tính tần suất
+ Dùng bảng tích phân hàm Laplace để tính giá trị tới hạn , tức là giá trị u sao cho:
+ Ước lượng m theo bất đẳng thức kép:
2.4 Ước lượng phương sai của biến ngẫu nhiên phân phối theo quy luật chuẩn
Theo (1), nửa chiều dài khoảng ước lượng: Nếu muốn ước lượng đạt độ chính xác ε thì phải lấy L ≤ ε Từ đó:
3 Kiểm định giả thuyết thống kê
Khi thực hiện nghiên cứu định lượng, mục tiêu chính là trả lời các câu hỏi nghiên cứu và kiểm tra các giả thuyết đã đặt ra Để đánh giá các giả thuyết này, chúng ta sử dụng phương pháp kiểm định giả thuyết, hay còn gọi là kiểm định ý nghĩa thống kê.
Hai giáo viên môn thống kê, Tom và Jerry, đều mong muốn áp dụng phương pháp giảng dạy hiệu quả cho lớp học của mình Tom yêu cầu sinh viên thực hiện bài tiểu luận bên cạnh việc học trên lớp, tin rằng điều này sẽ cải thiện hiệu quả học tập Ngược lại, Jerry cho rằng sinh viên nên tập trung lắng nghe trong giờ học để tiếp thu kiến thức tốt hơn Đây là năm đầu tiên Tom áp dụng phương pháp tiểu luận và cô hy vọng rằng nó sẽ giúp sinh viên nâng cao khả năng học tập.
3.2 Kiểm định về trung bình tổng thể
Cũng tương tự bài toán ước lượng khoảng, ta chỉ xét bài toán kiểm định với tổng thể phân phối Chuẩn
Xét biến ngẫu nhiên gốc trong phân phối chuẩn X ~ N(μ ; σ²) với tham số μ chưa biết, đại diện cho trung bình của tổng thể trong nghiên cứu Chúng ta tiến hành kiểm định giả thiết về tham số μ bằng cách so sánh với một số thực μ0 đã cho Các chứng minh đã được trình bày trong giáo trình, và ở đây, chúng ta áp dụng các công thức để thực hiện kiểm định và đưa ra kết luận phù hợp với từng trường hợp.
Trong một nghiên cứu về trọng lượng của một loại quả, các nhà khoa học đã tiến hành cân thử một số quả được chọn ngẫu nhiên Kết quả thu được được trình bày trong bảng số liệu dưới đây.
Biết rằng trọng lượng quả là đại lượng có phân phối chuẩn
(a) Tiêu chuẩn đặt ra cho trọng lượng trung bình của quả là 30g Với mức ý nghĩa 5%, có thể nói loại quả trên đạt tiêu chuẩn hay không?
(b) Mùa vụ trước trọng lượng trung bình của loại quả này là 29g Với mức ý nghĩa 5% có thể nói trọng lượng trung bình đã tăng lên không?
3.3 Kiểm định giả thuyết về phương sai tổng thể
Giả sử trong tổng thể có biến ngẫu nhiên gốc phân phối chuẩn, X ~ N( ,
Tham số 2 thể hiện mức độ phân tán, biến động, ổn định và đồng đều của tổng thể trong nghiên cứu, tuy nhiên giá trị cụ thể của nó vẫn chưa được xác định.
Chúng ta tiến hành kiểm định giả thuyết về mối quan hệ giữa phương sai tổng thể 2 và một giá trị phương sai cụ thể 2 0 đã cho Để thực hiện kiểm định này, chúng ta sử dụng một mẫu có kích thước n, với phương sai mẫu được ký hiệu là S 2 và độ lệch chuẩn là S.