4. שיטת הסימפלקס - "The "Simplex Method

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