دانلود مقاله برنامه ریزی ریاضی

فصل اول :

برنامه ریزی ریاضی :

مسائل بهینه سازی :

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

با یک مثال موضوع را کمی روشنتر خواهیم نمود:

مثال 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% نشود اینک به بررسی چند مثال جهت روشنتر شدن موضوع می پردازیم:

مثال 1.1: یک فروشگاه گوشت بصورت سنتی ترکیبی از گوشت خالص گاو و گوشت خوک را به مشتریان عرضه می کند. در این فروشگاه گوشت گاو شامل 80% گوشت خالص و 20% چربی می باشد و هر پوند آن با قیمت 80 سنت بفروش می رسد. هر پوند گوشت خوک نیز که شامل 68% گوشت خالص و 32% چربی می شود نیز با قیمت 60 سنت بفروش می رسد. اینک فروشگاه می خواهد بداند که از هر نوع گوشت چه میزانی را در این ترکیب استفاده نمایید به منظور آنکه هزینه خرید را کمینه نماییم ضمن آنکه میزان چربی ترکیب در بیش از 25% نشود؟

حل :

هدف این مسئله عبارتست از : مینیمم کردن هزینه (به سنت)، که z نامیده می شود، در هر پوند از ترکیب گوشت. در حالیکه z بصورت 80 مرتبه گوشت گاو بهمراه 60 مرتبه گوشت خوک تعریف می شود.

میزان گوشت گاو استفاده شده در هر پوند ترکیب x1 =

میزان گوشت خوک استفاده شده در هر پوند ترکیب x2 =

با توجه به متغیرهای فوق هدف بصورت

              (1)                                                                                     

تعریف می شود.

با توجه به صورت مسئله در می یابیم که هر پوند از این ترکیب شامل o.2x1 چربی گوشت گاو و نیز 0.32x2 چربی گوشت خوک خواهد شد. ضمن آنکه ترکیب چربی در کل نباید از 0.25 بیشتر شود. بنابراین :                  (3)                                                        x1 + x2 = 1

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

سرانجام به محدودیتهایی می رسیم که سبب جلوگیری از منفی شدن متغیرها می شوند، زیرا فروشگاه نمی شتواند مقادیر منفی متغیرها را در ترکیب بکار برد، بنابراین دو محدودیت پنهان  نیز به مدل آورده می شوند.

اینک مدل شامل ترکیبات فوق با توجه به محدودیت های (1) و (2) و (3) بصورت زیر بدست می آید:

(4)

مدل فوق یک برنامه خطی است. بدلیل آنکه تنها از دو متغیر استفاده شده است می توان از راه حل گرافیکی (نموداری) جهت حل استفاده نمود.

1.2 حل گرافیکی مدل خطی (4) از مسئله 1. 1:

به شکل 1. 1 نگاه کنید. فضای قابل قبول – فضایی از نقاط  که در آنها کلیه محدودیت ها رعایت می شوند و شامل متغیرهای بزرگتر مساوی صفر نیز هست – در شکل با هاشور مشخص شده است.

به منظور پیدا کردن بهترین مقدار z که z نامیده می شود، کمینه کردن مقدار z در این مثال، مقادیر از z در نظر گرفته شد و بردارهای آن کشیده می شود (در شکل با خط چین مشخص شده)

با انتخاب و جایگذاری  و سپس z=75 و با توجه به تابع هدف، داریم:

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

جواب معادل این دو تساوی برابر با   است بنابراین داریم:

مثال 1.3)

یک تولید کننده مبلمان 6 واحد چوب و 28 ساعت زمان ازاد جهت تهیه یک سری دکور دارد. دو مدل از این رکوردها در گذشته فروش خوبی داشته اند، بنابراین تولید کننده قصد دارد تا کارگاه خود را محدود به ساخت این دو مدل نماید. وی پیش بینی می کند که هر مدل I نیازمند 2 واحد چوب و 7 ساعت زمان باشد در حالیکه مدل  نیازمند 1 واحد چوب و 8 ساعت نیروی انسانی است.

قیمت هر واحد مدل I برابر 120 دلار و هر واحد مدل II برابر 80 دلار می باشد. اینک اگر تولید کننده بخواهد بیشترین سود را داشته باشد از هر کدام از مدل های فوق چه میزان می باید تولید کند؟

در اینجا هدف ماکزیمم سازی سود (به دلار) است که با z مشخص می گردد:

Z= ( ´120 تعداد واحدهای دکور نوع I که باید ساخته شوند) + ( ´80 تعداد واحدهای نوع II که باید ساخته شوند)

اگر متغیرها را بصورت زیر تعریف نماییم داریم:

تعداد مدل های نوع یک که باید ساخته شوند = x1

تعداد مدل های نوع II که باید ساخته شوند  = x2

در این صورت تابع هدف بصورت

(1)

تولیدکننده محدودیتهایی در قبال تعداد چوب های موجود دارد، زیرا هر سال I نیازمند 2 واحد چوب است،  به عنوان متغیر آن در نظر گرفته می شود. به همین ترتیب  نیز به عنوان واحدهای چوبی که به مدل II تخصیص داده می شوند در نظر گرفته می شوند. لذا محدودیت مربوط به موجودی چوب داریم:

(2)

همچنین تولیدکننده با محدودیتهای زمانی نیز روبه روست. هر مدل I نیازمند 7 ساعت نیروی انسانی و واحد مدل II نیازمند 8 ساعت نیروی انسانی می باشد بنابراین:

(3)

کاملا واضح است که مقادیر متغیرها نمی توانند تولید شوند، بنابراین دو محدودیت  نیز به مدل اضافه می شوند. بعلاوه، از آنجایی که هیچ سودی به دکورهای نیمه ساخته تعلق نمی گیرد، محدودیت پنهان دیگری که باید در نظر گرفته شود بصورت صحیح بودن مقادیر و  در نظر گرفته می شود. با ترکیب این محدودیت ها (1) و (2) و (3) می توانیم یک برنامه ریاضی را بصورت زیر در نظر بگیریم:

با در نظر گرفتن غیر منفی و عدد صحیح بودن متغیرها

مدل فوق یک مدل عدد صحیح است. بدلیل اینکه در اینجا فقط دو متغیر وجود دارد، یک جواب گرافیکی می تواند در حل مدل کمک نماید.

1.4 ارائه یک راه حل گرافیکی از برنامه عدد صحیح مدل (4)

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

خط چین ها نشان دنده بردارهای تابع هدف  می باشند زمانیکه مقادیر 240 و 330 و 380 را بگیرد. مشاهده می شود که خط  که از نقطه  می گذرد بیشترین میزان دکورهای مطلوب را می دهند. بنابراین تولید کننده می بایست سه واحد از مدل I تولید کند و از مدل II نیز هیچ رکوردی را تولید نکند، به منظور اینکه میزان سود وی  باشد.

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

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

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

اما در نزدیکترین نقطه عدد صحیح قابل قبول یعنی نقطه (2,1) تابع هدف مقدار  را دریافت می کند که به میزان 40 دلار از برنامه خطی غیر عدد صحیح کمتر می شود.

فرآیند یافتن جواب برای مسئله 1.3 در مسئله 7.8 توضیح داده شده است.

1.5 شرکت بین المللی ماینز بر روی سه مدن در شرق ویرجینیا مشغول کرا است.

سنگ استخراجی از هر معدن پیش از بارگیری به دو گروه تقسیم می شود و ظرفیت روزانه هر یک از معادن و نیز هزینه های عملیاتی استخراج روزانه هر معدن مانند جدول زیر می باشد: