תאריך עדכון: 11.9.2019

 

המחלקה למדעי המחשב

 

מבוא לאופטימיזציה

 

סוג הקורס: שיעור

שנת לימודים: תש"פא     סמסטר: א'        היקף שעות:  2 ש"ס

 

א.  מטרות הקורס:

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

ב. תוכן הקורס:

 

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

 

תכנית הוראה מפורטת לכל השיעורים:

 

מבוא לאופטימיזציה:

(כל נושא מלווה בדוגמאות ובעיות מהעולם האמיתי)

שיעור 1: משתנים, פונקציית מטרה ואילוצים

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

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

שיעורים 4: תכנות לא ליניארי: שיטת כופלי לגראנג, הסיאן.

שיעור 5: תכנות בשלמים. Branch and Bound

שיעור 6: פתרונות מקורבים לבעיות אופטימיזציה: Monte Carlo Search Tree

שיעור 7: אלגוריתמים מיוחדים לבעיות גנריות: בעיית ההשמה, בעיית התחבורה, בעיות נבחרות ברשתות.

שיעור 8-11: עבודה עצמית על פרוייקטים.

שיעור 12-14: הצגה ודיון

ג. חובות הקורס:

 

דרישות קדם: ציון עובר בכל קורסי שנה א'.

חובות ומטלות: עבודה.

מרכיבי הציון הסופי: 100% ציון עבודה.

 

ד. ביבליוגרפיה:

 

 ספרי הלימוד (textbooks):

 

1. Introduction to Operations Research, Ninth Edition, FREDERICK S. HILLIER
2. Introduction to Optimization, Pablo Pedregal (online)