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

نویسندگان: زهرا صابري – زهرا کاشفی

1-مقدمه
در رياضيات، مسائل برنامه ريزي خطي شامل بهينه سازي تابع هدفي خطي است که بايستي يکسري محدوديت در فرم هاي تساوي هاي خطي و نامساوي برقرار شوند. به طور خيلي غيررسمي برنامه ريزي خطي استفاده از مدل رياضي خطي براي بدست آوردن بهترين خروجي(به طور مثال حداکثر سود، حداقل کار) با توجه به شرط هاي داده شده (براي مثال فقط 30 ساعت کار در هفته، کار غير قانوني انجام ندادن و غيره) است. و به طور رسمي تر در يک چند سقفي (مانند چندضلعي يا چندوجهي) که تابعي با مقدار حقيقي بر روي آن تعريف شده است، هدف يافتن نقطه اي در اين چند سقفي است که تابع هدف بيشترين يا کمترين مقدار را دارا باشد. اين نقاط ممکن است موجود نباشد، اما اگر وجود داشته باشند جست و جو در ميان رئوس چند ضلعي يافتن حداقل يکي از آن ها را تضمين مي کند.

برنامه ريزي خطي به صورت استاندارد مي توانند نمايش داده شوند:

Maximize cTx

Subject to Ax ≤ b

x ≥ 0

X   بيانگر بردار متغير ها مي باشد و همچنين c وb  بردار ضرايب و A ماتريس ضرايب. عبارتي که بايد حداکثر يا حداقل شود تابع هدف نام دارد (در اين مورد  cTx    ).عبارت b Ax ≤ شرايطي هستند که يک چند وجهي محدب را نمايش مي دهند که تابع هدف روي آن بايد بهينه شود.
برنامه ريزي خطي مي تواند در زمينه هاي مختلف مطالعه مورد استفاده قرار گيرد. برنامه ريزي خطي به طور عمده در موقعيت هاي  تجاري و اقتصادي مورد استفاده قرار مي گيرد اما براي بعضي از مسائل مهندسي نيز مي تواند به کار برده شود. بعضي از صنعت ها که برنامه ريزي خطي را مورد استفاده قرار مي دهند عبارتند از حمل و نقل، انرژي، مخابرات و کارخانه ها و … . همچنين در مدل کردن مسائلي از قبيل برنامه ريزي، مسير يابي، زمانبندي،  تخصيص و طراحي مفيد است.يک ارزيابي انجام شده از 500 شرکت بزرگ دنيا، نشان داد که 85% درصد آنها از برنامه ريزي خطي استفاده نموده اند.[1]

2-تاريخچه برنامه ريزي خطي
مسئله حل يک سيستم نامساوي خطي به زمان فوريه[1] بر مي گردد. برنامه ريزي خطي به عنوان يک مدل رياضي به وجود آمد و در زمان جنگ جهاني دوم و پس از آن معلوم شد که طرح ريزي و هم آهنگي پروژه هاي مختلف و استفاده موثر از منابع کمياب يک ضرورت  است. تيم  SCOOP (محاسبات علمي برنامه هاي بهينه) نيروي هوايي ايالات متحده کار جدي خود را در ژوئن 1947 شروع کرد. ماحصل آن، ابداع روش سيمپلکس توسط جورج.بي.دانتزيک[2] در پايان تابستان 1947 بود. برنامه ريزي خطي به سرعت مورد توجه اقتصاد دانان، رياضي دانان، آماردانان، و موسسات دولتي قرار گرفت. در تابستان 1949 کنفرانسي در برنامه ريزي  و  براي برنامه ريزي مخارج و برگشت ها توسعه داده شد به طوري که با مسئوليت کميته Cowles براي تحقيق در اقتصاد برگزار شد. مقالات ارائه شده در اين کنفرانس اندکي بعد در سال 1951 به همت T.C.Koopmans در کتابي تحت عنوان تحليل فعاليت توليد و تخصيص جمع آوري شد.[2]. جان وان نيومن[3] در همان سال تئوري دو گانگي را توسعه داد و  لئونيد خاشيان[4] رياضي دان روسي ار تکنيک هاي ساده در اقتصاد قبل از دانتزيک استفاده کرد و جايزه نوبل را در سال 1975 در اقتصاد برد.

مثال اصلي دانتزيک يافتن بهترين تخصيص 70 نفر به 70 شغل بود و هنوز موفقيت او را نشان مي دهد. براي محاسبه احتياج به نمايش همه ي جايگشت ها براي انتخاب بهترين تخصيص بسيار وسيع و غير ممکن است. او مشاهده کرد با استفاده از الگوريتم سيمپلکس يافتن بهترين جواب فقط چند لحظه طول مي کشد و همچنين متوجه شد که جواب در گوشه چند ضلعي که به وسيله قيد هاي مسأله تشکيل مي شود وجود دارد.

3-کاربرد ها
برنامه ريزي خطي کاربرد هاي متعددي در ارتش، حکومت، صنعت و مهندسي شهر سازي يافته است همچنين اغلب به عنوان بخشي از طرح هاي محاسباتي، حل مسائل برنامه ريزي غير خطي، برنامه هاي گسسته، مسائل ترکيباتي، مسائل کنترل بهينه و برنامه ريزي احتمالي به کار مي رود.[2] برنامه ريزي خطي زمينه مهمي در بهينه سازي براي چندين دليل است: بسياري از مسائل عملي در تحقيق عمليات به عنوان مسئله برنامه ريزي خطي مي تواند بيان شود و همچنين تعدادي از الگوريتم هاي ديگر مسائل بهينه سازي به وسيله ي حل مسائل برنامه ريزي خطي، به عنوان زير مسئله کار مي کنند.    به طور تاريخي ايده هاي  برنامه ريزي خطي  الهام بخش بسياري از مفاهيم اوليه تئوري  بهينه سازي مانند دوگانگي، تجزيه، اهميت تحدب و تعميم آن بوده است.
برنامه ريزي خطي به طور عمده در اقتصاد کلان، مديرت تجاري، حداکثر کردن درآمد يا حداقل کردن هزينه ي توليد به کار مي رود. به عنوان مثال:  مديرت موجودي، مديرت دارايي و سهام، تخصيص منابع انساني و منابع غير انساني، برنامه ريزي سفرهاي تبليغاتي .
در بسياري شرکت ها و موسسات دولتي با به کارگيري موفقيت آميز برنامه ريزي خطي، ميليون ها دلار صرفه جويي کرده اند. در زير به بيان چند مورد از اين موفقيت ها اشاره مي کنيم:

با استفاده از برنامه ريزي خطي و برنامه ريزي عدد صحيح ، روشي براي زمان بندي گشت افسران پليس در سان فرانسيسکو، توسط تيلور و هاکس لي (1989) طراحي گرديد. با اين روش سالانه 11 ميليون دلار صرفه جويي حاصل شد، زمان پاسخ گويي به درخواست ها نيز حدود 3 ميليون دلار در سال افزايش يافت.
با استفاده از برنامه ريزي پويا، چائو و ديگران (1989) در حدود 79پست برق و بيش از 125 ميليون دلار در خريد موجودي و هزينه هاي کمبود صرفه جويي کردند.
با استفاده از برنامه ريزي عدد صحيح، واسکو و ديگران (1989) در طراحي تأسيسات قالب شمش به فولاد بتلهم کمک کردند. برنامه ريزي عدد صحيح باعث شد که در هزينه هاي عملياتي سالانه، 8 ميليون دلار صرفه جويي گردد.
با استفاده از مدل هاي شبکه پاول و ديگران (1988) يک مدل جهت تخصيص بار براي رانندگان کاميون در شرکت خطوط آمريکاي شمالي توسعه دادند. استفاده از اين مدل باعث ارائه خدمات بهتر به مشتريان و کاهش حدود 5/2 ميليارد دلار هزينه ساليانه شده است.
سوليوان و سکرست از برنامه ريزي خطي استفاده کردند تا در مورد چگونگي فرايند کره گيري از دوغ، شير خام، کشک شيرين و خامه براي پنير خامه اي، پنير بسته بندي، خامه ترش و خامه کشک تصميم گيري شود.استفاده از مدل، سود کره گيري را سالانه 48000 دلار افزايش داده است.
يک سواري يا کاميون قبل از جايگزيني چند سال مي تواند در يک کارخانه مورد استفاده قرار گيرد؟ نفت فيليپس از مدل هاي جايگزيني تجهيزات براي پاسخ به اين سؤال، استفاده کرد. اين مدل هاي جايگزيني تجهيزات، طبق برآورد انجام شده، باعث صرفه جويي سالانه 90000 دلار براي فيليپس شده اند.

4- تحقيقات جاري
موارد زير از جمله مواردي است که تحقيقات بر روي آنها ادامه دارد:
* پيدا نمودن الگوريتمي چند جمله اي زماني کاراتر جهت حل مسائل برنامه ريزي خطي
* پيدا نمودن الگوريتمي چند جمله اي قوي زماني کاراتر جهت حل مسائل برنامه ريزي خطي
* تعيين مسائلي که زمان اجراي مطابق الگوريتمهاي چند جمله اي قوي دارند( حالات خاص)

اينها مسائلي هستند که توسط استفان اسميت در بين 18 مسئله يزرگ حل نشده ي قرن 21 عنوان شده اند.در نوشته هاي اسميل اولين مسائل مسئله هاي تئوري برنامه ريزي خطي هستند.هر چند الگوريتم هايي براي حل مسائل برنامه ريزي خطي براي چند جمله اي با درجه يالا وجود دارد مانند روش بيضوي و نقطه دروني. ولي هيچ الگوريتمي براي چند جمله اي با درجه پائين يافت نشده است. توسعه ي الگوريتم هايي مانند اينها ميتواند کمکي به تئوري و همچنين تمريني براي حل مسائل برنامه ريزي خطي بزرگ تري باشد.
آيا با روش سطري کردن مي توان سيمپلکسي براي چند جمله اي ها به وجود آورد؟
اين سوالات وابسته به انجام آناليز و گسترش روش هايي مانند سيمپلکس است.

منابع
* 1- واين ال وينستون، “برنامه ريزي خطي”، 1380، نشر ترمه
* 2- مختار اس. بازارا، جان جي. جارويس، حنيف دي. شرالي، ” برنامه ريزي خطي” 1378، نشر کتاب دانشگاهي

3-http://en.wikipedia.org/wiki/Linear_programming

[1]  Fourier

[2] George B. Dantzig

[3] John von Neumann

[4] Leonid Kantorovich