01LabSimplex-Pesquisa Operacional o201701

Prévia do material em texto

Página 1 de 8 
 
 
OFICINA DATA ASSUNTO PROFESSOR 
01 01/05/2017 ALGORÍTMO SIMPLEX LUIZ ANTONIO PALMEIRA MONTEIRO 
FERRAMENTAS 
PLANILHA EXCELL + SOLVER 
 
 
 
1.1 Planilha Eletrônica 
É um aplicativo que apresenta uma Matriz onde: 
 Linhas - são numeradas (1, 2, 3...) 
 Colunas - são identificadas por letras do alfabeto (A, B, C, ...). 
 Célula – é formada pela intercessão de uma linha com uma coluna (exemplo: B3) 
 
 
 
 
 
 
 
O Microsoft Excel é uma planilha eletrônica 
 
1.2 Suplemento de Planilha Eletrônica 
 Suplemento é um recurso do Microsoft Excel que oferece comandos e recursos adicionais à planilha. 
 Dois dos suplementos mais comuns são as Ferramentas de Análise e o Solver. 
 Para usar esses suplementos, é necessário instalá-los e ativá-los. 
 
1.3 Instalar e ativar as Ferramentas de Análise e o Solver 
 Clique na guia Arquivo. 
 Clique em Opções 
 Deverá aparecer caixa de diálogo <Opções do Excel> (ver figura abaixo) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
CÓDIGO DISCIPLINA PERÍODO 
INF303 PESQUISA OPERACIONAL 8 
 
COORDENAÇÃO DE ENGENHARIA 
LABORATÓRIO COMPUTAÇÃO 
 A B C D 
1 
2 
 
 
3 B3 
 
 
4 
 
 
Página 2 de 8 
 
 Clique na categoria Suplementos na margem esquerda. 
 Próximo ao final da caixa de diálogo Opções do Excel, verifique se Suplementos do Excel está 
selecionado na caixa Gerenciar e clique em Ir. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Na caixa de diálogo Suplementos, marque as caixas de seleção de Ferramentas de Análise e 
Solver; em seguida, clique em OK. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Nota: Se o Excel exibir uma mensagem declarando que não pode executar esse suplemento e solicitar 
que você o instale, clique em Sim para instalá-lo. Nesse caso, como você está instalando dois 
suplementos, o Excel solicita a instalação duas vezes; uma vez para o Analysis ToolPak e uma para o 
Solver. 
No menu Dados, observe que um grupo Análise foi adicionado. Esse grupo contém botões de comando de 
Análise de Dados e do suplemento Solver, com os seguintes ícones: 
 
 
 
 
 
Agora o programa está pronto para começar a usar esses suplementos 
 
 
 
Página 3 de 8 
 
 
1.4 Solução do Simplex usando Solver do Excel 
 
Modelos de programação linear podem envolver muitas variáveis e restrições de tal forma que uma 
maneira adequada de se resolver tais modelos requer o uso do computador. No Excel pode-se usar o 
“Solver” para se resolver um problema de programação linear através da planilha. 
 
Seja o exemplo: Max Z =5x1 + 4x2 
S/a 6x1 + 4x2  24 
 x1 + 2x2  6 
 -x1 + x2  1 
 0x1 + x2  2 
x1  0; x2  0 
 
No Excel o processo irá requerer três etapas: 
 Etapa-1: Inclusão dos dados do problema na planilha eletrônica 
 Etapa-2: Fornecimento das informações ao “Solver” 
 Etapa-3: Resolução do problema 
 
Etapa-1: 
No Excel, o “Solver” utiliza a planilha como entrada de dados e saída de resultados. O modelo solicita 
quatro tipos de informação que são informadas em: 
 Células de dados de entrada (B5:C9 e F6:F9) corresponde aos coeficientes das variáveis de decisão 
na função objetivo e nas restrições 
 Células que representam o valor das variáveis (B13:C13) e da função objetivo (D13 = D5) 
 Definições algébricas da função objetivo e do lado esquerdo das restrições (D5:D9) através das 
fórmulas: 
- Função objetivo =5x1 + 4x2  Célula D5 = B5*$B$13+C5*$C$13 
- Restrição-1 = 6x1 + 4x2  Célula D6 = B6*$B$13+C6*$C$13 
- Restrição-2 = x1 + 2x2  Célula D7 = B7*$B$13+C7*$C$13 
- Restrição-3 = -x1 + x2  Célula D8 = B8*$B$13+C8*$C$13 
- Restrição-4 = 0x1 + x2  Célula D9 = B9*$B$13+C9*$C$13 
 Células que fornecem nomes ou símbolos explicativos 
 
 
 
 
 
 
 
 
 
 
 
 
 
Página 4 de 8 
 
Nota: O posicionamento desses quatro tipos de informação na planilha pode ser qualquer, isto é, não 
precisa seguir a disposição mostrada nesse exemplo. O importante é que elas possam ser referenciadas 
pelo “Solver”. 
 
Etapa-2: 
Fornecimento de informações ao “Solver” 
 No menu <Dados> do Excel no campo [Análise] selecionar a opção “Solver” 
 Deverá abrir a caixa de diálogo “Parâmetros do Solver” 
 Indique onde está a função objetivo na planilha colocando o endereço da célula no campo: 
“Definir Objetivo” = $D$5 
 Assinale qual o critério de otimização selecionando o “Radio Button”  Máx 
 Indique a região onde serão colocados os valores das variáveis de decisão na função objetivo 
informando no campo “Alterando células variáveis” = $B$13:$C$13 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Informe as restrições do problema clicando no botão <Adicionar> da caixa de diálogo “Parâmetros 
do Solver” 
 Deverá aparecer a caixa de diálogo “Adicionar Restrição” 
 
 
 
 
 
 
 
 
 
 
 
Página 5 de 8 
 
 Informe cada restrição indicando 
- “Referência de Células” = as células que descrevem o lado esquerdo (das variáveis) da restrição = 
$D$6:$D$9 
- Campo tipo de desigualdade (<=) 
- “Restrição” = Célula onde está o valor do lado direito da restrição (vetor b) = $F$6:$F$9 
 Clicar o botão <OK> 
 Adicionar as restrições de não negatividade clicando no botão <Adicionar> da caixa de diálogo 
“Parâmetros do Solver” 
 Informe a restrição de não negatividade indicando 
- “Referência de Células” = as células que descrevem o lado esquerdo (das variáveis) da restrição = 
$B$13:$C$13 
- Campo tipo de desigualdade (>=) 
- “Restrição” = Célula onde está o valor do lado direito da restrição (vetor b) = 0 
 Clicar o botão <OK> 
 Selecionar na text box “Selecionar um método de solução” a opção “LP Simplex” 
 
Etapa-3 
 Para resolver o problema clique no boltão <Resolver> existente no canto inferior direito da caixa de 
diálogo “Parâmetros do Solver” 
 Ao final do processo será mostrada a caixa de diálogo “Resultados do Solver” 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Se a montagem do modelo estiver correta, deverá aparecer mensagem: “O Solver encontrou uma 
solução. Todas as restrições e condições de adequação foram satisfeitas” 
- O valor ótimo da Função Objetivo z aparecerá na célula D5 
- O valor das variáveis de decisão para a solução ótima vai aparecer nas células B13 e C13 
 Se o problema não tiver solução viável deverá aparecer mensagem: “Solver não pode achar 
solução viável” 
 Se o valor ótimo da função objetivo for ilimitado, o Solver informará: “Os valores das células 
destino não convergem” 
 
Página 6 de 8 
 
 Mais detalhes sobre a solução poderão ser obtidos selecionado uma das opções: 
- Resposta 
- Sensibilidade 
- Limites 
 
1.5 Exemplo 
 
Determinada empresa está interessada em maximizar o lucro mensal proveniente de quatro de seus 
produtos designados por 1, 2, 3 e 4. 
Para fabricar esses quatro produtos ela utiliza dois tipos de máquinas e dois tipos de mão-de-obra, dadas 
nas tabelas 1 e 2 respectivamente. 
 
Máquina Tempo disponível (maq.hora/mês) 
M1 80 
M2 20 
 
Mão-de-obra Tempo disponível (homens-hora/mês) 
Mo1 120 
Mo2 160 
 
O setor técnico da empresa fornece os seguintes quadros de produtividade: 
 
(A) Número de máquinas-hora (ou horas de funcionamento de cada máquina) para produzir uma 
unidade de cada produto 
 Produtos 
Máquina 1 2 3 4 
M1 5 4 8 9 
M2 2 6 - 8 
 
(B) Número de homens-hora (ou horas de trabalho por homem) para produzir uma unidade de cada 
produto 
 Produtos 
Mão-de-obra 1 2 3 4 
Mo1 2 4 2 8 
Mo2 7 3 - 7 
 
(C) O setor comercial da empresa fornece 
Produtos Potencial de Vendas (unidades/mês) Lucro unitário (R$) 
1 70 10 
2 60 8 
3 40 9 
4 20 7 
 
Qual deve ser a produção mensal dos produtos 1, 2, 3 e 4 para que o lucro mensal da empresa seja 
máximo? Formular um modelo de programação linear para o problema. e resolver com o “Solver” do Excel. 
 
 
 
 
Página 7 de 8 
 
Solução: 
Definindo: 
 xi = nível de produção mensal do produto-i 
 Z = lucro mensal da empresa 
Entãoo problema fica: 
max Z = 10.x1 + 8.x2 + 9.x3 + 7.x4 
 x1  70 
 x2  60 
 x3  40 
 x4  20 
5.x1 + 4.x2 + 8.x3 + 9.x4  80 
2.x1 + 6.x2 + 0.x3 + 8.x4  20 
2.x1 + 4.x2 + 2.x3 + 8.x4  120 
7.x1 + 3.x2 + 0.x3 + 7.x4  160 
x1  0; x2  0; x3  0; x4  0 
 
Etapa-1: 
Montando o tableau do Simplex na planilha tem-se o quadro da figura abaixo: 
 
 
 
 
 
 
 
 
 
 
 
 
 
Nessa planilha tem-se: 
- Função objetivo =10.x1 + 8.x2 + 9.x3 + 7.x4  Célula F5 =B5*$B$16+C5*$C$16+D5*$D$16+E5*$E$16 
- Restrição-1: x1  70  Célula F6 =B6*$B$16+C6*$C$16+D6*$D$16+E6*$E$16 
- Restrição-2: x2  60  Célula F7 =B7*$B$16+C7*$C$16+D7*$D$16+E7*$E$16 
- Restrição-3: x3  40  Célula F8 =B8*$B$16+C8*$C$16+D8*$D$16+E8*$E$16 
- Restrição-4: x4  20  Célula F9 =B9*$B$16+C9*$C$16+D9*$D$16+E9*$E$16 
- Restrição-5: 5.x1 + 4.x2 + 8.x3 + 9.x4  80  Célula F10 =B10*$B$16+C10*$C$16+D10*$D$16+E10*$E$16 
- Restrição-6: 2.x1 + 6.x2 + 0.x3 + 8.x4  20  Célula F11 =B11*$B$16+C11*$C$16+D11*$D$16+E11*$E$16 
- Restrição-7: 2.x1 + 4.x2 + 2.x3 + 8.x4  120  Célula F12 =B12*$B$16+C12*$C$16+D12*$D$16+E12*$E$16 
- Restrição-8: 7.x1 + 3.x2 + 0.x3 + 7.x4  160  Célula F13 =B13*$B$16+C13*$C$16+D13*$D$16+E13*$E$16 
 
Etapa-2: 
Fornecimento de informações ao “Solver” 
 No menu <Dados> do Excel no campo [Análise] selecionar a opção “Solver” 
 
Página 8 de 8 
 
 Deverá abrir a caixa de diálogo “Parâmetros do Solver” 
 Indique onde está a função objetivo na planilha colocando o endereço da célula no campo: 
“Definir Objetivo” = $F$5 
 Assinale qual o critério de otimização selecionando o “Radio Button”  Máx 
 Indique a região onde serão colocados os valores das variáveis de decisão na função objetivo 
informando no campo “Alterando células variáveis” = $B$16:$C$16 
 Informe as restrições do problema clicando no botão <Adicionar> da caixa de diálogo “Parâmetros 
do Solver” 
 Deverá aparecer a caixa de diálogo “Adicionar Restrição” 
 Informe cada restrição indicando 
- “Referência de Células” = as células que descrevem o lado esquerdo (das variáveis) da restrição = 
$F$6:$F$13 
- Campo tipo de desigualdade (<=) 
- “Restrição” = Célula onde está o valor do lado direito da restrição (vetor b) = $H$6:$H$13 
 Clicar o botão <OK> 
 Adicionar as restrições de não negatividade clicando no botão <Adicionar> da caixa de diálogo 
“Parâmetros do Solver” 
 Informe a restrição de não negatividade indicando 
- “Referência de Células” = as células que descrevem o lado esquerdo (das variáveis) da restrição = 
$B$16:$E$16 
- Campo tipo de desigualdade (>=) 
- “Restrição” = Célula onde está o valor do lado direito da restrição (vetor b) = 0 
 Clicar o botão <OK> 
 Selecionar na text box “Selecionar um método de solução” a opção “LP Simplex” 
 
Etapa-3 
 Para resolver o problema clique no boltão <Resolver> existente no canto inferior direito da caixa de 
diálogo “Parâmetros do Solver” 
 Ao final do processo será mostrada a caixa de diálogo “Resultados do Solver” 
 
Solução: 
 x1 = 10. 
 x2 = 0. 
 x3 = 3,75. 
 x4 = 0 
 Valor da Função Objetivo na solução: Z = 133,75