PO UNIP 2

Prévia do material em texto

Unidade II 
 
 
PESQUISA OPERACIONAL 
 
 
Prof. Mauricio Fanno 
Resolução pelo Método Algébrico 
Encontrar a solução ótima por meio da resolução do sistema de 
equações estabelecidas a partir das inequações de restrições. 
Problemas 
 Complexidade na resolução – na prática, grande quantidade 
de equações. 
 Sistemas de equações com soluções indeterminadas. Menos 
equações do que incógnitas. 
Utilização de um algoritmo, chamado Simplex, criado por 
Dantzig, em 1947. 
 
 
Algoritmo 
Algoritmo é, segundo Houaiss 
 Sequência finita de regras, raciocínios ou operações que, 
aplicada a um número finito de dados, permite solucionar 
classes semelhantes de problemas. 
 Processo de cálculo; encadeamento das ações necessárias 
ao cumprimento de uma tarefa; processo efetivo, que produz 
uma solução para um problema num número finito de etapas. 
 Mecanismo que utiliza representações análogas para resolver 
problemas ou atingir um fim, em outros campos do raciocínio e 
da lógica. 
 Conjunto das regras e procedimentos lógicos perfeitamente 
definidos que levam à solução de um problema num número 
finito de etapas. 
 
Algoritmo Simplex: 
Conceitos Matemáticos 
Variáveis de entrada ou variáveis de decisão 
 O que desejamos saber; o que será otimizado. 
Variáveis de folga ou residuais 
 Utilizadas quando a inequação trabalhada apresenta uma 
desigualdade do tipo ≤. Corresponde à parcela não utilizada 
de determinado recurso. 
Variáveis de excesso e variáveis artificiais 
 As veremos mais à frente. Usadas quando não existe variável 
de folga. 
 
Situação-problema 
 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 uma das máquinas 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. 
 
Situação-problema 
 Será produzida, no mínimo, uma unidade de A e de B. Cada 
unidade vendida do produto A gera um lucro de R$ 80 e cada 
unidade do produto B, um lucro de R$ 60. Existe uma previsão 
máxima de demanda para o produto B, de 3 unidades, não 
havendo restrições quanto à demanda do produto A. Deseja-se 
saber quantas unidades de A e de B devem ser produzidas, de 
forma a maximizar o lucro e, ao mesmo tempo, obedecer a 
todas as restrições desse enunciado. 
Modelagem matemática 
Função objetivo 
 
Restrições 
 
 
Algoritmo Simplex: 
Etapas 
 1º passo: Transformar as inequações das restrições em 
equações, através da utilização das variáveis de folga. 
Restrição I: Máximo de horas disponível na máquina M1: 
4x + 6y ≤ 24 
 Significa que não podemos usar mais do que 24 horas de 
máquina M1, com o produto A que usa 4 horas e com o 
produto B que usa 6. 
Essa mesma situação poderia ser descrita como uma equação: 
4x + 6y + x2 = 24 
 Onde x2 significa a eventual sobra de horas na máquina M1 
Algoritmo Simplex: 
Etapas 
Transformando todas as inequações em equações temos: 
4x + 6y + x2 = 24 
4x + 2y + x3 = 16 
y + x4 = 24 
Note: 
 x2; x3 ; x4; são as variáveis residuais ou de folga 
 Temos 5 incógnitas (n=5) 
 Temos 3 equações (m=3) 
 Um sistema só é determinado se os números de equações 
e incógnitas for igual (m=n) 
 Essa situação caracteriza, portanto, um sistema de 
equações indeterminado. 
Algoritmo Simplex: 
Etapas 
 Um sistema de equações indeterminadas significa que não há 
apenas uma solução e sim infinitas soluções viáveis. Lembre-
se do polígono de soluções no método gráfico. 
Assim, define-se 
 Solução viável: uma das infinitas soluções possíveis. 
 Solução básica: solução básica quando se fixa (m-n) 
incógnitas igual a zero. 
 Base do sistema: qualquer solução básica, ou seja, um 
sistema em que temos m incógnitas e m equações. 
 Solução básica viável é a obtida quando se fica o (m-n) 
incógnitas iguais a zero e determina-se a solução para as 
demais incógnitas restantes. 
 
Algoritmo Simplex: 
Etapas 
O modelo matemático para aplicação do algoritmo Simplex no 
nosso exemplo é: 
4x + 6y + 1x2 + 0x3 + 0x4 = 24 
4x + 2y + 0x2 + 1x3 + 0x4 = 16 
0x + 1y + 0x2 + 0x3 + 1x4 = 3 
 Colocamos todos os coeficientes, inclusive quando são 0 e 1, 
porque isso nos será útil no uso do Simplex. 
Algoritmo Simplex: 
Etapas 
2º passo: Montar a planilha do algoritmo: 
 Criar as colunas 
 Base; 
 Uma coluna para cada variável; 
 Uma coluna para o termo independente. 
 Duas colunas de cálculos 
 Termo independente dividido pela coluna de trabalho; 
 Variáveis a incluir e a excluir. 
A aparência do cabeçalho da planilha ficará assim: 
 
 
 
 
 Criar as linhas 
 Uma para cada variável que não estiver zerada; 
 Uma linha de controle, no nosso caso, o lucro obtido. 
 
 
Algoritmo Simplex: 
Etapas 
A aparência da planilha fica da seguinte forma: 
 
 
 
 
 
 
 
 3º passo: Inserir, na tabela, os coeficientes das diversas 
equações e, na linha de controle, o lucro de cada produto 
com sinal negativo. 
Algoritmo Simplex: 
Etapas 
A planilha para o cálculo do algoritmo fica assim: 
 
 
 
 
 
 
 
 
 A partir daí, começaremos a sequência de cálculos. 
Algoritmo Simplex: 
Etapas 
Interatividade 
Quando dizemos que um sistema de equações é indeterminado, 
não podemos afirmar que: 
a) A quantidade de soluções viáveis é infinita. 
b) A resolução do sistema deve ser feita por tentativas. 
c) Na solução, deveremos assumir que algumas das incógnitas 
deverá assumir, por hipótese, o valor zero. 
d) O número de incógnitas é idêntico ao número de equações. 
e) A diferença entre o número de incógnitas e o numero de 
equações é a quantidade de incógnitas que deverá assumir 
valor zero em cada tentativa. 
 
Algoritmo Simplex: 
Cálculos 
 4º passo: Determinar a coluna de trabalho. É aquela que 
apresenta, na linha de controle, o maior valor negativo. No nosso 
caso, a coluna dos x, cuja coluna de controle é -80. Dividimos, em 
seguida, os valores do termo independente pela coluna de 
trabalho, essa é a variável que entrará na próxima tentativa. 
 
 
 
 
 
 
 
 
 
Algoritmo Simplex: 
Cálculos 
 A variável que irá sair é aquela que apresentar, na coluna “termo 
independente ÷ coluna de trabalho, o menor valor positivo. 
 
 
 
 
 
 
 
 O cruzamento da coluna de controle com a linha da variável que 
sai é chamado de pivô. 
 
Algoritmo Simplex: 
Cálculos 
 5º passo: Substituir, na base, a linha que sai pela que entra e 
calcular os novos coeficientes, dividindo os valores da linha 
que sai pelo valor do pivô. 
 
Máquina M1 4 6 1 0 0 24 6 Entra 
Máquina M2 4 2 0 1 0 16 4 x 
Demanda de B 0 1 0 0 1 3 ∞ Sai 
Controle /lucro -80 -60 0 0 0 0 
Base 
Variáveis de 
Entrada Variáveis Residuais Termo 
independent
e 
Termo 
independent
e ÷ coluna de 
trabalho 
Variávei
s a 
incluir e 
a excluir 
Produto 
A 
Produto 
B 
Máquin
a M1 
Máquina 
M2 
Demanda do 
Produto B 
x y b 
Máquina M1 
Produto A x 1 0,5 0 0,25 0 4 
Demanda de B 
Controle /lucro 
Algoritmo Simplex: 
Cálculos 
 6º passo: Colocar, no cruzamento de linhas e colunas de 
mesma variável, o valor 1 e nos demais espaços dessas 
colunas, o valor 0. 
 
Máquina M1 4 6 1 0 0 24 6 Entra 
Máquina M2 4 2 0 1 0 16 4 x 
Demanda de B 0 1 0 0 1 3 ∞ Sai 
Controle /lucro -80 -60 0 0 0 0 
Base 
Variáveis de Entrada Variáveis Residuais 
Termo 
independenteTermo 
independente ÷ 
coluna de 
trabalho 
Variáveis 
a incluir e 
a excluir 
Produto A Produto B Máquina M1 Máquina M2 
Demanda do 
Produto B 
x y b 
Máquina M1 0 1 0 
Produto A x 1 0,5 0 0,25 0 4 
Demanda de B 0 0 1 
Controle /lucro 0 0 0 
Algoritmo Simplex: 
Cálculos 
Os valores que faltam para preencher a nova tentativa serão 
determinados pela “regra do retângulo”: O valor do novo elemento 
é igual ao elemento correspondente da base anterior, menos o 
produto dos elementos que estão na diagonal do retângulo que 
não contêm o pivô dividido pelo pivô. Veja o exemplo abaixo: 
 B4 = B1 – (A1 x B2) ÷ A2 
 B4 = 6 – (4 x 2) ÷ 4 = 4 
 B6 = B3 – (A3 x B2) ÷ A2 
 B4 = 1 – (0x2) ÷ 4 = 1 
Algoritmo Simplex: 
Cálculos 
 Aplicando a “regra do retângulo” no nosso exemplo, temos: 
Algoritmo Simplex: 
Cálculos 
 7º passo: Repetimos o processo tantas vezes quanto 
necessário até que, na linha de controle, só apareçam 
números positivos ou nulos: 
 
 
Máquina M1 4 6 1 0 0 24 6 Entra 
Máquina M2 4 2 0 1 0 16 4 x 
Demanda de B 0 1 0 0 1 3 ∞ Sai 
Controle /lucro -80 -60 0 0 0 0 
Base 
Variáveis de 
Entrada Variáveis Residuais Termo 
independent
e 
Termo 
independente 
÷ coluna de 
trabalho 
Variávei
s a 
incluir e 
a excluir 
Produto 
A 
Produto 
B 
Máquina 
M1 
Máquina 
M2 
Demanda do 
Produto B 
x y b 
Máquina M1 0 4 1 -1 0 8 2 Entra 
Produto A x 1 0,5 0 0,25 0 4 8 y 
Demanda de B 0 1 0 0 1 3 3 Sai 
Controle /lucro 0 -20 0 20 0 320 
Algoritmo Simplex: 
Cálculos 
 
 
 
 
 
 
 
 
 
 
Algoritmo Simplex: 
Cálculos 
Algoritmo Simplex: 
Resumo 
 Chegamos à última tentativa: todos os valores da linha de 
controle são positivos ou nulos. 
 
 
 
 
 
Em resumo 
 Devemos produzir 3 produtos A(*). 
 Devemos produzir 2 produtos B (**) 
 Irá sobrar uma unidade de demanda do produto B (***) 
 O lucro será de $360,00 e é máximo (****) 
 
Interatividade 
Com relação ao algoritmo Simplex, é incorreto afirmar que: 
a) A coluna de trabalho é aquela que apresenta maior valor 
negativo na linha de controle. 
b) No cruzamento de linha e coluna correspondente à mesma 
variável, o valor a ser colocado é 1. 
c) A variável que entra numa próxima tentativa é a que apresenta 
maior valor positivo na coluna termo independente ÷ coluna 
de trabalho. 
d) A variável que sai numa próxima tentativa é a que apresenta 
menor valor positivo na coluna termo independente ÷ coluna 
de trabalho. 
e) Pivô é o cruzamento da linha da variável que sai com a coluna 
da variável que entra. 
Resolução pelo Método Computacional 
 Utilização de ferramentas computacionais para o cálculo das 
soluções ótimas. 
Muitas opções existentes 
 LINDO; 
 SAS; 
 GLP; 
 SOLVER, do Excel, que iremos utilizar. 
Basicamente, o algoritmo Simplex informatizado. 
 
Ferramenta Solver do Excel®: 
Habilitação 
O padrão é a ferramenta estar desativada. Para ativá-la, siga 
os passos: 
 Arquivo/Opções/Suplementos/Gerenciar/Suplementos do Excel. 
 Clique em Ir e selecione, na tela que aparecerá, a opção Solver. 
Clicando em OK, a ferramenta estará habilitada. 
Observação: A aparência das telas mostradas depende da 
geração de Excel usada, mas, em todas, o caminho é o mesmo. 
Nesta exposição usamos o Excel 2013. 
 
Ferramenta Solver do Excel®: 
Habilitação 
Ferramenta Solver do Excel®: 
Montagem da Planilha de Dados 
 Elaborar uma planilha Excel com os elementos que compõem 
o modelo matemático (variáveis, função objetivo e restrições). 
Vamos descrever o processo usando o exemplo dos Produtos A 
e B produzidos nas máquinas M1 e M2: 
 Função objetivo 
 
 Restrições 
 
Ferramenta Solver do Excel®: 
Montagem da Planilha de Dados 
Colocar na planilha todos os dados e equações características 
do problema: 
 
 
 
 
 
 
 Células B4 e C4 – ficam vazias. Nelas aparecerá o resultado 
desejado. Correspondem às variáveis de decisão. 
 Células B5 e C5 – Respectivamente, o lucro unitário do produto 
A e do Produto B. 
Ferramenta Solver do Excel®: 
Montagem da Planilha de Dados 
 
 
 
 
 
 
Célula D5 – Função objetivo: 
 D5 = (B4 * B5) + (C4 * C5). 
 Células B8; B9 e B10 – Necessidades horárias e de demanda 
para produzir o Produto A. 
 Células C8; C9 e C10 – Necessidades horárias e de demanda 
para produzir o Produto B. 
Ferramenta Solver do Excel®: 
Montagem da Planilha de Dados 
 
 
 
 
 
 
 Célula D8 – Restrição I: D8 = (B4*B8) + (C4*C8). 
 Célula D9 – Restrição II: D9 = (B4*B9) + (C4*C9). 
 Célula D10 – Restrição III: D10 = (B4*B10) + (C4*C10). 
 
Ferramenta Solver do Excel®: 
Montagem da Planilha de Dados 
 
 
 
 
 
 
 
 Células E8; E9 e E10 – Valores máximos disponíveis 
(o termo independente das inequações). 
Ferramenta Solver do Excel®: 
Especificação dos Parâmetros 
Acessar o Solver. Isso é feito na opção dados da Barra de 
Ferramentas, clicando em Solver: 
 
 
 
 
 
 
 
 Abrirá a caixa de parâmetros do Solver, na qual deveremos 
colocar as informações do problema, agora disponibilizadas 
na planilha. Faremos isso no próximo módulo. 
 
Interatividade 
Uma das seguintes afirmativas é falsa. Qual? 
a) Normalmente, a opção Solver está desativada no Excel. 
b) As informações características do problema devem ser 
colocadas na forma de planilha no Excel. 
c) A planilha com as informações do problema deve conter 
a função objetivo, as variáveis de decisão e as restrições 
d) Assim como no método algébrico, devemos transformar as 
inequações em equações. 
e) O acesso ao Solver é feito por meio da aba Dados, na barra 
de ferramentas. 
Ferramenta Solver do Excel®: 
Especificação dos Parâmetros 
Ferramenta Solver do Excel®: 
Especificação dos Parâmetros 
O primeiro campo a ser preenchido é Definir Objetivo. Use 
o mouse para selecionar a célula D5 na planilha, na qual 
colocamos a função objetivo: 
 
 
 
 Observe a seleção da opção Máx., que significa que desejamos 
maximizar a função objetivo. Podemos, em outras situações, 
desejar minimizar ou obter um valor exato. 
Ferramenta Solver do Excel®: 
Especificação dos Parâmetros 
Em seguida, colocamos no campo Alterando Células Variáveis, 
as células correspondentes às variáveis de decisão: 
 
 
 
Chegou a hora de colocarmos as restrições. Para isso, vamos 
clicar no botão Adicionar: 
 
 
Aparecerá a janela: 
 
 
Ferramenta Solver do Excel®: 
Especificação dos Parâmetros 
 Na caixa aberta, inserir no campo Referencia de Célula, a 
célula na qual está a fórmula da restrição (no caso da 
restrição I, a célula D8) e no campo Restrição, a célula na qual 
está o valor restrito (no caso da restrição I, a célula E8). 
 Observe que o sinal de desigualdade já está correto, ou seja, 
≤. Em outros casos este sinal deverá ser alterado. 
Ferramenta Solver do Excel®: 
Especificação dos Parâmetros 
Ferramenta Solver do Excel®: 
Especificação dos Parâmetros 
 Ao clicar em adicionar, a caixa fica pronta para receber a 
próxima restrição. 
 Devemos repetir este procedimento até que todas as restrições 
estejam adicionadas. 
Depois da última adição, clicar em OK. A caixa sumirá e voltará 
aos parâmetros do Solver: 
 
 
 
 
 Os botões ao lado do campo Sujeito às Restrições permitem 
retornar, editar; alterar ou excluir as restrições. 
Ferramenta Solver do Excel®: 
Especificação dos Parâmetros 
Duas seleções importantes devem ser feitas: 
 Selecionar a opção Tornar Variáveis Irrestritas Não Negativas 
(lembre-se das restrições lógicas x 0 e y 0). 
 Optar, na caixa abaixo dessa seleção, pelo cálculo de LP Simplex. Observe o botão Opções. Ele permite alterar parâmetros de 
precisão e velocidade, se necessário. No nosso caso não 
será necessário. 
Ferramenta Solver do Excel®: 
Especificação dos Parâmetros 
 Estamos prontos para resolver o problema. 
 
Ferramenta Solver do Excel®: 
Resolução 
 
 
 
 
 
 
 
 
 
 
 Clicando no botão Resolver, o Excel irá calcular 
a solução ótima. 
Ferramenta Solver do Excel®: 
Resolução 
Resolução Final 
Interatividade 
Uma das seguintes afirmativas é falsa. Qual? 
a) O primeiro passo para a utilização do Solver é montar uma 
planilha com todas as informações do modelo matemático. 
b) A função objetivo e as restrições devem ser colocadas no 
Excel como fórmulas matemáticas, usando as diversas 
células. 
c) Na tela de parâmetros do Solver, deve ser colocada a função 
objetivo no campo Alterando Células Variáveis. 
d) As restrições devem ser colocadas uma a uma na caixa 
Adicionar Restrição. 
e) As restrições lógicas são atendidas por meio da seleção do 
campo Tornar Variáveis Irrestritas Não Negativas. 
 
 
 
 
ATÉ A PRÓXIMA! 
	Slide Number 1
	Resolução pelo Método Algébrico
	Algoritmo
	Algoritmo Simplex:�Conceitos Matemáticos
	Situação-problema
	Situação-problema
	Modelagem matemática
	Algoritmo Simplex:�Etapas
	Algoritmo Simplex: �Etapas
	Algoritmo Simplex:�Etapas
	Algoritmo Simplex:�Etapas
	Algoritmo Simplex:�Etapas
	Algoritmo Simplex:�Etapas
	Algoritmo Simplex:�Etapas
	Algoritmo Simplex:�Etapas
	Interatividade
	Resposta
	Algoritmo Simplex:�Cálculos
	Algoritmo Simplex:�Cálculos
	Algoritmo Simplex:�Cálculos
	Algoritmo Simplex:�Cálculos
	Algoritmo Simplex:�Cálculos
	Algoritmo Simplex:�Cálculos
	Algoritmo Simplex:�Cálculos
	Algoritmo Simplex:�Cálculos
	Algoritmo Simplex:�Cálculos
	Algoritmo Simplex:�Resumo
	Interatividade
	Resposta
	Resolução pelo Método Computacional
	Ferramenta Solver do Excel®:�Habilitação
	Ferramenta Solver do Excel®:�Habilitação
	Ferramenta Solver do Excel®: �Montagem da Planilha de Dados
	Ferramenta Solver do Excel®:�Montagem da Planilha de Dados
	Ferramenta Solver do Excel®:�Montagem da Planilha de Dados
	Ferramenta Solver do Excel®:�Montagem da Planilha de Dados
	Ferramenta Solver do Excel®:�Montagem da Planilha de Dados
	Ferramenta Solver do Excel®: �Especificação dos Parâmetros
	Interatividade
	Resposta
	Ferramenta Solver do Excel®: �Especificação dos Parâmetros
	Ferramenta Solver do Excel®:�Especificação dos Parâmetros
	Ferramenta Solver do Excel®: �Especificação dos Parâmetros
	Ferramenta Solver do Excel®: �Especificação dos Parâmetros
	Ferramenta Solver do Excel®: �Especificação dos Parâmetros
	Ferramenta Solver do Excel®: �Especificação dos Parâmetros
	Ferramenta Solver do Excel®: �Especificação dos Parâmetros
	Ferramenta Solver do Excel®: �Especificação dos Parâmetros
	Ferramenta Solver do Excel®: �Resolução
	Ferramenta Solver do Excel®:�Resolução
	Resolução Final
	Interatividade
	Resposta
	Slide Number 54