Een concreet voorbeeld van lineair programmeren


Wat is Linair programmeren?

Wat is Linair programmeren?

Lineair programmeren is het berekenen van optimale combinaties om aan een bepaald doel te voldoen.

Om dit iets concreter voor te stellen beginnen we meteen met een eenvoudig voorbeeld:

Max, de hond van Sarah moet van de dierenarts een strikt dieet volgen waarbij hij elke dag een bepaalde hoeveelheid voedingsstoffen moet krijgen.
Het gaat hier om 2000 Kcal, 55 gr proteïnen en 800mg calcium. Hierbij heeft Sarah de keuze uit een aantal producten die elk een bepaalde samenstelling en prijs hebben. Om wat variatie te behouden wordt er voor gezorgd dat Max van elk product maar een bepaald volume per dag mag eten.

Doordat Sarah het niet breed heeft, is het tevens de bedoeling om de kost zo laag mogelijk te houden. Er moet dus een voedingschema samengesteld worden die zo performant mogelijk de beschikbare producten combineert.

Op het eerste zicht lijkt een dergelijk vraagstuk met wat logisch nadenken niet erg moeilijk om op te lossen, maar al snel zal blijken dat met hoe meer parameters men rekening dient te houden (bv meerdere producten of meerdere voedingsstoffen), het aantal mogelijke combinaties exponentieel omhoog gaat en je er zowel manueel als met een eenvoudig programma er niet meer zal geraken.

Om dit dergelijke vraagstukken op te lossen bestaat er een (complexe) rekenmethode: het lineair programmeren (zie Wikipedia voor de theorie hierachter).
In dit artikel gaan we ons echter niet verdiepen in de wiskunde die er achter zit, maar wel in hoe we dit met beschikbare tools kunnen oplossen.

Microsoft Solver Foundation

De Microsoft Solver Foundation is een nuget package die gratis kan worden gebruikt in .Net.
Doordat zowat elk lineair vraagstuk kan herleid worden naar eenzelfde vraagstelling (met uiteraard andere parameters) kan men met de Microsoft Solver Foundation dan ook praktisch elk vraagstuk oplossen.

Criteria opstellen

Een dergelijk vraagstuk kan verdeeld worden in 3 delen:

  • Decision: Hoeveel van elk hebben we nodig (in dit geval voeding)
  • Constraints (voorwaarden/limieten): voor elk voedingsattribuut een regel opstellen die de te bereiken waardes aangeeft (kan ook een range zijn)
  • Goal: het doel van de berekening, de contstrains bereiken tegen een zo laag mogelijke prijs

Voorbeeld

Initialiseren van het model

var context = SolverContext.GetContext();
var model = context.CreateModel();

Decision opstellen

Voor elk artikel moeten een decision opstellen. Een decision is een beslissing die moet genomen worden. We gaan dus vragen om voor een product een aantal te berekenen.
foreach (var article in articles)
{
var decision = new Decision(Domain.RealNonnegative,article.Name);
model.AddDecision(decision);
}

Constraints aanmaken

In de constraints gaan we de vereisten definiëren. In dit voorbeeld gaan we per voedingsattribuut gaan aangeven hoeveel de totale waarde moet zijn.
Hier is het mogelijk om met ranges te werken (bv de hoeveelheid energie moet liggen tussen 1600 Kcal en 2200 Kcal. Ranges kunnen uiterst handig zijn om kleine afwijkingen toe te laten waardoor de kostprijs drastisch kan zakken.
In dit voorbeeld gaan we uit van een minimum aan voedingsstoffen
var constrEnergy = $"{string.Join(" + ", articles.Select(o => $"{o.Energy} * {o.Name}"))} >= {energy}";
var constrProtein = $"{string.Join(" + ", articles.Select(o => $"{o.Proteins} * {o.Name}"))} >= {protein}";
var constrCalcium = $"{string.Join(" + ", articles.Select(o => $"{o.Calcium} * {o.Name}"))} >= {calcium}";
model.AddConstraint("Constr_Energy", constrEnergy);
model.AddConstraint("Constr_Protein", constrProtein);
model.AddConstraint("Constr_Calcium", constrCalcium);

We voegen ook nog een constraint toe voor het toegestane maximum aantal artikels
foreach (var article in articles)
{
var constr = $"{article.Name} <= {article.MaxPerDay}";
model.AddConstraint($"Max_{article.Name}", constr);
}

 

Doel opstellen

Het streefdoel die moet bereikt worden is uiteraard de constraints halen, maar dit moet tegen een zo laag mogelijke kost. Van alle mogelijke combinaties is de goedkoopste oplossing de beste.
var cost = $"{string.Join(" + ",articles.Select(o => $"{o.Price.FormatDecimal()} * {o.Name}"))}";
model.AddGoal("Cost", GoalKind.Minimize, cost)

Berekening uitvoeren

De Solver Foundation kan de berekening gaan uitvoeren en de juiste aantallen gaan weergeven (decisions)
foreach (var decision in solution.Decisions)
{
Console.WriteLine($"{decision.Name}: {decision.GetDouble()}");
}
Console.WriteLine($"Totale kost (in euro/dag): {solution.Goals.First().ToDouble():N2}");

Conclusie

Met de Microsoft Solver Foundation kan men op een vrij eenvoudige manier zeer complexe optimalisatie vraagstukken oplossen.
Deze library werd echter sedert 2012 niet meer bijgewerkt, maar doordat ik tot op heden nog geen andere libraries gevonden heb, is deze nog steeds aangeraden om te gebruiken.

Een ander goed uitgewerkt voorbeeld is te vinden op https://msdn.microsoft.com/en-us/library/ff628587(v=vs.93).aspx