واژههاي كليدي:مسأله جایابی و تخصیص؛ برنامهریزی وابسته به شانس؛ برنامهریزی با محدودیت شانس، برنامهریزی ترکیبی، برنامهریزی دو سطحی؛ الگوریتم ژنتیک. فهرست مطالبفصل 1: مقدمه11-1- مقدمه21-2- تعريف و اهميت موضوع21-3- هدف تحقيق31-4- روش تحقيق31-5- معرفي فصلها4فصل 2: مروري بر منابع52-1- مقدمه62-2- تعاريف، اصول و مباني نظري62-2-1- مروري بر فضاي ترکيبي62-2-2- معيارهاي رتبهبندي82-2-3- شبيهسازي ترکيبي92-3- مروري بر ادبيات موضوع92-3-1- مدلهاي برنامهريزي ترکيبي92-3-1-1- مدل کلي102-3-1-2- مدل برنامهريزي ارزش انتظاري102-3-1-3- برنامهريزي با محدوديت شانس112-3-1-4- برنامهريزي وابسته به شانس122-3-2- مسأله جايابي -ميانه132-4- نتيجهگيري15فصل 3: روش تحقيق173-1- مقدمه183-2- علت انتخاب روش183-3- تشريح كامل روش تحقيق193-3-1- مقدمات193-3-2- طراحي مدل جديد جايابي -ميانه در محيط ترکيبي213-3-3- روش حل233-3-4- الگوريتم ژنتيک263-3-4-1- معرفي کروموزومها263-3-4-2- جمعيت اوليه273-3-4-3- تست شدني بودن283-3-4-4- تابع ارزيابي293-3-4-5- فرآيند انتخاب والد293-3-4-6- عمليات تقاطع293-3-4-7- عمليات جهش323-3-4-8- فرآيند تخصيص مجدد323-3-4-9- فرآيند انتخاب جمعيت333-3-4-10- معيار توقف33فصل 4: نتايج و تفسير آنها344-1- مقدمه354-2- محتوا354-2-1- اجراي الگوريتم بر روي دادههاي قطعي354-2-2- اجراي مدل در محيط احتمالي374-2-3- اجراي مدل در محيط ترکيبي404-2-4- خلاصه51فصل 5: جمعبندي و پيشنهادها525-1- مقدمه535-2- محتوا535-2-1- جمعبندي535-2-2- نوآوري555-2-3- پيشنهادها55مراجع57پيوستها60 فهرست اشکالشکل (3-1) نمونهای از کروموزوم الگوريتم ارائه شده27شکل (3-2) نحوه عملکرد عمليات تقاطع تک نقطه30شکل (3-3) نحوه عملکرد عمليات تقاطع دو نقطه30شکل (3-4) نحوه عملکرد عمليات تقاطع سه والد31شکل (3-5) نحوه عملکرد عمليات جهش دو نقطهای32شکل (4-1)نمودار تغييرات و نسبت به در مثال احتمالی ليو39شکل (4-2)مختصات نقاط تقاضا و تسهيلات در مدل ارائه شده و مدلهای معرفی شده در ليو39شکل (4-3)نمودار تغييرات و نسبت به در مثال ون و ايوامورا41شکل (4-4)مختصات نقاط تقاضا و تسهيلات در مدل ارائه شده و مدلهای معرفی شده در ون و ايوامورا42شکل (4-5)نمودار تغييرات و نسبت به در مثال ليو44شکل (4-6)مختصات نقاط تقاضا و تسهيلات در مدل ارائه شده و مدلهای معرفی شده در ليو45شکل (4-7)نمودار تغييرات و نسبت به در مثال ونگ و واتادا47شکل (4-8)نمودار تغييرات و نسبت به در مسأله 26 استان49شکل (4-9) جايابی انبار در مسأله 26 استان50 فهرست جداولجدول (2-1) مقالههای موجود در زمينه جايابی در محيطهای غيرقطعی15جدول (4-1) نتايج حاصل از الگوريتم ارائه شده و نرمافزار جايابی داسکين بر روی دادههای گالوائو36جدول (4-2) نتايج حاصل از الگوريتم ارائه شده و نرمافزار جايابی داسکين بر روی دادههای گالوائو با تعيين تقاضا36جدول (4-3)مختصات و تقاضای نقاط نقاضا در مسأله ليو37جدول (4-4)جواب مسأله ليو به ازاء های مختلف38جدول (4-5) مکان و تقاضای نقاط تقاضا در مسأله ون و ايوامورا40جدول (4-6)جواب ون و ايوامورا به ازاء های مختلف41جدول (4-7) مکان و تقاضای نقاط تقاضا در مسأله ليو42جدول (4-8)جواب مسأله ليو به ازاء های مختلف43جدول (4-9) مسافت بين نقاط تقاضا و نقاط کانديد استقرار در مسأله ونگ و واتادا45جدول (4-10) مکان و تقاضای نقاط تقاضا در مسأله ونگ و واتادا45جدول (4-11)جواب مسأله ونگ و واتادا به ازاء های مختلف46جدول (4-12) تخصيص تسهيلات به نقاط تقاضا در مسأله ونگ و واتادا47جدول (4-13)مراکز استانها و تقاضای تصادفی فازی آنها48جدول (4-14)جواب مسأله 26 استان به ازاء های مختلف49 فهرست علائم اختصاريبردار غیرقطعی ...............................پیمانه احتمال...............................پیمانه اعتبار ..............................پیمانه شانس ..............................تعداد تسهیلات ..............................تقاضا .......................................حداقل قابلیت اطمینان قابل قبول ............فاصله .....................................قابلیت اطمینان ............................. فصل 1: مقدمه 1-1- مقدمهدر این فصل، موضوع و مسأله اصلی پایاننامه معرفی شده و هدف تحقیقات آن در رابطه با اهمیت موضوع بیان میگردد. در ادامه، مختصراً روشهای تحقیق مورد استفاده و سیر مراحل تحقیق ذکر میگردد.1-2- تعريف و اهميت موضوعگاهی اوقات، تقاضای نقاط ظاهراً از یک توزیع مشخص پیروی میکنند اما با آن توزیع به طور مناسب انطباق ندارند. یکی از دلایل این امر میتواند این باشد که تقاضا همزمان دارای خاصیت احتمالی بودن و فازی بودن است. به این نوع متغیرها، متغیرهای ترکیبی[1] میگویند. متغیرهای ترکیبی دارای انواع مختلفی است که در این پایاننامه بر اساس آنچه در ادبیات موضوع وجود دارد، متغیرهای تصادفی فازی[2] و فازی تصادفی[3] را انتخاب شده است.مسأله جایابی –میانه[4] با تقاضای ترکیبی، در عین حالی که دارای مصادیق واقعی است، اما کمتر توسط پژوهشگران مورد توجه قرار گرفته است. در مسأله –میانه، باید تعداد تسهیل در محلهای کاندید استقرار طوری مکانیابی و به نقاط تقاضا تخصیص داده شوند که جابجایی کل حداقل شود.از طرفی در بین مدلهای مختلف برنامهریزی ترکیبی، دو نوع مدل به نامهای مدل برنامهریزی با محدودیت شانس[5] و دیگری مدل برنامهریزی وابسته به شانس[6] وجود دارد که در هر دوی این مدلها، جواب مسأله وابستگی شدیدی به نظر تصمیمگیر دارند. در مدل برنامهریزی با محدودیت شانس، یک حد[7] برای تابع هدف تعریف شده و هدف آنست که این حد بهینه شود به شرط اینکه تابع هدف با یک قابلیت اطمینان که از تصمیمگیر گرفته میشود، از این حد بهتر باشد. در مدل برنامهریزی وابسته به شانس، هدف اینست که احتمال اینکه تابع هدف از یک سطح مشخص بهتر باشد را بیشینه کند که این سطح از تصمیمگیر گرفته میشود. در هر دوی این موارد، امکان دارد به دلیل عدم آشنایی تصمیمگیر با محیط، سطحی از تابع هدف یا قابلیت اطمینان، مناسب انتخاب نشده و لذا این مدلها جوابهایی ایجاد کند که قابل قبول برای تصمیمگیر نیست.1-3- هدف تحقيقدر این تحقیق، بر آن سعی شده تا با ارائه مدلی جدید به همراه روش حل مناسب آن، بتوان دخالت تصمیمگیر در مدل را کاهش داده و جوابی واقعی و قابل قبول برای تصمیمگیر بدست آورد.1-4- روش تحقيقبا بررسی مدلهای مختلف در محیطهای غیرقطعی، این مهم آشکار شد که در این مدلها، تصمیمگیر دخالت زیادی در آن داشته که در صورت عدم آشنایی کافی تصمیمگیر با محیط، میتواند منجر به جوابهایی غیرقابل قبول برای تصمیمگیر شود. این موضوع میتواند باعث کاهش کارایی این مدلها در مسائل واقعی شود.برای رفع این مشکل، دو مدل برنامهریزی با محدودیت شانس و برنامهریزی وابسته به شانس را ترکیب کرده و یک مدل جدید دو سطحی ایجاد شده است. در این مدل، اطلاعاتی که از تصمیمگیر گرفته میشود، نیازی به آشنایی با محیط ندارد؛ چراکه پارامترهایی که در مدلهای برنامهریزی با محدودیت شانس و برنامهریزی وابسته به شانس توسط تصمیمگیر مشخص میشد، در این مدل توسط خود مدل به صورت بهینه تعیین میشوند.برای حل مدل ارائه شده، ابتدا با برداشتی از روش جستجوی شبکهای[8] در برنامهریزی دوسطحی، سطوح مدل با هم ترکیب و سپس با الگوریتم ژنتیک حل شده است.در مدل ارائه شده در این پایاننامه، مواردی که از تصمیمگیر گرفته میشود عبارتند از حداقل قابلیت اطمینان قابل قبول توسط تصمیمگیر و تعیین وزن سطوح تابع هدف در ترکیب آنها.پس از ارائه مدل و روش حل، مسأله جایابی –میانه با استفاده از این روش مدل و حل شده است. برای حل، از الگوریتم ژنتیک با استفاده از برنامهنویسی در محیط متلب[9] استفاده شده که آن نیز توضیح داده شده است.1-5- معرفی فصلهااین پایاننامه شامل پنج فصل است. در فصل اول مقدمهای بر پایاننامه و هدف آن و نگاهی اجمالی به روش تحقیق بود. در فصل دوم، مروری بر منابع ارائه میشود که شامل تعاریف (مروری بر فضای غیرقطعی) و مروری بر ادبیات موضوع است. در بخش مروری بر ادبیات موضوع، مدلهای برنامهریزی ترکیبی و مدل جایابی –میانه بررسی میگردد.
ارائه يک مدل جديد جايابی و تخصيص در محيط غيرقطعی word
واژههاي كليدي:مسأله جایابی و تخصیص؛ برنامهریزی وابسته به شانس؛ برنامهریزی با محدودیت شانس، برنامهریزی ترکیبی، برنامهریزی دو سطحی؛ الگوریتم ژنتیک. فهرست مطالبفصل 1: مقدمه11-1- مقدمه21-2- تعريف و اهميت موضوع21-3- هدف تحقيق31-4- روش تحقيق31-5- معرفي فصلها4فصل 2: مروري بر منابع52-1- مقدمه62-2- تعاريف، اصول و مباني نظري62-2-1- مروري بر فضاي ترکيبي62-2-2- معيارهاي رتبهبندي82-2-3- شبيهسازي ترکيبي92-3- مروري بر ادبيات موضوع92-3-1- مدلهاي برنامهريزي ترکيبي92-3-1-1- مدل کلي102-3-1-2- مدل برنامهريزي ارزش انتظاري102-3-1-3- برنامهريزي با محدوديت شانس112-3-1-4- برنامهريزي وابسته به شانس122-3-2- مسأله جايابي -ميانه132-4- نتيجهگيري15فصل 3: روش تحقيق173-1- مقدمه183-2- علت انتخاب روش183-3- تشريح كامل روش تحقيق193-3-1- مقدمات193-3-2- طراحي مدل جديد جايابي -ميانه در محيط ترکيبي213-3-3- روش حل233-3-4- الگوريتم ژنتيک263-3-4-1- معرفي کروموزومها263-3-4-2- جمعيت اوليه273-3-4-3- تست شدني بودن283-3-4-4- تابع ارزيابي293-3-4-5- فرآيند انتخاب والد293-3-4-6- عمليات تقاطع293-3-4-7- عمليات جهش323-3-4-8- فرآيند تخصيص مجدد323-3-4-9- فرآيند انتخاب جمعيت333-3-4-10- معيار توقف33فصل 4: نتايج و تفسير آنها344-1- مقدمه354-2- محتوا354-2-1- اجراي الگوريتم بر روي دادههاي قطعي354-2-2- اجراي مدل در محيط احتمالي374-2-3- اجراي مدل در محيط ترکيبي404-2-4- خلاصه51فصل 5: جمعبندي و پيشنهادها525-1- مقدمه535-2- محتوا535-2-1- جمعبندي535-2-2- نوآوري555-2-3- پيشنهادها55مراجع57پيوستها60 فهرست اشکالشکل (3-1) نمونهای از کروموزوم الگوريتم ارائه شده27شکل (3-2) نحوه عملکرد عمليات تقاطع تک نقطه30شکل (3-3) نحوه عملکرد عمليات تقاطع دو نقطه30شکل (3-4) نحوه عملکرد عمليات تقاطع سه والد31شکل (3-5) نحوه عملکرد عمليات جهش دو نقطهای32شکل (4-1)نمودار تغييرات و نسبت به در مثال احتمالی ليو39شکل (4-2)مختصات نقاط تقاضا و تسهيلات در مدل ارائه شده و مدلهای معرفی شده در ليو39شکل (4-3)نمودار تغييرات و نسبت به در مثال ون و ايوامورا41شکل (4-4)مختصات نقاط تقاضا و تسهيلات در مدل ارائه شده و مدلهای معرفی شده در ون و ايوامورا42شکل (4-5)نمودار تغييرات و نسبت به در مثال ليو44شکل (4-6)مختصات نقاط تقاضا و تسهيلات در مدل ارائه شده و مدلهای معرفی شده در ليو45شکل (4-7)نمودار تغييرات و نسبت به در مثال ونگ و واتادا47شکل (4-8)نمودار تغييرات و نسبت به در مسأله 26 استان49شکل (4-9) جايابی انبار در مسأله 26 استان50 فهرست جداولجدول (2-1) مقالههای موجود در زمينه جايابی در محيطهای غيرقطعی15جدول (4-1) نتايج حاصل از الگوريتم ارائه شده و نرمافزار جايابی داسکين بر روی دادههای گالوائو36جدول (4-2) نتايج حاصل از الگوريتم ارائه شده و نرمافزار جايابی داسکين بر روی دادههای گالوائو با تعيين تقاضا36جدول (4-3)مختصات و تقاضای نقاط نقاضا در مسأله ليو37جدول (4-4)جواب مسأله ليو به ازاء های مختلف38جدول (4-5) مکان و تقاضای نقاط تقاضا در مسأله ون و ايوامورا40جدول (4-6)جواب ون و ايوامورا به ازاء های مختلف41جدول (4-7) مکان و تقاضای نقاط تقاضا در مسأله ليو42جدول (4-8)جواب مسأله ليو به ازاء های مختلف43جدول (4-9) مسافت بين نقاط تقاضا و نقاط کانديد استقرار در مسأله ونگ و واتادا45جدول (4-10) مکان و تقاضای نقاط تقاضا در مسأله ونگ و واتادا45جدول (4-11)جواب مسأله ونگ و واتادا به ازاء های مختلف46جدول (4-12) تخصيص تسهيلات به نقاط تقاضا در مسأله ونگ و واتادا47جدول (4-13)مراکز استانها و تقاضای تصادفی فازی آنها48جدول (4-14)جواب مسأله 26 استان به ازاء های مختلف49 فهرست علائم اختصاريبردار غیرقطعی ...............................پیمانه احتمال...............................پیمانه اعتبار ..............................پیمانه شانس ..............................تعداد تسهیلات ..............................تقاضا .......................................حداقل قابلیت اطمینان قابل قبول ............فاصله .....................................قابلیت اطمینان ............................. فصل 1: مقدمه 1-1- مقدمهدر این فصل، موضوع و مسأله اصلی پایاننامه معرفی شده و هدف تحقیقات آن در رابطه با اهمیت موضوع بیان میگردد. در ادامه، مختصراً روشهای تحقیق مورد استفاده و سیر مراحل تحقیق ذکر میگردد.1-2- تعريف و اهميت موضوعگاهی اوقات، تقاضای نقاط ظاهراً از یک توزیع مشخص پیروی میکنند اما با آن توزیع به طور مناسب انطباق ندارند. یکی از دلایل این امر میتواند این باشد که تقاضا همزمان دارای خاصیت احتمالی بودن و فازی بودن است. به این نوع متغیرها، متغیرهای ترکیبی[1] میگویند. متغیرهای ترکیبی دارای انواع مختلفی است که در این پایاننامه بر اساس آنچه در ادبیات موضوع وجود دارد، متغیرهای تصادفی فازی[2] و فازی تصادفی[3] را انتخاب شده است.مسأله جایابی –میانه[4] با تقاضای ترکیبی، در عین حالی که دارای مصادیق واقعی است، اما کمتر توسط پژوهشگران مورد توجه قرار گرفته است. در مسأله –میانه، باید تعداد تسهیل در محلهای کاندید استقرار طوری مکانیابی و به نقاط تقاضا تخصیص داده شوند که جابجایی کل حداقل شود.از طرفی در بین مدلهای مختلف برنامهریزی ترکیبی، دو نوع مدل به نامهای مدل برنامهریزی با محدودیت شانس[5] و دیگری مدل برنامهریزی وابسته به شانس[6] وجود دارد که در هر دوی این مدلها، جواب مسأله وابستگی شدیدی به نظر تصمیمگیر دارند. در مدل برنامهریزی با محدودیت شانس، یک حد[7] برای تابع هدف تعریف شده و هدف آنست که این حد بهینه شود به شرط اینکه تابع هدف با یک قابلیت اطمینان که از تصمیمگیر گرفته میشود، از این حد بهتر باشد. در مدل برنامهریزی وابسته به شانس، هدف اینست که احتمال اینکه تابع هدف از یک سطح مشخص بهتر باشد را بیشینه کند که این سطح از تصمیمگیر گرفته میشود. در هر دوی این موارد، امکان دارد به دلیل عدم آشنایی تصمیمگیر با محیط، سطحی از تابع هدف یا قابلیت اطمینان، مناسب انتخاب نشده و لذا این مدلها جوابهایی ایجاد کند که قابل قبول برای تصمیمگیر نیست.1-3- هدف تحقيقدر این تحقیق، بر آن سعی شده تا با ارائه مدلی جدید به همراه روش حل مناسب آن، بتوان دخالت تصمیمگیر در مدل را کاهش داده و جوابی واقعی و قابل قبول برای تصمیمگیر بدست آورد.1-4- روش تحقيقبا بررسی مدلهای مختلف در محیطهای غیرقطعی، این مهم آشکار شد که در این مدلها، تصمیمگیر دخالت زیادی در آن داشته که در صورت عدم آشنایی کافی تصمیمگیر با محیط، میتواند منجر به جوابهایی غیرقابل قبول برای تصمیمگیر شود. این موضوع میتواند باعث کاهش کارایی این مدلها در مسائل واقعی شود.برای رفع این مشکل، دو مدل برنامهریزی با محدودیت شانس و برنامهریزی وابسته به شانس را ترکیب کرده و یک مدل جدید دو سطحی ایجاد شده است. در این مدل، اطلاعاتی که از تصمیمگیر گرفته میشود، نیازی به آشنایی با محیط ندارد؛ چراکه پارامترهایی که در مدلهای برنامهریزی با محدودیت شانس و برنامهریزی وابسته به شانس توسط تصمیمگیر مشخص میشد، در این مدل توسط خود مدل به صورت بهینه تعیین میشوند.برای حل مدل ارائه شده، ابتدا با برداشتی از روش جستجوی شبکهای[8] در برنامهریزی دوسطحی، سطوح مدل با هم ترکیب و سپس با الگوریتم ژنتیک حل شده است.در مدل ارائه شده در این پایاننامه، مواردی که از تصمیمگیر گرفته میشود عبارتند از حداقل قابلیت اطمینان قابل قبول توسط تصمیمگیر و تعیین وزن سطوح تابع هدف در ترکیب آنها.پس از ارائه مدل و روش حل، مسأله جایابی –میانه با استفاده از این روش مدل و حل شده است. برای حل، از الگوریتم ژنتیک با استفاده از برنامهنویسی در محیط متلب[9] استفاده شده که آن نیز توضیح داده شده است.1-5- معرفی فصلهااین پایاننامه شامل پنج فصل است. در فصل اول مقدمهای بر پایاننامه و هدف آن و نگاهی اجمالی به روش تحقیق بود. در فصل دوم، مروری بر منابع ارائه میشود که شامل تعاریف (مروری بر فضای غیرقطعی) و مروری بر ادبیات موضوع است. در بخش مروری بر ادبیات موضوع، مدلهای برنامهریزی ترکیبی و مدل جایابی –میانه بررسی میگردد.