Файл: Арутюнян А.Г. Применение математических методов и ЭВМ в народном хозяйстве.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 17.07.2024
Просмотров: 170
Скачиваний: 0
{1 — 2p(b-*)\ (l), |
если j — j\, * = 1 , 2,..., |
m, |
j c j= 1— X |1 — 2p (*,*)} (i>i — /tJk), если i = j 0t |
(22.14) |
|
О, если j£ i,
будет оптимальным опорным планом задачи (22.4)—(22.7). Теперь на величины 1ц ставим более четкие ограниче ния. Очевидно, условие (22.2) не является пока строго огра ничивающим. Такое ограничение не только способствует установлению отношения порядка в множестве векторов Lit но и позволяет при решении рассматриваемой задачи не запоминать компоненты этих векторов. Последнее обстоя тельство в свою очередь облегчает практическую реализа цию решения этой задачи на ЭВМ, при больших значениях т и 7) (/= 1 , 2,..., т). Отметим, что общее количество век
торов Aj (следовательно и векторов Zy) будет iV= Tj-f-l.
Так как векторы At и £j являются /«-мерными, то для хране
ния компонентов всех векторов |
-необходимо |
т (1 |
J 7^) |
ячеек памяти ЭВМ1. |
|
|
i-t |
|
|
|
|
Если, например, т—6, 7'1= 7 ’2= ...= 7в= 5 , |
то для этого |
||
не достаточно’ оперативного запоминающего устройства со временных ЭВМ (это количество будет порядка_94 тысяч).
Величины /у можно определить следующим способом.
Принимается /, = /«, у = 1 , /|, = 0 |
(/= 1 , 2,..., т). |
||
Если /у < Ти, |
то |
|
|
|
1ц при |
i =f* tj, |
(22.15) |
|
7i,j-Н |
при 7«ei, |
|
|
|
||
и для каждого i2 = |
m, m — 1,..., / , -И |
величины /у меняют |
|
ся в пределах 0-5-7^, фиксируя каждый раз величины 1ц для i < /а.
Если же /у = |
7) и ^ > 1 , то |
уменьшается на |
единицу |
|
и возвращается |
к формуле (22.15). Этот |
процесс |
продол-1 |
|
1 Компоненты |
соответствующих векторов Д) |
определяются форму |
||
лой (22.1). |
|
|
|
|
307
жается до тех пор, пока |
получится ^=1 и 1-,j = |
7'i (при |
этом j = n). |
|
|
Из изложенного видно, что при указанном специаль |
||
ном виде матрицы условий |
задача представления |
вектора |
В в виде выпуклой комбинации ближайших (w -j-1) векто ров заданной матрицы имеет настолько простую геометри ческую интерпретацию, что ее решение осуществляется даже простой вычислительной схемой.
Блок-схема решения задачи (22,4)—(22.7) приведена на стр. 309.
§ 3. Применение методов параметрического линейного программирования для решения нелинейной задачи
В предыдущей главе были приведены примеры приме нения методов ПЛП для решения различных специальных видов задачи линейного программирования. Методы Ш1П успешно могут быть применены и для решения многих нелинейных задач. Примером этого факта является пара метрический метод Хаутеккера для решения задачи квадра тичного программирования (см. [41]).
Приведем еще один пример применения методов ПЛП.
В качестве примера будем |
рассматривать |
задачу (21.2)— |
|||
(21.4) в условиях изменения |
правых частей системы огра |
||||
ничений |
(22.3). |
Предположим, |
что вектор |
ограничений Я |
|
линейно |
зависит от численного |
параметра |
т. е. |
||
|
b\ = |
bi0-\-bh l, £ = 1 ,2 ,..., т. |
(23.1) |
||
Нетрудно заметить, что каждая основа задачи (21.2)— (21.4) является базисом на всей оси изменения параметра X. Следовательно, опорный план, полученный для некоторого
значения |
остается опорным планом этой задачи на всей |
||
действительной оси1. |
|
||
Из формулы (21.1) видно, что величины pj5 следова |
|||
тельно и целевая |
функция (21.2), зависят от параметра |
||
1 Справедливость |
этого факта |
следует из отсутствия ограничения |
|
на знак переменных. При наличии |
этих ограничений допустимость дан |
||
ного опорного |
плана |
сохраняется |
только на конечном интервале или |
на луче. |
|
|
|
Блок-схема решения нелинейной задачи со специальной структурой матрицы условий
Начало
1.Вычисление компонентов векто ра В* по формуле (22-9).
12. Вычисление компонентов векто ра Lit по формуле (22.10).
3.1 -»■*.
Вычисление компонентов 2 вектора Zj по формуле
(22.12).
— ш
309
Значит, признак оптимальности данного опорного плана сохраняется только на определенном интервале изменения Так как вследствие изменения >. точка # (/.) смещается, то меняются и величины f-j (/.). Для изучения поведения величин pj(>.) предположим, что в точке >.=0 имеется опор ный план, и по формуле (21.1) вычислены все рДО). Квад
ратичные функции pj2(>.) представляются в виде
Pj! ('•) = I »!, - 2>. £ Ьп ( а. — |
У= 1,2 |
п. (23.2) |
1=1 1-1
Выберем теперь два индекса у, и у2 и рассмотрим раз ность
р;, ('■ )-?], (ч = р ;, .(о ) - р ; , m |
£ 6ii(a,h __ ttjii). |
(23.з) |
Полученное соотношение показывает, что pj* (>.)—р / (>.) представляет собой линейную функцию от параметра и знак выражения
£ |
— а„.) |
|
(23.4) |
определяет поведение |
указанной разности |
при изменении |
|
Поскольку выражение вида (23.4) зависит только от |
|||
пары индексов j\ н у2 |
и не зависит от параметра |
то за |
|
ранее можно установить определенное отношение квази порядка в множестве векторов А^ условий задачи (21.2)— (21.4). Для обозначения этого отношения, следуя С. Бержу
(см. [15]), употребляем символ |
а отношение назовем |
|||
предшествованием. |
|
|
||
Точка |
предшествует |
точке |
/4j, (или точка Ajt сле |
|
дует за точкой |
Л;,) и обозначается |
|||
|
|
|
|
(23.5) |
если для |
них |
выражение' |
(23.4) |
неположительно. Точки |
А , и А1г назовем эквивалентными и обозначим |
||||
|
|
А , = |
Aj„ |
(23.5') |
если для них выражение (23.4) принимает нулевое зна чение.
310
Легко заметить, что все точки, связанные между со бой отношением эквивалентности, лежат на некоторой ги
перплоскости, для которой направление вектора |
В' = (Ьп, |
|||||
Ьп ,..., &пц)т совпадает |
с направлением нормали. Если точ |
|||||
ки |
Аи и Aj, |
связаны |
соотношением |
(23.5), |
то |
разность |
Pj |
(*•)— р]г( ') |
является |
возрастающей |
функцией от |
|
|
|
Обозначим через |
N множество |
{1, 2,..., |
га), |
а через |
|
/(0 ) — множество индексов базисных векторов такого опор
ного плана |
задачи |
(21,2)—(21.4), для |
которого |
в точке |
|||||
>.= 0 обеспечен признак оптимальности. |
Ясно, что для лю |
||||||||
бой пары индексов у ,£ /(0 ) |
и j £ N \ I ( 0 ) |
имеем |
|
|
|||||
|
|
■ |
PJ, (0) |
|
PJ, (0), |
|
|
(23.6) |
|
которое |
эквивалентно соотношению |
|
|
|
|||||
|
|
Pj, (0) |
Pjj (0) ^ |
О, |
|
|
(23.6') |
||
причем равенство может иметь место |
только |
в |
случае, |
||||||
если |
|
Pji (0) = |
maxpi (0) и |
pj,(0) = |
raiirapj. |
|
|
||
|
|
|
|
||||||
|
|
|
igl |
|
|
|
ill |
|
|
Возьмем |
теперь некоторый |
индекс |
j £ ! и |
определим |
|||||
подмножество |
|
|
|
|
|
|
|
||
|
|
I {j,) = |
{ i l H A ^ A l - |
|
|
|
(23.7) |
||
Найдем далее |
|
|
|
|
|
|
|
||
|
>.<!)==* min- |
|
Pi ,(0) — |
Pj (°) |
|
|
(23.8) |
||
|
|
|
|
|
|
||||
|
|
Jel(Ji) |
|
^ i i ( a iji — а п ) |
|
|
|
||
|
|
|
2 |
£ |
|
|
|
||
Если для каждого у£/ определить подмножество (23.7) |
|||||||||
и соответствующее |
число (23.8), |
то минимальное из полу |
|||||||
ченных |
чисел >.(1), |
Х(2>,..., |
>-,т) будет определять |
правую |
|||||
границу такого интервала изменения параметра |
|
на кото |
|||||||
ром имеющийся при >.=0 опорный план остается оптималь ным. Это следует из того, что знак разности pj, (>•) — Pj« (*) совпадает со знаком разности pj (>.) — pjt (>.) на всей дейст вительной оси изменения параметра X.
Заметим, что, в частности, полученная правая граница может совпадать с точкой Х = 0. Очевидно, что в этом
311
