---
title: "Linear programming — برنامه‌ریزی خطی"
source: "https://systems-analysis.info/int/Linear_programming_%E2%80%94_%D8%A8%D8%B1%D9%86%D8%A7%D9%85%D9%87%E2%80%8C%D8%B1%DB%8C%D8%B2%DB%8C_%D8%AE%D8%B7%DB%8C"
wiki: "systems-analysis.info/int"
article: "Linear_programming_—_برنامه‌ریزی_خطی"
language: "fa"
categories:
  - "Category:Mathematical modeling"
  - "Category:Operations research"
  - "Category:Persian"
revision_id: 3863
wiki_created_at: 2026-09-06T23:27:13Z
wiki_modified_at: 2026-09-06T23:27:13Z
downloaded_at: 2026-09-07T22:59:29Z
---

# Linear programming — برنامه‌ریزی خطی

**برنامه‌ریزی خطی** — شاخه‌ای از برنامه‌ریزی ریاضی و روشی پرکاربرد در تحقیق در عملیات است که به توسعه‌ی نظریه و روش‌های حل مسائل یافتن مقدار بهینه (ماکزیمم یا مینیمم) یک تابع خطی در حضور قیود خطی می‌پردازد.

برنامه‌ریزی خطی یکی از قدرتمندترین و پرکاربردترین ابزارها برای حل مسائل بهینه‌سازی در اقتصاد، مدیریت، برنامه‌ریزی، لجستیک و سایر حوزه‌ها به شمار می‌رود.

## موضوع و کاربرد

**مسئله‌ی اصلی برنامه‌ریزی خطی** — یافتن بهترین (بهینه‌ترین) شیوه‌ی تخصیص منابع محدود برای دستیابی به هدفی مشخص است، هنگامی که هم هدف و هم قیود استفاده از منابع را بتوان با روابط خطی بیان کرد.

- برنامه‌ریزی خطی امکان حل مسائل عملی زیر را فراهم می‌کند:
- برنامه‌ریزی بهینه‌ی تولید.
- بهینه‌سازی جریان‌های حمل‌ونقل (مسئله‌ی حمل‌ونقل).
- توزیع بهینه‌ی سرمایه‌گذاری‌ها.
- برش بهینه‌ی مواد. مسئله‌ی انتساب.

## صورت‌بندی ریاضی مسئله‌ی برنامه‌ریزی خطی

مسئله‌ی استاندارد برنامه‌ریزی خطی به صورت زیر فرمول‌بندی می‌شود:

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

از نظر ریاضی، این به معنای کار با توابع خطی و دستگاه‌های معادلات/نامعادلات خطی است.

## مفاهیم اساسی برنامه‌ریزی خطی

- متغیرهای تصمیم (متغیرهای کنترل‌پذیر): کمیت‌هایی که مقادیر آن‌ها باید در فرآیند حل مسئله تعیین شوند (برای مثال، حجم تولید محصولات مختلف، مقدار منابع تخصیص‌یافته به اهداف گوناگون).
- تابع هدف: تابع خطی از متغیرهای تصمیم که مقدار آن باید ماکزیمم یا مینیمم شود. این تابع هدف مسئله را به صورت کمّی بیان می‌کند (برای مثال، کل سود، مجموع هزینه‌ها).
- قیود: دستگاهی از معادلات خطی و/یا نامعادلات خطی که متغیرهای تصمیم باید آن‌ها را برآورده سازند. قیود محدودیت‌های منابع، الزامات فناوری، تکالیف برنامه‌ای و سایر شرایط مسئله را منعکس می‌کنند.
- ناحیه‌ی جواب‌های موجه (NDM): مجموعه‌ی تمام ترکیب‌های مقادیر متغیرهای تصمیم که همه‌ی قیود مسئله را برآورده می‌سازند. از نظر هندسی، در فضای چندبُعدی، NDM یک چندوجهی محدب (پولیدر) است که ممکن است نامحدود یا تهی باشد.
- جواب موجه: هر ترکیبی از مقادیر متغیرها که به NDM تعلق داشته باشد.
- جواب بهینه: جواب موجهی که تابع هدف در آن به مقدار بهینه‌ی خود (ماکزیمم یا مینیمم) می‌رسد. اگر جواب بهینه وجود داشته باشد، همواره بر مرز NDM قرار دارد، حداقل در یکی از رئوس چندوجهی محدب NDM (قضیه‌ی اساسی برنامه‌ریزی خطی).

## روش‌های حل مسائل برنامه‌ریزی خطی

چندین روش اصلی برای حل مسائل برنامه‌ریزی خطی وجود دارد:

- روش گرافیکی: برای مسائل با دو متغیر تصمیم به کار می‌رود. امکان تصویرسازی NDM و تابع هدف در صفحه را فراهم می‌کند و جواب بهینه از طریق تحلیل رئوس NDM یا جابجایی خط تراز تابع هدف یافته می‌شود.
- روش سیمپلکس: الگوریتم تکراری همه‌منظوره‌ای که توسط George Dantzig توسعه یافته است. این روش به صورت گام‌به‌گام از یک رأس NDM به رأس مجاور منتقل می‌شود و در هر گام مقدار تابع هدف را بهبود می‌بخشد تا زمانی که جواب بهینه یافته شود. این روش کلاسیک‌ترین و شناخته‌شده‌ترین روش حل مسائل برنامه‌ریزی خطی است.
- روش‌های نقطه‌ی داخلی: دسته‌ای جایگزین از الگوریتم‌ها که پس از روش سیمپلکس ظهور کردند. این روش‌ها از درون NDM به سمت جواب بهینه حرکت می‌کنند، نه از مرزهای آن. این روش‌ها به‌ویژه برای حل مسائل برنامه‌ریزی خطی با ابعاد بسیار بزرگ کارآمد هستند.

## دوگانگی در برنامه‌ریزی خطی

به هر مسئله‌ی برنامه‌ریزی خطی (که مسئله‌ی اولیه نامیده می‌شود) می‌توان یک مسئله‌ی برنامه‌ریزی خطی دیگر به نام مسئله‌ی دوگان را متناظر ساخت. مسئله‌ی اولیه و دوگان پیوند تنگاتنگی با یکدیگر دارند:

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

## کاربردهای برنامه‌ریزی خطی

برنامه‌ریزی خطی کاربرد گسترده‌ای در زمینه‌های زیر دارد:

- اقتصاد و تجارت (برنامه‌ریزی تولید، لجستیک، امور مالی، بازاریابی).
- صنعت (بهینه‌سازی فرآیندهای فناوری، مدیریت موجودی، برش مواد).
- حمل‌ونقل (بهینه‌سازی مسیرها، برنامه‌های زمانی). کشاورزی (بهینه‌سازی سطح زیر کشت، جیره‌های غذایی دام).
- انرژی (بهینه‌سازی بارگذاری ظرفیت‌های تولید برق).

## همچنین ببینید

- تحقیق در عملیات
- بهینه‌سازی
- تابع هدف
- قیود
- ناحیه‌ی جواب‌های موجه
- جواب بهینه

## منابع

- *Dantzig, G.* Линейное программирование, его применения и обобщения. — М.: Прогресс, 1966.
- *Yudin, D. B., Goldstein, E. G.* Линейное программирование (теория, методы и приложения). — М.: Наука, 1969.
- *Taha, Hamdy A.* Operations Research: An Introduction. — Pearson. (10th ed., 2017)
- *Hillier, Frederick S.; Lieberman, Gerald J.* Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)