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

סיכום תכנון ליניארי עם פרמטר

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

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

תזכורת: בעיית תכנון ליניארי

בבעיית תכנון ליניארי יש שני משתנים, xx ו-yy (למשל מספר המוצרים מכל סוג), ותנאים שהם חייבים לקיים. התנאים האלה הם מערכת האילוצים, והם נכתבים כאי-שוויונות. הגודל שרוצים להגדיל או להקטין (רווח, הכנסה, הוצאה) נקרא פונקציית המטרה, למשל f(x,y)=50x+40yf(x,y)=50x+40y.

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

בתחום שבסרטוט האילוצים הם x+2y≤16x+2y\le16, 3x+y≤183x+y\le18, x≥0x\ge0, y≥0y\ge0. הקדקודים הם O(0,0)O(0,0), A(6,0)A(6,0), B(4,6)B(4,6) ו-C(0,8)C(0,8). הקדקוד BB הוא נקודת החיתוך של הישרים x+2y=16x+2y=16 ו-3x+y=183x+y=18.

48369A(6,0)B(4,6)C(0,8)

עבור f(x,y)=5x+4yf(x,y)=5x+4y:

קדקודOOAABBCC
ערך ff00303044443232

הערך המקסימלי הוא 4444, בקדקוד B(4,6)B(4,6). הערך המינימלי הוא 00, בקדקוד OO.

פרמטר

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

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

בנושא הזה הפרמטר מופיע באחד משני מקומות:

איפה הפרמטרדוגמהמה הוא משנה
בפונקציית המטרהf(x,y)=kx+20yf(x,y)=kx+20yאת הערכים בקדקודים. התחום לא משתנה
באחד האילוציםx+y≤mx+y\le mאת התחום האפשרי ואת הקדקודים שלו

1. פרמטר בפונקציית המטרה: מציאתו מערך מקסימום או מינימום נתון

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

נניח שהרווח מעוגת שוקולד ידוע, 2020 ₪, אבל הרווח מעוגת גבינה לא ידוע. מסמנים אותו ב-kk, ופונקציית המטרה היא f(x,y)=kx+20yf(x,y)=kx+20y. אם השאלה נותנת את הרווח המקסימלי, אפשר למצוא את kk.

במדויק: כשפונקציית המטרה מכילה פרמטר והתחום האפשרי סגור, הנתון "הערך המקסימלי של ff בתחום הוא MM" אומר שני דברים: יש קדקוד שבו f=Mf=M, ובכל שאר הקדקודים f≤Mf\le M. הנתון "הערך המינימלי הוא MM" אומר: יש קדקוד שבו f=Mf=M, ובכל שאר הקדקודים f≥Mf\ge M.

הפרמטר בפונקציית המטרה לא משנה את התחום האפשרי, כי האילוצים לא תלויים בו. הוא משנה את הערכים בקדקודים, ולכן גם הקדקוד שבו מתקבל המקסימום יכול להשתנות. למשל בתחום שקדקודיו O(0,0)O(0,0), A(6,0)A(6,0), B(4,6)B(4,6), C(0,10)C(0,10), עם f(x,y)=kx+20yf(x,y)=kx+20y:

ערך kkf(A)=6kf(A)=6kf(B)=4k+120f(B)=4k+120f(C)=200f(C)=200המקסימום
10106060160160200200ב-CC
3535210210260260200200ב-BB
7070420420400400200200ב-AA

לכן אחרי שמוצאים את kk תמיד בודקים שהמקסימום באמת מתקבל בקדקוד שבו השתמשנו.

דרך הפתרון

מציאת הפרמטר מערך מקסימלי או מינימלי נתון

כשנתון הערך המקסימלי (או המינימלי) MM של פונקציית המטרה, ונתון באיזה קדקוד הוא מתקבל:

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

2. מציבים את השיעורים בפונקציית המטרה ומשווים ל-MM.

3. פותרים את המשוואה הליניארית ומוצאים את הפרמטר.

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

שים לב

אחרי שמצאתם את הפרמטר, כתבו את פונקציית המטרה המלאה, למשל f(x,y)=35x+20yf(x,y)=35x+20y, ורק אז ענו על שאר הסעיפים.

דוגמה - רווח מקסימלי נתון בקדקוד ידוע

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

נסמן ב-xx את מספר עוגות הגבינה וב-yy את מספר עוגות השוקולד. הרווח מעוגת שוקולד הוא 2020 ₪, והרווח מעוגת גבינה הוא kk ₪. התחום האפשרי מתואר בסרטוט (OO היא ראשית הצירים).

4836912ABC

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

ב. מצאו את שיעורי הקדקודים AA, BB ו-CC.

ג. ידוע שהרווח המקסימלי הוא 260260 ₪, והוא מתקבל בקדקוד BB. מצאו את kk.

פתרון

1. נתון: לכל היותר 1010 עוגות ולכל היותר 1818 כוסות קמח ביום. הרווח kk ₪ מעוגת גבינה ו-2020 ₪ מעוגת שוקולד. הרווח המקסימלי 260260 ₪, בקדקוד BB. המטרה: האילוצים, הקדקודים והפרמטר kk.

2. א. האילוצים: x+y≤10x+y\le10, 3x+y≤183x+y\le18, x≥0x\ge0, y≥0y\ge0. פונקציית המטרה: f(x,y)=kx+20yf(x,y)=kx+20y.

3. ב. AA על ציר ה-xx (y=0y=0): 3x=183x=18, ולכן A(6,0)A(6,0). CC על ציר ה-yy (x=0x=0): y=10y=10, ולכן C(0,10)C(0,10).

4. BB הוא נקודת החיתוך של x+y=10x+y=10 ו-3x+y=183x+y=18. מחסרים את המשוואות: 2x=82x=8, ולכן x=4x=4 ו-y=6y=6. B(4,6)B(4,6).

5. ג. מציבים את BB בפונקציית המטרה: f(4,6)=4k+120f(4,6)=4k+120. משווים לרווח המקסימלי: 4k+120=2604k+120=260, ולכן 4k=1404k=140 ו-k=35k=35.

6. בדיקה: עם f(x,y)=35x+20yf(x,y)=35x+20y: f(O)=0f(O)=0, f(A)=210f(A)=210, f(B)=260f(B)=260, f(C)=200f(C)=200. הערך 260260 הוא באמת הגדול ביותר.

תשובה

א. x+y≤10x+y\le10, 3x+y≤183x+y\le18, x≥0x\ge0, y≥0y\ge0; f(x,y)=kx+20yf(x,y)=kx+20y. ב. A(6,0)A(6,0), B(4,6)B(4,6), C(0,10)C(0,10). ג. k=35k=35: הרווח מעוגת גבינה 3535 ₪.

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

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

ערך שווה בשני קדקודים

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

במדויק: אם BB ו-CC הם שני קדקודים סמוכים של התחום (שני הקצוות של אותה צלע), ו-f(B)=f(C)f(B)=f(C) הוא הערך המקסימלי (או המינימלי) של ff בתחום, אז ff מקבלת את הערך הזה בכל נקודה של הצלע BCBC, וכל הנקודות האלה הן פתרונות אופטימליים.

בתחום שקדקודיו O(0,0)O(0,0), A(6,0)A(6,0), B(4,6)B(4,6), C(0,8)C(0,8), עם f(x,y)=10x+20yf(x,y)=10x+20y: f(A)=60f(A)=60, f(B)=160f(B)=160, f(C)=160f(C)=160. הערך המקסימלי 160160 מתקבל בשני הקדקודים BB ו-CC, וגם בכל נקודה של הצלע BCBC (על הישר x+2y=16x+2y=16). למשל הנקודה (2,7)(2,7), שמסומנת על הצלע: f(2,7)=20+140=160f(2,7)=20+140=160.

48369B(4,6)C(0,8)
דרך הפתרון

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

כשנתון שפונקציית המטרה (עם פרמטר) מקבלת ערך שווה בשני קדקודים BB ו-CC:

1. מוצאים את שיעורי BB ואת שיעורי CC.

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

3. משווים: f(B)=f(C)f(B)=f(C), ופותרים את המשוואה הליניארית.

4. מציבים את הפרמטר ומחשבים את הערך המשותף.

5. אם נאמר שזה הערך המקסימלי (או המינימלי), בודקים שבשאר הקדקודים הערך לא גדול ממנו (או לא קטן ממנו).

כל הנקודות על הצלע

אם הערך השווה בקדקודים הסמוכים BB ו-CC הוא הערך המקסימלי, כל נקודה על הצלע BCBC נותנת את אותו ערך מקסימלי. כש-xx ו-yy הם מספרי פריטים, הפתרונות הם הנקודות על הצלע ששני השיעורים שלהן מספרים שלמים.

שים לב

כדי לבדוק אם נקודה נמצאת על הצלע BCBC: מציבים אותה במשוואת הישר של הצלע, ובודקים שהשיעורים שלה נמצאים בין השיעורים של BB ושל CC.

שים לב

השוויון f(B)=f(C)f(B)=f(C) לבד לא אומר שזה הערך המקסימלי. אם השאלה שואלת על מקסימום, בודקים גם את שאר הקדקודים.

דוגמה - רווח מקסימלי שווה בשני קדקודים סמוכים

מפעל מייצר שני סוגי מוצרים, א ו-ב. ביום אחד אפשר לייצר לכל היותר 1010 מוצרים. מוצר א צריך שעה אחת במכונה I ו-22 שעות במכונה II. מוצר ב צריך 33 שעות במכונה I ושעה אחת במכונה II. מכונה I עובדת לכל היותר 2424 שעות ביום, ומכונה II לכל היותר 1616 שעות ביום.

נסמן ב-xx את מספר המוצרים מסוג א וב-yy את מספר המוצרים מסוג ב. האילוצים הם x+y≤10x+y\le10, x+3y≤24x+3y\le24, 2x+y≤162x+y\le16, x≥0x\ge0, y≥0y\ge0, והתחום האפשרי מתואר בסרטוט.

369369ABCD

הרווח ממוצר א הוא 6060 ₪, והרווח ממוצר ב הוא kk ₪.

א. מצאו את שיעורי הקדקודים AA, BB, CC ו-DD.

ב. ידוע שבקדקודים BB ו-CC מתקבל אותו רווח, והוא הרווח המקסימלי. מצאו את kk.

ג. מהו הרווח המקסימלי?

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

פתרון

1. נתון: האילוצים, פונקציית המטרה f(x,y)=60x+kyf(x,y)=60x+ky, ו-f(B)=f(C)f(B)=f(C) הוא הרווח המקסימלי. המטרה: kk, הרווח המקסימלי וכל האפשרויות שנותנות אותו.

2. א. AA: y=0y=0 ו-2x+y=162x+y=16, ולכן A(8,0)A(8,0). DD: x=0x=0 ו-x+3y=24x+3y=24, ולכן D(0,8)D(0,8).

3. BB הוא החיתוך של x+y=10x+y=10 ו-2x+y=162x+y=16. מחסרים: x=6x=6, ולכן y=4y=4: B(6,4)B(6,4).

4. CC הוא החיתוך של x+y=10x+y=10 ו-x+3y=24x+3y=24. מחסרים: 2y=142y=14, ולכן y=7y=7 ו-x=3x=3: C(3,7)C(3,7).

5. ב. f(B)=60⋅6+4k=360+4kf(B)=60\cdot6+4k=360+4k ו-f(C)=60⋅3+7k=180+7kf(C)=60\cdot3+7k=180+7k. משווים: 360+4k=180+7k360+4k=180+7k, ולכן 3k=1803k=180 ו-k=60k=60.

6. ג. עם f(x,y)=60x+60yf(x,y)=60x+60y: f(B)=f(C)=600f(B)=f(C)=600. בדיקה: f(O)=0f(O)=0, f(A)=480f(A)=480, f(D)=480f(D)=480, כולם קטנים מ-600600. הרווח המקסימלי 600600 ₪.

7. ד. הרווח המקסימלי מתקבל בכל נקודה של הצלע BCBC, כלומר על הישר x+y=10x+y=10 עם 3≤x≤63\le x\le6. הנקודות עם שיעורים שלמים: (3,7)(3,7), (4,6)(4,6), (5,5)(5,5), (6,4)(6,4).

תשובה

א. A(8,0)A(8,0), B(6,4)B(6,4), C(3,7)C(3,7), D(0,8)D(0,8). ב. k=60k=60. ג. 600600 ₪. ד. 33 מוצרי א ו-77 מוצרי ב, 44 ו-66, 55 ו-55, או 66 ו-44.

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

3. פרמטר באחד האילוצים

פרמטר באחד האילוצים

לפעמים הפרמטר נמצא באילוץ: למשל "ביום אחד אפשר לייצר לכל היותר mm פריטים", כלומר x+y≤mx+y\le m. כש-mm משתנה, הישר x+y=mx+y=m זז, ואיתו משתנים התחום האפשרי והקדקודים שלו.

במדויק: בשיעור הזה הפרמטר הוא המספר באגף הימני של אילוץ, כמו mm ב-x+y≤mx+y\le m. המקדמים של xx ושל yy קבועים, ולכן הישרים x+y=mx+y=m עבור ערכים שונים של mm מקבילים זה לזה. הקדקודים שנמצאים על הישר הזה תלויים ב-mm, והקדקודים האחרים לא.

בסרטוט האילוצים הם 2x+y≤202x+y\le20, x≥0x\ge0, y≥0y\ge0 ו-x+y≤mx+y\le m. התחום הצבוע מתאים ל-m=14m=14, והישר המקווקו הוא x+y=12x+y=12. עבור m=14m=14 הקדקוד שבו נפגשים x+y=mx+y=m ו-2x+y=202x+y=20 הוא (6,8)(6,8), ועבור m=12m=12 הוא (8,4)(8,4). הקדקוד (10,0)(10,0), על הישר 2x+y=202x+y=20, לא משתנה.

24681012142468101214(6,8)(8,4)

מה נתון ואיזו משוואה רושמים

מה נתוןאיזו משוואה רושמים
נקודה ידועה (a,b)(a,b) על הישר של האילוץ (למשל קדקוד ידוע)מציבים אותה במשוואת הישר. ב-x+y=mx+y=m: a+b=ma+b=m
ערך MM של פונקציית המטרה בקדקוד שעל הישרמבטאים את שיעורי הקדקוד בעזרת mm, מציבים בפונקציית המטרה ומשווים ל-MM
דרך הפתרון

מציאת פרמטר באילוץ

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

1. רושמים את מערכת האילוצים עם הפרמטר.

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

3. מתרגמים את הנתון למשוואה ליניארית עם הפרמטר.

4. פותרים ומוצאים את הפרמטר.

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

שים לב

צורת התחום תלויה בערך של mm. למשל באילוצים y≤8y\le8, x+y≤mx+y\le m, x≥0x\ge0, y≥0y\ge0 הקדקוד (m−8,8)(m-8,8) נמצא בתחום ושונה מ-(0,8)(0,8) רק כש-m>8m>8.

שים לב

באילוץ "לכל היותר mm" (≤m\le m), כש-mm גדל התחום האפשרי לא קטן: כל נקודה שהייתה בתחום נשארת בו, ולפעמים נוספות נקודות.

דוגמה א - קדקוד ידוע על הישר שבו הפרמטר

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

נסמן ב-xx את מספר השולחנות וב-yy את מספר הכיסאות. התחום האפשרי מתואר בסרטוט. הקדקוד BB, שבו נפגשים הישרים של שני האילוצים, הוא B(6,8)B(6,8).

4812481216AB(6,8)C

א. רשמו את מערכת האילוצים בעזרת mm.

ב. מצאו את mm.

ג. הרווח משולחן הוא 3030 ₪ ומכיסא 2020 ₪. כמה שולחנות וכמה כיסאות צריך לייצר ביום כדי שהרווח יהיה מקסימלי? מהו הרווח המקסימלי?

פתרון

1. נתון: לכל היותר mm פריטים ו-2020 לוחות ביום, הקדקוד B(6,8)B(6,8). המטרה: mm והייצור שנותן רווח מקסימלי.

2. א. x+y≤mx+y\le m, 2x+y≤202x+y\le20, x≥0x\ge0, y≥0y\ge0.

3. ב. BB נמצא על הישר x+y=mx+y=m. מציבים: 6+8=m6+8=m, ולכן m=14m=14. בדיקה: BB גם על הישר השני, 2⋅6+8=202\cdot6+8=20.

4. ג. הקדקודים: O(0,0)O(0,0); AA על ציר ה-xx: 2x=202x=20, ולכן A(10,0)A(10,0); CC על ציר ה-yy: y=14y=14, ולכן C(0,14)C(0,14); ו-B(6,8)B(6,8).

5. פונקציית המטרה f(x,y)=30x+20yf(x,y)=30x+20y: f(O)=0f(O)=0, f(A)=300f(A)=300, f(B)=340f(B)=340, f(C)=280f(C)=280. המקסימום ב-BB.

תשובה

א. x+y≤mx+y\le m, 2x+y≤202x+y\le20, x≥0x\ge0, y≥0y\ge0. ב. m=14m=14. ג. 66 שולחנות ו-88 כיסאות, רווח מקסימלי 340340 ₪.

דוגמה ב - רווח מקסימלי נתון: קדקוד בעזרת הפרמטר

חנות מכינה מארזים קטנים ומארזים גדולים. ביום אחד אפשר להכין לכל היותר 88 מארזים גדולים, ובסך הכול לכל היותר mm מארזים (m>8m>8). הרווח ממארז קטן הוא 3030 ₪, והרווח ממארז גדול הוא 5050 ₪.

נסמן ב-xx את מספר המארזים הקטנים וב-yy את מספר המארזים הגדולים.

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

ב. הביעו בעזרת mm את שיעורי הקדקודים של התחום האפשרי.

ג. ידוע שהרווח המקסימלי ביום הוא 760760 ₪. מצאו את mm.

ד. כמה מארזים מכל סוג צריך להכין כדי לקבל את הרווח המקסימלי?

פתרון

1. נתון: לכל היותר 88 מארזים גדולים ולכל היותר mm מארזים בסך הכול, הרווחים 3030 ₪ ו-5050 ₪, הרווח המקסימלי 760760 ₪. המטרה: mm והייצור שנותן את הרווח המקסימלי.

2. א. y≤8y\le8, x+y≤mx+y\le m, x≥0x\ge0, y≥0y\ge0. פונקציית המטרה: f(x,y)=30x+50yf(x,y)=30x+50y.

3. ב. O(0,0)O(0,0). AA: y=0y=0 ו-x+y=mx+y=m, ולכן A(m,0)A(m,0). BB: y=8y=8 ו-x+y=mx+y=m, ולכן x=m−8x=m-8: B(m−8,8)B(m-8,8). CC: x=0x=0 ו-y=8y=8: C(0,8)C(0,8).

4. ג. הערכים בקדקודים: f(O)=0f(O)=0, f(A)=30mf(A)=30m, f(B)=30(m−8)+400=30m+160f(B)=30(m-8)+400=30m+160, f(C)=400f(C)=400. תמיד 30m+160>30m30m+160>30m, וכש-m>8m>8 גם 30m+160>40030m+160>400. לכן המקסימום ב-BB.

5. משווים: 30m+160=76030m+160=760, ולכן 30m=60030m=600 ו-m=20m=20.

6. ד. B(20−8,8)=B(12,8)B(20-8,8)=B(12,8). בדיקה: f(A)=f(20,0)=600f(A)=f(20,0)=600, f(B)=760f(B)=760, f(C)=400f(C)=400.

4812162024369AB(12,8)C(0,8)
תשובה

א. y≤8y\le8, x+y≤mx+y\le m, x≥0x\ge0, y≥0y\ge0; f(x,y)=30x+50yf(x,y)=30x+50y. ב. O(0,0)O(0,0), A(m,0)A(m,0), B(m−8,8)B(m-8,8), C(0,8)C(0,8). ג. m=20m=20. ד. 1212 מארזים קטנים ו-88 גדולים.

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

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

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

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