עמוד ראשי

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

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

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

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

• 1964 – ועדת וורן לחקירת רצח קנדי מפרסמת את מסקנותיה
• 1991 – האלבום "Nevermind" של להקת הגראנג' נירוונה יוצא לאור
• 1991 – נפטר הסופר והמאייר דוקטור סוס, יוצרו של חתול תעלול (בתמונה‏: אנדרטה לזכרו)
• 1996 – מהומות פורצות בעקבות פתיחת מנהרות הכותל למבקרים

24 בספטמבר – חודש ספטמבר – היום בהיסטוריה