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