طريقة دانتزيغ. مشكلة نوع النقل هي حالة خاصة لمشكلة البرمجة الخطية

1. ما هي العبارات غير الصحيحة؟ طريقة دانزيج

الجواب: يمكن أن يعزى إلى مجموعة التدرج

2. أي من العبارات التالية صواب:

الإجابة: تسمى مشكلة LP مع نظام قيود غير متسق بالمشكلة المفتوحة.

3. أي من الطرق التالية غير نشطة

الجواب: النسبة الذهبية

4. أي من العبارات التالية صحيحة:

الإجابة: مهمة نوع النقل هي حالة خاصة للمهمة البرمجة الخطية

5. أى من العبارات التالية صحيحة: طريقة المربعات الصغرى

الجواب: يتعلق الأمر بحل النظام n المعادلات الخطيةعند تقريب النتائج بواسطة كثيرات الحدود من الترتيب n

6. أي من الطرق التالية غير متدرج

الجواب: طريقة بسيطة (طريقة Nelder-Mead)

7. أي من الطرق المشار إليها تسمح بإيجاد الحد الأقصى العالمي للدالة متعددة الوسائط

الجواب: المسح

8. ما هي طرق البحث المنسقة من بين القائمة

الجواب: الظل

9. تحقق من البيانات الصحيحة

الإجابة: لا يمكن استخدام طريقة العد البسيطة لإيجاد الطرف الأقصى وفقًا لإجراء Gauss-Seidel.

10. أشر إلى العبارة الصحيحة

الجواب: الخطة موجودة حل مقبولمهام

11. أشر إلى العبارة الخاطئة

الإجابة: طائرة تحتوي على نقطة زاوية واحدة على الأقل متعدد السطوح محدبيسمى المستوى المرجعي لهذا متعدد السطوح

12. حدد أرقام العبارات الصحيحة

الإجابة: لا يمكن حل مشكلات النقل باستخدام طريقة Danzig ، نظرًا لأنها مرتبطة بمشكلات البرمجة المنفصلة (1). الخطة الأصليةفي طريقة simplex ، نحصل على صفر من جميع المتغيرات الأساسية (3)

13. تشير العبارة الصحيحة؟

الإجابة: الحل الأساسي لمشكلة LP يتدهور إذا كان أحد المتغيرات الحرة على الأقل يساوي صفرًا

14. أي مما يلي غير صحيح:

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

15. أي العبارات أدناه صحيحة؟

الإجابة: تنتمي مشكلة البائع المتجول إلى مجال البرمجة المنفصلة.

16. أي مما يلي صحيح:

الإجابة: إحدى مشكلات التحسين الرئيسية هي "مشكلة الأبعاد"

17. ما هو الخطأ في البيانات أعلاه؟

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

18. أي من العبارات التالية غير صحيحة؟

الإجابة: يمكن حل مشكلة LP من خلال إجراء انتقال منظم من خطة إلى أخرى.

19. أي مما يلي صحيح

الجواب: داخل مجال الحلول المقبولة لمشكلة LP لا يمكن أن يكون هناك حد أقصى

20. أي مما يلي خاطئ؟

الجواب: لإيجاد الطرف الأقصى لخطي دالة الهدفباستخدام طريقة simplex ، من الضروري إجراء تكرارات n-m ، n هو عدد المجهول للمشكلة ، m هو عدد القيود العامة

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

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

إسقاطات التدرج
على محور الإحداثيات تساوي المشتقات الجزئية للدالة
للمتغيرات المقابلة ، أي

. (2.4)

تشمل طرق التدرج: طريقة الاسترخاء ، والتدرج ، والنزول الحاد وعدد من الطرق الأخرى.

ضع في اعتبارك بعض طرق التدرج.

طريقة التدرج

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

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

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

يمكن أن تبدو صيغة الخوارزمية كما يلي:

,
. (2.5)

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

سجل صيغة آخر للخوارزمية هو:

,
. (2.6)

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

في استراتيجية تغيير الملعب
في هذه الحالة يتم استخدام التدرجات
و
تختلف في الاتجاه. يتم تغيير خطوة البحث وفقًا للقاعدة:

(2.7)

أين
هي زاوية دوران التدرج اللوني عند الخطوة k-th ، يحددها التعبير

,

,
هي الحدود المسموح بها لزاوية دوران التدرج.

تظهر طبيعة البحث عن الطريقة المثلى في طريقة التدرج في الشكل. 2.1.

يمكن العثور على اللحظة التي ينتهي فيها البحث عن طريق التحقق من كل خطوة في العلاقة

,

أين هو خطأ الحساب المحدد.

أرز. 2.1. طبيعة الحركة نحو الأفضل في طريقة التدرج بخطوة كبيرة الحجم

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

عيب آخر لهذه الطريقة هو قدر كبير من الحسابات ، منذ ذلك الحين في كل خطوة ، يتم تحديد قيم جميع المشتقات الجزئية للوظيفة التي يتم تحسينها فيما يتعلق بجميع المتغيرات المستقلة.

طريقة النزول الحاد

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

يمكن تقليل مقدار الحساب باستخدام طريقة النزول الأكثر حدة.

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

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

أرز. 2.2. طبيعة الحركة نحو الأفضل في أشد درجات الانحدار (-) وطريقة التدرج (∙∙∙∙)

بالمقارنة مع طريقة التدرج اللوني ، فإن أسلوب النزول الحاد يكون أكثر فائدة نظرًا لتقليل مقدار الحساب.

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

كمعيار لإنهاء البحث ، يمكن استخدام نفس الشرط كما في الطريقة أعلاه.

بالإضافة إلى ذلك ، يمكن للمرء أيضًا قبول شرط إنهاء البحث في شكل العلاقة

,

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

.

التطبيق المشترك لشروط إنهاء البحث له ما يبرره في الحالات التي يكون فيها للوظيفة التي يتم تحسينها حدًا أدنى واضحًا.

أرز. 2.3 لتعريف نهاية البحث بأقصى طريقة نزول

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

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

يوجد طرق مختلفةاختيار الخطوة ، كل منها مجموعات متغير معينطريقة التدرج.

1. طريقة الانحدار الشديد.

ضع في اعتبارك دالة لمتغير قياسي واحد واختر القيمة التي تتساوى فيها

هذه الطريقة ، التي اقترحها O. Cauchy في عام 1845 ، تسمى الآن طريقة الهبوط الأكثر حدة.

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

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

نحن نطبق طريقة النزول الأكثر انحدارًا لتقليل الوظيفة التربيعية

مع مصفوفة محددة موجبة متماثلة أ.

وفقًا للصيغة (10.8) ، في هذه الحالة ، تبدو الصيغة (10.22) كما يلي:

لاحظ أن

هذه الوظيفة هي دالة تربيعية للمعامل a وتصل إلى الحد الأدنى عند هذه القيمة

وهكذا ، كما هو مطبق على تصغير التربيعية

دالة (10.24) ، فإن أقصى طريقة للهبوط تعادل الحساب بالصيغة (10.25) ، حيث

ملاحظة 1. نظرًا لأن الحد الأدنى للدالة (10.24) يتزامن مع حل النظام ، يمكن أيضًا استخدام طريقة النزول الأكثر حدة (10.25) ، (10.26) طريقة تكراريةحلول الأنظمة الخطية المعادلات الجبريةمع مصفوفات محددة موجبة متماثلة.

الملاحظة 2. لاحظ أين علاقة رايلي (انظر الفقرة 1.8).

مثال 10.1. نحن نطبق طريقة النزول الأكثر انحدارًا لتقليل الوظيفة التربيعية

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

نأخذ التقريب الأولي ونجري العمليات الحسابية باستخدام الصيغ (10.25) ، (10.26).

أنا التكرار.

II التكرار.

يمكن إثبات أنه سيتم الحصول على القيم عند التكرار

لاحظ أنه مع هكذا ،

يتقارب التسلسل الذي تم الحصول عليه بواسطة طريقة النزول الحاد بمعدل المتوالية الهندسيةقاسمها

على التين. يوضح 10.5 بالضبط مسار الهبوط الذي تم الحصول عليه في هذا المثال.

في حالة تصغير دالة تربيعية ، يكون ما يلي صحيحًا النتيجة النهائية.

نظرية 10.1. لنفترض أن A مصفوفة محددة موجبة متماثلة ودع الدالة التربيعية (10.24) يتم تصغيرها. بعد ذلك ، لأي اختيار للتقريب الأولي ، تتقارب أكثر طرق الانحدار حدة (10.25) ، (10.26) ويكون تقدير الخطأ التالي صحيحًا:

هنا و Lado هما الحد الأدنى والحد الأقصى لقيم eigenvalues ​​للمصفوفة A.

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

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

يتقارب التسلسل هنا بمعدل تقدم هندسي ، يكون قاسمه ، أي أبطأ بكثير ،

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

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

ملاحظة 2. بالنسبة لدالة الهدف التربيعية (10.24) ، يمكن إيجاد حل مسألة التصغير أحادية البعد (10.23) في صيغة صيغة صريحة بسيطة (10.26). ومع ذلك ، بالنسبة لمعظم الآخرين وظائف غير خطيةلا يمكن القيام بذلك ، ولحساب طريقة الهبوط الحاد يجب على المرء أن يطبق الطرق العدديةتصغير أحادي البعد من النوع الذي تمت مناقشته في الفصل السابق.

2. مشكلة "الوديان".

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

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

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

أكثر معلومات مفصلةحول مشكلة "الوديان" وأساليب "الأخدود" يمكن العثور عليها ، على سبيل المثال ، في ،.

3. مناهج أخرى لتحديد خطوة النسب.

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

طريقة Gauss-Seidel

تتكون الطريقة من إيجاد القيمة القصوى الجزئية للوظيفة الموضوعية بالتناوب لكل عامل. في نفس الوقت ، في كل مرحلة ، يتم تثبيت عوامل (k-1) ويختلف عامل واحد فقط

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

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

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

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

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

يتم تنفيذ طريقة التدرج (العادي) وفقًا للمخطط التالي:

أ) اختر نقطة أساسية ؛

ب) تحديد خطوات الحركة لكل عامل ؛

ج) تحديد إحداثيات نقاط الاختبار.

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

هـ) بناءً على نتائج التجارب ، يتم حساب تقديرات مكونات متجه التدرج في النقطة M لكل عامل من الدرجة الأولى:

حيث H i هي خطوة الحركة على طول X i.

X i - إحداثيات نقطة العمل السابقة.

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

مزايا الطريقة: البساطة ، سرعة الحركة الأعلى إلى الحد الأمثل.

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

أ) طريقة الصعود الحاد (Box-Wilson).

ب) اتخاذ القرار بعد صعود حاد.

ج) طريقة التحسين البسيط.

د) مزايا وعيوب الأساليب.

5.7.3 طريقة الصعود الحاد (Box-Wilson)

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

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

أين أنا ، ي ، ناقلات الوحدة كفي اتجاه محاور الإحداثيات المقابلة.

إجراء الحساب.

البيانات الأولية هي نموذج رياضي للعملية التي تم الحصول عليها بأي طريقة (PFE ، DFE ، إلخ).

يتم إجراء الحسابات بالترتيب التالي:

أ) من الأفضل ترجمة معادلة الانحدار إلى صيغة طبيعية باستخدام صيغ الترميز المتغيرة:

أين xقيمة ترميز i للمتغير x i ؛

X i - القيمة الطبيعية للمتغير x i ؛

X i C - المستوى المركزي للعامل في شكله الطبيعي ؛

l i - الفاصل الزمني لتغير العامل x i في الصورة الطبيعية.

ب) احسب خطوات الحركة إلى الحد الأمثل لكل عامل.

للقيام بذلك ، احسب نواتج معاملات معادلة الانحدار في الشكل الطبيعي بفواصل التباين المقابلة

ب i * .l أنا ,

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

يجب أن تتطابق علامة خطوة الحركة "أ" مع علامة معامل معادلة الانحدار المقابلة للعامل الأساسي (ب أ). يتم حساب قيمة الخطوات للعوامل الأخرى بما يتناسب مع العامل الأساسي وفقًا للصيغة:

يجب أن تتطابق علامات خطوات الحركة أيضًا مع علامات المعاملات المقابلة لمعادلة الانحدار.

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

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

يتم تكرار الإجراء ، مما يؤدي إلى زيادة عدد الخطوات على التوالي حتى الوصول إلى القيمة المرغوبة لمعلمة التحسين (Y). كل من العوامل بعد زالخطوات ستكون مهمة:

إذا كان Y®max X i \ u003d X i c + gl i ""

إذا كان Y® دقيقة. X i \ u003d X i c -gl i ``.(5.36)

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

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

أرز. 4.11.

أرز. 4.12.

(حالة ثنائية الأبعاد)

اختر أولاً نقطة البداية إذا كان ذلك ممكنًا في الحالة أحادية البعد (انظر القسم الفرعي 4.2.6)

تحرك فقط إلى اليسار أو اليمين (انظر الشكل 4.9) ، ثم في الحالة متعددة الأبعاد ، يكون عدد الاتجاهات الممكنة للحركة كبيرًا بشكل لا نهائي. على التين. 4.11 ، يوضح حالة متغيرين ، الأسهم الخارجة من نقطة البداية لكن،عرض مختلف الاتجاهات الممكنة. في الوقت نفسه ، يؤدي التحرك على طول بعضها إلى زيادة قيمة الوظيفة الهدف فيما يتعلق بالنقطة لكن(على سبيل المثال الاتجاهات 1-3), وفي اتجاهات أخرى يؤدي إلى انخفاضه (الاتجاهات 5-8). بالنظر إلى أن موضع النقطة المثلى غير معروف ، فإن الاتجاه الذي تزيد فيه الوظيفة الهدف بأسرع ما يكون هو الأفضل. هذا الاتجاه يسمى الانحدارالمهام. لاحظ ذلك في كل نقطة خطة تنسيقيكون اتجاه التدرج عموديًا على المماس لخط المستوى المرسوم عبر نفس النقطة.

في التحليل الرياضيثبت أن مكونات متجه التدرج للوظيفة في =/(*, × 2 ، ..., x ن)هي مشتقاتها الجزئية فيما يتعلق بالحجج ، أي

& إعلان / (x 1، x 2 ,.= (du / dhu، dy / dx 2، ...، dy / dx p). (4.20)

وبالتالي ، عند البحث عن الحد الأقصى باستخدام طريقة التدرج اللوني ، في التكرار الأول ، يتم حساب مكونات التدرج وفقًا للصيغ (4.20) لنقطة البداية ويتم اتخاذ خطوة العمل في الاتجاه الموجود ، أي يتم الانتقال إلى نقطة جديدة -0)

Y "بالإحداثيات:

1§gas1 / (x (0)) ،

أو في شكل ناقل

أين X-دائم أو معلمة متغيرة، الذي يحدد طول خطوة العمل ،؟ i> 0. في التكرار الثاني ، احسب مرة أخرى

متجه التدرج بالفعل لنقطة جديدة Y ، وبعد ذلك ، بشكل مماثل

الصيغة تذهب إلى النقطة x ^ > إلخ. (الشكل 4.12). عن التعسفي إلى-التكرار عشر لدينا

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

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

طول خطوة العمل هو المسافة بين النقطتين المتجاورتين x ^

1 "- سيكون متناسبًا مع معامل متجه التدرج. يمكنك ، على العكس من ذلك ، في كل تكرار اختيار Xبحيث يظل طول خطوة العمل ثابتًا.

مثال.مطلوب للعثور على الحد الأقصى للوظيفة

ص \ u003d 110-2 (lg ، -4) 2 -3 (* 2 -5) 2.

بالطبع ، باستخدام شرط ضروريأقصى حد ، نحصل على الفور على الحل المطلوب: X] - 4; × 2= 5. ومع ذلك ، على هذا مثال بسيطمن الملائم شرح خوارزمية طريقة التدرج. دعونا نحسب انحدار دالة الهدف:

غراد ص \ u003d (du / dx- ، dy / dx 2) \ u003d(4 (4 - * ،) ؛ 6 (5 - × 2)) وحدد نقطة البداية

أ * »= (س) °> = 0 ؛ 4 °> = O).

قيمة دالة الهدف لهذه النقطة ، كما يسهل حسابها ، تساوي ص [س ^ي = 3. دع X= const = 0.1. قيمة التدرج عند نقطة

3c (0) يساوي grad y | x ^ j = (16 ؛ 30). ثم في التكرار الأول ، وفقًا للصيغ (4.21) ، نحصل على إحداثيات النقطة

× 1)= 0 + 0.1 16 = 1.6 ؛ س ^ = 0 + 0.1 30 = 3.

ص (س (1)) \ u003d 110-2 (1.6 - 4) 2-3 (3-5) 2 \ u003d 86.48.

كما ترى ، فهي أكبر بكثير من القيمة السابقة. في التكرار الثاني ، لدينا بالصيغ (4.22):

• 1,6 + 0,1 4(4 - 1,6) = 2,56;