ARA7524 Pesquisa Operacional
Segundo Semestre - 2014
Quinta Lista de Exercı́cios
1. – (LW) Suponha que você está interessado em investir em projetos do seguinte conjunto de projetos {1, . . . , 7}. Modele as seguintes restrições usando
variáveis binárias (0 − 1):
(i) Você não pode investir em todos eles.
(ii) Você deve escolher pelo menos um deles.
(iii) O investimento 1 não pode ser escolhido se o investimento 3 é escolhido.
(iv) O investimento 4 pode ser escolhido somente se o investimento 2 também é escolhido.
(v) Você deve escolher ou ambos os investimentos 1 e 5, ou nenhum dos
dois.
(iv) Você deve escolher ou pelo menos um dos investimentos 1, 2, 3, ou pelo
menos dois investimentos de 2, 3, 5, 6.
2. – (LW) Formule um programa inteiro para o problema de colocar n
rainhas em um tabuleiro de xadrez n × n de tal forma que nenhuma rainha ataque qualquer outra rainha (ou seja, não pode existir duas rainhas
compartilhando qualquer linha, coluna, ou diagonal).
3. – (Martin Grötschel) Você conhece o problema Sudoku? Você pode visitar a página http://www.247sudoku.com/ para conhecê-lo. O Sudoku é
normalmente definido sobre uma matriz 9 × 9. É claro que ele pode ser
generalizado! Um problema Sudoku pode ser generalizado por uma matriz A com dimensão n2 × n2 subdividida em n2 submatrizes de dimensão
n × n (n ∈ N). Os números a serem preenchidos devem estar no conjunto
{1, . . . , n2 }. Por exemplo, para n = 3, teremos uma matriz A com dimensão
9 × 9 subdividida em 9 submatrizes de dimensão 3 × 3 cada. Os números a
serem preenchidos estão no conjunto {1, . . . , 9}.
Formule um programa inteiro que decide se uma dada instância F do
Sudoku generalizado tem uma solução ou não. Denote por fi,j ∈ F como
sendo o valor que está na linha i e coluna j da instância dada.