|
|
עמוד:106
3 . 3 . 1 שלב האתחול ( מציאת פתחן בסיסי אפשרי ) נציג תחילה שיטה פשוטה למציאת פתרון בסיסי התחלי ( המכיל m + n- \ משתנים ) העונים על האילוצים . שיטה זו נקראת שיטת הפינה הצפונית-מערבית . שיטה זו פשוטה עד מאוד , ובזה יתרונה . אולם כיוון שהשיטה אינה עושה כל שימוש בעלויות התובלה , הפתרון הבסיסי המתקבל עשוי להיות רחוק מן הפתרון האופטימלי , ואז יידרשו איטרציות נוספות כדי להגיע לפתרון האופטימלי . קיימות שיטות נוספות למציאת פתרון בסיסי התחלתי המביאות לפתרון התחלתי משופר ( זאת אומרת למחיר תובלה זול יותר ) והן ? . שיטת המיויר המינימלי ושיטת הקירוב של ווגל . הפתרון ששיטות אלו משיגות הוא אמנם משופר ביחס לשיטת הפינה הצפוניתמערבית , אך עדיין אינו אופטימלי . לא נציג שיטות אלו בספר זה . בהליך לבניית פתרון בסיסי אפשרי התחלתי בוחרים את « + « -1 המשתנים בזה אחר זה . לאחר כל בחירה , נותנים למשתנה שנבחר ערך שיקיים אילוץ אחד נוסף ( ועל-ידי כך מבטלים את אילוץ השורה או העמודה , כך שלא נבחן אותן עוד בקשר להקצאות . ( לאחר m + n-1 בחירות , יש בידינו פתרון בסיסי שלם שנבנה כך שיקיים את כל האילוצים . כדי להכיר וללמוד את השיטה , נשוב אל טבלה , 3 . 1 המציגה את בעיית התובלה בחברת " גלידות אביב" ( ללא העלויות ( c ?? בעזרת טבלה ריקה ( ללא הקצאות . ( טבלה 3 . 6 שיטת הפינה הצפונית-מערבית - מצב התחלתי
|
|