מבוא לפתרונות בסיסיים בהנדסה

אם אתה מהנדס או סטודנט להנדסה, אולי אתה יודע מה זה אומר לבצע אופטימיזציה.

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

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

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

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

פתרונות בסיסיים בתכנות לינארי

הגדרה פורמלית:

פתרון למודל תוכנית ליניארי המורכב מ-m משוואות ב-n משתנים מתקבל על ידי פתרון עבור m משתנים במונחים של המשתנים הנותרים (nm) וקביעת המשתנים (nm) שווה לאפס.

פתרון בסיסי בתכנות ליניארי הוא דרך לפתור בעיית תכנות ליניארי העומדת בדרישות טכניות מסוימות.

בפרט, וקטור x הוא פתרון בסיסי לפוליהדרון אם הוקטורים {ai : xi = 0} בלתי תלויים ליניארית.

המשמעות היא שהעמודות של A שיש להן משתנים xi שאינם אפס אינן תלויות ליניארית.

פתרון בסיסי עם רכיבים לא שליליים נקרא פתרון אפשרי בסיסי (BFS) (BFS).

BFS עומד בכל הכללים המגדירים פולידרון.

כל BFS הוא פינה של הפוליהדרון של פתרונות אפשריים מנקודת מבט גיאומטרית.

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

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

שיטת Simplex היא תהליך איטרטיבי שעובר מ-BFS אחד ל-BFS הבא עד שהוא מוצא את ה-BFS הטוב ביותר.

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

אם אין BFS כזה, אז ה-BFS הנוכחי הוא הטוב ביותר.

מודל תכנות לינארי

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

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

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

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

בנוסף, תוכניות ליניאריות מסוימות דורשות שכל משתני ההחלטה יהיו לא שליליים.

במודלים של תכנות ליניארי, אתה יכול גם להשתמש במשתנים שלמים ומשתנים בינאריים.

למשתנים בינאריים יכול להיות רק ערך של 0 או 1, כך שהם יכולים לקבל רק ערך של 0 או 1.

השיטה הפשוטה

אחת הדרכים הנפוצות ביותר לפתרון בעיות תכנות ליניאריות היא שיטת Simplex.

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

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

כדי להשתמש בשיטת הסימפלקס כדי למצוא את ה-BFS הטוב ביותר, עלינו למצוא בסיס B למטריצת האילוץ A ולפתור את המערכת Ax = b כאשר כל המשתנים מלבד הבסיס מוגדרים לאפס.

הערכים המתקבלים עבור המשתנים הבסיסיים יוצרים BFS.

אם קיים פתרון אופטימלי, אז קיים BFS אופטימלי.

שיטת Simplex עוברת מ-BFS אחד ל-BFS סמוך עד שהיא מגיעה ל-BFS אופטימלי על ידי שימוש בהליכי ציר.

השוואה בין פתרונות בסיסיים לפתרונות אפשריים

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

בפרט, חייב להיות לו וקטורים שאינם תלויים לינארית ובעלי ערכים שאינם אפס עבור xi, ו-x חייב להיות קטן מ-0.

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

אבל לא כל הפתרונות הישימים הם פתרונות מעשיים בסיסיים.

פתרונות מעשיים בסיסיים (BFSs) הם רק אלה התואמים לפינות הפולידרון של פתרונות אפשריים.

חזרה ליסודות: פתיחת הכוח של פתרונות בסיסיים בהנדסה

עדיין קשה להבין? תן לי לשנות קצת את נקודת המבט:

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

ובכן, אל דאגה, כי התשובה היא כאן: פתרו עבור m משתנים במונחים של המשתנים הנותרים (nm), והגדרו את המשתנים (nm) לאפס.

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

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

כעת נחזור להסבר.

פתרון בסיסי תכנות לינארי

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

מקרי שימוש

סיכום

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

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

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

כדי לקבל את התוצאות הטובות ביותר, יש לבחון היטב כל בעיה ולחשוב עליה.

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

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

קישורים והפניות

ספרים:

• תכנות לינארי מאת Vasek Chvatal
• דוגמנות ופתרון תכנות ליניארי עם R מאת Jose M. Sallan