Stochastic programming — תכנות סטוכסטי

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

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

ניסוח מתמטי של הבעיה

בצורה כללית, ניתן לנסח את בעיית התכנות הסטוכסטי כך: $\underset{x\in X}{min}𝔼[f(x,\xi )]$ כאשר:

• $x$ — וקטור משתני הבקרה (ההחלטות) שיש לקבוע.
• $X$ — קבוצת הפתרונות הקבילים עבור $x$, המוגדרת על ידי אילוצים דטרמיניסטיים.
• $\xi$ — וקטור אקראי המייצג את הפרמטרים הלא-ודאיים של הבעיה (לדוגמה, ביקוש, מחירים, תנאי מזג אוויר).
• $f(x,\xi )$ — פונקציית המטרה, שערכה תלוי הן בהחלטה שהתקבלה $x$ והן במימוש הווקטור האקראי $\xi$.
• $𝔼[\cdot ]$ — אופרטור התוחלת המתמטית, המחושב לפי התפלגות ההסתברות של הוקטור $\xi$.

עיקרון יסודי העומד בבסיס מודלים סטוכסטיים רב-שלביים הוא עיקרון אי-הקדמת העתיד (באנגלית: non-anticipativity principle). עיקרון זה קובע כי החלטות המתקבלות בכל שלב יכולות להיות תלויות רק במידע הזמין עד לאותו רגע, ואינן יכולות «להציץ לעתיד».

בעיה דו-שלבית עם זכות פיצוי

המודל הנפוץ ביותר הוא בעיה דו-שלבית עם זכות פיצוי (באנגלית: two-stage stochastic program with recourse). תהליך קבלת ההחלטות מחולק לשני שלבים:

1. שלב ראשון: מתקבלת החלטה «כאן ועכשיו» (here-and-now) — נקבע הוקטור $x$. החלטה זו חייבת להתקבל לפני שנודעת המימוש הספציפי של הוקטור האקראי $\xi$.
2. שלב שני: לאחר שהאירוע האקראי התרחש, מתקבלת החלטת תיקון או פיצוי (recourse decision) — הוקטור $y(\xi )$, שמטרתו למזער השלכות שליליות או לנצל הזדמנויות חיוביות שנוצרו כתוצאה מהשילוב של החלטת השלב הראשון $x$ והתוצאה $\xi$.

מתמטית, הבעיה הדו-שלבית של תכנות לינארי סטוכסטי מנוסחת כך: $\underset{x\in {ℝ}^{n_1}}{min}\{c^{T}x+{𝔼}_{\xi }[Q(x,\xi )]\}$ באילוצי השלב הראשון: $Ax=b,x\ge 0$. כאן $Q(x,\xi )$ היא פונקציית הפיצוי (recourse function), המייצגת את הערך האופטימלי של בעיית השלב השני: $Q(x,\xi )=\underset{y\in {ℝ}^{n_2}}{min}\{q(\xi {)}^{T}y\mid T(\xi )x+Wy=h(\xi ),y\ge 0\}$ כאשר $\xi$ הוא וקטור אקראי הכולל את הפרמטרים $q(\xi ),T(\xi )$ ו-$h(\xi )$; ו-$c,A,b$ ו-$W$ הם פרמטרים דטרמיניסטיים.

תכונות מפתח ומשפטים

• קמירות: אחד התוצאות היסודיות של התאוריה הוא שעבור בעיה דו-שלבית של תכנות לינארי סטוכסטי, פונקציית הפיצוי הצפויה $Q(x)={𝔼}_{\xi }[Q(x,\xi )]$ היא פונקציה קמורה. תכונה זו בעלת חשיבות עצומה, שכן היא מבטיחה שבעיית השלב הראשון הכוללת היא בעיית תכנות קמור, שעבורה קיימות שיטות פתרון יעילות והאופטימום הגלובלי חופף לאופטימום המקומי.
• שקילות דטרמיניסטית: אם לוקטור האקראי $\xi$ יש מספר סופי של מימושים אפשריים (תרחישים) ${\xi }_1,\dots ,{\xi }_K$ עם הסתברויות $p_1,\dots ,p_K$, ניתן לנסח מחדש את בעיית התכנות הסטוכסטי כבעיית אופטימיזציה דטרמיניסטית גדולה אחת. במקרה זה התוחלת המתמטית מוחלפת בסכום משוקלל על פני כל התרחישים. אולם גודל בעיה זו גדל לינארית עם מספר התרחישים, דבר המוביל ל«קללת הממדיות» והופך גישה זו לבלתי אפשרית מבחינה חישובית עבור מספר גדול של תרחישים.

השוואה עם אופטימיזציה רובוסטית

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

השוואת גישות לאופטימיזציה בתנאי אי-ודאות

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

דוגמאות

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

ראו גם

• תכנות מתמטי
• חקר ביצועים
• אופטימיזציה רובוסטית
• תכנות דינמי
• תורת הבקרה

הערות

</references>