Método de M Grande

Prévia do material em texto

3.2.3. Método de M Grande
Para um problema de Programação Linear em que todas as restrições são do tipo 
menor ou igual (≤), com os termos independentes não negativos, as varáveis de folgas 
introduzidas asseguram uma conveniente solução básica inicial. Entretanto, uma questão 
natural surge quando se pretende determinar uma solução básica inicial para modelos 
que envolvem restrições do tipo igualdade (=) e do tipo maior ou igual (≥). Para modelos 
desta natureza, o procedimento comum é o de introdução de variáveis fictícias, que 
assumem o papel de variáveis de folga na primeira solução básica. E o método de M 
Grande é aplicado para resolução de problemas deste tipo.
O Método de M Grande começa com a apresentação do problema de PL na forma 
canónica. Neste processo, todas as restrições do tipo maior ou igual (≥) e as do tipo 
igualdade (=) recebem variáveis de fictícias RI. Estas variáveis fazem parte da primeira 
solução básica. Entretanto, dado que as variáveis fictícias são externas ao modelo 
original de PL elas são penalizadas na Função Objectiva através de um valor M 
suficientemente grande. E dado que o M é um valor positivo suficientemente grande, 
toda variável Ri é penalizada na Função Objectivo com:
• sinal negativo (–), no caso de maximização; e 
• sinal positiv0 (+), no caso de minimização.
Devida esta penalização, a natureza do processo de optimização logicamente 
tenderá a anular toda variável Ri ao longo das iterações do Simplex. O exemplo a seguir 
dá detalhes sobre o Método de M Grande.
Exemplo Nº 1: Seja dado o seguinte problema de Programação Linear:
0,
3
1523
234:
6:
21
21
21
21
21
≥
=−
≥+
≤+
+=
xx
xx
xx
xxaSujeito
xxzMaximizar
Para resolver este problema de PL pelo Método de M Grande é necessário reduzir 
o problema na forma canónica, transformando todas as restrições em igualdades. Neste 
caso, em que nem todas as restrições são do tipo menor ou igual, deve-se adicionar uma 
variável de folga (s1), no primeiro membro da primeira restrição, subtrair uma variável de 
excesso (S2), na segunda restrição e não alterar a terceira restrição. Além disso, deve-se 
modificar a função objectiva. Estas operações têm como resultado o problema 
apresentado na forma canónica, com o seguinte aspecto:
0,,,
3
1523
234:
006:
2121
21
221
121
2121
≥
=−
=−+
=++
+++=
Ssxx
xx
Sxx
sxxaSujeito
SsxxzMaximizar
A segunda e a terceira restrições não possuem variáveis que possam desempenhar 
o papel da variável de folga na determinação da primeira Solução Básica. Assim, deve ser 
introduzidas duas varáveis fictícias (R1 e R2) nesta duas restrições e penaliza-las na 
Função Objectivo. Estas operações têm como resultado o problema com o seguinte 
aspecto:
0,,,,
3
1523
234:
6:
212121
221
1221
121
2121
≥
=+−
=+−+
=++
+++=
RRSsxx
Rxx
RSxx
sxxaSujeito
MRMRxxzMaximizar
Em seguida, deve-se escolher as variáveis a entrar na primeira Solução Básica, 
através da determinação do número de graus de liberdade (D). Neste exemplo, após a 
introdução das variáveis de folga, de excesso e fictícias, o problema passou a ter seis (6) 
variáveis. Entretanto, o número de restrições mantém-se igual a três (3). Assim, o 
número de graus de liberdade será:
D=6 – 3 = 3
E no presente exemplo, D=3 indica que devem ser anuladas três (3) variáveis. E, 
segundo as regra, devem ser anuladas inicialmente as variáveis originais do problema e, 
em seguida, as de excesso. E, após a última transformação do problema as suas 
restrições ficaram com o seguinte aspecto:
3
1523
234
221
1221
121
=+−
=+−+
=++
Rxx
RSxx
sxx
Destas relações, e de acordo com as regras, anulando as variáveis originais do 
problema (x1 e x2), e a variável de excesso (S2), obtém-se a primeira Solução Básica, que 
é a seguinte:








=
=
=
=
===
0
3
15
23
0
2
1
1
221
z
R
R
s
Sxx
Depois da terminação da primeira Solução Básica construi-se a primeira Tabela do 
Simplex, procedendo de modo análogo aos casos anteriores. Entretanto, a linha da 
Função Objectivo (linha do z) deve ser apresentada mostrando os efeitos da penalização 
decorrente da introdução das variáveis fictícias no modelo original. Deste modo, tem-se a 
seguinte tabela:
x1 x2 s1 S2 R1 R2
s1 1 4 1 0 0 0 23
R1 3 2 0 – 1 1 0 15
R2 1 – 1 0 0 0 1 3
z – 1 – 4M – 6 – M 0 M 0 0 – 18M
Nesta tabela, as três linhas intermédias representam as equações das restrições 
cujos termos independentes estão dados na última coluna. E a linha do z obtém-se 
passando todas as variáveis da função objectivo para o primeiro membro e penalizando 
as variáveis fictícias (R1 e R2).
Passando todas as variáveis da Função Objectivo, tem-se: 
Z – x1 – 6x2 = 0.
Os elementos da Linha da Função Objectivo foram obtidos associando os 
coeficientes de x1 e x2 da última expressão associadas aos valores decorrentes da 
penalização das variáveis fictícias que são obtidos através do produto de +M ou –M, pela 
soma dos coeficientes constantes nas linhas das variáveis fictícias Ri.
Neste caso de Maximização utiliza-se –M, para a penalização e os coeficientes das 
segunda e terceira linhas, pois é nestas linhas onde figurão as variáveis fictícias R1 e R2. 
Assim, os elementos da linha da Função Objectivo foram obtidos de seguinte modo:
• para a coluna de x1: – 1 + (3 + 1)×(–M) = – 1 – 4M;
• para a coluna de x2: – 6 + (2 – 1)×(–M) = – 6 – M;
• para a coluna de s1: 0 + (0 + 0)×(–M) = 0;
• para a coluna de S2: 0 + (–1 + 0)×(–M) = M; e
• para a última coluna: 0 + (15 + 3)×(–M) = – 18M; e
• as colunas das variáveis fictícias (R1 e R2) não são penalizadas.
x1 x2 s1 S2 R1 R2
s1 1 4 1 0 0 0 23
R1 3 2 0 – 1 1 0 15
R2 1 – 1 0 0 0 1 3
z – 1 – 4M – 6 – M 0 M 0 0 – 18M
As transformações iterativas das tabelas de Simplex, até se atingir os valores 
óptimos do problema, são feitas de modo análogo aos casos anteriores. Neste caso, em 
que se procura determinar um máximo, de acordo com as regras, escolhe-se a variável 
que apresenta o coeficiente mais negativo na linha da Função Objectivo (z). Deste modo, 
será a coluna de – 1 – 4M, pois, M é um valor suficientemente grande. Por isso, (– 1 – 4M) 
é menor que (– 6 – M).
Entretanto, para transformar a última linha (linha de z) é necessário determinar o 
factor a ser usado nas operações do Pivot para a transformação de todos elementos 
desta linha. Neste caso, e de acordo com as regras, o elemento da Coluna Pivot é menos 
três (– 1 – 4M) e o seu simétrico é três (1 + 4M). Dividindo esta última expressão pelo 
Elemento Pivot (1) obtém-se (1 + 4M). E para obtenção dos novos elementos desta linha 
é necessário fazer as operações do Pivot. Assim, os novos elementos da última linha 
serão os seguintes:
• para a coluna de x1: 0)41(141 =+×+−− MM ;
• para a coluna de x2: MMM 57)41(16 −−=+×−−− ;
• para a coluna de s1: 0)41(00 =+×+ M ;
• para a coluna de S2: MMM =+×+ )41(0 ;
• para a coluna de R1: 0)41(00 =+×+ M ;
• para a coluna de R2: MM 41)41(10 +=+×+ ; e
• para a coluna das soluções: MMM 63)41(318 −=+×+− .
x1 x2 s1 S2 R1 R2
s1 0 5 1 0 0 – 1 20
R1 0 5 0 – 1 1 – 3 6
x1 1 – 1 0 0 0 1 3
z 0 – 7 – 5M 0 M 0 1 + 4M 3 – 6M
Toda variável fictícia, após ser anulada deve ser retirada da Tabela de Simplex. 
Sendo assim, a próxima tabela não apresenta a coluna de R1.
x1 x2 s1 S2 R1
s1 0 0 1 1 – 1 14
x2 0 1 0 – 
5
1
5
1
5
6
x1 1 0 0 – 
5
1
5
1
5
21
z 0 0 0 – 
5
7
M+
5
7
5
57
Desta tabela pode-se observar que ainda existe uma Coluna Pivot, facto que indica 
que ainda não foi atigida a solução óptima do problema. Sendo assim, fazendo–se a sua 
transformação de modo análogo aos casos anteriores, obtém-se a seguinte tabela:
x1 x2 s1 S2
s2 0 0 1 1 14
x2 0 1
5
1 0 4
x1 1 0
5
1 0 7
z 0 0
5
7 0 31
Desta última tabela, pode-se observar que já não existem mais valores negativos 
na linha da Função Objectivo. Isto significaque já foram encontrados os valores óptimos. 
E a solução óptima do problema é extraída directamente da tabela e é a seguinte:







=
=
=
=
31
14
4
7
*
2
*
2
*
1
z
s
x
x
Exemplo Nº 2: Seja dado o seguinte problema de Programação Linear:
0,
232
10
723:
3:
21
21
21
21
21
≥
=+−
≤+
≥−
+=
xx
xx
xx
xxaSujeito
xxzMinimizar
A resolução deste problema procedesse de modo análogo ao caso anterior. Isto é, 
no início faz-se a transformação do problema para forma canónica, introduzindo:
• uma variável de excesso (S1) e uma variável fictícia (R1), na primeira restrição, por 
ser do tipo maior ou igual (≥);
• uma variável de folga (s2) na segunda restrição, por ser do tipo menor ou igual (≤);
• uma variável fictícia (R2) na terceira restrição, por ser do tipo igualdade (=).
0,,,,,
232
10
723:
3:
212121
221
221
1121
2121
≥
=++−
=++
=+−−
+++=
RRsSxx
Rxx
sxx
RSxxaSujeito
MRMRxxzMinimizar
Depois da transformação, usam-se as novas restrições para determinar a primeira 
Solução Básica. Para além disso, é necessário apresentar a Função Objectivo com todas 
as variáveis no primeiro membro. Assim, tem-se:
232
10
723
221
221
1121
=++−
=++
=+−−
Rxx
sxx
RSxx
Neste caso, o número de graus de liberdade será D=6 – 3 =3 o que implica que a 
primeira Solução Básica será:








=
=
=
=
===
0
2
10
7
0
2
2
1
121
z
R
s
R
Sxx
Após a transformação a função objectivo fica com o seguinte aspecto:
03 21 =−− xxz
Depois da terminação da primeira Solução Básica e da transformação da função 
objectivo, construi-se a primeira tabela de Simplex, que é a seguinte: 
x1 x2 S1 s2 R1 R2
R1 3 – 2 – 1 0 1 0 7
s2 1 1 0 1 0 0 10
R2 – 2 3 0 0 0 1 2
z – 1 + M – 3 + M – M 0 0 0 9M
Neste caso de Minimização utiliza-se +M, para a penalização e os coeficientes das 
primeira e terceira restrições, pois é nelas onde figurão as variáveis fictícias R1 e R2. 
Assim, os elementos da linha da Função Objectivo foram obtidos de seguinte modo:
• para a coluna de x1: – 1 + (3 – 2)×M = – 1 + M;
• para a coluna de x2: – 3 + (– 2 + 3)×M = – 3 + M;
• para a coluna de S1: 0 + ( – 1 + 0)×M = – M;
• para a coluna de s2: 0 + (0 + 0)×M = 0; e
• para a última coluna: 0 + (7 + 2)×M = 9M; e
• as colunas das variáveis fictícias (R1 e R2) não são penalizadas.
As transformações iterativas das tabelas de Simplex, até se atingir os valores 
óptimos do problema, são feitas de modo análogo aos casos anteriores. Neste caso, em 
que se procura determinar um mínimo, de acordo com as regras, escolhe-se a variável 
que apresenta o coeficiente mais positivo na linha da Função Objectivo (z). Deste modo, 
será a coluna de (–1+M), pois, M é um valor suficientemente grande. Por isso, (–1+M) é 
maior que (–3+M).
Entretanto, para transformar a última linha (linha de z) é necessário determinar o 
factor a ser usado nas operações do Pivot para a transformação de todos elementos 
desta linha. Neste caso, e de acordo com as regras, o elemento da Coluna Pivot é (– 1+M) 
e o seu simétrico é três (1–M). Dividindo esta última expressão pelo Elemento Pivot, o 
três (3), obtém-se ( 3
1 M− ). E para obtenção dos novos elementos desta linha é necessário 
fazer as operações do Pivot. Assim, os novos elementos da última linha serão os 
seguintes:
• para a coluna de x1: 0)
3
1
(31 =−×++− MM ;
• para a coluna de x2: M
M
M
3
5
3
11
)
3
1
(23 −−=−×−+− ;
• para a coluna de S1: M
M
M
3
2
3
1
)
3
1
(1 −−=−×−− ;
• para a coluna de s2: 0)
3
1
(00 =−×+ M ;
• para a coluna de R1: M
M
3
1
3
1
)
3
1
(10 −=−×+ ;
• para a coluna de R2: 0)
3
1
(00 =−×+ M ; e
• para a coluna das soluções: M
M
M
3
20
3
7
)
3
1
(79 +=−×+ .
Assim, após a transformação, usando-se as operações do Pivot, obtém-se a 
seguinte tabela:
x1 x2 S1 s2 R1 R2
x1 1 – 
3
2
– 
3
1 0
3
1 0
3
7
s2 0
3
5
3
1 1 – 
3
1 0
3
23
R2 1
3
5
– 
3
2 0
3
2 1
3
20
z 0 M
3
5
3
11 +− M
3
2
3
1 −− 0 M
3
1
3
1 − 0 M
3
20
3
7 +
Como se sabe, toda variável fictícia, após ser anulada deve ser retirada da Tabela 
de Simplex. Sendo assim, a próxima tabela não apresenta a coluna de R1.
x1 x2 S1 s2 R2
x1 1 0 – 
5
3 0
5
2 5
s2 0 0 1 1 – 1 1
x2 0 1 – 
5
2 0
5
3 4
z 0 0 – 
5
9 0 M−
5
11 17
Desta última tabela, pode-se observar que já não existem mais valores positivos 
na linha da Função Objectivo. Isto significa que já foram encontrados os valores óptimos. 
E a solução óptima do problema é extraída directamente da tabela e é a seguinte:







=
=
=
=
17
1
4
5
*
2
*
2
*
1
z
s
x
x
3.2.3.2. Problemas Resolvidos
Exercício Nº 1: Resolva o seguinte problema de Programação Linear:
0,,
723
62
2132:
52:
321
321
21
321
321
≥
≥+−
=−
≤++
+−=
xxx
xxx
xx
xxxaSujeito
xxxzMaximizar
1º)Transformar o problema na forma canónica;
0,,,,,,
723
62
2132:
52:
2121321
22321
121
1321
21321
≥
=+−+−
=+−
=+++
+++−=
RRSsxxx
RSxxx
Rxx
sxxxaSujeito
MRMRxxxzMaximizar
2º)Determinar a primeira Solução Básica;
723
62
2132
22321
121
1321
=+−+−
=+−
=+++
RSxxx
Rxx
sxxx
D = 7 – 3 = 4 ⇒: 








=
=
=
=
====
0
7
6
21
0
2
1
1
2321
z
R
R
s
Sxxx
3º)Modificar a Função Objectivo.
0)(52 21321 =++−+− RRMxxxz
4º)Compor a primeira tabela de Simplex e efectuara as sua transformações iterativas.
x1 x2 x3 s1 S2 R1 R2
s1 2 1 3 1 0 0 0 21
R1 1 -2 0 0 0 1 0 6
R2 1 -3 2 0 –1 0 1 7
Z 2–2M 2+5M –5–2M 0 M 0 0 –13M
x1 x2 x3 s1 S2 R1 R2
s1
2
1
2
11 0 1
2
3 0 –
2
3
2
21
R1 1 –2 0 0 0 1 0 6
x3
2
1
–
2
3 1 0 –
2
1 0
2
1
2
7
z M−
2
1
M2
2
11 +− 0 0 –
2
5 0 M+
2
5
M6
2
35 −
x1 x2 x3 s1 S2 R1
s1 0
2
13 0 1
2
3
–
2
1
2
15
x1 1 -2 0 0 0 1 6
x3 0 –
2
1 1 0 –
2
1
–
2
1
2
1
z 0 –
2
9 0 0 –
2
5
M+−
2
1
2
29
x1 x2 x3 s1 S2
x2 0 1 0
13
2
13
3
13
15
x1 1 0 0
13
4
13
6
13
108
x3 0 0 1
13
1
13
5−
13
14
z 0 0 0
13
9
13
19−
13
256
x1 x2 x3 s1 S2
S2 0
3
13 0
3
2 1 5
x1 1 -2 0 0 0 6
x3 0
3
5 1
3
1 0 3
z 0
3
19 0
3
5 0 27
5º) Compor a solução óptima do problema: 








=
=
=
=
=
27
5
3
0
6
*
2
*
3
*
2
*
1
z
S
x
x
x
Exercício Nº 2: Resolva o seguinte problema de Programação Linear:
0,,
725
23
15425:
3:
321
321
32
321
321
≥
=++
≤−
≥++
−+=
xxx
xxx
xx
xxxaSujeito
xxxzMinimizar
1º)Transformar o problema na forma canónica;
0,,,,,,
725
23
15425:
3:
2121321
2321
232
11321
21321
≥
=+++
=+−
=+−++
++−+=
RRSsxxx
Rxxx
sxx
RSxxxaSujeito
MRMRxxxzMinimizar
2º)Determinar a primeira Solução Básica;
723
23
15425
2321
232
11321
=++−
=+−
=+−++
Rxxx
sxx
RSxxx
D = 7 – 3 = 4 ⇒: 








=
=
=
=
====
0
7
2
15
0
2
2
1
1321
z
R
s
R
Sxxx
3º)Modificar a Função Objectivo.
0)(3 21321 =+++−− RRMxxxz
4º)Compor a primeira tabela de Simplex e efectuara as sua transformações iterativas.
x1 x2 x3 S1 s2 R1 R2
R1 5 2 4 –1 0 1 0 15
s2 0 3 –1 0 1 0 0 2
R2 1 5 2 0 0 0 1 7
z –1+6M –3+7M 1+6M –M 0 0 0 22M
x1 x2 x3 S1 s2 R1 R2
R1 5 0
3
14 –1
3
2− 1 0
3
41
x2 0 1
3
1− 0
3
1 0 0
3
2
R2 1 0
3
11 0
3
5− 0 1
3
11
z -1+6M 0 M
3
25 –M M
3
7
1 − 0 0 M
3
52
2 +
x1 x2 x3 S1 s2 R1 R2
R1
11
41 0 0 –1
11
16 1
11
14− 9
x2
11
1 1 0 0
11
2 0
11
1 1
x3
11
3 0 1 0
11
5− 0
11
3 1
z M
11
41
1+− 0 0 –M M
11
16
1+ 0 M
11
25− 2+9M
x1 x2 x3 S1 s2 R1
x1 1 0 0
41
11−
41
16
41
11
41
99
x2 0 1 0
41
1
41
6
41
1−
41
32
x3 0 0 1
41
1
41
23−
41
3−
41
14
z 0 0 0
41
11−
41
57
M−
41
11
41
181
x1 x2 x3 S1 s2
x1 1
3
8− 0
3
1− 0
3
1
s2 0
6
46 0
6
1 1
3
16
x3 0
6
23 1
6
1 0
3
10
z 0
2
19− 0
2
1− 0 –3
5º) Compor a solução óptima do problema: 










−=
=
=
=
=
3
3
16
3
10
0
3
1
*
2
*
3
*
2
*
1
z
s
x
x
x
3.2.4. Casos especiais no Método de Simplex
Esta secção considera quatro casos especiais que têm surgido na aplicação do 
Método de Simplex, a saber:
• soluções degeneradas;• soluções alternativas;
• soluções ilimitadas; e
• soluções inexistentes ou inviáveis.
Existem duas razões essenciais para o interesse no estudo dos casos especiais no 
Método de Simplex. Estas são:
• a explicação teórica das razões de surgimento destes casos; e
• a interpretação prática destes casos em problemas reais.
3.2.4.1. Soluções degeneradas.
Na aplicação das condições de viabilidade do Método de Simplex, para a 
determinação da variável a sair da solução básica, a regra de selecção do mínima razão 
positiva pode não ser satisfeita. Por exemplo, uma ou mais variáveis básicas podem 
assumir o valor zero (0) após a conclusão de uma certa iteração. Neste caso, a nova 
solução obtida é degenerada.
Exemplo 1 – Considere o seguinte problema:
0,
42
84:
73:
21
21
21
21
≥
≤+
≤+
+=
xx
xx
xxSujeito
xxzMaximizar
Resolvendo este problema tem-se:
0,,,
42
84:
)(073:
2121
221
121
2121
≥
=++
=++
+++=
ssxx
sxx
sxxSujeito
ssxxzMaximizar
42
84
221
121
=++
=++
sxx
sxx






=
=
=
==
⇒=−=
0
4
8
0
224
2
1
21
z
s
s
xx
D
073 21 =−−= xxz
1x 2x 1s 2s
1s 1 4 1 0 8
2s 1 2 0 1 4
z –3 –7 0 0 0
1x 2x 1s 2s
2x
4
1 1
4
1 0 2
2s
2
1 0
2
1 1 0
z
4
5− 0
4
5− 0 14
Nesta iteração inicial, qualquer uma das variáveis de folga s1 e s2 podia sair da 
solução básica. Por esta razão, ao se escolher a variável s1 a variável s2 assumiu o valor 
zero (0). Resultando, deste modo, uma solução básica degenerada. E a solução óptima é 
alcançada após se efectuar uma iteração adicional.
1x 2x 1s 2s
2x 0 1
2
1
2
1− 2
1x 1 0 –1 2 0
z 0 0
2
1
2
5 14
Deste modo obtém-se a solução óptima degenerada é a seguinte: 





=
=
=
14
2
0
*
*
2
*
1
z
x
x
A implicação prática de degenerescência pode ser explicada através da figura 9 
que dá a solução gráfica do modelo. Naquela figura, pode-se observar que três rectas 
passam pelo ponto optimizado (x1=0; x2=2). Uma vez que se trata de um problema 
bidimensional, o ponto diz-se que é sobredeterminado, pois necessita-se apenas de duas 
rectas para o definir. Deste modo, conclui-se que uma das restrições é redundante. 
Na prática, o simples conhecimento de que alguns dos recursos são supérfluos 
pode tornar-se muito útil durante a escolha da solução. Esta informação pode, também, 
levar a identificação de irregularidades no estabelecimento do modelo. Infelizmente, não 
existem regras para identificar as restrições redundantes a partir do Quadro de Simplex. 
Por isso, na ausência da resolução gráfica é difícil localizar a redundância.
1 2 3 5 6 7 8-1-2-3-4
-1
-2
1
6
5
4
3
2
0 x1
x2
4 9
•
7
x
1 + 4x2 ≤ 8 (redundante)
x
1 + 2x
2 ≤ 4
z = 3x1 + 7x
2
Solução óptima
degenerada
Figura 3.8. – Solução óptima degenerada
Sob o ponto de vista teórico, a degenerescência tem duas implicações, a saber:
i. A recirculação – se verificar-se as iterações 1 e 2, dos quadros de Simplex 
anteriores, observa-se que o valor da função objectivo não muda (z=14). Admite-
se assim, em termos genéricos, que o Método de Simplex repetirá a mesma 
sequência de iterações sem nuca melhorar o valor da função objectivo e sem 
terminar os cálculos;
ii. A identidade das soluções – examinando-se as mesmas iterações 1 e 2, pode-se 
observar que ambas conduzem a valores idênticos para todas as variáveis e para a 
função objectivo (x1=0, x2=2, s1=0, s2=0 e z=14), embora sejam diferentes na 
classificação das varáveis em básicas e não básicas.
Deste modo, pode-se admitir a possibilidade de se para os cálculos assim que se 
revele a degenerescência, apesar de se obter a solução óptima. No entanto, este 
conceito não é aceitável, pois a solução pode ser temporariamente degenerada, segundo 
o exemplo abaixo.
Exemplo 2 – Considere o seguinte problema:
0,
1234
84
84:
23:
21
21
21
21
21
≥
≤+
≤−
≤+
+=
xx
xx
xx
xxSujeito
xxzMaximizar
Resolvendo este problema tem-se:
0,,,,
1234
84
84:
)(023:
32121
321
221
121
32121
≥
=++
=+−
=++
++++=
sssxx
sxx
sxx
sxxSujeito
sssxxzMaximizar
1234
84
84
321
221
121
=++
=+−
=++
sxx
sxx
sxx








=
=
=
=
==
⇒=−=
0
12
8
8
0
235
3
2
1
21
z
s
s
s
xx
D
023 21 =−−= xxz
1x 2x 1s 2s 3s
1s 4 1 1 0 0 8
1s 4 –1 0 1 0 8
3s 4 3 0 0 1 12
z –3 –2 0 0 0 0
1x 2x 1s 2s 3s
1x 1
4
1
4
1 0 0 2
2s 0 –3 –1 1 0 0
3s 0 2 –1 0 1 4
z 0
4
5−
4
3 0 0 6
Observando-se o último quadro, verifica-se a degenerescência aparece nesta 
iteração 1. Entretanto, efectuando-se a segunda iteração, verifica-se que, diferentemente 
do caso anterior, a degenerescência desaparece na iteração 2 e o valor da função 
objectivo melhora de z=6 na iteração 1, para 2
17=z , na iteração 2, conforme se observa 
no quadro abaixo.
1x 2x 1s 2s 3s
1x 1 0
8
3 0
8
1−
2
3
2s 0 0
2
5− 1
2
3 6
2x 0 1
2
1− 0
2
1 2
z 0 0
8
1 0
8
5
2
17
Neste caso em que a degenerescência ocorre uma iteração intermédia o problema 
tem solução temporariamente degenerada. Por esta razão, as iterações do Simplex 
devem ser continuadas até se encontrar a solução óptima. E para este caso, a solução 
óptima não degenerada do problema é a seguinte:







=
=
=
2
17
2
2
3
*
*
2
*
1
z
x
x
3.2.4.2. Soluções alternativas.
Geralmente, quando a função objectivo é paralela a uma das restrições, ela 
assume um valor optimizado em mais do que um ponto, como soluções. Por isso, estas 
soluções são chamadas soluções alternativas.
Exemplo 1 – Considere seguinte problema:
0,
4
52:
42:
21
21
21
21
≥
≤+
≤+
+=
xx
xx
xxSujeito
xxzMaximizar
Resolvendo este problema tem-se:
0,,,
4
52:
)(042:
2121
221
121
2121
≥
=++
=++
+++=
ssxx
sxx
sxxSujeito
ssxxzMaximizar
4
52
221
121
=++
=++
sxx
sxx






=
=
=
==
⇒=−=
0
4
5
0
224
2
1
21
z
s
s
xx
D
042 21 =−− xxz
1x 2x 1s 2s
1s 1 2 1 0 5
2s 1 1 0 1 4
z –2 –4 0 0 0
1x 2x 1s 2s
2x
2
1 1
2
1 0
2
5
2s
2
1 0
2
1− 1
2
3
z 0 0 2 0 10
Este último quadro mostra que a solução optimizada é encontrada logo depois de 
efectuar-se esta primeira iteração, sendo ( 0*1 =x , 2
5*
2 =x e 10* =z ).
Veja-se agora como é que sabe que existe uma solução alternativa a partir do 
quadro de Simplex. Verificando-se os coeficientes das variáveis não básicas na linha da 
função objectivo (z) na iteração 1,verifica-se que o coeficiente da variável x1 é nulo (0), 
sendo esta uma variável não básica. Isto indica que a variável x1 pode entrar na solução 
básica sem alterar o valor da função objectivo z, mas causando alterações dos valores 
das variáveis. Assim, a segunda iteração faz com que, entrando o x1 na solução básica, 
vai forçar a saída do s2. Daqui resulta uma nova solução, que é a seguinte: ( 3*1 =x , 1
*
2 =x 
e 10* =z ).
1x 2x 1s 2s
2x 0 1 1 –1 1
1x 1 0 –1 2 3
z 0 0 2 0 10
Neste caso, diz-se que o problema tem pelo menos duas soluções óptimas 
alternativas, conforme acima se apresentam.
Na prática, o conhecimento de soluções alternativas é muito útil, porque dá ao 
gestor a possibilidade de escolher a solução que melhor responde a situação em estudo 
sem sofrer qualquer alteração da função objectivo.
Exemplo 2 – Considere o seguinte problema:
0,
1553
1836
2:
2:
21
21
21
21
21
≥
≤+
≤+
≤−
+=
xx
xx
xx
xxSujeito
xxzMaximizar
Resolvendo este problema tem-se:
0,,,,
1553
1836
2:
)(02:
32121
321
221
121
32121
≥
=++
=++
=+−
++++=
sssxx
sxx
sxx
sxxSujeito
sssxxzMaximizar
1553
1836
2
321
221
121
=++
=++
=+−
sxx
sxx
sxx








=
=
=
=
==
⇒=−=
0
15
18
2
0
235
3
2
1
21
z
s
s
s
xx
D
02 21 =−−= xxz
1x 2x 1s 2s 3s
1s 1 –1 1 0 0 2
2s 6 3 0 1 0 18
3s 3 5 0 0 1 15
z –2 –1 0 0 0 0
1x 2x 1s 2s 3s
1x 1 –1 1 0 0 2
2s 0 9 –6 1 0 6
3s 0 8 –3 0 1 9
z 0 –3 2 0 0 4
1x 2x 1s 2s 3s
1x 1 0
3
1
9
1 0
3
8
2x 0 1
3
2−
9
1 0
3
2
3s 0 0
3
7
9
8− 1
311
z 0 0 0
3
1 0 6
Este último quadro mostra que a solução optimizada é encontrada logo depois de 
efectuar-se esta segunda iteração, sendo ( 3
8*
1 =x , 32
*
2 =x e 6* =z ). Entretanto, verificando-
se os coeficientes das variáveis não básicas na linha da função objectivo (z),verifica-se 
que o coeficiente da variável s1 tornou-se novamente nulo (0), sendo esta uma variável 
não básica. Similarmente ao caso anterior, isto indica que a variável s1 pode entrar na 
solução básica sem alterar o valor da função objectivo z, mas causando alterações dos 
valores das variáveis. Assim, efectuando-se a terceira iteração obtém-se uma nova 
solução, que é a seguinte ( 7
15*
1 =x , 7
12*
2 =x e 6* =z ). conforme se pode observar no quadro 
abaixo.
1x 2x 1s 2s 3s
1x 1 0 0
21
2
7
1−
7
15
2x 0 1 1
7
1−
7
2
7
12
3s 0 0 0
21
8
7
3
7
11
z 0 0 0
3
1 0 6
3.2.4.3. Soluções não limitadas
Em alguns modelos de Programação Linear os valores das variáveis podem ser 
aumentados indefinidamente sem se violar nenhuma das restrições, o que significa que o 
espaço das soluções não é limitado, pelo menos numa das direcções. Daí resulta que o 
valor da função objectivo pode aumentar (caso de maximização) ou diminuir (caso da 
minimização) indefinidamente. Neste caso, pode-se dizer que, tanto o espaço das 
soluções, como o valor optimizado da função objectivo são não limitados.
Na prática, a não limitação num modelo indica que esse modelo não foi bem 
estabelecido. Pois se, por exemplo, um modelo gera uma solução que dá um lucro 
infinito, ele é completamente desprovido de senso. E, em casos reais, os erros mais 
usuais que originam a não limitação são os seguintes:
• a não consideração de uma ou mais restrições não redundantes; e
• a estimação inadequada dos parâmetros, ou seja, dos coeficientes das restrições.
Exemplo 1 – Considere seguinte problema:
0,
5
2:
2:
21
1
21
21
≥
≤
≤−
+=
xx
x
xxSujeito
xxzMaximizar
Resolvendo este problema tem-se:
0,,,
5
2:
)(02:
2121
21
121
2121
≥
=+
=+−
+++=
ssxx
sx
sxxSujeito
ssxxzMaximizar
5
2
21
121
=+
=+−
sx
sxx






=
=
=
==
⇒=−=
0
5
2
0
224
2
1
21
z
s
s
xx
D
02 21 =−− xxz
1x 2x 1s 2s
1s 1 –1 1 0 2
2s 1 0 0 1 5
z –1 –2 0 0 0
Neste quadro de partida pode ver que, tanto o x1, como o x2 podem entrar para a 
solução básica. Contudo, uma vez que o x2 tem maior coeficiente negativo na função 
objectivo é ele que deve ser seleccionado como variável de entrada. Entretanto, todos os 
coeficientes das restrições relativas a x2 não são positivas. Isto indica que o x2 pode 
crescer indefinidamente sem comprometer nenhuma das soluções.
Dado que cada aumento de x2 aumenta o z, um aumento infinito de x2 causa 
também um aumento infinito de z. Assim, conclui-se o problema tem solução não 
limitada.
Este facto pode ser verificado na figura abaixo onde se observa que o espaço de 
soluções é ilimitado na direcção de x2.
Figura 3.9. – Solução não limitada
Exemplo 2 – Considere o seguinte problema:
0,
623
4
3:
3:
21
21
1
21
21
≥
≥+
≤
≤−
+=
xx
xx
x
xxSujeito
xxzMaximizar
Resolvendo este problema tem-se:
1 2 3 5 6 7 8-1-2-3-4
-1
-2
1
6
5
4
3
2
0 x1
x2
4 9
7
z = x
1 + 2x
2
x1 ≤ 5
x 1 
- x
2
 ≤ 
2Espaço de
soluções 
não limitado
0,,,,,
623
4
3:
)(03:
132121
1321
21
121
132121
≥
=+−+
=+
=+−
+++++=
Rsssxx
Rsxx
sx
sxxSujeito
MRsssxxzMaximizar
623
4
3
1321
21
121
=+−+
=+
=+−
Rsxx
sx
sxx








=
=
=
=
===
⇒=−=
0
6
4
3
0
336
1
2
1
321
z
R
s
s
sxx
D
03 121 =−−−= MRxxz
1x 2x 1s 2s 3s 1R
1s 1 –1 1 0 0 0 3
2s 1 0 0 1 0 0 4
1R 3 2 0 0 –1 1 6
z –3–3M –1–2M 0 0 M 0 –6M
1x 2x 1s 2s 3s 1R
1s 0
3
5− 1 0
3
1
3
1− 1
2s 0
3
2− 0 1
3
1
3
1− 2
1x 1
3
2 0 0
3
1−
3
1 2
z 0 1 0 0 –1 1+M 6
1x 2x 1s 2s 3s
3s 0 –5 3 0 1 3
2s 0 1 –1 1 0 1
1x 1 –1 1 0 0 3
z 0 –4 3 0 0 9
1x 2x 1s 2s 3s
3s 0 0 –2 5 1 8
2x 0 1 –1 1 0 1
1x 1 0 0 1 0 4
z 0 0 –1 4 0 13
Este último quadro mostra que a solução optimizada ainda não foi alcançada, pois 
a variável s1 pode entrar na solução básica. Entretanto, verifica-se que todos os 
coeficientes das restrições relativas a s2 não positivos, isto é, são negativos e nulos, 
indicando que existe pelo menos uma variável que pode ser aumentada indefinidamente. 
Deste modo conclui-se que o problema tem solução não limitada. 
Em regra geral, para se identificar a existência de uma situação de não 
limitação, verifica-se se em qualquer iteração os coeficientes de uma das variáveis não 
básicas das restrições são não positivos. Se isso suceder, tem-se um espaço de 
soluções não básicas. Se, além disso, o coeficiente da tal variável na função objectivo 
for negativo, no caso de maximização, e positivo, no caso de maximização, então o 
valor da função objectivo é também não limitado.
3.2.4.4. Soluções inexistentes ou inviáveis
Se todas as restrições não poderem ser satisfeitas simultaneamente, diz-se que o 
modelo não tem uma solução viável. Esta situação nunca pode acontecer se todas as 
restrições forem do tipo menor ou igual (≤) assumindo constantes não negativas no 
segundo membro, uma vez que as variáveis de folga fornecem sempre uma solução 
admissível. No entanto, quando se empregam os outros tipos de restrições, torna-se 
imperioso que se usem as variáveis fictícias que, por definição, não garantem uma 
solução viável para o modelo original.
Embora se usem medidas para forçar as variáveis fictícias a tomar o valor zero na 
solução óptima, através da utilização das penalizações, este situação só pode ocorrer se 
o modelo tiver um espaço viável de soluções. Se não tiver, pelo menos uma variável 
fictícia será positiva na iteração óptima. Isto indica que o problema não tem solução ou 
tem solução inviável.
Sob o ponto de vista prático, um espaço de soluções não admissível indica a 
possibilidade de o modelo não estar correctamente formulado, uma vez que as restrições 
não são mutuamente compatíveis.
Exemplo 1 – Considere seguinte problema:
0,
1243
22:
23:
21
21
21
21
≥
≥+
≤+
+=
xx
xx
xxSujeito
xxzMaximizar
Resolvendo este problema tem-se:
0,,,,
1243
22:
)(023:
12121
1221
121
12121
≥
=+++
=++
++++=
Rssxx
Rsxx
sxxSujeito
MRssxxzMaximizar
1243
22
1221
121
=+++
=++
Rsxx
sxx






=
=
=
===
⇒=−=
0
12
2
0
325
1
1
221
z
R
s
sxx
D
023 121 =−−− MRxxz
1x 2x 1s 2s 1R
1s 2 1 1 0 0 2
1R 3 4 0 –1 1 12
z –3–3M –2–4M 0 0 M –12M
1x 2x 1s 2s 1R
2x 2 1 1 0 0 2
1R –5 0 –4 –1 1 4
z 1+5M 0 2+4M M 0 4–4M
Esta primeira iteração do Método de Simplex mostra que a variável fictícia R1 é 
positiva (R1=4) na solução óptima. Isto indica que o espaço das soluções é inviável, isto 
é, o problema não tem soluções. E a solução obtida é chamada Solução Peseudo-óptima. 
E a figura abaixo, mostra o espaço de soluções deste problema.
1 2 3 5 6 7 8-1-2-3-4
-1
-2
1
6
5
4
3
2
0 x1
x2
4 9
7
3x
1 +4x
2 ≥12
2x
1 +x
2 ≤2
•
Solução
pseudo-óptima
Figura 3.10. – Espaço de soluções inviáveis
Referências seleccionadas
Hartley, R. (1985), “Linear and Non-linear Programming”. An Introduction to Linear 
Methods in Mathematical Programming. Ellis Horwood Limited, West Sussex.
Taha, H. (1997), “Operations Reseach”. An Introduction. 6th Edition. Prentice-Hall, Inc. 
Upper Saddle River.
Andrade, Eduardo L. (2000). Introdução à Pesquisa Operacional”, 2ª Edição. Livro Técnicos 
e Científicos Editora, Rio de Janeiro.
Exercícios
1. Resolver por Método de M Grande os seguintes problemas de Programação Linear.
0,
82
1
622:
3:)
21
21
21
21
21
≥
≤+
≤+−
≥+
+−=
xx
xx
xx
xxaSujeito
xxzMaximizara
0,
6
1232
1:
23:)
21
2
21
21
21
≥
≤
≥+
≤−
+−=
xx
x
xx
xxaSujeito
xxzMinimizarb
0,
1523
234
3:
6:)
21
21
21
21
21
≥
≥+
≤+
=−
+=
xx
xx
xx
xxaSujeitoxxzMaximizarc
0,
8
1
1232:
64:)
21
2
21
21
21
≥
≤
≤−
≥+
+−=
xx
x
xx
xxaSujeito
xxzMinimizard
0,
52
1043
2674:
53:)
21
21
21
21
21
≥
=+
≥−
≤+
+=
xx
xx
xx
xxaSujeito
xxzMaximizare
0,
232
10
723:
3:)
21
21
21
21
21
≥
=+−
≤+
≥−
+=
xx
xx
xx
xxaSujeito
xxzMinimizarf
0,
52
1043
2674:
53:)
21
21
21
21
21
≥
=+
≥−
≤+
+=
xx
xx
xx
xxaSujeito
xxzMinimizarg
0,
52
1243
2474:
53:)
21
21
21
21
21
≥
≥+
≤−
≤+
+=
xx
xx
xx
xxaSujeito
xxzMaximizarh
0,
1523
234
3:
122:)
21
21
21
21
21
≥
≥+
≤+
=−
+−=
xx
xx
xx
xxaSujeito
xxzMinimizari
0,
962
3575
62:
32:)
21
21
21
21
21
≥
≥+
≤+
≤+−
+=
xx
xx
xx
xxaSujeito
xxzMaximizarj
0,
2
1243
82:
32:)
21
21
21
21
21
≥
≤−
≥+
≤+
+−=
xx
xx
xx
xxaSujeito
xxzMinimizark
0,
1532
2324
3:
6:)
21
21
21
21
21
≥
≥+
≤+
=+−
−=
xx
xx
xx
xxaSujeito
xxzMaximizarl
0,
3
52
4:
32:)
21
21
21
21
21
≥
≤+
≥+
≤+−
+=
xx
xx
xx
xxaSujeito
xxzMaximizarm
0,
2133
155
2052:
510:)
21
21
21
21
21
≥
≥+
≥+
≥+
+=
xx
xx
xx
xxaSujeito
xxzMaximizarn
2. Resolver por Método de M Grande os seguintes problemas de Programação Linear.
0,,
22
524
13253:
3:)
321
32
321
321
321
≥
=+−
≥+−
≤−+
+−=
xxx
xx
xxx
xxxaSujeito
xxxzMinimizara
0,,
12
324
112:
3:)
321
31
321
321
321
≥
=+−
≥++−
≤+−
++−=
xxx
xx
xxx
xxxaSujeito
xxxzMinimizarb
0,,
3463
1332
9:
2:)
321
321
321
321
321
≥
=−+−
=+−
≤++
++−=
xxx
xxx
xxx
xxxaSujeito
xxxzMinimizarc
0,,
423
62
2132:
2:)
321
321
21
321
321
≥
≥+−
=−
≤++
+−=
xxx
xxx
xx
xxxaSujeito
xxxzMaximizard
0,,
522
10443
25774:
653:)
321
321
321
321
321
≥
≥−+
≥+−
≤−+
−+=
xxx
xxx
xxx
xxxaSujeito
xxxzMaximizare
0,,,
8232
2
62:
2:)
4321
432
31
4321
4321
≥
≤+−
≤+−
≥+−−
+++=
xxxx
xxx
xx
xxxxaSujeito
xxxxzMinimizarf
0,,
232
102
523:
23:)
321
321
321
321
321
≥
≥−+−
≥++
≥+−
++=
xxx
xxx
xxx
xxxaSujeito
xxxzMinimizarg
0,,,
823
632
22:
2:)
4321
4321
4321
4321
4321
≥
≤+++−
=+−+
=−+−
++−−=
xxxx
xxxx
xxxx
xxxxaSujeito
xxxxzMinimizarh
0,,
2448
8426
2132:
242:)
321
31
321
321
321
≥
=+−
≥++−
≤++
++−=
xxx
xx
xxx
xxxaSujeito
xxxzMaxiimizari
0,,
725
23
15425:
3:)
321
321
32
321
321
≥
=++
≤−
≥++
−+=
xxx
xxx
xx
xxxaSujeito
xxxzMinimizarj
0,,
823
62
2132:
462:)
321
321
21
321
321
≥
≥+−
=−
≤++
+−=
xxx
xxx
xx
xxxaSujeito
xxxzMaximizark
3. Resolver por Método de M Grande os seguintes problemas de Programação Linear.
livrexxx
xxx
xx
xxxaSujeito
xxxzMaximizara
231
321
21
321
321
;0,
423
62
932:
2:)
≥
≥+−
=−
≤++
+−=
0;0,
725
426
15425:
3:)
321
321
32
321
321
≤≥
=−+
≤+
≥−+
++=
xxx
xxx
xx
xxxaSujeito
xxxzMinimizarb
0,;
423
62
2132:
2:)
321
321
21
321
321
≥
≥+−
=−
≤++
+−=
xxlivrex
xxx
xx
xxxaSujeito
xxxzMaximizarc
0,;
1024
732
846:
242:)
321
21
321
321
321
≥
=+−
≤++
≥++−
−−=
xxlivrex
xx
xxx
xxxaSujeito
xxxzMinimizard
0;0,
322
323
1:
752:)
231
321
321
321
321
≤≥
≥+−
≥+−
≤++
+−=
xxx
xxx
xxx
xxxaSujeito
xxxzMaximizare
0,,
42
42
6:
2:)
321
321
21
321
321
≥
≤−+−
≤+
≤++
+−=
xxx
xxx
xx
xxxaSujeito
xxxzMaximizarf
0,
2
1243
82:
33:)
21
21
21
21
21
≥
≤−
≥+
≤+
+−=
xx
xx
xx
xxaSujeito
xxzMinimizarg
0,
5
2446
1:
2:)
21
2
21
21
21
≥
≤
≥+
≤+−
+=
xx
x
xx
xxaSujeito
xxzMaximizarh
0,
152
13
54:
:)
21
21
21
21
21
≥
≥−
≤−
≥−
+−=
xx
xx
xx
xxaSujeito
xxzMaximizari
0,
2325
2953
1523:
726:)
21
21
21
21
21
≥
≥+
≥+
≥+
+=
xx
xx
xx
xxaSujeito
xxzMaximizarj
0,
4
22
33:
62:)
21
1
21
21
21
≥
≤
≥−
≥+
+=
xx
x
xx
xxaSujeito
xxzMinimizark
0,
22
22
42:
42:)
21
21
21
21
21
≥
≥+
≤+−
≤−
+−=
xx
xx
xx
xxaSujeito
xxzMaximizarl
0,
2
662
2438:
52:)
21
21
21
21
21
≥
≤+−
≥+−
≥+
+=
xx
xx
xx
xxaSujeito
xxzMaximizarm
0,
152
13
54:
:)
21
21
21
21
21
≥
≥−
≤−
≥−
+−=
xx
xx
xx
xxaSujeito
xxzMaximizarn
0,
1243
22:
23:)
21
21
21
21
≥
≥+
≤+
+=
xx
xx
xxaSujeito
xxzMaximizaro
0,
6034
10024
12043:
1020:)
21
21
21
21
21
≥
≤−
≥+
≤+
+=
xx
xx
xx
xxaSujeito
xxzMaximizarp
0,
2
662
2438:
52:)
21
21
21
21
21
≥
≤+−
≥+−
≥+
+=
xx
xx
xx
xxaSujeito
xxzMaximizarm
4. Uma pequena fábrica do ramo alimentar é constituída por três secções e pode 
produzir três produtos enlatados P1, P2, P3 cujos lúcros líguidos por unidade produzida 
são de 3, 2 e 4 u.m., respectivamente.
As secções I, II e III, têm capacidades de processamento limitadas em 480, 580 e 
720 horas, por mês, respectivamente. E as horas necessárias para o processamento 
de uma caixa do produto P1, P2 ou P3, são dadas na tabela abaixo.
SECÇÕES PRODUTOS
P1 P2 P3
I 2 0 4
II 2 2 2
III 2 4 2
Sabendo que os produtos os três produtos são vendidos em caixas de 12 latas 
estabeleça o óptimo programa de produção mensal para a fábrica.
5. Uma pequema empresa de distribuição de produtos alimentares dispõe de 1,2 
toneladas de arroz no primeiro dos seus dois armazéns e de mais uma tonelada no 
segundo armazém. E a empresa recebeu pedido provenientes de dois dos seus 
principais clientes nas quantidades de 18 e 14 sacos, de 50 quilos cada, 
respectivamente para os clientes 1 e 2.
Sabe-se que a empresa oferece transporte gratuído à todos os clientes que 
compram dez, ou mais, sacos. E para este caso, os custos unitários de transporte 
estimados, por saco de arroz, são os seguinte:
• do Armazém I para a loja do Cliente 1, 14 contos;
• do Armazém I para a loja do Cliente 2, 11 contos;
• do Armazém II para a loja do Cliente 1, 14 contos; e
• do Armazém II para a loja do Cliente 2, 13 contos;
Considere que o arroz existente em ambos os armazéns da empresa está em soacos 
de 50 quilos e determine o óptimo plano de distribuição do arroz para os dois 
clientes.
6. Uma pequena fábrica produz 3 produtos, A, B e C, que são vendidos a 160, 300 e 500 
unidades monetárias (UM), respectivamente. E devida a procura, as exigências de 
produção semanal são pelo menos 25 unidades de A, 15 de B e 10 de C.
Cada tipo de produto requer um certo tempo para fabricação das partes 
componentes, para a montagem e para a embalagem. Especificamente, uma 
unidades de A requer 3 homem-horas para a fabricação, 4 homem-horas para a 
montagem e 1 homem-hora para a embalagem. Os números correspondentes para 
uma unidade de B são 3, 5 e 5 homem-horas, e para uma unidade de C são 5, 6 e 3 
homem-horas. E a fábrica trabalha num único turno de 8 horas, por dia, durante 
5dias por semana.
Sabendo que a fábrica emprega 8 operários na Secção de Fabricação, 8 na Secção 
de Montagem e 4 na Secção de Embalagem, determine a óptima misturs de 
produção semanal para a fábrica.
	3.2.3. Método de M Grande
	3.2.3.2. Problemas Resolvidos
	3.2.4. Casos especiais no Método de Simplex
	3.2.4.1. Soluções degeneradas.
	3.2.4.2. Soluções alternativas.
	3.2.4.3. Soluções não limitadas
	3.2.4.4. Soluções inexistentes ou inviáveis