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

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

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

ניסוח מתמטי של הבעיה

בעיית תכנון לא-ליניארי היא פשוט:

$\max _{x\in X}f(x)$

כדי להביא את פונקציית המטרה למקסימום תוך קביעת n משתנים או לחלופין:

$\min _{x\in X}f(x)$

כדי להביא את המטרה למינימום, כאשר:

$f:R^{n}\to R$

$X\subseteq R^{n}$

שיטות לפתרון

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

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

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

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

ראו גם

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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