Симплексный метод и его применение

Любое графическое решение задач, поставленных в линейном программировании, определяет, что наиболее правильное (оптимальное) решение любой из задач полностью ассоциируется с крайней точкою множества (или угловой точкой пространства). На этой идее основывается алгебраический общий симплексный метод решения задач, который позволяет решать абсолютно любую задачу программирования.

Видео: Математика. Урок 1.5. Линейная алгебра. Симплекс-метод решения задачи линейного программирования

Чтобы перейти от геометрического способа решения задач к решению, использующему симплекс-метод линейного программирования, необходимо провести описание всех крайних точек пространства, применяя алгебраические методы. Для выполнения указанного преобразования необходимо привести любую задачу программирования в стандартную форму (также называемую канонической).

Для этого необходимо сделать следующие шаги:

• преобразовать в равенства все неравенства ограничений (реализуется при помощи введения дополнительных новых переменных);
• задачу максимизации необходимо преобразовать в задачу минимизации;
• необходимо получить неотрицательные переменные, преобразовав в них все свободные.

Видео: Теория игр. Лекция 5. Симплекс-метод. Часть 1

Полученная в итоге всех преобразований форма задачи стандартного вида, позволит определить базисное решение. Которое, в свою очередь, четко определяет все угловые точки пространства. Впоследствии симплексный метод позволит найти самое оптимальное решение из всех полученных базисных.

Главное, что выполняет подобный метод решения алгебраических заданий на практике – это последовательное и постоянное улучшение выполнения плана, результатом которого является реализация поставленных задач с максимальной долей эффективности. Основное, что необходимо сделать для получения желаемого результата – это правильно его реализовать в математическом и программном виде.

Итогом всех разработок должен стать симплексный метод, который представляет собой особую вычислительную процедуру, основанную на постоянном улучшении каждого последующего решения. Это происходит путем попарного сравнения всех точек плоскости и нахождения оптимальной.

Видео: Осциллятор "MACD" и его применение

Давно доказано, что весь поиск оптимального решения (в случае, если таковое имеется) завершается за целое и конечное количество шагов. Единственным исключением, которое не может обработать симплексный метод – это «вырожденная задача». При этом происходит так называемое «зацикливание», что приводит к постоянному повторению одних и тех же задач бесконечное количество раз.

Симплексный метод был разработан еще в 1947 году. Его «родителем» стал математик из США Джордж Данциг. В виду того, что симплексный метод обладает столь давней историей, сейчас он является одним из самых изученных и максимально эффективных для поиска оптимальных решений любых задач, стоящих перед человеком.

Видео: 87. Применение метода Вайкоффа на ФОРТС

Метод пошаговой оптимизации значительно упрощает любую деятельность общества. Его можно использовать как в научной, так и в производственной сферах. Его широкое применение поможет принимать математически обоснованные правильные решения сложных задач.