Modelagem em Pesquisa Operacional

Prévia do material em texto

Aula 1 – Modelagem em Pesquisa Operacional 
Objetivos: 
Ao final desta aula, o estudante será capaz de: 
1. Entender a estrutura básica de um modelo de Pesquisa Operacional. 
2. Modelar via Programação Linear diversos problemas relacionados a diversas 
áreas da Engenharia de Produção. 
1 Introdução à Pesquisa Operacional 
A área de conhecimento denominada Pesquisa Operacional (PO) estuda, desenvolve e 
aplica métodos analíticos (modelos matemáticos, estatísticos ou computacionais) para 
auxílio na tomada de decisão. 
A Pesquisa Operacional (PO) surgiu formalmente na Inglaterra durante a Segunda Guerra 
Mundial (1939-1945), quando um grupo de cientistas ingleses foi convocado para 
solucionar diversos problemas de natureza logística e militar, que visavam definir 
maneiras mais eficientes da utilização de recursos escassos. 
Após a Guerra, as ideias e propostas pelos cientistas foram adaptadas ao setor civil. É 
possível se encontrar desde então aplicações da PO visando a otimização de recursos em 
diversas áreas, como por exemplo em logística, finanças, recursos humanos, 
planejamento da produção, marketing, dentre outras. 
2 Modelos de Pesquisa Operacional 
Imagine um processo de tomada de decisão entre diversas alternativas conflitantes. 
Imagine ainda que existe um número muito grande de variáveis que pode influenciar este 
processo. Neste tipo de caso, um modelo pode auxiliar o decisor, para que o mesmo não 
tome a decisão com base apenas na sua experiência. 
Um modelo pode ser definido como uma simplificação de um sistema real que permite 
ao decisor simular diversos cenários e realizar diversas análises sobre o sistema. A Figura 
1.1 ilustra os passos dados quando um modelo é utilizado como auxílio na tomada de 
decisão. 
 
Figura 1.1 - Passos para o uso de modelos em um sistema real 
 
Observando o fluxograma da Figura 1.1, note que o processo começa com a chamada 
modelagem do problema, ou seja, com a construção de um modelo com base em 
observações do sistema real. Por se tratar de uma simplificação, o modelo não precisa 
contemplar todas as variáveis do sistema real, mas deve contemplar as suas principais. O 
modelo então gera resultados, que são utilizados para validar o modelo. Caso o modelo 
não seja validado, o modelo é revisto a fim de se identificar possíveis variáveis do sistema 
real importantes que não foram consideradas. Já em caso de validação, decisões são 
tomadas com base na interpretação dos resultados obtidos pelo modelo. 
Esta aula foca nos dois primeiros módulos do fluxograma, ou seja, no processo de 
modelagem do sistema real. Os modelos de PO possuem alguns componentes principais, 
que são: parâmetros de entrada; variáveis de decisão; restrições; função objetivo. 
2.1 Parâmetros de entrada 
Os Parâmetros de entrada são constantes com valores já conhecidos antes da construção 
do modelo e antes de se tomar qualquer decisão. 
2.2 Variáveis de Decisão 
As variáveis de decisão (incógnitas) são parâmetros para os quais os valores só serão 
conhecidos após a execução do modelo. Os três tipos de variáveis mais usados neste curso 
são: variáveis contínuas, inteiras ou binárias. Uma variável é dita contínua quando pode 
assumir qualquer valor real. Já a variável inteira pode assumir apenas valores inteiros. 
Finalmente, as variáveis binárias podem assumir apenas valores 1 (um) ou 0 (zero). 
2.3 Restrições 
As restrições são equações ou inequações matemáticas que limitam os possíveis valores 
que as variáveis de decisão podem assumir. 
2.4 Função Objetivo 
A função ou critério objetivo é uma função das variáveis de decisão que se deseja 
minimizar ou maximizar. 
No Exemplo 1.1, temos o nosso primeiro modelo de PO. 
Exemplo 1.1 (Mix de Produção) Uma empresa fabrica dois tipos de ração: R1 e R2. O 
lucro para cada 1 Kg vendido de R1 é R$ 160 enquanto o lucro para 1 kg vendido de R2 é 
100. Para se fabricar 1 kg da ração R1, são necessárias 3h, enquanto para se fabricar 1 kg 
de R2 são necessárias 2h. O tempo máximo mensal disponível para a fabricação de R1 e 
R2 são 90 h. Além disso, uma pesquisa de demanda do mercado mostra que o máximo 
que se deve produzir mensalmente de R1 são 25 kg. Deseja-se um modelo que decida o 
quanto deve ser produzido mensalmente de R1 e R2 de modo que o lucro desta empresa 
seja o maior possível. 
Solução: Todos os dados fornecidos no enunciado prévio, como por exemplo, o lucro 
associado a cada tipo de ração e o tempo necessário para se fabricar cada tipo de ração 
são considerados parâmetros de entrada do modelo. A decisão a ser tomada é a quantidade 
que deve ser fabricada de cada tipo de ração. Assim, criam-se duas variáveis 𝑥1 e 𝑥2, 
indicando a quantidade em Kg a ser fabricada de R1 e R2, respectivamente. 
Uma vez definidas as variáveis, modela-se então a função objetivo. Neste exemplo, 
deseja-se maximizar o lucro total da empresa dado que os lucros unitários de R1 e R2 são 
respectivamente 160 e 100. Matematicamente, a seguinte função objetivo é obtida: 
𝑀𝑎𝑥 𝑧 = 160𝑥1 + 100𝑥2 
O uso de uma variável 𝑧 para representar a função objetivo completa é muito comum em 
modelos de PO. Agora modela-se matematicamente as restrições do problema. Uma das 
restrições diz que a produção a ser realizada deve respeitar a quantidade de horas máxima 
de produção mensal, que é de 90 h. Dado que são necessárias respectivamente 3h e 2h 
para se fabricar um 1 kg de R1 e R2, tem-se então que: 
3𝑥1 + 2𝑥2 ≤ 90 
 A outra restrição do problema é relativa a uma pesquisa de mercado, que diz que o 
máximo que se deve produzir mensalmente de R1 são 25 kg. Matematicamente, tem-se: 
𝑥1 ≤ 25 
Deve-se ainda incluir ainda as restrições 𝑥1 ≥ 0 e 𝑥2 ≥ 0, a fim de evitar que se 
produzam quantidades negativas de cada ração. As restrições prévias são comumente 
chamadas de restrições de não negatividade e aparecem em grande parte dos modelos de 
PO. O modelo completo segue abaixo: 
𝑀𝑎𝑥 𝑧 = 160𝑥1 + 100𝑥2 
s.a.: 3𝑥1 + 2𝑥2 ≤ 90 
𝑥1 ≤ 25 
𝑥1 ≥ 0 
𝑥2 ≥ 0 
 
 
Cada modelo pode ser classificado como modelo de programação linear (PL) ou não 
linear (PNL). Um modelo linear é aquele em que tanto a função objetivo quanto as 
restrições são lineares. Caso contrário, temos um modelo não linear. Para se compreender 
melhor estas classificações, é necessário ter em mente o conceito do que é uma função 
linear. 
 
São exemplos de funções lineares: 𝑓(𝑥) = 2𝑥1 − 3𝑥2, 𝑔(𝑥) = 0,5𝑥1 + 𝑥2. Não são 
exemplos de funções lineares: ℎ(𝑥) = 2
𝑥1
𝑥2
− 3𝑥2, 𝑚(𝑥) = 2(𝑥1)2 + 𝑥2 
Com base na Definição 1.1, note que tanto a função objetivo quanto as restrições do 
modelo do Exemplo 1.1 são lineares. Logo, o Exemplo 1.1 é um exemplo de modelo PL. 
Neste curso, são estudados apenas problemas que podem ser modelados através de algum 
modelo PL. Estes problemas são chamados de Problemas de Programação Linear 
(PPLs). A seguir, são apresentados mais alguns exemplos de PPLs. 
Exemplo 1.2 (problema do transporte) Considere uma empresa que deseja transportar um 
determinado tipo de produto (medido em Kg) das suas 2 fábricas (F1 e F2) até 3 
consumidores (C1, C2, C3). As quantidades demandadas por C1, C2 e C3 são 
respectivamente 40 kg, 60 Kg e 100 Kg. As fábricas F1 e F2 possuem disponível para 
envio 120 Kg e 80 Kg, respectivamente. A Tabela 1.1 fornece o custo por Kg transportado 
entre cada fábrica e cada consumidor. 
Tabela 1.1: Custo por kg transportado entre cada fábrica e cada consumidor 
 C1 C2 C3 
F1 10 12 10 
F2 8 10 11 
 
O termo “s.a” é uma abreviação para “sujeito a”. Este termo é usado para separar a 
função objetivo das restrições. 
 
Nas restrições dos modelos estudados neste curso não são permitidos os sinais de 
estritamente maior (>) e estritamente menor (<). São permitidos apenas os sinais de 
igualdade (=), menor ou igual (≤) ou maior ou igual (≥). 
 
Definição 1.1: uma função 𝑓: ℝ𝑛 → ℝ é dita linear separa um vetor 𝑥 =
(𝑥1, 𝑥2, … , 𝑥𝑛) qualquer, 𝑓(𝑥)é da forma 𝑓(𝑥) = 𝑎1𝑥1 + 𝑎2𝑥2 + ⋯ + 𝑎𝑛𝑥𝑛 , onde 
𝑎1, 𝑎2, … , 𝑎𝑛 ∈ ℝ. 
 
 
Deseja-se um modelo PL que decida como deve ser feito o transporte dos produtos ao 
menor custo possível, garantindo que as demandas sejam atendidas e que a 
disponibilidade de cada fábrica seja respeitada. 
Solução: a decisão neste problema é o quanto é enviado de cada fábrica para cada 
consumidor. Assim, as seguintes variáveis são criadas: 
𝑥𝑖𝑗 → quantidade enviada (em Kg) da fábrica 𝑖 para o cliente 𝑗; 𝑖 = 1, 2 e 𝑗 = 1, 2, 3 
Note que a linha anterior define as seis variáveis do modelo de uma única vez. A função 
objetivo seria 
𝑚𝑖𝑛 𝑧 = 10𝑥11 + 12𝑥12 + 10𝑥13 + 8𝑥21 + 10𝑥22 + 11𝑥23 
Para cada um dos três clientes, deve-se criar uma restrição garantindo que a quantidade 
total a ser enviada para este cliente é igual à quantidade requisitada pelo mesmo: 
𝑥11 + 𝑥21 = 40 
𝑥12 + 𝑥22 = 60 
𝑥13 + 𝑥23 = 100 
Para cada uma das fábricas, deve-se criar uma restrição garantindo que sua capacidade de 
envio é respeitada: 
𝑥11 + 𝑥12 + 𝑥13 ≤ 120 
𝑥21 + 𝑥22 + 𝑥23 ≤ 80 
Note que neste exemplo a soma das demandas é igual a soma das capacidades de envio. 
Assim, os sinais de “≤ " poderiam ser substituídos por “=”. Finalmente, deve-se incluir 
as restrições de não negatividade, garantindo que não são produzidas quantidades 
negativas: 
𝑥𝑖𝑗 ≥ 0; 𝑖 = 1,2; 𝑗 = 1,2,3 
Note que a linha prévia define as seis restrições de não negatividade do modelo de uma 
única vez. O modelo completo é: 
𝑚𝑖𝑛 𝑧 = 10𝑥11 + 12𝑥12 + 10𝑥13 + 8𝑥21 + 10𝑥22 + 11𝑥23 
s.a.: 𝑥11 + 𝑥21 = 40 
𝑥12 + 𝑥22 = 60 
𝑥13 + 𝑥23 = 100 
𝑥11 + 𝑥12 + 𝑥13 ≤ 120 
𝑥21 + 𝑥22 + 𝑥23 ≤ 80 
𝑥𝑖𝑗 ≥ 0; 𝑖 = 1,2; 𝑗 = 1,2,3 
 
Exemplo 1.3 (problema do transbordo) Considere o mesmo exemplo anterior mas com 
uma ligeira diferença: o transporte agora não é feito direto da fábrica para o cliente, mas 
sim passando por um dentre dois centros de distribuição (CD1 e CD2). Em outras palavras, 
as fábricas transportam para os centros de distribuição, que por sua vez distribuem para 
os clientes. Então os custos por Kg do produto transportado de cada fábrica para cada CD 
e de cada CD para cada cliente são: 
 CD1 CD2 
F1 7 9 
F2 6 8 
 
 C1 C2 C3 
CD1 5 6 4 
CD2 3 7 6 
 
A quantidade requisitada por cada cliente e a capacidade de envio de cada fábrica são as 
mesmas do exemplo anterior. Deseja-se novamente um modelo de programação linear 
que decida como deve ser feito o transporte dos produtos ao menor custo possível, 
garantindo que as demandas sejam atendidas e que a disponibilidade de cada fábrica seja 
respeitada. 
Solução: a decisão agora é sobre o quanto vai ser transportado de cada fábrica para cada 
CD e de cada CD para cada cliente. Assim, poderiam ser criadas as seguintes variáveis: 
𝑥𝑖𝑗 → Quantidade enviada (em Kg) da fábrica 𝑖 para o CD 𝑗; 𝑖 = 1,2 e 𝑗 = 1,2 
𝑦𝑗𝑘 → Quantidade enviada (em Kg) do CD 𝑗 para o cliente 𝑘; 𝑗 = 1,2 e 𝑘 = 1,2,3 
A função objetivo visa minimizar o custo total de transporte: 
𝑚𝑖𝑛 𝑧 = 7𝑥11 + 9𝑥12 + 6𝑥21 + 8𝑥22 + 5𝑦11 + 6𝑦12 + 4𝑦13 + 3𝑦21 + 7𝑦22 + 6𝑦23 
De maneira similar ao exemplo anterior, existem restrições garantindo que as quantidades 
requisitadas por cada cliente devem ser atendidas: 
𝑦11 + 𝑦21 = 40 
𝑦12 + 𝑦22 = 60 
𝑦13 + 𝑦23 = 100 
Também de maneira similar ao exemplo anterior, existem restrições que garantam que a 
capacidade de cada fábrica deve ser respeitada: 
𝑥11 + 𝑥12 + 𝑥13 ≤ 120 
𝑥21 + 𝑥22 + 𝑥23 ≤ 80 
Deve-se ainda garantir que a quantidade total que chega em um determinado CD deve ser 
transportada para algum cliente: 
𝑥11 + 𝑥21 = 𝑦11 + 𝑦12 + 𝑦13 
𝑥12 + 𝑥22 = 𝑦21 + 𝑦22 + 𝑦23 
O modelo completo, incluindo as restrições de não negatividade é o que segue: 
𝑚𝑖𝑛 𝑧 = 10𝑥11 + 12𝑥12 + 10𝑥13 + 8𝑥21 + 10𝑥22 + 11𝑥23 
s.a.: 𝑦11 + 𝑦21 = 40 
𝑦12 + 𝑦22 = 60 
𝑦13 + 𝑦23 = 100 
𝑥11 + 𝑥12 + 𝑥13 ≤ 120 
𝑥21 + 𝑥22 + 𝑥23 ≤ 80 
𝑥11 + 𝑥21 = 𝑦11 + 𝑦12 + 𝑦13 
𝑥12 + 𝑥22 = 𝑦21 + 𝑦22 + 𝑦23 
𝑥𝑖𝑗 ≥ 0; 𝑖 = 1,2; 𝑗 = 1,2 
𝑦𝑗𝑘 ≥ 0; 𝑗 = 1,2; 𝑘 = 1,2,3 
 
Exemplo 1.4 (Investimentos) Um investidor possui hoje R$ 20.000,00 para investir nos 
próximos 6 meses. Para isso, possui 4 opções de investimentos: A, B, C e D. Ao final de 
cada aplicação, o capital investido é retornado com um percentual de acréscimo. A 
descrição de cada tipo de investimento encontra-se na tabela 1.2 a seguir: 
Tabela 2.2: Descrição dos investimentos 
Investimento Aplicação 
disponível no 
início dos meses 
Meses de 
duração da 
aplicação 
Percentual retornado 
ao final do 
investimento 
Tipo A 1,2,3,4,5,6 1 0,50% 
Tipo B 1,3,5 2 1,20% 
Tipo C 2, 4 2 1,40% 
Tipo D 1 6 6,00% 
 
Assim, por exemplo, o investimento em B pode ser feito hoje (mês 1), no início do 3º 
mês, ou no início do 5º mês. Em qualquer umas das opções prévias, o capital ficará 
investido por 2 meses. Ao final da aplicação, será devolvido o capital investido acrescido 
1,20%. 
Para diversificar os seus investimentos, em cada mês o investimento máximo em algum 
tipo de aplicação será de R$ 10.000,00. Deseja-se um modelo de programação linear que 
maximize o retorno do investidor no final da aplicação. 
Solução: Inicialmente, uma variável é criada para cada aplicação em cada mês que esta 
estiver disponível. Assim, sejam as variáveis 𝐴1, 𝐴2, 𝐴3, 𝐴4, 𝐴5e 𝐴6 representando o 
capital que será investido em A no início dos meses 1, 2, 3, 4, 5 e 6, respectivamente. 
Com definição similar são criadas as variáveis 𝐵1, 𝐵3, 𝐵5, 𝐶2, 𝐶4 e 𝐷1 para os demais tipos 
de investimentos. 
A função objetivo visa maximizar o capital no final do investimento. Note que os 
investimentos que duram até o final do investimento são 𝐴6, 𝐵5 e 𝐷1. Os demais terminam 
antes. Logo, a função objetivo será: 
𝑚𝑎𝑧 𝑧 = 1,005𝐴6 + 1,012𝐵5 + 1,06𝐷1 
Note que os demais investimentos são considerados de maneira implícita uma vez que o 
investimento em 𝐴6 será dado pelo que foi investido em meses anteriores no próprio 𝐴, 
em B e em C. 
Uma restrição deve garantir que 𝑅$ 20.000,00 serão investidos no primeiro mês. 
Matematicamente, tem-se: 
𝐴1 + 𝐵1 + 𝐷1 = 20.000 
Depois, deve-se criar uma restrição para cada um dos demais meses garantindo que o total 
investido em cada mês é igual ao retorno proveniente de meses anteriores. 
𝐶2 + 𝐴2 = 1,005𝐴1 (𝑚ê𝑠 2) 
𝐵3 + 𝐴3 = 1,005𝐴2 + 1,012𝐵1 (𝑚ê𝑠 3) 
𝐶4 + 𝐴4 = 1,005𝐴3 + 1,014𝐶2 (𝑚ê𝑠 4) 
𝐵5 + 𝐴5 = 1,005𝐴4 + 1,012𝐵3 (𝑚ê𝑠 5) 
𝐴6 = 1,005𝐴5 + 1,014𝐶4 (𝑚ê𝑠 6) 
Deve-se ainda criar as restrições que garantam que o investimento máximo em algum 
investimento é de R$ 10.000,00 
0 ≤ 𝐴1, 𝐴2, … , 𝐴6, 𝐵1, 𝐵3, 𝐵5, 𝐶2, 𝐶4, 𝐷1 ≤ 10000 
O modelo completo fica: 
𝑚𝑎𝑧 𝑧 = 1,005𝐴6 + 1,012𝐵5 + 1,06𝐷1 
s.a.: 𝐴1 + 𝐵1 + 𝐷1 = 20.000 
𝐶2 + 𝐴2 = 1,005𝐴1 (𝑚ê𝑠 2) 
𝐵3 + 𝐴3 = 1,005𝐴2 + 1,012𝐵1 (𝑚ê𝑠 3) 
𝐶4 + 𝐴4 = 1,005𝐴3 + 1,014𝐶2 (𝑚ê𝑠 4) 
𝐵5 + 𝐴5 = 1,005𝐴4 + 1,012𝐵3 (𝑚ê𝑠 5) 
𝐴6 = 1,005𝐴5 + 1,014𝐴4 (𝑚ê𝑠 6) 
0 ≤ 𝐴1, 𝐴2, … , 𝐴6, 𝐵1, 𝐵3, 𝐵5, 𝐶2, 𝐶4, 𝐷1 ≤ 10000 
Exercícios 
Exercício 1.1: Uma empresa fabrica 4 tipos de refrigerante, que utilizam na sua 
fabricação duas matérias primas em comum M1 e M2, ambas medidas em litros. Os lucros 
por litro de cada tipo de refrigerante produzido bem como os consumos em litros de M1 e 
M2 para se fabricar 1 litro de cada tipo de refrigerante encontram-se na Tabela 1.3 
Tabela 3.3: lucro e consumo de cada tipo de refrigerante 
 Tipo de refrigerante 
 1 2 3 4 
Lucro (R$) 75 200 150 100 
Consumo M1 (L) 2 6 5 2 
Consumo M2 (L) 1 2 2 1 
 
Assim, por exemplo, para a fabricação de cada 1 L do refrigerante do tipo 3, é gerado um 
lucro de R$ 150 e são consumidos 5 L de M1 e 2 L de M2. 
A empresa possui disponível 100 L da matéria prima M1 e50 L de M2. Deseja-se um 
modelo PL que decida como deve ser feita a produção destes refrigerantes de modo a 
maximizar o lucro da empresa. 
Solução comentada: Deseja-se saber o quanto de cada um dos quatro refrigerantes deve 
ser produzido. Assim, deve-se criar variáveis 𝑥1, 𝑥2, 𝑥3 e 𝑥4 indicando a quantidade em L 
que a ser produzida dos refrigerantes dos tipos 1, 2, 3 e 4 respectivamente. O modelo com 
base nestas variáveis é o que segue: 
𝑀𝑎𝑥 𝑧 = 75𝑥1 + 200𝑥2 + 150𝑥3 + 100𝑥4 
s.a.: 2𝑥1 + 6𝑥2 + 5𝑥3 + 2𝑥4 ≤ 100 
𝑥1 + 2𝑥2 + 2𝑥3 + 𝑥4 ≤ 50 
𝑥1, 𝑥2, 𝑥3, 𝑥4 ≥ 0 
A função objetivo visa maximizar o lucro total da produção dos Refrigerantes. As duas 
primeiras restrições garantem que as disponibilidades das matérias primas M1 e M2 são 
respeitadas. 
Exercício 1.2: Uma nutricionista quer montar porções de salada de frutas que contenham 
pelo menos 4000 UI de vitamina A e 60 mg de vitamina C. Para isso, ela dispõe de 
abacaxi, banana, maçã e melancia. O custo e as quantidades das vitaminas A e C 
associados a cada fruta disponível encontram-se na Tabela 1.4. 
Tabela 1.4: Custo e quantidade das vitaminas A e C disponíveis para cada fruta. 
Fruta Quantidade 
vitamina A 
(UI/kg) 
Quantidade 
vitamina C 
(mg/kg) 
Custo 
(R$/Kg) 
Abacaxi 7000 550 2,20 
Banana 3000 300 2,25 
Maçã 8000 400 3,50 
Melancia 6000 250 1,70 
Pede-se um modelo PL que indique qual a composição da salada de frutas atende as 
quantidades mínimas de vitaminas A e C e possui o menor custo possível. 
Solução comentada: Para facilitar a modelagem, Abacaxi, Banana, Maçã e Melancia são 
referidas como frutas 1, 2, 3 e 4, respectivamente. As seguintes variáveis são então 
criadas: 
𝑥𝑖 →Quantidade em Kg da fruta 𝑖 na salada de fruta; 𝑖 = 1, 2, 3, 4. 
A função objetivo visa minimizar o custo final da salada: 
𝑀𝑖𝑛 𝑧 = 2,2𝑥1 + 2,25𝑥2 + 3,5𝑥3 + 1,7𝑥4 
Deve-se criar uma restrição garantindo a quantidade mínima de Vitamina A na salada: 
7000𝑥1 + 3000𝑥2 + 8000𝑥3 + 6000𝑥4 ≥ 4000 
De maneira similar, uma restrição é criada para garantir a quantidade mínima de Vitamina 
C na salada: 
550𝑥1 + 300𝑥2 + 400𝑥3 + 250𝑥4 ≥ 60 
O modelo completo, já incluindo as restrições de não negatividade e fazendo 
simplificações nas restrições é: 
𝑀𝑖𝑛 𝑧 = 2,2𝑥1 + 2,25𝑥2 + 3,50𝑥3 + 1,70𝑥4 
s.a.: 7𝑥1 + 3𝑥2 + 8𝑥3 + 6𝑥4 ≥ 4 
55𝑥1 + 30𝑥2 + 40𝑥3 + 25𝑥4 ≥ 6 
𝑥𝑖 ≥ 0; 𝑖 ∈ {1,2,3,4} 
Exercício 1.3: Considere duas fazendas, onde deseja-se cultivar café e cana-de-açúcar. O 
total a ser cultivado em cada fazenda depende da área total disponível para cultivo e da 
quantidade de água total disponível para irrigação. A Tabela 1.5 fornece os valores 
prévios associados a cada fazenda. 
Tabela 1.5: Valores prévios associados a cada fazenda. 
Fazenda Área disponível (Acres) Quantidade total de água 
disponível (103litros) 
1 500 2.000 
2 800 2.500 
 
O consumo de Água e o Lucro associado a cada cultura é mostrado na Tabela 1.6 a seguir. 
Tabela 1.6: Consumo de água e lucro associado a cada cultura. 
Cultura Consumo de água (103litros/ acre) Lucro (𝑅$/acre) 
Café 6,0 3.000 
Cana-de-
açúcar 
4,5 2.000 
 
Para haver uma diversificação, a seguinte condição deve ser ainda satisfeita: 
● Uma única cultura pode ocupar no máximo 80% da área total cultivada de cada 
uma das fazendas. 
 
Deseja-se um modelo de PL que defina como deve ser feito o cultivo de modo a 
maximizar o lucro total obtido. 
Solução comentada: Para facilitar a modelagem, café e cana-de-açúcar é referenciado 
aqui como culturas 1 e 2, respectivamente. Com base nestes índices, as seguintes variáveis 
são criadas: 
𝑥𝑖𝑗 → Área total cultivada (em Acres) da cultura 𝑖 na fazenda 𝑗; 𝑖, 𝑗 ∈ {1,2} 
A função objetivo visa maximizar o lucro total: 
𝑀𝑎𝑥 𝑧 = 3000𝑥11 + 3000𝑥12 + 2000𝑥21 + 2000𝑥22 
Restrições devem ser criadas para garantir que o máximo a ser plantado em cada fazenda, 
somando as duas culturas, é menor ou igual a área total da mesma: 
𝑥11 + 𝑥21 ≤ 500 
𝑥12 + 𝑥22 ≤ 800 
Cada fazenda possui ainda uma disponibilidade máxima de água para consumo que deve 
ser respeitada: 
6𝑥11 + 4,5𝑥21 ≤ 2000 
6𝑥12 + 4,5𝑥22 ≤ 2500 
Deve-se garantir ainda que uma única cultura pode ocupar no máximo 80% da área total 
cultivada de cada uma das fazendas: 
 
𝑥11 ≤ 0,8(𝑥11 + 𝑥21) 
𝑥21 ≤ 0,8(𝑥11 + 𝑥21) 
𝑥12 ≤ 0,8(𝑥12 + 𝑥22) 
𝑥22 ≤ 0,8(𝑥12 + 𝑥22) 
O modelo completo, já incluindo as restrições de não negatividade e fazendo as 
distributivas é: 
𝑀𝑎𝑥 𝑧 = 3000𝑥11 + 3000𝑥12 + 2000𝑥21 + 2000𝑥22 
s.a.: 𝑥11 + 𝑥21 ≤ 500 
𝑥12 + 𝑥22 ≤ 800 
6𝑥11 + 4,5𝑥21 ≤ 2000 
6𝑥12 + 4,5𝑥22 ≤ 2500 
𝑥11 ≤ 0,8𝑥11 + 0,8𝑥21 
𝑥21 ≤ 0,8𝑥11 + 0,8𝑥21 
𝑥12 ≤ 0,8𝑥12 + 0,8𝑥22 
𝑥22 ≤ 0,8𝑥12 + 0,8𝑥22 
𝑥𝑖𝑗 ≥ 0; 𝑖, 𝑗 ∈ {1,2} 
Exercício 1.4: Considere novamente o Exemplo 1.3 (Problema do Transbordo). Neste 
exemplo, foi obtido um modelo de PL que definia como deve ser feito o transporte de um 
produto de duas fábricas (F1 e F2) para dois centros distribuição (CD1 e CD2) e o 
transporte do produto que chegam nos CDs até três clientes (C1, C2 e C3). Considere agora 
que o produto para chegar até o cliente não necessariamente precisa passar por algum CD, 
ou seja, o produto pode ser transportado diretamente da fábrica para o cliente, caso seja 
mais barato. A Tabela 1.7 a seguir fornece os custos por Kg transportado diretamente de 
cada fábrica para cada cliente. 
Tabela 1.7: Custos por quilograma transportado de cada fábrica para cada cliente. 
 C1 C2 C3 
F1 10 12 10 
F2 8 10 11 
 
 A demanda de cada cliente, a capacidade de fornecimento de cada fábrica e os custos de 
transporte tanto entre Fábricas e CDs quanto entre CDs e clientes são os mesmos 
fornecidos nos Exemplo 1.3 e 1.4. Pede-se um modelo PL que defina como deve ser feito 
o transporte minimizando o custo total de transporte e garantindo que as capacidades de 
fornecimento vão ser respeitadas e que a demanda é completamente atendida. 
Solução comentada: Neste exercício, deve-se decidir o quanto deve ser transportado: 
• De cada fábrica para cada CD. 
• De cada CD para cada Cliente. 
• De cada Fábrica diretamente para cada cliente. 
Assim, pode-se criar três tipos de variáveis, uma associada a cada decisão prévia: 
𝑥𝑖𝑗 → Quantidade enviada (em Kg) da fábrica 𝑖 para o CD 𝑗; 𝑖 = 1,2 e 𝑗 = 1,2 
𝑦𝑗𝑘 → Quantidade enviada (em Kg) do CD 𝑗 para o cliente 𝑘; 𝑗 = 1,2 e 𝑘 = 1,2,3 
𝑧𝑖𝑘 → Quantidade enviada (em Kg) da fábrica 𝑖 diretamente para o cliente 𝑘; 𝑖 = 1,2 e 
𝑘 = 1,2,3. 
A função objetivo visa minimizar o custo total de transporte: 
𝑚𝑖𝑛 𝑧 = 7𝑥11 + 9𝑥12 + 6𝑥21 + 8𝑥22 + 5𝑦11 + 6𝑦12 + 4𝑦13 + 3𝑦21 + 7𝑦22 + 6𝑦23
+ 10𝑧11 + 12𝑧12 + 10𝑧13 + 8𝑧21 + 10𝑧22 + 12𝑧23 
Devem haver restrições garantindo que as quantidades requisitadas por cada cliente 
devem ser atendidas: 
𝑦11 + 𝑦21 + 𝑧11 + 𝑧21 = 40 
𝑦12 + 𝑦22 + 𝑧12 + 𝑧22 = 60 
𝑦13 + 𝑦23 + 𝑧13 + 𝑧23 = 100 
Existem ainda restrições que garantam que a capacidade de cada fábrica deve ser 
respeitada: 
𝑥11 + 𝑥12 + 𝑧11 + 𝑧12 + 𝑧13 ≤ 120 
𝑥21 + 𝑥22 + 𝑧21 + 𝑧22 + 𝑧23 ≤ 80 
Finalmente, deve-se garantir que a quantidade total que chega em um determinado CD 
deve ser transportada para algum cliente: 
𝑥11 + 𝑥21 = 𝑦11 + 𝑦12 + 𝑦13 
𝑥12 + 𝑥22 = 𝑦21 + 𝑦22 + 𝑦23 
O modelo completo, incluindo as restrições de não negatividade é: 
𝑚𝑖𝑛 𝑧 = 7𝑥11 + 9𝑥12 + 6𝑥21 + 8𝑥22 + 5𝑦11 + 6𝑦12 + 4𝑦13 + 3𝑦21 + 7𝑦22 +
6𝑦23 + 10𝑧11 + 12𝑧12 + 10𝑧13 + 8𝑧21 + 10𝑧22 + 12𝑧23 
s.a.: 𝑦11 + 𝑦21 + 𝑧11 + 𝑧21 = 40; 
𝑦12 + 𝑦22 + 𝑧12 + 𝑧22 = 60; 
𝑦13 + 𝑦23 + 𝑧13 + 𝑧23 = 100; 
𝑥11 + 𝑥12 + 𝑧11 + 𝑧12 + 𝑧13 ≤ 120; 
𝑥21 + 𝑥22 + 𝑧21 + 𝑧22 + 𝑧23 ≤ 80; 
𝑥11 + 𝑥21 = 𝑦11 + 𝑦12 + 𝑦13; 
𝑥12 + 𝑥22 = 𝑦21 + 𝑦22 + 𝑦23; 
𝑥𝑖𝑗 ≥ 0; 𝑖 = 1,2; 𝑗 = 1,2; 
𝑦𝑗𝑘 ≥ 0; 𝑗 = 1,2; 𝑘 = 1,2,3; 
𝑧𝑖𝑘 ≥ 0; 𝑖 = 1,2; 𝑘 = 1,2,3 
 
3. ConclusãoNesta aula, a definição do que é um modelo PL foi apresentada e foi visto que este tipo 
de modelagem pode ser usado para diversos problemas de diversas áreas da Engenharia 
de Produção, como por exemplo planejamento da produção, logística e finanças. Para 
assimilação e consolidação deste conteúdo, diversos exemplos e exercícios foram 
propostos e discutidos detalhadamente. 
Resumo 
Foi visto nesta aula que um modelo é dito de Pesquisa Operacional (PO) quando faz uso 
métodos analíticos (modelos matemáticos, estatísticos ou computacionais) para auxílio 
na tomada de decisão. Um modelo de PO é dividido nas seguintes componentes: 
• Parâmetros de entrada: constantes com valores já pré-determinados antes da 
modelagem do problema. 
• Variáveis de decisão: incógnitas matemáticas cujos valores serão conhecidos 
após a execução do modelo. 
• Restrições: equações ou inequações matemáticas escritas em função das variáveis 
de decisão. Servem para definir quais são os possíveis valores que as variáveis 
podem assumir. 
• Função objetivo: Função matemática das variáveis de decisão que deve ser 
otimizada (maximizada ou minimizada). 
Um modelo é dito de Programação Linear (PL) quando tanto a função objetivo e 
restrições são lineares. Neste caso o problema associado é classificado como Problema 
de Programação Linear (PPL). Este curso é restrito a estudo de PPLs. Um modelo PL 
segue abaixo: 
𝑀𝑎𝑥 𝑧 = 160𝑥1 + 100𝑥2 
s.a. 3𝑥1 + 2𝑥2 ≤ 90 
𝑥1 ≤ 25 
𝑥1 ≥ 0 
𝑥2 ≥ 0 
O modelo prévio possui duas variáveis de decisão (𝑥1 e 𝑥2). As constantes que aparecem 
em todas as componentes do modelo formam os parâmetros de entrada do mesmo. O 
modelo possui ainda uma função objetivo de maximização e quatro restrições. As duas 
últimas são chamadas de restrições de não negatividade pois servem para dizer que as 
variáveis não podem assumir valores negativos. 
O entendimento do que é um modelo PL é importante, porém o mais importante desta 
aula é que o aluno desenvolva a capacidade de realizar suas próprias modelagens, o que 
requer muito treinamento. 
Informações sobre a próxima aula 
Na próxima aula, será visto o primeiro método de resolução de PPLs, conhecido como 
Método Gráfico. Tal método consiste em desenhar o espaço de soluções do problema e 
identificar a melhor solução para o mesmo através de um conjunto de passos bem 
definidos. O método gráfico é aplicado apenas a PPLs com duas variáveis. Apesar desta 
limitação, o conceito por trás deste método serve de embasamento para obtenção de um 
algoritmo de resolução de modelos com mais variáveis. 
Referências 
Taha, H. A. (2008). Pesquisa operacional. Pearson Educación. 
Belfiore, P., & Fávero, L. P. (2013). Pesquisa Operacional para cursos de 
Engenharia (Vol. 1). Elsevier Brasil.