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

множеств следует из конечности количества всевозможных основ (следовательно и базисов) задачи (11.1)—(11.3).

Простыми примерами можно показать, что в случае

этом множестве она порождается хотя бы двумя базисами (базисами, порождающими F{ А, М) на ЛД, и на ЛД,).

3°. Постановка задачи параметрического линей­ ного программирования с линейно зависящим о т па­ р а м е тр а вектором условий. На практике часто могут встретиться задачи ПЛП, в которых один из векторов условий линейно зависит от векторного параметра. Не на­ рушая общности, можем предположить, что от параметра зависит первый вектор условий. Задача формулируется

232

Функции а,, (Л) предполагаются линейными, т. е.

К

Множество

О= |А£Дк|С_ ^ 0 |

называем множеством допустимости задачи (11.11)—(11,13). Ясно, что область определения функции F (A )

N = |A£D \тах f\ X (А)] < ool

является подмножеством множества D , т. е. N ( D .

Для решения поставленной задачи в первую очередь необходимо изучить свойства множеств D и N.

Множество D может быть пустым или же состоять из единственной точки. Здесь пока будем рассматривать слу­

дующих возможных (одновременно взаимно-дополняющих) случаев:

а) лгДА'). х, (Л") = 0 , б) JTj (Л'). х ,( А " )^ 0 .

л "](А ')= 0 . Нетрудно убедиться, что вектор X (А ) = Х (А ') будет планом задачи (11.11)—(11.13) в любой точке отрез­ ка, соединяющего точки А' и А". Более того, этот вектор

233

где величина ^ определяется формулой

(11.16)

оХ\(Л")

Очевидно, величина ja удовлетворяет условиям:

О ^ |х 1; {г/»_о = 0; ti/e=i =■ 1 -

Непосредственной подстановкой можно убедиться, что вектор X (Л) является планом задачи (11.11)—(11.13) в соответствующей точке Л. Значит, множеству D выпукло.

Подставляя выражение (11.15) вектора X (А ) в целевую

/[X (A )l= «f(A ') K I - . ] F ( ? ) .

Но вектор -А"(Л), вообще говоря, может быть и не­ оптимальным планом задачи в точке Л. Отсюда и вытекает неравенство, определяющее вогнутость функции.

При разработке алгоритма решения задачи (11.11)— (11.13) будем пользоваться результатами следующего утверждения.

Утверждение 6. Пусть:

тор A'(A°)^G-o является планом задачи на всем пространст­ ве изменения Л.

234

Пт f \ X l { \ ') } = -| -оо и / i " i / [ A ' ( A " ) ] = + oo .

Пользуясь формулой (11.15), в промежуточной точке (11.14) можно построить соответствующую последователь­ ность векторов Х ' { А )£ G i. Учитывая равенство (11.17) и свойства величины |i, получаем:

И Г Л f \ X ‘ ( Л ) | жав -|- ОО.

А это означает справедливость утверждения.

Вместе с задачей (11.11)—(11.13) рассматриваем сле­ дующую задачу, которую условно назовем урезанной за­

Как видно, задача (11.11')—(11.13') отличается от за­ дачи (11.11)—(11.13) только тем, что здесь не участвует

1 D \ N — означает дополнение подмножества N до D, т. е. iVUD\<V= D.

235

Если Х ' — (хг, хи) — план задачи (11.1 Г )—(11.13'), то X — (0, л:,,..., х п) — план задачи (11Л 1)—(11.13). Отсюда ясно, что для построения функции F (А) на множестве ее определения можно использовать задачу (I I .И ')—(11.13').

§ 2. Краткое описание алгоритма решения обшей задачи

Добавлением переменных отклонения, систему ограни­ чений (11.2) приведем к каноническому виду и обеспечим неотрицательность правых частей этих ограничений при достаточно больших значениях параметров При этом, если для больших значений ).к все функции остаются неот­ рицательными, то векторы, соответствующие переменным отклонения, уже образуют исходный допустимый базис для решения поставленной задачи методом последовательного улучшения плана. Если же при таких значениях парамет­ ров Хк хотя бы одна из функций ф| (А) отрицательна, то вос­ пользуемся расширенной задачей (/И—задачей), для реше­ ния которой также применяем метод последовательного улучшения плана2. Предполагая достаточно большими зна­ чения параметров ).к и рг, через конечное число шагов по­ лучим оптимальный план расширенной задачи или же об­ наружим неограниченность целевой функции на множестве планов задачи. Ясно, что во втором случае текущий план расширенной задачи будет планом и исходной задачи, так как, до появления признака неограниченности целевой функ­ ции, в текущей симплексной таблице векторы, соответст­ вующие искусственным переменным, заранее исключаются из базиса. В таких случаях можно сразу перейти к опре­ делению области изменения параметров p.j, на которой дан-1

1 Нетрудно заметить, что при сделанных предположениях относи­ тельно функций i]/j (Л) они сохраняют свой знак при достаточно боль­ ших значениях параметров >.к. Аналогичным свойством обладают функ­ ции

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

236

мый опорный план является оптимальным, т. е. определить область Л',, на которой функция F (\ , Ы) порождается од­ ним и тем же базисом. После этого осуществляется пере­

ществляем переход к такой соседней области, на которой в оптимальном базисе участвует меньшее количество ис­ кусственных векторов. Очевидно, этого можно добиваться фиксацией области изменения параметров ц, и изменением параметров /.* {т. е. переход реализуется только в под­ пространстве изменения параметров >.к). При переходе к соседним областям, выбором определенного направления, каждый раз .многопараметрическую задачу приводим к однопараметрической. Решая по выбранному направлению S однопараметрическую задачу, через конечное число ша­ гов метода последовательного уточнения оценок либо избавимся от искусственных векторов, либо обнаружим, что вдоль выбранного луча исходная задача неразрешима. В последнем случае выбирается другое направление, по которому можно исключить из базиса хотя бы один искусст­ венный вектор.

Приведение многопараметрической задачи к однопа­ раметрической оправдывается тем, что свойство выпуклости функции многих переменных эквивалентно свойству выпук­ лости такой функции одной переменной, которая получает­ ся от данной функции многих переменных фиксированием произвольной точки и произвольного направления, т. е. имеет место следующее утверждение (см. [34], § 2.4, тео­ рема 1):

функция ф(Л) выпукла тогда и только тогда, когда функция ф' (<х) = ф (A w-f- a S) выпукла для произвольных А 0 и S.

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

Может оказаться, что в процессе решения задачи (11.1)—(11.3) вне вышеуказанного параллелепипеда, на

237