tomron87/hebrew-wikipedia-sentences-corpus huggingface dataset:
וריאציה על הבעיה בעלת חשיבות מיוחדת היא תכנון ליניארי בשלמים – אותה בעיה בתוספת הדרישה שהמשתנים יקבלו ערכים שלמים.
בעיה זאת היא NP-שלמה וגם היא נחקרה רבות.
לבעיות תכנון ליניארי יש שימושים רבים ומגוונים, למשל תכנון תקציב, ניתוב, תכנון דיאטה, הקצאת משאבים, תכנון תחבורה, מציאת אסטרטגיה אופטימלית ועוד.
הן נחקרו לראשונה על ידי לאוניד קנטורוביץ' וצ'אלינג קופמאנס (שזכו על מחקרים אלה בפרס נובל לכלכלה) החל משנות השלושים והארבעים של המאה העשרים.
בעיית תכנון ליניארי מורכבת מאוסף משתנים , עליהם יש אילוצים ליניאריים.
אילוץ ליניארי הוא אי-שוויון בין משוואה ליניארית על המשתנים לבין קבוע, כלומר או .
ניתן גם לדרוש שוויון; אם תנאי הבעיה אינם מאפשרים זאת, ניתן לדרוש שוויון באמצעות שני האי-שוויונות האחרונים שביחד שקולים לו.
בנוסף ישנה פונקציית מטרה שאותה יש למזער או למקסם.
לבעיה לא תמיד קיים פתרון (דוגמה פשוטה: התנאים הם ), וייתכן גם שפונקציית המטרה איננה חסומה (דוגמה פשוטה: התנאים הם , ויש למקסם את ).
לפיכך, פתרון הבעיה יכול להיות אחת משלוש אפשרויות: אין פתרון כלל, אין פתרון חסום, יש לפחות פתרון אופטימלי אחד.
לדוגמה: נניח ש- כלומר ישנם שלושה משתנים, והאילוצים הם:
פתרון למערכת האילוצים הזאת הוא הצבה של ערכים מספריים למשתנים, כך שכל האילוצים מתקיימים.
למשל וכן הם פתרונות למערכת.
לעומת זאת, הוא לא פתרון, שכן הוא לא מקיים את אי השוויון הראשון: לא מתקיים .
בנוסף למערכת האי שוויונות, נניח שצריך למקסם את פונקציית המטרה .
ניתן לראות שהצבת הפתרון הראשון שהוצג נותנת , ואילו הצבת הפתרון השני נותנת .
לכן הפתרון השני נותן ערך גבוה יותר לפונקציית המטרה.
ניתן להראות (בשיטות שידונו בהמשך הערך) שכל פתרון חוקי (כלומר פתרון שמקיים את כל האילוצים) אחר שנציב למשתנים יתן ערך קטן יותר מ-16, ועל כן הוא הפתרון האופטימלי.
אם כל אי השוויונות נתונים באותו כיוון (כלומר בכולם או בכולם ), אז נוח להציג את הבעיה בעזרת מטריצות.
למשל, את הבעיה שהצגנו לעיל ניתן להציג בכתיב מטרציוני כך:
בכתיב זה, בעיית תכנון ליניארי כוללת וקטור באורך , מטריצה בגודל , וקטור בגודל , ווקטור בגודל , כך שהבעיה היא למקסם או למזער את תחת האילוצים או .
בעיית תכנון ליניארי תקרא בעיה ב"צורה קנונית" אם היא מקיימת את התכונות הבאות:
המטרה היא למקסם ביטוי ליניארי (ולא למזער אותו)
כל בעיית תכנון ליניארי ניתן להעביר לצורה קנונית:
אם התכונה הראשונה אינה מתקיימת, ניתן להפוך את ל .
אם התכונה השנייה אינה מתקיימת עבור משתנה , ניתן להחליף את המשתנה בביטוי כאשר דורשים .
אם התכונה השלישית אינה מתקיימת, ניתן להחליף את "למזער את " ב"למקסם את " (ווקטור הפתרון יהיה אותו וקטור).
סך הכול הגדלנו את כמות המשתנים והמשוואות פי שניים לכל היותר.
זוהי צורת הצגה נוספת של בעיית תכנון ליניארי שהיא בעלת חשיבות באלגוריתמים כגון שיטת הסימפלקס.
בצורה זו מוסיפים משתני עזר (הנקראים משתני slack) כדי שתנאי הבעיה יהיו שוויונות או תנאי אי שליליות על המשתנים, וגם פונקציית המטרה בנויה ממשתנה אחד בלבד.
בכתיב מטריציוני הבעיה מוצגת כמטריצת בלוקים באופן הבא:
כאשר הם המשתנים המקוריים, הם משתני ה-slack, ו- הוא המשתנה שיש למקסם.
אז צורת ה-slack המתאימה היא:
ניתן לחשוב על הווקטורים באורך n כעל נקודות במרחב ה-n-ממדי.
במקרה זה, כל אילוץ חוצה את המרחב לשני חצאי מרחבים, כך שהפתרונות החוקיים נמצאים באחד מהם.
אוסף האילוצים יחדיו מתורגם לחיתוך של כל חצאי המרחבים הנוצרים באמצעות אוסף זה.
הצורה גאומטרית המתקבלת נקראת פוליטופ .
למשל, אם ישנם שני משתנים אז כל אילוץ יוצר חצי מישור ואם החיתוך של כל חצאי המישורים האלה חסום אז מתקבל מצולע קמור.
במרחב n-ממדי כללי, כל אילוץ באוסף יוצר חצי מרחב והחיתוך של כל חצאי המרחבים האלה יוצר פאון קמור.
משיקולי נוחות, נתייחס בהמשך ערך זה לצורות גאומטריות אלה כמצולע או פאון גם אם הן אינן חסומות ועל כן אינן מצולע/פאון במובן הרגיל.
כך גם עושים בספרות המקצועית בנושא.
קבוצת הפתרונות האופטימליים היא פוליטופ מממד קטן יותר (או שווה במקרה שהפונקציה קבועה), שנמצא בקצה הפוליטופ.
למשל, אם הבעיה ניתנת להצגה כפאון, הרי שקבוצת הפתרונות האופטמיליים יכולה להיות קודקוד של הפאון, צלע של הפאון, או פאה שלו.
בתמונה משמאל ניתן לראות הצגה גאומטרית של בעיית תכנון ליניארי בשני משתנים.
בעיה כזו אפשר להציג במרחב הדו-ממדי, כלומר במישור.
שלושת הישרים הצבעוניים הם אילוצים ליניאריים, שמחייבים את הפתרונות להיות מתחתם.
בנוסף אילוצי אי-שליליות על המשתנים גוררים שהם חייבים להיות ברביע הראשון.
האזור שהם יכולים להיות בו מסומן בצבע כחול, וניתן לראות שהוא מחומש.
תכנון ליניארי בשלמים (ILP - Integer Linear Programming) מציין בעיה דומה לבעיית התכנון הליניארי, אלא שהמשתנים חייבים לקבל ערכים שלמים דווקא.
בניגוד לבעיית תכנון ליניארי רגילה שלה יש פתרון פולינומי, בעיה זאת היא NP קשה.
הצגתה כבעיית הכרעה (האם קיים פתרון שבו ערך פונקציית המטרה עולה על ערך מסוים) היא בעיה NP שלמה.
ספירת הנקודות השלמות שמקיימות את התנאים היא בעיה P# שלמה.
זוהי אחת מהבעיות שהופיעו במאמר המפורסם של ריצ'רד קארפ מ-1972, בו הוא הציג רשימה של 21 בעיות NP שלמות.
למעשה, הבעיה אותה הציג קארפ חלשה הרבה יותר: המשתנים יכולים לקבל ערכים בוליאנים בלבד (0 או 1), ואין פונקציית מטרה למקסם – צריך לענות רק על השאלה האם קיים פתרון או לא.
הוא הציג רדוקציה מבעיית הספיקות.
כיוון שלא ידוע האם P=NP, לא ידוע האם יש אלגוריתם פולינומי לפתרון בעיית תכנון ליניארי בשלמים.
עם זאת, קיימים היום אלגוריתמים שמאפשרים לפתור רבות מהבעיות בזמן סביר, ועל כן פעמים רבות רדוקציה פולינומית מבעיה מסוימת לבעיית תכנון ליניארי בשלמים מספיקה כדי למצוא לה פתרון משביע רצון.
למעשה, את רוב הבעיות ה-NP שלמות ניתן להפוך לבעיות תכנון ליניארי בשלמים בקלות יחסית.
משום כך יש לאלגוריתמים לפתרון תכנון ליניארי בשלמים חשיבות גדולה, הן תאורטית והן מעשית, והם מאפשרים לפתור בעיות סיפוק אילוצים רבות.
ניתן גם לדרוש שרק חלק מהמשתנים יהיו שלמים; בעיה כזאת נקראת "תכנון ליניארי מעורב" (MIP - Mixed Integer Programming) והיא קשה לפחות כמו תכנון ליניארי בשלמים, כי כל בעיית תכנון ליניארי בשלמים היא בפרט גם בעיית תכנון ליניארי מעורב.
כאשר ידוע שלבעיית תכנון ליניארי יש פתרון אופטימלי שבו כל המשתנים שלמים, היא נקראת בעיית תכנון ליניארי שלמה.
עם זאת, עדיין ייתכן שיהיו לה גם פתרונות אופטימליים לא שלמים, כי יכולים להיות הרבה פתרונות אופטימליים.
זיהוי בעיה כזאת הוא חשוב, שכן במקרה זה אלגוריתם יעיל למציאת פתרון שלם יוכל לכלול פתרון הבעיה הרגילה (לאו דווקא בשלמים) וחילוץ הפתרונות השלמים מתוכה.
דוגמה לקריטריון כזה היא: בהינתן בעיה , אם המטריצה היא בעלת ערכים שלמים ויונימודולרית לחלוטין, כלומר הדטרמיננטה של כל תת-מטריצה של היא 0, 1, או 1-.
בנוסף, כל הערכים של צריכים להיות שלמים.
נניח שבמפעל מסוים רוצים לייצר שלושה מוצרים: מוצר 1, מוצר 2 ומוצר 3. לכל מוצר צריך כמות מסוימת של מים ושל חשמל כדי לייצר אותו.
כמויות המים והחשמל של המפעל מוגבלות.
כמו כן לכל מוצר יש מחיר אחר בו אפשר למכור אותו.
נניח שלמוצר ה-i צריך חשמל לקילוגרם, מים לקילוגרם, ומקבלים תמורתו שקלים לקילוגרם.
סה"כ יש למפעל חשמל ו- מים.
אז ניתן לכתוב את המשוואות הבאות:
פתרון הבעיה ימצא את המספרים , מהם ניתן למצוא את הכמויות שנייצר מכל מוצר.
נאמר שבמדינה מסוימת יש 3 נמלים ו-2 תחנות כוח.
בנמל מספר פורקים בכל יום ליטרים של נפט.
תחנת כוח מספר זקוקה ל- ליטרים כדי לפעול.
כמו כן בין נמל לתחנה יש כביש באורך (כאשר עלות ההובלה של ליטר נפט לקילומטר היא קבועה).
יש למצוא איך להזרים נפט במינימום מחיר.
כדי לפתור את הבעיה נגדיר 6 משתנים:
כאשר משתנה פירושו "כמות הליטרים שמזרימים מנמל לתחנה ".
שלושת האילוצים הראשונים הם על הנמלים - כל נמל יכול להוציא לכל היותר את כמות הנפט שיש לו.
שני האילוצים שאחר כך הם אילוצים על התחנות - כל תחנה צריכה לקבל כמות מספקת של נפט.
לאחר מכן יש אילוץ אי-שליליות (אי אפשר להעביר כמות שלילית של נפט).
פונקציית המטרה היא העלות הכוללת של השינוע ויש למזער אותה.
ניתן לראות שאם מתקיים אז אין לבעיה פתרון.
ואכן, אם בשלושת הנמלים יחד פורקים פחות נפט מהכמות שדרושה לתחנות, בוודאי אין אפשרות להזרים מספיק נפט.
בעיית כיסוי הקודקודים היא: בהינתן גרף , יש למצוא קבוצת קודקודים קטנה ביותר , כך שלכל קשת המקיימת , לפחות אחד מהקודקודים נמצא ב-.
נציג בעיית תכנון ליניארי בשלמים שפותרת אותה:
לכל קודקוד יהיה משתנה שאומר "הקודקוד ב-" אז המשוואות הן: לכל קשת , המשוואה תהיה (כלומר לפחות אחד מהקודקודים אכן ב-S).
ובנוסף נדרוש לכל קודקוד v.
(אין צורך לדרוש שכן זה בהכרח יתקיים בפתרון המינימלי, שהרי כל פתרון שבו יישאר כזה גם אם ).
יש למזער את הסכום .
הפתרון של בעיה זו בשלמים יהיה פתרון לבעיית כיסוי הקודקודים.
פתרון שאיננו בשלמים יתן לכל קודקוד משקל ממשי בין 0 ל-1, כך שסכום המשקלים לכל קשת הוא לפחות 1.
למשל, עבור הבעיה שבתמונה שמשמאל המשתנים הם והאילוצים הם בנוסף לאילוץ לכל i.
הפתרון האופטימלי הוא כך שהתוכנית הליניארית שלמה במקרה זה, ומצאה כיסוי מינימלי - {1,2,4}.
ניתן להראות גם שעבור גרף דו צדדי תמיד יהיה פתרון בשלמים, כיוון שהמטריצה יונימודולרית לחלוטין (כפי שתואר למעלה).
לעומת זאת, דוגמה בה התכנית לא מוצאת פתרון בשלמים: נניח שנתון לנו גרף משולש, כלומר שלושה קודקודים עם כל הקשתות ביניהם.
אזי התוכנית הליניארית שהצגנו תמצא את הפתרון , כלומר לא פתרון חוקי לבעיית כיסוי הקודקודים.
נדגים כיצד ניתן לפתור סודוקו באמצעות תכנון ליניארי בשלמים.
לכל שורה , עמודה וספרה ניצור משתנה שאומר "במשבצת שנמצאת בשורה , עמודה נמצאת הספרה ".
כל אחד משלושת הפרמטרים הללו הוא מקבל ערכים בין 1–9 (יש 9 שורות, 9 עמודות ו-9 ספרות בסודוקו) ולכן סך הכל יש משתנים.
משתנה שווה ל-1 אם בשורה ועמודה נמצאת הספרה , אחרת שווה לאפס.
לכל שורה ועמודה , יש בדיוק ספרה אחת שנמצאת במשבצת המתאימה, כלומר בדיוק אחד מהמשתנים מקבל את הערך 1. לכן האילוץ הוא .
לכל שורה , ולכל שתי עמודות שונות , לא ייתכן שאותה ספרה תתקבל בשתיהן (מאילוצי הסודוקו).
לכן לכל ספרה מוסיפים את האילוץ (לא ייתכן ששני המשתנים מקבלים את הערך 1 בו זמנית).
בדומה גם לכל עמודה ולכל שתי שורות שונות מוסיפים את האילוץ ולכל שתי משבצות שנמצאות באותו ריבוע 3x3, גם כן נוסיף את האילוץ .
הרמזים ההתחלתיים נותנים גם הם אילוצים.
למשל, בסודוקו שמשמאל בשורה 1, עמודה 1 נמצאת הספרה 5. אם כן המשתנה חייב לקבל את הערך 1, ואפשר להוסיף את האילוץ .
באופן כללי אם ברמזים נתון שבמשבצת שבשורה ועמודה יש את הערך , אז אפשר להוסיף את האילוץ .
נוסף לכל אלה יש להוסיף את האילוץ לכל המשתנים.
כדי לפתור את הסודוקו, יש למצוא פתרון כלשהו בשלמים למערכת האילוצים.
כלומר אין פונקציית מטרה (מבחינה פורמלית פונקציית המטרה היא הפונקציה הקבועה 0).
מפתרון זה ניתן לקרוא את הפתרון.
למשל בסודוקו שמשמאל נקבל שבפתרון המערכת מתקיים ואם כן המשבצת השלישית בשורה הראשונה מקבלת את הערך 4.
שימו לב: לא יכולנו להשתמש במשתנה כדי לקבל ישירות את הספרה שלו (למשל, שהמשתנה יקבל בפתרון את הערך 4).
הסיבה היא שצריך להוסיף, למשל, אילוצי , ולא ניתן לעשות זאת באילוצי תכנון ליניארי.
עבור הבעיה קיימת הבעיה הדואלית כאשר הוא וקטור m ממדי ו- זוהי המטריצה המשוחלפת ל-.
למעבר זה יש חשיבות תאורטית בהוכחות שונות, ובפרט בהוכחת הנכונות של אלגרותמים שונים.
בנוסף, ניתן למצוא גם קשר רעיוני בין הבעיות.
ניתן לחשוב על בעיה זאת כבעיה הבאה: הוא משתנה שמייצג חשמל, ו- משתנה שמייצג מים.
אז כל משוואה מתייחסת למוצר אחר, ומבקשת, תחת תנאי חשמל ומים, שהרווח יהיה לפחות מספר מסוים.
למשל המשוואה הראשונה מתייחסת למוצר מספר 1, בו המשוואה הראשונה דורשת שנשקיע מספיק חשמל ומים כדי לקבל את הרווח .
בדומה משוואות 2,3 מתייחסות למוצרים 2,3 בהתאמה.
תחת תנאים אלה, יש למזער את העלות הכוללת של מים וחשמל.
הבעיה הדואלית לדוגמה השנייה כוללת את המשתנים , משתנה לכל קשת, כך שלכל קודקוד יש את המשוואה ויש למקסם את .
כאשר המשתנים שלמים, הבעיה היא למצוא קבוצת קשתות מקסימלית כך שכל קודקוד נוגע בלכל היותר אחת מהן - בעיה הידועה כמציאת שידוך מקסימלי (לה יש פתרון פולינומי).
משפט הדואליות החלש קובע שאם הבעיה היא בצורה קנונית, אז הבעיה הדואלית מקיימת שלכל זוג פתרונות מתקיים , ובפרט גם לפתרונות האופטימליים.
משפט הדואליות החזק קובע שלפתרונות האופטימליים (אם הם קיימים - או שאחת הבעיות לא חסומה, ואז השנייה לא פיזיבלית).
משפט הדואליות החלש מאפשר למצוא תנאי עצירה לאלגוריתמים שונים: אם מריצים את האלגוריתם על הבעיה ועל הבעיה הדואלית לה במקביל, מקבלים חסמים מכל בעיה על השנייה: לכל שמוצאים, מהווה חסם עליון ל-, ולהפך.
ממשפט הדואליות החזק נובע משפט זרימה מקסימלית - חתך מינימלי, משפט קניג ומשפט המינימקס.
ההוכחה למשפט הדואליות החלש פשוטה למדי ודורשת מניפולציות על איברים בלבד:
כיוון ש- הוא פתרון, אז לכל מתקיים .
כמו כן, כיוון ש- הוא פתרון, לכל מתקיים .
נשלב את כל זאת כדי לקבל:
את משפט הדואליות החזק ניתן להוכיח בעזרת הלמה של פרקס.
בעיה בצורה קנונית נקראת "בעיית אריזה" אם כל ערכי המטריצות והווקטורים הם בעלי ערכים אי שליליים.
הסיבה לכינוי זה היא שאנחנו מנסים למקסם את מה שאנחנו מכניסים לערכים תוך מגבלה מלמעלה - כמו אדם שמנסה לארוז כמה שיותר לתוך נפח מוגבל.
בעיה בצורה הדואלית, , תקרא "בעיית כיסוי" אם היא מקיימת תכונה זו.
הסיבה לכינוי זה היא שאנחנו מנסים למצוא ערכים קטנים ביותר שיעברו סף מסוים - מנסים לכסות את הערכים ב-.
לבעיות אלה חשיבות מיוחדת, בפרט בשלמים, ואלגוריתמים רבים פותחו במיוחד בשבילן.
דוגמאות לבעיות אריזה הן בעיית תרמיל הגב, מציאת קבוצה בלתי תלויה מקסימלית, בעיית אריזת קבוצות (set packing) ובעיית אריזת הדליים (bin packing).
דוגמאות לבעיות כיסוי הן בעיית כיסוי קודקודים ובעיית כיסוי קבוצות.
האלגוריתם הוותיק ביותר הוא אלגוריתם הסימפלקס.
למעשה הוא לא אלגוריתם במובן הרגיל אלא משפחה של אלגוריתמים, שכן אחד הצעדים בו לא מוגדר וניתן לממש אותו בדרכים שונות.
האלגוריתם הומצא בשנת 1947 על ידי ג'ורג' דנציג.
האינטואיציה מאחורי השיטה מתקבלת מההצגה הגאומטרית לעיל.
כאמור, מרחב הפתרונות הפיזיביליים הוא פוליטופ קמור.
ניתן לראות שאם נעים על קו ישר, פונקציית המטרה הליניארית היא מונוטונית על הקו הזה.
מכאן נובע שהערך המקסימלי יתקבל על אחד הקודקודים (אלא אם הפוליטופ לא חסום).
שיטת הסימפלקס היא: מתחילים מקודקוד כלשהו, מסתכלים על הקודקודים שמחוברים אליו בצלע, בוחרים אחד מהם עליו פונקציית המטרה גדולה או שווה, ועוברים אליו (צעד המעבר נקרא pivot).
לא עוברים אל קודקוד שכבר היינו בו.
אם האלגוריתם מסתיים, זה כיוון שאין קודקודים יותר גדולים לעבור אליהם, וסיימנו בהצלחה.
כיוון שמספר הקודקודים סופי, האלגוריתם יסתיים בזמן סופי.
זמן ריצת האלגוריתם: צעד pivot לוקח , לכן זמן הריצה הוא , כאשר הוא מספר הצעדים שנעשה.
חסום על ידי מספר הקודקודים שעלול להיות אקסופננציאלי, לכן זמן הריצה עלול להיות אקספוננציאלי.
עד היום לא ידועה שיטה פולינומית לממש את זמן הריצה (אך גם לא ידוע שאין שיטה כזאת), ויש חסם תחתון אקספוננציאלי על רבות מהשיטות.
השיטה נמצאה ב 1979 על ידי לאוניד חצ'יאן, והיוותה פריצת דרך תאורטית גדולה בכך שהוכיחה זמן ריצה פולינומי, אך איננה מעשית לערכי n שאינם קטנים מאוד.
בשיטה מתחילים מאליפסואיד גדול מספיק כדי להכיל את הנקודה המינימלית, ואז בסדרת צעדים מקטינים את האלפיסואיד כך שהוא עדיין כולל אותה, עד שהאליפסואיד קטן מספיק.
האלגוריתם רץ בסיבוכיות , כאשר הוא אורך הקלט - מספר הביטים שצריך כדי לתאר את כל הבעיה.
אלגוריתם שנמצא על ידי המתמטיקאי ההודי נרמנדה קרמרקר בשנת 1984. אף על פי שלא היה האלגוריתם הפולינומי הראשון, הוא היה האלגוריתם הפולינומי הראשון שרץ בזמן מעשי (אף על פי שבדרך כלל שיטת הסימפלקס עדיפה על קלטים אמיתיים).
האלגוריתם נקרא גם "שיטת הנקודה הפנימית" (interior point method) משום שהוא "מחפש" את הנקודה האופטימלית בפנים הפוליטופ, ולא על שפתו כמו שיטת הסימפלקס.
נכון ל-2022, האלגוריתם הטוב ביותר הידוע רץ בסיבוכיות , כאשר הוא המעריך של ביצוע כפל מטריצות, כלומר כזה שניתן עבורו להכפיל מטריצות בסיבוכיות (נכון ל-2022, ידוע ), ו- הוא המעריך הדואלי של כפל מטריצות, כלומר המספר המקסימלי עבורו ניתן להכפיל מטריצות בגודלי בזמן (נכון ל-2022, ידוע ).
כאמור לעיל, הבעיה בשלמים היא NP קשה, לכן בהנחת , אין לה אלגוריתם פולינומי, אפילו אם לא מנסים למקסם פונקציית מטרה.
לכן אלגוריתמים לפתרון תכנון ליניארי בשלמים עושים את אחד הדברים הבאים:
רצים במקרה הגרוע בזמן אקספוננציאלי (במטרה שעל קלטים סבירים יסיימו בזמן סביר).
מוצאים פתרון שלא מקיים את כל האילוצים (במטרה למצוא פתרון שיקיים כמה שיותר).
רצים רק על קלטים שמקיימים הנחות כלשהן.
דורשים הרצה פעם אחת של אלגוריתם בזמן אקספוננציאלי, שמאפשרת מציאת מידע איתו יהיה אפשר לפתור בעיות רבות בזמן פולינומי.
רצים במקרים בהם ברור שיש פתרון (למשל, לבעיות אריזה תמיד קיים פתרון ה-0. לבעיות כיסוי תמיד יש פתרון בו כל המשתנים מקבלים את הערך המקסימלי של הווקטור ) ומנסים לקרב את פונקציית המטרה.
שימוש באלגוריתם של בעיית תכנון ליניארי רגילה יניב פתרון שאיננו דווקא בשלמים.
במקרה זה יש כמה דרכים לקבל ממנו פתרון רגיל.
אפשר למשל, לעגל את כל המשתנים אל הערך הקרוב ביותר.
אפשר גם במקרה של המשתנים הם אינדיקטורים (מקבלים ערכים בין 0 ל-1), עבור משתנה שקיבל את הערך , להגריל לו את הערך 1 בהסתברות ו-0 בהסתברות .
שיטות אלה יכולות להוביל לפתרונות שאינם מקיימים את כל האילוצים, או שאינם אופטימלים.
בבעיות אריזה, אם מעגלים את כל הערכים למטה, מקבלים פתרון חוקי (כי כל הערכים נשארו אי שליליים, ואי-הגדלה של כל המשתנים לא יכולה לסתור אילוץ).
הוא עשוי להיות קטן מהפתרון האופטימלי, אך אם פונקציית המטרה היא , ניתן לדעת שעיגול כל הערכים למטה יקטין כל משתנה בלכל היותר 1, ולכן יקטין את פונקציית המטרה בלכל היותר .
בדומה, עיגול למעלה של כל הערכים בבעיית כיסוי ימצא פתרון חוקי שפונקציית המטרה עליו עשויה להיות רחוקה ב- מהערך האופטימלי.
קיימים גם אלגוריתמים יותר מתוחכמים, למשל שיטת branch and cut, בה מוסיפים אילוצים נוספים כדי לכפות על המשתנים להיות שלמים, ובמידת הצורך מפצלים את הבעיה לכמה תתי בעיות, תוך "גדיעת" ענפים - לא נכנסים לתתי בעיות שאפשר לראות שלא יהיו טובות יותר מאחרות שניסינו כבר.
שיטה זאת תמיד מוצאת את הפתרון האופטימלי וגם יעילה למדי על קלטים אמיתיים, אך זמן הריצה במקרה הגרוע הוא אקספוננציאלי.
את כל השיטות הללו ניתן להפעיל גם על חלק מהמשתנים במקרה שרק על חלקם יש דרישת שלמות.
בהינתן מטריצה A בשלמים, בסיס גרייבר מאפשר לבצע עליה עיבוד מוקדם (שזמנו אקספוננציאלי) כדי לקבל מידע, בעזרתו יהיה אפשר לפתור את הבעיה בזמן פולינומי לכל וקטורים שלמים .
השיטה מבוססת על מציאת קבוצה סופית של איברים (שנקראת בסיס גרייבר), שמהם ניתן לחלץ פתרונות באמצעות אלגוריתם איטרטיבי.
אלגוריתם לנסטרה מאפשר לפתור את הבעיה בזמן פולינומי כאשר מספר המשתנים קבוע.
יותר בפירוט, אם ב-A יש שורות והמקדמים שלה חסומים על ידי , האלגוריתם מאפשר לפתור בזמן פולינומי ב-.
האלגוריתם עובר על המשתנים בזה אחר זה ומוצא קטע לכל אחד מהם בו הוא חסום בעזרת גאומטריה של מספרים, ולאחר מכן עובר על כל האפשרויות.
האלגוריתם הומצא על ידי הנדריק לנסטרה בשנת 1983. זמן הריצה המקורי היה , ומאז שופר כמה פעמים.
ניתן להשתמש באלגוריתמים כלליים, שאינם מיוחדים דווקא לתכנון ליניארי.
backtracking (לבעיות אריזה): בהינתן משתנה , והצבות לערכים , נציב ב את הערכים מ-0 ומעלה בזה אחר זה, ולכל אחד מהם נפתור רקורסיבית עבור המשתנה הבא.
מפסיקים כאשר אחד האילוצים נשבר.
אם (ומצאנו הצבה שנותנת פתרון חוקי) זוכרים את ערך פונקציית המטרה, כדי להחזיר את הערך המינימלי.
האלגוריתם מסתיים כאשר עוברים על כל הערכים עבור (ואז הפתרון מדויק, אך הזמן עלול להיות אקספוננציאלי) או כאשר עובר זמן שהוגדר מראש (ואז הוא לאו דווקא ימצא את הפתרון האופטימלי).
להתחיל עם פתרון כלשהו ולשפר אותו בעזרת אלגוריתמים כגון חיפוש מקומי או אופטימיזציית קן הנמלים.
שיטות שונות של למידת מכונה, למשל רשת עצבית מלאכותית.
העיסוק בבעיה התפתח באופן נפרד במערב ובברית המועצות.
הראשון שעסק בבעיה היה לאוניד קנטורוביץ', שב 1939 ניסח את הבעיה הכללית וחקר דרכים לפתור אותה.
הוא פרסם את מחקרו במאמר בשם "שיטות מתמטיות לארגון ותכנון של הייצור" בו הוא נתן דוגמאות שונות ושיטות לפתרון.
הוא טען שתכנון ליניארי נצרך רק בכלכלה קומוניסטית, כיוון שבכלכלה קפיטליסטית בעלי ההון ידאגו להקצאת משאבים.
במהלך מלחמת העולם השנייה הוא ניסה לרתום את מחקריו למאמץ המלחמתי, אך זכה להתעלמות בברית המועצות.
מעט אחר כך, צ'אלינג קופמאנס עסק בארצות הברית באופן בלתי תלוי בבעיה.
ב-1975 חלקו קנטורוביץ' וקופמאנס פרס נובל לכלכלה על מחקרם בנושא.
ב-1946 חקר את הבעיה ג'ורג' דנציג, במסגרת עבודתו בחיל האוויר האמריקאי על בעיות לוגיסטיקה, כהכללה של שיטותיו של וסילי לאונטיף על מידול בעיות כלכליות באמצעות מטריצות.
הוא עבד על הבעיה עם קומפאנס, וב-1947 פיתח את שיטת הסימפלקס.
כמו כן, בשנת 1948 הציג דנציג את מחקרו בפני ג'ון פון נוימן.
בתגובה, פון נוימן הציג לו את מחקרו על תורת המשחקים ואת הקשר שזיהה בין מחקר זה לבין הדואליות של תכנון ליניארי, ושיער את משפט הדואליות החזק.
דנציג הוכיח את המשפט אך פרסם בתפוצה פנימית בלבד.
הראשונים שפרסמו הוכחה פורמלית ברבים היו תלמידיו של פון נוימן - אלן טאקר, דייוויד גייל והרולד קון.
במשך שנים לא היה ידוע האם יש לבעיה גם פתרון פולינומי.
בעיה זאת נפתרה ב-1979 כאשר ליאוניד חצ'יאן מצא את שיטת האליפסואיד.
התגלית היוותה סנסציה, וכונתה במערב "הספוטניק של 1979".
על אף פריצת הדרך התאורטית, האלגוריתם לא מעשי.
עם זאת, בשנת 1984 מצא נרמנדה קרמרקר אלגוריתם פולינומי ומעשי שמכונה "שיטת נקודות הפנים".
הבעיה המשיכה להיות מוקד של מחקר פעיל, ובמהלך השנים הבאות זמן הריצה שופר שוב ושוב, למשל בשנת 1987 ובשנת 1989 על ידי פרווין פאידה.
גם תכנון ליניארי בשלמים נחקר כבר על ידי דנציג, שנתן כדוגמה בעיית השמה של 70 משימות ל70 אנשים, תוך אילוצים שונים, בעיה שאיננה ניתנת לפתרון באמצעות כוח גס (בוודאי לא באמצעים של אז, וגם לא כיום), מאחר שלשם כך דרוש לבדוק 70 עצרת אפשרויות.
לאחר הוכחת משפט קוק לוין, התברר שישנן בעיות NP שלמות ושתכנון ליניארי היא בעיה כזאת, וב-1972 כלל אותה קארפ במאמרו בו הציג בעיות NP שלמות.
מאז נעשה מחקר רב בנושא, אך פתרון פולינומי לא נמצא.
מפאת חשיבותה המעשית של בעיית התכנון הליניארי, פותחו כלים רבים המאפשרים פתרון של הבעיה, עבור שפות שונות, גם באקדמיות, גם באופן מסחרי וגם באופן וולנטרי.
תוכנה שמאפשרת פתרון מעשי של בעיות תכנות ליניארי נקראת LP solver.
דוגמה ל-LP solver היא cvxpy, אשר נכתב עבור שפת פייתון בקוד פתוח.
נראה כדוגמה תוכנה שתפתור את הבעיה שניתנה בתחילת הערך:
במדעי המחשב, שיטת התכנון הדינמי לבניית אלגוריתם, שהוצגה לראשונה בשנת 1953 על ידי ריצ'רד בלמן, היא שיטה לפתרון בעיות בעלות תת-מבנה מיטבי שאי אפשר לפתור אותן באופן יעיל בשיטת הפרד ומשול נאיבית.
שיטת הפרד ומשול נאיבית פותרת בעיה על ידי חלוקתה לתת-בעיות, הנפתרות בתורן על ידי חלוקתן לתת-בעיות קטנות אף יותר, עד שמתקבלות בעיות קטנות מספיק שניתן לפתור אותן באופן ישיר.
בעיות מסוג זה מתאפיינות בכך שלאחר חלוקתן למספר תת-בעיות, מתגלה כי יש תת-בעיות חופפות .
פתרון המבוסס על הפרד ומשול נאיבי פותר את תת-הבעיות החופפות מספר פעמים, פעם אחת עבור כל תת-בעיה, מה שעלול לגרום לכך שהפתרון של הבעיה המקורית יתבצע בסיבוכיות גבוהה מאוד.
האלטרנטיבה שמציעה שיטת התכנון הדינמי היא פתרון של כל תת-הבעיות בזו אחר זו, כאשר פתרון כל אחת מתת-הבעיות נשמר עבור שימוש עתידי.
באופטימיזציה מתמטית תכנות דינמי מתממש על ידי הגדרת פונקציות ערך V התלויות במשתנה מצב y כאשר V ידועות עבור השלב ההתחלתי ו V בשלב הסופי נותנות את הפתרון.
פונקציות V נבנות בצורה רקורסיבית כאשר בניית V של שלב n מתקבלת בצורה רקורסיבית מהשלבים הקודמים על ידי משוואת בלמן.
מקורם של אלגוריתמים בשיטת התכנון הדינמי הוא בבעיות שיש להן פתרון רקורסיבי, אך הפתרון הרקורסיבי הישיר אינו יעיל, מאחר שהוא דורש שאותן תת-בעיות תפתרנה שוב ושוב.
אם מספר תת-הבעיות הקיימות הוא "קטן יחסית", כלומר פולינומי, ניתן לפתור את הבעיה באמצעות תכנון דינמי.
דוגמאות לבעיות שתכנון דינמי הוא כלי אלגוריתמי חשוב לפתרונן: חישוב מרחק לוינשטיין, עימוד רצפים בביואינפורמטיקה, בעיית תרמיל הגב (סיבוכיות זמן פסאודו-פולינומית) וחישוב הסתברות לרצף תצפיות במודל מרקוב חבוי.
קווי פעולה למציאת אלגוריתם בשיטת התכנון הדינמי
מגלים כי זמן ריצת האלגוריתם הרקורסיבי (הפועל "מלמעלה למטה") הוא מעריכי.
מגלים כי מספר תת-הבעיות הקיימות הוא פולינומי, והסיבה לסיבוכיות המעריכית היא קריאות חוזרות לאלגוריתם עבור אותה תת-בעיה שכבר נפתרה.
פותרים את הבעיה על ידי פתרון כל תת-הבעיות – ממקרי הקצה שפתרונותיהם ידועים מראש ("כלפי מעלה") – עד שמגיעים לבעיה המקורית.
חישוב איבר כללי בסדרת פיבונאצ'י
סדרת פיבונאצ'י היא סדרה המוגדרת באמצעות נוסחת הנסיגה הבאה:
כאשר שני האיברים הראשונים בסדרה נתונים:
חישוב רקורסיבי, "מלמעלה למטה", של באמצעות כלל הנסיגה אפשרי, אבל בזבזני מאוד, מאחר שערכי הסדרה הראשונים יחושבו פעמים רבות (מספר מעריכי של פעמים).
לדוגמה, נחשב בצורה זו את האיבר החמישי בסדרה בצורה זו:
קל לראות בדוגמה זו שהערך מחושב שוב ושוב פעמים רבות, ושהחישוב ייעשה בלתי יעיל להפליא עבור ערכים גדולים של .
אלגוריתם תכנון דינמי לפתרון הבעיה יעבוד בכיוון ההפוך – הוא ינוע מערכי הקצה לערך הרצוי על ידי חישוב סדרתי של כל מספרי פיבונאצ'י עד אליו.
למשל עבור הדוגמה הקודמת שלנו, כאשר האלגוריתם יפעל כך:
חישוב באמצעות (שחושב בצעד הקודם) ו- (הנתון).
חישוב באמצעות (שחושבו בצעדים הקודמים).
ניתן לשים לב שבעוד שהאלגוריתם הרקורסיבי שתואר קודם לכן ביצע 9 קריאות רקורסיביות, האלגוריתם החדש ביצע 3 צעדים בלבד, מאחר שחישב את כל אחד מהערכים
בדרך זו ניתן לחשב את פונקציית פיבונאצ'י של כל מספר n בסיבוכיות ליניארית וזאת באמצעות "זכירה" של 2 מספרים בלבד.
המונח תכנון מס (או הימנעות חוקית ממס) מתאר פעולות שונות כגון לאקונות משפטיות ותעלולים פרשניים, על-מנת להפחית את חבות המס של יחיד או חברה.
בהינתן אפשרויות שונות לביצוע פעולה מסוימת, מתכנן המס משווה את גובה המס הנדרש בכל אחת מדרכי הביצוע האפשריות, במטרה לבחור את דרך הפעולה, שתניב את תוצאות המס הטובות ביותר עבורו.
מתן משקל לתוכניות עתידיות – בתכנון מס יש לייחס משקל נכבד לתוכניות עתידיות.
התחשבות בחידושי החקיקה והפסיקה – תכנון מס חייב שייעשה גם בהתאם לחידושי הפסיקה.
בחירת העסקה המתאימה – מגוון העסקאות הפוטנציאליות הוא רחב – יש לבחור את העסקה דלת המס ביותר.
הפחתת סכומי המיסים – קיימות דרכים שונות להפחית את סכומי המס, לעיתים אף בסיטואציות אבסורדיות.
נקיטת פעולות משפטיות מקדמיות – פעמים רבות רצוי להקדים ולנקוט בצעדים משפטים לרבות ביצוע עסקאות, על מנת להבטיח פוזיציה מתאימה בטרם ההתקשרות בעסקה.
תוכנית מס חייבת להקיף את כל המיסים הרלוונטיים, כדי להביא לתוצאות מס אופטימליות.
במקרה של פעילות בין-לאומית, יש להביא בחשבון את חוקי המיסוי בכל המדינות הרלוונטיות.
התווית עסקה שתעמוד במבחן משפטי – נדרשת הקפדה על בחירת מבנה התקשרות נכון, ועל ניסוח הוראות מתאימות בחוזה, על מנת שהעסקה לא תוכרז כמלאכותית, או תסווג בדרך שונה מהמבוקש.
כך גם יוצרים תשתית עובדתית מוצקה לטיעון אפשרי בהשגה או בערר על בסיס הפסיקה הקיימת.
זכותו של הנישום לתכנן את מיסיו מוכרת בשיטות מס רבות, ובכללן שיטת המס הישראלית.
זכות זו גם מאפשרת לנישום לערוך תכנון מס בין-לאומי, אשר במקרים רבים יגרום לכך שחבות המס שלו תהיה קרובה לאפס.
בישראל, אמר על כך נשיא בית המשפט העליון, מאיר שמגר:
בפסק דין פרומדיקו הסבירה השופטת פרוקצ'יה כי בדיני המס קיים קו הבחנה בין "תכנון מס לגיטימי" לבין "התחמקות ממס" האסורה על פי החוק.
תכנון מס והתחמקות ממס שתיהן נועדו להפחית מס, אך המבדיל ביניהם הוא השוני באמצעים שנעשה בהם שימוש – הנמנע ממס ייזקק לאמצעים חוקיים בלבד וינקוט בראש וראשונה גילוי מלא ואמיתי של כל העובדות, בעוד המתחמק ממס ישיג את מטרתו בדרך של הפרת החוק שעיקרה הסתרת עובדות והעלאת מצגי שווא.
עסקה מלאכותית היא פעולה שמטרתה היא הפחתת נטל המס אך אין הצדקה אחרת לקיומה.
בפקודת מס הכנסה סעיף 86 נקבע:
סעיף זה דומה מאוד לסעיף 84 לחוק מיסוי מקרקעין (שבח ורכישה).
בהתייחסו לפסקה זו מציין השופט זילברג שלפי המשפט העברי לא רק שעסקה כזו אינה תקפה, אלא אף אסורה, בדבריו הוא מדגיש את היחס השלילי הניתן במשפט העברי להתחמקות ממס.
תכנון ערים ואזורים הוא תחום ידע, מדע ומחקר, לימוד ועיון העוסק בתיעוד, פיתוח עירוני ואזורי, תכנון פיזי, חברתי וכלכלי של ערים, גושי ערים, שכונות, או של מועצות אזוריות המתייחסת אל אזור מסוים של יישובים חקלאיים כגון: כפרים, מושבים, קיבוצים או מושבות.
על אף שנדמה שישנה חפיפה בין תכנון ערים למקצועות אחרים כגון: אדריכלות, אדריכלות נוף, עירוניות נוף, ועיצוב עירוני, לא כך הדבר, שכן במקצועות אלו עוסקים ביתר פירוט ובקנה מידה קטן יותר של פיתוח ואילו תכנון אזורי עוסק בסביבה רחבה יותר וברמה פחות מפורטת.
מתכנן הערים היווני היפודמוס נחשב לאבי התכנון העירוני, בשל התכנון של מילטוס, אם כי דוגמאות לערים מתוכננות קיימות בכל העת העתיקה.
המוסלמים נחשבים למקור הרעיון של הקצאת תפקידים שונים לאזורים שונים, אם כי השימוש המערבי בכך מגיע בעיקר מהרעיונות של ה"קונגרס הבין-לאומי לאדריכלות מודרנית".
מבחינה היסטורית, מקורו של התכנון העירוני באדריכלות ובהנדסה האזרחית, והוא משתמש בגישה רציונלית ביותר לפתרון בעיות עירוניות על ידי תכנון פיזי.
אולם, מספר רעיונות של מבקרים של התכנון העירוני המודרניסטי שצברו תנופה בשנות ה-60 (לדוגמה, אלה של ג'יין ג'ייקובס) עזרו להרחיב את התחום של התכנון העירוני לכלול גם תכנון פיתוח כלכלי, תכנון קהילתי חברתי ותכנון סביבתי.
תרבות עמק האינדוס בתת היבשת ההודית נחשבת כתרבות הראשונה שפיתחה את התכנון העירוני.
עד ל-2600 לפנה"ס כמה יישובים קדם-האראפיים גדלו לערים בעלי אוכלוסייה של אלפי אנשים שלא עסקו בעיקר בחקלאות, ויצרו תרבות מאוחדת שעלייתה הפתאומית הייתה תוצאה של מאמץ מתוכנן.
נראה כי היה ארגון מחדש של חלק מהיישובים על מנת להתאימם לתוכנית מפותחת היטב.
מסיבה זו, תרבות עמק האינדוס נחשבת כראשונה שפיתחה את התכנון העירוני.
במאה הרביעית והשלישית לפנה"ס, הופצה התרבות ההליניסטית בשטחים שכבש אלכסנדר מוקדון.
במסגרת הפצת התרבות הוקמו ערים הלניסטיות אשר התאפיינו בתכנון היפודאמי.
התכנון ההיפודאמי קבע רשת רחובות רוחביים ואורכיים שיצרו משבצות המכונות אינסולות.
תכנון עירוני זה שיקף את החשיבה הרציונלית של התקופה וקבע מערכת מאוד רציונלית שכאילו שיטחה את הקרקע ובנתה עליה עיר מתוכננת היטב.
התכנון ההיפודאמי היה למעשה התכנון שבעקבותיו תוכננו גם אלפיים שנה מאוחר יותר ערים רבות ביבשת אמריקה.
הרומאים השתמשו בתוכנית קבועה עבור תכנון הערים שלהם, שפותחה ליעילות צבאית ואזרחית מקסימלית.
תכנון זה התחיל בשני רחובות ראשיים הניצבים אחד לשני ומפגשם הוא המרכז הרשמי של העיר.
הציר האורכי שעבר מצפון לדרום נקרא "קארדו" והציר הרוחבי ממזרח למערב נקרא "דקומנוס".
רוב השירותים העירוניים סבבו את מרכז העיר המוקף ברשת מרובעת צפופה של רחובות, וסביבן חומה להגנה.
על מנת להפחית את זמן התנועה ברחובות, שני רחובות אלכסוניים חוצים את רשת הרחובות המרובעת מפינה לפינה, דרך הרחבה המרכזית.
נהר בדרך כלל חוצה את העיר, מספק מים ותחבורה ומסלק ביוב, אפילו בזמן מצור.
ערים אירופאיות רבות עדיין משמרות את התבנית הזו, לדוגמה בטורינו.
גם בעיר העתיקה של ירושלים השתמר במידה חלקית תכנון זה מהתקופה הרומית והרחוב הראשי עדיין נקרא "הקארדו".
בתכנון העירוני בתרבות המוסלמית ישנו מושג חשוב הנקרא "חרם" (אזור שאסור לחלל).
אזורים כאלו היו מנזרים, או מקומות בהם מפלגות יריבות יכלו ליישב חילוקי דעות בשלום.
בדרך כלל היו אלו עיירות שנבנו ליד נהר אשר סיפק מים לשתייה לשימושים ביתיים (במעלה הזרם) ונשאו משם פסולת וביוב (במורד הזרם, בדרך כלל מתחת לאדמה, שלא כמו ברוב הערים באירופה בימי הביניים).
מבחינה זו, הכללים מזכירים חוקי תכנון מודרניים מבחינת מטרותיהם.
במהלך שתי המאות האחרונות בעולם המערבי (מערב אירופה, צפון אמריקה, יפן ואוסטרלאסיה) תכנון ואדריכלות עברו שלבים שונים של קונצנזוס רחב.
בתחילה הייתה העיר המתועשת של המאה ה-19, שם השליטה בבניינים הייתה בעיקר בידי עסקים והאליטה העשירה.
בערך עם תחילת המאה ה-20 החלה תנועה שמטרתה לספק סביבה בריאה יותר לאנשים, ובעיקר לעובדי תעשייה.
פותחו הרעיונות של ערי גנים והעיר היפה ונבנו כמה ערים לדוגמה, כמו וולוון גארדן סיטי באנגליה.
אולם, אלה היו בדרך כלל קטנות יחסית ולא היו בהן תושבים רבים.
רק בשנות ה-20 של המאה ה-20 החלה לעלות תנועת המודרניזם.
עיר מודרניסטית הייתה אמורה להיות סוג של אוטופיה ישימה ויעילה.
היו תוכניות לבנייה מחדש בקנה מידה גדול של ערים, כמו פריז, אם כי לא קרה דבר בקנה מידה גדול עד להרס שנגרם בעקבות מלחמת העולם השנייה.
לאחר מכן, נבנו כמה מבנים וקהילות מודרניסטיים.
אולם הם נבנו בזול והיו ידועים בבעיות החברתיות שנוצרו סביבם.
המודרניזם הסתיים בשנות ה-70 כשהפסיקו לבנות מגדלים אחידים וזולים בארצות רבות, כמו בריטניה וצרפת.
מאז רבים מהם נהרסו ובמקומם נבנו בניינים מסוגים אחרים.
במקום לעשות הכול מושלם ואחיד, התכנון כיום מתמקד באינדיבידואליזם ובגיוון של החברה והכלכלה.
לאחרונה הועלה נושא של תכנון ערים רב-תרבותיות, התמודדות ערים עם קליטת מהגרים, תאוריות של תכנון בעזרת דיאלוג בין קבוצות אתניות שונות ובדרכים חדשות של חשיבה על תכנון עירוני לאור אופיין המשתנה של ערים בעידן הגלובלי.
סוגיות אלו מנותחות בעבודות של ליאוני סנדרקוק.
בארצות מפותחות התעוררה תגובת-נגד לכמות גדולה מדי של גורמים מלאכותיים בסביבה – כמו שלטים, גדרות זמניות, וכדומה.
נושאים אחרים שיש עליהם מחלוקת חריפה בין מתכננים עירוניים הם המתח בין גידול פריפריאלי, גידול בצפיפות הדיור ותכנון יישובים חדשים.
יש גם דיונים רבים לגבי היתרון של ערבוב ייעודים שונים של הקרקע, כנגד היתרונות של הבדלה בין קרקע בעלת ייעודים שונים.
תכנון עירוני מוצלח מתחשב באופי של "בית" ו"תחושת מקום", זהות מקומית, כבוד למורשת הטבעית, האמנותית וההיסטורית, הבנה של הנוף העירוני, הולכי רגל וסוגי תחבורה אחרים, סיכונים טבעיים כמו אזורי שיטפון ועוד.
יש שאומרים שהפיאצה (רחבה) הימי ביניימית והארקדה (שורת עמודים בחזית המבנה הפונה לרחוב) הן בין האלמנטים המוצלחים ביותר של תכנון עירוני, כפי שרואים בערים איטלקיות כמו סיינה ובולוניה.
אף שלרוב ערים אינן מתוכננות מתחילתן, התכנון חשוב בשליטה על גידולן של ערים ושימוש בכלים כמו חלוקה לאזורים.
בהסתכלות היסטורית, ערים רבות שנחשבות ליפהפיות הן תוצאה של מערכות ארוכות טווח של איסורים והדרכה לגבי גודל הבניה, שימוש ומאפיינים.
אלה הותירו חופשיות מסוימת, אך עם זאת אכפו את השימוש בסגנונות מסוימים, בטיחות ולעיתים גם חומרים בדרכים מעשיות.
ישנן ערים שתוכננו מתחילתן, ואם כי התוצאות אינן תמיד כמו שתוכננו, לרוב נותרות עדויות לתכנון הראשוני.
כמה מהערים המתוכננות המוצלחות ביותר מורכבות מתאים שכוללים אזורי פארק, מסחר ודיור, כשהתא חוזר פעמים רבות.
לרוב התאים מובדלים על ידי רחובות.
בדרך כלל, לכל תא יש מבנים מיוחדים וגינון מיוחד בפארק, ושערים מיוחדים או מסמני גבול בקצה.
האזורים המסחריים נעשים מגוונים באופן טבעי.
הבדלים אלה עוזרים לנטוע תחושה של מקום, כאשר הדמיון בין התאים גורמים לכך שכל מקום בעיר מוכר במידת מה.
תכנון בטיחותי ועמידות בפני סיכונים
ערים רבות נבנות במקומות שנתונים לשיטפונות, גלי סערה, מזג אוויר יוצא דופן או מלחמה.
אם ניתן להגביל סכנות אלה לאזורים מסוימים (כמו אזורים המועדים לשיטפון), אפשר לעשות מהם אזורי פארק או חגורות ירוקות, דבר שמביא תוצאות יפות לעיתים.
שיטה מעשית נוספת היא לבנות את העיר על פסגות ההרים, ואת הפארקים בעמקים.
ניתן להפחית את הפגיעה של מזג אוויר קיצוני, שיטפון, מלחמה או מצבי חירום אחרים על ידי דרכי הימלטות בטוחות ומרכזי חירום.
אלה אינם יקרים במיוחד, ורבים רואים בהם אמצעי ביטחון הכרחי לכל אזור עירוני.
ישנן שיטות תכנון שעשויות לעזור לקבוצות אליטה לשלוט על האזרחים הרגילים.
מצב זה היה קיים לדוגמה ברומא, שם הפשיסטים יצרו פרוורים חדשים רבים על מנת לרכז את הפושעים והמעמדות הנמוכים בריחוק מהעיר האלגנטית.
מצופה מהמתכננים שימקסמו את הנגישות לאזור לאנשים עם יכולות ומוגבלויות שונות, לצפות מראש אזורים של פשע ולנסות למנוע אותו כבר בשלב התכנון, ולהשתמש באזורים אסורים לכניסת כלי רכב, על מנת להקל על החיים העירוניים.
תכנון עירוני מנסה לשלוט על פשיעה על ידי מבנים שתוכננו בעזרת תאוריות כמו סוציאל-אדריכלות או דטרמיניזם סביבתי.
תאוריות אלה טוענות שהסביבה העירונית יכולות להשפיע על הנאמנות של אינבידואל לחוקים חברתיים.
התאוריות טוענות שלחץ פסיכולוגי מתפתח באזורים צפופים יותר ופחות יפים.
מתח זה גורם לחלק מהפשעים ולשימוש מסוים בסמים.
התרופה היא מרחב אישי גדול יותר ועיצוב ותכנון טובים ויפים יותר, במקום פונקציונליזם.
תאוריות חברתיות אחרות מצביעות על כך שבאנגליה וברוב הארצות מאז המאה ה-18, השינוי של חברות מחקלאיות לתעשייתיות גרמו לקושי בהתאקלמות לחיים עירוניים.
תאוריות אלה מדגישות את העובדה שלעיתים מדיניות התכנון מתעלמות ממתחים אישיים, ומכריחים אנשים לחיות יחד בצורות לא נוחות.
לפיכך, אנשים רבים אינם מרגישים "בבית" גם כשהם בבית.
קיים קשר ישיר וברור בין הצפיפות של הסביבה העירונית לבין כמות התחבורה באותה הסביבה.
תחבורה באיכות גבוהה מביאה לעיתים קרובות לפיתוח.
פיתוח מעבר לצפיפות מסוימת עשוי להביא לצפיפות יתר בתחבורה.
תכנון טוב מנסה לכוון את הצפיפות הגבוהה של עבודה או מגורים ליד תחבורה ברמה גבוהה.
לדוגמה, יש ערים שמאפשרות מסחר ובניינים רבי-קומות רק מהלך רחוב אחד מתחנות רכבת או כבישים רחבים, ואת המבנים הקטנים יותר והפארקים שמים במקומות מרוחקים יותר.
הצפיפות בדרך כלל נמדדת כשטח הרצפה של בניינים חלקי שטח הקרקע, או, במקרה של דיור, על ידי מספר יחידות הדיור חלקי שטח הקרקע.
יחס של 1.5 הוא נמוך מאוד, ויחס של 5 הוא גבוה מאוד.
ברוב האזורים שמחוץ לעיר היחס הוא מתחת לשתיים, ואילו ברוב מרכזי הערים היחס הוא לפחות 5. בניינים של ארבע או חמש קומות לרוב מגיעים לצפיפות של 3 בערך, וגורדי שחקים – ל-30 או יותר.
צפיפות גבוהה רווחית מאוד ליזמים ולקבלנים.
הרשויות העירוניות מנסות לעודד צפיפויות נמוכות על מנת להוריד את מחירי התשתית, אם כי צפיפות נמוכה מדי אינה מאפשרת מספיק אוכלוסייה בשביל התשתית הזו.
בבריטניה נעשה ניסיון מרוכז להעלות את צפיפות המגורים על מנת להגיע לפיתוח רב יותר.
העלאה של הצפיפות גם מגדילה את היעילות של תחבורה, של חימום אזורי ושל שירותי-קהילה אחרים (בתי ספר, מרכזי בריאות וכדומה).
אולם מבקרים של גישה זו קוראים לה "דחיסת ערים" וטוענים שהיא מורידה את רמת החיים ואינה מאפשרת למתגוררים בעיר את החלום הפרוורי של בית עם גינה ועם שטח חניה קרוב.
בצפיפות של עד 1.5 רכב פרטי הוא אמצעי תחבורה יעיל גם עם כבישים בסיסיים יחסית.
רעיונות חדשניים כמו נתיבי תחבורה מיוחדים או נתיבים לשעת שיא יכולים להעלות את שיעור היעילות הזה אף ל-2.5.
בצפיפות של מעל ל-5, רכבות הן אמצעי יעיל.
אזורים אלה בדרך כלל התפתחו כתגובה לרכבות באמצע המאה ה-19, ולרוב התושבים של אזורים אלה הסתמכו מלכתחילה על הרכבת כאמצעי תחבורה.
בעיה נפוצה היא כשישנו מרווח של צפיפות מגורים בין 2 ל-5 שיוצר פקקי תנועה כבדים, אך שהצפיפות בשטח זה נמוכה מדי על מנת שרכבת או רכבת קלה תהיה יעילה באזור.
הפתרון הרגיל הוא אוטובוסים, אך אלה ומערכות רכבת קלה לעיתים נכשלים כאשר יש גישה רחבה לרכב פרטי, ולפעמים רק 1% מהאוכלוסייה משתמשת בהם.
יש תאורטיקנים הטוענים שהצורה היחידה למשוך אנשים מהרכב הפרטי היא על ידי מערכות הסעה פרטיות מהירות, אך רעיון זה עדיין לא יושם באף מקום בעולם.
טענה רווחת היא שהגדלת שטח הכבישים אף פעם לא תפתור את הבעיה, מכיוון שהגדלת הביקוש תגדיל את ההיצע והנוחות הנגרמת תגדיל את הביקוש לרכב פרטי, דבר שישיב את רמת הצפיפות בכביש לרמה הגבוהה הקודמת.
בארצות מסוימות הירידה בשביעות רצון מהסביבה העירונית הביאה להגירה מתמשכת אל ערים קטנות יותר או לאזורים כפריים.
תהליך הפרבור התרחש בעיקר בארצות הברית במחצית השנייה של המאה ה-20. תהליך הפרבור התקיים גם סביב ערים רבות באירופה וגם בישראל.
בשנות ה-70 וה-80 התוודעו מתכנני הערים לבעיות הרבות שגרם הפרבור.
מתוך שאיפה ליצור איכות חיים טובים יותר קרו תהליכים שפגעו בעיר ובאיכות הסביבה.
הפרבור גרם לתופעת היוממות, להידרדרות חברתית של מרכזי הערים, להגדלת פערים חברתיים ולפגיעה משמעותית באיכות הסביבה.
כיום, התכנון העירוני שואף לחזק חזרה את מרכזי הערים ולמנוע בנייה בצפיפות נמוכה בשולי העיר ובשטחים פתוחים.
תחום התכנון הסביבתי הוא התחום המגשר בין תכנון העירוני-אזורי להשפעות הסביבתיות.
מתכננים סביבתיים עוסקים בהשלכות סביבתיות של תוכניות בינוי ותשתיות ומפיקים ידע המגשר בין שני עולמות תוכן אלה.
אחד המסמכים החשובים בתכנון ערים הוא תסקיר השפעה על הסביבה, הנערך על פי חשיבות והיקף התכנית ועוסק באינטגרציה תכנונית-סביבתית באשר לממדי ההשפעה השונים של התכנית.
דו"ח כזה מכיל לדוגמה פרטים כגון מידדי רעש וחריגות צפויות; פליטות מזהמים; השפעות על המערכות הטבעיות בשטחי התוכניות ותחומים נוספים.
מוטיב בסיסי בדו"ח זה הוא מידת השילוב הבין-תחומי ולכן המורכבות הרבה של התכנון הסביבתי.
הארקולוגיה שואפת לאחד את תחומי האקולוגיה והאדריכלות, במיוחד אדריכלות נוף, על מנת לאפשר סביבה הרמונית לכל היצורים החיים.
בקנה מידה קטן יותר, תאוריית האקו-כפר המדגישה את הגודל המסורתי של 100–140 איש לקהילה, נעשתה פופולרית.
ברוב המודלים העירוניים או הכפריים המתקדמים, ההקשר המקומי חשוב ביותר.
ברבים, לגינון יש מקום מרכזי לא רק כחלק מהחקלאות אלא בחיים היום-יומיים של האזרחים.
תכנון ערים ואזורים במקורות היהודיים
לפי חוקי ההלכה בתים או דירות יהודיות אינם צריכות לפנות עם הכניסה או החזית זו מול זו כנהוג על פי סידור האוהלים של שבטי ישראל סביב המשכן.
שטחים פתוחים וריאות ירוקות וריאות ירוקות
לפי התורה יש להשאיר "רצועות ירוקות ושטחים פתוחים" גם כדי לתת נחלה אל בני שבט לוי, גר, יתום ואלמנה:
תכנון ובנייה בישראל כוללים את המוסדות העוסקים בהסדרת הקצאתה של קרקע לשימושים שונים, ובפרט לבנייה.
החוק העוסק בנושא זה הוא חוק התכנון והבנייה, תשכ"ה-1965.
בתקופה האימפריה הע'ותמנית הוקמו בארץ ישראל ערים מוקפות חומות עם שערים בסגנון מוסלמי ורחובות מקורים שכללו גם חנויות ושווקים.
בתקופה העות'מאנית בארץ ישראל, החקיקה בתחום התכנון והמקרקעין התבססה על חוקי השריעה ובעקבות רפורמת הטנזימאט הוכנסו לחקיקה תיקונים בהשראת קוד נפוליאון.
כניסת הבריטים לישראל הביאה בשורה בתחום תכנון הערים.
בעוד הגישה העות'מאנית הייתה לפעול באמצעים שיביאו שגשוג לאימפריה, הגישה הבריטית הייתה לפעול לפיתוח הארץ לטובת תושבי האזור.
לבריטים הייתה מודעות רבה לנושא תכנון הערים ושימור מבנים: בעקבות תהליכי עיור שגברו בעקבות המהפכה התעשייתית, ב-1909 נחקק בבריטניה החוק הראשון בעולם בתחום זה.
באפריל 1918 מושל ירושלים רונלד סטורס פרסם צו האוסר על בנייה ללא מתן היתר בתחום ירושלים וכן הוזמנו מומחי תכנון לטובת מלאכת שימור.
בתקופת המנדט גברה מגמת העיור בישראל.
העיר תל אביב גדלה מאוד ועל מנת להסדיר את המשך הפיתוח בה, נוצרה לה תוכנית מתאר ארוכת טווח על ידי האדריכל פטריק גדס.
תוכניות מתאר נעשו לערים נוספות וגם ליישובים חקלאים, כפי שעשה ריכרד קאופמן.
המדיניות הבריטית במדינות החסות הייתה לצמצם ככל הניתן את המעורבות בחוקי המדינה ולבצע שינויי חקיקה הכרחיים בלבד.
בתחום זה נדרשה חקיקה ובינואר 1921 פורסמה "פקודת בניין ערים 1921" אשר הייתה אחת מיוזמות החקיקה הראשונות של ממשלת המנדט ואשר צ'ארלס רוברט אשבי היה מהגורמים המובילים בעיצובה.
פקודה זו עברה כעשרה תיקונים והתגבשה ל"פקודת בניין ערים 1936".
הן היהודים והן הערבים חשו שהמדיניות הבריטית מופנית כנגדם מסיבות פוליטיות, אך נמצא כי לא היה לתחושות אלו בסיס, לפחות בתחום התכנון והבנייה.
הבריטים עמדו על עקרונות הפיתוח ובתוכם גישת עיר גנים בעוד היהודים לחצו להגדיל את הפיתוח והערבים התנגדו לרפורמות שסתרו את הנהוג בתקופה העות'מאנית.
הפקידות בארץ ישראל התחלקה לפקידות בכירה, בריטית בעיקרה, ופקידות זוטרה שכללה את תושבי האזור, יהודים וערבים.
עיקר הפקידים בוועדות התכנון המחוזיות היו יהודים ולא מעט מתיקוני הפקודה נולדו מיוזמתם.
בראשית ימי המנדט, פקודת בניין ערים הייתה ריכוזית מאוד-לכל התוכניות נדרש אישור הנציב העליון.
בהמשך גובש תיקון לפקודה כך שיואצלו יותר סמכויות לשלטון המקומי ומתן דגש על פיתוח ארצי ולא רק מקומי אך פקודה זו ששמה היה "פקודת תכנון עיר וכפר" לא יושמה עקב תום המנדט וחסרונות השיטה הקודמת נשארו גם לאחר הקמת המדינה.
עם קום המדינה אומצה "פקודת בניין ערים 1936" אל מערכת החוק הישראלית.
ב-1959 תוקנה פקודת בניין ערים וב-1965 חוקק חוק התכנון והבנייה אשר לאורך השנים עבר מעל 120 תיקונים ושינויים (נכון לשנת 2025).
מכוחו של חוק זה הוקמו ועדות התכנון והבנייה.
לאחר ההכרזה על מדינת ישראל כאשר החלה עלייה המונית של יהודים מכל העולם אל הארץ החלו מתכננים ואדריכלים ממזרח אירופה לתכנן את היישובים החדשים ואת השכונות החדשות שהוקמו לצורך אכלוס ויישוב הפזורה היהודית.
האדריכל אריה שרון נבחר לאדריכל הראשי של משרד השיכון ותכנן עבורו את התוכניות.
תוכנית המתאר הארצית הראשונה של מדינת ישראל אושרה בשנת 1951 ונקראה: "תכנון פיסי בישראל".
תמ"א 3, תוכנית מתאר ארצית לדרכים, אושרה בשנת 1976 והיוותה את התשתית התכנונית לסלילת רשת הדרכים ודרכי הגישה.
תוכניות מתאר ארציות נושאיות נוספות אושרו לאורך השנים והן כיסו מגוון רחב של נושאי תשתית כדוגמת רשת החשמל, שדות תעופה, תשתיות מיים וביוב, גנים לאומיים, שמורות טבע, חופים, תיירות, מסילות ברזל, כריה וחציבה ועוד.
תוכנית המתאר הארצית הכוללנית הבאה, תוכנית מתאר ארצית משולבת לבניה, פיתוח ולקליטת עליה תמ"א 31 א' אושרה בשנת 1993. התוכנית קודמה לאור לחצי הפיתוח שהתעוררו בעקבות העלייה המאסיבית של תחילת שנות התשעים, והיא שמה דגש על ביזור אוכלוסין אך בה בעת גם על שימורם של שטחים פתוחים ערכיים.
בשנת 2005 החליפה אותה תוכנית מתאר ארצית משולבת לבנייה, פיתוח ושימור, תמ"א 35. גם תוכנית זו, כקודמתה, שמה דגש על שימורם של שטחים פתוחים ואיכויות סביבתיות ואת הפיתוח הכווינה למספר מוקדים מטרופוליניים מרכזיים ברוח התכנון המקיים (תכנון בר קיימא).
ב-1949 נוסדה התאחדות הקבלנים בישראל.
ב-1969 הוקם מרכז הבנייה הישראלי בסמוך אל מרכז הירידים והקונגרסים ומכון התקנים בתל אביב.
לאורך השנים אירעו בישראל מחאות שונות על רקע יוקר הדיור.
בראשית שנות ה-90 נוצר משבר דיור עקב קליטת עלייה מברית המועצות ואתיופיה אשר הצריך יצירה מהירה של פתרונות דיור.
המדינה פנתה אל האדריכל יונה פיטלסון וכחלק מתמ"א 33, הוקמו אתרי קראוונים במקומות שונים בישראל.
בעקבות אסון המכביה ואסון ורסאי הוקמה ועדת זיילר לבטיחות מבנים אשר ממצאיה הובילו לעריכת שינויים בתחום הטכני של הבניה וכן להקמת מכוני בקרה פרטיים בישראל.
ב-2011, בעקבות משבר הדיור בישראל והמחאה החברתית שבאה בעקבותיו אושרה בכנסת רפורמה שכונתה חוק הווד"לים שמטרתה קיצור הליכי בנייה.
כמו כן, בעקבות דו"ח ועדת טרכטנברג הוקמה ועדה בינמשרדית לעידוד התחרותיות בענף המלט בישראל בראשות גל הרשקוביץ (ועדת הרשקוביץ).
בעקבות דו"ח הוועדה, התקבלה החלטה לחייב את נשר למכור את מפעל הרטוב ולהפחית את מחיר המלט ב-2%.
לפי הערכות שונות, עיקר העלויות, בממוצע 30%,
נובעות ממחיר הקרקע ואילו הוזלת המלט יכולה להביא לירידה של כ-3% ממחיר הדירה.
באפריל 2018 פורסמה רפורמה בתחום הקמת מבנים חקלאים בצפון הארץ (למעט רמת הגולן) המאפשרת קבלת היתר ל-37 סוגי מבנים ללא תוכנית אך עם מגבלות שונות, דבר המאפשר להוזיל ולקצר הליכי בנייה.
על פי חוק התכנון והבניה, המבקש להקים מבנה בישראל נדרש לקבל רישיון בנייה (היתר בנייה).
היתר בנייה ניתן - על פי רוב - על ידי הוועדה המקומית לתכנון ולבנייה, אולם ייתכנו מקרים שבהם הוא יינתן על ידי גורמים אחרים.
כאשר הוועדה המקומית דנה בבקשתו של האדם לקבל היתר בנייה, היא בוחנת אילו תוכניות חלות על הקרקע.
התוכניות החלות על הקרקע נותנות מענה לשתי שאלות עיקריות:
איזה מבנה מותר לבנות על הקרקע: שטח המבנה, גובה המבנה, עיצוב המבנה וכדומה.
מהם השימושים שמותר לבצע במבנה: מגורים, מסחר, תעשייה, חקלאות וכדומה.
בין עקרונות היסוד בדיני התכנון והבנייה בישראל נמנים גם עקרון השקיפות ועקרון שיתוף הציבור בהליכי אישור תוכניות.
לפי עקרון השקיפות- הודעה על הפקדת תוכנית מפורסמת ברשומות, בעיתונות ועוד.
הפרסום מאפשר לציבור לדעת על ההפקדה ולהגיש התנגדות לתוכנית.
לפי עקרון שיתוף הציבור- כל מעוניין בקרקע, בבנין או בכל פרט תכנוני אחר הרואה את עצמו נפגע על ידי תוכנית משהופקדה, רשאי להגיש התנגדות.
שלושת הסוגים העיקריים של התוכניות הם תוכנית מתאר ארצית, תוכנית מתאר מחוזית ותוכנית מתאר מקומית.
סוגים נוספים של תוכניות הם: תוכנית לתשתית לאומית, תוכנית דרך, תוכנית לשימור אתרים ועוד.
ככלל, על קרקע מסוימת - יהא גודלה אשר יהא - עשויות לחול כמה תוכניות במקביל.
במקרה כזה, יש צורך לקבוע מהו היחס בין התוכניות, כלומר - מי גוברת על מי במקרה של סתירה ביניהן.
קיים מדרג היררכי בין סוגים של תוכניות, וכלל האצבע הוא שתוכנית גבוהה במדרג גוברת על תוכנית נמוכה במדרג.
כמו כן, ככל שתוכנית גבוהה יותר במדרג, כך רמת הפירוט שלה נמוכה יותר.
משמעות הדבר היא שרמת הפירוט הנמוכה אינה מאפשרת, בדרך כלל, לוועדה המקומית להבין איזה מבנה מותר לבנות, ומהם השימושים שמותר לבצע במבנה.
זהו אמנם כלל אצבע, אולם ייתכנו מקרים שבהם תוכנית גבוהה במדרג ההיררכי תהא ברמת פירוט כזו, כך שניתן יהיה לקבל מכוחה היתר בנייה.
פרסום התוכניות והיכולת להשפיע עליהן משתנה בהתאם לסוג התכנית ובהתאם לוועדה שבסמכותה לאשר את התכנית.
תוכנית מתאר ארצית (או בקיצור: "תמ"א") היא תוכנית שחלה על כל שטח המדינה.
הדוגמה המוכרת ביותר לתוכנית כזו היא תמ"א 38, העוסקת בעידוד לחיזוק מבנים מפני רעידות אדמה, כאשר התמריץ לביצוע החיזוק הוא מתן אפשרות להגדיל את הבינוי.
תוכנית מתאר ארצית מוגשת על ידי המועצה הארצית לתכנון ובנייה לממשלת ישראל שאחראית על אישורה.
תמ"א 3 - תוכנית מתאר ארצית לדרכים: עוסקת בכבישים מרכזיים בכל שטח המדינה.
תמ"א 18 - תוכנית מתאר ארצית לתחנות תדלוק.
תמ"א 19 - תוכנית מתאר ארצית לבתי עלמין.
תמ"א 22 - תוכנית מתאר ארצית ליערות.
תמ"א 23 - תוכנית מתאר ארצית למסילות ברזל.
תמ"א 36 - עוסקת בהקמת אנטנות סלולריות.
תמ"א 35 - תוכנית מתאר ארצית משולבת לבנייה, לפיתוח ולשימור.
תמ"א 1 תוכנית המתאר הארצית האחודה מאחדת את מרבית תוכניות המתאר הארציות הנושאיות לתוכנית אחת.
ייתכנו מקרים שבהם תוכן תוכנית מתאר ארצית שתאושר על ידי ממשלת ישראל, אבל התוכנית תחול רק על חלק משטח המדינה ("תמ"א חלקית").
בישראל קיימים 6 מחוזות: צפון, חיפה, מרכז, תל אביב, דרום וירושלים.
תוכנית מתאר מחוזית (או בקיצור: "תמ"מ") היא תוכנית שחלה על שטחו של מחוז.
תוכנית המתאר המחוזית מתארת ברמת הפשטה גבוהה יחסית כיצד ייראה המחוז: ניתן לדעת איפה יהיה, למשל, פארק מטרופוליני או איפה יהיה אזור תעשייה או אזור מגורים.
כאשר נערכת ומאושרת תוכנית מתאר ארצית, בוחן מוסד התכנון הרלוונטי את תוכניות המתאר הארציות החלות, ולפיהן הוא יודע אילו הגבלות חלות על הכנת תוכנית המתאר המחוזית.
תוכנית מתאר מחוזית מאושרת על ידי המועצה הארצית לתכנון ובנייה.
תוכניות המתאר המחוזיות המרכזיות הן:
תמ"מ 1 - תוכנית המתאר המחוזית - מחוז ירושלים.
תמ"מ 2 - תוכנית המתאר המחוזית - מחוז צפון.
תמ"מ 5 - תוכנית המתאר המחוזית - מחוז תל אביב.
תמ"מ 6 - תוכנית המתאר המחוזית - מחוז חיפה.
תוכנית מתאר מקומית היא תוכנית שחלה על שטחו של מרחב תכנון מקומי אחד.
אם תוכנית המתאר המחוזית מתארת איפה יהיה אזור מגורים או אזור תעשייה, תוכנית המתאר המקומית כבר קובעת - ברמת הפשטה גבוהה יותר - אילו מבנים יוקמו באזורים אלו.
ההבדל המרכזי בין תוכנית מתאר מחוזית לתוכנית מתאר מקומית נעוץ בכך, שכל אחת מהן רואה לנגד עיניה "שלם" אחר.
למשל, אמנם נכון הוא שקרקע המצויה בעיר פתח תקווה נמצאת גם בתוכנית המתאר המקומית של פתח תקווה וגם בתוכנית המתאר המחוזית של מחוז מרכז, אבל בעוד שבתוכנית המתאר המחוזית הקרקע הזו היא חלק קטן מכלל המחוז, הרי שבתוכנית המתאר המקומית היא מהווה חלק גדול יותר מרחב התכנון המקומי פתח תקווה.
ככלל, תוכנית מתאר מקומית מאושרת על ידי הוועדה המחוזית לתכנון ובנייה.
במקרים מסוימים, הקבועים בסעיף 62א לחוק התכנון והבניה, עשויה תוכנית מתאר מקומית להתאשר על ידי הוועדה המקומית לתכנון ובנייה.
סוג מיוחד של תוכנית מתאר מקומית הוא תוכנית כוללנית.
הרעיון המרכזי בתוכנית כוללנית הוא לקבוע כיצד ייראה מרחב התכנון המקומי בעתיד (בדרך כלל תקופה בת 20 - 30 שנים קדימה).
כמו כן, קיומה של תוכנית כוללנית מאפשר לוועדה המקומית הרלוונטית - במקרים המתאימים - לקבל לידיה סמכות גדולה יותר באישור תוכניות מתאר מקומיות.
מוסדות תכנון בתחום הבנייה בישראל
ועדה לשמירה על קרקע חקלאית ושטחים פתוחים (ולקחש"פ)
ועדת המשנה לנושאים תכנוניים עקרוניים (ולנת"ע)
תכנון מנגנונים הוא תחום בתורת המשחקים, בעל יישומים בכלכלה.
בעוד שתורת המשחקים נוטה לחקור את התנהגות השחקנים במנגנונים קיימים, ענף תכנון המנגונים (המכונה לעיתים תורת המשחקים ההופכית), נועד לבנות משחקים אשר יגרמו לשחקניהם להתנהג באופן הרצוי למארגן המשחק.
מטרות מתכנן המנגנון יכולות להיות שונות - רווח מרבי (למשל בבעיית המכירה הפומבית), מיקסום תועלת המשתתפים (בקביעת מדיניות ממשלתית) ועוד.
התורה מספקת לו כלים לבנות מנגנונים אשר יאפשרו לו להשיג את מטרתו בלי להניח שיתוף פעולה של המשתתפים.
(להם אינטרסים שונים משלו) כדוגמה למנגנון למיקסום תועלת המשתתפים במכירה פומבית, ניתן להתבונן במנגנון מכרז מחיר שני.
פרס נובל לכלכלה לשנת 2007
ב-15 באוקטובר 2007 הודיעה הוועדה לבחירת פרס נובל לכלכלה כי חתני פרס נובל לשנת 2007 הם הכלכלנים האמריקנים פרופ' ליאוניד הורביץ מאוניברסיטת מינסוטה, פרופ' אריק מסקין מאוניברסיטת פרינסטון ופרופ' רוג'ר מאירסון מאוניברסיטת שיקגו.
הם זכו בפרס על פיתוחים בתחום עבור מוסדות כלכליים.
התאוריה פותחה על ידי פרופ' הורוביץ, ושוכללה ויושמה על ידי הפרופסורים מסקין ומאירסון.
תכנון ייצור בקיבולת סופית (Finite Capacity Scheduling) הוא שיטה המתזמנת את הייצור למועד הנכון כדי לספק את הדרישה למוצר בהתחשב בקיבולת משאבי הייצור.
החל משנות ה-80 של המאה ה-20 החל שימוש נרחב במערכות לעיתוד מלאי (Material Requirement Planning-MRP) אשר עזרו בזימון החומרים לייצור ובקבלת החלטות לתיזמון מועדי הייצור.
מערכות אלה מסתמכות על פרמטרים רבים כגון: גודלי המנה בייצור, מלאי ביטחון נדרשים, זמני אספקה ועוד.
מנגנונים אלו מהווים היום חלק ממערכות ERP הנמצאות בשימוש רחב.
מערכות לתכנון ייצור - Scheduling
המגבלה העיקרית של מערכות MRP, היא שמשאבי הייצור אינם מוגבלים בקיבולת הייצור ולכן הארגון עשוי לקבל המלצות לייצור שאינן מעשיות.
כאן נכנסות מערכות נלוות, המתבססות על נתוני הייצור ועוזרות לארגון בסידור פקודות העבודה תוך כדי עמידה במגבלות של משאבי הייצור.
מערכות לתכנון ייצור בקיבולת סופית יודעות להתמודד עם זמני כוונון (SETUP) כתלות במוצר, שימוש במטריצה, קצבי ייצור שונים למוצרים שונים ולמשאבים שונים, תלויות בין משימות (מרכזי עבודה), עמידה במועדי אספקה והקטנת עלויות ייצור.
בגלל המבנה של תוכנות אלו, הן יודעות לטפל במגוון רחב של בעיות זימון.
תכנון בעזרת מחשב (בראשי תיבות תב"ם, ובאנגלית CAD - Computer-Aided Design) הוא השימוש בטכנולוגיות מחשוב ככלי לתכן ועיצוב מוצרים.
שיטה נרחבת יותר קרויה תכן וייצור בעזרת מחשב (תיב"ם).
זהו מונח כללי המתייחס לכלי המחשוב המשמשים מהנדסים בעבודת התכן ההנדסי.
כלים אלו משמשים לתכן המוצרים ולתכנון הייצור של מוצרים אלו.
באנגלית, כלי המחשוב מוגדרים כ-CAx כאשר "x" מתחלף עבור כלי התכן ההנדסי השונים.
מטרות הכלים הללו הן מגוונות.
כלי התכנון נועדו לתת ממשק גרפי נוח למשתמש שבעזרתו ניתן לתכנן, לעצב ולבדוק את המוצר.
שרטוט המוצר שבעבר היה נעשה על גבי ניירות, שקופיות ואמצעים פיזיים אחרים, נעשה על גבי תוכנת המחשב, המאפשרת בקלות שכפול, מחיקה, הוספת חלקים שונים, חיבור, ועוד אמצעי עריכה ובקרה.
בדרך כלל בדיקות רבות וכללים הקשורים לעיצוב, בקרה ואיכות המוצר נבדקים אוטומטית על ידי הכלים.
כלים רבים מאפשרים סימולציות שבודקות את השימוש במוצר.
ישנם גם כלים המיועדים לבדיקות המוצר אחרי שיוצר כבר, לצורך בקרת איכות.
נהוג לחלק את מערכות התב"ם לארבעה דורות.
המערכות הראשונות (שנות ה-60–שנות ה-80 של המאה ה-20) היו מבוססות מחשב מרכזי, והציעו בעיקר יכולות דו־ממד.