Название: Решение задачи линейного программирования
Вид работы: реферат
Рубрика: Математика
Размер файла: 81.52 Kb
Скачать файл: referat.me-218071.docx
Краткое описание работы: Рассмотрим задачу линейного программирования Теорема . Если множество планов задачи (1) не пусто и целевая функция сверху ограничена на этом множестве, то задача (1) имеет решение.
Решение задачи линейного программирования
.
Рассмотрим задачу линейного программирования
(1)
Теорема
. Если множество планов задачи (1) не пусто и целевая функция
сверху ограничена на этом множестве, то задача (1) имеет решение.
Теорема
. Если множество допустимых планов имеет крайние точки и задача (1) имеет решение, то среди крайних точек найдется оптимальная.
Метод исключения Жордана-Гаусса для системы линейных уравнений.
Большинство из существующих численных методов решения задач линейного программирования использует идею приведения системы линейных уравнений
которая в матричной форме записывается в виде , к более удобному виду с помощью так называемого метода Жордада-Гаусса.
В первом уравнении системы отыскивается коэффициент , отличный от нуля. С помощью этого коэффициента обращаются в нуль коэффициенты при переменной
в остальных уравнениях системы. Для этого первое уравнение умножается на число
и прибавляется к уравнению с номером
,
. Затем первое уравнение делится на число
. Это преобразование называется элементарным преобразованием. Полученная эквивалентная система обладает тем свойством, что переменная
присутствует только в первом уравнении, и притом с коэффициентом 1. Переменная
называется базисной переменной.
Аналогичная операция совершается поочередно с каждым уравнением системы; при этом всякий раз преобразуются все уравнения и выполняется список базисных переменных.
Результатом применения метода Жордада-Гаусса является следующее: либо устанавливается, что система несовместна, либо выявляются и отбрасываются все «лишние» уравнения; при этом итоговая система уравнений имеет вид
,
,
где — список номеров базисных переменных,
— множество номеров небазисных переменных. Здесь
— ранг матрицы
коэффициентов исходной системы уравнений.
Полученную системы уравнений называют приведенной системой, соответствующей множеству номеров базисных переменных.
Симплекс-метод.
Симплекс –метод, метод последовательного улучшения плана, является в настоящее время основным методом решения задач ЛП.
Рассмотрим каноническую задачу ЛП
(2)
где векторы , матрица
и
. Множество планов в задаче (2) будем обозначать через
и будем предполагать, что все угловые точки
являются невырожденными.
, где вектор
определяется формулой
.
Теорема
. Если в угловой точке выполняется условие
, то
— решение задачи (2).
Теорема
. Для того, чтобы угловая точка являлась решением задачи (2), необходимо и достаточно, чтобы в ней выполнялось условие
.
Алгоритм симплекс-метода.
Переход из старой угловой точки в новую угловую точку
состоит, в сущности, лишь в изменении базисной матрицы
, в которую вместо вектора
вводится вектор
. Новая базисная матрица может быть теперь использована для вычисления базисных компонентов вектора
. Таким образом, алгоритм симплекс-метода может быть представлен в следующей форме.
Шаг 0.
Задать целевой вектор , матрицу условий
, вектор ограничений
и множество базисных индексов
. Сформировать базисную матрицу
и вектор
.
Шаг 1. Вычислить матрицу и вектор
.
Шаг 2. Вычислить вектор потенциалов и оценки
.
Шаг 3. Если для всех
, то остановиться: вектор
— базисный вектор оптимального плана; иначе перейти на шаг 4.
Шаг 4. Выбрать произвольный индекс и вычислить вектор
.
Шаг 5. Если , то остановиться:
; иначе перейти на шаг 6.
Шаг 6. Сформировать множество индексов и вычислить
.
Шаг 7. В множестве индекс
заменить на индекс
, в матрице
— вектор
— на вектор
, в векторе
— компоненту
на
. Перейти на шаг 1.
Похожие работы
-
Математические модели в экономике и программировании
Детерминированные и вероятностные математические модели в экономике. Преимущества и недостатки. Постановка задачи линейного программирования на примере задачи о пищевом рационе.
-
Решение задачи линейного программирования симплексным методом
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение Высшего профессионального образования «Волгоградский государственный технический университет»
-
Риск в задачах линейного программирования
Лабораторная работа №3 Риск в задачах линейного программирования. Задание Предприятие выпускает 2 вида продукции в объмах Н1 и Н2. Известен случайный вектор ограничений -
-
Решение задач линейного программирования
Министерство общего и профессионального образования Российской Федерации Воронежский Государственный Архитектурно – Строительный Университет
-
Постановка задачи линейного программирования и двойственная задача линейного программирования.
Линейное программирование является составной частью раздела математики, который изучает методы нахождения условного экстремума функции многих переменных и называется математическим программированием. В классическом математическом анализе рассматривается задача отыскания условного экстремума функции.
-
Задача линейного программирования
Юридический техникум Рассмотрено и одобрено ПЦК г. Кропоткин программирования Председатель ПЦК Покалицына О.В. План чтения лекции по учебной дисциплине
-
Метод ветвей и границ контрольная
Министерство образования Р.Ф. Тюменский государственный нефтегазовый университет Институт нефти и газа Кафедра менеджмента В отраслях ТЭК Контрольная работа по
-
Задачи по Математике 3
Задача 1 Решить графическим методом задачу линейного программирования А) найти область допустимых значений многоугольник решений Б) найти оптимумы целевой функции
-
Линейное программирование 3
БАЛТИЙСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ РЫБОПРОМЫСЛОВОГО ФЛОТА РФ ИНСТИТУТ ПРИКЛАДНОЙ ЭКОНОМИКИ И МЕНЕДЖМЕНТА КАФЕДРА «МЕНЕДЖМЕНТ» Контрольная работа
-
Математические методы методы
Общая задача линейного программирования Общей задачей линейного программирования называется задача, которая состоит в определении максимального или минимального значения функции