Qavariq to'plam. Qavariq kombinatsiya

Kavarik to'plam. Kavarik kombinatsiya Reja: Kavarik to'plam va kavarik kombinatsiya. Kavarik kombinatsiya haqidagi asosiy teoremalar. Asosiy teoremalar. chiziqli programmalashtirish masalasining yechimlari kavarik to'plam tashkil qilishi. chiziqli programmalash masalasining xossalari kavarik to'plam xossalari bilan uzviy bog'liqdir. Faraz kilaylik X1,X2,,Xn vektorlar (nuqtalar) n- o'lchovli Yen Yevklid fazosining ixtieriy nuqtalari bulsin. 1-ta'rif. X1,X2,,Xn nuqtalarning kavarik kombinatsiyasi deb, i0 () shartlarni kanoatlantirib, ixtieriy i sonlarga nisbatan tuzilgan 1X1+2X2+,+nXn yig'indiga aytiladi. Tekislikda A1(x11, x12) va A2(x21, x22) nuqtalarning kavarik kombinatsiyasini aniklaylik. Uning uchun shu nuqtalarni tutashtiruvchi yo'naltirilgan A1A2 kesmani olamiz. A1 va A2 nuqtalarning koordinatalri orqali A1A2 kesmada etgan ixtieriy A(x1, x2) nuqtaning x1, x2 koordinatalarini topamiz. A1A2= (x1-x11,x2-x12) va A1A2= (x21-x11, x22-x12) vektorlar o'zaro parallel va bir xil yunalgan. Shuning uchun A1A2= (A1A2), 01. Bundan esa x1- x11=( x21-x11) x2-x12=( x22-x12) eki x1=(1-)x11+ x21 x2=(1-)x12+ x22 Bu tengliklarda 1-=1, =2 belgilanishlar kiritsak, kuyidagiga ega bulamiz: x1=1 x11+2 x21 x2=1 x12+2 x22 (4) 1 0,20 va 1+2=1 (5) tengliklarda A nuqtaning koordinatalri A1 va A2 nuqtalarning kavarik kombinatsiyasidan iborat deyiladi. Agar 1=1 va 2=0 bulsa A nuqta A1A2 kesmaning A1 uchi bilan; 1 =0 va 2=1 bulsa A2 nuqta bilan ustma- ust tushadi va A1 va A2 nuqtalar A1A2 kesmaning chetki nuqtalari eki uchlari deyiladi. ta'rif. G -to'plam kavarik to'plam deyiladi, agar u uzining ixtieriy ikkita nuqtasi bilan birga, ularning kavarik kombinatsiyasini xam o'z ichiga olsa. Chetki nuqta kavarik to'plamning boshqa xechqanday 2 ta nuqtasining kavarik kombinatsiya bulmaydi. 3-ta'rif. chiziqli programmalash masalasining bush to'plam bo'lmagan joiz yechimlar to'plami masalaning yechim kupburchagi eki yechim sohasi deyiladi. Tekislikda kavarik kupburchak chekli uchlarga ega bo'lgan chegaralangan, epik to'plamdir. 1-teorema. chiziqli programmalash masalasining joiz yechimlar to'plami (agar bush to'plam bulmasa) kavarik to'plam bo'ladi. Isbot. X1 va X2 nuqtalar (1) - (3) chiziqli programmalash masalasining joiz yechimlari bulsin. X=1X1+2X2 (10, 20, 1+2=1) nuqta xam berilgan masalaning joiz yechimi bo'lishini isbot qilish kerak, yani X nuqta AX=V X0 shartlarni kanoatlantirishi kerak. X1, X2 - joiz yechim bo'lgani uchun AX1=V; X10 va AX2=V; X20. X nuqtani xam AX=V tenglikka kuyamiz: AX=A(1X1+2X2)= 1 AX1+2A X2=1V+2V=(1+2)V=V X10, X20 va 10, 20 bo'lgani uchun X0 bo'ladi. Demak, X nuqta xam chiziqli programmalash masalasining joiz yechimi bo'ladi. 2-teorema. Chegaralangan, epik, kavarik kupburchak o'zini uchlarining kavarik kupburchak o'zini uchlarining kavarik kombinatsiyasidan iborat. Teoremaning isbotini keltirmaymiz. 4-ta'rif. Agar chiziqli programmalash masalasining joiz yechimlari, yechim kupburchagining chetki nuqtalariga mos kelsa, ular bazis yechimlar deyiladi. Bu ta'rifdan, musbat komponentli bazis yechimlar tayanch yechimlar bo'lishi kelib chikadi. chiziqli programmalash masalasining kononik ...