Basic feasible solution (original) (raw)
In the theory of linear programming, a basic feasible solution (BFS) is a solution with a minimal set of non-zero variables. Geometrically, each BFS corresponds to a corner of the polyhedron of feasible solutions. If there exists an optimal solution, then there exists an optimal BFS. Hence, to find an optimal solution, it is sufficient to consider the BFS-s. This fact is used by the simplex algorithm, which essentially travels from some BFS to another until an optimal one is found.
| Property | Value |
|---|---|
| dbo:abstract | In the theory of linear programming, a basic feasible solution (BFS) is a solution with a minimal set of non-zero variables. Geometrically, each BFS corresponds to a corner of the polyhedron of feasible solutions. If there exists an optimal solution, then there exists an optimal BFS. Hence, to find an optimal solution, it is sufficient to consider the BFS-s. This fact is used by the simplex algorithm, which essentially travels from some BFS to another until an optimal one is found. (en) В теорії лінійного програмування, базовий допустимий розв'язок (БДР) це, інтуїтивно, розв'язок з найменшою кількість ненульових змінних. Геометрично, кожен БДР відповідає куту допустимих розв'язків. Якщо існує оптимальний розв'язок, тоді існує оптимальний БДР. Звідси, щоб знайти оптимальний розв'язок, достатньо розглядати лише БДР-и. Цей факт використовує симплекс-метод, який по суті мандрує від якогось БДР до іншого допоки на знайде оптимальний. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Elongated_pentagonal_orthocupolarotunda.png?width=300 |
| dbo:wikiPageExternalLink | https://or.stackexchange.com/a/7214/2576 |
| dbo:wikiPageID | 58654129 (xsd:integer) |
| dbo:wikiPageLength | 11473 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1108603449 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Nonsingular dbr:Basis_(linear_algebra) dbr:Polyhedron dbr:Convex_polyhedra dbr:Ellipsoid_method dbr:Convex_polytope dbr:Bauer_maximum_principle dbr:Dual_linear_program dbr:Column_space dbr:Linear_programming dbr:Nimrod_Megiddo dbr:Invertible_matrix dbc:Linear_programming dbr:Dimension dbr:Simplex_algorithm dbr:Slack_variable dbr:Strongly_polynomial_time dbr:Weakly_polynomial_time_algorithm dbr:File:Elongated_pentagonal_orthocupolarotunda.png |
| dbp:wikiPageUsesTemplate | dbt:One_source dbt:Reflist dbt:Rp |
| dct:subject | dbc:Linear_programming |
| rdfs:comment | In the theory of linear programming, a basic feasible solution (BFS) is a solution with a minimal set of non-zero variables. Geometrically, each BFS corresponds to a corner of the polyhedron of feasible solutions. If there exists an optimal solution, then there exists an optimal BFS. Hence, to find an optimal solution, it is sufficient to consider the BFS-s. This fact is used by the simplex algorithm, which essentially travels from some BFS to another until an optimal one is found. (en) В теорії лінійного програмування, базовий допустимий розв'язок (БДР) це, інтуїтивно, розв'язок з найменшою кількість ненульових змінних. Геометрично, кожен БДР відповідає куту допустимих розв'язків. Якщо існує оптимальний розв'язок, тоді існує оптимальний БДР. Звідси, щоб знайти оптимальний розв'язок, достатньо розглядати лише БДР-и. Цей факт використовує симплекс-метод, який по суті мандрує від якогось БДР до іншого допоки на знайде оптимальний. (uk) |
| rdfs:label | Basic feasible solution (en) Базовий допустимий розв'язок (uk) |
| owl:sameAs | wikidata:Basic feasible solution dbpedia-uk:Basic feasible solution https://global.dbpedia.org/id/9J9WJ |
| prov:wasDerivedFrom | wikipedia-en:Basic_feasible_solution?oldid=1108603449&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Elongated_pentagonal_orthocupolarotunda.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Basic_feasible_solution |
| is dbo:wikiPageDisambiguates of | dbr:BFS |
| is dbo:wikiPageRedirects of | dbr:Basis_of_a_linear_program |
| is dbo:wikiPageWikiLink of | dbr:BFS dbr:Egalitarian_item_allocation dbr:Fractional_Pareto_efficiency dbr:Karmarkar-Karp_bin_packing_algorithms dbr:Bland's_rule dbr:Simplex_algorithm dbr:Basis_of_a_linear_program |
| is foaf:primaryTopic of | wikipedia-en:Basic_feasible_solution |
