שאלה בתכנות לינארי.
נתון גרף מכוון G=(V,E)zzz, מקור siת בור ti ודרישה di לכל i בין 1 ל k, ולכל קשת e קיבול c(e)zzz ועלות b(e)zzz (מספרים ממשיים חיוביים) ליחידת זרימה בקשת. המטרה היא להזרים di יחידות זרימה מסוג i מsi לti (לכל i בין 1 לk), כך שסך כל הזרימה על כל קשת לא תחרוג מהקיבול שלה ושהעלות הכוללת של הזרימה תהיה מינימלית. כתבו תכנית לינארית המוצאת פיתרון. הפתרון שלי הוא כזה: משתנים Xi,e- כמות החומר מסוג i שנזרים בקשת e. פונ' מטרה: minΣΣxi,e*b(e)zzz (כאשר הΣ הראשונה היא על כל הi והשניה היא על כל הקשתות בE). אילוצים: 1. לכל קשת e מתקיים Σxi,e<=c(e)zzz (הΣ היא על כל הi. לא מזרימים בכל קשת יותר מהקיבול שלה). 2. xi,e לא שלילי לכל i ולכל e (לא מזרימים כמויות שליליות). חסרה לי דרישה בנוגע לdi. הבעיה היא שאני לא סתם יכול לכתוב Σxi,e=di לכל i כאשר הסכימה היא על הקשתות בE. צריך שהקשת e תהיה על מסלול בין si ל ti. איך אני כותב את הדרישה הזו? תודה מראש.
נתון גרף מכוון G=(V,E)zzz, מקור siת בור ti ודרישה di לכל i בין 1 ל k, ולכל קשת e קיבול c(e)zzz ועלות b(e)zzz (מספרים ממשיים חיוביים) ליחידת זרימה בקשת. המטרה היא להזרים di יחידות זרימה מסוג i מsi לti (לכל i בין 1 לk), כך שסך כל הזרימה על כל קשת לא תחרוג מהקיבול שלה ושהעלות הכוללת של הזרימה תהיה מינימלית. כתבו תכנית לינארית המוצאת פיתרון. הפתרון שלי הוא כזה: משתנים Xi,e- כמות החומר מסוג i שנזרים בקשת e. פונ' מטרה: minΣΣxi,e*b(e)zzz (כאשר הΣ הראשונה היא על כל הi והשניה היא על כל הקשתות בE). אילוצים: 1. לכל קשת e מתקיים Σxi,e<=c(e)zzz (הΣ היא על כל הi. לא מזרימים בכל קשת יותר מהקיבול שלה). 2. xi,e לא שלילי לכל i ולכל e (לא מזרימים כמויות שליליות). חסרה לי דרישה בנוגע לdi. הבעיה היא שאני לא סתם יכול לכתוב Σxi,e=di לכל i כאשר הסכימה היא על הקשתות בE. צריך שהקשת e תהיה על מסלול בין si ל ti. איך אני כותב את הדרישה הזו? תודה מראש.
