Симплексный метод и его применение
Любое графическое решение задач, поставленных в линейном программировании, определяет, что наиболее правильное (оптимальное) решение любой из задач полностью ассоциируется с крайней точкою множества (или угловой точкой пространства). На этой идее основывается алгебраический общий симплексный метод решения задач, который позволяет решать абсолютно любую задачу программирования.
Чтобы перейти от геометрического способа решения задач к решению, использующему симплекс-метод линейного программирования, необходимо провести описание всех крайних точек пространства, применяя алгебраические методы. Для выполнения указанного преобразования необходимо привести любую задачу программирования в стандартную форму (также называемую канонической).
Для этого необходимо сделать следующие шаги:
- преобразовать в равенства все неравенства ограничений (реализуется при помощи введения дополнительных новых переменных);
- задачу максимизации необходимо преобразовать в задачу минимизации;
- необходимо получить неотрицательные переменные, преобразовав в них все свободные.
Полученная в итоге всех преобразований форма задачи стандартного вида, позволит определить базисное решение. Которое, в свою очередь, четко определяет все угловые точки пространства. Впоследствии симплексный метод позволит найти самое оптимальное решение из всех полученных базисных.
Главное, что выполняет подобный метод решения алгебраических заданий на практике – это последовательное и постоянное улучшение выполнения плана, результатом которого является реализация поставленных задач с максимальной долей эффективности. Основное, что необходимо сделать для получения желаемого результата – это правильно его реализовать в математическом и программном виде.
Итогом всех разработок должен стать симплексный метод, который представляет собой особую вычислительную процедуру, основанную на постоянном улучшении каждого последующего решения. Это происходит путем попарного сравнения всех точек плоскости и нахождения оптимальной.
Давно доказано, что весь поиск оптимального решения (в случае, если таковое имеется) завершается за целое и конечное количество шагов. Единственным исключением, которое не может обработать симплексный метод – это «вырожденная задача». При этом происходит так называемое «зацикливание», что приводит к постоянному повторению одних и тех же задач бесконечное количество раз.
Симплексный метод был разработан еще в 1947 году. Его «родителем» стал математик из США Джордж Данциг. В виду того, что симплексный метод обладает столь давней историей, сейчас он является одним из самых изученных и максимально эффективных для поиска оптимальных решений любых задач, стоящих перед человеком.
Метод пошаговой оптимизации значительно упрощает любую деятельность общества. Его можно использовать как в научной, так и в производственной сферах. Его широкое применение поможет принимать математически обоснованные правильные решения сложных задач.