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