שיעור תאוריה
פתרון גרפי ורגישות בתכנון ליניארי בשני משתנים
איך מזהים שהנושא מתאים
- יש בדיוק שני משתני החלטה, ולכן אפשר לצייר את המודל על מערכת צירים.
- פונקציית המטרה והאילוצים ליניאריים: כל ביטוי הוא סכום של מקדמים כפול משתנים.
- מבקשים למקסם או למזער ערך, למשל רווח, עלות, זמן או כמות.
- מופיעים אילוצי משאבים כמו שעות עבודה, קיבולת, חומר גלם או תקציב.
- מבקשים גם ערכים דואליים, שינוי אגף ימין או טווחים למקדמי פונקציית המטרה.
אינטואיציה
בבעיה ליניארית עם שני משתנים כל אילוץ יוצר חצי-מישור: צד אחד של קו מותר, והצד השני אסור. החיתוך של כל החצאים המותרים הוא התחום האפשרי.
פונקציית המטרה היא גם קו. כשמגדילים את ערך המטרה, הקו זז במקביל לעצמו. בבעיית מקסימום, מזיזים אותו עד הנקודה האחרונה שבה הוא עדיין נוגע בתחום האפשרי. בדרך כלל נקודה זו היא קודקוד של התחום האפשרי.
הגדרות פורמליות
| מושג | משמעות |
|---|---|
| משתנה החלטה | גודל שהמודל בוחר, למשל כמה יחידות לייצר מכל מוצר. |
| פונקציית מטרה | הביטוי שאותו ממקסמים או ממזערים. |
| אילוץ | תנאי שמגביל את הפתרונות האפשריים. |
| תחום אפשרי | כל הנקודות שמקיימות את כל האילוצים, כולל אי-שליליות. |
| אילוץ פעיל (הדוק) | אילוץ שמתקיים בשוויון בנקודה הנבדקת. לאחר ההגדרה נשתמש בקיצור "אילוץ פעיל". |
| מרווח | כמות המשאב שלא נוצלה באילוץ מסוג ≤: אגף ימין פחות אגף שמאל. מרווח חיובי פירושו שהאילוץ אינו פעיל. |
| ערך דואלי | השינוי בערך המטרה האופטימלי לכל שינוי של יחידה אחת באגף ימין, כל עוד נשארים בתוך תחום ההתקפות. |
| תחום התקפות | הטווח שבו מבנה האילוצים הפעילים נשאר מתאים למסקנת הרגישות שבה משתמשים. |
מודל הוא ליניארי כאשר כל משתנה מופיע בחזקה ראשונה בלבד, אין מכפלות בין משתנים, וכל המקדמים קבועים. צורה כללית של בעיית מקסימום ליניארית בשני משתנים היא:
max Z = c₁x₁ + c₂x₂כאשר מתקיימים האילוצים:
a₁₁x₁ + a₁₂x₂ ≤ b₁, a₂₁x₁ + a₂₂x₂ ≤ b₂, x₁ ≥ 0, x₂ ≥ 0פירוש הסימנים במודל הכללי:
| סימון | משמעות |
|---|---|
| x₁, x₂ | משתני ההחלטה: הכמויות שהמודל צריך לבחור. |
| Z | ערך פונקציית המטרה, למשל הרווח הכולל או העלות הכוללת. |
| c₁, c₂ | תרומת יחידה אחת מכל משתנה לפונקציית המטרה. |
| a₁₁, a₁₂, a₂₁, a₂₂ | כמות המשאב שכל יחידה של משתנה צורכת בכל אילוץ. |
| b₁, b₂ | אגף ימין של האילוץ: כמות המשאב הזמינה או הגבול שמותר להשתמש בו. |
| x₁ ≥ 0, x₂ ≥ 0 | אילוצי אי-שליליות: לא מייצרים או בוחרים כמות שלילית. |
לפני כתיבת המודל ממירים את כל הנתונים ליחידות עקביות. אם השאלה אינה דורשת אילוצי שלמות, x₁ ו-x₂ הם משתנים רציפים ולכן פתרון שברי מותר מבחינה מתמטית.
שיטת פתרון
- בודקים שכל הביטויים ליניאריים ומגדירים את משתני ההחלטה, היחידות וסוג המשתנים.
- ממירים את הנתונים ליחידות עקביות.
- בונים פונקציית מטרה ומציינים במפורש אם ממקסמים או ממזערים.
- כותבים אילוץ לכל משאב או מגבלה, ומוסיפים אי-שליליות ואילוצי שלמות אם נדרשו.
- לצורך ציור, מחליפים כל אי-שוויון בשוויון ומוצאים חיתוכים עם הצירים.
- בודקים איזה צד של כל קו מקיים את האילוץ ובונים את התחום האפשרי.
- מוצאים את כל הקודקודים האפשריים בלבד. חיתוך שאינו מקיים את כל האילוצים אינו מועמד.
- מציבים כל קודקוד אפשרי בפונקציית המטרה ובוחרים את הערך הטוב ביותר.
- מוודאים גאומטרית: מזיזים את קו המטרה במקביל לעצמו בכיוון השיפור עד המגע האפשרי האחרון.
תוצאות אפשריות של הפתרון הגרפי
- פתרון אופטימלי יחיד: קו המטרה נוגע בתחום האפשרי בקודקוד אחד.
- ריבוי פתרונות אופטימליים: קו המטרה מקביל לצלע אופטימלית וחופף לה; כל נקודה על הקטע אופטימלית.
- בעיה ללא פתרון אפשרי: אין נקודה שמקיימת את כל האילוצים יחד.
- בעיה לא חסומה: אפשר לשפר את ערך המטרה ללא גבול בכיוון האופטימיזציה.
ערכים דואליים ושינוי אגף ימין
אם לאילוץ משאב מסוג ≤ יש מרווח חיובי בפתרון האופטימלי, הוא אינו פעיל והערך הדואלי שלו הוא אפס. אילוץ פעיל עשוי להשפיע על הרווח כאשר משנים את אגף ימין שלו.
נסמן ב-DVi את הערך הדואלי של אילוץ i, ב-ΔZ* את השינוי בערך המטרה האופטימלי, וב-Δbi את השינוי באגף ימין של אותו אילוץ:
DVi = ΔZ* / Δbiהיחס אומר כמה יחידות ערך מטרה מתקבלות עבור יחידת משאב אחת. מותר להשתמש בו רק כאשר השינוי נמצא בתחום ההתקפות שבו אותו מבנה של אילוצים פעילים נשמר.
טווח מקדמי פונקציית המטרה
כדי שהקודקוד האופטימלי יישאר אותו קודקוד, שיפוע קו המטרה צריך להישאר בין שיפועי שני האילוצים הפעילים באותו קודקוד.
mZ = -c₁ / c₂כאן mZ הוא שיפוע קו פונקציית המטרה, c₁ הוא המקדם של x₁, ו-c₂ הוא המקדם של x₂. אם האילוצים הפעילים בעלי שיפועים m₁ ו-m₂, בודקים עבור אילו ערכי c₁ או c₂ השיפוע -c₁/c₂ נשאר ביניהם. בכל פעם משנים מקדם אחד ומשאירים את האחר קבוע.
הערות מוכנות למבחן
- במודל ייצור, אילוצי המשאבים כמעט תמיד נכתבים כ-≤, כי אסור להשתמש ביותר מהקיבולת הזמינה.
- לפני ניסוח אילוץ, מוודאים שכל המקדמים ואגף ימין כתובים באותן יחידות.
- נקודה אופטימלית בגרף צריכה להיות גם אפשרית וגם בעלת ערך מטרה מיטבי ביחס לכל שאר הקודקודים.
- טבלת קודקודים והזזה מקבילה של קו המטרה הן שתי דרכים לתאר אותה אופטימיזציה; הטבלה מספקת את האימות המספרי.
- ערך דואלי הוא ערך ליחידת משאב, ולכן חשוב לשמור על יחידות: למשל שקלים לשעת תהליך.
- כאשר משנים אגף ימין, משתמשים בערך הדואלי רק בתוך תחום ההתקפות שבו אותם אילוצים פעילים נשארים רלוונטיים.
- כאשר משנים מקדם בפונקציית המטרה, קודם בודקים אם המקדם החדש נמצא בתחום ההתקפות; רק אחר כך מחשבים את ערך המטרה החדש.