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

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

تعداد متغیرهای ورودی بستگی دارد.

این متغیرها می توانند مستقل از یکدیگر باشند یا بوسیله یک یا تعدادی محدودیت با ایکدیگر ارتباط داشته باشند.
با یک مثال موضوع را کمی روشنتر خواهیم نمود:
مثال 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 شرکت بین المللی ماینز بر روی سه مدن در شرق ویرجینیا مشغول کرا است.

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

همچنین قرارداد نیروی کارگری ایجاب می کند که به کارگران هر معدن هزینه روزانه کار را کامل پرداخت نماید و یا به میزان که معدن در طول روز باز است به آنها پرداخت شود.

تعیین کنید تعداد روزهایی که هر معدن می بایست کار کند در طی هفته جاری اگر شرکت بر آنست که بخواهد تعهداتش را با کمترین هزینه نهایی به انجام برساند؟

اگر به ترتیب تعداد روزهای معادن و و باشند که می بایست در هفته جاری کار کند.

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

بعلاوه، بدلیل اینکه هیچ معدنی بیش از 7 روز در هفته نمی تواند کار کند سه محدودیت پنهان دیگر بصورت نیز به مدل افزوده می گردد.

در نهایت و در مورد قراردادهای کاری، شرکت هیچ چیز برای کارهای ساعتی در روز کسب نمی کند؛ بنابراین و و می بایست عدد صحیح باشند.

بنابراین برنامه ریاضی ما بصورت: در حالیکه کلیه متغیرها غیر منفی و عدد صحیح باشند.

مدل 4 یک مدل عدد صحیح است که جواب آن در مسئله 7.4 تعیین شده است.

مسئله 1.6: یک سازنده در حال ورود به هفته آخر تولید 4 مدل مختلف از کنسولهای چوبی تلویزیون است که با اندیس های I و II و III و IV شناخته می شوند.

هر یک از این مدل ها می بایست مونتاژ شوند و سپس آرایش شوند.

مدل ها به ترتیب به 4 و 5 و 3 و 5 ساعت زمان برای مونتاژ و 2 و 1.5 و 3 و 3 ساعت زمان برای آرایش شوند.

سود مدل ها به ترتیب برابر 7 و 7 و 6 و 9 می باشد.

سازنده 30000 ساعت زمان در دسترس برای مونتاژ محصولات (با داشتن 750 مونتاژ کار که در هفته 60 سات کار می کنند) و برای آرایش نیز 20000 ساعت در دسترس می باشد (500 دکوراتور با 40 ساعت کار در هفته).

تولیدکننده از هر مدل چه تعدادی را در هفه آخر باید جهت رسیدن به ماکزیمم سود تولید کند؟

(فرض کنید کلیه واحدها فروخته می شوند.) هدف ماکزیمم کردن سود (به دلار) می باشد که با Z نشان داده می شوند.

متغیرهای برنامه عبارتند از: X1 : تعداد کنسول های نوع I که در هفته تولید می شود.

X2 : تعداد کنسول های نوع II که در هفته تولید می شود.

X3 : تعداد کنسول های نوع III که در هفته تولید می شود.

X4 : تعداد کنسول های نوع IV که در هفته تولید می شود.

تابع هدف بصورت زیر نمایش داده می شود: در این مسئله محدودیت های زمانی بر روی زمان نهایی مونتاژ و نیز زمان نهایی آرایش وجود دارد که به ترتیب عبارتند از: بدلیل اینکه مقادیر منفی نمی توانند تولید شوند چهار محدودیت نهان نیز بصورت زیر به مدل افزوده می گردند .

بعلاوه از آنجایی که اکنون هفته آخر تولید قرار داریم، مدل های تکمیل نشده در پایان هفته هیچ سودی را دربرنخواهند داشت.

برای اجتناب از چنین احتمالاتی، ما نیاز به مقدار صحیح برای هر متغیر داریم.

بنابراین مدل نهیای بصورت زیر خواهد بود: مدل فوق یک مدل عدد صحیح است و جواب آن در مسئله 6.4 تعیین خواهد گردید.

مثال 1-7: شکرت Aztec دو نوع از گازوئیل بدون سرب تولید می کند نوع معمولی و سوپر که در هر ایستگاه عرضه سوخت با قیمت به ترتیب هر گالن barrel به 12 دلار و 16 دلار به فروش می رسد.

هر دو نوع و می بایست شرایط زیر را برآورده کنند: پارامترهای تحت refined در موجودی بصورت زیر است: شرکت Aztee از هر نوع نفت به چه میزان می بایست به گازوئیل تبدیل کند تا اینکه بیشترین سود هفتگی را داشته باشد؟

میزان X1+X2 از نوع معمولی تولید خواهد شد و میزان 2(X1+X2) سود در بر خواهد داشت.

میزان X3+X4 از نوع سوپر تولید خواهد شد و میزان 4(X3+X4) سود در بر خواهد داشت.

میزان X1+X3 از domestic استفاده خواهد شد که هزینه 8(X1+X3) در بر خواهد داشت.

میزان X2+X4 از خارجی استفاده خواهد شد که هزینه 15(X2+X4) در بر خواهد داشت.

بنابراین سود نهایی به میزان هزینه کم شده عبارت خواهد بود از: محدودیت هایی تولیدی با در نظر گرفتن میزان تقاضا که می بایست به مدل آورده شود و نیز میزان موجودی در دسترس و می باشند که عبارتند از: (ماکزیمم تقاضا از نوع معمولی) (ماکزیمم تقاضا از نوع سوپر) (می نیمم معمولی مورد نیاز) (می نیمم سوپر مورد نیاز) در مورد در دسترسب بودن نیز داریم: و میزان مورد نیاز از این دسته نیز باید حداقل 88 واحد سرب باشد.

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

سوال 1.8 یک می خواهد جهت یک مسافرت برنامه ریزی کند.

این hiker 5 وسیله نیاز دارد که می بایست با خود حمل کند اما با توجه به محدودیت وزن او تنها می تواد بار را حمل نماید.

جهت انتخاب بهتر وسایل او یک جدول تهیه کرده است که در آن به هر یک از اقلام و با توجه به اهمیت آنها یک مقدار تخصیص داده است: این کوهنور کدام وسایل را می بایست با خود حمل کند تا اینکه ارزش را حداکثر نماید بدون آنکه از محدوده مجاز وزن قابل حمل تجاوز کرده باشد؟

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

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

در نهایت برنامه ریاضی این مسئله بصورت زیر خواهد بود: کلیه متغیرها عدد صحیح : مدل فوق یک برنامه عدد صحیح است که جواب آن را در مسائل 6.7 و 14.16 خواهیم دید.

1.9 یک سوپر مارکت شبانه روزی درصدد، کاهش تعداد صندوقدار مورد نیاز می باشد، جدول زیر در خصوص زمانبندی افراد لازم عبارتست از: دوره 1 می بایست الزاماً پس از دوره 6 شروع شود.

یک صندوقدار در هر روز 8 ساعت consecutive که در ابتدای یکی از 6 پریود آغاز می گردد.

اینکه مسئله اصلی در تعیین تعداد ساعات کاری کارمندان بگونه ای که الزامات با داشتن حداقل صندوقداران برآورده شود: مدل فوق یک مدل عدد صحیح است که جواب آن در مسئله 6.3 تعیین خواهد گردید.

15.

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

هر پوند از پنیر لوکس شامل 0.21b میوه مخلوط و 0.81b پنیر گرانقیمت، در حالیکه هر پوند از پنیر معمولی شامل 0.21b مخلوط میوه و 0.31b پنیر گرانقیمت می باشد و 0.51b پنیر فیلر می باشد که هم ارزانتر است و هم در plentiful supply با توجه به تجربه های گذشته، فروشگاه دریافته است که تقاضاهای هر نوع از پنیر که به قیمت آن وابسته است عبارتست از: در حالیکه D نشاندهنده تقاضا (به پوند) و P نشاندهنده هزینه به دلار در هر پوند و D1 و D2 به ترتیب نشانگر نوع لوکس و نوع معمولی می باشد.

صاحب فروشگاه چند پوند از هر نوع مجزا می بایست تولید کند و چه هزینه ای را برای هر نوع می بایست در نظر بگیرد.

اگر بخواهد که درآمد فروشگاه حداکثر شود و هیچ موجودی در پایان کریسمس باقی نماند؟

اگر را مقدار پنیر لوکس (به پوند) در نظر بگیریم و X2 را مقدار پنیر معمولی.

اگر کلیه محصولات فروخته شوند تابع هدف بصورت زیر خواهد بود: اکنون، اگر تولید فراتر از تقاضا نشود کلیه محصولات واقعاً فروخته خواهند شد و هیچ موجودی در پایان دوره باقی نخواهد ماند مثلا اگر و باشد.

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

سرانجام، هیچ یک از محصولات و یا قیمتشان نمی توانند منفی باشند بنابراین 4 محدودیت مخفی بصورت نیز به مدل آورده می شود و مدل نهایی به صورت زیر در می آید: مدل فوق یک مدل درجه دوم است با چهار متغیر و و و .

قضیه ساده میشود اگر به این نکته اشاره کنیم که برای هر مقدار مثبت و تابع هدف افزایش می یابد اگر یا افزایش یابند.

(یعنی اگر ما و یک مقدار ثابت در نظر بگیریم آنگاه افزایش یا کاهش تابع هدف به افزایش یا کاهش یا بستگی دارد.) بنابراین برای بشینیه کردن تابع هدف میزان و باید بگونه ای افزایش یابد که محدودیت 2 به حالت تساوی درآید (در حال حاضر این محدودیت یک نامساوی با علامت می باشد.) در حالیکه و می توانند از تابع هدف حذف شوند جایگزین کردند.

بنابراین مدل نهایی با دو متغیر و بصورت زیر در می آید: که بسادگی توسط روش ترسیمی حل می شود.

مثال ارائه راه حل ترسیمی از مدل درجه دو (مدل 6) از مسئله 10 .

1) برای حل مدل به روش گرافیکی، منطقی است که مدل را ساده سازی نماییم، داریم: تابع هدف فوق برابر با تابع هدف زیر است: (نکته manz=min(-z) آورده شود.

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

برابر هر مقدار محدودیت یک مقدار ellipse را در نقطه (95,125) تعیین می کند و در نقطه در شکل 1.3 توسط منحنی های خط چین نشان داده شده است.

کمترین مقدار جهت پیدا کردن مشاهده می گردد که کم کردن محدودیت 2 از 1 وجود دارد که داریم: (3) اینک با حل کردن معادله 2 و 3 می توان مقدار بهینه مسئله 10.

1 را پیدا نمود: 1.12 یک سازنده پلاستیک پس از بررسی دریافت 1200 جعبه در انبار کارخانه اول و 1000 جعبه دیگر در انبار کارخانه دوم دارد.

این سازنده از سه retailers سفارش دریافت می کند که در اندازه های 1000 ، 700 و 500 جعبه می باشند.

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

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

با انجام این عمل و با در نظر گرفتن محدودیت های نهان، که جهت جلوگیری از منفی شدن حمل و نیز مدل ریاضی این مسئله بصورت زیر در می آید: مدل فوق یک برنامه عدد صحیح است که راه حل آن در مسئله 7.3 و نیز 8.6 ارائه می گردد.

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

مربی در حال حاضر 6 شناگر جهت انتخاب را دارد که زمان انتظار هر یک در حالت ا نفرادی به صورت جدول زیر است: مربی چگونه می تواند شناگرها را انتخاب کند بگونه ای که کمترین زمان در مجموع بدست آید؟

تابع هدف عبارتست از می نیمم کردن زمان کل که با z نشان داده می شود.

با استفاده از متغیر می توان مجموع زمانهایی را که شناگر به رسته اختصاص می دهد را پیدا نمود، نهایتا که تابع هدف بصورت زیر بدست می آید: از آنجایی که هیچ شناگری نمی تواند به بیش از یک رسته تخصیص پیدا کند داریم: و از آنجایی که هر رسته حتما باید به یک شناگر تخصیص پیدا کند و هیچ رسته ای بدون شناگر نماند داریم: این 10 محدودیت، بهمراه تابع هدف و محدودیت های نهان جهت عدم منفی شدن متغیرها و نیز صحیح بودن میزان آنها می باشد.

تشکیل یک برنامه عدد صحیح را می دهند که راه حل آن در مسئله 9.4 آمده است.

1.14 یک شرکت بزرگ تولیدکننده روغن می خواهد یک پالایشگاه بسازد که قابلیت عرضه سوخت به سه بندرگاه را داشته باشد.

بندر B در 300 کیلومتری شرقی 400 کیلومتری شمالی بندر A قرار دارد در حالیکه بندر C در 400 کیلومتری غربی و 100 کیلومتری جنوبی بندر B قرار دارد.

تعیین کنید بهترین مکان قرار گرفتن پالایشگاه را بگونه ای که میزان لوله مورد نیاز جهت اتصال این پالایشگاهها به بنادر حداقل شود.

تابع هدف این مسئله درصدد حداقل کردن مجموع فاصله بین پالایشگاه و سه بندر اطراف آن است.

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

در این سیستم بندر B دارای مختصات (300 400) و بندر C در مختصات (700 300) قرار دارد.

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

بنابراین مدل یک مدل غیر خطی خواهد بود که جواب آن در مسئله 14.1 آورده خواهد شد.