Qavariq dasturlashtirish

Qavariq programmalashtirish Reja: 1. Qavariq funksiyalar. 2. Qavariq programmalashtirish masalasi. 3. Kun-Takker teoremasi. 4. Frank-Vulf usuli va uning tadbiqlari. Qavariq funksiyalar ta'rif 1. Qavariq X to'plamda aniqlangan f (x) funksiya agar bu to'plamga qarashli ixtiyoriy nuqtalar uchun shartni qanoatlantiruvchi hamma larda quyidagi (1) tengsizlik o'rinli bo'lsa, u holda f (x) funksiya qavariq funksiya deyiladi. ta'rif 2. Agar va larning shu qiymatlarida quyidagi (2) tengsizlik bajarilsa, u holda f (x) funksiya botiq deyiladi. Agar f (x) funksiya qavariq bo'lsa, - f (x) botiq va aksincha f (x)=sx chiziqli funksiya bir vaqtda qavariq va botiqdir, bunda ixtiyoriy va lar uchun quyidagi tenglama o'rinlidir. ta'rif 3. Chiziqsiz programmalashtirish masalasining (1) (2) (3) mumkin bo'lgan yechimlar to'plami regulyarlik shartini qanoatlantiradi deyiladi, agarda mumkin bo'lgan yechimlar to'plamining aqalli birorta nuqtasi uchun shart o'rinli bo'lsa. Qavariq programmalashtirish masalasi Teorema 4. (1)-(3) masala qavariq programmalashtirish masalasi deyiladi, agarda funksiya botiq (kavariq) bo'lib, funksiya qavariq bo'lsa. Teorema 1. Qavariq programmalashtirish masalasining har qanday lokal maksimum (minimum) qiymatlari uning global maksimum (minimum) qiymatlaridan iboratdir. ta'rif 5. (3) qavariq programmalashtirish masalasining (4) funksiyasiga Lagranj funksiyasi deyiladi. Bunda Lagranj ko'paytuvchilari deyiladi. ta'rif 6. nuqta Lagranj funksiyaning egar nuqtasi deyiladi, agarda (5) barcha va lar uchun o'rinli bo'lsa. Kun-Takker teoremasi Teorema: (Kun - Takker teoremasi) Agar nuqta qavariq programmalashtirish masalasi (1) - (3) ning yechimi bo'lsa, shunday vektor mavjud bo'ladiki, unda nuqta Lagranj funksiyasining egar nuqtasini tashkil etadi. Boshqacha qilib aytganda barcha va lar uchun (5) tengsizlik o'rinlidir. Isbot. Agar nuqta qavariq programmalashtirish masalasi (1) - (3) ning yechimi bo'lsin. U holda shu nuqtada Lagranj funksiyasining minimumi mavjudligini birinchi tartibli zaruriy sharti bajarilish kerak, yani shart o'rinlidir. f (x) va funksiyalar qavariq funksiyalar bo'lganligi uchun ixtiyoriy uchun (6) funksiyaning ham qavariqligi kelib chiqadi. Shu sababli ixtiyoriy lar uchun (7) bo'ladi. nuqtani, teorema shartiga ko'ra, qavariq programmalashtirish masalasi (1) - (3) ning yechimi deb faraz qilganimiz uchun (8) tengsizlik o'rinlidir. (8) ga ko'ra, barcha uchun (9) ekanligi kelib chiqadi. Ikkinchi tomondan (6) dan (9) ni nazarda tutsak. (10) ekanligi kelib chiqadi. (7) va (10) tengsizliklardan (5) ning to'g'riligi kelib chiqadi. Demak, isbot qilingan teoremaga ko'ra, Lagranj funksiyasining egar nuqtasi mavjud bo'lsa, qavariq programmalashtirish masalasining yechimi mavjud degan xulosaga kelamiz. Chiziqsiz programmalashtirish masalasining g r a d i e n t u s u l i Gradient usuli yordamida, har qanday chiziqsiz programmalashtirish masalasini yechish mumkin Gradient usuli bilan berilgan masalaning yechimini topish jarayoni, iteratsion (ketma-ket) jarayon bo'lib, funksiyaning gradienti qadamda nol bo'lmaguncha yoki ...