Apostila Pesquisa Operacional I

Prévia do material em texto

Ministério da Educação 
Universidade Tecnológica Federal do Paraná 
Campus Medianeira 
Gerência de Ensino e Pesquisa 
Coordenações de Cursos 
 
 
CURSO: ENGENHARIA DE PRODUÇÃO. 
 
DISCIPLINA: PESQUISA OPRACIONAL 1. 
 
PROFESSOR: LEVI LOPES TEIXEIRA. 
 
 
 
ROTEIRO DE ESTUDOS. 
 
 
 
 
 
 
 
 
 
 
Medianeira - Agosto/2011. 
1 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
 
 
SUMÁRIO 
 
 
 
 
INTRODUÇÃO............................................................................................................................................................ 2 
PROGRAMAÇÃO LINEAR...................................................................................................................................... 2 
CONSTRUÇÃO DE MODELOS DE PROGRAMAÇÃO LINEAR.................................................................. 3 
SOLUÇÀO GRÁFICA DE UM PPL......................................................................................................................... 8 
SOLUÇÀO BÁSICA DE UM SISTEMA DE EQUAÇÃOES LINEARES....................................................... 11 
MÉTODO SIMPLEX.................................................................................................................................................. 12 
MÉTODO DO M GRANDE...................................................................................................................................... 14 
MÉTODO DAS DUAS FASES................................................................................................................................. 14 
VARIÁVEL LIVRE E TIPOS DE SOLUÇÕES DE UM PPL........................................................................... 15 
RESOLUÇÃO DE UM PPL USANDO O SOLVER DO EXCEL..................................................................... 19 
RESOLUÇÃO DE UM PPL USANDO O APLICATIVO LINDO................................................................... 21 
RESOLUÇÃO DE UM PPL USANDO O APLICATIVO LINGO................................................................... 22 
ANÁLISE DE SENSIBILIDADE............................................................................................................................. 24 
ANÁLISE DE SENSIBILIDADE USANDO O SOLVER, LINDO E LINGO................................................ 28 
DUALIDADE................................................................................................................................................................ 34 
ANÁLISE ECONÔMICA........................................................................................................................................... 37 
ALGORITMO DUAL SIMPLEX............................................................................................................................. 40 
ANÁLISE DE PÓS-OTIMIZAÇÃO........................................................................................................................ 41 
MÉTODO SIMPLEX REVISADO.......................................................................................................................... 47 
PROBLEMAS DE TRANSPORTES....................................................................................................................... 49 
PROGRAMANDO NO LINGO................................................................................................................................. 56 
PROBLEMAS DE TRANSBORDO........................................................................................................................ 59 
PROBLEMAS DE DESIGNAÇÃO.......................................................................................................................... 63 
OTIMIZAÇÃO EM REDES....................................................................................................................................... 67 
MODELO DETERMINÍSTICO DE ESTOQUE................................................................................................. 78 
 
 
 
 
 
 
 
 
2 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
INTRODUÇÃO 
 A pesquisa operacional (P.O.) tem as suas origens nas operações militares no período da 
segunda guerra. Os recursos escassos levaram os comandos militares aliados a convocarem 
cientistas para desenvolverem procedimentos que otimizassem a alocação de recursos. 
 Em 1947, George Dantzig desenvolveu o método simplex, um algoritmo usado na 
resolução de problemas de programação linear (PPL). Um modelo de PPL é formado 
basicamente por uma função objetivo (que deverá ser maximizada ou minimizada) e restrições 
representadas por expressões lineares. 
 São várias as áreas onde se aplicam a P.O.: 1) Problemas de misturas (adubos, ração, 
tintas, ligas metálicas, combustíveis, minérios, etc); 2) Problemas de corte (barras, bobinas, 
chapas, etc.); 3)Problemas de distribuição e localização (roteamento, localização de postos de 
saúde, escolas, etc); 4) Horários de trabalho (motoristas de ônibus, tripulação de avião, 
atendentes de telefone, etc.); 5) Planejamento de produção e estocagem (refinaria, indústria de 
móveis, etc.); 6) Finanças (crédito, bolsa de valores, etc.). 
 
PROGRAMAÇÃO LINEAR 
 
 De maneira geral um modelo de P.O. pode ser representado da seguinte forma: 
 Maximizar ou minimizar a função objetivo. 
 Sujeito a 
 Restrições 
 
 
CONCEITOS IMPORTANTES 
 
a) Variáveis de decisão: São variáveis usadas no modelo que podem ser controladas pelo 
tomador de decisão. A solução do problema é encontrada testando-se diversos valores 
das variáveis de decisão. Exemplo: O número de caminhões que a engarrafadora deve 
despachar num determinado dia. 
b) Parâmetros: São variáveis usadas no modelo que não podem ser controladas pelo 
tomador de decisão. A solução do problema é encontrada admitindo como fixos os 
valores dos parâmetros. Exemplo: A capacidade de cada caminhão que vai transportar 
refrigerante. Os caminhões têm uma capacidade especificada pelo fabricante e uma 
carga total transportada que é limitada pela legislação rodoviária. 
c) Função-objetivo: É uma função matemática que representa o principal objetivo do 
tomador de decisão. Ela é de dois tipos (minimização e maximização). Exemplo: 
Minimizar os custos de transportes relativos à distribuição de refrigerantes. 
d) Restrições: São regras que dizem que podemos (ou não) fazer e/ou quais são as 
limitações dos recursos ou das atividades que estão associadas ao modelo. 
PROPRIEDADES DA PROGRAMAÇÃO LINEAR 
 Em modelos de PL, a função objetivo e as restrições são expressões lineares. Linearidade 
implica que a PL deve satisfazer 3 propriedades básicas: 
1- Proporcionalidade: Essa propriedade requer que a contribuição de cada variável de 
decisão, tanto na função objetivo quanto nas restrições, seja diretamente proporcional 
ao valor da variável. Por exemplo, na função objetivo maximizar receita = 4x1 + 3x2, as 
constantes de proporcionalidade são 4 e 3 para os produtos 1 e 2, respectivamente. 
2- Aditividade: Essa propriedade requer que a contribuição total de todas as variáveis da 
função objetivo e das restrições seja a soma direta das contribuições individuais de cada 
variável. Em outras palavras a operação entre as variáveis deve ser adição ou subtração. 
3 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
3- Certeza: Todos os coeficientes da função objetivo e das restrições do modelo de PL são 
determinísticos, o que significa que são constantes conhecidas. 
CONSTRUÇÃO DE MODELOS DE PROGRAMAÇÃO LINEAR 
EXEMPLOS: 
1- Uma pequena indústria produz artigos A1 e A2 qua são vendidos a $ 200 / un. E $ 300 / 
un. , respectivamente. Na sua produção são utilizados 3 tipos de matérias-primas, P1, P2 
e P3, que são gastas da seguinte forma:2 unidades de P1 para fabricar 1 unidade de A1, 
4 unidades de P2 para fabricar 1 unidade de A1, 
1 unidade de P1 para fabricar 1 unidade de A2, 
1 unidade de P3 para fabricar 1 unidade de A2. 
 Por razões econômicas, as matérias-primas P1, P2 e P3 estão disponíveis no 
máximo em 20, 32 e 10 unidades, respectivamente. 
 O dono da empresa deseja saber as quantidades dos produtos A1 e A2 que 
devem ser produzidas para que a receita seja a maior possível. Construa o modelo do 
problema como um PPL. 
2- Um jovem pretende prestar um concurso público cujo exame envolve duas disciplinas, 
D1 e D2. Ele sabe que, para cada hora de estudo, pode obter 2 pontos na nota da 
disciplina D1 e 3 pontos na de D2 e que o rendimento é proporcional ao seu esforço. Ele 
dispõe de no máximo 50 horas para os estudos até o dia do exame. Para ser aprovado 
deverá obter na disciplina D1 no mínimo 20 pontos, na D2, no mínimo 30, e o total de 
pontos deverá ser pelo menos 70. Como, além da aprovação, ele gostaria de alcançar a 
melhor classificação possível, qual a melhor forma de distribuir as horas disponíveis 
para o seu estudo? Formular o Problema como um PPL. 
3- Uma pessoa em dieta necessita ingerir pelo menos 20 unidades de vitamina A, 10 
unidades de vitamina B e 2 unidades de vitamina C. Ela deve conseguir essas vitaminas a 
partir de dois tipos diferentes de alimentos: A1 e A2. A quantidade de vitaminas que 
esses produtos contêm por unidade e o preço unitário de cada um deles está expresso 
na seguinte tabela: 
 Vitamina A Vitamina B Vitamina C Preço unitário 
Alimento A1 4 1 1 30 u.m. 
Alimento A2 1 2 - 20 u.m. 
Qual a programação de compras dos alimentos A1 e A2 que essa pessoa deve fazer para 
cumprir sua dieta, ao menor custo possível? Construa o modelo linear para este 
problema. 
EXERCÍCIOS 
1- 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.n. A empresa necessita de 2 horas para fabricar uma 
unidade de P1 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. 
2- Um vendedor de frutas pode transportar 800 caixas de frutas para 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 
4 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
tangerina 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. 
3- 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 P1 e P2. Levantando os custos 
e consultado 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 dos recursos. 
Produtos Recurso R1/un. Recurso R2/un. Recurso R3/un. 
P1 2 3 5 
P2 4 2 3 
Disponibilidade de 
recursos por mês 
100 90 120 
Que produção mensal de P1 e P2 traz o maior lucro a empresa? Construa o modelo do 
sistema. 
4- Um fazendeiro está estudando a divisão de sua propriedade nas seguintes atividades: 
(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 criação de gado de 
corte. A recuperação das pastagens requer adubação (100kg/alq.) e irrigação (100.000 l 
de água/alq.) por ano. O lucro estimado nessa atividade é de $ 400,00 por alqueire por 
ano. (S) (plantio de soja)- Usar uma terceira parte para o plantio de soja. Essa cultura 
requer 200 kg por alqueire 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 l 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. 
5- 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: 
Material recuperado 1 – MR1- composição: 
Ferro – 60% - custo por kg = $0,20 
Carvão – 20% 
Silício – 20% 
Material recuperado 2 – MR2 – composição: 
Ferro – 70% - custo por kg = 0,25 
Carvão – 20% 
Silício – 5% 
Níquel- 5% 
A liga deve ter a seguinte composição final: 
Matéria prima % Mínima % Máxima 
Ferro 60 65 
Carvão 15 20 
Silício 15 20 
Níquel 5 8 
5 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
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? 
6- Uma certa agroindústria do ramo alimentício tirou de produção uma certa linha de 
produto não lucrativo. Isso criou um considerável excedente na capacidade de produção. 
A gerência está considerando dedicar essa capacidade excedente a um ou mais produtos, 
identificados como produtos 1, 2 e 3. A capacidade disponível das máquinas que poderia 
limitar a produção está resumida na tabela a seguir: 
 Tipo de máquina Tempo disponível (horas de máquina) 
 A 500 
 B 350 
 C 150 
 
 O número de horas de máquina requerido por unidade dos respectivos produtos, 
conforme representado a seguir: 
Tipo de máquina Produto 1 Produto 2 Produto 3 
 A 9 3 5 
 B 5 4 0 
 C 3 0 2 
 
 O lucro unitário é de $ 30, $ 12 e $ 15, respectivamente, para os produtos 1,2 e 3. 
Construa um modelo matemático como PPL para determinar a quantidade de cada 
produto que a empresa deve produzir para maximizar o lucro. 
7- Uma certa corporação tem 3 fábricas filiais com capacidade de produção excedente. As 3 
unidades têm capacidade para fabricar um certo produto, tendo a gerência decidido 
utilizar parte dessa capacidade de produção excedente para fazê-lo. Ele pode ser feito 
em 3 tamanhos – grande, médio e pequeno – os quais geram um lucro unitário líquido 
de $ 140, $ 120 e $ 100, respectivamente. As fábricas 1,2 e 3 têm capacidade excedente 
de mão-de-obra e de equipamento para produzirem 750, 900 e 450 unidades do 
produto por dia, respectivamente, independentemente do tamanho ou combinação de 
tamanhos envolvidos. Entretanto, a quantidade de espaço disponível para estoque em 
processo também impõe um limite às taxas de produção. As fábricas 1,2 e 3 têm 1.170, 
1.080 e 450 metros quadrados de espaço disponível para estoque de produtos em 
processo, em dia de produção, sendo que cada unidade dos tamanhos grande, médio e 
pequeno, produzida por dia, requer, 1,8, 1,35 e 1,08 metros quadrados, 
respectivamente. As previsões indicam que podem servendidas, por dia, 900, 1.200, e 
750 unidades dos tamanhos grande, médio e pequeno, respectivamente. Para manter 
uma carga de trabalho uniforme entre as fábricas,e para reter algum tipo de 
flexibilidade, a gerência decidiu que a produção adicional designada a cada fábrica deve 
utilizar a mesma porcentagem da capacidade excedente de mão-de-obra e de 
equipamento. A gerência deseja saber a quantidade de produto, por tamanho, que 
6 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
deveria ser produzida em cada uma das fábricas, para maximizar o lucro. Monte o 
modelo linear. 
8- Uma determinada empresa quer utilizar do melhor modo possível os recursos de 
madeira de uma de suas regiões florestais. Dentro dessa região, há uma serraria e uma 
fábrica de compensados, o que possibilita que as toras possam ser convertidas em 
madeira beneficiada ou compensada. Produzir uma mistura comercializável de 1 metro 
cúbico de produtos beneficiados requer 1 metro cúbico de pinho e 4 metros cúbicos de 
canela. Produzir 100 metros quadrados de madeira compensada requer 2 metros 
cúbicos de pinho e 4 metros cúbicos de canela. A região em questão dispõe de 32 metros 
cúbicos de pinho e 72 metros cúbicos de canela. Compromissos de vendas exigem que 
sejam produzidos, durante o período de planejamento, pelo menos 5 metros cúbicos de 
madeira beneficiada e 1.200 metros quadrados de madeira compensada. As 
contribuições ao lucro são de $ 45 por 1 metro cúbico de produtos beneficiados e $ 60 
por 100 metros quadrados de madeira compensada. Determine as quantidades (em 
metros cúbicos) de madeira beneficiada e de madeira compensada (em 100 metros 
quadrados) a serem produzidos. Monte o modelo linear. 
9- Uma companhia de aviação agrícola, que opera a partir de um determinado terminal, 
tem 8 aviões do tipo 1, 15 aviões do tipo 2 e 11 aviões do tipo 3, disponíveis para vôos. 
As capacidades de pesticidas para pulverização, em toneladas, são 4,5 para o tipo 1, 7 
para o tipo 2 e 5 para o tipo 3. 
 A companhia deve expedir aviões para as propriedades A e B. As necessidades de 
tonelagem são 20 na propriedade A e 28 na propriedade B. Sabe-se também que o 
excesso de pulverização em uma propriedade deve ser evitado; e que o avião pode voar 
somente uma vez durante o dia. 
 O custo de enviar do terminal a cada propriedade, em $, é dado pela seguinte 
tabela: 
Propriedade Avião – tipo 1 Avião – tipo 2 Avião – tipo 3 
 A 23 15 1,4 
 B 58 20 3,8 
 
 Denotando por x1, x2 e x3 os números de aviões de cada tipo enviado à 
propriedade A, e do mesmo modo, y1, y2 e y3 os aviões enviados à propriedade B. 
Formule o modelo de programação linear pertinente ao problema. 
 
RESPOSTAS 
1- x1 = quantidade a produzir de P1; x2 = quantidades a produzir de P2. 
Max Lucro = 100x1 + 150x2 
s.a. 
 2x1 + 3x2 <=120 
 x1<=40 
 x2<=30 
 x1, x2 >=0 
7 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
2- x1 = quantidade de caixas de pêssegos; x2 = quantidades de caixas de tangerinas. 
Max Lucro = 10x1 + 30x2 +4.000 
s.a. 
 x1 + x2 <=600 
 x1 >= 100 
 x2 <= 200 
 x1, x2 >=0 
3- x1 = quantidade a produzir de P1; quantidade a produzir de P2. 
Max Lucro = 120 x1 + 150 x2 
s.a 
 2x1 + 4x2 <=100 
 3x1 + 2x2 <=90 
 5x1 + 3x2 <=120 
 x1, x2 >=0 
4- x1 = alqueires para arrendamento; x2 = alqueires para pecuária; x3 = alqueires para 
soja. 
Max Lucro = 300x1 + 400x2 + 500x3 
s.a. 
 x1 + x2 + x3 <= 100 
 100x2 + 200x3 <= 14.000 
 100.000x2 + 200.000x3 <= 12.750.000 
 x1, x2, x3 >=0 
5- x1 = quantidade de MR1 na mistura; x2 = quantidade de MR2 na mistura; x3 = 
quantidade de ferro puro na mistura; x4 = quantidade de carvão na mistura; x5 = 
quantidade de silício na mistura; x6 = quantidade de níquel na mistura. 
Min Custo = 0,2x1 + 0,25x2 + 0,3x3 + 0,2 x4 + 0,28x5 + 0,5x6 
s.a. 
 0,6x1 + 0,7x2 + x3 >=0,6 
 O,6x1 + 0,7x2 + x3 <=0,65 
 0,2x1 + 0,2x2 + x4 <= 0,2 
 0,2x1 + 0,2x2 + x4 >=0,15 
 0,2x1 + 0,05x2 + x5 <=0,2 
 0,2x1 + 0,05x2 + x5 >=0,05 
 0,05x2 + x6 >= 0,05 
 0,05X2 + x6 <=0,08 
 x1 + x2 + x3 + x4 + x5 + x6 =1 
 x1,x2,x3,x4,x5,x6 >=0 
6- x1 = quantidade a ser produzida do produto 1; x2 = quantidade a ser produzida do 
produto 2; x3 = quantidade a ser produzida do produto 3. 
Max z = 30x1 + 12x2 + 15x3 
s.a. 
 9x1 + 3x2 + 5x3 <= 500 
 5x1 + 4x2 <= 350 
 3x1 + 2x3 <=150 
 x1, x2, x3 >=0 
8 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
7- x11, x21, x31 : produção na fábrica 1 dos 3 tamanhos (grande(1), médio (2) e pequeno 
(3); x12, x22, x32 : prod. Na fábr. 2 dos 3 tamanhos (grande(1), médio (2) e pequeno 
(3); o mesmo para x13, x23 e x33. 
Max z = 140 x11 + 140 x12 + 140x13 + 120x21 + 120x22 + 120x23 + 100x31 + 
100x32 + 100x33 
s.a. 
 x11 + x21 + x31 <=750 
 x12 + x22 + x32 <=900 
 x13 + x23 + x33 <=450 
 1,8x11 + 1,35x21 + 1,08x31 <=1170 
 1,8x12 + 1,35x22 + 1,08x32 <=1080 
 1,8x13 +1,35x23 + 1,08x33 <=450 
 x11 + x12 + x13 <= 900 
 x21 + x22 + x23 <=1200 
 x31 + x32 + x33 <=750 
 900(x11 + x21 + x31) – 750(x12 + x22 + x32) = 0 
 450(x12 + x22 + x32) – 900(x13 + x23 + x33) = 0 
 xij >=0, i=1,2,3 e j = 1,2,3 
8- x1 = madeira beneficiada; x2 = madeira compensada. 
Max z = 45x1 + 60x2 
s.a. 
 x1 + 2x2 <= 32 
 4x1 + 4x2 <= 72 
 x1 >= 5 
 x2 >=12 
 x1, x2 >=0 
9- x1 = número de aviões do tipo 1 usado na propriedade A; x2 = número de aviões do tipo 
2 usado na propriedade A; x3 = número de aviões do tipo 3 usado na propriedade A; y1 
= número de aviões do tipo 1 usado na propriedade B; y2 = número de aviões do tipo 2 
usado na propriedade B; y3 = número de aviões do tipo 3 usado na propriedade B. 
Min z = 23x1 + 15x2 + 1,4x3 + 58y1 + 20y2 + 3,8y3 
s.a. 
 x1 + y1 <=8 
 x2 + y2 <= 15 
 x3 + y3 <= 11 
 4,5x1 + 7x2 + 5x3 <= 20 
 4,5x1 + 7y2 + 5y3 <=28 
 x1, x2, x3, y1, y2, y3 <=0 
 
SOLUÇÃO GRÁFICA DE UM PPL 
 Problemas de programação linear que envolvam 2 variáveis de decisão podem ser 
facilmente resolvidos a partir do método gráfico. 
Procedimento: Representar graficamente as restrições. A intersecção dos gráficos (semi-planos) 
forma a região de soluções viáveis. A solução ótima deve ser encontrada entre os vértices dessa 
região. 
 
9 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
 
EXEMPLOS: 
Resolver pelo método gráfico os seguintes problemas de programação linear. 
 
1- Max z = 200x1 + 300x2 
s.a. 
 2x1 + x2 <=20 
 4x1 <= 32 
 x2 <= 10 
 x1>=0, x2>=0 
2- Max z = 2x1 + 3x2 
s.a. 
 x1 + x2 <= 50 
 2x1 + 3x2 >= 70 
 2x1 >= 20 
 3x2 >= 30 
 x1>=0, x2>=0 
3- Min z = 30x1 + 20x2 
s.a. 
 4x1 + x2 >= 20 
 x1 + 2x2 >= 10 
 x1 >= 2 
 x1>=0, x2 >= 0 
4- Max z = x1 + 2x2 
s.a. 
 4x1 + x2 >= 20 
 x1 + 2x2 >= 10 
 x1 >=2 
 x1>=0, x2>=0 
5- Min z = x1 + x2 
s.a. 
 -2x1 + x2 >=2 
 x1 – 2x2 >=2 
 x1>=0, x2>= 0 
6- Max z = x1 + x2 
s.a. 
 -2x1 + x2 <= 2 
 x1 – 2x2 <= 2 
 x1 + x2 <= 4 
 x1>=0, x2>=0 
 
 
EXERCÍCIOS 
Resolver graficamente os seguintes problemas de programação linear. 
4- Maximizar Lucro = 2x1 + 3x2 
s.a. 
 -x1 + 2x2 <= 4 
 x1+ 2x2 <=6 
x1 + 3x2 <=9 
10 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
x1, x2 >=0 
5- Maximizar Receita = 0,3x1 + 0,5x2 
s.a. 
 2x1 + x2 <=2 
 x1 + 3x2 <=3 
 x1, x2 >=0 
6- Maximizar Lucro = 2x1 + 3x2 
s.a. 
 x1 + 3x2 <=9 
 -x1 + 2x2 <=4 
 x1 + x2 <= 6x1, x2 >=0 
7- Minimizar Custo = 10x1 + 12x2 
s.a. 
 x1 + x2 <=20 
 x1 + x2 >=10 
 5x1 + 6x2 >=54 
 x1, x2 >=0 
8- Minimizar z = 7x1 + 9x2 
s.a. 
 -x1 + x2<=2 
 x1<=5 
 x2<=6 
 3x1 + 5x2 >=15 
 5x1 + 4x2 >=20 
 x1, x2 >=0 
9- Uma fábrica tem 3 tipos de máquinas, M1, M2 e M3, a serem utilizadas na fabricação dos 
produtos P1 e P2. O quadro abaixo descreve como a fábrica opera, diariamente: 
Máquinas\Produtos P1 P2 Disponibilidade/dia 
M1 3 2 20 h 
M2 4 0 12 h 
M3 2 5 18 h 
Formule o problema como um problema de programação linear para planejar a 
produção diária a fim de que o lucro seja o máximo possível, sabendo que o produto P1 
dá lucro de 200 u.m. e P2, 50 unidades. Resolver o problema pelo método gráfico. 
10- Uma companhia fabrica um produto a partir de dois ingredientes, A e B. Cada quilo de A 
contém 5 unidades do produto P1, 4 unidades do produto P2, 2 unidades doproduto P3 
e custa 100 u.m. Cada quilo de B contém 3 unidades do produto P1, 5 unidades do 
produto P2, 10 unidades do produto P3 e custa 150 u.m. A mistura deve conter pelo 
menos 20 unidades de P1, 18 unidades de P2 e 30 unidades de P3. Formule este 
problema como um problema de programação linear para que o custo do produto seja o 
menor possível. Resolver o problema pelo método gráfico. 
11- Um vendedor de frutas pode transportar 800 caixas de frutas para 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 
tangerina a 30 u.m. de lucro por caixa. De que forma deverá ele carregar o caminhão 
11 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
para obter o lucro máximo? Construa o modelo do problema. Resolva o problema pelo 
método gráfico. 
12- Uma pequena indústria produz artigos A1 e A2 qua são vendidos a $ 200 / un. E $ 300 / 
un. , respectivamente. Na sua produção são utilizados 3 tipos de matérias-primas, P1, P2 
e P3, que são gastas da seguinte forma: 
2 unidades de P1 para fabricar 1 unidade de A1, 
4 unidades de P2 para fabricar 1 unidade de A1, 
1 unidade de P1 para fabricar 1 unidade de A2, 
1 unidade de P3 para fabricar 1 unidade de A2. 
 Por razões econômicas, as matérias-primas P1, P2 e P3 estão disponíveis no 
máximo em 20, 32 e 10 unidades, respectivamente. 
 O dono da empresa deseja saber as quantidades dos produtos A1 e A2 que 
devem ser produzidas para que a receita seja a maior possível. 
13- O Governo Federal colocou 20 há de terras desmatadas à disposição de produtores 
locais. Estima-se que tal área seja utilizada para o plantio de soja e algodão. Calcula-se 
que há 1200 homens-horas disponíveis durante o período de semeadura; e que são 
necessários 20 homens-horas por hectare de soja e 120 homens-horas por hectare de 
algodão. Oferece-se ainda uma linha máxima de crédito de $ 6000,00, dividida da 
seguinte forma: $ 600,00 por hectere de soja e $ 200,00 por hectare de algodão. Como 
organizar essa área de plantio para maximizar o lucro se é sabido que as margens de 
lucro esperadas são $ 50 por hectare de soja e $ 25 por hectare de algodão? 
 
SOLUÇÃO BÁSICA DE UM SISTEMA DE EQUAÇÒES LINEARES 
EXEMPLO: Seja o sistema de equações lineares: 
 
𝑥1 + 3𝑥2 + 43 − 𝑥4 = 10
2𝑥1 + 𝑥2 − 𝑥3 + 2𝑥4 = 5
 ou 
1
2
 𝑥1 + 
3
1
 𝑥2 + 
 4
−1
 𝑥3 + 
−1
 2
 𝑥4 = 
10
5
 . A base é formada 
por dois vetores linearmente independentes. Fazendo x3 = x4 = 0, obtém-se: 
1
2
 𝑥1 + 
3
1
 𝑥2 =
 
10
5
 . Assim, a solução dita básica é x1 = 1, x2 = 3, x3 = 0 e x4 = 0. A C4,2 =6 fornece o total de 
soluções básicas que podem ser encontradas. 
PROBLEMA FUNDAMENTAL DE PL 
EXEMPLO: 
 Max z = 2x1 + 3x2 
 s.a. 
 x1 + 5x2 <=20 
 2x1 + x2 <= 10 
 x1>=0 e x2 >= 0 
a) Construir a região de soluções viáveis. 
12 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
b) Transformar o sistema de inequações, com a introdução de variáveis de folga, num 
sistema de equações com variáveis não negativas. 
c) Mostrar que as soluções básicas do sistema obtido são vértices da região de soluções 
viáveis. 
MÉTODO SIMPLEX 
(Para modelos de maximização e restrições do tipo <=) 
 
 𝑀𝑎𝑥 𝑧 = 𝑐1𝑥1 + 𝑐2𝑥2 + ⋯+ 𝑐𝑛𝑥𝑛 (F.O.) 
𝑠. 𝑎. 𝑎11𝑥1 + 𝑎12𝑥2 + ⋯+ 𝑎1𝑛𝑥𝑛 <= 𝑏1 
 𝑎21𝑥1 + 𝑎22𝑥2 + ⋯+ 𝑎2𝑛𝑥𝑛 <= 𝑏2 
………………… 
 𝑎𝑚1𝑥1 + 𝑎𝑚2𝑥2 + ⋯+ 𝑎𝑚𝑛𝑥𝑛 <= 𝑏𝑚 
𝑥1, 𝑥2,… , 𝑥𝑛 ≥ 0 
 
Introduzindo as variáveis de folga 𝑠1, 𝑠2,… , 𝑠𝑚 , o problema acima é transformado em: 
 
𝐹.𝑂. : 𝑧 − 𝑐1𝑥1 − 𝑐2𝑥2 −⋯− 𝑐𝑛𝑥𝑛 − 0𝑠1 − 0𝑠2 −⋯− 0𝑠𝑚 
𝑅𝑒𝑠𝑡𝑟𝑖çõ𝑒𝑠: 
𝑎11𝑥1 + 𝑎12𝑥2 + ⋯+ 𝑎1𝑛𝑥𝑛 + 𝑠1 = 𝑏1
𝑎21𝑥1 + 𝑎22𝑥2 + ⋯+ 𝑎2𝑛𝑥𝑛 + 𝑠2 = 𝑏2……………………………………………… . .
 𝑎𝑚1𝑥1 + 𝑎𝑚2𝑥2 + ⋯+ 𝑎𝑚𝑛𝑥𝑛 + 𝑠𝑚 = 𝑏𝑚
 
𝑥1, 𝑥2,…𝑥𝑛 ≥ 0 𝑒 𝑠1, 𝑠2,… , 𝑠𝑚 ≥ 0 
 
Onde x1, x2, ..., xn são as variáveis de decisão e a solução básica inicial 
é: 
𝑥1 = 𝑥2 = ⋯𝑥𝑛 = 0
𝑠1 = 𝑏1
𝑠2 = 𝑏2
𝑠𝑚 = 𝑏𝑚
 e z = 0. 
 
1) Para um problema de maximização com função objetivo (F.O.) Max z = 5x1 + 4x2 (por 
exemplo), sendo x1 e x2 variáveis não básicas, entra na base a variável com coeficiente 
mais positivo – no caso x1 (condição de otimalidade). 
2) Para determinar a variável que sai da base, calcula-se as razões não negativas entre os 
termos independentes (b) e os coeficientes (a) da variável que entra na base (no caso 
x1). Sai a variável da linha que apresentar a menor razão não negativa entre os 
coeficientes a e b. Para o caso onde x1 entra na base, tem-se: 
Min 
𝑏1
𝑎11
,
𝑏2
𝑎21
,… ,
𝑏𝑖
𝑎𝑖1
,… ,
𝑏𝑚
𝑎𝑚 1
 . Se 
𝑏𝑖
𝑎𝑖1
 é a menor razão não negativa, 𝑎𝑖1 é chamado de 
pivô. 
3) Zerar, usando operações elementares, os elementos da coluna do pivô, exceto o pivô que 
deve ser transformado em 1. 
EXEMPLOS: 
1- Resolver 
 Max z = 5x1 + 4x2 
 s.a. 
 6x1+4x2 <= 24 
 x1 + 2x2 <= 6 
 -x1 + x2 <= 1 
 x1 e x2 >=0 
2- Resolver graficamente e pelo método simplex o PPL. 
13 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
Max z = 3x1 + 5x2 
s.a. 
 2x1 + 4x2 <=10 
 6x1 + x2 <=20 
 x1 – x2 <=30 
 x1 >= 0 e x2 >= 0 
3- Resolva o PPL 
Min z = 3x1 - 4x2 + x3 
s.a. 
 x1 + x2 + x3 <=10 
 2x1 + x2 – x3 <= 20 
 x1, x2 e x3 >=0 (Obs.: multiplicar a F.O. por (-1). Desta forma, o problema de 
minimização é transformado em um problema de maximização: Max (-z) = -3x1 + 4x2 – x3). 
 
EXERCÍCIOS 
 
Resolver os modelos em programação linear, usando o método simplex. 
 
1- Max z = 10x1 + 12x2 
s.a. 
 x1 + x2 <=100 
 2x1 + 3x2 <= 270 
 x1, x2 >= 0 
2- Max z = 2x1 + 3x2 + 4x3 
s.a. 
 x1 + x2 + x3 <= 100 
 2x1 + x2 <=210 
 x1 <= 80 
 x1, x2, x3 >=0 
3- Max z = 0,2x1 + 2x2 + 4x3 
s.a. 
 x1 + 2x2 <= 20 
 3x1 + x3 <= 50 
 x1 + x2 – x3 <= 15 
 x1, x2, x3 >=0 
4- Max z = 5x1 - 3x2 + 4x3 – x4 
s.a. 
 x1 + x2 + x3 + x4 <= 600 
 2x1 + x3 <=280 
 x2 + 3x4 <=150 
 x1, x2, x3, x2 >=0 
5- Max z = 2x1 + 4x3 
s.a. 
 x1 + 2x2 + x3 <= 8.000 
 2x1 <= 6.000 
 x2 + x3 <=620 
 x1, x2, x3 >=0 
6- Max z = 2x1 + 4x2 + 6x3 
s.a. 
 x1 + x2 +x3 <= 100 
 2x1 – x2 + 5x3 <= 50 
 3x1 + x3 <= 200 
14 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
 x1, x2, x3 >=0 
RESPOSTAS: 
1- x1 = 30, x2 = 70, x3 = 0, x4 = 0 e z = 1.140. 
2- x1 = 0, x2 = 0, x3 = 100, x4 = 0, x5 = 210, x6 = 80 e z = 400. 
3- x1 = 0, x2 = 10, x3 = 50, x4 = 0, x5 = 0, x6 = 55 e z = 220. 
4- x1 = 0, x2 = 0, x3 = 280, x4 = 0, x5 = 320, x6 = 0, x7 = 150 e z = 1.120 
5- x1 = 3.000, x2 = 0, x3 = 620, x4 = 4.380, x5 = 0, x6 = 0 e z = 8.480 
6- x1 = 0, x2 = 75, x3 = 25, x4 = 17,5, x5 = 0, x6 = 0 e z = 450. 
 
 
PROBLEMAS COM RESTRIÇÕES DO TIPO “ >= ” OU “ = ”. 
 
 Problemas deste tipo apresentam uma solução básica inicial inviável. Para resolver esta 
questão devem-se acrescentar variáveis artificiais ao problema, encontrando assim uma solução 
básica inicial viável. Serão apresentados dois métodos para resolver este tipo de problema: M 
grande e 2 fases. 
 
MÉTODO DO M GRANDE 
 
 Acrescentam-se ao problema as variáveis artificiais, de modo que a solução básica inicial 
seja viável. Na F.O. os coeficientes das variáveis artificiais devem ser números grandes em 
relação aos coeficientes das variáveis de decisão. Já nas primeiras iterações procura-se tirar da 
base as variáveis artificiais. 
EXEMPLOS: 
 
1- Resolver 
Max z = x1 + x2 + x3 
s.a. 
 2x1 + x2 – x3 <= 10 
 x1 + x2 + 2x3 >= 20 
 2x1 + x2 + 3x3 = 60 
 x1, x2, x3 >=0 
2- Min z = 4x1 + x2 
s.a. 
 3x1 + x2 = 3 
 4x1 + 3x2 >= 6 
 x1 + 2x2 <=4 
 x1 e x2 >=0 
 
MÉTODO DAS 2 FASES OU F.O. ARTIFICIAL (W) 
 Acrescentam-se ao problema as variáveis artificiais e constrói-se uma F.O. artificial (W), 
esta função deverá ser minimizada. Após a minimização, se W = 0, abandona-se as variáveis 
artificiais. Caso contrário, a solução é inviável. 
EXEMPLOS: 
 
1- Resolver 
Max z = x1 + x2 + x3 
15 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
s.a. 
 2x1 + x2 – x3 <= 10 
 x1 + x2 + 2x3 >= 20 
 2x1 + x2 + 3x3 = 60 
 x1, x2, x3 >=0 
2- Min z = 4x1 + x2 
s.a. 
 3x1 + x2 = 3 
 4x1 + 3x2 >= 6 
 x1 + 2x2 <=4 
 x1 e x2 >=0 
 
VARIÁVEL LIVRE 
 
 Quando um PPL apresenta uma variável livre ou irrestrita de sinal, deve-se substituir 
essa variável pela diferença de duas variáveis não negativas. 
 
EXEMPLO 
 Dado o problema: 
 Max z = 5x1 + 3x2 
 s.a. 
 2x1 + x2 <=8 
 x1 – 2x2 <= 3 
 x1>=0 e x2 livre. 
 
Substitui-se x2 por x2’ – x2’’, sendo x2’>= 0 e x2’’ >=0. 
 
SOLUÇÃO DEGENERADA 
 
 Para determinar a variável que sai da base, determina-se a menor razão positiva entre 
os termos independentes e os coeficientes da variável que entra na base. Se ocorrer mais de um 
resultado nestas condições, uma ou mais variáveis básicas serão nulas, nesta situação a solução 
é dita degenerada. 
 
SOLUÇÕES MÚLTIPLAS 
 
 Se na solução ótima o coeficiente de uma variável não básica é zero, ela poderá entrar na 
base sem alterar o valor da função objetivo, gerando outra solução ótima, neste caso qualquer 
combinação linear dessa duas soluções também será ótima. 
 
EXEMPLOS 
 
1- Solução degenerada 
 
Max z = 3x1 + 9x2 
s.a. 
 x1 + 4x2 <=8 
 x1 + 2x2 <= 4 
 
 
 
16 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
Iteração Base x1 x2 x3 x4 Solução 
0 
Entra x2 
Sai x3 
Z -3 -9 0 0 0 
x3 1 4 1 0 8 
x4 1 2 0 1 4 
 
 Min {8/4, 4/2}= 2 
 
Iteração Base x1 x2 x3 x4 Solução 
1 
Entra x1 
Sai x4 
Z -3/4 0 9/4 0 18 
x2 ¼ 1 ¼ 0 2 
x4 ½ 0 -1/2 1 0 
 
 
Iteração Base x1 x2 x3 x4 Solução 
2 
Ótima 
Z 0 0 3/2 3/2 18 
x2 0 1 ½ -1/2 2 
x1 1 0 -1 2 0 
 
 
2- Soluções Múltiplas 
 
Max z = 2x1 + 4x2 
s.a. 
 x1 + 2x2 <= 5 
 x1 + x2 <=4 
 x1, x2 >=0 
 
 
Iteração Base x1 x2 x3 x4 Solução 
0 
Entra x2 
Sai x3 
Z -2 -4 0 0 0 
x3 1 2 1 0 5 
x4 1 1 0 1 4 
 
 
 
Iteração Base x1 x2 x3 x4 Solução 
1(ótima) 
Entra x1 
Sai x4 
Z 0 0 2 0 10 
x2 ½ 1 ½ 0 5/2 
x4 ½ 0 -1/2 1 3/2 
 
 
 
Iteração Base x1 x2 x3 x4 Solução 
2(ótima 
alternativa) 
Entra x2 
Sai x3 
Z 0 0 2 0 10 
x2 0 1 1 -1 1 
x1 1 0 -1 2 3 
 
17 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
 
3- Solução ilimitada 
 
Max z = 2x1 + x2 
s.a. 
 x1 – x2 <= 10 
 2x1 <= 40 
 x1, x2 >=0 
 
Base x1 x2 x3 x4 Solução 
Z -2 -1 0 0 0 
x3 1 -1 1 0 10 
x4 2 0 0 1 40 
 
EXERCÍCIOS 
1- Resolva pelo simplex, usando o método do M grande para obter a solução básica inicial. 
Max z = 2x1 + 3x2 
s.a. 
 x1 + x2 >= 10 
 2x1 + x2 <= 16 
 x1, x2 >=0 
2- Resolva pelo método simplex, usando o método das 2 fases para obter a solução básica 
inicial. 
Min z = 3x1 + 2x2 
s.a. 
 2x1 + x2 >= 10 
 x1 + 5x2 >= 15 
 x1, x2 >=0 
3- Resolva usando o simplex 
Max z = x1 + x2 + 2x3 
s.a. 
 x1 + 2x2 <=10 
 3x1 + 4x2 + x3 <=20 
 x1>=0, x3>=0, x2 livre de sinal. 
4- Mostre que o problema tem várias soluções. 
Min z = 2x1 + 4x2 + 10x3 
s.a. 
 x1 + x2 + x3 <= 120 
 x1 + 2x2 + 5x3 >= 30 
 x1, x2, x3 >=0 
5- Resolva usando o simplex 
Min z = 2x1 + 4x2 + 5x3 
s.a. 
 x1 + 2x2 + 10x3 <= 600 
 x1 – x2 + x3 >=50 
 2x1 – x3 <= 100 
18 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
 X1, x2, x3 >=0 
6- Verifique se a solução do modelo abaixo é limitada. Qual a melhor solução básica antes 
que a solução fique limitada? 
Max z = x1 + 2x2 + x3 
s.a. 
 2x1 + 3x2 + x3 >= 10 
 4x1 + x2 + 2x3 >=20 
 x1, x2, x3 >=0 
7- Min z = 3x1 + 2x2 + x3 
s.a. 
 3x1 + x2 + 3x3 >= 6 
 3x1 + 2x2 = 6 
 x1 – x2 <= 1 
 x1, x2, x3 >=0 
8- Um distribuidor de produtos para festas infantis compra dos produtores chapéus de 
papel, línguas-de-sogra e bexigas, e prepara caixas com esses 3 produtos na forma de 
kits para festas. Observações anteriores mostram que: (a) A quantidade de chapéus e 
línguas-de-sogra deve ser pelo menos 50% do total. (b) O pacote deve ter pelo menos 20 
bexigas. (c) Cada item deve concorrer com pelo menos 25% do total da caixa. O custo 
dos componentes (em milhares de unidades) é: chapéu de papel: 50.000; língua-de-
sogra: 20.000; bexigas: 5.000. Qual a composição da caixa que tem o menor custo? 
9- Uma empresa dispõe de recursos produtivos suficientes para produzir 3 diferentes 
produtos P1, P2 e P3. A capacidade de armazenagem, se fosse fabricado apenas um 
produto, seria de: 1.000 unidades para P1; 900 unidades para P2 e 1.200 unidades para 
P3. Espera-se ter que armazenar no máximo a produção de 5 dias. A capacidade de 
produção por hora para cada produto individualmente é de: 10 unidades para P1; 6 
unidades para P2 e 15 unidades para P3. A disponibilidade é de 8h/dia. A 
disponibilidade diária de matéria-prima, usada nos 3 produtos, é de 240 kg. O uso por 
unidade de produto é de 1,5kg para P1; 2,4 kg para P2 e 2 kg para P3. Se os lucros 
unitário são de 500 u.m. para P1, 800 u.m. para P2 e 400 u.m. para P3, qual a produção 
diária ótima? 
 
RESPOSTAS 
1- x1 = 0, x2 = 16 e z = 48 
2- x1 = 3,89, x2 = 2,22 e z = 16,11 
3- x1 = 0, x2 = 0, x3 = 20, x4 = 0, x5 = 0 e z = 40 (x2 = x5 –x4) 
4- x1 = 0, x2 = 0, x3 = 6, x4 = 114 e z = 60 . A variável não básica x2 tem coeficiente 
zero. 
5- x1 = 50, x2 = 0, x3 = 0, x4 = 550, x5 = 0, x6 = 0 e z = 100.6- Solução ilimitada. x1 = 0, x2 = 20, x3 = 0, x4 = 50 e z = 40. 
 
 
 
 
19 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
RESOLUÇÃO DE PPL USANDO O SOLVER DO EXCEL 
EXEMPLO: Resolver, usando o SOLVER do EXCEL, o seguinte PPL: 
Max z = 5x1 + 4x2 
 s.a. 
 6x1+4x2 <= 24 
 x1 + 2x2 <= 6 
 -x1 + x2 <= 1 
 x1 e x2 >=0 
 
SOLUÇÃO: 
No EXCEL, digite os dados do problema como mostra a figura 1. Os valores numéricos 
nas células da coluna D e linha 8 não são digitados, pois estes são os resultados obtidos 
com a execução do SOLVER. 
 
 
FIGURA 1 – PLANILHA DO EXCEL COM DADOS DO PPL. 
Além dos dados do problema, a figura 1 apresenta o procedimento para a resolução do 
PPL. No EXCEL (Office 2007) um PPL pode ser resolvido clicando na aba Dados e em 
seguida em Solver. Aberta a caixa de diálogo Parâmetros do solver, esta deverá ser 
preenchida com os dados do problema, como mostra a figura 2. 
20 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
 
FIGURA 2 – CAIXA DE DIÁLOGO DO SOLVER 
O campo Submeter às Restrições será preenchido a partir da caixa de diálogo Adicionar 
Restrição, caixa esta que pode ser aberta clicando no botão adicionar. A figura 3 mostra o 
preenchimento dos campos da caixa de diálogo Adicionar Restrição. 
 
 
 
 FIGURA 3- CAIXA DE DIÁLOGO PARA A INCLUSÃO DE RESTRIÇÕES 
 
 De volta à caixa de diálogo Parâmetros do Solver, clique no botão Opções e 
assinale os itens Presumir modelo linear e Presumir não negativo, conforme a figura 4. 
21 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
 
 FIGURA 4- OPÇÕES DO SOLVER 
 Finalmente em Parâmetros do Solver clique no botão Resolver. A solução ótima está 
registrada na figura 1 (x1 = 3, x2 = 1,5 e z = 21). 
 
RESOLUÇÃO DE PPL USANDO O APLICATIVO LINDO 
 Para problemas com um número reduzido de variáveis, a resolução de um PPL no LINDO 
é muito simples, basta digitar o problema na janela de comandos do LINDO como mostra a 
figura 5 
 
FIGURA 5 – RESOLUÇÃO DE UM PPL NO LINDO 
Na figura 5 aparece o PPL 
Max z = 5x1 + 4x2 
 s.a. 
 6x1+4x2 <= 24 
22 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
 x1 + 2x2 <= 6 
 -x1 + x2 <= 1 
 x1 e x2 >=0 
 
 As diferenças na escrita são mínimas, basicamente os comandos st e end. Digitado o 
problema, ele pode ser resolvido clicando-se em Solver na barra de ferramentas. A solução 
fornecida pelo LINDO aparece no formato mostrado na figura 6 
 
 
FIGURA 6 – FORMATO DA SOLUÇÀO DE UM PPL NO LINDO 
Além da solução ótimo (x1 = 3, x2 = 1,5 e z = 21), a figura 6 mostra também os preços duais e 
custos reduzidos. Os conceitos de preço dual e custo reduzido serão estudados no tópico. 
 
RESOLUÇÃO DE PPL USANDO O APLICATIVO LINGO 
 Da mesma forma que no LINDO, problemas com um número reduzido de variáveis 
podem ser resolvidos facilmente no LINGO. Basta digitar o problema na janela de comandos do 
LINGO como mostra a figura 7. 
 
23 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
 
FIGURA 7- RESOLUÇÃO DE UM PPL NO LINGO 
 Digitado o problema, ele pode ser resolvido clicando-se em Solver na barra 
de ferramentas. A solução fornecida pelo LINGO aparece no formato mostrado na figura 8. 
 
 
FIGURA 8 - FORMATO DA SOLUÇÀO DE UM PPL NO LINGO. 
 
EXERCÍCIOS. 
 Use o aplicativo LINDO, LINGO e o Solver do Excel para resolver os exercícios da lista 1 
(páginas 3, 4 e 5) 
 
24 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
ANÁLISE DE SENSIBILIDADE 
EXEMPLO 
 A Machine e Cia produz 2 produtos em 2 máquinas. Uma unidade do produto 1 requer 2 
horas da máquina 1 e 1 hora da máquina 2. Para o produto 2, uma unidade requer 1 hora da 
máquina 1 e 3 horas da máquina 2. As receitas por unidade dos produtos 1 e 2 são $ 30 e $ 20, 
respectivamente. O tempo de processamento diário disponível é 8 horas. Pretende-se 
maximizar a receita. Resolver o problema graficamente. 
SENSIBILIDADE DA SOLUÇÃO ÓTIMA ÀS VARIAÇÕES NA DISBONIBILIDADE DE RECURSOS 
(LADO DIREITO DAS RESTRIÇÕES). 
 Considere o problema da Machine e Cia. Calcular ∆z (variação da receita) para uma 
variação unitária na disponibilidade do recurso 1 (máquina 1), ou seja: mudar a restrição 1 para 
2x1 + x2 <=9 ou 2x1 + x2 <=7. Em seguida, faça o mesmo para a restrição 2. 
(Esta operação determinará o preço dual. Definição: Preço dual (preço sombra ou preço de 
oportunidade) é dado pela razão ∆z/∆Ri , onde ∆Ri = variação do recurso i. 
SOLUÇÃO: 
 Restrição 1: 2x1 + x2 <=7 ⇒ 
𝑥1 = 2,6
𝑥2 = 1,8
𝑧 = 114
⟹ Δ𝑧 = 128 − 114 ⟹ Δ𝑧 = 14 . 
 Restrição 2: x1 + 3x2 <= 7 ⇒ 
𝑥1 = 3,4
𝑥2 = 1,2
𝑧 = 126
⟹ Δ𝑧 = 128 − 126 ⟹ Δ𝑧 = 2. 
 Assim, o preço dual relativo ao recurso 1 é $14 e $2 para o recurso 2. Então, o preço dual 
indica a variação da receita total. Por exemplo: aumentando (ou diminuindo) o recurso 1 em 
uma unidade, a receita aumentará (ou diminuirá) em $ 14. 
DETERMINAÇÃO ALGÉBRICA DAS FAIXAS DE VIABILIDADE 
 Considere o problema da Machine e Cia. Sejam D1 e D2 as variações (positivas ou 
negativas) nos recursos 1 e 2, respectivamente. De forma que: 
 Max z = 30x1 + 20x2 
 s.a. 
 2x1 + x2 <= 8 + D1 
 x1 + 3x2 <= 8 + D2 
 x1, x2 >=0 
 
 Encontre os intervalos de variação para os recursos 1 e 2, para os quais o preço dual não 
sofre variação. 
QUADRO INICIAL 
Base x1 x2 x3 x4 Solução D1 D2 
Z -30 -20 0 0 0 0 0 
x3 2 1 1 0 8 1 0 
x4 1 3 0 1 8 0 1 
 
 
25 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
QUADRO ÓTIMO 
Base x1 x2 x3 x4 Solução D1 D2 
Z 0 0 14 2 128 14 2 
x1 1 0 3/5 -1/5 3,2 3/5 -1/5 
x2 0 1 -1/5 2/5 1,6 -1,5 2/5 
 
Assim: z = 128 + 14D1 + 2D2, x1 = 3,2 + 3D1/5 – D2/5 e x2 = 1,6 – D1/5 + 2D2/5. 
Condição de viabilidade: x1 >= 0 e x2 >= 0, fazendo D2 = 0 tem-se: 
3,2 +
3𝐷1
5
≥ 0
1,6 −
𝐷1
5
≥ 0
⟹
 
𝐷1 ≥ −5,33
𝐷1 ≤ 8
⟹ 5,33 ≤ 𝐷1 ≤ 8 ⟹ 8 − 5,33 ≤ 𝑟𝑒𝑐𝑢𝑟𝑠𝑜 1 ≤ 8 + 8 ⟹ 2,67 ≤ 𝑟𝑒𝑐 1 ≤ 16 (faixa 
de viabilidade para o recurso 1, isto significa que para variações do recurso 1 neste intervalo o 
preço dual permanecerá igual a $14). Fazendo D1 = 0, vem: 
3,2 −
𝐷2
5
≥ 0
1,6 +
2𝐷2
5
≥ 0
⟹ 
𝐷2 ≤ 16
𝐷2 ≥ −4
⟹
−4 ≤ 𝐷2 ≤ 16 ⟹ 4 ≤ 𝑟𝑒𝑐 2 ≤ 24 (faixa de viabilidade para o recurso 2) 
 
SENSIBILIDADE DA SOLUÇÃO ÓTIMA ÀS VARIAÇÕES NA RECEITA UNITÁRIA OU CUSTO 
UNITÁRIO (COEFICIENTES DA F.O.) 
 No problema da Machine e Cia, alterar a F.O. de z = 30x1 + 20x2 para z = 35x1 + 25x2 e 
calcular a solução ótima. 
SOLUÇÃO: 
 A solução ótima continua sendo o ponto (3,2;1,6), agora com z = 152. 
 Ainda considerando o problema da Machine e Cia, alterar a F.O. de z = 30x1 + 20x2 para 
z = 5x1 + 20x2 e calcular a solução ótima. 
SOLUÇÃO: 
 -Para o ponto extremo da região viável A(0;2,67) encontra-se z = 53,4. 
 - Para o ponto extremo da região viável B(4;0) encontra-se z = 20. 
 - Para o ponto extremo da região viável C(3,2;1,6) encontra-se z = 48 
Assim, a solução ótima é o ponto A. 
OBS.: para uma determinada variação nos coeficientes da F.O., dita faixa de otimalidade, 
a solução ótima (valores das variáveis de decisão) permanece sem alteração. 
DETERMINAÇÃO ALGÉBRICA DA FAIXA DE OTIMALIDADE. 
 Considere o problema da Machine e Cia. Sejam d1 e d2 as variações (positivasou 
negativas) nas receitas (ou custos) dos produtos 1 e 2, respectivamente. Assim, tem-se: 
 Max z = (30 + d1)x1 + (20 + d2)x2 
 Encontre as faixas de otimalidade. 
26 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
 QUADRO INICIAL 
Base x1 x2 x3 x4 Solução 
Z -30-d1 -20-d2 0 0 0 
x3 2 1 1 0 8 
x4 1 3 0 1 8 
 
 
Para se obter a nova linha da F.O., pode-se usar o quadro ótimo do problema original, 
acrescentando a linha I: (𝑑1 𝑑2 0 0 0) e a coluna I: 
1
𝑑1
𝑑2
 . Em seguida faz-se a operação: 
multiplica a coluna I pelos coeficientes da variável xj, somar os produtos e subtrair o coeficiente 
da linha I correspondente a xj. 
QUADRO ÓTIMO 
Base x1 x2 x3 x4 Solução 
Z 0 0 14 2 128 
x1 1 0 3/5 -1/5 3,2 
x2 0 1 -1/5 2/5 1,6 
 
Acrescentando col. I e lin I e fazendo a operação mencionada, obtém-se: 
 Linha I: d1 d2 0 0 0 
 Base x1 x2 x3 x4 Solução 
1 Z 0 0 14-d2/5 + 3d1/5 2-d1/5+2d2/5 128+3,2d1+1,6d2 
d1 x1 1 0 3/5 -1/5 3,2 
d2 x2 0 1 -1/5 2/5 1,6 
Coluna I 
Obs.: dj = 0 para as variáveis de folga. 
Condição de otimalidade: 
Coeficiente de x3 >=0 ⇒ 14 – d2/5 + 6d1/10 >= 0. 
Coeficientes de x4 >=0 ⇒ 2 – d1/5 + 2d2/5 >= 0 
Fazendo d2 = 0 ⇒ 
14 +
6𝑑1
10
≥ 0
2 −
𝑑1
5
≥ 0
⟹ 
𝑑1 ≥ −70/3
𝑑1 ≤ 10
⇒ −
70
3
≤ 𝑑1 ≤ 10 ⟹ 
30 −
70
3
≤ 𝑟𝑒𝑐𝑒𝑖𝑡𝑎 𝑑𝑜 𝑝𝑟𝑜𝑑𝑢𝑡𝑜 1 ≤ 30 + 10 ⟹ 6,67 ≤ 𝑟𝑒𝑐𝑒𝑖𝑡𝑎 𝑑𝑜 𝑝𝑟𝑜𝑑. 1 ≤ 40 (esta é a faixa de 
otimalidade para o coeficiente de x1 em F.O.- mantendo-se constante o coeficiente de x2). 
 A solução ótima do problema continuará sendo x1 = 3,2 e x2 = 1,6 enquanto a receita do 
produto 1 permanecer no intervalo 6,67 ≤ 𝑟𝑒𝑐𝑒𝑖𝑡𝑎 𝑑𝑜 𝑝𝑟𝑜𝑑. 1 ≤ 40. 
 Fazendo d1 = 0, encontra-se a faixa de otimalidade para a receita do produto 2: 
15 ≤ 𝑟𝑒𝑐𝑒𝑖𝑡𝑎 𝑑𝑜 𝑝𝑟𝑜𝑑𝑢𝑡𝑜 2 ≤ 90. 
 
27 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
CUSTO REDUZIDO 
 Definição: custo reduzido/unidade = (custo dos recursos/unidade) - (receita/unidade). 
 No quadro ótimo os coeficientes da linha da F.O. representam os custos reduzidos, sendo 
o preço dual representado pelos coeficientes da variáveis de folga/excesso da F.O.. Quando a 
restrição tem o sinal “=”, deve-se somar o coeficiente da variável artificial correspondente com 
o coeficiente de aj na F.O. original. 
EXEMPLO: 
 Max z = x1 + x2 + x3 
 s.a. 
 2x1 + x2 – x3 <= 10 
 x1 + x2 + 2x3 >=20 
 2x1 + x2 + 3x3 = 60 
 x1, x2 e x3 >=0 
 
Preparando o problema para ser resolvido pelo método do M grande, tem-se a F.O. : 
Max z = x1 + x2 + x3 + 0x4 + 0x5 – m2a2 – m3a3, onde a2 e a3 são variáveis artificiais. O 
coeficiente de a3 na linha z do quadrado ótimo é ½ + m3. Assim, o preço dual para a restrição 3 
é ½ + m3 +(-m3) =1/2. 
 No exemplo Machine e Cia o quadro ótimo mostra que o custo reduzido para os produtos 
1 e 2 é zero (coeficiente de x1 e x2 na F.O.) e preço dual: $14 e $ 2, coeficientes de x3 e x4, 
respectivamente. 
 Entendendo o preço dual como a valorização interna do recurso, tem-se: 
 Custo reduzido para o produto 1 (coef. de x1) = (qtde. recurso 1 p/ prod. 1).(preço dual 
p/ recurso 1) + (qtde do recurso 2 para o prod. 1). (preço dual p/ recurso 2) – (receita) = 2.14 
+ 1.2 – 30 = 0. 
 Custo reduzido p/ o produto 2 = 1.14 + 3.2 – 20 = 0 
 Seja xj uma variável de decisão. Se o custo reduzido de xj = k > 0, a produção de uma 
unidade de xj, acarreta um decréscimo na receita igual a k. 
 
EXEMPLO. 
 A Star e Cia monta 3 tipos de brinquedos – trens, caminhões e carros – usando 3 
operações. Os limites diários dos tempos disponíveis para as 3 operações são 430, 460 e 420 
minutos, respectivamente, e as receitas por unidade de trem, caminhão e carro de brinquedo 
são $ 3, $ 2 e $ 5, respectivamente. Os tempos de montagem por trem nas 3 operações são 1, 3 e 
1 minutos, respectivamente. Os tempos correspondentes por caminhão e por carro são (2, 0, 4) 
e (1, 2, 0) minutos ( o tempo zero significa que a operação não foi utilizada). Pretende-se 
maximizar a receita. 
(a) Use o simplex para resolver o problema como um PPL. 
(b) Determine a faixa de viabilidade para o recuso 2(operação 2: 460 minutos) e interprete o 
resultado. 
(c) Determine a faixa de otimalidade para a receita unitária do produto 2 (caminhões) e 
interprete o resultado. 
(d) O que acontecerá com a receita total se o recurso 1 aumentar de 430 para 435? Use o preço 
dual para justifique a sua resposta. 
(e) O que acontecerá com a receita total se o recurso 3 aumentar de 420 para 430? Use o preço 
dual para justifique a resposta. 
(f) O que acontecerá com a receita se a Star e Cia tiver que produzir 3 unidades do produto 1 
(trem). Use o custo reduzido para justificar a sua resposta. 
 
28 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
ANALISE DE SENSIBILIDADE USANDO OS APLICATIVOS LINDO, LINGO E O SOLVER 
EXEMPLO: Use o Solver e o Lindo para obter as faixas de viabilidade e otimalidade do seguinte 
PPL: 
Max z = 5x1 + 4x2 
 s.a. 
 6x1+4x2 <= 24 
 x1 + 2x2 <= 6 
 -x1 + x2 <= 1 
 x1 e x2 >=0 
 No processo de resolução de um PPL no Solver a última caixa de diálogo é Resultados do 
Solver, mostrada na figura 9. 
 
 
FIGURA 9- CAIXA DE DIÁLOGO RESULTADOS DO SOLVER 
 Nesta caixa de diálogo (figura 7), selecione o item Sensibilidade e clique ok. Desta forma 
obtém-se o relatório de sensibilidade, mostrado na figura 10. 
 
29 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
 
FIGURA 10 – RELATÓRIO DE SENSIBILIDADE 
 
 As duas últimas colunas da primeira tabela do relatório de sensibilidade (figura 8) 
mostram o acréscimo e decréscimo que pode ser praticado no coeficiente de x1 de modo que a 
solução ótima permanece sem alteração. Assim, a faixa de otimalidade para o coeficiente de x1 
é: 5 – 3 <= coeficiente de x1 <= 5 + 1 ⇒ 2 <= coeficiente de x1 <= 6. Para o coeficiente de x2, 
tem-se: 4 – 0,6666667 <= coeficiente de x2 <= 4 + 6 ⇒ 0,33333<= coeficiente de x2 <=10. 
 Nas duas últimas colunas da segunda tabela do relatório de sensibilidade (figura 8) 
estão registradas as possíveis variações na disponibilidade do recurso 1 de modo que o preço 
dual (preço sombra) permaneça sem alteração. Desta forma, a faixa de viabilidade para o 
recurso 1 é: 24 – 6,666667 <= recurso 1 <= 24 + 12 ⇒ 17,3333 <= recurso 1 <= 36. Para o 
recurso 2 tem-se: 6 – 2 <= recurso 2 <= 6 + 2 ⇒ 4 <=recurso 2 <= 8. Para o recurso 3 tem-se: 
1 – 2,5 <=recurso 3 <= 1 + infinito ⇒ -1,5 <= recurso 3 <= infinito. 
 
Análise de Sensibilidade no LINDO. 
 No LINDO, como explicado anteriormente, para resolver o problema clica-se em Solver. 
Após essa ação surge a pergunta DO RANGE(SENSITIVITY) ANALYSIS?, como mostra a figura 
11. 
 
30 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
 
FIGUARA 11 – ANÁLISE DE SENSIBILIDADE: SIM OU NÃO? 
 
 Clicando em Yes o Lindo resolve o problema e faz a análise de sensibilidade. O relatório 
emitido pelo Lindo aparece na figura 12. Em OBJ COFFICIENT RANGES pode-se obter as faixas 
de otimalidade e em RIGHTHAND SIDE RANGES obtém-se as faixas de viabilidade. 
 
 
 
 
FIGURA 12 – RELATÓRIO DE SENSIBILIDADE EMITIDO PELO LINDO 
31 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
Análise de Sensibilidade no LINGO. 
 Antes de resolver o problema, clique no menu LINGO e em seguida em Options. Assim, 
obtém-se a janela mostradana figura 13. 
 
FIGURA 13 – JANELA DO LINGO ONDE ATIVA-SE A ANALISE DE SENSIBILIDADE. 
 Na janela mostrada na figura 13, selecione a aba General Solver e no campo Dual 
Computations escolha a opção Prices & Ranges e clique em OK. Após a resolução do problema, 
ilustrado na figura 7, ative a janela de comandos do LINGO (figura 7) e clique no menu LINGO e 
em seguida na opção Range, como mostra a figura 14. 
32 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
 
FIGURA 14 – PROCEDIMENTO P/ DE ANÁLISE DE SENSIBILIDADE APÓS A OTIMIZAÇÃO DO 
PROBLEMA. 
 
 Clicando em Range, o LINGO fornece a análise de sensibilidade – figura 15. 
 
FIGURA 15 – RELATÓRIO DE ANÁLISE DE SENSIBILIDADE EMITIDO PELO LINGO. 
 
33 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
EXERCÍCIOS 
Resolver as questões abaixo usando o aplicativo Lindo e o solver do Excel 
1- No programa de produção para o próximo período, a empresa Beta Ltda., escolheu 3 
produtos P1, P2 e P3. O quadro abaixo mostra os montantes solicitados por unidade na 
produção. 
 
Produto Contribuição (lucro 
por unidade) 
Horas de trabalho Horas de uso de 
máquinas 
Demanda máxima 
 P1 2100 6 12 800 
 P2 1200 4 6 600 
 P3 600 6 2 600 
 
 Os preços de venda foram fixados por decisão política e as demandas foram estimadas 
tendo em vista esses preços. A firma pode obter um suprimento de 4800 horas de trabalho 
durante o período de processamento e pressupõe-se usar 3 máquinas que podem prover 7200 
horas de trabalho. 
MODELO LINEAR: 
 Max lucro = 2100x1 + 1200x2 + 600x3 
 s.a . 
 6x1 + 4x2 + 6x3 ≤ 4800 (horas de trabalho) 
 12x1 + 6x2 + 2x3 ≤ 7200 (horas de máquina) 
 1x1 ≤ 800 (demanda P1) 
 1x2 ≤ 600 (demanda P2) 
 1x3 ≤ 600 (demanda P3) 
 x1 ≥ 0, x2 ≥ 0 , x3 ≥ 0 
 Pede-se: 
a) Quais são os recursos abundantes? 
b) O que acontecerá com o lucro se o recurso horas de trabalho for aumentado em uma 
unidade? 
c) Além das horas de máquina já disponíveis, é interessante contratar uma hora a mais por 
$ 200,00? Justifique a sua resposta? 
d) Dê a faixa de variação do coeficiente x1 na função objetivo para que a solução ótima 
permaneça sem alteração. 
e) Dê a faixa de variação do recurso horas de máquina para que o preço dual 
correspondente permaneça sem sofrer alteração. 
34 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
2- A Star e Cia monta 3 tipos de brinquedos – trens, caminhões e carros – usando 3 
operações. Os limites diários dos tempos disponíveis para as 3 operações são 430, 460 e 
420 minutos, respectivamente, e as receitas por unidade de trem, caminhão e carro de 
brinquedo são $ 3, $ 2 e $ 5, respectivamente. Os tempos de montagem por trem nas 3 
operações são 1, 3 e 1 minutos, respectivamente. Os tempos correspondentes por 
caminhão e por carro são (2, 0, 4) e (1, 2, 0) minutos ( o tempo zero significa que a 
operação não foi utilizada). Pede-se: 
a) O lucro máximo; 
b) A solução do ppl sugere a fabricação de quantos trens? A produção de unidade a mais de 
trem aumentará ou diminuirá o lucro? Em quanto? 
c) Diminuindo a disponibilidade da restrição 2 (operação 2) em 10 minutos, o lucro 
aumentará ou diminuirá? Em quanto? Essa mudança na restrição 2 (diminuição em 10 
minutos) alterará o preço dual correspondente? 
d) Qual a faixa possível de variação do recurso 1 para que o preço dual permaneça igual a 
1? 
e) A solução ótima sugere a fabricação de quantos caminhões? E carros? 
f) Aumentando a receita unitária obtida com a venda de caminhões de $ 2 para $ 9, o 
número de de caminhões e carros fabricados deverá aumentar ou diminuir? 
3- O Sr. Jaime Santana, proprietário da Cia Santana, formulou corretamente o seu problema 
de maximizar o lucro da seguinte maneira: 
Max z = 32x1 + 40 x2 + 48x3 
s.a . x1 + x2 + x3 <=180 horas (máquina 1) 
 4x1 + 2x2 + 5x3 < = 280 horas (máquina 2) 
 2x1 + 5x2 + 5x3 <= 380 
 x1, x2, x3 >=0 
 a) No momento o produto 3 não está sendo fabricado, em quanto ficaria o lucro se fossem 
fabricados 10 unidades do produto 3? 
 b) Atualmente o lucro ótimo é 3680. Reduzindo a disponibilidade da máquina 3 para 350 
horas, o lucro sofrerá alteração? Justifique. 
 c) Dê a faixa de variação do coeficiente x1 na função objetivo para que a solução ótima (x1=40 
e x2= 60) permaneça sem alteração. 
 d) Você pagaria um preço de $ 5,50 por uma hora a mais de máquina 2? Justifique 
 4- Escolha 5 PPL e resolva-os a partir do LINDO e SOLVER. Imprima o resultado completo 
(incluindo a analise de sensibilidade). 
 
DUALIDADE 
 
 Em problemas de PL, o problema DUAL é obtido a partir de um problema PRIMAL 
(original). De forma que a solução ótima do dual é igual a solução ótima do primal. Se o primal é 
um problema de maximização, o dual correspondente é de minimização e vice-versa. 
 
REGRAS PARA CONSTRUÇÃO DO DUAL 
 
35 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
PROBLEMAS DE MAXIMIZAÇÃO PROBLEMAS DE MINIMIZAÇÃO 
 Restrições Variáveis 
 >= ⇔ <=0 
 <= ⇔ >=0 
 = ⇔ livre de sinal 
 Variáveis Restrições 
 >=0 ⇔ >= 
 <=0 ⇔ <= 
 Irrestrita ⇔ = 
 
 
EXEMPLOS 
1- Dado o primal: Max z = 2x1 + 3x2 + x3 
 s.a. 
 3x1 + 4x2 + 2x3 <= 10 
 2x1 + 6x2 + x3 <= 20 
 x1 – x2 – x3 <= 30 
 x1, x2, x3 >= 0 
 
 Obter o dual correspondente 
 
2- Dado o primal: Max z = 2x1 + 3x2 + x3 
 s.a 
 x1 + x2 <= 10 
 2x1 + 4x2 – x3 = 20 
 x1, x2, x3 >=0 
Obter o dual. 
 
3- Primal: Min z = 15x1 + 12x2 
 s.a. 
 x1 + 2x2 >= 3 
 2x1 – 4x2 <= 5 
 x1, x2 >=0 
Obter o dual. 
 
RELAÇÕES ENTRE AS SOLUÇÕES PRIMAL E DUAL 
 Considere um problema de maximização (primal) com restrições do tipo “<=”, variáveis 
não negativas e o problema dual correspondente. 
 No quadro ótimo do primal os coeficientesda F.O. correspondem aos valores das 
variáveis do dual, da seguinte forma: 
 PRIMAL DUAL 
Coeficiente da variável de folga ⇔ Valor da variável de decisão 
Coeficiente da variável de decisão ⇔ Valor da variável de folga 
 
EXEMPLO: 
 Primal: Max z = x1 + 2x2 + 3x3 
 s.a. 
 x1 + x2 + x3 <= 10 
 2x1 + x2 + 4x3 <=12 
36 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
 x1 + 3x2 – x3 <= 9 
 x1 >= 0, x2 >=0 e x3 >= 0 
 Dual: Min D = 10y1 + 12y2 + 9y3 
 s.a. 
 y1 + 2y2 + y3 >= 1 
 y1 + y2 + 3y3 >= 2 
 y1 + 4y2 – y3 >= 3 
 y1, y2, y3 >=0 
 
QUADRO ÓTIMO DO PRIMAL 
Base x1 x2 x3 s1 s2 s3 Solução 
Z 1,077 0 0 0 0,846 0,385 13,615 
s1 0,154 0 0 1 -0,308 -0,231 4,231 
x3 0,125 0 1 0 0,231 -0.077 2,077 
x2 0,461 1 0 0 0,077 0,308 3,692 
 
 Analisando o quadro acima, determina-se: 
 
𝑦1 = 0
𝑦2 = 0,846
𝑦3 = 0,385
 𝑉𝑎𝑟𝑖á𝑣𝑒𝑖𝑠 𝑑𝑒 𝑑𝑒𝑐𝑖𝑠ã𝑜 𝑛𝑜 𝑑𝑢𝑎𝑙 𝑜𝑢 𝑝𝑟𝑒ç𝑜 𝑑𝑢𝑎𝑙. 
 
 
𝑡1 = 1,077
𝑡2 = 0
𝑡3 = 0
 𝑉𝑎𝑟𝑖á𝑣𝑒𝑖𝑠 𝑑𝑒 𝑓𝑜𝑙𝑔𝑎 𝑛𝑜 𝑑𝑢𝑎𝑙 . 
 
Solução do primal: 
 
 
𝑥1 = 0
𝑥2 = 3,692
𝑥3 = 2,077
 𝐶𝑜𝑒𝑓𝑖𝑐𝑖𝑒𝑛𝑡𝑒𝑠 𝑑𝑎𝑠 𝑣𝑎𝑟𝑖á𝑣𝑒𝑖𝑠 𝑑𝑒 𝑓𝑜𝑙𝑔𝑎 (𝑡1, 𝑡2 𝑒 𝑡3)𝑛𝑜 𝑑𝑢𝑎𝑙 
 
 
𝑠1 = 4,231
𝑠2 = 0
𝑠3 = 0
 𝐶𝑜𝑒𝑓𝑖𝑐𝑖𝑒𝑛𝑡𝑒𝑠 𝑑𝑎𝑠 𝑣𝑎𝑟𝑖á𝑣𝑒𝑖𝑠 𝑑𝑒 𝑑𝑒𝑐𝑖𝑠ã𝑜 (𝑦1,𝑦2 𝑒 𝑦3)𝑛𝑜 𝑑𝑢𝑎𝑙. 
 
ALGUNS VALORES DO QUADRO ÓTIMO DUAL 
 
Base y1 y2 y3 t1 t2 t3 Solução 
-D 4,231 0 0 0 3,692 2,077 -13,615 
 0 0 1 1,077 
 1 0 0 0,846 
 0 1 0 0,385 
 
 
 
 No quadro inicial do primal, a matriz formada pelos coeficientes de s1, s2 e s3 (variáveis 
de folga) nas restrições é uma matriz identidade. No quadro ótimo esta matriz é transformada 
em inversa e pode ser usada para o cálculo dos preços duais y1, y2 e y3. 
 Preço dual = [vetor linha dos coeficientes da F.O. original das variáveis básicas (na 
ordem apresentada no quadro ótimo primal)] vezes [matriz inversa da solução primal ótima]. 
No exemplo anterior, tem-se: (y1 y2 y3) = (coef. De s1, x3 e x2 na F.O. original)x(matriz 
inversa) ⇒ (y1 y2 y3) = (0 3 2). 
1 −0,308 −0,231
0 0,231 −0,077
0 0,077 0,308
 ⇒ 
𝑦1 = 0
𝑦2 = 0,846
𝑦3 = 0,385
 
37 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
 
 Para obter o custo reduzido no modelo primal, usa-se as restrições do modelo dual. 
 
Custo reduzido do produto 1 = y1 + 2y2 + y3 -1 = 0 + 2.0,846 + 0,385 = 1,077 
Custo reduzido do produto 2 = y1 + y2 + 3y3 – 2 = 0 
Custo reduzido do produto 3 = y1 + 4y2 – y3 – 3 = 0 
 
CÁLCULO DA COLUNA DAS RESTRIÇÕES 
 
 Para obter a coluna j das restrições (lado direito ou lado esquerdo), deve-se multiplicar 
a matriz inversa pela coluna j das restrições originais. No exemplo anterior, tem-se: 
 
 
 
 
 
4,231
2,077
3,692
 = 
1 −0,308 −0,231
0 0,231 −0,077
0 0,077 0,308
 . 
10
12
9
 
 
 
𝐿𝑎𝑑𝑜 𝑑𝑖𝑟𝑒𝑖𝑡𝑜
𝑑𝑎𝑠 𝑟𝑒𝑠𝑡𝑟𝑖çõ𝑒𝑠
𝑛𝑜 𝑞𝑢𝑎𝑑𝑟𝑜 ó𝑡𝑖𝑚𝑜
 
𝐼𝑛𝑣𝑒𝑟𝑠𝑎 𝑞𝑢𝑎𝑑𝑟𝑜
ó𝑡𝑖𝑚𝑜 𝑝𝑟𝑖𝑚𝑎𝑙
 
𝐿𝑎𝑑𝑜 𝑑𝑖𝑟𝑒𝑖𝑡𝑜 𝑑𝑎𝑠
𝑟𝑒𝑠𝑡𝑟𝑖çõ𝑒𝑠 𝑜𝑟𝑖𝑔𝑖𝑛𝑎𝑖𝑠 
 
 
Obs.: pequenas diferenças são conseqüências dos arredondamentos. 
 
ANÁLISE ECONÔMICA 
 
 Considere um problema de maximização do lucro. Exemplo: seja o programa de 
produção de 2 itens P1 e P2, a partir dos recursos R1 e R2. O quadro abaixo resume os dados. 
 
Produtos Recurso R1 - uso/un. Recurso 2 - uso/un. Lucro/unidade 
P1 2 10 50 
P2 3 5 90 
Disponibilidade de 
recursos 
300 1000 
 
 O modelo linear é: 
 Max z = 50x1 + 90x2 
 s.a. 
 2x1 + 3x2 <=300 : restrição 1 (recurso 1) : y1(variável dual) 
 10x1 + 5x2 <= 1000 : restrição 2 (recurso 2): y2(variável dual) 
 x1, x2 >=0, onde x1 = quantidade de P1 e x2 = quantidade de P2. 
 
QUADRO ÓTIMO 
 
 x1 x2 s1 s2 Solução 
Z 10 0 30 0 9000 
x2 0,67 1 0,33 0 100 
s2 6,65 0 -1,65 1 500 
 
Onde s1 = variável de folga da restrição 1 e s2 = variável de folga da restrição 2. 
 
Pede-se: 
38 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
a) O modelo dual correspondente. 
b) A linha da F.O. e os termos independentes (lado direito das restrições) no quadro ótimo 
dual. 
c) Quais são os recursos abundantes? E os escassos? 
d) Se tivéssemos que fabricar 1 unidade de P1, o que iria ocorrer com o valor do lucro? 
e) O que acontecerá com a solução do problema se o recurso 1 for reduzido em 1 unidade? 
f) É interessante, em termos do lucro, vender 1 unidade do recurso 1 por $ 50? 
g) Qual o significado das variáveis duais y1 e y2? 
h) O que determina a F.O. do problema dual? 
i) Na restrição dual 2y1 + 10y2 >= 50, qual o significado do lado esquerdo? E do lado 
direito? 
j) Em termos de valor interno e externo, como justificar a produção de P2? 
k) Em termos econômicos, é compensador aumentar em 1 unidade o recurso 2? 
 
EXERCÍCIOS 
1- Suponha que um problema de produção tenha como modelo: 
Max L = x1 + 0,3x2 + 3x3 
s.a. 
 x1 + x2 + x3 <= 10 
 2x1 + x2 + 4x3 <= 12 
 x1 + 3x2 – x3 <= 9 
 x1, x2, x3 >=0 
e que o quadro final de solução pelo simplex seja: 
Base x1 x2 x3 s2 s2 s3 Solução 
L 0,5 0,45 0 0 0,75 0 9 
s1 0,5 0,75 0 1 -0,25 0 7 
x3 0,5 0,25 1 0 0,25 0 3 
s3 1,5 3,25 0 0 0,25 1 12 
Onde xi são as decisões de fabricação dos produtos Pi e si as sobras dos recursos Ri no 
programa. O objetivo é maximizar o lucro devido a produção e comercialização dos 
produtos. Responder às perguntas: 
(a) Qual a solução mostrada no quadro? 
(b) Quais são os recursos escassos? 
(c) O que ocorreria com o objetivo se por um motivo de força maior tivéssemos que 
fabricar uma unidade de P1? 
(d) Se alguém quisesse adquirir uma unidade do recurso R2, você estaria disposto a 
vender? Qual o preço que compensa a venda? 
(e) Construa o modelo dual do problema. 
(f) Construa o quadro final de solução do modelo dual, com os coeficientes que 
realmente interessam. Qual a solução do dual? 
(g) O que significa a variável dual y1? 
(h) O que mede a função objetivo dual? 
(i) O que mede o lado esquerdo da segunda restrição dual? E o lado direito? 
(j) Em termos de valores interno e externo, como podemos justificar a não produção de 
P2? 
(k) Em termos de valores interno e externo, como podemos justificar a não produção de 
P3? 
(l) Quanto você pagaria por uma unidade adicional do recurso R2? Por quê? 
Quanto você pagaria por uma unidade adicional do recurso R2? Por quê? 
39 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
2- Um pecuarista prepara ração a partir de 3 ingredientes, que contêm 3 nutrientes 
indispensáveis na alimentação dos animais. O quadro abaixo mostra a composição, 
exigências e custos dos elementos na mistura. 
Ingredientes Nutrientes (% por kg de ingredientes) Custo ingredien-
tes em u.m./kg Nutriente 1 Nutriente 2 Nutriente 3 
1 50 20 10 200 
2 20 30 30 150 
3 10 20 50 240 
Exigência mínima 
em kg/saco de 40kg 
6 5 8 
O objetivo e atender às exigências com menor custo. Pede-se: 
(a) Construir o modelo linear do problema, ende xi são as quantidades dos ingredientes 
usados por kg de ração. 
(b) Construir o modelo dual correspondente. 
(c) Resolver o Problemapelo método simplex (sugestão: resolva o modelo dual, que 
exige menos cálculos). Construa o quadro finalprimal e dual. 
(d) O que representam, no caso, as variáveis yi (variáveis duais)? 
(e) O que representam, no problema, as variáveis ti (variáveis de folga no dual)? 
(f) O que mede o lado esquerdo da primeira restrição primal? E o lado direito? 
(g) O que significa para o plano ótimo aumentar a exigência de seis para sete kg na 
participação do nutriente 1 no saco de ração? 
3- Um distribuidor dispõe de um armazém com 100.000 m3 para estocar produtos para 
venda futura. Ele dispõe de 30.000.000,00 u.m. para a compra, e pretende adquirir 3 
produtos cujos dados estão na tabela seguinte: 
Produtos Custo/unidade Preço de venda/un. Espaço p/ 
estocagem em m3 
P1 240 300 10 
P2 90 120 1 
P3 300 420 5 
Pede-se: 
(a) Construa o modelo linear do programa, em que, xi representam as decisões de 
compra dos produtos Pi, s1 folga do capital e s2 folga de espaço para estocagem. 
(b) Construa o modelo dual correspondente. 
(c) Resolva pelo simplex o modelo primal. Construa o quadro da solução ótima do 
modelo dual. 
(d) Qual a composição de compra que melhor serve ao distribuidor? 
(e) O que significa a função objetivo dual? 
(f) O que significam as variáveis de decisão dual? 
(g) O que significa as variáveis de folga duais? 
(h) Considere a primeira restrição primal: o que mede seu lado esquerdo? E o direito? 
(i) Considere a segunda restrição dual: o que mede seu lado esquerdo? E o lado direito? 
(j) Qual a conseqüência para o plano ótimo se tivéssemos mais 1m3 de espaço de 
estocagem, a um custo de 20 u.m. ? Por quê? 
RESPOSTAS: 
 2-(b) Modelo dual: Max D = 600y1 + 500y2 + 800y3 
 s.a. 
 50y1 + 20y2 + 10y3 <=20 
 20y1 + 30y2 + 30y3 <=150 
 10y1 + 20y2 + 50y3 <= 240 
 y1, y2, y3 >=0 
 
 2-(c) Solução dual: 
40 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
 
Base y1 y2 y3 t1 t2 t3 Solução 
D 0 315,38 0 1,54 26,15 0 4.320,77 
y1 1 -24,62 0 0,54 -1,85 0 3,46 
y3 0 0,23 1 0,02 -0,01 0 2,69 
t3 0 0,85 0 -0,02 0,04 1 70,77 
 
3-(a) Max L = 60x1 + 30x2 + 120x3 
 s.a. 
 10x1 + x2 + 5x3 <= 100.000 
 240x1 + 90x2 + 300x3 <= 30.000.000 
 x1, x2, x3 >= 0 
 
3-(b) 
Base x1 x2 x3 s1 s2 Solução 
L 240 0 30 30 0 3.000.000 
x2 10 1 5 1 0 100.000 
s2 -660 0 -150 -90 1 21.000.000 
 
ALGORITMO DUAL SIMPLEX 
 
 O problema inicia com uma solução ótima e inviável. As condições de viabilidade e 
otimalidade são: 
1) Condição de viabilidade dual: a variável que sai da base é a que tem valor mais negativo. 
Se todas as variáveis básicas forem não negativas, o algoritmo termina. 
2) Condição de otimalidade dual: min 
𝐶𝑗
𝑎𝑟𝑗
 , 𝑎𝑟𝑗 < 0 , onde: 
 𝐶𝑗 = coeficiente da variável não básica na linha z. 
𝑎𝑟𝑗 = coeficiente da restrição na linha de 𝑥𝑟 (𝑥𝑟 é a variável que sai da base). 
 
 Para iniciar o algoritmo deve-se cumprir 2 requisitos: 
1) A F.O. deve satisfazer a condição de otimalidade do método simplex primal. 
2) Todas as restrições devem ser do tipo (<=) 
 
Obs.: uma restrição do tipo “=” pode ser transformada em duas restrições do tipo “<=” 
e “>=”. 
EXEMPLOS: 
1- A restrição x1 + x2 = 1 é equivalente a 
𝑥1 + 𝑥2 ≤ 1
𝑥1 + 𝑥2 ≥ 1
 𝑜𝑢 
𝑥1 + 𝑥2 ≤ 1
−𝑥1 − 𝑥2 ≤ −1
 
41 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
2- Resolver aplicando o algoritmo dual simplex 
Min z = 3x1 + 2x2 + x3 
s.a. 
 3x1 + x2 + x3 >= 3 
 -3x1 + 3x2 + x3 >= 6 
 x1 + x2 + x3 <= 3 
 x1, x2, x3 >=0 
3- Use o dual simplex em 
Min z = 2x1 + x2 
s.a. 
 4x1 + 3x2 >=6 
 x1 + 2x2 <=3 
 x1 >=0 e x2 >=0 
 
 
 
ANÁLISE DE PÓS-OTIMIZAÇÃO 
 
1) Alterações que afetam a viabilidade: 
1.1) Alterações no lado direito das restrições. 
EXEMPLO: considere o problema da Star e Cia, cujo modelo é: 
 Max Receita (R) = 3x1 + 2x2 + 5x3 
 s.a. 
 x1 + 2x2 + x3 <= 430 (operação 1) 
 3x1 + 2x3 <= 460 (operação 2) 
 x1 + 4x2 <= 420 (operação 3) 
 x1, x2, x3 >=0, onde: 
x1 = quantidade de caminhões de brinquedo. 
x2 = quantidade de trens de brinquedo. 
x3 = quantidade de carros de brinquedo. 
 
QUADRO ÓTIMO : 
Base x1 x2 x3 x4 x5 x6 Solução 
R 4 0 0 1 2 0 1350 
x2 -1/4 1 0 1/2 -1/4 0 100 
x3 3/2 0 1 0 1/2 0 230 
x6 2 0 0 -2 1 1 20 
 
Onde: x4, x5 e x6 são as variáveis de folga das restrições 1, 2 e 3 respectivamente. 
 
 Suponha que a fábrica queira aumentar a capacidade diária das operações1, 2 e 3 em 
40%. Esta alteração afetará a receita? 
SOLUÇÃO: 
42 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
Aumentando-se em 40% as disponibilidades iniciais 
430
460
420
 em 40% obtém-se: 
602
644
588
 . Como 
visto anteriormente, pode-se calcular o lado direito das restrições usando a matriz inversa 
obtida no quadro ótimo. Assim: 
 
𝑥2
𝑥3
𝑥6
 = 
1/2 −1/4 0
0 1/2 0
−2 1 1
 . 
602
644
588
 = 
140
322
28
 , solução viável com R = 3.0 + 2.140 + 5.322 
=1890 
 
 
 Agora, suponha que 20 minutos da operação 3 sejam transferidos para a operação 1, de 
forma que as disponibilidades passam a ser: 
450
460
400
 . Ache a solução ótima. 
SOLUÇÃO: 
 
 
𝑥2
𝑥3
𝑥6
 = 
1/2 −1/4 0
0 1/2 0
−2 1 1
 . 
450
460
400
 = 
110
230
−40
 , a solução é inviável (x6 < 0). No quadro ótimo do 
problema inicial, alterar R e a coluna das disponibilidades dos recursos. Em seguida usar o dual 
simplex. 
R = 3.0 + 2.110 + 5.230 = 1370. 
 
Base x1 x2 x3 x4 x5 x6 Solução 
R 4 0 0 1 2 0 1370 
x2 -1/4 1 0 1/2 -1/4 0 110 
x3 3/2 0 1 0 1/2 0 230 
x6 2 0 0 -2 1 1 -40 
 
Aplicando o algoritmo do dual simplex, obtém-se o seguinte quadro ótimo: 
 
Base x1 x2 x3 x4 x5 x6 Solução 
R 5 0 0 0 5/2 ½ 1350 
x2 1/4 1 0 0 0 ¼ 100 
x3 3/2 0 1 0 1/2 0 230 
x4 -1 0 0 1 -1/2 -1/2 20 
 
Permanecendo a solução ótima do modelo original. 
 
1.2) Adição de novas restrições. 
EXEMPLO: considerar o problema da Star e Cia. Suponha a introdução de uma quarta operação 
com capacidade diária de 500 minutos. A restrição para a quarta operação é 3x1 + x2 + x3 <= 
500. Esta nova restrição alterará a solução ótima? 
SOLUÇÃO: 
 Substituindo a solução x1 = 0, x2 = 100 e x3 = 230 na quarta restrição, vem: 3.0 + 100 
+ 230 = 330 <= 500 (restrição satisfeita). Conclui-se que a restrição é redundante, 
permanecendo inalterada a solução ótima atual. 
 
43 
 
UTFPR - Medianeira Pesquisa Operacional 1 Levi Lopes Teixeira 
 Agora, suponha para a operação 4 a seguinte restrição: 3x1 + 3x2 + x3 <= 500. Obtenha 
a nova solução ótima. 
SOLUÇÃO: 
 A restrição não é redundante, pois 3x1 + 3x2 + x3 <= 500 não é satisfeita para x1 = 0, 
x2 = 100 e x3 = 230. Seja x7 a variável de folga da quarta restrição, assim tem-se: 3x1 + 3x2 + 
x3 + x7 = 500. Inserindo a restrição no quadro ótimo do problema original, obtém-se: 
Base x1 x2 x3 x4 x5 x6 x7 Solução 
R 4 0 0 1 2 0 0 1350 
x2 -1/4 1 0 1/2 -1/4 0 0 100 
x3 3/2 0 1 0 1/2 0 0 230 
x6 2 0 0 -2 1 1 0 20 
x7 3 3 1 0 0 0 1 500 
 
Observa-se no quadro que as colunas das variáveis x2 e x3 devem ser “arrumadas”, de 
forma que na linha de x7 apareçam zeros nas colunas de x2 e x3. Para tanto, deve-se efetuar a 
seguinte operação: nova linha de x7 = linha de x7 atual – [3.(linha de x2) + linha de x3]. Assim, 
obtém-se o quadro: 
 
 
Base x1 x2 x3 x4 x5 x6 x7 Solução 
R 4 0 0 1 2 0 0 1350 
x2 -1/4 1 0 1/2 -1/4 0 0 100 
x3 3/2 0 1 0 1/2 0 0 230 
x6 2 0 0 -2