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

O problema geral de programação linear é utilizado para otimizar (maximizar ou minimizar) uma função linear de variáveis, chamada de função objetivo, sujeita a uma série de equações (ou inequações) lineares, chamadas restrições.

A formulação do problema a ser resolvido segue três pontos básicos:

Definição do objetivo do problema
Definição das variáveis de decisão envolvidas
Conhecimento das restrições a que está sujeito o problema

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.

Assim, o problema geral de programação linear pode ser definido por:

Maximizar (ou minimizar) a função objetivo:

 $Z=c_{1}\cdot x_{1}+c_{2}\cdot x_{2}+...+c_{n}\cdot x_{n}\,\!$

sujeita às restrições:

 $a_{11}\cdot x_{1}+a_{12}\cdot x_{2}+...+a_{1n}\cdot x_{n}\leq b_{1}\,\!$ 
 $a_{21}\cdot x_{1}+a_{22}\cdot x_{2}+...+a_{2n}\cdot x_{n}\leq b_{2}\,\!$ 
 $a_{31}\cdot x_{1}+a_{32}\cdot x_{2}+...+a_{3n}\cdot x_{n}\leq b_{3}\,\!$ 
a
 $a_{m1}\cdot x_{1}+a_{m2}\cdot x_{2}+...+a_{mn}\cdot x_{n}\leq b_{m}\,\!$

considerando que todas as variáveis de decisão assumem valores positivos:

  $x_{1},x_{2},x_{n}\geq 0\,\!$

Solução Gráfica

Um problema que contenha duas variáveis pode ser resolvido graficamente.

Traça-se um gráfico com os seus eixos sendo as variáveis $x_{1}\,\!$ e $x_{2}\,\!$ .

A partir deste gráfico traçam-se as restrições do problema e delimita-se a região viável.

Após isso, traça-se uma reta com a inclinação da função objetivo, buscando retas paralelas a ela que forneçam a solução para o problema.

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

O conceito de modelos é de importância fundamental ao estudarmos pesquisa operacional. Um modelo é uma representação simplificada da realidade. Para criarmos um modelo de programação linear, precisamos identificar em um problema qual é a função objetivo, as restrições e o tipo de otimização que desejamos (queremos achar o máximo ou o mínimo da função-objetivo?). Veja o exemplo abaixo:

Uma empresa fabrica mesas e cadeiras. O quadro abaixo mostra os recursos consumidos por unidade de cada produto e os seus lucros.Quantas mesas e cadeiras podem ser fabricados para se maximizar o lucro?

Unidades Necessárias
Recurso	Mesa	Cadeira	Quantidade Disponível
Madeira	30	20	310
Metal	5	10	113
Lucro	6	8	-

A nossa função objetivo é o total de lucro da venda de mesas (M) e cadeiras (C). Queremos descobrir qual o valor máximo possível de lucro que podemos obter. Logo, nossa função objetivo é:

Máx $Z=6M+8C$ (Função-Objetivo)

Agora precisamos analisar as restrições. Temos uma quantidade máxima de madeira disponível (310) e cada mesa e cada cadeira gastam uma certa quantidade deste material (30 e 20). Logo, temos uma restrição:

$30M+20C\leq 310$ (Restrição 1)

Da mesma forma, existe uma quantidade limitada de metais, o que nos dá a segunda restrição:

$5M+10C\leq 113$ (Restrição 2)

Além disso, sabemos que não podemos fabricar uma quantidade negativa de cadeiras ou mesas:

$M,C\geq 0$

Pronto! Terminamos de construir o nosso 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 representam pontos que satisfazem a Restrição 2. Todos os pontos dentro ou abaixo àquela reta grossa menos inclinada satisfazem a Restrição 1. Pontos à direita da reta Y e acima 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), (1,4) e (0,4). O lucro em (0,0) é $0, em (3,0) é $3, em (3,3) é $9, em (1,4) é $9 e em (0,4) é $8. 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$ <<< reveja essa restrição, não pode ser >= 9... tem que ser <= 9 ... a solução do problema ficou errada, não tem como usar 4 tanques e 5 bombardeiros, sendo que só no tanque gastaria 8 soldados, e mais 5 no bombardeiro.. temos um limite de 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.