דף נוסחאות ושיטות עבודה - מודלים דטרמיניסטיים

שיטת עבודה כללית

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

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

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

ניסוח מודל

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

max/min Z = ∑ⱼ cⱼxⱼ פונקציית המטרה: מסכמים את התרומה של כל משתנה ובוחרים אם למקסם או למזער.

∑ⱼ aᵢⱼxⱼ {≤, =, ≥} bᵢ, i = 1,...,m כל ערך של i יוצר אילוץ נפרד; סימן האילוץ נקבע לפי משמעות הדרישה.

xⱼ ≥ 0, j = 1,...,n מוסיפים אי־שליליות כאשר ערך שלילי אינו אפשרי מבחינה מעשית.

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

בדיקת ליניאריות

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

תרגום משפטים נפוצים

ניסוח מילולי	תבנית מתמטית
לכל היותר, קיבולת, אין לעבור	שימוש ≤ קיבולת
לפחות, דרישת מינימום	כמות ≥ דרישה
בדיוק, איזון מלא	אגף שמאל = אגף ימין
A לפחות פי k מ-B	A ≥ kB
A לפחות p אחוז מהסך T	A ≥ (p/100)T
שימור או מאזן	כניסה + ייצור = יציאה + צריכה
בחירה כן או לא	y ∈ {0,1}
כמות של פריטים שאינם ניתנים לחלוקה	x ∈ ℤ, x ≥ 0

סדר עבודה

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

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

פתרון גרפי בשני משתנים

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

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

חיתוכי קו עם הצירים

ax + by = c מתחילים ממשוואת הגבול של האילוץ.

x = c/a (y = 0) לחיתוך עם ציר x מציבים y=0, מקבלים ax=c ומחלקים ב-a.

y = c/b (x = 0) לחיתוך עם ציר y מציבים x=0, מקבלים by=c ומחלקים ב-b.

a,b הם מקדמי המשתנים ו-c הוא אגף ימין. הנוסחה x=c/a דורשת a≠0, והנוסחה y=c/b דורשת b≠0; כאשר המקדם המתאים הוא אפס, אין חיתוך יחיד עם אותו ציר ולכן לא משתמשים בנוסחת החלוקה.

חיתוך מדויק של שני קווים

a₁x + b₁y = c₁ משוואת הגבול הראשונה.

a₂x + b₂y = c₂ משוואת הגבול השנייה.

Δ = a₁b₂ - a₂b₁ מחשבים את הדטרמיננטה של מקדמי המשתנים. אם Δ=0, אין חיתוך יחיד ולכן לא ממשיכים לנוסחאות החלוקה.

x = (c₁b₂ - c₂b₁)/Δ כלל קרמר: מחליפים את עמודת המקדמים של x באגפי ימין ומחלקים בדטרמיננטה המקורית.

y = (a₁c₂ - a₂c₁)/Δ מחליפים את עמודת המקדמים של y באגפי ימין ומחלקים באותה דטרמיננטה.

a₁,b₁,c₁ הם נתוני הקו הראשון, a₂,b₂,c₂ הם נתוני הקו השני, ו-Δ הוא הדטרמיננטה. הנוסחאות תקפות כאשר Δ ≠ 0; אם Δ=0, הקווים מקבילים או חופפים.

סיווג תוצאת הפתרון

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

בדיקת תשובה: כל קודקוד שנבדק חייב לקיים את כל האילוצים. נקודת חיתוך של שני קווים אינה בהכרח נקודה אפשרית.

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

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

לפני ההמרה מוודאים שאגף ימין אינו שלילי. אם כופלים אילוץ ב--1, הופכים גם את כיוון אי־השוויון.

מעבר לצורה סטנדרטית

סוג אילוץ	המרה לשוויון
ax ≤ b	מוסיפים משתנה סרק: ax + s = b, כאשר s ≥ 0.
ax ≥ b	מחסרים משתנה עודף: ax - e = b, כאשר e ≥ 0. אם אין בסיס התחלתי, מוסיפים גם משתנה מלאכותי.
ax = b	אם אין משתנה בסיסי טבעי, מוסיפים משתנה מלאכותי לשלב הראשון.

s הוא משתנה סרק המודד קיבולת לא מנוצלת; e הוא משתנה עודף המודד כמה עברנו דרישת מינימום.

מושגים בסיסיים

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

איטרציית סימפלקס

בוחרים משתנה נכנס: בטבלת מקסימום עם שורת Cⱼ-Zⱼ, בוחרים את הערך החיובי הגדול ביותר. אם הטבלה משתמשת ב-Zⱼ-Cⱼ, בוחרים את הערך השלילי ביותר.
בוחרים משתנה יוצא: מחשבים bᵢ/aᵢp רק בשורות שבהן aᵢp > 0, ובוחרים את היחס האי־שלילי הקטן ביותר.
מבצעים ציר: מחלקים את שורת הציר באיבר הציר ומאפסים את שאר עמודת הציר.
בודקים אופטימליות: עוצרים כאשר אין עלות מצומצמת שמאפשרת שיפור לפי מוסכמת הטבלה.

Cⱼ הוא מקדם המשתנה j בפונקציית המטרה, ו-Zⱼ הוא הערך שמתקבל עבור אותה עמודה מהמקדמים של הבסיס הנוכחי. p היא עמודת המשתנה הנכנס, aᵢp הוא המקדם בעמודה זו ובשורה i, ו-bᵢ הוא אגף ימין של אותה שורה.

אם בעמודת הכניסה אין אף aᵢp>0, אי אפשר לבצע מבחן מנה והבעיה אינה חסומה בכיוון השיפור. תיקו ביחס המינימלי עלול ליצור פתרון מנוון, ולכן בוחרים לפי כלל עקבי וממשיכים לבדוק את הטבלה.

משתנים מלאכותיים

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

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

ניתוח רגישות ודוח LINDO

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

מילון שדות בדוח LINDO

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

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

מרווח, עודף ואילוץ פעיל

Slack = RHS - LHS (LHS ≤ RHS) Surplus = LHS - RHS (LHS ≥ RHS)

LHS הוא ערך אגף שמאל ו-RHS הוא ערך אגף ימין. ערך אפס פירושו אילוץ פעיל (הדוק). מרווח או עודף חיובי מחייב ערך דואלי אפס; אילוץ פעיל עדיין עשוי לקבל ערך דואלי אפס.

ערך דואלי ושינוי באגף ימין

DVᵢ = ΔZ*/Δbᵢ הגדרה: הערך הדואלי הוא השינוי במטרה לכל יחידת שינוי באגף ימין.

ΔZ* = DVᵢ · Δbᵢ מכפילים את שני האגפים ב-Δbᵢ. משתמשים בצורה הזאת כדי לחשב שינוי כולל.

DVᵢ הוא הערך הדואלי של אילוץ i, Δbᵢ הוא השינוי באגף ימין, ו-ΔZ* הוא השינוי בערך המטרה האופטימלי.

תחום התקפות של אגף ימין

bᵢ - ADᵢ ≤ bᵢ,new ≤ bᵢ + AIᵢ

bᵢ הוא אגף ימין הנוכחי, AIᵢ היא העלייה המותרת, ADᵢ היא הירידה המותרת ו-bᵢ,new הוא הערך החדש. בדוח, INFINITY פירושו שאין גבול בכיוון המצוין במסגרת ניתוח הרגישות.

השלמת טווח של אילוץ לא פעיל

סוג האילוץ והמרחק משוויון	הטווח כל עוד הפתרון הנוכחי נשאר אפשרי
LHS≥b, עודף S=LHS-b>0	AI=S, AD=∞
LHS≤b, מרווח S=b-LHS>0	AI=∞, AD=S

AI היא העלייה המותרת ו-AD היא הירידה המותרת. בכיוון שמרפה את האילוץ אין גבול; בכיוון שמהדק אותו אפשר להתקדם רק עד שהמרווח או העודף מתאפס.

כדאיות רכישת משאב במקסום רווח

ΔZ_net = (DV - c)q

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

רגישות של מקדמי המטרה בפתרון גרפי

עבור Z=c₁x₁+c₂x₂, שיפוע קו המטרה הוא:

m_Z = -c₁/c₂

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

תחום התקפות של מקדם מטרה בדוח

cⱼ - ADⱼ ≤ cⱼ,new ≤ cⱼ + AIⱼ

cⱼ הוא המקדם הנוכחי של משתנה j, ו-cⱼ,new הוא המקדם החדש. גם כאן העלייה והירידה המותרות הן כמויות שינוי ולא נקודות קצה.

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

קמירות, לגראנז' ותנאי KKT

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

שלב 1: מסווגים את הבעיה

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

שלב 2: כותבים גרדיאנט ומטריצת הסיאן

נסמן את פונקציית המטרה ב-f(X) ואת וקטור המשתנים ב-X=(x₁,…,xₙ)ᵀ. הגרדיאנט אוסף את כל הנגזרות מסדר ראשון, והסיאן אוסף את כל הנגזרות מסדר שני:

∇f(X) = (∂f/∂x₁, ∂f/∂x₂, …, ∂f/∂xₙ)ᵀ H_f(X) = [∂²f/(∂xᵢ∂xⱼ)]_n×n H_f(x₁,x₂) = ⎡ ∂²f/∂x₁² ∂²f/(∂x₁∂x₂) ⎤ ⎣ ∂²f/(∂x₂∂x₁) ∂²f/∂x₂² ⎦

n הוא מספר המשתנים; i מונה שורות ו-j מונה עמודות בהסיאן. הסימון ᵀ מציין וקטור עמודה.

שלב 3: קובעים קמירות או קעירות

f″(x)≥0 לכל x במשתנה אחד: הפונקציה קמורה בכל התחום שנבדק.

f″(x)≤0 לכל x במשתנה אחד: הפונקציה קעורה בכל התחום שנבדק.

H_f(X)⪰0 לכל X בתחום בכמה משתנים: הסיאן חיובית למחצה ולכן f קמורה.

H_f(X)⪯0 לכל X בתחום הסיאן שלילית למחצה ולכן f קעורה.

אם לא משתמשים בנגזרות, אפשר לבדוק ישירות את ההגדרה: לכל u,v∈D ולכל t∈[0,1], קמירות דורשת f(tu+(1-t)v)≤tf(u)+(1-t)f(v); כיוון הפוך מגדיר קעירות. D הוא תחום קמור ו-t הוא משקל.

f,g קמורות ⇒ f+g קמורה בסכום, אי־שוויונות הקמירות מתחברים בלי לשנות כיוון.

a≥0, f קמורה ⇒ af קמורה כפל בקבוע אי־שלילי שומר על כיוון אי־השוויון.

a<0, f קמורה ⇒ af קעורה כפל בקבוע שלילי הופך את כיוון אי־השוויון.

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

f ו-g הן פונקציות המוגדרות על אותו תחום קמור, ו-a הוא קבוע ממשי.

מסלול א: אין אילוצים

f′(x̄)=0 או ∇f(X̄)=0 פותרים את כל משוואות הנגזרות ומקבלים נקודות יציבות מועמדות.

f″(x̄)>0 / f″(x̄)<0 במשתנה אחד: חיובי נותן מינימום מקומי; שלילי נותן מקסימום מקומי.

Dₖ>0 לכל k בכמה משתנים: כל המינורים הראשיים המובילים חיוביים, ולכן ההסיאן חיובית מוגדרת ומתקבל מינימום מקומי.

(-1)ᵏDₖ>0 לכל k הסימנים מתחלפים, ההסיאן שלילית מוגדרת ומתקבל מקסימום מקומי.

X̄ היא הנקודה הנבדקת ו-Dₖ הוא הדטרמיננטה של תת־המטריצה הראשית המובילה בגודל k×k. הסיאן לא מוגדרת נותנת נקודת אוכף; הסיאן למחצה בנקודה אחת אינה מכריעה לבדה. אם f קמורה בכל התחום, מינימום מקומי הוא גלובלי; אם היא קעורה בכל התחום, מקסימום מקומי הוא גלובלי.

אם במשתנה אחד f″(x̄)=0, מחפשים סדר r שעבורו f′(x̄)=…=f⁽ʳ⁻¹⁾(x̄)=0 אבל f⁽ʳ⁾(x̄)≠0. סדר זוגי עם סימן חיובי נותן מינימום, סדר זוגי עם סימן שלילי נותן מקסימום, וסדר אי־זוגי אינו נותן קיצון. בתחום סגור בודקים גם נקודות קצה.

מסלול ב: אילוצי שוויון בלבד

gᵢ(X) הוא אגף שמאל של אילוץ i, bᵢ הוא אגף ימין, ו-m הוא מספר האילוצים.

gᵢ(X)=bᵢ, i=1,…,m כותבים את כל אילוצי השוויון ומצמידים לכל אחד כופל λᵢ חופשי בסימן.

L(X,λ)=f(X)+∑ᵢλᵢ[bᵢ-gᵢ(X)] בונים את פונקציית לגראנז' לפי מוסכמת הקורס.

∂L/∂xⱼ=0, j=1,…,n גוזרים לפי כל משתני ההחלטה.

∂L/∂λᵢ=bᵢ-gᵢ(X)=0 גזירה לפי הכופלים מחזירה את אילוצי השוויון המקוריים.

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

מסלול ג: אילוצי אי־שוויון

gᵢ(X)≤bᵢ תחילה מסדרים כל אילוץ פונקציונלי לצורת הקורס.

Lₘₐₓ=f(X)+∑ᵢλᵢ[bᵢ-gᵢ(X)] במקסימום מוסיפים את המרווח, עם λᵢ≥0.

Lₘᵢₙ=f(X)-∑ᵢλᵢ[bᵢ-gᵢ(X)] במינימום מחסרים את המרווח, עם אותם כופלים לא שליליים.

∂L/∂xⱼ=0 1. יציבות: משוואה אחת לכל משתנה החלטה.

gᵢ(X)≤bᵢ 2. אפשריות ראשונית: המועמד מקיים את האילוצים.

λᵢ≥0 3. אפשריות דואלית: הכופלים בעלי הסימן הנדרש.

λᵢ[bᵢ-gᵢ(X)]=0 4. רפיון משלים: אם האילוץ אינו פעיל אז λᵢ=0; אם λᵢ>0 אז האילוץ פעיל.

פותרים מצבי פעילות: בכל אילוץ בוחנים gᵢ(X)=bᵢ או λᵢ=0, פותרים, ואז פוסלים כל מועמד שמפר אילוץ או סימן כופל. אילוץ פעיל עדיין יכול לקבל כופל אפס.

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

מסלול ד: מוסיפים אילוצי אי־שליליות

xⱼ≥0, μⱼ≥0 מצמידים כופל μⱼ לכל אילוץ אי־שליליות מפורש.

Lₘₐₓ=f+∑ᵢλᵢ(bᵢ-gᵢ)+∑ⱼμⱼxⱼ במקסימום מוסיפים גם את איברי האי־שליליות.

Lₘᵢₙ=f-∑ᵢλᵢ(bᵢ-gᵢ)-∑ⱼμⱼxⱼ במינימום מחסרים אותם.

μⱼxⱼ=0 מוסיפים רפיון משלים: אם xⱼ>0 אז μⱼ=0; אם μⱼ>0 אז xⱼ=0.

לאחר הרחבת L, חוזרים לארבעת תנאי KKT של מסלול ג וכותבים את משוואות היציבות לפי הלגראנז' המורחב.

שלב סיום: אימות ורגישות

f*=f(X*) מציבים את המועמד בכל האילוצים ואז מחשבים את ערך המטרה.

Δf*≈λᵢΔbᵢ באילוץ שוויון: הכופל נותן את השינוי המקומי בעקבות שינוי באגף ימין.

מקסימום: Δf*≈+λᵢΔbᵢ באילוץ אי־שוויון של בעיית מקסימום משתמשים בסימן פלוס.

מינימום: Δf*≈-λᵢΔbᵢ באילוץ אי־שוויון של בעיית מינימום משתמשים בסימן מינוס.

xⱼ≥rⱼ, מקסימום: Δf*≈-μⱼΔrⱼ העלאת גבול תחתון מצמצמת את התחום ולכן ערך המקסימום אינו יכול לעלות.

xⱼ≥rⱼ, מינימום: Δf*≈+μⱼΔrⱼ העלאת גבול תחתון מצמצמת את התחום ולכן ערך המינימום אינו יכול לרדת.

X* הוא הפתרון האופטימלי, f* הוא ערך המטרה האופטימלי, rⱼ הוא הגבול התחתון של xⱼ, ו-Δbᵢ,Δrⱼ הם שינויים קטנים באגפי הימין. נוסחאות הרגישות תקפות רק כל עוד מצב האילוצים הפעילים אינו משתנה.

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

בעיית תובלה

מחלקים כמויות ממקורות ליעדים כך שכל היצע וכל ביקוש מתקיימים והעלות הכוללת מזערית.

min Z = ∑ᵢ∑ⱼ cᵢⱼxᵢⱼ ממזערים את עלות המשלוח הכוללת בכל מסלולי המקור-יעד.

∑ⱼ xᵢⱼ = sᵢ, i = 1,...,m לכל מקור בנפרד, סכום המשלוחים היוצאים שווה להיצע שלו.

∑ᵢ xᵢⱼ = dⱼ, j = 1,...,n לכל יעד בנפרד, סכום המשלוחים הנכנסים שווה לביקוש שלו.

xᵢⱼ ≥ 0 כמות משלוח אינה יכולה להיות שלילית.

סימון	פירוש
xᵢⱼ	הכמות הנשלחת ממקור i ליעד j.
cᵢⱼ	עלות משלוח יחידה ממקור i ליעד j.
sᵢ	ההיצע במקור i.
dⱼ	הביקוש ביעד j.

איזון הבעיה

∑ᵢ sᵢ = ∑ⱼ dⱼ

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

פתרון התחלתי אפשרי

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

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

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

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

בדיקת אופטימליות בשיטת הפוטנציאלים

בתאים בסיסיים פותרים uᵢ+vⱼ=cᵢⱼ. אפשר לקבוע פוטנציאל אחד לאפס.
לכל תא לא בסיסי מחשבים Δᵢⱼ=cᵢⱼ-uᵢ-vⱼ.
בבעיית מינימום, אם כל Δᵢⱼ ≥ 0, הפתרון אופטימלי.
אם יש ערך שלילי, מכניסים את התא השלילי ביותר ובונים ממנו מעגל סגור שנע אופקית ואנכית דרך תאים בסיסיים בלבד.
מסמנים את תאי המעגל לסירוגין פלוס ומינוס, החל מפלוס בתא הנכנס.
מחשבים θ כהקצאה הקטנה ביותר בתאי המינוס, מוסיפים θ בתאי הפלוס ומחסרים אותו בתאי המינוס.
מחשבים מחדש את הפוטנציאלים ואת העלויות המצומצמות לאחר העדכון.

אם אין עלויות מצומצמות שליליות אך לתא לא בסיסי יש Δᵢⱼ=0, הפתרון הנוכחי אופטימלי וייתכן פתרון אופטימלי חלופי.

θ = min{xᵢⱼ : (i,j) ∈ M₋} M₋ היא קבוצת תאי המינוס במעגל. בחירה זו מבטיחה שאף הקצאה לא תהפוך לשלילית ושאחד מתאי המינוס יוכל לצאת מהבסיס.

xᵢⱼ,new = xᵢⱼ ± θ מוסיפים בתאי הפלוס ומחסרים בתאי המינוס; כך נשמרים כל סכומי השורות והעמודות.

uᵢ ו-vⱼ הם פוטנציאלים של מקור ויעד; Δᵢⱼ היא העלות המצומצמת של תא שאינו בסיסי.

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

בדיקת תשובה לפני הגשה

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