סילבוס

תוכן הקורס ומטרתו

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

נושאי הקורס:

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

-משפטי דואליות.

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

-אלגוריתמים יעילים (סיבוכיות פולינומית) לפתרון בעיות תכנות ליניארי.

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

-בעיות תכנות ליניארי מיוחדות שניתן לפתור אותן בזמן פולינומי חזק, גם כאשר המימד
הוא חלק מהקלט. (בעיות זרימה, בעיות עם שני משתנים באילוץ ועוד.)

-תכונות שלמות של קבוצות פוליהדרליות, ( יונימודולריות, איזון ועוד.)

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

- שימושים