برنامه ریزی عدد صحیحدرس های رایگان

مدل سازی برنامه ریزی عدد صحیح

تهیه شده توسط گروه آموزشی بهینه یاب

مدل سازی برنامه ریزی عدد صحیح

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

دانلود بسته طلایی آموزش مدل سازی برنامه ریزی عدد صحیح

برای دانلود جزوه کامل آموزش کامل مدل سازی برنامه ریزی عدد صحیح بر روی دکمه زیر کلیک کنید.

دانلود جزوه آموزش مدل سازی برنامه ریزی عدد صحیح

برای دانلود ویدیو آموزش کامل مدل سازی برنامه ریزی عدد صحیح بر روی دکمه زیر کلیک کنید.

دانلود ویدیو آموزش مدل سازی برنامه ریزی عدد صحیح

درس 11: مدل سازی برنامه ریزی عدد صحیح

تهیه شده توسط گروه بهینه یاب

 

در برنامه ریزی خطی فرض بخش پذیری باعث می‌شود که در بسیاری از مسائل واقعی، چنانچه مقادیری غیر از عدد صحیح به متغیرهای صحیح داده شده که از نظر مفهومی ‌بی معنا باشد. به عنوان مثال، تعداد نفرات یا تعداد دستگاه‌ها که باید به مقادیر صحیح اختصاص یابد. در ادبیات تحقیق در عملیات بررسی موارد فوق را برنامه ریزی خطی عدد صحیح می‌نامند که به اختصار برنامه ریزی عدد صحیح نامیده می‌شود. اگر همه متغیرهای تصمیم یک مسئله برنامه ریزی خطی، عدد صحیح باشند، به آن برنامه ریزی عدد صحیح خالص ( Pure integer programming) گفته می‌شود. اگر فقط در مورد تعدادی از متغیرها فرض عدد صحیح بودن صادق باشد، به آن برنامه‌ریزی عدد صحیح مختلط (Mixed integer programming) گفته می‌شود. در ادامه یک نمونه مسئله برنامه‌ریزی صفر و یک ارایه می‌شود.

مثال: یک شرکت تولیدی تصمیم دارد به منظور توسعه فعالیت‌های خود، کارخانه جدیدی در یکی از دو شهر (الف) و (ب) ایجاد نماید. در شهری که برای این منظور انتخاب می‌شود می‌تواند انبار جدیدی هم احداث نمود ولی حداکثر یک انبار می‌تواند داشته باشد. در ستون 4 جدول زیر، ارزش خالص فعلی هر کدام از این انتخاب‌ها و در ستون آخر، سرمایه مورد نیاز آورده شده است. حداکثر بودجه برای این توسعه 24 میلیون دلار است و هدف مسئله، تعیین ترکیبی از انتخاب‌ها است که ارزش خالص را بیشینه نماید. مدل سازی برنامه ریزی عدد صحیح این مثال را انجام دهید.

حل:

برنامه ریزی عدد صحیح

متغیر تصمیم این مسئله به صورت زیر است:

برنامه ریزی عدد صحیح

به دلیل اینکه تصمیم‌های x1 و x2 از نوع ناسازگار هستند (شرکت فقط یک کارخانه می‌تواند بسازد)، لذا به محدودیت زیر نیاز است:

برنامه ریزی عدد صحیح
به طور مشابه برای تصمیم‌های x3 و x4 هم این ناسازگاری برقرار است(شرکت حداکثر یک انبار می‌تواند داشته باشد)

برنامه ریزی عدد صحیح

تصمیم‌های x3 و x4 تصمیم‌های وابسته به x1 و x2 هستند(ساختن انبار در یک شهر منوط به ساخت کارخانه است). این شرط با استفاده از محدودیت زیر بیان می‌شود:

برنامه ریزی عدد صحیح

برنامه ریزی عدد صحیح

در محدودیت اول، اگر x1 برابر با صفر باشد (یعنی در شهر 1 کارخانه ساخته شود)، آنگاه x2 خواهد بود. ولی اگر در شهر 1 کارخانه‌ای ساخته شود، می‌توان در این شهر انبار ساخته شود( x3=0 or 1 ).

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

برنامه ریزی عدد صحیح

فرموله کردن مسائل با استفاده از متغیرهای صفر و یک

محدودیت‌های این یا آن (either-or constraint)

حالتی را در نظر بگیرید که از بین دو محدودیت موجود می‌توان یکی را انتخاب کرد ولی لزومی ندارد که هر دو محدودیت برقرار باشد. فرض کنید که در مسئله‌ای، یکی از دو محدودیت زیر باید برقرار باشد:

برنامه ریزی عدد صحیح
با استفاده از عدد M بزرگ می‌توان مدل سازی برنامه ریزی عدد صحیح این محدودیت‌ها را به صورت زیر در آورد:

برنامه ریزی عدد صحیح

که y متغیر صفر و یک است. اگر y=1 باشد، لذا خواهیم داشت:

برنامه ریزی عدد صحیح

که در این صورت محدودیت دوم برقرار است و لزومی به برقراری محدودیت اول نیست.

اگر y=0 باشد، محدودیت‌ها به صورت زیر می‌شوند:

برنامه ریزی عدد صحیح

که در این صورت محدودیت اول برقرار است و لزومی ‌به برقراری محدودیت دوم نیست.

k محدودیت از بین N محدودیت باید برقرار باشد.

اکنون حالتی را در نظر بگیرید که محدودیت‌هایی به صورت زیر وجود دارد.

برنامه ریزی عدد صحیح

می‌خواهیم k محدودیت از N محدودیت بالا برقرار باشد. مدل سازی برنامه ریزی عدد صحیح این مسئله به صورت زیر است:

برنامه ریزی عدد صحیح

توابع با N مقدار محتمل

تابع (f(x1,x2,…,xnرا در نظر بگیرید که تا یکی از N مقدار d1,d2,…,dN را می‌تواند اخذ نماید. مدل سازی برنامه ریزی عدد صحیح معادل زیر می شود:

برنامه ریزی عدد صحیح

مسئله هزینه ثابت

عملیات تولید، معمولا مستلزم صرف هزینه ثابت (Fixed charge) با هزینه راه اندازی (set up cost) است. در این صورت کل هزینه تولید شامل هزینه متغیر (متناسب با حجم فعالیت) و هزینه ثابت ( برای راه اندازی آن) است. اگر xj معرف حجم فعالیت شماره j، و kj هزینه راه اندازی آن و cj معرف هزینه انجام هر واحد از این فعالیت باشد، هزینه کل برابر خواهد بود با:
برنامه ریزی عدد صحیح

اکنون مدل زیر را در نظر بگیرید:

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

برنامه ریزی عدد صحیح

در مدل فوق، اگر yj=0 باشد، آنگاه 0=xj و سپس fj=0 خواهد بود. اگر yj=1 باشد، آنگاه xj می‌تواند هر مقدار مثبتی اخذ نماید و خواهیم داشت:

برنامه ریزی عدد صحیح

برنامه ریزی انبار

در مدل‌سازی سیستم‌های توزیع، بایستی در باره ارزش بین هزینه‌های حمل و نقل و هزینه‌های انبارداری تصمیم‌گیری شود. فرض کنید به عنوان مثال مدیری بایستی تصمیم بگیرید از میان n انبار کدام ها را برای برآوردن تقاضای m مشتری استفاده کند. متغیر تصمیم چنین تصمیمی ‌به صورت زیر است:

برنامه ریزی عدد صحیح
xij: مقدار کالایی که از انبار i به مشتری j می رود.

هزینه‌های مربوطه عبارتند از:

fi : هزینه ثابت اجاره برای انبار i اگر باز باشد

cij : هزینه عملیاتی در انبار i به علاوه هزینه حمل از انبار i به مشتری j

در این مسئله دو محدودیت وجود دارد که عبارتند از:

1 – تقاضا dj برای هر مشتری بایستی از انبارها تامین شود.

2 – کالا از یک انبار تنها وقتی حمل می‌شود که انبار باز باشد.

مدل برنامه‌ریزی خطی عدد صحیح به صورت زیر می‌شود:

برنامه ریزی عدد صحیح

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

برنامه ریزی عدد صحیح

مدل سازی برنامه ریزی عدد صحیح این مثال را انجام دهید.

حل:

متغیرهای تصمیم‌گیری به صورت زیر تعریف می‌شود:

برنامه ریزی عدد صحیح
برنامه ریزی عدد صحیح

توجه: برای مطالعه ادامه این درس و دانلود سایر محصولات مربوط به این درس می توانید به موارد زیر مراجعه کنید.

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

دانلود بسته طلایی آموزش مدل سازی برنامه ریزی عدد صحیح

برای دانلود جزوه کامل آموزش مدل سازی برنامه ریزی عدد صحیح بر روی دکمه زیر کلیک کنید.

دانلود جزوه آموزش مدل سازی برنامه ریزی عدد صحیح

برای دانلود ویدیو آموزش مدل سازی برنامه ریزی عدد صحیح بر روی دکمه زیر کلیک کنید.

دانلود ویدیو آموزش مدل سازی برنامه ریزی عدد صحیح

 

دیدگاهتان را بنویسید

دکمه بازگشت به بالا