Файл: Арутюнян А.Г. Применение математических методов и ЭВМ в народном хозяйстве.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 17.07.2024

Просмотров: 185

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

где область 0 ,д ( /? п+т определяется условиями:

пк

X «и х, (А ) + x„+i (Л) =

+

V Ьл кк,

1^=1, 2..... т,

(14.2')

J -i

 

k -i

 

 

* ,( Л )> 0 ; у =

1*

2..... я +

да.

(14.3')

При сделанных выше предположениях относительно величин 5ik и Ьх для достаточно удаленных от начала коор­ динат (хотя бы вдоль одной оси) точек задача (14 .Г )— (М .З')имеет исходный базис. Действительно, выбором век­

тора X (Л) = (х г (Л), x i (.\).....

JCn+m(A), с компонентами

! 0,

при _/«= 1, 2.....

п,

*

 

 

1.

8ik'k + 6j, при y = « -f-l, л +2,..., п-\-т,

строится исходный опорный план расширенной задачи. Зна­ чит основа, состоящая из единичных векторов, образует базис этой задачи.

Для нахождения точки допустимости задачи (14.1)— (14.3) решается расширенная задача. Для решения расши­ ренной задачи с помощью видоизмененной схемы метода последовательного улучшения плана исходная симплексная таблица заполняется следующим образом. В первых К

столбцах

первых т строк помещаются величины 8ilt, в

(К ~|-1 )-ом

столбце — величины Ь{. В остальных столбцах

первых т строк помещаются величины aVy В первых (/(+ 1 ) столбцах (/й -|-1)-ой строки помещаются нули, а в осталь­

ных столбцах — коэффициенты

с, из выражения (14.1) с

обратным

знаком. В первых К столбцах (/га+2)-ой строки

помещаются величины — £

g.b

в (/С —}-1)-0м столбце — ве-

 

i - 1

 

 

личина V

Ь„ а в остальных

столбцах — величины V а,..

U 1

 

 

1= 1

С целью единообразия элементы симплексной таблицы

обозначим

через х и.

 

 

Ясно, что значения базисных переменных в каждой точке определяются формулой

257

17—644

,Xji = ^i0(A ) = V

)'i ~f“ x \,к-t i. i = l , 2,..., m.

(14.4)

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

В основной части симплексной таблицы отыскивается

 

.

 

*Хт+2, Ь ”

min

j

 

 

 

 

 

 

 

K+2<j<K+-n +l

 

 

 

и

определяется

знак этой

величины. Если

х т+.2,

 

то

вектор с

номером

у — ( /( + 1 ) подлежит вводу в базис.

В

этом случае нужно

перейти

к определению вектора, под­

лежащего

исключению из

базиса.

Если лт+2. j„ ^ 0 , то

в

столбцах,

для которых Лт-нм — 0, отыскивается

 

 

 

 

 

-го-1-1 j, —

min

Х т -н ,

 

 

 

 

 

 

 

K+-2-ii <;K+4i+

 

 

 

 

и

определяется

знак

Если

Лщ+м, <^0, то

вектор

с

номером

у., — {К -J-1) подлежит вводу в базис.

Если же

-Xm+i.j,^0

или

*т+ 2.}0 > 0 ,

то уже

получен

оптимальный

опорный план расширенной

задачи

на некоторой

области

изменения параметра А. К детальному изучению этого слу­ чая мы вернемся позже.

Рассмотрим случай, когда признак оптимальности пока не обеспечен, т. е. когда определен номер вводимого в ба­ зис вектора. Выделяются положительные элементы в пер­ вых т строках выбранного столбца (столбца у0 или j\). Если в этом столбце нет ни одного положительного эле­ мента, то вычисления прекращаем, так как в этом случае ЛР= 0 .

Предположим, что в выбранном столбце имеется по крайней мере один положительный элемент. Выбор строки производится точно так, как в методе последовательного улучшения плана (с дополнительным требованием, что в случае вырожденности хотя бы для первых (/(+ 1 ) столбцов обязательно нужно применить способ устранения возмож­ ных зацикливаний, основанный на принципе е— прираще­ ния). После определения единственной строки реализуется преобразование симплексной таблицы по обычным форму­ лам метода последовательного улучшения плана и снова

258

рассматриваются элементы {т-\-2)-ой и (/и -Ц )‘ ой строк основной части таблицы.

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

пустимости

осуществляется следующая последовательность

действий.

 

 

 

 

 

1.

Принимается

^К = лг!-К.и .

 

 

2.

Выбираются

строки,

для

которых

( / = 1 ,

2,..., К —1)

и XiK Ф 0 (^> 0).

Здесь

возможны два

случая:

а)

есть

хотя бы

одна такая строка;

 

б) нет строки с этим свойством.

Вслучае б) в качестве значения параметра /.* выби­

рается произвольное число (например,

можно брать >.°к = 0)

и совершается переход к выполнению

пункта 4. В случае

а) — переход к пункту 3.

3.Из условий ?ikS*0 определяется:

где

max берется по всем г, для которых .* ^ = 0 ( /= 1 ,

2,...,

£ - 1 ) .

4.Вычисляется ft, k--i по формуле

 

Pi, k—1=

Pik-h-^ik

/ = 1 , 2,..., т .

5.

Анализ

значения к. Если А=р1, то k уменьшает

на единицу {к —1-»£) и совершается переход к выполне­

нию пункта 2. Если

же £ — 1,

то уже определена точка

Л°=з(л°1,

).°к),

в которой данная основа является оп­

тимальным опорным

планом задачи (14.1')—(14.3'). Значе­

ния базисных компонент опорного плана в точке Л° опре­

деляются

равенством

 

 

 

x i0 (Л°) = ft0, i =

1, 2..... т.

Ясно, что на неограниченном параллелепипеде базисность данной основы не нарушается. Если в оптималь­ ном базисе нет ни одного искусственного вектора, то в ука­ занной области уже имеется функция / ’ (Л). Может ока-

259

заться, что некоторые искусственные векторы входят в оп­ тимальный базис, но значения соответствующих базисных неизвестных В точке А0 равны нулю. В этом случае можно в точке Л'' продолжать процедуру преобразования таблицы так, чтобы избавиться от искусственных векторов. Если в точке Л9 хотя бы одна искусственная переменная входит в оптимальный опорный план с положительным значением, то выбирается такое направление, по которому имеется возможность достичь области допустимости задачи (14.1)— (14.3).

С целью выбора вектора направления, приводящего к более быстрому нахождению допустимой точки, рассмат­ ривается коэффициент при А\ в выражении целевой функ­ ции. Этот коэффициент представляет собой функцию

к ( Л ) =

.£m+2, к '-к -f-^m-t-2, К-Н t

(1 ^ -5 )

 

к-:

 

которая в точке Л = Л принимает строго

положительное

значение.

 

 

Отсюда ясно, что для достижения цели необходимо по­ пасть на гиперплоскость а (Л )= 0 .

В качестве направления выбирается вектор S с компо­ нентами sk = — -*m+2.k, и на луче Л +IJ.5 (^5*0) решается однопараметрическая задача с численным параметром |i. Для решения однопараметрической задачи к имеющейся симплексной таблице добавляются два дополнительных столбца (столбцы 2 и я + К + З ). В столбце (лг.-{-Х—f-2) заполняются значения базисных неизвестных и целевой

функции (коэффициенты при ц в точке Л — Л°). В столбце

к

(л-)—/С—f-З) заполняются величины V x iksk (/= 1 ,2 ,..., т-\-2).

Теперь на полуоси 0 ^ [ К ^ о о алгоритмом С. Гасса (см. (20])

решается

однопараметрическая

задача.

Через

конечное число шагов либо получится отрезок

[(j-t, nt+i]

изменения параметра

у., на которой оптимален

базис, состоящий из векторов условий задачи (14.1)—(14.3),

либо

луч (|it,

+ ° ° )*

на котором оптимальный базис содер­

жит

хотя

бы

один

искусственный вектор, либо же луч

(|j.t, -f-oo),

на котором рассматриваемая задача неразрешима.

260

В первом случае в точке -‘W A 0 + ut5 уже имеется решение исходной задачи. Во втором и в третьем случаях, используя выражение (14.5), выбирается новое направление и реша­ ется однопараметрическая задача, так как на указанном луче исходная задача заведомо неразрешима.

Указанным способом каждый раз в текущей точке К- мерного пространства выбирается подходящее направление

и вдоль этого направления

через конечное число перехо­

дов либо обнаруживаем, что

множество N пусто, либо опре­

деляем точку допустимости

исходной задачи (14.1)— (14.3).

Множество N пусто при следующих случаях:

а) текущая точка Л £ R K является точкой допустимости,

но ф ункция/[А (Л )| не

ограничена сверху на множест­

ве Ж д!

 

 

б) в текущей точке

нет ни одного направления S, по

которому линейная функция (14.5) уменьшается, и при ре­

шении соответствующей однопараметрической задачи

мож­

но получить положительное допустимое значение ji.

 

Случай б) означает, что система ограничений

(14.2),

(14.3) и

 

■ Й « 0

(Н .6)

несовместна.

 

Следует отметить, что вышеприведенный прием выбора

направления не является единственным. Можно предло­ жить целый ряд приемов выбора направления» позволяющих попасть в полупространство (14.6), содержащее множество допустимых точек (если такие вообще существуют).

Недостатком выбора направления внутренней нормали

к граничной

гиперплоскости

полупространства а (Л) в ка­

честве направления является то, что по

этому направле­

нию максимально возможное

значение

численного пара­

метра |а может быть равным нулю.

В этом случае н еобхо­

димо другое

направление S,

для

которого выполняется

условие

 

 

 

 

 

л - 5 > 0 ,

 

 

(14.7)

где п — внутренняя нормаль к граничной гиперплоскости полупространства (14.6). А таких направлений бесконечное количество. Конечно, конус таких направлений можно по261

Смотрите также файлы