|
|
עמוד:69
הגיאומטרי שתואר לעיל להליך אלגברי . בסעיף זה נציג אפוא את השיטה האלגברית של שיטת הסימפלקס , ונייחס אותה למושגים שהוצגו בדיון שלעיל . בהליך אלגברי , נוח יותר לדון באילוצי שוויון מאשר באילוצי אי-שוויון . לפיכך , השלב הראשון בפתרון בשיטת הסימפלקס הוא להמיר את האילוצים הפונקציונליים , הנתונים כאי-שוויונות , באילוצי שוויון שקולים . אילוצי האי-שליליות יכולים להישאר בצורתם המקורית , שכן האלגוריתם מתייחס אליהם רק בעקיפין . המרה זו מתבצעת על-ידי הוספת משתני סרק . ( slack variables ) על מנת להדגים זאת , נתבונן באילוץ הפונקציונלי הראשון בדוגמה שלנו ו X { + X < 2 משתנה הסרק לאילוץ זה הוא ו — 1 — SXJ £ /\ ' 1 — ^ שהוא בדיוק ההפרש שבין שני אגפי האי-שוויון . לכן נקבל . X , + X + X = 2 האילוץ המקורי x + x < 2 מתקיים רק כאשר , * > 0 ולכן האילוץ x / + X < 2 שקול למערכת האילוצים : *! + * 2 + * = 2 x > 0 נשתמש אפוא במערכת זו כתחליף לאילוץ המקורי . הוספת משתני סרק לכל יתר האילוצים הפונקציונליים במודל התכנון הליניארי המקורי של הדוגמה תיתן את המודל השקול שלהלן : Maximum Z = 5 X ] + 3 X 1 - 7 Subject to : 1 ) X ] + X + X = 2 , + 2 X + X = 2 2 ) A A ' , > 0 X > 0 X > 0 X > 0
|
|