Pesquisa Operacional AULA 2

Prévia do material em texto

PESQUISA OPERACIONAL 
AULA 2 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Prof. Ricardo Zanardini 
 
 
 
 
2 
CONVERSA INICIAL 
Olá! Seja bem-vindo à nossa segunda aula de Pesquisa Operacional! 
Na aula anterior, aprendemos o que é um problema de Programação 
Linear e como é possível formular problemas desse tipo. 
Nessa aula estudaremos como é possível resolver problemas de 
Programação Linear utilizando o método gráfico, o método Simplex e um 
software chamado WinQSB. 
Agora, para que possamos iniciar nossos estudos, vamos relembrar o 
problema da indústria de artigos de couro visto anteriormente. 
Problema de programação linear 
Sabemos que um problema de programação linear consiste em um 
problema de PO com uma função objetivo linear e restrições também lineares. 
Para entendermos melhor o que é e como resolvermos um problema de PL, 
vamos considerar o problema de uma indústria de artigos de couro que produz 
bolsas e carteiras, visto anteriormente. Relembrando os dados do problema, 
para a fabricação de uma bolsa, a indústria utiliza 500 gramas de couro e 1 hora 
do setor de corte e costura e para a fabricação de cada carteira, a indústria utiliza 
200 gramas de couro e 1 hora de corte e costura. Sabemos também que 
atualmente a indústria tem à disposição, por semana, 20 quilos de couro (20.000 
gramas) e 44 horas de corte e costura. O lucro referente à fabricação e venda 
de uma bolsa é de R$ 39,00 e o lucro referente à fabricação e venda de cada 
carteira é de R$ 17,00. 
Como já sabemos, para formular o problema precisamos determinar quais 
são as variáveis, a função objetivo e quais são as restrições inerentes ao 
problema. 
Para o problema em questão, as variáveis são as quantidades de cada 
item a serem produzidas: 
b - é a quantidade de bolsas a serem produzidas; 
 
 
3 
c - é a quantidade de carteiras a serem produzidas. 
O próximo passo é determinar a função objetivo. Como o lucro referente 
a cada bolsa corresponde a R$ 39,00 e o lucro referente a cada carteira 
corresponde a R$ 17,00, para obtermos o lucro total L, basta multiplicarmos as 
quantidades b e c de bolsas e carteiras a serem produzidas pelos respectivos 
lucros unitários e somarmos os resultados: 
L = 39b + 17c 
Como a meta é maximizar o lucro, a função objetivo é representada por: 
max L = 39b + 17c 
Com relação às restrições do problema, o primeiro passo é determinar 
quais são os fatores apresentados que limitam a produção de bolsas e carteiras. 
Para essa indústria, há um limite de matéria-prima que corresponde a 20 quilos 
de couro por semana, o que corresponde a 20.000 gramas de couro. Outro fator 
limitante é a disponibilidade do setor de corte e costura cuja capacidade semanal 
é de 44 horas. 
Sabendo que cada bolsa utiliza 500 gramas de couro, que cada carteira 
requer 200 gramas e que o limite máximo de couro é de 20.000 gramas, a 
primeira restrição do problema é: 
500b + 200c <= 20.000 
É fácil perceber que o produto 500b corresponde ao total de couro 
necessário para a fabricação de uma quantidade igual a b de bolsas e que o 
produto 200c corresponde à quantidade total de couro necessária para a 
fabricação de c carteiras. Para essa restrição utiliza-se o símbolo <= (menor ou 
igual), pois a quantidade total de couro utilizada pode ser inferior ou, no máximo, 
igual a 20.000 gramas, mas não pode ultrapassar essa quantidade. 
De modo análogo, podemos obter a segunda restrição do problema. 
Como essa restrição se refere à disponibilidade semanal do setor de corte e 
costura e cada item produzido utiliza 1 hora do referido setor, a outra restrição 
do problema é a seguinte: 
 
 
4 
1b + 1c <=44 
Nessa restrição temos que o tempo total destinado à utilização do setor 
de corte e costura para a produção de bolsas e carteiras de couro não pode ser 
superior a 44 horas. 
Sendo assim, a formulação para o problema é apresentada a seguir: 
max L = 39b + 17c 
s.a. 500b + 200c <= 20.000 
1b + 1c <= 44 
b >= 0, c >= 0 
Dizemos que as restrições b>=0 e c>=0 são as restrições de não 
negatividade, pois não faz sentido produzir quantidades negativas de bolsas ou 
carteiras. 
Inicialmente estudaremos o método gráfico. Sob o ponto de vista prático, 
não é um método muito eficiente, pois está limitado a duas variáveis. No entanto 
ele tem uma importância conceitual bastante forte. 
Por intermédio do método gráfico é possível visualizar um problema de 
PL bem como o significado geométrico das restrições e da função objetivo. 
Mas o que é o método gráfico e como ele pode ser utilizado? 
TEMA 1 - MÉTODO GRÁFICO 
Com o intuito de visualizar o significado geométrico da função objetivo e 
das restrições de um problema de programação linear com duas variáveis, 
podemos utilizar o método gráfico. Inicialmente iremos considerar um sistema de 
eixos coordenados onde cada variável do problema da indústria de artigos de 
couro está associada a um dos eixos. 
 
 
 
5 
 
 
A primeira restrição, 500b+200c<=20000 é representada facilmente 
construindo-se uma tabela como segue: 
 
Atribuímos, inicialmente, o valor 0 para b e calculamos o valor de c. Em 
seguida basta substituir c por 0 para determinarmos o valor de b. Note que as 
escolhas de b = 0 e c = 0 facilitam a representação da restrição pois geram 
pontos sobre os eixos coordenados. Como a restrição é de menor ou igual, 
consideramos a região que fica abaixo da reta 500b+200c=20000. 
 
 
 
6 
De modo similar, atribuímos valores nulos, separadamente, para b e c e 
substituímos esses valores na equação 1b+1c<=44 para, dessa maneira 
representamos em seguida a segunda restrição do problema. 
 
Novamente, pelo fato de termos uma restrição de menor ou igual, a região 
abaixo da reta 1b+1c=44 é considerada. 
 
Assim, temos a região factível destacada na figura abaixo. A região 
contém as possíveis soluções do problema. Por outro lado, pontos fora da região 
não satisfazem as restrições do problema. 
 
 
 
7 
Observe que as restrições limitam a capacidade de produção. Elas agem 
como cortes feitos em um plano, inicialmente ilimitado, mas que obviamente tem 
as limitações devido às características físicas do problema. 
Graficamente, a função objetivo pode ser representada atribuindo valores 
aleatórios para L e, em seguida, representando as respectivas retas obtidas. Mas 
por que devemos proceder assim? Note que a função objetivo é uma função cujo 
valor do lucro (L) depende das variáveis do problema, nesse caso, b e c. Como 
ainda não sabemos o valor ótimo dessas variáveis, atribuímos valores quaisquer 
para elas de modo a observarmos o comportamento de função objetivo e, 
consequentemente, encontrarmos a solução ótima do problema. 
Para o nosso exemplo, a função objetivo é dada por L=39b+17c. 
Com o intuito de representarmos graficamente a função objetivo, vamos 
atribuir, aleatoriamente, os seguintes valores para L: 
L=0 
L=1000 
L=1500 
Para L=0, a função objetivo pode ser escrita como 39b+17c=0. Para 
representarmos graficamente essa reta, construiremos uma tabela e 
atribuiremos um valor aleatório para b com o objetivo de substituir esse valor na 
expressão 39b+17c=0 para calcularmos c. Em seguida, atribuiremos um valor 
para c e com isso poderemos calcular o valor de b da mesma maneira. A tabela 
a seguir apresenta esses valores. 
 
Nesse caso é fácil perceber que a função objetivo passará pelos pontos 
(0, 0) e (-17, 39). 
 
 
8 
 
De modo análogo, podemos representar graficamente a função objetivo 
para L=1000. Nesse caso, os pontos escolhidos para quepossamos representar 
graficamente a reta são os seguintes. 
 
Logo, temos o seguinte gráfico. 
 
 
 
9 
E, finalmente, fazendo L=1500, a função objetivo pode ser escrita como 
39b+17c=1500 e a tabela contendo os valores de b e c para que possamos fazer 
a representação gráfica é a seguinte. 
 
Nesse caso, temos o seguinte gráfico. 
 
Observe que à medida em que aumentamos o valor de L, as retas 
associadas à função objetivo se aproximam cada vez mais de um dos vértices 
da região factível do problema. 
Isso sempre irá acontecer. A solução ótima de um problema de PL 
encontra-se em um dos vértices da região factível. No caso do problema possuir 
mais do que uma solução ótima, a solução encontra-se em todos os pontos entre 
dois vértices ótimos. Assim, uma forma bastante simples de determinar a solução 
ótima de um problema de PL através do método gráfico é construir uma tabela 
contendo os vértices da região factível e, em seguida, substituir cada um desses 
pontos na função objetivo. 
 
 
10 
 
Pensando assim, para que possamos resolver graficamente um problema 
de PL, não é necessário representar graficamente a função objetivo. Podemos 
construir uma tabela contendo os vértices da região factível. Em seguida, basta 
substituir as coordenadas do vértice na função objetivo e o que fornecer o maior 
valor corresponderá então à solução do problema. 
No nosso exemplo, os vértices são: (0, 0), (0, 44), (37,33; 6,66) e (40, 0). 
O vértice (37,33; 6,66) foi obtido através da resolução do sistema de equações 
 
Sendo assim, a tabela contendo os vértices e os respectivos valores de L 
é dada a seguir. 
 
Como o maior lucro possível foi L=1569,09 para b=37,33 e c=6,66, temos 
que a solução ótima do problema é: 
b=37,33 
 
 
11 
c=6,66 
L=1569,09 
 
Tanto o método gráfico quanto o método simplex fornecem soluções que 
nem sempre são inteiras. Quando utilizamos o WinQSB, por exemplo, é possível 
selecionar o tipo de variável do problema (contínua, inteira, binária ou irrestrita). 
No caso do problema da indústria de artigos de couro, o tipo mais indicado são 
as variáveis inteiras. 
É importante ressaltar que se o problema for de maximização, a solução 
ótima consiste no vértice que gera o maior valor para a função objetivo. Para 
problemas de minimização, o nosso objetivo é determinar o vértice que gera o 
menor valor para a função objetivo. 
Agora que vimos o que é o método gráfico e qual é o significado 
geométrico da função objetivo e das restrições, podemos aprender como é 
possível resolver um problema de programação linear utilizando o método 
Simplex. 
TEMA 2 - MÉTODO SIMPLEX 
Um importante método para a resolução de problemas de PL é o Método 
Simplex, criado por George B. Dantzig. O princípio básico do método consiste 
em, partindo de uma solução inicial, buscar a minimização ou a maximização do 
problema a ser resolvido. 
Para que possamos aprender a resolver um problema de PL utilizando o 
método simplex, vamos utilizar o exemplo da indústria de artigos de couro. 
Relembrando os dados do problema, para a fabricação de uma bolsa, a 
indústria utiliza 500 gramas de couro e 1 hora do setor de corte e costura e para 
a fabricação de cada carteira, a indústria utiliza 200 gramas de couro e 1 hora 
de corte e costura. Sabemos também que atualmente a indústria tem à 
disposição, por semana, 20 quilos de couro (20.000 gramas) e 44 horas de corte 
 
 
12 
e costura. O lucro referente à fabricação e venda de uma bolsa é de R$ 39,00 e 
o lucro referente à fabricação e venda de cada carteira é de R$ 17,00. 
A formulação do problema é: 
max L = 39b + 17c 
s.a. 500b + 200c <= 20.000 
1b + 1c <= 44 
b >= 0, c >= 0 
O primeiro passo é transformarmos as restrições de desigualdade em 
restrições de igualdade. Mas como podemos fazer isso. A resposta é bem 
simples: basta adicionarmos uma variável de folga para cada restrição de <= 
(menor ou igual). A variável de folga indica a quantidade que falta para que a 
igualdade entre os dois membros da inequação seja verificada. Como a folga 
não representa lucro, o coeficiente de cada variável de folga na função objetivo 
é sempre igual a zero. 
Logo, acrescentando as variáveis de folga, temos a seguinte formulação. 
max L = 39b + 17c + 0x3 + 0x4 
s.a. 500b + 200c + x3 <= 20.000 
1b + 1c + x4 <= 44 
b >= 0, c >= 0 
O próximo passo é criarmos uma tabela inicial para que possamos 
escrever os coeficientes da função objetivo e das restrições, bem como os 
termos independentes. Devido às características do método simplex, os 
coeficientes da função objetivo são escritos na tabela com os respectivos sinais 
invertidos. Para facilitar os cálculos que veremos a seguir, é importante 
colocarmos nomes nas linhas da tabela (L0, L1, L2...). 
 
 
 
13 
 
As variáveis b e c são chamadas de variáveis não básicas. Toda variável 
não básica tem valor igual a zero. Nesse caso, b=0, c=0 e, consequentemente, 
L=0 (valor que aparece no canto superior esquerdo). Por outro lado, as variáveis 
básicas x3 e x4 têm seus valores apresentados na primeira coluna das linhas 1 
e 2: x3=20000 e x4=44. Isso significa que todo o recurso disponível ainda não 
foi utilizado. 
Após preenchermos a tabela inicial, precisamos identificar qual variável 
deverá entrar na base e qual deverá sair. A variável que entrará na base é a que 
representa maior lucro. Nesse caso é a variável b cujo coeficiente é igual a -39. 
É importante lembrarmos que o sinal negativo existe apenas pelas 
características do método Simplex. 
Sabendo que b deverá entrar na base, precisamos saber qual das 
variáveis básicas (x3 ou x4) deverá sair da base. A variável que sai da base é 
aquela cujo recurso limita primeiro a produção. Para sabermos qual é o máximo 
que podemos produzir da variável que está entrando na base, basta dividirmos 
o total dos recursos disponíveis pela quantidade utilizada pela variável. No nosso 
exemplo devemos dividir 20000 por 500 e 44 por 1. O menor resultado indica 
qual é a variável que deixará a base. Como o menor resultado ocorreu na divisão 
de 20000 por 500, quem deixará a base é a variável x3. Isso pode ser facilmente 
observado ao olharmos a coluna referente a x3 e identificarmos em qual linha o 
coeficiente é igual a 1. 
O próximo passo é identificar o pivô (intersecção da coluna da variável 
que entra com a linha da variável que sai). 
 
 
14 
 
Devemos sempre transformar o pivô em 1. Como o pivô é igual a 500, 
basta dividirmos toda a linha 1 por esse número (500). 
 
O próximo passo agora é zerarmos os demais coeficientes da coluna da 
variável básica. Essa é uma das características da variável básica: pivô igual a 
1 e demais elementos iguais a zero. 
O primeiro passo é zerarmos o coeficiente da linha 0. Para isso devemos 
multiplicar a linha do pivô (linha 1) pelo coeficiente da linha a ser zerada (linha 
0), mas com o sinal invertido (39). Em seguida, somamos os resultados. 
 
O procedimento para zerarmos o coeficiente da linha 2 é análogo. 
Devemos multiplicar a linha 1 por -1 e, em seguida, somarmos com a linha 2. 
Os passos realizados até aqui devem ser repetidos até que todos os 
coeficientes da linha 0 sejam positivos ou zero, e nunca negativos. 
 
 
 
15 
Como o coeficiente de c na linha zero é negativo (-1,4), devemos realizar 
mais uma iteração do método Simplex. 
A variável que entra na base é c e a variável que sai da base é x4. O pivô 
é igual a 0,6. 
 
Para transformarmos o pivô em 1, devemos dividir a linha 2 por 0,6. 
 
Em seguida, devemos zerar os demais coeficientes da colunada variável 
c. 
 
Note que não há mais coeficientes negativos na linha 0. Isso significa que 
encontramos a solução ótima do problema. 
 
 
 
16 
A solução ótima consiste em 
b=37,33 
c=6,67 
L=1.569,34 
Excelente! Agora sabemos como podemos resolver um problema de PL 
utilizando o método Simplex. 
Lembre-se, em caso de dúvidas, não hesite em retomar alguns pontos da 
aula! 
TEMA 3 - SOFTWARE WINQSB 
Depois de ter visto os métodos gráfico e Simplex, veremos o software 
WinQSB, que é uma importante ferramenta para a resolução de problemas de 
Pesquisa Operacional. 
Em alguns casos, podemos resolver manualmente um problema de 
Programação Linear. 
No entanto, quanto maior for o número de variáveis e maior for o número 
de restrições, maior é o tempo e o esforço necessários para que possamos obter 
a solução de um problema de PL. 
Na prática, a imensa maioria dos problemas de pesquisa operacional é 
resolvida com o auxílio de algum software específico. O uso de softwares na 
pesquisa operacional é muito comum pois, além de agilizar a resolução dos 
problemas, diminui os possíveis erros que podem ser cometidos no processo de 
resolução desses problemas. 
Existem softwares bastante conhecidos no meio científico tais como 
GAMS, LINDO, LINGO, WinQSB... 
Alguns são gratuitos e outros não. A estrutura e funcionamento dos 
softwares destinados à resolução de problemas de pesquisa operacional é muito 
parecida entre eles. Em algumas empresas, devido à complexidade dos 
 
 
17 
problemas ou às características particulares, é comum que haja a necessidade 
de se desenvolver um software específico, mas na maioria das vezes os 
softwares existentes já são suficientes para que os problemas possam ser 
resolvidos. 
Nas nossas aulas utilizaremos o software gratuito WinQSB que pode ser 
obtido clicando no botão a seguir. 
http://winqsb.en.softonic.com/download#downloading 
Atualmente, a versão do WinQSB é a 2.0, que roda apenas em ambientes 
32 bits. Ao clicar no botão a seguir, você verá os passos necessários para a 
instalação do WinQSB. 
http://www.tantragyan.com/2013/11/download-and-install-winqsb-xp-
windows7.html 
É claro que a escolha do software deve ser feita de modo que as 
necessidades sejam atendidas da melhor maneira possível. 
Uma alternativa muito interessante é o software denominado PO que foi 
desenvolvido pelo professor Mauricio Pereira dos Santos. 
O link para download do software e de outros materiais está no botão a 
seguir. Clique e confira! 
http://www.mpsantos.com.br/ 
Vamos aprender então a resolver um problema de PL utilizando o 
WinQSB. É bem simples! 
Resolução de um problema de PL utilizando o WINQSB 
O WinQSB é um poderoso software gratuito desenvolvido por Yih-Long 
Chang. É um pacote de ferramentas com o intuito de servir de suporte para a 
tomada de decisões baseada em problemas de pesquisa operacional. 
 
 
 
18 
É muito simples começar a utilizar o WinQSB. Após o download e a instalação, 
basta clicar em Iniciar, Programas, WinQSB. Você verá um menu com várias 
opções. Para resolver os problemas de programação linear, iremos utilizar a 
opção Linear and Integer Programing. Basta clicar nessa opção. 
 
Fazendo isso, irá aparecer a seguinte janela: 
 
Em seguida, é só clicar em File e escolher a opção New Problem. 
 
 
19 
 
Agora um dos passos mais importantes para a resolução do problema de 
PL utilizando o WinQSB. Escolha um nome para o problema e escreva-o no 
campo denominado “Problem Title:”. O número de variáveis deve ser colocado 
no campo “Number of Variables:” e o número de restrições em “Number os 
Constraints:”. O critério da função objetivo (maximizar ou minimizar) será 
indicado no ítem “Objective Criterion”, selecionando a opção “Maximization” ou 
“Minimization” de acordo com o problema. A forma de entradas dos dados deve 
ser indicada em “Data Entry Format”. O ideal é deixar selecionada a forma 
matricial, indicada por “Spreadsheet Matrix Form”. Agora devemos indicar o tipo 
de variável do problema. A primeira opção é “Nonnegative continuous” que indica 
variáveis contínuas e não negativas. A segunda opção é “Nonnegative integer”. 
Utilizaremos essa opção quando o problema se refere a variáveis inteiras. A 
terceira opção indica variáveis binárias: “Binary (0,1)”. Essa opção deve ser 
marcada em problemas cujas variáveis podem assumir exclusivamente um dos 
seguintes valores: 0 ou 1. e, finalmente, a última opção indica variáveis irrestritas 
“Unsigned/unrestricted”, utilizadas em problemas onde as variáveis podem 
assumir valores positivos, negativos ou zero. 
 
 
20 
 
No caso do problema da indústria de artigos de couro, temos 2 variáveis 
inteiras, pois não faz sentido a produção fracionada de bolsas e carteiras, e 2 
restrições. Como o problema é de maximização, marcamos essa opção. 
Logo, o preenchimento fica assim: 
 
Agora é só clicar em “OK”. Teremos então uma tabela onde poderemos 
colocar os dados do problema: coeficientes da função objetivo e das restrições 
bem como os termos independentes (R.H.S.). 
 
 
21 
 
Preenchendo os respectivos campos, temos a seguinte figura. 
 
Após preenchermos os dados do problema, precisamos obter a solução. 
Para isso clicamos na opção “Solve and Analyze” e em seguida em “Solve the 
Problem”. 
 
Fazendo isso, aparecerá uma mensagem informando que o problema já 
foi resolvido. É só clicar em “OK”. 
 
 
22 
 
A solução do problema é fornecida na seguinte tabela: 
 
Os valores de x1 e x2, no caso do nosso problema, b e c, são, 
respectivamente, 38 e 5 e o valor do lucro é R$ 1.567,00 (Objective Function 
(Max.) =). O WinQSB também informa os custos reduzidos e as folgas das 
variáveis, além do preço sombra. Veremos com mais detalhes os significados de 
cada um desses elementos quando estudarmos a análise de sensibilidade de 
um problema. 
É possível escolher nomes para as variáveis e restrições. Também é 
possível adicionar ou excluir variáveis e restrições, além de alterar o critério da 
função objetivo. Essas opções podem ser encontradas no menu “Edit”. 
Se preferir, o mesmo problema também pode ser resolvido utilizando o 
PO ou outro software. 
FINALIZANDO 
Nessa aula aprendemos a resolver um problema de PL de maneiras 
diferentes: pelo método gráfico, pelo método Simplex e também através do uso 
de um software, em particular, o WinQSB. 
 
 
23 
Para saber mais acesse os links a seguir: 
http://pt.wikipedia.org/wiki/Programação_linear 
http://www.marcogandra.com.br/2012/08/o-que-e-programacao-
linear.html 
É importante também realizar a leitura dos capítulos 2, 3 e 4 da obra 
“Iniciação à pesquisa operacional no ambiente de gestão”, 2. Ed., dos 
professores Marcos Antônio Barbosa e Ricardo A. D. Zanardini, da editora 
Intersaberes. Se possível, resolva os exercícios propostos no final de cada 
capítulo. 
Outra sugestão de leitura são os capítulos 2 e 3 da obra “Pesquisa 
Operacional”, Hamdy A. Taha, da editora Pearson. 
Bons estudos!