Modelos Clássicos de Programação Linear - Aplicações

 

Aplicação e Formulação dos Modelos Clássicos de Programação Linear

A programação linear é uma das técnicas matemáticas de otimização mais amplamente utilizadas em contextos empresariais e organizacionais. A sua versatilidade permite modelar uma grande variedade de problemas reais, convertendo-os em formulações matemáticas que podem ser resolvidas de forma eficiente. Este artigo explora os principais modelos clássicos de programação linear, as suas características, formulações matemáticas e aplicações práticas.

Introdução à Programação Linear

A programação linear (PL) é uma técnica para otimizar uma função objetivo linear sujeita a restrições lineares. A estrutura geral de um problema de programação linear é:

Maximizar/Minimizar: Z = c₁x₁ + c₂x₂ + ... + cₙxₙ

Sujeito a:
    a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤/=/≥ b₁
    a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤/=/≥ b₂
    ...
    aₘ₁x₁ + aₘ₂x₂ + ... + aₘₙxₙ ≤/=/≥ bₘ
    x₁, x₂, ..., xₙ ≥ 0

A programação linear é resolúvel de forma eficiente através de algoritmos como o método simplex ou métodos de ponto interior, tornando-a uma ferramenta prática mesmo para problemas de grande escala.

Vamos explorar os principais modelos clássicos de programação linear, excluindo os modelos de rede (que serão abordados em outro artigo).

1. Modelo de Mistura (Blending)

Descrição

O modelo de mistura é utilizado quando diferentes ingredientes ou recursos devem ser combinados para criar produtos finais que atendam a determinados requisitos de qualidade, custo ou composição.

Aplicações

• Mistura de combustíveis em refinarias
• Formulação de alimentos e rações
• Preparação de ligas metálicas
• Composição de portfólios financeiros
• Mistura de fertilizantes

Formulação Matemática

Índices e Conjuntos:

• i = ingredientes disponíveis (i = 1, 2, ..., m)
• j = características ou requisitos (j = 1, 2, ..., n)

Variáveis de Decisão:

• xᵢ = quantidade do ingrediente i a ser utilizada na mistura

Parâmetros:

• cᵢ = custo por unidade do ingrediente i
• aᵢⱼ = quantidade da característica j por unidade do ingrediente i
• bⱼᵐⁱⁿ = nível mínimo requerido da característica j
• bⱼᵐᵃˣ = nível máximo permitido da característica j
• dᵢᵐⁱⁿ = disponibilidade mínima do ingrediente i
• dᵢᵐᵃˣ = disponibilidade máxima do ingrediente i

Função Objetivo (minimizar custo):

Min Z = Σ cᵢxᵢ  (i = 1, 2, ..., m)

Restrições:

1. Requisitos de características:

   bⱼᵐⁱⁿ ≤ Σ aᵢⱼxᵢ ≤ bⱼᵐᵃˣ  (j = 1, 2, ..., n)
   

2. Disponibilidade de ingredientes:

   dᵢᵐⁱⁿ ≤ xᵢ ≤ dᵢᵐᵃˣ  (i = 1, 2, ..., m)
   

3. Volume total da mistura (opcional):

   Σ xᵢ = V  (onde V é o volume total desejado)
   

4. Não-negatividade:

   xᵢ ≥ 0  (i = 1, 2, ..., m)
   

Exemplo Prático

Uma refinaria precisa produzir 10.000 litros de gasolina premium com octanagem mínima de 92. Dispõe de três tipos de componentes:

Componente	Octanagem	Custo (€/litro)	Disponibilidade (litros)
A	85	0,60	8.000
B	90	0,80	6.000
C	98	1,10	4.000

Formulação:

Min Z = 0,60xₐ + 0,80xᵦ + 1,10xᶜ
Sujeito a:
85xₐ + 90xᵦ + 98xᶜ ≥ 92(xₐ + xᵦ + xᶜ)  [Restrição de octanagem]
xₐ + xᵦ + xᶜ = 10.000                  [Volume total]
xₐ ≤ 8.000                            [Disponibilidade de A]
xᵦ ≤ 6.000                            [Disponibilidade de B]
xᶜ ≤ 4.000                            [Disponibilidade de C]
xₐ, xᵦ, xᶜ ≥ 0                         [Não-negatividade]

Simplificando a restrição de octanagem:

85xₐ + 90xᵦ + 98xᶜ ≥ 92xₐ + 92xᵦ + 92xᶜ
-7xₐ - 2xᵦ + 6xᶜ ≥ 0

2. Modelo de Planeamento de Produção

Descrição

O modelo de planejamento da produção ajuda a determinar quanto produzir de cada produto ao longo de um horizonte de tempo, considerando recursos limitados, demanda e custos.

Aplicações

• Planejamento industrial
• Programação de manufatura
• Agendamento de produção sazonal
• Dimensionamento de lotes de produção

Formulação Matemática

Índices e Conjuntos:

• i = produtos (i = 1, 2, ..., n)
• j = recursos (j = 1, 2, ..., m)
• t = períodos de tempo (t = 1, 2, ..., T)

Variáveis de Decisão:

• xᵢₜ = quantidade do produto i a ser produzida no período t
• Iᵢₜ = estoque do produto i ao final do período t

Parâmetros:

• pᵢ = lucro unitário do produto i
• cᵢ = custo de produção unitário do produto i
• hᵢ = custo de manutenção de estoque unitário do produto i
• aᵢⱼ = quantidade do recurso j necessária para produzir uma unidade do produto i
• bⱼₜ = disponibilidade do recurso j no período t
• dᵢₜ = demanda do produto i no período t

Função Objetivo (maximizar lucro total):

Max Z = Σ Σ (pᵢxᵢₜ - hᵢIᵢₜ)  (i = 1, 2, ..., n; t = 1, 2, ..., T)

Restrições:

1. Balanço de estoque:

   Iᵢ(t-1) + xᵢₜ - Iᵢₜ = dᵢₜ  (i = 1, 2, ..., n; t = 1, 2, ..., T)
   

2. Restrições de capacidade:

   Σ aᵢⱼxᵢₜ ≤ bⱼₜ  (j = 1, 2, ..., m; t = 1, 2, ..., T)
   

3. Não-negatividade:

   xᵢₜ, Iᵢₜ ≥ 0  (i = 1, 2, ..., n; t = 1, 2, ..., T)
   

Exemplo Prático

Uma empresa fabrica dois produtos usando dois recursos (máquinas e mão de obra) em dois períodos. Os dados são:

Produto	Lucro (€/unid.)	Custo estoque (€/unid.)	Recurso 1 (h/unid.)	Recurso 2 (h/unid.)
1	30	5	3	2
2	40	6	4	3

Período	Disponibilidade Recurso 1 (h)	Disponibilidade Recurso 2 (h)	Demanda Produto 1	Demanda Produto 2
1	200	180	20	10
2	180	160	30	20

Formulação:

Max Z = 30x₁₁ + 30x₁₂ + 40x₂₁ + 40x₂₂ - 5I₁₁ - 5I₁₂ - 6I₂₁ - 6I₂₂

Sujeito a:

x₁₁ - I₁₁ = 20                 [Balanço de estoque P1T1]

I₁₁ + x₁₂ - I₁₂ = 30           [Balanço de estoque P1T2]

x₂₁ - I₂₁ = 10                 [Balanço de estoque P2T1]

I₂₁ + x₂₂ - I₂₂ = 20           [Balanço de estoque P2T2]

3x₁₁ + 4x₂₁ ≤ 200              [Recurso 1, período 1]

2x₁₁ + 3x₂₁ ≤ 180              [Recurso 2, período 1]

3x₁₂ + 4x₂₂ ≤ 180              [Recurso 1, período 2]

2x₁₂ + 3x₂₂ ≤ 160              [Recurso 2, período 2]

x₁₁, x₁₂, x₂₁, x₂₂, I₁₁, I₁₂, I₂₁, I₂₂ ≥ 0   [Não-negatividade]

3. Modelo de Atribuição

Descrição

O modelo de atribuição é utilizado para designar recursos (pessoas, máquinas, equipamentos) a tarefas ou atividades, onde cada recurso pode ser atribuído a exatamente uma tarefa e cada tarefa requer exatamente um recurso.

Aplicações

• Alocação de funcionários a funções
• Designação de máquinas a trabalhos
• Atribuição de veículos a rotas
• Alocação de equipes a projetos

Formulação Matemática

Índices e Conjuntos:

• i = recursos (i = 1, 2, ..., n)
• j = tarefas (j = 1, 2, ..., n) (geralmente o número de recursos e tarefas é igual)

Variáveis de Decisão:

• xᵢⱼ = 1 se o recurso i for atribuído à tarefa j; 0 caso contrário

Parâmetros:

• cᵢⱼ = custo (ou tempo, eficiência, etc.) de atribuir o recurso i à tarefa j

Função Objetivo (minimizar custo total):

Min Z = Σ Σ cᵢⱼxᵢⱼ  (i = 1, 2, ..., n; j = 1, 2, ..., n)

Restrições:

1. Cada recurso é atribuído a exatamente uma tarefa:

   Σ xᵢⱼ = 1  (i = 1, 2, ..., n)
   

2. Cada tarefa recebe exatamente um recurso:

   Σ xᵢⱼ = 1  (j = 1, 2, ..., n)
   

3. Restrições de variáveis binárias:

   xᵢⱼ ∈ {0, 1}  (i, j = 1, 2, ..., n)
   

Nota: Embora o problema de atribuição seja tecnicamente um problema de programação inteira binária, ele tem a propriedade especial de que quando resolvido como um problema de programação linear (relaxando as restrições de integralidade), a solução ótima será naturalmente inteira.

Exemplo Prático

Quatro funcionários (1-4) devem ser designados a quatro tarefas (A-D). A matriz de custos (em euros) é:

Funcionário	Tarefa A	Tarefa B	Tarefa C	Tarefa D
1	14	5	8	7
2	2	12	6	5
3	7	8	3	9
4	2	4	6	10

Formulação:

Min Z = 14x₁ₐ + 5x₁ᵦ + 8x₁ᶜ + 7x₁ᵈ + 2x₂ₐ + 12x₂ᵦ + 6x₂ᶜ + 5x₂ᵈ + 
       7x₃ₐ + 8x₃ᵦ + 3x₃ᶜ + 9x₃ᵈ + 2x₄ₐ + 4x₄ᵦ + 6x₄ᶜ + 10x₄ᵈ

Sujeito a:

x₁ₐ + x₁ᵦ + x₁ᶜ + x₁ᵈ = 1   [Cada funcionário 1 recebe uma tarefa]

x₂ₐ + x₂ᵦ + x₂ᶜ + x₂ᵈ = 1   [Cada funcionário 2 recebe uma tarefa]

x₃ₐ + x₃ᵦ + x₃ᶜ + x₃ᵈ = 1   [Cada funcionário 3 recebe uma tarefa]

x₄ₐ + x₄ᵦ + x₄ᶜ + x₄ᵈ = 1   [Cada funcionário 4 recebe uma tarefa]

x₁ₐ + x₂ₐ + x₃ₐ + x₄ₐ = 1   [Tarefa A recebe um funcionário]

x₁ᵦ + x₂ᵦ + x₃ᵦ + x₄ᵦ = 1   [Tarefa B recebe um funcionário]

x₁ᶜ + x₂ᶜ + x₃ᶜ + x₄ᶜ = 1   [Tarefa C recebe um funcionário]

x₁ᵈ + x₂ᵈ + x₃ᵈ + x₄ᵈ = 1   [Tarefa D recebe um funcionário]

xᵢⱼ ∈ {0, 1} para todos i, j

4. Modelo de Carregamento ou Knapsack (Mochila)

Descrição

O modelo da mochila (knapsack) envolve selecionar um subconjunto de itens com diferentes valores e pesos, de forma a maximizar o valor total sem exceder a capacidade de uma "mochila" ou recurso limitado.

Aplicações

• Seleção de projetos de investimento
• Carregamento de contêineres ou veículos
• Corte de materiais
• Orçamento de capital

Formulação Matemática (Mochila 0-1)

Índices e Conjuntos:

• i = itens disponíveis (i = 1, 2, ..., n)

Variáveis de Decisão:

• xᵢ = 1 se o item i for selecionado; 0 caso contrário

Parâmetros:

• vᵢ = valor do item i
• wᵢ = peso (ou consumo de recurso) do item i
• W = capacidade total disponível

Função Objetivo (maximizar valor total):

Max Z = Σ vᵢxᵢ  (i = 1, 2, ..., n)

Restrições:

1. Restrição de capacidade:

   Σ wᵢxᵢ ≤ W  (i = 1, 2, ..., n)
   

2. Restrições de variáveis binárias:

   xᵢ ∈ {0, 1}  (i = 1, 2, ..., n)
   

Nota: A versão 0-1 do problema da mochila é um problema de programação inteira binária. Para formulá-lo como programação linear, pode-se relaxar a restrição binária para 0 ≤ xᵢ ≤ 1, embora isso possa levar a soluções fracionárias.

Exemplo Prático

Uma empresa de investimentos tem €10 milhões para investir em cinco projetos diferentes. Cada projeto tem um retorno esperado e um requisito de capital:

Projeto	Retorno esperado (milhões €)	Requisito de capital (milhões €)
1	4,2	3,0
2	5,0	4,0
3	3,8	2,5
4	6,0	5,0
5	3,5	2,0

Formulação:

Max Z = 4,2x₁ + 5,0x₂ + 3,8x₃ + 6,0x₄ + 3,5x₅

Sujeito a:

3,0x₁ + 4,0x₂ + 2,5x₃ + 5,0x₄ + 2,0x₅ ≤ 10,0   [Restrição de capital]

xᵢ ∈ {0, 1}  para i = 1, 2, 3, 4, 5

5. Modelo de Dieta ou Nutrição

Descrição

O modelo de dieta busca determinar a combinação ótima de alimentos que satisfaça requisitos nutricionais específicos ao menor custo possível.

Aplicações

• Planejamento de dietas para hospitais
• Formulação de rações para animais
• Planejamento nutricional em instituições
• Suplementação dietética otimizada

Formulação Matemática

Índices e Conjuntos:

• i = alimentos disponíveis (i = 1, 2, ..., n)
• j = nutrientes considerados (j = 1, 2, ..., m)

Variáveis de Decisão:

• xᵢ = quantidade do alimento i a ser incluída na dieta

Parâmetros:

• cᵢ = custo por unidade do alimento i
• aᵢⱼ = quantidade do nutriente j por unidade do alimento i
• bⱼᵐⁱⁿ = requisito mínimo diário do nutriente j
• bⱼᵐᵃˣ = limite máximo recomendado do nutriente j
• dᵢᵐⁱⁿ = consumo mínimo recomendado do alimento i (opcional)
• dᵢᵐᵃˣ = consumo máximo recomendado do alimento i (opcional)

Função Objetivo (minimizar custo total):

Min Z = Σ cᵢxᵢ  (i = 1, 2, ..., n)

Restrições:

1. Requisitos nutricionais:

   bⱼᵐⁱⁿ ≤ Σ aᵢⱼxᵢ ≤ bⱼᵐᵃˣ  (j = 1, 2, ..., m)
   

2. Limites de consumo (se aplicáveis):

   dᵢᵐⁱⁿ ≤ xᵢ ≤ dᵢᵐᵃˣ  (i = 1, 2, ..., n)
   

3. Não-negatividade:

   xᵢ ≥ 0  (i = 1, 2, ..., n)
   

Exemplo Prático

Um nutricionista precisa planejar uma dieta diária com três alimentos, satisfazendo requisitos mínimos de proteínas, vitaminas e calorias:

Alimento	Custo (€/unid.)	Proteínas (g/unid.)	Vitaminas (mg/unid.)	Calorias (kcal/unid.)
Alimento 1	2,00	8	3	120
Alimento 2	3,50	15	2	180
Alimento 3	1,80	5	4	90

Requisitos diários:

• Proteínas: mínimo 70g
• Vitaminas: mínimo 20mg
• Calorias: entre 800 e 1200 kcal

Formulação:

Min Z = 2,00x₁ + 3,50x₂ + 1,80x₃

Sujeito a:

8x₁ + 15x₂ + 5x₃ ≥ 70             [Restrição de proteínas]

3x₁ + 2x₂ + 4x₃ ≥ 20              [Restrição de vitaminas]

120x₁ + 180x₂ + 90x₃ ≥ 800        [Restrição mínima de calorias]

120x₁ + 180x₂ + 90x₃ ≤ 1200       [Restrição máxima de calorias]

x₁, x₂, x₃ ≥ 0                    [Não-negatividade]

6. Modelo de Corte e Empacotamento

Descrição

O modelo de corte e empacotamento procura determinar como cortar materiais maiores (bobinas, chapas, barras) em peças menores para atender a pedidos específicos, minimizando o desperdício ou o número de itens maiores utilizados.

Aplicações

• Corte de papel, tecido, metal, madeira
• Empacotamento de itens em contentores
• Programação de comprimentos em máquinas de corte
• Indústrias de vidro, aço, têxtil e móveis

Formulação Matemática (Modelo de Padrões de Corte)

Índices e Conjuntos:

• i = tipos de peças menores demandadas (i = 1, 2, ..., m)
• j = padrões de corte possíveis (j = 1, 2, ..., n)

Variáveis de Decisão:

• xⱼ = número de vezes que o padrão de corte j é utilizado

Parâmetros:

• aᵢⱼ = número de peças do tipo i produzidas pelo padrão de corte j
• dᵢ = demanda de peças do tipo i
• cⱼ = custo associado ao uso do padrão j (geralmente relacionado ao desperdício)

Função Objetivo (minimizar custo total ou desperdício):

Min Z = Σ cⱼxⱼ  (j = 1, 2, ..., n)

Restrições:

1. Satisfação da demanda:

   Σ aᵢⱼxⱼ ≥ dᵢ  (i = 1, 2, ..., m)
   

2. Não-negatividade:

   xⱼ ≥ 0  (j = 1, 2, ..., n)
   

3. Integralidade (opcional, torna o problema de programação inteira):

   xⱼ inteiro  (j = 1, 2, ..., n)
   

Exemplo Prático

Uma indústria produz barras de aço de 10 metros e precisa cortá-las para atender à procura/pedido de barras com comprimentos menores:

• 30 barras de 2 metros
• 40 barras de 3 metros
• 20 barras de 4 metros

Padrões de corte possíveis em uma barra de 10 metros:

• Padrão 1: 5 barras de 2 metros (sem desperdício)
• Padrão 2: 3 barras de 3 metros + 0,5 metro de desperdício
• Padrão 3: 2 barras de 4 metros + 1 barra de 2 metros (sem desperdício)
• Padrão 4: 2 barras de 3 metros + 2 barras de 2 metros (sem desperdício)
• Padrão 5: 1 barra de 4 metros + 2 barras de 3 metros (sem desperdício)

Formulação:

Min Z = x₁ + x₂ + x₃ + x₄ + x₅   [Minimizar o número total de barras de 10m]

Sujeito a:

5x₁ + 0x₂ + 1x₃ + 2x₄ + 0x₅ ≥ 30  [Procura de barras de 2m]

0x₁ + 3x₂ + 0x₃ + 2x₄ + 2x₅ ≥ 40  [Procura de barras de 3m]

0x₁ + 0x₂ + 2x₃ + 0x₄ + 1x₅ ≥ 20  [Procura de barras de 4m]

x₁, x₂, x₃, x₄, x₅ ≥ 0 e inteiros