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

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


טיפים לטסט על אמבולנס במד"א

אורך הטסט הוא בערך 20-30 דקות בהם הטסטר נותן הוראות ימינה ושמאלה ולפעמים קצת יותר. נראה שהטסטר מחפש להבין שאתה לא נהג חסר אחריות.
הרכב עצמו הוא אוטומט. מוט ההילוכים הוא בהגה ודרכו אפשר לעבור בין המצבים (Drive, Reverse etc).
ההמברקס הוא דוושת הרגל השמאלית.
טיפיםהעצות בלשון זכר רק לצורך פשטות.
בתחילת הנסיעה:
אם אתה הראשון, תדליק אורות דרך.

בדוק איך מעבירים את ההילוך ל 3 בלי להסתכל בידית ההילוכים כי הטסטר עלול לבקש במהלך הנסיעה שתעביר להילוך שלישי.

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

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

gnutls_handshake() failed: Access was denied

Error when running apt-get:

sudo apt-get update && sudo apt-get install yarn

gnutls_handshake() failed: Access was denied

The problem: There is proxy configuration error of apt-get

The fix:Define proxy for apt-get
1. sudo vim /etc/apt/apt.conf 2. Add line: Acquire::http::proxy "http://web-proxy.il.hpecorp.net:8080";
Source: https://ubuntuforums.org/showthread.php?t=2011511