Programação linear

Introdução à Programação Linear

Representações de redes são usadas para problemas de diversas áreas, tais como: redes de transporte, comunicação, energia, produção, distribuição, planejamento de projetos, gerenciamento de recursos, planejamento financeiro, dentre outras.

Objetivos para o estudo da programação linear : a) reconhecer os problemas que passíveis de análise pelo modelo; b) auxiliar o analista no estágio inicial da investigação; c) avaliar e interpretar inteligentemente os resultados; d) aplicar os resultados com a confiança que é adquirida somente com a compreensão dos problemas e dos resultados envolvidos.

Áreas de aplicação da programação linear:

a) problemas de alocação, ou seja, problemas envolvidos na alocação de recursos escassos entre fins alternativos, de acordo com algum critério. b) Problemas complexos de alocação que não podem ser resolvidos satisfatoriamente com as técnicas analíticas convencionais
Grande vantagem das redes: fornece representação visual e conceitual do problema.

fonte: http://www.ufjf.br/epd015/files/2010/06/modelos_otimizacao_redes.pdf
https://www.ebah.com.br/content/ABAAAAoh4AH/programacao-linear

O que é Programação Linear?

O termo Programação Linear (PL) foi utilizado pela primeira vez por George Dantzig para analisar um problema de planejamento para a força aérea americana. A PL se encaixa no campo da programação matemática e é uma área da pesquisa operacional que possue vasta aplicação em apoio à tomada de decisão. O termo “programação”, tanto linear quanto matemática, não possue ligação direta com a programação de computadores ou linguagem de programação. O termo PL foi desenvolvido originalmente para resolver problemas industriais. Assim, o termo “programação” da PL está relacionado ao planejamento de recursos escassos, visando atender as condições operacionais. O termo “linear” como o próprio nome já diz, expressa que as funções do modelo são lineares.
A programação linear busca fazer a designação ótima dos recursos disponíveis para que uma determinada atividade aconteça, ou seja, não há solução melhor do que a ofertada utilizando-se a PL (COLIN, 2007).
Puccini (1981) afirma que os problemas de PL, referem-se á distribuição eficiente de recursos limitados entre atividades competitivas, com a finalidade de atender a um determinado objetivo, por exemplo, maximização de lucros ou minimização de custos. Se tratando de programação linear, esse objetivo será expresso por uma função linear, a qual chamamos de função objetivo (F.O.). É necessário que se faça o esclarecimento do consumo destes recursos e a proporção em que se dá esse consumo. Essas informações serão fornecidas por meio de equações ou inequações lineares, uma para cada recurso. O conjunto das equações ou inequações lineares são nomeadas como restrições do modelo. As restrições estão ligadas diretamente ao tipo de problema. Exemplo: se for um problema relacionado a área de um plantio, as restrições de recursos econômicos para a realização do mesmo, assim como, a área em hectares disponíveis devem aparecer no problema.

o5t1tg.jpg

Fonte:Autor

Fonte:http://www2.uesb.br/cursos/matematica/matematicavca/wp-content/uploads/TCC-Mailton-Final.pdf

Pressuposições da PL

A programação linear necessita de quatro parâmetros, sendo eles:

2vb5rw9.jpg
Fonte: autor

Proporcionalidade

A necessidade da proporcionalidade indica que as contribuições de cada variável de decisão são proporcionais ao valor da variável de decisão. As contribuições da variável de decisão acontecem tanto na função-objetivo como nos lados esquerdos das restrições.

Aditividade

A suposição da aditividade indica que os relacionamentos entre as variáveis são sempre adições e subtrações, mas nunca outras operações. A implicação dessa suposição é que não pode haver relacionamentos de dependência (funcionais) entre as variáveis.

Divisibilidade

A divisibilidade indica que as variáveis podem ter valores fracionados, ou seja, as variáveis podem ser divididas em qualquer nível fracional. A implicação dessa suposição é que não pode haver a exigência de que as variáveis sejam inteiras.

Certeza

A suposição de certeza indica que todos os parâmetros utilizados nos modelos são conhecidos com certeza. Como muitas vezes acontece de essa suposição não ser verdadeira, utilizamos a análise de sensibilidade para alterar os parâmetros, capturando um pouco da incerteza associada a eles.

Tipos de PL

Um problema de PL pode:

  • ter apenas uma solução ótima.
  • múltiplas soluções.
  • não ter solução.
34ql8o5.png

Para um melhor entendimento destes tipos de programação linear vamos trabalhar com alguns exemplos:

Exemplo 1. Apenas uma solução ótima:

O problema da empresa MatoCerto é um exemplo de um problema de programação linear com apenas um objetivo.

Cada hectare combatido com o método de controle A gera um lucro de 60 R$/ha; com o método B: 50 R$/ha; e com o método C: 30 R$/ha. Sabendo que em estoque a empresa conta com 200 litros de insumo e uma disponibilidade de 150 horas homem por mês, qual o cenário de máximo lucro?

Ao resolver o problema no LPSolve, identificamos que solução ótimo é: combater 37.5 hectares, obtendo um lucro de R$ 1875,00. Este é o resultando ótimo e ele é único.

Exemplo 2. Soluções múltiplas

Um proprietário possui 20 hectares a disposição para plantar soja e algodão. Calcula-se que existem 1200 horas de mão de obra disponíveis para o plantio. São necessárias 20 horas para cada hectare de soja e 120 horas para cada hectare de algodão. O produtor possui R$ 60000 para investir, sabendo que um hectare de soja necessita de R$ 6000 para implantação e o algodão necessita de R$ 2000 por hectare. Como o proprietário deve dividir os 20 hectares sabendo que o lucro de cada hectare de soja é de R$ 600 e de algodão é de R$ 200?

Tanto pelo Simplex quanto pelo método gráfico, o problema apresentará múltiplas soluções como pode ser visto na figura abaixo. Existem dois pontos marcados como solução ótima. Isto indica que qualquer ponto sobre a aresta que liga os dois pontos evidenciados possui o mesmo valor de Z, ou seja, múltiplas soluções.

e63h4h.png

Figura. A figura apresenta a solução gráfica do problema acima, que apresenta múltiplas soluções. Fonte: autor

Exemplo 3. Não ter nenhuma solução ótima:

MaxZ = 90 X1 + 120 X2
S.a.
X1 <= 40
X1 >= 50
2 X1 + 3 X2 <= 180
X1, X2 >= 0
2939b1u.png

Figura. A figura apresenta a solução gráfica do problema acima, que não possui solução. As restrições são conflitantes e não determinam um espaço de soluções viáveis. Fonte: autor

Software

Existem disponíveis diversos programas de computador para resolução de problemas de programação linear. Ao longo deste material apresentaremos a maior parte das soluções no LPSolve. Mas em alguns momentos usaremos também o Excel com seu suplemento Solver ativado.

Excel

Para utilizar o Excel é necessário habilitar a ferramenta \textit{Solver}:

  1. Clique na guia Arquivo.
  2. Clique em Opções e, em seguida, clique na categoria Suplementos.
  3. Próximo ao final da caixa de diálogo Opções do Excel, verifique se Suplementos do Excel está selecionado e clique em Ir.
  4. Se o Excel exibir uma mensagem declarando que não pode executar esse suplemento e solicitar que você o instale, clique em Sim para instalá-lo.
  5. Na guia Dados, observe que um grupo Análise foi adicionado. Esse grupo contém um botão de comando Solver.

Abaixo, passo a passo da resolução de problemas de Programação Linear, por meio do Solver, no excel.

LPSolve

Programa de código aberto, disponível para download na plataforma Sourceforge. A sintaxe é muito parecida com a formulação matemática e é compatível com a \textit{sintaxe} de outros programas de otimização como LINGO e LINDO.

Tutorial de como utilizar o LPSolve

Para download:https://sourceforge.net/projects/lpsolve/

Programação Linear com o Software LINDO

Usando as informações do problema de PL e traduzindo-as para a estrutura de linguagem do programa LINDO:

A função objetivo deverá iniciar com os comandos max - maximização e min para minimização. As varáveis devem ser declaradas com no máximo 8 letras. O comando Subject to (sujeito a) deve vir antes de se declarar as restrições do problema. Ao final das restrições “)” . E por fim declarar com o comando End. Lembrando que se utiliza ponto para os decimais.

Formulação matemática:

MaximizarZ = 100x1+120x2
Sujeito a:
4x1+8<=480
5x1+6<=600
12x1+8<=540

Para solucionar o problema de PL, clicar no alvo em vermelho na figura.1 ou no comando Solver que irá gerar a análise do problema.

rgw775.png

Figura.1 Fonte: Autor

Abaixo na figura.2 os valores da solução e das varáveis do problema, apresentados na janela Reports Window:

ibdspc.jpg

Figura.2 Fonte: Autor

Link para download: https://www.lindo.com/index.php/ls-downloads

Problema MatoCerto

Volte ao problema da empresa MatoCerto que presta serviço de três métodos de controle de mato competição com as seguintes prescrições:

  • Método A. M.O.: 7h/ha. Insumo: 3 L/ha.
  • Método B. M.O.: 4h/ha. Insumo: 4 L/ha.
  • Método C. M.O.: 4h/ha. Insumo: 2 L/ha.

Cada hectare combatido com o método de controle A gera um lucro de 60 R$/ha; com o método B: 50 R$/ha; e com o método C: 30 R$/ha. Sabendo que em estoque a empresa conta com 200 litros de insumo e uma disponibilidade de 150 horas homem por mês, qual o cenário de máximo lucro?

Formulação conceitual

FUNÇÃO OBJETIVO:Maximizar o lucro da empresa com a escolha do 
método de controle.
Sujeito à:
*Limite de insumo
*Disponibilidade de horas por mês

Formulação matemática

MaxZ = 60 A + 50 B + 30 C
Sujeito a:
7 A + 4 B + 4 C <= 150
3 A + 4 B + 2 C <= 200

Para encontrar quanto de cada serviço a empresa MatoCerto deve vender para obter o maior lucro possível, sem exceder a disponibilidade dos insumos, podemos utilizar o LPSolve. Com pequenos ajustes, é possível entrar com a formulação matemática na janela do aplicativo:

2rdg4ef.png

Figura. Janela de entrada de dados no LPSolve. Fonte: autor

A solução irá aparecer um clique no botão "Play" de cor verde:

2dkilhj.png

Figura. Janela com resultado do provesso de otimização no LPSolve. Fonte: autor

O cenário que levará a empresa MatoCerto a obter o maior lucro possível é a prestação de serviço de combate B em 37.5 hectares. É evidente, que quanto mais hectares a empresa MatoCerto vender de serviço, mais lucro ela irá gerar. No entanto, infelizmente, a empresa só tem disponibilidade de insumos para 37.5 hectares. Ao realizar o combate em 37.5 hectares, a empresa estará obtendo um lucro de R$ 1875,00.

Veja que todos os valores que estamos apresentando agora, saem do programa que utilizamos para resolver o problema. Nenhum outro cenário, dentro da disponibilidade de insumos, irá gerar um lucro maior. Veja se você consegue achar um cenário melhor que o apresentado?

Erros mais comuns na modelagem utilizando o Software Lindo e o Excel

Entre os erros mais comuns cometidos por iniciantes em Programação Linear, e que você com certeza deve evitar são:

Utilizar uma variável na Função Objetivo e outra nas restrições: Se você definiu as variáveis como A1, A2, A3 etc., não poderá ter nas restrições variáveis escritas de outra forma. Por diversas vezes as pessoas colocam as variáveis A1, A2, A3 na Função Objetivo, e nas restrições colocam XA1, XA2, XA3 ou vice-versa. O software não vai entender que você está falando das mesmas variáveis e, possivelmente, lhe dará como resposta que a modelagem não tem solução, pois ele não consegue relacionar a Função Objetivo com as restrições, ou poderá entregar uma solução zerada.

Confundir restrições e variáveis de decisão: Por isso, fique atento e procure identificar o que cada parte do problema significa dentro da modelagem. A etapa de compreensão do problema é anterior à modelagem e é extremamente importante para que a modelagem fique de acordo. Se a máquina de usinagem tem um tempo disponível limitado à capacidade produtiva, ele será uma restrição, não considerando uma variável de decisão; confundir Função Objetivo e variáveis de decisão. Às vezes, por não saber bem como definir uma variável, algumas pessoas acabam utilizando termos como custos ou lucros na definição das variáveis quando essas questões de custo e de lucro geralmente fazem parte da Função Objetivo.

Trabalhar com unidades de medida ou de tempos diferentes: Se você tem algumas informações em horas e outras em minutos, escolha uma das unidades para trabalhar e transforme as demais para todas ficarem iguais. Segue o mesmo raciocínio se você tiver quantidades em Kg e toneladas no mesmo problema, por exemplo. Você deverá trabalhar com as mesmas unidades de tempo e de medida em toda a modelagem.

Troca de sinais na modelagem: Você deverá usar os sinais > (maior), < (menor) ou = (igual). Preste muita atenção, pois se você tiver uma restrição de capacidade, por exemplo, significa que não é possível produzir mais do que aquela restrição. Se você colocar um sinal de > (maior) você estará possibilitando que o software pegue valores maiores que a capacidade naquela restrição. Muita cautela a esses sinais, pois eles “contam” ao software as características do problema. Se você “contar” ao software as características erradas, a solução tem grandes chances de ficar errada também.
Ao utilizar o software, no nosso caso utilizaremos o Lindo e o Excel, devemos observar a sua linguagem para modelar corretamente.

No caso do Lindo: Para indicar um número multiplicando uma variável, basta colocar o número antes da variável, com espaços ou não, mas sem qualquer sinal de multiplicação. Salientamos que o número que multiplica a variável deve estar sempre antes da variável, pois caso contrário o software poderá interpretá-lo como se fosse outra variável. Nesse caso, se tivéssemos uma multiplicação 8xA, por exemplo, na modelagem escreveríamos como 8A ou 8 A. Nunca A8, porque assim o software interpretará como sendo outra variável, a variável A8 e não o número 8 multiplicando a variável.
Outro erro comum no software é que na sua sintaxe o ponto é separador de decimais. Portanto, se tivermos que colocar o valor 2,5 na modelagem, deveremos utilizar 2.5. Da mesma forma, se tivermos que representar o número 4.000 (quatro mil), não poderemos usar o ponto, pois o software entenderá como 4, já que o ponto é a vírgula para ele. Como separador de milhares, não utilize nada, apenas coloque os números (nesse caso, 4000).

Link para download:http://biblioteca.asav.org.br/vinculos/000045/000045c5.pdf

Ferramentas para estudo de modelagem de redes,utilizando o suplemento Solver do Excel

A programação Linear na Engenharia Florestal

A programação linear é uma poderosa ferramenta de planejamento e vem sendo largamente utilizada em todo o mundo. No setor florestal seu uso tem-se difundido bastante, principalmente nos países desenvolvidos.
Segundo Kirby (1978), no Serviço Florestal do Departamento de Agricultura Americano a programação linear vem sendo utilizada na solução de vários problemas: orçamentação, planejamento do uso do solo, transporte de madeira, manutenção de estradas e em planos de exploração.
Há vários trabalhos que mostram a utilidade da mesma para o setor florestal. Sanchez et al. (1985) demonstrou sua utilização para planejamento operacional do abastecimento florestal. Von Gadow (1982) demonstrou o uso para o planejamento anual de operações silviculturais. Rodriguez et al. (1986) demonstrou a utilização da programação linear no planejamento florestal de longo prazo, utilizando o modelo I sugerido por Clutter et al. (1983).
A inclusão de variáveis econômicas operacionais no planejamento representa um considerável aumento de sua precisão e versatilidade, com significativo ganho na aplicação dos recursos produtivos.

Introdução a Grafos

Ao contrário de muitos ramos da matemática, nascidos de especulações puramente teóricas, a
teoria dos grafos tem sua origem no confronto de problemas práticos. A teoria dos grafos
estuda objetos combinatórios -os grafos- que são um bom modelo para muitos problemas em
vários ramos da matemática, da informática, da engenharia, da química, da psicologia e da
indústria. Muitos dos problemas sobre grafos tornaram-se célebres porque são um interessante
desafio intelectual e porque têm importantes aplicações práticas. É inevitável esbarrar em
questões de complexidade computacional, pois muitos dos problemas da teoria dos grafos têm
motivação algorítmica. PEREIRA, G.M.R & CÂMARA, M.A. Algumas Aplicações da Teoria dos Grafos. Uberlândia MG UNIVERSIDADE FEDERAL DE UBERLÂNDIA. FAMAt em revista número 11- outubro de 20011.

Um grafo poder ser considerado como um par de conjuntos:
Um conjunto de coisas conhecidas como vértices e um conjunto de coisas conhecidas como arcos. Cada arco é um par ordenado de vértices. Podemos destacar dois tipos de grafos:

1 - Grafo Orientado

É um grafo "G" com um conjunto V de vértices (nós) e um conjunto U de arcos podendo ser indicado por G=(V,U).
Cada um dos arcos está associado a um par ordenado de vértices sendo o primeiro a extremidade inicial do arco e o outro a sua extremidade final.
O grafo apresentado na figura é Orientado, sendo o conjunto V = { v1 , v2 , v3 , v4 } e o conjunto
U = { u1 , u2 , u3 , u4 , u5 }. O arco u1 pode ser indicado pelo par ordenado ( v1 , v2 ) em que v1 é o extremo inicial e v2 é o extremo final; dando sequência nos demais.

2eefyoh.jpg

2 - Grafo Não Orientado

É o grafo em que a ligação entre quaisquer dois dos seus vértices não tem orientação. Neste tipo de grafo as ligações designam-se por arestas.
O grafo apresentado na figura é Não Orientado, sendo o conjunto V = { v1 , v2 , v3 , v4 } e o conjunto A = { a1 , a2 , a3 }.

2i95kqu.jpg

Os grafos podem ser utilizados para representar diversos casos como:

• Relações de parentesco de um grupo social;
• Redes rodoviárias, ferroviárias ,aéreas, eléctricas, etc;
• Circulação da informação num sistema;
• Sequência lógica da execução das tarefas de um projeto, dentre outros tipos de representações.

Caminho mínimo

Na teoria de grafos, o problema do caminho mínimo, procura encontrar a rota mínima ou o caminho mais curto entre dois pontos. Este mínimo pode ser a distância entre os pontos de origem e de destino, ou ainda, o tempo decorrido para se deslocar de um ponto a outro. É muito utilizado em problemas de redes de comunicações.

Construção do modelo matemático para caminho mínimo

Veja o modelo:

2mn3fpj.png

O nosso objetivo é partir do nó 1 ao nó 7.
Assim, vamos reproduzir o modelo matemático levando em consideração as seguintes dicas:

Função objetivo:

  • De forma organizada, montaremos todas as variáveis que começam com N1(representação do nó 1). Seguindo a sequência numérica, faremos todas as variáveis de N2, N3, … , N7. Não se esqueça de representar os pesos de cada variável. Esta sequência será importante para caso ocorra erro, a sua identificação e correção seja feita de forma mais rápida.

Restrições:

Nesta etapa, é muito importante observar as variáveis que estarão antes e depois do sinal ( = ).
É importante entendermos a estrutura da variável representada. Onde:

rcq4ah.png

Exemplo: N1N2 : representa a saída do nó 1 e a chegada no nó 2

  • Nomeie as restrições mantendo um padrão, sendo a primeira referente ao nó inicial e a segunda referente ao nó final.
  • No nó inicial, todas as variáveis serão igual a 1, ou seja, estarão do lado esquerdo do sinal ( = ). Note que todas estas variáveis começam com N1. O porquê disto é que todas estas variáveis representam a saída do N1 até o seguinte nó.
  • O nó final, todas as variáveis serão igual a 1, sendo semelhante ao nó inicial. A diferença nesta representação é que todos os finais das variáveis serão N7. O porquê disto é que todas as variáveis representam a chegada em N7.
  • Os nós intermediários serão representados por todas as variáveis que representam a chegada neste nó e todas as variáveis que representam todos os próximos nós que este nó trabalhado leva. Neste caso, todas as variáveis de chegada ao nó alvo serão representadas do lado esquerdo do sinal ( = ), e todas as variáveis que representam a saída deste nó serão representadas do lado direito.

Exemplo: N5: N2N5 + N4N5 = N5N6 + N5N7 ;

O nó 5 é representado pela restrição. Todas as variáveis que apresentam final N5 (chegada a N5) são descritos na parte esquerda do sinal ( = ). Logo, todas as variáveis com início N5 (saída de N5) são descritos na parte direita do sinal ( = ).

Assim, terminamos a formulação deste modelo, podendo resolvê-lo:

2hiczrd.png

Exemplo 1

Selecionar a melhor rota de Belo Horizonte à Diamantina,
 de maneira a formular e resolver um problema de programação linear.

Sabendo que:

BH-Sete Lagoas=76 KM
BH-Lagoa Santa=37 KM
Sete Lagoas- Paraopeba=43 KM
Lagoa Santa-Sete Lagoas=58 KM
Paraopeba-Curvelo(alternativa A)=73 KM
Paraopeba-Curvelo(alternativa B)=74 KM
Curvelo-Diamantina=129 KM
Lagoa Santa- Serro=189 KM
Serro-Diamantina(Milho Verde)=64 KM
Serro-Diamantina=89 KM
f4phqd.png
(edição autorizada)

Formulação conceitual

FUNÇÃO OBJETIVO: minimizar o caminho por meio da escolha da melhor rota entre
 Belo Horizonte e Diamantina.
Sujeito a:
* os caminhos para chegar ao destino.

Formulação matemática
MinZ:76BHSL+37BHLS+34SLPA+189LSSE+58LSSL+64SEDIA+89SEDIB+73PACVA+74PACVB+129CVDI;
S.A.:
O:BHSL+BHLS=1;
D:SEDIA+SEDIB+CVDI=1;
SL:BHSL+LSSL=SLPA;
LS:BHLS=LSSL+LSSE;
PA:SLPA=PACVA+PACVB;
CV:PACVA+PACVB=CVDI;
SE:LSSE=SEDIA+SEDIB;

Solução do problema
jfvtpf.png

O menor caminho a ser percorrido de Belo Horizonte à Diamantina será:
Belo Horizonte à Lagoa Santa.
Lagoa Santa à Serro.
Serro à Diamantina.

Problemas de caminho mínimo, também podem ser resolvidos com a utilização de Excel:

Uso de solvers para resolver problemas de programação linear:

Solver é um termo genérico para definir uma parte de um software matemático (programa de computador ou biblioteca) que ‘resolve’ um problema matemático. Ele pega a descrição do problema de alguma forma e calcula uma solução para o mesmo.
Existem diversos pacotes comerciais e gratuitos disponíveis para resolver problemas de programação linear. Em geral, eles diferem entre si pelos métodos implementados e tipos de problemas que são capazes de resolver, são exemplos:

ILOG CPLEX (IBM): Simplex, Pontos Interiores, Barrier, Branch & Bound. Resolve problemas de programação inteira, programação linear de larga escala, programação quadrática, problemas com restrições quadráticas convexas.

Gnu Linear Programming Kit (GLPK): Simplex Primal/Dual, Pontos Interiores Primal/Dual, Branch & Cut. Resolve problemas de programação linear e programação inteira mista.

AMPL (A Mathematical Programming Language) consiste em uma linguagem algébrica descritiva usada para modelar problemas de programação linear [Fourer, 1990].

GNU MathProg (GMPL):Consiste em um subconjunto da linguagem AMPL, compartilhando muitas partes da sintaxe dessa poderosa linguagem de modelagem.

ILOG CPLEX é um dos pacotes comerciais mais utilizados para resolver problemas de programação linear e programação inteira.

PROLIN:É uma ferramenta desenvolvida pela Universidade Federal de Viçosa - UFV - para solucionar problemas de Programação Linear - PPL. Agora, ele foi adaptado para a internet e está com a capacidade de solucionar PPLs de até 50 restrições e 100 variáveis. E pode ser usado via Internet.

fonte: https://homepages.dcc.ufmg.br/~vwcmorais/docs/apresentacao_solver1.pdf;

Grafos

Um grafo representa um conjunto de pontos e as suas ligações, mas quaisquer propriedades métricas são irrelevantes. Por exemplo, as distâncias entre os vértices e a forma das arestas (segmentos de reta ou outro formato mais complexo) não tem importância, na medida em que, num grafo, só é essencial saber se os vértices estão ou não ligados.
Grafos dizem-se isomorfos se existir uma relação de um para um entre os seus vértices, no sentido de que dois vértices são unidos por uma aresta num grafo, se e só se os vértices correspondentes estão unidos por uma aresta no outro grafo. Em termos correntes, pode dizer-se que a ideia de espaço e distância é irrelevante.

Um grafo diz-se simples se não contiver nenhum laço nem arestas múltiplas. No entanto, não tem arestas múltiplas, já que, para cada par de vértices, só existe, no máximo, uma aresta a ligá-los. Diz-se que existiriam arestas múltiplas no caso que se segue. Admita-se que se construiu um grafo para representar a rede viária entre as cidades A, B e C, onde cada cidade representa um vértice e as arestas são as estradas que ligam essas cidades. Se as cidades A e B têm duas estradas diferentes a uni-las, então, existem arestas múltiplas entre esses dois vértices.

2d7sh9l.png

Fonte: http://repositorio.uportu.pt/jspui/bitstream/11328/568/2/TMMAT%20107.pdf

Resolução de problema com grafos


Esse exercício simples introduz os problemas com grafos relacionando-os com situações do cotidiano, como o ciclo de amizades no Facebook.

Salvo indicação em contrário, o conteúdo desta página é licenciado sob Creative Commons Attribution-ShareAlike 3.0 License