שיעור 4:

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

כעת נעסוק במשתנה בינארי: זהו משתנה שמייצג לנו החלטה חיובית או שלילית ויכול לקבל ערכים: 0 או 1.

1. מציין החלטה חיובית: כן נייצר, כן נרכוש, כן נקים וכו'.
   
2. מייצג החלטה שלישית: לא נייצר, לא נרכוש, לא נקים וכו'.
   

ולכן כאשר קיימת בעיה רק עם משתנים בינארים אין צורך באילוץ אי שליליות ואילוץ שלמים.

דוגמא 1

חברה בודקת אפשרות להתרחב. יש אפשרות לבנות מפעל בעיר א' או בעיר ב'.

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

 

בנוסף, נתון שסך הוצאת ההתרחבות לא יכול להיות גבוה מ 10- מיליוני דולרים.

א. נסח את הבעיה באמצעות משתנים בינאריים.

ב. נסח אילוץ עבור כל אחד מהמגבלות שלהלן:

1. נדרש לבנות מפעל וגם מחסן בעיר א'.

2. נדרש לבנות מפעל או מחסן בעיר א', או את שניהם.

3. נדרש לבנות מפעל בעיר א', או בעיר ב', אך לא בשתיהן.

4. אם בונים מפעל בעיר א', אז יש לבנות שם גם מחסן.

5. יש לבנות מחסן בעיר א', אם ורק אם, בונים שם מפעל.

6. מותר לבנות לכל היותר 3 מבנים כלשהם )מפעלים או מחסנים(.

פיתרון לדוגמא 1:

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

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

    

   1. Y1+Y3=2
      
   2. Y1+Y3≥1 לא יתכן
      ש: Y1=0 ו Y3=0
      
   3. Y1+Y3=1
      
   4. Y1-Y3≤0
      
   5. Y1-Y3=0 אם אני מקימה מחסן אני צריכה מפעל וכנ"ל הפוך אין אופציה אחרת.
      
   6. Y1+Y2+Y3+Y4≤3
      

 

 

דוגמא 2

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

	סכום השקעה	תשואה צפויה
פרויקט 1	100,000	18%
פרויקט 2	150,000	21%
פרויקט 3	180,000	24%
פרויקט 4	275,000	26%

 

להלן אילוצים על ההשקעות:

1. אם משקיעים בפרויקט 1 אי אפשר להשקיע בפרויקט 4 .

1. חייבים להשקיע לפחות באחד משלושת הפרויקטים 1,2,3 .
   
2. אם משקיעים בפרויקט 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. מחירי החומרים נתונים בטבלה הבאה בדולר לטון:

 

המוצר הסופי נמכר במחיר של 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