מודל קו המתנה ותכנות לינארית

מבוא

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

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

מַטָרָה

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

מבנה מערכת קו המתנה

קו המתנה של ערוץ יחיד

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

מודל קו המתנה ותכנות לינארית

חלוקת כניסות

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

/ = ממוצע או כמות התרחשות ממוצעת במרווח

e = 2.17828

X = מספר המופעים במרווח

מודל קו המתנה ותכנות לינארית

זמן השירות הוא הזמן בו הלקוח מבלה בהתקנה לאחר תחילת השירות.

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

e = 2.17828

μ = מספר היחידות הממוצע שניתן להגיש בכל תקופה

מודל קו המתנה ותכנות לינארית

משמעת קו המתנה

התווך בו יחידות הממתינות לשירות מוזמנות לקבלו.

כל הקודם זוכה

אחרון פנימה, ראשון החוצה

תשומת לב ראשונה לעדיפות הגבוהה ביותר

פעולת מצב יציבה

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

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

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

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

מודל קו המתנה ותכנות לינארית

כיצד ניתן לשפר את פעולת קו ההמתנה?

מאפייני התפעול של המערכת עם קצב השירות הממוצע עלה ל- μ = 1.25 לקוחות בדקה.

מודל קו המתנה ותכנות לינארית

ניתוח כלכלי של קווי המתנה

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

Cw = עלות ההמתנה לתקופה לכל יחידה

L = מספר היחידות הממוצע במערכת

Cs = עלות שירות לתקופה עבור כל ערוץ

K = מספר הערוצים

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

מודל קו המתנה ותכנות לינארית

תכנות לינארי

מבוא

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

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

עבור מערכות עם משתנים רבים יותר, הנוהל אינו כה פשוט והם נפתרים באמצעות שיחה

שיטת סימפלקס (הומצאה על ידי GBDanzig, מתמטיקאי אמריקני בשנת 1951).

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

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

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

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

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

אחרים הם:

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

שלבים לפתרון בעיית תכנות לינארית

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