תכנון ליניארי

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

דוגמה קצרה: יש שלושה משתנים x1,x2,x3 ואילוצים ליניאריים. פתרונות חוקיים הם למשל x1=1,x2=1,x3=5 ו-x1=3,x2=2,x3=4. אם פונקציית המטרה היא 2x1+3x2+x3, הערכים הם 10 ו-16 בהתאמה. לכן x1=3,x2=2,x3=4 הוא אופטימלי בדוגמה זו.

בעיות נוחות להצגה בשפה של מטריצות: A x ≤ b עם וקטור משתנים x ופונקציית מטרה c^T x. הכתיב המקוצר עוזר בתכן אלגוריתמים ובניתוח תאורטי.

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

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

אם דורשים שהמשתנים יהיו שלמים, מקבלים ILP (Integer Linear Programming). בעיות אלה הן NP-קשות, והצורה ההכרעתית שלהן NP-שלמה. יש גם גרסאות מעורבות (MIP) שבהן רק חלק מהמשתנים שלמים.
יש שיטות מעשיות רבות, כמו חישוב רגיל ואז עיגול, שיטות הסתברותיות, או שיטות ענף וחיתוך (branch-and-cut). הזמן במקרה הגרוע יכול להיות אקספוננציאלי.

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

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

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

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

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

קיימות תוכנות רבות לפתירת LP בפועל. דוגמה בקוד פתוח היא cvxpy עבור פייתון. תוכנות כאלה מחזירות פתרונות מספריים, למשל x1=3,x2=2,x3=4 בדוגמה שהוזכרה.

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

לעיתים אין פתרון, לפעמים אפשר להגדיל בלי סוף, ולעיתים יש פתרון הכי טוב.
דוגמה קטנה: פתרונות חוקיים יכולים להיות x1=1,x2=1,x3=5 ו-x1=3,x2=2,x3=4. השני נותן ערך גדול יותר ולכן הוא הכי טוב.

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

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

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

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

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

תוכנות כמו cvxpy עוזרות לפתור בעיות תכנון ליניארי באופן ממוחשב.