אלגוריתמים 2 – תרגול 9
תכנות לינארי
תזכורת
שלבים למידול בעייה בתכנות לינארי
1. הגדרת משתנים (X)
נגדיר את המשתנים של הבעיה שלנו. לדוגמה א הבעיה עוסקת בגרפים, כנראה נרצה משתנה לכל קודוקוד או לכל צלע.
2. הגדרת מטרה (min/max)
נגדיר את המטרה שלנו – למקסם או למזער את סכום המשתנים שהגדרנו, עם משקלים במידת הצורך
3. הגדרת הגבלות (Ax <= b)
זה לרוב החלק הקשה – למדל את הבעיה כהגבלות לינאריות. אפשר להשתמש ב קטן/ גדול, קטן שווה/ גדול שווה, או שווה. (אסור קטן/ גדול ממש!)
* הרבה פעמים לא נצליח למדל את הבעיה כתכנות לינארי (למשל בעיות קשות), אלא כתכנות בשלמים – ההבדל היחיד הוא שמותר למשתנים לקבל רק ערכים שלמים. אמנם אין אלגוריתם פולינומי שפותר בעיות כאלה, אבל זה בהחלט יכול לעזור – למשלrelaxation של הבעיה לממשיים יכול להיות קירוב טוב לפתרון.
דוגמה – שידוך מקסימלי
תרגיל – זרימה ברשת
קלט:
גרף, כלומר קדקדים וצלעות.
נק' התחלה o נק' סיום n
פונקציית קיבולת לצלעות
מטרה:
מהו המקסימום זרימה האפשרי ברשת?
Linear Regression
הפרדת נקודות
הפרדת נקודות – הכללה לפולינום
קבוצה בת״ל מקסימלית
שידוך בעל משקל מקסימלי
טענה: המשקל האופטימלי בממשיים = האופטימלי בשלמים
מי שרוצה לשחק עם זה קצת, יש ספרייה מצויינת בפייטון שפותרת בעיות כאלה – cvxpy.
Welcome to CVXPY 1.3 — CVXPY 1.3 documentation