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

«Экономика»,
профиль «Финансы и кредит»

КЗЛП к другой К-матрице
Симплекс-разность К-матрицы КЗЛП
Способ построения опорного плана, более близкого к оптимальному
Критерий оптимальности опорного плана
Критерий отсутствия конечного решения
Алгоритм симплексного метода
Пример 1
Пример 2

(2)

Симплекс-метод решения ЗЛП

ее допустимых решений, или, что то же самое, неотрицательное базисное решение системы линейных уравнений , то метод решения задачи (1) должен содержать 4 момента:

1) обоснование способа перехода от одного опорного плана (К-матрицы) к другому;

2) указание признака оптимальности, позволяющего проверить, является ли данный опорный план оптимальным;

3) указание способа построения нового опорного плана, более близкого к оптимальному;

4) указание признака отсутствия конечного решения.

считать, что ранг матрицы А равен m, причем m Запишем КЗЛП в векторном виде:

(*)

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

ЗЛП к другой К-матрице.

Пусть известна К-матрица

(3)




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

компонент опорного плана, определяемого матрицей , равны нулю. Очевидно, что векторы и полностью задают опорный план, определяемый матрицей Например, пусть:


,




тогда ; и, следовательно, опорный план, определяемый , имеет вид:

Итак, пусть К-матрица (3) определяет невырожденный опорный план


Выберем в матрице столбец , не принадлежащий единичной подматрице, т. е. , , и такой, что в этом столбце есть хотя бы один элемент больше нуля.

Пусть . Считая направляющим элементом, совершим над матрицей один шаг метода Жордана - Гаусса. В результате получим новую матрицу



,

в которой стал единичным, но которая может и не быть К-матрицей, т.к. среди величин могут быть отрицательные.

Пусть в каком-либо столбце К-матрицы - есть хотя бы

один строго положительный элемент ( , ) . Тогда с помощью

одного шага метода Жордана-Гаусса можно построить новую К-матрицу

, выбрав направляющий элемент из условия

линейного программирования, которая определяет невырожденный опорный план

,
,

следовательно,

Остальные n-m компонент опорного плана равны нулю.

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




,


элементы которой выражаются через элементы матрицы по следующим формулам:

одного шага метода Жордана-
Гаусса мы получили L-матрицу ЗЛП, причем компоненты вектора


выражаются по следующим формулам:

(4*)

может и не быть К-матрицей ЗЛП, так как среди величин могут быть отрицательные.

Получим условия, которым должен удовлетворять направляющий элемент , чтобы
.

Из следует, что



тогда и только тогда, когда

(4)
Это первое условие, которое мы должны наложить на выбор
направляющего элемента.

следует, что


тогда и только тогда, когда

(5)

Условие (5) выполняется для всех ,

Перепишем неравенство (5) для строго положительных

в виде (6)

выполняться для всех ,
если выбрать таким, что

(7)

Если минимум в соотношении (7) достигается при одном значении
индекса i, то , т. е. матрица определяет в этом
случае план ЗЛП.
Если минимум в соотношении (7) достигается при нескольких значе-
ниях индекса i ,то


Тогда при

, т.е. матрица
определяет вырожденный опорный план ЗЛП.

(ч.т.д.)

при переходе от одной К-матрицы к другой.

Определение.

Величину

,

где - вектор, компонентами которого являются коэффициенты

линейной функции при базисных ( ) переменных

опорного плана, определяемого матрицей , назовем j-й

симплекс - разностью матрицы .

- опорные планы, определяемые матрицами

и соответственно. Тогда очевидно, что



и

,


где К-номер столбца , вводимого в базис при получении

матрицы из .

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

Теорема 2.

Пусть в матрице есть , и в столбце

( , ) есть хотя бы один строго положительный элемент.

Тогда от матрицы можно перейти к матрице , причем


.

разности матрицы неотрицательные. Тогда опорный план , определяемый матрицей , является оптимальным.

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

определяющая исходный опорный план



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

матрицы , симплекс-разности и находим номер К из условия

Шаг 2.
Если , то опорный план является оптимальным, а есть оптимальное
значение линейной формы , иначе переходим к шагу 3
Шаг 3.
Если то ЗЛП не имеет конечного решения.
Иначе находим номер L из условия
;

направляющий элемент на S-ой итерации метода есть элемент

:



Шаг 5.
Производим один шаг метода Жордана-Гаусса с направляющим

элементом . Присваиваем переменной S алгоритма

значение S+1 и переходим к шагу 1.

(1)



(2)

каждое неравенство дополнительную переменную
, .

Получим систему линейных уравнений:


(3)

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

столбцов, образующих единичную подматрицу

-коэффициенты целевой функции при столбцах, образующих единичную подматрицу

-соответствуют переменным задачи

-сначала содержит правые части системы уравнений , в конце алгоритма - искомые значения переменных

-для вычисления значений

следовательно, опорный план

определяемый К-матрицей , оптимальный,


Оптимальное значение линейной формы равно:

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


Итак,

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