(1)
Теорема. Если множество 
планов задачи (1) не пусто и целевая функция 
сверху ограничена на этом множестве, то задача (1) имеет решение.
Теорема. Если множество допустимых планов имеет крайние точки и задача (1) имеет решение, то среди крайних точек найдется оптимальная.
Метод исключения Жордана-Гаусса для системы линейных уравнений.
Большинство из существующих численных методов решения задач линейного программирования использует идею приведения системы линейных уравнений
которая в матричной форме записывается в виде 
, к более удобному виду с помощью так называемого метода Жордада-Гаусса.
В первом уравнении системы отыскивается коэффициент 
, отличный от нуля. С помощью этого коэффициента обращаются в нуль коэффициенты при переменной 
в остальных уравнениях системы. Для этого первое уравнение умножается на число 
и прибавляется к уравнению с номером 
, 
. Затем первое уравнение делится на число . Это преобразование называется элементарным преобразованием. Полученная эквивалентная система обладает тем свойством, что переменная присутствует только в первом уравнении, и притом с коэффициентом 1. Переменная называется базисной переменной.
Аналогичная операция совершается поочередно с каждым уравнением системы; при этом всякий раз преобразуются все уравнения и выполняется список базисных переменных.
Результатом применения метода Жордада-Гаусса является следующее: либо устанавливается, что система несовместна, либо выявляются и отбрасываются все «лишние» уравнения; при этом итоговая система уравнений имеет вид
, 
,
где 
— список номеров базисных переменных, 
— множество номеров небазисных переменных. Здесь 
— ранг матрицы 
коэффициентов исходной системы уравнений.
Полученную системы уравнений называют приведенной системой, соответствующей множеству 
номеров базисных переменных.
Симплекс-метод.
Симплекс –метод, метод последовательного улучшения плана, является в настоящее время основным методом решения задач ЛП.
Рассмотрим каноническую задачу ЛП
(2)
где векторы 
, матрица 
и 
. Множество планов в задаче (2) будем обозначать через и будем предполагать, что все угловые точки 
являются невырожденными.
, где вектор 
определяется формулой 
.
Теорема. Если в угловой точке 
выполняется условие 
, то — решение задачи (2).
Теорема. Для того, чтобы угловая точка 
являлась решением задачи (2), необходимо и достаточно, чтобы в ней выполнялось условие .
Алгоритм симплекс-метода.
Переход из старой угловой точки в новую угловую точку 
состоит, в сущности, лишь в изменении базисной матрицы 
, в которую вместо вектора 
вводится вектор 
. Новая базисная матрица может быть теперь использована для вычисления базисных компонентов вектора . Таким образом, алгоритм симплекс-метода может быть представлен в следующей форме.
Шаг 0. Задать целевой вектор 
, матрицу условий , вектор ограничений 
и множество базисных индексов 
. Сформировать базисную матрицу 
и вектор 
.
Шаг 1. Вычислить матрицу 
и вектор 
.
Шаг 2. Вычислить вектор потенциалов 
и оценки 
.
Шаг 3. Если 
для всех 
, то остановиться: вектор 
— базисный вектор оптимального плана; иначе перейти на шаг 4.
Шаг 4. Выбрать произвольный индекс 
и вычислить вектор 
.
Шаг 5. Если 
, то остановиться: 
; иначе перейти на шаг 6.
Шаг 6. Сформировать множество индексов 
и вычислить 
.
Шаг 7. В множестве 
индекс 
заменить на индекс 
, в матрице 
— вектор 
— на вектор , в векторе 
— компоненту 
на 
. Перейти на шаг 1.
Похожие работы
... лучей, исходящих из одной точки, называется многогранным выпуклым конусом с вершиной в данной точке. 1.4 Математические основы решения задачи линейного программирования графическим способом 1.4.1 Математический аппарат Для понимания всего дальнейшего полезно знать и представлять себе геометрическую интерпретацию задач линейного программирования, которую можно дать для случаев n = 2 и n = ...
... игр, теория массового обслуживания, и др. 1. ПОСТАНОВКА ЗАДАЧИ Целью нашего курсового проекта является решение задачи линейного программирования графическим методом. 1.1 Математическое программирование. Математическое программирование ("планирование") – это раздел математики, занимающийся разработкой методов отыскания экстремальных значений функции, на аргументы которой наложены ...
... . 1.3. Построение ограничений и градиента целевой функции : 1.4. Область допустимых решений – отрезок AB. 1.5. Точка А – оптимальная. Координаты т. А: ; ; . 2. Решение задачи линейного программирования симплекс-методом. Прямая задача. Задачу линейного программирования для любой вершины в компактной форме можно представить в виде: Для получения используем алгоритм, приведённый в ...
... задачи линейного программирования, они очень сложны и решаются специальными, обычно многостадийными приемами с использованием эвристических элементов. 3. Решение задач 3.1. Решение задачи линейного программирования 3.1.1.Постановка задачи Сформулируем задачу: Определить значения переменных, обеспечивающие минимизацию целевой функции. Составим целевую функцию и зададим ограничения. ...
0 комментариев