Metoda pedepsei

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 17 octombrie 2018; verificările necesită 5 modificări .

Metodele de penalizare ( methods of penalty functions ) sunt metode utilizate pe scară largă pentru rezolvarea problemelor tehnice și economice de optimizare [1] .

Eficient dacă funcția de penalizare decurge firesc din sensul tehnic al problemei.

Problemele de minimizare multicriterială sunt uneori reduse la metode de penalizare cu un singur criteriu. De exemplu, la stabilire, un criteriu principal este evidențiat ca funcție obiectivă, criteriile rămase sunt înlocuite cu restricții. La programare, restricțiile sunt luate în considerare cu ajutorul unei penalități (sunt transferate la funcția obiectiv) - în acest fel, toate criteriile sunt înlocuite cu unul singur.

Destul de des sunt utilizați atât în ​​cercetarea teoretică, cât și în dezvoltarea algoritmilor.

Potrivit pentru o estimare aproximativă a minimului global de probleme multi-extreme într-o regiune complexă admisibilă.

Această abordare poate fi folosită nu numai ca metodă de calcul, ci și ca metodă de descriere „soft” a sistemelor. Permite înlocuirea problemelor cu sisteme de constrângeri complexe cu probleme cu sisteme de constrângeri simple sau fără ele deloc, precum și rezolvarea problemelor cu sisteme de constrângeri inconsistente, obținând soluții practic acceptabile.

În metoda funcțiilor de penalizare, valoarea coeficienților de penalizare, de regulă, poate crește la nesfârșit. Varianta sa, metoda funcțiilor de penalizare exactă, face posibilă găsirea soluțiilor optime deja la valori finite ale coeficienților de penalizare [2] [3] . Acest lucru slăbește semnificativ problema condiționării proaste, care este tipică pentru metoda funcției de penalizare, care este de obicei folosită pentru a obține doar soluții aproximative. Cu toate acestea, metoda funcțiilor de penalizare exactă face posibilă obținerea de soluții exacte la problemele originale.

Istorie

Strict matematic, metoda penalizării a fost folosită pentru prima dată de matematicianul american R. Courant în 1943 (pentru a studia mișcarea într-o zonă limitată) [1] .

Metodele au fost utilizate pe scară largă pentru a rezolva problemele locale de minimizare în anii '60. Unul dintre cele mai populare a fost programul SUMT (dezvoltatori - americanii Fiakko și McCormick).

Dezavantaje

Irezistibil: în relieful funcțiilor de penalități și bariere, se formează râpe adânci de formă complexă, unde toate metodele de coborâre locală necondiționată sunt ineficiente [1] .

Există metode mai bune pentru minimizarea locală cu funcții de obiectiv și constrângere diferențiabile.

Vezi și

Note

  1. ↑ 1 2 3 Zhiliniskas A., Shatlyanis V. Caută optimul: computerul extinde posibilitățile. — M.: Nauka, 1989, p. 79, ISBN 5-02-006737-7
  2. ↑ Shmelev V. V. Funcții de penalizare exacte în programarea liniară liniară și întreagă. Automatizare si telemecanica , . 1992. Nr 5. S. 106-115.
  3. ↑ Shmelev V.V. Metoda funcțiilor de penalizare exactă pentru probleme de optimizare liniară cu numere întregi mixte. Teză pentru gradul de Doctor în Științe Fizice și Matematice, M.: ISA RAN, 2000, capitolele 1-5. Teza și rezumatul acesteia sunt disponibile pe site-ul Bibliotecii științifice electronice eLIBRARY.RU în lista publicațiilor lui Shmelev V.V.

Literatură

Link -uri