برنامه نویسی تصادفی یک مدل بهینه سازی است که به بهینه سازی با عدم اطمینان می پردازد. به عنوان مثال ، شرکتی را تصور کنید که انرژی را برای خانوارها فراهم کند. این شرکت بر اساس میزان تقاضا ، مسئولیت تحویل انرژی به خانوارها را بر عهده دارد. به طور معمول ، این مشکل می تواند به عنوان یک برنامه خطی ساده تر (LP) با محدودیت های مبتنی بر تقاضای خانوارها حل شود. اگرچه این مناسب است ، تقاضای آینده خانوارها همیشه مشخص نیست و احتمالاً به عواملی مانند آب و هوا و زمان سال بستگی دارد. بنابراین ، عدم اطمینان وجود دارد و مدل اصلی LP ما کافی نخواهد بود.

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

فرمولاسیون ریاضی

برنامه های دو مرحله ای

در مشکلات متجاوز ، شما باید اکنون تصمیم بگیرید و همچنین هزینه های مورد انتظار تصمیم خود را به حداقل برسانید. در این مرحله دوم ، ما قادر به جلوگیری از محدودیت های مسئله غیرقابل تحمل هستیم. ما مشکل دو مرحله ای زیر را بررسی خواهیم کرد ، اما توجه به این نکته حائز اهمیت است که این مشکلات با مراحل زیادی می توانند چند بعدی شوند.

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

مقدار بهینه مشکل مرحله دوم کجاست

در معادلات بالاتر از اصطلاح تضمین می شود که امکان پذیر باشد (با این واقعیت مشاهده می شود که به y بستگی دارد ، متغیر تصمیم گیری مرحله دوم).

هنگامی که این مقادیر مورد انتظار محاسبه شد، مسئله دو مرحله ای را می توان به صورت یک برنامه خطی با شکل زیر بازنویسی کرد. این معادل قطعی است و شامل حل همه سناریوهای ممکن است. در نهایت، تنها یک سناریو انتخاب خواهد شد و کاملاً بر اساس هزینه های مرحله 1 و ارزش مورد انتظار در مرحله 2 است.

مشکل معادل قطعی را می توان با استفاده از حل کننده هایی مانند CPLEX یا GLPK حل کرد، با این حال توجه به این نکته مهم است که اگر تعداد سناریوها زیاد باشد، ممکن است زمان زیادی طول بکشد.

ویژگی های مسئله

روش های آماری

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

برای ملموس تر کردن این فرمول، یک مثال ساده را در نظر می گیریم. بگویید یک پسر تحویل روزنامه وجود دارد که باید هر روز تصمیم بگیرد که چند روزنامه از شرکت روزنامه بخرد تا بتواند آنها را به مصرف کنندگان دیگر بفروشد. او از تجربیات گذشته خود به این نتیجه رسیده است که 3 سناریو برای تقاضای روزنامه ها وجود دارد. یا 100 با احتمال 0. 5، 150 با احتمال 0. 2 یا 200 با احتمال 0. 3 خواهد بود. از این رو، او باید تصمیم بگیرد که چند روزنامه در مرحله 1 خریداری کند. این مثال به صورت گرافیکی در زیر نمایش داده شده است.

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

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

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

برنامه های کاربردی

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

مثال عددی

فرض کنید مشکل بهینه سازی زیر را داریم:

این یک مسئله بهینه سازی خطی ساده با مجموعه راه حل بهینه است.

Now assume that variables and are uncertain and that there are three different scenarios, for the values of and , each occurring with a probability of 1/3. This new problem involves uncertainty and is thus considered a stochastic problem. We must now partition and into , x_, x_ " /> and , x_, x_ " />به ترتیب. پس از تبدیل شدن به نسخه گسسته، مشکل مطابق شکل زیر فرمول بندی مجدد می شود و می توان یک بار دیگر با استفاده از برنامه ریزی خطی آن را حل کرد.

راه حل بهینه جدید است.

نتیجه

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