תכנון לינארי – פונקציית מטרה ואופטימיזציה

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

מושגי יסוד בתכנון לינארי

תכנון לינארי הוא דרך לקבל החלטה כשיש מטרה כמותית ומגבלות. בבעיה יש:

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

בניית פונקציית מטרה ליניארית בשני משתנים

פונקציית מטרה ליניארית בשני משתנים היא מהצורה $f(x,y)=ax+by$, שבה $a$ ו-$b$ קבועים. המקדם $a$ מראה כמה תורמת כל יחידה של $x$ לערך הכולל, והמקדם $b$ מראה את התרומה של כל יחידה של $y$.

לדוגמה, אם מפעל מרוויח 50 ש"ח על כל יחידה ממוצר א ו-40 ש"ח על כל יחידה ממוצר ב, פונקציית המטרה לרווח היא $f(x,y)=50x+40y$. אם רוצים למזער עלות שבה כל ק"ג של מוצר א עולה 3 ש"ח וכל ק"ג של מוצר ב עולה 5 ש"ח, פונקציית המטרה היא $f(x,y)=3x+5y$.

בעת בניית הפונקציה יש להקפיד:

• להגדיר תחילה מה מייצגים $x$ ו-$y$, כולל יחידות מידה.
• לבדוק אם המטרה היא מקסימום או מינימום: רווח והכנסה בדרך כלל ממוקסמים; עלות, זמן או שימוש במשאב בדרך כלל ממוזערים.
• לוודא שהמקדמים לקוחים מהנתונים ולא מומצאים.

ערך הפונקציה בנקודה מסוימת מתקבל בהצבת שיעורי הנקודה. אם בנקודה $(10,20)$ מתקבל $f(10,20)=50 \cdot 10+40 \cdot 20=1300$, המשמעות היא שהבחירה הזו נותנת ערך של 1300 יחידות, למשל ש"ח או דקות, לפי הקשר השאלה.

תחום אפשרי לפעולתה של פונקציית המטרה

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

אילוצים נפוצים:

• הגבלת משאב: $2x+3y \le 120$, למשל סך שעות עבודה.
• דרישה מינימלית: $x+y \ge 80$, למשל סך יחידות שחובה לייצר.
• יחס בין כמויות: $y \le 2x$ או $x \ge y$.
• אי-שליליות: $x \ge 0$, $y \ge 0$, כאשר כמויות אינן יכולות להיות שליליות.

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

סימון התחום האפשרי במערכת צירים

כדי לתאר את התחום בגרף, עובדים לפי סדר:

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

אם אילוץ כולל שוויון, למשל $x+y=100$, התחום מוגבל לישר עצמו בלבד. אם האילוץ הוא אי-שוויון, התחום כולל את הישר ואת אחד מצדדיו, בהתאם לסימן.

מציאת ערך מקסימלי או מינימלי של פונקציית המטרה

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

יש שתי דרכים עיקריות למצוא את הערך המיטבי:

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

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

חישוב קודקודים בטכניקה אלגברית פשוטה

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

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

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

אם הקודקוד הוא חיתוך של ישר עם ציר, מציבים $x=0$ או $y=0$ במשוואת הישר. כך מתקבלים קודקודים שעל הצירים, למשל נקודות שבהן מייצרים רק מוצר אחד או לא מייצרים מוצר מסוים.

בחירת נקודות שלמות כאשר הכמויות חייבות להיות שלמות

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

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

לדוגמה, אם מוצרים אי אפשר לייצר בחצאי יחידות, נקודה כמו $(12.5,20)$ אינה אפשרית, גם אם היא נמצאת על גבול התחום. במקרה כזה בודקים נקודות שלמות סמוכות שמקיימות את כל האילוצים, כגון $(12,20)$ או $(13,19)$, אם הן שייכות לתחום, ומשווים את ערכי פונקציית המטרה.

קבלת החלטה מיטבית על פי הפתרון הגרפי והאלגברי

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

בעת קבלת ההחלטה יש להציג:

• את ערכי $x$ ו-$y$ שנבחרו.
• את הערך של פונקציית המטרה בנקודה זו.
• את המשמעות של הערך לפי יחידות המידה: ש"ח, דקות, ק"ג, מספר נקודות וכדומה.
• התייחסות לאילוצים: הנקודה שנבחרה חייבת להיות בתחום האפשרי, אחרת היא מתארת החלטה שאינה ניתנת לביצוע.

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

הקשר בין גרף האילוצים לבין הסיטואציה הכלכלית

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

כאשר נתונה סיטואציה מילולית, יש לזהות איזה אילוץ מתאים לכל משפט. משפט כמו "סך הייצור אינו עולה על 50 יחידות" מתורגם ל-$x+y \le 50$. משפט כמו "יש לייצר לפחות 20 יחידות ממוצר א" מתורגם ל-$x \ge 20$. משפט כמו "כמות מוצר ב אינה עולה על כפליים מכמות מוצר א" מתורגם ל-$y \le 2x$. התאמה נכונה בין המשפט לבין אי-השוויון היא תנאי לפתרון נכון.

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