UNIVERSIDADE CATLICA DE PERNAMBUCO
CENTRO DE CINCIAS SOCIAIS
CURSO:
ADMINISTRAO DE EMPRESAS
PESQUISA OPERACIONAL MDULO 1
2013.2
Prof.: Egenilton Rodolfo de Farias
Email: [email protected]
Pesquisa Operacional em Administrao Mdulo 1 Pgina 1
UNIVERSIDADE CATLICA DE PERNAMBUCO PR-REITORIA ACADMICA
CENTRO DE CINCIAS SOCIAIS
PLANO DE ENSINO
Semestre
2013.2
CDIGO: ADM1407 DISCIPLINA: Pesquisa Operacional
TURMA: CURSO: Administrao
HORA/AULA 72 PROFESSOR: Egenilton Rodolfo de Farias
EMENTA Apresentar os principais mtodos de otimizao e algoritmos de pesquisa operacional e a prtica correspondente, aplicveis s principais funes da gesto organizacional, numa perspectiva de interdisciplinaridade com as principais funes da gesto organizacional e de interao da teoria com a prtica.
CONTEXTUALIZAO
O curso visa integrao contnua entre a teoria e as aplicaes dos conceitos de Pesquisa Operacional fornecendo assim,
aos alunos, o instrumental necessrio para entender e manusear os principais modelos de aplicao e/ou anlise de dados.
OBJETIVO GERAL
Proporcionar aos alunos uma viso prtica e objetiva da utilizao dos recursos da Pesquisa Operacional no dia a dia da
empresa.
OBJETIVOS ESPECFICOS
Oferecer, atravs de bases conceituais e desenvolvimento de frmulas, as ferramentas de anlise de dados que contribuem
para uma tomada de deciso consciente e estratgica.
CONTEDO Definio de pesquisa operacional e construo de modelos. Programao linear: formulao e mtodo grfico; diretrizes para a formulao de modelos de programao linear; problema de maximizao e minimizao da funo objetivo; soluo grfica e problemas com duas variveis de deciso; alguns casos especiais; formulao geral do
problema de programao linear e sua anlise e soluo via o mtodo simplex. Os problemas de transporte e
designao e seus casos especiais. Teoria da deciso: problemas de deciso. Deciso tomada sob risco e rvores
de deciso. Deciso tomada sob incerteza e seus critrios. Simulao: o mtodo de Monte Carlo. Casos particulares
de simulao terica. Introduo teoria dos jogos: jogos com dois jogadores e somo zero. Estratgias puras e
mistas. Equilbrio de Nash e exemplos aplicados s empresas. Introduo teoria das filas. A estrutura bsica de
uma fila: a distribuio exponencial e a distribuio de Poisson. Modelo de fila com um ou mltiplos servidores.
Modelos de deciso de fila: custo e nvel de aspirao.
METODOLOGIA/RECURSOS DIDTICOS
Aulas expositivas. O plano de ensino da disciplina contemplar metodologia direcionada a realizao de trabalhos prticos,
desenvolvidos no ambiente organizacional e/ou com dados e informaes reais, visando a interao da teoria com a prtica.
AVALIAO DA APRENDIZAGEM:
A prtica ser obtida atravs de exerccios que, aps cada assunto ministrado, sero resolvidos detalhadamente e propostos
outros, acompanhados das respostas de modo que o aluno efetue o treinamento fora do horrio de aula, pois para se
dominar a Estatstica as aulas s no bastam, h que se exercitar bastante. Todos os alunos devem portar uma calculadora
durante o curso sem a qual no ser possvel o acompanhamento na resoluo dos problemas em sala de aula. As
avaliaes, em nmero de duas, escritas, uma em cada unidade de aprendizagem, com notas variando de zero a dez.
BIBLIOGRAFIA BSICA ANDRADE, E. L. Introduo pesquisa operacional: mtodos e modelos para anlise de decises. 4.ed. Rio de
Janeiro: LTC, 2009. MOREIRA, D. A. Pesquisa operacional: curso introdutrio. So Paulo: Thomson Learning, 2007. TAHA, H. A. Pesquisa operacional: uma viso geral. So Paulo: Pearson Prentice Hall, 2008.
BIBLIOGRAFIA COMPLEMENTAR EHRLICH, P. J. Pesquisa operacional: um curso introdutrio. So Paulo: Atlas, 1991. ELLENRIEDER. A. VON. Pesquisa operacional. Rio de Janeiro: Almeida Neves, 1971. LACHTERMACHER, G. Pesquisa operacional na tomada de decises: modelagem em Excel. Rio de Janeiro:
Elsevier,2007. RAGSDALE, C. T. Modelagem e anlise de deciso. So Paulo: Cengage Learning, 2009. SILVA, E. M. et al. Pesquisa operacional: programao linear. So Paulo: Atlas, 1999.
Pesquisa Operacional em Administrao Mdulo 1 Pgina 2
CRITRIOS DE AVALIAO DO 1 GQ
CRITRIO DE AVALIAO DA PROVA DO 1 GQ
Primeiramente feita uma anlise geral da prova: O aluno tentou responder a todas as questes?
Foi utilizado as frmulas, a HP 12C ou ambas ( opcional ao aluno o mtodo de resoluo)? A prova est
esmerada ou o aluno fez vrias tentativas para resolver as questes? Qual a ordem escolhida pelo aluno
para resoluo do problema, da mais difcil para a mais fcil ou o contrrio?
Em seguida feito a anlise de cada questo. No mtodo tradicional, as questes so corrigidas
de acordo com a ordem numrica, o que no permite fazer um estudo mais aprofundado do porqu o
aluno errou. Por isso a opo da ordem de correo da que o aluno desenvolveu melhor para a que ele
menos desenvolveu. Esse mtodo ajuda a esclarecer os seguintes aspectos: O aluno chegou resposta
correta? O resultado final foi direto ou ele desenvolveu os dados para chegar na resposta correta? Caso
no tenha chegado resposta correta, at que ponto ele avanou no desenvolvimento da resposta? O
aluno identificou os dados corretamente? A frmula usada estava correta? Houve erro no clculo? (O
aluno informado por escrito e verbalmente diversas vezes que o uso de calculadora individual, no
podendo ser divida entre colegas durante a prova. Se o aluno esqueceu ele tem que arcar com a
responsabilidade) O aluno errou por falta de ateno ou porque no sabia o mtodo de resoluo? O
mesmo erro foi verificado em todas as questes? Em algum momento o aluno tentou usar meio ilcito
para responder, olhou para a prova do colega ou estava com memria auxiliar?
Para que o aluno possa comparar a sua prova com o de outro colega necessrio que ele analise
as questes pela metodologia de correo supramencionada, escalonado as questes que o aluno
melhor respondeu at a que menos respondeu. A comparao pela ordem numrica desconsidera todos
os aspectos que foram mencionados acima.
CRITRIO DE AVALIAO DO TRABALHO DO 1 GQ
Em relao a avaliao do trabalho so analisados os seguintes aspectos: O aluno seguiu o roteiro
do trabalho? Houve fraude? O aluno copiou parcialmente ou totalmente de algum site ou livro? Levando
em considerao o tema designado, o aluno se aprofundou ou tratou o assunto superficialmente? Como
est a organizao do trabalho?
Pesquisa Operacional em Administrao Mdulo 1 Pgina 3
BNUS ACRESCICO NOTA DO 1 GQ
No primeiro dia de aula o aluno informado que, a critrio do professor, o aluno pode receber
algum bnus de acordo com o grau de comprometimento com a disciplina. Nessa ocasio a turma
informada que o valor desse bnus adicionado a soma dos pontos das questes respondidas.
Essa bonificao apenas um incentivo participao do aluno e comportamento disciplinar
exemplar em sala de aula.
Ela construda ao longo do semestre e se torna crescente ao passo que o aluno observado
respondendo as questes, tirando dvidas ao final da aula ou por email, participando ativamente da aula,
oferecendo sugestes para o aperfeioamento contnuo da metodologia utilizada.
Por outro lado, a bonificao se torna decrescente medida que o aluno demonstra pelas suas
atitudes descomprometimento com a aula.
O quantitativo de faltas no tem sido um bom indicador desse comprometimento, pois alguns
alunos tm enfrentados problemas delicados de ordem estritamente pessoais, como parentes
gravemente doentes, perdas de familiares, problemas no emprego, que tem geral um nmero de faltas
prximo ao limite aceitvel de 25% da carga horria. H alunos que tem uma quantidade de faltas acima
da mdia, digamos 12 ou mais faltas at 18 no mximo, mas que por email tem sido muito participativo,
mostrando o quanto desenvolveu de determinados exerccios, tirando dvidas, etc, o que demonstra um
certo grau de comprometimento com a disciplina.
Pesquisa Operacional em Administrao Mdulo 1 Pgina 4
CONCEITOS DE DECISO E O ENFOQUE GERENCIAL DA PESQUISA
OPERACIONAL A expresso Pesquisa Operacional foi utilizada pela primeira vez durante a Segunda Guerra Mundial, quando pesquisadores buscavam mtodos para facilitar decises estratgicas de operaes militares. Uma deciso um curso de ao escolhido pela pessoa, como o meio mais efetivo sua disposio, para alcanar os objetivos pretendidos.
Principais caractersticas do processo de deciso Processo seqencial: conseqncia de uma srie de fatores anteriores que criaram asa bases
para se chegar a ela. Processo complexo: envolve uma inter-relao entre pessoas, responsabilidades pelo servio,
comunicao e sistemas de informaes, cdigos de tica e moral e, s vezes, interesses e objetivos dos participantes. Alm disso, os processos podem variar dentro da empresa quanto ao(s):
Tamanho do grupo de deciso Tipos de sistemas de informaes gerenciais Tipos de decises que devem ser tomadas Estilo de liderana dos administradores Nvel da deciso dentro da empresa
Processo que implica em valores subjetivos: o mtodo pelo qual o valor de julgamento do gestor colocado na deciso estritamente pessoal.
Processo em ambiente institucional: todas as empresas tm uma estrutura organizacional personalizada que influencia e muitas vezes condiciona o processo de tomada de deciso.
Classificao das decises Nvel estratgico: quanto mais as atividades e os resultados de uma organizao forem afetados
pela deciso, mais estratgica ela ser. Grau de estruturao: uma deciso to mais bem estruturada quanto mais estreitamente o
processo puder ser acompanhado ou mesmo repetido, em outras ocasies e, s vezes, at mesmo em outros ambientes.
Para problemas com alto grau de estruturao, o gerente pode contar com tcnicas de Pesquisa Operacional, tais como Programao Linear, Teoria das Filas, Teoria dos Estoques, Programao Dinmica etc.
O enfoque gerencial da pesquisa operacional Enfoque clssico: nesse enfoque, a ateno principal estava mais voltada para a tcnica de
soluo (rigor matemtico do algoritmo) e para a obteno de uma soluo tima. Por outro lado, essa linha tradicional frustrava os administradores pela pouca flexibilidade dos modelos que s respondiam a perguntas padronizadas.
Enfoque atual: nessa abordagem qualitativa, o enfoque central deslocado do mtodo de soluo (geralmente um algoritmo matemtico complexo) para a formulao e para a modelagem ou seja, para o diagnstico do problema.
Fases de um estudo de pesquisa operacional Definio do problema:
Descrio exata dos objetivos do estudo; Identificao das alternativas de deciso existentes; Reconhecimento das limitaes, das restries e das exigncias do sistema.
Construo do modelo: O modelo mais apropriado para a representao do sistema est condicionado a definio do problema. A qualidade de todo o processo seguinte conseqncia do grau de representao da realidade que o modelo venha a apresentar.
Soluo do modelo: No caso de modelos matemticos, a soluo obtida pelo algoritmo mais adequado, em termos de rapidez de processamento e preciso da resposta. Nesse caso, ela chamada de soluo tima.
Pesquisa Operacional em Administrao Mdulo 1 Pgina 5
Validao do modelo: Ele vlido se, quando ocorrer inexatido em representar o sistema, ele for capaz de fornecer uma previso aceitvel do comportamento do sistema e uma resposta que possa contribuir para a qualidade da deciso a ser tomada. Um mtodo comum para se testar a validade do sistema analisar seu desempenho com dados passados do sistema e verificar se ele consegue reproduzir o comportamento que o sistema manifestou.
Implementao da soluo: Avaliadas as vantagens e a validade da soluo obtida, esta deve ser convertida em regras operacionais. A implementao, sendo uma atividade que altera uma situao existente, uma das etapas crticas do estudo.
Avaliao final: nessa fase, um fator que tem papel primordial a experincia do pessoal envolvido no estudo. No se deve esquecer que um modelo apenas uma representao simplificada, que no capta todas as caractersticas da realidade.
Perguntas para reviso 1. Quais so as caractersticas de um processo de tomada de deciso que possibilitam o uso de
tcnicas quantitativas no apoio e na preparao da deciso?
Soluo: O processo de tomada de deciso seqencial; trata-se de um processo complexo, que implica valores subjetivos e que desenvolvido em um ambiente institucional cujas regras so mais ou menos definidas. 2. Por que as decises com alto grau de estruturao so propcias s aplicaes de Pesquisa
Operacional?
Soluo: As decises que tm um alto grau de estruturao so fceis de modelar, dispe de uma grande quantidade de dados histricos e contam com menor grau de incerteza. 3. Justifique os critrios da qualidade da deciso.
Soluo: Uma deciso de boa qualidade cria o estado desejado (eficcia), otimiza a utilizao dos recursos (eficincia) e segue o processo adequado (consistncia do curso de ao). 4. Por que a escolha do problema certo a ser resolvido um dos fatores de qualidade?
Soluo: A escolha do problema certo a ser resolvido um dos fatores de qualidade porque significa manter o foco correto e objetivar a ao para a soluo. 5. Por que o nvel de conhecimento pode ser um obstculo qualidade de uma deciso?
Soluo: A informao de importncia crucial para a tomada de deciso. Quanto mais alto o nvel de informao necessrio para a tomada de deciso, maior o custo (tempo e dinheiro); quanto mais baixo, mais incerto o ambiente para a tomada de deciso 6. Quais as vantagens do enfoque atual da Pesquisa Operacional sobre o enfoque clssico?
Soluo: Pelo enfoque atual, a soluo tima de um problema apenas um referencial; mais importante o processo ou seja, importa menos o rigor matemtico da soluo, e mais o esprito crtico e a sensibilidade para se identificar o problema certo a ser resolvido e distinguir quais informaes so fundamentais e quais so acessrias para a deciso. 7. Do ponto de vista da preparao da deciso, quais so as vantagens da abordagem sistmica?
Soluo: A abordagem sistmica possibilita um aumento de conhecimento e da experincia em termos de tcnicas e mtodos para soluo de problemas; permite a antecipao dos resultados por meio de mtodos matemticos e estatsticos; e cria uma viso sistmica e intuitiva. 8. Justifique a importncia da experincia pessoal na avaliao dos resultados de um estudo de
Pesquisa Operacional.
Soluo: Nenhum modelo capta todas as caractersticas da realidade. A experincia do administrador sempre ter um papel relevante no processo de tomada de deciso.
Leitura recomendada
Andrade, Eduardo Leopoldino. Introduo pesquisa operacional. 3 ed. Rio de Janeiro: LTC, 2004. Captulos 1.
Pesquisa Operacional em Administrao Mdulo 1 Pgina 6
MODELAGEM DE PROBLEMAS GERENCIAIS Diversas vantagens podem ser citadas quando o administrador utiliza um processo de modelagem para a tomada de deciso:
Foram os administradores a tornarem explcitos seus objetivos.
Permitem a identificao e o armazenamento das diferentes decises que influenciam os objetivos, bem como dos relacionamentos entre as decises.
Buscam a identificao das variveis a serem includas e em que termos elas sero
quantificveis.
Tipos de Modelos O relacionamento entre as variveis em um modelo , na maioria das vezes, escrito em termos matemticos. Existem vrias formas de gerar e utilizar essas relaes, e por isso existem diversos tipos de modelos. O modelo mais apropriado para um dado problema depende de vrios fatores como:
Natureza matemtica das relaes entre as variveis;
Objetivos do tomador de decises;
Extenso do controle sobre as variveis de deciso;
Nvel de incerteza associado com o ambiente da deciso.
Com base nestas consideraes, podemos dividir os modelos em dois grandes tipos: Modelos de simulao;
Modelos de otimizao.
Ser analisado mais detalhadamente o modelo de otimizao, objetivo principal da disciplina.
CONSTRUO DOS MODELOS DE OTIMIZAO
Definio do problema Deve ser definido o objetivo bsico do problema, ou seja, a otimizao a ser alcanada. Por exemplo, maximizao de lucros, ou de desempenhos, ou de bem-estar social; minimizao de custos, de perdas, de tempo. O administrador deve reconhecer que existe um problema que precisa da melhor soluo, pela pesquisa dos valores timos das variveis.A opo pelo modelo de otimizao, ao invs de simulao poder ser mais til quando:
Existirem muitas variveis de deciso, tornado o modelo de simulao lento.
Houver restries nos recursos ou variveis que tornem complexo o processo de escolha dos valores das variveis.
Os sistemas requerem preciso nos clculos das variveis, para respeitar restries ou
evitar grandes variaes no resultado final.
Identificao das variveis relevantes Por exemplo, nmero de mquinas, a rea a ser explorada, as classes de investimento disposio etc. Normalmente, assume-se que todas estas variveis possam assumir somente valores positivos. O conjunto de variveis relevantes para um modelo de otimizao inclui:
Pesquisa Operacional em Administrao Mdulo 1 Pgina 7
Variveis de deciso: So definidas pelo analista como fornecedoras das informaes que serviro de base para a tomada de deciso. Exemplo: Se o problema for aplicar dinheiro em um projeto de expanso de uma fbrica para obter o mximo retorno, uma varivel de deciso poder ser a taxa de retorno.
Variveis controlveis ou endgenas: uma varivel gerada pelo prprio modelo durante o
processo de soluo, sendo dependente dos dados fornecidos, das hipteses estabelecidas e da prpria estrutura do modelo.
Variveis no-controlveis ou exgenas: So os fatores ou dados externos fornecidos ao
modelo e que representam as hipteses levantadas ou as condies que devem ser respeitadas.
Formulao da funo objetivo O objetivo ou problema analisado pelo modelo ser representado por uma funo objetivo, a ser maximizada ou minimizada; para que ela seja matematicamente especificada, devem ser definidas as variveis de deciso envolvidas.
Formulao das restries As variveis normalmente esto sujeitas a uma srie de restries, normalmente representadas por inequaes. Por exemplo, quantidade de equipamento disponvel, tamanho da rea a ser explorada, capacidade de um reservatrio, exigncias nutricionais para determinada dieta etc
Escolha do mtodo matemtico de soluo Tendo definido o problema, devemos agora escolher um mtodo matemtico apropriado para a soluo do modelo. A escolha feita tendo em vista o tipo de modelo matemtico criado e as anlises e questes para as quais o modelo deve fornecer subsdios.
Aplicao do mtodo de soluo O mtodo de soluo simplesmente um exerccio matemtico que pode ser realizado manualmente ou por computador.
Avaliao da soluo Nessa fase do modelo, tanto pode ser aceito como pode ser necessrio proceder as correes, para incorporar novas restries, novas variveis ou novos critrios.
Leitura recomendada
Andrade, Eduardo Leopoldino. Introduo pesquisa operacional. 3 ed. Rio de Janeiro: LTC, 2004. Captulos 2.
Pesquisa Operacional em Administrao Mdulo 1 Pgina 8
MODELO EM PROGRAMAO LINEAR
O modelo matemtico de programao linear composto de uma funo objetiva linear e de restries tcnicas representadas por um grupo de inequaes tambm lineares.
Roteiro 1. Variveis de deciso Explicar as decises que devem ser tomadas e representar as possveis decises atravs de variveis chamadas variveis de deciso. 2. Objetivo Identificar o objetivo da tomada de deciso. Eles aparecem geralmente na forma da maximizao de lucros ou receitas, minimizao de custos, perdas etc. 3. Restries Cada restrio imposta na descrio do sistema deve ser expressa como uma relao linear (igualdade ou desigualdade), montadas com as variveis de deciso.
Exemplo 01 Certa empresa fabrica dois produtos P1 e P2. O lucro unitrio do produto P1 de 1.000 unidades monetrias e o lucro unitrio de P2 de 1.800 unidades monetrias. A empresa precisa de 20 horas para fabricar uma unidade de P1 e de 30 horas para fabricar uma unidade de P2. O tempo anual de produo disponvel para isso de 1.200 horas. A demanda esperada para cada produto de 40 unidades anuais para P1 e 30 unidades anuais para P2. Qual o plano de produo para que a empresa maximize seu lucro nesses itens? Construa o modelo de programao linear para esse caso.
Soluo: 1. Variveis de deciso O que deve ser decido o plano de produo, ou seja, quais as quantidades anuais que devem ser produzidas de P1 e P2.
Portanto, as variveis de deciso sero 1X e 2X
1X quantidade anual a produzir de P1
2X quantidade anual a produzir de P2
2. Objetivo O objetivo maximizar o lucro, que pode ser calculado:
Lucro devido a P1: 1.000 1X (lucro por unidade de P1 quantidade produzida de P1)
Lucro devido a P2: 1.800 2X (lucro por unidade de P2 quantidade produzida de P2)
Lucro total: 21 X1800X1000L
Objetivo: maximizar 21 X1800X1000L
3. Restries As restries impostas pelos sistemas so:
Disponibilidade de horas para produo: 1200 horas.
Horas ocupadas com P1: 20 1X (uso por unidade quantidade produzida)
Horas ocupadas com P1: 30 2X (uso por unidade quantidade produzida)
Total em horas ocupadas na produo: 21 X30X20
Restrio descritiva da situao: 21 X30X20 1200
Pesquisa Operacional em Administrao Mdulo 1 Pgina 9
Disponibilidade de mercado para os produtos (demanda) Disponibilidade para P1: 40 unidades
Quantidade a produzir de P1: 1X
Restrio descritiva da situao: 1X 40
Disponibilidade para P2: 30 unidades
Quantidade a produzir de P2: 2X
Restrio descritiva da situao: 2X 30
Resumo do modelo:
max 21 X1800X1000L
Sujeito a:
Restries tcnicas
30X
40X
1200X30X20
2
1
21
Restries de no negatividade 0X
0X
2
1
Leitura recomendada
Silva, Ermes Medeiros da. & et al. Pesquisa operacional para os cursos de: economia,
administrao e cincias contbeis 3 ed. So Paulo: Atlas, 1998. Captulos 2, pginas 14 a 18.
Pesquisa Operacional em Administrao Mdulo 1 Pgina 10
EXERCCIOS
Exerccio 01 Para uma boa alimentao, o corpo necessita de vitaminas e protenas. A necessidade mnima de vitaminas de 32 unidades por dia e a de protenas de 36 unidades por dia. Uma pessoa tem disponvel carne e ovos para se alimentar. Cada unidade de carne contm 4 unidades de vitaminas e 6 unidades de protenas. Cada unidade de ovo contm 8 unidades de vitaminas e 6 unidades de protenas. Qual a quantidade diria de carne e ovos que deve ser consumida para suprir as necessidades de vitaminas e protenas com o menor custo possvel? Cada unidade de carne custa 3 unidades monetrias e cada unidade de ovo custa 2,5 unidades monetrias.
Soluo: 1. Variveis de deciso Devemos decidir quais as quantidades de carne e ovos a pessoa deve consumir no dia. As
variveis de deciso sero 1X e 2X
1X quantidade de carne a consumir no dia
2X quantidade de ovos a consumir no dia
2. Objetivo O objetivo minimizar o custo, que pode ser calculado:
Custo devido a carne: 3 1X (custo por unidade quantidade a consumir de carne)
Custo devido aos ovos: 2,5 2X (custo por unidade quantidade a consumir de ovos)
Custo total: 21 X5,2X3C
Objetivo: minimizar 21 X5,2X3C
3. Restries As restries impostas pelos sistemas so:
Necessidade mnima de vitamina: 32 unidades.
Vitamina de carne: 4 1X (quantidade por unidade unidades de carne a consumir)
Vitamina de ovos: 8 2X (quantidade por unidade unidades de ovos a consumir)
Total de vitaminas: 21 X8X4
Restrio descritiva da situao: 21 X8X4 32
Necessidade mnima de protena: 36 unidades
Protena de carne: 6 1X (quantidade por unidade unidades de carne a consumir)
Protena de ovos: 6 2X (quantidade por unidade unidades de ovos a consumir)
Total de Protena s: 21 X6X6
Restrio descritiva da situao: 21 X6X6 36
Resumo do modelo:
min 21 X5,2X3C
Sujeito a:
Restries tcnicas 36X6X6
32X8X4
21
21
Restries de no negatividade 0X
0X
2
1
Pesquisa Operacional em Administrao Mdulo 1 Pgina 11
Exerccio 02 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 couro para fabricar uma unidade de cinto. Sabendo-se que o total disponvel de couro de 6 unidades e que o lucro unitrio por sapato de 5 unidades monetrias e o do cinto de 2 unidades monetrias, pede-se: o modelo do sistema de produo do sapateiro, se o objetivo maximizar seu lucro por hora.
Soluo:
1X nmero de sapatos por hora
2X nmero de cintos por hora
mx 21 X2X5L
s.a.
0X ,0X
6X1X2
60X12X10
21
21
21
6 sapatos/hora = 10 min por sapato; 5 cintos/hora = 12 min por cinto.
Exerccio 03 Um vendedor de frutas pode transportar 800 caixas de frutas para sua regio de vendas. Ele necessita transportar 200 caixas de laranjas a 20 u.m. de lucro por caixa, pelo menos 100 caixas de pssegos a 10 u.m. de lucro por caixa, e no mximo 200 caixas de tangerinas a 30 u.m. de lucro por caixa. De que forma dever ele carregar o caminho para obter o lucro mximo? Construa o modelo do problema.
Soluo:
1X quantidade de caixas de pssegos
2X quantidade de caixas de tangerinas
mx 4000X30X10L 21
s.a.
0X ,0X
200X
100X
600XX
21
2
1
21
Ele necessita transportar 200 caixas de laranja, portanto 200 20 = 4000
Leitura recomendada
Silva, Ermes Medeiros da. & et al. Pesquisa operacional para os cursos de: economia,
administrao e cincias contbeis 3 ed. So Paulo: Atlas, 1998. Captulos 2, pginas 18 a 21.
Pesquisa Operacional em Administrao Mdulo 1 Pgina 12
APLICAES DE PROGRAMAO LINEAR: PROBLEMAS DE MISTURAS
O problema da mistura, em geral, consiste na obteno ou fabricao de um produto, aqui chamado de mistura, combinando-se alguns materiais disponveis na natureza ou disponveis no mercado (no exemplo de rao, pode ser milho, farinha de osso etc.). Problemas de mistura surgem em vrios processos industriais, como na produo de adubos, sucos concentrados de laranja, ligas metlicas, raes para determinados animais etc. e geralmente so parte de um problema mais geral de planejamento e controle da produo. A mistura produzida a partir de ingredientes que possuem os componentes desejados no novo produto (na rao, os componentes so protenas, vitaminas etc.) e que devem satisfazer determinadas especificaes (na rao, as especificaes so resultados de pesquisa em nutrio animal). A composio de cada ingrediente conhecida, isto , as propores dos componentes de cada ingrediente so dadas, como tambm o seu custo unitrio. Deseja-se determinar as quantidades de cada ingrediente que devemos utilizar para obter uma mistura com a composio especificada e com o menor custo possvel.
Formulao matemtica do problema da mistura n Nmero de ingredientes que podem ser utilizados na produo da mistura m Nmero de componentes relevantes para a mistura
jX Quantidade do ingrediente j que deve ser utilizada em uma unidade de mistura, j=1,2,...,n
ija Frao do componente i no ingrediente j, i=1,...,m e j=1,...,n
jb Frao do componente i na mistura, i=1,...,m
jc Custo de uma unidade do ingrediente j, j=1,...,n
Minimizar nn2211 XCXCXCC
s.a.
0X,,0X ,0X
1XXX
bXaXaXa
bXaXaXa
bXaXaXa
n21
n21
mnmn22m11m
2nn2222121
1nn1212111
Ele necessita transportar 200 caixas de laranja, portanto 200 20 = 4000
Exemplo 01 Uma agroindstria deve produzir um tipo de rao para determinado animal. Essa rao produzida pela mistura de farinha de trs ingredientes bsicos: osso, soja e resto de peixe. Cada um desses trs ingredientes contm diferentes quantidades de dois nutrientes necessrios a uma dieta nutricional balanceada: protena e clcio. O nutricionista especifica as necessidades mnimas desses nutrientes em 1 kg de rao. Cada ingrediente adquirido no mercado com certo custo unitrio ($/kg). Na tabela a seguir, os dados do problema so apresentados. Os ingredientes podem ser constitudos por outros elementos, mas que no so importantes para o problema em questo.
Pesquisa Operacional em Administrao Mdulo 1 Pgina 13
Dados para o problema da rao Ingredientes
Nutrientes Osso Soja Peixe Rao Protena 0,2 0,5 0,4 03 Clcio 0,6 0,4 0,4 05 Custos ($/kg) 0,56 0,81 0,46 Determinar em que quantidades os ingredientes devem ser misturados de modo a produzir uma rao que satisfaa s restries nutricionais com o mnimo custo.
Soluo:
1X Quantidade (em kg) de osso que deve ser utilizada em um unidade (1kg) da rao.
2X Quantidade (em kg) de soja que deve ser utilizada em um unidade (1kg) da rao.
3X Quantidade (em kg) de peixe que deve ser utilizada em um unidade (1kg) da rao.
mn 321 X46,0X81,0X56,0C
s.a.
0X,0X,0X
1XXX
5,0X4,0X4,0X6,0
3,0X4,0X5,0X2,0
321
321
321
321
Leitura recomendada
Arenales, MARCOS. & et al. PESQUISA OPERACIONAL. Rio de Janeiro: Elsevier, 2007. Captulo 2, pginas 15 a 20.
Pesquisa Operacional em Administrao Mdulo 1 Pgina 14
APLICAES DE PROGRAMAO LINEAR: PROBLEMAS DE TRANSPORTE Esses problemas referem-se ao transporte ou distribuio de produtos dos centros de produo aos mercados consumidores. Os produtos podem ser os mais variados possveis: petrleo, equipamentos, mquinas, produo agrcola etc. O problema consiste em transportar o produto dos centros de produo aos mercados consumidores de modo que o custo total de transporte seja o menor possvel. O transporte deve ser efetuado respeitando-se as limitaes de oferta e atendendo demanda.
Formulao matemtica do problema de transporte n Nmero de destinos para um produto m Nmero de origens para um produto
ijX Quantidade, no negativa, transportada do produto i para o destino j, i = 1, ..., m e j=1,2,...,n
ia Oferta do produto na origem i
jb demanda do produto no destino j
ijc Custo de transportar uma unidade do produto da origem i para o destino j
Minimizar
m
1i
n
1j
ijijXCC
s.a.
n ..., 1, j e m ..., 1, i 0X
n..., 1, j bX
m ..., 1, i aX
1
i
m
1i
ij
i
n
1j
ij
Exemplo 01 Considere uma companhia distribuidora de bebidas que tem 2 centros de produo (m = 2) Recife e Natal e 3 mercados consumidores principais (n = 3) Pernambuco, Paraba e Rio Grande do Norte. O custo unitrio de se transportar uma unidade do produto de cada centro de produo a cada mercado consumidor dado na tabela a seguir. Nessa tabela tambm so apresentadas as demandas de cada mercado e a quantidade mxima disponvel do produto em cada centro de produo no prximo perodo.
Dados para o problema de transporte da companhia de bebidas Mercado
Centro de suprimento Pernambuco Paraba Rio G. Norte Suprimento disponvel Recife 4 2 5 800 Natal 11 7 4 1000 Demanda dos mercados 500 400 900
Determinar as quantidades a ser transportadas de cada centro de produo para os mercados com o mnimo custo.
Soluo:
ijX Quantidade do produto a ser enviada do centro de produo i, i = 1 (Recife), 2 (Natal), ao mercado j, j =
1 (Pernambuco), 2 (Paraba), 3 (Rio G. Norte).
mn 232221131211 X4X7X11X5X2X4C
s.a.
0X,0X,0X,0X,0X,0X
900XX
400XX
500XX
1000XXX
800XXX
232221131211
2313
2212
2111
232221
131211
Leitura recomendada
Arenales, MARCOS. & et al. PESQUISA OPERACIONAL. Rio de Janeiro: Elsevier, 2007. Cap. 2, pg. 21 a 26.
Pesquisa Operacional em Administrao Mdulo 1 Pgina 15
APLICAES DE PROGRAMAO LINEAR: PLANEJAMENTO DA PRODUO Problemas de mix de produo, isto , fabricao de diversos produtos, aparecem em vrias situaes reais e envolvem decidir quais produtos e quanto fabricar de cada produto em um perodo. Tendo em vista a capacidade limitada da produo (mquinas, recursos humanos, capital, armazenagem etc.) e os diversos produtos que a empresa pode fabricar e vender; deseja-se determinar quais fabricar de cada produto, de modo a maximizar a margem de contribuio ao lucro da empresa.
Formulao matemtica do problema de transporte n Nmero de produtos diferentes fabricados m Nmero de recursos utilizados na fabricao do produto
jX Quantidade, no negativa, do produto j, j=1,2,...,n, a ser produzida em um perodo do
planejamento (por exemplo, um ms)
iC Capacidade do recurso i, i = 1, 2, ..., m, disponvel no perodo
ija Unidades do recurso i consumidas para a produo de uma unidade do recurso j
jd Produo mnima do produto j, que precisa ser realizada no perodo, devido aos pedidos em
carteira e a uma poltica de estoque mnimo para preservao do produto no mercado.
jv Produo mxima do produto j, que precisa ser realizada no perodo, para atender a
demanda estimada pelo departamento de vendas.
jl Lucro contribudo de cada unidade do produto j para a empresa.
Maximizar n
1j
jjXlL
s.a.
n..., 1, j vXd
m ..., 1, i CXa
jjj
i
n
1j
jij
Exemplo Um fabricante de geladeiras precisa decidir quais modelos deve produzir em uma nova fbrica recentemente instalada. O departamento de marketing e vendas realizou uma pesquisa de mercado que indicou que, no mximo, 1.500 unidades do modelo de luxo e 6.000 unidades do modelo bsico podem ser vendidas no prximo ms. A empresa j contratou um certo nmero de empregados e, com isso, dispe de uma fora de trabalho de 25.000 homens-hora por ms. Cada modelo de luxo requer dez homens-hora e cada modelo bsico requer oito homens-hora para ser montado. Alm disso, uma mesma linha de montagem compartilhada pelos dois modelos e considere que a capacidade de produo desta linha seja de 4.500 geladeiras por ms. O lucro unitrio do modelo de luxo de $100,00, e do modelo bsico de $50,00. Deseja-se determinar quanto produzir de cada modelo de modo a maximizar o lucro da empresa.
Soluo:
jX Quantidade de geladeiras do tipo j produzida durante o ms, j = 1 (luxo) e 2 (bsico).
mx 21 X50X100L
s.a.
000.6X0 e 500.1X0
500.4XX
000.25X8X10
21
21
21
Pesquisa Operacional em Administrao Mdulo 1 Pgina 16
TCNICA DE SOLUO PARA MODELOS DE PROGRAMAO LINEAR COM
DUAS VARIVEIS DE DECISO MTODO GRFICO Exemplo 1 Resolver o problema de programao linear:
Minimizar 21 X3X2C
s.a.
0X e 0X
8X
10XX5
5XX
21
1
21
21
Soluo: a) Construir a regio de solues das restries:
5XX 21 Se 1X = 0, ento 0 + 2X = 5
Se 2X = 0, ento 0 + 1X = 5
10XX5 21 Se 1X = 0, ento 5 0 + 2X = 10 ou 2X = 10
Se 2X = 0, ento 5 1X +0 = 10 ou 1X = 2
8X1 A representao grfica uma reta paralela ao eixo 2X pelo ponto 1X = 8
Grfico:
Tomando-se o ponto (5,5) para o teste da regio de soluo de cada uma das inequaes
temos, substituindo os valores 1X = 5 e 2X =5:
5XX 21 , ento 5 + 5 5 ou 10 5, a desigualdade verdadeira
10XX5 21 , ento 5 5 + 5 10 ou 30 10, a desigualdade verdadeira.
8X1 , substituindo 1X = 8, teremos 5 8, a desigualdade verdadeira.
b) Avaliar o desempenho da funo objetivo. Arbitraremos dois valores para C, por exemplo: C = 12 e C = 18. Para C = 12, teremos:
12X3X2 21 Se 1X = 0, ento 2 0 + 3 2X = 12 ou 2X = 4
Se 2X = 0, ento 2 1X + 3 0 = 12 ou 1X = 6
Para C = 18, teremos:
18X3X2 21 Se 1X = 0, ento 2 0 + 3 2X = 18 ou 2X = 6
Se 2X = 0, ento 2 1X + 3 0 = 18 ou 1X = 9
c) Concluso. medida que diminumos o valor de C, obtemos retas paralelas mais prximas da origem. Portanto, o ponto da regio de solues com o menor valor de C o ponto (5,0). Ponto de mnimo:
1X = 5, 2X = 0. Valor de mnimo = 2 5 + 3 0 = 10
Pesquisa Operacional em Administrao Mdulo 1 Pgina 17
Exemplo 2 Resolver o problema de programao linear:
Maximizar 21 X3X2L
s.a.
0X e 0X
12XX
60X6X4
21
21
21
Soluo: a) Construir a regio de solues das restries:
60X6X4 21 Se 1X = 0, ento 6 2X = 60 ou 2X = 10
Se 2X = 0, ento 4 1X = 60 ou 1X = 15
12XX 21 Se 1X = 0, ento 2X = 12
Se 2X = 0, ento 1X = 12
Grfico:
Tomando-se o ponto (15,12) para o teste da regio de soluo de cada uma das inequaes
temos, substituindo os valores 1X = 15 e 2X =12:
60X6X4 21 , ento 4 15 + 6 12 60 ou 132 60, o que falso.
12XX 21 , ento 15 + 12 12 ou 27 12, a desigualdade verdadeira.
b) Avaliar o desempenho da funo objetivo. Arbitraremos dois valores para L, por exemplo: L = 24 e L = 45. Para L = 24, teremos:
24X3X2 21 Se 1X = 0, ento 2 0 + 3 2X = 24 ou 2X = 8
Se 2X = 0, ento 2 1X + 3 0 = 24 ou 1X = 12
45X3X2 21 Se 1X = 0, ento 2 0 + 3 2X = 45 ou 2X = 15
Se 2X = 0, ento 2 1X + 3 0 = 45 ou 1X = 22,5
c) Concluso.
Conclumos que L atinge o maior valor na regio de solues sobre a reta 60X6X4 21 .
Portanto, todos os pontos do segmento a partir do ponto de equilbrio so solues timas do
modelo. Ponto de mximo: 1X = 15, 2X = 0. Valor de mximo = 2 15 + 3 0 = 30
Pesquisa Operacional em Administrao Mdulo 1 Pgina 18
TCNICA DE SOLUO PARA MODELOS DE PROGRAMAO LINEAR COM
DUAS VARIVEIS DE DECISO MTODO SIMPLEX Exemplo 1 Resolver o problema de programao linear:
Maximizar 21 X5X3L
s.a.
0X e 0X
18X2X3
6X
4X
21
21
2
1
Soluo: 1 Iterao Passo 1: Introduo da varivel de folga
Maximizar 54321 X0X0X0X5X3L
s.a.
0X e 0X
18XX2X3
6XX
4XX
21
521
42
31
Passo 2: Montagem da matriz de clculos
BASE 1X 2X 3X 4X 5X b
3X 1 0 1 0 0 4
4X 0 1 0 1 0 6
5X 3 2 0 0 1 18
L -3 -5 0 0 0 0
Soluo: 018060400503L Passo 3: Transformao da matriz (varivel que deve entrar e a que deve sair da base):
Entrar: 2X , por ter o maior valor negativo na linha (L)
Sair: 4X , Por ter o menor quociente na diviso b/ 2X
Nova matriz: Zerar os valores da coluna 2X , com exceo da linha pivor (segunda)
BASE 1X 2X 3X 4X 5X b
3X 1 0 1 0 0 4
2X 0 1 0 1 0 6
5X 3 0 0 -2 1 6
L -3 0 0 5 0 30
Soluo: 306000406503L 2 Iterao Passo 3: Transformao da matriz (varivel que deve entrar e a que deve sair da base):
Entrar: 1X , por ter o maior valor negativo na linha (L)
Sair: 5X , Por ter o menor quociente na diviso b/ 1X
Nova matriz: Zerar os valores da coluna 1X , com exceo da linha pivor (terceira)
BASE 1X 2X 3X 4X 5X b
3X 0 0 1 32 31 2
2X 0 1 0 1 0 6
1X 1 0 0 32 31 2
L 0 0 0 3 1 36
Soluo: 360000206523L
Pesquisa Operacional em Administrao Mdulo 1 Pgina 19
MTODO SIMPLEX: EXERCCIOS Exerccio 1 Resolver o problema de programao linear:
Maximizar 21 X3X9L
s.a.
0X e 0X
24X3X2
14X1X2
21
21
21
Soluo: 1 Iterao Passo 1: Introduo da varivel de folga
Maximizar 4321 X0X0X3X9L
s.a.
0X e 0X
24XX3X2
14XX1X2
21
421
321
Passo 2: Montagem da matriz de clculos
BASE 1X 2X 3X 4X b
3X 2 1 1 0 14
4X 2 3 0 1 24
L -9 -3 0 0 0
Soluo: 02401400309L Passo 3: Transformao da matriz (varivel que deve entrar e a que deve sair da base):
Entrar: 1X , por ter o maior valor negativo na linha (L)
Sair: 3X , Por ter o menor quociente na diviso b/ 2X
Nova matriz: Zerar os valores da coluna 1X , com exceo da linha pivor (segunda)
BASE 1X 2X 3X 4X b
1X 1 21 21 0 7
4X 0 2 -1 1 10
L 0 23 29 0 63
Soluo: 63100000379L Exemplo 2 Resolver o problema de programao linear, pelo mtodo simplex:
Maximizar 321 X1X5X3L
s.a.
0X e 0X ,0X
6X2
24X2X6
16X1X4X2
321
2
21
321
Soluo: 1 Iterao Passo 1: Introduo da varivel de folga
Maximizar 654321 X0X0X0X1X5X3L
s.a.
0X e 0X ,0X
6XX2
24XX2X6
16XX1X4X2
321
62
521
4321
Pesquisa Operacional em Administrao Mdulo 1 Pgina 20
Passo 2: Montagem da matriz de clculos
BASE 1X 2X 3X 4X 5X 6X B
4X 2 4 1 1 0 0 16
5X 6 2 0 0 1 0 24
6X 0 2 0 0 0 1 6
L -3 -5 -1 0 0 0 0
Soluo: 060240160010503L Passo 3: Transformao da matriz (varivel que deve entrar e a que deve sair da base):
Entrar: 2X , por ter o maior valor negativo na linha (L)
Sair: 6X , Por ter o menor quociente na diviso b/ 2X
Nova matriz: Zerar os valores da coluna 2X , com exceo da linha pivor (segunda)
BASE 1X 2X 3X 4X 5X 6X B
4X 2 0 1 1 0 -2 4
5X 6 0 0 0 1 -1 18
2X 0 1 0 0 0 21 3
L -3 0 -1 0 0 25 15
Soluo: 150018040013503L 2 Iterao Passo 3: Transformao da matriz (varivel que deve entrar e a que deve sair da base):
Entrar: 1X , por ter o maior valor negativo na linha (L)
Sair: 4X , Por ter o menor quociente na diviso b/ 1X
Nova matriz: Zerar os valores da coluna 1X , com exceo da linha pivor (terceira)
BASE 1X 2X 3X 4X 5X 6X B
1X 1 0 21 21 0 -1 2
5X 0 0 -3 -3 1 5 6
2X 0 1 0 0 0 21 3
L 0 0 21 23 0 - 21 21
Soluo: 21006000013523L 3 Iterao Passo 3: Transformao da matriz (varivel que deve entrar e a que deve sair da base):
Entrar: 6X , por ter o maior valor negativo na linha (L)
Sair: 5X , Por ter o menor quociente na diviso b/ 1X
Nova matriz: Zerar os valores da coluna 1X , com exceo da linha pivor (terceira)
BASE 1X 2X 3X 4X 5X 6X B
1X 1 0 -1/10 -1/10 1/5 0 16/5=3,2
6X 0 0 -3/5 -3/5 1/5 1 6/5=1,2
2X 0 1 3/10 3/10 -1/10 0 12/5=2,4
L 0 0 1/5 6/5 1/10 0 108/5=21,
6
Soluo: 6,212,100000014,252,33L