|
|
עמוד:42
2 . 1 פתרון גרפי לבעיית תכנון ליניארי בבעיית תכנון ליניארי יש למצוא , בתחום הפתרונות האפשריים , את הנקודה בעלת הערך האופטימלי , שיתקבל על-ידי הצבת נקודה זו בפונקציית המטרה . השלב הראשון בפתרון גרפי של בעיית תכנון ליניארי הוא שרטוט תחום הפתרונות האפשרי . השלב השני הוא מציאת הפתרון האופטימלי . מספר הנקודות בתחום הפתרונות האפשריים הוא בדרך-כלל אינסופי , ומציאת הנקודה בעלת הערך האופטימלי תלויה במבנה תחום הפתרונות האפשריים ובמבנה פונקציית המטרה . . 1 השיטה הגרפית כפי שראינו בפרק הקודם , לא נוכל לבטא בצורה גרפית בעיות החלטה שיש בהן יותר משני משתני החלטה , לכן פתרון בשיטה גרפית מוגבל לבעיות שיש בהן משתנה החלטה אחד או שניים . למרות מוגבלותה , שיטת הפתרון הגרפי תעניק לנו הבנה ברורה יותר של מאפייני הפתרון של בעיית תכנון ליניארית כללית ( עם n משתני החלטה , ( ותעזור לנו להבין , בצורה אינטואיטיבית , את שיטת הפתרון האלגברית . . 2 שיטת הסימפלקס ( שיטה אלגברית ) שיטת הסימפלקס היא שיטה אלגברית כללית לפתרון בעיות תכנון ליניארי . השיטה נחשבת כיום לאחת השיטות הנפוצות לפתרון בעיות תכנון ליניארי מכל הגדלים . שיטת הסימפלקס היא למעשה אלגוריתם המבצע סדרת פעולות החוזרות על עצמן כאשר בכל פעולה האלגוריתם מתקדם מפתרון אפשרי אחד לפתרון אפשרי אחר , הנותן לפונקציית המטרה ערך טוב יותר , בהתאם לדרישות הבעיה . שיטת הסימפלקס מאפשרת לפתור בעיות תכנון לינארי המכילות מספר גדול מאוד של משתני החלטה ; ניתן ליישם אותה בתוכנות מחשב המסייעות לפתרון יעיל של בעיות אלה . בפרק הראשון עסקנו בניסוח מתמטי של הבעיות שהוצגו ; בפרק השני נתמקד בדרך בה פותרים בעיית תכנון ליניארי נ משום כך , רוב הדוגמאות יינתנו בניסוח המתמטי הסופי . אם עדיין אינכם בקיאים בצורה מספקת בשלב המעבר מתיאור הבעיה לניסוחה המתמטי , חיזרו וקראו את הפרק הראשון העוסק בשלב זה .
|
|