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

1. Роль и место моделей булева программирования в проблеме оптимизации.

2. Основные виды моделей линиейного булева программирования.

3. О полиномиальных и не полиномиальных задачах в дискретной оптимизации.

4. Преобразование задачи с дискретными переменными к задаче с булевыми переменными.

5. Преобразование задачи *** к задаче нелинейного булева программирования.

6. Как записывается функционал Фишерского типа.

Литература

Лекция 15. НОВЫЕ МОДЕЛИ ЗАДАЧ ЛИНЕЙНОГО БУЛЕВА ПРОГРАММИРОВАНИЯ (2 часа)

План

1. Задача и модель оптимизации работы насосной станции

2. Модель задачи автоматической классификации

3. Задача об оптимизации размещения букв алфавита на клавиатуре ЭВМ

1. Задача и модель оптимизации работы насосной станции

Исследование и моделирование крупных насосных станций является одной из ключевых задач в системе машинного водоподъема (СМВ). В настоящее время в СМВ в основном используется диспетчерское управление, основанное на простых методах принятия решений, исходя из личного опыта и интуиции лица, принимающего решения (диспетчера) и решающего задачу управления для текущего момента времени. Такое управление приводит к перерасходу электроэнергии на водоподъем, непроизводительным сбросам и потерям воды, невыполнения графика водоподачи. Поэтому задачи, связанные с исследованием, моделированием и разработкой оптимальных алгоритмов управления работой насосной станции, особенно становятся актуальными в связи с переходом к рыночным условиям хозяйствования.

Исследуем работу насосной станции и определим ее основные управляющие параметры.

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

В насосных станциях используются крупные осевые насосные агрегаты типа "Р" и "ОП", центробежные типа "В". Для подъема воды на высоту до 25 м используются осевые насосные агрегаты, а на высоту более 25 м -центробежные. Для моделирования процесса водоподачи основными являются гидроэнергетические и расходные характеристики. Гидроэнергетические характеристики можно найти в каталогах. Расходная характеристика Q насосного агрегата зависит от высоты подъема H и от угла разворота лопасти насосного агрегата:

.

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

, (j=1,2,...,n),

где - угол разворота лопастей, соответствующий j-ой кривой; n - количество кривых.

Таким образом, расходная характеристика насосного агрегата полностью определяется двойкой

Состояние насосной станции определяется количеством работающих насосных агрегатов m_p из общего числа насосных агрегатов m и последовательностью углов разворота лопастей работающих насосных агрегатов

Например, i-й насосный агрегат может работать в n положениях

(i=1,2,...,m),

т.е. положение насосного агрегата определяется положением угла разворота лопастей.

Для работающих насосных агрегатов насосной системы введем следующие обозначения:

,

,

где M_P - множество номеров работающих насосных агрегатов;

- множество углов разворота лопастей работающих насосных агрегатов.

Следовательно, состояние насосной станции в каждый момент времени определяется тройкой .

Общая расходная характеристика насосной станции, соответствующая ее состоянию, определяется как алгебраическая сумма расходов каждого работающего насосного агрегата:

,

где Q_i(H,_i) - расходная характеристика i-го насосного агрегата;

H - высота подъема воды;

_i - угол разворота лопастей i-го насосного агрегата.

Потребляемая мощность насосной станции также определяется как алгебраическая сумма мощностей каждого работающего насосного агрегата:

,

где /кВт/ - мощность i-го насосного агрегата;

H_i -напор, м;

Q_i -расход i-го насосного агрегата, м³ /с;

-КПД i-го насосного агрегата.

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

Приводим постановку задачи оптимизации, которая является общепринятой в СМВ.

Пусть управляемый процесс в области

характеризуется определением регулирующей тройки

, (1)

где _min и _max - минимальное и максимальное допустимые значения углов разворота лопастей насосных агрегатов;

и - критические значения уровней верхнего и нижнего бьефов насосных станций, при которых требуется минимизировать функционал

(2)

с выполнением ограничения следующего вида

, (3)

здесь =0.05*Q_n - допустимая погрешность управления.

Задача оптимизации (2), (3) с оптимизируемой тройкой параметров (1) не подлежит эффективному решению существующими методами. В связи с этим возникшую задачу сформулируем как задачу линейного булева программирования в обобщенной постановке.

Предполагается, что в насосной станции имеются m насосных агрегатов:

P₁, P₂, ... , P_m .

Насосный агрегат P_i может работать в n_i положениях

(4)

где n_i -количество углов разворота лопастей i-го насосного агрегата; причем рассматривается случай, когда количество углов разворота лопастей для разных насосных агрегатов различно; кроме того, насосный агрегат P_i может находиться только в одном из перечисленных положений (4).

Известна производительность (производительность насосных агрегатов обычно регулируется углом разворота лопастей рабочего колеса работающих насосных агрегатов) каждого положения i-го насосного агрегата, т.е.

где q_ij - расходная характеристика i-го насосного агрегата при j-м положении угла разворота лопастей.

Также считаются известными значения следующих параметров

,

где c_ij - потребляемая мощность i-го насосного агрегата при j-м положении угла разворота лопастей.

Введем булевые переменные x_ij по следующему правилу: x_ij=1, если i-й насосный агрегат работает в j-м положении; x_ij=0 -в противном случае.

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

(5)

(6)

(7)

где и нижний и верхний пределы общей расходной характеристики насосной станции.

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

где -(i=1,2,...,m; j=1,2,...,n_i) - решение задачи (5)-(7). Номера работающих насосных агрегатов определяются из следующего условия: если для произвольного значения i =1 (j=1,2,...,n_i), то i-й насосный агрегат работает.

Здесь путем минимизации целевой функции (5) уменьшается общая потребляемая мощность насосной станции. Выполнения ограничения вида (6) обеспечивает подъем воды в допустимых пределах [ , ]. Выполнением ограничения вида (7) обеспечивается работа каждого насосного агрегата только в одном из возможных положений (4).