Programação Linear e Teoria de Grafos-SUR

Fazer download em docx, pdf ou txt
Fazer download em docx, pdf ou txt
Você está na página 1de 13

UNIVERSIDADE CATÓLICA DE MOÇAMBIQUE

Instituto de Educação a Distância - IED

Resolução de Trabalho do Campo l – Programação Linear e Teoria de Grafos

Domingaldo dos Santos

Código:708224654

Curso: Lic. em Ensino de Matemática

Cadeira:

Ano de frequência: 3 º ano

Docente: dr.

Nampula, Setembro de 2024

1
Classificação

Categorias Indicadores Padrões Nota


Pontuação Subt
do
máxima otal
tutor
 Índice 0.5
 Introdução 0.5
Aspectos
Estrutura  Discussão 0.5
organizacionais
 Conclusão 0.5
 Bibliografia 0.5
 Contextualização
(Indicação clara do 2.0
problema)
Introdução
 Descrição dos objectivos 1.0

 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. Objectivos do Trabalho.....................................................................................................4

1.1.1. Geral..............................................................................................................................4

1.1.2. Específicos.....................................................................................................................4

1.2. Metodologia do Trabalho..................................................................................................4

2. Resolução da actividade.......................................................................................................5

2.1. Resolução do número 1.....................................................................................................5

2.2. Resolução do número 2.....................................................................................................8

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. Objectivos do Trabalho


1.1.1. Geral
 Demonstrar resolução dos exercícios propostos.

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

a) Formular a função objectiva e as restrições do problema:

Sejam x 1 , x 2 e x 3 as toneladas de papel pesado, medio e fino produzidas respectivamente.

Função objectivo:

Maximizar Z=6 x 1+ 4 x 2 +5 x 3, restrições:

{
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)

Configuramos a tabela inicial do simplex, adicionando as variáveis de folga s1 e s2 e


transformando as desigualdades em igualdades:

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 .

Para calcularmos a variável de saída, calculamos as razoes:

30
Razão para s1 : =15
2

40
Razão para s2 : =20
2

A menor razão é 15, então a variável de saída é s1.

Tabela 1: x 1 entra na base, s2 sai da base.

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:

Pivotamento em 2 (localizado na intersecção da linha s1 e coluna x 1).

A nova linha s1 apos 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

Tabela 2: x 3 entra na base, s2 sai da base.

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

Pivotamento em 1 (localizado na intersecção da linha s2e coluna x 2). Apos pivotamento.

A nova linha s2 apos pivotamento: x 2+ 4 x 3−s 1+ s2 =10

Tabela 3: x 2 entra na base, x 3 sai da base.

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

Tabela 4: a tabela óptima foi alcançada

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

Interpretação da solução obtida:

A solução óptima é: x 1=10 , x2 =10 e Z =100.

Portanto, o lucro máximo é Z=100 u .m .

b) Análise da situação dos recursos:


 Para pasta:

8
2 x1 + x 2 + x 3=30 ⟹ 2 ( 10 )+1 ( 10 ) +1 ( 0 )=20+10=30 toneladas (totalmente utilizados)

 Para energia eléctrica:

2 x1 +2 x 2+ 5 x 3=40 ⟹2 ( 10 ) +2 ( 10 ) +5 ( 0 ) =40 unidades (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.

Construção o modelo dual:

Variáveis duais y 1e y 2 para as restrições de pasta e energia eléctrica, respectivamente.

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

Resolver o problema dual para encontrar os valores de y 1e y 2.

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:

Vamos resolver as duas primeiras equações:

Da equação (1), temos:

2 y 1+ 2 y 2=6/(2)⟹ y1 + y 2=3 (1)

Da equação (2), temos:

y 1 +2 y 2=4

Subtraindo a equação (1) da equação (2), obtemos:

9
( y 1 +2 y 2 )−( y 1 + y 2 ) =4−3 ⟹ y 2=1
Substituindo y 2=1, na equação (1), temos:

y 1 + y 2=3 ⟹ y 1+ 1=3 ⟹ y 1=3−1 ⟹ y 1=2.

Portanto, os valores de y 1e y 2 que resolvem o problema dual são: y 1=1 e y 2=2 .

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 .

2.2. Resolução do número 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:

 X 11 =1, se o nado livre é alocado ao nadador 1; zero, caso contrário.


 X 12=1, se o estilo peito é alocado ao nadador 1; zero, caso contrário.
 X 13=1 , se o estilo borboleta é alocado ao nadador 1; zero, caso contrário.
 X 14 =1, se o estilo costas é alocado ao nadador 1; zero, caso contrário.
 X 21=1, se o nado livre é alocado ao nadador 2; zero, caso contrário.
 X 22=1, se o estilo peito é alocado ao nadador 2; zero, caso contrário.
 X 23=1 , se o estilo borboleta é alocado ao nadador 2; zero, caso contrário.
 X 24 =1, se o estilo costas é alocado ao nadador 2; zero, caso contrário.
 X 31=1, se o nado livre é alocado ao nadador 3; zero, caso contrário.
 X 32=1, se o estilo peito é alocado ao nadador 3; zero, caso contrário
 X 33=1 , se o estilo borboleta o é alocado ao nadador 3; zero, caso contrário.
 X 34 =1, se o estilo costas é alocado ao nadador 3; zero, caso contrário.
 X 41=1, se o nado livre é alocado ao nadador 4; zero, caso contrário.
 X 42=1, se o estilo peito é alocado ao nadador 4; zero, caso contrário.
 X 43=1, se o estilo borboleta é alocado ao nadador 4; zero, caso contrário.
 X 44=1, se o estilo de costas é alocado ao nadador 4; zero, caso contrário.

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.

Vamos considerar cada nadador e os estilos disponíveis:

Nadador 1: Nadador 1: Nadador 1: Nadador 1:


Livre: 54 s Livre: 51 s Livre: 50 s Livre: 56 s
Peito: 54 s Peito: 57 s Peito: 53 s Peito: 54 s
Borboleta: 51 s Borboleta: 52 s Borboleta: 54 s Borboleta: 55 s
Costas: 53 s Costas: 52 s Costas: 56 s Costas: 53 s

Para minimizar o tempo total, podemos seguir esta abordagem:

1. Escolher o nadador mais rápido para cada estilo.


2. Garantir que cada nadador seja alocado a um único estilo.

Vamos analisar as melhores combinações:

 Nado Livre: Nadador 3 (50 s)


 Nado Peito: Nadador 3 já está alocado ao nado livre, então escolhemos o próximo
mais rápido, Nadador 1 (54 s)
 Nado Borboleta: Nadador 1 já está alocado ao nado peito, então escolhemos o
próximo mais rápido, Nadador 2 (52 s)
 Nado Costas: Nadador 4 (53 s)

Portanto, a configuração que minimiza o tempo total é:

 Estilo Livre: Nadadora 3 (50 segundos)


 Estilo Peito: Nadadora 3 (53 segundos)
 Estilo Golfinho: Nadadora 1 (51 segundos)
 Estilo Costas: Nadadora 2 (52 segundos)

Dessa forma, o Nadador 1 é alocado para o estilo borboleta.

11
3. Conclusão

Em resumo, os exercícios propostos sobre programação linear abrangem conceitos


fundamentais como o método simplex, construção de modelos matemáticos e análise dos
relacionamentos entre os modelos primal e dual. A prática desses conceitos permite aos
alunos não apenas resolver problemas teóricos mas também aplicar essas técnicas em
situações práticas no mundo real. A compreensão desses tópicos é crucial para qualquer
profissional que deseje trabalhar em áreas relacionadas à otimização, pesquisa operacional ou
análise quantitativa.

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

 Barroso, G.; Ellenrieder, A. (1971). Programação Linear. Almeida Neves Editores.


 Bregalda, P. F. (1981). Introdução à Programação Linear. Rio de Janeiro: Editora
Campus.
 Ferreira, Manuel A (1995). Programação Matemática; Lisboa; Edições Silado.

13

Você também pode gostar