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

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

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

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

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

==הקדמה==
בעיית תכנון ליניארי מורכבת מאוסף משתנים <math>x_1,...,x_n</math>, עליהם יש אילוצים ליניאריים. אילוץ ליניארי הוא [[אי-שוויון (מתמטיקה)|אי-שוויון]] בין [[משוואה ליניארית]] על המשתנים לבין קבוע, כלומר <math>a_{1i}x_1+...+a_{ni}x_n\le b_i</math> או <math>a_{1i}x_1+...+a_{ni}x_n\ge b_i</math>. ניתן גם לדרוש שוויון; אם תנאי הבעיה אינם מאפשרים זאת, ניתן לדרוש שוויון באמצעות שני האי-שוויונות האחרונים שביחד שקולים לו. בנוסף ישנה פונקציית מטרה <math>c_1 x_1+...+c_nx_n</math> שאותה יש למזער או למקסם.

לבעיה לא תמיד קיים פתרון (דוגמה פשוטה: התנאים הם <math>x\ge 1, x\le 0</math>), וייתכן גם שפונקציית המטרה איננה חסומה (דוגמה פשוטה: התנאים הם <math>x\ge 0</math>, ויש למקסם את <math>x</math>). לפיכך, פתרון הבעיה יכול להיות אחת משלוש אפשרויות: אין פתרון כלל, אין פתרון חסום, יש לפחות פתרון אופטימלי אחד.

לדוגמה: נניח ש-<math>n=3</math> כלומר ישנם שלושה משתנים, והאילוצים הם:
: <math>3x_1-2x_2+x_3\le 9</math>
: <math>7x_2-2x_3\le 6</math>
: <math>-5x_1+10x_2\le 5</math>
: <math>x_1+x_2-x_3\le 9</math>
פתרון למערכת האילוצים הזאת הוא הצבה של ערכים מספריים למשתנים, כך שכל האילוצים מתקיימים. למשל <math>x_1=1,x_2=1,x_3=5</math> וכן <math>x_1=3,x_2=2,x_3=4</math> הם פתרונות למערכת. לעומת זאת, <math>x_1=5,x_2=0,x_3=0</math> הוא לא פתרון, שכן הוא לא מקיים את אי השוויון הראשון: לא מתקיים <math>3 \cdot 5 -2\cdot 0+0 \le 9</math>.

בנוסף למערכת האי שוויונות, נניח שצריך למקסם את פונקציית המטרה  <math>2x_1+3x_2+x_3</math>. ניתן לראות שהצבת הפתרון הראשון שהצגנו נותנת <math>2\cdot 1+3\cdot 1+5=10</math>, ואילו הצבת הפתרון השני נותנת <math>2\cdot 3+3\cdot 2+4=16</math>. לכן, הפתרון השני נותן ערך גבוה יותר לפונקציית המטרה. ניתן להראות (בשיטות שידונו בהמשך הערך) שכל פתרון חוקי (כלומר פתרון שמקיים את כל האילוצים) אחר שנציב למשתנים יתן ערך קטן יותר מ-16, ועל כן <math>x_1=3,x_2=2,x_3=4</math> הוא הפתרון האופטימלי.

===כתיב מטרציוני===
אם כל אי השוויונות נתונים באותו כיוון (כלומר בכולם <math>ax_1+...\le b</math> או בכולם <math>ax_1+...\ge b</math>), אז נוח להציג את הבעיה בעזרת [[מטריצה|מטריצות]].

למשל, את הבעיה שהצגנו לעיל ניתן להציג בכתיב מטרציוני כך:
:<math>\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} \le \begin{pmatrix} 9 \\ 6 \\ 5 \\ 9 \end{pmatrix}	</math>
:<math>\max \begin{pmatrix} 2 & 3 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} </math>
בכתיב זה, בעיית תכנון ליניארי כוללת וקטור <math>x</math> באורך <math>n</math>, מטריצה <math>A</math> בגודל <math>m \times n</math>, וקטור <math>b</math> בגודל <math>m</math>, ווקטור <math>c</math> בגודל <math>n</math>, כך שהבעיה היא למקסם/למזער את <math>c^Tx</math> תחת האילוצים <math>Ax\le b</math> או <math>Ax\ge b</math>.

===צורה קנונית===
בעיית תכנון ליניארי תקרא בעיה ב"צורה קנונית" אם היא מקיימת את התכונות הבאות:{{הערה|[https://www.matem.unam.mx/~omar/math340/std-form.html Standard form for Linear Programs]}}
* כל התנאים הם מהצורה <math>a_{1i}x_1+...+a_{ni}x_n\le b_i</math>
* כל המשתנים מקיימים גם <math>x_i \ge 0</math>
* המטרה היא למקסם ביטוי ליניארי (ולא למזער אותו)
כל בעיית תכנון ליניארי ניתן להעביר לצורה קנונית:
* אם התכונה הראשונה אינה מתקיימת, ניתן להפוך את <math>a_{1i}x_1+...+a_{ni}x_n\ge b_i</math> ל <math>-a_{1i}x_1-...-a_{ni}x_n\le -b_i</math>.
* אם התכונה השנייה אינה מתקיימת עבור משתנה <math>x</math>, ניתן להחליף את המשתנה <math>x</math> בביטוי <math>x'-x''</math> כאשר דורשים <math>x',x''\ge 0</math>.
* אם התכונה השלישית אינה מתקיימת, ניתן להחליף את "למזער את <math>c_1 x_1+...+c_nx_n</math>" ב"למקסם את <math>-c_1 x_1+...-c_nx_n</math>" (ווקטור הפתרון יהיה אותו וקטור).
סך הכול הגדלנו את כמות המשתנים והמשוואות פי 2 לכל היותר.

===צורת slack===
זוהי צורת הצגה נוספת של בעיית תכנון ליניארי שהיא בעלת חשיבות באלגוריתמים כגון [[שיטת הסימפלקס]]. בצורה זו מוסיפים משתני עזר (הנקראים משתני slack) כדי שתנאי הבעיה יהיו שוויונות או תנאי אי שליליות על המשתנים וגם פונקציית המטרה בנויה ממשתנה אחד בלבד.{{הערה|[https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf Convex Optimization], p. 131}}

בכתיב מטריציוני, הבעיה מוצגת כ[[מטריצת בלוקים]] באופן הבא:
: <math>
 \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}
</math>
:<math>\mathbf{x} \ge 0, \mathbf{s} \ge 0</math>
: <math>\max z</math>
כאשר <math>x</math> הם המשתנים המקוריים, <math>s</math> הם משתני ה slack, ו-<math>z</math> הוא המשתנה שיש למקסם.

לדוגמה, אם הבעיה היא:
: <math>x_1+5x_2+2x_3\le 20</math>
: <math>x_2+4x_3\le 10</math>
:<math>x_1,x_2,x_3\ge 0</math>
: <math>\max x_1+x_2+x_3</math>
אז צורת ה-slack המתאימה היא:
:<math>z=x_1+x_2+x_3</math>
: <math>s_1 = -x_1-5x_2-2x_3 + 20</math>
: <math>s_2 = -x_2-4x_3+10</math>
:<math>x_1,x_2,x_3,s_1,s_2\ge 0</math>
: <math>\max z</math>

==הצגה גאומטרית ==
[[קובץ:Linear Programming Feasible Region.svg|frame|הצגה גאומטרית של תכנון ליניארי]]
ניתן לחשוב על הווקטורים באורך n כעל נקודות ב[[מרחב אוקלידי|מרחב]] ה-n-[[ממד (מתמטיקה)|ממדי]]. במקרה זה, כל אילוץ חוצה את המרחב לשני חצאי מרחבים, כך שהפתרונות החוקיים נמצאים באחד מהם. אוסף האילוצים יחדיו מתורגם ל[[חיתוך (מתמטיקה)|חיתוך]] של כל חצאי המרחבים הנוצרים באמצעות אוסף זה. הצורה גאומטרית המתקבלת נקראת [[פוליטופ]] {{אנ|Polytope}}.{{הערה|[https://people.richland.edu/james/ictcm/2006/geometric.html Linear Programming: Geometric Approach]}}

למשל, אם ישנם שני משתנים אז כל אילוץ יוצר חצי מישור ואם החיתוך של כל חצאי המישורים האלה חסום אז מתקבל [[מצולע קמור]]. במרחב n-ממדי כללי, כל אילוץ באוסף יוצר חצי מרחב והחיתוך של כל חצאי המרחבים האלה יוצר [[פאון]] קמור. משיקולי נוחות, נתייחס בהמשך ערך זה לצורות גאומטריות אלה כמצולע או פאון גם אם הן אינן חסומות ועל כן אינן מצולע/פאון במובן הרגיל. כך גם עושים בספרות המקצועית בנושא.{{ביאור|ב[[אנגלית]] הטרמינולוגיה לא אחידה; יש מקומות בהם קוראים לצורה שלא חייבת להיות חסומה polyhedron ולצורה שחייבת להיות חסומה polytope, ויש מקומות בהם זה הפוך.}}{{הערה|[https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf Convex Optimization], p. 31}}

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

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

==תכנון ליניארי בשלמים==
[[קובץ:IP polytope with LP relaxation.svg|ממוזער|בעיית תכנון ליניארי שפתרונותיה נמצאים בין הקווים הכחולים; הנקודות האדומות שעל גבי מערכת הצירים מסמנות את הפתרונות השלמים שקיימים לבעיה זו.]]
תכנון ליניארי בשלמים (ILP - Integer Linear Programming) מציין בעיה דומה לבעיית התכנון הליניארי, אלא שהמשתנים חייבים לקבל ערכים [[מספר שלם|שלמים]] דווקא. בניגוד לבעיית תכנון ליניארי רגילה שלה יש פתרון פולינומי, בעיה זאת היא [[NP קשה]]. הצגתה כבעיית הכרעה (האם קיים פתרון שבו ערך פונקציית המטרה עולה על ערך מסוים) היא בעיה NP שלמה. ספירת הנקודות השלמות שמקיימות את התנאים היא בעיה [[Sharp-P|P#]] שלמה.{{הערה|[https://drops.dagstuhl.de/opus/volltexte/2017/7515/pdf/LIPIcs-CCC-2017-6.pdf The Computational Complexity of Integer Programming with Alternations]}}

זוהי אחת מהבעיות שהופיעו במאמר המפורסם של [[ריצ'רד קארפ]] מ-1972, בו הוא הציג [[21 הבעיות ה-NP שלמות של קארפ|רשימה של 21 בעיות NP שלמות]]. למעשה, הבעיה אותה הציג קארפ חלשה הרבה יותר: המשתנים יכולים לקבל ערכים בוליאנים בלבד (0 או 1), ואין פונקציית מטרה למקסם – צריך לענות רק על השאלה האם קיים פתרון או לא. הוא הציג רדוקציה מ[[בעיית הספיקות]].{{הערה|שם=קארפ|[https://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf Richard Karp, reducibility among combinatoricial problems]}}

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

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

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

דוגמה לקריטריון כזה היא: בהינתן בעיה <math>Ax \ge b</math>, אם המטריצה <math>A</math> היא בעלת ערכים שלמים ויונימודולרית לחלוטין, כלומר ה[[דטרמיננטה]] של כל תת-מטריצה של <math>A</math> היא 0, 1, או 1-. בנוסף, כל הערכים של <math>b</math> צריכים להיות שלמים.{{הערה|[https://people.math.carleton.ca/~kcheung/math/notes/MATH5801/07/7_3_total_unimodularity.html Total unimodularity]}}

==דוגמאות==
=== הקצאת משאבים ===
נניח שבמפעל מסוים רוצים לייצר שלושה מוצרים: [[מוצר]] 1, מוצר 2 ומוצר 3. לכל מוצר צריך כמות מסוימת של מים ושל חשמל כדי לייצר אותו. כמות המים והחשמל של המפעל מוגבלות. כמו כן לכל מוצר יש מחיר אחר בו אפשר למכור אותו. נניח שלמוצר ה-i צריך <math>e_i</math> חשמל לקילוגרם, <math>w_i</math> מים לקילוגרם, ומקבלים תמורתו <math>c_i</math> שקלים לקילוגרם. סה"כ יש למפעל <math>e</math> חשמל ו-<math>w</math> מים. אז ניתן לכתוב את המשוואות הבאות:
:<math>e_1x_1+e_2x_2+e_3x_3\le e</math>
:<math>w_1x_1+w_2x_2+w_3x_3\le w</math>
:<math>x_1\ge 0,\ x_2\ge 0,\ x_3\ge 0</math>
:<math>\max c_1x_1+c_2x_2+c_3x_3</math>

פתרון הבעיה ימצא את המספרים <math>x_1,x_2,x_3</math>, מהם ניתן למצוא את הכמויות שנייצר מכל מוצר.

===בעיית הזרמה===
נאמר שבמדינה מסוימת יש 3 נמלים ו-2 [[תחנת כוח|תחנות כוח]]. בנמל מספר <math>i</math> פורקים בכל יום <math>a_i</math> ליטרים של [[נפט]]. תחנת כוח מספר <math>j</math> זקוקה ל-<math>b_j</math> ליטרים כדי לפעול. כמו כן בין נמל <math>i</math> לתחנה <math>j</math> יש כביש באורך <math>c_{i,j}</math> (כאשר עלות ההובלה של ליטר נפט לקילומטר היא קבועה). יש למצוא איך להזרים נפט במינימום מחיר.

כדי לפתור את הבעיה נגדיר 6 משתנים:
:<math>x_{1,1},x_{1,2},x_{2,1},x_{2,2},x_{3,1},x_{3,2}</math>
כאשר משתנה <math>x_{i,j}</math> פירושו "כמות הליטרים שמזרימים מנמל <math>i</math> לתחנה <math>j</math> ".

האילוצים הם:
:<math>x_{1,1}+x_{1,2}\le a_1</math>
:<math>x_{2,1}+x_{2,2}\le a_2</math>
:<math>x_{3,1}+x_{3,2}\le a_3</math>
:<math>x_{1,1}+x_{2,1}+x_{3,1}\ge b_1</math>
:<math>x_{1,2}+x_{2,2}+x_{3,2}\ge b_2</math>
:<math>x_{1,1},x_{1,2},x_{2,1},x_{2,2},x_{3,1},x_{3,2}\ge 0</math>
:<math>\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}</math>
שלושת האילוצים הראשונים הם על הנמלים - כל נמל יכול להוציא לכל היותר את כמות הנפט שיש לו. שני האילוצים שאחר כך הם אילוצים על התחנות - כל תחנה צריכה לקבל כמות מספקת של נפט. לאחר מכן יש אילוץ אי-שליליות (אי אפשר להעביר כמות שלילית של נפט). פונקציית המטרה היא העלות הכוללת של השינוע ויש למזער אותה.

ניתן לראות שאם מתקיים <math>a_1+a_2+a_3<b_1+b_2</math> אז אין לבעיה פתרון. ואכן, אם בשלושת הנמלים יחד פורקים פחות נפט מהכמות שדרושה לתחנות, בוודאי אין אפשרות להזרים מספיק נפט.

===בעיית כיסוי הקודקודים===
[[קובץ:6n-graf.svg|ממוזער|250px|שמאל|דוגמה לבעיית כיסוי קודקודים]]
[[בעיית כיסוי הקודקודים]] היא: בהינתן גרף <math>G</math>, יש למצוא קבוצת קודקודים קטנה ביותר <math>S</math>, כך שלכל קשת <math>e</math> המקיימת <math>e=(u,v)</math>, לפחות אחד מהקודקודים <math>u,v</math> נמצא ב-<math>S</math>. זוהי בעיה NP קשה. נציג בעיית תכנון ליניארי בשלמים שפותרת אותה:

לכל קודקוד <math>v</math> יהיה משתנה <math>x_v</math> שאומר "הקודקוד <math>v</math> ב-<math>S</math>" אז המשוואות הן: לכל קשת <math>(u,v)</math>, המשוואה תהיה <math>x_u+x_v \ge 1</math> (כלומר לפחות אחד מהקודקודים אכן ב-S). ובנוסף נדרוש <math>x_v\ge 0</math> לכל קודקוד v. (אין צורך לדרוש <math>x_u\le 1</math> שכן זה בהכרח יתקיים בפתרון המינימלי, שהרי כל פתרון שבו <math>x_v>1</math> יישאר כזה גם אם <math>x_v=1</math>). יש למזער את הסכום <math>\sum_{v\in G} x_v</math>.

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

למשל, עבור הבעיה שבתמונה שמשמאל המשתנים הם <math>x_1,...,x_6</math> והאילוצים הם <math>x_1+x_2\ge 1, x_1+x_5\ge 1, x_2+x_5\ge 1, x_2+x_3\ge 1, x_5+x_4\ge 1, x_3+x_4\ge 1, x_4+x_6\ge 1 </math> בנוסף לאילוץ <math>x_i \ge 0</math> לכל i. פונקציית המטרה היא <math>x_1+...+x_6</math>. הפתרון האופטימלי הוא <math>x_1=x_2=x_4=1,x_3=x_5=x_6=0</math> כך שהתוכנית הליניארית שלמה במקרה זה, ומצאה כיסוי מינימלי - {1,2,4}. ניתן להראות גם שעבור [[גרף דו צדדי]] תמיד יהיה פתרון בשלמים, כיוון שהמטריצה יונימודולרית לחלוטין (כפי שתואר [[#תכנון ליניארי שלם|למעלה]]).{{הערה|[https://www.jstor.org/stable/3689781 Packing, Covering and Partitioning Problems with Strongly Unimodular Constraint Matrices]}}

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

===סודוקו===
[[קובץ:Sudoku-by-L2G-20050714.svg|ממוזער|דוגמה לסודוקו]]
נדגים כיצד ניתן לפתור [[סודוקו]] באמצעות תכנון ליניארי בשלמים.{{הערה|[https://towardsdatascience.com/using-integer-linear-programming-to-solve-sudoku-puzzles-15e9d2a70baa הדגמה של הפתרון]|כיוון=ימין}}

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

האילוצים הם:
* לכל שורה <math>r</math> ועמודה <math>c</math>, יש בדיוק ספרה אחת שנמצאת במשבצת המתאימה, כלומר בדיוק אחד מהמשתנים <math>x_{r,c,1},...,x_{r,c,9}</math> מקבל את הערך 1. לכן האילוץ הוא <math>x_{r,c,1}+...+x_{r,c,9}=1</math>.
* לכל שורה <math>r</math>, ולכל שתי עמודות שונות <math>c_1,c_2</math>, לא ייתכן שאותה ספרה תתקבל בשתיהן (מאילוצי הסודוקו). לכן לכל ספרה <math>i</math> מוסיפים את האילוץ <math>x_{r,c_1,i}+x_{r,c_2,i}\le 1</math> (לא ייתכן ששני המשתנים מקבלים את הערך 1 בו זמנית). בדומה גם לכל עמודה <math>c</math> ולכל שתי שורות שונות <math>r_1, r_2</math> מוסיפים את האילוץ <math>x_{r_1,c,i}+x_{r_2,c,i}\le 1</math> ולכל שתי משבצות <math>(r_1,c_1),(r_2,c_2)</math> שנמצאות באותו ריבוע 3x3, גם כן נוסיף את האילוץ <math>x_{r_1,c_1,i}+x_{r_2,c_2,i}\le 1</math>.
:דוגמאות לאילוצים שכאלה: <math>x_{2,5,6}+x_{2,9,6}\le 1, x_{4,6,2}+x_{8,6,2}\le 1, x_{1,1,1}+x_{3,3,1}\le 1</math>
* הרמזים ההתחלתיים נותנים גם הם אילוצים. למשל, בסודוקו שמשמאל בשורה 1, עמודה 1 נמצאת הספרה 5. אם כן המשתנה <math>x_{1,1,5}</math> חייב לקבל את הערך 1, ואפשר להוסיף את האילוץ <math>x_{1,1,5}=1</math>. באופן כללי אם ברמזים נתון שבמשבצת שבשורה <math>r</math> ועמודה <math>c</math> יש את הערך <math>i</math>, אז אפשר להוסיף את האילוץ <math>x_{r,c,i}=1</math>.
* נוסף לכל אלה יש להוסיף את האילוץ <math>0\le x_{r,c,i} \le 1</math> לכל המשתנים.

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

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

== הצורה הדואלית ==
עבור הבעיה <math>Ax\le b,x \ge 0,\max c^Tx</math> קיימת הבעיה הדואלית <math> A^Ty\ge c,y \ge 0,\min b^Ty </math>כאשר <math>y</math> הוא וקטור m ממדי ו- <math>A^T</math> זוהי [[מטריצה משוחלפת|המטריצה המשוחלפת]] ל-<math>A</math>. למעבר זה יש חשיבות תאורטית בהוכחות שונות, ובפרט בהוכחת הנכונות של אלגרותמים שונים.

בנוסף, ניתן למצוא גם קשר רעיוני בין הבעיות. למשל, נחזור [[#הקצאת משאבים|לדוגמה הראשונה]]. המשוואות היו
:<math>e_1x_1+e_2x_2+e_3x_3\le e</math>
:<math>w_1x_1+w_2x_2+w_3x_3\le w</math>
:<math>x_1\ge 0,x_2\ge 0</math>
:<math>\max c_1x_1+c_2x_2+c_3x_3</math>
הבעיה הדואלית היא:
:<math>e_1y_1+w_1y_2\ge c_1</math>
:<math>e_2y_1+w_2y_2\ge c_2</math>
:<math>e_3y_1+w_3y_2\ge c_3</math>
:<math>\min ey_1+wy_2</math>
ניתן לחשוב על בעיה זאת כבעיה הבאה: <math>y_1</math> הוא משתנה שמייצג חשמל, ו-<math>y_2</math> משתנה שמייצג מים. אז כל משוואה מתייחסת למוצר אחר, ומבקשת, תחת תנאי חשמל ומים, שהרווח יהיה לפחות מספר מסוים. למשל המשוואה הראשונה מתייחסת למוצר מספר 1, בו המשוואה הראשונה דורשת שנשקיע מספיק חשמל ומים כדי לקבל את הרווח <math>c_1</math>. בדומה משוואות 2,3 מתייחסות למוצרים 2,3 בהתאמה. תחת תנאים אלה, יש למזער את העלות הכוללת של מים וחשמל.

הבעיה הדואלית [[#בעיית כיסוי הקודקודים|לדוגמה השנייה]] כוללת את המשתנים <math>x_e</math>, משתנה לכל קשת, כך שלכל קודקוד <math>v</math> יש את המשוואה <math>\sum_{v\in e} x_e\le 1</math> ויש למקסם את <math>\sum _{e \in E[G]} x_e</math>. כאשר המשתנים שלמים, הבעיה היא למצוא קבוצת קשתות מקסימלית כך שכל קודקוד נוגע בלכל היותר אחת מהן - בעיה הידועה כמציאת [[שידוך מקסימלי]] (לה יש פתרון פולינומי).

===משפטי הדואליות===
משפט הדואליות החלש קובע שאם הבעיה <math>\max c^Tx</math> היא בצורה קנונית, אז הבעיה הדואלית <math>\min b^Ty</math> מקיימת שלכל זוג פתרונות <math>x,y</math> מתקיים <math>b^Ty \ge c^Tx</math>, ובפרט גם לפתרונות האופטימליים.
.
משפט הדואליות החזק קובע שלפתרונות האופטימליים <math>b^Ty = c^Tx</math> (אם הם קיימים - או שאחת הבעיות לא חסומה, ואז השנייה לא פיזיבלית).

משפט הדואליות החלש מאפשר למצוא [[תנאי עצירה]] לאלגוריתמים שונים: אם מריצים את האלגוריתם על הבעיה ועל הבעיה הדואלית לה במקביל, מקבלים חסמים מכל בעיה על השנייה: לכל <math>y</math> שמוצאים, <math>b^Ty</math> מהווה חסם עליון ל-<math>c^Tx</math>, ולהפך.

ממשפט הדואליות החזק נובע [[משפט זרימה מקסימלית - חתך מינימלי]]{{הערה|[https://faculty.math.illinois.edu/~mlavrov/docs/482-fall-2019/lecture24.pdf The Max-Flow Min-Cut Theorem]}}, [[משפט קניג (תורת הגרפים)|משפט קניג]]{{הערה|[http://www.cs.toronto.edu/~anikolov/CSC473W18/Lectures/koenig.pdf K¨onig’s Theorem]}} ו[[משפט המינימקס]].{{הערה|[https://courses.cs.washington.edu/courses/cse521/16sp/521-lecture-16.pdf Duality and the Minimax theorem]}}

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

מתקיים <math>c^Tx=\sum_jc_jx_j</math>. כיוון ש-<math>x</math> הוא פתרון, אז לכל <math>i</math> מתקיים <math>\sum_ja_{ij}x_j\le b_i</math>. כמו כן, כיוון ש-<math>y</math> הוא פתרון, לכל <math>j</math> מתקיים <math>\sum_ia_{ij}y_j\ge c_j</math>. נשלב את כל זאת כדי לקבל:
:<math>c^Tx=\sum_j c_jx_j \le \sum_j(\sum_i a_{ij}y_i)x_j = \sum_{i,j}a_{ij}x_jy_i=\sum_i(\sum_j a_{ij}x_j)y_i \le \sum_i b_iy_i = b^T y</math>
כרצוי.

את משפט הדואליות החזק ניתן להוכיח בעזרת [[הלמה של פרקס]].{{הערה|[https://sma.epfl.ch/~niemeier/opt09/opt09_ch05.pdf Strong Duality]}}

==בעיות כיסוי ואריזה==
בעיה בצורה קנונית <math>Ax\le b,x \ge 0,\max c^Tx</math> נקראת "בעיית אריזה" אם כל ערכי המטריצות והווקטורים <math>A,b,c</math> הם בעלי ערכים אי שליליים. הסיבה לכינוי זה היא שאנחנו מנסים למקסם את מה שאנחנו מכניסים לערכים תוך מגבלה מלמעלה - כמו אדם שמנסה לארוז כמה שיותר לתוך נפח מוגבל.

בעיה בצורה הדואלית, <math> A^Ty\ge c,y \ge 0,\min b^Ty </math>, תקרא "בעיית כיסוי" אם היא מקיימת תכונה זו. הסיבה לכינוי זה היא שאנחנו מנסים למצוא ערכים קטנים ביותר שיעברו סף מסוים - מנסים לכסות את הערכים ב-<math>c</math>.

לבעיות אלה חשיבות מיוחדת, בפרט בשלמים, ואלגוריתמים רבים פותחו במיוחד בשבילן.{{הערה|[https://arxiv.org/pdf/1411.1124.pdf Nearly Linear-Time Packing and Covering LP Solvers]}}

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

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

==אלגוריתמים==
===שיטת הסימפלקס===
[[קובץ:Simplex-method-3-dimensions.png|ממוזער|הדגמה ויזואלית לשיטת הסימפלקס. הולכים לאורך צלעות הפאון מקודקוד לקודקוד, עד לפתרון אופטימלי.]]
האלגוריתם הוותיק ביותר הוא אלגוריתם הסימפלקס. למעשה הוא לא אלגוריתם במובן הרגיל אלא משפחה של אלגוריתמים, שכן אחד הצעדים בו לא מוגדר וניתן לממש אותו בדרכים שונות. האלגוריתם הומצא בשנת 1947 על ידי [[ג'ורג' דנציג]].{{הערה|[https://www.britannica.com/biography/George-Dantzig simplex method]}}

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

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

=== שיטת האליפסואיד ===
[[קובץ:Ellipsoid-method.png|ממוזער|איטרציה של שיטת האליפסואיד. עוברים מהאליפסה האדומה לאליפסה הירוקה, שמכילה גם היא את השטח הכחול.]]
השיטה נמצאה ב 1979 על ידי [[לאוניד חצ'יאן]], והיוותה פריצת דרך תאורטית גדולה בכך שהוכיחה זמן ריצה פולינומי, אך איננה מעשית לערכי n שאינם קטנים מאוד. בשיטה מתחילים מאליפסואיד [[גדול מספיק]] כדי להכיל את הנקודה המינימלית, ואז בסדרת צעדים מקטינים את האלפיסואיד כך שהוא עדיין כולל אותה, עד שהאליפסואיד קטן מספיק.{{הערה|[https://sma.epfl.ch/~eisenbra/OptInFinance/Slides/ellipsoid.pdf The ellipsoid method]}}

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

===האלגוריתם של קרמרקר===
אלגוריתם שנמצא על ידי המתמטיקאי ההודי [[נרמנדה קרמרקר]] בשנת 1984.{{הערה|שם=קרמרקר|[https://web.archive.org/web/20131228145520/http://retis.sssup.it/~bini/teaching/optim2010/karmarkar.pdf Narendra Karmarkar, A New Polynomial-Time Algorithm for Linear Programming]}} אף על פי שלא היה האלגוריתם הפולינומי הראשון, הוא היה האלגוריתם הפולינומי הראשון שרץ בזמן מעשי (אף על פי שבדרך כלל שיטת הסימפלקס עדיפה על קלטים אמיתיים).

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

===האלגוריתם הנוכחי===
נכון ל-2022, האלגוריתם הטוב ביותר הידוע רץ בסיבוכיות <math>O((n^\omega+n^{2.5-\alpha/2}+n^{2+1/6})L)</math>,{{הערה|[https://arxiv.org/pdf/1905.04447.pdf Solving Empirical Risk Minimization in the Current Matrix Multiplication Time]}} כאשר <math>\omega</math> הוא המעריך של ביצוע [[כפל מטריצות]], כלומר כזה שניתן עבורו להכפיל מטריצות בסיבוכיות <math>n^\omega</math> (נכון ל-2022, ידוע <math>\omega \le 2.38</math>), ו-<math>\alpha</math> הוא המעריך הדואלי של כפל מטריצות, כלומר המספר המקסימלי עבורו ניתן להכפיל מטריצות בגודלי <math>n \times n, n \times n^\alpha</math> בזמן <math>O(n^2)</math> (נכון ל-2022, ידוע <math>\alpha \ge 0.31</math>).

==אלגוריתמים למציאת פתרון בשלמים==
כאמור לעיל, הבעיה בשלמים היא NP קשה, לכן בהנחת <math>P\ne NP</math>, אין לה אלגוריתם פולינומי, אפילו אם לא מנסים למקסם פונקציית מטרה. לכן אלגוריתמים לפתרון תכנון ליניארי בשלמים עושים את אחד הדברים הבאים:
* רצים במקרה הגרוע בזמן אקספוננציאלי (במטרה שעל קלטים סבירים יסיימו בזמן סביר).
* מוצאים פתרון שלא מקיים את כל האילוצים (במטרה למצוא פתרון שיקיים כמה שיותר).
* רצים רק על קלטים שמקיימים הנחות כלשהן.
* דורשים הרצה פעם אחת של אלגוריתם בזמן אקספוננציאלי, שמאפשרת מציאת מידע איתו יהיה אפשר לפתור בעיות רבות בזמן פולינומי.
* רצים במקרים בהם ברור שיש פתרון (למשל, לבעיות אריזה תמיד קיים פתרון ה-0. לבעיות כיסוי תמיד יש פתרון בו כל המשתנים מקבלים את הערך המקסימלי של הווקטור <math>b</math>{{ביאור|נזכיר שבעיית כיסוי היא בצורה דואלית לקנונית, ופונקציית המטרה היא <math>\min b^Tx</math>}}) ומנסים לקרב את פונקציית המטרה.

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

בבעיות אריזה, אם מעגלים את כל הערכים למטה, מקבלים פתרון חוקי (כי כל הערכים נשארו אי שליליים, ואי-הגדלה של כל המשתנים לא יכולה לסתור אילוץ). הוא עשוי להיות קטן מהפתרון האופטימלי, אך אם פונקציית המטרה היא <math>\sum c_ix_i</math>, ניתן לדעת שעיגול כל הערכים למטה יקטין כל משתנה בלכל היותר 1, ולכן יקטין את פונקציית המטרה בלכל היותר <math>\sum c_i</math>. בדומה, עיגול למעלה של כל הערכים בבעיית כיסוי ימצא פתרון חוקי שפונקציית המטרה עליו עשויה להיות רחוקה ב-<math>\sum b_i</math> מהערך האופטימלי.

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

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

===בסיס גרייבר===
{{ערך מורחב|בסיס גרייבר}}
בהינתן מטריצה A בשלמים, בסיס גרייבר מאפשר לבצע עליה עיבוד מוקדם (שזמנו אקספוננציאלי) כדי לקבל מידע, בעזרתו יהיה אפשר לפתור את הבעיה <math>Ax= b, \max c^Tx</math> בזמן פולינומי לכל וקטורים שלמים <math>b,c</math>. השיטה מבוססת על מציאת [[קבוצה סופית]] של איברים <math>G(A)</math> (שנקראת בסיס גרייבר), שמהם ניתן לחלץ פתרונות באמצעות אלגוריתם [[איטרציה|איטרטיבי]].

===אלגוריתם לנסטרה===
אלגוריתם לנסטרה{{הערה| [https://pubsonline.informs.org/doi/abs/10.1287/moor.8.4.538 Integer Programming with a Fixed Number of Variables]}} מאפשר לפתור את הבעיה בזמן פולינומי כאשר מספר המשתנים קבוע. יותר בפירוט, אם ב-A יש <math>m</math> שורות והמקדמים שלה חסומים על ידי <math>N</math>, האלגוריתם מאפשר לפתור בזמן פולינומי ב-<math>O(m \log N)</math>. האלגוריתם עובר על המשתנים בזה אחר זה ומוצא [[קטע (מתמטיקה)|קטע]] לכל אחד מהם בו הוא חסום בעזרת [[גאומטריה של מספרים]], ולאחר מכן עובר על כל האפשרויות. האלגוריתם הומצא על ידי הנדריק לנסטרה בשנת 1983. זמן הריצה המקורי היה <math>(m \log N)^{O(1)}\cdot 2^{O(n^3)}</math>, ומאז שופר כמה פעמים.

===אלגוריתמים כלליים===
ניתן להשתמש באלגוריתמים כלליים, שאינם מיוחדים דווקא לתכנון ליניארי. נסקור כמה מהם בקצרה:
* '''[[backtracking]]''' (לבעיות אריזה): בהינתן משתנה <math>x_i</math>, והצבות לערכים <math>x_1,...,x_{i-1}</math>, נציב ב<math>x_i</math> את הערכים מ-0 ומעלה בזה אחר זה, ולכל אחד מהם נפתור רקורסיבית עבור המשתנה הבא. מפסיקים כאשר אחד האילוצים נשבר. אם <math>x_i=x_n</math> (ומצאנו הצבה שנותנת פתרון חוקי) זוכרים את ערך פונקציית המטרה, כדי להחזיר את הערך המינימלי. האלגוריתם מסתיים כאשר עוברים על כל הערכים עבור <math>x_1</math> (ואז הפתרון מדויק, אך הזמן עלול להיות אקספוננציאלי) או כאשר עובר זמן שהוגדר מראש (ואז הוא לאו דווקא ימצא את הפתרון האופטימלי).
* להתחיל עם פתרון כלשהו ולשפר אותו בעזרת אלגוריתמים כגון [[חיפוש מקומי]] או [[אופטימיזציית קן הנמלים]].
* שיטות שונות של [[למידת מכונה]], למשל [[רשת עצבית מלאכותית]].

==היסטוריה==
[[קובץ:Leonid Kantorovich 1975.jpg|ממוזער|לאוניד קנטורוביץ']]
העיסוק בבעיה התפתח באופן נפרד ב[[המערב|מערב]] וב[[ברית המועצות]].

הראשון שעסק בבעיה היה [[לאוניד קנטורוביץ']], שב 1939 ניסח את הבעיה הכללית וחקר דרכים לפתור אותה. הוא פרסם את מחקרו במאמר בשם "שיטות מתמטיות לארגון ותכנון של הייצור"{{הערה|[http://resistir.info/livros/kantorovich_mathematical_methods.pdf המאמר מתורגם לאנגלית]|כיוון=ימין}} בו הוא נתן דוגמאות שונות ושיטות לפתרון.{{הערה|mathematical methods of organizing and planning production, p. 390}} הוא טען שתכנון ליניארי נצרך רק בכלכלה [[קומוניזם|קומוניסטית]], כיוון שבכלכלה [[קפיטליזם|קפיטליסטית]] בעלי ההון ידאגו להקצאת משאבים.{{הערה|mathematical methods of organizing and planning production, p. 368}} במהלך [[מלחמת העולם השנייה]] הוא ניסה לרתום את מחקריו למאמץ המלחמתי, אך זכה להתעלמות ב[[ברית המועצות]].{{הערה|[https://apps.dtic.mil/sti/pdfs/ADA112060.pdf reminiscences about the origin of linear programming], p. 1}}
מעט אחר כך, [[צ'אלינג קופמאנס]] עסק ב[[ארצות הברית]] באופן בלתי תלוי בבעיה. ב-1975 חלקו קנטורוביץ' וקופמאנס [[פרס נובל לכלכלה]] על מחקרם בנושא.{{הערה|[https://www.nobelprize.org/prizes/economic-sciences/1975/summary/ נימוקי הזכייה באתר פרס נובל]|כיוון=ימין}}

ב-1946 חקר את הבעיה [[ג'ורג' דנציג]], במסגרת עבודתו ב[[חיל האוויר האמריקאי]] על בעיות לוגיסטיקה, כהכללה של שיטותיו של [[וסילי לאונטיף]] על מידול בעיות כלכליות באמצעות מטריצות.{{הערה|[https://apps.dtic.mil/sti/pdfs/ADA112060.pdf reminiscences about the origin of linear programming], p. 2}} הוא עבד על הבעיה עם קומפאנס, וב-1947 פיתח את שיטת הסימפלקס.{{הערה|reminiscences about the origin of linear programming, p. 4}}
כמו כן, בשנת 1948 הציג דנציג את מחקרו בפני [[ג'ון פון נוימן]]. בתגובה, פון נוימן הציג לו את מחקרו על [[תורת המשחקים]] ואת הקשר שזיהה בין מחקר זה לבין הדואליות של תכנון ליניארי, ושיער את משפט הדואליות החזק. דנציג הוכיח את המשפט אך פרסם בתפוצה פנימית בלבד. הראשונים שפרסמו הוכחה פורמלית ברבים היו תלמידיו של פון נוימן - אלן טאקר, דייוויד גייל והרולד קון.{{הערה|reminiscences about the origin of linear programming, p. 6}}

במשך שנים לא היה ידוע האם יש לבעיה גם פתרון פולינומי. בעיה זאת נפתרה ב-1979 כאשר ליאוניד חצ'יאן מצא את [[שיטת האליפסואיד]]. התגלית היוותה סנסציה, וכונתה במערב "הספוטניק של 1979".{{הערה| Eugene L. Lawler, The Great Mathematical Sputnik of 1979}} על אף פריצת הדרך התאורטית, האלגוריתם לא מעשי. עם זאת, בשנת 1984 מצא נרמנדה קרמרקר אלגוריתם פולינומי ומעשי שמכונה "שיטת נקודות הפנים".{{הערה|שם=קרמרקר}} הבעיה המשיכה להיות מוקד של מחקר פעיל, ובמהלך השנים הבאות זמן הריצה שופר שוב ושוב, למשל בשנת 1987 ובשנת 1989 על ידי פרווין פאידה.{{הערה| [http://theory.stanford.edu/~virgi/cs367/papers/vaidya.pdf Speeding-up linear programming using fast matrix multiplication, Pravin M. Vaidya]}}

גם תכנון ליניארי בשלמים נחקר כבר על ידי דנציג, שנתן כדוגמה בעיית השמה של 70 משימות ל70 אנשים, תוך אילוצים שונים, בעיה שאיננה ניתנת לפתרון באמצעות [[כוח גס]] (בוודאי לא באמצעים של אז, וגם לא כיום), מאחר שלשם כך דרוש לבדוק 70 [[עצרת (מתמטיקה)|עצרת]] אפשרויות.{{הערה|[https://apps.dtic.mil/sti/pdfs/ADA112060.pdf REMINISCENCES ABOUT THE ORIGINS OF LINEAR PROGRAMMING], p. 2}} לאחר הוכחת [[משפט קוק לוין]], התברר שישנן בעיות NP שלמות ושתכנון ליניארי היא בעיה כזאת, וב-1972 כלל אותה קארפ במאמרו בו הציג בעיות NP שלמות.{{הערה|שם=קארפ}} מאז נעשה מחקר רב בנושא, אך פתרון פולינומי לא נמצא.

==LP Solvers==
מפאת חשיבותה המעשית של בעיית התכנון הליניארי, פותחו כלים רבים המאפשרים פתרון של הבעיה, עבור [[שפת תכנות|שפות]] שונות, גם באקדמיות, גם באופן מסחרי וגם באופן וולנטרי. תוכנה שמאפשרת פתרון מעשי של בעיות תכנות ליניארי נקראת LP solver. דוגמה ל-LP solver היא cvxpy, אשר נכתב עבור שפת [[פייתון]] ב[[קוד פתוח]].{{הערה|[https://www.cvxpy.org/ אתר הבית של cvxpy]|כיוון=ימין}} נראה כדוגמה תוכנה שתפתור את הבעיה שניתנה בתחילת הערך:
<syntaxhighlight lang="python">
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})
</syntaxhighlight>
הרצת התוכנית מדפיסה את הפלט x1=3, x2=2, x3=4.

==ראו גם==
*[[תכנון דינמי]]
*[[תכנון לא-ליניארי]]
*[[אופטימיזציה קמורה]]

==לקריאה נוספת==
{{ltr|1=
* Jiˇrí Matoušek, Bernd Gärtner, [https://blogs.epfl.ch/extrema/documents/Maison%2020.05.10.pdf Understanding and Using Linear Programming]
* Stephen Boyd, Lieven Vandenberghe, [https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf Convex Optimization]

}}

==קישורים חיצוניים==
{{ויקישיתוף בשורה}}
* {{MathWorld}}
* {{בריטניקה}}
* {{דף שער בספרייה הלאומית|987007555765405171|אופטימיזציה מתמטית}}

==ביאורים==
{{ביאורים}}

==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}

{{ערך מומלץ}}
{{בקרת זהויות}}

[[קטגוריה:אופטימיזציה רציפה]]
[[קטגוריה:חקר ביצועים]]
[[קטגוריה:בעיות NP-שלמות]]