بخشی از پاورپوینت

اسلاید 1 :

  • هدف ما در این بحث شناسایی و مقایسه الگریتم های از لحاظ کارایی آنها و شناخت class های مختلف الگریتم ها از لحاظ پیچیدگی است.

تعبیر پیچیدگی

  • پیچیدگی(پیچیدگی زمانی)متناسب با کارایی یک الگریتم در حل یک مساله است.
  • پیچیدگی یک الگریتم متناسب با ماکزیمم تعداد عملگرهای محاسباتی مقدماتی(+-*/> <) مورد نیاز برای تبدیل ورودی یک الگریتم به خروجی آن با در نظر گرفتن همه حالتهای مساله است.
  • پیچیدگی یکی از مفاهیم مهم در حل مسایل است زیرا دانستن محدودیت های یک الگریتم در حل یک مساله در مدت زمان قابل قبول یکی از مسایل مهم در ارزیابی الگریتم ها است.
  • الگریتم هایی که کارایی بیشتری در حل مسایل بزرگ دارند مناسبترند.

اسلاید 2 :

  • اگر تعریف کنیم :

:sاندازه مساله – تعداد بیتهای داده های ورودی مساله

     به عنوان مثال در الگریتم های تئوری گراف اندازه مساله تابع تعداد راسها  یا تعداد یالها  یا هر دو است.

:C(s)تابع پیچیدگی

C(s)=4s+6     C(s)=2s2+7s+9 

  • رتبه یک الگریتم با تابع پیچیدگی C(s) رفتار C(s) را وقتیs به بینهایت میل میکند بیان میکند.

تعریف:

üالگریتم  cدارای رتبه چند جمله ای است اگر c یک تابع چند جمله ای باشد.

üالگریتم  cدارای رتبه نمایی است اگر c یک تابع نمایی باشد.

üالگریتم  cدارای رتبه فاکتوریل است اگر c یک تابع فاکتوریل باشد.

ü

ü

اسلاید 3 :

  • پیچیدگی در بد ترین حالت(worst-case complexity):

     بر حسب ماکزیمم تعداد محاسبات مورد نیاز برای حل مساله با در نظر گرفتن همه حالت های آن محاسبه میشود.

  • پیچیدگی انتظاری(expected time complexity):

     بر حسب میانگین تعداد محاسبات مورد نیاز برای حل مساله با در نظر گرفتن همه حالت های آن محاسبه میشود.

تعریف:

       اگر f و g به ترتیب توابع پیچیدگی 2 الگریتم a1 و a2 باشند، میگوییم f نسبت به g از رتبه بالاتری برخوردار نیست.

  • اگر C1=O(c2), C2=O(c1)باشد رتبه هر دو یکسان خواهد بود.

اسلاید 4 :

  • الگریتم های polynominalمعمولا الگریتم های خوب نامیده میشوند زیرا با افزایش ابعاد مساله ، تعداد محاسبات مورد نیاز برای حل مساله در مقایسه با سایر رتبه ها از رشد کمتری برخوردار است.

 

          به عبارت دیگر همواره مقداری برای  x0   وجود دارد که به ازای x>x0  الگریتم های polynominal  بهتر از الگریتم های نمایی و فاکتوریل عمل میکنند.

  • مسایلی که برای آن هیچ الگریتم چند جمله ای وجود ندارد مساله سخت(intractable) می نامیم.
  • Problem P-

  یک مساله Problem P-نامیده می شود اگر حداقل یک الگریتم برای حل آن وجود داشته باشد بگونه ای که کران بالای زمان حل مساله از یک رتبه Polynominal از اندازه ورودی های مساله باشد.

  • Problem NP-

یک مساله  را Problem NP-می نامیم اگر اثبات درستی آن (پاسخ مثبت به آن ) به صورت یک مساله P قابل تطبیق باشد.هر p  یک  NP نیز هست.

مثال : تعیین همیلتونی بودن یک گراف

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

  مسایل برنامه ریزی خطی

اسلاید 5 :

  • Problem NP Complete-

  مساله ای که الگریتم حل آن قابل انتقال و ترجمه  برای هر مساله NP  دیگری نیز باشدNP hard  نامیده میشود.

  اگر مساله ای  هم NP  و هم NP hard  باشد NP Complete نامیده میشود.

مثال:  تعیین همیلتونی بودن گراف و دیاگراف

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

اسلاید 6 :

  • مکان یابی از جمله مسایلی است که باید در مراحل اولیه طراحی تسهیلات مورد توجه قرار گیرد زیرا مکان مناسب برای یک واحد کارایی و اثربخشی را افزایش داده و منجر به بهبود در کل سیستم می گردد.
  • در این بحث ما مکان یابی را تحت عنوان کلی تری به نام مدیریت لجستیک بررسی می کنیم.
  • مدیریت لجستیک ، مدیریت فعالیت های توزیع و حمل و نقل(از تامین کننده تا مشتریان)در مقیاس بالا با هدف جابجایی مقدار مناسب از مواد مناسب در زمان مناسب و هزینه مناسب با استفاده از بهترین روشهاست.

اسلاید 7 :

  • طبقه بندی مسایل مدیریت لجستیک

  -مساله مکان یابی: تعیین مکان یک یا چند تسهیل در یک یا چند مکان بالقوه

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

  -مساله مکانیابی- تخصیص : علاوه بر مقدار کالایی که هر مشتری از هر تسهیل تامین می کند ،محل قرار گیری و ظرفیت آنها را هم مشخص می کند.

  • انواع مکانیابی تسهیلات:

     1-تک وسیله ای   

     2- چند وسیله ای

اسلاید 8 :

انواع مکانیابی تسهیلات:

  • مکانیابی گسسته: مکانهای ممکن برای یک واحد محدود باشد.(اکثر مسایل دنیای واقی )
  • مکانیابی پیوسته : مکانهای ممکن برای یک واحد نامحدود باشد.

فاکتورهای موثر در تصمیمات مربوط به مکانیابی

  • در عمل فاکتورهای مختلفی با اهمیت های متفاوت در تصمیمات مربوط به مکانیابی موثرند:

.1نزدیکی به منابع مواد اولیه

.2هزینه و میزان دسترسی به انرژی و تاسیسات ونیروی انسانی

.3قوانین دولتی در سطوح مختلفمرکزی ، محلی و منطقه ای

.4مالیات در سطوح مختلف

.5بیمه

.6هزینه های زمین و ساخت

.7نزدیکی به سیستم حمل ونقل

.8قوانین زیست محیطی

.9آب وهوا

.10نزدیکی به مشتریان

اسلاید 9 :

روشهای حل مسایل مکانیابی در فضای گسسته

  تحلیل های کیفی

روش رتبه بندی موقعیت ها

مراحل رتبه بندی:

.1لیست نمودن تمامی عوامل موثر در مکانیابی

.2وزن دهی به هر یک از عوامل

.3به هر مکان امتیازی بین 0 تا 100 داده شود

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

.5مجموع امتیاز وزنی هر مکان محاسبه و مقایسه شود.

  • در این روش ،تصمیم گیری براساس امتیاز وزنی است که این امتیازها به طور Subjective محاسبه شده اند. اما در تصمیم نهایی باید عوامل Objectiveمثل حمل ونقل و هزینه های عملیاتی نیز لحاظ شود.

اسلاید 10 :

تحلیل های کمی

  • مدل حمل و نقل

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

q  سوال: چگونه می توان با استفاده از مدل حمل ونقل برای انتخاب مکان بهینه بین چند محل استفاده نمود؟

در یک شبکه توزیع که m کارخانه و n مشتری داریم.بدلیل افزایش تقاضا نیاز به تاسیس یک واحد جدید داریم.کارخانه درp محل جدید می تواند قرار گیرد.برای تعیین مکان بهینه از بین این  pمکان می توان:

  Pمدل حمل ونقل تهیه کنیم که هر یک شاملn مشتری و  m+1کارخانه است .از بین آنها بهترین مدل با کمترین هزینه مشخص شده و مکان بهینه و نحوه توزیع بهینه کالاها مشخص می شود.

 

در متن اصلی پاورپوینت به هم ریختگی وجود ندارد. برای مطالعه بیشتر پاورپوینت آن را خریداری کنید