البرمجة الخطية

تعريفها :
- كلمة برمجة : تعني تخطيط وليس لها علاقة ببرامج الحاسوب .
- خطية : تعني أن الاقتران الرياضي الممثل للمسألة هو اقتران خطي " من الدرجة الأولى ".
إذن البرمجة الخطية تعني : تخطيط الأنشطة للحصول على أفضل النتائج لتحقيق الهدف الأفضل من بين جميع البدائل .
* تتركب مسألة البرمجة الخطية من :
أ- دالة الهدف ( تعبر عن أفضل الأرباح أو اقل التكاليف ) .
A- ::::::IVE FUNCTION :
MAX : Z = X 1 + 2 X2 .
ب- مجموعة من القيود يجب استيفاؤها .
وتسمى قيود المسألة أو القيود المهيكلة كما يسمى X1, X2 بمتغيرات القرار بحيث نبحث عن أفضل مزيج من هذين المركبين يجب أن تكون العلاقة بين هذه المتغيرات خطية.
B- STRUCTURAL CONSTRAINTS :
2 X1 + 6 X2  42
4 X1 + 2 X2  36
X2  4
ج- القيود عدم السلبية :
C- NON-NEGATIVITY RESTRICTIONS
X1 , X2  0 .
النموذج العام للمسائل البرمجية الخطية
الصيغة الرياضية
* يمكن التوصل إلى النموذج الرياضي العام عن طريق :
1- تحديد المتغيرات 2- تحديد دالة الهدف.
3- تحديد القيود المهيكلة 4- تحديد قيود عدم السلبية .
مثال : لإثبات النموذج العام لمسائل البرمجة الخطية
قيود الكميات اللازمة للإنتاج دالة الهدف
المنتوج ساعات العمل خشب م3 دهان / لتر الربح بالدينار
X1 طاولة 1 6.5 0.1 1.3 40
X2 كرسي 2 2.0 0.02 0.2 10
الكمية المتاحة 500 36 120 -

MAX : Z = 40 X1 + 10 X2
S.T :
6.5 X1 + 2 X2  500
0.1 X1 + 0.02 X2  36
1.3 X1 + 0.2 X2  120
N.N :
X1 , X2  0

(MAX , MIN) :
S.T. حسب القيود
a11X1 + a12X2 + ……. + a1n Xn  b1
a21X1 + a22X2 + ……. + a2n Xn  b2
a31X3 + a32X3 + ……. + a3n Xn  b3
a41X4 + a42X4 + ……. + a4n Xn  b4
N.N
X1 , X2 , …….. XN  0
بحيث أن :
I = 1 TO N
J = 1 TO N
لوضع النموذج على شكل مصفوفة
Z = CX
aX ( , = , ) b
X  0



مثال : إذا علمت أن مصنع للأجهزة يصنع نوعان من أجهزة الحاسوب حسب الجدول التالي :
MAX : Z = 3 X1 + 2 X2
S.T
3 X1 + X2  1500
X1 + X2  1000
X1 , X2  0
الأجهزة مواد خام ساعات العمل أرباح
الجهاز الأول 3 1 3
الجهاز الثاني 1 1 2
المتوفر 1500 1000

مثال : تتخصص إحدى الشركات الصناعية في إنتاج أربعة نوعيات من المنتجات، والجدول التالي يوضح رموز المنتجات وهامش ربح الوحدة، والعمليات الصناعية اللازمة لإنتاج تلك النوعيات ومعدل احتياج كل سلعة من هذه العمليات الصناعية وكذلك الطاقة القصوى للأقسام الصناعية:
MAX : Z = 2000 X1 + 5000 X2 + 4000 X3 + 2000 X4
S.T:
20 X1 + 20 X2 + 12 X3 + 10 X4  900
20 X1 + 25 X2 + 30 X3 + 15 X4  900
N.N:
X1 , X2 , X3 , X4  0

الأقسام الإنتاجية
المنتجات تجميع تصنيع ربح الوحدة
X1 20 20 2000
X2 20 25 5000
X3 12 30 4000
X4 10 15 2000
الطاقة 900 900 -





مثال : مصنع للحقائب ينتج نوعين من الحقائب وللمصنع وحدتان إنتاجيتان يتوفر لدى الوحدة الأولى 1500 ساعة / شهرياً ولدى الوحدة الثانية 1000 ساعة، ربح الحقيبة الواحدة للمنتج الأول 3 دنانير، وربح الحقيبة من النوع الثاني 2 دنانير .
- تحتاج الحقيبة الواحدة من النوع الأول إلى 3 ساعات في الوحدة الإنتاجية الأولى وساعة واحدة في الوحدة الإنتاجية الثانية .
- تحتاج الحقيبة الواحدة من النوع الثاني إلى 1 ساعة في الوحدة الإنتاجية الأولى و 1 ساعة في الوحدة الإنتاجية الثانية .
المطلوب : اكتب النموذج الرياضي لتغطية الأرباح .
MAX: Z = 3 X1 + 2 X2
S.T:
3 X1 + X2  1500
X1 + X2  1000
N.N:
X1 , X2  0

النوع مرحلة 1 مرحلة 2 الربح
حقيبة 1 3 1 3
حقيبة 2 1 1 2
موارد 1500 1000 -




الطريقة البيانية GRAPHICAL METHOD
لحل مشاكل البرمجة الخطية
- تعتبر طريقة سهلة وبسيطة وواضحة في معالجة مشاكل البرمجة الخطية، خاصة تلك المشاكل التي لا يزيد فيها المتغيرات عن اثنين والتي تحتوي على عدد بسيط من القيود.
- تعتبر مقدمة لدراسة طرق وأساليب أخرى أكثر تعقيداً مثل السمبلكس.
* يجب إتباع الخطوات التالية في أسلوب الرسم البياني :
- رسم المحور السيني والصادي ( الجزء الموجب من كل منهما ).
- تحديد نقطتين لكل مستقيم ( معادلة ).
- رسم المستقيمات المعبرة من المعادلات.
- تحديد نقطة الإمكانيات المتاحة.
- تعيين نقطة ضمن الإمكانيات المتاحة التي تعطي أفضل النتائج ( أعلى عائد أو أقل تكلفة )، وعادة ما تكون نقطة تقاطع مستقيمات، وتكون في حالة تعظيم الأرباح بعد ما يكون عن نقطة الأصل، وتكون في حالة تقليل التكاليف اقرب ما يكون من نقطة الأصل.

شكرا لك