| dbpprop:abstract
|
- In mathematical optimization theory, the simplex algorithm, created by the American mathematician George Dantzig in 1947, is a popular algorithm for numerical solution of the linear programming problem. The journal Computing in Science and Engineering listed it as one of the top 10 algorithms of the century. An unrelated, but similarly named method is the Nelder-Mead method or downhill simplex method due to Nelder & Mead (1965) and is a numerical method for optimizing many-dimensional unconstrained problems, belonging to the more general class of search algorithms. In both cases, the method uses the concept of a simplex, which is a polytope of N + 1 vertices in N dimensions: a line segment in one dimension, a triangle in two dimensions, a tetrahedron in three-dimensional space and so forth.
- Das Simplex-Verfahren (auch Simplex-Algorithmus) ist ein Optimierungsverfahren der Numerik zur Lösung linearer Optimierungsprobleme. Es löst ein solches Problem nach endlich vielen Schritten exakt oder stellt dessen Unlösbarkeit oder Unbeschränktheit fest. Die Grundidee des Simplex-Verfahrens wurde 1947 von George Dantzig vorgestellt. Seitdem hat es sich durch zahlreiche Verbesserungen zum wichtigsten Lösungsverfahren der linearen Optimierung in der Praxis entwickelt. Das Simplex-Verfahren ist ein Pivotverfahren. Obwohl bisher für jede Variante des Verfahrens ein Beispiel konstruiert werden konnte, bei dem der Algorithmus exponentielle Laufzeit benötigt, läuft der Simplex-Algorithmus in der Praxis meist schneller als andere Verfahren. Zwar gibt es zur Lösung einzelner linearer Programme auch andere konkurrenzfähige Methoden, z. B. Innere-Punkte-Verfahren. Der große Vorteil des Simplex-Algorithmus liegt jedoch darin, dass er bei leichter Veränderung des Problems – beispielsweise dem Hinzufügen einer zusätzlichen Bedingung – einen „Warmstart“ von der letzten verwendeten Lösung durchführen kann und daher meist nur wenige Iterationen zur erneuten Lösung benötigt, während andere Verfahren von vorne beginnen müssen. Darüber hinaus nutzt das Simplex-Verfahren die engen Zusammenhänge zwischen einem linearen Programm (LP) und seinem dualen LP aus und löst grundsätzlich beide Probleme gleichzeitig. Beide Eigenschaften sind in der nichtlinearen oder ganzzahligen linearen Optimierung von Bedeutung, wo sehr viele ähnliche LPs in Folge gelöst werden müssen. Die geometrische Grundidee des Algorithmus besteht darin, von einer beliebigen Ecke des Polyeders, das durch das lineare Programm definiert wird, entlang seiner Kanten zu einer optimalen Ecke zu laufen. Der Name des Verfahrens rührt daher, dass die nichtnegativen Linearkombinationen der Basisspalten in jeder Iteration einen simplizialen Kegel beschreiben. Ein Namensvetter dieses Verfahrens namens Downhill-Simplex-Verfahren (Nelder und Mead 1965) basiert ebenfalls auf einem Simplex, ist aber ein iteratives Verfahren zur nichtlinearen Optimierung.
- Simplexový algoritmus (duální simplex. algoritmus) od George Dantziga je algoritmus pro řešení úlohy lineárního programování. Metoda je ve spojitostí s vlastnostmi polytopu v N dimenzionálním euklidovském prostoru. Řešená úloha je tak i graficky interpretovatelná - hledají se vlastně co nejvíce vzdálené vrcholy polytopu.
- En la teoría de optimización, el algoritmo símplex, descubierto por el matemático norteamericano George Bernard Dantzig en 1947, es una técnica popular para dar soluciones numéricas del problema de la programación lineal. Un método sin relación, pero llamado de manera similar, es el método Nelder-Mead o método símplex cuesta abajo, debido a Nelder y Mead (1965), que es un método numérico para optimización de problemas libres multidimensionales, perteneciente a la clase más general de algoritmos de búsqueda. El que permite encontrar una solución óptima en un problema de maximización o minimización, buscando en los vértices del polígono. En ambos casos, el método usa el concepto de un símplex, que es un politopo de N + 1 vértices en N dimensiones: un segmento de línea sobre una línea, un triángulo sobre un plano, un tetraedro en un espacio de tres dimensiones y así sucesivamente.
- L'algorithme du simplexe de George Dantzig est une technique à la fois fondamentale et très populaire pour les problèmes de programmation linéaire. Ainsi, étant donné un ensemble d'inégalités linéaires sur <math>n</math> variables réelles, l'algorithme permet de trouver la solution optimale pour une fonction objectif, qui est elle aussi linéaire (l'algorithme fonctionne encore quand la fonction est croissante en chacune de <math>n</math> variables). En termes géométriques, l'ensemble des inégalités linéaires définit un polytope dans l'espace à <math>n</math> dimensions (polygone en 2 dimensions et polyèdre en 3 dimensions) et il s'agit de trouver le sommet optimal pour la fonction de coût donnée. L'idée de l'algorithme consiste à partir d'un sommet quelconque du polytope et, à chaque itération, d'aller à un sommet adjacent s'il est possible d'en trouver un meilleur pour la fonction objectif. S'il n'y en a pas, l'algorithme s'arrête en concluant que le sommet courant est optimal. En général, il y a plusieurs sommets adjacents au sommet courant qui sont meilleurs pour l'objectif. Il faut en sélectionner un seul, la règle de sélection est appelée règle de pivotage. Il a été montré pour les principales règles de pivotage employées que l'algorithme du simplexe pouvait prendre un temps de calcul exponentiel. En particulier, on ne sait pas s'il existe une règle de pivotage qui assurerait que l'algorithme se termine après un nombre polynomial d'étapes. On peut montrer que le nombre d'itérations de l'algorithme est majoré par : <math> \frac{N-2}{\nu-1} </math> où <math>\nu</math> est le plus petit nombre d'arêtes reliées à un même sommet du polytope parcouru par le simplexe et <math>N</math> est le nombre de sommets. On remarquera que <math>\nu</math> est minoré par la dimension de l'espace dans lequel vit le polytope. Néanmoins, l'algorithme du simplexe est très efficace en pratique et il est implémenté dans tous les solveurs de programmes linéaires. Les autres algorithmes de résolution de programmes linéaires sont basés soit sur la méthode de l'ellipsoïde soit sur la méthode du point intérieur.
- L'algoritmo del simplesso, ideato dall'americano George Dantzig nel 1947, è un metodo numerico per risolvere problemi di programmazione lineare. È citato dalla rivista americana Computing in Science and Engineering come uno dei dieci migliori algoritmi del secolo. Questo algoritmo fa uso del concetto di simplesso, cioè un politopo di N+1 vertici in N dimensioni: un segmento di retta in una dimensione, un triangolo in due dimensioni, un tetraedro in tre dimensioni.
- シンプレックス法(単体法とも。どちらも和訳：simplex method)は、1947年にG.B. Danzigが提案した、線形計画問題を解くアルゴリズムの中で最も広く使用されている方法である。線形計画法の1つ。
- De simplexmethode (of het simplexalgoritme) is een methode in de wiskundige optimalisatie. De techniek werd in 1947 door George Dantzig ontwikkeld. De simplexmethode lost een lineaire optimaliseringsprobleem in een eindig aantal stappen op, of stelt de onoplosbaarheid van het probleem vast. In theoretisch gevallen kunnen cycli optreden, die het vinden van de optimale oplossing verhinderen. De naam komt van het feit dat de vergelijkingen van het probleem een simplex beschrijven, waarvan de rand bij het vinden van de oplossing beschreven wordt.
- Simplex-algoritmen av George Dantzig er i matematisk optimaliseringsteori en populær teknikk for numerisk løsning av lineærprogrammeringsproblemet. En ubeslektet, men med likt navn er Nelder-Mead metoden eller downhill simplex method etter Nelder & Mead (1965) og er en numerisk metode for å optimalisere mange-dimensjonale ubegrensete problemer som hører til en mer generell klasse av søkealgoritmer. I begge tilfellene bruker metoden konseptet med en simplex, som er en polytop med N + 1 hjørner i N dimensjoner: et linjesegment på en linje, et triangel på et plan, et tetraeder i tre-dimensjonalt rom og så videre.
- Algorytm sympleksowy, inaczej metoda sympleks(ów) to stosowana w matematyce iteracyjna metoda rozwiązywania zadań programowania liniowego za pomocą kolejnego polepszania rozwiązania. Nazwa metody pochodzi od sympleksu, figury wypukłej będącej uogólnieniem trójkąta na więcej wymiarów.
- Em teoria de otimização matemática, o algoritmo simplex de George Dantzig é uma técnica popular para dar soluções numéricas de problemas da programação linear. Um método sem relação, mas chamado de maneira similar é o método Nelder-Mead ou método simplex de baixo custo devido a Nelder e Mead (1965) e é um método numérico para otimização de problemas livres multidimensionais, pertencentes à classe mais geral de algoritmos de busca. Em ambos os casos, o método usa o conceito de um simplex, que é um polítopo de N + 1 vértices em N dimensões: um segmento de linha sobre uma linha, um triângulo sobre um plano, um tetraedro em um espaço de três dimensões e assim sucessivamente.
- Не путать с «симплекс-методом» — методом оптимизации произвольной функции. См. Метод Нелдера — Мида Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Метод был разработан американским математиком Джорджем Данцигом (George Dantzig) в 1947 году.
- Simplexmetoden eller simplexalgoritmen är en metod inom optimeringsläran för att effektivt lösa linjärprogrammeringsproblem. Metoden uppfanns av den amerikanske matematikern George Dantzig och är i dag den i särklass mest använda algoritmen för att lösa LP-problem som nästan helt dominerar den kommersiella marknaden. Enligt linjärprogrammeringens fundamentalsats erhålles alltid optimum i minst en hörnpunkt till den tillåtna mängden och dessa hörn motsvaras av en (eller flera i det degenererade fallet) baslösning(ar). Simplexmetoden söker den bästa lösningen genom att systematisk flytta sig från en baslösning till en annan närliggande på ett sådant sätt att målfunktionsvärdet förbättras. Den söker inte igenom samtliga hörnpunkter då det även för förhållandevis "små" LP-problem finns oerhört många men eftersom problemet är konvext kommer den hörnpunkt för vilka ingen närliggande hörnpunkt har ett bättre målfunktionsvärde att vara optimallösningen till problemet.
- Симплекс-метод — метод розв'язання задачі лінійного програмування, в якому здійснюється скерований рух по опорних планах до знаходження оптимального розв'язку; симплекс-метод також називають методом поступового покращення плану.
- 数学优化中，由George Dantzig发明的单纯形法（simplex algorithm）是线性规划问题的数值求解的流行技术。有一个算法与此无关，但名称类似，它是Nelder-Mead法或称下山单纯形法，由Nelder和Mead发现（1965年），这是用于优化多维无约束问题的一种数值方法，属于更一般的搜索算法的类别。 这二者都使用了单纯形的概念，它是N维中的N + 1个顶点的凸包，是一个多胞体：直线上的一个线段，平面上的一个三角形，三维空间中的一个四面体，等等。
|
| rdfs:comment
|
- In mathematical optimization theory, the simplex algorithm, created by the American mathematician George Dantzig in 1947, is a popular algorithm for numerical solution of the linear programming problem. The journal Computing in Science and Engineering listed it as one of the top 10 algorithms of the century.
- Das Simplex-Verfahren (auch Simplex-Algorithmus) ist ein Optimierungsverfahren der Numerik zur Lösung linearer Optimierungsprobleme. Es löst ein solches Problem nach endlich vielen Schritten exakt oder stellt dessen Unlösbarkeit oder Unbeschränktheit fest. Die Grundidee des Simplex-Verfahrens wurde 1947 von George Dantzig vorgestellt. Seitdem hat es sich durch zahlreiche Verbesserungen zum wichtigsten Lösungsverfahren der linearen Optimierung in der Praxis entwickelt.
- Simplexový algoritmus (duální simplex. algoritmus) od George Dantziga je algoritmus pro řešení úlohy lineárního programování. Metoda je ve spojitostí s vlastnostmi polytopu v N dimenzionálním euklidovském prostoru. Řešená úloha je tak i graficky interpretovatelná - hledají se vlastně co nejvíce vzdálené vrcholy polytopu.
- En la teoría de optimización, el algoritmo símplex, descubierto por el matemático norteamericano George Bernard Dantzig en 1947, es una técnica popular para dar soluciones numéricas del problema de la programación lineal.
- L'algorithme du simplexe de George Dantzig est une technique à la fois fondamentale et très populaire pour les problèmes de programmation linéaire. Ainsi, étant donné un ensemble d'inégalités linéaires sur <math>n</math> variables réelles, l'algorithme permet de trouver la solution optimale pour une fonction objectif, qui est elle aussi linéaire (l'algorithme fonctionne encore quand la fonction est croissante en chacune de <math>n</math> variables).
- L'algoritmo del simplesso, ideato dall'americano George Dantzig nel 1947, è un metodo numerico per risolvere problemi di programmazione lineare. È citato dalla rivista americana Computing in Science and Engineering come uno dei dieci migliori algoritmi del secolo. Questo algoritmo fa uso del concetto di simplesso, cioè un politopo di N+1 vertici in N dimensioni: un segmento di retta in una dimensione, un triangolo in due dimensioni, un tetraedro in tre dimensioni.
- シンプレックス法(単体法とも。どちらも和訳：simplex method)は、1947年にG.B. Danzigが提案した、線形計画問題を解くアルゴリズムの中で最も広く使用されている方法である。線形計画法の1つ。
- De simplexmethode (of het simplexalgoritme) is een methode in de wiskundige optimalisatie. De techniek werd in 1947 door George Dantzig ontwikkeld. De simplexmethode lost een lineaire optimaliseringsprobleem in een eindig aantal stappen op, of stelt de onoplosbaarheid van het probleem vast. In theoretisch gevallen kunnen cycli optreden, die het vinden van de optimale oplossing verhinderen.
- Simplex-algoritmen av George Dantzig er i matematisk optimaliseringsteori en populær teknikk for numerisk løsning av lineærprogrammeringsproblemet. En ubeslektet, men med likt navn er Nelder-Mead metoden eller downhill simplex method etter Nelder & Mead (1965) og er en numerisk metode for å optimalisere mange-dimensjonale ubegrensete problemer som hører til en mer generell klasse av søkealgoritmer.
- Algorytm sympleksowy, inaczej metoda sympleks(ów) to stosowana w matematyce iteracyjna metoda rozwiązywania zadań programowania liniowego za pomocą kolejnego polepszania rozwiązania. Nazwa metody pochodzi od sympleksu, figury wypukłej będącej uogólnieniem trójkąta na więcej wymiarów.
- Em teoria de otimização matemática, o algoritmo simplex de George Dantzig é uma técnica popular para dar soluções numéricas de problemas da programação linear. Um método sem relação, mas chamado de maneira similar é o método Nelder-Mead ou método simplex de baixo custo devido a Nelder e Mead (1965) e é um método numérico para otimização de problemas livres multidimensionais, pertencentes à classe mais geral de algoritmos de busca.
- Не путать с «симплекс-методом» — методом оптимизации произвольной функции. См. Метод Нелдера — Мида Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве.
- Simplexmetoden eller simplexalgoritmen är en metod inom optimeringsläran för att effektivt lösa linjärprogrammeringsproblem. Metoden uppfanns av den amerikanske matematikern George Dantzig och är i dag den i särklass mest använda algoritmen för att lösa LP-problem som nästan helt dominerar den kommersiella marknaden.
- Симплекс-метод — метод розв'язання задачі лінійного програмування, в якому здійснюється скерований рух по опорних планах до знаходження оптимального розв'язку; симплекс-метод також називають методом поступового покращення плану.
|
![[RDF Data]](/statics/sw-cube.png)
