برنامه ریزی ریاضی
فصل اول :
برنامه ریزی ریاضی :
مسائل بهینه سازی :
در مسائل بهینه سازی وسیله ای (ابزاری) که بدنبال بیشینه سازی یا کمینه سازی یک مقدار مشخص می باشد تابع هدف نامیده می شود که به .. تعداد متغیرهای ورودی بستگی دارد. این متغیرها می توانند مستقل از یکدیگر باشند یا بوسیله یک یا تعدادی محدودیت با ایکدیگر ارتباط داشته باشند.
با یک مثال موضوع را کمی روشنتر خواهیم نمود:
مثال 1.1 :
نمونه بالا یک مسئله بهینه سازی برای هدف z می باشد. متغیرهای ورودی شامل x1 و x2 می باشند که به دو طریق محدود شده اند. x1 می بایست شود به x2 بوسیله عدد 3. و همچنین x2 می بایست بزرگتر یا مساوی 2 باشد. هدف یافتن مقادیری از متغیرهای ورودی بگونه ای است که جمع توان متغیرها کمینه شوند، با در نظر گرفتن محدودیتهایی که بوسیله قیود در نظر گرفته می شوند. یک برنامه ریزی مسئله بهینه سازی است که در آن هدف و محدودیت ها بوسیله توابع ریاضی و ارتباطات ریاضی داده می شوند (مانند مثال 1.1) .
مدل ریاضی که در این کتاب مورد استفاده قرار می گیرد به فرم زیر می باشد
هر یک از m محدودیت هایی که 1.1 نشان داده شده اند شامل یکی از سه حالت ³ = £ می شوند. بدین سان برنامه ریاضی نامحدودیت زمانی تشکیل می شود که هر یک از توابع gi صفر در نظر گرفته شوند وهر یک از مقادیر ثابت bi نیز صفر در نظر گرفته شوند.
برنامه ریزی خطی :
یک برنامه ریاضی خطی است اگر تابع هدف f(x1,x2,….,xn) و نیز هر یک از محدودیتها gi(x1,x2,…..,xn) به ازای (I = 1 , …. ,m ) در ضابطه خودشان خطی باشند
بعنوان مثال :
در حالیکه C1 ها و ouj ها (I = 1 , 2, ….. , m . j: 1 , 2, … , n ) اعداد ثابت باشند.
پی حالت فوق هر حالت دیگری ازبرنامه ریزی ریاضی غیر خطی می باشد. بنابراین مثال 1.1 یک برنامه غیر خطی در زمینه تابع z می باشد.
برنامه های عدد صحیح:
یک برنامه عدد صحیح یک (حالت خاص) از برنامه خطی می باشد بهمراه یکسری محدودیتهای اضافی که متغیرهای ورودی را محدود به گرفتن مقادیر صحیح می نماید. در نوع برنامه ریزی ضرورتی ندارد که ضرائب تابع هدف ( z .1 ) و همچنین محدودیت ها و همچنین مقادیر سمت راست نیز اعداد صحیح باشند، اما اغلب اوقات در این نوع برنامه ریزی این ضرائب و مقادیر سمت راست بصورت عدد صحیح دیده می شوند.
برنامه درجه دو :
یک برنامه درجه دوم نوعی برنامه ریزی ریاضی است که هر یک از محدودیتهای آن خطی است مانند آنچه در (1.3 ) دیده ایم- اما تابع هدف آنها بفرم زیر می باشد:
در حالیکه Gi و di مقادیر ثابتی باشند.
فرموله کردن یک مسئله :
مسائل بهینه سازی در اکثر مواقع هستند. فرآیند یافتن جواب (شامل دو مرحله اساسی می گردد) : مدل سازی مسئله توسط یک برنامه ریاضی و سپس حل نمودن آن برنامه توسط تکنیکهایی که در فصول 2 الی 15 توضیح داده خواهند شد.
رویکرد زیر جهت تبدیل یک مسئله از حالت نوشتاری به برنامه ریاضی توصیه می گردد.
گام 2) مقادیری را که می بایست بهینه شوند را تعیین نمایید. آن را بصورت توابع ریاضی نشان می دهید. در این مرحله تلاش زیادی را برای تعریف متغیرهای ورودی انجام می گردد. (معمولا در این هنگام برنامه نویس توجه زیادی را جهت تعریف متغیرهای ورودی و آنچه که می خواهد کمینه یا بیشینه سازد می نماید.)
گام 2) تمامی ملزومات قید شده، محدودیتها و قیود را تعریف نمایید و آنها را به زبان ریاضی تبدیل نمایید. این ملزومات شامل محدودیتهای برنامه نیز می شوند.
گام سوم ) شرایط مخفی مدل را نیز تعیین نمایید. چنین شرایطی بصورت واضح در مسئله قید می گردند. لیکن از موقعیت فیزیکی (دنیای واقعی) مدل می شوند. و عموما شامل قیود ومحدودیتهای عدد صحیح و غیر منفی می باشند که بر متغیرهای ورودی اعمال می شوند.
در هر برنامه ریاضی، ما بدنبال یافتن یک جواب هستیم. اگر یک سری از جواب های بهینه وجود داشته باشند، آنگاه هر یک از آنها می توانند بعنوان جواب بهینه باشند. در این حالت هیچ تفاوتی بین عملکرد جواب های بهینه چندگانه وجود ندارد اگر هیچ عملکرد صریحی در محدودیتها قید نشده باشد.
دلگشائی: بجای عبارت فوق می توان از عبارت زیر استفاده کرد:
جواب های بهینه چند گانه :
در هنگام حل یک برنامه ریاضی گاهی اوقات با حالتی مواجه می شویم که دسته ای از جواب ها وجود دارندکه هر کدام می توانند بعنوان جواب بهینه در نظر گرفته شوند ضمن آنکه کلیه محدودیتهای مسئله را نیز ارضاء می کنند. این حالت در زمان برنامه ریزی ریاضی اصطلاحاً جواب بهینه چندگانه نامیده می شود. در اینجا برنامه ریز با آزادی عملکرد بیشتری مواجه است و می تواند بنا به نیاز هر یک جوابها را انتخاب نموده و مورد استفاده قرار دهد.
چند مسئله حل شده :
یک فروشگاه تهیه گوشت بصورت سنتی تکه های گوشت را از ترکیبی از گوشت خالص گاو و گوشت خوک تهیه می کند. قسمت گوشت گاو ترکیب شامل 80% گوشت گاو و 20% چربی می باشد و هر پوند آن در فروشگاه به قیمت 80 دلار به فروش می رسد و قسمت گوشت خوک شامل 68% گوشت و 32% چربی می باشد و هر پوند آن 60 دلار قیمت دارد. چقدر در هر نوع گوشت می بایست در ترکیب استفاده شود اگر بخواهیم مینیمم کنیم هزینه خرید گوشت را و نیز میزان چربی گوشت بیش از 25% نشود اینک به بررسی چند مثال جهت روشنتر شدن موضوع می پردازیم: