סביבת ניסוי לתכנון בשלמים
פתרו תוכנית ליניארית קטנה בשלמים באמצעות ענף־וחסם מדויק וראו כל צומת בחיפוש. הנקודה הטובה ביותר מדווחת כאופטימלית מוכחת רק לאחר בחינת העץ כולו.
תוכניות מוגבלות ל־4,000 תווים ול־40 שורות, ל־8 משתנים ול־8 אילוצים עם שני משתנים או יותר; מגבלת הצמתים היא 1 עד 5,000, והחיפוש נעצר גם לאחר 3,000,000 צעדי חשבון מדויק. הכול מחושב במכשירכם בתהליך רקע, עם מגבלת זמן של 15 שניות. ניתן להוריד דוח JSON וקובץ CSV של הצמתים. בשורה הראשונה כתבו maximize או minimize ואת פונקציית המטרה. אחר כך כתבו אילוץ אחד בכל שורה. עד 4,000 תווים. בדקו את ההגדרות לפני ההרצה.
התוצאה שלכם
סביבת ניסוי לתכנון בשלמים
- כתבו בשורה הראשונה את פונקציית המטרה, כגון maximize 5x + 4y.
- הוסיפו אילוץ אחד בכל שורה, גבולות כגון x, y >= 0, ואם רוצים שורות כגון integer x או binary z.
- קבעו את מגבלת הצמתים והריצו את החיפוש.
- קראו את המצב, את הפתרון המוביל הנוכחי, את החסם הטוב ביותר ואת הפער, ואז הורידו את דוח JSON או את קובץ ה־CSV של הצמתים.
מה צפוי לקרות
תוכניות מוגבלות ל־4,000 תווים ול־40 שורות, ל־8 משתנים ול־8 אילוצים עם שני משתנים או יותר; מגבלת הצמתים היא 1 עד 5,000, והחיפוש נעצר גם לאחר 3,000,000 צעדי חשבון מדויק. הכול מחושב במכשירכם בתהליך רקע, עם מגבלת זמן של 15 שניות. ניתן להוריד דוח JSON וקובץ CSV של הצמתים.
ענף וחסם
כל צומת פותר במדויק את ההרפיה הליניארית בשיטת הסימפלקס. משתנה שלם בעל ערך שברי מתפצל לשני ענפים, x <= floor ו־x >= ceiling. צמתים נחתכים אם ההרפיה שלהם אינה אפשרית או אינה יכולה לשפר את נקודת המספרים השלמים הטובה ביותר שנמצאה. השיטה: Wolsey, Integer Programming, מהדורה 2, פרק 7 (2020).
מה פירוש „הוכח”
כאשר כל צומת נפתר או נחתך באמצעות חסם מדויק, מוכח שהפתרון המוביל הנוכחי אופטימלי או שהבעיה אינה אפשרית. אם מגבלת הצמתים או תקציב הצעדים עוצרים את החיפוש קודם, הפתרון המוביל הוא רק הנקודה הטובה ביותר שנמצאה עד כה, והדוח מציג את החסם הטוב ביותר ואת הפער ביניהם.
כללי הקלט
המשתנים שלמים אלא אם מציינים חלק מהם באמצעות integer x, y; במקרה כזה האחרים רציפים. אילוצים עם משתנה יחיד הופכים לחסמים. אם ההרפיה אינה חסומה, החיפוש נעצר, משום שתוכנית השלמים עשויה להיות לא חסומה או בלתי אפשרית.