מבוא לחקר ביצועים

מבוא לחקר ביצועים, תכנות ליניארי - תיאוריה ותרגילים

נילי בק * אמיר בק

ספר זה הוא פרי ניסיוננו בלימוד הקורס הראשון בחקר ביצועים בטכניון, אוניברסיטת תל אביב ובמכללה האקדמית של תל אביב יפו.
הספר עוסק בנושא התכנות הליניארי הרציף והשלם – נושא המהווה בסיס ללימודי חקר הביצועים והאופטימיזציה.
פרק 1 הינו פרק מבוא המציג מגוון רב של בעיות הניתנות לניסוח ליניארי (רציף או שלם). חלק מבעיות אילו ידון בהרחבה בפרקים הבאים.
פרק 2 דן בקצרה בתוכנת ה-MATLAB ותוכנת ה-CVX המאפשרות פתרון ממוחשב של בעיות תכנות ליניארי רציף.
פרקים 3-6 מכסים את התיאוריה הבסיסית של התכנות הליניארי הרציף – פתרונות אפשריים בסיסיים, שיטת הסימפלקס, דואליות וניתוח רגישות.
פרק 7 מציג אחד מן המודלים הבסיסיים והחשובים בתורת המשחקים המשתמש בצורה ישירה בתיאוריה של התכנות הליניארי.
פרקים 8-11 מציגים את נושא התכנות הליניארי בשלמים, וכוללים שיטות פתרון כגון שיטת חתכי גומורי ושיטת סעף וחסום.
פרק 12 דן בנושא הזרימה ברשתות שגם הוא מהווה למעשה דוגמה של בעיית תכנות ליניארי.
פרק 13 עוסק בתכנות דינמי בדיד – שיטה כללית לפתרון מגוון רב של בעיות אופטימיזציה וביניהן בעיות שנדונו בפרקים הקודמים.
הספר מסתיים בפרק 14 בו ניתנת "טעימה" לעולם האלגוריתמים המקורבים.

פרק 1: בעיות תכנות ליניארי: ניסוחים ופתרון גרפי
פרק 2: פתרון בעיות תכנות ליניארי בעזרת MATLAB
פרק 3: פתרונות אפשריים בסיסיים
פרק 4: שיטת הסמפלקס
פרק 5: הבעיה הדואלית
פרק 6: ניתוח רגישות
פרק 7: מבוא לתורת המשחקים
פרק 8: מבוא לתכנות בשלמים
פרק 9: יונימודולריות לחלוטין
פרק 10: חתכי גומורי
פרק 11: שיטת סעף וחסום (branch and bound)
פרק 12: זרימה ברשתות
פרק 13: תכנות דינמי
פרק 14: קירובים
פרק 15: מקורות