כופלי לגראנז'

שיטה מתמטית לפתרון בעיות אופטימיזציה עם אילוצים

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

העקום האדום מתאר את האילוץ g(x, y)=c. העקומים הכחולים הם קווים שווי ערך (קווי גובה) של (f(x, y. הנקודה שבה האילוץ האדום משיק לעקום הכחול היא נקודת מקסימום של (f(x, y לאורך עקומת האילוץ, מכיוון ש-d1 > d2.

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

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

נכונות השיטה עריכה

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

תיאור השיטה עריכה

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

השיטה היא להגדיר פונקציה חדשה:  

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

ההסיאן עריכה

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

דוגמאות עריכה

  • אנו רוצים למצוא את נקודות הקיצון של הפונקציה   בכפוף לאילוץ שהנקודות הן על המעגל  . נגדיר:
 

המשוואות שנקבל תהיינה:

 
 

 

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

ראו גם עריכה

קישורים חיצוניים עריכה

  מדיה וקבצים בנושא כופלי לגראנז' בוויקישיתוף