Programmazione lineare: risolvere problemi di ottimizzazione reali

I responsabili delle operazioni affrontano una sfida ricorrente: troppe decisioni, troppi vincoli e nessun modo ovvio per trovare la soluzione migliore. Una rete di distribuzione deve minimizzare i costi del carburante su decine di tratte rispettando finestre di consegna, capacità dei veicoli e orari degli autisti.

Questi due problemi condividono una struttura matematica. Quando obiettivi e vincoli possono essere espressi come relazioni lineari, stai lavorando con un problema di programmazione lineare. Ci interessa la programmazione lineare perché trova soluzioni ottimali quando lavori con risorse limitate e requisiti in competizione.

Ciò che rende potente la programmazione lineare è la sua garanzia: se esiste una soluzione ammissibile, l'algoritmo troverà quella ottimale. Ovviamente, le applicazioni reali raramente si adattano perfettamente agli esempi da manuale, ma comprendere l'impianto di base ti aiuta a riconoscere quando l'ottimizzazione può sostituire i tentativi a tentoni.

Questa guida ti porta dalle basi fino a implementazioni pratiche in Python. Passeremo da semplici problemi a due variabili che puoi visualizzare geometricamente a scenari complessi che richiedono soluzioni algoritmiche. Capirai sia la teoria matematica che rende possibile l'ottimizzazione, sia le competenze pratiche per implementare le soluzioni in autonomia.

Che cos'è la programmazione lineare?

La programmazione lineare ottimizza una funzione obiettivo lineare soggetta a vincoli lineari. In un progetto di instradamento delle consegne su cui ho lavorato, l'obiettivo era minimizzare la distanza totale percorsa rispettando vincoli come la capacità dei veicoli e le finestre orarie di consegna.

Comprendere la struttura di base

Ogni problema di programmazione lineare ha tre componenti: variabili decisionali, una funzione obiettivo e vincoli.

Le variabili decisionali rappresentano le scelte che stai facendo. Nei problemi di instradamento, variabili binarie possono indicare quale veicolo visita quale località. Nella pianificazione della produzione, le variabili possono rappresentare le quantità da produrre.

La funzione obiettivo definisce cosa stai ottimizzando. Deve essere una combinazione lineare delle variabili decisionali. I vincoli definiscono regole e limitazioni del tuo problema. Possono essere di tre tipi: uguaglianze, disuguaglianze minori o uguali e disuguaglianze maggiori o uguali.

from scipy.optimize import linprog

c = [10, 15]
A_ub = [[1, 0], [0, 1]]
b_ub = [100, 80]
A_eq = [[1, 1]]
b_eq = [150]
bounds = [(0, None), (0, None)]

result = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, 
                 bounds=bounds, method='highs')

print(f"Optimal solution: Truck 1 = {result.x[0]:.1f}, Truck 2 = {result.x[1]:.1f}")
print(f"Total cost: ${result.fun:.2f}")Offerto da

Il codice qui sopra minimizza il costo totale per due variabili decisionali, soggette a limiti individuali e a un requisito di copertura totale. I coefficienti dell'obiettivo [10, 15] rappresentano il costo per unità, i vincoli di disuguaglianza limitano l'intervallo di ciascuna variabile e il vincolo di uguaglianza garantisce la copertura totale.

Interpretazione geometrica

Comprendere la programmazione lineare geometricamente ha trasformato il mio modo di pensare all'ottimizzazione. Ogni vincolo definisce un semispazio, e la loro intersezione forma la regione ammissibile. Questa regione è sempre un politopo convesso, il che significa che qualsiasi segmento tra due punti interni rimane al suo interno.

Ecco l'intuizione cruciale: le soluzioni ottimali si trovano sempre ai vertici della regione ammissibile. Muoversi lungo uno spigolo migliora l'obiettivo o non lo cambia, quindi continui a muoverti finché non raggiungi un angolo. Questa proprietà rende efficienti gli algoritmi di programmazione lineare.

import numpy as np
import matplotlib.pyplot as plt

x = np.linspace(0, 8, 400)
y1 = (10 - x) / 2
y2 = 12 - 2*x

plt.figure(figsize=(10, 8))
plt.plot(x, y1, 'r-', label='x + 2y ≤ 10', linewidth=2)
plt.plot(x, y2, 'b-', label='2x + y ≤ 12', linewidth=2)

y_feasible = np.minimum(y1, y2)
y_feasible = np.maximum(y_feasible, 0)
plt.fill_between(x, 0, y_feasible, where=(y_feasible >= 0), 
                 alpha=0.3, color='green', label='Feasible region')

vertices = [(0, 0), (0, 5), (14/3, 8/3), (6, 0)]
for v in vertices:
    plt.plot(v[0], v[1], 'ko', markersize=10)
    obj_value = 3*v[0] + 4*v[1]
    plt.annotate(f'({v[0]:.1f}, {v[1]:.1f})\nObj: {obj_value:.1f}',
                 xy=v, xytext=(v[0]+0.3, v[1]+0.3))

plt.xlim(-0.5, 8)
plt.ylim(-0.5, 8)
plt.xlabel('x')
plt.ylabel('y')
plt.legend()
plt.grid(True, alpha=0.3)
plt.title('Geometric View: Optimal Solution at Vertex (4.7, 2.7)')
plt.show()Offerto da

Questa visualizzazione mostra la soluzione ottimale al vertice (4,7; 2,7) dove si intersecano due vincoli. La convessità della regione ammissibile garantisce l'assenza di “valli nascoste” in cui gli algoritmi potrebbero bloccarsi, assicurando che gli ottimi locali coincidano con quelli globali.

Trasformare problemi reali

La parte più difficile non è risolvere la matematica, ma tradurre problemi caotici in formulazioni pulite. Definire variabili e vincoli spesso richiede più tempo che eseguire l'ottimizzazione stessa.

Definire le variabili decisionali richiede di individuare le scelte fondamentali. Per il routing, potresti usare variabili binarie per l'assegnazione veicolo-località, o aggiungere variabili continue per l'ordine delle visite per semplificare i vincoli.

Costruire i vincoli significa tradurre le regole di business in disuguaglianze. Questo fa emergere ipotesi implicite. Quando un manager dice "ogni sede ha bisogno di una consegna", significa esattamente una o almeno una? Questi dettagli cambiano completamente la formulazione.

Ecco un esempio di formulazione usando PuLP:

from pulp import *

prob = LpProblem("Food_Bank_Routing", LpMinimize)

trucks = ['Truck_A', 'Truck_B', 'Truck_C']
centers = ['North', 'South', 'East', 'West', 'Central']

x = LpVariable.dicts("route", 
                     [(i, j) for i in trucks for j in centers],
                     cat='Binary')

distances = {
    ('Truck_A', 'North'): 15, ('Truck_A', 'South'): 20,
    ('Truck_A', 'East'): 10, ('Truck_A', 'West'): 25,
    ('Truck_A', 'Central'): 5,
    ('Truck_B', 'North'): 18, ('Truck_B', 'South'): 15,
    ('Truck_B', 'East'): 12, ('Truck_B', 'West'): 22,
    ('Truck_B', 'Central'): 8,
    ('Truck_C', 'North'): 20, ('Truck_C', 'South'): 25,
    ('Truck_C', 'East'): 15, ('Truck_C', 'West'): 18,
    ('Truck_C', 'Central'): 10,
}

prob += lpSum([distances[i, j] * x[i, j] 
               for i in trucks for j in centers])

for j in centers:
    prob += lpSum([x[i, j] for i in trucks]) == 1

max_stops = {'Truck_A': 3, 'Truck_B': 2, 'Truck_C': 3}
for i in trucks:
    prob += lpSum([x[i, j] for j in centers]) <= max_stops[i]

prob.solve()

print(f"Status: {LpStatus[prob.status]}")
print(f"Total distance: {value(prob.objective)} miles")
for i in trucks:
    route = [j for j in centers if value(x[i, j]) == 1]
    print(f"{i} visits: {', '.join(route)}")Offerto da

La formulazione sopra usa variabili binarie per le assegnazioni camion-centro, minimizza la distanza totale, garantisce che ogni centro riceva esattamente una consegna e rispetta i limiti di capacità dei camion.

Schemi classici offrono modelli pronti. Il diet problem minimizza i costi rispettando i requisiti nutrizionali. I problemi di trasporto minimizzano i costi di spedizione. Questo si è applicato direttamente alla mia sfida di routing. Riconoscere questi pattern accelera la formulazione, perché raramente stai risolvendo problemi davvero inediti.

La programmazione lineare trova soluzioni ottimali ai vertici delle regioni ammissibili definite dai vincoli. Immagine dell'autore

Metodi di soluzione e approcci algoritmici

Capire come funzionano gli algoritmi ha cambiato il mio modo di apprezzare la chiamata a linprog(). Non sono scatole nere, ma procedure matematiche eleganti.

Algoritmo del simplesso

L' algoritmo del simplesso, sviluppato da George Dantzig nel 1947, è il punto di partenza. La sua intuizione: attraversare sistematicamente da un vertice a quello adiacente, migliorando sempre l'obiettivo, finché non si raggiunge l'ottimo.

L'algoritmo mantiene un tableau ed esegue operazioni di pivot per muoversi tra i vertici. Ogni iterazione migliora l'obiettivo o determina l'ottimalità selezionando un elemento pivot e aggiornando tramite operazioni di riga.

from scipy.optimize import linprog
import numpy as np

c = [-3, -2]
A_ub = [[2, 1], [2, 3], [3, 1]]
b_ub = [18, 42, 24]
bounds = [(0, None), (0, None)]

result = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method='highs')

print(f"Optimal solution: x1 = {result.x[0]:.2f}, x2 = {result.x[1]:.2f}")
print(f"Maximum value: {-result.fun:.2f}")
print(f"Iterations: {result.nit}")Offerto da

Il codice sopra mostra come risolvere un problema di massimizzazione con il metodo del simplesso negando i coefficienti dell'obiettivo. Il solver si muove sistematicamente tra i vertici della regione ammissibile definita dai vincoli, raggiungendo la soluzione ottimale in poche iterazioni. Nei problemi più grandi, il simplesso può trovare l'ottimo in molte meno mosse del numero di vertici ammissibili, spesso in meno di 20 iterazioni anche con migliaia di possibilità.

Metodi a punti interni

Mentre il simplesso percorre i bordi, i metodi a punti interni navigano all'interno della regione ammissibile. Per grandi problemi di ottimizzazione di portafoglio con centinaia di asset, il simplesso può diventare lento mentre i metodi a punti interni risolvono in pochi secondi.

Il vantaggio chiave è la complessità in tempo polinomiale. L'algoritmo di Karmarkar (1984) ha reso pratici i metodi a punti interni, bilanciando il miglioramento dell'obiettivo con il restare lontani dai bordi dei vincoli. Solver moderni come Gurobi selezionano automaticamente tra simplesso e punti interni in base alle caratteristiche del problema.

Metodo grafico per due variabili

Per i problemi a due variabili, li risolvo sempre prima graficamente. Costruisce un'intuizione che si trasferisce a dimensioni superiori. Traccia i vincoli, individua la regione ammissibile e trova quale vertice ottimizza l'obiettivo.

from scipy.optimize import linprog

c = [-30, -40]
A_ub = [[2, 1], [1, 2]]
b_ub = [100, 80]
bounds = [(0, None), (0, None)]

result = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method='highs')

print(f"Bread loaves: {result.x[0]:.0f}")
print(f"Cakes: {result.x[1]:.0f}")
print(f"Maximum profit: ${-result.fun:.0f}")Offerto da

Questo problema di produzione di una panetteria massimizza il profitto di pane e torte, soggetto ai limiti di ore di forno e decorazione. La soluzione rivela quale punto d'angolo è ottimale geometricamente, rendendo concreto il comportamento “salta tra vertici” dell'algoritmo.

Applicazioni nei settori

La programmazione lineare applica lo stesso impianto matematico per risolvere problemi in ambiti anche molto diversi.

Manifattura e produzione

La pianificazione della produzione è stata la mia prima applicazione seria. Il problema del mix produttivo determina le quantità da fabbricare, con variabili che rappresentano la produzione, obiettivi che massimizzano il profitto e vincoli che catturano le limitazioni di risorse.

from pulp import *

products = ['Phone', 'Tablet', 'Laptop']

profits = {'Phone': 120, 'Tablet': 200, 'Laptop': 350}
assembly_time = {'Phone': 2, 'Tablet': 3, 'Laptop': 5}
testing_time = {'Phone': 1, 'Tablet': 1.5, 'Laptop': 2}

assembly_available = 500
testing_available = 200
min_production = {'Phone': 50, 'Tablet': 30, 'Laptop': 20}

model = LpProblem("Production_Planning", LpMaximize)
production = LpVariable.dicts("produce", products, lowBound=0, cat='Integer')

model += lpSum([profits[p] * production[p] for p in products])
model += lpSum([assembly_time[p] * production[p] for p in products]) <= assembly_available
model += lpSum([testing_time[p] * production[p] for p in products]) <= testing_available

for p in products:
    model += production[p] >= min_production[p]

model.solve()

print(f"Status: {LpStatus[model.status]}")
for p in products:
    print(f"{p}: {production[p].varValue:.0f} units")
print(f"Total profit: ${value(model.objective):,.0f}")Offerto da

Il modello sopra ottimizza la produzione di elettronica su tre linee di prodotto, bilanciando capacità di assemblaggio e collaudo con i requisiti minimi di produzione.

I problemi di miscelazione (blending) ottimizzano combinazioni che rispettano specifiche al costo minimo, ad esempio miscelando alimenti per soddisfare requisiti nutrizionali minimizzando il costo.

Trasporti e logistica

Il problema di trasporto è un altro esempio molto studiato. La struttura classica ha sorgenti con offerte e destinazioni con domande, minimizzando il costo totale di spedizione.

warehouses = ['Warehouse_A', 'Warehouse_B', 'Warehouse_C']
supply = {'Warehouse_A': 300, 'Warehouse_B': 400, 'Warehouse_C': 200}

customers = ['Customer_1', 'Customer_2', 'Customer_3', 'Customer_4']
demand = {'Customer_1': 200, 'Customer_2': 150, 'Customer_3': 250, 'Customer_4': 200}

costs = {
    ('Warehouse_A', 'Customer_1'): 8,  ('Warehouse_A', 'Customer_2'): 6,
    ('Warehouse_A', 'Customer_3'): 10, ('Warehouse_A', 'Customer_4'): 7,
    ('Warehouse_B', 'Customer_1'): 9,  ('Warehouse_B', 'Customer_2'): 12,
    ('Warehouse_B', 'Customer_3'): 8,  ('Warehouse_B', 'Customer_4'): 11,
    ('Warehouse_C', 'Customer_1'): 14, ('Warehouse_C', 'Customer_2'): 7,
    ('Warehouse_C', 'Customer_3'): 10, ('Warehouse_C', 'Customer_4'): 12,
}

model = LpProblem("Transportation", LpMinimize)

routes = [(w, c) for w in warehouses for c in customers]
shipments = LpVariable.dicts("ship", routes, lowBound=0)

model += lpSum([costs[i, j] * shipments[i, j] for (i, j) in routes])

for w in warehouses:
    model += lpSum([shipments[w, c] for c in customers]) <= supply[w]

for c in customers:
    model += lpSum([shipments[w, c] for w in warehouses]) >= demand[c]

model.solve()Offerto da

I problemi di flusso su rete generalizzano il trasporto a grafi con nodi di trasbordo. Ho letto che le compagnie aeree lo usano ampiamente per la pianificazione degli equipaggi e l'instradamento degli aeromobili.

Servizi finanziari e sanità

Nelle applicazioni finanziarie, il capital budgeting seleziona i progetti che massimizzano il rendimento soggetti a vincoli di budget:

projects = {
    'Project_A': {'return': 25000, 'cost': 100000, 'staff': 5},
    'Project_B': {'return': 30000, 'cost': 150000, 'staff': 7},
    'Project_C': {'return': 20000, 'cost': 80000, 'staff': 4},
}

budget = 300000
staff_available = 15

model = LpProblem("Capital_Budgeting", LpMaximize)
select = LpVariable.dicts("select", projects.keys(), cat='Binary')

model += lpSum([projects[p]['return'] * select[p] for p in projects])
model += lpSum([projects[p]['cost'] * select[p] for p in projects]) <= budget
model += lpSum([projects[p]['staff'] * select[p] for p in projects]) <= staff_available

model.solve()Offerto da

I sistemi sanitari affrontano infinite sfide di ottimizzazione. Ho fatto consulenza su un problema di programmazione dei turni in una clinica che assegnava infermieri ai turni rispettando requisiti di competenze ed equilibrio del carico di lavoro.

Applicazioni nelle tecnologie moderne

La programmazione lineare compare anche inaspettatamente all'interno del machine learning. La selezione delle feature può essere formulata come minimizzazione dell'errore soggetta a vincoli di sparsità. Il cloud computing la usa per allocare risorse su sistemi distribuiti.

Complessità computazionale e prestazioni

La complessità conta quando i problemi passano dagli esempi giocattolo ai sistemi in produzione.

Complessità del simplesso

Il simplesso ha una complessità affascinante. Ha un caso peggiore esponenziale ma ottime prestazioni medie. Casi patologici come il cubo di Klee-Minty lo costringono a esaminare ogni vertice, ma i problemi tipici ne esplorano solo una piccola frazione, scalando approssimativamente in modo quadratico.

L'ho verificato risolvendo problemi generati casualmente di dimensioni crescenti:

import time
import numpy as np
from scipy.optimize import linprog

def benchmark_simplex(num_vars, num_constraints):
    c = np.random.randn(num_vars)
    A_ub = np.random.randn(num_constraints, num_vars)
    b_ub = np.random.rand(num_constraints) * 10
    
    start = time.time()
    result = linprog(c, A_ub=A_ub, b_ub=b_ub, method='simplex')
    elapsed = time.time() - start
    
    return elapsed, result.nit

problem_sizes = [(10, 20), (50, 100), (100, 200), (200, 400)]

for n_vars, n_const in problem_sizes:
    times, iterations = [], []
    for _ in range(10):
        t, it = benchmark_simplex(n_vars, n_const)
        times.append(t)
        iterations.append(it)
    print(f"{n_vars}x{n_const}: {np.mean(times):.4f}s, {np.mean(iterations):.1f} iterations")Offerto da

I miei benchmark hanno mostrato che raddoppiare la dimensione del problema aumentava il tempo di meno di 4 volte, confermando un comportamento quasi polinomiale per distribuzioni tipiche.

Miglioramenti delle prestazioni

I solver moderni raggiungono prestazioni notevoli grazie a preprocessing, elaborazione parallela e selezione automatica degli algoritmi. Il preprocessing può ridurre la dimensione del problema del 30% o più automaticamente prima della risoluzione.

La degenerazione si verifica quando più vincoli sono attivi all'ottimo, potenzialmente causando ciclaggio. Mi è capitato quando due tratte avevano costi identici. I solver usano tecniche di perturbazione per evitare il ciclaggio, anche se i problemi degeneri si risolvono più lentamente.

Instabilità numerica emerge in problemi mal scalati. Mescolare importi monetari (migliaia di dollari) con quantità (unità singole) ha causato avvisi del solver. Il riscaling ha risolto immediatamente.

Confronto delle prestazioni dei solver: le soluzioni commerciali eccellono nei problemi su larga scala. Immagine dell'autore

Strumenti software e implementazione

La scelta degli strumenti influisce enormemente sulla produttività. Sono passato dal codificare a mano il simplesso all'uso di solver professionali che gestiscono problemi immensamente più grandi.

Solver commerciali e linguaggi di modellazione

CPLEX e Gurobi dominano l'ottimizzazione industriale, offrendo prestazioni di un ordine di grandezza migliori rispetto alle alternative open source per problemi grandi. Ho usato la licenza accademica di Gurobi per lavori sulla supply chain. Problemi che con SciPy richiedevano minuti si risolvevano in secondi.

PuLP è il mio riferimento in Python. Fornisce una API pulita per formulare modelli risolti da vari backend:

from pulp import *

model = LpProblem("my_problem", LpMaximize)

x = LpVariable("x", lowBound=0)
y = LpVariable("y", lowBound=0)

model += 3*x + 2*y
model += x + y <= 100
model += 2*x + y <= 150

model.solve()

print(f"Used solver: {model.solver}")
print(f"Status: {LpStatus[model.status]}")Offerto da

Il livello di astrazione consente codice indipendente dal solver che gira su sistemi diversi. Pyomo offre funzionalità più avanzate per ottimizzazioni complesse, incluso il non lineare e lo stocastico.

Cloud e alternative open source

Le piattaforme cloud offrono optimization-as-a-service per problemi irregolari su larga scala. Carichi i dati del problema e ricevi le soluzioni via API. L'architettura serverless è elegante, sebbene più lenta dei solver locali per problemi piccoli.

GLPK (GNU Linear Programming Kit) è l'affidabile cavallo di battaglia open source. Lo uso per insegnamento e progetti personali. HiGHS è un solver più recente con prestazioni notevoli. SciPy ha adottato di recente HiGHS come backend predefinito e i miei benchmark lo hanno visto alla pari con Gurobi in molti problemi.

Esempi di programmazione lineare

Lavorare su esempi completi favorisce la comprensione meglio della sola teoria.

Esempio 1: Diet problem

Il classico diet problem minimizza i costi rispettando i requisiti nutrizionali:

from pulp import *

foods = {
    'Oatmeal': {'cost': 0.50, 'calories': 110, 'protein': 4, 'vitamin': 2},
    'Chicken': {'cost': 2.50, 'calories': 250, 'protein': 30, 'vitamin': 0},
    'Eggs':    {'cost': 0.80, 'calories': 155, 'protein': 13, 'vitamin': 1},
    'Milk':    {'cost': 1.20, 'calories': 150, 'protein': 8, 'vitamin': 4},
    'Bread':   {'cost': 0.30, 'calories': 80, 'protein': 3, 'vitamin': 0}
}

min_calories, min_protein, min_vitamin = 2000, 50, 10

model = LpProblem("Diet_Optimization", LpMinimize)
servings = LpVariable.dicts("servings", foods.keys(), lowBound=0)

model += lpSum([foods[f]['cost'] * servings[f] for f in foods])
model += lpSum([foods[f]['calories'] * servings[f] for f in foods]) >= min_calories
model += lpSum([foods[f]['protein'] * servings[f] for f in foods]) >= min_protein
model += lpSum([foods[f]['vitamin'] * servings[f] for f in foods]) >= min_vitamin

model.solve()

print(f"Total cost: ${value(model.objective):.2f}")
for food in foods:
    if servings[food].varValue > 0.01:
        print(f"{food}: {servings[food].varValue:.2f} servings")Offerto da

La formulazione sopra trova la combinazione più economica di alimenti che soddisfa i requisiti nutrizionali giornalieri. Dimostra che le soluzioni LP ottimali non sono sempre pratiche senza vincoli aggiuntivi per varietà, gusto o preferenze alimentari.

Lo stesso impianto può anche fungere da base per decisioni aziendali come ottimizzare i piani di produzione o allocare i budget di marketing.

Esempio 2: Pianificazione multiperiodo

La pianificazione multiperiodo considera come i livelli di inventario influenzano i fabbisogni futuri su più periodi di tempo:

days = ['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday']

centers = {
    'North': {'daily_demand': [100, 80, 90, 110, 85], 'capacity': 250},
    'South': {'daily_demand': [120, 100, 95, 105, 130], 'capacity': 300},
}

delivery_cost = {'Monday': 50, 'Tuesday': 50, 'Wednesday': 50,
                 'Thursday': 50, 'Friday': 70}

model = LpProblem("Multiperiod_Routing", LpMinimize)

deliveries = LpVariable.dicts("deliver",
                              [(c, d) for c in centers for d in days],
                              lowBound=0)
inventory = LpVariable.dicts("inventory",
                            [(c, d) for c in centers for d in days],
                            lowBound=0)

model += lpSum([delivery_cost[d] * deliveries[c, d] 
                for c in centers for d in days])

for c in centers:
    for i, day in enumerate(days):
        if i == 0:
            model += inventory[c, day] == deliveries[c, day] - centers[c]['daily_demand'][i]
        else:
            prev_day = days[i-1]
            model += (inventory[c, day] == inventory[c, prev_day] + 
                     deliveries[c, day] - centers[c]['daily_demand'][i])
        model += inventory[c, day] <= centers[c]['capacity']

model.solve()Offerto da

I modelli multiperiodo aumentano la dimensione del problema ma sbloccano ottimizzazioni sofisticate. Il modello concentra le consegne nei giorni più economici, usando la capacità di stoccaggio per ridurre i costi complessivi.

Programmazione mista intera

Molti problemi coinvolgono decisioni discrete: costruire un impianto o no, assegnare un lavoratore o no. Serve la programmazione mista intera (MIP), che estende la programmazione lineare con variabili intere e binarie.

Introduzione e branch-and-bound

I problemi di routing richiedono decisioni intere. La variabile binaria x[i][j] indica se il veicolo i visita la località j. I veicoli non possono effettuare visite frazionarie.

Il branch-and-bound esplora sistematicamente uno spazio di soluzioni discrete risolvendo rilassamenti LP continui:

from pulp import *

model_continuous = LpProblem("Continuous", LpMaximize)
x_cont = LpVariable("x", lowBound=0)
y_cont = LpVariable("y", lowBound=0)

model_continuous += 3*x_cont + 4*y_cont
model_continuous += x_cont + 2*y_cont <= 10
model_continuous += 2*x_cont + y_cont <= 12

model_continuous.solve()
print(f"Continuous: x={x_cont.varValue:.2f}, y={y_cont.varValue:.2f}")

model_integer = LpProblem("Integer", LpMaximize)
x_int = LpVariable("x", lowBound=0, cat='Integer')
y_int = LpVariable("y", lowBound=0, cat='Integer')

model_integer += 3*x_int + 4*y_int
model_integer += x_int + 2*y_int <= 10
model_integer += 2*x_int + y_int <= 12

model_integer.solve()
print(f"Integer: x={x_int.varValue:.0f}, y={y_int.varValue:.0f}")Offerto da

La soluzione intera differisce dall'arrotondare la soluzione continua. Il branch-and-bound trova la soluzione intera ottimale, ma a un costo computazionale significativamente maggiore.

Quando usare la programmazione intera

Usa variabili intere quando le decisioni sono intrinsecamente discrete: apertura di impianti, assegnazione di lavoratori, instradamento di veicoli. Le ottimizzazioni nel mercato obbligazionario spesso richiedono soluzioni miste intere. Le variabili continue possono produrre assegnazioni frazionarie senza senso, mentre le variabili binarie generano soluzioni implementabili.

Tuttavia, la programmazione intera è molto più costosa. Problemi con centinaia di variabili intere possono richiedere ore contro i secondi degli LP continui. Se le quantità di produzione sono grandi, l'integralità conta meno perché l'arrotondamento influisce poco sulle soluzioni. Risolvi sempre prima il rilassamento continuo per controllare i limiti prima di impegnarti nella piena programmazione intera.

Conclusione

La programmazione lineare trasforma il modo in cui affronti i problemi di ottimizzazione. Lo stesso impianto matematico si applica a domini molto diversi, dal routing alla pianificazione della produzione fino alla gestione di portafogli.

Inizia con semplici problemi a due variabili che puoi visualizzare geometricamente. Implementa un simplesso di base per capire cosa fanno i solver commerciali dietro le quinte. Lavora su formulazioni reali, traducendo i requisiti di business in vincoli matematici.

Per approfondire, esplora i nostri corsi Introduction to Optimization in Python e Linear Algebra for Data Science per rafforzare le basi matematiche. Il nostro percorso di carriera Machine Learning Scientist in Python è un'altra ottima opzione.