Lista pesquisa operacional fundamentos

Prévia do material em texto

IFMG Campus Formiga Pesquisa Operacional
Lista: Fundamentos de PO (10 ptos)
Prof. Diego Mello Setembro/2016
Nome: Nota:
INSTRUÇÕES Leia atentamente a lista antes de resolvê-la. A lista é individual e deve ser
entregue com exercícios manuscritos em papel sulfite, contendo os cálculos passo a passo. Os
poliedro devem ser desenhados a régua, identificando a escala dos eixos quando for conveniente.
Pode-se usar calculadora científica e softwares matemáticos (sugestão: [R]). Os exercícios desta
lista são baseados nos slides po-fundamentos.pdf, disponíveis em https://sites.google.com/
a/ifmg.edu.br/diegosilva/disciplinas/2016/pesquisa-operacional.
1 Exercícios
Exercício 1. Defina os seguintes termos, com riqueza de detalhes (definições, exemplos, etc)
(a) Combinação Linear e Combinação Linear Convexa
(b) Produto Matricial e Produto Escalar
(c) Matriz Quadrada, Triangular, Identidade
(d) Matriz Inversa
(e) Conjunto de Vetores Linearmente Independentes (L.I.)
(f) Conjunto de Vetores Linearmente Dependentes (L.D.)
(g) Determinante
(h) Posto (Rank)
(i) Matriz Singular
(j) Espaço Vetorial e Sub-Espaço
(k) Hiperplano e Semi-Espaço
(l) Base
(m) Poliedro
(n) Conjunto Convexo
(o) Conjunto Limitado
(p) Ponto Extremo
(q) Vértice de Poliedro
(r) Direção e Raio
(s) Restrições
(t) Restrições Ligadas
(u) Matriz Básica
(v) Solução Factível
(w) Solução Básica
1
(x) Solução Básica Factível (SBF)
(y) Soluções Básicas Adjacentes
(z) Solução Básica Factível Degenerada
Exercício 2. Seja o espaço vetorial R2. Responda:
(a) Desenhe o espaço R2 com os vetores unitários canônicos
(b) Desenhe os vetores u =
[
3 2
]T
e v =
[
5 7
]T
(c) Determine o ângulo formado entre os vetores u e v
(d) Apresente um vetor w ortogonal ao vetor u
(e) Determine o produto escalar entre os vetores uv e vw
(f) Calcule u′v e v′u. Compare o resultado.
(g) Calcule u′(v + w) e u′v + u′w. Compare o resultado.
Exercício 3. Sejam 3 matrizes quadradas A, B e C, todas 2× 2, com elementos aij, bij e cij , com
i, j ∈ {1 . . . 2}. Desenvolvendo algebricamente as operações, mostre que:
(a) A(BC) = (AB)C (Prop. Associativa)
(b) A(B + C) = AB +AC (Prop. Distributiva)
(c) (AB)T = BTAT (Prop. Transposta)
Exercício 4. Utilizando o método de Gauss-Jordan calcule a solução para o seguinte sistema de
equações lineares, mostrando os calculos passo a passo (sugestão: implemente o algoritmo do Slide
32 em R, e execute-o exibindo os resultados parciais).


1 5 9 1 8
7 2 1 7 10
8 11 5 20 32
3 21 9 18 17
10 5 2 9 12




x1
x2
x3
x4
x5

 =


101
62
198
245
98


Exercício 5. Dada a matriz A obtida a partir do sistema linear do Exercício 4, calcule A−1.
Exercício 6. Discuta a relação que existe entre matrizes inversíveis e rank, vetores L.I. e singula-
ridade.
Exercício 7. Discuta os três casos possíveis de solução de um sistema de equações lineares sob o
ponto de vista do número de soluções, da influência do determinante, e da dependência/independência
linear, do posto (rank) da matriz A e da singularidade da matriz A.
Exercício 8. Seja V =



 10
0

 ,

 21
0

 ,

 1−1
1



 um conjunto de vetores em R3. Responda:
(a) O conjunto de vetores é L.I. ou L.D.? Use o método de Gauss-Jordan para mostrar o fato.
(b) Qual o determinante da matriz A formado pelos três vetores?
(c) Escolha dois vetores do conjunto e desenhe-os no espaço R3
(d) Crie um quarto vetor por meio de uma combinação linear dos outros 2 escolhidos no item (c)
(e) Desenhe o vetor resultante do item (d). Identifique a relação existente entre os vetores dos itens
(c), (d) e (e).
2
Exercício 9. Discuta o processo de solução para um sistema de equações lineares simultâneas no seu
caso mais geral. Inclua na discussão a influência do posto (rank), da dependência/independência
linear de suas linhas e colunas, da separação das variáveis em básicas e não-básicas, da operação de
inversa de matriz, e de outros elementos que julgar necessários a sua explicação.
Exercício 10. Encontre alguma solução para o seguinte sistema de equações lineares simultâneas.
Indique seus cálculos e anote cada decisão tomada, justificando-a (leve em conta as escolhas refe-
rentes à linhas e colunas da matriz, a formação de uma base, a presença de linhas/colunas L.D. e
L.I., a inversão da matriz e obtenção de uma solução quando o sistema possui dimensão m × n.
Apoie-se na sua discussão do Exercício 9.


1 0 0 0 0 1 0
1 1 2 1 0 0 0
0 1 6 0 1 0 0
0 6 36 0 6 0 0
0 1 0 0 0 0 1
0 10 0 0 0 0 10


x =


8
12
4
12
6
7


Exercício 11. Seja o seguinte problema de otimização, enunciado como segue:
“Deseja-se produzir ração animal a custo mínimo para a mistura de dois produtos A e B, que
possuem custos diferenciados: o produto A custa R$ 3, 00 por kg, enquanto que o produto B
custa R$ 4, 00 por kg.
Cada ave necessita das seguintes quantidades mínimas (em unidades/semana):
Vitamina Mínimo Semanal
1 50
2 100
3 60
4 180
Nutrientes apresentados na tabela acima são obtidos a partir dos produtos A e B, que possuem
a composição (em unidades de Vitamina/Kg de produto):
Vitamina Produto A Produto B
1 5 25
2 25 10
3 10 10
4 35 20
Deseja-se saber qual é a mistura dos produtos A e B que atende aos requisitos da ração com o
menor custo possível.”
O problema enunciado acima pode ser resolvido utilizando programação linear (P.L.), visto que o
problema pode ser modelado utilizando-se um conjunto de restrições lineares que respeita os pressu-
postos da programação linear. O modelo P.L. correspondente é dado a seguir:
3
min 3x1 + 4x2 (Custo Mistura)
s.t. 5x1 + 25x2 ≥ 50 (Min. Vitamina 1/Semana)
25x1 + 10x2 ≥ 100 (Min. Vitamina 2/Semana)
10x1 + 10x2 ≥ 60 (Min. Vitamina 3/Semana)
35x1 + 20x2 ≥ 180 (Min. Vitamina 4/Semana)
x1 ≥ 0 (Não-Negatividade)
x2 ≥ 0 (Não-Negatividade)
Pergunta-se:
(a) Verifique que os pressupostos da P.L. são atendidos pelo modelo dado acima
(b) Desenhe as restrições do modelo no espaço R2, identificando cada restrição. Utilize régua e
garanta a escala entre os eixos x1 e x2
(c) Identifique os vértices (pontos extremos) do poliedro formado, rotulando-os
(d) Escolha um ponto qualquer interior ao poliedro. Verifique se o ponto atende a todas as restrições
do modelo
(e) Escolha um vértice do poliedro. Verifique se o ponto atende a todas as restrições do modelo
(f) Escolha um ponto qualquer exterior ao poliedro. Verifique se o ponto atende a todas as restrições
do modelo
(g) Escolha um ponto contido em uma aresta do poliedro (i.e., contido no segmento de reta cujos
extremos são vértices do poliedro). Verifique se o ponto atende a todas as restrições do modelo
(h) Discuta os resultados encontrados nos itens (d), (e), (f) e (g).
(i) Desenhe o vetor custo c =
[
3.00 4.00
]T
no poliedro. (i) Substitua os valores de x1 e x2 dos
vértices do poliedro na função objetivo (Custo da Mistura). Identifique qual deles retorna o menor
custo de mistura.
(j) Qual é a relação entre o vetor custo dado no item (i) e o resultado encontrado no item (j)?
(k) O modelo de programação linear apresentado pode ser entendido como o seguinte sistema de
equações lineares simultâneas quando convertido na forma padrão:


5 25 −1 0 0 0
25 10 0 −1 0 0
10 10 0 0 −1 0
35 20 0 0 0 −1


︸ ︷︷ ︸
A
·


x1
x2
x3
x4
x5
x6


=


50
100
60
180


︸ ︷︷ ︸
b
Calcule uma solução básica (factível ou não) para o problema assumindo as seguintes bases: B1 =
{A1, A2, A3, A4}, B2 = {A1, A3, A4, A5}, B3 = {A3, A1, A2, A6}. Utilize a fórmula xB = B
−1b para
obter o valor das variáveis básicas, e atribua 0 para as variáveis não básicas.
(l) Desenhe no poliedro construído no item (b)as SB geradas pelas bases acima. Existe alguma
relação entre as soluções calculadas com o poliedro?
(m) Para cada SB encontrada no item (l), verifique quantas restrições são ativadas/ligadas.
(n) Resuma todos os conceitos vistos neste exercícios, correlacionando-os.
4
2 Bibliografia
Referências
[Taha] TAHA, H. A. Pesquisa Operacional. 8a. edição. Editora Prentice-Hall Brasil, ISBN 978-85-
7605-150-3, 2007.
[Arenales et al] ARENALES, M.; ARMENTANO, V.; MORABITO, R.; YANASSE, H. Pesquisa
Operacional para cursos de engenharia. 1a. edição. Editora Campus, ISBN 978-85-3521-454-3,
2006.
[Goldbarg e Luna] GOLDBARG, Marco Cesar; LUNA, Henrique Pacca L. Otimização combinató-
ria e programação linear: modelos e algoritmos. 2a. edição. Rio de Janeiro: Elsevier, 2005.
[Bertsimas e Tsitsiklis] BERTSIMAS, D., TSITSIKLIS, J. N. Introduction to Linear Optimization
Athena Scientific, 1997. ISBN: 1886529191.
[Bazaraa et al] BAZARAA, M. S., Jarvis, J. J., SHERALI, H. D. Linear Programming and Network
Flows, 4th Edition. Wiley and Sons. ISBN: 978-0-470-46272-0.
[Boldrini et al] BOLDRINI, J. L., COSTA, S. I. R., FIGUEIREDO, V. L., WETZLER, H. G.
Algebra Linear, 3a. Edição. Editora Harbra. ISBN: 85-294-0202-2.
5