--- title: "Programação Inteira" source: "https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Inteira" wiki: "systems-analysis.info/int" article: "Programação_Inteira" language: "pt" categories: - "Category:Operations research" - "Category:Portuguese" revision_id: 5886 wiki_created_at: 2026-09-06T23:55:25Z wiki_modified_at: 2026-09-06T23:55:25Z downloaded_at: 2026-09-07T23:10:52Z --- # Programação Inteira **Programação Inteira** (**PI**; em inglês: *integer programming, IP*) é um ramo da otimização matemática em que se investigam problemas nos quais algumas ou todas as variáveis devem assumir apenas valores inteiros[\[1\]](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Inteira#cite_note-ru-wiki-ip-1). O caso particular mais estudado é a **programação linear inteira** (**PLI**; em inglês: *integer linear programming, ILP*), onde a [Função objetivo](https://systems-analysis.info/int/Fun%C3%A7%C3%A3o_objetivo "Função objetivo") e as restrições são lineares. Diferentemente da programação linear, na qual as variáveis podem assumir quaisquer valores reais, a exigência de integralidade torna os problemas de PI significativamente mais difíceis de resolver[\[2\]](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Inteira#cite_note-wolsey-book-2). A programação inteira tem ampla aplicação em economia, logística, planejamento de produção e outras áreas onde as variáveis são discretas por natureza (por exemplo, o número de unidades de um produto fabricadas ou o número de trabalhadores)[\[3\]](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Inteira#cite_note-pisaruk-book-3). ## Definição e Terminologia O problema geral de programação linear inteira pode ser formulado da seguinte maneira: Encontrar um vetor $x$ que: maximiza (ou minimiza) $c^{T}x$ sujeito a: $Ax \leq b$ $x \geq 0$ $x \in {\mathbb{Z}}^{n}$ (todos os componentes do vetor $x$ são números inteiros) onde $x$ é o vetor de variáveis, $c$ e $b$ são vetores, e $A$ é a matriz de coeficientes[\[4\]](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Inteira#cite_note-conforti-book-4). Dependendo das restrições sobre as variáveis, distinguem-se os seguintes tipos de problemas: - **Programação inteira pura**: todas as variáveis devem ser inteiras. - **Programação inteira mista** (em inglês: *mixed-integer programming, MIP*): apenas uma parte das variáveis precisa ser inteira. - **Programação binária (0-1)**: as variáveis podem assumir apenas os valores 0 ou 1, o que permite modelar decisões lógicas do tipo "sim/não". ## Propriedades Chave e Complexidade ### Complexidade Computacional O problema de programação linear inteira, no caso geral, é NP-difícil[\[5\]](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Inteira#cite_note-karp-1972-5). Isso significa que não existe um algoritmo conhecido capaz de encontrar a solução ótima exata para um problema de PI arbitrário em tempo polinomial. A complexidade decorre da natureza combinatória do problema, pois o número de soluções inteiras possíveis pode crescer exponencialmente com o aumento do número de variáveis. ### Relação com a Programação Linear (Relaxação LP) Para qualquer problema de PI, é possível formular sua **relaxação linear** — um problema de programação linear (PL), no qual a exigência de integralidade das variáveis é removida. A solução da relaxação LP possui duas propriedades importantes: 1. Ela pode ser encontrada de forma significativamente mais rápida (em tempo polinomial). 2. O valor ótimo da função objetivo da relaxação LP fornece um limite (limite superior para problemas de maximização e limite inferior para minimização) para o valor ótimo do problema inteiro original[\[2\]](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Inteira#cite_note-wolsey-book-2). No entanto, o simples arredondamento da solução fracionária da relaxação LP para os inteiros mais próximos geralmente não leva a uma solução ótima, ou mesmo viável, para o problema inteiro[\[1\]](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Inteira#cite_note-ru-wiki-ip-1). ### Propriedade de Unimodularidade Total Existe uma classe importante de problemas de PLI que são resolvidos com a mesma facilidade que suas relaxações LP. São os problemas em que a matriz de restrições $A$ é **totalmente unimodular** (ou seja, o determinante de qualquer uma de suas submatrizes quadradas é igual a 0, +1 ou −1). Se a matriz $A$ é totalmente unimodular e o vetor $b$ é inteiro, então todos os vértices do poliedro de soluções viáveis da relaxação LP serão automaticamente inteiros. Consequentemente, a solução encontrada pelo método simplex será inteira[\[4\]](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Inteira#cite_note-conforti-book-4). Exemplos desses problemas incluem o problema do transporte e o problema da designação. ## Métodos de Solução Para resolver problemas gerais de PI que não possuem a propriedade de unimodularidade total, foram desenvolvidos métodos exatos baseados em ideias de enumeração implícita. - **Método Branch-and-Bound** (em inglês: *Branch and Bound*) — o principal método exato, baseado na divisão sistemática do conjunto de soluções viáveis em subconjuntos (ramificação) e na eliminação (poda) dos subconjuntos que comprovadamente não contêm a solução ótima. A relaxação LP é usada para avaliar o potencial dos subconjuntos[\[6\]](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Inteira#cite_note-en-wiki-ip-6). - **Método dos Planos de Corte** (método de Gomory; em inglês: *Cutting Plane Method*) — uma abordagem iterativa que adiciona sequencialmente novas restrições lineares ("cortes") ao problema. Esses cortes "cortam" soluções fracionárias da relaxação LP sem remover nenhuma solução inteira viável, aproximando gradualmente a região viável da relaxação LP ao fecho convexo das soluções inteiras[\[6\]](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Inteira#cite_note-en-wiki-ip-6). Solucionadores modernos (solvers) geralmente usam algoritmos híbridos, como o **método Branch-and-Cut** (em inglês: *Branch and Cut*), que combina as vantagens de ambas as abordagens. ## Exemplos e Áreas de Aplicação A programação inteira permite modelar uma variedade de problemas clássicos de otimização combinatória. - *Problema da Mochila*: um problema clássico de programação 0-1, no qual se deve selecionar um conjunto de itens com o maior valor total possível, sem exceder uma restrição de peso total. - *Problema do Caixeiro-Viajante*: o problema de encontrar a rota mais curta que passa por um conjunto de cidades. Pode ser formulado como um problema de programação inteira, onde as variáveis representam a inclusão de arestas de um grafo na rota final. Graças à sua flexibilidade, a PI é uma das ferramentas mais requisitadas em pesquisa operacional e encontra aplicação em áreas como: - **Logística e gerenciamento da cadeia de suprimentos**: otimização de rotas de transporte, localização de armazéns, gestão de estoques. - **Planejamento da produção**: elaboração de cronogramas de produção, alocação de recursos, carregamento de equipamentos. - **Finanças e economia**: formação de carteiras de investimento, orçamento de capital. - **Telecomunicações e energia**: projeto de redes de comunicação, planejamento da operação de unidades de energia. ## Ver também - Programação linear - Método Branch-and-Bound ## Notas 1. ↑ [1.0](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Inteira#cite_ref-ru-wiki-ip_1-0) [1.1](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Inteira#cite_ref-ru-wiki-ip_1-1) "Programação inteira". *Wikipédia*. [1] 2. ↑ [2.0](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Inteira#cite_ref-wolsey-book_2-0) [2.1](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Inteira#cite_ref-wolsey-book_2-1) Wolsey, Laurence A. (2020). *Integer Programming* (2nd ed.). John Wiley & Sons. 3. [↑](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Inteira#cite_ref-pisaruk-book_3-0) Pisaruk, N.N. (2010). *Modelos e métodos de programação inteira mista*. Minsk: BSU. 4. ↑ [4.0](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Inteira#cite_ref-conforti-book_4-0) [4.1](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Inteira#cite_ref-conforti-book_4-1) Conforti, M., Cornuéjols, G., & Zambelli, G. (2014). *Integer Programming*. Springer. 5. [↑](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Inteira#cite_ref-karp-1972_5-0) Karp, Richard M. (1972). "Reducibility among Combinatorial Problems". In: *Complexity of Computer Computations*. Springer. 6. ↑ [6.0](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Inteira#cite_ref-en-wiki-ip_6-0) [6.1](https://systems-analysis.info/int/Programa%C3%A7%C3%A3o_Inteira#cite_ref-en-wiki-ip_6-1) "Integer programming". *Wikipedia*. [2]