מחשבון איטרציה של שיטת הסימפלקס

אודות מחשבון זה

שיטת הסימפלקס של דנציג פותרת בעיות תכנות לינארי על ידי הליכה לאורך קודקודי הפוליטופ של התחום האפשרי, תוך שיפור ערך פונקציית המטרה בכל צעד עד שאין שיפור נוסף. איטרציית ציר אחת על הטבלה מורכבת מבחירת המשתנה הנכנס (בדרך כלל העמודה בעלת המקדם השלילי ביותר בשורת המטרה, בבעיית מקסום) והמשתנה היוצא (הנמצא באמצעות מבחן היחס המינימלי על עמודת האגף הימני, כדי לשמור על כל הערכים אפשריים), ואז ביצוע חיסור גאוס-ז'ורדן סביב איבר הציר הזה.

המחשבון מקבל טבלת סימפלקס — כשפונקציית המטרה בשורה האחרונה וערכי האגף הימני בעמודה האחרונה — ומבצע צעד ציר אחד בדיוק, ומחזיר את הטבלה המעודכנת כדי שתוכלו לראות במפורש את בחירת המשתנה הנכנס והיוצא ואת החישוב. תלמידי חקר ביצועים ותכנות לינארי משתמשים בו כדי לבדוק איטרציה אחת שנעשתה ביד מתוך בעיית סימפלקס גדולה יותר, ולא בפותר שקופץ ישר לפתרון האופטימלי.