שיעור תאוריה

ניסוח בעיות תכנון ליניארי

איך מזהים שהנושא מתאים

אינטואיציה

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

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

מודל ליניארי מאפשר רק תרומות קבועות לכל יחידה. לדוגמה, 4x₁ + 7x₂ הוא ביטוי ליניארי; הביטויים x₁x₂ ו-x₁² אינם ליניאריים.

הגדרות פורמליות

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

צורה כללית של מודל תכנון ליניארי היא:

max/min  Z = ∑ cⱼxⱼ ∑ aᵢⱼxⱼ {≤, =, ≥} bᵢ,   i = 1,...,m xⱼ ≥ 0,   j = 1,...,n

הסוגריים {≤, =, ≥} מציינים שכל אילוץ מקבל את הסימן שמתאים למשמעות המילולית שלו.

סימון משמעות
j אינדקס של משתנה החלטה; n הוא מספר המשתנים.
i אינדקס של אילוץ; m הוא מספר האילוצים.
xⱼ משתנה החלטה מספר j.
cⱼ התרומה של יחידה אחת מ-xⱼ לפונקציית המטרה.
aᵢⱼ הכמות שבה יחידה אחת מ-xⱼ משפיעה על אילוץ i.
bᵢ אגף ימין של אילוץ i: קיבולת, דרישה או גבול.

שיטת פתרון

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

תרגום ניסוחים נפוצים

ניסוח מילולי מבנה מתמטי
לכל היותר, קיבולת, אין לעבור ≤
לפחות, דרישה מינימלית ≥
בדיוק, איזון מלא =
לא יותר מ-α מתוך הסך הכולל x₁ ≤ α(x₁ + x₂ + ... + xₙ)
פי k לכל היותר ממשתנה אחר x₁ ≤ kx₂

דוגמה לפישוט אילוץ אחוזים

נניח שמוצר 1 יכול להיות לכל היותר מחצית מהכמות הכוללת:

x₁ ≤ 0.5(x₁ + x₂ + x₃)
  1. כופלים את שני האגפים ב-2 כדי להסיר את המקדם העשרוני. 2x₁ ≤ x₁ + x₂ + x₃
  2. מחסרים x₁ משני האגפים. x₁ ≤ x₂ + x₃

שתי הצורות שקולות. הצורה השנייה קצרה יותר, אך מותר להשתמש בה רק לאחר שהמעבר האלגברי הוצג.

הערות מוכנות למבחן

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