التحقق من التحسين

يمكن إجراء اختبار تحسين إذا استوفيت شرطين أي

1. هناك توزيعات m + n-1 ، التي يكون m بها عدد الصفوف ، n عدد الأعمدة. هنا م + ن - 1 = 6. لكن عدد التخصيصات هو خمسة.

2. يجب أن تكون هذه التوزيعات m + n - 1 في مواقع مستقلة. أي أنه لا ينبغي زيادة أو تخفيض أي تخصيص دون تغيير وضع التخصيصات أو انتهاك قيود الصف أو الكولوم.

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

لذلك ، لا يستوفي الشرط الأول وبالتالي من أجل تلبية الشرط الأول ، سيتعين علينا تخصيص كمية صغيرة E في الخلايا الخالية ذات تكلفة النقل الأقل. يمكن ملاحظة أنه يمكن تخصيص t في الخلية (2 ، 2) بتكلفة 7 وحدات ، ومع ذلك تظل التخصيصات في وضع مستقل كما هو موضح أدناه:

الآن عدد التخصيصات هو m + n- = 6 وهم في مواقع مستقلة.

اكتب مصفوفة التكلفة في الخلايا المخصصة.

مصفوفة التكلفة الأولية للخلايا المخصصة.

اكتب أيضًا قيم u _i و v _j كما تم شرحه سابقًا.

مصفوفة تقييم الخلية

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

يمكن أن نرى من الجدول 6 أنه إذا قمنا بالتخصيص في الخلية (1 ، 4) ، يتم تشكيل حلقة كما هو موضح ونخصص 10 وحدات بحيث يتم اختزال التخصيص في الخلية (2 ، 4) كما هو موضح أدناه في الجدول 7.

جدول تخصيص جديد سوف تصبح

تكلفة النقل = 5X ₂ + 10X ₁ 1 + 10X ₇ + 15X9 + 5X ₄ + 18 + 5 = 435 units. أي انخفضت تكلفة النقل من 475 وحدة إلى 435 وحدة.

تحقق من Optimaiity:

دعونا نرى ما إذا كان هذا الحل هو optima! أم لا؟ لذلك مرة أخرى يجب التحقق من شرطين أي

رقم التخصيص = m + n - 1 = 6 (راض)

التخصيص في وضع مستقل (راضٍ منذ لا يتم تشكيل الحلقة المغلقة للخلايا المخصصة)

اكتب التكلفة في القيم والقيم المخصصة من u _i و v _j

المثال 2:

(العرض والطلب غير المتوازن). حل مشكلة النقل التالية

إجمالي العرض = 200 وحدة ، الطلب = 185 وحدة.

حل:

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

الحل العملي الأساسي:

سوف نستخدم طريقة تقريب Vogel لإيجاد الحل المبدئي الأولي.

يتم إعطاء الحل المجدي الأولي من خلال المصفوفة التالية:

اختبار الاداء:

من المصفوفة أعلاه نجد أن:

(أ) عدد التوزيعات = m + n - 1 = 4 + 5-1 = 8

(ب) تكون هذه التوزيعات m + n - 1 في مواقع مستقلة.

لذلك يمكن إجراء اختبار التحسين. يتكون هذا من الخطوات الفرعية الموضحة مسبقًا كما هو موضح في الجداول أدناه:

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

النقل الأمثل (الحد الأدنى) بالإضافة إلى تكلفة الإنتاج.

Z = Rs. (4 × 25 + 6 × 5 + 8 × 20 +10 x 70 + 4 x 30 + 13 x 15 + 8 x 20 + 0 x 15)

= روبية. (100 + 30 + 160 + 170 + 120 + 195 + 160 + 0) = Rs. 1465.

المثال 3:

حل مشكلة النقل التالية لتعظيم الربح. نظرًا للاختلاف في تكلفة المواد الخام وتكلفة النقل ، يختلف ربح الوحدة بالعملة الروبية الموضح في الجدول أدناه:

حل مشكلة تعظيم الربح.

حل:

المشكلة غير متوازنة وبالتالي يجب إضافة صف زائف لجعله متوازنًا.

البحث عن حل عملي أساسي أولي:

يجب أن نستخدم طريقة تقريب vogel لتحديد الحل المجدي الأولي.

لاحظ أننا نتعامل مع مشكلة الحد الأقصى. ومن ثم ندخل الفرق بين أعلى وأعلى عناصر في كل صف على يمين الصف والفرق بين أعلى وأعلى العناصر في كل عمود في العمود المقابل.

يمثل كل من هذه الاختلافات وحدة الربح المفقودة لعدم تخصيص إلى أعلى خلية ربحية. وهكذا ، أثناء تحديد المخصصات ، في البداية نختار الخلية (2 ، 3) مع أعلى دخول في الصف 2 الذي يتوافق مع أعلى فرق من [45].

اختبار الاداء:

العدد المطلوب من التوزيعات = m + n - 1 = 3 + 4 - 1 = 6

العدد الفعلي للتخصيص = 5.

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

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

Z _max = Rs. [90 × 70 + 90 × 100 + 110 × 30 + 130 × 100 + 0 x 5]

= روبية. 31600.