AULAS DE PO 1

Prévia do material em texto

AULA 01 – PROGRAMAÇÃO LINEAR.
AULA 02 - FORMULAÇÃO DE PPL.
AULA 03 - RESOLUÇÃO DE PPL NO EXCEL.
AULA 04 - SOLUÇÃO GRÁFICA DE PPL.
AULA 05 - SOLUÇÃO GRÁFICA DE PPL NO APLICATIVO COMPUTACIONAL TORA.
AULA 06 - SOLUÇÕES BÁSICAS DE UM SISTEMA DE EQUAÇÕES LINEARES.
AULA 07 - ALGORITMO SIMPLEX (FORMA TABULAR).
AULA 08 - ALGORITMO SIMPLEX (TORA E 2 FASES).
AULA 09 - ALGORITMO SIMPLEX (2 FASES).
AULA 10 - RESOLUÇÃO DE PPL COM O APLICATIVO LINGO.
AULA 11 - RESOLUÇÃO DE PPL COM O LINGO E CASOS ESPECIAIS.
AULA 12 - DUALIDADE.
AULA 13 - ALGORITMO DUAL SIMPLEX.
AULA 14 - ANÁLISE DE SENSIBILIDADE (OPERAÇÕES MATRICIAIS).
AULA 15 - ANÁLISE DE SENSIBILIDADE (FAIXA DE VIABILIDADE)
AULAS DE PESQUISA OPERACIONAL I . PROF.: LEVI LOPES TEIXEIRA
AULA 16 - ANÁLISE DE SENSIBILIDADE (FAIXA DE OTIMALIDADE).
AULA 17 - ANÁLISE DE SENSIBILIDADE (CUSTO REDUZIDO0).
AULA 18 - ANÁLISE DE SENSIBILIDADE (EXCEL E LINGO).
AULA 19 - MÉTODO SIMPLEX REVISADO.
AULA 20 - PROBLEMAS DE TRANSPORTE.
AULA 21 - PROBLEMAS DE TRANSPORTE (APERFEIÇOAMENTO DE SOLUÇÃO BÁSICA).
AULA 22 - PROBLEMAS DE TRANSPORTE (EXCEL, LINGO E TORA).
AULA23 - PROBLEMAS DE DESIGNAÇÃO.
AULA 24 - PROBLEMAS DE DESIGNAÇÃO (MÉTODO HÚNGARO).
AULA25 - NOÇÕES BÁSICAS DE GRAFOS E PROBLEMA DO CAMINHO MÍNIMO.
AULA 26 - PROBLEMA DO CAMINHO MÍNIMO ( ALGORITMO DE FLOYD).
AULA 27 - PROBLEMA DO CAMINHO MÍNIMO (EXCEL E TORA).
AULA 28 - ÁRVORE GERADORA MÍNIMA.
AULA 29 - PROBLEMA DO FLUXO MÁXIMO.
AULAS DE PESQUISA OPERACIONAL I . PROF.: LEVI LOPES TEIXEIRA
AULA 01 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
PESQUISA OPERACIONAL É UMA FERRAMENTA DE APOIO À DECISÃO ESTRUTURADA.
EX.: ALOCAÇÃO DE RECURSOS LIMITADOS NA ADMINISTRAÇÃO DA PRODUÇÃO.
NA CLASSIFICAÇÃO DO CNPQ A PO ABRANGE AS SEGUINTES ÁREAS:
1)PROCESSOS ESTOCÁSTICOS E TEORIAS DAS FILAS;
2)PROGARAMAÇÃO LINEAR, NÃO-LINEAR, MISTA E DINÂMICA;
3)SÉRIES TEMPORAIS;
4)TEORIA DOS GRAFOS;
5)TEORIA DOS JOGOS.
AULA 01 – PESQUISA OPERACIONAL I . PROF.: LEVI LOPES TEIXEIRA
PROGRAMAÇÃO LINEAR (PL)
PROBLEMAS DE PROGRAMAÇÃO LINEAR (PPL): SÃO PROBLEMAS DE OTIMIZAÇÃO COMPOSTOS POR FUNÇÕES OBJETIVO E RESTRIÇÕES LINEARES.
MODELO LINEAR:
AULA 01 – PESQUISA OPERACIONAL I . PROF.: LEVI LOPES TEIXEIRA
PROPRIEDADES DA PROGRAMAÇÃO LINEAR
1)PROPORCIONALIDADE: A CONTRIBUIÇÃO DE CADA VARIÁVEL DE DECISÃO É DIRETEAMENTE PROPORCIONAL AO SEU VALOR.
EX.: MIN CUSTO = 2X1 + 4X2. VARIAÇÕES UNITÁRIAS EM X1 E X2 IMPLICAM EM VARIAÇÕES NO CUSTO IGUAIS A 2 E 4, RESPECTIVAMENTE.
2)ADITIVIDADE: AS VARIÁVEIS DE DECISÃO SÃO INDEPENDENTES, SENDO PERMITIDO ENTRE ELAS APENAS AS OPERAÇÕES DE ADIÇÃO E SUBTRAÇÃO.
CONTRA EX.: MIN CUSTO = 2X1X2 + 4/X2.
3)CERTEZA: OS COEFICIENTES DO MODELO LINEAR SÃO CONTANTES CONHECIDAS.
EX.: MAX RECEITA = 4X1 + 6X2. NO CASO DE X1 REPRESENTAR A QUANTIDADE VENDIDA DE UM DETERMINADO PRODUTO, 4 (VALOR FIXO) É O SEU PREÇO DE VENDA. MAS, EM PROBLEMAS REAIS É PROVÁVEL QUE ESTE VALOR SOFRA VARIAÇÕES.
AULA 01 – PESQUISA OPERACIONAL I . PROF.: LEVI LOPES TEIXEIRA
FORMULAÇÃO DE PPL
DEVE-SE ESTABELECER:
1)VARIÁVEIS DE DECISÃO (): RELATIVO AO QUE SE PODE CONTROLAR E DESEJA-SE DETERTMINAR.
2)FUNÇÃO OBJETIVO (): QUE DEVE SER MAXIMIZADA OU MINIMIZADA.
3)RESTRIÇÕES (): FUNÇÕES LIMITADAS POR UM PARÂMETRO b (QUE PODE SER A QUANTIDADE EM TONELADAS DO RECURSO SOJA, POR EXEMPLO).
AULA 01 – PESQUISA OPERACIONAL I . PROF.: LEVI LOPES TEIXEIRA
FORMULAÇÃO DE PPL (EXEMPLOS)
1) Uma companhia de mobília produz mesas e cadeiras como parte de sua linha de móveis de jardim. A tabela abaixo mostra os recursos consumidos e os lucros de cada produto. Por simplicidade, assumiremos que somente 2 recursos são consumidos para produzir os móveis de jardim: madeira (310 metros de placa em estoque) e trabalho (113 horas disponíveis). O proprietário deseja determinar quantas mesas e cadeiras deveriam ser feitas para maximizar os lucros.
	Recurso\un.	Mesa	Cadeira	Qtde. disponível
	Madeira(m de placa)	30	20	310
	Trabalho(horas)	5	10	113
	Lucro($)	6	8	 
AULA 01 – PESQUISA OPERACIONAL I . PROF.: LEVI LOPES TEIXEIRA
FORMULAÇÃO DE PPL (EXEMPLOS)
SOLUÇÃO EXEMPLO 1:
1) VARIÁVEIS DE DECISÃO:
X1 = QUANTIDADE MESAS PRODUZIDAS.
X2 = QUANTIDADE DE CADEIRAS PRODUZIDAS
2) FUNÇÃO OBJETIVO:
MAX LUCRO = 6X1 + 8X2 
30X1 + 20X2 <= 310 : RECURSO MADEIRA.
3) RESTRIÇÕES:
5X1 + 10X2 <= 113 : RECURSO TRABALHO.
X1, X2 >= 0 : VARIÁVEIS NÃO-NEGATIVAS.
AULA 01 – PESQUISA OPERACIONAL I . PROF.: LEVI LOPES TEIXEIRA
FORMULAÇÃO DE PPL (EXEMPLOS)
SOLUÇÃO EXEMPLO 1:
MODELO LINEAR:
MAX LUCRO = 6X1 + 8X2 
S.A.
30X1 + 20X2 <= 310
5X1 + 10X2 <= 113
X1, X2 >= 0
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 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.
9
AULA 01 – PESQUISA OPERACIONAL I . PROF.: LEVI LOPES TEIXEIRA
FORMULAÇÃO DE PPL (EXEMPLOS)
SOLUÇÃO EXEMPLO 2:
VARIÁVEIS DE DECISÃO:
X1 = QUANTIDADE PRODUZIDA DO PRODUTO 1 – P1
X2 = QUANTIDADE PRODUZIDA DO PRODUTO 2 – P2
MODELO LINEAR:
MAX = 100X1 + 150X2
S.A. 
2X1 + 3X2 <= 120 : TEMPO EM HORAS.
X1 <= 40 : DEMANDA DE P1.
X2 <= 30 : DEMANDA DE P2.
X1,X2 >= 0
AULA 01 – PESQUISA OPERACIONAL I . PROF.: LEVI LOPES TEIXEIRA
FORMULAÇÃO DE PPL (EXEMPLOS)
3-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 para obter o lucro máximo? Construa o modelo do problema.
SOLUÇÃO EX 3. MODELO LINEAR:
MAX LUCRO = 20X1 + 10X2 + 30X3
S.A. X1 = 200 
 X2 >= 100 
 X3 <= 200
 X1 + X2 + X3 <= 800
 X1,X2,X3 >=0
X1, X2, X3 = QUANTIDADE DE CAIXAS DE LARANJAS, PESSÊGOS E TANGERINAS, RESPECTIVAMENTE. 
OBS.: PODE SER FEITO COM DUAS VARIÁVEIS.
AULA 01 – PESQUISA OPERACIONAL I . PROF.: LEVI LOPES TEIXEIRA
FORMULAÇÃO DE PPL (EXEMPLOS)
4- Um sapateiro trabalha 10 horas por dia e faz 6 sapatos por hora, se fizer somente sapatos, e 5 cintos por hora, se fizer somente cintos. Ele gasta 2 peças de couro para fabricar uma unidade de sapato e 1 peça de couro para fabricar um cinto. O total disponível de couro é de 60 peças diárias. O lucro unitário para sapatos e cintos é R$ 6 e R$ 4, respectivamente. Quantos sapatos e cintos devem ser fabricados, respeitando a disponibilidade dos recursos, para maximizar o lucro diário do sapateiro. 
Solução ex. 4.
MODELO LINEAR:
MAX LUCRO = 6X1 + 4X2
S.A. 2X1 + X2 <= 60 : COURO.
 5X1 + 6X2 = 300 : TEMPO (X1/6 + X2/5 = 10)
 X1, X2 >=0
X1 = QUANTIDADE DE SAPATOS PRODUZIDOS.
X2 = QUANTIDADE DE CINTOS PRODUZIDOS.
AULA 02 – PESQUISA OPERACIONAL I . PROF.: LEVI LOPES TEIXEIRA
FORMULAÇÃO DE PPL (EXEMPLOS)
Problemas de transporte.
Suponha que existam m origens e n destinos para um produto e que o custo de transportar uma unidade desse produto da origem i para o destino j é Cij. Além disso, a oferta do produto na origem i é ai e a demanda do produto no destino j é bj. Deseja-se minimizar o custo de transporte do produto de forma que as demandas sejam atendidas.
MODELO LINEAR: 
 
 
 
 
 
 
AULA 02 – PESQUISA OPERACIONAL I . PROF.: LEVI LOPES TEIXEIRA
FORMULAÇÃO DE PPL (EXEMPLOS)
1) Uma companhia faz esquis em 3 fábricas através do mundo. As fábricas suprem 4 depósitos que distribuem os esquis diretamente às lojas. O problema é determinar quantos pares deesquis devem ser transportados de cada fábrica para os vários depósitos para minimizar o custo total. 
Quadro com os custos unitários:
	 	Frankfurt	New York	Phoenix	Yokohama	Fonte
	Rio 	19	17	3	21	100
	Seoul	15	21	18	6	300
	Telaviv	11	14	15	22	200
	Demanda	150	100	200	150	600
AULA 02 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
FORMULAÇÃO DE PPL (EXEMPLOS)
SOLUÇÃO EXEMPLO 1:
VARIÁVEIS DE DECISÃO:
Xij = QUANTIDADE DE ESQUIS TRANSPORTADA DA ORIGEM i PARA O DESTINO j, COM i = 1,2,3 E j = 1,2,...,4.
MODELO LINEAR:
MIN CUSTO = 19X11 + 17X12 + ... + 22X34
S.A. 
X11 + X12 + X13 + X14 = 100 : OFERTA RIO.
X21 + X22 + X23 + X24 = 300 : OFERTA SEOUL.
X31 + X32 + X33 + X34 = 200 : OFERTA TELAVIV.
X11 + X21 + X31 = 150 : DEMANDA FRANKFURT.
X12 + X22 + X32 = 100 : DEMANDA NEW YORK.
X13 + X23 + X33 = 200 : DEMANDA PHOENIX.
X14 + X24 + X34 = 150 : DEMANDA YOKOHAMA.
Xij >= 0, i = 1,2,3 E j = 1,2,...,4
AULA 02 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
FORMULAÇÃO DE PPL (EXEMPLOS)
Problema de Mistura.
Seja n o número de ingredientes que podem ser utilizados na produção de uma mistura e m o número de componentes relevantes para a mistura.
 
 .
 
 
 . z = custo.
AULA 02 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
FORMULAÇÃO DE PPL (EXEMPLOS)
2) Uma agroindústria deve produzir um tipo de ração para determinado animal. Essa ração é produzida pela mistura de farinhas de três ingredientes básicos: osso, soja e resto de peixe. Cada um desses três ingredientes contém diferentes quantidades de dois nutrientes necessários a uma dieta nutricional balanceada: proteína e cálcio. O nutricionista especifica as necessidades mínimas desses nutrientes em 1 kg de ração. Cada ingrediente é adquirido no mercado com um certo custo unitário ($/kg). O quadro abaixo apresenta os dados do problema.
	 	Ingredientes			 
	Nutrientes	Osso	Soja	Peixe	Ração
	Proteína	0,2	0,5	0,4	0,3
	Cálcio	0,6	0,4	0,4	0,5
	Custo ($/kg)	0,56	0,81	0,46	 
Deve-se determinar em que quantidades os ingredientes devem ser misturados de modo a produzir uma ração que satisfaça às restrições nutricionais com mínimo custo.
AULA 02 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
FORMULAÇÃO DE PPL (EXEMPLOS)
SOLUÇÃO EXEMPLO 2:
VARIÁVEIS DE DECISÃO:
MODELO LINEAR:
= custo
S.A. 
 
 
 
AULA 02 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
FORMULAÇÃO DE PPL (EXEMPLOS)
3- Na implantação de uma barragem de grande consumo de concreto, decidiu-se utilizar como fontes de agregados graúdos: Britas graníticas, seixos rolados e pedra britada comercial. Os custos e as composições granulométricas de cada agregado e a composição granulométrica ideal são dados na tabela a seguir.
DESEJA-SE SABER A QUANTIDADE DE BRITAS, SEIXOS E PEDRAS (EM m3) QUE MINIMIZA O CUSTO COM AGREGADOS GRAÚDOS.
AULA 02 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
FORMULAÇÃO DE PPL (EXEMPLOS)
SOLUÇÃO EXEMPLO 3:
AULA 02 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
FORMULAÇÃO DE PPL (EXEMPLOS)
4- Uma companhia despacha caminhões de grãos provenientes de 3 silos para 4 moinhos. Veja a tabela com os custos unitários.
	 	Moinho 1	Moinho 2	Moinho 3	Moinho 4	Oferta(ton)
	Silo 1	10	2	20	11	15
	Silo 2	12	7	9	20	25
	Silo 3	4	14	16	18	10
	Demanda(ton)	5	15	15	15	50
Faça a formulação do modelo linear que determine o plano ótimo que minimiza o custo do transporte. 
AULA 02 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
FORMULAÇÃO DE PPL (EXEMPLOS)
SOLUÇÃO EXEMPLO 4
VARIÁVEIS DE DECISÃO:
Xij = QUANTIDADE DE TONELADAS DE GRÃOS TRANSPORTADA DA ORIGEM i PARA O DESTINO j, COM i = 1,2,3 E j = 1,2,...,4.
MODELO LINEAR:
MIN CUSTO = 10X11 + 2X12 + ... + 18X34
S.A. 
X11 + X12 + X13 + X14 = 15 
X21 + X22 + X23 + X24 = 25 
X31 + X32 + X33 + X34 = 10 
X11 + X21 + X31 = 5 
X12 + X22 + X32 = 15 
X13 + X23 + X33 = 15 
X14 + X24 + X34 = 15 
Xij >= 0, i = 1,2,3 E j = 1,2,...,4
AULA 02 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
FORMULAÇÃO DE PPL (EXEMPLOS)
5- 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.
AULA 02 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
FORMULAÇÃO DE PPL (EXEMPLOS)
SOLUÇÃO EXEMPLO 5.
Max z = 2x1 + 3x2
s.a.
	 x1 + x2 <= 50
	2x1 + 3x2 >= 70
	2x1 >= 20
	 3x2 >= 30
	x1>=0, x2>=0 
VARIÁVEIS DE DECISÃO:
X1= NÚMERO DE HORAS DE ESTUDO RESERVADO P/ A DISCIPLINA D1.
X2= NÚMERO DE HORAS DE ESTUDO RESERVADO P/ A DISCIPLINA D2.
MODELO LINEAR:
AULA 03 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
RESOLUÇÃO DE PPL USANDO O SOLVER DO EXCEL (EXEMPLOS)
1- USE O SOLVER DO EXCEL PARA RESOLVER O SEGUINTE PPL:
Max z = 5x1 + 4x2
 s.a. 
 6x1+4x2 <= 24
 x1 + 2x2 <= 6
 -x1 + x2 <= 1
 x1 e x2 >=0
AULA 03 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
RESOLUÇÃO DE PPL USANDO O SOLVER DO EXCEL (EXEMPLOS)
SOLUÇÃO EXEMPLO 1:
Arraste a fórmula em D2 para as células D3, D4 e D5. Cole a fórmula em D2 na célula D8.
AULA 03 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
RESOLUÇÃO DE PPL USANDO O SOLVER DO EXCEL (EXEMPLOS)
SOLUÇÃO EXEMPLO 1: Na aba “DADOS” clique em “SOLVER” e preencha a janela “PARÂMETROS DO SOLVER” COMO SEGUUE:
AULA 03 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
RESOLUÇÃO DE PPL USANDO O SOLVER DO EXCEL (EXEMPLOS)
SOLUÇÃO EXEMPLO 1:
O campo Submeter às Restrições (SLIDE ANTERIOR) 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 a seguir mostra o preenchimento dos campos da caixa de diálogo Adicionar Restrição.
SOLUÇÃO EXEMPLO 1:
De volta à caixa de diálogo Parâmetros do Solver, clique no botão Resolver para obter a seguinte solução: 
AULA 03 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
RESOLUÇÃO DE PPL USANDO O SOLVER DO EXCEL (EXEMPLOS)
EXEMPLO 2.
AULA 03 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
RESOLUÇÃO DE PPL USANDO O SOLVER DO EXCEL (EXEMPLOS)
Uma companhia faz esquis em 3 fábricas através do mundo. As fábricas suprem 4 depósitos que distribuem os esquis diretamente às lojas. O problema é determinar quantos pares de esquis devem ser transportados de cada fábrica para os vários depósitos para minimizar o custo total. 
Quadro com os custos unitários:
	 	Frankfurt	New York	Phoenix	Yokohama	Fonte
	Rio 	19	17	3	21	100
	Seoul	15	21	18	6	300
	Telaviv	11	14	15	22	200
	Demanda	150	100	200	150	600
SOLUÇÃO EXEMPLO 2:
VARIÁVEIS DE DECISÃO:
Xij = QUANTIDADE DE ESQUIS TRANSPORTADA DA ORIGEM i PARA O DESTINO j, COM i = 1,2,3 E j = 1,2,...,4.
MODELO LINEAR:
MIN CUSTO = 19X11 + 17X12 + ... + 22X34
S.A. 
X11 + X12 + X13 + X14 = 100 : OFERTA RIO.
X21 + X22 + X23 + X24 = 300 : OFERTA SEOUL.
X31 + X32 + X33 + X34 = 200 : OFERTA TELAVIV.
X11 + X21 + X31 = 150 : DEMANDA FRANKFURT.
X12 + X22 + X32 = 100 : DEMANDA NEW YORK.
X13 + X23 + X33 = 200 : DEMANDA PHOENIX.
X14 + X24 + X34 = 150 : DEMANDA YOKOHAMA.
Xij >= 0, i = 1,2,3 E j = 1,2,...,4
AULA 03 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
RESOLUÇÃO DE PPL USANDO O SOLVER DO EXCEL (EXEMPLOS)
AULA 03 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
RESOLUÇÃO DE PPL USANDO O SOLVER DO EXCEL (EXEMPLOS)
Solução ex. 2.
INSERIR NA D1: “=SOMARPRODUTO(K7:N9;C7:F9)”
AULA 03 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRARESOLUÇÃO DE PPL USANDO O SOLVER DO EXCEL (EXEMPLOS)
SOLUÇÃO EXEMPLO 2:
AULA 03 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
RESOLUÇÃO DE PPL USANDO O SOLVER DO EXCEL (EXEMPLOS)
SOLUÇÃO EXEMPLO 2:
AULA 04 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
SOLUÇÃO GRÁFICA DE UM PPL (EXEMPLOS).
1)
Max z = 200x1 + 300x2
s.a.
 (1)	2x1 + x2 <=20
 (2)	4x1 <= 32
 (3)	 x2 <= 10
	x1>=0, x2>=0
 X1
X2
10
(1)
GRADIENTE DE z:
Z = (200,300)
(2)
8
10
(3)
AULA 04 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
SOLUÇÃO GRÁFICA DE UM PPL (EXEMPLOS).
SOLUÇÃO EXEMPLO 1: X1=5; X2=10 e Z=4000 (SOLUÇÃO ÓTIMA)
AULA 04 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
SOLUÇÃO GRÁFICA DE UM PPL (EXEMPLOS).
2)
Max z = 2x1 + 3x2
s.a.
 (1) 	 x1 + x2 <= 50
 (2)	2x1 + 3x2 >= 70
 (3)	2x1 >= 20
 (4)	 3x2 >= 30
	x1>=0, x2>=0 
 X1
X2
50
50
(1)
35
10
70/3
10
(2)
(3)
(4)
Z = (2,3)
Z 
SOLUÇÃO ÓTIMA: X1=10; X2=40 e Z=140 
AULA 04 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
SOLUÇÃO GRÁFICA DE UM PPL (EXEMPLOS).
3) 
MIN Z= 2X1 – X2
S.A. 
(1) X1 + X2 >= 10
(2) -10X1 + X2 <= 10
(3) -4X1+X2 <= 20
(4) X1 + 4X2 >= 20
 X1,X2>=0
10
10
X2
X1
(1)
(2)
(3)
20
20
(4)
Z = (2,-1)
AULA 04 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
SOLUÇÃO GRÁFICA DE UM PPL (EXEMPLOS).
SOLUÇÃO EXEMPLO 3: SOLUÇÃO ILIMITADA.
AULA 04 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
SOLUÇÃO GRÁFICA DE UM PPL (EXEMPLOS).
EXEMPLO 4.
Min z = 30x1 + 20x2
s.a.
(1)	4x1 + x2 >= 20
(2)	x1 + 2x2 >= 10
(3)	x1 >= 2
	x1>=0, x2 >= 0
SOLUÇÃO ÓTIMA:
X1 = 4,29
X2= 2,86
Z = 185,71
AULA 04 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
SOLUÇÃO GRÁFICA DE UM PPL (EXEMPLOS).
EXEMPLO 5.
MAX Z=30X1+20X2
S.A.
(1) X1+X2>=1
(2) X1-X2>=-1
(3) 3X1+2X2<=6
(4) X1-2X2<=1
 X1,X2>=0
A(0,8;1,8) com z=60 e B(1,75;0,375) com z=60 São pontos ótimos. O problema apresenta soluções múltiplas, sendo P=αA+(1-α)B , α [0,1], a solução geral.
A(0,8;1,8) com z=60 e B(1,75;0,375) com z=60 São pontos ótimos. O problema apresenta soluções múltiplas, sendo P=αA+(1-α)B , α [0,1], a solução geral.
41
AULA 05 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
SOLUÇÃO GRÁFICA DE UM PPL COM O APLICATIVO TORA.
TELA INICIAL DO APLICATIVO TORA
AULA 05 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
SOLUÇÃO GRÁFICA DE UM PPL COM O APLICATIVO TORA.
EXEMPLO 1:
Max z = 200x1 + 300x2
s.a.
 (1)	2x1 + x2 <=20
 (2)	4x1 <= 32
 (3)	 x2 <= 10
	x1>=0, x2>=0
NESTE EXEMPLO, ESCOLHE-SE A OPÇÃO “Linear Programming”.
NA TELA SEGUINTE CLIQUE EM “ GO TO”
A SEGUNDA TELA DO TORA TRAZ A LISTA DE OPÇÕES
AULA 05 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
SOLUÇÃO GRÁFICA DE UM PPL COM O APLICATIVO TORA.
EXEMPLO 1:
Max z = 200x1 + 300x2
s.a.
 (1)	2x1 + x2 <=20
 (2)	4x1 <= 32
 (3)	 x2 <= 10
	x1>=0, x2>=0
PREENCHER COM O NÚMERO DE VARIÁVEIS E RESTRÇÕES, 2 E 3, RESPECTIVAMENTE
AULA 05 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
SOLUÇÃO GRÁFICA DE UM PPL COM O APLICATIVO TORA.
SOLUÇÃO EXEMPLO 1:
APÓS PREENCHIMENTO DOS CAMPOS, CLIQUE EM “SOLVE Menu”
AULA 05 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
SOLUÇÃO GRÁFICA DE UM PPL COM O APLICATIVO TORA.
SOLUÇÃO EXEMPLO 1:
NA JANELA “SOLVE/MODIFY” ESCOLHA A OPÇÃO “ Solve Problem – Graphical”
NA TELA SEGUINTE, CLIQUE EM “GO TO”
AULA 05 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
SOLUÇÃO GRÁFICA DE UM PPL COM O APLICATIVO TORA.
SOLUÇÃO EXEMPLO 1:
PARA TRAÇAR O GRÁFICO, CLIQUE AQUI.
AULA 05 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
SOLUÇÃO GRÁFICA DE UM PPL COM O APLICATIVO TORA.
EXEMPLO 2.
Min z = x1 + x2
s.a.
(1)	-2x1 + x2 >=2
(2)	x1 – 2x2 >=2
	x1>=0, x2>= 0
(1)
(2)
-1
-1
2
2
X1
X2
PROBLEMA INVIÁVEL
AULA 05 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
SOLUÇÃO GRÁFICA DE UM PPL COM O APLICATIVO TORA.
EXEMPLO 3.
Max z = x1 + x2
s.a.
(1)	-2x1 + x2 <= 2
(2)	x1 – 2x2 <= 2
(3)	x1 + x2 <= 4
	x1>=0, x2>=0
(1)
(2)
-1
-1
2
2
X1
X2
(3)
4
4
A(2/3;10/3) com z=4 e B(10/3;2/3) com z=4 São pontos ótimos. O problema apresenta soluções múltiplas, sendo P=αA+(1-α)B , α [0,1], a solução geral.
B
A
AULA 05 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
SOLUÇÃO GRÁFICA DE UM PPL COM O APLICATIVO TORA.
EXEMPLO 4.
O Governo Federal colocou 20 hectares 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 hectare 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?
AULA 05 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
SOLUÇÃO GRÁFICA DE UM PPL COM O APLICATIVO TORA.
SOLUÇÃO EXEMPLO 4:
MODELO LINEAR:
X1=QUANTIDADE DE HECTARES DE SOJA.
X2=QUANTIDADE DE HECTARES DE ALGODÃO.
MAX Z = 50X1 + 25X2
S.A.
(1) X1+X2<= 20
(2) 20X1+120X2<=1200 
(3) 600X1+200X2<=6000
 X1,X2>=0
(1)
20
20
X1
X2
10
60
(2)
(3)
10
30
SOLUÇÃO ÓTIMA: 
X1=7,06;
X2=8,82;
Z=573,53.
SOLUÇÃO ÓTIMA
AULA 05 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
SOLUÇÃO GRÁFICA DE UM PPL COM O APLICATIVO TORA.
EXEMPLO 5.
MIN Z=X1+3X2
S.A.
(1) 2X1+X2>=10
(2) -X1+X2<=20
(3) X1-2X2<=10
(4) X1+X2<=30
 X1,X2>=0
Solução ótima: A(5,0) com z=5
AULA 06 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
SOLUÇÕES BÁSICAS DE UM SISTEMA DE EQ. LINEARES.
Definição. Dado um sistema linear m x n, m <= n, Ax = b, A ∊ ℝmxn, x ∊ ℝn, b ∊ ℝm, dizemos que uma submatriz B, m x m, com det B ≠ 0 é uma matriz base.
EXEMPLO 1:
ENTÃO, A MATRIZ 
É BASE (det B ≠ 0 ).
AS VARIÁVEIS CORRESPONDENTES ÀS COLUNAS DE B (x1 E x3) SÃO DITAS BÁSICAS, ENQUANTO AS OUTRAS (x2 E x4) SÃO AS NÃO-BÁSICAS.
DENOTANTO AS VARIÁVEIS BÁSICAS POR XB E AS NÃO-BÁSICAS POR XN, TEMOS: 
ENTRE OUTRAS.
AULA 06 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
Definição. Dado um sistema de equações lineares, m x n, m <=n, Ax = b, A ∊ ℝmxn, x ∊ ℝn, b ∊ ℝm , diz-se que x* ∊ ℝn , tal que Ax* = b é uma solução básica se os valores das variáveis não-básicas forem zero .
NO EXEMPLO 1:
UMA DAS SOLUÇÕES BÁSICAS É:
SENDO:
O número máximo de soluções básicas é dado por 
Neste exemplo, temos:
Uma solução básica é viável se os valores das variáveis básicas forem maiores ou iguais a zero.
SOLUÇÕES BÁSICAS DE UM SISTEMA DE EQ. LINEARES.
AULA 06 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
FORMA PADRÃO DE UM PPL
Dizemos que um PPL na forma
Está na forma PADRÃO.
FORMA CACÔNICA DE UM PPL
Dizemos que um PPL na forma
Está na forma CANÔNICA.
PARA PASSAR UM PPL NA FORMA PADRÃO PARA A FORMA CANÔNICA, BASTA FAZER A INSERÇÃO DE VARIÁVEIS DE FOLGA.
EXEMPLO 2:
Max z = 2x1 + 3x2
 s.a. 
 x1 + 5x2 <=20
 2x1 + x2 <= 10
 x1>=0 e x2 >= 0
INSERINDO AS FOLGAS x3 E x4, TEMOS:
FORMA CANÔNICA
Max z = 2x1 + 3x2
 s.a. 
 x1 + 5x2 + x3=20
 2x1 + x2 + x4= 10
 x1,x2,x3,x4>=0
SOLUÇÕES BÁSICAS DE UM SISTEMA DE EQ. LINEARES.
AULA 06 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
O conjunto de soluções viáveis de um PPL é um conjunto convexo. Pode ser provado que se o PPL admitir solução ótima, esta será atingida para, ao menos, um vértice do conjunto de soluções viáveis deste PPL. Além disso, um vértice equivale a uma solução básica viável (XB>=0).
SOLUÇÕES BÁSICAS DE UM SISTEMA DE EQ. LINEARES.
EXEMPLO 3: DADO O PPL, RESOLVER GRAFICAMENTE. TRANSFORMARNA FORMA CANÔNICA E ENCONTRAR AS SOLUÇÕES BÁSICAS.
Max z = 2x1 + 3x2
 s.a. 
(1) x1 + 5x2 <=20
(2) 2x1 + x2 <= 10
 x1>=0 e x2 >= 0
AULA 06 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
SOLUÇÕES BÁSICAS DE UM SISTEMA DE EQ. LINEARES.
X1
X2
20
5
4
10
(1)
(2)
REGIÃO VIÁVEL
C
B
A
D
E
F
OS PONTOS A,B,C,D,E e F SÃO AS SOLUÇÕES BÁSICAS. SENDO: A,B,D e E VIÁVEIS. A SOLUÇÃO ÓTIMA É O PONTO D(10/3, 10/3). 
SOLUÇÃO EXEMPLO 3.
AULA 06 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
SOLUÇÃO DO EXEMPLO 3: FORMA CANÔNICA E SOLUÇÕES BÁSICAS.
FORMA CANÔNICA
Max z = 2x1 + 3x2
 s.a. 
 x1 + 5x2 + x3=20
 2x1 + x2 + x4= 10
 x1,x2,x3,x4>=0
Onde x3 e x4 são as
Variáveis de folga.
SOLUÇÕES BÁSICAS (X):
1) Com XB =(x3,x4)’ e XN =(x1,x2)’, vem X = (x1,x2,x3,x4)’=(0,0,20,10)’ e z=2*0+3*0 =0
2) Com XB =(x2,x4)’ e XN =(x1,x3)’, vem X = (x1,x2,x3,x4)’=(0,4,0,6)’ e z=2*0+3*4=12
3) Com XB =(x2,x3)’ e XN =(x1,x4)’, vem X = (x1,x2,x3,x4)’=(0,10,-30,0)’. Ponto F (inviável)
4) Com XB =(x1,x4)’ e XN =(x2,x3)’, X = (x1,x2,x3,x4)’=(20,0,0,-30)’. C (inviável) 
5) Com XB =(x1,x3)’ e XN =(x2,x4)’, vem X = (x1,x2,x3,x4)’=(5,0,15,0)’ e z=10 
6) Com XB =(x1,x2)’ e XN =(x3,x4)’, vem X =(x1,x2,x3,x4)’=(10/3,10/3,0,0)’ e z=50/3. 
Como o maior valor de z é 50/3, a solução básica ótima é X =(x1,x2,x3,x4)’=(10/3,10/3,0,0)’ 
SOLUÇÕES BÁSICAS DE UM SISTEMA DE EQ. LINEARES.
AULA 06 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
EXEMPLO 4. DADO O PPL, RESOLVER GRAFICAMENTE. TRANSFORMAR NA FORMA CANÔNICA E ENCONTRAR AS SOLUÇÕES BÁSICAS.
Max z = 5x1 + 4x2
 s.a. 
(1) 6x1 + 4x2 <=24
(2) x1 + 2x2 <= 6
(3) -x1 + x2 <= 1
 x1>=0 e x2 >= 0
SOLUÇÕES BÁSICAS DE UM SISTEMA DE EQ. LINEARES.
AULA 06 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
SOLUÇÃO EXEMPLO 4: FORMA CANÔNICA E SOLUÇÕES BÁSICAS.
FORMA CANÔNICA
Max z = 5x1 + 4x2
 s.a. 
(1) 6x1 + 4x2 +x3=24
(2) x1 + 2x2 +x4= 6
(3) -x1 + x2+ x5 = 1
 x1,x2,x3,x4,x5>=0
Onde: x3, x4 e x5 são as variáveis de folga.
SOLUÇÕES BÁSICA (X):
X=(0,0,24,6,1)’.
X=(0,6,0,-6,-5)’ (inviável). 
3) X=(0,3,12,0,-2)’ (inviável). 
4) X=(0,1,20,4,0)’. 
X=(4,0,0,2,5)’. 
X=(6,0,-12,0,7)’ (inviável). 
X=(-1,0,30,7,0)’ (inviável). 
X=(3,3/2,0,0,5/2)’ (SOLUÇÃO ÓTIMA). 
X=(2,3,0,-2,0)’. 
X=(5/2,7/2,-5,0,0)’ (inviável). 
SOLUÇÕES BÁSICAS DE UM SISTEMA DE EQ. LINEARES.
AULA 06 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
EXEMPLO 5: UTILIZE SOLUÇÕES BÁSICAS PARA ENCONTRAR A SOLUÇÃO ÓTIMA PARA O SEGUINTE PPL: 
Max z = x1 + x2 + x3
 s.a. 
 x1 + 2x2+x3 <=10
 2x1 + 3x3 <= 20
 x1, x2, x3 >= 0
SOLUÇÃO ÓTIMA: x1=10; x2=0; x3=0 E z=10
SOLUÇÕES BÁSICAS DE UM SISTEMA DE EQ. LINEARES.
AULA 07 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).
O ALGORITMO SIMPLEX PESQUISA A SOLUÇÃO ÓTIMA DE UM PPL ENTRE AS SOLUÇÕES BÁSICAS VIÁVEIS DO PROBLEMA. O ALGORITMO É CONSTITUIDO DE REGRAS QUE AGILIZAM A BUSCA DO ÓTIMO.
Etapas do Método Simplex.
 
Etapa 1. Determine uma solução básica inicial.
 
Etapa 2. Selecione uma variável para entrar na base usando a condição de otimalidade. Pare aqui se não houver nenhuma variável para entrar na base; a última solução é a ótima.. Senão passe para a etapa 3.
 
Etapa 3. Selecione uma variável para sair da base usando a condição de viabilidade.
 
Etapa 4. Determine a nova solução básica. Passe para a etapa 2.
AULA 07 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).
Seja o PPL formulado da seguinte maneira:
Adicionando as variáveis de folga e escrevendo as equações em um quadro, temos:
AULA 07 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).
	 							
	-z							
								
								
								
								
								
Onde 
 são variáveis básicas, que no caso do quadro inicial correspondem às folgas 
, respectivamente.
AULA 07 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).
Critério de otimalidade.
Basta verificar se na segunda linha (-z) do quadro existe algum elemento positivo. Se não existir, esta solução será ótima.
 
Critério de viabilidade.
Se existir elemento positivo na linha –z, escolhe-se o mais positivo (suponha ), então a variável correspondente () deverá entrar na base. Para determinar a variável que sai da base, busca-se o mínimo entre os quocientes:
Se 
AULA 07 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).
Conclui-se que é a variável que deve sair da base. O elemento pivô () está na intersecção da linha (linha pivô) correspondente à variável ( que sai da base e a coluna (coluna pivô) correspondente à variável ( que entra na base. A troca entre as variáveis é baseada nas operações de Gauss-Jordan. Onde, por operações elementares sobre as linhas da tabela, os elementos da coluna pivô são transformados em zero, exceto que é transformado em 1.
 
Observação: problemas de minimização podem ser transformados em maximização com a multiplicação da F.O. por -1. Desta forma, mantém para este tipo de problema o critério de otimalidade.
AULA 07 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).
EXEMPLO 1. DADO O PPL, RESOLVER GRAFICAMENTE E COM A APLICAÇÃO DO ALGORITMO SIMPLEX.
Max z = 5x1 + 4x2
 s.a. 
(1) 6x1 + 4x2 <=24
(2) x1 + 2x2 <= 6
(3) -x1 + x2 <= 1
 x1>=0 e x2 >= 0
EXEMPLO 2: RESOLVER O PPL:
Max z = 5x1 + 4x2
 s.a. 
(1) 6x1 + 4x2 <=24
(2) x1 + 2x2 <= 6
(3) -x1 + x2 <= 1
 x1>=0 e x2 >= 0
AULA 07 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).
Max -z + 5x1 + 4x2 = 0
 s.a. 
(1) 6x1 + 4x2 +s1 =24
(2) x1 + 2x2 +s2 = 6
(3) -x1 + x2 +s3 = 1
 x1,x2,s1,s2>=0 
PREPARANDO A F.O. E INSERINDO AS VARIÁVEIS DE FOLGA s1,s2 E s3
	 	x1	x2	s1	S2	s3	b
	-Z	5	4	0	0	0	0
	s1	6	4	1	0	0	24
	s2	1	2	0	1	0	6
	s3	-1	1	0	0	1	1
QUADRO INICIAL
A PRIMEIRA COLUNA DO QUADRO, COM EXCEÇÃO DE –Z, É FORMADO PELAS VARIÁVEIS BÁSICAS s1, s2 E s3. AS NÃO-BÁSICAS SÃO x1 E x2. A ÚLTIMA COLUNA TRAZ A SOLUÇÃO PARA Z E VARIÁVEIS BÁSICAS.
SOLUÇÃO BÁSICA: x1=x2=0; s1=24; s2=6 E s3=1.
AULA 07 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).
	 	x1	x2	s1	s2	s3	b
	-Z	5	4	0	0	0	0
	s1	6	4	1	0	0	24
	s2	1	2	0	1	0	6
	s3	-1	1	0	0	1	1
QUADRO INICIAL
SOLUÇÃO EXEMPLO 2:
CONDIÇÃO DE OTIMALIDADE: A SOLUÇÃO OBTIDA COM O QUADRO INICIAL NÃO É ÓTIMA, POIS A LINHA –Z TRAZ COEFICIENTES POSITIVOS. ENTÃO, VARIÁVEIS NÃO-BÁSICAS PODEM ENTRAR NA BASE PARA QUE OCORRA MELHORIAS EM Z. ESCOLHE-SE PARA ENTRAR NA BASE A VARIÁVEL COM MAIOR COEFICIENTE POSITIVO, NESTE CASO ESCOLHE-SE X1, COM COEFICIENTE IGUAL A 5, PARA ENTRAR NA BASE.
CONDIÇÃO DE VIABILIDADE: ESTA REGRA É USADA PARA DEFINIR A VARIÁVEL QUE SAI DA BASE. PARA TANTO, DIVIDE-SE A COLUNA b PELOS COEFICIENTES POSITIVOS DA COLUNA DA VARIÁVEL QUE ENTRARÁ NA BASE (X1), EXCETO VALORES DA LINHA –Z. O MENOR DOS QUOCIENTES INDICARÁ A VARIÁVEL QUE DEVE SAIR DA BASE. ASSIM: 
ESTE QUOCIENTE CORRESPONDE À LINHA DA VARIÁVEL BÁSICA s1. PORTANTO, s1 SAI DA BASE E 6 É O PIVÔ.
AULA 07 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).
	 	x1	x2	s1	s2	s3	b
	-Z	5	4	0	0	0	0
	s1	6	4	1	0	0	24
	s2	1	2	0	1	0	6
	s3	-1	1	0	0	1	1
	 	x1	x2	s1	s2	s3	b
	-Z	5	4	0	0	0	0
	s1	1	2/3	1/6	0	0	4
	s2	1	2	0	1	0	6
	s3	-1	1	0	0	1	1
FAZER O PIVÔ IGUAL A 1, DIVIDINDO A LINHA 2 (L2) POR 6
A COLUNA DA VARIÁVEL QUE ENTRA NA BASE (X1) É FORMADA POR ZEROS, EXCETO O PIVÔ QUE É IGUAL A 1. PARA TANTO, FAZ-SE AS OPERAÇÕES:
	 	x1	x2	s1	s2	s3	b
	-Z	0	2/3	-5/6	0	0	-20
	x1	1	2/3	1/6	0	0	4
	s2	0	4/3	-1/6	1	0	2
	s3	0	5/3	1/6	0	1	5
A SOLUÇÃO BÁSICA NESTA ITERAÇÃO É: x1=4; s2=2; s3=5 E x2=s1=0.
A LINHA –Z AINDA APRESENTA COEFICIENTE POSITIVO. PORTANDO ESTA SOLUÇÃO NÃO É ÓTIMA E X2 ENTRA NA BASE.
AULA 07 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).x1	x2	s1	s2	s3	b
	-Z	0	2/3	-5/6	0	0	-20
	x1	1	2/3	1/6	0	0	4
	s2	0	4/3	-1/6	1	0	2
	s3	0	5/3	1/6	0	1	5
ASSIM, s2 SAI DA BASE E 4/3 É O PIVÔ. TRANSFORMAR O PIVÔ EM 1, A PARTIR DA OPERAÇÃO (*):
	 	x1	x2	s1	s2	s3	b
	-Z	0	2/3	-5/6	0	0	-20
	x1	1	2/3	1/6	0	0	4
	s2	0	1	-1/8	3/4	0	3/2
	s3	0	5/3	1/6	0	1	5
Critério de viabilidade.
AULA 07 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).
	 	x1	x2	s1	s2	s3	b
	-Z	0	2/3	-5/6	0	0	-20
	x1	1	2/3	1/6	0	0	4
	s2	0	1	-1/8	3/4	0	3/2
	s3	0	5/3	1/6	0	1	5
FAZER, PARA X2 ENTRAR NA BASE, AS SEGUINTES OPEARAÇÕES:
	 	x1	x2	s1	s2	s3	b
	-Z	0	0	-3/4	-1/2	0	-21
	x1	1	0	1/4	-1/2	0	3
	x2	0	1	-1/8	3/4	0	3/2
	s3	0	0	3/8	-5/4	1	5/2
A SOLUÇÃO BÁSICA NESTA ITERAÇÃO É: x1=3; x2=3/2; s3=5/2; E s1=s2=0.
A LINHA –Z NÃO APRESENTA COEFICIENTE POSITIVO. PORTANDO ESTA SOLUÇÃO É ÓTIMA.
SOLUÇÃO EXEMPLO 2:
AULA 07 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).
EXEMPLO 3.
Resolver o PPL
Max z = 3x1 + 5x2
s.a.
 2x1 + 4x2 <=10
 6x1 + x2 <=20
 x1 – x2 <=30
 x1,x2>=0
OBS.: Este exemplo foi resolvido no aplicativo TORA. Onde a solução é ótima quando os coeficientes das variáveis na linha z são não negativos
Para a montagem do quadro simplex inicial, a função objetivo é escrita na forma:
Max z – 3x1 – 5x2 = 0
AULA 07 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).
SOLUÇÃO EXEMPLO 3
SOLUÇÃO ÓTIMA
AULA 08 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).
EXEMPLO 1:
Min z = 3x1 - 4x2 + x3
s.a.
 x1 + x2 + x3 <=10
 2x1 + x2 – x3 <= 20
 x1,x2,x3>=0
TRANSFORMANDO EM UM PROBL. DE MAX., PREPARANDO A F.O. E INSERINDO AS VARIÁVEIS DE FOLGA s1 E s2, OBTEMOS:
MAX z -3x1 + 4x2 - x3=0
s.a.
 x1 + x2 + x3+s1=10
 2x1 + x2 – x3+s2= 20
 x1,x2,x3>=0
	 	x1	x2	x3	s1	S2	b
	Z	-3	4	-1	0	0	0
	s1	1	1	1	1	0	10
	s2	2	1	-1	0	1	20
X2 ENTRA NA BASE.
ASSIM, s1 SAI DA BASE
	 	x1	x2	x3	s1	S2	b
	Z	-7	0	-5	-4	0	-40
	x2	1	1	1	1	0	10
	s2	1	0	-2	-1	1	10
FAZER AS SEGUINTES OPEARAÇÕES:
Obs.:
= 
AULA 08 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).
Min Z= -X1-X2+X3;
S.A.
4X1+2X2+5X3<=10;
X1+X2+3X3<=20;
X1,X2,X3>=0
EXEMPLO 2:
76
AULA 08 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).
ESCOLHA A OPÇÃO “Linear Programming”.
NA TELA SEGUINTE CLIQUE EM “ GO TO”
PREENCHER COM O NÚMERO DE VARIÁVEIS E RESTRÇÕES, 3 E 2, RESPECTIVAMENTE
Resolver o PPL: Min z = 3x1 - 4x2 + x3; s.a. (1) x1 + x2 + x3 <=10;
 (2) 2x1 + x2 – x3 <= 20; x1,x2,x3>=0, COM O “TORA”
SOLUÇÃO
AULA 08 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).
APÓS PREENCHIMENTO DOS CAMPOS, CLIQUE EM “SOLVE Menu”
AULA 08 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).
NA JANELA “SOLVE/MODIFY” ESCOLHA A OPÇÃO “ Solve Problem – Algebric – Iterations – All slack starting solution”
NA TELA SEGUINTE, CLIQUE EM “GO TO”
AULA 08 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).
CLIQUE EM “All Iterations” OU “Next Iterations” para obter uma iteração de cada vez.
AULA 08 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).
SOLUÇÃO ÓTIMA NA SEGUNDA ITERAÇÃO, COM Z= 40.
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. Este tipo de problema pode ser resolvido pelos métodos: M grande e 2 fases. No método do M grande acrescentam-se ao problema 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. A seguir serão apresentados os passos e exemplos para o método das 2 fases.
AULA 08 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).
AULA 08 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).
MÉTODO DAS 2 FASES.
AULA 08 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).
Exemplo 3. Resolver
Max z = x1 + x2 + x3
s.a.
 2x1 + x2 – x3 <= 10
 x1 + x2 + 2x3 >= 20
 2x1 + x2 + 3x3 = 60
 x1, x2, x3 >=0
 
Max z = x1 + x2 + x3
s.a.
(1) 2x1 + x2 – x3+x4 = 10 
(2) x1 + x2 + 2x3 - x5 + a2 = 20 
(3) 2x1 + x2 + 3x3 + a3 = 60 
 x1, x2, x3,x4,x5,a2 e a3 >=0
Solução.
 
Acrescentando as variáveis de folga (x4), excesso (x5) e artificiais (a2 e a3), temos:
Assim, W=a2+a3. Isolando a2 em (2) e a3 em (3), vem: 
W=-3x1-2x2-5x3+x5+80.
Min W=-3x1-2x2-5x3+x5+80 =Max (-W)= 3x1+2x2+5x3-x5-80
AULA 08 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).
Primeira fase (otimização de W).
Montando o quadro inicial, temos:
		x1	x2	x3	x4	x5	a2	a3	Solução
	-z	1	1	1	0	0	0	0	0
	x4	2	1	-1	1	0	0	0	10
	a2	1	1	2	0	-1	1	0	20
	a3	2	1	3	0	0	0	1	60
	W	3	2	5	0	-1	0	0	80
Na linha W o coeficiente mais positivo é o 5. Logo, x3 deve entrar na base. O menor dos quocientes entre é . Logo, a variável a2 deve sair da base e 2 é o pivô. Utilizando as operações de Gauss-Jordan, vem:
		x1	x2	x3	x4	x5	a2	a3	Solução
	-z	0,5	0,5	0	0	0,5	-0,5	0	-10
	x4	2,5	1,5	0	1	-0,5	0,5	0	20
	x3	0,5	0,5	1	0	-0,5	0,5	0	10
	a3	0,5	-0,5	0	0	1,5	-1,5	1	30
	W	0,5	-0,5	0	0	1,5	-2,5	0	30
AULA 09 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).
MÉTODO DAS DUAS FASES.
SOLUÇÃO DO EXEMPLO 3 DA AULA 08
Na linha W o coeficiente mais positivo é o 1,5. Logo, x5 deve entrar na base. O menor dos quocientes entre é . Logo, a variável a3 deve sair da base e 1,5 é o pivô. Utilizando as operações de Gauss-Jordan, vem:
		x1	x2	x3	x4	x5	a2	a3	Sol.
	-z	0,33	0,67	0	0	0	0	-0,33	-20
	x4	2,67	1,33	0	1	0	0	0,33	30
	x3	0,67	0,33	1	0	0	0	0,33	20
	x5	0,33	-0,33	0	0	1	-1	0,67	20
	W	0	0	0	0	0	-1	-1	0
AULA 09 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).
MÉTODO DAS DUAS FASES.
SOLUÇÃO DO EXEMPLO 3 DA AULA 08
O quadro é ótimo para W e W=0. Logo, eliminam-se as variáveis artificiais e inicia-se a segunda fase com a otimização de z.
AULA 09 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).
	Base	x1	x2	x3	x4	x5	Sol.
	-z	0,33	0,67	0	0	0	-20
	x4	2,67	1,33	0	1	0	30
	x3	0,67	0,33	1	0	0	20
	x5	0,33	-0,33	0	0	1	20
MÉTODO DAS DUAS FASES.
SOLUÇÃO DO EXEMPLO 3 DA AULA 08. OTIMIZAÇÃO DE Z.
Na linha -z o coeficiente mais positivo é o 0,67. Logo, x2 deve entrar na base. O menor dos quocientes entre é . Logo, a variável x4 deve sair da base e 1,33 é o pivô. Seguindo, desta forma, até a solução ótima.
AULA 09 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).
MÉTODO DAS DUAS FASES.
SOLUÇÃO DO EXEMPLO 3 DA AULA 08. OTIMIZAÇÃO DE Z.
QUADRO ÓTIMO OBTIDO NO “TORA”.
AULA 09 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).
EXEMPLO 1: USE O MÉTODO 2 FASES PARA RESOLVER O SEGUINTE PPL.
Min z = 4x1 + x2
s.a. 
 (1) 3x1 + x2 = 3
 (2) 4x1 + 3x2 >= 6
 (3) x1 + 2x2 <=4
 x1 e x2 >=0
Solução.
 Transformando em um problema de maximização, acrescentando as variáveis de folga (x3), excesso (x4) e artificiais (a1 e a2), temos:
Max -z = -4x1 - x2
s.a.
(1) 3x1 + x2+a1 = 3 
(2) 4x1 + 3x2 – x4 + a2 = 6 
(3) x1 + 2x2 + x3 = 4 
 x1, x2, x3,x4,a1 e a2>=0
Assim, W=a1+a2. Isolando a1 em (1) e a2 em (2), vem: 
W=-7x1-4x2+x4+9.
Min W=-7x1-4x2+x4+9 =Max (-W)= 7x1+4x2-x4-9.
		x1	x2	x3	x4	a1	a2	Solução
	Z	-4	-1	0	0	0	0	0
	a1	3	1	0	0	1	0	3
	a2	4	3	0	-1	0	1	6
	x3	1	2	1	0	0	0	4
	W	7	4	0	-1	0	0	9
Na linha W o coeficiente mais positivo é o 7. Logo, x1 deve entrar na base. O menor dos quocientes entre é . Logo, a variável a1 deve sair da base e 3 é o pivô. Utilizando as operações de Gauss-Jordan, vem:
AULA 09– PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).
Primeira fase (otimização de W).
Montando o quadro inicial, temos:
AULA 09 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).
Primeira fase (otimização de W).
		x1	x2	x3	x4	a1	a2	Solução
	Z	0	1/3	0	0	4/3	0	4
	x1	1	1/3	0	0	1/3	0	1
	a2	0	5/3	0	-1	-4/3	1	2
	x3	0	5/3	1	0	-1/3	0	3
	W	0	5/3	0	-1	-7/3	0	2
Na linha W o coeficiente mais positivo é o 5/3. Logo, x2 deve entrar na base. O menor dos quocientes entre é . Logo, a variável a2 deve sair da base e 5/3 é o pivô. Utilizando as operações de Gauss-Jordan, vem:
AULA 09 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO SIMPLEX (FORMA TABULAR).
Primeira fase (otimização de W).
		x1	x2	x3	x4	a1	a2	Solução
	Z	0	0	0	1/5	8/5	-1/5	18/5
	x1	1	0	0	1/5	3/5	-1/5	3/5
	x2	0	1	0	-3/5	-4/5	3/5	6/5
	x3	0	0	1	1	1	-1	1
	W	0	0	0	0	-1	-1	0
O quadro é ótimo para W e W=0. Logo, eliminam-se as variáveis artificiais e inicia-se a segunda fase com a otimização de z.
AULA 09 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
Segunda fase (otimização de Z).
		x1	x2	x3	x4	Solução
	Z	0	0	0	1/5	18/5
	x1	1	0	0	1/5	3/5
	x2	0	1	0	-3/5	6/5
	x3	0	0	1	1	1
ALGORITMO SIMPLEX (FORMA TABULAR).
Na linha z o coeficiente mais positivo é o 1/5. Logo, x4 deve entrar na base. O menor dos quocientes entre é . Logo, a variável x3 deve sair da base e 1 é o pivô. 
AULA 09 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
Segunda fase (otimização de Z).
ALGORITMO SIMPLEX (FORMA TABULAR).
		x1	x2	x3	x4	Solução
	Z	0	0	-1/5	0	17/5
	x1	1	0	-1/5	0	2/5
	x2	0	1	3/5	0	9/5
	x4	0	0	1	1	1
AULA 10 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
SIMPLEX 2 FASES NO APLICATIVO “TORA”.
SIGA A SEQUÊNCIA ESTABELECIDA PARA O EXEMPLO DA AULA 8 E NA JANELA “SOLVE/MODIFY” ESCOLHA A OPÇÃO “ Solve Problem – Algebric – Iterations – Two phase method”
AULA 10 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
RESOLUÇÃO DE PPL USANDO O APLICATIVO “LINGO 11.0”
EXEMPLO 2:
Max z = 5x1 + 4x2
 s.a. 
 6x1+4x2 <= 24
 x1 + 2x2 <= 6
 -x1 + x2 <= 1
 x1 e x2 >=0
Para resolver com o auxílio do LINGO um PPL com um número reduzido de variáveis, basta digitar o problema na janela de comandos do aplicativo como mostra a figura abaixo.
SOLVER
AULA 10 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
RESOLUÇÃO DE PPL USANDO O APLICATIVO “LINGO 11.0”
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 abaixo.
AULA 10 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
RESOLUÇÃO DE PPL USANDO O APLICATIVO “LINGO 11.0”
EXEMPLO 3:
Um agricultor pode usar dois diferentes grãos na alimentação de suas galinhas. Os dados estão na tabela baixo:
Determinar o custo mínimo da ração de frango.
AULA 10 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
RESOLUÇÃO DE PPL USANDO O APLICATIVO “LINGO 11.0”
SOLUÇÃO EXEMPLO 3
C=custo total
x1,x2=quantidade em
 Kg dos grãos 1 e 2, 
respectivamente.
 
Modelo:
Min C=0,6x1+0,35x2
s.a.
5x1+7x2>=8
4x1+2x2>=15
2x1+x2>=3
x1,x2 
Objective value: 2.250000
 
 Variable Value Reduced Cost
 X1 3.750000 0.000000
 X2 0.000000 0.5000000E-01
 
 Row Slack or Surplus Dual Price
 1 2.250000 -1.000000
 2 10.75000 0.000000
 3 0.000000 -0.1500000
 4 4.500000 0.000000
AULA 10 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
RESOLUÇÃO DE PPL USANDO O APLICATIVO “LINGO 11.0”
PROGRAMAÇÃO NO LINGO
Esta outra opção do LINGO é recomendada quando o PPL apresenta um grande número de variáveis e restrições. Nesta modalidade as restrições de um mesmo tipo podem ser representadas por apenas uma linha de comandos.
EXEMPLO 4.
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.
AULA 10 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
RESOLUÇÃO DE PPL USANDO O APLICATIVO “LINGO 11.0”
MODELO EXEMPLO 4.
 
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 trens de brinquedo.
x2 = quantidade de caminhões de brinquedo.
x3 = quantidade de carros de brinquedo.
AULA 10 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
RESOLUÇÃO DE PPL USANDO O APLICATIVO “LINGO 11.0”
PROGRAMA EXEMPLO 4: NA JANELA DE COMANDOS DIGITA-SE AS SEGUINTES LINHAS:
AULA 10 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
RESOLUÇÃO DE PPL USANDO O APLICATIVO “LINGO 11.0”
EXEMPLO 4: SEÇÕES DO PROGRAMA.
Na secção SETS estão definidos dois grupos de objetos relacionados (vetor e matriz), sendo matriz derivado de vetor. O grupo vetor tem 3 elementos (posições), os parâmetros b e c e a variável x possuem as mesmas características do grupo vetor. Já a constante a possui as características do grupo derivado matriz. Assim, a é uma matriz 3x3.
	Na secção DATA são apresentados os dados (a, b e c) necessários para a resolução do problema.
	O comando @SUM (função objetivo) soma o produto c(i)*x(i) para todos os membros do grupo vetor.
	O comando @FOR gera 3 restrições (i=1,2 e 3) do tipo: (soma do produto a(i,j)*x(j) <= b(i)).
	Para a execução do programa, basta clicar em solver.
Obs.: os dados podem ser importados ou exportados para planilhas do Excel a partir do comando @OLE (Object Linking and Embedding). 
EXEMPLO 5:
Um fabricante está iniciando a última semana de produção de quatro diferentes modelos de consoles em madeira para aparelhos de televisão, designados respectivamente, I, II, III e IV. Cada um deles deve ser montado e em seguida decorado. Os modelos necessitam, respectivamente de 4, 5, 3 e 5 horas para montagem e de 2, 1, 5 e 3 horas para decoração. Os lucros sobre as vendas dos modelos são respectivamente 7, 7, 6 e 9 reais. O fabricante dispõe de 30.000 horas para a montagem destes produtos (750 montadores trabalhando 40 horas por semana) e de 20.000 horas para decoração (500 decoradores trabalhando 40 horas semanais). Quanto de cada um dos modelos deve ser produzido durante a próxima semana a fim de maximizar o lucro? Admita que todas as unidades produzidas possam ser vendidas. 
AULA 10 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
RESOLUÇÃO DE PPL USANDO O APLICATIVO “LINGO 11.0”
AULA 10 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
RESOLUÇÃO DE PPL USANDO O APLICATIVO “LINGO 11.0”
SOLUÇÃO EXEMPLO 5:
Variáveis de Decisão:
xI = quantidade de consoles do modelo I;
xII = quantidade de consoles do modelo II;
xIII = quantidade de consoles do modelo III;
xIV = quantidade de consoles do modelo IV;
ou, mais resumidamente:
xi = quantidade de consoles do modelo i (i = I, II, III, IV).
Modelo Matemático:
Max Lucro = 7 xI + 7 xII + 6 xIII + 9 xIV
sujeito a: 4 xI + 5 xII + 3 xIII + 5 xIV  30000(restrição com relação ao tempo de montagem);
	 2 xI + xII + 5 xIII + 3 xIV  20000 (restrição com relação ao tempo para decoração);
	 xI, xII, xIII, xIV  0.
 
AULA 10 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
RESOLUÇÃO DE PPL USANDO O APLICATIVO “LINGO 11.0”
SOLUÇÃO EXEMPLO 5.
EXEMPLO 1.
1-Uma empresa agroindustrial deseja desenvolver um sistema de captação de água a partir de m locais potencialmente favoráveis. O custo variável de bombear água do local i=1,2 é Cij, proporcional a quantidade bombeada para o local j. A quantidade máxima que o local i pode produzir mensalmente é Li. Há 3 locais de demanda de água, sendo que o local j necessita da quantidade Qj, mensalmente, j= 1, 2 e 3. A unidade de água é 1 metro cúbico. Construa um modelo que minimize o custo, decida quanto de água mandar do poço i para o local j, mensalmente. Escrever o modelo linear e resolver.
DADOS: C11=1; C12=1,2; C13=0,9; C21=1,5;C22=1; C23=1,3; L1=1000000; L2=1200000; Q1=800000; Q2=600000; Q3=700000.
AULA 11 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
RESOLUÇÃO DE PPL USANDO O APLICATIVO “LINGO 11.0”
AULA 11 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
RESOLUÇÃO DE PPL USANDO O APLICATIVO “LINGO 11.0”
SOLUÇÃO EXEMPLO 1: MODELO.
xij = quantidade de água a ser bombeada do local i (i = 1, 2, ..., m) para o local j (j = 1, 2, 3).
Modelo Matemático:
Min Custo = (x11) + ( 1,2 x12) +(0,9x13)+(1,5x21)+(x22)+(1,3x23).
sujeito a: x11 + x12 + x13  1000000 (restrição com relação a quantidade máxima que o local 1 pode produzir);
	 x21+x22+x23 <= 1200000;
 
	 x11 + x21 = 800000 (restrição com relação a quantidade mínima requerida pelo local 1);
	 x12 + x22 = 600000 
 x13+x23 = 700000
		xij  0, (i = local 1, 2, ..., m e j = local 1, 2, 3).
AULA 11 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
RESOLUÇÃO DE PPL USANDO O APLICATIVO “LINGO 11.0”
SOLUÇÃO EXEMPLO 1: PROGRAMA.
AULA 11 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
RESOLUÇÃO DE PPL USANDO O APLICATIVO “LINGO 11.0”
EXEMPLO 2.
Uma empresa florestal tem quatro locais em que plantam árvores. Eles estão considerando quatro espécies de árvores, os pinheiros, abetos, nozes e outras folhosas. Os dados sobre o problema estão na tabela abaixo. 
Quanto de área deve se empregar ao cultivo de diversas espécies nos diferentes lotes para que o retorno seja máximo?
AULA 11 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
RESOLUÇÃO DE PPL USANDO O APLICATIVO “LINGO 11.0”
Max R = 16x11+12x12+20x13+18x14+14x21+13x22+24x23+20x24+17x31+10x32+28x33+20x34+12x41+11x42+18x43+17x44
s.a.
x11+x12+x13+x14<=1500 (área local 1)
x21+x22+x23+x24<=1700 (área local 2)
x31+x32+x33+x34<=900 (área local 3)
x41+x42+x43+x44<=600 (área local 4)
17x11+15x21+13x31+10x41>=22500 (demanda Pine)
14x12+16x22+12x32+11x42>=9000 (demanda Spruce)
10x13+12x23+14x33+8x43>=4800 (demanda Walnut)
9x14+11x24+8x34+6x44>=3500 (demanda Hardwood)
 
SOLUÇÃO EXEMPLO 2. MODELO
xij = área (em kiloacres) do sítio i destinada a espécie j, i=1,..,4 e j=1,..,4 
AULA 11 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
RESOLUÇÃO DE PPL USANDO O APLICATIVO “LINGO 11.0”
SOLUÇÃO EXEMPLO 2. PROGRAMA
AULA 11 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
CASOS ESPECIAIS DO SIMPLEX
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.
 
Exemplo 3.
Max z = 3x1 + 9x2
s.a.
 x1 + 4x2 <=8
 x1 + 2x2 <= 4
 
AULA 11 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
CASOS ESPECIAIS DO SIMPLEX
	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
SOLUÇÃO DEGENERADA
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
SOLUÇÕES MÚLTIPLAS
 
	Se na solução ótima o coeficiente (FO) 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 dessas duas soluções também será ótima.
 
Exemplo 4.
Max z = 2x1 + 4x2
s.a. 
 x1 + 2x2 <= 5
 x1 + x2 <=4
 x1, x2 >=0
AULA 11 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
CASOS ESPECIAIS DO SIMPLEX
AULA 11 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
CASOS ESPECIAIS DO SIMPLEX
SOLUÇÕES MÚLTIPLAS
	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
AULA 11 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
CASOS ESPECIAIS DO SIMPLEX
SOLUÇÃO ILIMITADA
 
Exemplo 5
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
	Base	X1	X2	x3	x4	Solução
	-Z	0	3	-2	0	-20
	X1	1	-1	1	0	10
	X4	0	2	-2	1	20
	Base	X1	X2	x3	x4	Solução
	-Z	0	0	1	-3/2	-50
	X1	1	0	0	1/2	20
	X2	0	1	-1	1/2	10
A solução não é ótima e x1 deve entrar a base. Porém, o teste do bloqueio não aponta a variável (x1, x2) que deve sair da base.
AULA 11 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
CASOS ESPECIAIS DO SIMPLEX
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 6
	Dado o problema:
 Max z = 5x1 + 3x2
 s.a.
 2x1 + x2 <=8
 x1 – 2x2 <= 3
 x1>=0 e x2 livre.
Substitui-se, no ex. 6, x2 (variável livre de sinal) por x2’ – x2’’, sendo x2’>= 0 e x2’’ >=0. Assim, escreve-se o ex. 6 na forma: 
 Max z = 5x1 + 3x2’-3x2’’
 s.a.
 2x1 + x2’-x2’’ <=8
 x1 – 2x2’+2x2’’ <= 3
 x1>=0 ,x2’ >=0 e 		x2’’>=0.
AULA 12 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
DUALIDADE
Dado um problema de PL que passaremos a chamar de primal, é possível associar outro PPL denominado dual, ou, sem fazer distinção entre os dois problemas, podemos dizer que temos um par de problemas duais ou par prima-dual.  
Definição 1. Dado um problema de PL.
 
O dual de (P) é o problema
 
 
 
Onde são chamadas de variáveis duais.
AULA 12 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
DUALIDADE
Exemplo 1. Obter o dual para o PPL.
 
 
Solução. (P) pode ser transformado em:
 
 
Portanto, o seu dual, por definição, será:
AULA 12 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
DUALIDADE
REGRAS PRÁTICAS PARA A CONSTRUÇÃO DO DUAL
	PROBLEMAS DE MAXIMIZAÇÃO	 	PROBLEMAS DE MINIMIZAÇÃO
	RESTRIÇÕES	 	VARIÁVEIS
	≥	⇔	≤ 0
	≤	⇔	≥ 0
	=	⇔	LIVRE DE SINAL
	VARIÁVEIS	⇔	RESTRIÇÕES
	≥ 0	⇔	≥
	≤ 0	⇔	≤
	IRRESTRITA	⇔	=
AULA 12 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
DUALIDADE
EXEMPLO 2: OBTER O DUAL
DOS PPLs:
a) Max z = 2x1 + 3x2 + x3
 s.a.
 3x1 + 4x2 + 2x3 <= 10
 2x1 + 6x2 + x3 <= 20
 x1 – x2 – x3 <= 30
 x1, x2, x3 >= 0 
 
b) Max z = 2x1 + 3x2 + x3
 s.a
 x1 + x2 <= 10
 2x1 + 4x2 – x3 = 20
 x1, x2, x3 >=0
c) Min z = 15x1 + 12x2
 s.a.
 x1 + 2x2 >= 3
 2x1 – 4x2 <= 5
 x1 é irrestrita, x2 >=0
Solução exemplo a):Min D = 10y1 + 20y2 +30y3
 s.a.
 3y1 + 2y2 +y3 >= 2
 4y1 + 6y2 –y3 >= 3
 2y1 +y2 –y3 >= 1
 y1, y2, y3 >= 0 
AULA 12 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
DUALIDADE
Solução exemplo 2 b)
Min D = 10y1 + 20y2
s.a.
 y1 + 2y2 >= 2
 y1 + 4y2 >= 3 
 - y2 >= 1
 y1>=0 e y2 é irrestrita
Solução exemplo 2 c)
Max D = 3y1 + 5y2
s.a.
 y1 + 2y2 = 15
2y1 -4y2 <= 12
 y1>=0, y2 <=0
Teorema Fraco de Dualidade. Seja o par de problemas Primal-Dual da definição 1.
Se é solução viável do primal e é solução viável do dual, então
Corolário 1. Se é solução viável em (P) e é solução viável em (D) e , então é solução ótima em (P) e é solução ótima em (D).
Corolário 2. 
(i) Se o problema primal é ilimitado, então o dual é inviável.
(ii) Se o problema dual é ilimitado, então o primal é inviável.
Teorema Forte de Dualidade (TFD). Em um par de problemas de PL primal-dual, se o primal (P) possuir uma solução ótima finita, então o seu dual (D) possuirá solução ótima finita e os valores ótimos serão iguais.
AULA 12 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
DUALIDADE
AULA 12 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
DUALIDADE
Definição 2. Seja o par de problemas primal-dual da Definição 1. Seja , solução básica viável do primal, e , solução básica viável do dual. Diz-se que obedecem às condições de folgas complementares se e somente se:
Teorema das Folgas Complementares (TFC). Seja o par de problemas primal-dual da Definição 1. são soluções ótimas de (P) e (D), respectivamente, se e somente se forem viáveis e obedecerem às condições de Folgas Complementares .
AULA 12 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
DUALIDADE
EXEMPLO 3. DADO O PPL
MAX z = 5x1 + 4x2
 s.a. 
 6x1+4x2 <= 24
 x1 + 2x2 <= 6
 -x1 + x2 <= 1
 x1 e x2 >=0,
COM SOLUÇÃO ÓTIMA:
x1=3; x2=1,5; z = 21.
OBTER A SOLUÇÃO ÓTIMA DO DUAL CORRESPONDENTE 
SOLUÇÃO.
DUAL: MIN D = 24y1 +6y2 +y3
 s.a. 
 6y1 +y2 –y3 >= 5
 4y1 +2y2 +y3 >=4
 y1,y2,y3 >=0
INSERINDO AS FOLGAS NOS PROBLEMAS PRIMAL E DUAL:
PRIMAL: 6x1+4x2 = 24 – v1 v1 = 0.
 x1 + 2x2 = 6 –v2 v2 = 0. 
 -x1 + x2 = 1 – v3 v3 = 2,5. 
DUAL: 6y1 +y2 –y3 = 5 +h1
 4y1 +2y2 +y3 =4 +h2
 
AULA 12 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
DUALIDADE
SOLUÇÃO EXEMPLO 3.
Pelo TFC, temos:
x1.h1 =0 3.h1=0 h1=0
x2.h2 =0 1,5.h2=0 h2=0
y1.v1 =0
y2.v2 =0
y3.v3 =0 y3.(2,5)=0 y3=0
SUBSTITUINDO y3 = h1 = h2 =0 NAS EQUAÇÕES:
6y1 +y2 –y3 = 5 +h1
4y1 +2y2 +y3 =4 +h2, VEM:
CUJA SOLUÇÃO É: 
y1= ¾ e y2 = ½ 
CONSIDERANDO O TFD, TEMOS: z = D = 21.
ASSIM, TEMOS A SEGUINTE SOLUÇÃO ÓTIMA PARA O DUAL:
y1= ¾ ; y2 = ½ ; y3=h1=h2=0 e D=21
AULA 12 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
DUALIDADE
EXEMPLO 4. 
OBTER, USANDO OS TEOREMAS DA DUALIDADE, A SOLUÇÃO ÓTIMA DO DUAL CORRESPONDENTE AO PPL (P):
(P): Max z = 200x1 + 300x2
 s.a.
 	2x1 + x2 <=20
 	4x1 <= 32
 	 x2 <= 10
	x1>=0, x2>=0,
SABENDO QUE A SOLUÇÃO ÓTIMA DE (P) É:
x1=5; x2=10 e z=4000.
AULA 12 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
DUALIDADE
SOLUÇÃO EXEMPLO 4.
DUAL: 
 MIN D = 20y1 +32y2 +10y3
 s.a. 
 2y1 +4y2 >= 200
 y1 +y3 >=300
 y1,y2,y3 >=0
INSERINDO AS FOLGAS NOS 
PROBLEMAS PRIMAL E DUAL:
PRIMAL: 
 2x1+x2 = 20 – v1 v1 = 0.
 4x1 = 32 –v2 v2 = 12. 
 x2 = 10 – v3 v3 = 0. 
DUAL: 
 2y1 +4y2 = 200 +h1
 y1 + y3 =300 +h2
Pelo TFC, temos:
x1.h1 =0 h1=0
x2.h2 =0 h2=0
y1.v1 =0
y2.v2 =0 y2=0
y3.v3 =0.
SUBSTITUINDO y2 = h1 = h2 =0 NAS EQUAÇÕES:
2y1 +4y2 = 200 +h1
y1 +y3 =300 +h2, OBTÉM-SE A SOLUÇÃO ÓTIMA DO DUAL:
y1=100; y3=200; y2=h1=h2=0 e D=4000.
AULA 13 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO DUAL SIMPLEX
O método dual simplex é uma aplicação do método simplex ao problema dual. Um dos principais usos deste método ocorre em reotimizações de problemas de otimização linear; quando, após o problema original ter sido resolvido, novas restrições são adicionadas (problema novo). Se a solução ótima do problema original (já determinada) satisfaz as novas restrições, então ela também é ótima para o problema novo. Caso contrário, a solução ótima do problema original é infactível para o problema novo, e uma reotimização deste problema usando o método simplex necessita da introdução de variáveis artificiais. Entretanto, do ponto de vista do problema dual, novas restrições ao problema primal implicam novas variáveis duais, de modo que a solução dual não perde a factibilidade, porém pode deixar de ser ótima.
AULA 13 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO DUAL SIMPLEX
 EXEMPLO 1. Seja o PPL.
 
Cujo quadro ótimo é:
	Base	X1	X2	X3	X4	Solução
	-Z	0	0	-1	-1	-8
	X1	1	0	1	-1	4
	X2	0	1	0	1	2
Introduzir uma terceira restrição 3x1+x2≤9 ao modelo. Substituindo a solução na nova restrição, concluímos que esta pode alterar a solução ótima. Pois, a restrição (3.4 +2 ≤9) não é verificada. Neste caso, a região viável foi alterada.
AULA 13 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO DUAL SIMPLEX
Aproveitando o quadro ótimo do problema original, com a inclusão da terceira restrição e respectiva folga, temos:
	Base	X1	X2	X3	X4	X5	Solução
	-Z	0	0	-1	-1	0	-8
	X1	1	0	1	-1	0	4
	X2	0	1	0	1	0	2
	X5	3	1	0	0	1	9
Observa-se no quadro que as colunas das variáveis x1 e x2 devem ser “arrumadas”, de forma que na linha de x5 apareçam zeros nas colunas de x1 e x2. Para tanto, deve-se efetuar a seguinte operação: nova linha de x5 = linha de x5 atual – [3.(linha de x1) + linha de x2]. Assim, obtém-se o quadro:
AULA 13 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO DUAL SIMPLEX
	Base	X1	X2	X3	X4	X5	Solução
	-Z	0	0	-1	-1	0	-8
	X1	1	0	1	-1	0	4
	X2	0	1	0	1	0	2
	X5	0	0	-3	2	1	-5
Do ponto de vista do primal a solução é ótima, mas inviável. Para o dual a solução é viável, mas não é ótima. Então, procurando o ótimo a partir do algoritmo dual simplex, tira-se da base a variável com valor mais negativo (no caso X5) e entra X3 (menor quociente entre os coeficiente de variável não-básica na linha –z e coeficientes negativos na linha de X5).
	Base	X1	X2	X3	X4	X5	Solução
	-Z	0	0	0	-5/3	-1/3	-19/3
	X1	1	0	0	-1/3	1/3	7/3
	X2	0	1	0	1	0	2
	X3	0	0	1	-2/3	-1/3	5/3
AULA 13 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO DUAL SIMPLEX
O primal simplex mantém a viabilidade do primal procurando obter a viabilidade do dual. O dual simplex procede no sentido inverso, ou seja, mantém a viabilidade do dual procurando a viabilidade do primal. Outra característica do dual simplex é atuar em cima do quadro relativo ao problema primal, sendo aplicado em uma situação de solução ótima e inviável, usando-se os critérios:	
-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.
-Condição de otimalidade dual: min , onde:
 = coeficiente da variável não básica na linha z.
 = coeficientes da restrição na linha de ( é a variável que sai da base).
	Para iniciar o algoritmo deve-se cumprir 2 requisitos:
A F.O. deve satisfazer a condição de otimalidade do método simplex primal e todas as restrições devem ser do tipo (<=).
 
AULA 13 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO DUAL SIMPLEX
Obs.: uma restrição do tipo “=” 
pode ser transformada em duas 
restrições do tipo “<=” e “>=”.
EXEMPLO 2:
A restrição x1 + x2 = 1 é equivalente a: 
EXEMPLO 3.
 USE O ALGORITMO DUAL SIMPLEX 
PARA RESOLVER O PPL:
Min z = 3x1 + 2x2 + x3
s.a.
 3x1 + x2 + x3 >= 3
 -3x1 + 3x2 + x3 >= 6 
 x1 + x2 + x3 <= 3
 x1, x2, x3 >=0
SOLUÇÃO EXEMPLO 3.TRANSFORMANDO EM UM PROBLEMA DE MAXIMIZAÇÃO E AS DESIGUALDADES DO TIPO “>=“ EM “<=“, TEMOS:
Max -z = -3x1 - 2x2 - x3
s.a.
 -3x1 - x2 - x3 <= -3
 3x1 - 3x2 - x3 <= -6 
 x1 + x2 + x3 <= 3
 x1, x2, x3 >=0
AULA 13 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO DUAL SIMPLEX
	 	x1	x2	x3	s1	s2	s3	Solução
	z	-3	-2	-1	0	0	0	0
	s1	-3	-1	-1	1	0	0	-3
	s2	3	-3	-1	0	1	0	-6
	s3	1	1	1	0	0	1	3
SOLUÇÃO EXEMPLO 3. 
QUADRO INICIAL (A SOLUÇÃO É ÓTIMA, MAS INVIÁVEL).
PELOS CRITÉRIOS DE VIABILIDADE E OTIMALIDADE: s2 SAI DA BASE PARA x2 ENTRAR () E -3 É O PIVÔ.
	 	x1	x2	x3	s1	s2	s3	Solução
	z	-5	0	-1/3	0	-2/3	0	4
	s1	-4	0	-2/3	1	-1/3	0	-1
	x2	-1	1	1/3	0	-1/3	0	2
	s3	2	0	2/3	0	1/3	1	1
AULA 13 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO DUAL SIMPLEX
	 	x1	x2	x3	S1	s2	s3	Solução
	z	-5	0	-1/3	0	-2/3	0	4
	s1	-4	0	-2/3	1	-1/3	0	-1
	x2	-1	1	1/3	0	-1/3	0	2
	s3	2	0	2/3	0	1/3	1	1
	 	x1	x2	x3	s1	s2	s3	Solução
	z	-3	0	0	-1/2	-1/2	0	9/2
	x3	6	0	1	-3/2	1/2	0	3/2
	x2	-3	1	0	1/2	-1/2	0	3/2
	s3	-2	0	0	1	0	1	0
SOLUÇÃO EXEMPLO 3. 
A VARIÁVEL s1 SAI DA BASE PARA x3 ENTRAR () E -2/3 É O PIVÔ.
AULA 13 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO DUAL SIMPLEX
EXEMPLO 4.
 USE O ALGORITMO DUAL
 SIMPLEX 
PARA RESOLVER O PPL:
Min z = 2x1 + x2
s.a.
 4x1 + 3x2 >=6
 x1 + 2x2 <=3
 x1 >=0 e x2 >=0
SOLUÇÃO EXEMPLO 4.
TRANSFORMANDO EM UM PROBLEMA DE MAXIMIZAÇÃO E AS DESIGUALDADES DO TIPO “>=“ EM “<=“, TEMOS:
Max -z = -2x1 - x2 
s.a.
 -4x1 -3x2 <= -6
 x1 + 2x2 <= 3 
 x1, x2, x3 >=0
AULA 13 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ALGORITMO DUAL SIMPLEX
	 	x1	x2	s1	s2	Solução
	z	-2	-1	0	0	0
	s1	-4	-3	1	0	-6
	s2	1	2	0	1	3
SOLUÇÃO EXEMPLO 4. 
QUADRO INICIAL (A SOLUÇÃO É ÓTIMA, MAS INVIÁVEL).
PELOS CRITÉRIOS DE VIABILIDADE E OTIMALIDADE: s1 SAI DA BASE PARA x2 ENTRAR () E -3 É O PIVÔ.
	 	x1	x2	s1	s2	Solução
	z	-2/3	0	-1/3	0	2
	x2	4/3	1	-1/3	0	2
	s2	-5/3	0	-2/3	1	-1
AULA 14 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ANÁLISE DE SENSIBILIDADE
Ao se achar a solução de um PPL, esta deverá ser criticada face às variações que pode sofrer o modelo. Isto é, devemos avaliar como as variações no modelo afetam a solução do PPL original.
Seja o PPL: 
 Max z = CTx, CT ∊ ℝn
 s.a.
 Ax = b, A ∊ ℝmxn, x ∊ ℝn, b ∊ ℝm
 x >= 0
Onde:
	CT = vetor linha.
	x = vetor coluna.
	b = vetor coluna.
	
Considerando a F.O. como 
mais uma restrição do problema, 
tem-se o sistema linear:
 , x >= 0. 
Escrevendo na forma matricial, 
vem:
 (1)
Seja B uma matriz base do sistema
 Ax = b, com x >=0 e xB o vetor correspondente de variáveis básicas com como seu vetor de coeficientes da F.O. Assim, pode-se escrever. 
 (2).
AULA 14 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ANÁLISE DE SENSIBILIDADE
 Isolando em (2) , vem:
 
 ou
 
 ,
 com isso obtém-se o lado direito do quadro simplex. A obtenção de todos os coeficientes da tabela simplex é feita da seguinte maneira.
	Multiplica-se à esquerda a equação (1) por . Assim, tem-se:
AULA 14 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ANÁLISE DE SENSIBILIDADE
 
 ⇒
 
 
 
Sendo Pj o j-ésimo vetor coluna de A e o coeficiente original da F.O. (coluna j). Podemos, então, escrever a coluna da tabela simplex associada com a variável xj , podendo ser representada como:
AULA 14 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ANÁLISE DE SENSIBILIDADE
	Base	Xj	Solução
	Z		
	xB		
COEFICIENTES DO QUADRO SIMPLEX POR OPERAÇÕES MATRICIAIS.
QUADRO 1.
AULA 14 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ANÁLISE DE SENSIBILIDADE
OPERAÇÕES COM MATRIZES NO EXCEL – MATRIZ INVERSA.
AULA 14 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ANÁLISE DE SENSIBILIDADE
OPERAÇÕES COM MATRIZES NO EXCEL – MULTIPLICAÇÃO.
EXEMPLO 1. DADO O PPL
Max z = 50x1 + 90x2
s.a.
2x1 + 3x2 <=300
10x1 + 5x2 <=1000
x1,x2>=0
 
UTILIZE AS OPERAÇÕES DO QUADRO 1(aula 14) PARA DETERMINAR O QUADRO ÓTIMO, SENDO x2 E s2 (NESTA ORDEM) A BASE ÓTIMA.
Obs.: s2 é a folga da segunda restrição. 
AULA 14 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ANÁLISE DE SENSIBILIDADE
AULA 14 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ANÁLISE DE SENSIBILIDADE
SOLUÇÃO EXEMPLO 1. 
Max z = 50x1 + 90x2
s.a.
2x1 + 3x2 +s1=300
10x1 + 5x2 +s2=1000
x1,x2,s1,s2>=0
x2 s2
ATUALIZAÇÃO DOS COEFICIENTES DAS RESTRIÇÕES
ATUALIZAÇÃO DOS COEFICIENTES DA F.O. ()
SOLUÇÃO ÓTIMA:
AULA 14 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ANÁLISE DE SENSIBILIDADE
SOLUÇÃO EXEMPLO 1.
ATUALIZAÇÃO DOS COEFICIENTES DA F.O.
=
CÁLCULO DE z: 
	 	x1	x2	s1	s2	Solução
	Z	10	0	30	0	9000
	x2	2/3	1	1/3	0	100
	s2	20/3	0	-5/3	1	500
QUADRO ÓTIMO
EXEMPLO 2. DADO O PPL
Max z = 2x1 + 4x2 + 3x3
s.a.
x1 + 3x2 + x3 <=500
2x1 + x2 + 4x3 <=200
x1 + x2 + 2x3 <= 700
x1,x2, x3>=0
 UTILIZE AS OPERAÇÕES DO QUADRO 1 PARA DETERMINAR O QUADRO ÓTIMO, SENDO x2, x3 E s3 (NESTA ORDEM) A BASE ÓTIMA.
Obs.: s3 é a folga da terceira restrição. 
AULA 14 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ANÁLISE DE SENSIBILIDADE
AULA 14 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ANÁLISE DE SENSIBILIDADE
SOLUÇÃO EXEMPLO 2.
 Max z = 2x1 + 4x2 + 3x3
s.a.
x1 + 3x2 + x3 +s1=500
2x1 + x2 + 4x3 +s2=200
x1 + x2 + 2x3 +s3= 700
x1,x2, x3,s1,s2,s3>=0
AULA 14 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ANÁLISE DE SENSIBILIDADE
SOLUÇÃO EXEMPLO 2.
AULA 14 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ANÁLISE DE SENSIBILIDADE
SOLUÇÃO EXEMPLO 2.
AULA 14 – PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ANÁLISE DE SENSIBILIDADE
SOLUÇÃO EXEMPLO 2.
AULA 15– PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ANÁLISE DE SENSIBILIDADE
VALOR DA VARIÁVEL DUAL (y)
	Segundo o teorema forte da dualidade o valor da FO do primal é igual ao valor da FO do dual , onde x e y são soluções finitas do primal e dual, respectivamente. Ou seja:
Sabemos do quadro 1 (aula 14) que Z= (1) 
= 
 
 
No primal, o valor da variável dual (y), normalmente, é denominada de preço dual.
FAIXA DE VIABILIDADE
	O quociente entre a variação do valor de z (F.O) e a variação do lado direito das restrições (que chamaremos disponibilidade do recurso) é chamado de PREÇO DUAL OU SOMBRA, e este permanece sem alterações enquanto o recurso permanecer dentro de um determinado intervalo, denominado FAIXA DE VIABILIDADE. Então, queremos encontrar as possíveis variações do recurso que não implicam na inviabilidade da solução básica.
AULA 15– PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ANÁLISE DE SENSIBILIDADE
EXEMPLO 1. Obter: (a) FAIXA DE VIABILIDADE para os recursos 1 e 2 do seguinte PPL; (b) Preço dual relativo aos recursos 1 e 2; (c) O valor de z na solução ótima quando a disponibilidade do recurso 1 aumenta de 6 para 10 e no caso da redução de 6 para 1.
 
 : Recurso 1.
 : Recurso 2.
.
AULA 15– PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ANÁLISE DE SENSIBILIDADE
FAIXA DE VIABILIDADE
SOLUÇÃO EXEMPLO 1. Sejam D1 e D2 as variações (positivas ou negativas) nos recursos 1 e 2, respectivamente. Acrescentando D1 e D2 ao quadro inicial do simplex do PPL (P), temos:
	Base	x1	x2	x3	x4	Solução	D1	D2
	Z	1	2	0	0	0	0	0
	x3	1	1	1	0	6	1	0
	x4	0	1	0	1	2	0	1
Observa-se que a matriz formada pelas colunas de x3 e x4 é igual à formada pelas colunas de D1 e D2. Desta forma, no quadro ótimo estas matrizes também serão iguais, ou seja:
	Base	X1	X2	X3	X4	Solução	D1	D2
	Z	0	0	1	1	8	1	1
	X1	1	0	1	-1	4	1	-1
	X2	0	1	0	1	2	0	1
QUADRO ÓTIMO PPL (P)
AULA 15– PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ANÁLISE DE SENSIBILIDADE
FAIXA DE VIABILIDADE
SOLUÇÃO EXEMPLO 1.
AULA 15– PESQUISA OPERACIONAL I. PROF.:LEVI LOPES TEIXEIRA
ANÁLISE DE SENSIBILIDADE
FAIXA DE VIABILIDADE
SOLUÇÃO EXEMPLO 1.
Conforme a equação 1 (Z= ), Z e as componentes do vetor
 são diretamente proporcionais, sendo as componentes do preço dual 
() as constantes (dentro da faixa de viabilidade) de proporcionalidade.
Então, no caso do recurso 1 (rec 1) aumentar de 6 para 10, temos:
2
No caso em que o valor do recurso 1 diminui de 6 para 1, não se pode usar o atual preço dual para calcular o novo Z, pois o novo valor da disponibilidade do recurso 1 está fora da sua atual faixa de viabilidade .
ANÁLISE DE SENSIBILIDADE
FAIXA DE VIABILIDADE
AULA 15– PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
EXEMPLO 2. (a) Formule o modelo linear para o problema abaixo. (b) Encontre a faixa de viabilidade para o recurso água. ( c) Determine o preço dual dos recursos. (d) Use o preço dual para determinar o valor do lucro se cada recurso aumentar em 10 unidades.
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 kl 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 kl 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 kl de água;14.000 kg de adubo;100 alqueires de terra.
Max Lucro = 300x1 + 400x2 + 500x3
s.a.
		x1 + x2 + x3 <= 100
	 100x2 + 200x3 <= 14.000
	 100x2 + 200x3 <= 12.750
		x1, x2, x3 >=0
x1 = alqueires para arrendamento; x2 = alqueires para pecuária; x3 = alqueires para soja.
ANÁLISE DE SENSIBILIDADE
FAIXA DE VIABILIDADE
AULA 15– PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
SOLUÇÃO EXEMPLO 2.
a)
ANÁLISE DE SENSIBILIDADE
FAIXA DE VIABILIDADE
AULA 15– PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
SOLUÇÃO EXEMPLO 2 
	BASE	x1	x2	x3	s1	s2	s3	sol
	"-z"	0	0	0	-300	0	-1	-42750
	x1	1	0,5	0	1	0	-0,005	36,25
	s2	0	0	0	0	1	-1	1250
	x3	0	0,5	1	0	0	0,005	63,75
b) QUADRO ÓTIMO
x1= 36,25 + D1 – 0,005D3; s2 = 1250 + D2 – D3; x3 = 63,75 + 0,005D3.
Fazendo D1=D2=0, temos:
36,25 -0,005D3 >=0  D3<= 7250
1250 – D3 >=0  D3<=1250
63,75+0,005D3>=0  D3>= - 12750
FAIXA DE VIABILIDADE 12750 – 12750 <=Recurso água <=12750 + 1250  0 <= Recurso água <= 14000
 
162
ANÁLISE DE SENSIBILIDADE
FAIXA DE VIABILIDADE
AULA 15– PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
SOLUÇÃO EXEMPLO 2. 
 
Recurso 1 (terra): 100  110. Lucro = 42750 + 10*300 = 45750.
Recurso 2 (adubo) : 14000  14010. Lucro = 42750 + 10*0 = 42750.
Recurso 3 (água) : 12750  12760. Lucro = 42750 + 10*1 = 42760. 
c)
d)
ANÁLISE DE SENSIBILIDADE
FAIXA DE OTIMALIDADE
AULA 16– PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
Enquanto (condição de otimalidade) a solução ótima xB= não sofre alterações. Por outro lado, a não otimalidade implica em outra base e em consequência disso xB pode ter outro resultado. Então, queremos encontrar possíveis variações no vetor inicial CT que não implicam em alterações na solução ótima xB=.
EXEMPLO 1. Obter a FAIXA DE OTIMALIDADE para os coeficientes da F.O. do PPL abaixo, sabendo que x1 e x2 (nesta ordem) formam a base ótima do PPL
 
 
Usando para as variáveis não básicas x3 e x4 (folgas) na solução ótima, temos:
Coeficiente de x3 na linha da F.O. = .
 Obs.: . 
Coeficiente de x4 na linha da F.O. = . 
Obs.: .
ANÁLISE DE SENSIBILIDADE
FAIXA DE OTIMALIDADE
AULA 16– PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
SOLUÇÃO EXEMPLO 1. Sejam d1 e d2 as variações (positivas ou negativas) nas componentes do vetor inicial CT (coeficientes de x1 e x2 na F.O., respectivamente). Assim, tem-se:
ANÁLISE DE SENSIBILIDADE
FAIXA DE OTIMALIDADE
AULA 16– PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
SOLUÇÃO EXEMPLO 1.
Da condição de otimalidade, temos:
1+d10 e d2-d1+10. 
Para d2=0, tiramos -1d11. Sendo assim, o intervalo
 -1+1 < coef. De x1<1+1 é a faixa de otimalidade do coef. De x1 na F.O.
 Isto é, enquanto o coef. De x1 permanecer nesta faixa, a solução ótima xB= não sofre alteração. 
Fazendo d1=0, temos d2 -1 e o intervalo -1+2<coef. De x2 < 2+∞ é a faixa de otimalidade para o coef. De x2 na F.O.
Obs.: Caso o quadro ótimo do PPL possuir variável não básica com coeficiente nulo na F.O. , o PPL possuirá múltiplas soluções ótimas.
ANÁLISE DE SENSIBILIDADE
FAIXA DE OTIMALIDADE
AULA 16– PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
EXEMPLO 2.
Obter a FAIXA DE OTIMALIDADE para os coeficientes da F.O. do PPL abaixo, sabendo que x2 e x4 (folga da segunda restrição) formam a base ótima do PPL.
Max z = 50x1 + 90x2
s.a.
2x1 + 3x2 <=300
10x1 + 5x2 <= 1000
X1,x2>=0
Usando para as variáveis não básicas x1 e x3 (folga) na solução ótima, temos:
Coeficiente de x1 na linha da F.O. = .
 
Coeficiente de x3 na linha da F.O. = . 
ANÁLISE DE SENSIBILIDADE
FAIXA DE OTIMALIDADE
AULA 16– PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
SOLUÇÃO EXEMPLO 2. Sejam d1 e d2 as variações (positivas ou negativas) nas componentes do vetor inicial CT (coeficientes de x1 e x2 na F.O., respectivamente). Assim, tem-se:
ANÁLISE DE SENSIBILIDADE
FAIXA DE OTIMALIDADE
AULA 16– PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
SOLUÇÃO EXEMPLO 2.
Da condição de otimalidade, temos:
30+d2/30 e 10+2d2/3- d10. 
Para d2=0, tiramos d110. Sendo assim, o intervalo
 50 - ∞ < coef. De x1<+10 é a faixa de otimalidade do coef. De x1 na F.O.
 Isto é, enquanto o coef. De x1 permanecer nesta faixa, a solução ótima xB= não sofre alteração. 
Fazendo d1=0, temos d2 -15 e o intervalo 90-15<coef. De x2 < 90+∞ é a faixa de otimalidade para o coef. De x2 na F.O.
ANÁLISE DE SENSIBILIDADE
AULA 17– PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
CUSTO REDUZIDO
Cada variável do problema original possui um custo reduzido (valor da variável de folga no dual correspondente).
Significado do custo reduzido (não nulo) de uma variável de decisão não básica (
Total que seu coeficiente na F.O. do problema original deve melhorar para que ele (custo reduzido) passe a ser nulo, possibilitando que deixe de ser zero na solução ótima.
(b)Quanto a F.O. irá piorar para cada unidade que a variável correspondente aumente a partir de zero.
Cálculo do custo reduzido da variável de decisão .
ANÁLISE DE SENSIBILIDADE
CUSTO REDUZIDO
EXEMPLO 1. Considere 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 1 - uso/un.	Recurso 2 - uso/un.	Lucro/unidade
	P1	2	10	50
	P2	3	5	90
	Disponibilidade de recursos	300	1000	 
Sabendo que x2 (quantidade produzida de P2) e x4 (folga da segunda restrição – recurso 2) formam a base ótima do PPL, pede-se: (a) Preço dual dos recursos 1 e 2; (b) Custo reduzido das variáveis de decisão;(c) Os recursos abundantes e 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 3 unidades? (f) É interessante, em termos do lucro, vender 1 unidade do recurso 1 por $ 50? (g) Quanto deve ser o valor mínimo do lucro unitário do produto P1 para que ele seja produzido?
AULA 17– PESQUISA OPERACIONAL I. PROF.: LEVI LOPES TEIXEIRA
ANÁLISE DE SENSIBILIDADE
CUSTO REDUZIDO
O modelo linear:
	 Max z = 50x1 + 90x2
 s.a.
 2x1 + 3x2 <=300 : restrição 1 (recurso 1)
 10x1 + 5x2 <= 1000 : restrição 2 (recurso 2)
 x1, x2 >=0,