Реферат

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

Работа добавлена на сайт bukvasha.net: 2015-10-28

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 11.11.2024


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

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


(1)

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

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

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



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

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

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

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

, ,

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

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

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

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

(2)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Реферат Банкротство и реорганизация
2. Реферат на тему Home Schooling And Internet Technology Essay Research
3. Реферат Дифференцированное обучение учащихся с разной функциональной асимметрией полушарий
4. Реферат Русская зима
5. Реферат Смирна
6. Реферат Социальные утопии как предпосылки социологии
7. Реферат на тему Dream ExpressCollege Admissions Essay Essay Research Paper
8. Реферат на тему Review Glasgow In 1901 By James Hamilton
9. Реферат Судебная система Англии
10. Реферат Битва при Тигранакерте