שיטת Gomory. הפתרון של בעיות תכנות בשלמים

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

השימושים העיקריים של בעיות עם משתנה, מספר שלם, הוא אופטימיזציה. שיטה המשתמשת שלם תכנות לינארי, המכונה גם שיטת חתוכים.

שיטת Gomory היה שמו של המתמטיקאי, שפותחה לראשונה אלגוריתם 1957-1958 עדיין בשימוש נרחב כדי לפתור בעיות תכנות לינארי שלם. הצורה הקנונית של בעית תכנות השלם מאפשרת נגישה במלואם לחשוף את היתרונות של שיטה זו.

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

כדי להצדיק את האלגוריתמים המספריים לפתרון בעיות יש צורך לבצע חפיפה נוספת של תנאים שונים.

בשיטת Gomory, בדרך כלל לשקול תוכניות רבות עבור הבעיה כביכול של פתרונות פאון מוגבלים. על בסיס זה, את הסט של כל התכנית האינטגרלית יש ערך מוגבל למשימה.

כמו כן, עבור פונקצית אחריות אינטגרלית להניח כי הערכים של המקדמים הם גם מספרים שלמים. למרות חומרת התנאים הללו, חלש שבניהולם כמה.

שיטת Gomory בעצם כרוכה הגבלות בנייה, אשר חתכו פתרונות שאינם nonintegral. במקרה זה, אין חתוכים שום תכנית פתרונות שלמים.

האלגוריתם לפתרון הבעיה כרוך במציאת פתרונות הולמים שיטת סימפלקס, מבלי לקחת בחשבון את התנאים של integrality. אם כל המרכיבים של התכנית אופטימלית מכילים החלטות הקשורות מספרים שלמים, ניתן להניח כי מטרת תכנות השלם מושגת. אולי כי הוא נמצא insolubility של הבעיה, ולכן יש לנו הוכחה שהבעיה תכנות בשלמים אין פתרון.

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

כאשר מגבלות בבנייה יש לבחור רכיב של תכנית אופטימלית עם השבר הגבוה ביותר. זוהי מגבלה זו תתווסף השולחן סימפלקס הקיים.

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

לאחר שביצע מספר סופי של איטרציות, אנו להשיג תוכנית אופטימלית לבעיה המוצגת מול התכנות שלם, או להוכיח insolubility של הבעיה.