תכנון לא-ליניארי

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

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

ניסוח מתמטי של הבעיה[עריכת קוד מקור | עריכה]

כאשר:

בעיית תכנון לא-ליניארי מבקשת למצוא את הערך (או הערכים)

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

לחלופין, תחת אותם תנאים, בעיית תכנון לא-ליניארי יכולה לבקש למצוא את

כלומר, להביא את פונקציית המטרה למינימום.

שתי הבעיות שקולות, שכן

שיטות לפתרון[עריכת קוד מקור | עריכה]

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

בעיות שאינן נופלות באחת מהקטגוריות הקודמות מצריכות אופטימיזציה לא-קמורה שנחשבת לקטגוריה מורכבת. קבוצת שיטות נפוצות הן מסוג סעף וחסום (branch and bound) המחלקות את הבעיה לתתי-מחלקות ופותרת קירוב של כל תת-מחלקה כזו באמצעות אופטימיזציה קמורה. בכל שלב החסם העליון על הפתרון והחסם התחתון מתקרבים עד שמגיעים לדיוק הרצוי.

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

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

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]