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