Apostila 3 - Pesquisa Operacional

Prévia do material em texto

Capítulo 3 Algoritmo Simplex 
Pesquisa Operacional I Jhoab Negreiros 
1
 
 
 
 
 
 
 
 
 
 
CAPÍTULO 3 
Algoritmo Simplex 
 
 
 
3.1 Introdução 
 
O algoritmo Simplex é a ferramenta básica da programação linear. O objetivo do algoritmo é 
transformar uma matriz dada em outra equivalente que contenha certo “desenho” ou “padrão”. 
Este capítulo faz um esboço do Simplex, destacando seu parentesco com o algoritmo de 
Gauss-Jordan discutido no capítulo três. 
 
3.2 Conversão de desigualdade em uma equação 
 
Em restrições ( )≤ , o lado direito pode ser considerado como a representação do limite 
imposto à disponibilidade de um recurso, caso em que o lado esquerdo representaria a utilização 
desse recurso limitado pelas atividades (variáveis) do modelo. Assim, a diferença entre direito e o 
lado esquerdo da restrição ( )≤ resultaria na quantidade do recurso não utilizada ou folga. 
Para converter uma desigualdade ( )≤ em uma equação, uma variável de folga não 
negativa é adicionada ao primeiro membro da restrição. 
 
Exemplo 1. Dada a seguinte desigualdade: 3 2 12x y+ ≤ . 
Para transformar em uma equação adicionamos a variável de folga 1F e logo temos: 
1 13 2 12, 0x y F com F+ + = ≥ 
Capítulo 3 Algoritmo Simplex 
Pesquisa Operacional I Jhoab Negreiros 
2
 De forma semelhante, uma restrição ( )≥ estabelece um limite inferior para as atividades do 
modelo de programação linear, de modo que a quantidade pela qual o lado esquerdo excede o 
limite mínimo representa uma sobra. Consegue-se a conversão de ( )≥ em uma igualdade com a 
subtração de uma variável de sobra não negativa do lado esquerdo da desigualdade. 
 
Exemplo 2. Dada a seguinte desigualdade: 100x y+ ≥ . 
Para transformar em uma equação subtraímos a variável de folga 2F e logo temos: 
2 2100, 0x y F com F+ − = ≥ 
 
 A última possibilidade restante é que o lado direito da equação resultante seja negativo. A 
condição sempre pode ser satisfeita multiplicando-se ambos os lados da equação resultante por 
( )1− . 
 
Exemplo 3. Dada a seguinte desigualdade: 2 20x y− + ≤ − . 
Para transformar em uma equação adicionamos a variável de folga 3F e logo temos: 
3 32 20, 0x y F com F− + + = − ≥ 
Agora, multiplicando ambos os lados por ( )1− , teremos um lado direito não negativo, como 
desejado, isto é: 
32 20x y F− − = 
 
3.3 Transição da Solução Gráfica para a Solução Algébrica 
 
As idéias transmitidas pela solução gráfica do problema de programação linear lançam as 
bases para o desenvolvimento do método algébrico simplex. No método gráfico, a região de 
soluções é delineada pelos meios-espaços, que representam as restrições, e, no método simplex, a 
região de soluções é representada por m equações lineares simultâneas e n variáveis não 
negativas. A figura a seguir traça um paralelo entre os dois métodos. 
 
 
Capítulo 3 Algoritmo Simplex 
Pesquisa Operacional I Jhoab Negreiros 
3
Método Gráfico Método Algébrico 
Represente todas as restrições em gráfico, 
entre elas as restrições de não-negatividade. 
Represente a região de soluções por m 
equações em n variáveis e restrinjam todas as 
variáveis a valores não negativos, m n< . 
Identifique os pontos extremos viáveis da região 
de soluções. 
Determine as soluções básicas viáveis das 
equações. 
Candidatos à solução ótima são dados por um 
número finito de pontos extremos. 
Candidatas à solução ótima são dadas por um 
número finito de soluções básicas viáveis. 
Use a função objetivo para determinar o ponto 
extremo ótimo entre todos os candidatos. 
Use a função objetivo para determinar a solução 
básica viável ótima entre todos os candidatos. 
 
 Podemos verificar visualmente pelo gráfico por que a região de soluções tem um número 
infinito de pontos de solução, mas como podemos tirar a mesma conclusão da representação 
algébrica de soluções? A resposta é que na representação algébrica o número de equações m é 
sempre menor do que ou igual ao número de variáveis n . Se m n= , e as equações forem 
consistentes, o sistema tem somente uma solução; mas se m n< (o que representa a maioria dos 
problemas de PL), então o sistema de equações, novamente, se consistente, dará como resultado 
um número infinito de soluções. 
 
Exemplo 4. A equação 2x = tem ( )1m n= = e a solução é obviamente única. { }2S = , mas 
para a equação 1x y+ = , temos ( )1m = e ( )2n = , que resulta em um número infinito de 
soluções: ( ){ }1 ,S y y= − para todo � ∈ ℝ. 
 
3.4 Determinação Algébrica dos Pontos Extremos 
 
Em um conjunto de m n× equações ( )m n< , se igualarmos ( )n m− variáveis a zero, e 
depois resolvermos as m equações para as m variáveis restantes, a solução resultante, se for 
única, é denominada solução básica e deve corresponder a um ponto extremo (viável ou inviável) 
da região de soluções. Isso significa que o número máximo de pontos extremos é: 
,
!
!( )!n m
nC
m n m
=
−
 
Capítulo 3 Algoritmo Simplex 
Pesquisa Operacional I Jhoab Negreiros 
4
Exemplo 5. Considere o seguinte problema de PL com duas variáveis: 
( ), 2 3
2 4
2 5
, 0
Maximizar f x y x y
Restrições x y
x y
x y
= +
+ ≤
+ ≤
≥
 
 
Em linguagem algébrica, a região de soluções do problema de programação PL é representado por: 
1
2
1 1
2 4
2 5
, , , 0
x y F
x y F
x y F F
+ + =
+ + =
≥
 
 
 
 
 O sistema tem 2m = equações e 4n = variáveis. Assim, de acordo com a regra dada, os 
pontos extremos podem ser determinados algebricamente igualando 4 2 2n m− = − = variáveis a 
zero e depois, resolvendo para as 2m = variáveis restantes. 
Se fizermos 0x = e 0y = , as equações dão a solução (básica) única: 1 24, 5F F= =
.(Esta solução corresponde ao ponto A.) 
 
Um outro ponto pode ser determinado, fazendo 1 0F = e 2 0F = . Então resolvendo as 
duas equações: 
Capítulo 3 Algoritmo Simplex 
Pesquisa Operacional I Jhoab Negreiros 
5
2 4
2 5
x y
x y
+ =

+ =
, 
o que dá como resultado a solução básica 1x = e 2y = , que é o ponto C na figura. 
 
 É provável que você esteja imaginando como podemos decidir quais n m− variáveis 
devem ser igualadas a zero para chegar a um ponto extremo específico. Sem o auxílio da solução 
gráfica, não podemos dizer quais n m− variáveiszero estão associadas com quais pontos 
extremos. Mas isso não nos impede de enumerar todos os pontos extremos da região de soluções. 
Apenas considere todas as combinações nas quais n m− variáveis sejam igualadas a zero e 
resolva as equações resultantes. Isso feito, a solução ótima é a solução básica viável (pontos 
extremos) que resultar no melhor valor para a função objetivo. 
 
Neste exemplo temos: 4,2
4 3 6
2!
C ×= = pontos extremos. 
 
 Examinando a figura podemos localizar os quatro pontos A, B, C, D, E e F, todos são 
soluções para o problema, mas os dois últimos são não viáveis, porque não satisfazem todas as 
restrições. 
 Para resumir a transição da solução gráfica para a solução algébrica, as m n− variáveis 
zero são conhecidas como variáveis não básicas. As restantes m variáveis são denominadas 
variáveis básicas e sua solução é denominada solução básica. 
Variáveis 
não básicas 
Variáveis 
básicas 
Solução 
básica 
Pontos 
extremos 
Viáveis ou 
não viáveis 
Valor da 
f.o. 
(x, y) (F1, F2) (4, 5) A Sim 0 
(x, F1) (y, F2) (4, –3) F Não -- 
(x, F2) (y, F1) (5/2, 3/2) B Sim 7,5 
(y, F1) (x, F2) (2, 3) D Sim 4 
(y, F1) (x, F1) (5, –6) E Não -- 
(F1, F2) (x, y) (1, 2) C Sim 8 (ótimo) 
 
 
3.5 Natureza Iterativa do Método Simplex 
 
Em vez de enumerar todas as soluções básicas (pontos extremos) do problema de PL 
(como fizemos na tabela acima), o método simplex investiga somente algumas dessas soluções. 
Capítulo 3 Algoritmo Simplex 
Pesquisa Operacional I Jhoab Negreiros 
6
 Normalmente o método simplex começa na origem, onde 0x y= = . Nesse ponto de 
partida, o valor da função objetivo é zero, e a pergunta lógica é se um aumento em x e/ou y não 
básicas acima de seus valores zero atuais pode melhorar o valor da f.o., basta investigar o valor da 
mesma. 
Maximizar: ( , ) 2 3f x y x y= + . 
 
 A função mostra que um aumento em x ou y (ou em ambas) acima de seus valores zero 
atuais melhorará o seu valor. O método simplex exige o aumento de uma variável por vez, sendo 
que a variável selecionada será aquela que tiver a maior taxa de melhoria para a f.o. (com isso 
chegamos ao ponto B). 
 Portanto, no ponto B o método simplex aumentará o valor de x para alcançar o ponto 
extremo melhorado C, que é a solução ótima. Assim, o caminho do método simplex é definido como 
A B C→ → . Cada ponto extremo ao longo do caminho é associado a uma iteração. É importante 
observar que o método simplex percorre as bordas da região de soluções, o que significa que o 
método não pode atravessar a região de soluções e ir de A para C diretamente. 
 
3.6 Detalhes de Cálculo do Algoritmo Simplex 
 
Esta seção apresenta os detalhes de cálculo de uma iteração do método simplex, incluindo 
as regras para determinar as variáveis que entram na base e que saem da base, bem como as 
regras para interromper os cálculos quando a solução ótima tiver sido alcançada. A explicação se 
dará por meio de um exemplo numérico. 
 
Exemplo 6. Usaremos o problema de PL a seguir: 
: 5 4
: 6 4 24
2 6
1
2
, 0
Maximizar z x y
Restrições x y
x y
x y
y
x y
= +
+ ≤
+ ≤
− + ≤
≤
≥
 
 
O problema é expresso na forma de equações como: 
Capítulo 3 Algoritmo Simplex 
Pesquisa Operacional I Jhoab Negreiros 
7
1 2 3 4
1
2
3
4
1 2 3 4
: 5 4 0 0 0 0
: 6 4 24
2 6
1
2
, , , , , 0
Maximizar z x y F F F F
Restrições x y F
x y F
x y F
y F
x y F F F F
= + + + + +
+ + =
+ + =
− + + =
+ =
≥
 
As variáveis 1 2 3, ,F F F e 4F são as folgas associadas às respectivas restrições. 
 
Em seguida, escrevemos a função objetivo como: 5 4 0z x y− − = . 
 
Dessa maneira, a tabela simplex inicial pode ser representada da seguinte maneira: 
 
Base Z X Y F1 F2 F3 F4 Solução 
Z 1 -5 -4 0 0 0 0 0 Linha Z 
F1 0 6 4 1 0 0 0 24 Linha F1 
F2 0 1 2 0 1 0 0 6 Linha F2 
F3 0 -1 1 0 0 1 0 1 Linha F3 
F4 0 0 1 0 0 0 1 2 Linha F4 
 
O arranjo da tabela específica e o conjunto de variáveis básicas e não básicas, apresenta a 
solução associada com a iteração inicial. 
Variáveis não básicas (zero) em A: ( , )x y . 
 Variáveis básicas: ( 1, 2, 3, 4)F F F F . 
 
A solução inicial é ótima? A função objetivo: 5 4z x y= + mostra que a solução pode ser 
melhorada, aumentando x ou y . Coeficiente da f.o. mais positivo é selecionado como a variável 
ao entrar na base. Essa regra é denominada condição de otimalidade. 
A determinação da variável que sai com base na tabela simplex exige o cálculo das razões 
não negativas entre o lado direito das equações (coluna solução) e o coeficiente de restrição 
correspondente da variável que entra na base x . 
 
 Entrando Razão 
Base X Solução (ou intercepto) 
F1 6 24 X = 24/6 = 4 (Mínimo) 
F2 1 6 X = 6/1 = 6 
F3 -1 1 X = 1/-1 = -1 (Ignorar) 
F4 0 2 X = 2/0 (Ignorar) 
 Conclusão: X entra, F1 sai. 
 
Capítulo 3 Algoritmo Simplex 
Pesquisa Operacional I Jhoab Negreiros 
8
Observem que os valores das razões calculadas são as interseções das restrições com o 
eixo x da variável que entra na base. A regra associada com os cálculos das razões é denominada 
condição de viabilidade. 
 
 
O novo ponto de solução B é determinado pela troca entre a variável que entra na base X e 
a variável que sai da base F1 na tabela simplex para produzir os seguintes conjuntos de variáveis 
não básicas e básicas. 
Variáveis não básicas (zero) em B: ( 1, )F y . 
 Variáveis básicas: ( , 2, 3, 4)x F F F . 
 
O processo de troca é baseado nas operações de Gauss-Jordan, que identifica a coluna da 
variável que entra na base como a coluna do pivô, e a linha da variável que sai como a linha do 
pivô. 
 
Os cálculos serão aplicados a primeira tabela da seguinte forma: 
� Substituir F1 na coluna base por X; 
� Nova linha X = Linha F1 atual ÷ 6; 
� Nova linha Z = Linha Z atual – ( – 5 ) × Nova linha X; 
� Nova linha F2 = Linha F2 atual – ( 1 ) × Nova linha X; 
� Nova linha F3 = Linha F3 atual – ( – 1 ) × Nova linha X; 
Capítulo 3 Algoritmo Simplex 
Pesquisa Operacional I Jhoab Negreiros 
9
� Nova linha F4 = Linha F4 atual – ( 0 ) × Nova linha X. 
Base Z X Y F1 F2 F3 F4 Solução 
Z 1 0 -2/3 5/6 0 0 0 20 Linha Z 
X 0 1 2/3 1/6 0 0 0 4 Linha F1 
F2 0 0 4/3 -1/6 1 0 0 2 Linha F2 
F3 0 0 5/3 1/6 0 1 0 5 Linha F3 
F4 0 0 1 0 0 0 1 2 Linha F4 
 
 
Observe que a nova tabela tem as mesmas propriedades da tabela inicial. O novo valor da 
função objetivo é igual a 20. 
 
Pela condição de otimalidade mostra que Y é a variávelque deve entrar na base. A 
condição de viabilidade produz o seguinte: 
 
 Entrando Razão 
Base Y Solução (ou intercepto) 
X 2/3 4 Y = 4:2/3 = 6 
F2 4/3 2 Y = 2:4/3 = 1,5 (Mínimo) 
F3 5/3 5 Y = 5:5/3 = 3 
F4 1 2 Y = 2:1 = 2 
 Conclusão: Y entra, F2 sai. 
 
Substituindo F2 na coluna base por Y que entra, as seguintes operações de filas por Gauss-
Jordan são aplicadas: 
� Substituir F2 na coluna base por Y; 
� Nova linha Y = Linha F2 atual ÷ 4/3; 
� Nova linha Z = Linha Z atual – ( – 2/3 ) × Nova linha Y; 
� Nova linha X = Linha X atual – ( 2/3 ) × Nova linha Y; 
� Nova linha F3 = Linha F3 atual – ( 5/3 ) × Nova linha Y; 
� Nova linha F4 = Linha F4 atual – ( 1 ) × Nova linha Y. 
 
Esses cálculos produzem a tabela a seguir. 
 
Base Z X Y F1 F2 F3 F4 Solução 
Z 1 0 0 3/4 1/2 0 0 21 Linha Z 
X 0 1 0 1/4 -1/2 0 0 3 Linha X 
Y 0 0 1 -1/8 3/4 0 0 3/2 Linha Y 
F3 0 0 0 3/8 -5/4 1 0 5/2 Linha F3 
F4 0 0 0 1/8 -3/4 0 1 1/2 Linha F4 
Capítulo 3 Algoritmo Simplex 
Pesquisa Operacional I Jhoab Negreiros 
10
 
Com base na condição de otimalidade, nenhum dos coeficientes da linha Z associados com 
as variáveis não básicas F1 e F2, é negativo. Assim, essa tabela simplex é ótima. 
 
A solução ótima pode ser lida na tabela simplex da seguinte maneira: 
 
Variável Valor Recomendação 
de decisão ótimo 
X 3 Produzir 3t diárias de tintas para exteriores. 
Y 1,5 Produzir 1,5t diárias de tintas para interiores. 
Z 21 Lucro diário é $ 21,00. 
 
A solução também fornece informações dos recursos. Um recurso é designado como 
escasso se as atividades (variáveis) do modelo o usarem totalmente. Caso contrário, o recurso é 
denominado abundante. Essa informação é obtida da tabela ótima pela verificação do valor da 
variável de folga associada à restrição que representa o recurso. Se a folga for zero, o recurso é 
totalmente utilizado e, por conseguinte, é classificado como escasso. Ao contrário, uma folga 
positiva indica que o recurso é abundante. 
 
Classificação das restrições do modelo: 
 
Recurso Valor da Folga Condição 
Matéria-prima, M1 F1 Escasso 
Matéria-prima, M2 F2 Escasso 
Limite de Mercado F3 Abundante 
Limite da demanda F4 Abundante 
 
3.7 Método das duas Fases 
 
Os problemas de PL nos quais todas as restrições são ( )≤ com lados direitos não 
negativos oferecem uma solução básica inicial viável conveniente na qual todas as variáveis são de 
folga. Isso não acontece com modelos que envolvem restrições ( )= e ( )≥ . 
 O procedimento para iniciar a resolução de problemas de PL com as restrições ( )= e ( )≥ 
é usar variáveis artificiais que desempenham o papel de folgas na primeira iteração e então, 
descartá-las legitimamente em iterações posteriores. 
 
Capítulo 3 Algoritmo Simplex 
Pesquisa Operacional I Jhoab Negreiros 
11
Usaremos o exemplo para desenvolver o método: 
Exemplo 7. Minimizar a função: 4 5Z x y= + , sujeito a restrições: 
3 3
4 3 6
2 4
, 0
x y
x y
x y
x y
+ =
+ ≥
+ ≤
≥
 
 
Fase I 
 
Usando F1 como uma sobra na segunda restrição e F2 como folga na terceira restrição. A 
terceira equação tem sua variável de folga, F2, mas a primeira e a segunda equação não têm, 
adicionamos as variáveis artificiais R1 e R2 nas duas primeiras equações, e a forma de equações 
do problema é dada como: 
 
: 1 2Minimizar r R R= + 
Sujeito a: 
 
3 1 3
4 3 1 2 6
2 2 4
, , 1, 2, 1, 2 0
x y R
x y F R
x y F
x y F F R R
+ + =
+ − + =
+ + =
≥
 
 
A tabela associada é dada: 
 
Base X Y F1 R1 R2 F2 Solução 
r 0 0 0 -1 -1 0 0 Linha r 
R1 3 1 0 1 0 0 3 Linha R1 
R2 4 3 -1 0 1 0 6 Linha R2 
F2 1 2 0 0 0 1 4 Linha F2 
 
Antes de continuar com os cálculos do método simplex, precisamos tornar a linha r 
consistente com o resto da tabela. Especificamente, na tabela, 1 0x y F= = = , o que resulta na 
solução básica 1 3R = , 2 6R = e 2 4F = , o que resulta na solução básica: 3 6 9r = + = (em vez 
de 0, como mostra a tabela acima). 
 
Para isso são substituídas na linha r , usando os seguintes cálculos: 
Capítulo 3 Algoritmo Simplex 
Pesquisa Operacional I Jhoab Negreiros 
12
 
 (1 1 1 2)Nova linha r linha velha r linha R linha R= + × + × . 
 
Base X Y F1 R1 R2 F2 Solução 
r 7 4 -1 0 0 0 9 Linha r 
R1 3 1 0 1 0 0 3 Linha R1 
R2 4 3 -1 0 1 0 6 Linha R2 
F2 1 2 0 0 0 1 4 Linha F2 
 
Entrando X e saindo da base R1. 
 
Base X Y F1 R1 R2 F2 Solução 
r 0 5/3 -1 -7/3 0 0 2 Linha r 
X 1 1/3 0 1/3 0 0 1 Linha X 
R2 0 5/3 -1 -4/3 1 0 2 Linha R2 
F2 0 5/3 0 -1/3 0 1 3 Linha F2 
 
Entrando Y e saindo da base R2. 
 
Base X Y F1 R1 R2 F2 Solução 
r 0 0 0 -1 -1 0 0 Linha r 
X 1 0 1/5 9/15 -1/5 0 3/5 Linha X 
Y 0 1 -3/5 -4/5 3/5 0 6/5 Linha Y 
F2 0 0 1 1 -1 1 1 Linha F2 
 
Como mínimo 0r = , a Fase I produz a solução básica viável 3
5
x = , 
6
5
y = e 2 1F = . 
Nesse ponto, as variáveis artificiais concluíram sua missão e podemos eliminar totalmente suas 
colunas da tabela e passar para a Fase II. 
 
Fase II 
 
Após eliminar as colunas artificiais, escrevemos o problema original como: 
: 4Minimizar Z x y= + 
 
Capítulo 3 Algoritmo Simplex 
Pesquisa Operacional I Jhoab Negreiros 
13
Sujeito a: 
1 31
5 5
3 61
5 5
1 2 1
, , 1, 2 0
x F
y F
F F
x y F F
+ =
− =
+ =
≥
 
Base X Y F1 F2 Solução 
Z -4 -1 0 0 0 Linha Z 
X 1 0 1/5 0 3/5 Linha X 
Y 0 1 -3/5 0 6/5 Linha Y 
F2 0 0 1 1 1 Linha F2 
 
Novamente, como as variáveis básicas x e y têm coeficientes não zero na linha Z, elas 
devem ser substituídas com a utilização dos seguintes cálculos: 
 
(4 1 )Nova linha Z linha velha Z linha x linha y= + × + × 
 
Portanto, a tabela inicial da Fase II é dada como: 
 
Base X Y F1 F2 Solução 
Z 0 0 1/5 0 18/5 Linha Z 
X 1 0 1/5 0 3/5 Linha X 
Y 0 1 -3/5 0 6/5 Linha Y 
F2 0 0 1 1 1 Linha F2 
 
Como estamos minimizando F1, devemos entrar na solução. 
 
Base X Y F1 F2 Solução 
Z 0 0 0 -1/5 17/5 Linha Z 
X 1 0 0 -1/5 2/5 Linha X 
Y 0 1 0 3/5 9/5 Linha Y 
F1 0 0 1 1 1 Linha F1 
 
Resumo do método das duas fases: 
 
Fase 1: Expresse o problema na forma de equações e adicione as variáveis artificiais necessárias 
às restrições para garantir uma solução básica inicial. Em seguida, ache uma solução básica com 
as equações resultantes que, independentemente do problema de PL ser de maximização ou 
minimização, sempre minimizará a soma das variáveis artificiais.Se o valor mínimo da soma for 
positivo, o problema de PL não tem nenhuma solução viável, o que encerra o processo (lembre-se 
de que uma variável artificial positiva significa que uma restrição original não foi satisfeita). 
Fase 2: Use a solução viável da Fase 1 como uma solução básica viável inicial para o problema 
original. 
Capítulo 3 Algoritmo Simplex 
Pesquisa Operacional I Jhoab Negreiros 
14
3.8 Atividades 
 
Exercício 1. Sabendo que a função objetivo de um problema de programação linear é dada por 
( , ) 4 5f x y x y= + , determine o valor máximo (a),(b) e (c) e mínimo (d) desta função sobre as 
restrições utilizando o método simplex. 
(a) 
0, 0
2 15
2 15
x y
x y
x y
≥ ≥

+ ≤
 + ≤
 
(b) 
0, 0
60, 50
2 120
x y
x y
x y
≥ ≥
 ≤ ≤
 + ≤
 
(c) 
0, 0
25
5
x y
x y
x y
≥ ≥

+ ≤
 + ≥
 
(d) 
0, 0
3 12
3 4 30
2 7 28
x y
x y
x y
x y
≥ ≥
 + ≥

+ ≥
 + ≥
 
 
Exercício 2. Uma fábrica produz dois artigos A e B, que devem passar por duas máquinas 
diferentes M1 e M2. M1 tem 12 horas de capacidade diária disponível e M2 tem 5 horas. Cada 
unidade de produto A requer 2 horas em ambas as máquinas. Cada unidade de produto B requer 3 
horas em M1 e 1 hora em M2. O lucro líquido de A é de R$ 60,00 por unidade e o de B, R$ 70,00 
por unidade. Determinar a quantidade a ser produzida de A e B a fim de se ter um lucro máximo. 
 
Exercício 3. Uma pequena fábrica de papel toalha manufatura três tipos de produtos A, B e C. A 
fábrica recebe o papel em grandes rolos. O papel é cortado, dobrado e empacotado. Dada a 
pequena escala da fábrica, o mercado absorverá qualquer produção a um preço constante. O lucro 
unitário de cada produto é respectivamente R$ 1,00, R$ 1,50, e R$ 2,00. O quadro abaixo identifica 
o tempo requerido para operação (em horas) em cada seção da fábrica, bem como a quantidade de 
máquinas disponíveis, que trabalham 40 horas por semana. Planeje a produção semanal da fábrica. 
 
Capítulo 3 Algoritmo Simplex 
Pesquisa Operacional I Jhoab Negreiros 
15
Seção Produto A Produto B Produto C Quantidade de Máquina 
Corte 8 5 2 3 
Dobra 5 10 4 10 
Empacotamento 0,7 1 2 2 
 
Exercício 4. Um criador de coelhos alimenta os animais com cinco tipos de ração, cuja composição 
de nutrientes (unidades/Kg) está mostrada abaixo: 
Nutrientes Ração A Ração B Ração C Ração D Ração E 
Proteínas 30 20 15 80 20 
Carboidratos 60 20 60 20 20 
Gordura 5 10 5 3 2 
Custo/Kg 0,20 0,30 0,40 0,50 0,25 
 
Ele calculou as necessidades diárias de alimentação de cada animal em, pelo menos, 80 unidades 
de proteína, 120 unidades de carboidratos e 30 unidades de gordura. Qual deve ser a mistura das 
rações acima a custo mínimo? 
 
Exercício 5. Desejamos otimizar o lucro pela utilização de até quatro opções de culturas (milho, 
trigo, soja e açúcar). As restrições referem-se ao espaço utilizado, gastos com preparo do terreno e 
utilização de mão-de-obra. Tem-se disponível 400 ha de terra para o cultivo. A matriz abaixo 
apresenta os dados referentes a cada cultura: 
 
Atividade Milho Trigo Soja Açúcar Disponível 
Preparo do terreno (R$/ha) 1.000,00 1.200,00 1.500,00 1.200,00 500.000,00 
Mão-de-obra (homens/dia) 20 30 25 28 10.000 
Lucro (R$/ha) 600,00 800,00 900,00 500,00 
 
Exercício 6. Uma empresa produz televisão em 3 fábricas: São Paulo, João Pessoa e Manaus. Os 
pontos principais de revenda, com as respectivas encomendas mensais são: 
 
Capítulo 3 Algoritmo Simplex 
Pesquisa Operacional I Jhoab Negreiros 
16
Rio de Janeiro 6.000 unidades 
Salvador 5.000 unidades 
Aracajú 2.000 unidades 
Maceió 1.000 unidades 
Recife 3.000 unidades 
 
A produção máxima mensal em cada fábrica é: 
São Paulo 10.000 unidades 
João Pessoa 5.000 unidades 
Manaus 6.000 unidades 
 
O custo de transportes das fábricas até as revendas é dado pelo quadro abaixo: 
R$ por 1.000 unidades de TV. 
Para 
De 
Rio de Janeiro 
(1) 
Salvador 
(2) 
Aracaju 
(3) 
Maceió 
(4) 
Recife 
(5) 
(1) São Paulo 1.000 2.000 3.000 3.500 4.000 
(2) João Pessoa 4.000 2.000 1.500 1.200 1.000 
(3) Manaus 6.000 4.000 3.500 3.000 2.000 
 
Determinar o número de unidades produzidas em cada fábrica e entregues a cada revenda, a fim de 
minimizar o custo de transporte.