Савина Н.В. Применение теории вероятности и методов оптимизации в системах электроснабжения
Подождите немного. Документ загружается.
251
программирования, в которой вместо П
j
фигурирует неотрицательный параметр
П
j
´. Это достигается с помощью преобразования П
j
= b
j
+ П
j
´, где П
j
´ ≥0, и
последующей подстановкой правой части полученного соотношения вместо
параметра П
j
всюду, где он фигурирует в математической модели.
В последующем мы убедимся насколько удобно представлять любую
линейную оптимизационную модель в компактном и полностью
детерминированном виде. Различного рода преобразования, рассмотренные
выше, вполне позволяют справиться с этой задачей.
В настоящее время в электроэнергетических оптимизационных задачах
существует большое разнообразие форм представления линейных
оптимизационных моделей. В дальнейшем будем стремиться представлять
модели в виде следующих двух канонических форм.
1. Любую задачу линейного программирования можно рассматривать как
задачу минимизации
∑
=
k
1i
jj
ПЗ
(174)
при условии
∑
=
=
k
1j
jjij
bПb (i=1, 2, …, l), b
i
≥0; (175)
П
j
≥0 ( j = 1, 2, …, k). (176)
2. Любую задачу линейного программирования можно свести к
максимизации
∑
=
k
1j
jj
ПЭ (177)
при наличии ограничений
∑
=
≤
k
1j
jjij
bПb (i=1, 2, …, l); (178)
П
j
≥0 ( j = 1, 2, …, k). (179)
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
252
7.3. Симплексный метод
Постановка задачи
Из методов линейного программирования наибольшее распространение
получил симплекс-метод /28/. При его использовании определяются значения
целевой функции на поверхности ограничения. Для нахождения оптимального
значения целевой функции выбирается переменная, которую увеличивают до
тех пор, пока не подходят к очередному ограничению. Причем, изменяемая
величина обладает свойством сообщать целевой функции максимальное
приращение при условии, если остальные переменные фиксированы. С целью
постепенного освоения симплексного алгоритма первоначально рассмотрим
задачу в упрощенном виде:
минимизировать
-2П
1
– 3П
2
– 7П
3
– 9П
4
(180)
при ограничениях
1П
1
+ 1П
2
+ 1П
3
+ 1П
4
≤9; (181)
1П
1
+ 2П
2
+ 4П
3
+ 8П
4
≤24; (182)
П
j
≥ 0 ( j = 1, 2, …, 4).
Предварительно представляют задачу в виде, удобном для использования
симплекс-метода. С этой целью в зависимости (181) и (182) вводятся
дополнительные переменные П
5
и П
6
, превращающие неравенства в равенства.
В результате получим видоизмененные зависимости-ограничения
1П
1
+ 1П
2
+ 1П
3
+ 1П
4
+ 1П
5
=9; (183)
1П
1
+ 2П
2
+ 4П
3
+ 8П
4
+ 1П
6
=24. (184)
Для начала попытаемся искать решение задачи, придав максимально
возможное значение П
4
, т.е. той переменной, которая входит в выражение
целевой функции с наибольшим коэффициентом. Наибольшая величина П
4
при
нулевых значениях остальных переменных должна удовлетворять
одновременно зависимостям (183) и (184). Легко убедиться, что это пробное
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
253
значение параметра П
4
равно 24/8=3 и полностью определяется
коэффициентами в ограничении. При этом целевая функция примет значение -
9·3=-27. Если рассмотреть другой случай, в котором в качестве пробного
решения выбрано максимально допустимое значение П
3
, равное 4·6=24, то
целевая функция примет значение -7·6=-42, то есть меньшее по сравнению с
предшествующим вариантом. Таким образом, из-за наличия ограничений
использование переменной, обладающей наибольшей удельной стоимостью, не
всегда приводит к наилучшему результату.
Из зависимости (183) следует, что если П
3
=6, то П
5
=3. Поскольку целевая
функция не зависит от П
5
, можно попытаться улучшить решение, выбирая
различные комбинации других переменных. Если бы не существовали
некоторые простые правила, позволяющие сразу же исключить из
рассмотрения заведомо неудовлетворительные решения, перебор различных
пробных решений был бы весьма трудоемким. Предположим, например, что
оптимальное решение можно найти, задаваясь положительными значениями П
2
и П
3
при нулевых значениях П
1
, П
4
, П
5
и П
6
. Необходимо проверить, является
ли данное положение правильным. Для этого достаточно научиться лишь
манипулировать соотношениями (183) и (184), используя приемы элементарной
алгебры, применяемые при решении системы, состоящей из двух линейных
уравнений. В математике такой подход называют методом исключения
переменных или методом Гаусса.
Предварительно перенесем П
1
, П
4
, П
5
и П
6
в уравнениях (183) и (184) в
правые части:
1П
2
+ 1П
3
= 9 - 1П
1
-1П
4
-1П
5
; (185)
2П
2
+ 4П
3
=24 - 1П
1
- 8П
4
- 1П
6
. (186)
Затем из уравнения (186) исключим П
2
, для чего умножим обе части
уравнения (185) на 2 и полученный результат вычтем из (186). Выполнив эти
операции, получим
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
254
1П
2
+ 1П
3
= 9 - 1П
1
-1П
4
-1П
5
; (187)
2П
3
=6 + 1П
1
- 6П
4
+ 2П
5
- 1П
6
. (188)
После этого произведем нормировку коэффициента при П
3
в уравнении
(188), разделив обе части его на 2. В результате получим
1П
2
+ 1П
3
= 9 - 1П
1
-1П
4
-1П
5
; (189)
1П
3
=3 + 0,5П
1
- 3П
4
+ 1П
5
- 1П
6
. (190)
Наконец, из выражения (189) следует исключить П
3
, что достигается
вычитанием (190) из (189):
П
2
= 6 -
3
2
П
1
+2П
4
-2П
5
+
1
2
П
6
; (191)
П
3
=3 +
1
2
П
1
- 3П
4
+ 1П
5
-
1
2
П
6
. (192)
Сочетание нормировки с операцией исключения переменной называют
поиском опорного плана.
Согласно предположению П
1
=П
4
=П
5
=П
6
=0. Тогда из уравнений (191) и
(192) П
2
=6, П
3
=3. Легко показать, что при этом удовлетворяются ограничения
(183) и (184). Для данного решения целевая функция принимает значение -3·6-
7·3 = -39. Однако при П
3
=6 функция (180) принимает меньшее значение равное
-42 при предположении (П
1
=П
2
=П
4
=0). Следовательно, предложенный вариант
решения (П
1
=П
4
=П
5
=П
6
=0, П
2
=6, П
3
=3) не является оптимальным.
Попытаемся найти простой способ, позволяющий проверить на оптимальность
рассматриваемый набор значений переменных П
j
(j=1, 2, …, 6) без каких бы то
ни было предварительных проб. Для этого подставим П
2
и П
3
, заданные
соотношениями (192) и (193), в выражение для целевой функции:
–2П
1
– 3(6 –
3
2
П
1
+2П
4
–2П
5
+
2
1
П
6
) – 7(3+
2
1
П
1
–3П
4
+1П
5
–
2
1
П
6
) –9П
4
=
=–39–1П
1
+6П
4
–1П
5
+2П
6
. (194)
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
255
Из этого соотношения следует, что при П
1
>0 и П
5
>0 (коэффициенты при
которых отрицательные) значение функции будет меньше -39. Действительно,
если в (193) увеличить на единицу П
1
или П
5
, то ровно на единицу уменьшится
значение целевой функции.
Предположим, что мы решим увеличивать значение П
1
. Каков при этом
допустимый предел? С помощью уравнений (191) и (192) можно показать, что
при П
4
=П
5
=П
6
=0 увеличение значения П
1
на единицу приводит к уменьшению
П
2
на
3
2
и одновременному увеличению П
3
на
1
2
.
Однако допустимое решение должно удовлетворять условию П
j
≥0.
Следовательно, значение П
1
не может превышать 4, поскольку при П
1
=4 и
П
4
=П
5
=П
6
=0 значение П
2
становится равным нулю. При этом по выражению
(193) значение целевой функции становится равным -39-1·4=-43.
Продолжая поиск оптимального решения, рассмотрим другой пробный
вариант, предположив, что П
1
и П
3
могут принимать положительные значения,
а значения остальных переменных равны нулю. Используя приемы, с помощью
которых были получены уравнения (191) и (192), легко разрешить уравнения
(183) и (184) относительно П
1
и П
3
:
П
1
=4 –
3
2
П
2
+
3
4
П
4
–
3
4
П
5
+
3
1
П
6
; (195)
П
3
=5–
3
1
П
2
–
3
7
П
4
+
3
1
П
5
–
3
1
П
6.
(196)
Полагая П
2
=П
4
=П
5
=П
6
=0, получим П
1
=4 и П
3
=5. При этом целевая
функция принимает значение –2·4
–
7·5=
–43. Отметим, что данное значение
совпадает с тем, которое было получено с помощью функции (193). С целью
проверки рассматриваемого пробного варианта на оптимальность можно, как и
в предыдущем случае, подставить уравнение (184) и (185) в выражение для
целевой функции:
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
256
–43+
3
2
П
2
+
3
14
П
4
+
3
1
П
5
+
3
5
П
6
. (197)
Нетрудно убедиться, что при любом положительном приращении
переменных П
2
, П
4
, П
5
и П
6
целевая функция принимает значения, большие по
сравнению с только что полученным. Следовательно, данное решение
действительно является оптимальным.
Изложенное в ходе проведенного выше анализа можно привести в
надлежащую систему и представить в виде некоторой совокупности правил.
Разработанный симплексный алгоритм позволяет обоснованно выбирать
пробные варианты и устанавливать критерий оценки степени оптимальности
каждого из рассматриваемых пробных решений.
Алгоритм симплексного метода оптимизации
Для решения задач линейного программирования можно использовать
несколько различных алгоритмов. Однако наиболее эффективным и
распространенным среди них оказался следующий алгоритм.
Попытаемся весь ход рассуждений, приводящих к решению задачи,
рассмотренной выше, описать в словесной форме.
Модель задачи содержит два уравнения. Пробные решения выбирались
следующим образом. Допускалось, что две переменные принимают некоторые
положительные значения, а остальные переменные предполагались
тождественно равными нулю.
Стремясь к обобщению, можно предположить, что в тех случаях, когда
модель содержит m переменных, называемых базисными, принимающих
некоторые положительные значения при нулевых значениях остальных
переменных, называемых внебазисными.
Вначале допустим, что решение существует, причем оптимальное
значение целевой функции конечно. В этом случае вычислительная процедура
(алгоритм) будет выглядеть следующим образом.
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
257
Шаг 1. Выберем m переменных, задающих допустимое пробное решение.
Исключим эти переменные из выражения для целевой функции.
Шаг 2. Проверим, нельзя ли за счет одной из переменных, приравненной
вначале к нулю, улучшить значение целевой функции, придавая ей отличные от
нуля (причем положительные) значения. Если это возможно, перейти к шагу 3.
В противном случае вычисления заканчиваются.
Шаг 3. Найдем предельное значение переменной, за счет которой можно
улучшить значение целевой функции.
Увеличение значения этой переменной допустимо до тех пор, пока одна
из m переменных, вошедших в пробное решение, не обратится в нуль.
Исключим из выражения для целевой функции только что упомянутую
переменную и введем в пробное решение ту переменную, за счет которой
результат может быть улучшен.
Шаг 4. Разрешим систему m уравнений относительно переменных,
вошедших в новое пробное решение. Исключим эти переменные из выражения
для целевой функции и вернемся к шагу 2.
Важно отметить, что при однозначном понимании данного предписания
предложенный алгоритм действительно приводит к оптимальному решению
для любой модели линейного программирования за конечное число итераций.
Пример решения оптимизационной задачи симплексным методом
Минимизировать
F(
П
)=20–5П
1
–30П
4
+6П
5
(198)
при ограничениях:
П
1
–3П
4
+2П
5
=6; (199)
П
2
+0,1П
4
+3П
5
=12; (200)
П
3
+2П
4
–П
5
=1; (201)
П
j
≥0 ( j=1, 2, …, 5).
Находим первое допустимое базисное решение:
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
258
П
1
=6; П
2
=12; П
3
=1; П
4
=П
5
=0.
Здесь П
1
, П
2
, П
3
– базисные переменные; П
4
и П
5
– в небазисные переменные.
В целевой функции представлена только одна базисная переменная П
1
,
поэтому уравнение (199) преобразовываем относительно П
1
и подставляем
правую часть в уравнение (198):
П
1
=6+3П
4
–2П
5
;
F(П)=20–5(6+3П
4
–2П
5
) –30П
4
+6П
5
=–10–45П
4
+16П
5
. (202)
Анализ знаков и значений коэффициентов в функции (202) показывает,
что для уменьшения значения F(
П
) необходимо вывести из внебазисных
переменную П
4
и ввести ее в новое базисное решение. Найдем переменную,
которую следует вывести из первоначального базиса и перевести в разряд
внебазисных переменных. Для этого выписываем систему ограничений
(199)…(201), причем П
5
остается равным нулю:
П
1
–3П
4
=6; П
2
+0,1П
4
=12; П
3
+2П
4
=1. (203)
Анализ этих уравнений показывает, что при увеличении П
4
до 0,5
переменная П
3
становится равной нулю. Следовательно, эта переменная П
3
и
должна быть выведена из базиса.
Таким образом, на втором шаге симплекс – алгоритма принято
следующее решение: для уменьшения значения целевой функции вывести из
базиса переменную П
3
и ввести в базис П
4
.
Выпишем уравнение (201) и решим его относительно П
4
:
П
4
=0,5(1+П
5
–П
3
).
Полученное выражение подставим в (199) и (200) и исключим из них
вводимую в базис переменную П
4
:
П
1
–1,5(1+П
5
–П
3
)+2П
5
=6;
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
259
П
2
+0,05(1+П
5
–П
3
)+3П
5
=12
или
П
1
+1,5П
3
+0,5П
5
=7,5; (204)
П
5
–0,05П
3
+3,05П
5
=11,95. (205)
Проводя нормировку (201) относительно П
4
, с учетом (204) и (205)
получим новую систему ограничений:
П
1
+1,5П
3
+0,5П
5
=7,5; (206)
П
5
–0,05П
3
+3,05П
5
=11,95. (207)
П
4
+0,5П
3
–0,5П
5
=0,5 (208)
и новый опорный план
П
1
=7,5–1,5П
3
–0,5П
5
; (209)
П
2
=11,95+0,05П
3
–3,05П
5
; (201)
П
4
=0,5–0,5П
3
+0,5П
5
. (211)
Новое допустимое базисное решение: П
1
=7,5; П
2
=11,95; П
4
=0,5;
П
3
=П
5
=0. Подставляя выражения (199) и (201) в (198), получим выражение
целевой функции через новые внебазисные переменные П
3
и П
5
:
F(
П
)=20–5(7,5–1,5П
3
–0,5П
5
) –30(0,5–0,5П
3
+0,5П
5
)+
+6П
5
=–32,5+22,5П
3
–6,5П
5
. (212)
Из этого выражения ясно, что на второй итерации целесообразно
увеличивать П
5
, то есть вводить в базис, переменную П
5
. С учетом П
3
=0
система ограничений (206)…(208) запишется в виде
=−
=+
=+
.5,0П5,0П
;95,11П05,3П
;5,7П5,0П
54
52
51
(213)
Из полученной системы видно, что при достижении переменной П
5
значения 3,918 переменная П
2
становится равной нулю. Следовательно,
переменную П
2
следует вывести из базиса:
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
260
П
5
=(11,95+0,05П
3
–П
2
)
1
3,05
=3,918+0,015П
3
–0,328П
2
.
Подставляя полученное выражение в (206) и (208), получим
П
1
+1,5П
3
+0,5(3,918+0,015П
3
–0,328П
2
)=7,5
или
П
1
+1,508П
3
–0,164П
2
=5,54;
П
4
+0,5П
3
–0,5(3,918+0,015П
3
–0,328П
2
)=0,5,
или
П
4
+0,492П
3
+0,164П
2
=2,46.
Новая система ограничений запишется в виде
П
1
-0,164П
2
+1,508П
3
=5,54; (214)
П
4
+0,164П
2
+0,492П
3
=2,46; (215)
П
5
+0,328П
2
–0,015П
3
=3,918. (216)
Выразим новые базисные переменные через внебазисные:
П
1
=5,54+0,164П
2
–1,508П
3
;
П
4
=2,46–0,164П
2
–0,492П
3
;
П
5
=3,918–0,328П
2
+0,015П
3
.
Подставим полученные выражения в (198):
F(
П
)=20–5(5,54+0,164П
2
–1,508П
3
) –30(2,46–0,164П
2
–0,492П
3
)+
+6(3,918–0,328П
2
+0,015П
3
)= –57,99+2,132П
2
+22,42П
3
. (217)
Отсутствие отрицательных коэффициентов при внебазисных переменных
показывает, что достигнуто оптимальное значение целевой функции
F(
П
0
)=–57,99. Оптимальные значения параметров при этом
0
П
= [5,54; 0; 0; 2,46; 3,918 ]. (218)
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com