PROGRAMAÇAO LINEAR

1.0 PROGRAMAÇÃO LINEAR

É um técnica de otimização que são utilizadas na resolução de problemas quantitativos que tem seus modelos representados por expressão lineares. Muitos problemas práticos em pesquisa operacional podem ser expressos como problemas de programação linear. Tais casos de programação linear como problemas de network flow e problemas de multicommodity flow são considerados importantes para que se tenha gerado muita pesquisa em algoritmos especializados para suas soluções. Tem algoritmos que funcionam resolvendo problemas de programação linear como subproblemas. Historicamente, a PL foi inspirada nos conceitos centrais de teoria da otimização, tais como: dualidade, decomposição e a importância da convexidade e suas generalizações. Hoje se tornou um recurso bastante difundido pela suas simplicidades e possibilidade de aplicação.

Na Programação Linear existem combinações de variáveis, uma delas pode chamar de Função Objetivo, cujas variáveis podem maximizar ou minimizar. Em qualquer modelo podemos encontrar restrições, essas podem ser representadas por equações ou inequações, que indicam uma limitação na situação real, como: escassez de recursos, limitações de mercado, entre outros.

Assim, podemos resumir a técnica de Programação Linear: Problema Resolução: Conjunções de restrições – Função Objetiva

Já a resolução de um problema PL, podemos citar alguns casos:

A) Problemas com duas variáveis

- Solução Gráfica – Solução Análise Matemática

- Através de um Algorítmo, ou seja, Método Simplex

B) Problemas com um número qualquer de variáveis – Solução via Análise Matemática

- Através de um Algoritmo, ou seja, Método Simplex

Com esta análise poderemos partir para o processo de Análise de Sensibilidade. Ao buscarmos a solução de um problema, iremos nos deparar com várias soluções. Estas soluções entrarão na Região Permissível, ou seja, compondo conjunto de soluções viáveis, porém para nós será cabível a solução que ao mesmo tempo satisfaz as restrições e minimiza/maximiza a função objetivo, assim, auxiliando-nos na nossa tomada de decisões. Dentro de cada técnica para solucionar nossos problemas em PL, sempre procuramos buscar a solução ótima, assim, analisaremos quão sensível é a tal solução.

Áreas de Aplicação:

A) Administração de Produção;

B) Análise de Investimentos;

C) Alocação de Recursos Limitados;

D) Planejamento Regional;

E) Logística: Custo de Transporte, Localização de Rede de distribuição;

F) Alocação de Recursos em Marketing em diversos ramos.

1.1 Modelagem do Problema de Programação Linear

Tem maior impacto econômico. Pois os problemas de Programação Linear são aplicações mais bem-sucedidas comercialmente da pesquisa operacional. As evidências são de que as aplicações ao estruturar o problema sob a forma de um modelo matemático, porém, o intuito é de ajudar no processo de decisão. Programa Linear é uma ferramenta de planejamento que nos ajuda a selecionar que atividades (variáveis de decisões) empreendem, dado que essas alternativas competem entre si pela utilização de recursos escassos/restrições ou então precisam satisfazer alguns requisitos mínimos. O objetivo é minimizar ou maximizar uma função das atividades, geralmente lucros ou perdas. O problema resume-se na maximização ou minimização de uma função linear, a função objetiva, também é sujeita a restrições lineares.

1.2 Exemplos de modelagem do problema de programação linear:

1) “Uma fábrica produz dois produtos A e B. Cada um deles deve ser processado por duas máquinas, M1 e M2. Devido à programação de outros produtos, que também utilizam essas máquinas, a máquina M1 tem 24 horas de tempo disponível para os produtos A e B, enquanto a máquina M2 tem 16 horas de tempo disponível. Para produzir uma unidade do produto A, gastam-se 4 horas em cada máquina M1 e M2. Para produzir uma unidade do produto B, gastam-se 6 horas na máquina M1 e 2 horas na máquina M2. Cada unidade vendida do produto A gera um lucro de R$ 80,00 e cada unidade vendida do produto B gera um lucro de R$ 60,00. Existe uma previsão máxima de demanda para o produto B de 3 unidades, não havendo restrições quanto a demanda do produto A. Deseja-se saber quantas unidade de A e de B devem ser produzidas, de forma a maximizar o lucro e, ao mesmo tempo, obedecer a todas as restrições.”

Resolução:

a) Reconhecer as variáveis de decisão. Aqui as variáveis de decisão serão os produtos A e B, pois depende destes a quantidade a ser produzida para que o lucro seja máximo.

TOTAL

PRODUTO M1 – (horas) M2 – (horas) LUCRO – (R$) DEMANDA A 4 4 80 - B 6 2 60 3

b) Montar a Função Objetivo e as Restrições

Função Objetivo: É maximizar o lucro em função da quantidade de unidades do produto A e B. Logo, assumo a quantidade do produto A, sendo x e a quantidade do produto B, sendo y. Assim, Maximizar: 80x + 60y

Restrições:

• Escassez de Recursos das máquinas M1 e M2 e o consumo de horas na produção de cada produto A e B. Note que, as máquinas 1 e 2, tem de disponibilidade, 24 horas e 16 horas, respectivamente. Assim, M1 ≤ 24 M2 ≤ 16

Precisamos relacionar a disponibilidade das máquinas, com as variáveis de decisão, caso contrário, nossa restrição não terá ligação nenhuma com a tomada de decisão. Sendo assim, uma forma de relacionar, é verificar que cada produto possui um tempo específico para sua produção em cada máquina. Verificando na tabela dos dados, temos:

A máquina M1 com relação aos produtos A e B têm a seguinte relação: M1 = 4x + 6y

A máquina M2 com relação aos produtos