Linear Programming Output summary 2 страница

	Джем	Концентрат	Сок
(для 5-галонных банок)
Отпускная цена, долл.	15,0	30,25	20,75
Стоимость сырья, долл.	9,85	21,05	13,28
Другие расходы, долл.	1,05	2,15	1,96
Себестоимость, долл.	10,90	23,20	15,24
Чистый доход, долл.	4,80	7,05	5,51

Составьте оптимальный производственный план для компании Hi-C.

Комплексные задачи 93

2.2. ⁹ Сталелитейная компания имеет литейный цех и два прокатных стана. Ли­тейный цех производит три типа стальных заготовок, которые, прежде чем попасть на прокатные станы, обрабатываются в механическом цехе.

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

т,.г, „_тт^_п,„. Длина заготовки Внутренняя цена Цена на рынке

j ип заготовки,..

(футы) (в долл. на одну заготовку) (в долл. на одну заготовку)

1 800 90 108

2 1200 130 145

3 1650 180 194

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

Тип станка	Время обработки одной заготовки типа	Количество станков	Общее время работы станка в месяц
					(часы)
Потребности прокатных станов месяца.	в стальных заготовках на следующие три
Потребность в заготовках
	Первый прокатный стан	Второй прокатный стан
Месяц Заготовки типа 1	Заготовки типа 2	Заготовки типа 3	Заготовки типа 1	Зеготовки Заготовки типа 2 типа 3
					100 0
					200 200
					400 200

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

⁹ Взято из S. Jain, К. Stott, Е. Vasold. "Orderbook Balancing Using a Combination of Linear Pro­gramming and Heuristic Techniques", Interfaces, Vol. 9, No. 1, November 1978, pp. 55-67.

Глава 2. Введение в линейное программирование

2.3. Фирма АгкТес собирает персональные компьютеры для частных клиентов. На следующие четыре квартала имеются заказы на 400, 700, 500 и 200 ком­пьютеров соответственно. Фирма может производить больше компьютеров, чем указано в заказах, но в таком случае приходится платить 100 долл. за хранение одного компьютера в течение квартала. Увеличение производства в следующем квартале, по сравнению с предыдущим, приводит к дополни­тельному набору работников, что повышает себестоимость одного компью­тера на 60 долл. При уменьшении производства в следующем квартале, по сравнению с предыдущим, придется прибегнуть к сокращению персонала, что также увеличивает себестоимость одного компьютера на 50 долл. Как организовать сборку компьютеров, чтобы удовлетворить все заказы?

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

Ежемесячная производительность заготовительного цеха составляет 3000 стульев, 1000 столов и 580 книжных полок (несобранных). В сбороч­ном цехе работают 150 рабочих в две 8-часовые смены 5 дней в неделю. Среднее время сборки одной единицы продукции равно 20, 40 и 15 минут соответственно для стульев, столов и книжных полок.

Количество рабочих в сборочном цехе колеблется в зависимости от того, сколько человек в настоящее время находится в ежегодном отпуске. В мае, июне и июле планируют уйти в отпуск соответственно 20, 25 и 45 человек.

Отдел маркетинга фабрики оценил потребность рынка в их продукции на май, июнь и июль следующим образом.

Продукт	Май Июнь	Июль	Остаток на конец апреля
Стул	2800 2300
Стол	500 800
Книжная полка	320 300
Себестоимость продукции и ее отпускная цена показаны в следующей таблице.
Продукт	Себестоимость (долл.)	Отпускная цена (долл.)
Стул
Стол
Книжная полка

Если какая-либо продукция не продана в течение того месяца, в каком она произведена, то она может быть продана в следующем месяце. Хранение одной единицы стоит 2% от стоимости этой продукции.

Помогите фабрике разработать план ежегодных отпусков для работников сборочного цеха.

ГЛАВА 3

СИМПЛЕКС-МЕТОД

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

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

Основное свойство симплекс-метода заключается в том, что решение задачи ЛП осуществляется итерационно. На каждой итерации алгоритм переходит к новой угловой точке, которая потенциально может улучшить значение целевой функции. Этот процесс перехода от одной угловой точки к следующей заканчивается, когда дальнейшее улучшение значений целевой функции невозможно.

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

3.1. СТАНДАРТНАЯ ФОРМА ЗАДАЧИ ЛП

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

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

2. Все переменные неотрицательные.

3.1.1. Преобразование неравенств в равенства

Неравенства любого типа (со знаками неравенств < или >) можно преобразовать в равенства путем добавления в левую часть неравенств дополнительных перемен­ных — остаточных или избыточных¹, которые связаны с неравенствами типа "<" и ">" соответственно.

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

Глава 3. Симплекс-метод

Для неравенств типа "<" в левую часть неравенства вводится неотрицательная остаточная переменная. Например, в модели компании Reddy Mikks (пример 2.1.1) ограничение на количество сырья Ml задается в виде неравенства 6х, + 4х₂ < 24. Вво­дя новую неотрицательную переменную s,, которая показывает остаток (неспользованное количество) сырья Ml, это ограничение преобразуется в равенство

6x,+4x₂ + s₁ = 24, s,>0.

Неравенства типа ">" в задачах ЛП обычно устанавливают нижнюю границу че­го-либо. Избыточная переменная определяет превышение значения левой части неравенства над этой границей. Так, в модели "диеты" (пример 2.2.2) неравенство х_} + х₂ > 800 показывает, что суточное производство пищевой добавки не должно быть меньше 800 фунтов. Математически это неравенство эквивалентно равенству

х, + х₂ - S, = 800, S, > 0.

Положительное значение избыточной переменной S, показывает превышение суточного производства добавки над минимальным значением в 800 фунтов.

Важно еще раз подчеркнуть, что дополнительные переменные — остаточная s, и избыточная S, — всегда неотрицательные.

Правую часть равенства всегда можно сделать неотрицательной, умножив все равенство на -1. Кроме того, заметим, что неравенство типа "<" также преобразу­ется в неравенство типа ">" посредством умножения обеих частей неравенства на -1. Например, неравенство -х, + х₂ < -3 эквивалентно равенству

-х, + х₂ + s, = -3, s, > 0.

Теперь, умножая обе части этого равенства на -1, получим равенство с неотрица­тельной правой частью: х, - х₂ - s, = 3.

УПРАЖНЕНИЯ 3.1.1

1. В модели компании Reddy Mikks (пример 2.2.1) рассмотрите допустимое ре­шение х, = 3 т и х₂ = 1 т. Для этого решения найдите недоиспользование сы­рья Ml и М2.

2. В модели "диеты" (пример 2.2.2) определите превышение над минимальным допустимым объемом производства пищевой добавки, на которую расходует­ся 500 фунтов кукурузной муки и 600 фунтов — соевой.

3. Дано неравенство 10х,-Зх₂>-5. Покажите, что в результате преобразова­ния, когда сначала обе части неравенства умножаются на -1, а затем нера­венство преобразуется в равенство, получется такое же равенство, что и в ре­зультате преобразования, когда сначала исходное неравенство преобразуется в равенство, а затем умножается на -1.

4. Два изделия, Р1 и Р2, можно произвести на двух различных станках Ml и М2. Время изготовления любого изделия на любом станке одинаково. Про­изводительность станка Ml составляет 200 изделий за смену, а производи­тельность станка М2 — 250 изделий. Мастер планирует сбалансировать ра­бочее время таким образом, чтобы общее количество изделий, произведенных на одном станке, не превышало более чем на 5 единиц общее количество изделий, изготовленных на другом станке. Доход от одного изде­лия Р1 составляет 10, а от второго — 15 долл. Запишите эту задачу в стан­дартной форме линейного программирования.

3.1. Стандартная форма задачи ЛП 97

5. Покажите, как следующую целевую функцию можно записать в стандартной форме задачи ЛП.

Минимизировать z = maxflx, - х₂ + Зх₃\, \-х_х + Зх₂ - х₃\},

х_х, х₂, х₃>0.

6. Покажите, что т равенств вида

Y,^a„^x,=^b,- ' = 1.2,...,ш,

7 = 1

эквивалентны следующим т + 1 неравенствам.

Ё^аЛ-*" ' = 1.2,...,m,

7 = 1

II f III \ III

3.1.2. Свободная переменная

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

Пример 3.1.1

Ресторан быстрого обслуживания McBurger торгует порционными мясными пиро­гами и чизбургерами. На порцию мясного пирога идет четверть фунта мяса, а на чизбургер — только 0,2 фунта. В начале рабочего дня в ресторане имеется 200 фун­тов мяса, можно еще прикупить мясо в течение дня, но уже с наценкой в 25 центов. Мясо, оставшееся в конце рабочего дня, жертвуется благотворительной организа­ции. Ресторан получает доход 20 центов от одной порции мясного пирога и 15 цен­тов — от одного чизбургера. Как и многие другие, этот ресторан не может продать в день более 900 бутербродов. Какова должна быть доля каждого блюда (т.е. сколь­ко порций мясного пирога и сколько чизбургеров) в ежедневном производстве рес­торана, чтобы максимизировать его доход?

Сначала рассмотрим ограничения. Обозначим через х_х и х₂ соответственно количество порций мясного пирога и чизбургеров, производимых рестораном. Для их производ­ства ресторан может либо ограничиться 200 фунтами мяса, либо прикупить еще. В первом случае получаем ограничение в виде неравенства 0,25х, + 0,2х, < 200, а во втором— 0,25л', + 0,2д:₂ > 200. Естественно, выбор одного из этих неравенств будет существенно влиять на возможное оптимальное решение. Так как мы не знаем, какое из них необходимо, логично заменить их одним равенством 0,25*, + 0,2д:₂+ дг₃ = 200, гдех, — свободная переменная. Фактически свободная переменная х₃ в данной ситуа­ции одновременно играет роли как остаточной, так и избыточной переменной.

Далее построим целевую функцию. Ресторан хочет максимизировать свой доход. Очевидно, что для максимизации дохода желательно как можно больше продавать своей продукции, но для этого необходимы дополнительные закупки мяса. В этом случае переменная х₃ должна быть отрицательной, т.е. должна играть роль избы­точной переменной.

Глава 3. Симплекс-метод

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

*з ^{= х}1 ~ ^х1> ^гД^{е х}1 > ^хз - °-Если л* > 0 и л₃ = 0, то переменная.v₃ играет роль остаточной. Если, напротив, х'_} > О и xl = 0, то переменная х₃ выступает в роли избыточной. (Теория задач ЛП гласит, что переменные х*₃ и.v₃~ не могут одновременно принимать положительные значе­ния.) Итак, теперь ограничение можно записать в виде равенства

0,25л-, +0,2х₂ + х; - х~ = 200. Целевая функция получает следующее выражение.

Максимизировать z = 0,20 + 0, [5х₂ - 0,25 х_}

УПРАЖНЕНИЯ 3.1.2

1. В некотором машинном центре производятся два изделия, причем на производ­ство одной единицы первого изделия затрачивается 10 минут рабочего времени, а на единицу второго изделия — 12 минут. Рабочее время машинного центра ог­раничено 2500 минут в день (некоторые операции центр может выполнять па­раллельно); возможно превышение этой величины, но каждая дополнительная минута работы машинного центра стоит 50 центов. В рабочий день допустимо производить от 150 до 200 единиц первого изделия, но не более 45 единиц второго.

a) Предполагая, что доход от единицы первого изделия составляет 6,00 долл., а второго — 7,50 долл., постройте модель и найдите оптимальное соотно­шение между объемами производства изделий, максимизирующее общий доход, а также дополнительное время работы машинного центра.

b) Если стоимость дополнительного времени работы машинного центра уве­личится до 1,50 долл., будет ли компания использовать это время?

2. Фирма производит три вида изделий, прибыль от которых составляет соот­ветственно 2, 5 и 3 долл. на единицу изделия. Для производства этих изделий фирма располагает 80 рабочими часами ручного труда и 65 часами машинно­го времени. Для производства одной единицы изделия каждого из трех видов требуется 2, 1 и 2 часа ручного труда и 1, 1 и 2 часов машинного времени со­ответственно. При необходимости фирма может увеличить количество рабо­чих часов ручного труда и количество часов машинного времени, но каждый дополнительный час ручного труда будет стоить 15, а машинного — 10 долл.

Сформулируйте задачу линейного программирования и найдите ее опти­мальное решение с помощью программы TORA.

3. В задачах ЛП, где есть несколько свободных переменных, преобразование типа *_;=.v*-.v~, х*, Xj>0, удваивает соответствующее число неотрицатель­ных переменных. Но при использовании подстановок х =x'j-w, x'j,w>0

можно к свободных переменных заменить на ft + 1 неотрицательных. Ис­пользуя программу TORA, покажите, что эти два метода приводят к одному и тому же решению следующей задачи ЛП.

Максимизировать z = -2x, + Зх₂ - 2х₃

3.2. Переход от графического решения к алгебраическому

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

4х, - х₂ - 5х₃ = 10,

2х, + Зх₂ + 2х₃ = 12,

я, > 0, х₂, х_ъ — свободные переменные.

3.2. ПЕРЕХОД ОТ ГРАФИЧЕСКОГО РЕШЕНИЯ К АЛГЕБРАИЧЕСКОМУ

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

Графический метод

Алгебраический метод

Графическое представление всех ограничений, включая условие неотрицательности

Пространство решений состоит из бесконечного количества допустимых точек

Определяются допустимые угловые точки пространства решений

Кандидатами на оптимальное решение будут конечное число угловых точек

Целевая функция используется для определения оптимальной угловой точки среди всех кандидатов

Задание пространства решений посредством системы из т линейных уравнений с п неотрицательными переменными, т<п

Задача имеет бесконечное количество допустимых решений

Находятся допустимые базисные решения системы уравнений

Кандидатами на оптимальное решение будут конечное число базисных допустимых решений

Целевая функция используется для определения оптимального базисного допустимого решения среди всех кандидатов

Рис. 3.1. Переход от графического решения к алгебраическому

Мы можем увидеть пространство решений графического метода, имеющее бес­конечное число точек решений, но как можно сделать подобное заключение на ос­нове алгебраического представления пространства решений? Ответ заключается в том, что в алгебраическом представлении количество уравнений т всегда меньше или равно количеству переменных п.² Если т = п и система уравнений совместна, то

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

Глава 3. Симплекс-метод

она имеет только одно решение³; если же т < п и система уравнений совместна, то она имеет бесконечное множество решений. Простая иллюстрация в качестве доказа­тельства: для уравнения х = 2 имеем т = п = 1, а его решение, очевидно, единствен­ное. Для уравнения х + у = 1 имеем т — 1 и п = 2, этому уравнению удовлетворяет бесконечное множество решений (любая точка на прямой х + у=1 будет решением).

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

Следующий пример иллюстрирует это положение.

Пример 3.2.1

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

Максимизировать z = 2л-, + Зл₂

при выполнении условий

2л-,+л-_г<4, л-, + 2х._г < 5, л-,,л-₂>0.

На рис. 3.2 показано пространство решений для этой задачи. ^х2

0 1 2 3 4 5

Рис. 3.2. Пространство решений для примера 3.2.1

Это не совсем верно: совместная система уравнений имеет единственное решение тогда, когда она невырождена. — Прим. ред.

3.2. Переход от графического решения к алгебраическому

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

Максимизировать z = 2х_х + Зх_г

при выполнении условий

2дг, + х₂ + s, = 4, л-, + 2х_г + s₂ = 5,

*^2' ^1' ^2 — ^*

Здесь имеем систему из т = 2 уравнений для л = 4 переменных. Согласно сформу­лированному выше правилу угловые точки можно определить алгебраически, при­своив я-т = 4- 2 = 2 переменным нулевых значений и решив затем систему урав­нений относительно оставшихся т = 2 переменных. Если, например, положить х_х = 0 и х₂ = 0, тогда решением системы будет s, = 4, s₂ = 5. Это решение соответству­ет точке Л на рис. 3.2 (убедитесь, что решение 5, = 4, s₂ = 5 действительно соответст­вует точке А). Другую угловую точку можно определить, если положить s, = 0 и 5₂ = 0. В этом случае надо найти решение системы

2х_х + х₂ = 4,

я, + 2x₂ = 5.

Решением в данном случае будет jt, = 1 и х, = 2, что соответствует точке С на рис. 3.2.

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

4'

В нашем примере мы имеем ^1 =-^- = 6 У^гловых точек. Но, глядя на рис. 3.2,

можно насчитать только 4 угловые точки —А, В, С nD. Где "спрятались" еще две точки? В действительности точки Е и F также являются угловыми точками, но это недопустимые угловые точки, поскольку они не удовлетворяют всем ограничени­ям задачи. Такие недопустимые угловые точки не рассматриваются как кандидаты на оптимальное решение.

Для полного перехода к алгебраическому методу решения задач ЛП необходимо как-то назвать угловые точки разного типа на "алгебраическом" языке. На этом языке п - т переменные, которые полагаются равными нулю, называются неба­зисными переменными. Если оставшиеся т переменные имеют единственное ре­шение, то в этом случае они называются базисными переменными, а совокупность значений, которые они получают в результате решения системы уравнений, со­ставляют базисное решение (см. рис. 3.1). Если при этом все переменные прини­мают неотрицательные значения, то такое базисное решение является допусти­мым. В противном случае — недопустимым.⁴

ⁱ В русскоязычной математической литературе также применяются термины "план", "опорный план" и "оптимальный опорный план" как эквиваленты для терминов "базисное ре­шение", "допустимое базисное решение" и "оптимальное базисное решение". — Прим. ред.

102 Глава 3. Симплекс-метод

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

Небазисные	Базисные	Базисные	Соответствующие	Допустимо	Значение
(нулевые)	пере-	решения	угловые точки	ли решение?	целевой
переменные	менные				функции z
х2)	(Si, 8г)	(5, 4)	А	Да
Si)	(Хг, 8г)	(4, -3)	F	Нет	—
(X1. s2)	(Хг, Si)	(2,5, 1,5)	D	Да	7,5
(*2, Si)	(*1, s2)	(2, 3)	В	Да
(Хг, S>)	(Хь Si)	(5, -6)	Е	Нет	—
(Si, «г)	(Xi, x2)	(1,2)	С	Да	8 (оптимум)

Как видно из примера 3.2.1, при возрастании размера задачи (т.е. при увеличе­нии значений пит) процесс перечисления всех угловых точек становится отдель­ной чрезвычайно сложной задачей. Например, при п = 20 и т = 10, когда необхо­димо решить С'°₀ = 184756 систем уравнений порядка 10x10, получаем устрашающую, в вычислительном отношении, задачу. Здесь следует учесть, что за­дачи ЛП размерности 10x20 считаются небольшими — реальные задачи могут иметь сотни и даже тысячи переменных и ограничений. Однако симплекс-метод в значительной степени снимает эту проблему, поскольку он рассматривает не все возможные базисные решения (т.е. угловые точки пространства решений), а только часть всех допустимых базисных решений.

УПРАЖНЕНИЯ 3.2

1. Проверьте все базисные и небазисные решения, приведенные в конце при­мера 3.2.1.

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

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

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

х₁ + 3х₂<6, Зх₁ + 2х₂<6, x_v х_г>0.

a) Запишите задачу в стандартной форме.

b) Найдите все базисные решения этой задачи и определите, какие из них допустимые, а какие — нет.

c) Путем непосредственной подстановки решений в целевую функцию опре­делите наилучшее допустимое базисное решение.

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

e) Определите, чему на рисунке, где представлено пространство решений, соответствует недопустимое базисное решение.

3.2. Переход от графического решения к алгебраическому

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

a) Максимизировать z = 2х_х - 4х₂ + Ъх₃ - 6x_t при ограничениях

х_г + 4х₂ - 2х₃ + 8x_t < 2, -x_l + 2x₂ + 3x₃ + 4x_i<l,

^Х2* *^3' — О"

b) Минимизировать z = х_х + 2x₂ - 3jc₃ - 2x_t при ограничениях

л:, + 2x₂ - 3jc₃ + x₄ = 4, jc, + 2jc₂ + x₃ + 2x_t = 4, ^-p x₂, x₃, x₄ — 0.

4. Покажите, что все базисные решения следующей задачи ЛП недопустимы.

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

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

х, + 2х₂<6, 2х, + х₂ > 16, jc,, jc₂>0.

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

Максимизировать z = 2х_х + Зх₂ + Ъх₃

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

-бх, + 7х₂-9х₃>4, -х_х + х₂ + 4х₃ = 10, *„ *₃>0,

х₂ — свободная переменная. Приведите задачу к стандартной форме, используя для этого подстановку х, =х* Покажите, что в этой задаче не существует базисных решений, в

которые входили бы одновременно х, и х\.

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

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

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