بخشی از مقاله
تحلیل و بررسی مباحث برنامه ریزی خطی
چکیده :
پژوهش عملیاتی (تحقیق در عملیات) یا علم مدیریت، با علم تصمیم و کاربرد آن در ارتباط است. علم مدیریت را می توان به عنوان شاخه ای از حوزه مدیریت قلمداد کرد که رویه عقلایی، منطقی، سیستماتیک و علمی را در تحلیل فرآیند مدیریت و مسائل مدیریتی بکار می گیرد. پژوهش عملیاتی را می توان "مجموعه ای از مدل ها و تکنیک های کمی که از طریق روش های علمی، مدیران را در امر تصمیم گیری یاری می دهد" تعریف کرد. پژوهش عملیاتی((OR، شاخه ای از ریاضیات کاربردی و علم اداری است که با رشته های مختلف علمی ارتباط دارد و از روش هایی مانند مدل سازی ریاضی، آمار و الگوریتم هایی برای یافتن راه حلی بهینه یا نزدیک به بهینه برای مسائل پیچیده استفاده می کند. از نقطه نظر عملی، OR را می توان هنر بهینه سازی، یعنی هنر یافتن کمینه یا بیشینه توابع هدف تعریف نمود. از نقطه نظر سازمانی، OR به مدیریت کمک می کند تا با استفاده از فرآیند علمی به اهدافش برسد. واژگان OR و علم مدیریت، اغلب به یک معنا بکار می روند. اگر دنبال تمایز این دو باشیم، علم مدیریت رابطه نزدیک تری با مدیریت بازرگانی دارد در حالی که OR ارتباط نزدیک تری با مهندسی صنایع دارد. مهندسی صنایع، بیشتر از یک نقطه نظر مهندسی بهره می گیرد و مهندسان صنایع اغلب، تکنیک های OR را به عنوان بخش عمده ای از مجموعه ابزارهای خود در نظر می گیرند. ORرا می توان چارچوبی نظام یافته دانست که روی کاربرد فن آوری اطلاعات برای تصمیم گیری آگاهانه متمرکز است. به دیگر سخن OR علم اختصاص بهینه منابع است. هدف OR فراهم آوردن مبانی منطقی برای تصمیم گیری است از راه جستجو برای فهم و پی ریزی شرایط پیچیده و استفاده از این فهم برای پیش بینی رفتار سیستم و بهبود عملکرد سیستم. بیشتر کار واقعی با استفاده از تکنیک های عددی و تحلیلی، برای ساخت و حل مدل های ریاضی سیستم های سازمانی مرکب از انسان، ماشین ها و راهکارها، انجام می پذیرد.
واژگان کلیدی : پژوهش عملیاتی ، برنامه ریزی خطی ، الگوریتم سیمپلکس
مقدمه ای بر پژوهش عملیاتی (تحقیق در عملیات)
نقش OR در بخش های خصوصی و همگانی به سرعت در حال افزایش است. بطور کلی OR گستره پهناوری از موضوعات حمل و نقل، مدیریت دارایی ها، تولید، ارتباطات، رایانه، سود، هزینه و بسیاری دیگر زمینه ها، که در آنها بهبود سودآوری اقتصادی در اولویت است، را پوشش می دهد. در بخش همگانی، مطالعات OR بیشتر روی سیاست گذاری انرژی، دفاع، سلامت، مدیریت منابع آب، طراحی و عملکرد سیستم های اورژانس شهری یا عدالت جنایی متمرکز است. OR یک روش تحلیلی برای حل مسائل و تصمیم گیری را ارائه می کند که در مدیریت سازمان ها سودمند است. در OR مسائل، نخست به اجزای پایه تفکیک می شوند دوم با تحلیل های ریاضی (برنامه ریزی ریاضی)حل می شوند. برخی از روش های تحلیلی مورد استفاده در OR شامل منطق ریاضی، شبیه سازی، تحلیل شبکه، تئوری صف و تئوری بازی می شوند. فرآیند واقعی OR را در حالت کلی می توان در سه مرحله پیمود:
مجموعه ای از راه حل های بالقوه برای یک مسأله، شناسایی و ایجاد می شود. این مجموعه می تواند بزرگ باشد.
گزینه های معرفی شده در گام نخست تحلیل می شوند و به مجموعه کوچک تری از گزینه های موجه تر و کارآمدتر کاهش می یابد.
1
گزینه های بدست آمده در گام دوم تحت اجرای شبیه سازی شده و در صورت امکان در معرض یک تحلیل واقعی در یک محیط در دنیای واقعی قرار می گیرند. در گام پایانی، علم مدیریت، تصمیم گیری و بهینه سازی نقش عمده و پر رنگی ایفا می کنند.
رویهم رفته، OR کارآمدی و کارایی یک سازمان، اداره، کارخانه یا بنگاه اقتصادی را بالا می برد. از این رو برخی از مزایای OR را می توان در این موارد جست: -1 کاهش هزینه یا سرمایه گذاری -2 افزایش سود، بهره وری یا بازگشت سرمایه -3 افزایش ارزش سهام -4 مدیریت و کاهش ریسک -5 افزایش کیفیت تصمیم گیری ها -6 افزایش توان عملیاتی و کاهش تأخیرها -7 بهینه سازی شکل استفاده از منابع محدود
قلمرو پژوهش عملیاتی، ابداع و کاربرد تحلیل های کمی برای حل مسائلی است که مدیران با آن روبرو هستند. فرآیند پژوهش عملیاتی مستلزم کوشش در تصمیم گیری و حل مسأله است. فرآیند حل مسأله به سه مرحله عمده شکل زیر طبقه بندی می شود:
یک کارخانه باید برای بسیاری موضوعات مربوط به تولید، توزیع، مصرف کننده ها، سهامداران، پردازش اطلاعات، کارمندان، اجتماع، قیمت گذاری و دیگر تصمیم گیری نماید. مجموعه این تصمیمات نیاز به یک برنامه ریزی و تصمیم گیری بهینه دارد که مدیریت عملیاتی شامل پژوهش عملیاتی و علم مدیریت می تواند راهگشای خوبی برای آن باشد. تصمیم گیری اقتصادی نیاز به انتخاب بهترین تصمیم از میان گزینه های تصمیم گیری دارد. هدف می تواند بیشینه کردن سود، کمینه کردن هزینه ، عملکرد موفق با توجه به نگرش و اقبال مشتریان یا گاهی نجات کارخانه در شرایط بحرانی باشد. تصمیم گیری ها با توجه به نیازهایی مانند بودجه و محدودیت منابع محدود می شوند. روش های پژوهش عملیاتی ابزارهایی توانمند و هوشمند برای چنین تصمیم گیری هایی در کارخانه ها هستند. کاربردهای OR در مدیریت تجاری، در قالب علوم کاربردی مانند علم مدیریت، مدیریت عملیاتی، مدیریت منطقی (لجستیک) مدیریت چرخه تولید و علم تصمیم گیری، بطور مفصل مورد بحث قرار گرفته اند.
در پژوهش عملیاتی، ما مدل های ریاضی را ساخته و بکار می گیریم. این مدل ها معمولاً انتزاعی از برنامه ریزی ریاضی و غالباً خطی مسائل مربوط به تجارت، صنایع یا مدیریت است. هر مدل انتزاعی از شرایط واقعی، باید آن شرایط و مسأله را چنان ساده سازی کند که تنها فاکتورهایی که نقش کارآمدتری در تابع هدف دارند وارد مدل شوند و دیگر عوامل حذف شوند. در دیگر صورت، نمی توانیم مسأله را محاسبه و تصمیم مشخصی بگیریم. پس از تصمیم گیری نیز باید با اعتبار سنجی تصمیم، درستی آن را بیازماییم. برای اینکه بتوانیم یک مدل ریاضی(خطی) از مسأْله ایجاد کنیم باید برداشت ها از مسأله و محدودیت های موجود را به دقت فرموله کنیم. اما در تعیین عواملی که نقش اثرگذارتری در تابع هدف دارند باید دقت لازم را به عمل بیاوریم که همین خود بخش مهمی از علم مدیریت و تصمیم سازی است. در برنامه ریزی ریاضی ما با سه دسته عامل سر و کار داریم: -1 عوامل بیرونی یا برون زا (external or exogenous) یا همان عواملی که به عنوان متغیرهای ورودی و اثرگذار وارد مدل می شوند. -2 عواملی که مدل می کوشد توضیح و پاسخی برای آنها ارائه نماید یا همان عوامل درون زا (endogenous)، وابسته یا ستاده (خروجی) مدل. -3 عواملی که باید از آنها در ساخت مدل چشم پوشید.
تقسیم بندی مدلهای ریاضی تحقیق در عملیات
همانطور که متوجه شدید در تحقیق در عملیات از مدل برای برنامه ریزی هرچه بهتر سیستم های نظامی، صنعتی، تجاری، مدیریتی، اقتصادی، شهرسازی، ساختمانی، حمل ونقل ...,موجود یا مربوط به آینده استفاده می کنیم .مدل های برنامه ریزی از نظر تقسیم بندی ریاضی به چند دسته تقسیم می شوند از جمله:
1 -برنامه ریزی خطیLinear Programming
2 -برنامه ریزی با اعداد صحیح.Integer Prog
3 -برنامه ریزی پویا.Dynamic Prog
4 -برنامه ریزی با متغیرهای از درجه یک ببالا) برنامه ریزی غیرخطی) Non-linear
5 -برنامه ریزی آرمانی.Goal Prog
لذا ما در این پژوهش به بررسی برنامه ریزی خطی می پردازیم .
برنامه ریزی خطی
برنامه ریزی خطی (Linear Programming) یکی از ارکان اصلی مدیریت سازمان می باشد ، از طرفی تصمیم گیری در مورد چگونگی ترکیب
و عملکرد و مشخص کردن اهداف پیش شرطی برای برنامه ریزی در سازمان می باشد به همین سبب است که امروزه از مدل سازی جهت تفسیر و حل صحیح و مناسب مسائل استفاده میشود که عموما این فرایند را میتوان از طریق مدلهای موجود در تحقیق در عملیات میسر ساخت.
این روش با استفاده از روابط ریاضی کمک میکند تا مدیران به هنگام تصمیم گیری در مورد فعالیتهای گوناگون بتوانند با شناسایی محدودیتهای کار نیز اهداف مساله بهترین و بهینه ترین تصمیم را اتخاذ کرده و مناسب ترین راهکار را استفاده نمایند ، که عموما این اهداف شامل حداکثر سود و یا حداقل کردن هزینه ها می باشد.
برنامه ریزی خطی عبارت است از یک تکنیک ریاضی جهت تخصیص منابع محدود موجود به بهترین صور ت ممکن در حالیکه روابط فیمابین عوامل متغیرها خطی باشد.
برنامهریزی خطی، یا همان بهینهسازی خطی، روشی در ریاضیات است که به پیدا کردن مقدار کمینه یا بیشینه از یک تابع خطی روی یک چندضلعی محدب میپردازد. این چندضلعی محدب در حقیقت نمایش نموداری تعدادی محدودیت از نوع نامعادله روی متغیرهای تابع است. به بیان سادهتر به وسیله برنامهسازی خطی میتوانهترینب نتیجه (مثلاً بیشترین سود یا کمترین هزینه) را در شرایط خاص و با محدودیتهای خاص به دست آورد. محل اصلی استفاده برنامهریزی خطی در مدیریت و اقتصاد است، اما در مهندسی نیز کاربردهای فراوانی دارد. درواقع برنامه ریزی خطی بخشی از تحقیق در عملیات و موسوم به علم مدیریت است که اول بار توسط نیروی هوایی ارتش آمریکا بکار گرفته شد. میتوان گفت حدود یکچهارم کل محاسبات علمی که بر روی رایانه انجام گرفتهاست، به برنامهریزی خطی و مشتقات آن مربوط میشود.
فردریک س. هیلیر- جرالد ج. لیبرمن، ترجمه محمد مدرس و اردوان آصفوزیری، تحقیق در عملیات، چاپ دهم تهران: نشر جوان، 1382
در برنامه ریزی خطی می توان مسائل مختلف از قبیل ترکیب تولید ، سرمایه گذاری ، بازار یابی ، حمل و نقل ، فرمولاسیون محصول ، زمان بندی چند دوره ای و ... را مدل سازی کرده با استفاده از نرم افزارهای مربوطه به حل آن بپردازیم.
در ریاضیات، مسائل برنامه ریزی خطی شامل بهینه سازی تابع هدفی خطی است که بایستی یکسری محدودیت در فرم های تساوی های خطی و نامساوی برقرار شوند. به طور خیلی غیررسمی برنامه ریزی خطی استفاده از مدل ریاضی خطی برای بدست آوردن بهترین خروجی(به طور مثال حداکثر سود، حداقل کار) با توجه به شرط های داده شده (برای مثال فقط 30 ساعت کار در هفته، کار غیر قانونی انجام ندادن و غیره) است.
و به طور رسمی تر در یک چند سقفی (مانند چندضلعی یا چندوجهی) که تابعی با مقدار حقیقی بر روی آن تعریف شده است، هدف یافتن نقطه ای در این چند سقفی است که تابع هدف بیشترین یا کمترین مقدار را دارا باشد. این نقاط ممکن است موجود نباشد، اما اگر وجود داشته باشند جست و جو در میان رئوس چند ضلعی یافتن حداقل یکی از آن ها را تضمین می کند.
برنامه ریزی خطی به صورت استاندارد می توانند نمایش داده شوند:
بیانگر بردار متغیر ها می باشد و همچنین c و bبردار ضرایب و A ماتریس ضرایب. عبارتی که باید حداکثر یا حداقل شود تابع هدف نام دارد (در این مورد.( cTx عبارت b Ax ≤ شرایطی هستند که یک چند وجهی محدب را نمایش می دهند که تابع هدف روی آن باید بهینه شود.
برنامه ریزی خطی می تواند در زمینه های مختلف مطالعه مورد استفاده قرار گیرد. برنامه ریزی خطی به طور عمده در موقعیت های تجاری و اقتصادی مورد استفاده قرار می گیرد اما برای بعضی از مسائل مهندسی نیز می تواند به کار برده شود. بعضی از صنعت ها که برنامه ریزی خطی را مورد استفاده قرار می دهند عبارتند از حمل و نقل، انرژی، مخابرات و کارخانه ها و . … همچنین در مدل کردن مسائلی از قبیل برنامه ریزی، مسیر یابی، زمانبندی، تخصیص و طراحی مفید است.یک ارزیابی انجام شده از 500 شرکت بزرگ دنیا، نشان داد که %85 درصد آنها از برنامه ریزی خطی استفاده نموده اند.
تاریخچه برنامه ریزی خطی
مسئله حل یک سیستم نامساوی خطی به زمان فوریه بر می گردد. برنامه ریزی خطی به عنوان یک مدل ریاضی به وجود آمد و در زمان جنگ جهانی دوم و پس از آن معلوم شد که طرح ریزی و هم آهنگی پروژه های مختلف و استفاده موثر از منابع کمیاب یک ضرورت است. تیم SCOOP )محاسبات علمی برنامه های بهینه) نیروی هوایی ایالات متحده کار جدی خود را در ژوئن 1947 شروع کرد. ماحصل آن، ابداع روش سیمپلکس توسط جورج.بی.دانتزیک در پایان تابستان 1947 بود. برنامه ریزی خطی به سرعت مورد توجه اقتصاد دانان، ریاضی دانان، آماردانان، و موسسات دولتی قرار گرفت. در تابستان 1949 کنفرانسی در برنامه ریزی و برای برنامه ریزی مخارج و برگشت ها توسعه داده شد به طوری که با مسئولیت کمیته Cowles برای تحقیق در اقتصاد برگزار شد. مقالات ارائه شده در این کنفرانس اندکی بعد در سال 1951 به همت T.C.Koopmans در کتابی تحت عنوان تحلیل فعالیت تولید و تخصیص جمع آوری شد.. جان وان نیومن در همان سال تئوری دو گانگی را توسعه داد و لئونید خاشیان ریاضی دان روسی ار تکنیک های ساده در اقتصاد قبل از دانتزیک استفاده کرد و جایزه نوبل را در سال 1975 در اقتصاد برد.
مثال اصلی دانتزیک یافتن بهترین تخصیص 70 نفر به 70 شغل بود و هنوز موفقیت او را نشان می دهد. برای محاسبه احتیاج به نمایش همه ی جایگشت ها برای انتخاب بهترین تخصیص بسیار وسیع و غیر ممکن است. او مشاهده کرد با استفاده از الگوریتم سیمپلکس یافتن بهترین جواب فقط چند لحظه طول می کشد و همچنین متوجه شد که جواب در گوشه چند ضلعی که به وسیله قید های مسأله تشکیل می شود وجود دارد.
کاربرد ها
برنامه ریزی خطی کاربرد های متعددی در ارتش، حکومت، صنعت و مهندسی شهر سازی یافته است همچنین اغلب به عنوان بخشی از طرح های محاسباتی، حل مسائل برنامه ریزی غیر خطی، برنامه های گسسته، مسائل ترکیباتی، مسائل کنترل بهینه و برنامه ریزی احتمالی به کار می رود. برنامه ریزی خطی زمینه مهمی در بهینه سازی برای چندین دلیل است: بسیاری از مسائل عملی در تحقیق عملیات به عنوان مسئله برنامه ریزی خطی می تواند بیان شود و همچنین تعدادی از الگوریتم های دیگر مسائل بهینه سازی به وسیله ی حل مسائل برنامه ریزی خطی، به عنوان زیر مسئله کار می کنند.
به طور تاریخی ایده های برنامه ریزی خطی الهام بخش بسیاری از مفاهیم اولیه تئوری بهینه سازی مانند دوگانگی، تجزیه، اهمیت تحدب و تعمیم آن بوده است.
برنامه ریزی خطی به طور عمده در اقتصاد کلان، مدیرت تجاری، حداکثر کردن درآمد یا حداقل کردن هزینه ی تولید به کار می رود. به عنوان مثال: مدیرت موجودی، مدیرت دارایی و سهام، تخصیص منابع انسانی و منابع غیر انسانی، برنامه ریزی سفرهای تبلیغاتی.
در بسیاری شرکت ها و موسسات دولتی با به کارگیری موفقیت آمیز برنامه ریزی خطی، میلیون ها دلار صرفه جویی کرده اند. در زیر به بیان چند مورد از این موفقیت ها اشاره می کنیم:
با استفاده از برنامه ریزی خطی و برنامه ریزی عدد صحیح ، روشی برای زمان بندی گشت افسران پلیس در سان فرانسیسکو، توسط تیلور و هاکس لی (1989) طراحی گردید. با این روش سالانه 11 میلیون دلار صرفه جویی حاصل شد، زمان پاسخ گویی به درخواست ها نیز حدود 3 میلیون دلار در سال افزایش یافت.
با استفاده از برنامه ریزی پویا، چائو و دیگران (1989) در حدود 79پست برق و بیش از 125 میلیون دلار در خرید موجودی و هزینه های کمبود صرفه جویی کردند.
با استفاده از برنامه ریزی عدد صحیح، واسکو و دیگران (1989) در طراحی تأسیسات قالب شمش به فولاد بتلهم کمک کردند. برنامه ریزی عدد صحیح باعث شد که در هزینه های عملیاتی سالانه، 8 میلیون دلار صرفه جویی گردد.
با استفاده از مدل های شبکه پاول و دیگران (1988) یک مدل جهت تخصیص بار برای رانندگان کامیون در شرکت خطوط آمریکای شمالی توسعه دادند. استفاده از این مدل باعث ارائه خدمات بهتر به مشتریان و کاهش حدود 2/5 میلیارد دلار هزینه سالیانه شده است.
سولیوان و سکرست از برنامه ریزی خطی استفاده کردند تا در مورد چگونگی فرایند کره گیری از دوغ، شیر خام، کشک شیرین و خامه برای پنیر خامه ای، پنیر بسته بندی، خامه ترش و خامه کشک تصمیم گیری شود.استفاده از مدل، سود کره گیری را سالانه 48000 دلار افزایش داده است.
یک سواری یا کامیون قبل از جایگزینی چند سال می تواند در یک کارخانه مورد استفاده قرار گیرد؟ نفت فیلیپس از مدل های جایگزینی تجهیزات برای پاسخ به این سؤال، استفاده کرد. این مدل های جایگزینی تجهیزات، طبق برآورد انجام شده، باعث صرفه جویی سالانه 90000 دلار برای فیلیپس شده اند .
تحقیقات جاری
موارد زیر از جمله مواردی است که تحقیقات بر روی آنها ادامه دارد:
* پیدا نمودن الگوریتمی چند جمله ای زمانی کاراتر جهت حل مسائل برنامه ریزی خطی
* پیدا نمودن الگوریتمی چند جمله ای قوی زمانی کاراتر جهت حل مسائل برنامه ریزی خطی
* تعیین مسائلی که زمان اجرای مطابق الگوریتمهای چند جمله ای قوی دارند( حالات خاص)
