דילוג לתוכן המרכזי

סיכום תכנון ליניארי

מתמטיקה כיתה י"ב 3 יח"ל · 6 נושאים

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

תזכורת: אי-שוויון ליניארי וחצי מישור

כבר ראינו שהישר 2x+y=82x+y=8 מחלק את המישור לשני חלקים. בצד אחד של הישר מתקיים 2x+y<82x+y<8, ובצד השני 2x+y>82x+y>8.

במדויק: הפתרון של אי-שוויון ליניארי בשני משתנים, כמו ax+by≤cax+by\le c (כאשר aa ו-bb אינם שניהם 00), הוא קבוצת כל הנקודות (x,y)(x,y) שמקיימות אותו. בסרטוט זה חצי מישור: כל הנקודות שבצד אחד של הישר ax+by=cax+by=c. כשהסימן הוא ≤\le או ≥\ge, גם הנקודות שעל הישר עצמו שייכות לפתרון. כשהסימן הוא << או >>, הן לא שייכות.

כדי לדעת איזה צד של הישר הוא הפתרון, מציבים נקודה אחת שאינה על הישר. נוח להציב את (0,0)(0,0): ב-2x+y≤82x+y\le8 מקבלים 0≤80\le8, וזה נכון. לכן הפתרון הוא הצד של הישר שבו נמצאת ראשית הצירים, כמו בשטח הצבוע. את הישר עצמו מסרטטים בעזרת נקודות החיתוך שלו עם הצירים: (4,0)(4,0) ו-(0,8)(0,8).

-3-2-112345678-2246810(4,0)(0,8)

מהו תכנון ליניארי

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

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

- משתנים xx ו-yy: שני הגדלים שאנחנו מחליטים עליהם (למשל מספר המוצרים מכל סוג).

- מערכת אילוצים: אי-שוויונות (ולפעמים גם משוואות) ממעלה ראשונה ב-xx וב-yy, שמתארים את המגבלות.

- פונקציית מטרה f(x,y)=ax+byf(x,y)=ax+by: הגודל שרוצים להגדיל ככל האפשר (מקסימום) או להקטין ככל האפשר (מינימום).

הפתרון האופטימלי הוא נקודה (x,y)(x,y) שמקיימת את כל האילוצים, ושבה פונקציית המטרה מקבלת את הערך המקסימלי או המינימלי, לפי מה שנדרש בבעיה.

השלבים של כל בעיה הם תמיד אותם שלבים, ולפיהם בנוי הנושא:

1. מגדירים את xx ואת yy וכותבים את מערכת האילוצים.

2. כותבים את פונקציית המטרה וקובעים אם מחפשים מקסימום או מינימום.

3. מסרטטים את התחום האפשרי ומוצאים את הקדקודים שלו.

4. מציבים את הקדקודים בפונקציית המטרה ובוחרים את הפתרון האופטימלי.

5. עונים על השאלה במילים של המצב.

1. תרגום בעיה מילולית למערכת אילוצים

אילוץ ומערכת אילוצים

כל מגבלה שכתובה בשאלה ("יש לכל היותר 60 שעות עבודה", "צריך לייצר לפחות 5 מוצרים") הופכת לאי-שוויון. אי-שוויון כזה נקרא אילוץ.

במדויק: אילוץ הוא אי-שוויון (או משוואה) ממעלה ראשונה ב-xx וב-yy שכל תוכנית מותרת חייבת לקיים. מערכת האילוצים היא כל האילוצים של הבעיה יחד: תוכנית מותרת רק אם היא מקיימת את כולם. כש-xx ו-yy הם כמויות (מספר מוצרים, קילוגרמים, שעות), המערכת כוללת גם את x≥0x\ge0 ו-y≥0y\ge0.

את הנתונים של בעיה כזאת נוח לסדר בטבלה: שורה לכל סוג מוצר, ועמודה לכל משאב (שעות, חומר, כסף). בשורה האחרונה כותבים כמה יש מכל משאב. כל עמודה הופכת לאילוץ אחד:

(כמות למוצר מסוג א)⋅x+\cdot x+(כמות למוצר מסוג ב)⋅y≤\cdot y\le(כמה יש).

מילים וסימנים

מה כתוב בשאלההסימן
לכל היותר, לא יותר מ-, עד≤\le
לפחות, לא פחות מ-≥\ge
יותר מ-, גדול מ->>
פחות מ-, קטן מ-<<
בדיוק==
דרך הפתרון

כתיבת מערכת האילוצים

כשנתונה בעיה מילולית עם שני סוגים של מוצרים (או פריטים):

1. מגדירים במילים: xx = מספר הפריטים מהסוג הראשון, yy = מספר הפריטים מהסוג השני (ובאיזו תקופה: ביום, בשבוע, במחזור ייצור).

2. מסדרים את הנתונים בטבלה: לכל סוג, כמה הוא צורך מכל משאב.

3. לכל משאב כותבים אילוץ: (כמות לפריט אחד מהסוג הראשון)⋅x+\cdot x+(כמות לפריט אחד מהסוג השני)⋅y\cdot y, ומשווים לכמות שיש בעזרת הסימן המתאים.

4. מוסיפים אילוצים על xx או על yy לבד, אם יש (למשל "לפחות 5 פריטים מהסוג השני": y≥5y\ge5).

5. מוסיפים x≥0x\ge0 ו-y≥0y\ge0.

שים לב

כל המספרים באילוץ אחד צריכים להיות באותן יחידות. אם זמן לפריט נתון בדקות והזמן שיש נתון בשעות, ממירים קודם (למשל 3030 דקות =0.5=0.5 שעה).

שים לב

המקדם של xx הוא הכמות לפריט אחד. אם כתוב "לייצור 1010 פריטים דרושים 44 קילוגרמים", המקדם הוא 0.40.4.

דוגמה - אילוצים מטבלת זמנים בשעות ובדקות

מפעל מייצר אופניים רגילים ואופניים חשמליים. בכל אופניים יש שני שלבים: הרכבה ובדיקה.

•הרכבה של אופניים רגילים נמשכת 33 שעות, ושל אופניים חשמליים 22 שעות. בשבוע אפשר להרכיב לכל היותר 6060 שעות.

•בדיקה של אופניים רגילים נמשכת 3030 דקות, ושל אופניים חשמליים שעה אחת. בשבוע אפשר לבדוק לכל היותר 1515 שעות.

•בכל שבוע המפעל חייב לייצר לפחות 55 אופניים חשמליים.

סמנו ב-xx את מספר האופניים הרגילים וב-yy את מספר האופניים החשמליים שהמפעל מייצר בשבוע. כתבו את מערכת האילוצים של הבעיה.

פתרון

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

2. מסדרים בטבלה. את זמן הבדיקה ממירים לשעות: 3030 דקות =0.5=0.5 שעה.

סוגהרכבה (שעות)בדיקה (שעות)
אופניים רגילים (xx)330.50.5
אופניים חשמליים (yy)2211
לכל היותר60601515

3. אילוץ ההרכבה: 3x+2y≤603x+2y\le60.

4. אילוץ הבדיקה: 0.5x+y≤150.5x+y\le15. אפשר לכפול ב-22 ולקבל x+2y≤30x+2y\le30.

5. "לפחות 55 אופניים חשמליים": y≥5y\ge5.

6. מספר האופניים לא שלילי: x≥0x\ge0. (את y≥0y\ge0 כבר מבטיח y≥5y\ge5.)

תשובה

3x+2y≤603x+2y\le60, x+2y≤30x+2y\le30, y≥5y\ge5, x≥0x\ge0

שאלות פתוחות על תרגום בעיה מילולית למערכת אילוצים

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

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

אחרי שכתבנו את המגבלות, צריך לדעת מה אנחנו רוצים להשיג: רווח גדול ככל האפשר? הוצאה קטנה ככל האפשר? את הגודל הזה כותבים כפונקציה של xx ושל yy.

במדויק: פונקציית המטרה היא פונקציה ממעלה ראשונה בשני משתנים, f(x,y)=ax+byf(x,y)=ax+by, שנותנת לכל תוכנית (x,y)(x,y) את הגודל שרוצים לשפר (רווח, הכנסה, עלות, זמן). המקדם aa הוא התרומה של פריט אחד מהסוג הראשון לגודל הזה, והמקדם bb הוא התרומה של פריט אחד מהסוג השני. הבעיה קובעת אם מחפשים את הערך המקסימלי של ff או את הערך המינימלי שלה.

פונקציית המטרה היא לא אילוץ: אין בה סימן ≤\le או ≥\ge. היא לא אומרת מה מותר, אלא כמה שווה כל תוכנית. למשל אם הרווח מכל שולחן הוא 5050 שקלים ומכל כיסא 3030 שקלים, אז f(x,y)=50x+30yf(x,y)=50x+30y, והתוכנית "44 שולחנות ו-66 כיסאות" שווה f(4,6)=200+180=380f(4,6)=200+180=380 שקלים.

מקסימום או מינימום

מה מחפשיםמקסימום או מינימום
רווח, הכנסהמקסימום
עלות, הוצאה, מחיר שמשלמיםמינימום
דרך הפתרון

כתיבת פונקציית המטרה

כשנתון כמה מרוויחים (או משלמים) על כל פריט:

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

2. כותבים f(x,y)=f(x,y)=(הסכום לפריט מהסוג הראשון)⋅x+\cdot x+(הסכום לפריט מהסוג השני)⋅y\cdot y.

3. קובעים לפי השאלה אם מחפשים מקסימום או מינימום.

4. ערך של תוכנית מסוימת מוצאים בהצבה: למשל f(10,6)f(10,6) הוא הערך כש-x=10x=10 ו-y=6y=6.

שים לב

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

דוגמה - עלות לפריט שמחשבים מכמה חומרים

מאפייה מכינה עוגות משני סוגים. לעוגה מסוג א דרושים 0.30.3 ק"ג קמח ו-0.20.2 ק"ג סוכר. לעוגה מסוג ב דרושים 0.50.5 ק"ג קמח ו-0.10.1 ק"ג סוכר. מחיר ק"ג קמח הוא 88 שקלים, ומחיר ק"ג סוכר הוא 55 שקלים. המאפייה רוצה שעלות החומרים תהיה נמוכה ככל האפשר.

סמנו ב-xx את מספר העוגות מסוג א וב-yy את מספר העוגות מסוג ב.

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

ב. מהי עלות החומרים ל-1010 עוגות מסוג א ו-66 עוגות מסוג ב?

פתרון

1. נתון: כמות הקמח והסוכר לכל עוגה, ומחיר ק"ג מכל חומר. המטרה: פונקציית העלות, וערך שלה בתוכנית אחת.

2. עלות החומרים לעוגה מסוג א: 0.3⋅8+0.2⋅5=2.4+1=3.40.3\cdot8+0.2\cdot5=2.4+1=3.4 שקלים.

3. עלות החומרים לעוגה מסוג ב: 0.5⋅8+0.1⋅5=4+0.5=4.50.5\cdot8+0.1\cdot5=4+0.5=4.5 שקלים.

4. פונקציית המטרה: f(x,y)=3.4x+4.5yf(x,y)=3.4x+4.5y. זו עלות, ולכן מחפשים מינימום.

5. מציבים x=10x=10, y=6y=6: f(10,6)=3.4⋅10+4.5⋅6=34+27=61f(10,6)=3.4\cdot10+4.5\cdot6=34+27=61.

תשובה

א. f(x,y)=3.4x+4.5yf(x,y)=3.4x+4.5y, מחפשים מינימום. ב. 6161 שקלים.

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

3. סרטוט התחום האפשרי ומציאת קדקודיו

התחום האפשרי וקדקודיו

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

במדויק: התחום האפשרי הוא קבוצת כל הנקודות (x,y)(x,y) שמקיימות את כל האילוצים של המערכת בבת אחת. הישרים שעליהם נמצא הגבול של התחום נקראים הישרים התוחמים. קדקוד של התחום הוא נקודה של התחום שבה נחתכים שני ישרים תוחמים (נקודת "פינה" של התחום).

במערכת x+2y≤8x+2y\le8, x≤6x\le6, x≥0x\ge0, y≥0y\ge0 התחום האפשרי הוא מרובע. הישרים התוחמים הם x+2y=8x+2y=8, x=6x=6 וצירי השיעורים. לתחום יש ארבעה קדקודים: O(0,0)O(0,0), (6,0)(6,0), (6,1)(6,1) ו-(0,4)(0,4). בסרטוט הישר x=6x=6 הוא הקו האנכי.

-1123456789-112345(0,4)(6,1)(6,0)
דרך הפתרון

סרטוט התחום האפשרי

כשנתונה מערכת אילוצים:

1. לכל אילוץ מסרטטים את הישר שלו (מחליפים את סימן אי-השוויון ב-==). נוח למצוא שתי נקודות: מציבים x=0x=0 ומוצאים yy, ואז מציבים y=0y=0 ומוצאים xx.

2. ישר מהצורה x=kx=k מאונך לציר ה-xx, וישר מהצורה y=ky=k מקביל לציר ה-xx.

3. לכל אילוץ בוחרים את הצד הנכון של הישר: מציבים את (0,0)(0,0) באי-השוויון. אם מתקבל משפט נכון, זה הצד של הראשית. אם לא, זה הצד השני. אם הישר עובר דרך (0,0)(0,0), מציבים נקודה אחרת, למשל (1,0)(1,0).

4. התחום האפשרי הוא השטח המשותף לכל הצדדים שנבחרו. x≥0x\ge0 ו-y≥0y\ge0 שמים אותו ברביע הראשון.

דרך הפתרון

מציאת הקדקודים

כשהתחום האפשרי מסורטט:

1. קדקוד על ציר: מציבים x=0x=0 (על ציר ה-yy) או y=0y=0 (על ציר ה-xx) במשוואת הישר שעובר שם.

2. קדקוד שבו נחתכים שני ישרים: פותרים את מערכת שתי המשוואות שלהם. למשל מבודדים את yy בשתיהן ומשווים.

3. בודקים שהנקודה שהתקבלה מקיימת את כל האילוצים.

שים לב

לא כל נקודת חיתוך של שני ישרים היא קדקוד. אם היא לא מקיימת אחד האילוצים האחרים, היא מחוץ לתחום, ולא מציבים אותה בפונקציית המטרה.

דוגמה - חמישה קדקודים ונקודת חיתוך שאינה קדקוד

נתונה מערכת האילוצים:

x+y≤10x+y\le10, 2x+y≤162x+y\le16, y≤8y\le8, x≥0x\ge0, y≥0y\ge0.

א. סרטטו את התחום האפשרי.

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

פתרון

1. נתון: חמישה אילוצים. המטרה: התחום האפשרי והקדקודים שלו.

2. הישר x+y=10x+y=10 עובר דרך (0,10)(0,10) ו-(10,0)(10,0). הישר 2x+y=162x+y=16 עובר דרך (0,16)(0,16) ו-(8,0)(8,0). הישר y=8y=8 מקביל לציר ה-xx.

3. הצבת (0,0)(0,0) בשלושת האילוצים נותנת 0≤100\le10, 0≤160\le16, 0≤80\le8: הכול נכון, ולכן בכל אילוץ התחום הוא בצד של הראשית.

4. קדקודים על הצירים: O(0,0)O(0,0), (8,0)(8,0) (על 2x+y=162x+y=16; הנקודה (10,0)(10,0) לא מקיימת 2x+y≤162x+y\le16), ו-(0,8)(0,8) (על y=8y=8).

5. חיתוך x+y=10x+y=10 עם 2x+y=162x+y=16: y=10−xy=10-x ו-y=16−2xy=16-2x, ולכן 10−x=16−2x10-x=16-2x, x=6x=6, y=4y=4. הנקודה (6,4)(6,4) מקיימת y≤8y\le8.

6. חיתוך x+y=10x+y=10 עם y=8y=8: x=2x=2. הנקודה (2,8)(2,8) מקיימת 2⋅2+8=12≤162\cdot2+8=12\le16.

7. חיתוך 2x+y=162x+y=16 עם y=8y=8: x=4x=4, אבל 4+8=12>104+8=12>10. הנקודה (4,8)(4,8) לא בתחום, ולכן היא לא קדקוד.

בסרטוט: הישר 2x+y=162x+y=16 בקו מקווקו, והישר y=8y=8 הוא הקו האופקי.

-11234567891011-11234567891011(8,0)(6,4)(2,8)
תשובה

O(0,0)O(0,0), (8,0)(8,0), (6,4)(6,4), (2,8)(2,8), (0,8)(0,8)

שאלות פתוחות על סרטוט התחום האפשרי ומציאת קדקודיו

4. מציאת הפתרון האופטימלי בתחום אפשרי סגור

תחום אפשרי סגור

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

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

במערכת x+y≤6x+y\le6, y≤4y\le4, x≥0x\ge0, y≥0y\ge0 התחום הוא מרובע סגור עם הקדקודים O(0,0)O(0,0), (6,0)(6,0), (2,4)(2,4) ו-(0,4)(0,4). הישר x+y=6x+y=6 מסורטט בקו מלא, והישר y=4y=4 בקו מקווקו.

-112345678-1123456(0,4)(2,4)(6,0)

איפה נמצא הפתרון האופטימלי בתחום סגור

בתחום אפשרי סגור יש לפונקציית המטרה f(x,y)=ax+byf(x,y)=ax+by גם ערך מקסימלי וגם ערך מינימלי, וכל אחד מהם מתקבל באחד הקדקודים של התחום. לכן מספיק להציב את הקדקודים בלבד.

דרך הפתרון

מציאת הפתרון האופטימלי

כשנתונים התחום האפשרי (סגור) ופונקציית המטרה:

1. מוצאים את שיעורי כל הקדקודים.

2. מציבים כל קדקוד בפונקציית המטרה ורושמים בטבלה: קדקוד וערך ff.

3. בבעיית מקסימום בוחרים את הקדקוד עם הערך הגדול ביותר. בבעיית מינימום בוחרים את הקדקוד עם הערך הקטן ביותר.

4. עונים במילים: כמה מכל סוג, ומה הערך האופטימלי (למשל הרווח המקסימלי).

שים לב

שיעורי הקדקוד הם התשובה לשאלה "כמה מכל סוג". הערך של ff בקדקוד הוא התשובה לשאלה "מהו הרווח המקסימלי" (או העלות המינימלית). עונים על כל שאלה בנפרד.

דוגמה - רווח מקסימלי בחקלאות: חמישה קדקודים

חקלאי מגדל עגבניות ומלפפונים. יש לו לכל היותר 4040 דונם. דונם עגבניות צורך 33 קוב מים ביום, ודונם מלפפונים צורך 66 קוב מים ביום. החקלאי יכול להשתמש לכל היותר ב-180180 קוב מים ביום. בנוסף, מותר לו לגדל לכל היותר 3030 דונם עגבניות.

הרווח מדונם עגבניות הוא 500500 שקלים, והרווח מדונם מלפפונים הוא 600600 שקלים.

סמנו ב-xx את מספר הדונמים של עגבניות וב-yy את מספר הדונמים של מלפפונים.

א. כתבו את מערכת האילוצים ואת פונקציית המטרה.

ב. כמה דונם מכל ירק צריך לגדל כדי שהרווח יהיה מקסימלי? מהו הרווח המקסימלי?

פתרון

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

2. אילוצים: x+y≤40x+y\le40 (שטח), 3x+6y≤1803x+6y\le180, כלומר x+2y≤60x+2y\le60 (מים), x≤30x\le30 (עגבניות), x≥0x\ge0, y≥0y\ge0.

3. פונקציית המטרה: f(x,y)=500x+600yf(x,y)=500x+600y. זה רווח, ולכן מחפשים מקסימום.

4. קדקודים על הצירים: O(0,0)O(0,0), (30,0)(30,0) (על x=30x=30) ו-(0,30)(0,30) (על x+2y=60x+2y=60; הנקודה (0,40)(0,40) לא מקיימת x+2y≤60x+2y\le60).

5. חיתוך x=30x=30 עם x+y=40x+y=40: (30,10)(30,10). בדיקה: 30+20=50≤6030+20=50\le60.

6. חיתוך x+y=40x+y=40 עם x+2y=60x+2y=60: מחסרים את המשוואות ומקבלים y=20y=20, ואז x=20x=20. בדיקה: 20≤3020\le30.

7. מציבים בפונקציית המטרה:

קדקודf(x,y)=500x+600yf(x,y)=500x+600y
(0,0)(0,0)00
(30,0)(30,0)15,00015{,}000
(30,10)(30,10)21,00021{,}000
(20,20)(20,20)22,00022{,}000
(0,30)(0,30)18,00018{,}000

8. הערך הגדול ביותר מתקבל ב-(20,20)(20,20). (בסרטוט: הישר x+y=40x+y=40 בקו מלא, הישר x+2y=60x+2y=60 בקו מקווקו, והישר x=30x=30 הוא הקו האנכי.)

‫עגבניות‬‫מלפפונים‬10203040102030(30,10)(20,20)(0,30)
תשובה

א. x+y≤40x+y\le40, x+2y≤60x+2y\le60, x≤30x\le30, x≥0x\ge0, y≥0y\ge0; f(x,y)=500x+600yf(x,y)=500x+600y. ב. 2020 דונם עגבניות ו-2020 דונם מלפפונים. הרווח המקסימלי: 22,00022{,}000 שקלים.

שאלות פתוחות על מציאת הפתרון האופטימלי בתחום אפשרי סגור

5. מציאת הפתרון האופטימלי בתחום אפשרי פתוח

תחום אפשרי פתוח

כשהאילוצים הם מהסוג "לפחות" (למשל "צריך לאכול לפחות 120120 גרם חלבון"), אפשר תמיד לקחת עוד ועוד, והתחום האפשרי לא נסגר: הוא ממשיך בלי סוף, ככל ש-xx או yy גדלים.

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

במערכת x+2y≥6x+2y\ge6, 2x+y≥62x+y\ge6, x≥0x\ge0, y≥0y\ge0 התחום נמצא מעל שני הישרים וממשיך בלי סוף. יש לו שלושה קדקודים: (0,6)(0,6), (2,2)(2,2) ו-(6,0)(6,0). הישר x+2y=6x+2y=6 מסורטט בקו מלא, והישר 2x+y=62x+y=6 בקו מקווקו.

-1123456789-112345678(0,6)(2,2)(6,0)

פתרון אופטימלי בתחום פתוח

כשהתחום האפשרי פתוח ונמצא ברביע הראשון (x≥0x\ge0, y≥0y\ge0), ופונקציית המטרה היא f(x,y)=ax+byf(x,y)=ax+by עם a>0a>0 ו-b>0b>0 (למשל עלות):

•יש ל-ff ערך מינימלי, והוא מתקבל באחד הקדקודים של התחום.

- אין ל-ff ערך מקסימלי: בתחום יש נקודות עם xx או yy גדולים כרצוננו, ושם ff גדלה בלי גבול.

דרך הפתרון

מינימום בתחום פתוח

כשהתחום האפשרי פתוח ומחפשים מינימום (למשל הוצאה מינימלית):

1. מוצאים את הקדקודים: נקודות החיתוך של הישרים התוחמים זה עם זה ועם הצירים, שמקיימות את כל האילוצים.

2. מציבים כל קדקוד בפונקציית המטרה.

3. בוחרים את הקדקוד עם הערך הקטן ביותר.

שים לב

בתחום פתוח שואלים על מינימום. אם בתחום כזה מוסיפים אילוץ "לכל היותר" שסוגר אותו, התחום נעשה סגור, ואז אפשר למצוא גם מקסימום.

דוגמה - הוצאה מינימלית על תערובת מזון

במשק מערבבים שני סוגים של מזון לבעלי חיים. בכל שק מסוג א יש 3030 גרם חלבון, 2020 גרם פחמימות ו-55 גרם סיבים. בכל שק מסוג ב יש 1010 גרם חלבון, 2020 גרם פחמימות ו-1515 גרם סיבים. בכל יום צריך לפחות 120120 גרם חלבון, לפחות 160160 גרם פחמימות ולפחות 6060 גרם סיבים.

מחיר שק מסוג א הוא 55 שקלים, ומחיר שק מסוג ב הוא 33 שקלים.

סמנו ב-xx את מספר השקים מסוג א וב-yy את מספר השקים מסוג ב ביום. כמה שקים מכל סוג צריך לקנות ביום כדי שההוצאה תהיה מינימלית? מהי ההוצאה המינימלית?

פתרון

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

2. אילוצים: 30x+10y≥12030x+10y\ge120, כלומר 3x+y≥123x+y\ge12 (חלבון); 20x+20y≥16020x+20y\ge160, כלומר x+y≥8x+y\ge8 (פחמימות); 5x+15y≥605x+15y\ge60, כלומר x+3y≥12x+3y\ge12 (סיבים); x≥0x\ge0, y≥0y\ge0.

3. פונקציית המטרה: f(x,y)=5x+3yf(x,y)=5x+3y, מחפשים מינימום. כל האילוצים הם "לפחות", ולכן התחום פתוח.

4. קדקודים על הצירים: (0,12)(0,12) (על 3x+y=123x+y=12) ו-(12,0)(12,0) (על x+3y=12x+3y=12).

5. חיתוך 3x+y=123x+y=12 עם x+y=8x+y=8: מחסרים ומקבלים 2x=42x=4, x=2x=2, y=6y=6. בדיקה: 2+18=20≥122+18=20\ge12.

6. חיתוך x+y=8x+y=8 עם x+3y=12x+3y=12: מחסרים ומקבלים 2y=42y=4, y=2y=2, x=6x=6. בדיקה: 18+2=20≥1218+2=20\ge12.

7. מציבים בפונקציית המטרה:

קדקודf(x,y)=5x+3yf(x,y)=5x+3y
(0,12)(0,12)3636
(2,6)(2,6)2828
(6,2)(6,2)3636
(12,0)(12,0)6060

8. הערך הקטן ביותר מתקבל ב-(2,6)(2,6). (בסרטוט: הישר x+y=8x+y=8 בקו מקווקו, הישר 3x+y=123x+y=12 הוא התלול מבין השניים האחרים, והישר x+3y=12x+3y=12 הוא המתון.)

24681012142468101214(0,12)(2,6)(6,2)(12,0)
תשובה

22 שקים מסוג א ו-66 שקים מסוג ב. ההוצאה המינימלית: 2828 שקלים ביום.

שאלות פתוחות על מציאת הפתרון האופטימלי בתחום אפשרי פתוח

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

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

כל נקודה (x,y)(x,y) במערכת הצירים מתארת תוכנית אחת: "xx מהסוג הראשון ו-yy מהסוג השני". השאלה "האם אפשר לבצע את התוכנית?" היא בעצם השאלה "האם הנקודה בתחום האפשרי?".

במדויק: נקודה (x,y)(x,y) נמצאת בתחום האפשרי אם היא מקיימת את כל האילוצים, ואז התוכנית שהיא מתארת אפשרית. אם היא לא מקיימת אפילו אילוץ אחד, היא מחוץ לתחום, והתוכנית לא אפשרית. נקודה בתחום שמקיימת אילוץ מסוים בשוויון נמצאת על הישר של האילוץ הזה, בגבול התחום.

בתחום של x+2y≤8x+2y\le8, x≤6x\le6, x≥0x\ge0, y≥0y\ge0:

- A(2,1)A(2,1): 2+2=4≤82+2=4\le8, והנקודה בתוך התחום.

- B(4,2)B(4,2): 4+4=84+4=8, כלומר האילוץ x+2y≤8x+2y\le8 מתקיים בשוויון. הנקודה על הישר x+2y=8x+2y=8, בגבול התחום.

- C(5,3)C(5,3): 5+6=11>85+6=11>8. הנקודה מחוץ לתחום.

בסרטוט הישר x=6x=6 הוא הקו האנכי.

-1123456789-112345ABC

מה המיקום של הנקודה אומר על המצב

מיקום הנקודהמה זה אומר
בתוך התחום, לא על אף ישר תוחםהתוכנית אפשרית, ואף אילוץ לא מתקיים בשוויון (למשל נשארות שעות עבודה שלא נוצלו)
על ישר תוחם, בגבול התחוםהתוכנית אפשרית, והאילוץ של הישר הזה מתקיים בשוויון (למשל כל השעות מנוצלות)
מחוץ לתחוםהתוכנית לא אפשרית: לפחות אילוץ אחד לא מתקיים
על ציר ה-yy (x=0x=0)לא מייצרים בכלל מהסוג הראשון
על ציר ה-xx (y=0y=0)לא מייצרים בכלל מהסוג השני
דרך הפתרון

בדיקה אם תוכנית אפשרית

כשנתונה תוכנית (xx מסוג אחד ו-yy מסוג אחר) ושואלים אם היא אפשרית:

1. מציבים את xx ואת yy בכל אחד מהאילוצים.

2. אם כל האילוצים מתקיימים, התוכנית אפשרית (הנקודה בתחום).

3. אם אילוץ אחד או יותר לא מתקיים, התוכנית לא אפשרית. כותבים איזה אילוץ לא מתקיים ומה המשמעות שלו במילים (למשל "אין מספיק שעות עבודה").

שים לב

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

דוגמה - שתי תוכניות לחקלאי: אפשרית ולא אפשרית

חקלאי מגדל xx דונם עגבניות ו-yy דונם מלפפונים. מערכת האילוצים שלו היא:

x+y≤40x+y\le40 (שטח), x+2y≤60x+2y\le60 (מים), x≤30x\le30, x≥0x\ge0, y≥0y\ge0.

הרווח שלו הוא f(x,y)=500x+600yf(x,y)=500x+600y שקלים, והרווח המקסימלי הוא 22,00022{,}000 שקלים.

א. החקלאי שוקל לגדל 1010 דונם עגבניות ו-1010 דונם מלפפונים. האם זה אפשרי? אם כן, האם זו התוכנית הרווחית ביותר?

ב. האם אפשר לגדל 1010 דונם עגבניות ו-2828 דונם מלפפונים? נמקו.

פתרון

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

2. א. מציבים (10,10)(10,10): 10+10=20≤4010+10=20\le40, 10+20=30≤6010+20=30\le60, 10≤3010\le30. כל האילוצים מתקיימים, ולכן התוכנית אפשרית.

3. הרווח: f(10,10)=5,000+6,000=11,000f(10,10)=5{,}000+6{,}000=11{,}000 שקלים. זה פחות מ-22,00022{,}000, ולכן זו לא התוכנית הרווחית ביותר.

4. ב. מציבים (10,28)(10,28): 10+28=38≤4010+28=38\le40, אבל 10+56=66>6010+56=66>60. אילוץ המים לא מתקיים, ולכן הנקודה מחוץ לתחום. במילים: התוכנית צריכה 3⋅10+6⋅28=1983\cdot10+6\cdot28=198 קוב מים ביום, ויש רק 180180.

בסרטוט: הישר x+y=40x+y=40 בקו מלא, הישר x+2y=60x+2y=60 בקו מקווקו, והישר x=30x=30 הוא הקו האנכי.

‫עגבניות‬‫מלפפונים‬10203040102030(10,10)(10,28)
תשובה

א. אפשרי, אבל הרווח 11,00011{,}000 שקלים קטן מהרווח המקסימלי. ב. לא אפשרי: אילוץ המים לא מתקיים, כלומר אין מספיק מים.

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

כל האתר במבט אחד

קיצורי דרך לכל הכלים, הבגרויות והקורסים

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