Pesquisa Operacional Introducao a Pesqui

Prévia do material em texto

1 
Pesquisa Operacional 
 
 
Introdução à Pesquisa Operacional 
Programação Linear 
 
 
 
Sumário 
 
2 
 
• Modelagem e limitações da Programação Linear. 
 
• Resolução Gráfica. 
 
• Forma padrão de um modelo de Programação Linear. 
 
• Definições e Teoremas. 
 
• Forma canônica de um sistema de equações lineares. 
 
• Método Simplex. 
 
• Exercícios 
3 
 
Programação Linear: 
Preocupação em encontrar a melhor solução para problemas 
associados com modelos lineares. 
 
Modelo de Programação Linear: 
Maximização (ou minimização) de uma função objetivo linear com 
relação as variáveis de decisão do modelo. 
Respeitando-se as limitações (restrições) do problema expressas por 
um sistema de equações e inequações associadas com as variáveis de 
decisão do modelo. 
Programação Linear 
Modelagem em Programação Linear 
4 
Razões para o uso da Programação Linear: 
 
1. Grande variedade de situações podem ser aproximadas por 
modelos lineares. 
 
2. Existência de técnicas (algoritmos) eficientes para a solução 
de modelos lineares. 
 
3. Possibilidade de realização de análise de sensibilidade nos 
dados do modelo. 
 
4. Estágio de desenvolvimento da tecnologia computacional. 
Modelagem em Programação Linear 
5 
Passos básicos na obtenção de modelos de PL: 
 
1. Identificar as variáveis de decisão, representá-las em simbologia 
algébrica. 
 
2. Identificar as restrições do problema, expressá-las como 
equações ou inequações lineares em termos das variáveis de 
decisão. 
 
3. Identificar o objetivo de interesse no problema, representá-lo 
como função linear em termos das variáveis de decisão, que 
deverá ser maximizada ou minimizada. 
Modelagem em Programação Linear 
6 
Construção de modelos não é uma ciência, mas uma 
arte, podendo ser melhorada com a prática. 
 
 
Exemplos a serem trabalhados: 
 
Determinação do mix de produção 
Seleção de mídia para propaganda 
Um problema de treinamento 
Uma indústria química 
Uma oficina mecânica 
Dimensionamento de equipes de inspeção 
Modelagem em Programação Linear 
 
7 
Determinação do mix de produção 
 
Uma companhia deseja programar a produção de um utensílio de cozinha 
que requer o uso de dois tipos de recursos – mão-de-obra e material. A 
companhia está considerando a fabricação de três modelos e o seu 
departamento de engenharia forneceu os dados a seguir: 
Modelo 
A B C 
Mão-de-obra 
(horas por unidade) 
7 3 6 
Material 
(kg por unidade) 
4 4 5 
Lucro 
($ por unidade) 
4 2 3 
O suprimento de material é de 
200 kg por dia. A 
disponibilidade diária de mão-
de-obra é 150 horas. Formule 
um modelo de Programação 
Linear para determinar a 
produção diária de cada um dos 
modelos de modo a maximizar 
o lucro total da companhia. 
Modelagem em Programação Linear 
8 
Formulação do modelo 
 
1. Identificação das variáveis de decisão: 
XA – produção diária do modelo A 
XB – produção diária do modelo B 
XC – produção diária do modelo C 
2. Identificação das restrições: 
(Limitação de mão-de-obra) 7XA + 3XB + 6XC  150 
(Limitação de material) 4XA + 4XB +5XC  200 
(Não-negatividade) XA  0, XB 0, XC  0. 
3. Identificação do objetivo: maximização do lucro total 
Lucro Total = L = 4XA + 2XB +3XC 
Max L = 4XA + 2XB +3XC 
Modelagem em Programação Linear 
 
9 
 
Modelo 
Encontrar números XA, XB, XC tais que: 
 
Max L= 4XA + 2XB +3XC 
 
 
Sujeito as restrições: 7XA + 3XB +6XC  150 
 4XA + 4XB +5XC  200 
 XA  0, XB 0, XC  0 
Modelagem em Programação Linear 
 
10 
Seleção de mídia para propaganda 
 
Uma companhia de propaganda deseja planejar uma campanha em 03 
diferentes meios: TV, rádio e revistas. Pretende-se alcançar o maior 
número de clientes possível. Um estudo de mercado resultou em: 
TV 
horário 
TV 
horário 
Rádio Revistas 
normal nobre 
Custo 40.000 75.000 30.000 15.000 
Clientes 
Atingidos 
400.000 900.000 500.000 200.000 
Mulheres 
Atingidas 
300.000 400.000 200.000 100.000 
0bs: valores válidos para cada veiculação da propaganda. 
Modelagem em Programação Linear 
 
11 
 
A companhia não quer gastar mais de $ 800.000 e, adicionalmente, 
deseja: 
(1) Que no mínimo 2 milhões de mulheres sejam atingidas; 
(2) Gastar no máximo $ 500.000 com TV; 
(3) Que no mínimo 03 veiculações ocorram no horário normal TV; 
(4) Que no mínimo 02 veiculações ocorram no horário nobre TV; 
(5) Que o nº. de veiculações no rádio e revistas fiquem entre 05 e 10, para 
cada meio de divulgação. 
 Formular um modelo de PL que trate este problema, 
determinando o nº. de veiculações a serem feitas em cada meio de 
comunicação, de modo a atingir o máximo possível de clientes. 
Modelagem em Programação Linear 
 
12 
Resolução do exemplo “seleção de mídia para propaganda” 
Variáveis de decisão: 
X1 = nº. de exposições em horário normal na tv. 
X2 = nº. de exposições em horário nobre na tv. 
X3 = nº. de exposições feitas utilizando rádio 
X4 = nº. de exposições feitas utilizando revistas. 
Função-objetivo: 
“Maximizar nº. de clientes atingidos” 
Max Z = 400.000X1 + 900.000X2 + 500.000X3 + 200.000X4 
Modelagem em Programação Linear 
 
13 
Restrições: 
Orçamento: 
40.000X1 + 75.000X2 + 30.000X3 + 15.000X4  800.000 
Mulheres atingidas: 
300.000X1 + 400.000X2 + 200.000X3 + 100.000X4  2.000.000 
Gasto com TV 
40.000X1 + 75.000X2  500.000 
Nº. de veiculações em TV, rádio e revistas 
X1  3, X2  2, 5  X3  10, 5  X4  10 
Não-negatividade 
X1, X2, X3, X4  0. 
Modelagem em Programação Linear 
 
14 
Um problema de treinamento 
 
 Uma empresa de máquinas ferramentas tem um programa 
de treinamento para operadores de máquinas. Alguns operadores 
já treinados podem trabalhar como instrutores neste programa 
ficando responsáveis por 10 trainees cada. A empresa pretende 
aproveitar apenas 07 trainees de cada turma de 10. 
 
 Estes operadores treinados também são necessários na 
linha de fabricação, e sabe-se que serão necessários para os 
próximos meses: 100 operadores em janeiro, 150 em fevereiro, 
200 em março, e 250 em abril. Atualmente há 130 operadores 
treinados disponíveis na empresa. 
Modelagem em Programação Linear 
 
15 
Encontrar um modelo de PL que forneça um programa de 
treinamento de custo mínimo e satisfaça os requisitos da empresa 
em termos de nº. de operadores treinados disponíveis a cada mês. 
 
Observação: acordo firmado com o sindicato proíbe demissões de 
operadores treinados no período. 
Os custos associados a cada situação são: 
 
Trainees ...........................................................................$ 400. 
Operador treinado trabalhando ........................................$ 700. 
Operador treinado ocioso..................................................$ 500. 
 
Modelagem em Programação Linear 
 
16 
Variáveis de decisão: 
X6 = operadores ociosos em março 
X5 = operadores trabalhando como instrutores em março 
X4 = operadores ociosos em fevereiro 
X3 = operadores trabalhando como instrutores em fevereiro 
X2 = operadores ociosos em janeiro 
Resolução do exemplo: Um problema de treinamento 
 
Observe que a cada mês um operador treinado está: operando 
máquina, trabalhando como instrutor, ou estáocioso. Além disto, o 
nº. de operadores treinados trabalhando nas máquinas é fixo e 
conhecido: 100 em janeiro, 150 em fevereiro, 200 em março e 250 
em abril. 
X1 = operadores trabalhando como instrutores em janeiro 
Modelagem em Programação Linear 
 
17 
Função-objetivo: 
Min C = 400(10X1 + 10X3 + 10X5) + 700(X1 + X3 + X5) + 
 + 500(X2 + X4 + X6) + 700(100 + 150 + 200) 
 
Min C = 4700X1 +500X2 + 4700X3 +500X4 +4700X5 +500X6 + 315.000 
 
“Custo total = custo trainees + custo instrutores + custo ociosos + 
custo operadores trabalhando em máquinas”. 
Modelagem em Programação Linear 
 
18 
Restrições: X1, X2, X3, X4, X5, X6  0 (não-negatividade) 
 Abril: 250 = 130 + 7X1 + 7X3 + 7X5  7X1 + 7X3 + 7X5 = 120. 
operadores treinados no início do mês = operadores nas máquinas 
+ instrutores + operadores ociosos. 
Equação de balanço mensal: 
 Janeiro: 130 = 100 + X1 + X2  X1 + X2 = 30 
 Fevereiro: 130 + 7X1 = 150 + X3 + X4  7X1 - X3 - X4 = 20 
 Março: 130 + 7X1 + 7X3 = 200 + X5 + X6  7X1 + 7X3 - X5 - X6 = 70 
Treinees qualificados como 
operadores em jan 
Treinees qualificados como 
operadores em fev 
Treinees qualificados como 
operadores em mar 
Modelagem em Programação Linear 
 
19 
Uma indústria química 
 
 Dois produtos, A e B, são feitos a partir de duas operações 
químicas. Cada unidade do produto A requer 02 horas da operação 1 e 03 
horas da operação 2. Cada unidade do produto B requer 03 horas da 
operação 1 e 04 horas da operação 2. O tempo total disponível para a 
realização da operação 1 é de 16 horas, e o tempo total para a operação 2 
é de 24 horas. 
 
 A produção do produto B resulta, também, num subproduto C 
sem custos adicionais. Sabe-se que parte do produto C pode ser vendido 
com lucro, mas o restante deve ser destruído. Previsões mostram que no 
máximo 05 unidades do produto C serão vendidas, e sabe-se que cada 
unidade do produto B fabricada gera 02 unidades do produto C. 
 
Modelagem em Programação Linear 
 
20 
Sabe-se que: 
 
Produto A gera um lucro de $ 4 por unidade. 
Produto B gera um lucro de $ 10 por unidade. 
Produto C gera um lucro de $ 3 por unidade se for vendido. 
Produto C gera um custo de $ 2 por unidade se for destruído 
 Determinar um modelo de PL para tratar este problema, e 
encontrar quanto produzir de cada produto, de modo a maximizar 
o lucro da indústria química. 
Modelagem em Programação Linear 
 
21 
Observe que o lucro da venda do produto A é uma função linear, 
mas com respeito ao produto C isto não ocorre. 
Resolução do exemplo: Uma indústria química - produto A 
Quantidade 
 Lucro 
Produto A 
4 
Produto B 
10 
Quantidade 
Produto C 
-2 
Lucro 
3 
 5 
Modelagem em Programação Linear 
 
22 
2 X1 + 3 X2  16 (disponibilidade de tempo para operação 1) 
3 X1 + 4 X2  24 (disponibilidade de tempo para operação 2) 
X3 + X4 = 2 X2 (produção do produto C a partir do produto B) 
X3  5 (previsão de produto C que pode ser vendido) 
X1, X2, X3, X4  0 (não-negatividade) 
Restrições: 
Artifício: considerar as variáveis de decisão como sendo 
X1 = quantidade produto A produzida 
X2 = quantidade produto B produzida 
X3 = quantidade produto C vendida 
X4 = quantidade produto C destruída 
Função-objetivo: 
Max Z = 4 X1 + 10 X2 + 3 X3 – 2 X4 
Modelagem em Programação Linear 
 
23 
Oficina mecânica 
 
 Uma oficina mecânica tem 01 furadeira vertical e 05 fresas, 
que são usadas para a produção de conjuntos formados de 2 partes. 
Sabe-se qual é a produtividade de cada máquina na fabricação destas 
partes do conjunto: 
Furadeira Fresa 
Parte 1 03 20 
Parte 2 05 15 
Obs: tempo para produzir as partes dado em minutos. 
Modelagem em Programação Linear 
 
24 
O encarregado pela oficina deseja manter uma carga balanceada 
nas máquinas de modo que nenhuma delas seja usada mais que 30 
minutos por dia que qualquer outra, sendo o carregamento de 
fresamento dividido igualmente entre as 05 fresas. 
 
 
Achar um modelo de PL para dividir o tempo de trabalho entre as 
máquinas de modo a obter o máximo de conjuntos completos ao 
final de um dia, num total de 08 horas de trabalho. 
 
Modelagem em Programação Linear 
 
25 
Restrições: 
3X1 + 5X2  480 
(minutos por dia disponíveis para a furadeira) 
 
(20X1 + 15X2)/5 = 4X1 + 3X2  480 
(minutos por dia disponíveis para cada fresa) 
 
Resolução do exemplo: Oficina mecânica 
Variáveis de decisão: 
 X1 = número de partes 1 produzidas por dia 
 X2 = número de partes 2 produzidas por dia 
Modelagem em Programação Linear 
 
26 
Observe que esta última restrição não é linear, mas é equivalente 
a duas equações lineares que podem substituí-la: 
 
X1 - 2X2  30 e -X1 + 2X2  30 
 
X1, X2  0 (não-negatividade). 
 
|(4X1 + 3X2) - (3X1 + 5X2)| = |X1 -2X2|  30 
(Balanceamento de carga entre as máquinas) 
 
Modelagem em Programação Linear 
 
27 
“maximização do número de conjuntos completos por dia” 
Max Z = min (X1, X2) 
 
Observe que esta função não é linear, mas pode ser linearizada 
utilizando-se uma nova variável, da forma: 
 
Seja Y = min (X1, X2), Y  0, naturalmente tem-se duas novas 
restrições 
 
 Dadas por: Y  X1 e Y  X2. 
 
A função-objetivo linear fica sendo: Max Z = Y 
Função-objetivo: 
Modelagem em Programação Linear 
 
28 
Problema de dimensionamento de equipes de inspeção 
 
 Uma companhia deseja determinar quantos inspetores alocar 
à uma dada tarefa do controle da qualidade. As informações 
disponíveis são: 
 
 Há 08 inspetores do nível 1 que podem checar as peças a 
uma taxa de 25 peças por hora, com uma acuracidade de 98%, sendo 
o custo de cada inspetor deste nível $4 por hora; 
 
 Há 10 inspetores do nível 2 que podem checar as peças a 
uma taxa de 15 peças por hora, com uma acuracidade de 95%, sendo 
o custo de cada inspetor deste nível $3 por hora. 
Modelagem em Programação Linear 
 
29 
A companhia deseja que no mínimo 1800 peças sejam 
inspecionadas por dia (= 08 horas). 
 
Sabe-se, ainda, que cada erro cometido por inspetores no controle 
da qualidade das peças acarreta um prejuízo à companhia de $2 por 
peça mal inspecionada. 
 
Formular um modelo de PL para possibilitar a designação ótima do 
nº. de inspetores de cada nível de modo a otimizar o custo da 
inspeção diária da companhia. 
 
Modelagem em Programação Linear 
 
30 
 
Função objetivo: 
 
Minimizar C = custo total diário de inspeção ($/dia) 
onde : custo total = custo do salário dos inspetores + custo dos erros 
 
Min C = 8 *[(4X1 + 3X2) + 2 * (25*0,02X1 + 15*0,05X2)] 
Min C = 40X1 + 36X2 
Resolução do exemplo: Dimensionamento de equipes de inspeção 
Variáveis de decisão: 
Xi = nº. de inspetores do nível i (= 1, 2) alocados à inspeção. 
Prejuizo da inspeção ($$) 
Modelagem em Programação Linear 
 
31 
1. Quanto ao nº. de inspetores disponíveis: 
 X1  8 (inspetores do nível 1) 
 X2  10 (inspetores do nível 2) 
2. Quanto ao nº. de peças inspecionadas por dia: 
 8 * (25X1 + 15X2)  1800  5X1 + 3X2  45 
3. Restrições implícitas de não negatividade: 
 X1  0 
 X2  0. 
Restrições: 
Resolução gráfica de modelos de PL 
32 
Aplicável para modelos com 02 variáveis de decisão 
 
Útil para a ilustração de alguns conceitos básicos utilizados na 
resolução de modelos de maior porte. 
Etapas a serem seguidas na resolução gráfica 
 
1º Passo: identificara região viável do modelo, isto é, quais são os 
pares (X1, X2) que satisfazem a todas as restrições. 
 
2º Passo: achar a melhor solução viável, denominada Solução 
Ótima e denotada por (X1*, X2*), que leva ao valor ótimo da 
função-objetivo Z*. 
Resolução gráfica de modelos de PL 
 
33 
Problema de mix de Produção 
 
Fabricação de dois modelos de brinquedos: B1 e B2. 
 
• Lucros unitários/dúzia: $8 para B1 e $5 para B2 
• Recursos disponíveis: 
 1000 kg de plástico especial. 
 40 horas para produção semanal. 
 
• Requisitos do Departamento de Marketing: 
 Produção total não pode exceder 700 dúzias; 
 A quantidade de dúzias de B1 não pode exceder em 350 a 
quantidade de dúzias de B2. 
 
• Dados técnicos: 
 B1 requer 2 kg de plástico e 3 minutos por dúzia. 
 B2 requer 1 kg de plástico e 4 minutos por dúzia. 
Resolução gráfica de modelos de PL 
 
34 
A Gerência está procurando um 
programa de produção que aumente 
o lucro da Companhia. 
Resolução gráfica de modelos de PL 
 
35 
Variáveis de decisão: 
X2: produção semanal de B2 (em dúzias). 
X1: produção semanal de B1 (em dúzias). 
Função Objetivo: Maximizar o Lucro semanal 
Resolução gráfica de modelos de PL 
 
36 
 Max 8X1 + 5X2 (Lucro semanal) 
 
 sujeito a: 
 2X1 + 1X2 ≤ 1000 (Plástico - Kg) 
 3X1 + 4X2 ≤ 2400 (Tempo de produção - minutos) (40*60) 
 X1 + X2 ≤ 700 (Produção total) 
 X1 - X2 ≤ 350 (mix) 
 Xj  0, j = 1,2 (Não negatividade) 
Resolução gráfica de modelos de PL 
37 
Conceitos importantes: 
Os pontos (X1, X2) que satisfazem todas as restrições do 
modelo formam a Região Viável. 
Esses pontos são chamados de Soluções Viáveis. 
 
Usando a resolução gráfica pode-se representar todos as 
restrições (semi-planos), a função objetivo (reta) e os três 
tipos de pontos viáveis. 
Resolução gráfica de modelos de PL 
 
38 
1º Passo: 
 
 Traçar eixos cartesianos, associando a cada um deles uma 
variável de decisão. 
 
 No exemplo de fabricação de brinquedos: X1 para o eixo 
das abscissas e X2 para o eixo das ordenadas. 
 
 As restrições de não-negatividade, X1  0 e X2  0, 
implicam que os pares (X1, X2) viáveis estão no 1º quadrante 
dos eixos considerados. 
Resolução gráfica de modelos de PL 
 
39 
2º Passo: 
 
 Observar que a função-objetivo, ao se fixar um valor para Z, 
representa uma reta. Alterações neste valor de Z gera uma família de 
retas paralelas. 
 
 No exemplo dos brinquedos: considere a reta obtida fazendo 
Z= 2000, isto é , a reta dada por 8X1 + 5X2 = 2000. Percebe-se que ao se 
traçar retas paralelas no sentido de ficar mais afastado da origem (0, 0), o 
valor de Z aumenta. 
 
 De fato pode-se verificar que a reta paralela, que contém algum 
ponto da região viável, no caso o ponto ótimo X* = (320, 360), e está 
mais afastada da origem, corresponde a um valor ótimo da função 
objetivo Z* = 4360. 
Resolução gráfica de modelos de PL 
 
40 
Representando as condições de não negatividade 
X2 
X1 
Resolução gráfica de modelos de PL 
41 
Observar que no exemplo dos brinquedos, as restrições correspondem a 
semi-planos associados, respectivamente, às retas suportes dadas por: 
 
 2X1 + 1X2 = 1000 
 3X1 + 4X2 = 2400 
 X1 + X2 = 700 
 X1 - X2 = 350 
 Xj  0, j = 1,2 
 
Notar que cada reta suporte define dois semi-planos no espaço (X1, X2). 
Para identificar qual destes semi-planos é de interesse no caso, ou seja, 
contém os pontos que satisfazem a desigualdade da restrição, basta testar 
algum ponto à esquerda ou à direita (acima ou abaixo) da reta suporte da 
desigualdade. 
Um ponto que torna isto fácil é a origem (0, 0), mas poderia ser qualquer 
outro. 
Resolução gráfica de modelos de PL 
 
42 
1000 
500 
Viável 
X2 
Inviável 
Tempo de 
produção 
3X1+4X2  2400 
Restrição da produção total 
 X1+X2  700 (redundante) 
500 
700 
Restrição do plástico 
2X1+X2  1000 
X1 
700 
Resolução gráfica de modelos de PL 
 
43 
1000 
Viável 
X2 
Inviável 
Tempo de Produção 
3X1+4X2  2400 
 Restrição da produção total: 
 X1+X2 700 (redundante) 
500 
Restrição do mix da produção: 
X1-X2  350 
Restrição do plástico 
2X1+X2 1000 
X1 
700 
Resolução gráfica de modelos de PL 
44 
1000 
500 
Viável 
X2 
Inviável 
500 
700 
X1 
700 
Há três tipos de pontos viáveis. 
Pontos interiores. Pontos na fronteira. Pontos extremos. 
Resolução gráfica de modelos de PL 
 
45 
A busca por uma Solução Ótima: 
Começar com algum valor de lucro arbitrário, 
Por exemplo $2000... 
Depois aumentar o lucro, se possível... 
...e continuar até que seja inviável 
600 
700 
1000 
500 
X2 
X1 
X* = (320, 360) 
com Z* = 4.360 
46 
Pontos extremos e Soluções Ótimas 
Se o problema de Programação Linear tem uma Solução 
Ótima, um ponto extremo é Solução Ótima. 
 
Resolução gráfica de modelos de PL 
 
Resolução gráfica de modelos de PL 
 
47 
Visualização de situações possíveis 
 X2 
Solução 
única 
X1 
Z 
Z* 
Solução 
ilimitada 
Z 
X2 
 
X1 
Resolução gráfica de modelos de PL 
 
48 
Soluções Ótimas Múltiplas 
 Quando a função objetivo é paralela a alguma restrição. 
Todos os pontos do segmento de 
reta serão Soluções Ótimas. 
X* = X*1 + (1 - )X*2, com 0    1 
X*1 
X*2 
Resolução gráfica de modelos de PL 
 
49 
Múltiplas Soluções 
Ótimas 1 – 
Segmento de Reta 
Ótimo 
X1 
X* 
Z 
Z
* 
X2 
X2 
X1 
Múltiplas 
Soluções Ótimas 2 
Semi-reta Ótima 
Z* 
X* 
Resolução gráfica de modelos de PL 
 
50 
X2 
X1 
O conjunto 
viável é vazio. 
Há restrições 
incompatíveis. 
Problema 
inviável 
Forma padrão de modelo de PL 
 
51 
 
 Um modelo de PL com m restrições e n variáveis está na 
forma padrão se possuir as características abaixo: 
 
1. A função-objetivo é de minimização ou maximização; 
 
2. Todas as restrições estão na forma de igualdade; 
 
3. Todas as variáveis são não-negativas; 
 
4. As constantes de cada restrição são não-negativas. 
Forma padrão de modelo de PL 
 
52 
Modelo na forma padrão: 
 
Minimizar (ou maximizar) Z = C1 X1 + C2 X2 + ... + Cn Xn 
 
 
 
 
 
 Sujeito a: 













0. b ..., 0, b 0, b
0 X ..., 0, X 0, X
b = X A + ... + X A + X A
... ... ... ... 
... ... ... ... 
b = X A + ... + X A + X A
b = X A + ... + X A + X A
m21
n21
mnmn2m21m1
2n2n222121
1n1n212111
53 
Notação matricial para um modelo na forma padrão: 
 
Minimizar (ou maximizar) Z = C X 
 
 Sujeito a: 
 
 
Onde: A (m x n)  matriz de coeficientes tecnológicos 
 
 X (n x 1)  vetor das variáveis de decisão 
 
 b (m x 1)  vetor de demandas 
 
 C (1 x n)  vetor de custos (lucros) 








0. b
0 X
bAX
Forma padrão de modelo de PL 
 
54 
Redução de um modelo geral para a forma padrão 
 
O Método Simplex exige que o modelo esteja na forma padrão. 
 
 
Tratando com restrições na forma de inequações: 
 
Estas restrições são transformadas em equações através da 
introdução de novasvariáveis (não-negativas), chamadas de 
“variáveis de folga”. 
Forma padrão de modelo de PL 
 
Forma padrão de modelo de PL 
 
55 
Tratando com variáveis não-positivas: 
 
 
 Suponha que num determinado modelo há uma variável X1 
 0. 
 
 Basta substituí-la no modelo por uma nova variável não-
negativa X1’  0, dada por X1’ = – X1. 
Forma padrão de modelo de PL 
 
56 
Exemplo: 
 
Considere o problema de dimensionamento de equipes de 
inspeção: 
 
 
X1  8  X1 + X3 = 8, X3  0 é uma variável de folga. 
 
X2  10  X2 + X4 = 10, X4  0 é uma variável de folga. 
 
5 X1 + 3 X2  45  5 X1 + 3 X2 – X5 = 45, X5  0 é uma variável 
 de folga. 
 
Forma padrão de modelo de PL 
 
57 
Interpretação das variáveis de folga no exemplo: 
 
 
X3 = número de inspetores do nível 1 não utilizados. 
 
X4 = número de inspetores do nível 2 não utilizados. 
 
X5 = número (extra) de peças inspecionadas por dia, acima da 
quantidade mínima (1800) especificada pela empresa 
 
 
Variáveis de folga fornecem informações úteis sobre o problema. 
 
Forma padrão de modelo de PL 
58 
Tratando com variáveis livres (irrestritas em sinal): 
 
Em algumas situações exige-se o uso de variáveis que podem 
assumir tanto valores positivos, nulos, e negativos. Estas variáveis 
são chamadas de livres (free) ou irrestritas em sinal. 
 
Exemplo: Modelo de Planejamento Macroeconômico 
 
Uma das Variáveis de Decisão é a Taxa de Inflação que pode 
assumir qualquer valor positivo, nulo ou negativo (neste caso é 
conhecida como Deflação). 
 
Tratando com variáveis livres (irrestritas em sinal): 
 
59 
Estas variáveis devem ser eliminadas do modelo na forma padrão. Há, 
pelo menos, duas maneiras de se fazer isto: 
 
 1. Por substituição – utilizando uma das restrições do modelo, 
já na forma padrão (igualdade), procura-se expressar a variável livre 
como função das demais variáveis (não negativas) do modelo. A seguir 
eliminar a variável livre do modelo substituindo-a pela função 
escolhida na etapa anterior. A equação utilizada para expressar a 
variável livre como função das demais variáveis também será 
eliminada do modelo. 
 
 2. Por transformação – Suponha que a variável livre é S. Basta 
substituir em todas as restrições, e na função objetivo, a variável S por 
S = S’ – S”, com S’  0 e S”  0 sendo duas novas variáveis (auxiliares) 
no modelo. 
Forma padrão de modelo de PL 
 
 
 
 











livre X 0, X 0, X
3 5 = 2X X 3X
2 2 X + X X 
1 7 X + X + X 
321
321
321
3 21
Exemplo Completo 
 
Obtenha a forma padrão do modelo abaixo: 
 
Maximizar Z = X1 – 2X2 + 3X3 
 
 
 
 Sujeito a: 
60 
Forma padrão de modelo de PL 
 
61 
 
1. Introduzir variáveis de folga nas restrições (1) e (2): 
 
X1 + X2 + X3 + X4 = 7 (1’) com X4  0. 
X1 – X2 + X3 – X5 = 2 (2’) com X5  0. 
 
2. Multiplicar a restrição (3) por (– 1) para eliminar b3 = – 5 < 0: 
–3X1 + X2 + 2X3 = 5 (3’) 
 
3. Substituir X2 0 por X2’  0 através de X2’ = – X2: 
 Max Z = X1+ 2 X2’ + 3 X3 
 
 Sujeito a: 
 
 
 
 
 
 






'3' 5 = 2X + 'X 3X
'2' 2 = X X + 'X X 
'1' 7 = X + X + 'XX 
321
5321
4321
Forma padrão de modelo de PL 
 
62 
4. Eliminar X3: 
 
4.1. Substituição ou 4.2. Transformação 
 
Max Z = -2X1 + 5X2’ - 3X4 + 21 ou Max Z = X1 + 2X2’ + 3X3’ - 3X3’ 
 
 
s. a: s. a: 
 
 
 
Usando 
De (1’’): X3 = 7 – X1 + X2’ – X4 ou X3 = X3’ – X3’’ 








0 X ,X ,'X ,X
9= 2X + 'X 5X
5 = X + X '2X 
5421
421
542











0X ,X ,''X ,'X ,'X ,X
5= ''2X ''+2XX 3X 
2=X ''X 'X '+X+X 
7=X ''X 'X '+X X 
543321
332 1
53321
 4332 1
Definições e Teoremas em PL 
 
63 
Ponto central na resolução de modelos de PL é a solução de 
sistemas de equações lineares. 
 
Apresenta-se a seguir o Método de Eliminação de Gauss Jordan. 
 
 
 Considere o sistema de equações abaixo: 
 
(S1) 
 
 
 
 (nº variáveis >> nº equações) 
 
 




2 4 X X3XX X
1 2 X2X4XX2X
54321
54321
Definições e Teoremas em PL 
 
64 
• Conjunto solução de (S1) é a coleção de todos os valores de 
(X1, X2, X3, X4, X5) que satisfazem as equações (1) e (2) 
conjuntamente. 
 
• Dois sistemas são equivalentes se possuem o mesmo conjunto 
solução. 
 
• Sistemas equivalentes podem ser obtidos por meio de 
operações elementares sobre as linhas do sistema: 
 
 1. Multiplicar (dividir) qualquer equação por um nº. 
 
 2. Adicionar à qualquer equação uma Combinação Linear das 
demais equações. 
Forma Canônica 
 
65 
 Um sistema (S2) equivalente a (S1) pode ser obtido 
multiplicando-se a equação (1) por – 1 e adicionando-se o 
resultado à equação (2): 
 
(S2) 
 
 
 Um sistema (S3) equivalente a (S1) pode ser obtido 
multiplicando-se equação (4) por 2 e adicionando-se o resultado à 
equação (3): 
 
(S3) 
 
 
(S3) é denominado uma forma canônica do sistema original (S1). 





(4) 2 3X X + 2X X 
(3) 2X2X4XX2X
 5432
54321





(6) 2 = 3X X + 2X X 
(5) 6 = 4X 2X 3X X
5432
5431
Forma Canônica 
 
66 
Considere uma forma canônica de um sistema de equações lineares: 
(como (S3) anteriormente obtido) 
 
• Uma variável é dita ser variável básica para uma dada equação do 
sistema se ela possuir coeficiente 1 nesta equação e coeficientes 
nulos nas demais equações do sistema. 
 
Exemplo: em (S3) X1 e X2 são variáveis básicas 
 
• Variáveis que não satisfazem a condição acima são chamadas de 
variáveis não-básicas. 
 
Exemplo: em (S3) X3, X4, X5 são variáveis não-básicas. 
Solução Básica 
67 






M
N






2
5
A solução de um sistema na forma canônica, obtida fazendo-se as 
variáveis não-básicas iguais a zero, é chamada de uma solução 
básica (SB). 
Nº máximo de soluções básicas = 
 
Exemplo: 
Em (S3) fazendo-se X3 = X4 = X5 = 0  X1 = 6 e X2 = 2 formam 
uma solução básica. 
 
Nº de soluções básicas = = 10 
 
 
Uma Solução Básica Viável (SBV) de um sistema é uma solução 
básica onde todas as variáveis assumem valores não-negativos. 
 
Exemplo: a solução básica do exemplo anterior é uma SBV. 
Pivoteamento 
 
68 
Operações de Pivoteamento são as operações elementares 
aplicadas à um sistema para transformar uma dada variável em 
variável básica. São usadas pelo método de eliminação de 
Gauss Jordan. Deve-se identificar o elemento Pivô – que deve 
ser transformado em 1 e os demais elementos da sua coluna 
que devem ser transformados em 0. 
 
 
Para obter uma forma canônica de um sistema basta aplicar 
uma sequência de operações de pivoteamento (método de 
Gauss Jordan) de modo se conseguir uma variável básica 
associada com cada equação. 
Método de Eliminação de Gauss Jordan 
 
69 
Artifício para a realizaçãode operações de pivoteamento: 
 
Considere o sistema (S) abaixo: 
 
 (S) 
 
Achar (S’) uma forma canônica de (S) de modo que X1 seja a 
variável básica associada com a equação (1), e X3 seja a variável 
básica associada com a equação (2). 





(2) 2 = X 4X + X
(1) 4= X6+X2X2
321
321
Método de Eliminação de Gauss Jordan 
 
70 
VB X1 X2 X3 b Operações Elementares Feitas 
 
 
 
 X1 2 -2 6 4 (1) - Pivô em azul 
 
 X3 -1 4 -1 2 (2) 
(S’) 
 
 
Solução básica (não é viável): X1 = – 4 (Variável básica) 
X3 = 2 (Variável básica) X2 = 0 (Variável não básica) 
 
 

 
2 = X+ X3/2 
4 = X2/11X
32
21
 X1 1 -11/2 0 -4 (1’’) = (1’) - 3*(2’’) 
 
 X3 0 3/2 1 2 (2’’) = (2’)/2 – Equação do Pivô 
 X1 1 -1 3 2 (1’) = (1)/2 - Equação do Pivô 
 
 X3 0 3 2 4 (2’) = (2) + (1’) – Pivô em Azul 
Teoremas em PL 
 
71 
Teorema 1 
 
Dado um modelo já na forma padrão, as soluções básicas viáveis do 
sistema de equações, correspondente às restrições do modelo, estão 
associadas a pontos extremos do conjunto de soluções viáveis do 
modelo original. 
 
 
Teorema 2 
 
Se um modelo de Programação Linear possui Solução Ótima então 
pelo menos um ponto extremo, do conjunto de soluções viáveis do 
modelo original, corresponde a uma Solução Ótima. 
Comentários Gerais 
 
72 
Procedimento simplista para resolver um modelo de PL 
 
• Gerar todas as possíveis soluções básicas viáveis. 
 
• Determinar qual das soluções básicas viáveis corresponde ao 
melhor valor da função-objetivo. 
 
Problemas: 
1. Nº de soluções básicas viáveis pode ser excessivo. 
 
2. Modelo pode apresentar solução ilimitada ou ainda ser inviável. 
 
Observe que problemas de médio porte, que aparecem na prática, 
costumam envolver centenas de variáveis (valor de n) e milhares de 
restrições (valor de m).