Промежуточные вычислении 3 страница

Со временем эти спекулятивные сделки вышли из-под контроля, что приве­ло всех брокеров к банкротству. К тому же, финансовое положение брокер­ской фирмы было таково, что все деньги брокеров были вложены во внеш­них клиентов и сделки между самими брокерами, причем таким образом, что практически каждый брокер стал должником другого.

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

Из-за финансовых затруднений неплатежеспособной группы брокеров су­дебные инстанции постановили, что заключенные ранее сделки должны выполняться только для удовлетворения определенных судом требова­ний, поскольку брокеры не имеют собственных источников капитала. В частности, судебные инстанции требуют свести количество погашаемых сделок между брокерами к минимуму. Это означает, что если брокер А должен брокеру В сумму X, а брокер В — брокеру А сумму Y, то эти вза­имные долги сведутся к одному с суммой долга |Х - Y|. Эта сумма считает­ся долгом А перед В, если X > Y, и долгом В перед А, когда X < Y. Если X = У, долг погашен. Эта идея погашения взаимных долгов распространяет­ся на все долги между брокерами.

Каковы ваши предложения по выходу из данной финансовой ситуации? В частности, ответьте на следующие вопросы.

1. Как рассчитать доли возвращаемых долгов?

2. К какому минимальному количеству можно свести взаимные долги ме­жду брокерами?

Задача основана на материалах статьи Taha Н. "Operations Research Analysis of a Stock Market Problem", Computers and Operations Research, Vol. 18, No. 7, pp.597-602, 1991.

ГЛАВА 7

ТЕОРИЯ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Эта глава представляет строгий математический фундамент теории линейного программирования (ЛП). Здесь будет обоснован симплекс-метод и теория двойст­венности. Кроме того, будут рассмотрены такие эффективные вычислительные ал­горитмы, как модифицированный симплекс-метод, метод декомпозиции, метод решения задач, содержащих ограничения на значения переменных, и методы па­раметрического программирования. В заключение будет представлен алгоритм Кармаркара, полностью отличный от симплекс-метода. Этот алгоритм наиболее эффективен при решении очень больших задач ЛП.

В этой главе используется аппарат матричной алгебры. Читатель, не знакомый с матричной алгеброй, может обратиться к приложению А.

В задачах линейного программирования пространство допустимых решений всегда имеет форму выпуклого множества. Множество называется выпуклым, если отрезок прямой, соединяющий две различные точки этого множества, полностью принадлежит данному множеству. Крайней точкой выпуклого множества является точка, принадлежащая этому множеству, но которая не лежит ни на каком отрезке прямой, соединяющей две различные точки этого множества. Фактически крайние точки — это то же самое, что и угловые точки, которые использовались в главах 2, 3 и 4.

На рис. 7.1 показаны два множества. Множество а, которое представляет ти­пичное пространство решений задачи ЛП, является выпуклым множеством, тогда как множество б невыпуклое.

7.1. ОСНОВЫ СИМПЛЕКС-МЕТОДА

а

б

Рис. 7.1. Примеры выпуклого и невыпуклого множеств

Глава 7. Теория линейного программирования

В разделе 2.3 мы графически показали, что оптимальное (конечное) решение двухмерной задачи ЛП соответствует крайней (угловой) точке пространства допус­тимых решений. Этот результат основан на том факте, что в задачах ЛП любая до­пустимая точка представима как функция крайних точек пространства решений. Например, в выпуклом множестве на рис. 7.1, а имеется шесть крайних точек X,, Х₂, Х₆, произвольную допустимую точку X можно представить как линейную комбинацию крайних точек:

X - оцХ, + сс₂Х₂ + ОзХ₃ + сс₄Х₄ + сс₅Х₅ + сс₆Х₆,

где все коэффициенты ос, > 0 и выполняется равенство

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

Пример 7.1.1

Покажем, что следующее множество является выпуклым.

С = {(х„ х,) | х, < 2, х₂< 3, х, > 0, х₂ >0}. Пусть X, ={х,',л₂} и X, = {х²,х²} — две различные точки из множества С. Если мно­жество С выпукло, тогда точка X = (х,, х₂) = otjX, + о^Х, должна принадлежать это­му множеству. Чтобы точка X принадлежала множеству С, ее координаты должны удовлетворять неравенствам, которые определяют это множество.

х, = а.х,¹ + а,х,² < а, х 2 + а, х 2 = 2.

х, = a_sx\ + а₂х\ < а, хЗ + а, х3 = 3.

Таким образом (поскольку а, + а₂ = 1), x_i < 2 и х₂ < 3. Так как коэффициенты а, и otj неотрицательны, то координаты также удовлетворяют условиям неотрицательности.

УПРАЖНЕНИЯ 7.1.1

1. Покажите, что множество Q = {x_t, х₂1 х, + х₂ < 1, х, > 0, х₂ > 0} выпуклое. Су­щественно ли в данном случае условие неотрицательности переменных?

2. Покажите, что множество Q = {х,, х₂| х> 1 или х₂ > 2} не является выпуклым.

3. Найдите графически крайние точки выпуклого множества

Q = {х,, х₂1 х, + х₂ < 2, х, > 0, х₂ > 0}.

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

4. Представьте внутреннюю точку (3, 1) пространства решений, показанного на рис. 7.2, как выпуклую комбинацию крайних точек А, В, С и D, где каждая крайняя точка должна иметь строго положительный весовой коэффициент.

7.1. Основы симплекс-метода

^х2

5 4 3 2 1

О 1 2 3 4 5 6 Рис. 7.2. Пространство решений для упражнения 4

7.1.1. Базисные решения

В этом разделе задачу ЛП, записанную в стандартной форме (см. раздел 3.1), пред­ставим в новой форме записи с использованием матричных обозначений. Обозначим

через X = (Xj, х₂.....х_п)^т n-мерный вектор переменных, через А — матрицу размер

тхп, содержащую коэффициенты левых частей ограничений, b = (ft,, b₂, b_m)^T — m-мерный вектор правых частей ограничений, С = (c_v с₂, с_п) — л-мерный вектор коэффициентов целевой функции. С помощью матричной формы записи стандарт­ную задачу ЛП можно представить следующим образом.

Максимизировать или минимизировать г = СХ

при ограничениях

АХ = Ь, Х>0.

На основе стандартной формы для симплекс-таблиц из главы 3 (см. также рис. 4.1) т крайних справа столбцов матрицы А всегда можно представить в виде единичной матрицы I, для чего, возможно, придется надлежащим образом расположить пере­менные и использовать при необходимости искусственные переменные.

Базисное решение системы уравнений АХ = b получается путем присвоения п -т переменным нулевых значений и последующим решением системы из т уравне­ний относительно оставшихся т переменных (предполагается, что эта система име­ет единственное решение). Теория линейного программирования устанавливает следующее соответствие между геометрическим определением крайних точек и ал­гебраическим определением базисного решения.

Крайние точки множества {X | АХ = Ь} <=> Базисные решения системы АХ = Ь. Это соответствие означает, что все крайние точки области решений задачи ЛП полностью определяются базисными решениями системы АХ = b и наоборот. От­сюда следует, что множество базисных решений содержит всю информацию, необ­ходимую для оптимального решения задачи ЛП. Более того, если наложить усло­вия неотрицательности X > 0, поиск оптимального решения ограничится только множеством допустимых базисных решений.

Глава 7. Теория линейного программирования

Чтобы формализовать определение базисного решения, представим систему АХ = b в векторной форме

где вектор Р_; — j-й столбец матрицы А. Подмножество из т векторов Р_у формирует базис В тогда и только тогда, когда эти векторы линейно независимы. Для этого необходимо (и достаточно), чтобы определитель матрицы В, состоящей из данных т векторов, был отличен от нуля, т.е. det(B) Ф О.¹ В этом случае матрица В называ­ется невырожденной. Обозначим через Х_в вектор из т переменных, ассоциирован­ных с векторами Р_;, составляющих невырожденную матрицу В. Тогда Х_в будет ба­зисным решением, если он будет решением системы ВХ_В = Ь.

Пусть В"¹ — матрица, обратная к матрице В (напомним, что матрица В невыро­жденная). Тогда базисное решение находим по формуле:

х_в = в'ь.

Если выполняется неравенство B"'b > 0, тогда Х_в будет допустимым решением.

В заключение отметим, что количество базисных решений у системы из т урав­нений с п неизвестными не превышает величины

т\(п — т)\

Пример 7.1.2

Найдем и классифицируем (как допустимые или недопустимые) все базисные ре­шения следующей системы уравнений

В следующей таблице показаны все базисные решения. Матрица, обратная к мат­рице В, вычислена методами, приведенными в разделе А.2.7.

В

BX_s = b

Решение

Статус

(Pi. Рз) (Рг, Рз)

Не является базисом

Л	3>		(Л
1 \*	г)	ы
(■ Л			г
1 1
4 8		=
1 3
ч~4 %)				*)

Допустимое

Недопустимое

Здесь и далее автор обозначает через В как базис, т.е. совокупность базисных векторов, так и матрицу, составленную из этих векторов. Это не приводит к недоразумениям, так как из контекста всегда понятно, о чем идет речь. — Прим. ред.

7.1. Основы симплекс-метода

Рассмотрим эту же задачу, представив систему в векторной форме:

Здесь векторы Р,, Р₂, Р₃, b являются двухмерными; в общем виде они представимы как (о,, а₂)^т. На рис. 7.3 на плоскости (a_lt а₂) показаны векторы данной системы. Например, вектор b = (4, 2)^т, где а, = 4, а₂ = 2.

Рис. 7.3. Векторное представление системы уравнений

Поскольку у нас только два уравнения (т = 2), базис должен состоять из двух век­торов, выбранных среди Р,, Р₂ и Р₃. Из рис. 7.3 видно, что пары векторов (Р,, Р₂) и(Р₂Р₃) могут быть базисами, поскольку векторы в этих парах независимы. Но пара векторов (Pj, Р₃) не может составить базис, так как эти векторы линейно зависимы.

Алгебраический подход к определению базиса требует, чтобы определитель матри­цы, составленной из векторов, претендующих на роль базисных, был отличен от нуля. Вычисления определителей показывают, что пары векторов (Р_р Р₂) и (Р₂ Р₃) будут базисами, а векторы (Р_1; Р₃) не могут составить базис.

det(P,, Р,) = det Q ^ j = (1 х (-2)) - (2 х 3) = -8 * 0. det(P₂,P₃) = detj ^Ъ ~J = (^3x(^_2W~ (^_2х(^_1)) ^{= _8} mo-

deler,, Р₃) = det

fl -Г 2 -2 = (1х(-2))-(2х(-1)) = 0.

Глава 7. Теория линейного программирования

УПРАЖНЕНИЯ 7.1.2

1. Представленные ниже системы уравнений а) и б) имеют единственные ба­зисные решения, система в) — бесконечно много решений, а г) не имеет решения. Докажите это, представив решения графически на плоскости. На основании данных примеров выведите общие закономерности, определяю­щие у системы уравнений единственное решение, бесконечно много реше­ний или отсутствие решений.

а) в) х₁+3х₂ = 2, Зх₁+х₂ = 3. 2л;, + &х₂ = 4, лг, + Зл:₂ = 2.

б) г) 2*, + Зх₂ = 1, 2л:,-л:_г = 2. 2л;, - 4л:₂ = 2, -лг,-1-2л:₂ = 1.

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

а) в) Д) 1 -з)Ц (l,

-1

б)

г) е) 2 1

2 1

<\ О -2

Я:

3. Дана следующая система уравнений.

'Г				V
						.0,		,2,

Определите, какой из следующих наборов векторов образует базис.

a) (Р„ Р₂, Р₃)

b) (Р„ Р₂, Р₄)

c) (Р₂,Р„Р₄)

d) (Р„ Р₂, Р₃, Р₄)

4. Истинны или ложны следующие утверждения?

a) Если матрица В не вырождена, то система ВХ = b имеет единственное решение.

b) Система ВХ = b не имеет решения, если матрица В вырождена и вектор b независим относительно векторов, составляющих матрицу В.

c) Система ВХ = b имеет бесконечно много решений, если матрица В вырож­дена и вектор b зависим относительно векторов, составляющих матрицу В.

7.1. Основы симплекс-метода

7.1.2. Матричное представление симплекс-таблиц

В этом разделе мы используем матричную алгебру для построения симплекс-таблиц. Рассмотрим стандартную задачу ЛП

максимизировать г = СХ при ограничениях АХ = b, X > 0.

Эту задачу ЛП можно также записать следующим образом.

-С

Для любой симплексной итерации будем обозначать через Х_в базисный вектор переменных, а через С_в — вектор коэффициентов целевой функции, соответст­вующих этому базису. Поскольку все небазисные переменные равны нулю, стан­дартная задача ЛП будет сведена к задаче с целевой функцией г = С_ВХ_В и ограниче­ниями ВХ_В = Ь, где текущее решение удовлетворяет следующему уравнению.

-с,

В

ся в-]		с, в-V
В";		, в-ь,

Здесь при обращении матрицы использовались формулы из раздела А.2.7.

Симплекс-таблица получается из исходной задачи ЛП путем вычислений по следующей формуле.

С, В

в­-С А

'\ сввр	(°1
,0 в 1,	W

Выполнив вычисления по этой формуле, получаем такую симплекс-таблицу.

Базис	X;	Решение
z	С8В"1Р;-С,	CsB"1b

х₈

В"¹ Р,

в^ь

В этой таблице необходимо вычислить только обратную матрицу В^-1, так как другие элементы таблицы получаются из исходных данных задачи.

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

Пример 7.1.3

Рассмотрим следующую задачу ЛП.

Максимизировать г = дс, + 4х₂ + 7х₃ + 5х₄

при ограничениях

2*! + х_г + 2х₃ + 4.х₄ = 10, Здс₁ - х₂ - 2х₃ + 6x_t = 5, х„ х₂, х₃, x_t>0. Пусть В = (Р,, Р₂) является допустимым базисом.

Глава 7. Теория линейного программирования

На основании В = (Р,,Р₂) имеем Х_в = (х,, х₂)^т и С_в = (1,4). Вычисляем обратную матрицу В"¹:

В

Находим текущее базисное решение

2 1

3 -1

	Л	Л
	\5	ъ)

х.=Г I = в ь =

5 5 3 _2 V5 5J

Далее вычисляем в симплекс-таблице значения коэффициентов ограничений:

(±0(2 1 2 Л) (1 0 0 2 В"'(Р„Р,.Р,,Р₄)= ■< ⁵

¹ " ^{3 4} 1 -МЗ -1 -2 6 [0 1 2 0

Теперь находим коэффициенты z-строки симплекс-таблицы:

С_в[В-^,(Р₁.Р₂,Рз,Р₄)]-С = (1,4)^ ° ° ^-(1,4,7,5) = (0.0.1.-3). Наконец, вычисляем значение целевой функции:

z = C_aB-^,b = C_BX_e=(l,4)

= 19,

Таким образом, получаем значения следующей симплекс-таблицы.

Базис	Х1	хг	хз	Хл	Решение
z				-3
хз
хг

Еще раз подчеркнем, что в этой таблице основные вычисления связаны с нахожде­нием обратной матрицы В^-1, другие элементы таблицы получаются на основе вы­численной матрицы В"¹ и исходных данных задачи.

УПРАЖНЕНИЯ 7.1.3

1. Пусть в примере 7.1.3 В = (Р₃, Р₄). Покажите, что соответствующее базисное ре­шение является допустимым и постройте соответствующую симплекс-таблицу.

2. Дана следующая задача ЛП.

Максимизировать г = 5х, + 12х₂ + 4х₃

при ограничениях

х, + 2х₂ + х₃ + х₄ = 10,

^3* ^4 ~

Определите, какие из следующих наборов векторов образуют базис: (Р,, Р₂),

(р₂, р₃), (р₃, р₄).

7.2. Модифицированный симплекс-метод

3. Дана следующая задача ЛП.

Минимизировать г = 2х_х + х₂

при ограничениях

Зяг, -(- х₂ — х₃~ 3, 4л:, + Зх₂ - х₄ = 6, + 2jc₂ + х_ь = 3, Хр х₂, яг₃, х₄, я:₅ > 0.

Вычислите симплекс-таблицу, соответствующую Х_в = (x_v х₂, х_ь)^Г, и опреде­лите, будет ли это решение допустимым и оптимальным.

4. Дана следующая симплекс-таблица с оптимальным решением задачи ЛП.

Базис	Х1	хг	х3	Xt	х5	Решение
z						?
х3					-1
х2
Х1				-1

Здесь переменные х_а, x_t и х_ь являются дополнительными (остаточными). С помощью матричных вычислений реконструируйте исходную задачу ЛП, затем вычислите оптимальное значение целевой функции.

5. В стандартной задаче ЛП разобьем вектор X на два — X = (X,, Х„)^т. Здесь вектор Х„ соответствует начальному базисному решению, состоящему из до­полнительных и искусственных переменных (так что В = I). Тогда матрицу А можно представить как А = (D, I). Вектор С также разделим на два вектора С, и С„ в соответствии с векторами X, и Х„. Покажите, что в этом случае сим­плекс-таблицу можно записать в следующем виде, который в точности соот­ветствует виду симплекс-таблицы из главы 3.

Базис	X,	Xi,	Решение
z	CSB"1D-C|	СвВ 1 - Сц	с8вчь
х8	B"1D	В'1	в-'ь

7.2. МОДИФИЦИРОВАННЫЙ СИМПЛЕКС-МЕТОД

В разделе 7.1.1 показано, что оптимальное решение задачи линейного програм­мирования всегда находится среди множества базисных (допустимых) решений. Выполнение симплекс-метода начинается с допустимого базисного решения В, за­тем осуществляется переход к следующему допустимому базисному решению, ко­торое улучшает (по крайней мере, не ухудшает) значение целевой функции, и так до тех пор, пока не будет достигнуто оптимальное решение.

Модифицированный симплекс-метод предусматривает выполнение точно та­ких же этапов, как и обычный табличный симплекс-метод, описанный в главе 3. Основное отличие между ними заключается в том, что в обычном симплекс-методе при переходе от одного базиса к другому используется процедура преобра­зования строк симплекс-таблицы с помощью метода Гаусса-Жордана, тогда как

Глава 7. Теория линейного программирования

в модифицированном симплекс-методе эти преобразования осуществляются пу­тем вычисления обратной матрицы В^-1, и основные действия связаны именно с вычислением этой матрицы.

7.2.1. Условия оптимальности и допустимости

Рассмотрим стандартную задачу ЛП.

я

Максимизировать или минимизировать г = СХ при ограничениях ^PjX, =b, х.>

0,j= 1, 2, га.

Для данного базисного вектора Х_в и соответствующих базиса В и вектора коэф­фициентов целевой функции С_в на каждой итерации вычисления значений сим­плекс-таблицы выполняются по следующим формулам (см. раздел 7.1.2).

_г + £ц-с_у)*;=с_в в-'ь

(X_B)_i+X(B-'P_J),x_;=(B-¹b)_l,

j=l

где Zj - с\ = С_ВВ^_1Р_; - с\. Здесь запись (V), используется для обозначения t-ro элемента вектора V.

Условие оптимальности симплекс-метода. Из уравнения для значений z-строки, приведенного выше, следует, что увеличение значения небазисной пере­менной x_f приводит к возрастанию (убыванию) значения целевой функции z выше текущего значения С_ВВ^_1Ь только в том случае, если разность z_j - с\ строго отрица­тельна в задаче максимизации или строго положительна в задаче минимизации. В противном случае переменная не может улучшить текущее решение и должна остаться небазисной с нулевым значением. Таким образом, любая небазисная пе­ременная, удовлетворяющая этому условию, может быть включена в базис, что, возможно, улучшит значение целевой функции. В симплекс-методе действует эм­пирическое правило, которое гласит, что в качестве вводимой в базис переменной выбирается переменная, которой соответствует наибольший (по модулю) отрица­тельный коэффициент г — с\ в z-строке в задаче максимизации или наибольший по­ложительный аналогичный коэффициент в задаче минимизации.

Условие допустимости симплекс-метода. Определение исключаемого из базиса вектора основано на проверке ограничения, представленного в виде равенства, со­ответствующего i-й базисной переменной. Это равенство имеет следующий вид.

(ХД.+^В-'РДх^В-'Ь),.

Обозначим через P_k вводимый вектор, определенный из условия оптимальности, а через х_к — вводимую в базис переменную, принимающую положительное значе­ние. Поскольку все остальные небазисные переменные сохраняют нулевые значе­ния, равенство ограничения, соответствующее базисной переменной (Х_в),, можно записать следующим образом.

(Х_в), = (В-¹Ь)₁-(В-¹РДх, Это уравнение показывает, что при (В~'РД > 0 возрастание переменной х_к не приведет к отрицательному значению базисной переменной (Х_в)₍ только в том слу­чае, если будет выполняться неравенство

(B"'b), - (В^_1РД х_к > 0 для всех L

7.2. Модифицированный симплекс-метод

Таким образом, максимальное значение вводимой переменной x_k можно вычис­лить по следующей формуле.

Базисная переменная, на которой достигается этот минимум, становится ис­ключаемой.

УПРАЖНЕНИЯ 7.2.1

1. Дана следующая задача ЛП.

Векторы Р,, Р₂, Р₃ и Р₄ показаны на рис. 7.4. Предположим, что текущим ба­зисом является В = (Р_р Р₂).

a) Если вектор Р₃ ввести в базис, какой вектор необходимо из него исклю­чить, чтобы полученное базисное решение было допустимым?

b) Может ли вектор Р₄ быть частью допустимого базиса?

2. Докажите, что для всех базисных переменных соответствующие разности г_у - с_у равны нулю.

3. Докажите, что если в задаче максимизации (минимизации) для всех неба­зисных переменных х_; выполняется неравенство г. - с. > О (< 0), то задача имеет единственное оптимальное решение. Если же для некоторых небазис­ных переменных х. выполняется равенство г.-с_у = 0, задача имеет альтерна­тивное оптимальное решение.

4. Пусть начальное базисное решение задачи ЛП сформировано только из до­полнительных остаточных переменных. С помощью матричного представле­ния симплекс-таблицы покажите, что применение процедуры, описанной в разделе 3.3, где уравнение для целевой функции записано как

Максимизировать г — с,*, + с₂х₂ + с₃х₃ + с₄х₄

при ограничениях

Р_Л+Р_Л + Р_Л + Р_Л-Ь х„ х₂, х₃, х₄>0.

Рис. 7.4. Векторы для упражнения 1

Глава 7. Теория линейного программирования

автоматически приведет к вычислению разностей г. - с. для всех переменных в начальной симплекс-таблице.

5. Пусть начальное базисное решение задачи ЛП сформировано только из ис­кусственных переменных. Используя матричное представление симплекс-таблицы, покажите, что применение процедуры исключения искусствен­ных переменных из целевой функции (для чего использовались ограниче­ния-равенства), описанной в разделе 3.4.1, приведет к вычислению разно­стей z_t - Cj для всех переменных в начальной симплекс-таблице.

6. Пусть дана задача ЛП, в которой не накладываются ограничения на знак пе­ременной х_к. Докажите, что после замены х_к=х_к - х_к, где х\ и х~_к неотрица­тельны, невозможна ситуация, когда переменные х\ и х_к заменяют одна другую в альтернативных оптимальных решениях.

7. Дана задача ЛП, записанная в стандартной форме и имеющая т ограничений (в виде равенств) и п неизвестных. Определите число смежных крайних то­чек, которые можно достичь из невырожденной крайней точки пространства решений. Почему здесь существенно условие невырожденности крайней точки?

8. Применяя условие допустимости симплекс-метода, предположим, что х_г — базисная переменная, имеющая нулевое значение, а дс.— вводимая. Объяс­ните, почему для того, чтобы переменную л:_г исключить из базиса, необходи­мо выполнение неравенства (В^_1Р_;)_г>0. Какие возникнут проблемы при вы­полнении неравенства (В^-1РД.<0? (Подсказка. При ответе учитывайте, что переменная х_г должна остаться неотрицательной.)