תזכורת: בעיית תכנון ליניארי
בבעיית תכנון ליניארי יש שני משתנים, ו- (למשל מספר המוצרים מכל סוג), ותנאים שהם חייבים לקיים. התנאים האלה הם מערכת האילוצים, והם נכתבים כאי-שוויונות. הגודל שרוצים להגדיל או להקטין (רווח, הכנסה, הוצאה) נקרא פונקציית המטרה, למשל .
במדויק: התחום האפשרי הוא קבוצת כל הנקודות שמקיימות את כל האילוצים. פונקציית המטרה היא פונקציה ממעלה ראשונה בשני משתנים, . כשהתחום האפשרי סגור (מצולע), הערך המקסימלי והערך המינימלי של בתחום מתקבלים כל אחד לפחות בקדקוד אחד של התחום. לכן מציבים את שיעורי כל הקדקודים בפונקציית המטרה ומשווים בין הערכים.
בתחום שבסרטוט האילוצים הם , , , . הקדקודים הם , , ו-. הקדקוד הוא נקודת החיתוך של הישרים ו-.
עבור :
הערך המקסימלי הוא , בקדקוד . הערך המינימלי הוא , בקדקוד .
פרמטר
לפעמים חסר בשאלה נתון אחד: הרווח ממוצר מסוים, או מספר הפריטים שאפשר לייצר. במקום מספר כותבים אות, למשל או . האות הזאת נקראת פרמטר.
במדויק: פרמטר הוא מספר קבוע שאינו ידוע, ומסמנים אותו באות. בניגוד ל- ול-, שמשתנים מנקודה לנקודה בתחום, לפרמטר יש ערך אחד בכל השאלה. כדי למצוא אותו משתמשים בנתון נוסף מהשאלה: רושמים משוואה ליניארית (או מערכת משוואות) שבה הפרמטר הוא הנעלם, ופותרים.
בנושא הזה הפרמטר מופיע באחד משני מקומות:
1. פרמטר בפונקציית המטרה: מציאתו מערך מקסימום או מינימום נתון
פרמטר בפונקציית המטרה
נניח שהרווח מעוגת שוקולד ידוע, ₪, אבל הרווח מעוגת גבינה לא ידוע. מסמנים אותו ב-, ופונקציית המטרה היא . אם השאלה נותנת את הרווח המקסימלי, אפשר למצוא את .
במדויק: כשפונקציית המטרה מכילה פרמטר והתחום האפשרי סגור, הנתון "הערך המקסימלי של בתחום הוא " אומר שני דברים: יש קדקוד שבו , ובכל שאר הקדקודים . הנתון "הערך המינימלי הוא " אומר: יש קדקוד שבו , ובכל שאר הקדקודים .
הפרמטר בפונקציית המטרה לא משנה את התחום האפשרי, כי האילוצים לא תלויים בו. הוא משנה את הערכים בקדקודים, ולכן גם הקדקוד שבו מתקבל המקסימום יכול להשתנות. למשל בתחום שקדקודיו , , , , עם :
לכן אחרי שמוצאים את תמיד בודקים שהמקסימום באמת מתקבל בקדקוד שבו השתמשנו.
מציאת הפרמטר מערך מקסימלי או מינימלי נתון
כשנתון הערך המקסימלי (או המינימלי) של פונקציית המטרה, ונתון באיזה קדקוד הוא מתקבל:
1. מוצאים את שיעורי הקדקוד: פותרים את מערכת המשוואות של שני הישרים שנפגשים בו.
2. מציבים את השיעורים בפונקציית המטרה ומשווים ל-.
3. פותרים את המשוואה הליניארית ומוצאים את הפרמטר.
4. בודקים: מציבים את הפרמטר ומחשבים את בכל הקדקודים. צריך להיות הערך הגדול ביותר (במקסימום) או הקטן ביותר (במינימום).
אחרי שמצאתם את הפרמטר, כתבו את פונקציית המטרה המלאה, למשל , ורק אז ענו על שאר הסעיפים.
דוגמה - רווח מקסימלי נתון בקדקוד ידוע
מאפייה מכינה בכל יום עוגות גבינה ועוגות שוקולד. ביום אחד אפשר להכין לכל היותר עוגות. לעוגת גבינה צריך כוסות קמח, ולעוגת שוקולד כוס קמח אחת. במאפייה יש לכל היותר כוסות קמח ביום.
נסמן ב- את מספר עוגות הגבינה וב- את מספר עוגות השוקולד. הרווח מעוגת שוקולד הוא ₪, והרווח מעוגת גבינה הוא ₪. התחום האפשרי מתואר בסרטוט ( היא ראשית הצירים).
א. רשמו את מערכת האילוצים ואת פונקציית המטרה.
ב. מצאו את שיעורי הקדקודים , ו-.
ג. ידוע שהרווח המקסימלי הוא ₪, והוא מתקבל בקדקוד . מצאו את .
1. נתון: לכל היותר עוגות ולכל היותר כוסות קמח ביום. הרווח ₪ מעוגת גבינה ו- ₪ מעוגת שוקולד. הרווח המקסימלי ₪, בקדקוד . המטרה: האילוצים, הקדקודים והפרמטר .
2. א. האילוצים: , , , . פונקציית המטרה: .
3. ב. על ציר ה- (): , ולכן . על ציר ה- (): , ולכן .
4. הוא נקודת החיתוך של ו-. מחסרים את המשוואות: , ולכן ו-. .
5. ג. מציבים את בפונקציית המטרה: . משווים לרווח המקסימלי: , ולכן ו-.
6. בדיקה: עם : , , , . הערך הוא באמת הגדול ביותר.
א. , , , ; . ב. , , . ג. : הרווח מעוגת גבינה ₪.
2. פונקציית מטרה שמקבלת ערך שווה בשני קדקודים
ערך שווה בשני קדקודים
לפעמים פונקציית המטרה מקבלת אותו ערך בשני קדקודים של התחום. אם זה גם הערך המקסימלי, אין פתרון אופטימלי אחד בלבד: יש כמה דרכים להגיע לאותו רווח מקסימלי.
במדויק: אם ו- הם שני קדקודים סמוכים של התחום (שני הקצוות של אותה צלע), ו- הוא הערך המקסימלי (או המינימלי) של בתחום, אז מקבלת את הערך הזה בכל נקודה של הצלע , וכל הנקודות האלה הן פתרונות אופטימליים.
בתחום שקדקודיו , , , , עם : , , . הערך המקסימלי מתקבל בשני הקדקודים ו-, וגם בכל נקודה של הצלע (על הישר ). למשל הנקודה , שמסומנת על הצלע: .
מציאת הפרמטר מערך שווה בשני קדקודים
כשנתון שפונקציית המטרה (עם פרמטר) מקבלת ערך שווה בשני קדקודים ו-:
1. מוצאים את שיעורי ואת שיעורי .
2. מציבים כל קדקוד בפונקציית המטרה. מקבלים שני ביטויים עם הפרמטר.
3. משווים: , ופותרים את המשוואה הליניארית.
4. מציבים את הפרמטר ומחשבים את הערך המשותף.
5. אם נאמר שזה הערך המקסימלי (או המינימלי), בודקים שבשאר הקדקודים הערך לא גדול ממנו (או לא קטן ממנו).
כל הנקודות על הצלע
אם הערך השווה בקדקודים הסמוכים ו- הוא הערך המקסימלי, כל נקודה על הצלע נותנת את אותו ערך מקסימלי. כש- ו- הם מספרי פריטים, הפתרונות הם הנקודות על הצלע ששני השיעורים שלהן מספרים שלמים.
כדי לבדוק אם נקודה נמצאת על הצלע : מציבים אותה במשוואת הישר של הצלע, ובודקים שהשיעורים שלה נמצאים בין השיעורים של ושל .
השוויון לבד לא אומר שזה הערך המקסימלי. אם השאלה שואלת על מקסימום, בודקים גם את שאר הקדקודים.
דוגמה - רווח מקסימלי שווה בשני קדקודים סמוכים
מפעל מייצר שני סוגי מוצרים, א ו-ב. ביום אחד אפשר לייצר לכל היותר מוצרים. מוצר א צריך שעה אחת במכונה I ו- שעות במכונה II. מוצר ב צריך שעות במכונה I ושעה אחת במכונה II. מכונה I עובדת לכל היותר שעות ביום, ומכונה II לכל היותר שעות ביום.
נסמן ב- את מספר המוצרים מסוג א וב- את מספר המוצרים מסוג ב. האילוצים הם , , , , , והתחום האפשרי מתואר בסרטוט.
הרווח ממוצר א הוא ₪, והרווח ממוצר ב הוא ₪.
א. מצאו את שיעורי הקדקודים , , ו-.
ב. ידוע שבקדקודים ו- מתקבל אותו רווח, והוא הרווח המקסימלי. מצאו את .
ג. מהו הרווח המקסימלי?
ד. מצאו את כל האפשרויות לייצור יומי (מספרים שלמים של מוצרים) שנותנות את הרווח המקסימלי.
1. נתון: האילוצים, פונקציית המטרה , ו- הוא הרווח המקסימלי. המטרה: , הרווח המקסימלי וכל האפשרויות שנותנות אותו.
2. א. : ו-, ולכן . : ו-, ולכן .
3. הוא החיתוך של ו-. מחסרים: , ולכן : .
4. הוא החיתוך של ו-. מחסרים: , ולכן ו-: .
5. ב. ו-. משווים: , ולכן ו-.
6. ג. עם : . בדיקה: , , , כולם קטנים מ-. הרווח המקסימלי ₪.
7. ד. הרווח המקסימלי מתקבל בכל נקודה של הצלע , כלומר על הישר עם . הנקודות עם שיעורים שלמים: , , , .
א. , , , . ב. . ג. ₪. ד. מוצרי א ו- מוצרי ב, ו-, ו-, או ו-.
3. פרמטר באחד האילוצים
פרמטר באחד האילוצים
לפעמים הפרמטר נמצא באילוץ: למשל "ביום אחד אפשר לייצר לכל היותר פריטים", כלומר . כש- משתנה, הישר זז, ואיתו משתנים התחום האפשרי והקדקודים שלו.
במדויק: בשיעור הזה הפרמטר הוא המספר באגף הימני של אילוץ, כמו ב-. המקדמים של ושל קבועים, ולכן הישרים עבור ערכים שונים של מקבילים זה לזה. הקדקודים שנמצאים על הישר הזה תלויים ב-, והקדקודים האחרים לא.
בסרטוט האילוצים הם , , ו-. התחום הצבוע מתאים ל-, והישר המקווקו הוא . עבור הקדקוד שבו נפגשים ו- הוא , ועבור הוא . הקדקוד , על הישר , לא משתנה.
מה נתון ואיזו משוואה רושמים
מציאת פרמטר באילוץ
כשאחד האילוצים מכיל פרמטר, ונתון עוד מידע על התחום או על פונקציית המטרה:
1. רושמים את מערכת האילוצים עם הפרמטר.
2. מוצאים את שיעורי הקדקודים. קדקוד על הישר עם הפרמטר מוצאים בעזרת הפרמטר (פותרים את מערכת המשוואות של שני הישרים).
3. מתרגמים את הנתון למשוואה ליניארית עם הפרמטר.
4. פותרים ומוצאים את הפרמטר.
5. מציבים את הפרמטר בחזרה ובודקים שהתחום והקדקודים מתאימים לנתוני השאלה.
צורת התחום תלויה בערך של . למשל באילוצים , , , הקדקוד נמצא בתחום ושונה מ- רק כש-.
באילוץ "לכל היותר " (), כש- גדל התחום האפשרי לא קטן: כל נקודה שהייתה בתחום נשארת בו, ולפעמים נוספות נקודות.
דוגמה א - קדקוד ידוע על הישר שבו הפרמטר
בנגרייה מייצרים שולחנות וכיסאות. ביום אחד אפשר לייצר לכל היותר פריטים. לשולחן צריך לוחות עץ ולכיסא לוח אחד, ובנגרייה יש לכל היותר לוחות ביום.
נסמן ב- את מספר השולחנות וב- את מספר הכיסאות. התחום האפשרי מתואר בסרטוט. הקדקוד , שבו נפגשים הישרים של שני האילוצים, הוא .
א. רשמו את מערכת האילוצים בעזרת .
ב. מצאו את .
ג. הרווח משולחן הוא ₪ ומכיסא ₪. כמה שולחנות וכמה כיסאות צריך לייצר ביום כדי שהרווח יהיה מקסימלי? מהו הרווח המקסימלי?
1. נתון: לכל היותר פריטים ו- לוחות ביום, הקדקוד . המטרה: והייצור שנותן רווח מקסימלי.
2. א. , , , .
3. ב. נמצא על הישר . מציבים: , ולכן . בדיקה: גם על הישר השני, .
4. ג. הקדקודים: ; על ציר ה-: , ולכן ; על ציר ה-: , ולכן ; ו-.
5. פונקציית המטרה : , , , . המקסימום ב-.
א. , , , . ב. . ג. שולחנות ו- כיסאות, רווח מקסימלי ₪.
דוגמה ב - רווח מקסימלי נתון: קדקוד בעזרת הפרמטר
חנות מכינה מארזים קטנים ומארזים גדולים. ביום אחד אפשר להכין לכל היותר מארזים גדולים, ובסך הכול לכל היותר מארזים (). הרווח ממארז קטן הוא ₪, והרווח ממארז גדול הוא ₪.
נסמן ב- את מספר המארזים הקטנים וב- את מספר המארזים הגדולים.
א. רשמו את מערכת האילוצים ואת פונקציית המטרה.
ב. הביעו בעזרת את שיעורי הקדקודים של התחום האפשרי.
ג. ידוע שהרווח המקסימלי ביום הוא ₪. מצאו את .
ד. כמה מארזים מכל סוג צריך להכין כדי לקבל את הרווח המקסימלי?
1. נתון: לכל היותר מארזים גדולים ולכל היותר מארזים בסך הכול, הרווחים ₪ ו- ₪, הרווח המקסימלי ₪. המטרה: והייצור שנותן את הרווח המקסימלי.
2. א. , , , . פונקציית המטרה: .
3. ב. . : ו-, ולכן . : ו-, ולכן : . : ו-: .
4. ג. הערכים בקדקודים: , , , . תמיד , וכש- גם . לכן המקסימום ב-.
5. משווים: , ולכן ו-.
6. ד. . בדיקה: , , .
א. , , , ; . ב. , , , . ג. . ד. מארזים קטנים ו- גדולים.