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

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

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

==ניסוח מתמטי של הבעיה==
כאשר:
:<math>f: \mathbb{R}^n \to \mathbb{R}</math>
:<math>X \subseteq \mathbb{R}^n</math>
בעיית תכנון לא-ליניארי מבקשת למצוא את הערך (או הערכים)
:<math>\underset{x \in X}{\text{argmax}}\ f(x)</math>
במילים אחרות, מבקשים להביא את פונקציית המטרה למקסימום, תוך קביעת <math>n</math> משתנים.

לחלופין, תחת אותם תנאים, בעיית תכנון לא-ליניארי יכולה לבקש למצוא את
:<math>\underset{x \in X}{\text{argmin}}\ f(x)</math>
כלומר, להביא את פונקציית המטרה למינימום.

שתי הבעיות [[שקילות (לוגיקה)|שקולות]], שכן
:<math>\min_{x \in X}f(x) = -\max_{x \in X}\left(-f(x)\right)</math>

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

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

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

גישה אחרת לפתרון סופגת את האילוצים המוגדרים בבעיה לתוך פונקציית המטרה באמצעות "קנס" על חריגה מהם. גישה זו נקראת גישת קנס (Penalty Method), והיא מאפשר רדוקציה לבעיה בכל המרחב ה-n-ממדי <math>\mathbb{R}^n</math>, בלי מגבלות נוספות.

==ראו גם==
* [[תכנון ליניארי]]

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

{{בקרת זהויות}}

[[קטגוריה:ערכים שבהם תבנית בריטניקה אינה מתאימה]]
[[קטגוריה:אופטימיזציה רציפה]]