Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Convexidade e programação linear

+2 votos
102 visitas
perguntada Set 26, 2016 em Matemática por Mauro Patrão (71 pontos)  

Considere o conjunto

\[C = \{y \in \mathbb{R}^n : c^Ty = \min \{c^Tx : Ax = b, x \geq0\}\}\]

e também o conjunto

\[\tilde{C} = \{(b,z) : z = c^Tx, Ax = b, x \geq0\}\]

(a) Mostre que \(C\) é um conjunto convexo.

(b) O que se pode dizer sobre \(C\) se a solução do problema de programação linear é única?

(c) Mostre que \(\tilde{C}\) é um conjunto convexo.

(d) Mostre que \(z(b) = \min \{c^Tx : Ax = b, x \geq0\}\) é uma função convexa.

Compartilhe

1 Resposta

+2 votos
respondida Set 26, 2016 por Mauro Patrão (71 pontos)  
editado Dez 4, 2016 por Mauro Patrão

(a) Considere \(y, y' \in C\) e também \(t \in (0,1)\). Temos que

\[ c^Ty = c^Ty^\prime = \min \{c^Tx : Ax =b, x \geq 0\} \]

Segue então que

\[ c^T(ty + (1-t)y^\prime) = tc^Ty + (1-t)c^Ty^\prime = \\ = \min \{c^Tx : Ax =b, x \geq 0\} \]

mostrando que \(ty + (1-t)y' \in C\) e portanto que \(C\) é um conjunto convexo.

(b) Como \(C\) é o conjunto das soluções do problema linear, se a solução for única, então \(C\) é um conjunto unitário.

(c) Considere \((b,z), (b',z') \in \tilde{C}\) e também \(t \in (0,1)\). Temos que

\[ z = c^Tx, Ax = b, x \geq 0 \\ z^\prime = c^Tx^\prime, Ax^\prime = b^\prime, x^\prime \geq 0 \]

Segue então que

\[ tz + (1-t)z^\prime = c^T(tx + (1-t)x^\prime), \\ A(tx + (1-t)x^\prime) = tb + (1-t)b^\prime, \\ tx + (1-t)x^\prime \geq 0 \]

mostrando que

\[ t(b,z) + (1-t)(b^\prime,z^\prime) = (tb + (1-t)b^\prime, tz + (1-t)z^\prime)) \in \tilde{C} \]

e portanto que \(\tilde{C}\) é um conjunto convexo.

(d) Esse item segue direto da definição de função convexa e do item anterior, pois é imediato que

\[ \tilde{C} = \{(b,z) : z \geq z(b)\} \]

comentou Nov 13, 2016 por santiago (131 pontos)  
Solução muito interessantes! Só falta mudar a demonstração para min.
comentou Dez 4, 2016 por Mauro Patrão (71 pontos)  
Já alterei a demonstração de max para min.
Valeu, Santiago!
...