[ricotero]

Hola...

Tengo este problema

Sea X= {Ax<= b} y sea x0 tal que Ax0<0 Demostrar que x0 no puede ser un punto extremo de X

Muchas gracias, no he podido con él.

Pero donde tu dices Ax<0 no debería ser Ax<b , y visceversa.... Yo intentaba demostrar que x0 se puede expresar como una combinación convexa de los puntos extremos del politopo

[Fernando Revilla]

Suponiendo \( A\in{\mathbb{R}^{m\times{n}}} \), las condiciones \( Ax\leq{0} \) se escriben en la forma:

\( D\;\equiv{}\;\begin{Bmatrix} a_{11}x_1+...+a_{1n}x_n\leq{b_1}\\\ldots\\a_{m1}x_1+...+a_{mn}x_n\leq{b_m}\end{matrix} \)

Si \( f:D\rightarrow{\mathbb{R}} \) no nula viene dada por:

\( f(x_1,...,x_n)=c_1x_1+...+c_nx_n\;,\quad (c_1,...,c_n)\neq{(0,...,0)} \)

entonces, si un extremo se alcanzara en \( x_0 \) tal que \( Ax_0<b \) el punto \( x_0 \) sería interior a \( D \) y las parciales de \( f \) en \( x_0 \) se deberian anular:

\(  \dfrac{{\partial f}}{{\partial x_1}}(x_0)=c_1=0\;,\;...\;,\; \dfrac{{\partial f}}{{\partial x_n}}(x_0)=c_n=0 \)

lo cual es absurdo.

Saludos.

P.D.

(1) Hemos elegido \( f \) de esa manera dado que la pregunta está en el apartado de programación. lineal.
(2) Si \( f=0 \) la proposición es falsa.

[ricotero]

hola... no entiendo por qué las derivadas parciales de x0 deberían ser 0..........
¿No habría manera demostrar que x0 se puede expresar como una combinación convexa de otros puntos extremos?

Además donde escribes Ax<= 0, ¿no debería ser Ax<b y visceversa?

Muchas gracias

[Fernando Revilla]

Entiendo, es que yo he usado la palabra extremo como sinónimo de extremo de una función objetivo \( f \).

Bien, si \( x_0 \) pudiera expresarse como combinación lineal convexa de los puntos \( x_1,x_2,\;(Ax_1=Ax_2=b) \) tendríamos \( x_0=tx_1+(1-t)x_2\;(t\in{[0,1]}) \). Entonces:

\( Ax_0=A( \;tx_1+(1-t)x_2\;)=tAx_1+(1-t)Ax_2=tb+(1-t)b=b \)

lo cual es absurdo.

Saludos.