🗊Презентация Методы оптимальных решений. Симплексный метод

Дисциплина МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ Кафедра математических методов в экономике

СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗЛП Введение. Определение К-матрицы в КЗЛП Переход от одной К-матрицы КЗЛП к другой К-матрице Симплекс-разность К-матрицы КЗЛП Способ построения опорного плана, более близкого к оптимальному Критерий оптимальности опорного плана Критерий отсутствия конечного решения Алгоритм симплексного метода Пример 1 Пример 2

Пусть требуется решить задачу (1) Или (2)

Так как решением задачи (2) является крайняя точка множества Р ее допустимых решений, или, что то же самое, неотрицательное базисное решение системы линейных уравнений , то метод решения задачи (1) должен содержать 4 момента: Так как решением задачи (2) является крайняя точка множества Р ее допустимых решений, или, что то же самое, неотрицательное базисное решение системы линейных уравнений , то метод решения задачи (1) должен содержать 4 момента: 1) обоснование способа перехода от одного опорного плана (К-матрицы) к другому; 2) указание признака оптимальности, позволяющего проверить, является ли данный опорный план оптимальным; 3) указание способа построения нового опорного плана, более близкого к оптимальному; 4) указание признака отсутствия конечного решения.

Определение К-матрицы в КЗЛП Рассмотрим каноническую задачу линейного программирования (КЗЛП): Будем считать, что ранг матрицы А равен m, причем m<n. Запишем КЗЛП в векторном виде: (*) где – j-й столбец матрицы А. Дадим одно из определений опорного плана. ОП ЗЛП будем называть такой план , что векторы , входящие в разложение со строго положительными , линейно независимы. К-матрицей КЗЛП будем называть расширенную матрицу системы линейных уравнений, равносильной системе (*), содержащую единичную подматрицу на месте первых n своих столбцов и все элементы (n+1)-го которой неотрицательны. Число К-матриц конечно и не превышает . Каждая К-матрица определяет ОП КЗЛП и наоборот.

Переход от одной К-матрицы ЗЛП к другой К-матрице. Пусть известна К-матрица (3) Обозначим через вектор номеров базисных (единичных) столбцов матрицы , - вектор, компоненты которого есть базисные компоненты опорного плана, определяемого матрицей , и могут быть отличны от нуля.

Возьмем в матрице столбец К , не принадлежащий единичной подматрице ( , ) и такой, что в этом столбце есть хотя бы один отличный от нуля элемент. Возьмем в матрице столбец К , не принадлежащий единичной подматрице ( , ) и такой, что в этом столбце есть хотя бы один отличный от нуля элемент. Пусть . Считая направляющим элементом, совершим над матрицей один шаг метода Жордана-Гаусса. В результате получим новую матрицу , элементы которой выражаются через элементы матрицы по следующим формулам:

Симплекс-разность К-матриц ЗЛП. Изменение функции при переходе от одной К-матрицы к другой.

Способ построения опорного плана (матрицы ), более близкого к оптимальному, чем

Критерий оптимальности опорного плана Теорема 3 Пусть все симплекс - разности матрицы неотрицательные. Тогда опорный план , определяемый матрицей , является оптимальным.

Критерий отсутствия конечного решения. Теорема 4 Пусть в матрице есть , и в столбце ( , ) нет ни одного положительного элемента. Тогда ЗЛП (1) не имеет конечного решения.

Алгоритм симплекс-метода Пусть известна исходная К-матрица ЗЛП, определяющая исходный опорный план Последовательно строятся К-матрицы ЗЛП, пока не выполнится критерий оптимальности или критерий, позволяющий убедиться в отсутствии конечного решения. Рассмотрим алгоритм S-ой итерации симплекс-метода. В начале S-ой итерации имеем К-матрицу ЗЛП, определяющую опорный план

Шаг 1. Шаг 1. Вычисляем для столбцов матрицы , симплекс-разности и находим номер К из условия Шаг 2. Если , то опорный план является оптимальным, а есть оптимальное значение линейной формы , иначе переходим к шагу 3 Шаг 3. Если то ЗЛП не имеет конечного решения. Иначе находим номер L из условия ; направляющий элемент на S-ой итерации метода есть элемент

Шаг 4. Шаг 4. Вычисляем компоненты вектора : Шаг 5. Производим один шаг метода Жордана-Гаусса с направляющим элементом . Присваиваем переменной S алгоритма значение S+1 и переходим к шагу 1.

Пример 1 Симплекс-методом решить ЗЛП: (1) (2)

Приводим систему линейных неравенств (2) к каноническому виду, вводя в каждое неравенство дополнительную переменную Приводим систему линейных неравенств (2) к каноническому виду, вводя в каждое неравенство дополнительную переменную , . Получим систему линейных уравнений: (3)

Целевая функция (1) будет иметь вид Целевая функция (1) будет иметь вид Расширенная матрица системы линейных уравнений (3) является исходной К-матрицей ЗЛП, которая определяет исходный опорный план:

Введём следующие обозначения: Введём следующие обозначения: S-номер итерации i-номера строк таблицы -номера столбцов, образующих единичную подматрицу -коэффициенты целевой функции при столбцах, образующих единичную подматрицу -соответствуют переменным задачи -сначала содержит правые части системы уравнений , в конце алгоритма - искомые значения переменных -для вычисления значений

Результаты последовательных итераций симплекс-алгоритма оформим в виде симплекс-таблицы. Результаты последовательных итераций симплекс-алгоритма оформим в виде симплекс-таблицы.

Пересчёт таблицы

На второй итерации S=2, все следовательно, опорный план На второй итерации S=2, все следовательно, опорный план определяемый К-матрицей , оптимальный, Оптимальное значение линейной формы равно:

Пример 2 Симплекс-методом решить ЗЛП: (4) (5) Приводим ЗЛП (4-5) к каноническому виду (6)

Результаты последовательных итераций запишем в симплекс-таблицу. Результаты последовательных итераций запишем в симплекс-таблицу.

Из симплекс-таблицы при S=2 следует, что согласно шагу 3 Из симплекс-таблицы при S=2 следует, что согласно шагу 3 симплекс-алгоритма, данная ЗЛП не имеет конечного решения, т.к. отрицательная симплекс-разность соответствует столбцу , все элементы которого неположительны. Итак,

Список литературы Мастяева И.Н., Горемыкина Г.И., Семенихина О.Н., Методы оптимизации: линейные модели. М.: МЭСИ, 2015. Мастяева И.Н., Горемыкина Г.И., Семенихина О.Н., Исследование операций и методы оптимизации. М.: МЭСИ, 2015. Мастяева И.Н., Горемыкина Г.И., Семенихина О.Н., Методы оптимальных решений. М.: Курс, 2016.