תכנון בלוקים

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

נאמר שאנו מבקשים לאמוד במהירות את כוחם של עשרה סוסי עבודה, ובאפשרותנו לרתום למחרשה ארבעה סוסים בכל פעם. דגימה של רביעיות סוסים באקראי תיצור הטיות הנובעות מעצם הדגימה, ולכן רצוי לדגום באופן סימטרי, כל שכל סוס ישתתף בחרישה אותו מספר פעמים. אם חוששים לאינטראקציות אפשר להקפיד יותר, ולדגום כך שכל צמד סוסים יופיע מספר שווה של פעמים. באופן נאיבי אפשר למדוד כמה זמן נדרש מכל רביעיית סוסים לחרוש ניר אחד, אלא שניסוי מלא ידרוש ${\binom {10}{4}}=210$ ימי עבודה. אפשר לבצע במקום זה ניסוי קצר יותר, שיימשך רק 15 ימי עבודה, כך שכל סוס ישתתף בחרישה שש פעמים, וכל שני סוסים ישתתפו בחרישה יחד פעמיים. זהו "תכנון בלוקים מאוזן" עם פרמטרים $(10,15,6,4,2)$. האיזון מאפשר להשיג שונות נמוכה של האומדים בהשוואה לניסוי לא מאוזן באורך דומה.

הגדרה והפרמטרים היסודיים

תכנון בלוקים מאוזן (Balanced Incomplete Block Design, ובקיצור המקובל BIBD) הוא מערכת הכוללת קבוצה של $\nu$ נקודות ומשפחה של $b$ בלוקים, שהם תת-קבוצות בגודל $k$, כך שכל נקודה נמצאת בדיוק ב-$r$ בלוקים, וכל זוג נקודות נמצא בדיוק ב-$\lambda$ בלוקים. הווקטור $(\nu ,b,r,k,\lambda )$ מחזיק את הפרמטרים של המערכת.

הנחות הסימטריה מובילות לשני אילוצים על הפרמטרים: $\nu r=bk$ ו-$r(k-1)=\lambda (\nu -1)$ (הוכחה: ספור נקודות וזוגות של נקודות בבלוקים, בשתי דרכים). בזכות האילוצים האלה, הפרמטרים נקבעים על ידי כל שלושה מתוכם. יש שתי דרכים מקובלות לציין את הפרמטרים: כל החמישה בסדר המופיע לעיל; או רק גודל הקבוצה, גודל הבלוק, ומקדם הכפילות, $(\nu ,k,\lambda )$. לאור ההכללה להלן, מקובל גם הסימון $2-(\nu ,k,\lambda )$.

אי-השוויון של פישר קובע שמספר הבלוקים אינו נופל ממספר הנקודות (כלומר $\nu \leq b$). התנאים האריתמטיים הכרחיים, אבל אינם מספיקים. לדוגמה, לא קיים תכנון עם הפרמטרים $(43,43,7,7,1)$ (Tarry, 1900).

הכללות

תכנון בלוקים מאוזן נקרא גם תכנון-2, משום שהדרישה היא שכל 2 נקודות תהיינה שייכות לאותו מספר בלוקים. בציון הפרמטרים, מדובר בתכנון $2-(\nu ,k,\lambda )$, שבו, בהכרח, $b={\frac {\lambda \nu (\nu -1)}{k(k-1)}}$ ו-$r={\frac {\lambda (\nu -1)}{k-1}}$.

בדומה לזה, אפשר להגדיר תכנון-t לכל t: מערכת שבה כל t-יה של נקודות נמצאת ב-$\lambda$ בלוקים. זהו תכנון $t-(\nu ,k,\lambda )$. התנאי עבור ערך מסוים של t גורר את התנאי לכל ערך נמוך ממנו (עם $\lambda$ אחר), בדיוק כפי שהדרישה שכל זוג נקודות יהיה שייך למספר קבוע של בלוקים (t=2) גוררת את הדרישה שכל נקודה תהיה שייכת למספר קבוע של בלוקים (t=1). תכנון-1 אינו אלא פירוק של קבוצה לבלוקים זרים בגודל קבוע.

מערכת שיוך (association scheme) היא מערכת שבה הזוגות (או באופן כללי יותר תת-הקבוצות בגודל t) מחולקים למשפחות, שבכל אחת מהן יש איזון (ערך $\lambda$) אחר.

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

מקרים פרטיים

תכנון-t עם $\lambda =1$ נקרא מערכת שטיינר: מערכת שבה כל t נקודות שייכת לבלוק יחיד. בפרט, BIBD (כלומר תכנון-2) עם $\lambda =1$ ו-$k=3$, היינו, תכנון $2-(\nu ,3,1)$, עם $b={\frac {\nu (\nu -1)}{6}}$ בלוקים ו-$r={\frac {\nu -1}{2}}$, הוא מערכת שטיינר משולשת.

תכנונים סימטריים

תכנון-2 שבו מספר הבלוקים שווה למספר הנקודות ($\nu =b$) נקרא תכנון סימטרי. תכנון הוא סימטרי אם ורק אם $k=r$, אם ורק אם $\nu ={\frac {k(k-1)}{\lambda }}+1$. בתכנון סימטרי כל שני בלוקים נחתכים ב-$\lambda$ נקודות, וגם להפך: מערכת של $\nu$ תת-קבוצות בגודל קבוע של קבוצה בגודל $\nu$, שכל שתיים מהן נחתכות במספר קבוע של נקודות, היא תכנון סימטרי. משפט ברוק-רייזר-צ'ולה מציב תנאי על קיומו של תכנון סימטרי $(\nu ,\nu ,k,k,\lambda )$: אם $\nu$ זוגי אז הסדר $k-\lambda$ הוא ריבוע; ואם $\nu$ אי-זוגי צריך להיות פתרון שלם למשוואה הדיופנטית $x^{2}-(k-\lambda )y^{2}-(-1)^{(\nu -1)/2}\lambda z^{2}=0$.

תכנון סימטרי עם $\lambda =1$ הוא מישור פרויקטיבי סופי. לדוגמה, התכנון היחיד עם פרמטרים $(7,7,3,3,1)$ הוא מישור פאנו.

תכנון סימטרי עם $\lambda =2$ נקרא דו-מישור: כל שתי נקודות מוכלות בשני בלוקים, וכל שני בלוקים נחתכים בשתי נקודות. הפרמטרים של תכנון כזה הם $(k(k-1)/2+1,k,2)$, והערך k-2 הוא הסדר שלו. ידועים רק 18 דו-מישורים, מסדר 0, 1, 2, 3, 4 (שלושה), 7 (ארבעה), 9 (חמישה), 11 (שניים). הסדרים 5,6,8,10 אינם אפשריים לפי משפט ברוק-רייסר-צ'ולה.

תכנון סימטרי עם הפרמטרים $(4a-1,4a-1,2a-1,2a-1,a-1)$ נקרא תכנון הדמר; יש התאמה בין תכנונים כאלה לבין מטריצות ריבועיות H שכל רכיביהן 1 או 1-, המקיימות $\ HH^{t}=4aI$.

בניות מתכנון נתון

המשלים של תכנון בלוקים מאוזן הוא התכנון עם אותה קבוצת נקודות, והחלפת כל בלוק במשלים שלו. המשלים של תכנון $(\nu ,b,r,k,\lambda )$ הוא תכנון $(\nu ,b,b-r,\nu -k,\lambda +b-2r)$. המספר $n=r-\lambda$ הוא הסדר של תכנון בלוקים מאוזן. לתכנון ולמשלים שלו יש אותו סדר.

מתכנון $t-(\nu ,k,\lambda )$ מתקבל התכנון הנגזר $(t-1)-(\nu -1,k-1,\lambda )$ על ידי הסרת נקודה מן המרחב ומכל הבלוקים שעוברים דרכה (הבלוקים שאינם עוברים דרכה, מושלכים). ידוע איזה תכנוני-2 סימטריים הם נגזרים.

מתכנון סימטרי אפשר לבנות את התכנון הדואלי עם אותם פרמטרים, שהנקודות שלו הן הבלוקים של התכנון המקורי, ובלוק שלו הוא קבוצת הבלוקים שעוברים דרך נקודה בתכנון המקורי. הבנייה עובדת משום שכל שני בלוקים של תכנון סימטרי נחתכים כאמור ב-$\lambda$ נקודות. מתכנון סימטרי $(\nu ,\nu ,k,k,\lambda )$ אפשר לבנות הטלה, שהיא תכנון $(k,\nu -1,k-1,\lambda ,\lambda -1)$ שהנקודות שלו הן הנקודות בבלוק קבוע של התכנון המקורי, והבלוקים שלו הם החיתוכים של הבלוק הקבוע עם הבלוקים האחרים. אפשר גם לבנות שארית (residual design) שהיא תכנון $(\nu -k,\nu -1,k,k-\lambda ,\lambda )$, על ידי מחיקת כל הנקודות בבלוק קבוע.

מטריצת החילה

תכנון בלוקים הוא גאומטריית חילה עם אובייקטים משני טיפוסים (נקודות ובלוקים). אפשר לתאר תכנון בלוקים באמצעות מטריצה $\ A\in \operatorname {M} _{b\times \nu }(\mathbb {Z} )$ שערכיה הם 1 (במקומות (x,b) שבהם הנקודה x שייכת לבלוק b) ו-0 (אם לא). מן התנאי על זוגות של נקודות נובע ש-$A^{t}A=\lambda J_{\nu }+(r-\lambda )I_{\nu }$, כאשר I היא מטריצת היחידה, ו-J המטריצה שכל רכיביה 1. כאשר התכנון סימטרי זו מטריצה הפיכה, ומכאן נובע ש-$AA^{t}=A^{t}A$, ולכן כל שני בלוקים נחתכים באותו מספר נקודות. חישוב הדטרמיננטה גם מוכיח את משפט ברוק-רייזר-צ'ולה עבור $\ \nu$ זוגי. (ההוכחה למקרה האי-זוגי יותר מתוחכמת, ומבוססת על ראיית מטריצת החילה כאיזומורפיזם בין תבניות ריבועיות).

דוגמאות

יש BIBD יחיד עם פרמטרים $(6,10,5,3,2)$. יש ארבעה BIBD עם פרמטרים $(8,14,7,4,3)$.

פתירות

תכנון בלוקים מאוזן נקרא פתיר (resolvable) אם אפשר לחלק את הבלוקים שלו למשפחות שכל אחת מהן מהווה חלוקה של המרחב לבלוקים זרים. מישור אפיני סופי הוא פתיר. בעיית 15 התלמידות של קירקמן מבקשת לפתור את מערכת שטיינר המשולשת $(15,35,7,3,1)=S(15,3,2)$.

ראו גם

• מערכת שטיינר
• גרף רגולרי בחזקה (strongly regular graph)

קישורים חיצוניים

• תכנון בלוקים, באתר MathWorld (באנגלית)   

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

35708902תכנון בלוקים