تحقیق در مورد برنامه ریزی نیمه معین (SDP)

اختصاصی از اس فایل تحقیق در مورد برنامه ریزی نیمه معین (SDP) دانلود با لینک مستقیم و پر سرعت .

لینک پرداخت و دانلود *پایین مطلب*

فرمت فایل:Word (قابل ویرایش و آماده پرینت)

تعداد صفحه18

فهرست مطالب

 

1 مقدمه........................................................................................................................ 4

2 مروری کوتاه بر برنامه ریزی خطی......................................................... 4

3 نکاتی پیرامون ماتریس ها و مخروط های نیمه معین.................... 6

4 برنامه ریزی نیمه معین................................................................................ 8

5 دوگان مسئله  SDP............................................................................................ 11

6 خواص کلیدی مسائل برنامه ریزی خطی که به برنامه ریزی نیمه معین گسترش نمی یابند .................................................................................................................. 16

7 SDP در بهینه سازی تر کیبیاتی.............................................................. 16

1 . 7   بیان SDP Relaxation  از مسئله برش یالی ماکسیمم..... 16

منابع و مراجع....................................................................................................... 19

1-مقدمه:

برنامه ریزی نیمه معین (SDP) جذاب ترین تحول برنامه ریزی ریاضی در دهه90میلادی محسوب می شود . SDP در موضوعات گوناگون از جمله بهینه سازی مقید محدب سنتی ، نظریه کنترل و بهینه سازی ترکیبیاتی کاربرد دارد. به دلیل آنکه SDP قابل حل به وسیله روش نقطه درونی می باشد ، بیشتر این موارد کاربرد ، در عمل نیز همانند تئوری کارا هستند.

2-مروری کوتاه بر برنامه ریزی خطی: 

مسئله  LPرا در حالت استاندارد در نظر بگیرید:

LP : minimize   c.x

1. t.   ai.x = bi ,  i=1,…,m

1. xR.

که در اینجا x یک بردار  nمتغیره است و نماد« c.x »حاکی از ضرب داخلی "" می باشد . همچنین  │ RnRn+  و  Rn+ فضای اقلیدسی نا منفی نامیده می شود.در حقیقت Rn+ یک مخروط بسته محدب است ، زمانی به یک مجموعه مانند K یک مخروط بسته محدب می گوییم که شرایط زیر را داشته باشد :

• اگر x و y بهK تعلق داشته باشد آنگاه نیز به K تعلق داشته باشد که در آن و  اسکالر های نا منفی هستند.

   R+  : 

• K یک مجموعه بسته باشد.

 این تعریف را می توانیم اینگونه بیان کنیم :

" منیمم کردن تابع خطی« c.x » بطوری که x درm معادله ai.x = bi (i=1,…,m) صدق کند و x متعلق به مخروط بسته محدب Rn+  باشد "

دوگان یک مسئله LP را به صورت زیر نشان می دهیم :

      LD : maximize  

1. t.  

1. sR.

اگر x یک جواب شدنی برای مسئله LP و(y,s) یک جواب شدنی برای مسئله   LD باشد آنگاه فاصله دوگانی به صورت زیر است: