Otimização Linear – Problema da Mistura

4 de março de 20264 de março de 2026 dbasamantalekecinskas Otimizacao_linear_Pesquisa_operacional, Sem categoria

Em busca da mistura com menos custo, ou seja, minimizar o preço.

Notação matemática:

\begin{aligned} \text{A variável de decisão } x_j \text{ é a quantidade do ingrediente } j. \\ x &amp;= (x_1, x_2, \dots, x_n)^T \end{aligned}

\begin{aligned} \text{O ingrediente } j \text{ tem custo } C_j. \\ c &amp;= (C_1, C_2, \dots, C_n)^T \end{aligned}

\begin{aligned} \text{Cada ingrediente } j \text{ possui proporção } A_{ij} \text{ do componente } i. \\ A &amp;= \begin{pmatrix} A_{11} &amp; A_{12} &amp; \dots &amp; A_{1n} \\ A_{21} &amp; A_{22} &amp; \dots &amp; A_{2n} \\ \vdots &amp; \vdots &amp; \ddots &amp; \vdots \\ A_{m1} &amp; A_{m2} &amp; \dots &amp; A_{mn} \end{pmatrix} \end{aligned}

\begin{aligned} \text{Cada componente } i \text{ possui limite mínimo } R_i \text{ e máximo } S_i. \\ R &amp;= (R_1, R_2, \dots, R_m)^T \\ S &amp;= (S_1, S_2, \dots, S_m)^T \end{aligned}

objetivo é achar as proporções dos ingredientes que respeitem os limites e chegue ao menor custo.

\begin{aligned} \text{Objetivo: encontrar as proporções } x \text{ que minimizam o custo} \\ \min \quad &amp; c^T x \\ \text{sujeito a} \quad &amp; R \leq A x \leq S \\ &amp; x \geq 0 \end{aligned}

Modelo:

\begin{aligned} \min \quad &amp; c_1 x_1 + c_2 x_2 + \dots + c_n x_n \\[6pt] \text{s.a:} \quad &amp; x_1 + x_2 + \dots + x_n = 1 \\[6pt] &amp; a_{1,1}x_1 + a_{1,2}x_2 + \dots + a_{1,n}x_n \ge r_1 \\ &amp; a_{2,1}x_1 + a_{2,2}x_2 + \dots + a_{2,n}x_n \ge r_2 \\ &amp; \vdots \\ &amp; a_{m,1}x_1 + a_{m,2}x_2 + \dots + a_{m,n}x_n \ge r_m \\[6pt] &amp; a_{1,1}x_1 + a_{1,2}x_2 + \dots + a_{1,n}x_n \le s_1 \\ &amp; a_{2,1}x_1 + a_{2,2}x_2 + \dots + a_{2,n}x_n \le s_2 \\ &amp; \vdots \\ &amp; a_{m,1}x_1 + a_{m,2}x_2 + \dots + a_{m,n}x_n \le s_m \\[6pt] &amp; x_1, x_2, \dots, x_n \ge 0 \end{aligned}

Exemplos de aplicações:

Exemplo 1)

Modelo: Alocação de Entregas com Capacidade

Contexto

Uma organização precisa distribuir entregas para centros regionais.
Cada centro deve ser atendido por exatamente um veículo.
Cada veículo tem um limite máximo de atendimentos.

O objetivo é minimizar a distância total percorrida.

			
from pulp import LpProblem, LpMinimize, LpVariable, lpSum, LpStatus, value, PULP_CBC_CMD
# Criar problema
modelo = LpProblem("Delivery_Allocation_Model", LpMinimize)
veiculos = ['V1', 'V2', 'V3']
locais = ['Norte', 'Sul', 'Leste', 'Oeste', 'Centro']
# Variável binária: y[v,l] = 1 se veículo v atende local l
y = LpVariable.dicts(
    "assign",
    [(v, l) for v in veiculos for l in locais],
    cat="Binary"
)
# Matriz de custos (distâncias)
custo = {
    ('V1', 'Norte'): 15, ('V1', 'Sul'): 20,
    ('V1', 'Leste'): 10, ('V1', 'Oeste'): 25,
    ('V1', 'Centro'): 5,
    ('V2', 'Norte'): 18, ('V2', 'Sul'): 15,
    ('V2', 'Leste'): 12, ('V2', 'Oeste'): 22,
    ('V2', 'Centro'): 8,
    ('V3', 'Norte'): 20, ('V3', 'Sul'): 25,
    ('V3', 'Leste'): 15, ('V3', 'Oeste'): 18,
    ('V3', 'Centro'): 10,
}
# -------------------------
# Função Objetivo
# -------------------------
modelo += lpSum(custo[(v, l)] * y[(v, l)] for v in veiculos for l in locais)
# -------------------------
# Restrição 1:
# Cada local deve ser atendido exatamente uma vez
# -------------------------
for l in locais:
    modelo += lpSum(y[(v, l)] for v in veiculos) == 1
# -------------------------
# Restrição 2:
# Capacidade máxima de atendimentos por veículo
# -------------------------
limite_atendimentos = {'V1': 3, 'V2': 2, 'V3': 3}
for v in veiculos:
    modelo += lpSum(y[(v, l)] for l in locais) <= limite_atendimentos[v]
# Resolver
modelo.solve(PULP_CBC_CMD(msg=False))
# Resultados
print("Status:", LpStatus[modelo.status])
print("Distância total mínima:", value(modelo.objective))
for v in veiculos:
    atendimentos = [l for l in locais if value(y[(v, l)]) > 0.5]
    print(f"{v} atende: {', '.join(atendimentos) if atendimentos else 'Nenhum'}")

		

			
Status: Optimal
Distância total mínima: 63.0
V1 atende: Norte, Leste, Centro
V2 atende: Sul
V3 atende: Oeste

		

Exemplo 2)

custo mínimo para 1Kg de ração com as restrições abaixo de quantidade mínima de proteína e sódio.

Modelo com valores respectivos para Frango/Osso/Trigo, com:

mistura total = 1 kg
proteína mínima
sódio máximo
$x_1, x_2, x_3 \ge 0$ x1,x2,x3≥0

Atenção: os coeficientes como exemplo na tabela (proteína: 0.6/0.2/0.1 e sódio: 0.1/0.05/0.02; limites proteína ≥ 0.4 e sódio ≤ 0.08).

			
import numpy as np
from scipy.optimize import linprog
# -------------------------
# Variáveis de decisão
# x1 = kg Frango, x2 = kg Osso, x3 = kg Trigo
# -------------------------
# Função objetivo: minimizar custo
# min 5x1 + 4x2 + 6x3
c = np.array([5, 4, 6], dtype=float)
# Restrições do tipo A_ub @ x <= b_ub
# 1) Proteína mínima: 0.6x1 + 0.2x2 + 0.1x3 >= 0.4
#    Convertemos para <= multiplicando por -1:
#   -0.6x1 -0.2x2 -0.1x3 <= -0.4
# 2) Sódio máximo: 0.1x1 + 0.05x2 + 0.02x3 <= 0.08
A_ub = np.array([
    [-0.6, -0.2, -0.1],  # proteína (convertida)
    [ 0.1,  0.05, 0.02], # sódio
], dtype=float)
b_ub = np.array([
    -0.4,  # proteína mínima
     0.08, # sódio máximo
], dtype=float)
# Restrição de igualdade: x1 + x2 + x3 = 1 (mistura total)
A_eq = np.array([[1, 1, 1]], dtype=float)
b_eq = np.array([1], dtype=float)
# Limites (não negatividade): x1, x2, x3 >= 0
bounds = [(0, None), (0, None), (0, None)]
# Resolver
res = linprog(
    c=c,
    A_ub=A_ub, b_ub=b_ub,
    A_eq=A_eq, b_eq=b_eq,
    bounds=bounds,
    method="highs"
)
# Resultados
if res.success:
    x1, x2, x3 = res.x
    print("✅ Solução ótima encontrada (custo mínimo)")
    print(f"x1 (Frango) = {x1:.4f} kg")
    print(f"x2 (Osso)   = {x2:.4f} kg")
    print(f"x3 (Trigo)  = {x3:.4f} kg")
    print(f"Custo mínimo = R$ {res.fun:.4f}")
    # Checagem das restrições (opcional)
    proteina = 0.6*x1 + 0.2*x2 + 0.1*x3
    sodio    = 0.1*x1 + 0.05*x2 + 0.02*x3
    print("\n🔎 Checagem:")
    print(f"Total       = {x1 + x2 + x3:.4f} (deve ser 1)")
    print(f"Proteína    = {proteina:.4f} (>= 0.4)")
    print(f"Sódio       = {sodio:.4f} (<= 0.08)")
else:
    print("❌ Não foi possível encontrar solução.")
    print("Motivo:", res.message)
✅ Solução ótima encontrada (custo mínimo)
x1 (Frango) = 0.5000 kg
x2 (Osso)   = 0.5000 kg
x3 (Trigo)  = 0.0000 kg
Custo mínimo = R$ 4.5000
🔎 Checagem:
Total       = 1.0000 (deve ser 1)
Proteína    = 0.4000 (>= 0.4)
Sódio       = 0.0750 (<= 0.08)

		

Otimização Linear – Problema da Ração

3 de março de 20263 de março de 2026 dbasamantalekecinskas Otimizacao_linear_Pesquisa_operacional, Sem categoria

Um dos primeiros problemas utilizando Otimização Linear e métodos de pesquisa operacional.

Problema da Ração é um exemplo típico utilizado como exemplo para Otimização Linear.

Imagina que uma fabrica de ração tenha que produzir a ração animal com 3 ingredientes, como o frango, osso e trigo.

Onde abaixo teríamos um custo, apenas como exemplo, dos 3 ingredientes por Kg:

Preço R$/Kg: Frango = 5 , Osso = 4, Trigo = 6

Sendo assim as variáveis decisão serão a quantidade para cada ingrediente:

Quantidade Kg: Frango = x1, Osso = x2, Trigo = x3

Função Objetivo: Queremos reduzir o custo total de cada ingrediente da ração. Portanto o custo será:

Min 𝑐𝑇𝑥′ =5×1+4×2+6×3

Curiosidade: O resultado da expressão $c to the cap T-th power x prime$ é um escalar obtido pela combinação linear das derivadas das componentes do vetor

$x$ , resultando em: $bold c raised to the bold cap T power bold x prime equals sum from bold i equals 1 to bold n of bold c sub bold i bold x sub bold i prime$

2) Restrições:

Quantidade de cada ingrediente não pode ser negativa e que a produção de pelo menos 1Kg de ração.

x1 + x2+ x3 = 1 (Kg)

x1 > =0

x2 > =0

x3 > =0

Nutriente	Frango (x₁)	Osso (x₂)	Trigo (x₃)	Restrição
Proteína	0.6	0.2	0.1	≥ 0.4
Sódio	0.1	0.05	0.02	≤ 0.08
Preço Kg	5	4	6	= 1 kg

ou seja, restrições são:

Quantidade total: $x_1 + x_2 + x_3 = 1$

Proteína mínima: $0.6x_1 + 0.2x_2 + 0.1x_3 \ge 0.4$

Sódio máximo: $0.1x_1 + 0.05x_2 + 0.02x_3 \le 0.08$

Não negatividade: $x_1, x_2, x_3 \ge 0$

Abaixo está a solução em Python com linprog, Otimização para custo mínimo a cada 1Kg de ração.

			
import numpy as np
from scipy.optimize import linprog
# -------------------------
# Variáveis de decisão
# x1 = kg Frango, x2 = kg Osso, x3 = kg Trigo
# -------------------------
# Função objetivo: minimizar custo
# min 5x1 + 4x2 + 6x3
c = np.array([5, 4, 6], dtype=float)
# Restrições do tipo A_ub @ x <= b_ub
# 1) Proteína mínima: 0.6x1 + 0.2x2 + 0.1x3 >= 0.4
#    Convertemos para <= multiplicando por -1:
#   -0.6x1 -0.2x2 -0.1x3 <= -0.4
# 2) Sódio máximo: 0.1x1 + 0.05x2 + 0.02x3 <= 0.08
A_ub = np.array([
    [-0.6, -0.2, -0.1],  # proteína (convertida)
    [ 0.1,  0.05, 0.02], # sódio
], dtype=float)
b_ub = np.array([
    -0.4,  # proteína mínima
     0.08, # sódio máximo
], dtype=float)
# Restrição de igualdade: x1 + x2 + x3 = 1 (mistura total)
A_eq = np.array([[1, 1, 1]], dtype=float)
b_eq = np.array([1], dtype=float)
# Limites (não negatividade): x1, x2, x3 >= 0
bounds = [(0, None), (0, None), (0, None)]
# Resolver
res = linprog(
    c=c,
    A_ub=A_ub, b_ub=b_ub,
    A_eq=A_eq, b_eq=b_eq,
    bounds=bounds,
    method="highs"
)
# Resultados
if res.success:
    x1, x2, x3 = res.x
    print("✅ Solução ótima encontrada (custo mínimo)")
    print(f"x1 (Frango) = {x1:.4f} kg")
    print(f"x2 (Osso)   = {x2:.4f} kg")
    print(f"x3 (Trigo)  = {x3:.4f} kg")
    print(f"Custo mínimo = R$ {res.fun:.4f}")
    # Checagem das restrições (opcional)
    proteina = 0.6*x1 + 0.2*x2 + 0.1*x3
    sodio    = 0.1*x1 + 0.05*x2 + 0.02*x3
    print("\n🔎 Checagem:")
    print(f"Total       = {x1 + x2 + x3:.4f} (deve ser 1)")
    print(f"Proteína    = {proteina:.4f} (>= 0.4)")
    print(f"Sódio       = {sodio:.4f} (<= 0.08)")
else:
    print("❌ Não foi possível encontrar solução.")
    print("Motivo:", res.message)

		

✅ Solução ótima encontrada (custo mínimo)
x1 (Frango) = 0.5000 kg
x2 (Osso)   = 0.5000 kg
x3 (Trigo)  = 0.0000 kg
Custo mínimo = R$ 4.5000

🔎 Checagem:
Total       = 1.0000 (deve ser 1)
Proteína    = 0.4000 (>= 0.4)
Sódio       = 0.0750 (<= 0.08)

Otimização Linear

13 de fevereiro de 20264 de março de 2026 dbasamantalekecinskas Otimizacao_linear_Pesquisa_operacional

Otimização Linear:

A Programação Linear é um dos pilares da Pesquisa Operacional.

Otimização Linear, ou Programação Linear (PL), é um método matemático para tomar a melhor decisão em um problema, maximizando ou minimizando um objetivo (como lucro ou custo) sujeito a um conjunto de restrições representadas por equações lineares. Ela é aplicada na pesquisa operacional para resolver situações complexas do mundo real, como planejamento de produção, definindo as quantidades ideais de produtos a fabricar para otimizar o lucro, ou criando misturas com o menor custo possível, respeitando a disponibilidade de componentes.

Função Objetivo é linear: min ou max da função linear abaixo.

O atributo alt desta imagem está vazio. O nome do arquivo é image-22.png

Restrições tambem linear: Limitações de recursos (materiais, tempo, mão de obra), expressas como inequações (<= ou >=) ou equações (=) lineares.

s.a.: Ax >= b x>=0

Objetivo: Maximizar o lucro ou minimizar custos, expresso como uma função linear .

O atributo alt desta imagem está vazio. O nome do arquivo é image-23.png

Elementos Principais:

Função Objetivo:Uma função matemática (linear) que expressa o objetivo do problema, como maximizar o lucro ou minimizar o custo.
Variáveis de Decisão:As variáveis que precisam ser determinadas para atingir o objetivo (ex: quantidade de cada produto a ser produzida).
Restrições:Condições que limitam as variáveis de decisão, expressas como igualdades ou desigualdades lineares (ex: disponibilidade de ingredientes, demanda máxima ou mínima de um produto).

Objetivos exemplos:

Ter unico otimizador global.
Ter infinitos otimizadores globais
Ser infactivel.
Ser factivel, mas sem otimizador.

em python podemos utilizar as bibliotecas linprog, mip, pub

1) Unica solução:

Obs: por padrao no linprog bounds = ( 0, None ), que são as restrições da “Unica solução”

2) Infinitas soluções:

Obs.: Aqui as restrições acima estão em A_eq e b_eq

3) Infactivel

4) Ilimitado

Alguns Exemplo de otimizador em python:

Exemplo:

Problema: Maximizar

$Z = 3x + 4y$ Z=3x+4y

s.a. $x + 2y \le 10$ x+2y≤10, $2x + y \le 12$ 2x+y≤12, $x\ge 0$ x≥0, $y\ge 0$ y≥0

			
# prog linear interpretação geometrica
import numpy as np
import matplotlib.pyplot as plt
# grade para x
x = np.linspace(0, 8, 400)
# restrições (em forma y = ...)
y1 = (10 - x) / 2          # x + 2y = 10  -> y = (10 - x)/2
y2 = 12 - 2*x              # 2x + y = 12  -> y = 12 - 2x
plt.figure(figsize=(10, 8))
# linhas das restrições
plt.plot(x, y1, label=r'$x + 2y \leq 10$', linewidth=2)
plt.plot(x, y2, label=r'$2x + y \leq 12$', linewidth=2)
# não-negatividade (eixos)
plt.axvline(0, linewidth=2)  # x = 0
plt.axhline(0, linewidth=2)  # y = 0
# região viável: abaixo das duas retas e acima de y=0
y_feasible = np.minimum(y1, y2)
y_feasible = np.maximum(y_feasible, 0)
plt.fill_between(x, 0, y_feasible, alpha=0.25, label='Região viável')
# vértices (calculados/confirmados)
# Interseção das retas:
# x + 2y = 10
# 2x + y = 12  -> solução: x=14/3, y=8/3
vertices = [
    (0, 0),
    (0, 5),             # quando x=0 na 1ª restrição: 2y=10 -> y=5 (e satisfaz a 2ª)
    (14/3, 8/3),         # interseção
    (6, 0)              # quando y=0 na 2ª restrição: 2x=12 -> x=6 (e satisfaz a 1ª)
]
# função objetivo (max)
def Z(x, y):
    return 3*x + 4*y
# plotar vértices e anotar valor da função objetivo
for (vx, vy) in vertices:
    plt.plot(vx, vy, 'ko', markersize=8)
    plt.annotate(
        f'({vx:.2f}, {vy:.2f})\nZ={Z(vx, vy):.2f}',
        xy=(vx, vy),
        xytext=(vx + 0.25, vy + 0.25)
    )
# destacar o ótimo
best = max(vertices, key=lambda p: Z(p[0], p[1]))
plt.plot(best[0], best[1], 'k*', markersize=14, label='Ótimo')
plt.xlim(-0.5, 8)
plt.ylim(-0.5, 8)
plt.xlabel('x')
plt.ylabel('y')
plt.grid(alpha=0.3)
plt.legend()
plt.title(f'Visão Geométrica: ótimo no vértice ({best[0]:.2f}, {best[1]:.2f})')
plt.show()
print("Vértice ótimo:", best, "com Z =", Z(best[0], best[1]))

		

Samanta Lekecinskas – Data Science e Machine Learning

Data Science e Machine Learning

Otimizacao_linear_Pesquisa_operacional