Silna dvoyistist vipadok u matematichnij optimizaciyi koli pryama i dvoyisti cilovi znachennya rivni Isnuye podibnij vipadok slabka dvoyistist koli pryama zadacha maye optimalne znachennya ne menshe za dvoyistu tobto rozriv dvoyistosti bilshij abo rivnij nulyu Linijne programuvannya red Pryama zadacha Dvoyista zadachamaksimizuvati c T x displaystyle c T x nbsp minimizuvati b T y displaystyle b T y nbsp za umov A x b displaystyle begin matrix Ax leq b end matrix nbsp za umov A T y c y 0 displaystyle begin matrix A T y c y geq 0 end matrix nbsp Teorema pro silnu dvoyistist Yaksho pryama i dvoyisti zadachi rozv yazni todi optimalni tochki x y displaystyle x y nbsp zadovolnyayut c T x y T b displaystyle c T x y T b nbsp Dovedennya Rozglyanemo take rivnyannya A 0 c T b T 0 A T 0 A T 0 I x y b 0 c c 0 displaystyle begin bmatrix A amp 0 c T amp b T 0 amp A T 0 amp A T 0 amp I end bmatrix begin bmatrix x y end bmatrix leq begin bmatrix b 0 c c 0 end bmatrix nbsp Yaksho isnuyut x y displaystyle x y nbsp sho zadovolnyayut comu rivnyannyu todi A x b displaystyle Ax leq b nbsp otzhe x displaystyle x nbsp dopustimij rozv yazok y 0 displaystyle y geq 0 nbsp i A T y c displaystyle A T y c nbsp otzhe y displaystyle y nbsp takozh dopustimij rozv yazok Todi oskilki c T x b T y 0 displaystyle c T x b T y leq 0 nbsp ta za princip slabkoyi dvoyistosti mayemo sho c T x y T b displaystyle c T x y T b nbsp i na comu dovedennya zakincheno Inakshe zgidno z naslidkom lemi Farkasha isnuye vektor y T l x p T x m T w T 0 displaystyle y T lambda x p T x m T w T geq 0 nbsp sho zadovolnyaye y T l x p T x m T w T A 0 c T b T 0 A T 0 A T 0 I 0 displaystyle begin bmatrix y T amp lambda amp x p T amp x m T amp w T end bmatrix begin bmatrix A amp 0 c T amp b T 0 amp A T 0 amp A T 0 amp I end bmatrix 0 nbsp i y T l x p T x m T w T b 0 c c 0 lt 0 displaystyle begin bmatrix y T amp lambda amp x p T amp x m T amp w T end bmatrix begin bmatrix b 0 c c 0 end bmatrix lt 0 nbsp Z cogo mayemo take y T A l c T displaystyle y T A lambda c T nbsp i y 0 displaystyle y geq 0 nbsp l b A x m x p w 0 displaystyle lambda b A x m x p w 0 nbsp tobto A x p x m l b displaystyle A x p x m leq lambda b nbsp y T b lt c T x p x m displaystyle y T b lt c T x p x m nbsp Yaksho l gt 0 displaystyle lambda gt 0 nbsp todi mozhna pomnozhiti vektor y T l x p T x m T w T displaystyle begin bmatrix y T amp lambda amp x p T amp x m T amp w T end bmatrix nbsp na 1 l displaystyle 1 lambda nbsp i vvazhati sho l 1 displaystyle lambda 1 nbsp Odnak todi punkti 1 i 2 pokazuyut sho x p x m displaystyle x p x m nbsp i y displaystyle y nbsp dopustimi dlya pryamoyi i dvoyistoyi zadach vidpovidno a punkt 3 superechit slabkij dvoyistosti Inakshe yaksho l 0 displaystyle lambda 0 nbsp to z punktu 3 viplivaye sho abo y T lt 0 displaystyle y T lt 0 nbsp abo c T x p x m gt 0 displaystyle c T x p x m gt 0 nbsp U pershomu vipadku dvoyista programa neobmezhena sho superechit rozv yaznosti pryamoyi Ce mozhna pobachiti tak pripustimo sho y f displaystyle y f nbsp dopustimij rozv yazok dvoyistoyi programi oberemo dovilne m gt 0 displaystyle mu gt 0 nbsp i rozglyanemo y f m y displaystyle y f mu y nbsp Cya suma takozh ye dopustimim rozv yazkom dvoyistoyi programi oskilki y f m y 0 displaystyle y f mu y geq 0 nbsp i y f m y T A y f T A m y T A b T displaystyle y f mu y T A y f T A mu y T A b T nbsp i mozhna zrobiti y f m y T displaystyle y f mu y T nbsp yak zavgodno velikim vibravshi vidpovidne m displaystyle mu nbsp Yaksho c T x p x m gt 0 displaystyle c T x p x m gt 0 nbsp to analogichni dovodi pokazuyut sho pryama zadacha neobmezhena sho takozh daye superechnist displaystyle square nbsp Div takozh red Umova Slejtera Otrimano z https uk wikipedia org w index php title Silna dvoyistist amp oldid 35486653
