|
|
עמוד:71
פתרון ב 0 י 0 י אפשרי ( basic feasible solution ) הוא פתרון קדקוד אפשרי מורחב . לפיכך , פתרון הקדקוד האפשרי ( 0 , 1 ) בדוגמה שראינו , שקול לפתרון הבסיסי האפשרי ( 0 , 1 , 1 , 0 ) בצורה המורחבת של הבעיה . שאלה 2 . 11 נתונה בעיית תכנון ליניארי דו-ממדית . א . כמה פתרונות בסיסיים סמוכים ישנם לפתרון בסיסי אפשרי ? ב . כמה פתרונות בסיסיים אפשריים סמוכים ישנם לפתרון בסיסי אפשרי ? פתרון בסיסי ופתרון בסיסי אפשרי הם מונחים מרכזיים בתכנון ליניארי , ולכן יש להבהיר את תכונותיהם האלגבריות . בצורה המורחבת של הבעיה , מספר המשתנים ( 4 ) גדול 2-ב ממספר המשוואות ( 2 ) של האילוצים הפונקציונליים . פירושו של דבר , שבפתרון המערכת קיימות שתי דרגות חופש , ( degrees of freedom ) שכן ניתן לקבוע ערך שרירותי כלשהו לכל שניים מבין המשתנים , ולפתור את שתי המשוואות בשני המשתנים שנותרו . שיטת הסימפלקס קובעת את הערך השרירותי כאפס . בפתרון הנוכחי , המשתנים שערכם נקבע לאפס נקראים משתנים לא-בסיסיים , ( nonbasic variables ) והמשתנים האחרים נקראים משתנים בסיסיים . ( basic variables ) הפתרון שמתקבל נקרא פתרון בסיסי . אם כל המשתנים הבסיסיים הס אי-שליליים ( כלומר מקיימים גם את אילוצי האי-שליליות , ( אזי הפתרון נקרא פתרון בסיסי אפשרי . להדגמת הגדרות אלה נתבונן שנית בפתרון הבסיסי האפשרי . ( 0 , 1 , 1 , 0 ) ניתן לקבל פתרון זה על-ידי בחירת X , ו- # במשתנים הלא-בסיסיים , כלומר המשתנים שיקבלו את הערך 4 אפס . שני פתרונות בסיסיים אפשריים הם סמוכים אם כל משתניהם הלא-בסיסיים זהים מלבד משתנה אחד . פירושו של דבר , שניתן לעבור מפתרון בסיסי אפשרי נוכחי לפתרון בסיסי אפשרי סמוך לו על-ידי הפיכה של משתנה לא-בסיסי אחד למשתנה בסיסי ושל משתנה בסיסי אחד למשתנה לא בסיסי .
|
|