Programação Linear Inteira

Prévia do material em texto

FACULDADE DE TECNOLOGIA DE MOGI DAS CRUZES 
CURSO SUPERIOR DE TECNOLOGIA EM LOGÍSTICA 
 
 
 
Antônio Flavio Silva 
Ariany Fernanda Sueitt de Jesus 
Arlinda de Jesus Ribeiro 
Fernanda Marin Fernandes 
Karoline Alves Fernandes Dias 
Jonathan Pereira de Castilho 
Lucas André Barreto 
Kairo Sumida 
 
 
 
 
 
 
PROGRAMAÇÃO LINEAR INTEIRA 
 
 
 
 
 
 
Mogi das Cruzes – SP 
2017 
FACULDADE DE TECNOLOGIA DE MOGI DAS CRUZES 
CURSO SUPERIOR DE TECNOLOGIA EM LOGÍSTICA 
 
 
Antônio Flavio Silva 
Ariany Fernanda Sueitt de Jesus 
Arlinda de Jesus Ribeiro 
Fernanda Marin Fernandes 
Karoline Alves Fernandes Dias 
Jonathan Pereira de Castilho 
Lucas André Barreto 
Kairo Sumida 
 
 
 
 
 
PROGRAMAÇÃO LINEAR INTEIRA 
 
Trabalho elaborado como exigência parcial para 
compor a nota semestral na matéria de Métodos 
Quantitativos do curso de Tecnólogia em Logística 
na Faculdade de Tecnologia de Mogi das Cruzes. 
 
 
 
 
 
 
Mogi das Cruzes – SP 
2017
Sumário 
1. INTRODUÇÃO ........................................................................................................... 1 
2. MÉTODOS QUANTITATIVOS DE GESTÃO ....................................................... 1 
3. PROGRAMAÇÃO LINEAR INTEIRA ................................................................... 2 
3.1 TIPOS DE MODELAGEM .................................................................................... 2 
3.2. COMO MODELAR OS PROBLEMAS ............................................................... 4 
3.2.1 SOLUÇÃO ATRAVÉS DO SOLVER ............................................................ 5 
3.2.2 SOLUÇÃO PELO MÉTODO DE BRANCH AND BOUND ........................ 7 
3.3 EXEMPLOS DE PROGRAMAÇÃO LINEAR INTEIRA .................................. 13 
4. APLICAÇÕES DA PROGRAMAÇÃO LINEAR INTEIRA ................................ 14 
5. CONSIDERAÇÕES FINAIS ................................................................................... 15 
6. REFERENCIAL BIBLIOGRÁFICO ..................................................................... 16 
 
 
FIGURAS 
Figura 1 - SOLVER .......................................................................................................... 6 
Figura 2 e 3 - Solução 3, segundo LINDO. .................................................................... 12 
Figura 3 - Exemplo de PLI ............................................................................................. 13 
Figura 4 - Resultado no gráfico ...................................................................................... 14 
 
TABELAS 
 
Tabela 1 - Modelo de PL no excel. ................................................................................... 5 
Tabela 2 - Solução sem PLI. ............................................................................................. 6 
Tabela 3 - Solução com PLI ............................................................................................. 7 
Tabela 4 - Primeira tabela LINDO ................................................................................... 7 
Tabela 5 - Segundo tabela LINDO ................................................................................... 8 
Tabela 6 - Primeira Tabela Solução 2 .............................................................................. 9 
Tabela 7 - Segunda Tabela solução 2 ............................................................................... 9 
Tabela 8 - Terceira tabela solução 2 ................................................................................. 9 
Tabela 9 - Primeira tabela solução 3 .............................................................................. 11 
Tabela 10 - Segunda tabela solução 3 ............................................................................ 11 
Tabela 11 - Terceira tabela solução 3 ............................................................................. 11 
1 
 
 
1. INTRODUÇÃO 
A Programação linear é uma ramificação da Pesquisa Operacional, comumente 
conhecida como PO, tem como funcionalidade definir o método utilizado para resolução 
do problema de variáveis de decisão, restrições e maximização ou minimização de 
resultados. 
A programação inteira pode ser entendida como um caso específico da 
Programação linear, onde as variáveis devem ser inteiras (ou ao menos, parte destas 
variáveis). À rigor o nome mais correto a ser utilizado é Programação Linear Inteira. 
Quando todas as variáveis possuírem valores inteiros, o modelo é denominado de 
um problema de programação Linear Inteira Pura, caso contrário, é denominado de 
Programação Inteira Mista. 
Conforme afirma Henrique, Batista, Ramirez, Cavalcante e Oliveira (2011) o uso 
de estratégias para agregar valor a qualquer organização se torna útil. Ou seja, essa opção 
estratégica de análises de situações traz resultados específicos e direcionados para a 
organização. 
Esta pesquisa acadêmica tem caráter exploratório, com base em pesquisas 
bibliográficas na área de exatas e com funcionalidade de abrir o campo de visão e 
possibilitar o interesse e a compreensão do assunto proposto como parte de instrução para 
o curso de Tecnologia em Logística na FATEC, Faculdade de Tecnologia de Mogi das 
Cruzes, com ênfase na disciplina de Métodos quantitativos de Gestão. 
Diante disso, é importante perceber que ao otimizar processos, a empresa tem 
conhecimento de si mesma e ao seu redor, conseguindo resolver seus problemas de forma 
mais consciente e precisa, sem perder tempo diante as infinitas possibilidades. 
 
2. MÉTODOS QUANTITATIVOS DE GESTÃO 
É a mais comum no mercado, e prioriza apontar numericamente a frequência e a 
intensidade em um meio empresarial, (Foco do estudo), para que, decisões precisas sejam 
tomadas com base em dados pré-existentes com a intenção de soluções ótimas, assim 
elevando o aproveitamento e aumentando quaisquer lucros desejados. 
2 
 
Estas medidas são precisas e podem ser úteis para decisões mais acertadas. Neste 
caso, as ferramentas estatísticas devem ser aplicadas com rigor para que haja a 
confiabilidade necessária para, através da amostra, inferirmos resultados sobre os 
interesses desejados na organização. 
O mais comum em grandes empresas é que haja um profissional da área de exatas 
para que calcule com precisão os dados e dispare para sua organização as diretrizes 
necessárias, com isso, os profissionais utilizam programas matemáticos tais como: Excel 
com a funcionalidade solver e o Lindo, para que o processo seja mais inteligente e eficaz. 
Dentro dos Métodos quantitativos encontramos as linhas de estudo, tais como: 
Teoria dos Grafos, arvores, roteirização, caminhos, canto noroeste, etc. todos com o 
intuito de encontrar métodos e maneiras rentáveis de gestão dos negócios. 
Adentro da matéria nos deparamos com programação linear, onde variáveis de 
decisão são influenciadas a convergirem com restrições e identificar possíveis soluções 
para otimização da gestão, onde encontramos a Programação Linear Inteira. 
 
3. PROGRAMAÇÃO LINEAR INTEIRA 
Um problema que for resolvido pela técnica de programação inteira pode ter seu 
resultado diferente de arredondamentos, interferindo assim no resultado geral, a 
programação inteira tem como técnica e particularidade a utilização do “Método Branch 
and Bound” que se baseia na montagem de um diagrama tipo “arvore” em que cada ramo 
é uma opção da solução inteira. 
O método simplex é utilizado em apenas alguns ramos dessa arvore, sendo assim, o 
computador é indispensável para solução. Tem como vantagem o método de programação 
inteira a ideia de resultados mais realistas e exatos,já suas desvantagens se encontram na 
dificuldade de modelagem. 
 
3.1 TIPOS DE MODELAGEM 
LANCHETERMACHER diz que diante de uma série de situações conflitantes e 
concorrentes, é realizado o processo de modelagem da situação ou exaustivas simulações 
nos mais diversos cenários, para estudar de maneira mais profunda o problema. Existem 
basicamente 3 tipos de modelagem são eles: A modelagem física, Analógicas e 
Matemáticas: 
3 
 
O Modelo Físico seria um protótipo reduzido de um objeto como uma aeronave, para 
ter uma visão reduzida ou aumentada do projeto. E serve também como auxiliar para o 
modelo matemático durante projetos muito grandes e complexos. 
O Modelo Análogo é uma representação normalmente em um painel e que nos leva a 
uma conclusão da situação, como uma barra de volume do som da televisão, uma barra 
cheia representa a intensidade máxima e quanto menor a barra menor a intensidade. 
Modelo matemático e mais utilizado principalmente para a PO é o modelo que 
representa as grandezas em formas de variáveis de decisão e a relação entre elas por 
expressões matemáticas. Para um modelo matemático existir é necessário existir 
informações quantificáveis, de maneira que: 
• Seja possível atingir os resultados necessários; 
• O modelo consista com os dados; 
• O modelo possa ser analisado no momento da sua criação. 
Segundo MARTINS, uma vez construído o modelo matemático diversas são as 
maneiras ou áreas que nos auxilia a obtenção da solução como a Programação Linear, 
Programação em Redes, Teoria dos Grafos e a Teoria das Filas. E também diversos 
softwares, como exemplos temos o Solver do Excel, que atua com planilhas eletrônicas, 
o LINDO – Linear Discrete Optimizer e o CPLEX, para problemas de Programação 
Linear e Não Linear e variações, para Simulação o PROMODEL e o ARENA. 
O processo de criação do modelo matemático pode parecer simples, visto que é a 
identificação de cada variável e o relacionamento de cada variável, mas a não 
identificação adequada das variáveis ou o não compreendimento da expressão matemática 
levará à uma solução errada, perdendo tempo, dinheiro e esforço. 
Ao analisar um problema de programação inteira e a sua modelagem, por ser uma 
parte da programação linear, apresenta características parecidas no seu modelo 
matemático, diferenciando apenas quando pelo menos uma variável de decisão é do tipo 
inteira. Uma ideia é resolver como um problema de PL simples, omitir as virgulas e 
aproximando o resultado para a casa mais próxima. Podendo ocorrer os seguintes 
problemas. Nenhum dos pontos vizinhos são viáveis ou o ponto não é a solução ótima de 
programação inteira. Para garantir a otimização, uma busca por todos os valores próximos 
da função objetivo são calculados e é escolhido aquele que apresenta a melhor solução, 
porém, um grande conjunto de variáveis pode tornar o processo exaustivo. 
O Branch and Bounds ajuda com a verificação exaustiva pois é um algoritmo que 
separa as soluções viáveis, tentando o arredondamento para os possíveis números 
4 
 
próximos e criando novos ramos da arvore até a solução tornar-se inviável. Ao final as 
folhas são verificadas e encontrada a solução ótima de programação inteira. 
 
3.2. COMO MODELAR OS PROBLEMAS 
Para iniciar um problema de programação linear é necessário seguir alguns passos, 
e são ele: 
• Encontrar as vaiáveis de decisão; 
• Escrever as restrições; 
• Escrever a Função objetivo; 
• Montar o Modelo de PL. 
 
Exemplo: 
Uma empresa pode desenvolver quatro tipos de atividades: planejamento, 
desenvolvimento, implementação e análise. Tais atividades competem entre si quanto ao 
uso dos recursos espaço, mão-de-obra e insumos diversos. Ele dispõe de 900 metros, 600 
homens-hora e 480 unidades monetária. 
A quantidade necessária de cada recurso para se produzir uma unidade de cada 
atividade é: para planejamento: 7 metros, 6 mão-obra e 2 unidades monetária; para 
desenvolvimento é 8 metros, 6 mão-obra e 8 unidades monetária; para implementação: 3 
metros, 8 mão-obra e 4 unidades monetária; para análise: 5 metros, 5 mão-obra e 2 
unidades monetária. O lucro (em unidades monetárias) esperado pela produção de uma 
unidade de cada atividade é 90 pelo planejamento, 160 pelo desenvolvimento, 40 pela 
implementação e 100 pela análise. 
 
Vamos definir o modelo para encontrar a solução utilizando dos passos descritos 
no início da sessão. 
 
Primeiro Passo, definir as Variáveis de decisões. 
 
x1:Quantidade da atividade de Planejamento; 
x2: Quantidade de atividade de Desenvolvimento; 
x3: Quantidade de atividade de Implementação; 
x4: Quantidade de atividade de Análise. 
5 
 
 
 
Segundo passo, encontrar as restrições: 
 
Disponibilidade da Quantidade de espaço: 7x1+8x2+3x3+5x4 <= 900; 
Disponibilidade da Quantidade de Mão de Obra: 6x1+6x2+8x3+5x4 <= 600; 
Disponibilidade da Quantidade de Insumo: 2x1+8x2+4x3+2x4 <= 480; 
Não negatividade: x1;x2;x3;x4 >=0 e inteiros. 
 
Terceiro Passo, escrever a função objetivo. 
MAX Z = 90x1+160x2+40x3+100x4 
 
MODELO DE PL 
MAX Z = 90x1+160x2+40x3+100x4 
Sujeito a. 
7x1+8x2+3x3+5x4 <= 900 
6x1+6x2+8x3+5x4 <= 600 
2x1+8x2+4x3+2x4 <= 480 
x1;x2;x3;x4 =>0 e inteiros 
 
3.2.1 SOLUÇÃO ATRAVÉS DO SOLVER 
Realizado e montado o modelo de PL inicial iremos resolve-lo através da 
ferramenta SOLVER. 
No Excel montamos a seguinte tabela 1: 
Tabela 1 - Modelo de PL no excel. 
 x1 x2 x3 x4 Restrição sinal disponibilidade 
Espaço 7 8 3 5 0 <= 900 
Mão de obra 6 6 8 5 0 <= 600 
Insumo 2 8 4 2 0 <= 480 
FO 90 160 40 100 R$ - 
Solução 
Fonte: Autores 
E aplicaremos a ferramenta solver indo em dados. 
6 
 
Com o solver aberto iremos definir a função objetivo do problema, depois 
selecionar a área da solução (em verde) e por fim adicionar as restrições como na imagem 
a seguir. 
Figura 1 - SOLVER 
Fonte: Autores 
 
Adicionado as restrições iremos obter os seguintes resultados na tabela 2 
Tabela 2 - Solução sem PLI. 
Fonte: Autores 
Porém, esse não é o resultado real dos problemas, pois não é possível fazer 
42,85714286 de atividade para desenvolvimento (x2) e o mesmo acontece com o processo 
de análise (x4). Por isso aplicados os conceitos de programação linear inteira onde esses 
valores precisam ser completos. 
 x1 x2 x3 x4 restrição sinal disponibilidade 
Espaço 7 8 3 5 685,7142857 <= 900 
Mão de obra 6 6 8 5 600 <= 600 
Insumo 2 8 4 2 480 <= 480 
FO 90 160 40 100 R$ 13.714,29 
Solução 0 42,85714286 0 68,57142857 
7 
 
Para que isso aconteça será acrescentado uma restrição para que a solução seja 
inteira. Vamos ao solver clicamos em adicionar depois selecionamos a área em verde da 
tabela e escolher no sinal o (int) de inteiro e pronto. 
Após isso o solver nos apresenta a solução mais real do problema conforma a 
tabela 3. 
Tabela 3 - Solução com PLI 
 x1 x2 x3 x4 restrição sinal disponibilidade 
Espaço 7 8 3 5 684 <= 900 
Mão de obra 6 6 8 5 598 <= 600 
Insumo 2 8 4 2 480 <= 480 
FO 90 160 40 100 R$ 13.680,00 
Solução 0 43 0 68 
Fonte: Autores 
Sendo assim finalizamos o exercício encontrando a solução mais próxima da 
realidade. 
 
3.2.2 SOLUÇÃO PELO MÉTODO DE BRANCH AND BOUND 
Para resolver com o método do branch and bound iremos utilizar da ferramenta 
LINDO. Temos o seguinte problema: 
Max 3x1+8x2 
s.t. 
3x1+x2<=7 
x1+2x2<=5 
x1 e x2 => 0 e inteiros 
 
A ferramenta LINDO nos mostra a seguinte tabela 4 para a solução do problema. 
Tabela 4 - Primeira tabela LINDO 
ROW (BASIS) X1 X2 SLK 2 SLK 3 BI 
1 ART -3.000 -8.000 0.0000.000 0.000 
2 SLK 2 3.000 1.000 1.000 0.000 7.000 
3 SLK 3 1.000 2.000 0.000 1.000 5.000 
ART ART -3.000 -8.000 0.000 0.000 0.000 
Fonte: Autores 
Pôr a tabela conter valores negativos, precisamos melhora-la para uma solução 
mais ótima. 
8 
 
Após melhora-la temos a seguinte solução. Tabela 5. 
Tabela 5 - Segundo tabela LINDO 
ROW (BASIS) X1 X2 SLK2 SLK3 BI 
1 ART 1.000 0.000 0.000 4.000 20.000 
2 SLK 2 2.500 0.000 1.000 -0.500 4.500 
3 X2 0.500 1.000 0.000 0.500 2.500 
Fonte: Autores 
Essa tabela seria a solução ótima se ela não tivesse um valor incompleto, por isso 
apartir desssa tabela. Iniciaremos nossa arvore, segundo método de bount and bound. 
Notamos que na tabela o valor de x2 = 2,5 e na programação linear inteira não 
podemos utilizar valores incompletos, por isso iremos definir mais dois modos de 
solução: 
Primeiro iremos aproximar o valor incompleto a seus valores inteiros, então 
temos: 
2 <=X2=>3 
X2 precisa ser maior que 3 e menor que 2, nossa árvore fica da seguinte forma: 
 
 
 
 
 
 
 
 
 
 
 
 
 
Z= 20 
X1 = 0 
X2 = 2,5 
Z= ? 
X1 = ? 
X2 = ? 
Z= ? 
X1 = ? 
X2 = ? 
9 
 
Então encontrar os valores para esses novos problemas iremos voltar ao modelo 
de PL e acrescentar cada restrição que na imagem está no quadrado acima da seta. 
Novo modelo adicionado x2<= 2 
Max 3x1+8x2 
s.t. 
3x1+x2<=7 
x1+2x2<=5 
x2<= 2 
Iremos repetir os passos das tabelas do LINDO e encontrar a solução ótima, 
primeira tabela: 
Tabela 6 - Primeira Tabela Solução 2 
ROW (BASIS) X1 X2 SLK2 SLK3 SLK4 BI 
1 ART -3.000 -8.000 0.000 0.000 0.000 0.000 
2 SLK 2 3.000 1.000 1.000 0.000 0.000 7.000 
3 SLK 3 1.000 2.000 0.000 1.000 0.000 5.000 
4 SLK 4 0.000 1.000 0.000 0.000 1.000 2.000 
ART ART -3.000 -8.000 0.000 0.000 0.000 0.000 
Fonte: Autores 
Podemos notar a presença de mais uma variável de folga o SLK 4. 
A tabela contém valores negativos, por isso precisamos melhora-la. Resultado 
após melhora-la tabela 7. 
Tabela 7 - Segunda Tabela solução 2 
ROW (BASIS) X1 X2 SLK2 SLK3 SLK4 BI 
1 ART -3.000 0.000 0.000 0.000 8.000 16.000 
2 SLK 2 3.000 0.000 1.000 0.000 -1.000 5.000 
3 SLK 3 1.000 0.000 0.000 1.000 -2.000 1.000 
4 X2 0.000 1.000 0.000 0.000 1.000 2.000 
Fonte: Autores 
Ainda notamos a presença de valores negativos e continuamos aplicando os 
critérios para melhorar a tabela. A seguir a nova tabela melhorada, tabela 8. 
Tabela 8 - Terceira tabela solução 2 
ROW (BASIS) X1 X2 SLK2 SLK3 SLK 4 BI 
1 ART 0.000 0.000 0.000 3.000 2.000 19.000 
2 SLK 2 0.000 0.000 1.000 -3.000 5.000 2.000 
3 X1 1.000 0.000 0.000 1.000 -2.000 1.000 
4 X2 0.000 1.000 0.000 0.000 1.000 2.000 
Fonte: Autores 
10 
 
Encontramos a solução ótima do novo modelo com uma nova restrição x<=2 
Notamos que não números quebrados na solução, por isso encontramos uma solução mais 
viável para o exercício. 
 
Assim fica nossa arvore: 
 
 
 
 
 
 
 
 
 
 
 
 
Agora precisamos encontrar a solução para X=> 3, aplicamos novamente os 
passos realizados na última solução. 
Novo modelo de PL adicionado a restrição de X=>3 
 
Max 3x1+8x2 
s.t. 
3x1+x2<=7 
x1+2x2<=5 
x2=>3 
 
Após formular o novo modelo, iniciamos novamente o processo de tabelas pela 
ferramenta LINDO, primeira tabela segundo LINDO, tabela 9. 
 
 
Z= 19 
X1 = 1 
X2 = 2 
Z= ? 
X1 = ? 
X2 = ? 
Z= 20 
X1 = 0 
X2 = 2,5 
11 
 
Tabela 9 - Primeira tabela solução 3 
ROW (BASIS) X1 X2 SLK2 SLK 3 SLK 4 BI 
1 ART -3.000 -8.000 0.000 0.000 0.000 0.000 
2 SLK 2 3.000 1.000 1.000 0.000 0.000 7.000 
3 SLK 3 1.000 2.000 0.000 1.000 0.000 5.000 
4 SLK 4 0.000 -1.000 0.000 0.000 1.000 -3.000 
ART ART 0.000 -1.000 0.000 0.000 0.000 -3.000 
Fonte: Autores 
 
Nota-se a presença de números negativos na linha 1ART, por isso sabemos que 
essa tabela não contem a solução do exercício. Aplicamos então os critérios de 
melhoramento de tabela, entrada e saída de uma variável básica e não básica. 
 
E teremos uma nova tabela, tabela 10. 
 
Tabela 10 - Segunda tabela solução 3 
ROW (BASIS) X1 X2 SLK 2 SLK3 SLK 4 BI 
1 ART -3.000 0.000 0.000 0.000 -8.000 24.000 
2 SLK 2 3.000 0.000 1.000 0.000 1.000 4.000 
3 SLK 3 1.000 0.000 0.000 1.000 2.000 -1.000 
4 X2 0.000 1.000 0.000 0.000 -1.000 3.000 
ART ART 1.000 0.000 0.000 0.000 2.000 -1.000 
Fonte: Autores 
 
Contendo valor negativa na linha 1 ART, sabemos que essa ainda não é a solução 
para o problema. Então, continuamos aplicando os critérios de melhoramento. A seguir 
tabela 11 com resultado. 
 
Tabela 11 - Terceira tabela solução 3 
ROW (BASIS) X1 X2 SLK2 SLK3 SLK 4 BI 
1 ART -3.000 0.000 0.000 0.000 -8.000 24.000 
2 SLK 2 3.000 0.000 1.000 0.000 1.000 4.000 
3 SLK 3 1.000 0.000 0.000 1.000 2.000 -1.000 
4 X2 0.000 1.000 0.000 0.000 -1.000 3.000 
ART ART 1.000 0.000 0.000 0.000 2.000 -1.000 
Fonte: Autores 
 
12 
 
Ainda contendo valor negativa na linha 1 ART, sabemos que essa ainda não é a 
solução para o problema. Então, continuamos aplicando critérios de melhoramento. Nova 
tabela. 
Tabela 12 - Quarta tabela solução 3 
ROW (BASIS) X1 X2 SLK2 SLK 3 SLK 4 BI 
1 ART 0.000 0.000 1.000 0.000 -7.000 28.000 
2 X1 1.000 0.000 0.333 0.000 0.333 1.333 
3 SLK 3 0.000 0.000 -0.333 1.000 1.667 -2.333 
4 X2 0.000 1.000 0.000 0.000 -1.000 3.000 
ART ART 0.000 0.000 -0.333 0.000 1.667 -2.333 
Fonte: Autores 
 
Após essa tabela o lindo nos informa que esse modelo é infactível, pois a solução 
demanda de mais disponibilidade a qual o exercício não dispõe 
Figura 2 e 3 - Solução 3, segundo LINDO. 
 
Fonte: Autores 
 
Ou seja, não há solução viável para esse modelo de PL, então ficamos com nossa 
arvore da seguinte maneira. 
 
 
13 
 
 
 
 
 
 
 
 
 
 
 
Com isso, podemos encontrar a solução mais real e viável para a solução do 
modelo de PL, sendo está a de X<= 2 com z* = 19 nos pontos de X1 = 1 e X2 = 2, 
utilizando da programação linear inteira método de Branch and Bound. 
 
3.3 EXEMPLOS DE PROGRAMAÇÃO LINEAR INTEIRA 
Figura 3 - Exemplo de PLI 
 
 
• O exemplo anterior é um problema de programação linear inteira, pois as 
variáveis devem ser inteiras. 
• Na Figura (a) têm-se os pontos que representam as soluções factíveis do 
problema (todosos pontos inteiros que satisfazem as restrições). 
Z= 19 
X1 = 1 
X2 = 2 
Infactível 
Z= 20 
X1 = 0 
X2 = 2,5 
14 
 
• O problema de programação linear (PPL) obtido ao desconsiderarmos as 
restrições de integralidade das variáveis inteiras é conhecido como a relaxação 
linear do PPI (ver Figura (b)). 
• Existem outros tipos de relaxação, como por exemplo, a Relaxação Lagrangiana: 
relaxam-se algumas restrições, consideradas complicadas, incorporando uma 
penalidade na função objetivo; 
Figura 4 - Resultado no gráfico 
 
• Como podemos observar a solução do PPL é sempre maior ou igual à solução do 
PPI, pois o problema relaxado é composto por todas as soluções inteiras e também 
as soluções reais do problema, logo são formadas por um conjunto de soluções 
factíveis mais abrangentes. 
 
4. APLICAÇÕES DA PROGRAMAÇÃO LINEAR INTEIRA 
 Existem áreas bastante abrangentes que utilizam-se da PI. Desde problemas 
relacionados a logística de grandes empresas, até a elaboração de atribuições de 
professores a matérias e horários escolares. 
Na área de logística de transportes para o uso racional de frotas de veículos e de 
roteamento, que são amplamente estudados na área de otimização combinatória, utilizam-
se da técnica branch-and-bound e das variações branch-and-cut, branch-and-price e 
branch-and-cut-and-price. O problema de roteamente do veículos sempre engloba 
restrições de capacidade, bem como problemas com janela de tempo e frota heterogênea. 
 Pode ser aplicada no desenvolvimento de uma aplicaçao para solucionar um 
problema de programação de horários em escolas, sendo modelado matematicamente 
15 
 
como um problema de programação inteira em que há necessidade de considerar os 
requisitos pedagógicos e organizacionais de cada instituição de ensino e restriçoes 
pessoais, e para o processamento da grade horária, sendo necessário cadastro das entradas 
dos professores, disciplinas, cursos, salas e preferências de alocação dos professores. 
Adequa-se a este tipo de programação, principalmente por suas restrições serem dadas a 
um conjunto de perguntas que podem ser respondidas por "sim" ou "não", sendo assim, 
pode se adotar o uso da variável binária. Não só este, como muitos dos problemas podem 
ser solucionados por decisões "Sim-ou-Não" onde 0 e 1 pode representas sim, não ou em 
situação "ou-ou". 
 Casos em que é preciso Otimização Combinatória, que são problemas de decisão 
de sequências, programas e itinerários, que como mencionado anteriormente, muito 
utilizado em roteirização na logística de transportes. Outros exemplos são: O bastante 
conhecido "Problema do Caxeiro Viajante", em que para a quantidade "x" de cidades, 
existem (x-1)! (fatorial) diferentes percursos; Problema de programação de máquinas, 
onde para uma certa quantidade de itens denominados como "n" a serem produzidos em 
cada máquina denominada como "m", existem (n!)m sequencias possíveis. 
 
5. CONSIDERAÇÕES FINAIS 
Conforme pesquisado, a programação linear inteira pode analisar o uso de 
estratégias para qualquer organização, viabilizando escolhas apontando suas soluções e 
por meio de cálculos matemáticos precisos e dados estatísticos trazer resultados 
específicos e direcionados para a organização. 
É importantíssimo que a empresa possua conhecimento de si mesma e ao seu 
redor, para poder aplicar todos os métodos e processos e assim conseguir resolver seus 
problemas de forma precisa, sem perdas rentáveis e produtivas. 
Um profissional conhecedor da área de exatas se faz mais que necessário para que 
todos os dados e processos sejam aplicados com precisão, demonstrando para sua 
organização os caminhos necessários, com o uso de ferramentas como como o Excel, com 
a funcionalidade solver, e o Lindo, para que assim as tomadas de decisões sejam mais 
rápidas, precisas e eficazes. 
Utilizando-se de modelos matemáticos, as empresas podem obter informações 
quantificáveis, de maneira que seja possível atingir os resultados necessários com base 
16 
 
em modelos consistentes com dados e, posteriormente, possa ser analisado e sempre 
consultado. 
Na área de logística de transportes, o uso da programação linear inteira se torna 
eficaz, pois para o uso total de frotas de veículos e de um completo mapeamento de rotas, 
se faz necessários cálculos matemáticos combinados com limites de cargas e obtenção de 
lucros, que são amplamente estudados na área de pesquisa operacional, e utilizam-se de 
técnicas como branch-and-bound e branch-and-price e branch-and-cut-and-price. 
 Também pode ser aplicada em desenvolvimentos ou aplicações para solucionar 
problema simples de agendas corporativas, tais como de uma escola, sendo esses a 
programação de horários, sendo modelado matematicamente como um problema de 
programação inteira em que há necessidade de considerar o tempo de chegada, 
permanência e saída, demanda exigida e disponibilidades diversas e restrições pessoais. 
O grupo concluiu que, para uma performance satisfatória no tempo atuais, 
empresas precisam se adequar e utilizar de ferramentas matemáticas e dados cada vez 
mais precisos, não só empresas, como também conhecer todos os processos a serem 
usados. A obtenção de lucro sempre será o objetivo, contudo, sem um estudo prévio por 
analise de modelos matemáticos e seu uso adequado, fará com que a empresa fique para 
traz em termos de tomada de decisões. O Lindo e o Excel, este último com a opção do 
modelo solver, se tornam essenciais para análises detalhadas, sendo importantes para a 
tomada de decisão ser a mais precisa e eficaz. 
 
 
6. REFERENCIAL BIBLIOGRÁFICO 
ARAUJO, Silvio Alexandre de, 2016, Programação Inteira, 
<http://wiki.icmc.usp.br/images/3/32/Pi_aula_16_11_finalizacaoPI_mari.pdf> acesso 
em 08/06/2017. 
 
DUARTE, Vania Maria do Nascimento, 2016, Pesquisa Quantitativa e Qualitativa, 
<http://monografias.brasilescola.uol.com.br/regras-abnt/pesquisa-quantitativa-
qualitativa.htm> acesso em 11/06/2017. 
 
INSTITUTO PHD, 2015, Pesquisa Quantitativa e Pesquisa Qualitativa: Entenda a 
diferença, <http://www.institutophd.com.br/blog/pesquisa-quantitativa-e-pesquisa-
qualitativa-entenda-a-diferenca/> acesso em 10/06/2017. 
 
17 
 
LANCHTERMACHER, Gerson. Pesquisa Operacional na Tomada de Decisão, 3 Ed. 
Campos Ltda, 2007 
 
Longo, José Humberto, 2004. Técnicas para Programação Inteira e Aplicações em 
Problemas de Roteamento de Veículos, Tese de Doutorado, PUC RIO, 
<https://www.maxwell.vrac.puc-rio.br/6029/6029_1.PDF> acesso em 11/06/2017. 
 
MARTINS, Fernando Augusto Silva. Introdução a pesquisa operacional, Cultura 
Acadêmica, São Paulo, 2011 
 
NOGUEIRA, Fernando 2010, Programação Inteira, UFJF, 
<http://www.ufjf.br/epd015/files/2010/06/ProgramacaoInteira.pdf> acesso em 
10/06/2017. 
P.S. FERREIRA2 , E.W. KARAS3 , F.L. PALUCOSKI4 , A.A. RIBEIRO5, Aplicação 
de Programação Inteira na Distribuição de Encargos Didáticos em Instituições de 
Ensino, Sociedade Brasileira de Matemática Aplicada e Computacional, 2011, 
<http://www.sbmac.org.br/tema/seletas/docs/v12_2/Ferreira_et_all.pdf> acesso em 
10/06/2017. 
UFRGS, Apostila de Pesquisa Operacional, 2011, 
<http://www.producao.ufrgs.br/arquivos/disciplinas/382_Apostila_Pesquisa_Operacion
al_Parte_3.pdf> acesso em 09/06/2017. 
 
VICENTE, Renato, 2014, Métodos Quantitativos, 
<http://www.al.sp.gov.br/StaticFile/ilp/RVicente_MetodosQuantitativos_aula6.pdf> 
acesso em 09/06/2017.