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

/>(1)

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

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

Метод исключения Жордана-Гаусса для системы линейныхуравнений.

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

/>

которая в матричной формезаписывается в виде />, к более удобномувиду с помощью так называемого метода Жордада-Гаусса.

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

Аналогичная операциясовершается поочередно с каждым уравнением системы; при этом всякий разпреобразуются все уравнения и выполняется список базисных переменных.

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

/>, />,

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

Полученную системыуравнений называют приведенной системой, соответствующей множеству /> номеров базисныхпеременных.

Симплекс-метод.

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

Рассмотрим каноническуюзадачу ЛП

/>(2)

где векторы />, матрица /> и />. Множество планов в задаче(2) будем обозначать через /> и будемпредполагать, что все угловые точки /> являютсяневырожденными.

/>, где вектор /> определяется формулой />.

Теорема. Если в угловой точке /> выполняется условие />, то /> — решение задачи (2).

Теорема. Для того, чтобы угловая точка /> являлась решением задачи(2), необходимо и достаточно, чтобы в ней выполнялось условие />.

Алгоритм симплекс-метода.

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

Шаг 0. Задать целевой вектор />, матрицу условий />, вектор ограничений /> и множество базисныхиндексов />. Сформировать базиснуюматрицу /> и вектор />.

Шаг 1. Вычислитьматрицу /> и вектор />.

Шаг 2. Вычислитьвектор потенциалов /> и оценки />.

Шаг 3. Если /> для всех />, то остановиться: вектор /> — базисный вектороптимального плана; иначе перейти на шаг 4.

Шаг 4. Выбратьпроизвольный индекс /> и вычислитьвектор />.

Шаг 5. Если />, то остановиться: />; иначе перейти на шаг 6.

Шаг 6. Сформироватьмножество индексов /> и вычислить />.

Шаг 7. В множестве /> индекс /> заменить на индекс />, в матрице /> — вектор /> — на вектор />, в векторе /> — компоненту /> на />. Перейти на шаг 1.