Преамбула
Собственно, зачем. Когда-то мои поиски качественного описания симплекс-метода заняли уйму времени. Для того, чтобы прочие не страдали, я постараюсь изложить более полную информацию о решении задач данным способом. Кому-то, возможно, эта тема покажется далекой от IT, однако она полезней, чем подумают многие. Скажем даже больше, до наступления эры квантовых компьютеров оптимизация будет играть ключевую роль в работе настоящих программистов. Статья довольно тяжелая, но при надобности можно и потерпеть.
Постановка
Крайне важную нишу в методах оптимизации занимают задачи линейного программирования (ЛП). Они заключаются в минимизации (или максимизации) целевого линейного функционала на многомерном пространстве при наличии ограничений, заданных в виде линейных неравенств. Формально каноническая задача ЛП выглядит следующим образом:
Требуется найти 
при заданных ограничениях 
. Для ясности: x — вектор переменных, C — вектор коэффициентов (C^T[N]*x[N] и задает линейный функционал). Матрица А является матрицей полного ранга, иначе говоря rang A[M, N] = min(M, N).
Приведем тривиальный пример. Допустим, мы ищем 
при условиях: 
Для лучшего представления прикладываю график множества ограничений:
Читать полностью »
