hoekoplossing

Een hoekoplossing is een oplossing van een optimalisatieprobleem waarbij de optimale waarde zich aan een hoekpunt (extrempunt) van het realiseerbare gebied bevindt. Dit gebied ontstaat door de constraints, vaak lineair, en vormt een convex polytoon. Hoekoplossingen komen vooral voor bij lineaire programmering en bij problemen waarbij de doel- of kostenfunctie lineair is.

Bij lineaire programmering is het realiseerbare gebied een convex polytoon, en de doelfunctie lineair. Daardoor ligt een optimum vaak op een hoekpunt of op een geheel randgebied dat meerdere hoekpunten omvat. Als de richting van de optimum parallel loopt aan een rand van het gebied, kunnen meerdere hoekpunten tegelijk optimaal zijn; dan spreekt men van meerdere hoekoplossingen of van een optimale rand.

Voorbeeld: overwegingen met x1 en x2 onder de voorwaarden x1 ≥ 0, x2 ≥ 0, x1 + x2 ≤ 1. De hoekpunten zijn (0,0), (1,0) en (0,1). Voor een minimale waarde van de kostenfunctie c1 x1 + c2 x2 ligt de oplossing bij (0,0) als c1 en c2 positief zijn. Bij andere doelstellingen of coëfficiënten kan een andere hoekoplossing optreden.

Praktisch is het zo dat veel algoritmen voor lineaire programmering, zoals het simplex-algoritme, van hoek naar hoek gaan. In welbepaalde gevallen zijn er meerdere hoekoplossingen of een oneindig aantal optimale oplossingen langs een rand—dan wordt doorgaans gesproken van een gezicht van het realiseerbare gebied.

Zie ook: extrempunt, lineaire programmering, realiseerbaar gebied.