|
|
עמוד:64
2 . 2 שיטת הסימפלקס שיטת הסימפלקס ( The Simplex Method ) היא אלגוריתם לפתרון של בעיות תכנון ליניארי . השיטה מבוססת על הרעיון של סריקה יעילה של קדקודים בתחום הפתרונות האפשריים , עד למציאת הקדקוד בעל הערך האופטימלי , בהתאם להגדרת הבעיה . כאשר הבעיה היא בעיית מקסימום , שיטת הסימפלקס תמצא את הקדקוד בעל הערך המקסימלי עבור פונקציית המטרה , וכאשר הבעיה היא בעיית מינימום , שיטת הסימפלקס תמצא את הקדקוד בעל הערך המינימלי עבור פונקציית המטרה . שיטת הסימפלקס היא אלגוריתם משופר שאינו מצריך בהכרח את סריקת כל הקדקודים , אלא יוצא מקדקוד כלשהו של תחום הפתרונות האפשריים , ומתקדם מקדקוד לקדקוד עד לקדקוד בעל הערך האופטימלי . שיטת הסימפלקס היא בעלת סיבוביות ( ממוצעת ) נמוכה מסיבוכיות הסריקה של כל הקדקודיס . השיטה נחשבת כיום לאחת השיטות היעילות לפתרון בעיות תכנון ליניארי מכל הגדלים . שיטת הסימפלקס היא למעשה אלגוריתם איטרטיבי המבצע סדרת פעולות החוזרות על עצמן , ובכל פעולה האלגוריתם מתקדם מפתרון אפשרי אחד לפתרון אפשרי אחר הנותן לפונקציית המטרה ערך טוב יותר בהתאם לדרישות הבעיה . שיטת הסימפלקס היא אלגוריתם אלגברי שבו כל איטרציה כרוכה בפתרון מערכת משוואות לשם קבלת פתרון חדש שייבחן במבחן האופטימליות . ואולם לשיטה זו יש גם משמעות גיאומטרית . כדי לרענן את זכרוננו , מוצג באיור 2 . 10 הגרף המתאים לבעיה שבדוגמה 2 . 2 לעיל . דוגמה 2 . 6 7 Maximum Z = 5 X ] + 3 X 2 Subject to : 1 . X + X < 2 x 2 2 . X + 2 X < 2 x 2
|
|