ВВЕДЕНИЕ
1 Литературный обзор
2 Модель задачи
3 Решение задачи
Планируется электрифицировать Билибинский район Чукотского АО, точнее 12 его населенных пунктов. Удобнее всего сделать это с помощью ветряных электростанций. Установить ветряные электростанции возможно в 9 местах. (Приведена карта-схема. Рис.1) Величины Cj , j = 1, . . . , n задают стоимость постройки (млн.руб.) электростанции в месте j, (Таблица 1). Поставлять энергию в населенный пункт имеет смысл, если станция находится на расстоянии не более 40 км (зона действия электростанции показана на карте-схеме).
Нужно определить, в каких местах построить электростанции, чтобы все населенные пункты были электрифицированы, а суммарные затраты на их постройку были бы минимальными.
Таблица 1 - Стоимость постройки электростанции
|
j
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
|
(млн.руб.)
|
12
|
19
|
25
|
18
|
29
|
32
|
21
|
28
|
30
|
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
Вопросы экологии и энергетической безопасности все сильнее влияют на нашу жизнь. Увеличивающееся загрязнение окружающей среды, нарушение теплового баланса атмосферы постепенно приводят к глобальным изменением климата. Современные наиболее используемые источники электроэнергии это гидро-, тепло- и атомные электростанции. Дефицит энергии и ограниченность топливных ресурсов с всё нарастающей остротой показывают неизбежность перехода к нетрадиционным, альтернативным источникам энергии. Они экологичны, возобновляемы, основой их служит энергия Солнца и Земли. К тому же возобновляемые энергоресурсы распределены относительно равномерно, поэтому лидерство в их использовании, скорее всего, завоюют страны с квалифицированной рабочей силой, восприимчивостью к нововведениям, эффективным финансовым структурам и стратегическим предвидением.
Актуальность и важность скорейшего перехода к АИЭ можно рассматривать в нескольких аспектах:
Глобально-экологический: сегодня общеизвестен и доказан факт пагубного влияния на окружающую среду традиционных энерго - добывающих технологий (в т.ч. ядерных и термоядерных), их применение неизбежно ведет к катастрофическому изменению климата уже в первых десятилетиях XXI веке.
Политический: та страна, которая первой в полной мере освоит альтернативную энергетику, способна претендовать на мировое первенство и фактически диктовать цены на топливные ресурсы;
Экономический: переход на альтернативные технологии в энергетике позволит сохранить топливные ресурсы страны для переработки в химической и других отраслях промышленности. Кроме того, стоимость энергии, производимой многими альтернативными источниками, уже сегодня ниже стоимости энергии из традиционных источников, да и сроки окупаемости строительства альтернативных электростанций существенно короче. Цены на альтернативную энергию снижаются, на традиционную - постоянно растут;
Социальный: численность и плотность населения постоянно растут. При этом трудно найти районы строительства АЭС, ГРЭС, где производство энергии было бы рентабельно и безопасно для окружающей среды. Общеизвестны факты роста онкологических и других тяжелых заболеваний в районах расположения АЭС, крупных ГРЭС, предприятий топливно-энергетического комплекса, хорошо известен вред, наносимый гигантскими равнинными ГЭС, - всё это увеличивает социальную напряженность.
Эволюционно-исторический: в связи с ограниченностью топливных ресурсов на Земле, а также экспоненциальным нарастанием катастрофических изменений в атмосфере и биосфере планеты существующая традиционная энергетика представляется тупиковой; для эволюционного развития общества необходимо немедленно начать постепенный переход на альтернативные источники энергии.
В этой связи проблема обеспечения отдаленных народов дешевой энергией и сохранения природных ресурсов является актуальной.
Целью курсового проекта является решение задачи размещения ветряных электростанций в условиях крайнего севера, а именно вычисление минимальных затрат на постройку электростанций для обеспечения энергией всех населенных пунктов.
Для достижения поставленной цели необходимо решить ряд задач, основными из которых являются:
- Изучить методы решения задач планирования и размещения и выбрать наиболее оптимальный метод для решения нашей задачи;
- Решить практическую задачу как задачу о покрытии множества;
- Рассмотреть и проанализировать алгоритм решения задачи.
Литературный обзор
Задачи размещения и планирования характеризуются следующими особенностями. На территории некоторого региона задано исходное размещение существующих объектов (например, потребителей продукци и складов) и требуется определить количество новых объектов и места их размещения с учетом их взаимодействия с существующими и между собой таким образом, чтобы оптимизировать некоторый критерий эффективности. Рассмотрим основные показатели и характеристики этих задач. К ним относятся:
а) характеристики существующих и новых объектов;
б) характер взаимодействия между ними;
в) тип пространства решений (размещений);
г) мера расстояния между объектами (метрика пространства размещений);
д) критерий оценки вариантов решений.
Одним из основных показателей, характеризующих новые объекты, является их количество. Кроме того, в зависимости от размеров, каждый новый объект можно рассмотреть либо как точку, либо как протяженный объект. В последнем случае управляемой переменной является форма объекта или форма занимаемой им площади, а задача сводится к задаче планирования размещения. Что касается существующих объектов, то они также в зависимости от размеров могут рассматриваться как точечные либо как протяженные объекты.
Кроме того, размещение может быть статическим или динамическим, детерминированным или стохастическим. Если размещение существующих объектов является управляемой переменной, то возникает задача перепланировки (размещения).
Мера расстояния (метрика пространства размещений) также может учитываться при формулировке задач размещения.
Часто в качестве приближенной оценки фактических расстояний используют евклидово расстояние. Возможны разные критерии оптимизации: минимизация суммарных затрат, минимизация максимальных затрат, максимизация некоторой прибыли. Взаимодействие новых и существующих объектов может быть:
а) зависящее от размещения и независящее от него;
б) статическое или динамическое;
в) детерминированное или стохастическое.
Пространство решений может быть непрерывным, когда новые объекты могут быть размещены в любой его точке, и дискретным, если задано лишь конечное множество точек, где возможное размещение новых объектов. [3]
Модель нашей задачи соответствует модели задач о покрытии множества. Задача о покрытии множеств формулируется следующим образом. Пусть A = {aij} -матрица размера m × n с элементами aij , равными 0 или 1. Обозначим множество индексов строк через M = {1, . . . ,m} и множество индексов столбцов - N = {1, . . . , n}.
Считается, что столбец j покрывает строку i, если aij = 1. Каждому столбцу j ставится в соответствие положительное число cj , называемое весом столбца. Требуется найти подмножество S ⊆ N, которое покрывает все строки из M и имеет минимальный суммарный вес.
Методы решения задач о покрытии множества:
- Жадный приближенный алгоритм;
- Генетический алгоритм;
- Метод ветвей и границ;
- И др.[1,2].
В данной курсовой работе будет рассмотрен «Жадный алгоритм».
Обоснование выбора метода:
- Относительно небольшая матрица
- Самый простой из существующих методов
Жадный алгоритм обладает достаточной мощью и хорошо подходит для широкого класса задач. Алгоритмы поиска минимальных остовных деревьев являются классическим примером применения жадного метода.
Жадный алгоритм — алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным. Известно, что если структура задачи задается матроидом, тогда применение жадного алгоритма выдаст глобальный оптимум. Данный метод удобен для небольших матриц.
