Рефераты по теме Математика

Реферат Решение задачи линейного программирования скачать бесплатно

Скачать реферат бесплатно ↓ [28.73 KB]

Текст реферата Решение задачи линейного программирования

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

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

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

Метод исключения Жордана-Гаусса для системы линейных уравнений. Большинство из существующих численных методов решения задач линейного программирования использует идею приведения системы линейных уравнений

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

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

Симплекс-метод. Симплекс –метод, метод последовательного улучшения плана, является в настоящее время основным методом решения задач ЛП.
Рассмотрим каноническую задачу ЛП

где векторы  и  и будем предполагать, что все угловые точки  являются невырожденными.
, где вектор  определяется формулой
Теорема. Если в угловой точке  выполняется условие  — решение задачи (2).
Теорема. Для того, чтобы угловая точка  являлась решением задачи (2), необходимо и достаточно, чтобы в ней выполнялось условие
Алгоритм симплекс-метода. Переход из старой угловой точки  в новую угловую точку  состоит, в сущности, лишь в изменении базисной матрицы  вводится вектор
Шаг 0. Задать целевой вектор  и множество базисных индексов  и вектор
Шаг 1. Вычислить матрицу  и вектор
Шаг 2. Вычислить вектор потенциалов  и оценки
Шаг 3. Если  для всех  — базисный вектор оптимального плана; иначе перейти на шаг 4.
Шаг 4. Выбрать произвольный индекс  и вычислить вектор
Шаг 5. Если
Шаг 6. Сформировать множество индексов  и вычислить
Шаг 7. В множестве  индекс  заменить на индекс  — вектор  — на вектор  — компоненту  на