Spisu treści:
Definicja - Co oznacza metoda Simplex?
Metoda simpleks w optymalizacji matematycznej jest dobrze znanym algorytmem stosowanym do programowania liniowego. Według czasopisma Computing in Science & Engineering ta metoda jest uważana za jeden z 10 najlepszych algorytmów, które powstały w XX wieku.
Metoda simpleks przedstawia zorganizowaną strategię oceny wierzchołków wykonalnego regionu. Pomaga to ustalić optymalną wartość funkcji celu.
George Dantzig opracował metodę simpleks w 1946 roku.
Metoda ta znana jest również jako algorytm simpleks.
Techopedia wyjaśnia metodę Simplex
Metoda simpleks służy do wyeliminowania problemów w programowaniu liniowym. Bada kolejno sąsiednie wierzchołki zestawu wykonalnego, aby upewnić się, że przy każdym nowym wierzchołku funkcja celu zwiększa się lub pozostaje nienaruszona. Ogólnie rzecz biorąc, metoda simpleks jest niezwykle potężna, co zwykle zajmuje co najwyżej 2–3 m iteracji (tutaj m oznacza zakres ograniczeń równości) i zbiega się w przewidywanym czasie wielomianowym dla określonych rozkładów losowych danych wejściowych.
Metoda simpleks wykorzystuje systematyczną strategię do generowania i testowania kandydujących rozwiązań wierzchołków programu liniowego. Przy każdej iteracji wybiera zmienną, która może dokonać największej modyfikacji w kierunku minimalnego rozwiązania. Ta zmienna następnie zastępuje jedną ze zmiennych towarzyszących, która najbardziej ją drastycznie ogranicza, przenosząc w ten sposób metodę simpleks na inną część zestawu rozwiązań w kierunku rozwiązania końcowego.
Ponadto metoda simplex jest w stanie ocenić, czy nie istnieje żadne rozwiązanie. Można zaobserwować, że algorytm jest zachłanny, ponieważ wybiera najlepszą opcję przy każdej iteracji, bez zapotrzebowania na informacje z wcześniejszych lub przyszłych iteracji.
Czasami podstawowa struktura danych stosowana metodą simpleks jest nazywana słownikiem. Słowniki zawierają ilustrację zestawu równań, które są odpowiednio dostosowane do istniejącej podstawy. Słowniki mogą służyć do intuicyjnego zrozumienia, dlaczego wszystkie zmienne wchodzą i wychodzą z podstawy.
