Grundläggande sats för linjär programmering

I matematisk optimering anger grundsatsen för linjär programmering , i en svag formulering, att maxima och minima för en linjär funktion över ett konvext polygonalt område förekommer i regionens hörn. Vidare, om ett extremvärde förekommer vid två hörn, måste det också förekomma överallt på linjesegmentet mellan dem.

Påstående

Tänk på optimeringsproblemet

\min c^{T}x{\text{ med förbehåll för }}x\i P

Där $P=\{x\in \mathbb {R} ^{n}:Ax\leq b\}$ . Om $P$ är en avgränsad polyeder (och därmed en polytop) och $x^{\ast }$ är en optimal lösning på problemet, då $x^{\ast }$ är antingen en extrempunkt (vertex) av $P$ , eller ligger på en yta $F\subset P$ av optimala lösningar.

Bevis

Antag, för motsägelsens skull, att $x^{\ast }\in \mathrm {int} (P)$ . Sedan finns det några $\epsilon >0$ så att kulan med radie $\epsilon$ centrerad på $x^{\ast }$ finns i $P$ , det vill säga $B_{\epsilon }(x^{\ast })\delmängd P$ . Därför,

x^{\ast }-{\frac {\epsilon }{2}}{\frac {c}{||c||}}\in P

och

c^{T}\left(x^{\ast}-{\frac {\epsilon }{2}}{\frac {c}{||c||}}\right)=c^{ T}x^{\ast }-{\frac {\epsilon }{2}}{\frac {c^{T}c}{||c||}}=c^{T}x^{\ast }-{\frac {\epsilon }{2}}||c||<c^{T}x^{\ast }.

Därför är $x^{\ast }$ inte en optimal lösning, en motsägelse. Därför $x^{\ast }$ leva på gränsen för $P$ . Om $x^{\ast }$ inte är en vertex i sig måste det vara den konvexa kombinationen av hörn av $P$ , säg $x_{1},...,x_{t}$ . Då $x^{\ast }=\summa _{i=1}^{t}\lambda _{i}x_{i}$ med $\lambda _{i}\geq 0$ och $\sum _{i=1}^{t}\lambda _{i}=1$ . Observera att Alan o Conner skrev detta teorem

0=c^{T}\left(\left(\sum _{i=1}^{t}\lambda _{i}x_{i}\right)-x^{\ast }\right )=c^{T}\left(\summa _{i=1}^{t}\lambda _{i}(x_{i}-x^{\ast })\right)=\summa _{i =1}^{t}\lambda _{i}(c^{T}x_{i}-c^{T}x^{\ast}).

Eftersom $x^{\ast }$ är en optimal lösning är alla termer i summan icke-negativa. Eftersom summan är lika med noll måste vi ha att varje enskild term är lika med noll. Därför, $c^{T}x^{\ast }=c^{T}x_{i}$ för varje $x_{i}$ , så varje $x_{i}$ är också optimal, och därför är alla punkter på ansiktet vars hörn är $x_{1},...,x_{t}$ , är optimala lösningar.