|
|
עמוד:66
כזכור , בסעיף הקודם הגענו למסקנה כי הפתרונות האופטימליים של בעיית תכנון ליניארי ( שהתחום האפשרי שלה חסום ) נמצאים על קדקוד אחד או על שני קדקודים סמוכים ( הנמצאים על אותה צלע ) של תחום הפתרונות האפשריים . לכן הפתרון האופטימלי יימצא באחד ( או בשניים ) מארבעת פתרונות הקדקוד שבתחום האפשרי ! קדקוד אופטימלי ( optimal vertex ) הוא קדקוד שמהווה פתרון אופטימלי לבעיית התכנון הליניארי . שלוש תכונות היסוד של שיטת הסימפלקס מסוכמות להלן ו 1 א . אם לבעיה יש פתרון אופטימלי יחיד , אזי הוא חייב להיות פתרון קדקוד אפשרי . 1 ב . אם לבעיה פתרונות אופטימליים רבים , אז לפחות שניים מהם חייבים להיות פתרונות אפשריים סמוכים ( קדקודים הנמצאים על אותה צלע . ( . 2 מספר הקדקודים האפשריים הוא סופי . . 3 אם לפתרון קדקוד אפשרי אין פתרונות קדקוד אפשריים סמוכים שהם טובים ממנו ( כפי שנמדד על-ידי פונקציית המטרה , ( Z אזי אין כלל פתרון אחר טוב ממנו ; כלומר פתרון הקדקוד האפשרי במקרה זה הוא אופטימלי . תכונה 1 הוסברה בסעיף הקודם . תכונה 2 נובעת מן העובדה , כי , ככלל , כאשר לפנינו בעיה בעלת m אילוצים על משתני ההחלטה /! -ו משתני החלטה , אזי מספר פתרונות הקדקוד הוא ? m \ m ! n ) n \( m-n )\ שהוא מספר סופי . תכונה 3 נובעת מהעובדה שפונקציית המטרה ליניארית , האילוצים ליניאריים ולכן מתקבל תחום אפשרי שצורתו מצולע רב-ממדי קמור ( מצולע רב-ממדי קמור נקרא , "סימפלקס" מכאן שם השיטה . ( הוכחה פורמלית של תכונה 3 נמצאת בספר '' מודלים דטרמינסטיים בחקר ביצועים - כרך א , "' הוצאת האוניברסיטה הפתוחה , סעיף . 5 . 1
|
|