אופטימיזציה עוזרת לך למצוא את התוצאה הטובה ביותר שמביאה רווח, מפחיתה עלויות או מגדירה פרמטר שגורם לכשלים בתהליך העסקי.
תהליך זה נקרא גם תכנות מתמטי. זה פותר את הבעיה של קביעת חלוקת המשאבים המוגבלים הדרושים להשגת המטרה שהציב ראש בעיית האופטימיזציה. מבין כל האפשרויות האפשריות, רצוי למצוא את זו שממקסמת (או מקטינה) את פרמטר השליטה, למשל רווח או עלות. מודלים של אופטימיזציה נקראים גם מדריכים או נורמטיביים מכיוון שהם מבקשים למצוא אסטרטגיה ישימה עבור העסק.
היסטוריית פיתוח
תכנות לינארי (LP) עובד עם סוג של בעיות אופטימיזציה שבהן כל האילוצים הם ליניאריים.
הצגת היסטוריה קצרה של התפתחות LP:
- בשנת 1762, לגראנג' פתרה בעיות אופטימיזציה פשוטות עם אילוצי שוויון.
- בשנת 1820, גאוס החליטמערכת משוואות לינארית באמצעות חיסול.
- בשנת 1866, וילהלם ג'ורדן שיכלל את השיטה של מציאת שגיאות בריבועים הקטנים כקריטריון התאמה. זה נקרא כעת שיטת גאוס-ירדן.
- המחשב הדיגיטלי הופיע ב-1945.
- דנציג המציא שיטות סימפלקס ב-1947.
- בשנת 1968, פיאקו ומקורמיק הציגו את שיטת Inside Point.
- בשנת 1984, קרמרקר יישם את שיטת הפנים כדי לפתור תוכניות ליניאריות, והוסיף את הניתוח החדשני שלו.
LP הוכיח את עצמו ככלי רב עוצמה, הן ליצירת מודלים של בעיות בעולם האמיתי והן בתור תיאוריה מתמטית בשימוש נרחב. עם זאת, הרבה בעיות אופטימיזציה מעניינות אינן ליניאריות.
מה לעשות במקרה זה? חקר בעיות כאלה כולל תערובת מגוונת של אלגברה לינארית, חשבון רב משתנים, ניתוח מספרי ושיטות חישוביות. מדענים מפתחים אלגוריתמים חישוביים, כולל שיטות נקודות פנימיות לתכנות ליניארי, גיאומטריה, ניתוח של קבוצות ופונקציות קמורות, וחקר בעיות בעלות מבנה מיוחד כמו תכנות ריבועי.
אופטימיזציה לא ליניארית מספקת הבנה בסיסית של ניתוח מתמטי ונמצאת בשימוש נרחב בתחומים שונים כגון הנדסה, ניתוח רגרסיה, ניהול משאבים, חקר גיאופיזי וכלכלה.
סיווג של בעיות אופטימיזציה
צעד חשוב פנימהתהליך האופטימיזציה הוא סיווג מודלים, שכן אלגוריתמי הפתרון שלהם מותאמים לסוג מסוים.
1. בעיות באופטימיזציה דיסקרטית ומתמשכת. יש מודלים הגיוניים רק אם המשתנים לוקחים ערכים מתת-קבוצה נפרדת של מספרים שלמים. אחרים מכילים נתונים שיכולים לקבל כל ערך אמיתי. בדרך כלל קל יותר לפתור אותם. שיפורים באלגוריתמים, בשילוב עם התקדמות בטכנולוגיית המחשב, הגדילו באופן דרמטי את הגודל והמורכבות של בעיית אופטימיזציה של תכנות ליניארי.
2. אופטימיזציה בלתי מוגבלת ומוגבלת. הבדל חשוב נוסף הוא משימות שבהן אין מגבלה על משתנים. זה יכול לנוע בהרבה מאומדים פשוטים ועד למערכות של שוויון ואי-שוויון המדגימות קשרים מורכבים בין נתונים. בעיות אופטימיזציה כאלה ניתנות לסווג נוסף לפי אופי הפונקציות (לינאריות ולא ליניאריות, קמורות וחלקות, ניתנות להבדלה ולא ניתנות להבדלה).
3. משימות היתכנות. המטרה שלהם היא למצוא ערכים משתנים שעומדים במגבלות המודל ללא מטרת אופטימיזציה ספציפית.
4. משימות משלימות. הם נמצאים בשימוש נרחב בטכנולוגיה ובכלכלה. המטרה היא למצוא פתרון שיעמוד בתנאי ההשלמה. בפועל, משימות עם מספר יעדים מנוסחות לעתים קרובות מחדש למטרות בודדות.
5. אופטימיזציה דטרמיניסטית מול סטוכסטית. אופטימיזציה דטרמיניסטית מניחה שהנתונים עבורהמטלות מדויקות לחלוטין. עם זאת, בנושאים אקטואליים רבים לא ניתן לדעת אותם מכמה סיבות.
הראשון קשור לשגיאת מדידה פשוטה. הסיבה השנייה היא יותר עקרונית. זה טמון בעובדה שחלק מהנתונים מייצגים מידע על העתיד, למשל, הביקוש למוצר או המחיר לתקופת זמן עתידית. בעת אופטימיזציה בתנאי אופטימיזציה סטוכסטיים, אי ודאות כלולה במודל.
רכיבים עיקריים
פונקציית המטרה היא זו שיש למזער או למקסם. לרוב סוגי בעיות האופטימיזציה יש פונקציה אובייקטיבית אחת. אם לא, לעתים קרובות ניתן לנסח אותם מחדש כך שיעבדו.
שני חריגים לכלל זה:
1. משימת חיפוש יעד. ברוב היישומים העסקיים, המנהל רוצה להשיג מטרה מסוימת תוך עמידה במגבלות המודל. המשתמש לא רוצה במיוחד לייעל משהו, ולכן אין טעם להגדיר פונקציה אובייקטיבית. סוג זה מכונה בדרך כלל בעיית סיפוק.
2. הרבה תכונות אובייקטיביות. לעתים קרובות, משתמש ירצה לבצע אופטימיזציה של מספר יעדים שונים בו-זמנית. הם בדרך כלל אינם תואמים. משתנים שמבצעים אופטימיזציה עבור יעד אחד עשויים שלא להיות הטובים ביותר עבור אחרים.
סוגי רכיבים:
- קלט מבוקר הוא קבוצה של משתני החלטה המשפיעים על הערך של פונקציה אובייקטיבית. במשימת ייצור, משתנים עשויים לכלול את התפלגות המשאבים הזמינים השונים או את העבודה הנדרשתכל פעולה.
- אילוצים הם קשרים בין משתני החלטה ופרמטרים. לבעיית ייצור, לא הגיוני להשקיע זמן רב בפעילות כלשהי, אז הגבל את כל המשתנים ה"זמניים".
- פתרונות אפשריים ואופטימליים. הערך של ההחלטה עבור משתנים, שתחתיהם מתקיימים כל האילוצים, נקרא סיפוק. רוב האלגוריתמים תחילה מוצאים אותו, ואז מנסים לשפר אותו. לבסוף, הם משנים משתנים כדי לעבור מפתרון אפשרי אחד לאחר. תהליך זה חוזר על עצמו עד שפונקציית המטרה מגיעה למקסימום או למינימום שלה. תוצאה זו נקראת הפתרון האופטימלי.
אלגוריתמים של בעיות אופטימיזציה שפותחו עבור התוכניות המתמטיות הבאות נמצאים בשימוש נרחב:
- קמור.
- ניתן להפרדה.
- ריבועי.
- גיאומטרי.
Google Linear Solvers
אופטימיזציה או תכנות לינארית הוא השם שניתן לתהליך החישובי של פתרון אופטימלי של בעיה. הוא מעוצב כמערכת של קשרים ליניאריים המתעוררים בדיסציפלינות מדעיות והנדסיות רבות.
Google מציעה שלוש דרכים לפתור בעיות אופטימיזציה ליניארית:
- ספריית קוד פתוח של Glop.
- תוסף אופטימיזציה לינארית עבור Google Sheets.
- שירות אופטימיזציה לינארי בסקריפט של Google Apps.
Glop מובנה ב-Googleפותר ליניארי. זה זמין בקוד פתוח. אתה יכול לגשת ל-Glop דרך מעטפת הפותר הליניארית של OR-Tools, שהיא מעטפת עבור Glop.
מודול אופטימיזציה לינארי עבור Google Sheets מאפשר לך לבצע הצהרה ליניארית של בעיית האופטימיזציה על ידי הזנת נתונים בגיליון אלקטרוני.
תכנות ריבועי
פלטפורמת ה-Premium Solver משתמשת בגרסת LP/ריבועית מורחבת של שיטת Simplex עם מגבלות עיבוד בעיות LP ו-QP של עד 2000 משתני החלטה.
SQP פותר בעיות בקנה מידה גדול משתמש ביישום מודרני של שיטת הסט הפעיל עם דלילות כדי לפתור בעיות תכנות ריבועיות (QP). מנוע XPRESS Solver משתמש בהרחבה טבעית של שיטת "Interior Point" או Newton Barrier כדי לפתור בעיות QP.
MOSEK Solver מחיל שיטות מוטבעות של "נקודה פנימית" ושיטות כפולות אוטומטיות. זה יעיל במיוחד עבור בעיות QP בשילוב רופף. זה יכול גם לפתור את הבעיות של Scale Quadratic Constraint (QCP) ו- Second Order Cone Programming (SOCP).
חישובים מרובי פעולות
הם נמצאים בשימוש מוצלח למדי עם השימוש בתכונות Microsoft Office, למשל, פתרון בעיות אופטימיזציה ב-Excel.
בטבלה שלמעלה, הסמלים הם:
- K1 - K6 - לקוחות שצריכים לספק סחורה.
- S1 - S6 הם אתרי ייצור פוטנציאליים שניתן לבנות עבור זה. ניתן ליצור1, 2, 3, 4, 5 או כל 6 המיקומים.
ישנן עלויות קבועות עבור כל מתקן המופיע בעמודה I (תיקון).
אם המיקום לא ישנה דבר, זה לא ייחשב. אז לא יהיו עלויות קבועות.
זהה מיקומים פוטנציאליים כדי לקבל את העלות הנמוכה ביותר.
בתנאים אלה, המיקום מבוסס או לא. שני המצבים הללו הם: "TRUE - FALSE" או "1 - 0". ישנם שישה מצבים עבור שישה מיקומים, לדוגמה, 000001 מוגדר לשישי בלבד, 111111 מוגדר לכל.
במערכת המספרים הבינארית, יש בדיוק 63 אפשרויות שונות מ-000001 (1) עד 111111 (63).
L2-L64 אמור כעת לקרוא {=MULTIPLE OPERATION (K1)}, אלו הן התוצאות של כל הפתרונות החלופיים. אז הערך המינימלי הוא=Min (L) והחלופה המתאימה היא INDEX (K).
CPLEX תכנות מספרים שלמים
לפעמים קשר ליניארי אינו מספיק כדי להגיע ללב בעיה עסקית. זה נכון במיוחד כאשר החלטות כרוכות בבחירות בדידות, כמו האם לפתוח או לא לפתוח מחסן במקום מסוים. במצבים אלה, יש להשתמש בתכנות מספרים שלמים.
אם הבעיה כרוכה הן בבחירות בדידות והן בבחירות מתמשכות, זו תוכנית מעורבת של מספרים שלמים. יכולות להיות לו בעיות ריבועיות ליניאריות וקמורות ואותם אילוצים מסדר שני.
תוכניות שלמות הן הרבה יותר מורכבות מתוכניות ליניאריות, אבל יש להן יישומים עסקיים חשובים. תוֹכנָהתוכנת CPLEX משתמשת בשיטות מתמטיות מורכבות כדי לפתור בעיות שלמים. השיטות שלו כוללות חיפוש שיטתי אחר שילובים אפשריים של משתנים נפרדים באמצעות הרפיית תוכנה ליניארית או ריבועית כדי לחשב גבולות על הערך של הפתרון האופטימלי.
הם גם משתמשים ב-LP ובשיטות אחרות לפתרון בעיות באופטימיזציה כדי לחשב אילוצים.
פתרון Microsoft Excel Standard
טכנולוגיה זו משתמשת ביישום הבסיסי של שיטת Simplex הראשית כדי לפתור בעיות LP. הוא מוגבל ל-200 משתנים. "פותר פרימיום" משתמש בשיטת סימפלקס ראשונית משופרת עם גבולות דו-צדדיים למשתנים. פלטפורמת Premium Solver משתמשת בגרסה מורחבת של LP/Quadratic Simplex Solver כדי לפתור בעיית אופטימיזציה עם עד 2000 משתני החלטה.
LP בקנה מידה גדול לפלטפורמת Premium Solver מיישמת יישום חדיש של שיטת הסימפלקס הפשוטה והכפולה, המשתמשת בדלילות במודל LP כדי לחסוך זמן וזיכרון, אסטרטגיות מתקדמות לעדכון ו שחזור מטריצות, תמחור וסיבובים מרובים וחלקיים, ולהתגברות על ניוון. מנוע זה זמין בשלוש גרסאות (מסוגל להתמודד עם עד 8,000, 32,000 משתנים ומגבלות ללא הגבלה).
MOSEK Solver כולל סימפלקס ראשי ודואלי, שיטה המנצלת גם את הדלילות ומשתמשת באסטרטגיות מתקדמות לעדכון מטריצות ו-"refactorization". זה פותר בעיות בגודל בלתי מוגבל, היהנבדק על בעיות תכנות ליניאריות עם מיליוני משתני החלטה.
דוגמה שלב אחר שלב ב-EXCEL
כדי להגדיר את מודל בעיית האופטימיזציה ב-Excel, בצע את השלבים הבאים:
- ארגן את הנתונים עבור הבעיה בגיליון אלקטרוני בצורה הגיונית.
- בחר תא לאחסון כל משתנה.
- צור בתא נוסחה לחישוב המודל המתמטי היעד של בעיית האופטימיזציה.
- צור נוסחאות לחישוב הצד השמאלי של כל אילוץ.
- השתמש בתיבת דו-שיח ב-Excel כדי לספר ל-Solver על משתני החלטה, יעדים, אילוצים וגבולות רצויים בפרמטרים אלה.
- הפעל את "Solver" כדי למצוא את הפתרון האופטימלי.
- צור גיליון אקסל.
- ארגן את הנתונים עבור הבעיה ב-Excel שבו מחושבת הנוסחה של פונקציית המטרה והאילוץ.
בטבלה לעיל, התאים B4, C4, D4 ו-E4 נשמרו כדי לייצג את משתני ההחלטה X 1, X 2, X 3 ו-X 4. דוגמאות להחלטה:
- מודל תמהיל המוצרים ($450, $1150, $800 ורווח של $400 למוצר) הוזן בתאים B5, C5, D5 ו-E5, בהתאמה. זה מאפשר לחשב את היעד ב-F5=B5B4 + C5C4 + D5D4 + E5E4 או F5:=SUMPRODUCT (B5: E5, B4: E4).
- ב-B8 הזינו את כמות המשאבים הדרושה לייצור כל סוג של מוצר.
- נוסחה עבור F8:=SUMPRODUCT(B8:E8, $B$4:$E$4).
- העתק את זהנוסחה ב-F9. סימני דולר ב-$B$4:$E$4 מציינים שטווח תאים זה נשאר קבוע.
- ב-G8 הזינו את כמות המשאבים הזמינה מכל סוג, התואמת לערכי ההגבלות בצד ימין. זה מאפשר לך לבטא אותם כך: F11<=G8: G11.
- זה שווה ערך לארבע מגבלות F8<=G8, F9 <=G9, F10 <=G10 ו-F11=0
שדות יישום מעשי של השיטה
לאופטימיזציה ליניארית יש יישומים מעשיים רבים כדוגמה לבעיית אופטימיזציה:
חברה יכולה לייצר מספר מוצרים עם מרווח תרומה ידוע. ייצור יחידה של כל פריט דורש כמות ידועה של משאבים מוגבלים. המשימה היא ליצור תוכנית ייצור כדי לקבוע כמה מכל מוצר יש לייצר כדי שהרווח של החברה יהיה מקסימלי מבלי להפר את אילוצי המשאבים.
בעיות ערבוב הן הפתרון לבעיות אופטימיזציה הקשורות לשילוב מרכיבים למוצר הסופי. דוגמה לכך היא בעיית הדיאטה שנחקרה על ידי ג'ורג' דנציג ב-1947. ניתנים מספר חומרי גלם כמו שיבולת שועל, חזיר ושמן חמניות לצד תכולת התזונה שלהם כמו חלבון, שומן, ויטמין A ומחירם לק ג. האתגר הוא למזג מוצר קצה אחד או יותר מחומרי גלם בעלות הנמוכה ביותר האפשרית תוך שמירה על גבולות המינימום והמקסימום של ערכם התזונתי.
יישום קלאסי של בעיית אופטימיזציה ליניארית הוא קביעת ניתוב לצרכיםתעבורה ברשתות תקשורת או תחבורה. יחד עם זאת, יש לנתב זרימות דרך הרשת באופן שכל דרישות התעבורה יתקיימו מבלי להפר את תנאי רוחב הפס.
בתאוריה מתמטית, ניתן להשתמש באופטימיזציה ליניארית כדי לחשב אסטרטגיות אופטימליות במשחקי סכום אפס לשני אנשים. במקרה זה מחושבת התפלגות ההסתברות לכל משתתף, שהיא מקדם הערבוב האקראי של האסטרטגיות שלו.
שום תהליך עסקי מוצלח בעולם אינו אפשרי ללא אופטימיזציה. ישנם אלגוריתמי אופטימיזציה רבים זמינים. שיטות מסוימות מתאימות רק לסוגים מסוימים של בעיות. חשוב להיות מסוגל לזהות את המאפיינים שלהם ולבחור את שיטת הפתרון המתאימה.
