Linear programming — תכנות לינארי

תכנות לינארי — הוא ענף של תכנות מתמטי וכלי נפוץ בחקר פעולות, העוסק בפיתוח תיאוריה ושיטות לפתרון בעיות מציאת קצה (מקסימום או מינימום) של פונקציה לינארית בכפוף לאילוצים לינאריים.

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

נושא ומטרה

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

• תכנות לינארי מאפשר לפתור בעיות מעשיות כגון:
• תכנון ייצור אופטימלי.
• אופטימיזציה של זרימות תחבורה (בעיית התחבורה).
• הקצאה אופטימלית של השקעות.
• חיתוך אופטימלי של חומרים. בעיית השיבוץ.

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

בעיית התכנות הלינארי הסטנדרטית מנוסחת כך:

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

מבחינה מתמטית, מדובר בעבודה עם פונקציות לינאריות ומערכות של משוואות/אי-שוויונות לינאריים.

מושגי יסוד בתכנות לינארי

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

שיטות פתרון בעיות תכנות לינארי

קיימות מספר שיטות עיקריות לפתרון בעיות תכנות לינארי:

• השיטה הגרפית: משמשת לבעיות עם שני משתני החלטה. מאפשרת לתאר באופן חזותי את התפ"ק ואת פונקציית המטרה במישור ולמצוא את הפתרון האופטימלי על ידי ניתוח קדקודי התפ"ק או הזזת קו הרמה של פונקציית המטרה.
• שיטת הסימפלקס: אלגוריתם איטרטיבי אוניברסלי שפותח על ידי George Dantzig. השיטה עוברת בצורה עוקבת מקדקוד אחד של התפ"ק לקדקוד שכן, תוך שיפור ערך פונקציית המטרה בכל צעד, עד למציאת הפתרון האופטימלי. זוהי השיטה הקלאסית והמוכרת ביותר לפתרון בעיות תכנות לינארי.
• שיטות נקודה פנימית: מחלקה חלופית של אלגוריתמים שהופיעו לאחר שיטת הסימפלקס. הן נעות לעבר הפתרון האופטימלי בתוך התפ"ק ולא לאורך גבולותיו. שיטות אלו יעילות במיוחד לפתרון בעיות תכנות לינארי בעלות ממדים גדולים מאוד.

דואליות בתכנות לינארי

לכל בעיית תכנות לינארי (הנקראת הפרימאל) ניתן להתאים בעיית תכנות לינארי אחרת הנקראת הדואל. הפרימאל והדואל קשורים זה לזה קשר הדוק:

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

יישומים של תכנות לינארי

תכנות לינארי מוצא שימוש נרחב ב:

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

ספרות

• Dantzig, G. Linear Programming and Extensions. — מ': Progress, 1966.
• יודין ד. ב., גולשטיין א. ג. תכנות לינארי (תיאוריה, שיטות ויישומים). — מ': Nauka, 1969.
• Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
• Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)

ראו גם

• חקר פעולות
• אופטימיזציה
• פונקציית מטרה
• אילוצים
• תחום הפתרונות הקבילים
• פתרון אופטימלי