PESQUISA OPERACIONAL FAFIRE

Prévia do material em texto

PESQUISA OPERACIONAL 
Introdução – Decisão 
Um profissional que assume uma função de gerente (gestor) em uma empresa logo se depara 
com situações onde deverá tomar algum tipo de decisão.  
E é exatamente essa a principal característica deste gerente (gestor)  para os outros 
funcionários: TOMAR DECISÕES. 
À medida que este profissional vai ascendendo na carreira, os problemas e as decisões vão se 
tornando mais complexas e de maior responsabilidade. 
De fato, tomar decisões é uma tarefa básica da gestão, nos seus vários níveis, estratégico, 
gerencial (tático) ou operacional, devendo ser entendido que o ato de decidir significa fazer 
uma opção entre alternativas de solução que sejam viáveis de serem aplicadas à situação 
 
O que significa decidir ? 
• “Tomar decisões é o processo de escolher uma dentre um conjunto de alternativas” 
(Caravantes, 2005: 446) 
• “ Uma decisão pode ser descrita, de forma simplista, como uma escolha entre 
alternativas ou possibilidades com o objetivo de resolver um problema ou aproveitar 
uma oportunidade.” (Sobral, 2008: 98) 
• “A tomada de decisão ocorre em reação a um problema. Isto é, existe uma 
discrepância entre o estado atual das coisas e o estado desejável que exige uma 
consideração sobre cursos de ação alternativos. (...)O conhecimento sobre a existência 
de um problema e sobre a necessidade de uma decisão depende da percepção da 
pessoa.” (Robbins, 2005: 111) 
• “(...)Embora tudo aquilo que um administrador faz envolva a tomada de decisões, isso 
não significa que todas as decisões sejam complexas e demoradas. Naturalmente, as 
decisões estratégicas têm mais visibilidade, mas os administradores tomam muitas 
pequenas decisões todos os dias. Aliás, quase sempre, as decisões gerenciais são de 
rotina. No entanto, é o conjunto dessas decisões que permite à organização resolver 
problemas, aproveitar oportunidades e, com isso, alcançar seus objetivos.” (Sobral, 
2008: 100) 
Os Administradores devem ter como objetivo em suas tomadas de decisão: 
• minimizar perdas, 
• maximizar ganhos e  
• alcançar uma situação em que, comparativamente, o gestor julgue que haverá 
um ganho entre o estado em que se encontra a organização e o estado em 
que irá encontrar‐se, após implementar essa decisão. 
Uma pesquisa feita com diferentes tipos de organizações na América do Norte pela State 
University of Ohio, nos EUA, teve uma conclusão assustadora: os executivos erram a mão em 
mais de metade das decisões que tomam. E errar a mão, nesse caso, dói no bolso: técnicas 
equivocadas de tomada de decisão custam bilhões de dólares todo ano em tempo e dinheiro 
desperdiçados. A razão desse fenômeno, ao que parece, está na maneira como as  decisões 
são tomadas” (Paul Nutt, 1998) 
 
Exemplos de Problemas de Decisão 
 Se tanto a Matéria Prima quanto a Mão de Obra são limitados, qual a quantidade de 
produtos que maximiza o lucro da empresa? 
 Se um dado combustível é obtido de uma mistura de produto de preços   variados, 
qual a composição de menor custo com poder calorífico   suficiente? 
 Se existem vários caminhos que ligam duas cidades, qual é o que propicia o menor 
gasto de combustível? 
 Se o espaço para armazenamento é limitado, de quanto deve ser o pedido de material 
para atender a demanda de um certo período? 
 
Fatores que afetam a decisão 
 
Vários fatores afetam a tomada de decisão e entre eles podemos destacar: 
• Tempo disponível para a tomada de decisão; 
• A importância da decisão; 
• O ambiente; 
• Certeza / incerteza e risco; 
• Agentes decisores; 
• Conflito de interesses.  
 
Problemas – Tipos  
Todo o problema de decisão apresenta aquilo que podemos chamar genericamente de DADOS 
que após o seu processamento irá gerar INFORMAÇÕES. 
A natureza e a variedade destas informações dependem de cada caso particular:  
 Problemas Estruturados 
 Decisões sob Certeza 
 Variáveis conhecidas e relação entre ação e resultados é 
determinística. Programação Linear. 
 Decisões sob Risco 
 Variáveis conhecidas e relação entre ação e resultados é probabilística. 
 Decisões sob Incerteza 
 Variáveis conhecidas e relação entre ação e resultados é desconhecida 
ou incerta. 
 Problemas Não‐Estruturados  
 Uma ou mais de suas variáveis são desconhecidas ou não pode ser 
determinada com algum grau de confiança. Teoria de filas. 
 
 
DEFINIÇÕES 
 Pesquisa Operacional é uma abordagem científica para a solução de problemas no 
gerenciamento de sistemas complexos. 
EURO (Associação das Sociedades de Pesquisa Operacional da Europa)  
 Por meio do uso de técnicas como a modelagem matemática para analisar situações 
complexas, a Pesquisa Operacional dá aos executivos o poder de tomar decisões mais 
efetivas e de construir sistemas mais produtivos, baseados em dados mais completos, 
consideração de todas as alternativas possíveis, previsões cuidadosas de resultados e 
estimativas de risco e nas mais modernas ferramentas e técnicas de decisão. 
The Guide to Operational Research, do INFORMS (Institute for Operations Research and the Management Sciences) 
 A Pesquisa Operacional (PO) é uma ciência aplicada voltada para a resolução de 
problemas reais. Tendo como foco a tomada de decisões, aplica conceitos e métodos 
de outras áreas científicas para concepção, planejamento ou operação de sistemas 
para atingir seus objetivos.  
SOBRAPO (Sociedade Brasileira de Pesquisa Operacional) 
 Pesquisa Operacional é um método científico que provê executivos com uma base 
quantitativa para decisões concernentes às operações sob seu controle.” 
Morse & Kimball, 1950, p.1 
 
Desenvolvimento da PO 
 Segunda Guerra Mundial 
 Um grupo de cientistas foi convocado na INGLATERRA para estudar problemas 
de estratégia e de tática associados com a defesa do país.  
 O objetivo era decidir sobre a utilização eficiente de recursos militares 
limitados.  
 A convocação deste grupo marcou a primeira atividade formal de pesquisa 
operacional. 
Resultados Positivos 
 Os Estados Unidos se motivaram a iniciarem atividades semelhantes. A eles é devida a 
propagação principalmente à equipe de cientistas liderada por George Bernard 
Dantzig (1914‐2005), convocada durante a Guerra.  
 Ao esforço de pesquisa, concluído em 1947, deu‐se o nome de: Método Simplex, que 
tornou possível a solução de problemas de otimização de vários tipos, como 
transporte, produção, etc 
 
Após a 2ª Guerra Mundial 
 
 Atraiu o interesse de diversas outras áreas: 
 Negócios; 
 Tecnologia; 
 Defesa; 
 Entre outras. 
 Como a natureza dos problemas encontrados é bastante abrangente e 
complexa, exigindo portanto uma abordagem que permita reconhecer os 
múltiplos aspectos envolvidos.  
 
No Brasil 
 O  início da PO no Brasil se deu aproximadamente uma década após sua  implantação 
na Grã‐ Bretanha e nos Estados Unidos,  sendo que as aplicações à economia é que 
motivou os trabalhos pioneiros da PO. 
 Em 1958  teve  início o Curso de Engenharia de Produção  (em nível de graduação) do 
Instituto Tecnológico de Aeronáutica  (ITA). Foram criados os cursos de Programação 
Linear, Teoria dos Jogos, 
 Simulação,  Teoria  das  Filas  e  Estatística,  oferecidos  aos  alunos  deEngenharia  de 
Produção da USP e do ITA. 
 O  primeiro  grupo  formal  de  PO  estabelecido  no  Brasil  em  uma  empresa  foi  o  da 
Petrobrás, criado em 1965. 
 Em 1966 foi realizado no Rio o "Primeiro Seminário de PO no Brasil”, promovido pela 
Petrobrás.  Nesta  época  foi  fundada  a  SOBRAPO  ‐  Sociedade  Brasileira  de  Pesquisa 
Operacional, que congrega interessados no desenvolvimento e uso de técnicas de PO. 
 
Pesquisa Operacional então é... 
Método científico de tomada de decisão  
 Uma decisão pode ser classificada em estruturada se envolve uma série de fatores que 
possam ser quantificados, e logo, equacionados; 
 Pesquisa Operacional é uma ferramenta de apoio à decisão estruturada; 
 
Definição do Problema 
 
 
 
Modelagem
 
Estru
 
 
utura de Mod
• Aqu
de
form
min
• A fuvalo
etc.
Fun
delos  
ui devem
decisão
ma da
nimizaçã
unção o
or do ob
.), em fu
nção
mos ide
o. Eles
maximiz
ão de cu
bjetivo 
bjetivo (
unção da
o Obj
ntificar
apare
zação d
ustos, pe
é a expr
lucro,cu
as variá
etivo
o objet
ecem g
de lucro
erdas et
ressão q
usto, rec
veis de 
o
ivo da t
eralmen
os ou re
tc.
que calc
ceita, pe
decisão
tomada
nte na
eceitas,
cula o 
erda 
o.
 
 
 
 
 
Vamos lá...mais decisões 
 
Considerem: 
  Um fazendeiro deseja determinar quantos acres de trigo e milho ele deve plantar esse 
ano. 
Um acre de trigo: ‐  Rende 25 sacas //  Requer 10 h trabalho/semana.  // a saca vale R$ 4,00 no 
mercado 
Um acre de milho:  Rende 10 sacas //  Requer 4 h trabalho/semana. //  A saca vale R$3,00 no 
mercado.  
O governo garante a compra de pelo menos 30 sacas de milho/ano.  
  O fazendeiro dispõe:  7 acres de terra //   Pode trabalhar 40 horas/semana. 
Limite de 7 acres  ‐  Limite de 40 horas por semana  
 
Vamos exercitar 
1. Faça o modelo do problema do fazendeiro: 
• Um fazendeiro deseja determinar quantos acres de trigo e milho ele deve plantar esse 
ano. 
• Um acre de trigo rende 25 sacas e requer 10 horas de trabalho/semana. A saca vale 
R$4,00 no mercado. 
• Um acre de milho rende 10 sacas e requer 4 horas de trabalho/semana. A saca vale 
R$3,00 no mercado. 
• O governo garante a compra de pelo menos 30 sacas de milho/ano. O fazendeiro 
dispõe de 7 acres de terra e pode trabalhar 40 horas/semana. 
• O Fazendeiro deseja maximizar seus ganhos.  
 
2. Certa empresa fabrica 2 produtos P1 e P2. O lucro por unidade de P1 é de 100 u.m. e o 
lucro unitário de P2 é de 150 u.m. A empresa necessita de 2 horas para fabricar uma 
unidade de P 1 e 3 horas para fabricar uma unidade de P2. O tempo mensal disponível 
para essas atividades é de 120 horas. As demandas esperadas para os dois produtos 
levaram a empresa a decidir que os montantes produzidos de P1 e P2 não devem 
ultrapassar 40 unidades de P1 e 30 unidades de P2 por mês. Construa o modelo do 
sistema de produção mensal com o objetivo de maximizar o lucro da empresa. 
3. Um vendedor de frutas pode transportar 800 caixas de frutas para a sua região de 
vendas. Ele necessita transportar 200 caixas de laranjas a 20 u. m. de lucro por caixa, 
pelo menos 100 caixas de pêssegos a 10 u. m. de lucro por caixa e no máximo 200 
caixas de tangerinas a 30 u.m. de lucro por caixa. De que forma deverá ele carregar o 
caminhão para obter o lucro máximo? Construa o modelo do problema. 
4. Uma rede de televisão local tem o seguinte problema: foi descoberto que o programa 
“A” com 20 minutos de música e 1 minuto de propaganda chama a atenção de 30.000 
telespectadores, enquanto o programa “B”, com 10 minutos de música e 1 minuto de 
propaganda chama a atenção de 10.000 telespectadores. No decorrer de uma semana, 
o patrocinador insiste no uso de no mínimo, 5 minutos para sua propaganda e que não 
há verba para mais de 80 minutos de música. Quantas vezes por semana cada 
programa deve ser levado ao ar para obter o número máximo de telespectadores? 
Construa o modelo do sistema 
5. Uma empresa fabrica 2 modelos de cintos de couro. O modelo M1, de melhor 
qualidade, requer o dobro do tempo de fabricação em relação ao modelo M2. Se 
todos os cintos fossem do modelo M2, a empresa poderia produzir 1.000 unidades por 
dia. A disponibilidade de couro permite fabricar 800 cintos de ambos os modelos por 
dia. Os cintos empregam fivelas diferentes, cuja disponibilidade diária é de 400 para 
M1 e 700 para M2. Os lucros unitários são de $ 4,00 para M1 e $ 3,00 para M2. Qual o 
programa ótimo de produção que maximiza o lucro total diário da empresa? Construa 
o modelo do sistema descrito. 
6. Uma empresa, após um processo de racionalização de produção, ficou com 
disponibilidade de 3 recursos produtivos, R1, R2 e R3. Um estudo sobre o uso desses 
recursos indicou a possibilidade de se fabricar 2 produtos P 1 e P2. Levantando os 
custos e consultando o departamento de vendas sobre o preço de colocação no 
mercado, verificou‐se que P1 daria um lucro de $ 120,00 por unidade e P2, $ 150,00 
por unidade. O departamento de produção forneceu a seguinte tabela de uso de 
recursos. 
 
7. Um fazendeiro está estudando a divisão de sua propriedade nas seguintes atividades 
produtivas: 
A (Arrendamento) — Destinar certa quantidade de alqueires para a plantação de cana‐
de‐açúcar, a uma usina local, que se encarrega da atividade e paga pelo aluguel da 
terra $300,00 por alqueire por ano. 
P (Pecuária) – Usar outra parte para a criação de gado de corte. A recuperação das 
pastagens requer adubação (100 kg/alq) e irrigação (100.000 l de água/alq) por ano. O 
lucro estimado nessa atividade é de $ 400,00/alqueire no ano. 
S (Plantio da Soja) – Usar uma terceira parte para o plantio da soja. Essa cultura requer 
200 Kg/alq de adubos e 200.000 l de água/alq para irrigação por ano. O lucro estimado 
nessa atividade é de $ 500,00/alqueire no ano. 
Disponibilidade de recursos por ano: 12.750.000 litros de água; 14.000 kg de adubo; 
100 alqueires de terra. 
Quantos alqueires deverá destinar a cada atividade para proporcionar o melhor 
retorno? Construa o modelo de decisão. 
 
8. Duas  fábricas produzem  3 diferentes  tipos de papel.   A  companhia que  controla  as 
fábricas  tem  um  contrato  para  produzir  pelo menos:  16  toneladas  de  papel  fino,  6 
toneladas de papel médio e 28 toneladas de papel grosso.  Existe uma demanda para 
cada tipo de espessura.  O custo de produção na primeira fábrica é de $ 1.000 e o da 
segunda fábrica é de $ 2.000 por dia.  A primeira fábrica produz 8 toneladas de papel 
fino, 1  tonelada de papel médio e 2  toneladas de papel grosso por dia, enquanto a 
segunda  fábrica  produz  2  toneladas  de  papel  fino,  1  tonelada  de  papel médio  e  7 
toneladas de papel grosso.   Quantos dias  cada  fábrica deverá operar para  suprir os 
pedidos mais economicamente? 
 
9. Suponhamos  que  8,  12  e  9  unidades  de  proteínas,  carboidratos  e  gorduras, 
respectivamente,  sejam  as  necessidades  semanais  mínimas  para  cada  pessoa.  O 
alimento  A  (macarronada)  contém  por  quilo  2,  6  e  1  unidade  de  proteínas, 
carboidratos e gorduras, e o alimento B (feijoada) contém por quilo 1, 1 e 3 unidades 
respectivamente. Se A custa 3 unidades monetárias  (u.m.) e B custa 2 u.m., quantos 
quilos de cada um deve‐se comprar por semana para ter a dieta de menor custo? 
10. O departamento de marketing de uma empresa estuda a  forma mais econômica de 
aumentar em 30% as vendas de seus dois produtos P1 e P2. As alternativas são: 
a) Investir em um programa  institucional com outras empresas do mesmo ramo. Esse 
programa  requer  um  investimento mínimo  de  $  3.000,00  e  deve  proporcionar  um 
aumento de 3% nas vendas de cada produto, para cada $ 1.000,00 investidos; 
b) Investir diretamente na divulgação dos produtos. Cada $ 1.000,00 investidos em P1 
retornam um aumento de 4% nas vendas, enquanto que para P2 o retorno é de 10%. 
A empresa dispõe de $ 10.000,00 para esse empreendimento. Quanto deverá destinar 
a cada atividade? 
Construa o modelo do sistema descrito. 
 
11. Uma liga especial constituída de ferro, carvão, silício e níquel pode ser obtida usando a 
mistura desses minerais puros além de 2 tipos de materiais recuperados: 
 
 
 
A liga deve ter a seguinte composição final: 
 
 
O custo dos materiais puros são (por Kg): ferro: $0,30; carvão: $0,20; silício: $0,28; 
níquel:$0,50.  
Qual deverá ser a composição da mistura em termos dos materiais disponíveis, com menor 
custo por Kg?  Construa o modelo de decisão. 
 
12. Uma  rede  de  depósitos  de  material  de  construção  tem  4  lojas  que  devem  ser 
abastecidas com 50 m3 (L1), 80 m3 (L2), 40 m3(L3), 100 m3(L4) de areia grossa. Essa 
areia pode ser encarregada em 3 portos P1, P2 e P3, cujas distâncias às lojas estão no 
quadro (em km): 
 
 
O caminhão pode transportar 10 m3 por viagem. Os portos tem areia para suprir 
qualquer demanda.Estabelecer um plano de transporte que minimize a distância total percorrida entre os 
portos e as lojas e supra as necessidades das lojas. 
Construa o modelo linear do problema. 
 
 
PROGRAMAÇÃO LINEAR ‐ MÉTODO GRÁFICO ‐  
 
Solução Gráfica de Problemas de PL  
 
 
A solução gráfica pode ser feita em 03 passos: 
a) Identificação e construção das retas de restrição; 
b) Identificação da região viável; 
c) Identificação do ponto ótimo;  
 
O Problema do Desenhista 
• Um desenhista faz quadros artesanais para vender numa feira que acontece todo dia, à 
noite; 
• Ele faz desenhos grandes e desenhos pequenos, e vende‐os por R$5,00 e R$2,00, 
respectivamente; 
• Só é possível vender 4 desenhos grandes, e 3 desenhos pequenos por noite; 
• O desenho grande é feito em uma hora (grosseiro) e o pequeno é feito em duas horas 
(detalhado). Além disso, o desenhista desenha 8 horas por dia antes de ir para a feira. 
 
Determine o Modelo! 
 
Gráfico 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Outro
Uma 
Na fa
Na fa
A em
Sabe‐
Soluç


x 14
o Exemplo –
empresa po
abricação do
A  empre
intensiva
abricação do
A empres
capital). 
presa dispõe
De 18 ho
De 12 ho
‐se que os lu
Produto 1
 
ção Gráfica –
 Para cada
 Dado um
combinaç
isolucros
x  21
– Resolver !!!
de fabricar d
o Produto 1  
sa  gasta nov
 em mão‐de
o Produto 2  
sa gasta uma
e para um pe
ras‐homem;
ras‐máquina
ucros líquidos
1 $4 e  Produ
– As Curvas d
a valor de Z t
 valor de Z é
ções de prod
. 
xZ 
! 
dois produto
ve horas‐ho
‐obra). 
a hora‐home
eríodo de pro
 e  
a.  
s dos produt
uto 2 $1. 
de Níveis (Iso
tem‐se uma 
é possível tra
dução dão o 
x2 4
os (1 e 2).  
mem  e  três
em e uma ho
odução: 
tos são: 
olucro) 
reta no plan
çar um lugar
mesmo lucro
Zx 1
s horas‐máq
ora‐máquina
o (x2 versus
r geométrico
o, essas curv
uina  (a  tecn
a (a tecnolog
x1). 
o (uma reta) 
vas são conh
 
nologia utiliz
gia é intensiv
onde as vári
ecidas como
 
 
ada  é 
va em 
ias 
o 
Soluç
 
Soluç
 
 
 
REVIS
o
o
o
o
ção Gráfica –
ção Gráfica –
SÃO ‐  Progr
o A Compa
o C
o Margem 
o C
o M
o As cadeir
o M
o A
o Cada unid
– As Curvas d
– Casos onde
amação Line
nhia MAXIM
Cadeiras e M
de Contribui
Cadeira = $ 8
Mesa     = $ 6
ras e mesas s
Montagem  
Acabamento 
dade dos pro
de Níveis (Iso
e não há solu
ear  ‐ Resolve
MÓVEIS fabric
esas 
ição Unitária
,00 
6,00 
são processa
 
odutos conso
olucro) 
ução  
er !!! 
ca 2 tipos de
a: 
adas em 2 de
ome as segu
e produtos: 
epartamento
intes horas n
 
os: 
na fabricaçãoo:  
 
 
 
 
Adaptação para outras formas de modelo  
1. Restrições  do  tipo  "="  exigem  que  seja  acrescida  uma  variável  artificial,  sem  sentido 
físico, para que a restrição possa compor no tableau original do Simplex. 
2. Restrições  do  tipo  ">"  exigem,  além  da  variável  artificial,  também  uma  variável  de 
excesso, para que a restrição possa compor no tableau original do Simplex.  
 
SOLUÇÃO POR SISTEMA DE EQUAÇÕES LINEARES (SEL) 
 
  
 
• Sistema  com  n  variáveis  e  m  equações  (n>m)  é  indeterminado,  apresentando 
infinitas soluções. 
• No caso em estudo: 
o n  = 4 
o m = 2 
• Estratégia de Solução: forma‐se sistema de equações com m variáveis válidas e (n‐m) 
variáveis de valor zero e resolve‐se o modelo C vezes, de forma iterativa. 
  
 

Proce
 
1
2
3
4
5
6
7
 O método
 U
(i
 C
 C
d
 A
in
 
edimentos d
1. Introduzi
2. Montar u
com os re
objetivo t
3. Estabelec
originais 
folga (VA
4. Como pró
primeira 
maior val
Se todas 
nessa linh
Se algum
valor da f
5. Para esco
procedim
a) Dividir 
da coluna
nessa col
b) O men
anulada, 
6. Usando o
básica nu
variável q
7. Retornar 
A soluçã
de um p
resolv
O proce
corr
extrem
o simplex é u
Um algoritmo
iterado) segu
Cada percurs
Conseqüente
de outros fác
Além das  ite
nício e um cr
do Método S
r as variávei
um quadro p
espectivos si
transformad
cer uma solu
(VARIÁVEIS 
ARIÁVEIS BÁS
óxima variáv
linha, a maio
lor negativo)
as variáveis 
ha, a solução
a dessas var
função‐objet
olher a variáv
mento: 
os elemento
a da variável
una, o proce
nor coeficient
tornando‐se
operações co
um vetor ide
que está sen
ao PASSO 4 
ão mostrou q
problema de
ver Sistemas
Linear
edimento ape
retamente, po
amente lento
maiore
MÉ
um algoritmo
o é um proc
uidamente a
o do proced
emente, um 
ceis. 
rações, os a
ritério para d
implex ‐ Pas
s de folga, u
ara os cálcul
nais e, na pr
da. 
ução básica in
NÃO BASICA
SICAS).  
vel a entrar n
or contribuiç
).  
que estão fo
o atual é ótim
iáveis tiver v
tivo. 
vel que deve
os da última 
 que vai entr
esso deve pa
te indica a e
e variável não
om as linhas 
ntidade, ond
do anulada.
para iniciar 
que a resolu
e PL consiste 
s de Equaçõe
res
esar de funcio
ode se tornar 
o para problem
es
ÉTODO SIMP
o. 
cesso onde 
até que o res
imento siste
algoritmo su
lgoritmos  ta
determinar q
ssos 
ma para cad
los, colocand
rimeira linha
nicial, usualm
AS)  e achand
na base, esco
ção para o au
ora da base t
ma. 
valor nulo, te
e deixar a bas
coluna pelo
rar na base. 
arar, já que a
quação cuja 
o‐básica. 
da matriz, tr
de o element
nova iteraçã
ção 
em 
es 
nar 
mas 
 
PLEX 
um procedim
ultado desej
emático é cha
ubstitui um p
ambém  inclu
quando para
a desigualda
do os coeficie
, incluir os co
mente atribu
do valores po
olher a variáv
umento da fu
iverem coefi
emos outra s
se, deve‐se r
s correspond
Se não houv
 solução é ili
respectiva v
ransformar a
to 1 aparece
ão. 
mento  sistem
jado seja obt
amado de ite
problema dif
uem um proc
r.  
ade 
entes de tod
oeficientes d
uindo zero às
ositivos para 
vel não‐básic
unção objeti
icientes nulo
solução ótim
realizar o seg
dentes elem
ver elemento
imitada. 
variável básic
a coluna da n
 na linha cor
mático é  rep
tido. 
eração. 
fícil por uma
cedimento d
das as variáve
da função‐
s variáveis 
as variáveis 
ca que forne
vo (ou seja, 
os ou positivo
a, com o me
guinte 
entos positiv
o nenhum po
ca deverá se
nova variável
rrespondente
petido 
a série 
de dar 
eis 
de 
ce, na 
tem o 
os 
esmo 
vos 
ositivo 
r 
l 
e à 
 
Passo
 
 
 
 
 
Trans
 
 
 
Passo
     O 

  Prod
(maio
          
 
 

Se fo
máxim
 
 
o1: Introduz
            Ma
            Suj
4x1 + 2x2 
2x1 + 4x2 +
               x
sformar a fun
de          Z
para      Z 
o 3, 4 e 5:  
problema é 
 D
n
 D
b
   Qual de
duzir primeir
or valor nega
                 x1
 Qual vari
ormos produ
ma possível?
  1ª restri
ir as variáve
ax Z = 8x1 + 6
jeito a: 
+ 1x3                   =
+         + 1x4 =
x1, x2, x3 e x4  
nção‐objetiv
Z = 8x1 + 6x2 
‐ 8x1 ‐ 6x2 = 
descobrir: 
Das 2 variáve
na base?  
Das 2 variáve
base?  
everá entrar 
ro o produto
ativo) 
= ‐8 (coluna 
iável deverá
zir apenas o
?  
ção: 4x1 + 0x
eis de folga 
6x2 + 0x3 + 0x
= 60 
= 48 
   0  
vo: 
0  
eis não‐básic
eis básicas (p
na base?  
o que mais c
pivô)  e   x2 
á sair da base
o produto qu
x2 = 60   M
x4 
cas (nulas) n
positivas) na
contribui par
= ‐6 
e? 
ue mais cont
Max x1 = 15 
a primeira s
 primeira so
ra o  lucro, c
 
tribui para o 
solução, qua
olução, qual d
como  indicad
lucro (x1), q
l deverá se e
deverá ser s
do na última
qual a quant
 
entrar 
sair da 
a  linha 
tidade 
 
Ou se
colun
Assim
 
O  coe
pivô p
Nova
 
Para 
Linha
Usan
Nova
  2
eja: Dividir o
na da variáve
m o menor va
eficiente da 
pelo número
 linha pivô = 
eliminar a no
as (exceto a l
do se a segu
a linha = anti
ª restrição: 2
os elementos
el que vai ent
alor é o mais
nova variáv
o pivô, de mo
antiga linha 
ova variável 
inha pivô, sã
uinte fórmula
iga linha – (c
2x1 + 0x2 = 48
s da última c
trar na base.
s restritivo e
vel básica de
odo que: 
pivô / núme
básica das o
ão modificad
a: 
coeficiente d
8   Max x1
coluna pelos
. Dá‐se o nom
everá  ser m
ero pivô  
outras equaç
das para 
da coluna piv
= 24  
s correspond
me de linha 
udado para 
ões, todas as
vô)x nova lin
denteseleme
pivô 
+1, dividind
s 
nha pivô 
entos positiv
do‐se  toda a
vos da 
 
 
  linha 
 
  
 
 
  
O  coeficiente da nova variável básica deverá  ser mudado para +1, dividindo‐se  toda a  linha 
pivô pelo número pivô, de modo que: 
Nova linha pivô = antiga linha pivô / número pivô  
 
 
 
Para 
Linha
Usan
Nova
 
 
eliminar a no
as (exceto a l
do se a segu
a linha = anti
ova variável 
inha pivô, sã
uinte fórmula
iga linha – (c
básica das o
ão modificad
a: 
coeficiente d
outras equaç
das para 
da coluna piv
ões, todas as
vô)x nova lin
s 
nha pivô 
 
 
 
Outro
Maxi
 
 
(1
(2
(3
x1;x2 ≥
 
 
 
 
o Exemplo d
mizar Z = 3x1
   
   
1)   x1              ≤
2)        2x2    
3) 3x1+2x2  ≤
≥ 0 
do Método S
1+5x2  
 
sujeit
≤   4 
   ≤ 12 
≤ 18 
implex 
to a