שיעור 4:
עד עכשיו עסקנו בהגדרת משתנה כמותי,כל משתנה החלטה קיבל ערכים כמותיים.
כעת נעסוק במשתנה בינארי: זהו משתנה שמייצג לנו החלטה חיובית או שלילית ויכול לקבל ערכים: 0 או 1.
- מציין החלטה חיובית: כן נייצר, כן נרכוש, כן נקים וכו'.
- מייצג החלטה שלישית: לא נייצר, לא נרכוש, לא נקים וכו'.
ולכן כאשר קיימת בעיה רק עם משתנים בינארים אין צורך באילוץ אי שליליות ואילוץ שלמים.
דוגמא 1
חברה בודקת אפשרות להתרחב. יש אפשרות לבנות מפעל בעיר א' או בעיר ב'.
ניתן גם לבנות מחסן בכל אחד מהאתרים. עלות הקמת המפעלים\המחסנים והרווח הצפוי לאחר ההקמה בכל אתר מסוכמים בטבלה להלן:
שאלת כן/לא |
משתנה החלטה בינארי |
רווח עתידי (מיליונים) |
עלות הקמה (מיליונים) |
הקמת מפעל בעיר א' |
Y1 |
9 |
6 |
הקמת מפעל בעיר ב' |
Y2 |
5 |
3 |
הקמת מחסן בעיר א' |
Y3 |
6 |
5 |
הקמת מחסן בעיר ב' |
Y4 |
4 |
2 |
בנוסף, נתון שסך הוצאת ההתרחבות לא יכול להיות גבוה מ 10- מיליוני דולרים.
א. נסח את הבעיה באמצעות משתנים בינאריים.
ב. נסח אילוץ עבור כל אחד מהמגבלות שלהלן:
1. נדרש לבנות מפעל וגם מחסן בעיר א'.
2. נדרש לבנות מפעל או מחסן בעיר א', או את שניהם.
3. נדרש לבנות מפעל בעיר א', או בעיר ב', אך לא בשתיהן.
4. אם בונים מפעל בעיר א', אז יש לבנות שם גם מחסן.
5. יש לבנות מחסן בעיר א', אם ורק אם, בונים שם מפעל.
6. מותר לבנות לכל היותר 3 מבנים כלשהם )מפעלים או מחסנים(.
פיתרון לדוגמא 1:
נגדיר משתני החלטה:
Yi Yi=0 לא נקים מפעל /מחסן בעיר א'/ב'
i=1,2,3,4 Yi=1 כן נקים מפעל /מחסן בעיר א'/ב'
פונקצית המטרה:מאחר ויש רווחים ועלויות הסכך הכללי הוא מקסימום.
MAXZ=9Y1 + 5Y2 + 6Y3 + 4Y4
אילוצים:
S.T: 6Y1+3Y2+5Y3+2Y4≤10
בינארי משמעותו– Y יכול לקבל או את הערך 0 או 1 Yi=bin
-
כל אחד מהסעיפים עומד בפני עצמו: ואת כל אחד מהאילוצים נבצע בהתאם לנדרש של כל סעיף.
- Y1+Y3=2
- Y1+Y3≥1 לא יתכן
ש: Y1=0 ו Y3=0
- Y1+Y3=1
- Y1-Y3≤0
- Y1-Y3=0 אם אני מקימה מחסן אני צריכה מפעל וכנ"ל הפוך אין אופציה אחרת.
- Y1+Y2+Y3+Y4≤3
- Y1+Y3=2
דוגמא 2
חברה מעוניינת להשקיע חצי מליון ₪ והיא שוקלת לבחור בין 4 פרויקטים. הסכום הנדרש להשקעה והתשואה הצפויה מכל אחד הפרויקטים נתונים בטבלה הבאה:
סכום השקעה |
תשואה צפויה |
|
פרויקט 1 |
100,000 |
18% |
פרויקט 2 |
150,000 |
21% |
פרויקט 3 |
180,000 |
24% |
פרויקט 4 |
275,000 |
26% |
להלן אילוצים על ההשקעות:
- אם משקיעים בפרויקט 1 אי אפשר להשקיע בפרויקט 4 .
- חייבים להשקיע לפחות באחד משלושת הפרויקטים 1,2,3 .
- אם משקיעים בפרויקט 2 חייבים להשקיע בפרויקט 4 .
החברה מעוניינת במקסימום רווח. נסח את הבעיה כבעיית תכנון בינארי
פיתרון לדוגמא 2:
נתונה לי כמות הכסף ולא כמות שאני יכולה להשקיע ולכן זה לא משתנה כמותי אלה בינארי
הגדרת משתני החלטה:
Yi=0 לא נשקיע בפרויקט i
Yi=1 כן נשקיע בפרויקט i
i=1,2,3,4
פונקצית המטרה:
MAXZ=0.18*100,000*Y1+0.21*150,000*Y2+0.24*180,000*Y4+0.26*275,000*Y4
אילוצים:
S.T:
100,000Y1+150,000Y2+180,000Y3+275,000Y4≤500,000
לפי השאלה לא יכול להתקיים T1=0 Y4=1 ולכן האילוץ: Y1+Y4≤1
Y1+Y2+Y3+Y4≥1
Y2 – Y4≤ 0
Yi=bin
דוגמא 3
יצרן משתמש במספר חומרי גלם לייצור מוצר מסוים (סוג של בטון). חומרי הגלם באים משתי קטגוריות :חומרי בסיס : SV1, SV2 , חומרי חיזוק : TV3, TV4, TV5. מחירי החומרים נתונים בטבלה הבאה בדולר לטון:
חומר |
TV5 |
TV4 |
SV3 |
SV2 |
SV1 |
מחיר |
114 |
109 |
132 |
128 |
115 |
המוצר הסופי נמכר במחיר של 118 דולר לטון. אין עלויות עיבוד של חומר הגלם. כמות השימוש בחומרי הגלם שווה לכמות המוצר. אין איבוד חומר בזמן העיבוד. אם משתמשים בחומר גלם מסוים, אי-אפשר לעבד יותר מקיבולת קו הייצור.קיבולות הייצור: לכל היותר 210 טון חומרי בסיס. לכל היותר 260 טון חומרי חיזוק. בהנחה שניתן למכור כל כמות מיוצרת של המוצר, יש להחליט אילו חומרי גלם לרכוש ובאילו כמויות כך שהרווח יהיה מקסימלי, בכפוף לאילוצים הבאים:
- המוצר הסופי חייב להיות מורכב משלושה חומרי גלם לכל היותר.
- אם משתמשים בחומר גלם (בסיס או מחזק), יש להשתמש לפחות ב- 30 טון.
- אם משתמשים בחומר בסיס SV1 או SV2 חייבים להשתמש גם ב – TV4.
נסח את הבעיה על פי המודל המתאים.
פתרון לדוגמא 3:
הגדרת משתני החלטה:
Xi- כמות חומר גלם שנרכוש בטון
I=1,2,3,4,5
Yi=0 לא נרכוש חומר גלם מסוג i
Yi=1 כן נרכוש חומר גלם מסוג i
i=1,2,3,4,5
פונקצית המטרה:
-115X1-128X2-132X3-109X4-114X5
אילוצים:
S.T: X1+X2 210
X3+X4+X5 260
מאחר ודיברו בסוגים ולא בכמות טון מדובר במשתנה בינארי ß Y1+Y2+Y3+Y4+Y5≤3
כאשר באילוץ מופיע משתנה בינארי וכמותי נכפול את המשתנה הבינארי בקבוע ולכן:
Xi≥ 30*Yi נסדר ונקבל ß Xi-30Yi≥0
Y1-Y4 ≤0
Y2-Y4 ≤0
Yi=bin
Xi=bin
מאחר ומדובר בטון, וטון לא חייב להיות מספר שלם לכן אין אילוץ שלמים.
הערה:
כאשר בשאלה הגדרנו משתנה כמותי וגם משתנה בינארי יש לקשר את כל אחד מהמשתנים הכמותיים למשתנה הבינארי המתאים ולקיבולת הייצור/הרכישה.
הקישור יתבצע על ידי הכפלה של קבוע במשתנה הבינארי:
X1≤210Y1
X2≤210Y2
X3≤260Y3
X4≤260Y4
X5≤260Y5
כעת נוסיף נתון נוסף:
נניח שאומרים לנו אם נרכוש חומר גלם SV2 תהיה לנו עלות נוספת של 1000 דולר.
כעת נוסיף את הנתון הנ"ל לפונקצית המטרה שלנו:
-115X1-128X2-132X3-109X4-114X5 – 1000*Y2