وبلاگ رسمی دکتر ماریا افشاری راد
درباره
این وبلاگ صرفا جهت اطلاع رسانی، ثبت تمرینات تحویلی، طرح درس ها و پرسش و پاسخ دانشجویان طراحی شده است. 
اطلاعات تماس
موضوعات
۱۳۹۵ خرداد
۱۳۹۵/۰۳/۲۳
۱۱:۲۵
ماریا افشاری راد
۱۸۸
۰

کران دوگان برای مساله کوله پشتی از طریق حل مساله رهاسازی شده به دست می آید. پس ابتدا مساله زیر را حل می کنیم:

max z=42x1+26x2+35x3+71x4+53x5

s.t.

14x1+10x2+12x3+25x4+20x5<=69

x1<=1

x2<=1

x3<=1

x4<=1

x5<=1

جواب های زیر به دست می آیند:

x=(1,0,1,1,0.9) , Zu*=195.7

برای به دست آوردن کران اولیه نیز کافی است یک جواب شدنی دلخواه برای مساله کوله پشتی انتخاب کنیم. مثلا انتخاب کالاهای 1و2و3 و4 که در این صورت مقدار تابع هدف 42+26+35+71=174 خواهد بود.


بنابراین اگر *Z مقدار دقیق بهینه تابع هدف در مساله کوله پشتی باشد، داریم:   

174 <= Z* <= 195.7

پایان مهلت تمرینات
۱۳۹۵/۰۳/۲۱
۲۰:۲۰
ماریا افشاری راد
۱۹۶
۰

به اطلاع کلیه دانشجویان دروس ترکیبیات و برنامه ریزی عدد صحیح می رساند، از آنجایی که پاسخ همه تمرینات حل نشده در کلاس در وبلاگ گذاشته شده است،  از این پس (95/3/21) هیچ تمرین تحویلی پذیرفته نخواهد بود.

با آروزی پیروزی در آزمون ها

حل مسائل ترکیبیات
۱۳۹۵/۰۳/۲۱
۲۰:۱۴
ماریا افشاری راد
۱۷۶
۰

۱۳۹۵/۰۳/۲۱
۱۸:۳۳
ماریا افشاری راد
۲۳۸
۰

مدل رهاسازی خطی مساله تطابق برای گراف مساله 1 به شکل زیر است:

max x19+x111+x28+x210+x211+x37+x312+x49+x511+x611+x612

s.t.

x19+x111<=1

x28+x210+x211<=1

x37+x312<=1

x611+x612<=1

x19+x49<=1

x111+x211+x511+x611<=1

x312+x612<=1

x19<=1

x111<=1

x28<=1

x210<=1

x211<=1

x37<=1

x312<=1

x49<=1

x511<=1

x611<=1

x612<=1

جواب های زیر به دست می آیند:

x28=x37=x49=x511=x612=1 , Z*=5

(سایر x ها برابر با صفر هستند. )

در حالت وزن دار نیز تنها تابع هدف به شکل زیر در می آید:

max 9x19+4x111+7x28+3x210+5x211+6x37+3x312+x49+3x511+7x611+6x612

جواب های زیر به دست می آیند:

x28=x19=x37=x511=x612=1 , Z*=31

(سایر x ها برابر با صفر هستند. )

همان طور که می بینیم، به دلیل دوافرازه بودن گراف، جواب های مدل رهاسازی شده، صحیح هستند.

۱۳۹۵/۰۳/۲۱
۱۶:۲۷
ماریا افشاری راد
۲۰۵
۰

فرض کنید C={C1,...,Ck} مجموعه ای از خوشه های گراف G باشد که هر یال G توسطه یکی از خوشه ها پوشش داده شده است. آنگاه اگر S یک مجموعه مستقل راسی باشد، بنابراین هیچ یک از خوشه ها شامل بیش از یک نقطه از S نمی تواند باشد. پس می توان گفت تعداد اعضای S از تعداد خوشه ها کمتر یا مساوی است: |S|<=k.

که این همان رابطه ضعیف دوگانی است.

در گراف زیر بزرگترین خوشه از اندازه 3 است و 4 تا از این خوشه ها موجود است که روی هم رفته شامل 10 یال می شوند. این ده یال را با رنگ قرمز نشان داده ایم. 9 یال دیگر نیز توسط این چهار خوشه پوشش داده شده اند که با رنگ سبز نشان داده شده اند. دو یال دیگر نیز با خوشه های اندازه 2 پوشش داده شده اند که با رنگ زرد نشان داده شده اند و سایر یال های با رنگ آبی، توسط این دو خوشه پوشش داده شده اند. بنابراین 6 خوشه (4 تا از اندازه 4 با رنگ قرمز و 2تا از اندازه 2 با رنگ زرد) ساختیم که همه یال ها را پوشش می دهند.

مجموعه S={2,4,8,9,11,15} نیز یک مجموعه پایدار از اندازه 6 است. یعنی به کران بالایش رسیده است.

۱۳۹۵/۰۳/۲۱
۱۶:۰۳
ماریا افشاری راد
۱۹۳
۰

ابتدا باید مدل رهاسازی شده مساله مسیریابی حل شود. برای اینکه به جواب هایی غیرصحیح برسیم و یا به جوابهایی صحیح برسیم که در آن حلقه وجود دارد، تنها بین صفر و یک بوودن متغیرهای xij را لحاظ کرده ایم، یعنی مساله زیر:

 

 

 

 

 

با حل مدل فوق جواب های زیر به دست می آیند:

همان‌طور که می‌بینیم جواب های حاصل عددصحیح نیستندو همچنین حلقه نیز وجود دارد:

بنابراین می توان با در نظر گرفتن S={2,3,6} از بروز این حلقه ها جلوگیری کرد (توجه کنید که نمی توانیم S={1,2,6} را در نظر بگیریم زیرا گره (1) نیز در آن وجود دارد. داریم:

محدودیت های بالا را به مدل اولیه اضافه می کنیم. جواب به شکل زیر به دست می آید:

که در آن  y1=y4=1,  y2=2.5, y3=y5=y6=1.5. حال مجددا محدودیت‌های مربوط به حلقه های S={2,4,6} و S={2,3,5} را به مدل اصلی اضافه می کنیم و این روند را تارسیدن به جواب بهینه صفر و یک ادامه می دهیم.

۱۳۹۵/۰۳/۲۱
۱۴:۴۳
ماریا افشاری راد
۱۷۹
۰

(اصلاحیه: در صورت سئوال ظرفیت عدد نوشته شده روی یال (3,6) باید 0.5 باشد)

برای نوشتن یک نامعادله معتبر از مساله جداسازی مساله فروشنده دوره‌گرد کمک می‌گیریم:

باید برای شبکه داده شده ابتدا به ازای هر انتخاب نقطه مبدا s و نقطه مقصد t یک بار مساله کمترین برش را حل کنیم و جواب آن را به دست آوریم، که به C(6,2)=15 حالت می توان این کار را کرد:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

به عنوان مثال در اولین حالت باید مساله کمترین برش به شکل زیر خواهد بود، گره خاکستری رنگ گره مبدا و گره زرد رنگ گره مقصد است. توجه داریم که بسیاری از این مسائل کمترین برش را می توان به صورت شهودی و از روی شکل به دست آورد. یعنی برشی را با کمترین ظرفیت طوری تعیین کنیم که گره مبدا و مقصد را از هم جدا کند. 

حال برای هر یک از حالت‌هایی که ظرفیت کمترین برش یافت شده از 2 کمتر باشد، می توان نامعادله معتبر نوشت. فرض کنید برش دوم را انتخاب می کنیم که به شکل زیر است:

بنابراین خواهیم داشت s={3} و t={1,2,4,5,6} و نامعادله مربوط به این مجموعه به شکل زیر است که به مدل رهاسازی شده اضافه خواهد شد:

x23+x36+x34>=2

 

۱۳۹۵/۰۳/۲۱
۱۳:۲۴
ماریا افشاری راد
۱۷۳
۰

ترکیبیات و کاربردها
۱۳۹۵/۰۳/۰۳
۱۴:۵۴
ماریا افشاری راد
۱۷۵
۰

تمامی حقوق این سامانه برای دانشگاه علم و فناوری مازندران محفوظ است
سامانه وبلاگ ویهان
محصول مشترک گروه شرکت های نرم افزاری ویهان و دانشگاه علم و فناوری مازندران
نسخه ۱.۰