Objektiv funktion

En objektiv funktion är  en reell eller heltalsfunktion av flera variabler som är föremål för optimering ( minimering eller maximering ) för att lösa något optimeringsproblem. Termen används inom matematisk programmering, operationsforskning , linjär programmering , statistisk beslutsteori och andra områden inom matematiken, främst av tillämpad karaktär, även om målet med optimering också kan vara lösningen av ett matematiskt problem i sig [1] . Förutom den objektiva funktionen kan variabler i optimeringsproblemet vara föremål för restriktioner i form av ett system av likheter eller ojämlikheter. I det allmänna fallet kan objektivfunktionsargumenten specificeras på godtyckliga uppsättningar.

Exempel

Släta funktioner och ekvationssystem

Problemet med att lösa vilket ekvationssystem som helst

kan formuleras som ett problem med att minimera den objektiva funktionen

Om funktionerna är smidiga kan minimeringsproblemet lösas med gradientmetoder .

För varje smidig objektivfunktion kan man likställa partiella derivator med avseende på alla variabler. Den optimala objektivfunktionen kommer att vara en av lösningarna till ett sådant ekvationssystem. I fallet med en funktion kommer detta att vara ett system av minsta kvadraters (LSM) ekvationer . Varje lösning av det ursprungliga systemet är en lösning av minsta kvadratsystemet. Om det ursprungliga systemet är inkonsekvent, så gör LSM-systemet, som alltid har en lösning, det möjligt att få en ungefärlig lösning av det ursprungliga systemet. Antalet ekvationer i LSM-systemet sammanfaller med antalet okända, vilket ibland underlättar lösningen av gemensamma initiala system.

Linjär programmering

Ett annat välkänt exempel på en objektiv funktion är en linjär funktion som förekommer i linjära programmeringsproblem. I motsats till den kvadratiska objektivfunktionen är optimering av en linjär funktion möjlig endast om det finns begränsningar i form av ett system av linjära likheter eller ojämlikheter.

Kombinatorisk optimering

Ett typiskt exempel på en kombinatorisk målfunktion är den objektiva funktionen för resandeförsäljarproblemet . Denna funktion är lika med längden på Hamiltons cykel på grafen . Den ges på uppsättningen av grafvertexpermutationer [ 2] och bestäms av grafens kantlängdsmatris. Den exakta lösningen av sådana problem beror ofta på en uppräkning av alternativ.

Anteckningar

  1. ↑ Målfunktion, matematisk programmering // Mathematical Encyclopedic Dictionary. - M . : "Ugglor. uppslagsverk" , 1988.
  2. ↑ En sådan permutation en-till-en definierar en Hamiltonsk cykel för en asymmetrisk matris av grafkantlängder.

Se även

Litteratur