\documentclass[11pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[brazil]{babel}
\usepackage{pifont}
\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 1 }

\vspace{0.3cm}
\end{center}

\begin{enumerate}
\item Considere que você deve escolher entre investir em um subconjunto de 7
tipos de 
investimentos $\{1, 2, \dots, 7\}$ e resolveu usar um modelo de programação
inteira com variáveis 0-1 (uma para cada tipo de investimento). Modele as
seguintes restrições: 
\begin{itemize}
\item não se pode investir em tudo;
\item pelo menos um tipo de investimento deve ser escolhido;
\item investimento 1 não pode ser escolhido se o investimento 3 for escolhido;
\item investimento 4 só pode ser escolhido se o investimento 2 for escolhido.
\end{itemize}

\item Mostre que $X = \{ x \in \{0,1\}^4 | 2x_1 + x_2 + x_3 + x_4 \le 3\}$ é
o mesmo que  

\[ \begin{array}{lll}
  X' & = \{x \in \{0,1\}^4 |&  x_1 + x_2 + x_3 \le 2 \\
     &    & x_1 + x_2 + x_4 \le 2\\
     &    & x_1 + x_3 + x_4 \le 2\}
\end{array}
\]

\item Escreva a formulação do problema do lot sizing (planejamento de
produção) para 6 períodos com demandas $(6, 7, 4, 6, 3, 8)$, custo por unidade
produzida de $(3, 4, 3, 4, 4, 5)$, custo de armazenamento $(1, 1, 1, 1, 1,
1)$, custo fixo de $(12, 15, 30, 23, 19, 45)$ e com a restrição extra de que
no máximo 10 itens podem ser produzidos em cada período. Ache a melhor solução
que você encontrar para esta instância. 

\item Considere o problema $(P_1)$ abaixo: 

\[ \begin{array}{ll}
 min & \sum_{j=1}^5 c_jx_j \\
 s.a.  &\frac{7}{4} x_1 - \frac{2}{3} x_2 + \frac{5}{2} x_3 - \frac{5}{12} x_4
 + \frac{19}{6} x_5 = \frac{8}{3} \\
       & x_j \ge 0, x_j\in Z \mbox{ para } j = 1, \dots, 5.  
\end{array}
\]

\begin{itemize}
\item Mostre que $(P_2)$ abaixo é uma relaxação de $(P_1)$. 
\[ \begin{array}{ll}
 min & \sum_{j=1}^5 c_jx_j \\
 s.a.  &\frac{3}{4} x_1 + \frac{1}{3} x_2 + \frac{1}{2} x_3 + \frac{7}{12} x_4
 + \frac{1}{6} x_5 \le \frac{2}{3} + w \\
       & x_j \ge 0, x_j\in Z \mbox{ para } j = 1, \dots, 5. \\
       & w \in Z. 
\end{array} 
\]

\item Mostre que $(P_3)$ abaixo é uma relaxação de $(P_2)$. 
\[ \begin{array}{ll}
 min & \sum_{j=1}^5 c_jx_j \\
 s.a.  &\frac{3}{4} x_1 + \frac{1}{3} x_2 + \frac{1}{2} x_3 + \frac{7}{12} x_4
 + \frac{1}{6} x_5 \le \frac{2}{3} \\
       & x_j \in R \mbox{ para } j = 1, \dots, 5. \\ 
\end{array} 
\]
\end{itemize} 
\end{enumerate}

\end{document}
