תכנון לינארי

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

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

הצורה הסטנדרטית והצורה הקאנונית

מקובל לנסח בעיות תכנון לינארי בצורה הידועה כ-"צורה הסטנדרטית". כל בעיית תכנון לינארי ניתן לנסח בצורה זו:

מקסם את $\ c^{t}x$ תחת האילוצים $0\leq x$ ו-$\ Ax\leq b$.

כאשר:

A - מטריצה ממשית $\ (a_{ij})$ מסדר $\ m\times n$.

b - וקטור ממשי $\ (b_{i})$ מסדר m.

c - וקטור ממשי $\ (c_{i})$ מסדר n.

x - וקטור ממשי $\ (x_{i})$ מסדר n.

דוגמה

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

נניח כי קיימים $\ n$ סוגים שונים של פריטי מזון שניתן להכניס לדיאטה, ו-$\ m$ סוגים שונים של אבות מזון שיש להביא בחשבון בעת בניית הדיאטה: ויטמינים, חלבונים, מינרלים וכדומה. כמו כן קיים לכל מזון ערך קלורי.

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

כלומר, בבעיה זו הווקטור $\ (x_{i})$ מציין את כמות המזון מכל סוג שנצרכת במהלך הדיאטה, הווקטור $\ (c_{i})$ מציין את כמות הקלוריות שבכל אחד מסוגי המזון, הווקטור $\ (b_{i})$ מציין את הכמות שיש לצרוך מכל אחד מאבות המזון, ואילו המטריצה A מכילה את המידע על כמות אבות המזון שמצוייה בכל אחד מסוגי המזון (כל עמודה שייכת לסוג מזון אחר, ושורותיה מפרטות את כמות אבות המזון שבו).

הבעיה עצמה היא מציאת המינימום של $\ c^{t}x$ תחת האילוצים $0\leq x$ ו-$\ Ax\geq b$

ראו גם

• שיטת הסימפלקס