Решение задачи линейного программирования

  • Просмотров 1462
  • Скачиваний 202
  • Размер файла 28
    Кб

Решение задачи линейного программирования. Рассмотрим задачу линейного программирования (1) Теорема. Если множество планов задачи (1) не пусто и целевая функция сверху ограничена на этом множестве, то задача (1) имеет решение. Теорема. Если множество допустимых планов имеет крайние точки и задача (1) имеет решение, то среди крайних точек найдется оптимальная. Метод исключения Жордана-Гаусса для системы линейных уравнений.

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

Переменная называется базисной переменной. Аналогичная операция совершается поочередно с каждым уравнением системы; при этом всякий раз преобразуются все уравнения и выполняется список базисных переменных. Результатом применения метода Жордада-Гаусса является следующее: либо устанавливается, что система несовместна, либо выявляются и отбрасываются все «лишние» уравнения; при этом итоговая система уравнений имеет вид где

— список номеров базисных переменных, — множество номеров небазисных переменных. Здесь — ранг матрицы коэффициентов исходной системы уравнений. Полученную системы уравнений называют приведенной системой, соответствующей множеству номеров базисных переменных. Симплекс-метод. Симплекс –метод, метод последовательного улучшения плана, является в настоящее время основным методом решения задач ЛП. Рассмотрим каноническую

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