مقالات

13.8E: تحسين وظائف المتغيرات المتعددة (تمارين) - الرياضيات


13.8: تحسين وظائف عدة متغيرات

البحث عن النقاط الحرجة

في التمارين من 1 إلى 5 ، أوجد كل النقاط الحرجة.

1) (و (س ، ص) = 1 + س ^ 2 + ص ^ 2 )

إجابه:
( (0,0))

2) (و (س ، ص) = 1 - (س -2) ^ 2 + (ص + 3) ^ 2 )

3) (و (س ، ص) = (3 س − 2) ^ 2 + (ص − 4) ^ 2 )

إجابه:
( left ( frac {2} {3}، 4 right) )

4) (f (x، y) = x ^ 4 + y ^ 4−16xy )

إجابه:
((0،0) ، رباعي (-2 ، -2) ، رباعي (2،2) )

5) (f (x، y) = 15x ^ 3−3xy + 15y ^ 3 )

إجابه:
((0،0)، quad left ( frac {1} {15}، frac {1} {15} right) )

البحث عن Extrema واختبار الجزئيات الثاني

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

6) (f (x، y) = - sqrt {x ^ 2 + y ^ 2} )

إجابه:
كريت. نقاط: ((0 ، 0) )
Extrema: (f ) له حد أقصى نسبي (0 ) في ((0 ، 0) ).
لتبرير ذلك ، ضع في اعتبارك حقيقة أن دالة الجذر التربيعي لا يمكنها إعطاء قيمة سالبة ، لذلك لا يمكن لهذه الدالة أن تُرجع قيمة موجبة. نظرًا لأن قيمتها (0 ) عند النقطة الحرجة ((0 ، 0) ) ، فإننا نعلم أنها يجب أن تكون الوظيفة الحد الأقصى المطلق القيمة.

7) (و (س ، ص) = - س ^ 2−5 ص ^ 2 + 8 س − 10 ص − 13 )

إجابه:
كريت. نقاط: ((4، -1) )
Extrema: (f ) له حد أقصى نسبي (8 ) في ((4 ، −1) ).
لتبرير ذلك ، نكمل المربع في هذه الدالة ، مع الحرص على إخراج معامل الحدود قبل إكمال المربع.
[ start {align *} f (x، y) & = −x ^ 2−5y ^ 2 + 8x − 10y − 13 & = - (x ^ 2-8x quad quad) −5 (y ^ 2 + 2y quad quad) −13 & = - (x ^ 2-8x + 16) −5 (y ^ 2 + 2y + 1) −13 + 16 + 5 & = - (x- 4) ^ 2 -5 (ص + 1) ^ 2 + 8 نهاية {محاذاة *} ]
لاحظ أن هذه الدالة متعددة الحدود التربيعية تأخذ الشكل (z = - (x ^ 2 + y ^ 2) ) ، لذلك يمكننا أن نرى أنه سيكون لها نسبيا (وفي الواقع ، مطلق) أقصى عند قمته (النقطة الحرجة ((4 ، -1) )). يمكننا أيضًا أن نجادل بأنه نظرًا لأننا نطرح الحدود التربيعية من 8 ، فلا يمكننا الحصول على قيمة دالة أكبر من 8 ، وبما أننا نحصل على القيمة 8 عند النقطة الحرجة ((4 ، -1) ) ، فإننا تعرف أنها ستكون القيمة القصوى المطلقة لهذه الوظيفة.

8) (f (x، y) = x ^ 2 + y ^ 2 + 2x − 6y + 6 )

9) (f (x، y) = sqrt {x ^ 2 + y ^ 2} +1 )

إجابه:
كريت. نقاط: ((0، 0) )
Extrema: (f ) لديه حد أدنى نسبي من (1 ) في ((0،0) ).
لتبرير ذلك ، ضع في اعتبارك حقيقة أن دالة الجذر التربيعي لا يمكن أن تعطي قيمة سالبة ، لذلك لا يمكن لهذه الدالة أن ترجع قيمة أقل من (1 ). نظرًا لأن قيمتها (1 ) عند النقطة الحرجة ((0 ، 0) ) ، فإننا نعلم أن (1 ) يجب أن تكون الوظيفة الحد الأدنى المطلق القيمة.

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

10) (f (x، y) = - x ^ 3 + 4xy − 2y ^ 2 + 1 )

11) (و (س ، ص) = س ^ 2 ص ^ 2 )

إجابه:
كريت. نقاط: جميع النقاط على السطور (س = 0 ) و (ص = 0 ) هي نقاط حرجة لهذه الوظيفة.
Exrema: فشل اختبار الجزئيات الثاني.
نظرًا لأن (x ^ 2y ^ 2> 0 ) لكل (x ) و (y ) يختلفان عن الصفر ، و (x ^ 2y ^ 2 = 0 ) عندما يكون إما (x ) أو (y ) يساوي صفرًا (أو كليهما) ، ثم الحد الأدنى المطلق لـ (0 ) يحدث في جميع النقاط على (x ) - أو (y ) - المحاور ، أي لجميع النقاط على خطوط (س = 0 ) و (ص = 0 ).

12) (f (x، y) = x ^ 2−6x + y ^ 2 + 4y − 8 )

13) (و (س ، ص) = 2 س ص + 3 س + 4 ص )

إجابه:
كريت. النقاط: ( left (−2، - frac {3} {2} right) )
Exrema: (f ) بها نقطة سرج عند ( left (−2، - frac {3} {2}، - 6 right) ).

14) (و (س ، ص) = 8 س ص (س + ص) +7 )

15) (f (x، y) = x ^ 2 + 4xy + y ^ 2 )

إجابه:
كريت. نقاط: ((0،0) )
Exrema: (f ) بها نقطة سرج عند ((0،0،0) ).

16) (f (x، y) = x ^ 3 + y ^ 3−300x − 75y − 3 )

17) (f (x، y) = 9 ^ x ^ 4y ^ 4 )

إجابه:
كريت. نقاط: جميع النقاط على السطور (س = 0 ) و (ص = 0 ) هي نقاط حرجة لهذه الوظيفة.
Extrema: فشل اختبار الجزئيات الثاني.
نظرًا لأن المصطلح (-x ^ 4y ^ 4 <0 ) للجميع (x ) و (y ) يختلف عن الصفر ، و (-x ^ 4y ^ 4 = 0 ) عندما يكون إما (x ) أو (y ) يساوي صفرًا (أو كليهما) ، فلا يمكن لهذه الوظيفة أن تحقق قيمة أكبر من (9 ) في أي مكان ، ولكنها (9 ) عند النقاط الحرجة. وبالتالي (f ) لها حد أقصى مطلق (9 ) في جميع النقاط على (س ) - أو (ص ) - محاور ، أي لجميع النقاط على السطور (س = 0 ) و (ص = 0 ).

18) (و (س ، ص) = س ^ 2 + 10xy + ص ^ 2 )

إجابه:
كريت. نقاط: ((0،0) )
Extrema: (f ) لديه نقطة سرج عند ((0،0،0) ).

19) (و (س ، ص) = س ^ 4 + ص ^ 2 + 2 س ص + 3 )

إجابه:
كريت. نقاط: ((0،0)، quad left (- frac { sqrt {2}} {2}، frac { sqrt {2}} {2} right)، quad left ( frac { sqrt {2}} {2} ، - frac { sqrt {2}} {2} right) )
Extrema: (f ) لها نقطة سرج عند ((0 ، 0 ، 3) ) ،
(f ) لديه حد أدنى محلي من (2.75 ) عند النقطة ( left (- frac { sqrt {2}} {2} ، frac { sqrt {2}} {2} حق) ).
(f ) لديه حد أدنى محلي من (2.75 ) عند النقطة ( left ( frac { sqrt {2}} {2} ، - frac { sqrt {2}} {2} حق) ).

20) (و (س ، ص) = 7 س ^ 2 ص + 9 س ص ^ 2 )

21) (f (x، y) = 3x ^ 2−2xy + y ^ 2−8y )

إجابه:
كريت. نقاط: ((2،6) )
Extrema: يحتوي (f ) على حد أدنى نسبي من (-24 ) يقع في ((2،6) ).

22) (و (س ، ص) = 3 س ^ 2 + 2 س ص + ص ^ 2 )

23) (و (س ، ص) = ص ^ 2 + س ص + 3 ص + 2 س + 3 )

إجابه:
كريت. نقاط: ((1، −2) )
Extrema: (f ) لديه نقطة سرج عند ((1، −2،1) ).

24) (f (x، y) = x ^ 2 + xy + y ^ 2−3x )

25) (f (x، y) = x ^ 2 + 2y ^ 2 − x ^ 2y )

إجابه:
كريت. نقاط: ((0،0)، quad (-2،1)، quad (2،1) )
Extrema: (f ) لديه حد أدنى نسبي من (0 ) عند ((0،0) ) ونقاط السرج عند ((2،1،2) ) و ((2،1) ، 2) ).

26) (و (س ، ص) = س ^ 2 + ص − ه ^ ص )

27) (f (x، y) = e ^ {- (x ^ 2 + y ^ 2 + 2x)} )

إجابه:
كريت. نقاط: ((-1،0) )
Extrema: (f ) له حد أقصى نسبي (e ) يقع في ((-1،0) ).
انظر هذه المشكلة موضحة في CalcPlot3D.

28) (و (س ، ص) = س ^ 2 + س ص + ص ^ 2 − س − ص + 1 )

29) (و (س ، ص) = س ^ 2 ص (9 - س + ص) )

إجابه:
كريت. نقاط: ( left ( frac {9} {2} ، - frac {9} {4} right) ، quad (9،0) ) ، وجميع النقاط على السطر (x = 0 )
Extrema: (f ) بها نقطة سرج عند ((9،0،0) ) والحد الأدنى النسبي (- 102.515625 ) عند ( left ( frac {9} {2}، - frac {9} {4} right) ).
في النقاط الحرجة على الخط (x = 0 ) ، لا يحتوي (f ) على نقاط قصوى أو نقاط سرج نسبية ، لكنها تمثل نوعًا من قاع السطح.

30) (f (x، y) = - x ^ 2−5y ^ 2 + 10x − 30y − 62 )

31) (f (x، y) = 120x + 120y − xy − x ^ 2 − y ^ 2 )

إجابه:
كريت. نقاط: ((40،40) )
Extrema: (f ) له حد أقصى نسبي (4800 ) يقع في ((40،40) ).

32) (و (س ، ص) = 2 س ^ 2 + 2 س ص + ص ^ 2 + 2 س − 3 )

33) (f (x، y) = x ^ 2 + x − 3xy + y ^ 3−5 )

إجابه:
كريت. النقاط: ( left ( frac {1} {4}، frac {1} {2} right) ) و ((1، 1) )
Extrema: (f ) بها نقطة سرج عند ( left ( frac {1} {4} ، frac {1} {2} ، - frac {79} {16} right) ) و حد أدنى نسبي من (-5 ) عند ((1،1) ).

34) (f (x، y) = 2xye ^ {- x ^ 2 − y ^ 2} )

في التدريبات 35 - 37 ، حدد القيم القصوى ونقاط السرج. استخدم CAS لرسم الدالة.

35) [T] (f (x، y) = ye ^ x − e ^ y )

إجابه:

توجد نقطة السرج عند ((0،0، -1). )

36) [T] (f (x، y) = x sin (y) )

37) [T] (f (x، y) = sin (x) sin (y)، quad x∈ (0،2π)، quad y∈ (0،2π) )

إجابه:

توجد نقطة سرج عند ((π ، π) ، ) الحد الأقصى المحلي عند ( left ( frac {π} {2} ، frac {π} {2} right) ) و ( يسار ( frac {3π} {2} ، frac {3π} {2} right) ) ، والحد الأدنى المحلي عند ( left ( frac {π} {2} ، frac {3π} {2 } right) ) و ( left ( frac {3π} {2} ، frac {π} {2} right) ).

المساهمون

  • جيلبرت سترانج (معهد ماساتشوستس للتكنولوجيا) وإدوين "جيد" هيرمان (هارفي مود) مع العديد من المؤلفين المساهمين. هذا المحتوى من OpenStax مرخص بترخيص CC-BY-SA-NC 4.0. قم بالتنزيل مجانًا من http://cnx.org.

  • خلق بول سيبيرجر (كلية مجتمع مونرو) مشكلتين 19 و 29 ، وأضاف أرقامًا ديناميكية للمشكلتين 27 و 35.

13.8E: تحسين وظائف المتغيرات المتعددة (تمارين) - الرياضيات

أنت على وشك امسح عملك في هذا النشاط. هل انت متأكد من أنك تريد أن تفعل هذا؟

نسخة محدثة متوفرة

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

محرر التعبير الرياضي

يمكننا أن نرى الآن أن هذه المنطقة دالة في متغيرين ، و.

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

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

حتى نتمكن من الاستفادة من الهوية.

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

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


13.8E: تحسين وظائف المتغيرات المتعددة (تمارين) - الرياضيات

أنت على وشك امسح عملك في هذا النشاط. هل انت متأكد من أنك تريد أن تفعل هذا؟

نسخة محدثة متوفرة

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

محرر التعبير الرياضي

الآن نضع مهارات التحسين لدينا في العمل.

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

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

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

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

نحن نعمل الآن على حل مشكلة مماثلة بدون أرقام محددة.

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

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

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

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

مع مشاكل التحسين ، سترى مجموعة متنوعة من المواقف التي تتطلب منك الجمع بين مهارات حل المشكلات وحساب التفاضل والتكامل. ركز على عملية. يجب على المرء أن يتعلم كيفية تكوين المعادلات من المواقف التي يمكن التلاعب بها في ما تحتاجه. انسَ حفظ كيفية إجراء "هذا النوع من المشكلات & # x2019 & # x2019 بدلاً من" هذا النوع من المشكلات. & # x2019 & # x2019

إن تعلم عملية ما سيفيد المرء أكثر بكثير من حفظ أسلوب معين.


الطرق العددية للتصميم الأمثل المقيد

12.1.4 وظيفة النسب

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

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

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


13.8E: تحسين وظائف المتغيرات المتعددة (تمارين) - الرياضيات

يمكن لـ ga حل المشكلات عندما تكون بعض المتغيرات ذات قيمة صحيحة. أعط IntCon ، متجه لـ x المكونات التي هي أعداد صحيحة:

IntCon هو متجه للأعداد الصحيحة الموجبة التي تحتوي على x المكونات ذات القيمة الصحيحة. على سبيل المثال ، إذا كنت تريد تقييد x (2) و x (10) ليكونا عددًا صحيحًا ، فاضبط IntCon على [2،10].

يقبل محلل البدائل أيضًا قيود الأعداد الصحيحة.

توجد قيود على أنواع المشكلات التي يمكن لـ ga حلها باستخدام متغيرات عدد صحيح. على وجه الخصوص ، لا يقبل ga أي قيود مساواة عندما تكون هناك متغيرات عدد صحيح. للحصول على تفاصيل ، راجع خصائص Integer ga Solver.

يحل ga مشاكل الأعداد الصحيحة بشكل أفضل عندما تقدم الحدود الدنيا والعليا لكل منها x مكون.

تحسين عدد صحيح مختلط لوظيفة Rastrigin

يوضح هذا المثال كيفية العثور على الحد الأدنى من وظيفة Rastrigin المقيدة بحيث يكون المكون الأول من x هو عدد صحيح. مكونات x تقتصر أيضًا على أن تكون في المنطقة 5 ≤ x (1) ≤ 2 0 π ، - 2 0 π ≤ x (2) ≤ - 4 π.

ضع حدودًا لمشكلتك

قم بتعيين وظيفة الرسم حتى تتمكن من عرض تقدم ga

قم باستدعاء ga solver حيث يحتوي x (1) على قيم عدد صحيح

ga يتقارب بسرعة إلى الحل.

خصائص Integer ga Solver

توجد بعض القيود على أنواع المشكلات التي يمكن لـ ga حلها عند تضمين قيود عدد صحيح:

لا توجد قيود مساواة خطية. يجب أن يكون لديك Aeq = [] و beq = []. للحصول على حل بديل محتمل ، راجع بلا قيود المساواة.

لا توجد قيود المساواة غير الخطية. يجب أن ترجع أي دالة قيد غير خطية [] لقيد المساواة غير الخطية. للحصول على حل بديل محتمل ، راجع مثال: البرمجة الصحيحة بقيد المساواة غير الخطي.

فقط نوع مزدوج فيكتور.

لا توجد وظيفة إنشاء مخصصة (خيار CreationFcn) ، أو وظيفة التقاطع (خيار CrossoverFcn) ، أو وظيفة الطفرة (خيار MutationFcn) أو الدرجات الأولية (خيار InitialScoreMatrix). إذا قمت بتوفير أي من هذه ، فإن ga يتجاوز إعداداتها.

يستخدم ga وظيفة اختيار الدورة الثنائية فقط (خيار SelectionFcn) ، ويتخطى أي إعداد آخر.

لا توجد وظيفة هجينة. يتجاوز ga أي إعداد لخيار HybridFcn.

يتجاهل ga خيارات ParetoFraction و DistanceMeasureFcn و InitialPenalty و PenaltyFactor.

القيود المذكورة طبيعية بشكل أساسي وليست تعسفية. على سبيل المثال:

لا توجد وظائف هجينة تدعم قيود الأعداد الصحيحة. لذلك لا تستخدم ga الدوال المختلطة عندما تكون هناك قيود عدد صحيح.

للحصول على متغيرات عدد صحيح ، يستخدم ga وظائف إنشاء وتقاطع وطفرة خاصة.

لا قيود المساواة

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

إنشاء اثنين من قيود عدم المساواة:

لكتابة هذه القيود بالصيغة A x ≤ b ، اضرب المتباينة الثانية في -1:

يمكنك محاولة تضمين قيد المساواة باستخدام A = [3، -2-3،2] و b = [5-5].

كن على علم بأن هذا الإجراء يمكن أن يفشل.

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

x (1) و x (3) و x (5) هي أعداد صحيحة.

من الصعب تصغير وظيفة Ackley. إضافة قيود صحيحة والمساواة يزيد من صعوبة.

لتضمين قيود المساواة غير الخطية ، قم بإعطاء قيمة تسامح صغيرة تسمح لقاعدة x أن تكون ضمن tol من 4. بدون التسامح ، لا يتم استيفاء قيود المساواة غير الخطية أبدًا ، ولا يدرك المحلل عندما يكون لديه حل ممكن.

اكتب التعبير المعياري (س) = 4 كمتراجحتين "أقل من صفر":

السماح بتسامح بسيط في عدم المساواة:

القاعدة (x) - 4 - tol ≤ 0
- (القاعدة (x) - 4) - tol 0.

اكتب دالة قيد عدم المساواة غير الخطية التي تنفذ هذه التفاوتات:

MaxStallGenerations = 50 & # 8212 اسمح للحل بالمحاولة لفترة من الوقت.

FunctionTolerance = 1e-10 & # 8212 حدد معيار إيقاف أكثر صرامة من المعتاد.

MaxGenerations = 300 & # 8212 السماح بأجيال أكثر من الافتراضي.

PlotFcn =gaplotbestfun & # 8212 مراقبة التحسين.

عيّن الحدود الدنيا والعليا لمساعدة المحلل:

مكونات odd x هي أعداد صحيحة ، كما هو محدد. معيار x هو 4 ، ضمن التسامح النسبي المحدد لـ 1e-3.

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

افحص الحل الثاني:

يعطي التشغيل الثاني حلاً أفضل (قيمة دالة لياقة أقل). مرة أخرى ، مكونات odd x هي أعداد صحيحة ، وقاعدة x2 هي 4 ، ضمن التسامح النسبي المحدد لـ 1e-3.

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

عدد صحيح فعال ga

لاستخدام ga بشكل أكثر فاعلية في مشاكل الأعداد الصحيحة ، اتبع هذه الإرشادات.

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

إذا لم تتمكن من ربط مكون ، فحدد نطاقًا أوليًا مناسبًا. بشكل افتراضي ، يُنشئ ga مجتمعًا أوليًا بنطاق [-1e4،1e4] لكل مكون. يمكن أن يعطي النطاق الأولي الأصغر أو الأكبر نتائج أفضل عندما تكون القيمة الافتراضية غير مناسبة. لتغيير النطاق الأولي ، استخدم خيار InitialPopulationRange.

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

يمكن أن تستغرق ga وقتًا طويلاً لتتقارب. إذا وصلت إلى الحد الأقصى لعدد الأجيال (علامة الخروج 0) ، فقم بزيادة قيمة خيار MaxGenerations.

تقليل معدل الطفرات. للقيام بذلك ، قم بزيادة قيمة خيار CrossoverFraction من القيمة الافتراضية 0.8 إلى 0.9 أو أعلى.

قم بزيادة قيمة خيار EliteCount من القيمة الافتراضية 0.05 * عدد السكان إلى 0.1 * حجم السكان أو أعلى.

للحصول على معلومات حول الخيارات ، راجع وسيطة إدخال خيارات ga.

خوارزمية الجا الصحيح

تتضمن البرمجة الصحيحة باستخدام ga العديد من التعديلات على الخوارزمية الأساسية (انظر كيف تعمل الخوارزمية الجينية). لبرمجة عدد صحيح:

تفرض وظائف الإنشاء والتقاطع والطفرة الخاصة أن تكون المتغيرات أعدادًا صحيحة. للحصول على التفاصيل ، انظر Deep et al. [2].

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

إذا كان العضو ممكنًا ، فإن وظيفة العقوبة هي وظيفة اللياقة.

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

للحصول على تفاصيل وظيفة الجزاء ، انظر Deb [1].

لا تفرض ga قيودًا خطية عند وجود قيود عدد صحيح. بدلاً من ذلك ، يدمج ga انتهاكات القيد الخطية في وظيفة العقوبة.


مشاكل

المشكلة 1
أوجد رقمين موجبين مثل حاصل ضربهما 10 ومجموعهما هو الأدنى. تحقق من إجابتك بيانيا.

حل المشاكل 1
لنفترض أن (x ) هو الرقم الأول و (y ) هو الرقم الثاني ، بحيث يكون (x gt 0 ) و (y gt 0 ) و (S ) مجموع رقمين.
المجموع: (S = x + y ) ، الكمية المطلوب تحسينها لها متغيرين
المنتج: (x cdot y = 10 ) ، بالنظر إلى العلاقة بين المتغيرين
حل ما ورد أعلاه من أجل (ص )
(y = dfrac <10> )
استبدل (y ) بـ ( dfrac <10> ) في المجموع
(S (x) = x + dfrac <10> = dfrac ) بالمجال (x gt 0 ) ، تحتوي الكمية المراد تحسينها على متغير واحد فقط
أوجد المشتق الأول لـ (S )
(S '(x) = dfrac )
أصفار المشتق
(x = sqrt <10> ) و (x = - sqrt <10> ) ، أصفار المشتق الأول هي نقاط حرجة
حدد (x ) إيجابي: (x = sqrt <10> ) هي نقطة جوهرية لـ (S ) ، حدد النقاط الحرجة في المجال
لا يحتوي مجال (S ) على نقاط نهاية وبالتالي قد يحتوي (S ) على حد أدنى عند النقطة الحرجة.
احسب المشتق الثاني لـ (S )
(S '(x) = dfrac <20> ) ، تعطي علامة المشتق الثاني التقعر الذي يخبر بدوره ما إذا كان لدينا حد أدنى أو أقصى
بما أن (x gt 0 ) ، (S '( sqrt <10>) ) موجب (مقعر) مما يؤكد أن (S ) به حد أدنى عند (x = sqrt <10 > )
الرقمان الموجبان (x ) و (y ) الذي يساوي حاصل ضربهما 10 ومجموعهما هو الأدنى:
(x = sqrt <10> حوالي 3.16 ) و (y = dfrac <10> < sqrt <10>> = sqrt <10> حوالي 3.16 )
الرسم البياني أدناه هو الكمية المطلوب تحسينها (S = x + dfrac <10> ) التي لها قيمة دنيا عند (x حوالي 3.16 )


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

حل المشاكل 2
لنفترض أن (x ) هو الرقم الأول و (y ) هو الرقم الثاني و (P ) منتج الرقمين.
(P = x cdot y )
(6 س + 2 ص = 150 ) معطى
حل ما ورد أعلاه من أجل (ص )
(ص = 75-3 س )
استبدل (y ) بـ (75-3 x ) في (P )
(P (x) = x cdot (75-3 x) = 75 x - 3 x ^ 2 )
المشتق الأول من (P )
(الفوسفور (س) = 75-6 س )
مشتق صفر
(س = 75/6 = 25/2 )
المشتق الثاني من (P )
(P '' (x) = - 6 ) ، المشتق الثاني سلبي ، تقعر لأسفل ، مما يؤكد أن (P ) له حد أقصى عند (x = 25/2 )
(y = 75-3 x = 75-3 dfrac <25> <2> = dfrac <75> <2> )

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

حل المشاكل 3
ارسم صورة بحيث يكون (L ) هو الطول و (W ) عرض كل مستطيل والعرض هو الجانب الشائع.

المساحة الإجمالية للمستطيلين هي: (A = 2 L cdot W )
الطول الإجمالي للمبارزة: (4 لتر + 3 واط = 180 ) (المعادلة 1)
حل المعادلة أعلاه من أجل (W )
(W = 60 - dfrac <4> <3> لتر )
استبدل (W ) بـ (60 - dfrac <4> <3> L ) في صيغة المنطقة (A )
(A (L) = 2 L (60 - dfrac <4> <3> L) = - dfrac <8> <3> L ^ 2 + 120 L )
هناك عدة طرق للعثور على مجال (A ). دعونا نستخدم طريقة رسومية.
نرسم الرسم البياني للمعادلة الخطية (4 L + 3 W = 180 ) كما هو موضح أدناه ونحدد نطاق القيم التي يأخذها (L ).


من الرسم البياني لدينا
أصغر قيمة لـ (L ) هي صفر
أكبر قيمة لـ (L ) هي 45
ومن ثم يُعطى مجال (A ) بالفاصل الزمني: (L in [0، 45] )
احسب المشتق الأول لـ (A ) بالنسبة لـ (L )
(A '(L) = - dfrac <16> <3> L + 120 )
أوجد أصفار (A ')
(- dfrac <16> <3> L + 120 = 0 )
حل المعادلة أعلاه من أجل (L )
(L = 22.5 )
قم بتقييم (A ) عند النقطة الحرجة ونقاط النهاية.
(A (22.5) = - dfrac <8> <3> (22.5) ^ 2 + 120 (22.5) = 1350 )
(أ (0) = 0 )
(A (45) = - dfrac <8> <3> (45) ^ 2 + 120 (45) = 0 )
(A (L) ) له حد أقصى مطلق لـ (L = 22.5 ) متر
و (W = 60 - dfrac <4> <3> (22.5) = 30 ) متر
أبعاد كل مستطيل هي: (22.5 ) في (30 )

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

حل المشاكل 4
دع (س ) يكون طول القطعة الأولى لعمل مربع و (ص ) القطعة الثانية لعمل دائرة. (x ) و (y ) هما محيط ومحيط المربع والدائرة على التوالي.


(س + ص = 100 ) (المعادلة 1)
لنكن جانب المربع. نظرًا لأن (x ) هو محيط المربع ، نكتب
(س = 4 ثانية )
ومن ثم يتم إعطاء جانب (s ) المربع بواسطة
(s = dfrac <4>)
دعونا (r ) نصف قطر الدائرة. بما أن (y ) هو محيط الدائرة ، فإننا نكتب
(ص = 2 بي r )
ومن ثم يتم إعطاء نصف قطر (r ) الدائرة بواسطة
(r = dfrac <2 بي> )
دع (A ) هي المساحة الإجمالية التي يحيط بها المربع والدائرة
(A = s ^ 2 + pi r ^ 2 )
استبدل (s ) و (r ) بتعبيراتهما أعلاه
(A = يسار ( dfrac <4> right) ^ 2 + pi left ( dfrac <2 pi> right) ^ 2 )
تبسيط
(A = dfrac <16> + dfrac <4 بي> )
حل المعادلة 1 من أجل (y )
(ص = 100 - س )
استبدل (y ) بـ (100 - x ) في (A ) أعلاه
(A (x) = dfrac <16> + dfrac <(100-x) ^ 2> <4 pi> )
نظريًا (x ) يمكن أن يأخذ القيم من صفر إلى (100 ) ومن ثم يتم إعطاء مجال (A ) من خلال الفاصل الزمني: (x in [0،100] )
حساب المشتق الأول من (أ )
(A '= dfrac<8> - dfrac <1> <2 pi> (100-x) )
أوجد أصفار (A ')
( dfrac<8> - dfrac <1> <2 pi> (100-x) = 0 )
حل ل x )
(x = dfrac <400> < pi +4> حوالي 56 ) متر
قم بتقييم (A ) عند النقاط الحرجة ونقاط النهاية
(A (56) = dfrac <56 ^ 2> <16> + dfrac <(100-56) ^ 2> <4 pi> = 350 )
(A (0) = dfrac <0 ^ 2> <16> + dfrac <(100-0) ^ 2> <4 pi> = 795 )

(A (100) = dfrac <100 ^ 2> <16> + dfrac <(100-100) ^ 2> <4 pi> = 625 )
المساحة الإجمالية (أ ) هي الأصغر (الحد الأدنى) عند (س = 56 )
نستخدم الآن المعادلة 1 لإيجاد (y )
(ص = 100 - س = 44 ) متر

المشكلة 5
مربع بنهايات مربعة من الضلع (س ) وطول (ل ) يجب أن يصنع بحيث (L + 4 x = 4 ) متر. أوجد أبعاد الصندوق التي تعطي الحجم الأكبر.

حل المشاكل 5
مساحة الطرف المربع للضلع (x ) هي (x ^ 2 )
حجم (V ) المربع.
(ع = س ^ 2 لتر )
حل المعادلة المعطاة (L + 4 x = 4 ) من أجل (L )
(لتر = 4-4 س )
عوّض (L ) بـ (4-4 x ) في تعبير المجلد
(V (x) = x ^ 2 (4 - 4x) )
أصغر قيمة نظرية لـ (س ) هي صفر. يتم الحصول على أكبر قيمة لـ (x ) عن طريق ضبط (L = 0 ) في المعادلة المعطاة (L + 4 x = 4 ). ومن ثم فإن أكبر قيمة لـ (س ) هي (1 ).
يتم إعطاء مجال (V ) من خلال الفاصل الزمني المغلق: (x in [0،1] )
حساب المشتق الأول من (V )
(V '(x) = 8x-12x ^ 2 )
أوجد أصفار (V ')
(8 س - 12 س ^ 2 = 0 )
النقاط الحرجة هي حلول للمعادلة أعلاه: (x = 0 ) و (x = dfrac <2> <3> ) وكلاهما ضمن المجال
تقييم (V ) عند النقاط الحرجة ونقاط النهاية.
(V (0) = 0 ^ 2 (4 - 4 (0)) = 0 )
(V (2/3) = (2/3) ^ 2 (4-4 (2/3)) = 16/27 )
(V (1) = (1) ^ 2 (4-4 (1)) = 0 )
يتم الحصول على أكبر حجم من أجل (س = 2/3 )
نستخدم الآن معادلة معينة لإيجاد (L )
(L = 4-4 × = 4/3 ) أمتار

المشكلة 6
تبلغ التكلفة الإجمالية ، بما في ذلك تصنيع الآلة الحاسبة الإلكترونية وتعبئتها وتوزيعها 21 دولارًا. إذا كان الجهاز يباع بسعر (x ) دولار لكل منهما ، فإن عدد (n ) الأجهزة المباعة هو [n = dfrac <200> + 10 (50-x) ] ما هو سعر البيع (x ) الذي سيزيد من الربح؟ (تلميح: الربح = إجمالي الإيرادات لأجهزة (n ) - التكلفة الإجمالية للأجهزة (n ))

حل المشاكل 6
لنفترض أن (R_t ) هو إجمالي الإيرادات من بيع (n ) الأجهزة التي يتم تقديمها بواسطة
(R_t = n x )
لنفترض أن (C_t ) هي التكلفة الإجمالية لتصنيع وتغليف وتوزيع (n ) الأجهزة التي يتم تقديمها بواسطة
(C_t = 21 n )
يتم إعطاء الربح (P ) لأجهزة (n ) بواسطة
(P = R_T - C_T = n x - 21 n = n (x - 21) )
استبدل (n ) بالتعبير الوارد أعلاه واكتب
(P = يسار ( dfrac <200> + 10 (50-س) يمين) (س - 21) )
تبسيط
(P (x) = 200 + 10 (50-x) (x - 21) = -10x ^ 2 + 710x-10300 )
مجال (P ) هو: (x in (0، infty) ) لأنه إذا كان سعر البيع (x ) أصغر من أو يساوي تكلفة 21 دولارًا ، فلا يوجد ربح على الإطلاق وليس هناك حد أعلى لسعر البيع.
حساب المشتق الأول من (P )
(ف '(س) = -20 س + 710 )
أوجد أصفار (V ')
(- 20x + 710 = 0 )
(س = 35.5 )
نظرًا لعدم وجود نقاط نهاية ، نستخدم المشتق الثاني لتأكيد أن الربح الأقصى عند (x = 35.5 ).
احسب المشتق الثاني لـ (V )
(ف '(س) = -20 )
المشتق الثاني سلبي (مقعر لأسفل) ويؤكد أن الربح (P ) هو الحد الأقصى لسعر البيع (س = 35.5 )

المشكلة 7
ما هي أبعاد المستطيل ذي المساحة الأكبر التي يمكن نقشها تحت قوس المنحنى (y = dfrac <1>) والمحور x؟

حل المشاكل 7
لنفترض (x ) أن يكون نصف طول المستطيل. رأس المستطيل يقع على المنحنى ، وبالتالي فإن إحداثي y يساوي ( dfrac <1>).


عرض المستطيل يساوي إحداثي y للرأس الأيمن العلوي كما هو موضح في الرسم البياني أعلاه. ومن ثم يتم إعطاء مساحة المستطيل (A ) بواسطة
(A (x) = 2 x cdot dfrac <1> )
يتم إعطاء مجال (A ) من خلال الفاصل الزمني: (x in [0، infty) )
حساب المشتق الأول من (أ )
(A '(x) = dfrac <2 (x ^ 2 + 1) -2x (2x)> << left (x ^ 2 + 1 right) ^ 2 >> = dfrac <2 left ( 1 -x ^ 2 right)> < left (x ^ 2 + 1 right) ^ 2> )
أوجد أصفار (A ')
(1-س ^ 2 = 0 )
حلين: (س = 1 ) و (س = - 1 )
(س ) أكبر من أو يساوي الصفر ، لذلك نختار النقطة الحرجة (س = 1 )
احسب المشتق الثاني لـ (A )
(A '' (x) = - dfrac <4x (-x ^ 2 + 3)> <(x ^ 2 + 1) ^ 3> )
احسب قيمة (A '' ) لـ (x = 1 )
(أ '' (1) = - 1 )
(A '' (1) ) سلبي (مقعر لأسفل) وبالتالي (A ) يكون الحد الأقصى عند (x = 1 ).
أبعاد المستطيل مع أكبر مساحة هي
الطول = (2 × = 2 (1) = 2 )
العرض = ( dfrac <1> <1 ^ 2 + 1> = dfrac <1> <2> )

المشكلة 8
ما أبعاد المستطيل الذي يحتوي على أكبر مساحة يمكن كتابتها في المثلث القائم الزاوية بارتفاع 4 والوتر 5؟

حل المشاكل 8
رسم تخطيطي لهذه المشكلة ضروري.


تُعطى مساحة المستطيل بواسطة
(A = ح cdot ث )
نحتاج الآن إلى إيجاد علاقة بين (ح ) و (ث ).
نستخدم أولًا نظرية فيثاغورس لإيجاد القاعدة BC للمثلث القائم الزاوية
(BC = sqrt <5 ^ 2 - 4 ^ 2> = 3 )
Triangles AEF and ABC are similar, hence the equality of the ratios
( dfrac = dfrac )
( AE = 4 - h) , ( EF = w ) , ( AB = 4 ) and ( BC = 3 )
استبدل
( dfrac<4-h> = dfrac<4> <3>)
( h = - dfrac<4> <3>w + 4 )
Substitute ( h ) by the above expression in the area ( A )
( A = (- dfrac<4> <3>w + 4) w = - dfrac<4> <3>w^2 + 4w )
Domain of ( A ) is given by: ( w in [0 , 3] )
Calculate first derivative of ( A )
( A '(w) = - dfrac<8> <3>w + 4 )
Find Zeros of ( A' )
(- dfrac<8> <3>w + 4 = 0 )
critical point, solution of the above equation: ( w = dfrac<3> <2>)
Evaluate ( A ) at the critical point and the endpoint of the domain
( A(3/2) = 3)
( A(0) = 0 )
( A(3) = 0 )
The rectangle has a maximum area for ( w = 3/2 )
The dimensions of the rectangle with maximum area are
( w = x = dfrac<3> <2>)
( h = - dfrac<4> <3>w + 4 = - dfrac<4> <3>dfrac<3> <2>+ 4 = 2)

Problem 9
Show analytically that the function ( f(x) = - 5 - 4 cos(x) + cos(2x) , ext 0 le x le 2pi ) is never positive.

Solution to Problems 9
One way to answer this question is to show that the maximum value of function ( f ) is not positive.
Calculate first derivative of ( f )
( f '(x) = 4 sin(x) - 2 sin(2x) )
Use the identity ( sin(2x) = 2 sin(x) cos(x) ) to rewrite the derivative in factored form as
( f '(x) = 4 sin(x) - 2 sin(2x) = 4 sin(x) - 4 sin(x) cos(x) = 4 sin(x) (1 - cos(x) ) )
( sin(x) = 0 ) gives three solutions within the domain ( [0 , 2pi] )
( x = 0 ) , ( x = pi ) and ( x = 2 pi )
( 1 - cos(x) = 0 ) which is equivalent to ( cos(x) = 1 )
has two solutions within the domain ( [0 , 2pi] )
( x = 0 ) and ( x = 2pi )
We now determine the absolute maximum value of ( f ) at all the zeros of the first derivative and the endpoints
( f(0) = - 5 - 4 cos(0) + cos(2(0)) = - 8 )
( f(2pi) = - 5 - 4 cos(2pi) + cos(2(2pi)) = - 8 )
( f(pi) = - 5 - 4 cos(pi) + cos(2(pi)) = 0)
The maximum value of ( f(x) ) is equal to zero and therefore ( f(x) ) is never negative.

Problem 10
Find the radius ( r ) of the base of a cone and its altitude ( h ) such that the slant height is ( 5 ) cm and its volume is the largest.



The volume of a cone of radius ( r ) and altitude ( h ) is given by
( V = dfrac<1> <3>pi r^2 h )
Using the Pythagorean theorem, we can write
( h^2 + r^2 = 5^2 )
Solve the above for ( h )
( h = sqrt <25 - r^2>)
Substitute ( h ) in the volume ( V )
(V(r) = dfrac<1> <3>pi r^2 sqrt <25 - r^2>)
The domain of ( V ) is given by: ( r in [0,5] )

Calculate first derivative of ( V )
( V '(r) = dfrac <3>(2r sqrt <25 - r^2>+ r^2 (dfrac<1><2>) (-2r) (25 - r^2)^ <-1/2>) = dfrac <3>dfrac<(50r-3r^3)>>)
Find Zeros of ( A' )
(50 r -3r^3 = 0 )
عامل
(r(50 - 3 r^2) = 0 )
The above equation has three solutions: ( r = 0 ) , ( r = sqrt<3>> approx 4.08 ) and ( r = - sqrt<3>> approx - 4.08).
( r = - sqrt<3>> ) is not in the domain and therefore there are three critical points:
Function ( V ) has 3 critical points: ( r = 0 ) , ( r = sqrt<3>> ) and ( r = 5 )
( r = 0 ) and ( r = sqrt<3>> ) make ( V' = 0 )
and ( r = 5 ) is a value that makes the denominator of ( V' ) equal to zero and therefore the derivative ( V' ) is undefined.

Evaluate ( V ) at the critical points and the endpoints.
(V(sqrt<3>>) = dfrac<1> <3>pi (sqrt<3>>)^2 sqrt<25 - (sqrt<3>>)^2> approx 50.38)

( r = sqrt<3>> approx 4.08 ) is the radius that gives a maximum volume.

Substitute ( r ) by its numerical value to obtain

Problem 11
Find the point on the line given by ( y = 4 - x ) that is closest to the point ( (6 , 3) )

Solution to Problems 11
We first need to understand that by "closest" it is meant the smallest distance.
Any point ( M ) on the line ( y = 4 - x ) has coordinates ( (x , 4 - x) )


The distance D between point ( (6 , 3) ) and point M is given by
( D = sqrt < (x - 6)^2 + (4 - x - 3)^2>= sqrt < (x - 6)^2 + (1 - x)^2>)
The domain of ( D ) is given by: ( x in (-infty,infty) )
We are looking for point ( M ) that is closest to point ( (6 , 3) ) and therefore we are looking for the smallest (minimum) distance ( D ) between these two points.

Calculate first derivative of distance ( D )
( D ' = dfrac<1> <2>dfrac<(4x-14)><(2x^2-14x+37)^<1/2>> )
Find Zeros of ( D' )
(4x-14 = 0 )
Solution of the above equation is ( x = dfrac<7><2>) which a critical point of (D)
We do not need to find the second derivative because the sigh of the first derivative is easy to obtain. The denominator is a square root and therefore positive. Hence the sign of the first derivative is the same as the sign of the numerator ( 4x-14 ).
For ( x < 14/4 ) , ( D' ) is negative and for ( x > 14/4 ) , ( D' ) is positive and therefore distance ( D ) has a minimum at ( x = 14/4 = 7/2)
The y coordinate is given by
( y = 4 - x = 4 - 14/4 = 1/2 )
the point on the line ( y = 4 - x ) that is closest to the point ( (6 , 3) ) has the coordinates ( (7/2 , 1/2) )

Problem 12
A company is to build a pipeline from point A offshore (in the ocean) to point B along the coastline. The cost of the pipeline to be built along the coastline is ( k ) dollars per kilometer and the cost of the pipeline offshore is ( 3 k ) dollars, where ( k ) is constant. Find the distances of the pipeline offshore from A to D and along the coast from D to B so that the total cost of the pipeline from A to B is the lowest.


Solution to Problems 12
Let ( x ) be the distance from D to B (along the coastline) and ( y ) be the distance from A to D (offshore) that we need to find.
Use Pythagorean theorem in triangle ACB to find the distance from C to B.
( CB = sqrt <50^2 - 30^2>= 40 ) km
Distance from C to D is equal to ( CB - x = 40 - x )
Use the Pythagorean theorem in triangle ACD to write
( y = sqrt <30^2 + (40 - x)^2>)
The total cost C of the pipeline is given by
( C_t(x) = k x + 3 k y = k x + 3 k sqrt <30^2 + (40 - x)^2>)
( x ) can take values from 0 to 40. Hence the domain of ( C_t ) is given by the interval: ( x in [0,40] )

Find the derivative of ( C_t )
( C_t '(x) = k - 3 k (1/2)(2)(40 - x) (30^2 + (40 - x)^2)^ <-1/2>= k dfrac<(30^2 + (40 - x)^2)^<1/2>-3(40-x)><(30^2 + (40 - x)^2)^<1/2>> )
Find the zeros of ( C_t ' ) , k is a constant not equal to zero.
( (30^2 + (40 - x)^2)^<1/2>-3(40-x) = 0 )
( (30^2 + (40 - x)^2)^ <1/2>= 3(40-x) )
Square both sides
( left((30^2 + (40 - x)^2)^<1/2> ight)^2 = (3(40-x))^2 )
( 30^2 + (40 - x)^2 = 9x^2-720x+14400 )
( -8x^2+640x-11900 = 0 )
The above quadratic equation has two solutions but one of them is an extraneous solution. The only valid solution to the original equation ( C'_t(x) = 0 ) is
( x = dfrac<(80-15sqrt<2>)> <2>approx 29.40 )
which is a critical point within the domain.

Evaluate ( C_t ) for the two endpoints and the critical point
( C_t(0) = 150 k )
( C_t(40) = 130 k )
( C_t(29.40) = 124.85 k )
Hence ( x = 29.40 ) km gives the lowest total cost.
( y ) is given by
( y = sqrt <30^2 + (40 - 29.40)^2>= 31.81 ) km

Problem 13
Show that if ( x + y = K ) , where ( K ) is a constant, then ( x cdot y le left(dfrac <2> ight)^2 ).
( x , y ) and ( K ) are real numbers.

Solution to Problems 13
We need to show that the maximum of the product ( x cdot y ) is less than or equal to ( left(dfrac <2> ight)^2 )
Express ( y ) in terms of ( x )
( y = K - x )
يترك
( P(x) = x cdot y = x(K-x) = - x^2 + x K)
The domain of ( P ) is given by the interval: ( x in (-infty , infty) )
First derivative of ( P ), remember ( K ) is a constant
( P'(x) = -2x + K )
Find zeros of ( P' )
( -2x + K = 0 )
Solve for ( x )
( x = K/2 )
Find second derivative
( P''(x) = -2)
The second derivative is negative (concave down) , hence ( P ) has a maximum at ( x = K/2 )
Find ( y )
( y = K - x = K - K/2 = K/2 )
The maximum value of ( P ) is given by
( P(K/2) = x cdot y = dfrac <2>cdot dfrac <2>= left(dfrac <2> ight)^2 )
Hence ( P = x cdot y le left(dfrac <2> ight)^2 )


11.1.1. Goal of Optimization¶

Although optimization provides a way to minimize the loss function for deep learning, in essence, the goals of optimization and deep learning are fundamentally different. The former is primarily concerned with minimizing an objective whereas the latter is concerned with finding a suitable model, given a finite amount of data. In Section 4.4 , we discussed the difference between these two goals in detail. For instance, training error and generalization error generally differ: since the objective function of the optimization algorithm is usually a loss function based on the training dataset, the goal of optimization is to reduce the training error. However, the goal of deep learning (or more broadly, statistical inference) is to reduce the generalization error. To accomplish the latter we need to pay attention to overfitting in addition to using the optimization algorithm to reduce the training error.


محتويات

Applications for combinatorial optimization include, but are not limited to:

    [3][4]
  • Developing the best airline network of spokes and destinations
  • Deciding which taxis in a fleet to route to pick up fares
  • Determining the optimal way to deliver packages
  • Working out the best allocation of jobs to people
  • Designing water distribution networks problems (e.g. reservoir flow-rates) [5]

There is a large amount of literature on polynomial-time algorithms for certain special classes of discrete optimization, a considerable amount of it unified by the theory of linear programming. Some examples of combinatorial optimization problems that fall into this framework are shortest paths and shortest-path trees, flows and circulations, spanning trees, matching, and matroid problems.

For NP-complete discrete optimization problems, current research literature includes the following topics:

  • polynomial-time exactly solvable special cases of the problem at hand (e.g. see fixed-parameter tractable)
  • algorithms that perform well on "random" instances (e.g. for traveling salesman problem) that run in polynomial time and find a solution that is "close" to optimal
  • solving real-world instances that arise in practice and do not necessarily exhibit the worst-case behavior inherent in NP-complete problems (e.g. TSP instances with tens of thousands of nodes [6] ).

Combinatorial optimization problems can be viewed as searching for the best element of some set of discrete items therefore, in principle, any sort of search algorithm or metaheuristic can be used to solve them. Perhaps the most universally applicable approaches are branch-and-bound (an exact algorithm which can be stopped at any point in time to serve as heuristic), branch-and-cut (uses linear optimisation to generate bounds), dynamic programming (a recursive solution construction with limited search window) and tabu search (a greedy-type swapping algorithm). However, generic search algorithms are not guaranteed to find an optimal solution first, nor are they guaranteed to run quickly (in polynomial time). Since some discrete optimization problems are NP-complete, such as the traveling salesman problem [ بحاجة لمصدر ] , this is expected unless P=NP.

In the field of approximation algorithms, algorithms are designed to find near-optimal solutions to hard problems. The usual decision version is then an inadequate definition of the problem since it only specifies acceptable solutions. Even though we could introduce suitable decision problems, the problem is more naturally characterized as an optimization problem. [7]

ان NP-optimization problem (NPO) is a combinatorial optimization problem with the following additional conditions. [8] Note that the below referred polynomials are functions of the size of the respective functions' inputs, not the size of some implicit set of input instances.

  • the size of every feasible solution y ∈ f ( x ) is polynomially bounded in the size of the given instance x ,
  • the languages < x ∣ x ∈ I >> and < ( x , y ) ∣ y ∈ f ( x ) >> can be recognized in polynomial time, and
  • m is polynomial-time computable.

This implies that the corresponding decision problem is in NP. In computer science, interesting optimization problems usually have the above properties and are therefore NPO problems. A problem is additionally called a P-optimization (PO) problem, if there exists an algorithm which finds optimal solutions in polynomial time. Often, when dealing with the class NPO, one is interested in optimization problems for which the decision versions are NP-complete. Note that hardness relations are always with respect to some reduction. Due to the connection between approximation algorithms and computational optimization problems, reductions which preserve approximation in some respect are for this subject preferred than the usual Turing and Karp reductions. An example of such a reduction would be the L-reduction. For this reason, optimization problems with NP-complete decision versions are not necessarily called NPO-complete. [9]

NPO is divided into the following subclasses according to their approximability: [8]


Linear programming

Although widely used now to solve everyday decision problems, linear programming was comparatively unknown before 1947. No work of any significance was carried out before this date, even though the French mathematician Joseph Fourier seemed to be aware of the subject’s potential as early as 1823. In 1939 a Russian mathematician, Leonid Vitalyevich Kantorovich, published an extensive monograph, Matematicheskie metody organizatsi i planirovaniya proizvodstva (“Mathematical Methods for Organization and Planning of Production”), which is now credited with being the first treatise to recognize that certain important broad classes of scheduling problems had well-defined mathematical structures. Unfortunately, Kantorovich’s proposals remained mostly unknown both in the Soviet Union and elsewhere for nearly two decades. Meanwhile, linear programming had developed considerably in the United States and Western Europe. In the period following World War II, officials in the United States government came to believe that efficient coordination of the energies and resources of a whole nation in the event of nuclear war would require the use of scientific planning techniques. The advent of the computer made such an approach feasible.

Intensive work began in 1947 in the U.S. Air Force. The linear programming model was proposed because it was relatively simple from a mathematical viewpoint, and yet it provided a sufficiently general and practical framework for representing interdependent activities that share scarce resources. In the linear programming model, the modeler views the system to be optimized as being made up of various activities that are assumed to require a flow of inputs (e.g., labour and raw materials) and outputs (e.g., finished goods and services) of various types proportional to the level of the activity. Activity levels are assumed to be representable by nonnegative numbers. The revolutionary feature of the approach lies in expressing the goal of the decision process in terms of minimizing or maximizing a linear objective function—for example, maximizing possible sorties in the case of the air force, or maximizing profits in industry. Before 1947 all practical planning was characterized by a series of authoritatively imposed rules of procedure and priorities. General objectives were never stated, probably because of the impossibility of performing the calculations necessary to minimize an objective function under constraints. In 1947 a method (described in the section The simplex method) was introduced that turned out to solve practical problems efficiently. Interest in linear programming grew rapidly, and by 1951 its use spread to industry. Today it is almost impossible to name an industry that is not using mathematical programming in some form, although the applications and the extent to which it is used vary greatly, even within the same industry.

Interest in linear programming has also extended to economics. In 1937 the Hungarian-born mathematician John von Neumann analyzed a steadily expanding economy based on alternative methods of production and fixed technological coefficients. As far as mathematical history is concerned, the study of linear inequality systems excited virtually no interest before 1936. In 1911 a vertex-to-vertex movement along edges of a polyhedron (as is done in the simplex method) was suggested as a way to solve a problem that involved optimization, and in 1941 movement along edges was proposed for a problem involving transportation. Credit for laying much of the mathematical foundations should probably go to von Neumann. In 1928 he published his famous paper on game theory, and his work culminated in 1944 with the publication, in collaboration with the Austrian economist Oskar Morgenstern, of the classic Theory of Games and Economic Behaviour. In 1947 von Neumann conjectured the equivalence of linear programs and matrix games, introduced the important concept of duality, and made several proposals for the numerical solution of linear programming and game problems. Serious interest by other mathematicians began in 1948 with the rigorous development of duality and related matters.

The general simplex method was first programmed in 1951 for the United States Bureau of Standards SEAC computer. Starting in 1952, the simplex method was programmed for use on various IBM computers and later for those of other companies. As a result, commercial applications of linear programs in industry and government grew rapidly. New computational techniques and variations of older techniques continued to be developed.

More recently there has been much interest in solving large linear problems with special structures—for example, corporate models and national planning models that are multistaged, are dynamic, and exhibit a hierarchical structure. It is estimated that certain developing countries will have the potential of increasing their gross national product (GNP) by 10 to 15 percent per year if detailed growth models of the economy can be constructed, optimized, and implemented.


13.8E: Optimization of Functions of Several Variables (Exercises) - Mathematics

MACS 33000 - Computational Mathematics and Statistics Camp (Pre-Fall 2020)

  • Meeting day: August 31-September 18, MTWThF
  • Time: To be determined
  • Location: To be determined

This course surveys mathematical and statistical tools that are foundational to computational social science. Topics to be reviewed include mathematical notation and linear equations, calculus, linear algebra, probability theory, and statistical inference. Students are assumed to have encountered most of these topics previously, so that the camp serves as a refresher rather than teaching entirely new topics. Class sessions will emphasize problem solving and in-class exercises applying these techniques. Students who successfully complete the camp are situated to pass the MACSS math and statistics placement exam and enroll in computationally-enhanced course offerings at the University of Chicago without prior introductory coursework.

Who should take this course

  • Students in the Masters in Computational Social Science
  • MA and PhD students in the social sciences who have significant prior training and experience in mathematics and statistics and seek to complete the Certificate in Computational Social Science
  • Students looking for a slower-paced camp focused specifically on algebra, calculus, and probability should enroll in SOSC 30100 - Mathematics for Social Sciences. This two-week course makes no assumption of prior math/stats training. Those of you who struggle with the material of this course may switch after the first week to SOSC 30100.

This course may only be taken for pass/fail (non-credit), not for a letter grade or audit. Assignments are comprised of daily problem sets. You are encouraged to work in groups, and the instructional staff is available for consultation during class hours. We expect most students should be able to finish the problem sets during class hours. Grades will be based upon performance on the problem sets.

The University of Chicago is committed to diversity and rigorous inquiry from multiple perspectives. The MAPSS, CIR, and Computation programs share this commitment and seek to foster productive learning environments based upon inclusion, open communication, and mutual respect for a diverse range of identities, experiences, and positions.