Giáo trình Mô hình hóa và mô phỏng mạng (Các hệ thống rời rạc nói chung)

105 trang hoanguyen 3710

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Mô hình hóa và mô phỏng mạng (Các hệ thống rời rạc nói chung)", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_mo_hinh_hoa_va_mo_phong_mang_cac_he_thong_roi_rac.docx

Nội dung text: Giáo trình Mô hình hóa và mô phỏng mạng (Các hệ thống rời rạc nói chung)

MÔ HÌNH HÓA VÀ MÔ PHỎNG MẠNG (CÁC HỆ THỐNG RỜI RẠC NÓI CHUNG) 1. Những vấn đề cơ bản về mô hình hóa 1.1. Hệ thống 1.2. Mô hình 1.3. Những bài toán mô hình hóa 1.4. Các phương pháp mô hình hóa 1.5. Thảo luận 2. Cơ bản về thuyết xác suất 2.1. Khái niệm, định nghĩa 2.2. Các luật phân bố các biến ngẫu nhiên 2.3. Các đặc tính định lượng các biến ngẫu nhiên 2.4. Những phân bố điển hình các biến ngẫu nhiên 2.5. Thảo luận 3. Mô hình toán học những hệ thống rời rạc 3.1. Những khái niệm chính 3.2. Phân loại các mô hình hàng đợi 3.3. Tham số và đặc tính của hệ thống hàng đợi 3.4. Tham số và đặc tính của mạng hàng đợi 3.5. Thảo luận 4. Mô hình hóa phân tích 4.1. Hệ thống hàng đợi một kênh với luồng đồng nhất 4.2. Hệ thống hàng đợi nhiều kênh với luồng đồng nhất 4.3. Hệ thống hàng đợi một kênh với luồng không đồng nhất 4.4. Mạng hàng đợi mở có dạng mũ với luồng đồng nhất 4.5. Mạng hàng đợi đóng có dạng mũ với luồng đồng nhất 4.6. Thảo luận 5. Mô hình hóa số học (mô hình các tiến trình ngẫu nhiên) 5.1. Khái niệm tiến trình ngẫu nhiên 5.2. Tham số và đặc tính tiến trình ngẫu nhiên Markov 5.3. Các phương pháp tính mô hình Markov 5.4. Mô hình Markov các hệ thống hàng đợi 5.5. Mô hình Markov các mạng hàng đợi 5.6. Thảo luận 6. Mô hình hóa mô phỏng 6.1. Cơ sở mô hình hóa mô phỏng 6.2. Các phương pháp hình thành số ngẫu nhiên 6.3. Nhập môn GPSS World
6.4. Quá trình mô hình hóa trong môi trường GPSS World 6.5. Các operator trong GPSS World 6.6. Các command trong GPSS World 6.7. Làm quen với hệ thống NS2/NS3
MÔ HÌNH HÓA VÀ MÔ PHỎNG MẠNG (CÁC HỆ THỐNG RỜI RẠC NÓI CHUNG) Ngay cả nếu những chứng minh của bạn là đúng và rõ ràng đến đâu đi nữa, rằng loại trừ đi tất cả những sai lầm, thì dù sao vẫn tìm ra được người chỉ ra rằng bạn sai. (những quy luật của Murphy) Mô hình hóa toán học là một công cụ mạnh và hiệu quả để nghiên cứu những đối tượng, hệ thống, và tiến trình khác nhau trong nhiều lĩnh vực khác nhau trong hoạt động của con người. Sự đa dạng của các tiến trình trong những hệ thống và trong các đối tượng được nghiên cứu là ứng với sự đa dạng của những phương pháp và công cụ toán học được sử dụng trong lý thuyết mô hình hóa. Mô hình hóa – một quá trình nghiên cứu hệ thống gồm có nhiều bước phức tạp nhất, hướng đến việc làm sáng tỏ những tính chất và quy luật của hệ thống cần được nghiên cứu, với mục tiêu là tạo mới hoặc là nâng cấp chúng [các hệ thống]. Trong quá trình mô hình hóa một tập hợp các bài toán tương quan được giải quyết, trong đó cơ bản là phát triển mô hình, phân tích tính chất và đưa ra khuyến cáo cho việc nâng cấp những hệ thống có sẵn hoặc thiết kế những hệ thống mới. Phần lớn các hệ thống kỹ thuật, trong đó có máy tính và mạng, được mô tả bằng những thuật ngữ là những tiến trình ngẫu nhiên rời rạc với việc sử dụng các phương pháp xác suất. Trong này phần lớn áp dụng những mô hình toán học [mà để mô tả tổ chức kết cấu-hoạt động những hệ thống được nghiên cứu] là được xây dựng trên cơ sở những mô hình [thuộc] thuyết hàng đợi (queueing theory) mà việc phân tích chúng (các mô hình) có thể được thực hiện bằng những phương pháp phân tích (analytical), số học (numeral) và thống kê (statistic). Trong đó các phương pháp phân tích thì sử dụng các phương pháp xác suất [trong] thuyết hàng đợi, phương pháp số học sử dụng các phương pháp các tiến trình ngẫu nhiên Markov, phương pháp thống kê sử dụng phương pháp mô hình hóa mô phỏng (simulation). Theo tác giả, vì phức tạp không hẳn là tốt, cũng chưa hẳn là đúng, nên trong khi sử dụng các phương pháp phân tích (analytical) luôn hướng đến những công thức toán học đơn giản, [điều này] cũng đủ tạo điều kiện thực hiện những báo cáo có ý nghĩa, không chạy theo tính toán phức tạp mà vẫn đưa ra được những cái nhìn đầy đủ về tính chất tương thích [tương đương] của những hệ thống thực với mô hình. Việc sử dụng những công thức đơn giản cũng tạo điều kiện tính toán những đặc tính hoạt động (functioning characteristics) chủ yếu như: tải ngoài, tải trong và những giá trị trung bình của những đặc tính [mang tính] xác-suất-về-thời-gian (time-probabilistic) của những hệ thống. Tài liệu lý thuyết này có kèm theo những ví dụ và bài tập hướng đến việc phát triển kiến thức và kỹ năng vận dụng những mô hình và phương pháp đơn giản nhất để
tính tải ngoài, tài trong của những thành phần riêng biệt trong hệ thống và toàn bộ hệ thống và để thực hiện những phân tích đặc tính hoạt động những hệ thống thực, được mô tả (mô hình hóa) dưới dạng những mô hình hàng đợi hoặc những mô hình các tiến trình ngẫu nhiên Markov. Tài liệu này có thể giúp người đọc đạt được những mục tiêu cơ bản sau: 2.1. Có được một cái nhìn ban đầu về những nguyên lý mô hình hóa những hệ thống phức tạp trên cơ sở những ví dụ mô hình hàng đợi [được sử dụng rộng rãi] và những phương pháp tính toán của chúng với việc sử dụng 3 phương pháp chính: phân tích, số học và mô phỏng. 2.2. Hiểu biết được những nền tảng toán học cơ bản nhất cho việc nghiên cứu sau này và ý nghĩa toán học đơn giản nhất cho những tiến trình và hệ thống thực. 2.3. Hiểu biết được một bộ nhỏ nhất các mô hình, phương pháp và công cụ để nghiên cứu những hệ thống thực không phức tạp trong những lĩnh vực ứng dụng khác nhau.
1. Những vấn đề cơ bản về mô hình hóa Tất cả, những gì bắt đầu tốt đẹp, lại kết thúc tồi tệ. Tất cả những gì bắt đầu tồi tệ, thì kết thúc càng tồi tệ hơn. (Quy luật Pudder) Mô hình hóa - thay một đối tượng ban đầu bằng một đối tượng khác, mà gọi là mô hình (hình 1.1), và việc thực hiện những thực nghiệm với mô hình là với mục tiêu nhận được những thông tin về hệ thống bằng cách nghiên cứu những tính chất của mô hình. Đối tượng ban đầu (hệ thống, Mô hình tiến trình) Hình 1.1. Về khái niệm “mô hình hóa”. Những đối tượng mô hình hóa trong kỹ thuật là những hệ thống và những tiến trình chạy trong hệ thống đó. Nói riêng, trong kỹ thuật những đối tượng mô hình hóa là máy tính, tổ hợp máy tính, hệ thống tính toán và mạng máy tính. Mô hình hóa cho khả năng nghiên cứu những đối tượng mà việc thực nghiệm trực tiếp với chúng là: Khó thực hiện; Không lợi về kinh tế; Nói chung là không thể thực hiện. Mô hình hoá – một lĩnh vực quan trọng trong việc áp dụng những hệ thống tính toán hay mạng máy tính trong khoa học và kỹ thuật: trong toán học và vật lý, trong việc bán vé xe và vé máy bay, trong việc kiến tạo cơ khí và máy móc, trong quang học và điện tử, v.v. Sự lan rộng hơn nữa của mô hình hóa nằm trong những lĩnh vực như kinh tế, xã hội, nghệ thuật, sinh học, y học, v.v. Trong khi đó, máy tính và mạng máy tính tự nó là những đối tượng mô hình hóa trong giai đoạn: thiết kế những hệ thống mới hoặc nâng cấp (cải thiện) những hệ thống có sẳn, phân tích hiệu quả sử dụng những hệ thống trong những điều kiện khác nhau (ví dụ trong những tình huống cực đoan, trong những điều kiện tăng nhu cầu về tính tin cậy (reliability)). Áp dụng mô hình hóa trong giai đoạn thiết kế tạo điều kiện thực hiện việc phân tích những trường hợp khác nhau của những lời giải cho đồ án, xác định khả năng làm việc và đánh giá tính tin cậy của hệ thống, đưa ra được điểm thắt cổ chai và những nơi [có] tải nhỏ, cũng như đưa ra những khuyến cáo về những thay đổi hợp lý những thành phân và cấu trúc hay phương thức hoạt động của hệ thống.
1.1. Hệ thống 1.1.1. Khái niệm hệ thống và phức hệ “Phức tạp hóa thì đơn giản, đơn giản hóa thì phức tạp” (Luật Maier) Hệ thống – tập hợp những phần tử (element) tương tác (liên hệ) với nhau, mà những phần tử này kết nối với nhau thành một thể toàn vẹn để đạt được một mục tiêu nào đó, xác định được tính năng của hệ thống. Phần tử – một đối tượng nhỏ nhất không thể chia ra nữa, được xem như một thể toàn vẹn. Hệ thống phức tạp (hệ thống lớn) được đặc trưng bởi số lượng lớn những phần tử tham gia và [số lượng lớn] những kết nối giữa chúng với nhau. Phức hệ (complex) – tập hợp những hệ thống tương tác với nhau. Phần tử, hệ thống và tổ hợp – là những khái niệm tương đối. Bất kỳ một phần tử nào cũng có thể được xem như một hệ thống, nếu nó có thể được chia nhỏ ra thành những thành phần nhỏ hơn – những phần tử. Ngược lại, bất kỳ một phức hệ nào cũng có thể được xem như hệ thống, nếu những hệ thống trong tổ hợp đó xem như những phần tử. Liên hệ với điều này thì khái niệm ‘hệ thống’ và ‘phức hệ’ thường xem như những khái niệm tương đương. Ví dụ: máy tính có thể được xem là một hệ thống mà phần tử của nó là CPU, bộ nhớ, ổ đĩa, thiết bị vào ra. Trong khi đó, CPU có thể được xem như một hệ thống mà gồm những phần tử như thiết bị số học-logic, thiết bị điều khiển, bộ đếm lệnh, v.v . Để mô tả hệ thống thì cần thiết phải xác định được cấu trúc và chức năng và tương ứng với nó là tổ chức kết cấu và hoạt động. 1.1.2. Cơ cấu và hoạt động “Những hệ thống phức tạp có khuynh hướng mâu thuẫn với chính với những chức năng của chúng” (Nguyên lý Shateler) Cơ cấu (cấu trúc, structure) của hệ thống được cho bởi danh sách những phần tử trong thành phần của hệ thống và những kết nối giữa chúng. Các phương thức mô tả cấu trúc: Đồ thị (graph) Mạch (scheme) Phân tích – bằng cách cho số lượng các loại phần tử, số lượng mỗi loại và ma trận liên kết, xác định tương tác giữa các phần tử.
Hoạt động (chức năng, function) của hệ thống – quy tắc để đạt được một mục tiêu đặt ra, mô tả trạng thái hệ thống và hướng đến việc nhận được kết quả, thể hiện được chức năng của hệ thống. Các phương thức mô tả hoạt động: Thuật toán Phân tích Đồ họa Bảng 1.1.3. Tổ chức (organization) Một hệ thống phức tạp mà thiết kế vội vàng thì không bao giờ làm việc, và khi chỉnh sửa nó để hoạt động được, thì không thể (Luật thứ 16 trong Hệ thống học) Tổ chức hệ thống – phương thức đạt được một mục tiêu nào đó khi chọn một cơ cấu (cấu trúc) và hoạt động xác định của hệ thống. Có 2 loại tổ chức hệ thống: Tổ chức theo cơ cấu (structured organization): được xác định bởi tổ hợp các phần tử và phương thức kết nối thành cơ cấu giữa chúng với nhau, đảm bảo được khả năng thực hiện các hoạt động được giao. Tổ chức theo hoạt động (functional organization): được xác định bởi phương thức tạo ra hoạt động của hệ thống, đủ để đạt được mục tiêu đặt ra. 1.1.4. Những tính chất của hệ thống Bất kỳ hệ thống phức tạp nào cũng mang theo nó những tính chất căn bản, mà những tính chất này yêu cầu áp dụng những cách tiếp cận mang tính hệ thống khi nghiên cứu chúng bằng những phương pháp mô hình hóa toán học. Những tính chất này gồm có: Tính toàn vẹn (integrity) Tính gắn kết (coherence) Tính tổ chức (organization) Tính tích hợp (intergrativity) Kết luận: Hệ thống không phải là tập hợp đơn giản các phần từ. Khi phân chia hệ thống thành những phần nhỏ hơn và nghiên cứu mỗi một thành phần thì không thể biết được tất cả các tính chất của hệ thống toàn diện được. 1.1.5. Tính hiệu quả (effectiveness)
Nói chung thường thì mô hình hóa hướng đến việc giải những bài toán sau: Bài toán phân tích, liên quan đến việc đánh giá tính hiệu quả của hệ thống, được cho trong dạng tập hợp các chỉ số [về] hiệu quả (index of effectiveness). Bài toán tổng hợp, hướng đến việc xây dựng những hệ thống tối ưu theo tiêu chí hiệu quả được chọn. Tính hiệu quả - cấp độ tương xứng của hệ thống với công dụng của nó. Hiệu quả của hệ thống thường được đánh giá bởi tập hợp chỉ số hiệu quả. Chỉ số hiệu quả – thước đo (measure) một tính chất của hệ thống. Chỉ số hiệu quả luôn mang ý nghĩa định lượng. Số lượng các chỉ số hiệu quả những hệ thống kỹ thuật trong nhiều trường hợp có thể là khá lớn. Thường thì các chỉ số hiệu quả là trái nghịch nhau. Nghĩa là, sự thay đổi tổ chức theo kết cấu hoặc tổ chức theo hoạt động dẫn đến sự cải thiện của một chỉ số này, nhưng làm tồi đi một chỉ số hiệu quả khác, điều này làm phức tạp việc chọn được một khả năng (trường hợp) tổ chức cơ cấu-hoạt động tốt nhất cho hệ thống được thiết kế. Rõ ràng là tốt nhất thì chỉ nên có một chỉ số hiệu quả. Kiểu chỉ số loại này được gọi là tiêu chí hiệu quả. Tiêu chí hiệu quả (effectiveness criteria) - thước đo hiệu quả của hệ thống, gộp tất cả các tính chất của hệ thống trong một đánh giá – chính là giá trị tiêu chí hiệu quả. Nếu khi tính hiệu quả tăng, giá trị tiêu chí tăng thì tiêu chí được gọi là thuận, nếu giá trị tiêu chỉ giảm thì tiêu chí gọi là nghịch. Hệ thống tối ưu – hệ thống mà tương ứng là giá trị tiêu chí hiệu quả thuận (nghịch) lớn nhất (nhỏ nhất) trong tất cả các khả năng có thể để xây dựng hệ thống thỏa mãn được yêu cầu được cho. Phân tích (analysis) – quá trình xác định những tính chất (được mô tả bởi những đặc tính) mang theo ở hệ thống trên cơ sở những tham số (về hoạt động và cấu trúc). Phân tích Tham số Đặc tính Tổng hợp (synthesis) – quá trình xác định những tham số của hệ thống thỏa mãn những yêu cầu về những đặc tính. Tổng hợp Đặc tính Tham số
1.1.6. Tham số và đặc tính Bất kỳ một hệ thống nào về định lượng được mô tả bởi tập hợp các giá trị, có thể chia thành 2 lớp sau: Tham số (parameter) – được mô tả bởi tính chất ban đầu của hệ thống và là dữ liệu đầu vào khi giải quyết bài toán phân tích. Đặc tính (characteristics) – được mô tả bởi tính chất đứng thứ hai (đứng sau) và được xác định trong quá trình giải bài toán phân tích như là một hàm của tham số: đặc tính = f(tham số). Tập hợp tham số của những hệ thống kỹ thuật có thể chia thành: Tham số trong: o Tham số cơ cấu – mô tả thành phần và cấu trúc của hệ thống. o Tham số hoạt động – mô tả tổ chức hoạt động. Tham số ngoài: o Tham số tải ngoài – mô tả tác động đầu vào hệ thống. o Tham số môi trường xung quanh – thường mô tả những tác động môi trường bên ngoài mà không thể điều khiển được như là nhiễu, v.v. Tham số thì có thể là: Định trước (deterministic: tất định, định mệnh, định trước) hoặc là ngẫu nhiên (random). Có thể điều khiển được (controllable) hoặc không thể điều khiển được (uncontrollable). Đặc tính của hệ thống có thể chia thành: Toàn cục – mô tả tính hiệu quả của hệ thống một cách toàn diện. Cục bộ – mô tả chất lượng hoạt động của những phần tử riêng lẻ hoặc một phần của hệ thống. Những đặc tính toàn cục của những hệ thống kỹ thuật chia thành: Hiệu suất – mô tả tốc độ của hệ thống, ví dụ số lượng công việc thực hiện trong 1 khoảng thời gian. Thời gian – mô tả khía cạnh về thời gian hoạt động của hệ thống, ví dụ như thời gian giải quyết một bài toán trong hệ thống tính toán. Độ tin cậy.
Kinh tế (giá thành, giá cả) mô tả dưới dạng những chỉ số giá thành. Đặc tính khác: ví dụ khối lượng, sự tiêu thụ năng lượng, nhiệt năng, v.v. Như vậy, tham số hệ thống có thể được giải thích như là những giá trị đầu vào nào đó, còn đặc tính – giá trị đầu ra, phụ thuộc vào tham số và được xác định trong quá trình phân tích hệ thống. Tham số Đặc tính 푆- cơ cấu - Hiệu suất 퐹- hoạt động - Thời gian 푌- tải ngoài Hệ thống - Độ tin cậy - Tính kinh tế - môi trường bên ( ) 푍- Những cái khác ngoài Hình 1.2. Liên hệ giữa tham số và đặc tính Như vậy quy luật hoạt động của hệ thống có thể được thể hiện ở dạng: (푡) = (푆,퐹,푌, ,푡), – một hàm, điều kiện logic, thuật toán, bảng hoặc là mô tả bẳng lời, mà xác định quy tắc (hay luật) biến đổi giá trị vào (tham số) thành giá trị ra (đặc tính). (푡) ― vector các đặc tính, phụ thuộc vào thời điểm hiện tại t (t≥0): = , , , ,푍 1.1.7. Tiến trình Tiến trình (process) – sự thay đổi tuần tự (sequential change) của những trạng thái của hệ thống theo thời gian. Trạng thái của hệ thống được cho bởi tập hợp những giá trị các biến mô tả trạng thái đó. Hệ thống nằm trong trạng thái nào đó, nếu hệ thống đó hoàn toàn được mô tả bởi những giá trị các biến xác định trạng thái đó. Hệ thống thực hiện một bước chuyển tiếp (transition) từ một trạng thái này sang trạng thái khác nếu các biến mô tả của nó thay đổi từ những giá trị, xác định một trạng thái, sang những giá trị xác định một trạng thái khác. Nguyên nhân tạo nên một bước chuyển tiếp từ trạng thái này sang trạng thái khác, gọi là sự kiện (event).
Khái niệm ‘hệ thống’ và ‘tiến trình’ quan hệ chặt chẽ với nhau và thường được xem như những khái niệm tương đương, giống trường hợp thuật ngữ ‘trạng thái’ và ‘bước chuyển tiếp’. 1.1.8. Phân loại hệ thống và tiến trình Hệ thống và tiến trình được phân loại như sau: Dựa vào phương thức thay đổi trạng thái của những giá trị xác định trạng thái chia thành: Hệ thống (hoặc tiến trình) liên tục (continuous), đặc trưng bởi sự chuyển tiếp mịn (smooth) từ một trạng thái sang một trạng thái. Những giá trị xác định trạng thái đó có thể nhận bất kỳ một giá trị nào trong một khoảng nào đó (bao gồm cả giá trị vô cùng). Hệ thống (hoặc tiến trình) rời rạc (discrete) – đặc trưng bởi những sự chuyển tiếp đột ngột (abrupt). Những giá trị xác định trạng thái thay đổi đột ngột và được ghi thành số (rời rạc), trong khi đó số trạng thái hệ thống có thể là hữu hạn hoặc vô hạn. Dựa vào đặc tính của những tiến trình chạy trong hệ thống được chia thành: Hệ thống (hoặc tiến trình) định trước – hành vi mà có thể được xác định trước. Hệ thống (hoặc tiến trình) ngẫu nhiên – trong đó những tiến trình được phát triển phụ thuộc vào những yếu tố ngẫu nhiên. Dựa vào chế độ hoạt động chia thành: Hệ thống hoạt động trong chế độ ổn định (tĩnh - stationary) - khi mà đặc tính của hệ thống không phụ thuộc vào thời gian, nghĩa là không thay đổi [trong quá trình] thời gian hoạt động của hệ thống Hệ thống hoạt động trong chế độ không ổn định – khi mà đặc tính của hệ thống thay đổi theo thời gian, nghĩa là phụ thuộc vào thời gian hoạt động. Chế độ không ổn định có thể được gây ra bởi: o Khoảng bắt đầu công việc của hệ thống. o Tính không ổn định của các tham số hệ thống, bao gồm cả sự thay đổi tham số hệ thống theo thời gian. o Quá tải hệ thống (system overload) – khi hệ thống không làm việc khi tải ngoài đặt lên nó. 1.2. Mô hình Nếu mà cảm thấy dường như công việc đó dễ làm, thì nhất định là sẽ khó (Định lý Stockmaier) (STOCKMAYER'S THEOREM: If it looks easy, it's tough)
Mô hình (model) – đối tượng vật lý (thật) hoặc trừu tượng (giả), mô tả một cách tương xứng với hệ thống được nghiên cứu. 1.2.1. Yêu cầu cơ bản đối với mô hình Với tất cả những mô hình cần được thiết kế, có 2 yêu cầu nghịch nhau: Tính đơn giản của mô hình; Tính tương đương (cân xứng) với hệ thống được nghiên cứu. Cấp độ phức tạp (hay đơn giản) của mô hình được xác định bởi mức độ chỉ rõ từng chi tiết, mức độ này phụ thuộc vào những giả định được chấp nhận: giả định càng lớn, mức độ chi tiết càng nhỏ, vì vậy, mô hình càng đơn giản, tính tương đương với hệ thống cần nghiên cứu càng nhỏ. Tính tương đương (adequacy, cân xứng) – sự tương đối của mô hình với hệ thống ban đầu, được đặc trưng bởi mức độ gần giống tính chất của mô hình với tính chất của hệ thống được nghiên cứu. 1.2.2. Phân loại mô hình Mô hình được phân loại theo những yếu tố sau: Theo đặc tính hoạt động của hệ thống: o Định trước (deterministic) – khi mà sự hoạt động của hệ thống được mô tả bằng những giá trị định trước; o Ngẫu nhiên (hay xác suất) – khi mà sự hoạt động của hệ thống được mô tả bằng những biến ngẫu nhiên. Theo đặc tính của những tiến trình chạy trong hệ thống: o Liên tục – trong hệ thống các tiến trình chạy liên tục theo thời gian; o Rời rạc – trong hệ thống tiến trình thay đổi theo trạng thái đột đột trong những khoảng thời gian rời rạc. Theo cấp độ tin cậy của những dữ liệu đầu vào: o Những tham số được biết trước; o Những tham số không biết được trước. Theo chế độ hoạt động: o Ổn định, mà những đặc tính không thay đổi theo thời gian; o Không ổn định, mà những đặc tính thay đổi theo thời gian. Theo công dụng: o Tĩnh hay cơ cấu, được mô tả bằng thành phần và cấu trúc của hệ thống; o Động hay hoạt động, được mô tả bằng hoạt động theo thời gian. o Cơ cấu-hoạt động . Theo phương thức mô tả và thực hiện:
o Mang tính khái niệm hay nội dung – là các mô tả dùng chữ viết, lời; o Mang tính vật lý hay vật liệu – mô hình tương đương hay tương tự với nguyên thể hoặc là tiến trình hoạt động của nó giống của nguyên thiể và có cùng bản chất vật lý khác; o Mang tính toán học và trừu tượng – là mô tả hình thức với sự hỗ trợ của ngôn ngũ trừu tượng, mà nói riêng là sự dùng những liên hệ toán học dùng để mô tả hoạt động của hệ thống; o Mang tính chương trình (thuật toán, máy tính) – những chương trình máy tính, tạo điều kiện thể hiện bằng độ họa đối tượng được nghiên cứu bằng giả lập hay thể hiện đồ họa các sự phụ thuộc toán học (công thức), mà sự phụ thuộc này mô tả đối tượng cần tìm đó. Tương đương như vậy phân biệt có mô hình hóa vật lý, mô hình hóa toán học và mô hình hóa máy tính. Giữa phân loại hệ thống và mô hình không nhất thiết là tồn tại sự tương quan 1:1. Ví dụ như, những hệ thống rời rạc có thể được biểu diễn bằng những mô hình liên tục, một hệ thống định trước – bằng những mô hình ngẫu nhiên (xác suất) và ngược lại. 1.2.3. Tham số hóa mô hình Về mặt định lượng thì bất kỳ một mô hình và hệ thống tương xứng với nó được mô tả bằng tập hợp những giá trị, mà có thể chia thành ‘tham số’ và ‘đặc tính’. Các thành phần tham số và đặc tính của mô hình được xác định bởi thành phần tham số và đặc tính của hệ thống được nghiên cứu, và về lý tưởng thì chúng có thể giống nhau. Trường hợp thông thường thì chúng khác nhau. Tham số và đặc tính của mô hình được hình thành trong thuật ngữ của công cụ toán học, còn tham số và đặc tính của hệ thống được hình thành trong thuật ngữ của lĩnh vực ứng dụng. Nói chung thì phân chia tham số và đặc tính thành 2 loại: tính hệ thống và tính mô hình. Vì điều này mà xuất hiện bài toán tham số hóa mô hình, nghĩa là thiết lập sự tương quan giữa tham số và đặc tính của mô hình với của hệ thống. 1.3. Những bài toán mô hình hóa Mô hình hóa, như là một quá trình nghiên cứu các hệ thống phức tạp, thông thường giải quyết những bài toán tương quan như sau: Thiết kế (phát triển) mô hình; Phân tích đặc tính hệ thống; Tổng hợp hệ thống; Phân tích chi tiết hệ thống đã tổng hợp.
1.3.1. Phát triển mô hình Phát triển mô hình bao gồm việc chọn một công cụ toán học cụ thể để mô tả được mô hình và xây dựng mô hình hoặc tập hợp các mô hình cho ra được những khả năng [các trường hợp] có thể của các tổ chức cơ cấu-hoạt động của hệ thống. Trong quá trình phát triển mô hình thì cần thiết xác định các thành phần và danh sách các tham số và đặc tính của mô hình, và thiết lập sự liên hệ giữa tham số với đặc tính của hệ thống cần được nghiên cứu, nghĩa là thực hiện tham số hóa mô hình. 1.3.2. Phân tích đặc tính hệ thống Phân tích đặc tính của hệ thống với sự sử dụng mô hình (đã được phát triển trước đó) bao gồm việc đưa ra những tính chất và quy luật của những tiến trình chạy trong hệ thống với những trường tổ chức [cơ cấu và hoạt động] khác nhau, và chọn ra những khuyến cáo để giải bài toán cơ bản trong thiết kế hệ thống (bài toán thiết kế hệ thống đôi khi gọi là bài toán thiết kế tổng hợp hay bài toán tổng hợp). 1.3.3. Tổng hợp hệ thống Như đã đề cập ở trên, tổng hợp hệ thống là việc xác định tham số hệ thống để thỏa mãn yêu cầu về đặc tính của hệ thống. Giải quyết bài toán tổng hợp có liên quan đến việc xác định sự phụ thuộc của đặc tính hoạt động của hệ thống vào tham số, mà sự phụ thuộc này được thể hiện dưới dạng những liên hệ toán học phức tạp. Lúc đó, khả năng nhận được kết quả (có thể chấp nhận được) trong quá trình giải bài toán tổng hợp vượt ra khả năng của các phương pháp toán học tối ưu và bài toán tổng hợp nói chung về toán học dường như là không thể giải được (vì tính phức tạp và mức độ khó khăn là rất lớn khi tính đến những điểm (hay nghiệm) đặc biệt của những hệ thống thực). Để giảm tính phức tạp của bài toán tổng hợp, quá trình thiết kế được chia thành thứ tự các bước, mỗi một bước thì giải quyết những bài toán tổng hợp riêng – xác định được các tham số mà có liên hệ với những khía cạnh tổ chức riêng của hệ thống, với sự sử dụng của mô hình này hay mô hình khác. Phụ thuộc vào mục tiêu mà có thể chia những bài toán tổng hợp riêng: Tổng hợp theo cơ cấu – bao gồm việc chọn phương thức tổ chức cơ cấu của hệ thống, mà trong đó có thể thỏa mãn những yêu cầu của bài toán kỹ thuật, tổng hợp theo cơ cấu có thể chi thành 2 bước: o Tổng hợp theo các phần tử bao gồm việc xác định các yêu cầu tham số của từng phần tử riêng của hệ thống;
o Tổng hợp theo cấu trúc liên kết (topology) bao gồm việc xác định phương thức tương tác của những phần tử, nghĩa là xác định cấu trúc liên kết. Tổng hợp theo hoạt động – chọn chế độ (phương thức) hoạt động của hệ thống. Tổng hợp theo tải ngoài – xác định nhu cầu cho tham số tải ngoài, đảm bảo cho việc hoạt động của hệ thống với chất lượng được cho. Tổng hợp theo các bước tạo có thể nhận được chỉ là những lời giải tối ưu gần đúng mà ‘chất lượng’ của lời giải này được kiểm tra bằng việc phân tích chi tiết hệ thống đã tổng hợp. 1.3.4. Phân tích chi tiết hệ thống đã tổng hợp Phân tích chi tiết hệ thống đã tổng hợp được thực hiện với mục đích đánh giá chất lượng giải quyết bài toán thiết kế hệ thống và [đánh giá] các tham số hệ thống trong quá trình tổng hợp, cũng như đưa ra những khả năng tới hạn [chặn trên, chặn dưới] của hệ thống, những điểm thắt nút cổ chai trong hệ thống, v.v 1.4. Các phương pháp mô hình hóa Mọi thứ dường như không dễ dàng (Hệ quả của luật Murphy) Khi nghiên cứu những hệ thống kỹ thuật với đặc tính hoạt động rời rạc thường hay sử dụng những phương pháp mô hình hóa toán học sau: Phân tích (analytical) – (công cụ: thuyết xác suất, thuyết hàng đợi, thuyết các tiến trình ngẫu nghiên, các phương pháp tối ưu, ); Số học (numeral) – ( sử dụng các phương pháp phân tích số học để nhận được nhũng kết quả hữu hạn ở dạng số, khi mà không thể có được sự liên hệ phân tích (toán học) của đặc tính vào tham số ở dạng [công] thức rõ ràng. Thống kê hay còn gọi là mô phỏng (nghiên cứu trên máy tính, dựa vào phương pháp các phép thử thống kê (statistical test) và sử dụng các chương trình chuyên biệt và ngôn ngữ mô hình hóa: NS2, OMNeT++, OPNET (cho mạng máy tính), GPSS World, SIMULA, v.v Kết hợp các phương pháp trên. 1.4.1. Phương pháp phân tích Các phương pháp phân tích bao gồm việc xây dựng mô hình toán học ở dạng các công thức toán học, khi đó sự liên hệ cần thiết (giữa tham số và
đặc tính) được lấy từ mô hình toán học bắng việc sử dụng tuần tự các quy tắc toán học. Ưu điểm của phương pháp này là khả năng nhận được lời giải trong một dạng thức rõ ràng (ví dụ: công thức), tạo điều kiện phân tích chi tiết các tiến trình chạy trong hệ thống, trong một phạm vi rộng sự thay đổi các tham số hệ thống. Những kết quả trong dạng thức phân tích là cơ sở để chọn được khả năng tối ưu tổ chức cơ cấu-hoạt động của hệ thống trong giai đoạn tổng hợp. Khuyết điểm các phương pháp này là sử dụng chuổi các giả định trong quá trình xây dựng mô hình toán học và không thể nhận được lời giải ở dạng [công] thức rõ ràng được vì việc không tìm được lời giải (nghiệm) cho các phương trình ở dạng phân tích, hoặc do thiếu những hàm ban đầu trong các công thức tích phân. Trong những trường hợp này thường sử dụng các phương pháp số học. Phương pháp phân tích chia thành: Chính xác; Gần đúng; Heuristic. 1.4.2. Phương pháp số học Phương pháp số học dựa trên việc xây dựng chuỗi hữu hạn các phép tính (operation) trên các con số. Áp dụng các phương pháp số học dẫn đến việc thay các phép tính và biểu thức toán học bằng phép tính tương ứng trên các con số, ví dụ như thay thế tích phân bằng toán tử cộng, tổng vô cùng bằng một số hữu hạn, v.v Kết quả việc sử dụng các phương pháp số học là những bảng và đồ thị sự phụ thuộc, mở (tìm) ra tính chất của đối tượng. Các phương pháp số học là tiếp theo của các phương pháp phân tích trong những trường hợp khi mà kết quả không nhận được một cách rõ ràng bằng phân tích. 1.4.3. Phương pháp thống kê Trong những trường hợp khi mà phân tích mô hình toán học bằng phương pháp số học có thể không cho ra kết quả vì mức độ khó khăn lớn hay tính không ổn định của thuật toán làm gần đúng và làm tròn số, mô hình mô phỏng được xây dựng, mà trong đó các tiến trình chạy trong máy tính (hệ thống tính toán) được mô tả bởi chuổi các phép tính các con số, mà các con số này là thể hiện của giá trị đầu vào và ra của các phần tử tương ứng. Mô hình mô phỏng kết nối các tính chất của các phần tử riêng
lẻ thành một hệ thống thống nhất. Khi thực hiện việc tính toán, mà được sinh ra bởi mô hình mô phỏng, trên cơ sở những tính chất của các phần tử đơn lẻ, có thể xác định được tính chất của toàn hệ thống. Khi xây dựng mô hình mô phỏng thường sử dụng phương pháp thử thống kê (phương pháp Monte-Carlo). Các thủ tục xây dựng và phân tích những mô hình mô phỏng bằng phương pháp thử thống kê gọi là mô hình hóa thông kê. Mô hình hóa thống kê là quá trình nhận được các dữ liệu thống kê về tính chất của hệ thống được nghiên cứu. Ưu điểm của mô hình hóa thống kê là tính phổ quát, đảm bảo khả năng thực hiện các phân tích hệ thống ở bất kỳ mức độ phức tạp nào với bất kỳ mức độ chi tiết nào. Khuyết điểm – độ khó khăn của quá trình mô hình hóa và tính chất riêng của kết quả, không vạch ra được sự phụ thuộc [chung], mà chỉ được xác định trong những điểm riêng lẻ nào đó. Mô hình hóa thống kê thường được sử dụng để đánh giá sai số các phương pháp phân tích và số học. 1.4.4. Kết hợp các phương pháp Phân tích-số học – trong đó một phần kết quả nhận được bằng số, phần còn lại – với sự sử dụng liên hệ toán học. Mô phỏng-phân tích – là mô hình hóa mô phỏng kèm theo các phương pháp phân tích. 1.5. Thảo luận Khi đặt ra bất kỳ một môn học khoa học hoặc kỹ thuật nào, một trong những vấn đề căn bản là hình thành thuật ngữ, phục vụ cho nền tảng sau để học tập các khía cạnh lý thuyết cũng như thực hành của môn đó. Mục đích của việc hình thành cơ sở thuật ngữ là thiết lập sự tương quan giữa thuật ngữ được sử dụng với hàm nghĩa trong đặt trong nó. Câu hỏi 1: Có thể xem máy tính cá nhân như là một hệ thống, mà các phần tử của nó là block hệ thống và những thiết bị ngoài gắn với nó như màn hình, máy in và scanner hay không? Thảo luận: Khái niệm ‘hệ thống’ được sử dụng rộng rãi trong cuộc sống hàng ngày của chúng ta. Chúng ta nói ‘hệ thống kiến thức’, ‘hệ thống đánh giá’, v.v Tuy nhiên có thể để ý rằng, những thuật ngữ trên không hoàn toàn tương ứng với định nghĩa ở trên. Và mặc dù có thể cố gắng tìm ra được những phần tử trong những ‘hệ thống’ đó và sự liên kết giữa chúng, thì vẫn thấy có gì đó được chấp
nhận mang tính nhân tạo. Tình huống như vậy được gây ra là bởi trong những ví dụ như thế ‘hệ thống’ được sử dụng – có thể nói rằng – trong một ý nghĩa rộng. Trong mỗi lĩnh vực có thể đưa vào khái niệm ‘hệ thống’. Khi mô hình hóa các hệ thống kỹ thuật thì sử dụng khái niệm ‘hệ thống’ được định nghĩa như ở trên (trong tài liệu này). Vì vậy, nếu sử dụng định nghĩa hệ thống, như một tập hợp các phần tử liên hệ với nhau, thì dường như máy tính với thiết bị ngoài được xem là một hệ thống. Tuy nhiên để ý rằng ở phần thứ hai của định nghĩa hệ thống, nói rằng, các phần tử được kết nối với nhau thành một thể phải đảm bảm đạt được mục tiêu nào đó, xác định được công dụng của hệ thống. Điều này có nghĩa là, hệ thống, ngoài tổ chức cơ cấu ở dạng tập hợp các phần tử liên hệ với nhau, thì phải sở hữu thêm tổ chức hoạt động, nghĩa là trong nó phải chạy các tiến trình nào đó theo thời gian, làm thay đổi trạng thái của hệ thống. Từ điểm này suy ra rằng, một máy tính không làm việc thì không gọi là một hệ thống. Trong khi đó, nếu trong máy tính này giải quyết một bài toán nào đó, thì nó có thể được xem là một hệ thống, sở hữu tổ chức cơ cấu và chức năng. Nên nhớ thêm rằng, hệ thống thì phải sở hữu những tính chất như tính toàn vẹn tính gắn kết, tính tổ chức, tính tích hợp. Sự có mặt các tính chất này tạo điều kiện xem hệ thống như một thể hoàn chỉnh và [tạo điều kiện] áp dụng cách tiếp cận hệ thống để nghiên cứu nó. Đặc biệt tính chất cuối cùng (tính tích hợp) chứng thực rằng, không thể biết được tính chất toàn thể hệ thống trong khi phân tích chỉ các tính chất của những phần tử của nó. Nói một cách khác, hệ thống sở hữu những tính chất mà không một phần tử nào trong thành phần của hệ thống sở hữu được. Câu hỏi 2: Sự khác biệt giữa ‘tham số’ và ‘đặc tính’ của hệ thống là như thế nào? Có thể nào đặc tính là tham số và ngược lại không? Thảo luận: Ở một vài tài liệu không để ý đến việc phân biệt giữa tham số và đặc tính. Hơn nữa, lại có những giá trị vừa được gọi là tham số, vừa được gọi là đặc tính. Định nghĩa bên trên thì phân chia rõ ràng 2 lớp giá trị mô tả hệ thống: tham số và đặc tính, nghĩa là sự thay đổi tham số dẫn đến sự thay đổi đặc tính. Tuy nhiên cùng lúc đó có thể hiểu rằng ‘tham số’ và ‘đặc tính’ – những khái niệm tương đối. Điều này có thể minh chứng bằng ví dụ sau. Nếu một máy tính giải quyết một bài toán nào đó được xem như một hệ thống, một trong những phần tử của nó là bộ vi xử lý, thì hiệu suất (tốc độ) của bộ vi xử lý là tham số, sự thay đổi của nó dẫn đến sự thay đổi của giá trị như: thời gian thực hiện bài toán , mà trong trường hợp này được xem là đặc tính của hệ thống. Nếu bộ vi xử lý được xem như một hệ thống, bao gồm thiết bị số học-logic, thiết bị điều khiển, các bộ nhớ register, v.v thì tốc độ của bộ vi xử lý sẽ là đặc tính, nó phụ thuộc vào những
tham số của các thành phần trong nó. Có thể nói rằng, tham số của hệ thống chủ yếu là mô tả các phần tử và sự liên hệ giữa chúng (cả tham số cơ cấu và tham số hoạt động), còn đặc tính mô tả hệ thống một cách toàn vẹn. Tuy nhiên điều này không hoàn toàn đúng, bởi vì đặc tính có thể mô tả một hệ thống toàn vẹn (đặc tính [mang tính] toàn cục), cũng như một phần tử đơn lẻ hay hệ thống con (đặc tính [manh tính] cục bộ). Câu hỏi 3: Thuật ngữ ‘hệ số hiệu quả’ và ‘đặc tính’ có đồng nghĩa với nhau không? Thảo luận: Thật vậy, thuật ngữ ‘chỉ số hiệu quả’ và ‘đặc tính’ là khá gần nhau về khái niệm theo định nghĩa, có thể nói rằng chúng là một. Tuy vậy, giữa chúng vẫn có sự khác nhau. Thứ nhất, chỉ số hiệu quả luôn có ý nghĩa về định lượng, nghĩa là được thể hiện ở dạng đánh giá định lượng (con số), còn đặc tính có thể mang tính chất lượng. Ví dụ, để mô tả mạng máy tính thường sử dụng những đặc tính, như là tính mở , tính quy mô, tính linh hoạt, bảo mật thông tin, v.v mà việc đưa định lượng của chúng là tùy điều kiện, hoặc là hoàn toàn không thể. Thứ hai là, tập hợp các chỉ số hiệu quả khi nghiên cứu một hệ thống nào đó phụ thuộc vào tính năng của nó, trong khi đó đặc tính thì mô tả toàn bộ tập hợp tính chất của hệ thống. Trong khi đó thì, có thể là một vài đặc tính là không đáng kể. Ví dụ: một máy tính công dụng để sử dụng trong không gian vũ trụ hoặc khoang máy bay thì chỉ số hiệu quả quan trọng của nó là khối lượng và độ tiêu thụ năng lượng. Nếu một máy tính công dụng cho việc giải quyết những bài toán mô hình hóa, tối ưu phức tạp nào đó, mà yêu cầu cần hiệu suất tính toán thì những hệ số hiệu quả thực tế của nó là hiệu suất, thời gian phản ứng, còn khối lượng và độ tiêu thụ năng lượng có thể là không có ý nghĩa gì đặc biệt. Câu hỏi 4: Có bao nhiêu tiêu chí hiệu quả được sử dụng khi tổng hợp hệ thống tối ưu? Thảo luận: Để mô tả hệ thống thường sử dụng các chỉ số hiệu quả đối nghịch với nhau. Sự đối nghịch này nằm ở chỗ, khi cố gắng cải thiện một hoặc vài chỉ số hiệu quả nào đó theo sự thay đổi tham số tổ chức cơ cấu-hoạt động của hệ thống thường dẫn đến làm xấu đi những chỉ số hiệu quả còn lại.Ví dụ, nếu chúng ta muốn xây dựng một hệ thống tính toán với hiệu suất và độ tin cậy cao, thì rõ ràng là giá thành của nó rất lớn. Ngược lại, nếu mục đích xây dựng hệ thống tính toán rẻ hơn, thì hiệu suất và tính tin cậy rõ ràng là ở một cấp độ chừng mực nào đó. Vậy thì để giải quyết bài toán tổng hợp tối ưu tốt nhất là chỉ một tiêu chí hiệu quả, nghĩa là chỉ có một hàm mục tiêu (objective function), mà hàm này tạo điều kiện chọn từ tập hợp các khả năng xây dựng hệ thống tốt nhất, nói chính xác hơn, là
một khả năng tối ưu, mà khi đó tiêu chí hiệu quả nhận giá trị lớn nhất (tiêu chí hiệu quả thuận) hoặc là nhỏ nhất (tiêu chí hiệu quả nghịch). Tồn tại một vài cách xây dựng tiêu chí hiệu quả khi có tập hợp các hệ số hiệu quả mà có thể được sử dụng khi giải những bài toán tổng hợp tối ưu. Đó là, trước hết cái gọi là những tiêu chí hiệu quả ghép (composite) [cộng ghép (addictive) và nhân (multiplicative)] là kết nối nhiều chỉ số hiệu quả. Tuy nhiên trong thực hành phổ biến hơn là tiêu chí hiệu quả với những giới hạn, mà được xây dựng theo nguyên lý sau: từ tập hợp các chỉ số hiệu quả thì một [chỉ số] là được chọn làm tiêu chí hiệu quả, còn những chỉ số khác thì bị giới hạn lại. Để ý rằng, dạng thức tiêu chí hiệu quả phụ thuộc vào tính năng của hệ thống. Nếu hệ thống có công dụng cho việc đảm bảo độ tin cậy cao thì trong các tiêu chí hiệu quả có thể sử dụng một trong các chỉ số độ tin cậy. Nếu một hệ thống phải có hiệu suất cao thì trong tiêu chí hiệu quả sử dụng hiệu suất của hệ thống [làm tiêu chí hiệu quả]. Có thể có tình huống khi mà yêu cầu cho hệ thống đó là gồm cả hiệu suất gồm cả độ tin cậy. Khi đó sử dụng tiêu chí hiệu quả ghép làm như tiêu chí hiệu quả, kết hợp cả 2 chỉ số hiệu quả: hiệu suất và độ tin cậy. Có thể kết luận rằng, cụm từ kiểu như ‘hệ thống tối ưu hơn’ hay ‘hệ thống kém tối ưu hơn’ là không đúng, bởi vì hệ thống tối ưu chỉ tồn tại một phiên bản duy nhất. Đó là hệ thống đảm bảo hàm cực đại hoặc cực tiểu, được cho bởi tiêu chí hiệu quả. Câu hỏi 5: Có thể nghiên cứu một hệ thống làm việc trong chế độ không ổn định, bằng những phương pháp mà được phát triển cho chế độ ổn định không? Thảo luận: Như đã nói, chế độ làm việc không ổn định được phát sinh từ 3 yếu tố: [giai đoạn] bắt đầu làm việc của hệ thống, tải ngoài không ổn định và việc quá tải [trong]. Phần lớn các nghiên cứu những hệ thống kỹ thuật thường được thực hiện trong giả định là, chế độ chuyển tiếp đã hoàn thành, và trong hệ thống không có quá tải. Trong trường hợp ngược lại thì sử dụng những phương pháp nghiên cứu đặc biệt, được phát triển để [nghiên cứu] cho chế độ chuyển tiếp và chế độ quá tải. Nhiều hệ thống thực mà trong đó có hệ thống kỹ thuật làm việc trong chế độ khhông ổn định, được phát sinh bởi sự không ổn định của tải ngoài. Để nghiên cứu những hệ thống như vậy bằng những phương pháp mà được phát triển cho chế độ ổn định, có thể sử dụng những cách tiếp cận khác nhau mà cách tiếp cận cơ bản trong số đó là như sau. Thứ nhất, có thể thử phân chia những khoảng thời gian liên tục, mà trong những khoảng đó tải ngoài không thay đổi, nghĩa là ổn định, hoặc là sự thay đổi của tải ngoài không lớn, có thể bỏ qua. Thứ hai, nghiên
cứu – bằng những phương pháp mà được phát triển cho chế độ ổn định – có thể thực hiện trong tính toán khi tải ngoài đạt lớn nhất hoặc trung bình. Câu hỏi 6: Bằng phương pháp nào để đạt được sự thỏa thuận giữa sự đơn giản và sự tương đương của mô hình? Thảo luận: Đạt được sự thỏa thuận giữa tính đơn giản của mô hình và sự tương đương của nó với hệ thống được nghiên cứu là một trong những vấn đề phức tạp nhất của lý thuyết mô hình hóa. Từ một khía cạnh là mong muốn có được mô hình với mức độ chi tiết lớn nhất thể hiện được tất cả các điểm đặc biệt của tổ chức cơ cấu-hoạt động. Thì từ một khía cạnh khác, mô hình đó có thể là phức tạp đến nỗi mà nghiên cứu nó là không thể hoặc là cần tài nguyên nguyên liệu và thời gian rất lớn. Cũng chú ý rằng, để nghiên cứu những mô hình phức tạp thường thì không thể phát triển những phương pháp toán học chính xác, còn việc áp dụng những phương pháp gần đúng [cồng kềnh] dẫn đến sai số lớn trong kết quả. Có một điểm quan trọng nữa trong khi phát triển mô hình, đó là tính chính xác trong diễn tả của dữ liệu đầu vào, đặc biệt liên hệ với tham số tải ngoài. Nếu xác suất diễn tả của tham số tải ngoài hoặc tham số cơ cấu-hoạt động mà lớn, thì rõ ràng là, việc xây dựng mô hình chính xác là không có ý nghĩa. Vì vậy, sự chọn lựa mức độ chi tiết của mô hình được phát triển phụ thuộc vào nhiều yếu tố và ảnh hưởng đáng kể đến độ xác thực của kết quả nhận được trong quá trình mô hình hóa. Câu hỏi 7:Tham số hóa mô hình trong quá trình nghiên cứu hệ thống thực có ý nghĩa gì? Thảo luận: Giai đoạn tham số hóa mô hình trong quá trình nghiên cứu hệ thống thực có ý nghĩa to lớn trong việc nhận được kết quả. Trong giai đoạn này thật tế nền tảng của tính tương đương với hệ thống được nghiên cứu được đặt ra, bởi vì chính trong quá trình tham số hóa các giá trị của những tham số đầu vào được xác định, mà những tham số này được sử dụng trong mô hình và đảm bảo độ tin cậy của kết quả thu được. Lỗi mà do việc tham số hóa trong không thành công là không thể được bù đắp ngay cả sử dụng mô hình siêu chính xác (siêu tương đương) và những phương pháp tính toán chính xác. Hơn nữa, lỗi do việc tham số hóa có thể tăng lên nhiều lần và dẫn đến việc nhận được những giá trị của các đặc tính được nghiên cứu là tuyệt đối không đúng. Vì vậy để ý rằng, trong giai đoạn tham số hóa thì thiết lập sự tương đương không những giữa các giá trị tham số và đặc tính của hệ thống và mô hình, mà còn sự tương đương về thuật ngữ giữa khái niệm đã cho trong những thuật ngữ của lĩnh vực ứng dụng cụ thể và các phần tử của hệ thống nghiên cứu với những
khái niệm được sử dụng trong mô toán học và các phần tử trong mô hình toán học tương ứng. Ví dụ trong kỹ thuật tính toán khi mô tả máy tính có sử dụng khái niệm và những phần tử, như là bài toán, chưưng trình, dữ liệu, bộ vi xử lý, bộ nhớ,v.v Giả thuyết rằng trong mô hình toán học về máy tính sử dụng [những khái niệm như] tiến trình ngẫu nhiên, để mô tả chúng trong thuyết các tiến trình ngẫu nhiên sử dụng những thuật ngữ và các phần tử như trạng thái, sự chuyển tiếp, sự kiện, đồ thị các chuyển tiếp, ma trận xác suất chuyển tiếp, v.v Làm sáng tỏ và thiết lập một cách hợp lý sự tương ứng giữa các khái niệm với các phần tử đã cho là một trong những bài toán tham số hóa. Thực tế thì, tham số hóa – đó là giai đoạn trung gian thiết lập sự tương ứng 1:1 giữa mô hình khái niệm và mô hình toán học. Câu hỏi 8: Phân tích chi tiết hệ thống đã được thiết kế cẩn thiết đến mức như thế nào? Thảo luận: Cần thiết đến mức độ quan trọng việc trong việc nhận được đồ án chất lượng của hệ thống được tổng hợp. Bài toán tổng hợp thường được giải với sự sử dụng nhưng mô hình tương đối đơn giản, mà [những mô hình này] tạo điều kiện nhận được lời giải ở dạng lời giải phân tích rõ ràng. Khi này sai số của mô hình, và của những phương pháp tính toán những đặc tính của hệ thống trong trường hợp sử dụng những công thức toán học gần đúng có thể mang đến sự khác biệt to lớn giữa những giá trị tính toán và giá trị thực của những tham số được tối ưu. Liên hệ với điều này nên xuất hiện sự cần thiết phải kiểm tra và làm chính xác những giá trị tham số về tổ chức cơ cấu-hoạt động tìm được, và với điều này, rất là tự nhiên, cần thiết sử dụng những mô hình tương đương nhất, tạo điều kiện nhận được kết quả trong mức độ lớn nhất sự tương đương với thực tế. Trong những mô hình như thế thường nhận những mô hình mô phỏng mà có thể được xây dựng tương ứng, mà [những mô hình này] được xây dựng với sự làm gần đúng đến mức cao nhất với hệ thống thực khi tính đến mức độ chi tiết lớn hơn so với mô hình phân tích. Ngoài ra trong quá trình phân tích chi tiết hệ thống được tổng hợp phải đưa ra được những khả năng giới hạn của hệ thống, điểm nút chai trong hệ thống, và cũng như xác định được những yêu cầu đã cho được thực hiện tốt như thế nào đối với chất lượng hoạt động của hệ thống được thiết kế. Câu hỏi 9: Nếu như đã nói, phương pháp thống kê (mô phỏng) nghiên cứu những hệ thống phức tạp là phổ quát, thì việc sử dụng phương pháp phân tích có tính thực tế là bao nhiêu?
Thảo luận: Thật sự là mô hình hóa mô phỏng có thể được xem như là một công cụ phổ quát nghiên cứu các hệ thống phức tạp với đặc tính hoạt động ngẫu nhiên, tạo điều kiện thực hiện việc phân tích hiệu quả hoạt động của hệ thống với bất kỳ mức độ phức tạp với bất kỳ mức độ chi tiết nào.Yếu tố duy nhất, giới hạn việc sử dụng mô hình hóa mô phỏng là hiệu suất của máy tính để chạy các thực hiện mô phỏng. Hệ thống nghiên cứu càng phức tạp, trong đó càng nhiều các phần tử và sự kết nối, thì càng cần máy tính mạnh hơn nữa, có thể sử dụng đến siêu máy tính. Lúc này hiệu suất máy tính không chỉ đơn giản tốc độ xử lý của bộ vi xử lý, mà còn dung lượng bộ nhớ, và trong những trường hợp khác, yêu cầu cao hơn về hiệu suất cũng như dung lượng bộ nhớ ngoài. Cùng lúc đó, mô hình mô phỏng cũng mang theo những khuyết điểm, giới hạn việc áp dụng nó. Đặc tính riêng về kết quả là một trong những số đó, điều này không thể tìm ra được sự phụ thuộc của đặc tính hoạt động hệ thống vào tham số tổ chức cơ cấu-hoạt động của nó, mà chỉ xác định nó trong một vài điểm riêng. Ngoài ra, mô hình mô phỏng là công cụ hiệu quả trong quá trình thiết kế chỉ trong trường hợp là nếu cần thiết so sánh một vài trường hợp xây dựng hệ thống và chọn cái tốt nhất trong số đó. Tuy nhiên trên thực tế thì giải quyết bài toán tổng hợp tối ưu các hệ thống phức tạp (hệ thống quy mô lớn, đặc trưng bởi số lượng lớn các tham số cơ cấu-hoạt động và tải ngoài) là gần như không thể. Vì vậy, các phương pháp mô mình hóa phân tích được áp dụng trong những trường hợp sau: Để thực hiện việc báo cáo đánh giá ở giai đoạn phân tích và thiết kế ban đầu, không yêu cầu tính chính xác cao của kết quả tìm được. Để nghiên cứu trong một phạm vi rộng sự thay đổi các tham số tính chất và quy luật được mang theo của hệ thống được nghiên cứu ; kết quả nhận được có thể làm cơ sở để đua ra những khuyến cáo cho việc thiết kế hệ thống. Để giải quyết những bài toán tổng hợp tối ưu khi thiết kế những hệ thống mới. Câu hỏi 10: Trong một vài tài liệu thay vì sử dụng khái niệm ‘hệ thống tối ưu’ thì sử dụng khái niệm ‘hệ thống hợp lý’. Có sự tương quan như thế nào giữa 2 khái niệm này? Thảo luận: ‘Hệ thống tối ưu’ có nghĩa là, những giá trị tham số của tổ chức cơ cấu-hoạt động được xác định trong quá trình tối ưu hóa toán học và chúng là tối ưu, có nghĩa là đảm bảo một cực đại (hoặc cực tiểu) của tiêu chí hiệu quả được chọn. Trên thực tế thì không thể nào xây dựng hệ thống như vậy
với những giá trị tham số như vậy, mà điều này có thế được gây ra từ một vài nguyên nhân, trong đó có tính chất rời rạc của các tham số được tối ưu. Ví dụ, trong quá trình tổng hợp một mạng truyền dữ liệu nào đó, nhận được các giá trị tối ưu về độ thông qua (throughput) của 3 kênh truyền là: 428Kbit/s, 764 kbit/s, 931kbit/s. Giả sử rằng, kênh truyền thực tế có độ thông qua là 256kbit/s, 512 kbit/s và 1024 kbit/s. Rõ ràng rằng, lời giải cuối cùng của bài toán sẽ nhận các giá trị là 256kbit/s, 512 kbit/s và 1024 kbit/s. Bởi vì các giá trị này khác với các giá trị tối ưu, hệ thống được thiết kế không thể gọi là hệ thống tối ưu. Những hệ thống như vậy thường được gọi là ‘hợp lý’ (rational), ý nói rằng, tham số của nó gần với, chứ không phỉa là bằng với giá trị tối ưu. Đôi khi ‘hệ thống hợp lý’ được hiểu như là một trường hợp nào đó trong số những khả năng được chọn trên cơ sở phân tích đặc tính hoạt động. Như vậy, rõ ràng trong trường hợp này, không liên quan gì đến tối ưu. Câu hỏi 11: Có gì khác nữa giữa khái niệm tổng hợp (synthesis) và khái niệm thiết kế (design, projectus)? Thảo luận: Những khái niệm này khá là gần nhau về ý nghĩa và thường được sử dụng như là đồng nghĩa. Cùng lúc đó giữa chúng tồn tại một số điểm khác biệt, ít nhất là từ xuất xứ từ tiếng nước ngoài. Thuật ngữ ‘tổng hợp’ (tiếng La tinh: synthesis) – có nghĩa là kết nối những phần tử thành thể thống nhất – hệ thống và không tách rời với thuật ngữ ‘phân tích’. Thuật ngữ ‘thiết kế’(tiếng La tinh: projectus, tiếng Anh: design) có nghĩa là quá trình tạo một đề án – nguyên mẫu (propotype) của hệ thống mới. Khi thiết kế những hệ thống kỹ thuật bài toán cơ bản bao gồm việc tạo ra một dự án (project, kế hoạch), trên cơ sở đó một hệ thống thực được xây dựng, còn trong quá trình tổng hợp – chỉ là xác định tham số và thành phần của hệ thống được thiết kế. Như vậy, tổng hợp có thể được xem như một trong những giai đoạn (nhiều lúc có thể được xem là cơ bản) trong thiết kế hệ thống thực. Cũng có thể xem ‘tổng hợp’ – khái niệm toán học thường được sử dụng trong cụm từ ‘tổng hợp tối ưu’, còn ‘thiết kế’ – khái niệm mang tính kỹ thuật hơn và không phải luôn luôn cần sử dụng các phương pháp toán học nào để xây dựng hệ thống. Nói cách khác, tổng hợp những hệ thống kỹ thuật được thực hiện với sự sử dụng các phương pháp mô hình hóa toán học, cùng lúc đó
thiết kế được xem như, trước hết là, sử dụng những các lời giải mang tính kỹ sư-kỹ thuật, mà sự chứng minh (làm sáng tỏ) những lời giải đó có thể được thực hiện bởi những tính toán toán học.
2. Cơ bản về thuyết xác suất Chúa không chơi trò súc sắc (Albert Einstein) Mô hình hóa toán học những hệ thống rời rạc với đặc điểm hoạt động ngẫu nhiên có yêu cầu sử dụng mô hình hàng đợi, được mô tả bởi công cụ thuyết xác suất. Chương này xem xét những điểm cơ bản của thuyết xác suất, kiến thức của nó là cần thiết để hiểu và nắm vững những tài liệu ở những phần sau, liên quan đến việc và tính toán một cách đúng đắn những mô hình xác suất, cũng như phân tích ý nghĩa của kết quả nhận được. 2.1. Khái niệm, định nghĩa 1.1.1. Sự kiện, xác suất Nếu có sự việc khó chịu nào đó có thể xảy ra, nó sẽ xảy ra (Luật Murphy) Sự kiện – bất kỳ việc nào mà trong kết quả thực nghiệm là có thể xảy ra hoặc là không xảy ra. Xác suất (Probability) của sự kiện là thước đo mang tính số lượng mức độ khả năng [xuất hiện] khách quan của sự kiện đó. Giả sử rằng có một thực nghiệm hoặc một hiện tượng nào đó, phụ thuộc vào việc xảy ra hoặc không xảy ra của nó gọi là một sự kiện A. Với điều kiện thực nghiệm được thực hiện nhiều lần giống nhau và không phụ thuộc nhau, thì xác suất của sự kiện A được tính như sau: 푃( ) = , 푛 Trong đó, n – tổng số lượng kết quả không phụ thuộc, m – số lượng kết quả xuất hiện sự kiện A. Xác suất nhận giá trị từ 0 đến 1. Sự kiện, mà xác suất của nó bằng 0, gọi là không thể. Sự kiện mà xác suất của nó bằng 1 gọi là xác thực (chắc chắn, tin cậy). Một vài sự kiện có thể tạo thành nhóm các sự kiện toàn vẹn, nếu trong kết quả của thực nghiệm chắc chắn phải xuất hiện một trong số đó. Một vài sự kiện gọi là không kết hợp trong thực nghiệm đó, nếu không có việc 2 sự kiện nào trong nhóm đó xuất hiện cùng lúc. Vài sự kiện gọi là có khả năng bằng nhau trong thực nghiệm đó, nếu không một sự kiện nào trong số đó là có khả năng [xuất hiện] hơn sự kiện khác. Những sự kiện gọi là không phụ thuộc lẫn nhau, nếu sự xuất hiện của một trong số đó là không phụ thuộc vào những sự kiện đã xảy ra trước đó. 2.1.1. Biến ngẫu nhiên
Biến ngẫu nhiên (random variable) là biến mà có thể nhận giá trị này hay giá trị khác, mà không biết trước. Biến ngẫu nhiên có thể là có 2 loại: Rời rạc, nhận chỉ những giá trị riêng biệt với nhau, giá trị của chúng có thể được đánh số. Ví dụ: Số bài toán được thực hiện bởi máy tính trong một ngày, số lượng truy cập bộ nhớ ngoài trong quá trình giải bài toán, số lượng thông báo được truyền trong mạng máy tính trong một khoảng thời gian. Liên tục có thể nhận bất kỳ giá trị nào trong một khoảng nào đó. Ví dụ: Những khoảng thời gian giữa những thời điểm đến của những yêu cầu giải quyết bài toán, hoặc là giữa những thời điểm hình thành thông báo được truyền trong mạng truyền thông. Thỉnh thoảng các biến ngẫu nhiên có bản chất rời rạc, được xem như liên tục. Sự thay thế như vậy trong tình huống mà biến ngẫu nhiên nhận tập hợp lớn các giá trị không khác nhau nhiều, và rằng sự thay thế biến ngẫu nhiên rời rạc bằng giá trị liên tục thực tế là không ảnh hưởng đến kết quả tính toán. Ví dụ, thời gian truyền packet trên kênh truyền trong mạng máy tính được xác định bằng tỷ lệ giữa chiều dài packet với độ thông qua (throughput) của kênh truyền, là biến ngẫu nhiên rời rạc, thường được xem như biến ngẫu nhiên liên tục, mà giá trị này thay đổi trong khaỏng từ 0 đến một giá trị giới hạn nào đó, xác định bởi giá trị chiều dài packet lớn nhất. Biến ngẫu nhiên thường được ký hiệu bằng chữ cái lớn, còn những giá trị khả năng nhận được – chữ nhỏ tương ứng. Ví dụ, biến ngẫu nhiên X – số lượng truy cập đến ổ cứng trong quá trị giải bài toán trong máy tính – có thể nhận những giá trị 1 = 0, 2 = 1, 3 = 2, 2.2. Các luật phân bố các biến ngẫu nhiên Bất kỳ công việc cũng đòi hỏi thời gian lớn hơn là bạn nghĩ (Hệ quả của luật Murphy) Mô tả toán học của biến ngẫu nhiên được cho bằng luật phân bố, thiết lập sự tương ứng giữa giá trị và xác suất xuất hiện của chúng. Xét biến ngẫu nhiên rời rạc X, nhận những giá trị 1, 2, 3, 푛. Giá trị X có thể nhận mỗi một giá trị nào trong số này với xác suất nào đó. Ký hiệu 푖(푖 = 1,푛 ) mà xác suất mà biến ngẫu nhiên X nhận giá trị 푖: 푖 = 푃( = 푖). Nếu trong kết quả thực nghiệm giá trị X nhận chỉ một trong số những giá trị này, thì chúng ta có một nhóm toàn vẹn các sự kiện không kết hợp và tổng các xác suất các biến ngẫu nhiên rời rạc bằng một:
푛 푖 = 1. 푖=1 Xác suất tổng bằng cách nào đó có thể được phân bố bởi những giá trị riêng biệt. Biến ngẫu nhiên hoàn toàn được mô tả bởi từ cái nhìn xác suất, nếu chúng ta cho nó một phân bố, nghĩa là thiết lập cái gọi là luật phân bố. Luật phân bố các biến ngẫu nhiên là bất cứ sự quan hệ , thiết lập một liên hệ giữa biến ngẫu nhiên được nhận và xác suất tương ứng của chúng. 2.3. Luật phân bố các biến ngẫu nhiên rời rạc Luật phân bố biến ngẫu nhiên rời rạc X (luật phân bố rời rạc) nhận những giá trị 1, 2, 3, 푛, có thể được cho bởi những phương thức sau: Phân tích: ở dạng công thức toán học, thể hiện sự phụ thuộc của xác suất vào biến ngẫu nhiên: 푖 = ( 푖) (i=1,푛); Bảng: ở dạng chuỗi phân bố biến ngẫu nhiên, trong đó liệt kê những giá trị có thể của biến ngẫu nhiên với xác suất tương ứng: Giá trị của biến 1 2 푛 ngẫu nhiên Xác suất P 1 2 푛 Đồ thị: ở dạng phân bố đa giác, trong đó trục hoành là những giá trị có thể của biến ngẫu nhiên, còn trục tung là xác suất của những giá trị này. Biểu diễn đồ thị của luật phân bố các biến ngẫu nhiên rời rạc dễ nhìn và tạo điều kiện đánh giá chúng gần với luật [phân bố] nào đó. 3 2 푛 1 1 2 3 푛 Hình 2.1. Đa giác phân bố 2.4. Luật phân bố các biến ngẫu nhiên liên tục Với các biến ngẫu nhiên liên tục không thể cho luật phân bố ở dạng mà được cho giống như biến ngẫu nhiên rời rạc, vì các biến ngẫu nhiên liên tục có tập hợp
voo cùng các giá trị có thể, làm đầy một khoảng nào đó và xác suất xuất hiện một giá trị cụ thể nào đó là bằng không. Vì điều này, để mô tả các biến ngẫu nhiên liên tục sử dụng phương pháp thiết lập sự tương ứng khác giữa giá trị của biến ngẫu nhiên với xác suất xuất hiện của chúng, ở dạng hàm phân bố xác suất. Hàm phân bố xác suất (hay đơn giản gọi là hàm phân bố 퐹( ) biến ngẫu nhiên X là xác suất mà biến ngẫu nhiên X nhận giá trị nhỏ hơn một giá trị cho trước x nào đó: 퐹( ) = 푃( 푖, thì 퐹( 푗) ≥ 퐹( 푖); 퐹( ―∞) = 0; 퐹( +∞) = 1. Xác suất mà biến ngẫu nhiên nhận giá trị trong khoảng (a,b) nào đó được xác định bởi hàm phân bố:
푃( < < ) = 퐹( ) ―퐹( ). Hàm phân bố F(x) là đặc trưng phổ quát của biến ngẫu nhiên và tồn tại vừa cho các giá trị liên tục và giá trị rời rạc. Hàm phân bố biến ngẫu nhiên rời rạc X, mà nhận các giá trị 1, 2, 3, 푖, được xác định: ―1 퐹( ) = 푃( < ) = ∑푖=1 푖, trong đó 푖 – xác suất mà biến ngẫu nhiên X nhận giá trị 푖. Trong thực tế, thay vì sử dụng hàm phân bố thường hay sử dụng phương thức biểu diễn hàm phân bố biến ngẫu nhiên liên tục ở dạng mật độ phân bố xác suất (probability distribution density), mà khác với hàm phân bố ở chổ là có tính trực quan cao và tạo điều kiện nhận được sự biểu diễn gần với một dạng phân bố nào đấy với những phân bố lý thuyết đã biết trước đây. Mật độ phân bố xác suất f(x) được xác định bởi đạo hàm của hảm phân bố F(x) theo x: 퐹( ) ( ) = 퐹′( ) = . Mật độ phân bố biến ngẫu nhiên liên tục X cũng được biểu diễn ở dạng: Phân tích ở dạng một biều thức toán học y=f(x); Đồ thị ở dạng mà hàm (đồ thị) biểu diễn sự phụ thuộc y=f(x) (H. 2.3, a), hoặc ở dạng biểu đồ thanh mật độ phân bố. f(x) f(x) 0 X 0 1 2 3 X Hình 2.3. Đồ thị (a) và biểu đồ thanh mật độ phân bố Tính chất của mật độ phân bố: Là một hàm không âm: f(x)≥0; +∞ ( ) = 1. ―∞
Liên hệ giữa F(x) và f(x): 퐹 = . (2.2) ( ) ∫―∞ ( ) Khi đó, xác suất mà biến ngẫu nhiên nhận giá trị trong khoảng (a,b) nào đó được xác định thông qua mật độ phân bố: 푃 = 퐹 ―퐹 = ― . ( < < ) ( ) ( ) ∫―∞ ( ) ∫―∞ ( ) Như vậy luật phân bố các biến ngẫu nhiên liên tục có thể được cho dưới dạng: Hàm phân bố F(x) biến ngẫu nhiên X, cũng được gọi là luật phân bố tích phân; Mật độ phân bố f(x) biến ngẫu nhiên X, cũng được gọi là luật phân bố vi phân. 2.5. Các đặc tính định lượng các biến ngẫu nhiên Ngay cả một thực hành nhỏ cũng có một lý thuyết lớn (Luật Buker) Những đặc tính định lượng tạo điều kiện diễn tả trong hình thức ngắn gọn những điểm đặc biệt đáng kể của phân bố biến ngẫu nhiên, ví dụ: Giá trị trung bình, mà xung quanh quanh nó tập hợp những giá trị có thể của biến ngẫu nhiên; Cấp độ phân tán của những giá trị xung quanh giá trị trung bình; Tính không đối xứng (hay tính lệch) của mật độ phân bố; Tính dốc (tính nhọn của đỉnh) của mật độ phân bố. Trong thuyết xác suất thường sử dụng những đặc tính định lượng khác nhau, có những ý nghĩa khác nhau và lĩnh vực áp dụng khác nhau. Trong số đó, trên thực tế, thường sử dụng nhất là thời điểm (moment) ban đầu và thời điểm trung tâm ở những cấp độ khác nhau, mỗi trong số đó mô tả một tính chất nào đó của phân bố. Thời điểm ban đầu được xem như tương đối so với gốc tọa độ, còn thời điểm trung tâm – tương đối so với giá trị trung bình (mong đợi toán học), nghĩa là trung tâm phân bố. Nói chung, để mô tả biến ngẫu nhiên thường sử dụng tập hợp vô cùng các thời điểm ban đầu và thời điểm trung tâm. Giữa các thời điểm định lượng và luật phân bố biến ngẫu nhiên tồn tại một sự tương ứng, có nghĩa là, khi biết luật phân bố có thể tính được bất cứ thời điểm nào, số lượng của chúng là vô cùng. Cùng lúc đó, khi biết một số lượng nhất định thời điểm ban đầu và thời điểm trung tâm, thì có thể bằng cách làm xấp xỉ có thể đạt được luật phân bố biến ngẫu nhiên ở
dạng hàm hoặc mật độ phân bố, trong khi đó, số lượng thời điểm càng lớn thì sự xấp xỉ càng chính xác. Trong thực tế thường sử dụng giới hạn một vài thời điểm ban đầu và thời điểm trung tâm đầu tiên, được xem như đủ tin cậy để nhận được kết quả đúng. 2.5.1. Thời điểm ban đầu Giả thuyết rằng, biến ngẫu nhiên X được mô tả bởi xác suất xuất hiện 1, 2, , 푛 các giá trị 1, 2, 3, 푛, nếu X – giá trị rời rạc, và bởi mật độ phân bố f(x) ∈ ( ― ∞, + ∞), nếu X – giá trị liên tục. Thời điểm ban đầu 훼푠[ ] cấp độ s biến ngẫu nhiên X được xác định như sau (푠 = 1,2, ): 푛 푠 푖 푖 –đố푖 푣ớ푖 푖ế푛 푛 ẫ 푛ℎ푖ê푛 ờ푖 ạ 푖=1 훼푠[ ] = +∞ 푠 ( ) ― đố푖 푣ớ푖 푖ế푛 푛 ẫ 푛ℎ푖ê푛 푙푖ê푛 푡ụ ―∞ Thời điểm ban đầu đầu tiên 훼1[ ] biến ngẫu nhiên X: 푛 푖 푖 –đố푖 푣ớ푖 푖ế푛 푛 ẫ 푛ℎ푖ê푛 ờ푖 ạ 푖=1 훼1[ ] = +∞ ( ) ― đố푖 푣ớ푖 푖ế푛 푛 ẫ 푛ℎ푖ê푛 푙푖ê푛 푡ụ ―∞ Gọi là mong đợi toán học, hoặc là giá trị trung bình của biến ngẫu nhiên và được ký hiệu [ ] = 훼1[ ]. Mong đợi toán học đặc trưng cho vị trí của biến ngẫu nhiên trên trục số, nghĩa là chỉ ra một giá trị trung bình theo xác suất (không nhầm với trung bình theo số học), mà chung quanh nó được nhóm lại tất cả các giá trị có thể của biến ngẫu nhiên. Thời điểm ban đầu thứ hai 훼2[ ] biến ngẫu nhiên X đặc trưng độ phân tán (dispersion), nghĩa là sự tản mát các biến ngẫu nhiên tương đối so với gốc tọa độ và có chiều đo (dimension) là bình phương của biến ngẫu nhiên. 2.5.2. Thời điểm trung tâm Thời điểm trung tâm 훽푠[ ] cấp độ s biến ngẫu nhiên X được xác định như sau (푠 = 1,2, ): 푛 푠 ( 푖 ― [ ]) 푖 –đố푖 푣ớ푖 푖ế푛 푛 ẫ 푛ℎ푖ê푛 ờ푖 ạ 푖=1 훽푠[ ] = +∞ ( ― [ ])푠 ( ) ― đố푖 푣ớ푖 푖ế푛 푛 ẫ 푛ℎ푖ê푛 푙푖ê푛 푡ụ ―∞
Hiệu của biến ngẫu nhiên và mong đợi toán học ( ― [ ]) là độ lệch của biến ngẫu nhiên với mong đợi toán học và gọi là biến ngẫu nhiên trung tâm. Khi đó thời điểm trung tâm cấp độ s biến ngẫu nhiên X có thể đuợc xác định như là mong đợi toán học cấp độ s của biến ngẫu nhiên trung tâm tương ứng: 푠 훽푠[ ] = [( ― [ ]) ]. Bất kỳ biến ngẫu nhiên nào thì thời điểm trung tâm cấp bậc thứ nhất đều bằng không, vì mong đợi toán học của biến ngẫu nhiên trung tâm là bằng không. Thời điểm trung tâm thứ hai được gọi là [độ] phân tán biến ngẫu nhiên và được ký hiệu là D[X]: [ ] = 훽2[ ]. Độ phân tán được tính theo công thức: 푛 2 ( 푖 ― [ ]) 푖 –đố푖 푣ớ푖 푖ế푛 푛 ẫ 푛ℎ푖ê푛 ờ푖 ạ 푖=1 [ ] = +∞ ( ― [ ])2 ( ) ― đố푖 푣ớ푖 푖ế푛 푛 ẫ 푛ℎ푖ê푛 푙푖ê푛 푡ụ ―∞ Có thể chứng minh rằng độ phân tán và thời điểm ban đấu thứ hai có liên hệ: 2 [ ] = 훼2[ ] ― ( [ ]) . (2.3) Độ phân tán biến ngẫu nhiên, cũng như thời điểm ban đầu thứ hai đặc trưng cho độ tản mát các giá trị của biến ngẫu nhiên, nhưng là khác với thời điểm ban đầu thứ hai, là tương đối với mong đợi toán học, và có chiều đo (dimension) là bình phương của biến ngẫu nhiên. Khi giải nhiều bài toán khác nhau để thuận tiện thì hay dùng một đặc tính độ tản mát, mà chiều đo của nó trung với chiều đo của biến ngẫu nhiên. Đặc tính này gọi là độ lệch trung bình bình phương (standard deviation) 휎[ ], được tình bằng căn bậc hai của độ phân tán: 휎[ ] = [ ] Một đặc trưng tản mát biến ngẫu nhiên mà không có chiều đo, được xác định trong vùng giá trị dương, thường dùng là hệ số biến thiên 휗[ ], được xác định bằng tỷ lệ giữa độ lệch trung bình bình phương với mong đợi toán 휎[ ] học: 휗[ ] = , với điều kiện [ ] 0 [ ] > Áp dụng những đặc tính định lượng làm giảm nhẹ đáng kể việc giải nhiều bài toán xác suất nói riêng, và khi giải những bài toán phức tạp, khi sử dụng
những luật phân bố dẫn đến việc tính toán nặng nề và không nhận được kết quả cuối cùng ở dạng rõ ràng. Rất thường xuyên đạt được lời giải cuối cùng, khi bỏ luật phân bố qua một bên và dựa vào một số các đặc tính định lượng. Nếu trong bài toán có một số lượng lớn biến ngẫu nhiên, thì để có một để xuất toàn diện về một luật phân bố cuối cùng, thì không yêu cầu phải biết hết các luật phân bố của từng biến ngẫu nhiên, mà chỉ cần biết một vài đặc tính định lượng của những giá trị này. Ngoài ra, trong thực tế (đời sống hàng ngày) hiếm khi dựa vào luật phân bố để mô tả những giá trị vật lý cụ thể, mà thường chuộng hơn việc sử dụng các khái niệm như giá trị trung binh và, trong một vài trường hợp thì là độ phân tán, hay giá trị lớn nhất và nhỏ nhất. Thật sự vậy, đối với những hành khách xe buýt thì gần như không quan tâm đến việc luật phân bố khoảng thời gian giữa các xe buýt, mà quan trọng và dễ hiểu hơn là giá trị trung bình và giá trị lớn nhất khoảng thời gian đó. Trong khi đó, khi mô hình hóa luồng giao thông để nhận được kết quả đúng và đáng tin cậy thì có thể cần có kiến thức về luật phân bố, hoặc là, ít nhất là một vài thời điểm của phân bố những khoảng cần [biết]. Thay thế cho biến ngẫu nhiên là giá trị không ngẫu nhiên, gọi là định trước (định mệnh). Trong một vài bài toán thì giá trị định trước X=x được xem như biến ngẫu nhiên với xác suất p=1, chỉ nhận một và một giá trị x. 2.6. Những phân bố điển hình biến ngẫu nhiên Mô hình hóa các hệ thống kỹ thuật với đặc trưng hoạt động rời rạc có yêu cầu sử dụng những luật phân bố khác nhau, bao gồm cả [phân bố] rời rạc và liên tục biến ngẫu nhiên. Ở đây sẽ xem xét một số phân bố điển hình biến ngẫu nhiên, được sử dụng rộng rãi trong những mô hình hàng đợi. Các luật phân bố biến ngẫu nhiên rời rạc được sử dụng rộng rãi nhất là: Phân bố Poisson; Phân bố hình học. Vì trong những mô hình hàng đợi toán học thì biến ngẫu nhiên liên tục thường là thời gian, những luật phân bố giá trị liên tục thường được quan tâm nhất được xác định trong vùng giá trị dương: Thống nhất (uniform); Mũ (exponential); Erlang (HypoExponential);
Erlang chuẩn hóa; HyperExponential; HyperErlang; 2.6.1. Phân bố Poisson Biến ngẫu nhiên rời rạc X phân bố theo luật Poisson, nếu xác suất P(X=k) mà nó nhận giá trị xác định ( = ) được biểu diễn bằng công thức: ― (k=0,1,2, ) (2.5) = 푃( = ) = !푒 Trong đó a – một giá trị dương nào đó, gọi là tham số của phân bố Poisson. Hình 2.4 mô tả phân bố Poisson hình chữ nhật với ba giá trị tham số phân bố: = 0.5; = 1; = 2. Biến ngẫu nhiên Poisson thỏa mãn những điều kiện sau: Số lượng sự kiện diễn ra trong hai khoảng thời gian phân biệt là độc lập. Xác suất một sự kiện diễn ra trong một khoảng thời gian nhỏ là tỷ lệ thuận với toàn bộ chiều dài của khoảng thời gian đó. Ngoài việc áp dụng cho thời gian, biến ngẫu nhiên Poisson có thể áp dụng cho những khu vực không gian riêng biệt. Ứng dụng: Số người chết do ngựa đá trong quân đội Phổ (lần đầu tiên yêu cầu); Dị tật bẩm sinh và di truyền đột biến; Bệnh hiếm gặp (như bệnh bạch cầu, nhưng không AIDS vì nó là truyền nhiễm và do đó không độc lập) - đặc biệt là trong trường hợp hợp lý; Tai nạn xe hơi; Lưu lượng dòng chảy và khoảng cách trống lý tưởng; Số lỗi đánh máy trên một trang; Tóc tìm thấy trong hamburger của McDonald; Lỗi của một máy tính trong một tháng. Nếu a là số trung bình của sự kiện xảy ra trong một khoảng thời gian nhất định hoặc khu vực không gian trong phân bố Poisson, thì giá trị trung bình và phương sai (variance) của phân bố Poisson đều bằng a.
0.7 0.6 0.5 a=0.5 0.4 P(X=k) a=1 0.3 a=2 0.2 0.1 0 0 1 2 3 4 5 6 7 8 k Hình 2.4. Phân bố Poisson Thông tin thêm: [1, 2]. 2.6.2. Phân bố hình học Phân bố hình học (geometric distribution) biến ngẫu nhiên rời rạc X=k có dạng: = 푃( = ) = 휌 (1 ― 휌) ( = 0,1,2, ), (2.6) trong đó 휌 ― tham số hình học của phân bố (0 < 휌 < 1). Phân bố (2.6) có thể được viết ở một vài dạng khác, nếu tham số 휌 được thay thể bởi tham số 훾 = 1 ― 휌: = 훾(1 ― 훾) (0 < 훾 < 1; = 0,1,2, ).
0.9 0.8 0.7 0.6 0.5 P(X=k) 0.4 γ=0.2 0.3 γ=0.5 0.2 γ=0.8 0.1 0 0 1 2 3 4 5 6 7 8 Hình 2.5. Phân bố hình học Ý nghĩa (ứng dụng) của phân bố hình học trong thực tế? Phân bố hình học với tham số 휌 mô hình số lượng các thất bại sẽ xảy ra trước sự thành công đầu tiên trong tập hợp các thử nghiệm nhị thức (binomial), với 휌 là xác suất của một thử nghiệm thành công. Ví dụ về phân bố hình học: Chọn một con bài từ một bộ bài (không có lá joker) và đoán màu (cơ, rô, chuồn, bích) của nó trước khi nhìn vào nó. Số lần đoán sai sẽ có trước khi đoán đúng có thể được ước tính là [mang tính] hình học (25%). Sự phân bố hình học giả sử rằng 휌 là không đổi với mỗi một thử nghiệm, tức là không có được điều gì tốt hơn sau mỗi lần đoán sai (sẽ phải đặt lá bài và xáo trộn lại). Nó cũng giả định rằng, phải kiên trì tiếp tục, ngay cả khi phải mất một trăm thất bại trước khi thành công. Do đó, một số cảnh báo là cần thiết trong ứng dụng của nó. Tham khảo thêm: [3]. 2.6.3. Phân bố thống nhất Biến ngẫu nhiên liên tục X phân bố một cách thống nhất (giống nhau, uniform) trong khoản (a,b), nghĩa là xác suất bằng nhau cho tất cả các giá trị từ tối thiểu (a) đến tối đa (b), nếu hàm phân bố F(x) và hàm mật độ phân bố f(x) có dạng tương ứng như sau: 0 ℎ푖
1 ℎ푖 Hình 2.6 mô tả hàm phân bố và mật độ phân bố thống nhất. F(x) f(x) 1 1 ― 0 a b x 0 a b x Hình 2.6. Hàm và mật độ phân bố thống nhất. 2.6.4. Phân bố mũ (exponential) Biến ngẫu nhiên liên tục X nhận những giá trị dương trong khoảng (0,+∞) phân bố theo dạng mũ nếu hàm F(x) và f(x) phân bố theo dạng sau: 퐹( ) = 1 ― 푒―훼 , ( ) = 훼푒―훼 , (2.7) trong đó 훼 > 0 - tham số của phân bố; ≥ 0 – biến ngẫu nhiên liên tục. Điểm đặc biệt của phân bố mũ là, hệ số biến thiên của nó không phụ vào tham số 훼 và luôn bằng 1: 훾푒 [ ] = 1. Trên hình 2.7 mô tả hàm phân bố và hàm mật độ phân bố của phân bố mũ với 3 tham số: 훼 = 2;훼 = 1;훼 = 0.5. 1 0.9 0.8 0.7 0.6 α=0.5, M[X]=2 0.5 0.4 α=1, M[X]=1 0.3 α=2, M[X]=0.5 0.2 0.1 0 0 1 2 3 4 5 6 7 8 9
4 3.5 3 2.5 α=2 2 α=1 1.5 α=0.5 1 0.5 0 0 1 2 3 4 5 6 7 8 Hình 2.7. Hàm phân bố và hàm mật độ phân bố mũ. Giải thích: Nếu các sự kiện được cho là xảy ra ngẫu nhiên theo thời gian (tức là theo tiến trình Poisson) và thời gian trung bình giữa các sự kiện 1 bằng [ ] = 훼, thì thời gian giữa các sự kiện liên tiếp sẽ được phân bố theo Exp (α). Ví dụ, nếu doanh nghiệp bảo hiểm nhận thấy rằng một số loại thảm họa thiên nhiên cụ thể xảy ra trung bình 5.5 năm một lần, thì thời gian giữa các thiên tai liên tiếp có thể được mô hình hóa như là Exp (1/5.5) năm. Phân bố mũ được sử dụng rộng rãi trong thuyết hàng đợi khi mô tả các tiến trình ngẫu nhiên [chạy] trong các mô hình hàng đợi. Điều này giải thích bằng việc, rằng phân bố mũ sở hữu một tính chất tuyệt vời, mà chỉ có phân bố này mới có, nhờ tính chất này mà với nhiều mô hình hàng đợi có thể đạt được những kết quả phân tích đơn giản và có dạng rõ ràng. Với phân bố này có liên quan chặt chẽ đến một lớp tiến trình rời rạc đặc biệt, gọi là tiến trình Markov, mà trong đó các sự chuyển tiếp (transition) giữa những trạng thái không phụ thuộc vào lịch sử của tiến trình (hay không phụ thuộc vào tiến trình trước đó), và được xác định bởi trạng thái của tiến trình trong thời gian cụ thể đó.Tính chất này đôi khi được gọi là tính chất thiếu vắng bộ nhớ của phân bố mũ (hay chính xác hơn, của những biến ngẫu nhiên phân bố theo mũ), và trong thuyết hàng đợi thì sử dụng thuật ngữ ‘ thiếu vắng hậu quả’ (không dẫn đến hậu quả). Khả năng nhận được kết quả phân tích tương đối đơn giản khi sử dụng giả định tính chất mũ của các tiến trình ngẫu nhiên làm xuất hiện moojt số luật phân bố đặc biệt được xem xét sau đó, là những kết hợp của những phân bố mũ và tạo điều kiện làm đơn giản khi giải nhiều bài toán, liên quan đến nghiên cứu các mô hình hàng đợi. Chúng là những phân bố
sau: Phân bố Erlang (HypoExponential), phân bố HyperExponential, phân bố HyperErlang. 2.6.5. Phân bố Erlang Phân bố Erlang cấp độ k là phân bố mà mô tả biến ngẫu nhiên liên tục X, nhận những giá trị dương (0;+∞) và là tổng của k lần biến ngẫu nhiên không phụ thuộc với nhau, phân bố theo chỉ một và một loại phân bố mũ với tham số α. Hàm phân bố và hàm mật độ phân bố của phân bố Erlang cấp độ k có dạng sau: 푖 훼(훼 ) ―1 퐹 ( ) = 1 ― 푒―훼 ∑ ―1 (훼 ) ; ( ) = 푒―훼 , (2.8) 푖=0 푖! ( ― 1)! Trong đó α và k – những tham số dương của phân bố (α>0;k=1,2, ); x≥0 – biến ngẫu nhiên liên tục. Có thể hình dung phân bố Erlang bằng ‘tổng’ các phân bố mũ: Exp(α) Exp(α) Exp(α) Trên hình 2.8 mô tả hàm mật độ phân bố Erlang khi α=1 với 3 giá trị tham số k=1;k=2;k=4. Khi k=1 phân bố Erlang trở thành phân bố mũ, còn khi k ∞ thì phân bố trở thành phân bố chuẩn tắc (normal distribution). 1 0.9 0.8 0.7 0.6 k=1 0.5 k=2 0.4 k=4 0.3 0.2 0.1 0 0 1 2 3 4 5 6 7 8 Hình 2.8. Mật độ phân bố Erlang Vì phân bố Erlang có 2 tham số, nên nó có thể được sử dụng để làm xấp xỉ những phân bố thực tế thông qua 2 thời điểm đầu. Hệ số biến thiên của phân bố Erlang phụ thuộc vào tham số k và nhận giá trị nhỏ hơn hoặc bằng 1:
1 훾 ( ) = ≤ 1 ( = 1,2, ). Để ý rằng, mong đợi toán học của phân bố Erlang phụ thuộc vào tham số k điều này tạo nên khó khăn nhất định trong việc xấp xỉ các phân bố thực bởi luật Erlang, vấn đề này không còn khi sử dụng phân bố Erlang chuẩn hóa. 2.6.6. Phân bố Erlang chuẩn hóa Phân bố Erlang chuẩn hóa là phân bố tổng k lần các biến ngẫu nhiên không phụ thuộc với nhau, mỗi một biến phân bố theo luật mũ với tham số k α (phụ thuộc vào k). Nói cách khác là tổng của k lần các biến ngẫu nhiên mũ, mỗi biến có mong đợi toán học nhỏ hơn k lần so với mong đợi toán học ban đầu của phân bố thực, điều này dẫn đến việc không phụ thuộc mong đợi toán học của phân bố Erlang chuẩn hóa vào giá trị k. Biểu thức toán học cho hàm phân bố và hàm mật độ phân bố Erlang chuẩn hóa nhận được từ 2.8, khi thay thế α bằng k α. 푖 훼( 훼 ) ―1 퐹 ( ) = 1 ― 푒― 훼 ∑ ―1 ( 훼 ) ; ( ) = 푒― 훼 , (2.9) 푖=0 푖! ( ― 1)! Hệ số biến thiên của phân bố Erlang chuẩn hóa giống với hệ số biến thiên của phân bố Erlang không chuẩn hóa: phụ thuộc vào k, nhỏ hơn hoặc bằng 1: 1 훾 ( ) = ≤ 1 ( = 1,2, ). 푛 Trên hình 2.9 mô tả hàm mật độ phân bố Erlang chuẩn hóa khi α=1 với 3 giá trị tham số k=1;k=2;k=16. 2 1.8 1.6 1.4 1.2 k=1 1 k=2 0.8 k=16 0.6 0.4 0.2 0 0 0.5 1 1.5 2 2.5 3 3.5 4 Hình 2.9. Mật độ phân bố Erlang chuẩn hóa.
Phân bố Erlang chuẩn hóa khi k ∞, khác với phân bố Erlang bình thường, trở thành biến định trước 1/ α. 2.6.7. Phân bố siêu mũ (HyperExponential) Trong những trường hợp khi phân bố thực của biến ngẫu nhiên liên tục nào đó có hệ số biến thiên lớn hơn 1, để xấp xỉ [phân bố] này thì có thể sử dụng phân bố siêu mũ (HyperExponential). Suy từ tên [siêu mũ] mà ra, thì phân bố siêu mũ có liên hệ gì đó với phân bố mũ và là sự pha trộn [và thêm] giữa các phân bố mũ khác nhau. Quá trình hình thành biến ngẫu nhiên với phân bố siêu mũ từ những biến ngẫu nhiên của phân bố mũ như sau. Giả định rằng, có n các bộ phát (generator) các biến ngẫu nhiên phân bố mũ với các tham số 훼1,훼2, ,훼푛 tương ứng (mong đợi toán học lần lượt là 1 = 1 훼1, 2 = 1 훼2, , 푛 = 1 훼푛), trong đó 훼푖 ≠ 훼푗, với ∀푖 ≠ 푗 (푖,푗 = 1,푛). Cho rằng trong kết quả một thử nghiệm với xác suất 푞푖 được sản sinh bởi một biến ngẫu nhiên với bộ phát i với tham số 훼푖 푖 = 1,푛 , trong đó 푞1 + 푞2 + + 푞푛 = 1. Tập hợp biến ngẫu nhiên nhận được trong kết quả thực hiện tập hợp các thử nghiệm như thế, sẽ phânbố theo luật siêu mũ: 푛 ―훼푖 푛 ―훼푖 퐹( ) = ∑푖=1 푞푖(1 ― 푒 ) = 1 ― ∑푖=1 푞푖푒 푛 ―훼푖 (2.10) ( ) = ∑푖=1 푞푖훼푖푒 Phân bố siêu mũ (2.10) có (2n-1) tham số: 훼1,훼2, ,훼푛 và 푞1,푞2, ,푞푛―1, vì 푛 푞푛 = 1 ― ∑푖=1 푞푖. Trong trường hợp đơn giản nhất biến ngẫu nhiên với phân bố siêu mũ có thể có được khi sử dụng chỉ 2 phân bố mũ: n=2. Khi đó hàm phân bố và mật độ phân bố siêu mũ sẽ có dạng: 퐹( ) = 푞(1 ― 푒―훼1 ) + (1 ― 푞)(1 ― 푒―훼2 ) ―훼1 ―훼2 (2.11) ( ) = 푞훼1푒 + (1 ― 푞)훼2푒 Để ý rằng, phân bố siêu mũ (2.11) là [phân bố] có 3 tham số, nghĩa là có 3 tham số không phụ thuộc q, 훼1,훼2 (0<q<1;훼1 ≥ 0;훼2 ≥ 0). Vì vậy, xấp xỉ các phân bố thực theo siêu mũ là thực hiện theo 3 thời điểm của phân bố, chứ không phải là 2, như của phân bố Erlang. Trên hình 2.10 mô tả hàm mật độ phân bố siêu mũ biến ngẫu nhiên X với mong đợi toán học bằng 1, cho 2 giá trị hệ số biến thiên: 훾[ ] = 2 và 훾[ ] = 4. Tham số của phân bố 2.11 có các giá trị sau: 훼1 = 0.183;훼2 = 1.506 cho phân bố với 훾[ ] = 2; 훼1 = 0.091;훼2 = 4.022 cho phân bố với 훾[ ] = 4. Trong đó tham số q là giống nhau cho cả 2 phân bố và bằng 0.07. Ở đây để so sánh có mô tả thêm hàm mật độ phân bố mũ với cùng một mong đợi toán học (M=1).
4 3.5 3 2.5 γ=2 2 γ=4 1.5 Exp 1 0.5 0 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 Hình 2.10. Hàm mật độ phân bố siêu mũ Như đã thấy từ biểu đồ, mật độ phân bố siêu mũ so với [mật độ phân bố] mũ được đặc trưng bởi sự giảm đột ngột trong vùng giá trị biến ngẫu nhiên nhỏ, trong khi đó, hệ số biến thiên càng lớn thì sự phụ thuộc này càng đột ngột. Có thể chứng minh rằng, xác suất xuất hiện những giá trị nhỏ của biến ngẫu nhiên với phân bố siêu mũ là lớn hơn nhiều so với xác suất xuất hiện các giá trị lớn. Hãy xác định xác suất mà biến ngẫu nhiên nhận những giá trị nhỏ hơn mong đợi toán học M (giá trị trung bình). Để xác định được, thì tính giá trị hàm phân bố ở điểm x=M: Pr(X<M)=F(x=M)=F(M). Khi đó với ví dụ phân bố siêu mũ ở trên ta nhận được: 0,735 ℎ표 ℎâ푛 ố 푣ớ푖 훾[ ] = 2 Pr( < ) = 퐹( ) = 0,919 ℎ표 ℎâ푛 ố 푣ớ푖 훾[ ] = 4 Như vậy, hơn 73% giá trị của biến ngẫu nhiên theo luật siêu mũ với hệ số biến thiên bằng 2, rơi vào khoảng (0;M) và chỉ 27% giá trị rơi vào khoảng lớn hơn giá trị trung bình. Với biến ngẫu nhiên mà hệ số biến thiên bằng 4, xác suất rơi vào khoảng (0;M) còn lớn hơn và gần bằng 92%. Rõ ràng là, hệ số biến thiên càng lớn thì xác suất rơi xuất hiện những giá trị nhỏ càng lớn. Với phân bố mũ: Pr( < ) = 퐹( ) = 0,632.
Miêu tả về phân bố siêu mũ sẽ không đầy đủ nếu không để ý đến ‘đuôi’ của phân bố này.Trên hình 2.11 mô tả biểu đồ hàm mật độ phân bố siêu mũ với giá trị biến ngẫu nhiên lơn hơn 4 (với cùng một mong đợi toán học M=1). 0.02 0.018 0.016 0.014 0.012 γ=2 0.01 γ=4 0.008 Exp 0.006 0.004 0.002 0 4 4.4 4.8 5.2 5.6 6 6.4 6.8 7.2 7.6 8 8.4 8.8 9.2 9.6 Hình 2.11. ‘Đuôi’ của hàm mật độ phân bố siêu mũ. Từ biểu đồ thấy rằng, đường cong của mật độ phân bố siêu mũ với hệ số biến thiên bằng 4 có ‘đuôi dài’ còn gọi là ‘đuôi nặng’, đặc trưng cho sự ít thay đổi. Điều này nghĩa là, với phân bố siêu mũ, xác suất xuất hiện giá trị lớn của biến ngẫu nhiên là cao hơn đáng kể so với, ví dụ như phân bố mũ. Vì vậy, khác nhau cơ bản phân bố siêu mũ với phân bố mũ ở chỗ, phân bố siêu mũ đặc trưng bởi xác suất lớn xuất hiện những giá trị nhỏ của biến ngẫu nhiên và cũng lúc, xác suất lớn xuất hiện những giá trị lớn của biến ngẫu nhiên. 2.6.8. Phân bố siêu Erlang (HyperErlang) Phân bố siêu Erlang là hổn hợp các phân bố Erlang chuẩn hóa và là phân bố chung nhất của biến ngẫu nhiên liên tục không âm, vì hệ số biến thiên nằm trong khoảng 0 đến +∞. Thành phần của phân bố siêu Erlang, khác với siêu mũ, là các phân bố Erlang chuẩn (thay cho phân bố mũ). Mật độ phân bố siêu Erlang: ―1 푛 푖훼푖( 푖훼푖 ) 푖 ( ) = ∑ 푞 푒― 푖훼푖 , 푖=1 푖 ( 푖 ― 1)! Dưới đây là bảng các đặc tính định lượng các phân bố rời rạc và liên tụ các đặc tính định lượng gồm: Mong đợi toán học M[X]; Thời điểm ban đầu thứ hai 훼2[ ];
Độ phân tán D[X]; Độ lệch trung bình bình phương (standard deviation) 휎[ ]; Hệ số biến thiên 훾[ ]. Trong phần chú ý chỉ ra giá trị hoặc phạm vi thay đổi tham số của phân bố tương ứng. Phân bố M[X] 휶 [푿] D[X] 흈[푿] 휸[푿] Chú ý Poisson a a(a+1) a 1 a>0 Hình học 1 ― 훾 2(1 ― 훾)2 (1 ― 훾)2 1 ― 훾 1 0 a nhất 2 3 12 2 3 3( + ) Mũ 1 2 1 1 1 훼 > 0 훼 훼2 훼2 훼 Erlang ( + 1) 1 = 1,2, 훼 훼2 훼2 훼 Erlang 1 ( + 1) 1 1 1 = 1,2, chuẩn hóa 훼 훼2 훼2 훼 푛 푛 푛 Siêu mũ 훼2[ ] ― D[X] 훾[ ] ≥ 1 푞푖 푞푖 2 ( [ ])2. 푞 = 1 훼 훼2 푖 푖=1 푖 푖=1 푖 푖=1 푛 푛 Siêu 푞 + 1 훼2[ ] ― D[X] 훾[ ] ≥ 0 훼푖 > 0 푖 푖 2 Erlang 푞푖 2 ( [ ]) . 훼푖 = 1,2, 훼푖 푖훼푖 푖=1 푖=1 푖 = 1,2, Nên nhớ rằng, những đặc tính định lượng liên hệ với nhau bằng những liên hệ đơn giản: 2 [ ] = 훼2[ ] ― ( [ ]) 휎[ ] = [ ] 휎[ ] 휎[ ]= [ ]
3. Mô hình toán học những hệ thống rời rạc Số lượng những giả thuyết khôn ngoan để giải thích bất kỳ hiện tượng đã cho nào đó là vô cùng (Định đề Persig) Nghiên cứu các hệ thống phức tạp yêu cầu xây dựng những mô hình toán học trừu tượng, thể hiện bằng ngôn ngữ biểu thức toán học trong những thuật ngữ của thuyết toán học xác định, tạo điều kiện nhận được sự phụ thuộc của các đặc tính hoạt động vào tham số của hệ thống được nghiên cứu. Nghiên cứu các tiến trình chạy trong những hệ thống rời rạc với đặc trưng hoạt động ngẫu nhiên , được thực hiện trong khung lý thuyết hàng đợi và lý thuyết các tiến trình ngẫu nhiên. Trong đó nhiều mô hình các hệ thống thực được xây dựng trên cơ sở mô hình hàng đợi, mà được chia ra thành các mô hình cơ sở ở dạng hệ thống hàng đợi và mô hình mạng ở dạng mạng hàng đợi, là những đối tượng toán học được mô tả trong thuật ngữ các công cụ toán học tương ứng. 3.1. Những khái niệm chính 3.1.1. Hệ thống hàng đợi Để mô tả một khái niệm nào đó thì nhiều tài liệu khác nhau về mô hình và các phương pháp thuyết xác suất sử dụng nhiều thuật ngữ khác nhau. Thuyết hàng đợi có nhiều tài liệu gọi là thuyết phục vụ số đông (hàng loạt). Trong thuyết hàng đợi thì thuật ngữ ‘ thiết bị phục vụ’ (service device) có thể được sử dụng bằng những thuật ngữ khác như ‘thiết bị (device, server)’, ‘kênh (channel)’,’đường dây (line),v.v. Thường thì điều này liên quan đến lĩnh vực ứng dụng mà trong đó ứng dụng mô hình hàng đợi. Ví dụ, thuật ngữ ‘cuộc gọi’ (call) và ‘đường dây’ được sử dụng trong lĩnh vực điện thoại (đặc biệt từ đây xuất hiện thuyết phục vụ số đông, thuật ngữ ‘khách hàng’ (customer) được sử dụng trong mô hình các cửa hàng, ngân hàng, cửa hiệu hớt tóc, v.v. Trong khi nghiên cứu mô hình hàng đợi như là một mô hình trừu tượng thì ở đây đưa vào và sử dụng bất cứ thuật ngữ nào tùy thuộc vào lĩnh vực ứng dụng của mô hình đó. Với mỗi thuật ngữ trong những dấu ngoặc có liệt kê những thuật ngữ đồng nghĩa, mà có thể gặp trong những tài liệu khác (đặc biệt trong các tài liệu tiếng Anh). Hệ thống hàng đợi (HTHĐ) – đối tượng toán học (trừu tượng), gồm một hoặc nhiều các thiết bị (kênh) D để phục vụ các yêu cầu (application, request, proposal) A đi vào trong hệ thống và thiết bị lưu trữ S (storage device), nơi chứa các yêu cầu, tạo thành hàng đợi Q và chờ đợi phục vụ (Hình 3.1).
S(Q) A D Tiến trình: Các yêu Đợi trong Phục vụ trong cầu đến hàng đợi thiết bị Mô tả: Luồng các QLĐ QLPV Luồng yêu cầu ra yêu cầu vào Ưu tiên Hình 3.1. Hệ thống hàng đợi Yêu cầu (những thuật ngữ có thể gặp: yêu cầu (application, request), nhu cầu (demand), cuộc gọi (call), khách hàng (customer) ) – đối tượng đi vào HTHĐ và yêu cầu phục vụ trong thiết bị phục vụ. Tập hợp các yêu cầu phân bố theo thời gian gọi là luồng yêu cầu; Thiết bị phục vụ (hay đơn giản gọi là thiết bị (các thuật ngữ có thể gặp: kênh (channel), đường dây (line) – phần tử của HTHĐ, chức năng là phục vụ các yêu cầu. Trong mỗi thời điểm trong thiết bị chỉ có một yêu cầu để phục vụ. Phục vụ - sự kéo dài [hay trì hoãn] (delay) thời gian của một yêu cầu trong trong thiết bị phục vụ. Thời gian phục vụ - thời gian trì hoãn (phục vụ) yêu cầu trong thiết bị. Thiết bị lưu trữ (buffer) – tập hợp các chỗ để đợi các yêu cầu [phía] trước thiết bị phục vụ. Số lượng chỗ để đợi gọi là dung lượng lưu trữ. Yêu cầu đi vào HTHĐ có thể ở một trong hai trạng thái: Trạng thái phục vụ (nằm trong thiết bị phục vụ); Trạng thái chờ (nằm trong thiết bị lưu trữ), nếu tất cả các thiết bị phục vụ bị bận phục vụ các yêu cầu khác. Yêu cầu trong nằm trong thiết bị lưu trữ và đợi phục vụ tạo thành hàng đợi các yêu cầu. Số lượng các yêu cầu chờ đợi để phục vụ nằm trong thiết bị lưu trữ xác định chiều dài hàng đợi. Quy luật đệm (QLĐ, buffering discipline) – quy tắc đưa yêu cầu vào thiết bị lưu trữ (bộ đệm, buffer). Quy luật phục vụ (QLPV, service discipline) – quy tắc chọn các yêu cầu từ hàng đợi để phục vụ trong thiết bị. Độ ưu tiên – đặc quyền cho việc đưa yêu cầu vào thiết bị lưu trữ hoặc chọn yêu cầu một loại nào đó từ hàng đợi để phục vụ trong thiết bị so với các yêu cầu loại khác.
Như vậy, HTHĐ bao gồm: Các yêu cầu chạy qua hệ thống, tạo thành luồng các yêu cầu; Hàng đợi các yêu cầu được tạo thành trong thiết bị lưu trữ; Cac thiết bị phục vụ. Ở đây khi không nói gì khác về HTHĐ thì sẽ sử dụng các giả định sau: Yêu cầu đi vào hệ thống, lập tức đưa vào phục vụ nếu thiết bị rảnh; Trong thiết bị phục vụ mỗi một thời điểm chỉ có một yêu cầu; Sau khi hoàn thành việc phục vụ một yêu cầu nào đó trong thiết bị, yêu cầu trong hàng đợi được chọn để phục vụ từ hàng đợi là lập tức, nghĩa là nói một cách khác, thiết bị [phục vụ] làm việc không nghỉ, nếu trong hàng đợi có ít nhất một yêu cầu; Việc đi đến của yêu cầu vào HTHĐ và thời gian phục vụ của chúng là không phụ thuộc vào việc có bao nhiêu yêu cầu đang có trong hệ thống, hoặc là những nhân tố khác; Thời gian phục vụ các yêu cầu là không phụ thuộc vào tốc độ đến của yêu cầu vào hệ thống. 3.1.2. Mạng hàng đợi Mạng hàng đợi (MHĐ) tập hợp các HTHĐ tương tác với nhau, trong môi trường đó các yêu cầu lưu thông (Hình 3.2, a). Thành phân chính của MHĐ là các nút (node) và nguồn phát (generator) các yêu cầu. Nút của MHĐ là hệ thống hàng đợi. Nguồn – nguồn phát các yêu cầu đến MHĐ và yêu cầu các bước phục vụ xác định trong những nút của mạng. Để mô tả MHĐ sử dụng đồ hình (graph) mạng hàng đợi: Đồ hình (graph) MHĐ – đồ hình có hướng, các đỉnh của nó tương ứng là những nút của MHĐ, còn các cung mô tả sự di chuyển các yêu cầu giữa các nút (Hình 3.2, b). Sự chuyển tiếp các yêu cầu giữa các nút MHĐ có thể được cho ở dạng xác suất chuyển giao. Đường di chuyển các yêu cầu trong MHĐ được gọi là định tuyến (route).
N1 휆,훼 D D ‘G’ N3 D D N2 a) 1 3 ‘G’ 2 b) Hình 3.2. Mạng hàng đợi 3.1.3. Luồng yêu cầu Tập hợp những sự kiện phân bố theo thời gian được gọi là luồng (traffic). Nếu sự kiện là sự xuất hiện các yêu cầu, thì gọi là luồng yêu cầu. Để mô tả luồng yêu cầu, cần thiết đưa ra những khoảng thời gian 휏 = 푡 ― 푡 ―1 giữa những thời điểm lân cận 푡 ―1 và 푡 việc các yêu cầu đến [xuất hiện] với số thứ tự (k-1) và k tương ứng (k=1,2, ; 푡0 ― thời điểm bắt đầu). Đặc tính cơ bản của luồng yêu cầu là cường độ 휆 – số yêu cầu trung bình 1 chạy qua [đi qua] trong một giới hạn trong một đơn vị thời gian. Giá trị = 휆 xác định khoảng thời gian trung bình giữa hai yêu cầu liên tiếp. Luồng, mà trong đó những khoảng thời gian 휏 giữa các yêu cầu liên tiếp nhận những giá trị xác định biết trước được gọi là định trước (deterministic). Nếu trong trường hợp này mà các khoảng thời gian đó bằng nhau ( 휏 = 휏 với mọi k=1,2, ) thì luồng được gọi là đều đặn (regular). Mô tả đầy đủ cho luồng đều đặn chỉ cần cho cường độ luồng 휆 hoặc giá trị 휏. Luồng, mà trong đó những khoảng thời gian 휏 giữa các yêu cầu liên tiếp là biến ngẫu nhiên thì gọi là [luồng] ngẫu nhiên. Để mô tả đầy đủ luồng yêu cầu ngẫu nhiên, cần đưa ra các luật phân bố (휏 ) tất cả các khoảng 휏 ( = 1,2, ). Luồng ngẫu nhiên mà trong đó tất cả các 휏1, 휏2, giữa các yêu cầu không phụ thuộc trong tập hợp và được mô tả bởi các hàm phân bố 1(휏1), 2(휏2), được gọi là luồng với phản ảnh (hậu quả) có giới hạn. Luồng ngẫu nhiên trong đó tất cả các khoảng 휏1, 휏2, phân bố theo cùng một luật 1(휏1) được gọi là [luồng] định kỳ (recurrent). Luồng yêu cầu được gọi là tĩnh (statical) nếu cường độ 휆 và luật phân bố
(휏) những khoảng thời gian giữa các yêu cầu không thay đổi theo thời gian. Nếu ngược lại thì luồng yêu cầu gọi là không tĩnh (non-statical). Luồng yêu cầu gọi là thông thường (ordinary) nếu ở mỗi thời điểm 휏 có thể xuất hiện chỉ một yêu cầu. Nếu ở một thời điểm nào đó có thể xuất hiện hơn một yêu cầu thì gọi là luồng yêu cầu không thông thường hay gọi là [luồng yêu cầu] theo nhóm (group). Luồng yêu cầu gọi là không có phản ảnh (hậu quả) nếu các yêu cầu đến không phụ thuộc vào nhau, nghĩa là thời điểm đến các yêu cầu theo thứ tự không phụ thuộc vào việc, khi nào và đã có bao nhiêu yêu cầu đã đến trước thời điểm đó. Luồng tĩnh thông thường không có phản ảnh được gọi là đơn giản nhất. Những khoảng thời gian 휏 giữa các yêu cầu trong luồng đơn giản nhất phân bố theo dạng mũ với hàm phân bố: (휏) = 1 ― 푒―휆휏, (3.1) trong đó 휆 > 0 – tham số của phân bố, là cường độ của luồng yêu cầu. Luồng đơn giản nhất thường được gọi là [luồng] Poisson, bởi vì số yêu cầu k đi vào trong một khoảng thời gian t cho trước phân bố theo luật Poisson: 푃 (휆푡) ―휆푡 , ( ( ,푡) = ! 푒 3.2) Trong đó 푃( ,푡) – xác suất [yêu cầu] đến bằng k yêu cầu trong một khoảng thời gian cố định t; 휆 – tần số luồng yêu cầu. Ở đây – biến ngẫu nhiên rời rạc, nhận những giá trị nguyên: = 0,1,2, ; t>0 và 휆 > 0 – các tham số luật Poisson. Chú ý rằng, luồng Poisson khác với luồng đơn giản nhất, có thể là: Tĩnh, nếu cường độ 휆 không thay đổi theo thời gian; Không tĩnh, nếu cường độ luồng phụ thuộc vào thời gian 휆 = 휆(푡). Trong khi đó, luồng đơn giản nhất, theo định nghĩa là luôn luôn tĩnh. Nghiên cứu bằng phương pháp phân tích những mô hình hàng đợi thường được thực hiện trong giả định sử dụng luồng đơn giản nhất, được sinh ra bởi chuỗi các điểm đặc biệt sau: Tính cộng (kết hợp) các luồng. Tổng của H các luồng tĩnh thông thường không phụ thuộc với các cường độ 휆1,휆2, ,휆 tạo thành một luồng đơn giản nhất với cường độ: 휆 = ∑ =1 휆 (3.3)
Trong điều kiện là những luồng được cộng vào ảnh hưởng ít và giống nhau đến luồng tổng. Trên thực tế luồng tổng gần với đơn giản nhất khi H≥5. Rõ ràng là, khi cộng những luồng đơn giản nhất thì luồng tổng sẽ là luồng đơn giảng nhất với bất cứ giá trị H nào. Tính phân tách luồng theo xác suất. Một luồng đơn giản nhất theo cách nào đó có thể được phân tách thành 2 luồng đơn giản nhất theo xác suất 휆1 = 휆 và 휆2 = (1 ― )휆. Tính đơn giản. Giả định về luồng đơn giản nhất tạo điều kiện với nhiều mô hình toán học tương đối dễ dàng nhận được kết quả rõ ràng sự phụ thuộc của đặc tính từ các tham số. Phân tích mô hình với các luồng yêu cầu không phải là luồng đơn giản nhất thường tạo nên nhiều khó khăn về toán học và không luôn luôn nhận được kết quả phân tích toán học. Chính tên luồng ‘đơn giản nhất’ nhờ điểm đặc biệt này. 3.1.4. Thời gian phục vụ yêu cầu Thời gian phục vụ – thời gian yêu cầu nằm trong thiết bị phục vụ - biến ngẫu nhiên và được mô tả bởi hàm phân bố (휏) hoặc hàm mật độ phân bố (휏) = ′(휏) . Trong trường hợp các luồng là không đồng nhất thì thời gian phục vụ yêu cầu có thể được phân biệt bởi các hàm phân bố khác nhau hoặc chỉ là giá trị trung bình. Thường thì thời gian phục vụ yêu cầu sử dụng luật mũ, điều này làm đơn giản đáng kể vấn đề về toán học. Điều này được tạo ra bởi rằng các tiến trình chạy trong những hệ thống với phân bố mũ của những khoảng thời gian, gọi là [tiến trình] Markov. Biến ngược lại với thời gian phục vụ trung bình b đặc trưng cho số yêu cầu trung bình, mà có thể được phục vụ trong một đơn vị thời gian, gọi là cường độ phục vụ: 휇 = 1 . Trong nhiều trường hợp sự phụ thuộc toán học phân tích có thể nhận được với bất kỳ luật phân bố nào của thời gian phục vụ các yêu cầu. Khi đó để xác định giá trị trung bình đặc tính phục vụ, nói riêng, sẽ chỉ cần biết ngoài mong đợi toán học b, thời điểm thứ hai vủa phân bố (độ phân tán) hoặc hệ số biến thiên 휈 củ thời gian phục vụ. Thời gian 0, ở lại trước khi phục vụ xong trong hệ thống, tính từ lúc thời điểm đi vào hệ thống của yêu cầu, và tính thêm rằng, vào thời điểm đến trong hệ thống có thể không có một yêu cầu nào, nghĩa là tính thêm thời gian chết của hệ thống, thì gọi là thời gian trước phục vụ. Mong đợi toán học của thời gian này được tính: 2 2 [ 0] = 휆 (1 + 휈 )/2, (3.4) trong đó 휆 – cường độ luồng đơn giản nhất các yêu cầu, đi vào hệ thống. 3.1.5. Chiến lược điều khiển luồng yêu cầu
Chiến dịch điều khiển luồng trong những mô hình hàng đợi có 2 dạng sau: Quy tắc đệm (QTĐ); Quy tắc phục vụ (QTPV). Ở đây chỉ xem xét vấn đề phân loại các loại chiến lược để thấy được mức độ da dạng của chúng. QTĐ được phân loại theo các dấu hiệu sau: Sự có mặt của độ ưu tiên giữa các yêu cầu: o Không có ưu tiên; o Có ưu tiên. Phương thức (chế độ) thay thế các yêu cầu từ hàng đợi: o Không có sự thay thế: khi yêu cầu đi vào hàng đợi đã đầy sẽ bị mất; o Với sự thay thế yêu cầu với cùng một loại (một lớp); o Với sự thay thế yêu cầu thuộc loại (lớp) có độ ưu tiên thấp nhất; o Với sự thay thế yêu cầu thuộc vào nhóm các lớp có độ ưu tiên thấp. Quy tắc thay thế hoặc chọn yêu cầu để phục vụ: o Thay thế ngẫu nhiên; o Thay thế yêu cầu đến cuối cùng, nghĩa là yêu cầu đến muộn nhất; o Thay thế yêu cầu lâu nhất, nghĩa là yêu cầu nằm trong thiết bị lưu trữ lâu nhất; Khả năng thay đổi độ ưu tiên. Phân loại theo phân công phục vụ của yêu cầu (đối với QTPV): Chế độ đơn: mỗi một lần phục vụ chỉ lấy một yêu cầu; Chế độ nhóm: mỗi lần phục vụ lấy một nhóm các yêu cầu của một hàng đợi, chỉ được thực hiện sau khi tất cả các yêu cầu trước đó đã được phục vụ xong; Phối hợp 2 chế độ: một phần yêu cầu được phục vụ đơn lẻ, một phần – theo nhóm; QTPV có thể sử dụng những quy tắc chọn yêu cầu sau để phục vụ: Không có độ ưu tiên: o Phục vụ theo thứ tự đến (FIFO – First In First Out); o Phục vụ theo thứ tự đảo ngược (LIFO - Last In First Out); o Phục vụ theo thứ tự ngẫu nhiên; o Phục vụ theo thứ tự luân phiên (khi có nhiều thiết bị phục vụ, việc phục vụ theo thứ tự luân phiên các hàng đợi từ 1,2, H, H – số lượng các thiết bị lưu trữ hay hàng đợi) Có độ ưu tiên:
o Ưu tiên tương đối , có nghĩa là độ ưu tiên chỉ được tính sau sau thời điểm hoàn thành phục vụ yêu cầu khi chọn một yêu cầu mới để phục vụ và không ảnh hưởng đến tiến trình phục vụ của những yêu cầu có ưu tiên thấp hơn, nói cách khác, khi có yêu cầu có độ ưu tiên cao hơn đi vào hệ thống thì không đưa đến việc phải ngừng phục vụ yêu cầu có độ ưu tiên thấp hơn; o Ưu tiên tuyệt đối, có nghĩa là khác với ưu tiên tương đối: khi có yêu cầu với độ ưu tiên cao hơn đi vào hệ thống, thì việc phục vụ yêu cầu có ưu tiên thấp hơn bị ngừng và thay thế cho việc phục vụ yêu cầu có ưu tiên cao hơn. Yêu cầu bị ngắt giữa chừng có thể bị mất hoặc là quay trở lại hàng đợi, khi quay trở lại hàng đợi thì có thể phải phục vụ lại từ đầu hoặc là được tiếp tục phục vụ từ thời điểm bị ngắt; o Có ưu tiên hỗn tạp: nghĩa là có thể được phối hợp giữa phục vụ không ưu tiên, hay ưu tiên tương đối và ưu tiên tuyệt đối; o Có ưu tiên luân phiên: giống như trường hợp ưu tiên tương đối nhưng dành cho một nhóm các yêu cầu; o Phục vụ theo lịch (kế hoạch): khi các yêu cầu các loại (lớp) khác nhau (nằm trong những thiết bị lưu trữ khác nhau) được chọn để phục vụ tương ứng theo một lịch (hoặc kế hoạch) nào đó, được cho bởi chuỗi chất vấn hàng đợi các yêu cầu , ví dụ trong trường hợp có 3 loại (lớp) yêu cầu thì lịch (hay kế hoạch) có thể có dạng: {1,2,1,3,1,2} Trong số các QLPV ở trên thì quy luật có ưu tiên hỗn tạp có một vị trí đặc biệt, vì sở hữu được tính chung so với các QLPV chế độ đơn. Để mô tả toán học cho quy luật có ưu tiên hỗn tạp sử dụng ma trận ưu tiên, là ma trận hình vuông 푄 = [푞푖푗|푖,푗 = 1,2, , ], trong đó H – số loại (lớp) các yêu cầu đi vào hệ thống. Phần tử 푞푖푗của ma trận cho độ ưu tiên của yêu cầu của lớp i so với yêu cầu lớp j và nhận những giá trị sau: 0 – không có ưu tiên; 1 – ưu tiên tương đối; 2 – ưu tiên tuyệt đối. Các phần tử của ma trận phải thỏa mãn những yêu cầu sau: 푞푖푖 = 0, vì giữa các yêu cầu của cùng một loại (lớp) không thể thiết lập độ ưu tiên; Nếu 푞푖푗 = 1 hoặc 푞푖푗 = 2 thì 푞푗푖 = 0, vì nếu yêu cầu của loại (lớp) i có ưu tiên [hơn] so với yêu cầu loại (lớp) j điều ngược lại là không thể.
Phụ thuộc vào khả năng thay đổi độ ưu tiên, trong quá trình hoạt động của hệ thống các quy luật ưu tiên đệm và ưu tiên phục vụ chia thành 2 lớp sau: Với ưu tiên tĩnh: độ ưu tiên không thay đổi theo thời gian; Với ưu tiên động: độ ưu tiên thay đổi theo thời gian trong quá trình hoạt động của hệ thống phụ thuộc vào những nhân tố khác nhau, ví dụ: khi đạt đến một giá trị tới hạn của chiều dài hàng đợi của yêu cầu một loại (lớp) nào đó, mà có độ ưu tiên bé, nó có thể được gán cho độ ưu tiên cao hơn. 3.2. Phân loại các mô hình hàng đợi 3.4.1. Những mô hình cơ sở Khi mô hình hóa những hệ thống thực với đặc trưng hoạt động rời rạc thường sử dụng rộng rãi các mô hình cơ sở ở dạng hệ thống hàng đợi, được phân loại như sau (hình 3.5): 휇 = 1/ 휇 = 1/ 휆 휆 D D a) b) 휇 D 휆1 휇푖 = 1/ 푖 휆 D D 휆 b) d) Hình 3.3. Phân loại các mô hình cơ sở Theo số lượng chỗ trong thiết bị lưu trữ: o Không có thiết bị lưu trữ: các yêu cầu đi vào hệ thống và đặt các thiết bị phục vụ vào trạng thái bận phục vụ cho các yêu cầu có ưu tiên cao, như vậy sẽ nhận phải sự từ chối và mất mát những yêu cầu [khác], những hệ thống như vậy gọi là HTHĐ từ chối; o Với thiết bị lưu trữ có dung lượng giới hạn (HTHĐ có mất mát): trong đó yêu cầu đi vào bị mất, nếu nó đặt vào cuối thiết bị lưu trữ đã đầy (hình 3.3, a); o Với thiết bị lưu trữ có dung lượng vô hạn (HTHĐ không mất mát): trong đó với bất kỳ yêu cầu đi vào nào luôn luôn tìm được chỗ trong thiết bị lưu trữ để chờ (hình 3.3, b). (Giả định về dung lượng lưu trữ vô hạn có thể
được sử dụng để mô hình hóa những hệ thống thực, trong đó xác suất mất mát yêu cầu vì tràn thiết bị lưu trữ (tràn bộ đệm) có dung lượng giới hạn nhỏ hơn 10―3). Theo số lượng các thiết bị phục vụ: o Một kênh: chỉ chứa một thiết bị phục vụ (hình 3.3, a,b,d); o Nhiều kênh: chứa K các thiết bị phục vụ (hình 3.3, c). Trong những HTHĐ nhiều kênh thường giả thuyết rằng, tất cả các thiết bị phục vụ là giống nhau và giống nhau về khả năng truy cập cho bất kỳ yêu cầu nào. Theo số lượng các loại (lớp) các yêu cầu đi vào HTHĐ: o Với luồng yêu cầu đồng nhất (hình 3.3, a,b,c); o Với luồng yêu cầu không đồng nhất (hình 3.3, d). Các luồng yêu cầu đồng nhất tạo thành các yêu cầu cùng một loại (lớp), còn luồng yêu cầu không đồng nhất là luồng yêu cầu có vài loại (lớp). Trong HTHĐ, vốn là mô hình toán học trừu tượng, các yêu cầu thuộc về những loại (lớp) khác nhau trong trường hợp nếu chúng trong hệ thống thực được mô hình hóa khác nhau chỉ một trong những nhân tố sau: Thời gian phục vụ; Độ ưu tiên. Nếu các yêu cầu không khác nhau về thời gian phục vụ và độ ưu tiên thì, trong HTHĐ chúng có thể được xem như các yêu cầu cùng một loại (lớp), không phụ thuộc vào bản chất vật lý. 3.4.2. Những mô hình mạng Phụ thuộc vào cấu trúc và tính chất của hệ thống được nghiên cứu mô hình của chúng có thể phục vụ (phục dịch, serve) cho một vài lớp. Phụ thuộc vào đặc trưng tiến trình đến và phục vụ các yêu cầu vào mạng hàng đợi chia thành: Ngẫu nhiên: trong đó những tiến trình đi vào và/hoặc phục vụ các yêu cầu mang tính chất ngẫu nhiên, nghĩa là khoảng thời gian giữa những yêu cầu đi vào và/hoặc thời gian phục vụ của chúng trong các nút là các biến ngẫu nhiên, được mô tả bởi những luật phân bố tương ứng; Định trước: trong đó những khoảng thời gian giữa các yêu cầu đi vào và thời gian phục vụ yêu cầu trong các nút là những biến (giá trị) định trước. Phụ thuộc vào tính phụ thuộc (dependence) liên hệ giữa cường độ các luồng yêu cầu trong những nút khác nhau chi thành: Tuyến tính; Không tuyến tính.
Trong MHĐ tuyến tính, cường độ luồng các yêu cầu ở nút j liên hệ với cường độ luồng yêu cầu ở nút i theo biểu thức tuyến tính sau: λj = αijλi. Trong đó αij – hệ số tỷ lệ, chỉ ra cường độ luồng yêu cầu ở nút j gấp bao nhiêu lần so với ở nút i (푖,푗 = 1,푛). Vì sự phụ thuộc (biểu thức tuyến tính) trên đúng cho từng cặp các nút, biểu thức này có thể viết lại ở dạng khác và thể hiện được cường độ đến của yêu cầu ở tất cả các nút 푗 = 1,푛 thông qua chỉ một và một cường độ, ví dụ như [thông qua] cường độ luồng yêu cầu : λ0 đi vào mạng hàng đợi từ nguồn phát các yêu cầu: 휆푗 = 훼푗휆0. (3.5) Hệ số tỷ lệ 훼푗 > 0 chỉ ra cường độ luồng yêu cầu ở nút j khác bao nhiêu lần so với cường độ từ nguồn phát yêu cầu, và còn gọi là hệ số truyền (transfer coefficient). Hệ số truyền có thể nhận bất kỳ giá trị dương nào. Hệ số truyền đóng vai trò quan trọng khi phát trỉên các biểu thức toán học và tính toán các đặc tính hoạt động của mô hình mạng. Điều này được suy ra bởi ý nghĩa vật lý của hệ số truyền. Hệ số truyền có thể được hiểu như là số lượng trung bình lần các yêu cầu ‘rơi vào’ nút đó (j) trong thời gian ở trong mạng. Ví dụ, nếu hệ số truyền của nút nào đó trong mạng hàng đợi bằng 3, thì có nghĩa là, bất kỳ một yêu cầu nào trong thời gian ở trong mạng có trung bình 3 lần rơi vào phục vụ ở nút đó. Giá trị của hệ số truyền bằng 0.25 có nghĩa là, trung bình có 1 yêu cầu trong 4 yêu cầu rơi vào phục vụ ở nút đó, còn 3 yêu cầu còn lại thì không. Trong các MHĐ không tuyến tính các cường độ luồng các yêu cầu có liên hệ phức tạp và không tuyến tính, điều này khiến việc nghiên cứu khó khăn hơn nhiều. Tính không tuyến tính của MHĐ được gây ra bởi: Sự mất mát các yêu cầu trong mạng, ví dụ do giới hạn dung lượng lưu trữ trong các nút; Sự nhân lên của các yêu cầu, ví dụ như sự hình thành một số các yêu cầu mới sau khi hoàn thành phục vụ một yêu cầu nào đó trong một nút nào đó trong mạng. Phụ thuộc vào số lượng các yêu cầu lưu chuyển trong mạng phân các MHĐ ra thành: Mở; Đóng; Đóng-mở;