PROGRAMAÇÃO LINEAR

1. Forma Padrão do Modelo de Programação Linear 2. Relações de Equivalência 3. Suposições da Programação Linear 4. Exemplos de Modelos de PPL 5. Suposições da Programação Linear 6. Solução Gráfica e Interpretação 7. Propriedades dos PPL’s 8. Método Simplex 9. Solução Algébrica 10. Método Simplex na Forma Tableau 11. Método das Duas Fases 12. Método Simplex na Forma Tableau 13. Dualidade em Programação Linear 14. Algoritmo SIMPLEX Primal-Dual 15. Análise de Pós-otimalidade

Forma padrão do modelo de Programação

Linear

Max nn xcxcxcz +++= ...2211

s.a: 11212111 ... bxaxaxa nn =+++

22222121 ... bxaxaxa nn =+++

� mnmnmm bxaxaxa =+++ ...2211

njx j ,...,10 =∀≥

Suposições da Programação Linear

1. Proporcionalidade 2. Aditividade 3. Divisibilidade 4. Certeza 5. Perspectiva das suposições

Relações de Equivalência

Qualquer que seja a estrutura do PPL, sempre é possível transformá-lo no formato padrão apresentado acima. Para tanto, utilizam-se as seguintes relações de equivalência:

a) Relação entre equações e inequações

∞≤≤

=+≡≤

∑∑ ==

i

n

j

iijijn

j

ijij

S

bSxabxa

01

1

∞≤≤

=−≡≥

∑∑ ==

i

n

j

iijijn

j

ijij

S

bSxabxa

01

1

b) Relação entre maximização e minimização

∑∑==

−=−≡=n

j

jj

n

j

jj xczMinxczMax11

)()(

c) Tratamento de limites de variáveis

≥′

+′=⇒′=−≡≠≥

0

:ãoSubstituiç0

j

jjj

j x

xxxxx

���

≥′

′−=⇒′=−≡≤

0

:ãoSubstituiç

j

jjjj

j x

xxxxx

���

≥′′≥′

′′−′=≡∞≤≤∞−

00 jj

jjj

j xex

xxxx

Exemplo - Empresa WYNDOR GLASS CO.

Capacidade

Janelas Portas Disponível

1 1 0 4

2 0 2 12

3 3 2 18

Lucro Unit. $3 $5

ProdutosPlanta

Max Z = 3 X1 + 5 X2

S.a: X1 ≤≤≤≤ 4

2 X2 ≤≤≤≤ 12

3 X1 + 2 X2 ≤≤≤≤ 18

X1, X2 ≥≥≥≥ 0

0 1 2 3 4 5 6 7 8 9

0

1

2

3

4

5

6

7

8

9

X1

X2

Propriedades dos PPL’s

(a) Se existe exatamente uma solução ótima, então deve ser uma solução factível em um vértice;

(b) Se existem soluções ótimas múltiplas, então ao

menos duas delas devem ser soluções factíveis em vértices adjacentes;

(c) Existe um número finito de soluções factíveis em

vértices; (d) Se uma solução factível em um vértice é igual ou

melhor (segundo o valor de Z) que todas as soluções factíveis nos vértices adjacentes a ela, então é igual ou melhor que todas as demais soluções factíveis existentes nos vértices, isto é, é uma solução ótima.

Método Simplex

1. Passo inicial: iniciar com uma solução factível em um vértice;

2. Teste de otimalidade: se não existe solução factível

em um vértice adjacente, melhor que a solução atual, então PARE. A solução atual é ótima. Em caso contrário, vá ao passo 3;

3. Passo iterativo: movimente em direção de uma

solução factível melhor, em um vértice adjacente; volte ao passo 2.

Solução Algébrica

Modelo Original (Wyndor Glass Co.) Max Z = 3 X1 + 5 X2

s.a: X1 ≤≤≤≤ 4

2 X2 ≤≤≤≤ 12

3 X1 + 2 X2 ≤≤≤≤ 18

X1,X2 ≥≥≥≥ 0 Forma padrão equivalente Max Z s.a: Z – 3 X1 – 5 X2 = 0 X1 + S1 = 4 2 X2 + S2 = 12 3 X1 + 2 X2 + S3 = 18

X1,X2,S1,S2,S3 ≥≥≥≥ 0

Solução aumentada Solução básica Solução básica viável = Vértice Soluções adjacentes

Z – 3 X1 – 5 X2 = 0 X1 + S1 = 4 2 X2 + S2 = 12 3 X1 + 2 X2 + S3 = 18

Solução: Z,X1,X2,S1,S2,S3)=(0,0,0,4,12,18) O que fazer para melhorar a solução ? Que variável sai da base ? Como representar o sistema de equações lineares ? Nova representação do sistema de equações lineares Z – 3 X1 + + 5/2 S2 = 30 X1 + S1 = 4 X2 + 1/2 S2 = 6 3 X1 - S2 + S3 = 6

Solução: (Z,X1,X2,S1,S2,S3)=(30,0,6,4,0,6) O que fazer para melhorar a solução ? Que variável sai da base ? Como representar o sistema de equações lineares ? Nova representação do sistema de equações lineares Z + 3/2 S2 + S3 = 36 S1 + 1/3 S2 – 1/3 S3 = 2 X2 + 1/2 S2 = 6 X1 - 1/3 S2 + 1/3 S3 = 2

Solução: (Z,X1,X2,S1,S2,S3)=(36,2,6,2,0,0) O que fazer para melhorar a solução ?

Método Simplex na Forma Tableau

Variável Lado

Básica Z X1 X2 S1 S2 S3 Direito

Z 1 -3 -5 0 0 0 0

S1 0 1 0 1 0 0 4

S2 0 0 2 0 1 0 12

S3 0 3 2 0 0 1 18

Coeficientes

Variável Lado

Básica Z X1 X2 S1 S2 S3 Direito

Z 1 -3 0 0 5/2 0 30

S1 0 1 0 1 0 0 4

X2 0 0 1 0 1/2 0 6

S3 0 3 0 0 -1 1 6

Coeficientes

Variável Lado

Básica Z X1 X2 S1 S2 S3 Direito

Z 1 0 0 0 3/2 1 36

S1 0 0 0 1 1/3 -1/3 2

X2 0 0 1 0 1/2 0 6

X1 0 1 0 0 -1/3 1/3 2

Coeficientes

Como escolher a variável que entra na base no caso de empate ? Como escolher a variável que sai da base no caso de empate ? E se não existe variável que possa sair da base ? Como descobrir se existem soluções ótimas múltiplas ?

Método das Duas Fases

Seja o PPL genérico em sua forma padrão, denominado de P1, onde ibi ∀≥ ,0 , para o qual não é possível obter

uma solução básica inicial trivial:

(P1) Max ∑=

=n

j

jj xcz1

s.a: mibxan

j

ijij ,...,11

=∀=∑=

njx j ,...,10 =∀≥

Então, sempre é possível construir o PPL abaixo, denominado de P2, incluindo variáveis artificiais:

(P2) Max ∑=

=n

j

jj xcz1

s.a: mibdxan

j

iijij ,...,11

=∀=+∑=

njx j ,...,10 =∀≥

midi ,...,10 =∀≥

O problema P2 sempre tem uma solução básica viável trivial:

mibd ii ,...,1, =∀=

njx j ,...,1,0 =∀=

Equivalência entre os problemas P1 e P2 midi ,...,1,0 P2 P1 =∀=⇔≡

Considere o PPL abaixo, denominado de P3:

(P3) Min ∑=

=m

iidw

1

s.a: mibdxan

j

iijij ,...,11

=∀=+∑=

njx j ,...,10 =∀≥

midi ,...,10 =∀≥

Então: i) toda solução de P3 é também solução de P2; ii) se a solução ótima de P3 tiver 0=w , então também

será uma solução básica viável para o P1. Algoritmo 1. Se P1 tem solução básica viável trivial, vá para 4; 2. Formule P3, e resolva-o; 3. Se na solução ótima de P3 as variáveis artificiais

forem nulas, então uma solução básica viável para P1 foi encontrada; vá para 4. Em caso contrário, PARE; P1 não tem solução viável;

4. Resolva P1, considerando a solução básica viável

conhecida.

Exemplo

Min Z = 3 X1 + 2 X2 + 4 X3 s.a: 2 X1 + X2 + 3 X3 = 60

3 X1 + 3 X2 + 5 X3 ≥≥≥≥ 120

X1,X2,X3 ≥≥≥≥ 0 Forma Equivalente Z’ = (-Z) = -3 X1 - 2 X2 - 4 X3 Max Z’ Z’ + 3 X1 + 2 X2 + 4 X3 = 0 2 X1 + X2 + 3 X3 = 60 3 X1 + 3 X2 + 5 X3 – S2 = 120

X1,X2,X3,S2 ≥≥≥≥ 0 Incluindo Variáveis Artificiais Max Z’ Z’+ 3 X1 + 2 X2 + 4 X3 = 0 2 X1 + X2 + 3 X3 + d1 = 60 3 X1 + 3 X2 + 5 X3 – S2 + d2 = 120

X1,X2,X3,S2,d1,d2 ≥≥≥≥ 0

Problema da Primeira Fase Min W = d1 + d2 ou Max W’= (-W) = - d1 – d2 W’ + d1 + d2 = 0 Z’+ 3 X1 + 2 X2 + 4 X3 = 0 2 X1 + X2 + 3 X3 + d1 = 60 3 X1 + 3 X2 + 5 X3 – S2 + d2 = 120

X1,X2,X3,S2,d1,d2 ≥≥≥≥ 0 Problema Fase 1 – Forma Tableau

Iteração 0

V.B. W' Z' X1 X2 X3 S2 d1 d2 Valor

W' 1 0 -5 -4 -8 1 0 0 -180

Z' 0 1 3 2 4 0 0 0 0

a1 0 0 2 1 3 0 1 0 60

a2 0 0 3 3 5 -1 0 1 120

Iteração 1

V.B. W' Z' X1 X2 X3 S2 d1 d2 Valor

W' 1 0 1/3 -4/3 0 1 8/3 0 -20

Z' 0 1 1/3 2/3 0 0 -4/3 0 -80

X3 0 0 2/3 1/3 1 0 1/3 0 20

a2 0 0 -1/3 4/3 0 -1 -5/3 1 20

Iteração 2

V.B. W' Z' X1 X2 X3 S2 d1 d2 Valor

W' 1 0 0 0 0 0 1 1 0

Z' 0 1 1/2 0 0 1/2 -1/2 -1/2 -90

X3 0 0 2/3 0 1 3/4 1/3 -1/4 15

X2 0 0 -1/4 1 0 -3/4 -5/4 3/4 15

Problema Fase 2 – Forma Tableau

Iteração 0

V.B. Z' X1 X2 X3 S2 Valor

Z' 1 1/2 0 0 1/2 -90

X3 0 2/3 0 1 3/4 15

X2 0 -1/4 1 0 -3/4 15 Solução do Problema X1 = 0 X2 = 15 X3 = 15 S2 = 0

Z’ = -90 ⇒⇒⇒⇒ Z = 90

Método Simplex na Forma Matricial

Max xczT

= (1.a)

s.a: bAx = (1.b)

0≥x (1.c)

onde n

Rxc ∈0,, , m

Rb ∈ e A é uma matriz nm× de

posto m. Obtenção de uma Solução

No sistema de equações lineares (1.b), para que uma solução seja determinada, é necessário, considerando que mn ≥ , arbitrar o valor de mn − variáveis. Particionando o vetor de variáveis de modo a caraterizar as variáveis que serão arbitradas e aquelas que serão calculadas, e seguindo esta partição para os demais elementos do PPL, tem-se:

=

R

B

x

xx

=

R

B

c

cc [ ]RBA = (2)

onde m

BB Rxc ∈, , mn

RR Rxc−∈, , B é uma matriz mm ×

não-singular, e R é uma matriz )( mnm −× .

Com isto o PPL poderá ser re-escrito na forma:

Max RTRB

TB xcxcz += (3.a)

s.a: bxRxB RB =+ (3.b)

0e0 ≥≥ RB xx (3.c)

Arbitrando o valor das mn − componentes do vetor de variáveis Rx , os valores das componentes do vetor Bx

poderão ser obtido a partir da equação (3.b):

RB xRbxB −=

( )RB xRbBxBB −= −− 11

RB xRBbBx11 −− −= (4)

No caso particular em que se arbitra 0=Rx , tem-se

uma solução básica1, e o valor das componentes do vetor Bx poderá ser obtido através de:

bBxB1

ˆ−= (5)

Considere que a solução assim obtida satisfaz as condições de não-negatividade das variáveis básicas, apresentadas em (3.c), isto é, que 0ˆ ≥Bx . Neste caso,

diz-se que esta solução é uma solução básica viável.

1 Os vetores

Bx e Rx são denominados de vetor de variáveis básicas e

vetor de variáveis não-básicas, respectivamente.

Cálculo do valor da função objetivo O valor da função objetivo, que poderá ser calculado através da equação (3.a), no caso particular de uma solução básica resume-se a:

BTB xcz ˆˆ = (6)

Até agora, mostrou-se como o valor das variáveis Bx

pode ser obtido a partir do arbítrio das variáveis Rx .

Variando-se o valor destas, obtém-se diferentes soluções para Bx . Substituindo (4) na expressão (3.a),

obtém-se:

( )

( ) RTB

TRB

TB

RTRR

TB

TB

RTRR

TB

xRBccxcz

xcxRBcbBcz

xcxRBbBcz

1

11

11

ˆ−

−−

−−

−+=

+−=

+−=

( ) RTB

TR xRBcczz

1ˆ

−−+= (7)

Com esta expressão, pode-se calcular o valor da função objetivo de novas soluções, como função dos valores

arbitrados para Rx . Portanto, diferente valores de Rx

produzem diferentes valores para a função objetivo.

Condição de otimalidade Considerando que deseja-se obter uma solução com valor da função objetivo maior do que o valor atual z , isto é, que zz ˆ> , a seguinte condição deve ser satisfeita:

( ) 01 <−−R

TR

TB xcRBc (8)

Dado que na solução básica corrente 0=Rx , e que a

condição de não-negatividade deve ser mantida, para satisfazer a condição (8) é necessário aumentar as componentes de Rx associadas a componentes

negativas do vetor

TR

TB cRBc −=∆ −1

(9)

Obviamente, se não existirem componentes negativas em ∆ , isto é, se 0<∆∃/ j , não será possível aumentar o

valor de z. Neste caso, diz-se que a solução básica viável corrente é a solução ótima do PPL.

Troca de base Mesmo que exista mais do que uma componente

0<∆ j , o Método Simplex considera que apenas uma

componente de Rx é aumentada a cada vez. Neste

caso, diversas estratégias de escolha poderão ser adotadas. Teoricamente, a única condição para que se obtenha uma solução melhor, é que se escolha uma componente 0<∆ j . Na prática, a escolha da

componente negativa de menor valor, isto é:

min { | 0}

k j jj

∆ = ∆ ∆ < (10)

é uma boa estratégia para aumentar o valor da função objetivo, pois é a que produz o maior incremento em z com o aumento unitário da respectiva componente em

Rx .

Determinada a variável não-básica que será aumentada, associada a uma componente 0<∆k , e denotada por

kRx , deve-se determinar o valor do incremento.

Em princípio, quanto maior o valor do incremento, maior será o valor de z. A fim de manter a viabilidade da solução, é necessário que a nova solução, que poderá ser calculada pela expressão (4), satisfaça a seguinte condição:

011 ≥−= −−RB xRBbBx (11)

Considerando que apenas um componente do vetor de variáveis não-básicas é incrementado por vez, esta expressão resume-se a:

0ˆ1 ≥−= −

kk RRBB xaBxx (12)

ou ainda, considerando as várias linhas desta condição vetorial:

mixaxxkii RikBB ,...,10ˆ =∀≥−= (13)

onde ika é a i-ésima componente de kRaB

1− .

Considerando que a variável não-básica será aumentada (positiva), é necessário verificar a condição (13) somente para 0>ika . Com isto o incremento da

variável não-básica será limitado em:

{ }

>== 0|ˆ

minmin ikik

B

ii

ir a

a

xiθθ (14)

Não existindo 0>ika , não haverá limites para o

incremento da variável não-básica. Neste caso, diz-se que não existe solução ótima finita, ou que a solução é ilimitada, pois o valor da função objetivo ∞→z .

Por outro lado, encontrado um limite rθ para o

incremento da variável não-básica, uma nova solução poderá ser obtida fazendo-se:

rRkx θ= (15)

Com isto, 0=

rBx e o valor da função objetivo aumenta

para rkzz θ∆+= ˆ .

Esta nova solução poderá ser representada por uma nova partição no vetor de variáveis x, na qual a variável básica que foi anulada passa a fazer parte do vetor de variáveis não-básicas Rx , e a variável não-básica que

foi incrementada passa a fazer parte do vetor de variáveis básicas Bx . A esta operação, dá-se o nome de

troca de base. Efetuada a re-definição dos vetores Rx e Bx , todas as

etapas do processo são repetidas até que se obtenha uma solução ótima ou uma solução ilimitada.

Dualidade em Programação Linear

Seja o PPL apresentado na forma abaixo:

(PRIMAL) Max xcT

(I.a)

s.a: bAx ≤ (I.b)

0≥x (I.c)

Então sempre é possível construir o PPL que se segue:

(DUAL) Min πTb (II.a)

s.a: cAT ≥π (II.b)

0≥π (II.c)

O PPL Primal relaciona-se com o PPL Dual através das seguintes proposições: Proposição 1

i) Seja *

x a solução ótima do PPL Primal. Seja *π a

solução ótima do PPL Dual. Então ** πTT

bxc = . ii) Se o PPL Primal tem solução ilimitada, então o PPL

Dual não tem solução, e vice-versa. Proposição 2

Seja *

x a solução básica ótima do PPL Primal, e B a

base correspondente. Então TR

TB cRBc −= −1*π é a

solução ótima do PPL Dual.

Algoritmo SIMPLEX Primal-Dual

(G. B. DANTZIG, 1956) P0 Monte o PPL em sua forma padrão. Escolha um

conjunto de m variáveis básicas quaisquer, e particione o problema como segue:

Max RTRB

TB xcxc +

s.a: bRxBx RB =+

P1 Calcule 1−

B .

Calcule bBxB

1ˆ

−= e T

R

T

B cRBcz −=∆ −1.

P2 Determine

ir BiB xx ˆminˆ = .

Determine jjk zz ∆=∆ min .

Se 0z e ˆ <∆≤∆ kBk rxz , então vá a P3.

Se 0ˆ e ˆ <∆<rr BkB xzx , então vá a P4.

Se 0z e 0ˆ ≥∆≥ kBrx , então PARE. A solução

atual é ótima.

P3 Iteração Primal. Calcule kk aBa1−= . Se 0>∃/ ika ,

então PARE. O problema tem solução ilimitada. Em caso contrário, determine a variável que deverá sair da base:

>== 0|

ˆminmin ik

ik

B

iiir aa

xiθθ

Vá para P5.

P4 Iteração Dual. Calcule RBeaT

rr

1−= , onde T

re é o

r-ésimo vetor linha unitário. Se 0<∃/ rja , então

PARE. O problema não tem solução viável. Em caso contrário, determine a variável que deverá entrar na base:

<

∆== 0|maxmax rj

rj

j

jjjk aa

zαα

P5 Troca de base. Efetue a troca de base entre as

variáveis kr RB xx ↔ . Determine a nova partição

para o PPL e retorne a P1.

Exemplo de Aplicação do Algoritmo Simplex Primal-Dual Max 321 423 xxx ++

s.a: 1022 321 ≥++ xxx

124 31 ≥+ xx 16321 ≤++ xxx

0,, 321 ≥xxx

Montando o problema na forma padrão, obtém-se as seguintes matrizes e vetores:

X1 3

X2 2

X = X3 C = 4

S1 0

S2 0

S3 0

2 1 2 -1 0 0 10

A = 1 0 4 0 -1 0 b = 12

1 1 1 0 0 1 16

Iteração 1

S1 -1 0 0 -1 -1 0 0

Xb = S2 B = 0 -1 0 B = 0 -1 0

S3 0 0 1 0 0 1

X1 2 1 2

Xr = X2 R = 1 0 4

X3 1 1 1

Cb' = 0 0 0 Cr' = 3 2 4

S1 -1 0 0 10 -10

Xb = S2 = 0 -1 0 * 12 = -12

S3 0 0 1 16 16

-1 0 0 2 1 2

dZ = 0 0 0 * 0 -1 0 * 1 0 4 - 3 2 4

0 0 1 1 1 1

dZ = -3 -2 -4 Observando os resultados verifica-se que as condições de otimalidade e viabilidade não são satisfeitas e que a realização de uma iteração dual é recomendada, escolhendo-se a segunda variável básica para sair da base.

-1 0 0 2 1 2

a2 = 0 1 0 * 0 -1 0 * 1 0 4 = -1 0 -4

0 0 1 1 1 1

= 3 ? 1Alfa e portanto a primeira variável não-básica entra na base.

Iteração 2

S1 -1 2 0 -1 -1 2 0

Xb = X1 B = 0 1 0 B = 0 1 0

S3 0 1 1 0 -1 1

S2 0 1 2

Xr = X2 R = -1 0 4

X3 0 1 1

Cb' = 0 3 0 Cr' = 0 2 4

S1 -1 2 0 10 14

Xb = X1 = 0 1 0 * 12 = 12

S3 0 -1 1 16 4

-1 2 0 0 1 2

dZ = 0 3 0 * 0 1 0 * -1 0 4 - 0 2 4

0 -1 1 0 1 1

dZ = -3 -2 8 Observando os resultados verifica-se que a solução é viável e que as condições de otimalidade não são satisfeitas e portanto a realização de uma iteração primal é recomendada, com a escolha da primeira variável não-básica para entrar na base.

-1 2 0 0 -2

a1 = 0 1 0 * -1 = -1

0 -1 1 0 1

?

= ?

4

Teta

e portanto a terceira variável básica sai da base.

Iteração 3

S1 -1 2 0 -1 -1 0 2

Xb = X1 B = 0 1 -1 B = 0 0 1

S2 0 1 0 0 -1 1

S3 0 1 2

Xr = X2 R = 0 0 4

X3 1 1 1

Cb' = 0 3 0 Cr' = 0 2 4

S1 -1 0 2 10 22

Xb = X1 = 0 0 1 * 12 = 16

S2 0 -1 1 16 4

-1 0 2 0 1 2

dZ = 0 3 0 * 0 0 1 * 0 0 4 - 0 2 4

0 -1 1 1 1 1

dZ = 3 1 -1 Verifica-se que as condições de viabilidade continuam sendo satisfeitas, o que ainda não acontece com as condições de otimalidade. Portanto, é recomendada uma iteração primal, escolhendo-se a terceira variável não-básica para entrar na base.

-1 0 2 2 0

a1 = 0 0 1 * 4 = 1

0 -1 1 1 -3

?

= 16

?

Teta

e a segunda variável básica é escolhida para sair da base.

Iteração 4

S1 -1 2 0 -1 -1 0 2

Xb = X3 B = 0 4 -1 B = 0 0 1

S2 0 1 0 0 -1 4

S3 0 1 2

Xr = X2 R = 0 0 1

X1 1 1 1

Cb' = 0 4 0 Cr' = 0 2 3

S1 -1 0 2 10 22

Xb = X3 = 0 0 1 * 12 = 16

S2 0 -1 4 16 52

-1 0 2 0 1 2

dZ = 0 4 0 * 0 0 1 * 0 0 1 - 0 2 3

0 -1 4 1 1 1

dZ = 4 2 1 e a solução é ótima. O valor da função objetivo poderá ser calculado por:

22

Z = 0 4 0 * 16 = 64

52

Interpretação dos Resultados Max 321 423 xxx ++ (Lucro)

s.a: 1022 321 ≥++ xxx (Subproduto 1)

124 31 ≥+ xx (Subproduto 2)

16321 ≤++ xxx (Mão de Obra)

0,, 321 ≥xxx

X1, X2, X3 são quantidades dos processos de produção

Var. Valor dZ

X1 0 1

X2 0 2

X3 16 0

S1 22 0

S2 52 0

S3 0 4

Z 64

Análise de Pós-otimalidade

Seja o PPL na forma padrão

Max xcT

s.a: bAx =

0≥x

e seja ( )**, RB xx a sua solução básica ótima. Se algum

parâmetro do modelo sofrer alteração, uma nova solução deverá ser determinada. Entre as alterações mais significativas, tem-se: 1. Alteração de um coeficiente do vetor b 2. Alteração de um coeficiente do vetor c a) associado a uma variável não-básica b) associado a uma variável básica 3. Inclusão e exclusão de restrição a) restrições não-ativas b) restrições ativas 4. Inclusão e exclusão de variável a) variáveis básicas b) variáveis não-básicas Obs. Em alguns sistemas computacionais (Lindo, MPSX, Excel) existe a opção de efetuar a análise sobre os coeficientes de b e de c .

Caso 1 - Alteração de um coeficiente do vetor b Os valores das variáveis básicas na solução ótima do

PPL é dada, a partir dos valores *Rx por:

( )*1*RB xRbBx −= −

Dado que um coeficiente do vetor b sofreu alteração, isto é, dado que o novo vetor b é dado por

rr ebb ⋅∆+= , onde re é o r-ésimo vetor coluna unitário

tem-se:

( ) ( )[ ]*1*1*RrrRB xRebBxRbBx −⋅∆+=−= −−

( ) rrBrrRB eBxeBxRbBx ⋅∆⋅+=⋅∆⋅+−= −−− 1*1*1*

Para que esta nova solução continue sendo ótima é necessário que:

01** ≥⋅∆⋅+= −

rrBB eBxx

ou

miBxx irrBB ii,...,1,01** =∀≥⋅∆+= −

Desta expressão obtém-se os limites r∆ para variação

de cada componente do vetor b , na forma apresentada abaixo.

<−

≤∆

>−

≥∆

≡−≥⋅∆

−

−

−

−−

0 se

0 se

1

1

*

1

1

*

*1

ir

ir

B

r

ir

ir

B

r

Birr

BB

x

BB

x

xB

i

i

i

Caso 2 - Alteração de um coeficiente do vetor T

Rc

Para a solução ótima de um PPL, tem-se:

01 ≤−=∆ −

jTB

TRj RBccZ

j, se 0ˆ =T

R jx

No caso do j-ésimo coeficiente do vetor TRc modificar,

isto é, se jTR

TR jj

cc ∆+= , tem-se para o caso da solução

básica permanecer ótima:

011 ≤−∆+=−=∆ −−

jTBj

TRj

TB

TRj RBccRBccZ

jj

0≤∆+∆=∆ jjj ZZ , ou

jj Z∆−≤∆

Caso 3 - Alteração de um coeficiente do vetor T

Bc

No caso do k-ésimo coeficiente do vetor T

Bc modificar,

isto é, se Tkk

TB

TB ecc ⋅∆+= , onde T

ke é o k-ésimo vetor

linha unitário, tem-se, para o caso da solução básica permanecer ótima:

( ) 01 ≤⋅∆+−=∆ −j

Tkk

TB

TRj RBeccZ

j

011 ≤⋅∆−−=∆ −−j

Tkkj

TB

TRj RBeRBccZ

j

0≤⋅∆−∆=∆ kjkjj RZZ ,

onde j

T

kkj RBeR1−=

<∆

≤∆

>∆

≥∆

≡∆≥⋅∆

0 se

0 se

kjkj

jk

kjkj

j

k

jkjk

RR

Z

RR

Z

ZR