books البرمجه الخطيه
If you do not find what you're looking for, you can use more accurate words.
البرمجة الخطية (Info)
طور فلكرسون وجونسون ودانتزيج هذه الطريقة وهي : لكل ضلع في المخطط نخصص متغير وهو 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 باضافة : بدل القيد الأول .
