שם הכותב: תאריך: 20 נובמבר 2014

שיעור 4:

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

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

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

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

דוגמא 1

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

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

שאלת כן/לא

משתנה החלטה בינארי

רווח עתידי

(מיליונים)

עלות הקמה

(מיליונים)

הקמת מפעל בעיר א'

Y1

9

6

הקמת מפעל בעיר ב'

Y2

5

3

הקמת מחסן בעיר א'

Y3

6

5

הקמת מחסן בעיר ב'

Y4

4

2

 

בנוסף, נתון שסך הוצאת ההתרחבות לא יכול להיות גבוה מ 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+2Y410

בינארי משמעותו– Y יכול לקבל או את הערך 0 או 1 Yi=bin

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

     

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

 

 

דוגמא 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,000Y4500,000

לפי השאלה לא יכול להתקיים T1=0 Y4=1 ולכן האילוץ: Y1+Y41

Y1+Y2+Y3+Y41

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+Y53

כאשר באילוץ מופיע משתנה בינארי וכמותי נכפול את המשתנה הבינארי בקבוע ולכן:

Xi 30*Yi נסדר ונקבל ß Xi-30Yi0

Y1-Y4 0

Y2-Y4 0

Yi=bin

Xi=bin

מאחר ומדובר בטון, וטון לא חייב להיות מספר שלם לכן אין אילוץ שלמים.

הערה:

כאשר בשאלה הגדרנו משתנה כמותי וגם משתנה בינארי יש לקשר את כל אחד מהמשתנים הכמותיים למשתנה הבינארי המתאים ולקיבולת הייצור/הרכישה.

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

X1210Y1

X2210Y2

X3260Y3

X4260Y4

X5260Y5

כעת נוסיף נתון נוסף:

נניח שאומרים לנו אם נרכוש חומר גלם SV2 תהיה לנו עלות נוספת של 1000 דולר.

כעת נוסיף את הנתון הנ"ל לפונקצית המטרה שלנו:

-115X1-128X2-132X3-109X4-114X5 – 1000*Y2


 



+ 5 = ארבע עשרה

תואר ראשון
תואר שני
מרצים