Capítulo I: Programação Linear Investigação Operacional

1. Problemas de Programação Linear (PPL)

Programação Linear (PL)- conjunto de técnicas que permitem resolver os problemas

de optimização no sistema de recursos limitados, sendo lineares quer a função objectivo
quer as restrições.

Problemas de Programação Linear - são problemas de maximização ou minimização

de função de variáveis designada por objectivo, que depende de um número finito de
variáveis. Estas variáveis podem ser independentes uma das outras ou podem estar
relacionadas através de uma ou mais restrições.

1.1 Formulação do Problema de PL

O modelo matemático (PL) inclui três conjuntos fundamentais de elementos sendo eles:
a) Variáveis de decisão e Parâmetros: as variáveis de decisão são as incógnitas para
serem determinadas da solução do modelo. Os parâmetros representam as variáveis
controladas do sistema. Os parâmetros podem ser determinísticos ou probabilísticos.

b) Limitações ou Restrições: para considerar as limitações físicas do sistema, o

modelo deve incluir restrições que limitam os valores possíveis das variáveis de decisão.
Isto é, usualmente, expresso em forma de equações e/ou inequações matemáticas. Por
exemplo, seja x1 e x2 o número de unidades produzidas de dois produtos (variáveis de
decisão) e seja a1 e a2 a matéria prima (recursos) por unidade (parâmetro). Se o total dos
recursos disponíveis é A, a função restritiva é dada por a1x1+a2x2=A.

c) Função objectivo (FO): Define a medida de efectividade do sistema como uma

função matemática de suas variáveis de decisão. Por exemplo, se objectivo do sistema é
maximizar o lucro total, a função objectiva deve especificar o lucro em termos das
variáveis de decisão, isto é MaxZ=C1x1+C2x2+...+Cnxn .

1.2 Construção do modelo matemático

Antes da construção de um modelo matemático deve-se responder a 4 perguntas:
i. Qual a medida de efectividade do objectivo? Isto é, como será expressa a solução
do problema (em reais economizados, unidades vendidas, itens produzidos, etc.)
Lucas Jamisse Pág. 1
Capítulo I: Programação Linear Investigação Operacional

ii. Quais são os factores sob controle (variáveis controladas)? Isto é, quais aspectos
do problema podem-se fazer alguma coisa?
iii. Quais são os factores não controlados (as variáveis não controladas)? Isto é, quais
aspectos do problema têm-se de aceitar como dados?
iv. Quais são as relações entre estes factores e os objectivos? Isto é, pode esta relação
ser expressa em forma de relações matemáticas que constituirão um modelo de
problema?

1.2.1 Modelos de Programação (optimização) linear - Modelos de apoio a decisão

Os parâmetros do modelo de PL para um problema onde estào envolvidas n –
actividades e m – recursos podem ser definidos utilizando a seguinte tabela:
Utilização de recursos
Recursos por actividade Total de recurso
1 2 3 .... n disponível (bi)
1 a11 a12 a13 ..... a1n b1
2 a21 a22 a23 ..... a2n b2
.... ..... ..... ..... ..... ..... .....
m am1 am2 am3 ..... am n bm
Lucro / custo unitário C1 C2 C3 ..... Cn
Nível das Actividades X1 X2 X3 ..... Xn

Representaçào do modelo de Programação linear

Maximização Minimização
Max .Z  c1 x1  c2 x2  ...  cn xn Min.Z  c1 x1  c2 x2  ...  cn xn
a11 x1  a12 x2  ...  a1n xn  b1 a11 x1  a12 x2  ...  a1n xn  b1
a x  a x  ...  a  b a x  a x  ...  a  b
 21 1 22 2 2n 2  21 1 22 2 2n 2

Suj. a .......... ........ Suj. a .......... ........

a x  a x ....  a x  b a x  a x ....  a x  b
 m1 1 m 2 2 mn n m
 m1 1 m 2 2 mn n m

 xi  0, i  1, ..., n  xi  0, i  1, ..., n

aij, bi, ci são as constantes; xj sào as variáveis de decisão.

Lucas Jamisse Pág. 2

Capítulo I: Programação Linear Investigação Operacional

Exemplo 1.1 Um refeitório de uma fábrica de pré-fabricados para construção fornece pequenas
refeições aos seus trabalhadores. Um dos pratos confeccionados é constituído à base de dois
produtos alimentares. Sabendo que 1 kg de produto 1 custa 300$ e fornece 200 calorias e 22
unidades de gordura, e 1 kg de produto 2 custa 1000$ e fornece 400 calorias e 7 unidades de
gordura, preparar a dieta mais económica de modo a conter pelo menos 250 calorias mas não
mais do que 20 unidades de gordura.
Resolução
Este é um exemplo típico de um problema de programação linear. Para tornar claro , as relações
entre o objectivo e as restrições apresenta-se a tabela.
Elemento Nutritivo Produtos alimentares
Necessidades
Produto 1 Produto 2
Calorias 200 400 250
Gordura 22 7 20
Custo unitário ($) 300 1000

Variáveis de decisão: X1- Peso do produto 1 e X2-Peso do produto 2

Modelo matemático correspondente é:
Min.imizar W  300 X 1  1000X 2
200 X 1  400 X 2  250

Sujeto a 22 X 2  7 X 2  20
X , X  0
 1 2

1.3 Método Matricial

- A solução básica admissível inicial (SBA0) é formada por variáveis de folga (+Xi). Portanto, o
problema de maximização (minimização), ao transformar para a forma padrão introduz-se uma
variável de folga para cada restição do tipo A  b j .

-Se uma submatriz Bm*m (quadrada) da matriz A do sistema de equações correspondentes às

restrições (na forma padrão) é não singular, isto é, o determinante de Bm*m é não nulo, então
Bm*m designa-se Base.
- As m variáveis x1, x2, ...,xm correspondentes às colunas de Bm*m , designam-se por variáveis
básicas e as restantes n-m variáveis xm+1, ...,xn designam-se por variáveis não básicas.
- Se todas as variáveis básicas da solução básica X=( x1, x2, ...,xm, 0, ..., 0) são não negativas
então X é uma solução básica admissível (SBA).

Lucas Jamisse Pág. 3

Capítulo I: Programação Linear Investigação Operacional

- Se alguma variável básica x1, x2, ...,xm for igual a zero, a solução básica designa-se por solução
básica degenerada.

Exemplo 1.2 A fábrica de gelados Derretem-se na Boca SARL fabrica duas qualidades de
gelados: cassata de nozes (C) e pistachio de frutas (P). A loja encontra-se localizada numa
animada área turística de modo que toda a produção é sempre vendida. Um cone de C custa
75,00Mtn enquanto um cone de P custa 60,00Mtn. Um cone de C necessita de 4 gr de mistura de
frutas e de 2gr de noz moída. Um cone de P requer 6gr de mistura de frutas e 1gr de noz moída.
Contudo, apenas podem ser produzidas por hora 96gr de mistura de frutas e 24gr de noz moída.
a) Quantos cones de cada tipo devem ser fabricados de modo a maximizar a receita em cada
hora?
Resolução
Modelo procurado: Forma padrão:

Determinação das SBA pela forma matricial (Gauss-Jordan)

SBA0:
x1 x2 x3 x4 b0 x3 x4
 4 6 1 0 96 1 0
A=   , B= 0 1 , O determinante de B é não nulo, então o
2 1 0 1 24  

1 0  x 3  96
sistema BX B  b0 tem solução única, i. é, B  0  BX B  b0   *     ,
0 1  x 4  24
SBA : X  (0,0,96,24).
SBA1:

x1 x2
 4 6 4 6  x1  96
B1 =   , B1  0  B1 X B  b0   *    
2 1 2 1  x 2  24

tem sol.única, SBA1 : X  (6,12,0,0).

Lucas Jamisse Pág. 4

Capítulo I: Programação Linear Investigação Operacional

SBA2:

x1 x3
4 1 4 1  x1  96
B2 =   , B 2  0  B 2 X B  b 0  2 0 *  x   24
 2 0    3  
tem sol.única, SBA2 : X  (12, 0, 48, 0).
SBA3:

x1 x4
 4 0 4 0  x1  96
B3 =   , B 3  0  B 3 X B  b0    *      , Dado que x 4  0 a sol. é única e não
2 1 2 1  x 4  24
admissível  SBNA3 : X  (24,0,0,24) .

SBNA4:

X2 x3
6 1  6 1  x 2  96
B4 =   , B 4  0  B 4 X B  b0   *     ,
1 0 1 0  x3  24
x 3  0  SBNA4 : X  (0,24,48,0) .
SBNA5:

X2 x4
6 0  6 0  x 2  96
B5 =   , B 5  0  B 5 X B  b0   *    
1 1 1 1  x 4  24
tem sol.única  SBA5 : X  (0,16, 0, 8).

Lucas Jamisse Pág. 5

Capítulo I: Programação Linear Investigação Operacional

O problema do exemplo 1.2, tem 6 soluções básicas, das quais, apenas 4 correspondem a pontos
extremos de K (k=região admissível), i.é, apenas 4 são SBA.
Ponto extremo Variáveis Base Solução Natureza
de K não básicas Básica da solução
B=(0,0) x1, x2 x3, x4 X  (0,0,96,24) SBA
B1=(6, 12) x3, x4 x1, x2 X  (6,12,0,0) SBA
B2=(12, 0) x2, x4 x1, x3 X  (12, 0, 48, 0) SBA
B5=(0, 16) x1, x3 x2, x4 . X  (0, 16, 0, 8) SBA
B3=(24, 0) x2, x3 x1, x4 X  (24,0,0,24) SBNA
B4=(0, 24) x1, x4 x2, x3 X  (0,24,48,0) SBNA
Demostra-se que X B  B 1b0 onde B 1 é a matriz inversa de B.

Para maximizar a receita devem ser produzidos 6 cones do tipo C e 12 cones do tipo P. Portanto,
a solucão óptima é B1=(6, 12) com Zmax=1170, 00 Mtn.

1.4 Resolução de problemas de PL pelo método Gráfico

Os problemas com apenas duas variáveis podem resolver-se graficamente com grande facilidade.
A existência de um número superior de variáveis de decisão torna os problemas de difícil
resolução gráfica, pelo que nestes casos este processo não tem sentido.
-Se existe um valor óptimo da função objectivo num PPL, este valor ocorre em um ou mais
pontos extremos da região das soluções admissíveis.

Exemplo 1.3 Considere o problema do exemplo 1.2 :

a) Resolva-o graficamente.
Resolução
r1: 4x1+6x2=96 r2: 2x1+x2=24 rZ: 75x1+60x2=0
x1 x2 x1 x2 x2
x1
0 16 0 24 0 0
24 0 12 0 4 -5

Lucas Jamisse Pág. 6

Capítulo I: Programação Linear Investigação Operacional

Transladando (traçar rectas paralelas à recta Z=0) a recta Z=0 até atingir o ponto
extremo máximo: B1 = r1∩r2
Resolvendo as equações :
 x1  6
4 x  6 x 2  96 Sol. óptima (única): B1 
r1  r2   1  x 2  12 Z opt.  1170
2 x1  x 2  24

Exemplo 1.4 Considere o seguinte problema de PL (minimização).

MinimizarW  3x1  2 x2
 x1 3
 x2  4

 x  x  5
Suj a  1 2
 x1  5 x 2  5
5 x1  2 x2  10

 xi  0, i  1, 2
Resolva-o graficamente:
Resolução
W  3x1  2 x2  0  Rz
 x1  3  r1
 x2  4  r 2
As equações são: 
 x1  x2  5  r 3


 x1  5 x 2  5  r 4
5 x1  2 x2  10  r 5


 xi  0, x2  0

Lucas Jamisse Pág. 7

Capítulo I: Programação Linear Investigação Operacional

Recta1 Recta2 Recta3 Recta4 Recta5 RectaZ

X1 X2 X1 X2 X1 X2 X1 X2 X1 X2 X1 X2
3 R R 4 0 5 0 1 0 5 0 0
-- -- -- -- 5 0 5 0 2 0 -2 3

Transladando a recta Z até atingir o ponto extremo mínimo: A = r4∩r5

Resolvendo as equações :
 x  5 x2  5
r4  r5   1
5 x1  2 x2  10
Sol. óptima (única):
 x1  40 / 23

 x2  15 / 23 Z opt.  150 / 23

Lucas Jamisse Pág. 8

Capítulo I: Programação Linear Investigação Operacional

1.5 Exercícios Propostos

1.5.1 - Formule os modelos matemáticos correspondetes a PPL

Exercício 1.1. A empresa Sementes de Moçambique (SEMOC), pretende semear arroz e milho,
dispondo para tal de áreas que não excedem, respectivamente, 3 e 4 hectare nos arredores de
Boane. Por outro lado, as suas disponibilidades em trabalho são apenas de 9 horas diárias.
Admitindo que, por cada hectare semeado de arroz é necessário 1 hora de trabalho diário e por
cada hectare de milho são necessárias 2 horas. Sabendo que por cada hectare de arroz semeado o
lucro é de 5 u.m. e por cada hectare de milho 2 u.m, formule o problema como um problema de
programação linear.

Exercício 1.2. A companhia Pintados de fresco produz tinta para interiores e exteriores. A tinta é
fabricada por meio da transformação de 2 tipos de matéria prima: A e B. A companhia tem
acessíveis diariamente um máximo de 6 toneladas de A e 8 de B. Para produzir 1 ton. de tinta de
exteriores são necessárias 1ton. de A e 2 ton. de B, enquanto para produzir 1 ton. de tinta de
interiores são necessárias 2ton. de A e 1ton. de B, em cada dia. Um estudo de mercado concluiu
que a procura diária de tinta de interiores não pode exceder a da tinta de exteriores em mais de
1ton. O preço de venda por tonelada é 3u.m. para a tinta de exteriores e 2u.m. para a tinta de
interiores. Pretende-se determinar o esquema de produção a adoptar para maximizar a receita
diária.
a) Construa um modelo matemático de PL para o problema, explicitando as variáveis de decisão,
restrições e função objectivo. Encontre a solução do problema.

Exercício 1.3. Uma pequena manufatura produz dois modelos, Standart e Luxo, de um certo
produto. Cada unidade do modelo standart requer 3 horas de lixação e 1 hora de polimento. Cada
unidade do modelo de luxo exige 1 hora de lixação e 4 horas de polimento. A fábrica dispõe de 2
lixadores e 3 polidores, cada uma trabalha 40 horas semanais. As margens de lucro são 24 e 32
unidades de medida, respectivamente, para cada unidade standart e luxo. Não existem restrições
de demanda para ambos os modelos. Elabore um modelo de programação linear que permita
calcular a produção semanal que maximiza a margem total de lucro do fabricante.

Exercício 1.4 O senhor João Obadias é vendedor de frutas, ele pode transportar 1200 caixas de frutas para o
mercado grossista de zimpeto. O Obadias já transporta 300 caixas de laranjas a 25 u.m de lucro por

Lucas Jamisse Pág. 9

Capítulo I: Programação Linear Investigação Operacional

caixa por mês. Ele necessita transportar pelo menos 150 caixas de pêssegos a 13 u.m. de lucro por caixa, e
no máximo 220 caixas de tangerinas a 40 u.m. de lucro por caixa.
a) De que forma deverá o senhor Obadias carregar o caminhão para obter o lucro máximo?

Exercício 1.5. Uma pessoa precisa de 10, 12, e 12 unidades dos produtos químicos A, B e C,
respectivamente para o seu jardim. Um produto liquido contém 5, 2 e 1 unidades de A, B e C,
respectivamente por vidro; um produto em pó contém 1, 2 e 4 unidades de A, B e C,
respectivamente por caixa. Se o produto líquido custa 3u.m. por vidro e o produto em pó custa
2u.m. por caixa, quantos vidros e quantas caixas ele deve comprar para minimizar o custo e
satisfazer as necessidades?

Exercício1.6. Uma rede de televisão local tem o seguinte problema: foi descoberto que o
programa A com 20minutos de música e 1 minuto de propaganda chama a atenção de 30.000
telespectadores, enquanto o programa B, com 10 minutos de música e 1 minuto de propaganda
chama atenção de10.000 telespectadores. No decorrer de uma semana, o patrocinador insiste no
uso de no mínimo, 5 minutos para sua propaganda e que não há verba para mais de 80 minutos
de música. Quantas vezes por semana cada programa deve ser levado ao ar para obter o número
máximo de telespectadores?

Exercício1.7. Uma empresa produz dois bens, A e B. A margem bruta do produto A é de 40

u.m./tonelada e do produto B é 30 u.m./tonelada. A unidade de produção compõe-se de três
secções: corte, mistura e embalagem, cujo equipamento pode ser utilizado 9 horas por dia. O
processo da produção caracteriza-se do seguinte modo: o produto A é primeiro cortado e depois
embalado, enquanto o produto B é primeiro misturado e depois embalado. Cada tonelada do
produto A utiliza 1/2 hora da secção de Corte e 1/3 da secçào de Embalagem. Cada tonelada do
produto B utiliza 1 hora da secção de mistura e 2/3 da secçào de embalagem.
Construa um modelo matemático de PL de modo a maximizar a margem bruta total, explicitando
as variáveis de decisão, restrições e função objectivo.

Lucas Jamisse Pág. 10

Capítulo I: Programação Linear Investigação Operacional

1.6 Resolução de problemas de PL pelo método Simplex

Método Simplex- é um algoritmo que permite resolver os PPL.

1.6.1 Algoritmo Simplex

Passo1. Reescrever o problema na forma padrão:

-identificar uma SBA0 inicial.
Passo2. Construir o quadro simplex (tabela preliminar simplex):
-Calcular os custos reduzidos (Cj-Zj ou Zj –Cj, j=1...n).
Passo3. Avaliar a optimalidade da solução:
-se todos custos reduzidos forem não positivos (Cj-Zj≤0 ou Zj –Cj≤0) a SBA0 é uma
solução óptima (tabela terminal), caso contrário determinar o elemento pivô da seguinte
forma:
a) escolhe-se na linha dos custos reduzidos o maior elemento positivo, e a coluna que
contem este elemento chama-se coluna pivô.
b) divide-se cada termo independente pelo correspondente elemento positivo da coluna
pivô. A linha que apresentar o menor quociente positivo é chamada linha pivô.
c) o elemento que se situa no cruzamento entre a linha pivô e a coluna pivô é chamado
pivô.
Passo4. Construir uma nova tabela simplex, aplicando o método de redução de Gauss-
Jordan:
-Determinar a variável não básica que entra ( aquela com maior custo reduzido) e
variável que sai (aquela com menor quociente).
-Reduzir a 1 o número pivô, dividindo toda linha pivô pilo pivô.
-Reduzir a zero as outras componentes da coluna pivô da seguinte formula:
nova linha = linha – (componente da coluna pivô* nova linha pivô).
i
-calcular a nova SBA

Passo5. Avaliar a optimalidade de solução:

i
-Se todos os custos reduzidos forem não positivos (Cj-Zj≤0 ou Zj –Cj≤0) a SBA é uma

solução óptima (tabela terminal) , caso contrário, repetir o passo4 até encontrar a tabela
terminal (sem elemento pivô).

Lucas Jamisse Pág. 11

Capítulo I: Programação Linear Investigação Operacional

Exemplo 1.5 Considere o problema do exemplo 1.2 :

Resolução:
Forma padrão:
Adicionar as variáveis de folga Xi, i=3,4 para cada
restrição:

 4 6 1 0
  I  B
 2 1 0 1

Tabela Preliminar simplex

Cj 75 60 0 0
Cb Xb X1 X2 X3 X4 bj
0 X3 4 6 1 0 96 → l1
0 X4 2 1 0 1 24 → l2
Zi 0 0 0 0 0
Cj-Zi 75↑ 60 0 0

Primeira iteração
0 X3 0 4 1 -2 48 →l 1
'
 l1  4 * l 2''

75 X1 1 1/2 0 1/2 12 → l 2'  l2

2
Zi 75 75/2 0 75/2 900
Cj-Zi 0 45/2↑ 0 -75/2

Tabela terminal
60 X2 0 1 1/4 -1/2 12 → l1'  l1
4
75 X1 1 0 -1/8 3/4 6 → l2 ' 1
 l 2  * l1''
2
Zi 75 60 45/8 105/4 1170
Cj-Zi 0 0 -45/8 -105/4

Solução optima: X=(6, 12, 0, 0) Zmax =1170

Lucas Jamisse Pág. 12

Capítulo I: Programação Linear Investigação Operacional

Exemplo 1.6 Resolva o seguinte PPL pelo método simplex.

MaximizarZ  2 x1  3x 2
2 x1  x 2  6
x  2x  8

Suj a  1 2

 x1  x 2  1
 xi  0, i  1, 2
Resolução:
Forma Padrão:
Adicionar as variáveis de folga Xi, i=3,4,5 para
cada restrição:
Max.Z  2 x1  3x 2  0 x3  0 x 4  0 x5
 2 1 1 0 0
2 x1  x 2  x3  0 x 4  0 x5  6  
x  2x  0x  x  0x  8  1 2 0 1 0
 1 2 3 4 5
1 1 0 0 1
Suj. a   
 x1  x 2  0 x3  0 x 4  x5  1
 x  0, i  1,5 I  B
 i
Tabela Preliminar simplex inicial
Cj 2 3 0 0 0
Cb Xb X1 X2 X3 X4 X5 bi
0 X3 2 1 1 0 0 6 → l1
0 X4 1 2 0 1 0 8 → l2
0 X5 1 -1 0 0 1 1 → l3
Zi 0 0 0 0 0 0
Cj-Zi 2 3 ↑ 0 0 0
1ª iteração
0 X3 3/2 0 1 -1/2 0 2 → l1 '  l1  1 * l 2'
3 X2 1/2 1 0 1/2 0 4 → l2'  l1
2
0 X5 3/2 0 0 1/2 1 5 → l 3  l 3  1 * l 2'
'

Zi 3/2 3 0 3/2 0 12
Cj-Zi 1/2↑ 0 0 -3/2 0
2ª iteração (Tabela terminal)
2 X1 1 0 2/3 -1/3 0 4/3 → l1' 
' 2
l1
3
3 X2 0 1 -1/3 2/3 0 10/3 → l2 '  l2 
1 ''
* l1
2
0 X5 0 0 -1 1 1 3 → l3 '
3
 l 3  * l1''
2
Zi 2 3 1/3 4/3 0 38/3
Cj-Zi 0 0 -1/3 -4/3 0

Solução óptima: X=(4/3; 10/3; 0; 0;3) Z=38/31

Lucas Jamisse Pág. 13
Capítulo I: Programação Linear Investigação Operacional

1.7 Restrições do tipo A  b ou A  b

O processo iterativo do método simplex sempre exige uma SBA0 a partir da qual se busca
uma solução óptima. Nos problemas de maximização com restrições do tipo A  b , esta
SBA0 era formada pelas variáveis de folga. No entanto, no caso de existirem restrições do
tipo A  b ou A  b para as quais os termos independentes (b) são não negativos (com
excepção das restrições de não negatividade), a introdução das variáveis de folga não
conduz à obtenção directa de uma SBA0.

Deste modo, depois de o modelo de PL estar apresentado na forma padrão, é necessário a

criação de um conjunto de varáveis artificiais. Por forma a identificar uma SBA0 para o
problema, não tendo estas variáveis qualquer significado quer de ordem econômica quer
de natureza física.

Portanto, para resolver estes PPL de não existência de uma SBA0 é aplicado o
procedimento Dual, os métodos de grande M, de duas fases e o Dual-simlex, que são
modificações do método simplex directo.

Obs.: O problema de maximização (ou minimização), ao transformar para a forma padrão

introduz-se uma variável de excesso (-Xi) e uma variável artificial (+ai) para cada restição do
tipo A  b j e introduz-se apenas a variável artificial (+ai) para cada restição do tipo A  b .

1.7.1 Método de grande M

Este método é caracterizado por penalizar as variáveis artificiais na função objectivo por
um M arbitrariamente muito grande. Os sinais desses coeficientes serão negativos para
problemas de maximização e positivos para problemas de minimização.

A solução encontrada utilizando este método, será a solução do problema se:

- o óptimo for obtido sem a existência de variáveis artificiais na base.
- atingir um óptimo com variáveis artificiais na base mas de valor nulo.

Lucas Jamisse Pág. 14

Capítulo I: Programação Linear Investigação Operacional

1.7.1 Método de duas fases

Neste método um PPL é resolvido em duas fases distintas.

-A primeira fase começa com a passagem ao problema auxiliar, minimizando a soma das
variáveis artificiais (função objectivo artificial-Za) que constituem a base, quer o
problema inicial seja de minimização, quer seja de maximização. Efectua-se em seguida
o algorítmo simplex para o problema auxiliar. Portanto, qualquer solução do problema
inicial é igualmente solução do problema auxiliar com as variáveis artificiais todas nulas
(Za=0).

-Na segunda fase do problema procede-se à eliminação, do quadro simplex, das variáveis
artificiais, efectuando-se em seguida a resolução do problema inicial usando o algorítmo
primal do simplex, dado que é conhecida uma SBA0, obtida na primeira fase.

Exemplo 1.7 Resolva o seguinte PPL pelo método simplex de Grande M

MinimizarW  75x1  60x 2
4 x1  6 x 2  96

Suj a 2 x1  x 2  24
 x  0, i  1, 2
 i
Resolução:
Forma padrão:
Adicionar a variável de folga X1 na primeira Adicionando a variável artificial a na
restrição: segunda restrição:
MinimizarW  75x1  60x 2  0 x3 MinimizarW  75x1  60x 2  0 x3  Ma
4 x1  6 x 2  x3  96 4 x1  6 x 2  x3  0a  96
  4 6 1   4 6 1 0
Suj a 2 x1  x 2  0 x3  24   Suj a 2 x1  x 2  0 x3  a  24  
 x  0, i  1, 2,3  2 1 0  x , a  0, i  1, 2,3  2 1 0 1
 i  i
naoI  naoB I  B

Tabela Preliminar simplex inicial

Cj 75 60 0 +M
Cb
Xb X1 X2 X3 a bj
0 X3 4 6 1 0 96 → l1
M a 2 1 0 1 24 → l2
Zi 2M M 0 M 24M

Lucas Jamisse Pág. 15

 Capítulo I: Programação Linear Investigação Operacional

Zi-Cj 2M-75↑ M-60 0 0

0 X3 0 4 1 -2 48 →l 1
'
 l1  4 * l 2''

75 X1 1 1/2 0 1/2 12 → l 2'  l2

2
Zi 75 75/2 0 75/2 900
Zi-Cj 0 -45/2 0 75/2-M

Sol óptima: X=(12; 0; 48;0) ZMIN=900

Exemplo 1.8 Resolva o seguinte PPL pelo método simplex das duas fases
MinZ  720x1  880x 2  160x3
2 x1  4 x 2  3x3  6

S .a 4 x1  4 x 2  3

 xi  0, i  1,3 Resolução

Forma padrão:
Adicionando as variáveis de excesso (- x4 e -x5) Adicionando as variáveis artificiais (a1 e a2)
nas restrições: nas restrições:
MinZ  720x1  880x 2  160x3  0( x4  x5) MinZ a  a1  a2
2 x1  4 x 2  3x3  x 4  6 2 x1  4 x 2  3x3  x 4  a1  6
 
S .a 4 x1  4 x 2  x5  3 S .a 4 x1  4 x 2  x5  a 2  3
x  0  x  0, a  0
 i  i i

2 4 3 1 0  2 4 3 1 0 1 0 
   
 4 4 0 0  1 4 4 0 0 1 0 1 
Nao I  NaoBase I  bsse, I  (a1 a 2)
1ª Fase :MinZ=a1+a2
Tabela Preliminar simplex inicial(1ª Fase)
Cj 0 0 0 0 0 1 1
Cb Xb X1 X2 X3 X4 X5 a1 a2 bi
1 a1 2 4 3 -1 0 1 0 6
1 a2 4 4 0 0 -1 0 1 3
Zj 6 8 3 -1 -1 1 1 9
Zj-cj 6 8 3 -1 -1 0 0
1ª Iteração(1ª Fase)
1 a1 -2 0 3 -1 1 1 1 3
0 x2 1 1 0 0 -1/4 0 1/4 3/4
Zj -2 0 3 -1 1 1 1 3
Zj-cj -2 0 3 -1 1 0 0

Lucas Jamisse Pág. 16

Capítulo I: Programação Linear Investigação Operacional

2ª Iteração (Tabela terminal-1ª Fase)

0 X3 -2/3 0 1 -1/3 1/3 1/3 1/3 1
0 x2 1 1 0 0 -1/4 0 1/4 3/4
Zj 0 0 0 0 0 0 0 0
Zj-cj 0 0 0 0 0 -1 -1

2ª fase:MinZ=720x1+880x2+160x3
Cj 0 0 0 0 0
Cb Xb x1 x2 x3 x4 x5 bi
160 X3 -2/3 0 1 -1/3 1/3 1
880 x2 1 1 0 0 -1/4 3/4
Zj 2320/3 880 160 -160/3 -500/3 820
Zj-cj 160/3 0 0 -160/3 -500/3
1ª Iteração (Tabela terminal-2ª fase)
160 X3 0 0 1 -1/3 1/6 3/2
720 X1 1 1 0 0 -1/4 3/4
Zj 720 720 0 -160/3 -460/3 780
Zj-cj 0 -160 -160 -160/3 -460
Sol. óptma: X=(3/4, 0, 3/2, 0, 0), Z=780

1.8 Casos Especiais nos PLL

Nos problemas anteriores de PL a solução óptima e única era obtida num ponto extremo do
domínio solução, no entanto, podem ocorrer os seguintes casos:
1.8.1 - Óptimo não finito - O PLL não tem óptimo finito, geralmente quando as restrições estão
mal elaboradas, pois tendo recursos finitos não se poderia aumentar infinitamente os lucros ou
despesas. Analiticamente, ocorre o seguinte:
-No quadro simplex todas as componentes da coluna pivô são não positivas e a variável em
questão está em condições ( C j  Z j  0 ou Z j  C j  0 ) de entrar na base.

1.8.2 - Óptimas alternativas - O PLL tem duas ou mais soluções (solução múltipla), quando a
função objectivo assume o seu valor óptimo em mais de um ponto extremo. Analiticamente,
ocorre o seguinte:
-No quadro simplex óptimo existe alguma variável não básica com custo reduzido nulo
( C j  Z j  0 ou Z j  C j  0 ) com pelo menos uma componente positiva na correspondente

coluna do quadro. Outras soluções podem ser obtidas pela seguinte

fórmula

X *   x1  (1   ) x2 onde   (0, 1) , X *  SBNA, x1  SBA e x 2  SBA

Lucas Jamisse Pág. 17

Capítulo I: Programação Linear Investigação Operacional

1.8.3 - Problema Impossível - O PLL não tem nenhuma solução, quando as restrições não
apresentam um plano comum. Analiticamente, ocorre o seguinte:
-No quadro simplex existe algum termo independente negativo e todos os custos reduzidos são
não positivos ( C j  Z j  0 ou Z j  C j  0 ).

1.8.4 - Empate no critério de saída da base - Devido à ocorrência de empate no critério de saída
da base,o algoritmo primal do simplex pode entrar em ciclo em situações de degenerência. Por
esta razão, aplica-se a técnica de perturbação que garante a não ocorrência de um ciclo durante
todo o processo de cálculo. Esta técnica consiste no seguinte:
-Passar a matriz identidade às primeiras colunas do quadro simplex;
-Perturbar os termos independentes, calculando os quocientes entre as componentes da primeira

linha nas colunas das variáveis onde existe o empate, tal que min{ 1 , 0 } 0,
a1n a(1i ) n
assim sendo, a variável correspondente a (1+i)-ésima linha sai da base.

Exemplo 1.9 Resolva o seguinte PPL pelo método simplex das duas fases
Minimizar Z  2 x1  x 2
4 x1  2 x 2  12

Suj a 2 x1  x 2  6
 x  0, i  1, 2
 i
Resolução
Forma padrão:
Adicionando as variáveis de folga (x3) e de Adicionando a variável artificial a1
excesso (- x4) nas restrições: Na segunda restrição:
MinZ  2 x1  x2  0 x3  0 x4 MinZ a  a1
4 x1  2 x 2  x3  0 x 4  12 4 x1  2 x 2  x3  0 x 4  0a1  12
 
S .a 2 x1  x 2  0 x3  x 4  6 S .a 2 x1  x 2  0 x3  x 4  a1  6
x  0 x  0
 i  i
4  2 1 0   4  2 1 0 0
   
2 1 0 1   2 1 0  1 1
Nao I  NaoBase I  Base
1ª fase: MinZ a  a1
Cj 0 0 0 0 1
cb Xb X1 X2 X3 X4 a1 bj
0 X3 4 -2 1 0 0 12
1 a1 2 1 0 -1 1 6
Zj 2 1 0 -1 1 6
Lucas Jamisse Pág. 18
Capítulo I: Programação Linear Investigação Operacional

Zj-Cj 2 ↑ 1 0 -1 0
Método de perturbação
Cj 0 1 0 0 0
cb xb X3 a1 X1 X2 X4 bj
0 X3 1 0 4 -2 0 12
1 a1 0 1 2 1 -1 6
Zj 0 1 2 1 -1 6
Zj-Cj 0 0 2 1 -1
Min{1/4; 0/2}=0 → a1 sai da base
0 X3 1 -2 0 -4 2 0
0 X1 0 1/2 1 1/2 -1/2 3
Zj 0 0 0 0 0 0
Zj-Cj 0 -1 0 0 0

3 
 
3 0   2 
1 1  1 
seja   ; X *   0    6    3  com Zopt=6
2 2  2   
0  24  12 
 
 

Resolvendo o exemplo anterior pelo método gráfico:

Resolução

Lucas Jamisse Pág. 19

Capítulo I: Programação Linear Investigação Operacional

Este é um caso especial, pois a função objectivo

alcança o seu valor máximo em qualquer ponto do
segmento de recta B1B3.
Existem duas SBA óptimas com o valor óptimo 6:
- X1=(3,0,0)-que corresponde ao ponto B1=(3,0)
-X2=(0,6,24) -que corresponde ao ponto B3=(0,6)
Qualquer outra solução não básica admissível (SNBA)
óptima, X* , é obtida como combinação linear convexa
de X* e X* , atribuindo a  valores numéricos
diferentes entre 0 e 1.
Portanto, A SBNA óptima X*=(3/2, 3, 12) corresponde
ao ponto B2=( 3/2, 3) do segmento de recta B1B3.
Sol. Múltiplas ou óptimas alternativas.

Exemplo 1.9.1 Considere o seguinte problema de PL.

Maximizar Z  3x1  x 2
 x1  x 2  1

Suj a 2 x1  x 2  6
 x  0, i  1, 2
 i
Resolva-o graficamente:
Resolução
Recta1 Recta2 RectaZ
X1 X2 X1 X2 X1 X2
0 -1 0 6 0 0
1 0 3 0 -1 3

Este é um caso especial, pois não existe o

limite máximo sobre a RA .
Transladando a recta Z sobre a regiao
admissível, Z não chega a atingir o
extremo máximo.
Sol. infinidade de soluções

Lucas Jamisse Pág. 20

Capítulo I: Programação Linear Investigação Operacional

1.6 Exercícios propostos

1.6.1 Resolva cada um dos seguintes problemas aplicando o método adequado

a) Maximizar Z  x1  2 x 2 b) MaximizarZ  2 x1  3 x2
 x1  2 x 2  3  x1  x2  7
 2 x  3 x  12
Suj a  x1  x 2  3 
 x  0, i  1, 2 Sujeito a  1 2

 i  x1  5

 xi  0, i  1, 2
Sol.: x(0, 3) Z=6
Sol.: x(0, 7) Z=21

c) MaximizarW  75x1  60 x 2 d ) MinimizarZ  3 x1  2 x2  4 x3

4 x1  6 x 2  96 2 x1  x2  3 x3  60
 
Suj a 2 x1  x 2  24 Suj a 3 x1  3 x2  5 x3  120
 x  0, i  1, 2  x  0, i  1, 3
 i  i

Sol.: x=(0, 24, 48, 0) Zmax=1440 Sol.: x(0, 15, 15) Z=90

f ) Maximizar Z  3x2
e) MinimizarW   x1  x2
 x1  x2  1
 x1  x2  1 3x  2 x  12
6 x  4 x  24 
 Suj a  1 2
Suj a  1 2
x  2 x2 5
 1
 x2  2 
  xi  0, i  1, 2
 xi  0, i  1, 2
Sol.: Infinidade de soluções
Sol.: óptimas alternativas
x1=2(6), x2=2 W=4(6)

h) Maximizar Z  3x1  4 x 2
g ) MaximizarW  x1  2 x 2  3x 3
 x1  2 x 2  4
 x1  2 x 2  4 
 Suj a  x1  x 2  3
Suj a  x1  2 x3  5
 x  0, i  1, 2
 x  0, i  1, 2,3  i
 i
Sol. : Não Admissível
Sol. X := (0; 2; 5/2; 0) Z = 23/2

Lucas Jamisse Pág. 21

Capítulo I: Programação Linear Investigação Operacional

1.6.2 Resolva os seguintes exercícios de revisão

Referências:
Fazenda , Rodrigues (2013)- Operational Research - UEM
Mulenga, A. C. (1999)-Introduçào ao processo decisório-UEM, Maputo.
Ramalhete, Guerreiro e Magalhães, (1984)- Investigação operacional
TAHA, HA (1997) – Operational Research- an Introduction, 6th edition, Prentice-Hall
Internacional, Inc. USA

Lucas Jamisse Pág. 22