طريقة الحل المجرية. الطريقة المجرية لحل مسائل الواجبات

خوارزمية الحل:

1. نحن نحل المشكلة إلى الحد الأدنى. هدف هذه الخطوة- الحصول على أكبر عدد ممكن من الأصفار في المصفوفة C. للقيام بذلك، نجد الحد الأدنى من العنصر في المصفوفة C في كل صف ونطرحه من كل عنصر في الصف المقابل. وبالمثل، في كل عمود نطرح الحد الأدنى للعنصر المقابل.

إذا تم إعطاء مصفوفة غير مربعة، فإننا نجعلها مربعة عن طريق جعل التكاليف تساوي الحد الأقصى للرقم في المصفوفة المعطاة.

2. إذا كان من الممكن، بعد الانتهاء من الخطوة الأولى، إجراء مهام، أي تحديد عنصر صفر في كل صف وعمود، فسيكون الحل الناتج هو الأمثل. إذا تعذر تحديد المواعيد، فانتقل إلى الخطوة الثالثة.

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

الطريقة المجريةالأكثر فعالية عند حل مشاكل النقل بكميات صحيحة من الإنتاج والاستهلاك.

مثال

مشكلة التخصيص هي حالة خاصة من مشكلة النقل، حيث ai = bj = 1. لذلك، يمكن حلها عن طريق خوارزميات مشكلة النقل. دعونا نفكر في طريقة أخرى أكثر فعالية وتأخذ في الاعتبار تفاصيل النموذج الرياضي. تسمى هذه الطريقة بالخوارزمية المجرية.

ويتكون من الخطوات التالية:

1) تحويل صفوف وأعمدة المصفوفة؛

2) تحديد الغرض؛

3) تعديل المصفوفة المحولة.

الخطوة الأولى. الهدف من هذه الخطوة هو الحصول على أقصى عدد ممكن من العناصر الصفرية في المصفوفة C. وللقيام بذلك، اطرح الحد الأدنى لعنصر الصف المقابل من جميع عناصر كل صف، واطرح الحد الأدنى لعنصر العمود المقابل من جميع العناصر من كل عمود.

الخطوة الثانية.إذا كان من الممكن، بعد تنفيذ الخطوة الأولى، تحديد عنصر صفر واحد في كل صف وكل عمود من المصفوفة C، فسيكون الحل الناتج هو التعيين الأمثل.

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

إذا بعد الخطوة الثالثة حل مثاليلم يتم تحقيق ذلك، فيجب تكرار إجراء رسم الخطوط المستقيمة حتى يتم الحصول على حل مقبول.

مثال.

توزيع الموارد بين الكائنات.

حل. الخطوة الأولى. قيم الحد الأدنى لعناصر الصفوف 1 و 2 و 3 و 4 هي 2 و 4 و 11 و 4 على التوالي. بطرح القيمة الدنيا المقابلة من عناصر كل صف، نحصل على

قيم الحد الأدنى لعناصر الأعمدة 1 و 2 و 3 و 4 هي 0، 0، 5، 0 على التوالي. بطرح القيمة الدنيا المقابلة من عناصر كل عمود، نحصل على ذلك

الخطوة الثانية. لم يتم استلام أي مهمة كاملة وتحتاج مصفوفة التكلفة إلى التعديل.

الخطوة الثالثة. شطب العمود 1، الصف 3، الصف 2 (أو العمود 2). قيمة الحد الأدنى للعنصر غير المتقاطع هي 2:

نطرحها من جميع العناصر غير المتقاطعة، ونضيفها مع جميع العناصر الموجودة عند تقاطع خطين، ونحصل على

إجابة. نقوم بتوجيه المورد الأول إلى الكائن الثالث، والثاني - إلى الكائن الثاني، والرابع - إلى الكائن الأول، والمورد الثالث - إلى الكائن الرابع. تكلفة الوجهة: 9 + 4 + 11 + 4 = 28.

ملحوظات. 1. إذا لم تكن المصفوفة الأصلية مربعة، فأنت بحاجة إلى تقديم موارد وهمية أو كائنات وهمية لجعل المصفوفة مربعة.

مشكلة التكليف

خوارزمية لحل مشكلة تعيين عنق الزجاجة

مشكلة اختناق التعيين

المحاضرة 13. مشاكل الواجب. الخوارزمية المجرية

تم حل هذه المشكلة عن طريق الخوارزمية الموضحة أعلاه. وهنا إنتاجها.

متاح نوظائف على بعض خطوط التجميع و نالعمال الذين يجب تكليفهم بهذه الوظائف؛ الأداء المعروف ج جعامل أنافي العمل ي. والحقيقة أنه مع بعض التوزيع على الوظائف، عامل ط كيقع على مكان العمل ي كيمكن وصفها بالجدول التالي:

وجود وسيلة سالتعيين إلى أماكن العمل، يمكنك العثور على الحد الأدنى من الإنتاجية الخاصة بهذه الطريقة ولاحظ أن هذا الحد الأدنى من الإنتاجية هو الذي يحدد سرعة الناقل وإنتاجيته. يسمى مكان العمل الذي يتم فيه تحقيق الحد الأدنى من الإنتاجية عنق الزجاجة في المهمة.

الهدف هو تعظيم

الخطوة 0.نقوم بإصلاح مصفوفة الإنتاجية وأي مهمة للوظائف. يترك س- الحد الأدنى من الأداء لهذا الغرض. لنبني ورقة عملنفس أبعاد المصفوفة ج; في خلية بها رقم ( اي جاي) في هذا الجدول سنضع الرمز "´" if ; وإلا فإننا سوف نترك هذه الخلية فارغة.

الخطوة 1.بالنظر إلى ورقة العمل التي تم إنشاؤها في الخطوة السابقة كورقة عمل في الخوارزمية لاختيار أكبر تطابق في رسم بياني ثنائي، فسنجد أكبر تطابق مناظر. إذا اتضح نأضلاعه، ثم تتم استعادة مهمة جديدة للوظائف على طولها ومع مستوى جديد أعلى، الحد الأدنى من الأداء. دعونا نشير إليها مرة أخرى بواسطة سوالعودة إلى الخطوة 0.إذا كان عدد الحواف أقل ن، فإن التعيين الحالي للوظائف هو الأمثل بالفعل.

بيانات المشكلة:

مثال 13.1. مطلوب للتوزيع ميعمل (أو فناني الأداء) على نآلات. وظيفة أنا (أنا=1,...,م)، يتم تنفيذها على الجهاز ي(ي=1،...، ن)، يرتبط بالتكاليف. تتكون المهمة من توزيع العمل عبر الأجهزة (يتم تنفيذ مهمة واحدة على جهاز واحد) بما يتوافق مع التصغير إجمالي التكاليف ج ج.

مثال 13.2. ج=(ج ج) – تكلفة إنتاج الجزء أناعلى الجهاز يتحتاج إلى العثور على توزيع الآلات بحيث تكون التكلفة الإجمالية للإنتاج في حدها الأدنى.

مثال 13.3.مشكلة النقل. يتم تحديد نقاط إنتاج السلع ونقاط استهلاك البضائع. مطلوب تحديد المراسلات الفردية الأمثل بين نقاط الإنتاج ونقاط الاستهلاك، بناءً على مصفوفة تكلفة النقل جبين النقاط ذات الصلة (أي تقليل التكلفة الإجمالية للنقل).

هنا تمثل الأعمال "نقاط الأصل" وتمثل الآلات "نقاط الوجهة". العرض عند كل نقطة مصدر يساوي 1. وبالمثل، الطلب عند كل نقطة وجهة يساوي 1. تكلفة "النقل" (إرفاق) العمل أناإلى الآلة ييساوي ج ج. إذا لم يكن من الممكن إنجاز بعض الأعمال على جهاز معين، فإن التكلفة المقابلة تعتبر باهظة للغاية عدد كبير.

قبل حل مثل هذه المشكلة لا بد من إزالة الخلل عن طريق إضافة عمل أو آلات وهمية حسب الظروف الأولية. لذلك، دون فقدان العمومية يمكننا وضعها م = ن.

دع = 0 إذا ي-لا يتم إنجاز عملي أنا-الآلة، = 1، إذا ي-يتم تنفيذ العمل على أنا-الآلة. وبالتالي، يمكن كتابة حل المشكلة في النموذج مصفوفة ثنائية الأبعاد. الحل الممكن يسمى ميعاد. يتم إنشاء حل ممكن عن طريق اختيار عنصر واحد بالضبط في كل صف من المصفوفة وعنصر واحد بالضبط في كل عمود من تلك المصفوفة.

ملاحظة 1 . لقيمة معينة نموجود ن! حلول ممكنة.

نموذج رياضيمهام:

تصغير الوظيفة ، مع القيود:

, (12.1)

, (12.2)

القيود (12.1) ضرورية لضمان تنفيذ كل مهمة مرة واحدة بالضبط. تضمن القيود (12.2) أنه سيتم تعيين وظيفة واحدة بالضبط لكل آلة.

مثال 13.4.لتوضيح مسألة التعيين، فكر في جدول يحتوي على ثلاث وظائف وثلاث آلات. تكلفة إنتاج الجزء أناعلى الجهاز ي :

نحن بحاجة إلى إيجاد توزيع الآلات بحيث تكون التكلفة الإجمالية للإنتاج في حدها الأدنى.

الهيكل المحدد لمشكلة المهمة يجعل من الممكن استخدامها طريقة فعالةلحلها.

ملاحظة 2. لن يتغير الحل الأمثل للمشكلة إذا تم طرح قيمة ثابتة عشوائية من أي صف أو عمود في مصفوفة التكلفة.

توضح الملاحظة 2 أنه إذا كان من الممكن إنشاء مصفوفة جديدة بعناصر صفرية وهذه العناصر الصفرية أو مجموعة فرعية منها تتوافق مع حل مقبول، فإن هذا الحل سيكون الأمثل.

.

الوجهة المثالية: , , , أخرى , .

لسوء الحظ، ليس من الممكن دائمًا تحديد الحل بهذه البساطة. لمثل هذه الحالات، فكر في الخوارزمية التالية.

الخطوة 1.(تصغير الصفوف والأعمدة). الهدف من هذه الخطوة هو الحصول على أقصى عدد ممكن من العناصر الصفرية في مصفوفة التكلفة. للقيام بذلك، يتم طرح الحد الأدنى لعنصر الصف المقابل من جميع عناصر كل صف، ثم يتم طرح الحد الأدنى لعنصر العمود المقابل من جميع عناصر كل عمود من المصفوفة الناتجة. ونتيجة لذلك، يتم الحصول على مصفوفة التكلفة المنخفضة والبدء في البحث عن المهام.

الخطوة 2.(تعريف المهام). في هذه الخطوة، يمكنك استخدام الخوارزمية للعثور على "أكبر تطابق مع مصفوفة رسم بياني ثنائي (هناك احتمالات أخرى)، إذا تم استبدال كل =0 من المصفوفة بـ "1"، و>0 بـ "0" .

إذا لم يتم العثور على الغرض الكامل، فمن الضروري إجراء مزيد من التعديل لمصفوفة التكلفة، أي. انتقل إلى الخطوة 3.

الخطوه 3. (تعديل المصفوفة المخفضة). بالنسبة لمصفوفة التكلفة المخفضة:

أ) احسب عدد الأصفار في كل صف غير مسطر وفي كل عمود غير مسطر.

ب) شطب الصف أو العمود الذي يحتوي على أكبر عدد ممكن من الأصفار.

ج) نفذ الخطوات أ) و ب) حتى يتم شطب جميع الأصفار.

د) من جميع العناصر غير المتقاطعة، اطرح الحد الأدنى من العناصر غير المتقاطعة وأضفه إلى كل عنصر يقع عند تقاطع خطين.

انتقل إلى الخطوة 2.

ملاحظة 3.لو المشكلة الأصليةهي مشكلة تعظيم، فيجب ضرب جميع عناصر مصفوفة التكلفة في (-1) وإضافتها بما يكفي عدد كبيربحيث لا تحتوي المصفوفة على عناصر سلبية. وينبغي بعد ذلك حل المشكلة باعتبارها مشكلة التقليل.

مثال 13.5.دعونا نوضح تشغيل الخوارزمية المجرية باستخدام مثال مشكلة التخصيص مع مصفوفة التكلفة التالية:

.

التكرار 1

الخطوة 1. تقليل الصفوف والأعمدة.

قيم الحد الأدنى لعناصر الصفوف 1 و 2 و 3 و 4 هي 2 و 4 و 11 و 4 على التوالي. وبطرح القيمة الدنيا المقابلة من عناصر كل صف، نحصل على المصفوفة التالية:

.

قيم الحد الأدنى لعناصر الأعمدة 1 و 2 و 3 و 4 هي 0 و 0 و 5 و 0 على التوالي. بطرح القيمة الدنيا المقابلة من عناصر كل عمود، نحصل على المصفوفة التالية.

صياغة ذات معنى للمشكلة. يوجد n من السيارات في الجمعية، كل منها قادرة على نقل Q i طن من البضائع شهريًا (i = 1,2،…، n). وبمساعدتهم، من الضروري ضمان نقل البضائع (الخشب، والمسامير، وما إلى ذلك) من الموردين إلى المستهلكين عن طريق نالطرق بكمية R j طن شهريًا (j = 1,2,…, n).
وتتمثل المهمة في نقل جميع البضائع بأقل التكاليف؛ وللقيام بذلك، يجب إرسال كل سيارة على طول طريق واحد فقط. فإذا كانت قدرة السيارة على نقل البضائع أقل من حاجة المستهلك لهذه البضائع، إذن هذا الطريقلا يمكن تخصيص السيارة. ولذلك، يتم تجميع المصفوفة C، التي تميز التكاليف ط-الالسيارة إذا تم تكليفها بذلك ي-الطريق.

الطريقة المجرية لحل مسائل الواجبات

خوارزمية الطريقة المجرية.

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

أدت السمات المحددة لمشاكل التعيين إلى ظهور طريقة مجرية فعالة لحلها. الفكرة الرئيسية للطريقة المجرية هي الانتقال من الأصل مصفوفة مربعةالقيمة C إلى مصفوفتها المكافئة Ce مع عناصر غير سالبة ونظام مكون من n أصفار مستقلة، لا ينتمي اثنان منها إلى نفس الصف أو نفس العمود. بالنسبة لـ n معين، هناك n! حلول ممكنة. إذا قمنا في مصفوفة التخصيص X بترتيب وحدات n بحيث يوجد في كل صف وعمود وحدة واحدة فقط، مرتبة وفقًا للأصفار المستقلة الموجودة في مصفوفة التكلفة المكافئة Se، فإننا نحصل على حلول مجدية لمشكلة التخصيص.

وينبغي أن يؤخذ في الاعتبار أنه بالنسبة لأي تخصيص غير صالح، يُفترض أن التكلفة المقابلة تساوي عددًا كبيرًا بما فيه الكفاية M في الحد الأدنى من المشاكل. إذا لم تكن المصفوفة الأصلية مربعة، فيجب إدخال عدد إضافي مطلوب من الصفوف أو الأعمدة، ويجب تخصيص قيم لعناصرها تحددها ظروف المشكلة، ربما بعد التخفيض، والبدائل السائدة باهظة الثمن أو رخيصة، ينبغي استبعادها.

الطريقة المجرية

تعد الطريقة المجرية من أكثر طرق الحل إثارة للاهتمام والأكثر شيوعًا مهام النقل.

دعونا أولا نتناول الأفكار الرئيسية للطريقة المجرية باستخدام مثال حل مشكلة الاختيار (مشكلة التخصيص)، وهي حالة خاصة من مشكلة T، ثم نعمم هذه الطريقة لمشكلة T اعتباطية.

الطريقة المجرية لمشكلة المهمة

صياغة المشكلة.لنفترض أن هناك أعمال مختلفةوالآليات، كل واحدة منها يمكن أن تؤدي أي وظيفة، ولكن بكفاءة غير متساوية. نشير إلى أداء الآلية عند أداء العمل، و = 1,...,ن؛ ي = 1,...,ن. ويشترط توزيع الآليات بين الوظائف بحيث يتم تعظيم التأثير الكلي لاستخدامها. تسمى هذه المهمة مشكلة الاختيارأو مشكلة الاحالة.

رسميا، يتم كتابته مثل هذا. يجب عليك تحديد التسلسل التالي من العناصر من المصفوفة

بحيث يكون المجموع أقصى وفي نفس الوقت من كل صف وعمود معتم اختيار عنصر واحد فقط.

دعونا نقدم المفاهيم التالية.

عناصر المصفوفة صفر معتسمى الأصفار المستقلة إذا كان أي صف وعمود عند التقاطع الذي يقع فيه العنصر لا يحتوي على عناصر أخرى من هذا القبيل.

اثنين المصفوفات المستطيلة معو دتسمى مكافئة ( ج ~ د)، إذا للجميع اي جاي. مسائل التخصيص التي تحددها المصفوفات المتكافئة تكون متكافئة (أي أن الحلول المثلى لأحدها ستكون الأمثل للثانية، والعكس صحيح).

وصف خوارزمية الطريقة المجرية

تتكون الخوارزمية من مرحلة أولية ولا تزيد عن ( ن-2) التكرارات المتسلسلة. ويرتبط كل تكرار بالتحويلات المكافئة للمصفوفة التي تم الحصول عليها نتيجة للتكرار السابق، ومع اختيار الحد الأقصى لعدد الأصفار المستقلة. النتيجة النهائية للتكرار هي زيادة عدد الأصفار المستقلة بمقدار واحد. بمجرد أن يصبح عدد الأصفار المستقلة متساويا ن، تم حل مشكلة الاختيار، و الخيار الأفضليتم تحديد التخصيصات من خلال مواقع الأصفار المستقلة في المصفوفة الأخيرة.

المرحلة الأولية. العثور على الحد الأقصى للعنصر في ي- m ويتم طرح كافة عناصر هذا العمود بالتتابع من الحد الأقصى. يتم تنفيذ هذه العملية على جميع أعمدة المصفوفة مع. ونتيجة لذلك، يتم تشكيل مصفوفة مع عناصر غير سلبية، في كل عمود يوجد على الأقل، واحد صفر.

التالي نعتبر أنا-الصف الرابع من المصفوفة الناتجة، ابحث عن الحد الأدنى لعنصرها a i واطرح الحد الأدنى من كل عنصر في هذا الصف. يتم تكرار هذا الإجراء مع جميع الخطوط. ونتيجة لذلك، نحصل على المصفوفة مع 0 (مع 0 ~ ج)، وكل صف وعمود يحتوي على صفر واحد على الأقل. عملية التحويل الموصوفة معالخامس مع 0 يسمى تخفيض المصفوفة.

ابحث عن صفر عشوائي في العمود الأول وقم بوضع علامة عليه بعلامة النجمة. ثم ننظر إلى العمود الثاني، وإذا كان فيه صفر يقع في صف لا يوجد فيه صفر بعلامة النجمة، فإننا نضع علامة النجمة عليه. وبالمثل، فإننا ننظر إلى جميع أعمدة المصفوفة واحدًا تلو الآخر مع 0 وقم بتمييز الأصفار التالية بعلامة "*" إن أمكن. ومن الواضح أن الأصفار من المصفوفة مع 0 المميزة بعلامة النجمة مستقلة. وبهذا تنتهي المرحلة الأولية.

(ك+1) التكرار. لنفترض ذلك ك-تم تنفيذ التكرار بالفعل ونتيجة لذلك تم الحصول على المصفوفة معك. إذا كانت تحتوي على عدد n من الأصفار متبوعة بعلامة النجمة، فستنتهي عملية الحل. وإلا نذهب إلى ( ك+1) -التكرار.

كل تكرار يبدأ بالمرحلة الأولى وينتهي بالمرحلة الثانية. بينهما يمكن تنفيذ مرحلتين عدة مرات: الثالثة - الأولى. قبل بدء التكرار، تشير العلامة "+" إلى أعمدة المصفوفة معكوالتي تحتوي على أصفار مع علامات النجمة.

المرحلة الأولى. عرض الأعمدة غير المحددة معك. إذا لم يكن هناك عناصر صفرية بينهم، انتقل إلى المرحلة الثالثة. إذا كان الصفر غير المحدد للمصفوفة معكتم اكتشافه، فمن الممكن حدوث إحدى الحالتين: 1) السطر الذي يحتوي على صفر غير محدد يحتوي أيضًا على صفر بعلامة النجمة؛ 2) لا يحتوي هذا السطر على صفر مع علامة النجمة.

وفي الحالة الثانية، ننتقل مباشرة إلى المرحلة الثانية، ونضع علامة على هذا الصفر بضربة واحدة.

في الحالة الأولى، يتم تمييز هذا الصفر غير المحدد بحدود ويتم تمييز السطر الذي يحتوي عليه (مع علامة "+" على يمين السطر). إنهم ينظرون من خلال هذا الخط، ويجدون صفرًا بعلامة النجمة ويدمرون علامة "+" من اختيار العمود الذي يحتوي على هذا الصفر.

بعد ذلك، يقومون بالبحث في هذا العمود (الذي أصبح غير محدد بالفعل) ويبحثون عن الصفر (أو الأصفار) غير المحدد الذي يقع فيه. يتم تمييز هذا الصفر بحدود ويتم تمييز السطر الذي يحتوي على هذا الصفر (أو الأصفار). ثم ينظرون عبر هذا الخط، ويبحثون عن صفر به علامة النجمة.

وتنتهي هذه العملية، في عدد محدود من الخطوات، بإحدى النتائج التالية:

1) جميع أصفار المصفوفة معكأبرزت، أي. موجودة في الصفوف أو الأعمدة المميزة. وفي هذه الحالة ينتقلون إلى المرحلة الثالثة؛

2) يوجد صفر غير محدد في السطر الذي لا يوجد فيه صفر بعلامة النجمة. ثم ينتقلون إلى المرحلة الثانية، مع وضع علامة على هذا الصفر بضربة واحدة.

المرحلة الثانية. في هذه المرحلة، يتم إنشاء السلسلة التالية من أصفار المصفوفة معك: صفر بادئ مع أولي، وصفر مع علامة نجمية تقع في نفس العمود مثل صفر بادئ مع أولي في نفس الصف مثل صفر بادئ مع علامة النجمة، وما إلى ذلك. لذلك، يتم تشكيل السلسلة عن طريق الانتقال من 0 " إلى 0 * على طول العمود، من 0 * إلى 0 " على طول الصف، وما إلى ذلك.

يمكن إثبات أن الخوارزمية الموصوفة لبناء سلسلة لا لبس فيها ومحدودة، وأن السلسلة تبدأ دائمًا وتنتهي بصفر مع أولي.

بعد ذلك، نضع العلامات النجمية فوق عناصر السلسلة الموجودة في الأماكن الفردية (0 ")، وندمرها فوق العناصر الزوجية (0 *). ثم ندمر جميع الحدود فوق العناصر معكوالرموز "+". سيتم زيادة عدد الأصفار المستقلة بمقدار واحد. على هذا ( ك+ 1) -اكتمل التكرار.

المرحلة الثالثة. ينتقلون إلى هذه المرحلة بعد المصفوفة الأولى إذا كانت جميعها أصفارًا معكأبرز. في هذه الحالة، من بين العناصر غير المحددة معكاختر الحد الأدنى وقم بتعيينه ح (ح>0). بعد ذلك يطرحون حمن جميع عناصر المصفوفة معكيقع في صفوف غير محددة ويتم إضافته إلى جميع العناصر الموجودة في الأعمدة المحددة. ونتيجة لذلك، يتم الحصول على مصفوفة جديدة مع "ك، مقابل معك. لاحظ أنه مع هذا

التحول، كل الأصفار مع مصفوفة النجمة معكتبقى صفر في مع " ك بالإضافة إلى ذلك، تظهر فيه أصفار جديدة غير محددة. ولذلك نعود إلى المرحلة الأولى. وبعد الانتهاء من المرحلة الأولى، حسب نتيجتها، إما أن ينتقلوا إلى المرحلة الثانية أو يعودوا إلى المرحلة الثالثة.

بعد عدد محدودالتكرار، المرحلة الأولى التالية ستنتهي بالتأكيد بالانتقال إلى المرحلة الثانية. وبعد تنفيذه سيزداد عدد الأصفار المستقلة بمقدار واحد و ( ك+ 1) - سيتم الانتهاء من التكرار الأول.

مثال 3.4.حل مشكلة التعيين مع المصفوفة

عند حل المشكلة نستخدم الترميز التالي:

علامة الاختيار "+" المراد تدميرها محاطة بدائرة؛ السلسلة، كما كان من قبل، يشار إليها بالسهام.

المرحلة الأولية. نجد الحد الأقصى لعنصر العمود الأول - 4. نطرح منه جميع عناصر هذا العمود. وبالمثل للحصول على الأعمدة الثاني والثالث والرابع والخامس مصفوفة جديدةاطرح جميع عناصر هذه الأعمدة من n" خمسة وثلاثة واثنين وثلاثة على التوالي. نحصل على المصفوفة مع "(ج"~ج). منذ في كل سطر مع "هو صفر، ثم مع " = مع 0 وتنتهي عملية تخفيض المصفوفة. بعد ذلك، نبحث عن الأصفار المستقلة "*" ونضع علامة عليها مع 0 ابتداء من السطر الأول.

التكرار الأول. المرحلة الأولى. نسلط الضوء على الأعمدة الأول والثاني والرابع من المصفوفة بعلامة "+". مع 0 التي تحتوي على 0 * .

ننظر إلى العمود الثالث غير المحدد، ونجد فيه صفرًا غير محدد مع 23 = 0، حدده بحدود وحدد السطر الثاني بعلامة "+". ننظر من خلال هذا الخط ونجد العنصر الموجود فيه مع 22 = 0 * وقم بإزالة علامة التحديد الخاصة بالعمود الثاني الذي يحتوي على 0 * . ثم ننظر إلى العمود الثاني - لا توجد فيه عناصر غير محددة. ننتقل إلى العمود الأخير غير المحدد (الخامس)، ونبحث فيه عن الأصفار غير المحددة. وبما أنه لا توجد أصفار غير محددة، فإننا ننتقل إلى المرحلة الثالثة.

المرحلة الثالثة. العثور على الحد الأدنى للعنصر في الجزء غير المحدد من المصفوفة مع 0 (أي العناصر الموجودة في أعمدة وصفوف غير مميزة بعلامة "+"). إنه متساوي ح = 1.

طرح او خصم ح= 1 من جميع عناصر الصفوف غير المحددة (أي الكل باستثناء الثاني) وإضافة إلى جميع عناصر الأعمدة المحددة (الأول والرابع). دعونا نحصل على المصفوفة مع " 1 والانتقال إلى المرحلة الأولى.

المرحلة الأولى. قبل البدء، نسلط الضوء مرة أخرى على الأعمدة الأول والثاني والرابع بعلامة "+". ننظر إلى العمود الثالث غير المحدد، ونجد فيه صفرًا غير محدد مع 23 = 0، ضع علامة عليها بعلامة الشرطة. نظرًا لأن السطر الثاني يحتوي على 0 * (element مع 22)، ثم حدد الصف الثاني بعلامة "+"، ثم قم بتدمير علامة التحديد للعمود الثاني، حيث يوجد 0 *. ثم ننظر إلى العمود الثاني ونجد فيه صفرًا غير محدد مع 12 = 0، ضع علامة عليها بعلامة الشرطة. لأن السطر الأول به صفر مع علامة النجمة مع 14 = 0 *، ثم نظللها بعلامة "+" وندمر علامة التحديد الخاصة بالعمود الرابع، حيث توجد علامة 0 * هذه. ثم نراجع العمود الرابع ونجد فيه صفراً غير محدد مع 54 = 0. نظرًا لعدم وجود صفر مع علامة النجمة في السطر الذي يقع فيه، مع تحديد هذا 0 بضربة، ننتقل إلى المرحلة الثانية.

النظر في المثال التالي. يجب أن يكون هناك خمسة أشخاص لأداء خمس وظائف مختلفة. ومن بيانات التقارير نعرف مقدار الوقت الذي يستغرقه كل منهم لإكمال كل مهمة. وتظهر هذه البيانات في الجدول.

فناني الأداء
الاحتياجات

في في هذه الحالةتمثل القيم الوقت الذي يقضيه كل عامل في كل وظيفة، وتكون القيم إما 1 أو 0، مع 1 إذا تم تعيين العامل i للوظيفة j و0 في جميع الحالات الأخرى. وبالتالي، يتم تقليل المشكلة إلى تقليل الوظيفة. البرمجة الخطية لطريق التكلفة

مع مراعاة القيود التالية.

ومن الواضح أننا إذا تجاهلنا الشرط الأخير واستبدلناه بالشرط

وينتج عن ذلك مشكلة نقل تكون فيها جميع الاحتياجات وجميع الموارد متساوية. في الحل الأمثل، تكون جميعها إما عددًا صحيحًا أو صفرًا، ويكون الواحد هو العدد الصحيح الوحيد الممكن. وبالتالي فإن حل مشكلة النقل في ظل هذه الظروف يؤدي دائما إلى المساواة.

ومع ذلك، بسبب الانحطاط، فإن طرق حل مشاكل النقل في حالة مشكلة المهمة غير فعالة. بالنسبة لأي تعيين، تتطابق الإمدادات حسب الصف دائمًا تلقائيًا مع الطلب حسب العمود، وبالتالي، بدلاً من 2n-1، نحصل على قيم n غير صفرية. في هذا الصدد، من الضروري ملء المصفوفة بقيم n-1 لـ e، وقد يتبين أن القيم غير الصفرية تحدد الحل الأمثل، لكن الفحص لا يكتشفها، لأن القيم​ من e يتم وضعها بشكل غير صحيح.

تعتمد طريقة حل مشكلة المهمة على نظريتين واضحتين إلى حد ما. الأول ينص على أن الحل لن يتغير إذا تمت إضافة أو طرح ثابت ما في أي عمود أو صف في المصفوفة. تمت صياغة هذه النظرية بدقة على النحو التالي:

النظرية 1.

إذا كان يقلل

للجميع مثل

ثم يقلل أيضًا من الوظيفة

حيث أمام الجميع

النظرية 2.

إذا كان كل شيء ممكنا، فمن الممكن العثور على مجموعة من هذا القبيل

فإن هذا الحل هو الأمثل.

النظرية الثانية واضحة. لإثبات النظرية الأولى، نلاحظ ذلك

ونظراً لأن الكميات المطروحة من Z للحصول عليها لا تعتمد عليها، فإنها تصل إلى الحد الأدنى كلما تم تصغير Z، والعكس صحيح.

طريقة الحل المطورة هي إضافة ثوابت إلى الصفوف والأعمدة وطرحها من الصفوف والأعمدة حتى يختفي عدد كافي من القيم ليعطي حل يساوي صفر.

يبدأ إيجاد الحل بطرح أصغر عنصر من كل صف ثم من كل عمود. ويبين الجدول نتائج المثال أعلاه.

الجدول أ)

فناني الأداء		خصم

الجدول ب)

فناني الأداء
خصم

تم طرح إجمالي 10 وحدات من الأعمدة والصفوف. لذلك، لتقييم أي حل تم الحصول عليه بشكل صحيح باستخدام الجدول (ب)، من الضروري إضافة 10 وحدات إلى النتيجة

بادئ ذي بدء، يسعون جاهدين لإيجاد حل يتضمن فقط خلايا الجدول (ب) التي تحتوي على صفر عناصر، حيث أن مثل هذا الحل، إذا أمكن العثور عليه، سيكون الأفضل على الإطلاق. ومع ذلك، هناك حالات حيث يكون للعديد من الحلول نفس الجودة. تم وضع علامة على الحل المقبول في الجدول (ب) بين قوسين. ومع ذلك، من أجل تحديد ما إذا كان يمكن تحسين الحل، يتم تطبيق الخوارزمية التالية.

ولنلاحظ أولا أن أي طرح إضافي من صف أو عمود، وإن كان قد يؤدي إلى ظهور أصفار جديدة، إلا أنه يؤدي حتما إلى ظهور عناصر سالبة، بحيث لا يكون الحل الصفري الآن هو الحل الأمثل بالضرورة. ومع ذلك، يمكن إزالة العناصر السلبية عن طريق إضافة الأرقام المقابلة إلى الصفوف أو الأعمدة. على سبيل المثال، إذا قمت بطرح 2 من العمود 1 في الجدول (ب)، فسيظهر العنصر 2 في الصف 1. إذا أضفت الآن 2 إلى الصف 1، فستحصل مرة أخرى على مصفوفة تحتوي على عناصر غير سالبة. التحدي هو الحصول على أصفار جديدة بالطريقة المحددة، ولكن في نفس الوقت الحصول في النهاية على مصفوفة تحتوي على حل يتكون من أصفار فقط. يمكن إثبات أن الخوارزمية الموضحة أدناه توفر حلاً لهذه المشكلة.

1. رسم الحد الأدنى من الخطوط الأفقية والعمودية التي تتقاطع مع جميع الأصفار مرة واحدة على الأقل. وتنفيذ هذه الخطوة في الجدول (ب) يعطي النتيجة في الجدول 1.

الجدول 1

لاحظ أنه في هذه الحالة يتم استخدام أربعة أسطر فقط، وبالتالي فإن الخلايا الصفرية لا تحتوي على الحل الأمثل.

• 2. حدد أصغر عنصر لا يتم رسم أي خط من خلاله. في المثال هو 1 في الخلية (5،2).
• 3. اطرح هذا العدد من جميع العناصر التي لا يرسم عليها خطوط، وأضفه إلى جميع العناصر التي يرسم عليها خطين. ينتج عن هذا المثال النتيجة الموضحة في الجدول 2.

الجدول 2

يجب أن تؤدي هذه الخطوة إلى ظهور صفر في خلية لم يكن هناك أي منها سابقًا. في المثال قيد النظر، هذه هي الخلية (5،2).

4. تحديد ما إذا كان هناك حل بين مجموعة الأصفار الجديدة. إذا لم يتم العثور على حل (في هذا المثال لا يوجد حل)، فارجع إلى الخطوة 1 وقم بتنفيذ كافة الخطوات اللاحقة حتى يتم العثور على حل. وبالاستمرار في النظر في هذا المثال، نحصل على النتيجة الموضحة في الجدول 3.

الجدول 3

يحتوي هذا الجدول بالفعل على حل، مع وضع علامة بين قوسين وقيمته 13، وهو 1 أفضل من الجدول الأصلي حل ممكن. , .

مثال 2.

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

لننفذ الخطوة الأولى من الخوارزمية.

الآن دعونا نطرح الحد الأدنى من التكاليفمن عناصر الصفوف المقابلة.

في الخطوة الثانية من الخوارزمية نجد الحد الأدنى من القيمحسب الأعمدة وطرحها من عناصر الأعمدة المقابلة لها. ونتيجة لذلك نحصل على المصفوفة المبينة في الجدول التالي.

وفي المصفوفة الأخيرة، ترتيب العناصر الصفرية لا يسمح بتخصيص وظيفة واحدة لكل طفل. على سبيل المثال، إذا قمنا بتعيين داشا لتنظيف المرآب، فسيتم استبعاد العمود الأول من المزيد من الدراسة ومن ثم لن يكون هناك أي عناصر صفرية في صف Alla.

• 1) في المصفوفة الأخيرة، نرسم الحد الأدنى من الخطوط الأفقية والعمودية على طول الصفوف والأعمدة من أجل شطب جميع العناصر الصفرية.
• 2) ابحث عن أصغر عنصر غير مشطوب واطرحه من العناصر المتبقية غير المشطوبة وأضفه إلى العناصر الموجودة عند تقاطع الخطوط المرسومة.

في المشكلة هذا المثالويتطلب الأمر ثلاثة خطوط مستقيمة، وهذا يؤدي إلى الجدول التالي:

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

الحل الأمثل الموضح في الجدول يقترح على داشا تنظيف المرآب، وكاتيا لقص المروج، وآلا لغسل السيارات، وساشا لتمشية الكلاب. القيمة المقابلة دالة الهدفيساوي 1+10+5+5=21. ويمكن الحصول على نفس القيمة من خلال جمع قيم وقيمة العنصر الأصغر بين جميع العناصر التي لم يتم شطبها.