Đề tài Giải quyết một số bài toán bằng mô hình hàng đợi

ÑAÏI HOÏC HUEÁ TRÖÔØNG ÑAÏI HOÏC KHOA HOÏC TIEÅU LUAÄN MOÂN HOÏC MOÂ PHOÛNG NGAÃU NHIEÂN Ñeà taøi: GIAÛI QUYEÁT MOÄT SOÁ BAØI TOAÙN BAÈNG MOÂ HÌNH HAØNG ÑÔÏI Thaày giaùo höôùng daãn: PGS.TS. Traàn Loäc Huøng Hoïc vieân thöïc hieän: Traàn Thaùi Sôn Lôùp Cao hoïc Khoa hoïc maùy tính – Khoaù 2008-2010 Hueá, thaùng 6/2009 A. LỜI NÓI ĐẦU Hầu hết các hiện tượng tự nhiên và xã hội đều có tính chất ngẫu nhiên và có thể được đặt trưng bằng dãy gồm các biến ngẫu nhiên có phân phối xác định nào đó. Khi họ các biến ngẫu nhiên phụ thuộc vào thời gian ta gọi là quá trình ngẫu nhiên. Quá trình vận hành của một hệ thống vật lý theo thời gian, tín hiệu truyền dẫn và nhiễu của một hệ thống viễn thông, quá trình sắp hàng ở một tổng đài,... là các quá trình ngẫu nhiên. Hệ thống hàng đợi là một hệ thống biến động theo thời gian và các trạng thái của nó phát sinh ngẫu nhiên. Phương pháp giải quyết các bài toán trên các mô hình hàng đợi chủ yếu vào phân tích các quá trình ngẫu nhiên độc lập làm hệ thống thay đổi trạng thái liên tục theo thời gian. Từ các nghiên cứu cụ thể trên một số phân phối thường gặp, một số mô hình được trình bày một cách tường minh dưới dạng: phân phối xác suất của biến đặc trưng của hệ thống. Các hệ thống quan trọng sẽ được xem xét: hệ thống khách hàng – phục vụ, hệ thống quản lý kho và hệ thống sử dụng thiết bị. Tiểu luận: “Giải quyết một số bài toán bằng mô hình hàng đợi” nhằm mục đích đưa ra cơ chế hoạt động của hàng đợi và ứng dụng vào việc giải quyết tối ưu bài tóan kinh doanh. Nội dung chính của tiểu luận gồm: Cơ sở mô phỏng ngẫu nhiên. Hệ thống hàng đợi. Bài toán ứng dụng hệ thống hàng đợi. Bản thân xin chân thành cảm ơn Thầy giáo PGS.TS. Trần Lộc Hùng đã tận tình hướng dẫn, cung cấp các tài liệu để tôi hoàn thành tiểu luận này. Do khả năng có hạn nên tiểu luận không tránh khỏi những thiếu sót và hạn chế. Rất mong nhận được sự góp ý và chỉ bảo của thầy để bản thân có thể hoàn chỉnh hơn nữa những hiểu biết của mình. B. NỘI DUNG 1. CƠ SỞ MÔ PHỎNG NGẪU NHIÊN 1.1. Khái niệm về mô phỏng ngẫu nhiên Mô phỏng (Simulation) được ứng dụng rộng rãi trong kinh tế, kỹ thuật và nhiều lĩnh vực khác. Theo từ điển chính xác Oxford, bản 1976, " Mô phỏng có nghĩa là giả cách, … làm ra vẻ như, hành động như, bắt chước giống với, mang hình thức của, giả bộ như …, làm giả các điều kiện của tình huống nào đó thông qua một mô hình với mục đích huấn luyện hoặc tiện lợi". Về mặt ý nghĩa kỹ thuật, mô phỏng (hay nói đúng hơn, phương pháp mô phỏng) hàm chứa việc áp dụng một mô hình nào đó để tạo ra kết quả, chứ không có nghĩa là thử nghiệm một hệ thống thực tế nào đó đang cần nghiên cứu hay khảo sát. Nếu mô hình có chứa các thành phần hay yếu tố ngẫu nhiên thì chúng ta có mô phỏng ngẫu nhiên. Thuật ngữ " Phương pháp Monte-Carlo" xuất hiện từ thế chiến thứ hai khi tiến hành các mô phỏng ngẫu nhiên trong quá trình phát kiến bom nguyên tử. Ngày nay, thuật ngữ này đôi khi cũng được dùng đồng nghĩa với thuật ngữ phương pháp mô phỏng ngẫu nhiên, như khi ta nói phương pháp Monte-Carlo tính tích phân chẳng hạn, tuy nhiên, nó không được sử dụng một cách rộng rãi. Chúng ta xét mô phỏng trên hai quan điểm: Nghệ thuật và kỹ thuật (với tứ cách một công cụ), mà trong một số trường hợp khó phân định ranh giới rạch ròi. Trong phần này chúng ta nghiên cứu mô phỏng ngẫu nhiên về phương diện một số kỹ thuật, công cụ thường sử dụng. 1.2. Các công cụ chủ yếu của mô phỏng 1.2.1. Nguồn ngẫu nhiên. Để áp dụng mô phỏng ngẫu nhiên trước hết cần phải có được một nguồn các số ngẫu nhiên. Các số ngẫu nhiên như vậy có thể được tạo ra bởi các hàm sinh số ngẫu nhiên. Trong nhiều ngôn ngữ lập trình (như Visual C++, hay Builder C++ 5.0, Pascal, …), ta sẽ thấy có một cặp hàm dạng RAND(seed) và RANDOM(seed) để phát sinh các số được coi là ngẫu nhiên. Các tham số seed ở trên được gọi là hạt mầm ngẫu nhiên, đóng vai trò khởi tạo dãy số ngẫu nhiên. Thông thường, các nguồn này được coi như tồn tại một cách đương nhiên. Câu hỏi đặt ra là chúng đã đủ "tốt" hay chưa? Trong tiểu luận này chúng ta không đi sâu vào việc phân tích các vấn đề trên. Một cách khái quát có thể nói rằng, các số được gọi là các số ngẫu nhiên được tạo ra như vậy còn xa mới thực sự ngẫu nhiên. Một cách chính xác hơn, chúng ta có thể gọi là các số giả ngẫu nhiên mà thôi. Chất lượng của nguồn ngẫu nhiên có thể ảnh hưởng rất lớn tới kết quả nghiên cứu khi sử dụng phương pháp mô phỏng ngẫu nhiên. 1.2.2 Mô hình ngẫu nhiên Hai lý do chính cho việc áp dụng mô phỏng ngẫu nhiên là: - Tổng hợp dữ liệu theo sự phân loại nhất định. - Đưa ra các dự báo. Muốn áp dụng mô phỏng ngẫu nhiên cần phải có mô hình. Như vậy, mục đích của mô phỏng ngẫu nhiên cũng gần với mục đích của mô hình hoá (modelling). Có hai loại mô hình thường được áp dụng, đó là: mô hình cơ chế (mechanistic model) và mô hình tiện dụng (convenient model). Cả hai loại này đều có thể được sử dụng để trợ giúp các công việc nghiên cứu, khảo sát nhằm gia tăng sự nhận biết và tìm kiếm tri thức, dự báo và hỗ trợ việc ra quyết định. Để ứng dụng một mô hình, ta có hai sự lựa chọn sau: - Tiến hành việc phân tích về mặt toán học để tìm hiểu hành vi của mô hình. Vấn đề này nhiều khi trở nên rất phức tạp với các hệ phi tuyến nhiều biến, do đó chúng ta cần đặt ra thêm các giả thiết. Tuy nhiên những giả thiết "chặt chẽ quá" của toán học đôi khi trở nên "đáng nghi ngờ" trong thực tế. - Thí nghiệm với mô hình đang xem xét. Đối với các mô hình ngẫu nhiên các giá trị phản hồi (đầu ra) sẽ biến thiên, vì vậy chúng ta cần tạo ra hàng loạt các thể hiện (dữ liệu nhân tạo) với những bộ tham số khác nhau của mô hình. Đôi khi cũng cần xem xét tới sự lựa chọn thứ ba, đó là tiếp cận (hybrid approach) của hai lựa chọn trên. 1.3 Một số phân phối xác suất thường gặp Để áp dụng mô phỏng ngẫu nhiên cần biết một số kiến thức cơ bản mà chúng ta sẽ nhắc lại ngay sau đây. Biến ngẫu nhiên là một khái niệm quan trọng trong xác suất thống kê. Một cách giản lược, biến ngẫu nhiên còn gọi là đại lượng ngẫu nhiên, được hiểu là biến nhận giá trị tuỳ thuộc vào kết quả của phép thử (phép đo, quan sát, thí nghiệm) mà không thể đoán trước được. Biến ngẫu nhiên chia làm hai loại chính: rời rạc và liên lục. Biến rời rạc có thể nhận các giá trị từ một tập hợp (có lực lượng) hữu hạn hoặc đếm được. Biến liên tục là một khái niệm toán học về loại biến ngẫu nhiên có thể nhận các giá trị dày sát nhau trên một hoặc một số khoảng đoạn số thực nào đó (để trình bày vấn đề đơn giản, ở đây chúng ta chỉ nói tới biến ngẫu nhiên nhận các giá trị là số thực). Trong thực tế, không có một đại lượng ngẫu nhiên nào là liên tục theo nghĩa tuyệt đối, chẳng qua là chúng ta không nhận biết được (một cách cố ý hay không cố ý) khoảng cách giữa các giá trị rất sát nhau của nó mà thôi. Phân phối xác suất của biến ngẫu nhiên rời rạc được minh họa qua ví dụ sau: Xét biến X có thể rơi vào một trong ba trạng thái được định lượng bởi các giá trị 6, 9, 12 với các xác suất tương ứng của các trạng thái là 0,3, 0,4 và 0,3. Chú ý rằng tổng các xác suất bằng 1 (100%) được phân phối vào các giá trị biến ngẫu nhiên X có thể lấy như trình bày trong bảng sau đây, được gọi là bảng phân phối xác suất. Các giá trị của X: xi 6 9 12 Xác suất tương ứng: pi 0,3 0,4 0,3 (Chú ý: ) Một số phân phối xác suất thường dùng của biến ngẫu nhiên liên tục và rời rạc được liệt kê dưới đây: a. Phân phối đều trong [0,1): X nhận các giá trị thuộc nửa khoảng [0,1) với khả năng như nhau. Hàm mật độ xác suất f(x) của nó được biểu diễn như hình 1 dưới: P(xa) f(x) x P(x<a) 0 f2 1 1 Hình 1, Đồ thị hàm mật độ phân phối đều b. Phân phối Poisson: Với một hệ thống hàng chờ một kênh, số X tín hiệu đến trong một khoảng thời gian là một biến ngẫu nhiên. Giả sử số tín hiệu đến trung bình trong một khoảng thời đã biết được (kí hiệu ), thì với một số điều kiện nhất định có thể coi X tuân theo luật phân phối xác suất Poisson như sau: Các giá trị của x: xi 0 1 …..……..x…..……. + Xác suất pi tương ứng P(X=x)= Chú ý rằng số đặc trưng cho giá trị trung bình của biên ngẫu nhiên X được gọi là kỳ vọng. Trong phân phối Poisson, kỳ vọng của X là . Số đặc trưng cho sự phân tán các giá trị của X xung quanh giá trị kỳ vọng của nó được gọi là độ lệch chuẩn . Với phân phối Poisson thì 2= . c. Phân phối mũ: Trên đây ta đã xét phân phối Poisson của số các tín hiệu đến trong một đơn vị thời gian. Một kiểu biến ngẫu nhiên thường xét là khoảng thời gian giữa hai tín hiệu liên tiếp sẽ tuân theo phân phối mũ. Đây là biến ngẫu nhiên liên tục chỉ nhận các giá trị không âm với hàm mật độ xác suất là f(T)= . Ký hiệu biến ngẫu nhiên đang xét là T thì xác suất P(T có thể hiểu là xác suất cộng dồn cho tới t. Do đó hàm phân phối xác suất của T là F(t)= d. Phân phối chuẩn tắc N(0,1): Giả sử X là biến ngẫu nhiên có phân phối chuẩn tắc N(0,1). Lúc đó nó có kỳ vọng m = 0 và độ lệch chuẩn . Hàm phân phối xác suất của X có dạng: F(x) = P(X. Cho X là biến ngẫu nhiên tuân theo luật phân phối chuẩn N(m,) có kỳ vọng m, độ lệch chuẩn . Lúc đó thực hiện phép đổi biến Z= thì Z là một biến ngẫu nhiên tuân theo luật phân phối chuẩn tắc N(0,1). 1.4 Các bước cơ bản khi sử dụng mô phỏng ngẫu nhiên: Có 10 bước cơ bản thường sử dụng trong khi dùng phương pháp mô phỏng ngẫu nhiên để nghiên cứu và giải quyết các bài toán thực tế: Bước 1: Xác định vấn đề mô phỏng và lập kế hoạch nghiên cứu Bước 2: Chọn dữ liệu và xây dựng mô hình toán học tương ứng để giải quyết vấn đề đặt ra Bước 3: Kiểm tra hiệu lực Bước 4: Xây dựng thuật toán và viết chương trình để chuyển đổi từ mô hình toán học sang mô hình mô phỏng có thể kiểm nghiệm với sự giúp đỡ của máy tính điện tử Bước 5: Chạy chương trình Bước 6: Kiểm tra Bước 7: Thiết kế thí nghiệm Bước 8: Tạo sản phẩm Bước 9: Trên cơ sở rút ra từ phương pháp mô phỏng ngẫu nhiên, tiến hành phân tích, đánh giá vấn đề thực tế và rút ra các kết luận cần thiết Bước 10: Báo cáo kết quả Các bước trên thể hiện bằng lưu đồ sau: Đặt bài toán và kế hoạch nghiên cứu Chọn dữ liệu, xác định mô hình Hiệu lực? Lập trình, kiểm tra Chạy chương trình Kiểm tra Thiết kế thí nghiệm Tạo sản phẩm Phân tích dữ liệu ra Kết quả Không Không Có Có Trên đây là các bước cần làm khi áp dụng mô phỏng ngẫu nhiên để tìm ra các phương án hợp lý cho các bài toán thực tế. Ngoài ra, mô phỏng còn được áp dụng để giải quyết nhiều vấn đề khác. 2. HỆ THỐNG HÀNG ĐỢI: 2.1 Mô tả hệ thống: Hệ thống hàng đợi hay còn gọi là hệ thống khách hàng và phục vụ. Hệ thống được xây dựng nhằm phục vụ các nhu cầu phát sinh từ một quần thể nhất định. Chẳng hạn: quầy bán hàng, dịch vụ du lịch, ngân hàng, phòng đào tạo chăm lo các đăng ký học tập của học sinh… Như vậy, hệ thống hàng đợi bao gồm bộ phận tiếp nhận khách hàng, các trạm phục vụ khách hàng (số lượng nhiều hay ít là tùy thuộc vào số lượng khách hàng). Bộ phận khác phát sinh từ ngoài vào là quần thể mà từ đó khách hàng đi tới hệ thống. Hai bộ phận này kết hợp với nhau và tạo ra sự hoạt động của hệ thống: thời gian phục vụ khách hàng, số khách hàng chờ được phục vụ tạo thành hàng đợi, quy tắc phục vụ khách hàng như thế nào là hợp lý… Người quản trị hệ thống khách hàng và phục vụ phải xác định cho được những chi phí vô ích. Những chi phí vô ích này tạo thành tính không hiệu quả của hệ thống. Có hai dạng chi phí vô ích: Chi phí của khách hàng phải chờ trong hệ thống trước khi được phục vụ. Chi phí này có thể hiểu được một cách tương đương là trong cùng một khoảng thời gian quản lý T, nếu khách hàng chờ lâu thì lượng khách hàng chờ tới trong khoảng thời gian T giảm. Chi phí cho các trạm phục vụ khách hàng nhưng lại không có khách hàng. Như vậy trong khoảng thời gian quản lý T, tỷ lệ thời gian phục vụ khách hàng tạo thành hiệu suất U của một trạm phục vụ. Hiệu suất càng gần 1 thì chi phí vô ích càng nhỏ và ngược lại, nếu hiệu suất gần bằng 0 thì chi phí vô ích càng lớn. server Đây là hai loại chi phí ngược nhau: nếu giảm chi phí vô ích từ phía khách hàng tức là giảm thời gian chờ của khách hàng thì phải tăng số trạm phục vụ; và như vậy làm tăng chi phí vô ích từ phía phục vụ. Ngược lại nếu muốn giảm chi phí vô ích từ phía phục vụ thì phải giảm số trạm phục vụ nhưng điều này lại làm tăng thời gian chờ của khách hàng. Rõ ràng muốn tăng tính hiệu quả hoạt động của hệ thống thì cần phải cân đối tổng thể từ hai loại chi phí này. Queue Input Output Hình 2 : Mô hình xếp hàng đơn giản nhất là chỉ có một hàng đợi đơn Trong hệ thống xếp hàng này các khách hàng vào từ phía bên trái và ra khỏi phía bên phải. Vòng tròn miêu tả server (hệ thống phục vụ). Ví dụ trong một dãy quầy thanh toán tiền trong một siêu thị, server sẽ là các nhân viên thao tác máy đếm tiền. Trong mạng dữ liệu, server là phương tiện truyền dẫn liên kết đầu ra, các đường dây, trung kế, CPU...Còn hình chữ nhật mô tả hàng đợi (queue) mà nó chứa các khách hàng trước khi được vào phục vụ tại server. Đôi khi ta có thể gọi hệ thống như vậy là một hệ thống xếp hàng hay một hàng đợi tuỳ thuộc vào hoàn cảnh cụ thể. Trong trường hợp đó, khi dùng từ hàng đợi ta hiểu là toàn bộ hệ thống xếp hàng bao gồm các yêu cầu đang đợi dịch vụ và các yêu cầu đang được phục vụ. Do đó thuật ngữ độ dài hàng đợi được hiểu là số các yêu cầu đang đợi cộng thêm các yêu cầu đang được phục vụ. 2.2 Phân tích thành phần của hệ thống: Nội lực: Cơ sở tiếp nhận khách hàng nơi mà khách hàng phải chờ trước khi được phục vụ, các trạm phục vụ khách hàng (hoặc các nhân viên phục vụ), quy tắc phục vụ khách hàng sao cho hiệu quả hoặc phải phù hợp với tình hình hiện tại của hệ thống, khả năng phục vụ khách hàng của các trạm: phục vụ nhanh hay chậm… Ngoại lực: Quần thể nơi phát sinh ra khách hàng và số khách hàng phát sinh đi tới hệ thống. 2.3 Một số quy tắc phục vụ của hàng đợi Thứ tự mà theo đó các công việc trong hàng xếp được phục vụ gọi là quy tắc phục vụ. Hầu như các hệ thống xếp hàng ngày nay được sử dụng để phục vụ khách hàng theo trình tự mà chúng tới. Trình tự phục vụ đó là FIFS (First In First Served) : đến trước phục vụ trước hay còn gọi là FCFS (First Come First Served). Ngoài ra, còn có một số kiểu phục vụ khác như là: LCFS (Last Come First Served) hay LIFO (Last In First Out) : Theo đó các khách hàng đến sau sẽ được phục vụ trước. LCFSPR( LCFS With Pre_Emptive) : Khi các khách hàng đến sau nhất sẽ thế chỗ của khách hàng đang được phục vụ cho đến khi nó được phục vụ xong thì phục vụ có thể tiếp tục đối với khách hàng bị thế chỗ ngay nơi mà nó bị ngắt trước đây, trong trường hợp đó ta có dịch vụ với quyền ưu tiên phục vụ trước_LIFOPR. RR(Round Robin): Phục vụ vòng tròn, thời gian tại một tài nguyên được phân chia thành một số các khoảng nhỏ có độ dài cố định và được gọi là các lượng tử (quantum). Một khách hàng mới tham gia vào hàng đợi và chờ để lên được đầu hàng theo nguyên tắc FCFS và cuối cùng khách hàng nhận được một lượng tử cho quá trình phục vụ. Khi lượng tử này hết mà khách hàng vẫn cần được phục vụ thì khách hàng đó phải quay trở về đầu hàng đợi và quá trình lặp lại cho tới khi khách hàng đó được phục vụ xong. SPT (Shortest Proceesing Time First): Nghĩa là thời gian xử lý ngắn nhất sẽ được phục vụ trước. SRPT (Shortest Remaining Proceesing Time First): Thời gian xử lý ngắn nhất được đề cử. 2.4 Ký hiệu Kendall: Kendall đã đưa ra 6 tham số để phân biệt hệ thống này với hệ thống khác:A/B/s/k/m/q. Vị trí của các tham số là tầm quan trọng của tham số ảnh hưởng tới hệ thống. Vị trí số 1: tham số A đặc trưng cho phân phối khách hàng đi tới hệ thống. Vị trí số 2: tham số B đại diện cho phân phối của thời gian phục vụ khách hàng. Vị trí số 3: tham số s là các trạm phục vụ khách hàng. Vị trí số 4: tham số k giới hạn sức chứa của hệ thống đối với số khách hàng phải đợi. Vị trí số 5: tham số m mô tả lực lượng của quần thể nơi mà khách hàng phát sinh. Lực lượng có thể vô hạn cũng như hữu hạn với số lượng nhiều hoặc ít. Vị trí số 6: tham số q đại diện cho các quy tắc áp dụng để phục vụ khách hàng. Quy tắc FIFS (First In First Served) “ tới trước phục vụ trước”, quy tắc LCFS (Last Come First Served) “ tới sau phục vụ trước”, Ưu tiên PFO (Piotity First Out),… Sơ đồ hoạt động: k A S trạm B m Chú ý: Một số định ngầm được quy định cho các tham số ít quan trọng. Chẳng hạn k = ∞ m = ∞ q = FIFO Trường hợp các tham số được hiểu như định ngầm thì sẽ không cần thể hiệu trong ký hiệu Kendall. Ví dụ: Ta có dạng mô tả A/B/4/50/2000/FIFS biểu diễn một hệ thống xếp hàng có các đặc tính sau: + A là phân phối Poission. Khoảng thời gian giữa các khách hàng đến hệ thống liên tiếp nhau có tuân theo quy luật phân phối mũ. +B có phân phối lũy thừa cho thời gian phục vụ khách hàng. Khoảng thời gian yêu cầu để phục vụ mỗi khách hàng có phân phối tuỳ ý. + Hệ thống chỉ có thể chứa được 50 khách hàng trong đó có 4 khách hàng đang được phục vụ ( hay là có 4 server ) và 46 khách hàng phải xếp hàng. Mỗi lần vùng đệm đầy, bất kỳ một khách hàng nào đến cũng bị từ chối và bị huỷ cho tới khi hàng được rút ngắn lại(không ở trạng thái đầy). + Nguồn các khách hàng có sức chứa 2000 khách hàng. + Phương thức phục vụ là FIFS ( First In First Served). 2.5 Các quá trình ngẫu nhiên trong hệ thống: Quá trình ngẫu nhiên độc lập: Từ sơ đồ hoạt động có thể thấy ngay có 2 quá trình ngẫu nhiên độc lập: quá trình khách hàng xuất hiện ở đầu vào hệ thống, ký hiệu {At}tT ; quá trình 2 là quá trình phục vụ khách hàng tại đầu ra của hệ thống, ký hiệu {Bt}tT. Quá trình ngẫu nhiên đặc trưng của hệ thống: Trạng thái của hệ thống là số khách hàng trong hệ thống. Số khách hàng này biến động từ thời điểm này sang thời điểm khác và tạo thành quá trình ngẫu nhiên đặc trưng cho hệ thống. Quá trình này được ký hiệu {Xt}tT. Phần dưới đây đề tài này giới hạn chỉ xét tính chất dừng của quá trình này. Giả sử rằng Xt →Z, khi t → ∞. Khi đó Z sẽ là số khách hàng trong hệ thống ở chế độ dừng. 2.6 Mục tiêu xây dựng mô hình: Xác định phân phối dừng Z. Phương pháp xác định phân phối dừng Z là dựa vào phân phối xác suất ở đầu vào, số khách hàng tới hệ thống và phân phối xác suất ở đầu ra, thời gian phục vụ một khách hàng. Nói chung các phân phối này rất đa dạng và mỗi một phân phối lại cho một kết quả khác, nhưng phương pháp nghiên cứu là như nhau. Chúng ta sẽ minh họa phương pháp xây dựng mô hình qua hệ thống M/M/s. 2.7 Phân phối số khách hàng trong hệ thống ở chế độ dừng (biến Z): Xét hệ thống M/M/s, trong đó: Số khách hàng xuất hiện trong một đơn vị thời gian d = 1 tuân theo phân phối Poisson P(l). Thời gian phục vụ khách hàng ở tất cả các trạm là như nhau và tuân theo phân phối lũy thừa E(µ). Xét không gian trạng thái của hệ thống là E = {0,1,2,…,k,…}. Khi đó ta cần tính các xác suất: P(Z = k) = qk, với k = 0,1,2,… Sử dụng đồ thị cân bằng mô tả sự biến động của Z: 0 1 2 k-1 k k+1 Tại nút 0: Luồng ra = q0l Luồng vào = q1µ Cân bằng luồng: q0l = q1µ và q1 = (l/µ)q0. Nếu đặt j = l/µ, thì q1 = jq0. Tại nút 1: Luồng ra = q1l + q1µ Luồng vào = q0l + q22µ Cân bằng luồng: q1l + q1µ = q0l + q22µ và q2 = j2/2!q0 Bằng phương pháp quy nạp tới k = s -1, nhưng có kết quả tới s, hay với k <s: Tiếp tục xét luồng tại nút s: Luồng ra = qsl + qssµ Luồng vào = qs-1l + qs+1sµ Cân bằng luồng: qs(l + sµ) = qs-1l + qs+1sµ, và suy ra: Bằng phương pháp quy nạp suy ra với mọi k = s + m: Ta tìm q0 từ đẳng thức: q0 + q1 + … + qk + … = 1. Thay các quan hệ của qk vào đẳng thức ta được kết quả: Từ phân phối của Z, ta tìm được số khách hàng trung bình trong hệ thống: E(Z) 2.8 Luật Little và các phép trung bình đối ngẫu: Xét các biến ngẫu nhiên: T : Khoảng thời gian ngẫu nhiên xuất hiện một khách hàng. Z : Số lượng cá thể phát sinh trong T thời gian. W : Số lượng cá thể phát sinh trong một đơn vị thời gian. Khi đó: Z = WT. Luật Little phát biểu: E(Z) = E(W)E(T). Từ đây có thể ứng dụng tính trung bình về thời gian. Ta có các kết quả dưới đây: Số khách hàng trong hệ thống là Z và thời gian ở trong hệ thống của một khách hàng là T. Biết: Suy ra: Số khách hàng đang được phục vụ là G và thời gian phục vụ của một khách hàng là Ts. Đặt: Suy ra: Mặt khác: Ta lại có hệ thức: Chú ý: Hệ thức trên thể hiện số trạm hoạt động trên số trạm hiện hữu, nến nó cũng đồng thời thể hiện hiệu suất của số trạm hiện hữu. Hay j = U là hiệu suất của số trạm phục vụ trong hệ thống. Số khách hàng chờ là Y và thời gian chờ của một khách hàng là Tf: Đặt Suy ra: Mặt khác dễ thấy hệ thức: Từ đây nhận được: Tính chi phí vô ích trong hệ thống hỗ trợ quyết định: Giả thiết: Trong thời gian chờ của khách hàng chờ càng lâu thì chi phí vô ích càng lớn với đơn giá c1. Trạm phục vụ ngồi không càng lâu thì chi phí vô ích cũng tăng lên với đơn giá c2. Yêu cầu: Tính tổng từng loại chi phí vô ích và tổng gộp 2 loại chi phí vô ích để có thể quyết định: tổ chức bao nhiêu trạm phục vụ là tối ưu. Đặt: T : Là khoảng thời gian quản lý. s : Là số trạm phục vụ. Gf(s) : Là tổng chi phí vô ích do khách hàng sinh ra trong hệ thống có s trạm phục vụ. Gs(s) : Là tổng chi phí vô ích do phục vụ sinh ra với s trạm. Khi đó, Gf(s) được tính như sau: Tổng số khách hàng tới hệ thống trong T thời gian = lT. Tổng thời gian chờ của khách hàng = Suy ra: Trong khi đó, Gs(s) được tính qua: Số trạm không có khách hàng R có phân phối qs-r, r = 0, 1, …, s-1. Suy ra số trạm trung bình không có khách hàng: Khi đó: . Cuối cùng tổng gộp các chi phí vô ích: G(s) = Gf(s) + Gs(s) là mục tiêu cần xử lý với s tốt nhất. 3. BÀI TOÁN ỨNG DỤNG HỆ THỐNG HÀNG ĐỢI Bài toán kinh doanh xăng: Ở một trạm xăng với một bơm xăng người ta để ý thấy rằng thường xuyên có sự chen chúc và lộn xộn do có nhiều người chờ mua xăng. Người ta tiến hành nghiên cứu giải quyết bài toán đặt ra: “Liệu có cần thêm bơm xăng không? Và nếu có thêm thì thêm bao nhiêu để đạt hiệu quả kinh tế: doanh số lớn nhất?” Trước hết, người ta nghiên cứu tìm mật độ khách hàng tới xếp hàng mua xăng sau đó sẽ xét mật độ khách hàng được phục vụ. Khảo sát số liệu khách hàng tới mua xăng: Trong khoảng thời gian thường xuyên có khách hàng tới mua xăng (từ 8 giờ đến 16 giờ), người ta tiến hành quan sát và đếm số khách hàng tới mua xăng trong khoảng thời gian 5 phút với 100 khoảng thời gian như vậy, kế tiếp nhau hoặc không, được thực hiện. Kết quả cho trong bảng dưới đây: Số khách hàng mua xăng Tần suất quan sát 0 29 1 34 2 24 3 9 4 3 >=6 1 Cộng: 100 Bảng tần số khách hàng mua xăng Khảo sát thời gian phục vụ khách hàng: 100 khách hàng được quan sát ngẫu nhiên và người ta đo thời gian phục vụ họ. Thời gian phục vụ Số khách hàng <1’ 23 Từ 1’ – 2’ 20 Từ 2’ – 3’ 14 Từ 3’ – 4’ 12 Từ 4’ – 5’ 9 Từ 5’ – 6’ 5 Từ 6’ – 7’ 4 Từ 7’- 8’ 5 Từ 8’ – 9’ 3 Từ 9’ – 10’ 2 Từ 10’ – 11’ 1 Từ 11’ – 12’ 1 >12’ 1 Cộng 100 Bảng khảo sát thời gian phục vụ khách hàng Các bước xử lý: Bước 1: Xác định các tham số: l và µ Bước 2: Kiểm tra phân phối số khách hàng tới xếp hàng và phân Phối thời gian phục vụ 1 khách hàng theo tham số l và µ vừa ước lượng (tính c2) Bước 3: Xác định các thông số trung bình Bước 4: Xử lý số trạm tối ứu. Giải: Bước 1: Xếp hàng tuân theo phối Poisson trong từng khoảng thời gian 5’. Suy ra l như sau: 5X = số khách hàng tới trạm xăng trong từng khoảng 5’ và Ta ước lượng µ: Y = thời gian phục vụ một khách hàng ~ E(µ) và E(µ) = Bước 2: Kiểm định các tham số µ và l để xét tính phù hợp giữa số phát sinh thực tế và lý thuyết. Sử dụng phép kiểm định c2: ; d = n-1-p ni: Số quan sát tại mức i N = 100; pi xác suất ước lượng theo phân phối. n: Các mức trong bảng tần số. p: Số tham số của phân phối (p = 1, do chỉ số có l là tham số) d: Độ tự do của c2 Kiểm định “l=0,25” (Ho): dưới Ho: l=0,25 và t = 5 phút Bảng tính Số khách hàng i (1) Số quan sát thực tế ni (2) Số Pi lý thuyết (3) Số quan sát lý thuyết Npi (4) Di = |Npi - ni| (5) D2i (6) c2 (7) 0 29 0,28 28 1 1 0,03571 1 34 0,36 36 2 4 0,11111 2 24 0,23 23 1 1 0,04347 3 9 0,09 9 0 0 0 >=4 4 0,04 4 0 0 0 c2 = 0,1903 Ta tính được: n = 5, c2 = 0,1903 và d = 5 – 1 – 1 = 3 ci2(7) = (6)/(4), Di(5) = (4) – (2) Kiểm định l = 0,25; t = 5 phút c2 < c2d(0,95): chấp nhận Ho c2 >= c2d(0,95): bác bỏ Ho (Tra bảng c23(95%) = 0,325) Do c23 = 0,325 > c2 = 0,1903 Þ chấp nhận Ho hay chấp nhận l = 0,25. Kiểm định µ = 0,30 (Ho): Lập bảng tính c2 cho µ với phân phối E(µ) trên các khoảng tách biệt ở đây là các khoảng thời gian và được đại diện bởi số trung bình (Những điểm giữa của khoảng thời gian). Để dễ tính toán ta cần gôm các khoảng thời gian có phát sinh ít khách hàng. Ta nhận được bảng sau: Số lớp C (1) Các khoảng TG (ti-1 – ti) (2) TG PV TB (3) Số KH PV quan sát ni (4) Số pi LT (5) Số KH PV lý thuyết N*pi (6) Di=|Npi-ni| (7) D2i (8) c2i=(8)/(4) (9) 1 <1 phút 0,5 23 0,26 26 3 9 0,3462 2 1---2 1,5 20 0,19 19 1 1 0,0526 3 2---3 2,5 14 0,14 14 0 0 0 4 3---4 3,5 12 0,11 11 1 1 0,0909 5 4---5 4,5 9 0,08 8 1 1 0,1250 6 5---7 6 9 0,10 10 1 1 0,1 7 7---9 8 8 0,06 6 2 4 0,6667 8 >9 9 5 0,06 6 1 1 0,1667 c2 = 1,5481 Công thức tính pi: d = n-1-p = 8-1-1 = 6 Þ tra bảng c26(95%) sau đó so sánh với c2 và dễ dàng suy ra µ = 0,30 tin cậy ở mức 95% là có thể sử dụng cho tính toán. Bước 3: Do µ = 0,30 > l = 0,25 nên s >= 1 hệ thống hoạt động ở chế độ dừng khi thời gian đủ lớn (sau 30 phút khi trạm làm việc). Ta tính các thông số quan trọng: s = 1, j = j/µ = 0,25/0,3 = 5/6 Số khách hàng thường xuyên trong hệ thống là: Thời gian xếp hàng trung bình của một khách hàng là: Bước 4: Tìm giải pháp tối ưu. Bài toán kinh tế áp dụng đặt ra: Giả sử nếu có khách hàng tới mua xăng nhưng thấy số người xếp hàng > 4 người, thì người đó bỏ đi. Hãy tìm giải pháp kinh tế tối ưu (lợi nhuận tối đa) nếu: Lợi nhuận thu được từ một khách hàng mua xăng trung bình là 500đ Mở thêm cây xăng: trả lương cho một nhân viên 300.000đ/tháng (30 ngày) và khấu hao thiết bị là 150.000/tháng (30 ngày). Trường hợp s = 1 Trung bình số khách hàng tới trong ngày trong khoảng thời gian làm việc ổn định: Sáng: 8h – 10h30 Chiều: 1h30 – 4h30 Þ số thời gian tính toán là: T = 5,5 giờ Do đó: A = 5,5 x 60 x 0,25 = 83 khách hàng tới trung bình trong khoảng thời gian ổn định. Xác suất khách hàng bỏ đi nếu số khách hàng trong hệ thống >=4: pB = 1 – (p0 + p1 + p2 + p3 + p4) = j5 Trung bình số khách hàng bỏ đi trong ngày: Thiệt hại do mất khách hàng trong tháng (30 ngày): B = 33 x 500đ x 30 = 495.500đ Thiệt hại do cây xăng không có khách hàng trong tháng: Số thời gian làm việc trong ngày: C = 50 x 3,27 = 2,7 giờ Số thời gian không có khách hàng: 5,6 – 2,7 = 2,8 giờ/ngày Thiệt hại do không có khách hàng trong tháng: Lợi nhuận: I1 = 50KH x 500 x 30 – 157.000 = 593.000 đ Tổng thiệt hại: H1 = 495.000 + 157.000 = 625.000 đ Phương án tăng thêm 1 trạm bơm xăng: s = 2 Þ Khách hàng tới mua hầu như được phục vụ ngay Þ Tất cả khách hàng đều được phục vụ và chỉ có thiệt hại do không có khách hàng. Để tính thiệt hại này ta tính số trạm xăng trung bình không có khách hàng: Chú ý: Thiệt hại do không có khách hàng: D = 450.000 x 1,165 = 524.000 đ Lợi nhuận: I2 = 83 x 500 x 30 – 524.000 = 721.000 đ Phương án tăng 2 trạm bơm xăng: s = 3 Ta tính được: , Số thiệt hại do không có khách hàng: D = 450.000 x 2,167 = 975.150 đ Lợi nhuận đạt: I3 = 83 x 500 x 30 – 975.150 = 269.850 đ Kết luận: s = 2 bơm xăng thì lợi nhuận cao nhất và nhân viên làm việc nhẹ nhàng. C. KẾT LUẬN Việc ứng dụng lý thuyết mô phỏng để giải quyết các bài toán trong thực tế có ý nghĩa hết sức quan trọng, nó không những giúp các nhà doanh nghiệp giảm được chi phí mà còn hỗ trợ cho việc hoạch định các chiến lược kinh doanh. Việc xây dựng mô hình mô phỏng trong thực tế là rất khó khăn và phức tạp . Hệ thống hàng đợi có nhiều ứng dụng quan trọng trong việc phân tích và giải quyết một số bài toán thực tế. Tuy nhiên, vì thời gian có hạn, sự am hiểu về môn học còn hạn chế nên tiểu luận chỉ tập trung phân tích Hệ thống hàng đợi và một ứng dụng đơn giản của hệ thống này. Nguyện vọng tiếp theo của bản thân là cố gắng tìm hiểu sâu hơn về Hệ thống hàng đợi cùng với các ứng dụng thực tế và đa dạng hơn. Một lần nữa tôi xin chân thành cảm ơn thầy giáo PGS.TS. Trần Lộc Hùng đã giúp tôi trong quá trình tiếp cận môn học và thực hiện tiểu luận này. D. TÀI LIỆU THAM KHẢO [1] Trần Lộc Hùng, Cơ sở mô phỏng ngẫu nhiên, NXB Giáo Dục, 1997. [2] Trần Lộc Hùng, Bài giảng Mô phỏng ngẫu nhiên (Cao học CNTT 2007), Huế, 2007. [3] Phạm Văn Khánh Lý thuyết mô phỏng đại lượng ngẫu nhiên và quá trình ngẫu nhiên.