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

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

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

הרעיון של פתרון בר-ביצוע בסיסי מגיע בשלב זה.

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

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

אני אדבר על איך למצוא אותם, ממה הם עשויים ולמה הם חשובים.

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

הבנת פתרון מעשי בסיסי

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

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

פתרון אפשרי בסיסי (BFS) הוא רעיון מפתח בתכנות ליניארי שעוזר למצוא את הפתרונות הטובים ביותר.

BFS הוא פתרון עם המספר הקטן ביותר האפשרי של משתנים שאינם אפס.

זוהי פינה בפוליהדרון של פתרונות אפשריים.

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

מציאת פתרון בסיסי אפשרי אופטימלי

כדי למצוא את ה-BFS הטוב ביותר, עלינו לעשות את הפעולות הבאות:

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

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

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

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

כמו כן, תמיד יש BFS אופטימלי אם יש פתרון אופטימלי.

שימוש בשיטת Simplex כדי למצוא BFS אופטימלי

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

הוא עובר מ-BFS אחד ל-BFS "סמוך" על ידי שימוש בהליך הציר.

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

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

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

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

מי צריך תשובות פשוטות ומעשיות בכלל? פשוט לזרוק הכל ביחד ולקוות לטוב.

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

או שזה?

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

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

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

מציאת פתרון בסיסי אפשרי

פתרון אפשרי בסיסי (BFS) הוא פתרון לבעיית אופטימיזציה ליניארית העונה על כל האילוצים ויש לה את המספר המועט ביותר של משתנים שאינם אפס.

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

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

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

מציאת פתרון מעשי בסיסי ראשוני

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

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

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

שיטת Simplex הדו-שלבית היא דרך נוספת לפתור את הבעיה.

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

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

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

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

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

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

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

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

משתנה רפיון הוא רק ההבדל בין הצד הימני של אילוץ לצד השמאלי.

לדוגמה, עבור האילוץ הראשון, אנו מגדירים משתנה רפוי x4 = 14 - 2x1 - x2 - x3. מבחינת המשתנה החדש הזה, האילוץ הראשון שווה ערך פשוט ל-x4 ≥ 0, שהוא אילוץ חיוביות עבור x4.

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

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

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

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

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

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

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

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

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

לפתרון אפשרי בסיסי יש לכל היותר m משתנים שאינם אפס ולפחות nm משתנים שהם אפס, כאשר n הוא מספר משתני ההחלטה ו-m הוא מספר האילוצים.

BFS הוא פינה בפוליהדרון של פתרונות אפשריים, ולכל BFS יש n אילוצים פעילים שאינם תלויים ליניארית.

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

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

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

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

חשיבותו של פתרון אפשרי בסיסי

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

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

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

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

וידאו: פתרונות מעשיים בסיסיים

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

מקרי שימוש

סיכום

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

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

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

זה מדהים שאתה יכול להרתיח בעיות מסובכות למערכת פשוטה של ​​משוואות ואז להשתמש במשוואות האלה כדי לפתור בעיות בעולם האמיתי.

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

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

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

ספרים:

• תכנות לינארי: יסודות והרחבות
• תכנות לינארי: תיאוריה ויישומים