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

Linear Programming

البرمجة الخطية هي فرع من الاستمثال الرياضي وهذا الفرع يبحث في إيجاد النقاط المثلى لدالة معينة وفق قيود (constraints) معينة.
البرمجة الخطية هي حالة خاصة جداً بحيث أن الدالة هي خطية والقيود عبارات عن متراجحات خطية .
ولها تطبيقات كثيرة ،
مثلاً في متغيرين $x_1,x_2$ نريد أن نجد أصغر قيمة للمقدار $c_1x_1 + c_2 x_2$ ولكن بشرط أن يحقق الحل المتراجحات التالية:

$\begin{array}{l}a_{11}x_1+a_{12}x_2 \leq b_1 \\a_{21}x_1+a_{22}x_2 \leq b_2 \\a_{31}x_1+a_{32}x_2 \leq b_3\end{array}$

في حالة متغيرين في مجموعة حل نظام المتراجحات تكون عادة محددة بمضلع ما . والمبرهنة الرئيسة للبرمجة الخطية هي أن النقطة المثلى (إن وجدت) هي أحد رؤوس المضلع!

يمكن تعميمها لـ n من المتغيرات بـ m من المتراجحات .
لتكن $c,x \in \mathbb R^n , b \in \mathbb R^m, A \in \mathbb R^{m \times n}$

فإن مسألة البرمجة الخطية تصاغ بالشكل المصفوفي المختصر:

$\begin{array}{ll}\mbox{minimize} & c^T x \\ \mbox{subject to} & Ax \leq b \end{array}$

تكون مجموعة حل نظام المتباينات عبارة فوق-مسطح polytope في الفضاء $\mathbb R^n$ ، وتكون النقطة المثلى إن وجدت أحد رؤوس فوق-المسطح.
وتسمى هذه المنطقة المحصورة بالمسطح بالمجموعة الممكنة feasible set ، وإن كانت المجموعة خالية فإن المسألة غير ممكنة infeasible .

لذا يجب البحث عن النقطة المثلى عبر رؤوس هذا المسطح والتي قد يكون عددها كبيراً عندما تكون n بالمئات أو الآلاف.

خوارزمية السبملكس (simplex algorithm) هي خوارزمية لحل مسائل البرمجة الخطية ، ولذا كانت طريقة simplex طريقة منظمة للبحث عن النقطة المثلى. وقد طورها George Dantzig عام 1948 .

ما زال في طور الإنشاء

هنالك نقص في شرحك لموضوع البرمجة الخطية وهو ام جيع المتغيرات يجب ان تكون غير سالبة في مسألة البرمجة الخطية والا كيف يمكن حل مسألة البرمجة الخطية بطريقة السمبلكس اذا لم تكن جميع متغيرات المسألة غير سالبة الا عن طريق فرض المتغيرات كحاصل طرح متغيرين غير سالبين وهذا يفقد المسألة التي ذكرتها انت صيغتها العمومية

رد

اتمنى توضيح ان البرمجه

قدم بواسطة Anonymous في ثلاثاء, 05/04/2010 - 18:53

اتمنى توضيح ان البرمجه الخطية يمكن حلها بطريقتين الا وهي السمبلكس والجراف ... وشرح كل طريقة .

شكرا للموقع

رد

تعريفها : - كلمة برمجة : تعني

قدم بواسطة Anonymous في خميس, 10/06/2011 - 14:13

تعريفها :
- كلمة برمجة : تعني تخطيط وليس لها علاقة ببرامج الحاسوب .
- خطية : تعني أن الاقتران الرياضي الممثل للمسألة هو اقتران خطي " من الدرجة الأولى ".
إذن البرمجة الخطية تعني : تخطيط الأنشطة للحصول على أفضل النتائج لتحقيق الهدف الأفضل من بين جميع البدائل .
* تتركب مسألة البرمجة الخطية من :
أ- دالة الهدف ( تعبر عن أفضل الأرباح أو اقل التكاليف ) .
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
لحل مشاكل البرمجة الخطية
- تعتبر طريقة سهلة وبسيطة وواضحة في معالجة مشاكل البرمجة الخطية، خاصة تلك المشاكل التي لا يزيد فيها المتغيرات عن اثنين والتي تحتوي على عدد بسيط من القيود.
- تعتبر مقدمة لدراسة طرق وأساليب أخرى أكثر تعقيداً مثل السمبلكس.
* يجب إتباع الخطوات التالية في أسلوب الرسم البياني :
- رسم المحور السيني والصادي ( الجزء الموجب من كل منهما ).
- تحديد نقطتين لكل مستقيم ( معادلة ).
- رسم المستقيمات المعبرة من المعادلات.
- تحديد نقطة الإمكانيات المتاحة.
- تعيين نقطة ضمن الإمكانيات المتاحة التي تعطي أفضل النتائج ( أعلى عائد أو أقل تكلفة )، وعادة ما تكون نقطة تقاطع مستقيمات، وتكون في حالة تعظيم الأرباح بعد ما يكون عن نقطة الأصل، وتكون في حالة تقليل التكاليف اقرب ما يكون من نقطة الأصل.