MAC-IME-USP CARLOS EDUARDO FERREIRA

SALA 297A TEL.: 3091 6140

E-MAIL cef@ime.usp.br

MAC 330 - Programação Inteira - MAC 5780

Segundo semestre de 2002

Lista de Exercício 3

1. Considere a árvore de enumeração abaixo, de um problema de minimização.
   
   $$\epsffile{l3f1.eps}$$
   
   
   a. Quais são os melhores limitantes inferior e superior que conhecemos para o valor da solução ótima do problema?
   b. Quais nós podem ser desativados e quais devem ainda ser explorados?

2. Considere o problema abaixo
   
   $$\begin{array}{llclcl} \max & 9x_1 & + & 5x_2 \\ & 4x_1 & +... ...1 & + & 2x_2 & \leq & 19 \\ & & & x & \in & Z^2_+ \end{array}$$
   
   
   Resolva o problema por branch-and-bound.

3. Considere o problema da mochila, e suponha que os itens estão ordenados de forma que $\frac{v_1}{f_1} \geq \frac{v_2}{f_2} \geq \dots \geq \frac{v_n}{f_n}$, onde $v_i$ são os valores e $f_i$ os pesos dos itens. Suponha ainda que $\sum_{i=1}^{s-1} f_i \leq F$ e $\sum_{i=1}^{s} f_i > F$.

   a. Mostre que a solução da relaxação linear do problema é dada por:
   

   $$x_i = \left\{ \begin{array}{ll} 1, & i = 1, \dots, s-1; \\ (... ..._s, & i = s; \\ 0, & i = s+1, \dots, n. \end{array} \right.$$
   
   

   b. Usando o resultado acima para dar limitantes, resolva usando Branch and Bound a instância em que $F=12$, $f = (5, 3, 8, 7)$ e $v = (17, 10, 25, 17)$.

4. Para cada exemplo abaixo é dado um conjunto viável $X$ e um ponto $x$. Encontre uma inequação válida para $X$ que corta o ponto $x$.

   a.
   

   $$X = \{(x,y) \in R^2_+ \times \{0,1\} : x_1 + x_2 \leq 2y, x_1 \leq 1, x_2 \leq 1 \}$$
   
   
   
   
   $$(x_1, x_2, y) = (1, 0, 0.5)$$
   
   

   b.
   

   $$X = \{x \in Z^5_+ : 9x_1 + 12x_2 + 8x_3 + 17x_4 + 13x_5 \geq 50\}$$
   
   
   
   
   $$x = (0, \frac{25}{6}, 0, 0, 0)$$
   
   

5. Mostre que a inequação $y_2 + y_3 + 2y_4 \leq 6$ é válida para
   
   $$X = \{ y \in Z^4_+ : 4y_1 + 5y_2 + 9y_3 + 12y_4 \leq 34 \}$$
   
   

6. Considere o problema
   
   $$\begin{array}{lrl} \min & x_1 + 2x_2 & \\ & x_1 + x_2 & \ge... ...{5}{2} x_2 & \geq \frac{5}{2} \\ & x \in Z^2_+ & \end{array}$$
   
   
   O ponto $x^* = (\frac{15}{4}, \frac{1}{4})$ é a solução ótima da relaxação linear do problema. Encontre uma inequação válida que corta $x^*$.