Capítulo

PROGRAMAÇÃO LINEAR

Muitas decisões importantes enfrentadas por um gerente de negócios concentram-se na melhor

maneira de alcançar os objetivos da empresa, sujeito às restrições impostas ao

gerente pelo ambiente operacional. Essas restrições podem tomar a forma de
recursos limitados, como tempo, trabalho, energia, material ou dinheiro; ou eles podem ser
na forma de diretrizes restritivas, como uma receita para fazer cereal ou
especificações de engenharia. Um dos objetivos mais frequentes das empresas
é obter o maior lucro possível ou, em outras palavras, maximizar o lucro. O
objetivo de unidades organizacionais individuais dentro de uma empresa (como uma produção ou
O departamento de embalagem geralmente tem como objetivo minimizar custos. Quando um gerente tenta

resolver um tipo geral de problema buscando um objetivo que está sujeito a

restrições, a técnica de ciência da gestão chamada programação linear é
frequentemente usado. Ele tem dois tipos, o modelo de maximização e o modelo de minimização.

Existem três etapas na aplicação da técnica de programação linear. Primeiro,

o problema deve ser identificado como sendo solucionável por programação linear. Segundo,
o problema não estruturado deve ser formulado como um modelo matemático. Terceiro, o
o modelo deve ser resolvido utilizando técnicas matemáticas estabelecidas. O linear
a técnica de programação deriva seu nome do fato de que o funcional
as relações no modelo matemático são lineares e a técnica de solução
consiste em passos matemáticos pré-determinados—isto é, um programa. Neste capítulo
nos preocuparemos com a formulação do modelo matemático que
representa o problema e depois resolve este modelo usando um gráfico.
Objetivos Gerais:

Ao final do capítulo, você deverá ser capaz de:

1. apreciar o uso e aplicação da programação linear na tomada de decisão

fazendo;
2. formular modelo na resolução de problemas empresariais especialmente em

maximização e minimização dos recursos empresariais; e

 3. apreciar o uso de gráficos na resolução de problemas de tomada de decisão.

Aula 1: Modelo de Maximização

Um modelo de programação linear consiste em certos componentes comuns e

características. Os componentes do modelo incluem variáveis de decisão, um objetivo
função e restrições do modelo, que consistem em variáveis de decisão e
parâmetros. Variáveis de decisão são símbolos matemáticos que representam níveis de
atividade pela empresa. Por exemplo, uma empresa de fabricação de equipamentos elétricos deseja

produzir rádios, torradeiras e relógios, onde, e são símbolos que representam

quantidades de cada item desconhecidas. Os valores finais de, e, conforme determinado
pela empresa, constituem uma decisão (por exemplo, a equação de rádios é uma decisão da empresa
para produzir 100 rádios).

At the end of the lesson, you should be able to:

1. enumerar os componentes do modelo de programação linear;
2. aplicar modelo de maximização em problema de tomada de decisão;

3. formular programação linear de maximização; e

4. formule um modelo matemático usando um gráfico.

A função objetivo é uma relação matemática linear que descreve

o objetivo da empresa em termos das variáveis de decisão. A função objetivo
sempre consiste em maximizar ou minimizar algum valor (por exemplo, maximizar o
lucro ou minimizar o custo de produção de rádios.
As restrições do modelo também são relacionamentos lineares das variáveis de decisão;
eles representam as restrições colocadas na empresa pelo ambiente operacional.
As restrições podem estar na forma de recursos limitados ou diretrizes restritivas.
Por exemplo, apenas 40 horas de trabalho podem estar disponíveis para produzir rádios durante

produção. Os valores numéricos reais na função objetivo e nas restrições,

como as 40 horas de trabalho disponíveis, são parâmetros.
A próxima seção apresenta um exemplo de como um modelo de programação linear
é formulada. Embora este exemplo seja simplificado, é realista e representa o
tipo de problema ao qual a programação linear pode ser aplicada. No exemplo, o
os componentes do modelo são identificados e descritos de forma distinta. Ao estudar cuidadosamente

neste exemplo, você pode se familiarizar com o processo de formular linear

modelos de programação.

Modelo de Maximização
A Beaver Creek Pottery Company é uma pequena operação artesanal administrada por um nativo.

Conselho tribal americano. A empresa emprega artesãos habilidosos para produzir argila
tigelas e canecas com designs e cores autênticas de nativos americanos. Os dois
Os recursos primários utilizados pela empresa são argila de cerâmica especial e mão de obra qualificada.

Given these limited resources, the company desires to know how many bowls and
canecas a produzir a cada dia para maximizar o lucro. Isso é geralmente referido como
como um tipo de problema de mix de produtos. Este cenário é ilustrado na Figura 2.1.
 Os dois produtos têm os seguintes requisitos de recursos para produção
e lucro por item produzido (ou seja, os parâmetros do modelo):
Requisitos de Recursos
Produto Trabalho Argila Lucro
(hr./unidade) (lb./unidade) (por unidade)
Tigela 1 4 40
Caneca 2 3 50

Existem 40 horas de trabalho e 120 libras de argila disponíveis a cada dia para
produção. Vamos formular este problema como um modelo de programação linear por
definindo cada componente do modelo separadamente e depois combinando os
componentes em um único modelo. Os passos neste processo de formulação são
resumido da seguinte forma:

Resumo das Etapas de Formulação do Modelo de LP

Passo 1: Defina as variáveis de decisão

Quantas tigelas e canecas produzir
Passo 2: Defina a função objetivo
Maximizar o lucro
Passo 3: Defina as restrições
Os recursos (argila e mão de obra) disponíveis

Variáveis de Decisão
A decisão que a administração enfrenta neste problema é quantas tigelas.
e canecas a produzir. As duas variáveis de decisão representam o número de tigelas
e canecas a serem produzidas diariamente. As quantidades a serem produzidas podem ser
representado simbolicamente como

1=

2=
A Função Objetivo
O objetivo da empresa é maximizar o lucro total. A empresa
o lucro é a soma dos lucros individuais obtidos de cada tigela e caneca. Lucro
o lucro derivado de tigelas é determinado multiplicando-se o lucro unitário de cada tigela, $40,

pelo número de tigelas produzidas, 1Da mesma forma, o lucro proveniente de canecas é derivado

do lucro unitário de uma caneca, $50, multiplicado pelo número de canecas

produzido 2 Assim, o lucro total, que iremos definir simbolicamente como Z, pode ser
expresso matematicamente como$40x1+ $50x2Ao colocar o termo maximizar em
na frente da função de lucro, expressamos o objetivo da firma—maximizar o total
profit:
= $40 1+ $50x2
onde
Z = lucro total por dia
$40x1lucro com tigelas
$50x2lucro com canecas
Restrições do Modelo
Neste problema, dois recursos são utilizados para a produção—mão de obra e argila—ambos de
que são limitados. A produção de tigelas e canecas requer tanto mão de obra quanto argila. Para

cada tigela produzida, 1 hora de trabalho é necessária. Portanto, o trabalho utilizado para o

a produção de tigelas é1 1 horas. Da mesma forma, cada caneca requer 2 horas de trabalho;
assim, o trabalho utilizado para produzir canecas todos os dias é2 2 horas. O total de trabalho utilizado

pela empresa é a soma dos valores individuais de trabalho utilizados para cada um
product:
1 1+ 2 2

No entanto, a quantidade de trabalho representada é limitada a 40 horas por dia;

assim, a restrição completa de trabalho é
1 1+ 2 2≤ 40 hr
A desigualdade "menor ou igual a" (≤) é empregada em vez de uma igualdade
porque as 40 horas de trabalho são uma limitação máxima que pode ser utilizada, não um
quantidade que deve ser utilizada. Esta restrição permite à empresa alguma flexibilidade; o
a empresa não está restrita a usar exatamente 40 horas, mas pode usar a quantidade que quiser
é necessário maximizar o lucro, até um máximo de 40 horas. Isso significa que é
possível ter capacidade ociosa ou em excesso (ou seja, algumas das 40 horas podem não ser)
usado).
A restrição para a argila é formulada da mesma forma que a restrição de trabalho.
Como cada tigela requer 4 libras de argila, a quantidade de argila usada diariamente para

a produção de tigelas é4x1 libras; e porque cada caneca requer 3 libras

de argila, a quantidade de argila utilizada diariamente para canecas é3x2 . Dado que a quantidade de
A argila disponível para produção a cada dia é de 120 libras, a restrição de material pode
ser formulado como
4x1+ 3x2≤ 120 lb
Uma restrição final é que o número de tigelas e canecas produzidas deve ser
ou zero ou um valor positivo, pois é impossível produzir itens negativos.
Essas restrições são chamadas de restrições de não negatividade e são expressas
matematicamente como

1≥ 0, x2≥ 0
O modelo de programação linear completo para este problema pode agora ser
resumido da seguinte forma:

maximize Z = $40x1+ $50x2

Sujeito a
1 1+ 2 2≤ 40
4x1 + 3x2≤ 120
1, 2≥ 0
A solução deste modelo resultará em valores numéricos para e que irão
maximizar o lucro total, Z. Como uma possível solução, considere 1= 5tigelas e 2=

10mugs. First, we will substitute this hypothetical solution into each of the
restrições para garantir que a solução não exija mais recursos
do que as restrições mostram estão disponíveis:

1 5( )+ 2(10) ≤ 40
25 ≤ 40
e
4 ( 5+
) 3(10) ≤ 120
 50 ≤ 120
Como nenhuma das restrições é violada por esta solução hipotética, dizemos
a solução é viável (ou seja, possível). Substituindo esses valores de solução no
a função objetivo dá Z = 40 (5) + 50 (10) = $700. No entanto, por enquanto,
não temos como saber se $700 é o lucro máximo.
Agora considere uma solução de 1= 10tigelas e 2= 20canecas. Esta solução
resulta em um lucro de
Z = $4010( +$50(20)
)
= 400 +1,000
= $1400
Embora esta seja certamente uma solução melhor em termos de lucro, é inviável.
(ou seja, não é possível) porque viola a restrição de recursos para mão de obra:
1 (10 ) + 2 (20 ) ≤ 40
50 ≤ 40
A solução para este problema deve maximizar o lucro sem violar o
restrições. A solução que alcança este objetivo é 1= 24 tigelas e 2= 8
canecas, com um lucro correspondente de $1.360. A determinação desta solução é
mostrado usando a abordagem de solução gráfica na seção seguinte.
Soluções Gráficas de Modelos de Programação Linear
Após a formulação de um modelo matemático, a próxima etapa na
a aplicação da programação linear a um problema de tomada de decisão é encontrar o
solução do modelo. Uma abordagem comum para a solução é resolver algébricamente o
conjunto de relações matemáticas que formam o modelo manualmente ou usando um
programa de computador, assim determinando os valores para as variáveis de decisão.
No entanto, como os relacionamentos são lineares, alguns modelos e soluções podem ser
ilustrado graficamente.
O método gráfico é realisticamente limitado a modelos com apenas duas decisões
variáveis, que podem ser representadas em um gráfico de duas dimensões. Modelos com
três variáveis de decisão podem ser graphadas em três dimensões, mas o processo é
bastante complicado, e modelos com quatro ou mais variáveis de decisão não podem ser

gráfico de tudo.
 Embora o método gráfico seja limitado como uma abordagem de solução, é muito
útil neste momento da nossa apresentação sobre programação linear, pois fornece um
imagem de como uma solução é derivada. Gráficos podem fornecer uma compreensão mais clara
de como as abordagens de solução computacional e matemática apresentadas em
os capítulos subsequentes funcionam e, assim, uma melhor compreensão das soluções.

Solução Gráfica de um Modelo de Maximização

O modelo de mix de produtos será usado para demonstrar o gráfico
interpretação de um problema de programação linear. Lembre-se de que o problema descreve
A tentativa da Beaver Creek Pottery Company de decidir quantas tigelas e canecas produzir
produzir diariamente, dado quantidades limitadas de trabalho e argila.

O modelo completo de programação linear foi formulado como

= $40 1+ $50 2

Sujeito a
1 1+ 2 2≤ 40 ℎ
4x1+ 3x2 ≤ 120lb de argila

1, 2≥ 0
onde
1=

2=

A figura 2.2 é um conjunto de coordenadas para as variáveis de decisão e, sobre o qual o gráfico
do nosso modelo será desenhado. Observe que apenas o quadrante positivo é desenhado (ou seja, o

quadrante onde 1, 2sempre será positivo) devido à não negatividade

restrições 1≥ 0 2≥ 0.
 O primeiro passo para desenhar o gráfico do modelo é plotar as restrições em
o gráfico. Isso é feito tratando ambas as restrições como equações (ou linhas retas)
e plotando cada linha no gráfico. Vamos considerar a linha da restrição de trabalho primeiro:

1+ 2 2= 40
Um procedimento simples para traçar esta linha é determinar dois pontos que estão
na linha e então desenhe uma linha reta através dos pontos. Um ponto pode ser encontrado
por deixar e resolver para 2:

0 +2 2= 40

2= 20
Assim, um ponto está nas coordenadas 1= 0 e x2= 20Um segundo ponto
pode ser encontrado ao deixar 2= 0e resolvendo para 1:

1+ 2(0) = 40

1= 40
Agora temos um segundo ponto, 1= 40, 2= 0A linha no gráfico
representando esta equação é desenhado conectando esses dois pontos, como mostrado em
Figura 2.3. No entanto, este é apenas o gráfico da linha de restrição e não reflete
a restrição inteira, que também inclui os valores que são menores ou iguais a
(≤) esta linha. A representação de toda a restrição é mostrada na Figura 2.4.
 Para testar a correção da área da restrição, verificamos quaisquer dois pontos—
um dentro da área de restrição e um fora. Por exemplo, verifique o ponto A em
Figura 2.4, que está na interseção de 1= 10, e x2= 10Substituindo estes
valores na seguinte restrição laboral,
10 + 2(10) ≤ 40
30 ≤40 h
mostra que o ponto A está de fato dentro da área de restrição, uma vez que esses valores

para 1 2gerar uma quantidade que não exceda o limite de 40 horas. Em seguida, nós
verifique o ponto B em e 1= 40 e x2 =30:

40 +2(30) ≤ 40
 100 ≤ 40 hr

O ponto B está obviamente fora da área de restrição porque os valores para

1 2produzir uma quantidade (100) que excede o limite de 40 horas.
Nós traçamos a linha para a restrição de argila da mesma forma que a para o
restrição de trabalho—encontrando dois pontos na linha de restrição e conectando-os
com uma linha reta. Primeiro, deixe 1= 0 e resolva para x2:
40 (0 ) +3 x2= 120

2= 40
Realizar esta operação resulta em um ponto, 1= 0, 2= 40. Em seguida, nós

, 2= 0e então resolver para 1:

40 x1+ 3(0)= 120

1= 30

Combinando os dois gráficos individuais para tanto trabalho quanto argila (Figuras 2.4 e 2.5)
produz um gráfico das restrições do modelo, como mostrado na Figura 2.6. A sombreada
a área na Figura 2.6 é a área que é comum a ambas as restrições do modelo. Portanto,
 esta é a única área no gráfico que contém pontos (ou seja, valores para 1 2)

que satisfará ambas as restrições simultaneamente. Por exemplo, considere os pontos

R, S e T na Figura 2.7. O ponto R satisfaz ambas as restrições; assim, dizemos que é um
ponto de solução viável. O ponto S satisfaz a restrição de argila, mas excede a mão de obra
restrição; assim, é inviável. O ponto T não satisfaz nenhuma restrição; assim, também é
inviável.
A área sombreada na Figura 2.7 é referida como a área de solução viável
porque todos os pontos nesta área satisfazem ambas as restrições. Algum ponto dentro deste
a área de solução viável resultará em máximo lucro para a Cerâmica Beaver Creek
Empresa. O próximo passo na abordagem de solução gráfica é localizar este ponto.

A área da solução viável é

uma área no gráfico que é
limitado pela restrição
equações
The Optimal Solution Point
O segundo passo no método de solução gráfica é localizar o ponto em
a área de solução viável que resultará no maior lucro total. Para começar a
análise da solução, primeiro plotamos a linha da função objetivo para uma seleção arbitrária
nível de lucro. Por exemplo, se dissermos que o lucro, Z, é de $800, a função objetivo é
$800 = 40 1+ 50 2

Plotar esta linha assim como plotamos as linhas de restrição resulta no gráfico
mostrado na Figura 2.8. Cada ponto nesta linha está na área de solução viável e irá
resultar em um lucro de $800 (ou seja, cada combinação de 1 2nesta linha dará
um valor Z de $800). No entanto, vamos ver se um lucro ainda maior será
forneça uma solução viável. Por exemplo, considere lucros de $1.200 e $1.600, como
mostrado na Figura 2.9.
Uma parte da linha da função objetivo para um lucro de $1.200 está fora do
área de solução viável, mas parte da linha permanece dentro da área viável.
Portanto, esta linha de lucro indica que existem pontos de solução viáveis que fornecem
um lucro superior a $800. Agora vamos aumentar o lucro novamente, para $1.600. Este lucro
a linha, também mostrada na Figura 2.9, está completamente fora da área de solução viável. O
o fato de que nenhum ponto nesta linha é viável indica que um lucro de $1.600 não é
possível.
 Porque um lucro de $1.600 é muito grande para as limitações da restrição, já que
mostrado na Figura 2.9, a questão do valor máximo do lucro permanece. Podemos
veja na Figura 2.9 que o lucro aumenta à medida que a linha da função objetivo se afasta
do ponto de origem (ou seja, o ponto 1= 0, 2= 0). Dada essa característica, o
o lucro máximo será alcançado no ponto onde a linha da função objetivo é
mais distante da origem e ainda tocando um ponto na área da solução viável.
Este ponto é mostrado como ponto B na Figura 2.10.
Para encontrar o ponto B, colocamos uma régua paralela à função objetivo.
linha$800 = 40 x1+ 50 2 na Figura 2.10 e mova-o para fora da origem o mais longe possível
como podemos sem perder o contato com a área de solução viável. O ponto B é referido
como a solução otimizada (ou seja, a melhor).

Os Valores da Solução
O terceiro passo na abordagem de solução gráfica é resolver os valores
de 1 2uma vez que o ponto de solução ótimo foi encontrado. É possível
determinar o 1 2coordenadas do ponto B na Figura 2.10 diretamente do
gráfico, conforme mostrado na Figura 2.11. As coordenadas gráficas correspondentes ao ponto

B na Figura 2.11 são 1= 24 e 2= 8Esta é a solução optimal para o

decisão
variáveis no problema. No entanto, a menos que um gráfico absolutamente preciso seja desenhado,

é frequentemente difícil determinar a solução correta diretamente do gráfico. A

uma abordagem mais exata é determinar os valores da solução matematicamente uma vez que
o ponto ótimo no gráfico foi determinado. A abordagem matemática para
a determinação da solução é descrita nas páginas seguintes. Primeiro, no entanto, nós vamos
considere algumas características da solução.
Na Figura 2.10, à medida que a função objetiva foi aumentada, o último ponto que ela
tocado na área de solução viável estava na fronteira da solução viável
área. O ponto de solução está sempre nesta fronteira porque a fronteira contém
os pontos mais distantes da origem (ou seja, os pontos correspondentes ao maior
lucro). Essa característica dos problemas de programação linear reduz o número de
pontos de solução possíveis consideravelmente, de todos os pontos na área da solução para apenas

esses pontos na fronteira. No entanto, o número de possíveis pontos de solução é

reduzido ainda mais por outra característica dos problemas de programação linear.
O ponto de solução estará na fronteira da área de solução viável e
em um dos cantos do limite onde duas linhas de restrição se intersectam. (O
graphical axes, you will recall, are also constraints because 1≥ 0e 2≥ 0).
Esses cantos (pontos A, B e C na Figura 2.11) são protuberâncias, ou extremos, em
a área da solução viável; eles são chamados de pontos extremos. Foi provado
matematicamente que a solução ótima em um modelo de programação linear será sempre
ocorre em um ponto extremo. Portanto, em nosso problema de amostra, a solução possível
os pontos são limitados aos três pontos extremos, A, B e C. O extremo ótimo
o ponto é o ponto extremo que a função objetivo toca por último ao sair do
área de solução viável, conforme mostrado na Figura 2.10.

Do gráfico mostrado na Figura 2.10, sabemos que a solução ótima

o ponto é B. Porque o ponto B é formado pela interseção de duas linhas de restrição, conforme
como mostrado na Figura 2.11, essas duas linhas são iguais no ponto B. Assim, os valores de e
at that intersection can be found by solving the two equationssimultaneously.
Primeiro, convertemos ambas as equações em funções de 1:

1+ 2 2= 40

1= 40 −2 2

e
 4x1 + 3x2= 120
4x1= 120 − 3x2

1= 30 - 3 2 /4

Agora, deixamos 1na primeira equação igual 1na segunda equação

40 -2 2= 30 − 3x2 /4
e resolver para 2:

5x2 /4 =10

2= 8
Substituindo 2= 8 em uma das equações originais dado um valor
para 1 :

1= 40 −2 2

1= 40 −2(8)

1= 24
Assim, a solução ótima no ponto B da Figura 2.11 é 1= 24 a e x2= 8.
Substituir esses valores na função objetivo resulta no lucro máximo,
Z = 40 x1+ 50 2

Z = 40(24) +50(8)
Z = $1,360
Em termos do problema original, a solução indica que se a cerâmica
company produces 24 bowls and 8 mugs, it will receive $1,360, the maximum daily
lucro possível (dadas as limitações de recursos).
Dado que a solução ótima estará em um dos pontos extremos.
A, B ou C, também podemos encontrar a solução testando cada um dos três pontos para ver
que resulta no maior lucro, em vez de graficar a função objetivo
e vendo qual ponto ele toca por último ao sair da área de solução viável.
A Figura 2.12 mostra os valores de solução para os três pontos, A, B e C, e o
montante do lucro, Z, em cada ponto.
Conforme indicado na discussão da Figura 2.10, o ponto B é a solução ótima
ponto porque é o último ponto que a função objetivo toca antes de sair
área de solução. Em outras palavras, a função objetiva determina qual extremo
o ponto é ótimo. Isso porque a função objetivo designa o lucro que
acumulará de cada combinação de 1 2valores nos pontos extremos. Se
a função objetivo tinha coeficientes diferentes (ou seja, diferentes 1 2lucro

valores), um dos pontos extremos além de x B poderia ter sido ótimo.

Vamos supor por um momento que o lucro por tigela é de $70 em vez de $40,
e o lucro por caneca é de $20 em vez de $50. Esses valores resultam em um novo
função objetivoZ = 70 x1+ 20 x2 Se as restrições do modelo para trabalho ou argila são
não mudou, a área de solução viável permanece a mesma, como mostrado na Figura 2.13.
No entanto, a localização da função objetivo na Figura 2.13 é diferente daquela
da função Objetivo original na Figura 2.10. A razão para esta mudança é que
os novos coeficientes de lucro dão à função objetiva linear uma nova inclinação.
 A inclinação pode ser determinada transformando a função objetivo em
equação geral para uma linha retay = a + bx, onde y é a variável dependente,
ais a intersecção com o eixo y, bis a inclinação, e xis é a variável independente. Para nossa amostra

função objetivo, 2é a variável dependente correspondente ao brinquedo (ou seja, está na

eixo vertical), e 1é a variável independente. Assim, a função objetivo pode
se transforme na equação geral de uma linha da seguinte forma:
Z = 70 x1+ 20 x2
20 x2= Z − 70 x1

Esta transformação identifica a inclinação da nova função objetivo como

-7/2(o sinal de menos indica que a linha inclina-se para baixo). Em contraste, o
a inclinação da função objetivo original era-4/5.
Se movermos esta nova função objetivo para fora da área de solução viável,
o último ponto extremo que toca é o ponto C. Resolver a restrição simultaneamente
as linhas no ponto C resultam na seguinte solução:
1= 30
4x1 + 3x2= 120
e

2 = 40 − ( 4x1 /3)

2= 40 − 4(30)/3)

2= 0
Assim, a solução ótima no ponto C na Figura 2.13 é 1= 30tigelas 2=

0canecas, e = $2,100lucro. Alterar os coeficientes da função objetivo resulta em

uma nova solução.
Este breve ponto. Primeiro, o ponto extremo ótimo é determinado por
função objetivo, e um ponto extremo em um dos eixos do gráfico é tão provável de ser
a solução ótima como está é um ponto extremo em um eixo diferente. Em segundo lugar, a solução
é sensível aos valores dos coeficientes na função objetivo. Se a objetivo
Os coeficientes da função são alterados, como em nosso exemplo, a solução pode mudar.
Da mesma forma, se os coeficientes das restrições forem alterados, o espaço de solução e a solução

os pontos podem mudar também. Esta informação pode ter consequências na decisão
fabricante tentando determinar quanto de um produto [Link]
análise—o uso de programação linear para avaliar os efeitos de mudanças em
parâmetros do modelo.

Deve-se notar que alguns problemas não têm um único ponto extremo
solução. Por exemplo, quando a linha da função objetivo é paralela a uma das
linhas de restrição, um segmento de linha inteiro é limitado por dois pontos de canto adjacentes

que são ótimos; não há um único ponto extremo na linha da função objetivo. Em
nesta situação existem múltiplas soluções ótimas. Este e outros tipos irregulares
dos resultados da solução em programação linear são discutidos no final deste capítulo

Variável de folga
Uma vez que a solução ótima foi encontrada no ponto B na Figura 2.12, simultaneamente
equações foram resolvidas para determinar os valores de 1 2. Lembre-se de que o
a solução ocorre em um ponto extremo onde as linhas da equação de restrição se intersectam com
um ao outro ou com o eixo. Assim, as restrições do modelo são consideradas como
equações (=) em vez de desigualdades ≤ ou ≥.
Há um procedimento padrão para transformar restrições de desigualdade ≤ em
equações. Essa transformação é alcançada adicionando uma nova variável, chamada de uma
variável de folga, para cada restrição.
Para o exemplo da empresa de cerâmica, as restrições do modelo são

1+ 2 2≤ 40 h .

1+ 3x2≤ 120 lb. de barro

A adição de uma variável de folga única, 1, à restrição de mão de obra e 2para

a restrição para a argila resulta nas seguintes equações:

1+ 2 2+ 1= 40 hr. pôr de laboratório

4 x1+ 3x2+ 2= 120lb. pote de argila

 As variáveis de folga nessas equações, 1 2, assumirá qualquer valor
necessary to make the left-hand side of the equation equal to the right-hand side.
Por exemplo, considere uma solução hipotética de 1= 5e 2= 10Substituindo
esses valores nas equações anteriores resultam em
1+ 2 2+ 1= 40ℎ .
5 +2(10) + 1= 40ℎ .

1= 15 ℎ .
e
4x1+ 3x2+ 2 = 120 lb. pó de argila
5 ( 5+
)( 3)10 + 2= 120 lb. pó de argila

2= 70 .
Neste exemplo, 1= 5tigelas e 2= 10canecas representam uma solução que
não faz uso da quantidade total disponível de trabalho e argila. No trabalho
restrição, 5 tigelas e 10 canecas requerem apenas 25 horas de trabalho. Isso deixa 15
horas que não são utilizadas. Assim, 1representa a quantidade de trabalho não utilizado, ou folga.

Na restrição de argila, 5 tigelas e 10 canecas requerem apenas 50 libras de argila.

Isso deixa 70 libras de argila não utilizadas. Assim, 2representa a quantidade de não utilizado

argila. Em geral, variáveis folgadas representam a quantidade de recursos não utilizados.

A instância definitiva de recursos não utilizados ocorre na origem, onde 1=

0e 2= 0. Substituindo esses valores nas equações resulta em

1+ 2 2+ 1= 40
0 +20 (+ ) s1= 40

1= 400ℎ .
e
4x1+ 3x2+ 2 = 120
4(0) +3(0) + s2= 120

2= 120 lb. de argila

 Como não ocorre produção na origem, todos os recursos são
não utilizado; assim, as variáveis de folga são iguais aos totais disponíveis de cada uma

resource: 1= 40horas de trabalho e 2= 120libras de argila.

Qual é o efeito dessas novas variáveis de folga na função objetivo?
A função objetivo do nosso exemplo representa o lucro obtido a partir do
produção de tigelas e canecas
= 40 1+ 50x2
O coeficiente 40 é a contribuição para o lucro de cada tigela; 50 é o
contribuição para o lucro de cada caneca. O que, então, fazem as variáveis de folga e

contribute? They contributenothingto profit because they represent unused

os recursos. O lucro é gerado apenas depois que os recursos são utilizados na fabricação de tigelas

e canecas. Usando variáveis de folga, podemos escrever a função objetivo como

maximizar (Z) = 40x1+ 50x2+ 0s1+ 0 2

Como no caso das variáveis de decisão ( 1 2 ), as variáveis de folga podem ter

apenas valores não negativos, pois recursos negativos não são possíveis. Portanto,
para esta formulação de modelo 1, 2, 1 2≥ 0.
O modelo completo de programação linear pode ser escrito no que é referido
para a forma padrão com variáveis de folga da seguinte forma:

máximize (Z) = 40x1+ 50x2+ 0s1+ 0 2

Sujeito a
1+ 2 2+ 0s1= 40

4x1+ 3x2+ 2= 120

1, 2, 1 2≥ 0.
Os valores da solução, incluindo a folga em cada ponto de solução, são
resumido da seguinte forma:
 A Figura 2.14 mostra a solução gráfica deste exemplo, com folga
variáveis incluídas em cada ponto de solução

Resumo dos Passos da Solução Gráfica

Os passos para resolver um modelo de programação linear gráfica são
resumido aqui:
1. Plote as restrições do modelo como equações no gráfico; em seguida, considerando
as desigualdades das restrições indicam a área de solução viável.
2. Trace a função objetivo; em seguida, mova essa linha para fora da origem para
localize o ponto de solução ótimo.
3. Resolva as equações simultâneas no ponto de solução para encontrar o ótimo
solution values.
Ou
1. Resolva as equações simultâneas em cada ponto de canto para encontrar a solução
valores em cada ponto.
2. Substitua esses valores na função objetivo para encontrar o conjunto de
valores que resultam no valor máximo de Z
Aula 2: Modelo de Minimização

As mentioned at the beginning of this chapter, there are two types of linear
problemas de programação: problemas de maximização (como a Cerâmica Beaver Creek)
Exemplo de empresa) e problemas de minimização. Um problema de minimização é
formulado da mesma maneira básica que um problema de maximização, exceto por algumas pequenas

diferenças. O seguinte problema de amostra demonstrará a formulação de um

modelo de minimização.
Ao final da lição, você deverá ser capaz de:
1. enumere os componentes do modelo de programação linear;
2. aplicar modelo de minimização em problema de tomada de decisão;

3. formular minimização de programação linear; e

4. formule um modelo matemático usando um gráfico.

Um agricultor está se preparando para plantar uma cultura e precisa fertilizar um campo. Há dois

marcas de fertilizante para escolher, Super-gro e Crop-quick. Cada marca produz um

quantidade específica de nitrogênio e fosfato por saco, conforme abaixo:

O campo do fazendeiro requer pelo menos 16 libras de nitrogênio e pelo menos 24

libras de fosfato. Super-gro custa $6 por saco, e Crop-quick custa $3. O
o fazendeiro quer saber quantas sacas de cada marca comprar para
minimizar o custo total de fertilização. Este cenário é ilustrado na Figura 2.15.
Os passos no processo de formulação do modelo de programação linear são
resumido da seguinte forma:
Variáveis de Decisão
O objetivo do agricultor é minimizar o custo total de fertilização. O total
o custo é a soma dos custos individuais de cada tipo de fertilizante comprado. O
a função objetivo que representa o custo total é expressa como
maximize (Z) = 6x1+ 3x2
onde
6x1= −
3x2= −
Restrições do Modelo

Os requisitos para nitrogênio e fosfato representam as restrições de

o modelo. Cada saco de fertilizante contribui com um número de libras de nitrogênio e
fosfato para o campo. A restrição para o nitrogênio é
2 1+ 4x2≥ 16 lb.
onde
2 1= ℎ ( ) −
4x2= ℎ ( ) −

Em vez de uma desigualdade a≤(menor ou igual a), como usada no Castor

Modelo da Creek Pottery Company, esta restrição exige que a ≥ (maior ou igual a
à) desigualdade. Isso ocorre porque o teor de nitrogênio para o campo é um mínimo
exigência especificando que pelo menos 16 libras de nitrogênio sejam depositadas no
campo do agricultor. Se uma solução de custo mínimo resultar em mais de 16 libras de nitrogênio
em campo, isso é aceitável; no entanto, o valor não pode ser inferior a 16
libras.
A restrição para o fosfato é construída como a restrição para o nitrogênio:
4x1+ 3x2 ≥ 24 lb.
Com este exemplo, mostramos dois dos três tipos de linear
restrições do modelo de programação, ≤ e ≥. O terceiro tipo é uma igualdade exata, =.
tipo especifica que um requisito de restrição deve ser exato. Por exemplo, se o
o agricultor disse que a necessidade de fosfato para o campo era exatamente 24
libras, a restrição teria sido
4x1+ 3x2≥ 24 lb.
Assim como em nosso modelo de maximização, também há restrições de não negatividade em

este problema indica que sacos negativos de fertilizante não podem ser comprados:
1, 2≥ 0
A formulação completa do modelo para este problema de minimização é

maximizar (Z) = 6x1+ 3x2

Sujeito a
 2 1+ 4x2≥ 16 lb. de nitrogênio
4x1+ 3x2≥ 24 lb. de fosfato

1, 2≥ 0

Solução Gráfica de um Modelo de Minimização

Seguimos os mesmos passos básicos na solução gráfica de uma minimização
modelo como em um modelo de maximização. O exemplo do fertilizante será utilizado para

demonstrar a solução gráfica de um modelo de minimização.

 O primeiro passo é graficar as equações das duas restrições do modelo, como
mostrado na Figura 2.16. Em seguida, a área de solução viável é escolhida, para refletir o ≥
desigualdades nas restrições, conforme mostrado na Figura 2.17
.

Depois que a área de solução viável foi determinada, o segundo passo na

A abordagem da solução gráfica é localizar o ponto ótimo. Lembre-se de que em um
problema de maximização, a solução ideal está na fronteira do viável
área de solução que contém o(s) ponto(s) mais distante(s) da origem. A solução ótima
um ponto em um problema de minimização também está na borda da solução viável
área; no entanto, o limite contém o(s) ponto(s) mais próximo(s) da origem (zero sendo
o menor custo possível).
Como em um problema de maximização, a solução ótima está localizada em um dos
pontos extremos da fronteira. Nesse caso, os pontos de canto representam
extremidades na fronteira da área de solução viável que estão mais próximas do
origem. A Figura 2.18 mostra os três pontos de canto — A, B e C — e o objetivo
função linha.
À medida que a função objetivo se aproxima da origem, o último ponto que toca em
o
a área da solução viável é A. Em outras palavras, o ponto A é o mais próximo do objetivo
a função pode chegar à origem sem abranger pontos inviáveis. Assim, ela
corresponde ao menor custo que pode ser alcançado

O passo final na abordagem de solução gráfica é resolver os valores de

e no ponto A. Porque o ponto A está no 2eixo 1= 0;assim,4 0 + 3x( 2=) 24
2= 8
Dado que a solução ótima é 1= 0, 2= 8, o custo mínimo, Z, é
Z = 6x1+ 3x2
Z = 6(0) + 3(8)
Z =$24
Isso significa que o agricultor não deve comprar nenhum Super-gro, mas, em vez disso,

deve comprar oito sacos de Crop-quick, a um custo total de $24.

Variáveis de Excedente

Restrições de maior ou igual não podem ser convertidas em equações por

adicionando variáveis slack, assim como nas restrições. Lembre-se do nosso modelo de fertilizante, formulado

como
maximizar (Z) = 6x1+ 3x2

Sujeito a
2 1+ 4x2≥ 16 lb. de nitrogênio
4x1+ 3x2≥ 24 lb. de fosfato

1, 2≥ 0
onde

1= −

2= −
= ′ ℎ
Porque este problema tem restrições ao invés das restrições do
Exemplo de maximização da Beaver Creek Pottery Company, as restrições são
convertido para equações de uma forma um pouco diferente. Em vez de adicionar uma variável de folga como nós

fez com uma restrição, subtraímos uma variável de excesso. Enquanto uma variável de folga é
adicionados e refletem recursos não utilizados, uma variável de excedente é subtraída e reflete
o excesso acima de um nível mínimo de requisito de recurso. Como uma variável de folga, uma

a variável excedente é representada simbolicamente por e deve ser não negativa. Para o
a restrição de nitrogênio, a subtração de uma variável excedente dá
2 1+ 4x2− 1= 16
A variável excedente transforma a restrição de nitrogênio em uma equação.
Como exemplo, considere a solução hipotética

1= 0

2= 10
Substituir esses valores na equação anterior resulta em
2(0) + 4(10) − 1= 16
− 1= 16 - 40
 − 1= 24 lb. de nitrogênio
Nesta equação, pode ser interpretado como a quantidade extra de nitrogênio acima de

o requisito mínimo de 16 libras que seria obtido ao comprar 10

sacos de fertilizante Crop-quick. De maneira semelhante, a restrição para fosfato é
convertido em uma equação subtraindo uma variável de excedente, 2:

4x1+ 3x2− 2= 24
Como acontece com as variáveis de folga, as variáveis de excedente não contribuem em nada para

o custo geral de um modelo. Por exemplo, adicionar nitrogênio ou fosfato

no campo não afetará o custo do agricultor; a única coisa que afeta o custo é a
número de sacos de fertilizante comprados. Assim, a forma padrão desta linear
o modelo de programação é resumido como
maximize (Z) = 6x1+ 3x2+ 0s1+0 s2
Sujeito a
2 1+ 4x2− 1= 16
4x1+ 3x2− 2= 24

1, 2, 1, 2≥ 0
A Figura 2.19 mostra as soluções gráficas para o nosso exemplo, com variáveis de excedente.
incluído em cada ponto de solução.
Exercícios
1.A Moore’s Meatpacking Company produz uma mistura de cachorro-quente em 1.000 libras

lotes. A mistura contém dois ingredientes - frango e carne bovina. O custo

per pound of each of these ingredients is as follow
Ingredient Cost/lb
Frango Php75
Carne bovina Php125

Cada lote tem os seguintes requisitos de receita:

pelo menos 500 libras de frango
b. Pelo menos 200 libras de carne bovina

A proporção de frango para carne bovina deve ser de pelo menos 2 para 1. A empresa quer ...

conhecer a mistura ótima de ingredientes que minimizará o custo. Formule uma

modelo de programação linear para este problema
2. Resolva o seguinte modelo de programação linear graficamente:
= 4x1+ 5x2
Sujeito a
1+ 2 2≤ 10
6x1 + 6x2≤ 36
1≤ 4
1, 2≥ 0