Pesquisa operacional/Introdução à Programação Linear

O que é Programação Linear?

Suponha que uma empresa produza quatro modelos diferentes de brinquedos. Cada um deles gera uma quantidade de lucro diferente ao ser vendida. O brinquedo 1 gera 10$ de lucro, o 2 gera 8$, o 3 gera 9$ e o 4 gera 7$. A função que determina o lucro da empresa é:

$Z=10x_{1}+8x_{2}+9x_{3}+7x_{4}$

Assumindo que as variáveis são a quantidade de cada brinquedo que é vendida.

Esta é uma função linear, pois cada um dos termos da equação que a forma é uma constante ou um produto entre uma constante e um valor variável. Suponha agora que nós estamos interessados em descobrir qual é o maior lucro possível para esta empresa assumindo que o número máximo de vendas do brinquedo 1 é 100, do brinquedo 2 é 60, do brinquedo 3 é 40 e do brinquedo 4 é 70. Podemos então expressar este problema da seguinte forma:

Máx $Z=10x_{1}+8x_{2}+9x_{3}+7x_{4}$ (Função Objetivo)

$1x_{1}+0x_{2}+0x_{3}+0x_{4}\leq 100$ (Restrição 1)

$0x_{1}+1x_{2}+0x_{3}+0x_{4}\leq 60$ (Restrição 2)

$0x_{1}+0x_{2}+1x_{3}+0x_{4}\leq 40$ (Restrição 3)

$0x_{1}+0x_{2}+0x_{3}+1x_{4}\leq 70$ (Restrição 4)

$x_{1},x_{2},x_{3},x_{4}\geq 0$ (As variáveis de decisão são não-negativas)

O que temos acima é um modelo de Programação Linear. Ele é formado sempre por uma função linear (que é a função objetivo) e por um conjunto de ineqüações lineares (restrições do problema). No exemplo acima, desejamos obter o maior lucro possível (maior valor de Z). O objetivo da programação linear é justamente fornecer ferramentas para resolver o desafio de encontrar o maior ou o menor valor possível em uma função linear cujas variáveis possuem restrições.

A História da Programação Linear

O desenvolvimento de técnicas algébricas para se lidar com inequações lineares é algo bastante antigo. Durante o século XVIII, o matemático e físico Jean-Baptiste Joseph Fourier desenvolveu vários métodos inovadores para se resolver sistemas de ineqüações. Um dos principais algoritmos desenvolvido por Fourier foi o Método de Eliminação de Fourier–Motzkin.

Durante a Segunda Guerra Mundial, novas tecnologias bélicas levaram à criação de grupos acadêmicos com o objetivo de resolver problemas como o uso eficiente de radares, canhões antiaéreos, escoltas navais, etc. O objetivo era sempre reduzir custos militares e buscar maximizar as baixas inimigas. Para resolver estes problemas, a Programação Linear mostrou-se extremamente útil. Os grupos acadêmicos que a utilizavam eram sempre mantidos secretos até o ano de 1947, após o término da guerra. Foi quando a Programação Linear passou a ser muito usada em empresas com o objetivo de reduzir despesas e maximizar lucros.

Também no ano de 1947, o matemático George Dantzig desenvolveu o Algoritmo Simplex, a maneira mais eficiente conhecida de se resolver modelos de Programação Linear. No mesmo ano, John von Neumann desenvolveu a teoria da dualidade e Leonid Kantorovich foi a primeira pessoa a aplicar a Programação Linear à Economia.

Em 1979, Leonid Khachiyan desenvolveu um novo algoritmo para resolver modelos de programação linear: o Algoritmo Elipsóide. O seu algoritmo foi o primeiro criado que era capaz de resolver problemas em tempo polinomial. Apesar disso, era mais lento que o já conhecido Algoritmo Simplex, tanto na teoria como na prática.

Em 1984, surge mais um método de se resolver problemas de pesquisa operacional: o Algoritmo do Ponto Interior, criado por Narendra Karmarkar. Assim como o Algoritmo Elipsóide, ele era polinomial. A diferença é que ele era bem mais rápido e conseguia competir com o Algoritmo Simplex.

A Criação de Modelos

2.1 MODELO MATEMÁTICO DE PROGRAMAÇÃO LINEAR Usa-se programação matemática para a determinação da solução ótima de problemas que exigem que se decida sobre a utilização eficaz de uma quantidade limitada de recursos, para a obtenção de um determinado objetivo. Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto 3 A programação linear é uma técnica de programação matemática e, consiste na otimização (maximização ou minimização) de uma função linear, denominada de Função Objetivo, respeitando-se um sistema linear de igualdades ou desigualdades que recebem o nome de Restrições do modelo.

2.1 MODELO MATEMÁTICO DE PROGRAMAÇÃO LINEAR Usa-se programação matemática para a determinação da solução ótima de problemas que exigem que se decida sobre a utilização eficaz de uma quantidade limitada de recursos, para a obtenção de um determinado objetivo. Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto 3 A programação linear é uma técnica de programação matemática e, consiste na otimização (maximização ou minimização) de uma função linear, denominada de Função Objetivo, respeitando-se um sistema linear de igualdades ou desigualdades que recebem o nome de Restrições do modelo.

2.1 MODELO MATEMÁTICO DE PROGRAMAÇÃO LINEAR Usa-se programação matemática para a determinação da solução ótima de problemas que exigem que se decida sobre a utilização eficaz de uma quantidade limitada de recursos, para a obtenção de um determinado objetivo. Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto 3 A programação linear é uma técnica de programação matemática e, consiste na otimização (maximização ou minimização) de uma função linear, denominada de Função Objetivo, respeitando-se um sistema linear de igualdades ou desigualdades que recebem o nome de Restrições do modelo.

2.1 MODELO MATEMÁTICO DE PROGRAMAÇÃO LINEAR Usa-se programação matemática para a determinação da solução ótima de problemas que exigem que se decida sobre a utilização eficaz de uma quantidade limitada de recursos, para a obtenção de um determinado objetivo. Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto 3 A programação linear é uma técnica de programação matemática e, consiste na otimização (maximização ou minimização) de uma função linear, denominada de Função Objetivo, respeitando-se um sistema linear de igualdades ou desigualdades que recebem o nome de Restrições do modelo.

2.1 MODELO MATEMÁTICO DE PROGRAMAÇÃO LINEAR Usa-se programação matemática para a determinação da solução ótima de problemas que exigem que se decida sobre a utilização eficaz de uma quantidade limitada de recursos, para a obtenção de um determinado objetivo. Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto 3 A programação linear é uma técnica de programação matemática e, consiste na otimização (maximização ou minimização) de uma função linear, denominada de Função Objetivo, respeitando-se um sistema linear de igualdades ou desigualdades que recebem o nome de Restrições do modelo.

Solução Gráfica

Muito bem! Já sabemos como criar os modelos de Programação Linear. Mas... Como podemos resolvê-los? Como usar todos aqueles algoritmos comentados na seção sobre a história da Programação Linear? Bem, vamos com calma. Vamos ver primeiro uma das formas mais simples de se resolver este problema (embora não seja computacionalmente eficiente). Vamos fazer um gráfico analisando o Domínio da função-objetivo mostrada no exempo acima:

As linhas mais finas representam o eixo X e Y, os quais representam respectivamente o número de mesas (M) e cadeiras (C). Todos os pontos dentro ou abaixo àquela reta grossa mais inclinada verticalmente representam pontos que satisfazem a Restrição 2. Todos os pontos deitro ou abaixo àquela reta grossa inclinada mais horizontalmente satisfazem a Restrição 1. Pontos à direita da reta Y e àcima do eixo X satisfazem a exigência de que não podemos fabricar um número negativo de objetos. Quanto mais restrições um ponto no gráfico acima satisfaz, mais escuro ele aparece. A única região onde todas as restrições são satisfeitas é aquele triângulo escuro localizado próximo ao centro do gráfico. Os vértices do triângulo são os pontos (0,0), (0,10) e (5,0).

No ponto (0,0), o nosso lucro é nulo, pois não fabricamos nenhum produto. No ponto (0,10), nosso lucro é 80$. No ponto (5,0), nosso lucro é 30$. No exemplo dado acima, a forma de obter o maior lucro possível é abandonar completamente a fabricação de mesas e se dedicar apenas às cadeiras. E devemos produzir exatamente 10 cadeiras para termos o maior lucro possível.

Perceba que no exemplo acima, o Domínio da função-objetivo era uma região triangular. Como estamos sempre lidando com eqüações e ineqüações lineares, o domínio sempre será um polígono. Nunca conseguiremos obter curvas no gráfico do Domínio da função-objetivo. Outra coisa interessante é que o ponto ótimo que estávamos buscando coincidiu com um dos vértices do polígono. No caso de modelos de programação linear, isso sempre será verdade.

Sabendo disso, você já cohece a forma mais rudimentar de encontrarmos a solução de um modelo de programação Linear. Basta fazermos o gráfico do Domínio da função-objetivo e checarmos os valores da função em todos os seus vértices. Entretanto, essa não é a melhor forma de resolver este tipo de problema. No exemplo acima, haviam apenas duas variáveis (M e C). Mas e se houvessem mais? Como esboçar o gráfico do Domínio? E se o nosso Domínio fôsse representado por um polígono com 300 vértices? Seria trabalhoso demais calcular o valor da função em 300 pontos diferentes!

Bem, veremos métodos melhores de se resolver este tipo de problemas nos próximos capítulos.

Exercícios

1. Um vendedor ambulante sabe preparar pastéis e cachorros-quentes. Um cachorro-quente custa o dobro do preço de um pastel. Ele nunca consegue vender mais do que três pastéis e mais do que quatro cachorros-quentes em um mesmo dia. Um pastel vem com uma pitada de mostarda e um cachorro-quente com duas pitadas. Ele só tem disponível nove pitadas de mostarda para gastar em um único dia. Quantos pastéis e cachorros-quentes ele deve produzir em um único dia para ter o máximo possível de lucro? Resolva construindo um modelo de programação linear.

---

2. Estamos durante a Segunda Guerra Mundial. Temos à nossa disposição tanques e bombardeiros para atacar nossos inimigos. Sabemos que um tanque causa em média 20 baixas inimigas e um bombardeiro causa 50 baixas. Temos apenas 4 tanques à nossa disposição. Um bombardeiro requer 1 soldado para pilotá-lo e um tanque requer 2 (e não cabem soldados adicionais no veículo). Temos a obrigação de enviar no mínimo 9 soldados para o ataque para colaborar com as tropas aliadas que também atacarão. Com quantos tanques e bombardeiros devemos atacar para causar o maior número de baixas?

---

3. No exemplo acima, o que mudaria se acrescentássemos a informação de que temos 5 bombardeiros à nossa disposição?

Respostas dos Exercícios

1. A função-objetivo é:

Máx $Z=P+2C$ (P=Pastel, C=Cachorro-Quente, Z=lucro)

As restrições são:

$P\leq 3$

$C\leq 4$

$P+2C\leq 9$

$P,C\geq 0$

O gráfico do Domínio é:

O polígono mais escuro que representa os pontos que atendem à todas as restrições possui como vértices os pontos (0,0), (3,0), (3,3) e (1,4). O lucro em (0,0) é 0$. Em (3,0) é 3$. Em (3,3) é 9$. Em (1,4) é 9$. Neste exemplo, não existe apenas um único ponto que representa o máximo da função - existem infinitos pontos. Todos aqueles que pertencem ao Domínio e estão na reta que liga (3,3) e (1,4) são o máximo da função e representam a quantidade ideal de produção de pastéis e cachorros-quentes para o vendedor ambulante. Como o vendedor ambulante não pode fazer um número fracionário de pastéis e cachorros, quentes, a resposta é: 3 pastéis e 3 cachorros-quentes ou então 1 pastel e 4 cachorros-quente.

---

2. Temos que resolver o modelo:

Máx $Z=50B+20T$ sujeito às seguintes restrições:

$T\leq 4$

$B+2T\geq 9$

$T,B\geq 0$

Perceba que não é possível resolver este modelo. Não existe nenhuma informação que limite superiormente o número de bombardeiros que temos disponíveis. Logo, podemos simplesmente dizer que o melhor é atacar com infinitos bombardeiros. Isso é um absurdo. É uma solução inconcebível. Modelos com solução infinita costumam ocorrer quando algum tipo de restrição é omitida do modelo.

---

3. Isso acrescenta uma nova restrição ao modelo:

$B\leq 5$

Agora sim podemos resolver o modelo. Tente desenhar o gráfico do Domínio desta função-objetivo. Ele gera um triângulo com três vértices. A resposta é que devemos enviar 4 tanques e 5 bombardeiros para que causemos em média 330 baixas no inimigo.