בחינה 1, חלק 2 · שיעור פתרון

שאלה 1: תמהיל ייצור של שני מוצרים

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

נוסח השאלה

מפעל מייצר שני מוצרים, A ו-B. כל מוצר עובר שלושה תהליכים. המפעל מעוניין בתמהיל הייצור השבועי שימקסם את הרווח הכולל, ללא אילוצי שלמות.

מוצר תהליך 1 תהליך 2 תהליך 3 רווח ליחידה
A 6 שעות 4 שעות 8 שעות 1,800 ₪
B 10 שעות 12 שעות 8 שעות 2,400 ₪

קיבולת שבועית: תהליך 1 עד 72 שעות, תהליך 2 עד 68 שעות, ותהליך 3 עד 68 שעות.

  1. א. נסחו את הבעיה כבעיית תכנון ליניארי: הגדירו את משתני ההחלטה, נסחו את פונקציית המטרה ואת האילוצים המתאימים.
  2. ב. פתרו את הבעיה באופן גרפי והראו את החישובים המתאימים.
  3. ג. חשבו את הערך הדואלי של כל אחד מהאילוצים.
  4. ד. בהשקעה שבועית של 145 ₪ ניתן להוסיף 5 שעות הפעלה לתהליך השני. האם ההשקעה כדאית? אם לא, הסבירו; אם כן, חשבו את הנקודה האופטימלית החדשה ואת השינוי ברווח השבועי.
  5. ה. בבעיה המקורית, חשבו את החסמים על כל אחד ממקדמי פונקציית המטרה.
  6. ו. בבעיה המקורית, הרווח ליחידת מוצר B ירד ל-2,000 ₪. האם הדבר ישפיע על הפתרון האופטימלי ועל ערך פונקציית המטרה שמצאתם בסעיף ב'? הסבירו כיצד.

זיהוי השיטה

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

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

פתרון מודרך

א ניסוח המודל

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

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

x₁
מספר יחידות מוצר A שמייצרים בשבוע.
x₂
מספר יחידות מוצר B שמייצרים בשבוע.
Z
הרווח השבועי הכולל, בשקלים.
max  Z = 1800x₁ + 2400x₂ 6x₁ + 10x₂ ≤ 72 4x₁ + 12x₂ ≤ 68 8x₁ + 8x₂ ≤ 68 x₁ ≥ 0,   x₂ ≥ 0

תוצאת הסעיף: התקבל מודל שממקסם רווח תחת שלוש מגבלות שעות ואילוצי אי-שליליות.

ב פתרון גרפי

נוסח הסעיף: פתרו את הבעיה באופן גרפי והראו את החישובים המתאימים.

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

כדי לצייר אילוץ, הופכים את אי-השוויון לשוויון ומוצאים את חיתוכי הקו עם הצירים:

אילוץ משוואת הקו חיתוך עם ציר x₁ חיתוך עם ציר x₂
1 6x₁ + 10x₂ = 72 (12, 0) (0, 7.2)
2 4x₁ + 12x₂ = 68 (17, 0) (0, 17/3) ≈ (0, 5.67)
3 8x₁ + 8x₂ = 68 (8.5, 0) (0, 8.5)
גרף מחושב של שלושת האילוצים, התחום האפשרי והנקודה האופטימלית.
התחום האפשרי מוצלל בכחול. קו המטרה מגיע לערכו המרבי בחיתוך של אילוצים 2 ו-3.

נחשב במדויק את חיתוך אילוצים 2 ו-3. נסמן את משוואת אילוץ 2 ב-(1) ואת משוואת אילוץ 3 ב-(2):

(1)   4x₁ + 12x₂ = 68 (2)   8x₁ + 8x₂ = 68
  1. מכפילים את משוואה (1) ב-2 כדי שמקדמי x₁ בשתי המשוואות יהיו שווים. 2(4x₁ + 12x₂) = 2 · 68   ⇒   8x₁ + 24x₂ = 136
  2. מחסרים את משוואה (2) מהמשוואה החדשה. איברי 8x₁ מתבטלים, ולכן נשאר רק x₂. (8x₁ + 24x₂) - (8x₁ + 8x₂) = 136 - 68 16x₂ = 68
  3. מחלקים את שני אגפי המשוואה ב-16. x₂ = 68/16 = 4.25
  4. מציבים x₂ = 4.25 במשוואה (2) כדי למצוא את x₁. 8x₁ + 8 · 4.25 = 68   ⇒   8x₁ = 34   ⇒   x₁ = 4.25

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

קודקוד ערך פונקציית המטרה
(0, 0) Z = 0
(0, 17/3) Z = 2400 · 17/3 = 13,600
(4.25, 4.25) Z = 1800 · 4.25 + 2400 · 4.25 = 17,850
(8.5, 0) Z = 1800 · 8.5 = 15,300

תוצאת הסעיף: מייצרים x₁ = 4.25 ו-x₂ = 4.25. הרווח השבועי המרבי הוא Z = 17,850 ₪.

ג ערכים דואליים

נוסח הסעיף: חשבו את הערך הדואלי של כל אחד מהאילוצים.

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

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

אילוץ שימוש בנקודה (4.25, 4.25) קיבולת מסקנה
1 6 · 4.25 + 10 · 4.25 = 68 72 לא פעיל; המרווח הוא 72 - 68 = 4, ולכן DV₁ = 0.
2 4 · 4.25 + 12 · 4.25 = 68 68 פעיל (הדוק).
3 8 · 4.25 + 8 · 4.25 = 68 68 פעיל (הדוק).

אילוץ 2: משווים בין אגף ימין 68 לבין קצה הטווח שבו הנקודה היא (8.5, 0) ואגף ימין 34.

DV₂ = (17,850 - 15,300) / (68 - 34) DV₂ = 2,550 / 34 = 75

אילוץ 3: בקצה ההשוואה השני הנקודה היא (0, 17/3). נסמן ב-b₃ את אגף ימין של אילוץ 3 בנקודת ההשוואה. שמירת השבר המדויק מונעת שגיאת עיגול:

b₃ = 8 · (17/3) = 136/3 DV₃ = (17,850 - 13,600) / (68 - 136/3) DV₃ = 4,250 / (68/3) = 187.5

תוצאת הסעיף: הערכים הדואליים הם DV₁ = 0, DV₂ = 75 ו-DV₃ = 187.5 ₪ לשעת תהליך.

ד הוספת 5 שעות לתהליך 2

נוסח הסעיף: בהשקעה שבועית של 145 ₪ ניתן להוסיף 5 שעות הפעלה לתהליך השני. האם ההשקעה כדאית? אם לא, הסבירו; אם כן, חשבו את הנקודה האופטימלית החדשה ואת השינוי ברווח השבועי.

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

נסמן ב-b₂ את אגף ימין של אילוץ 2. האינדקסים min, max ו-new מציינים את הגבול התחתון, הגבול העליון והערך החדש. גבולות תחום ההתקפות מתקבלים בשני הקודקודים שבהם מבנה הפתרון מתחלף:

b2,min = 4 · 8.5 + 12 · 0 = 34 b2,max = 4 · 3.25 + 12 · 5.25 = 76 b2,new = 68 + 5 = 73 ∈ [34, 76]

לכן מותר להשתמש בערך הדואלי DV₂ = 75. תוספת הרווח לפני עלות היא 75 · 5 = 375 ₪.

כדי למצוא את הנקודה החדשה, פותרים את החיתוך בין אילוץ 2 החדש, שנסמן (1), לבין אילוץ 3, שנסמן (2):

(1)   4x₁ + 12x₂ = 73 (2)   8x₁ + 8x₂ = 68
  1. מפשטים כל משוואה: מחלקים את (1) ב-4 ואת (2) ב-8. (1)   x₁ + 3x₂ = 18.25 (2)   x₁ + x₂ = 8.5
  2. מחסרים את משוואה (2) ממשוואה (1). איברי x₁ מתבטלים. (x₁ + 3x₂) - (x₁ + x₂) = 18.25 - 8.5 2x₂ = 9.75
  3. מחלקים את שני האגפים ב-2. x₂ = 9.75/2 = 4.875
  4. מציבים במשוואה (2) כדי למצוא את x₁. x₁ + 4.875 = 8.5   ⇒   x₁ = 3.625
רווח חדש לפני עלות
18,225 ₪
תוספת רווח לפני עלות
375 ₪
עלות שבועית
145 ₪
תוספת רווח נטו
375 - 145 = 230 ₪
רווח שבועי נטו חדש
18,225 - 145 = 18,080 ₪

תוצאת הסעיף: ההשקעה כדאית. הנקודה החדשה היא (3.625, 4.875), ותוספת הרווח השבועי נטו היא 230 ₪.

ה חסמים על מקדמי פונקציית המטרה

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

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

האילוצים הפעילים (הדוקים) בנקודה האופטימלית הם אילוצים 2 ו-3. נסמן ב-m₂ וב-m₃ את שיפועיהם. c₁ ו-c₂ הם מקדמי x₁ ו-x₂ בפונקציית המטרה.

m₂ = -4/12 = -1/3 m₃ = -8/8 = -1 1/3 ≤ c₁/c₂ ≤ 1

כאשר c₂ = 2400 נשאר קבוע:

800 ≤ c₁ ≤ 2400

כאשר c₁ = 1800 נשאר קבוע:

1800 ≤ c₂ ≤ 5400

תוצאת הסעיף: הטווחים הם 800 ≤ c₁ ≤ 2400 ו-1800 ≤ c₂ ≤ 5400.

ו ירידת הרווח ממוצר B

נוסח הסעיף: בבעיה המקורית, הרווח ליחידת מוצר B ירד ל-2,000 ₪. האם הדבר ישפיע על הפתרון האופטימלי ועל ערך פונקציית המטרה שמצאתם בסעיף ב'? הסבירו כיצד.

הרעיון: בודקים אם המקדם החדש נמצא בתחום ההתקפות שמצאנו בסעיף ה'. אם כן, הקודקוד נשאר ורק הרווח בו משתנה.

c₂ = 2000 נמצא בתוך תחום ההתקפות 1800 ≤ c₂ ≤ 5400, ולכן הפתרון נשאר (4.25, 4.25). נסמן ב-Znew את הרווח השבועי לאחר השינוי.

Znew = 1800 · 4.25 + 2000 · 4.25 = 16,150 (2400 - 2000) · 4.25 = 1,700 17,850 - 1,700 = 16,150

תוצאת הסעיף: תמהיל הייצור אינו משתנה. הרווח השבועי החדש הוא 16,150 ₪, כלומר ירידה של 1,700 ₪.

תשובה סופית

  1. א. max Z = 1800x₁ + 2400x₂, תחת שלושת אילוצי השעות ואילוצי אי-השליליות.
  2. ב. הפתרון האופטימלי הוא (4.25, 4.25), והרווח המרבי הוא 17,850 ₪.
  3. ג. הערכים הדואליים הם (0, 75, 187.5) ₪ לשעה עבור אילוצים 1, 2 ו-3.
  4. ד. ההשקעה כדאית. הנקודה החדשה היא (3.625, 4.875), ותוספת הרווח נטו היא 230 ₪.
  5. ה. 800 ≤ c₁ ≤ 2400 ו-1800 ≤ c₂ ≤ 5400.
  6. ו. הפתרון נשאר (4.25, 4.25), והרווח החדש הוא 16,150 ₪.

המשך במבחן

בחינה 1, חלק 2 · שאלה 1

זהו פתרון השאלה האחרון במבחן.

חזרה לרשימת המבחנים