3.

DUALIDADE E ANÁLISE DE SENSIBILIDADE

3.1 DUALIDADE EM PROGRAMAÇÃO LINEAR

Todo o problema de programação linear, a que chamamos primal, tem associado a ele um
correspondente problema, chamado dual; ambos são complementares e relacionados de
forma que a solução óptima de um fornece informações completas sobre o outro.

3.1.1 TRANSFORMAÇÃO DE UM PROBLEMA PRIMAL EM DUAL

Seja dado o seguinte problema de programação linear, na forma literal ou canónica,

problema primal.

Maximizar z = c1x1+c2x2+c3x3+...+cmxm
a11 x1 + a12 x 2 + a13 x3 + ... + a1m x m ≤ b1
a 21 x1 + a 22 x 2 + a 23 x3 + ... + a 2 m x m ≤ b2
Sujeito à − − − − − − − − − − − − − − − − − − − − −
a n1 x1 + a n 2 x 2 + a n3 x3 + ... + a nm x m ≤ bn
xi ≥ 0; i = 1, m ; j = 1, n

O seu problema dual pode ser escrito na forma canónica assim.

Minimizar w = b1y1+b2y2+b3y3+...+bnyn
a11 y1 + a 21 y 2 + a 31 y 3 + ... + a n1 y n ≥ c1
a12 y1 + a 22 y 2 + a 32 y 3 + ... + a n 2 y n ≥ c 2
Sujeito à − − − − − − − − − − − − − − − − − − − − −
a1m y1 + a 2 m y 2 + a3m y 3 + ... + a nm y n ≥ c m
yi ≥ 0; i = 1, m ; j = 1, n

As variáveis yj são chamadas variáveis duais.

O problema dual, para os modelos em que o conjunto das restrições tem um único tipo de
desigualdades por exemplo ≥ ou ≤, é construído a partir do primal da seguinte forma:

Regras:
Regra 1. Cada linha do problema primal (restrição), corresponde a uma variável no dual
(coluna);
Regra 2. Os termos independentes das restrições (recursos), passam para coeficientes da
função objectivo no dual;
Regra 3. Se o primal é um problema de maximização, o seu dual será um problema de
minimização e vice- versa;
Regra 4. As variáveis do primal e dual são não negativas.
Exemplo 3.1. Apresentar o problema dual do seguinte problema de maximização de
programação linear.

Max z = x1 + 2x2
x1 + 5 x 2 ≤ 18
2 x1 + x 2 ≤ 15
Sujeito à 5 x1 − 2 x 2 ≤ 20
0 x1 + x 2 ≤ 8
xi ≥ 0

O problema dual correspondente é: Min w = 18y1+15y2+20y3+8y4

y1 + 2 y 2 + 5 y 3 + 0 y 4 ≥ 1
Sujeito à 5 y1 + y 2 − 2 y 3 + 1 y 4 ≥ 2
yi ≥ 0

Voltando a transformação de um primal no seu dual, consideremos a forma matricial dos

problemas:

Problema Primal Problema Dual

x1 y1
x2 y2
Max z = (c1 c 2 ... c m ) • Min w = (b1 b2 ... bn ) •
... ...
xm yn
a 11 a 12 ... a 1m x1 b1 a 11 a 21 ... a n1 y1 c1
a 21 a 22 ... a 2m x2 b2 a 12 a 22 ... a n2 y2 c2
Suj à • ≤ Suj à • ≥
..................... ... ... ..................... ... ...
a n1 a n2 ... a nm xm bn a 1m a 2m ... a nm yn cm

A seguinte tabela mostra as relações entre o problema primal e dual.

Problema Primal Problema Dual

• n restrições e m variáveis • m variáveis e n restrições
• coeficientes da função objectivo • constantes
• constantes • coeficientes da função objectivo
Problema (max) Problema (min) Problema (max) Problema (min)
Restrição (P) Variável (D) Variável (P) Restrição (D)
≥ ⇔ ≤ 0 ≥ 0 ⇔ ≥
≤ ⇔ ≥ 0 ≤ 0 ⇔ ≤
= ⇔ não restrita não restrita ⇔ =

!"
Da representação matricial, pode-se concluir que os coeficientes do problema dual são
formados pela matriz transposta dos coeficientes do problema primal.

Primal max Z = CX min W = BY ⇐ Dual

AX ≤ B At Y ≥ C
Suj à Suj à
X ≥0 Y ≥0

Onde A é matriz dos coeficientes do problema primal e At é a matriz transposta de A,

calculada trocando as linhas com as colunas de A.

Exemplo 3.2. Formar o dual do problema.

Min w = 4x1 + 8x2
3 x1 + 7 x 2 ≥ 40
1x1 − 1x 2 ≥ 18
Sujeito à
5 x1 + 1x 2 = 22
xi ≥ 0

Resolução
O problema primal tem 3 restrições, portanto 3 variáveis duais sendo a terceira não
restrita.

Etapa 1. transformar a equação em duas inequações.

Min w = 4x1 + 8x2

3 x1 + 7 x 2 ≥ 40
1x1 − 1x 2 ≥ 18
Sujeito à 5 x1 + 1x 2 ≥ 22
− 5 x1 − 1x 2 ≥ −22
xi ≥ 0

Etapa 2. Escrever o dual correspondente com y3 = y3+- y3-

Max z = 40y1 + 18y2 + 22y3+ - 22y3- Max z = 40y1 + 18y2 + 22y3

3 y1 + 1 y 2 + 5 y 3+ − 5 y 3− ≤ 4 3 y1 + 1 y 2 + 5 y 3 ≤ 4
+ −
Suj à 7 y1 − 1 y 2 + 1 y − 1 y ≤ 8 ou
3 3 Suj à 7 y1 − 1 y 2 + 1 y 3 ≤ 8
+ −
y i ≥ 0; y ≥ 0; y ≥ 0
3 3 y i ≥ 0; y 3 nao restrito

!#
3.1.2 INTERPRETAÇÃO ECONÓMICA DAS VARIÁVEIS DUAIS

As variáveis duais podem receber uma interpretação económica, que leva ao cálculo da
utilidade marginal (preço de sombra, valor marginal, etc.) dos recursos. Vejamos as
relações das suas soluções através de um exemplo.

Exemplo 3.3. Uma indústria dispõe de três recursos A, B e C, em quantidades limitadas,

com os quais pretende produzir dois produtos: produto 1 e produto 2. A tabela a baixo dá
a utilização unitária de cada recurso em cada um dos produtos e a disponibilidade de cada
recurso. A indústria sabe que cada unidade produzida do produto 1 dá uma margem
unitária de lucro de 5 u.m., e cada unidade produzida do produto 2 dá uma margem
unitária de lucro de 6 u.m. O problema da programação da produção da empresa é
determinar a quantidade a ser feita dos produtos 1 e 2, de forma a maximizar a margem
total de lucro.

Recurso Recurso gasto para fazer 1 unidade de Disponibilidade

Produto 1 Produto 2
A 1 2 14
B 1 1 9
C 7 4 56

Resolução
Problema 1:
Maximizar z = 5x1 + 6x2
1x1 + 2 x 2 ≤ 14
1x1 + 1x 2 ≤ 9
Sujeito à
7 x1 + 4 x 2 ≤ 56
xi ≥ 0

Suponhamos que a indústria tenha a alternativa de vender os recursos A, B e C, em vez

de empregá-los na produção dos dois produtos.

O problema agora é encontrar o valor de cada unidade do recurso. É evidente que a venda
dos recursos deve fornecer um ganho pelo menos igual ao obtido com a utilização deles
na produção.

Sejam
y1 valor do recurso A por unidade;
y2 valor do recurso B por unidade e
y3 valor do recurso C por unidade

O valor total do estoque dos recursos é: 14y1 + 9y2 + 56y3

!$
Por outro lado, cada um dos produtos pode ser avaliado, levando em conta a utilização
dos recursos por unidade fabricada. Assim, o produto 1 gasta 1 unidade do recurso A, 1
unidade de B e 7 unidades de C, sua avaliação em termos do conteúdo de recurso é:
1y1 + 1y2 + 7y3

Para o produto 2, analogamente a avaliação é: 2y1 + 1y2 + 4y3

É claro que essas avaliações dos produtos não podem ser inferiores as margens unitárias
de lucro fornecidas por cada um. Assim podemos escrever:

Produto1. 1y1+1y2+7y3 ≥ 5
Produto 2. 2y1+1y2+4y3 ≥ 6

Neste conjunto de inequações o administrador tem interesse em determinar o valor

mínimo do estoque total, tendo em conta que as avaliações dos produtos sejam pelo
menos iguais aos lucros unitários fornecidos. Em termos de programação linear, estamos
a descrever o problema dual.

Problema 2
Minimizar W = 14y1+9y2+56y3
1 y1 + 1 y 2 + 7 y 3 ≥ 5
Sujeito à 2 y1 + 1 y 2 + 4 y 3 ≥ 6
yi ≥ 0

Conforme as definições anteriores, o problema 1 é primal e o problema 2 é o dual.

Portanto, as variáveis duais podem ser interpretadas como avaliações unitárias dos
recursos relativos as contribuições de cada um para a obtenção do lucro total. Isto
significa que, resolvidos os problemas, as variáveis duais indicam as variações que
ocorrem no valor da função objectivo do primal, para variações unitárias nos níveis dos
recursos.

Resolução do problema primal

Atenção: vamos designar de yi as variáveis de folga.

Maximizar Z = 5x1 + 6x2 +0y1+0y2+0y3

1x1 + 2 x 2 + 1 y1 + 0 y 2 + 0 y 3 = 14
1x1 + 1x 2 + 0 y1 + 1 y 2 + 0 y 3 = 9
Sujeito à
7 x1 + 4 x 2 + 0 y1 + 0 y 2 + 1 y 3 = 56
xi ≥ 0; y i ≥ 0

!
Tabela simplex inicial
Base x1 x2 y1 y2 y3 bi
y1 1 2 1 0 0 14 → (7)
y2 1 1 0 1 0 9 → (9)
y3 7 4 0 0 1
56 → (14)
Z -5 -6 0 0 0 0
a
1 iteração
Base x1 x2 y1 y2 y3 bi
x2 1/2 1 1/2 0 0 7 → l1’=1/2l1
y2 1/2 0 -1/2 1 0 2 → l2’=l2-l1’
y3 5 0 -2 0 1
28→ l3’=l3-4l1’
z -2 0 3 0 0 42→ l4’=l4+6l1’
a
2 Iteração
Base x1 x2 y1 y2 y3 bi
X2 0 1 1 -1 0 5 → l1’=l1-1/2l2’
x1 1 0 -1 2 0 4 → l2’=2l2’
y3 0 0 3 -10 1
8 → l3’=l3-5l2’
Z 0 0 1 4 0 50→ l4’=l4+2l2’

Solução primal: x1= 4; x2 = 5; y1 = 0; y2 = 0; y3 = 8 e Zmax = 50

Resolução do problema dual. Designando por xi as variáveis de excesso e ai as variáveis

artificiais, logo estamos numa escolha entre o método de grande M e o método de duas
fases; vamos optar pelo método de duas fases.
Minimizar W = 14y1+9y2+56y3+0x1+0x2+0a1+0a1
1 y1 + 1 y 2 + 7 y 3 − 1x1 + 0 x 2 + 1a1 + 0a 2 = 5
Sujeito à 2 y1 + 1 y 2 + 4 y 3 + 0 x1 − 1x 2 + 0a1 + 1a 2 = 6
y i ≥ 0; xi ≥ 0; a i ≥ 0

Tabela inicial simplex (1a fase)

base Y1 y2 y3 x1 x2 a1 a2 bi
a1 1 1 7 -1 0 1 0 5 → (0.71)
a2 2 1 4 0 -1 0 1 6 → (1.5)
W -14 –9 -56 0 0 0 0 0
Za -3 -2 -11 1 1 0 0 -11
1a Fase (iteração 1)
base y1 y2 y3 x1 x2 a1 a2 bi
y3 1/7 1/7 1 -1/7 0 1/7 0 5/7 →l1’=1/7l1
a2 10/7 3/7 0 4/7 -1 -4/7 1 22/7 →L2’=l2-4l1’
W -6 –1 0 -8 0 8 0 40 →L3’=l3+56l1’
Za -10/7 -3/7 0 -4/7 1 11/7 0 -22/7→l4’=l4+11l1’

!!
1a Fase (iteração 2)
base y1 y2 y3 x1 x2 a1 a2 bi
y3 0 1/10 1 -1/5 1/10 1/5 –1/10 2/5 →l1’=l1-1/7l2’
y1 1 3/10 0 2/5 -7/10 –2/5 7/10 11/5 →L2’=7/10l2’
W 0 4/5 0 –28/5 –21/5 28/5 21/5 266/5 →L3’=l3+6l2’
Za 0 0 0 0 0 1 1 0 →l4’=l4+10/7l2’

Za = 0; a1 = 0 e a2 = 0, logo devemos passar para a segunda fase.

Tabela simplex inicial (2a fase)

base y1 y2 y3 x1 x2 bi
y3 0 1/10 1 -1/5 1/10 2/5 → (4)
y1 1 3/10 0 2/5 -7/10 11/5 → (22/3)
W 0 4/5 0 –28/5 –21/5 266/5→
a
2 fase (iteração 1)
base y1 y2 y3 x1 x2 bi
y2 0 1 10 -2 1 4 → l1’=10l1
y1 1 0 -3 1 -1 1 → l2’=l2-3/10l1’
W 0 0 -8 -4 -5 50 → l3’=l3-4/5l1’

Solução dual y1=1; y2 = 4; y3 = 0; x1 = 0; x2 = 0 com Wmin = 50

Comparando as duas tabelas terminais e as soluções obtidas chega-se as conclusões ou

relações:

Relação 1. Para quaisquer duas soluções viáveis possíveis do primal e dual, tem-se
Z≤W exemplo z = 42 e w = 266/5.

Relação 2. As soluções óptimas dos dois problemas guardam entre se a relação:

Max Z = Min W Zmax = Wmin = 50

Relação 3. Os valores das variáveis duais podem ser obtidos da solução do problema
primal, bastando tomar os coeficientes da última linha das variáveis básicas iniciais. Se o
dual é de maximizar, lemos os valores tal como estão, caso contrário lemos com o sinal
oposto, portanto:

Saindo de max (P) para min (D)

Solução primal: x1 = 4; x2 = 5; y1 = 0; y2 = 0; y3 = 8; Zmax = 50
Solução dual: y1 = 1; y2 = 4; y3 = 0; x1 = 0; x2 = 0; Wmin = 50

Saindo de min (P) para max (D)

Solução primal: y1 = 1; y2 = 4; y3 = 0; x1 = 0; x2 = 0; Wmin = 50
Solução dual: x1 = 4; x2 = 5; y1 = 0; y2 = 0; y3 = 8; Zmax = 50

!%
Além da aplicação ao estudo de casos na empresa, a dualidade permite-nos entre outros
casos:
1. Já que a resolução dos problemas de minimização pelo método de duas fases, leva
muitas iterações, uma alternativa é usar a dualidade para obter a solução primal.

2. Resolução rápida dos problemas de programação linear. De facto, em muitos casos o

dual tem menos tabelas simplex que o primal, sempre que o número de restrições do
primal exceder o número de variáveis.

3. Resolução de problemas de teoria de jogos. Na determinação da estratégia óptima e

do valor de um jogo de duas pessoas de soma nula, aplicam-se os conceitos da
dualidade. Pois, o modelo matemático de um jogo pode ser convertido num problema
de programação linear e as estratégias óptimas de cada jogador serão as soluções do
primal e do dual.

Exemplo 3.4. Resolver o seguinte problema de minimização usando o procedimento

dual.

Minimizar W = 3y1 + 2y2

y1 + 2 y 2 ≥ 10
y1 + y 2 ≥ 8
Sujeito à
2 y1 + y 2 ≥ 12
yi ≥ 0

Resolução
Max Z = 10x1 + 8x2 + 12x3 + 0y1 + 0y2
1x1 + 1x 2 + 2 x3 + 1 y1 + 0 y 2 = 3
Sujeito à 2 x1 + 1x 2 + 1x3 + 0 y1 + 1 y 2 = 2
xi ; y i ≥ 0

Tabela simplex inicial

base x1 x2 x3 y1 y2 bi
Y1 1 1 2 1 0 3 → (1.5)
y2 2 1 1 0 1 2 → (2)
Z -10 -8 -12 0 0 0
a
1 Iteração
base x1 x2 x3 y1 y2 bi
X3 1/2 1/2 1 1/2 0 3/2 → l1’=1/2l1
y2 3/2 1/2 0 -1/2 1 1/2 → l2’=l2-l1’
Z -4 -2 0 6 0 18→ l3’=l3+12l1’

!&
2a Iteração
base x1 x2 x3 y1 y2 bi
X3 0 1/3 1 2/3 –1/3 4/3→l1’=l1-1/2l2
x1 1 1/3 0 -1/3 2/3 1/3 →l2’=2/3l2
Z 0 -2/3 0 14/3 8/3 58/3→ l3’=l3+4l2’

3a Iteração – Tabela terminal simplex

base x1 x2 x3 y1 y2 bi
x3 -1 0 1 1 –1 1 →l1’=l1-1/3l2
x2 3 1 0 -1 2 1 → l2’= 3l2
Z 2 0 0 4 4 20→l3’=l3+2/3l2’

Solução primal: y1 = 4; y2 = 4; x1 = 2; x2 = 0; x3 = 0; Wmin = 20

Solução dual : x1 = 0; x2 = 1; x3 = 1; y1 = 0; y2 = 0; Zmax = 20

Antes de introduzir a análise de sensibilidade importa referir algumas propriedades que

facilitam as operações nas relações entre o problema primal e dual. Para isso voltemos ao
exemplo 3.3 do parágrafo 3.1.2 e apresentemos novamente a resolução do problema
primal

Problema 1: Problema 2
Maximizar Z = 5x1 + 6x2 Minimizar W = 14y1+9y2+56y3
1x1 + 2 x 2 ≤ 14
1 y1 + 1 y 2 + 7 y 3 ≥ 5
1x1 + 1x 2 ≤ 9
Sujeito à Sujeito à 2 y1 + 1 y 2 + 4 y 3 ≥ 6
7 x1 + 4 x 2 ≤ 56
yi ≥ 0
xi ≥ 0

Resolução do problema 1.
Maximizar Z = 5x1 + 6x2 +0y1+0y2+0y3
1x1 + 2 x 2 + 1x3 + 0 x 4 + 0 x5 = 14
1x1 + 1x 2 + 0 x3 + 1x 4 + 0 x5 = 9
Sujeito à
7 x1 + 4 x 2 + 0 x3 + 0 x 4 + 1x5 = 56
xi ≥ 0
Tabela simplex inicial
Base x1 x2 x3 x4 x5 bi
x3 1 2 1 0 0 14 → (7)
x4 1 1 0 1 0 9 → (9)
x5 7 4 0 0 1
56 → (14)
Z -5 -6 0 0 0 0

!'
1a iteração
Base x1 x2 x3 x4 x5 bi
x2 1/2 1 1/2 0 0 7 → l1’=1/2l1
x4 1/2 0 -1/2 1 0 2 → l2’=l2-l1’
x5 5 0 -2 0 1
28→ l3’=l3-4l1’
Z -2 0 3 0 0 42→ l4’=l4+6l1’
a
2 Iteração
Base x1 x2 x3 x4 x5 bi
x2 0 1 1 -1 0 5 → l1’=l1-1/2l2’
x1 1 0 -1 2 0 4 → l2’=2l2’
x5 0 0 3 -10 1
8 → l3’=l3-5l2’
Z 0 0 1 4 0 50→ l4’=l4+2l2’
Solução primal: x1= 4; x2 = 5; x3 = 0; x4 = 0; x5 = 8 e Zmax = 50
Solução dual : y1 = 1; y2 = 4; y3 = 0; y4 = 0; y5 = 0; Wmin = 50

Propriedade 1. Em qualquer iteração do método simplex, no primal ou dual, a matriz

que aparece sob as variáveis básicas usadas na solução inicial (variáveis de folga, de
excesso ou artificiais), pode ser usada para gerar as contribuições unitárias para o valor
da função objectivo (coeficientes da última linha do quadro simplex, designados por ∆i).

A prática desta propriedade pode ser vista em três passos:

Passo 1. Identificar os coeficientes originais da função objectivo correspondentes às

variáveis básicas na actual iteração e escrevê-los num vector linha, na mesma ordem das
linhas da tabela simplex.

Passo 2. Multiplicar o vector resultante pela matriz que aparece sob as variáveis iniciais
na respectiva iteração.

Passo 3. Subtrair os coeficientes originais da função objectivo correspondente às

variáveis básicas da solução inicial dos respectivos coeficientes obtidos no passo 2.

Demonstração da propriedade 1.
Passo 1: No problema 1, anterior na 2a iteração as variáveis básicas são: x2, x1, x5 cujos
coeficientes da função objectivo são (6, 5, 0)
(x2 x1 x5 )
(6 5 0)

Passo 2: A matriz que aparece nessa iteração sob as variáveis básicas iniciais (variáveis
de folga) é:
1 -1 0
-1 2 0
3 - 10 1

!(
Multiplicando o vector linha pela matriz dos coeficientes das variáveis básicas temos:

1 -1 0
(6 5 0 )• -1 2 0 = (1 4 0)
3 - 10 1

Passo 3: Subtraindo o vector resultante aos valores iniciais das variáveis básicas iniciais
obtemos os resultados da terceira linha na iteração final.

Para a variável x3: ∆3 = 1 – 0 = 1

Para a variável x4: ∆4 = 4 – 0 = 4
Para a variável x5: ∆5 = 0 – 0 = 0

Os valores obtidos por esta propriedade são chamados multiplicadores do simplex e são
valores óptimos das variáveis duais. Outros nomes usados são: custos implícitos, custos
de oportunidade ou preços de sombra.

Propriedade 2. Em qualquer iteração do primal ou dual os valores das variáveis na base

podem ser obtidos pela multiplicação da matriz definida na propriedade 1, pelo vector
coluna contendo os valores originais dos recursos (vector dos termos independentes).

Demonstração da propriedade 2.

a) Na 1a iteração, os valores das variáveis básicas são:

x2 1/2 0 0 14 7
x4 = - 1/2 1 0 • 9 = 2
x5 -2 0 1 56 28

b) Na 2a iteração, os valores das variáveis básicas são:

x2 1 -1 0 14 5
x1 = -1 2 0 • 9 = 4
x5 3 - 10 1 56 8

o que confirma os resultados obtidos na iteração final.

Propriedade 3. Em qualquer iteração do primal ou dual, os coeficientes de qualquer

variável nas restrições podem ser obtidos pela multiplicação da matriz definida na
propriedade 1, pelo vector coluna contendo os coeficientes originais da mesma variável
nas restrições.

!
Demonstração da propriedade 3.
2
a) Os coeficientes originais de x2 na tabela simplex inicial são: 1
4
a
Na 2 iteração, os coeficientes de x2 são obtidos pelo produto:

1 -1 0 2 1
-1 2 0 • 1 = 0
3 - 10 1 4 0
1
b) Os coeficientes originais de x3 na tabela simplex inicial são: 0
0
a
Na 2 iteração, os coeficientes de x3 são obtidos pelo produto:

1 -1 0 1 1
-1 2 0 • 0 = −1
3 - 10 1 0 3

Propriedade 4. Em qualquer iteração do método simplex, a substituição das variáveis

duais pelos respectivos multiplicadores do simplex, relativos a variáveis básicas da
solução inicial, permite obter os coeficientes da equação Z transformada, pela diferença
entre o primeiro membro e segundo das restrições correspondentes do dual.

Demonstração da propriedade 4.

Na 1a iteração do problema 1, temos os seguintes multiplicadores do simplex relativos as

variáveis básicas na solução inicial.

Para a variável x3: ∆3 = 3 → variável dual y1

Para a variável x4: ∆4 = 0 → variável dual y2
Para a variável x5: ∆5 = 0 → variável dual y3

As restrições duais correspondentes a x1 e x2 são respectivamente:

x1 → 1 y1 + 1 y 2 + 7 y 3 ≥ 5
x 2 → 2 y1 + 1 y 2 + 4 y3 ≥ 6

Os coeficientes de Z transformado são obtidos substituindo y1 por ∆3; y2 por ∆4 e y3 por

∆5. Assim:

%"
Para x1: 1*3 + 1*0 + 7*0 – 5 = -2, logo ∆1 = -2
Para x2: 2*3 + 1*0 + 4*0 – 6 = 0, logo ∆2 = 0

O que confere com os resultados obtidos na resolução do problema. Como ∆1 < 0, isto
significa que a solução ainda não é óptima, x1 deve entrar na base e por outro lado a
solução do dual não é viável, o que nos leva a concluir que:

• Enquanto o primal não for óptimo, o dual será inviável;

• As restrições do dual, correspondentes às variáveis básicas, são satisfeitas como

equações, o que significa que a respectiva variável de excesso é nula;

• O problema primal começa com uma solução viável não óptima que deve ser
optimizada, enquanto que o dual começa com uma solução inviável com valor
superior ao óptimo e continua inviável até que a solução óptima seja atingida.

3.2 MÉTODO DUAL – SIMPLEX

Até agora, nos problemas de programação linear que consideramos era obrigatório que
todos os elementos do lado direito da tabela simplex fossem positivos. Isto significa que
todas as soluções eram viáveis. Pela propriedade 4, sabemos que as soluções duais são
inviáveis até que a solução óptima seja obtida. No entanto é possível que durante o
processo de solução, venhamos a ter uma solução dual viável, o que significa inviável no
primal.

O método Dual – Simplex se destina a resolver esse tipo de problema. As diferenças em

relação ao método simplex se resumem nas regras de entrada e saída de variáveis na base.

Dado um problema de minimização para resolvé-lo pelo método Dual - Simplex deve-se
transformar as inequações do tipo ≥ para ≤ , em seguida aplicar as regras 1 e 2 para o
problema de minimização.

Regra 1. Variável que sai: é a variável básica com o valor mais negativo. Se todas as
variáveis básicas tiverem valores positivos, a solução é óptima.

Regra 2. Variável que entra: é escolhida entre as variáveis fora da base, da seguinte
forma:
• Dividir os coeficientes do lado esquerdo da equação z transformada (coeficientes da
função objectivo) pelos correspondentes coeficientes negativos da equação da
c
variável que sai. ij = i ; a ij < 0
a ij

%#
• A variável que entra é a que tem o menor valor entre os quocientes encontrados (para
o problema de minimização) ou o menor valor absoluto (para o problema de
maximização).

Quando, em ambos os casos, não houver coeficientes negativos na linha da variável que
sai da base, o problema não tem solução viável.

Exemplo 3.5. Resolver o seguinte problema pelo método dual - simplex.

Minimizar W = 2x1 + 1x2
4 x1 + 3 x 2 ≥ 6
Sujeito à 1x1 + 2 x 2 ≤ 3
xi ≥ 0
Resolução
Para resolver o problema sem usar o método de duas fazes nem do grande M, vamos
escrever o problema na forma padrão e introduzimos depois as variáveis de folga.

Minimizar W = 2x1 + 1x2 Min W = 2x1 + 1x2 + 0x3 + 0x4

− 4 x1 − 3 x 2 ≤ −6 − 4 x1 − 3 x 2 + x3 + 0 x 4 = −6
Sujeito à 1x1 + 2 x 2 ≤ 3 Suj. à 1x1 + 2 x 2 + 0 x3 + x 4 = 3
xi ≥ 0 xi ≥ 0

Tabela inicial simplex

Base x1 x2 x3 x4 bi
x3 -4 -3 1 0 -6
x4 1 2 0 1 3
W -2 -1 0 0 0
(1/2) (1/3)
A variável que sai é x3 porque x3 = -6; e x2 entra na base porque 1/3 < 1/2.

1a iteração
Base x1 x2 x3 x4 bi
x2 4/3 1 -1/3 0 2 → l1’=-1/3l1
x4 -5/3 0 2/3 1 -1 → l2’=l2-2l1’
W -2/3 0 -1/3 0 2 → l3’=l3+l1’
(2/5)
2a iteração
Base x1 x2 x3 x4 Bi
x2 0 1 1/5 4/5 6/5 → l1’=l1- 4/3l’2
x1 1 0 -2/5 -3/5 3/5 → l2’=-3/5l2
W 0 0 -3/5 -2/5 12/5→ l3’=l3+2/3l2’

Solução X = {3/5; 6/5; 0; 0} Wmin = 12/5

Para a solução dual temos Y = (3/5; 2/5; 0; 0} Zmax = 12/5

%$
Exemplo 3.6. Resolver o problema de programação linear.
(a) pelo método gráfico (b) pelo método dual - simplex.

Minimizar W = 3x1 +2x2

3 x1 + x 2 ≥ 3 ...r1
4 x1 + 3 x 2 ≥ 6 ...r2
Sujeito à
x1 + x 2 ≤ 3 ...r3
xi ≥ 0 r4 , r5

a) Resolução pelo método gráfico

R 1 : x1 x 2 R2 : x1 x2 R3: x1 x2 recta W: x1 x2
0 3 0 2 0 3 0 0
1 0 3/2 0 3 0 1 -3/2

x2
4

1 2 3 4 x1

r3
-1
r2
r1

Do gráfico o ponto extremo e mínimo é P = r1∩ r2

3 x1 + 1x 2 = 3
Resolvendo o sistema das rectas teremos a solução
4 x1 + 3 x 2 = 6

X = (3/5; 6/5) com Wmin = 21/5

%
b) Resolvendo pelo método dual – simplex, temos:

Minimizar W = 3x1 +2x2 + 0x3 +0x4 +0x5

− 3 x1 − x 2 + 1x3 + 0 x 4 + 0 x5 = −3
− 4 x1 − 3 x 2 + 0 x3 + x 4 + 0 x5 = −6
Sujeito à
+ 1x1 + 1x 2 + 0 x3 + 0 x 4 + 1x5 = 3
xi ≥ 0
Tabela inicial simplex
Base x1 x2 x3 x4 x5 bi
x3 -3 -1 1 0 0 -3
x4 -4 -3 0 1 0 -6
x5 1 1 0 0 1 3
W -3 -2 0 0 0 0
(3/4) (2/3)
a
1 Iteração
Base x1 x2 x3 x4 x5 bi
x3 -5/3 0 1 -1/3 0 -1 → l1’=l1+l2’
x2 4/3 1 0 -1/3 0 2 → l2’=-1/3l2’
x5 -1/3 0 0 1/3 1
1 → l3’=l3 -l2’
W -1/3 0 0 -2/3 0 4 → l4’=l4+2l2’
(1/5) (2)
a
2 Iteração
Base x1 x2 x3 x4 x5 Bi
x1 1 0 -3/5 1/5 0 3/5 → l1’=-3/5l1
x2 0 1 4/5 -3/5 0 6/5 → l2’=l2 -4/3l1’
x5 0 0 -1/5 2/5 1
6/5→ l3’=l3 –1/3l1’
W 0 0 -1/5 -3/5 0 21/5→ l4’=l4+1/3l1’

Solução X = (3/5; 6/5; 0;0;6/5) com Wmin = 21/5

3.2.2 EXERCÍCIOS PROPOSTOS

Exercício 3.1. Escreva os problemas na forma canónica e transforme – os em duais.

a) Minimizar W = 9y1 + 2y2 b) Maximizar Z = 16x1 + 12x2

x1 + x 2 ≥ 16
4 y1 + y 2 ≥ 13
x1 − x 2 ≤ −9
Sujeito à 3 y1 + y 2 ≤ 12 Sujeito à
3 x1 + x 2 ≤ 21
yi ≥ 0
xi ≥ 0

%!
Exercício 3.2. Considere o seguinte problema de programação linear:

Minimizar W = 5x1 + 2x2

2 x1 + x 2 ≥ 8
x1 + x 2 ≥ 6
Sujeito à 1
x1 + x 2 ≥ 4
2
xi ≥ 0

a) Escreva o problema dual correspondente.

b) Obtenha a solução do primal a partir da resolução do dual pelo método simplex.
(Resp. X = (0; 8; 0; 2; 4) com Wmin = 16 u.m)

Exercício 3.3. Considere o seguinte problema de programação linear.

Maximizar Z = 12x1 + 15x2
4 x1 + 3 x 2 ≤ 12
Sujeito à 2 x1 + 5 x 2 ≤ 10
xi ≥ 0

Usando o método simplex resolva o problema e apresente as soluções do primal e dual.

(Primal: Resp. X = (15/7; 8/7; 0; 0) com Zmax = 300/7)
(Dual : Resp: Y = (15/7; 12/7; 0; 0) com Wmin = 300/7)

Exercício 3.4. Nos seguintes casos transformar em duais e depois resolver os problemas.
a) Min W = 5y1 + 2y2 b) Min W = 2y1 + 1y2 + 3y3
2 y1 + 3 y 2 ≥ 6 1 y1 + 1 y 2 + 1 y 3 ≥ 100
Sujeito à 2 y1 + 1 y 2 ≥ 7 Sujeito à 2 y1 + 1 y 2 + 0 y3 ≥ 50
yi ≥ 0 yi ≥ 0

c) Min W = 7y1 + 5y2 d) Min W = 2y1 + 1y2

2 y1 + 1 y 2 ≥ 4
2 y1 + 1 y 2 = 20
1 y1 − 2 y 2 ≥ −8
Sujeito à Sujeito à 2 y1 + 1 y 2 ≥ 10
− 2 y1 + y 2 ≥ −8
yi ≥ 0
yi ≥ 0

a) Resp. Y = (0; 7; 15; 0) com Wmin = 14

b) Resp. Y = (0; 100; 0; 0; 50) com Wmin = 100
c) Resp. Y = (2; 0; 0; 10; 4) com Wmin = 14
d) Resp. Y = (10; 0; 0; 0; 10) com Wmin = 20

%%
Exercício 3.5. Uma empresa de transporte dispõe de dois tipos de camiões que podem
operar em três percursos diferentes. A capacidade semanal de transporte em cada um dos
tipos de camiões e a procura semanal mínima de serviços de carga, expressos em
toneladas estão indicados no quadro seguinte.

Percursos Tipos de camiões Procura mínima

Tipo A Tipo B
1 10 10 180
2 12 15 200
3 10 10 220

Sabendo que os custos de operação de cada camião são 50 e 80 u.m por semana
respectivamente, quantos veículos de cada tipo deve a empresa utilizar nos percursos
indicados, de modo a minimizar os custos. (use o procedimento dual se necessário).
(Resp. Y = (22; 0; 40; 64; 0) com Wmin = 1100 u.m.)

Exercício 3.6. Resolva o seguinte problema de programação linear, primeiro

graficamente e depois pelo algoritmo dual do método simplex.
Minimizar W = 4y1 + 5y2
y1 + 2 y 2 ≥ 80
Sujeito à 3 y1 + y 2 ≥ 75
yi ≥ 0
(Resp. Y = (14; 33; 0; 0) com Wmin = 221)

Exercício 3.7. Resolva os seguintes problemas pelo método dual simplex, se necessário
apresente a solução pelo método gráfico. Nota: substituir as equações por duas
inequações.

a) Min W = 4x1 + 2x2

x1 + x 2 = 1
suj. à 3 x1 − x 2 ≥ 2
xi ≥ 0

b) Min W = 2x1+3x2
2 x1 + 1x 2 ≥ 3
suj. à 1x1 + 1x 2 = 2
xi ≥ 0
Respostas:
a) X = (3/4; 1/4 ; 1/6; 0; 0) Wmin = 7/2
b) X = (2; 0; 1; 0; 0) Wmin = 4

%&
3.3 ANÁLISE DE SENSIBILIDADE EM PROGRAMAÇÃO LINEAR

A análise de sensibilidade em modelos de programação linear significa simplesmente

procurar uma nova interpretação a partir da solução obtida. Já que tanto os recursos como
os preços no mercado estão sujeitos a mudanças contínuas e subsequentes reavaliações, a
análise Pós – Optimização é uma ferramenta dinâmica e indispensável ao administrador
para avaliar as consequências das mudanças.

A análise de sensibilidade da solução óptima tem como objectivo determinar as

condições para as quais a solução óptima obtida é ainda válida. A solução óptima de um
problema é calculada com base nos dados do modelo, que podem sofrer variações por
várias razões:
• Porque os dados foram estimados e não traduzem a realidade;
• Novas possibilidades apareceram após a formulação do modelo e que devem ser
consideradas na implementação da solução.

Conclusão: A análise de sensibilidade tem por objectivo verificar a validade da solução

obtida quando submetida a variações nos coeficientes do modelo original.

Exemplo 3.7. Vamos utilizar as tabelas simplex inicial e terminal do problema 3.3
Maximizar Z = 5x1 + 6x2
1x1 + 2 x 2 ≤ 14
1x1 + 1x 2 ≤ 9
Sujeito à
7 x1 + 4 x 2 ≤ 56
xi ≥ 0

Tabela inicial simplex

base x1 x2 x3 x4 x5 bi
x3 1 2 1 0 0 14
x4 1 1 0 1 0 9
x5 7 4 0 0 1 56
Z -5 -6 0 0 0 0

Tabela terminal simplex

base x1 x2 x3 x4 x5 bi
x2 0 1 1 -1 0 5
x1 1 0 -1 2 0 4
x5 0 0 3 -10 1 8
Z 0 0 1 4 0 50

Vamos supor que o recurso b1 seja alterado de 14 para 16. Como esta mudança afectará
os valores da solução original.

%'
De acordo com a propriedade 2, os novos valores das variáveis básicas serão:
x2 1 -1 0 16 7
x1 = - 1 2 0 • 9 = 2
x5 3 - 10 1 56 14

Como todos os valores são maiores ou iguais a zero, a solução actual é viável e óptima.
Assim para x1 = 2; x2 = 7 e x5 = 14 temos Z = 5*2 + 6*7 = 52, o que significa que a
variação de b1 de 14 para 16 trouxe um aumento no lucro ∆z = 52 – 50 = +2 u.m.

Seja a seguinte mudança para o recurso b1 de 14 para 20.

x2 1 -1 0 20 11
x1 = - 1 2 0 • 9 = −2
x5 3 - 10 1 56 26

Como x1 é negativo, esta solução não é viável, logo deve ser procurada uma outra
solução óptima retirando x1 da base.

De um modo geral, pode-se procurar a variação permissível para cada variável nos
recursos sem que a solução se torne inviável.

Demonstração do cálculo dos limites de oscilação dos valores dos recursos.

a) Vamos analisar a variação positiva admissível no recurso b1 do exemplo 3.7, partindo
da solução óptima.
x2 1 -1 0 14 + d
x1 = - 1 2 0 • 9 ≥0
x5 3 - 10 1 56
Resolvendo o produto matricial temos:
5+d 5+d ≥ 0 d ≥ −5
4 − d ≥ 0 ou 4−d ≥ 0 ⇔ d ≤ 4
8 + 3d 8 + 3d ≥ 0 d ≥ −8 / 3

A maior variação positiva no recurso 1, sem alterar a base é de 4 unidades (d = 4), ou seja
o valor máximo admissível é 14+4 = 18 unidades.

b) Vamos analisar agora a variação negativa no recurso 1.

x2 1 -1 0 14 − d 5−d ≥ 0 d ≤5
x1 = - 1 2 0 • 9 ≥0 ; 4 + d ≥ 0 ⇔ d ≥ −4
x5 3 - 10 1 56 8 − 3d ≥ 0 d ≤ 8/3

A maior variação negativa no recurso 1, sem alterar a base deve ser de 8/3 ou o valor
mínimo admissível é de 14 – 8/3 = 34/3.

%(
Assim, sem haver alteração na base que forma a solução óptima, a quantidade do recurso
1 pode variar de 34/3 até 18. Com o recurso 2, usando o mesmo raciocínio calcula-se o
intervalo de oscilação. Quanto ao recurso 3, cuja variável de folga tem valor positivo na
solução básica (tabela terminal), a redução máxima admissível é a própria folga (8
unidades) e qualquer aumento não afecta a solução final.

"

Para se obter os intervalos de oscilação dos recursos podem se usar os limites:

∆+ = limite superior – é igual ao menor quociente absoluto entre o novo valor do recurso
na tabela terminal da variável que era básica na tabela inicial (no nosso caso o recurso 1
está associado a x3) e os coeficientes negativos da mesma variável na tabela terminal
(razões negativas).
bi
∆+ = min | raz. neg | = min | |; a ij < 0
a ij
∆- = limite inferior – é igual ao menor quociente absoluto entre os novos recursos
óptimos e os coeficientes positivos da variável associada ao recurso bi (razões positivas).
bi
∆− = min | raz. pos | = min | |; a ij > 0
a ij
Exemplo 3.8. Calcular o intervalo óptimo de oscilação de todos os recursos do exemplo
3.7 anterior.
a) b1 está associado a x3 = 14 na tabela inicial, logo vamos usar a coluna de x3 na tabela
terminal.
4 5 8 8
∆+ = min | raz. neg | = min | | = 4 ↑ . ∆− = min | raz. pos | = min | ; |= ↓ .
-1 1 3 3
O intervalo é: 14 – 8/3 ≤ b1 ≤ 14 + 4 ⇔ 34/3 ≤ b1 ≤ 18

b) b2 está associado a x4 = 9 na tabela inicial, logo vamos usar a coluna de x4 na tabela

terminal.
5 8 4
∆+ = min | raz. neg | = min | ; |= ↑ .
- 1 − 10 5
4
∆− = min | raz. pos | = min | | = 2 ↓ .
2
O intervalo é: 9 – 2 ≤ b2 ≤ 9 + 4/5 ⇔ 7 ≤ b2 ≤ 9.8

c) b3 está associado a x5 = 56 na tabela inicial, logo vamos usar a coluna de x5 na tabela

terminal.
∆+ = min | raz. neg | = min | nao existe | = nao limitado ↑ .
8
∆− = min | raz. pos | = min | | = 8 ↓ .
1
O intervalo é: 56 - 8 ≤ b3 ≤ 56 + ∞ ⇔ 48 ≤ b3 ≤ ∞

%
 Exemplo 3.9. Seja o seguinte problema de programação linear, reportando os lucros
unitários e as horas gastas na produção de um determinado artigo que passa por três
secções:
max imizar z = 16 x1 + 16 x 2 (margem bruta)
4x 1 + 4x 2 ≤ 24 (seccao de corte)
4x 1 + 2x 2 ≤ 18 (seccao de montagem)
sujeito a
2x 1 + 6x 2 ≤ 32 (seccao de acabamento)
xi ≥ 0
onde x1 – representa centenas de peças do tipo A a produzir diariamente;
x2 – representa centenas de peças do tipo B a produzir diariamente.
O quadro óptimo do simplex para este modelo económico matemático é o seguinte

base x1 x2 x3 x4 x5 Recurso
x2 0 1 1/2 -1/3 0 3
x1 1 0 -1/4 1/2 0 3
x5 0 0 -5/2 2 1 8
Z 0 0 4 0 0 96

Admitindo que a disponibilidade do recurso na secção de corte seja alterada de 24 para 30

horas, quais as consequências desta alteração na solução óptima.

Resolução
x2 1/2 - 1/3 0 30 9
x1 = - 1/4 1/2 0 • 18 = 3 / 2
x5 - 5/2 2 1 32 −7

x5 deve sair da base e o novo z é: Z = 16*3/2 + 16*9 = 168

base x1 x2 x3 x4 x5 Recurso
x2 0 1 1/2 -1/3 0 9
x1 1 0 -1/4 1/2 0 3/2
x5 0 0 -5/2 2 1 -7
Z 0 0 4 0 0 168

Iteração 1. (método dual - simplex)

base x1 x2 x3 x4 x5 Recurso
x2 0 1 0 1/15 1/5 38/5
x1 1 0 0 3/10 -1/10 11/5
x3 0 0 1 -4/5 -2/5 14/5
Z 0 0 0 16/5 8/5 784/5

Solução
X = (11/5; 38/5; 14/5; 0; 0) com Zmax = 784/5 e ∆z = 304/5

&"
 # # $

As variações nos coeficientes da função objectivo afectam os valores da variável z e

influenciam os testes para um problema optimizado. A análise de sensibilidade deve ser
feita considerando as variáveis básicas e não básicas.

% #

Estes coeficientes afectam os multiplicadores do simplex que devem ser alterados antes
de conferir a optimidade do problema.

Exemplo 3.10. Vamos supor que no exemplo 3.7, o coeficiente de x2 tenha sido alterado
de 6 para 4. A nova função objectivo será Z = 5x1 + 4x2 + 0x3 + 0x4 + 0x5 e os
coeficientes que nos interessam são os das variáveis (x2 x1 x5) ou o vector (4 5 0).
1 -1 0
Usando a propriedade 1 temos: (4 5 0 )• -1 2 0 = (− 1 6 0)
3 - 10 1

Assim, os novos multiplicadores do simplex para as variáveis fora da base na tabela

terminal são:
x3: ∆3 = -1 – 0 = -1
x4: ∆4 = 6 – 0 = 6

como ∆3 < 0, isto significa que a solução actual não continua óptima e deve –se introduzir
x3 na base. Para isso o novo valor da função objectivo é calculado tomando em
consideração a nova função objectivo. Z = 5*4 + 4*5 = 40.

Tabela inicial simplex

Base x1 x2 x3 x4 x5 bi
x2 0 1 1 -1 0 5
x1 1 0 -1 2 0 4
x5 0 0 3 -10 1 8
Z 0 0 -1 6 0 40

1a iteração
Base x1 x2 x3 x4 x5 bi
x2 0 1 0 7/3 -1/3 7/3
x1 1 0 0 -4/3 1/3 20/3
x3 0 0 1 -10/3 1/3 8/3
Z 0 0 0 8/3 1/3 128/3

Como todos ∆i são maiores ou iguais a zero a nova solução é: X = (20/3; 7/3; 8/3; 0; 0)
com Zmax = 128/3. Sendo assim, a variação de c2 de 6 para 4 diminuiu o rendimento em
∆z = z2 – z1 = 128/3 – 50 = - 22/3 u.m.

&#
Observação: Caso as variáveis fora da base não pertençam à solução inicial, que
geralmente é formada pelas variáveis de folga, deve-se aplicar a propriedade 4 para
calcular os multiplicadores do simplex.

% #

Como estes coeficientes não afectam os multiplicadores do simplex, os multiplicadores

disponíveis podem ser utilizados para verificar se o problema está optimizado ou não de
forma imediata.

O intervalo óptimo de oscilação dos coeficientes da função objectivo pode ser obtido
calculando os limites:

∆+ = limite superior – é igual ao menor quociente absoluto entre os multiplicadores do

simplex da tabela terminal e os coeficientes negativos das variáveis não básicas da linha
correspondente à variável básica associada ao coeficiente considerado (para o nosso
exemplo 3.7, c1 está associado a x1 = 4 na tabela terminal, logo temos que calcular razões
negativas na linha 2).
ci
∆+ = min | raz. neg | = min | | ; a ij < 0
a ij
∆- = limite inferior – é igual ao menor quociente absoluto entre os multiplicadores do
simplex da tabela terminal e os coeficientes positivos para a linha considerada (razões
positivas).
ci
∆ − = min | raz. neg | = min | | ; a ij > 0
a ij
Exemplo 3.11. Para o exemplo 3.7, encontrar os intervalos óptimos de oscilação dos
coeficientes das variáveis x1, x2, x5.
Resolução
A função objectivo é z = 5x1 + 6x2 + 0x3 + 0x4 + 0x5
As variáveis básicas na tabela terminal são x1, x2 e x5, portanto os coeficientes a variar
são c1 = 5; c2 = 6 e c5 = 0.

• O c1 = 5 ou o coeficiente de x1 corresponde a linha 2 na tabela terminal.

1 4
∆+ = min | raz. neg | = min | | = 1 ↑ . ∆− = min | raz. pos | = min | | = 2 ↓ .
-1 2
O intervalo é: 5 – 2 ≤ c1 ≤ 5 + 1 ⇔ 3 ≤ c1 ≤ 6

• c2 = 6 ou coeficiente de x2 corresponde a linha 1 na tabela terminal.

4 1
∆+ = min | raz. neg | = min | | = 4 ↑ . ∆− = min | raz. pos | = min | | = 1 ↓ .
-1 1

O intervalo é: 6 – 1 ≤ c2 ≤ 6 + 4 ⇔ 5 ≤ c2 ≤ 10

&$
• c5 = 0 ou coeficiente de x5 corresponde a linha 3 na tabela terminal.
4 2
∆+ = min | raz. neg | = min | |= ↑.
- 10 5
1 1
∆− = min | raz. pos | = min | | = ↓ .
3 3
O intervalo é: 0 –1/3 ≤ c5 ≤ 0 + 2/5 ⇔ -1/3 ≤ c5 ≤ 2/5

3.3.3 VARIAÇÕES NOS COEFICIENTES DAS ACTIVIDADES

% #

As alterações nos coeficientes dessas variáveis afectam os elementos da matriz definida

na propriedade 1, e como esta matriz é fundamental para toda a análise de sensibilidade,
essas variações podem fazer com que a actual solução deixe de ser óptima ou mesmo
viável. A forma mais simples dessa análise é admitir que temos um novo problema,
portanto, deve-se procurar uma nova solução.

% # #

As alterações nos coeficientes das variáveis fora da base poderão modificar a solução
óptima, pois a variável alterada poderá vir a se tornar básica. Assim, uma nova
verificação de que o problema está optimizado é necessário e deve ser realizada.

Exemplo 3.12. Dado o seguinte problema de programação linear.

Maximizar Z = 4x1 + 6x2 + x3
6 x1 + 4 x 2 + 1x3 ≤ 24
Sujeito à 4 x1 + 8 x 2 + 2 x3 ≤ 32
xi ≥ 0

a) Resolva o problema usando o método simplex.

1 1
b) Suponha que os coeficientes de x3 sejam modificados de para qual será o
2 1
efeito desta mudança na solução óptima do problema.

Resolução
a) Tabela inicial simplex
base x1 x2 x3 x4 x5 bi
x4 6 4 1 1 0 24 → (6)
x5 4 8 2 0 1 32 → (4)
Z -4 -6 -1 0 0 0

&
1a iteração
Base x1 x2 x3 x4 x5 bi
x4 4 0 0 1 -1/2 8 →l1’=l1-4l2’
x2 1/2 1 1/4 0 1/8 4 →l2’=1/8l2
Z -1 0 1/2 0 3/4 24→l3’=l3+6l2’

2a iteração : tabela terminal

Base x1 x2 x3 x4 x5 bi
X1 1 0 0 1/4 -1/8 2 →l1’=1/4l1
X2 0 1 1/4 -1/8 3/16 3 →l2’=l2-1/2l1’
Z 0 0 1/2 1/4 5/8 26→l3’=l3+l1’
Solução: X = (2; 3; 0; 0; 0) com Zmax = 26

b) Para testar se o problema está optimizado depois da mudança dos coeficientes de x3

devemos retirar da tabela terminal os multiplicadores do simplex correspondentes as
variáveis básicas iniciais: ∆4 = 1/4 ; ∆5 = 5/8

Do problema dual e escrevendo as variáveis duais em termos das variáveis de folga

temos:
Min W = 24x4 + 32x5
6 x 4 + 4 x5 ≥ 4
4 x 4 + 8 x5 ≥ 6
Suj à
1x 4 + 2 x5 ≥ 1
xi ≥ 0

A restrição 3 no problema dual, depois da mudança dos coeficientes de x3 será:

1x4 + 1x5 ≥ 1, usando a propriedade 4 o novo multiplicador simplex relativo a x3 no
problema primal é: ∆3 = 1*∆4 +1*∆5 – 1 = 1*1/4 + 1*5/8 – 1 = -1/8.

Como ∆3 é negativo, conclui-se que a solução anterior não continua óptima. Da

propriedade 3, podemos encontrar os novos coeficientes de x3 a partir da tabela terminal.
1 1 1
-
4 8 1 8
• =
1 3 1 1
−
8 16 16

Substituindo na tabela terminal os novos coeficientes de x3 teremos a nova tabela inicial .

Tabela inicial simplex
Base x1 x2 x3 x4 x5 bi
X1 1 0 1/8 1/4 -1/8 2 → (16)
x2 0 1 1/16 -1/8 3/16 3 → (48)
Z 0 0 -1/8 1/4 5/8 26

&!
1a iteração: tabela terminal
base x1 x2 x3 x4 x5 bi
x3 8 0 1 2 -1 16→l1’=8l1
x2 -1/2 1 0 -1/4 1/4 2→l2’=l2-1/16l1’
Z 1 0 0 1/2 1/2 28→l3’=l3+1/8l1’

Como todos os multiplicadores simplex são positivos ou iguais a zero já temos a nova
solução óptima. X = (0; 2; 16; 0; 0) com Zmax = 28. Portanto esta variação dos
coeficientes de x3 aumentou o rendimento em 28-26 = +2 u.m.

&

Este caso pode ser considerado como variações simultâneas nos coeficientes da função
objectivo e nos coeficientes do vector actividade correspondente à nova variável, que não
é básica. Pois no problema inicial a nova variável é considerada como se tivesse
coeficientes nulos.

Exemplo 3.13. Analisar o exemplo 3.12, introduzindo agora uma nova variável x4
conforme o modelo apresentado.
Maximizar Z = 4x1 + 6x2 + 1x3 + 3x4
6 x1 + 4 x 2 + 1x3 + 2 x 4 ≤ 24
Sujeito à 4 x1 + 8 x 2 + 2 x3 + 2 x 4 ≤ 32
xi ≥ 0
Resolução
O teste de optimidade da solução, fornece o multiplicador do simplex para x4, tomando os
coeficientes da restrição 4 no problema dual e da tabela final anterior.
Restrição 4: 2x5 + 2x6 ≥ 3
Multiplicadores simplex do problema primal: ∆5 = 1/4; ∆6 = 5/8
Multiplicador simplex para x4 no primal: ∆4 = 2*1/4 + 2*5/8 – 3 = -5/4

O multiplicador de x4 indica que este deve entrar na base e seus coeficientes no último
quadro do problema serão:
1 1 1
-
4 8 2 4
• =
1 3 2 1
−
8 16 8

A nova tabela simplex inicial com as variáveis de folga renomeadas é:

Base x1 x2 x3 x4 x5 x6 bi
x1 1 0 0 1/4 1/4 -1/8 2→ (8)
x2 0 1 1/4 1/8 -1/8 3/16 3→ (24)
Z 0 0 1/2 -5/4 1/4 5/8 26

&%
1a iteração
base x1 x2 x3 x4 x5 x6 bi
x4 4 0 0 1 1 -1/2 8→ l1’=4l1
x2 -1/2 1 1/4 0 -1/4 1/4 2→ l2’=l2-1/8l1’
Z 5 0 1/2 0 3/2 0 36→L3’=l3+5/4l1’

A nova solução é X = (0; 2; 0; 8; 0; 0) com Zmax = 36

Resp. A introdução da variável x4 com o coeficiente 3 na função objectivo e 2 nas
restrições aumenta o rendimento em 36 – 26 = 10u.m.

'

A adição de uma nova restrição pode alterar a viabilidade da solução, se ela não for
redundante. O procedimento para a análise é o seguinte:

1. Testar se a nova restrição é satisfeita para a actual solução óptima, em caso

afirmativo, a nova restrição diz-se redundante.
2. Se não for satisfeita, ela deve ser introduzida no sistema e novos cálculos devem ser
feitos para-se obter a nova solução óptima.

Exemplo 3.14. analisar o exemplo 3.12, depois de introduzir a restrição 3:

Restrição 3: 2x1 +8x2 + x3 ≤ 24

Resolução
O novo modelo com a terceira restrição é:

Maximizar Z = 4x1 + 6x2 + 1x3

6 x1 + 4 x 2 + 1x3 ≤ 24
4 x1 + 8 x 2 + 2 x3 ≤ 32
Sujeito à
2 x1 + 8 x 2 + 1x3 ≤ 24
xi ≥ 0

1. Teste: Para o problema anterior a solução óptima é: x1 = 2; x2 = 3; x3 = 0 e Z = 26

restrição 1: 6*2 + 4*3 + 1*0 = 24 ( = 24 verdadeiro)
restrição 2: 4*2 + 8*3 + 2*0 = 32 ( = 32 verdadeiro)
restrição 3: 2*2 + 8*3 + 1*0 = 28 ( > 24 não satisfeita), a nova restrição não é
redundante.

2. Resolução do novo problema: a solução anterior já não é viável e novas iterações

devem ser feitas. Assim, vamos colocar no quadro terminal anterior os coeficientes da
nova restrição e a correspondente variável de folga.

&&
Tabela inicial simplex
base x1 x2 x3 x4 x5 x6 bi
x1* 1 0 0 1/4 -1/8 0 2 →
x2* 0 1 1/4 -1/8 3/16 0 3 →
x6 2 8 1 0 0 1
24→
Z 0 0 1/2 1/4 5/8 0 26

Como x1 e x2 estão na base seus coeficientes na nova restrição devem ser nulos e é por
isso que tomamos as suas posições como pivô.

1a iteração
base x1 x2 x3 x4 x5 x6 bi
x1 1 0 0 1/4 -1/8 0 2 → l1’=l1
x2* 0 1 1/4 -1/8 3/16 0 3 → l2’=l2
x6 0 8 1 -1/2 1/4 1
20→ l3’=l3-2l1’
Z 0 0 1/2 1/4 5/8 0 26→ l4’=l4
a
2 iteração
base x1 x2 x3 x4 x5 x6 bi
x1 1 0 0 1/4 -1/8 0 2 → l1’=l1
x2 0 1 1/4 -1/8 3/16 0 3 → l2’=l2
x6 0 0 -1 1/2 -5/4 1
-4→ l3’=l3-8l2’
Z 0 0 1/2 1/4 5/8 0 26→ l4’=l4
a
3 iteração
base x1 x2 x3 x4 x5 x6 bi
x1 1 0 0 1/4 -1/8 0 2 → l1’=l1
x2 0 1 0 0 1/8 1/4 2 → l2’=l2-1/4l3’
x3 0 0 1 -1/2 5/4 -1
4 → l3’=-l3
Z 0 0 0 1/2 0 1/2 24→ l4’=l4-1/2l3’

Nova solução X = (2; 3; 4; 0; 0; 0) com Zmax = 24

Resp. A introdução da restrição 3, com os coeficientes 2, 8 e 1 cujo valor do recurso é 24,
reduz o rendimento em 24 – 26 = -2 u.m.

&'
3.3.6 EXERCÍCIOS PROPOSTOS

Exercício 3.8. Dado o problema

Maximizar Z = 2x1 + 1x2
0 x1 + 3x 2 ≤ 6
4 x1 + 1x 2 ≤ 8
Sujeito à
1x1 + 0 x 2 ≤ 3
xi ≥ 0
a) Resolva o problema.(Resp: X = (3/2; 2; 0; 0; 3/2) Z1 = 5)
b) Se o recurso b1 for mudado de 6 para 4, qual será o efeito desta mudança no lucro Z.
(Resp: X = (5/3; 4/3; 0; 0; 4/3) Z2 = 14/3 e ∆z = -1/3
c) Encontre os intervalos óptimos de oscilação de todos os recursos do problema.
(Resp: 0 ≤ b1 ≤ 24; 2 ≤ b2 ≤ 14; 3/2 ≤ b3 ≤ não limitado.

Exercício 3.9. Para o seguinte problema de programação linear:

Maximizar Z = 1x1 + 3/2x2
2 x1 + 2 x 2 ≤ 160
1x1 + 2 x 2 ≤ 120
Sujeito à
4 x1 + 2 x 2 ≤ 280
xi ≥ 0
a) Resolva o problema.(Resp. X = (40; 40; 0; 0; 40) e Z1 = 100)
b) Se o recurso b2, variar de 120 para 98 qual será o efeito sobre a solução óptima
inicial. (Resp: X = (182/3; 56/3; 4/3; 0; 0), Z2 = 266/3 e ∆z = -34/3)
c) Se o coeficiente de x2 na função objectivo mudar de 3/2 par 2, qual será o efeito sobre
z. (Resp: X = (40; 40;0; 0; 40), Z3 = 120 e ∆z = +20
d) Encontre os intervalos óptimos tanto dos recursos como dos coeficientes da função
objectivo no problema inicial. (Resp: 3/4 ≤ c1 ≤ 3/2; 1 ≤ c2 ≤ 2
120 ≤ b1 ≤ 520/3; 100 ≤ b2 ≤ 160; 240 ≤ b3 ≤ não limitado)

Exercício 3.10. Dado o problema

Maximizar Z = 2x1 + 3x2 + 7x3 + 9x4
1x1 + 1x 2 + 1x3 + 1x 4 ≤ 9
Sujeito à 1x1 + 2 x 2 + 4 x3 + 8 x 4 ≤ 24
xi ≥ 0
a) Resolva o problema (Resp: X = (4; 0; 5; 0) Z1 = 43)
b) Verificar a optimidade da solução, para a seguinte variação nos coeficientes de x2 de
1 2
para (Resp: X = (4; 0; 5; 0) Z2 = 43; ∆z = 0)
2 2

&(
 1 1
c) Verificar o mesmo de (b) para x4 com a variação para .
8 2
(Resp: X = (0; 0; 0; 9) Z3 = 81; ∆z = +38)

Exercício 3.11. Para o seguinte problema de programação linear:

Minimizar W = 10x1 + 20x2
6 x1 + 2 x 2 ≥ 36
Sujeito à 2 x1 + 4 x 2 ≥ 32
xi ≥ 0
a) Resolva o problema.(Resp. X = (4; 6; 0; 0) e W1 = 160)
b) No modelo anterior introduza a variável x3 com coeficiente 3 na função objectivo, 3
na restrição 1 e 1 na restrição 2. Analise o efeito da introdução da nova variável no
modelo. (Resp: X = (4; 6; 0; 0; 0), W2 = 160 então ∆w = 0)
c) Analisar de novo o problema, mas agora introduzindo a restrição 4x1 + 2x2 ≥ 30.
(Resp: X = (14/3; 17/3; 10/3; 0; 0), W2 = 160 então ∆w = 0)

Exercício 3.12. O quadro óptimo do problema de programação linear:

max imizar Z = 3x 1 + 2x 2
4x 1 + 3x 2 ≤ 120
sujeito a 1x 1 + 3x 2 ≤ 60
x1, x2 ≥ 0
é o seguinte, com x3 e x4 designando variáveis de folga.

)# )$ ) )!
*# # +! #+! " "
*! " +! ,#+! # "
- " #+! +! " "

a) Suponha que os coeficiente técnicos de variável x2, mudarem de (3, 3) para (2, 1),
obtenha a nova solução óptima através da análise de sensibilidade.
(Resp:. X = (0,60,0,0), Zmax = 120, z = 30)
b) Se os termos independentes ou recursos das restrições forem alterados de (120, 60)
para (140, 40), determine a nova solução óptima ( as propriedades para encontrar a
nova solução). (Resp: X = (35, 0,0, 5), Zmax = 105, z = 15)

Referências:
ANDRADE, EL(1998) – Introdução à Pesquisa Operacional – métodos e modelos para a análise de
decisão, 2a edição, editora LTC, RJ, Brasil: cap4;
BARNETT, RA; Michael, RZ (1990) – Finite Mathematics – for business, economics, life science and
social sciences, 5th edition, USA: cap6;
TAHA, HA(1997) – Operations Research – an introduction, 6th edition, Prentice-Hall International, Inc.
USA: cap4.

&