What is linear programming (hebrew)

"תכנות לינארי" או "תכן לינארי" אינו מדבר על שיטת קידוד של תוכנה אלא על שיטה למציאת דרך אופטימלית להתנהגות במציאות. 

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

הכי קל להבין מה זה "תכנות לינארי" הוא לבחון דוגמא פשוטה.

הדוגמא

חקלאי מגדל לאורך שנים מלפפונים ועגבניות בשדה ששטחו 30 דונם. 

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

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

האחראי על השיווק במושב, דורש שיוקצה לפחות 1 דונם לגידול מלפפונים על כל 3 דונם לגידול עגבניות.

החקלאי גם בדק ומצא כמה עלה לו לגדל כל גידול וכמה הרוויח ממנו:

החקלאי שואל - בכמה דונם לגדל עגבניות וכמה מלפפונים?

שלב ראשון - המרה למודל מתמטי

יש שתי פרמטרים שצריך למצוא אותם: X1 (מספר הדונמים שיוקצו לגידול עגבניות) ו X2 (מספר הדונמים שיוקצו לגידול מלפפונים).

מה שצריך הוא למצוא את X1, X2 כך ש Z (הרווח הצפוי מהגידולים) יהיה הכי גדול.

Max Z = 3*1200X1 + 4*600X2 = 3600X1 + 2400X2

המגבלות הקיימות:

X1 + X2 ≤ 30   שטח

18X1 + 10X2 ≤ 450 מכסת מים

X1 – 3X2 ≤ 0         יחס בין גידולים

X1, X2 ≥ 0

שלב שני - ציור המגבלה הראשונה על גרף:

השטח הורוד הוא כל ה X1,X2 שעונים על התנאי הראשון.

שלב שלישי - ציור כל שאר התנאים:

X1 + X2 ≤ 30   שטח (סגול)

18X1 + 10X2 ≤ 450 מכסת מים (כחול)

X1 – 3X2 ≤ 0         יחס בין גידולים (ורוד)

מה שנקבל הוא השטח בגרף של התחום האפשרי של פתרונות. כל נקודה בו עונה על כל המגבלות אבל רק נקודה אחת נותנת רווח מקסימליץ

שלב רביעי - מציאת הנקודה המיטבית:

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

אז מה שנשאר הוא לבדוק את הרווח של כל נקודה בקודקוד במצולע ואז לקחת את הנקודה בה הרווח הוא הכי גדול.

אבל מה קורה אם יש יותר משני פרמטרים שיוצרים מגבלות על הפתרון?

במקרה כזה אי אפשר לעשות גרף.

אבל אל דאגה - יש אלגוריתם בשם "סימפלקס" שעושה את העבודה. זה האלגוריתם שכנראה הכניס הכי הרבה כסף למשתמשים בו.

לא נסביר פה את האלגוריתם אבל הנה השלד שלו: