|
|
עמוד:115
כפי שראינו , כדי לבדוק אופטימליות בשיטת הסימפלקס ( פרק , ( 2 יש "לאפס" את מחירי המשתנים הבסיסיים בפונקציית המטרה . איפוס מחירי המשתנים הבסיסיים בבעיות תובלה ייעשה על-ידי הפחתת הערך u { ( ערך קבוע המתאים לצורך איפוס מחירי המשתנים הבסיסיים . אופן החישוב של ערך זה יוסבר בהמשך ) מכל המחירים בשורה , והפחתת הערך p מכל המחירים בשורה j באופן שיתקבל c tj - u - v ? = 0 עבור כל משתנה בסיסי . את ערכי , •» v ^ נקבל על-ידי פתירת מערכת המשוואות י- , = 0 c - « - , - 1 עבור כל / ^ ^ -ו שעבורס x הוא משתנה בסיסי . ^ עבור כל משתנה לא-בסיסי נחשב את המחיר החדש ו ז על-ידי הפחתת « , של השורה שבה הוא נמצא והפחתת י של העמודה שבה הוא נמצא . כלומר , נחשב עבור כל משתנה לאבסיסי את ערך הביטוי ' , י H < - « , - ואם יימצא משתנה לא-בסיסי שערך זה ( מחירו החדש ) יהיה שלילי , אז ניתן להוסיפו כמשתנה בסיסי לפתרון , ולהוציא משתנה אחר במקומו . כלומר הפתרון הנוכחי אינו אופטימלי . המסקנה היא , שהנתונים היחידים הדרושים בשיטת הסימפלקס לתובלה , פרט לנתוני הקלט ( ערכי mr s ? , , c tj הס הפתרון הבסיסי האפשרי הנוכחי , הערכים הנוכחיים של « , my 1 ' -ו והערכים של ( .. V y cp ^ Da ^ n cp 3 n \ yDn ( c" - « - , - > ' בזמן פתירת בעיה בחישוב ידני , נוח לרשום את המידע הזה בכל איטרציה בטבלת הסימפלקס לתובלה , כמתואר בטבלה . 3 . 13 כזכור , הפתרון הבסיסי ההתחלתי ( שקיבלנו בשיטת הפינה הצפונית-מערבית ) מופיע בטבלה . 3 . 9 פתרון זה כולל את המשתנים : ! 1 = 230 , 000 , y * , OOO . OdS % 22 = 260 , 000 , * 23 = 220 , 000 A כאשר מחוץ לבסיס נמצאים המשתנים , , x ? . וערכם הוא . 0 * 12 ]? 1
|
|