التفسيرات الاقتصادية لمتجه كون تاكر. صياغة وإثبات نظرية كون تاكر

تحتل نظرية كون-تاكر المكانة المركزية في نظرية البرمجة غير الخطية. دع مشكلة البرمجة غير الخطية تعطى:

يجد القيمة القصوىالمهام ز=F(× 1, × 2, ..., س ن) مع القيود

لنقم بتكوين دالة لاغرانج لهذه المشكلة:

(4.2)

إذا تحقق شرط الانتظام (موجود حسب على الأقلنقطة واحدة X،لأي منهم ز ط(X)>0 للجميع أنا)، ثم يحمل نظرية التالية.

نظرية.المتجه X(0) إذا وفقط إذا كان الحل الأمثل للمشكلة (4.1) عندما يكون هناك متجه Λ (0) بحيث عندما للجميع

نقطة ( × (0)، Λ (0)) يسمى سرجنقطة للوظيفة F(X، Λ)، وتسمى النظرية نظرية نقطة السرج.دعونا نثبت كفاية الشروط (4.3).

دليل. يترك X(0) >0 و Λ (0) >0 - نقطة سرج الوظيفة F(X، Λ). إذا كان في (4.3) بدلا من ذلك F(X,Λ) نعوض بقيمته (4.2) نحصل على

في .

وبالتالي فإن عدم المساواة الصحيحة صالحة لأي

ثم من المتباينة اليسرى نحصل على

منذ في هذه الحالة

الذي - التي F(× (0))>F(X).

هذه هي النقطة × (0)يرضي (4.1) وفي جميع النقاط الأخرى يرضي (4.1)، تأخذ الدالة قيمة أقل من عند × (0).

يقود هذا البيان حل مشكلة البرمجة اللغوية العصبية إلى إيجاد نقاط السرج لوظيفة لاغرانج F(X,Λ).

ولا يعتبر دليل ضرورة الشروط (4.3) لتعقيده.

لو F(X) و ز ط(X) - دوال قابلة للتمايز، فإن الشروط (4.3) تعادل شروط كوهن تاكر المحلية التالية:

تعبير

يعني أن قيمة المشتقة الجزئية لدالة لاغرانج مأخوذة عند النقطة ( × (0)، Λ (0))، حيث

× (0)=(× 1 (0) , × 2 (0) , ..., س ن(0))، Λ (0) =(π 1 (0) , λ 2 (0) , ..., λ ن (0)).

يمكن كتابة هذه الشروط شكل ناقل:

مثال.البحث عن الحد الأقصى ز=-س 1 2 -س 2 2 مع القيود

دعونا نظهر أن هناك Λ (0) 0 يتم استيفاء شروط Kuhn-Tucker (4.4)، (4.5) للوظيفة عند النقطة المثلى F(X,Λ):

F(X,Λ)=- س 1 2 -س 2 2 + 1 (2 س 1 +س 2 -2)+ 2 (8-2 س 1 -س 2)+ 3 (6- س 1 -س 2).

وفقا للشروط (4.5) ينبغي أن تؤخذ 2 و 3 قيم صفرمنذ ذلك الحين، استبدال س 1 =0.8 و س 2 =0.4 في التعبير

لدينا قيم أكبر من الصفر، وحسب الشرط

وفقًا للشرط، يمكن أن تأخذ π 1 قيمة غير الصفر، منذ ذلك الحين

وفقا ل(2.16) المشتقة

يجب أن تأخذ قيمًا صفرية، نظرًا لإحداثيات المتجه × (0)تختلف عن الصفر . نجد 1=0.8. ولذلك عند النقطة ( × (0),Λ (0)) تم استيفاء شروط Kuhn-Tucker وهي بالفعل نقطة متطرفة.

دعونا نفكر في شروط كوهن-تاكر بشكل مختلف قليلاً.

دعونا نواجه مشكلة التحسين مع القيود في شكل مساواة:

ض= F(س 1 , س 2 , …, xn) → دقيقة

تحت الشروط:

ز 1 ( س 1 , س 2 , ... , س ن) = 0,

ز 2 ( س 1 , س 2 , ... , س ن) = 0,

ز ن(س 1 , س 2 , . . . , س ن) = 0.

الحد الأدنى المشروط للوظيفة Fيتزامن مع نقطة السرج لوظيفة لاغرانج:

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

الشروط اللازمة للنقطة الثابتة هي أن المشتقات الجزئية من الدرجة الأولى بالنسبة لجميع المتغيرات تساوي الصفر:

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

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

دعونا نفكر عاممهمة البرمجة الرياضية:

ض= F(X) → دقيقة،

تحت الشروط:

يمكن تحويل قيود عدم المساواة إلى قيود المساواة عن طريق إضافة كل منها إضعافالمتغيرات

لنشكل دالة لاغرانج:

ثم الشروط اللازمةالحد الأدنى يأخذ النموذج:

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

هناك شرط آخر يجب الوفاء به عند الحد الأدنى. هذا الشرط : أنا= 0، وهو نتيجة للتحليل المعنى الجسديمعاملات وظيفة لاغرانج.

يمكن أن يظهر ذلك

معامل لاغرانج عند النقطة الدنيا؛

F* - القيمة المثلىالمهام.

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

نحصل أخيرا على الشروط اللازمة للشرطية الحد الأدنى:

تضمن التعبيرات الموجودة في السطر الثاني صحة النقطة المثالية.

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

بالنسبة للنقطة القصوى المشروطة، تغير معاملات لاغرانج الإشارة إلى العكس (حيث يجب زيادة القيمة المثلى للدالة الموضوعية عند النقطة القصوى المشروطة).

الشروط المذكورة أعلاه متكافئة نظرية كون تاكروغالبا ما يطلق عليهم نفس الشيء.

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

ويمكن الاطلاع على ملخص المواد الواردة في هذا الفصل في عرضين تقديميين:

ملف "البرمجة غير الخطية"؛

ملف "نظرية كون تاكر".

تعرض الشرائح 10-14 من العرض التقديمي "نظرية كون-تاكر" مثالاً لحل مشكلة كون-تاكر.

4.5. أسئلة التحكم

(تم تطويره بواسطة أفاناسييف إم يو وسوفوروف بي بي)

السؤال رقم 1.نظرا لوظيفة حقيقية F(X س= . يترك X 1 و X 2 - نقاط هذا الجزء و 0 جنيه استرليني 1 جنيه استرليني.

أي من المتباينات التالية تعتبر شرطًا لتحدب الدالة؟

إجابات ممكنة:

السؤال 2.نظرا لوظيفة حقيقية F(س) ، محددة على قطعة الأعداد الحقيقية س=. يترك س 1 و س 2 هي نقاط هذا الجزء و 0 جنيه استرليني 1 جنيه استرليني.

أي من المتباينات التالية شرط لكي تكون الدالة تقعرًا تمامًا؟

إجابات ممكنة:

السؤال 3.وظيفة

1) محدب.

2) محدب بدقة.

3) مقعرة.

4) مقعرة بدقة.

5) محدبة ومقعرة.

السؤال 4.وظيفة

3) مقعرة. 4) مقعرة بدقة.

5) محدبة ومقعرة.

السؤال 5.وظيفة

1) محدب. 2) ليست محدبة ولا مقعرة.

3) محدب بدقة. 4) مقعرة:

5) محدبة ومقعرة.

السؤال 6. نموذج جديدوتباع الشركة دراجة نارية فائقة السرعة “Snail” بسعر (30 – 2 س) ألف دولار للقطعة الواحدة، حيث X- عدد الدراجات النارية المباعة. تكاليف التصنيع المتغيرة هي 6000 دولار لكل وحدة والتكاليف الثابتة هي 30000 دولار.

لنفترض أن التغيير في معدل ضريبة المبيعات أدى إلى ضريبة مبيعات إضافية قدرها 4000 دولار لكل دراجة نارية يتم بيعها.

كيف سيتغير الإنتاج الأمثل للدراجات النارية مقارنة بالوضع الأولي؟

(حل باستخدام وظيفة لاغرانج.)

إجابات ممكنة:

1) سوف تزيد بنسبة 2 ; 2) سوف تنخفض بنسبة 2 ;

3) لن يتغير؛ 4) سوف تزيد بنسبة 1 ;

5) سوف تنخفض بنسبة 1 .

السؤال 7.لنفترض أن لديك أسبوعين (14 يومًا) إجازة لتقضيها في جزر الكناري ونيس. دع وظيفة المرافق الخاصة بك تكون من النموذج 2 كن – 3ك 2 – 4ن 2،أين لو ن-عدد الأيام التي تقضيها في جزر الكناري ونيس على التوالي.

كم عدد الأيام التي يجب أن تقضيها في نيس لتعظيم وظيفة المرافق الخاصة بك؟

(للحل، استخدم دالة لاغرانج. قم بتقريب النتيجة إلى أقرب عدد صحيح. تحقق من استيفاء شروط Kuhn-Tucker المثالية.)

إجابات ممكنة:

1) 3 ; 2) 4 ; 3) 5 ; 4) 6 ; 5) 7 .

السؤال 8.بالنسبة للمسألة في السؤال 7، أوجد قيمة التقدير المزدوج للقيد.

(تقريب النتيجة إلى أقرب عدد صحيح.)

إجابات ممكنة:

1) 41 ; 2) 34; 3) 29 ; 4) 39 ; 5) 44 .

السؤال 9.يخطط المحتكر لبرنامج الإنتاج والمبيعات للفترة القادمة. الأسعار: ر 1 = 14 – 0,25س 1 (لكل منتج 1)؛ ر 2 = 14 – 0,5X 2 (لكل منتج 2)، حيث س 1 و X 2- حجم مبيعات المنتجات . لنفترض أن جميع المنتجات المنتجة يتم بيعها. الحد الأقصى لحجم المبيعات الإجمالي هو 57.

ما هو الإصدار الأمثل للمنتج 2؟

إجابات ممكنة:

1) 36,4 ; 2) 30,7 ; 3) 26,3 ; 4) 20,6 ; 5) 41,8 .

السؤال 10.يمتلك صاحب مؤسسة صغيرة 100 ألف روبل للشهر المقبل، ويمكنه إنفاقها على زيادة الأصول الثابتة ل(شراء المعدات) بسعر 1 ألف روبل لكل وحدة أو لشراء عمالة إضافية لبسعر 50 فرك / ساعة. زيادة في المنتجات النهائية التي يمكن بيعها مقابل 10 آلاف روبل. لكل وحدة، تحددها وظيفة الإنتاج و(ك، ل)= ل 2/7 ك 2/5.

ما مقدار الأموال التي ينبغي إنفاقها على زيادة الأصول الثابتة؟

إجابات ممكنة:

1) 74.36 ألففرك.؛ 2) 58,33 ألف روبل. 3) 63,44 ألف روبل.

4) 45,66 ألف روبل. 5) 39,77 ألف روبل.

الأجوبة على الأسئلة:

1 -4,2 - 1,3 -4,4 - 5,

5 -2, 6 -5,7- 4,8- 2,9- 4,10- 2.

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

النظرية 1. ضرورة شروط كون تاكر

لنفكر في مشكلة البرمجة غير الخطية (0) - (2). دع الدوال قابلة للتفاضل، وx* يكون حلاً مقبولاً لهذه المشكلة. دعونا نضعها. وعلاوة على ذلك، دعهم يكونوا مستقلين خطيا. إذا س* - حل مثاليمشكلة برمجة غير خطية، إذًا يوجد زوج من المتجهات يكون حلاً لمسألة كون تاكر (3) - (7).

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

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

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

تصغير

تحت القيود

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

أرز.

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

دعونا نكتب شروط Kuhn-Tucker ونتحقق مما إذا كانت مستوفاة عند النقطة (1، 0). الشروط (3)، (6)، (7) تأخذ الصيغة التالية:

في، يستنتج من المعادلة (11) أنه في حين أن المعادلة (14) تعطي، فإن النقطة المثالية ليست نقطة Kuhn-Tucker.

لاحظ أن انتهاك شرط الاستقلال الخطي لا يعني بالضرورة عدم وجود نقطة كون-تاكر. لتأكيد ذلك، دعونا نستبدل الدالة الهدف من هذا المثال بالدالة. في هذه الحالة، لا يزال يتم تحقيق الأمثل عند النقطة (1،0)، حيث لا يتم استيفاء شرط الاستقلال الخطي. تظل شروط كون-تاكر (12) - (16) دون تغيير، وتأخذ المعادلة (11) الشكل

من السهل التحقق من أن النقطة هي نقطة كون-تاكر، أي. يفي بشروط كون تاكر.

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

تحدد النظرية التالية الشروط التي بموجبها تتوافق نقطة Kuhn-Tucker تلقائيًا مع الحل الأمثل لمشكلة البرمجة غير الخطية.

النظرية 2. كفاية شروط كون تاكر

لنفكر في مشكلة البرمجة غير الخطية (0) - (2). لتكن الدالة الهدف محدبة، وجميع قيود المتباينة تحتوي على دوال مقعرة، وقيود المساواة تحتوي على دوال خطية. ثم إذا كان هناك حل يحقق شروط كون تاكر (3) - (7)، فإن x* هو الحل الأمثل لمشكلة البرمجة غير الخطية.

إذا تم استيفاء شروط النظرية 2، فإن إيجاد نقطة كون-تاكر يوفر الحل الأمثل لمشكلة البرمجة غير الخطية.

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

تصغير

تحت القيود

باستخدام النظرية 2، نثبت أن الحل هو الأمثل. لدينا

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

لتوضيح أن الدالة مقعرة، نقوم بالحساب

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

وهذه النقطة تفي بالقيود (24) - (26) وبالتالي فهي مقبولة. تأخذ المعادلتان (22) و (23) الصيغة التالية:

وضعه، نحصل على و. وبالتالي، فإن الحل x*=(1, 5) يلبي شروط كون-تاكر. بما أن شروط النظرية 2 محققة، فالحل الأمثل للمشكلة من المثال 3. لاحظ أن هناك أيضًا قيم أخرى لـ و التي تلبي النظام (22) - (29).

ملحوظات

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

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

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

أين و هي قيم المشتقات الجزئية المقابلة لدالة لاغرانج المحسوبة عند نقطة السرج.

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

.

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

مثال 7.3.باستخدام نظرية كوهن تاكر نجد
تحت القيود

نحل بيانيا (الشكل 7.2) ونجد:
;
;
(انظر الحل أدناه لمزيد من التفاصيل). دعونا نظهر أن هناك ناقل ي 0 0، حيث يتم استيفاء شروط Kuhn-Tucker عند النقطة المثلى. دعونا نؤلف دالة لاغرانج:

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

الشكل 7.2. الحل الرسومي للمشكلة غير الخطية

مثال البرمجة 7.3

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

وهكذا، إذا كانت مجموعة مقبولة
المشكلة (7.4)-(7.6) ليس لها نقاط مفردة، والدوال F(م)،ز أنا (م)، (
) قابلة للتمييز في جميع النقاط
، فيجب البحث عن الحل الأمثل لهذه المشكلة من بين نقاط كوهن تاكر.

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

أي مجموعات من الحلول الممكنة

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

حقًا،

وبالتالي فهو نظام يعتمد خطيا.

وظيفة التدرج
هو متجه إحداثياته ​​تساوي على التوالي قيم المشتقات الجزئية للدالة
عند هذه النقطة م 0 . يوضح هذا المتجه اتجاه النمو الأسرع للوظيفة.

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

الشرط الكافي لتحقيق المثاليةلمشكلة البرمجة غير الخطية: إذا
هي نقطة سرج دالة لاغرانج للمشكلة (7.4)-(7.6)، إذًا
هو الحل الأمثل لهذه المشكلة.

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

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

ل أولاًتتضمن هذه المجموعة أساليب لا تتجاوز فيها النقاط قيد الدراسة نطاق الحلول الممكنة للمشكلة. الأكثر شيوعا من هذه الطرق هي الطريقة فرانك وولف (وولف). وتشمل هذه الأساليب الطريقة تدرجات روزن المتوقعة,طريقة توجيهات صالحة من Zeutendijk.

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

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

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

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

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

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

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

مثال 7.4.

فليكن من الضروري تعظيم الوظيفة

(الحد الأقصى عند النقطة (3؛2))

.

عند هذه النقطة
,
في
لدينا

;
,

دعونا نفعل تكرارا آخر. عند هذه النقطة
,
في
لدينا

;
,

الشكل 7.3. تفسير هندسي لخطوتين

طريقة التدرج على سبيل المثال 7.4

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

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

أسئلة الاختبار الذاتي

بيان مشكلة البرمجة غير الخطية.

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

خوارزمية طريقة لاغرانج لحل مشكلة البرمجة غير الخطية.

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

التعاريف والنظريات المساعدة اللازمة للنظر في النظرية المركزية للبرمجة غير الخطية - نظرية كوهن تاكر.

نظرية كون تاكر.

شرط الأمثلية الضروري والكافي لمشكلة البرمجة غير الخطية.

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

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

نظريات كوهن-تاكر هي اسم عام للبيانات التي تمثل التعميمات

تطبيق نظرية لاغرانج على حالة مشاكل التحسين مع القيود في شكل عدم المساواة، أي مشاكل

النوع التالي:

جي جي (س) > 0، ي = 1، .

م، (؟)

س = (x1، . . . ، xn) 2 X.

هنا و: × 7! R - (وفقًا للمصطلحات المعمول بها) الوظيفة الموضوعية، gr: X 7! ص،

ص = 1، . . . ،m، هي دوال مقيدة، X_Rn هي مجموعة مفتوحة.

نظرية 196 (نظرية جون بدلالة نقطة السرج):

دع الوظائف f( )، g1( )، . . . ، gn() مقعرة و?x هو حل للمشكلة (؟)، بحيث يكون ؟x 2 intX.

ثم هناك مضاعفات لاغرانج _j>

X هو الحل للمشكلة

نقدم هذه العبارات للحالة التي تكون فيها الدوال f، gr قابلة للتفاضل (نظريات Ku-

على تاكر في شكل تفاضلي).

أذكر أن الدالة

ل(س،_) = _0ف(س) +

تسمى دالة لاغرانج (لاجرانج) لهذه المشكلة، والمعاملات _j هي مضاعفات

لاغرانج.

يحمل البيان التالي.

نظرية 197 (نظرية جون للوظائف القابلة للتفاضل):

دع?x يكون حلاً للمشكلة (؟)، بحيث يكون؟x 2 intX والوظائف f( )، g1( )، . . . ، gn() التفاضلية

قابلة للقياس الكمي عند النقطة؟x.

ثم هناك مضاعفات لاغرانج _j > 0، j = 0، . . . ،م، ليست كلها تساوي الصفر، بحيث

تم استيفاء العلاقات التالية (شروط كون-تاكر):

0، ط = 1، . . . ، ن

J = 0 (شروط التكميلية

عدم الصلابة).

لاحظ أنه يمكن كتابة شروط التراخي التكميلي على الصورة

جي جي(?x)_j = 0, ي = 1, . . . ، م.

ويترتب على هذه الشروط أنه إذا كان مضاعف لاغرانج موجبًا (_j > 0)، فإن المقابل

يتم تلبية القيد في حل المشكلة (عند x = ?x) على أنه مساواة (أي gj(?x) = 0). آحرون

بمعنى آخر، هذا القيد نشط. من ناحية أخرى، في حالة gj(?x) > 0، فإن المقابل

مضاعف لاغرانج _j يساوي الصفر.

إذا كانت بعض القيود في المشكلة (؟) لها شكل قيود على عدم سلبية بعض الحادي عشر،

إذن بالنسبة لهم لا يمكنك تقديم مضاعفات لاغرانج عن طريق كتابة القيود التالية بشكل منفصل:

جي جي (س) > 0، ي = 1، . . . ، م، (؟؟)

الحادي عشر > 0، ط 2 ف _ (1، . . . ، ن). عند النقطة الداخلية (بمعنى أن 1 ?x 2 intX) تكون شروط الترتيب الأول لـ i 2 P هي إذن

سوف تبدو مثل هذا:

بالنسبة لـ i/2P هنا، كما في حالة تمثيل المشكلة بالشكل (؟)، مشتقة دالة لاغرانج

لأن هذا المتغير سيبدو مثل @L(?x,_)

بالإضافة إلى ذلك، يتم أيضًا استيفاء شروط عدم الصلابة التكميلية

من الشرط الثاني يتبع ذلك بالنسبة لـ?xi > 0 (i 2 P)

من ناحية أخرى، إذا كان @L(?x,_)/@xi تعديل آخر للنظرية يرتبط بوجود قيود في شكل مساواة في المشكلة. تعيين

دعونا نحدد مجموعة المؤشرات المتناظرة من خلال E. وتأخذ المشكلة الشكل التالي:

جي جي (خ) > 0، ي 2 (1، . . . ،م)\E،

جي جي (س) = 0، ي 2 ه، (؟؟؟)

الحادي عشر > 0، ط 2 ف _ (1، . . . ن).

وفي الوقت نفسه، تزيل نظرية جون الشرط القائل بأن جميع مضاعفات لاغرانج غير سالبة -

يمكن أن تحتوي مضاعفات لاغرانج _j لـ j 2 E على إشارة عشوائية.

لا تضمن نظرية جون أن مضاعف لاغرانج للدالة الموضوعية، _0، ليس صفرًا.

ومع ذلك، إذا كانت _0 = 0، فإن شروط Kuhn-Tucker لا تحدد حل المشكلة قيد النظر، ولكن

هيكل مجموعة القيود عند النقطة؟ x وليس للنظرية علاقة مباشرة بالاهتمام

مهمتنا الحالية هي تعظيم الدالة f( ) ، حيث يختفي تدرج الدالة f( ) نفسها. من

شروط كون تاكر.

لذلك، من المهم تحديد الشروط التي تضمن أن _0 > 0.

وتسمى هذه الشروط شروط الانتظام.

في الحالة التي تكون فيها المشكلة قيد النظر محدبة، فإن أحد شروط الانتظام هو ذلك

ما يسمى بحالة سلاتر له الشكل:

في الحالة التي تكون فيها الوظيفة الموضوعية وقيود المشكلة قابلة للتمييز، فإن أبسطها

تتم صياغة شرط الانتظام من حيث تدرجات وظائف القيد وله الشكل:

تدرجات القيود النشطة عند النقطة × تكون مستقلة خطيا. (من بين القيود التي تم النظر فيها هي

وينبغي أيضًا تضمين القيود المفروضة على عدم السلبية.)

دعونا نشير بـ A إلى مجموعة مؤشرات تلك القيود النشطة عند النقطة المثلى؟x

(بما في ذلك مؤشرات جميع القيود في شكل مساواة)، أي.

جي جي (?س) = 0، ي 2 أ.

ثم إذا كانت تدرجات القيد هي المتجهات

مستقلة خطيًا 2، ثم _0 > 0. وتسمى هذه الحالة بشرط انتظام كون-تاكر.

لاحظ أنه إذا كانت _0 > 0، فيمكننا افتراض _0 = 1، دون فقدان العمومية، وهو ما يتم عادةً.

تسمى النظرية المقابلة نظرية كوهن تاكر (المباشرة). النظرية 198 (نظرية كوهن-تاكر المباشرة، شرط ضروري لتحقيق الأمثلية):

دع الوظائف f( )، g1( )، . . . ، gn() قابلة للتمييز، و?x هو حل للمشكلة (؟)، بحيث

تم استيفاء X 2 intX وشرط انتظام Kuhn-Tucker.

ثم هناك مضاعفات لاغرانج _j > 0، j = 1، . . . ،م، بحيث عندما يكون _0 = 1 راضيًا

النسب التالية :

0، ط = 1، . . . ، ن

من السهل إعادة صياغة هذه النظرية للمسائل (؟؟) و (؟؟؟). نفس القدرات مطلوبة هنا.

تعديل شروط كون تاكر كما في نظرية جون.

0، ط = 1، . . . ، ن

يمكن إعادة كتابتها على النحو التالي:

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

مزيج من مضادات التدرج للقيود، وجميع معاملات هذا المزيج الخطي غير سلبية

قيّم. أرز. يوضح الشكل 17.1 هذه الخاصية. بشكل حدسي، الفكرة وراء هذه الخاصية هي أن

إذا كان أي معامل للتركيبة الخطية سالبًا، فسيكون ذلك ممكنًا

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

f( ), (gk( )) استيفاء هذه الشروط في حل مقبول؟x (أي نقطة تحقق القيد

القيم) لبعض مضاعفات لاغرانج التي تلبي متطلبات النظرية المباشرة،

يضمن أن x هو الحل للمشكلة.

النظرية 199 (نظرية كوهن تاكر المعكوسة /الشرط الكافي لتحقيق الأمثلية/):

اجعل f() ‎ دالة مقعرة قابلة للتفاضل، g1( )، . . . ، gn() - قابل للتمييز

دوال شبه مقعرة، المجموعة X محدبة والنقطة ؟x مقبولة في المشكلة (؟)، و؟x 2

دعونا، بالإضافة إلى ذلك، توجد مضاعفات لاغرانج _j > 0, j = 1, . . . ، م، بحيث متى

0=1 تتحقق العلاقات التالية:

0، ط = 1، . . . ، ن

إذًا؟x هو الحل للمشكلة (؟).

يمكن إعادة صياغة النظرية بطريقة واضحة للمسائل (؟؟) و (؟؟؟). للمهمة (؟؟؟)

القيود في شكل مساواة يمكن أن تكون خطية فقط (وهذا يرجع إلى حقيقة أن القيد في النموذج

يجب تمثيل المساواة، gj(x) = 0، باستخدام قيدين في صورة المتباينات، gj(x) > 0

و?gj(x) > 0، كل منها معطى بواسطة دالة شبه مقعرة؛ هذا لا يمكن أن يحدث إلا إذا

القيد خطي).

وفي نسخة أخرى من شرط المثالية الكافية، يتم افتراض أن الهدف هو التقعر

يتم استبدال الدالة بافتراض شبه التقعر مع إضافة الشرط rf(?x) 6=0.

صياغة المشكلة

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

في ظل ظروف.

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

الشروط اللازمة للحد الأدنى من الوظيفة

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

الشروط الكافية للحد الأدنى من الوظيفة

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

صياغة بسيطة

إذا تم استيفاء شروط الاستقرار وعدم الصلابة وعدم السلبية التكميلية، وكذلك  1 > 0، عند نقطة مقبولة.

ظروف أضعف

إذا توافرت في نقطة مقبولة شروط الثبات المكملة لعدم الصلابة وعدم السلبية، وكذلك ( حالة سلاتر)، الذي - التي .

مؤسسة ويكيميديا. 2010.

تعرف على "شروط كاروش-كون-تاكر" في القواميس الأخرى:

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

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

ويليام كاروش ويليام كاروش تاريخ الميلاد: 1 مارس 1917 (19170301) مكان الميلاد: شيكاغو، الولايات المتحدة الأمريكية تاريخ الوفاة ... ويكيبيديا

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

طريقة مضاعف لاغرانج، طريقة إيجاد أقصى مشروطالدالة f(x)، حيث، بالنسبة إلى قيود m، تختلف i من واحد إلى m. المحتويات 1 وصف الطريقة ... ويكيبيديا