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

שאלה 1: ניסוח מודל לתוכנית אימונים

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

נוסח השאלה

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

מקום מגורים בינוני טוב מצוין
מקומי 600 900 500
לא מקומי 800 600 200
  • יש לקבל לפחות 2,000 ולכל היותר 2,500 סטודנטים.
  • מספר בעלי הציון טוב יהיה לפחות פי 3 ממספר בעלי הציון בינוני.
  • יתקבלו לפחות 550 בעלי ציון מצוין, והם יהיו לפחות 25% מכלל המתקבלים.
  • יתקבלו לפחות 300 סטודנטים לא מקומיים.
  • סטודנט בעל ציון בינוני דורש 50 שעות תגבור בשנה, וסטודנט בעל ציון טוב דורש 30 שעות. למכון סל של 5,300 שעות תגבור.
  • כל סטודנט משלם 10,000 ₪. בעל ציון מצוין מקבל מלגה של 2,000 ₪, וסטודנט לא מקומי מקבל מימון מעונות של 1,500 ₪.

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

זיהוי השיטה

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

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

פתרון מודרך

1 הגדרת משתני ההחלטה

נוסח המשימה: הגדירו את משתני ההחלטה והסבירו כל אחד מהם.

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

x₁, x₂, x₃
מספר הסטודנטים המקומיים שמתקבלים עם ציון בינוני, טוב ומצוין, בהתאמה.
y₁, y₂, y₃
מספר הסטודנטים הלא מקומיים שמתקבלים עם ציון בינוני, טוב ומצוין, בהתאמה.
D
המספר הכולל של הסטודנטים שמתקבלים לתוכנית.
Z
הרווח השנתי של המכון, בשקלים.

האינדקס 1 מציין ציון בינוני, האינדקס 2 מציין ציון טוב והאינדקס 3 מציין ציון מצוין. האות x מציינת מקומיים והאות y מציינת לא מקומיים.

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

2 פונקציית המטרה

נוסח המשימה: נסחו את פונקציית המטרה והסבירו אותה.

הרעיון: כל מתקבל מכניס 10,000 ₪; ממפחיתים מלגה מכל מצטיין ומימון מעונות מכל לא מקומי.

max  Z = 10,000D - 2,000(x₃ + y₃) - 1,500(y₁ + y₂ + y₃)

האיבר 10,000D הוא ההכנסה מכל הסטודנטים. האיבר 2,000(x₃+y₃) הוא סך מלגות ההצטיינות, והאיבר 1,500(y₁+y₂+y₃) הוא סך מימון המעונות ללא מקומיים.

תוצאת המשימה: פונקציית המטרה ממקסמת את ההכנסות נטו לאחר שתי ההטבות שהמכון מממן.

3 אילוצי המודל

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

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

זמינות מועמדים

x₁ ≤ 600,   x₂ ≤ 900,   x₃ ≤ 500 y₁ ≤ 800,   y₂ ≤ 600,   y₃ ≤ 200

אי אפשר לקבל מקבוצה מסוימת יותר מועמדים ממספר הנרשמים באותה קבוצה.

סך המתקבלים וקיבולת התוכנית

D = x₁ + x₂ + x₃ + y₁ + y₂ + y₃ 2,000 ≤ D ≤ 2,500

הרכב לפי ציוני קבלה

x₂ + y₂ ≥ 3(x₁ + y₁) x₃ + y₃ ≥ 550 x₃ + y₃ ≥ 0.25D

האילוץ הראשון דורש שמספר בעלי הציון טוב יהיה לפחות פי 3 ממספר בעלי הציון בינוני. שני האילוצים הבאים מחייבים גם מספר מוחלט וגם שיעור מינימלי של מצטיינים.

מקום מגורים ושעות תגבור

y₁ + y₂ + y₃ ≥ 300 50(x₁ + y₁) + 30(x₂ + y₂) ≤ 5,300

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

תחום הערכים

x₁, x₂, x₃, y₁, y₂, y₃ ∈ ℤ₊ D ∈ ℤ₊

ℤ₊ היא קבוצת המספרים השלמים שאינם שליליים. נדרשת שלמות מפני שהמשתנים סופרים בני אדם.

תוצאת המשימה: כל דרישות השאלה תורגמו לאילוצים עם כיוון ויחידות תואמים.

4 בדיקת עקביות של הנתונים

בדיקה משלימה: האם המודל שנוסח לפי הנתונים המודפסים יכול לקבל פתרון אפשרי?

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

יש לכל היותר 500 + 200 = 700 מועמדים מצטיינים. מאחר שחייבים לקבל לפחות 2,000 סטודנטים, לפחות 2,000 - 700 = 1,300 מהם יהיו בעלי ציון בינוני או טוב.

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

1,300 · 30 = 39,000 שעות תגבור 39,000 > 5,300

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

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

תשובה סופית

  1. משתנים: x₁,x₂,x₃ למקומיים ו-y₁,y₂,y₃ ללא מקומיים, לפי ציונים בינוני, טוב ומצוין; D הוא סך המתקבלים.
  2. מטרה: max Z = 10,000D - 2,000(x₃+y₃) - 1,500(y₁+y₂+y₃).
  3. אילוצים: מגבלות הזמינות, 2,000 ≤ D ≤ 2,500, דרישות היחס והאחוז, לפחות 300 לא מקומיים, מגבלת שעות ותחום שלם אי-שלילי.
  4. בדיקת נתונים: סל של 5,300 שעות אינו מאפשר לקבל 2,000 סטודנטים; המודל לפי הנוסח בלתי אפשרי.

המשך במבחן

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

המשך לפי סדר השאלות במבחן.

לשאלה הבאה: שאלה 4 - קמירות ואופטימיזציה קלאסית