Наш логотип
Научно-производственный центр "Приоритет"Приоритет качества и профессионализма  —  Приоритет новых технологий  —  Приоритет Ваших интересов
Новости компании как нас найти Лицензии Наши сертификаты   Задайте Ваш вопрос, и мы ответим! Советчик диспетчера    Спрут
О компании
Проектирование
Строительство и монтаж
Оборудование
Сервис
Примеры технических решений
Программный комплекс для энергетики
Системы управления

Контактная
информация

Адрес: 113035,
г. Москва,
ул. Садовническая, 15;

Многоканальный телефон: (495) 995-2733.
Факс: (495) 995-2733 9
e-mail:
общий prioritet@priortelecom.ru
отдел проектирования project@priortelecom.ru
строительный отдел montage@priortelecom.ru
сервисный центр service@priortelecom.ru
научный отдел (программное обеспечение для энергосистем soft@priortelecom.ru
отдел продаж development@
priortelecom.ru

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

Оглавление


Введение

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

Известно, что задачи целочисленного программирования (ЦП), как правило, являются NP-сложными ([5]). Развитие за последние 20 лет метода направленного перебора -- метода ветвей и границ (МВГ) и создание изощренных программ для ЭВМ (главным образом, коммерчиских) в известной мере удовлетворили потребность в решении задач (частично) целочисленного программирования (ЦЛП/ЧЦЛП).

Однако, возможности МВГ очень ограничены. Оставаясь в рамках МВГ, трудно расчитывать на существенное увеличение размеров решаемых задач ЧЦЛП. Поэтому, он не применим для больших систем.

В последнее время, разработан ряд методов улучшающих МВГ. Так, в 1998 году начались исследования метода узловых векторов (МУВ). Для задач средней размерности (до 80 целочисленных переменных) время решения по алгоритму МУВ оказалось в среднем в 2-5 раз меньше, чем по МВГ. К сожалению, этот метод не применим для систем из 1000 и более узлов.

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

К оглавлению >>>


Постановка задачи

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

К оглавлению >>>


Предварительные замечания

Такая постановка является довольно типичной. В частности, если узлы — это электрогенерирующие узлы, то — минимальная и максимальная электронагрузка. (Задаются по технической характеристике агрегата.) Условие кусочно-линейности стоимостной характеристики тоже легко объяснить. Хотя агрегат может работать в любой точке отрезка , стоимостная характеристика задана только в нескольких точках. Значения стоимости в остальных точках необходимо апроксимировать. Обычно достаточно линейной апроксимации. Она работает достаточно быстро и дает ответ в пределах технической погрешности. Реже применяется апроксимация сплайнами. Она работает несколько медленнее, что не оправдывает повышение точности. Кроме того, описанные ниже алгоритмы переносятся и на случай сплайновой апроксимации.

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

К оглавлению >>>


Алгоритм

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

В начале итераций , . Далее, на каждой итерации для каждой станции строим массив приростов стоимости.

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

В результате итераций мы построили последовательность точек . — суммарная продукция, — суммарная стоимость после -ой итерации. Далее будет показано, что эти точки являются оптимальными. Поэтому если случайно совпало с одним из , то получен оптимальный ответ. В заключении будет показано, что произойдет, если не совпало ни с одним из .

К оглавлению >>>


Обоснование алгоритма

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

Значит задачу можно дискретизировать. Алгоритм дает последовательность увеличений нагрузок на станциях. Каждый шаг — это увеличение нагрузки -ой станции с до . Скорость изменения стоимости на -ом шаге обозначим .

Теорема 2
Имеет место неравенство: .

Это значит, что с каждым шагом увеличение нагрузки все менее выгодно. Ломаная — выпукла вниз.

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

Теорема 4
На плоскости построим ломаную , , . Для произвольного значения найдем оптимальное распределение нагрузок с общей стоимостью . Тогда точка лежит выше ломаной.

К оглавлению >>>


Погрешность алгоритма

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

В результате итераций получается последовательность точек . Для суммарной продукции стоимость минимальна по теореме 3, поэтому, если совпадает с одним из , то в результате алгоритма будет получен оптимальный результат. В противном случае это не так. Вообще говоря, для произвольного задачу нельзя решить подобными итерационными методами. Так как для оптимального увеличения нагрузки иногда на отдельных узлах нагрузку нужно уменьшать, то получить оптимальный ответ этим методом нельзя. Наиболее известным методом общего решения является метод направленного перебора — метод ветвей и границ. К сожалению, для большого числа узлов этот метод слишком трудоемок. В этом случае данный метод работает очень быстро, но дает погрешность. Величину погрешности можно оценить из следующих соображений.

Теорема 4 показывает, что ломаная огибает все возможные распределения снизу (по цене). Это дает нижнюю границу. Теорема 2 говорит, что эта ломаная выпукла вниз.

Если построить оптимальную кривую от , то она будет не ниже ломаной, совпадать с ней по крайней мере в вершинах ломаной, скорость ее роста меньше скорости роста стоимости на любом узле. Если добавить условие возрастания всех стоимостных характеристик (в реальных задачах это всегда так), то эта кривая тоже возрастает. Все вместе это позволяет по ломаной понять общий вид оптимальной кривой. Если узлов много, то в ломаной много вершин. Значит отклонения от оптимального распределения относительно малы. На практике все исходные характеристики заданы с некоторой погрешностью, поэтому и ответ достаточно получить с такой погрешностью. Практика показывает что при технической точности в два процента при числе узлов более 10 данный алгоритм дает необходимую точность. При меньшем числе узлов применим метод ветвей и границ. К сожалению, формат данной статьи не позволяет объяснить число 10: это статистика реальных систем.

К оглавлению >>>


Заключение

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

Алгоритм описанный в данной работе представляет большой интерес для изучения оптимизации суточных диспетчерских графиков электрических и тепловых нагрузок энергообъектов. Поэтому, данная статья является частью более общего проекта. Он описан в [2].

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

К оглавлению >>>


Литература и гиперссылки

  • [1] Лазебник Л.А. Отчет о научно-исследовательской работе: оптимизация перспективных режимов работы электростанций и энергосистем. -- М.: ЭНИН , 1984.
  • [2] Беркович Р.М., Куно М.Я., Фейман В.Г. Оптимизация суточных диспетчерских графиков электрических и тепловых нагрузок энергообъектов с учетом ограничений по скорости изменения параметров режимов, топливу, перегрузкам в электрической сети. — http://www.priortelecom.ru/Soft/PPT02.htm
  • [3] Лебедев С.С. Целочисленное программирование и множители Лагранжа. — Экономика и математические методы. 1974.Т.10.Вып.3.
  • [4] Ху Т. Целочисленное программирование и потоки в сетях. -- М.:Мир , 2000.
  • [5] Фридман Ф.А. Метод упорядоченного перебора целочисленного программирования. — Экономика и математические методы. 1974.Т.10.Вып.6.
  • [6] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. -- М.: Мир. 1982.
  • [7] Donald E. Knuth The art of computer programming. http://www-cs-faculty.standfort.edu/knuth/taocp.html

Р. М. Беркович
2003-07-03

О Компании | Новости | Как нас найти | Лицензии | Сертификаты | Вопросы? | Проектирование | Строительство и монтаж | Оборудование | Сервис | Примеры технических решений | Программный комплекс для энергетики: Советчик диспетчера, TPP, PPT02, Спрут | Системы управления.

Структурированные сети: LANConnect 200, ISCS GigaPath, кабельные системы XE | Радиосистемы и системы беспроводного доступа | АТС: Coral, Definity, Hicom | Системы передачи

Copyright © 2000