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

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

اسلاید 1: پائيز 1388مباني تحقيق در عملياتدكتر علي اكبر جلاليدانشكده برق دانشگاه علم و صنعت ايرانگروه كنترل - ترم پائيز 1388

اسلاید 2: پائيز 1388مباني تحقيق در عملياتهفته اول

اسلاید 3: پائيز 1388مباني تحقيق در عملياتInstructor: Dr. Ali A. JalaliOffice: Electronic Research CenterEmail: ajalali@webmail.iust.ac.irClass hour: Saturday and Monday 8:00 AM-9:30 AMOffice hour: Saturday and Monday 13:00 PM-14:00 PM, or any other time by appointmentWebsite: www.drjalali.irTextbook: Introduction to Operations Research by: Hillier/Lieberman 7th Edition with CD

اسلاید 4: پائيز 1388توضيح درس This course is an introduction to deterministic operations research models.Topics include linear programming, network flow problems, transportation and dynamic programming. We will learn how to model real-world decision-making problems by using operations research methods, how to solve the problems, and how to analyze and interpret the results. Basic knowledge on linear algebra and calculus is assumed. Microsoft Excel will be used in the course.

اسلاید 5: پائيز 1388Homework The due date of the homework should be enforced. Late homework is only accepted for emergency or medical reasons with official proofs.There are total 6 homework assignments and projects. All 6 of them will be counted into your final grade.You can discuss with your classmates when doing homework and projects, but you have to write it out in your own words. If necessary, you may be asked to explain in person what you have written in your homework and projects. Copied homework and projects will not be graded if detected.Both exams are closed book, final exam is comprehensive.Homework and class projects: 10%Midterm exam: 35%Final exam: 55%

اسلاید 6: پائيز 1388مقدمه اي بر تحقيق در عمليات (Hillier/Lieberman)38 سال است اين كتاب در دنيا تدريس مي شود!هفتمين چاپ آن (سال 2002) در دسترس كلاس است.چاپ هشتم كتاب هم در سال 2005 آماده است.اين كتاب داراي سايت به آدرس: www.mhhe.com/hillier است.

اسلاید 7: پائيز 1388TextBook – CD1متن كامل كتابآموزش همراه با تصوير متحرك

اسلاید 8: پائيز 1388TextBook – CD2

اسلاید 9: پائيز 1388http://mhhe.com/engcs/industrial/hillier/splash/

اسلاید 10: پائيز 1388آخرين نسخه كتاب سال 2010

اسلاید 11: پائيز 1388مطالب افزوده در نسخه كتاب سال 2010

اسلاید 12: پائيز 1388آنچه در اين كلاس به آنها خواهيم پرداخت.

اسلاید 13: پائيز 1388مقدمه اي بر تحقيق در عمليات (Hillier/Lieberman)

اسلاید 14: پائيز 1388متن الكترونيكي

اسلاید 15: پائيز 1388چاپ هشتم كتاب سال 2005

اسلاید 16: پائيز 1388

اسلاید 17: پائيز 1388

اسلاید 18: پائيز 1388

اسلاید 19: پائيز 1388تحقيق در عمليات چيست؟در جنگ جهاني دوم فرماندهي نظامي در انگلستان از گروهي ازدانشمندان دعوتي بعمل آورد تا در مسائل سوق الجيشي و تدابيرجنگي مربوط به دفاع زميني و هوايي اين کشور مطالعه نمايند. هدف آنها تعيين موثرترين روش استفاده از منابع محدود نظامي بود. از جمله مسائلي که مورد بررسي قرار گرفت مطالعه کارايي بمب افکنهاي نوع جديد و روش استفاده از راداري بود که به تازگي اختراع شده بود. تشکيل اين گروه علمي به عنوان اولين فعاليت رسمي تحقيق در عمليات به شمار آمده است.نام تحقيق در عمليات ظاهراْ بدين مناسبت داده شده بود که اين گروه به پژوهش در عمليات (نظامي) پرداخته بود. اين رشته جديد تصميم گيري از آغاز به عنوان رشته اي شناخته شده است که اطلاعات علمي را از طريق تلاش گروهي متخصص در نظامهاي مختلف به منظور تعيين بهترين نحوه استفاده از منابع محدود به کار مي گيرد.نتايج اميدبخشي که توسط گروههاي تحقيق در عمليات در بريتانيا به دست آمده بود فرماندهي نظامي ايالات متحده را بر آن داشت تا فعاليتهاي مشابهي را شروع نمايد. از فعاليتهاي موفقيت آميز گروههاي آمريکايي مي توان مطالعه مسائل پيچيده تدارکات نظامي، ابداع الگوهاي جديد پرواز، طرح مين گذاري دريا و استفاده موثر از وسائل الکترونيکي را نام برد.

اسلاید 20: پائيز 1388تحقيق در عمليات چيست؟پس از جنگ موفقيت گروههاي نظامي توجه مديران صنعتي را به خودجلب کرد. اينان در جستجوي راه حلهايي براي مسائل خود بودند که بر اثر واردشدن تخصص شغلي در تشکيلات تجاري روز به روز حادتر مي شدند. زيرا با وجود اين واقعيت که اصولا مشاغل تخصصي براي خدمت به هدف کلي يک سازمان به وجود مي آيند، اهداف فردي اين مشاغل ممکن است همواره با مقاصد آن سازمان سازگار نباشند. اين وضع منجر به مسائل تصميم گيري پيچيده اي شده است که نهايتا سازمان تجاري را مجبور نموده تا درصدد استفاده از موثرترين روشهاي تحقيق در عمليات برآيند.اگرچه پيشگامي تحقيق در عمليات به عنوان يک نظام جديد با بريتانياي کبير بود چيزي نگذشت که رهبري اين رشته به سرعت در حال رشد را ايالات متحده به دست گرفت. اولين تکنيک رياضي در اين رشته که مورد قبول همه قرار گرفت و روش سيمپلکس برنامه ريزي خطي ناميده شد در سال ۱۹۴۷ توسط رياضيدان آمريکايي جورج. ب. دانتسيک به وجود آمد. از آن به بعد با تلاشها و همکاريهاي علاقه مندان در موسسات علمي و صنعتي تکنيکها و کاربردهاي جديدي پديد آمده اند.

اسلاید 21: پائيز 1388تحقيق در عمليات يا پژوهش عملياتي تحقيق در عمليات يا پژوهش عملياتي(Operations Research, Operational Research) كه به طور مخفف OR ناميده مي‌شود شاخه‌اي بين‌رشته‌اياز رياضيات است كه از گرايش‌هايي مانند برنامه‌ريزي رياضي، آمار و طراحي الگوريتم‌ها استفاده مي‌كند تا در مسائل بهينه سازي نقطه بهينه را پيدا كند. يافتن نقطه بهينه بر اساس نوع مسله مفاهيم مختلف دارد و درتصميم سازيها استفاده مي‌شود. مسائل تحقيق در عمليات بر بيشينه سازي (ماكزيمم سازي) - مانند سود، سرعت خط توليد، توليد زراعي بيشتر، پهناي باند بيشتر و غيره- يا كمينه سازي (مي‌نيمم‌سازي) -مانند هزينه كمتر و كاهش ريسك و غيره با استفاده از يك يا چند قيد تمركز دارند. ايده اصلي تحقيق در عمليات يافتن بهترين پاسخ براي مسائل پيچيده‌اي است كه با زبان رياضي مدل‌سازي شده‌اند كه باعث بهبود يا بهينه‌سازي عملكرد يك سيستم مي‌شوند.عبارت تحقيق در عمليات گاهي علم مديريت يا management science نيز ناميده مي‌شود و معمولاً علم مديريت ارتباط نزديكي به مسائل مديريت تجارت دارد.

اسلاید 22: پائيز 1388تحقيق در عمليات يا پژوهش عملياتيتحقيق در عمليات يكي از زيرشاخه‌هاي رياضيات كاربردي است و جنبه‌هاي كاربردي آن در مهندسي صنايع نيز مورد توجه قرار مي‌گيرد. رياضيات كاربردي به متخصصان امكان مي‌دهد تا جنبه‌هاي نظري تحقيق در عمليات را بررسي كرده و آن‌را گسترش دهند و توانايي ايجادو توسعه تحقيق در عمليات را فراهم كنند. مهندسي صنايع با استفاده از جنبه‌هاي كاربردي تحقيق در عمليات سعيمي‌كند تا آن‌را در صنعت و تجارت به كار گيرد. ابزارهاي اصلي استفادهشده توسط تحقيق در عمليات مدل‌سازي رياضي، بهينه‌سازي، آمار، نظريه گراف، نظريه بازي‌ها، نظريه صف، آناليز تصميم‌گيري و شبيه‌سازي است. به دليل ماهيت محاسباتي اين شاخه، OR با علوم كامپيوتر پيوند دارد و تحليل‌گر تحقيق در عمليات معمولاً از نرم‌افزارها يا كدهاي اختصاصي استفاده مي‌كنند كه توسط خودشان يا همكارانشان ايجاد شده‌اند. نرم‌افزارهاي تجاري تحقيق در عمليات معمولاً با عنوان ابزارهاي حل مساله شناخته مي‌شوند و قابليت استفاده در نرم‌افزارها و كد‌هاي خودنوشته را دارا هستند. ويژگي بارز تحقيق در عمليات نگاه كلي آن به سيستمها و بهبود آن است و به جاي آنكه بر يك يا چند جزء سيستم تمركز كند تمام سيستم را مد نظر قرار مي‌دهد. تحليل‌گران تحقيق در عمليات معمولاً با مسائل جديدي مواجه مي‌شوند و بايد تشخيص دهند كه كدام‌يك از روش‌ها بيشتر با ساختار سيستم، اهداف بهبود و قيدهاي زماني و توان محاسباتي منطبق است. به همين دليل (و دلايل ديگر) نقش نيروي انساني در تحقيق در عمليات حياتي است. همانند ابزارهاي ديگر، تكنيك‌هاي OR به تنهايي قادر به حل مسائل نيستند.

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

اسلاید 24: پائيز 1388مراجع و تكليف دانشجوياندانشجويان با مراجعه به آدرس http://alihadi.blogfa.com/post-62.aspx مطالب ارائه شده را خواهند يافت. لطفآ در موقع خواندن متن وارد لينكهاي مربوطه شويد و اطلاعات خود را در مورد واژگاهاي مختلف مثل: بهره‌وري، كارايي و اثربخشي افزايش دهيد. ساير مراجع: http://fa.wikipedia.orghttp://kashef.ropage.comhttp://isen.ir/?p=37  

اسلاید 25: پائيز 1388برنامه ريزي خطيبرنامه ريزي خطي مي تواند در زمينه هاي مختلف مورد مطالعه و استفاده قرار گيرد. برنامه ريزي خطي به طور عمده در موقعيت هاي  تجاري و اقتصادي مورد استفاده بيشتري قرار مي گيرد اما براي بعضي از مسائل مهندسي نيز مي تواند به کار برده شود. بعضي از صنعت ها که برنامه ريزي خطي را مورد استفاده قرار مي دهند عبارتند از حمل و نقل، انرژي، مخابرات و کارخانه ها و … . همچنين در مدل کردن مسائلي از قبيل برنامه ريزي، مسيريابي، زمانبندي،  تخصيص و طراحي مفيد است.يک ارزيابي انجام شده از 500 شرکت بزرگ دنيا، نشان داد که 85% درصد آنها از برنامه ريزي خطي استفاده نموده اند.

اسلاید 26: پائيز 1388برنامه ريزي خطي در رياضيات، مسائل برنامه ريزي خطي شامل بهينه سازي تابع هدفي خطي است که بايستي يکسري محدوديت در فرم هاي تساوي هاي خطي و نامساوي برقرار شوند. به طور خيلي غيررسمي برنامه ريزي خطي استفاده از مدل رياضي خطي براي بدست آوردن بهترين خروجي (به طور مثال حداکثر سود، حداقل کار) با توجه به شرط هاي داده شده (براي مثال فقط 30 ساعت کار در هفته، کار غير قانوني انجام ندادن و غيره) است.و به طور رسمي تر در يک چند سقفي (مانند چندضلعي يا چندوجهي) که تابعي با مقدار حقيقي بر روي آن تعريف شده است، هدف يافتن نقطه اي در اين چند سقفي است که تابع هدف بيشترين يا کمترين مقدار را دارا باشد. اين نقاط ممکن است موجود نباشد، اما اگر وجود داشته باشند جست و جو در ميان رئوس چند ضلعي يافتن حداقل يکي از آن ها را تضمين مي کند.

اسلاید 27: پائيز 1388تاريخچه برنامه ريزي خطي مسئله حل يک سيستم نامساوي خطي به زمان فوريه بر مي گردد. برنامه ريزي خطي به عنوان يک مدل رياضي به وجود آمد و در زمان جنگ جهاني دوم و پس از آن معلوم شد که طرح ريزي و هم آهنگي پروژه هاي مختلف و استفاده موثر از منابع کمياب يک ضرورت  است. تيم  SCOOP (محاسبات علمي برنامه هاي بهينه) نيروي هوايي ايالات متحده کار جدي خود را در ژوئن 1947 شروع کرد. ماحصل آن، ابداع روش سيمپلکس توسط جورج.بي.دانتزيک در پايان تابستان 1947 بود.برنامه ريزي خطي به سرعت مورد توجه اقتصاد دانان، رياضي دانان، آماردانان، و موسسات دولتي قرار گرفت. در تابستان 1949 کنفرانسي در برنامه ريزي  و  براي برنامه ريزي مخارج و برگشت ها توسعه داده شد به طوري که با مسئوليت کميته Cowles براي تحقيق در اقتصاد برگزار شد. مقالات ارائه شده در اين کنفرانس اندکي بعد در سال 1951 به همت T.C.Koopmans در کتابي تحت عنوان تحليل فعاليت توليد و تخصيص جمع آوري شد. جان وان نيومن در همان سال تئوري دو گانگي را توسعه داد و  لئونيد خاشيان رياضي دان روسي ار تکنيک هاي ساده در اقتصاد قبل از دانتزيک استفاده کرد و جايزه نوبل را در سال 1975 در اقتصاد برد.

اسلاید 28: پائيز 1388تاريخچه برنامه ريزي خطيمثال اصلي آقاي دانتزيک يافتن بهترين تخصيص 70 نفر به 70 شغل بود. براي محاسبه احتياج به نمايش همه ي جايگشت ها براي انتخاب بهترين تخصيص بسيار وسيع و غير ممکن است. او مشاهده کرد با استفاده از الگوريتم سيمپلکس يافتن بهترين جواب فقط چند لحظه طول مي کشد و همچنين متوجه شد که جواب در گوشه چند ضلعي که به وسيله قيد هاي مسأله تشکيل مي شود وجود دارد. يك لينك خوب: http://www.mang.canterbury.ac.nz/people/jfraffen/faqs/LPfaq.htm

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

اسلاید 30: پائيز 1388كاربردهادر بسياري شرکت ها و موسسات دولتي با به کارگيري موفقيت آميز برنامه ريزي خطي، ميليون ها دلار صرفه جويي کرده اند. در زير به بيان چند مورد از اين موفقيت ها اشاره مي کنيم:با استفاده از برنامه ريزي خطي و برنامه ريزي عدد صحيح، روشي براي زمان بندي گشت افسران پليس در سان فرانسيسکو، توسط تيلور و هاکس لي (1989) طراحي گرديد. با اين روش سالانه 11 ميليون دلار صرفه جويي حاصل شد، زمان پاسخ گويي به درخواست ها نيز حدود 3 ميليون دلار در سال افزايش يافت.با استفاده از برنامه ريزي پويا، چائو و ديگران (1989) در حدود 79پست برق و بيش از 125 ميليون دلار در خريد موجودي و هزينه هاي کمبود صرفه جويي کردند.با استفاده از برنامه ريزي عدد صحيح، واسکو و ديگران (1989) در طراحي تأسيسات قالب شمش به فولاد بتلهم کمک کردند. برنامه ريزي عدد صحيح باعث شد که در هزينه هاي عملياتي سالانه، 8 ميليون دلار صرفه جويي گردد.با استفاده از مدل هاي شبکه پاول و ديگران (1988) يک مدل جهت تخصيص بار براي رانندگان کاميون در شرکت خطوط آمريکاي شمالي توسعه دادند. استفاده از اين مدل باعث ارائه خدمات بهتر به مشتريان و کاهش حدود 5/2 ميليارد دلار هزينه ساليانه شده است.سوليوان و سکرست از برنامه ريزي خطي استفاده کردند تا در مورد چگونگي فرايند کره گيري از دوغ، شير خام، کشک شيرين و خامه براي پنير خامه اي، پنير بسته بندي، خامه ترش و خامه کشک تصميم گيري شود.استفاده از مدل، سود کره گيري را سالانه 48000 دلار افزايش داده است.يک سواري يا کاميون قبل از جايگزيني چند سال مي تواند در يک کارخانه مورد استفاده قرار گيرد؟ نفت فيليپس از مدل هاي جايگزيني تجهيزات براي پاسخ به اين سؤال، استفاده کرد. اين مدل هاي جايگزيني تجهيزات، طبق برآورد انجام شده، باعث صرفه جويي سالانه 90000 دلار براي فيليپس شده اند. 

اسلاید 31: پائيز 1388برنامه ريزي خطيبرنامه ريزي خطي به صورت استاندارد مي توانند نمايش داده شوند:Maximize cTx Subject to Ax ≤ bx ≥ 0 X   بيانگر بردار متغير ها مي باشد و همچنين c و b  بردار ضرايب و A ماتريس ضرايب. عبارتي که بايد حداکثر يا حداقل شود تابع هدف نام دارد (در اين مورد  cTx ).عبارت b Ax ≤ شرايطي هستند که يک چند وجهي محدب را نمايش مي دهند که تابع هدف روي آن بايد بهينه شود.

اسلاید 32: پائيز 1388

اسلاید 33: پائيز 13880 1 2 3 4 5 6 2 4 6 840X1 +15X2 >=10014X1 + 35X2>=140X1 <=5 X2 <=5 X1, X2 >=03X1 + 9X2 = ?Optimal SolutionX1 = 5X2 = 2X1X2

اسلاید 34: پائيز 1388روش سيمپلكسhttp://math.uww.edu/~mcfarlat/s-prob.htmاينجا

اسلاید 35: پائيز 1388روش سيمپلكس

اسلاید 36: پائيز 1388روش سيمپلكساينجا

اسلاید 37: پائيز 1388روش سيمپلكساينجا

اسلاید 38: پائيز 1388روش سيمپلكس

اسلاید 39: پائيز 1388روش سيمپلكسhttp://math.uww.edu/~mcfarlat/s-prob.htm

اسلاید 40: پائيز 1388روش سيمپلكس