Симплексные методы решения задач оптимизации в электроэнергетике
Симплексный метод относится к линейному программированию и применяется при решении задач оптимизации при наличии выпуклой целевой функции
и линейных уравнений-ограничений в форме неравенств
или же в матричной форме
Например, при наличии двух оптимизируемых параметров и четырех уравнений ограничений исходная модель имеет вид
Для решения задачи симплексным методом исходная модель приводится к стандартной, канонической форме.
Для этого целевая функция и все уравнения-ограничения приводятся к форме равенств с неотрицательной правой частью. При этом все переменные также неотрицательны
.
Здесь Si – вспомогательная переменная, вводимая в i-е уравнение для приведения его к форме равенства, ее знак положителен для неравенств вида 
и отрицательный для неравенств вида 
.
В канонической форме для данного примера число ограничений m=4, а число переменных увеличивается до n=6.
Рис. 53. Допустимое пространство решений
Допустимое пространство решений в координатах оптимизируемых параметров получается как пересечение прямых, уравнения которых получены приравниванием нулю вспомогательной переменной в одном из ограничений (см. рис. 53).
Например, уравнение прямой, полученной приравниванием нулю вспомогательной переменной в первом ограничении S1=0 и проходящей через точки E и F, имеет вид
Точки A, B, C, D, E, F – экстремальные точки допустимого пространства решений, в которых обнуляются n–m переменных.
Суть симплексного метода заключается в том, что оптимальное решение ищется среди экстремальных точек допустимого пространства решений по определенному алгоритму, уменьшающему число переборов.
Например (см. рис. 54), если начальное приближение – точка A, то затем переход осуществляется к смежной точке, но не произвольной, а к той, которая обеспечивает наискорейший рост целевой функции.
Рис. 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), в котором место исключаемой переменной в новом базисе занимает включаемая, все коэффициенты симплекс-таблицы пересчитываются по алгоритму Жордана- Гаусса
если i=r (т.е. для элементов ведущей строки),
если i≠r (т.е. для всех остальных элементов).
Табл. 4. Новое базисное решение
| Переменные | z | x1 | x2 | S1 | S2 | S3 | S4 | B | |
| Цел. ф-я |  |  | … | … | … | … | … |  | |
| БАЗИС | … | … | … | … | … | … | … | … | … |
| … | … | … | … | … | … | … | … | … | |
| … | … | … | … | … | … | … | … | … | |
| … |  |  | … | … | … | … | … |  |
Метод искусственного базиса
Данный метод применяется в тех случаях, когда в системе имеются ограничения со знаками ≤, ≥, = и является модификацией ранее рассмотренного табличного симплексного метода.
Решение производится путем введения в целевую функцию и ограничения искусственных переменных со знаками, зависящими от типа оптимума. Для исключения искусственных переменных из базиса они вводятся в целевую функцию с большими отрицательными коэффициентами –М или с большими положительными при решении задачи минимизации.
Если в базисе отсутствуют искусственные переменные (все искусственные переменные исключены из базиса), то решение признается оптимальным.
Исходная модель включает целевую функцию
и систему ограничений, включающую m ограничений-неравенств
и k ограничений-равенств
В качестве примера подобной исходной модели, включающей ограничения, как в форме равенств, так и в форме неравенств, можно рассмотреть минимизацию целевой функции z расходов при строительстве энергосистемы
.
В этой модели имеют место n ограничений неравенств по максимальной мощности электростанций и два ограничения равенства из условий мгновенного и долгосрочного баланса мощностей
,
где
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, в процессе которого модель приобретает вид
;
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. определение исключаемой из базиса переменная по наименьшему положительному отношению правой части соответствующего ограничения к элементу ведущего столбца bi/aik. (строка, соответствующая исключаемой переменной, является ведущей строкой r, элемент на пересечении ведущей строки и ведущего столбца является ведущим элементом ark);
6. составление нового базисного решения, в котором столбец, соответствующий исключаемой переменной удаляется из таблицы, место исключаемой переменой в базисе занимает включаемая переменная, позиция на пересечении ведущей строки и столбца Cб заполняется коэффициентом включаемой переменной в целевой функции, все коэффициенты симплекс-таблицы пересчитываются по алгоритму Жордана- Гаусса
если i=r (т.е. для элементов ведущей строки),
если i≠r (т.е. для всех остальных элементов).
Этот алгоритм повторяется до тех пор, пока из базиса не будут удалены все искусственные переменные.
Модифицированный симплексный метод
В основу данного метода положены такие свойства линейной алгебры, которые позволяют в ходе решения задачи работать только с частью матрицы ограничений.
Данный метод также называется методом обратной матрицы.
В процессе работы алгоритма происходит спонтанное обращение матрицы ограничений по частям, соответствующим текущему базисному вектору. Это делает привлекательной машинную реализацию данного алгоритма вследствие экономии памяти под промежуточные переменные и сокращении времени вычислений.
Использование данного метода особенно эффективно при n>>m.
Общие и отличительные черты модифицированного симлексного метода относительно ранее рассмотренных показаны в табл. 6.
Табл. 6. Традиционные и отличительные черты модифицированного симплексного метода
| Традиционные черты решения задач линейного программирования | Отличительные черты |
| 1. Приведение модели к канонической форме | 1. Наличие двух таблиц: основной и вспомогательной |
| 2. Коррекция базиса методом исключения Жордана-Гаусса | 2.Порядок их заполнения |
| 3. Проверка условия оптимальности | 3. Особенности расчетных формул |