Usuários online

Mostrando postagens com marcador Matemática Computacional. Mostrar todas as postagens
Mostrando postagens com marcador Matemática Computacional. Mostrar todas as postagens

sexta-feira, 6 de dezembro de 2013

Notas Finais 2013 - provisório

Olá alunos,

Primeiramente, obrigado por todas as coisas que fizemos juntos nesse ano que está terminando. Agradeço a compreensão de todos, principalmente pelos problemas que tivemos com o laboratório de circuitos digitais. Espero que tenham aprendido alguma coisa comigo, assim como eu aprendi muito com vocês.

FELIZ NATAL e ANO NOVO! BOAS FÉRIAS...


CIRCUITOS DIGITAIS


MATEMÁTICA COMPUTACIONAL





Observação: se alguma nota estiver faltando, entre em contato por e-mail ou facebook: flaviofreitas.




sexta-feira, 11 de janeiro de 2013

Notas Finais 2012

Notas Finais

Caso esteja faltando alguma nota é porque não foram enviados os trabalhos.

Matemática Computacional

 


Sistemas de Apoio à Decisão



sexta-feira, 23 de novembro de 2012

Matemática Computacional - Aula 23/11/2012

Problema do Caixeiro Viajante

Vide esse link para discussão. Seria possível usarmos o conceito MinMax para solucionar o problema do caixeiro viajante? Ou outros problemas de PCV?

terça-feira, 20 de novembro de 2012

Matemática Computacional - Aula 20/11/2012

Problema do Carteiro Rural

É uma generalização do Problema do Carteiro Chinês, e, juntamente com o Problema do Caixeiro Viajante, constitui um dos principais Problemas de Roteamento de Veículos (PRV). Esses problemas estão dentro de uma classe maior de problemas denominados Problemas de Roteamento Geral (ver Letchford [1996]), e inclui um grande número de casos particulares e importantes.

O Problema do Carteiro Chinês (PCC)

A importância do modelo do carteiro chinês para a área de roteamento de veículos

As aplicações dos caminhos eulerianos se relacionam, basicamente, com problemas de atendimento sequencial, sobre um conjunto de usuários de um serviço oferecido no interior de uma rede de tráfego, tais como, entrega de correio, coleta de lixo, vendas por atacado etc.

Um problema interessante ligado ao conceito de grafo semi-euleriano é o Problema do Carteiro Chinês. Imagine um carteiro que deve percorrer um roteiro todo dia. O problema é de identificar esse roteiro de maneira a minimizar a distância total percorrida. Essa situação pode ser representada por um grafo onde as arestas correspondem às ruas e os vértices correspondem aos cruzamentos.

Se o grafo é euleriano, a solução consiste simplesmente em achar um circuito euleriano. Mais interessante é o caso de um grafo não euleriano. Consideremos por exemplo um grafo semi-euleriano, como ilustrado na figura 4. Supondo que o carteiro quer voltar ao lugar de origem, portanto com certeza para cada um dos vértices 1 e 8, uma das arestas adjacentes será atravessada no mínimo duas vezes.


Vídeo

Nesse vídeo, a respeito dos problemas das classes P e NP, veja uma breve explicação dos problemas intratáveis. Ao final, há uma explicação a respeito do problema do carteiro chinês, além do caso para grafos mistos, em que o problema se torna NP-difícil. -- Fonte: Video realizado para a disciplina de linguagens formais e autômatos da Universidade Federal de São Paulo.

terça-feira, 23 de outubro de 2012

Matemática Computacional - Aula 23/10/2012

Método Simplex

1º) O método Simplex
Vamos ver uma definição matemática do método Simplex. Pegue aqui o material para estudo teórico.

2º) Aulas em vídeo
Vamos assistir à uma aula em vídeo que demonstra o uso prático do método. A aula é única, mas está dividida em duas partes.
  1. Aula 1
  2. Aula 2
3º) Problemas
Em seguida vamos resolver os problemas da aula do dia 28/09/2012 usando o método Simplex visto na aula de hoje.

terça-feira, 16 de outubro de 2012

Matemática Computacional - Aula 16/10/2012

Revisão de Álgebra Linear
Resolução de Sistema de Equações usando o Método de Gauss-Jordan

1. Calcule a matriz inversa usando pivoteamento.

   | 1  3  6 |
a. | 4  7  2 |
   | 5  2  8 |

   | 6  8  3 |
b. | 6  1  9 |
   | 8  6  3 |

   | 4  5  6 10 |
c. | 6  2  9  3 |
   | 4  1  8  3 |
   | 3  6  1  2 |


2. Resolva cada um dos sistemas abaixo, usando os métodos de Gauss e de Jordan, e depois verifique as respostas obtidas usando programas como o Maple ou sites como Wolfram|Alpha.


sexta-feira, 28 de setembro de 2012

Matemática Computacional - Aula 28/09/2012

Exercícios

Resolva numericamente usando o Solver.

1. A Fábrica de Rádios Sinval Vulah S.A. fabrica os modelos A, B e C que tem contribuição ao lucro de $16, $30 e $50, respectivamente. As exigências de produção mínima semanal são 20.000 para o modelo A, 120.000 para o modelo B e 60.000 para o modelo C. Cada tipo de rádio requer uma certa quantidade de tempo para fabricação das partes componentes, para a  montagem  e  para  embalagem.  Especificamente,  uma  unidade  do  modelo  A  requer  0.3 horas para fabricar, 0.4 horas para montar e 0.1 para embalar. Os números correspondentes para uma unidade do modelo B são 0.4, 0.5 e 0.2, e para uma unidade do modelo C são 0.5, 0.8 e 0.3. Durante a próxima semana, a fábrica tem disponíveis 120.000 horas de tempo de fabricação, 160.000 horas de montagem e 48.000 horas de embalagem. Formule o modelo e resolva utilizando o Solver.

2. Uma fábrica de computadores produz dois modelos de microcomputadores A e B. O modelo A fornece um lucro de R$ 180,00 e B, de R$ 300,00. O modelo A requer, na sua produção, um gabinete pequeno e uma unidade de disco. O modelo B requer 1 gabinete grande e 2 unidades de disco. Existem no estoque 60 do gabinete pequeno, 50 do gabinete grande e 120 unidades de disco. Pergunta-se: Qual deve ser o esquema de produção que maximiza o lucro?

3. Uma  empresa  do  ramo  de  madeira  produz  madeira  tipo  compensado  e  madeira  serrada 
comum e seus recursos são 40 m³ de pinho e 80 m³ de canela. A madeira serrada dá um 
lucro de R$ 5,00 por m³ e a madeira compensada dá um lucro de R$ 0,70 por m³. Para produzir uma mistura de 1 metro cúbico de madeira serrada são requeridos 1 m³ de pinho e 3 m³ de canela. Para produzir 100 m³ de madeira compensada são requeridos 3 m³ de pinho e 5 m³ de canela. Compromissos de venda exigem que sejam produzidos pelo menos 5 m³ de madeira serrada e 900 m² de madeira compensada. Qual é o esquema de produção que maximiza o lucro?

4. Uma  empresa  tem  três  tipos  de  máquinas  de  processamento,  tendo  cada  uma  delas velocidade e taxas de defeitos diferentes. As máquinas do tipo I podem produzir 20 peças por  hora  com  5%  de  peças  defeituosas;  as  do  tipo  II,  15  peças  por  hora  com  10%  de defeitos e as do tipo III, 10 peças por hora sem defeitos. O custo horário de operação por máquina é US$ 2,00; US$ 1,75 e US$ 1,50, respectivamente. Devem ser processadas 3500 peças por dia  (8 horas/dia), mas só se dispõe de 8 máquinas do tipo I, 10 do tipo II e 20 do tipo III. Cada peça defeituosa custa à empresa US$ 1,00. Formule um modelo de PL para determinar a solução ótima para este problema. 

5. Uma empresa petrolífera tem três refinarias (r = 1,2,3), e pretende distribuir combustíveis do  tipo  Y  e  Z  para  quatro  mercados  diferentes  (m  =  1,2,3,4).  O  custo  de  transporte  do combustível  Y  é  2/3  do  custo  de  transporte  do  combustível  Z  e  ambos  são  diretamente proporcionais  à  distância.  A  demanda  mensal  de  Y  e  Z  para  cada  mercado  é  DYm  e  DZm respectivamente. A  produção diária de Y e Z em cada refinaria é PYr e PZr, respectivamente. 

Para um melhor uso da matéria-prima, cada refinaria deve produzir no mínimo 3 galões de Y para cada 2 galões do combustível Z. Formule um modelo de PL que minimize os custos de transporte e que, no caso de faltar combustível distribua a produção proporcionalmente à demanda. 

6. Uma empresa petrolífera tem três refinarias (r = 1,2,3), e pretende distribuir combustíveis do  tipo  Y  e  Z  para  quatro  mercados  diferentes  (m  =  1,2,3,4).  O  custo  de  transporte  do combustível  Y  é  2/3  do  custo  de  transporte  do  combustível  Z  e  ambos  são  diretamente proporcionais  à  distância.  A  demanda  mensal  de  Y  e  Z  para  cada  mercado  é  DYm  e  DZm respectivamente. A produção diária de Y e Z em cada refinaria é PYr e PZr, respectivamente. 

Antes  da  distribuição,  os  combustíveis  Y  e  Z  deverão  permanecer  em  estoque  por  pelo menos 15 e 20 dias, respectivamente. A capacidade total de estocagem de cada refinaria é limitada em Cr. Formule um modelo de PL que minimize os custos de transporte e que, no caso de faltar combustível distribua a produção proporcionalmente à demanda. 

7. Um fundo de investimentos tem até R$ 300.000,00 para aplicar em duas ações. A empresa D  é  diversificada  (tem  40%  do  seu  capital  aplicado  em  cerveja  e  o  restante  aplicado  em refrigerantes)  e  espera-se  que  forneça  bonificações  de  12%.  A  empresa  N  não  é diversificada (produz apenas cerveja) e espera-se que distribua bonificações de 20%. Para este investimento, considerando a legislação governamental aplicável, o fundo está sujeito às seguintes restrições: 
a)  O investimento na empresa diversificada pode atingir R$ 270.000,00.
b)  O investimento na empresa não-diversificada pode atingir R$ 150.000,00.
c)  Em cada produto (cerveja ou refrigerante) pode-se investir até R$ 180.000,00.
Pede-se: Qual o esquema de investimento que maximiza o lucro? 

8. Uma empresa aérea deseja comprar aviões a jato grandes, médios e pequenos. O preço de compra é de US$ 33,5 milhões para cada avião grande, US$ 25,0 milhões para cada avião médio  e  US$  17,5  milhões  para  cada  avião  pequeno.  O  conselho  diretor  autorizou  um comprometimento  máximo  de  US$  750  milhões  para  esta  compra.  Qualquer  que  seja a compra  realizada,  espera-se que haja  mercado  para  assegurar  a utilização  dos  aviões  em sua capacidade máxima. Se estima que os lucros anuais líquidos (descontando o custo de recuperação do  capital  aplicado),  é  de  US$  2,1  milhões  para  um  avião  grande,  US$  1,5 milhões para um avião médio e US$ 1,15 milhões para um avião pequeno. 

Supõe-se que a empresa poderá dispor de pilotos treinados para operar até 30 aviões novos. 
Se  forem  comprados  apenas  aviões  pequenos,  as  instalações  de  manutenção  poderiam comportar até 40 aviões, porém cada avião médio equivale a 1¼ aviões pequenos e cada avião  grande  equivale  a  1¾  aviões  pequenos,  em  termos  de  utilização  das  mesmas instalações de manutenção. Formule um modelo de programação inteira para este problema.

9. A diretora de pessoal de uma empresa de aviação comercial deve decidir quantas aeromoças deverão ser treinadas e contratadas nos próximos seis meses. As necessidades, expressas pelo  número  de  aeromoças-horas-de-voo  são  as  seguintes:  8.000  em  janeiro;  9.000  em fevereiro; 7.000 em março; 10.000 em abril; 9.000 em maio; e 11.000 em junho. 

Leva um mês de treinamento antes que uma aeromoça possa ser posta em um voo regular; assim,  uma  garota  deve  ser  contratada  pelo  menos  1  mês  antes  que  ela  seja  realmente necessária. Cada moça treinada requer requer 100 horas de supervisão de uma aeromoça experiente durante o mês de treinamento, de modo que são disponíveis 100 horas a menos para o serviço de voo por aeromoças regulares. 

Cada aeromoça experiente pode trabalhar até 150 horas em um  mês, e a empresa dispõe de  60  aeromoças  no  começo  de  janeiro.  A  política  da  empresa  é  não  demitir  ninguém. 

Porém, no fim de cada mês, aproximadamente 10% das aeromoças pedem demissão para se  dedicarem  a  outras  atividades  e  para  se  casarem.  Uma  aeromoça  experiente  custa a empresa R$ 1.500,00 por mês, enquanto que na fase de treinamento o custo é de somente R$ 900,00 (já incluindo os encargos legais). 

10. Formule um modelo de programação linear para determinar a política ótima de contratação e 
treinamento da empresa, e utilize um pacote de programação linear para obter a solução ótima. Interprete a solução encontrada. 

Uma companhia de transporte resolveu adquirir uma nova frota de caminhões para o que dispõe de R$ 4.000.000,00. Existem no mercado três modelos de caminhões que podem ser adquiridos: A, B e C. 

O caminhão A pode receber até 10 toneladas de carga, tem uma velocidade média de 56 km/h e custa R$ 80.000,00; B tem uma capacidade de 20 toneladas e uma velocidade média de 48 km/h, seu custo e R$ 130.000.00; C é provido de leito para o ajudante de motorista e, por isso, embora seja semelhante a B, a sua capacidade é de 18 toneladas e seu custo é de R$ 150.000.00. 

O caminhão A é operado por uma só pessoa e, se for utilizado em três turnos, pode rodar 18 horas por dia. 

Os caminhões B e C exigem e pessoas; enquanto B pode rodar 18 horas por dia, no regime de três turnos, C pode trabalhar 21 horas por dia. 

A companhia dispõe de 150 motoristas; as possibilidades de obter mais são muito reduzidas. 

Por outro lado, as disponibilidades de manutenção limitam a nova frota a um máximo de 30 veículos. 

Pede-se  que  se  estabeleça  um  modelo  de  programação  linear  destinado  a  determinar quantos veículos de cada tipo devem ser adquiridos, de modo que a capacidade da frota em ton.km por dia seja máxima. Resolva o problema e interprete a solução obtida. 

Matemática Computacional - Aula 25/09/2012

Exercícios Mais Complexos

Na aula de hoje veremos a modelagem de alguns exercícios mais complexos e a solução de problemas de mais de duas variáveis usando o Solver, tanto do Microsoft Excel 2010 quanto do BrOffice 3. Deixo a cargo de vocês tentarem usar o Solver como vimos na aula e resolver numericamente os problemas abaixo. Quem quiser pode baixar o software GeoGebra, que é gratuito, e tentar resolver graficamente os problemas.


O Problema do Sítio K
Um sitiante está planejando sua estratégia de plantio para o próximo ano. Por informações obtidas nos órgãos governamentais, sabe que as culturas de trigo, arroz e milho serão as mais rentáveis na próxima safra. Por experiência, sabe que a produtividade de sua terra para as culturas desejadas é a constante na tabela.

Cultura
Produtividade em kg/m²
(experiência)
Lucro por kg de Produção
(informações do governo)
Trigo
0,2
10,80 centavos
Arroz
0,3
4,20 centavos
Milho
0,4
2,03 centavos

Por falta de um local de armazenamento próprio, a produção máxima, em toneladas, está limitada a 60. A área cultivável do sítio é de 200000 m². Para atender as demandas de seu próprio sítio, é imperativo que se plante 400 m² de trigo, 800 m² de arroz e 10000 m² de milho.


Solução
Variáveis de decisão: xT, xA, xM
Função objetivo:
Max z = 2,16xT + 1,26xA + 0,812xM
Lucro por m² em centavos
Restrições:
xT ≥ 400, xA ≥ 800, xM ≥ 10000
Restrições associadas à área total disponível:
xT + xA + xM ≤ 200000
Restrição associada ao armazenamento (em quilos):
0,2xT + 0,3xA + 0,4xM ≤ 60000
Restrições de não negatividade:
xT ≥ 0, xA ≥ 0, xM ≥ 0


O Problema da Frota de Caminhões K
Uma companhia de transporte resolveu adquirir uma nova frota de caminhões para o que dispõe de R$ 4.000.000,00. Há três tipos de caminhões que podem ser adquiridos: A, B e C.
O caminhão A pode receber até 10 toneladas de carga, tem uma velocidade média de 56 km/h e custa R$ 80.000,00; B tem uma capacidade de 20 toneladas e uma velocidade média de 48 km/h, seu custo é R$ 130.000,00; C é provido de leito para o ajudante de motorista e, por isso, embora seja semelhante a B, sua capacidade é de 18 toneladas e seu custo é R$ 150.000,00.
A é operado por uma só pessoa e, se for utilizado em 3 turnos, pode rodar 18 horas por dia. B e C exigem 2 pessoas; enquanto B pode rodar 18 horas por dia, no regime de 3 turnos, C pode trabalhar 21 horas por dia.
A companhia dispõe de 150 motoristas; as possibilidades de obter mais são muito reduzidas. Por outro lado, as disponibilidades de manutenção limitam a nova frota a um máximo de 30 veículos.
Pede-se que se estabeleça o modelo de programação linear destinado a determinar quantos veículos de cada tipo devem ser adquiridos, de modo que a capacidade da frota em tonelada/km por dia seja máxima. Poderia a solução ótima ser aplicada sem nenhuma análise?

Tipo
Custo
(R$)
Capacidade
(Tonelada)
Velocidade
(km/h)
Motoristas
Turno
(h/d)
A
80000
10
56
1
18
B
130000
20
48
2
18
C
150000
18
48
2
21


Solução
Variáveis de decisão: xA, xB, xC
Função objetivo:
Max z = 10/(56x18)xA + 20/(48x18)xB + 18/(48x21)xC
Tonelada por km diário
Restrição associada ao custo total:
8xA + 13xB  + 15xC <= 400 (em R$ 10.000,00)
Restrição associada ao número de motoristas:
xA + 2xB  + 2xC <= 150 (motoristas)
Restrição associada ao número de caminhões:
xA + xB  + xC <= 30 (veículos)
Restrições de não negatividade:
xA ≥ 0, xB ≥ 0, xC ≥ 0




O Problema da Refinaria K
Em uma determinada refinaria, o petróleo bruto sofre os seguintes processamentos antes de ser transformado em gás/óleo ou gasolina bruta:
A tabela representa a capacidade máxima de processamento de cada unidade de operação.




Formular o problema de modo a maximizar os lucros totais, solucionando-o graficamente.



Solução
Deixo esse para vocês pesquisarem e tentarem resolver sozinhos.



sexta-feira, 21 de setembro de 2012

Matemática Computacional - Aula 21/09/2012

Exercícios Para Solução Gráfica

1. Suponha-se que se deseja produzir uma ração a custo mínimo pela mistura de dois produtos A e B, sendo que eles apresentam custos diferenciados:
  • Produto A: R$ 3,00 por kg
  • Produto B: R$ 4,00 por kg
Quanto às aves, sabe-se que uma ave necessita de uma alimentação de vitaminas, cujas quantidades mínimas (em unidades por semana) mostramos a seguir:
  • Vitamina 1 – 50 unidades
  • Vitamina 2 – 100 unidades
  • Vitamina 3 – 60 unidades
  • Vitamina 4 – 180 unidades
Os nutrientes acima serão obtidos dos produtos A e B, que possuem a composição a seguir:

Vitamina Composição
(unidades de vitamina por kg do produto)
Produto A
Produto B
1
5
25
2
25
10
3
10
10
4
35
20

Construa o modelo matemático com o objetivo de minimizar o custo.

2. Resolva graficamente os problemas de programação linear:
a. 

b. 

c. 


Aulas de Matemática da Computação e Sistemas de Apoio à Decisão

Aulas a Partir de 21/09/2012 em Novo Local

Olá alunos,

As aulas de Matemática da Computação e Sistemas de Apoio à Decisão a partir de hoje, 21/09/2012 sexta-feira, ocorrerão no prédio novo do DACC.

As reposições de aula começam, de acordo com o calendário de reposição de greve, a partir do dia 24/09/2012 segunda-feira. Portanto, hoje, teremos aulas normais.

domingo, 16 de setembro de 2012

Sistemas de Apoio à Decisão - Prontuário Eletrônico

Olá alunos,

Um Sistema de Apoio a Decisão (SAD) médico é todo software que auxilie os médicos na solução de problemas (Shortliffe, 1990). Uma das funções do Prontuário Eletrônico é o apoio a decisão e os SAD são as melhores ferramentas disponíveis, apesar de pouco conhecidos ou usados aqui no Brasil.

Sistemas de Apoio a Decisão no PSF « Informática Médica no PSF:

'via Blog this'

sexta-feira, 14 de setembro de 2012

Matemática Computacional - Aula 14/09/2012


Exercícios Propostos

1. Certa empresa fabrica 2 produtos P1 e P2. O lucro por unidade de P1 é de 100 u.m. e o lucro unitário de P2 é de 150 u.m. A empresa necessita de 2 horas para fabricar uma unidade de P1 e 3 horas para fabricar uma unidade de P2. O tempo mensal disponível para essas atividades é de 120 horas. As demandas esperadas para os 2 produtos levaram a empresa a decidir que os montantes produzidos de P1 e P2 não devem ultrapassar 40 unidades de P1 e 30 unidades de P2 por mês. Construa o modelo do sistema de produção mensal com o objetivo de maximizar o lucro da empresa.

Resolução
Empresa produz 2 produtos (P1 e P2)

Com relação a P1
  • Lucro é 100 u.m.
  • Tempo para produzir é 2 horas
  • Produção máxima é 40 uni/mês
Com relação a P2
  • Lucro é 150 u.m.
  • Tempo para produzir é 3 horas
  • Produção máxima é 30 uni/mês
Tempo mensal disponível para produção das duas unidades é de 120 horas

Definição das Variáveis
  • Variável a ser otimizada
           Máx.lucro: lucro máximo a ser atingido por mês
  • Variáveis básicas
           x1: Quantidade ótima de produção/mês de P1
           x2: Quantidade ótima de produção/mês de P2

Função Objetivo
Máx.lucro = 100 x1 + 150 x2

Conjunto de Restrições
2 x1 + 3 x2 ≤ 120
x1 ≤ 40             restrições técnicas
x2 ≤ 30
x1 ≥ 0; x2 ≥ 0 restrição de não negatividade

2. Uma empresa de comida canina produz dois tipos de rações: Tobi e Rex. Para a manufatura das rações são utilizados cereais e carne. Sabe-se que:
  • a ração Tobi utiliza 5 kg de cereais e 1 kg de carne, e a ração Rex utiliza 4 kg de carne e 2 kg de cereais;
  • o pacote de ração Tobi custa $ 20 e o pacote de ração Rex custa $ 30;
  • o kg de carne custa $ 4 e o kg de cereais custa $ 1;
  • estão disponíveis por mês 10 000 kg de carne e 30 000 kg de cereais.
Deseja-se saber qual a quantidade de cada ração a produzir de modo a maximizar o lucro.

Resposta
Maximizar Z = 11 x1 + 12 x2
   sujeito a
      x1 + 4 x2 ≤ 10000      restrição de carne
      5 x1 + 2 x2 ≤ 30000   restrição de cereais
      x1, x2 ≥ 0                   positividade das variáveis

3. Um vendedor de frutas pode transportar 800 caixas de frutas para sua região de vendas. Ele necessita transportar 200 caixas de laranjas a 20 u.m. de lucro por caixa, pelo menos 100 caixas de pêssegos a 10 u.m. de lucro por caixa, e no máximo 200 caixas de tangerinas a 30 u.m. de lucro por caixa. De que forma deverá ele carregar o caminhão para obter o lucro máximo? Construa o modelo do problema.

Resposta
x1: número de caixas de pêssego (OBS: laranja NÃO é variavel. TEM que levar 200 caixas)
x2: número de caixas de tangerina

Maximizar Z = 10 x1 + 30 x2 + 200 * 20
   sujeito a
      x1 ≥ 100 (pêssego)   (Dividindo tudo por 100)
      x2 ≤ 200 (tangerina)
      x1 + x2 + 200 ≤ 800 (capacidade de caminhada) para x1 = 0, x2 = 6 / para x2 = 0, x1 = 6
      x1, x2 ≥ 0

4. Uma rede de televisão local tem o seguinte problema: foi descoberto que o programa “A” com 20 minutos de música e 1 minuto de propaganda chama a atenção de 30.000 telespectadores, enquanto o programa “B”, com 10 minutos de música e 1 minuto de propaganda chama a atenção de 10.000 telespectadores. No decorrer de uma semana, o patrocinador insiste no uso de no mínimo 5 minutos para sua propaganda e que não há verba para mais de 80 minutos de música. Quantas vezes por semana cada programa deve ser levado ao ar para obter o número máximo de telespectadores? Construa o modelo do sistema.

Resposta
x1: frequência semanal de A
x2: frequência semanal de B

Número de telespectadores (Maximização)

Maximizar Z = 30000 x1 + 10000 x2
   sujeito a
      20 x1 + 10 x2 ≤ 80   restrição música
      x1 + x1 ≥ 5               restrição propaganda
      x1 ≥ 0                      restrição produção não-negativa
      x2 ≥ 0                      restrição produção não-negativa

5. Um sapateiro faz 6 sapatos por hora, se fizer somente sapatos, e 5 cintos por hora, se fizer somente cintos. Ele gasta 2 unidades de couro para fabricar 1 unidade de sapato e 1 unidade de couro para fabricar uma unidade de cinto. Sabendo-se que o total disponível de couro é de 6 unidades e que o lucro unitário por sapato é de 5 unidades monetárias e o do cinto é de 2 unidades monetárias, pede se: o modelo do sistema de produção do sapateiro, se o objetivo é maximizar seu lucro por hora.

Resposta
x1: quantidade de sapatos/hora
x2: quantidade de cintos/hora

Lucro (Maximização)

Maximizar Z = 5 x1 + 2 x2
   sujeito a
      2 x1 + x2 ≤ 6              restrição quantidade couro
      10 x1 + 12 x2 ≤ 60     restrição tempo (min.)
      x1 ≥ 0                        restrição produção não-negativa
      x2 ≥ 0                        restrição produção não-negativa


Bom proveito!

segunda-feira, 12 de dezembro de 2011

Matemática Computacional - 1ºC - Notas Finais - 2011

Matemática Computacional - Notas Finais - 1ºC - 2011

Após correção dos trabalhos recebidos, aqui está a nota final.



COMENTÁRIOS
No primeiro trabalho (30 pontos) foram entregues trabalhos completos e manuscritos. No segundo trabalho (60 pontos) muitos alunos demoraram a entregar os resultados, bem como as soluções dos problemas apresentados foram em parte, ajudadas por mim, daí a nota não ser total. A terceira nota (10 pontos) refere-se à participação em exercícios e problemas apresentados em sala de aula, e portanto, diretamente proporcional à presença.


Boas férias a todos.

sábado, 5 de novembro de 2011

Matemática Computacional - Aula 04/11/2011 (Problemas do tipo Carteiro Chinês)

Problemas do tipo "Carteiro Chinês"
Em especial o "Problema do Carteiro Rural"

INTRODUÇÃO


O Problema do Carteiro Rural (PCR) (pesquise também em inglês por Rural Postman Problem) considera que o percurso deve ser garantido sobre um subconjunto de ligações do grafo, partindo e retornando de um vértice origem dado (Lenstra & Rinooy Kan, 1981; Christofides et al., 1984; Corberán, 1994; Corberán, 1998; Corberán et al., 2001; Nobert & Picard, 1996; Eiselt et al., 1995ii; Negreiros, 1996).



O problema de roteamento em arcos capacitados (Capacitated Arc Routing Problem - CARP) consiste em visitar um subconjunto de arestas do grafo que descreve o problema, atendendo às suas demandas.


Aplicações possíveis para o CARP são a coleta de lixo urbano e a inspeção de linhas de força.


O CARP é um problema NP-difícil, mesmo no caso onde existe apenas um veículo (chamado de Problema do Carteiro Rural).


Neste caso, o uso de meta-heurísticas surge como uma estratégia de solução eficiente.


Este artigo apresenta um algoritmo genético híbrido para o CARP, que é testado em instâncias disponíveis na literatura.


Os resultados obtidos até o momento demonstram a eficiência do algoritmo proposto quando comparado com limites inferiores descritos na literatura.  





LEITURA SUGERIDA


Antes de continuar, leia os artigo Um Algoritmo Evolutivo para o Problema de Roteamento em Arcos Capacitados, Problema de Roteamento de Veículos sobre Arcos e Um Modelo de Resolução Para o Problema de Roteirização em Arcos com Restrição de Capacidade, em especial a parte sobre Carteiro Rural (página 47, salvo engano).


Você também pode se interessar pela leitura do artigo A Genetic Algorithm for the Undirected Rural Postman Problem, naturalmente em inglês.


O excelente trabalho Algoritmos para Roteamento de Leituristas merece especial atenção para a explicação de diversas e complexas fórmulas.






PROBLEMAS



O roteamento de leituristas consiste em um problema importante de natureza prática, envolvendo grandes empresas fornecedoras de energia elétrica, água e gás, nas quais trabalhadores são incumbidos de registrar o consumo de cada cliente, dispersos geograficamente nas ruas e avenidas de uma localidade. Esse problema, de difícil tratamento e elevado número de restrições, prevê a elaboração de um conjunto de rotas abertas, pelas quais os leituristas devem percorrer, atendendo a demanda por serviço de leitura. Uma solução ótima para esse problema procura minimizar as seguintes propriedades: 

  • Número de leituristas necessários para atender toda demanda; 
  • O tempo de percurso, ou seja, o tempo utilizado pelo leiturista para se deslocar de uma região a outra sem realizar qualquer leitura; 
  • Violação da carga horária do leiturista.



A motivação desse trabalho provém da demanda por soluções computacionais para esse problema, sobretudo por parte das empresas que se utilizam desse serviço, em virtude de diversos fatores, como: 

  • Dificuldade de obter soluções manualmente; 
  • Reduzida qualidade das soluções atualmente colocadas em prática; 
  • Rápida mudança do cenário consumidor, sobretudo nas metrópoles, onde se verifica uma acentuada verticalização do espaço geográfico; 
  • Necessidade de obter soluções no curto prazo. 




O roteamento de leituristas envolve um conjunto de particularidades inerentes, por exemplo: modo como o serviço de leitura se realiza (U ou Z); presença de segmentos de rua que não requerem leitura; tolerâncias máxima e mínima de carga horária; diferença entre ler e percorrer um segmento de rua. 


A natureza desse problema permite generalizá-lo como um problema de roteamento em arcos que, por sua vez, consiste em determinar um subconjunto ordenado de arestas E’ sobre um grafo  G(V,E) (E’ ⊆ E), atendendo às restrições (de demanda, capacidade, dentre outras) e minimizando determinada função custo. Ao problema de roteamento em arcos encontra-se ligada uma vasta árvore de subproblemas, dos quais o mais conhecido é o Problema do Carteiro Chinês (CPP), o qual pode ser resolvido polinomialmente sobre um grafo não-direcionado.


Problema do Carteiro Chinês (CPP)


Um vídeo introdutório bem simplificado

Um vídeo mais elaborado e mais profundo




Se algumas arestas do grafo são requeridas, enquanto outras não, o problema passa a se denominar Problema do Carteiro Rural (RPP). Foi demonstrado que o RPP é NP-Completo, portanto difícil de obter soluções ótimas para instâncias suficientemente grandes. Se for adicionada ao RPP uma restrição de capacidade, torna-se ainda mais difícil resolvê-lo até a otimalidade. Verifica-se que o problema de roteamento de leituristas (visto anteriormente) é similar ao RPP capacitado. 


Foram constatadas duas heurísticas na literatura para roteamento de leituristas, que utilizam abordagens distintas, antagônicas inclusive, para tratar do problema. Esses algoritmos foram desenvolvidos para resolver os problemas locais nos quais estavam inseridos, logo são dotados de características específicas não compartilhadas. Nesse trabalho esses algoritmos foram denominados RFCS1 (“route first, cluster second”) e CFRS1 (“cluster first, route second”).


Você ainda pode ler (em inglês) o documento Chinese Postman Problem que explica de maneira lúdica o problema do carteiro chinês. Também pode visitar o link http://eie507.eie.polyu.edu.hk/ss-submission/B7a/. O arquivo PDF The directed Chinese Postman Problem contém alguma implementação em linguagem C++.








PROBLEMA PROPOSTO


Resolver o seguinte problema do carteiro chinês


Sortear n pontos, no mínimo 4 e no máximo 10, num plano XY, de forma que os pontos tenham distâncias variadas entre si. Depois, ligar os n pontos aos outros n - 1 pontos, com k arestas (k aleatoriamente definido entre 1 e n - 1).


Determinar a menor distância total para cobrir com um passeio (ou tour) todos os arcos do grafo assim determinado. Obviamente, o circuito (ou ciclo) euleriano, quando existente no grafo, é a solução do carteiro chinês.






SOLUÇÃO


A ideia para a solução do problema proposto é o desenvolvimento de um software (em alguma linguagem visual, como o Visual Studio C#) para a solução e apresentação gráfica dos passos em busca da solução para o problema do Carteiro Chinês.

LinkWithin

Related Posts Plugin for WordPress, Blogger...

NOSSO OBJETIVO

OBJETIVO

Este blog será usado para divulgação de minhas ideias, notícias sobre tecnologia, disponibilização de links para download de materiais diversos (incluindo materiais didáticos -- que poderão ser usados em minhas aulas e/ou cursos). Gostaria de DEIXAR BEM CLARO que quaisquer materiais disponibilizados através deste blog são, tão somente, para acompanhamento de aulas e/ou cursos, e não constituem de modo algum, aulas na modalidade "ensino à distância" (EAD). Alunos têm total acesso aos materiais disponíveis, mas somente como tutoriais passo a passo. Apostilas disponibilizadas através deste blog não são materiais obrigatórios em disciplinas cursadas ou cursos ministrados.

RESPONSABILIDADE

O autor deste blog não é responsável pelo mau uso, intencional ou não, de qualquer código de programa disponibilizado aqui. Os códigos de programas disponíveis neste blog para download é e serão sempre, e tão somente, para uso didático durante o aprendizado. Seja bem-vindo.