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

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

10. Каковы соотношения между крайними точками пространства решений и ба­зисными решениями при вырожденности и невырожденности решений? Ка­кое максимальное число итераций симплекс-метода может быть выполнено в одной и той же крайней точке?

11. Дана следующая задача ЛП: максимизировать г = СХ при ограничениях АХ < b, X > 0, где b > 0. Предположим, что вводимый в базис вектор Р_у таков, что по крайней мере один элемент вектора В~'Р_у положителен.

a) Пусть вектор Р, заменен на аР_;, где а — положительное число, при этом переменная Xj остается переменной, вводимой в базис. Найдите соотноше­ния между значениями переменной x_jt соответствующими векторам Р_у и cdt*.

b) Ответьте на вопрос предыдущего пункта, если дополнительно вектор b за­менен на вектор рЧЬ, где (3 — положительное число.

12. Дана следующая задача ЛП: максимизировать z = СХ при ограничениях АХ<Ь, Х>0, где Ь>0. Предположим, что после получения оптимального решения возникла идея сделать небазисную переменную x_t базисной (т.е. приносящей доход, если вспомнить экономическую интерпретацию задач ЛП) путем уменьшения ресурсов, расходуемых на единицу x_/t до величины 1/а от исходного значения, где а— число, превышающее единицу. По­

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

скольку сокращено потребление ресурсов, ожидается, что доход на единицу Xj также уменьшится до величины 1/а от исходного значения. Может ли это изменение привести к рентабельности переменной x_t? Каковы ваши рекомен­дации относительно того, чтобы сделать переменную х. приносящей доход?²

13. Дана следующая задача ЛП: максимизировать г = СХ при ограничениях (A, I)X = b, X > 0. Обозначим через Х_в текущий базисный вектор, через С_в — вектор коэффициентов целевой функции, соответствующих базисным пере­менным. Допустим, что вектор С_в изменен на D_B. Докажите, что в этом слу­чае разности 2.-с_у, соответствующие базисному вектору Х_в, останутся рав­ными нулю. Дайте объяснение этому.

7.2.2. Вычислительная процедура модифицированного симплекс-метода

Имея условия оптимальности и допустимости, приведенные в разделе 7.2.1, можно описать последовательность вычислений, выполняемых в модифицирован­ном симплекс-методе.

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

Шаг 1. Каким-либо подходящим способом вычисляется обратная мат-рица В.

Шаг 2. Для каждой небазисной переменной х_/ вычисляется величина

z_rc_rC_BW^lV-c_r

Если для всех небазисных переменных x_j величины z_i - с_}>0 в задаче максимизации или г. - с. < 0 в задаче минимизации, то вы­числения заканчиваются, так как получено оптимальное решение

х_в = в-¹ь,г = с_вх_в.

Иначе на основе условия оптимальности определяется вводимая (в базис) переменная дс как небазисная переменная, которой соот­ветствует наибольшая (по модулю) отрицательная величина г. - с_/ в задаче максимизации или наибольшая положительная в задаче минимизации.

Этот вопрос можно переформулировать без "экономического" подтекста: при каких ус­ловиях переменная x_t может быть представлена в оптимальном решении? — Прим. ред.

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

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

Шаг 3. Вычисляется вектор В~'Р_у. Если все элементы этого вектора от­рицательны или равны нулю, вычисления заканчиваются, так как задача не имеет ограниченного решения. Иначе вычисляется вектор В 'b. Для всех строго положительных элементов вектора В^_1Р вычисляется отношение, определенное в условии допусти­мости. Базисная переменная x_t, которой соответствует наимень­шее отношение условия допустимости, становится исключаемой из базиса переменной.

Шаг 4. Из текущего базиса В формируется новый базис путем замены в базисе В вектора Р_; на вектор Р,. Выполняется переход к этапу 1 для начала новой итерации.

Пример 7.2.1

С помощью модифицированного симплекс-метода решим заново задачу о компании Reddy Mikks из раздела 2.1. Решение этой задачи обычным симплекс-методом дано в разделе 3.3.2. Сравнение двух решений данной задачи показывает, что оба метода выполняют одну и ту же последовательность действий.

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

максимизировать г = (5, 4, 0, 0, 0, 0)(л:₁, х_г, х₃, x_t, х₅, х₆)^Т

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

					V
' 6 4				(Г	*2		'24s
1 2					*3
-1 1					*4
, 0 1				к	*5
					Л)
	#2»		*4.	*5> *6^0.

Мы используем запись С = (с,, с₂, с₆) для представления вектора коэффициентов целевой функции и (Р,, Р₂, Р₆)— для представления столбцов коэффициентов левых частей ограничений. Вектор правых частей ограничений обозначим Ь.

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

Итерация О

Х„ - (*„ x_t, x_t, х/, С_Во = (0, 0, 0, 0). В₀ = (Р₃,Р₄,Р₅,Р_в) = 1, в-' -I.

Таким образом,

Х,_о = В-¹Ь = (24,6,1,2)^Г, _г=СД =0.

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

Вычисления условия оптимальности с_в|в-' = (0, 0, 0, 0).

Ц " *,Ui - ^С*Л' (Pi. Р.) - <*„ с_г) = (-5, -4). Отсюда следует, что вводимым в базис вектором будет Р,. Вычисления условия допустимости

^xe„ ⁼ (*з> *4. *6. ^e)^{r =} (²⁴> ⁶' *> ²)^Г-В-'Р, =(6, 1,-1, 0)^г.

Следовательно,

х, =1шп|^ру,—,—| =min{4, 6,—,—}=4, и вектор Р₃ определяется как исключаемый из базиса.

Результаты выполненных вычислений представим в виде знакомой симплекс-таблицы. Такое представление поможет сравнить модифицированный и обычный симплекс-методы.

Базис	Х1	хг х3	Хл	хь	х6	Решение
z	-5	-Л 0
Хз
Х4
Хь	-1
Хб

Итерация 1

^Х«, = (*,. *4> *S> *в) > ^СВ, = (⁵> °> ⁰> ⁰)-

(6 О О ОЛ

В.^.Р,, Р₅,Р_в) =

110 0 -10 10 ^0 0 0 1,

Используя подходящий метод вычисления обратной матрицы В~' (в разделе А.2.7

приведен метод вычисления обратных матриц на основе их мультипликативного представления), находим

' i о о 0^Л

о

-110 0 6

ioio

0 0 0 1

Отсюда получаем

В~' b = (4, 2, 5, 2)\ 2 = С_в Х_в = 20.

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

Вычисления условия оптимальности

с_нв:' = -,о,о,о

Ц " с)_ггя = С„В-¹ (Р₂₎ Р₃) - (с₂, с₃) = ^-|, |

Отсюда следует, что вводимым в базис будет вектор Р₂. Вычисления условия допустимости

^хч ⁼ (*i> ^х*> ^хь> ^x<f ⁼ (⁴> ²' ⁵> ²)^Г-

ВГ'Р₂=1т.т.г.1

2 4 5

з'з'з'

Следовательно,

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

Итерация 2

Х_в, = (*„ х_г, х₅, х/, С_в, = (5, 4, 0, 0).

В₂ = (Р„Р₂,Р₅,Р₆) =

(Ь 4 0 0\ 12 0 0 -1110 0 10 1

Находим

/ 1

в;¹ =

о о

i \ ^{0 0}

I ^{1 0}

i л о i

Отсюда получаем

х_в, = в₂-ь=|з,т,т.

Ill

2'2'2

z= С_ЯХ_Й. -21.

Вычисления условия оптимальности

ад'=(2.1, о, о].

i^zj - *,U«= С_8;В₂-' (Р₃, Р₄) - (с₃, с₄) = ^, 1 Отсюда следует, что решение Х_Л оптимально. Вычисления заканчиваются. Оптимальное решение:

х. = 3. л:„ = 1.5. 2 = 21.

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

УПРАЖНЕНИЯ 7.2.2

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

2. Решите модифицированным симплекс-методом следующие задачи ЛП.

a) Максимизировать z = 6л:, - 2х₂ + Зх₃ при ограничениях

2 л:, - х₂ + 2х₃ < 2, х₁ +4х₃ < 4,

b) Максимизировать г = 2л:, + л:₂ 4- 2л:₃ при ограничениях

4л:, + Зл:₂-1-8д:₃< 12, 4л:, + л:₂ +12л:₃<8, 4л:,-л:₂ + 3л:₃<8, л:,, л:₂, х₃>0.

c) Минимизировать z = 2jc, + л:₂ при ограничениях

Зл:, -Ь л:₂ ⁼ 3, 4л:, + Зл:₂ > 6, л:, + 2л:₂<3, л:,, лс₂>0.

d) Минимизировать z = 5лс, - 4л:₂ 4- 6л:₃ 4- 8л:₄ при ограничениях

л:, + 7л:₂ + Зл:₃ + 7л:₄ < 46, Зл:, - л:₂ + л:₃ + 2л:₄<20, 2x_l + 3x₂-x₃ + x_i>18,

^2' ^3* ^4 ~ ^*

3. Решите следующую задачу ЛП с помощью модифицированного симплекс-метода, используя в качестве начального базиса вектор = (л:₂, л:₄, л:₅)^г.

Минимизировать г = 7х₂ + 11л:₃ - 10л:₄ + 26л:₆ при ограничениях

х₂-х₃ + х, + х_в = 6,

л:₂ - д:₃ 4- д:₄ 4- Зл:₆ — 8,

л:, 4- л:₂ - Зл:₃ 4- л:₄ 4- л:₅ = 12,

Х\> ^3> ^Ч' ^5' ^"6 —

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

a) Задача из упражнения 2,с.

b) Задача из упражнения 2,d.

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

с) Задача из упражнения 3 (отказавшись от предложенного начального ре­шения Хд_о).

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

Шаг 0. Пусть В₀ = I — начальный базис, причем хотя бы один из элемен­тов вектора отрицателен (т.е. решение недопустимо).

Шаг 1. Вычисляем текущие значения базисных переменных: Х_в = B"'b. Вы­бираем в качестве исключаемой из базиса переменную, имеющую наибольшее отрицательное значение (обозначим исключаемую пе­ременную х_г). Если все элементы в Х_в неотрицательны, то вычисле­ния заканчиваются, так как достигнуто допустимое решение.

Шаг 2.

a) Для всех небазисных переменных х_у вычисляем разности z_j-c_j = С_ВВ^_1Р. - е..

b) Для всех небазисных переменных х_у вычисляем коэффициенты ограниче­ний (В"'Р)_г, ассоциированные со строкой, соответствующей исключаемой переменной х_г.

c) Определяем вводимую в базис переменную как переменную, на которой достигается следующий минимум.

, (В-'рд<о|.

Если все (В'РД > 0, допустимого решения не существует.

Шаг 3. Формируем новый базис путем замены в базисе вектора Р. на Р_г. Вычисляем новую обратную матрицу В"¹ и переходим к шагу 1.

Примените описанный метод для решения следующей задачи.

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

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

Зх, + х₂ > 3, 4х, + Зх₂ > 6, х, + 2х₂ < 3, х,, х₂> 0.

7.3. АЛГОРИТМ РЕШЕНИЯ ЗАДАЧ С ОГРАНИЧЕННЫМИ ПЕРЕМЕННЫМИ

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

= min

j

(В-РД

7.3. Алгоритм решения задач с ограниченными переменными

Специальный алгоритм решения задач с ограниченными переменными, кото­рый мы рассмотрим в этом разделе, особенно эффективен, поскольку он учитывает тот факт, что ограничения заданы в явном виде. Сначала рассмотрим более простой случай, когда заданы только нижние границы на значения переменных. При яв­ных ограничениях X > L замена (подстановка) типа

X = L + X', Х'>0

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

Теперь рассмотрим ситуацию с верхними границами X<U. В данном случае прямая замена X = U - X", X" > 0 невозможна, поскольку обратная подстановка не гарантирует неотрицательности X. Здесь необходимо применение других процедур.

Запишем задачу ЛП с верхними границами на значения переменных как

максимизировать г = {СХ | (A, I)X = Ь, 0 < X < U}.

При выполнении алгоритма решения задач с ограниченными переменными явно используются только ограничения (A, I)X = b, X > 0; ограничения вида X < U учи­тываются лишь в измененном симплексном условии допустимости.

Пусть Х_в = В^_1Ь — текущее базисное допустимое решение задачи ЛП с ограни­чениями (A, I)X = b, X > 0. Обозначим через Р_; вводимый в базис вектор, опреде­ленный на основе обычного симплексного условия оптимальности. Если предполо­жить, что все небазисные переменные равны нулю, уравнение ограничения относительно базисной переменной x_t будет записано следующим образом.

(ХД=(В^,Ь),-(В-^,Р.),х_/

Поскольку вводимая переменная х примет положительное значение, величина базисной переменной (Х_в), возрастет или уменьшится, в зависимости от того, бу­дет значение (В'РД отрицательным или положительным. Таким образом, при оп­ределении значения вводимой переменной x_j необходимо удовлетворить следую­щие три условия.

1. Базисная переменная (Х_в), должна остаться неотрицательной, т.е. (Х_в), > 0.

2. Базисная переменная (Х_в), не должна превышать своей верхней границы, т.е. должно выполняться неравенство (Х_в), < (U_B)„ где U_B — вектор, содержащий упорядоченные элементы вектора U, соответствующие вектору Х_в.

3. Вводимая переменная x_t не может принять значения, превышающего верх­нюю границу, т.е. должно выполняться неравенство x.<u_t, где и.— у-й эле­мент вектора U.

Первое условие (Х_в), > 0 требует выполнения неравенства

(В-Ц-СВ-'РДа^О, которое заведомо будет выполняться, если

х,*е.=тЫ^(В"Н-

(в-'рд

(В-'РДэ-О.

Это условие полностью соответствует условию допустимости обычного симплекс-метода.

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

Условие (ХД < (U_B), эквивалентно неравенству

(в-'ьх-св-'рдж^ид,

которое будет выполняться, если

|(B-'b),-(U,),

л: <8, = тЫ ' - ' 1 (В-'Р,),

(В~'РД. <0

Наконец, третье условие будет выполнено, если выполняется неравенство х < и_г Все три неравенства относительно х. можно обобщить в виде следующего условия.

лг_у = тт{в₁₍ 9₂, и).

Базис, формируемый для следующей итерации, зависит от того, какое значение (0,, 0₂ или и) примет переменная х_}. Предполагая, что (Х_в)_г— исключаемая пере­менная, получаем следующие правила формирования базиса.

1. Если х. = Qj, то переменная (Х_в)_г исключается из базиса и принимает нулевое значение. Новый базис формируется точно так же, как в обычном симплекс-методе с вводимой переменной x_t и исключаемой (Х_в)_г.

2. Если х_л = 6₂, переменная (Х_в)_г исключается из базиса и принимает значение своей верхней границы. Новый базис формируется точно так же, как в обыч­ном симплекс-методе, но с учетом того, что переменная (Х_в)_г равна верхней границе. Поскольку значения в, и 6₂ получены при условии, что все небазис­ные переменные равны нулю, необходимо выполнить преобразование новой небазисной переменной (Х_в)_г, чтобы она также приняла нулевое значение.

Это достигается с помощью подстановки (X_B)_r= (U_B)_r- (X_fi)', где (Х_в)'>0.

Не имеет особого значения, когда выполняется эта подстановка: до или после вычисления нового базиса.

3. Если х^ = u_jt то базисный вектор Х_в остается неизменным, поскольку в данном случае никакая из текущих базисных переменных не принимает ни нулевого значения, ни значения своей верхней границы. Таким обра­зом, переменная х_} остается небазисной, но со значением своего верхнего предела. После подстановки дс = ы_; - лг_у выполняется следующая итера­ция симплекс-метода.

В случае равенства значений 0,, 0₂ и ы_у выбор правила, в соответствии с которым переходим к следующей итерации симплекс-метода, произволен. Вместе с тем предпочтительнее использовать третье правило (л:_у = и), так как в этом случае тре­буется выполнить меньший объем вычислений.

Подстановка x_f = и_} - x'_t изменяет исходные значения с_}, Р_у и b на cj = -c_jt PJ = -Р_у

и b' = b - UjPj. Это означает, что при выполнении модифицированного симплекс-метода на каждой итерации все вычисления (таких величин, как В"¹, Х_в и z_y-c_y) должны основываться на измененных значениях С, А и b (более подробно этот во­прос рассмотрен в упражнении 7.3.1.5).

7.3. Алгоритм решения задач с ограниченными переменными

Пример 7.3.1

Решим следующую задачу ЛП вышеописанным методом решения задач с ограни­ченными переменными.

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

х,+у + 2х₃<14,

2х₁ + 4у + 3х₃<43,

О < х, < 4, 7 < у < 10, 0 < х₃ < 3.

Поскольку переменная у ограничена положительной константой не только сверху, но и снизу, производим замену у = х₂ + 7, где 0 < х₂ < 10 - 7 = 3.

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

Итерация 0

Базис Xi хг хз xt х₅ Решение

z -3 -5 -2 0 0 35

x_t 112 10 7

х_ъ 2 4 3 0 1 15

Имеем В = В"¹ = I и Х_в = (л:₄, x_s)^T = B~'b = (7,1 Ъ)^т. Принимая переменную х₂ в качестве вводимой в базис переменной (z₂ - с₂ — -5), получаем B~^lP₂ = (1, 4)^т. Отсюда следует

0₂ = оо (поскольку В^_1Р₂ > 0).

Так как по условию л:₂ < 3, получаем значение, принимаемое переменной х₂.

х₂ = min{3,75, °о, 3} = 3 = и₂.

Поскольку л:₂ = и₂, базис остается неизменным; переменная х₂ в базис не вводится (остается небазисной), но принимает значение своей верхней границы. После под­становки х₂ = 3 - х\ получаем новую симплекс-таблицу.

Базис	Х1	/ Х2	хз	Xt	х5	Решение
z	-3		-2
Xi,		-1
Хь	.. 2	-Л

Выполненная подстановка изменяет исходный вектор правых частей ограничений с Ь= (7, 15)^г на Ь' = (4, 3)^г. Эти изменения должны учитываться в последующих вычислениях.

Максимизировать z = Зх₁ + 5у + 2х.

8, = mirH—, — > = 3,75, что соответствует переменной х₅,

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

Итерация 1. Определяем вводимую в базис переменную Базисный вектор Х_в и обратная матрица В"¹ (= I) такие же, как на предыдущей итерации. Вычисляем

в-'р.-а.г)'.

Отсюда следует

6, = nun j у, — > = 1,5, что соответствует переменной х_&,

9₂ = оо (поскольку В^-1Р, > 0).

Так как по условию задачи де, < 4, получаем значение, принимаемое переменной

je_I-min{l,5,oo, 4} = 1,5 (=9,).

В данной ситуации переменная х, становится базисной со значением 1,5, перемен­ная jc₅ выводится из базиса и принимает нулевое значение. Получаем следующую симплекс-таблицу.

Базис	Х1			Xi	Хь	Решение
z		-1	5/2		3/2	109/2
Xi			1/2		-1/2	5/2
х,		-2	3/2		1/2	3/2

Итерация 2. Имеем новую обратную матрицу.

В =

о

Значения базисных переменных определяются так:

Х_в = (*_4> xj = В¹ Ь' = (5/2, 3/2)^т,

где Ь' = (4, 3)^г— значения правых частей ограничений, вычисленные в конце ну­левой итерации.

Определяем х\ как вводимую в базис переменную. Учитывая, что К = ^-Р₂, получаем

Далее вычисляем

'5 2 1'

в'р; =(i,-2)^r

= 2,5, что соответствует базисной переменной x_t,

= 1,25, что соответствует базисной переменной х_г.

Так как по условию х[ < 3, получаем значение, принимаемое переменной х\.

х₂ = min{2,5,1,25, 3} = 1,25 (= 8₂).

7.3. Алгоритм решения задач с ограниченными переменными

Таким образом, переменная х'_г вводится в базис (со значением 1,25), из которого

исключается переменная дс, с ненулевым значением, равным ее верхней границе. Применяем подстановку х₁ = 4 - х\ и получаем следующую симплекс-таблицу.

Базис	А	х2	Хз	ха	Xs	Решение
z		-1	5/2		3/2	109/2
ха			1/2		-1/2	5/2
	-1	-2	3/2		1/2	-5/2
Далее в базис вводится переменная	х\ и исключается х\	, что приводит к следующей
симплекс-таблиц	е.
Базис	А	х.	Хз	ха	Xs	Решение
z	1/2		7/4		5/4	223/4
Ха	■1/2		5/4		-1/4	5/4
/ X,	1/2		-3/4		-1/4	5/4

Данная таблица представляет допустимое оптимальное решение. Оптимальные зна­чения переменных х_1У х_г и х₃ получаем обратной подстановкой: дс, = u_i - х\ =4-0 = 4, х_г = и₂ - х'₂ = 3 - 5/4 = 7/4 и х₃ = 0. Теперь вычисляем значение переменной у: у = 1₂ + х₂=7 + 7/4 = 35/4. Оптимальное значение целевой функции равно z = 223/4.

УПРАЖНЕНИЯ 7.3.1

1. Дана следующая задача линейного программирования.

Максимизировать z = 2x_t + х₂

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

х₁ + х₂<3, 0 < х, < 2, 0 < х₂ < 2.

a) Решите задачу графическим способом и определите последовательность крайних точек пространства решений, ведущих к оптимальному решению.

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

c) Как алгоритм решения задач с ограниченными переменными распознает крайние точки пространства решений?

2. Решите следующую задачу ЛП методом решения задач с ограниченными пе­ременными.