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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Здесь Si – вспомогательная переменная, вводимая в i-е уравнение для приведения его к форме равенства, ее знак положителен для неравенств вида Симплексные методы решения задач оптимизации в электроэнергетике - student2.ru и отрицательный для неравенств вида Симплексные методы решения задач оптимизации в электроэнергетике - student2.ru .

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

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

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

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

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

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

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

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

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

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

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

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

1. составление начального базисного решения приравниванием нулю оптимизируемых параметров (в данном примере X1 и X2 и исходный базис при этом – S1, S2, S3, S4, см. табл. 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. определение исключаемой из базиса переменной по наименьшему положительному отношению правой части соответствующего ограничения к элементу ведущего столбца bi/aik (строка, соответствующая исключаемой переменной, является ведущей строкой r, Элемент на пересечении ведущей строки и ведущего столбца является ведущим элементом ark);

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

Симплексные методы решения задач оптимизации в электроэнергетике - student2.ru если i=r (т.е. для элементов ведущей строки),

Симплексные методы решения задач оптимизации в электроэнергетике - student2.ru если i≠r (т.е. для всех остальных элементов).

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

Переменные z x1 x2 S1 S2 S3 S4 B
Цел. ф-я Симплексные методы решения задач оптимизации в электроэнергетике - student2.ru Симплексные методы решения задач оптимизации в электроэнергетике - student2.ru Симплексные методы решения задач оптимизации в электроэнергетике - student2.ru
БАЗИС
Симплексные методы решения задач оптимизации в электроэнергетике - student2.ru Симплексные методы решения задач оптимизации в электроэнергетике - student2.ru Симплексные методы решения задач оптимизации в электроэнергетике - student2.ru

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где

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

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

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

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

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

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

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

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

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

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

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

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

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

;

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  

где

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

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

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

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

Симплексные методы решения задач оптимизации в электроэнергетике - student2.ru если i=r (т.е. для элементов ведущей строки),

Симплексные методы решения задач оптимизации в электроэнергетике - student2.ru если i≠r (т.е. для всех остальных элементов).

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

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

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

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

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

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

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

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

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

Наши рекомендации