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.
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
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
terça-feira, 4 de dezembro de 2012
Matemática Computacional - Minimax
Olhe essa implementação de Jogo da Velha usando MiniMax em C#. Dará uma luz em quem ainda não desenvolveu nada do trabalho.
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
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.
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.
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
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.
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?
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.
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 da Frota de Caminhões K
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:
Construa o modelo matemático com o objetivo de minimizar o custo.
2. Resolva graficamente os problemas de programação linear:
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
- Vitamina 1 – 50 unidades
- Vitamina 2 – 100 unidades
- Vitamina 3 – 60 unidades
- Vitamina 4 – 180 unidades
| 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:
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.
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'
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
- Lucro é 150 u.m.
- Tempo para produzir é 3 horas
- Produção máxima é 30 uni/mês
Definição das Variáveis
- Variável a ser otimizada
- Variáveis básicas
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.
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!
terça-feira, 11 de setembro de 2012
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.
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"
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:
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:
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)
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.
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.
Assinar:
Postagens (Atom)
Quem sou eu
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.









