Programação Linear Aplicada · Capítulo 6 · Encerramento
Modelagem, métodos de solução e aplicações
Objetivos de aprendizagem
6.1 / Programação Inteira
Ao longo da disciplina, a Programação Linear permitiu organizar decisões de produção, transporte e alocação de recursos. Seus modelos combinam variáveis, função objetivo e restrições lineares. Uma hipótese importante é a divisibilidade: as variáveis podem assumir valores fracionários.
Essa hipótese é adequada para toneladas, litros e horas de operação. Porém, uma resposta como 3,6 caminhões ou 2,33 máquinas não representa diretamente uma decisão executável. Quando a decisão exige unidades indivisíveis, precisamos impor a integralidade.
Definição
Na Programação Linear Inteira, algumas ou todas as variáveis devem assumir valores inteiros. A função objetivo e as restrições permanecem lineares; muda o domínio das variáveis e, com ele, o conjunto de soluções admissíveis.
O conjunto inteiro está contido na região viável contínua. Por isso, o ótimo contínuo pode deixar de ser admissível e o Simplex, isoladamente, não assegura uma solução inteira. Este capítulo encerra a disciplina conectando a modelagem já estudada a decisões quantitativas e decisões do tipo sim ou não.
6.2 / Programação Inteira
Todas as variáveis de decisão são inteiras. Exemplo: quantidades de máquinas de dois tipos, x₁, x₂ ∈ ℤ≥0.
Combina variáveis inteiras e contínuas. Exemplo: número de caminhões n ∈ ℤ≥0 e carga q ≥ 0, em toneladas, com q ≤ Cn.
As variáveis assumem 0 ou 1. Exemplo: y = 1 se uma instalação for aberta; y = 0 caso contrário. É um caso particular da PI.
Os coeficientes cⱼ representam contribuições ao objetivo; aᵢⱼ são consumos ou relações técnicas; bᵢ são limites. O conjunto I identifica as variáveis que exigem integralidade. Se I contém todas as variáveis, a PI é pura; se contém apenas parte delas, é mista. Restrições de igualdade e de mínimo também podem aparecer.
6.3 / Programação Inteira
Uma empresa produz equipamentos A e B, vendidos em unidades indivisíveis. Cada unidade utiliza dois recursos limitados. O objetivo é maximizar o lucro do período. Os valores são didáticos e as quantidades de recursos usam unidades compatíveis com a tabela.
| Informação | A | B | Disponibilidade |
|---|---|---|---|
| Recurso 1 | 2 | 1 | 7 |
| Recurso 2 | 1 | 2 | 7 |
| Lucro unitário (R$) | 5 | 4 | — |
Definimos x₁ como o número de equipamentos A e x₂ como o número de equipamentos B produzidos no período.
Trata-se de uma PI pura: ambas as variáveis são inteiras não negativas. Os limites de recursos continuam sendo restrições lineares. Não precisamos alterar a forma da função objetivo para representar a indivisibilidade.
6.4 / Programação Inteira
A relaxação linear retira temporariamente a exigência de integralidade, mantendo todas as outras restrições. Assim, podemos aplicar o método gráfico ou o Simplex.
No exemplo, a interseção das restrições ativas satisfaz 2x₁ + x₂ = 7 e x₁ + 2x₂ = 7. Subtraindo as equações, x₁ = x₂; substituindo, 3x₁ = 7.
Os demais vértices são (0; 0), (3,5; 0) e (0; 3,5), com lucros 0, 17,5 e 14. Logo, o ótimo contínuo é 21. Ele não é uma solução admissível para equipamentos indivisíveis.
O papel dos limites
Na maximização, o ótimo da relaxação é um limite superior para o ótimo inteiro. Uma solução inteira viável fornece um limite inferior. Na minimização, os sentidos se invertem.
Isso decorre da inclusão entre conjuntos viáveis: retirar a integralidade amplia as possibilidades de escolha. Se a solução ótima da relaxação já for inteira, ela também será ótima para o problema inteiro.
6.5 / Programação Inteira
Arredondar (7/3; 7/3) para (2; 2) produz uma solução viável: os dois recursos têm consumo 6, inferior ao limite 7. O lucro, entretanto, é apenas 18.
A combinação (3; 1) consome 7 unidades do recurso 1 e 5 do recurso 2. Seu lucro é 5(3) + 4(1) = 19, superior ao resultado arredondado.
| Alternativa | x₁ | x₂ | Z | Situação |
|---|---|---|---|---|
| Relaxação | 7/3 | 7/3 | 21 | Ótima contínua; não inteira |
| Arredondamento | 2 | 2 | 18 | Viável; não ótima |
| Candidata inteira | 3 | 1 | 19 | Viável; otimalidade demonstrada a seguir |
| Arredondamento para cima | 3 | 3 | 27 | Inviável: ambos os consumos são 9 |
6.6 / Programação Inteira
O método combina relaxações lineares e uma busca organizada em subproblemas. Ramificar significa dividir as possibilidades inteiras. Limitar significa usar o valor ótimo de cada relaxação para verificar se vale a pena continuar a busca. A melhor solução inteira conhecida é chamada de incumbente.
A raiz tem solução (7/3; 7/3), com limite superior 21. Como há variáveis fracionárias, precisamos ramificar.
Todo valor inteiro de x₁ satisfaz x₁ ≤ 2 ou x₁ ≥ 3. Criamos A e B acrescentando uma dessas condições às restrições originais. Nenhuma solução inteira é perdida.
Em A, x₁ ≤ 2: o ótimo relaxado é (2; 2,5), com Z = 20; a variável x₂ ainda é fracionária. Em B, x₁ ≥ 3: o ótimo é (3; 1), com Z = 19. Como é inteiro, B é encerrado e essa solução torna-se a incumbente.
Não podemos encerrar A: seu limite 20 ainda supera o lucro 19 já alcançado.
Os dois filhos herdam x₁ ≤ 2 e todas as restrições originais. A1, com x₂ ≤ 2, tem ótimo (2; 2), Z = 18. A2, com x₂ ≥ 3, tem ótimo (1; 3), Z = 17. Ambos são inteiros e inferiores à incumbente. Encerramos os dois nós.
No exemplo, todos os nós finais foram encerrados por integralidade; os valores também permitem comparar os seus resultados com a incumbente. Nenhum ramo em aberto pode superar 19.
A ordem de exploração pode variar sem alterar o ótimo comprovado. Em problemas grandes, a árvore pode crescer muito; implementações combinam seleção de nós, heurísticas e cortes. A compreensão exigida aqui é a lógica de ramificar, estabelecer limites e comprovar a solução, como discutido por Trick e pelo MIT.
6.7 / Programação Inteira
Uma empresa precisa transportar pelo menos 18 toneladas em uma viagem. Pode contratar veículos pequenos, com capacidade de 4 toneladas e custo de R$ 40 por viagem, ou grandes, com capacidade de 7 toneladas e custo de R$ 65. Há veículos suficientes dos dois tipos e é permitido deixar parte da capacidade ociosa. Quantos contratar para minimizar o custo?
Sejam x₁ a quantidade de veículos pequenos e x₂ a quantidade de veículos grandes. Como não se contrata uma fração de veículo, ambas as variáveis são inteiras não negativas.
A desigualdade é de mínimo: a capacidade contratada deve atender ou superar 18 toneladas. Exigir igualdade impediria combinações válidas com capacidade ociosa.
O custo por tonelada de capacidade é R$ 10 no veículo pequeno e aproximadamente R$ 9,29 no grande. Sem integralidade, a melhor opção seria usar somente o grande: x₁ = 0 e x₂ = 18/7, com custo 1170/7 ≈ R$ 167,14. Por ser uma minimização, esse valor é um limite inferior para o ótimo inteiro.
Fixada a quantidade de veículos grandes, escolhemos o menor número de pequenos que atende à carga. Contratar mais pequenos apenas aumentaria o custo.
| Grandes x₂ | Pequenos x₁ mínimos | Capacidade (t) | Custo (R$) |
|---|---|---|---|
| 0 | 5 | 20 | 200 |
| 1 | 3 | 19 | 185 |
| 2 | 1 | 18 | 170 |
| 3 | 0 | 21 | 195 |
Para x₂ ≥ 3, o custo é pelo menos R$ 195, mesmo sem veículos pequenos, e cresce com x₂. Portanto, nenhum caso omitido pode melhorar R$ 170. A tabela, junto desse limite, comprova a otimalidade.
Decisão ótima
Contratar um veículo pequeno e dois grandes: capacidade total de 18 toneladas, custo mínimo de R$ 170 e nenhuma capacidade ociosa.
Exemplo elaborado para este capítulo, com valores didáticos.
6.8 / Programação Inteira
Para escolher projetos, abrir instalações ou contratar fornecedores, usamos yⱼ = 1 quando a decisão é adotada e yⱼ = 0 caso contrário. A variável representa uma escolha, não uma quantidade física contínua.
| Relação | Restrição binária | Interpretação |
|---|---|---|
| Dependência | yB ≤ yA | B exige A; A não exige B |
| No máximo uma | yA + yB ≤ 1 | Pode escolher nenhuma ou apenas uma |
| Exatamente uma | yA + yB = 1 | Uma escolha é obrigatória |
| Pelo menos uma | yA + yB ≥ 1 | Ambas também são permitidas |
| Vincular produção e abertura | 0 ≤ q ≤ Uy | Sem abertura, q = 0; U é um limite válido |
No último caso, q pode ser contínua e y é binária, formando um modelo misto. O valor U deve ser um limite justificável para a produção; não deve ser escolhido arbitrariamente grande.
6.9 / Programação Inteira
Uma pequena empresa dispõe de R$ 6 mil e avalia dois investimentos. Cada um pode ser realizado integralmente ou não ser realizado. Os valores são didáticos; os benefícios podem ser somados.
| Investimento | Custo (R$ mil) | Benefício estimado (R$ mil) |
|---|---|---|
| A — equipamento | 4 | 7 |
| B — divulgação | 3 | 5 |
Definimos y₁ = 1 se o investimento A for realizado e 0 caso contrário; y₂ = 1 se o investimento B for realizado e 0 caso contrário. Não são quantidades de equipamentos ou ações: cada variável indica apenas a escolha da alternativa apresentada.
Os números 4 e 3 são os custos da tabela. Multiplicar cada custo pela respectiva variável inclui o gasto quando a escolha é sim (1) e o elimina quando a escolha é não (0). O número 6 é o orçamento disponível. Já 7 e 5 são os benefícios usados na função objetivo.
| (y₁, y₂) | Escolha | Gasto | Benefício | Situação |
|---|---|---|---|---|
| (0, 0) | Nenhum | 0 | 0 | Viável |
| (1, 0) | Somente A | 4 | 7 | Viável e ótima |
| (0, 1) | Somente B | 3 | 5 | Viável |
| (1, 1) | A e B | 7 | 12 | Inviável: gasto maior que 6 |
Solução e interpretação
Escolher somente A: (y₁, y₂) = (1, 0). O benefício máximo viável é R$ 7 mil, o gasto é R$ 4 mil e sobram R$ 2 mil do orçamento. A combinação com maior benefício bruto, A + B, é descartada porque não cabe no orçamento.
6.10 / Programação Inteira
Uma empresa pode adquirir um software e contratar um treinamento específico para ele. O treinamento só pode ser contratado se o software também for adquirido. O orçamento é de R$ 3 mil. Para simplificar, os benefícios estimados abaixo são incrementais e aditivos: o benefício do treinamento se soma ao do software.
| Decisão | Custo (R$ mil) | Benefício adicional (R$ mil) |
|---|---|---|
| Adquirir software | 2 | 3 |
| Contratar treinamento | 1 | 4 |
Seja y₁ = 1 se o software for adquirido e y₂ = 1 se o treinamento for contratado; caso contrário, cada variável vale 0. Os custos 2 e 1 vêm da tabela, e o limite 3 vem do orçamento.
A condição y₂ ≤ y₁ traduz “treinamento exige software”. Se y₁ = 0, ela obriga y₂ = 0. Se y₁ = 1, permite y₂ igual a 0 ou 1. Portanto, comprar o software não obriga a contratar o treinamento.
| (y₁, y₂) | Escolha | Gasto | Benefício | Situação |
|---|---|---|---|---|
| (0, 0) | Nenhuma | 0 | 0 | Viável |
| (1, 0) | Somente software | 2 | 3 | Viável |
| (0, 1) | Somente treinamento | 1 | 4* | Inviável: viola y₂ ≤ y₁ |
| (1, 1) | Software e treinamento | 3 | 7 | Viável e ótima |
*O valor 4 é apenas a avaliação algébrica da função objetivo nessa combinação. Ela não representa uma alternativa permitida, pois o treinamento depende da aquisição do software.
Solução e interpretação
Adquirir o software e contratar o treinamento: (y₁, y₂) = (1, 1). O gasto é R$ 3 mil e o benefício total estimado é R$ 7 mil.
Os dois exemplos foram elaborados para este capítulo. A seguir, a mesma abordagem é ampliada para três projetos.
6.11 / Programação Inteira
Uma organização dispõe de R$ 5 mil para investir em três projetos independentes. Cada projeto pode ser executado uma única vez, integralmente, ou não ser escolhido. Os benefícios estimados são aditivos e não há dependências entre os projetos.
| Projeto | Investimento (R$ mil) | Benefício (R$ mil) |
|---|---|---|
| A | 4 | 7 |
| B | 3 | 5 |
| C | 2 | 4 |
Use y₁, y₂ e y₃ para os projetos A, B e C, respectivamente: yⱼ = 1 se o projeto for selecionado e yⱼ = 0 caso contrário.
Com três variáveis binárias, há apenas 2³ = 8 possibilidades. Podemos conferir todas elas diretamente.
| (y₁, y₂, y₃) | Investimento | Benefício | Situação |
|---|---|---|---|
| (0, 0, 0) | 0 | 0 | Viável |
| (1, 0, 0) | 4 | 7 | Viável |
| (0, 1, 0) | 3 | 5 | Viável |
| (0, 0, 1) | 2 | 4 | Viável |
| (1, 1, 0) | 7 | 12 | Inviável |
| (1, 0, 1) | 6 | 11 | Inviável |
| (0, 1, 1) | 5 | 9 | Viável e ótima |
| (1, 1, 1) | 9 | 16 | Inviável |
A melhor combinação viável é (0; 1; 1): executar os projetos B e C. O investimento total é R$ 5 mil e o benefício máximo é R$ 9 mil. Embora A tenha o maior benefício individual, a combinação B + C apresenta resultado melhor dentro do orçamento.
Exemplo elaborado para este capítulo, com valores didáticos. A seguir, o caso California amplia a mesma lógica para quatro decisões e acrescenta dependências e exclusão entre alternativas.
6.12 / Programação Inteira
No caso didático de Hillier e Lieberman, a empresa considera construir fábricas e depósitos em Los Angeles e San Francisco. Deseja maximizar o valor presente líquido (VPL) dos investimentos, respeitando um orçamento de US$ 10 milhões. As fábricas podem ser construídas nas duas cidades, mas haverá no máximo um depósito; cada depósito exige uma fábrica na mesma cidade.
| Variável | Decisão se xⱼ = 1 | VPL (US$ milhões) | Capital (US$ milhões) |
|---|---|---|---|
| x₁ | Fábrica em Los Angeles | 9 | 6 |
| x₂ | Fábrica em San Francisco | 5 | 3 |
| x₃ | Depósito em Los Angeles | 6 | 5 |
| x₄ | Depósito em San Francisco | 4 | 2 |
Todas as variáveis são binárias: xⱼ = 0 indica não realizar o investimento. Os valores abaixo seguem o caso discutido no texto-base da conversa.
Se x₁ = 0, então x₃ = 0; se x₂ = 0, então x₄ = 0. Uma fábrica pode existir sem depósito. A desigualdade x₃ + x₄ ≤ 1 permite não construir depósito algum; usar igualdade mudaria o enunciado.
Quatro variáveis binárias geram 2⁴ = 16 combinações. Aplicando as dependências, a exclusão entre depósitos e o orçamento, restam as cinco alternativas viáveis abaixo. Para um modelo pequeno, a enumeração completa comprova o ótimo.
| (x₁, x₂, x₃, x₄) | Capital | VPL | Decisão |
|---|---|---|---|
| (0, 0, 0, 0) | 0 | 0 | Nenhuma instalação |
| (1, 0, 0, 0) | 6 | 9 | Fábrica LA |
| (0, 1, 0, 0) | 3 | 5 | Fábrica SF |
| (0, 1, 0, 1) | 5 | 9 | Fábrica e depósito SF |
| (1, 1, 0, 0) | 9 | 14 | Duas fábricas — ótima |
A fábrica com depósito em Los Angeles custaria 11 e viola o orçamento; as duas fábricas com depósito em San Francisco também custariam 11. As duas fábricas com depósito em Los Angeles custariam 14. As demais combinações violam dependências ou a condição de no máximo um depósito.
6.13 / Programação Inteira
Selecionar projetos com orçamento limitado; usar variáveis binárias e restrições de dependência.
Decidir quais instalações abrir e quanto transportar; combinar custos fixos, capacidades e demandas.
Designar pessoas a turnos ou tarefas; respeitar cobertura, disponibilidade e limites de jornada.
Selecionar rotas, alocar aeronaves e representar quantidades indivisíveis de veículos.
Essas aplicações retomam a mesma disciplina de modelagem: definir unidades, explicitar hipóteses e validar restrições. Uma resposta computacional só é útil se o modelo representar corretamente as decisões reais.
A sensibilidade de um modelo inteiro requer cuidado: pequenas alterações nos dados podem mudar discretamente as escolhas. Não se deve aplicar automaticamente ao modelo inteiro a interpretação dos preços-sombra da relaxação. Compare cenários resolvendo novamente o modelo.
6.14 / Programação Inteira
Monte primeiro o exemplo de produção em uma planilha. Use as fórmulas abaixo no Excel em português; em outras configurações, os nomes e separadores podem mudar.
| Célula / intervalo | Conteúdo |
|---|---|
| B2:C2 | Quantidades x₁ e x₂; valores iniciais 0 |
| B3:C3 | Lucros unitários: 5 e 4 |
| D3 | =SOMARPRODUTO(B2:C2;B3:C3) |
| B5:C5 / E5 | Consumos 2 e 1 / limite 7 |
| B6:C6 / E6 | Consumos 1 e 2 / limite 7 |
| D5 | =SOMARPRODUTO($B$2:$C$2;B5:C5) |
| D6 | =SOMARPRODUTO($B$2:$C$2;B6:C6) |
Em outra aba, use B2:E2 para x₁,…,x₄; B3:E3 para os VPLs (9; 5; 6; 4); B4:E4 para os capitais (6; 3; 5; 2). Em F3 calcule =SOMARPRODUTO(B2:E2;B3:E3), e em F4 =SOMARPRODUTO(B2:E2;B4:E4).
Maximize F3 alterando B2:E2. Adicione F4 ≤ 10, D2 ≤ B2, E2 ≤ C2, e uma célula auxiliar F5 = D2+E2 com F5 ≤ 1. Defina B2:E2 como binárias (bin). O resultado esperado é (1; 1; 0; 0), com VPL 14.
Se a execução terminar por limite de tempo ou tolerância, diferencie “melhor solução encontrada” de “ótimo comprovado”. Consulte o guia do Solver da Microsoft.
6.15 / Programação Inteira
O capítulo integra a modelagem de Hillier e Lieberman e Taha com a apresentação de métodos de Trick e os materiais do MIT. O exemplo de produção foi desenvolvido didaticamente; o caso California é uma adaptação do exemplo desses autores, com os coeficientes do texto-base. A numeração dos capítulos dos livros varia conforme a edição.
HILLIER, Frederick S.; LIEBERMAN, Gerald J. Introdução à Pesquisa Operacional. McGraw-Hill / AMGH. Capítulo de Programação Inteira, especialmente decisões binárias e o caso California Manufacturing Company. Na edição digitalizada discutida em aula: capítulo 11, seção 11.1.
TAHA, Hamdy A. Operations Research: An Introduction. Pearson. Capítulos de modelagem e programação inteira. Consulte a edição adotada na disciplina.
TRICK, Michael A. A Tutorial on Integer Programming. Carnegie Mellon University, material de curso dos anos 1990. Seções de modelagem, relação com PL e Branch and Bound.
ORLIN, James; NASRABADI, Ebrahim. 15.053 — Optimization Methods in Management Science. Primavera de 2013. Aulas 10–14: formulação inteira, Branch and Bound e cortes.
Encerramento da disciplina
Modelar é traduzir uma decisão em variáveis, objetivos, restrições e domínios coerentes. Resolver é buscar a melhor alternativa admissível e compreender o alcance da comprovação. Interpretar é transformar a resposta matemática em uma decisão justificável. A Programação Inteira amplia esse percurso para unidades indivisíveis e escolhas do tipo sim ou não.