מודלים דטרמיניסטיים - דף נוסחאות

עמוד 1: תכנון ליניארי, סימפלקס ורגישות

בחירת השיטה

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

ניסוח מודל

מטרה: מחברים לכל משתנה תרומה ליחידה כפול מספר יחידות max/min  Z = Σk ck xk אילוץ: מחברים את התרומה של כל משתנה לאותו כלל ומשווים לגבול Σk ar,k xk { ≤, =, ≥ } br,  r = 1,...,m xk ≥ 0,  k = 1,...,n

מוסכמת אינדקסים: r מסמן שורת אילוץ, ו-k מסמן משתנה או עמודה. לכן xk הוא מספר היחידות, ck הוא רווח או עלות ליחידה, ar,k הוא מקדם המשתנה באילוץ, ו-br הוא גבול האילוץ.

  1. מגדירים משתנים עם משמעות, יחידה, תקופה וסוג.
  2. מאחדים יחידות ובודקים ליניאריות.
  3. כותבים מטרה: תרומה ליחידה כפול כמות.
  4. מתרגמים כלל אחד לכל אילוץ.
  5. מוסיפים אי שליליות ושלמות רק כשנדרשו.
לכל היותר≤
לפחות≥
בדיוק=
A לפחות p% מהסך TA ≥ (p / 100) T
בחירה כן או לאy ∈ {0, 1}
כמות שלמהx ∈ ℤ,  x ≥ 0

בדיקה: בכל אילוץ שני האגפים חייבים להיות באותן יחידות.

כדאיות משאב נוסף

רווח נקי = (תועלת ליחידה פחות מחיר ליחידה) כפול הכמות ΔZnet = (DV - c) q

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

השלמת סימפלקס: בסיס מלאכותי

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

  • שני שלבים: בשלב א ממזערים W = Σ Ar. אם W* > 0 אין פתרון אפשרי; אם W* = 0 מסירים את המלאכותיים וממשיכים למטרה המקורית.
  • M גדול: נותנים לכל מלאכותי קנס גדול במטרה. מקבלים פתרון רק אם כל המלאכותיים התאפסו.

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

צורה סטנדרטית וסימפלקס

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

א. הופכים כל אילוץ למשוואה

תחילה דורשים br ≥ 0. אם אגף ימין שלילי, כופלים את כל השורה ב--1 והופכים את כיוון האי שוויון.

האילוץהמשוואה שמכניסים לטבלה
LHSr ≤ brLHSr + sr = br
LHSr ≥ brLHSr - er = br
LHSr = brלא משנים; ייתכן שיידרש משתנה מלאכותי

LHSr הוא כל אגף שמאל של אילוץ r; br הוא הגבול. sr הוא הקיבולת שלא נוצלה, ו-er הוא הכמות שבה עברנו דרישת מינימום. שניהם אי שליליים.

ב. בונים בסיס התחלתי

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

משתנה מרווח sr יוצר בדרך כלל בסיס טבעי. משתנה עודף מופיע עם -1, ובאילוץ שוויון אין עמודת יחידה; בשורות שאין להן בסיס מוסיפים זמנית משתנה מלאכותי Ar.

ג. מבצעים איטרציית סימפלקס במקסימום

Ck הוא מקדם המשתנה במטרה; Zk הוא הערך שכבר מיוחס לעמודה לפי הבסיס הנוכחי. לכן Ck - Zk מודד כמה עוד אפשר לשפר ליחידה.

  1. משתנה נכנס: בשורת Ck - Zk בוחרים את החיובי הגדול; בשורת Zk - Ck את השלילי ביותר.
  2. משתנה יוצא: בעמודה הנכנסת p מחשבים br / ar,p רק עבור ar,p > 0. המנה הקטנה היא השורה שמגיעה ראשונה לאפס ולכן חייבת לצאת.
  3. ציר: מחלקים את שורת הציר באיבר הציר לקבלת 1, ואז מחסרים כפולות שלה מכל שורה אחרת עד ששאר עמודת הכניסה מתאפסת.
  4. עצירה וקריאה: עוצרים כשאין עוד עלות מצומצמת שמשפרת. משתנה בסיסי מקבל את אגף ימין של שורתו, משתנה לא בסיסי שווה 0, ואת Z קוראים משורת המטרה.

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

מרווח, עודף וערך דואלי

מרווח = הגבול העליון פחות מה שנוצל בפועל Slack = RHS - LHS  (LHS ≤ RHS) עודף = מה שהתקבל בפועל פחות דרישת המינימום Surplus = LHS - RHS  (LHS ≥ RHS) שינוי במטרה = ערך דואלי כפול שינוי בגבול האילוץ ΔZ* = DVr · Δbr

LHS הוא הערך שהתקבל באגף שמאל ו-RHS הוא הגבול באגף ימין. DVr אומר בכמה ישתנה הערך האופטימלי Z* אם נשנה את br ביחידה אחת.

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

קריאת דוח LINDO

OBJECTIVE VALUEערך המטרה
VALUEערך המשתנה
REDUCED COSTבכמה מקדם המטרה צריך להשתפר לפני שמשתנה אפס יהיה כדאי
SLACK OR SURPLUSכמה קיבולת נשארה או בכמה עברנו את דרישת המינימום
DUAL PRICESהשינוי בערך המטרה עבור יחידה נוספת באגף ימין
CURRENT COEF / RHSהערך הנוכחי
ALLOWABLE INC / DECכמות שינוי, לא נקודת קצה

שורה 1 בדוח היא פונקציית המטרה; אילוץ 1 במודל מופיע בדרך כלל בשורה 2.

רגישות מקדם מטרה

שיפוע קו המטרה מתקבל מיחס מקדמי המשתנים Z = c1 x1 + c2 x2,  mZ = -c1 / c2 תחום המקדם = הערך הנוכחי פחות הירידה ועד הערך הנוכחי ועוד העלייה ck - ADk ≤ ck,new ≤ ck + AIk

ck הוא הרווח או העלות של יחידה אחת ממשתנה k. אותו קודקוד נשאר אופטימלי כל עוד שיפוע קו המטרה נשאר בין שיפועי שתי הצלעות הפעילות. משנים מקדם אחד בכל פעם; אם c2 = 0, קו המטרה אנכי ובודקים אותו ישירות.

תחום אגף ימין

גבול תחתון = ערך נוכחי פחות ירידה מותרת br,min = br - ADr גבול עליון = ערך נוכחי ועוד עלייה מותרת br,max = br + AIr

AIr ו-ADr הם גודל העלייה והירידה המותרות מהערך הנוכחי, לא גבולות התחום עצמם.

LHS ≥ b,  S = LHS - b > 0AI = S,  AD = ∞
LHS ≤ b,  S = b - LHS > 0AI = ∞,  AD = S

פתרון גרפי

  1. לציור קו הגבול מחליפים את האי שוויון בשוויון.
  2. מוצאים שני חיתוכי צירים ומציבים נקודת בדיקה לבחירת הצד המותר.
  3. חותכים את כל האזורים המותרים ומסמנים רק את קודקודי התחום המשותף.
  4. מחשבים את המטרה בכל קודקוד; בוחרים את הגדול במקסימום או הקטן במינימום.
ax + by = c x = c / a  (y = 0, a ≠ 0),  y = c / b  (x = 0, b ≠ 0)

חיתוך שני קווים: אלימינציה

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

בדיקה: מציבים את הזוג שהתקבל בשתי המשוואות המקוריות.

אופטימיזציה קלאסית ותובלה

עמוד 2: נגזרות, לגראנז', KKT ובעיית תובלה

1. גרדיאנט ומטריצת הסיאן

f(X) היא פונקציית המטרה, ו-X=(x1,...,xn)T הוא וקטור משתני ההחלטה.

גרדיאנט = גוזרים את המטרה פעם אחת לפי כל משתנה
∇f(x1, x2) = ∂f/∂x1 ∂f/∂x2
הסיאן = גוזרים שוב: כל נגזרת גרדיאנט לפי כל משתנה
Hf(x1, x2) = ∂2f/∂x12 ∂2f/(∂x1∂x2) ∂2f/(∂x2∂x1) ∂2f/∂x22

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

2. קמירות וקעירות

f′′(x) ≥ 0קמורה בתחום
f′′(x) ≤ 0קעורה בתחום
Hf(X) ⪰ 0קמורה בתחום
Hf(X) ⪯ 0קעורה בתחום
f(tu + (1 - t)v) ≤ t f(u) + (1 - t) f(v) u, v ∈ D,  0 ≤ t ≤ 1

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

  • f+g קמורה אם f,g קמורות.
  • a≥0: af שומרת על קמירות.
  • a<0: af הופכת לקעורה.
  • למכפלה fg אין כלל; בודקים מחדש.

3. ללא אילוצים

  1. מוצאים מועמדים פנימיים: פותרים f′(x̄)=0 או ∇f(X̄)=0. נקודה יציבה היא רק מועמדת, עדיין לא תשובה.
  2. מסווגים כל מועמד בעזרת הנגזרת השנייה או הסיאן.
  3. בודקים גם קצות תחום, ואז משתמשים בקמירות או בקעירות כדי לקבוע אם התוצאה גלובלית.
מינימום מקומי במשתנה אחד f′′(x̄) > 0
מקסימום מקומי במשתנה אחד f′′(x̄) < 0
מינימום מקומי בכמה משתנים: כל המינורים המובילים חיוביים D1 > 0,  D2 > 0,  ... ⇒  H ≻ 0 מקסימום מקומי בכמה משתנים: סימני המינורים מתחלפים D1 < 0,  D2 > 0,  D3 < 0,  ... ⇒  H ≺ 0

D1, D2, ... הם הדטרמיננטים של הבלוקים השמאליים העליונים, לפי סדר גודל עולה. בשני משתנים: D1 = fxx ו-D2 = det(H). הסיאן לא מוגדרת בנקודה יציבה מעידה על אוכף; הסיאן למחצה בנקודה אחת אינה מספיקה לסיווג.

אם f′′(x̄)=0, עוברים לנגזרות מסדר גבוה עד הראשונה שאינה אפס: סדר זוגי וסימן חיובי נותן מינימום, זוגי ושלילי נותן מקסימום, וסדר אי זוגי אינו נותן קיצון.

4. לגראנז' לאילוצי שוויון

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

gr(X) הוא אגף שמאל של אילוץ r, br הוא הערך הנדרש, ו-λr הוא כופל האילוץ. בשוויון הכופל חופשי בסימן.

gr(X) = br,  r = 1,...,m לגראנז' = המטרה ועוד, לכל אילוץ, כופל כפול הפער מהדרישה L(X, λ) = f(X) + Σr λr [br - gr(X)] במועמד לאופטימום כל הנגזרות של לגראנז' מתאפסות ∂L / ∂xk = 0,  k = 1,...,n ∂L / ∂λr = br - gr(X) = 0
  1. בונים את L: המטרה ועוד כופל כפול הפער בכל אילוץ.
  2. גוזרים לפי כל משתנה החלטה ולפי כל כופל, ומשווים את כל המשוואות לאפס.
  3. פותרים את המערכת, מציבים באילוצים המקוריים ומסווגים את המועמדים.

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

5. KKT לאילוצי אי שוויון

הרעיון: לא כל אילוץ משפיע בנקודת האופטימום. תחילה מסדרים כל אילוץ כ-gr(X) ≤ br ומצמידים לו כופל λr ≥ 0, שמודד את השפעתו כשהוא פעיל.

מקסימום: מוסיפים כופל כפול המרווח שנותר באילוץ Lmax = f + Σr λr (br - gr) מינימום: מחסירים את אותו ביטוי לפי מוסכמת הסימנים של הקורס Lmin = f - Σr λr (br - gr)
אין כיוון שיפור מקומי∂L / ∂xk = 0
הנקודה מותרתgr(X) ≤ br
סימן הכופלים תקיןλr ≥ 0
פעיל או חסר השפעהλr [br - gr(X)] = 0

איך פותרים: לכל אילוץ בודקים שני מצבים: או שהוא פעיל ולכן gr(X) = br, או שאינו פעיל ולכן λr = 0. פותרים כל צירוף ופוסלים תוצאה שמפרה אילוץ או סימן כופל. אילוץ פעיל עדיין יכול לקבל כופל אפס.

מקסימום: f קעורה. מינימום: f קמורה. בשניהם gr קמורות. אז KKT מספיק לאופטימום גלובלי.

6. אי שליליות מפורשת

μk הוא הכופל של הגבול xk ≥ 0, ולכן הוא משפיע רק כאשר המשתנה נמצא על הגבול xk = 0.

גם המשתנה וגם הכופל אינם שליליים, ולפחות אחד מהם חייב להיות אפס xk ≥ 0,  μk ≥ 0 Lmax = f + Σr λr (br - gr) + Σk μk xk Lmin = f - Σr λr (br - gr) - Σk μk xk μk xk = 0

ברפיון משלים: xk > 0 ⇒ μk = 0, כי הגבול אינו פעיל; μk > 0 ⇒ xk = 0, כי הכופל פועל רק על הגבול.

7. רגישות בכופלים

שינוי משוער בערך האופטימלי = כופל כפול שינוי קטן בגבול
אילוץ שוויון Δf* ≈ λr · Δbr
אי שוויון במקסימום Δf* ≈ +λr · Δbr
אי שוויון במינימום Δf* ≈ -λr · Δbr
גבול תחתון במקסימום Δf* ≈ -μk · ΔLBk
גבול תחתון במינימום Δf* ≈ +μk · ΔLBk

f* הוא ערך המטרה האופטימלי, Δbr הוא שינוי קטן באגף ימין, ו-ΔLBk הוא שינוי בגבול התחתון. הקירוב תקף כל עוד קבוצת האילוצים הפעילים אינה משתנה.

בעיית תובלה: המודל

עלות כוללת = סכום של עלות ליחידה כפול הכמות שנשלחה בכל נתיב min  Z = Σr Σk cr,k xr,k מכל מקור שולחים את כל ההיצע; לכל יעד מספקים את כל הביקוש Σk xr,k = sr,  Σr xr,k = dk xr,k ≥ 0

r מסמן מקור ו-k יעד. xr,k היא הכמות שנשלחה, cr,k העלות ליחידה, sr ההיצע ו-dk הביקוש.

Σr sr = Σk dk

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

פתרון התחלתי

  • צפון מערבית: מתקדמים מהפינה לפי סדר התאים; העלויות אינן משפיעות על הבחירה.
  • עלות מזערית: בכל שלב בוחרים את התא הזמין הזול ביותר.
  • פוגל: הקנס מודד את המחיר של ויתור על התא הזול בשורה או בעמודה.
  1. בוחרים שורה או עמודה עם הקנס הגדול.
  2. מקצים בתא הזול את מינימום ההיצע והביקוש שנותרו.
  3. מוחקים שורה או עמודה שהושלמה ומחשבים קנסות מחדש.

נדרשים m+n-1 תאים בסיסיים. אם חסרים, מוסיפים תא בסיסי בכמות אפס בלי ליצור מעגל.

פוטנציאלים ומעגל שיפור

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

  1. בתאים הבסיסיים פותרים ur + vk = cr,k. ur הוא פוטנציאל שורה ו-vk פוטנציאל עמודה; קובעים אחד מהם לאפס.
  2. בתא לא בסיסי מחשבים Δr,k = cr,k - ur - vk: השינוי בעלות אם התא ייכנס.
  3. אם כל Δr,k ≥ 0, אין נתיב שמוזיל את העלות והפתרון אופטימלי.
  4. אחרת, התא השלילי ביותר נכנס לבסיס.
  5. בונים מעגל דרך תאים בסיסיים בלבד, בתנועות אופקיות ואנכיות, ומסמנים לסירוגין +,-,+,-.
כמות ההעברה במעגל = המשלוח הקטן ביותר בתאי המינוס θ = min { xr,k : (r, k) ∈ M- } מוסיפים אותה בתאי הפלוס ומחסירים בתאי המינוס xr,k,new = xr,k ± θ

θ מונע משלוח שלילי; תא לא בסיסי עם Δr,k = 0 עשוי לתת אופטימום חלופי.