494 CHAPTER9 PROGRAMÇÃOLINEAR

9.3 O MÉTODO SIMPLEX: MAXIMIZAÇÃO

Para problemas de programação linear envolvendo duas variáveis, o método de solução gráfica
introduzido na Seção 9.2 é conveniente. No entanto, para problemas que envolvem mais de dois
variáveis ou problemas que envolvem um grande número de restrições, é melhor usar solução
methods that are adaptable to computers. One such method is called thesimplex method,
desenvolvido por George Dantzig em 1946. Ele nos proporciona uma maneira sistemática de examinar
os vértices da região factível para determinar o valor ótimo da função objetivo.
Apresentamos este método com um exemplo.
Suponha que queremos encontrar o valor máximo de zϭ 4x1ϩ 6x2,onde x1Ն 0andx2 Ն 0
subject to the following constraints.
Ϫx1ϩ 5x2Յ 11
Ϫx1ϩ 5x2Յ 27
2x1ϩ 5x2Յ 90
Como o lado esquerdo de cada desigualdade é menor ou igual ao lado direito, há
devem existir números não negativos s,s
1 2e3quespode ser adicionado ao lado esquerdo de cada equa-
a produção do seguinte sistema de equações lineares.
Ϫx1ϩ 5x2ϩ s1 ϩ s2ϩ s3ϭ 11
Ϫx1ϩ 5x2ϩ s1ϩ s2ϩ s3ϭ 27
2x1ϩ 5x2ϩ s1ϩ s2ϩ s3ϭ 90
The numberss1,s2e3são chamados de variáveis slack porque ocupam o "slack" em
cada desigualdade.

Forma Padrão de um Um problema de programação linear está na forma padrão se busca maximizar o objetivo.
funções ativasϭ c1x1ϩ c2 x2ϩ . . . ϩ cn xnsujeito às restrições
Programação Linear
a11x1ϩ a12x2ϩ . . . ϩ a1nxnՅ b1
Problema
a21x1ϩ a22x2ϩ . . . ϩ a2nxnՅ b2
.
.
.
am1 x1ϩ am2 x2ϩ . . . ϩ amnxnՅ bm

ondeeuՆ 0andbeuՆ [Link] de adicionar variáveis de folga, o sistema correspondente de

constraint equationsis
a11x1ϩ a12x2ϩ . . . ϩ a1nxnϩ s1 ϭ b1
a21x1ϩ a22x2ϩ . . . ϩ a2nxn ϩ s2 ϭ b2
.
.
.
am1x1ϩ umm2x2ϩ . . . ϩ amnxn ϩ smϭ bm
onde estái Ն 0.
 SEÇÃO9.3 OMÉTODOSIMPLES:MAXIMIZAÇÃO 495

R E M A R C A: Observe que para um problema de programação linear na forma padrão, o objetivo

a função deve ser maximizável, não minimizável. (Problemas de minimização serão discutidos em
Seções 9.4 e 9.5.

Uma solução básica de um problema de programação linear na forma padrão é uma solução
͑x1,x2, . . . ,xn,s1,s2, . . . ,sm͒ das equações de restrição nas quais há no máximo m variáveis
não nulo––as variáveis que são não nulas são chamadas de variáveis básicas. Uma solução básica para
todas as variáveis não negativas são chamadas de solução básica viável.

O Tableau Simplex
O método simplex é realizado realizando operações elementares nas linhas de uma matriz.
que chamamos de tableau simplex. Este tableau consiste na matriz aumentada correspondente.
respondendo às equações de restrição junto com os coeficientes da função objetivo
escrito na forma
Ϫc1x1Ϫ c2x2Ϫ . . . Ϫ cnxnϩ ͑0s͒ 1ϩ ͑0s͒ 2ϩ . . . ϩ ͑0͒ smϩ zϭ 0.

No tableau, é costume omitir o coeficiente de z. Por exemplo, o tableau simplex

para o problema de programação linear

zϭ 4x1ϩ 6x2 Função objetivo

}
Ϫx1ϩ 5x2 ϩ s1ϩ s2ϩ s3 ϭ 11
Ϫx1ϩ 5x2ϩ s1ϩ s2ϩ s3ϭ 27 Restrições
2x1ϩ 5x2ϩ s1ϩ s2ϩ s3ϭ 90
é o seguinte.
Básico
x1 x2 s1 s2 s3 b Variáveis
Ϫ1 1 1 0 0 11 s1
1 1 0 1 0 27 s2
2 5 0 0 1 90 s3

Ϫ4Ϫ6 0 0 0 0
↑
Valor z atual

Para este tableau simplex inicial, as variáveis básicas são1,s2,ands3, e então no básico
variáveis (que têm um valor de zero) são x1andx2Assim, das duas colunas que estão
mais à direita, vemos que a solução atual é
x1ϭ 0,x2ϭ 0,s1ϭ 11,s2ϭ 27, e3ϭ 90.
Essa solução é uma solução básica factível e frequentemente é escrita como

͑x1,x2,s1,s2,s3͒ ϭ ͑0, 0, 11, 27, 90͒.

496 CAPÍTULO9 PROGRAMÇÃOLINEAR

A entrada no canto inferior direito do tableau simplex é o valor atual de z. Observe

que as entradas da linha inferior sob e xsão
1 x2 negativos dos coeficientes de ex1
os
x2na função objetivo
zϭ 4x1ϩ 6x2.
Para realizar uma verificação de optimalidade para uma solução representada por um tableau simplex, observamos
nas entradas na linha inferior do tableau. Se alguma dessas entradas for negativa (como
acima), então a solução atual não é ótima.

Pivotando
Uma vez que tenhamos configurado a tabela simplex inicial para um problema de programação linear, o sim-
o método plex consiste em verificar a otimalidade e, então, se a solução atual não for óptima
timal, melhorando a solução atual. (Uma solução melhorada é aquela que tem um valor z maior)
do que a solução atual.) Para melhorar a solução atual, trazemos uma nova variável básica
para a solução––chamamos essa variável de variável de entrada. Isso implica que uma das
as variáveis básicas atuais devem sair, caso contrário teríamos muitas variáveis para uma básica
solução – chamamos essa variável de variável de saída. Escolhemos a variável de entrada e
variáveis de partida da seguinte forma.
1. A variável de entrada corresponde à menor (a mais negativa) entrada no
linha inferior do tableau.
2. A variável de partida corresponde à menor razão não negativa de beu͞aij, no
coluna determinada pela variável de entrada.
3. A entrada na tabela simplex na coluna da variável que entra e a que sai
A linha da variável é chamada de pivô.
Finalmente, para formar a solução melhorada, aplicamos a eliminação de Gauss-Jordan à coluna
que contém o pivô, conforme ilustrado no exemplo a seguir. (Esse processo é chamado de
girando.)

E X A M P L E 1 Mudando de Direção para Encontrar uma Solução Melhorada

Use o método simplex para encontrar uma solução melhorada para o problema de programação linear.
representado pelo seguinte tableau.
Básico
x1 x2 s1 s2 s3 b Variáveis

Ϫ1 1 1 0 0 11 s1
1 1 0 1 0 27 s2
2 5 0 0 1 90 s3

Ϫ4Ϫ6 0 0 0 0

A função objetivo para este problema é zϭ 4x1ϩ 6x2.

 SEÇÃO9.3 THESIMPLEXMETHOD:MAXIMIZATION 497

SoluçãoNote que a solução atual ͑xϭ1 0,xϭ 0,sϭ

2 11,sϭ
1 27,sϭ 90͒
2 3 corresponde a
az–valor de 0. Para melhorar esta solução, determinamos que x2 é a variável de entrada,
porqueϪ6 é a menor entrada na fileira inferior.
Básico
x1 x2 s1 s2 s3 b Variáveis

Ϫ1 1 1 0 0 11 s1
1 1 0 1 0 27 s2
2 5 0 0 1 90 s3

Ϫ4Ϫ6 0 0 0 0
↑
Entrando

Paraverporqueescolhemos2como a variável de entrada, lembre-se dissoϭ 4x1ϩ 6x2Portanto, isso

parece que uma mudança de unidade em x2produz uma mudança de 6 inz, enquanto uma mudança de unidade em x1
produz uma mudança de apenas 4 pol.
Para encontrar a variável de partida, localizamos o beuque têm elementos positivos correspondentes
na coluna de variáveis de entrada e forme as seguintes razões.
11 27 90
ϭ 11 ϭ 27 ϭ 18
1 1 5
Aqui, a menor razão positiva é 11, então escolhemos1como a variável de partida.
Básico
x1 x2 s1 s2 s3 b Variáveis

Ϫ1 1 1 0 0 11 s1 ← Partindo
1 1 0 1 0 27 s2
2 5 0 0 1 90 s3

Ϫ4Ϫ6 0 0 0 0
↑
Entrando

Observe que o pivô é a entrada na primeira linha e na segunda coluna. Agora, usamos Gauss-
Eliminação de Jordan para obter a seguinte solução aprimorada.
Antes de girar Após a rotação

Ϫ1 1 1 0 0 11 Ϫ1 1 1 0 0 11

΄ 1
2
Ϫ4 Ϫ6
1
5
0
0
0
1
0
0
0
1
0
27
90
0
΅ ΄ 2
7
Ϫ10
0
0
0
Ϫ1
Ϫ5
6
1
0
0
0
1
0
16
35
66
΅
O novo tableau agora aparece da seguinte forma.
498 CAPÍTULO9 PROGRAMAÇÃOLINEAR

Básico
x1 x2 s1 s2 s3 b Variáveis

Ϫ1 1 1 0 0 11 x2
2 0 Ϫ1 1 0 16 s2
7 0 Ϫ5 0 1 35 s3

Ϫ10 0 6 0 0 66

Observe que2substituiu1na coluna base e a solução melhorada

͑x1,x2,s1,s2,s3͒ ϭ ͑0, 11, 0, 16, 35͒

tem valor az de
zϭ 4x1ϩ 6x2ϭ 4͑0͒ ϩ 6͑11͒ ϭ 66.

No Exemplo 1, a solução melhorada ainda não é ótima, uma vez que a linha inferior ainda tem uma
entrada negativa. Assim, podemos aplicar mais uma iteração do método simplex para avançar ainda mais.
x a variável de entrada. Além disso, o pequeno-
provar nossa solução da seguinte forma. Escolhemos1como
é a razão não negativa de 11͞ ͑ Ϫ1͒16͞2ϭ 8 e 35͞7ϭ 5 é 5, sos3está partindo
variável. A eliminação de Gauss-Jordan produz o seguinte.

Ϫ1 1 1 0 0 11 Ϫ1 1 1 0 0 11

΄ 2
7
Ϫ10
0
0
0
Ϫ1
Ϫ5
6
1
0
0
0
1
0
16
35
66
΅ ΄ 2
1
Ϫ10
0
0
0
Ϫ1
Ϫ57
6
1
0
0
0
1
7
0
16
5
66
΅
2 1
0 1 0 16

΄ ΅
7 7
3
0 0 7 1 Ϫ27 6
1
1 0 Ϫ57 0 7 5
10
0 0 Ϫ87 0 7 116

Assim, o novo tableau simplex é o seguinte.

Básico
x1 x2 s1 s2 s3 b Variáveis
2 1
0 1 7 0 7 16 x2
3
0 0 7 1 Ϫ27 6 s2
1
1 0 Ϫ57 0 7 5 x1
10
0 0 Ϫ87 0 7 116

Neste tableau, ainda há uma entrada negativa na última linha. Assim, escolhemos1como o
entrando variáveis e2como a variável de partida, conforme mostrado no seguinte tableau.
 SEÇÃO9.3 THESIMPLEXMETHOD:MAXIMIZATION 499

Básico
x1 x2 s1 s2 s3 b Variáveis
2 1
0 1 7 0 7 16 x2
3
0 0 7 1 Ϫ27 6 s2 ← Departing
1
1 0 Ϫ57 0 7 5 x1
10
0 0 Ϫ87 0 7 116
↑
Entrando

Ao realizar mais uma iteração do método simplex, obtemos o seguinte tableau.

(Tente verificar isso.)
Básico
x1 x2 s1 s2 s3 b Variáveis
1
0 1 0 Ϫ23 3 12 x2
7
0 0 1 3 Ϫ23 14 s1
5
1 0 0 3 Ϫ13 15 x1
8 2
0 0 0 3 3 132 ←Valor máximo de z

Neste tableau, não há elementos negativos na linha inferior. Portanto, nós determinamos-
minerei a solução ideal para ser

͑x1,x2,s1,s2,s3͒ ϭ ͑15, 12, 14, 0, 0͒

com

zϭ 4x1ϩ 6x2ϭ 4͑15͒ ϩ 6͑12͒ ϭ 132.

OBSERVAÇÃO: Podem ocorrer empates na escolha de variáveis de entrada e/ou saída. Caso isso
acontecer, qualquer escolha entre as variáveis empatadas pode ser feita.

Porque o problema de programação linear no Exemplo 1 envolveu apenas duas variáveis de decisão
Figura 9.18 tabelas, poderíamos ter usado uma técnica de solução gráfica, como fizemos no Exemplo 2, Seção
x2 9.2. Observe na Figura 9.18 que cada iteração no método simplex corresponde a mover
de um vértice dado a um vértice adjacente com um valor z melhorado.
25

20
(5, 16) ͑0, 0͒ ͑0, 11͒ ͑5, 16͒ ͑15, 12͒
15 (15, 12) zϭ 0 zϭ 66 zϭ 116 zϭ 132
10 (0, 11)
5
(0, 0) (27, 0)
O Método Simplex
x1
5 10 15 20 25 30 Resumimos os passos envolvidos no método simplex da seguinte forma.
500 CAPÍTULO9 PROGRAMAÇÃOLINEAR

O Método Simplex Para resolver um problema de programação linear em forma padrão, use os seguintes passos.
1. Converta cada desigualdade no conjunto de restrições em uma equação, adicionando folga.
(Forma Padrão) variáveis.
2. Crie a tabela simplex inicial.
3. Localize a entrada mais negativa na linha inferior. A coluna para esta entrada é chamada de
a coluna de entrada. (Se ocorrerem empates, qualquer uma das entradas empatadas pode ser usada para determinar
a coluna de entrada.)
4. Forme as razões das entradas na 'coluna b' com suas correspondentes positivas
entradas na coluna de entrada. A linha de partida corresponde ao menor não-
razao negativaeu͞aeuj (Se todas as entradas na coluna de entrada forem 0 ou negativas, então há)
não há solução máxima. Para empates, escolha qualquer entrada.) A entrada na linha de partida
e a coluna de entrada é chamada de thepivot.
5. Use operações elementares de linha para que o pivô seja 1 e todas as outras entradas em
as colunas de entrada estão em 0. Este processo é chamado de pivotagem.
6. Se todas as entradas na linha inferior forem zero ou positivas, este é o tableau final. Se não, vá para
voltar ao Passo 3.
7. Se você obtiver um tableau final, então o problema de programação linear tem um máximo
a solução, que é dada pela entrada no canto inferior direito do tableau.

Observe que a solução básica viável de uma tabela simplex inicial é

͑x1,x2, . . . ,xn,s1,s2, . . . ,sm ͒ ϭ ͑0, 0, . . . , 0,b1,b2, . . . ,bm .͒
Esta solução é básica porque no máximo as variáveis são não nulas (nomeadamente as variáveis de folga).
É viável porque cada variável é não negativa.
Nos próximos dois exemplos, ilustramos o uso do método simplex para resolver um
problema envolvendo três variáveis de decisão.

E X A M P L E 2 O Método Simplex com Três Variáveis de Decisão

Use o método simplex para encontrar o valor máximo de

zϭ 2x1Ϫ x2ϩ 2x3 Função objetivo

sujeito às restrições
2x1ϩ 2x2Ϫ 2x3Յ 10
2x1ϩ 2x2Ϫ 2x3Յ 20
2x1ϩ 2x2ϩ 2x3Յ 25

onde está1Ն 0,x2Ն 0,e ao3Ն 0.

Solução Usando a solução básica viável

͑x1,x2,x3,s1,s2,s3͒ ϭ ͑0, 0, 0, 10, 20, 5͒
o tableau simplex inicial para este problema é o seguinte. (Tente verificar esses cálculos,
e note o "empate" que ocorre ao escolher a primeira variável de entrada.)
 SEÇÃO9.3 THESIMPLEXMETHOD:MAXIMIZATION 501

Básico
x1 x2 x3 s1 s2 s3 b Variáveis

2 1 0 1 0 0 10 s1
1 2 Ϫ2 0 1 0 20 s2
0 1 2 0 0 1 5 s3 ← Partindo
Ϫ2 1 Ϫ2 0 0 0 0
↑
Entrando

Básico
x1 x2 x3 s1 s2 s3 b Variáveis

2 1 0 1 0 0 10 s1 ← Partindo
1 3 0 0 1 1 25 s2
1 1 5
0 2 1 0 0 2 2 x3

Ϫ2 2 0 0 0 1 5
↑
Entrando

Básico
x1 x2 x3 s1 s2 s3 b Variáveis
1 1
1 2 0 2 0 0 5 x1
5
0 2 0 Ϫ12 1 1 20 s2
1 1 5
0 2 1 0 0 2 2 x3

0 3 0 1 0 1 15

Isso implica que a solução ótima é

͑x1,x2,x3,s1,s2,s3͒ ϭ ͑5, 0, 52 , 0, 20, 0͒

e o valor máximo de z é 15.

Ocasionalmente, as restrições em um problema de programação linear incluirão uma equação.

Nesses casos, ainda adicionamos uma "variável de folga" chamada de variável artificial para formar o ini-
tabela simplex tial. Tecnicamente, essa nova variável não é uma variável de folga (porque há
não há folga a ser considerada). Depois de ter determinado uma solução ideal em um problema desse tipo,
você deve verificar se as equações dadas nas restrições originais estão satisfeitas.
O exemplo 3 ilustra tal caso.

E X A M P L E 3 O Método Simplex com Três Variáveis de Decisão

Use o método simplex para encontrar o valor máximo de

zϭ 3x1ϩ 2x2ϩ x3 Função objetivo

502 CHAPTER9 LINEARPROGRAMMING

sujeito às restrições
4x1 ϩ 3x2ϩ 3x3ϭ 30
2x1ϩ 3x2ϩ 3x3Յ 60
2x1ϩ 2x2ϩ 3x3Յ 40

onde está1 Ն 0,x2Ն 0,e a3Ն 0.

Solução Usando a solução básica viável

͑x1,x2,x3,s1,s2,s3͒ ϭ ͑0, 0, 0, 30, 60, 40͒
the initial simplex tableau for this problem is as follows. (Note thats1 é uma vari- artificia
capaz, em vez de uma variável folgada.)
Básico
x1 x2 x3 s1 s2 s3 b Variáveis

4 1 1 1 0 0 30 s1 ← Partindo
2 3 1 0 1 0 60 s2
1 2 3 0 0 1 40 s3

Ϫ3Ϫ2Ϫ1 0 0 0 0
↑
Entrando

Básico
x1 x2 x3 s1 s2 s3 b Variáveis
1 1 1 15
1 4 4 4 0 0 2 x1
5 1
0 2 2 Ϫ12 1 0 45 s2 ← Partindo
7 11 65
0 4 4 Ϫ14 0 1 2 s3
3 45
0 Ϫ54Ϫ14 4 0 0 2
↑
Entrando

Básico
x1 x2 x3 s1 s2 s3 b Variáveis
1 3
1 0 5 10 Ϫ110 0 3 x1
1 2
0 1 5 Ϫ15 5 0 18 x2
12 1
0 0 5 10 Ϫ170 1 1 s3
1 1
0 0 0 2 2 0 45
Isso implica que a solução ótima é
͑x1,x2,x3,s1,s2,s3͒ ϭ ͑3, 18, 0, 0, 0, 1͒
e o valor máximo de z é 45. (Esta solução satisfaz a equação dada na con-
restrições porque4͑ 3͒ ϩ 1͑ 18͒ ϩ 1͑ 0͒ ϭ 30.͒
 SECTION9.3 THESIMPLEXMETHOD:MAXIMIZATION 503

Aplicações

E X A M P L O 4A Aplicação Empresarial: Lucro Máximo

Um fabricante produz três tipos de fixações de plástico. O tempo necessário para moldagem,
o corte e a embalagem são apresentados na Tabela 9.1. (Os tempos são dados em horas por dúzia
instalações.)
TABELA9.1

Processo TipoA Tipo B Tipo C Tempo total disponível

3
Moldagem 1 2 2 12.000
2 2
Aparar 3 3 1 4.600
1 1 1
Embalagem 2 3 2 2.400

Lucro $11 R$ 16 $15 —

Quantas dúzias de cada tipo de fixture devem ser produzidas para obter um lucro máximo?

SoluçãoDeixando x1,x2, e x3representar o número de dúzias das unidades dos Tipos A, B e C, respe-
tivamente, a função objetivo é dada por
Lucroϭ Pϭ 11x1ϩ 16x2ϩ 15x3.
Além disso, usando as informações na tabela, construímos as seguintes restrições.
2
3 x1ϩ 2x2ϩ 32 x3Յ 12,000
2 2 3
3 x1ϩ 3 x2ϩ 2 x3Յ 14.600
1 1 1
2 x1ϩ 3 x2 ϩ 2 x3 Յ 12.400
(Também assumimos que x1 Ն 0,x2Ն 0,e depois3Ն 0.) Agora, aplicando o método simplex com
a solução básica viável
͑x1,x2,x3,s1,s2,s3͒ ϭ ͑0, 0, 0, 12,000, 4,600, 2,400͒
obtemos os seguintes tabelas.
Básico
x1 x2 x3 s1 s2 s3 b Variáveis
3
1 2 2 1 0 0 12.000 s1 ← Partindo
2 2
3 3 1 0 1 0 4,600 s2
1 1 1
2 3 2 0 0 1 2,400 s3

Ϫ11Ϫ16Ϫ15 0 0 0 0
↑
Entrando
504 CAPÍTULO9 PROGRAMÇÃOLINEAR

Básico
x1 x2 x3 s1 s2 s3 b Variables
1 3 1
2 1 4 2 0 0 6.000 x2
1 1 1
3 0 2 Ϫ3 1 0 600 s2
1 1
3 0 4 Ϫ16 0 1 400 s3 ← Partindo
Ϫ3 0 -3 8 0 0 96,000
↑
Entrando

Básico
x1 x2 x3 s1 s2 s3 b Variáveis
3 3
0 1 8 4 0 Ϫ32 5.400 x2
1
0 0 4 Ϫ16 1 Ϫ1 200 s2 ← Partindo
3
1 0 4 Ϫ12 0 3 1.200 x1
13
0 0 Ϫ34 2 0 9 99,600
↑
Entrando

Básico
x1 x2 x3 s1 s2 s3 b Variáveis

0 1 0 1 Ϫ32 0 5.100 x2
0 0 1 Ϫ23 4 Ϫ4 800 x3
1 0 0 0Ϫ3 6 600 x1

0 0 0 6 3 6 100,200
A partir deste tableau simples final, vemos que o lucro máximo é de $100.200, e isso é
obtido pelos seguintes níveis de produção.
TipoA: 600 dúzias de unidades

Tipo B: 5.100 dúzias de unidades

Tipo C: 800 dúzias de unidades

OBSERVAÇÃO: No Exemplo 4, note que o segundo tableau simplex contém um "empate" para o
entrada mínima na linha inferior. (Tanto a primeira quanto a terceira entradas na linha inferior são
Ϫ3.) Embora tenhamos escolhido a primeira coluna para representar a variável de partida, poderíamos ter sido.
escolheu a terceira coluna. Tente reformular o problema com esta escolha para ver o que você obtém
a mesma solução.

E X A M P L E 5A Business Application: Media Selection

As alternativas de publicidade para uma empresa incluem televisão, rádio e jornal

anúncios. Os custos e estimativas para cobertura de audiência estão apresentados na Tabela 9.2
 SEÇÃO9.3 THESIMPLEXMETHOD:MAXIMIZATION 505

TABELA9.2

Televisão Jornal Rádio

Custo por anúncio R$ 2.000 $ 600 $ 300

Público por anúncio 100.000 40.000 18.000

O jornal local limita o número de anúncios semanais de uma única empresa a

dez. Além disso, para equilibrar a publicidade entre os três tipos de mídia, não mais
mais da metade do número total de anúncios deve ocorrer no rádio, e pelo menos 10%
deve ocorrer na televisão. O orçamento semanal de publicidade é de R$ 18.200. Quantos anúncios...
Os anúncios devem ser veiculados em cada um dos três tipos de mídia para maximizar o público total?

SoluçãoPara começar, deixamos x1,x2,e x3representar o número de anúncios na televisão, notícias-

papel e rádio, respectivamente. A função objetivo (a ser maximizada) é, portanto,

zϭ 100.000x1ϩ 40.000x2ϩ 18.000x3 Função objetivo

onde está1Ն 0,x2Ն 0,e ou3Ն [Link] restrições para este problema são as seguintes.
2000x1 ϩ 600x2ϩ 300x3Յ 18,200
2000x1ϩ 600x2ϩ 300x3Յ 10
2000x1ϩ 600x2ϩ 300x3 Յ 0.5͑x1ϩ x2ϩ x3͒
2000x1ϩ 600x2ϩ 300x3Ն 0,1͑x1ϩ x2ϩ x3͒

A more manageable form of this system of constraints is as follows.

}
20x1ϩ 6x2ϩ 3x3Յ 182
20x1ϩ 6x2ϩ 3x3Յ 110
Ϫx1Ϫ 6x2 ϩ 3x3Յ 180 Restrições
Ϫ9x1ϩ 6x2ϩ 3x3Յ 180

Assim, o tableau simplex inicial é o seguinte.

Básico
x1 x2 x3 s1 s2 s3 s4 b Variáveis

20 6 3 1 0 0 0 182 s1 ← Partindo
0 1 0 0 1 0 0 10 s2
Ϫ1 Ϫ1 1 0 0 1 0 0 s3
Ϫ9 1 1 0 0 0 1 0 s4

Ϫ100,000 Ϫ40.000Ϫ18.000 0 0 0 0 0
↑
Entrando
506 CHAPTER9 PROGRAMAÇÃOLINEAR

Agora, a este tableau inicial, aplicamos o método simplex da seguinte forma.

Básico
x1 x2 x3 s1 s2 s3 s4 b Variáveis
3 3 1 91
1 10 20 20 0 0 0 10 x1
0 1 0 0 1 0 0 10 s2 ← Partindo
23 1 91
0 Ϫ170 20 20 0 1 0 10 s3
37 47 9 819
0 10 20 20 0 0 1 10 s4

0 Ϫ10.000Ϫ3,0005,000 0 0 0 910.000
↑
Entrando

Básico
x1 x2 x3 s1 s2 s3 s4 b Variáveis
3 1 61
1 0 20 20 Ϫ130 0 0 10 x1
0 1 0 0 1 0 0 10 x2
23 1 7 161
0 0 20 20 10 1 0 10 s3 ← Partindo
47 9 37 449
0 0 20 20 Ϫ 10 0 1 10 s4

0 0 Ϫ3,000 5,000 10,000 0 0 1.010.000

↑
Entrando

Básico
x1 x2 x3 s1 s2 s3 s4 b Variáveis
1
1 0 0 23 Ϫ293 Ϫ233 0 4 x1
0 1 0 0 1 0 0 10 x2
1 14 20
0 0 1 23 23 23 0 14 x3
8 118 47
0 0 0 23 Ϫ 23 Ϫ 23 1 12 s4
118.000 272.000 60.000
0 0 0 23 23 23 0 1.052.000
A partir deste tableau, vemos que a audiência semanal máxima para um orçamento de publicidade de
$18.200 é
zϭ 1.052.000 Audiência máxima semanal

e isso ocorre quando1ϭ 4,x2ϭ 10,e3ϭ 14. Nós resumimos os resultados aqui.

Número de
Mídia {"Advertisements":"Anúncios"}
Cost Público
Televisão 4 R$ 8.000 400.000
Jornal 10 $ 6.000 400.000
Rádio 14 R$ 4.200 252.000
Total 28 R$ 18.200 1.052.000
 SECTION9.3 EXERCÍCIOS 507

SEÇÃO 9.3❑ EXERCISES

Nos Exercícios 1 a 4, escreva o tableau simplex para a programação linear dada. 11. Função objetivo: [Link] function:
problema de programação. Você não precisa resolver o problema. (Em cada zϭ 5x1ϩ 2x2ϩ 8x3 z ϭ x1Ϫ x2 ϩ 2x3
caso a função objetivo deva ser maximizada.) Restrições: Restrições:
[Link]ção objetivo: [Link]ção objetivo: 2x1Ϫ 4x2ϩ 3x3Յ 42 2x1ϩ 2x2Յ 8
zϭ x1ϩ 2x2 zϭ x1ϩ 3x2 2x1ϩ 3x2 Ϫ 3x3Յ 42 2x1ϩ 2x3Յ 5
Constraints: Restrições: 6x1Ϫ 3x2ϩ 3x3Յ 42 x1,x2,x3Ն 0
2x1ϩ x2Յ 8 x1ϩ x2Յ 4 x1,x2,x3Ն 40
2x1ϩ x2Յ 5 x1Ϫ x2Յ 1 13. Função objetivo: 14. Função objetivo:
2x1,x2Ն 0 x1,x2 Ն 0 zϭ 4x1ϩ 5x2 zϭ x1ϩ 2x2
3. Função objetivo: [Link]ção Objetivo: Restrições: Restrições:
zϭ 2x1ϩ 3x2ϩ 4x3 zϭ 6x1Ϫ 9x2 3x1ϩ 7x2Յ 10 2x1ϩ 3x2Յ 15
Constraints: Restrições: 3x1ϩ 7x2Յ 42 2x1Ϫ 3x2Յ 12
x1ϩ 2x2ϩ x3Յ 12 2x1Ϫ 3x2Յ 26 x1,x2Ն 40 x1,x2Ն 10
x1ϩ 2x2ϩ x3Յ 18 2x1 ϩ 3x2Յ 20 15. Função objetivo: [Link]ção objetivo:
x1,x2,x3 Ն 10 x1,x2Ն 20 zϭ 3x1ϩ 4x2ϩ x3ϩ 7x4 zϭ x1
Restrições: Restrições:
Nos Exercícios 5–8, explique por que o problema de programação linear é
8x1ϩ 3x2ϩ 4x3ϩ 5x4Յ 7 3x1ϩ 2x2Յ 60
não está na forma padrão como dado.
2x1ϩ 6x2ϩ 4x3ϩ 5x4Յ 3 3x1ϩ 2x2Յ 28
5.(Minimizar) 6.(Maximizar)
2x1ϩ 4x2ϩ 5x3ϩ 2x4Յ 8 3x1 ϩ 4x2 Յ 48
Função objetivo: Função objetivo:
x1,x2,x3,x4Ն 0 x1,x2Ն 40
zϭ x1ϩ x2 zϭ x1ϩ x2
Restrições: Restrições: 17. Função objetivo: 18. Função objetivo:
zϭ x1Ϫ x2ϩ x3 zϭ 2x1ϩ x2ϩ 3x3
x1ϩ 2x2Յ 4 2x1ϩ 2x2Յ Ϫ6
x1,x2Ն 0 2x1Ϫ 2x2Յ Ϫ1 Constraints: Restrições:
x1,x2Ն Ϫ0 2x1ϩ 2x2Ϫ 3x3Յ 40 2x1ϩ x2ϩ 3x3Յ 59
2x1ϩ 2x2ϩ 3x3Յ 25 2x1ϩ x2ϩ 3x3Յ 75
7.(Maximizar) 8.(Maximizar)
2x1ϩ 2x2ϩ 3x3Յ 32 2x1ϩ x2ϩ 6x3Յ 54
Função objetivo: Função objetivo:
x1,x2,x3Ն 30 x1,x2,x3Ն 50
zϭ x1ϩ x2 zϭ x1ϩ x2
Restrições: Constraints: [Link]ção objetivo:
zϭ x1 ϩ 2x2Ϫ x4
2x1ϩ x2ϩ 3x3Յ 5 x1ϩ x2Ն 4
Restrições:
2x1ϩ x2Ϫ 2x3Ն 1 2x1ϩ x2Ն 6
x1ϩ 2x2ϩ 3x3ϩ x4Յ 24
2x1ϩ x2ϩ 3x3 Յ 0 x1,x2Ն 0
x1ϩ 3x2ϩ 7x3ϩ x4Յ 42
x1,x2,x3 Ն 0
x1,x2,x3,x4Ն 40
Nos Exercícios 9–20, use o método simplex para resolver o dado
[Link]ção objetivo:
problema de programação linear. (Em cada caso, a função objetivo
zϭ x1ϩ 2x2ϩ x3Ϫ x4
deve ser maximizado.)
Restrições:
9. Função objetivo: 10. Função objetivo:
2x1ϩ 3x2ϩ 3x3ϩ 4x4Յ 60
zϭ x1ϩ 2x2 zϭ x1ϩ x2
2x1ϩ 3x2ϩ 2x3ϩ 5x4Յ 50
Restrições: Restrições: 2x1ϩ 3x2ϩ 2x3 ϩ 6x4Յ 72
x1ϩ 4x2Յ 18 3x1ϩ 2x2Յ 16 x1,x2,x3,x4Ն 70
x1ϩ 4x2Յ 12 3x1ϩ 2x2Յ 12
x1,x2 Ն 10 x1,x2Ն 10
508 CHAPTER9 PROGRAMAÇÃOLINEAR

21. Um comerciante planeja vender dois modelos de computadores para casa em 26. Suponha que no exercício 25 o tempo total disponível para a montagem
custos de $250 e $400, respectivamente. O modelo de $250 gera um brilho, pintura e embalagem é 4000 horas, 2500 horas, e
o lucro de $45 e o modelo de $400 gera um lucro de $50. O 1500 horas, respectivamente, e que o lucro por unidade é de $48
o comerciante estima que a demanda total mensal não irá (Modelo A), $50 (Modelo B) e $52 (Modelo C). Quantos
exceder 250 unidades. Encontrar o número de unidades de cada modelo que de cada tipo deve ser produzido para obter um lucro máximo?
deve ser estocado para maximizar o lucro. Suponha que [Link] empresa orçou um máximo de $600.000 para publicidade.
o comerciante não quer investir mais de $70.000 em anunciando um certo produto nacionalmente. Cada minuto de televisão
inventário de computadores. (Veja o Exercício 21 na Seção 9.2.) o custo do tempo é de $60.000 e cada anúncio de página inteira em jornal custa
22. Um produtor de frutas tem 150 acres de terra disponíveis para cultivar dois $15,000. Cada anúncio na televisão é esperado ser visto por 15
plantas, A e B. Leva um dia para podar um acre da planta A e milhão de espectadores, e cada anúncio de jornal deve ser
dois dias para cultivar um acre da cultura B, e há 240 dias por ano visto por 3 milhões de leitores. A pesquisa de mercado da empresa
ano disponível para poda. Leva 0,3 dia para colher um acre de o departamento aconselha a empresa a usar no máximo 90% do
cultura A e 0,1 dia para colher um acre de cultura B, e há 30 orçamento de publicidade em anúncios na televisão. Como deve o
dias por ano disponíveis para colheita. Encontre o número de acres o orçamento de publicidade deve ser alocado para maximizar o total audi-
de cada fruta que deve ser plantada para maximizar o lucro, como- sentido?
fazendo a suposição de que o lucro é de $140 por acre para a cultura A e $235 [Link] o Exercício 27 assumindo que cada jornal de uma página
por acre para B. (Veja o Exercício 22 na Seção 9.2.) O anúncio custa $30.000.
[Link] produtora tem 50 acres de terra para a qual ela planeja cultivar 29. Um investidor tem até $250.000 para investir em três tipos de
três culturas. Custa $200 produzir um acre de cenouras e investimentos. O Tipo A paga 8% ao ano e tem um fator de risco de
o lucro é de $60 por acre. Custa $80 para produzir um acre de O tipo B paga 10% anualmente e tem um fator de risco de 0,06.
aipo e o lucro é de $20 por acre. Finalmente, custa $140 para O Tipo C paga 14% ao ano e tem um fator de risco de 0,10.
produzir um acre de alface e o lucro é de $30 por acre. ter um portfólio bem equilibrado, o investidor impõe o fol-
o método simplex para encontrar o número de acres de cada cultura As condições de baixo risco. O fator de risco médio não deve ser nenhum
ela deve plantar para maximizar seu lucro. Assuma que maior que 0,05. Além disso, pelo menos um quarto do total
seu custo não pode exceder $10.000. o portfólio deve ser alocado para investimentos do Tipo A e pelo menos
[Link] empresa de sucos de frutas faz duas bebidas especiais misturando um quarto do portfólio deve ser alocado para o Tipo B investir
sucos de maçã e abacaxi. A primeira bebida utiliza 30% de maçã Quanto deve ser alocado para cada tipo de investimento?
suco e 70% de abacaxi, enquanto a segunda bebida usa 60% a obter um retorno máximo?
maçã e 40% de abacaxi. Há 1000 litros de maçã e 30. Um investidor tem até $450.000 para investir em três tipos de
1500 litros de suco de abacaxi disponíveis. Se o lucro para o investimentos. Tipo A paga 6% ao ano e tem um fator de risco
a primeira bebida custa $0,60 por litro e para a segunda bebida é do 0. O Tipo B paga 10% ao ano e tem um fator de risco de 0,06.
$0.50, use o método simples para encontrar o número de litros de O Tipo C paga 12% anualmente e tem um fator de risco de 0,08. Para
cada bebida que deve ser produzida para maximizar o ter um portfólio bem equilibrado, o investidor impõe o
lucro. As condições seguintes. O fator de risco médio não deve ser nenhum
[Link] fabricante produz três modelos de bicicletas. O tempo maior que 0,05. Além disso, pelo menos metade do total
(em horas) necessárias para montagem, pintura e embalagem o portfólio deve ser alocado em investimentos do Tipo A e pelo menos
cada modelo é o seguinte. um quarto do portfólio deverá ser alocado para o Tipo B invest-
quantos devem ser alocados para cada tipo de
Modelo A Modelo B Modelo C investimento para obter um retorno máximo?
Montando 2 2,5 3 31. Uma empresa de contabilidade tem 900 horas de tempo de equipe e 100 horas
de revisar o tempo disponível a cada semana. A empresa cobra
Pintura 1,5 2 1 $2000 for an audit and $300 for a tax return. Each audit
Embalagem 1 0,75 1,25 requer 100 horas de tempo da equipe e 10 horas de tempo de revisão,
e cada declaração de impostos requer 12,5 horas de tempo da equipe e 2,5
O tempo total disponível para montar, pintar e embalar horas de tempo de revisão. Qual número de auditorias e declarações fiscais
são 4006 horas, 2495 horas e 1500 horas, respectivamente. trará uma receita máxima?
The profit per unit for each model is $45 (Model A), $50
(Modelo B), e $55 (Modelo C). Quantos de cada tipo
deve ser produzido para obter um lucro máximo?
 SECTION9.4 THESIMPLEXMETHOD:MINIMIZATION 509

32. A firma de contabilidade no Exercício 31 aumenta sua cobrança por um 35. (Maximize) 36.(Maximizar)
auditoria de até $2500. Qual o número de auditorias e declarações de imposto que Função objetivo: Função objetivo:
gerar uma receita máxima? zϭ 2,5x1ϩ x2 zϭ x1ϩ 12x2
In the simplex method, it may happen that in selecting the departing Restrições: Restrições:
todas as variáveis calculadas são negativas. Isso indica uma 3x1ϩ 5x2Յ 15 2x1ϩ 3x2Յ 20
solução limitada. Demonstre isso nas Exercícios 33 e 34. 5x1ϩ 2x2Յ 10 2x1ϩ 3x2Յ 35
x1,x2Ն 10 x1,x2Ն 30
33.(Maximizar) 34. (Maximizar)
C 37. Use um computador para maximizar a função objetivo
Função objetivo: Função objetivo:
zϭ x1 ϩ 2x2 zϭ x1ϩ 3x2 zϭ 2x1ϩ 7x2ϩ 6x3ϩ 4x4
Restrições: Restrições: sujeito às restrições
Ϫx1Ϫ 3x2Յ 1 Ϫx1ϩ x2Յ 20 1,2x1ϩ 0,7x2ϩ 0,83x3 ϩ 0,5x4Յ 65
Ϫx1ϩ 2x2Յ 4 Ϫ2x1ϩ x2Յ 50 1,2x1ϩ 0,7x2ϩ 0,83x3ϩ 1.2x4Յ 96
x1,x2Ն 0 x1,x2Ն 50 0,5x1ϩ 0,7x2ϩ 01.2x3ϩ 0,4x4Յ 80
onde está1,x2,x3,x4Ն 0.
Se o método simplex termina e uma ou mais variáveis não estão em C [Link] um computador para maximizar a função objetivo
a base final tem entradas na linha inferior iguais a zero, trazendo isso
As variáveis na base determinarão outras soluções ótimas. zϭ 1,2x1ϩ x2ϩ x3ϩ x4
Demonstre isso nos Exercícios 35 e 36. sujeito ao mesmo conjunto de restrições dadas no Exercício 37.

9.4 O MÉTODO SIMPLEX: MINIMIZAÇÃO

Na Seção 9.3, aplicamos o método simplex apenas a problemas de programação linear em
forma padrão onde a função objetivo era maximizada. Nesta seção, estendemos
este procedimento para problemas de programação linear em que a função objetivo é ser minimizada
otimizado.
Um problema de minimização está em forma padrão se a função objetivo wϭ c1x1ϩ c2x2
ϩ . . . ϩ cn xndeve ser minimizado, sujeito às restrições

a11x1ϩ a12x2ϩ . . . ϩ a1nxnՆ b1

a21x1ϩ a22x2ϩ . . . ϩ a2nxnՆ b2

..
.
a m1x1ϩ am2x2ϩ . . . ϩ amnxnՆ bm

onde está xeuՆ 0 e andbeuՆ 0.O procedimento básico usado para resolver tal problema é convertê-lo
para um problema de maximização em forma padrão, e então aplicar o método simplex como dis-
discutido na Seção 9.3.
No Exemplo 5 na Seção 9.2, usamos métodos geométricos para resolver o seguinte
problema de minimização.