שיעור 3
תכנון לינארי -ניסוח בעיות השקעה ותובלה
דוגמא 1:
משקיע שוקל אלטרנטיבות שונות להשקעה במשך 5 השנים הבאות. השקעה ניתנת לביצוע ביום הראשון של כל שנה. אפשרויות ההשקעה הנן:
השקעה A: .אפשרית בתחילת כל שנה נותנת תשואה של 15% לאחר שנתיים.
השקעה B: אפשרית רק בתחילת השנה השלישית נותנת תשואה של 25% לאחר 3 שנים. כמות הכסף המקסימאלית שנתן להשקיע באפיק זה הנה 040444 דולר
השקעה C: אפשרית רק בתחילת השנה השנייה. נותנת תשואה של 40% לאחר 4 שנים. כמות הכסף המקסימאלית שנתן להשקיע באפיק זה דולר 340444
אג"ח ממשלתיות: השקעה זו אפשרית בתחילת כל שנה. נותנת תשואה של 6% בשנה
בידי המשקיע 100,000 דולר להשקעה. כיצד יבנה את תכנית ההשקעות שלו על מנת להגיע לכמות הכסף המקסימאלית בתום 5 שנים.
נסח את הבעיה כבעיית תכנון ליניארי.
פתרון דוגמא 1- בעיית השקעה
נעבוד לפי השלבים:
- הגדרת משתני החלטה
- פונקציית המטרה
- אילוצים
משתני החלטה: המשקיע צריך לקבל החלטה כמה כסף להשקיע בכל אפיק ובנוסף השנים.
ולכן: XiJ- כמות הכסף שנשקיע בתחילת כל שנה באפיק מסויים.
X- כמות הכסף שנשקיע
i- בתחילת שנה כאשר ( i=1,2,3,4,5)
J- אפיק (J=1,2,3,4,5)
לדוגמא: XiJ- כמות הכסף שנשקיע בתחילת שנה ראשונה באפיק A
פונקציית המטרה: דרוש לנו מקסימום של כמות הכסף וכמות התשואה.
כאשר רוצים לנסח בעיית השקעה מומלץ לסדר את הנתונים בטבלה:
6 |
5 |
4 |
3 |
2 |
1 |
אפיקי ההשקעה |
X5A |
X4A |
X3A |
X2A |
X1A |
A |
|
|
|
X3B |
|
|
B |
|
|
|
|
X2C |
|
C |
|
X5G |
X4G |
X3G |
X2G |
X1G |
G- אג"ח ממשלתית |
|
1.4X2C + 1.25X3B + 1.15X4A + 1.06X5G |
1.15X3A + X4G1.06 |
X2A +1.15 1.06X3G |
1.15X1A + 1.06X2G |
1.06X1G |
100,000 |
כמות כסף זמינה |
כעת ננסח את פונקציית המטרה:זוהי סף כמות הכסף בתום השנה ה 5.
MAXZ=1.4X2C +1.25X3B +1.15X4A +1.06X5G
אילוצים:
אל האילוצים ננסח לפי העמודות של הטבלה:
S.T : 1. X1A + X1G ≤ 100,000
2. X2A + X2C + X2G – 1.06X1G ≤ 0
3. X3A + X3B + X3G – 1.15X1A – 1.06X1G ≤0
4. X4A +X4G – 1.15X2A – 1.06X3G ≤0
5. X5G – 1.15X3A – 1.06X4G ≤0
6. X3B ≤40,000
7. X2C ≤30,000
XiJ≥0
דוגמא 2
חברת מייצרת רכיבים אלקטרוניים בשני מפעלים שונים ומובילה את הרכיבים לחמישה מחסנים אזוריים.עלות הייצור במפעל 1- 22 ₪ ליחידה ועלות הייצור במפעל 2- 27 ₪ ליחידה.
הביקוש השבועי הצפוי הינו: מחסן 1- 2000 יחידות ,מחסן 2- 3000 יחידות, מחסן 3- 1000 יחידות, מחסן 4- 5000 יחידות, מחסן 5- 4000 יחידות. יש לספק את הביקושים למחסנים האזוריים. עלויות ההובלה מהמפעלים למחסנים נתונות בטבלה הבאה:
מחסן 1 |
מחסן 2 |
מחסן 3 |
מחסן 4 |
מחסן 5 |
|
מפעל 1 |
3 ₪ |
2 ₪ |
5 ₪ |
4 ₪ |
2 ₪ |
מפעל 2 |
6 ₪ |
4 ₪ |
2 ₪ |
3 ₪ |
5 ₪ |
קיבולת הייצור השבועית של כל אחד מהמפעלים היא 8000 יחידות
א. נסח את הבעיה כבעיית תכנון ליניארי
ב. חשב את הפתרון האופטימאלי באמצעות התוכנה
פתרון דוגמא 2- בעיית תובלה
בעיית תובלה עוסקת בהובלת יח' מוצר ממקורות ליעדים.
כאשר : מקור = מי ששולח את יח' המוצר(מפעל, מחסן). יעד– מי שמקבל את יח' המוצר (לקוח, סניף)
המטרה בבעיות תובלה היא בדרך כלל מינימום-מאחר ומדובר בעלויות ייצור מהמקור ליעד.
משתני ההחלטה:
XiJ- כמות היחידות שיש להוביל ממפעל מסויים למחסן מסויים( מהמקור ליעדים) .
X- כמות היחדיות שנוביל
i- מקורות–מפעלים (i=1,2)
J- יעדים – מחסנים (J=1,2,3,4,5)
לדוגמא: X12=20, כמות היחידות שנוביל ממפעל 1 למחסן 2 היא 520 יחידות.
פונקציית המטרה: (כוללת את סך העלויות שלי שמורכבות הן מעלויות ייצור והן מעלויות הובלה)
MIN Z= 25X11+24X12+27X13+26X14+24X15 + 33X21+31X22+29X23+30X24+32X25
אילוצים:
S.T: 1. X11+X12+X13+X14+X15 ≤ 8000
ניתן לנסח גם כך:
2. X21+X22+X23+X24+X25 ≤8000
3. X11+X21 =2000
4. X12+X22=3000
5. X13+X23=1000
6. X14+X24=5000
7. X15+X25=4000
XiJ≥0
XiJ =int