תכנות לינארית: לשם מה, דגמים, אילוצים, יישומים - מתמטיקה - 2025

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

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

איור 1. תכנות לינארית משמשת באופן נרחב לייעול הרווחים. מקור: פיקסלס.

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

Z = k ₁ x + k ₂ y

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

Z = k ₁ x ₁ + k ₂ x ₂ + k ₃ x ₃ +….

והאילוצים מעוצבים גם במתמטיקה על ידי מערכת של משוואות או אי-שוויון, ליניאריות שווה ב- x ו- y.

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

תכנות לינארית פותחה באופן עצמאי על ידי הפיזיקאי והמתמטיקאי האמריקני ג'ורג 'דאנציג (2005-1914) והממתמטיקאי והכלכלן הרוסי לאוניד קנטורוביץ' (1912-1986) זמן קצר לאחר מלחמת העולם השנייה.

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

איור 2. מתמטיקאים ג'ורג 'דאנציג (משמאל) ולאוניד קנטורוביץ' (מימין). מקור: פ. זפטה.

דגמי תכנות לינאריים

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

-פונקציה אובייקטיבית

משתני החלטה

-הגבלות

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

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

Z = ∑k _i x _i

במשוואה הזו, k _i הם מקדמים ו- X _i הם המשתנים ההחלטה.

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

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

סוגי הגבלות

אתה יכול להיות מספר M של מגבלות, החל מ j = 1 עד j = M. מבחינה מתמטית ההגבלות הן משלושה סוגים:

1. A _j = ∑ a _ij . x _i
2. B _j ≥ ∑ b _ij . x _i
3. C _j ≤ ∑ c _ij . x _i

ההגבלה הראשונה היא מסוג המשוואה הליניארית ומשמעותה שיש לכבד את הערך _Aj , הידוע.

שתי ההגבלות הנותרות הינן אי שוויון לינארי וזה אומר שניתן לכבד או לחרוג לערכים הידועים _Bj ו- _Cj , כאשר הסמל שמופיע הוא ≥ (גדול או שווה ל) או לכבד או לא לחרוג, אם הסמל הוא ≤ (פחות מ או שווה ל).

דוגמה לדוגמא

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

פטיסרי מקומי ידוע בשתי התמחויות: עוגת יער שחור ועוגת סקרפנטין.

בהכנתו הם זקוקים לביצים וסוכר. בשביל היער השחור אתה זקוק ל 9 ביצים ו 500 גרם סוכר, ואילו לסכריפנטין אתה צריך 8 ביצים ו 800 גרם סוכר. מחירי המכירה בהתאמה הם 8 $ ו- 10 $.

הבעיה היא: כמה עוגות מכל סוג חייבות המאפייה להכין כדי למקסם את הרווח שלה, בידיעה שיש לה 10 קילו סוכר ו 144 ביצים?

משתני החלטה

משתני ההחלטה הם "x" ו- "y", שלוקחים ערכים אמיתיים:

-x: מספר עוגות היער השחור

-y: עוגות מסוג sacripantine.

הגבלות

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

לכן, בצורה מתמטית, מגבלות אלה לובשות את הצורה:

1. x ≥ 0
2. ו- ≥0
3. 9x + 8y ≤ 144
4. 0.5 X + 0.8y ≤ 10

אילוצים 1 ו -2 מהווים תנאי של אי שליליות שנחשפה בעבר, וכל אי השוויון שהועלה הם לינאריים. בהגבלות 3 ו -4 הם הערכים שאסור לעבור מהם: 144 ביצים ו 10 ק"ג סוכר.

פונקציה אובייקטיבית

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

G = 8x + 10y

שיטות פתרון

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

- שיטה גרפית או גיאומטרית

כאשר יש לך בעיה דו משתנה כמו זו בסעיף הקודם, האילוצים קובעים אזור מצולע במישור ה- xy, הנקרא אזור בר ביצוע או אזור הכדאיות.

איור 3. איור 3. האזור ריאלי, בו נמצא הפיתרון של בעיית האופטימיזציה. מקור: Wikimedia Commons.

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

במקרה של המאפייה שרוצה לייעל את הרווחים, קווי האילוץ הם:

1. x = 0
2. y = 0
3. 9x + 8y = 144
4. 0.5 X + 0.8y = 10

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

למרבה המזל, לבעיית המאפה האזור האפשרי אינו ריק, יש לנו את זה למטה.

איור 4. איור 4. האפשרי של בעיית המאפה. הקו עם השג 0 חוצה את המקור. מקור: F. Zapata עם Geogebra.

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

G = k ₁ x + k ₂ y → y = -k ₁ x / k ₂ + G / k ₂

עם קו זה אנו משיגים את כל הזוגות (x, y) המספקים רווח נתון G, כך שיש משפחה של קווים לפי הערך של G, אך כולם עם אותו שיפוע -k ₁ / k ₂ , כך שהם קווים מקבילים.

הפיתרון האופטימלי

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

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

עבור המאפה שלנו, קודקודי המועמד הם A, B ו- C.

- שיטת ה- Simplex של דנציג

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

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

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

יישומים

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

להלן מספר שדות:

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

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

בבחירת המזון המזין ביותר ובעלות הנמוכה ביותר בתעשיות הבקר והעופות.

תרגילים שנפתרו

- תרגיל 1

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

פִּתָרוֹן

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

1. x ≥ 0
2. ו- ≥0
3. 9x + 8y ≤ 144
4. 0.5 X + 0.8y ≤ 10

האזור הניתן על ידי אי השוויון 1 ו -2 תואם לרבע הראשון של המטוס הקרטזיאני. לגבי אי השוויון 3 ו -4, נתחיל במציאת קווי ההגבלה:

9x + 8y = 144

0.5 x + 0.8y = 10 → 5x + 8y = 100

האזור האפשרי הוא ריבועי שהקודקודים שלו הם הנקודות A, B, C ו- D.

הרווח המינימלי הוא 0, ולכן קו 8x + 10y = 0 הוא הגבול התחתון וקווי הרווח האיסו יש שיפוע -8/10 = - 0.8.

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

איור 5. איור 5. פיתרון גרפי של תרגיל 1, המציג את האזור האפשרי ואת נקודת הפיתרון C באחד מקודקודי האזור. מקור: פ. זפטה.

פיתרון זה תואם קו של שיפוע -0.8 העובר דרך אחת מהנקודות A, B או C, שהקואורדינטות שלהן הן:

א (11; 5.625)

B (0; 12.5)

C (16, 0)

פיתרון אופטימלי

אנו מחשבים את הערך של G עבור כל אחת מהנקודות הבאות:

- (11; 5.625): G _A = 8 x 11 + 10 x 5.625 = 144.25

- (0; 12.5): G _B = 8 x 0 + 10 x 12.5 = 125

- (16, 0): G _C = 8 x 16 + 10 x 0 = 128

הרווח הגבוה ביותר נמצא בייצור 11 עוגות יער שחור וש 5,625 עוגות סקרפנטין. פיתרון זה מסכים עם זה שנמצא באמצעות התוכנה.

- תרגיל 2

אמת את התוצאה של התרגיל הקודם על ידי שימוש בפונקציה Solver הזמינה ברוב הגיליונות האלקטרוניים כגון Excel או LibreOffice Calc, המשלבים את אלגוריתם ה- Simplex לייעול בתכנות ליניארית.

פִּתָרוֹן

איור 6. פירוט הפיתרון מתרגיל 1 דרך גיליון האלקטרוני של Libre Office Calc. מקור: פ. זפטה.

איור 7. פירוט הפיתרון מתרגיל 1 דרך הגיליון האלקטרוני של Libre Office Calc. מקור: פ. זפטה.

הפניות

1. מַברִיק. תכנות לינארי. התאושש מ: brilliant.org.
2. Eppen, G. 2000. מחקר תפעול במדע מנהלי. 5. מַהֲדוּרָה. אולם פרנטיס.
3. Haussler, E. 1992. מתמטיקה לניהול וכלכלה. 2. מַהֲדוּרָה. Iberoamericana, עורכת גרופ.
4. Hiru.eus. תכנות לינארי. התאושש מ: hiru.eus.
5. ויקיפדיה. תכנות לינארי. התאושש מ: es. wikipedia.org.