Problem z optymalizacją - Optimization problem

W matematyce , informatyce i ekonomii , Problem optymalizacji jest problemem znalezienia najlepszego rozwiązania ze wszystkich możliwych rozwiązań .

Problemy optymalizacyjne można podzielić na dwie kategorie, w zależności od tego, czy zmienne są ciągłe czy dyskretne :

Problem optymalizacji ze zmiennymi dyskretnymi jest znany jako optymalizacja dyskretna , w której obiekt, taki jak liczba całkowita , permutacja lub wykres, musi zostać znaleziony ze zbioru policzalnego .
Problem ze zmiennymi ciągłymi jest znany jako ciągła optymalizacja , w której należy znaleźć optymalną wartość z funkcji ciągłej . Mogą obejmować problemy ograniczone i problemy multimodalne.

Ciągły problem optymalizacji

Standardowe formy z ciągłym problemem jest optymalizacja

{\ Displaystyle {\ rozpocząć {wyrównane} & {\ underset {x} {\ operatorname {minimalizacja}}} && f (x) \\ & \ operatorname {temat \; do} && g_ {i} (x) \ równoważnik 0, \ quad i = 1, \ dots, m \\ &&& h_ {j} (x) = 0, \ quad j = 1, \ dots, p \ end {aligned}}}

gdzie

$f : ℝ n \to ℝ$ jest funkcją celu, którą należy zminimalizować na $n$ -wektorze zmiennym $x$ ,
$g i (x) \leq 0$ nazywane są ograniczeniami nierówności
$h j (x) = 0$ nazywane są ograniczeniami równości i
$m \geq 0$ i $p \geq 0$ .

Jeśli $m = p = 0$ , problemem jest nieograniczony problem optymalizacji. Zgodnie z konwencją, standardowa forma definiuje problem minimalizacji . Problemem maksymalizacja można leczyć niweczy funkcji celu.

Problem optymalizacji kombinatorycznej

Formalnie, kombinatoryczny problem optymalizacji $A$ jest poczwórny $(I, f, m, g)$ , gdzie

$Ja$ jest zbiorem instancji;
dana instancja $x \in I$ , $f (x)$ jest zbiorem wykonalnych rozwiązań;
podano instancję $X$ i rozwiązanie dopuszczalne $Y$ w $X$ , $m (x, y)$ oznacza środek z $Y$ , który jest zwykle dodatni rzeczywistym .
$g$ jest funkcją celu i jest wartością $minimalną$ lub $maksymalną$ .

Celem jest wówczas znaleźć dla niektórych instancji $x$ to optymalne rozwiązanie , to jest wykonalne rozwiązanie $y$ z

{\ Displaystyle m (x, r) = g {\ bigl \ {} m (x, y ') \ mid y' \ in f (x) {\ bigr \}}.}

Dla każdego problemu optymalizacji kombinatorycznej istnieje odpowiadający mu problem decyzyjny, który pyta, czy istnieje wykonalne rozwiązanie dla określonej miary $m 0$ . Na przykład, jeśli nie jest to wykres $G$ , który zawiera wierzchołki $u$ i $v$ , problem optymalizacji może być „znaleźć drogę od $U$ do $V$ , który wykorzystuje najmniejszą liczbę krawędzi”. Ten problem może mieć odpowiedź, powiedzmy, 4. Odpowiedni problem decyzyjny brzmiałby: „czy istnieje ścieżka od $u$ do $v,$ która wykorzystuje 10 lub mniej krawędzi?” Na ten problem można odpowiedzieć prostym „tak” lub „nie”.

W dziedzinie algorytmów aproksymacyjnych algorytmy są projektowane w celu znalezienia prawie optymalnych rozwiązań trudnych problemów. Zwykła wersja decyzyjna jest zatem nieodpowiednią definicją problemu, ponieważ określa tylko akceptowalne rozwiązania. Chociaż moglibyśmy wprowadzić odpowiednie problemy decyzyjne, problem jest bardziej naturalnie scharakteryzowany jako problem optymalizacji.

Zobacz też

Problem z liczeniem (złożoność)
Optymalizacja projektu
Problem funkcjonalny
Problem z rękawiczkami
Badania operacyjne
Satysfakcjonujące : nie trzeba szukać optymalnego, wystarczy „dostatecznie dobre” rozwiązanie.
Problem z wyszukiwaniem
Programowanie pół nieskończone

Bibliografia

Linki zewnętrzne

„Jak kształtowanie ruchu optymalizuje przepustowość sieci” . IPC . 12 lipca 2016 r . Źródło 13 lutego wykupu w 2017 r .

Languages

In other projects