|
|
עמוד:104
שאלה 3 . 12 א . כמה פעמים אפשר להפעיל את התהליך האיטרטיבי הזה ? ב . בטבלה שלהלן מפורטים נתוני בעיית תובלה מסוימת ונתון פתרון לא-בסיסי ( עם 4 משתנים בסיסיים במקום . ( 3 הביאו את הפתרון לפתרון בסיסי . כלומר , הראו כיצד ניתן לוותר על אחד המשתנים ( על-ידי הבאתו לערך אפס ) באמצעות התהליך האיטרטיבי לעיל . 3 . 2 . 3 תכונת הפתרונות השלמים הפתרון האופטימלי של בעיית תכנון ליניארי עשוי להכיל ערכים לא שלמים עבור משתני ההחלטה ( לדוגמה * 12 = 3- וכיו"ב . ( בבעיית תובלה אי-אפשר להרשות זאת שכן ההקצאות אמורות להיות שלמות ( בדוגמה של חברת "גלידות , 'אביבי למשל , כל יחידת הקצאה היא ארגז קירור אחד , ולא 3— ארגזים , וכדומה . ( הוספת האילוץ *•? " שלמים" לניסוח הבעיה מסווגת אותה כ '' בעיית תכנון ליניארי בשלמים . '' קבוצה זו של בעיות ( בעיות תכנון ליניארי , שלהן נדרשים פתרונות שלמים ) שייכת למחלקת הסיבוביות NP ( שלהן לא נמצא עד כה פתרון בזמן סביר , כמו בעיית הסוכן הנוסע , מציאת מעגל המילטון , צביעת מפה בשלושה צבעים ועוד . ( כיוון שבבעיית התובלה ההקצאות צריכות להיות שלמות , יכולנו להימצא בבעיה חמורה . למזלנו , התבנית של הבעיה מבטיחה כי עבור עלויות ( c tp שלמות , ועבור היצעים dr
|
|