مقاله کامل مقدمه ای بر برنامه ریزی اعداد صحیح و برنامه ریزی معادلات درجه 2

فصل 1
برنامه ریزی عدد صحیح
بسیاری از مسائل دنیای واقعی می توانستند به صورت برنامه های خطی مدل بندی شوند به جز تعدادی و یا تمام متغیرهایی که ناگزیرند که عدد صحیح باشند چنین مسائلی، مسائل برنامه ریزی عدد صحیح نامیده می شود.
کسی ممکن است فکر کند که این مسائل از مسائل برنامه ریزی خطی خیلی سخت تر نیستند. به عنوان مثال، ما در فصل 13 دیدیم که برای مسائل جریان شبکه با اطلاعات ریاضی، روش سیمپلکس به طور اتوماتیک جواب های صحیح تولید می کند. اما این مسئله فقط خوش شانسی بود، عموما، کسی نمی تواند انتظار داشته باشد که جوابهای صحیح به دست آورد. در حقیقت، همان طور که در این فصل می بینیم مسائل برنامه ریزی ریاضی عموما برای موشکافی شدن، نسبت به مسائل خطی، سخت تر هستند. در دنیای واقعی، مشکلات بسیار مهمی وجود دارند که می توانند به عنوان مسائل برنامه ریزی عدد صحیح ، فرمول بندی شوند. موضوع بسیار مهم است به طوری که چندین مونوگراف کاملا فدای این مساله شده اند در این فصل، ما فقط تعداد کمی از کاربردهای مطلوب را ارائه خواهیم داد که می توانند به عنوان مسائل برنامه ریزی عددصحیح مدل بندی شوند و سپس ما در مورد یک تکنیک برای حل مشکلات در این طبقه بحث خواهیم کرد به نام (روش) شاخه و کران.
1) مشکلات فهرست بندی (طرح ریزی):
مشکلات بسیاری وجود دارند که به عنوان مشکلات فهرست بندی طبقه بندی می شوند، فقط 2 مشکل مرتبط از این نوع را بررسی می کنیم: فهرست بندی تجهیزات و مشکلات فهرست بندی خدمه که این دو نوع در رویارویی با خطوط هوایی بزرگ هستند.
خطوط هوایی به صورت زیر چگونگی مسیر هواپیماهایشان را تعیین می کنند، اول، تعدادی از پروازهای خاص بر اساس تقاضای بازار مشخص می شوند. یک Leg بر اساس تعریف ،پروازی است که از جایی در یک زمان بلند می شوند و در جای دیگر فرود می آید (امیدواریم) مثلا، یک Leg می تواند پروازی باشد از نیویورک به شیکاگو در ساعت 7:30 صبح. یکی دیگر ممکن است
از شیکاگو به سان فرانسیسکو باشد در ساعت 1:00 عصر. نکته مهم این است که این Leg ها بر اساس تقاضای بازار مشخص می شوند و بنابراین از پیش مشخص نیست که از چه طریقی این Leg ها را با هم قرار دهیم که هواپیما در دسترس باشد تا همه آنها را پوشش دهد که این مسئله نشان می دهد، برای هر هواپیما آن خط هوایی باید مسیرهایی را با هم قرار دهد که هواپیما پرواز خواهد کرد. یک مسیر، به صورت تعریفی شامل توالی پروازهایی است که برای آن، مقصد یک Leg مبدا دیگری است (و البته مقصد نهایی باید مبدا اولین Leg باشد که یک حلقه ی بسته ایجاد می کند)
مشکلات فهرست بندی هواپیما به طور کل در دو مرحله، مغلوب می شوند، اول مسیرهای منطقی مشخص می شوند که با محدودیت های تنظیم و موقتی متعدد مواجه می شوند (شما نمی توانید جایی را قبل از رسیدن به آنجا ترک کنید، زمان نیز باید برای پایین آوردن و سوار شدن مسافرین ذخیره شود) این شکل تعیین مسیر به هیچ روی ناچیز نیست، اما این منظور اصلی ما در اینجا نمی باشد، بنابراین ما باید به سادگی فرض کنیم که مجموعه ای از مسیرهای منطقی تقریبا مشخص شده است با دادن مسیرهای بالقوه مرحله ی دوم انتخاب یک چیدمان است همراه با این خصوصیت که هر Leg دقیقا با یک مسیر پوشش می یابد اگر ترتیب مسیرهای بالقوه به اندازه ی کافی غنی باشد ما در اینجا انتظار خواهیم داشت که چندین راه حل علمی وجود داشته باشد، بنابراین مثل همیشه، هدف ما، انتخاب بهترین است، که در این مورد ما آن موردی را تعریف می کنیم که هزینه ی کل را به حداقل برساند. برای فرمول بندی این مشکل به عنوان یک برنامه ی ریاضی قرار دهید:

با این یادداشت و خلاصه شکل فهرست بندی تجهیزات می شود:

این مدل اغلب، مشکل تقسیم کردن نامیده می شود، از آنجا که دسته ای از Leg ها تقسیم می شوند و یا بخش بخش می گردند در میان مسیر های متعدد خدمه ی پرواز، لزوما همان هواپیما را حول یک مسیر دنبال نمی کنند. دلیل اصلی این است که اجباری که برای خدمه ی پرواز به کار می رود با آنهایی که برای هواپیما به کار می رود متفاوت است. (مثلا خدمه ی پرواز گاهگاهی نیاز به خواب دارند) بنابراین مسئله چیدمان، مسیرهای بالقوه ی مختلفی دارد. همچنین گاهی منطقی است که به خدمه اجازه می دهیم که به عنوان مسافرانی که در برخی Leg ها هستند، سوار شوند که این کار با این هدف است که آنها در وضعیت یک پرواز بعد قرار گیرند. با این تغییرات مشکل فهرست بندی خدمه:
این مدل اغلب به عنوان مشکل پوشش چیدمان نامیده می شود زیرا خدمه برای پوشش هر Leg تعیین می شوند.
2) مشکل فروشنده در حال سفر
فروشنده ای را مورد توجه قرار دهید که لازم است هر nشهر را مقالات کند که ما باید به عنوان 0…n-1 معین کنیم. هدف او این است که از شهر سکونت خودش 0 شروع کند و یک تور ایجاد کند که هر یک از شهرهای باقی مانده را یکبار و فقط یکبار دیدن کند و سپس به شهر خودش بازگردد. ما فرض می کنیم که فاصله بین هر دو شهر معلوم است. (فاصله لزوما نباید فاصله باشد، این می تواند زمان سفر و یا بهتر هزینه سفر باشد) و اینکه فروشنده می خواهد توری
ایجاد کند که فاصله ی کلی را به حداقل برساند این مشکل، مشکل فروشنده در حال سفر نامیده می شود. شکل 1-22 مثالی است که هفت شهر را نشان می دهد. مسلما، یک تور بالیست کردن شهرها به ترتیبی که آنها دیدن می شوند تعیین می شوند.اگر اجازه دهیم که Si به شهر iامین شهر ملاقات شده اشاره کند، سپس تور به سادگی می تواند به صورت زیر شرح داده شود.
شکل 22-1
تعداد کل تورهای ممکنه مساوی تعداد راه هایی است که هر کس می تواندn-1 شهر را پس و پیش کند یعنی
عوامل موثر حتی برای n کوچک، عظیم هستند. مثلا

بنابراین معین کردن از هر سوالی خارج است، هدف ما فرمول بندی کردن این مشکل به عنوان یک مسئله ریاضی است که می تواند سریعتر از مورد استفاده قرار دادن دیگر تعیین کننده ها حل شود منطقی به نظر می رسد که برای هر (j و i) یک متغییر تصمیم معرفی کنیم که مساوی یک خواهد بود اگر تور شهر j را فورا بعد از شهر i ملاقات کند در غیر این صورت مساوی 0 خواهد بود در این مورد این متغییرها تابع هدف به آسانی به این صورت نوشته می شود.

بخش گول زننده فرمول بندی قیدها است که ضمانت کند که xij غیر صفر دقیقا با یک تور جدی مطابقت می کند. بعضی از قیدها کاملا واضح هستند. مثلا پس از اینکه فروشنده شهر i را دیدن کرد او باید به یک و فقط یک شهر دیگر (بعدی) برود. ما می توانیم این قید را به صورت زیر بنویسیم
22-1
(ما آنها را قیدهای رفتن به می نامیم) همچنین وقتی که فروشنده یک شهر را ملاقات می کند او باید از یک و فقط یک شهر قبلی و نه بیشتر آمده باشد که می شود
22-2
(در مقایسه ما اینها را قیدهای آمدن از می نامیم. اگر قیدهای رفتن به و آمدن از کافی هستند که اطمینان دهند که متغییرهای تصمیم گیری یک تور را نشان می دهند، مشکل فروشنده ی در حال سفر برای حل شدن تقریبا آسان خواهد بود به دلیل اینکه این فقط یک مشکل تعیین کردن است که به طرز موثر به وسیله ی روش سیمپلکس حل خواهد شد اما متاسفانه این قیدها کافی نیستند زیرا آنها امکان تشکیل تورهای کوچکتر را رد نمی کنند. مثال در شکل 2-22 نشان داده می شود.
شکل 2-22
لازم است که ما قیدهای بیشتری را معرفی کنیم تا ارتباط پذیری گرافی را که تور نشان می دهد را ضمانت کنیم. برای دیدن چگونگی آن، یک تور خاص را مورد نظر قرار دهید:

اجازه دهید:

به عنوان تعداد توقف ها در طول توری که در آن شهرi ملاقات می شود تعریف گردد یعنی اینکه چه زمانی شهرi در طول تور ملاقات می شود. از این تعریف ما

را می بینیم به طور کل

به طوری که ما می توانیم در مورد tj بگونه ای فکر کنیم که معکوس Si است برای یک تور جدی

همچنین هر ti یک عدد صحیح بین 0 و n-1 است بنابراین tj قیدهای زیر را ایجاد می کند.

توجه کنید که با کسر کردن n در xij=0 ما به طرز موثر شرایط را همیشه حفظ کرده ایم این قیدها مختصرا به صورت زیر بیان می شوند.
3-22
حالا این قیدها بر اساس شرایطی که یک تور جدی دارد استنتاج می شود این نشان می دهد که آنها همچنین راه حلی را برای یک تور جدی تحمیل می کنند آنها تورهای فرعی را رد می کنند برای دیدن این مسئله خلاف این را فرض کنید که برای فرمول های 1-22 و 2-22 و 3-22 راه حلی وجود دارد که این ها حداقل 2 تور فرعی را در بر می گیرد تور کوچکی را مد نظر قرار دهید که شهر 0 را در بر ندارد اجازه دهید r تعداد leg ها در این تور فرعی را نشان دهد مسلما است. حالا فرمول 3-22 را برای تمام این تورهای کوچک جمع بزنید.
درسمت چپ، ما جمع tj ها را روی هر شهر ملاقات شده در تور کوچک داریم و در سمت راست ما همین جمع رابه اضافه rداریم با حذف کردن جمع ها از این دو طرف ما فرمول زیر را داریم.

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

توجه کنید که برای مسئله n شهر n2+2 متغیر در این فرمول وجود دارد.
3)هینه های ثابت:
جملات در یک تابع هدف اغلب هزینه های مرتبط به درآمد را در یک فعالیت نشان می دهد تا کنون ما همیشه فرض کرده ایم که هر کدام از این اصطلاحات یک تابع خطی مثل cx است به هر حال گاهی واقعی تر است که فرض کنیم یک هزینه ثابت برای درآمد در این فعالیت علاوه بر یک هزنیه متغییر خطی وجود دارد که یعنی چنین اصطلاحی ممکن است شکل زیر را داشته باشد

اگر فرض کنیم که در اندازه ی xیک کران بالا وجود دارد سپس این نتیجه می دهد که چنین تابعی می تواند به طور برابر با استفاده از تابع خطی مشخص در هزینه ی معرفی کردن یک متغییر بامقدار صحیح مدل بندی شود عملا فرض کنید که u یک کران بالا برای متغییر xاست بگذارید y به یک متغییر {0,1} مقدار اشاره کند که فقط و فقط وقتی x بزرگتر از صفر است برابر یک می باشد سپس:

همچنین شرایطی که در آن y مساوی یک است دقیقا زمانی که است می تواند از طریق معرفی قید زیر ضمانت شود

البته اگر تابع هدف چند جمله وابسته با هزینه های ثابت دارد سپس این راهکار باید برای هر یک از این جملات استفاده شود.
4) تابع های هدف غیر خطی
گاهی جملات تابع هدف اصلا خطی نیستند مثلا چنین جمله ای می تواند شبیه تابع نشان داده شده در شکل 3-22 باشد
در فصل 24 ما در مورد الگوریتم های موثر بحث خواهیم کرد که این الگوریتم ها می توانند در حضور تابع های هدف غیر خطی استفاده شوند حداقل زمانی که آنها خصوصیت های مناسب انتقالی دارند.در این بخش ما چگونگی تخمین زدن برنامه ریزی عدد صحیح برای فرمول بندی یک جمله ی غیر خطی عمومی در تابع هدف را نشان خواهیم داد. گام اول تخمین زدن تابع غیر خطی بوسیله یک تابع خطی پیوسته است گام دوم معرفی متغییرهای صحیح است که به ما اجازه می دهد که تابع خطی غیر پیوسته را که ارتباطهای خطی را نشان می دهد ارائه دهیم. برای دیدن چگونگی این مسئله ابتدا متغییر x را در جمع زیر تجزیه می کنیم.
در اینجا xi نشان می دهد چگونه مقدار بازه [0,x] شامل iامین جزء خطی از تابع خطی غیر پیوسته است (شکل 3-22 را ببینید)

فایل : 39 صفحه

فرمت : Word