Programação Linear e Teoria de Grafos-SUR
Programação Linear e Teoria de Grafos-SUR
Programação Linear e Teoria de Grafos-SUR
Código:708224654
Cadeira:
Docente: dr.
1
Classificação
Metodologia adequada ao
2.0
objecto do trabalho
Articulação e domínio do
discurso académico
Conteúdo (expressão escrita 3.0
cuidada, coerência /
Análise e coesão textual)
discussão Revisão bibliográfica
nacional e internacional
2.0
relevante na área de
estudo
Exploração dos dados 2.5
Contributos teóricos
Conclusão 2.0
práticos
Paginação, tipo e tamanho
Aspectos
Formatação de letra, paragrafo, 1.0
gerais
espaçamento entre linhas
Normas APA 6ª
Rigor e coerência das
Referências edição em
citações/referências 2.0
Bibliográficas citações e
bibliográficas
bibliografia
2
Folha para recomendações de melhoria: A ser preenchida pelo tutor
___________________________________________________________________________
___________________________________________________________________________
___________________________________________________________________________
___________________________________________________________________________
___________________________________________________________________________
___________________________________________________________________________
___________________________________________________________________________
___________________________________________________________________________
___________________________________________________________________________
___________________________________________________________________________
___________________________________________________________________________
___________________________________________________________________________
___________________________________________________________________________
___________________________________________________________________________
___________________________________________________________________________
3
4
Índice
1. Introdução.............................................................................................................................4
1.1.1. Geral..............................................................................................................................4
1.1.2. Específicos.....................................................................................................................4
2. Resolução da actividade.......................................................................................................5
3. Conclusão...........................................................................................................................10
4. Referências bibliográficas..................................................................................................11
5
1. Introdução
A Programação Linear (PL) é uma técnica matemática amplamente utilizada para otimização
de problemas que envolvem a alocação eficiente de recursos limitados. Este trabalho tem
como objetivo resolver exercícios propostos e explorar os conceitos fundamentais da
Programação Linear, com ênfase nos métodos simplex, dual e primal simplex, que são
ferramentas essenciais para resolver problemas de otimização linear. A PL é aplicada em
diversas áreas, incluindo economia, engenharia, logística e ciência da computação, onde
decisões precisam ser tomadas sob restrições
Neste trabalho, serão apresentados exercícios propostos que ilustram a aplicação prática dos
conceitos discutidos. Através da resolução desses exercícios, espera-se proporcionar uma
compreensão mais clara dos métodos mencionados e suas inter-relações. Além disso, será
abordada a importância do entendimento do modelo dual em relação ao modelo primal e
como isso pode influenciar a escolha do método a ser utilizado na resolução de problemas
complexos.
Por fim, este estudo busca não apenas apresentar os fundamentos teóricos da Programação
Linear e Teoria de Grafos, mas também incentivar a prática através da resolução de
problemas reais que podem ser modelados utilizando essas técnicas matemáticas.
1.1.2. Específicos
Determine a solução óptima usando o algoritmo simplex
Construir o modelo dual do problema e determine a partir do quadro óptimo primal a
solução dual.
6
1.2. Metodologia do Trabalho
A metodologia de estudo utilizada neste trabalho baseou-se na pesquisa bibliográfica, tendo
como universo da análise as publicações existentes em material impresso (livros, revistas,
trabalhos de conclusão) e em meio electrónico (Internet).
2. Resolução da actividade
2.1. Resolução do número 1
Função objectivo:
{
2 x 1 + x 2+ x3 ≤ 30(restrito de pasta)
Sujeitas a 2 x 1 +2 x2 +5 x 3 ≤ 40 (restrito de energia)
x 1 ≥ 0 , x2 ≥ 0 , x 3 ≥ 0(nao negatividade)
2 x1 + x 2 + x 3+ s 1=30
2 x1 +2 x 2+ 5 x 3 + s2=40
Agora vamos identificar as variáveis de entrada e saída. A variável de entrada é aquela com o
coeficiente mais negativo na linha Z, que é x 1=−6 .
30
Razão para s1 : =15
2
40
Razão para s2 : =20
2
x1 x2 x3 s1 s2 Z b Variáveis básicas
2 1 1 1 0 0 30 s1
2 2 5 0 1 0 40 s2
-6 -4 -5 0 0 1 0 Z
7
Realizamos as operações de pivotamento:
1 1 1 1 1
2
( 2 x1 + x 2 + x 3+ s 1 )= ∙ 30→ x 1+ x + x + s1 =15
2 2 2 2 3 2
x1 x2 x3 s1 s2 Z b Variáveis básicas
1 0,38 0 0,63 -0,12 0 13,75 x1
0 0,25 1 -0,25 0,25 0 2,5 s2
0 -0,5 0 2,5 0,5 1 95 Z
x1 x2 x3 s1 s2 Z b Variáveis básicas
1 0 -1,5 1 -0,5 0 10 x1
0 1 4 -1 1 0 10 x3
0 0 2 2 1 1 100 Z
x1 x2 x3 s1 s2 Z b Variáveis básicas
1 0 -1,5 1 -0,5 0 10 x1
0 1 4 -1 1 0 10 x2
0 0 2 2 1 1 100 Z
8
2 x1 + x 2 + x 3=30 ⟹ 2 ( 10 )+1 ( 10 ) +1 ( 0 )=20+10=30 toneladas (totalmente utilizados)
Isso significa, que se alguém quisesse adquirir uma unidade de pasta como recurso, não
estaria disposto a vender, pois toda pasta disponível já esta sendo utilizada na produção
óptima.
Avaliação da venda de uma unidade de pasta adicional. Analisaremos o valor sombra (preço
dual) do recurso pasta a partir da solução dual. Construímos o modelo dual e resolvemos para
os valores sombra.
Função objectivo dual (minimizar o custo dos recursos): MinW =30 y 1 +40 y 2
Sujeito a:
{
2 y 1 +2 y 2 ≥ 6
y 1 +2 y 2 ≥ 4
y 1+5 y 2 ≥5
y1 , y2 ≥ 0
Para resolver o problema dual, podemos usar o método analítico ou numérico como
progranacao linear. Para simplicidade, vamos resolver analiticamente.
Primeiro, reescrevemos as desigualdades para formar um sistema de equações que podem ser
resolvidas:
y 1 +2 y 2=4
9
( y 1 +2 y 2 )−( y 1 + y 2 ) =4−3 ⟹ y 2=1
Substituindo y 2=1, na equação (1), temos:
O valor que eu pagaria por uma unidade adicional de energia eléctrica é igual ao preço
sombra desse recurso, que pode ser encontrado na solução dual. Analisando o que obtemos na
resolução dual, o valor do preço sombra para energia eléctrica y 2=2 .
O treinador deseja designar os nadadores para os diferentes estilos de modo a obter o menor
tempo possível para completar o medley. Considere que a variável de decisão do modelo
matemático para este problema é x i j , que recebe o valor igual a ''1'' se decidirmos que o estilo
''i'' será alocado ao designado ''j'', sendo ''0'' se decidirmos o contrário, de tal forma:
10
Para determinar a alocação que minimiza o tempo total, precisamos analisar os tempos de
cada nadador em cada estilo e escolher a combinação que resulta no menor tempo total.
11
3. Conclusão
12
Portanto, os exercícios propostos em programação linear proporcionam uma compreensão
abrangente dos métodos utilizados para otimização em contextos diversos. O aprendizado do
método simplex, aliado à habilidade de construir modelos adequados e à análise das relações
entre os modelos primal e dual, forma uma base sólida para qualquer estudante ou
profissional que deseje aplicar técnicas de programação linear em situações práticas. A
prática contínua com esses conceitos não apenas reforça o conhecimento teórico, mas
também aprimora as habilidades analíticas necessárias para resolver problemas complexos.
4. Referências bibliográficas
13