بهینه‌سازی (مدلهای ریاضی والگوریتم های فراابتکاری)

تحقيق درعمليات :

بعد از انقلاب صنعتي، جهان شاهد رشد حيرت انگيز سازمانها از نظر بزرگي و پيچيدگي بوده است . كارگاه هاي كوچك استادكاران و پيشه‌وران ادوار گذشته جاي خود را به شركتهاي غول پيكر عصر جديد داده‌اند . شكي نيست كه اين تحولات ثمرات مهمي به بار مي‌آورد . اما افزايش تخصصي ، دركنار فوايد بيشمارش ، مسائل جديد را نيز به همراه داشت كه بسياري از سازمانها هنوز هم با آن مواجهند ، از جمله اين مسائل ، تمايل هر بخش سازمان به رشدي مستقل درجهت تحقق اهداف خود ، برمبناي نظام ارزش مورد قبول خود ، و بدون هماهنگي همه جانبه با كل سازمان است .

با افزايش تخصص و درجه پيچيدگي در يك سازمان ، مسئله تخصيص منابع موجود بين فعاليتهاي بخشهاي مختلف آن ، به منظور دستيابي به بالاترين كارايي كل سازمان ، هر روز مشكل و مشكل تر مي‌شود . كاوشي كه درجهت رسيدن به راه بهتري براي حل اين نوع مسائل آغاز شده بود ، زمينه مناسب پيدايش تحقيق در عمليات را فراهم ساخت.

هر مساله نيازمند تصميم‌گيري را مي‌توان در انواع مسائل تحقيق در عمليات طبقه‌بندي كرد .امروزه پيچيدگي و هزينه بالاي عمليات و وسعت تشكيلات سازماني، لزوم شيوه‌هاي تصميم‌گيري مناسب و انجام تصميمات مستدل را براي مديران روشن مي‌سازد . تحقيق درعمليات با بسياري از مسائل محوري مربوط به تصميم‌گيري مديران در ارتباط است. تحقيق درعمليات مجموعه اي از تكنيكها وروشهاي استنتاج شده از رياضيات وديگر علوم است كه به طور قابل ملاحظه اي در بهبود تصميمات مديريتي مي‌تواند موثر واقع گردد . به عبارت ديگر تحقيق در عمليات “
 مجموعه اي از مدلها و تكنيكهاي كمي است كه از طريق روشهاي علمي، مديران را در امر تصميم‌گيري ياري مي‌دهد” مي‌باشد .  

تاريخچه تحقيق در عمليات :

اولين استفاده سازمان يافته از تحقيق در عمليات در طول جنگ جهاني دوم در سال 1941 در انگلستان آ‎غاز شد . دانشمندان انگليسي رادار را توسعه داده بودند اما ارتش با بهترين نحوه به كارگيري اين وسيله جديد آشنا نبود . بدين منظور گروهي از دانشمندان جمع شدند و با به كارگيري تكنيكهاي موثر رياضي داده‌هاي عملياتي را تحليل، و پيشنهاداتي را در اين مورد عرضه نمودند كه توانست توان دفاعي انگليسي را تقريبا ده برابر افزايش دهد. موفقيت اين گروه موجب استفاده از اين گونه گروه ها در بررسي مسائل مختلف نظامي شد از جمله در جهت حداكثر كردن احتمال موفقيت حمله‌ی هواپيماهاي انگليسي به زير دريايي هاي آلماني.

موفقيت گروه هاي پژوهش عملياتي موجب گسترش اين گروه ها گرديد . شايد يكي از معروفترين گروه ها ، گروهي بود كه تحت سرپرستي فيزيكداني به نام بلاكت(Blackett) تشكيل گرديد . اين گروه شامل سه فيزيولوژيست ، دو رياضيدان ، يك متخصص فيزيك نجومي و يك فيزيكدان عمومي بود . اين تيم توانست تأثير زيادي در پيروزي جنگهاي انگلستان بخصوص پيروزي جنگ دريايي آتلانتيك شمالي داشته باشد .

تأثيرات مثبت اين گروه ها باعث شد گروههاي مشابهي نیز در ارتش امريكا ايجاد شود. در اين دوره فعاليتهاي جان فون نيومن (John von Newman) و جرج دانتزيك (George Dantzig) سهم بسزايي در رشد زمينه هاي مختلف تحقيق در عمليات، ايفا نمود.

فضاي مناسب به وجود آمده در قبول پژوهش عملياتي و علم مديريت از سوي صنايع در دهه پنجاه موجب رشد سريع اين علم گرديد . انجمنهاي حرفه اي زيادي تشكيل شد كه مهمترين آنها انجمن پژوهش عملياتي انگلستان ( 1950 ) و انجمن پژوهش عملياتي امريكا ( 1952 ) انيستيتو علم مديريت امريكا ( 1952 ) ( كه اكنون 6500 عضو دارد ) و انيستيتو علم تصميم ( 1969 ) بودند .در حقيقت بيش از 40 كشور دنيا عضو فدراسيون بين المللي انجمنهاي تحقيق در عمليات يا International federation of operations Research societeis ( IFORS ) مي باشند .

ويژگيهاي اساسي تحقيق در عمليات :

این ويژگيها را به ترتيب زير مي‌توان بيان كرد .

1. برخورد سيستمي :

معني برخورد سيستمي اين است كه مدير كوششي آگاهانه را براي درك روابط متقابل بين بخشهاي مختلف سازمان و نفش آنها در پشتيباني از عملكرد كل سازمان به اجرا در مي آورد . به عبارت ديگر قبل از اجرا هر عمل بايستي اثرنهايي آن را بر سيستم سنجيد .

2. بكارگيري روش علمي :

روش علمي مستلزم فرآيندي سيستماتيك از مشاهده ، تعريف مسأله ، فرموله كردن فرضيه ، آزمون فرضيه و كسب نتايج مي‌باشد . مراحل يك تجسس علمي را مي‌توان در شكل زير نشان داد . 

3. استفاده از گروه متخصص در رشته هاي مختلف علوم :

مسائل بزرگ و پيچيده نيازمند گروهي متخصص است تا دامنه وسيعي از مهارتها را براي حل آن مورد استفاده قرار دهد بسياري از مسائل سازماني، براي مثال داراي جنبه هاي اقتصادي، اجتماعي، سياسي، مهندسي، طبيعي، زيستي و روانشناسي هستند. اگرچه غير ممكن است كه يك فرد در همه اين رشته ها متخصص شود، اما وجود يك گروه اين امكان را كه مساله از جنبه هاي مختلف و به وسيله متخصصين مختلف مورد بررسي و تجزيه و تحليل قرار گيرد را فراهم مي‌سازد، و به اين ترتيب جوابي بهتر براي مساله يافته مي‌شود.

4. استفاده از مدل

يك مدل، نمايش خاصي از يك واقعيت است . جنبه مشترك مدل ها ، عليرغم گوناگوني آنها ، ساده كردن “ واقعيت ” است. مدل عبارت است از يك تجريد انتخابي ( مبتني بر انتخاب ) ازواقعيت.

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

_ مدلهاي شمايلي (Iconic Models)

_ مدلهاي قياسي (Analogues Models)

_ مدلهاي سمبوليك يا رياضي (Symbolic  models)

از نظر احتمالي بودن نيز به دو گروه مدلهاي احتمالي و غيراحتمالي مي‌توان طبقه بندي نمود.

درجدول زير بعضي از انواع مدلهاي مورد استفاده در تحقيق و ميزان كاربرد آنها ارائه شده است.

فرآيند تحقيق در عمليات مستلزم كوشش در تصميم‌گيري و حل مساله است. اين فرآيند به وسيله نويسندگان مختلف به شيوه هاي متفاوت توضيح داده شده است. لي (Sing M , Lee)، گرين (Thad B . Green) ، نيوسام (Walte B . Newsom) به سه مرحله زير اشاره كرده اند.

1. فعاليتهاي قبل از مدل‌سازي

2. فعاليتهاي ضمن مدل‌سازي

3. فعاليتهاي بعد از مدل‌سازي

شكل زير نموداري از پارادايم هشت مرحله اي تحقيق در عمليات را نشان  مي‌دهد. بايستي توجه داشت كه اين نمودار به عنوان مجموعه اي دقيق ازمراحل متوالي نيست، به طوري كه هر مرحله به دنبال مراحل قبلي قرار گيرد. برعكس به ميزان زيادي مي‌تواند اين گامها در هر مساله خاصي جابجا گردد.

1. فعاليتهاي قبل از مدل سازي : قدم 1 و قدم 2

2. فعاليتهاي ضمن مدل سازي : قدم 3 ، قدم 4 ، قدم 5 ، قدم 6

3. فعاليتهاي بعد از مدل سازي : قدم 7 و قدم 8

 

برخی از کاربردهای برنامه‌ریزی ریاضی

•تخصیص بهینه نیروهای کاری به مشاغل

•مدیریت ترافیک و شبکه های ارتباطی

•زمان بندی(کارکنان، مراحل تولید،پوشش تلویزیونی و ..) 

•مدیریت بهینه جریان مواد در کارخانجات

•بودجه ریزی بهینه

•مدیریت بهینه حمل و نقل کالا

• زنجیره تامين

برنامه‌ريزي خطي و مثالی از آن :

برنامه‌ريزي خطي رده اي است از مدلهاي برنامه‌ريزي رياضي كه مربوط مي‌شود به مسئله تخصيص كارايي منابع محدود به فعاليتهاي معلوم، به منظور نيل به هدفي مطلوب ( مانند بيشينه ساختن سود يا كمينه ساختن زمان ) خصوصيت بارز مدلهاي برنامه‌ريزي خطي اين است كه در آنها توابع معرف هدف و قيود، خطي هستند.

مثالي از برنامه‌ريزي خطي :

يك شركت تعاوني مي خواهد در سال آينده به 3 شركت اقماري اش سي ميليون ريال اعتبار تخصيص دهد . به علت تعهداتش به كاركنان ثابت شركت و به دلايل ديگر ، شركت تعاوني يك حداقل تخصيصي براي هر يك از شركتها در نظر گرفته است . اين مبالغ به ترتيب 3 ميليون ، 5 ميليون و 8 ميليون دلار است. شركت اقماري 2 به خاطر ماهيت عملياتي اش بدون افزايش سرمايه اوليه اش نمي‌تواند بيش از 17 ميليون دلار به كار اندازد . شركت تعاوني در حال حاضر تمايلي به افزايش سرمايه ندارد. هر شركت با پولي كه دريافت مي‌كند  فرصت اجراي پروژه هاي مختلفي را دارد . نرخ بهره به ازاي هر پروژه تدوين شده است. به علاوه در بعضي از پروژه ها درجذب سرمايه سقفي وجود دارد . داده‌هاي هر پروژه در زير آمده است .

اين مسأله را بصورت يك مدل برنامه‌ريزي خطي فرموله كنيد .

روش حل مسأله :  مقدار پولي كه شركت i ام  براي پروژهj ام خود سرمايه‌گذاري مي‌كند ( برحسب ميليون دلار )

قيود حداقل تخصيص براي هر شركت :

قيود محدوديت سقف سرمايه‌گذاري هر شركت در پروژه هايش :

قيود مقدار كل سرمايه‌گذاري در تمام شعبه ها : 

جهت حل مدلهاي برنامه‌ريزي خطي جرج دانتزيك الگوي كاراي سيمپلكس را ارائه كرده است که مسأله‌ی فوق الذکر نیز از همین راه قابل حل می‌باشد. 

الگوریتم‌های فراابتکاری

جهت درک فلسفه الگوریتم های فراابتکاری در ابتدا باید با یک مشکل بزرگ که مربوط است به کاربرد برنامه ریزی ریاضی در عمل .

جهت تبیین بهتر در ابتدا باید با حل ترسیمی برنامه ریزی ریاضی اشنا شویم:

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

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

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

لذا به تعداد نقاط گوشه‌ای، محاسبه خواهیم داشت.  

اما یک مشکل بزرگ:

اگر تعداد ورودیهای مساله بسیار زیاد باشد که بالتبع آن تعداد محدودیتها نیز بسیار زیاد خواهد بود، چقدر محاسبه خواهیم داشت؟

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

البته مشکلات دیگری نیز وجود دارد:

اگر محدویت ها غیر خطی بوده و بصورت منحنی باشند؟

اگر فضای حل مساله بیشتر از 2 بعد باشد؟ (x,y,z) 

الگوریتم های فراابتکاری (شاخه‌ای از هوش مصنوعی) تنها راه حل کنونی برای حل این مشکلات می باشند.

 

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

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

مقایسه زمان حل یک مساله VRP در دو روش قطعی ریاضی و الگوریتم فرا ابتکاری (متاهیوریستیک) با افزایش حجم ورودیهای مساله(B&B معرف روش قطعی است و GA معرف روش ژنتیک)

برخی از انواع الگوریتم‌های فراابتکاری

 

گردآورنده مطالب و مولف:   محمد بزازی              مشاور علمی: دکتر توکلی مقدم                  ویراستاران:  ویدا محمدی، مرتضی محمدی