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

ЛАБОРАТОРНАЯ РАБОТА №3

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

Цель работы: Получение навыков составления математических моделей для решения задач линейного программирования с целочисленными дискретными переменными в пакете MS Excel. Приобретение навыков решения оптимизационных задач электроэнергетики с целыми и дискретными переменными.

Краткие теоретические сведения.

B.1. Задачи с целочисленными переменными

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

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

х_k – целое, k = 1, 2, … l, (5.1)

где l – количество целочисленных переменных, l < n;

n – общее количество переменных.

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

Введение дополнительных ограничений по целочисленности переменных существенно увеличивает объем вычислений и усложняет мапра вычислительную процедуру при поиске оптимального решения. Однако в заданном диапазоне изменения переменной целочисленная переменная имеет меньшее количество значений, чем непрерывная переменная. В частности, в диапазоне 0 < x < 3 целочисленная переменная х имеет четыре значения (х = 0, 1, 2, 3), а непрерывная переменная – бесконечное количество значений.

Попытка решить целочисленную оптимизационную задачу методом полного перебора значений переменных приводит к очень большему объему вычислений. Так, например, в задаче с тремя целочисленными переменными и диапазоном их изменения 0 < x _k < 10, k = 1, 2, 3 количество целочисленных решений составит 11³=1331. Ясно, что для реальных оптимизационных задач метод полного перебора не приемлем

 

B.2. Двоичные переменные

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

Распространенными задачами с двоичными переменными являются задачи выбора оптимального решения (варианта) из определенного числа заданных решений (вариантов). Если вариант входит в оптимальное решение, то двоичная переменная, соответствующая этому варианту, равна 1. Если вариант не входит в оптимальное решение, то соответствующая двоичная переменная равна 0. Например, если линия электропередачи входит в оптимальную электрическую сеть, то двоичная переменная, соответствующая этой линии равна 1; если линия электропередачи не входит в оптимальную электрическую сеть, то соответствующая двоичная переменная равна 0.

В отличие от традиционных переменных х _i двоичные переменные будем обозначать δ_i, где i =1, 2, … n.

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

Если в оптимальное решение должен входить один из двух (i и j) вариантов, то сумма переменных

δ _i + δ _j = 1.

Если в оптимальное решение должны входить и i –й и j –й варианты, то сумма переменных

δ _i + δ _j = 2.

Если в оптимальное решение может входить или не входить, каждый из двух (i и j) вариантов, то сумма переменных

δ _i + δ _j > 0.

Если при входе (не входе) в оптимальное решение i –го варианта в это решение должен войти (не войти) и j –й вариант, то

δ _i = δ _j.

Аналогичные условия можно записать для трех и более вариантов. Если из n возможных вариантов в оптимальное решение должны входить только m вариантов (m < n), то

δ₁ + δ₂ + … + δ _n = m.

Очевидно, что количество логических условий типа «если …, то …» не ограничено.

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.

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

Пример 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оставьте математическую модель для простейшей оптимизационной задачи с дискретными переменными.