Skip to main content

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         יחס בין גידולים (ורוד)

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


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

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

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



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

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

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

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




Comments

Popular posts from this blog

Best freeware - XML editor

As a software developer, I open XML files all the time. I a heavy commercial XML editor. But nothing can compare to a small, thin and free XML editor like 'foxe'. A great feature is has is the alignment of long XML strings to readable XML format (Shift-F8). It help lot of times when the XML file was generated by some tool and was not readable. Homepage: http://www.firstobject.com/dn_editor.htm

Jenkins error: groovy.lang.MissingPropertyException

I tried to run groovy build step and got below error. This post will describe how I solved the problem. Caught: groovy.lang.MissingPropertyException: No such property: hudson for class: script

SSL in pictures

Here is my summary on SSL (or as I like to call it 'SSL for dummies')