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

Транспортная задача - это задача отыскания таких путей перевозки продукта от пунктов производства к пунктам потребления, при которых общая стоимость перевозок оказывается минимальной.

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

Пусть в проектируемой системе электроснабжения имеется i = 1, 2,... n узлов источников питания и j = 1, 2,... m узлов потребителей. Мощность каждого из источников составляет A_i, а мощность каждого из потребителей - Bj единиц мощности (е.м.). Известно взаимное расположение узлов источников и потребителей. Стоимость передачи единицы мощности от источника i к потребителю j (удельная стоимость) составляет Zj у.е./е.м.

Общее количество возможных к строительству линий электропередачи, связывающих источники с потребителями, составляет nm. Мощности, передаваемые по этим линиям, являются искомыми переменными Xj, следовательно, количество искомых переменных составляет nm.

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

С позиций теоретической электротехники электрическая сеть является электрической цепью и для этой сети применимы все законы, известные из курса электротехники, в частности 1-й закон Кирхгофа. Для каждого i-го источника питания сумма мощностей, оттекающих по линиям ко всем j=1,2,...m узлам потребителей, равна мощности Ai этого источника

m

Для каждого j-го потребителя сумма мощностей, притекающих по линиям от всех i=1,2,...n источников, равна мо щ ности Bj этого потребителя

Соотношения (3.2) и (3.2а), представляющие собой балансы мощности в каждом из узлов, являются ограничениями при решении транспортной задачи. Общее количество ограничений равно количеству узлов источников и потребителей n+ т.

Из теоретической электротехники известно, что для любой электрической сети количество независимых уравнений, составленных по 1-му закону Кирхгофа, на единицу меньше количества узлов и составляет (n+m- 1). Следовательно, количество независимых ограничений составляет (n+m-1). Количество базисных (не равных нулю) переменных равняется количеству независимых ограничений и составляет (n+m-1). Остальные переменные являются свободными (равными нулю). Количество свободных переменных составляет (nm-(n+m-1)).

Каждая базисная переменная xij соответствует присутствию в схеме линии между узлами i и j, поскольку мощность, протекающая между узлами i и j, не равна нулю. Каждая свободная переменная x_iJ- соответствует отсутствию в схеме линии между узлами i и j, поскольку мощность, протекающая между узлами i и j, равна нулю.

В рассматриваемой постановке транспортной задачи все искомые мощности Xij, передаваемые от источников к потребителям, являются неотрицательными. Следовательно, граничные условия имеют вид

Выражения (3.1), (3.2), (3.2а) и (3.3) представляют собой математическую модель транспортной задачи. Видно, что выражения целевой функции (3.1) и ограничений (3.2) и (3.2а) являются

линейными. Следовательно, транспортная задача может быть решена симплекс-методом.

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

особенностей транспортной задачи ее решение оказывается слишком громоздким.

Особенности транспортной задачи следующие:

все ограничения имеют форму равенств;

все коэффициенты при переменных в системе ограничений равны плюс единице;

каждая переменная дважды входит в систему ограничений; один раз в балансы узлов источников (3.2), второй раз в балансы узлов потребителей (3.2а).

С учетом этих особенностей для решения транспортных задач разработаны специальные методы решения, более простые, чем симплекс-метод.

Поиск по сайту: