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

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

ВНИМАНИЕ! Работа на этой странице представлена для Вашего ознакомления в текстовом (сокращенном) виде. Для того, чтобы получить полностью оформленную работу в формате Word, со всеми сносками, таблицами, рисунками (вместо pic), графиками, приложениями, списком литературы и т.д., необходимо скачать работу.

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

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

[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.


Скачиваний: 1
Просмотров: 0
Скачать реферат Заказать реферат