البرمجة الخطية: هي أكثر اساليب بحوث العمليات استخداما في مجال اتخاذ القرارات , وقد شاع استخدامها في عام 1947 بواسطة العالم جورج دانتزج الذي ادخل اسلوب السمبليكس في حل مشاكل البرمجة الخطية.
تعريف البرمجة الخطية:هي اسلوب رياضي يساعد على اتخاذ القرار الامثل في استخدام الموارد المتاحة, وذلك لهدف تعظيم الربح او خفض التكلفة. لذلك تعالج مسائل البرمجة الخطية عادة مشكلة تعظيم (تكبير) أو تصغير دالة معينة تسمى دالة الهدف ضمن مجال محدد . يتحدد هذا المجال بواسطة مجموعة من قيود مفروضة على متغيرات الدالة وغالباً ما تكون هذه القيود او الشروط على شكل متباينات أو معادلات. أما كلمة خطية فتعني أن دالة الهدف و جميع القيود دوال خطية في المتغيرات الداخلة فيها, وتسمى هذه المتغيرات بمتغيرات القرار.أما كلمة برمجة فترادف في معناها كلمة خطة قصيرة الأجل كما تشير الى وضع المشكلة بصيغة رياضية او نموذج رياضي وحلها بالاعتماد على العلاقات الخطية وهذا البرنامج يحدد انواع الانشطة اللازم القيام بها وتوقياتها وكمياتها باسلوب يتميز بالتتابعية, بمعنى ان هذا الاسلوب يصل بنا الى الحل الامثل على خطوات.
- مجالات تطبيق البرمجة الخطية:ان استخدامات البرمجة الخطية قد اتسعت لتشمل معظم نواحي الحياة سواء كان بالقطاع الخاص او العام , الربحي وغير الربحي ومن مجالات تطبيقها:
1) تخطيط الإنتاجاي (تخطيط المخرجات) , وتقليل تكلفة الإنتاج , أو تعظيم ربح.
2) تحديد تشكيلة المنتجات المثلى (اختيار عدد معين من المنتجات من بين عدة بدائل مطروحة ؛ مع الاخذ في الاعتبار طاقة الانتاج ومستلزماته المتاحة ومتطلباته لتحقيق أقصى ربح ممكن).
3) مشكلة تصميم المنتجات و الخدمات.إرشاد الإدارة في اختيار انسب المواد الداخلة في انتاج منتج او خدمة وارشادها في مدى توفر هذه المواد وكيفية استخدامها الأمثل, وفي التوقع المسبق للإنتاجية , مما يؤدي للوصول للهدف بطريقة مثلى
4) تخطيط عناصر المدخلات لنظام العمليات والانتاج.توفير التسهيلات والامكانيات اللازمة لتشغيل نظام العمليات والانتاج من اجل الحصول على المنتجات المطلوبة بحيث تحقق اعلى ربح ممكن مثل تخطيط المواد الخام المطلوبه للحصول ع منتج معين.
5) مشكلات النقل والتوزيع :اختيار اقصر مسارات النقل التي تحقق اقل تكلفة واعلى كفاءة توزيعية ممكنه)
6) مشاكل التخصيص:تخصيص الالات او العاملين لمهام معينة لتحقيق اقصى كفاءة واعلى ربح
7) مشكلة تخطيط الاستثمارات.( اختيار الاستثمار المناسب من بين عدة بدائل والذي يحقق اعلى ربح )
- الشروط الواجب توافرها في المشاكل التي يمكن حلها بأسلوب البرمجة الخطية :
1. التحديد الدقيق للهدف الذي تسعى الإدارة إلى تحقيقه في شكل كمي والهدف يكون تعظيم أو تدنية .
2. أن تكون هناك علاقة خطية بين المتغيرات التي تظهر في المشكلة وأن يتوافر شرط الإيجابية أو عدم السلبية .
3. أن تكون الموارد المتاحة محدودة أي نادرة (لابد ان يكون هناك قيد او اكثر )
- المنطق الاساسي للبرمجة الخطية:تعتمد البرمجة الخطية على صياغة المشكلة في شكل نمطي يساعد في تسهيل العمليات الحسابية المختلفة , وتؤكد على عدم اغفال أي عنصر هام في المشكلة, وتنظر الى أي مشكلة على انها تمثل نظام متكامل مكون من جزئيات تربط بينها علاقات تبادلية , وتسعى لتحقيق هدف معين , وتصف هذه العلاقات التبادلية باستخدام المتباينات او المعادلات للوصول للحل الامثل مع الاخذ في الاعتبار القيود المفروضة.
- خطوات استخدام البرمجة الخطية
- مراحل استخدام اساليب البرمجة الخطية تتمثل بالخطوات التالية):
- تحديد وصياغة المشكلة بشكل محدد ودقيق .
- بناء نموذج رياضي يعبر عن النظام(المشكلة) موضع البحث باستخدام المتباينات والمعادلات المختلفة .
- استخراج حل من النموذج .ومن أساليب البرمجة الخطية التي تمكن من الوصول للحل:
1) الأسلوب البياني : ويستخدم في حالة وجود مجهولية في المشكلة المطلوب وضع حل لها .
2) أسلوب السمبلكس : وهو الأسلوب العام في حل مشاكل البرمجة الخطية .
3) أسلوب النقل .
4) أسلوب التخصيص .
شرح أساليب البرمجة الخطية :
- الأسلوب البياني: يعتبر من أسهل أساليب البرمجة التعرف عليه يساعد على تفهم مشاكل البرمجة الخطية لكن يصعب استخدامه إذا زاد عدد المتغيرات عن أثنين .وتعتمد الطريقة البيانية أساساً على منطق تمثيل القيود الخاصة بالمشكلة في شكل خطوط مستقيمة ، ويمثل كل محور من المحورين الأفقي والرأسي أحد المتغيرين الخاصين بالمشكلة .ومن خلال الرسم يتم تحديد منطقة الحلول الممكنة والتي تفي بشروط المشكلة ولا تخل بأي منها ، ومن ثم اختبار مثالية الحل للتوصل للحل الأمثل للمشكلة . ويتم اختبار الحل بثلاث طرق للتأكد من مثالية الحل وهي:
1) الطريقة الجبرية: وذلك بحل كل معادلتين تضمان قيدين متقاطعين لاستخراج قيم المتغيرات عند كل تقاطع ثم التعويض عن تلك القيمة في دالة الهدف واختبار تلك القيم التي تحقق أعلى قيمة لدالة الهدف.
2) الطريقة الحسابية :يطلق عليها طريقة نقط الأركان ويتم فيها اختبار قيم المتغيرات عند كل ركن من أركان المنطقة الممكنة للإنتاج ، ثم اختبار الركن الذي يحقق أعلى قيمة لدالة الهدف.
3) طريقة خطوط الربح :ويمكن من خلاله التوصل إلى حل لمشكلة البرمجة الخطية وذلك عن طريق التعبير عن دالة الهدف في الرسم بخط مستقيم يعبر عن كميات متساوية من المساهمة لتغطية التكاليف بالربح عند كل مستوى من مستويات الإنتاج .ثم يقوم برسم سلسلة من خطوط الربح الموازية للخط الأول والتي تأخذ في التباعد تدريجياً عن نقطة الأصل وفي إتجاه اليمين . ويتحدد ميل خط الربح على أساس نسبة الربح المتحقق من المتغير الأول إلى الربح المتحقق من المتغير الثاني . ونصل إلى الحل الأمثل عندما يتلامس خط الربح مع أعلى نقطة في منطقة الحلول الممكنة .
- أسلوب السمبلكس :اسلوب السمبلكس هو الاسلوب او الطريقة العامة للبرمجة الخطية وقد ظهر بعد الاسلوب البياني الذي اظهر عدم فاعليته اذا زاد عدد المتغيرات عن اثنين , ولهذا نلجأ الى استخدام السمبلكس الذي يعد اسلوبا متطورا للوصول للحل الامثل
- ظاهرة الثنائية في مشاكل البرمجة الخطية :من المعروف في مشاكل البرمجة الخطية أن لكل مشكلة مقابل أو معكوس وهذا يسمى ظاهرة الثنائية في مشاكل البرمجة الخطية. النموذج الأصلي والبرنامج الخطي الثنائي :الفكرة الأساسية وراء نظرية الثنائية أن كل مشكلة من مشاكل البرمجة الخطية لها برنامج خطي يصاحبها .فمشاكل البرمجة الخطية التي تهدف إلى تعظيم الربح في النموذج الأصلي يصاحبها دائما مشكلة أخرى تهدف إلى تخفيض التكاليف يطلق عليها المشكلة الثنائية والعكس صحيح .والمنطق وراء ذلك يرجع الى ارتباط الارباح بالتكاليف فالارباح هي عائد التكلفة وبالتالي كلما انخفضت التكاليف زادت الارباح.
- أسلوب النقل: يعتبر أسلوب النقل أحد أساليب البرمجة الخطية الذي يمكن إدارة الإنتاج والعمليات من حل بعض المشاكل ذات الصفة الخاصة بطريقة أكفأ من طريقة السمبلكس المعروفة في البرمجة الخطية . * أوجه التشابه في أسلوب النقل وأسلوب السمبلكس :١. هي عملية تتابعية .٢. تبدأ بحل أساسي ممكن ثم تنتقل إلى حل آخر أفضل ممكن أيضا .٣. في كل مرحلة هناك اختبار يجرى للتأكد من إذا كان هناك إمكانية لتخفيض التكاليف أم لا .٤. الحل الأمثل يتم التوصل إليه عندما لايكون هناك أي إمكانية لتخفيض تكلفة النقل .تابع اسلوب النقل• مشاكل النقل يمكن حلها بواسطة أسلوب السمبلكس ولكن أسلوب النقل متطور ونابع من الأسلوب الأمثل ويوصل للحل بطرية أفضل .• يقدم أسلوب النقل عادة أداة مساعدة لإدارة الإنتاج والعمليات في التوصل إلى إتخاذ القرار الرشيد فيما يتعلق ببعض مشاكل تخطيط الإنتاج .
* شروط مشاكل النقل :١. أن يكون هناك تحديد واضح ودقيق للأهداف المطلوب تحقيقها .٢. أن تكون هناك قيود مفروضة على الموارد المتاحة للوقت .٣. أن يتحقق شرط الخطية بين متغيرات التكلفة .٤. أن يكون أمام الإدارة حرية الاختيار بين عدة عوامل مختلفة للوصول إلى الهدف . المعلومات والبيانات اللازمة توفرها لإدارة الإنتاج والعمليات لحتى تستطيع حل هذا النوع من المشاكل:١. إجمالي الموارد المتاحة في المصانع أو مناطق الإمداد .٢. إجمالي الكميات المطلوبة للجهات المختلفة .٣. بيانات عن التكاليف الخاصة بنقل وحدة واحدة من المنتجات من كل مصدر إلى مناطق الطلب .٤. بيانات عن أسعار البيع والأرباح لوحدة المنتج في كل موقع توزيع .
خطوات ترتيب المشكلة :١. تحديد الهدف ، أي تحديد دالة الهدف لمشكلة النقل وتكون عادة تخفيض تكلفة النقل .٢. التعبير عن القيود أو الإمكانيات المحددة التي تحد من إستخدام بدائل النقل المتاحة في شكل متباينات طاقة كل مصنع للانتاج او امكانية كل مخزن للتوزيع.٣. توافر شرط أساسي وهو عدم السلبية أي أن جميع متغيرات المشكلة يجب أن تكون ذات قيمة موجبة . • يتم التفرقة في أسلوب النقل بين حالتين :١. حالة الطلب يتعادل مع العرض (حالة التوازن) . وتحدث اذا كانت الكميات المتاحة متساوية مع الكميات المطلوبة , وحقيقة ان هذه الحاله هي الغير شائعة.٢. حالة عدم تعادل الطلب مع العرض (عدم التوازن) .
ساحة النقاش