UNIVERSIDADE CATÓLICA DE MOÇAMBIQUE

Instituto de Educação à Distância

Resolução de Exercícios

Estudante: Nivaldo José Augusto e Código: 708216779

Curso: Licenciatura em Ensino de Matemática

Disciplina: Programação Linear e

Teoria de Grafos

Ano: 3o

Tutor: Rabi Francisco Pedro Mussa

Gaza, Agosto de 2023

 Classificação

Categorias Indicadores Padrões Nota

Pontuação
do Subtotal
máxima
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
1.0
objectivos
 Metodologia adequada
2.0
ao 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
Aspectos tamanho de letra,
Formatação 1.0
gerais paragrafo, 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
Recomendações de melhoria: A ser preenchida pelo tutor

_
Índice

1.0.Introdução ............................................................................................................................. 1

2.Objectivos ................................................................................................................................ 1

2.1.Geral .............................................................................................................................. 2

2.2.Específicos .................................................................................................................... 2

3.0.Desenvolvimento .................................................................................................................. 3

4.0.Conclusão ........................................................................................................................... 10

5.0.Referências Bibliográficas .................................................................................................. 11

1.0.Introdução
**Introdução ao Trabalho de Campo: Resolução de Exercícios em Programação Linear e
Teoria de Grafos**

A disciplina de Programação Linear e Teoria de Grafos desempenha um papel fundamental no

desenvolvimento de habilidades analíticas e algorítmicas dos estudantes, capacitando-os a
abordar uma ampla gama de problemas do mundo real. A combinação desses dois campos
oferece ferramentas poderosas para otimização e análise de sistemas complexos, seja na gestão
de recursos, logística, engenharia, economia ou outras áreas.
Neste trabalho, abordaremos exercícios que exigem a aplicação de técnicas de Programação
Linear e Teoria de Grafos para encontrar soluções ótimas ou avaliar cenários específicos. A
resolução desses exercícios envolverá a formulação adequada dos problemas, a escolha das
variáveis e restrições relevantes, a seleção de métodos de resolução apropriados e a
interpretação dos resultados obtidos.
Além de desenvolver habilidades quantitativas, este trabalho de campo também incentivará a
capacidade dos alunos de pensar de forma lógica e criativa para modelar situações do mundo
real em termos matemáticos. A colaboração e a troca de ideias entre os alunos serão
incentivadas, uma vez que muitos problemas podem ter abordagens diferentes e enriquecedoras.
No decorrer deste trabalho, exploraremos exemplos práticos que variam desde a otimização de
produção e distribuição até a análise de redes sociais e de transporte. Ao final, os participantes
deverão ter adquirido uma compreensão aprofundada das técnicas de Programação Linear e
Teoria de Grafos, bem como a capacidade de aplicá-las de maneira eficaz para enfrentar
desafios do mundo real.
Em suma, este trabalho de campo proporcionará aos alunos a oportunidade de mergulhar nas
complexidades da Programação Linear e Teoria de Grafos através da resolução prática de
exercícios, preparando-os para abordar problemas do mundo real de forma analítica, sistemática
e inovadora.

2.Objectivos

1
 2.1.Geral
 Aplicar a programação linear para resolução de problemas e teoria de grafos.

2.2.Específicos
 Resolver exercícios concretos de Programação Linear;

 Descrever grafos;

 Classificar os grafos.

2
 3.0.Desenvolvimento
1. Pensando em atrair o público da classe mais exigente, o fabricante de triciclos motorizado
vulgo “txopela” decidiu introduzir um modelo de luxo que será produzido, junto com o
habitual modelo básico, em uma nova fabrica recentemente instalada em Maputo. O
departamento de marketing e vendas realizou uma pesquisa de mercado que indicou que, no
máximo, 1.500 unidades do modelo de luxo e 6.000 unidades do modelo básico podem ser
vendidos no próximo mês. Além disso, constatou-se que o volume totalda produção dos dois
modelos de “txopela” não pode exceder a 5.000 por mês. Aempresa já contratou um certo
numero de empregados e, com isso, dispõe de uma forca de trabalho de 25.000 homens-hora
por mês. Cada modelo de luxo requer dez homens- hora e cada modelo básico requer oito
homens-hora para ser montado. O lucro unitário domodelo de luxo e de 30.000 MT, e do
modelo básico e de 15.000 MT.

a) Ajude a empresa a determinar quanto produzir de cada modelo de txopela,

formulandoum modelo de programação linear.
b) Resolva o problema utilizando o método gráfico mostrando todos os passos.
Interprete o resultado.
Resolução 1
1.a) passo 1:
Recursos Modelo luxo Modelo básico Disponibilidade
Modelo luxo/ básico 1500 6000 5000
Forca de trabalho 10 8 25000
Lucro unitário do modelo 30000 15000 _______________

Variáveis de decisão
X1 - Número de “txopelas” produzidas no Modelo de luxo.
X2 - Número de “txopelas” produzidas no Modelo de básico.
Maximizar Z= 30000X1 + 15000X2

3
 X1,X2 ≥ 0

1.b)

Passo 3:
1. Lucro:em(1500,0)( 1500 ,0 ):eu=30.000⋅1500+15.000⋅0=45,000,000eu=30.000⋅1500+15.000⋅
0=45 ,000 ,000
2. Lucro:em(0,6.000)( 0 ,6.000 ):eu=30.000⋅0+15.000⋅6.000=90,000,000eu=30.000⋅0+15.000⋅6.
000=90 ,000 ,000
3. Lucro:em(2000,3.000)( 2000 ,3000 ):eu=30.000⋅2000+15.000⋅3.000=105,000,000eu=30.000⋅
2000+15.000⋅3.000=105 ,000 ,000
4. Lucro:em(1250,875)( 1250 ,875 ):eu=30.000⋅1250+15.000⋅875=58,125,000eu=30.000⋅1250+
15.000⋅875=58 ,125 ,000
Z= 0
30000X1 + 15000X1 = 0
30000X1
X2 = − 15000

X2 = -2X1 recta Z

r1: r2:

4
 X2

Dominio de solucao
3500

36

15/3 2500 X1

r2
r1

SPL={X1=0;X2=3125 Zmáx=46875000 }
2.Dado o problema de Programação Linear abaixo:

𝑀i𝑛 𝑍 = 3𝑥1 + 2𝑥2

𝑆𝑢j𝑒i𝑡𝑜 𝑎: 𝑥1 + 2𝑥2 ≥ 10

𝑥1 + 𝑥2 ≥

8 2𝑥1 +

𝑥2 ≥ 12

𝑥1, 𝑥2 ≥ 0

a) Determine o Dual associado a este problema.

b) Verifique que [𝑥1, 𝑥2, 𝑥3] = [0, 1, 1] é uma solução Dual-viável.
c) Utilize o Teorema da Complementaridade de Folgas para verificar se a solução
dada em
b) e solução óptima do problema dual.
d) Utilize o Teorema da Dualidade Forte para verificar se a solução dada em b) é
soluçãoóptima do problema dual.

5
Resolução 2

a) Determinar o Dual associado a este problema:

O problema de programação linear dado é:

Min Z = 3X1 + 2X2

Para escrever o Dual, precisamos introduzir variáveis de folga para cada restrição do problema primal e
criar uma variável dual correspondente para cada restrição do primal. Chamaremos as variáveis de folga
de s1, s2 e s3, e as variáveis duais correspondentes de y1, y2 e y3.

O problema Dual é:

Max W = 10y1 + 8y2 + 12y3

Sujeito a:

b) Verificar que [X1, X2, X3] = [0, 1, 1] é uma solução Dual-viável:

Primeiramente, a notação [X1, X2, X3] não foi definida anteriormente. Assumiremos que [X1, X1, S1, S1,
S3], onde S1, S2 e S3 são as variáveis de folga correspondentes às três restrições do problema primal.

Vamos verificar se [X1, X2, S1, S2, S3] = [0, 1, 1, 0, 0] é uma solução dual-viável. Substituindo os
valores na formulação dual:

W = 10y1 + 8y2 + 12y3

Com y1 = 0, y2 = 1, y3 = 0:

W = 10*0 + 8*1 + 12*0= 8 logo concluímos que [X1, X2, X3] = [0, 1, 1] é uma solução Dual-viável.

6
c) Utilizar o Teorema da Complementaridade de Folgas para verificar se a solução dada
em b) é solução óptima do problema dual:
O Teorema da Complementaridade de Folgas diz que se uma solução primal factível e uma
solução dual factível são encontradas de modo que todas as variáveis de folga e as variáveis
duais associadas são iguais a zero, então ambas as soluções são ótimas.
Na solução dada em b), todas as variáveis de folga (S1, S2, S3) e as variáveis duais associadas
(y1, y2, y3) são iguais a zero. Portanto, de acordo com o Teorema da Complementaridade de
Folgas, essa solução primal e dual é ótima.

d) Utilizar o Teorema da Dualidade Forte para verificar se a solução dada em b) é solução

óptima do problema dual:

O Teorema da Dualidade Forte estabelece que, se existirem soluções primal e dual factíveis,
então o valor ótimo do problema primal é igual ao valor ótimo do problema dual.

Na solução dada em b), calculamos o valor ótimo do problema dual que é W = 8.

Comparando o valor ótimo do problema primal (que é a função objetivo do primal) com o valor
ótimo do problema dual, vemos que ambos são iguais a 8. Portanto, de acordo com o Teorema
da Dualidade Forte, a solução dada em b) é uma solução ótima do problema dual.

2.A partir do Método Simplex determine a solução óptima do seguinte problema de

Programação Linear apresentando todos os passos.

𝑀𝑎𝗑: 𝑍 = 2𝑥1 + 6𝑥2

𝑆𝑢j𝑒i𝑡𝑜 𝑎: 𝑥1 + 2𝑥2 ≤ 10

2𝑥1 + 𝑥2 ≤ 8

𝑥1 + 2𝑥2 ≥ 3

𝑥1, 𝑥2 ≥ 0
Resolução

Método Simplex para o problema de Programação Linear:

O problema de programação linear dado é: Max Z = 2x1 + 6x2

7
Vamos usar o método Simplex para encontrar a solução ótima passo a passo.
Passo 1: Formar a tabela Simplex inicial:
Base x1 x2 S1 S2 S3 RHS
S1 1 2 1 0 0 10
S2 2 1 0 1 0 8
S3 -1 -2 0 0 1 -3
Z -2 -6 0 0 0 0
a
1 iteração

2a iteração

Solução: X1 =10; X2 = 9/4; X3= 6; X4= 6; X5= 13; Zmax = 48

8
4.Grafo e suas propriedades:
Resolução
A matriz de adjacência dada é:
01110
10001
10001
10000
01100

a) Sequência de graus dos vértices de G: A sequência de graus dos vértices é [3, 2, 2, 1, 2].

b) Existem caminhos v4 - v5 de comprimento 2? Não, não existem caminhos v4 - v5 de

comprimento 2, pois não há uma aresta direta entre v4 e v5.

c) G não é euleriano e é semi-euleriano: Um grafo é euleriano se todos os vértices têm grau

par, e é semi-euleriano se exatamente dois vértices têm grau ímpar.

No grafo dado, os vértices v1, v3 e v5 têm grau ímpar (3, 2 e 2, respectivamente), o que significa
que o grafo não é euleriano. No entanto, como exatamente dois vértices têm grau ímpar, ele é
semi-euleriano e tem um caminho euleriano aberto.

5.Matriz de incidência

1 0 0 1 0 0 0 1 0 10

11101000001

01010100101

00001111000

00100011010

6.Determine o caminho mais curto de:

a) A para J;

A→C→B→F→G→H→J

b) A para I;

A→C→B→F→I

c) D para J;

D→F→G→H →

9
4.0.Conclusão
Ao longo deste trabalho de campo, exploramos as interseções fascinantes entre Programação
Linear e Teoria de Grafos, duas disciplinas poderosas que desempenham um papel essencial na
resolução de problemas complexos e na otimização de processos em diversas áreas. Através da
resolução de exercícios práticos, os participantes puderam aplicar conceitos teóricos em
situações do mundo real, desenvolvendo suas habilidades analíticas, de modelagem e de
resolução de problemas.

Durante as atividades, os alunos tiveram a oportunidade de compreender a importância de

escolher as abordagens certas para diferentes tipos de problemas, selecionando métodos de
otimização adequados e explorando estruturas de grafos para analisar redes e conexões. A
formulação precisa dos problemas, a interpretação dos resultados obtidos e a capacidade de
comunicar as soluções de maneira clara foram habilidades fundamentais desenvolvidas ao
longo desse trabalho.

À medida que concluímos este trabalho de campo, os participantes estão mais bem preparados
para enfrentar problemas da vida real que envolvem otimização, alocação de recursos, análise
de redes e muito mais. A combinação de Programação Linear e Teoria de Grafos oferece uma
base sólida para abordar uma variedade de cenários complexos, capacitando os alunos a tomar
decisões embasadas em dados, a identificar padrões em redes intricadas e a propor soluções
inovadoras para desafios contemporâneos.

No final, esperamos que os participantes apliquem as habilidades adquiridas neste trabalho de

campo não apenas em suas carreiras acadêmicas, mas também em suas jornadas profissionais,
contribuindo para a resolução de problemas e aprimoramento de sistemas em uma ampla gama
de indústrias. A interseção entre Programação Linear e Teoria de Grafos continuará a
desempenhar um papel vital na construção de um mundo mais eficiente e conectado,
impulsionado pelo poder da análise matemática e algorítmica.

10
 5.0.Referências Bibliográficas
1.ACKOFF, RL, Sasieni, M.W(1968) – Fundamentals of Operations Research, John Wiley &
Sans, Inc USA.

2.ANDRADE, EL (1998) – Introdução à Pesquisa Operacional – métodos e modelos para a

análise de

decisão, 2a edição, editora LTC, RJ, Brasil

3.FARIA, AN(1978) – Dinâmica da Administração – perspectivas e projectos, editora LTC,

Rio de Janeiro,

Brasil;

4.HILLIER, FS; Gerald, J.L(1995) – Introduction to Operations Research – sexth Edition,

McGraw-Hill, International Editions, Singapure;

5.TAHA, HA(2003) – Operations Research an Introduction, sixth edition, Prentice – Hall

International, Inc, USA.

6.TAVARES, Luís Valadares, OLIVEIRA, Rui Carvalho, THEMIDO, Isabel Hall, CORREIA,
FranciscoNunes (1996) Investigação Operacional. Editora McGraw-Hill de Portugal, Ldª;

7.HILL, Manuela Magalhães, SANTOS, Mariana Marques dos (1999) Investigação

Operacional Vol. 1 – Programação Linear. Edições Sílabo;

8.HILL, Manuela Magalhães, SANTOS, Mariana Marques dos (2008) Investigação

Operacional -Vol. 3 – Transportes, Afectação e Optimização de Redes. Edições Sílabo;

9.HILLIER, Frederick S., LIEBERMAN, Gerald J. (2006) Introdução à Pesquisa Operacional,

8ª edMcGraw-Hill Interamericana do Brasil, Ldª.

10.TAHA, Hamdy A. (2007) Operations Research: An Introduction, 8th Ed. Pearson Prentice
Hall.

11