سیستم همکاری در فروش سپیده

•          تعريف

يک گراف اوزان  متصل ناميده ميشود اگر از هر گره به گره ديگر راهي باشد.

يک جزء (Component)از گراف نامتصل  G  خود يک زيرگراف اوزان با حد اکثر گره هاي متصل است.

تحليل ساختار گراف G(V,W)

ساختار گراف نکات جالبي را در ارتباط با مساله به ما نشان مي دهد

1  مثلا اگرN1, N2به هم و به  چند E وصل باشند ولي از ساير Nها  جدا باشند، در اين صورت يافتن محل بهينه N1, N2 مستقل از بقيه N هاست.

2  به طور مثال اگر در اين گراف V12 , W13 هر دو صفر باشند اين گراف را ميتوان به دو زير گراف تجزيه نمود که مساله متناظر هر يک از آنها را ميتوان به صورت مستقل حل نمود.

3  اگر يک  N فقط با يک تسهيل ديگر (چه جديد چه موجود) ارتباط داشته باشد ، مکان بهينه آن حتما روي همان تسهيل خواهد بود.

4  اگر به طور مثال     N4 به E1  ,  E2 وصل بوده وبه هيچ يک ازN هاي ديگر متصل نباشد، مکان بهينه آن بسته به اينکه W  کدام يک بزرگتر باشد، روي E1  يا  E2 قرار ميگيرد. 

مثال 1

E₁توليد سيمان(2000و1000)

E₂توليدات فولادي(600و700)

E₃بارگيري(0و1300)

N₁قالب گيري بتن

N₂واحد مونتاژ و انبار

X₁=x₂=700

Y₁=y₂=600

Total cost =18.4

•          درمسائلي که تا کنون بررسي شد فرض بر اين بود که اوزان(ماتريس w) معلوم مي باشد .اما اين فرض هميشه درست نيست .

•          در اين بحث در مورد مسائلي صحبت مي کنيم که وزن ها خود مانند مکان تسهيلات جديد متغير تصميم هستند .

•          به عنوان مثال،     مکانيابي مراکز توزيع يا انبارهايي که کالاها را از تسهيلات دريافت و بين مشتريان توزيع مي کنند.در حالتي که تخصيص مشتريان به انبار ها نيز مورد نظر ماست.

•          مثال 4  مساله جايابي سکوهايي براي حفر چاه هاي نفت و همزمان تخصيص چاه هاي نفت به هر يک از سکوها براي حداقل نمودن مجموع هزينه ساخت سکوها و حفرچاه ها.

متغير هاي تصميم سايز هر سکو – مکان هر سکو – چاه هاي تخصيص يافته به هر سکو

مفروضات مساله مکان چاه هاي کشف شده – نوع سکو ها – نوع  ساخت سکوها

متغيرهاي غير قابل کنترل عمق اهداف – خصوصيات زمين شناسي – شرايط دريا و امواج