|
|
עמוד:105
3 , 3 שיטת סימפלקס מקוצרת לבעיית התובלה בעיית התובלה , כמו כל בעיית תכנון ליניארי אחרת , ניתנת לפתרון בשיטת הסימפלקס . אולם כיוון שלבעיה תבנית ייחודית , אפשר להגיע אל הפתרון ביתר קלות . בסעיף זה נציג גרסה משופרת של שיטת הסימפלקס המתאימה לבעיית התובלה . השיטה המשופרת מבוססת על השלבים הבסיסיים של שיטת הסימפלקס . . 1 צעד האתחול - יש למצוא פתרון בסיסי אפשרי התחלתי . . 2 השלב האיטרטיבי = א . מבחן האופטימליות - דרושה ידיעה של משוואת פונקציית המטרה הנוכחית ( שמתקבלת על-ידי החסרה משורה אפס כפולה מסוימת של שורה אחרת באיטרציה הקודמת . ( אם קיימים מקדמים שליליים של המשתנים הלא-בסיסיים בפונקציית המטרה , אזי הפתרון הנוכחי אינו אופטימלי , ויש לעבור לפתרון בסיסי אחר . אחרת , סיום . ב . המעבר לפתרון בסיסי אחר מורכב משלושת הצעדים שלהלן ו . i בחירת המשתנה הנכנס לבסיס - יש למצוא את המשתנה שהמקדם שלו בפונקציית המטרה הנוכחית הוא השלילי ביותר . . ii קביעת המשתנה היוצא מהבסיס - יש לזהות את המשתנה הבסיסי הראשון שמתאפס עקב הגידול במשתנה הנכנס לבסיס . . iii קביעת הפתרון הבסיסי האפשרי החדש - יש להחסיר כפולות מסוימות של שורה אחת מיתר השותת בטבלת הסימפלקס הנוכחית . ג . חזור למבחן האופטימליות . בסעיפים הבאים נתאר כיצד ניתן לבצע כל שלב ושלב בצורה פשוטה יחסית לשיטת הסימפלקס . וביקושים ( d ) שלמים , גם ההקצאות בפתרון האופטימלי יהיו שלמות . לפיכך אין צורך tj להוסיף את אילוצי השלמות לניסוח הבעיה .
|
|