שיעור תאוריה

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

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

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

אינטואיציה

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

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

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

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

באילוץ מסוג ≤ מוסיפים משתנה סרק:

a₁x₁ + ... + aₙxₙ ≤ b a₁x₁ + ... + aₙxₙ + s = b, s ≥ 0

המשתנה s הוא המרווח. כאשר s = 0, האילוץ פעיל; כאשר s > 0, נשאר משאב לא מנוצל.

באילוץ מסוג ≥ מחסרים משתנה עודף:

a₁x₁ + ... + aₙxₙ ≥ b a₁x₁ + ... + aₙxₙ - e = b, e ≥ 0

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

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

min Z = c₁x₁ + ... + cₙxₙ max (-Z) = -c₁x₁ - ... - cₙxₙ

הפתרון במשתני ההחלטה אינו משתנה; רק סימן ערך המטרה מתהפך.

שיטת פתרון

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

דוגמה: מציאת הפתרון הבסיסי ההתחלתי

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

max Z = 3x₁ + 2x₂ x₁ + x₂ ≤ 4 2x₁ + x₂ ≤ 6 x₁, x₂ ≥ 0

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

שני האילוצים הם מסוג ≤, ולכן מוסיפים משתני סרק s₁ ו-s₂. כל משתנה מודד את הקיבולת שלא נוצלה באילוץ שלו:

x₁ + x₂ + s₁ = 4 2x₁ + x₂ + s₂ = 6

בוחרים את s₁ ו-s₂ כמשתנים בסיסיים. לכן המשתנים הלא בסיסיים x₁ ו-x₂ מוצבים באפס. x₁ = 0, x₂ = 0
פותרים עבור המשתנים הבסיסיים. לאחר ההצבה, כל משוואה קובעת ישירות את ערך משתנה הסרק שלה. s₁ = 4, s₂ = 6
בודקים אפשריות. כל ארבעת המשתנים אי-שליליים, ולכן זהו פתרון בסיסי אפשרי. (x₁, x₂, s₁, s₂) = (0, 0, 4, 6)
מציבים בפונקציית המטרה. Z = 3(0) + 2(0) = 0

גאומטרית, הפתרון (x₁, x₂) = (0,0) הוא קודקוד של התחום האפשרי. צעדי הסימפלקס יעברו לקודקודים סמוכים תוך החלפת משתנה בסיסי ולא בסיסי.

תוצאה: הפתרון הבסיסי האפשרי ההתחלתי הוא (x₁, x₂, s₁, s₂) = (0,0,4,6), ובו Z = 0.

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