Pesquisa Operacional com GAMS

Prévia do material em texto

PESQUISA OPERACIONAL
DESENVOLVIMENTO E OTIMIZAÇÃO DE 
MODELOS MATEMÁTICOS POR MEIO DA 
LINGUAGEM GAMS
UNESP
Aneirson Francisco da Silva- Doutorando-UNESP
Fernando Augusto Silva Marins, Dr- UNESP
Guilherme Martin Silva
Paulo Roberto Marcondes de Andrade Lopes 
O objetivo desta apostila é fornecer conceitos matemáticos sobre a estrutura da 
linguagem de modelagem General Algebraic Modeling System – GAMS. Após a 
leitura desta apostila o leitor estará apto a desenvolver e otimizar modelos lineares 
e combinatórios utilizando a linguagem e o software GAMS.
A estrutura da apostila está definida primeiramente pela revisão da história da 
pesquisa operacional, e em seguida a explicação a respeito dos modelos lineares, 
iniciando pelas particularidades desse modelo, teoria de redes DEA. Também são
abordados modelos de otimização combinatória e problemas NP-HARD.
Capítulo 1
1. A EVOLUÇÃO DA PESQUISA OPERACIONAL
O termo Pesquisa Operacional “PO” foi empregado pela primeira vez em 1939. A partir de 
individualizada e batizada, tornou-se possível fixar suas origens em épocas remotas da história 
da ciência e da sociedade.
1.1. O MÉTODO DA PESQUISA OPERACIONAL
A experimentação tomada no sentido restrito - isto é, a manipulação física das variáveis - é 
geralmente impossível ou impraticável quando se lida com organizações governamentais, 
militares ou industriais. Apesar disso, a experimentação é às vezes possível, particularmente no 
caso de subsistemas, e desempenha papel importante na PO. Na maioria das vezes, entretanto, o 
sistema global em estudo não pode ser submetido a um tratamento desta natureza. Quem 
trabalha em pesquisa operacional é geralmente obrigado a construir representações do sistema e 
do seu comportamento para se orientar durante a pesquisa. Os modelos em PO assumem a forma 
de uma ou mais equações ou inequações para traduzir a condição de que algumas, ou todas as 
variações controladas só podem ser manipuladas dentro de limites. O conjunto destas equações 
constitui, ao mesmo tempo, um modelo de sistema e um modelo de decisão.
A solução pode ser extraída do modelo mediante experimentação (isto é, por simulação) ou 
mediante análise matemática. Para alguns tipos de função f (por exemplo, relações algébricas 
elementares), desde que as restrições não sejam numerosas, a matemática clássica fornece 
instrumentos perfeitamente adequados para a determinação dos melhores valores das variáveis 
controladas. Por outro lado, a função f pode consistir em um conjunto de regras de cálculo (um 
algoritmo) que nos permita medir a utilidade (U) do desempenho para qualquer conjunto de 
valores das variáveis controladas e não controladas.
Em alguns casos o comportamento do elemento humano que toma a decisão não pode ser 
representado no modelo. Ocorre a necessidade do uso de simulações que envolverão a 
participação de seres humanos, sendo denominados jogos de operações. 
Introdução________________________________________________________________________ 4
A otimização, portanto, produz a melhor solução para o problema que foi modelado.
A correspondência entre modelo e realidade terá de ser aferida (testada) e a solução avaliada. 
Isto é, teremos de comparar seu desempenho com o da política ou procedimento que ela irá 
substituir. Os resultados da pesquisa devem ser implantados. É nesta fase que se faz o teste e a 
avaliação final da pesquisa; proporcionando, pois, ao especialista as maiores e melhores 
oportunidades de aprender.
Cinco fases num projeto de PO:
1. Formulação do problema
2. Construção do modelo
3. Obtenção da solução
4. Teste do modelo e avaliação da solução
5. Implantação e acompanhamento da solução (manutenção)
As vantagens e desvantagens da utilização de modelos foram assim definidas:
Vantagens
a) Emerge sob a forma gráfica, para representar a realidade aprendida em 
determinado momento; 
b) Simplifica a visualização da amplitude das variáveis sem alterar a essência; 
c) Ajuda a identificar várias relações possíveis entre os elementos da realidade; 
d) Possibilita compreender relações complexas; 
e) Serve como base para estabelecer e aprimorar parâmetros. 
Desvantagens
f) Limitações na identificação de todas as variáveis relevantes que influenciam em 
determinada situação; 
g) Problemas na definição das propriedades a serem mensuradas e na especificação 
de procedimentos para tal; 
h) Dificuldades no entendimento entre os provedores e os usuários da informação. 
Introdução________________________________________________________________________ 5
A representação simplificada de um problema prático por meio de um modelo matemático 
permite que sobre ele se aplique técnicas e métodos que facilitam a obtenção de uma solução.
1.2. O IMPACTO DA PESQUISA OPERACIONAL
A Pesquisa Operacional tem tido um grande impacto crescente na administração de empresas 
nos anos recentes. Tanto o número quanto a variedade de suas aplicações continuam a crescer 
rapidamente. Algumas de suas técnicas envolvem idéias sofisticadas em ciências políticas, 
matemática, economia, teoria da probabilidade e estatística. Como também sendo usada 
amplamente em outros tipos de organizações, inclusive negócios e indústria. 
Muitas indústrias, inclusive a de aviação e mísseis, automóveis, comunicações, computadores, 
energia elétrica, eletrônica, alimentos, metalúrgica, mineração, papel, petróleo e transporte, têm 
feito uso extensivo da pesquisa operacional. Mesmo instituições financeiras, agências 
governamentais e hospitais têm aumentado rapidamente o uso que fazem da pesquisa 
operacional.
Vejamos alguns dos problemas que têm sido resolvidos por técnicas particulares de pesquisa 
operacional:
 PROGRAMAÇÃO LINEAR: tem sido usada com sucesso na solução de problemas relativos à 
alocação de pessoal, mistura de materiais, distribuição, transporte, carteira de 
investimento, avaliação da eficiência;
 PROGRAMAÇÃO DINÂMICA: tem sido aplicada também com sucesso a áreas como 
planejamento de despesas de publicidade, distribuição do esforço de vendas e 
programação de produção;
 TEORIA DAS FILAS: tem tido aplicação na solução de problemas relativos a 
congestionamento de tráfego, máquinas de serviços sujeitas à quebra, determinação do 
nível de uma força de serviço, programação do tráfego aéreo, projetos de represas, 
programação de produção e operação de hospitais;
 PROGRAMAÇÃO INTEIRA: que é uma forma de programação linear onde as variáveis 
podem apenas apresentar números inteiros. Tem sido utilizada na resolução de 
problemas de investimento dentre outros;
Introdução________________________________________________________________________ 6
 PROGRAMAÇÃO MISTA: que é uma forma de programação linear onde as variáveis podem 
assumir valores binários, inteiros e contínuos, este modelo também é definido como 
otimização combinatória, enquadrando-se em problemas de dificuldades não polinomiais 
NP-HARD;
 PROGRAMAÇÃO NÃO LINEAR: modelo matemático onde a função objetivo, as restrições 
ou ambas, apresentam não linearidade em seus coeficientes.
 PROGRAMAÇÃO MULTIOBJETIVO: é uma forma de programação linear e não linear onde 
se analisa múltiplas funções objetivos;
 GOAL PROGRAMMING: que é uma extensão dos modelos de programação multiobjetivo, 
contendo vários modelos específicos para cada problema de decisão;
Outras técnicas de pesquisa operacional, tais como teoria de estoque, teoria dos jogos, 
teoria dos grafos e simulação, também tem sido aplicadas com sucesso a(em) diversos contextos.
 Capítulo 2
2. ESTRUTURAÇÃO E OTIMIZAÇÃO DE MODELOS LINEARES ESTACIONÁRIOS 
O anexo A contempla a linguagem de modelagem GAMS. Abordando as principais funções e aestrutura dessa linguagem de modelagem, mostrando suas principais vantagens. O anexo B 
contempla as principais linguagens de modelagens, abordando as principais vantagens da 
linguagem GAMS em relação às demais linguagens. 
Vamos iniciar a modelagem do problema do Giapetto pela linguagem GAMS. A linguagem GAMS 
requer que o problema seja traduzido na forma algorítmica.
1- Giapetto fabrica dois tipos de brinquedos de madeira. Soldados e trens. Um soldado é 
vendido por R$ 27,00 e usa R$ 10,00 de matéria prima. Cada soldado que é fabricado 
tem um custo adicional de R$ 14,00 relativo à mão de obra. Um trem é vendido por R$ 
21,00 e gasta R$ 90,00. O custo de mão de obra adicional para cada trem é de R$ 
10,00. A fabricação destes brinquedos requer dois tipos de mão de obra: Carpintaria e 
Acabamento. Um soldado necessita de 2 horas para acabamento e 1 para carpintaria. 
Um trem necessita de 1 hora para acabamento e 1 hora de carpintaria. Cada semana, 
Giapetto pode obter qualquer quantidade de matéria prima, mas tem a disposição até 
100 horas de acabamento e 80 de carpintaria. A demanda por trens é ilimitada, mas a 
venda de soldados é de no máximo 40 por semana. Giapetto quer maximizar seu lucro 
diário. Formular o modelo matemático que poderia ser usado por Giapetto para 
maximizar seu lucro semanal.
1 passo: Modelar o problema. Vamos descrever as variáveis do problema, o que na linguagem 
GAMS é chamada de (SETS ) numa tradução pode-se chamar de índices ou conjuntos.
Índices:
Xi,j: Quantidade a ser produzida do produto i utilizando os recursos j. O GAMS é um software 
orientado ao objeto, logo temos que declarar esses objetos que no caso são os i produtos e os j 
recursos.
Estruturação e otimização de modelos lineares estacionários________________________________ 8
2 passo: Definir os parâmetros (PARAMETER) do modelo: Neste caso sabemos a margem de 
contribuição unitária por produto i. Portanto, é necessário esse parâmetro que estará ligado ao 
índice i. Vamos chamar este parâmetro de MCi. Outro parâmetro é com relação à disponibilidade 
dos recursos, sendo este parâmetro ligado ao índice j. Vamos chamar este parâmetro de Aj. 
Finalmente, devemos criar um parâmetro que mostre o consumo unitário de cada recurso por 
produto, sendo este parâmetro pertencente aos índices i e j. Neste caso na linguagem GAMS deve 
ser criado uma Tabela (TABLE), que vamos chamar de R i, j.
3 passo: Definir as variáveis de decisão: Temos uma decisão que é saber o valor da margem de 
contribuição, vamos definir essa variável de Xi. Na linguagem GAMS é necessário informar uma 
variável que vai definir a função objetivo, neste caso chamaremos de Z, que vai definir os valores 
ótimos de produção de cada produto.
4 passo: Definir as equações (EQUATIONS): as equações são definidas por meio do número de 
restrições mais a função objetivo. A primeira equação vai definir o valor da margem de 
contribuição, portanto chamaremos a mesma de margem. A segunda equação vai determinar o 
quanto será consumido por recurso j vamos chamar essa equação de consumo. E a última 
equação definirá o limite máximo de demanda do produto soldado. Agora podemos resolver o 
problema do Amigo Giapetto.
0
40
.
:asujeito
. Z
,
""
,
2






JI
SOLDADO
n
i
jiji
i
ii
X
X
AXR
XMCMax
A Tabela 2.1 mostra alguns comandos básicos da linguagem GAMS
Tabela 2.1- Comandos básicos em linguagem GAMS
Estruturação e otimização de modelos lineares estacionários________________________________ 9
Símbolo Significado
G Define uma inequação de sinal maior ou igual
L Define uma inequação de sinal de menor ou igual
E Define uma equação (X= n)
“ São fixadores de índices 
‘ Também é um fixador de índices 
PROD Expressão para produto de uma série
SUM Expressão para somatório
Model Descreve o modelo estudado
Solve Descreve a utilização de um solver específico
Display Recurso utilizado para calcular o primal e o dual 
A Tabela 2.2 mostra as funções padrão de GAMS.
Tabela 2.2- Funções padrão em GAMS
Nome Descrição Definição Número de Argumentos
ABS Valor absoluto |ARG| 1
ARCTAN Arco Tangente Arctan (arg); resultado em 
radianos
1
CEIL Função teto Maior inteiro ≥ arg 1
COS Cosseno Cos (arg) argumento em 
radianos
1
ERRORF Função erro Integral de distribuição normal 
padrão 
1
EXP Exponencial earg 1
FLOOR Função piso Maior inteiro ≤ arg 1
Estruturação e otimização de modelos lineares estacionários________________________________ 10
Nome Descrição Definição Número de Argumentos
LOG Logaritmo 
natural
Log do arg na base e 1
Log10 Logaritmo 
comum
Log de arg na base 10 1
MAPVAL Função 
mapeamento
Atribuiu números a valores 
especiais 
1
MAX Maior valor Max (arg1, arg2,...,argn) >1
MIN Menor valor Min (arg1, arg2,..,argn) >1
MOD Resto arg1-trunc(arg1/arg2) x arg3 2
Normal Randômica 
normal
Número aleatório distribuído 
normalmente com argumento 
arg1 e desvio padrão arg2
2*
POWER Potência inteira
ROUND Arredondamento 
SIGN Sinal 
SIN Seno Sem (arg); arg em radianos
SQR Quadrado arg x arg 1
SQRT Raiz quadrada 1
TRUNC Truncamento Sign (arg) x floor (abs(arg)) 1
UNIFORM Randômica 
uniforme
Número aleatório distribuído 
uniformemente entre arg1 e arg2
2*
A Figura 1.1 mostra os processos para obtenção do modelo do Giapetto em linguagem GAMS. 
Clicando em F9 é obtido a solução para este modelo. A solução ótima para este modelo seria. 
Produzir 20 soldados e 60 trens gerando um lucro máximo de R$ 180,00 reais. O GAMS oferece 
algumas estatísticas referentes ao tamanho do modelo, como se pode ver abaixo no caso do 
Estruturação e otimização de modelos lineares estacionários________________________________ 11
modelo Giapetto. As contagens de “BLOCKS” se refere ao número de equações genéricas e 
variáveis. As contagens de “SINGLE” se refere as linhas e colunas individuais que estão sendo 
geradas na instancia particular do modelo. Para os modelos não lineares, são fornecidas outras 
estatísticas para descrever o grau de não linearidade do problema (BROOKE et al., 1997).
Estruturação e otimização de modelos lineares estacionários________________________________ 12
Figura 1.1- Modelo Giapetto em linguagem GAMS.
2- O Senhor Martins é dono de uma oficina muito movimentada na cidade de 
Guaratinguetá- SP. Ele querendo maximizar seus retornos e também, visando à 
realização de novos investimentos na sua oficina. Resolveu procurar você/SA, para 
fazer um planejamento da sua produção, visando à maximização do lucro, e 
identificar possíveis áreas para realização de novos investimentos. Os dados da 
empresa estão logo abaixo:
Tipo de Máquina Produto 
1
Produto 2 Produto 3 Tempo 
disponível
Torno 5 3 5 400
Fresa 8 4 0 500
Furadeira 2 5 3 300
Lucro 20 15 18
Demanda Semanal 
máxima
40 50 20
 Uma oficina mecânica deseja alocar o tempo ocioso disponível em suas máquinas para a 
produção de três produtos. A Tabela abaixo mostra as informações sobre as necessidades de 
horas de máquina para produzir uma unidade de cada produto, assim como a 
disponibilidade das máquinas, o lucro dos produtos e a demanda máxima existente no 
mercado. Deseja-se o esquema semanal de produção de lucro máximo.
Resolvendo o exemplo do senhor Martins.
1 passo: Descrever os índices.
i, j Os objetos são os i produtos e j recursos
2 passo: Descrever os parâmetros.
Estruturação e otimização de modelos lineares estacionários________________________________ 13
Ri, j: Consumo unitários por produto i de cada recurso j.
Aj: Quantidade disponível do recurso j.
Di: Demanda máxima por produto i.
Li:Lucro unitário por produto i.
3 passo: Descrever as variáveis de decisão.
Xi: Define a produção do produto i.
Z: Expressão da função objetivo.
4 passo: Descrever as equações.
Margem: Define o lucro máximo
Consumoj: Define o consumo por produto i do recurso j.
Dprodutosi: Define a demanda máxima por produto i.
5 passo: Construção do modelo matemático.
0X
DXDprodutos
A.XRconsumo
:asujeito
.XLMax Z
JI,
iii
n
i
jiji,j
n
i
ii






Estruturação e otimização de modelos lineares estacionários________________________________ 14
Estruturação e otimização de modelos lineares estacionários________________________________ 15
Figura 1.2: Modelo matemático exemplo 2 em linguagem GAMS.
Solução ótima: Produzir 40 unidades do produto 1, 32 unidades do produto 2 e 20 unidades do 
produto 3. Gerando um lucro máximo de R$ 1.640,00. 
Solução Dual: Produto 1 R$ 14,00, produto 3 R$ 9,00 e Furadeira R$ 3,00. Interpretação 
econômica do dual. Se a oficina aumentasse a demanda do produto 1 em uma unidade o lucro 
aumentaria em R$ 14,00. Se a usina aumentasse a demanda em uma unidade do produto 2, o 
lucro aumentaria em R$ 9,00. Se o tempo disponível de utilização da furadeira fosse aumentada 
em uma hora o lucro aumentaria em R$ 3,00.
Desenvolva e otimize os modelos dos problemas descritos a seguir utilizando-se do
software GAMS.
1 – Uma indústria fabrica dois tipos de papel e para isso utiliza somente uma máquina. Devido a 
certas restrições de matéria prima, não se pode diariamente produzir mais do que 4 tons de 
papel do tipo A, nem mais do que 6 tons do tipo B. Requer-se 1 hora da máquina para produzir 1 
ton. de papel do tipo A e 1 hora para produzir 1 ton. de papel do tipo B. O lucro por ton. 
produzida é de R$ 2,00 para o papel do tipo A e de R$ 5,00 para o papel do tipo B. O tempo de 
utilização da máquina é de 8 horas/dia. Elaborar o plano ótimo de produção.
2 – Uma pequena indústria usa três tipos de matérias primas, P, Q, R para a fabricação de dois 
produtos A e B. As matérias primas em disponibilidade na fábrica são:
 20 unidades de P;
 12 unidades de Q; e
 16 unidades de R.
Por razões tecnológicas, uma unidade do produto A necessita respectivamente de 2, 2 e 4 
unidades de matérias primas P, Q e R. Para o produto B esses coeficientes técnicos são 4, 2 e 0, 
respectivamente. O fabricante sabe que o lucro na produção de A é de 0,5 unidades monetárias e 
de B é de 1 unidade monetária. Qual o lucro máximo e quais as quantidades produzidas das 
mercadorias A e B para se obter o lucro máximo?
Estruturação e otimização de modelos lineares estacionários________________________________ 16
3 – Uma companhia de investimento dispõe de R$ 100.000,00 para investir em ações e letras 
imobiliárias.
Sua política de aplicação consiste em:
 Empregar, no máximo, 50% do disponível em ações; e
 Empregar, no máximo, 60% do disponível em letras imobiliárias.
Através de uma pesquisa de mercado, a companhia verificou que deveria empregar, no máximo, 
40% do disponível, na diferença entre o dobro da quantidade investida em ações e a quantidade 
investida em letras; e empregar, no máximo, 1% do disponível na soma da oitava parte investida 
em ações com a quinta parte investida em letras.
As ações produzem uma rentabilidade de 5% ao mês e as letras 4% ao mês. Qual o investimento 
ótimo?
4 – Uma fábrica de canetas quer saber do Departamento de Engenharia quantas canetas de cada 
tipo (standard, luxo e esferográfica) deverão ser produzidas, para que o lucro da empresa seja 
máximo.
INFORMAÇÕES:
a) Do departamento de Produção
Produções máximas mensais possíveis para cada um dos tipos de canetas (isto é, 
produzir-se só um tipo):
 Standard 15.000
 Luxo 10.000
 Esferográfica 20.000
b) Do Departamento de Vendas 
Máximo de vendas mensais para cada um dos tipos:
 Standard 12.000
 Luxo 8.000 
 Esferográfica 30.000
c) Do Departamento de Contabilidade
Lucro unitário para cada tipo: 
Estruturação e otimização de modelos lineares estacionários________________________________ 17
 Standard R$ 0,70
 Luxo R$ 0,50
 Esferográfica R$ 0,30
5 – Uma fábrica de automóveis e caminhões possui os seguintes departamentos;
1. Estamparia de pranchas metálicas;
2. Montagem de motores;
3. Montagem de automóveis; e
4. Montagem de caminhões.
O departamento 1 deve estampar, no mínimo por mês, as pranchas necessárias para 25.000 
automóveis ou 35.000 caminhões, ou as correspondentes combinações de automóveis e 
caminhões.
O departamento 2 deve no mínimo por mês, montar 33.333 motores de automóveis e 16.667 
motores de caminhões ou as correspondentes combinações de motores de automóvel e 
caminhão.
O departamento 3 pode montar e terminar 40.000 automóveis e o departamento 4, mensalmente 
25.000 caminhões (ambos utilizando sua capacidade máxima).
Com o constante aumento do combustível, a fábrica sabe que o prejuízo na fabricação de um 
automóvel é de R$ 500,00 e na fabricação de um caminhão é de R$ 200,00. Qual a quantidade de 
automóveis e caminhões a ser produzida a fim de que a fábrica tenha o menor prejuízo possível, 
dadas as condições atuais do mercado?
6 – Uma indústria de aparelhos eletrodomésticos tem equipamento para produzir geladeiras, 
máquinas de lavar e fogões.
O regime de operação da indústria é de 45 horas semanais. Seu equipamento pode fabricar, por 
hora, 50 geladeiras ou 25 máquinas de lavar ou 75 fogões.
Uma pesquisa de mercado revelou que a demanda semanal é de 1.000 geladeiras, 500 máquinas 
de lavar e 1.500 fogões.
Estruturação e otimização de modelos lineares estacionários________________________________ 18
A geladeira proporciona, por cada unidade vendida, um lucro de R$ 40,00; a máquina de lavar R$ 
120,00 e o fogão um lucro de R$ 30,00.
Qual seria o modelo matemático da indústria que permitiria o lucro máximo semanal ? 
7 – Um sapateiro faz 6 sapatos por hora, se fizer somente sapatos, e 5 cintos por hora, se fizer 
somente cintos. Ele gasta 2 unidades de couro para fabricar uma unidade de sapato e uma 
unidade de couro para fabricar uma unidade de cinto. Sabendo-se que o total disponível de couro 
é de 6 unidades e que o lucro unitário por sapato é de 5 unidades monetárias e o do cinto é de 2 
unidades monetárias, pede-se: o modelo do sistema de produção do sapateiro, se o objetivo é 
maximizar seu lucro por hora. 
8 – Um vendedor de frutas pode transportar 800 caixas de frutas para sua região de vendas. Ele 
necessita transportar 200 caixas com laranjas, tendo um lucro de 20 u.m. por caixa, pelo menos 
100 caixas com pêssegos a 10 u.m. de lucro por caixa e no máximo 200 caixas com tangerinas a 
30 u.m de lucro por caixa. Construir o modelo matemático que permita ao vendedor carregar o 
caminhão de modo a obter o lucro máximo. 
9 – Uma rede de televisão local tem o seguinte problema: foi descoberto que o programa “A” com 
20 minutos de música e 1 minuto de propaganda chama a atenção de 30.000 telespectadores, 
enquanto o programa “B” com 10 minutos de música e 1 minuto de propaganda chama a atenção 
de 10.000 telespectadores. NO decorrer deuma semana, o patrocinador insiste no uso de no 
mínimo, 5 minutos para sua propaganda e que não há verba para mais de 80 minutos de música. 
Quantas vezes por semana cada programa devem ser levadas ao ar para obter o número máximo 
de telespectadores? Construa o modelo do sistema. 
10 – Um fazendeiro está estudando a divisão de sua propriedade nas seguintes atividades 
produtivas.
Estruturação e otimização de modelos lineares estacionários________________________________ 19
A (Arrendamento) – Destinar certa quantidade de alqueires para a plantação de cana de açúcar, a 
uma usina local, que se encarrega da atividade e paga pelo aluguel da terra $ 300,00 por alqueire 
por ano.
P (Pecuária) – Usar outra parte para criação de gado de corte. A recuperação das pastagens 
requer adubação (100 kg / Alq) e irrigação (100.000 l de água / Alq) por ano. O lucro estimado 
nessa atividade é de $ 400,00 / Alq no ano.
S (Plantio de Soja) – Usar uma terceira parte para o plantio de soja. Essa cultura requer 200 kg 
por alqueire de adubos e 200.000 l de água / Alq para irrigação por ano. O lucro estimado nessa 
atividade é de $ 500,00 por alqueire no ano.
Disponibilidade de recursos por ano: 
12.750.000 l de água;
14.000 kg de adubo; e
100 alqueires de terra. 
Quanto alqueire deverá destinar a cada atividade para proporcionar o melhor retorno?
 Capítulo 3
3. DESENVOLVIMENTO E OTIMIZAÇÃO DE MODELOS LINEARES PRÁTICOS POR MEIO DO GAMS
É comum durante o desenvolvimento de modelos matemáticos nos depararmos com problemas onde há 
limites de demanda para determinados produtos. Como exemplo, iremos modelar um problema em 
linguagem GAMS. Os dados estão dispostos abaixo. O Quadro 3.1 refere-se aos recursos disponíveis na 
fazenda para realização das atividades leiteiras e de corte.
Quadro 3.1- Recursos disponíveis
Abreviatura RESTRIÇÕES
AT Área total disponível para a atividade leiteira – ha/ano
TR Custo da terra (devendo ser considerado o custo de oportunidade e o custo de manutenção –
adubação, reforma de pasto, limpeza e destoca) – R$/ano
BE Custo e despesas com benfeitorias (considerando-se a depreciação, o custo de oportunidade e
o custo de manutenção) – R$/ano
MI Custo e despesas com máquinas e implementos (considerando-se a depreciação, o custo de
oportunidade e o custo de manutenção) – R$/ano
EQ Custo e despesas com equipamentos (considerando-se a depreciação, o custo de
oportunidade e o custo de manutenção) – R$/ano
RE Custo e despesas com reprodutores (considerando-se a depreciação e o custo de
oportunidade) – R$/ano
AL Custo e despesas com alimentação (considerando-se o gasto com concentrados, suplementos
e forrageiras e o custo alternativo) – R$/ano
PV Custo e despesas com produtos veterinários (considerando-se o gasto e o custo alternativo) –
R$/ano
IA Custo e despesas com inseminação artificial (considerando-se o gasto e o custo alternativo) –
R$/ano
TE Custo e despesas com transferência de embriões (considerando-se o gasto e o custo
alternativo) – R$/ano
DA Gastos com despesas administrativas (considerando-se também o custo alternativo) – R$/ano
MK Gastos com marketing e propaganda (considerando-se também o custo alternativo) – R$/ano
MO Custo e despesas com mão-de-obra (considerando-se o gasto efetivo, os encargos pagos e o
custo alternativo) – R$/ano
A Tabela 3.1 mostra os recursos disponíveis e o consumo por categoria de animal para o ano de 2004.
Desenvolvimento e Otimização de Modelos Lineares Práticos Por Meio do GAMS______________ 21
Tabela 3.1- Consumo anual por animal.
Restrições
RECURSOS 
DISPONÍVEIS Unidades
RECURSOS CONSUMIDOS POR
CATEGORIA
Bezerras Bezerros Novilhas Vacas Touro
AT 196,50 ha/ano 0,09 0,09 0,25 0,35 0,42
TR 39.493,39 R$/ano 43,37 32,81 66,12 88,78 1535,85
BE 9.894,38 R$/ano 4,07 3,08 3,16 68,26 10,99
MI 51.601,87 R$/ano 70,83 53,59 45,25 276,01 57,34
EQ 13.605,94 R$/ano 3,73 2,83 2,17 99,14 15,12
RE 2.432,04 R$/ano 10,35 7,83 6,59 0,94 0,00
AL 235.063,69 R$/ano 161,32 122,07 393,56 1239,10 261,18
PV 19.243,82 R$/ano 42,26 31,98 27,62 73,10 21,38
IA 3.923,65 R$/ano 16,69 12,63 10,64 1,52 0,00
TE 7.240,00 R$/ano 30,81 23,31 19,63 2,81 0,00
DA 35.535,30 R$/ano 34,14 25,83 19,83 214,86 78,97
MK 18.089,05 R$/ano 69,52 52,60 51,92 5,61 80,40
MO 51.729,07 R$/ano 42,60 32,23 28,87 316,79 114,95
RO Orçamento disponível: R$ 487.852,20
Essa Tabela foi obtida por meio de rateio, considerando o consumo efetivo de recursos e o tempo de 
permanência de cada categoria animal na propriedade. Para garantir a sustentabilidade econômica da
produção de leite e da produção animais da Fazenda , foram inseridas restrições adicionais as 
quantidades máximas e mínimas que cada categoria animal deveria possuir, conforme apresentado na
Tabela 3,2. Esses valores são baseados na taxa de lotação histórica da fazenda no ano de 2003.
Tabela 3.2- Categorias de animais
Categoria Qtde Máxima Qtde Mínima
X1 95 39
X2 135 53
X3 170 60
X4 200 100
X5 12 -
O orçamento disponível é de R$ 487.852,20. O objetivo é maximizar a quantidade de animais. Formule o 
modelo utilizando-se da linguagem GAMS.
Desenvolvimento e Otimização de Modelos Lineares Práticos Por Meio do GAMS______________ 22
Índices:
i associado às categorias de animais (Bezerras, Bezerros, Novilhas, Vacas e Touros).
j associado às categorias dos recursos (AT, TR, BE, MI, EQ, RE, AL, PV, IA, TE, DA, MK, MO,RO).
Parâmetros:
Pj: associado ao índice j define os limites máximos de cada recurso.
Ri, j: associado ao consumo unitário do recurso j por categoria de animal i.
Variáveis:
Xi: Quantidade por categoria de animal.
Z: Associada ao cálculo da função objetivo.
Equações:
Animais define a função objetivo
AJ: Calcula o quanto a ser utilizado do recurso j por categoria de animal i.
maxbezerrai: máximo de bezerras.
minbezerrai: mínimo de bezerras.
maxbezerrosi: máximo de bezerros.
minbezerrosi: mínimo de bezerros.
maxnovilhasi: máximo de novilhas.
minnovilhasi: mínimo de novilhas.
maxvacasi: máximo de vacas
minvacasi: mínimo de vacas.
mintouroi: mínimo de touro.
maxtouroi: máximo de touro.
Vamos introduzir outro comando na linguagem GAMS denominado SCALAR neste caso esse comando vai 
representar uma constante que não está ligado a nenhum índice.
Desenvolvimento e Otimização de Modelos Lineares Práticos Por Meio do GAMS______________ 23
0X
9Xmintouro
12Xmaxtouro
100Xminvacas
200Xmaxvacas
60Xsminnovilha
170Xsmaxnovilha
53"Xminbezerro
135"Xmaxbezerro
39"Xminbezerra
95"Xmaxbezerra
.
:a sujeito
 Zanimais
ji,
touro""i
touro""i
vacas""i
vacas""i
novilhas""i
novilhas""i
bezerros"i
bezerros"i
bezerras"i
bezerras"i















j
n
i
iji,
n
i
i
PXR
X
Para este modelo temos um problema de programação inteira. Este assunto será discutido nos próximos 
capítulos. Portanto, resolveremos o mesmo por meio da otimização linear contínua.
A Figura 3.1 mostra o modelo em linguagem GAMS. A solução ótima não inteira seria: bezerras= 39, 
bezerros= 132,33, novilhas= 132,172, vacas= 127,773 e touro= 8,71. Utilizando 486.350,05 do 
orçamento.
Desenvolvimento e Otimização de Modelos Lineares Práticos Por Meio do GAMS______________ 24
Figura 3.1- Modelo agricultura em GAMS.
Os ‘e as “ (estes pontos ‘ “) são indexadores de índices na linguagem GAMS.
Exemplo 4: Alocação de tarefas.
Uma empresa de correios deseja estabelecer o número de funcionários de horários integral que deve 
contratar para iniciar suas atividades. Para fazê-lo, recebeu uma matriz da empresa com o número 
mínimo de funcionários por dia da semana. Estas informaçõesse encontram na Tabela 3.3. O 
Desenvolvimento e Otimização de Modelos Lineares Práticos Por Meio do GAMS______________ 25
sindicato dos empregados de franqueadores dos correios mantém um acordo sindical que 
determina que cada empregado deve trabalhar cinco dias consecutivos e folgar em seguida dois 
dias, e que as franquias devem ter apenas empregados com horário integral. Desenvolva e otimize o
modelo de maneira a determinar o número total de empregados que a franquia deve contratar e o 
número de empregados por dia, utilizando a linguagem de modelagem GAMS.
Tabela 3.3- Dados do problema da empresa correios.
Dia da semana Número de funcionários
Domingo 11
Segunda-feira 18
Terça-feira 12
Quarta-feira 15
Quinta-feira 14
Sexta-feira 14
Sábado 16
Índices:
n: associado ao número de funcionários 
s: associado aos dias da semana.
Parâmetros:
Alocaçãos,n: associado ao número de funcionários n requeridos no dia da semana s.
Funcionáriosn: associado ao número mínimo de funcionários n para trabalhar no dia da semana s.
Variáveis:
Z associada à função objetivo.
Xs: número de funcionários i contratados no dia da semana s.
Equações:
Func: calcula a função objetivo.
Alocadosn: calcula o número de funcionários alocados em cada dia da semana s.
A Figura 3.2 mostra o resumo do modelo no GAMS. A solução ótima para o problema é contratar 22,6666 
funcionários no total, sendo que seria contratado 5 funcionários no domingo, 1,666 na segunda, 4.667 na 
terça, 7,667 na quinta e 3.667 no sábado. Os totais de empregados disponíveis por dia da semana estão 
dispostos abaixo, sendo N1 número de funcionários que iniciam a atividade no domingo e N7 o número 
de funcionários que iniciam a atividade no sábado. N1= 16.333, N2= 18, N3= 15, N4= 15, N5= 19 e N6=14 
e N7= 16
Desenvolvimento e Otimização de Modelos Lineares Práticos Por Meio do GAMS______________ 26
0X
osfuncionari.alocacao alocados
:asujeito
X Zfunc.
ns,
n
s
ns,n
s
s





s
n
X
Figura 3.2- Modelo correios pelo GAMS.
Exemplo de decisão entre fazer ou comprar:
A turbo motores LTDA, uma fábrica de motores especiais, recebeu recentemente R$ 100.000,00 em 
pedidos de seus três tipos de motores. Cada motor necessita de um determinado número de horas de 
trabalho no setor de montagem e acabamento. A turbo motores deseja determinar quantos motores 
devem ser produzidos em sua fábrica e quantos devem ser produzidos de forma terceirizada para 
Desenvolvimento e Otimização de Modelos Lineares Práticos Por Meio do GAMS______________ 27
atender à demanda de pedidos. A Tabela 3.4 mostra as informações referentes a esta empresa.
Tabela 3.4- Dados da empresa turbo motores.
Modelo 1 2 3 Disponibilidade
Demanda 3000 unid 2500 unid 550 unid
Montagem 1 h/unid 2h/unid 0,5 h/unid 6000 h
Acabamento 2.5 h/unid 1h/unid 4h/unid 10000h
Custo de 
produção 
R$ 50 R$ 90 R$ 120
Terceirização R$ 65 R$ 92 R$ 140
Índices:
p: associado à produção.
j: associado aos recursos.
Parâmetros:
Aj: associado à disponibilidade dos recursos j.
Produzirp,: associado ao consumo da recurso j pelo produto p.
Custop: associado ao custo de produção do produto p.
cust: associado ao custo de terceirização t.
demandap,: associado a decisão unitária de produção e terceirização.
demandasp: associado a demanda do produto p que pode ser fabricado ou terceirizado.
Variáveis.
Z relacionado à função objetivo.
Mincp,: quantidade a ser produzida e terceirizada do produto p visando a obtenção do menor custo.
Produzidop: quantidade a ser fabricada do produto p.
Terceirizadop: quantidade a ser terceirizada do produto p.
Equações:
Customin: calcula o custo mínimo.
Consumop: calcula o consumo do recurso j pelo produto p.
Decisãop,t: calcula a decisão entre produzir e terceirizar.
Desenvolvimento e Otimização de Modelos Lineares Práticos Por Meio do GAMS______________ 28
Modelo matemático:
0zado terceiriproduzido, minc,
demandasoterceirzadproduzido
Aproduzido.produzir..consumo
:aSujeito
cus.doterceirizacusto.produzido Zcustomin.
ppp
jpjp,j
p
tppp





 
p
t
A figura 3.3 resume o desenvolvimento desse modelo em GAMS.
Desenvolvimento e Otimização de Modelos Lineares Práticos Por Meio do GAMS______________ 29
Figura 3.3- Modelo de decisão de compra ou terceirização em GAMS
Solução ótima: Produzir P1=3.000; P2= 500; P3= 500, terceirizando a produção de P2= 2.000. Gerando um 
lucro máximo= R$ 43.900,00. 
 Capítulo 4
4. DESENVOLVIMENTO E OTIMIZAÇÃO DE MODELOS DINÂMICOS 
A maioria dos problemas de otimização práticos são multiperíodo ou dinâmicos, e neste caso o 
modelo matemático torna-se mais complexo. Resolvamos o problema de estoque:
Uma empresa de barcos precisa determinar quantos veleiros devem ser produzidos durante 
cada um dos 4 próximos trimestres. A demanda de cada um dos trimestres é: primeiro 
trimestre, 40 veleiros; segundo trimestre, 60 veleiros, terceiro trimestre, 75 veleiros, quarto 
trimestre, 25 veleiros. A empresa quer atender a demanda prontamente. No início do 
primeiro trimestre, a empresa tem 10 veleiros em estoque. No início de cada trimestre, a 
empresa precisa decidir quantos veleiros devem ser produzidos durante o trimestre. Por 
simplicidade, assume-se que os veleiros são fabricados durante um trimestre podem ser 
usados para atender a demanda deste trimestre. Durante cada trimestre, a empresa pode 
produzir até 40 veleiros com sua mão de obra regular a um custo de R$ 400,00 por veleiros. 
Tendo de trabalhar com horas extras durante o trimestre, a empresa pode produzir veleiros 
a mais a um custo total de R$ 450,00 por barco. No final de cada trimestre após ter ocorrido 
a produção e a demanda do trimestre ter sido atendida, um custo de transporte ou 
armazenagem de R$ 20,00 por barco ocorre. Desenvolva o modelo matemático por meio do 
software GAMS.
Solução:
Índices:
i: associado ao produto veleiro.
t: associado aos trimestres. 
Na linguagem GAMS há outra função chamada alias, esta função permite a inclusão de subíndices 
no modelo matemático. Neste caso vamos criar 2 subíndices, associados ao índice principal t
t,textra: associado à produção utilizando horas extras no trimestre t.
t,stoks: associado ao estoque do produto veleiro no trimestre t.
Desenvolvimento e Otimização de Modelos Dinâmicos____________________________________ 31
Parâmetros:
Demandat: associado à demanda requerida do produto i para cada trimestre t.
Producaot: associado à produção máxima para o produto i para cada trimestre t.
Mt,i: associado à produção do produto i usando a mão de obra normal no trimestre t.
Extratextra,i: associado à produção do produto i utilizando horas extras no trimestre t.
Estocagemstoks,i: associado à estocagem do produto i no trimestre t.
I0t,i,: associado ao estoque inicial do produto i no trimestre t.
Contrt: controle de estoque inicial.
Variáveis:
Z função objetivo.
produtoextrat,i: produção do produto i com mão de obra extra no trimestre t.
produtoestoquet,i: estoque do produto i no trimestre t.
Equações:
Mincusto: calcula o custo mínimo da função objetivo.
Limitet: calcula a produção do produto i no trimestre t.
fabricaot: calcula o limite fabricado em horas disponíveis.
calculoestoquet: calcula a capacidade de estoque no trimestre t. 
0 oqueprodutoest,raprodutoext,produtos
demandaoqueprodutoest
I0raprodutoextprodutooqueprodutoestoquecalculoest
producaoprodutofabricacao
demandaoqueprodutoestI0raprodutoextproduto.limite
:asujeito
estocagem.0quesprodutoestextra.raprodutoextM.produto
it,it,it,
ti1,-t
it,it,it,it,t
i
tit,t
i
ti1,-t,
i
it,
i
it,t
itextra,istoks,
istoks,istoks,itextra,itextra,
it,
it,it,










 
i
iii
it
Z
A Figura 4.1 mostra este modelo em linguagem GAMS.
Desenvolvimento e Otimização de Modelos Dinâmicos____________________________________ 32
Desenvolvimento e Otimização de Modelos Dinâmicos____________________________________ 33
Figura 4.1- Modelo dinâmico de estoque em linguagem GAMS.
Solução ótima: produção utilizando horas normais: t1=40; t2= 40; t3= 40 e t4= 25.
Produção utilizando horas extras: t2= 10; t3= 35.
Estoques: t1= 10. Custo mínimo R$ 7.840,00
Exemplo 2: Fluxo de caixa multiperíodo.
Uma empresa está construindo um novo restaurante que integrará a sua cadeia no próximo 
ano. Para tal, necessita de um total de R$ 500.000,00 que será pago à construtora em duas 
parcelas de R$ 150.000,00 ao final do 2º e 5º meses, e uma parcela de R$ 200.000,00 ao 
Desenvolvimento e Otimização de Modelos Dinâmicos____________________________________ 34
término da construção no fim do 7º mês. A empresa dispõe de 4 tipos de investimentos que 
podem ser utilizados a fim de gerar caixa para quitar a construção de maneira a reduzir a 
necessidade total de caixa. Informações:
Investimento Aplicação 
disponível no 
início dos meses
Meses de duração 
da aplicação
Retorno ao final do 
investimento
Tipo A 1,2,3,4,5,6,7 1 1.5%
Tipo B 1,3,5 2 3.2%
Tipo C 1,4 3 4.5%
Tipo D 1 7 9%
Solução:
Índices:
j: associado aos tipos de investimento.
m: associado aos meses.
a: associado às aplicações disponíveis.
Parâmetros:
Investimentosj, a, m: associado a alocado do disponível a no tipo de investimento j no mês m.
Dm: associado à parcela a ser paga no mês m.
Variáveis:
Z associada à função objetivo.
Utilizadoj, a: associada ao valor aplicado no tipo de investimento j do disponível a.
Equações:
Aplicações: calcula a função objetivo.
Cálculom: calcula o valor aplicado em cada tipo de investimento. 
Desenvolvimento e Otimização de Modelos Dinâmicos____________________________________ 35
0Utilizado
DUtilizado.tosInvestimen
:asujeito
UtilizadoDUtilizadoCUtilizadoBA UtilizadoMin Z..Aplicações
aj,
n
aj,
maj,ma,j,
1111




A Figura 4.2 contempla o modelo fluxo de caixa em linguagem GAMS.
Figura 4.2- Modelo fluxo de caixa em linguagem GAMS.
Desenvolvimento e Otimização de Modelos Dinâmicos____________________________________ 36
Exercícios propostos
Uma fábrica produz refrigeradores, freezers e fornos. A demanda mensal média destes produtos 
é, respectivamente, de 115.000, 58.000 e 48.000 unidades, e segue um esquema de médias 
móveis com período de 4, isto é, a demanda de quatro meses consecutivos e constantes ao longo 
do tempo. A demanda registrada nos últimos três meses foi à seguinte:
Demanda mensal por (unidades)
Produto Julho Agosto Setembro
Refrigerador 125.000 108.000 136.000
Freezer 57.000 52.000 73.000
Forno 45.000 36.000 58.000
Para fabricar estes produtos, três recursos básicos são necessários (MDO, MP e energia), cujos 
consumos unitários estão apresentados no quadro abaixo.
Consumo unitário
Produto MDO/ horas Material Kg Energia kWh
Refrigerador 1,4 17 25
Freezer 1,7 21 23
Forno 1,1 10 17
A fábrica dispõe de 1.900 empregados na linha de produção, cada um dos quais trabalha 200 
horas por mês. O custo de armazenamento mensal de uma unidade de cada produto R$ 10, R$ 13, 
R$ 8, respectivamente. A disponibilidade mensal de energia é 5,5 x 106 KW/h. A empresa poderá 
comprar até 3.850 ton/ mês de material, que poderá ser armazenado a um custo mensal de R$ 
0,15kg. Desenvolva o modelo matemático que permita determinar o plano ótimo de produção-
material-pessoal para os próximos 12 meses, de modo a garantir que todos os empregados 
entrem em férias (1 mês) durante este período. Considere que no início do mês de outubro não 
existe estoque de produto acabado e que o estoque de matéria-prima é de 3.200 toneladas.
 Capítulo 5
5. DESENVOLVIMENTO E OTIMIZAÇÃO DE MODELOS INTEIROS 
Supondo que a empresa X, tenha uma disponibilidade máxima de R$ 650 reais para realizar 
vários investimentos. A taxa mínima de atratividade requerida por esta empresa é 10%, 
para cada um dos projetos. Os projetos 1 a 6 são mutuamente excludentes, ou seja, a escolha 
de um elimina os outros 5.
Após a realização dos cálculos obtiveram os seguintes resultados
Projeto Investimento Inicial/
(UM 1.000,00)
Valor Presente p/ I=
 10% p/UM 1.000,00
1 R$ 150,00 R$ 500,00
2 R$ 160,00 R$ 515,00
3 R$ 170,00 R$ 555,00
4 R$ 210,00 R$ 530,00
5 R$ 180,00 R$ 565,00
6 R$ 240,00 R$ 595,00
7 R$ 200,00 R$ 500,00
8 R$ 150,00 R$ 400,00
9 R$ 70,00 R$ 30,00
10 R$ 250,00 R$ 350,00
11 R$ 150,00 R$ 300,00
Selecionar o portfólio de projetos que maximize o valor presente desta empresa. Os recursos 
disponíveis são de R$ 650.
Solução:
Índices:
p: associado aos projetos disponíveis.
Parâmetros:
Investimentop: capital disponível para investir no projeto p.
Desenvolvimento e Otimização de Modelos Inteiros______________________________________ 38
VPLp: Valor presente do projeto p.
 Variáveis:
Z: Função objetivo
MAXVPLp: associado à escolha do projeto p.
Modelo matemático:
 10,MaxVPL
650toInvestimen.MAXVPL
1MAXVPL
:asujeito
VPL.MAXVPLMax Z
p
pp
6
p
p
n
p
p






p
Desenvolvimento e Otimização de Modelos Inteiros______________________________________ 39
Figura 5.1- Modelo MIP1 em GAMS.
Solução ótima: Investir nos projetos: P1, P7, P8 e P11. Gerando um VPL máximo R$ 1.700,00.
Exemplo 2:
Uma indústria quer se expandir, construindo nova Fábrica ou em Itajubá ou em 
Guaratinguetá. Também será considerada a construção de um novo Depósito na cidade que 
for selecionada para receber a nova Fábrica. O Valor Presente Líquido de cada alternativa 
está na Tabela 5.1. A última coluna dá o Capital Requerido para os investimentos, sendo o 
capital total disponível $25 milhões. Achar a combinação viável de alternativas que 
Maximize o Valor Presente Líquido Total.
Tabela 5.1- Dados para a construção da nova Fábrica.
Decisão Sim ou Não VPL
Capital
Requerido
1 Fábrica em Itajubá 7.000.000 20.000.000
2 Fábrica em Guaratinguetá 5.000.000 15.000.000
3 Depósito em Itajubá 4.000.000 12.000.000
4 Depósito em Guaratinguetá 3.000.000 10.000.000
Desenvolvimento e Otimização de Modelos Inteiros______________________________________ 40
Solução: Modelo Matemático:
 10,selecao
selecaoselecao
iaorçamentárRestrição25.000.000capital.selecao
:asujeito
VPL.selecaoMax Z
ji,
deposito"",itajuba""fabrica"",itajuba""
n
ji,
ji,ji,
n
ji,
ji,ji,






A Figura 5.2 mostra este modelo em linguagem GAMS.
Desenvolvimento e Otimização de Modelos Inteiros______________________________________ 41
Figura 5.2- Modelo MIP2 em linguagem GAMS.
Solução ótima: Construir tudo em Guaratinguetá. Gerando um VPL máximo de R$ 8.000.000,00.
Repare que utilizamos o solver MIP (CPLEX 12.1.0), sendo este solver o mais adequado para 
resolver problemas mistos, binários e inteiros.
 Capítulo 6
6. DESENVOLVIMENTO E OTIMIZAÇÃO DE MODELOS DE REDES 
De forma geral, modelos de rede são utilizados em casos especiais de otimização linear que são 
mais bem analisados por meio de uma representação gráfica. 
Modelos de rede são diagramas compostos por uma coleção de vértices ou nós ligados entre si 
por um conjunto de arcos, conforme mostra a Figura 6.1. Os nós são os círculos e os arcos são as 
retas de ligação. 
Figura 6.1- Componentes de uma rede.
Os problemas modelados como redesgeralmente apresentam números associados aos nós e aos 
arcos. Em problemas de transporte modelados como redes, por exemplo, os números associados 
aos nós podem representar a quantidade de produtos ofertados ou demanda pelo nó, ao passo 
que os valores dos arcos podem refletir os custos de transporte (ou tempo, ou à distância) entre 
um nó e o outro. Diversos problemas de tomada de decisão práticos estão categorizados como 
problemas de Rede. Entre eles pode-se citar:
 Problemas de transporte; Escala de Produção; Rede de Distribuição; Problemas de Menor 
Caminho; Problemas de fluxo máximo; Problemas de caminho crítico; Problemas de 
árvores geradoras mínimas.
A Figura 6.2 contempla um exemplo de redes em problemas de transporte.
Desenvolvimento e Otimização de modelos de redes______________________________________ 43
Figura 6.2- Exemplo de problemas de transporte.
Exemplo 1:
Uma empresa fabricante de bicicletas possui três fábricas localizadas no Rio, em São Paulo e 
em Belo Horizonte. A produção da empresa deve ser entregue em Recife, Salvador e Manaus. 
Considerando os custos de transporte unitários, a capacidade de produção das fábricas e a 
demanda dos centros consumidores ilustrados na Tabela a seguir.
 Determine quanto deve ser produzido e entregue por fábrica em cada centro consumidor, de 
forma a minimizar os custos de transporte.
Fábrica/ 
Consumidor
Recife Salvador Manaus Capacidade
Rio 25 20 30 2000
SP 30 25 25 3000
BH 20 15 23 1500
Demanda 2000 2000 1000
Solução:
Índices:
i: associado às fábricas
j: associado aos destinos.
Parâmetros:
Custoi, j: associado ao envio da fábrica i para o destino j.
Desenvolvimento e Otimização de modelos de redes______________________________________ 44
Capacidadei: associado à capacidade máxima de armazenagem da fábrica i.
Demandasj: associado à demanda requerida pelo destino j.
Variáveis:
Z: função objetivo.
Mincustoi, j: associada à quantidade enviada da fábrica i para o destino j ao menor custo.
MODELO MATEMÁTICO:
0envio
Demandaenvio
capacidadeenvio
:asujeito
.custoenvio
ji,
jji,
j
iji,
,
ji,ji,







i
n
ji
Z
A Figura 6.3 mostra este modelo em GAMS.
Desenvolvimento e Otimização de modelos de redes______________________________________ 45
Figura 6.3: Modelo Rede 1.
Desenvolvimento e Otimização de modelos de redes______________________________________ 46
Este modelo pode ser representado por um formato de rede conforme contemplado pela Figura
6.4.
Figura 6.4- Modelo de rede do exemplo 1.
Em modelos de transporte as equações devem estar equilibradas, isto é, oferta total= demanda 
total. Entretanto, podemos adotar um fluxo de balanceamento.
Hipótese do Problema Tipo de Restrição
Oferta > Demanda Entradas-Saídas ≥ Oferta ou demanda do nó
Oferta < Demanda Entradas- Saídas ≤ Oferta ou Demanda do nó
Oferta= Demanda Entradas-Saídas= Oferta ou demanda do nó
Neste caso a oferta é maior que a demanda.
A Figura 6.5 contempla este exemplo modelado em linguagem GAMS.
Desenvolvimento e Otimização de modelos de redes______________________________________ 47
Figura 6.5- Exemplo de modelo de rede em transportes.
Desenvolvimento e Otimização de modelos de redes______________________________________ 48
6.2 DESENVOLVIMENTO E OTIMIZAÇÃO DE MODELOS DE REDES EM PROBLEMAS 
DE ESCALA DE PRODUÇÃO 
Uma empresa fornece motores para um grande número de equipes de fórmula 1. A 
companhia detém uma série de contratos de entregas futuras programadas para o próximo 
ano. As entregas deverão ocorrer trimestralmente, de acordo com as necessidades das 
equipes. A Tabela a seguir resume por trimestre as entregas programadas, a capacidade 
máxima de produção e o custo unitário de produção. As entregas são feitas no final do 
trimestre e os motores podem ser armazenados por quantos trimestres forem necessários 
ao custo de 0,015 milhão de reais por trimestre. A diretoria deseja minimizar os custos 
totais de produção (produção + armazenagem). Quantos e quando os motores pedidos 
devem ser produzidos e entregues?
Trimestre
Pedidos 
Contratados
Capacidade de 
Produção
Custos unitários em milhares de 
reais
1 10 25 1,08
2 15 35 1,11
3 25 30 1,1
4 20 10 1,13
Para resolver este problema como um problema de transporte, precisamos primeiramente 
determinar quais serão as fontes, os destinos e as variáveis de decisão.
Solução:
Índices:
i: associado à produção dos motores.
j: associado à entrega dos motores.
t: associado aos trimestres.
Parâmetros:
Custoi, t: associado ao custo de produção.
Capacidadei: capacidade máxima de produção.
Contratosj, t: associado à demanda dos motores em cada trimestre.
Desenvolvimento e Otimização de modelos de redes______________________________________ 49
Demandasj, i, t: associado à entrega do motor produzido no trimestre t a ser entregue nos 
trimestres.
capacidadesp11i, t: associado à entrega dos motores produzidos no trimestre t.
estoquest: associado ao custo de estoque no trimestre t.
estoquessi, t: associado ao estoque no trimestre t. 
Variáveis:
Z: função objetivo.
Envioi, t: quantidade a ser enviada do motor produzido no trimestre t.
Stokt: associada à ociosidade no trimestre t.
0stok
0envio
30stok
contratosdemandas.envio
capacidadeestoquess.stokcapacidade.envio
:asujeito
estoques.stok.custoenvio
t
ji,
t
 tj, ti,j, ti,
t
n
t
i ti,t ti, ti,
tt
,
ti, ti,








 

n
t
i
n
t
n
ti
Z
Desenvolvimento e Otimização de modelos de redes______________________________________ 50
Desenvolvimento e Otimização de modelos de redes______________________________________ 51
Figura 6.6 - Exemplo de modelos de produção.
6.3 DESENVOLVIMENTO E OTIMIZAÇÃO DE MODELOS DE REDE DE DISTRIBUIÇÃO 
Problemas que consideram múltiplas fontes, centros consumidores e locais intermediários por 
onde os produtos simplesmente passam são denominados de problemas de rede de distribuição. 
Os problemas de transporte podem ser vistos como uma simplificação do problema de rede de 
distribuição de custo mínimo, onde as localizações intermediárias não existem. 
Exemplo 1:
Uma montadora de tratores está iniciando as suas operações no país, construindo duas 
fábricas: uma na Bahia e outra em São Paulo. A montadora está estudando a forma de 
distribuição de seus carros para as diversas revendas, localizadas nos estados de Goiás, Rio 
de Janeiro, Minas Gerais, Paraná, Santa Catarina e Rio Grande do Sul, que minimize o custo 
total de distribuição. As capacidades instaladas de cada uma das fábricas, as demandas das 
revendas, bem como os custos unitários de transporte entre fábricas e revendas estão 
evidenciadas na rede abaixo:
Desenvolvimento e Otimização de modelos de redes______________________________________ 52
Figura 6.7- Diagrama de Rede do exemplo 1.
Neste problema a oferta é maior que a demanda e, portanto, adota-se que as entradas- saídas ≤ 
oferta do nó.
Solução:
Índices:
i: associado aos nós de oferta.
j: associado aos nós de demanda.
Parâmetros:
Capacidadei: associado à capacidade máxima dos nós de oferta.
Demandaj: associado à demanda máxima do destino j.
Custoi, j: associado ao custo de envio da origem i para o destino j.
Redei j: associado à distribuição da origem i para o destino j.
Redesi, j: associado à distribuição da rede.
Variáveis:
Z: função Objetivo.
Envioi, j: quantidade a ser enviada da origem i para o destino j.
Desenvolvimento e Otimização de modelos de redes______________________________________ 53
Modelo:
0envio
Demandaredes.envio
capacidaderede.envio:asujeito
.custoenvio
ji,
i
jji,ji,
j
iji,ji,
,
ji,ji,







n
ji
Z
A Figura 6.8 mostra esse modelo em linguagem GAMS. Solução ótima: 
Origem/Destino SC MG GO RJ RS PR
BA 200 150 150
SP 100 200 300
D 50 250
Custo mínimo R$ 28.000,00
Desenvolvimento e Otimização de modelos de redes______________________________________ 54
Figura 6.8- Modelo distribuição em GAMS.
A variável D é uma adição de uma origem fictícia, pois a demanda é maior que a oferta e, em 
modelos de transporte a oferta total = demanda total. A leitura é a seguinte: não foram enviadas 
50 e 250 unidades para SC e RS respectivamente.
6.4 DESENVOLVIMENTO E OTIMIZAÇÃO DE PROBLEMAS DO MENOR CAMINHO 
O problema do menor caminho representa um caso especial de problemas de redes, em que os 
arcos significam a distância entre dois pontos (vértices ou nós). Quando desejamos achar a rota 
que une estes pontos com distância mínima entre as possíveis rotas, temos um problema do tipo 
do menor caminho. 
Em problemas do menor caminho haverá sempre dois tipos de vértices especiais chamados de 
origem e destino. Entre estes nós há nós intermediários, que podem representar cidades que 
conectam rodovias, subestações em problemas de distribuição de energia, e assim por diante.
Exemplo 2:
A fábrica de artigos e decoração Águia, localizada em Lambari, Minas Gerais, deve entregar 
uma grande quantidade de peças na cidade de Baependi, localizada no mesmo estado. A 
empresa quer saber qual o caminho que seu caminhão de entregas deve percorrer para 
Desenvolvimento e Otimização de modelos de redes______________________________________ 55
minimizar a distância total percorrida. A Figura 6.9 mostra as cidades e as respectivas 
distâncias.
Figura 6.9- Mapa rodoviário que liga as cidades de Lambari a Baependi
Solução:
Índices:
i: associado aos nós de oferta.
j: associado aos nós de demanda.
Parâmetros:
Distânciai, j: associado à distância da origem i para o destino j.
Circuitoi, j: associado à rede entre a origem i para o destino j.
Circuito2i, j: associado à rede entre a origem i para o destino j.
Circuito3i, j: associado à rede entre a origem i para o destino j.
Circuito4i, j: associado à rede entre a origem i para o destino j.
Cicloi, j: associado à rede entre a origem i=lambari para o destino j.
Ciclosi, j: associado à rede para o destino final.
Nosi: associado ao nó especial da origem.
Nosj: associado ao nó especial do destino final.
Variáveis:
Z: função Objetivo.
Desenvolvimento e Otimização de modelos de redes______________________________________ 56
Envioi, j: quantidade a ser enviada da origem i para o destino j.
Modelo:
 1;0envio
0circuito4.envio
0circuito3.envio
0circuito2.envio
0circuito.envio
Nosciclo.envio
Nosciclo.envio
:asujeito
.distanciaenvio
ji,
i
ji,ji,
i
ji,ji,
i
ji,ji,
i
ji,ji,
i
jji,ji,
j
iji,ji,
,
ji,ji,















n
ji
Z
A Figura 6.10 mostra esse modelo em GAMS.
Desenvolvimento e Otimização de modelos de redes______________________________________ 57
Figura 6.10- Problema do menor caminho em GAMS.
Desenvolvimento e Otimização de modelos de redes______________________________________ 58
6.5 DESENVOLVIMENTO E OTIMIZAÇÃO DE PROBLEMAS DE FLUXO MÁXIMO
O tipo de problema de fluxo máximo é utilizado quando queremos maximizar a quantidade de 
fluxo de um ponto de origem para um ponto de destino, sujeitos a restrições de capacidade de 
fluxo nos arcos.
Estes problemas geralmente envolvem um fluxo de materiais como água, óleo, gás, energia por 
meio de uma rede de tubos ou cabos, porém, também podem representar o fluxo mínimo de 
carros em uma malha rodoviária, de produtos em linha de produção, e assim por diante.
Exemplo:
Uma empresa distribuidora de gás deseja determinar a quantidade máxima de metros 
cúbicos por segundo de gás que pode bombear da estação de campos para o centro 
consumidor do Rio de Janeiro, por meio da rede de gasodutos. A Figura 6.11 ilustra a 
estrutura da rede de distribuição e apresenta a capacidade de fluxo máximo nos trechos em 
metros cúbicos por segundo.
Figura 6.11- Rede de gasodutos que ligam campos ao Rio de Janeiro.
Solução:
Índices:
i: associado aos nós de oferta.
ii: associado aos nós de destino.
Parâmetros:
Desenvolvimento e Otimização de modelos de redes______________________________________ 59
Capacidadei, ii: associado à capacidade máxima de fluxo de cada nó.
Circuitoi,ii: associado ao circuito do nó A.
Circuito2i,ii: associado ao circuito do nó 1.
Circuito3i, ii associado ao circuito do nó 2.
Circuito4i, ii: associado ao circuito do nó 3.
Circuito5i, ii: associado ao circuito do nó 4.
Circuito6i, ii: associado ao circuito do nó B.
Variáveis:
Z: função Objetivo.
Envioi, ii: quantidade a ser enviada da origem i para o destino j.















envio
0circuito.envio
0circuito5.envio
0circuito4.envio
0circuito3.envio
0circuito2.envio
0circuito.envio
capacidadeenvio
:asujeito
envio
iii,
iii,
iii,iii,
iii,
iii,iii,
iii,
iii,iii,
iii,
iii,iii,
iii,
iii,iii,
iii,
iii,iii,
iii,iii,
"a",b""Z
A Figura 6.12 contempla esse modelo em linguagem GAMS.
Desenvolvimento e Otimização de modelos de redes______________________________________ 60
Desenvolvimento e Otimização de modelos de redes______________________________________ 61
Figura 6.12: Modelo fluxo máximo em GAMS.
Solução ótima:
Origem/destino A 1 2 3 4 B
A 40 20
1 20 20
2 20
3 20
4 40
B 60
Fluxo máximo BA= 60.
6.6 DESENVOLVIMENTO E OTIMIZAÇÃO DE PROBLEMAS DE ESCALA DE PRODUCAO COMO 
MODELOS DE REDE POR MEIO DO GAMS
O caso dos problemas de escala de produção pode ser visto como problemas de transporte na 
forma tradicional.
Exemplo:
A fábrica de eletrodomésticos Galáctica deseja realizar o escalonamento de sua produção de 
liquidificadores para os próximos quatro meses. A fábrica pode produzir mensalmente, em 
jornada normal, 150.000 unidades a um custo unitário de R$ 15. Por meio do pagamento de 
horas extras, a capacidade mensal de produção da fábrica pode ser aumentada em 50.000 
liquidificadores, a um custo de produção unitário de R$ 22 (somente aos adicionais). Existe a 
possibilidade de armazenagem ilimitada de unidades de um mês para o outro a um custo 
unitário mensal de R$ 3. Sabendo que as demandas de liquidificadores para os próximos 
Desenvolvimento e Otimização de modelos de redes______________________________________ 62
quatro meses são de 120.000, 200.000, 120.000 e 180.000, resolva o problema utilizando-se 
da linguagem GAMS.
Do nó Para o nó Custo
1 A 15
1 E 0
2 A 22
3 B 15
3 E 0
4 E 0
4 B 22
5 C 15
5 E 0
6 C 22
6 E 0
T D 15
T E 0
8 D 22
8 E 0
A B 3
A C 3
C D 3
Os nós ímpares são os nós de produção sem horas extras. As letras a, b, c e d referem-se à
demanda por mês, o nó E é um nó fictício utilizado para equilibrar a oferta com a demanda.
Solução:
Índices:
i: associado aos nós de oferta.
j: associado aos nós de destino.
Parâmetros:
Desenvolvimento e Otimização de modelos de redes______________________________________ 63
Custoi ,j: associado ao custo entre os nós de saída com os nós de entrada.
Cicloi,j: associado ao circuito entre os nós com o nó fictício.
Circuitoi, j: associado ao circuito do nó A.
Circuito2i, j: associado ao circuito do nó 1.
Circuito3i, j associado ao circuito do nó b.
Circuito4i, j: associado ao circuito do nó c.
Circuito5i, j: associado ao circuito do nó e.
Variáveis:Z: função Objetivo.
Envioi, ii: quantidade a ser enviada da origem i para o destino j.














envio
180000circuito5.envio
180000circuito4.envio
120000circuito3.envio
200000circuito2.envio
120000circuito.envio
demandaciclo.envio
:asujeito
custo.envio
ji,
ji,ji,
ji,ji,
ji,ji,
ji,ji,
ji,ji,
ji,ji,
j
ji,ji,
i
Z
A Figura 6.13 contempla este modelo em linguagem GAMS.
Desenvolvimento e Otimização de modelos de redes______________________________________ 64
Desenvolvimento e Otimização de modelos de redes______________________________________ 65
Desenvolvimento e Otimização de modelos de redes______________________________________ 66
Figura 6.13: Modelo de escala de produção formulado em GAMS.
A Tabela abaixo apresenta um plano de manutenção de uma estufa dinâmica da Pintura a 
Pó LTDA. Uma das aplicações desse tipo de estufa é curar a tinta pó (de alta resistência) que 
é aplicada em peças metálicas. Por meio de um processo eletromagnético, o pó de tinta fica 
impregnado na peça, que é levada para dentro da estufa. Quando a peça entra na estufa a 
uma temperatura de aproximadamente 200 graus, a tinta derrete e fica impregnada na 
peça, num processo denominado cura da tinta. Em casos de produção de alto volume de 
peças pequenas e médias, produtos são fixados em gancheiras, que são transportados por 
trilhos que passam dentro da estufa aquecida.
Atividade Descrição Predecessor 
imediato
Tempo [hs]
A Desligar e desaquecer a estufa - 6
B Avaliar rolamentos danificados - 4
C Trocar rolamentos danificados B, A 7
D Avaliar e trocar resistências danificadas A 8
E Limpar estufa internamente D 10
F Lubrificar trilho com grafite C 2
G Fazer inspeção final E, F 1
H Religar estufa G 2
Figura 6.14- Atividades de um projeto de manutenção
Desenvolvimento e Otimização de modelos de redes______________________________________ 67
As atividades A e B não possuem atividades precedentes e, portanto, não há arestas de entrada. A 
atividade C possui arestas como predecessores imediatos, as atividades A e B. A atividade D 
possui como predecessor apenas a atividade A. As outras atividades são introduzidas na rede da 
mesma forma. Os números na construção da rede, algumas regras são levadas em consideração.
 O tamanho da aresta não tem associação com as atividades;
 As atividades iniciadas no final da aresta não podem ser iniciadas antes das atividades que 
são iniciadas no inicio da arestas;
 As atividades são representadas exclusivamente pelo seu início e término (evento inicial e 
final);
 Nós não podem ser duplicados;
 Dois nós só podem ser conectados por uma única aresta;
OBS: A função objetivo neste caso é o tempo total, logo é definida por H+2, ou seja, o horário de 
término da última atividade. Com relação às atividades A e B, como não há nenhuma atividade 
predecessora tem-se A=B= 0. Sobre a modelagem das atividades que possuem predecessoras, 
como por exemplo, a atividade C, que tem a atividade A e B como predecessoras, tem-se:
4ou 4
6ou 6


BCBC
ACAC
A figura 6.15 mostra a modelagem em GAMS
Desenvolvimento e Otimização de modelos de redes______________________________________ 68
Desenvolvimento e Otimização de modelos de redes______________________________________ 69
Figura 6.15- Modelo CPM EM GAMS
Exercícios para diversão.
Desenvolvimento e Otimização de modelos de redes______________________________________ 70
1) Análise a rede abaixo e faça o que é pedido.
Considere que os números indicados em cada aresta significam o número de quilômetros 
necessários para um automóvel percorrer a estrada entre duas cidades indicadas pelo nós 
extremos das arestas observadas. Monte o modelo e determine a rota que um automóvel deve 
seguir para sair de Chapecó e chegar a porto alegre, percorrendo a menor quantidade de 
quilômetros possível. 
2) Considere a reconstrução de um armazém que será feito. As atividades associadas são 
apresentados na Tabela a seguir:
Atividad
e
Descrição Predecessor 
imediato
Tempo 
[dias]
A Demolir o armazém - 2
B Comprar materiais para atividade de 
alvenaria
- 1
C Separar material reutilizável A 1
D Escavação de fundações A 2
E Preparação do acesso ao depósito A 1
F Fazer lista de outros materiais necessários C 1
Desenvolvimento e Otimização de modelos de redes______________________________________ 71
G Fazer fundações de concreto B, D 2
H Fazer acesso E 1
I Levantar paredes de alvenaria B, G 8
J Nivelar chão e fazer o contra piso F, G 2
K Instalar fiação e sistema elétrico F, I 1
L Acabar paredes K, M, N 5
M Fazer telhado F, I 1
N Acabar piso de concreto J 5
O Montar calhas e tubulações de escoamento F, M 1
P Limpar H, L, O 1
Crie a rede associada ao projeto de reconstrução e indique qual o menor tempo para realização 
do projeto. Qual é o caminho crítico?
3) A pessoa responsável pelo plano de atividade do armazém cometeu dois pequenos erros. 
Ela introduziu duas relações da precedência imediata redundantes. Isso é uma falha 
conceitual e acontece nos planos de atividades mal feitos. Quais são as duas relações de 
precedência que não deveriam ter sido colocadas no plano?
72
 Capítulo 7
7. DESENVOLVIMENTO E OTIMIZAÇÃO DE MODELOS DE OTIMIZAÇÃO COMBINATÓRIA 
Neste tópico vamos comentar sobre problemas de dificuldade polinomial (P) e problemas de 
dificuldade não polinomiais (NP).
Problemas polinomiais são problemas cujos algoritmos conhecidos fornecem soluções que 
podem ser obtidas por meio de uma função polinomial de n tamanho de entrada, ou seja: f (n) = 
O(nk) sendo que(k) uma constante. Problemas NP são problemas cujos algoritmos de solução 
conhecidos são baseados em enumeração, seja ela implícita ou não. De maneira geral, o número 
de combinações possíveis é assustadoramente grande, fazendo com que os algoritmos 
enumerativos não consigam resolver problemas com grande número de entradas em tempo 
hábil. São denominados algoritmos de tempo exponencial e, é nestes contextos que se encaixam 
os problemas de otimização combinatória. Os problemas NP podem ser classificado, conforme 
(COLIN, 2007):
 Problemas NP - Completos: são problemas que possuem uma forte evidência da não 
existência de um algoritmo cujo tempo de solução seja uma função polinomial do 
tamanho da entrada. São considerados os mais difíceis da classe NP, e, se algum deles for 
resolvido em tempo polinomial, então todos os problemas NP também serão.
Quando se sabe que um problema de otimização é NP - difícil, tem-se a certeza de que nem 
sempre a solução ótima será encontrada. Portanto, tem se aplicado métodos heurísticos, como 
por exemplo, algoritmos genéticos, colônias de formigas, busca tabu, dentre outras. Abaixo 
encontra-se o modelo do problema do Caixeiro-Viajante (CV), sendo este modelo de otimização 
combinatória.
Desenvolvimento e Otimização de Modelos de otimização combinatória_______________________73
  0u,1,0
subrotasSão
n)2,3,...,jn;3,...,2,ij;(i1-nnxuu
chegadadeRestrição
saídadeRestrição 
:asujeito
.Min Z
j,
ji,ji
1
,
1
,
1 1
,,








 
ji
n
j
ji
n
i
ji
n
i
n
j
jiji
X
X
X
XC
As restrições de saída e de chegada são binárias, e garantem que cada um dos xij seja 0 ou 1. As 
restrições de saída garantem que para cada cidade haverá apenas uma rota de saída e, 
analogamente uma chegada para as restrições de chegada.
As restrições de subrotas ou subcircuitos garantem que a solução ótima não contenha 
subcircuitos.
Exemplo1:
PARA
Sede P1 P2P3 P4
Sede 5 3.8 2.2 2.4
P1 5 2.6 3.1 5.1
P2 3.8 2.6 1.6 2.8
P3 2.2 3.1 1.6 2.3
DE
P4 2.4 5.1 2.8 2.3
A Figura 7.1 mostra a solução deste problema por meio da linguagem GAMS.
Desenvolvimento e Otimização de Modelos de otimização combinatória_______________________74
Desenvolvimento e Otimização de Modelos de otimização combinatória_______________________75
,
Desenvolvimento e Otimização de Modelos de otimização combinatória_______________________76
Desenvolvimento e Otimização de Modelos de otimização combinatória_______________________77
Desenvolvimento e Otimização de Modelos de otimização combinatória_______________________78
Figura 7.1-Modelo caixeiro viajante em GAMS.
A Figura 7.2 mostra os caminhos a serem percorridos.
Desenvolvimento e Otimização de Modelos de otimização combinatória_______________________79
Figura 7.2-Modelo Caixeiro Viajante otimizado pelo GAMS.
OBS: com n vértices há 
2
)!1( n ciclos distintos. 
 Capítulo 8
8. DESENVOLVIMENTO E OTIMIZAÇÃO DE MODELOS DE ANÁLISE POR ENVOLTÓRIA DE 
DADOS
Em termos de programação matemática, a análise por envoltória de dados (DEA- Data 
Envelopment Analysis), também chamada de análise de fronteiras ou análise de eficiência, é 
considerada uma técnica relativamente nova. Ao mesmo tempo, também é considerada um dos 
sucessos recentes da programação linear. No DEA existem as chamadas DMU- Decision Making 
Units, ou seja, as unidades tomadoras de decisão.
Em linhas gerais, a DEA avalia problemas com múltiplos recursos (usados para gerar produtos e 
ou serviços e múltiplas saídas para cada unidade) (COLIN, 2007). A capacidade com que as DMUs 
conseguem gerar saídas para determinadas entradas define sua eficiência. Supõe-se que as DMUs 
menos eficientes podem melhorar sua eficiência até o limite das melhores unidades , cuja 
eficiência é de 100%. Mais especificamente, a DEA determina, segundo Colin (2007):
 A melhor prática- grupo das DMUs mais eficientes;
 As DMUs menos eficientes comparadas com as melhores práticas;
 A quantidade de recursos utilizados de forma improdutiva nas DMUs menos eficientes;
 Para cada uma das DMUs menos eficientes, o grupo das unidades de melhor prática que 
são mais parecidas com elas e que poderiam ser usadas como benchmarks.
Antes de prosseguir com o DEA, vamos entender alguns significados.
 Eficácia – Capacidade da unidade produtiva atingir as metas previamente estabelecidas;
 Produtividade – Razão entre o que foi produzido e o que foi gasto para produzir. Ex.: 
Peças/H.h;
 Eficiência – Conceito relativo que compara o que foi produzido com o que poderia ter sido 
produzido. Pode ser entendida como uma comparação entre as produtividades 
observadas;
Desenvolvimento e Otimização de modelos de análise por envoltória de dados_________________ 81
Se uma unidade atingiu a meta, foi eficaz. Se conhecermos os recursos que a unidade dispunha 
podemos avaliar se esta foi produtiva. Se soubermos quais foram os resultados da concorrência 
podemos avaliar a eficiência da unidade (SOARES DE MELLO, 2005)
O modelo DEA CCR (Charnes, Cooper e Rhodes, 1978) é apresentado no modelo abaixo. 
 i , v 
 j,, u 
nc,, k 
 xv
 yu
 S.a.: 
 xv
 yu
Max E
i
j 
m
i
iki
s
j
jkj
m
i
ici
s
j
jcj
c












0
0
,,,,211
1
1
1
1

Onde: c é o índice da unidade que está sendo avaliada. O problema acima envolve a procura de 
valores para u e v, que são os pesos, de modo que maximize a soma ponderada dos outputs 
(output “virtual”) dividida pela soma ponderada dos inputs (input “virtual”) da DMU em estudo, 
sujeita à restrição de que esse quociente seja menor ou igual a 1, para todas as DMUs. 
Esta função está sujeita à restrição de que, quando o mesmo conjunto de coeficientes de entrada 
e saída (vis e ujs) for aplicado a todas as outras unidades de serviços que estão sendo 
comparadas, nenhuma unidade de serviço excederá 100% de eficiência ou uma razão de 1,00.. 
Porém, o modelo acima não é linear e sim um problema de programação fracionária. Entretanto, 
o modelo linearizado é descrito abaixo.
 x, y. , , v u 
n...,c, , k xv- yu 
xv S.a.: 
yuMax E
ij
m
i
iki 
s
j
jkj 
m
i
ici 
s
j
jcj c










0
,,,210 
1
11
1
1

Esta forma do problema é conhecida como problema dos multiplicadores, como também são 
chamados os pesos, uj e vi. 
Desenvolvimento e Otimização de modelos de análise por envoltória de dados_________________ 82
Exemplo 1:
Um hospital deseja avaliar sua eficiência em relação aos demais hospitais da cidade. A 
Tabela abaixo contempla os dados de entrada e saída analisados
Hospital Entradas (x) Saídas (y)
Capital
Mão de 
obra
Jovens Adultos Idosos
1 5 14 9 4 16
2 8 15 5 7 10
3 7 12 4 9 13
Neste caso são 3 problemas de programação linear, uma para cada DMU.
A Figura 8.1 mostra a solução deste modelos por meio do GAMS. Lembrando-os que 
Desenvolvimento e Otimização de modelos de análise por envoltória de dados_________________ 83
Figura 8.1- Modelo DEA em GAMS
Basicamente o que muda de um modelo para o outro é a função objetivo e a equação 4 (calculo 
4). Vamos interpretar a solução ótima para o último modelo. W2= 0,9 ; W3= 7.1% e V2= 8.3%. 
Neste caso as saídas adultos e jovens são importantes para manter a eficiência máxima do 
hospital 3. Deve-se conservar a mão de obra. A Figura 8.2 contempla um exemplo de como 
modelar o dual de um problema de DEA.
Desenvolvimento e Otimização de modelos de análise por envoltória de dados_________________ 84
Figura 8.2- Modelo primal e Dual de problemas de DEA.
Pelo GAMS também é possível rodar vários modelos continuamente. Vamos mostrar um exemplo 
tomando como base o exemplo exposto acima. A Figura 8.3 mostra este exemplo.
Desenvolvimento e Otimização de modelos de análise por envoltória de dados_________________ 85
Figura 8.3: Modelo DEA GLOBAL.
Desenvolvimento e Otimização de modelos de análise por envoltória de dados_________________ 86
Repare que inseriu-se mais uma variável e também algumas equações e, ao rodar o modelo, deve 
ser informado apenas as equações pertencentes ao modelo desejado.
Outro tipo de modelo DEA que iremos ver nesta apostila é conhecido por BCC (Banker, Charnes e 
Cooper, 1984). No modelo DEA CCR há retornos de escalas constantes, válido para unidades 
operando em escala ótima. No modelo BCC ou VRS, substitui o axioma da proporcionalidade pelo 
axioma da convexidade linear, soma dos lambdas igual a 1. Fronteira côncava e linear por parte, 
também chamado de retorno variáveis de escala.
 u
j, i. , , v u 
k ,uyuxv 
xv S.a.: 
uyuMax E
ij
j
jkj
j
iki 
i
ici 
j
jjff










* 
0
0* 
1
*.
.
1
1
00
As eficiências no modelo DEA BCC são maiores ou iguais as eficiências do modelo CCR. No modelo 
CCR as eficiências independem da orientação; os outros resultados de DEA dependem da 
orientação
No modelo BCC todos os resultados de DEA dependem da orientação. A Figura 8.4 mostra as 
diferenças entre estes modelos.
Figura 8.4- Modelos DEA
Desenvolvimento e Otimização de modelos de análise por envoltória de dados_________________ 87
A figura 8.5 contempla a solução deste exemplo