Транспортные задачи в сетевой постановке

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

Первая составляющая образует так называемые «постоянные» затраты, не зависящие от передаваемой мощности, вторая – «переменные» затраты.

Математическая модель задачи имеет следующий вид:

З =

где а_i – удельные затраты, пропорциональные капитальным затратам на сооружение 1 км линии;

b_i – удельные затраты на передачу 1 Мвт на расстояние 1 км;

L_i – длина участка сети;

|P_i| - абсолютное значение передаваемой мощности, полученное без учета

направления электропередачи (эта величина всегда положительна).

Для решения данной задачи может быть использован «метод ветвей и границ». Идея метода состоит в последовательном делении всевозможных вариантов на непересекающиеся группы и подгруппы, отличающиеся друг от друга тем, что в одной группе или подгруппе вариантов ветвь, по которой производится деление, присутствует, тогда как в другой отсутствует (cм. пример 6).

Для каждой группы вариантов определяется нижняя оценка затрат V, равная сумме нижних оценок постоянных V₁ и переменных V₂ затрат.

V = V₁ + V₂ = min + min .

Для определения V₁ применяются методы теории графов, для определения V₂ - стандартные методы решения транспортных задач.

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

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

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

Оптимальным решением задачи является вариант схемы электроснабжения,

для которого получено минимальное значение целевой функции.

Дата добавления: 2014-01-06