Prévia do material em texto
Métodos Quantitativos
Marcio Quirino - 1
SUMÁRIO
Saiba Quais Conteúdos Você Irá Aprender Conosco ........................................................................... 4
Onboarding................................................................................................................................................. 4
A Pesquisa Operacional Como Ferramenta de Apoio à Decisão ......................................................... 5
Descrição ................................................................................................................................................... 5
Propósito .................................................................................................................................................... 5
Preparação ................................................................................................................................................. 5
Objetivos .................................................................................................................................................... 5
Introdução .................................................................................................................................................. 5
1. Conceitos gerais de Pesquisa Operacional............................................................................. 6
Pesquisa Operacional ................................................................................................................................ 6
Origem – Circo de Blackett ..................................................................................................................... 6
Aplicação da PO na análise de decisão ..................................................................................................... 7
Problemas do cotidiano .......................................................................................................................... 8
Modelos matemáticos ................................................................................................................................ 9
Composição ........................................................................................................................................... 9
Classificação ........................................................................................................................................ 10
Fases de um estudo de Pesquisa Operacional ........................................................................................ 10
2. Principais características e propriedades de um modelo de Programação Linear .............. 12
Programação Linear ................................................................................................................................. 12
Características ..................................................................................................................................... 12
Elementos ............................................................................................................................................ 12
Passo a passo para a construção de um modelo de Programação Linear .............................................. 13
Aplicação do passo a passo para a construção de um modelo de Programação Linear ......................... 14
Identificação das variáveis de decisão ................................................................................................. 15
Identificação da função objetivo ........................................................................................................... 15
Identificação do conjunto de restrições ................................................................................................ 16
3. Método gráfico para a solução de problemas de Programação Linear ................................ 17
Aplicação do Método Gráfico para a solução de um problema de Programação Linear .......................... 17
Espaço de soluções ............................................................................................................................. 17
Restrição de horas de costura .............................................................................................................. 18
Delimitação do espaço de soluções ..................................................................................................... 18
Situações particulares da solução de um problema de Programação Linear pelo Método Gráfico.......... 20
Solução ótima única ............................................................................................................................. 20
Problema inviável ................................................................................................................................. 21
Problema ilimitado ................................................................................................................................ 21
Problema de múltiplas soluções ........................................................................................................... 21
Considerações Finais ............................................................................................................................... 22
Referências .............................................................................................................................................. 22
Explore+ ................................................................................................................................................... 22
Métodos Quantitativos
Marcio Quirino - 2
Aplicações da Programação Linear ..................................................................................................... 23
Descrição ................................................................................................................................................. 23
Propósito .................................................................................................................................................. 23
Preparação ............................................................................................................................................... 23
Introdução ................................................................................................................................................ 23
1. Técnica de modelagem em problemas clássicos de programação linear ............................ 23
Modelagem de problemas de programação linear ................................................................................... 23
Problema da mistura ............................................................................................................................ 24
Teoria na prática ...................................................................................................................................... 24
Exemplo - problema da dieta ................................................................................................................ 24
Problema do planejamento de produção e de estoques .......................................................................... 26
Problema estático ................................................................................................................................. 26
Teoria na prática ...................................................................................................................................... 26
Problema do planejamento de produção estático ................................................................................ 26
Problema dinâmico ................................................................................................................................... 27
Teoria na prática ......................................................................................................................................peixe a serem consumidos por dia pelas crianças;
• x4 = 100g de salada a serem consumidos por dia pelas crianças.
Identificar a função objetivo
Em seguida, devemos identificar a função objetivo. Sabemos que a mãe deseja gastar o menor valor possível,
de modo que este deve ser um problema de minimização! A mãe já fez a pesquisa de preços, então só nos falta
montar a função objetivo:
Min Z= 2x1+20x2+25x3+3x4
Identificar o conjunto de inequações
Porém, não se esqueça de que a mãe também está preocupada com a qualidade nutricional da alimentação
de seus filhos e que a nutricionista indicou que as crianças devem comer, no mínimo, 10mg de vitamina A, 70mg de
vitamina C e 250mg de vitamina D por dia. As informações nutricionais em mg de vitamina A C e D dos alimentos leite,
carne, peixe e salada são apresentadas na tabela de informações nutricionais, já apresentada. Assim, podemos
identificar o conjunto de inequações que representam estas restrições. São elas:
• 2x1+2x2+10x3+20x4≥10→Vitamina A
• 50x1+20x2+10x3+30x4≥70→Vitamina C
• 80x1+70x2+10x3+80x4≥250 →Vitamina D
Não podemos nos esquecer das restrições de não negatividade para as variáveis de decisão. Logo, temos que:
x1, x2, x3, x4≥0
Modelo
Enfim, temos que o modelo para este exemplo do problema da dieta é:
Min Z= 2x1+20x2+25x3+3x4
Sujeito a:
• 2x1+2x2+10x3+20x4≥10
• 50x1+20x2+10x3+30x4≥70
• 80x1+70x2+10x3+80x4≥250
• x1, x2, x3, x4≥0
Métodos Quantitativos
Marcio Quirino - 26
Problema do planejamento de produção e de estoques
Neste tipo de problema, deseja-se determinar níveis para atividades de produção, considerando que
a capacidade de produção de cada atividade sofra restrições de caráter tecnológico e prático.
O problema do planejamento de produção pode ser estático ou dinâmico.
Problema estático
No problema estático, considera-se a produção em determinado horizonte de programação finito, de
modo que as formulações contemplam apenas um período, conforme verificaremos no exemplo a seguir:
Teoria na prática
Problema do planejamento de produção estático
Uma fábrica de bicicletas está planejando seus níveis de produção para o próximo semestre. O custo
unitário da produção da bicicleta infantil é de R$280,00, enquanto o custo unitário da produção da bicicleta
para adultos é de R$620,00.
São necessários seis trabalhadores para fazer um lote de 8 bicicletas infantis por dia, enquanto três
trabalhadores conseguem fabricar 5 bicicletas de adulto por dia. Existem 200 pessoas disponíveis para a
produção de bicicletas, podendo ser alocadas em qualquer um dos dois serviços.
A fábrica tem capacidade máxima de produção de 300 bicicletas. Ainda, para atender à demanda
existente, devem ser produzidos, no mínimo, 20 lotes de bicicletas infantis e 15 lotes de bicicletas de adultos.
Formule o modelo de programação linear para minimizar o custo de produção da fábrica.
O primeiro passo para a construção de qualquer modelo consiste em identificar as variáveis de decisão para o
problema. Neste caso, a variável de decisão deve ser xi, sendo x a quantidade de bicicletas do tipo “i” a ser produzida
por dia. Logo, temos:
• x1 = número de bicicletas infantis a serem produzidas por dia;
• x2 = número de bicicletas infantis a serem produzidas por dia.
Em seguida, passamos à definição da função objetivo. A fábrica tem como meta minimizar o seu custo de
produção diário. Assim, como o custo unitário da produção da bicicleta infantil é de R$280,00, e da bicicleta de adulto
é de R$620,00, temos a seguinte função objetivo:
Min Z= 280x1+620x2
A fábrica emprega 200 funcionários por dia. São necessários seis trabalhadores para fazer um lote de 8
bicicletas infantis por dia, logo, cada trabalhador produziria 0,75 bicicletas por dia. Três trabalhadores fabricam 5
bicicletas de adulto por dia, logo, cada trabalhador produziria 0,625 bicicletas. Com esses dados, conseguimos definir
a restrição da fábrica com relação à capacidade de mão de obra:
0,75x1+0,6x2 ≤200
A fábrica tem capacidade máxima de produção de 300 bicicletas. Logo, a restrição com relação à capacidade
da fábrica é:
x1+x2 ≤300
Além disso, para atender à demanda existente devem ser produzidos, no mínimo, 20 lotes de bicicletas infantis.
Como cada lote é composto por 8 bicicletas infantis, devem ser produzidas, ao menos, 160 bicicletas infantis.
x1 ≥160
Por sua vez, devem ser produzidos 15 lotes de bicicletas de adultos, com 5 bicicletas em cada um, de modo
que:
x2 ≥75
Métodos Quantitativos
Marcio Quirino - 27
Enfim, temos que o modelo para este exemplo do problema de planejamento da produção estático é:
Min Z= 280x1+620x2
Sujeito a:
0,75x1+0,6x2 ≤200
x1+x2 ≤300
x1 ≥160
x2 ≥75
Repare que, neste caso, não são necessárias as restrições de não negatividade das variáveis de decisão
devido às restrições para o atendimento mínimo da demanda.
Neste exemplo, resolvemos um problema de planejamento de produção estático. Contudo, em
situações reais, é mais comum realizar o planejamento para diferentes períodos de tempo. Nesses casos,
são necessários modelos dinâmicos, ou seja, que utilizam formulações do tipo multiperíodo.
Problema dinâmico
Nos modelos de programação dinâmica, as disponibilidades de matéria-prima e de mão de obra, e
até os lucros, podem variar ao longo do tempo. Também são considerados os níveis de estoque, visando
sempre atender à demanda em todos os períodos, com o menor custo possível.
A seguir, vamos desenvolver o modelo matemático para um problema de planejamento de produção
dinâmico.
Teoria na prática
Problema do planejamento de produção dinâmico
Uma fábrica de bicicletas está planejando seus níveis de produção para os próximos seis meses. A
fábrica tem capacidade máxima de estocar 6.000 bicicletas. Os dados com relação à produção máxima
mensal, ao custo unitário de produção e à demanda mensal são apresentados na tabela a seguir:
Mês 1 2 3 4 5 6
Custo unitário de produção (R$) 240,00 250,00 265,00 285,00 280,00 260,00
Demanda (unidades) 1.000 4.500 6.000 5.500 3.500 4.000
Produção máxima (unidades) 4.000 3.500 4.000 4.500 4.000 3.500
Dados de produção de bicicletas. Fonte: Adaptado de Ragsdale (2009).
Sabe-se que o estoque inicial do semestre é de 2.750 unidades, e que o custo de estoque é
equivalente a 1,5% do custo unitário de produção no mesmo mês. Desenvolva o modelo matemático para
minimizar o custo total da fábrica no próximo semestre.
O primeiro passo para a modelagem deste exemplo de um clássico problema de planejamento de produção
dinâmico é a definição das variáveis de decisão. As variáveis de decisão devem ser x i, sendo x o número de unidades
de bicicletas a serem produzidas no mês “i”, e ei, sendo e o inventário inicial do mês “i”. Logo, temos:
xi = número de unidades a produzir no mês i, i=1 a 6
ei = inventário inicial mês i, i=1 a 6
Comentário
Repare que pela primeira vez estamos modelando um problema em que o índice da variável de decisão se
refere ao período de tempo, pois estamos analisando a situação ao longo do tempo.
Conhecendo o custo unitário de produção e o custo de estoque de cada mês, conseguimos determinar a função
objetivo para a minimização dos custos da fábrica:
Métodos Quantitativos
Marcio Quirino - 28
Min Z= 240x1+250x2+265x3+285x4+280x5+260x6 + 3,6(e1+e2)/2 + 3,75(e2+e3)/2 + 3,98(e3+e4)/2+ 4,28(e4+e5)/2
+ 4,20(e5+ e6)/2 + 3,9(e6+e7)/2
Observe que o estoque inicial em dado mês equivale ao estoque final do mês anterior, e que estamos
considerando o custo do estoque médio no mês. Assim, para o custo de estoque, consideramos que o nível de estoque
é a média entre o valor de inventário inicial e final do mês.
A produção de unidades de bicicleta por mês deve ser, no mínimo, o suficiente para atender à demanda, porém
não pode superar a produção máxima mensal. Logo, temos as seguintes restrições com relação aos níveis de
produção.2.000≤x1 ≤ 4.000} mês 1
1.750 ≤ x2 ≤3.500} mês 2
2.000 ≤ x3 ≤4.000} mês 3
2.250 ≤ x4 ≤ 4.500} mês 4
2.000 ≤ x5 ≤4.000} mês 5
1.750 ≤ x6 ≤3.500} mês 6
Sabe-se também que a capacidade máxima de estoque na fábrica é de 6.000 unidades de bicicletas. Logo, o
estoque final em cada mês não pode ser superior a essa capacidade máxima, de modo que esta restrição será do tipo
≤.
Como o Estoque final = Estoque inicial + produção - unidades vendidas, temos:
x1 + e1 - 1.000 = 0
Enfim, temos que o modelo para este exemplo do problema de fazer x comprar é:
Min Z= 350x1+400x2+430x3+ 460c1+540c2+580c3
Sujeito a:
Métodos Quantitativos
Marcio Quirino - 31
x1 + c1 = 3.000
x2 + c2 = 2.000
x3 + c3 = 1.000
2x1 + 1,5x2 + 3x3 ≤10.000
x1 + 2x2 + x3 ≤ 6.000
x1, x2, x3, c1, c2, c3 >= 0
É importante ressaltar que a decisão sobre a terceirização é um pouco simplificada, pois focam-se
apenas os aspectos econômicos. Contudo, a terceirização de determinados produtos ou serviços deve incluir
outras considerações além de questões econômicas, devendo, além disso, considerar aspectos estratégicos
como competências essenciais e vantagens competitivas. Ao delegar certos serviços a terceiros
(outsourcing), a empresa pode se concentrar em sua competência central, mantendo-se competitiva no
mercado.
2. Técnica de modelagem nos problemas de transporte e
transbordo
Problemas de transporte
O problema de transportes é a aplicação de programação linear mais frequente na logística.
Esse padrão de problema envolve decisões como o volume a ser transportado entre localidades,
podendo envolver ou não decisões referentes ao desenho da cadeia e também problemas de localização.
O problema de programação linear para o problema clássico de transportes consiste em definir o
melhor caminho (ou rota) para fazer com que determinada quantidade de produtos de um ponto de
suprimento chegue a um ponto de demanda. O objetivo pode ser minimizar as distâncias percorridas, o
custo de transporte ou até mesmo maximizar os níveis de serviço ou o lucro com vendas.
O problema de transporte é um modelo fluxo em grafo bipartido, de modo que não existem nós
intermediários de transbordo ou transição para fluxo, conforme ilustrado.
Rede do problema de transportes.
Atenção
Na rede de transportes, os nós representam os pontos de suprimento e de demanda, enquanto os arcos
representam a conexão entre os nós.
Conforme pode ser observado, no problema de transportes, há m pontos de suprimento, cada um
com capacidade de oferta máxima designada por Si, onde o índice i representa o ponto de suprimento em
Métodos Quantitativos
Marcio Quirino - 32
questão (i = 1,…, m). Existem ainda n pontos de demanda a serem abastecidos por estes pontos de
suprimento. Cada ponto de demanda recebe pelo menos Dj unidades do produto a ser transportado, sendo
que o índice j representa os pontos de demanda, tal que j = 1, …, n. Para cada unidade do ponto de
fornecimento i remetida ao ponto de demanda j incorre um custo cij, que é o custo de fornecer o produto ao
pontode demanda j a partir do ponto de suprimento i.
Assim sendo, para modelar o problema de transportes, consideramos a variável de decisão x ij, que
representa o número de unidades do produto específico despachadas do ponto de suprimento i para o ponto
de demanda j. Considerando que a função objetivo seja minimizar o custo total de transporte, temos que a
função objetivo é:
As condições de transporte estão sujeitas a restrições de fornecimento e de demanda. Logo, o total
transportado para o ponto de demanda tem que, ao menos, atender à quantidade mínima demandada,
enquanto o total transportado a partir do ponto de suprimento não pode ser superior à sua capacidade de
oferta. Logo, as restrições para o problema clássico de transportes podem ser representadas pelas seguintes
equações:
Em suma, o modelo matemático para o problema clássico de transporte é:
Sujeito a:
Para facilitar o entendimento do modelo matemático para o problema clássico de transportes, vamos
resolver o exemplo a seguir:
Métodos Quantitativos
Marcio Quirino - 33
Teoria na prática
Problema de transporte
Uma empresa fabricante de bicicletas conta com duas plantas, uma localizada em São Paulo e outra
em Recife. A empresa atende ao público por meio de três revendedores, localizados em Porto Alegre,
Brasília e Manaus.
Rede do problema de transportes.
Plantas
Custos de envio por unidade
Ofertas Mercados
Porto Alegre Brasília Manaus
SP 25 30 70 600
Recife 60 35 50 700
Demandas 450 500 300
Distâncias para a rede do problema de transportes. Fonte: Renata Albergaria de Mello Bandeira
Formule o problema de programação linear que minimize os custos de distribuição da empresa.
Consideramos que i=1 para São Paulo e i=2 para Recife, enquanto j=1 para Porto Alegre, j=2 para Brasília e
j=3 para Manaus. Logo, as variáveis de decisão são:
x11= quantidade de produtos transportados de São Paulo para Porto Alegre;
x12= quantidade de produtos transportados de São Paulo para Brasília;
x13= quantidade de produtos transportados de São Paulo para Manaus;
x21= quantidade de produtos transportados de Recife para Porto Alegre;
x22= quantidade de produtos transportados de Recife para Brasília;
x23= quantidade de produtos transportados de Recife para Manaus.
A função objetivo para minimizar o custo total de transporte é:
Minz Z=25X11+30X12+70X13+60X21+35X22+50X23
O total transportado para Porto Alegre tem que ser, ao menos, igual a 450, para atender à demanda mínima
da cidade. Para Brasília e Manaus, devem ser transportadas, no mínimo, 500 e 300 bicicletas, respectivamente. Assim,
as restrições referentes à demanda são:
X11+X21 ≥450 à restrição quanto → demanda para Porto Alegre;
X12+X22 ≥500à restrição quanto → demanda para Brasília;
X13+X23 ≥300à restrição quanto → demanda para Manaus.
O total transportado de São Paulo não pode ser superior a 600 unidades, pois trata-se da capacidade máxima
de oferta da planta. Já o total transportado de Recife deve ser inferior a 700 unidades, que é a capacidade máxima de
oferta desta planta. Assim, as restrições referentes à oferta são:
X11+X12+X13+≤600à restrição quanto ao suprimento de São Paulo;
X21+X22+X23≤700à restrição quanto ao suprimento de Recife.
Métodos Quantitativos
Marcio Quirino - 34
O modelo matemático deste problema é:
Minz Z=25X11+30X12+70X13+60X21+35X22+50X23
Sujeito a:
X11+X21 ≥450
X12+X22 ≥500
X13+X23 ≥300
X11+X12+X13≤600
X21+X22+X23≤700
X11, X12, X13, X21, X22, X23≥0
Saiba mais
Os problemas de transporte são casos particulares de problemas de programação linear, de modo que sua
resolução algébrica pode ser desenvolvida por algoritmos de programação linear. Entretanto, é possível aproveitar as
particularidades do problema de transporte para resolvê-lo de forma mais eficiente que o caso geral do simplex. Assim,
existem algoritmos específicos para a solução do problema de transporte, como o Método do Canto Noroeste e o
Método de Vogel, porém não vamos abordá-los aqui. Caso você tenha interesse em aprofundar os seus
conhecimentos, recomenda-se a leitura do capítulo 7 de Winston (2004).
Problema de transbordo
O problema de transbordo segue lógica semelhante ao problema de transportes, porém este não é
um modelo fluxo em grafo bipartido, pois existem nós intermediários de transbordo ou de transição para
fluxo, conforme ilustrado na figura a seguir:
Rede do problema de transbordo.
Além de um conjunto de m nós, que representam os pontos de suprimentos, e n nós, que
representam os pontos de demanda, a rede também dispõe de l pontos de transbordo.
É importante que você saiba bem a diferença entre estes diferentes tipos de nó:
A. Pontos de suprimento
✓ São responsáveis pelo fornecimento de insumos, de modo que podem remetê-los para outros
pontos, porém não podem recebê-los.
B. Pontos de demanda
✓ São os pontos de consumo, de modo que devem receber insumos de outros pontos, porém
não podem recebê-los.
C. Pontos de transbordo
✓ Podem tanto receber insumos de outros pontos quanto remeter insumos para outros pontos,
ou seja, são locais onde é possível realizar a transferência da carga. Um centro de
distribuição, por exemplo, pode funcionar como um ponto de transbordo em uma cadeia
Métodos Quantitativos
Marcio Quirino - 35
logística, recebendo insumos de diversas plantas ou diversos fornecedores, realizando a
consolidação da carga e remetendo insumos para outras plantas, outros centros de
distribuição ou clientes. Um depósito também é um bom exemplo de um ponto de transbordo.
Uma particularidade do problema de transbordo é que aquilo que é transportado das unidades
intermediárias (de transbordo) aos mercados consumidores não deve ultrapassar a quantidade de produto
que chega a tais pontos.
A quantidade que insumos que chega a um ponto de transbordo deve ser igual à quantidade de
insumos que sai dele.
Com essa restrição, garantimos o equilíbrio do fluxo neste nó, ou seja, o fluxo que entra deve ser
igual a todo o fluxo que sai. Portanto, o modelo matemático para o problema de transbordo é semelhante ao
do problema clássico de transporte, porém acrescenta-se a restrição de equilíbrio nos nós que representam
pontos de transbordo.
Temos que o modelo matemático para o problema de transbordo é:
Sujeito a:
Para facilitar o entendimento do modelo matemático para o problema clássico de transbordo, vamos
resolver o exemplo a seguir:
Teoria na prática
Problema de transbordo
Uma empresa fabricante de bicicletas conta com duas plantas, uma localizada em São Paulo e outra
em Recife, e atende o público por meio de dois revendedores, localizados em Porto Alegre e Manaus. A
empresa também dispõe de um centro de distribuição, localizado em Brasília, que pode ser usado como
ponto de transbordo caso contribua para reduzir o custo total de transporte.
Métodos Quantitativos
Marcio Quirino - 36
Rede do problema de transbordo.
Plantas/CD
Custos de envio por unidade
Ofertas
Mercados/CD
Porto Alegre Manaus Brasília
SP 25 70 30 600
Recife 60 50 35 700
Brasília 45 65 0
Demandas 450 500
Demandas e custos de transporte por unidade. Fonte: Renata Albergaria de Mello Bandeira
Consideramos que i=1 para São Paulo, i=2 para Recife e i=3 para Brasília, enquanto j=1 para Porto Alegre, j=2
para Manaus e j=3 para Brasília. Logo, as variáveis de decisão são:
x11= quantidade de produtos transportados de São Paulo para Porto Alegre;
x12= quantidade de produtos transportados de São Paulo para Manaus;
x13= quantidade de produtos transportados de São Paulo para Brasília;
x21= quantidade de produtos transportados de Recife para Porto Alegre;
x22= quantidade de produtos transportados de Recife para Manaus;
x23= quantidade de produtos transportados de Recife para Brasília;
x31= quantidade de produtos transportados de Brasília para Porto Alegre;
x32= quantidadede produtos transportados de Brasília para Manaus.
A função objetivo para minimizar o custo total de transporte é:
Min Z=25X11+70X12+30X13+60X21+50X22+35X23+45X31+65X32
O total transportado para Porto Alegre tem que ser, ao menos, igual a 450, para atender à demanda mínima
da cidade. Para Brasília e Manaus, devem ser transportadas, no mínimo, 500 e 300 bicicletas, respectivamente. Assim,
as restrições referentes à demanda são:
X11+X21 +X31≥450 → restrição quanto à demanda para Porto Alegre;
X12+X22 +X32≥500 → restrição quanto à demanda para Manaus.
O total transportado de São Paulo não pode ser superior a 600 unidades, pois esta é a capacidade máxima de
oferta da planta. Já o total transportado de Recife deve ser inferior a 700 unidades, que é a capacidade máxima de
oferta desta planta. Assim, as restrições referentes à oferta são:
X11+X12+X13+≤600 → restrição quanto ao suprimento de São Paulo;
X21+X22+X23≤700 → restrição quanto ao suprimento de Recife.
Lembre-se ainda da restrição de equilíbrio nos nós que representam pontos de transbordo. Tudo o que chega
no centro de distribuição de Brasília deve ser igual ao que sai de Brasília, conforme indicado na equação a seguir:
Métodos Quantitativos
Marcio Quirino - 37
X11+ X23+=X31+X32
O modelo matemático deste problema é:
Min Z=25X11+70X12+30X13+60X21+50X22+35X23+45X31+65X32
Sujeito a:
X11+X21 +X31≥450
X12+X22 +X32≥500
X11+X12+X13+≤600
X21+X22+X23≤700
X11+ X23+=X31+X32
X11, X12 , X13, X21, X22, X23, X31,X32 ≥0
3. Técnica de modelagem em problemas de alocação
Problemas de alocação
No problema de alocação, também denominado problema de designação ou de matching, existem
dois conjuntos e devem ser formados pares entre os elementos destes dois conjuntos.
O problema consiste em determinar a formação destes pares, ou seja, a combinação destes
elementos de modo a minimizar o custo total de todas as alocações, respeitando as restrições existentes.
Atenção
O problema da alocação visa designar tarefas a designados, podendo ser pessoas, máquinas, veículos ou até
mesmo fábricas. Neste tipo de problema, há um custo associado para o designado desempenhar cada tarefa. Assim,
o objetivo final é determinar a combinação de alocações que minimiza o custo total.
Também pode ser considerado que cada designado i tem determinado interesse em efetuar cada
tarefa j, dado por pij. Logo, o objetivo é realizar a alocação de maneira que a soma dos interesses seja
maximizada.
Atenção
Destaca-se que, no problema de alocação, o número de designados e de tarefas devem ser iguais. Assim,
temos n designados e n tarefas. Cada tarefa deve ser atribuída a apenas um designado, que também só deve realizar
uma única tarefa. Além disso, todas as tarefas devem ser executadas.
O problema da alocação pode ser considerado um caso especial do modelo de transportes, no qual
cada origem tem uma unidade disponível e cada destino requer também uma unidade. Assim, o problema
de alocação é um problema de transporte balanceado, no qual todas as demandas e capacidades são iguais
a 1. Desse modo, o problema de alocação utiliza variáveis binárias. A variável binária, ou booleana, pode
assumir apenas dois valores, zero ou 1. No problema de alocação, a variável de decisão x ij recebe o valor
igual a “1” se decidirmos que a tarefa “i” será alocada para o designado “j”, sendo “0” se decidirmos o
contrário. De tal forma, temos que o modelo matemático para o problema da alocação é:
Sujeito a:
Métodos Quantitativos
Marcio Quirino - 38
Saiba mais
Os modelos de alocação podem ser adotados para auxiliar no processo de tomada de decisão em diversas
situações reais, tal como na determinação da escala de vendedores para pontos de venda, na distribuição de atividades
para membros de uma equipe ou na alocação de máquinas para resolver diferentes tarefas.
Para facilitar o entendimento do modelo matemático para o problema clássico de alocação, vamos
resolver o exemplo a seguir:
Teoria na prática
A supervisora de uma equipe de limpeza em um hotel necessita formar equipes de camareiras para
realizar a limpeza dos quartos na hora de troca de hóspedes. Os hóspedes que estão realizando check-out
precisam sair do quarto até às 12h, enquanto os novos hóspedes podem realizar o check-in a partir de 14h.
Assim, as esquipes têm pouco tempo para organizar e limpar todos os cômodos. Logo, a supervisora precisa
organizar as equipes de modo que os serviços sejam realizados o mais rápido possível.
A supervisora precisa formar a equipe para cuidar dos quartos do terceiro andar do hotel. As tarefas
a serem realizadas são: arrumar as camas, limpar o banheiro, varrer o quarto e tirar o pó. As camareiras
desempenham as tarefas, por quarto, nos seguintes tempos:
Camareira
Tarefa
Arrumar cama Limpar banheiro Varrer quarto Tirar o pó
Lara 2 min 5 min 7 min 3 min
Ana 3 min 6 min 8 min 4 min
Julia 4 min 4 min 6 min 5 min
Talita 2 min 5 min 7 min 2 min
Tempo para execução das tarefas Fonte: Renata Albergaria de Mello Bandeira
Formule o problema de programação linear que minimize o tempo de arrumação do quarto.
Neste problema de alocação, a variável de decisão xij recebe o valor igual a “1” se decidirmos que a tarefa “i”
será alocada para o designado “j”, sendo “0” se decidirmos o contrário. De tal forma, temos:
x11= 1, se Lara arruma a cama; zero, caso contrário;
x12= 1, se Lara limpa banheiro; zero, caso contrário;
x13 =1, se Lara varre o quarto; zero, caso contrário;
x14=1, se Lara tira o pó; zero, caso contrário;
x21= 1, se Ana arruma a cama; zero, caso contrário;
x22= 1, se Ana limpa banheiro; zero, caso contrário;
x23= 1, se Ana varre o quarto; zero, caso contrário;
x24= 1, se Ana tira o pó; zero, caso contrário;
Métodos Quantitativos
Marcio Quirino - 39
x31= 1, se Julia arruma a cama; zero, caso contrário;
x32= 1, se Julia limpa banheiro; zero, caso contrário;
x33= 1, se Julia varre o quarto; zero, caso contrário;
x34= 1, se Julia tira o pó; zero, caso contrário;
x41= 1, se Talita arruma a cama; zero, caso contrário;
x42= 1, se Talita limpa banheiro; zero, caso contrário;
x43= 1, se Talita varre o quarto; zero, caso contrário;
x44= 1, se Talita tira o pó; zero, caso contrário.
O modelo matemático para o problema da alocação é:
Min Z= 2X11+5X12+7X13+3X14+3X21+6X22+8X23+4X24+4X31+4X32+6X33+5X34+2X41+5X42+7X43+2X44
Sujeito a:
X11+X12+X13+X14=1
X21+X22+X23+X24=1
X31+X32+X33+X34=1 Cada trabalhador desempenha apenas uma tarefa.
X41+X42+X43+X44=1
X11+X21+X31+X41=1
X13+X23+X33+X43=1
X12+X22+X32+X42=1 Cada tarefa é alocada para apenas um trabalhador.
X14+X24+X34+X44=1
X11, X12, X13, X14, X21, X22, X23, X24, X31, X32, X33, X34, X41, X42, X43, X44 ꞓ {0,1}
Saiba mais
Assim como o problema de transportes, o problema da alocação também é um caso particular de problemas
de programação linear, de modo que sua resolução algébrica pode ser desenvolvida por algoritmos de programação
linear. Porém, tal como o problema de transportes, possui particularidades específicas que podem ser aproveitadas
para resolvê-lo de forma mais eficiente. Assim como para a solução do problema de transporte, com o Método do Canto
Noroeste e o Método de Vogel, também existem algoritmos específicos para a solução do problema de alocação, a
exemplo do algoritmo húngaro. Porém, não vamos abordá-los aqui. Caso você tenha interesse em aprofundar os seus
conhecimentos, recomenda-se a leitura do capítulo 7 de Winston (2004).
Considerações Finais
Vimos como a Pesquisa Operacional pode auxiliar no apoio a processos de decisão, em especial
para problemas complexos. Ao longo dos módulos, aprendemos sobre modelos matemáticos e como estes
podem nos ajudar na análise de decisão, em especial por permitirem avaliar a solução do problema em
diferentes cenários a um menor tempo e custo. Além disso, colocamos estes conceitos em práticaà medida
que aprendemos a construir modelos matemáticos para problemas de programação linear.
Métodos Quantitativos
Marcio Quirino - 40
Entretanto, é preciso ter em mente que a modelagem não é uma tarefa simples, principalmente para
aqueles que estão iniciando neste campo do conhecimento. Assim, para nos familiarizarmos com a técnica
de modelagem e podermos construir modelos com mais facilidade, é preciso praticar por meio de exercícios.
A prática é essencial para nos ajudar a entender e a dominar a lógica por trás da modelagem matemática.
Outro ponto que também facilita a internalização deste conhecimento é entender que alguns modelos,
conhecidos como problemas típicos, seguem padrões semelhantes. Portanto, se entendemos a lógica por
trás dessa “categoria” de problemas, conseguiremos modelar os demais problemas desta mesma classe.
Por isso, é importante conhecer esses padrões!
No módulo 1, apresentamos os problemas clássicos da mistura, do planejamento de produção e de
estoques, e fazer versus comprar. Dedicamos os módulos 2 e 3 para entender a lógica do problema de
transporte e de seus casos particulares. O destaque para o problema de transporte ocorre porque trata-se
do modelo de programação linear mais aplicado na área da logística. Abordamos, ainda, no módulo 2 o
problema de transbordo, enquanto no módulo 3 tratamos especificamente do problema de alocação.
Até o momento, aprendemos a solucionar os modelos matemáticos por meio da aplicação do Método
Gráfico. Contudo, tal método é restrito a problemas mais simples, com até duas variáveis de decisão.
Referências
DiSERIO, L.; SAMPAIO, M. Projeto da cadeia de suprimento: uma visão dinâmica da decisão fazer
versus comprar. In: Revista de Administração de Empresas, v. 41, n. 1, p. 54-66, 2001.
GOLDBARG, M. C.; LUNA, H. P. Otimização combinatória e programação linear. 2. ed. São Paulo:
Campus, 2005.
LACHTERMACHER, G. Pesquisa operacional na tomada de decisões. Rio de Janeiro: LTC, 2016.
RAGSDALE, C. T. Modelagem e análise de decisão. São Paulo: Cengage Learning, 2009.
RODRIGUES, L. H.; AHLERT, F.; LACERDA, D. P.; CAMARGO, L. F. R.; LIMA, P. Pesquisa
operacional: programação linear passo a passo: do entendimento do problema à interpretação da solução.
São Leopoldo: Unisinos, .
SLACK, N.; CHAMBERS, S.; HARLAND, C.; HARRISON, A.; JOHNSTON, R. Administração da
produção. São Paulo: Atlas, 1997.
STIGER, G. J. The cost of Subsistence. Journal of Farm Economics 27(2), p. 303-314, 1945.
WINSTON, W. L.; GOLDBERG, J. B. Operations research: applications and algorithms. Vol. 3.
Boston: Cengage Learning, 2004.
Explore+
Para obter mais conhecimento sobre os conteúdos discutidos, sugerimos a seguinte leitura:
WINSTON, W. L.; GOLDBERG, J. B. Operations research: applications and algorithms. Vol. 3.
Boston: Cengage Learning, 2004.
Métodos Quantitativos
Marcio Quirino - 41
Dualidade e Análise de Sensibilidade
Descrição
O problema dual, o método dual-simplex e a relevância da análise de sensibilidade.
Propósito
Dominar a técnica da dualidade facilitará solução de problemas complexos de programação linear.
Por sua vez, a análise de sensibilidade o ajudará a responder a diversas questões gerenciais, relacionadas
a solução de problemas de programação linear, incerteza ou erros de estimativa quanto aos coeficientes do
modelo.
Preparação
Para o estudo deste conteúdo, são necessários uma calculadora e um software editor de planilhas
eletrônicas com o add in do Solver habilitado. Conhecimento sobre o método simplex e modelos de
programação linear
Introdução
Você já deve saber como desenvolver modelos matemáticos que representem, de forma simplificada,
um problema complexo para o qual desejamos encontrar a solução ótima, utilizando equações lineares.
Esses modelos nos auxiliam no processo de tomada de decisão, na medida em que nos permitem minimizar
custos, maximizar resultados e aprimorar as configurações operacionais em diversos problemas práticos
importantes.
Problemas de programação linear tratam de alguns problemas representativos que você poderia
enfrentar no ambiente empresarial, tais como: o problema da mistura; a decisão entre fabricar ou comprar;
o problema do planejamento de produção e de estoques; o problema de transporte e de transbordo; e
problemas de alocação. É possível solucioná-los por meio do método gráfico, do método simplex ou com o
auxílio de ferramentas computacionais, que facilitam bastante o nosso trabalho!
Entretanto, é importante compreender que encontrar a solução ótima para um problema nem sempre
significa que ele esteja resolvido! No processo de modelagem, assumimos premissas e fazemos estimativas
(às vezes incertas) com relação aos custos ou mesmo quanto à demanda ou à disponibilidade de recursos
em determinada situação ou em um período. A análise de sensibilidade trata exatamente de avaliar o
impacto dessas incertezas na solução ótima, avaliando os erros de estimativa quanto aos coeficientes do
modelo ou quanto a mudanças que possam ocorrer.
Lachtermacher (2009) reforça a importância de realizar essa análise pós-otimização, verificando as
possíveis variações dos valores dos coeficientes da função objetivo, dos coeficientes e das constantes das
restrições, sem que a solução ótima seja alterada. Destaca-se que a análise de sensibilidade está
relacionada ao problema dual associado ao primal. A dualidade nos permite – além de análises econômicas,
como variações marginais – resolver o problema, dependendo do número de restrições e de variáveis, de
forma mais eficiente computacionalmente.
1. Dualidade para solução de problemas de programação
linear
O problema dual e o método dual-simplex
O conceito de dualidade está relacionado à possibilidade do tratamento de duas naturezas distintas
em uma mesma entidade. Arenales et al. (2007) destacam que diversos fenômenos físicos e químicos
Métodos Quantitativos
Marcio Quirino - 42
podem ser representados por modelos com estruturas e comportamentos iguais, porém interpretados de
formas distintas.
Especificamente em programação matemática, podemos afirmar que todo problema de programação
linear tem um dual correspondente, sendo o problema original denominado primal.
Entender o conceito de dualidade é importante para interpretar a solução de problemas de
otimização, bem como para o aprendizado de tópicos mais avançados em programação matemática.
Métodos de decomposição, por exemplo, têm base na teoria primal-dual. Além disso, podemos obter
melhorias em termos de algoritmos ao levar em conta a contraparte dual, tal como no método dual-simplex.
Existe uma série de relações e teoremas entre o primal e o dual, na qual se destacam:
A. O dual do dual é o primal.
B. Se um dos dois problemas apresenta uma solução ótima, o outro necessariamente também,
sendo que o valor de ambas as soluções coincide (teorema da dualidade forte).
C. Uma solução viável do problema dual representa um limite superior para o problema primal
(teorema da dualidade fraca).
D. Se o primal é um problema inviável, o seu dual é ilimitado.
E. Se o primal é um problema ilimitado, o seu dual é inviável.
F. O número de variáveis do dual é igual ao número de restrições do primal.
G. O número de restrições do dual é igual ao número de variáveis do primal.
H. O sentido da otimização é sempre inverso entre o primal e o dual, ou seja, se o primal é um
problema de maximização, o dual é de minimização. Por sua vez, se o primal for um problema
de minimização, seu dual é de maximização.
I. Os termos independentes do primal surgem como coeficientes na função objetivo no dual e vice-
versa.
J. Os termos constantes das restrições do dual são os coeficientes das variáveis da função objetivo
do primal, enquanto os coeficientes das variáveis da função objetivo do dual são os termos
constantes das restrições do primal.
K. A matriz doscoeficientes do dual é a transposta da matriz dos coeficientes do primal.
L. Complementaridade das folgas: Seja fi a variável de folga associada à restrição i. Seja yi a variável
dual associada à restrição i. Assim, yifi = 0, para todo i. O yi representa o preço-sombra (valor
marginal) de um recurso. Logo, quando fi ≥ 0, yi = 0. Quando si = 0, yi ≥ 0.
Em suma, existe um conjunto de regras para se obter o dual de um problema de programação linear,
sintetizado na tabela a seguir.
Par assimétrico
Problema primal (dual) Problema dual (primal)
Maximizar Minimizar
Termos independentes Coeficientes da Função Objetivo (FO)
Coeficientes da Função Objetivo (FO) Termos independentes
i-ésima linha de coeficientes
tecnológicos
i-ésima coluna de coeficientes
tecnológicos
j-ésima coluna de coeficientes
tecnológicos
j-ésima linha de coeficientes
tecnológicos
Restrição com relação tipo: Variável tipo:
≤ Não negativa
≥ Não positiva
= Sem restrição de sinal
Variável tipo: Restrição com relação tipo:
Não negativa ≥
Não positiva ≤
Sem restrição de sinal =
Tabela: Conversão de problemas em geral
Métodos Quantitativos
Marcio Quirino - 43
Com base nas regras apresentadas na tabela, conseguimos achar o dual de qualquer problema de
programação linear. Vamos treinar, determinando o dual para o seguinte problema de programação linear
primal:
Max ZP = 6X1 + 4X 2+ 10X3
X1+ 3X2 + 2X3 ≤ 15
2X2-X3 ≥ 5
2X1 + X2 - 5X3 = 10
X1, X2, X3 ≥ 0
Se o primal é um problema de maximização, sabemos que o dual é um problema de minimização.
Sabemos, também, que os termos independentes do primal são os coeficientes da função objetivo do dual.
Desse modo, a função objetivo do dual é:
Min ZD = 15Y1 + 5Y2 + 10Y3
Sabemos ainda que os coeficientes da função objetivo do primal são os termos independentes do
dual. A matriz dos coeficientes do dual é a transposta da matriz dos coeficientes do primal. Além disso,
variáveis não negativas no primal implicam restrições do tipo ≥ no dual. Assim, conseguimos determinar as
restrições para o dual, que são:
Y1 + Y3 ≥6
3Y1 + 2Y2 + Y3 ≥ 4
2Y1 - Y2 - 5Y3 ≥ 10
Ainda é preciso determinar os tipos de variáveis. Como a restrição 1 do primal é ≤, temos que y1 ≥0.
A restrição 2 do primal é ≥, logo, y2 é não positiva (y2 ≤ 0). A restrição 3 é uma equação, logo y3 é irrestrita
(y3 € IR). Assim, chegamos à conclusão de que o dual para o problema apresentado é:
Min ZD = 15Y1 + 5Y2 + 10Y3
s.a Y1 + Y3 ≥ 6
3Y1 + 2Y2 + Y3 ≥ 4
2Y1 - Y2 - 5Y3 ≥ 10
Y1 ≥ 0
Y2 ≤ 0
Y3 € IR
Para fixar a aprendizagem, veja agora como determinar o dual do problema a seguir:
Min W = 50Y1 + 20 Y2 + 30Y3 + 80Y4
s.a 400Y1 + 200Y2 + 150Y3 + 500Y4 > 500
3Y1 + 2Y2 > 6
2Y1 + 2Y2 + 4Y3 + 4Y4 > 10
2Y1 + 4Y2 + Y3 + 5Y4 > 8
Y1, Y2, Y3,Y4 > 0
Métodos Quantitativos
Marcio Quirino - 44
Se o primal é um problema de minimização, sabemos que o dual é um problema de maximização.
Os termos independentes do primal são os coeficientes da função objetivo do dual. Desse modo, a função
objetivo do dual é :
Max Z = 500X1 + 6X2 + 10X3 + 8X4
Os coeficientes da função objetivo do primal são os termos independentes do dual, e a matriz dos
coeficientes do dual é a transposta da matriz dos coeficientes do primal. Além disso, variáveis não negativas
no primal implicam restrições do tipo ≥ no dual. Logo, as restrições para o dual são:
400X1 + 3X2 + 2X3 + 2X4 ≥ 50
200X1 + 2X2 + 2X3 + 4X4 ≥ 20
150X1 + 4X3 + X4 ≥ 30
500X1 + 4X3 + 5X4 ≥ 80
Por fim, deve-se determinar os tipos de variáveis. Como as restrições do primal são ≥, as variáveis
X são não positivas (X ≤ 0). Assim, chegamos à conclusão de que o dual para o problema apresentado é:
Max Z = 500X1 + 6X2 + 10X3 + 8X4
s.a 400X1 + 3X2 + 2X3 + 2X4 ≥ 50
200X1 + 2X2 + 2X3 + 4X4 ≥ 20
150X1 + 4X3 + X4 ≥ 30
500X1 + 4X3 + 5X4 ≥ 80
X1, X2, X3 X4 ≥ 0
Interpretação econômica do problema dual
O número de variáveis do problema dual é igual ao número de restrições do problema primal. Vale
notar que as variáveis originais do problema dual estão associadas às variáveis de folga/excesso do
problema primal. De fato, as variáveis originais do problema dual (y i) representam economicamente o valor
marginal do recurso da restrição i em relação ao valor da função objetivo, ou seja, o preço-sombra. Trata-se
do valor pelo qual a função objetivo seria melhorada caso a quantidade do recurso i fosse aumentada em
uma unidade.
Como foi apresentado, há o teorema da complementaridade das folgas, em que y ifi = 0 para todo
i. Esse teorema pode ser interpretado em função do preço-sombra, como descrito a seguir:
A. Quando a variável de folga (fi) para a restrição i é não negativa, há sobra do recurso i. Assim,
não faz sentido ter um valor marginal para o recurso, de modo que o preço-sombra (yi) deve
ser zero.
B. Quando a variável de folga (fi) para a restrição i é nula, todo o recurso i está sendo consumido,
não havendo assim sobra dele. Logo, o preço-sombra deve ser maior que zero.
O conceito de preço-sombra pode parecer um pouco abstrato, então, vamos trabalhar um exemplo
para ajudar na compreensão desse conceito e na interpretação econômica do problema dual.
Caso Fitwear S.A.
A Fitwear S.A. é uma confecção de roupas esportivas, tendo uma linha fitness feminina que produz roupas de
ginástica exclusivas para mulheres, como tops e calças de lycra.
Métodos Quantitativos
Marcio Quirino - 45
Cada top de ginástica, vendido por $80,00, gasta $20,00 de matéria-prima, como tecido e alinhamentos, e
$32,00 de mão de obra. Trinta minutos de corte e 15 minutos de costura são demandados para a confecção de uma
unidade desse produto.
Cada calça de ginástica, vendida por $120,00, utiliza $35,00 de matéria-prima, como tecido e alinhamentos, e
$40,00 de mão de obra. Quinze minutos de corte e 30 minutos de costura são demandados para a confecção de uma
unidade desse produto.
Por semana, a Fitwear só pode contar com 100 horas de corte e 160 horas de costura. Qual deve ser o plano
de produção (quantos tops e quantas calças de ginástica devem ser produzidas) para maximizar os lucros da empresa?
Consideramos as seguintes variáveis:
A. x1
✓ Número de tops de ginástica confeccionados a cada semana.
B. x2
✓ Número de calças de ginástica confeccionadas a cada semana.
Temos a seguinte formulação matemática:
Max Z = 28X1 + 40X2
s.a
0,5X1 + 0,25X2 ≤ 100 → restrição de horas de corte
0,25X1 + 0, 5X2 ≤ 160 → restrição de horas de costura
X1, X2 ≥ 0 → restrição de não negatividade das variáveis de decisão
Teoria na prática
Agora imagine que uma grande indústria têxtil estivesse disposta a comprar todos os recursos da
Fitwear (sua capacidade de corte e de costura). Qual seria o preço de equilíbrio mínimo a partir do qual a
Fitwear poderia abrir mão da fabricação?
Sejam y1 e y2 os preços de equilíbrio referentes à capacidade da Fitwear em horas de corte e de costura,
respectivamente. A grande indústria têxtil deseja então minimizar o total a ser pago pela capacidade de corte e de
costura da Fitwear, ou seja, a função objetivo do dual está relacionada ao ponto de vista do comprador:
Função objetivo
O comprador deseja o menor preço, mas este deve ser atraente o suficiente para que a Fitwear considere a
venda. Assim sendo, para comprar toda a capacidade (horas) de corte e de costura necessária para confeccionar um
top de ginástica, o ágio a ser pago deve ser, no mínimo, o que a Fitwear lucraria com a venda do produto. O mesmo
se passa com a calça de ginástica. Logo, as condições para realizar o negócio seriam:
Métodos Quantitativos
Marcio Quirino - 46
Condiçõesdo negócio
Portanto, o problema dual da Fitwear pode ser formulado assim:
Min W = 100Y1 + 160Y2
s.a 0,5Y1 + 0,25Y2 ≥ 28
0,25Y1 + 0,5Y2 ≥ 40
A solução ótima é dada por: y1 = 0, y2 = 80, w = 12.800. Observe que, na conjuntura do problema,
assumindo a indiferença entre produzir ou vender para a indústria têxtil, a capacidade de corte (horas de
corte) excedente não tem preço para a Fitwear. Por sua vez, o ágio a ser cobrado por 1 hora de costura é
de $80,00.
Dualidade na eficiência computacional para a solução de problemas
de programação linear
Como você viu, uma das razões para o estudo dos problemas duais está relacionada ao número de
restrições. Algumas vezes, em termos computacionais, é mais eficiente resolver o problema dual do que o
seu primal, em função de número de restrições e variáveis, uma vez que a solução ótima do dual é sempre
igual à de seu primal. Para facilitar o entendimento desse conceito, considere o problema primal a seguir:
Max Z = 10X1 - 4X2 + 7X3,
s.a 3X1 - X2 + 2X3 0
Regras para identificação da solução ótima na Tabela Simplex ótima
do primal
Sabemos que a solução ótima do dual é sempre igual à solução ótima do primal. Porém, como ler a
solução ótima do dual a partir da Tabela Simplex ótima do problema primal?
Fogliatto (2004) sistematizou as regras para identificação da solução ótima do dual na linha z da
Tabela Simplex ótima do primal. Essas regras são apresentadas a seguir:
Métodos Quantitativos
Marcio Quirino - 47
2. Sensibilidade da solução obtida para problemas de
programação linear em relação à incerteza ou erros de
estimativa quanto aos coeficientes do modelo
O que é a análise de sensibilidade
A análise de sensibilidade, também chamada de análise pós-otimalidade, consiste em avaliar os
impactos que variações nos parâmetros podem provocar na solução ótima do problema em estudo. A partir
dessa análise, é possível verificar como alterações nos parâmetros iniciais de um problema de programação
linear afetam a sua solução ótima e identificar os valores alternativos dos parâmetros que levariam a uma
nova solução para o problema.
Em outras palavras, a análise de sensibilidade permite avaliar como variações na disponibilidade de
recursos ou variações nos coeficientes da função objetivo (custos, preço etc.) afetam a solução ótima, sem
ser necessária a resolução do problema novamente.
Como alguns problemas envolvem um grande número de variáveis e restrições, exigindo muito tempo
computacional para a sua solução, essa é uma grande vantagem!
É importante ressaltar que, ao construirmos um modelo matemático para um problema de
programação linear, assumimos valores exatos para os coeficientes desse modelo. No entanto, na realidade,
eles podem sofrer alterações constantemente. Os preços que uma empresa cobra por seus produtos podem
mudar, ou um fornecedor pode ter uma redução na sua capacidade de produção e, com isso, diminuir a
disponibilidade de oferta de determinado produto. Um funcionário, por exemplo, pode ficar doente e faltar,
alterando assim a produtividade da fábrica.
Atenção
São diversas as situações que podem nos levar a incertezas com relação aos valores dos coeficientes. Por
isso, torna-se fundamental compreender o quão sensível é a solução de um modelo de programação linear a essas
possíveis alterações.
Métodos Quantitativos
Marcio Quirino - 48
Por meio da análise de sensibilidade, é possível identificar em quantas unidades a disponibilidade
de um dado recurso pode variar ou qual é a maior variação admissível nos coeficientes da função objetivo
sem que seja alterada a base ótima. Assim, esse tipo de avaliação faz com que a análise de sensibilidade
seja um dos tópicos mais importantes em programação linear.
A análise de sensibilidade estuda como um modelo de programação matemática se comporta quando
submetido a mudanças em suas condições iniciais, tais como:
• Mudança no vetor de custos (das variáveis básicas e não básicas).
• Mudança no vetor de termos independentes.
• Mudanças nos coeficientes das variáveis.
• Acréscimo de restrições.
• Acréscimo de novas variáveis.
É preciso destacar que conseguimos analisar todas essas mudanças por meio do Solver. Após
resolver um problema de programação linear, o Solver fornece uma análise de sensibilidade, informando
sobre diversas situações, como: a faixa de valores que os coeficientes da função objetivo podem assumir
sem alterar a solução ótima; o impacto provocado por alterações na disponibilidade dos diversos recursos
limitados sobre o valor ótimo da função objetivo; o impacto que alterações nos coeficientes das restrições
terão sobre a solução ótima do problema etc.
Problema Glass Co.
Como ilustração das mudanças abordadas no tópico anterior, examine cada um dos casos no
exemplo da Glass Co.
Glass Co.
A empresa Glass Co., que possui três fábricas, produz janelas e portas de vidro. As esquadrias e ferragens em
aço são feitas na fábrica 1, as esquadrias de madeira são produzidas na fábrica 2, e a fábrica 3 produz o vidro e monta
os produtos.
A direção da empresa decidiu modernizar a linha de produtos e propôs o lançamento de duas novidades:
• Produto 1: porta de vidro de 2,5m com esquadria de alumínio.
• Produto 2: janela adornada com esquadria de madeira 1,2m x 1,8m.
O produto 1 requer capacidade produtiva das fábricas 1 e 3. O produto 2 precisa das fábricas 2 e 3. A divisão
de marketing concluiu que a empresa poderia vender tanto quanto fosse possível produzir desses produtos por essas
fábricas. Porém, ambos os produtos competem por capacidade produtiva da fábrica 3, não estando claro qual mix dos
dois produtos seria mais lucrativo. É preciso então determinar quais devem ser as taxas de produção para maximizar
o lucro total sujeitas às restrições impostas pela capacidade produtiva:
Fábrica
Tempo de produção por lote (em horas) Tempo de produção disponível
por semana (horas) Produtos
1 2
1 1 0 4
2 0 2 12
3 3 2 18
Lucro por lote $3.000,00 $5.000,00
Tabela: Produção empresa Glass Co. extraída de Hillier e Lieberman, 2013, pág. 21
No caso da Glass Co., a empresa deve decidir os produtos a serem fabricados. Logo, a definição da
variável de decisão é:
A. X1
✓ Quantidade de lotes produtos 1 fabricados.
Métodos Quantitativos
Marcio Quirino - 49
B. X2
✓ Quantidade de lotes produtos 2 fabricados.
Para cada lote de portas de vidro de 2,5m com esquadria de alumínio (produto 1) vendido, a empresa
lucra $3.000,000, enquanto o lucro de venda de cada lote de janela adornada com esquadria de madeira
1,2m x 1,8m (produto 2) equivale a $5.000,00. Logo, o lucro total é igual a 3000X1 + 5000X2, de modo que
a função objetivo para o problema é
Max Z = 3X1 + 5X2
No caso do problema da Glass Co., foi considerada ilimitada a demanda por seus produtos e a oferta
de matéria-prima, de modo que não entram como restrições no modelo matemático. Porém, há restrições
relacionadas ao tempo de produção disponível por semana em cada fábrica. Logo, temos as seguintes
restrições:
X1 ≤ 4
2X2 ≤ 12 à X2 ≤6
3X1 + 2X2 ≤ 18
Há ainda a restrição de não negatividade das variáveis de decisão, uma vez que não se pode produzir
um número negativo de portas ou janelas. Assim, a restrição 4 é dada por: X1, X2≥0. Portanto, o modelo
para o problema é:
Max Z = 3X1 + 5X2
s.a
X1 ≤ 4
2X2 ≤ 12
3X1 + 2X2 ≤ 18
X1, X2 ≥ 0
Implantação do problema Glass Co. no Solver
Antes de analisar a sensibilidade do problema pelo Solver, é preciso implementar seu modelo
matemático no Excel. Para isso, veremos a implantação de um modelo no software Excel. A implantaçãodo
modelo matemático para o problema da Glass Co. servirá para encontrar a sua solução, com vistas à
posterior análise do Relatório de Sensibilidade, fornecido pelo Solver do Excel.
O passo inicial para a solução do problema é a organização dos dados, como veremos a seguir:
Métodos Quantitativos
Marcio Quirino - 50
Começamos representando as variáveis de decisão(X1 e X2) na planilha, bem como seus coeficientes
na função objetivo. Em amarelo estão destacadas as células variáveis/ajustáveis, reservadas na planilha
para representar as variáveis de decisão do modelo.
Em seguida, é preciso criar uma fórmula que represente a função objetivo, usando a função
“SOMARPRODUTO” do Excel para os coeficientes da função objetivo e as células destinadas a receber o
valor das variáveis de decisão. Com isso, a célula destacada em amarelo para a função objetivo recebeu a
fórmula 3*X1+5*X2.
O passo seguinte se dá com a inserção das duas restrições para o problema da Glass Co.
Métodos Quantitativos
Marcio Quirino - 51
• Observe a função SOMARPRODUTO entre os vetores que indicam os coeficientes das restrições
e as células destinadas para receber o valor das variáveis de decisão, além da inserção das constantes b
de cada restrição (lado direito da restrição).
Após a inserção da restrição 3 (3X1 + 2X2 ≤ 18) está finalizada a implementação do modelo do
problema de programação linear da Glass Co. no Excel.
Terminamos a implementação do modelo. Agora, vamos resolvê-lo.
Para tanto, é necessário indicar para o Solver o que cada célula da planilha representa:
• A função objetivo
• As variáveis de decisão
• As restrições
Então, define-se a célula de destino (aquela que representa a função objetivo na caixa de diálogo
Parâmetros do Solver). Observe que a célula E11 contém a fórmula que representa a função objetivo para
o problema, como havia sido preparado. Neste momento, instrui-se também o Solver para tentar maximizar
seu valor, especificando o botão Max.
Definindo a função objetivo na célula de destino. Captura de tela do Excel.
Métodos Quantitativos
Marcio Quirino - 52
Em seguida, é preciso indicar as células que representam as variáveis de decisão no modelo.
Observe que as células C10 e D10 na planilha representam as variáveis de decisão para o modelo. O Solver
determinará os valores ótimos para essas células.
Definindo as variáveis de decisão. Captura de tela do Excel.
É o momento, então, de definir as células de restrição na planilha e as restrições que se aplicam a
essas células. As células de restrição são aquelas em que foram implementadas as fórmulas para cada
restrição. Para definir as células de restrição, clique no botão Adicionar na janela Parâmetros do Solver e,
em seguida, preencha a caixa de diálogo Incluir Restrições, apresentada na figura a seguir. Observe que
as células E15, E16 e E17 representam as células de restrição cujos valores devem ser menores ou iguais
aos indicados nas células G15, G16 e G17, respectivamente.
Especificando as células de restrição. Captura de tela do Excel.
Métodos Quantitativos
Marcio Quirino - 53
Ainda é necessário especificar que as variáveis de decisão devem ser iguais ou maiores do que zero.
Para isso, basta clicar em Tornar Variáveis Irrestritas Não Negativas na caixa de diálogo Parâmetros do
Solver, conforme indicado na figura a seguir. Por fim, para encontrar a solução ótima para o problema, basta
clicar no botão Resolver, também indicado na figura a seguir.
Condições de não negatividade. Captura de tela do Excel.
A próxima figura apresenta a tela de saída do Excel com a solução ótima para o problema da Glass
Co., sendo X1 igual a dois, X2 igual a três e o valor ótimo de z igual a 36.
Solução ótima para o problema da Glass Co. Captura de tela do Excel.
Após resolver o modelo de programação linear, o Solver exibe a caixa de diálogo Resultados do
Solver, por meio da qual é possível solicitar três tipos de Relatório, a saber:
• Relatório de Resposta
• Relatório de Sensibilidade
• Relatório de Limites
A caixa de resultados do Solver está ilustrada a seguir.
Métodos Quantitativos
Marcio Quirino - 54
O Relatório de Resposta traz a solução do problema. Esse relatório é praticamente autoexplicativo.
Observa-se na tabela Célula do Objetivo, na coluna Valor Final, a solução ótima para o problema. Na
tabela Células Variáveis, na coluna Valor Final, estão os valores que as variáveis X1 e X2 recebem na
solução ótima do problema. A tabela final do relatório traz as informações sobre as restrições. A coluna Valor
da Célula indica os valores finais assumidos por cada restrição com os valores ótimos das variáveis de
decisão. Por sua vez, a coluna Margem de Atraso indica a diferença entre o valor do lado direito de cada
restrição (o valor b) e os valores finais assumidos por cada restrição com os valores ótimos das variáveis de
decisão. Assim sendo, por meio da figura a seguir, pode-se observar que se essa solução for implementada,
todo o tempo de produção disponível nas fábricas 2 e 3 estão sendo utilizados, havendo uma “sobra” de
capacidade de duas horas na fábrica 1.
Relatório de Resposta para o problema da Glass Co. Captura de tela do Excel.
Métodos Quantitativos
Marcio Quirino - 55
Análise de sensibilidade do problema da Glass Co. no Solver
O Relatório de Sensibilidade, apresentado a seguir, permite analisar o impacto das alterações nos
coeficientes, na solução ótima para o problema da Glass Co.
Relatório de Resposta para o problema da Glass Co. Captura de tela do Excel.
Mudança no coeficiente da função objetivo de uma variável básica
Essa análise serve para você compreender o quanto os coeficientes da função objetivo das variáveis
básicas podem variar, de forma que a base permaneça sendo a ótima.
No problema da Glass Co., os coeficientes da função objetivo representam o lucro da empresa com
a venda de cada tipo de produto. Não é difícil imaginar situações reais que levassem a alterações na matriz
de custos da empresa e que, consequentemente, impactassem o lucro com a venda de seus diferentes
produtos.
Exemplo
O componente de um produto pode ser importado, de modo que variações cambiais levariam a alterações no
seu custo e no lucro obtido com a sua venda.
Na coluna Objetivo Coeficiente da tabela Células Variáveis do Relatório de Sensibilidade,
observam-se os valores originais atribuídos aos coeficientes de cada variável de decisão na função objetivo.
As duas colunas seguintes, Permitido Aumentar e Permitido Reduzir, indicam os aumentos e as reduções
permitidos nos valores dos coeficientes de cada variável de decisão na função objetivo sem que haja
alterações na base da solução ótima do problema. Dessa forma:
A. X1
✓ O coeficiente de X1 pode reduzir em 3 unidades ou aumentar em 4,5 unidades sem alterar a
solução ótima, assumindo que todos os demais coeficientes se mantenham constantes).
B. X2
✓ O coeficiente de X2, ou seja, o lucro da venda do produto 2, pode reduzir em 2 unidades, sem
que a solução ótima seja alterada. Porém, perceba que, mesmo que esse coeficiente aumente
indefinidamente, não teremos alterações na solução ótima para o problema da Glass Co.
Métodos Quantitativos
Marcio Quirino - 56
Mudanças simultâneas nos coeficientes da função objetivo
Você acabou de ver que as colunas Permitido Aumentar e Permitido Reduzir indicam os aumentos e
as reduções permitidos nos valores dos coeficientes de cada variável de decisão na função objetivo, sem
que haja alterações na base da solução ótima do problema, assumindo que todos os demais coeficientes
do modelo permaneçam constantes.
Mas e se ocorressem alterações simultâneas em mais de um coeficiente da função objetivo?
Será que a solução atual permaneceria ótima?
Para esta análise, utiliza-se a técnica conhecida como “Regra dos 100%”. Aoaplicar essa regra,
duas situações diferentes podem ocorrer (RAGSDALE, 2009):
A. Situação 1
✓ Todas as variáveis, cujos coeficientes da função objetivo se alteram, têm custos reduzidos
diferentes de zero.
✓ Nesse caso, não há alteração na solução ótima atual desde que o coeficiente de cada variável
modificada permaneça dentro dos limites estabelecidos nas colunas “Permitido Aumentar” e
“Permitido Reduzir” do Relatório de Sensibilidade.
B. Situação 2
✓ Pelo menos uma variável, cujo coeficiente da função objetivo se altere, tem um custo reduzido
igual a zero.
✓ Nesse caso, é preciso analisar a proporção de alteração planejada em cj para a máxima
alteração permissível para a qual a solução atual permanece ótima (rj):
✓ Sendo:
• Cj = coeficiente da função objetivo para a variável xj
• Ij = o aumento permissível em cj dado pelo Relatório de Sensibilidade (coluna “Permitido
Aumentar”)
• Dj = a redução permissível em cj dada pelo Relatório de Sensibilidade (coluna “Permitido
Reduzir”)
✓ Se apenas um coeficiente da função objetivo se alterar, a solução atual permanece ótima
desde que rj ≤ 1 (caso rj seja expresso como porcentagem, deve ser menor ou igual a 100%).
De forma semelhante, se mais de um coeficiente da função objetivo se alterar, a solução atual
permanecerá ótima desde que. É importante ressaltar que, se, a solução atual pode
permanecer ótima, mas não há garantias.
Mudança no coeficiente da função objetivo de uma variável não
básica
No problema da Glass Co., as duas variáveis de decisão, cujos coeficientes na função objetivo são
diferentes de zero, são variáveis básicas. Na tabela “Células Variáveis” do Relatório de Sensibilidade,
observa-se que os valores da coluna “Reduzido Custo” são nulos, tanto para X1 quanto para X2.
Métodos Quantitativos
Marcio Quirino - 57
Os valores “Reduzido Custo” indicam o quanto o coeficiente da função objetivo de uma variável não
básica pode variar sem que a solução ótima para o problema se altere.
Exemplo
Caso houvesse um produto 3, cuja quantidade de itens vendidos fosse representada pela variável x3, e este
tivesse o valor de 10 unidades na coluna “Reduzido Custo”, tal fato implicaria um aumento permissível de 10 unidades
no coeficiente da função objetivo para o produto 3.
Isso significa que a solução atual permaneceria como ótima desde que alterações no lucro marginal do produto
3 resultassem em um número menor ou igual a 10.
Conforme reforçado por Ragsdale (2009), o aumento no valor da função objetivo será identificado de
maneiras distintas de acordo com o tipo de problema:
A. Problema de maximização
✓ O custo reduzido de uma variável deve ser não negativo para indicar que um aumento no
valor da variável implica um aumento no valor da função objetivo.
B. Problema de minimização
✓ O custo reduzido deve ser não positivo para indicar melhorias na função objetivo.
Mudança no vetor de demandas ou termo independente
Nessa análise, o que se deseja é compreender como mudanças nos termos independentes das
restrições (vetor de demandas) afetam a solução ótima para o problema de programação linear em análise.
Em outras palavras, por meio dessa análise, é possível determinar o quão melhor (ou pior) a solução seria
se houvesse mais ou menos de determinado recurso. Entretanto, essa análise é distinta para restrições
agrupadas e restrições não agrupadas.
As restrições que tenham folga igual a zero na solução ótima para um problema de programação
linear são chamadas de restrições agrupadas. Esse tipo de restrição impede que aperfeiçoemos mais a
função objetivo. Por exemplo, como observado no Relatório de Resposta para o problema da Glass Co., as
restrições relativas à capacidade das fábricas 2 e 3 limitam a maximização do lucro da empresa, sendo,
assim, restrições agrupadas, enquanto a restrição quanto à capacidade da fábrica 1 é não agrupada.
Atenção
Apesar de os preços-sombra indicarem que o valor da função objetivo se modifica caso o valor do termo
independente da restrição seja alterado, eles não indicam os valores que as variáveis de decisão vão assumir. A
determinação dos novos valores ótimos para as variáveis de decisão exige a realização das devidas alterações no
modelo implementado no Excel e que este seja resolvido outra vez.
Mudança no vetor de demandas ou termo independente em restrições agrupadas
A análise de sensibilidade em relação a mudanças no vetor de demandas em restrições agrupadas
é fornecida na coluna Sombra Preço da tabela Restrições do Relatório de Sensibilidade.
O preço-sombra de uma restrição indica o impacto que o aumento de uma unidade no valor do RHS
(b) da restrição tem sobre o valor da função objetivo, dado que todos os demais coeficientes permaneçam
constantes. Assim:
A. Preço-sombra positivo
✓ Indica o aumento do valor de z obtido para a solução ótima.
B. Preço-sombra negativo
✓ Implica uma redução no valor de z obtido para a solução ótima.
No entanto, os valores do preço-sombra se aplicam somente se o aumento ou redução no valor do
termo independente da restrição se mantém dentro dos limites permitidos de aumento e redução de cada
restrição, indicados no Relatório de Sensibilidade.
Métodos Quantitativos
Marcio Quirino - 58
Exemplo
O Relatório de Sensibilidade do problema da Glass Co. indica que o preço-sombra para a restrição associada
à disponibilidade de horas na fábrica 2 é igual 3. Dessa forma, se o número de horas disponíveis na fábrica 2 aumentar
na faixa de 0 a 3, o valor ótimo da função objetivo muda (aumenta) em 3 unidades para cada hora adicional. Se o
número de horas disponíveis se reduzir para uma quantia na faixa de 0 a 3, o valor ótimo da função objetivo muda
(reduz) em -3 unidades.
Mudança no vetor de demandas ou termo independente em restrições não agrupadas
A restrição para a fábrica 1 tem preço-sombra igual a zero com um aumento permissível igual a
infinito e uma redução permissível igual a 2. Desse modo, a disponibilidade de horas para a fábrica 1 pode
aumentar para qualquer valor, que a função objetivo não se altera. Esse resultado já era esperado, uma vez
que, atualmente, a capacidade da fábrica 1 já está sendo subutilizada, ou seja, há disponibilidade de horas
na fábrica 1 (horas não utilizadas). Além disso, o valor do termo independente dessa restrição pode se
reduzir em até duas horas, sem afetar a solução ótima.
Mudança no coeficiente de restrição de uma variável básica
Neste tópico, você verá como alterações em coeficientes de restrição afetam a solução ótima em um
problema de programação linear. Por exemplo, caso houvesse uma alteração na produtividade da fábrica 3,
sendo agora necessárias oito horas para se produzir um lote do produto 1, ainda seria lucrativo para a Glass
Co. continuar a produzir lotes desses produtos?
No exemplo, a quantidade de lotes de produtos 1 fabricados (variável X1) é uma variável básica.
Logo, mudanças em um coeficiente de suas restrições implicariam alterações em B e em quase toda a
Tabela Simplex, conforme pode ser verificado na figura a seguir.
Tabela Simplex.
Assim, a solução ótima permaneceria a mesma apenas se as duas situações a seguir ocorressem:
A. O lado direito da Tabela Simplex ótima (o vetor B-1.b) permanecesse positivo.
B. Todos os valores zj-cj fossem maiores que zero.
Dica
Mudanças no coeficiente de restrição de uma variável básica implicam tantas alterações na Tabela Simplex
final que se torna mais fácil resolver novamente o problema.
Relatório de Limites
A próxima figura apresenta o Relatório de Limites para o problema da Glass Co.
Métodos Quantitativos
Marcio Quirino - 59
Relatório de Limites para o problema da Glass Co. Captura de tela do Excel
O Relatório de Limites apresenta o valor ótimo para cada célula variável, além de indicar quais
valores a célula de destino assume se cada célula variável for ajustada para seu limitesuperior ou inferior.
A coluna “Inferior Limite” apresenta o menor valor que cada variável pode assumir, enquanto os valores de
todas as outras células variáveis permanecerem constantes e todas as restrições forem satisfeitas. Por sua
vez, a coluna “Superior Limite” apresenta o maior valor que cada variável pode assumir, enquanto os valores
de todas as outras células variáveis permanecerem constantes e todas as restrições forem satisfeitas.
Para você reforçar o aprendizado dos conceitos apresentados referentes à análise de sensibilidade
e, consequentemente, para facilitar a sua compreensão, veja a seguir um exemplo de aplicação para a
análise de sensibilidade em problemas de programação linear.
Exemplo de aplicação para análise de sensibilidade
Uma confeitaria produz três tipos de doces, compostos por açúcar e chocolate. A empresa tem
disponibilidade de 50kg de açúcar e 100kg de chocolate por semana e deseja maximizar seu lucro semanal.
A tabela a seguir apresenta as restrições de composição e lucro por produto da confeitaria.
Doce Açúcar Chocolate Lucro
1 1 2 3
2 1 3 7
3 1 1 5
Tabela: Restrições de composição e lucro por produto.
Questões:
1. Ache a solução ótima para o problema.
2. Para quais valores de lucro do doce 1 a base atual permanece ótima? Se o lucro do doce 1
fosse $7,00, a solução ótima sofreria alterações?
3. Para quais valores de lucro do doce 2 a base atual permanece ótima? Se o lucro do doce 2
fosse $13,00, haveria uma nova solução ótima?
4. Para quais valores de açúcar disponível a base permaneceria a mesma?
5. Se 60kg de açúcar estivessem disponíveis, qual seria o lucro da empresa?
Primeiramente, encontraremos a solução ótima para o problema.
Métodos Quantitativos
Marcio Quirino - 60
Para atender à questão 1, o primeiro passo é construir o modelo matemático do problema. Para isso,
adotamos as seguintes variáveis de decisão:
A. X1
✓ Quantidade de lotes do doce 1 produzida por semana.
B. X2
✓ Quantidade de lotes do doce 2 produzida por semana.
C. X3
✓ Quantidade de lotes do doce 3 produzida por semana.
A confeitaria tem como objetivo maximizar seu lucro semanal, sendo: $3,00 o lucro unitário obtido
pela venda de um lote do doce 1; $7,00 o lucro unitário obtido pela venda de um lote do doce 2; e $5,00 o
lucro unitário obtido pela venda de um lote do doce 3. Logo, a função objetivo desse problema é:
Max Z =X1 + 7X2 + 5X3
A produção de um lote do doce 1 requer 1kg de açúcar e 2kg de chocolate. Um lote do doce 2
demanda 1kg de açúcar e 3kg de chocolate, enquanto a produção de um lote do doce 3 requer 1kg de
açúcar e 1kg de chocolate. Como a confeitaria tem disponibilidade de 50kg de açúcar e 100kg de chocolate
por semana, são as seguintes as restrições que limitam a função objetivo do problema, além da condição
de não negatividade das variáveis de decisão (X1, X2, X3 ≥ 0):
A. Disponibilidade de açúcar
X1 + X2 + X3 ≤ 50 →
B. Disponibilidade de chocolate
2X1 + 3X2 + X3 ≤ 100
Dessa forma, o modelo matemático para esse problema de programação linear é:
Max Z = 3X1 + 7X2 + 5X3
s.a.:
X1 + X2 + X3 ≤ 50
2X1 + 3X2 + X3 ≤ 100
X1, X2, X3 ≥ 0
Em seguida, implementa-se o modelo no Solver do Excel, de modo a encontrar a solução ótima. A
figura a seguir apresenta a tela do Excel com a implantação do modelo no Solver após a sua solução.
Métodos Quantitativos
Marcio Quirino - 61
Implantação do modelo no Solver e sua solução. Captura de tela do Excel.
A próxima figura apresenta o Relatório de Resposta desse problema.
Relatório de Resposta. Captura de tela do Excel.
Nessas figuras é possível observar que a solução ótima para o problema é produzir 25 lotes do doce
2 e 25 lotes do doce 3, de modo a obter um lucro semanal de $300,00 com a venda dos três tipos de produto.
Para atender às demais solicitações do problema, torna-se necessário obter o Relatório de
Sensibilidade por meio do Solver. Esse relatório é apresentado na figura a seguir.
Métodos Quantitativos
Marcio Quirino - 62
Relatório de Sensibilidade. Captura de tela do Excel.
Agora, podemos resolver as outras questões:
Resolução da questão 2
É possível responder à questão 2 do problema por meio da análise das colunas Permitido Aumentar e Permitido
Reduzir da tabela Células Variáveis do Relatório de Sensibilidade. O valor de “Permitido aumentar” mostra que o
coeficiente da função objetivo pode aumentar em até 3 unidades, sendo que a solução ótima permaneceria a mesma.
Aumentos superiores a 3 unidades implicam alterações na solução ótima. Assim, pode-se afirmar que a base
permanece a mesma para valores de c1 ≤ 6. Portanto, se o lucro do doce 1 for de $7,00, haverá uma nova solução
ótima.
Resolução da questão 3
A questão 3 trata do intervalo de valores de c2 para os quais a base atual permanece ótima. Para respondê-la,
é necessário verificar as colunas Permitido Aumentar e Permitido Reduzir para a variável X2, na tabela Células
Variáveis. Desse modo, pode-se concluir que, para 5 ≤ c2 ≤ 15, a solução ótima se mantém. Logo, se o lucro do doce
2 fosse $13,00, a solução ótima seria a mesma.
Resolução da questão 4
A questão 4 é sobre os valores de disponibilidade de açúcar para os quais a base permaneceria a mesma. A
resposta pode ser obtida por meio da análise das colunas Permitido Aumentar e Permitido Reduzir da tabela Restrições,
do Relatório de Sensibilidade. A conclusão é que a base permanece a mesma para o intervalo 33,33 ≤ b2 ≤100.
Resolução da questão 5
Com a resolução da questão 4 também é possível responder à questão 5, pois, se a disponibilidade de açúcar
for igual a 60kg, o valor ainda estará dentro do intervalo para b2, de modo que não haverá alteração nas variáveis base.
Porém, a solução ótima se altera para 340 (300+4*10).
Considerações Finais
A aprendizagem de técnicas de pesquisa operacional nos habilita a representar situações complexas
por meio de modelos matemáticos, permitindo a análise de diferentes cenários, de forma mais rápida e
barata. Aplicar tais técnicas no processo de tomada de decisão para a solução desses problemas é de
grande auxílio.
Entretanto, encontrar a solução ótima nem sempre é simples, exigindo grande número de cálculos.
Visando a facilitar o trabalho, foram desenvolvidos diferentes softwares computacionais que permitem a
Métodos Quantitativos
Marcio Quirino - 63
solução de problemas de programação matemática, desde o Solver de pacotes de planilhas eletrônicas,
como o Excel, até programas mais robustos dedicados exclusivamente à otimização, como o CPLEX.
Além disso, encontrar a solução ótima para um problema nem sempre significa que ele esteja
resolvido! É importante conhecer o grau de liberdade na tomada de decisão, ou seja, saber quais as margens
de manobra necessárias para alterar determinados aspectos na construção do modelo sem que a solução
ótima seja modificada (RODRIGUES et al., 2014). A análise pós-otimalidade, conhecida como análise de
sensibilidade, permite esse tipo de avaliação.
No desenvolvimento do modelo, premissas são assumidas e estimativas são feitas em relação a
parâmetros e coeficientes, que, na realidade, podem sofrer alterações ao longo do tempo. Por exemplo, o
custo de um produto pode aumentar, alterando então sua margem de lucro. Um fornecedor pode enfrentar
problemas na produção de um componente, o que influenciará a disponibilidade desse produto. A análise
pós-otimalidade permite avaliar a sensibilidade da solução em relação à incerteza ou a erros de estimativa
quanto aos coeficientes do modelo, ou quanto a mudanças que possam ocorrer.
A análise de sensibilidade está relacionada ao problema dual associado ao primal. A teoria da
dualidade pode ser aplicada em análises econômicas, como variações marginais. Em algumas situações,
dependendo do número de restrições e de27
Problema do planejamento de produção dinâmico .............................................................................. 27
Problema fazer x comprar ........................................................................................................................ 29
Teoria na prática ...................................................................................................................................... 29
Problema fazer x comprar .................................................................................................................... 29
2. Técnica de modelagem nos problemas de transporte e transbordo .................................... 31
Problemas de transporte .......................................................................................................................... 31
Teoria na prática ...................................................................................................................................... 33
Problema de transporte ........................................................................................................................ 33
Problema de transbordo ........................................................................................................................... 34
Teoria na prática ...................................................................................................................................... 35
Problema de transbordo ....................................................................................................................... 35
3. Técnica de modelagem em problemas de alocação ............................................................. 37
Teoria na prática ...................................................................................................................................... 38
Considerações Finais ............................................................................................................................... 39
Referências .............................................................................................................................................. 40
Explore+ ................................................................................................................................................... 40
Dualidade e Análise de Sensibilidade ................................................................................................. 41
Descrição ................................................................................................................................................. 41
Propósito .................................................................................................................................................. 41
Preparação ............................................................................................................................................... 41
Introdução ................................................................................................................................................ 41
1. Dualidade para solução de problemas de programação linear ............................................ 41
O problema dual e o método dual-simplex ............................................................................................... 41
Interpretação econômica do problema dual ............................................................................................. 44
Métodos Quantitativos
Marcio Quirino - 3
Teoria na prática ...................................................................................................................................... 45
Dualidade na eficiência computacional para a solução de problemas de programação linear ................ 46
Regras para identificação da solução ótima na Tabela Simplex ótima do primal ..................................... 46
2. Sensibilidade da solução obtida para problemas de programação linear em relação à
incerteza ou erros de estimativa quanto aos coeficientes do modelo ........................................................ 47
O que é a análise de sensibilidade ........................................................................................................... 47
Problema Glass Co. ................................................................................................................................. 48
Implantação do problema Glass Co. no Solver ........................................................................................ 49
Análise de sensibilidade do problema da Glass Co. no Solver ................................................................ 55
Mudança no coeficiente da função objetivo de uma variável básica .................................................... 55
Mudanças simultâneas nos coeficientes da função objetivo ................................................................ 56
Mudança no coeficiente da função objetivo de uma variável não básica ................................................. 56
Mudança no vetor de demandas ou termo independente .................................................................... 57
Mudança no vetor de demandas ou termo independente em restrições agrupadas ............................ 57
Mudança no vetor de demandas ou termo independente em restrições não agrupadas ..................... 58
Mudança no coeficiente de restrição de uma variável básica .............................................................. 58
Relatório de Limites .................................................................................................................................. 58
Exemplo de aplicação para análise de sensibilidade ............................................................................... 59
Considerações Finais ............................................................................................................................... 62
Referências .............................................................................................................................................. 63
Explore+ ................................................................................................................................................... 63
Método Simplex ................................................................................................................................... 64
Descrição ................................................................................................................................................. 64
Propósito .................................................................................................................................................. 64
Preparação ............................................................................................................................................... 64
Introdução ................................................................................................................................................ 64
1. Método simplex para a solução de problemas de programação linear ................................ 64
O método simplex para a solução de modelos de programação linear .................................................... 64
O que é um simplex? ............................................................................................................................... 65
Método gráfico.......................................................................................................................................... 65
Método simplex ........................................................................................................................................ 66
Fase 2: {início da iteração simplex} ...................................................................................................... 68
Método simplex em sua forma tabularvariáveis, a dualidade também pode ser aplicada para que o
problema seja resolvido de modo mais eficiente, computacionalmente.
Referências
ARENALES, M. et al. Pesquisa operacional. Rio de Janeiro: Elsevier, 2007.
FOGLIATO, F. Pesquisa operacional. Porto Alegre: Deprot/ UFRGS, 2006.
HILLIER, F. S.; LIEBERMAN, G. J. Introdução à pesquisa operacional. Brasil: McGraw Hill, 2013.
LACHTERMACHER, G. Pesquisa operacional na tomada de decisões. Rio de Janeiro: Campus,
2009.
RAGSDALE, C. T. Modelagem e análise de decisão. São Paulo: Cengage Learning, 2009.
RODRIGUES, L. H. et al. Pesquisa operacional – programação linear passo a passo: do
entendimento do problema à interpretação da solução. São Leopoldo: Unisinos, 2014.
Explore+
Sobre os conceitos de análise de sensibilidade e dualidade, leia:
Operations Research: Applications and Algorithms (2004), de Winston, W. L. e Goldberg, J. B.,
capítulos 5 e 6;
Pesquisa operacional na tomada de decisões (2009), de Lachtermacher, G., capítulo 5;
Pesquisa operacional (2007), de Arenales, M. et al., seção 2.10 do capítulo 2.
Sobre a utilização do Solver, leia o capítulo 4 de Modelagem e análise de decisão (2009), de
Ragsdale C. T.
Métodos Quantitativos
Marcio Quirino - 64
Método Simplex
Descrição
O método simplex para a solução de modelos de programação linear e a utilização do solver na
solução de problemas de programação linear.
Propósito
Dominar a solução de problemas de programação linear, seja por meio do método simplex, ou pela
utilização de softwares, permitirá que você aplique a técnica de modelagem no processo de decisão de
problemas complexos de diversas origens, em especial em sua atuação profissional.
Preparação
Para o conteúdo deste tema, são necessários uma calculadora e um software editor de planilhas
eletrônicas com o add-in do solver habilitado.
Introdução
A modelagem matemática nos permite representar, de forma simplificada, um problema complexo
por meio de linguagem matemática. Com isso, conseguimos analisar diferentes cenários de forma mais
rápida e barata do que se a situação fosse avaliada na realidade, auxiliando-nos, assim, no processo de
tomada de decisão.
No contexto da programação linear, que se aplica, por exemplo, no planejamento de redes logísticas,
há métodos, como o método gráfico, que se restringem à solução de problemas com apenas duas ou no
máximo três variáveis de decisão. Como solucionar, então, problemas mais complexos, com maior número
de variáveis de decisão? Este é o assunto a ser tratado neste tema. A seguir, abordaremos o método simplex
para a solução de problemas de programação linear e aprenderemos a utilizar o solver do Excel para a
solução desse tipo de problema!
1. Método simplex para a solução de problemas de
programação linear
O método simplex para a solução de modelos de programação
linear
Podemos resolver, de forma simples, problemas de programação linear com duas variáveis de
decisão por meio do método gráfico. Entretanto, são poucos os problemas de programação linear no mundo
real que envolvem apenas duas variáveis de decisão, de modo que a aplicação do método gráfico é bastante
limitada.
Então, como fazemos para solucionar problemas mais complexos, com um maior número de
variáveis de decisão?
Existe uma série de técnicas matemáticas para resolver problemas de programação linear com
qualquer número de variáveis sem a necessidade de visualizar em gráficos as regiões viáveis. Dentre tais
técnicas, destaca-se o algoritmo simplex, que foi o primeiro método desenvolvido para resolver problemas
de programação linear.
O algoritmo simplex foi desenvolvido por George B. Dantzig, em 1947, enquanto trabalhava como
consultor em matemática para o controle da Força Aérea norte-americana. O método simplex é específico
para a solução de problemas de otimização linear (equações ou inequações lineares). Trata-se de um
Métodos Quantitativos
Marcio Quirino - 65
algoritmo eficiente que se baseia na solução sucessiva de sistemas de equações indeterminados, em que
sistemas adjacentes são avaliados de forma iterativa, sendo, assim, adaptável ao cálculo computacional.
Na época, os computadores estavam começando a surgir, e a resolução desse tipo de problema se tornava
importante na prática!
O simplex é considerado uma das grandes contribuições à programação matemática.
Antes de estudarmos o algoritmo simplex, é importante entendermos o conceito do simplex e
recordarmos alguns pontos sobre a solução de problemas de programação linear com duas variáveis de
decisão por meio do método gráfico.
O que é um simplex?
Um simplex é um polígono convexo, ou seja, com propriedade especial: uma reta que passe por
quaisquer dois pontos pertencentes a um simplex deve estar contida inteiramente dentro do simplex. Logo,
na figura a seguir, observa-se que o polígono representado em (a) não é convexo, enquanto o ilustrado em
(b) é um simplex.
Polígono não convexo e polígono simplex.
As restrições de um problema de programação linear sempre definem hiperespaços convexos. Esta
é a premissa do algoritmo simplex e de boa parte da teoria de otimização convexa. Assim, o espaço de
soluções de um problema de programação linear, ou seja, a área formada pela intersecção das restrições
do problema, é uma forma geométrica simplex.
Método gráfico
Para encontrar a solução ótima pelo método gráfico, precisamos seguir os seguintes passos:
1. Desenhe as retas correspondentes às restrições do problema e encontre o espaço de soluções.
2. Desenhe o vetor z (função objetivo).
3. Desenhe linhas ortogonais ao vetor z. Essas são as linhas de isocusto, isto é, são as retas que
têm o mesmo valor de z.
4. Calcule o valor de z no ponto ótimo, ou seja, a linha de isocusto com maior z que ainda pertence
ao espaço de soluções.
Na verdade, esta foi a grande ideia de Dantzig para o desenvolvimento do algoritmo simplex: dado
que a solução ótima está em um vértice do espaço de soluções viáveis, por que não percorrê-los em busca
da melhor solução possível?
Métodos Quantitativos
Marcio Quirino - 66
Método simplex
Conforme verificamos, a chave do algoritmo simplex está no formato da região limitada pelas
restrições. Portanto, apesar de ser um procedimento algébrico, os conceitos subjacentes ao método simplex
são geométricos.
O simplex é um algoritmo iterativo, que se utiliza de um ferramental baseado em álgebra linear para
a resolução sucessiva de sistemas de equações, embora as restrições de problemas de programação
matemática sejam tipicamente inequações. Desse modo, a primeira etapa do método simplex consiste em
converter as restrições de desigualdade em restrições de igualdade equivalente. O algoritmo simplex só
pode ser rodado se o problema estiver escrito na forma canônica, que é a forma de se representar programas
matemáticos por meio de equações. Para isso, precisamos criar as chamadas variáveis de folga ou de
excesso.
A. Variáveis de folga (f)
✓ Exemplo (forma canônica):
B. Variáveis de excesso (e)
✓ Veja o caso do problema da Fitwear, apresentado a seguir. Será que conseguimos escrevê-
lo em sua forma canônica?
Caso Fitwear S/A
A Fitwear S/A é uma confecção de roupas esportivas, tendo uma linha fitness feminina, na qual
produz roupas de ginástica exclusivas para mulheres, como tops e calças de lycra.
Cada top de ginástica é vendido por R$80,00 e utiliza R$20,00 de matéria-prima, como tecido
e alinhamentos, e R$32,00 de mão de obra. Trinta minutos de corte e 15 minutos de costura
são demandados para a confecção de um top de ginástica.
Cada calça de ginástica é vendida por R$120,00 e utiliza R$35,00 de matéria-prima, como
tecido e alinhamentos, e R$40,00 de mão de obra. Quinze minutos de corte e 30 minutos de
costura são demandados para a confecção de uma calça de ginástica.
A Fitwear só pode contar com 100 horas de corte porsemana e 160 horas de costura. A
confecção não tem problemas no fornecimento de matérias-primas, de modo que seu
suprimento pode ser considerado ilimitado, bem como a demanda semanal de seus produtos.
A Fitwear deseja planejar sua produção semanal de modo a maximizar seus lucros.
Quando modelamos o problema, consideramos as seguintes variáveis de decisão:
A. x1
✓ Número de tops de ginástica confeccionados a cada semana.
B. x2
✓ Número de calças de ginástica confeccionadas a cada semana.
Assim, chegamos à seguinte formulação matemática em sua forma-padrão.
Métodos Quantitativos
Marcio Quirino - 67
Observe que tanto a restrição referente às horas de corte quanto a restrição referente às horas de
costura são do tipo ≤. Logo, precisaremos de duas variáveis de folga, f1e f2, para passar o problema para
sua forma canônica.
Sujeito à (forma canônica):
Uma vez adicionadas as variáveis de folga, o problema da Fitwear é dito no formato canônico e
pronto para ser resolvido pelo método simplex!
Para resolver o problema de programação linear, o algoritmo simplex se baseia na solução sucessiva
de sistemas de equações, utilizando-se do conceito de variáveis básicas e não básicas:
A. Variáveis básicas
✓ São aquelas para as quais o sistema de equações é resolvido.
B. Variáveis não básicas
✓ São aquelas que são zeradas para que o sistema de equações apresente uma solução, ou
seja, para que o número de equações seja igual ao número de variáveis, permitindo, assim,
a solução do sistema de equações.
No problema da Fitwear, por exemplo, temos quatro variáveis (x1, x2, f1 e f2) e apenas duas equações
(restrições). Entretanto, para que um sistema de equações lineares seja resolvido, é necessário que o
número de equações seja igual ao número de variáveis. De tal modo, para resolver o problema da Fitwear,
devemos considerar duas variáveis como nulas (não básicas) e resolver o problema para outras duas
(variáveis básicas), e assim fazemos por iterações sucessivas, até que encontremos o par de variáveis
básicas que nos dá a solução ótima.
Em linhas gerais, o algoritmo simplex parte de uma solução viável do sistema de equações que
constituem as restrições do problema de programação linear, solução essa normalmente extrema (vértice).
A partir dessa solução inicial, o algoritmo adota um critério de escolhas para encontrar novos e melhores
vértices da envoltória convexa do problema, e outro critério para determinar se o vértice escolhido (solução
básica) é ou não um vértice ótimo (GOLDBARG; LUNA, 2005). Assim, pelo método simplex, devemos:
1. Transformar o modelo em sua forma canônica, ou seja, transformar o sistema de inequações em
sistema de equações.
2. Determinar uma solução básica inicial, que será iterativamente melhorada.
3. Realizar o teste da otimalidade, ou seja, verificar se a iteração atual é ótima ou se outras variáveis
não base (ou seja, que estão zeradas) devem entrar na base, pois têm potencial para contribuir
para melhorar a solução.
Métodos Quantitativos
Marcio Quirino - 68
4. Realizar o teste da mínima razão, que determinará qual variável básica deve sair da base, ou
seja, verificará quais das variáveis devem passar a ser nulas para que a nova variável entre na
base.
5. Calcular a nova solução básica e voltar ao passo 3.
Arenales et al. (2007) descrevem o algoritmo simplex em duas fases. A fase 1 traz o procedimento
de como determinar uma solução inicial, enquanto o método simplex propriamente dito é apresentado na
fase 2.
A. Passo 1
B. Passo 2
Fase 2: {início da iteração simplex}
A. Passo 1: {cálculo da solução básica}
B. Passo 2: {cálculo dos custos relativos}
✓ {vetor multiplicador simplex}
✓ {custos relativos}
✓ {determinação da variável a entrar na base}
Métodos Quantitativos
Marcio Quirino - 69
C. Passo 3: {teste da otimalidade}
D. Passo 4: {cálculo da direção simplex}
E. Passo 5: {determinação do passo e variável a sair da base}
F. Passo 6: {atualização: nova variável básica, troque a L-ésima coluna de B pela K-ésima
coluna de N}
✓ Matriz básica nova:
✓ Matriz não básica nova:
✓ Iteração = iteração +1
✓ Retorne ao passo 1
{fim da iteração simplex}
Na forma de algoritmo, como apresentado por Arenales et al. (2007), o método simplex pode parecer
difícil, mas vamos entender o que Dantzig propôs por meio de um exemplo.
Caso da empresa Glass Co.
A empresa Glass Co., que possui três fábricas, produz janelas e portas de vidro. As esquadrias e ferragens em
aço são feitas na fábrica 1, as esquadrias de madeira são produzidas na fábrica 2 e a fábrica 3 produz o vidro e monta
os produtos.
A direção da empresa decidiu modernizar sua linha de produtos e propôs o lançamento de dois novos produtos:
• Produto 1: porta de vidro de 2,5m com esquadria de alumínio.
• Produto 2: janela adornada com esquadria de madeira 1,2m x 1,8m.
Métodos Quantitativos
Marcio Quirino - 70
O produto 1 requer capacidade produtiva das fábricas 1 e 3. O produto 2 precisa das fábricas 2 e 3. A divisão
de marketing concluiu que a empresa poderia vender tanto quanto fosse possível produzir desses produtos por essas
fábricas. Porém, ambos os produtos competem por capacidade produtiva da fábrica 3, não estando claro qual mix dos
dois seria mais lucrativo. Determine quais devem ser as taxas de produção para maximizar o lucro total, sujeitas às
restrições impostas pela capacidade produtiva:
Fábrica
Tempo de produção por lote (em horas)
Tempo de produção disponível por semana (horas) Produtos
1 2
1 1 0 4
2 0 2 12
3 3 2 18
Lucro por lote R$3.000,00 R$5.000,00
Produção empresa Glass Co. Extraída de Hillier e Lieberman, 2013, pág. 21
Inicialmente, devemos escrever o modelo matemático para o problema da Glass Co., seguindo os
passos do procedimento para construção do modelo de programação linear:
1. Identificação das variáveis de decisão
2. Identificação da função objetivo
3. Identificação do conjunto de restrições
A seguir, vamos seguir cada um dos passos indicados.
A. Identificação das variáveis de decisão
B. Identificação da função objetivo
C. Identificação do conjunto de restrições
✓ No caso do problema da Glass Co., foram consideradas ilimitadas a demanda por seus
produtos e a oferta de matéria-prima, de modo que não entram como restrições no modelo
matemático. Porém, há restrições relacionadas ao tempo de produção disponível por semana
em cada fábrica.
Métodos Quantitativos
Marcio Quirino - 71
Fábrica
Tempo de produção por lote (em horas)
Tempo de produção disponível por semana (horas) Produtos
1 2
1 1 0 4
2 0 2 12
3 3 2 18
Produção empresa Glass Co. Extraída de Hillier e Lieberman, 2013, pág. 21.
Enfim, temos o seguinte modelo matemático para o problema da Glass Co.:
Mas qual é o mix de produção que nos dá a solução ótima?
O primeiro passo do algoritmo simplex é transformar o modelo em seu formato canônico.
Passando para o formato canônico, temos:
Métodos Quantitativos
Marcio Quirino - 72
Como as taxas de crescimento são positivas (3 e 5) e este é um problema de maximização,
concluímos que a solução inicial (0,0,4,12,18) não é a solução ótima!
Verificamos, então, que x2 passa a receber o valor de 6, enquanto f2 se torna uma variável não base
e nula. Assim, deduzimos intuitivamente o teste da mínima razão.
O objetivo do teste da mínima razão é determinar qual variável básica cai a zero primeiro à
medida que a variável básica que entra é aumentada.
Métodos Quantitativos
Marcio Quirino - 73
Podemos descartar imediatamente a variável básica em qualquer equação cujo coeficiente da
variável básica que entra é zero ou negativo, já que uma variável básica não decresceria à medida que a
variável básica que entra aumentasse.
No caso do problema da GlassCo., ao aumentarmos o valor de x2 de 0 a 6, temos mudanças na
solução.
Logo, f3 sai da base para x1 entrar com o valor igual a 2. Porém, ao aumentarmos o valor de x1 de 0
a 2, temos mudanças na solução.
Métodos Quantitativos
Marcio Quirino - 74
Método simplex em sua forma tabular
Aprendemos até agora a forma algébrica do simplex, que é a melhor para aprender a lógica por trás
do algoritmo. Porém, não é a forma mais conveniente para realizar cálculos necessários. As operações
realizadas no método simplex podem ser organizadas em tabelas, chamadas tabelas simplex. Essa
organização é a mais indicada para quando estivermos resolvendo um problema de programação linear
manualmente.
Considere um problema de otimização linear:
Métodos Quantitativos
Marcio Quirino - 75
Na forma de algoritmo, como apresentado por Arenales et al. (2007), o método simplex tabular pode
parecer difícil, mas vamos entendê-lo resolvendo o exemplo da Glass Co., cujo modelo em formato canônico
é apresentado a seguir.
Métodos Quantitativos
Marcio Quirino - 76
Inicialmente, vamos definir o formato da tabela de maneira a facilitar sua compreensão. A tabela
simplex tem, do lado esquerdo, as variáveis básicas e, do lado direito, as constantes das equações. No meio
da tabela, ficam todos os coeficientes das restrições e da função objetivo. Por padronização, colocaremos
na primeira linha (zero) a equação que representa a função objetivo, conforme apresentado na figura a
seguir.
Tabela simplex.
Métodos Quantitativos
Marcio Quirino - 77
Em seguida, devem-se escrever as linhas que compõem as restrições da tabela simplex, conforme
indicado na figura a seguir.
Restrições da tabela simplex.
Métodos Quantitativos
Marcio Quirino - 78
Preenchendo a tabela simplex para o problema da Glass Co.
Observa-se, por meio da figura anterior, que os únicos elementos faltantes estão do lado direito da
tabela simplex e correspondem à fórmula:
Tabela simplex inicial para o problema da Glass Co.
Uma vez preenchida a tabela inicial, devemos identificar as variáveis candidatas a entrar na base na
primeira linha da tabela. Para isso, devemos analisar os valores dos coeficientes de cada variável
apresentados na segunda linha da tabela simplex, levando em consideração o tipo de problema
apresentado, maximização ou minimização:
Métodos Quantitativos
Marcio Quirino - 79
Teste da mínima razão para o problema da Glass Co.
Métodos Quantitativos
Marcio Quirino - 80
Operações com a linha pivot para o problema da Glass Co.
Dica
Para a linha (2), não é preciso realizar nenhuma operação, uma vez que os valores para as colunas x2 e x1 já
são coincidentes.
Renata Albergaria de Mello Bandeira
Métodos Quantitativos
Marcio Quirino - 81
Teste da mínima razão para o problema da Glass Co. — 2a iteração
Primeira operação elementar (linha (4)) para o problema da Glass Co. — 2a iteração.
Dica
Para a linha (3) não é preciso realizar nenhuma operação, uma vez que os valores para as colunas x1 e f3 já
são coincidentes nesta linha.
Métodos Quantitativos
Marcio Quirino - 82
Operações com a linha pivot para o problema da Glass Co. — 2a iteração.
Atenção
Verifique, na figura anterior, que não há mais valores negativos na segunda linha da tabela simplex (1), de
modo que não há mais variáveis para entrar na base. Logo, concluímos que a solução ótima para o problema da Glass
Co. é x1=2, x2=6 e z=36, tal como apresentado na seção método simplex, quando resolvemos este mesmo problema
por meio do método simplex em sua forma analítica.
2. Solução de problemas de programação linear
Utilização do solver para solução de problemas de programação
linear
No módulo 1, aprendemos a resolver problemas de programação linear por meio do método simplex,
tanto o analítico quanto o tabular. Aplicamos essas técnicas em alguns exemplos, de modo a entender a
lógica do algoritmo. Porém, pudemos verificar que são muitos os cálculos que precisam ser feitos para
resolvermos problemas de programação linear manualmente, e apenas um erro em uma conta nos levaria
a um resultado errado. Contudo, felizmente, existem diversos softwares de computador que podem ser
utilizados para nos auxiliar a encontrar a solução ótima para problemas de programação matemática, por
exemplo:
A. LINDO
B. CPLEx
C. Aimms
D. GAMS
E. MathPro
Usando o software de computador adequado, podemos resolver facilmente quaisquer problemas de
programação linear.
As técnicas para a solução de problemas de programação linear são, inclusive, desenvolvidas por
meio de pacotes de planilhas eletrônicas. Assim sendo, aprenderemos nesta seção a utilizar o solver do
pacote de planilhas eletrônicas Excel para solução de problemas de programação linear.
Dica
Os mesmos conceitos e técnicas que apresentaremos a seguir também podem ser aplicados em outros pacotes
de planilhas, dadas as necessidades de alterações em detalhes de implementação.
Passos para implementar um problema de programação linear em
planilha
Ragsdale (2009) apresenta cinco passos que devem ser feitos para implementar qualquer problema
de programação linear em uma planilha:
Métodos Quantitativos
Marcio Quirino - 83
1. Organize os dados para o modelo (os coeficientes das restrições, os coeficientes da função
objetivo etc.) na planilha.
2. Reserve as células separadas na planilha para representar cada variável de decisão do modelo
algébrico. Isso é útil na determinação de fórmulas para a função e restrições do objetivo.
3. Crie uma fórmula para cada célula da planilha que corresponda à função objetivo no modelo
algébrico.
4. Para cada restrição, crie uma fórmula em uma célula separada na planilha. Muitas das fórmulas
de restrição têm estrutura semelhante, de modo que, quando possível, crie fórmulas de restrição
que possam ser copiadas para implementar outras fórmulas de restrição.
5. Use sombras e cores de fundo e/ou bordas para identificar as células que representam as
variáveis de decisão, restrições e funções objetivos do modelo.
Instalando o solver
Demonstraremos, neste módulo, como usar o solver do Excel resolvendo o problema enfrentado pela
Fitwear. No entanto, antes de iniciarmos a resolução do problema, é preciso instalar o solver nos pacotes
de planilhas eletrônicas Excel. Para isso, siga o passo a passo:
Clique em arquivos > opções no Excel, conforme indicado na figura.
Instalando o solver — Passo 1. Captura do Excel.
O segundo passo é clicar em suplementos na tela que foi aberta.
Métodos Quantitativos
Marcio Quirino - 84
Instalando o solver — Passo 2. Captura do Excel.
Na tela seguinte, clique no botão ir, em gerenciar suplementos do Excel.
Instalando o solver — Passo 3. Captura do Excel.
Na próxima tela, clique na opção solver.
Métodos Quantitativos
Marcio Quirino - 85
Instalando o solver — Passo 4. Captura do Excel.
Para finalizar, basta clicar na aba dados para visualizar a opção solver.
Instalando o solver — Passo 5. Captura do Excel.
Utilizando o solver
Agora que já temos o solver instalado no nosso Excel, vamos iniciar a resolução do problema da
Fitwear visto no módulo 1.
Dica
Caso seja necessário, retorne ao módulo anterior e relembre como desenvolvemos o modelo matemático do
problema.
Observe a seguir o modelo matemático, considerando as variáveis de decisão:
Temos a formulação matemática em sua forma-padrão.
Métodos Quantitativos
Marcio Quirino - 86
Variáveis de decisão. Captura de tela do Excel.
O próximo passo é criar uma fórmula que represente a função objetivo de acordo com as variáveis
de decisão indicadas na figura. Para isso, devemos utilizar a função “somarproduto” do Excel, que faz o
produto escalar entre doisvetores.
Métodos Quantitativos
Marcio Quirino - 87
Função “somarproduto”. Captura de tela do Excel.
Função objetivo. Captura de tela do Excel.
De maneira análoga à que fizemos a representação da função objetivo, precisamos representar as
restrições. Para isso, também vamos utilizar a função “somarproduto” do Excel. Veja a seguir como
inserimos as duas restrições para o problema da Fitwear na planilha eletrônica.
A. Restrição de horas de corte
Restrição de horas de corte. Captura de tela do Excel.
Métodos Quantitativos
Marcio Quirino - 88
B. Restrição de horas de costura
Restrição de horas de costura. Captura de tela do Excel.
Finalmente, terminamos a implementação do modelo do problema de programação linear da Fitwear
no Excel. Entretanto, ainda precisamos resolvê-lo.
Para isso, é preciso indicar para o solver o que cada célula da planilha representa:
• A função objetivo
• As variáveis de decisão
• As restrições
Assim sendo, devemos definir a célula de destino, ou seja, aquela que representa a função objetivo
na caixa de diálogo parâmetros do solver, como indicado na próxima figura. Observe que a célula E9 contém
a fórmula que representa a função objetivo para o nosso problema, como havíamos preparado
anteriormente. Neste momento, devemos instruir também o solver para tentar maximizar seu valor,
especificando o botão max.
Métodos Quantitativos
Marcio Quirino - 89
Definindo a função objetivo na célula de destino. Captura de tela do Excel.
O próximo passo consiste em indicar as células que representam as variáveis de decisão no modelo.
Observe, na figura a seguir, que as células C8 e D8, em nossa planilha, representam as variáveis de decisão
para o modelo. O solver determinará os valores ótimos para essas células.
Definindo as variáveis de decisão. Captura de tela do Excel.
A seguir, devemos definir as células de restrição na planilha e as restrições que se aplicam a essas
células.
Atenção
As células de restrição são aquelas em que implementamos as fórmulas para cada restrição.
Para definir as células de restrição, siga os passos:
Clique no botão incluir.
Métodos Quantitativos
Marcio Quirino - 90
Especificando as células de restrição — passo 1. Captura de tela do Excel.
Preencha a caixa de diálogo incluir restrições.
Especificando as células de restrição — passo 2. Captura de tela do Excel.
Observe que as células E13 e E14 representam as células de restrição cujos valores devem ser
menores ou iguais aos indicados nas células G13 e G14, respectivamente.
Especificando as células de restrição — passo 3. Captura de tela do Excel.
Já especificamos as restrições, mas ainda precisamos determinar que as variáveis de decisão devem
ser iguais ou maiores do que zero. Para isso, basta clicar em tornar variáveis irrestritas não negativas na
caixa de diálogo parâmetros do solver, conforme indicado na figura a seguir. Enfim, para encontrarmos a
solução ótima para o problema, basta clicar no botão resolver.
Métodos Quantitativos
Marcio Quirino - 91
Condições de não negatividade. Captura de tela do Excel.
A figura a seguir apresenta a tela de saída do Excel com a solução ótima para o problema da Fitwear.
Solução ótima para o problema da Fitwear. Captura de tela do Excel.
Observe que x1 deve ser 53,33, x2 recebe 293,333 e o valor ótimo de z é igual a 13.226,67.
Considerações Finais
A pesquisa operacional pode nos auxiliar no apoio a processos de decisão, em especial para
problemas complexos. Estudamos o método simplex, tanto pelo modo analítico quanto pelo tabular, por meio
do qual aprendemos a resolver problemas de programação linear, encontrando a solução ótima para este
tipo de problema. Contudo, resolvê-los manualmente é muito trabalhoso, envolvendo um grande número de
cálculos. Um simples erro em uma das contas requeridas implica encontrar uma solução equivocada para o
problema. Por isso, é muito importante conhecer softwares computacionais que permitem a solução de
problemas de programação matemática.
São muitos os softwares computacionais dedicados à solução de problemas de programação
matemática, como o CPLEx, o GAMS, o LINDO, o LINGO etc. No entanto, problemas de programação linear
podem ser resolvidos pelo solver de pacotes de planilhas eletrônicas. Aprendemos a solucionar problemas
de programação linear por meio do solver do Excel. Isso certamente facilitará que consigamos aplicar a
Pesquisa Operacional para a solução de problemas reais.
Métodos Quantitativos
Marcio Quirino - 92
Referências
ARENALES, M. et al. Pesquisa operacional. Rio de Janeiro: Elsevier, 2007.
FOGLIATO, F. Pesquisa operacional. Porto Alegre, 2006. (Notas de aula).
GOLDBARG, M. C.; LUNA, H. P. Otimização combinatória e programação linear. 2. ed. São Paulo:
Campus, 2005.
LACHTERMACHER, G. Pesquisa operacional na tomada de decisões. Rio de Janeiro: Campus,
2009.
RAGSDALE, C. T. Modelagem e análise de decisão. São Paulo: Cengage Learning, 2014.
RODRIGUES, L. H.; AHLERT, F.; LACERDA, D. P.; CAMARGO, L. F. R.; LIMA, P. Pesquisa
operacional: programação linear passo a passo: do entendimento do problema à interpretação da solução.
São Leopoldo: Unisinos, 2014.
Explore+
Para saber mais sobre os assuntos tratados nesta aula, leia:
Conheça métodos preparatórios (utilizados antes do emprego do simplex) para resolver problemas
diferentes do padrão de maximização com restrições do tipo menor ou igual no capítulo 4 do livro “Operations
research: applications and algorithms (Vol. 3)”, de Winston e Goldberg (2004).
Para se aprofundar na utilização do solver para a solução de problemas de programação linear,
sugerimos a leitura do capítulo 3 do livro “Modelagem e análise de decisão”, de Ragsdale (2009)...................................................................................................... 74
2. Solução de problemas de programação linear ...................................................................... 82
Utilização do solver para solução de problemas de programação linear ................................................. 82
Passos para implementar um problema de programação linear em planilha ........................................... 82
Instalando o solver ................................................................................................................................... 83
Utilizando o solver .................................................................................................................................... 85
Considerações Finais ............................................................................................................................... 91
Referências .............................................................................................................................................. 92
Explore+ ................................................................................................................................................... 92
Métodos Quantitativos
Marcio Quirino - 4
Métodos Quantitativos
Saiba Quais Conteúdos Você Irá Aprender Conosco
Onboarding
Seja bem-vindo à disciplina de Métodos Quantitativos, um componente crucial em sua formação
acadêmica e profissional. Aqui, você será introduzido aos conceitos fundamentais e técnicas avançadas de
Pesquisa Operacional, essenciais na otimização de processos decisórios em diversos contextos
empresariais e econômicos.
Nossa jornada inicia-se com o estudo da Programação Linear, um poderoso instrumento analítico
para resolver problemas de otimização. Você aprenderá sobre suas características e propriedades, e como
essa abordagem pode ser aplicada para melhorar a eficiência e eficácia nas operações e estratégias das
empresas. Por meio da técnica do método gráfico, você adquirirá a habilidade de visualizar e solucionar
problemas de Programação Linear, uma competência fundamental no mundo corporativo.
A técnica de modelagem será uma ferramenta constante em nosso percurso. Você aplicará essa
técnica em situações variadas, desde problemas clássicos até cenários mais complexos, como os
envolvendo questões de transporte, transbordo e alocação. Essa versatilidade na aplicação de modelos
quantitativos é crucial para um gestor, permitindo uma adaptação e resposta ágeis às diversas situações e
desafios empresariais.
A dualidade e a sensibilidade são conceitos que exploraremos profundamente, ajudando-o a
compreender como as soluções podem ser adaptadas frente às incertezas e alterações nos cenários de
negócios. Isso lhe proporcionará uma base sólida para fazer análises críticas e tomar decisões estratégicas
mais informadas.
O método simplex, uma das pedras angulares da Programação Linear, será outro foco de nosso
aprendizado. Através dele, você será capaz de resolver problemas complexos e melhorar sua capacidade
de tomada de decisão em situações que requerem pensamento analítico e estratégico.
Além disso, o uso do solver como ferramenta para solucionar problemas de Programação Linear o
capacitará a lidar com questões práticas e reais, simulando a aplicação direta dos conhecimentos adquiridos
em situações do cotidiano empresarial.
Ao concluir esta disciplina, você não somente terá desenvolvido habilidades quantitativas e analíticas
fundamentais, mas também terá adquirido uma compreensão prática de como essas habilidades se aplicam
no ambiente profissional. Isso será um diferencial significativo em sua jornada para se tornar um gestor
eficaz e bem-sucedido, capaz de usar o conhecimento quantitativo como uma ferramenta vital para a tomada
de decisões estratégicas. Este é o início de uma jornada empolgante que irá enriquecer não apenas seu
conhecimento acadêmico, mas também sua competência profissional. Bem-vindo a esta viagem de
descoberta e desenvolvimento.
Métodos Quantitativos
Marcio Quirino - 5
A Pesquisa Operacional Como Ferramenta de Apoio à
Decisão
Descrição
A Pesquisa Operacional e sua aplicação na análise de decisões, a Programação Linear na solução
de problemas complexos e o método gráfico para a solução de modelos de Programação Linear.
Propósito
Compreender o conceito, a origem e as aplicações da Pesquisa Operacional para fins de apoio ao
processo de tomada de decisão na atuação como gestor, em especial, na solução de problemas complexos.
Preparação
Antes de iniciar o conteúdo, tenha em mãos uma régua para aplicar o método gráfico. Também são
necessários uma calculadora ou um software editor de planilhas eletrônicas para realizar as operações
matemáticas necessárias.
Objetivos
A. Módulo 1
✓ Descrever conceitos gerais de Pesquisa Operacional e sua importância no processo de
tomada de decisão
B. Módulo 2
✓ Descrever as principais características e propriedades de um modelo de Programação Linear
C. Módulo 3
✓ Aplicar o método gráfico para a solução de problemas de Programação Linear
Introdução
É comum termos dificuldades para identificar a melhor solução quando nos deparamos com um
problema complexo. Afinal, são tantos os dados e possíveis cenários que não conseguimos processar
sozinhos tantas informações. Esse tipo de situação é comum em nossas vidas pessoais e, especialmente,
nos negócios.
Acabamos, nesses casos, tomando decisões com base em opiniões, intuições ou em experiências
passadas – nossas ou mesmo de outras pessoas ou empresas. Sem dúvidas, esses caminhos são
importantes e devem ser sempre considerados no processo de tomada de decisão. No entanto, em situações
complexas, o desenvolvimento de modelos pode ser uma poderosa ferramenta de auxílio à tomada de
decisão.
Modelos são simplificações do objeto ou do problema de decisão que representam. A grande
vantagem em adotar um modelo para apoio ao processo de tomada de decisão é a possibilidade de examinar
diferentes cenários, em geral, de forma mais rápida e barata do que se fosse analisado na realidade.
Entre os diversos tipos de modelo que podem ser utilizados, destacam-se os modelos matemáticos,
que adotam a lógica e a formulação matemática para representar o problema estudado.
A Pesquisa Operacional (PO) é o campo do conhecimento que trata do desenvolvimento de
modelos matemáticos e algoritmos para auxiliar o decisor na análise de problemas complexos. A PO se
destaca por fornecer uma ferramenta quantitativa para apoio ao processo de tomada de decisão para
problemas complexos.
Métodos Quantitativos
Marcio Quirino - 6
No primeiro módulo, iremos abordar os principais conceitos da Pesquisa Operacional, sua origem e
a importância de sua aplicação no ambiente gerencial. A PO compreende diferentes técnicas, como
programação matemática, simulação, cadeias de Markov, métodos estatísticos, Teoria das Filas, Teoria dos
Jogos, Teoria dos Grafos, heurística e meta-heurísticas. Neste conteúdo, iremos focar em programação
matemática, mais precisamente na Programação Linear.
No segundo módulo, conheceremos as técnicas de Programação Linear para o desenvolvimento de
modelos matemáticos e da aplicação do método gráfico para a solução de problemas de Programação
Linear.
1. Conceitos gerais de Pesquisa Operacional
Pesquisa Operacional
A Pesquisa Operacional (PO) é definida pela Sociedade Brasileira de Pesquisa Operacional
(SOBRAPO) como:
A área de conhecimento que estuda, desenvolve e aplica métodos analíticos avançados para auxiliar na
tomada de melhores decisões nas mais diversas áreas de atuação humana. SOBRAPO, 2021
A Pesquisa Operacional fornece ferramentas quantitativas ao processo de tomada de decisões
(PRADO, 2016). Dessa forma, a PO auxilia o decisor na análise de variados aspectos e situaçõesde um
problema complexo, por meio de uso de técnicas de modelagem matemática e eficientes algoritmos
computacionais. Isso permite a tomada de decisões efetivas e a construção de sistemas mais produtivos
(SOBRAPO, 2021).
O estudo da PO permite o domínio de diversas técnicas relacionadas à programação e
modelagem matemática.
Por meio desses conceitos e das ferramentas quantitativas, poderemos analisar os mais variados
tipos de problemas, e fornecendo dados e informações concretos para auxiliar no processo de tomada de
decisão.
Saiba mais
Sociedade Brasileira de Pesquisa Operacional
Fundada em 1969, a Sociedade Brasileira de Pesquisa Operacional (SOBRAPO) reúne os profissionais de
Pesquisa Operacional que atuam no País – em universidades, na iniciativa privada e no setor público –, com o objetivo
de incentivar o desenvolvimento desse campo do conhecimento.
Além de organizar simpósios anuais, a SOBRAPO mantém as revistas Pesquisa Operacional e Pesquisa
Operacional para Desenvolvimento, buscando incentivar a publicação sobre o tema.
Origem – Circo de Blackett
A PO teve seus primeiros casos de aplicação no meio militar, durante a Segunda Guerra Mundial.
Na ocasião, foram formados grupos de cientistas de diferentes especialidades a fim de oferecer apoio
quantitativo aos comandantes das operações militares inglesas e norte-americanas para a solução de
complexos problemas de natureza logística e de tática e estratégia militar (BELFIORE; FÁVERO, 2012).
Saiba mais
Entre os grupos formados, destacou-se o aquele liderado por Patrick Maynard Stuart Blackett – o Barão de
Blackett. A equipe do Barão de Blackett, composta por membros de formações diversas – físicos, matemático,
topógrafos, astrofísicos e fisiólogos –, era conhecida como o Circo de Blackett. A equipe foi responsável pela publicação
de um dos primeiros artigos sobre Pesquisa Operacional.
Métodos Quantitativos
Marcio Quirino - 7
O artigo apresentava um modelo matemático para analisar o emprego dos meios antiaéreos das
tropas aliadas para fazer frente aos bombardeiros alemães (Stuckas). Outros problemas típicos abordados
na ocasião se referiam ao tamanho e roteamento de comboios, ao gerenciamento da produção e à
distribuição de armamentos e munições, à coleta e distribuição de correspondência, ao problema de escala
e à localização de radares, de modo a maximizar as áreas de cobertura.
Os bons resultados obtidos com a aplicação das técnicas de Pesquisa Operacional durante a
Segunda Guerra levaram à disseminação desse conhecimento entre organizações de diversas áreas
após o fim do período de combate.
A partir de 1947, é crescente o interesse das indústrias na utilização das técnicas desenvolvidas na
área militar para auxiliar no planejamento e controle da produção.
Atenção
A disseminação da Pesquisa Operacional na área de planejamento e controle, no entanto, só foi possível
devido aos avanços que ocorriam no campo da informática. Tais avanços permitiram o advento de microcomputadores,
bem como o aumento da velocidade e de capacidade de processamento computacional.
Aplicação da PO na análise de decisão
Empresas dos mais diversos setores, atualmente, empregam técnicas de Pesquisa Operacional com
intuito de tornar seu processo de tomada de decisão mais eficiente e assertivo. Além do meio militar, a PO
é aplicada em indústrias de manufaturas, empresas de transporte, empresas de construção, de
telecomunicações, bancos, em assistência médica e até no serviço público.
Veja algumas empresas que utilizam a PO:
A. Petrobrás
✓ A Petrobrás é uma empresa petroleira que possui diversos especialistas em pesquisa
operacional em seu quadro de funcionários. Esses especialistas utilizam modelos
matemáticos para analisar e criar cenários para diferentes problemas de natureza complexa.
✓ Entre os problemas resolvidos com auxílio da PO, podemos citar o dimensionamento da frota
e a roteirização de helicópteros para o transporte de pessoal para as plataformas offshore, a
previsão de reservas de petróleo, a programação de operações em poços de petróleo, a
alocação de equipes em diversas atividades ou o gerenciamento da distribuição de derivados
de petróleo.
B. MRS Logística
✓ A MRS Logística – operador ferroviário que atua na Malha Regional Sudeste da antiga Rede
Ferroviária Federal S.A. – também é um exemplo de empresa brasileira que adota diferentes
técnicas de pesquisa operacional para apoiar seus diferentes processos de tomada de
decisão.
✓ A MRS possui especialistas em diversas técnicas de PO que utilizam seu conhecimento para
apoiar a solução de problemas complexos. Entre esses problemas, estão a alocação eficiente
da tripulação nos trens, a alocação de locomotivas e vagões nas diferentes composições de
trens, a programação de manutenção preventiva de seus ativos, ou o processo de
planejamento e programação do transporte ferroviário de carga.
C. Consultoria especializada
✓ Existem empresas de consultoria especializadas em Pesquisa Operacional, que fornecem
seus serviços para auxiliar outras organizações na solução em seus processos de tomada de
decisão. Tais empresas utilizam conceitos das diversas áreas da PO – como programação
matemática, simulação ou Inteligência Computacional – para modelar os problemas de seus
clientes.
Métodos Quantitativos
Marcio Quirino - 8
✓ As empresas conseguem, com isso, rodar diversas análises, fornecendo dados aos seus
clientes sobre como o evento em estudo se comportaria em diversos cenários, sujeito a
alterações dos parâmetros.
Problemas do cotidiano
É evidente a importância da Pesquisa Operacional na análise de decisão, em especial no ambiente
gerencial. No entanto, as técnicas de pesquisa operacional também podem auxiliar a tomar decisões no seu
dia a dia.
Exemplo
Vamos supor que você queira comprar seu primeiro carro. Para isso, tem economizado a remuneração que
recebe no estágio e deseja selecionar investimentos para obter o melhor rendimento possível. Nesse caso, o
planejamento financeiro pode ser modelado por um modelo matemático que auxiliará a maximizar os seus rendimentos.
O planejamento financeiro é apenas um exemplo de como você pode aplicar conceitos de PO em sua vida
cotidiana.
Ao aplicar conceitos de PO para a solução de um problema, desenvolvemos um modelo
matemático para representar o fenômeno estudado. Dessa forma, conseguimos analisar diversos
cenários e ter estimativas baseadas em uma análise quantitativa.
As decisões, portanto, não serão tomadas apenas com base em opiniões, intuições ou experiências
passadas de outras pessoas ou empresas. Ao modelar um problema, temos um processo decisório mais
criterioso e com menos incertezas.
Modelo
"Um modelo é uma representação abstrata e simplificada de um sistema real, com o qual se pode explicar,
reproduzir, simular ou testar seu comportamento, no todo ou em partes". COUGO, 1997
Um mapa é um modelo, assim como uma maquete que o arquiteto utiliza para que seus clientes
consigam ter noção da visão espacial, em 3D, do projeto desenvolvido. Uma formulação matemática usada
para expressar um fenômeno físico também é um modelo.
É importante ter em mente que os modelos são versões simplificadas do objeto ou problema
de decisão que representam.
Entretanto, para que seja válido, o modelo precisa representar, de forma precisa, as características
relevantes do objeto ou problema de decisão estudado. Afinal, espera-se que o modelo melhore os
processos de tomada de decisão ao ser implementado.
Atenção
A modelagem permite explicitar objetivos, bem como a possibilidade de ganhar conhecimento e entendimento
sobre o problema investigado. Além disso, a implantação de um modelo quantifica as decisões, permitindo a análise
de cenários que seriam impossíveis de serem analisados na realidade. Outra vantagem da construção de modelos é a
economia de recursos e de tempo.
Na PO,modelamos os problemas matematicamente e, a partir do modelo obtido, usamos algoritmos
para encontrar soluções para diferentes cenários do problema a ser analisado. Podemos utilizar diferentes
tipos de modelos, como veremos a seguir nesta aula.
Os diferentes tipos de modelo nos levam a adotar diferentes técnicas de PO, como Programação
Linear, Programação Não Linear, Teoria das Filas, Simulação, Inteligência Computacional e Teoria
dos Jogos. Nesta aula, vamos conhecer os modelos de Programação Linear.
Veja o posicionamento da Associação Brasileira de Pesquisa Operacional (ABEPRO) sobre
Disciplinas da pesquisa Operacional:
Métodos Quantitativos
Marcio Quirino - 9
A. Disciplinas da Pesquisa Operacional
✓ A Associação Brasileira de Pesquisa Operacional (ABEPRO) é a instituição representativa de
docentes, discentes e profissionais de Engenharia de Produção no País. Em 2017, a
ABEPRO organizou as áreas do conhecimento relacionadas à Engenharia de Produção, tanto
na graduação quanto na Pós-Graduação, na pesquisa e nas atividades profissionais.
✓ A Pesquisa Operacional, por ser uma importante área do conhecimento para a Engenharia
de Produção, foi incluída na organização da ABEPRO.
✓ De acordo com o documento da ABEPRO, a PO envolve resolução de problemas reais,
envolvendo situações de tomada de decisão, por meio de modelos matemáticos processados
computacionalmente. Aplica conceitos e métodos de outras disciplinas científicas na
concepção, no planejamento ou na operação de sistemas para atingir seus objetivos. Procura,
assim, introduzir elementos de objetividade e racionalidade nos processos de tomada de
decisão, sem descuidar dos elementos subjetivos e de enquadramento organizacional que
caracterizam os problemas.
✓ O documento ainda organiza as principais disciplinas de PO em:
1. Modelagem, Simulação e Otimização
2. Programação Matemática
3. Processos Decisórios
4. Processos Estocásticos
5. Teoria dos Jogos
6. Análise de Demanda
7. Inteligência Computacional
O foco deste tema é a Programação Matemática.
Modelos matemáticos
Ragsdale (2009) define um modelo matemático como:
Conjunto de relacionamentos matemáticos e suposições lógicas, geralmente implementados em um
computador, como representação de algum problema ou fenômeno de decisão do mundo real.
O modelo matemático usa a lógica e a formulação matemática para obter uma representação do
problema ou do evento a ser analisado e, a partir de então, analisar, desenvolver cenários e obter soluções
para a situação modelada.
O uso de modelos matemáticos é mais barato do que replicar a estrutura real, além de permitir
testar todas as possíveis soluções para diferentes cenários (RODRIGUES et al., 2014).
Composição
Um modelo matemático em pesquisa operacional é composto, basicamente, por variáveis de
decisão, funções objetivo e restrições. O modelo de otimização busca os valores das variáveis de decisão
que otimizam – maximizam ou minimizam – a função objetivo, ao mesmo tempo em que atendem às
restrições às quais o problema é submetido. Vejamos alguns exemplos:
A. Função objetivo - maximizar ou minimizar
✓ Maximizar lucro de uma empresa
B. Sujeito a restrições
✓ Disponibilidade de matérias-primas, de mão de obra etc.
Por exemplo, para aplicar o dinheiro que você conseguiu economizar com a remuneração de seu
estágio, você vai ao banco verificar as diferentes opções de investimento disponíveis.
Nesse problema, você deseja maximizar seu rendimento – função objetivo. Os recursos que você
aplicará em cada opção de investimento são as variáveis de decisão. Além disso, você está sujeito às
Métodos Quantitativos
Marcio Quirino - 10
restrições relativas ao total de recurso disponíveis e às exigências do banco para que sejam realizadas as
diferentes aplicações.
Classificação
Os modelos matemáticos de otimização, segundo Winston (2004), podem ser classificados em:
A. Modelos estáticos ou dinâmicos
✓ As variáveis de decisões nos modelos estáticos não envolvem sequências de decisões em
múltiplos períodos de tempo, ao contrário do que ocorre em modelos dinâmicos.
✓ Em outras palavras, em um modelo estático, analisamos o problema em um único intervalo
de tempo. Já em um modelo dinâmico, analisamos o problema ao longo do tempo.
B. Modelos lineares ou não lineares
✓ Quando as funções objetivo e restrições envolvem apenas equações lineares, temos um
modelo linear. Quando a função objetivo ou alguma restrição é função polinomial ou de
qualquer outro tipo, temos modelos não lineares.
✓ A solução de modelos não lineares é mais complexa do que a de modelos lineares.
C. Modelos inteiros ou não inteiros
✓ Quando todas as variáveis de decisão estão livres para assumir valores fracionais, temos um
modelo não inteiro. No entanto, se uma ou mais variáveis de decisão adotadas no modelo
matemático necessitam ser inteiras, temos um modelo inteiro.
D. Modelos determinísticos ou estocásticos
✓ Os componentes são definidos a priori, ou seja, sem aleatoriedade. No entanto, quando os
elementos apresentam probabilidade de ocorrência – ou seja, há aleatoriedade –, temos um
modelo estocástico.
Neste conteúdo, abordaremos apenas os modelos determinísticos.
Fases de um estudo de Pesquisa Operacional
Winston (2004) propõe um procedimento composto por sete passos para o desenvolvimento de
modelos matemáticos em estudos de pesquisa operacional, conforme apresentado na imagem abaixo:
Procedimento para desenvolvimento de modelos matemáticos em estudos de pesquisa operacional.
Métodos Quantitativos
Marcio Quirino - 11
A. Formulação do problema
✓ O passo inicial do procedimento proposto por Winston (2004) consiste em entender e definir
o problema a ser analisado. Para tanto, é preciso identificar os objetivos e processos
organizacionais que precisam ser estudados antes de resolver o problema. De tal forma, é
fundamental ouvir aquele que lida com o problema.
✓ A comunicação com o cliente, nesse momento, é indispensável para entender a situação real
a ser modelada. No exemplo da seleção dos investimentos a serem realizados com a
remuneração de seu estágio, o problema consiste em maximizar os rendimentos de suas
aplicações financeiras.
B. Observação do sistema
✓ É necessário, em seguida, observar o sistema para descobrir o que deve ser determinado –
as variáveis do problema – e aquilo que está disponível – os dados do problema. Nessa etapa,
devem ser coletados os dados necessários para estimar os valores das variáveis e os
parâmetros que afetam o problema analisado. Tais estimativas são adotadas no
desenvolvimento do modelo (passo 3) e em sua análise (passo 4).
✓ É nesse momento que coletamos os dados para nossos parâmetros e as variáveis de entrada.
É importante ressaltar a importância do processo de coleta de dados, pois a qualidade dos
dados de entrada é fundamental para a qualidade dos resultados obtidos pelo modelo.
✓ No exemplo da seleção dos investimentos a serem realizados com a remuneração de seu
estágio, é preciso que você conheça as taxas de administração do banco, o rendimento de
cada opção de investimento e o valor mínimo que deve ser aplicado em cada opção.
C. Formulação do modelo matemático
✓ O modelo matemático é desenvolvido nessa etapa, com a identificação das variáveis de
decisão, sua função objetivo e suas restrições. Ao longo desta aula, desenvolveremos a
formulação de vários modelos matemáticos para a solução de problemas.
D. Verificação do modelo matemático e uso para predição
✓ Após o desenvolvimento do modelo matemático, é necessário se certificar de que o modelo
é válido e representa a realidade de forma fidedigna. Deve-se ter em mente que não basta
aplicar cegamente o modelo desenvolvido.
✓ Caso ocorram modificações na situação real que está sendo analisada, é necessário que tais
modificações possam ser incorporadas no modelo. No exemploda seleção dos
investimentos, novas opções de investimento poderiam ser oferecidas pelo banco, e você
deve poder incorporá-las em sua análise.
E. Seleção da melhor alternativa
✓ Este é o momento de selecionar a alternativa – ou as alternativas, afinal, podemos ter mais
de uma solução ótima – que otimiza a função objetivo do problema analisado.
F. Apresentação dos resultados e conclusão
✓ As melhores alternativas e os diferentes cenários devem ser apresentados ao decisor, para
que ele tenha todas as informações necessárias para uma tomada de decisão mais assertiva.
Nesse momento, pode ser que o decisor não esteja contente com os resultados
apresentados.
✓ Isso pode ocorrer em função de alguma definição incorreta do problema analisado, devido a
problemas na etapa de formulação do problema – etapa 1 –, ou mesmo à falha por parte do
modelador em envolver o decisor no projeto desde o início. Desse modo, pode ser necessário
retornar para os passos 1, 2 ou 3.
G. Implantação e análise das recomendações
✓ O sistema deve ser constantemente monitorado, e qualquer alteração deve ser incorporada
ao modelo, de modo que as recomendações permitam que a organização atinja seus
objetivos.
Métodos Quantitativos
Marcio Quirino - 12
2. Principais características e propriedades de um modelo de
Programação Linear
Programação Linear
A Programação Matemática – geralmente chamada de otimização –, pode ser definida como:
Um campo da ciência de gerenciamento que encontra a maneira ideal ou mais eficiente de usar recursos
limitados para atingir os objetivos de um indivíduo ou de uma empresa. RASGADALE, 2009
A Programação Linear, por sua vez, é uma das técnicas mais difundidas de otimização, e sua
aplicação é indicada para a solução de problemas de otimização que podem ser modelados por meio de
equações lineares.
Saiba mais
A Programação Linear vem sendo aplicada em problemas de indústrias de diferentes setores, como bancos,
petroleiras, empresas de educação ou em operadores de transportes. Empresas como a Fedex e a Amazon, por
exemplo, utilizam essas técnicas para programar as rotas e determinar o caminho mínimo na gestão de suas cadeias
de distribuição.
No processo de modelagem, é preciso entender as características do problema a fim de traduzi-las
para uma linguagem matemática. No caso específico da Programação Linear, essa “tradução” ocorre por
meio do desenvolvimento de uma série de equações lineares, que representam as características do
problema analisado.
Atenção
A Programação Linear, em suma, é uma técnica de solução de problemas que visa determinar o máximo ou o
mínimo de uma função linear cujas variáveis estão sujeitas a um conjunto de restrições representadas por um sistema
de equações ou inequações lineares.
Características
As principais características de problemas de Programação Linear são:
1. Todas as equações são da forma linear, ou seja:
2. Há sempre um objetivo a ser otimizado – maximizado ou minimizado. Isso significa que há sempre
a busca pela melhor solução entre várias alternativas. Apenas um objetivo pode ser otimizado
por vez, sendo representado pela função objetivo.
3. No problema, há fatores controláveis que serão analisados, verificando-se os valores desses
fatores que levam ao melhor resultado para otimizar o objetivo. Tais fatores controláveis são as
variáveis de decisão (x1, x2, ..., xm). A função objetivo é escrita em termos das variáveis de
decisão.
4. No problema, há fatores não controláveis que influenciam os resultados encontrados para as
variáveis de decisão. Esses fatores não controláveis são os parâmetros (a1, a2, ..., am).
Elementos
Um modelo de Programação Linear apresenta elementos principais – as variáveis de decisão, os
parâmetros, a função objetivo e o conjunto de restrição. A seguir, vejamos cada um deles.
A. Variáveis de decisão
✓ São os fatores controláveis do problema a ser analisado. Trata-se, portanto, das incógnitas a
serem definidas na solução do problema de otimização. Podemos citar como exemplo a
Métodos Quantitativos
Marcio Quirino - 13
quantidade de um produto a ser transportado da origem i para o destino j, x ij, sendo x a
quantidade do produto a ser transportado de i para j.
B. Parâmetros
✓ São os fatores não controláveis do problema a ser analisado, ou seja, os dados de entrada
que devem ser coletados antes da etapa de modelagem do problema. Os parâmetros
influenciam diretamente os valores obtidos para a solução ótima do problema de otimização.
✓ Como exemplo, podemos citar o custo de transportar uma unidade de um produto por
quilômetro, cij. Nesse caso, c corresponde ao custo por quilômetro percorrido no transporte
de um determinado produto de i para j – R$/km.
C. Função objetivo
✓ É a expressão matemática do objetivo a ser maximizado ou minimizado na situação
analisada. Por exemplo, pode-se desejar minimizar o custo total do transporte de um produto
de n origens i para m possíveis destinos j. Dessa forma, a função objetivo seria:
✓ Min Custo=
D. Restrições
✓ É um conjunto de equações lineares que traduzem o limite físico à solução do problema, ou
seja, são os limitantes dos valores das variáveis de decisão. Por exemplo, a quantidade total
de um produto que pode ser transportado da origem i para o destino j não pode ser infinita.
✓ Esse total é limitado pela disponibilidade de produtos na origem i. Desse modo, temos que
, sendo Si a disponibilidade de produto na origem i.
E. Representação
✓ Podemos representar um modelo de Programação Linear da seguinte forma:
Passo a passo para a construção de um modelo de Programação
Linear
Uma vez compreendidas as principais características e os principais elementos de problemas de
Programação Linear, podemos passar para a construção de modelos matemáticos de Programação Linear.
No processo de modelagem, devemos transformar a linguagem do problema em uma linguagem
matemática. Para isso, devemos começar definindo as variáveis de decisão e, posteriormente, a função
objetivo e as restrições.
Sugerimos que seja seguida uma sequência de três passos para a modelagem de um problema de
Programação Linear, conforme apresentado na imagem a seguir:
Métodos Quantitativos
Marcio Quirino - 14
Procedimento para desenvolvimento de modelos de Programação Linear.
A. Identificação das variáveis de decisão
✓ O passo inicial do procedimento proposto consiste em identificar as variáveis desconhecidas
a serem determinadas – variáveis de decisão.
B. Identificação da função objetivo
✓ Nessa etapa, deve-se identificar o objetivo a ser atingido e representá-lo como uma função
linear das variáveis de decisão. Conforme Rodrigues et al. (2014) orientam, essa etapa é
explicitada no enunciado do problema, bastando uma leitura atenta do texto.
✓ Deve-se prestar especial atenção a alguns sinalizadores, como:
o Deseja-se minimizar o custo total de transporte – minimização.
o Deseja-se maximizar o lucro da empresa. – maximização.
C. Identificação do conjunto de restrições
✓ Nessa etapa, devem ser listadas todas as restrições do problema, sendo expressas como
equações (=) ou inequações lineares (>,de um problema de
Programação Linear por meio da construção de um modelo. Para isso, seguiremos os passos apresentados
previamente.
Exemplo
A Fitwear S/A é uma confecção de roupas esportivas e tem uma linha fitness feminina. Essa linha produz
roupas de ginástica exclusivas para mulheres, como tops e calças de lycra.
Cada top de ginástica é vendido por R$ 80,00 e utiliza R$ 20,00 de matéria-prima, como tecido e alinhamentos,
e R$ 32,00 com mão de obra. Além disso, são demandados 30 minutos de corte e 15 minutos de costura para a
confecção de um top de ginástica.
Métodos Quantitativos
Marcio Quirino - 15
Cada calça de ginástica é vendida por R$ 120,00 e utiliza R$ 35,00 de matéria-prima, como tecido e
alinhamentos, e R$ 40,00 de mão de obra. São demandados 15 minutos de corte e 30 minutos de costura para a
confecção de uma calça de ginástica.
A Fitwear só pode contar com 100 horas de corte por semana e 160 horas de costura. A confecção não tem
problemas no fornecimento de matérias-primas, de modo que o seu suprimento pode ser considerado ilimitado assim
como a demanda semanal de seus produtos.
A Fitwear deseja planejar sua produção semanal de modo a maximizar seus lucros.
Vamos usar, a seguir, os passos do procedimento proposto para construção do modelo de
Programação Linear para o caso da Fitwear S/A.
Identificação das variáveis de decisão
As variáveis de decisão devem descrever completamente as decisões a serem tomadas. No caso da
Fitwear, a empresa deve decidir os produtos a serem confeccionados. Com isso, a definição da Variável de
Decisão seria:
• xi – quantidade de produto i confeccionada
Desse modo, temos:
• x1 = Número de tops de ginástica confeccionados a cada semana.
• x2 = Número de calças de ginástica confeccionadas a cada semana.
Identificação da função objetivo
Em qualquer problema de Programação Linear, o analista sempre deseja maximizar ou minimizar
alguma função das variáveis de decisão. No enunciado do problema, devemos procurar pelo propósito que
se procura atingir. Dessa forma, saberemos o que deve ser maximizado ou minimizado a fim de definirmos
a função objetivo.
No caso da Fitwear, a empresa deseja maximizar seu lucro semanal:
A Fitwear deseja planejar sua produção semanal de modo a maximizar seus lucros.
Atenção
Lucro semanal = lucro semanal oriundo da venda de tops + lucro semanal oriundo da venda de calças.
Precisamos, portanto, determinar o ganho semanal obtido com a venda dos produtos e subtrair
destes os gastos semanais com matéria-prima e mão de obra. Vejamos:
Ganho semanal da venda de tops e calças
Cada top é vendido por R$ 80,00, e cada calça é vendida por R$ 120,00. Logo, o ganho semanal é
igual a 80x1 + 120x2.
Observe que também devemos considerar os custos. Vejamos:
A. Gasto semanal com matéria-prima
✓ Cada top utiliza R$ 20,00 em matéria-prima, e cada calça utiliza R$ 35,00.
✓ Logo, o gasto semanal com matéria-prima é igual a 20x1 + 35x2.
B. Gasto semanal com mão de obra
✓ Para confeccionar cada top, gasta-se R$ 32,00 em mão de obra. Para cada calça, gasta-se
R$ 40,00. Logo, o gasto semanal com mão de obra é igual a 32x1 + 40x2.
Desse modo, para determinar a função objetivo, tem-se:
• (+) Ganho semanal com vendas: (80x1 + 120x2)
• (-) Custo de matéria-prima: – (20x1 + 35x2)
Métodos Quantitativos
Marcio Quirino - 16
• (-) Custo de mão de obra: – (32x1 + 40x2)
• (80x1 + 120x2) – (20x1 + 35x2) – (32x1 + 40x2) = 28x1 + 45x2
A função objetivo, portanto, é
Os coeficientes da função objetivo indicam a contribuição de cada variável nos lucros da
Fitwear.
Identificação do conjunto de restrições
Observa-se que os valores dos coeficientes da função objetivo para o problema de Programação
Linear do caso da Fitwear são positivos, e este é um problema de maximização. Desse modo, à medida que
x1 e x2 crescem, o valor da função objetivo aumenta. No entanto, x1 e x2 não podem crescer indefinidamente,
pois existem as restrições.
Comentário
No caso do problema da Fitwear, foram consideradas ilimitadas a demanda por seus produtos e a oferta de
matéria-prima, de modo que não entram como restrições no modelo matemático.
Existem, no entanto, duas restrições relacionadas ao tempo disponível para corte e ao tempo disponível para
a costura.
Essas restrições devem ser definidas em termos das variáveis de decisão x1 e x2. Com isso, temos:
A. Restrição 1: 100 horas de corte por semana.
✓ Cada top de ginástica requer 30 minutos de corte, e cada calça de ginástica requer 15 minutos
de corte para sua confecção. Além disso, a Fitwear só pode contar com 100 horas de corte
por semana.
✓ (total de horas de corte/semana) = (0,5x1 + 0,25x2)
✓ Logo, a restrição 1 é dada por: 0,5x1 + 0,25x2 ≤ 100.
B. Restrição 2: 160 horas de costura por semana.
✓ Cada top de ginástica requer 15 minutos de costura, e cada calça de ginástica requer 30
minutos de costura para sua confecção. Além disso, a Fitwear só pode contar com 160 horas
de corte por semana.
✓ (total de horas de costura/semana) = (horas de costura/top) * (tops produzidos/semana) +
(horas de costura/calça) * (calças produzidas/semana)
✓ (total de horas de corte/semana) = (0,25x1 + 0,5x2)
✓ Logo, a restrição 2 é dada por: 0,25x1 + 0,5x2≤160.
C. Restrição 3: restrição de não negatividade das variáveis de decisão.
✓ Há ainda a restrição de não negatividade das variáveis de decisão, uma vez que não se pode
produzir um número negativo de calças e tops de ginástica.
✓ Logo, a restrição 3 é dada por: x1, x2≥0.
Métodos Quantitativos
Marcio Quirino - 17
✓ Após seguirmos os passos indicados para a construção de um modelo de Programação
Linear, temos a formulação matemática para o problema da Fitwear S/A, conforme
apresentado a seguir:
✓ Devemos considerar que o modelo está sujeito a:
o 0,5x1 + 0,25x2 ≤ 100 restrição de horas de corte
o 0,25x1 + 0,5x2 ≤ 160 restrição de horas de costura
o x1, x2 ≥ 0 restrição de não negatividade das variáveis de decisão
3. Método gráfico para a solução de problemas de
Programação Linear
Aplicação do Método Gráfico para a solução de um problema de
Programação Linear
No módulo anterior, aprendemos a modelar um problema de Programação Linear e aplicamos o
conhecimento adquirido para o caso da Fitwear S/A. Dessa forma, conseguimos construir o modelo de
Programação Linear.
Agora, temos outra questão a resolver:
Como podemos solucionar o modelo de Programação Linear de modo a definir a solução que
corresponde ao melhor valor possível da função objetivo? Em outras palavras, como encontramos essa
solução ótima?
Espaço de soluções
As restrições de um modelo de Programação Linear delimitam a região de suas possíveis soluções,
ou seja, definem o conjunto de soluções viáveis. Nesse sentido, o conjunto de restrições delimita o chamado
espaço de soluções.
O espaço de soluções é formado por todos os pontos que satisfazem as restrições do problema.
Vamos determinar, a seguir, o espaço de soluções para o caso da Fitwear.
Voltando ao problema da Fitwear, temos:
Sujeito a:
• 0,5x1 + 0,25x2 ≤ 100 restrição de horas de corte
• 0,25x1 + 0,5x2 ≤ 160 restrição de horas de costura
• x1, x2 ≥ 0 não negatividade das variáveis de decisão
Restrição de horas de corte
A figura a seguir mostra a área delimitada pela restrição referente ao número de horas de corte
disponíveis pela Fitwear por semana, considerando a condição de não negatividade das variáveis de
decisão.
Métodos Quantitativos
Marcio Quirino - 18
Espaço de soluções para a restrição de horas de corte.
Restrição de horas de costura
Já a figura a seguir mostra a área delimitada pela restrição referente ao número de horas de corte
disponíveis pela Fitwear por semana, considerando a condição de não negatividade das variáveis de
decisão.
Espaço de soluções para a restrição de horas de costura.
Delimitação do espaçode soluções
A figura a seguir destaca, em roxo, o espaço de soluções para o problema da Fitwear. Desse modo,
a figura mostra a área delimitada pelo conjunto de restrições para o caso em análise.
• 0,5x1 + 0,25x2 ≤ 100 restrição de horas de corte
• 0,25x1 + 0,5x2 ≤ 160 restrição de horas de costura
• x1, x2 ≥ 0 não negatividade das variáveis de decisão
Espaço de soluções para problema da Fitwear.
Conseguimos visualizar, na figura acima, o espaço de soluções para o problema da Fitwear, que
consiste no quadrilátero formado pelos pontos ABCD.
Métodos Quantitativos
Marcio Quirino - 19
Desse modo, sabemos que todas as possíveis soluções viáveis para o problema da Fitwear
se encontram nesse quadrilátero.
É preciso responder, no entanto, a duas questões fundamentais:
• Qual ponto corresponde ao melhor valor possível da função objetivo?
• Como determinar a solução ótima, ou seja, aquela que maximiza o lucro da confecção?
Já conhecemos o espaço de soluções no caso da Fitwear. Agora, só é preciso determinar qual dos
pontos do quadrilátero ABCD nos proporciona o maior valor de Z= 28x1 + 40x2.
Repare que, para qualquer Z, temos que x2 = 0,25 * Z – 0,7*x1. Essas são as linhas de isocusto, que
são paralelas entre si.
Atenção
Retas paralelas
Duas retas são paralelas quando ocupam o mesmo plano e não possuem nenhum ponto em comum. Desse
modo, as retas paralelas nunca se cruzam.
Duas retas paralelas têm o mesmo coeficiente angular. Logo, se o coeficiente angular de uma reta s é ms, e
esta reta é paralela a uma reta r cujo coeficiente angular corresponde a mr, podemos afirmar que:
ms = mr
Perceba, ainda, que a reta x2= 0,25 * Z - 0,7*x1 é perpendicular ao vetor (28,40), formado pelos
coeficientes da função objetivo. Vejamos:
Z = 28x1 + 40x2 → Vetor (28,40) → x2 = 40/28 * x1= 10/7 * x1
Atenção
Retas perpendiculares
No ponto de intersecção de duas retas perpendiculares, é formado um ângulo reto (de medida igual a 90°).
Duas retas perpendiculares têm os seus coeficientes angulares opostos e inversos. Logo, se o coeficiente
angular de uma reta s é ms, e esta reta é perpendicular a uma reta r cujo coeficiente angular corresponde a mr,
podemos afirmar que:
ms = –1 / mr ou ms.mr = –1
Solução ótima
O passo para finalizar o problema da Fitwear consiste em escolher o ponto no espaço viável que
maximiza o valor da função objetivo. Para tanto, devemos plotar o vetor (28,40) no espaço de soluções e
determinar a reta perpendicular que pertence ao espaço de soluções (quadrilátero ABCD) e possui o maior
valor para Z.
A figura a seguir apresenta o espaço de soluções e o vetor (28,40). Ao se desenhar as retas paralelas
(linhas de isocusto) perpendiculares ao vetor (28,40), temos que a reta que possui maior valor de z e ainda
pertence ao espaço de soluções corresponde a z = 13.226,67 (linha destacada em vermelho), sendo x1
igual a 53,33 e x2 igual a 293,33.
Métodos Quantitativos
Marcio Quirino - 20
Solução ótima para o problema da Fitwear.
Para o problema da Fitwear, temos que o planejamento de produção semanal que traz o maior lucro
possível para a empresa é a confecção de 53,33 tops e 293,33 calças de ginástica. Dessa forma, a Fitwear
teria um lucro semanal equivalente a R$ 13.226,67.
Note que o problema da Fitwear possui apenas duas variáveis de decisão. Esse tipo de problema
mais simples, com apenas duas variáveis de decisão, pode ser resolvido com relativa facilidade por meio de
um método chamado de Método Gráfico. Logo, para encontrar a solução ótima, precisamos seguir os passos
do Método Gráfico, apresentados a seguir:
1. Desenhe as retas correspondentes às restrições do problema e encontre o espaço de soluções.
2. Desenhe o vetor z.
3. Desenhe linhas ortogonais ao vetor z. Essas são as linhas de isocusto, isto é, são as retas que
possuem o mesmo valor de z.
4. Calcule o valor de z no ponto ótimo, ou seja, a linha de isocusto com maior z que ainda toca o
espaço de soluções.
Situações particulares da solução de um problema de Programação
Linear pelo Método Gráfico
Após resolver um problema de otimização, seja pelo Método Gráfico seja por qualquer outro método,
podemos chegar a quatro situações particulares:
1. Solução ótima única e identificada.
2. Inviável, ou seja, não existem soluções viáveis para o problema apresentado.
3. Ilimitado, ou seja, a função objetivo pode crescer infinitamente.
4. Múltiplas soluções, ou seja, o problema possui mais de uma solução ótima (infinitas).
Vejamos, a seguir, cada uma dessas situações representados graficamente.
Solução ótima única
Na figura a seguir vemos um exemplo da aplicação do Método Gráfico para um problema com uma
única solução ótima.
Solução ótima única.
Métodos Quantitativos
Marcio Quirino - 21
Problema inviável
Esta figura apresenta um exemplo da aplicação do Método Gráfico para um problema inviável.
Nesses casos, as restrições não formam nenhum espaço de soluções viáveis.
Problema inviável.
Problema ilimitado
Veja um exemplo da aplicação do Método Gráfico para um problema ilimitado, ou seja, com solução
tendendo ao infinito. Nesses casos, as restrições formam um espaço aberto de soluções viáveis, conforme
pode ser observado no exemplo da figura a seguir.
Observe que se trata de um problema de maximização.
Problema Ilimitado.
Problema de múltiplas soluções
Aqui vemos um exemplo da aplicação do Método Gráfico para um problema de múltiplas soluções,
ou seja, com mais de uma solução ótima. Esse tipo de problema também pode ser denominado de
problemas com soluções alternativas.
Nesses casos, a linha de isocusto, ao abandonar o espaço de soluções viáveis, intersecciona com
uma linha inteira, e não somente um ponto desse conjunto. Isso ocorre porque a linha de isocusto é, na
verdade, paralela à reta dessa restrição, conforme pode ser observado no exemplo da figura a seguir.
Observe que várias soluções são simultaneamente ótimas nesse tipo de problema.
Problema com múltiplas soluções.
Métodos Quantitativos
Marcio Quirino - 22
Considerações Finais
Neste conteúdo, visitamos os principais conceitos da Pesquisa Operacional, abordando a sua origem
e evolução como campo do conhecimento. Verificamos a sua importância e a aplicabilidade de suas técnicas
e ferramentas no apoio ao processo de tomada de decisão em diferentes campos de atuação e setores.
Trabalhamos o conceito de modelo e vimos como um modelo nos traz benefícios na análise de
decisão. Nesse sentido, um modelo é uma simplificação do problema a ser analisado, de modo que nos
permite avaliar diferentes cenários em um menor tempo e com menos recursos.
Para que possamos de fato usufruir desses benefícios, é fundamental que o modelo e a qualidade
dos dados de entrada sejam fidedignos. Nesse contexto, foram apresentados os principais passos a serem
seguidos para o desenvolvimento de um modelo matemático em estudos de Pesquisa Operacional.
Uma das técnicas mais difundidas de Pesquisa Operacional é a Programação Linear, cujos conceitos
também foram apresentados. Aprendemos sobre os principais elementos de um modelo de Programação
Linear e vimos como construir esse tipo de modelo e encontrar sua solução por meio do Método Gráfico.
Todo esse conhecimento foi apresentado por meio do desenvolvimento do modelo matemático para o
exemplo da Fitwear!
Referências
COUGO, P. Modelagem conceitual e projeto de banco de dados. Rio de Janeiro: Elsevier Brasil,
2013.
FÁVERO, L. P.; BELFIORE, P. Pesquisa operacional para cursos de administração. Rio de Janeiro:
Elsevier Brasil, 2012.
OLIVEIRA, F. Métodos quantitativos. Rio de Janeiro, 2016. (Notas de aula).
PRADO, D. Programação linear. Vol. 1. São Paulo: Falconi, 2016.
RAGSDALE, C. T. Modelagem e análise de decisão. São Paulo: Cengage Learning, 2009.
RODRIGUES, L. H.; AHLERT, F.; LACERDA, D. P.; CAMARGO, L. F. R. & LIMA, P. Pesquisaoperacional: programação linear passo a passo – do entendimento do problema à interpretação da solução.
São Leopoldo: Unisinos, 2014.
SOBRAPO – Sociedade Brasileira de Pesquisa Operacional (2021). O que é Pesquisa Operacional?
Disponível em meio eletrônico. Consultado em: 04 fev. 2021.
WINSTON, W. L.; GOLDBERG, J. B. Operations research: applications and algorithms. Vol. 3.
Belmont, Califórnia: Thomson/Brooks/Cole, 2004.
Explore+
Assista ao vídeo O que é Pesquisa Operacional?, da Sociedade Britânica de Pesquisa Operacional
(OR Society), disponível no YouTube, para entender melhor o que é a Pesquisa Operacional, o
desenvolvimento desse campo do conhecimento e suas possibilidades de aplicação.
Leia os capítulos 1 e 2 do livro Pesquisa operacional na tomada de decisões, de G. Lachtermacher,
publicado em 2016.
Leia os capítulos 1 e 2 do livro Modelagem e análise de decisão, de C. T. RAGSDALE, publicado em
2009.
Métodos Quantitativos
Marcio Quirino - 23
Aplicações da Programação Linear
Descrição
Modelagem de problemas clássicos de programação linear: fabricação versus compra, problemas de
mistura, planejamento, produção e estoques, transporte, transbordo e alocação.
Propósito
Discutir os problemas clássicos de programação linear a fim de entender a técnica de modelagem e
a importância desse campo do conhecimento, essencial para a sua formação e atuação no processo de
decisão de problemas complexos.
Preparação
Tenha em mãos uma calculadora ou um software editor de planilhas eletrônicas para que possa
realizar as operações matemáticas necessárias.
Introdução
Os modelos são simplificações do objeto ou problema de decisão que representam. Você pode estar
se perguntando: como a modelagem matemática pode auxiliar o processo de tomada de decisão, em
especial em problemas complexos? A modelagem matemática possibilita examinar diferentes cenários, em
geral, de forma mais rápida e barata do que analisar a situação na realidade.
O foco deste conteúdo é a programação linear, uma das técnicas mais difundidas na Pesquisa
Operacional (PO). Aqui, reforçaremos os conceitos sobre a construção de modelos de programação linear
na modelagem de problemas clássicos de programação linear, abordando suas diferentes aplicações. Com
isso, passaremos a dominar a técnica de modelagem e entenderemos melhor a importância desse campo
do conhecimento, em especial, a sua aplicação no planejamento de redes logísticas, por meio do problema
de transporte e transbordo, e de alocação, problemas clássicos de programação linear que merecem ser
destacados!
1. Técnica de modelagem em problemas clássicos de
programação linear
Modelagem de problemas de programação linear
O processo de modelagem consiste em transformar a linguagem do problema em linguagem
matemática. Para isso, devemos começar definindo as variáveis de decisão e, posteriormente, a função
objetivo e as restrições, conforme os passos ilustrados abaixo:
1. Identificação das variáveis de decisão
2. Identificação da função objetivo
3. Identificação do conjunto de restrições
Atenção
O passo mais importante no desenvolvimento de modelos de programação linear consiste na definição correta
das variáveis de decisão. Um equívoco na seleção das variáveis de decisão implica erros na identificação da função
objetivo e do conjunto de restrições.
Existem classes de modelos de programação linear que são adaptáveis a uma série de situações
práticas, sendo considerados como “problemas típicos.” Esses modelos seguem padrões semelhantes, de
modo que podemos considerar que formam diferentes “classes” de problemas. Assim, se soubermos
Métodos Quantitativos
Marcio Quirino - 24
modelar um destes problemas típicos, provavelmente conseguiremos modelar os demais problemas da
mesma classe. Por isso, é tão importante conhecer esses padrões e entender a lógica por trás da construção
destes modelos matemáticos (RODRIGUES et al., 2014).
Neste módulo, serão abordados alguns dos principais modelos de programação linear considerados
“típicos.” Devemos entender como funciona o padrão de modelagem para cada problema típico para que,
então, possamos aplicar essa mesma lógica a outros problemas da mesma classe, ou seja, que seguem o
mesmo padrão.
Dica
Estude e faça a maior quantidade de exercícios possível. Apenas com a prática você internalizará a lógica e
desenvolverá seus modelos com maior facilidade.
Trataremos, a seguir, dos problemas da mistura, do planejamento de produção e de estoques, e
fazer versus comprar. Estes são problemas clássicos que podem ser aplicados em diferentes setores
produtivos.
Problema da mistura
Muitos modelos de programação linear representam situações em que o tomador de decisão deseja
minimizar o custo para atender a determinadas condições (restrições). O problema da mistura, também
conhecido como o problema da dieta, é um dos modelos clássicos que se encaixa neste tipo de padrão.
Veja mais informações sobre o problema da dieta:
A. O problema da dieta
✓ O problema da dieta foi proposto pela primeira vez por Stiger (1945), tendo sido um dos
primeiros problemas de otimização linear a ser implementado na prática com sucesso. Neste
tipo de problema, o tomador de decisão deseja determinar níveis de utilização de matérias-
primas na composição de uma ração alimentar, que deve respeitar certas características
nutricionais, estando limitado à disponibilidade de matérias-primas e insumos, bem como ao
atendimento da demanda. É importante destacar que este tipo de problema não se limita à
dieta humana, sendo aplicado também à elaboração de rações para gado, peixe, aves etc.
✓ Entretanto, de forma mais ampla, o problema da mistura não se restringe apenas à
composição de rações alimentares. O problema da mistura pode ser aplicado à produção de
ligas metálicas, à especificação de combustíveis, à fabricação de remédios ou de produtos
químicos em geral, à produção de adubos ou de papel. Em suma, o problema da mistura
representa uma classe de modelos clássicos, que podem ser aplicados a diferentes setores.
Neste tipo de problema, diferentes insumos devem ser misturados em uma proporção ideal
para fabricar produtos para a comercialização.
Teoria na prática
Exemplo - problema da dieta
Uma mãe está muito preocupada com a alimentação de seus filhos. Ela deseja que as crianças
tenham uma alimentação equilibrada e, assim, consultou uma nutricionista que lhe recomendou que eles
comam, no mínimo, 10mg de vitamina A, 70mg de vitamina C e 250mg de vitamina D por dia.
Porém, além de se preocupar com a qualidade da alimentação, essa mãe também está preocupada
com os custos. Ela deseja oferecer aos seus filhos essa dieta equilibrada, porém ao menor custo possível.
Por isso, ela fez uma pesquisa e descobriu as informações nutricionais para diferentes tipos de alimento,
conforme apresentado na tabela a seguir:
Métodos Quantitativos
Marcio Quirino - 25
Vitamina Leite (l) Carne (kg) Peixe (kg) Salada (100g)
A 2 2 10 20
C 50 20 10 30
D 80 70 10 80
Tabela de informações nutricionais em mg Fonte: Adaptado de Goldbarg e Luna (2005)
A mãe também foi ao supermercado e verificou que um litro de leite custa R$2,00, um quilo de carne
custa R$20,00, um quilo de peixe custa R$25,00 e para preparar 100g de salada ela gastaria R$3,00.
Vamos usar nossos conhecimentos de programação linear para ajudar essa mãe a escolher a melhor
dieta para seus filhos com o menor custo possível!
Definir variáveis de decisão
O primeiro passo para a modelagem deste exemplo de um clássico problema da dieta é a definição das
variáveis de decisão. A variável de decisão deve ser xi, sendo x a quantidade de alimento do tipo “i” a ser consumida
por dia. Logo, temos:
• x1 = litros de leite a serem consumidos por dia pelas crianças;
• x2 = quilos de carne a serem consumidos por dia pelas crianças;
• x3 = quilos deMais conteúdos dessa disciplina
revisao metodos quantitativos - Resumo- AVA 01
- AVA 02
- AVA 03
- Teste de Novas Receitas PATOLOGIAS - Cookie de Banana
- Pesquisa Ocupacional_ Teste 1_ Tentativa 1 - Nota 10
- Pesquisa Operacional e Modelagem Matemática
- Questionario 2 - Analise de Operacoes_ Revisao da tentativa
- PO - percurso-de-aprendizagem-04
- 1 (814)
- a Teoria das Filas, para que um cliente seja atendido, geralmente, este deve passar por uma fila que é organizada com o objetivo de proporcionar um...
- retende-se realizar a simulação do desempenho limitado de um determinado circuito elétrico composto por capacitores, indutores e resistores, sendo ...
- Pergunta 5 No desenvolvimento de modelos de programação linear, existem classes de modelos que são considerados como "problemas típicos". Esses mo...
- o processamento de uma fila, isto é, na forma como ela será gerenciada, existe a organização de fila, que é muito empregada em centros de distribuição
- Em diversas áreas do conhecimento, como economia, engenharia e ciência da computação, as matrizes são utilizadas para organizar dados e resolver probl
- No método simplex, soluções básicas são pontos no espaço de solução que satisfazem todas as restrições do problema de programação linear (PL). Essa
- os modelos de programação dinâmica, busca-se estabelecer uma estratégia para gerenciar as variáveis podem criar ao longo do tempo, como disponibili...
- Nos modelos de programação dinâmica, busca-se estabelecer uma estratégia para gerenciar as variáveis podem criar ao longo do tempo, como disponibil...
- Questão 10 Para conhecermos o processo de construção do conhecimento matemático, desde suas origens mais primitivas, buscamos vestígios do conhecim...
- 40 Ler em voz alt Uma locadora de automóveis, devido ao aumento da demanda, precisa adquirir novos automóveis. Atualmente há três tipos de veículos à
- ual é a principal desvantagem do método simplex em relação a outros métodos de otimização? A Sensibilidade a problemas mal condicionados. B D...
- Atualmente muitas empresas fazem O envase de água mineral. Uma dessas empresas possui embalagens de 500 ml, 1,5 le de 201. A extração diária é de no m
- Em um problema de programação linear, as limitações do problema geram uma região denominada região factível. Em relação à região factivel, temos as se
- SA1_LI_ATV 1 T3 ATV1_ Pesquisa sobre a DU-E (Declaração Única de Exportação) e as três principais formas de exportação _ Igor Ferreira da Silva
- LT1_Comportamento_Consumidor_Pesquisa_Mercado_30mai19 RPaula
