Optimization problem (original) (raw)
Optimalizační problém je problém nalezení nejlepšího ze všech přípustných řešení. Mějme funkci , kde a je množina všech řešení. Hledáme pak takové, aby bylo maximální, případně minimální. Hovoříme pak o minimalizačním nebo maximalizačním problému.
| Property | Value |
|---|---|
| dbo:abstract | Optimalizační problém je problém nalezení nejlepšího ze všech přípustných řešení. Mějme funkci , kde a je množina všech řešení. Hledáme pak takové, aby bylo maximální, případně minimální. Hovoříme pak o minimalizačním nebo maximalizačním problému. (cs) Bei einem Optimierungsproblem sind ein Lösungsraum (Menge von möglichen Lösungen) und eine Bewertungsfunktion (auch Ziel- oder Fitnessfunktion) gegeben. Man will eine Lösung mit möglichst großem Wert finden, oder Aussagen über die Werte der Lösungen machen. In diesem Fall läge ein Maximierungsproblem vor, bei einem Minimierungsproblem sind Lösungen mit möglichst kleinem gesucht, aber dieser Fall lässt sich durch einfaches Negieren von auf den vorigen zurückführen. Man unterscheidet drei Problemstellungen: * Entscheidungsprobleme, bei denen zusätzlich ein Grenzwert gegeben ist, und ermittelt werden soll, ob es ein gibt mit . * eigentliche Optimierungsprobleme, bei denen man den Wert der besten Lösung wissen will, also . * Suchprobleme, bei denen eine optimale Lösung gesucht ist, oder eine Lösung mit einer gegebenen Mindestqualität, also ein mit . Oder man will einfach eine möglichst gute Lösung finden (Approximation). In der Theoretischen Informatik meint man mit Optimierungsproblem in der Regel ein eigentliches Optimierungsproblem, bei dem also nur der bestmögliche Wert und keine Lösung selbst gesucht ist. Auch betrachtet man üblicherweise den Sonderfall einer diskreten Bewertungsfunktion , da dies meist keinen erheblichen Unterschied macht und man reelle Zahlen weniger gut handhaben kann, z. B. näherungsweise als Gleitkommazahlen. Meistens betrachtet man in der Theoretischen Informatik aber Entscheidungsprobleme. Zu einem Optimierungsproblem lässt sich leicht ein Entscheidungsproblem erzeugen, indem man zur Problemstellung den Grenzwert bzw. hinzunimmt. Umgekehrt kann man für die meisten praktisch interessanten Probleme zeigen, dass ein Lösungsweg für das Entscheidungsproblem zu einer Lösung des entsprechenden Such- oder Optimierungsproblems modifiziert werden kann, die nicht entscheidend mehr Rechenzeit oder Speicherplatz benötigt. In der praktischen Anwendung hat man es meistens mit Suchproblemen zu tun, denn der Wert einer optimalen Lösung nützt einem ohne Kenntnis dieser Lösung in der Regel nichts.Einen Algorithmus, der ein Optimierungsproblem löst, nennt man Optimierungsalgorithmus. Analog spricht man beim Minimierungs- und Maximierungsproblem genauer vom Minimierungs- oder Maximierungsalgorithmus. Einen Algorithmus, der ein Optimierungsproblem näherungsweise löst, bezeichnet man als Approximationsalgorithmus, oft aber auch etwas ungenau ebenfalls als Optimierungsalgorithmus. (de) En matemáticas, ciencias de la computación y economía, un problema de optimización es el problema de encontrar la mejor solución a partir de todas las . Los problemas de optimización se pueden dividir en dos categorías, dependiendo de si las variables son continuas o discretas: * Un problema de optimización con variables discretas se conoce como , en la que un objeto como un número entero, una permutación o un gráfico se debe encontrar en un conjunto contable. * Un problema con variables continuas se conoce como , en la que se debe encontrar un valor óptimo de una función continua. Pueden incluir problemas restringidos y problemas multimodales. (es) In mathematics, computer science and economics, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories, depending on whether the variables are continuous or discrete: * An optimization problem with discrete variables is known as a discrete optimization, in which an object such as an integer, permutation or graph must be found from a countable set. * A problem with continuous variables is known as a continuous optimization, in which an optimal value from a continuous function must be found. They can include constrained problems and multimodal problems. (en) In matematica e in informatica, un problema di ottimizzazione è il problema di trovare la migliore soluzione fra tutte le soluzioni fattibili. I problemi di ottimizzazione possono essere divisi in due categorie a seconda se le variabili sono continue o discrete. Un problema di ottimizzazione con variabili discrete è noto come un problema di ottimizzazione combinatoria. In un problema di ottimizzazione combinatoria, stiamo cercando un oggetto come un intero, una permutazione o un grafo proveniente da un insieme finito (o possibilmente infinito numerabile). (it) 최적화 문제는 수학 혹은 컴퓨터 과학에서 모든 테스트 케이스에 대해 답을 찾는 최적의 해법을 찾는 문제를 말한다. (ko) 最適化問題（さいてきかもんだい、英: optimization problem）とは、特定の集合上で定義された実数値関数または整数値関数についてその値が最小（もしくは最大）となる状態を解析する問題である。こうした問題は総称して数理計画問題（すうりけいかくもんだい、英: mathematical programming problem, mathematical program）、数理計画とも呼ばれる。最適化問題は、自然科学、工学、社会科学などの多種多様な分野で発生する基本的な問題の一つであり、その歴史は18世紀の変分問題に遡る。1940年代に線型計画法が登場して以来、理論的な研究や数値解法の研究が非常に活発に行われ、その応用範囲はいろいろな分野に拡大されていった。実世界の現象の数理的な解析に関わる問題や抽象的な理論の多くをこの最適化問題という一般的なくくりに入れることができる。物理学やコンピュータビジョンにおける最適化問題は、考えている関数をモデル化された系のエネルギーを表すものと見なすことによって、エネルギー最小化問題と呼ばれることもある。 (ja) In de wiskunde en de informatica is een optimaliseringsprobleem het probleem van het vinden van de beste oplossing uit alle haalbare oplossingen. Optimaliseringsproblemen kunnen worden onderverdeeld in twee categorieën naargelang de variabelen continu of discreet zijn. Een optimaliseringsprobleem met discrete variabelen staat bekend als een combinatorisch optimaliseringsprobleem. In een combinatorisch optimaliseringsprobleem zijn wij op zoek naar een object, zoals een geheel getal, permutatie of grafiek uit een eindige (of eventueel aftelbaar oneindige) verzameling. (nl) Problem optymalizacyjny – problem obliczeniowy, którego rozwiązanie polega na znalezieniu największej bądź najmniejszej wartości pewnego parametru problemu, która spełnia określoną własność. Parametr, którego największej bądź najmniejszej wartości szukamy, nazywa się funkcją kosztu (funkcja celu). Problem optymalizacyjny nazywa się problemem maksymalizacyjnym, jeśli polega on na znalezieniu największej wartości funkcji kosztu, i 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. (pl) Зада́ча оптиміза́ції — задача знаходження точки (точок) мінімуму, або декількох мінімумів заданої функції. (uk) Problema de otimização, em matemática ou ciência da computação, é um problema de encontrar a melhor solução de todas as soluções viáveis. O problema de otimização pode ser dividido em duas categorias dependendo se as variáveis são continuas ou discretas. Um problema de otimização com variáveis discretas é conhecido como um problema de otimização combinatória. Em um problema de otimização combinatória, procuramos por um objeto como um inteiro, uma permutação ou grafo de um conjunto finito (ou possivelmente enumerável). (pt) Optimeringsproblem, ett beräkningsproblem där det gäller att hitta den för ett givet problem. Optimeringsproblem löses inom optimeringsläran. Klassiska optimeringsproblem: * handelsresandeproblemet (TSP) "the Traveling Salesman Problem" * kappsäcksproblemet * * * * (sv) 最佳化問題（英語：Optimization problem）在數學與電腦科學領域中，是從所有中尋找最優良的解的問題。根據變數是連續的或離散的，最佳化問題可分為兩類：連續最佳化問題與組合優化。 相對於決策問題(Decision problem)、功能性問題(Function problem)，最佳化問題是：從問題的多個解中，求出最佳解。例子：背包問題 (zh) |
| dbo:wikiPageExternalLink | https://www.ipctech.com/how-traffic-shaping-optimizes-network-bandwidth |
| dbo:wikiPageID | 1126536 (xsd:integer) |
| dbo:wikiPageLength | 5381 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1119690919 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Minimum_(mathematics) dbr:Approximation_algorithm dbr:Permutation dbr:Decision_problem dbr:Continuous_function dbr:Countable_set dbr:Mathematics dbr:Measure_(mathematics) dbr:Mathematical_object dbr:Graph_(discrete_mathematics) dbr:Constrained_optimization dbr:Constraint_(mathematics) dbr:Continuous_optimization dbr:Combinatorial_optimization dbr:Computational_problem dbr:Computer_science dbr:Additive_inverse dbr:Economics dbr:Euclidean_space dbr:Discrete_optimization dbc:Computational_problems dbr:Continuity_(mathematics) dbr:Maximum_(mathematics) dbr:Integer dbr:Canonical_form dbr:Real_number dbr:Real_numbers dbr:Set_(mathematics) dbr:Loss_function dbr:Variable_(mathematics) dbr:Discrete_variable dbr:Feasible_solution dbr:Continuous_variable dbr:Positive_(mathematics) |
| dbp:wikiPageUsesTemplate | dbt:= dbt:Annotated_link dbt:Authority_control dbt:Citation_needed dbt:Cite_web dbt:Main dbt:Math dbt:Mvar dbt:Reflist dbt:Short_description dbt:Broader dbt:Convex_analysis_and_variational_analysis |
| dct:subject | dbc:Computational_problems |
| gold:hypernym | dbr:Problem |
| rdf:type | owl:Thing yago:WikicatComputationalProblems yago:Abstraction100002137 yago:Attribute100024264 yago:Condition113920835 yago:Difficulty114408086 yago:Problem114410605 dbo:Disease yago:State100024720 |
| rdfs:comment | Optimalizační problém je problém nalezení nejlepšího ze všech přípustných řešení. Mějme funkci , kde a je množina všech řešení. Hledáme pak takové, aby bylo maximální, případně minimální. Hovoříme pak o minimalizačním nebo maximalizačním problému. (cs) In matematica e in informatica, un problema di ottimizzazione è il problema di trovare la migliore soluzione fra tutte le soluzioni fattibili. I problemi di ottimizzazione possono essere divisi in due categorie a seconda se le variabili sono continue o discrete. Un problema di ottimizzazione con variabili discrete è noto come un problema di ottimizzazione combinatoria. In un problema di ottimizzazione combinatoria, stiamo cercando un oggetto come un intero, una permutazione o un grafo proveniente da un insieme finito (o possibilmente infinito numerabile). (it) 최적화 문제는 수학 혹은 컴퓨터 과학에서 모든 테스트 케이스에 대해 답을 찾는 최적의 해법을 찾는 문제를 말한다. (ko) 最適化問題（さいてきかもんだい、英: optimization problem）とは、特定の集合上で定義された実数値関数または整数値関数についてその値が最小（もしくは最大）となる状態を解析する問題である。こうした問題は総称して数理計画問題（すうりけいかくもんだい、英: mathematical programming problem, mathematical program）、数理計画とも呼ばれる。最適化問題は、自然科学、工学、社会科学などの多種多様な分野で発生する基本的な問題の一つであり、その歴史は18世紀の変分問題に遡る。1940年代に線型計画法が登場して以来、理論的な研究や数値解法の研究が非常に活発に行われ、その応用範囲はいろいろな分野に拡大されていった。実世界の現象の数理的な解析に関わる問題や抽象的な理論の多くをこの最適化問題という一般的なくくりに入れることができる。物理学やコンピュータビジョンにおける最適化問題は、考えている関数をモデル化された系のエネルギーを表すものと見なすことによって、エネルギー最小化問題と呼ばれることもある。 (ja) In de wiskunde en de informatica is een optimaliseringsprobleem het probleem van het vinden van de beste oplossing uit alle haalbare oplossingen. Optimaliseringsproblemen kunnen worden onderverdeeld in twee categorieën naargelang de variabelen continu of discreet zijn. Een optimaliseringsprobleem met discrete variabelen staat bekend als een combinatorisch optimaliseringsprobleem. In een combinatorisch optimaliseringsprobleem zijn wij op zoek naar een object, zoals een geheel getal, permutatie of grafiek uit een eindige (of eventueel aftelbaar oneindige) verzameling. (nl) Зада́ча оптиміза́ції — задача знаходження точки (точок) мінімуму, або декількох мінімумів заданої функції. (uk) Problema de otimização, em matemática ou ciência da computação, é um problema de encontrar a melhor solução de todas as soluções viáveis. O problema de otimização pode ser dividido em duas categorias dependendo se as variáveis são continuas ou discretas. Um problema de otimização com variáveis discretas é conhecido como um problema de otimização combinatória. Em um problema de otimização combinatória, procuramos por um objeto como um inteiro, uma permutação ou grafo de um conjunto finito (ou possivelmente enumerável). (pt) Optimeringsproblem, ett beräkningsproblem där det gäller att hitta den för ett givet problem. Optimeringsproblem löses inom optimeringsläran. Klassiska optimeringsproblem: * handelsresandeproblemet (TSP) "the Traveling Salesman Problem" * kappsäcksproblemet * * * * (sv) 最佳化問題（英語：Optimization problem）在數學與電腦科學領域中，是從所有中尋找最優良的解的問題。根據變數是連續的或離散的，最佳化問題可分為兩類：連續最佳化問題與組合優化。 相對於決策問題(Decision problem)、功能性問題(Function problem)，最佳化問題是：從問題的多個解中，求出最佳解。例子：背包問題 (zh) Bei einem Optimierungsproblem sind ein Lösungsraum (Menge von möglichen Lösungen) und eine Bewertungsfunktion (auch Ziel- oder Fitnessfunktion) gegeben. Man will eine Lösung mit möglichst großem Wert finden, oder Aussagen über die Werte der Lösungen machen. In diesem Fall läge ein Maximierungsproblem vor, bei einem Minimierungsproblem sind Lösungen mit möglichst kleinem gesucht, aber dieser Fall lässt sich durch einfaches Negieren von auf den vorigen zurückführen. Man unterscheidet drei Problemstellungen: (de) En matemáticas, ciencias de la computación y economía, un problema de optimización es el problema de encontrar la mejor solución a partir de todas las . Los problemas de optimización se pueden dividir en dos categorías, dependiendo de si las variables son continuas o discretas: (es) In mathematics, computer science and economics, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories, depending on whether the variables are continuous or discrete: (en) Problem optymalizacyjny – problem obliczeniowy, którego rozwiązanie polega na znalezieniu największej bądź najmniejszej wartości pewnego parametru problemu, która spełnia określoną własność. Parametr, którego największej bądź najmniejszej wartości szukamy, nazywa się funkcją kosztu (funkcja celu). Problem optymalizacyjny nazywa się problemem maksymalizacyjnym, jeśli polega on na znalezieniu największej wartości funkcji kosztu, i minimalizacyjnym, jeśli szukana jest najmniejsza wartość funkcji kosztu. (pl) |
| rdfs:label | Optimalizační problém (cs) Optimierungsproblem (de) Problema de optimización (es) Problema di ottimizzazione (it) 최적화 문제 (ko) 最適化問題 (ja) Optimization problem (en) Optimaliseringsprobleem (nl) Problem optymalizacyjny (pl) Problema de otimização (pt) Optimeringsproblem (sv) Задача оптимизации (ru) Задача оптимізації (uk) 最佳化問題 (zh) |
| owl:sameAs | freebase:Optimization problem yago-res:Optimization problem http://d-nb.info/gnd/4390818-4 wikidata:Optimization problem dbpedia-cs:Optimization problem dbpedia-de:Optimization problem dbpedia-es:Optimization problem dbpedia-fa:Optimization problem http://hi.dbpedia.org/resource/इष्टतमकरण_समस्या dbpedia-it:Optimization problem dbpedia-ja:Optimization problem dbpedia-ko:Optimization problem dbpedia-nl:Optimization problem dbpedia-pl:Optimization problem dbpedia-pt:Optimization problem dbpedia-ru:Optimization problem dbpedia-sr:Optimization problem dbpedia-sv:Optimization problem dbpedia-uk:Optimization problem dbpedia-vi:Optimization problem dbpedia-zh:Optimization problem https://global.dbpedia.org/id/57UPg |
| prov:wasDerivedFrom | wikipedia-en:Optimization_problem?oldid=1119690919&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Optimization_problem |
| is dbo:wikiPageRedirects of | dbr:Optimal_solution dbr:Optimal_value |
| is dbo:wikiPageWikiLink of | dbr:Qiskit dbr:Elastic_matching dbr:Envy_minimization dbr:List_of_complexity_classes dbr:NAG_Numerical_Library dbr:NPO dbr:Nearest_neighbor_search dbr:Memetic_algorithm dbr:Metaheuristic dbr:Open-shop_scheduling dbr:Rate–distortion_theory dbr:Proactive_learning dbr:Boundary_tracing dbr:Algorithm dbr:Application-specific_integrated_circuit dbr:Approximation-preserving_reduction dbr:Approximation_algorithm dbr:Best_worst_method dbr:Vertex_cover dbr:Degrees_of_freedom_problem dbr:Derivative_test dbr:Independent_set_(graph_theory) dbr:Inverse_lithography dbr:Invex_function dbr:Ivar_Ekeland dbr:L-reduction dbr:Leximin_order dbr:List_of_optimization_software dbr:List_of_research_methods_in_biology dbr:Vector_optimization dbr:Complete_coloring dbr:Computability dbr:Convex_optimization dbr:Mathematical_optimization dbr:Maximum_cut dbr:Maximum_likelihood_estimation dbr:Memetics dbr:Wave_power dbr:Quadratically_constrained_quadratic_program dbr:Ekeland's_variational_principle dbr:Equation_solving dbr:Gap_reduction dbr:Glossary_of_artificial_intelligence dbr:Glossary_of_engineering:_M–Z dbr:NUPACK dbr:Optimal_binary_search_tree dbr:Optimal_job_scheduling dbr:MRF_optimization_via_dual_decomposition dbr:Simulated_annealing dbr:Steiner_tree_problem dbr:Combinatorial_optimization dbr:Commelec dbr:Comparison_of_optimization_software dbr:Competitive_programming dbr:Complexity_class dbr:Computational_complexity_theory dbr:Computational_problem dbr:Feasible_region dbr:Feedback_arc_set dbr:Frank–Wolfe_algorithm dbr:Friction_of_distance dbr:Fritz_John_conditions dbr:Fully_polynomial-time_approximation_scheme dbr:Function_problem dbr:Hardness_of_approximation dbr:Identical-machines_scheduling dbr:PLS_(complexity) dbr:PTAS_reduction dbr:Partition_problem dbr:Pattern_recognition dbr:Spectral_theory dbr:Map_segmentation dbr:Mathematical_economics dbr:Matrix_chain_multiplication dbr:Optimal_tax dbr:Backpropagation dbr:Travelling_Salesman_(2012_film) dbr:Data-driven_control_system dbr:Data_validation_and_reconciliation dbr:Duality_(optimization) dbr:Duality_gap dbr:Job-shop_scheduling dbr:Karush–Kuhn–Tucker_conditions dbr:Line_wrap_and_word_wrap dbr:Local_optimum dbr:Minimum_Population_Search dbr:Promise_problem dbr:2022_in_environmental_sciences dbr:3-dimensional_matching dbr:D-Wave_Systems dbr:Existential_risk_from_artificial_general_intelligence dbr:Barrier_resilience dbr:Baruch_Schieber dbr:Numbers_(season_2) dbr:Packing_problems dbr:Cavity_method dbr:Digital_goods_auction dbr:Flow-shop_scheduling dbr:Global_analysis dbr:Glove_problem dbr:Graph_matching dbr:Iterated_conditional_modes dbr:Quadratic_knapsack_problem dbr:Quadratic_programming dbr:Quadratic_unconstrained_binary_optimization dbr:Reeb_graph dbr:Interval_arithmetic dbr:January–March_2022_in_science dbr:Cost_distance_analysis dbr:Courcelle's_theorem dbr:Covariance_intersection dbr:Shadow_price dbr:Artificial_life dbr:APX dbr:LP-type_problem dbr:Lagrange_multiplier dbr:Bidding dbr:Bin_packing_problem dbr:Bipartite_dimension dbr:Blahut–Arimoto_algorithm dbr:Edge_cover dbr:Boolean_satisfiability_algorithm_heuristics dbr:Polynomial-time_approximation_scheme dbr:Spectral_method dbr:Claude_Lemaréchal dbr:Guillotine_cutting dbr:Guillotine_partition dbr:OR-Tools dbr:Canadian_traveller_problem dbr:R._Tyrrell_Rockafellar dbr:Search_problem dbr:Loss_function dbr:Markov_decision_process dbr:SNP_(complexity) dbr:Semi-infinite_programming dbr:Set_cover_problem dbr:Subset_sum_problem dbr:Skyline_operator dbr:Slack_variable dbr:Variable_neighborhood_search dbr:Signomial dbr:Stochastic_approximation dbr:Immune_network_theory dbr:Imperialist_competitive_algorithm dbr:Sustainable_agriculture dbr:Evolutionary_algorithm dbr:Evolver_(software) dbr:Fitness_approximation dbr:NP-equivalent dbr:NP-hardness dbr:Nonlinear_programming dbr:Multi-agent_pathfinding dbr:Multi-objective_optimization dbr:Multiple_subset_sum dbr:Multiway_number_partitioning dbr:Single-machine_scheduling dbr:Topology_optimization dbr:Value_function dbr:Set_packing dbr:Parametric_programming dbr:Parallel_task_scheduling dbr:Premature_convergence dbr:Set_splitting_problem dbr:Sparse_dictionary_learning dbr:Unrelated-machines_scheduling dbr:Uniform-machines_scheduling dbr:Submodular_set_function dbr:Variational_quantum_eigensolver dbr:Sustainable_food_system dbr:Talent_scheduling dbr:Optimal_solution dbr:Optimal_value |
| is foaf:primaryTopic of | wikipedia-en:Optimization_problem |