Universidade Federal de Juiz de Fora - Programação LinearA Tabela Simplex anterior fornece a seguinte solução: x1 = 0, x2 = 60, u1 = 40, u2 = 0, u3 = 160 e Z = 90. Uma vez que

Fernando Nogueira Programação Linear 1

ProgramaProgramaçção Linearão Linear


Exemplo Típico

Uma industria produz 2 produtos, I e II, sendo que cada produto consome um certo número de horas em 3 máquinas A, B e C para ser produzido, conforme a tabela:

O tempo de funcionamento máximo disponível das máquinas é:

O lucro obtido por cada produto I é $1,00 e por cada produto II é $1,50.

Quanto fabricar de cada produto de modo que seja obedecida a capacidade operativa das máquinas com o maior lucro possível ?

Produto Tempo Máquina A Tempo Máquina B Tempo Máquina C

I 2 1 4

II 2 2 2

Máquina Máximo tempo disponível

A 160

B 120

C 280


( ) 2121 x5.1xZx,xlucroMax +==

Função Objetivo

⎪⎪⎩

⎪⎪⎨

⎧

≥≤+≤+≤+

0x,x280x2x4

120x2x160x2x2

21

21

21

21Máquina A

Máquina B

Máquina C

Prod. não negativa

Modelagem Matemática

Restrições

x1 a quantidade do produto I a ser fabricada

x2 a quantidade do produto II a ser fabricada

Em notação matricial

[ ] ⎥⎦

⎤⎢⎣

⎡=⇒=

2

1

122111 xx

.5.11ZxcZFunção Objetivo

Restrições

⎥⎥⎥

⎦

⎤

⎢⎢⎢

⎣

⎡≤⎥

⎦

⎤⎢⎣

⎡

⎥⎥⎥

⎦

⎤

⎢⎢⎢

⎣

⎡⇒≤

280120160

xx

.242122

bxA2

1

131223


Interpretação Geométrica

A região fechada formada pelas restrições é sempre convexa e contém todas as soluções possíveis ou viáveis: região das restrições.Teorema Fundamental da Programação Linear

Uma vez que todas as equações e/ou inequações envolvidas são lineares, o valor ótimo da função-objetivo Z só pode ocorrer em um dos vértices da região das restrições.


O Método Simplex (Dantzig, 1948)

Considerações Iniciais

O Método Simplex é um algoritmo que sistematiza a solução de problemas de P.L. de maneira eficiente computacionalmente (não éforça-bruta).

Seja m o número de equações e/ou inequações de restrição e n o número de variáveis (incógnitas), tem-se:

2 problemas ocorrem na resolução de 1)A existência de desigualdades implica que a solução égeralmente um conjunto e não única.

2)A não necessariamente possui inversa ⇒ geralmente A não équadrada .obs: o fato de A ser quadrada não garante a existência de inversa.

1nn111 xcZ = 1m1nnm bxA ≤

1m1nnm bxA ≤

( )nm ≠

( )>≥<≤ ou,,


Solução do Problema 1

Transformar as desigualdades em igualdades através da introdução de variáveis de folga (slack variables). Exemplo:

Solução do Problema 2

Anular n variáveis. Uma vez que (n + m) é sempre maior que m, sempre tem-se mais incógnitas de que equações, assim o sistema é sub-determinado ⇒ infinitas soluções. No entanto, anulando n variáveis, o sistema fica:

Quais n variáveis deve-se anular para obter solução ótima ???

0u,u,u,x,xcom280ux2x4280x2x4

120ux2x120x2x160ux2x2160x2x2

32121

32121

22121

12121

≥

⎪⎩

⎪⎨

⎧

=++⇔≤+=++⇔≤+=++⇔≤+

( ) ( ) 1m1mnmnm bxA =++

Tem-se então um sistema com m equações e (n + m) incógnitas:

1m1mmm bxA =


O Método

Reescrevendo a função-objetivo e as inequações como equações:

Deve-se achar uma solução inicial viável qualquer. A maneira mais simples para isto é “zerar” as variáveis de controle (x1 = x2 = 0). Com isso, as variáveis de folga assumem valores máximos (u1 = 160, u2 = 120 e u3 = 280). Esta é uma solução viável (nenhuma restrição foi violada), porém é a pior possível, pois Z = 0.

Pode-se classificar as variáveis do problema como:

Variáveis Básicas: variáveis que compõem a solução em cada iteração.

Variáveis Não-Básicas: variáveis que foram anuladas.

⎪⎪⎩

⎪⎪⎨

⎧

=++++=++++=++++=−−−−−

280uu0u0x2x4120u0uu0x2x160u0u0ux2x2

0u0u0u0x5.1xZ

32121

32121

32121

32121


Partindo de uma solução inicial qualquer, o Método Simplex verifica se existe uma outra solução que seja melhor que a solução atual. Isto se dáatravés da análise da função-objetivo:

Fazendo , as derivadas parciais de Z em relação as variáveis (de controle e de folga) fornecem a taxa de crescimento de Z nas direções destas variáveis.

O fato acima permite deduzir que enquanto houver variáveis não-básicas com coeficientes negativos em a solução poderá ser melhorada. Uma vez que o objetivo é maximizar Z, deve-se escolher dentre as variáveis não-básicas, aquela que possuir maior taxa de variação (coeficiente mais negativo) para compor as variáveis básicas, no caso x2. Para isso, alguma variável básica terá que deixar a base para compor as variáveis não-básicas. Qual variável deve deixar a base, ou seja, mudar do grupo das variáveis básicas para o grupo das variáveis não-básicas ?

0u0u0u0x5.1xZ 32121 =−−−−−

32121 u0u0u0x5.1xZ ++++=

1xZ

1

=∂∂ 0

uZ

2

=∂∂0

uZ

1

=∂∂5.1

xZ

2

=∂∂ 0

uZ

3

=∂∂

0u0u0u0x5.1xZ 32121 =−−−−−


A medida que x2 (a variável que era não-básica e agora é variável básica) aumenta, deve-se diminuir cada variável básica corrente correspondente a uma linha na qual x2 tenha coeficiente positivo. Assim, quanto x2 pode crescer antes que uma das variáveis básicas corrente atinja seu limite inferior 0 (não viole nenhum restrição) ?

Com isso, conclui-se que quando x2 = 60, u2 = 0, e portanto, poderá ir para o grupo das variáveis não-básicas.

básicanãoiávelvarépois,0x:obs140x0uPara280uu0u0x2x460x0uPara120u0uu0x2x80x0uPara160u0u0ux2x2

0u0u0u0x5.1xZ

1

2332121

2232121

2132121

32121

−=

⎪⎪⎩

⎪⎪⎨

⎧

=⇒==++++=⇒==++++=⇒==++++

=−−−−−

Antes AgoraVariáveis básicas u1,u2,u3 u1,x2,u3

Variáveis não-básicas x1,x2 x1,u2


Uma vez que x2 “entrou” na base e u2 “saíu” da base, faz-se necessário então alterar os valores dos coeficientes do sistema de equações de maneira equivalente. Este processo é obtido através do Método de Gauss-Jordan. Retomando o problema ao ponto inicial, pode-se montar a seguinte tabela (Tabela Simplex):

Se o vetor [2 2 2 –1.5]t (correspondente a coluna de x2) transformar-se no vetor [0 1 0 0]t (correspondente a coluna de u2), x2 estará pertencendo a base e u2 sairá da base. Para realizar o Método de Gauss-Jordan énecessário escolher o elemento pivô, o qual é obtido pela interseção da coluna pivô com a linha pivô.

00005.11280100241200102116000122

buuuxx 32121

−−

}}

Restrições

função-objetivo


A coluna pivô é a coluna correspondente à variável que vai entrar na base (x2 no caso) e a linha pivô é a linha na qual a interseção com a coluna correspondente à variável que vai sair da base é igual a 1 (no caso a interseção da 2 linha com a coluna correspondente a u2).

Realizando o Método de Gauss-Jordan a Tabela Simplex fica:

Esta tabela refere-se ao seguinte sistema:900430041

160110036002101214001101buuuxx 32121

−−

− }}

Restrições

função-objetivo

⎪⎪⎩

⎪⎪⎨

⎧

=+−++=++++=+−++=−+−−−

160uuu0x0x360u0u21u0xx2140u0uux0x90u0u43u0x0x41Z

32121

32121

32121

32121

}}

Restrições

função-objetivo


A Tabela Simplex anterior fornece a seguinte solução:

x1 = 0, x2 = 60, u1 = 40, u2 = 0, u3 = 160 e Z = 90.

Uma vez que x1 é uma variável não-básica e possui coeficiente negativo, esta deverá entrar base e conseqüentemente u1 deverá sair da base. Com esta alteração, a Tabela Simplex após o Método de Gauss-Jordan fica:

que corresponde ao seguinte sistema:1000214100

4012300400121104001101buuuxx 32121

−−

− }}

Restrições

função-objetivo

⎪⎪⎩

⎪⎪⎨

⎧

=++−++=++−++=+−++=−++−−

40uu2u3x0x040u0uu21xx040u0uux0x

100u0u21u41x0x0Z

32121

32121

32121

32121

}}

Restrições

função-objetivo


A Tabela Simplex anterior fornece a seguinte solução:

x1 = 40, x2 = 40, u1 = 0, u2 = 0, u3 = 40 e Z = 100.

Uma vez que não existe variáveis não-básicas com coeficiente negativo a solução não poderá mais ser melhorada, portanto, está solução é ótima.

Conclusão

Em P.L. existe maneiras de combinar n variáveis iguais a zero.

No exemplo, n = 2 e m = 3, que resulta em 10 soluções possíveis, o que implica que seria necessário resolver 10 sistemas de equações (força-bruta). No entanto, o Método Simplex resolveu apenas 2 sistemas de equações (neste caso) e alcançou a solução ótima.

obs: combinação

( )⎟⎟⎠

⎞⎜⎜⎝

⎛ +m

mn

( ) ⇒−=⎟⎟

⎠

⎞⎜⎜⎝

⎛!yx!y

!xyx


Solução de um Modelo Geral de P.L. pelo Método SimplexAté o momento

Função-Objetivo deve ser maximizadaVariáveis de controle não negativaApresentam uma solução básica inicial

Quando uma ou mais dessas características não são satisfeitas, faz-se necessário determinar uma forma equivalente ⇒ mudar o modelo e não o algoritmo. 1.MinimizaçãoSe a função-objetivo é de minimização deve-se multiplica-lá por –1.

obs: restrições não são alteradas.

}

321321 xx4x3ZMaxxx4x3ZMin −+−=−⇒+−=

Simplex exige essas 3 características


2.Variável Livre ou NegativaSubstituir a variável livre pela diferença de 2 outras não-negativas.Substituir a variável negativa por uma outra positiva com coeficiente -1.

⎪⎪⎪

⎩

⎪⎪⎪

⎨

⎧

≤⇒≥

≤+≤++

++=

0xlivrex

0x20x3x2

10xxxxx2xZMax

3

2

1

21

321

321

⎪⎩

⎪⎨

⎧

≥≤−+≤−−+

−−+=

0x,x,x,x20x3x3x210xxxx

xx2x2xZMax

6541

541

6541

6541

63

542

xxxxx

Fazendo

−=−=

3.Solução Básica InicialSe a restrição é do tipo faz-se necessário acrescentar uma variável de folga negativa.

Se a restrição é do tipo =, já tem-se um equação e, portanto, não é preciso acrescentar variável de folga. No entanto, quando estes 2 casos ocorrem não é formada uma sub-matriz identidade automaticamente e, portanto, não origina uma solução básica inicial.Exemplo:

0ucom,10ux10x 1111 ≥=−⇒≥

x3 negativa


⇒

⎪⎪⎩

⎪⎪⎨

⎧

≥=++≥++≤−+

++=

0x,x,x60x3xx2

20x2xx10xxx2

xxxZMax

321

321

321

321

321

⎪⎪⎩

⎪⎪⎨

⎧

=++++=−+++=++−+=−−−−−

60u0u0x3xx220uu0x2xx10u0uxxx20u0u0xxxZ

21321

21321

21321

21321

000111600031220102111001112

buuxxx 21321

−−−

−− }

}

Restrições

função-objetivo

A Tabela Simplex fica:

Nota-se na Tabela Simplex que não existe uma sub-matriz identidade. Neste caso, acrescenta-se Variáveis Artificiais (Auxiliares) nas linhas cujas as restrições são do tipo

ou = . O sistema fica:≥


0a,a,u,u,u,x,x,xcom

60aa0u0u0x3xx220a0auu0x2xx10a0a0u0uxxx20a0a0u0u0xxxZ

32321321

3221321

3221321

3221321

3221321

≥

⎪⎪⎩

⎪⎪⎨

⎧

=++++++=++−+++=++++−+=−−−−−−−


00000111601000312200110211100001112

baauuxxx 3221321

−−−

−− }

}

Restrições

função-objetivoAgora tem-se uma sub-matriz identidade, porém a2= 20 e a3 = 60.

O retorno ao modelo original deve ser feito com a eliminação das Variáveis Artificiais. Isto é realizado através do Método do M Grande ou do Método da Função-Objetivo Auxiliar.


Método da Função-Objetivo AuxiliarEste método consiste em utilizar uma função-objetivo auxiliar W(a1,a2,...,ar) formada pela soma das r Variáveis Artificiais ⇒ W(a1,a2,...,ar) = a1 + a2 + ... + ar .

Uma vez que as Variáveis Artificiais podem ser escritas em função das Variáveis de Controle e de Folga, pode-se sempre minimizar W(a1,a2,...,ar) até W(a1,a2,...,ar) = 0, o que corresponde a a1= a2 = ... = ar = 0, fazendo então as Variáveis Artificiais pertencerem ao grupo das Variáveis Não-Básicas. Com isso, obtém-se uma solução viável para o problema podendo-se então abandonar a Função-Objetivo Auxiliar e as Variáveis Artificiais. Exemplo:

Função-Objetivo Auxiliar

W(a2,a3) = a2 + a3

⇒

⎪⎪⎩

⎪⎪⎨

⎧

≥=++≥++≤−+

++=

0x,x,x60x3xx2

20x2xx10xxx2

xxxZMax

321

321

321

321

321

0a,a,u,u,u,x,x,xcom

60aa0u0u0x3xx220a0auu0x2xx10a0a0u0uxxx20a0a0u0u0xxxZ

32321321

3221321

3221321

3221321

3221321

≥

⎪⎪⎩

⎪⎪⎨

⎧

=++++++=++−+++=++++−+=−−−−−−−

Dá 2o restrição a2 = – x1 – x2 – 2x3 + u2 + 20

Dá 3o restriçãoa3 = – 2x1 – x2 – 3x3 + 60


Substituindo a2 e a3 em W(a2,a3), fica:

Min W(a2,a3) = Max – W(a2,a3) = 3x1 + 2x2 + 5x3 – u2 – 80 = 0

que na forma de equação é – W(a2,a3) – 3x1 – 2x2 – 5x3 + u2 = – 80


80001052300000111

601000312200110211100001112

baauuxxx 3221321

−−−−−−−

−− }

}

Restrições

função-objetivo} função-objetivo

auxiliarApós 2 iterações (neste exemplo) do Método Simplex, a Tabela Simplex fica:

01100000203

1000032

31

203211003

13

1203

1000131

32

303100103

46

16baauuxxx 3221321

−−

−−}}}

Restrições

função-objetivofunção-objetivo

auxiliar


A Tabela Simplex agora apresenta uma solução cuja as Variáveis Artificiais são Variáveis Não-Básicas (portanto, iguais a zero) e podem então ser desprezadas e o Método Simplex pode continuar sendo utilizado a fim de encontrar a solução ótima.Considerações Finais1.Problema de DegeneraçãoA saída de uma V.B. com valor nulo provoca o aparecimento de uma outra V.B. nula na próxima solução sem alteração do valor da Função-Objetivo. Neste caso a solução é denominada degenerada, indicando que existe, no mínimo, uma restrição redundante. Se os coeficientes da Função-Objetivo retornam não negativos em alguma iteração, o caso não apresenta dificuldade. O problema surge quando as iterações levam a circuitos, sem caracterizar a solução ótima. Neste caso faz-se necessário utilizar regras mais complexas, as quais não serão abordadas neste curso. Tal problema é bastante raro em aplicações práticas.2.Solução IlimitadaOcorre quando a variável que entra na base não possui em sua coluna nenhum coeficiente positivo, não sendo portanto possível determinar a linha pivô. Exemplo:

⎪⎩

⎪⎨

⎧

≥≤+−

≥+

+=

0x,x0xx

40xxx0xZMax

21

21

21

21


3.Soluções Múltiplas

Se na solução ótima o coeficiente de um V.N.B. é zero, esta variável poderá entrar na base sem alterar o valor da função objetivo, gerando outra solução ótima. Neste caso qualquer combinação linear dessas 2 soluções também será ótima. Exemplo:

⎪⎩

⎪⎨

⎧

≥≤+≤+

+=

0x,x10x5x212x3x4

x10x4ZMax

21

21

21

21

4.Soluções Inviável

Se o problema de P.L. não possuir nenhuma solução viável, então o Método da Função-Objetivo Auxiliar (ou do M Grande) irá fornecer na solução final no mínimo uma variável artificial com valor diferente de zero, caso contrário, todas variáveis artificiais serão nulas. Exemplo:

⎪⎩

⎪⎨

⎧

≥≥+−

≥−

+=

0x,x1xx

1xxxxZMax

21

21

21

21


5.Lado Direito das Restrições Negativas

Solução Inicial: x1 = x2 = 0, u1 = -1 e u2 = -10 ⇒ Inviável, pois u1 e u2 são negativos.

Sempre que houver restrições cujo lado direito são negativos deve-se multiplicar ambos os lados destas restrições por –1.

Solução Inicial: x1 = x2 = u1 = u2 = 0, a1= 1, a2 = 10 ⇒ Viável.

⎪⎩

⎪⎨

⎧

≥−=+++−=+++

⇒⎪⎩

⎪⎨

⎧

≥−≤+

−≤+

0u,u,x,x10uu0x5x21u0uxx

0x,x10x5x2

1xx

2121

2121

2121

21

21

21

⎪⎩

⎪⎨

⎧

≥=++−−−−=++−−−−

⎪⎩

⎪⎨

⎧

≥⇒≥−−

≥−−⇒

⎪⎩

⎪⎨

⎧

≥−≤+

−≤+

0a,a,u,u,x,x10aa0uu0x5x21a0au0uxx

0x,x10x5x2

1xx

0x,x10x5x2

1xx

212121

212121

212121

21

21

21

21

21

21

Documents

Universidade Federal de Juiz de Fora - Programação LinearA Tabela Simplex anterior fornece a seguinte solução: x1 = 0, x2 = 60, u1 = 40, u2 = 0, u3 = 160 e Z = 90. Uma vez que