البرمجة الرياضية الخطية من الأساليب الأساسية والمهمة التي تساعد متخذي القرار على اتخاذ قرارات سليمة وبطريقة فهمية، أسلوب البرمجة الخطية. وتعد مسائل البرمجة الخطية جزءاً من مسائل البرمجة الرياضية التي تضم الخطية منها واللاخطية؛ ثم إذا البرمجة الرياضية هي بدورها جزء من موضوع أكثر شمولية، يسمى ببحوث العمليات، أوالبحث العملياتي، التي تتعلق جميعها بمسائل التنظيم والإدارة ومسائل النقل والزراعة والصناعة....الخ.

إن البرمجة الرياضية الخطية هي مسألة تفضيل، ونقصد هنا بمسائل التفضيل تلك المسائل الرياضية التي تبحث عن تعظيم أوتقليل دالَّة (تابع) خطية موضوعة إلى مقيدات رياضية خطية أيضاً.

خلال الحرب العالمية الثانية، وبنتيجة محدودية الموارد العسكرية، كلفت الحكومة البريطانية فريقاً من كبار الفهماء دراسة مسائل كيفية توزيع مواردها العسكرية، وما يتناسب مع أفضل وضع دفاعي جوي وبري، ولقد أطلق على دراسات هذا الفريق اسم بحوث العمليات أوالبحث العملياتي. ثم أخذت هذه التسمية تطلق على كافة الأبحاث والدراسات التي تتعامل مع مسائل البرمجة أوالتوزيع ومسائل اتخاذ القرار. وقد حثَّت النتائج المشجعة لفريق بحوث العمليات البريطاني الإدارة العسكرية الجوية الأمريكية على تكوين فريق مشابه للقيام بالدراسات اللازمة في هذا المجال. فقد وجدت هذه الفرق حتى أساليب مسائل التفضيل التقليدية، كطريقة مضاريب لاغرانج مثلاً، ليست ذات فائدة كبيرة في حل مسائل البرمجة الخطية، مما استوجب إيجاد أساليب أكثر فاعلية في عام 1947 م حين طور جورج دانتزغ Dantzig عضوالفريق الأمريكي لبحوث العمليات الطريقة المبسطة (السمبلكس) لحل مسألة البرمجة الخطية؛ لكن لم تنشر تفاصيل هذه الطريقة إلا في عام 1956م. وبعد نشر الطريقة المبسطة(السمبلكس) وقع تسارع كبير في استخدام وتطوير البرمجة الخطية. ومن المشاركات التطويرية المهمة في ذلك المجال أعمال جال Gal التي قام بها وحده أوبمشاركة آخرين معه، إذ قاموا بصَوْغ المسألة الثنائية لمسألة البرمجة الخطية. وفي أيامنا هذه نجد حتى البرمجة الخطية تستخدم في مختلف المجالات الصناعية والاقتصادية والخدمية والعسكرية، وحيثما توجد عدة موارد محدودة الكمية مشهجرة في تشكيل أوإنتاج سلعة أوتقديم خدمة معينة.

إن المسائل الاقتصادية أوالفهمية، والتي يمكن حتى تصاغ كمسألة برمجة خطية، يجب حتى يتوفر فيها الأساسيات التالية: 1 ـ وجود غاية أوهدف يراد الوصول إلية مثل تحقيق كسب أعظمي أوتحقيق كلفة أصغرية أواقتصاد أعظمي في الوقت أوالجهد وغير ذلك. ويعبر عن ذلك بتابع رياضي خطي نسميه بتابع الهدف أوتابع الربح في حالة تعظيم، أوبتابع الخسارة في حالة تقليل. 2 ـ وجود عدد كبير من المتحولات أوالمجاهيل التي يجب تحديد قيمها للوصول إلى الغاية المطلوبة، وتسمى هذه المتحولات بمتحولات القرار. 3 ـ وجود علاقات ارتباط خطية بين تلك المتحولات وتسمى هذه العلاقات بقيود المسألة. إذن البرنامج الخطي هواستمثال optimization (تعظيم أوتقليل) دالَّة خطية، تحت قيود خطية. ويمكن رياضياً حتى نعبر عن ذلك بالشكل التالي: <nowiki>

حيث المجموعة {I={1,2,...,m تعبر عن مجموعة الأدلة الكلية للقيود، والمجموعة I0 هي مجموعة جزئية من I وتعبر عن مجموعة الأدلة التي تصف قيود المساواة للمسألة، والمجموعة -I هي مجموعة جزئية من I وتعبر عن مجموعة الأدلة التي تصف قيوداً أصغر أوتساوي للمسألة، والمجموعة +I هي مجموعة جزئية من I وتعبر عن مجموعة الأدلة التي تصف قيوداً أكبر أوتساوي للمسألة. نفترض حتى التوابع <nowiki>

هي توابع خطية. إنه ليس قيداً إذا افترضنا حتى جميع المتحولات (Xi(i=1,....,n ليست سالبة لأنه إذا عثر متحول xj يأخذ قيماً حقيقية لا على التعيين موجبة أوسالبة، يمكننا الاستعاضة عنه بالفرق -xj+- xj حيث المتحولان +xj و-xj يأخذان قيماً غير سالبة . أما إذا عثر متحول سالب من الشكل 0£ xj فإنه يمكننا أيضاً إبداله بمتحول حديث من الشكل yj=-xj. آلية وضْع البرنامج الرياضي الخطي لوضع البرنامج الرياضي الخطي يجب اتباع المراحل التالية:

1 ـ تحديد المتحولات التي يجب علينا إيجاد قيمها (متحولات القرار) وتمثيلها برموز جبرية.
2 ـ تحديد جميع القيود والعلاقات الممكنة التي تربط بين هذه المتحولات، ويعبَّر عن ذلك بمعادلات خطية أومتراجحات بحيث تكون هذه القيود خطية.
3 ـ تحديد تابع الهدف وتمثيله بتابع خطي بالنسبة للمتحولات، وتحديد ما إذا كان الهدف من المسألة تعظيم التابع الهدفي أوتقليله.

ويمكننا حتى نخط البرنامج الرياضي الخطي بطريقة المصفوفات كما يلي: <nowiki>

حيث عدد المتحولات غير المعلومة هوn وعدد القيود m وA مصفوفة القيود m×n وc متجهة عمود بـ n مركبة وbمتجهة عمود بـ m مركبة أيضاً وT يرمز إلى المنقول. إن حل البرنامج السابق يعني إيجاد القيمة الحقيقية التي تعطي التابع قيمة أعظميه (قيمة مثلى للتابع) على منطقة القيود، التي تسمى عادة منطقة الإمكانات. أما إذا أردنا حتى نفتش عن النقطة (قيم مثلى للمتحولات) من منطقة الإمكانات، والتي توافق القيمة فنخط المسألة على الشكل التالي: <nowiki>

وهذا يعني حتى الخوارزميات الموضوعة لحل البرامج الرياضية الخطية في حالة تعظيم، هي نفسها تصلح لحل البرامج الرياضية الخطية في حالة تقليل، وذلك بالاستفادة من العلاقة السابقة. الثنائية في البرمجة الخطية بوجه عام ودوماً يوجد إمكان اشتقاق برنامج رياضي خطي من جميع برنامج رياضي خطي آخر مفروض، نسميه عادة بالبرنامج الثنائي أوبالبرنامج المرافق للبرنامج الرياضي الخطي الأساسي. وربماقد يكون حل البرنامج الثنائي أسهل من البرنامج الأساسي في بعض الحالات، ويمكن حتى يفيد أيضاً في صياغة خوارزميات بُغْية إيجاد حلول لبرامج رياضية خطية، يطلب أحياناً حتى تكون حلولها المثلى تنتمي إلى مجموعة الأعداد السليمة بدلاً من مجموعة الأعداد الحقيقية.

والبرنامج الخطي الثنائي للبرنامج الرياضي الخطي التالي: <nowiki>

أهم الخوارزميات لحل البرامج الرياضية الخطية

من أبرز الطرق وأسهلها على الإطلاق لحل البرامج الرياضية الخطية، طريقة السمبلكس (1956) لـ دانتزغ Dantzig وقد بقيت هذه الطريقة مطبقة لسهولة التعامل معها على الرغم من ازدياد تعقيديتها (تعبر التعقيدية عن عدد العمليات الحسابية الأعظمي للوصول إلى الحل المثالي للمسألة) وتقدر تعقيدية طريقة السمبلكس بـ عملية حسابية وهي تعقيدية أسية. لكن في عام 1979 اقترح عالم روسي كاشيان (Khachian) طريقة جديدة لحل البرامج الرياضية الخطية بتعقيدية جبرية (O(n7L حيث n ترمز إلى عدد متحولات القرار وL ترمز إلى عدد البتات bits اللازمة لتوصيف معطيات الدخل للمسألة الخطية (c,b,A) وهذه الكيفية تعهد بطريقة القطوع الناسيرة. إذا هذه الطريقة مبنية بناء رياضياً مبنادىً، وهي تتفوق على طريقة السمبلكس نظرياً، لكن في المسائل العملية بقيت السمبلكس أكثر استعمالاً وموثوقية، لأن طريقة كاشيان لم تعط نتائج أكثر دقة وقناعة في المسائل العملية الحقيقية. في عام 1984 حصل تحول كبير في البرمجة الخطية، إذ نشر العالم الأمريكي كارماركار (Karmarkar) طريقتة الشهيرة ذات التعقيدية الجبرية (O(n3.5L وعلى ما يبدو، هذه الطريقة واعدة إذ عولج بها كثير من المسائل التطبيقية، ولا سيما في البحوث البترولية، وأعطت نتائج ممتازة. لكن مع جميع هذا سيبقى أمام طريقة السمبلكس أيضاً أيام جميلة بسبب سهولتها الفائقة.

مثال1: مسألة المزج يراد تحضير منتج ذي هجريب معين بحيث تحتوي الواحدة منه على الكميات (bi(i=1,...,m من العناصر (Bi(i=1,...,mكحد أدنى ويمكن تحضير هذا المنتج من المواد (Aj(j=1,...,n حيث تحتوي الواحدة من Aj على الكمية aij من العنصر Biوتكلف الواحدة من Aj المبلغ cj ويراد تحضير هذا المنتج بأقل كلفة ممكنة. يصاغ البرنامج الخطي لهذه المسألة على الشكل التالي: <nowiki>

مثال2: مسألة التنظيم الغذائي

اقترح طبيب على مريضه حتى يتناول يومياً كحد أدنى كميات معينة bi من فيتامينات أومقويات أساسية i=1,2,...,m)Bi)ضرورية لجسمه. يريد هذا المريض حتى يحصل على هذه الفيتامينات بتناوله الخضراوات والفواكه المتوفرة في الأسواق المحلية ولنرمز لهذه المواد بـ (Aj(j=1,...,n . فرضا حتى ثمن الوحدة الواحدة (مقدرة بـ غ أوكغ او....الخ) من المادة Aj هوcjوحدة نقدية حيث تحتوي هذه الوحدة على الكمية aij من الفيتامين الأساسي الأول Bi وa2j من الفيتامين الأساسي الثاني B2إلى غير ذلك ... والمطلوب في هذه المسألة تحديد الكميات (xj(j=1,...,n الواجب تناولها من المواد الغذائية من قبل المريض للحصول على تنظيم غذائي سليم يحقق طلب الطبيب من جهة وبأقل التكاليف من جهة أخرى <nowiki>

مثال3: مسألة تنظيم الإنتاج

لنفترض حتى معملاً ينتج الأنواع (Aj(j=1,...,n من مادة معينة قابلة للترويج، حيث يجري في عملية الإنتاج استخدام المواد الأولية (Bi(i=1,...,m المتوفر منها في المعمل وفي الوقت الحاضر الكميات (bi(i=1,...,m. إذا كانت الوحدة الواحدة من المنتج Aj تستهلك من المادة الأولية Bi الكمية aij وإذا كان الربح الصافي من إنتاج تلك الوحدة هو فالمطلوب تنظيم الإنتاج بحيث يحقق المعمل ربحا حقيقياً أعظمياً. <nowiki>

المصادر

• الموسوعة المعهدية