Lineaire programmering: echte optimalisatieproblemen oplossen

Operationsmanagers staan voor een terugkerende uitdaging: te veel beslissingen, te veel beperkingen en geen duidelijke manier om de beste oplossing te vinden. Een distributienetwerk moet brandstofkosten minimaliseren over tientallen routes, met inachtneming van bezorgtijdvensters, voertuigcapaciteiten en roosters van chauffeurs.

Deze twee problemen delen een wiskundige structuur. Wanneer je doelen en beperkingen als lineaire relaties kunnen worden uitgedrukt, werk je met een lineair programmeringsprobleem. We geven om lineaire programmering omdat het optimale oplossingen vindt wanneer je werkt met beperkte middelen en concurrerende eisen.

Wat lineaire programmering krachtig maakt, is de garantie: als er een haalbare oplossing bestaat, zal het algoritme de optimale vinden. Toegegeven, toepassingen in de praktijk passen zelden perfect in de leerboekvoorbeelden, maar inzicht in het kernkader helpt je herkennen wanneer optimalisatie giswerk kan vervangen.

Deze gids neemt je mee van de basis naar werkende Python-implementaties. We gaan van eenvoudige twee-variabeleproblemen die je geometrisch kunt visualiseren naar complexe scenario's die algoritmische oplossingen vereisen. Je begrijpt zowel de wiskundige theorie achter optimalisatie als de praktische vaardigheden om zelf oplossingen te implementeren.

Wat is lineaire programmering?

Lineaire programmering optimaliseert een lineaire doelfunctie onderworpen aan lineaire beperkingen. In een distributieroutingsproject waar ik aan werkte, was het doel de totale rijafstand te minimaliseren met inachtneming van beperkingen zoals voertuigcapaciteit en bezorgtijdvensters.

De basisstructuur begrijpen

Elk lineair programmeringsprobleem heeft drie componenten: beslissingsvariabelen, een doelfunctie en beperkingen.

Beslissingsvariabelen vertegenwoordigen de keuzes die je maakt. In routingproblemen kunnen binaire variabelen aangeven welk voertuig welke locatie bezoekt. In productieplanning kunnen variabelen productieaantallen voorstellen.

De doelfunctie definieert wat je optimaliseert. Het moet een lineaire combinatie van je beslissingsvariabelen zijn. Beperkingen definiëren de regels en beperkingen van je probleem. Ze komen in drie vormen: gelijkheden, kleiner-dan-of-gelijk-aan, of groter-dan-of-gelijk-aan ongelijkheden.

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}")Mogelijk gemaakt door

De code hierboven minimaliseert de totale kosten voor twee beslissingsvariabelen, onderworpen aan individuele limieten en een eis voor totale dekking. De objectcoëfficiënten [10, 15] vertegenwoordigen kosten per eenheid, ongelijkheidsbeperkingen begrenzen het bereik van elke variabele, en de gelijkheidsbeperking waarborgt totale dekking.

Geometrische interpretatie

Lineaire programmering geometrisch begrijpen, heeft mijn kijk op optimalisatie veranderd. Elke beperking definieert een halfvlak, en hun snijvlak vormt de haalbare regio. Deze regio is altijd een convex polytoop, wat betekent dat elke lijn tussen twee binnenpunten binnnen blijft.

De cruciale inzicht: optimale oplossingen liggen altijd op hoekpunten van de haalbare regio. Bewegen langs een rand verbetert je doel of niet, dus je blijft bewegen tot je een hoek bereikt. Deze eigenschap maakt algoritmen voor lineaire programmering efficiënt.

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()Mogelijk gemaakt door

Deze visualisatie toont de optimale oplossing bij het hoekpunt (4,7; 2,7) waar twee beperkingen elkaar snijden. De convexe haalbare regio garandeert dat er geen verborgen dalen zijn waar algoritmen vast kunnen lopen, waardoor lokale optima gelijk zijn aan globale optima.

Echte problemen transformeren

Het lastigste is niet de som oplossen, maar rommelige problemen vertalen naar strakke formuleringen. Het definiëren van variabelen en beperkingen kost vaak meer tijd dan de optimalisatie zelf draaien.

Beslissingsvariabelen definiëren vraagt om het identificeren van fundamentele keuzes. Voor routing kun je binaire variabelen gebruiken voor voertuig-locatie-toewijzingen, of continue variabelen toevoegen voor bezoekvolgorde om beperkingen te vereenvoudigen.

Beperkingen opstellen betekent bedrijfsregels vertalen naar ongelijkheden. Dit legt verborgen aannames bloot. Wanneer een manager zegt "elke locatie heeft één levering nodig", betekent dat precies één of minimaal één? Deze details veranderen de formulering volledig.

Hier is een voorbeeldformulering met 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)}")Mogelijk gemaakt door

De bovenstaande formulering gebruikt binaire variabelen voor toewijzing van vrachtwagens aan centra, minimaliseert de totale afstand, zorgt dat elk centrum precies één levering krijgt en respecteert de capaciteitslimieten van vrachtwagens.

Klassieke probleempatronen bieden sjablonen. Het dieetprobleem minimaliseert kosten met inachtneming van voedingsvereisten. Transportproblemen minimaliseren verzendkosten. Dit paste direct toe op mijn eigen routinguitdaging. Het herkennen van deze patronen versnelt de formulering, omdat je zelden echt nieuwe problemen oplost.

Lineaire programmering vindt optimale oplossingen op de hoekpunten van haalbare regio's die door beperkingen worden gedefinieerd. Afbeelding door de auteur

Oplossingsmethoden en algoritmische benaderingen

Begrijpen hoe algoritmen werken veranderde mijn waardering voor het aanroepen van linprog(). Het zijn geen black boxes maar elegante wiskundige procedures.

Simplex-algoritme

Het simplex-algoritme, ontwikkeld door George Dantzig in 1947, is het vertrekpunt. Het inzicht: systematisch van hoekpunt naar aangrenzend hoekpunt gaan, steeds de doelwaarde verbeterend, tot je het optimum bereikt.

Het algoritme onderhoudt een tableau en voert pivotoperaties uit om tussen hoekpunten te bewegen. Elke iteratie verbetert de doelwaarde of bepaalt optimaliteit door een pivelelement te kiezen en via rijoperaties bij te werken.

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}")Mogelijk gemaakt door

De code hierboven laat zien hoe je een maximalisatieprobleem met de simplex-methode oplost door de objectcoëfficiënten te negateren. De solver beweegt systematisch tussen de hoekpunten van de haalbare regio die door de beperkingen is gedefinieerd en bereikt de optimale oplossing in slechts enkele iteraties. Bij grotere problemen kan de simplexmethode het optimum in veel minder stappen vinden dan het aantal haalbare hoekpunten, vaak in minder dan 20 iteraties, zelfs met duizenden mogelijkheden.

Binnenpuntsmethoden

Terwijl simplex langs de grenzen gaat, navigeren binnenpuntsmethoden door het binnenste van de haalbare regio. Voor grote portefeuille-optimalisatieproblemen met honderden assets kan simplex traag worden, terwijl binnenpuntsmethoden het in seconden oplossen.

Het grote voordeel is polynomiale tijdcomplexiteit. Karmarkars algoritme (1984) maakte binnenpuntsmethoden praktisch, door doelverbetering te balanceren met op afstand blijven van grenslijnen. Moderne solvers zoals Gurobi kiezen automatisch tussen simplex en binnenpunt op basis van probleemkenmerken.

Grafische methode voor twee variabelen

Voor tweedimensionale problemen los ik ze eerst grafisch op. Dit bouwt intuïtie op die overdraagbaar is naar hogere dimensies. Plot beperkingen, identificeer de haalbare regio en bepaal welk hoekpunt de doelfunctie optimaliseert.

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}")Mogelijk gemaakt door

Dit bakkerijproductieprobleem maximaliseert de winst uit brood en taarten, onderworpen aan oven- en decoratie-uren. De oplossing onthult welk hoekpunt geometrisch optimaal is, waardoor het hoekpunt-hopgedrag van het algoritme concreet wordt.

Toepassingen in verschillende sectoren

Lineaire programmering past hetzelfde wiskundige kader toe om problemen in totaal verschillende domeinen op te lossen.

Productie en fabricage

Productieplanning was mijn eerste serieuze toepassing. Het productmixprobleem bepaalt productieaantallen, met variabelen die productie vertegenwoordigen, doelen die winst maximaliseren en beperkingen die hulpbronschaarste vastleggen.

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}")Mogelijk gemaakt door

Het bovenstaande model optimaliseert de elektronica-productie over drie productlijnen, waarbij assemblage- en testcapaciteit worden gebalanceerd met minimale productie-eisen.

Mengproblemen optimaliseren mengsels die aan specificaties voldoen tegen minimale kosten, zoals het mengen van voedingsmiddelen om aan voedingsvereisten te voldoen met minimale kosten.

Transport en logistiek

Het transportprobleem is een ander klassiek voorbeeld. De klassieke structuur heeft bronnen met aanbod en bestemmingen met vraag, waarbij de totale verzendkosten worden geminimaliseerd.

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()Mogelijk gemaakt door

Netwerkstroomproblemen generaliseren transport naar grafen met overslagknooppunten. Ik heb gelezen dat luchtvaartmaatschappijen dit uitgebreid gebruiken voor ploegroosters en vliegtuigroutering.

Financiële dienstverlening en zorg

In financiële toepassingen selecteert kapitaalbudgettering projecten die het rendement maximaliseren binnen budgetbeperkingen:

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()Mogelijk gemaakt door

Zorgsystemen staan voor eindeloze optimalisatie-uitdagingen. Ik adviseerde bij een planningsprobleem in een kliniek waarbij verpleegkundigen aan diensten werden toegewezen, met inachtneming van vaardigheidseisen en werkbalans.

Moderne technologie-toepassingen

Lineaire programmering duikt ook onverwacht op binnen machine learning. Featureselectie kan worden geformuleerd als het minimaliseren van voorspellingsfouten onder schaarste-beperkingen. Cloud computing gebruikt het voor resourceallocatie over gedistribueerde systemen.

Computationele complexiteit en prestaties

Complexiteit doet ertoe wanneer problemen opschalen van speelgoedvoorbeelden naar productieomgevingen.

Complexiteit van het simplex-algoritme

Simplex heeft een fascinerend complexiteitsprofiel. Het heeft een exponentieel slechtste geval, maar uitstekende gemiddelde prestaties. Pathologische gevallen zoals de Klee-Minty-kubus dwingen het elk hoekpunt te onderzoeken, maar typische problemen onderzoeken slechts een klein deel, en schalen ruwweg kwadratisch.

Ik testte dit door willekeurig gegenereerde problemen van toenemende grootte op te lossen:

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")Mogelijk gemaakt door

Mijn benchmarks lieten zien dat een verdubbeling van de probleemgrootte de tijd met minder dan 4x verhoogde, wat bijna-polynomiaal gedrag bevestigt voor typische verdelingen.

Prestatieverbeteringen

Moderne solvers bereiken opvallende prestaties via preprocessing, parallelle verwerking en automatische algoritmekeuze. Preprocessing kan de probleemgrootte automatisch met 30% of meer verminderen voor het oplossen.

Degeneratie treedt op wanneer meerdere beperkingen strak zijn in het optimum, wat mogelijk cyclen veroorzaakt. Ik kwam dit tegen toen twee routes identieke kosten hadden. Solvers gebruiken perturbatietechnieken om cycli te vermijden, al lossen gedegenereerde problemen trager op.

Numerieke instabiliteit ontstaat bij slecht geschaalde problemen. Het mengen van geldbedragen (duizenden dollars) met hoeveelheden (enkele stuks) veroorzaakte solver-waarschuwingen. Herschalen loste het meteen op.

Vergelijking van solverprestaties: commerciële oplossingen excelleren bij grootschalige problemen. Afbeelding door de auteur

Softwaretools en implementatie

De toolkeuze heeft enorme impact op productiviteit. Ik ben geëvolueerd van handmatig simplex coderen naar professionele solvers die veel grotere problemen aankunnen.

Commerciële solvers en modelleertalen

CPLEX en Gurobi domineren industriële optimalisatie, met een orde van grootte betere prestaties dan open source-alternatieven voor grote problemen. Ik gebruikte Gurobi's academische licentie voor supply chain-werk. Problemen die met SciPy minuten kostten, waren in seconden opgelost.

PuLP is mijn Python go-to. Het biedt een strakke API voor het formuleren van modellen die door verschillende backends worden opgelost:

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]}")Mogelijk gemaakt door

De abstractielaag betekent solver-agnostische code die op verschillende systemen draait. Pyomo biedt geavanceerdere features voor complexe optimalisatie, waaronder niet-lineaire en stochastische programmering.

Cloud en open-source alternatieven

Cloudplatforms bieden optimization-as-a-service voor onregelmatige grootschalige problemen. Je uploadt probleemdata en ontvangt oplossingen via een API. De serverloze architectuur is elegant, maar trager dan lokale solvers voor kleine problemen.

GLPK (GNU Linear Programming Kit) is het betrouwbare open-source werkpaard. Ik gebruik het voor onderwijs en persoonlijke projecten. HiGHS is een nieuwere solver met indrukwekkende prestaties. SciPy heeft HiGHS onlangs als standaard-backend overgenomen, en mijn benchmarks toonden dat het Gurobi op veel problemen evenaart.

Voorbeelden van lineaire programmering

Werken aan complete voorbeelden bouwt begrip beter op dan alleen theorie.

Voorbeeld 1: Dieetprobleem

Het klassieke dieetprobleem minimaliseert kosten terwijl aan voedingsvereisten wordt voldaan:

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")Mogelijk gemaakt door

De bovenstaande formulering vindt de goedkoopste combinatie van voedingsmiddelen die aan de dagelijkse voedingsvereisten voldoet. Dit laat zien dat optimale LP-oplossingen niet altijd praktisch zijn zonder extra beperkingen voor variatie, smaak of dieetvoorkeuren.

Ditzelfde kader kan ook dienen als basis voor zakelijke beslissingen zoals het optimaliseren van productieschema's of het toewijzen van marketingbudgetten.

Voorbeeld 2: Meerperiodenplanning

Meerperiodenplanning houdt rekening met hoe voorraadniveaus toekomstige behoeften beïnvloeden over meerdere perioden:

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()Mogelijk gemaakt door

Meerperiodenmodellen vergroten de probleemgrootte maar ontsluiten geavanceerde optimalisatie. Het model bundelt leveringen op goedkopere dagen en gebruikt opslagcapaciteit om de totale kosten te verlagen.

Gemengd-gehele getallen programmeren

Veel problemen bevatten discrete beslissingen: bouw een faciliteit of niet, wijs een werknemer toe of niet. Dit vereist mixed-integer programming (MIP), een uitbreiding van lineaire programmering met gehele en binaire variabelen.

Introductie en branch-and-bound

Routingproblemen hebben gehele beslissingen nodig. De binaire variabele x[i][j] geeft aan of voertuig i locatie j bezoekt. Voertuigen kunnen geen fractionele bezoeken afleggen.

Branch-and-bound doorzoekt systematisch een discrete oplossingsruimte door continue LP-relaxaties op te lossen:

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}")Mogelijk gemaakt door

De gehele oplossing verschilt van het afronden van de continue oplossing. Branch-and-bound vindt de optimale gehele oplossing, maar tegen aanzienlijk hogere rekenkosten.

Wanneer integer programming gebruiken

Gebruik gehele variabelen wanneer beslissingen van nature discreet zijn: faciliteiten openen, werknemers toewijzen, voertuigen routeren. Optimalisaties op de obligatiemarkt vereisen vaak gemengd-gehele oplossingen. Continue variabelen kunnen onzinnige fractionele toewijzingen opleveren, terwijl binaire variabelen uitvoerbare oplossingen geven.

Integer programming is echter veel duurder. Problemen met honderden gehele variabelen kunnen uren duren, versus seconden voor continue LP's. Als productieaantallen groot zijn, maakt integrality minder uit omdat afronden nauwelijks invloed heeft op oplossingen. Los altijd eerst de continue relaxatie op om grenzen te controleren voordat je je commit aan volledige integer programming.

Conclusie

Lineaire programmering verandert hoe je optimalisatieproblemen benadert. Hetzelfde wiskundige kader is toepasbaar in sterk verschillende domeinen, van routing tot productieplanning en portefeuillebewaking.

Begin met eenvoudige tweedimensionale problemen die je geometrisch kunt visualiseren. Implementeer basis-simplex om te begrijpen wat commerciële solvers onder de motorkap doen. Werk met echte formuleringen en vertaal bedrijfsvereisten naar wiskundige beperkingen.

Wil je je expertise verdiepen? Bekijk onze cursussen Introduction to Optimization in Python en Linear Algebra for Data Science om je wiskundige basis te versterken. Onze Machine Learning Scientist carrièretrack in Python is ook een mooie optie.