НОВЫЕ МОДЕЛИ ЗАДАЧ ЛИНЕЙНОГО БУЛЕВА ПРОГРАММИРОВАНИЯ Исполнитель

НОВЫЕ МОДЕЛИ ЗАДАЧ ЛИНЕЙНОГО БУЛЕВА ПРОГРАММИРОВАНИЯ

План

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

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

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

{spoiler=Подробнее} ,

,

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

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

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

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

,

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

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

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

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

,

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

        H_i -напор, м;

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

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

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

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

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

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

                                                  ,                                                 (1)

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

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

                                                                                               (2)

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

                                                  ,                                                (3)

здесь e=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).

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

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

Предполагается, что заданы п объектов, и для каждой пары объектов i и j предполагается заданным число d_ij (d_ij³0), f называемое расстоянием между объектами i и j (если эти объекты могут рассматриваться как элементы п мерного евклидова пространства).

Задача состоит в разбиении множества всех объектов на р классов (предполагается, что целое число р задано) и выборе в каждом классе специального объекта, называемого представителем этого класса, так чтобы сумма расстояний от объектов до их представителей была минимальна.

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

1, если объект с номером i отнесен к классу, представителем которого является объект с номером j;

            0 - в противном случае.

Здесь для идентификации объектов через булевые переменные х_ij использованы обозначения с двумя индексами, первый из которых i-указывает номер объекта в исходной выборке; второй j-номер объекта, который определен в качестве представителя одного из классов.

Приведенные обозначения и понятия разъясним на следующем примере. Пусть задано 10 объектов и требуются их разбиения на 3 класса, т.е. п=10 и р=3.

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

x₁₇=1; x₂₂=1;            x₃₂=1;     x₄₉=1;     x₅₉=1;

x₆₂=1; x₇₇=1;            x₈₇=1;     x₉₉=1;     x₁₀₂=1;

Остальные элементы матрицы булевых переменных Х равны нулю. В качестве представителей классов определены следующие объекты:

x₂₂=1 - представитель (условно первого) класса, куда входят следующие объекты: x₂₂, x₃₂, x₆₂  и x₁₀₂, ;

x₇₇=1 - представитель (условно второго) класса, куда входят следующие объекты: x₁₇, x₇₇  и x₈₇,

x₉₉=1 - представитель (условно третьего) класса, куда входят следующие объекты: x₄₉, x₅₉  и x₉₉,.

Как стало ясно из примера, представителями классов могут быть определены только диагональные элементы булевой матрицы X.

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

                                                                            (8)

                                                                                     (9)

                                                                                                        (10)

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

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

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

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

В данной работе впервые предлагается новая модель для задачи оптимального размещения букв алфавита любого языка на клавиатуре ЭВМ в виде линейной модели булева программирования. Для формализации задачи вводится булева матрица

по следующему правилу

x_ij    =

Первый индекс i используется для определения порядкового номера буквы в исходном алфавите, второй индекс j - для идентификации порядкового номера клавиши на клавиатуре.

Вводятся следующие понятия:

a_i - частота появления буквы c порядковым номером i в генеральной выборке слов рассматриваемого алфавита    (в данном случае необходимо исследовать достаточно большое число слов);

c_j - расстояние от центра клавиатуры до клавиши с порядковым номером j.

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

                                                                              (11)

                                                                               (12)

                                                                              (13)

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

Ограничения видов (12) и (13) использованы для обеспечения закрепления каждой буквы только за одной клавишей и обратно.

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

Для решения задачи (11) - (13) можно использовать эффективные методы линейного булева программирования.

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

1. Общее описание работы насосной станции.
2. Линейная булевая модель работы насосной станции.
3. Что понимается под задачей автоматической классификации?

Модель задачи оптимального размещения букв алфавита на клавиатуре{/spoilers}