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

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

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

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

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

הקדמה

בעיית תכנון ליניארי מורכבת מאוסף משתנים $x_{1},...,x_{n}$, עליהם יש אילוצים ליניאריים. אילוץ ליניארי הוא אי-שוויון בין משוואה ליניארית על המשתנים לבין קבוע, כלומר $a_{1i}x_{1}+...+a_{ni}x_{n}\leq b_{i}$ או $a_{1i}x_{1}+...+a_{ni}x_{n}\geq b_{i}$. ניתן גם לדרוש שוויון; אם תנאי הבעיה אינם מאפשרים זאת, ניתן לדרוש שוויון באמצעות שני האי-שוויונות האחרונים שביחד שקולים לו. בנוסף ישנה פונקציית מטרה $c_{1}x_{1}+...+c_{n}x_{n}$ שאותה יש למזער או למקסם.

לבעיה לא תמיד קיים פתרון (דוגמה פשוטה: התנאים הם $x\geq 1,x\leq 0$), וייתכן גם שפונקציית המטרה איננה חסומה (דוגמה פשוטה: התנאים הם $x\geq 0$, ויש למקסם את $x$). לפיכך, פתרון הבעיה יכול להיות אחת משלוש אפשרויות: אין פתרון כלל, אין פתרון חסום, יש לפחות פתרון אופטימלי אחד.

לדוגמה: נניח ש-$n=3$ כלומר ישנם שלושה משתנים, והאילוצים הם:

$3x_{1}-2x_{2}+x_{3}\leq 9$

$7x_{2}-2x_{3}\leq 6$

$-5x_{1}+10x_{2}\leq 5$

$x_{1}+x_{2}-x_{3}\leq 9$

פתרון למערכת האילוצים הזאת הוא הצבה של ערכים מספריים למשתנים, כך שכל האילוצים מתקיימים. למשל $x_{1}=1,x_{2}=1,x_{3}=5$ וכן $x_{1}=3,x_{2}=2,x_{3}=4$ הם פתרונות למערכת. לעומת זאת, $x_{1}=5,x_{2}=0,x_{3}=0$ הוא לא פתרון, שכן הוא לא מקיים את אי השוויון הראשון: לא מתקיים $3\cdot 5-2\cdot 0+0\leq 9$.

בנוסף למערכת האי שוויונות, נניח שצריך למקסם את פונקציית המטרה $2x_{1}+3x_{2}+x_{3}$. ניתן לראות שהצבת הפתרון הראשון שהצגנו נותנת $2\cdot 1+3\cdot 1+5=10$, ואילו הצבת הפתרון השני נותנת $2\cdot 3+3\cdot 2+4=16$. לכן, הפתרון השני נותן ערך גבוה יותר לפונקציית המטרה. ניתן להראות (בשיטות שידונו בהמשך הערך) שכל פתרון חוקי (כלומר פתרון שמקיים את כל האילוצים) אחר שנציב למשתנים יתן ערך קטן יותר מ-16, ועל כן $x_{1}=3,x_{2}=2,x_{3}=4$ הוא הפתרון האופטימלי.

כתיב מטרציוני

אם כל אי השוויונות נתונים באותו כיוון (כלומר בכולם $ax_{1}+...\leq b$ או בכולם $ax_{1}+...\geq b$), אז נוח להציג את הבעיה בעזרת מטריצות.

למשל, את הבעיה שהצגנו לעיל ניתן להציג בכתיב מטרציוני כך:

${\begin{pmatrix}3&-2&1\\0&7&-2\\-5&10&0\\1&1&-1\end{pmatrix}}\cdot {\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\end{pmatrix}}\leq {\begin{pmatrix}9\\6\\5\\9\end{pmatrix}}$

$\max {\begin{pmatrix}2&3&1\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\end{pmatrix}}$

בכתיב זה, בעיית תכנון ליניארי כוללת וקטור $x$ באורך $n$, מטריצה $A$ בגודל $m\times n$, וקטור $b$ בגודל $m$, ווקטור $c$ בגודל $n$, כך שהבעיה היא למקסם/למזער את $c^{T}x$ תחת האילוצים $Ax\leq b$ או $Ax\geq b$.

צורה קנונית

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

• כל התנאים הם מהצורה $a_{1i}x_{1}+...+a_{ni}x_{n}\leq b_{i}$
• כל המשתנים מקיימים גם $x_{i}\geq 0$
• המטרה היא למקסם ביטוי ליניארי (ולא למזער אותו)

כל בעיית תכנון ליניארי ניתן להעביר לצורה קנונית:

• אם התכונה הראשונה אינה מתקיימת, ניתן להפוך את $a_{1i}x_{1}+...+a_{ni}x_{n}\geq b_{i}$ ל $-a_{1i}x_{1}-...-a_{ni}x_{n}\leq -b_{i}$.
• אם התכונה השנייה אינה מתקיימת עבור משתנה $x$, ניתן להחליף את המשתנה $x$ בביטוי $x'-x''$ כאשר דורשים $x',x''\geq 0$.
• אם התכונה השלישית אינה מתקיימת, ניתן להחליף את "למזער את $c_{1}x_{1}+...+c_{n}x_{n}$" ב"למקסם את $-c_{1}x_{1}+...-c_{n}x_{n}$" (ווקטור הפתרון יהיה אותו וקטור).

סך הכול הגדלנו את כמות המשתנים והמשוואות פי 2 לכל היותר.

צורת slack

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

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

${\begin{bmatrix}1&-\mathbf {c} ^{T}&0\\0&\mathbf {A} &\mathbf {I} \end{bmatrix}}{\begin{bmatrix}z\\\mathbf {x} \\\mathbf {s} \end{bmatrix}}={\begin{bmatrix}0\\\mathbf {b} \end{bmatrix}}$

$\mathbf {x} \geq 0,\mathbf {s} \geq 0$

$\max z$

כאשר $x$ הם המשתנים המקוריים, $s$ הם משתני ה slack, ו-$z$ הוא המשתנה שיש למקסם.

לדוגמה, אם הבעיה היא:

$x_{1}+5x_{2}+2x_{3}\leq 20$

$x_{2}+4x_{3}\leq 10$

$x_{1},x_{2},x_{3}\geq 0$

$\max x_{1}+x_{2}+x_{3}$

אז צורת ה-slack המתאימה היא:

$z=x_{1}+x_{2}+x_{3}$

$s_{1}=-x_{1}-5x_{2}-2x_{3}+20$

$s_{2}=-x_{2}-4x_{3}+10$

$x_{1},x_{2},x_{3},s_{1},s_{2}\geq 0$

$\max z$

הצגה גאומטרית

הצגה גאומטרית של תכנון ליניארי

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

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

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

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

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

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

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

זוהי אחת מהבעיות שהופיעו במאמר המפורסם של ריצ'רד קארפ מ-1972, בו הוא הציג רשימה של 21 בעיות NP שלמות. למעשה, הבעיה אותה הציג קארפ חלשה הרבה יותר: המשתנים יכולים לקבל ערכים בוליאנים בלבד (0 או 1), ואין פונקציית מטרה למקסם – צריך לענות רק על השאלה האם קיים פתרון או לא. הוא הציג רדוקציה מבעיית הספיקות.

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

ניתן גם לדרוש שרק חלק מהמשתנים יהיו שלמים; בעיה כזאת נקראת "תכנון ליניארי מעורב" (MIP - Mixed Integer Programming) והיא קשה לפחות כמו תכנון ליניארי בשלמים, כי כל בעיית תכנון ליניארי בשלמים היא בפרט גם בעיית תכנון ליניארי מעורב.

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

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

דוגמה לקריטריון כזה היא: בהינתן בעיה $Ax\geq b$, אם המטריצה $A$ היא בעלת ערכים שלמים ויונימודולרית לחלוטין, כלומר הדטרמיננטה של כל תת-מטריצה של $A$ היא 0, 1, או 1-. בנוסף, כל הערכים של $b$ צריכים להיות שלמים.

דוגמאות

הקצאת משאבים

נניח שבמפעל מסוים רוצים לייצר שלושה מוצרים: מוצר 1, מוצר 2 ומוצר 3. לכל מוצר צריך כמות מסוימת של מים ושל חשמל כדי לייצר אותו. כמות המים והחשמל של המפעל מוגבלות. כמו כן לכל מוצר יש מחיר אחר בו אפשר למכור אותו. נניח שלמוצר ה-i צריך $e_{i}$ חשמל לקילו, $w_{i}$ מים לקילו, ומקבלים תמורתו $c_{i}$ שקלים לקילו. סה"כ יש למפעל $e$ חשמל ו-$w$ מים. אז ניתן לכתוב את המשוואות הבאות:

$e_{1}x_{1}+e_{2}x_{2}+e_{3}x_{3}\leq e$

$w_{1}x_{1}+w_{2}x_{2}+w_{3}x_{3}\leq w$

$x_{1}\geq 0,\ x_{2}\geq 0,\ x_{3}\geq 0$

$\max c_{1}x_{1}+c_{2}x_{2}+c_{3}x_{3}$

פתרון הבעיה ימצא את המספרים $x_{1},x_{2},x_{3}$, מהם ניתן למצוא את הכמויות שנייצר מכל מוצר.

בעיית הזרמה

נאמר שבמדינה מסוימת יש 3 נמלים ו-2 תחנות כוח. בנמל מספר $i$ פורקים בכל יום $a_{i}$ ליטרים של נפט. תחנת כוח מספר $j$ זקוקה ל-$b_{j}$ ליטרים כדי לפעול. כמו כן בין נמל $i$ לתחנה $j$ יש כביש באורך $c_{i,j}$ (כאשר עלות ההובלה של ליטר נפט לקילומטר היא קבועה). יש למצוא איך להזרים נפט במינימום מחיר.

כדי לפתור את הבעיה נגדיר 6 משתנים:

$x_{1,1},x_{1,2},x_{2,1},x_{2,2},x_{3,1},x_{3,2}$

כאשר משתנה $x_{i,j}$ פירושו "כמות הליטרים שמזרימים מנמל $i$ לתחנה $j$ ".

האילוצים הם:

$x_{1,1}+x_{1,2}\leq a_{1}$

$x_{2,1}+x_{2,2}\leq a_{2}$

$x_{3,1}+x_{3,2}\leq a_{3}$

$x_{1,1}+x_{2,1}+x_{3,1}\geq b_{1}$

$x_{1,2}+x_{2,2}+x_{3,2}\geq b_{2}$

$x_{1,1},x_{1,2},x_{2,1},x_{2,2},x_{3,1},x_{3,2}\geq 0$

$\min c_{1,1}x_{1,1}+c_{1,2}x_{1,2}+c_{2,1}x_{2,1}+c_{2,2}x_{2,2}+c_{3,1}x_{3,1}+c_{3,2}x_{3,2}$

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

ניתן לראות שאם מתקיים $a_{1}+a_{2}+a_{3}<b_{1}+b_{2}$ אז אין לבעיה פתרון. ואכן, אם בשלושת הנמלים יחד פורקים פחות נפט מהכמות שדרושה לתחנות, בוודאי אין אפשרות להזרים מספיק נפט.

בעיית כיסוי הקודקודים

דוגמה לבעיית כיסוי קודקודים

בעיית כיסוי הקודקודים היא: בהינתן גרף $G$, יש למצוא קבוצת קודקודים קטנה ביותר $S$, כך שלכל קשת $e$ המקיימת $e=(u,v)$, לפחות אחד מהקודקודים $u,v$ נמצא ב-$S$. זוהי בעיה NP קשה. נציג בעיית תכנון ליניארי בשלמים שפותרת אותה:

לכל קודקוד $v$ יהיה משתנה $x_{v}$ שאומר "הקודקוד $v$ ב-$S$" אז המשוואות הן: לכל קשת $(u,v)$, המשוואה תהיה $x_{u}+x_{v}\geq 1$ (כלומר לפחות אחד מהקודקודים אכן ב-S). ובנוסף נדרוש $x_{v}\geq 0$ לכל קודקוד v. (אין צורך לדרוש $x_{u}\leq 1$ שכן זה בהכרח יתקיים בפתרון המינימלי, שהרי כל פתרון שבו $x_{v}>1$ יישאר כזה גם אם $x_{v}=1$). יש למזער את הסכום $\sum _{v\in G}x_{v}$.

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

למשל, עבור הבעיה שבתמונה שמשמאל המשתנים הם $x_{1},...,x_{6}$ והאילוצים הם $x_{1}+x_{2}\geq 1,x_{1}+x_{5}\geq 1,x_{2}+x_{5}\geq 1,x_{2}+x_{3}\geq 1,x_{5}+x_{4}\geq 1,x_{3}+x_{4}\geq 1,x_{4}+x_{6}\geq 1$ בנוסף לאילוץ $x_{i}\geq 0$ לכל i. פונקציית המטרה היא $x_{1}+...+x_{6}$. הפתרון האופטימלי הוא $x_{1}=x_{2}=x_{4}=1,x_{3}=x_{5}=x_{6}=0$ כך שהתוכנית הליניארית שלמה במקרה זה, ומצאה כיסוי מינימלי - {1,2,4}. ניתן להראות גם שעבור גרף דו צדדי תמיד יהיה פתרון בשלמים, כיוון שהמטריצה יונימודולרית לחלוטין (כפי שתואר למעלה).

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

סודוקו

דוגמה לסודוקו

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

לכל שורה $r$, עמודה $c$ וספרה $i$ ניצור משתנה $x_{r,c,i}$ שאומר "במשבצת שנמצאת בשורה $r$, עמודה $c$ נמצאת הספרה $i$". כל אחד משלושת הפרמטרים הללו הוא מקבל ערכים בין 1–9 (יש 9 שורות, 9 עמודות ו-9 ספרות בסודוקו) ולכן סך הכל יש $9\cdot 9\cdot 9=729$ משתנים. משתנה $x_{r,c,i}$ שווה ל-1 אם בשורה $r$ ועמודה $c$ נמצאת הספרה $i$, אחרת $x_{r,c,i}$ שווה לאפס.

האילוצים הם:

• לכל שורה $r$ ועמודה $c$, יש בדיוק ספרה אחת שנמצאת במשבצת המתאימה, כלומר בדיוק אחד מהמשתנים $x_{r,c,1},...,x_{r,c,9}$ מקבל את הערך 1. לכן האילוץ הוא $x_{r,c,1}+...+x_{r,c,9}=1$.
• לכל שורה $r$, ולכל שתי עמודות שונות $c_{1},c_{2}$, לא ייתכן שאותה ספרה תתקבל בשתיהן (מאילוצי הסודוקו). לכן לכל ספרה $i$ מוסיפים את האילוץ $x_{r,c_{1},i}+x_{r,c_{2},i}\leq 1$ (לא ייתכן ששני המשתנים מקבלים את הערך 1 בו זמנית). בדומה גם לכל עמודה $c$ ולכל שתי שורות שונות $r_{1},r_{2}$ מוסיפים את האילוץ $x_{r_{1},c,i}+x_{r_{2},c,i}\leq 1$ ולכל שתי משבצות $(r_{1},c_{1}),(r_{2},c_{2})$ שנמצאות באותו ריבוע 3x3, גם כן נוסיף את האילוץ $x_{r_{1},c_{1},i}+x_{r_{2},c_{2},i}\leq 1$.

דוגמאות לאילוצים שכאלה: $x_{2,5,6}+x_{2,9,6}\leq 1,x_{4,6,2}+x_{8,6,2}\leq 1,x_{1,1,1}+x_{3,3,1}\leq 1$

• הרמזים ההתחלתיים נותנים גם הם אילוצים. למשל, בסודוקו שמשמאל בשורה 1, עמודה 1 נמצאת הספרה 5. אם כן המשתנה $x_{1,1,5}$ חייב לקבל את הערך 1, ואפשר להוסיף את האילוץ $x_{1,1,5}=1$. באופן כללי אם ברמזים נתון שבמשבצת שבשורה $r$ ועמודה $c$ יש את הערך $i$, אז אפשר להוסיף את האילוץ $x_{r,c,i}=1$.
• נוסף לכל אלה יש להוסיף את האילוץ $0\leq x_{r,c,i}\leq 1$ לכל המשתנים.

כדי לפתור את הסודוקו, יש למצוא פתרון כלשהו בשלמים למערכת האילוצים. כלומר אין פונקציית מטרה (מבחינה פורמלית פונקציית המטרה היא הפונקציה הקבועה 0). מפתרון זה ניתן לקרוא את הפתרון. למשל בסודוקו שמשמאל נקבל שבפתרון המערכת מתקיים $x_{1,3,4}=1$ ואם כן המשבצת השלישית בשורה הראשונה מקבלת את הערך 4.

שימו לב: לא יכולנו להשתמש במשתנה $x_{r,c}$ כדי לקבל ישירות את הספרה שלו (למשל, שהמשתנה $x_{1,3}$ יקבל בפתרון את הערך 4). הסיבה היא שצריך להוסיף, למשל, אילוצי $x_{r,c1}\neq x_{r,c2}$, ולא ניתן לעשות זאת באילוצי תכנון ליניארי.

הצורה הדואלית

עבור הבעיה $Ax\leq b,x\geq 0,\max c^{T}x$ קיימת הבעיה הדואלית $A^{T}y\geq c,y\geq 0,\min b^{T}y$כאשר $y$ הוא וקטור m ממדי ו- $A^{T}$ זוהי המטריצה המשוחלפת ל-$A$. למעבר זה יש חשיבות תאורטית בהוכחות שונות, ובפרט בהוכחת הנכונות של אלגרותמים שונים.

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

$e_{1}x_{1}+e_{2}x_{2}+e_{3}x_{3}\leq e$

$w_{1}x_{1}+w_{2}x_{2}+w_{3}x_{3}\leq w$

$x_{1}\geq 0,x_{2}\geq 0$

$\max c_{1}x_{1}+c_{2}x_{2}+c_{3}x_{3}$

הבעיה הדואלית היא:

$e_{1}y_{1}+w_{1}y_{2}\geq c_{1}$

$e_{2}y_{1}+w_{2}y_{2}\geq c_{2}$

$e_{3}y_{1}+w_{3}y_{2}\geq c_{3}$

$\min ey_{1}+wy_{2}$

ניתן לחשוב על בעיה זאת כבעיה הבאה: $y_{1}$ הוא משתנה שמייצג חשמל, ו-$y_{2}$ משתנה שמייצג מים. אז כל משוואה מתייחסת למוצר אחר, ומבקשת, תחת תנאי חשמל ומים, שהרווח יהיה לפחות מספר מסוים. למשל המשוואה הראשונה מתייחסת למוצר מספר 1, בו המשוואה הראשונה דורשת שנשקיע מספיק חשמל ומים כדי לקבל את הרווח $c_{1}$. בדומה משוואות 2,3 מתייחסות למוצרים 2,3 בהתאמה. תחת תנאים אלה, יש למזער את העלות הכוללת של מים וחשמל.

הבעיה הדואלית לדוגמה השנייה כוללת את המשתנים $x_{e}$, משתנה לכל קשת, כך שלכל קודקוד $v$ יש את המשוואה $\sum _{v\in e}x_{e}\leq 1$ ויש למקסם את $\sum _{e\in E[G]}x_{e}$. כאשר המשתנים שלמים, הבעיה היא למצוא קבוצת קשתות מקסימלית כך שכל קודקוד נוגע בלכל היותר אחת מהן - בעיה הידועה כמציאת שידוך מקסימלי (לה יש פתרון פולינומי).

משפטי הדואליות

משפט הדואליות החלש קובע שאם הבעיה $\max c^{T}x$ היא בצורה קנונית, אז הבעיה הדואלית $\min b^{T}y$ מקיימת שלכל זוג פתרונות $x,y$ מתקיים $b^{T}y\geq c^{T}x$, ובפרט גם לפתרונות האופטימליים. . משפט הדואליות החזק קובע שלפתרונות האופטימליים $b^{T}y=c^{T}x$ (אם הם קיימים - או שאחת הבעיות לא חסומה, ואז השנייה לא פיזיבלית).

משפט הדואליות החלש מאפשר למצוא תנאי עצירה לאלגוריתמים שונים: אם מריצים את האלגוריתם על הבעיה ועל הבעיה הדואלית לה במקביל, מקבלים חסמים מכל בעיה על השנייה: לכל $y$ שמוצאים, $b^{T}y$ מהווה חסם עליון ל-$c^{T}x$, ולהפך.

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

הוכחה

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

מתקיים $c^{T}x=\sum _{j}c_{j}x_{j}$. כיוון ש-$x$ הוא פתרון, אז לכל $i$ מתקיים $\sum _{j}a_{ij}x_{j}\leq b_{i}$. כמו כן, כיוון ש-$y$ הוא פתרון, לכל $j$ מתקיים $\sum _{i}a_{ij}y_{j}\geq c_{j}$. נשלב את כל זאת כדי לקבל:

$c^{T}x=\sum _{j}c_{j}x_{j}\leq \sum _{j}(\sum _{i}a_{ij}y_{i})x_{j}=\sum _{i,j}a_{ij}x_{j}y_{i}=\sum _{i}(\sum _{j}a_{ij}x_{j})y_{i}\leq \sum _{i}b_{i}y_{i}=b^{T}y$

כרצוי.

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

בעיות כיסוי ואריזה

בעיה בצורה קנונית $Ax\leq b,x\geq 0,\max c^{T}x$ נקראת "בעיית אריזה" אם כל ערכי המטריצות והווקטורים $A,b,c$ הם בעלי ערכים אי שליליים. הסיבה לכינוי זה היא שאנחנו מנסים למקסם את מה שאנחנו מכניסים לערכים תוך מגבלה מלמעלה - כמו אדם שמנסה לארוז כמה שיותר לתוך נפח מוגבל.

בעיה בצורה הדואלית, $A^{T}y\geq c,y\geq 0,\min b^{T}y$, תקרא "בעיית כיסוי" אם היא מקיימת תכונה זו. הסיבה לכינוי זה היא שאנחנו מנסים למצוא ערכים קטנים ביותר שיעברו סף מסוים - מנסים לכסות את הערכים ב-$c$.

לבעיות אלה חשיבות מיוחדת, בפרט בשלמים, ואלגוריתמים רבים פותחו במיוחד בשבילן.

דוגמאות לבעיות אריזה הן בעיית תרמיל הגב, מציאת קבוצה בלתי תלויה מקסימלית, בעיית אריזת קבוצות (set packing) ובעיית אריזת הדליים (bin packing).

דוגמאות לבעיות כיסוי הן בעיית כיסוי קודקודים ובעיית כיסוי קבוצות.

אלגוריתמים

שיטת הסימפלקס

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

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

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

זמן ריצת האלגוריתם: צעד pivot לוקח $O(mn)$, לכן זמן הריצה הוא $O(pmn)$, כאשר $p$ הוא מספר הצעדים שנעשה. $p$ חסום על ידי מספר הקודקודים שעלול להיות אקסופננציאלי, לכן זמן הריצה עלול להיות אקספוננציאלי. עד היום לא ידועה שיטה פולינומית לממש את זמן הריצה (אך גם לא ידוע שאין שיטה כזאת), ויש חסם תחתון אקספוננציאלי על רבות מהשיטות.

שיטת האליפסואיד

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

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

האלגוריתם רץ בסיבוכיות $O(n^{6}L)$, כאשר $L$ הוא אורך הקלט - מספר הביטים שצריך כדי לתאר את כל הבעיה.

האלגוריתם של קרמרקר

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

האלגוריתם נקרא גם "שיטת הנקודה הפנימית" (interior point method) משום שהוא "מחפש" את הנקודה האופטימלית בפנים הפוליטופ, ולא על שפתו כמו שיטת הסימפלקס. זמן הריצה שלו הוא $O(n^{3}L)$

האלגוריתם הנוכחי

נכון ל-2022, האלגוריתם הטוב ביותר הידוע רץ בסיבוכיות $O((n^{\omega }+n^{2.5-\alpha /2}+n^{2+1/6})L)$, כאשר $\omega$ הוא המעריך של ביצוע כפל מטריצות, כלומר כזה שניתן עבורו להכפיל מטריצות בסיבוכיות $n^{\omega }$ (נכון ל-2022, ידוע $\omega \leq 2.38$), ו-$\alpha$ הוא המעריך הדואלי של כפל מטריצות, כלומר המספר המקסימלי עבורו ניתן להכפיל מטריצות בגודלי $n\times n,n\times n^{\alpha }$ בזמן $O(n^{2})$ (נכון ל-2022, ידוע $\alpha \geq 0.31$).

אלגוריתמים למציאת פתרון בשלמים

כאמור לעיל, הבעיה בשלמים היא NP קשה, לכן בהנחת $P\neq NP$, אין לה אלגוריתם פולינומי, אפילו אם לא מנסים למקסם פונקציית מטרה. לכן אלגוריתמים לפתרון תכנון ליניארי בשלמים עושים את אחד הדברים הבאים:

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

שימוש באלגוריתמים הרגילים

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

בבעיות אריזה, אם מעגלים את כל הערכים למטה, מקבלים פתרון חוקי (כי כל הערכים נשארו אי שליליים, ואי-הגדלה של כל המשתנים לא יכולה לסתור אילוץ). הוא עשוי להיות קטן מהפתרון האופטימלי, אך אם פונקציית המטרה היא $\sum c_{i}x_{i}$, ניתן לדעת שעיגול כל הערכים למטה יקטין כל משתנה בלכל היותר 1, ולכן יקטין את פונקציית המטרה בלכל היותר $\sum c_{i}$. בדומה, עיגול למעלה של כל הערכים בבעיית כיסוי ימצא פתרון חוקי שפונקציית המטרה עליו עשויה להיות רחוקה ב-$\sum b_{i}$ מהערך האופטימלי.

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

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

בסיס גרייבר

ערך מורחב – בסיס גרייבר

בהינתן מטריצה A בשלמים, בסיס גרייבר מאפשר לבצע עליה עיבוד מוקדם (שזמנו אקספוננציאלי) כדי לקבל מידע, בעזרתו יהיה אפשר לפתור את הבעיה $Ax=b,\max c^{T}x$ בזמן פולינומי לכל וקטורים שלמים $b,c$. השיטה מבוססת על מציאת קבוצה סופית של איברים $G(A)$ (שנקראת בסיס גרייבר), שמהם ניתן לחלץ פתרונות באמצעות אלגוריתם איטרטיבי.

אלגוריתם לנסטרה

אלגוריתם לנסטרה מאפשר לפתור את הבעיה בזמן פולינומי כאשר מספר המשתנים קבוע. יותר בפירוט, אם ב-A יש $m$ שורות והמקדמים שלה חסומים על ידי $N$, האלגוריתם מאפשר לפתור בזמן פולינומי ב-$O(m\log N)$. האלגוריתם עובר על המשתנים בזה אחר זה ומוצא קטע לכל אחד מהם בו הוא חסום בעזרת גאומטריה של מספרים, ולאחר מכן עובר על כל האפשרויות. האלגוריתם הומצא על ידי הנדריק לנסטרה בשנת 1983. זמן הריצה המקורי היה $(m\log N)^{O(1)}\cdot 2^{O(n^{3})}$, ומאז שופר כמה פעמים.

אלגוריתמים כלליים

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

• backtracking (לבעיות אריזה): בהינתן משתנה $x_{i}$, והצבות לערכים $x_{1},...,x_{i-1}$, נציב ב$x_{i}$ את הערכים מ-0 ומעלה בזה אחר זה, ולכל אחד מהם נפתור רקורסיבית עבור המשתנה הבא. מפסיקים כאשר אחד האילוצים נשבר. אם $x_{i}=x_{n}$ (ומצאנו הצבה שנותנת פתרון חוקי) זוכרים את ערך פונקציית המטרה, כדי להחזיר את הערך המינימלי. האלגוריתם מסתיים כאשר עוברים על כל הערכים עבור $x_{1}$ (ואז הפתרון מדויק, אך הזמן עלול להיות אקספוננציאלי) או כאשר עובר זמן שהוגדר מראש (ואז הוא לאו דווקא ימצא את הפתרון האופטימלי).
• להתחיל עם פתרון כלשהו ולשפר אותו בעזרת אלגוריתמים כגון חיפוש מקומי או אופטימיזציית קן הנמלים.
• שיטות שונות של למידת מכונה, למשל רשת עצבית מלאכותית.

היסטוריה

לאוניד קנטורוביץ'

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

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

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

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

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

LP Solvers

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

import cvxpy
x1 = cvxpy.Variable(name="x1")
x2 = cvxpy.Variable(name="x2")
x3 = cvxpy.Variable(name="x3")
constraints = [
    3 * x1 - 2 * x2 + x3 <= 9,
    7 * x2 - 2 * x3 <= 6,
    -5 * x1 + 10 * x2 <= 5,
    x1 + x2 - x3 <= 9,
]
target = cvxpy.Maximize(2 * x1 + 3 * x2 + x3)
problem = cvxpy.Problem(target, constraints)
problem.solve()
print(f"x1={x1.value}, x2={x2.value}, x3={x3.value})

הרצת התוכנית מדפיסה את הפלט x1=3, x2=2, x3=4.

ראו גם

• תכנון דינמי
• תכנון לא-ליניארי
• אופטימיזציה קמורה

לקריאה נוספת

• Jiˇrí Matoušek, Bernd Gärtner, Understanding and Using Linear Programming
• Stephen Boyd, Lieven Vandenberghe, Convex Optimization

קישורים חיצוניים

מדיה וקבצים בנושא תכנון ליניארי בוויקישיתוף

• תכנון ליניארי, באתר MathWorld (באנגלית)
• topic/linear-programming-education תכנון ליניארי, באתר אנציקלופדיה בריטניקה (באנגלית)
• אופטימיזציה מתמטית, דף שער בספרייה הלאומית

הערות שוליים

ערך מומלץ