תבנית:ערך מומלץ 24 בספטמבר 2023

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

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

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

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

לערך המלא – מומלצים נוספים