Straffmetod

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 17 oktober 2018; kontroller kräver 5 redigeringar .

Straffmetoder ( metoder för strafffunktioner ) är metoder som används i stor utsträckning för att lösa tekniska och ekonomiska optimeringsproblem [1] .

Effektiv om strafffunktionen följer naturligt av problemets tekniska innebörd.

Problem med att minimera flera kriterier reduceras ibland till straffmetoder med ett enda kriterium. Till exempel, vid fastställandet pekas ett huvudkriterium ut som en objektiv funktion, de återstående kriterierna ersätts med restriktioner. Vid programmering beaktas begränsningar med hjälp av en straffavgift (de överförs till den objektiva funktionen) - på så sätt ersätts alla kriterier med ett.

Ganska ofta används de både i teoretisk forskning och i utvecklingen av algoritmer.

Väl lämpad för en ungefärlig uppskattning av det globala minimumet av multiextrema problem i en komplex tillåten region.

Detta tillvägagångssätt kan användas inte bara som en beräkningsmetod, utan också som en metod för "mjuk" beskrivning av system. Det gör att man kan ersätta problem med komplexa begränsningssystem med problem med enkla begränsningssystem eller utan dem alls, samt att lösa problem med inkonsekventa begränsningssystem och få praktiskt taget acceptabla lösningar.

I metoden för strafffunktioner kan värdet av straffkoefficienter i regel öka på obestämd tid. Dess variant, metoden för exakta strafffunktioner, gör det möjligt att hitta optimala lösningar redan vid ändliga värden av straffkoefficienter [2] [3] . Detta försvagar avsevärt problemet med dålig kondition, vilket är typiskt för strafffunktionsmetoden, som vanligtvis används för att få fram endast ungefärliga lösningar. Metoden med exakta strafffunktioner gör det dock möjligt att få exakta lösningar på de ursprungliga problemen.

Historik

Rent matematiskt användes straffmetoden först av den amerikanske matematikern R. Courant 1943 (för att studera rörelse i ett begränsat område) [1] .

Metoder användes i stor utsträckning för att lösa lokala minimeringsproblem på 60-talet. En av de mest populära var SUMT-programmet (utvecklare - amerikanerna Fiakko och McCormick).

Nackdelar

Oemotståndlig: i lindring av funktionerna för straff och barriärer bildas djupa raviner av komplex form, där alla metoder för lokal ovillkorlig härkomst är ineffektiva [1] .

Det finns bättre metoder för lokal minimering med differentierbara mål- och begränsningsfunktioner.

Se även

Anteckningar

  1. ↑ 1 2 3 Zhiliniskas A., Shatlyanis V. Sök efter det optimala: datorn utökar möjligheterna. — M.: Nauka, 1989, sid. 79, ISBN 5-02-006737-7
  2. ↑ Shmelev V. V. Exakta strafffunktioner i linjär och heltalslinjär programmering. Automation och telemekanik , . 1992. Nr 5. S. 106-115.
  3. ↑ Shmelev V.V. Metod för exakta strafffunktioner för linjära blandade heltalsoptimeringsproblem. Avhandling för doktorsexamen i fysikaliska och matematiska vetenskaper, M.: ISA RAN, 2000, kapitel 1-5. Avhandlingen och dess sammandrag finns tillgängliga på webbplatsen för Scientific Electronic Library eLIBRARY.RU i listan över publikationer av Shmelev V.V.

Litteratur

Länkar