Алоев Т.Б., Асланова Е.М., Белова М.Т.

Оптимизация функционирования и развития систем

им. Х.М. Бербекова, Россия

К.ф.-м.н. Асланова Е.М.

Кабардино-Балкарский государственный университет

им. Х.М. Бербекова, Россия

К.э.н. Белова М.Т.

Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования «Финансовый университет при Правительстве Российской Федерации», Россия

Оптимизация функционирования и развития систем

, (1)

где  – коэффициент усиления -ой дуги.

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

(2)

при ограничениях, определяющих допустимое множество

(3)

где  – вектор потока дуг графа ;

- вектор интенсивностей источников потока в вершинах графа;  и -векторы ограничений пропускных способностей дуг соответственно сверху и снизу;

-обобщённая матрица инциденций графа , элементы которой строятся по правилу:

Выпуклая целевая функция (2) составлена из выпуклых функций затрат  функционирования отдельных дуг графа . Условия (3) представляют собой записанные совместно первый закон Кирхгофа [1] и зависимость (1).

Под решением задачи в работе понимается вектор  такой, что

, (5)

где - заданная погрешность.

Отказ от точного решения задачи (2)-(4) даёт возможность аппроксимировать её линейной задачей. Так как данные задачи известны с погрешностью и при решении допускается погрешность, такое понимание оптимального вектора не нарушает соответствия задачи (2)-(4) практической ситуации оптимального функционирования конкретной системы.

Оптимальное развитие системы заключается в установлении таких параметров и режимов, при которых затраты на развитие и функционирование были бы наименьшими. Оптимальное развитие в статическом (отсутствует этапность развития) детерминированном случае описывается так же, как и оптимальное функционирование, обобщённой транспортной задачей (2)-(4).

Отличие состоит в виде функции цели задачи. В случае функционирования  – выпуклая функция, при описании развития , определяемая соотношением [1]

, (6)

где

 – капитальные затраты на -ый уровень развития -го элемента; – невыпуклая функция. Указанное отличие в характере функциональной зависимости  обобщённых транспортных задач - моделей оптимального функционирования и оптимального развития – весьма существенное – задачи развития оказываются многоэкстремальными. Причём наличие фиксированных доплат создаёт значительные трудности решения таких задач. Для линейных транспортных задач с фиксированными доплатами разработаны специальные методы решения [2,3]. В данной работе строится метод решения более общей задачи, в которой могут быть отличными от единицы коэффициенты усиления дуг ,количество уровней развития  больше единицы и функции затрат  являются нелинейными.

Под решением задачи оптимального развития понимается приближённое с точностью  решение , удовлетворяющее неравенству (5). Переход от точного решения к приближённому в выпуклой задаче, оптимальный вектор которой может быть найден различными методами, сводит решение задачи к более простой – линейной. Отказ от точного решения многоэкстремальной задачи даёт возможность решить задачу оптимального развития. Эта возможность в работе реализуется применением схемы ветвей и границ.

Решение многоэкстремальных задач (2)-(4) представляет собой конкретизацию метода ветвей и границ [2], при которой процесс решения состоит из ряда последовательных этапов. На каждом -ом этапе рассматривается список ограничивающих выпуклых обобщённых транспортных задач , объединение допустимых множеств которых  совпадает с допустимым множеством  исходной задачи:

(a) ,

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

Функции цели  ограничивающих задач  являются минорантами функции цели  исходной задачи на множествах :

(б)

(в) существует система множеств  таких, что  и

.

Значение каждой из ограничивающих задач  согласно свойству (б) может служить нижней границей  на . Величина согласно свойству (а) может служить нижней оценкой значения исходной задачи  на - ом этапе:

(7)

Верхней оценкой - го этапа служит величина:

   (8).

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

Следовательно, на каждом этапе известна оценка погрешности принятия в качестве решения исходной задачи определяемого равенством (8) оптимального вектора -го этапа :

(9)

Поэтому, если на некотором -ом этапе выполнено неравенство

 (10)

то вектор  удовлетворяет условию (5). На этом этапе процесс решения может быть закончен.

Переход от го к следующему му этапу решения задачи  заключается в том, что из списка  ограничивающих выпуклых задач (2)-(4) го этапа  исключается одна, на которой достигается нижняя оценка  Допустимое множество этой задачи  разбивается на два не пересекающихся множества  и , на которых формируются новые выпуклые обобщенные транспортные задачи  и  Построенные задачи включаются в список ограничивающих задач (2)-(4) вместо исключенной. В результате получается совокупность задачго этапа .

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

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

ÄÄ,

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

(11)

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

(12)

Разбиение  на  и  по координате  в случае непрерывной функции цели задачи  производится по значению

(13)

При наличии разрыва  на (он возможен согласно (6)), разбиение осуществляется по точке разрыва.

Таким образом, оптимальный вектор исходной многоэкстремальной задачи (2)-(4), описывающей оптимальное развитие системы, находится решением конечного числа образуемых по ней оценочных выпуклых обобщенных транспортных задач.

1. Т.Б. Алоев, Е.М. Асланова. Об одном обобщении транспортной задачи. – Вестник КБГУ, серия Математические науки, выпуск 2 - Нальчик, 1998.

2. В.Н. Бурков, А.И. Лазебник, И.Л. Хранович. Метод ветвей и границ как регулярный метод решения нерегулярных задач математического программирования I,II. – Автоматика и телемеханика, №7 и №10, 1972.

3. В.Р. Хачатуров. Аппроксимационно-комбинаторный метод и некоторые его приложения. – Журнал вычислительной математики и математической физики, №6, 1974.

4. Р. Рокафеллар. Выпуклый анализ. - М., "Мир", 1973.