Question

اگر $S$ یک مجموعه باز باشد,نشان دهید مساله زیر جواب بهینه ندارد.

$$Max\ cx$$ $$s.t.\ x \epsilon S$$

که در آن $c \neq 0$ است.

Answer 1

به برهان خلف فرض کنیم مساله ی فوق دارای جواب بهینه ای در نقطه ی $ x^{0} $ باشد.چون مساله ماکزیمم سازی است پس مقدار بهینه تابع هدف با حرکت در جهت بردار گرادیان(بردار $c$) بدست می آید.چون مجموعه ی $S$ باز است,پس هر نقطه ی آن درونی است و لذا از نقطه ی $x^0$ در راستای بردار $c$ می توانیم حرکت کنیم.طبق تعریف مجموعه ی باز ,$ \delta > 0 $ وجود دارد بطوریکه $N_ \delta (x^0) \subset S$(توجه دارید که $N_ \delta (x^0)$ یک همسایگی به مرکز $x^0$ و شعاع $ \delta $ است).پس با حرکت در جهت بردار گرادیان از نقطه ی $x^0$ به نقطه ی دیگری می رسیم که به ازای آن مقدار تابع هدف بیشتر از $Z(x^0)$ می شود که $Z$ مقدار تابع هدف می باشد.که این در تناقض با بهینه بودن $x^0$ است.

پس مساله فوق نمی تواند جواب بهینه داشته باشد.

Comments

پس ما برای این درس هم باید آنالیز بلد باشیم!

ممنون

---

مسایل از این قبیل,تحلیلی هستند.این ها تعاریف بسیار ساده و در عین حال مهم و پرکاربرد آنالیز هستند که برای حل خیلی از مسایل کابرد دارن.پس باید روشون تسلط داشته باشید.

Answer 2

پاسخ اولی بسیار زیبا و تئوری خیلی قشنگی بود.

برای پاسخی دیگر به این مسئله،می‌دانیم که جوابهای بهینه یک مسئله در نقاط راسی اتفاق می افتند و( طبق تعریف نقاط راسی ) نقاط راسی در مرزها قرار دارند، حال اگر فضای شدنی یک مسئله باز باشد آن‌گاه مرز خود را در بر نمی‌گیرد و در واقع نقاط راسی مجموعه را نیز در بر نگرفته و بنابراین نقاط بهینه و جواب بهینه ندارد.

Answer 3

پاسخ اول گنگه.اما پاسخ دوم کاملا صحیحه در واقع میشه ثابت کرد هر نقطه ی گوشه ای مرزیه