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 - 2. semestre 1998

Primeira Prova

Esta prova será resolvida em duas partes. A primeira parte se encerra em duas horas, e a esta parte será atribuída uma nota $P$₁ . Você poderá entregar uma nova versão da prova até o dia 30 de setembro, às 14 horas. As questões que você não deseja alterar devem ser indicadas nesta segunda parte. A segunda parte receberá uma nota $P$₂ . A nota final da prova será dada por $\{2P$₁ + P₂3} .

1.

(valor 1.0 ponto)
Calcule em função de $n$ o número de chamadas do procedimento $S$ no fragmento abaixo de programa:

para $i:=0$ at'e $n$ faça
		 para $j:=0$ at'e $i$ faça
		 		 para $k:=0$ at'e $i$ faça
		 		 		 se $i\; \ne j$ então $S(i,j,k)$.

Ajuda: $\sum$_i=0ⁿ i² = {2n³ +3n² +n6} .

2.

(valor 1.0 pontos)
Simule o algoritmo de Dijkstra para achar um caminho mínimo entre o vértice $1$ e todos os outros vértices no grafo abaixo.

$$\epsffile{p1f1.eps}$$

3.

(valor 2.0 pontos)
Dado um grafo $G=(V,E)$ com pesos $c$_e nas arestas e $X\; \subseteq V$, definimos $e(X)$ uma aresta tal que $c_{e(X)} = \min\{c_e \vert e=\{u,v\}, u \in X, v \not \in X\}$.

Mostre que, para todo $X\; \subseteq V$, existe uma árvore geradora mínima que contém $e(X)$.

4.

(Valor 2.0 pontos)
Em um torneio de basquete (onde não há empates), um vetor $p\; =\; (p$₁,...,p_n) é chamado de vetor de pontuação se cada $p$_i especifica o número de vitórias do $i$-ésimo time no torneio, onde cada time jogou contra cada um dos outros exatamente uma vez.

Usando uma formulação do problema como um Problema de Transporte encontre condições necessárias e suficientes (se possível, uma que seja necessária e suficiente ao mesmo tempo) para que um vetor $p$ não seja um vetor de pontuação.

5.

(valor 1.0 ponto)

Em uma iteração do método simplex para redes tem-se uma solução $x$ árvore viável correspondente à árvore $T$ desenhada abaixo. Sabe-se que o arco $e=(12,9)$ está em $E$. Complete as tabelas abaixo após incluir o arco $e$ na árvore e retirar algum arco $f$ usando a regra de Cunningham para evitar ciclagem (todos os arcos têm custo igual a 1):

$$\epsffile{p1f2.eps}$$

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

pred - 1 1 3 4 5 5 7 7 5 3 11 12 13 12

suc 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1

y 0 0

arcos (3,4) (4,5) (7,5) (7,9) (12,11) (3,11) (12,9) outros

x 5 5 5 6 8 5 0 5

6.

(valor 1.0 ponto)
Descreva a regra de Cunningham para evitar ciclagem no método simplex para redes, justificando por que, ao usar tal regra, evita-se o problema de ciclagem.

7.

(valor 2.0 pontos)
Considere o problema de transporte $(PT)$ abaixo ($n\; =\; |V|$): $$\begin{array} {ll} \min & cx \\ s.a. & Ax = b \\ & x \geq 0 \end{array}$$e o correspondente problema perturbado $(PT)$, $$\begin{array} {ll} \min & cx \\ s.a. & Ax = \tilde{b} \\ & x \geq 0 \end{array}$$onde dado um $\epsilon >\; 0$, $b$_w := b_w - (n-1)ε para a raiz $w$ e $b$_i := b_i + ε para todo $i\; \in V\; \setminus \{w\}$.

Mostre que

a. Toda solução árvore viável de $(PT)$ é não degenerada.

b. Uma árvore $T$ é viável em $(PT)$ se e só se $T$ é fortemente viável em $(PT)$.