\documentclass[11pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[brazil]{babel}
\usepackage{pifont}
\usepackage{epsf}
\setlength{\textheight}{8.5in}
\setlength{\textwidth}{6.5in}
\setlength{\evensidemargin}{0pt}
\setlength{\oddsidemargin}{0pt}
\setlength{\topmargin}{-30pt}


\begin{document}
\noindent
{\footnotesize {\sc MAC--IME--USP}}  \hfill {\footnotesize {\sc Carlos Eduardo Ferreira}}

\vspace{-1mm}
\hfill {\footnotesize {\sc Sala 297A Tel.: 3091 6140}}

\vspace{-1mm}
\hfill {\footnotesize {\sc e-mail} cef@ime.usp.br}

\vspace{1cm}

\begin{center}
{\large\bf MAC 330 - Programação Inteira - MAC 5780 }
\end{center}

\begin{center}
{\bf Segundo semestre de 2002}
\end{center}

\begin{center}
{\large  Lista de Exercício 3}

\vspace{0.3cm}
\end{center}

\begin{enumerate}

\item 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? 

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

\item 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; \\
(F - \sum_{i=1}^{s-1} f_i)/f_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)$. 

\item 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) \]


\item 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 \} \]

\item Considere o problema 
\[ \begin{array}{lrl}
\min & x_1 + 2x_2 & \\
     & x_1 + x_2 & \geq 4 \\
     & \frac{1}{2} x_1 + \frac{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^*$. 
\end{enumerate}

\end{document}

