عنوان :

مقاله برنامه ریزی خطی

تعداد صفحات : ۴۹

نوع فایل : ورد و قابل ویرایش

چکیده

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

همچنین این روش دغدغه های ذهنی بسیاری از مدیران در مواردی چون میزان تولید، سود ، درآمد و غیره را نیز برطرف نموده است .

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

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

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

 واژه های کلیدی: برنامه ریزی خطی، تابع هدف، الگوریتم سیمپلکس، تحلیل حساسیت

فهرست مطالب

فصل اول: مقدمه و تعاریف
مقدمه    ۱
چکیده    ۲
تاریخچه    ۳
تعاریف    ۴
فصل دوم: کلیات
مثالی برای توضیح برنامه ریزی خطی    ۸
حل ترسیمی مسائل برنامه ریزی خطی با دو متغیر    ۱۴
یافتن ناحیه موجه     ۱۶
یافتن جواب بهینه     ۱۸
جواب های بهینه چندگانه      ۲۰
الگوریتم سیمپلکس    ۲۴
تحلیل حساسیت     ۲۷
تحلیل ترسیمی تأثیر حاصل از تغییر یک ضریب در تابع هدف     ۲۸
اهمیت تحلیل حساسیت    ۳۲
فصل سوم:کاربردها و معرفی نرم افزار
کاربرد      ۳۳
استفاده از نرم افزارهای لیندو و لینگو در مسائل برنامه ریزی خطی     ۳۵
تحقیقات جاری    ۳۷
فصل چهارم: نتیجه گیری
نتیجه گیری     ۳۸
واژه نامه     ۳۹
منابع    ۴۱

منابع:

۱-  وینستون،واین.ال . ” تحقیق در عملیات برنامه ریزی خطی ” ، مترجمین رضا زنجیرانی فراهانی،نسرین عسگری، محمد مدرس یزدی تهران : انتشارات ترمه ،چاپ اول، ۱۳۸۰ ؛ ۸۷۷ ص .

۲-    Bazaraa,M., and J.jarvis.Linear Programming and Network Flows.New York: Wiley,1990

مقدمه

      برنامه ریزی خطی(LP) ابزاری برای حل مسائل بهینه سازی است.

در سال ۱۹۴۷، جورج دانتزیگ[۱] یک روش کارا به نام الگوریتم سیمپلکس برای حل مسائل برنامه ریزی خطی (که LP نیز نامیده می شود)توسعه داد.با توسعه الگوریتم سیمپلکس،LP برای مسائل بهینه سازی گوناگونی مانند بانکداری،آموزش،فعالیت های جنگی،نفت و حمل و نقل کامیون ها استفاده شده است.در یک ارزیابی انجام شده از ۵۰۰ شرکت بزرگ دنیا،۸۵% آنها از برنامه ریزی خطی استفاده کرده اند.

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

تاریخچه

    مسئلهٔ حل مجموعه‌ای ازنامعادلات خطی از زمان فوربه مطرح بوده‌است. برنامه‌ریزی خطی[۲](LP) به عنوان یک مدل ریاضی در زمان جنگ جهانی دوم شکل گرفت تا خرج‌ها و بازگشت‌های مالی را طوری سامان بخشد که به کاهش هزینه‌های ارتش و افزایش خسارات دشمن بینجامد. این طرح تا سال۱۹۴۷  سری باقی ماند. پس از جنگ، بسیاری از صنایع به استفاده‌ از آن پرداختند. پایه‌گذاران این حوزه جورج دانتزیگ[۳] منتشرکنندهٔ روش سیمپلکس در سال۱۹۴۷ ،جان نیومن[۴] مطرح‌کننده نظریه دو گانگی در همان سال، و لئونید کانتروویچ[۵] ریاضیدان روس که از تکنیک‌های مشابهی پیش از دانتزینگ استفاده کرد ونوبل سال ۱۹۵۷ را برد هستند. نخستین بار در سال ۱۹۷۹ لئونید خاچیان[۶] نشان داد که مسئله‌ برنامه‌ریزی خطی در مرتبه زمانی چند جمله ای قابل حل است. اما پیشرفت اساسی‌تر زمانی حاصل شد که نراندرا کارمارکار[۷] یک روش نقطه داخلی جدید برای حل این مسائل معرفی کرد. مثال دانتزینگ برای منتصب کردن هفتاد نفر به هفتاد شغل متمایز کارآمدی برنامه‌ریزی خطی را به نمایش می‌گذارد. توان محاسباتی لازم برای آزمودن همهٔ جایگشت های  ممکن این مسئله بسیار بالاست. این تعداد از تعداد ذرات موجود در عالم بیشتر است، با این حال، پیدا کردن پاسخ بهینه با تبدیل مسئله به یک مسئله برنامه‌ریزی خطی و حل آن با روش سیمپلکس تنها لحظاتی طول می‌کشد.

تعاریف

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

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

    تابع هدف:در هر مسئله برنامه ریزی خطی تابعی که باید بیشینه یا کمینه شود را تابع هدف گوییم.

      نامعادلات خطی:به ازای هر تابع خطی )(  fو هر عدد b،نامعادلات ذیل خطی هستند:

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

ضریب تکنولوژی:ضریب متغیرهای تصمیم در محدودیت ها، ضریب تکنولوژی نام دارد چون اغلب منعکس کننده تکنولوژی مورد استفاده برای تولید محصولات مختلف هستند.

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

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

سمت راست محدودیت:عدد سمت راست هرمحدودیت سمت راست محدودیت (rhs)[8] نامیده می شود معمولا rhs مربوط به یک محدودیت،میزان منابع در دسترس را نشان می دهد.

     آزاد در علامت:اگر یک متغیر  بتواند یک مقدار مثبت یا منفی یا صفر فرض شود می گوییم متغیر آزاد در علامت که به اختصار به آن urs [9] می گوییم.

  جواب:کلیه مقادیری که متغیر های تصمیم اختیار می کند به تنهایی یک جواب محسوب می شود.

  جواب موجه : جوابی است که در تمام محدودیت ها صدق می کند.

 جواب غیر موجه :کلیه مقادیری که خارج از منطقه موجه قرار دارند.

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

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

 جواب های بهینه مدل برنامه ریزی خطی ، ممکن است انواع مختلفی داشته باشند که به شرح ذیل بیان می گردد….

الف : جواب بهینه چند گانه داشته باشد:

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

ب : فاقد جواب بهینه باشد :

   در این حالت مدل،جواب بهینه ندارد و این در واقعیت امکان پذیر نیست ، در چنین صورتی باید مجددا مسئله را فرموله و حل نماییم.

ج: ناحیه جواب ، بی کران باشد:

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

   منطقه موجه :ناحیه ای از جواب های موجه است که در همه محدودیت ها صادق است.

   تابع خطی:تابع بر حسب  یک تابع خطی است اگر و فقط اگر برای بعضی مجموعه های ثابت  رابطه ذیل برقرار باشد:

 برنامه‌ریزی خطی:

یا همان بهینه‌سازی خطی، روشی در ریاضیات است که به پیدا کردن مقدار کمینه یا بیشینه از یک تابع خطی روی یک چند ضلعی محدب می‌پردازد.[۱۰] این چندضلعی محدب در حقیقت نمایش نموداری تعدادی محدودیت از نوع نامعادله روی متغیر های تابع است. به بیان ساده‌تر به وسیله برنامه‌سازی خطی می‌توان بهترین نتیجه (مثلاً بیشترین سود یا کمترین هزینه) را در شرایط خاص و با محدودیت‌های خاص به دست آورد.

 محل اصلی استفاده برنامه‌ریزی خطی در اقتصاد است، اما در مهندسی نیز کاربردهای فراوانی دارد. می‌توان گفت حدود یک‌چهارم کل محاسبات علمی که بر روی رایانه انجام گرفته‌است، به برنامه‌ریزی خطی و مشتقات آن مربوط می‌شود.[۱۱]