Съдържание:
Определение - Какво означава Simplex метод?
Симплексният метод в математическата оптимизация е добре известен алгоритъм, използван за линейно програмиране. Според списанието Computing in Science & Engineering, този метод се счита за един от топ 10 алгоритмите, възникнали през ХХ век.
Симплексният метод представя организирана стратегия за оценка на върховете на изпълним регион. Това помага да се установи оптималната стойност на обективната функция.
Джордж Данциг разработва симплексния метод през 1946г.
Методът е известен още като симплекс алгоритъм.
Техопедия обяснява симплексния метод
Симплексният метод се използва за премахване на проблемите в линейното програмиране. Той разглежда последователно съседните върхове на изпълнимото множество, за да гарантира, че при всяка нова върха, обективната функция се увеличава или не се влияе. Като цяло симплексният метод е изключително мощен, който обикновено отнема най-много 2m до 3m итерации (тук m обозначава обхвата на ограничения за равенство) и се сближава в очакваното полиномно време за специфични разпределения на произволен вход.
Симплексният метод използва систематична стратегия за генериране и тестване на вершинните решения на кандидатите на линейна програма. При всяка итерация той избира променливата, която може да направи най-голямата промяна спрямо минималното решение. След това тази променлива замества една от нейните променливи, което най-драстично я ограничава, като по този начин прехвърля симплексния метод към друга част от набора от решения и към крайното решение.
Освен това симплексният метод е в състояние да прецени дали всъщност няма решение. Може да се отбележи, че алгоритъмът е алчен, тъй като избира най-добрия вариант при всяка итерация, без търсене на информация от по-ранни или предстоящи итерации.
Понякога основната структура на данни, прилагана чрез симплексния метод, се нарича речник. Речниците включват илюстрация на набора от уравнения, които са добре настроени към съществуващата основа. Речниците могат да се използват, за да предложат интуитивно разбиране защо всички променливи влизат и напускат основата.
