دانلود تحقیق برنامه ریزی نیمه معین

Word 312 KB 7322 15
مشخص نشده مشخص نشده اقتصاد - حسابداری - مدیریت
قیمت قدیم:۷,۱۵۰ تومان
قیمت با تخفیف: ۵,۰۰۰ تومان
دانلود فایل
  • بخشی از محتوا
  • وضعیت فهرست و منابع
  • چکیده:

     

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

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

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

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

     

    در پایان گزارش به  بررسی مساله ای جالب و خواندنی در نظریه گراف اقدام شده است که شاید این مثال بار دیگر ارتباط تنگاتنگ شاخه های متفاوت ریاضی با یکدیگر را به اثبات برساند.

     

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

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

     

    در پایان از زحمات بی دریغ دکتر محمدرضا پیغامی که نصایح و رهنمود های ایشان ما را به داشتن شهودی هر چه بهتر از دنیای ریاضیات کاربردی سوق می دهد،کمال تشکر را داریم.

     

     

    1-مقدمه:

     

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

     

     

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

     

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

     

    LP : minimize   c.x

           

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

                   

                      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  

           

          s.t.    

     

                                sR.

     

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

     

     

    و نا مساوی بالا به خاطر  و حاصل می شود . از قضیه قوی دوآلیتی می دانیم که اگر مسئله اولیه LP دارای جواب شدنی متناهی باشد آنگاه مسئله LD نیز شدنی متناهی است و c.x=y.b و این نتیجه می دهد که فاصله دوگانی (دوآلیتی) وجود ندارد.(برابر صفر است)یعنی اگرX فضای شدنی مسئله LP و F فضای شدنی مسئلهLD  باشد آنگاه:

     

     X   F :

     

     

    3-     نکاتی پیرامون ماتریس ها و مخروط های نیمه معین:

     

    اگر X یک ماتریس  باشد زمانی گوئیم X یک ماتریس مثبت نیمه  معین(PSD ) است که رابطه زیر برقرار باشد:

    v Rn  :    vT X v

     

    اگر X یک ماتریس  باشد گوئیم X یک ماتریس مثبت  معین(PD ) است هر گاه :

    v Rn , v0 :    vT X v

     

    فرض کنید نشان دهنده مجموعه ماتریس های  متقارن  باشد و نشان دهنده مجموعه ماتریس های متقارن نیمه معین  و مجموعه ماتریس های   مثبت معین باشد.

     

    فرض کنیم X و Y ماتریس های متقارن دلخواهی باشند. می نویسیم ""   به این منظور که نشان دهیم X یک ماتریس  مثبت نیمه معین است و نماد "" بیانگر آن است که "" یعنی ماتریس  مثبت نیمه معین است. به طریق مشابه هر گاه X یک ماتریس متقارن و مثبت معین باشد آن را با "" نشان می دهیم .

     

    تذکر 1:  یک مخروط بسته محدب در R  است که بعد آن برابر  است.

     

    برای اثبات تذکر 1 فرض می کنیم XوW و فرض می کنیم ثابت دلخواه باشند در این صورت هر گاه Rnv و دلخواه باشد داریم :

     

    پس   و این نشان می دهد که  یک مخروط است.اثبات بسته بودن نیز ساده و سرراست است.

     

    خواص زیر را برای ماتریس های متقارن بیان می کنیم :

     

    اگر  باشد  که در آن ماتریس متعامد یکه (و  ماتریس قطری است.

     

    اگر  به شکل بیان شده در بالا باشد آنگاه ستون های  تشکیل  مجموعه ای از n بردار سرشت نمای متعامد X  می دهند،که مقادیر ویژه آنها درایه های متناظر روی ماتریس قطری D است.

     

     اگر و فقط اگر  به طوری که تمامی مقادیر سرشت نمای ماتریس X که عناصر ماتریس قطری D می باشند نا منفی باشند.

     

     اگر و فقط اگر  به طوری که تمامی مقادیر سرشت نمای ماتریس X که عناصر ماتریس قطری D می باشند مثبت باشند.

     

    اگر  و  آنگاه   برای تمامی،...،  .

     

    فرض کنیم ماتریس M بصورت زیر باشد :

     

    ,

     

    که  ،  یک بردار و  یک بردار  اسکالر است در این صورت  اگر و فقط اگر .

     

    4-     برنامه ریزی نیمه معین :

     

    فرض کنیم  . می توانیم به X بصورت یک ماتریس نگاه کنیم و یا به طور معادل بصورت آرایه ای از  مؤلفه بصورت  . همچنین می توانیم آنرا  بصورت یک شی (بردار ) در فضای  تصور کنیم . تمامی این 3 طریق متفاوت برای تصور X کارآمد خواهند بود.

     

    سوال: یک تابع خطی ار X به چه صورتی می تواند باشد؟ اگر  یک تابع خطی از X باشد آنگاه را می توانیم بصورت  نمایش می دهیم بطوری که :

     

     

    اگر X یک ماتریس متقارن باشد بدون از دست دادن کلیت می توانیم فرض کنیم C نیز یک ماتریس متقارن است . با  این نماد گذاری اکنون آماده هستیم تا یک برنامه ریزی نیمه معین را تعریف کنیم . یک برنامه ریزی نیمه معین (SDP) یک مسئله بهینه سازی به فرم :

     

    SDP : minimize    

     

          s.t.     = bi ,      i=1,…,m

                   

                      ,

     

    است.توجه کنید که در SDP ، متغیر ما ماتریس X می باشد ولی برای سهولت در تصور می توانیم X  را به صورت آرایه ای از  عدد یا به طور برداری در  در نظر بگیریم.

    تابع هدف ، تابع خطی  می باشد و X می بایست در m معادله خطی صدق کند که این معادلات به صورت  ،  هستند.

    متغیر X همچنین باید در مخروط (محدب بسته ) ماتریس های متقارن نیمه معین مثبت یعنی  قرار داشته باشد . توجه شود که داده های معلوم در مسئله SDP از یک ماتریس متقارن C ( که داده برای تابع هدف محسوب می شود ) و m عدد ماتریس متقارن  و m- بردار b(bبرداری است در  Rm) که معادلات مربوط به مؤلفه های آن تشکیل m معادله خطی را می دهند ، ساخته شده است.

     

    اجازه بدهید با مثالی ازSDP برای n=3 و m=2 آشنا شویم . ماتریس های و را به صورت زیر تعریف می کنیم :

     

    , ,و

     

    و  ،.پس متغیر X یک ماتریس   متقارن بصورت زیر خواهد بود :

     

    ,

     

    و برای مثال بالا خواهیم داشت :

     

     =

                

     

    در بالا از رابطه  ، ،  به دلیل متقارن بودن X استفاده کردیم . بنابراین مسئله SDP را می توان به صورت زیر نوشت:

     

    SDP : minimize          

     

          s.t.      

                

               

     

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

    همان طور که "  " در مسئله LP بیانگر این است که هر یک از n مؤلفه بردار x نا منفی اند نماد "  " در مسئله SDP بیانگر این است که هر یک از مقادیر ویژه ماتریس x نا منفی هستند.

     

    به سهولت می توانیم نشان دهیم که LP حالتی خاص از SDP است . برای دیدن یک نمونه از آن فرض کنیم  داده های مسئله LP را تشکیل می دهند ماتریس های  AوC را به صورت زیر تعریف می کنیم:

                                                                                                

    ,,.

     

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

     

              SDP : minimize         

     

          s.t.     = bi ,      i=1,…,m

                   

               , , ,  

               ,

    به همراه فرض :

     

    .

     

     

    البته در عمل هیچ گاه یک مسئله LP را در هنگام حل به SDP تبدیل نمی کنند . رابطه بالا به وضوح نشان می دهد که LPحالت خاصی از مسئله SDP می باشد.

     

    5-دوگان مسئله : SDP

     

    مسئله دوگان SDP بصورت زیر تعریف می شود :

     

     

     

    SDD :maximize      

    s.t.          

     

     

                   

    یک طریق مناسب برای تصور مسئله دوگان برنامه ریزی نیمه معین به صورت زیر است :

    فرض کنید ضرایب   ، داده شده باشند در این صورت هدف ماکسیمم کردن تابع خطی  است. قید های مسئله SDP بیان می کنند که ماتریس S که به صورت زیر تعریف شده است :

     

    باید مثبت نیمه معین باشد و به طور معادل میتوان نوشت:

     

     

    ما این طرز ساخت را با مثالی که قبلا ارائه کردیم ، نشان می دهیم .

     

    از مثال قبلی داریم :

     

    , و ,  ،

     

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

     

     

    SDD :maximize  

           

     

    s.t.      

     

     

     

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

     

    SDD :maximize  

           

     

    s.t.        

     

     

    اغلب کار کردن با مسئله دوگان SDD راحت تر از مسئلهSDPاست زیرا در مسئله دوگان متغیرها تنها از m ضریب  تشکیل شده اند.

     

    همانند مسئله برنامه ریزی خطی LP مختاریم تا به سهولت  از یک صورت مسئله SDP ( اولیه یا دوگان) به صورت دیگر برویم و بدون از دست دان کلیت می توانیم هر یک از آنها را به عنوان مسئله اولیه در نظر بگیریم.

     

    در زیر قضیه ضعیف دوآلیتی ( دوگانی) را برای مسئله SDP را بیان می کنیم :

     

    قضیه. 1. 5  : فرض کنیم X جواب شدنی برای مسئله SDP و  یک جواب شدنی برای مسئله SDD باشد در این صورت فاصله دوگانی برابر است با :

  • فهرست:

    1 مقدمه 4
    2 مروری کوتاه بر برنامه ریزی خطی 4
    3 نکاتی پیرامون ماتریس ها و مخروط های نیمه معین 6
    4 برنامه ریزی نیمه معین 8
    5 دوگان مسئله SDP 11
    6 خواص کلیدی مسائل برنامه ریزی خطی که به برنامه ریزی نیمه معین گسترش نمی یابند 16
    7 SDP در بهینه سازی تر کیبیاتی 16
    1 . 7 بیان SDP Relaxation از مسئله برش یالی ماکسیمم 16
    منابع و مراجع 19


    منبع:

     1-Robert M.Ferund : "Introduction to Semidefinite Programming(SDP)",Massachusetts Institute of Technology, March 2004

     

    2-L.Vadenberghe and S.Boyd: "Semidefinite programming ", AMS , March 2006

     

    3-Kenneth Hoffman and Ray Kunze :"Linear algebra (second edition)" ,Prentice-Hall,1971

     

فصل اول : برنامه ریزی ریاضی : مسائل بهینه سازی : در مسائل بهینه سازی وسیله ای (ابزاری) که بدنبال بیشینه سازی یا کمینه سازی یک مقدار مشخص می باشد تابع هدف نامیده می شود که به .. تعداد متغیرهای ورودی بستگی دارد. این متغیرها می توانند مستقل از یکدیگر باشند یا بوسیله یک یا تعدادی محدودیت با ایکدیگر ارتباط داشته باشند. با یک مثال موضوع را کمی روشنتر خواهیم نمود: مثال 1.1 : نمونه بالا ...

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

الف) تاريخچه ايده ي نمايش يک تابع برحسب مجموعه ي کاملي از توابع اولين بار توسط ژوزف فوريه، رياضيدان و فيزيکدان بين سال هاي ????-???? طي رساله اي در آکادمي علوم راجع به انتشار حرارت، براي نمايش توابع بکار گرفته شد. در واقع براي آنکه يک تابعf(x

هدف «ریاضیات علم نظم است و موضوع آن یافتن، توصیف و درک نظمی است که در وضعیت‌های ظاهرا پیچیده‌نهفته است و ابزارهای اصولی این علم ، مفاهیمی هستند که ما را قادر می‌سازند تا این نظم را توصیف کنیم» . دکتر دیبایی استاد ریاضی دانشگاه تربیت معلم تهران نیز در معرفی این علم می‌گوید: «علم ریاضی، قانونمند کردن تجربیات طبیعی است که در گیاهان و بقیه مخلوقات مشاهده می‌کنیم . علوم ریاضیات این ...

هدف ریاضیات علم نظم است و موضوع آن یافتن، توصیف و درک نظمی است که در وضعیت‌های ظاهرا پیچیده‌ نهفته است و ابزارهای اصولی این علم ، مفاهیمی هستند که ما را قادر می‌سازند تا این نظم را توصیف کنیم» . دکتر دیبایی استاد ریاضی دانشگاه تربیت معلم تهران نیز در معرفی این علم می‌گوید: «علم ریاضی، قانونمند کردن تجربیات طبیعی است که در گیاهان و بقیه مخلوقات مشاهده می‌کنیم . علوم ریاضیات این ...

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

علم آمار بر نظریهٔ آمار مبتنی است که شاخه‌ای از ریاضیات کاربردی است. در نظریهٔ آمار،اتفاقات تصادفی و عدم قطعیت توسط نظریهٔ احتمال، مدل‌بندی می‌شوند. در این علم، مطالعه و قضاوت معقول در بارهٔ موضوع‌های گوناگون، بر مبنای یک جمع انجام می‌شود و قضاوت در مورد یک فرد خاص، اصلاً مطرح نیست. از آن‌جا که هدف آمار این است که «بهترین» اطلاعات را از داده‌های موجود تولید کند، بعضی نویسندگان، ...

محيط زيست لطيف ترين قسمت زندگي در هر مکاني است. رشته محيط زيست در ايران زير شاخه مهندسي منابع طبيعي است و اساس آن بر حفاظت از طبيعت مي باشد؛ در ابتدا مباحث زيست محيطي در دل رشته هاي ديگر تدريس مي شد. اما با گسترش روزافزون و چشم گير اين علم در جها

- در نظام‌ها و سبک های ادبی همواره بر برتری هنرور، هنر پرور و صاحب هنر تکیه و تأیید شده است این برتری گاه از زبان حماسه سرای بزرگ ایران فردوسی نوعی گوهر فردی و در خود پادشاهان و پهلوانان و بزرگان همپایه با فرایندی ایزدی یاد شده و گاهی از زبان غزلسرایان همچون حافظ از هنر همانند گوهر نفس فضیلت و کمال سالک و رهرو یاد شده گاهی از دید منتقدانت اجتماعی همچون عبید، صائب و یا پروین ...

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

ثبت سفارش
تعداد
عنوان محصول