Симплексные методы решения задач оптимизации в электроэнергетике

Симплексный метод относится к линейному программированию и применяется при решении задач оптимизации при наличии выпуклой целевой функции

и линейных уравнений-ограничений в форме неравенств

или же в матричной форме

Например, при наличии двух оптимизируемых параметров и четырех уравнений ограничений исходная модель имеет вид

Для решения задачи симплексным методом исходная модель приводится к стандартной, канонической форме.

Для этого целевая функция и все уравнения-ограничения приводятся к форме равенств с неотрицательной правой частью. При этом все переменные также неотрицательны

 

 

.

Здесь S_i – вспомогательная переменная, вводимая в i-е уравнение для приведения его к форме равенства, ее знак положителен для неравенств вида и отрицательный для неравенств вида .

В канонической форме для данного примера число ограничений m=4, а число переменных увеличивается до n=6.

 

Рис. 53. Допустимое пространство решений

 

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

Например, уравнение прямой, полученной приравниванием нулю вспомогательной переменной в первом ограничении S₁=0 и проходящей через точки E и F, имеет вид

Точки A, B, C, D, E, F – экстремальные точки допустимого пространства решений, в которых обнуляются n–m переменных.

Суть симплексного метода заключается в том, что оптимальное решение ищется среди экстремальных точек допустимого пространства решений по определенному алгоритму, уменьшающему число переборов.

Например (см. рис. 54), если начальное приближение – точка A, то затем переход осуществляется к смежной точке, но не произвольной, а к той, которая обеспечивает наискорейший рост целевой функции.

 

 

Рис. 54. Геометрическая интерпретация симплексного метода

 

Симплексный метод включает следующие этапы:

1. составление начального базисного решения приравниванием нулю оптимизируемых параметров (в данном примере X₁ и X₂ и исходный базис при этом – S₁, S₂, S₃, S₄, см. табл. 3);

 

Табл. 3. Начальное базисное решение

Переменные	z	x1	x2	S1	S2	S3	S4	B
Цел. ф-я z		-c1	-c2
БАЗИС	S1		a11	a12					b1
S2		a21	a22					b2
S3		a31	a32					b3
S4		a41	a42					b4

 

2. определение включаемой в новый базис перемененной из числа небазисных переменных по максимальному по модулю отрицательному коэффициенту в z-строке (что соответствует наискорейшему росту целевой функции) или по наибольшему положительному при решении задачи максимизации (столбец, соответствующий включаемой переменной, является ведущим столбцом k);

3. определение исключаемой из базиса переменной по наименьшему положительному отношению правой части соответствующего ограничения к элементу ведущего столбца b_i/a_ik (строка, соответствующая исключаемой переменной, является ведущей строкой r, Элемент на пересечении ведущей строки и ведущего столбца является ведущим элементом a_rk);

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

если i=r (т.е. для элементов ведущей строки),

 

если i≠r (т.е. для всех остальных элементов).

 

Табл. 4. Новое базисное решение

Переменные	z	x1	x2	S1	S2	S3	S4	B
Цел. ф-я			…	…	…	…	…
БАЗИС	…	…	…	…	…	…	…	…	…
…	…	…	…	…	…	…	…	…
…	…	…	…	…	…	…	…	…
…			…	…	…	…	…

 

 

Метод искусственного базиса

 

Данный метод применяется в тех случаях, когда в системе имеются ограничения со знаками ≤, ≥, = и является модификацией ранее рассмотренного табличного симплексного метода.

Решение производится путем введения в целевую функцию и ограничения искусственных переменных со знаками, зависящими от типа оптимума. Для исключения искусственных переменных из базиса они вводятся в целевую функцию с большими отрицательными коэффициентами –М или с большими положительными при решении задачи минимизации.

Если в базисе отсутствуют искусственные переменные (все искусственные переменные исключены из базиса), то решение признается оптимальным.

Исходная модель включает целевую функцию

 

 

и систему ограничений, включающую m ограничений-неравенств

и k ограничений-равенств

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

.

В этой модели имеют место n ограничений неравенств по максимальной мощности электростанций и два ограничения равенства из условий мгновенного и долгосрочного баланса мощностей

 

,

где

E_n – нормативный коэффициент эффективности капиталовложений в энергетике,

K_0i – капитальные вложения на единицу установленной мощности для i-й электростанции, [руб/МВт],

P_iуст – установленная мощность i-й электростанции, [МВт],

T_maxi – время использования максимальной мощности i-й электростанции, [час],

γ_i – стоимость топлива для выработки электроэнергии для i-й электростанции, [руб/ кВт*ч],

P_imax – максимальная мощность i-й электростанции, [МВт],

P_н – мощность нагрузки, [МВт].

 

Алгоритм метода искусственного базиса включает следующие этапы:

1. введение в ограничения-неравенства вспомогательных переменных X_n+1….X_n+m для приведения ограничений к канонической форме;

2. введение в целевую функцию и все ограничения m+k искусственных переменных X_n+m+1….X_n+2m+k, в процессе которого модель приобретает вид

 

;

 

 

3. составление начального базисного решения (см. табл. 5),

Табл. 5. Начальное базисное решение

Переменные

X1

Xn

Xn+1

Xn+m

Xn+m+1

Xn+2m+k

B

Cб

Цел. ф-я

C1

…

Cn

…

–M

…

–M

–M

БАЗИС

Xn+m+1

a1,1

…

a1,n

…

b1

…

…

…

…

…

…

…

…

…

…

…

…

–M

Xn+2m

am,1

…

am,n

…

bm

–M

Xn+2m+1

am+1,1

…

am+1,n

…

…

bm+1

…

…

…

…

…

…

…

…

…

…

…

…

–M

Xn+2m+k

am+k,1

…

am+k,n

…

…

bm+k

Искусственная цел. ф-я, z

z1

…

zn

zn+1

…

zn+m

zn+m+1

…

zn+2m+k

 

где

;

4. определение включаемой в новый базис перемененной из числа небазисных переменных по максимальному по модулю отрицательному коэффициенту в z-строке искусственной целевой функции (столбец, соответствующий включаемой переменной, является ведущим столбцом k);

5. определение исключаемой из базиса переменная по наименьшему положительному отношению правой части соответствующего ограничения к элементу ведущего столбца b_i/a_ik. (строка, соответствующая исключаемой переменной, является ведущей строкой r, элемент на пересечении ведущей строки и ведущего столбца является ведущим элементом a_rk);

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

если i=r (т.е. для элементов ведущей строки),

 

если i≠r (т.е. для всех остальных элементов).

Этот алгоритм повторяется до тех пор, пока из базиса не будут удалены все искусственные переменные.

 

Модифицированный симплексный метод

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

Данный метод также называется методом обратной матрицы.

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

Использование данного метода особенно эффективно при n>>m.

Общие и отличительные черты модифицированного симлексного метода относительно ранее рассмотренных показаны в табл. 6.

Табл. 6. Традиционные и отличительные черты модифицированного симплексного метода

Традиционные черты решения задач линейного программирования	Отличительные черты
1. Приведение модели к канонической форме	1. Наличие двух таблиц: основной и вспомогательной
2. Коррекция базиса методом исключения Жордана-Гаусса	2.Порядок их заполнения
3. Проверка условия оптимальности	3. Особенности расчетных формул