پرش به محتویات

مقدمه و تعاریف

سیستم

System

هدف اکثر مسائل بهینه‌سازی مهندسی، کاهش ورودی (هزینه و یا زمان1) و افزایش خروجی (درآمد) است

\[ productivity = \frac{output}{input} \]

مثال فروشنده مسافر

یک فروشنده باید به مدت ۵ هفته بین دو شهر مشهد و تهران سفر کند. او شنبه از تهران به مشهد سفر کرده و سه شنبه بر‌می‌گردد. بهای بلیط رفت و برگشت ۴۰۰ دلار است اما اگر سفر در تعطیلات بیفتد ۲۰٪ تخفیف شامل بلیط‌ها می‌شود. بهای بلیط یک طرفه ۷۵٪ بلیط دوطرفه است. اقتصادی ترین برنامه سفر را پیدا کنید.

یافتن موارد زیر به حل مساله کمک می‌کند:

  • گزینه‌ها/متغیرهای تصمیم
  • قیود و محدودیت‌ها
  • هدف

Model Components

گزینه‌ها
گزینه شرح هزینه
۱ پنج تهران-مشهد-تهران \(5 \times 400 = 2000\)
۲ یک تهران-مشهد + چهار مشهد-تهران-مشهد + یک مشهد-تهران \(.75 \times 400 + 4 \times .8 \times 400 + .75 \times 400 = 1880\)
۳ یک تهران-مشهد-تهران (رفت اول و برگشت آخر) + چهار مشهد-تهران-مشهد \(5 \times .8 \times 400 = 1600\)

تمرین

  • چند گزینه نشدنی بیان کنید
  • یک گزینه شدنی بیان کنید و هزینه آن را حساب کنید

مثال حصارکشی

مالک یک خانه قصد دارد باغچه حیاط پشتی منزلش را حصارکشی کند. به دلیل سهولت باغبانی، شکل حصار باید مستطیل باشد. او ۱۰۰ متر حصار در انباری منزلش پیدا می‌کند. حداکثر مساحتی که می‌تواند با آن باغچه‌اش را حصارکشی کند چقدر است؟

گزینه‌ها
  • \(40\times10\)
  • \(30\times20\)
  • \(25\times25\)
  • ...

Fencing example

\[\begin{align} 2(w + h) = L \\ w \geq 0,h \geq 0 \end{align}\]
مدل ریاضی
\[\begin{align} Maximize\ z = wh \\ \\ subject\ to \\ 2(w + h) = L \\ \\ w, h \geq 0 \end{align}\]
حل مدل
\[\begin{align} w=\frac{L}{2} - h \\ z = wh = h(\frac{L}{2} - h)=\frac{Lh}{2} - h^2 \\ \frac{\partial{z}}{\partial{h}} = \frac{L}{2} - 2h = 0 \\ h = \frac{L}{4} = 25 \\ \end{align}\]

تمرین

  • سه جواب جدید پیدا کنید

تکنیک‌های مورد استفاده در تحقیق در عملیات

  • برنامه‌ریزی خطی: تابع هدف و قیود مساله رفتار خطی دارند
  • برنامه‌ریزی عدد صحیح: متغیرهای مساله از نوع عدد صحیح هستند
  • برنامه‌ریزی پویا: مساله به اجزای کوچکتر با رفتارهای مختلف شکسته می‌شود
  • برنامه‌ریزی شبکه: مساله بصورت یک شبکه مدل می‌شود
  • برنامه‌ریزی غیرخطی: توابع مدل رفتار غیرخطی دارند
  • روش‌های ابتکاری و فرا ابتکاری: از رفتار طبیعت برای حل مسائل پیچیده (NP-hard2) الگوبرداری می‌شود

مدل‌سازی

Modeling

مثال

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

Plastic container production process

متغیرهای مهم:

  • نرخ تولید: تابعی از ظرفیت تولید، استاندارد کیفیت، دسترسی به مواد
  • نرخ مصرف: تقاضای بازار، حمل و نقل

مراحل تحقیق در عملیات

Operation research steps

  • تعریف مساله
    • متغییرهای مستقل
    • تابع هدف
    • قیود و محدودیت‌ها
  • ساخت مدل
    • ساده‌سازی مدل
    • مفروضات
  • حل مدل
    • نوع مدل (خطی، غیر خطی، NP-hard)
    • شبیه‌سازی
  • اعتبارسنجی
    • تحلیل حساسیت
    • داده‌های جدید
    • شبیه‌سازی
  • پیاده‌سازی
    • قابل پیاده‌سازی
    • ترجمه نتایج به دستورالعمل قابل درک

  1. زمان به هزینه و بالعکس قابل تبدیل است. از این روش در ساده‌سازی توابع هدف چند وجهی استفاده می‌شود ↩

  2. Non-deterministic Polynomial-time hard ↩