ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.10.2024
Просмотров: 86
Скачиваний: 0
Необходимость учета при разработке массива исходной информации ряда факторов (территориальное размещение потребителей относительно сети магистральных и распреде лительных газопроводов, влияние вида используемого энер гоносителя на экономику процесса, пропускная способность участков газопроводов и т. д.) обусловливает количество формируемых в каждой математической модели ограничечений.
С точки зрения технологической постановки учет всех этих факторов, влияющих на размерность задачи, позволя ет получить более представительные результаты по сравнению с вариантом реализации задачи меньшей размерности, не учитывающей всех определяющих факторов.
Исходя из этой предпосылки (необходимости реализации задач большого размера), а также из особенностей матрицы ограничений каждой математической модели, позволяющей значительно упростить вычислительную схему, при решении подзадач отдельных временных периодов использованы идеи блочного программирования.
Детальное описание алгоритма разложения Данцига— Вулфа (метода декомпозиции) применительно к матрицам, имеющим ярко выраженную блочную структуру, приведено в работах [56, 69, 134]. Поэтому в данной работе остановимся на основных особенностях алгоритма применительно к кон кретным подзадачам распределения ресурсов природного га за между потребителями в отдельные периоды года.
Особенность матрицы ограничений отдельных подзадач заключается в следующем: все коэффициенты при неизвест ных в группах ограничений (9-22) и (9-28) равны единице; группы ограничений (9-22) и (9-28) имеют цепочную струк туру (каждое неизвестное входит только в одно уравнение); все ограничения (9-25) — (9-28) подзадачи второго периода являются неравенствами; часть ограничений в группе (9-22) подзадачи первого периода являются строгими математиче скими равенствами. Последние две особенности определяют некоторое отличие вычислительных схем отдельных подза дач. Так как на ЭЦВМ в первую очередь реализуется мате матическая модель второго периода, рассмотрим алгоритм решения этой задачи при условии, когда все ее ограничения являются неравенствами.
Особенности алгорита решения модели осенне-зимнего периода. Разделим матрицу ограничений модели второго периода на два блока. К первому блоку относим ограничения
260
(9-25), (9-26), (9-27), ко второму — (9-28), (9-29). Ограниче ния первого блока (с учетом дополнительного ограничения) образуют вспомогательную p-задачу, ограничения второго блока — вспомогательную у-задачу.
Для формирования вспомогательных задач примем сле дующие обозначения: вектор любого опорного решения вспо могательной у-задачи — Уѵ‘, матрица коэффициентов при неизвестных в ограничениях (9-25), (9-26), (9-27) — S; вектор свободных членов ограничений (9-25) — (9-27)
А — (ßj',. . . , öl, • • •»Op, Qi, . . . , <7/)т
(где символ т — знак транспонирования — указывает, что вектор А, компоненты которого выписаны в строку, являет ся вектором-столбцом); каждая компонента вектора А — ах, причем
т = 1, 2 , . . . , (т + р + /).
' Запишем следующие соотношения в векторной форме:
|
|
Рѵ = |
5 ПУѴ; |
|
(9-35) |
|
|
dv = |
CYV, |
|
(9-36) |
где |
каждая |
компонента вектора Р ѵ обозначается |
как р*. |
||
На основании принятых |
обозначений и |
соотношений |
|||
(9-35) и (9-36) сформируем вспомогательную р-задачу. |
|||||
Максимизировать |
N |
|
|
||
|
|
h = |
|
(9-37) |
|
|
|
|
|
||
|
|
V =1 |
|
|
|
при |
ограничениях-неравенствах |
|
|
||
|
N |
Px^ < ад х — 1 * 2........ (т + р + |
|
|
|
|
2 |
/); |
(9-38) |
||
|
Ѵ=1 |
|
|
|
|
при |
ограничении — равенстве |
|
|
||
|
|
N |
|
|
|
|
|
2> ѵ |
= 1; |
|
(9-39) |
|
|
Ѵ = І |
|
|
|
при несвободных переменных |
|
|
|
||
|
|
рѵ > 0 ; ѵ = |
1, 2, |
|
(9-40) |
|
|
|
|
|
26t |
I
Отличительной особенностью вспомогательной задачи является значительно меньшее количество ограничений, чем в исходной математической модели осенне-зимнего периода. Вместо группы ограничений в исходной задаче (9-28) во вспомогательной задаче записывается одно дополнительное ограничение (9-39).
p-задача реализуется на ЭЦВМ модифицированным симп лекс-методом. Для отыскания разрешающего столбца (вво димого в базис векторов) запишем задачу, сопряженную за
даче (9-37) — (9-40). |
|
Прямая р-задача: |
Сопряженная задача: |
Максимизировать |
Минимизировать |
N |
т + р + І |
h = 2^ѵРѵ |
Y = 2 а*и* + ъ (941> |
ѵ=1 |
т=1 |
при ограничениях-неравенствах при несвободных переменных
N |
|
|
2 рХ 0т. |
ыт > 0; т = |
|
Ѵ=1 |
|
|
т = 1, 2 , . . . , ( т + р + І), |
= 1 1 2 , . . . , ( т - j- p + l ) , |
( 9 - 4 2 ) |
при ограничении-равенстве |
при свободной переменной |
|
N |
« і $ 0 , |
( 9 - 4 3 ) |
|
||
Ѵ =1
при несвободных переменных при ограничениях-неравенствах
рѵ > 0; ѵ = 1, 2, .. .N
2 Ftyb + v i > |
d vl V = |
T=1 |
|
= 1 , 2 |
( 9 - 4 4 ) |
Имея значения двойственных переменных (определяемых из последней строки симплекс-таблицы p-задачи), можем определить, какое из ограничений сопряженной задачи
(9-41) — (9-44) не выполняется, т. е.
« т < 0 ; т= 1 , 2 |
, ( т + р + І) |
( 9 - 4 5 ) |
либо |
|
|
т + р+ І |
|
|
2 Р Х + Ѵі < d v ; V = 1 , 2 |
(9 ‘ 4 6 ) |
|
• t . - |
|
|
262
Запишем неравенства (9-45) и (9-46) следующим образом:
|
|
|
— нт > 0 ; т = 1, |
2 ,...,( т |
+ р + іу, |
|
(9-47) |
|||||
|
— |
2 |
|
|
— » i > 0 ; |
v = |
1, |
2 ,...,N . |
(9-48) |
|||
|
|
|
X—1 |
|
|
|
|
|
|
|
|
|
Подставив |
в формулу (9-48) |
соотношения |
(9-35) и |
|||||||||
(9-36), |
получим выражение |
r |
sn |
|
-I |
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|||
т |
п |
I |
|
|
|
|
Ь1 |
|
|
|
|
|
22 2 |
—(Цц • • * »Urn+p+z) |
|
|
+ СЦг( |
+ |
|||||||
<«=!/=! Г= 1 |
|
|
|
|
сП |
|
Иг |
|
|
|||
|
|
|
|
|
|
|
^ |
|
|
|
||
|
|
|
|
|
|
|
m+p+Z |
|
|
|||
|
р |
п |
I |
|
|
|
|
|
|
|
|
|
+ 2 2 2 . |
■(til, . .. » Mpj-f-p-^-/) |
|
|
+ |
|
|||||||
|
/'» 1 |
/ « J г=«І |
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
сП |
|
|
|
|
|
|
|
|
|
|
|
L- '’ш+р-Н -*t'ir |
|
|||
|
|
|
|
|
+ C'i гГ,/г- Оі> 0 , |
|
|
|
(9-49) |
|||
где s'1...... sm+p-K |
— элементы |
ijr- либо i'jr-го вектора-столб |
||||||||||
ца матрицы S11 (индексы 1, |
т + р + / |
условно показы |
||||||||||
вают, в какой |
строке |
матрицы S11 стоит данный элемент); |
||||||||||
yjjr и 2£/г |
— значения |
неизвестных в одном из |
опорных |
|||||||||
решений следующей вспомогательной у-задачи. |
|
|
||||||||||
Максимизировать |
|
|
г «и |
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
||
т |
п |
I |
|
|
|
|
|
|
+ сі1г УHr + |
|||
w = 2 2 |
|
2 { |
(ИХ* • • • I ит+р+і) |
|
|
|||||||
і = 1 / = |
1 г = 1 |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
-s'1 |
|
Z/r |
|
|
|
|
|
|
|
|
|
|
|
т+р+1 |
|
|
|
|
р |
п |
I |
|
|
|
|
|
|
|
|
|
|
+ 2 2 2 |
•(«!, |
• • . |
I Um+p+/) |
|
|
t'l’r + |
с’ |
Zi'fr |
||||
»•'=1 /= 1 |
Г= |
1 |
|
|
|
|
S:,П |
|
|
|
|
|
|
|
|
|
|
|
|
L |
|
|
|
|
|
|
|
|
|
|
|
|
|
m+P-W • |
|
(9-50) |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
263
при условиях |
|
|
|
|
|
|
m |
l |
p |
i |
|
|
|
2 |
%Уііг + |
2 |
2 |
Zi'f + Уі= br / = |
1. 2 ,..., п, |
(9-51) |
|
|
Г=1Г=1 |
|
|
|
|
|
|
УUr > |
0; (// > 0; z,./r > |
0. |
(9-52) |
|
Оценки функционала задачи (9-50) — (9-52) изменяются и формируются на каждой итерации p-задачи. Опорное ре шение у-задачи (на каждой итерации p-задачи) находится следующим образом.
Полагаем, что в каждом из уравнений системы (9-51) только одно неизвестное отличается от нуля, т. е. решением системы является вектор Уѵ, для каждого j только одна из компонент которого у**, либо zy*r, либо уѴ* отличается от
нуля и равна
Индекс этой компоненты (для каждого / = 1, 2, ..., п) вычисляется из следующих соотношений:
для множества уцг
для множества z,'/r
max — (ult • • • »
Для множества искусственных переменных у/ оценки в функционале (9-50) равны нулю.
Таким образом, опорное решение вспомогательной у-за- дачи (на каждой итерации p-задачи) находится весьма про сто, не требуя использования специальных методов линейно го программирования. Благодаря этому упрощается вычи слительная схема всего алгоритма решения модели осеннезимнего периода.
При реализации на ЭЦВМ информация, которая необ ходима для формирования вектора, вводимого в базисное множество векторов вспомогательной p-задачи, сосредото
264