Programação Linear

1 INTRODUÇÃO

Programação Linear é uma técnica de Otimização bastante utilizada na resolução de problemas quantitativos que tenham seus modelos representados por expressões lineares, sendo elas equações e/ou inequações. Pela sua simplicidade e a possibilidade de aplicação em uma considerável diversidade de problemas, tornou-se um recurso bastante difundido.

Em um modelo de Programação Linear, existe uma combinação de variáveis, cujo objetivo é ser maximizada ou minimizada. Para essa combinação de variáveis de decisão chamaremos de Função Objetivo. Em todo modelo de Programação Linear, existem restrições, representadas por equações e/ou inequações, que indicam uma limitação na situação real, tal como, escassez de recursos, limitações de mercado, etc. Dado um modelo em PL, identificamos sempre um Parâmetro, que são valores fixos e independentes e também as Variáveis de Decisão, sendo elas que poderão assumir diversos valores, de forma a maximizar ou minimizar a função objetivo.

Podemos assim resumir a técnica de Programação Linear:

Problema RESOLUÇÃO

- Conjunto de restrições - Função Objetivo

Quanto à resolução de um problema de PL, temos os seguintes casos:

a) Para problema com duas variáveis

- Solução Gráfica - Solução Análise matemática

- Através de um Algorítmo (Método Simplex).

b) Para problema com um número qualquer de variáveis - Solução via Análise matemática

- Através de um Algorítmo (Método Simplex)

tal análise, partiremos para o processo de Análise de Sensibilidade

Veremos que ao buscarmos a solução de um problema, iremos nos deparar com diversas soluções, que neste caso estarão dentro do que chamaremos de Região Permissível, compondo assim, o conjunto de Soluções Viáveis, porém para nós só será cabível aquela que ao mesmo tempo satisfaz dos as restrições e maximiza (ou minimiza) a função objetivo, nos auxiliando assim, durante a tomada de decisão. Logo, dentro de cada técnica para solucionar nosso problema em PL, sempre buscaremos determinar a Solução Ótima, bem como, analisaremos quão sensível é tal solução. Para

Sendo assim, iniciaremos mostraremos um problema dentro de uma visão geral, ou seja, partindo do enunciado, montamos as restrições, a função objetivo e em seguida processamos as técnicas de resolução, que aqui serão por método gráfico (apenas com duas variáveis) e o Método Simplex.

Á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

maior impacto econômico

Os problemas de Programação Linear estão entre as aplicações mais bem-sucedidas comercialmente da Pesquisa Operacional; de fato, há considerável evidência de que eles estão entre as aplicações de Ao estruturar problema sob a forma de um modelo matemático, o intuito é de nos ajudar no processo de decisão: que atividades empreender e quanto de cada uma, a fim de satisfazer um dado objetivo. Programação Linear é uma ferramenta de planejamento que nos ajuda a selecionar que atividades (variáveis de decisão) empreender, dado que essas alternativas (diversas alternativas) competem entre si pela utilização de recursos escassos (restrições) ou então precisam satisfazer certos requisitos mínimos. O objetivo será maximizar (minimizar) uma função das atividades, geralmente lucros (perdas). O problema resume-se na maximização (ou minimização) de uma função linear, a função objetiva, sujeita a restrições também lineares. A seguir são apresentados exemplos de modelagem do problema de programação linear.

Exemplo 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,0 e cada unidade vendida do produto B gera um lucro de R$ 60,0. 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.

b) Formular uma tabela.

TOTAL

PRODUTO M1 – (horas) M2 – (horas) LUCRO – (R$) DEMANDA A 4 4 80 - B 6 2 60 3 c) 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

Agora 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, tem a seguinte