מחבר: צוות חינוך טכנולוגי מטח

שנת ההוצאה: תשס"ד - 2004

מילות מפתח: יחסים מתמטיים; מערכות מחשבים

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

נושא/נושאים: , מדעי המחשב

תוכן הספר:

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

• תוכן העניינים

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

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

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

• איור ‭1.1‬ תיאור התחום האפשרי

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

• איור ‭1.2‬ תיאור הפעולה של פונקציית המטרה

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

• איור ‭1.3‬ התיאור הגרפי של פונקציית המטרה ‭Z =3X, - 6‬

• איור ‭1.4‬ התחום האפשרי של האילוץ ‭2X + X - 2 < 0‬ ‭t 2‬

• איור ‭1.5‬ 2 התחום האפשרי של האילוץ ‭* , + X/ < 1‬

• אייר ‭1.6‬ תחום פתרונות אפשריים לפתרון המוגדר על-ידי 4 אילוצים

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

• איור ‭1.7‬ מכלאות הרכיבה המעגלית (משמאל) והריבועית (מימין)

• 1.6 סיכום

• 1.7 פתרונות לשאלות נבחרות

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

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

• איור ‭2.1‬ התיאור הגרפי של מודל התכנון הליניארי הנתון בדוגמה ‭2.1‬

• אייר ‭2.2‬ תחוס הפתרונות האפשריים (התחום המקווקו)

• איור ‭2.3‬ היטל הגובה של פונקציית המטרה עבור ‭Z=2‬

• אייר ‭2.4‬ היטלי הגובה של פונקציית המטרה (הקווים המקווקווים)

• איור ‭2.5‬ תחום הפתרונות האפשריים (התחום המקווקו)

• איור ‭2.6‬ תחום הפתרונות האפשריים (התחום המקווקו‭.(‬ התחום אינו חסום מצידו הימני ונמשך לאינסוף

• איור ‭2.7‬ היטל הגובה של פונקציית המטרה עבור ‭Z = 0‬

• איור ‭2.8‬ היטלי הגובה של פונקציית המטרה (הקווים המקווקווים)

• איור ‭2.9‬ תחום הפתרונות האפשריים (תחום ריק)

• 2.2 שיטת הסימפלקס

• איור ‭2.10‬ תחוס הפתרונות האפשריים לבעיה בדוגמה ‭2.2‬ (התחום המקווקו)

• איוו ‭2.11‬ ערך פונקציות המטרה בקדקודים האפשריים של דוגמה ‭2.6‬

• 2.3 פתרונות לשאלות נבחרות

• איור ‭2.12‬ התחום האפשרי

• איור ‭2.13‬ התחום האפשרי והיטלי הגובה של פונקציית המטרה (הקווים המקווקוויס)

• איור ‭2.14‬ היטלי הגובה של פונקציית המטרה (הקווים המקווקווים‭.(‬ שימו לב כי היטלי קווי הגובה מקבילים לקו התוחם את תחום הפתרונות האפשריים מימין

• איור ‭2.15‬

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

• 3.1 הצגת הבעיה

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

• טבלה ‭3.5‬ מערכת התובלה הנוכחית בחברת "גלידות אביב" - פתרון לא-בסיסי

• טבלה ‭3.4‬ מערכת התובלה הנוכחית בחברת "גלידות אביב" - פתרון לא-בסיסי

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

• טבלה ‭3.6‬ שיטת הפינה הצפונית-מערבית - מצב התחלתי

• טבלה ‭3.7‬ שיטת הפינה הצפונית-מערבית - לולאה ראשונה

• טבלה ‭3.8‬ שיטת הפינה הצפונית-מערבית - לולאה שנייה

• טבלה ‭3.9‬ שיטת הפינה הצפונית-מערבית - לולאה שלישית

• טבלה ‭3.10‬ הפתרון הבסיסי המתקבל בשיטת הפינה הצפונית-מערבית

• טבלה ‭3.11‬ דוגמה של טבלת סימפלקס לתובלה

• טבלה ‭3.12‬ שינוי מחיר בעמודה 1

• טבלה ‭3.13‬ טבלת סימפלקס לתובלה ההתחלתית (לפני קבלת ערכי ‭((c ;y - u i - c‬

• טבלה ‭3.14‬ טבלת סימפלקס לאיטרציה הראשונה

• טבלה ‭3.15‬ טבלת סימפלקס חלקית עבור פתרון בסיסי אחר (לא אופטימלי)

• טבלה ‭3.16‬ טבלת סימפלקס (שלמה) עבור הפתרון הבסיסי החדש

• טבלה ‭3.17‬ תגובת השרשרת הנגרמת בעקבות הגדלת המשתנה הנכנס לבסיס, ‭x 23‬

• טבלה ‭3.18‬ טבלת הסימפלקס עבור האיטרציה השנייה

• טבלה ‭3.19‬ תצורה כללית של טבלת הסימפלקס לתובלה

• 3.4 פתרונות לשאלות נבחרות

• 3.5 שאלות נוספות

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

• 4.1 דוגמאות של בעיות זרימה ברשתות

• איור ‭4.1‬ רשת כבישים

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

• איור ‭4.8‬ תיאור המסלול

• איור ‭4.7‬ דוגמה למסלול בגרף

• איור ‭4.9‬ מעגל בגרף

• איור ‭».10‬ דוגמה לגרף מעגלי

• איור ‭4.11‬ דוגמה לגרף לא מעגלי

• איור ‭4.12‬ דוגמה לגרף שלם בעל 4 קדקודים

• טבלה ‭4.1‬ המרכיבים העיקריים של רשתות נבחרות

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

• טבלה ‭:4.1‬ ממשק של מבנה הנתונים גרף (גרף משוקלל - רשת)

• 4.4 מטריצת מסלולים

• 4.5 פתרונות לשאלות נבחרות

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

• 5.1 דוגמאות של בעיית המסלול הקצר ביותר

• איור ‭5.1‬ מפת הכבישים בעיר

• איור ‭5.2‬ רשת כבישים המקשרת מספר יישובים

• איור ‭5.3‬ האפשרויות להגיע מקדקוד a לקדקוד/ברכבת התחתית בפריס

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

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

• אייר ‭5.5‬ גרף עם רכיב קשיר אחד

• אייר ‭5.6‬ גרף עם שלושה רכיבים קשיריס

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

• טבלת הרצה לשאלה 3

• עץ פורש BFS

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

• 5.7 מיון טופולוגי

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

• 5.9 פתרונות לשאלות נבחרות

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

• 6.1 הצגת הבעיה

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

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

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

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

עמודים:

I  II  III  IV  V  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  
21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  
46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  
71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  
96  97  98  99  100  101  102  103  104  105  106  107  108  109  110  111  112  113  114  115  116  117  118  119  120  
121  122  123  124  125  126  127  128  129  130  131  132  133  134  135  136  137  138  139  140  141  142  143  144  145  
146  147  148  149  150  151  152  153  154  155  156  157  158  159  160  161  162  163  164  165  166  167  168  169  170  
171  172  173  174  175  176  177  178  179  180  181  182  183  184  185  186  187  188  189  190  191  192  193  194  195  
196  197  198  199  200  201  202  203  204  205  206  207  208  209  210  211  212  213  214  215  216  217  218  219  220  
221  222  223  224  225  226  227  228  229  230  231  232  233  234  235  236  237  238  239  240  241  242  243  244  245  
246  247  248  249  250  251  252  253  254  255  256  257  258  259  260  261  262  263  264  265  266  267  268  269  270  
271  272  273  274  275  276  277  278  279  280  281  282  283  284  285  286  287  288  289  290  291  292  293  294  295  
296  297  298  299  300  301  302  303  304  305  306  307  308  309  310  311  312  313  314  315  316  317  318  319  320  
321  322  323  324  325  326  327  328  329  330  331  332  333  334  335  336  337  338  339  340  341  342  343  344  345  
346  347  348  349  350  351  352  353  354  355  356  357  358  359  360  361  362  363