Optimale oplossing (optimalisatie)

Optimale oplossing — in operations research, optimalisatie en beslissingstheorie is dit een toelaatbare oplossing (d.w.z. een oplossing die aan alle beperkingen van het vraagstuk voldoet) die een extremale (maximale of minimale, afhankelijk van de probleemstelling) waarde van de doelfunctie oplevert.

Het vinden van de optimale oplossing is het voornaamste doel bij het oplossen van de meeste optimalisatievraagstukken.

Wezen en kenmerken

Een optimale oplossing heeft twee essentiële kenmerken:

1. Toelaatbaarheid: Zij moet voldoen aan alle beperkingen die aan de variabelen van het model zijn opgelegd. Met andere woorden: een optimale oplossing behoort altijd tot het toelaatbaar gebied (TG). 2. Extremaliteit ten opzichte van de doelfunctie: Onder alle toelaatbare oplossingen levert zij de beste (maximale of minimale) waarde van de doelfunctie op, die het optimaliteitscriterium formaliseert.

Niet elke toelaatbare oplossing is optimaal, maar elke optimale oplossing moet per definitie toelaatbaar zijn.

Relatie met het toelaatbaar gebied

Het toelaatbaar gebied (TG) is de verzameling van alle alternatieven (combinaties van variabelewaarden) die voldoen aan de beperkingen van het vraagstuk. De optimale oplossing is het punt (of de punten) in dit gebied waar de doelfunctie haar extremum bereikt. Als het TG leeg is, heeft het vraagstuk noch toelaatbare, noch — bijgevolg — optimale oplossingen.

Rol van de doelfunctie en de beperkingen

• Beperkingen bepalen de verzameling van mogelijke oplossingen (het TG).
• De doelfunctie bepaalt welke van deze mogelijke oplossingen de beste (optimale) is.

Zonder doelfunctie is het onmogelijk te bepalen welke toelaatbare oplossing optimaal is. Zonder beperkingen kan het vraagstuk triviaal zijn of geen eindige optimale oplossing hebben (bijvoorbeeld het maximaliseren van een lineaire functie zonder beperkingen).

Uniciteit van de optimale oplossing

De optimale oplossing is niet altijd uniek. In sommige vraagstukken (bijvoorbeeld in lineaire programmering, wanneer de doelfunctie evenwijdig loopt aan een van de actieve beperkingen) kan er een oneindige verzameling van optimale oplossingen bestaan met dezelfde waarde van de doelfunctie. De waarde van de doelfunctie in het optimum (of de optima) is echter altijd uniek (als het optimum bestaat).

Methoden voor het bepalen van de optimale oplossing

Voor het zoeken naar optimale oplossingen in operations research worden verschillende wiskundige methoden gebruikt, afhankelijk van het type model:

• Simplexmethode (voor lineaire programmering)
• Methoden van gradientafdaling en andere numerieke methoden (voor niet-lineaire programmering)
• Branch-and-bound-methode, afsnijdingsmethoden (voor gehele programmering)
• Methoden van dynamische programmering

Afhankelijkheid van het model

Het is belangrijk te begrijpen dat een oplossing alleen optimaal is binnen het kader van het gehanteerde wiskundige model. Als het model de werkelijke situatie onvoldoende weerspiegelt (een verkeerde doelfunctie is gekozen, belangrijke beperkingen of afhankelijkheden zijn niet meegenomen), kan de formeel gevonden optimale oplossing in de praktijk ineffectief of zelfs onjuist blijken.

Optimaliteit in meerdoelsvraagstukken

In vraagstukken met meerdere doelfuncties (meerdoelsoptimalisatie) wordt het begrip van één optimale oplossing vaak vervangen door het begrip Pareto-optimaliteit. Een Pareto-optimale oplossing is een toelaatbare oplossing waarvoor het onmogelijk is de waarde van één doelfunctie te verbeteren zonder de waarde van ten minste één andere doelfunctie te verslechteren.

Literatuur

• Ventzel, E.S. Issledovanie operatsij: zadachi, printsipy, metodologija. — Moskou: Nauka, 1988.
• Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
• Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)

Zie ook

• Operations research
• Optimalisatie
• Wiskundig model
• Doelfunctie
• Beperkingen
• Toelaatbaar gebied
• Toelaatbare oplossing
• Criterium
• Beslissingstheorie
• Meerdoelsoptimalisatie
• Pareto-optimaliteit
• Extremum