كتب البرمجه الخطيه
اذا لم تجد ما تبحث عنه يمكنك استخدام كلمات أكثر دقة.
# البرمجة الخطية وبحوث العمليات
# البرمجه الخطيه باستخدام الرسم البياني
# البرمجة الخطية في المحاسبة
# البرمجه الخطيه باستخدام الحل البياني
# البرمجه الخطيه باسلوب السمبلكس
# البرمجه الخطية في الرياضيات
# البرمجه الخطيه 2015
# البرمجه الخطيه لتعظيم الربح
# المعادلات الخطية
# الأصول الخطية
# مسائل البرمجة الخطية
# الخطية منهج
# الخطية المطلب
# الأسس الرياضية للبرمجة الخطية
# النسخ الخطية النسخة
# دور البرمجة الخطية
# حل مسائل البرمجة الخطية
# مقدمه عن البرمجة الخطيه
# أساليب البرمجة الخطية
عرض المزيد
المصدر: wikipedia.org
البرمجة الخطية (معلومة)
طور فلكرسون وجونسون ودانتزيج هذه الطريقة وهي : لكل ضلع في المخطط نخصص متغير وهو 1 إذا وفقط إذا الضلع من ضمن الحل الأفضل للمسألة وقد كان تعريف مسألة البرمجة الخطية كالتالي :
: Minimize
: Subject to
توضيحات :
- من الواضح ان دالة الهدف هي مقياس لوزن الدائرة التي نريد ايجادها، وذلك لان كل يمكن ان يكون 1 أو 0 , اي ان ضلع يمكن ان تكون بالحل وبالتالي نضيف وزنها (وحينها ) أو يمكن الا يكون بالحل ثم بالتالي اي انه لن نحسب وزن الضلع .
- القيود(Constraints) في السطر 1+2 هي تحدد ان كل رأس (vertex) نستخدمه مرة واحدة في الحل اي ان لكل رأس درجة الخروج ودرجة الدخول اليه على الأكثر 1 .
- اما القيد 3 فهو يدعى "إلغاء المسارات الدائرية القصيرة" اي مسارات دائرية بطول اقل من n , وذلك لانه إذا كان هناك مسار دائري أقصر من n على مجموعة جزئية S من الرؤوس حينها سيحوي هذا المسار الدائري على اضلاع، وحينها القيد 3 لن يتحقق لذا لا يمكن ان نجد حلا أقصر من المرغوب به، وانتبه أيضا ان مسار دائري بطول 1 لا يمكن ان يكون حلا وذلك حسب قيود 1+2 (وبالتالي كذلك ل-n-1) لذا فانه مسموح وضع القيد :
- اما القيد الأخير فهو لبيان ان كل ضلع يمكن ان تكون بالحل الأمثل أو لا : إذا كان الضلع في الحل حينها يكون قيمة المتغير 1 وخلاف ذلك 0 .
- يمكن استبدال قيد 3 بالقيد التالي :
لحل هذه المسألة الخطية يمكن استخدام اي وسيلة لحل المسائل الخطية على الاعداد الكاملة ولكن هذه الخوارزمية لا يمكن ان تحله بوقت حدودي إذ انه يوجد متغيرات و- قيود درجة (1+2) و قيود على طول المسارات (3) لذا فانه لا يمكن حلها بشكل مباشر ما يحتم علينا استخدام طرق اخرى .
لتخفيف كمية القيود كانت هناك حاجة لتغيير هذه البرمجة الخطية واستبدالها بمسألة خطية اخرى مع كمية قيود اقل وقد كان هذا وسميت البرمجة الخطية MTZ على أسماء كاتبيها . وكان الحل باضافة متغيرات اضافية :
توضيح :
- القيد الأول منهما لضمان انه لا يوجد مسار دائري جزئي على المجموعات الجزئية : لذا فانه لا يوجد مسارات دائرية جزئية طولها اقل من n
- القيد الثاني يضمن ان كل معرف بشكل واحد ووحيد لكل حل ممكن .
ملاحظات :
- تبين ان البرمجة الخطية MTZ اضعف من البرمجة الاولى لانه تم برهنة انه في بعض الحالات القيمة التي يمكن ان ينتجها MTZ تكون اقل منها في البرمجة الاولى .
- يمكن تقوية MTZ باضافة : بدل القيد الأول .
