MAC-IME-USP CARLOS EDUARDO FERREIRA

SALA 297A TEL.: 818 6140

E-MAIL cef@ime.usp.br

MAC 325 - Otimização Combinatória - MAC 5781

Segunda Lista de Exercícios (30 pontos) - Entrega: 28 de setembro

1.

(6+6 pontos)
Resolva os problemas abaixo usando o Método Simplex para Redes. $$\epsffile{l2f1.eps}$$

$$\epsffile{l2f2.eps}$$

2.

(4+4 pontos)
Considere a árvore $T$ dada pelos seguintes vetores:

$$\begin{tabular} {c\vert c\vert c\vert c\vert c\vert c\vert c... ... suc & 4 & 6 & 7 & 8 & 2 & 3 & 9 & 5 & 1 \\ \hline\end{tabular}$$

a. Desenhe a árvore $T$.

b. Mostre as alterações nos vetores correspondentes a retirar a aresta (5,9) e colocar a aresta (1,2).

3.

(10 pontos)
Suponha um problema de transporte (PT) viável (ou seja, com pelo menos uma solução viável).
Mostre que (PT) é ilimitado se e somente se existe em $G$ um circuito orientado com custo total negativo (i.e. $\sum$_{e ∈C} c_e < 0 ).

4.

(14 pontos) (de preferência sem olhar no caderno...)
Seja $T$ uma árvore geradora de $G$, $x$ uma solução árvore viável, $c$ o vetor de custo das arestas, $b$ o vetor de demandas dos vértices e $y$ um vetor tal que $y$_j = y_i + c_(i,j) para toda arco $(i,j)$ de $T$. Defina $c:=\; c\; -\; yA$, onde $A$ é a matriz de incidências de $G$, e mostre que:

a. $cx\; =\; 0$.

b. $cx\; =\; yb$

c. Para todo $x\text{'}$ tal que $Ax\text{'}=b$, $cx\text{'}\; =cx\text{'}\; +\; cx$.

d. Se $c\ge 0$, então $x$ é uma solução ótima.

Seja $e\; \in E\; \setminus T$ e considere o circuito $C$ formado por $e$ em $T$. Considere ainda $R\; \subseteq C$ como o conjunto das arestas de $C$ que têm orientação contrária à de $e$ em $C$. Defina, $$x'_e := \left\{ \begin{array} {ll} x_e, & \mbox{se } e \not... ...x_e + t, & \mbox{se } e \in C \setminus R. \end{array} \right.$$e mostre que:

e. $Ax\text{'}\; =\; b$.

f. $cx\text{'}\; =\; cx\; +c$_e t .

g. Se $c$_e < 0 e $R\; =\; \varnothing$ então o problema é ilimitado.