Problem optymalizacyjny

Problem optymalizacyjny – problem obliczeniowy, którego rozwiązanie polega na znalezieniu największej bądź najmniejszej wartości pewnej funkcji, tzw. funkcją kosztu (lub funkcją straty lub funkcją celu), która zależy od jednego lub większej liczby parametrów, opisujących dany problem optymalizacyjny. Problem optymalizacyjny nazywa się problemem maksymalizacyjnym, jeśli polega on na znalezieniu największej wartości funkcji tej, a minimalizacyjnym, jeśli szukana jest najmniejsza wartość funkcji kosztu.

Każdy problem optymalizacyjny daje się sprowadzić do problemu decyzyjnego, w tym sensie, że każdy problem optymalizacyjny ma swoją wersję decyzyjną. Odwrotne twierdzenie nie musi być prawdziwe.

Przykład

W optymalizacyjnej wersji problemu pokrycia wierzchołkowego poszukiwany jest najmniejszy zbiór wierzchołków danego grafu incydentny z każdą krawędzią. Jest więc to problem minimalizacyjny.

Linki zewnętrzne

• JarosławJ. Górnicki JarosławJ., Zadania trudniejsze od innych, „Delta”, maj 2023, ISSN 0137-3005 [dostęp 2025-10-19] .