B.3. Задачи с дискретными переменными

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

В ряде других задач искомые переменные могут принимать не любые, а только определенные значения, из которых требуется выбрать значения переменных, отвечающие оптимальному решению. Например, в заданном узле системы электроснабжения нужно установить компенсирующее устройство, мощность которого может быть равной значениям Q _k1, Q_{k 2}, … Q_kn. Из этого ряда требуется выбрать оптимальное значение мощности компенсирующего устройства, соответствующее выбранному критерию.

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

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

Пусть в оптимизационной задаче имеется n искомых переменных x_i (i =1, 2, … n). Дискретные значения каждой переменной заданы. В оптимальное решение должны войти k переменных (k < n). Каждой переменной x _i поставим в соответствие двоичную переменную δ _i. Если в процессе решения задачи δ _i =1, то переменная x_i войдет в оптимальное решение; если δ _i =0, то переменная x _i не войдет в оптимальное решение.

Целевая функция включает в себя и дискретные x ₁, x ₂, … x_n и двоичные переменные δ₁, δ₂,…δ _n

Z (x ₁, x ₂, … x _n, δ₁, δ₂,…δ _n) → extr.

В систему ограничений входят и дискретные и двоичные переменные

f ₁ (x ₁, x₂,... x_n, δ₁, δ₂,…δ _n, b ₁ )=0,

f ₂ (x ₁, x₂,... x_n, δ₁, δ₂,…δ _n, b₂)=0,

.........................

f_m(x ₁, x₂,... x_n, δ₁, δ₂,…δ _n, b_m)=0.

К этой системе добавляются ограничения вида

δ₁ + δ₂ + … + δ _n = k, (5.9)

δ _i – двоичные, i =1, 2, … n.

Граничные условия, как таковые, не записываем, поскольку возможные значения дискретных переменных являются заданными, а значения двоичных переменных могут быть только 0 или 1.

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

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

Исходные данные:

напряжение схемы U = 10 кВ;

сопротивления линий R ₁=0,4, R ₂=0,5, R ₃=0,6 Ом;

реактивные нагрузки узлов 1, 2 и 3 Q ₁=600, Q ₂=500, Q ₃=400 квар;

мощность компенсирующего устройства Q_k =1000 квар

Рис. 1. Схема электроснабжения

Решение. В рассматриваемой схеме имеются три узла 1, 2 и 3, в каждом из которых можно установить компенсирующее устройство. Обозначим переменными Q_{k 1}, Q_{k 2} и Q_{k 3} мощности компенсирующих устройств, размещаемых соответственно в узлах 1, 2 и 3. Это дискретные переменные, каждая из которых может принимать два значения 0 или 1000 квар.

Каждой переменной Q_{k 1}, Q_{k 2} и Q_{k 3} поставим в соответствие двоичную переменную δ₁, δ₂ и δ₃.

Целевая функция, представляющая собой потери мощности в схеме, будет иметь следующий вид:

Δ Р = a ₁(Q ₁ + Q ₂ + Q ₃ - Q _k1δ₁- Q _k2δ₂ - Q _k3δ₃)² + a ₂(Q ₂ + Q ₃ - Q _k2δ₂ - Q _k3δ₃)² + a ₃(Q ₃ - Q _k3δ₃)² → min,

где а _i= R _i/ U ² (i =1, 2, 3).

Выражение для потерь мощности предусматривает возможность установки компенсирующего устройства в каждом из трех узлов. Однако в зависимости от величины двоичной переменнойкомпенсирующее устройство в узле i должно быть установлено при δ_i =1 или не должно быть установлено при δ_i =0.

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

δ₁ + δ₂ + δ₃ = 1,

δ₁, δ₂ и δ₃ – двоичные.

Величина дискретной переменной Q_ki будет зависеть от значения соответствующей двоичной переменной δ_i. Переменная Q_ki = Q_k при δ_i=1 и Q_ki = 0 при δ_i=0. Запишем эти условия

Q_{k 1} = Q_k δ₁,

Q_{k 2} = Q_k δ₂,

Q_{k 3} = Q_k δ₃.

Граничные условия не записываем, поскольку имеем только двоичные и дискретные переменные.

Результаты решения задачи с помощью программного обеспечения Excel приведены в приложении П5:

δ₁=0, δ₂ =1, δ₃ = 0, Q_{k 1} = 0, Q_{k 2} = 1000 квар, Q_{k 3} = 0, Δ Р = 2010 Вт.

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

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

Исходные данные те же, что и в примере 9. Мощность компенсирующего устройства может принимать следующие дискретные значения: 1100, 1200 или 1300 квар.

Решение. В рассматриваемом примере имеем одну дискретную переменную – мощность компенсирующего устройства во 2-м узле. Эта переменная может принимать три дискретных значения Q _k1=1100, Q _k2=1200 и Q _k3=1300 квар. Каждому значению дискретной переменной поставим в соответствие двоичную переменную δ₁, δ₂ и δ₃.

Целевая функция, представляющая собой потери мощности в схеме, будет иметь следующий вид:

Δ Р = a ₁(Q ₁ + Q ₂ + Q ₃ - Q _k1δ₁ - Q _k2δ₂ - Q _k3δ₃)² + a ₂(Q ₂ + Q ₃ - Q _k1δ₁ - Q _k2δ₂ - Q _k3δ₃)² + a ₃ Q ₃² → min.

где а _i= R _i/ U ² (i =1, 2, 3).

Рассмотрим ограничения. Поскольку дискретная переменная должна принять только одно значение, сумма двоичных переменных должна быть равна 1

δ₁ + δ₂ + δ₃ = 1,

δ₁, δ₂ и δ₃ – двоичные.

Других ограничений нет.

Граничные условия не записываем, поскольку имеем только дискретную и двоичные переменные.

Результаты решения задачи:

δ₁=0, δ₂ =1, δ₃ = 0, Q _k1 = 0, Q _k2 = 1200 квар, Q _k3 = 0, Δ Р = 1770 Вт.

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

Задание

Составить математическую модель для определения в схеме электроснабжения (рис. 2) оптимальных мест установки и мощности компенсирующих устройств Q_k. Критерий оптимальности - минимум потерь активной мощности в схеме. Исходные данные приведены ниже.

Рис. 2. Схема электроснабжения

 

Требуется найти оптимальные места установки и мощности компенсирующих устройств для случаев:

1) мощность компенсирующих устройств может принимать любые целыезначения, при напряжении схемы U = 6 кВ;

2) Решить задачу пункта №1 при напряжении схемы U = 10 кВ;

3) Решить задачу пункта №1 при напряжении схемы U = 35кВ;

4) Мощность компенсирующих устройств может принимать следующие дискретные значения: 400, 450, 900 или 1125кВАр, при напряжении схемы U = 6 кВ;

5) Решить задачу пункта №4 при напряжении схемы U = 10 кВ;

6) Решить задачу пункта №4 при напряжении схемы U = 35кВ.

 

ВАРИАНТЫ ЗАДАНИЙ

N	R 1	R2	R 3	Q 1	Q 2	Q 3
	0,4	0,5	0,6
	0,4	0,6	0,5
	0,5	0,4	0,6
	0,5	0,6	0,4
	0,6	0,5	0,4
	0,6	0,4	0,5
	0,3	0,5	0,6
	0,3	0,6	0,5
	0,5	0,3	0,6
	0,5	0,6	0,3
	0,6	0,5	0,3
	0,6	0,3	0,5
	0,4	0,3	0,6
	0,4	0,6	0,5
	0,3	0,4	0,6
	0,3	0,6	0,4
	0,6	0,3	0,4
	0,6	0,4	0,3
	0,4	0,5	0,3
	0,4	0,3	0,5
	0,5	0,4	0,3
	0,5	0,3	0,4
	0,3	0,5	0,4
	0,3	0,4	0,5
	0,4	0,5	0,2
	0,4	0,2	0,5
	0,5	0,4	0,2
	0,5	0,2	0,4
	0,2	0,5	0,4
	0,2	0,4	0,5

Контрольные вопросы:

1. Приведите примеры оптимизационных задач с дискретными переменными для электроэнергетики.

2. Приведитематематическую модель дляоптимизационных задач с дискретными переменными.

3. Покажите как с помощью применения двоичных переменных можно накладывать на решаемую задачу целый ряд логических условий типа «если …, то …».

4. Cоставьте математическую модель для простейшей оптимизационной задачи с дискретными переменными.