Файл: Пояг, М. А. Комплексное использование и охрана водных ресурсов Молдавии.pdf

полнительный так называемый фиктивный водопотребитель, которому в качестве объема спроса приписывает­ ся разница между общим объемом воды и фактической потребностью в ней, то есть

После введения фиктивного водопотребителя открытая водотранспортирующая задача преобразуется в закры­ тую модель.

Выполним первое распределение объемов воды мето­ дом северо-западного угла.

У первого водоисточника имеется 2 235 млн. м3, а пер­ вому водопотребителю требуется 3 798 млн. м3 воды, поэтому все 2 235 млн. м3 записываем первому водопо­ требителю. При этом для удобства водоподачу записы­ ваем в первом нижнем углу клетки.

Так как все запасы первого водоисточника распреде­ лены, приступаем к распределению запасов воды второ­ го водоисточника. Во втором водоисточнике имеется 993

потребителю 993 млн. м3 воды от второго водоисточника. При этом ему еще недостает 570 млн. м3 (1563—993). Снова записываем первому водопотребителю недостаю­ щие 570 млн. м3 воды от третьего водоисточника, а у по­ следнего остается еще 19 м3 (589—570). Эти 19 млн. м3 от третьего водоисточника передаем второму водопотре­ бителю, которому не хватает еще 837 млн. м3 (856—19). Они доставляются от четвертого водоисточника. У чет­ вертого водоисточника осталось еще 313 млн. м3 (1150—— 837), которые доставляются третьему водопотребителю, и тем самым полностью распределяются запасы воды четвертого водоисточника. Этим заканчивается распреде­ ление водных ресурсов;" все водопотребители удовлет­ ворены и вся вода распределена. Следовательно, полу­ чен первоначальный опорный план распределения потребностей, Удельные затраты воды в клетках с потреб­ ностями, то есть в занятых клетках, обведены квадрати­ ками.

Прежде чем проверить на оптимальность полученную схему распределения поставок воды, необходимо прове­ рить количество занятых клеток. Их должно быть

151

га+ П'—1, так как допустимое распределение поставок во­ ды можно выполнить только в том случае, если число за­ нятых клеток не меньше, чем m + n— 1. Однако допусти­ мое распределение по произвольному набору такого чис­ ла занятых клеток выполнить не всегда можно. Необхо­ димо выполнение и других условий:

а) в каждом столбце или строке должно быть не ме­ нее одной занятой клетки, а любая занятая клетка мо­ жет оказаться единственной в своей строке или столбце, но не может быть единственной одновременно и в столб­ це, и в строке;

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

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

Проверим, составляют ли занятые клетки в табл. 20 вычеркиваемую комбинацию. Начнем просмотр матри­ цы со строк. Вычеркнем занятые клетки 1,1 и 2,1, явля­ ющиеся единственными в своих строках. Переходим за­ тем на просмотр столбцов и вычеркиваем клетки 3,1 и 4,3 — единственные в своих столбцах. Снова просматри­ ваем матрицу по строкам и вычеркиваем клетки 3,2 и 4,2. Следовательно, занятые клетки расположены в порядке вычеркиваемой комбинации.

Если в матрице число занятых клеток будет меньше гп+ п—1, то имеют место случаи вырождения задачи и ее решение затрудняется. Для устранения случая вырож­ дения необходимо поменять местами строки или столб­ цы или же свести в некоторые клетки так называемые нулевые водоподачи. Для этого вписывается в опреде­ ленную клетку нулевая поставка и клетка считается за­ нятой. В нашем случае заполненных клеток 6 , то есть равно гп+ п— 1 (3+4—1). Следовательно, план не явля­ ется вырожденным и можно продолжить решение за­

дачи.

152

После первого распределения поставок подсчитыва­ ется общая стоимость транспортирования воды

ШШ

F(x) = 2 ^С,,-X,j = 0,1199x2235+0,1184x993 +

wJ=i

+0,1231 х 570+0,0211X 19+ 0,147X 837+0,0278 х 313 =

=268+118 + 72 + 0,4+12 + 8,6 — 479 млн. руб.

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

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

153

д, 13= 0,1231 — 0,1184 + 0,0147 — 0,0211 +0,0323 -

-0.0278 = +0,0028.

Теперь рассмотрим, что собой представляют характе­ ристики, вычисленные для каждой цепи.

Очевидно, для улучшения исходного распределения водотранспортирования необходимо проверить целесооб­ разность перемещения части запасов воды из занятых клеток в свободные. Если в клетку 1,2 запишем транс­ портирование хотя бы одного кубометра воды, то для сохранения общей балансировки водных ресурсов по строкам и столбцам придется в клетке 1,1 по той же строке уменьшить поставку на кубометр воды, и баланс воды по первой строке сохранится. Для сохранения же баланса воды по первому и второму столбцам придет­ ся в клетке 2,1 увеличить, а в клетке 2 ,2 уменьшить на кубометр воды. В результате такого перераспределения кубометра воды по первой цепи мы уменьшаем удельные затраты на 0,0009 руб. (0,0181—0,1199+0,1184—0,0175).

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

154

Характеристика клетки 1,3 показывает, что перенесе­ ние поставок в эту клетку вызывает уменьшение удель­ ных затрат в размере 0,0115 руб. ( + 0,0124—0,0181— —0,0323 + 0,0175) в расчете на кубометр воды.

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

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

Внашем случае отрицательная характеристика при­ надлежит клетке 2,3 (Л 2,3 = —0,0086). Поэтому по дан­ ной цепи и выполняется перераспределение поставок так, чтобы в свободной клетке появились поставки. Для этого вдоль всей цепи перемещается такой объем воды, который равен наименьшему объему водоподачи одной из ее занятых клеток, имеющей в цепи отрицательные удельные затраты. Этот объем вычитается из объемов водоподачи всех клеток данной цепи с отрицательными затратами и прибавляется к объему водоподачи всех клеток цепи с положительными затратами. В результате такого перемещения сохранился баланс воды по всем строкам и столбцам матрицы.

Вцепи, построенной для свободной клетки 2,3 пере­

мещается поставка, равная 313 млн. м3 воды. После этой поставки вдоль всей цепи получается следующее но­ вое распределение воды в клетках этой цепи: Х41=313— —313 = 0; Х23=0+313=313; X,, = 993—313=680; Х42= = 1150—294=856.

После этого составляется новая таблица распределе­ ния поставок воды с учетом выполненного перераспре­ деления по цепи 2 , 3(табл. 2 1 ).

В результате полученной новой схемы .распределения водных ресурсов приведенные затраты уменьшились на 2,7 млн. руб. (31ЗХ 0,0086). Все затраты по транспорти­ рованию воды водопотребителям составят 476,3 млн. руб. (479,0—2,7). Однако следует проверить, является ли полученная схема оптимальной. Для этого, снова со-

155

155

Наличие отрицательных характеристик указывает на неоптимальность схемы и необходимость дальнейшего

ееулучшения.

Вцепи, построенной для клетки 1,3, перемещаем

объем наименьшей поставки из вершины с отрицательным тарифом, то есть 313. После перемещения этой поставки

с учетом перераспределения водных ресурсов в цепи клетки 1,3 (табл. 22).

157