در این پایان نامه مسائل برنامه ریزی چند پارامتری صحیح آمیخته خطی (MP-MILP) را بررسی می کنیم.
یک مساله برنامه ریزی ریاضی را مساله برنامه ریزی صحیح آمیخته گوییم هرگاه بعضی از متغیرها پیوسته و بعضی از آن ها مقید به گرفتن مقادیر صحیح باشند. در برنامه ریزی پارامتری، تغییرات مدل برنامه ریزی خطی تحت تاثیر پارامتری مانند θ ، مورد تجزیه و تحلیل قرار می گیرد.
الگوریتم اولیه شاخه و کران برای مسائل بهینه سازی ارائه می شود که می تواند به صورت یک درخت بیان شود. هدف ما در این پایان نامه، ارائه یک الگوریتم جدید برای حل مسائل برنامه ریزی چند پارامتری صحیح آمیخته خطی می باشد.
این الگوریتم برگرفته از روش شاخه و کران است که برای حل زیر مساله برنامه ریزی خطی چند پارامتری در گره ها استفاده می شود، و یک روش مقایسه ای مناسب برای به روز کردن درخت به کار می برد. همچنین در مسایل مورد نظر، ضرایب تابع هدف و بردار سمت راست محدودیت ها، مقادیری نامعین می باشند.
در آخر دو مثال برای شرح گام های الگوریتم پیشنهاد شده، ارائه می شود.
 

یک شکل از لم فارکاس را برای دستگاه های نامساوی دو سطحی ارائه می دهیم و از آن در بدست آوردن یک خصوصیت مهم جواب های سراسری رده ای از برنامه های دو سطحی چند جمله ای با برنامه های خطی در سطح پایین، استفاده می کنیم. لازم به ذکر است که توابع هدف برنامه های چند جمله ای سطح بالا، چند جمله ای قهری هستند. تابع چند جمله ای f یک چند جمله ای قهری نامیده می شود هرگاه  liminf ∥x∥ f(x) = +∞ . در نتیجه نشان می دهیم که یک دنباله از جوابهای بهین از برنامه های خطی نیمه معین به جواب بهین سراسری برنامه دوسطحی چند جمله ای، تحت شرایط مناسبی، همگرا می باشد. همچنین، مقدار بهین سراسری برنامه دو سطحی چند جمله را با استفاده از جعبه ابزار YALMIP بدست می آوریم.

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

  روش نقطه درونی اولیه و دوگان از کارآمدترین روشها از نقطه نظر محاسباتی است. دراین پایان نامه یک تابع کرنل جدید معرفی می کنیم که کارایی روش های بروز رسانی بزرگ نقطه درونی اولیه و دوگان را نتیجه می دهد. سپس نتیجه می گیریم که در بعضی وضعیت ها کران های تکرار از مرتبه ی(( O(m^((3m+1)/2m) n^((m+1)/2m) log(n/ϵ                  هستند و حداقل به خوبی بهترین کران های تکراری، از مرتبه ی(( O(√n logn log(n/ϵ)) ، است که تاکنون برای روش های بروز رسانی بزرگ نقطه درونی اولیه و دوگان شناخته شده اند. این نتیجه شکاف موجود بین رفتارعملی الگوریتم بروز رسانی بزرگ و نتایج اجرایی نظری را کاهش می دهد، که یک مسئله ی باز است. نتایج عددی، کارایی الگوریتم ارائه شده را نشان می دهد.

روش سیمپلکس را می توان برای حل مسئله برنامه ریزی قطعه به قطعه خطی (PLP) و مسئله برنامه ریزی کسری خطی (LFP) گسترش داد. در این پایان نامه ، توسعه ی بیشتر روش سیمپلکس را برای حل مسائل برنامه ریزی کسری قطعه به قطعه خطی(PLFP) بررسی می کنیم . مسئله برنامه ریزی خطی (LP)، PLP وLFP حالت های خاصی از PLFP هستند. الگوریتم سیمپلکس مطرح شده در این پایان نامه برای حل PLFP ، یک چارچوب واحد را برای حل چندین نوع مسئله بهینه سازی مهم تامین می کند .

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

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