Formulação de problemas de programação linear e
Transcrição
Formulação de problemas de programação linear e
PROGRAMAÇÃO LINEAR Formulação de problemas de programação linear e resolução gráfica A programação linear surge pela primeira vez, nos novos programas de Matemática A no 11º ano de escolaridade. Contudo também no 12 º ano, na Matemática B, se podem encontrar questões ligadas a este assunto, embora com outra formulação. A programação linear (PL) vai permitir aos alunos aplicar conceitos leccionados no 10º ano e ampliados no 11º. Os alunos vão ter oportunidade de resolver problemas, essencialmente da área da Economia, com ferramentas matemáticas simples. O que é a PL A PL é uma técnica da Matemática Aplicada usada no ramo de Investigação Operacional (IO). A origem da IO como ciência é atribuído à coordenação das operações militares durante a 2ª Guerra Mundial. A palavra “programação” refere-se a uma programação de tarefas ou planificação, não a uma programação no sentido da informática. A palavra “Linear”, advém do facto de as expressões (condições) que se utilizam serem lineares. Objectivo da PL. O objectivo desta técnica é optimizar problemas de decisão, através da utilização de modelos, que representem uma realidade. O óptimo na globalidade é um mínimo ou máximo a ser alcançado, nas condições existentes. A aplicabilidade da PL é enorme, pode aplicar-se a situações militares, indústria, agricultura, economia, etc. Contudo, é na área económica que mais se tem desenvolvido. Pretende-se que os alunos se familiarizem-se com decisões concretas de decisão em termos de planeamento, que podem ter a ver com minimizar consumos, custos ou maximizar lucros. Um modelo na PL é constituído por: • Variáveis de decisão (que pretendemos determinar) • Objectivo (o que se pretende optimizar) • Restrições (que têm de ser satisfeitas) Os procedimentos para determinar a solução (de modo a que o objectivo se cumpra) podem ser variados. O mais antigo é o método Simplex. O método Simplex consiste de um algoritmo que permite resolver problemas de Programação Linear. Netprof Contudo o método que iremos utilizar baseia-se na representação gráfica. Foi George Dantzig que, entre 1947 e 1949, desenvolveu os conceitos principais da PL. Como curiosidade refira-se que o primeiro problema resolvido por Dantzig – para desgosto de sua esposa – foi um problema de dieta de custo mínimo. Este problema necessitava da resolução de um sistema de 9 equações (requisitos de nutrição) e 77 variáveis de decisão. Em 1947, George Dantzig e outros cientistas do Departamento da Força Aérea Americana, apresentaram um método denominado Simplex para a resolução dos problemas de Programação Linear (PL). As primeiras e grandes aplicações foram no domínio militar. .-.-.-.-.-.-.-.-.-.-.-.-. Exemplo Uma empresa fabrica dois produtos A e B. Cada um deste produtos requer uma certa quantidade de tempo na linha de montagem e ainda mais algum para a sua finalização. Cada produto do tipo A necessita de 5 horas na linha de montagem e de 2 horas para a finalização. Cada produto de tipo B necessita de 3 horas na linha de montagem e de 4 horas para a finalização. Numa semana, a empresa dispõe de 108 horas para a linha de montagem e 60 horas para a finalização. Toda a produção é vendida. O lucro de cada produto é de 120 € para o produto A e de 210 € para o B. Quantas unidades, por semana, dos produtos A e B se devem produzir, de modo a que o lucro seja máximo? Podemos elaborar uma tabela para melhor esquematizar os dados: Montagem A B Disponibilidade Finalização 5 3 108 2 4 60 Lucro 120 210 Seja x o número de unidades que a empresa produz, por semana, do produto A e y o número de unidades que a empresa produz, por semana, do produto B. O tempo necessário na linha de montagem para os dois produtos é 5x+3y horas, no total. Como somente existem 108 horas de disponibilidade, temos a restrição: 5x+3y ≤ 108 De forma análoga temos a seguinte restrição: 2x+4y ≤ 60 Netprof Consideremos os lucros: Cada unidade do produto A origina um lucro de 120 euros assim, com x unidades produzidas do produto A, obtêm-se 120x euros de lucro. Cada unidade do produto B origina um lucro de 210 euros assim, com y unidades de B, obtêm-se 210y euros de lucro. O lucro semanal é dado por: L= 120x+210y. Pretendemos maximizar o lucro. Claro que temos que acrescentar duas condições x ≥ 0 e y ≥ 0, pois a produção é não negativa. Resumindo: • Variáveis de decisão (que pretendemos determinar): x e y … número de unidades … • Objectivo (o que se pretende optimizar) maximizar o lucro: L= 120x+210y • Restrições (que têm de ser satisfeitas) 5x+3y ≤ 108 2x+4y ≤ 60 x≥0 y≥0 Habitualmente escreve-se na seguinte forma: max. L= 120x+210y sujeito a 5x+3y ≤ 108 2x+4y ≤ 60 x≥0 y≥0 Resolvamos o problema graficamente (Método Gráfico) Como x ≥ 0 e y ≥ 0, iremos precisar somente do primeiro quadrante dos eixos de coordenadas. As outras duas restrições resolvem-se em ordem a y e considera-se o domínio plano respectivo. y ≤- (5/3)x+ 36 e y ≤-0,5x+15 Na figura seguinte estão representados os pontos (área sombreada) que respeitam as restrições do problema. Podemos considerar que a solução que procuramos se encontra no polígono [OABC] . Netprof Os pontos que estão nesta região dizem-se pontos admissíveis. E os vértices O, A, B e C dizem-se vértices da região admissível. Resta saber quais destes pontos maximizam o lucro. Ora, L= 120x+210y ⇔ y = -(4/7)x + L/210, representa uma família de rectas todas com o mesmo declive (-4/7) e cuja ordenada na origem é L/210. Assim sendo a um maior valor de L/210 corresponde a um maior valor de L e assim sendo a resolução do nosso problema consiste em encontrar a recta com declive -4/7 de maior ordenada na origem e que tenha algum contacto com o polígono. Netprof Das várias rectas de declive -4/7 a que tem maior ordenada na origem e tem pontos de contacto com o domínio, é a que passa no vértice B. Este ponto é a solução do sistema. Para encontrar o valor exacto da solução basta resolver o sistema que é composto pelas rectas que intersectam o ponto B. 5 x + 3 y = 108 x = 18 ⇔ 2 x + 4 y = 60 y = 6 Assim para que a empresa, que produz o produtos A e B, tenha o maior lucro possível, deve produzir semanalmente 18 unidades do produto A e 6 unidades do produto B. Podemos saber qual é esse lucro: L= 120x18+210x6= 3420 euros semanais. Nota: Considere o seguinte teorema: Dado um problema de programação linear, se S for a região admissível e for limitada então existe um máximo e mínimo em S e cada um destes ocorre pelo menos num dos vértices da região. Se S não for limitada, então pode não existir nem máximo nem mínimo. Mas se existir ele encontra-se num vértice de S. Este teorema permite-nos conciliar estes resultados com o método gráfico. Netprof Assim no exemplo anterior, como a região admissível é limitada então a solução que procuramos encontra-se num dos vértices da área. Temos 4 vértices para a solução óptima. Façamos uma tabela para procurar o valor máximo. O A B C x y 0 23,5 18 0 0 0 6 15 L= 120x+210y 0 2820 3420 3150 Observando o quadro, rapidamente se obtém o valor que pretendíamos determinar. Observações: Ao resolver um problema de PL pode ocorrer uma das seguintes situações: 1. O problema tem uma única solução óptima. 2. O problema tem várias soluções óptimas (uma infinidade). Netprof 3. O problema não tem um valor óptimo finito. A região de admissibilidade não é limitada e o valor da função objectivo cresce indefinidamente no sentido favorável (positivo ou negativo). 4. O problema é impossível, não tem nenhuma solução. Acontece quando não existem soluções admissíveis, isto é, o conjunto de soluções admissíveis é vazio. Netprof
Documentos relacionados
Grupo I – Sistema Operativo Windows Grupo II – Microsoft Word
Grupo II – Microsoft Word Execute o Microsoft Word e efectue as seguintes tarefas, gravando para a DISQUETE o seu documento com o nome EXAME sempre que achar necessário.
Leia mais