מתמטיקה תכנותית לינארית

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

אופטימיזציה: תכנות לינארית

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

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

בכפוף למגבלת אילוצים המתבטאים כחוסר שוויון:

ה- a's, b's ו- c הם קבועים הנקבעים על ידי היכולות, הצרכים, העלויות, הרווחים ודרישות ומגבלות אחרות של הבעיה. הנחת היסוד ביישום שיטה זו היא שהקשרים השונים בין ביקוש לזמינות הם לינאריים; כלומר, אף אחד מ- x _i לא מוגדל לכוח שאינו 1. כדי להשיג את הפיתרון לבעיה זו, יש צורך למצוא את הפיתרון של מערכת אי השוויון הקווי (כלומר, מערך ה- n של המשתנים x _i המספקים בו זמנית את כל אי השוויון). לאחר מכן מעריכים את הפונקציה האובייקטיבית על ידי החלפת ערכי ה- x _i במשוואה המגדירה f.

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

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