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

פרק 1. מודל התכנון הליניארי ... 1

1.1 דוגמה לבעיית תכנון ליניארי (תיאור מילולי) ... 2

1.2 ניסוח מתמטי של בעיית תכנון ליניארי ... 3

1.3 מרכיבי מודל התכנון הליניארי ... 8

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

1.5 דוגמאות לניסוח בעיות תכנון ליניארי ... 18

1.6 סיכום ... 26

1.7 פתרונות לשאלות נבחרות ... 33

פרק 2. פתרון של בעיות תכנון ליניארי ... 41

2.1 פתרון גרפי לבעיית תכנון ליניארי ... 42

2.2 שיטת הסימפלקס ... 64

2.3 פתרונות לשאלות נבחרות ... 80

3. בעיית התובלה ... 91

3.2 הצגת בעיית התובלה כבעיית תכנון ליניארי ... 98

3.3 שיטת סימפלקס מקוצרת לבעיית התובלה ... 105

3.4 פתרונות לשאלות נבחרות ... 126

3.5 שאלות נוספות ... 144

פרק 4. מודלים של זרימה אופטימלית ברשתות ... 150

4.2 מונחים לדיון בבעיות זרימה ברשתות ... 151

4.3 סקירת מבני נתונים שונים לייצוג גופים ורשתות ... 168

4.4 מטריצת מסלולים ... 188

4.5 פתרונות לשאלות נבחרות ... 208

פרק 5. בעיית המסלול הקצר ביותר ... 211

5.2 גרסאות שונות של בעיית המסלול הקצר ביותר ... 214

5.3 הגדרה פורמלית של בעיית המסלול הקצר ... 218

5.4 מסלולים אופטימליים ברשת מקדקוד המקור ליתר הקדקודים - אלגוריתם דיקסטרה ... 229

5.6 סריקת גרף לעומק (DFS) ... 265

5.7 מיון טופולוגי ... 287

5.8 מציאת המסלולים הקצרים ביותר בין כל הזוגות ... 303

5.9 פתרונות לשאלות נבחרות ... 323

6. עץ פורש מינימלי ... 326

6.2 עצים - הגדרות ותכונות יסוד ... 329

6.3 האלגוריתם של קרוסקל (Kruskal) למציאת עץ פורש מינימלי ... 332

6.4 האלגוריתם של פרים (Prim) ... 344

6.5 שאלות לסיכום פרק 6 ... 356