Ficha 02 - Programacao Linear

Prévia do material em texto

Investigação Operacional Programação Linear (PL)
Docente: António Onofre 1/6
1. PROGRAMAÇÃO LINEAR (PL)
1.1. INTRODUÇÃODesigna - se por programação linear (PL) um conjunto de técnicas que permitem resolveros problemas de optimização, num sistema de recursos limitados, sendo lineares, quer afunção objectivo, quer as restrições.A importância especial da PL resulta não só das potencialidades dos seus algoritmos deresolução e da sua grande aplicação prática, mas também da sua génese de estardirectamente relacionada com os conceitos fundamentais da Investigação Operacional.A programação linear lida-se com problemas que dizem respeito a atribuição e adistribuição de recursos entre as diversas tarefas ou actividades que devem ser realizadas.Normalmente, os recursos disponíveis não são suficientes para que todas as actividadessejam executadas no nível desejado. Assim, o que se procura, é encontrar a melhordistribuirão possível dos recursos, de forma a atingir um valor óptimo objectivo (máximopara lucros) e (mínimo para custos).Assim, um problema de programação linear e caracterizado por três elementos básicos:1. Variáveis de decisão, que são o centro das atenções na resolução do problema;2. Existência de um objectivo, expresso em ternos das variáveis de decisão;3. Existência de restrições à aplicação dos recursos, tanto em relação as quantidadesdisponíveis como na forma de emprego.Os estudos de programação linear permitem responder questões como:1. Estando presentes certas condições de produção, qual a quantidade de umdeterminado produto, entre vários, que se deve produzir para obter o maiorlucro possível ?2. Sendo impostas algumas especificações, qual e a composição da mistura quecorresponde ao custo mínimo?3. Estando impostas as condições de trabalho, como repartir o conjunto demão-de-obra entre as diferentes tarefas e especialidades, com o objectivo deminimizar as despesas ou maximizar a eficiência?
Investigação Operacional Programação Linear (PL)
Docente: António Onofre 2/6
1.2. Modelos de Investigação OperacionalImagine que você tenha um compromisso de trabalho de cinco semanas entre Tete (TT) eMaputo (MP). Você pega um avião em Tete na segunda-feira e volta na quarta-feira. Umapassagem aérea normal de ida e volta custa 18.000,00 mt, mas há um desconto de 20% seas datas do bilhete abrangerem um final de semana. Uma passagem só de ida emqualquer direcção custa 75% preço normal. Como seria mais conveniente você compraras passagens para o período de cinco semanas?Podemos considerar a situação como um problema de tomada de decisão cuja soluçãorequer a resposta a três perguntas:1. Quais são as alternativas para a decisão?2. Sob quais restrições a decisão é tomada?3. Qual seria um critério objectivo para avaliar as alternativas?Três alternativas são consideradas:1. Comprar cinco passagens normais TT-MP-TT partindo as segundas-feiras eretornando as quartas-feiras da mesma semana.2. Comprar uma passagem TT-MP, quatro MP-TT-MP que abranjam finais de semanae uma MP-TT.3. Comprar uma passagem TT-MP-TT para cobrir a segunda-feira da primeirasemana e quarta-feira da última semana, e quatro MP-TT-MP para cobrir asviagens restantes. Todos esses bilhetes nessa alternativa abrangeriam pelo menosum fim de semana.A restrição a essas opções é que você possa ser capaz de sair de TT nas segunda-feira evoltar na quarta-feira da mesma semana.Um critério objectivo óbvio para avaliar as alternativas propostas é o preço dos bilhetes.A alternativa de menor custo é a melhor.Especificamente, temos:Custo da alternativa 1 = 5x18000= 90.000,00Custo da alternativa 2 = 0.75x18000+4x(0.8*18000)+0.75x18000= 84.600,00Custo da alternativa 3 = 5x(0.8x18000)= 72.000,00
Portanto, você devera escolher a alternativa 3.Embora o exemplo precedente ilustre os três componentes de um modelo de problemade Programação Linear – alternativas, critérios objectivo e restrições – as situações sãodiferentes no que se refere aos detalhes do modo como cada componente é desenvolvidoe construído. Para ilustrar esse ponto, considere a montagem de um rectangulo de área
Investigação Operacional Programação Linear (PL)
Docente: António Onofre 3/6
máxima com um pedaço de fio de comprimento L polegadas. Qual deveria ser a largura ealtura do rectangulo?Em comparação com o exemplo das passagens aéreas, o número de alternativas noexemplo presente não é finito; ou seja, a largura e altura do retângulo podem assumir umnúmero infinito de valores. Para formalizar essa observação, as alternativas do problemasão identificadas definindo a largura e a altura por variáveis (algébricas) continuas.Seja:w= largura do rectangulo em polegadash= altura do rectangulo em polegadas.
Com base nessas definições, as restrições da situação podem ser expressas verbalmentecomo:
1. Largura do rectangulo + altura do rectangulo = metade do comprimento do fio2. Largura e altura não podem ser negativas.Essas restrições são expressas algebricamente como:1. 2 + ℎ =2. ≥ 0 , ℎ≥ 0
Agora, o único componente restante é o objectivo do problema, ou seja, a maximização daárea do rectangulo. Seja z a área do rectangulo, então o modelo completo se torna:= ℎ2 + ℎ =, ℎ≥ 0
A solução optima desse modelo é = ℎ= , o que significa a construção de uma formaquadrada.Com base nos dois exemplos precedentes, o modelo geral de IO pode ser organizado noseguinte formato geral:
A solução do modelo é viável se satisfazer todas as restrições.É óptima se, além de ser viável, resultar no melhor valor (máximo ou mínimo) dafunção objectivo. No exemplo das passagens aéreas, o problema apresenta três
MinimizarouMaximizar Função Objectivo
Sujeito a restrições
Investigação Operacional Programação Linear (PL)
Docente: António Onofre 4/6
alternativas viáveis, sendo que a terceira dá solução óptima. No problema do rectangulo,uma alternativa viável deve satisfazer a condição = ℎ= com w e h assumindovalores não negativos. Isso leva a um numero infinito de soluções e, deferentemente doproblema das passagens aéreas, a solução óptima é determinada por uma ferramentamatemática adequada.
1.3. Modelagem com Programação Linear
Exemplo:Uma companhia de montagem de lâmpadas, usa dois modelos para a montagem: omodelo actual automático e o modelo antigo com acessória. Cada pessoa no modelo actualrequer 1 hora de trabalho se vier do departamento de corte, e 3 horas se vier dodepartamento de verificação. No modelo antigo, cada pessoa necessita de 2 horas detrabalho, se vier do departamento de corte e 4 horas de trabalho se, for do departamentode verificação. O numero máximo de horas de trabalho por dia para o departamento decorte e de verificação e 32 e 84, respectivamente. Se a companhia recebe um lucro de 50u.m. por cada lâmpada vinda do modelo actual e 80 u.m. do modelo antigo, quantaslâmpadas devem ser produzidas por dia em cada modelo de modo que a companhiamaximize o lucro diário?.
ResoluçãoEste e um exemplo típico de um problema de programação linear. Para tornar claro, asrelações entre o objectivo e as restrições, apresenta-se a tabela 1.
Tabela 1. Resumo dos dados do problema.Departamento Horas de trabalho por pessoamodelo actual modeloantigo Número máximode horas de trabalhoDe corte 1 2 32De verificação 3 4 84Lucros porlâmpada 50 80O método usado para a formulação dos problemas de programação linear temuma determinada lógica, ainda que esta não seja rigorosamente seguida:
1. Analise qualitativa do problema, que depende da experiencia adquirida anteriormente,isto e, a sensibilidade de analisar e relacionar a informação;
2. Formulação do problema, i.e, a definição das variáveis de decisão, da funçã oobjectivo e das restrições;
3. Elaboração do modelo matemático que consiste na indicação das relações entreas variáveis de decisão, a função objectivo e as restrições.
Investigação Operacional Programação Linear (PL)
Docente: António Onofre 5/6
Assim, teremos:
Variáveis de decisão:
1x - Número de lâmpadas produzidas no modelo actual por dia;
2x - Número de lâmpadas produzidas no modelo antigo por dia.
Função objectivo:Oobjectivo do administrador da companhia e decidir quantas lâmpadas são necessáriaspor dia para cada modelo, de modo que ele tenha o lucro máximo diário.
21 8050 xxL  é a função objectivo(a)
RestriçõesRestrições são inequações ou equações que representam as relações entre asquantidades produzidas, as composições das horas e a disponibilidade máxima do recurso(hora).Restrição para o departamento de corte: 3221 21  xxRestrição para o departamento de verificação: 8442 21  xxComo não podemos produzir um número negativo de lâmpadas, então adiciona-se arestrição de não negatividade: 0;0 21  xx ou usualmente: 0, 21 xxAssim, escreve-se o modelo matemático do problema de programação linear.
restriçõesdasConjunto
xx
xx
xx
àsujeito
objectivoFunçãoxxZMaximizar










0,
8443
3221
8050
21
21
21
21
Qualquer solução que satisfaz todas as restrições do modelo e uma solução possível
(admissivel).No exemplo anterior assumimos que tanto a função objectivo como as restrições sãotodas lineares. Intrinsecamente assumimos:Proposição 1. Proporcionalidade - nos modelos de programação linear, a contribuiçãodas variáveis de decisão na função objectivo e nas restrições e directamente proporcionalaos valores que as variáveis assumem.Proposição 2. Aditividade - a contribuição total de todas as variáveis na funçãoobjectivo e em cada restrição e igual a soma das contribuições individuais de cadavariável.
Investigação Operacional Programação Linear (PL)
Docente: António Onofre 6/6
BibliografiaHandy, A. Taha. (2008)Pesquisa Operacional: uma visão geral, Practice Hill International.8 Edição, São Paulo.Mulenga, Alberto (2006), Investigação Operacional uma abordagem introdutória,Maputo.