Файл: Арутюнян А.Г. Применение математических методов и ЭВМ в народном хозяйстве.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 17.07.2024
Просмотров: 184
Скачиваний: 0
степенно сужать добавлением к условию (14.7) дополни тельных условий вида
V х л ( A + ^ O + ^i. к+1 ^ 0 , |
(14.8) |
где
Но количество ограничений вида (14.8) не может пре восходить т. Значит максимальное количество перебирае мых направлений может быть т-\-1.
Приведем другой способ выбора направлений, который, по сравнению с описанным во многих случаях, будет более эффективным. Если /-ой строке симплексной таблицы со ответствует искусственная базисная переменная, то в ка честве направления выбирается внутренняя нормаль к гра ничной гиперплоскости полупространства
к |
(14.9) |
V * ik >,k + Х\, к+1 0. |
Если при движении по этому направлению попадаем в полупространство (14.9), то тем самым из базиса исклю чается i-ая искусственная переменная. Тогда выбирается одна из оставшихся строк, содержащая искусственную пе ременную. Если же при движении !вдоль данного направ ления попадаем на граничную точку области разрешимости однопараметрической задачи, не пересекая граничную ги перплоскость полупространства (14.9), то заключаем, что многопараметрическая задача неразрешима. Действительно, если вдоль указанного направления данная искусственная переменная не исключается из базиса, то она не будет исключена и при движении вдоль любого направления.
Как видно, второй способ выбора направления в не которых случаях может быть неэффективным по сравнению с первым, однако он гарантирует выявление случаев не разрешимости задачи за конечное число выборов направ лений.
262
Предположим, теперь, что при движении но выбран ному направлению можно попасть вточку A £ jV. Очевидно, функция F (Л) порождается данным базисом на некотором выпуклом многогранном множестве Nv содержащем эту точку, причем эта точка находится на грани множества JV„ которое определяется системой линейных неравенств
_ |
к |
•*io(A) = |
X •*«'-1+-Чк+|5*0, 1— 1, 2..... т. (14.10) |
|
k—1 |
Используя метод М. Л. Балинского (см. [931), можно найти все вершины множества Nv Однако этот метод до вольно трудоемкий и, как будет показано в дальнейшем, нет необходимости в определении всех вершин этого множества.
Так как каждое множество А , связано с определен ным базисом Б-, то запоминанием базисов Б-, выражений базисных компонент соответствующих опорных планов н выражений функции Р(Л ), можно последовательно перейти от одной области к другой и в конечном итоге найти все множества Nx.
Приведем краткое описание алгоритма переходов от граничных гиперплоскостей к соседним множествам Nx.
В симплексной таблице, соответствующей базису Б0£М, выбираем первую строку (/= *1) и из имеющейся точки Л® двигаемся по направлению нормали к граничной гипер плоскости
Л ^ А ) — 0 |
(14.11) |
при г = 1 .
По этому направлению решается однопараметрическая задача, в результате чего определяются отрезки [nt, im+i|. изменения численного параметра ц, на каждом из которых функция
?1 М = F (Л’ + 4 S,)
порождается определенным базисом S t. Ясно, что критиче ским точкам [г, соответствуют /(-мерные точки Л '= Л °+(1,5, находящиеся на критических (граничных) гиперплоскостях соответствующих множеств Nt.
Через конечное число переходов получается критиче ская точка (л-т,» правее которой либо задача (однопарамет-
263
рическая) |
неразрешима, |
либо функция |
<fj(y-) порождается |
|||||||
одним |
и |
тем |
же базисом. |
Переходя |
к /(-мерной точке |
|||||
Лт‘ = Л п+ |
И тД обнаруживаем, |
что этому лучу соответст-. |
||||||||
вует некоторое полупространство пространства /?к. |
||||||||||
Отметим, что при каждом переходе по направлению |
||||||||||
соответствующие |
базисы |
/>t |
включаются |
в множест |
||||||
во Л1. |
|
|
|
|
|
|
|
|
|
|
В точке Лт‘ |
выбирается |
новое направление S2, совпа |
||||||||
дающее |
с |
нормалью |
к |
граничной |
гиперплоскости (14.11) |
|||||
при 1 = |
2, |
и повторяется |
описанный |
выше процесс только |
||||||
с той лишь разницей, |
что при переходе к новому отрезку |
|||||||||
в однопараметрической |
задаче |
получаемый |
базис сравни |
|||||||
вается с базисами множества М. При появлении базиса, имеющегося в множестве М, процесс перехода но данному направлению прекращается и реализуется переход к рас смотрению следующей строки.
Таким образом, путем рассмотрения всех строк сим плексной таблицы, последовательно выбираются направ
ления |
Sj и базисы |
Бт | т = V Ti-\- t |
строятся все области |
/V, и |
даются выражения функции F (Л) |
на этих множествах. |
|
В случае К = |
2 описанный алгоритм чрезмерно упро |
||
щается. Оказывается, что этим алгоритмом пользоваться легче, чем алгоритмом, предложенным Иренеушом Ныков-
ским (см. [59]).
Блок-схема изложенного алгоритма решения задачи
(14.1)— (14.3) |
приведена на стр. 265 и 266. |
||
Приведем пример параметрической задачи для случая |
|||
двухмерного |
векторного параметра Л = (Х ,, ).2), |
||
Пример. |
Для каждого A = |
().j, >.„) построить функцию |
|
|
F (А ) = т ах/ = |
max {2х, — Злс2), |
|
% |
G\ |
°А |
|
где множество Оц определяется |
условиями: |
||
|
Зхг— 2лг2 ^ |
+ 2>.2, |
|
|
—х г— * 2s£3X2 — 1, |
||
|
х ,^ 0 ; |
х 2^ 0 . |
|
Задача решается первым алгоритмом метода последо264
Блок-Схема решения задачи параметрического линейного программирования с линейно зависящим от параметра вектором ограничений
Начало
Все ли (позволяющие исклю 0 . чить искусственные векторы)
направления рассмотрены?
265
Продолжение блок-схемы решения задачи параметрического линейного программирования с линейно зависящим от параметра
вектором ограничений
266
вательного |
улучшения плана. |
Процесс |
решения записан |
||||||
в приведенных |
ниже таблицах. |
|
|
|
|
|
|||
Базис |
X, |
h |
с , . , . |
Р, |
Рг |
р э |
Л |
Номер |
|
итерации |
|||||||||
Р э |
1 |
2 |
0 |
I I I |
— 2 |
|
0 |
|
|
РА |
0 |
3 |
— 1 — 1 — 1 |
|
1 |
0 |
|
||
- |
О |
0 |
|
— 2 |
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
Базис |
>1 |
X, |
св. ч. |
Р, |
Р2 |
Р3 |
РА |
Номер |
|
итерации |
|||||||||
Р, |
1 |
2 |
0 |
1 |
2 |
|
|
|
|
3 |
3 |
3 |
|
|
|
|
|||
|
|
|
|
|
|
|
|||
' 4 |
1 |
11 |
|
|
5 |
|
|
|
|
|
|
|
|
3 |
3 |
|
|
|
|
|
|
|
|
|
5 |
2 |
0 |
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таким |
образом, |
всего |
одна |
итерация приводит |
к вы |
||||
полнению условия |
оптимальности. |
|
|
|
|
||||
Необходимость |
в столбцах |
^ и |
£1 появляется |
только |
|||||
на первой итерации, когда получен оптимальный базис. Выбирается точка Л<0>, направление 6' и достраиваются СТОЛбцЫ (1 и р,
Л<°> определяется из таблицы итерации 1 по формуле
+ |
|
+ |
( / « 1 , 2), |
т. е. |
|
|
|
— X. -4- — >. + 0 ^ 0 , |
|
||
3 I T |
3 |
2-Г |
|
J _ x _l _LLx i x ) .
3 3 *
Принимая >-2— 1, получим:
— X, Д - Л ^ о , Х ,^ 2 ; |
|
3 1 г 3 |
1 |
. _L> + _ - з = о , x ,s *8 . |
|
3 1 Л 3 |
’ 1 |
37
Для простоты можно взять >4 = |
1, т. е. получить |
A|0, = ( U ) . |
_ _ - |
В качестве направления выбирается |
вектбр S = 0 —-V '. |
Достраивает имеющаяся |
таблица: |
|
|
|
|
|||||
Базис |
X, |
х2 |
св. ч- |
|
Р2 |
Р 3 |
Л, |
I1 |
|
Номер |
|
|
итерации |
||||||||
|
|
|
0 |
1 |
_2_ |
|
0 |
— 1 |
1 |
|
|
|
|
3 |
3 |
||||||
|
|
11 |
— 1 |
0 |
Г |
1 |
|
— 4 |
3 |
1(0) |
|
|
|
3 |
|
- |
|||||
|
|
|
|
|
|
|
|
|
||
- |
|
|
0 |
0 |
5 |
|
0 |
—2 |
2 |
|
3 |
3 |
3 |
з ’ |
|
||||||
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
||||
Коэффициент при р. в первой строке равен — ^ 8 1к/^0>= |
||||||||||
|
|
|
|
|
|
|
|
|
|
k—1 |
. |
1 |
2 . |
1» а свободный член— |
|
|
К |
||||
= — { — + |
— |
|
|
= |
||||||
= — + — + 0 — 1.
Аналогично получаются элементы второй и третьей строк.
268