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

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

سرانجام این مسئله را لئونید خاچیان در سال ۱۹۷۹ با ارائه روش بیضوی حل کرد. این روش در بدترین حالت هم دارای زمان اجرای چندجمله‌ای بود. این روش تأثیر چندانی در جنبهٔ عملی مسئله نداشت چرا که همچنان روش سیمپلکس در همه موارد به جز تعداد محدودی از مسائل بهتر عمل می‌کرد. اما اهمیت نظری روش خاچیان غیرقابل‌انکار بود. این روش الهام‌بخش به وجود آمدن نسل جدیدی از راه‌حل‌ها شد که به آن‌ها روش نقطه داخلی گفته می‌شود. در این روش‌ها نقاط داخلی محدوده قابل بررسی متغیرها پیموده می‌شود و به سمت نقطه بهینه حرکت انجام می‌گیرد.

فهرست مطالب:

روش سیمپلکس

فرم استاندارد

ویژگی های فرم استاندارد

متغیرهای کمکی

متغیرهای کمبود

تبدیل نامعادله به معادله

تبدیل مدل به فرم استاندارد

متغیر مازاد

تبدیل مدل برنامه ریزی خطی به شکل استاندارد

مدل حداکثر سازی

مدل حداقل سازی

تابلوی اولیه سیمپلکس

شرح تابلوی سیمپلکس

پر کردن تابلوی سیمپلکس

انتقال ضرایب فنی به تابلو

طریقه نوشتن سطر صفر

متغیرهای اساسی

انتخاب متغیر ورودی

نمایش هندسی

انتخاب متغیر خروجی

سطر – ستون و عنصر لولا

تابلوی جدید سیمپلکس

محاسبه سطر جدید لولا

مقادیر سطر جدید

شرط بهینگی تابلوی سیمپلکس

روش سیمپلکس برای حل مسائل حداقل سازی

آزمون شرایط تابلوی سیمپلکس

ورود متغیر مصنوعی

M چیست؟

حل مسائل با ترکیبی از محدودیت ها

چگونگی تبدیل انواع مدل

روش دو مرحله ای

تفاوت روش دو مرحله ای و روش M بزرگ

موارد خاص

جواب بهینه چند گانه

فاقد ناحیه جواب

ناحیه جواب بیکران

جواب تهبگن

متغیرهای منفی

متغیرهای آزاد در علامت

متغیرهای با حد پایین منفی

مفهوم علامتها در سطر صفر

مفهوم قیمت سایه ای

قیمت های سایه برای مدلهای غیر استاندارد

و…