|
|
עמוד:7
הבעיה שהצגנו היא דוגמה לבעיית החלטה . בבעיה מסוג זה יש לבחור משתני החלטה שיקיימו את כל האילוצים , ויביאו לאופטימוס את פונקציית המטרה . כלומר , יש לבחור פתרון אפשרי אופטימלי . שאלה 1 . 2 מצאו את ערך פונקציית המטרה Z עבור נקודות אלה ו X = 320-1 X y = 420 ( נקודת המפגש בין שני הישרים המייצגים את האילוצים ) בתכנון ליניארי כל קבוצת ערכים של משתני החלטה תיקרא פתרון , גם אם אינה עונה על אילוצי הבעיה . בתכנון ליניארי אנו מבחינים בין סוגים שונים של פתרונות , כמפורט להלן . פתרון אפשרי ( feasible solution ) הוא פתרון המקיים את כל אילוצי הבעיה . הפתרון האפשרי שהוצג באיור 1 . 1 הוא . X , = 500-1 X = 150 ואילו A ' , = 0 Nin X = 800-ו פתרון שאינו אפשרי . אוסף כל הפתרונות האפשריים נקרא התחום האפשרי או תחום הפתרונות האפשרי . באיור 1 . 1 התחום האפשרי הוא התחום המקווקו . פתרון אופטימלי ( optimal solution ) הוא פתרון אפשרי הנותן את הערך הטוב ביותר לפונקציית המטרה . כלומר , פתרון אופטימלי נותן את הערך הקטן ביותר עבור בעיית מינימום , או את הערך הגדול ביותר עבור בעיית מקסימום . בדוגמה שראינו , הפתרון האופטימלי התקבל בקודקוד של התחום האפשרי . תופעה זו של פתרון אופטימלי בקודקוד אינה מקרית , והיא נובעת מהסיבה הזו ו כאשר יש למצוא נקודת מינימום או נקודת מקסימום של פונקציית מטרה ליניארית , ככל שנתקדם בכיוון העלייה של הפונקציה או בכיוון הירידה שלה , נקבל פתרון טוב יותר . תחום הפתרונות האפשריים מגביל את התקדמותנו בכיוון העלייה או הירידה , לכן ברור שנשאף להתקדם אל הנקודה האחרונה האפשרית , הנמצאת כמובן על שפת התחום האפשרי . מהדוגמה של מפעל הגבינות ניתן להכליל ולהסיק את המסקנה הזו ;
|
|