|
|
עמוד:79
ב . השלב האיטרטיבי . 1 מבחן האופטימליות כדי לקבוע אם הפתרון הנוכחי אופטימלי , בדוק אם קייס משתנה לא-בסיסי שהגדלתו תגדיל את ערך פונקציית המטרה Z ניתן לעשות זאת על-ידי בדיקת הסימן של מקדמיהם של כל המשתנים הלא-בסיסיים בפונקציית המטרה . אם כל המקדמים שליליים , אזי הפתרון הנוכחי אופטימלי , ויש לעצור . אחרת , יש לחזור לשלב האיטרטיבי . . 2 מציאת פתרון בסיסי אפשרי חדש : 2 . 1 קבע מהו המשתנה הנכנס לבסיס : בחר את המשתנה הלא-בסיסי , שהגדלת ערכו תגדיל את Z בשיעור הרב ביותר . לשם כך , השתמש במשוואת פונקציית המטרה הנוכחית , שבה מבוטא Z באמצעות המשתנים הלא-בסיסיים בלבד , ובחר את המשתנה הלא-בסיסי בעל המקדם החיובי הגדול ביותר . : 2 . 2 קבע מהו המשתנה היוצא מהבסיס : בחר את המשתנה הבסיסי שמתאפס ראשון כתוצאה מהגדלת ערכו של המשתנה הנכנס לבסיס . מאחר שכל אחד מהמשתנים הבסיסיים מופיע רק במשוואה אחת , קל לבדוק מתי יתאפס המשתנה הבסיסי הנדון כתוצאה מהגדלת ערכו של המשתנה הנכנס לבסיס . לאחר מכן , יש למצוא את המשוואה שבה מתקבל הערך הקטן ביותר של החסם העליון . המשתנה הבסיסי המופיע באותה משוואה הוא המשתנה היוצא מהבסיס . : 2 . 3 חישוב הפתרון הבסיסי האפשרי החדש : באמצעות הבאת מערכת המשוואות לצורה קנונית , פתור את מערכת המשוואות הנוכחית עבור המשתנים הבסיסיים ועבור , Z המבוטא במונחים של המשתנים הלא-בסיסיים . אפס את כל המשתנים הלא-בסיסיים ; ערכו של כל משתנה בסיסי וכן של Z שווה לערך הנמצא באגף ימין במשוואה שבה הוא מופיע ( עם מקדם . ( + 1 קביעת הפתרון הבסיסי החדש אינה נכללת בחומר הלימוד של הקורס . שאלה 2 . 15 נתונה בעיית התכנון הליניארי שלהלן : Maximum Z = aX + 2 . ^ 2
|
|