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 1

1. 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:
   • não se pode investir em tudo;
   • pelo menos um tipo de investimento deve ser escolhido;
   • investimento 1 não pode ser escolhido se o investimento 3 for escolhido;
   • investimento 4 só pode ser escolhido se o investimento 2 for escolhido.

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

   
   

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

3. 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.

4. Considere o problema $(P_1)$ abaixo:

   
   

   $$\begin{array}{ll} min & \sum_{j=1}^5 c_jx_j \\ s.a. &\frac... ...x_j \ge 0, x_j\in Z \mbox{ para } j = 1, \dots, 5. \end{array}$$
   
   
   • 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... ...Z \mbox{ para } j = 1, \dots, 5. \\ & w \in Z. \end{array}$$
     
     

   • 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... ... & x_j \in R \mbox{ para } j = 1, \dots, 5. \\ \end{array}$$