برنامه ریزی خطی (Linear Programming - LP)، در ریاضیات (Mathematics)

انواع روش های بهینه سازی (Optimization Methods) را در آموزش زیر شرح دادیم :

برنامه ریزی خطی (Linear Programming - LP) :

📌 تعریف و مفهوم پایه

برنامه ریزی خطی (Linear Programming) یکی از اساسی ترین و پرکاربردترین روش های بهینه سازی است. در این روش، تابع هدف (Objective Function) و تمام قیود (Constraints) به صورت خطی هستند. به عبارت دیگر، همه روابط ریاضی مدل، خطی می باشند. فرم استاندارد یک مسئله برنامه ریزی خطی به صورت زیر است:

\[ \text{Maximize (or Minimize)} \quad Z = c_1x_1 + c_2x_2 + \ldots + c_nx_n \] \[ \text{Subject to:} \quad a_{11}x_1 + a_{12}x_2 + \ldots + a_{1n}x_n \leq b_1 \] \[ \quad a_{21}x_1 + a_{22}x_2 + \ldots + a_{2n}x_n \leq b_2 \] \[ \quad \vdots \] \[ \quad a_{m1}x_1 + a_{m2}x_2 + \ldots + a_{mn}x_n \leq b_m \] \[ \quad x_1, x_2, \ldots, x_n \geq 0 \]

🔍 اجزای اصلی مدل LP

متغیرهای تصمیم (Decision Variables): نمایش داده شده با

\[ x_1, x_2, ..., x_n \]

که مقادیر آنها باید تعیین شود.

تابع هدف (Objective Function): ترکیب خطی از متغیرها که باید بیشینه یا کمینه شود.

قیود (Constraints): محدودیت های مسئله که به صورت نامعادلات خطی یا معادلات خطی هستند.

شرط علامت (Sign Restrictions): معمولا متغیرها غیرمنفی فرض می شوند (

\[ x_j \geq 0 \]

).

💡 کاربردها

برنامه ریزی خطی در حوزه های مختلفی کاربرد دارد: برنامه ریزی تولید (مخلوط محصولات بهینه)، مسائل حمل و نقل (کمینه کردن هزینه حمل)، تخصیص منابع (منابع محدود به فعالیت های مختلف)، مسائل ترکیب مواد (مخلوط های نفتی، خوراک دام)، برنامه ریزی مالی (بهینه سازی پرتفوی)، و بسیاری مسائل مهندسی و مدیریتی.

🧮 مثال عددی ساده

یک کارخانه دو محصول A و B تولید می کند. سود هر واحد A برابر ۴۰ دلار و هر واحد B برابر ۳۰ دلار است. برای تولید A به ۲ واحد مواد اولیه و ۱ ساعت کارگر نیاز است. برای B به ۱ واحد مواد اولیه و ۲ ساعت کارگر نیاز است. موجودی مواد اولیه ۱۰۰ واحد و ساعت کارگر موجود ۸۰ ساعت است. مسئله LP به صورت زیر است:

\[ \text{Maximize} \quad Z = 40x_1 + 30x_2 \] \[ \text{Subject to:} \quad 2x_1 + x_2 \leq 100 \quad \text{(مواد اولیه)} \] \[ \quad x_1 + 2x_2 \leq 80 \quad \text{(ساعت کارگر)} \] \[ \quad x_1, x_2 \geq 0 \]

📐 روش های حل

روش های اصلی حل مسائل LP عبارتند از روش سیمپلکس (که در مورد بعد توضیح داده می شود)، روش گرافیکی (برای مسائل دو بعدی)، و روش های نقطه درونی. جواب بهینه همیشه در یکی از رئوس ناحیه موجه (Feasible Region) قرار دارد.

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