A seguir, uma demonstração do livro.
Para adquirir a versão completa em papel, acesse:
www.pagina10.com.br
Programação Linear: a técnica mais importante da Pesquisa Operacional - 2
RESOLUÇÃO GRÁFICA
Nesta
seção,
vamos
mostrar
como
podemos
resolver
graficamente problemas de programação linear de duas variáveis. Para
tanto, utilizaremos o programa gratuito GRAPH® em sua versão 4.3,
®
GRAPH é marca registrada de Ivan
retomando o problema da confecção de uma seção anterior.
Johansen (2007). Novas versões, manuais e
códigos fonte estão disponíveis em
www.padowan.dk.
Exemplo 1K
Uma pequena confecção está dividida em três setores, corte, costura e
embalagem com, respectivamente, 5, 9 e 4 funcionários. Durante certo
período, produzirá, com exclusividade, vestidos e camisetas. A tabela
seguinte mostra os tempos em minutos que cada um dos produtos
consome nos três setores:
vestido
camiseta
corte
3 min
1 min
costura
6 min
1 min
embalagem
1 min
1 min
a) Quantos vestidos e quantas camisetas deverá produzir no intervalo de 6
minutos se os lucros respectivos por unidade de cada produto forem R$
14,00 e R$ 7,00?
Este problema foi modelado na seção anterior, ocasião em que
obtivemos:
Cada vestido demora 3 minutos e cada
maximizar F  14x  7y
camiseta 1 minuto no corte, onde temos 30
3x  y  30

sujeito a 6x  y  54
x  y  24

minutos(5 funcionários x 6 minutos)
disponíveis. Similarmente, cada vestido
demora 6 e cada camiseta demora 1 minuto
na costura onde temos 54 (9 x 6) minutos
disponíveis. Finalmente, para serem
embadados, cada vestido e cada camiseta
demoram 1 minuto, onde temos 24 (4 x 6)
minutos disponíveis.
Ao lado, representamos alguns pontos do
Podemos considerar os pontos (x, y) do plano cartesiano para representar
os pares de solução para o problema considerado. Assim, o ponto
genérico (x, y) representará as quantidades x de vestidos e y de
camisetas. Com o programa Graph, podemos destacar alguns destes
pontos no plano cartesiano xy:
camisetas
30
plano cartesiano relevantes para o problema.
25
Veja que quantidades negativas não têm
significado e, desta forma, omitimos os
20
outros quadrantes do plano. Estes pontos,
15
com algum trabalho de digitação, poderão ser
10
representados num arquivo do Graph através
5
do botão Inserir série de pontos ou da tecla
1
de atalho F4.
2
3
4
5
6
7
8
9
10
11
vestidos
No entanto, nem todas estas combinações serão possíveis de serem
implementadas na prática devido às limitações impostas pelos setores.
Por exemplo, o setor de embalagem imprime a restrição x + y ≤ 24.
Assim, não será possível embalar em 6 minutos, por exemplo, x = 10
vestidos e y = 15 camisetas pois, neste caso, 10 + 15 = 25 > 24. Assim, a
restrição x + y ≤ 24
Programação Linear: a técnica mais importante da Pesquisa Operacional - 3
selecionará uma região de pontos possíveis no gráfico anterior. Esta
Isso pode ser obtido a partir do botão Inserir
região será o triângulo formado pelas retas x + y = 24, x = 0 (eixo y) e y =
relação, que insere uma nova equação ou
0 (eixo x).
camisetas
inequação através do ícone é x < y ou da
tecla F6. No campo relação, digite "x+y<=24"
30
25
e, no campo constante, digite "x>=0 and
y>=0". O resultado será o triângulo
20
(10, 15)
sombreado ao lado. Veja que o ponto (10, 15)
se encontra fora do triângulo, o que mostra a
inviabilidade de implementar a produção de
10 vestidos e 15 camisetas sob o ponto de
15
10
5
Embalagem x + y ≤ 24
vista do setor de embalagem.
5
10
15
20
25
vestidos
Em seguida, colocamos as demais inequações no gráfico, isto é, as
restrições devidas aos setores de corte e de costura:
Procedemos de modo análogo usando o
recurso inserir relação por mais duas vezes,
uma para cada desigualdade. Assim, para
Costura
que uma solução seja viável, é necessário
que pertença aos três triângulos
simultaneamente, isto é, pertença ao
pentágono definido pela intersecção dos três
triângulos da figura.
Embalagem
Corte
No entanto, para que o Graph exiba apenas o pentágono das intersecções
dos 3 triângulos, você poderá inserir uma única relação e especificar, além
de "x>=0" e "y>=0" as outras duas no parâmetro constante, todas
interligadas com a palavra reservada "and":
24
22
20
Embalagem
18
16
14
12
Corte
10
8
6
4
Costura
2
1
2
3
4
5
6
7
8
9
O efeito produzido será o da figura ao lado.
Veja que apenas os pontos localizados na região poligonal
sombreada representarão combinações de vestidos (x) e de camisetas (y)
possíveis de serem produzidas no intervalo de 6 minutos. A questão que
se coloca agora é: qual destes pontos representará a combinação de
maior lucro? Para tanto, tomamos a função objetivo F = 14x + 7y, e
isolamos o valor de y, obtendo a equação:
Programação Linear: a técnica mais importante da Pesquisa Operacional - 4
Desta maneira, transformamos uma função F
F  14x  7y  y 
de duas variáveis x e y numa família de
F
 2x
7
funções y que, para cada F fixo, será
representada pela reta de equação dada.
Assim, para cada valor de F, teremos uma reta específica. Por exemplo,
atribuindo-se diferentes valores a F, teremos:
70
 2x
7
105
F  105  y =
 2x
7
140
F  140  y =
 2x
7
Como estas três retas apresentam os
F  70  y =
mesmos coeficientes angulares (2), as
tangentes trigonométricas dos ângulos α
serão iguais e, consequentemente, os
ângulos  serão iguais, o que determinará
três retas paralelas.
Os gráficos destas três retas estão desenhados na figura a seguir. Cada
uma das retas representará combinações de vestidos (x) e de camisetas
(y) que resultarão no lucro F indicado. Assim, por exemplo, a reta mais
abaixo, com F = 70, é formada por pontos que representam combinações
de vestidos e de camisetas que proporcionarão lucro de F = 70 reais:
24
22
Embalagem
20
18
Para inserir cada uma das retas, clique sobre
16
o ícone do gráfico ou tecle "INS". Em seguida,
14
Corte
F = 140
12
mantenha o tipo da função na padrão y = f(x)
10
e digite "70/7−2x", escolha uma cor e uma
8
expessura para a reta e clique em OK.
6
Proceda de modo similar para cada uma das
F = 105
F = 70
4
Costura
2
outras retas.
1
2
3
4
5
6
7
8
9
Desta forma, teremos muitas maneiras de produzir lucro de R$ 70, muitas
de produzir lucro de R$ 105 e também de R$ 140 e que estas retas
seguem paralelas entre si e sobem à medida que F aumenta. Pelo gráfico
acima, concluímos que haverá apenas uma maneira de o lucro ser o maior
possível: isso ocorrerá para a reta paralela que tocar o ponto de encontro
das duas restrições, embalagem e corte, destacado na figura anterior. As
coordenadas deste ponto, portanto poderão ser dadas pela resolução do
seguinte sistema de equações:
22
F = 189
Embalagem
x  y  24 
 ()
3x  y  30 

2x  6  x  3
20
18
16
14
12
F = 140
10
y  24  3  y  21
F = 105
8
6
F = 70
4
Este ponto indicará que serão necessários produzir x = 3 vestidos e y = 21
2
1
2
3
4
Realmente, se traçarmos a reta y = 189/7
−2x no gráfico anterior, veremos que ela
camisetas em 6 minutos para que o lucro seja o maior possível:
F  14x  7y
F  14  3  7  21  189
tocará o ponto (3, 21) e será paralela às
demais.
Assim, podemos concluir, com isso, que a solução ótima será,
necessariamente, algum ponto do contorno da região poligonal.
Programação Linear: a técnica mais importante da Pesquisa Operacional - 5
Existe um recurso do Graph realmente sensacional para visualizar
estas retas paralelas através de uma animação. Para tanto, desabilite
todas as quatro retas anteriores clicando sobre o seu objeto no lado
esquerdo do menu e defina a seguinte constante F = 0:
Para isso, clique sobre o botão funções
otimizadas de ícone f(t) ou pressione "CTRL
F". Na coluna Nomes, digite F e na coluna
Definição digite 0 (zero).
Agora, insira uma nova função e a parametrize conforme a seguinte caixa
de diálogo:
Na definição de função, digite "F/7−2x". O
Graph entenderá que F é o valor 0 digitado
anteriormente e traçará a reta que conterá os
pontos que terão lucro zero, isto é, f(x) =
−2x, o que inclui apenas o ponto (0, 0) do
pentágono.
Agora, clique no menu Calc e na opção animação... e configure a janela
de diálogo como indicado:
Isso gerará um vídeo onde o valor de F será
continuamente modificado de 0 até 189
(valor ótimo), com passos de 10, isto é, F
será 0, depois 10, depois 20, etc, até 189. A
velocidade de frames/segundos deverá ser
no mínimo 10, para que tenhamos uma idéia
de que uma mesma reta estará se
deslocando sobre o pentágono com o
aumento do valor de F até 189.
Clicando sobre o botão Animação, o Graph gerará um vídeo .avi que,
inclusive, poderá ser salvo em seu computador:
Veja ao lado o instante em que F é igual a
110 (mostrado no canto inferior direito),
ocasião em que demos pause no vídeo e
visualizamos a reta correspondente ao lucro
de 110 reais. Continuando a visualizar, a reta
parecerá se deslocar paralelamente até o
ponto azul, encontro das restrições
embalagem e corte, ponto ótimo do
problema de PL em questão: x = 3 e y = 21.
Programação Linear: a técnica mais importante da Pesquisa Operacional - 6
b) Quantos vestidos e camisetas deverá produzir no intervalo de 6
minutos se os lucros respectivos por unidade de cada produto são R$
28,00 e R$ 7,00?
Alterou-se apenas o lucro unitário dos vestidos de R$ 14 para R$ 28.
Assim, a região de soluções viáveis será a mesma pentagonal fechada
enquanto que as retas de lucro terão a seguinte equação:
F  28x  7y  y 
F
 4x
7
Assim, para cada um valor de F específico, teremos uma reta diferente,
todas, porém, com o mesmo coeficiente angular e, portanto, paralelas
como as do item anterior:
Comparando estas retas com as do item
70
 4x
7
105
F  105  y 
 4x
7
140
F  140  y 
 4x
7
anterior, concluímos que apenas os
F  70  y 
coeficientes angulares se alteraram (de 2
para 4). Haverá possibilidades, então, de a
solução ótima ser alterada, conforme
veremos a seguir.
Observando as retas paralelas, concluímos que a solução ótima será agora
o ponto de encontro das restrições do corte e da costura:
24
22
Embalagem
20
18
F = 231
16
Corte
14
12
F = 140
10
8
F = 105
6
4
2
Costura
F = 70
1
2
3
4
5
6
7
8
9
6x  y  54 
 ()
3x  y  30

3x  24  x  8
y  54  6  8  y  6
Este ponto indicará que serão necessários produzir x = 8 vestidos e y = 6
camisetas em 6 minutos para que o lucro seja o maior possível:
Corte
F = 266
F  28x  7y
F  28  8  7  6  266
Costura
5
6
7
8
9
Como no item anterior, poderemos gerar uma nova animação para
visualizar as retas se deslocando paralelamente em direção ao ponto (8, 6)
de solução ótima. Concluímos que esta solução ótima será novamente
outro ponto do contorno da região poligonal.
Programação Linear: a técnica mais importante da Pesquisa Operacional - 7
c) Quantos vestidos e camisetas deverá produzir no intervalo de 6
minutos se os lucros respectivos por unidade de cada produto são R$
21,00 e R$ 7,00?
Analogamente,
obtemos a família de retas da função objetivo
modificando-se apenas o lucro unitário dos vestidos para R$ 21:
F  21x  7y  y 
F
 3x
7
Devemos agora obter algumas retas substituindo-se F por valores
Além de paralelas entre si, estas retas
específicos:
deverão ser paralelas à reta do corte, pois a
70
 3x
7
105
F  105  y 
 3x
7
140
F  140  y 
 3x
7
F  70  y 
equação desta é 3x + y = 30
 y = 30 − 3x. Logo, as retas F têm o
mesmo coeficiente angular m = −3 que a
reta do corte.
O gráfico ficará:
24
Veja agora que as retas objetivo serão
camisetas
22
paralelas à reta do corte. Assim, para um
20
valor específico de F, a reta pontilhada
18
16
passará sobre a reta corte e, para um valor
corte
14
infinitesimalmente superior de F, a reta
12
pontilhada deixará de fazer intersecção com a
10
F = 140
F = 105
8
poligonal. Desta forma, todos os pontos do
6
corte entre x = 3 e x = 8 serão soluções
4
ótimas deste problema.
2
F = 70
1
2
3
4
5
6
7
-2
8
9
10
vestidos
A figura anterior indica que teremos múltiplas soluções para o problema,
isto é, todos os pontos localizados sobre a reta corte de x = 3 a x = 8
serão soluções ótimas. Para encontrar os pontos ótimos que indicarão
soluções inteiras, basta fazer x = 3, 4, 5, 6, 7 e 8 sobre a reta de corte:
reta corte: y  30  3x
x  3  y  30  3  3  21
x  4  y  30  3  4  18
x  5  y  30  3  5  15
x  6  y  30  3  6  12
x  7  y  30  3  7  9
x  8  y  30  3  8  6
Para encontrar o valor de F correspondente aos pontos ótimos,
substituímos as coordenadas de qualquer um ponto ótimo na função
objetivo:
F  21x  7y
(3,7)  F  21 3  7  21  210
(7,9)  F  21 7  7  9  210
Programação Linear: a técnica mais importante da Pesquisa Operacional - 8
Desta forma, podemos traçar a reta objetivo com F = 210 e igualmente
marcar os pontos obtidos. Assim, todos estes serão soluções ótimas do
problema, o que nos faz concluir que este problema de PL terá soluções
múltiplas:
24
camisetas
(3, 21)
22
20
Apesar de o segmento do corte conter
infinitos pontos, o problema em questão se
(4, 18)
(5, 15)
16
14
interessa apenas pelas soluções inteiras que
12
são os 6 pontos destacados no gráfico ao
10
lado.
F = 210
18
4
(7, 9)
F = 105
8
6
(6, 12)
F = 140
(8, 6)
F = 70
2
1
2
3
4
5
6
7
-2
8
9
10
vestidos
Podemos reconhecer que um problema de PL com duas
variáveis apresentará soluções múltiplas quando a função objetivo F for
uma combinação linear de alguma restrição. No exemplo anterior, a
formulação exata será:
maximizar F  21x  7y
Alinhamos os coeficientes de x e de y nas
sujeito a
restrições e também na função objetivo,
além de destacarmos os coeficientes
 3x  1y  30

6x  1y  54
1x  1y  24

unitários para maior clareza.
Veja como os coeficientes da função objetivo serão iguais ao da restrição
corte multiplicados por 7. Assim, a solução ótima será todo o lado da
Podemos generalizar, com algumas
poligonal relacionada a esta restrição. Isso porque as famílias de retas F
adaptações, este resultado para problemas
serão paralelas entre si e também paralelas à reta do corte.
de PL com mais de 2 variáveis, o que torna
os problemas com soluções múltiplas
facilmente identificáveis.
Como nos itens anteriores, poderemos gerar uma interessante
animação para visualizar que o segmento do corte é a solução múltipla
deste problema de PL:
Para tanto, defina F = 0 no recurso Funções
Otimizadas (tecla F6 ou ícone f(t)). Em
seguida, adicione a função "F/7−3x" e clique
sobre Calc >> animação e parametrize a
caixa como segue:
Se prefirir, salve o vídeo para que o mesmo possa ser exibido no
Windows quando desejar.
Programação Linear: a técnica mais importante da Pesquisa Operacional - 9
EXERCÍCIOS
Dica 12: observe como a região poligonal
12) Utilizando os recursos do programa Graph®, gráficos e animações, e
definida pelas restrições será a mesma para
também habilidades algébricas, obtenha as soluções inteiras dos
os três itens.
seguintes problemas de PL:
a)
b)
c)
max F  4x  y
max F  2x  2y
max F  2x  5y
x  y  30

sujeito a x  2y  42
x  3y  54

x  y  30

sujeito a x  2y  42
x  3y  54

x  y  30

sujeito a x  2y  42
x  3y  54

Dica 13: a variável x é a quantidade de
13) Considerando o problema da confecção de camisetas e calças,
camisetas, y é a de calças a serem
inicialmente resolvido no exercício 2 e posteriormente modelado no
produzidas por dia para otimizar o lucro total.
exercício 6 como:
maximizar F  8x  13y
sujeito a

x  156

y  90
 x
y


1
 300 250
a) Represente a região poligonal de restrições usando o programa Graph.
b) Resolva graficamente e compare a solução obtida com o resultado do
exercício 2.
Dica 14: a variável x é a quantidade de
embalagens de 5 kg a serem usadas e y é a
14) Considerando o problema do comerciante de ração inicialmente
de 18 kg para embalar 1.000 kg de ração e
resolvido no exercício 3 e, em seguida, modelado no exercício 7 como:
proporcionar o máximo lucro.
maximizar F  4x  15y
sujeito a
 x  60

 y  40
5x  18y  1000

a) Represente a região de restrições usando o programa Graph. Por que
motivos, esta será apenas um segmento de reta?
b) Resolva graficamente e compare a solução obtida com o resultado do
exercício 3.
Dica 15: a variável x é a quantidade de
aviõezinhos de madeira, y é a de aço a serem
15) Retomando agora o exercício 8 da fábrica de aviõezinhos, utilize a
produzidas por hora com o objetivo de
modelagem obtida:
maximizar o lucro total obtido.
maximizar F  3x  5y
sujeito a
 x  2y  30

2x  4y  40

 x  10
y  6

e o programa Graph para obter a solução ótima.
16) Explique o motivo pelo qual não podemos usar o programa Graph para
resolver o problema do sacolão, inicialmente desenvolvido neste capítulo.
Programação Linear: a técnica mais importante da Pesquisa Operacional - 10
17) Utilizando os recursos do programa Graph® e também habilidades
algébricas, obtenha as soluções dos seguintes problemas de PL:
a)
C
c)
min F  x  4y
min F  x  2y
x  200

sujeito a y  150
x  3y  450

x  200

sujeito a y  150
x  3y  900

 x  200

sujeito a  y  150
 x  3y  900

18) O polígono fechado ABCDE refere-se à região de restrições de um
D
problema de PL que objetiva minimizar o custo total onde os custos
unitários são, para x e y, respectivamente iguais a R$ 300 e a R$ 350.
B
CUS
TO
=
Qualquer ponto da diagonal BE apresenta custo de R$ 155 mil.
155
.00
a) Qual o será o ponto ótimo?
0,
E
A
50
b)
min F  x  4y
b) Encontre as coordenadas deste ponto e o custo ótimo associado,
100 150 200 250 300 350 400 450
sabendo-se que as escalas em x e y não são necessariamente iguais.
O enunciado a seguir refere-se às questões de 19 a 21. Considere a
região poligonal definida por:
Ay
B
2x  y  140

 4x  y  150
9x  y  280

C
19) Associe cada um dos lados AB, BC e CD a cada uma das restrições
dadas e, em seguida, encontre os seus vértices A, B, C, D e E.
x
E
D
20) Considerando-se a região poligonal como as restrições de um
problema de maximização de PL, qual das funções objetivos seguintes
não apresentará soluções múltiplas e por quê?
a) F = 4x + 2y
b) F = 20x + 5y
c) F = 27x + 3y
d) F = 2x + 3y
21) Para a função objetivo que é a resposta do exercício anterior, mostre
Dica 21: (arte da capa) esta figura caracteriza
que os valores de F para cada um dos pontos vértices da região poligonal
definitivamente a função F como função de
são exibidos na figura seguinte:
duas variáveis, x e y, e seu gráfico é exibido
z
ao lado bem como ilustrado na capa deste
420
livro. Trata-se de uma parte do plano no
400
espaço tridimensional que é imagem da
região poligonal definida pelas restrições no
plano xy. O trabalho deste exercício se
resume assim ao cálculo numérico da função
y
190
A
poligonal e conferência com os valores
B
F em cada um dos pontos vértices da região
exibidos no gráfico. Assim, o ponto A
C
definido por x = 0 e y = 140 é aquele que
F = 2x + 3y
E
pontos da região poligonal dada.
62
D
maximiza a função F = 2x + 3y para os
x
Programação Linear: a técnica mais importante da Pesquisa Operacional - 11
EXERCÍCIOS AVANÇADOS
22) Um feirante precisa vender em sua barraca um mínimo de 100 dúzias
y
360
320
280
240
200
160
120
80
40
de maçãs e um mínimo de 120 dúzias de peras e um total de 300 dúzias
das duas frutas juntas. Seu objetivo é o de minimizar o custo total na
aquisição destas duas frutas.
a) Mostre a região de restrições graficamente.
b) Se a solução ótima apontou 200 dúzias de peras e 100 de maçãs,
x
50
100 150 200 250 300
mostre algebricamente que o custo da dúzia de maçãs é maior ou igual ao
custo da dúzia de peras.
23) Considere o seguinte problema de PL:
y
maximizar F  ux  vy
200
160
120
sujeito a
B
80
y
 x

1

 150 200
 x  3y  300

C
40
D
A
50
100
A região poligonal ABCD das restrições encontra-se pintada no gráfico ao
x
150
lado. Qual deverá ser a relação entre u e v para que:
a) o ponto B seja a solução ótima do problema?
b) o segmento BC seja a solução ótima do problema (soluções múltiplas)?
c) o ponto C seja a solução ótima do problema?
d) o segmento CD seja a solução ótima do problema (soluções múltiplas)?
e) o ponto D seja a solução ótima do problema?
24) A região poligonal aberta desenhada ao lado refere-se às restrições de
um problema de PL.
y
150
a) Encontre as equações destas restrições.
120
b) Considerando a função objetivo como:
90
A
60
minimizar F  ux  vy
B
30
x
50
100
150
200
encontre a relação entre os coeficientes u e v para que o vértice A seja a
solução ótima única, o segmento AB seja a solução ótima (múltipla) e o
ponto B seja a solução ótima única deste problema de PL.
25) A região poligonal fechada desenhada ao lado refere-se às restrições
y
de um problema de PL.
150
120
C
a) Encontre as inequações destas restrições.
B
D
b) Considerando a função objetivo como:
90
60
maximizar F  ux  vy
30
A
E
50
100
150
x
200
encontre a relação entre os coeficientes u e v para que cada um dos
vértices seja a solução ótima do problema.
.
Programação Linear: a técnica mais importante da Pesquisa Operacional - 12
Visite o site e conheça melhor estes e outros livros didáticos.
www.pagina10.com.br