stanford-oval/wikipedia huggingface dataset:
תכנון ליניארי
הצגה גאומטרית

ניתן לחשוב על הווקטורים באורך 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 מים. אז ניתן לכתוב את המשוואות הבאות:
פתרון הבעיה ימצא את המספרים  x_{1},x_{2},x_{3}, מהם ניתן למצוא את הכמויות שנייצר מכל מוצר.
דוגמאות > בעיית הזרמה

נאמר שבמדינה מסוימת יש 3 נמלים ו-2 תחנות כוח. בנמל מספר  i פורקים בכל יום  a_{i} ליטרים של נפט. תחנת כוח מספר  j זקוקה ל- b_{j} ליטרים כדי לפעול. כמו כן בין נמל  i לתחנה  j יש כביש באורך  c_{i,j} (כאשר עלות ההובלה של ליטר נפט לקילומטר היא קבועה). יש למצוא איך להזרים נפט במינימום מחיר.
כדי לפתור את הבעיה נגדיר 6 משתנים:
כאשר משתנה  x_{i,j} פירושו "כמות הליטרים שמזרימים מנמל  i לתחנה  j ".
האילוצים הם:
שלושת האילוצים הראשונים הם על הנמלים - כל נמל יכול להוציא לכל היותר את כמות הנפט שיש לו. שני האילוצים שאחר כך הם אילוצים על התחנות - כל תחנה צריכה לקבל כמות מספקת של נפט. לאחר מכן יש אילוץ אי-שליליות (אי אפשר להעביר כמות שלילית של נפט). פונקציית המטרה היא העלות הכוללת של השינוע ויש למזער אותה.
ניתן לראות שאם מתקיים  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.
הרמזים ההתחלתיים נותנים גם הם אילוצים. למשל, בסודוקו שמשמאל בשורה 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. למעבר זה יש חשיבות תאורטית בהוכחות שונות, ובפרט בהוכחת הנכונות של אלגרותמים שונים.
בנוסף, ניתן למצוא גם קשר רעיוני בין הבעיות. למשל, נחזור לדוגמה הראשונה. המשוואות היו
הבעיה הדואלית היא:
ניתן לחשוב על בעיה זאת כבעיה הבאה:  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}. נשלב את כל זאת כדי לקבל:
כרצוי.
את משפט הדואליות החזק ניתן להוכיח בעזרת הלמה של פרקס.
בעיות כיסוי ואריזה

בעיה בצורה קנונית  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
ביאורים

↑  באנגלית הטרמינולוגיה לא אחידה; יש מקומות בהם קוראים לצורה שלא חייבת להיות חסומה polyhedron ולצורה שחייבת להיות חסומה polytope, ויש מקומות בהם זה הפוך.
↑  נזכיר שבעיית כיסוי היא בצורה דואלית לקנונית, ופונקציית המטרה היא  \min b^{T}x
הערות שוליים

↑  Standard form for Linear Programs
↑  Convex Optimization, p. 131
↑  Linear Programming: Geometric Approach
↑  Convex Optimization, p. 31
↑  The Computational Complexity of Integer Programming with Alternations
1 2  Richard Karp, reducibility among combinatoricial problems
↑  Total unimodularity
↑  Packing, Covering and Partitioning Problems with Strongly Unimodular Constraint Matrices
↑  הדגמה של הפתרון
↑  The Max-Flow Min-Cut Theorem
↑  K¨onig’s Theorem
↑  Duality and the Minimax theorem
↑  Strong Duality
↑  Nearly Linear-Time Packing and Covering LP Solvers
↑  simplex method
↑  The ellipsoid method
1 2  Narendra Karmarkar, A New Polynomial-Time Algorithm for Linear Programming
↑  Solving Empirical Risk Minimization in the Current Matrix Multiplication Time
↑  Integer Programming with a Fixed Number of Variables
↑  המאמר מתורגם לאנגלית
↑  mathematical methods of organizing and planning production, p. 390
↑  mathematical methods of organizing and planning production, p. 368
↑  reminiscences about the origin of linear programming, p. 1
↑  נימוקי הזכייה באתר פרס נובל
↑  reminiscences about the origin of linear programming, p. 2
↑  reminiscences about the origin of linear programming, p. 4
↑  reminiscences about the origin of linear programming, p. 6
↑  Eugene L. Lawler, The Great Mathematical Sputnik of 1979
↑  Speeding-up linear programming using fast matrix multiplication, Pravin M. Vaidya
↑  REMINISCENCES ABOUT THE ORIGINS OF LINEAR PROGRAMMING, p. 2
↑  אתר הבית של cvxpy
| --- | --- |
ערך מומלץ: 
| --- | --- |
בקרת זהויות :  NLI: 987007555765405171  BnF: cb119415380 (data)  GND: 4035816-1  LCCN: sh85082127  NDL: 00570683  NKC: ph122356 
הצגה גאומטרית של תכנון ליניארי
בעיית תכנון ליניארי שפתרונותיה נמצאים בין הקווים הכחולים; הנקודות האדומות שעל גבי מערכת הצירים מסמנות את הפתרונות השלמים שקיימים לבעיה זו.
דוגמה לבעיית כיסוי קודקודים
דוגמה לסודוקו
הדגמה ויזואלית לשיטת הסימפלקס. הולכים לאורך צלעות הפאון מקודקוד לקודקוד, עד לפתרון אופטימלי.
איטרציה של שיטת האליפסואיד. עוברים מהאליפסה האדומה לאליפסה הירוקה, שמכילה גם היא את השטח הכחול.
לאוניד קנטורוביץ'
היסטוריה של מכניקת הזורמים

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

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

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

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