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

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

Адрес: 115184,
г. Москва,
ул. Татарская Б. 35, стр.2;

Многоканальный
телефон
: (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
Rambler's Top100
Яндекс цитирования

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

Оглавление


Введение

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

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

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

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

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

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


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

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

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


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

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

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

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


Алгоритм

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

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

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

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

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


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

Теорема 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 © 1999-2023