Математика

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



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


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

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

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

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


смотреть на рефераты похожие на "Решение задачи линейного программирования "