Unidade II - Introdução à Programação Linear

Prévia do material em texto

Simulação e Tomada 
de Decisão
Material Teórico
Responsável pelo Conteúdo:
Prof. Ms. Roberto Luiz Garcia Vichinsky
Revisão Textual:
Profa. Ms. Fátima Furlan
Introdução à Programação Linear
• Programação Matemática – Conceitos Gerais
• Programação Linear
 · O objetivo desta unidade é expor os conceitos da Programação Linear 
como ferramenta de apoio para a solução de problemas de alocação 
de recursos empresariais. 
OBJETIVO DE APRENDIZADO
Introdução à Programação Linear
Orientações de estudo
Para que o conteúdo desta Disciplina seja bem 
aproveitado e haja uma maior aplicabilidade na sua 
formação acadêmica e atuação profissional, siga 
algumas recomendações básicas: 
Assim:
Organize seus estudos de maneira que passem a fazer parte 
da sua rotina. Por exemplo, você poderá determinar um dia e 
horário fixos como o seu “momento do estudo”.
Procure se alimentar e se hidratar quando for estudar, lembre-se de que uma 
alimentação saudável pode proporcionar melhor aproveitamento do estudo.
No material de cada Unidade, há leituras indicadas. Entre elas: artigos científicos, livros, vídeos e 
sites para aprofundar os conhecimentos adquiridos ao longo da Unidade. Além disso, você também 
encontrará sugestões de conteúdo extra no item Material Complementar, que ampliarão sua 
interpretação e auxiliarão no pleno entendimento dos temas abordados.
Após o contato com o conteúdo proposto, participe dos debates mediados em fóruns de discussão, 
pois irão auxiliar a verificar o quanto você absorveu de conhecimento, além de propiciar o contato 
com seus colegas e tutores, o que se apresenta como rico espaço de troca de ideias e aprendizagem.
Organize seus estudos de maneira que passem a fazer parte 
Mantenha o foco! 
Evite se distrair com 
as redes sociais.
Mantenha o foco! 
Evite se distrair com 
as redes sociais.
Determine um 
horário fixo 
para estudar.
Aproveite as 
indicações 
de Material 
Complementar.
Procure se alimentar e se hidratar quando for estudar, lembre-se de que uma 
Não se esqueça 
de se alimentar 
e se manter 
hidratado.
Aproveite as 
Conserve seu 
material e local de 
estudos sempre 
organizados.
Procure manter 
contato com seus 
colegas e tutores 
para trocar ideias! 
Isso amplia a 
aprendizagem.
Seja original! 
Nunca plagie 
trabalhos.
UNIDADE Introdução à Programação Linear
Contextualização
A escassez de recursos é um problema persistente em qualquer setor da atividade 
humana. Nem sempre temos em mãos todos os recursos adequados para atender 
as nossas necessidades, assim como uma organização também nem sempre dispõe 
de todos os recursos necessários para atender plenamente as demandas de suas 
diversas atividades.
A dificuldade de se alocar adequadamente os recursos escassos para atender 
às necessidades dos diversos departamentos é um dos problemas mais comuns 
dentro de qualquer organização. As empresas procuram empregar os recursos 
de forma eficaz, buscando sempre a otimização dos resultados, que normalmente 
corresponde à maximização dos lucros ou à minimização dos custos. Entretanto, a 
decisão sobre a melhor forma de se aplicar os recursos escassos geralmente é um 
processo complexo, que exige certo grau de estruturação. 
Dentro da Pesquisa Operacional (PO), a área que estuda as questões referentes à 
alocação dos recursos escassos, buscando a melhor forma de realizá-la, é a chamada 
“Programação Matemática”, da qual se deriva a “Programação Linear”, onde um 
modelo matemático constituído de funções lineares é utilizado para representar 
um cenário real, no qual o objetivo é representado por uma função matemática 
que expressa a solução ótima do problema (maximização ou minimização de uma 
determinada grandeza).
“O desenvolvimento da programação linear tem sido classificado entre os 
mais importantes avanços científicos dos meados do século XX e temos 
de concordar com essa afirmação. Seu impacto desde 1950 tem sido 
extraordinário. Hoje em dia é uma ferramenta-padrão que poupou muitos 
milhares ou milhões de dólares para muitas empresas ou até mesmo 
negócios de tamanho moderado em diversos países industrializados 
ao redor do mundo; e seu emprego em outros setores da sociedade se 
espalhou rapidamente.”
(HILLIER, F. S.; LIEBERMAN, G. J. Introdução à Pesquisa Operacional. 9. ed. Porto Alegre: McGraw-Hill, 2013, p.25)
8
9
Programação Matemática – Conceitos Gerais
A Programação Matemática é a área da Pesquisa Operacional (PO) que estuda as 
questões referentes à alocação dos recursos escassos, procurando a melhor forma 
de realizá-la. Um modelo matemático é utilizado para representar uma situação-
problema, onde o objetivo almejado é representado por uma função matemática 
que expressa a solução ótima do problema (maximização ou minimização de uma 
determinada grandeza).
O formato geral de um modelo aplicado na “Programação Matemática” é 
apresentado abaixo:
Onde:
f( ) - Representa a função objetivo Z
xj - Representa uma determinada variável de decisão (j=1,2,3,...,n)
bi - Quantidade disponível de um determinado recurso (i=1,2,3,...,m)
gi( ) - Função que representa uma determinada restrição (i=1,2,3,...,m)
n - Número de variáveis de decisão
m - Número de restrições
Devido sua extensão, a Programação Matemática é subdividida em áreas 
menores, das quais se destacam a Programação Linear (onde as funções que 
representam os objetivos e restrições são lineares) e a Programação Não-linear 
(onde pelo menos uma das funções não é linear). Nesta unidade estudaremos 
a Programação Linear, abordando a formulação e montagem dos modelos 
matemáticos, assim como a resolução gráfica e analítica desses modelos.
Programação Linear
A Programação Linear (PL) é uma das ferramentas de Pesquisa Operacional 
mais utilizada na resolução de problemas complexos de tomada de decisão. De 
modo geral, podemos defini-la como sendo uma técnica aplicada nos processos 
decisórios, cujo objetivo é encontrar a solução ótima para uma determinada 
situação-problema representada por um modelo matemático, sendo esse modelo 
composto por funções lineares.
9
UNIDADE Introdução à Programação Linear
É importante salientar que um modelo matemático é uma forma de representação 
matemática de um cenário real reduzido aos dados relevantes da situação-problema. 
A identificação e classificação desses dados é o primeiro passo do processo de mode-
lagem, que consiste em extrair do cenário real todas as informações importantes para 
o entendimento e modelagem da situação-problema, sendo essas informações, ou 
dados, classificadas nas seguintes categorias: 
 · Variáveis de decisão: são as incógnitas do problema, ou seja, correspondem 
aos dados que serão encontrados como solução;
 · Parâmetros: são os dados fixos e conhecidos do problema;
 · Variáveis de restrição: são os limitadores das variáveis de decisão, ou seja, são 
os valores que restringem as possíveis soluções;
 · Função objetivo: é a função que define a qualidade da solução, ou seja, é a 
função que representa a otimização desejada (maximização ou minimização).
Um modelo matemático de PL tem o seguinte formato geral:
O mesmo modelo pode ser representado em seu formato reduzido:
Onde:
n - é o número de variáveis de decisão
m - é o número de variáveis de restrição
i - é o índice de uma determinada restrição (i =1,2,3,...,m)
j - é o índice de uma determinada variável de decisão (j=1,2,3,...,n)
cj - é o coeficiente (constante) da variável de decisão xj.
aij - é o coeficiente da variável de decisão xj da j-ésima restrição.
10
11
Formulação de Problemas de Programação Linear 
Para exemplificar a formulação e resolução de problemas de Programação Linear, 
vamos considerar um cenário hipotético, no qual se deseja a maximização dos 
lucros. Começaremos com a apresentação do cenário e em seguida construiremos 
o modelo matemático para iniciarmos a resolução do problema por meio das 
técnicas de Programação Linear.
a) Apresentação do cenário hipotético
A indústria de móveis MOVBEL produzmesas do tipo A e do tipo B. Todas 
as mesas produzidas, após o processo de fabricação, passam por um controle de 
qualidade. Cada unidade de mesa do tipo A leva 3 horas para ser produzida e mais 
1 hora para ser inspecionada pelo controle de qualidade. Cada unidade de mesa do 
tipo B leva 2 horas para ser produzida e mais 2 horas para ser inspecionada. Para 
a fabricação das mesas dos tipos A e B, o departamento de produção disponibiliza 
120 horas/semana, e o departamento de controle de qualidade disponibiliza 80 
horas/semana. O lucro obtido por unidade vendida de mesa do tipo A é de R$ 
90,00 e o lucro por unidade de mesa do tipo B é de R$ 70,00.
Sabendo-se que toda a produção é vendida, deseja-se saber quantas mesas 
do tipo A e B devem ser produzidas por semana para que a empresa obtenha 
o lucro máximo. 
b) Identificação e classificação dos dados relevantes
Variáveis de decisão: 
 · X1: quantidade de mesas do tipo A a ser produzida
 · X2: quantidade de mesas do tipo B a ser produzida
Parâmetros:
 · 3h: tempo para fabricação de uma mesa do tipo A
 · 1h: tempo para inspeção de qualidade de uma mesa do tipo A
 · 2h: tempo para fabricação de uma mesa do tipo B
 · 2h: tempo para inspeção de qualidade de uma mesa do tipo B
 · R$ 90,00: lucro por unidade de mesa do tipo A
 · R$ 70,00: lucro por unidade de mesa do tipo B
Variáveis de restrição:
 · 120h/semana: disponibilidade de horas para fabricação
 · 80h/semana: disponibilidade de horas para inspeção
Função objetivo:
 · Z: maximização do lucro
11
UNIDADE Introdução à Programação Linear
c) Modelo matemático
Maximizar Z = 90.X1 + 70.X2 (função objetivo)
Sujeito a
 3.X1 + 2.X2 ≤ 120 (restrição de horas de fabricação)
 1X1 + 2X2 ≤ 80 (restrição de horas de inspeção)
 X1, X2 ≥ 0 (restrição de não negatividade)
Para a resolução deste problema de PL, dentre as diversas técnicas oferecidas 
pela Pesquisa Operacional, utilizaremos os métodos gráfico e analítico. O método 
gráfico consiste na representação do modelo matemático através de uma construção 
gráfica dentro do plano cartesiano, onde a solução ótima pode ser encontrada 
apenas com a simples observação desse gráfico. O método analítico consiste na 
análise matemática das funções do modelo, a partir da qual podemos determinar a 
solução ótima do problema.
Quando o problema envolve duas variáveis de decisão, como é o caso do nosso 
exemplo, que envolve apenas as variáveis X1 e X2, podemos facilmente resolvê-lo 
por meio dos métodos gráfico e analítico. Se o problema envolver mais de três 
variáveis de decisão, esses métodos se tornam inviáveis, sendo que nesse caso são 
indicadas outras técnicas de PO, como por exemplo, o método SIMPLEX, que 
utiliza algoritmos iterativos para a solução de problemas complexos. 
Resolução Gráfica do Problema
Para resolver graficamente um problema de Programação Linear, devemos 
primeiramente estabelecer um plano cartesiano onde cada um dos eixos (abscissas 
e ordenadas) deverá representar uma das variáveis de decisão. Para o problema 
da indústria de móveis MOVBEL, vamos representar a variável X1 (quantidade de 
mesas do tipo A) por meio do eixo das abscissas, e a variável X2 (quantidade de 
mesas do tipo B) por meio do eixo das ordenadas. Lembre-se de que essas variáveis 
são as incógnitas do problema e que o nosso objetivo é encontrar os seus valores 
ótimos para a maximização do lucro. Dessa forma, o nosso gráfico inicial deverá se 
apresentar como mostra a Figura 1.
Figura 1 - Representação gráfica com indicação das variáveis de decisão
12
13
O próximo passo é determinar as regiões do plano onde se encontram as soluções 
viáveis para cada uma das funções de restrição do problema. Essas regiões são cha-
madas de “regiões admissíveis”. Vamos começar com a restrição de não negatividade, 
a qual determina que as variáveis de decisão X1 (quantidade de mesas do tipo A) e X2 
(quantidade de mesas do tipo B) não podem ser negativas. Neste caso, a região admis-
sível encontra-se no quadrante positivo do plano, como mostra a Figura 2.
Figura 2 - Região admissível da restrição de não negatividade
Vamos agora encontrar a região que contém as soluções viáveis correspondentes 
à próxima restrição. Consideremos a restrição de horas de fabricação, que 
representa a quantidade de horas semanais disponível para a fabricação das mesas:
3.X1 + 2.X2 ≤ 120
 Horas semanais disponíveis para a fabricação das mesas
 Quantidade de mesas do tipo B a ser produzida
 Tempo em horas para a fabricação de uma mesa tipo B 
 Quantidade de mesas do tipo A a ser produzida 
 Tempo em horas para a fabricação de uma mesa tipo A 
Note que a restrição é determinada por uma inequação de 1º grau (linear), sendo 
assim, existem infinitas soluções para o problema. Porém, para essa restrição, é fácil 
deduzir que a solução ótima é o pleno emprego dos recursos para a máxima produção 
de mesas, ou seja, é a utilização de todo o tempo disponível para o processo de fabri-
cação, que neste caso é 120 horas semanais. Devemos então encontrar dois pontos 
que definem a reta dessa inequação para que possamos traçá-la no gráfico. Vamos 
achar os pontos onde a reta corta os eixos das abscissas e ordenadas, atribuindo valor 
0 (zero) à variável X1 para encontrarmos o primeiro ponto e atribuindo valor 0 (zero) 
à variável X2 para encontrarmos o segundo ponto, conforme demonstrado a seguir. 
Para X1 = 0, temos: 2.X2 ≤ 120  X2 ≤ 120 ÷ 2  X2 ≤ 60
Para X2 = 0, temos: 3.X1 ≤ 120  X1 ≤ 120 ÷ 3  X1 ≤ 40
13
UNIDADE Introdução à Programação Linear
Dessa forma, encontramos os dois pontos da reta: (0,60) e (40,0). Com esses 
pontos, podemos traçá-la conforme mostra a Figura 3. 
Figura 3 - Reta que representa a solução ótima para a restrição de horas de fabricação
Sendo essa reta a representação dos valores máximos possíveis de X1 e X2 que 
atendem a restrição, podemos concluir que qualquer ponto sobre ou abaixo dela 
é uma solução viável do problema. Dessa forma, a região admissível da restrição 
de horas de fabricação pode ser representada pela área destacada em amarelo no 
gráfico da Figura 3. Entretanto, também devemos considerar a restrição anterior 
representada pela área destacada em azul, que corresponde à restrição de não 
negatividade das variáveis X1 e X2. Portanto, a região que contém as soluções do 
problema, por enquanto, é representada pela intersecção dessas duas regiões.
Temos ainda outra restrição: quantidade de horas semanais disponível para o 
controle de qualidade das mesas (restrição de horas de inspeção). Devemos aplicar 
o mesmo procedimento para encontrarmos a região admissível dessa restrição, 
cuja inequação é apresentada a seguir:
1.X1 + 2.X2 ≤ 80
 Horas semanais disponíveis para a inspeção das mesas
 Quantidade de mesas do tipo B
 Tempo em horas para a inspeção de uma mesa tipo B 
 Quantidade de mesas do tipo A 
 Tempo em horas para a inspeção de uma mesa tipo A 
Para essa restrição, também é fácil deduzir que a solução ótima é o pleno 
emprego dos recursos para a máxima quantidade de mesas inspecionadas, ou 
seja, é a utilização de todo o tempo disponível para o controle de qualidade, que 
neste caso é 80 horas semanais. Portanto, vamos encontrar e traçar a reta que 
representa essa solução ótima, definindo os pontos onde ela corta os eixos das 
abscissas e ordenadas:
14
15
Para X1 = 0, temos: 2.X2 ≤ 80  X2 ≤ 80 ÷ 2  X2 ≤ 40
Para X2 = 0, temos: X1 ≤ 80 
Dessa forma, encontramos os dois pontos da reta: (0,40) e (80,0). Com esses 
pontos, podemos traçá-la conforme mostra a Figura 4. Observe que a reta desta 
restrição está representada em verde.
Figura 4 - Reta que representa a solução ótima para a restrição de horas de inspeção (em verde)
Sendo essa reta a representação dos valores máximos possíveis de X1 e X2 que 
atendem a restrição, podemos concluir que qualquer ponto sobre ou abaixo dela é 
uma solução viável do problema. 
Considerando todas as restrições do problema (restrição de não negatividade, 
restrição dehoras de fabricação e restrição de horas de inspeção), podemos dizer 
que as soluções viáveis do problema encontram-se na área de intersecção das 
regiões admissíveis do conjunto de restrições, conforme mostra a Figura 5, onde a 
área hachurada representa a região das soluções viáveis do problema.
Figura 5 - Soluções viáveis do problema (área hachurada)
Observe que a região admissível (que contém as soluções viáveis) é representada 
graficamente por um polígono, cujos vértices podem ser obtidos facilmente com ape-
nas a simples observação do gráfico, conforme podemos notar por meio da Figura 6.
15
UNIDADE Introdução à Programação Linear
Figura 6 - Vértices da região admissível obtidos graficamente
Agora sabemos que a solução ótima do problema se encontra em algum 
ponto da área definida pelo polígono, incluindo as linhas que o delimitam. Para 
encontrar essa solução ótima, na qual o valor de X1 (quantidade de mesas do 
tipo A a produzir) e o valor de X2 (quantidade de mesas do tipo B a produzir) 
gerarão o maior valor como resultado da função objetivo (maior lucro), devemos 
primeiramente encontrar algumas relações geométricas da função objetivo Z, 
cuja equação é destacada a seguir. 
Z = 90.X1 + 70.X2 (Função objetivo) 
 Quantidade de mesas do tipo B a ser produzida
 Lucro por unidade de mesa do tipo B
 Quantidade de mesas do tipo A a ser produzida
 Lucro por unidade de mesa do tipo A
Observe que a função linear Z possui duas variáveis independentes (X1 e X2), 
que podem assumir infinitos valores, gerando dessa forma, infinitas retas paralelas 
(com o mesmo coeficiente angular). Precisamos conhecer pelo menos duas dessas 
retas para a conclusão da análise do nosso problema. Uma forma simples de obtê-
las, é criar duas equações onde os resultados sejam arbitrários, porém, múltiplos 
dos coeficientes, que neste caso são 90 e 70. Vamos então considerar as seguintes 
equações a e b:
a) 90.X1 + 70.X2 = 630 (630 é múltiplo dos coeficientes 90 e 70)
b) 90.X1 + 70.X2 = 1260 (1260 é múltiplo dos coeficientes 90 e 70)
Para encontrarmos as coordenadas que definem a reta de cada uma dessas 
equações, basta acharmos os pontos onde as retas cortam os eixos das abscissas e 
ordenadas, obedecendo aos seguintes procedimentos:
16
17
1) Encontrar os pontos da reta a
 Equação a: 90.X1 + 70.X2 = 630
 Para X1 = 0, temos: 70.X2 = 630  X2 = 630 ÷ 70  X2 = 9 
 Para X2 = 0, temos: 90.X1 = 630  X1 = 630 ÷ 90  X1 = 7
 Pontos da reta a: (0, 9) e (7, 0)
2) Encontrar os pontos da reta b
 Equação b: 90.X1 + 70.X2 = 1260
 Para X1 = 0, temos: 70.X2 = 1260  X2 = 1260 ÷ 70  X2 = 18 
 Para X2 = 0, temos: 90.X1 = 1260  X1 = 1260 ÷ 90  X1 = 14
 Pontos da reta b: (0, 18) e (14, 0)
Encontrados os pontos, devemos traçar as retas conforme mostra a Figura 7.
Figura 7 - Retas a e b geradas a partir da função objetivo Z
Analisando graficamente as retas a e b, podemos verificar que elas são parale-
las, com coeficiente angular negativo (retas decrescentes). Entretanto, a informa-
ção mais importante para nossas finalidades é a constatação de que quanto mais 
distante da origem a reta se encontra, maior é o lucro resultante da função. Veja 
que a reta a (representada em vermelho na Figura 7) é a mais próxima da origem e 
corresponde à equação que tem como resultado o valor 630, ao passo que a reta b 
(representada em azul na Figura 7) corresponde à equação que tem como resulta-
do o valor 1260. Neste caso, para determinarmos a equação que apresenta como 
resultado o maior valor possível (lucro máximo), devemos encontrar a reta mais 
distante da origem e que ainda contenha pelo menos um ponto dentro da região 
admissível (representada graficamente pelo polígono). Para isso, podemos traçar 
várias outras retas paralelas acima da reta b, realizando uma espécie de varredura, 
até encontrarmos a última reta que ainda toca a região admissível, como mostra 
a Figura 8.
17
UNIDADE Introdução à Programação Linear
Figura 8 - Retas paralelas traçadas para a varredura da região admissível
O ponto da região admissível tocado pela última reta é justamente aquele que 
representa o maior lucro possível, ou seja, a melhor solução para o problema, que 
neste caso é o ponto 20, 30 (X1 = 20 e X2 = 30). Isso significa que a empresa 
MOVBEL deverá produzir 20 mesas do tipo A e 30 mesas do tipo B para obter 
o lucro máximo. Podemos então resolver a função objetivo Z da seguinte forma:
Z = 90.X1 + 70.X2 
Z = 90.20 + 70.30
Z = 1800 + 2100
Z = 3900 
Portanto, produzindo 20 mesas do tipo A e 30 mesas do tipo B, a empresa 
MOVBEL terá um lucro de R$ 3.900,00, que corresponde ao lucro máximo 
possível para o cenário apresentado.
A seguir, é apresentada uma a sequência resumida de passos para a resolução 
gráfica do problema apresentado. No final, faremos algumas considerações para que 
essa sequência possa ser aplicada nas diversas situações de Programação Linear.
Sequência de passos para a resolução gráfica de PL:
18
19
Considerações
1. A região admissível de uma determinada restrição sempre estará sobre e 
abaixo da reta da inequação quando a relação desta for “menor ou igual” 
(≤), conforme mostra a Figura 9.
Figura 9 - Região admissível quando a relação da inequação for “menor ou igual” (≤)
2. A região admissível de uma determinada restrição sempre estará sobre e 
acima da reta da inequação quando a relação desta for “maior ou igual” 
(≥), conforme mostra a Figura 10.
19
UNIDADE Introdução à Programação Linear
Figura 10 - Região admissível quando a relação da inequação for “maior ou igual” (≥)
3. Para encontrarmos a possível solução ótima do problema, aplicamos um 
método simples que consiste em encontrar 2 retas a partir da função objetivo. 
Através da análise dessas retas, podemos definir o sentido de varredura da 
região admissível para que possamos encontrar a reta que expressa a melhor 
solução. Para ilustrar, vamos tomar a seguinte função objetivo: Z = 3.X1 
+ 2.X2. Para encontrarmos a primeira reta, devemos atribuir à variável 
dependente Z um valor que seja múltiplo dos coeficientes da função, que 
neste caso são 3 e 2. Da mesma forma, para a segunda reta, devemos atribuir 
à variável Z outro valor que também seja múltiplo dos coeficientes (que pode 
ser, por exemplo, o dobro do primeiro). Sendo assim, teremos:
Reta a: 3.X1 + 2.X2 = 6 (6 é múltiplo dos coeficientes 3 e 2)
Reta b: 3.X1 + 2.X2 = 12 (12 é múltiplo dos coeficientes 3 e 2)
Para encontrarmos as coordenadas que definem a reta de cada uma dessas 
equações, basta acharmos os pontos onde as retas cortam os eixos, conforme 
demonstração a seguir:
Reta a:
P/ X1 = 0: 2.X2 = 6  X2 = 3 
P/ X2 = 0: 3.X1 = 6  X1 = 2
Pontos da reta a: (0, 3) e (2, 0)
Reta b:
P/ X1 = 0: 2.X2 = 12  X2 = 6 
P/ X2 = 0: 3.X1 = 12  X1 = 4
Pontos da reta b: (0, 6) e (4, 0)
Caso a função objetivo seja a maximização, o sentido de varredura da 
região admissível será sempre da reta que representa o menor resultado para 
a reta que representa o maior resultado, até encontrarmos a reta paralela 
que tangencia a região admissível, sendo essa reta aquela que contém 
pelo menos um ponto que representa a melhor solução para o problema 
(maximização), conforme demonstra a Figura 11.
20
21
Figura 11 - Sentido de varredura da região admissível para problemas de maximização
Caso a função objetivo seja a minimização, o sentido de varredura da região 
admissível será sempre da reta que representa o maior resultado para a reta que 
representa o menor resultado, até encontrarmos a reta paralela que tangencia 
a região admissível, sendo essa reta aquela que contém pelo menos um ponto 
que representa a melhor solução para o problema (minimização), conforme 
demonstra a Figura 12.
Figura 12 - Sentido de varredura da região admissível para problemas de minimização
4. Há casos em que a última reta (aquela que expressa a solução ótima do pro-
blema) passa exatamente sobre toda a extensão de um dos lados do polígono 
que delimita a região admissível,sendo que nesses casos não existe uma única 
solução ótima. Qualquer um dos pontos do lado do polígono que coincide com 
a reta pode ser considerado uma solução ótima, conforme mostra a Figura 13.
Figura 13 - Situação onde existem múltiplas soluções ótimas
21
UNIDADE Introdução à Programação Linear
Resolução Gráfica de um Problema de Minimização 
Vimos nas seções anteriores a resolução do problema de maximização da indústria 
de móveis MOVBEL. Vamos agora resolver um problema de minimização, conside-
rando o seguinte cenário hipotético:
Um produtor agrícola necessita de no mínimo 32 unidades de fertilizante 
fosfatado e de 36 unidades de fertilizante potássico para atender as neces-
sidades de fertilização semanal de sua lavoura. Em seu estoque, o produtor 
tem esses fertilizantes em duas versões: vidro (fertilizante liquido) e caixa 
(fertilizante em pó), sendo que cada vidro contém 4 unidades do produto 
fosfatado e 6 unidades do produto potássico, e cada caixa contém 8 unida-
des do produto fosfatado e 4 unidades do produto potássico. Sabendo-se 
que cada unidade de vidro custa R$ 10,00 e cada unidade de caixa custa 
R$ 8,00, quais quantidades de vidros e caixas devem ser utilizadas semanal-
mente para que o produtor tenha o menor custo, atendendo às necessidades 
de sua lavoura em relação à fertilização?
Dados do problema
Variáveis de decisão (incógnitas do problema):
 X1: quantidade de vidros (fertilizante líquido) a utilizar. 
 X2: quantidade de caixas (fertilizante em pó) a utilizar. 
Parâmetros:
 R$ 10,00: custo de 1 unidade de vidro.
 R$ 8,00: custo de 1 unidade caixa.
 4: unidades do fertilizante fosfatado em um vidro.
 6: unidades do fertilizante potássico em um vidro.
 8: unidades do fertilizante fosfatado em uma caixa.
 4: unidades do fertilizante potássico em uma caixa.
Variáveis de restrição:
 32: unidades de fertilizante fosfatado (mínimo necessário).
 36: unidades de fertilizante potássico (mínimo necessário).
Função objetivo:
 Z: minimização do custo.
22
23
Modelo matemático
Minimizar Z = 10.X1 + 8.X2 (função objetivo)
Sujeito a
 4.X1 + 8.X2 ≥ 32 (restrição de fertilizante fosfatado)
 6.X1 + 4.X2 ≥ 36 (restrição de fertilizante potássico)
 X1, X2 ≥ 0 (restrição de não negatividade)
Representação gráfica das restrições
Primeiramente, devemos encontrar os pontos que cortam os eixos de cada uma 
das retas que representam as restrições, conforme demonstrado a seguir:
(1) Restrição de fertilizante fosfatado (4.X1 + 8.X2 ≥ 32) 
 p/ X1=0: 8.X2 ≥ 32  X2 ≥ 4 
 p/ X2=0: 4.X1 ≥ 32  X1 ≥ 8
 Pontos: (0, 4) e (8, 0) 
(2) Restrição de fertilizante potássico (6.X1 + 4.X2 ≥ 36)
 p/ X1=0: 4.X2 ≥ 36  X2 ≥ 9 
 p/ X2=0: 6.X1 ≥ 36  X1 ≥ 6
 Pontos: (0, 9) e (6, 0) 
Com os pontos encontrados, vamos traçar as retas e definir a região admissível 
do problema. Como este é um caso de minimização, onde as inequações das 
restrições apresentam a relação “maior ou igual” (≥), a região admissível estará 
acima das retas, conforme mostra a Figura 14.
Figura 14 - Região admissível para o problema de minimização
Devemos lembrar que a restrição de não negatividade das variáveis X1 e X2, 
determina que a região admissível esteja no quadrante positivo do gráfico.
23
UNIDADE Introdução à Programação Linear
Representação gráfica e análise de duas retas da função objetivo Z
Lembre-se de que para encontrarmos a solução ótima do problema, devemos, 
primeiramente, encontrar duas retas da função objetivo, onde os resultados das 
duas equações que representam essas retas devem ser múltiplos dos coeficientes, 
conforme demonstrado a seguir.
Função objetivo: Z = 10.X1 + 8.X2
(a) 10.X1 + 8.X2 = 120 (120 é múltiplo dos coeficientes 10 e 8)
 p/ X1=0: 8.X2 = 120  X2 = 15 
 p/ X2=0: 10.X1 = 120  X1 = 12
 Pontos: (0, 15) e (12, 0) 
(b) 10.X1 + 8.X2 = 80 (80 é múltiplo dos coeficientes 10 e 8)
 p/ X1=0: 8.X2 = 80  X2 = 10 
 p/ X2=0: 10.X1 = 80  X1 = 8
 Pontos: (0, 10) e (8, 0) 
Para encontrarmos os pontos das retas, tomamos os valores 120 e 80 como 
resultados da função objetivo. Esses valores foram escolhidos propositadamente para 
que as retas interceptem a região admissível, de forma a facilitar a visualização gráfica. 
Entretanto, poderíamos considerar quaisquer valores múltiplos dos coeficientes. 
Sendo o resultado da equação a (120) maior que o resultado da equação b 
(80), o sentido de varredura da região admissível deve ser da reta a para a reta 
b, ou seja, do maior para o menor resultado, pois, procuramos pelo menor custo 
(minimização). A Figura 15 ilustra esse fato.
Figura 15 - Sentido da varredura para o problema de minimização
24
25
Determinação da solução ótima
Efetuando a varredura, encontramos a última reta que tangencia a região admissí-
vel, como mostra a Figura 16. 
Figura 16 - Solução ótima do problema de minimização
Neste nosso exemplo, encontramos uma única solução ótima, que corresponde 
ao ponto X1=5 e X2=1,5 (um dos vértices da região admissível). Observe que esse 
ponto é justamente a intersecção das retas de restrição, sendo assim, também 
podemos encontrá-lo matematicamente igualando as duas funções de restrição e 
resolvendo o sistema resultante, conforme demonstrado a seguir. 
4.X1 + 8.X2 ≥ 32 (restrição de fertilizante fosfatado)
6.X1 + 4.X2 ≥ 36 (restrição de fertilizante potássico)
Substituindo o operador relacional “maior ou igual” (≥) por “igual” (=), para 
transformar as inequações em equações, temos:
4.X1 + 8.X2 = 32 (1) 
6.X1 + 4.X2 = 36 (2) 
4.X1 = 32 - 8.X2 (isolando X1 da equação 1)
X1 = (32÷4) - (8.X2÷4)  X1 = 8 - 2.X2 (3)
6.(8 - 2.X2)+ 4.X2 = 36 (substituindo X1 da equação 2)
48 - 12.X2 + 4.X2 = 36  -8X2 = 36 - 48  -8X2 = -12  X2 = 1,5
X1 = 8 - 2.(1,5) (substituindo X2 da equação 3)
X1 = 8 - 3  X1 = 5 
Desta forma, podemos verificar que a solução ótima para este problema se 
encontra no ponto X1=5 e X2=1,5, ou seja, para conseguir o menor custo, o 
produtor deve utilizar 5 vidros de fertilizante líquido (X1) e 1,5 caixa de fertilizante 
em pó (X2). 
25
UNIDADE Introdução à Programação Linear
Resolução Analítica de um Problema de Maximização
Para resolvermos analiticamente um problema de Programação Linear, devemos 
inicialmente conhecer os vértices da região admissível, pois, se o problema tiver uma 
solução ótima, ela estará em um dos vértices dessa região. Para ilustrar a aplicação 
desse método, tomemos como exemplo o problema da maximização de lucro da 
indústria de móveis MOVBEL, cujo modelo matemático é apresentado a seguir. 
O primeiro passo para a resolução deste problema é encontrarmos os vértices do 
polígono da região admissível. Iniciaremos por encontrar os vértices localizados sobre 
os eixos das ordenadas e das abscissas, para tanto, devemos determinar os pontos 
onde cada uma das retas (geradas pelas restrições do modelo) cruzam esses eixos.
Restrição de horas de fabricação: 3.X1 + 2.X2 ≤ 120
P/ X1 = 0 : 2.X2 ≤ 120  X2 ≤ 120 ÷ 2  X2 ≤ 60
P/ X2 = 0 : 3.X1 ≤ 120  X1 ≤ 120 ÷ 3  X1 ≤ 40
Pontos: (0, 60) e (40, 0)
Restrição de horas de inspeção: 1X1 + 2X2 ≤ 80
P/ X1 = 0, : 2.X2 ≤ 80  X2 ≤ 80 ÷ 2  X2 ≤ 40
P/ X2 = 0 : X1 ≤ 80 
Pontos: (0, 40) e (80, 0)
Encontramos assim os pontos (0, 60), (40, 0), (0,40) e (80,0). Sabendo-se que 
os operadores relacionais das inequações de restrição são do tipo “menor ou igual” 
(≤), concluímos que a região admissível se encontra abaixo das retas. Portanto, 
são vértices do polígono dessa região apenas os pontos (0, 40) e (40, 0), como 
podemos observar por meio do gráfico apresentado na Figura 17.
Figura 17 - Os dois vértices da região admissível: (0,40) e (40,0)
26
27
Observe que o ponto (0, 60) da restrição de horas de fabricação está acima do 
ponto (0, 40) da restrição de horas de inspeção, sendo assim, devemos desprezar 
o primeiro. Da mesma forma, devemos desprezar o ponto (80, 0) da restrição 
de horas de inspeção, pois ele se encontra à direita do ponto (40, 0) da restrição 
de horas defabricação. Sendo assim, veja que não é preciso construir um gráfico 
para identificarmos os pontos dos vértices. Podemos identificá-los simplesmente 
empregando o seguinte critério: quando a região admissível é definida abaixo das 
retas de restrição, os vértices são os pontos mais próximos da origem (0, 0), ou 
seja, para o vértice que se encontra sobre o eixo das abscissas, considera-se o ponto 
cuja abscissa X1 seja a menor, e para o vértice que se encontra sobre o eixo das 
ordenadas, considera-se o ponto cuja ordenada X2 também seja menor.
Neste nosso problema existem outros dois vértices: um na origem (ponto 0,0) e 
outro na intersecção das retas de restrição. Para determinarmos esse último, devemos 
construir e resolver um sistema envolvendo as equações das restrições, conforme segue. 
3.X1 + 2.X2 ≤ 120 (restrição de horas de fabricação)
1.X1 + 2.X2 ≤ 80 (restrição de horas de inspeção)
Substituindo o operador relacional “menor ou igual” ( ≤) por “igual” (=), para 
transformar as inequações em equações, temos:
3.X1 + 2.X2 = 120 (1) 
1.X1 + 2.X2 = 80 (2) 
Subtraindo a equação 2 da equação 1, temos:
3.X1 - 1.X1 + 2.X2 - 2.X2 = 120 - 80
2.X1 = 40  X1 = 20 
Substituindo X1=20 da equação 2, temos:
20 + 2.X2 = 80  2.X2 = 80 - 20  2.X2 = 60  X2 = 30
E desta forma encontramos a coordenada X1=20 e X2=30, que corresponde ao 
vértice da área admissível onde as retas de restrição se intersectam, como podemos 
constatar através da Figura 18. 
Figura 18 - Vértice da região admissível onde as retas de restrição se intersectam
27
UNIDADE Introdução à Programação Linear
Encontradas as coordenadas dos quatro vértices, devemos relacioná-las em uma 
tabela, mostrando o resultado da função objetivo Z para cada uma delas. A Tabela 1 
apresenta esse processo.
Tabela 1 - Resultados da função objetivo Z para cada um dos vértices
Vértices Função objetivo Z
Z = 90.X1 + 70.X2X1 X2
0 0 Z = 90 . 0 + 70 . 0 = 0
0 40 Z = 90 . 0 + 70 . 40 = 2800
20 30 Z = 90 . 20 + 70 . 30 = 3900 (solução ótima)
40 0 Z = 90 . 40 + 70 . 0 = 3600
Analisando a tabela, podemos concluir que a solução ótima para o problema se 
encontra no vértice cuja coordenada é 20,30 (X1=20 e X2=30), pois a resposta 
da função objetivo Z para essa coordenada corresponde ao maior valor possível 
(3900). Portanto, produzindo 20 mesas do tipo A e 30 mesas do tipo B, a empresa 
MOVBEL terá um lucro de R$ 3.900,00, que corresponde ao lucro máximo possível 
para o cenário apresentado (observe que essa solução é a mesma encontrada por 
meio do método gráfico).
Resolução Analítica de um Problema de Minimização 
Para demonstrar a resolução analítica de um problema de minimização, vamos 
retomar o exemplo do produtor agrícola que deseja minimizar o custo em relação 
à fertilização de sua lavoura. O modelo matemático do problema é apresentado 
a seguir.
Lembremos que as variáveis de decisão X1 e X2 correspondem, respectivamente, 
às quantidades de vidros e caixas de fertilizante a serem utilizadas.
Devemos aplicar os mesmos procedimentos adotados para o problema de 
maximização, porém, lembre-se de que a solução ótima será aquela que apresentar 
o menor resultado para a função objetivo Z, pois, neste caso, procuramos pelo 
menor custo possível. Os procedimentos para a resolução do problema são 
apresentados nos itens a seguir.
28
29
a) Determinar o ponto da reta da primeira restrição cuja abscissa é zero (X1=0): 
 4.X1 + 8.X2 ≥ 32
 0 + 8.X2 ≥ 32  X2 ≥ 32 ÷ 8  X2 ≥ 4 
b) Determinar o ponto da reta da primeira restrição cuja ordenada é zero (X2=0): 
 4.X1 + 8.X2 ≥ 32
 4.X1 + 0 ≥ 32  X1 ≥ 32 ÷ 4  X1 ≥ 8 
c) Determinar o ponto da reta da segunda restrição cuja abscissa é zero (X1=0):
 6.X1 + 4.X2 ≥ 36
 0 + 4.X2 ≥ 36  X2 ≥ 36 ÷ 4  X2 ≥ 9 
d) Determinar o ponto da reta da segunda restrição cuja ordenada é zero (X2=0). 
 6.X1 + 4.X2 ≥ 36
 6.X1 + 0 ≥ 36  X1 ≥ 36 ÷ 6  X1 ≥ 6 
e) Obter o primeiro vértice da região admissível considerando o ponto que tem 
como abscissa o valor zero (X1=0) e como ordenada o maior valor encontrado 
de X2 (que neste caso é o valor encontrado no item c, ou seja, 9). Portanto, 
o primeiro vértice é o ponto 0, 9 (X1=0 e X2=9).
f) Obter o segundo vértice da região admissível considerando o ponto que tem 
como ordenada o valor zero (X2=0) e como abscissa o maior valor encontrado 
de X1 (que neste caso é o valor encontrado no item b, ou seja, 8). Portanto, 
o segundo vértice é o ponto 8, 0 (X1=8 e X2=0).
g) Obter o terceiro vértice da região admissível resolvendo o sistema de equações 
correspondente às restrições do problema. Esse vértice corresponde ao ponto 
onde as retas das duas restrições se intersectam.
 4.X1 + 8.X2 = 32 (1) (restrição de fertilizante fosfatado)
 6.X1 + 4.X2 = 36 (2) (restrição de fertilizante potássico)
 4.X1 = 32 - 8.X2 (isolando X1 da equação 1)
 X1 = (32÷4) - (8.X2÷4) 
 X1 = 8 - 2.X2 (3)
 6.(8 - 2.X2)+ 4.X2 = 36 (substituindo X1 na equação 2)
 48 - 12.X2 + 4.X2 = 36 
 -8X2 = 36 - 48 
 -8X2 = -12  X2 = 1,5
 X1 = 8 - 2.(1,5) (substituindo X2 na equação 3)
 X1 = 8 - 3  X1 = 5 
Portanto, o terceiro vértice é o ponto 5,1.5 ( X1=5 e X2=1,5).
29
UNIDADE Introdução à Programação Linear
h) Construir uma tabela relacionando os vértices encontrados e calculando o 
resultado da função objetivo Z para cada um deles. 
Vértices Função objetivo Z
Z = 10.X1 + 8.X2X1 X2
0 9 Z = 10 . 0 + 8 . 9 = 72
8 0 Z = 10 . 8 + 8 . 0 = 80
5 1,5 Z = 10 . 5 + 8 . 1,5 = 62 (solução ótima)
Podemos verificar que a solução ótima para este problema se encontra 
no ponto X1 = 5 e X2 = 1,5 (ponto onde o resultado da função objetivo Z 
apresenta o menor resultado, ou seja, o menor custo possível). Sendo assim, 
para conseguir o menor custo (R$ 62,00), o produtor deve utilizar 5 vidros 
de fertilizante líquido (X1) e 1,5 caixa de fertilizante em pó (X2). Veja que o 
resultado encontrado com o método analítico é o mesmo resultado encontrado 
com o método gráfico.
30
31
Material Complementar
Indicações para saber mais sobre os assuntos abordados nesta Unidade:
 Livros
Pesquisa Operacional na Tomada de Decisões
LACHTERMACHER, G. Pesquisa Operacional na Tomada de Decisões. 4. ed. 
São Paulo: Pearson Prentice Hall, 2012. Capítulo 2.
Introdução à Pesquisa Operacional
HILLIER, F. S.; LIEBERMAN, G. J. Introdução à Pesquisa Operacional. 9. ed. 
Porto Alegre: Mc Graw-Whill, 2013. Capítulo 3.
 Leitura
Programação Linear Aplicada a uma Microempresa de Comunicação Visual
https://goo.gl/ZJ1syL
Programação Linear: Um Estudo de Caso sobre os Custos de Transporte em uma Empresa do Setor de Confecções 
de Catalão-GO
https://goo.gl/XF8RRz
31
UNIDADE Introdução à Programação Linear
Referências
ANDRADE, E. L. Introdução à Pesquisa Operacional: Métodos e Modelos Para a 
Análise de Decisão. 4. ed. Rio de Janeiro: LTC - Livros Técnicos e Científicos, 2011.
HILLIER, F. S.; LIEBERMAN, G. J. Introdução à Pesquisa Operacional. 9. ed. 
Porto Alegre: Mc Graw-Whill, 2013.
LACHTERMACHER, G. Pesquisa Operacional na Tomada de Decisões. 4. ed. 
São Paulo: Pearson Prentice Hall, 2012.
32