תכנות לא לינארית: שיטות ותרגילים - מתמטיקה - 2025

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

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

איור 1. איור 1. בעיית תכנות לא לינארית (NLP). כאשר G היא הפונקציה (הלא ליניארית) למיטוב באזור הירוק, הנקבעת על ידי האילוצים. מקור: פ. זפטה.

ולכן לא ניתן להשתמש בהליכים והשיטות של תכנות לינארית.

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

שיטות תכנות לינאריות

לבעיות תכנות לא לינאריות, השיטות העיקריות בהן נעשה שימוש הן:

1.- שיטות גרפיות.

2.- מכפילי לגראנז 'כדי לחקור את גבול אזור הפתרונות.

3.- חישוב שיפוע לבחינת הקצוות של הפונקציה האובייקטיבית.

4.- שיטת הירידה בצעדים, כדי למצוא את נקודות שיפוע האפס.

5.- שיטה שונה של מכפילי לגראנז '(עם תנאי קרוש-קון-טאקר).

דוגמא לפיתרון בשיטה גרפית

דוגמה לפיתרון בשיטה הגרפית היא זו שניתן לראות באיור 2:

איור 2. דוגמה לבעיה לא ליניארית עם מגבלות לא ליניאריות והפתרון הגרפי שלה. מקור: פ. זפטה.

תרגילים

- תרגיל 1 (שיטה גרפית)

הרווח G של חברה מסוימת תלוי בכמות שנמכרה של מוצר X ובכמות שנמכרה של מוצר Y, בנוסף, הרווח נקבע על ידי הנוסחה הבאה:

G = 2 (X - 2) ² + 3 (Y - 3) ²

לכמויות X ו- Y ישנן ההגבלות הבאות:

X≥0; Y≥0 ו- X + Y ≤ 7

קבע את הערכים של X ו- Y שמייצרים את הרווח המרבי.

איור 3. איור 3. ניתן לעצב את הרווח של חברה על מנת למצוא את הרווח המרבי באמצעות תכנות לא לינארית. מקור: Pixabay.

פִּתָרוֹן

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

לפיתרון הבעיה תבחר השיטה הגרפית.

ראשית, אזור הפתרונות ייקבע, אשר ניתן על ידי המגבלות.

כ- X≥0; Y≥0, יש למצוא את הפיתרון ברבע הראשון של מישור XY, אך מכיוון שהוא חייב להיות נכון גם ש- X + Y ≤ 7, הפיתרון נמצא בחלקו התחתון של הקו X + Y = 7.

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

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

האליפסה מוצגת באיור 1 לערכים שונים של G. ככל שהערך של G גבוה יותר, כך הרווח גדול יותר.

ישנם פתרונות השייכים לאזור, אך אינם נותנים את ערך ה- G המרבי, בעוד שאחרים, כמו G = 92.4, נמצאים מחוץ לאזור הירוק, כלומר אזור הפתרונות.

לאחר מכן, הערך המקסימאלי של G, כך ש- X ו- Y שייכים לאזור הפתרונות, מתאים:

G = 77 (רווח מרבי), הניתן ל- X = 7 ו- Y = 0.

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

- תרגיל 2 (שיטה אנליטית: מכפילי לגראנז ')

מצא את הפיתרון (x, y) שהופך את הפונקציה f (x, y) = x ² + 2y ² לכל היותר באזור g (x, y) = x ² + y ² - 1 = 0.

פִּתָרוֹן

ברור שמדובר בבעיית תכנות לא לינארית, שכן גם הפונקציה האובייקטיבית f (x, y) וגם ההגבלה g (x, y) = 0, אינם שילוב לינארי של המשתנים x ו- y.

תשתמש בשיטת מכפילי Lagrange, המחייבת תחילה להגדיר את פונקציית Lagrange L (x, y, λ):

L (x, y, λ) = f (x, y) - λ g (x, y) = x ² + 2y ² - λ (x ² + y ² - 1)

כאשר λ הוא פרמטר המכונה מכפיל Lagrange.

כדי לקבוע את הערכים הקיצוניים של הפונקציה האובייקטיבית f, באזור הפתרונות הניתן על ידי המגבלה g (x, y) = 0, בצע את הצעדים הבאים:

מצא את הנגזרות החלקיות של פונקציית Lagrange L, ביחס ל- x, y, λ.

-הערוך כל נגזרת לאפס.

להלן רצף פעולות אלה:

1. ∂L / ∂x = 2x - 2λx = 0
2. ∂L / ∂y = 4y - 2λy = 0
3. ∂L / ∂λ = - (x ² + y ² - 1) = 0

פתרונות מערכת אפשריים

פיתרון אפשרי של מערכת זו הוא λ = 1 כך שהמשוואה הראשונה מסופקת, ובמקרה זה y = 0 כך שהשנייה תהיה מרוצה.

פיתרון זה מרמז על כך ש- x = 1 או x = -1 כדי שהמשוואה השלישית תהיה מסופקת. בדרך זו הושגו שני פתרונות S1 ו- S2:

S1: (x = 1, y = 0)

S2: (x = -1, y = 0).

האלטרנטיבה האחרת היא ש- = 2 כך שהמשוואה השנייה מסופקת, ללא קשר לערך y.

במקרה זה, הדרך היחידה להסתפק במשוואה הראשונה היא עבור x = 0. בהתחשב במשוואה השלישית, ישנם רק שני פתרונות אפשריים, אשר נקרא S3 ו- S4:

S3: (x = 0, y = 1)

S4: (x = 0, y = -1)

כדי לגלות אילו או מהפתרונות הללו ממקסמים את הפונקציה האובייקטיבית, אנו ממשיכים להחליף ב- f (x, y):

S1: f (1, 0) = 1 ² + 2.0 ² = 1

S2: f (-1, 0) = (-1) ² + 2.0 ² = 1

S3: f (0, 1) = 0 ² + 2.1 ² = 2

S4: f (0, -1) = 0 ² + 2 (-1) ² = 2

אנו מסיקים כי הפתרונות שממקסמים f, כאשר x ו- y שייכים להיקף g (x, y) = 0 הם S3 ו- S4.

זוגות הערכים (x = 0, y = 1) ו- (x = 0, y = -1) ממקסמים את f (x, y) באזור הפיתרון g (x, y) = 0.

- תרגיל 3 (שיפוע אפסי)

מצא פתרונות (x, y) לפונקציה האובייקטיבית:

f (x, y) = x ² + 2 y ²

לאפשר להיות מקסימאלי באזור g (x, y) = x ² + y ² - 1 ≤ 0.

פִּתָרוֹן

תרגיל זה דומה לתרגיל 2, אך אזור הפיתרון (או ההגבלה) משתרע לאזור הפנימי של ההיקף g (x, y) = 0, כלומר למעגל g (x, y) ≤ 0. זה כולל להיקף ולאזור הפנימי שלו.

הפיתרון בגבול כבר נקבע בתרגיל 2, אך עדיין נותר לבחון את האזור הפנימי.

לשם כך, יש לחשב את שיפוע הפונקציה f (x, y) ולהגדיר אותו שווה לאפס, כדי למצוא ערכים קיצוניים באזור הפיתרון. זה שווה לחישוב הנגזרות החלקיות של f ביחס ל- x ו- y בהתאמה ולהגדרתו שווה לאפס:

∂f / ∂x = 2 x = 0

∂f / ∂y = 4 y = 0

למערכת המשוואות הזו יש הפיתרון היחיד (x = 0, y = 0) השייך למעגל g (x, y) ≤ 0.

החלפת ערך זה בפונקציה f תוצאות:

f (0, 0) = 0

לסיכום, הערך המרבי שהפונקציה נוקטת באזור הפיתרון הוא 2 ומתרחש בגבול אזור הפיתרון, לערכים (x = 0, y = 1) ו- (x = 0, y = -1) .

הפניות

1. אבריאל, מ. 2003. תכנות לא לינאריות. הוצאת דובר.
2. בזארא. 1979. תכנות לא לינאריות. ג'ון וויילי ובניו.
3. Bertsekas, D. 1999. תכנות לא לינאריות: מהדורה שנייה. אתנה סיינטיפיק.
4. Nocedal, J. 1999. אופטימיזציה נומרית. שפרינגר-ורלאג.
5. ויקיפדיה. תכנות לא לינארית. התאושש מ: es.wikipedia.com