VA_Pesquisa_Operacional_Aula_5_Tema_5

Prévia do material em texto

Tema 5: Solução de Problemas de 
Programação Linear – Parte I 
 
Profª Ivonete Melo de Carvalho, Me 
Para início de conversa 
Forma padrão para o método simplex 
•  Modelos Equivalentes para o Uso do Método 
Simplex 
•  Necessariamente, o problema de programação 
linear, deve estar na forma padrão. 
⎪
⎩
⎪
⎨
⎧
≥
≤+
≤+
+=
0x,x
427x3x
10010x10x
:aSujeito
40x60xZMax
:ObjetivoFunção
21
21
21
21
Problema de Minimização 
Se a função objetivo for de minimizar, devemos 
multiplicá-la por (-1), obtendo uma função 
equivalente para maximização. 
Considere o seguinte problema de PL: 
Minimizar: Z = 3x1+4x2+x3 
Sujeito a: 
x1 + x2 + x3 ≤ 10 
3x1 + x2 - x3 ≤ 20 
x1, x2, x3 ≥ 0 
Quando a solução ótima for 
encontrada para o equivalente, 
não se esquecer de multiplicar 
por (-1) o “-Z” para obter “Z”. 
Modelo Equivalente na Forma Padrão 
Minimizar: Z = 3x1 - 4x2 +x3 *(-1) 
Maximizar: (-Z) = –3x1 + 4x2 – x3 
Sujeito a: 
x1 + x2 + x3 ≤ 10 
3x1 + x2 - x3 ≤ 20 
x1, x2, x3 ≥ 0 
Se uma variável do modelo não 
possuir a condição de não 
negatividade, pode-se substituí-la 
pela diferença de duas outras 
variáveis não negativas. 
Problema de Variável Livre 
Considere o seguinte problema de PL: 
Maximizar Z = x1 + 2x2 + x3 
Sujeito a: x1 + x2 + x3 ≤ 10 
 2x1 + 3x2 ≤ 20 
 x1, x3 ≥ 0 
 x2 → livre 
 
Modelo Equivalente na Forma Padrão 
Modelo Original: 
Faremos : x2 = x4 - x5 
Max Z = x1 + 2x2 + x3 
S.a: x1 + x2 + x3 ≤ 10 
 2x1 + 3x2 ≤ 20 
 x1, x3 ≥ 0 
 x2 → livre 
Quando a solução ótima for 
ca lcu lada para o modelo 
equivalente, não se esquecer de 
substituir (x4 - x5) por “x2”. 
Modelo Equivalente na Forma Padrão 
Faremos : x2 = x4 - x5 
Modelo Equivalente: 
Max Z = x1 + 2(x4-x5) + x3 
S.a: x1 + (x4-x5) + x3 ≤ 10 
 2x1 + 3(x4-x5) ≤ 20 
 x1, x3 , x4, x5 ≥ 0 
Continuando 
A segunda restrição aparece 
com sinal “≥” e a terceira 
restrição aparece com sinal “=” 
Problema de Solução Inicial 
Considere o seguinte problema de PL: 
Maximizar Z = x1 + x2 + x3 
Sujeito a: 
2x1 + x2 - x3 ≤ 10 
x1 + x2 +2x3 ≥ 20 
2x1 + x2 +3x3 = 60 
x1, x2, x3 ≥ 0 
 
Problema de Solução Inicial 
Aparece quando: 
•  A restrição é do tipo ≥ 
 Nesse caso, a variável de folga é subtraída e o seu 
valor é negativo, quando 
se anulam as variáveis de 
decisão; 
• A restrição é do tipo = 
Essas res t r i ções não 
recebem variáveis de 
folga. 
 
A função W deve ser escrita em 
termos das variáveis originais do 
problema e comporá o novo 
objetivo a ser minimizado. 
Quando as variáveis auxiliares 
forem todas não-básicas, então W 
será igual a zero . 
Modelo Equivalente na Forma Padrão 
A inserção das variáveis auxiliares no problema de programação 
linear nos leva a criar uma função objetivo auxiliar (W), 
formada pela soma das variáveis auxiliares: 
W = a1 + a2 + a3 + ... + an 
Modelo Equivalente na Forma Padrão 
Para estes casos, acrescentamos nas restrições do tipo 
“≥” as variáveis de folga e variáveis auxiliares 
(denominadas de “ai”) e nas restrições do tipo “=” 
acrescentamos apenas variáveis auxiliares com o 
objet ivo de formar um 
mode lo equ iva lente de 
programação linear, para 
então podermos utilizar o 
m é t o d o s i m p l e x p a r a 
solucioná-lo. 
 
Modelo Equivalente na Forma Padrão 
As variáveis auxiliares são abandonadas quando 
todas são, ao mesmo tempo, variáveis não-básicas no 
problema. Consequentemente a função objetivo 
auxiliar também é abandonada. 
Ter-se-á neste momento, o 
modelo original com uma 
solução básica inicial 
procurada. 
Vamos praticar? 
Programação Linear Utilizando 
Microsoft Excel 
Resolução do modelo de PL com o “Solver” 
Função Objetivo: 
Min Z = 22x1 + 26x2 + 30x3 
Sujeita a: 
20x1 + 20x2 + 10x3 ≥ 250 
20x1 + 40x2 + 10x3 ≥ 230 
30x1 + 20x2 + 40x3 ≥ 120 
x1 , x2, x3 ≥ 0 
 
Instale a ferramenta (1) 
Instale a ferramenta (2) 
Preparando a planilha 
Preenchendo os dados 
O “solver” 
•  Na sequência serão apresentadas as telas 
da planilha com os comandos necessários 
para a utilização da ferramenta Solver da 
planilha Excel. 
•  Abra sua planilha 
e acompanhe as 
orientações. 
Registrar a célula com 
a fórmula de Z (E11) Selecionar o Min 
para a Função Objetivo 
“Células” para informar 
os valores das variáveis 
de decisão. 
Adicionar as Restrições 
Célula da 
fórmula do 1º 
membro da 
restrição. 
Sinal da 1ª restrição. 
Célula do 2º 
membro 
da 1ª restrição 
Registrar a 1ª 
restrição. 
Clicar em Adicionar 
para inserir novas 
restrições. 
Registrar a 1ª 
restrição. 
Registrar a “três” 
restrições e “OK” para sair. 
Registrar a 3ª 
restrição. 
Clicar em “ Opções” 
para registros adicionais. 
Conferir os 
registros 
Modelo Linear 
Não 
negatividade 
para x1, x2, 
x3. 
Clique em “OK” 
 para sair 
Clicar em “Resolver” 
Relatório (Resposta) 
Solução Ótimo 
x1=12,5 ; x2=0; x3=0 
Mim Z =275 
Finalizando 
Utilizando o Excel – Solver 
•  O Solver é uma ferramenta que nos 
possibilita resolver problemas particulares da 
programação linear. 
•  É só entrar com os 
pa râme t ro s e e l e 
ajusta o problema, 
resolve e informa a 
solução (se ela existir). 
•  Trabalhe no Excel.