תורת העמידה בתור. בשיעור מעשי נשקול נתיב זה ונשווה את תוצאות הסימולציה עם הפתרון התיאורטי

דוגמאות לפתרון בעיות מערכת הִזדַנְבוּת

זה נדרש כדי לפתור בעיות 1-3. הנתונים הראשוניים ניתנים בטבלה. 2–4.

סימון מסוים המשמש בתורת התורים לנוסחאות:

n הוא מספר הערוצים ב-QS;

λ היא עוצמת הזרימה הנכנסת של יישומים P in;

v היא עוצמת הזרימה היוצאת של יישומים P out;

μ היא עוצמת זרימת השירות P בערך;

ρ הוא מחוון עומס המערכת (תנועה);

m הוא המספר המרבי של מקומות בתור, מה שמגביל את אורך תור הבקשות;

i הוא מספר מקורות הבקשה;

p k היא ההסתברות למצב k-ה של המערכת;

p o - ההסתברות לבטלה של המערכת כולה, כלומר ההסתברות שכל הערוצים פנויים;

p syst היא ההסתברות לקבל אפליקציה למערכת;

p ref - הסתברות דחיית הבקשה בקבלתה למערכת;

р about - ההסתברות שהיישום יקבל שירות;

A הוא התפוקה המוחלטת של המערכת;

Q הוא התפוקה היחסית של המערכת;

och - המספר הממוצע של יישומים בתור;

r הוא המספר הממוצע של יישומים בשירות;

syst הוא המספר הממוצע של יישומים במערכת;

pt - זמן ההמתנה הממוצע לפנייה בתור;

r הוא זמן ההגשה הממוצע של הבקשה, הקשור רק לבקשות השירות;

sys הוא זמן השהייה הממוצע של אפליקציה במערכת;

oj הוא הזמן הממוצע המגביל את זמן ההמתנה לאפליקציה בתור;

הוא המספר הממוצע של ערוצים עסוקים.

התפוקה המוחלטת של QS A היא המספר הממוצע של יישומים, ĸᴏᴛᴏᴩᴏᴇ יכולה להיות מוגשת על ידי המערכת ליחידת זמן.

תפוקת QS יחסי Q הוא היחס בין מספר הבקשות הממוצע שהמערכת מוגשת ליחידת זמן למספר הממוצע של בקשות שהתקבלו במהלך זמן זה.

בעת פתרון בעיות בתורים, חשוב מאוד להקפיד על הרצף הבא:

1) קביעת סוג ה-QS לפי טבלה. 4.1;

2) בחירת נוסחאות בהתאם לסוג ה-QS;

3) פתרון בעיות;

4) גיבוש מסקנות על הבעיה.

1. תכנית מוות ורבייה.אנו יודעים שברשותנו גרף מצב מסומן, אנו יכולים לכתוב בקלות את משוואות קולמוגורוב עבור הסתברויות מצבים, וגם לכתוב ולפתור משוואות אלגבריותעבור ההסתברויות הסופיות. ראוי לומר שבמקרים מסוימים המשוואות האחרונות

להחליט מראש, תרתי משמע. בפרט, ניתן לעשות זאת אם גרף המצב של המערכת הוא מה שנקרא 'סכימה של מוות ורבייה'.

גרף המדינה עבור ערכת המוות והרבייה הוא הצורה המוצגת באיור. 19.1. המוזרות של גרף זה היא שניתן להרחיב את כל מצבי המערכת לשרשרת אחת, שבה כל אחד מהמצבים הממוצעים ( ס 1 , ש 2 ,…,S n-1) מחובר באמצעות חץ קדימה ואחורה עם כל אחד מהמדינות השכנות - ימין ושמאל, והמצבים הקיצוניים (ס 0 , שנ) - עם מדינה שכנה אחת בלבד. המונח 'סכימה של מוות ורבייה' מקורו בבעיות ביולוגיות, שבהן תכנית כזו מתארת ​​את השינוי בגודל האוכלוסייה.

סכמת המוות והרבייה נמצאת לעתים קרובות מאוד בבעיות תרגול שונות, בפרט - בתורת התור, בהקשר זה, מועיל, אחת ולתמיד, למצוא את ההסתברויות הסופיות של מדינות עבורה.

נניח שכל זרימות האירועים שמעבירות את המערכת לאורך חיצי הגרף הן הפשוטות ביותר (למען הקיצור, נקרא גם את המערכת סוהתהליך המתרחש בו - הפשוט ביותר).

באמצעות הגרף באיור. 19.1, אנו מחברים ופותרים משוואות אלגבריות להסתברויות הסופיות של המצב), הקיום נובע מכך שמכל מצב אתה יכול ללכת לכל מצב אחר, מספר המצבים הוא סופי). למדינה הראשונה ס 0 יש לנו:

(19.1)

למדינה השנייה S1:

בשל (19.1), השוויון האחרון מצטמצם לטופס

איפה קלוקח את כל הערכים מ-0 עד פ.אז ההסתברויות הסופיות p0, p1,..., p n מספקים את המשוואות

(19.2)

בנוסף, עלינו לקחת בחשבון את מצב הנורמליזציה

ע 0 + ע 1 + ע 2 +…+ ע n=1. (19.3)

בואו נפתור את מערכת המשוואות הזו. מהמשוואה הראשונה (19.2) אנו מבטאים ע 1 דרך ר 0 :

ע 1 = ע 0. (19.4)

מהשני, בהתחשב (19.4), אנו מקבלים:

(19.5)

‣‣‣ מהשלישי, תוך התחשבות (19.5),

(19.6)

ובכלל, לכל ק(מ-1 עד נ):

(19.7)

הבה נשים לב לנוסחה (19.7). המונה הוא המכפלה של כל העוצמות בחצים המובילים משמאל לימין (מההתחלה עד מדינה נתונה סק), ובמכנה - מכפלת כל העוצמות בחצים המובילים מימין לשמאל (מההתחלה עד Sk).

Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, כל ההסתברויות של המדינה ר 0 , עמ' 1 , ..., р נבא לידי ביטוי באמצעות אחד מהם ( ר 0). הבה נחליף ביטויים אלה בתנאי הנורמליזציה (19.3). אנחנו מסתדרים באמצעות סוגריים ר 0:

מכאן אנו מקבלים את הביטוי עבור ר 0 :

(העלינו את הסוגריים בחזקת -1 כדי לא לכתוב שברים של שתי קומות). כל שאר ההסתברויות מתבטאות במונחים של ר 0 (ראה נוסחאות (19.4) - (19.7)). שימו לב שהמקדמים עבור ר 0 בכל אחד מהם אינם אלא חברים עוקבים בסדרה אחרי היחידה בנוסחה (19.8). אז, בחישוב ר 0 , כבר מצאנו את כל המקדמים הללו.

הנוסחאות שהתקבלו שימושיות מאוד בפתרון הבעיות הפשוטות ביותר של תורת התורים.

^ 2. נוסחה קטנה.כעת אנו מפיקים נוסחה חשובה אחת המתייחסת (עבור המשטר המגביל, הנייח) למספר הממוצע של יישומים ל syst, הממוקם במערכת התורים (כלומר מוגש או עומד בתור), וזמן השהייה הממוצע של האפליקציה במערכת W syst.

הבה ניקח בחשבון כל QS (ערוץ אחד, רב-ערוצי, מרקוביאן, לא מרקוביאן, עם תור בלתי מוגבל או מוגבל) ושני זרמים של אירועים הקשורים אליו: זרימת הלקוחות המגיעים ל-QS וזרם הלקוחות העוזבים את ה-QS. QS. אם נקבע משטר מגביל, נייח במערכת, אז המספר הממוצע של יישומים המגיעים ל-QS ליחידת זמן שווה למספר האפליקציות הממוצע היוצא ממנו: לשני הזרימות יש אותה עוצמה λ.

לציין: X(t) -מספר הבקשות שהגיעו ל-CMO לפני הרגע ט. י(ט) - מספר הבקשות שיצאו מה-CMO

עד הרגע ט.שתי הפונקציות הן אקראיות ומשתנות בפתאומיות (מוגברת באחת) ברגע הגעת הבקשות (איקס(ט)) ויציאות של בקשות (Y(t)).סוג הפונקציות X(t) ו-Y(t)מוצג באיור. 19.2; שני הקווים מדורגים, העליון הוא X(t),נמוך יותר- Y(t).ברור, לכל רגע טההבדל שלהם ז(ט)= X(t) - Y(t)אינו אלא מספר היישומים ב-QS. כאשר הקווים X(t)ו Y(t)מיזוג, אין בקשות במערכת.

קחו בחשבון פרק זמן ארוך מאוד ט(ממשיך מנטלית את הגרף הרבה מעבר לשרטוט) וחשב עבורו את מספר האפליקציות הממוצע ב-QS. זה יהיה שווה לאינטגרל של הפונקציה Z T)על מרווח זה חלקי באורך המרווח ת:

ל syst. = . (19.9) o

אבל האינטגרל הזה אינו אלא השטח של הדמות המוצללת באיור. 19.2. בואו נסתכל היטב על התמונה הזו. הדמות מורכבת ממלבנים שלכל אחד מהם גובה שווה לאחד ובסיס השווה לזמן השהייה במערכת של הסדר המקביל (הראשון, השני וכו'). בואו נציין את הזמנים האלה t 1 , t 2 ,...נכון, בסוף המרווח טכמה מלבנים ייכנסו לדמות המוצללת לא לגמרי, אלא חלקית, אבל עם דמות גדולה מספיק טהדברים הקטנים האלה לא יהיו חשובים. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, אנו יכולים להניח כי

(19.10)

כאשר הסכום חל על כל ההזמנות שהתקבלו במהלך ט.

בואו נפריד בין הימין לבין צד שמאל(.19.10) באורך המרווח ט.אנו משיגים, תוך התחשבות (19.9),

ל syst. = . (19.11)

מחלקים ומכפילים צד ימין(19.11) לעוצמה X:

ל syst. = .

אבל הגודל Tλהוא לא יותר ממספר הבקשות הממוצע שהתקבלו במהלך הזמן ^ ט.במקרה שנחלק את סכום כל הזמנים אניעל מספר הפניות הממוצע, אז נקבל את זמן השהות הממוצע של האפליקציה במערכת W syst. כך,

ל syst. = λ W syst. ,

W syst. = . (19.12)

זוהי הנוסחה הנפלאה של ליטל: לכל QS, לכל אופי של זרימת האפליקציות, לכל חלוקת זמן שירות, לכל דיסציפלינה של שירות זמן השהייה הממוצע של לקוח במערכת שווה למספר הלקוחות הממוצע במערכת חלקי עוצמת תזרים הלקוחות.

בדיוק באותו אופן, נגזרת הנוסחה השנייה של ליטל, המתייחסת לזמן הממוצע שהאפליקציה מבלה בתור ^ ו וומספר הפניות הממוצע בתור ל och:

W och = . (19.13)

עבור הפלט, זה מספיק במקום השורה התחתונה באיור. 19.2 קח פונקציה U(t)- מספר הבקשות שנותרו עד הרגע טלא מהמערכת, אלא מהתור (אם אפליקציה שנכנסה למערכת לא נכנסת לתור, אלא נכנסת מיד לשירות, אנחנו עדיין יכולים לשקול שהיא נכנסת לתור, אבל נשארת בו זמן אפס) .

הנוסחאות של ליטל (19.12) ו- (19.13) ממלאות תפקיד חשוב בתורת התורים. לרוע המזל, ברוב המדריכים הקיימים, נוסחאות אלו (הוכחו ב השקפה כלליתיחסית לאחרונה) אינם ניתנים 1).

§ 20. מערכות התורים הפשוטות ביותר ומאפייניהן

בסעיף זה, נשקול כמה מה-QS הפשוטים ביותר ונגזר ביטויים עבור המאפיינים שלהם (מדדי ביצועים). במקביל, נדגים את הטכניקות המתודולוגיות העיקריות האופייניות לתורת התורים היסודית, א'א''א. לא נעסוק במספר דגימות ה-QS שלגביהן ייגזרו הביטויים הסופיים של המאפיינים; ספר זה אינו מדריך לתיאוריית העמידה בתור (תפקיד כזה מבוצע הרבה יותר על ידי מדריכים מיוחדים). המטרה שלנו היא להציג לקורא כמה א'טריקים כדי להקל על תיאוריית התורים, שבמספר ספרים זמינים (אפילו מתיימרים להיות פופולריים) יכולים להיראות כמו אוסף של דוגמאות.

כל זרימות האירועים המעבירות QS ממדינה למדינה, בסעיף זה, נשקול את הפשוטים ביותר (מבלי לקבוע זאת כל פעם ספציפית). ביניהם יהיה מה שנקרא 'זרם השירות'. המשמעות היא זרימת הבקשות המוגשות על ידי ערוץ אחד עמוס ברציפות. בזרימה זו, למרווח בין אירועים, כמו תמיד בזרימה הפשוטה ביותר, יש התפלגות אקספוננציאלית (במדריכים רבים, במקום זאת, אומרים: זמן שירות הוא אקספוננציאלי, אנו בעצמנו נשתמש במונח זה בעתיד).

1) בספר פופולרי, ניתנת גזירה שונה במקצת, בהשוואה לאמור לעיל, של הנוסחה של ליטל. באופן כללי, היכרות עם ספר זה ('שיחה שתי') מועילה להיכרות ראשונית עם תורת העמידה בתור.

בסעיף זה, חלוקת זמן השירות האקספוננציאלית תהיה מובן מאליו, כמו תמיד עבור המערכת ה"פשוטה ביותר".

אנו נציג את מאפייני היעילות של ה-QS הנבחנים במהלך המצגת.

^ 1. פ-ערוץ QS עם כשלים(בעיית ארלנג). כאן אנו רואים את אחת הבעיות הראשונות בזמן, ''קלאסית'' של תורת התורים;

בעיה זו נבעה מהצרכים המעשיים של הטלפוניה ונפתרה בתחילת המאה שלנו על ידי המתמטיקאי הדני ארלנט. המשימה מוגדרת כך: יש פערוצים (קווי תקשורת), המקבלים זרימה של יישומים בעוצמה λ. לזרימת השירות יש עוצמה μ (ההדדיות של זמן השירות הממוצע טעל אודות). מצא את ההסתברויות הסופיות של מצבי ה-QS, כמו גם את המאפיינים של היעילות שלו:

^א-תפוקה מוחלטת, כלומר, המספר הממוצע של יישומים שהוגשו ליחידת זמן;

ש-תפוקה יחסית, כלומר, החלק הממוצע של בקשות נכנסות המוגשות על ידי המערכת;

^ P otk- ההסתברות לכישלון, כלומר העובדה שהבקשה משאירה את ה-QS ללא הגשה;

ק-מספר ממוצע של ערוצים עמוסים.

פִּתָרוֹן. מצבי מערכת ^S(QS) ימוספרו בהתאם למספר הבקשות במערכת (במקרה זה, זה עולה בקנה אחד עם מספר הערוצים העסוקים):

S 0 -אין יישומים ב-SMO,

S 1 -יש בקשה אחת ב-QS (ערוץ אחד תפוס, השאר בחינם),

סק-ב-SMO הוא קיישומים ( קהערוצים עמוסים, השאר בחינם),

S n -ב-SMO הוא פיישומים (כולם נהערוצים עמוסים).

גרף מצב ה-QS מתאים לתכנית המוות ברבייה (איור 20.1). בואו נסמן את הגרף הזה - הניחו את עוצמת זרימות האירוע ליד החצים. מ ס 0 אינץ' S1המערכת מועברת על ידי זרימת בקשות בעוצמה λ (ברגע שמגיעה בקשה, המערכת קופצת מ S0ב S1).אותה זרימת יישומים מתרגמת

מערכת מכל מצב שמאלי למצב הימני הסמוך (ראה את החצים העליונים באיור 20.1).

בואו נניח את עוצמת החצים התחתונים. תן למערכת להיות במדינה ^S 1 (ערוץ אחד עובד). הוא מייצר μ שירותים ליחידת זמן. שמנו למטה ליד החץ ס 1 →סעוצמה 0 μ. עכשיו דמיינו שהמערכת נמצאת במדינה S2(שני ערוצים עובדים). כדי שהיא תלך אליה S 1,יש צורך שהערוץ הראשון או השני יסיים את השירות; העוצמה הכוללת של זרימות השירות שלהם היא 2μ; שים אותו בחץ המתאים. זרימת השירות הכוללת שניתנת על ידי שלושת הערוצים היא בעוצמה של 3μ, קערוצים - ק"מ.הנחנו את העוצמות הללו בחצים התחתונים באיור. 20.1.

ועכשיו, בידיעה של כל העוצמות, נשתמש בנוסחאות מוכנות (19.7), (19.8) להסתברויות הסופיות בסכימה של מוות ורבייה. לפי הנוסחה (19.8) נקבל:

מונחי פירוק יהיו המקדמים עבור p 0בביטויים עבור p1

שימו לב שנוסחאות (20.1), (20.2) אינן כוללות את העוצמות λ ו-μ בנפרד, אלא רק כיחס λ/μ. לציין

λ/μ = ρ (20.3)

ונכנה את הערך של ''העוצמה המופחתת של זרימת הבקשות'. המשמעות שלו היא המספר הממוצע של בקשות המגיעות במשך זמן השירות הממוצע של בקשה אחת. באמצעות סימון זה, אנו משכתבים נוסחאות (20.1), (20.2) בצורה:

נוסחאות (20.4), (20.5) להסתברויות המצב הסופי נקראות נוסחאות ארלנג - לכבודו של מייסד תורת התורים. רוב הנוסחאות האחרות של התיאוריה הזו (היום יש יותר מהן מאשר פטריות ביער) אינן נושאות שמות מיוחדים.

Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, נמצאות ההסתברויות הסופיות. על בסיסם, נחשב את מאפייני היעילות של QS. ראשית אנו מוצאים ^ P otk. - ההסתברות שהבקשה הנכנסת תידחה (לא תוגש). לשם כך, יש צורך שכל פהערוצים היו עמוסים, אז

ר otk = ר n = . (20.6)

מכאן אנו מוצאים את התפוקה היחסית - ההסתברות שהבקשה תוגש:

ש = 1 - פלִפְתוֹחַ = 1 - (20.7)

אנו משיגים את התפוקה המוחלטת על ידי הכפלת עוצמת זרימת הבקשות λ ב ש:

A = λQ = λ. (20.8)

נותר רק למצוא את המספר הממוצע של ערוצים עסוקים ק.ניתן היה למצוא ערך זה 'א' ישירות', כמו ערך צפוימשתנה אקראי בדיד עם ערכים אפשריים 0, 1, ..., פוההסתברויות של ערכים אלו p 0 p 1 , ..., p n:

ק = 0 · p 0 +אחד · p 1 + 2 · p 2 + ... + n · P n .

מחליף כאן ביטויים (20.5) עבור רק , (ק = 0, 1, ..., P)וביצוע הטרנספורמציות המתאימות, נשיג בסופו של דבר את הנוסחה הנכונה עבורה ק.אבל נדפיס את זה הרבה יותר קל (הנה זה, אחד הטריקים הקטנים'!) ואכן, אנחנו יודעים את רוחב הפס המוחלט אבל.אין זו אלא עוצמת זרימת האפליקציות שמשרתת המערכת. כל מועסק ב.י.של ליחידת זמן משרת בממוצע |1 בקשות. אז המספר הממוצע של ערוצים עמוסים הוא

k = A/μ, (20.9)

או, נתון (20.8),

k = (20.10)

אנו מעודדים את הקורא לעבד את הדוגמה בעצמו.
מתארח ב- ref.rf
יש תחנת תקשורת עם שלושה ערוצים ( נ= 3), עוצמת זרימת היישומים λ = 1.5 (יישומים לדקה); זמן שירות ממוצע לכל בקשה ט vol = 2 (דקות), כל זרימות האירועים (כמו בכל הפסקה הזו) הן הפשוטות ביותר. מצא את הסתברויות המצב הסופי ואת מאפייני הביצועים של ה-QS: א, ש, פאוקיי, ק.ליתר ביטחון, הנה התשובות: ע 0 = 1/13, ע 1 = 3/13, ע 2 = 9/26, עמ' 3 = 9/26 ≈ 0,346,

אבל≈ 0,981, ש ≈ 0,654, פפתוח ≈ 0.346, k ≈ 1,96.

ניתן לראות מהתשובות, אגב, שה-CMO שלנו עמוס במידה רבה: מתוך שלושה ערוצים, כשניים עמוסים בממוצע, וכ-35% מהבקשות הנכנסות נותרו ללא מתן שירות. אנו מזמינים את הקורא, אם הוא סקרן ולא עצלן, לברר: כמה ערוצים יידרשו על מנת לספק לפחות 80% מהפניות הנכנסות? ואיזה חלק מהערוצים יהיה בטל בו זמנית?

יש כבר איזה רמז אופטימיזציה.למעשה, התוכן של כל ערוץ עולה סכום מסוים ליחידת זמן. יחד עם זאת, כל אפליקציית שירות מביאה הכנסה מסוימת. הכפלת הכנסה זו במספר הבקשות הממוצע אבל,בשירות ליחידת זמן, נקבל את ההכנסה הממוצעת מ-CMO ליחידת זמן. מטבע הדברים, עם גידול במספר הערוצים, ההכנסה הזו גדלה, אך גם העלויות הכרוכות בתחזוקת הערוצים גדלות. מה יגבר - גידול בהכנסות או בהוצאות? זה תלוי בתנאי המבצע, בדמי שירות א' ובעלות אחזקת הערוץ. הכרת הערכים הללו, תוכל למצוא את מספר הערוצים האופטימלי, החסכוני ביותר. לא נפתור בעיה כזו, נשאיר הכל לאותו "קורא לא עצלן וסקרן" להמציא דוגמה ולפתור אותה. באופן כללי, המצאת בעיות מפתחת יותר מאשר פתרון של אלה שכבר נקבעו על ידי מישהו.

^ 2. QS חד ערוץ עם תור בלתי מוגבל.בפועל, QS ערוץ אחד עם תור הוא די נפוץ (רופא המשרת חולים; טלפון ציבורי עם דוכן אחד; מחשב שממלא הזמנות משתמשים). בתורת התור, QS חד-ערוץ עם תור תופס מקום מיוחד (רוב הנוסחאות האנליטיות שהתקבלו עד כה עבור מערכות לא-מרקוביניות שייכות ל-QS כאלה). מסיבה זו, נקדיש תשומת לב מיוחדת ל-QS חד ערוץ עם תור.

שיהיה QS חד ערוצי עם תור שלא מוטלות עליו הגבלות (לא על אורך התור, ולא על זמן ההמתנה). QS זה מקבל זרימה של בקשות בעוצמה λ ; לזרימת השירות יש עוצמה μ הפוכה לזמן השירות הממוצע של הבקשה טעל אודות. נדרש למצוא את ההסתברויות הסופיות של מצבי ה-QS, כמו גם את המאפיינים של יעילותו:

ל syst. - מספר יישומים ממוצע במערכת,

W syst. - זמן שהייה ממוצע של הבקשה במערכת,

^ ל אוך- המספר הממוצע של יישומים בתור,

W och - הזמן הממוצע שאפליקציה מבלה בתור,

פזאן - ההסתברות שהערוץ תפוס (מידת הטעינה של הערוץ).

לגבי המוחלט רוחב פס אבלוקרוב משפחה ש,אז אין צורך לחשב אותם:

בשל העובדה שהתור אינו מוגבל, כל בקשה תוגש במוקדם או במאוחר, בקשר לכך A = λ,מאותה הסיבה ש= 1.

פִּתָרוֹן. מצבי המערכת, כבעבר, ימוספרו לפי מספר האפליקציות ב-QS:

ס 0 - הערוץ בחינם

ס 1 - הערוץ תפוס (משרת את הבקשה), אין תור,

ס 2 - הערוץ תפוס, בקשה אחת נמצאת בתור,

ס k - הערוץ תפוס, ק- 1 יישומים נמצאים בתור,

תיאורטית, מספר המדינות אינו מוגבל בשום דבר (אין סוף). לגרף המדינה יש את הצורה המוצגת באיור. 20.2. זוהי תוכנית של מוות ורבייה, אבל עם מספר אינסופי של מצבים. על כל החצים, זרימת הבקשות בעוצמה λ מעבירה את המערכת משמאל לימין, ומימין לשמאל - זרימת השירות בעוצמה μ.

קודם כל, הבה נשאל את עצמנו, האם יש הסתברויות סופיות במקרה הזה? אחרי הכל, מספר המצבים של המערכת הוא אינסופי, ובאופן עקרוני, ב t → ∞התור יכול לגדול ללא הגבלת זמן! כן, זה נכון: ההסתברויות הסופיות ל-QS כזה לא תמיד קיימות, אלא רק כשהמערכת לא עמוסה מדי. ניתן להוכיח שאם ρ הוא בהחלט פחות מאחד (ρ< 1), то финальные вероятности существуют, а при ρ ≥ 1 очередь при ט→ ∞ גדל ללא הגבלה. עובדה זו נראית "בלתי מובנת" במיוחד עבור ρ = 1. נראה כי אין דרישות בלתי אפשריות למערכת: במהלך השירות של בקשה אחת, בממוצע, מגיעה בקשה אחת, והכל אמור להיות מסודר, אבל במציאות זה לא. עבור ρ = 1, ה-QS מתמודד עם זרימת הבקשות רק אם הזרימה הנתונה היא סדירה, וגם זמן השירות אינו אקראי, שווה למרווח בין הבקשות. במקרה זה לא יהיה תור כלל ב-QS, הערוץ יהיה עמוס באופן שוטף ויוציא באופן קבוע בקשות מטופלות. אבל ברגע שזרימת הבקשות או זרימת השירות יהפכו לפחות מעט אקראית, התור כבר יגדל ללא הגבלת זמן. בפועל, זה לא קורה רק בגלל שא'אן אינסוף פניות בתור' הוא הפשטה. הנה כמה טעויות שעלולות להוביל להחלפה משתנים אקראייםהציפיות המתמטיות שלהם!

אבל בואו נחזור ל-QS החד-ערוץ שלנו עם תור בלתי מוגבל. למהדרין, הנוסחאות להסתברויות הסופיות בסכימה של מוות ורבייה נגזרו על ידינו רק למקרה של מספר סופי של מצבים, אבל בואו ניקח חירויות - נשתמש בהן למספר אינסופי של מצבים. הבה נחשב את ההסתברויות הסופיות של מצבים לפי נוסחאות (19.8), (19.7). במקרה שלנו, מספר האיברים בנוסחה (19.8) יהיה אינסופי. אנחנו מקבלים ביטוי עבור p 0:

ע 0 = -1 =

\u003d (1 + p + p 2 + ... + p k + ... .) -1. (20.11)

הסדרה בנוסחה (20.11) היא התקדמות גיאומטרית. אנחנו יודעים את זה עבור ρ< 1 ряд сходится - это бесконечно убывающая геометрическая прогрессия со знаменателœем р.
מתארח ב- ref.rf
עבור p ≥ 1, הסדרה מתפצלת (שהיא הוכחה עקיפה, אם כי לא קפדנית, להסתברויות המצב הסופי p 0 , p 1 , ..., p k , ...קיים רק עבור r<1). Теперь предположим, что это условие выполнено, и ρ <1. Суммируя прогрессию в (20.11), имеем

1 + ρ + ρ 2 + ... + ρ k + ... = ,

ע 0 = 1 - עמ'. (20.12)

הסתברויות p 1 , p 2 , ..., p k ,... ניתן למצוא לפי הנוסחאות:

p1 = ρ p 0, p 2= ρ2 p 0 ,…,p k = ρ p0, ...,

מכאן, בהתחשב (20.12), אנו מוצאים לבסוף:

p1= ρ (1 - ρ), p2= ρ 2 (1 - ρ), . . . , p k =ρ ק(1 - p), . . .(20.13)

כפי שאתה יכול לראות, ההסתברויות p0, p1, ..., p k,...יוצרים התקדמות גיאומטרית עם המכנה p.
מתארח ב- ref.rf
באופן מוזר, הגדול שבהם p 0 -ההסתברות שהערוץ יהיה בחינם בכלל. לא משנה עד כמה המערכת עמוסה בתור, אם רק היא יכולה בכלל להתמודד עם זרימת היישומים (ρ<1), самое вероятное число заявок в системе будет 0.

מצא את המספר הממוצע של יישומים ב-QS ^L syst. . כאן אתה צריך להתעסק קצת. ערך אקראי Z-מספר בקשות במערכת - יש ערכים אפשריים 0, 1, 2, .... ק,...עם הסתברויות p0, p 1 , p 2 , ..., p k , ...הציפייה המתמטית שלו היא

למערכת = 0 p 0 +אחד · ע 1 + 2 ע 2 +…+ק · ע k +…= (20.14)

(הסכום נלקח לא מ-0 ל-∞, אלא מ-1 ל-∞, שכן איבר האפס שווה לאפס).

אנו מחליפים לנוסחה (20.14) את הביטוי עבור p k (20.13):

ל syst. =

כעת נוציא את הסימן של הסכום ρ (1-ρ):

ל syst. = ρ(1-ρ)

כאן אנו מיישמים שוב את האטריקא: קρ ק-1 אינו אלא הנגזרת ביחס ל- ρ של הביטוי ρ ק; אומר,

ל syst. = ρ(1-ρ)

על ידי החלפת פעולות ההבחנה והסיכום, אנו משיגים:

ל syst. = ρ (1-ρ) (20.15)

אבל הסכום בנוסחה (20.15) אינו אלא סכום של התקדמות גיאומטרית פוחתת אינסופית עם האיבר הראשון ρ והמכנה ρ; כמות זו

שווה ל , והנגזרת שלו . החלפה של ביטוי זה לתוך (20.15), נקבל:

למערכת = . (20.16)

ובכן, עכשיו בואו ניישם את הנוסחה של ליטל (19.12) ונמצא את זמן השהייה הממוצע של אפליקציה במערכת:

W syst = (20.17)

מצא את המספר הממוצע של יישומים בתור ל och. נטען כדלקמן: מספר האפליקציות בתור שווה למספר האפליקציות במערכת פחות מספר האפליקציות בשירות. אז (לפי כלל התוספת של ציפיות מתמטיות), המספר הממוצע של פניות בתור ל pt שווה למספר האפליקציות הממוצע במערכת למערכת פחות המספר הממוצע של בקשות בשירות. מספר הבקשות בשירות חייב להיות אפס (אם הערוץ פנוי) או אחד (אם הוא תפוס). התוחלת המתמטית של משתנה אקראי כזה שווה להסתברות שהערוץ תפוס (סימנו את זה רזאן). מובן מאליו, ר zan שווה לאחד פחות ההסתברות p 0שהערוץ בחינם: L ext והזמן הממוצע של המתנה זו Wחיצוני (שתי הכמויות האחרונות קשורות לפי הנוסחה של ליטל). לבסוף, מצא את סך הקנס היומי W, אותו תצטרך התחנה לשלם עבור ירידת מרץ של רכבות על פסים חיצוניים, אם התחנה משלמת קנס a (רובל) עבור שעה אחת של ירידת מרץ של רכבת אחת. ליתר ביטחון, הנה התשובות: ל syst. = 2 (הרכב), W syst. = 1 (שעה), לנקודות = 4/3 (הרכב), W pt = 2/3 (שעות), לחיצוני = 16/27 (הרכב), Wחיצוני = 8/27 ≈ 0.297 (שעות). העונש היומי הממוצע W על המתנה לרכבות על מסילות חיצוניות מתקבל על ידי הכפלת מספר הרכבות הממוצע המגיעות לתחנה ביום, זמן ההמתנה הממוצע לרכבות על מסילות חיצוניות וקנס שעתי. א: W ≈ 14.2 א.

^ 3. ערוץ מחדש של QS עם תור בלתי מוגבל.דומה לחלוטין לבעיה 2, אבל קצת יותר מסובכת, הבעיה של נ- ערוץ QS עם תור בלתי מוגבל. מספור המדינות הוא שוב בהתאם למספר היישומים במערכת:

נ<1. В случае если ρ/נ≥ 1, התור גדל עד אינסוף.

נניח שהתנאי ρ/ נ < 1 выполнено, и финальные вероятности существуют. Применяя всœе те же формулы (19.8), (19.7) для схемы гибели и размножения, найдем эти финальные вероятности. В выражении для p 0תהיה סדרה של איברים המכילים פקטוריאלים, בתוספת סכום של התקדמות גיאומטרית פוחתת אינסופית עם המכנה ρ/ נ. לסכם את זה, אנחנו מוצאים

(20.22)

עכשיו בואו נמצא את המאפיינים של יעילות QS. מבין אלה, הכי קל למצוא את המספר הממוצע של ערוצים עסוקים ק== λ/μ, = ρ (זה נכון בדרך כלל עבור כל QS עם תור בלתי מוגבל). מצא את המספר הממוצע של יישומים במערכת למערכת ומספר האפליקציות הממוצע בתור ל och. מבין אלה, קל יותר לחשב את השני, לפי הנוסחה

ל och =

ביצוע הטרנספורמציות המתאימות לפי המדגם של בעיה 2

(עם בידול של הסדרה), אנו מקבלים:

ל och = (20.23)

הוספת אליו את המספר הממוצע של אפליקציות בשירות (זה גם המספר הממוצע של ערוצים עסוקים) k =ρ, נקבל:

למערכת = ל och + ρ. (20.24)

חלוקת ביטויים עבור לאוח ו למערכת על λ , באמצעות הנוסחה של ליטל, אנו מקבלים את זמן השהייה הממוצע של אפליקציה בתור ובמערכת:

(20.25)

עכשיו בואו נפתור דוגמה מעניינת.
מתארח ב- ref.rf
משרד כרטיסי רכבת עם שני חלונות הוא QS דו-ערוצי עם תור בלתי מוגבל שמתבסס מיד לשני חלונות (אם חלון אחד פנוי, הנוסע הבא בתור לוקח אותו). הקופה מוכרת כרטיסים בשתי נקודות: A ו בְּ.עוצמת זרם האפליקציות (נוסעים שרוצים לקנות כרטיס) לשתי הנקודות א' וב'זהה: λ A = λ B = 0.45 (נוסע לדקה), ובסך הכל הם יוצרים זרימה כללית של יישומים בעוצמה של λ A + λB = 0.9. קופאי מקדיש בממוצע שתי דקות לשרת נוסע. הניסיון מלמד כי תורים מצטברים במשרד הכרטיסים, הנוסעים מתלוננים על איטיות השירות. אבלובתוך בְּ,ליצור שני משרדי כרטיסים מיוחדים (חלון אחד בכל אחד), למכור כרטיסים אחד - רק לנקודה אבל, השני - רק לעניין בְּ.תקינות ההצעה הזו שנויה במחלוקת - יש הטוענים שהתורים יישארו זהים. נדרש לבדוק את תועלת ההצעה בחישוב. מכיוון שאנו יכולים לחשב את המאפיינים רק עבור ה-QS הפשוט ביותר, נניח שכל זרימות האירועים הן הפשוטות ביותר (זה לא ישפיע על הצד האיכותי של המסקנות).

ובכן, בוא ניגש לעניינים. הבה נבחן שתי אפשרויות לארגון מכירת כרטיסים - הקיימת והמוצעת.

אפשרות I (קיימת). QS דו-ערוצי מקבל זרימה של יישומים בעוצמה של λ = 0.9; עוצמת זרימת תחזוקה μ = 1/2 = 0.5; ρ = λ/μ = l.8. מאז ρ/2 = 0.9<1, финальные вероятности существуют. По первой формуле (20.22) находим p 0 ≈ 0.0525. הממוצע, מספר האפליקציות בתור נמצא לפי הנוסחה (20.23): L och ≈ 7.68; הזמן הממוצע של הלקוח בתור (לפי הראשונה מהנוסחאות (20.25)), שווה ל- Wנקודות ≈ 8.54 (דקות).

אפשרות II (מוצעת). יש צורך לשקול שני ערוץ QS אחד (שני חלונות מיוחדים); כל אחד מקבל זרימת בקשות בעוצמה λ = 0.45; μ . עדיין שווה ל-0.5; ρ = λ/μ = 0.9<1; финальные вероятности существуют. По формуле (20.20) находим среднюю длину очереди (к одному окошку) ל och = 8.1.

הנה אחד בשבילך! אורך התור, מסתבר, לא רק שלא ירד, אלא גדל! אולי זמן ההמתנה הממוצע בתור ירד? בוא נראה. דליה לנקודות על λ = 0.45, נקבל Wנקודות ≈ 18 (דקות).

זה הרציונליזציה! במקום לרדת, גם אורך התור הממוצע וגם זמן ההמתנה הממוצע בו גדלו!

בואו ננסה לנחש למה זה קרה? לאחר שחשבנו על המוח שלנו, הגענו למסקנה: זה קרה מכיוון שבגרסה הראשונה (QS דו-ערוצית) חלקיק הזמן הממוצע שאינו פעיל הוא פחות

דוגמאות לפתרון בעיות של מערכות תורים - הקונספט והסוגים. סיווג ותכונות של הקטגוריה "דוגמאות לפתרון בעיות של מערכות תורים" 2017, 2018.

לא פעם, כאשר מנתחים מערכות כלכליות, יש לפתור את מה שנקרא בעיות תור שמתעוררות במצב הבא. אפשר לנתח את מערכת אחזקת הרכב המורכבת ממספר מסוים של תחנות בעלות קיבולות שונות. בכל תחנה (אלמנט מערכת), עשויים להתרחש לפחות שני מצבים אופייניים:

1. מספר הפניות גבוה מדי עבור התחנה הזו, יש תורים וצריך לשלם על עיכובים בשירות;
2. התחנה מקבלת מעט מדי בקשות וכעת כבר צריך לקחת בחשבון את ההפסדים שנגרמו מהשבתת התחנה.

ברור כי מטרת ניתוח המערכת במקרה זה היא לקבוע קשר כלשהו בין הפסדי הכנסה עקב תוריםוהפסד עקב רק אניתחנות.

תורת התורים- חלק מיוחד בתורת המערכות הוא חלק בתורת ההסתברות בו לומדים מערכות תורים באמצעות מודלים מתמטיים.

מערכת תורים (QS)- זהו מודל הכולל: 1) זרימה אקראית של דרישות, שיחות או לקוחות הזקוקים לשירות; 2) האלגוריתם ליישום שירות זה; 3) ערוצים (התקנים) לתחזוקה.

דוגמאות ל-CMOs הם קופות, תחנות דלק, שדות תעופה, ספקים, מספרות, רופאים, מרכזיות טלפון ומתקנים אחרים המשרתים יישומים מסוימים.

בעיית תורת התוריםמורכבת בפיתוח המלצות לבנייה רציונלית של QS וארגון רציונלי של עבודתם על מנת להבטיח יעילות שירות גבוהה בעלויות אופטימליות.

המאפיין העיקרי של בעיות במעמד זה הוא התלות הברורה של תוצאות הניתוח וההמלצות שהתקבלו בשני גורמים חיצוניים: תדירות הקבלה ומורכבות הפקודות (ומכאן זמן ביצוען).

נושא תורת התורים הוא יצירת קשר בין אופי זרם האפליקציות, ביצוע ערוץ שירות נפרד, מספר הערוצים ויעילות השירות.

כפי ש מאפייני QSנחשב:

• האחוז הממוצע של פניות שנדחות ומשאירות את המערכת ללא שירות;
• זמן השבתה ממוצע של ערוצים בודדים ושל המערכת כולה;
• זמן המתנה ממוצע בתור;
• ההסתברות שהבקשה שהתקבלה תינתן מיד;
• חוק חלוקת אורך התורים ואחרים.

אנו מוסיפים כי בקשות (דרישות) נכנסות ל-QS באופן אקראי (בזמנים אקראיים), עם נקודות של עיבוי ונדירות. זמן השירות של כל דרישה הוא גם אקראי, ולאחר מכן ערוץ השירות פנוי ומוכן למלא את הדרישה הבאה. לכל QS, בהתאם למספר הערוצים והביצועים שלהם, יש רוחב פס מסוים. תפוקת SMOאולי מוּחלָט(מספר ממוצע של בקשות שהוגשו ליחידת זמן) ו קרוב משפחה(יחס ממוצע בין מספר הבקשות שהוגשו למספר המוגשות).

3.1 מודלים של מערכות תורים.

ניתן לאפיין כל QS על ידי הביטוי: (א ב ג ד ה ו) , איפה

א - הפצה של זרימת הקלט של יישומים;

ב - הפצה של זרימת הפלט של יישומים;

ג - תצורה של מנגנון השירות;

ד – משמעת בתור;

ה – בלוק המתנה;

ו הוא הקיבולת של המקור.

עכשיו בואו נסתכל מקרוב על כל תכונה.

זרם קלט של יישומים- מספר הבקשות שהתקבלו במערכת. מאופיין בעוצמת זרימת הקלט ל.

זרימת פלט של יישומים- מספר האפליקציות המוגשות על ידי המערכת. מאופיין בעוצמת זרימת הפלט M.

הגדרות מערכתמרמז על המספר הכולל של ערוצים וצמתי שירות. SMO עשוי להכיל:

1. ערוץ אחדשירותים (מסלול אחד, ספק אחד);
2. ערוץ שירות אחד, כולל מספר צמתים טוריים(מזנון, מרפאה, מסוע);
3. כמה ערוצים דומיםשירותים מחוברים במקביל (תחנות דלק, דלפק מידע, תחנת רכבת).

לפיכך, ניתן להבחין בין QS חד ורב ערוצי.

מצד שני, אם כל ערוצי השירות ב-QS תפוסים, אז האפליקציה שניגשת אליה עשויה להישאר בתור, או לעזוב את המערכת (לדוגמה, קופת חיסכון ומרכזית טלפון). במקרה זה, אנחנו מדברים על מערכות עם תור (ממתין) ומערכות עם כשלים.

תורהוא אוסף יישומים שנכנסו למערכת לצורך שירות וממתינים לשירות. התור מאופיין באורך התור ובמשמעת שלו.

משמעת בתורהוא הכלל לטיפול בבקשות מהתור. הסוגים העיקריים של תורים כוללים את הדברים הבאים:

1. PERPPO (כל הקודם זוכה) הוא הסוג הנפוץ ביותר;
2. POSPPO (כל הקודם זוכה);
3. SOP (בחירה אקראית של יישומים) - ממאגר הנתונים.
4. יחסי ציבור - שירות עדיפות.

אורך התוראולי

• בלתי מוגבל - אז מדברים על מערכת עם ציפייה טהורה;
• שווה לאפס - אז מדברים על מערכת עם כשלים;
• מוגבל באורך (מערכת מסוג מעורב).

בלוק המתנה– "קיבולת" המערכת - סך כל האפליקציות במערכת (בתור ובשירות). בדרך זו, e=c+ד.

קיבולת מקורשיוצר בקשות שירות הוא המספר המרבי של בקשות שיכולות להיכנס ל-QS. לדוגמה, בשדה תעופה, קיבולת המקור מוגבלת במספר כל המטוסים הקיימים, וקיבולת המקור של מרכזיית טלפון שווה למספר תושבי כדור הארץ, כלומר. זה יכול להיחשב בלתי מוגבל.

מספר דגמי QS מתאים למספר השילובים האפשריים של רכיבים אלו.

3.2 זרם קלט של דרישות.

עם כל פרק זמן א, א+ ט ], הבה נקשר משתנה אקראי איקס, שווה למספר הבקשות שהתקבלו במערכת במהלך הזמן ט.

זרימת הבקשות נקראת יַצִיב, אם חוק ההפצה אינו תלוי בנקודה הראשונית של המרווח א, אך תלוי רק באורך המרווח הנתון ט. למשל, זרימת האפליקציות למרכזית הטלפון במהלך היום ( ט\u003d 24 שעות) לא יכול להיחשב נייח, אבל בין 13 ל 14 שעות ( ט\u003d 60 דקות) - אתה יכול.

הזרימה נקראת ללא אפקט לוואי, אם ההיסטוריה של הזרימה לא תשפיע על קבלת דרישות בעתיד, כלומר. הדרישות אינן תלויות זו בזו.

הזרימה נקראת רגיל, אם לא יותר מבקשה אחת יכולה להיכנס למערכת בפרק זמן קצר מאוד. לדוגמה, הזרם למספרה הוא רגיל, אבל לא למשרד הרישום. אבל אם כמשתנה אקראי איקסשקלו זוגות של בקשות הנכנסות למשרד הרישום, ואז זרימה כזו תהיה רגילה (כלומר, לפעמים ניתן לצמצם זרימה יוצאת דופן לזרם רגיל).

הזרימה נקראת הכי פשוט, אם הוא נייח, ללא אפקט שלאחר ורגיל.

משפט ראשי.אם הזרימה היא הפשוטה ביותר, אז ה-r.v. X [ א . + ט] מופץ לפי חוק Poisson, כלומר. .

תוצאה 1. הזרימה הפשוטה ביותר נקראת גם זרימת Poisson.

תוצאה 2. M(איקס)= M(איקס [ א , א + ט ] )= לט, כלומר בְּמַהֲלָך ט לטיישומים. לכן, ליחידת זמן אחת המערכת מקבלת בממוצע ליישומים. ערך זה נקרא עָצמָהזרם קלט.

שקול דוגמה .

הסטודיו מקבל בממוצע 3 פניות ביום. בהנחה שהזרימה תהיה הפשוטה ביותר, מצא את ההסתברות שמספר הבקשות יהיה לפחות 5 ביומיים הקרובים.

פִּתָרוֹן.

לפי המשימה, ל=3, ט=2 ימים, זרם קלט Poisson, נ ³5. בעת פתרון, נוח להציג את האירוע ההפוך, המורכב מכך שבמהלך הזמן טיתקבלו פחות מ-5 בקשות. לכן, לפי נוסחת הפואסון, אנחנו מקבלים

^

3.3 מצב המערכת. מטריצה ​​וגרף של מעברים.

ברגע אקראי בזמן, ה-QS עובר ממצב אחד לאחר: מספר הערוצים התפוסים, מספר הבקשות והתורים וכו', משתנה. כך, ה-QS עם נערוצים ואורך תור שווה ל M, יכול להיות באחד מהמצבים הבאים:

ה 0 - כל הערוצים בחינם;

ה 1 - ערוץ אחד תפוס;

ה נ- כל הערוצים תפוסים;

ה נ +1 - כל הערוצים תפוסים ובקשה אחת נמצאת בתור;

ה נ + M– כל הערוצים וכל המקומות בתור תפוסים.

מערכת דומה עם כשלים יכולה להיות במדינות ה 0 – ה נ .

עבור QS עם ציפייה טהורה, יש קבוצה אינסופית של מצבים. בדרך זו, מַצָב ה נ QS בזמן ט היא הכמות נ אפליקציות (דרישות) שנמצאות במערכת בזמן נתון, כלומר. נ= נ(ט) - ערך אקראי, ה נ (ט) הן התוצאות של משתנה מקרי זה, ו פ נ (ט) היא ההסתברות שהמערכת תהיה במדינה ה נ .

אנחנו כבר מכירים את מצב המערכת. שימו לב שלא כל המצבים של המערכת שווים. מצב המערכת נקרא מָקוֹראם המערכת יכולה לעזוב את המצב הזה אבל לא יכולה לחזור אליו. מצב המערכת נקרא מְבוּדָד,אם המערכת לא יכולה לצאת או להיכנס למצב זה.

כדי לדמיין את התמונות של מצבי המערכת, נעשה שימוש בדיאגרמות (מה שנקרא גרפי מעבר), שבהן החצים מציינים את המעברים האפשריים של המערכת ממצב אחד למשנהו, כמו גם את ההסתברויות למעברים כאלה.

איור 3.1 - גרף מעבר

Comp.	E 0	E 1	E 2
E 0	P 0.0	P 0.1	P 0.2
E 1	P 1.0	R 1.1	R 1.2
E 2	R 2.0	R 2.2	R 2.2

גם לפעמים נוח להשתמש במטריצת המעבר. במקרה זה, העמודה הראשונה פירושה המצבים ההתחלתיים של המערכת (נוכחי), ולאחר מכן ניתנות ההסתברויות למעבר ממצבים אלה לאחרים.

מאז המערכת תעבור בהכרח מאחד

מצב לאחר, אז סכום ההסתברויות בכל שורה תמיד שווה לאחד.

3.4 QS חד ערוץ.

3.4.1 QS חד ערוצי עם כשלים.

נשקול מערכות העומדות בדרישות:

(P/E/1):(–/1/¥) . נניח גם שזמן השירות של לקוח אינו תלוי במספר הלקוחות הנכנסים למערכת. כאן ולמטה, "P" פירושו שזרימת הקלט מופצת לפי חוק Poisson, כלומר. הפשוטה ביותר, "E" פירושו שזרימת הפלט מופצת באופן אקספוננציאלי. גם כאן ולהלן, הנוסחאות העיקריות ניתנות ללא הוכחה.

עבור מערכת כזו, שני מצבים אפשריים: ה 0 - המערכת חינמית ו ה 1 - המערכת תפוסה. בואו ניצור מטריצת מעבר. בוא ניקח דטהוא כמות אינסופית של זמן. תן לאירוע א' להיות מורכב מהעובדה שבמערכת במהלך הזמן דטקיבל בקשה אחת. אירוע ב' מורכב מכך שבמהלך הזמן דטבקשה אחת הוגשה. מִקרֶה אבל אני , ק- במהלך דטהמערכת תעבור מהמדינה ה אנילתוך מדינה ה ק. כי להיא עוצמת זרימת הקלט, ואז במהלך הזמן דטנכנס למערכת בממוצע l*Dטדרישות. כלומר, ההסתברות לקבלת תביעה אחת P(A)=אני* דט, וההסתברות לאירוע ההפוך Р(А)=1-l*Dט.P(B)=ו(דט)= פ(ב< ד ט)=1- ה - M ד ט = M דט- ההסתברות למתן שירות לבקשה בזמן דט. לאחר מכן A 00 - הבקשה לא תתקבל או תתקבל אלא תוגש. A 00 \u003d Ā + A * V. R 00 \u003d 1 - l*Dט. (לקחנו את זה בחשבון (דט) 2 הוא ערך אינפיניטסימלי)

א 01 - הבקשה תתקבל אך לא תוגש. A 01 = A * . R 01 = l*Dט.

ו-10 - הבקשה תוגש ולא תהיה חדשה. A 10 \u003d B * א. R 10 = m*Dט.

ו-11 - הבקשה לא תוגש או שתגיע חדשה שטרם הוגשה. A 11 = +V * A. R 01 = 1- m*Dט.

לפיכך, אנו מקבלים את מטריצת המעבר:

Comp.	E 0	E 1
E 0	1-l * Dt	ל * Dt
E 1	M * Dt	1-מ' * Dt

הסתברות להשבתת מערכת וכשל.

הבה נמצא כעת את ההסתברות שהמערכת נמצאת במצב ה 0 בכל נקודת זמן ט(הָהֵן. ר 0 ( ט) ). גרף פונקציות
מוצג באיור 3.2.

האסימפטוטה של ​​הגרף היא קו ישר
.

ברור, מנקודה מסוימת ט,

1

איור 3.2

סוף סוף אנחנו מבינים את זה
ו
, איפה ר 1 (ט) היא ההסתברות שבזמן ט המערכת תפוסה (כלומר נמצאת במצב ה 1 ).

ברור שבתחילת פעולת ה-QS, התהליך המתמשך לא יהיה נייח: זה יהיה מצב "מעברי", לא נייח. לאחר זמן מה (התלוי בעוצמות זרימות הקלט והפלט), תהליך זה יגווע והמערכת תעבור למצב פעולה נייח ויציב, והמאפיינים ההסתברותיים לא יהיו תלויים יותר בזמן.

מצב פעולה נייח ומקדם עומס מערכת.

אם ההסתברות שהמערכת תהיה במצב ה ק, כלומר ר ק (ט), לא תלוי בזמן ט, אז הם אומרים שה-QS הקימה מצב נייחעֲבוֹדָה. יחד עם זאת, הערך
שקוראים לו גורם עומס מערכת(או הצפיפות המופחתת של זרימת היישומים). ואז לגבי ההסתברויות ר 0 (ט) ו ר 1 (ט) נקבל את הנוסחאות הבאות:
,
. אתה יכול גם להסיק: ככל שמקדם העומס של המערכת גדול יותר, כך גדל הסיכוי שהמערכת תיכשל (כלומר, ההסתברות שהמערכת תפוסה).

לשטיפת המכוניות יחידה אחת לתחזוקה. מכוניות מגיעות בחלוקת פויסון בתעריף של 5 מכוניות לשעה. זמן השירות הממוצע לרכב אחד הוא 10 דקות. מצא את ההסתברות שמכונית מתקרבת תמצא את המערכת תפוסה אם ה-QS במצב נייח.

פִּתָרוֹן.לפי המשימה, ל=5, M y =5/6. אנחנו צריכים למצוא את ההסתברות ר 1 היא ההסתברות לכשל במערכת.
.

3.4.2 QS חד ערוצי עם אורך תור בלתי מוגבל.

נשקול מערכות שעומדות בדרישות: (Р/Е/1):(d/¥/¥). המערכת יכולה להיות באחת המדינות ה 0 , …, ה ק, ... הניתוח מראה כי לאחר זמן מה מערכת כזו מתחילה לפעול במצב נייח אם עוצמת זרימת הפלט עולה על עוצמת זרימת הקלט (כלומר, מקדם העומס של המערכת קטן מאחד). בהתחשב בתנאי זה, אנו מקבלים את מערכת המשוואות

פתרון אשר נמצא כי . לפיכך, בתנאי ש y<1, получим
סוף כל סוף,
ו
היא ההסתברות שה-QS יהיה במדינה ה קבנקודת זמן אקראית.

מאפיינים ממוצעים של המערכת.

עקב קליטה לא אחידה של דרישות במערכת ותנודות בזמן השירות, נוצר תור במערכת. עבור מערכת כזו, אתה יכול לחקור:

• נ – מספר הדרישות ב-QS (בתור ובשירות);
• v - אורך התור;
• w - זמן המתנה לתחילת השירות;
• w 0 הוא הזמן הכולל ששהה במערכת.

נתעניין מאפיינים ממוצעים(כלומר, אנחנו לוקחים את הציפייה המתמטית של המשתנים האקראיים הנחשבים, וזוכרים את זה y<1).

הוא המספר הממוצע של יישומים במערכת.

הוא אורך התור הממוצע.

הוא זמן ההמתנה הממוצע לתחילת השירות, כלומר. זמן המתנה בתור.

- הזמן הממוצע שהאפליקציה מבלה במערכת - בתור ובשירות.

בשטיפת המכוניות יש בלוק אחד לשירות ויש מקום לתור. מכוניות מגיעות בחלוקת פויסון בתעריף של 5 מכוניות לשעה. זמן השירות הממוצע לרכב אחד הוא 10 דקות. מצא את כל מאפייני ה-QS הממוצעים.

פִּתָרוֹן. ל=5, M=60 דקות/10 דקות = 6. מקדם עומס y =5/6. לאחר מכן מספר המכוניות הממוצע במערכת
, אורך תור ממוצע
, זמן ההמתנה הממוצע לתחילת השירות
שעות = 50 דקות, ולבסוף זמן השהייה הממוצע במערכת
שָׁעָה.

3.4.3 QS חד ערוצי מסוג מעורב.

נניח שאורך התור הוא Mדרישות. ואז, לכל ס£ M, ההסתברות למצוא את ה-QS במדינה ה 1+ ס, מחושב לפי הנוסחה
, כלומר בקשה אחת מוגשת ואחרת סיישומים נמצאים בתור.

ההסתברות להשבתת מערכת היא
,

וההסתברות לכשל במערכת היא
.

שלוש מערכות חד ערוציות ניתנות, עבור כל אחת ל=5, M =6. אבל המערכת הראשונה היא עם כשלים, השנייה היא עם המתנה טהורה, והשלישית היא עם אורך תור מוגבל, M=2. מצא והשווה את ההסתברויות לזמן השבתה של שלוש המערכות הללו.

פִּתָרוֹן.לכל המערכות מקדם עומס y=5/6. למערכת עם כשלים
. למערכת עם ציפייה טהורה
. למערכת עם אורך תור מוגבל
. המסקנה ברורה: ככל שיש יותר יישומים בתור, כך הסבירות להשבתת מערכת קטנה יותר.

3.5 QS רב ערוצי.

3.5.1 QS רב ערוצי עם כשלים.

נשקול מערכות (Р/Е/s):(-/s/¥) בהנחה שזמן השירות אינו תלוי בזרם הקלט וכל הקווים פועלים באופן עצמאי. מערכות רב ערוציות, בנוסף למקדם העומס, יכולות להיות מאופיינות גם על ידי המקדם
, איפה ס– מספר ערוצי שירות. בחינת QS רב-ערוצית, אנו משיגים את הנוסחאות הבאות (נוסחאות Erlang) עבור ההסתברות שהמערכת תהיה במצב ה קבזמן אקראי:

, k=0, 1, …

פונקציית עלות.

כמו במערכות חד-ערוציות, עלייה במקדם העומס מובילה לעלייה בסבירות לכשל במערכת. מנגד, גידול במספר קווי השירות מביא לעלייה בסבירות להשבתה של המערכת או ערוצים בודדים. לפיכך, יש צורך למצוא את המספר האופטימלי של ערוצי שירות עבור QS זה. ניתן למצוא את המספר הממוצע של קווי שירות חינם לפי הנוסחה
. בואו נכיר את C( ס) – פונקציית עלות QS תלוי עם 1 – עלות סירוב אחד (קנס בגין בקשה שלא מולאה) ומן עם 2 - עלות זמן השבתה של קו אחד ליחידת זמן.

כדי למצוא את האפשרות האופטימלית, עליך למצוא (ואפשר לעשות זאת) את הערך המינימלי של פונקציית העלות: מ(ס) = עם 1* ל * ע ס +c 2*, שהגרף שלו מוצג באיור 3.3:

איור 3.3

החיפוש אחר הערך המינימלי של פונקציית העלות הוא שאנו מוצאים את ערכיה תחילה ס =1, ואז עבור ס =2, ואז עבור ס =3 וכו'. עד שבשלב מסוים הערך של הפונקציה С( ס) לא יהיה גדול יותר מהקודם. זה אומר שהפונקציה הגיעה למינימום שלה והתחילה לגדול. התשובה היא מספר ערוצי השירות (ערך ס) שעבורו פונקציית העלות היא מינימלית.

דוגמא .

כמה קווי שירות צריכים להכיל QS עם כשלים, אם ל\u003d 2 ריב / שעה, M\u003d 1reb / ​​שעה, העונש על כל כישלון הוא 7,000 רובל, עלות השבתה עבור שורה אחת היא 2,000 רובל. תוך שעה?

פִּתָרוֹן. y = 2/1=2. עם 1 =7, עם 2 =2.

הבה נניח של-QS יש שני ערוצי שירות, כלומר. ס =2. לאחר מכן
. כתוצאה מכך, C(2) = ג 1 *ל*ע 2 +c 2 *(2- י*(1-ר 2 )) = =7*2*0.4+2*(2-2*0.6)=7.2.

בואו נעמיד פנים כך ס =3. לאחר מכן
, C(3) = ג 1 *ל*ע 3 +c 2 *
=5.79.

נניח שיש ארבעה ערוצים, כלומר. ס =4. לאחר מכן
,
, C(4) = ג 1 *ל*ע 4 +c 2 *
=5.71.

הבה נניח של-QS יש חמישה ערוצי שירות, כלומר. ס =5. לאחר מכן
, C(5) = 6.7 - יותר מהערך הקודם. לכן, המספר האופטימלי של ערוצי שירות הוא ארבעה.

3.5.2 QS רב ערוצי עם תור.

נשקול מערכות (Р/Е/s):(d/d+s/¥) בהנחה שזמן השירות אינו תלוי בזרימת הקלט וכל הקווים פועלים באופן עצמאי. נאמר שהמערכת הותקנה פעולה נייחת, אם המספר הממוצע של תביעות נכנסות קטן ממספר התביעות הממוצע שהוגשו בכל קווי המערכת, כלומר. ל

P(w>0) האם ההסתברות להמתין לתחילת השירות,
.

המאפיין האחרון מאפשר לפתור את בעיית קביעת המספר האופטימלי של ערוצי שירות באופן שההסתברות להמתנה לתחילת השירות קטנה ממספר נתון. לשם כך, די לחשב את ההסתברות לציפיות ברציפות ס =1, ס =2, ס=3 וכו'

דוגמא .

SMO - תחנת אמבולנס של מיקרו-מחוז קטן. ל=3 שיחות לשעה, ו M= 4 שיחות לשעה לצוות אחד. כמה צוותים חייבים להיות בתחנה כדי שהסבירות להמתין ליציאה תהיה פחות מ-0.01?

פִּתָרוֹן.גורם עומס מערכת y =0.75. נניח שיש שני צוותים זמינים. תן לנו למצוא את ההסתברות לחכות שהשירות יתחיל ב- ס =2.
,
.

נניח שיש שלוש חטיבות, כלומר. ס=3. לפי הנוסחאות, אנחנו מקבלים את זה ר 0 =8/17, P(w>0)=0.04>0.01 .

נניח שיש ארבעה צוותים בתחנה, כלומר. ס=4. ואז נקבל את זה ר 0 =416/881, P(w>0)=0.0077<0.01 . לכן צריכות להיות ארבע חטיבות בתחנה.

3.6 שאלות לשליטה עצמית

1. הנושא והמטלות של תורת העמידה בתור.
2. QS, הדגמים והייעודים שלהם.
3. זרם קלט דרישות. עוצמת זרם הקלט.
4. מצב המערכת. מטריצה ​​וגרף של מעברים.
5. QS חד ערוצי עם כשלים.
6. QS חד ערוצי עם תור. מאפיינים.
7. מצב פעולה נייח. גורם עומס מערכת.
8. QS רב ערוצי עם כשלים.
9. אופטימיזציה של פונקציית עלות.
10. QS רב ערוצי עם תור. מאפיינים.

3.7 תרגילים לעבודה עצמאית

1. למזנון בתחנת הדלק יש דלפק אחד. מכוניות מגיעות לפי חלוקת Poisson, עם ממוצע של 2 מכוניות ל-5 דקות. בממוצע, 1.5 דקות מספיקות להשלמת הזמנה, אם כי משך השירות מחולק על פי חוק אקספוננציאלי. מצא: א) את ההסתברות שהדוכן יהיה סרק; ב) ביצועים ממוצעים; ג) ההסתברות שמספר המכוניות המגיעות יהיה לפחות 10.
2. מכשיר רנטגן מאפשר לך לבדוק בממוצע 7 אנשים בשעה. עוצמת המבקרים היא 5 אנשים בשעה. בהנחה של פעולה נייחת, קבע את המאפיינים הממוצעים.
3. זמן השירות ב-QS מציית לחוק אקספוננציאלי,
   M = 7 דרישות לשעה. מצא את ההסתברות שא) זמן השירות הוא בין 3 ל-30 דקות; ב) התביעה תוגש תוך שעה. השתמש בטבלת ערכי הפונקציה ה איקס .
4. ישנו עגינה אחת בנמל הנהר, עוצמת זרימת הקלט היא 5 כלי שייט ביום. עוצמת פעולות ההעמסה והפריקה היא 6 ספינות ביום. תוך התחשבות במצב הפעולה הנייח, קבע את כל המאפיינים הממוצעים של המערכת.
5. ל=3, M=2, העונש על כל תקלה הוא 5, ועלות ההשבתה לשורה היא 2?
6. מהו המספר האופטימלי של ערוצי שירות ש-QS צריך להיות אם ל=3, M =1, העונש על כל תקלה הוא 7, ועלות ההשבתה לשורה היא 3?
7. מהו המספר האופטימלי של ערוצי שירות ש-QS צריך להיות אם ל=4, M=2, העונש על כל תקלה הוא 5, ועלות ההשבתה לשורה היא 1?
8. קבע את מספר מסלולי ההמראה למטוסים, בכפוף לדרישה שהסתברות להמתנה חייבת להיות קטנה מ-0.05. יחד עם זאת, עוצמת זרימת הקלט היא 27 מטוסים ביום, ועוצמת השירות שלהם היא 30 מטוסים ביום.
9. כמה קווי מסוע עצמאיים שוות ערך צריכה להיות לבית מלאכה כדי להבטיח את קצב העבודה, שבהם ההסתברות להמתנה לעיבוד מוצרים חייבת להיות פחות מ-0.03 (כל מוצר מיוצר על ידי קו אחד). ידוע כי עוצמת קבלת ההזמנות היא 30 מוצרים בשעה, ועוצמת עיבוד מוצר בקו אחד היא 36 מוצרים לשעה.
10. משתנה אקראי רציף X מופץ לפי חוק מעריכי עם הפרמטר l=5. מצא את פונקציית ההתפלגות, המאפיינים וההסתברות לפגיעה ב-r.v. X בטווח שבין 0.17 ל-0.28.
11. המספר הממוצע של שיחות המגיעות למרכזייה בדקה אחת הוא 3. בהנחה שהזרימה היא Poisson, מצא את ההסתברות שתוך 2 דקות יהיו: א) שתי שיחות; ב) פחות משתי שיחות; ג) לפחות שתי שיחות.
12. יש 17 חלקים בקופסה, מתוכם 4 פגומים. ההרכב מצייר 5 חלקים באקראי. מצא את ההסתברות שא) כל החלקים שחולצו הם באיכות גבוהה; ב) בין החלקים שחולצו 3 פגומים.
13. כמה ערוצים צריכים להיות ל-QS עם כשלים אם ל\u003d 2 ריב / שעה, M\u003d 1reb / ​​שעה, העונש על כל כישלון הוא 8,000 רובל, עלות השבתה עבור שורה אחת היא 2,000 רובל. תוך שעה?

משימה 1.קונסולת השיגור מקבלת זרימת בקשות, שהיא זרימת Erlang מסדר שני. עוצמת זרימת האפליקציות היא 6 אפליקציות בשעה. אם השולח עוזב את הקונסולה ברגע אקראי, אז בבקשה הראשונה הבאה עליו לחזור לקונסולה. מצא את צפיפות ההתפלגות של זמן ההמתנה לבקשה הבאה ושרטט את הגרף שלה. חשב את ההסתברות שהשולח יכול להיעדר בין 10 ל-20 דקות. פִּתָרוֹן. מכיוון שזרימת ארלנג מהסדר השני היא זרימה נייחת עם אפקט לוואי מוגבל, אז הנוסחה של פאלם תקפה עבורה

איפה f1(θ)- צפיפות התפלגות ההסתברות לזמן ההמתנה של האירוע הקרוב הראשון;
λ - עוצמת זרימה;
- סדר זרימה;
(θ) היא פונקציית התפלגות ההסתברות עבור הזמן בין שני אירועים סמוכים של זרימת הסדר של ארלנג (E).
ידוע שלפונקציית ההתפלגות עבור הזרימה E יש את הצורה

. (2)

לפי תנאי הבעיה, זרימת האפליקציות היא Erlang בסדר גודל =2. ואז מ-(1) ו-(2) נקבל
.
מהיחס האחרון עבור λ=6 יהיה לנו

f1(θ)=3е-6θ(1+6θ), θ≥0. (3)

בואו נשרטט את הפונקציה f1(θ) . בְּ θ <0 יש לנו f1(θ) =0 . בְּ θ =0 , f1(0)=3. קחו בחשבון את הגבול

בעת חישוב הגבול לחשיפת אי בהירות סוג, נעשה שימוש בכלל L'Hopital. על סמך תוצאות המחקר, אנו בונים גרף של הפונקציה f1(θ) (איור 1).

נשים לב לממדי הזמן בטקסט המשימה: לעוצמה, מדובר באפליקציות לשעה, לזמן, לדקות. נעבור ליחידת זמן אחת: 10 דקות = 1/6 שעה, 20 דקות = 1/3 שעה. עבור ערכים אלה, אפשר לחשב f1(θ) ולחדד את אופי העקומה

אורדינאטות אלו מסומנות בגרף מעל נקודות העקומה המתאימות.
ממהלך תורת ההסתברות ידוע כי ההסתברות לפגיעה במשתנה מקרי איקסלתוך המקטע [α, β] שווה מספרית לשטח מתחת לעקומת צפיפות ההסתברות f(x). אזור זה מתבטא באינטגרל מובהק

לכן, ההסתברות הרצויה שווה ל

ניתן לחשב את האינטגרל הזה בקלות לפי חלקים אם נניח
U=1+6θו dV=e-6θdθ. לאחר מכן dU=6dθו V= .
שימוש בנוסחה אנחנו מקבלים

תשובה: ההסתברות שהשולח יכול להיעדר בין 10 ל-20 דקות היא 0.28.

משימה 2.בחדר התצוגה 5 תצוגות. זרימת המשתמשים היא הפשוטה ביותר. מספר המשתמשים הממוצע המבקרים בחדר התצוגה ביום הוא 140. זמן עיבוד המידע על ידי משתמש אחד בתצוגה אחת מופץ על פי חוק אקספוננציאלי ועומד בממוצע על 40 דקות. קבע אם יש מצב פעולה נייח של האולם; ההסתברות שהמשתמש ימצא את כל התצוגות תפוסות; מספר ממוצע של משתמשים בחדר התצוגה; מספר ממוצע של משתמשים בתור; זמן תצוגה סרק ממוצע; הזמן הממוצע שהמשתמש מבלה בחדר התצוגה. פִּתָרוֹן.ה-QS שנחשב בבעיה שייך למחלקת המערכות הרב-ערוציות עם תור בלתי מוגבל. מספר ערוצים = 5. הבה נמצא את עוצמת ה-λ של זרימת הבקשות: איפה (שעות) - הזמן הממוצע בין שני יישומים עוקבים של זרימת המשתמשים הנכנסת. לאחר מכן משתמש/שעה

בואו נמצא - את עוצמת זרימת השירות: , כאשר M[T service]=40 דקות=0.67 שעות - זמן שירות ממוצע למשתמש אחד עם תצוגה אחת,

לאחר מכן משתמש/שעה

לפיכך, למסווג של מערכת זו יש את הצורה CMO (5, ∞; 5.85; 1.49).
חשב את מקדם העומס QS . ידוע כי עבור QS ממעמד זה, מצב נייח קיים אם היחס בין מקדם העומס של המערכת למספר הערוצים הוא פחות מאחד. למצוא את הקשר הזה
.
לכן, המשטר הנייח קיים. התפלגות ההסתברות של המצב המגביל מחושבת על ידי הנוסחאות

מאז =5, יש לנו

בוא נחשב את P* - ההסתברות שהמשתמש ימצא את כל התצוגות תפוסות. ברור שזה שווה לסכום ההסתברויות של אירועים כאלה: כל התצוגות תפוסות, אין תור (p5); כל התצוגות תפוסות, משתמש אחד בתור (p6); כל התצוגות תפוסות, שני משתמשים נמצאים בתור (p7), וכן הלאה. מכיוון שלקבוצה שלמה של אירועים סכום ההסתברויות של אירועים אלה שווה לאחד, אזי השוויון

P * \u003d p5 + p6 + p7 + ... \u003d 1 - ro - p1 - p2 - p3 - p4.

בוא נמצא את ההסתברויות האלה: ro=0,014; p1=3,93*0,014; p2=7,72*0,014; p3=10,12*0,014; p4=9,94*0,014.
אם מוציאים את הגורם המשותף מהסוגריים, אנחנו מבינים
P*=1-0.0148*(1+3.93+7.72+10.12+9.94)=1-0.014*32.71=1-0.46=0.54.
משתמש בנוסחאות לחישוב מדדי ביצוע? למצוא:

• 1. מספר ממוצע של משתמשים בתור

2. מספר משתמשים ממוצע בחדר התצוגה

3. זמן המתנה ממוצע לתצוגה בחינם

4. זמן השהות הממוצע של המשתמש בחדר התצוגה

תשובה: אופן הפעולה הנייח של חדר התצוגה קיים ומאופיין במדדים הבאים R*=0.54; מִשׁתַמֵשׁ; מִשׁתַמֵשׁ; ; .

משימה 3.זרימת Poisson נייחת של בקשות נכנסת למערכת תורים דו-ערוצית (QS) עם כשלים. הזמן בין הגעות של שתי בקשות רצופות מחולק לפי החוק האקספוננציאלי עם הפרמטר λ=5 בקשות לדקה. משך הטיפול בכל בקשה הוא 0.5 דקות. בשיטת מונטה קרלו, מצא את מספר הלקוחות הממוצע שהוגשו בזמן של 4 דקות. רמז: בצע שלוש בדיקות. פִּתָרוֹן.הבה נתאר את המודל הסטטיסטי של הפעולה של QS נתון באמצעות דיאגרמות זמן. הבה נציג את הסימון הבא עבור צירי זמן:
Vx- זרימת יישומים נכנסת, כאן ti- רגע קבלת הבקשות; טי- מרווחי זמן בין שני יישומים עוקבים. זה ברור ש ti=ti-1 +Tאני.
ערוץ שירות K1-first;
ערוץ שירות K2 שניות; כאן, הקווים העבים על ציר הזמן מייצגים מרווחי עמוס של ערוץ. אם שני הערוצים פנויים, אזי הבקשה מקבלת שירות בערוץ K1, אם הוא תפוס, הבקשה מטופלת על ידי ערוץ K2.
אם שני הערוצים תפוסים, הבקשה משאירה את ה-QS ללא הגשה.
Out OB - זרימה יוצאת של בקשות מטופלות.
Out PT הוא הזרם היוצא של בקשות שאבדו עקב כשלים ב-QS (שני הערוצים תפוסים).
בדיקות סטטיסטיות נמשכות לפרק זמן. ברור, כל שעות נוספות tmaxכרוך בהחזרת הבקשה לזרם היוצא Out PT. אז באיור. 3 בקשה מס' 10 שנכנסה אז למערכת t10, אין זמן להגיש עד הרגע tmax, כי t10+Tmont.>tmax. לכן, הוא אינו מתקבל על ידי הערוץ החינמי K1 לשירות והוא מאופס ל-Out PT, מקבל סירוב.

אורז. 3

מתוך דיאגרמות התזמון, ניתן לראות כי יש צורך ללמוד כיצד לדגמן מרווחים טאני. אנו מיישמים את השיטה של ​​פונקציות הפוכות. מאז המשתנה האקראי טימופץ לפי החוק האקספוננציאלי עם הפרמטר λ =5, אז לצפיפות ההתפלגות יש את הצורה ו(τ)=5е-5τ. ואז הערך F(Ti)פונקציית התפלגות ההסתברות נקבעת על ידי האינטגרל

.

ידוע שטווח התפלגות פונקציה ו(ט) יש חתך. אנו בוחרים מספר מטבלת המספרים האקראיים וקובעים טאנימשוויון , מנין . לעומת זאת, אם . לכן, אתה יכול לקבל יישום מיידי מטבלת המספרים האקראיים. כתוצאה מכך,
e-5Tאני= ri, או -5Tאני= אינרי, איפה . נוח להזין את תוצאות החישובים בטבלה.
למבחן מס' 1 נלקחו מספרים אקראיים מתוך נספח 2, החל מהמספר הראשון של השורה הראשונה. דגימה נוספת בוצעה לפי שורות. בוא נעשה עוד שני מבחנים.
שימו לב לבחירת המספרים האקראיים מהטבלה של נספח 2, אם במבחן מס' 1 המספר האקראי האחרון לבקשה מס' 16 היה 0.37 (המספר האקראי הראשון בשורה השנייה), אזי מבחן מס' 2 מתחיל ב המספר האקראי הבא 0.54. ניסיון מס' 2 מכיל את המספר האקראי האחרון 0.53 (המספר החמישי בשורה השלישית). לכן, המבחן השלישי יתחיל במספר 0.19. באופן כללי, בתוך אותה סדרת בדיקות נבחרים מספרים אקראיים מהטבלה ללא פערים והוספות בסדר מסוים, למשל בשורות.

טבלה 1. מבחן מס' 1

בקשה מס. אני	Sl. מספר ri		-ברי טי	רגע קבלת הבקשה ti=ti-1+Ti	זמן סיום השירות. ti+0.50		מונה יישומים
					K1

טבלה 2 מבחן מס' 2

בקשה מס. אני	Sl. מספר ri		-ברי טאני	רגע קבלת הבקשה ti=ti-1+Ti	זמן סיום השירות. ti+0.50		מונה יישומים

טבלה מס' 3 מבחן מס' 3

בקשה מס. אני		Sl. מספר ri		-ברי טאני	רגע קבלת הבקשה ti=ti-1+Ti	זמן סיום השירות. ti+0.50		מונה יישומים
						K1

לפיכך, על פי התוצאות של שלוש בדיקות, מספר האפליקציות שקיבלו שירות היה בהתאמה: x1=9, x2=9, x3=8. מצא את המספר הממוצע של בקשות לטיפול:

תשובה: המספר הממוצע של בקשות המוגשות על ידי ה-QS ב-4 דקות הוא 8.6(6).

הזרימה והיישום הפשוטים ביותר של בעיות מעשיות.

זרימת פואסון לא נייחת.

זרימות עם השלכות מוגבלות (פלמה זורמת).

זרמי התאוששות.

1. הקדמה.

1.1. התייחסות להיסטוריה.

רוב המערכות איתן מתמודד האדם הן סטוכסטיות. ניסיון לתאר אותם מתמטית בעזרת מודלים דטרמיניסטיים מוביל להתגסות של מצב העניינים האמיתי. כאשר פותרים בעיות של ניתוח ותכנון של מערכות כאלה, יש לקחת בחשבון את מצב העניינים מתי האקראיות היא המגדירהלתהליכים המתרחשים במערכות. יחד עם זאת, הזנחת האקראיות, ניסיון "לסחוט" את פתרון הבעיות המפורטות למסגרת דטרמיניסטית מובילים לעיוות, לטעויות במסקנות והמלצות מעשיות.

הבעיות הראשונות של תיאוריית מערכות התורים (TSMO) נבחנו על ידי עובד של חברת הטלפון קופנהגן, המדען הדני A.K. ארלנג (1878-1929) בין 1908 ל-1922. משימות אלו התעוררו בעקבות הרצון לייעל את תפעול רשת הטלפונים ולפתח שיטות לשיפור איכות שירות הלקוחות מראש, בהתאם למספר המכשירים בהם נעשה שימוש. התברר שהמצבים המתעוררים במרכזיות טלפונים אופייניים לא רק לתקשורת טלפונית. תפעול שדות תעופה, נמלי ים ונהר, חנויות, מחלקות טרמינלים, מערכות מחשוב אלקטרוניות, תחנות מכ"ם וכו'. ניתן לתאר במונחים של TSMO.

1.2. דוגמאות למערכות תורים. ניתוח משימות TSMO.

דוגמה 1התקשורת הטלפונית של ארלנג הייתה מרכזית טלפון הקשורה למספר רב של מנויים. מפעילי הטלפון של התחנה, עם קבלת שיחות, חיברו את מספרי הטלפון זה לזה.

משימה: כמה טלפונים (בהנחה שהם עובדים באופן מלא) צריכים לעבוד בתחנה כך שהפסד התביעות יהיה מינימלי.

דוגמה 2מערך האמבולנסים של אזור עירוני מסוים מורכב מנקודה (המקבלת בקשות למילוי), מספר אמבולנסים ומספר צוותים רפואיים.

המטרה: קביעת מספר הרופאים, צוותי התמיכה, כלי הרכב, כך שזמן ההמתנה לקריאה יהיה אופטימלי למטופלים, תוך מזעור עלות תפעול המערכת ומקסום איכות השירות.

דוגמה 3משימה חשובה היא ארגון הובלה ימית ונהר של סחורות. בהקשר זה, יש חשיבות מיוחדת לשימוש מיטבי בספינות ובמתקני נמל.

מטרה: לספק כמות מסוימת של תעבורה בעלות מינימלית. במקביל, להפחית את זמן ההשבתה של כלי השיט במהלך פעולות הטעינה והפריקה.

דוגמה 4מערכת עיבוד המידע מכילה ערוץ מרובה ומספר מחשבים. האותות מהחיישנים נשלחים לערוץ המולטיפלקס, שם הם מאוחסנים ומעובדים מראש. ואז הם נכנסים למחשב שבו התור מינימלי.

משימה: להבטיח את האצת עיבוד האותות עבור אורך תור כולל נתון.

דוגמה 5. באיור 1.1. מוצג תרשים בלוקים של מערכת תורים טיפוסית - חברת תיקונים (לדוגמה, לתיקון מחשב אישי). סדר פעולתו ברור מהתרשים ואינו מצריך הבהרה.

איור 1.1.

לא קשה להביא דוגמאות רבות נוספות מתחומי פעילות שונים.

אופייני למשימות כאלה הוא:

1. תנאים של אקראיות "כפולה" -

• רגע קבלת ההזמנה לשירות הינו אקראי (במרכזית הטלפון, בעמדת האמבולנס, בכניסת המעבד, רגע הגעת הספינה לטעינה וכו' הינו אקראי);
• משך זמן השירות הוא אקראי.

2) בעיית הנגע של זמננו - תורים: ספינות מול מנעולים, מכוניות מול דלפקים, משימות בכניסת מעבדים של מתחם מחשבים וכו'.

א.ק. ארלנג הפנה את תשומת הלב לעובדה שניתן לחלק את QS לשני סוגים, כלומר: מערכות עם ציפיות ומערכות עם הפסדים. במקרה הראשון, הבקשה המתקבלת בכניסה של המערכת "ממתינה" לתור הביצוע, במקרה השני היא נדחית בגלל ערוץ השירות תפוס ואובד עבור ה-QS.

בעתיד, נראה שבעיות חדשות מתווספות לבעיות הארלנג הקלאסיות:

מערכות אמיתיות שיש לטפל בהן בפועל, ככלל, הן מורכבות מאוד וכוללות מספר שלבים (שלבים) של תחזוקה (איור 1.1). זאת ועוד, בכל שלב תיתכן אפשרות לכשל בביצוע או שיש מצב של שירות עדיפות ביחס לדרישות אחרות. במקרה זה, קישורי שירות בודדים עשויים להפסיק את עבודתם (לתיקון, התאמה וכו') או שיתחברו כספים נוספים. ייתכנו נסיבות שבהן בקשות שנדחו יוכנסו מחדש למערכת (זה יכול לקרות במערכות מידע).

1.3. מושגים, הגדרות, טרמינולוגיה.

לכל QS יש מבנה מוגדר היטב, המוצג באיור 1.2

איור 1.2

הגדרות, מונחים

• זרם הוא רצף של אירועים. זרימת בקשות השירות נקראת זרימת הביקוש.
• זרימת הבקשות הנכנסת למערכת השירות נקראת הזרימה הנכנסת.
• זרם הבקשות המטופל נקרא הזרם היוצא.
• מערך התורים והתקני השירות (ערוצים) נקרא מערכת השירות.
• כל בקשה נכנסת לערוץ משלה, שם היא עוברת פעולת שירות.
• לכל CMO יש כללים מסוימים לתור וחוקים או משמעת שירות.

1.4. סיווג CMO.

1.4.1. על פי אופי מקור הדרישות, נבדלים QS עם מספר סופי ואינסופי של דרישות בקלט.

במקרה הראשון מסתובב במערכת מספר סופי, קבוע בדרך כלל, של דרישות, אשר לאחר השלמת השירות חוזרות למקור.

במקרה השני, המקור מייצר מספר אינסופי של בקשות.

דוגמה 1בית מלאכה עם מספר קבוע של מכונות או מספר מסוים של מחשבים במחלקת טרמינלים הדורשים בדיקה ותיקון מונעים מתמשכים.

דוגמה 2. רשת האינטרנט עם ביקוש אינסופי בכניסה, בכל חנות, מספרה וכו'.

הסוג הראשון של QS נקרא סגור, השני - פתוח.

SMO להבחין:

1.4.2. משמעת שירות:

1. שירות על בסיס כל הקודם זוכה;
2. שירות בסדר אקראי (בהתאם לחוק הפצה נתון);
3. שירות עדיפות.

1.4.3. על פי אופי הארגון:

1. עם כישלונות;
2. עם ציפיות;
3. עם המתנה מוגבלת.

במקרה הראשון, הבקשה נדחית כאשר הערוץ תפוס. במקרה השני, הוא עומד בתור ומחכה לשחרור הערוץ. במקרה השלישי, הוכנסו הגבלות על זמן ההמתנה.

1.4.4. לפי מספר יחידות שירות:

1. ערוץ יחיד;
2. שני ערוצים;
3. רב ערוצי.

1.4.5. לפי מספר השלבים (שלבי) השירות - עבור חד פאזי ורב פאזי. (כל קו ייצור יכול לשמש דוגמה ל-QS רב-שלבי).

1.4.6. מאפייני ערוץ: להומוגנית, כאשר לערוצים יש את אותו מאפיין, והטרוגניים אחרת.

זה נדרש כדי לפתור בעיות 1-3. הנתונים הראשוניים ניתנים בטבלה. 2-4.

סימון מסוים המשמש בתורת התורים לנוסחאות:

n הוא מספר הערוצים ב-QS;

λ - עוצמת הזרימה הנכנסת של יישומים P in;

v - עוצמת הזרימה היוצאת של יישומים P out;

μ - עוצמת זרימת השירות P בערך;

ρ - מחוון עומס מערכת (תנועה);

מ' - המספר המרבי של מקומות בתור, הגבלת אורך תור הבקשות;

i - מספר מקורות יישום;

p to - ההסתברות למצב ה-k של המערכת;

p about - ההסתברות לזמן סרק של המערכת כולה, כלומר ההסתברות שכל הערוצים פנויים;

p syst - ההסתברות לקבל בקשה במערכת;

p otk - ההסתברות לסירוב לבקשה בקבלתה למערכת;

p about - ההסתברות שהבקשה תוגש;

A הוא התפוקה המוחלטת של המערכת;

Q הוא התפוקה היחסית של המערכת;

och - המספר הממוצע של יישומים בתור;

o - המספר הממוצע של בקשות בשירות;

syst - המספר הממוצע של יישומים במערכת;

pt - זמן המתנה ממוצע לאפליקציה בתור;

o - זמן ההגשה הממוצע של הבקשה, המתייחס רק לבקשות המוגשות;

sys - זמן השהייה הממוצע של האפליקציה במערכת;

exp - זמן ממוצע המגביל את ההמתנה לאפליקציה בתור;

מספר ממוצע של ערוצים עמוסים.

התפוקה המוחלטת של QS A היא המספר הממוצע של יישומים שהמערכת יכולה לשרת ליחידת זמן.

תפוקת QS יחסי Q הוא היחס בין מספר האפליקציות הממוצע המוגשות על ידי המערכת ליחידת זמן לבין המספר הממוצע של בקשות שהתקבלו במהלך זמן זה.

בעת פתרון בעיות תור, יש צורך להקפיד על הרצף הבא:

1) קביעת סוג ה-QS לפי טבלה. 4.1;

2) בחירת נוסחאות בהתאם לסוג ה-QS;

3) פתרון בעיות;

4) גיבוש מסקנות על הבעיה.

1. תכנית מוות ורבייה.

אנו יודעים שבהינתן גרף מצב מסומן, אנו יכולים לכתוב בקלות את משוואות קולמוגורוב עבור הסתברויות מצב, וגם לכתוב ולפתור משוואות אלגבריות עבור ההסתברויות הסופיות. במקרים מסוימים, ניתן לפתור את המשוואות האחרונות מראש, בצורה מילולית. בפרט, ניתן לעשות זאת אם גרף המצב של המערכת הוא מה שנקרא "תכנית מוות ורבייה".

גרף המדינה עבור ערכת המוות והרבייה הוא הצורה המוצגת באיור. 19.1. המוזרות של גרף זה היא שניתן לצייר את כל מצבי המערכת לשרשרת אחת, שבה כל אחד מהמצבים הממוצעים ( ס 1 , ש 2 , …, ש n-1) מחובר על ידי חץ קדימה ואחורה עם כל אחד מהמדינות השכנות - ימין ושמאל, והמצבים הקיצוניים (ס 0 , שנ) - עם מדינה שכנה אחת בלבד. המונח "תכנית מוות ורבייה" מקורו בבעיות ביולוגיות, כאשר שינוי בגודל האוכלוסייה מתואר על ידי תכנית כזו.

סכימת המוות והרבייה נתקלת לעתים קרובות מאוד בבעיות תרגול שונות, במיוחד בתורת התור, לכן כדאי, אחת ולתמיד, למצוא את ההסתברויות הסופיות של מדינות עבורה.

נניח שכל זרימות האירועים שמעבירות את המערכת לאורך חיצי הגרף הן הפשוטות ביותר (למען הקיצור, נקרא גם את המערכת סוהתהליך המתרחש בו הם הפשוטים ביותר).

באמצעות הגרף באיור. 19.1, אנו מחברים ופותרים משוואות אלגבריות להסתברויות הסופיות של המצב), הקיום נובע מכך שמכל מצב אתה יכול ללכת לכל מצב אחר, מספר המצבים הוא סופי).

למדינה הראשונה ס 0 יש לנו:

(19.1)

למדינה השנייה S1:

בשל (19.1), השוויון האחרון מצטמצם לטופס

איפה קלוקח את כל הערכים מ-0 עד פ.אז ההסתברויות הסופיות p0, p1,..., p n מספקים את המשוואות

(19.2)

בנוסף, עלינו לקחת בחשבון את מצב הנורמליזציה

ע 0 + ע 1 + ע 2 +…+ ע n=1. (19.3)

בואו נפתור את מערכת המשוואות הזו. מהמשוואה הראשונה (19.2) אנו מבטאים ע 1 דרך ר 0 :

ע 1 = ע 0. (19.4)

מהשני, בהתחשב (19.4), אנו מקבלים:

(19.5)

מהשלישי, תוך התחשבות (19.5),

(19.6)

ובכלל, לכל ק(מ-1 עד נ):

(19.7)

הבה נשים לב לנוסחה (19.7). המונה הוא המכפלה של כל העוצמות בחצים המובילים משמאל לימין (מההתחלה למצב הנתון ס k), והמכנה הוא המכפלה של כל העוצמות בחצים המובילים מימין לשמאל (מההתחלה עד Sk).

לפיכך, כל ההסתברויות של המדינה ר 0 , עמ' 1 , ..., р נבא לידי ביטוי באמצעות אחד מהם ( ר 0). הבה נחליף ביטויים אלה בתנאי הנורמליזציה (19.3). אנחנו מסתדרים באמצעות סוגריים ר 0:

מכאן אנו מקבלים את הביטוי עבור ר 0 :

(העלינו את הסוגריים בחזקת -1 כדי לא לכתוב שברים של שתי קומות). כל שאר ההסתברויות מתבטאות במונחים של ר 0 (ראה נוסחאות (19.4)-(19.7)). שימו לב שהמקדמים עבור ר 0 בכל אחד מהם הם לא יותר מחברים עוקבים בסדרה אחרי היחידה בנוסחה (19.8). אז, בחישוב ר 0 , כבר מצאנו את כל המקדמים הללו.

הנוסחאות שהתקבלו שימושיות מאוד בפתרון הבעיות הפשוטות ביותר של תורת התורים.

2. נוסחה קטנה.

כעת אנו מפיקים נוסחה חשובה אחת המתייחסת (עבור המשטר המגביל, הנייח) למספר הממוצע של יישומים ל syst, הממוקם במערכת התורים (כלומר מוגש או עומד בתור), וזמן השהייה הממוצע של האפליקציה במערכת W syst.

הבה ניקח בחשבון כל QS (ערוץ אחד, רב-ערוצי, מרקוביאן, לא מרקוביאן, עם תור בלתי מוגבל או מוגבל) ושני זרמים של אירועים הקשורים אליו: זרימת הלקוחות המגיעים ל-QS וזרם הלקוחות העוזבים את ה-QS. QS. אם נקבע משטר מגביל, נייח במערכת, אז המספר הממוצע של יישומים המגיעים ל-QS ליחידת זמן שווה למספר האפליקציות הממוצע היוצא ממנו: לשני הזרימות יש אותה עוצמה λ.

לציין: X(t) -מספר הבקשות שהגיעו ל-CMO לפני הרגע ט. י(ט) — מספר הבקשות שיצאו מה-CMO

עד הרגע ט.שתי הפונקציות הן אקראיות ומשתנות בפתאומיות (מוגברת באחת) ברגע הגעת הבקשות (איקס(ט)) ויציאות של בקשות (Y(t)).סוג הפונקציות X(t) ו-Y(t)מוצג באיור. 19.2; שני הקווים מדורגים, העליון הוא X(t),נמוך יותר- Y(t).ברור, לכל רגע טההבדל שלהם ז(ט)= X(t) - Y(t)אינו אלא מספר היישומים ב-QS. כאשר הקווים X(t)ו Y(t)מיזוג, אין בקשות במערכת.

קחו בחשבון פרק זמן ארוך מאוד ט(ממשיך מנטלית את הגרף הרבה מעבר לשרטוט) וחשב עבורו את מספר האפליקציות הממוצע ב-QS. זה יהיה שווה לאינטגרל של הפונקציה Z T)על מרווח זה חלקי באורך המרווח ת:

ל syst. = . (19.9) o

אבל האינטגרל הזה אינו אלא השטח של הדמות המוצללת באיור. 19.2. בואו נסתכל היטב על הציור הזה. הדמות מורכבת ממלבנים שלכל אחד מהם גובה שווה לאחד ובסיס השווה לזמן השהייה במערכת של הסדר המקביל (הראשון, השני וכו'). בואו נציין את הזמנים האלה t 1 , t 2 ,...נכון, בסוף המרווח טכמה מלבנים ייכנסו לדמות המוצללת לא לגמרי, אלא חלקית, אבל עם דמות גדולה מספיק טהדברים הקטנים האלה לא יהיו חשובים.

(19.10)

כאשר הסכום חל על כל הבקשות שהתקבלו במהלך הזמן ט.

מחלקים את הצדדים הימניים והשמאליים (.19.10) באורך המרווח ט.אנו משיגים, תוך התחשבות (19.9),

ל syst. = . (19.11)

אנו מחלקים ומכפילים את הצד הימני של (19.11) בעוצמה X:

ל syst. = .

אבל הגודל Tλהוא לא יותר ממספר הבקשות הממוצע שהתקבלו במהלך הזמן ^ ט.אם נחלק את סכום כל הזמנים אניעל מספר הפניות הממוצע, אז נקבל את זמן השהות הממוצע של האפליקציה במערכת W syst. כך,

ל syst. = λ W syst. ,

W syst. = . (19.12)

זוהי הנוסחה הנפלאה של ליטל: לכל QS, לכל אופי של זרימת האפליקציות, לכל חלוקת זמן שירות, לכל דיסציפלינה של שירות זמן השהייה הממוצע של בקשה במערכת שווה למספר הבקשות הממוצע במערכת חלקי עוצמת זרם הבקשות.

בדיוק באותו אופן, נגזרת הנוסחה השנייה של ליטל, המתייחסת לזמן הממוצע שהאפליקציה מבלה בתור ^ ו וומספר הפניות הממוצע בתור ל och:

W och = . (19.13)

עבור הפלט, זה מספיק במקום השורה התחתונה באיור. 19.2 קח פונקציה U(t)- מספר הבקשות שנותרו עד הרגע טלא מהמערכת, אלא מהתור (אם הבקשה שנכנסה למערכת לא נכנסת לתור, אלא נכנסת מיד לשירות, אנחנו עדיין יכולים לשקול שהיא נכנסת לתור, אבל נשארת בו זמן אפס) .

הנוסחאות של ליטל (19.12) ו- (19.13) ממלאות תפקיד חשוב בתורת התורים. למרבה הצער, ברוב המדריכים הקיימים, נוסחאות אלו (שהוכחו בצורה כללית יחסית לאחרונה) אינן ניתנות 1).

מערכות התורים הפשוטות ביותר ומאפייניהן

בסעיף זה, נשקול כמה מה-QS הפשוטים ביותר ונגזר ביטויים עבור המאפיינים שלהם (מדדי ביצועים). במקביל, נדגים את הטכניקות המתודולוגיות העיקריות האופייניות לתיאוריה היסודית, ה"מרקוביאנית" של עמידה בתור.

לא נעסוק במספר דגימות ה-QS שלגביהן ייגזרו הביטויים הסופיים של המאפיינים; הספר הזה אינו מדריך לתיאוריית התורים (מדריכים מיוחדים ממלאים את התפקיד הזה הרבה יותר טוב). המטרה שלנו היא להציג לקורא כמה "טריקים קטנים" כדי להקל על תיאוריית התורים, שבמספר ספרים זמינים (אפילו מתיימרים להיות פופולריים) יכולים להיראות כמו אוסף של דוגמאות.

כל זרימות האירועים המעבירות QS ממדינה למדינה, בסעיף זה, נשקול את הפשוטים ביותר (מבלי לקבוע זאת כל פעם ספציפית). ביניהם יהיה מה שנקרא "זרימת שירות". המשמעות היא זרימת הבקשות המוגשות על ידי ערוץ אחד עמוס ברציפות. בזרם זה, למרווח בין אירועים, כמו תמיד בזרם הפשוט ביותר, יש התפלגות אקספוננציאלית (מדריכים רבים אומרים במקום זאת: "זמן השירות הוא אקספוננציאלי", אנו בעצמנו נשתמש במונח זה בעתיד).

בספר פופולרי ניתנת גזירה שונה במקצת, בהשוואה לאמור לעיל, של הנוסחה של ליטל. באופן כללי, היכרות עם ספר זה ("שיחה שנייה") מועילה להיכרות ראשונית עם תורת העמידה בתור.

בסעיף זה, ההתפלגות האקספוננציאלית של זמן השירות תהיה מובן מאליו, כמו תמיד עבור המערכת ה"פשוטה".

אנו נציג את מאפייני היעילות של ה-QS הנבחנים במהלך המצגת.

1. פ- ערוץ QS עם כשלים(בעיית ארלנג). כאן אנו רואים את אחת הבעיות ה"קלאסיות" הראשונות בזמן של תורת העמידה בתור; בעיה זו נבעה מהצרכים המעשיים של הטלפוניה ונפתרה בתחילת המאה שלנו על ידי המתמטיקאי הדני ארלנט. המשימה מוגדרת כך: יש פערוצים (קווי תקשורת), המקבלים זרימה של יישומים בעוצמה λ. לזרימת השירות יש עוצמה μ (ההדדיות של זמן השירות הממוצע טעל אודות).

מצא את ההסתברויות הסופיות של מצבי ה-QS, כמו גם את המאפיינים של היעילות שלו:

^ א -תפוקה מוחלטת, כלומר, המספר הממוצע של יישומים שהוגשו ליחידת זמן;

ש-תפוקה יחסית, כלומר, החלק הממוצע של בקשות נכנסות המוגשות על ידי המערכת;

^ P otk- ההסתברות לכישלון, כלומר העובדה שהבקשה תשאיר את ה-QS ללא הגשה;

ק -מספר ממוצע של ערוצים עמוסים.

פִּתָרוֹן. מצבי מערכת ^S(QS) ימוספרו בהתאם למספר הבקשות במערכת (במקרה זה, זה עולה בקנה אחד עם מספר הערוצים העסוקים):

S 0 -אין יישומים ב-SMO,

S 1 -יש בקשה אחת ב-QS (ערוץ אחד תפוס, השאר בחינם),

Sk —ב-SMO הוא קיישומים ( קהערוצים עמוסים, השאר בחינם),

S n -ב-SMO הוא פיישומים (כולם נהערוצים עמוסים).

גרף מצב ה-QS מתאים לתכנית המוות ברבייה (איור 20.1). בואו נסמן את הגרף הזה - הניחו את עוצמת זרימות האירוע ליד החצים. מ ס 0 אינץ' S1המערכת מועברת על ידי זרימת בקשות בעוצמה λ (ברגע שמגיעה בקשה, המערכת קופצת מ S0ב S1).אותה זרימה של בקשות מעבירה את המערכת מכל מצב שמאל למצב הימני השכן (ראה את החצים העליונים באיור 20.1).

בואו נניח את עוצמת החצים התחתונים. תן למערכת להיות במדינה ^S 1 (ערוץ אחד עובד). הוא מייצר μ שירותים ליחידת זמן. שמנו למטה ליד החץ ס 1 →סעוצמה 0 μ. עכשיו דמיינו שהמערכת נמצאת במדינה S2(שני ערוצים עובדים). כדי שהיא תלך אליה S 1,יש צורך שהערוץ הראשון או השני יסיים את השירות; העוצמה הכוללת של זרימות השירות שלהם היא 2μ; שים אותו בחץ המתאים. זרימת השירות הכוללת שניתנת על ידי שלושת הערוצים היא בעוצמה של 3μ, קערוצים - ק"מ.הנחנו את העוצמות הללו בחצים התחתונים באיור. 20.1.

ועכשיו, בידיעה של כל העוצמות, נשתמש בנוסחאות המוכנות (19.7), (19.8) להסתברויות הסופיות בסכימה של מוות ורבייה.

לפי הנוסחה (19.8) נקבל:

מונחי פירוק יהיו המקדמים עבור p 0בביטויים עבור p1

שימו לב שנוסחאות (20.1), (20.2) אינן כוללות את העוצמות λ ו-μ בנפרד, אלא רק כיחס λ/μ. לציין

λ/μ = ρ (20.3)

ונכנה את הערך של p "העוצמה המופחתת של זרימת היישומים". המשמעות שלו היא המספר הממוצע של בקשות המגיעות במשך זמן השירות הממוצע של בקשה אחת. באמצעות סימון זה, אנו משכתבים נוסחאות (20.1), (20.2) בצורה:

נוסחאות (20.4), (20.5) להסתברויות המצב הסופי נקראות נוסחאות ארלנג, לכבודו של מייסד תורת התורים. רוב הנוסחאות האחרות של התיאוריה הזו (היום יש יותר מהן מאשר פטריות ביער) אינן נושאות שמות מיוחדים.

לפיכך, נמצאות ההסתברויות הסופיות. על בסיסם, נחשב את מאפייני היעילות של QS. ראשית אנו מוצאים ^ P otk. - ההסתברות שהבקשה הנכנסת תידחה (לא תוגש). לשם כך יש צורך שכל פהערוצים היו עמוסים, אז

ר otk = ר n = . (20.6)

מכאן אנו מוצאים את התפוקה היחסית - ההסתברות שהבקשה תוגש:

ש = 1 - פלִפְתוֹחַ = 1 - (20.7)

אנו משיגים את התפוקה המוחלטת על ידי הכפלת עוצמת זרימת הבקשות λ ב ש:

A = λQ = λ. (20.8)

נותר רק למצוא את המספר הממוצע של ערוצים עסוקים ק.ניתן למצוא ערך זה "ישירות", כציפייה מתמטית למשתנה אקראי בדיד עם ערכים אפשריים 0, 1, ..., פוההסתברויות של ערכים אלו p 0 p 1 , ..., p n:

ק = 0 · p 0 +אחד · p 1 + 2 · p 2 + ... + n · P n .

מחליף כאן ביטויים (20.5) עבור רק , (ק = 0, 1, ..., P)וביצוע הטרנספורמציות המתאימות, נשיג בסופו של דבר את הנוסחה הנכונה עבורה ק.אבל נפיק את זה הרבה יותר קל (הנה זה, אחד ה"טריקים הקטנים"!) ואכן, אנחנו יודעים את התפוקה המוחלטת אבל.אין זו אלא עוצמת זרימת האפליקציות שמשרתת המערכת. כל מועסק ב.י.של ליחידת זמן משרת בממוצע |1 בקשות. אז המספר הממוצע של ערוצים עמוסים הוא

k = A/μ, (20.9)

או, נתון (20.8),

k = (20.10)

אנו מעודדים את הקורא לעבד את הדוגמה בעצמו. יש תחנת תקשורת עם שלושה ערוצים ( נ= 3), עוצמת זרימת היישומים λ = 1.5 (יישומים לדקה); זמן שירות ממוצע לכל בקשה ט v = 2 (דקות), כל זרימות האירועים (כמו בכל הפסקה הזו) הן הפשוטות ביותר. מצא את הסתברויות המצב הסופי ואת מאפייני הביצועים של ה-QS: א, ש, פאוקיי, ק.ליתר ביטחון, הנה התשובות: ע 0 = 1/13, ע 1 = 3/13, ע 2 = 9/26, עמ' 3 = 9/26 ≈ 0,346,

אבל≈ 0,981, ש ≈ 0,654, פפתוח ≈ 0.346, k ≈ 1,96.

ניתן לראות מהתשובות, אגב, שה-CMO שלנו עמוס במידה רבה: מתוך שלושה ערוצים, כשניים עמוסים בממוצע, וכ-35% מהבקשות הנכנסות נותרו ללא מתן שירות. אנו מזמינים את הקורא, אם הוא סקרן ולא עצלן, לברר: כמה ערוצים יידרשו על מנת לספק לפחות 80% מהפניות הנכנסות? ואיזה חלק מהערוצים יהיה בטל בו זמנית?

יש כבר איזה רמז אופטימיזציה.למעשה, התוכן של כל ערוץ ליחידת זמן עולה סכום מסוים. יחד עם זאת, כל אפליקציית שירות מביאה הכנסה מסוימת. הכפלת הכנסה זו במספר הבקשות הממוצע אבל,בשירות ליחידת זמן, נקבל את ההכנסה הממוצעת מ-CMO ליחידת זמן. מטבע הדברים, עם גידול במספר הערוצים, ההכנסה הזו גדלה, אך גם העלויות הכרוכות בתחזוקת הערוצים גדלות.

מה יגבר - גידול בהכנסות או בהוצאות? הדבר תלוי בתנאי המבצע, ב"דמי שירות אפליקציה" ובעלות אחזקת הערוץ. הכרת הערכים הללו, תוכל למצוא את מספר הערוצים האופטימלי, החסכוני ביותר. לא נפתור בעיה כזו, ונשאיר את אותו "קורא לא עצלן וסקרן" להמציא דוגמה ולפתור אותה. באופן כללי, המצאת בעיות מפתחת יותר מאשר פתרון של אלה שכבר נקבעו על ידי מישהו.

QS חד ערוץ עם תור בלתי מוגבל.

בפועל, QS ערוץ אחד עם תור הוא די נפוץ (רופא המשרת חולים; טלפון ציבורי עם דוכן אחד; מחשב שממלא הזמנות משתמשים). בתורת התור, QS חד-ערוץ עם תור תופס מקום מיוחד (רוב הנוסחאות האנליטיות שהתקבלו עד כה עבור מערכות לא-מרקוביניות שייכות ל-QS כאלה). לכן, נקדיש תשומת לב מיוחדת ל-QS חד ערוצי עם תור.

שיהיה QS חד ערוצי עם תור שלא מוטלות עליו הגבלות (לא על אורך התור, ולא על זמן ההמתנה). QS זה מקבל זרימה של בקשות בעוצמה λ ; לזרימת השירות יש עוצמה μ הפוכה לזמן השירות הממוצע של הבקשה טעל אודות.

נדרש למצוא את ההסתברויות הסופיות של מצבי ה-QS, כמו גם את המאפיינים של יעילותו:

ל syst. — מספר יישומים ממוצע במערכת,

W syst. הוא זמן השהייה הממוצע של בקשה במערכת,

^ ל אוך- המספר הממוצע של יישומים בתור,

W och — הזמן הממוצע שאפליקציה מבלה בתור,

פזאן — ההסתברות שהערוץ תפוס (מידת הטעינה של הערוץ).

לגבי התפוקה המוחלטת אבלוקרוב משפחה ש,אז אין צורך לחשב אותם:

בשל העובדה שהתור אינו מוגבל, כל בקשה תוגש במוקדם או במאוחר, לפיכך A = λ,מאותה הסיבה ש= 1.

פִּתָרוֹן. מצבי המערכת, כבעבר, ימוספרו לפי מספר האפליקציות ב-QS:

ס 0 — הערוץ בחינם

ס 1 - הערוץ תפוס (משרת את הבקשה), אין תור,

ס 2 - הערוץ תפוס, בקשה אחת נמצאת בתור,

ס k - הערוץ תפוס, ק - 1 יישומים נמצאים בתור,

תיאורטית, מספר המדינות אינו מוגבל בשום דבר (אין סוף). לגרף המדינה יש את הצורה המוצגת באיור. 20.2. זוהי תוכנית של מוות ורבייה, אבל עם מספר אינסופי של מצבים. בכל החצים, זרימת הבקשות בעוצמה λ מעבירה את המערכת משמאל לימין, ומימין לשמאל, זרימת השירות בעוצמה μ.

קודם כל, הבה נשאל את עצמנו, האם יש הסתברויות סופיות במקרה הזה? אחרי הכל, מספר המצבים של המערכת הוא אינסופי, ובאופן עקרוני, ב t → ∞התור יכול לגדול ללא הגבלת זמן! כן, זה נכון: ההסתברויות הסופיות ל-QS כזה לא תמיד קיימות, אלא רק כשהמערכת לא עמוסה מדי. ניתן להוכיח שאם ρ הוא בהחלט פחות מאחד (ρ< 1), то финальные вероятности существуют, а при ρ ≥ 1 очередь при ט→ ∞ גדל ללא הגבלה.

עובדה זו נראית "בלתי מובנת" במיוחד עבור ρ = 1. נראה כי אין דרישות בלתי אפשריות למערכת: במהלך השירות של בקשה אחת, בממוצע, מגיעה בקשה אחת, והכל אמור להיות מסודר, אבל במציאות זה לא. עבור ρ = 1, ה-QS מתמודד עם זרימת הבקשות רק אם זרימה זו היא סדירה, וגם זמן השירות אינו אקראי, שווה למרווח בין בקשות. במקרה ה"אידיאלי" הזה, לא יהיה תור ב-QS כלל, הערוץ יהיה עמוס באופן רציף ויוציא באופן קבוע בקשות שירות.

אבל ברגע שזרימת הבקשות או זרימת השירות יהפכו לפחות מעט אקראית, התור כבר יגדל ללא הגבלת זמן. בפועל, זה לא קורה רק בגלל ש"מספר אינסופי של יישומים בתור" הוא הפשטה. אלו הן השגיאות הגסות שהחלפת משתנים אקראיים בציפיות המתמטיות שלהם יכולה להוביל אליהן!

אבל בואו נחזור ל-QS החד-ערוץ שלנו עם תור בלתי מוגבל. למהדרין, הנוסחאות להסתברויות הסופיות בסכימה של מוות ורבייה נגזרו על ידינו רק למקרה של מספר סופי של מצבים, אבל בואו ניקח חירויות - נשתמש בהן למספר אינסופי של מצבים. הבה נחשב את ההסתברויות הסופיות של מצבים לפי נוסחאות (19.8), (19.7). במקרה שלנו, מספר האיברים בנוסחה (19.8) יהיה אינסופי. אנחנו מקבלים ביטוי עבור p 0:

ע 0 \u003d -1 \u003d (1 + p + p 2 + ... + p k + ... .) -1. (20.11)

הסדרה בנוסחה (20.11) היא התקדמות גיאומטרית. אנחנו יודעים את זה עבור ρ< 1 ряд сходится — это бесконечно убывающая геометрическая прогрессия со знаменателем р. При р ≥ 1 ряд расходится (что является косвенным, хотя и не строгим доказательством того, что финальные вероятности состояний p 0 , p 1 , ..., p k , ...קיים רק עבור r<1).

כעת נניח שתנאי זה מתקיים ו- ρ1 + ρ + ρ 2 + ... + ρ k + ... = ,

ע 0 = 1 - עמ'. (20.12)

הסתברויות p 1 , p 2 , ..., p k ,... ניתן למצוא לפי הנוסחאות:

p1 = ρ p 0, p 2= ρ2 p 0 ,…,p k = ρ p0, ...,

מאיפה, בהתחשב (20.12), אנו מוצאים לבסוף:

p1= ρ (1 - ρ), p2= ρ 2 (1 - ρ), . . . , p k =ρ ק(1 - p), . . .(20.13)

כפי שאתה יכול לראות, ההסתברויות p0, p1, ..., p k,...יוצרים התקדמות גיאומטרית עם המכנה p. באופן מוזר, הגדול שבהם p 0 -ההסתברות שהערוץ יהיה בחינם בכלל. לא משנה עד כמה המערכת עמוסה בתור, אם רק היא יכולה בכלל להתמודד עם זרימת היישומים (ρ<1), самое вероятное число заявок в системе будет 0.

מצא את המספר הממוצע של יישומים ב-QS ^L syst. . כאן אתה צריך להתעסק קצת. ערך אקראי Z-מספר בקשות במערכת - יש ערכים אפשריים 0, 1, 2, .... ק,...עם הסתברויות p0, p 1 , p 2 , ..., p k , ...הציפייה המתמטית שלו היא

למערכת = 0? p 0 + 1 ? ע 1 + 2 ? ע 2 +…+ק ? ע k +…= (20.14)

(הסכום נלקח לא מ-0 ל-∞, אלא מ-1 ל-∞, שכן איבר האפס שווה לאפס).

אנו מחליפים לנוסחה (20.14) את הביטוי עבור p k (20.13):

ל syst. =

כעת נוציא את הסימן של הסכום ρ (1-ρ):

ל syst. = ρ(1-ρ)

כאן אנו מיישמים שוב את "הטריק הקטן": קρ ק-1 אינו אלא הנגזרת ביחס ל- ρ של הביטוי ρ ק; אומר,

ל syst. = ρ(1-ρ)

על ידי החלפת פעולות ההבחנה והסיכום, אנו משיגים:

ל syst. = ρ (1-ρ) (20.15)

אבל הסכום בנוסחה (20.15) אינו אלא סכום של התקדמות גיאומטרית פוחתת אינסופית עם האיבר הראשון ρ והמכנה ρ; כמות זו

שווה ל , והנגזרת שלו היא . החלפת ביטוי זה ב-(20.15), נקבל:

למערכת = . (20.16)

ובכן, עכשיו בואו ניישם את הנוסחה של ליטל (19.12) ונמצא את זמן השהייה הממוצע של אפליקציה במערכת:

W syst = (20.17)

מצא את המספר הממוצע של יישומים בתור ל och. נטען כדלקמן: מספר האפליקציות בתור שווה למספר האפליקציות במערכת פחות מספר האפליקציות בשירות. אז (לפי כלל התוספת של ציפיות מתמטיות), המספר הממוצע של פניות בתור ל pt שווה למספר האפליקציות הממוצע במערכת למערכת פחות המספר הממוצע של בקשות בשירות.

מספר הבקשות בשירות יכול להיות אפס (אם הערוץ פנוי) או אחד (אם הוא תפוס). התוחלת המתמטית של משתנה אקראי כזה שווה להסתברות שהערוץ תפוס (סימנו את זה רזאן). מובן מאליו, ר zan שווה לאחד פחות ההסתברות p 0שהערוץ בחינם:

רזאן = 1 - ר 0 = p. (20.18)

לכן, המספר הממוצע של בקשות בשירות שווה ל

^L בערך= ρ, (20.19)

ל och = ל syst - ρ =

ולבסוף

ל pt = (20.20)

באמצעות הנוסחה של ליטל (19.13), אנו מוצאים את הזמן הממוצע שהאפליקציה מבלה בתור:

(20.21)

לפיכך, כל המאפיינים של יעילות QS נמצאו.

הבה נציע לקורא לפתור דוגמה בעצמו: QS חד ערוצית היא חצר תיווך רכבת, המקבלת את הזרימה הפשוטה ביותר של רכבות בעוצמה של λ = 2 (רכבות לשעה). שירות (פירוק)

הרכב נמשך זמן אקראי (הדגמתי) עם ערך ממוצע t בערך = 20(דקה). בפארק ההגעה של התחנה שני מסילות שעליהן יכולות להמתין לשירות רכבות המגיעות; אם שתי המסילות תפוסות, הרכבות נאלצות להמתין על הפסים החיצוניים.

נדרש למצוא (למצב הפעילות המגביל והנייח של התחנה): ממוצע, מספר רכבות למערכת הקשורה לתחנה, זמן ממוצע Wמערכת שהות רכבת בתחנה (במסילות פנימיות, במסילות חיצוניות ובתחזוקה), מספר ממוצע לנקודות של רכבות שמחכות בתור לפירוק (לא משנה באיזה מסילה), זמן ממוצע Wנקודות נשארות הרכב ברשימת ההמתנה. כמו כן, נסו למצוא את מספר הרכבות הממוצע הממתינות לפירוק על המסילות החיצוניות. לחיצוני והזמן הממוצע של המתנה זו Wחיצוני (שתי הכמויות האחרונות קשורות לפי הנוסחה של ליטל).

לבסוף, מצא את סך הקנס היומי W, אותו תצטרך התחנה לשלם עבור ירידת מרץ של רכבות על פסים חיצוניים, אם התחנה משלמת קנס a (רובל) עבור שעה אחת של ירידת מרץ של רכבת אחת. ליתר ביטחון, הנה התשובות: ל syst. = 2 (הרכב), W syst. = 1 (שעה), לנקודות = 4/3 (הרכב), W pt = 2/3 (שעות), לחיצוני = 16/27 (הרכב), Wחיצוני = 8/27 ≈ 0.297 (שעות). העונש היומי הממוצע W על המתנה לרכבות על מסילות חיצוניות מתקבל על ידי הכפלת מספר הרכבות הממוצע המגיעות לתחנה ביום, זמן ההמתנה הממוצע לרכבות על מסילות חיצוניות וקנס שעתי. א: W ≈ 14.2 א.

ערוץ מחדש של QS עם תור בלתי מוגבל.

דומה לחלוטין לבעיה 2, אבל קצת יותר מסובכת, הבעיה של נ- ערוץ QS עם תור בלתי מוגבל.

μ 2μ kμ (k+1)μ nμ nμ nμ nμ nμ

יש תוכנית של מוות ורבייה, אבל עם מספר אינסופי של מצבים. הבה נציין ללא הוכחה את התנאי הטבעי לקיומן של הסתברויות סופיות: ρ/ נ n ≥ 1, התור גדל עד אינסוף.

נניח שהתנאי ρ/ נ < 1 выполнено, и финальные вероятности существуют. Применяя все те же формулы (19.8), (19.7) для схемы гибели и размножения, найдем эти финальные вероятности. В выражении для p 0תהיה סדרה של איברים המכילים פקטוריאלים, בתוספת סכום של התקדמות גיאומטרית פוחתת אינסופית עם המכנה ρ/ נ. לסכם את זה, אנחנו מוצאים

(20.22)

עכשיו בואו נמצא את המאפיינים של יעילות QS. מבין אלה, הכי קל למצוא את המספר הממוצע של ערוצים תפוסים ק= λ/μ, = ρ (זה נכון בדרך כלל עבור כל QS עם תור בלתי מוגבל). מצא את המספר הממוצע של יישומים במערכת למערכת ומספר האפליקציות הממוצע בתור ל och. מבין אלה, קל יותר לחשב את השני, לפי הנוסחה

ל och =

ביצוע הטרנספורמציות המתאימות לפי המדגם של בעיה 2

(עם בידול של הסדרה), אנו מקבלים:

ל och = (20.23)

הוספת אליו את המספר הממוצע של אפליקציות בשירות (זה גם המספר הממוצע של ערוצים עסוקים) k =ρ, נקבל:

למערכת = ל och + ρ. (20.24)

חלוקת ביטויים עבור לאוח ו למערכת על λ , באמצעות הנוסחה של ליטל, אנו מקבלים את זמן השהייה הממוצע של אפליקציה בתור ובמערכת:

(20.25)

עכשיו בואו נפתור דוגמה מעניינת. משרד כרטיסי רכבת עם שני חלונות הוא QS דו-ערוצי עם תור בלתי מוגבל שמתבסס מיד לשני חלונות (אם חלון אחד פנוי, הנוסע הבא בתור לוקח אותו). הקופה מוכרת כרטיסים בשתי נקודות: A ו בְּ.עוצמת זרם האפליקציות (נוסעים שרוצים לקנות כרטיס) לשתי הנקודות א' וב'זהה: λ A = λ B = 0.45 (נוסע לדקה), ובסך הכל הם יוצרים זרימה כללית של יישומים בעוצמה של λ A + λB = 0.9. קופאי מקדיש בממוצע שתי דקות לשרת נוסע.

הניסיון מלמד כי תורים מצטברים במשרד הכרטיסים, הנוסעים מתלוננים על איטיות השירות. אבלובתוך בְּ,ליצור שני משרדי כרטיסים מיוחדים (חלון אחד בכל אחד), למכור כרטיסים אחד - רק לנקודה אבל, השני - רק לעניין בְּ.על תקינותה של הצעה זו אפשר להתווכח - יש הטוענים שהקווים יישארו זהים. נדרש לבדוק את תועלת ההצעה בחישוב. מכיוון שאנו מסוגלים לחשב מאפיינים רק עבור ה-QS הפשוטים ביותר, הבה נניח שכל זרימות האירועים הן הפשוטות ביותר (זה לא ישפיע על הצד האיכותי של המסקנות).

ובכן, בוא ניגש לעניינים. שקול שתי אפשרויות לארגון מכירת כרטיסים - הקיימת והמוצעת.

אפשרות I (קיימת). QS דו-ערוצי מקבל זרימה של יישומים בעוצמה של λ = 0.9; עוצמת זרימת תחזוקה μ = 1/2 = 0.5; ρ = λ/μ = l.8. מאז ρ/2 = 0.9<1, финальные вероятности существуют. По первой формуле (20.22) находим p 0 ≈ 0.0525. הממוצע, מספר האפליקציות בתור נמצא לפי הנוסחה (20.23): L och ≈ 7.68; הזמן הממוצע של הלקוח בתור (לפי הראשונה מהנוסחאות (20.25)), שווה ל- Wנקודות ≈ 8.54 (דקות).

אפשרות II (מוצעת). יש צורך לשקול שני ערוץ QS אחד (שני חלונות מיוחדים); כל אחד מקבל זרימת בקשות בעוצמה λ = 0.45; μ . עדיין שווה ל-0.5; ρ = λ/μ = 0.9<1; финальные вероятности существуют. По формуле (20.20) находим среднюю длину очереди (к одному окошку) ל och = 8.1.

הנה אחד בשבילך! אורך התור, מסתבר, לא רק שלא ירד, אלא גדל! אולי זמן ההמתנה הממוצע בתור ירד? בוא נראה. דליה לנקודות על λ = 0.45, נקבל Wנקודות ≈ 18 (דקות).

זה הרציונליזציה! במקום לרדת, גם אורך התור הממוצע וגם זמן ההמתנה הממוצע בו גדלו!

בואו ננסה לנחש למה זה קרה? לאחר שחשבנו על זה, הגענו למסקנה: זה קרה בגלל שבגרסה הראשונה (דו-ערוצים QS) חלקיק הזמן הממוצע שכל אחת משתי הקופאיות בטלה הוא פחות: אם הוא לא עסוק בשירות נוסע שקונה כרטיס לנקודה אבל,הוא יכול לדאוג לנוסע שקונה כרטיס לנקודה בְּ,ולהיפך. בגרסה השנייה, אין אפשרות להחלפה כזו: קופאית לא מאוכלסת פשוט יושבת בחיבוק ידיים...

- נו , בסדר, הקורא מוכן להסכים, ניתן להסביר את העלייה, אבל למה היא כל כך משמעותית? האם יש כאן טעות בחישוב?

ונשיב על השאלה הזו. אין שגיאה. העובדה , שבדוגמה שלנו, שני ה-QS עובדים על גבול היכולות שלהם; אם תגדיל מעט את זמן השירות (כלומר, תפחית את μ), הם לא יוכלו יותר להתמודד עם זרימת הנוסעים, והתור יתחיל לגדול ללא הגבלת זמן. ו"זמן השבתה נוסף" של הקופאי שווה, במובן מסוים, לירידה בתפוקה שלו μ.

כך, תוצאת החישובים, שנראית בתחילה פרדוקסלית (או אפילו פשוט לא נכונה), מתגלה כנכונה וניתנת להסבר.

סוג זה של מסקנות פרדוקסליות, שהסיבה להן אינה ברורה בשום פנים ואופן, עשירה בתורת התור. המחבר עצמו נאלץ שוב ושוב להיות "מופתע" מתוצאות החישובים, שהתבררו מאוחר יותר כנכונות.

בהתחשב במשימה האחרונה, הקורא יכול להעלות את השאלה כך: אחרי הכל, אם הקופה מוכרת כרטיסים לנקודה אחת בלבד, אז, באופן טבעי, זמן השירות אמור לקטון, ובכן, לא בחצי, אבל לפחות במידת מה, אבל חשבנו שזה עדיין הממוצע הוא 2 (דקות). אנו מזמינים קורא בררן כל כך לענות על השאלה: כמה צריך להפחית כדי ש"הצעת הרציונליזציה" תהפוך לרווחית?

שוב, אנו נפגשים, אמנם אלמנטריים, אך עדיין בעיית אופטימיזציה. בעזרת חישובים טנטטיביים, גם במודלים הפשוטים ביותר, של מרקוב, ניתן להבהיר את הצד האיכותי של התופעה - כיצד משתלם לפעול, וכיצד אינו משתלם. בחלק הבא, נציג כמה מודלים אלמנטריים שאינם מרקוביאנים שירחיב עוד יותר את האפשרויות שלנו.

לאחר שהקורא הכיר את השיטות לחישוב הסתברויות המצב הסופי ומאפייני היעילות עבור ה-QS הפשוטה ביותר (הוא שלט בסכימת המוות והרבייה ובנוסחה הקטנה), ניתן להציע לו עוד שני QS פשוטים לשיקול עצמאי.

QS חד ערוצי עם תור מוגבל.הבעיה שונה מבעיה 2 רק בכך שמספר הבקשות בתור מוגבל (לא יכול לחרוג מכמה נתון ט).אם בקשה חדשה מגיעה ברגע שכל המקומות בתור תפוסים, היא משאירה את ה-QS ללא שירות (נדחה).

יש צורך למצוא את ההסתברויות הסופיות של מצבים (אגב, הם קיימים בבעיה זו עבור כל ρ - אחרי הכל, מספר המצבים הוא סופי), ההסתברות לכישלון ר otk, רוחב פס מוחלט אבל,ההסתברות שהערוץ תפוס ר zan, אורך תור ממוצע ל och, המספר הממוצע של בקשות ב-CMO ל syst , זמן המתנה ממוצע בתור W och , זמן שהייה ממוצע של בקשה ב-CMO W syst. כשמחשבים את מאפייני התור, אפשר להשתמש באותה טכניקה שהשתמשנו בבעיה 2, עם ההבדל שיש לסכם לא התקדמות אינסופית, אלא סופית.

לולאה סגורה QS עם ערוץ אחד ו Mמקורות יישומים.למען הקונקרטיות, בואו נקבע את המשימה בצורה הבאה: עובד אחד משרת טמכונות, שכל אחת מהן דורשת התאמה (תיקון) מעת לעת. עוצמת זרימת הביקוש של כל מכונה עובדת שווה ל-λ . אם המכונה לא תקינה ברגע שהעובד פנוי, הוא ניגש מיד לשירות.

אם הוא לא תקין ברגע שבו העובד עסוק, הוא עומד בתור ומחכה שהעובד יהיה פנוי. זמן הגדרה ממוצע ט rev = 1/μ. עוצמת זרם הבקשות המגיעות לעובד תלויה בכמה מכונות פועלות. אם זה עובד קמכונות, זה שווה קλ. מצא את הסתברויות המצב הסופי, את המספר הממוצע של מכונות עובדות ואת ההסתברות שהעובד יהיה עסוק.

שימו לב שב-QS זה, הסתברויות סופיות יתקיימו גם עבור כל ערכים של λ ו-μ = 1/ ט o, מכיוון שמספר המצבים של המערכת הוא סופי.