برنامه ريزي خطي
Linear Programming ( LP)
برنامه ريزي خطي يكي از کاربردی ترين و موثرترين روشهاي بهينه سازي است . برنامه ريزي خطي توسط جئورج دانتزينگ ( George Dantzing ) در سال 1947 ابداع شد[1].
برنامه ريزي به معني برنامه نويسي كامپيوتر نيست بلكه شما مي توانيد با حل مساله برنامه ريزي خطي با كامپيوتر به جواب برسيد .
اولين روشی که برای حل مسائل برنامه ريزی خطی LP بوجود آمد , روش Simplex بود اين روش به وسيله نيروی هوايي آمريکا در جنگ جهانی دوم توسعه پيدا کرد .
اين روش بهترين الگوريتم مشهور به زبان ساده برای حل مسائل برنامه ريزی خطی است که بيشتر برای مسائل کوچک و متوسط برنامه ريزی خطی LP به کار مي رود . روش های متعددی برای تکميل روش Simplex ارائه شده است , از جمله روش Interior point که روشی برای اصلاح pivoting روش Simplex است
. در حال حاضر روش های سريعتر و متعددی برای حل مساله برنامه ريزی خطی
ارائه شده است . که در اين بخش به چند مورد آن بطور خلاصه پرداخته مي شود .
1- روش Simplex
2- روش Dual
3- روش اصلاح شده Simplex (Revised Simplex )
4- روش کارمارکار ( Karmarkar )
5- روش خاشيان
مثالهايي از مسائل LP كه در صنعت اتفاق مي افتد :
_ انتخاب بهترين محصول براي رسيدن به ماكزيمم سود .
_ پيدا كردن نمونه توزيع از كارخانه به انبار براي حداقل كردن قيمت نگهداري و توزيع با محدوديت ظرفيت .
- پيدا كردن مينيمم هزينه حرارتي در شبكه مبدلهاي حرارتي
- انتخاب بهترين توزيع جريان در کوره شکست حرارتی
- در سيستم های بويلر و turbo generator
- بهترين جريان برگشتی در برج های تقطير
هر
يك از اين مسائل شامل تعدادي متغير ، معادله مساوي و نا مساوي مي شود .
جواب مساله علاوه بر اين كه بايد معادلات محدوديت را برآورده كند بايد
اكسترمم تابع هدف را نيز برآورده نمايد ، (ماكزيمم سود يا مينيمم هزينه)
با كمك كامپيوتر شما مي توانيد مسائل LP را با صدها و هزاران متغير و محدوديت حل نماييد .
مسائل برنامه ريزي خطي(LP) يك نوع مساله برنامه ريزي محدب ( convex programming
) مي باشد كه تابع هدف محدب و محدوديت هاي خطي از نوع منطقه محدب است .
به اين معني كه اپتيمم موضعي ، اپتيمم نهايي ( هدف ) خواهد بود .
ادامه دارد ...http://www.menhaj.net