ПО МАТЕМАТИКЕ
---< о —
А.С. СОЛОДОВНИКОВ
СИСТЕМЫ
ЛИНЕЙНЫХ
НЕРАВЕНСТВ

ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ
ВЫПУСК 48
А. с. солодовников
СИСТЕМЫ
ЛИНЕЙНЫХ НЕРАВЕНСТВ
ИЗДАНИЕ ВТОРОЕ,
ПЕРЕРАБОТАННОЕ И ДОПОЛНЕННОЕ
ИЗДАТЕЛЬСТВО «НАУКА»
ГЛАВНАЯ РЕДАКЦИЯ
ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ
МОСКВА 1977
512
С 60
УДК 512
АННОТАЦИЯ
В книге рассказывается о связи между систе-
мами линейных неравенств и выпуклыми много-
гранниками, дается описание множества всех
решений системы линейных неравенств, изу-
чаются вопросы совместности и несовместности;
наконец,' дается понятие о линейном программи-
ровании как об одной из глав теории систем ли-
нейных неравенств. В последнем параграфе дается
доказательство теоремы двойственности линейного
программирования.
Книга рассчитана на школьников старших
классов и всех любителей математики.
Александр Самуилович Солодовников
СИСТЕМЫ ЛИНЕЙНЫХ НЕРАВЕНСТВ
(Серия: «Популярные лекции по математике»)
М., 1977 г., 112 стр. с илл.
Редактор В. В. Донченко
Техн, редактор С. Я. Шкляр	Корректор В. П. Сорокина
Сдано в набор 15.07.77. Подписано к печати 29.11.77. Бумага 84Х108’/з2
тип. № 1. Физ. печ. л. 3,5. Усл. печ. л, 5,88. Уч-иэд. л. 5,19. Тираж 130 000 экз.
Цена книги 15 коп< Заказ № 681
Издательство «Наука»
Главная редакция физико-математической литературы
117071, Москва, В-71, Ленинский проспект, 15
Ордена Трудового Красного Знамени Ленинградская типография № 2
имени Евгении Соколовой Союзполиграфпрома при Государственном коми-
тете Совета Министров СССР по делам издательств, полиграфии и книжной
торговли.
198052, Ленинград, Л-52, Измайловский проспект, 29.
20202—007 пл © Главная редакция
V 7о'“о0-7о	физико-математической литературы
UOo(UJ)-/o	издательства «Наука», 1977, с изменениями
ПРЕДИСЛОВИЕ
Неравенства первой степени, или, как принято их
называть, линейные неравенства, — это нера-
венства вида
ах + by + с О
(для простоты мы написали неравенство с двумя не-
известными хну). Теория систем линейных нера-
венств — небольшой, но весьма увлекательный раздел
математики. Интерес к нему обусловлен в значитель-
ной мере красотой геометрического содержания, ибо
в переводе на геометрический язык задание системы
линейных неравенств с двумя или тремя неизвест-
ными означает задание выпуклой многоугольной об-
ласти на плоскости или, соответственно, выпуклого
многогранного тела в пространстве. Тем самым, на-
пример, учение о выпуклых многогранниках — древ-
няя, как мир, часть геометрии — превращается в одну
из глав теории систем линейных неравенств. Имеются
в этой теории и разделы, близкие сердцу алгебраиста;
к ним относится, например, замечательная аналогия
между свойствами систем линейных неравенств и
свойствами систем линейных уравнений (все,
что связано с последними, изучено очень давно и
очень подробно).
До недавнего времени можно было думать, что
линейные неравенства так и останутся объектом чисто
математического творчества. Положение коренньш
образом изменилось начиная с середины 40-х годов
этого столетия, когда возникла новая область при-
кладной математики — линейное программи-
рование — с важными приложениями в экономике
и технике. В конечном счете линейное программиро-
вание — это всего лишь один из разделов (хотя и
очень важный) теории систем линейных неравенств.
1*
з
Эта небольшая книга как раз и ставит своей
целью ознакомить читателя с различными аспектами
теории систем линейных неравенств: с геометрической
стороной вопроса и тесно связанными с нею методами
решения систем, с некоторыми чисто алгебраическими
свойствами систем, с вопросами линейного програм-
мирования. Для чтения ее не нужно никаких знаний,
превышающих школьный курс математики.
Коснемся в нескольких словах истории освещен-
ных в этой книге вопросов.
Хотя по своему предмету теория систем линейных
неравенств должна, казалось бы, относиться к самым
основным и элементарным разделам математики, до
последнего времени ею занимались сравнительно
мало. Начиная с последних лет прошлого века, из-
редка появлялись работы, в которых освещались те
или иные свойства систем линейных неравенств.
Можно отметить в этой связи имена таких математи-
ков, как Г. Минковский (один из крупнейших гео-
метров конца прошлого и начала этого столетия, осо-
бенно известен своими работами по выпуклым мно-
жествам и как автор «геометрии Минковского»),
Г. Ф. Вороной (один из родоначальников «петербург-
ской школы теории чисел»), А. Хаар (венгерский ма-
тематик, получил известность благодаря работам по
«интегрированию на группах»), Г. Вейль (один из
наиболее выдающихся математиков первой половины
нашего века, о его жизни и деятельности можно про-
читать в брошюре И. М. Я гл ома «Герман Вейль»,
изд-во «Знание», М., 1967). Некоторые из полученных
ими результатов в той или иной мере нашли отраже-
ние в настоящей книге (хотя и без упоминания об их
авторах).
По-настоящему интенсивное развитие теории си-
стем линейных неравенств началось лишь в 40—50-х
годах этого столетия, когда бурный рост прикладных
дисциплин (линейное, выпуклое и другие разновид-
ности «математического программирования», так на-
зываемая «теория игр» и т. д.) сделал необходимым
углубленное и систематическое изучение линейных
неравенств. В настоящее время полный список статей
и книг по линейным неравенствам насчитывал бы, ве-
роятно, сотни различных названий.
§ 1. НЕСКОЛЬКО ФАКТОВ ИЗ АНАЛИТИЧЕСКОЙ
ГЕОМЕТРИИ
1°. Операции над точками. Введем на плоскости
прямоугольную систему координат. Тот факт, что точ-
ка М имеет в этой системе координаты х и у, мы за-
писываем следующим образом:
М — (х, у) или же просто М(х, у).
Наличие координатной системы позволяет произ-
водить над точками плоскости некоторые операции,
а именно операцию сложения точек и опе-
рацию умножения точки на число.
Сложение точек определяется так: если Mi =.
= (Xi, z/i) и М2 = (х2, у2), то
М] -|- М2 — (Xi -|- х2, у\ -|- у2).
Таким образом, сложение точек сводится к сложению
их одноименных координат.
Геометрический смысл этой
операции очень прост (рис. 1):
точка + М2 есть четвертая
вершина параллелограмма, по-
строенного на отрезках OMj и
ОМ2 как на сторонах (О — нача-
ло координат). Остальными тре-
мя вершинами параллелограмма
являются Мь О, М2.
То же самое можно, впрочем, сказать и по-дру-
гому: точка Mi + М2 получается из точки М2 путем
параллельного переноса в направлении отрезка ОМ]
на величину, равную длине этого отрезка.
Умножение точки М(х, у) на произвольное число k
производится по следующему правилу:
kM — (kx, ky).
б
Геометрический смысл этой операции еще проще, чем
в случае сложения: при k > 0 точка М' = kM лежит
на луче ОМ, причем ОМ' = k-OM-, при k <Z 0 точка
М' лежит на продолжении луча ОМ за точку О, при-
чем ОМ' — | k| • ОМ (рис. 2).
Вывод указанного выше геометрического истолко-
вания обеих операций послужит неплохим упражне-
нием для читателя *).
Введенные нами операции очень удобны для пе-
ревода геометрических фактов на язык алгебры. При-
ведем несколько примеров такого перевода.
1)	Отрезок М[М2 состоит из всех точек вида
SjAlj -|- s2M2,
где $i, $2— любые два неотрицательных числа, сумма
которых равна 1.
Здесь чисто геометрический факт — принадлеж-
ность точки отрезку Л1|Л42— записывается в виде ал-
гебраического соотношения М = SjM। + s2M2 с ука-
занными выше ограничениями на s<, s2.
Для доказательства рассмотрим произвольную
точку М на отрезке MiTW2. Проведя через М прямые,
параллельные ОМ2 и OMit получим точку N[ на от-
резке ОМ[ и точку N2 на отрезке ОМ2 (рис. 3). Пусть
_ М2М _ М1М
Sl — M2Mt ’ S2 — МгМ2 ’
*) Если только читатель не знаком с основами учения о
векторах. С векторной точки зрения наши операции, как извест-
но^ означают следующее: точка М, + М2 есть конец вектора
OMi + OAf2, а точка kM — конец вектора k OM (при условии,
что началом этого вектора является точка О).
6
числа Si и s2 неотрицательны и в сумме дают 1. Из
подобия соответствующих треугольников находим
ONi _ М2М	ON2 MiM
OMi ~' Af2M, — S>’ ОМ2 ~ М\М2	®2’
откуда следует Л4 = s4!4i, N2 = s^M2. Но М = Ni 4-'
.4- Аг, следовательно, М = SiMi 4- s2M2. Наконец, за-
метим, что, когда точка М пробегает отрезок МГМ2
в направлении от Mi к М2, число s2 пробегает все зна-
чения от 0 до 1. Предложение 1) доказано.
2)	Любая точка М прямой М{М2 представляется
в виде
tMi 4- (1 — /) М2,
где-, t — некоторое число.
В самом деле, если, точка М лежит на отрезке
AliAla, то наше утверждение, следует из доказанного
выше. Пусть М лежит вне отрезка AfiAf2- Тогда либо
точка Mi лежит на отрезке ММ2 (как на рис. 4), либо
М2 лежит на отрезке MMi- Предположим, например,
что имеет место первый случай. Тогда, по доказан-
ному,
Mi = sM + (1— s) М2 (0 < s < 1).
Отсюда
М = 1 Mi - М2 = tMi 4- (1 - t}M2,
где / = —. Случай, когда М2 лежит на отрезке MMi,
предоставляем рассмотреть читателю.
7
3)	Когда параметр s возрастает от 0 до оо, точка
sB пробегает луч ОВ*), а точка А sB — луч, вы-
ходящий из А в направлении ОВ. Когда s убывает от
О до — оо, точки sB и А + sB пробегают лучи, допол-
нительные к указанным выше. Для доказательства
достаточно взглянуть на рис. 5 и 6.
Из предложения 3) вытекает, что при изменении s
от — оо до + оо точка А -f- sB пробегает прямую, про-
ходящую через А параллельно ОВ.
Операции сложения и умножения на число можно,
разумеется, производить и над точками в простран-
стве. В этом случае, по определению,
Л1] + Л12 = (xi + х2, у\ + у2, zx + z2),
kM = (kx, ky, kz).
Все предложения, доказанные выше, очевидно, бу-
дут справедливы и в пространстве.
В заключение этого раздела примем одно согла-
шение, которое поможет нам в дальнейшем формули-
ровать многие факты более ясно и лаконично. Имен-
но, если Ж и S — какие-либо два множества точек
(на плоскости или в пространстве), то условимся под
их «суммой» Ж + Z понимать совокупность всех то-
чек вида К + L, где К — произвольная точка из Ж,
a L-— произвольная точка из S.
В математике давно уже применяется специальная
запись для обозначения принадлежности какой-либо
точки данному множеству. А именно, для того чтобы
указать, что точка Л1 принадлежит множеству Л, пи-
*) Предполагается, что точка В отлична от начала коор-
динат О.
8
шут М s JK. (знак s заменяет слово «принадле*
жит»). Итак, Ж + 25 есть множество всех точек вида
К + L, где К е Ж’, a L е 9?.
Исходя из геометрического смысла сложения то*
чек, можно дать простое правило для сложения то*
чечных множеств Ж и 9?. Это правило заключается
в следующем: нужно для каждой точки К е Ж по*
строить множество, получающееся из 9? параллель*
ным переносом на отрезок ОК, затем все полученный
таким образом множества объединить в одно. Это по*
следи ее и будет Ж 4- 95.
Укажем несколько примеров.
1.	Пусть множество Ж состоит из одной точки /(,
в то время как S?, — какое угодно множество точек.
Рис. 1,	Рис. 8.
Множество К + S’ есть результат параллельного пв*
реноса множества 9? на отрезок ОК (рис. 7). В част«
Ности, если 9? — прямая, то К +’ S’ — прямая, парад*
дельная S’. Если при этом прямая S’ проходит через
начало координат, то К 4- S’ есть прямая, параллель*
ная 9? и проходящая через точку К (рис. 8).
2.	Ж и S’ — отрезки (на плоскости или в про-
странстве), не параллельные между собою (рис. 9).
Тогда множество Ж 4- S’ — параллелограмм со сто-
ронами, равными и параллельными Ж и S’ (соответ*
ственно). Что получится в случае, когда отрезки Ж,
и S’ параллельны?
3.	Ж — плоскость, a 9? — не параллельный ей от-
резок. Множество Ж 4- S’ есть часть пространства,
Заключенная между двумя плоскостями, параллель-
ными Ж (рис. 10).
4.	Ж и S’— круги радиусов rY и г2 с центрами Pi
и Р2 (соответственно), лежащие в одной плоскости я.
2 А, С, Солодовников	9
Тогда Ж 4- Z — круг радиуса /ч + Гг с центром в точ-
ке Pi -f- Р2, лежащий в плоскости, параллельной л;
(рис. 11).
2°. Геометрический смысл уравнения и неравен-
ства первой степени с двумя или тремя неизвестными.
Рассмотрим уравнение первой степени с двумя неиз-
вестными х и у:
ах 4- by 4- с — 0.	(1)
Истолковывая х и у как, координаты точки на
плоскости, естественно поставить вопрос: какое
множество на плоскости образуют точки, координаты
которых удовлетворяют уравнению (1), или, выра-
жаясь короче, какое множество точек определяет
уравнение (1)?
10
Мы дадим ответ, хотя, вероятно, он известен чита-
телю: множество точек, определяемых уравнением (1),
есть прямая линия на плоскости. Действительно, если
b =/= 0, то уравнение (1) приводится к виду
у = kx + р,
а это уравнение, как известно, определяет прямую.
Если же b = 0, то уравнение приводится к виду
х — h
и определяет прямую, параллельную оси ординат.
Рис. 12.
Аналогичный вопрос возникает и в отношении не-
равенства
ах + by -f- с 0.	(2)
Какое множество точек на плоскости определяет не-
равенство (2)?
И здесь ответ очень прост. Если b =/= 0, то данное
неравенство приводится к одному из видов
у kx + р или у kx -f- р.
Нетрудно понять, что первому из этих неравенств удо-
влетворяют все точки, лежащие «выше» прямой у —
= kx 4- Р или же на этой прямой, а второму—все
точки, лежащие «ниже» прямой у — kx 4- р или на
этой прямой (рис. 12). Если же b — 0, то неравенство
приводится к одному из видов
х h или х й;
первому из них удовлетворяют все точки, лежащие
«правее» прямой х = h или на этой прямой,
2*	Ц
второму — все точки, лежащие «левее» прямой
х = h или на этой прямой (рис. 13).
Итак, уравнение (1) определяет на координатной
плоскости прямую линию, а неравенство (2) — одну
из двух полуплоскостей, на которые эта прямая раз-
бивает всю плоскость
(саму прямую мы считаем при-
надлежащей любой из двух
определяемых ею полуплоско-
стей).
Мы хотим теперь решить
аналогичные вопросы в отно-
шении уравнения
ах + by + cz + d = 0 (3)
и неравенства
ах + by + cz + d 0; (4)
разумеется, при этом х, у, z
истолковываются как коорди-
наты точки в пространстве.
Результат, как нетрудно предвидеть, получится сле-
дующий.
Теорема. Уравнение (3) определяет в про-
странстве некоторую плоскость, а неравенство (4)—
Ьдно из двух полупространств, на которые эта пло-
скость разбивает все пространство (сама плоскость
считается принадлежащей любому из двух определяе-
мых ею полупространств).
Доказательство. Из трех чисел а, Ь, с хотя
бы одно отлично от нуля; пусть, например, с =/= 0.
Тогда уравнение (3) приводится к виду
г == kx 4- ly 4- р.
(5)
Обозначим через J? множество всех точек М(х, у, z),
удовлетворяющих (5). Наша цель — показать, что 3?
есть плоскость.
Выясним, какие точки из Z принадлежат коорди-
натной плоскости yOz. Для этого следует в (5) поло*
жить х = 0. Получим
z == ly -j- р.
(6)
12
Итак, пересечение Z с плоскостью yOz есть прямая
и, определяемая в этой плоскости уравнением (6)
(рис. 14).
Аналогично найдем, что пересечение S’ с пло-.
скостью xOz есть прямая v, определяемая в этой пло<
скости уравнением
z = kx -f- р.
(7)1
Обе прямые и и v проходят через точку Р (0, 0, р).
Обозначим через л плоскость, содержащую пря«
мые и и v. Покажем, что
ству S’.
Для этой цели достаточ-
но установить следующий
факт: прямая, проходящая
через любую точку А е v
параллельно и, принадле-
жит S’.
Сначала найдем какую-
нибудь точку В такую, что
ОВ || и. В плоскости yOz
уравнение z = ly + р опре-
деляет прямую и; значит,
уравнение z = ly опреде-
ляет прямую, параллель-
л принадлежит множен
ную и и проходящую через
начало координат (на рис. 14 она показана пункти<
ром). В качестве В можно взять точку с координа-
тами у = 1, z = I, лежащую на этой прямой.
Произвольная точка А <= v имеет координаты х, О,
kx + р. Выбранная нами точка В имеет координаты
О, 1, I. Прямая, проходящая через А параллельно и.
состоит из точек
А + sB = (х, 0, kx +' р) -f- $ (0, 1, /) =
= (х, s,kx 4- р 4- si),
где $ — произвольное число (см. предложение 3) из
раздела 1°). Легко проверить, что координаты точки
А 4- sB удовлетворяют уравнению (5), т. е. что А 4-1
14- sB е S’. Этим доказано, что плоскость л целиком
принадлежит множеству S’.
Остается сделать последний шаг — показать, что
S’ совпадает с л, т. е. что никаких точек вне л мно-|
жество S' не содержи^
13
Для этого рассмотрим три точки: точку Л4(х0, у о, z0),
лежащую в плоскости л, точку М'(х0> уй, z0 + е), ле-
жащую «над» плоскостью л (е > 0), и точку
М" (х0, у0, z0— е), лежащую «под» л (рис. 15). Так
как М е л, то z0 = kxo +
+ 1Уо -f- Р и, следова-
тельно,
Zq 4* 8 > kXo 4* lyo 4- Рг
Zfl — 8 <с kxo 4“ lyo 4- Р‘
Отсюда видно, что коор-
динаты точки М' удовле-
творяют строгому нера-
венству
z > kx 4- ly 4- Р,
а координаты точки М"— строгому неравенству
z с kx 4- ly 4* Р-
Тем самым М' и М" не принадлежат S. Это до-
казывает, что S совпадает с плоскостью л. Кроме
того, из наших рассуждений следует, что множество
всех точек, удовлетворяющих неравенству
ах 4- by 4- cz 4- d 0,
есть одно из двух полупространств («верхнее» или
«нижнее»), на которые плоскость л разбивает все
пространство.
§ 2. ГЕОМЕТРИЧЕСКИЙ СМЫСЛ СИСТЕМЫ
ЛИНЕЙНЫХ НЕРАВЕНСТВ
С ДВУМЯ ИЛИ ТРЕМЯ НЕИЗВЕСТНЫМИ
Пусть дана система неравенств
а\.х 4~ Ь^у 4~	0,
п2х 4- Ь2у + с2 > 0, f
(1)
&mX "I- bmy 4“	0
с двумя неизвестными х и у.
Первое неравенство системы определяет на коор-
динатной плоскости хОу некоторую полуплоскость Ш,
14
второе — полуплоскость Пг и т. д. Если какая-либо
пара чисел х, у удовлетворяет всем неравенствам (1),
то соответствующая точка М (х, у) принадлежит всем
полуплоскостям Пь Пг, ..., Пт одновременно. Дру-
гими словами, точка М принадлежит пересечению
(общей части) указанных полуплоскостей. Легко ви-
деть, что пересечение конечного числа полуплоскостей
есть некоторая многоугольная область X. На рис. 16
показана одна из возмож-
ных областей Вдоль
контура области изобра-
жены штрихи, идущие
внутрь области. Они од-
новременно указывают, с
какой стороны от данной
прямой лежит соответст-
вующая полуплоскость;
то же самое указано и с
помощью стрелок.
Область Ж называет-
ся областью реше-
ний	системы (1).
Сразу же отметим, что	рИс. 16.
область решений не всег-
да бывает ограничена; в результате пересечения не-
скольких полуплоскостей может возникнуть и неогра-
ниченная область, как, например, область на рис. 17.
Имея в виду то обстоятельство, что граница области
W состоит из кусков прямых (или из целых прямых),
мы говорим, что W есть многоугольная об-
ласть (заметим, что в случае, когда область Ж ог-
раничена, ее называют просто многоугольни-
ком*) решений системы (1)). Разумеется,
возможен и такой случай, когда нет ни одной
точки, принадлежащей одновременно всем рассма-
триваемым полуплоскостям, т. е. когда область X
*) Здесь мы должны во избежание недоразумений сделать
одну оговорку. В школьном курсе геометрии под «многоуголь-
ником» понимается замкнутая линия, состоящая из отрезков пря-
мых. Между тем в литературе по линейным неравенствам этот
термин обозначает не саму линию, а множество всех точек пло-
скости, охваченных ею (т. е. лежащих внутри или иа самой
линии). В дальнейшем термин «многоугольник» мы будем по-
нимать именно в этом последнем смысле.
15
«пуста»; это означает, что система (1) противоречива.
Такой случай изображен на рис. 18.
Область решений Ж всегда выпукла. Напомним,
.что, согласно общему определению, множество точек
Рис. 18.
Рис. 17.
(на плоскости или в пространстве) называется в ы-
п у к лым, если вместе с любыми двумя своими точ-
ками А и В оно содержит и весь отрезок АВ. Рис. 19
иллюстрирует различие между выпуклым и невыпук-
лым множествами. Выпуклость области решений Ж.
Рис. 19.
вытекает из самого способа образования области;
ведь последняя получена путем пересечения несколь-
ких полуплоскостей, а каждая полуплоскость есть вы-
пуклое множество.
Впрочем, чтобы не оставалось никаких неясностей
в отношении выпуклости Ж, докажем следующую
лемму.
Она получается
Лемма. Пересечение любого числа выпуклых
множеств есть выпуклое множество.
Доказательство. Пусть и J2 — два вы-
пуклых множества и Ж — их пересечение. Рассмо-
трим любые две точки А и В, принадлежащие Ж
(рис. 20). Так как А ^Ж\, В <= Ж1_ н множество
выпукло, то отрезок АВ принадлежит Жъ Аналогич-
ным образом отрезок АВ принадлежит Ж2- Итак, от-
резок АВ принадлежит одновременно обоим множе-
ствам Ж\ и Ж2, а следователь-
но, и их пересечению Ж. Этим
доказано, что Ж — выпуклое
множество. Аналогичное рас-
суждение показывает, что пе-
ресечение любого числа (не
обязательно двух) выпуклых
множеств есть выпуклое мно-
жество.
Итак, геометрическое ме-
сто точек, координаты кото-
рых удовлетворяют всем нера-
венствам (1), или область
решений системы (1), есть вы-
пуклая многоугольная область Ж.
в результате пересечения всех полуплоскостей, отве-
чающих неравенствам данной системы.
Обратимся к случаю трех неизвестных. Теперь нам
дана система
-|- bvy -|- щг -р 0, '
п2х +b2y +c2z 4-rf2 >0,
4" ^тУ 4" ст% 4"	0. ,
(2)
Каждое из написанных неравенств определяет, как мы
знаем из § 1, некоторое полупространство. Поэтому
область, определяемая данной системой, будет пред-
ставлять собой пересечение (общую часть) т полу-
пространств. Но пересечение конечного числа полу-
пространств есть некоторая выпуклая многогранная
область Ж. На рис. 21 приведен пример такой обла-
сти при т = 4. В этом примере область Ж есть обыч-
ный тетраэдр (точнее, Ж состоит из всех точек, лежа-
щих внутри и на границе тетраэдра). И вообще
17
нетрудно понять, что любой выпуклый многогранник
можно получить в результате пересечения конечного
числа полупространств *). Конечно, возможен и такой
случай, когда область Ж не ограничена (прости-
рается в бесконечность); пример такой области изо-
бражен на рис. 22. Наконец, может оказаться, что
вообще не существует точек, удовлетворяющих всем
рассматриваемым неравенствам (система (2) проти-
воречива); тогда область W пуста. Такой случай изо-
бражен на рис. 23.
Особо следует остановиться на случае, когда среди
неравенств (2) имеются два таких:
ах 4- by + cz + d О,
— ах — by — cz — d О,
которые можно заменить одним уравнением
ах + by -f- cz -f- d ~ 0.
Последнее определяет в пространстве некоторую пло-
скость л. Остальные неравенства (2) будут выделять
из плоскости л некоторую выпуклую многоугольную
область, которая и будет служить областью решений
системы (2). Мы видим, что частным случаем выпук-
лой многогранной области в пространстве может слу-
жить выпуклая многоугольная область на плоскости.
*) Это место нуждается в пояснении того же рода, что и
в сноске на стр. 15. Дело в том, что в школьном курсе геомет-
рии под «многогранником» понимается замкнутая поверхность,
составленная из плоских граней. Мы будем вкладывать в этот
термин более широкий смысл, называя «многогранником» не
саму поверхность, а множество всех точек пространства, охва-
ченных ею (разумеется, это множество включает и самую по-
верхность, ио только — как часть).
18
На рис. 24 область Ж представляет собой треуголь-
ник, образованный пересечением пяти полупро-
странств: два из них ограничены «горизонтальной»
плоскостью л, остальные три полупространства в пе-
ресечении образуют «вертикальную» трехгранную
призму.
По аналогии со случаем двух неизвестных мы на
зываем область Ж о б л а
стемы (2). Еще раз под-
черкнем то обстоятельство,
что область Ж, будучи пере-
сечением некоторого числа
полупространств, обязатель-
но выпукла.
Итак, система (2) опре-
деляет в пространстве вы-
пуклую многогранную об-
ласть Ж. Последняя по-
лучается в результате пе-
тью решений с и-
Рис. 24.
ресечения всех полупро-
странств, отвечающих неравенствам данной системы.
Если область Ж ограничена, то ее называют про-
сто м н о го г р а н н и ком решений системы (1).
§ 3. ВЫПУКЛАЯ ОБОЛОЧКА СИСТЕМЫ ТОЧЕК
Вообразим, что в плоскость, имеющую вид беско-
нечного листа фанеры, в точках Alt Аг, ... , Ар вбиты
колышки. Изготовив петлю из резины и растянув ее
как следует, охватим ею все колышки (пунктирная
линия на рис. 25). Затем дадим петле стянуться, ра-
зумеется, насколько позволят забитые нами колышки.
Множество точек, охваченных петлей после стягива-
ния, изображено на рис. 25 штриховкой. Оно пред-
ставляет собой, очевидно, некоторый выпуклый мно?
гоугольник. Последний называется выпуклой
оболочкой системы точек А\, Аг, ..., Ар.
Если точки Ль Аг, ..., Ар расположены не на пло-
скости, а в пространстве, то осуществить аналогичный
эксперимент практически довольно трудно. Однакб
дадим волю воображению и представим себе, что
точки Ль Аг, ..., Ар удалось заключить в мешок, сде-
ланный из тугой резиновой пленки. Предоставленный
самому себе, мешок будет стягиваться до тех пор,
19
пока этому не начнут мешать некоторые из данных
точек. Наконец, наступит такой момент, когда даль-
нейшее стягивание будет уже невозможно (рис. 26).
Довольно ясно, что к этому моменту мешок примет
форму выпуклого многогранника с вершинами в не-
которых из точек At, Аг, ...» Ар. Область простран-
ства, охваченная этим многогранником, снова назы-
вается выпуклой оболочкой системы точек At, Аг, ...
>  , Ар.
Данное выше определение выпуклой оболочки хотя
и очень наглядно, но не вполне безупречно с точки
зрения «математической строгости». Определим те-
перь это понятие строго.
Пусть Ai, Аг, .. •, Ар — произвольный набор точек
'(на плоскости или в пространстве). Рассмотрим все-
возможные точки вида
+ s2A2 + ,.. + SpAp,
(D
где Si, «2, ..., Sp — какие угодно неотрицательные
Висла, дающие в сумме единицу:
s2, ..., sp>0 и Sj + s2+ ... +«р=1. (2)
Определение. Множество точек вида (1)
с условием (2) называется выпуклой оболоч-
кой системы то че к At, Аг, ,.., Ар и обозна-
чается
И1, А, • • • > Лр).
80
Чтобы убедиться в том, что это определение не
расходится с прежним, рассмотрим сначала случаи
р = 2 и р = 3. Если р = 2, то нам даны две точки At
и Аг. Множество (Дь Аг), как показывает предложен
ние 1) § 1, есть отрезок ДИг.
Если р = 3, то нам даны три точки At, Аг и Аз.
Покажем, что множество {At, Аг, Дз) состоит из всех
точек, лежащих внутри и на сторонах треугольника
А 1А%Аз.
И вообще докажем следующую лемму.
Лемма. Множество (Д1, ..., Ap~t, Ар) состоит
из всевозможных отрезков, соединяющих точку Ар
с точками множества {At, ..., Др-i).
Доказательство. Для удобства дальнейших
записей обозначим множество (Дь ..., Др-i) через
Яр_\, а множество (Дь ..., Др-ь Др) через Яр.
Рассмотрим любую точку Де.#р. Она имеет вид
Д = $1Д1 + ... Д-sp_^p_! Д-5рДр,
где
Si, ...» sp^0, Si+ ... +sp = l.
Если sp = 0, то A^J(p-t', таким образом, множе-
ство Яр-t является частью Яр. Если sp=l, то
Д = ДР; таким образом, точка Др принадлежит Яр.
Итак, Яр содержит Яр-Х и точку Др. Покажем те-
перь, что любой отрезок А'АР, где А’ Яр-t, целиком
принадлежит Яр.
Если А — точка такого отрезка, то
А = tA' 4" $ДР (f, s 0, 14~ s = 1).
С другой стороны, по определению точки А' имеем
Д/==/1Д1+ ... +/Р-1ДР-1
(Л» •••» ^р-1^0» 4+ ••• + ^р-1=1)>
следовательно,
Д = //1Д1+ ... ftp-1 Ap-t	s Ар.
Полагая tti = Si, ..., ttp-t = sp_b s = sp, получим (1)>
(2). Этим доказано, что А^ЯР. Итак, любой из ука-
занных выше отрезков целиком принадлежит Яр,
21
Нам остается теперь проверить, что ничего сверх
таких отрезков множество jftP не содержит, т. е. что
любая точка А из Лр принадлежит одному из рас-
сматриваемых отрезков.
Пусть А е М-р. Тогда имеем (1), (2). Можно счи-
тать sp 1, иначе А = Ар, и доказывать нечего. Но
если sp 1, то Si + ... + sp-i = 1 — sp > 0, поэтому
можем записать
Л = («14- ... +sp-i)[—г— Д] + ...
Loi Т ... -f Зр —i
S п — I	”1
••• + S, + ... +sp_, Лр-1] + Мр-
Выражение, стоящее в квадратных скобках, опреде-
ляет некоторую точку А', принадлежащую j(p-\, ибо
коэффициенты при Alt ..., Ap-i в этом выражении
неотрицательны и в сумме дают 1. Итак,
4 = (Si+ ... + sP-i) 4'+ sp4p.
Поскольку коэффициенты при А' и Ар также неотри-
цательны и в сумме дают 1, точка А лежит на отрезке
А'АР. Этим доказательство леммы завершается.
Теперь нетрудно понять, что данное в начале этого
параграфа наглядное определение выпуклой оболочки
и последующее строгое определение эквивалентны.
Действительно, какое бы из двух определений выпук-
лой оболочки мы ни взяли за основу, в обоих слу-
чаях переход от выпуклой оболочки системы At, ...
..., Ар-1 к выпуклой оболочке системы Ai, ..., Ap-i,
Ар происходит по одному и тому же правилу: точ-
ку Ар нужно соединить отрезками со всеми точками
выпуклой оболочки для 41, ..., Ар-1 (при наглядном
определении выпуклой оболочки это правило непо-
средственно очевидно, при строгом определении оно
составляет содержание леммы). Если теперь учесть,
что при р = 2 мы получаем согласно обоим опреде-
лениям одно и то же множество — отрезок А1Аг, — то
эквивалентность обоих определений станет очевидной.
Впрочем, термин «выпуклая оболочка» еще не
вполне нами оправдан, ибо мы еще не показали, что
множество (41, 4г, ..., 4Р) всегда выпукло. Сделаем
это сейчас.
22
Пусть А и В — две произвольные точки этого мно-
жества:
А —	+ s2A2 + ... + spAp,
В — /1Д+/2А+ ••• + tpAp,
где
Si....sp, ti, .... tp > 0,
si + • • • 4* sp = ti A- •  • A- tp — 1-	(3)
Любая точка С отрезка АВ имеет вид
С = sA + tB,
где
s, t 0, s + t — 1,	(4)
откуда следует
С = s (S]Ai 4- ... -j~spAp) 4- t(tiAi 4-... 4- tpAp) ='
= (SS1 4- tti) Ai 4*... 4* (ssp 4- ttp)Ap.
Числа, стоящие коэффициентами при Ai, ..., Ар,
неотрицательны и в сумме дают 1 (как следует из
(3), (4)). Это означает, что точка С принадлежит
множеству (Ai, А2, .... Ар}, т. е. что это множество
является выпуклым.
Вместе с тем легко видеть, что (Af, А2, ..., Ар} —
это наименьшее из всех выпуклых множеств, со-
держащих исходные точки Аь А2, ..., Ар, т. е. что оно
содержится в любом из таких множеств. Это утверж-
дение непосредственно следует из доказанной выше
леммы и из определения выпуклого множества.
Указанный выше факт объясняет название «вы-
пуклая оболочка». Одновременно он дает еще одно
объяснение тому, что множество (Аь А2, ..., Ар} мо-
жет быть получено с помощью приема, описанного
в начале этого параграфа. Ведь множество, охвачен-
ное резиновой петлей (или пленкой) после того, как
последняя стянется до предела вокруг системы точек
Аь А2, ..., Ар, — это и есть как раз наименьшее вы-
пуклое множество, содержащее указанные точки.
§ 4. ВЫПУКЛЫЙ МНОГОГРАННЫЙ КОНУС
Начнем с определения.
Выпуклым многогранным конусом на-
зывается пересечение конечного числа полупрост-
ранств, граничные плоскости которых проходят черв»
23
общую точку, последняя называется вершиной
конуса.
Прежде всего укажем, в каком отношении поня-
тие выпуклого многогранного конуса находится к си-
стемам линейных неравенств. Ограничимся частным
случаем, а именно, когда вершина конуса есть начало
координат. Это означает, что все граничные плоско-
сти проходят через начало координат. Но уравнение
плоскости, проходящей через начало координат, имеет
вид
ах 4- by + cz = О
(свободный член уравнения должен равняться нулю,
в противном случае (0, 0, 0) не будет решением). Та-
ким образом, выпуклый многогранный конус с верши-
ной в начале координат — это область решений неко-
торой системы однородных неравенств:
а{х + Ьху + щг ^>0, '
а2х + b2y + с2г 0,
►
dm* bmy 4* cmz > 0. t
Разумеется, верно и обратное: область решений од-
нородной системы неравенств всегда представляет со-
бой некоторый выпуклый много-
8	гранный конус с вершиной в на-
Лк	чале координат.
/1 \\	Примером выпуклого много-
/ I \\	гранного конуса может служить
/	I	\\	выпуклая область в простран-
/	I	\\	Стве, границей которой служит
/	/	\ \	некоторый многогранный угол
Z-—---г-----> \ вершиной S — нечто вроде
X.	I	бесконечной выпуклой Пира-
Миды, не имеющей основа-
ния и неограниченно прости-
Рис. 27» рающейся в направлении от
Вершины (на рис. 27 изобра-
жена одна из таких пирамид, имеющая четыре
грани). Но возможны и менее интересные случай, на-
пример:
1.	Полупространство (рис. 28, а). У такого «ко-
нуеа» роль вершины может играть любая точка S е
84
ел, где л — граничная плоскость данного полупро*
странства.
2.	Пересечение двух полупространств, граничные
плоскости которых пересекаются по некоторой пря*
мой I (рис. 28, б). Роль вершины может играть любая
точка Se /.
3.	Плоскость. Ясно, что любую плоскость л в прр-
странстве можно рассматривать как пересечение двух
Рис. 28.
полупространств, расположенных по разные стороны
от л (рис. 28, в). Роль вершины в этом случае может*
играть любая точка Sen.
4.	Полуплоскость (рис. 28, а). Вершина S — любая
точка граничной прямой.
5.	Прямая. Каждую прямую I в пространстве
можно получить пересечением трех полупространств,
граничные плоскости которых проходят через I
(рис. 28,6). Вершина S — любая точка прямой I.
6.	Угол (меньший 180°) в произвольной плоско*
сти л (рис. 28, е). Угол можно получить, пересекая
плоскость л с двумя полупространствами (каи
именно?).
3 А. С. Солодовникоз
23
7.	Луч (рис. 28,ж). Луч может рассматриваться
как пересечение прямой и полупространства. Вер-
шина 5 — начало луча.
8.	Точка. Такой «конус» можно получить, взяв
общую часть луча и соответствующего полупростран-
ства (рис. 28, з).
Конечно, перечисленные нами примеры 1—8 рас-
ходятся (одни в меньшей степени, другие в большей)
с обычным употреблением слова «конус», но мы вы-
нуждены с этим мириться, если хотим сохранить дан-
ное в начале этого параграфа общее определение вы-
пуклого многогранного конуса.
Постараемся теперь в нескольких словах показать,
что указанными выше множествами исчерпываются
все многогранные выпуклые конусы в пространстве.
Пусть р обозначает число полупространств, пере-
сечением которых является рассматриваемый конус
Ж. Если /7=1, то наше утверждение справедливо,
ибо тогда Ж есть полупространство. Простое рассуж-
дение, которое мы предоставим провести читателю,
показывает, что если наше утверждение верно для
конуса, полученного в результате пересечения р по-
лупространств, то оно верно также и для конуса, об-
разованного пересечениехМ р 4- 1 полупространств. От-
сюда по принципу полной математической индукции
следует, что наше утверждение справедливо для лю-
бого р.
Выпуклые многогранные конусы обладают мно-
гими интересными свойствами. Рамки настоящей кни-
ги не позволяют нам углубляться в эту тематику —
ограничимся лишь несколькими, наиболее простыми
предложениями.
Введем еще одно определение, или, если угодно,
обозначение.
Пусть В(, В2, ..., Bq — произвольный набор из
конечного числа точек (в пространстве). Символом
(Bt, В2, ..., Bq) мы будем обозначать множество то-
чек вида
tlBi 4- /гТ?2 4~ . . . 4" tqBq,
где ti, t2, .tq — произвольные неотрицательные
числа.
Что представляет собой геометрически множество
(Bi, В2, .... Вд)? Из определения ясно, что оно яв-
26
ляется суммой множеств (Bi), (В2),	(Bq); по-
этому сначала мы должны выяснить, что представ-
ляет собой множество (В), т. е. множество точек
вида tB, где t — любое неотрицательное число, а В —
фиксированная точка. Но ответ на последний вопрос
очевиден: если В есть начало координат, то и множе-
ство (В) совпадает с началом; в противном случае
(В) есть луч, выходящий из начала координат и про-
ходящий через точку В. Теперь заметим, что сумма
любого множества с началом координат есть снова
Рис. 29.
это же множество; отсюда ясно, что, изучая множе-
ства (Bi, В2, .... Bq), мы ничего не потеряем, если
будем считать все точки Bi, В2, ..., Bq отличными от
начала координат. Тогда множество (Blt В2, ..., Bq)
будет представлять собой сумму лучей (Вг), (В2), ...
(Bq).
Последнее замечание делает почти очевидной сле-
дующую лемму.
Лемма. Множество (Вь ... ,Bq-i, Bq) есть объ-
единение отрезков, соединяющих каждую точку мно-
жества (Bit ..., Bq-i) с каждой точкой луча (Bq).
Строгое доказательство леммы проводится по тому
же плану, что и доказательство аналогичной леммы
из § 3; рекомендуем читателю провести его самостоя-
тельно.
Исходя из леммы, легко вывести, что (Вь В2) есть
угол, прямая или луч (рис. 29, а, б, в). Затем легко
установить, что (Bf, В2, В3) есть одно из множеств:
бесконечная трехгранная пирамида, плоскость, полу-
плоскость, угол, прямая, луч. Теперь становится яс-
ным, что между множествами (Bi, В2, .... Bq) и вы-
пуклыми многогранными конусами должна существо-
вать тесная связь. И такая связь действительно
з*
27
Имеется. Для большей отчетливости сформулируем со«
ответствующие предложения в виде двух теорем.
Теорема 1. Множество (Д, В2, ,Bq) или
совпадает со всем пространством, или же представ-
ляет собой некоторый выпуклый многогранный конус
с вершиной в начале координат.
Что множество (Вь В2, ..., Bq) действительно мо-
жет совпадать со всем пространством, показывает та-
кой пример. Рассмотрим четыре точки В(, В2, В3, Bit
расположенные так, что лучи (Bi), (В?), (В3), (В|)
образуют попарно тупые углы (рис. 30). Каждое из
множеств (Bi, В2, Вз),
-	(Вь В2, В4), (В;, В3, В4),
°*	(В2, Вз, Bi) представ-
ляет собой бесконечную
трехгранную пирамиду
in	с вершиной в начале ко-
£	ординат. Множество
'	(В,, В2, В3, В4), очевидно,
I	содержит каждую из этих
1	пирамид. Но объединение
указанных пирамид сов-
IV	падает со всем простран-
ством!
Рис. 30.	Теорема 2. Любой
выпуклый многогранный
конус с вершиной в начале координат есть множество
вида (Bi, В2, ..., Вд).
Доказательство теоремы 1 мы проведем
лишь в общих чертах. Воспользуемся методом полной
математической индукции. Утверждение теоремы при
q — 1 очевидно. Предположим теперь, что теорема
справедлива для множеств вида (Вь ..., Вд), и, опи-
раясь на этот факт, докажем ее справедливость для
множеств (Bt, ..,, Вд, Bg+i).
По предположению индукции (В); ..., Bq) есть
либо все пространство, либо некоторый выпуклый
многогранный конус в нем. В первом случае доказы-
вать, в сущности, нечего, ибо тогда (Bf, ..., Вд, Вд+1)
есть тоже все пространство. Пусть имеет место второй
случай: (Bit .,., Bq) есть выпуклый многогранный ко-
нус Ж. По лемме множество (Вь ..., Вд, Bq+i) есть
объединение отрезков, соединяющих каждую точку
множества с каждой точкой луча (Bq+i). Но, как
28
было показано ранее, любой выпуклый многогранный
конус Ж есть либо бесконечная выпуклая пирамида,
либо одно из множеств 1—8. Рассмотрев для каждого
из этих случаев указанное выше объединение отрез-
ков, нетрудно убедиться (проделайте это самостоя-
тельно!), что оно либо совпадает со всем простран-
ством, либо снова является выпуклым многогранным
конусом. Итак, теорема верна для множеств вида
(В^, а также верна для (В4..Вд, Bg+i), коль скоро
мы предположим ее справед-
ливой для (Bi....Вд). От-
сюда следует, что теорема вер-
на при любом q.
Доказательство тео-
ремы 2. Пусть Ж — выпук-
лый многогранный конус с вер-
шиной в начале координат О.
Как мы уже говорили, Ж есть
либо бесконечная выпуклая
пирамида, либо одно из мно-
жеств 1—8.
Пусть Ж — пирамида. Вы-
берем на каждом из ее ребер
по одной точке; получим систему
Мы утверждаем, что множество
есть как раз Ж.
точек В\, В2, ..., Вд.
(Bi, В2......Вд) и
Для доказательства рассмотрим какую-либо пло-
скость л, пересекающую все ребра пирамиды Ж. По-
лучим точки B'i, В'2, ..., Вд (рис. 31). Очевидно,
В' -- klBl, В2----- k2B2, . .., Вд -- kgBg, (1)
где klt k2, ..., kg — некоторые неотрицательные числа.
Пусть теперь В — какая-либо точка пирамиды, от-
личная от вершины О. Луч ОВ пересекается с пло-
скостью л в некоторой точке В'. Очевидно, В' принад-
лежит выпуклой оболочке системы В{, В2, ..., Вд,
и поэтому
в'=51в;+я2в2'+ ... +SqB'q,
где St, s2, ..., sg — неотрицательные числа, в сумме
дающие 1. Если теперь учесть (1), то получим
В' = SlklBl + S2k2B2 4" ... + SgkgBq,
29
а если еще учесть, что В' — kB (fe > 0), то найдем,
что
В = tlBl + t2B2 + ... -\-tqBqt
где
s.k,
(t=l, 2,	q).
Итак, мы показали, что любая точка В пирамиды
принадлежит множеству (Вь В2, Bq). Обратное
(т. е. что любая точка множества (Bh В2, ..., Bq)
принадлежит УС} очевидно. Итак, УС совпадает с
(Bi, В2, ..., Bq).
Случай, когда УС есть одно из исключительных
множеств 1—8, разбирается без особого труда; предо-
ставляем его читателю.
§ 5. ОБЛАСТЬ РЕШЕНИЙ СИСТЕМЫ НЕРАВЕНСТВ
С ДВУМЯ НЕИЗВЕСТНЫМИ
Наша задача теперь — дать эффективное описание
всех решений системы линейных неравенств. В на-
стоящем параграфе эта задача решается для систем
с двумя неизвестными х и у. Несмотря на то, что
число неизвестных невелико (всего два), мы поста-
раемся провести анализ таких систем с общих пози-
ций, т. е. так, чтобы полученные при этом результаты
можно было легко перенести на системы с большим
числом неизвестных.
В конечном счете решение любой системы линей-
ных неравенств сводится к решению ряда систем ли-
нейных уравнений. Мы будем рассматривать решение
системы линейных уравнений как нечто простое, как
элементарное действие, и не будем смущаться, если
для реализации предлагаемого метода придется со-
вершать такое действие много раз.
1°. Необходимые леммы. Пусть дана система нера-
венств
U\X + bry + с, ^>0,
а2х +Ь2у +с2 >0,
(1)
amx + bmy + cm^Q.
30
Оказывается целесообразным наряду с ней рассмо-
треть соответствующую систему однородных нера-
венств
ахх + Ь[у 0, '
а2х + Ь2у >0,
(2)
amx + bmy^0, ,
а также соответствующую систему однородных урав-
нений
ахх + Ьху = 0, '
а2х + Ь2у — О,
(3)
W + bmy = 0.
Область решений системы (1) на координатной
плоскости хОу обозначим через Ж, системы (2) — че-
рез Жй, системы (3) — через £. Очевидно,
где символ с: заменяет слова «содержится в» *).
Лемма 1. Имеет место включение
Ж + Ж о сХ
т. е. сумма любого решения данной системы нера-
венств с любым решением соответствующей однород-
ной системы неравенств является снова решением
данной системы.
Доказательство. Пусть А — произвольная
точка из Ж, В — произвольная точка из Жъ- Тогда
справедливы неравенства
а1хА + b\UA + Cj >0,
а2хА + Ь2Уд + с2 >0, и
атхА + ЪтуА + Ст 0
ЩХВ + Ъхув > 0,
а2Хв 4" Ь2ув 0,
атхв + Ьтув > 0.
*) Не следует смешивать символ с с введенным ранее
е — последний употребляется в том случае, когда речь идет о
принадлежности какой-либо точки какому-либо множеству. Если
же хотят записать тот факт, что одно множество является
частью другого, то употребляют символ с.
31
Складывая каждое неравенство, написанное слева,
с соответствующим неравенством, написанным спра-
ва, получим
(к А + ХВ)
а2 (хА + хв)
Ув) + ci
+ ^2 (У А 4~ У в) + С2 О,
ат (ХА 4“ хв) 4”	(УА + Ув) + ст О-
Эти неравенства означают, что пара чисел хА 4“ хв,
У А.+ Ув — координат
Рис. 32.
точки А + В — является реше-
нием исходной системы (1),
т. е. что А + В е Ж. Лемма
доказана.
Лемма 2. 1) Если неко-
торый луч с началом в точке А
целиком принадлежит множе-
ству Ж и Р — произвольная
точка этого луча, то Р — А е
Е= Ж Q.
2) Если некоторая прямая
целиком принадлежит множе-
ству Ж и А, Р — две произ-
вольные точки этой прямой, то
Р — А^З?.
Доказательство 1). Обозначим точку Р — А
через В. Рассматриваемый нами луч состоит из точек
следующего вида:
Д + sB,
(4)
где s — произвольное неотрицательное число (рис. 32).
Любая из этих точек является по условию решением
системы (1), т. е.
ai (ха + sxb) + (Уа + s«/b) + ci 0,
а2 (хл 4- sxB) + b2 (Уа 4- syB) + с2 > 0,
(5)
ат (хд + sxB) + Ьт (уА + syB) + ст > 0.
Рассмотрим, например, первое из этих неравенств.
Оно может быть записано в виде
(Д1Хд + Ь^д + С[) + s (fl\XB -f- Ь[ув) 0.
32
Поскольку это неравенство справедливо при любом
s 0, то коэффициент при s, как нетрудно видеть,
должен быть неотрицательным числом:
а1хв biyB 0.
Аналогично из рассмотрения остальных неравенств
(5) можно получить
ЩХВ ^2Ув 0,
атхв + Ьтув^0,
откуда видно, что точка В принадлежит множе-»
ству Жо.
Доказательство 2) проводится аналогично. Рас-
сматриваемая прямая состоит из точек вида (4), где
s — произвольное число. Поэтому неравенства (5)’
справедливы при любом значении s. Отсюда вытекает,
что в каждом из этих неравенств суммарный коэффи-
циент при s должен равняться нулю, т. е.
aiXB + Ьхув =0,
а2хв +Мв
атхВ + Ьтув — 0.
Следовательно, В е 2Е. Лемма доказана.
Легко видеть, что леммы 1 и 2 справедливы для
систем с любым числом неизвестных.
2°. Случай, когда система неравенств (1) нормаль-
ная. Рассмотрим снова систему неравенств (1) и со-
ответствующую ей систему однородных уравнений (3),
Последняя имеет очевидное решение х = 0, у = 0.
Это решение называется нулевым. Для исследования
системы (1) оказывается важным знать, имеет ли си-
стема (3) также и ненулевые решения. В связи с этим
введем такое
Определение. Система линейных неравенств
называется нормальной, если соответствующая
система линейных однородных уравнений имеет толь-
ко нулевое решение.
Другими словами, система неравенств нормальна,
если определенное выше множество 3? — область
33
решений соответствующей однородной системы урав-
нений — содержит только одну точку (начало коор-
динат).
Разумеется, понятие нормальной системы имеет
смысл при любом числе неизвестных.
Нетрудно показать, что совместная система нера-
венств нормальна тогда и только тогда, когда область
ее решений Ж не содержит ни одной прямой.
Действительно, если система нормальна, т. е. мно-
жество 2? содержит только начало координат, то об-
ласть Ж не содержит прямых — это сразу же следует
из второго утверждения леммы 2. Если система не яв-
ляется нормальной, то множество S содержит по
крайней мере одну точку В, отличную от начала ко-
ординат. Разумеется, все точки вида kB, где k — лю-
бое число, также принадлежат 3? *). Но в таком слу-
чае, какова бы ни была точка Р Ж (а такая точка
обязательно найдется, ибо система совместна и, сле-
довательно, область Ж не пуста), множество всех то-
чек вида РkB (где k— любое число) по лемме 1
принадлежит Ж. Указанное множество, как мы знаем,
есть прямая линия. Значит, в случае, когда система
не нормальна, область Ж содержит прямую. Этим
полностью доказано подчеркнутое выше предложение.
В этом разделе мы изучим область решений си-
стемы (1), предполагая, что эта система совместна
(область Ж не пуста) и нормальна.
Прежде всего, из того факта, что область Ж не
содержит прямых, вытекает, что она обязательно
имеет вершины. В понятие вершины мы вклады-
ваем следующий смысл (близкий к интуитивному по-
ниманию слова «вершина»).
. Вершиной области Ж называется такая точка
области, которая не является внутренней точкой ни
для одного отрезка, целиком лежащего в Ж. Другими
словами, вершина есть точка А е Ж, обладающая тем
свойством, что любой отрезок, принадлежащий Ж и
проходящий через А, должен иметь в этой точке на-
чало или конец (рис. 33, а и б, где точка А — одна
из вершин; на рис. 33,6 область Ж есть отрезок).
*) Если числа х, у, г — координаты точки В—удовлетво-
ряют однородной системе уравнений, то и числа kx, ky, kz-—
координаты точки kB — также удовлетворяют этой системе.
34,
Поясним подробнее, почему интересующее нас вы-
пуклое множество Ж имеет вершины. Если Ж лежит
на прямой, то это либо отдельная точка, либо отре-
зок, либо луч, и существование вершин очевидно. Если
же Ж не лежит на прямой, то рассмотрим границу
этого множества. Она состоит из отрезков и лучей
(полных прямых Ж не
содержит). Очевидно, ко-
нец любого из таких от-
резков и начало любого t/zzzZK /	—
из лучей будут вершина- Р/Ж///
ми Ж.	X/S/s
Нахождение вершин 'yr а)
области Ж не представ-
ляет особого труда. Пре-	Рис. 33.
жде всего заметим, что
t-му неравенству системы (1) на координатной пло-
скости хОу отвечает полуплоскость, граничная пря-
мая которой Ц определяется уравнением	j
atx + &;t/+ Ci = 0 (i = 1, 2, ..., tn).
Очевидно, точка А из области Ж в том и только в том
случае является вершиной, когда она принадлежит
двум различным граничным прямым.
Условимся называть правильной любую подсисте-
му из двух уравнений системы
а\Х +b{y +ci =0, '
а2х +М +с2 =0,
(6)
^тх + Ьту + Ст = 0
при условии, что эта подсистема имеет единственное
решение (х, у).
Из данной выше характеристики вершины выте-
кает теперь следующий способ нахождения вершин
области Ж.
Чтобы найти все вершины, следует найти решения
всех правильных подсистем системы (6) и отобрать из
них те, которые удовлетворяют исходной системе (1).
Поскольку число правильных подсистем не превос-
ходит С!т — числа сочетаний из т по 2, — то и вершин
области Ж не может быть больше. Итак, число вер-
шин конечно.
.35
Замечание. Из сказанного выше вытекает, что
если область X решений нормальной системы не
имеет ни одной вершины, то эта область пуста — си-
стема не имеет решений (несовместна).
Пример 1. Найти все вершины области X, оп-
ределяемой системой неравенств
х + у Аг 1 >0, '
х — 2у — 2^0, ’
2х — у — 4^0. .
Решая подсистемы
х + г/ + 1 = 0, | х + г/ -J- 1 = 0, | х — 2у — 2 = 0,1
х — 2// — 2 = 0, J 2х — г/ — 4 = 0,) 2х — у — 4 = 0 J
(все рни оказываются правильными), находим три
точки:
(О, -1),	(1, -2),	(2, 0),
из которых только вторая и третья удовлетворяют
всем заданным неравенствам. Значит, вершинами об-
ласти X являются точки
Лг(1, -2) и Д2 (2,0).
Вернемся к системе (1). Пусть
Aj, А2, ...» Ар
— все вершины области X. Множество (Ль Аг, ...
..., Ар)—выпуклая оболочка системы точек
Ль А2, ..., Ар — также принадлежит X (ибо X—
выпуклая область!). Но тогда по лемме I и мно-
жество
(Ль Л2, ..., Ар) + Ха
принадлежит X. Покажем, что в действительности эта
сумма совпадает с X, т. е. что справедлива сле-
дующая
Теорема. Если система неравенств нормальна,
то
Г = <ЛЬ Л2, .... Ар) + Х0,	(7)
где Л1, Л2, ..., Лр — все вершины области X.
Доказательство. Пусть Р — произвольная
точка области X, отличная от вершин области. Пря<
36
мая Д1Р пересекает выпуклую область Ж либо по не-
которому отрезку AiA (рис. 34), либо по'лучу с на-
чалом в А1 (рис. 35). Во втором случае Р— At s Жо
(лемма 2), следовательно, Р е Ai + Жо- В первом жё
случае рассуждаем так: если точка А лежит на огра-
ниченном ребре AfAj области Ж (как на рис. 34), то
Р принадлежит выпуклой оболочке точек At, А{, Ajt
если же точка А лежит на неограниченном ребре с на-
чалом в вершине At (рис.
36), то по лемме 1 имеем
<4 е Л; + Ж а, в силу че-
Рис. 36.
го Р е (А1, Д,) + Жо. Та-
ким образом, во всех
случаях точка Р оказы-
вается принадлежащей д
множеству (Дь А2, ... ‘
..., Др)+^0. Теорема
доказана.
Поскольку способ оты-
скания вершин нам уже
известен, то для полного
описания области Ж не
хватает только умения находить область Жо- Послед-
няя представляет собой область решений однородной
нормальной системы (2). К ее описанию мы и пере-
ходим.
3°. Однородная нормальная система неравенств (2).
Каждое из неравенств (2) определяет полуплоскость,
граничная прямая которой проходит через начало ко-
ординат. Общая часть этих полуплоскостей и есть Жо.
37
В данном случае среди граничных прямых имеют-
ся по крайней мере две различные (система (2) нор-
мальна!). Следовательно, Жо либо совпадает с нача-
лом координат (х = О, у = 0), либо есть луч с вер-
шиной в начале координат, либо представляет собой
некоторый угол, меньший 180°, с вершиной в начале
координат. Если мы будем знать две точки Bt и В2,
лежащие на разных сторонах
этого угла (рис. 37), то все
точки угла запишутся в виде
8 = 1^ +t2B2,	(8)
где fi и t2 — произвольные не-
отрицательные числа. Но оты-
скать точки Bi и В2 совсем не-
трудно, если учесть, что каж-
дая из них: а) принадлежит
Рис. 37.	т. е. удовлетворяет систе-
ме (2), и б) лежит на границе
Ж о, т. е. удовлетворяет одному из уравнений (3). Если
Жо есть луч, то вместо (8) имеем
B = tBv,
(9)
где Bi — любая точка этого луча (отличная от на-
чала), a t — произвольное неотрицательное число.
Пример 2. Найти область Жо решений системы
х + У > 0, '
х- 2у>0, ►
(Ю)
2х — у 0,
а также область Ж решений системы примера 1.
Решение. Система (10) нормальна: единствен-
ное решение соответствующей однородной системы
уравнений
х + у = 0, '
х — 2р = 0, 
2х — у = 0 .
(Н)
есть (0, 0).
Выберем какую-либо точку, удовлетворяющую
первому из уравнений (11) (но отличную от (0, 0)),
например, точку С(—1, 1). Простой проверкой убеж-
даемся, что точка С удовлетворяет не всем неравен-
38
ствам (10), следовательно, ни сама она, ни какая-
либо точка луча ОС (отличная от начала О) не при-
надлежат Хо. Рассмотрев точку — С (т. е. точку
(1, —1)), находим, что она принадлежит Хо- Итак,
Вг =(1, —1). Второму уравнению удовлетворяет точ-
ка (2, 1); она тоже является решением системы (10),
так что В2 = (2, 1). Область Хц состоит из точек
(рис. 38)
/1В1 + /2В2 = Л(1, -1) + М2, 1) = :Л + 2/2, —+/2),
где /] и /2 — произвольные неотрицательные числа.
Рис. 39.
Обращаясь к системе неравенств примера 1, мы
замечаем, что соответствующая ей однородная си-
стема неравенств есть как раз (10). По доказанной
выше теореме имеем
•Г = <А, А) + Х,
где Ai(1, —2) и Л2(2, 0)— вершины области X. Итак,
X состоит из точек (рис. 39)
s(l, -2) + (1 -S)(2, 0) + (/, + 2/2, -ti + f2) =
= (2 — s 4”1\ 4- 2/2, — 2s —-f- /2),
где s — любое число из промежутка [0, 1], a ti, /2 —
любые неотрицательные числа.
Пример 3. Найти область решений системы
2х — у^0, "J
— 4x4-2# > 0, >
х-h #>0. J
39
Поступая, как в примере 2, находим только один луч:
B =	2) = (/, 2/)	(/>0)
(рис. 40).
Пример 4. Найти область решений системы
2х — у 0,
x + i/>0, '
— Зх + у 0. 
случае ни одно из урав-
2х — у — 0,
х+«/ = 0,
— Зх + у = 0
Рис. 40. не имеет рещений (кроме (0, 0)),
которые удовлетворяли бы всем за-
данным неравенствам. Область состоит из одной
точки (0, 0)—начала координат.
4°. Случай, когда система неравенств (1) не яв-
ляется нормальной. Это означает, что область реше-
ний 3? однородной системы уравнений (3) содержит
не только начало коорди-
нат. Следовательно, все
уравнения (3) определя-
ют на плоскости одну и
ту же прямую, и эта пря-
мая есть 3?.
Согласно лемме 1 об-
ласть Ж вместе с каждой
своей точкой Р содержит
прямую Р + 3? (прямую,
проходящую через Р па-
раллельно 3?\ Рассмот-
рим какую-нибудь пря-
мую Т, не параллель-
ную 2. Если мы будем
знать, какие точки прямой 0~ принадлежат области
Ж, — множество этих точек обозначим Ж у, — то смо-
жем найти и саму область Ж, ибо тогда Ж — Ж? + 3?
(рис. 41).
Уравнение прямой 9? есть ape + byj = 0. В этом
уравнении один из коэффициентов а^ или bi отличен
40
от нуля; пусть, например, (ч #= 0. Тогда в качестве
прямой 3~, не параллельной 3?, можно взять ось у
(ее уравнение есть х = 0). В этом случае множество
Жг —будем теперь обозначать его Жу — есть часть
оси у, попавшая в Ж. Чтобы найти это множество,
следует положить в системе (1) х = 0. Тогда полу-
чим систему неравенств
biy + c^O,
Ь2У + с2 > 0,
(12)
ЬщУ ('т о
с одним неизвестным у, решить которую не состав-
ляет труда*). Заметим, что множество Жу может
быть или пустым множеством (тогда и Ж пустое),
или точкой, отрезком, лучом (но не всей осью у, ибо
в противном случае Ж есть вся плоскость, что невоз-
можно). Найдя это множество, мы будем знать и об-
ласть Ж, ибо
ж=жУ + &
(13)
(если 3? не параллельна оси у).
Пример 5. Найти область Ж решений системы
х + у — 1 >0,
— х — у + 2 ^0,
2х + 2у + 3 > 0.
Легко «видеть, что данная система не является нор-
мальной и 3? есть прямая
х + у = 0
(не параллельная оси у). Полагая х = 0, получим си-
стему
у-1>0,
- У + 2>0,
2у + 3>0,
*) Заметим, что система (12) (рассматриваемая как систе-
ма неравенств с одним неизвестным) будет уже нормальной.
Действительно, в противном случае соответствующая ей одно-
родная система имела бы некоторое ненулевое решение у*’, но
тогда система (3) имела бы решение (0, у*), не принадлежащее 3?,
4 А» С. Солодовников	41
из которой видно, что Ж у — пересечение Ж с осью у —
есть отрезок с концами С] (0,1) и С2(0,2). Значит,
Ж есть множество точек вида (рис. 42)
(0, у) + (х, — х) = (х, у — х),
где х произвольно, а у — любое число в промежутке
от 1 до 2.
В заключение кратко остановимся на одной теореме, которая
вытекает из полученных выше результатов. В рассматриваемом
нами сейчас двумерном случае
(т. е. когда все происходит на
плоскости) эта теорема не произ-
водит особого впечатления н пра-
вильнее всего было бы рассмат-
ривать ее как отправной пункт
для обобщения на «п-мерный»
случай. Последний изучается в § 7.
Теорема. Любая (непу-
стая) выпуклая многоугольная
область ЗА на плоскости может
быть представлена в виде суммы
Л;, Л2, ..Лр) + (В„ В2, .,В9)_
(U)
Первое слагаемое этой суммы
есть выпуклая оболочка не-
Л2, ..., Ар, а второе — множество
+ tqBq, где tt, t2, tg — произ-
которой системы точек Л],
точек вида /jBj + t2B2 + ..
вольные неотрицательные числа.
Доказательство теоремы может быть проведено в несколько
слов. Рассмотрим систему неравенств, задающую Ж Если эта
система нормальна, то имеет место равенство (7); учитывая,
что в этом равенстве есть одно из множеств вида (Bt, В2),
(В]) или (О) (начало координат), находим, что в случае нор-
мальной системы наше утверждение справедливо. Если система
не является нормальной, то имеет место равенство (13), из ко-
торого также следует представимость ЗА в нужном виде (по-
чему?).
Заметим, что если все точки Ль Л2, ..., Ар совпадают с
началом координат О, то и множество (Л], Л2, ..., Л,,) сов-
падает с О; тогда от суммы (14) остается лишь второе слагае-
мое. В случае, когда точки Bt, В2, ..., В, совпадают с О, мно-
жество (В\, В2, ..., В,) также совпадает с О и от суммы (14)
остается лишь первое слагаемое.
Обратная теорема также имеет место, хотя и с некоторой
оговоркой.
Теорема. Любое множество вида
(Л], Л2, .... Лр) + (Bi, Bi, ..., Bq)
на плоскости есть либо вся плоскость, либо некоторая выпуклая
многоугольная область в ней.
42
Доказательство довольно очевидно. Второе слагаемое, т. е.
область X’o — fBh Вг, .... Вя), есть либо вся плоскость, либо
полуплоскость, либо некоторый угол (меньший 180°), либо луч,
либо точка (начало координат). Первое же слагаемое Х\ ==
= (Ль А?.......Ар) представляет собой некоторый выпуклый
Рис. 43.
многоугольник. Множество Xi + Хо можно получить, подвергая
Ха параллельным переносам на отрезки ОЛ] (где /(i — любая
точка из Xt) н беря объединение полученных множеств
(рис. 43). Легко видеть, что при этом получится или вся пло-
скость (так будет, если Ха— вся плоскость), или некоторая вы-
пуклая многоугольная область в ней.
§ 6. ОБЛАСТЬ РЕШЕНИЙ СИСТЕМЫ
С ТРЕМЯ НЕИЗВЕСТНЫМИ
После обстоятельного анализа, данного в преды-
дущем параграфе, мы можем теперь, при рассмотре-
нии систем с тремя неизвестными, свести необходи-
мую теорию к минимуму.
Наряду с исходной системой
а{х +b{y 4-CjZ Ч-dj >0, ]
+ bmy + cmz + dm~^Q j
мы снова, как в § 5, рассматриваем две системы:
ахх + Ь\у 4- C[Z 0,
О-'щХ 4“ Ь)пУ 4" c-mz 4^ 0
и
а{х + b{y + C[Z — 0,
4“ Ьту -ф cmz 0.
(!)
С!)
(3)
4*
43
Область решений системы (1) снова обозначаем
через Ж, системы (2) — через Жо, системы (3) — че-
рез £. Пользуясь введенной ранее терминологией,
можно сказать, что Ж есть некоторая выпуклая мно-
гогранная область в пространстве, а Жо — выпуклый
многогранный конус. Леммы 1 и 2 из § 5, как уже от-
мечалось, остаются в силе и здесь.
1°. Случай, когда система неравенств (1) нормаль-
на. Тогда область Ж не содержит прямых и, следова-
тельно, имеет хотя бы одну вершину. В самом деле,
если Ж лежит в плоскости (а такой случай возможен,
как отмечалось в § 2), то Ж — выпуклая многоуголь-.
ная область на плоскости, не содержащая прямых, и
поэтому, как объяснено в разделе 2° § 5, обязана
иметь вершины. Если же область Ж не лежит в пло-
скости, то рассмотрим ее границу. Она состоит из
плоских граней, каждая из которых — как выпуклая
многоугольная область, не содержащая прямых, —
должна иметь вершины. Но легко видеть, что вершина
любой грани является одновременно и вершиной об-
ласти Ж,
В каждой вершине А области Ж сходятся по край-
ней мере три граничные плоскости, для которых точка
А является единственной общей точкой. В самом деле,
если бы это было не так, то все граничные плоскости,
проходящие через А, или совпали бы, или имели бы
общую прямую. Но тогда достаточно малый отрезок,
проходящий через А и лежащий в общей граничной
плоскости или на общей граничной прямой, принад-
лежал бы Ж, что противоречит определению вер-
шины.
Сказанное выше заставляет нас внести очевидные
изменения в способ отыскания вершин, описанный
в разделе 2° § 5. А именно, правильной подси-
стемой теперь следует называть подсистему не из
двух, а из трех, уравнений системы
+ b\y + C[Z + d{ =0,
amx + bmy + cmz + dm = 0,
(4)
при условии, что решение (х, у, z) этой подсистемы
единственно. При таком понимании правильной под-
44
системы способ отыскания вершин остается в точно-
сти тем же, что и раньше, а именно:
Чтобы найти все вершины области Ж, следует
найти решения всех правильных подсистем системы
(4) и отобрать среди них те, которые удовлетворяют
исходной системе (1).
Сохраняет силу и теорема раздела 2° § 5; измене-
ния, которые необходимо внести в доказательство этой
теоремы, очевидны. Замечание о том, что нормальная
система в случае отсутствия вершин у области Ж не
имеет решений, также остается справедливым.
Пример 1. Найти вершины области Ж, опреде-
ленной с помощью системы неравенств
2х	у	z —	1	0,	'
х 4“ 2 у	4“	2 —	1	О,
х	У	2г —	1	>	О,
х +	у-\-	z—	1	>	0.
(5)
В данном случае соответствующая однородная си-
стема уравнений имеет вид
2х 4“ у 4~ 2 — 0, '
х 4- 2у 4- z = 0,
х 4- У + 2г = 0,
х4- У + 2 = 0. )
Решая ее, убеждаемся, что единственное решение
есть (0, 0, 0) — система (5) нормальна.
Для нахождения вершин нам придется рассмотреть
всевозможные подсистемы из трех уравнений си-
стемы (4):
2х 4- у 4- г — 1 = 0,
х 4- 2у 4- г — 1=0,
х 4- у 4- 2г — 1 = 0; .
2х 4- У 4- z—l=0,
х 4- у 4- 2г — 1 = 0,
х4- У+ 2—1=0; .
2х 4- у 4- г — 1 —• 0,
х 4" 2у 4" 2 — 1 = 0,
х 4- У + г—1=0;
х 4~ 2у 4- г — 1=0,
х 4- У 4- 2г — 1 = 0,
х4- у + г—1=0.
45
Проделав необходимые вычисления, найдем, что
все подсистемы правильны, и их решениями являются
точки
(4> Т’т)- (°> °, о. (0.1.0), (1,0,0),
из которых первая не удовлетворяет системе (5),
а остальные три удовлетворяют. Следовательно, вер-
шины области Ж~.
А (1,0,0), А2 (0,1,0), Л3 (0,0,1).
2°. Нормальная однородная система неравенств
(2). Каждое из неравенств (2) определяет полупро-
странство, граничная плоскость которого проходит
через начало координат.
В'данном случае пересечением граничных плоско-
стей является единственная точка — начало коорди-
нат (система (2) нормальна!). Другими словами,
множество Жо — область решений системы (2) — есть
выпуклый многогранный конус с единственной вер-
шиной. Из данного в § 4 перечисления выпуклых мно-
гогранных конусов следует, что в нашем случае Жо
есть либо бесконечная выпуклая пирамида, либо пло-
ский угол, либо луч, либо, наконец, одна точка (на-
чало координат). Последний случай оставим пока
в стороне. Во всех остальных случаях имеем
Хо = (В1, В2....Bq),
где Bi, В2, ..., Bq — какие-либо точки, выбранные по
одной на каждом ребре конуса Жо (см. теорему 2 § 4).
Найти такие точки можно, исходя из следующего со-
ображения. Каждая из них: а) принадлежит Жо, т. е.
удовлетворяет системе (2), и б) принадлежит линии
пересечения двух различных граней, т. е. удовлетво-
ряет двум непропорциональным *) уравнениям из си-
стемы (3).
*) Уравнения ах + by + cz = 0 и а'х + Ь'у + с'г = 0 мы
называем «непропорциональными», если не выполнено хотя бы
а b с
одно из равенств = -р- = в этом случае соответствую-
щие плоскости пересекаются по прямой.
46
Если окажется, что единственная точка, удовлетво-
ряющая условиям а) и б), есть (0, 0, 0), то область
Жй совпадает с началом координат.
Пример 2. Найти область Жй решений системы
2х + У + 2^0, '
х+2у+ г>0,
х 4- у 4- 2z 0,
х4- у+ г>0
(6)
и далее область Ж решений системы из примера 1.
Прежде всего заметим, что система (6) связана
с системой неравенств (5) из примера 1; именно, (6)
есть однородная система, отвечающая (5). Следова-
тельно, система (6) нормальна.
В данном случае систему из двух непропорцио-
нальных уравнений можно составить шестью различ-
ными способами:
х + 2у4- 2 = 0,1 2x4- у4~ 2 = 0,1 2х 4- 1/4- 2 = 0,1
х4- y4-2z = 0;J х4- г/4-2? = 0; ) х-\-у+ z = 0; J
2x4- #4- 2 = 0,1 х4-2у4- 2 = 0,1 х 4-J/4-2z = 0,1
х 4“ 2у4“ 2 = 0*, J Х4- у-4- 2 = 0; J х 4~ У~1~ 2 = 0. )
Для каждой из этих шести систем выбираем два не-
нулевых решения: (х, у, z) и (—х, —у, —z). Напри-
мер, для первой системы можно взять (3, —1, —1) и
(—3, 1, 1); неравенствам (6) удовлетворяет только
первое из этих решений. Отсюда получаем точку В,—
= (3, —1, —1). Поступая аналогично с остальными
пятью системами, находим точки В2 = (—1, 3, —1) и
В3 = (—1, —1, 3). Итак, область Жй состоит из то-
чек вида
tiBi -|- t2B2 4- t3B> =
— (3/i —12 —t2, —1\ 4- 3/q — 6, — /i — /2 4" 3/>),
где /i, /2, h — произвольные неотрицательные числа.
Обратимся теперь к системе неравенств (5) из
примера 1. Соответствующая ей однородная система,
как уже отмечалось, есть как раз (6). Следовательно,
область Ж имеет вид
(Л[, А2, Аз) 4"
47
и состоит из точек
SjXi -f- s2A2 -|- з3Л3 -|- tlBl + /гВ2 + /3В3 “
= Sj (1, 0, 0) + s2 (0, 1, 0) + s3 (0, 0, 1) +
+/i(3, -1, - 1) + /2(- 1, 3, - l) + /3(- 1, -1, 3)=
= (si + 3/] — t2 — is, s2 t\ + З/2 /3, $з — t\ — t2 + 3/3),
где числа ti, /2, /3 произвольные неотрицательные,
a si, s2, s3 неотрицательны и в сумме дают 1.
3°. Случай, когда система неравенств (1) не яв-
ляется нормальной. Это означает, что область реше-
ний £ однородной системы уравнений (3) содержит
точки, отличные от начала координат. Так как £
представляет собой пересечение плоскостей, то воз-
можны два случая:
1. £ есть прямая. Согласно лемме 1 область Ж
вместе с каждой своей точкой Р содержит прямую
Р + £. Рассмотрим какую-нибудь плоскость £, не-
параллельную £. Если мы будем знать, какие точки
плоскости £ принадлежат области Ж — множество
этих точек обозначим Ж ,т, — то сможем найти и саму
область Ж, ибо тогда Ж = Ж? + £.
Но, какова бы ни была прямая £, в качестве
непараллельной ей плоскости £ всегда можно вы-
брать одну из координатных плоскостей хОу, xOz
или yOz. Допустим, например, что £ не параллельна
плоскости yOz. Примем эту плоскость за £’. В этом
случае множество Ж? — будем обозначать его теперь
Жу,г— есть часть плоскости yOz, попавшая в Ж
(рис. 44). Чтобы найти это множество, следует по-
48
ложить в системе (1)х = 0. Тогда получим систему
неравенств *)
Ьгу +c,z +d, >0,
^тУ Ч~ 4~	0,
которую можно решить методом, изложенным в § 5.
Найдя множество Ж г, сможем записать
^’ = ^,г + -2’
(8)
(если прямая S не параллельна плоскости yOz), что
и дает полное описание области Ж.
Замечание. Если окажется, что множество
Жу,г пустое, то и Ж пустое. Это означает, что си-
стема (1) несовместна.
Пример 3. Найти область Ж решений системы
— 2х -[-	у	z	—	1 0,
— Зх —	у	+ 4z	—	1 0,	*
— х —	2у	4-3z	>0.	,
(9)
Рассмотрим соответствующую однородную систему
уравнений	
— 2х + у + 2 = 0,
— Зх — у + 4z = 0, 
— х — 2у + 3z = 0. .
(Ю)
Решая ее, обнаруживаем, что третье уравнение есть
следствие первых двух, так что система сводится
к первым двум уравнениям. Множество ее решений S,
есть прямая, по которой пересекаются плоскости
— 2х + У + z = 0
— Зх — у + 4z = 0.
Выберем какую-нибудь точку В на прямой S, от-
личную от начала координат. Для этого достаточно
найти какие-нибудь три числа х, у, z (не равные од-
*) Система (7), как нетрудно видеть, будет уже нормальной
(см. аналогичную сноску на стр. 41),
49
повременно нулю), удовлетворяющие первым двум
уравнениям системы (10). Возьмем, например, 1, 1, 1.
Итак, 3? есть прямая ОВ, где В — (1, 1, 1).
Легко видеть, что прямая 2? не параллельна, на-
пример, координатной плоскости yOz. Полагая в си-
стеме (9) х = 0, получим систему
tj+ z — 1>0,
- г/ + 4з- 1>0,
— 2 у Л- 32	0
с двумя неизвестными у и г, которая нормальна. Об-
ласть ее решений Жу, г можно найти методом, изло-
женным в § 5. Проделав необходимые вычисления,
найдем, что Ж,. г есть множество, состоящее из одной
(3	2 \
у, -д-1 (в плоскости yOz). Следовательно,
искомая область Ж состоит из всех точек вида
Л + /В=(о,|, 4) + /(1, 1, 1)=(/, |+/, 4+/),
где t — любое неотрицательное число (область Ж есть
прямая, параллельная 3?).
2. 3? есть плоскость. Тогда в качестве секущего
множества Ж берем какую-нибудь прямую, не парал-
лельную этой плоскости; в частности, можно взять
одну из координатных осей. Допустим, например, что
ось г не параллельна 3?\ примем ее за Ж. Чтобы
найти множество Жт — часть оси г, попавшую в Ж,—
следует положить в системе (1) х = 0, у = 0. Тогда
получим систему неравенств
o,z + d, >0,
Ст? &т
о,
(11)
которая решается без особого труда*). Найдя мно-
жество Жг, сможем записать (рис. 45).
Ж-=Жг + 3?	(12)
(если плоскость 3? не параллельна оси г), что и дает
полное описание Ж.
*) Система (11) является нормальной.
50
Замечание. Если множество Жг окажется пу-
стым, то и Ж пустое. В этом случае система (1) не*
совместна.
Пример 4. Найти область Ж решений системы
х— г/ + 2 + 1 > О, 4
— х + у — z + 2 0. )
(13)
В данном случае соответствующая однородная си-
стема уравнений имеет вид
х — г/ + 2 = 0, |
— х-\- у — 2 = 0. )
(14)
Здесь второе уравнение есть
следствие первого, поэтому
область решений системы (14)
есть плоскость S’, определяе-
мая уравнением
х — у + 2 = 0.
Легко видеть, что эта пло-
скость пересекает ось 2 в един-
ственной точке и, следователь-
но, не параллельна оси 2. Най-
дем множество Жг-
Рис. 45.
стему
Полагая в системе (13) х = 0, у = 0, получим си-
z+1
-2 + 2
>0,
>0,
из которой следует, что
-1<2<2.	(15)
Итак, Ж есть множество Жг + S, состоящее из точек
вида (0, 0, 2) + (х, у, —х + у) = {х, у, z — х + у), где
х и у произвольны, а 2 удовлетворяет неравенст-
вам (15).
Мы заканчиваем этот параграф формулировкой двух теорем,
представляющих собой обобщение двух последних теорем § 5
на трехмерный случай. Единственное изменение, которое следует
внести для этого в формулировки упомянутых теорем § 5, со-
стоит в замене слова «плоскость» словом «пространство».
Теорема. Любая (непустая) выпуклая многогранная об-
ласть в пространстве может быть представлена в виде суммы
(А, Д2, .... Ар) (Bi, В2, ..., Bq).
51:
Теорема. Любое множество вида
(Ат А2..............Ар) + (BY, В2,..., Вч)
в пространстве есть либо все пространство, либо некоторая вы-
пуклая многогранная область в нем.
Доказательства обеих теорем почти дословно повторяют до-
казательства соответствующих теорем в двумерном случае. Пре-
доставляет читателю детально провести эти доказательства.
§ 7. СИСТЕМЫ ЛИНЕЙНЫХ НЕРАВЕНСТВ
С ЛЮБЫМ ЧИСЛОМ НЕИЗВЕСТНЫХ
В предыдущих параграфах мы сосредоточили свое
внимание на системах неравенств с двумя или тремя
неизвестными. Такое ограничение диктовалось в ос-
новном двумя обстоятельствами: во-первых, тем, что
исследование этих систем несложно и целиком укла-
дывается в рамки «школьной» математики; во-вторых
(и это в данном случае более существенно), тем, что
решения таких систем имеют наглядный геометриче-
ский смысл (точки на плоскости или в простран-
стве). Однако в приложениях (например, к вопросам
линейного программирования) чаще встречаются си-
стемы неравенств с числом неизвестных п > 3. Обой-
ти их молчанием значило бы сильно обеднить изло-
жение вопроса. Поэтому мы постараемся хотя бы
кратко рассказать, как обстоит дело при любом
п > 3.
Для геометрического истолкования системы линей-
ных неравенств с п неизвестными нам необходимо об-
ратиться к так называемому «-мерному про-
странству.
Начнем с определения соответствующих понятий,
причем ограничимся лишь самым необходимым.
Точка «-мерного пространства по оп-
ределению задается упорядоченным набором из «
чисел
, %2> • • • > Хп,
называемых координатами точки. Мотивом к по-
добному определейию является тот основной для ана-
литической геометрии факт, что точка на плоскости
характеризуется парой чисел, а в пространстве —
тройкой чисел. В дальнейшем вместо того, чтобы го-
ворить «точка М имеет координаты Xi, Хг,, хп», мы
52
будем писать М = (хь х2, .... х„) или просто
М (xi, х2, ..., хп). Точка (0, 0,	, 0) называется н а-
чалом координат или просто началом.
Прежде всего укажем, что понимается под «отрез-
ком» в n-мерном пространстве. Согласно § 1, в обыч-
ном пространстве отрезок ЛТ1Л12 может быть охарак-
теризован как множество всех точек вида
SjAfi + s2M2,
где Si, S2 — любые два неотрицательных числа, даю-
щие в сумме 1. Переходя от трехмерного пространства
к n-мерному, мы принимаем эту характеристику за
определение отрезка. Точнее, пусть
М' (х(, Х2, .... Хп) и М" (х{, х", .... Хп)
—две произвольные точки n-мерного пространства.
Тогда отрезком М'М" называется множество всех
точек вида
s'M' + s"M" =
= (s'x' + S"x'[, s'x2 + s"x".s'x'n + s"x"),	(1 )
где s', s" — любые два неотрицательных числа с сум-
мой 1. При s' = 1, s" = 0 мы получаем точку М',
при s' = 0, s" = 1 — точку М". Это — концы отрезка
М'М". Остальные точки (они получаются при s' > 0,
s" > 0) называются внутренними точками отрезка.
Из дальнейших понятий, относящихся к п-мерному
пространству, нам понадобится понятие гиперпло-
скости. Это — обобщение понятия плоскости в обыч-
ном трехмерном пространстве. Приставка «гипер»
имеет здесь вполне определенный смысл. Дело в том,
что в n-мерном пространстве возможны «плоскости»
различных типов: одномерные «плоскости» (они назы-
ваются «прямыми линиями»), двумерные «плоскости»
и т. д., наконец, (п— 1)-мерные «плоскости»; послед-
ние и носят название «гиперплоскостей».
Определение. Гиперплоскостью в п-мер-
ном пространстве называется совокупность точек
M(xi, х2, . .., хп), координаты которых удовлетворяют
уравнению первой степени
а^ + а2х2 + ... + апхп + b = 0,	(2)
где хотя бы одно из чисел at, а2, ..., ап (коэффициен-
тов при неизвестных) отлично от нуля. При п = 3
53
уравнение (2) принимает вид O|.Yi + а2х2 + а3х3 + Ь~
= 0 — это есть не что иное, как уравнение плоскости
в обычном пространстве (где координаты обозначены
Xi, Хг, х3, а не х, у, z, как обычно).
По отношению к гиперплоскости (2) все п-мерное
пространство разбивается на две части: область, в ко-
торой выполняется неравенство
«[X] + а2х2 + ... + апхп + b 0,	(3)
и область, в которой
а{хх + а2х2+ ... + апхп + Ъ < 0.	(4)
Эти области называются полупространствами.
Таким образом, каждая гиперплоскость разбивает все
пространство на два полупространства, для которых
она является общей частью.
Понятие выпуклого тела также обобщается на
n-мерный случай. Множество точек в n-мерном про-
странстве называется выпуклым, если вместе
с любыми двумя своими точками М' и М" оно содер-
жит и весь отрезок М'М".
Нетрудно показать, что любое полупространство
является выпуклым множеством. В самом деле, пусть
точки М'(х', х', х'п) и М"(х'', х2, ..., х'п) принад-
лежат полупространству (3). Докажем, что и любая
точка М отрезка М'М" также принадлежит этому по-
лупространству.
Координаты точки М представляются в виде (1)
или, что то же самое, в виде
Xi = sxi + (1 — s)x7,
=	+ (!-«)<.	(0<5<1).
= + 0 ~s>x"n
Подставляя эти выражения в левую часть (3), по-
лучим
а{ (sx' + (1 — s) х") + а2 (sx' + (1 — s) х") + ...
...+Ms< + (i “«) + *==
— s (а{х[ + a2x'2 + ... + anx'n) +
+ (1 — s) (ajX" 4- a2x" + •.. + artx") + sb + (1 — s) b
54
(мы заменили число b суммой sb + (1 — s) Ь), что
равно
s |>Х+ • • • +aX+ft] + 0 ~ [aix" + • • • + Vn+b].
Каждая из двух сумм, заключенных в квадратные
скобки, неотрицательна, поскольку обе точки М' и М"'
принадлежат полупространству (3). Следовательно, и
все написанное выражение неотрицательно (ведь s
^Ои (1 — s) > 0). Этим доказано, что точка М при-
надлежит полупространству (3), т. е. что это полупро-
странство выпукло.
После всего сказанного нетрудно понять, какая
геометрическая терминология должна соответствовать
системе линейных неравенств с п неизвестными. Пусть
дана система
«Л + а2х2 + ... + ctnxn + а 0, ]
&1Л?! + ^2 + • • . + ЬпХп + Ь 0,
СЛ + с2х2 + ... -t- спхп -f- с > 0. )
Каждое из написанных неравенств определяет некото-
рое полупространство, а все написанные неравенства
совместно — некоторую область Ж в «-мерном про-
странстве, являющуюся пересечением конечного числа
полупространств. Область Ж является выпуклой, так
как выпукло любое из образующих ее полупро-
странств.
По аналогии с трехмерным случаем мы называем
область в п-мерном пространстве, являющуюся пере-
сечением конечного числа полупространств, выпук-
лой многогранной областью, а в случае,
когда это пересечение является ограниченным множе-
ством, — просто выпуклым многогранником.
Здесь слова «ограниченное множество» следует пони-
мать в том смысле, что координаты всех точек рас-
сматриваемой области не превосходят по абсолютной
величине некоторой постоянной с:
|xt|< с, ..., |xn| С с для всех точек данной области.
Итак, совокупность точек п-мерного пространства,
координаты которых удовлетворяют системе (5), есть
выпуклая многогранная область Ж, получающаяся
в результате пересечения всех полупространств, отве-
чающих неравенствам данной системы.
55
Отметим еще раз, что если эта область ограничена,
то мы .называем ее выпуклым многогранником.
Методы фактического описания области УС, кото<
рые мы рассмотрели в § 5 для систем с двумя неиз«
вестными и в § 6 для систем с тремя неизвестными,
с соответствующими изменениями переносятся на слу-
чай п неизвестных. Останавливаться, однако, на этом
мы не будем, так как исчерпывающее изложение по-
требовало бы довольно много места. К тому же при
большом числе неизвестных эти методы становятся
малоэффективными: их использование связано с че-
ресчур громоздкими вычислениями.
Замечательно, что общие теоремы о строении выпуклых
многогранных множеств в трехмерном пространстве полностью
сохраняют силу в «-мерном пространстве, хотя доказательства
усложняются. Ограничимся только формулировками этих теорем
и необходимыми пояснениями к ним.
. Теорема 1. Выпуклая оболочка любой конечной системы
точек Л1; Л2, .... Лр является выпуклым многогранником.
Для большей отчетливости подчеркнем, что здесь устанав-
ливается связь между двумя различно определенными типами
множеств: выпуклой оболочкой системы точек Ль Л2, ...,ЛР,
которая обозначается (Ль Л2....Ар) и определяется как мно-
жество всех точек вида
Sj Aj + з2Л2 + ... + SpAp,
где Sj, s2, ..., sP — любые неотрицательные числа, дающие в
сумме 1, и выпуклыми многогранниками, т. е. ограниченными
областями, получающимися в результате пересечения конечного
числа полупространств.
В двумерном и трехмерном пространствах справедливость
теоремы 1 очевидна (хотя бы из наглядного смысла выпуклой
оболочки), в многомерном же случае совсем не очевидна и тре-
бует доказательства.
Теорема 1' (обратная к 1). Любой выпуклый многогран-
ник совпадает с выпуклой оболочкой некоторой конечной систе-
мы точек.
В действительности можно утверждать даже большее: вы-
пуклый многогранник совпадает с выпуклой оболочкой своих
вершин. Определение вершины — то же самое, что н в двумер-
ном случае (вершина есть такая точка многогранника, которая
не является внутренней точкой ни для одного отрезка, целиком
принадлежащего многограннику). Можно показать, что число
вершин всегда конечно.
Теорема 2. Любое множество вида (В,, В2.......Bq) либо
совпадает со всем пространством, либо представляет собой не-
который выпуклый многогранный конус с вершиной в начале ко-
ординат.
Напомним, что символ (Blt В2, ..., Bq) обозначает множе-
ство всех точек, представимых в виде
tiBi + t2B2	tgBq,
66
где ti, t2....— любые неотрицательные числа. Выпуклый
многогранный конус определяется как пересечение конечного
числа полупространств, граничные гиперплоскости которых
имеют общую точку (вершину конуса). Справедливость теоре-
мы 2 в трехмерном пространстве была установлена в § 4 (тео-
рема 1 § 4).
Теорема 2'. Любой выпуклый многогранный конус с вер-
шиной в начале координат может быть представлен как
(В1, В2....Bq).
Справедливость для трехмерного случая была доказана
в § 4 (теорема 2 § 4).
Теорема 3. Любая выпуклая многогранная область мо-
жет быть представлена в виде суммы
(Ai> А2,..Ар) + (Bi, В2, ..., Bq).
Теорема 3'. Любая сумма указанного вида есть или все
пространство или некоторая выпуклая многогранная область
в нем.
§ 8. РЕШЕНИЕ СИСТЕМЫ ЛИНЕЙНЫХ НЕРАВЕНСТВ
ПУТЕМ ПОСЛЕДОВАТЕЛЬНОГО УМЕНЬШЕНИЯ ЧИСЛА
НЕИЗВЕСТНЫХ
Из курса алгебры средней школы читателю изве-
стен метод решения системы линейных уравнений, за-
ключающийся в последовательном уменьшении числа
неизвестных. Для системы, содержащей три неизвест-
ных х, у, z, сущность этого метода можно описать сле-
дующим образом.
Из каждого уравнения данной системы выражаем
неизвестное z через неизвестные х и у. Затем полу-
ченные выражения (куда входят только х и у) при-
равниваем друг другу. Получаем новую систему—•
с двумя неизвестными х и у. Например, если исходная
система была
2х — Зу + z — — 1, '
х — у + 2г = 5,
4г/ — z = 5,
(1)
то, разрешив каждое уравнение относительно z, по-
лучим
z = — 2х + Зу — 1, '
1	1 1	। 5
2 -	2 %	2	2 ’ *
(1')
г =
4г/ — 5;
57
приравняв затем выражения, стоящие в правых частях
(достаточно первое из указанных выражений прирав-
нять по очереди каждому из остальных), получим си-
стему
-2х + 3у-1 = -|х + 4у+|, )
22	2 ?	(2)
— 2х + Зу — 1 =	4у — 5 )
с двумя неизвестными х и у. К системе (2) можно
применить тот же прием: из уравнений (2) находим
3.7s
У— + I
5	5	>	(2')
у = — 2х + 4, )
после чего получаем уравнение
3 I 7	п . .
-5*+ -5-= — 2х + 4
уже с одним неизвестным х. Решив это уравнение,
находим х = 1, после чего из системы (2х) находим
у = 2 и, наконец, из системы (Iх) получаем z = 3.
Оказывается, что нечто подобное можно проделать
и с любой системой линейных неравенств. Решение
системы неравенств с п неизвестными xit ..., xn-i, хп
сводится таким путем к решению системы неравенств
сп — 1 неизвестными xit ..., xn-i, затем полученная
система может быть сведена к системе с п — 2 неиз-
вестными xi, ..., хп-2 и т. д., пока не придем к системе
неравенств с одним неизвестным xt. А решение си-
стемы с одним неизвестным — задача вполне элемен-
тарная. Таким путем мы получаем возможность найти
(по крайней мере в принципе) любое решение исход-
ной системы неравенств.
Итак, пусть дана система линейных неравенств
с п неизвестными Xi, Х2, ..., х„ — в дальнейшем для
удобства ссылок будем называть ее «система (S)».
При рассмотрении системы (S) возникает ряд во-
просов: будет ли система совместной; если да, то как
найти все ее решения; как устроены несовместные
системы неравенств? На все эти вопросы ответ будет
дан здесь и в следующем параграфе. При этом ока-
зывается очень полезным связать с каждой системой
линейных неравенств новую систему, в которой число
58
неизвестных на единицу меньше,.чем в исходной си-
стеме,— эту новую систему мы называем сопутст-
вующей.
Перейдем к ее описанию.
Рассмотрим любое из неравенств системы (S). Оно
имеет вид
щхх + а2,г2 + ... 4- апхп + а > 0.	(3)
Если ап = 0, то оставим это неравенство без измене-
ния. Если ап < 0, то перенесем член апхп в правую
часть и разделим обе части неравенства на положи-
тельное число — ап-, получим неравенство вида
^1Х1 + ••• + Ьп-1хп-1 + Ъ хп.
В случае ап > 0 перенесем в правую часть неравен-
ства все слагаемые, кроме апхп, и разделим обе части
на ап\ получим неравенство
хп щхх 4" •" • 4-	1 4-
Итак, умножив каждое из неравенств исходной си-
стемы на подходящее положительное число, получим
равносильную ей систему вида
Хп Q1,
Хп -5s Qa>
Хп Qq>
Rr>®,
59
где Pi, .,,, Р-р, Qi, .. t, Qg, Ri, (,,, 7?r суть выражения
вида ал + • • • + a.n-i.xn-i + а (не содержащие xn) *).:
Систему (T) можно записать короче:
Ра хп^ Qfp "I
tfY>o, J
чи-
(S')
чи-
где а — любое из чисел 1, 2, .,., р, р — любое из
сел 1, 2, ..., q, у — любое из чисел 1, 2, ..., г.
Рассмотрим наряду с системой (Г) систему
Ра )
Ry О /
(где а — любое из чисел 1, 2, ..., р, р — любое из
сел 1, 2, q, у — любое из чисел 1, 2, . . .
сп— 1 неизвестными Xi, ..., xn-i **). Условимся на-
зывать эту систему сопутствующей (по отношению
к исходной системе (S) или равносильной ей си-
стеме (Г)).
Между решениями систем (S) и (S') существует
тесная связь. Выражением этой связи служит сле-
дующая
Теорема. Если от любого решения системы (S)
отбросить значение последнего неизвестного хп, то по*
лучим некоторое решение сопутствующей системы (S').
Обратно, для любого решения сопутствующей си-
стемы (S') можно найти такое значение неизвестного
хп, присоединив которое, получим решение исходной
системы (S).
Первое утверждение теоремы очевидно (если ка-
кой-нибудь набор значений неизвестных удовлетво-
ряет системе (S), то он удовлетворяет и системе (Т)\
но тогда для этого же набора выполняются и все не-
равенства системы (S')). Докажем второе.
*) Разумеется, если в системе (S) нет ни одного неравен-
ства, в котором ап <0, то в системе (Т) не будет первого
блока. Аналогично, если отсутствуют неравенства с ап > 0, то
в системе (Г) не будет второго блока. Наконец, если в (S) нет
неравенств с ап = 0, то в (Т) отсутствует третий блок.
**) Если окажется, что в системе (Г) первый или второй
блок отсутствует, то (S') будет состоять только из неравенств
Ру 0. Если в (Г) отсутствует третий блок, то в (S') будут
только неравенства Ра Qp.
60
Пусть
Х1 Х<1’ •••’ Хп-1 Хп-1
.— какое-нибудь решение системы (S'). Подставив
указанные значения неизвестных в выражения Pit ...
.... Рр, Qi, • • •, Qq, Ri, .... Rr, получим некоторые
числа PJ, .... Р°р, Q°lt .... Q°q, R°v R°r. Для них
должны выполняться неравенства
P°a>Q°&	Н)
(а— любое из чисел 1, 2......р, а р— любое из чи-
сел 1, 2, ..., q),
Pv > О	(5)
(у —любое из чисел 1, 2,	г).
Первая группа написанных неравенств (т. е. (4))
показывает, что каждое из чисел Q°, .не боль-
ше, чем любое из чисел P°t........Р°. Но в таком
случае обязательно найдется число х°п, которое за-
ключено между всеми числами Q®, ..., Q® и всеми
Г}0	Г10
числами Р[9 ..Рр:
p^^QI
где а — любое из чисел 1, 2, р, а р — любое из
чисел 1, 2, .... q (рис. 46). Но эти неравенства вместе
гу, О
-
*  О——О	О х О' —О " 0—0------
Q! Р° Р,° Р° Р,°-
Рис. 46.
с неравенствами (5) означают, что набор значений
неизвестных
X. у 0	у	—— у 0	у  уО
1 I ’	’ Ai 1 rt— 1’ п п
является решением системы (Г), а следовательно, и
(S). Теорема доказана.
Следующие два добавления к теореме будут иг-
рать дальше важную роль.
1. Система (S) линейных неравенств совместна
тогда и только тогда, когда совместна сопутствующая
61
ей система (S'). Это — прямое следствие доказанной
теоремы.
2. Все решения исходной системы (S) могут быть
получены следующим способом: нужно к каждому
решению х°, ..., сопутствующей системы (S') при-
соединить любое из чисел х°п, заключенных между
всеми числами Q°.....Q°q и всеми числами Р°.....Р°р,
Это предложение фактически было доказано в ходе
доказательства теоремы.
Скажем несколько слов о геометрическом смысле доказан-
ной выше теоремы. Допустим, что (S) — система неравенств
с тремя неизвестными х, у, г. Сопутствующая система (S') есть
система с двумя неизвестными х, у. Обозначим через X(S)
область решений системы (S) (это — некоторое множество то-
чек в пространстве) и через Ж (S')—область решений систе-
мы (S') (множество точек иа плоскости). Доказанная теорема
в переводе на геометрический язык означает следующее.
Область Ж (S') есть проекция области Ж (S) на координат-
ную плоскость хОу.
Итак, для произвольной системы (S) линейных не-
равенств с неизвестными х1у х2, ..., хп мы построили
новую, сопутствующую систему (S'), в которой неиз-
вестными являются xiy х2, ..., хп-1. Но для системы
(S') можно, в свою очередь, построить сопутствую-
щую систему (S") (с неизвестными х2, •••, хп_2),
для последней — сопутствующую систему (S'") и т. д.
Продолжая этот процесс, мы после ряда шагов при-
дем к системе (S<n-!>), состоящей из неравенств с од-
ним неизвестным хь Из указанного выше предложе-
ния 1 вытекает, что система (S) совместна в том и
только в том случае, когда совместна система (S<n-1)).
Но решить вопрос о совместности или несовместности
системы с одним неизвестным не представляет ника-
кого труда. Таким образом, мы получаем возмож-
ность при помощи весьма простых вычислений узнать,
совместна система (S) или нет.
Допустим, что система совместна. Тогда возникает
задача — решить систему или, говоря более подробно,
указать все ее решения (все наборы значений неиз-
вестных, для которых выполняются неравенства дан-
ной системы). Мы станем на следующую точку зрения
(хотя вначале она покажется читателю странной):
система (S) решена, если построены системы (S'),
62
(3"),	(S(n-1)). Чем объясняется такая точка зре-
ния, мы сейчас увидим, но сперва введем одно
Определение. Набор значений первых k не-
известных
уО уО	уО
Л1> Л2, . . .,
называется допустимым, если его можно продолжить
до решения исходной системы (S), т. е. если суще-
ствуют такие числа x°k+i, ..., х°п, что набор x°s, ...
..., х%, x°k+l, ...,х°п является решением системы (3).
Как только построены системы (S'), (З") и т. д.,
мы получаем возможность:
1)	найти все допустимые значения неизвестного xt
(из системы (3<п~й));
2)	для любого конкретного допустимого значения
х° найти все совместные с ним значения неизвестного
Хг, т. е. такие значения, которые вместе с х® образуют
допустимый набор (они находятся путем подстановки
х® в систему (S<"~2>);
3)	для любого конкретного допустимого набора
х®, х® найти все совместные с ним значения неизвест-
ного х3 (они находятся путем подстановки xf и х®
в систему (S<n-3))) и т. д.
Именно в этом смысле и следует понимать наше
утверждение, что система (3) решена, если построены
системы (S'), (S"), ..., (S<n-1)).
Пример. Решим в указанном смысле систему
7х + 2у — 2z — 4	0, >
— х— у— z + 4^0,
— 2х ~|~ Зу	z — 1	О,
5х — у + z -j- 2	0.
Разрешив каждое неравенство системы относи-
тельно z, запишем систему в виде
j х + у — 2 > z,
— х — y + 4^z,
(6)
2х — Зу + 1,
z > — 5х + у — 2.
63
Сопутствующая система имеет вид
jx + y —2> 2х — Зу+1,
ух + у —2> —5х+ У —2,
— х —1/4-4^ 2х —Зг/4-1,
— х — у + 4^ — 5х + у — 2
или, после приведения подобных членов,
х + 4у - 3> О,
17
~2Х	>0,
— Зх 2у ~4* 3	0,
4х — 2у 4- 6 0.
Разрешив каждое неравенство относительно у,
запишем эту систему в виде
3.3)
У>-Тх + ^
3	3
у> ~2Х~~~2’ 
2х -}- 3	z/,
х >0.
(7)
Система, сопутствующая этой, имеет вид
2x + 3>-iJ + |,
2х + 3> |х-’, '
х^> 0;
она равносильна одному неравенству
х > 0
(8)
Итак, исходная система совместна. Согласно при-
нятой нами точке зрения, системы (8), (7), (6) дают
решение поставленной задачи. Именно, неравенство
,(8) показывает, что существует решение (х, у, г) ис-
ходной системы с любым неотрицательным х. Если
выбрано конкретное значение х, то из системы (7)
64
можно найти возможные значения для у. Если вы<
браны конкретные значения для х и у, то из системы
(6) найдутся возможные значения z.
Положим, например, х = 1; тогда из системы (7)’
получим следующие неравенства, ограничивающие у\
т-
Возьмем, например, у — 4. Полагая
х — 1, у = 4, получим неравенства,
в системе (6)'
ограничиваю'
щие z\
или просто
Полагая, например, z = — 2, получим одно из реше-
ний исходной системы: х = 1, у = 4, z = — 2,
§ 9. НЕСОВМЕСТНЫЕ СИСТЕМЫ
До сих пор нас интересовали преимущественно та-
кие системы неравенств, которые имели хотя бы одно
решение (были совместны). Что касается несовмест-
ных систем, то их изучение представляется, на первый
взгляд, ненужным занятием; к тому же кажется ма-
ло правдоподобным, чтобы с такими системами можно
было связать сколько-нибудь содержательную теорию.
В действительности же дело обстоит совсем иначе:
свойства несовместных систем не только представляют
интерес сами по себе, но и дают ключ к пониманию
целого ряда важных фактов. Так, например, основная
теорема линейного программирования (теорема двой-
ственности, см. § 14) выводится в конечном счете из
некоторых свойств несовместных систем.
Рассмотрим произвольную систему линейных нера-
венств. Для удобства записей будем пока считать, что
число неизвестных равно трем, хотя все сказанное
в равной мере будет относиться к системам с любым
числом неизвестных.
65
Итак, дана система
4~ Ь^у -(- C\Z 4- d,	О,
а2х + Ь2у + c2z + d2	О,
атх + bmy + cmz 4- dm^O.
(1)
Умножим, обе части первого из неравенств (1) на
какое-либо неотрицательное число kiy обе части вто-
рого — на неотрицательное число k2 и т. д., а затем
полученные неравенства сложим. В результате мы
придем к неравенству
(^i^i 4" /г2я2 4-
+ (&А + k2b2 4
4" (fejCj + k2c2 4~
4~ kyi} -J- k2d2 4-
+ bnlam) x +
4~ knb'J) у +
4“ 'V.ii) 4”
4“ kmdm 0,
(2)
которое будем называть комбинацией нера-
венств (1).
Может случиться, что некоторая комбинация не-
равенств (1) представляет собой неравенство вида
0-x4-0-z/4-0-z4-d>0,	(3)
где d—строго отрицательное число (после деления
на |d| получается тогда неравенство —1 1>0). Ясно,
что никакой набор значений неизвестных такому не-
равенству удовлетворять не будет, поэтому в рассма-
триваемом случае система (1) несовместна (не имеет
решений). Весьма замечательно, что справедливо и
обратное предложение, а именно: если система (1)
несовместна, то некоторая комбинация ее неравенств
имеет вид (3), где d < 0.
Это предложение мы докажем сейчас в общем виде
(т. е. для систем с любым числом неизвестных), по
прежде введем такое определение. Условимся
называть неравенство
ах 4- by 4- cz 4- d 0
противоречивым, если ему не удовлетворяет ни
один набор значений неизвестных. Очевидно, любое
66
противоречивое неравенство имеет вид (3), где d < О
(докажите это!). Предложение, которое мы должны
доказать, можно теперь сформулировать в виде сле-
дующей теоремы.
Теорема о несовместных системах не-
равенств. Если система линейных неравенств не-
совместна, то некоторая комбинация этих неравенств
есть противоречивое неравенство.
Доказательство проведем индукцией по п —<
числу неизвестных в нашей системе.
При п = 1 система имеет вид
а}х + О,
а2*+ ^2^0,
(4)
атх 4“ Ьт О'
Можно считать, что все коэффициенты alt а2, .,.
.. ., ат отличны от нуля. Действительно, если, напри-
мер, «1 — 0, то первое неравенство имеет вид 0-х+
+ bi 0; если число Ь{ неотрицательно, то такое не-
равенство можно отбросить, если же Е отрицательно,
то первое неравенство нашей системы противоречиво,
и доказывать нечего.
Итак, будем считать, что ни одно из чисел
ai, а2, • • •, ат не равно нулю. Легко видеть, что среди
этих чисел обязательно должны быть как положи-
тельные, так и отрицательные: в самом деле, если бы
все указанные числа имели один и тот же знак, на-
пример, были положительны, то система (4) приво-
дилась бы к виду
и, следовательно, была бы совместной.
Предположим, для определенности, что первые k
из чисел «1, «2, ..., ат положительны, а остальные
т — k отрицательны. Тогда система (4) равносильна
системе
(5)
Ьъ
— наибольшее;
ak
например, таким является —Тогда в си-
6Z1
(5) первые k неравенств могут быть заменены
лишь первым неравенством. Аналогично среди
-----—,		выберем наименьшее, тогда
ak+l	ат
пусть,
стеме
одним
чисел
остальные т — k неравенств системы (5) могут быть
заменены одним лишь последним неравенством. Та-
ким образом, система (4) равносильна системе из
двух неравенств:
х
Ь\ '
ai ’
Ьщ
в-т 9 '
и ее несовместность означает, что
(6)
«1 ат	’
Из (6) вытекает
Ьта{ — Ь{ат < 0	(7)
(следует учесть, что tzi > О и ат < 0). Если теперь
первое из неравенств (4) умножить на положительное
число — ат, а последнее — на положительное число
ai, а затем произвести сложение, то получится нера-
венство
О • х + (Ьтах — Ь{ат) О,
(8)
68
которое в силу (7) является противоречивым. Итак,,
для систем с одним неизвестным теорема справед*
лива.
Предположим теперь, что утверждение теоремы
справедливо для систем неравенств с п— 1 неизвест-
ными, и в этом предположении установим его спра-
ведливость для случая п неизвестных.
Итак, пусть дана несовместная система линейных
неравенств с п неизвестными Хч, ..., хп; придер-
живаясь обозначений предыдущего параграфа, назо-
вем ее «система (S)». Построим для нее сопутствую-
щую систему (S'); последняя будет несовместна вслед
за (S). Поскольку число неизвестных в системе (S')
равно п—1, то к ней применимо предположение ин-
дукции. Это означает, что некоторая комбинация не-
равенств системы (S') представляет собой противо-
речивое неравенство. Но нетрудно видеть, что каждое
неравенство системы (S') является комбинацией не-
равенств из (S): действительно, если просто сложить
неравенства Ра хп и хп Qp системы (S), то по-
лучим Ра + хп хп + Qp или Ра Qp, т. е. одно из
неравенств системы (S') (см. § 8, системы (Т) и (S')),
Отсюда, в свою очередь, вытекает, что некоторая ком-
бинация неравенств исходной системы (S) есть про-
тиворечивое неравенство. Теорема доказана.
Теорема о несовместных системах линейных
неравенств — лишь одно из проявлений глубокой ана-
логии, которая существует между свойствами систем
линейных неравенств и свойствами систем линейных
уравнений. Попробуем заменить в формулировке тео-
ремы слово «неравенство» словом «уравнение». Полу-
чится следующее предложение:
Если система линейных уравнений несовместна, то
некоторая комбинация этих уравнений есть противоре-
чивое уравнение.
Оказывается., это предложение тоже справедливо.
В несколько иной формулировке оно носит название
теоремы Кронекера— Капелли и доказы-
вается в курсе линейной алгебры (так назы-
вается раздел математики, в котором изучаются ли-
нейные операции, т. е. операции, подобные сложению
точек и умножению точки на число в n-мерном про-
странстве). Впрочем, для правильного понимания ска-
занного выше необходимо внести уточнение в понятие
69
комбинации. Комбинация уравнений’строится тем же
путем, что и комбинация неравенств, с той только
разницей, что разрешается умножать данные уравне-
ния на какие угодно, а не только неотрицательные
числа. Противоречивым, как и в случае неравенств,
называется уравнение, не имеющее решений. Нетруд-
но показать, что противоречивое уравнение обяза-
тельно должно иметь вид
О • Х\ 4~ 0 • %2 4~ • • • 4" о  хп 4- Ь — о,
(9)
где b — число, отличное от нуля (после деления обеих
частей на b получаем «уравнение» 1 =0).
Особо важным является один частный случай тео-
ремы о несовместных системах неравенств, а именно,
когда данная система содержит неравенства
Хг^О, . .х„^0.
(Ю)
Обозначив остальную часть системы через (S), можно
сказать, что задача состоит в отыскании всех Неотри-
цательных (т. е. удовлетворяющих условиям (10)) ре-
шений системы (S). Если эта задача не имеет реше-
ний, то, согласно только что доказанной теореме, не-
которая комбинация неравенств системы (S),
4” а2х2 + • • • + апхп 4* а 0,
(Н)
в сумме с некоторой комбинацией неравенств (10),
йрГ] + k2x2 + ... + knxn 0
(/гь k2, kn неотрицательны),
дает противоречивое неравенство
0 • X] -|- 0 • ,v2 4* • • • 4- 0 • 4- с > 0,
где с — отрицательное число. Следовательно,
й1 = —ki <0, а2 = — k2 < 0......ап = — kn < 0,
а <' 0.
Сформулируем полученный результат в виде от-
дельного предложения.
Следствие из теоремы о несовместных
системах. Если система неравенств не имеет неот-
рицательных решений, то некоторая комбинация этих
неравенств есть неравенство вида (11), где все коэф-
фициенты ai, а2, ..., ап 0, а свободный член а < 0.
70
§ 10. ОДНОРОДНАЯ СИСТЕМА ЛИНЕЙНЫХ НЕРАВЕНСТВ.
ФУНДАМЕНТАЛЬНЫЙ НАБОР РЕШЕНИЙ
В § 8 мы рассмотрели способ нахождения решений
системы линейных неравенств. При всех очевидных
достоинствах этого способа некоторые вопросы ре-
шить с его помощью нельзя; например, указанный
способ не позволяет обозреть множество всех реше-
ний данной системы неравенств. Именно этой цели и
посвящены ближайшие два параграфа нашей книжки.
Основные трудности, как мы увидим, связаны с рас-
смотрением однородных систем — этой задаче посвя-
щен настоящий параграф; общий же случай (т. е. не-
однородная система неравенств) разбирается в § 11.
При этом нет особой необходимости ограничивать себя
случаем двух или трех неизвестных: с самого начала
мы будем рассматривать систему из любого числа не-
равенств с любым числом неизвестных. Для удобства
читателя разобьем изложение на ряд пунктов.
Г. Линейная функция от п аргументов. Общий
вид однородного неравенства с п неизвестными есть
арсх + а2х2 + ... + апхп 0.
Рассмотрим отдельно выражение
+ а2х2 + ... + апхп,	(1)
стоящее в левой части неравенства. Это выражение
называется линейной функцией. Роль аргументов иг-
рают п переменных Xi, х2, ..., х№. Впрочем, можно
считать, что функция (1) зависит не от п аргументов,
а от одного: этим аргументом является точка
X = (Х1, Х2, ... , Хп)
«-мерного пространства.
Условимся в дальнейшем функцию (1) обозначать
кратко L(X):
L(X) = a^Xi -f- a2x2 -p . .. -f- anxn',
если же задана не одна такая функция, а несколько,
то будем обозначать их Ll(X), L2(X) и т. д.
Установим следующие два свойства линейной
функции.
1.
L(kX)=kL(X),
где X — любая точка, a k — любое число.
71
2.
L(X + Y)=L(X)^L(Y),
где X и Y — любые две точки.
Свойство 1 очевидным образом следует из равен*
ства
«1 (kxi) + a2(kx2) 4-... -j-an (kxn) =
= k (GtlXl 4* #2X2 4~, • • • .+. anxn)<
Докажем теперь свойство 2. Пусть
X = (Xi, х2....хп) и У = (г/ь у2, ..., уп) .
Тогда
L (X 4- У) = (xj 4- У1) 4* а2 (х2 + У2) + • • <
• •. 4~ ап (хп 4- Уп) — (ал 4- а2х2 4~ •• • 4- апхп) 4*
4-	(<21У1 4- й2у2 4- • • • 4- апУп) — Т (X) 4- Т (Y).
2°. Некоторые свойства решений однородной си-
стемы линейных неравенств. Пусть дана однородная
система m линейных неравенств с п неизвестными:
a]Xi 4-4-	••• 4-я„хп^0	(1-е	неравенство),	Т
Ьрц 4- Ь2х2 4-	• •  4- Ьпхп 0	(2-е	неравенство),	I
СЛ 4- с2х2 4-	•••4- СпХп^®	(т-е	неравенство).	)
Обозначив левые части неравенств соответственно
Li(X), L2(X), Lm(X), перепишем данную систему
в виде
А(Х)>о, л
l2 W>o, I	(2)
im(x)>o, J
где
X = (xlt х2, .... хп).
Установим следующие два предложения.
1. Если точка X есть решение системы (2) и k—•
любое неотрицательное число, то точка kX есть снова
решение системы (2).
72
2. Если X и Y — два решения системы (2), то
X + Y есть снова решение системы (2).
Оба предложения легко следуют из доказанных
в п. 1° свойств линейной функции. Действительно,
пусть i — любой из номеров 1, 2, .... tn. Имеем
Ll(kX) = kLi (Х)>0
(ибо k 0 и Ц (X)	0), а также
Lt (X + Y) = Lt (X) + Li(Y)^Q
(ибо Li (X)	0 и Li (У)	0).
Из предложений 1 и 2 непосредственно вытекает
такое следствие.
Если некоторые точки Xlt Х2, ..., Хр являются ре-
шениями системы (2), то и любая точка вида
k\X^ + ^2-^2	kpXp,	(3)
где ki, k2, ..., kp — неотрицательные числа, тоже яв-
ляется решением системы (2).
Действительно, каждая из точек &Л, k2X2, ...
..., kpXp в силу предложения 1 является решением
системы (2), но тогда и сумма этих точек в силу пред-
ложения 2 будет решением системы (2).
Условимся называть любую точку вида (3), где
ki, fe, ..., kp — неотрицательные числа, неотрицатель-
ной комбинацией точек Xi, Х2, ..., Хр. Тогда указан-
ное выше следствие будет допускать такую формули-
ровку.
Неотрицательная комбинация любого числа реше-
ний однородной системы (2) есть снова решение этой
системы.
3°. Фундаментальный набор решений. Введем та-
кое определение.
Набор из конечного числа решений
Хг, х2....хр
однородной системы (2) называется фундаменталь-
ным набором решений, если любое решение X этой
системы может быть задано формулой
X = k{Xi + k2X2-\- ... + kpXp,	(4)
где k^ k2, ..., kp — неотрицательные числа. В этом
случае, следовательно, формула (4), в которой
ki, k2,	—любые неотрицательные числа, дает
73
обозрение всех решений системы (2). Отсюда ясно,
что нахождение фундаментального набора решений
есть задача первостепенной важности при исследова-
нии системы (2). Конечной целью наших построений
и будет как раз являться выработка алгоритма, по-
зволяющего с помощью весьма простых операций на-
ходить фундаментальный набор решений для любой
системы (2).
4°. Построение фундаментального набора для си-
стемы, состоящей из одного неравенства. Построим
фундаментальный набор решений для неравенства
а2х2 + . •. + апхп 0,	(5)
где числа аи а2, ... ,ап не равны одновременно нулю.
Для этой цели рассмотрим наряду с неравенством
{5) уравнение
ai-^i + a2-^2 + ... + апхп = 0.	(6)
Из свойств линейной функции, доказанных в п. 1°,
дегко вытекают следующие два предложения:
1. Если X — какое-нибудь решение уравнения (6)
и k — любое число, то kX— снова решение уравне-
ния (6).
2. Если X и У— два решения уравнения (6), то
X + У есть снова решение уравнения (6).
Доказательства предоставляем читателю.
По условию, среди чисел а2, ..., ап имеются не
равные нулю. Положим, например, что ап =# 0. Тогда
уравнение можно записать в виде
хп~—(alxt + а2х2 + ••• + an-A~l)- (6')
“Л
Полагая Xj = l, х2=0, ..., хп-\ — ^, найдем из послед-
него уравнения хп — —Таким образом, точка
ап
%, = (.. о,..., О, -£)
является решением уравнения (6). Аналогичным об-
разом можно получить решения
^=(«•1.......»-£)•
Xn-t = (о, О, .... 1, -
74
Пусть теперь
X = (ait а2, .. ., а„_ь а„)	(7)
— любое решение уравнения (6). Имеем, согласно (6'),
“п =— ~ (а1а1 + а2а2 +	+ an-l“n-l)==
“Л
(fll \ I /	02 4 !	I	(	&П — 1 \
~ —) + «2 (—“I- ••• +а»-1( а )’
/ X Un /	х ап /
Рассматривая точку
aIXI+«2-^2+ ••• 4~“n-lXl-l =
....-z-)+<°-1..........-£)+•••
... 4-а»-, (О, 0.. I,
убеждаемся, что ее координаты совпадают с коорди-
натами точки X. Поэтому справедливо равенство
X —	-|- а2%2 + ••• + “п-1^п-р	(8)
Добавим теперь к построенным ранее точкам Xlt
Х2.....Xn-i еще одну:
Хп =— (Xi + Х2 + ••• + Х^).	(9)
Из указанных в начале этого пункта свойств решений
уравнения (6) следует, что точка Хп тоже является
решением. Теперь нетрудно доказать следующий
факт: любое решение X уравнения (6) является не-
отрицательной комбинацией решений Хи Х2, ...
. •., Хп—1, Хп.
В самом деле, пусть a — положительное число,
превосходящее любое из чисел |ai|, |а2\, .... |an-i|-
Из (8) и (9) следует
X — (а, + a) Х\ + (а2 + а) Х2 + ...
• • • 4~ (“п-i + “) Xn-i -|- аХп,
что и служит доказательством нашего утверждения.
Для краткости дальнейших записей обозначим ле-
вую часть уравнения (6) через L(X). Выберем какое-
нибудь решение уравнения L(X) = 1 и обозначим это
решение Xn+i- Мы утверждаем, что набор точек
Х{> Х2, Хп-Ь Хп, Xn+i	(10)
75
является фундаментальным набором решений для не-
равенства (5),
В самом деле, каждая из указанных точек удовле-
творяет неравенству (5). Пусть теперь X' — любое ре-
шение этого неравенства; следовательно, L(X')=a,
где а 0. Тогда точка
Х = Х'-аХп+{
удовлетворяет уравнению (6), ибо
L(X) = L(X')-aL(X^==a-a - 1=0.
Если теперь записать
Х' = Х + аХп+1
и учесть, что точка X является неотрицательной ком-
бинацией точек Xi, ..., Xn~i, Хп, то станет ясно, что
X' представима в виде неотрицательной комбинации
точек (10).
Рассмотрим конкретный пример. Пусть требуется
построить фундаментальный набор решений для не-
равенства
— 2xs — 4х2 + х3>0	(И)
с тремя неизвестными xj, х2, х3.
Прежде всего записываем уравнение
— 2%1 — 4х2 + х3 = 0
и разрешаем его относительно одного из неизвестных,
например, х3:
х3 — 2Х( -|- 4х2.
Теперь последовательно полагаем одно из неизвест-
ных Xi, Х2 (входящих в правую часть уравнения) рав-
ным 1, а остальные нулю. Получаем такие решения!
Х( = (1,0,2),	Х2 = (0, 1, 4).
Далее, в качестве Х3 берем точку
Х3 = -(Х1 + Х2) = (-1, -1, -6)
и, наконец, за Xt принимаем одно из решений урав-
нения
— 2xi — 4х2 + х3 = 1,
например, Л4 = (0, 0, 1).
76
Точки Xlt Х2, Х3, Xj, образуют фундаментальный
набор решений для неравенства (11). Общее решение
имеет вид
X — k[Xi 4* ^2-^2 4" кзХз 4* кцХц =
=&,(!, О, 2)4-й2(0, 1,4) + ^з(-1,-1, ~6)4-М0, 0. 1)
или
Xi — kl k3,
х2 = k2 — k.3,
Х3 =	4- 4&2 — 6А?з 4- ki,
где ki, /г2, k3, ki — произвольные неотрицательные
числа.
5°. Перестройка фундаментального набора реше-
ний при добавлении к системе еще одного неравен-
ства. Чтобы научиться строить фундаментальные на-
боры решений, рассмотрим вначале такую задачу.
Пусть дана однородная система
Ц (Х)>0,
l2QO>o,
Lm(X)>0
(12)
линейных неравенств. Пусть, далее, известен фунда-
ментальный набор решений
Хъ х2,.... хр
для этой системы. Требуется построить фундамен-
тальный набор решений для системы, полученной до-
бавлением к (12) еще одного неравенства
£(Л)>0.	(13)
Решения системы (12)—это в точности все неот-
рицательные комбинации точек Х>, Х2, ..., Хр. Среди
этих комбинаций нам нужно выбрать такие, которые
удовлетворяли бы неравенству (13) и, более того, со-
ставили бы фундаментальный набор решений для си-
стемы (12), (13).
По отношению к функции L(X) —левой части не-
равенства (13)— все точки Xi, Х2, ..., Хр можно раз-
бить на три группы: точки, для которых £(Х)> 0,
точки, для которых L(X)<0 и, наконец, точки, для
77
которых L(X)=0. Точки первой группы обозначим
Х^, X*, •»., Xk, точки второй группы — Xf, Х2, ...
..., ХГ, точки третьей группы — X?, Х°............ Х°.
Таким образом,
v”b	v+ v~	v~*	vO
Л1 ,	Л/г , Л1,	Л/ ,	Ль	As
— это те же	самые точки	Xi, Х2,	• • •,	Хр, но	только
расположенные, может быть, в другом порядке.
Разумеется, все точки Ха (а=1, ..., k) удовле-
творяют неравенству (13). То же самое относится и
к Ху (у = 1, ..., s). Что же касается точек Х$ (р =
= 1..../), то из них ни одна не является решением
неравенства (13). Однако, из каждой пары
X*, X?
(одна точка «плюсовая» и одна «минусовая») можно
образовать неотрицательную комбинацию
аХ* + ЬХ&	(14)
так, чтобы она удовлетворяла условию £(Х)= 0. Для
этого следует взять
a = -L(Xf), 6 = L(xJ). (15)
Действительно, числа а и b положительны в, кроме
того,
L (аХ* + ЬХ^) = aL (xj) + bL (Хр ) =
= -L (XB~) L (Xj) + L (Xj) L (XB) = 0.
Обозначим точку (14), где а и b имеют указанные
выше значения, через Х°в:
Х°е==-£(Хё)х+ + £(х+)Хв-.	(16)
Ответ к поставленной нами задаче дает следующая
Теорема. Точки
v+	v'b v0	vO v0	v0	v0	/1*7\
Ai , . .	Л/г , A i,	. .	A$, Ai i,	A [2,	. . Akl	UI )
(всего здесь записано k + s + kl точек) образуют
фундаментальный набор решений для системы
(12), (13).
78
Чтобы доказать теорему, установим сначала та-
кую лемму.
Лемма. Любая неотрицательная комбинация то-
чек Ха и Xq может быть представлена как неотри-
цательная комбинация точек Xt, ^ав или же как не-
отрицательная комбинация точек Хд,
Доказательство леммы. Пусть
X = cXt + dX$
— неотрицательная комбинация точек Ха и Х$. Рас-
смотрим наряду с X точку
XQa& = aXi + bXt,
где числа а и Ь определены формулами (15). Сравним
два отношения: у и у. Если первое больше вто-
d с
рого, то, полагая -у = А, — = %4-р, где ц>0, будем
иметь:
X = (Ха + ра) Ха + ХЬХ$ = л4в +
т. е. точка X представима в виде неотрицательной
комбинации Ха и Если указанные выше отно-
шения равны, то X = ЛХаВ- Наконец, если -у < -у, то,
с d
полагая — = X, -у = Л + ц, где ц > 0, получим
X = ЛХаВ + ц&Ав •
Лемма доказана.
Доказательство теоремы. Прежде всего
заметим, что каждая из точек (17) удовлетворяет си-
стеме (12), (13). Поэтому, чтобы доказать теорему,
нам остается лишь проверить следующее: если какая-
то точка X является решением системы (12), (13), то
она представима в виде неотрицательной комбинации
точек (17).
Будучи решением системы (12), точка X представ-
ляется в виде неотрицательной комбинации ее фунда-
ментальных точек Xi, Х2....Хр:
X-aiXi'-}- ... a,iXt + b\Xi + ...
• • • + biXi + CiX[ + ... -f-	(18)
79
где все коэффициенты alt .... <щ, &ь ..., bi, clt ..., cs
неотрицательны.
Если все числа bi, ..., bi равны нулю, то, очевидно,
доказывать нечего. Предположим поэтому, что среди
указанных чисел имеются строго положительные. За-
метим, что тогда среди чисел ai, ..., ah тоже имеются
строго положительные: в противном случае получи-
лось бы
L(X) = bi	... + biL (Xi ) + C\L (x?)	...
... +csLW),
что невозможно, так как X удовлетворяет неравен-
ству (13).
Допустим, для определенности, что at > 0 и bi > 0.
Пользуясь леммой, можно заменить сумму б^Х^+^ХГ"
неотрицательной комбинацией точек X*, Х°ц или же
точек Xf, Хп. Если в выражении для точки X про-
извести такую замену, то общее число отличных от
нуля коэффициентов при X*.........X*, Xf, ..., XT
уменьшится по крайней мере на 1. Если при этом
окажется, что во вновь полученном выражении для X
не все коэффициенты при XT, • ••, XT равны нулю,
то снова заменим одну из сумм вида aXt + ЬХТ не-
отрицательной комбинацией точек Х„, Х% или же
точек XT, Х°а&; в результате число отличных от нуля
коэффициентов при XT, ..., Xt, XT, ..., XT умень-
шится еще по крайней мере на 1. Так будет про-
должаться до тех пор, пока для точки X не полу-
чится выражение, в котором все коэффициенты при
XT, XT будут равны нулю. Мы придем тогда
к равенству вида
X = 611X1*" + . . . + а*Хй + 2 ^а₽Хар +
а, Р
+ С]Х? + ... + CsXs,
где все коэффициенты справа больше либо равны
нулю. Но это и есть требуемое представление для X.
Теорема доказана.
80
60. Существование и способ построения фундамен-
тального набора решений. Рассмотрим произвольную
систему однородных линейных неравенств. Для пер-
вого неравенства системы можно (способом, описан-
ным в п. 4°) построить фундаментальный набор ре-
шений. Присоединив к первому неравенству второе,
можно, опираясь на теорему п. 5°, построить фунда-
ментальный набор решений для системы, состоящей
из первых двух неравенств. Далее присоединяем
третье неравенство и т. д., пока не получим фунда-
ментальный набор решений для всей исходной си-
стемы неравенств. Этим доказано существование и
одновременно указан способ построения фундамен-
тального набора решений.
Разумеется, если в данной системе неравенств
имеется подсистема, для которой сразу можно ука-
зать фундаментальный набор решений, то в качестве
исходного пункта следует взять эту подсистему; при-
соединяя к ней последовательно остальные неравен-
ства, мы после ряда шагов построим искомый фунда-
ментальный набор.
Пример. Для системы
Л W — — Зх] — 4х2 + 5х3 — 6x4 0,
Z.2 (ЙЭ ==	2х[ Ч" Зх2 — Зх3 -|- Х4 0 /
требуется найти все неотрицательные решения, т. е.
все решения, удовлетворяющие условиям
Xi^O, '
х2>0,
х3>0,
х4^0. .
(20)
Иначе говоря, нужно найти общее решение системы
(19), (20).
Нетрудно видеть, что для системы (20) фундамен-
тальным набором будет являться набор из точек
Х1 = (1, 0, 0, 0), Х2 = (0, 1, 0, 0),
Х3 = (0, 0, 1, 0), Х4 = (0, 0, 0, 1)
$1
(действительно, любое решение (аз, аг, аз, а4) си-
стемы (20) представимо в виде а4Хз + агХ2 + а3Х3 ~Н
+ «Л). Присоединим к системе (20) первое из не-
равенств (19) и для полученной таким образом си-
стемы построим фундаментальный набор решений,
используя теорему п. 5°. Для удобства вычислений
составим такую таблицу:
					L1 (X)
	1	0	0	0	-3
х2	0	1	0	0	-4
Хз	0	0	1	0	5
	0	0	0	1	-6
В каждой строке таблицы указана одна из фун-
даментальных точек для системы (20), а также зна-
чение функции Li(X) для этой точки. Из таблицы
видно, что единственной точкой типа Ха является Х3,
точки типа XjT суть Хь Х2, Х4, а точек типа Х$
в данном случае нет.
Находим точки типа Х^. Ими будут:
Х?1 = ЗХз + 5Х1 = (5, 0, 3, 0),
Хзг = 4Х3 + 5Х2 = (0, 5, 4, 0).
Х34 = 6Х3 + 5Х4 = (0, 0, 6, 5).
Чтобы не усложнять дальнейших записей, обозначим
эти точки У1, Y2, Yi (соответственно), а вместо Х3 бу-
дем писать У3.
Точки У3, Уз, У2, У4 образуют фундаментальный
набор решений для системы, состоящей из (20) и пер-
вого из неравенств (19).
82
Присоединяем к этой системе второе из неравенств
(19) и составляем следующую таблицу:
					/-2 (У)
Уз	0	0	1	0	—3
У1	5	0	3	0	1
у2	0	5	4	0	3
У<	0	0	6	5	-13
Из таблицы видно, что роль точек Ya теперь играют
Yx, ^2, роль точек Ур" играют У3, У4, а точек типа У у нет.
Находим точки типа У°в:
У?з = ЗУ1 + У3 = (15, 0, 10, 0) = 5(3, 0, 2, 0),
У°3 = ЗУ2 + ЗУ3 = (0, 15, 15,.0) = 5(0, 3, 3, 0),
У°4=13У1 + У4 = (65, 0, 45, 5) = 5 (13, 0, 9, 1),
У«4=13У2 + ЗУ4 = (О, 65, 70, 15) = 5(0, 13, 14, 3)
Точки Уь У2, У?з, Угз, У?4, У24 образуют фундамен-
тальный набор решений для системы (19), (20). Общее
решение имеет вид
X = aYi + &У2 + cY°i3 + dy23 + сУ ?4 + f У24 =
= я(5, 0, 3, 0) + Ь(0, 5, 4, 0) + 5с(3, 0, 2, 0) +
+ 5d(0, 3, 3, 0) + 5е(13, 0, 9, 1) + 5/(0, 13, 14, 3),
где а, Ь, с, d, е, f — какие угодно неотрицательные
числа.
Если положить а = kx, b = k2, 5с = k3, 5d = kit
5е = /г5, 5f = k&, то получим для X представление
X = kx (5, 0, 3, 0) + k2 (0, 5, 4, 0) + k3 (3, 0, 2, 0) +
+ МО, 3, 3, 0) + М13, 0, 9, 1) + МО, 13, 14, 3), (21)
где klt k2, k6 — произвольные неотрицательные
числа.
83
В заключение этого пункта отметим, что, доказав существо-
вание фундаментального набора решений для любой однородной
системы линейных неравенств, мы тем самым доказали теоре-
му 2' из § 7 о строении любого выпуклого многогранного ко-
нуса (см. стр. 57).
§ 11. РЕШЕНИЕ НЕОДНОРОДНОЙ СИСТЕМЫ НЕРАВЕНСТВ
Теперь, когда мы научились строить общее реше-
ние однородной системы неравенств, не составляет
труда решить аналогичную задачу для произвольной,
т. е. неоднородной, системы неравенств.
Пусть
а1х1 + а2х2 + ... +	> а, '
Ml + Ь2х2 + ... 4- Ьпхп Ь, ,
0-^1 “Ь а2Х2 "4" • • • 4” апХп
— произвольная система линейных неравенств с п
неизвестными Xi, х2....хп. Рассмотрим наряду с ней
однородную систему
fljXj “Ь а2Х2 4- • • • + апХп — at О, '
Mi 4- Ь2х2 4- ... 4" Ьпхп — bt^Q, f (2^
CjXi 4~ с2х2 4- ... 4- спХп. — ct^Q
с п 4-1 неизвестными хь х2, ..., хп, t.
Между решениями систем (1) и (2) имеется опре-
деленного рода связь. А именно, если xt, х2, ..., хп,
t — какое-либо решение системы (2), причем t > 0, то
числа
у ____ Xl у _________ Хг	s ____ Хп
*1	> Х2 ----- I > г . Хп —	(о)
будут составлять решение системы (1) .
В самом деле, рассмотрим, например, первое из
неравенств (2). Оно выполняется для чисел xlt х2, ...
..., хп, t, т. е.
al^l + а2Х2 4- ... 4- апхп at.
Разделив обе части неравенства на положительное
число t, будем иметь
Mi + а2х2 4- ... 4" апхп а,
84
НО это означает, что набор чисел xit х2, .... удо<
влетворяет первому из неравенств (1). Аналогичной
рассуждение можно провести для любого из нера-
венств (2), откуда и следует наше утверждение.
Нетрудно видеть, что любое решение системы (1)
может быть получено указанным выше способом. Дей-
ствительно, если Xi, х2, ..., хп — какое-либо решение
системы (1), то числа Xi = xlt х2 = х2, ..., хп = хп,
t *= 1 удовлетворяют системе (2), и при этом справед-
ливы равенства (3).
Итак, чтобы отыскать все решения J?i, х2, ..., хп
системы (1), следует найти все решения системы (2),
для которых t 5> 0, и преобразовать каждое из них по
формулам (3).
Пример. Пусть требуется найти все решения си-
стемы
ЗХ| — 4х2	5%з ^5- 6,
2xi + Зг2 — Зх3 — 1,
%1>0,
х2>0,
х3>0.
(4)
Поступая, как указано выше, запишем вспомога-
тельную однородную систему
— 3%! — 4х2 + 5х3 — 61 О,
2д*| Зх2 — Зх3 t О,
%! > О,
х2>0,
х3>0.
Добавляя к этой системе неравенство t 0 (ибо
нас интересуют только такие решения, для который
t>6), получаем систему (19), (20) из § 10, с той
лишь разницей, что вместо х4 написано t. Множество
решений этой системы, как показано в § 10 (см. (21)’
в § 10), описывается формулами
Xi = 5ki -|- 3Zj3 -|- 13&5,
х2 = б/с2 Ц- 3^4	13&§,
•Уз = 3ki + 4Хг2 + 2/г3 + 3^4 + 9/г5 4- 14/г6,
/ =» k5 -J- ЗЛ6,
85
где kt, k2, ..., kg — любые неотрицательные числа. Так
как нас интересуют лишь решения, для которых t > О,
то следует считать, что хотя бы одно из чисел k$, kg
отлично от нуля (строго положительно). Теперь нахо-
дим общее решение системы (4) по формулам
_ 5kt + 3k3 + 13й5
х'—	kg + Зй6
__ 5^2 4-	4- 13fe6	у,-\
2	kg + 3£6	’	J
'___ 3k4 4- 4^з 4- 2&з -|- 3&4 + Qkg 4“ 14&е	
3~	fe64-3fe6	"• J
Еще раз подчеркнем, что в этих формулах klt ki, ...
..., ke — любые неотрицательные числа^ причем хотя
бы одно из чисел kg, kg отлично от нуля.
Установив, что решение системы (1) указанным выше спо-
собом сводится к решению однородной системы (2), мы факти-
чески доказали теорему 3 из § 7 о строении любой выпуклой
многогранной области. Проиллюстрируем это на примере систе-
мы (4). Положим
4-^7	«-1. 2. 3.
так как числа fei, k2, k3, kt — произвольные неотрицательные, то
и числа k2, k3, k4 произвольные неотрицательные. Далее
положим
k' =	k' =	3fe|5	•
3 kg 4~ 3^6 ’	® kg+ 3kg ’
числа k5 и k6 неотрицательны и связаны условием k5 4- k6 = 1-
Теперь формулы (5) можно записать в виде одного равенства
(хр х2, х3) = k' (5, 0, 3) 4- k'2 (0, 5, 4) 4- k3 (3, 0, 2) 4-
4- k4 (0, 3, 3) + k3 (13, 0, 9) + kg (о,	(6)
Введем обозначения:
Хх = (5, 0, 3), Х2 = (0, 5, 4), Х3 = (3, 0, 2),
Х4 = (0, 3, 3), Х5 = (13, 0, 9), Х6 = (О, -В -ИЛ .
\ О о /
Принимая во внимание указанные выше ограничения на k,, k,,
k3, k4, а также на k5, kg, равенство (6) можно истолковать
теперь следующим образом: множество решений системы (4) есть
(Xi, Х2. Х3, Х4) 4-(Х5, Хь). Тем самым утверждение теоремы 3 § 7
доказано для системы (4).
86
§ 12. ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Линейное программирование — сравнительно ко-
ван область прикладной математики, развившаяся
в 40-х — 50-х годах нашего столетия в связи с реше-
нием разнообразных экономических задач.
Как правило, задачи, с которыми мы встречаемся в
экономике, и особенно в сфере планирования произ-
водства, — это задачи на отыскание наиболее выгод-
ного варианта. В каждой из них требуется ответить на
вопрос: как распорядиться предоставленными нам
ограниченными ресурсами, чтобы добиться наи-
большего эффекта. До недавнего времени единствен-
ным методом решения подобных задач была обыкно-
венная прикидка, решение «на глаз»; или же путем
перебора всех возможных вариантов находился луч-
ший. Сейчас положение меняется. В последние деся-
тилетия сложность производства возросла в такой сте-
пени, что простой перебор вариантов стал невозмо-
жен. Факторов, влияющих на решение, оказалось так
много, что количество вариантов стало исчисляться в
ряде случаев миллиардами. В связи с этим резко воз-
рос интерес к математическим методам в экономике.
Процессу «математизации экономики» способствовало
также развитие вычислительной техники, в частности,
появление электронных вычислительных машин.
Рассмотрим некоторые примеры задач линейного
программирования.
Пример 1. На предприятии, выпускающем из-
делия двух типов, производственная мощность цеха
сборки составляет 100 изделий первого или 300 изде-
лий второго типа в сутки; в то же время отдел техни-
ческого контроля в состоянии проверить не более
150 изделий (любого типа) в сутки. Известно далее,
что изделие первого типа стоит вдвое дороже, чем
изделие второго типа. Требуется при этих условиях
найти такой план выпуска продукции (столько-то из-
делий первого типа и столько-то второго в сутки), ко-
торый обеспечивал бы предприятию наибольшую при-
быль.
Искомый план выпуска продукции задается с по-
мощью двух неотрицательных целых чисел х, у (х —
87
количество изделий первого типа, у — второго), кото-
рые должны удовлетворять следующим условиям*):
3% + у < 300; х + у < 150;
2х -|- У максимально.
Другими словами, среди неотрицательных цело-
численных решений системы
Зх у 300, *)
x+«/<150 J	(1)
нужно выбрать такое, которое сообщает наибольшее
значение линейной функции
f = 2х + у.
Если на плоскости ввести прямоугольную систему
координат хОу, то множество решений системы (1)
изобразится с помощью заштрихованного многоуголь-
ника на рис. 47. Из того же рисунка можно уяснить,
что решением задачи является
точка Р (75, 75)— одна из вер-
шин многоугольника.
Действительно, рассмотрим пря-
мую 2х + у = с, где с — некоторое
число. Обозначим эту прямую Zc,
С ростом числа с прямая 1С сме-
щается «вверх» (и притом оставаясь
параллельной своему исходному по-
ложению). Самым большим значе-
нием с, при котором прямая Zo еще
имеет общие точки с заштрихован-
ным многоугольником, является то
значение с, при котором эта прямая
проходит через точку Р. Следователь-
но, в этой точке функция 2х + у до-
стигает своего наибольшего значения
(по сравнению с ее значениями в
остальных точках многоугольника).
Разобранный нами пример,
конечно, очень примитивен, но
все же он дает некоторое представление о характере
задач линейного программирования. В каждой из них
*) Первое условие исходит от цеха сборки. Действительно,
вместо одного изделия первого типа цех может выпустить три
изделия второго типа. Следовательно, вся продукция цеха в
пересчете на изделия второго типа составляет Зх -f- у штук; это
число не должно превосходить 300,
88
требуется найти максимальное (или минимальное)’
значение некоторой линейной функции п переменных
f = CtXi '-ф- с2х2 + ... + спхп,
при условии, что эти переменные подчинены заданной
системе линейных неравенств (в число которых вхо-
дят обязательно условия неотрицательности перемен-
ных: х, > 0, ..., х„ 5s 0). В некоторых задачах (как,
например, в приведенном выше примере) на перемен-
ные накладывается дополнительно условие целочис-
ленности.
Пример 2 (задача о диете). Из имеющихся
в распоряжении видов пищи нужно составить такую
диету, которая, с одной стороны, обеспечивала бы
удовлетворение минимальных потребностей организма
в питательных веществах (белках, жирах, углеводах,
витаминах и т. д.) и вместе с тем требовала бы наи-
меньших затрат.
Рассмотрим простую математическую модель этой
задачи.
Пусть имеются два вида продуктов, /7t и /72, со-
держащих питательные вещества А, В, С. Известно,
сколько питательного вещества того или иного вида
содержится в 1 кг пищи /71 или /72; эти сведения ука-
заны в таблице
	А	В	с
в 1 кг 77i	а.	ь.	Cl
в 1 кг 77 2	а2	ъ2	с2
Кроме этих данных, нам известны: а, Ь, с — ежесу-
точные потребности организма в А, В, С (соответ-
ственно) и Si, s2 — стоимости 1 кг пищи Пь П2 (со-
ответственно). Требуется рассчитать количество Xi
продукта /71 и количество х2 продукта П2 так, чтобы
обеспечить необходимое количество питательных ве-
ществ при минимальных затратах на пищу.
Очевидно, общая стоимость пищи будет
<S »= SjXj + s2x2.
89
Общее количество вещества А в обоих видах пищи
равно aiXi + а2х2. Оно должно быть не меньше а:
а^х^ Н- а2х2 Д-
Аналогичные неравенства должны выполняться для В
и С: Ь[Х[ + Ь2х2 2^ Ь, С[Х[ + с2х2 с. Таким образом,
приходим к следующей задаче.
Дана система
atXj + а2х2 а,
biXt + b2x2 b, '
CiXi + С2Х2 > с ,
(2)
трех линейных неравенств с двумя неизвестными
Xi, х2 и линейная функция
3 = Si-tj 4* s2x2.
Требуется среди неотрицательных решений (х1( х2)
системы (2) выбрать такое, при котором функция 3
достигает наименьшего значения (минимизируется).
К подобным схемам могут быть сведены различные
задачи о составлении сплавов, смесей горючего, за-
дачи об определении состава животноводческих кор-
мовых смесей наименьшей стоимости, о составлении
смеси химических удобрений и т. д.
Пример 3 (транспортная задача). Уголь, до-
бываемый в нескольких месторождениях, отправляет-
ся ряду потребителей: заводам, электростанциям
и т. п. Известно, сколько угля добывается в каждом
из месторождений, скажем, за месяц, и сколько его
требуется на тот же срок любому из потребителей.
Известны расстояния между месторождениями и по-
требителями, а также условия сообщения между
ними; учитывая эти данные, можно подсчитать, во
что обходится перевозка каждой тонны угля из лю-
бого месторождения в любой пункт потребления. Тре-
буется при этих условиях спланировать перевозки
угля таким образом, чтобы затраты на них были ми-
нимальными.
Примем, для простоты, что имеются лишь два
месторождения Afb М2 и три потребителя /7Ь П2, П3.
Количества угля в и М2 равны соответственно а4 и
а2; потребности пунктов /7Ь П2, П3 пусть будут соот-
ветственно Ь2, Ь3. Будем считать, что суммарные
90 '
запасы равны суммарным потребностям:
а1 4" а2 = Ь\ + Ь-2 + Ь3
— такое предположение вполне естественно. Наконец,
заданы числа сц (t == 1, 2; / = 1, 2, 3)—стоимости
перевозки тонны угля из М, в П}. Задача состоит в на-
хождении шести чисел
Хц, х12,	Х13,	Х21,	Х22,	х23>
где Хц — количество угля, предназначенное к от-
правке из Mt в Ilj.
Для удобства обозрения составим такую таблицу:
	в /71	в П2	в П3	Всего отправлено
Из Mt	Хи	Х12	Х13	41
Из М2	Х21	Х22	х23	а2
Всего привезено	61	bi	Ьз	
Общее количество угля, вывезенное из Mlt должно
равняться аг, отсюда имеем условие
xll + *12 4* Х(з = Др
Аналогичное условие должно выполняться для М2:
Х21 + х22 + *23 = й2-
Общее количество угля, привезенное в /7Ь должно'
равняться Ьг, отсюда
*11 + *21 = Ь\.
Аналогично получаем условия:
Х12 4* Х-22 = ^2>	*13 + *23 = ^3-
Предполагаем, что стоимость перевозки прямо про-
порциональна количеству перевозимого угля, т. е. пе-
ревозка из Мг в П} стоит СцХ{]. Тогда общая стоимость
всех перевозок будет
•S = СцХц 4- С12Х12 + С)зХ1з 4* с21*21 4* с22*22 4* с23*23-
91
Таким образом, приходим к следующей задаче.
Дана система
*п 4" *12 4* *13 = а1>
*21 4* *22 4* *23 — а2>
*11 4* *21 = ^1,
*12 4* *22 == ^2,
*13 4* *23 = &3
(3)
пяти линейных уравнений с шестью неизвестными и
линейная функция 3. Требуется среди неотрицатель-
ных решений
*11,	*12,	*13,	*21,	*22,	*23
системы (3) выбрать такое, при котором функция S
достигает наименьшего значения (минимизируется).
Поставленная задача может быть, конечно, сфор-
мулирована и в более общем виде, т. е. с любым чис-
лом месторождений и потребителей. Она получила на-
звание транспортной задачи и явилась одной из пер-
вых проблем, для решения которых были с успехом
применены методы линейного программирования.
Мы рассмотрели в упрощенном виде три задачи
линейного программирования. При всем разнообразии
их сюжетов в постановке задач имеется много общего.
В каждой задаче ищутся значения нескольких неиз-
вестных, причем требуется, чтобы:
а)	эти значения были неотрицательны;
б)	эти значения удовлетворяли некоторой системе
линейных уравнений или линейных неравенств;
в)	при этих значениях некоторая линейная функ-
ция обращалась в минимум (или максимум).
Заметим, что роль условия б) кажется скорее раз-
деляющей, нежели объединяющей: ведь в одном слу-
чае неизвестные должны удовлетворять уравнениям,
а в другом случае — неравенствам. Но позже мы уви-
дим, что один случай легко сводится к другому.
Задачами такого рода и занимается линейное про-
граммирование. Говоря точнее, линейное программи-
рование — это математическая дисциплина, изучаю-
щая методы нахождения наименьшего (или наиболь-
шего) значения линейной функции нескольких пере-
22
менных, при условии, что последние удовлетворяют
конечному числу линейных уравнений и неравенств.
Число переменных и число условий (уравнений, нера-
венств) могут быть, разумеется, какими угодно. В ре-
альных задачах эти числа весьма велики (порядка од-
ного или нескольких десятков, а иногда и больше).
Запишем сказанное на точном языке формул. Об-
щая математическая формулировка задачи линейного
программирования выглядит следующим образом.
Дана система линейных уравнений-.
«п4 + «124 + ••• + alnxn = Ьи
«214 + «224 + . . . + «2n4l = Ь2, г	ф
«/п14 + «/п24 + • • • + «тп4 = bm ?
и линейная функция
f = CiXt + с2х2 + ... + cnxn.	(II)
Требуется найти такое неотрицательное решение
4>0, 4>0, .... 4>0	(III)
системы (I), при котором функция f принимает наи-
меньшее значение (минимизируется).
Уравнения (I) называются ограничениями данной
задачи. Строго говоря, условия (III) тоже являются
ограничениями, однако их не принято так называть,
поскольку они не характерны для данной задачи, а яв-
ляются общими для всех задач линейного программи-
рования.
Из трех рассмотренных выше примеров, казалось
бы, только последний (транспортная задача) подхо-
дит под только что данную формулировку. Остальные
два выглядят несколько иначе, поскольку все входя-
щие в них ограничения имеют вид неравенств, а не
уравнений. Однако от ограничений-неравенств с по-
мощью простого приема можно перейти к эквивалент-*
ным ограничениям, заданным в форме уравнений.
В самом деле, предположим, что среди ограниче-
ний данной задачи имеется неравенство
«14+ «г4+ ••• + «„*„ +6 >0.	(4)
Введем новое, так называемое добавочное неиз-
вестное хп+1, связанное с неизвестными 4, 4, ..., хп
уравнением
«1X1 4* Й2Х2 4* • • • 4- апхп 4- Ъ = хп+1.
Очевидно, неравенство (4) равносильно условию не-
отрицательности xn+t. Если для каждого из нера-
венств, входящих в систему ограничений данной за-
дачи, ввести свое добавочное неизвестное, потребовав
дополнительно, чтобы все добавочные неизвестные
были неотрицательны, то задача примет стандартную
форму (I), (II), (III), хотя и с большим числом не-
известных. Продемонстрируем этот прием на примере
задачи о диете. Система ограничений в этой задаче
состоит из трех неравенств, поэтому вводим три до-
бавочных неизвестных Хз, х4, х$. В результате огра-
ничения принимают вид уравнений:
а1Х1 4" а2х2 — х3~а>
biXi 4" b2x.2 — х4 = Ь, •
CjXj 4" С2Х-2 — Х5 = С. .
Требуется среди всех неотрицательных решений этой
системы найти такое, которое минимизирует функцию
S = 51-Г, 4* s2x2.
По существу, конечно, нас интересуют в искомом ре-
шении только значения xj и Хг.
. Часто в задаче линейного программирования тре-
буется разыскать не минимум, а максимум линейной
функции f. Так как max f = — min(—f) (докажите
это), то одна задача сводится к другой заменой f
на —f.
Мы показали, что задача линейного программирования с
ограничениями-неравенствами сводится к задаче с ограничения-
ми-уравнениями. Весьма интересно, что возможно и обратное
сведение, т. е. любую задачу линейного программирования мож-
но сформулировать так, что все ограничения будут иметь вид
неравенств. Останавливаться на этом мы не будем.
Сделаем в заключение несколько замечаний отно-
сительно принятой терминологии. Любое неотрица-
тельное решение системы ограничений называется до-
пустимым. Допустимое решение, дающее минимум
функции /, называется оптимальным. Отыскание оп-
тимального решения и является как раз нашей целью.
Оптимальное решение (если оно существует) не обя-
зательно единственно: возможны случаи, когда имеет-
ся бесчисленное множество . оптимальных решений.
84
§ 13. СИМПЛЕКС-МЕТОД
Реальные задачи линейного программирования со-
держат, как правило, большое число ограничений и
неизвестных. Естественно, что решение таких задач
связано с большим объемом вычислений. Это затруд-
нение преодолевается с помощью быстродействующих
вычислительных машин. Алгоритм, лежащий в основе
машинной программы, может быть связан со специ-
фикой данного класса задач. Так, например, для ре-
шения транспортной задачи имеются весьма простые
алгоритмы, обусловленные особенностями ее системы
ограничений. Однако существуют и общие методы, по-
зволяющие найти решение любой задачи линейного
программирования в обозримое число шагов. К их
числу относится прежде всего так называемый сим-
плекс-метод и некоторые его модификации*).
Г. Описание симплекс-метода. Итак, рассмотрим
задачу линейного программирования. Дана некоторая
система линейных уравнений с п неизвестными
Xi, х2, ..., хп и некоторая линейная функция f. Тре-
буется среди неотрицательных решений данной си-
стемы найти такое, которое минимизирует функцию /.
Для начала работы по симплекс-методу требуется,
чтобы заданная система уравнений была приведена
к такому виду, в котором какие-то г неизвестных вы-
ражены через остальные, причем свободные члены
этих выражений неотрицательны. Предположим, на-
пример, что п = 5 и неизвестные, которые выражены
через остальные, — это Xt, х2, Хз. Следовательно, си-
стема ограничений приведена к виду
где
Xi —- о	О4Х4 0,5X5,
Х2 = Р 4* &4Х4 + Рз-^З»
*3 = Y + Y4*4 + Y5*5> -
а^>0, ₽^>0, Y 0-
(1)
(2)
Можно ли на самом деле привести систему к такому
виду и как это сделать — этот вопрос мы рассмотрим
позже (см. п. 2°). Неизвестные Xt, х2, х3, находящие-
ся в левых частях системы (1), называются базисными,
*) Название «симплекс-метод» не связано с существом дела,
а объясняется случайным обстоятельством.
95
а весь набор {хц х2, *з}, который мы обозначим для
краткости одной буквой Б, — базисом; остальные не-
известные называются небазисными или свободны-
ми*). Подставляя в первоначальное выражение для
функции f вместо базисных неизвестных их выражения
через небазисные из (1), мы можем и саму функцию f
также записать через небазисные неизвестные х4, х&:
! = С + С^ + С5Х5.
Положим все небазисные неизвестные равными
нулю:
х4 = 0, х5 = 0,
и найдем из системы (1) значения базисных неиз-
вестных:
xt = а, х2 = р, х3 = у.
Полученное таким путем решение системы
(а, ₽, Y, 0, 0)
будет, вследствие (2), допустимым. Оно называется
базисным решением, отвечающим базису Б={хь х2, х3].
Для базисного решения значение функции f равно
Решение задачи линейного программирования при
помощи симплекс-метода распадается на ряд шагов.
Каждый шаг заключается в том, что от данного ба-
зиса Б мы переходим к другому базису Б' с таким
расчетом, чтобы значение f уменьшилось или, по край-
ней мере, не увеличилось: fB, fБ. Новый базис Б'
получается из старого Б весьма просто: из Б уда-
ляется одно из неизвестных и взамен него вводится
другое (из числа прежних небазисных). Разумеется,
изменение базиса влечет за собой соответствующую
перестройку системы (1). После некоторого числа k
таких шагов мы или приходим к базису Б<к\ для ко-
торого есть искомый минимум функции f, а соот-
ветствующее базисное решение является оптималь-
ным, или же выясняем, что задача решения не имеет.
*) Последнее название связано с тем, что при нахождении
всех решений системы (1) (безотносительно к задаче линейного
программирования) этим неизвестным можно придавать любые
значения.
96
Проиллюстрируем симплекс-метод на примерах.
Пример 1. Пусть заданная система ограничен
ний и функция f приведены к такому виду:
Xi = 1 — х4 + 2х5> '
х2 = 2 + 2х4 — х6, -
Хз — 3 ~~ Зх4 х5; .
f = X4 — XS.
Здесь неизвестные Хц х2, Хз образуют базис. Соответ-
ствующее базисное решение есть
(1, 2, 3, 0, 0);
значение f для этого решения равно 0.
Посмотрим, не является ли это решение оптималь-
ным. Поскольку Хз входит в f с отрицательным коэф-
фициентом, мы можем попытаться уменьшить значе-
ние f, увеличив xs (и сохранив нулевое значение для
х^). Однако делать это следует осторожно, поскольку
при изменении Хз будут меняться значения Xi, х2, Хз,
и нужно следить за тем, чтобы ни одно из них не ста-
ло отрицательным.
Так как увеличение х5 приводит к увеличению х(,
то для Xi такой опасности не существует. Рассматри-
вая Хг и Хз, находим, что Хз может быть увеличено до
2 (и не более, иначе х2 станет отрицательным), что
дает Xt = 5, х2 == 0, Хз = 1. В итоге получаем новое
допустимое решение (5, 0, 1, 0, 2), в котором число
положительных неизвестных по-прежнему равно трем.
Значение f для этого решения равно —2.
Новый базис теперь состоит из х4, х5, х3. Чтобы
осуществить соответствующую перестройку системы
ограничений, нужно выразить эти неизвестные через
х2, х4. Начинаем с уравнения для х2 (нового небазис-
ного неизвестного), из которого выражаем х5 (новое
базисное неизвестное):
х5 = 2 + 2х4 — х2;
затем выражаем Xi, х3 и f:
Xi = 1 — х4 -]- 2 (2 4* 2х4 — х2),
Хз = 3 — Зх4 — (2 + 2х4 — х2),
f = Xi — (2 + 2х4 — х2),
07
Итак, задача приведена к виду
Х[ = 5 + Зх4 — 2х2, '
х5 = 2 + 2х4 — х2, ’
х3 = 1 — 5х4 + х2, .
f _ _ 2 — х4 + х2.
Новое базисное решение есть
(5, 0, 1,0, 2);
значение f для этого решения равно —2. На этом за-
канчивается первый шаг процесса.
Выясним, нельзя ли еще уменьшить значение f.
Коэффициент при х4 в выражении для f отрицателен,
поэтому можно попытаться уменьшить f, увеличив х4
(без изменения х2 = 0). Первое и второе уравнения
этому нисколько не препятствуют, а из третьего урав-
нения видно, что х4 можно увеличить до -g- (и не бо-
лее, иначе Хз станет отрицательным). Полагая
1	п	28	12	Л
Х4 —у, Х2 = 0, получим X! х5 = —,	х3=0.
В итоге имеем новое допустимое решение l-g-, 0, 0,
5 ’ 5 )•
Новый базис теперь состоит из х4, х^, х4. Из урав-
нения для Хз (нового небазисного неизвестного) выра-
жаем х^ (новое базисное неизвестное):
__1_ 1 । 1
•^4 g 5 т 5 ^2
и подставляем это выражение в остальные уравнения.
В итоге система принимает вид
_ 28	з	7
#1	5	5	5 Х2г
_ 12	2	3
~ 5	5	Хз	5 Хъ
_ 1 1 , 1
Xi g 5 Хз т 5 х2,
а для функции f получается выражение
г 11 , 1	,4
f —-----5" + -5 х3 + -5 Х2-
98
Новое базисное решение есть
,	П и
соответствующее ему значение f равно---g-. На этом
заканчивается второй шаг процесса.
Так как в последнюю запись функции f оба неиз-
вестных Хз и х2 входят с положительными коэффициен-
тами, минимум f достигается при х3 = х2 — 0. Это
означает, что последнее базисное решение 0, 0,
1	12\
•g-, -g-l является оптимальным и искомый мини-
, 11 .
мум I равен---g-; задача решена.
В разобранном примере процесс закончился на-
хождением оптимального решения. Однако имеется
еще одна возможность окончания процесса. Чтобы ее
проиллюстрировать, решим следующий пример.
Пример 2.
Х3 = 1 + X] — х2,
Хд = 2 — X] + 2х2; )
f = — х{ — х2.
Здесь базис образован неизвестными х3, х4. Базис-
ное решение имеет вид
(0, 0, 1, 2),
соответствующее значение функции f равно 0.
Коэффициент при Хд в выражении для f отрица-
телен, поэтому пытаемся увеличить Xi (не меняя
х2 = 0). Первое уравнение этому не препятствует, из
второго же уравнения видно, что х1 можно увеличить
только до 2, что дает х3 — 3, хд = 0. Новое допусти-
мое решение есть (2, 0, 3, 0); значение f для этого ре-
шения равно —2.
Новый базис теперь состоит из х3, хь Выражаем
из второго уравнения Xi и подставляем это выражение
в первое уравнение, а также в f. Задача принимает
вид
Хз= 3 — х4 —|— х2, ")
Xi = 2 — х4 + 2х2; )
f = — 2 -f- Хд — Зх2.
9g-
Новое базисное решение есть
(2, 0, 3, 0),
а соответствующее ему значение f равно —2.
В последнем выражении для f коэффициент при
хг отрицателен. Посмотрим, насколько можно умень-
шить значение f путем увеличения хг (при сохране-
нии %4 = 0). С этой целью просматриваем члены с хг
в обоих уравнениях системы и замечаем, что оба ко-
эффициента при Хг положительны. Таким образом, хг
можно увеличивать неограниченно, не нарушая поло-
жительности Хз и Xi. При этом f будет принимать от-
рицательные значения, как угодно большие по абсо-
лютной величине. Итак, min f — — оо (как говорят,
функция f не ограничена снизу), и оптимального ре-
шения не существует.
Как видно из приведенных примеров, в основе очередного
шага симплекс-метода лежит выбор отрицательного коэффициен-
та при некотором небазисном неизвестном Xj в выражении для f.
Если таких коэффициентов оказывается не один, а несколько,
то можно выбрать любой из них. Это обстоятельство вносит
В расчеты некоторый элемент произвола. Однако и на этом
произвол не обязательно кончается: может случиться, что при
увеличении х, до крайнего предела сразу несколько базисных
неизвестных обращаются в нуль. Тогда любое из них х, можно
поменять ролями с Xj, т. е. сделать Xi небазнсным, a xj, на-
оборот, ввести в базис.
Разумеется, можно было бы устранить произвол, введя ка-
кое-нибудь дополнительное соглашение. Однако особой необхо-
димости в этом нет. На самом деле некоторый произвол даже
Полезен, так как он позволяет варьировать процесс вычислений
И, значит, искать такую последовательность шагов, которая воз-
можно быстрее ведет к решению задачи.
2°. Отыскание первого базиса. В предыдущем
пункте была описана процедура решения задачи ли-
нейного программирования симплекс-методом. В ка-
честве предварительного условия мы требовали, чтобы
система ограничений была приведена к виду*)
Xi — а + аг+1хг+1 + . • • + «А,
*2= ₽+ Pr+lA + I + ••• + РпА,
Xr = Y + Yr+1A+1 + »• • + Nnxn,
(3)
*) Или к аналогичному виду, когда слева стоят не
Xi, хг....хг, а другие г неизвестных; остальные п — г неиз-
вестных должны входить в правые части.
100
где а О, р О, ..., у 0; тогда мы говорим, что
неизвестные Xi, х2, ..., хг образуют базис.
Во многих задачах линейного программирования
базис усматривается непосредственно. В других слу-
чаях его приходится искать. Рассмотрим один из ме-
тодов нахождения базиса, называемый обычно «ме-
тодом искусственного базиса».
Для иллюстрации метода разберем пример.
Пример. Дана система ограничений
2%! — 2х2 + 2х3 — х4 — 7х5 = — 4,
— Х[ -|- Зх2 — 2х3 -|- Х4 -|- 3,Г3	5.
Требуется разрешить ее относительно некоторого ис-
ходного базиса.
Прежде всего преобразуем данную систему так,
чтобы свободные члены уравнений стали неотрица-
тельными. Для этого следует умножить обе части пер-
вого уравнения на —1. Получим систему
— 2Х] + 2х2 — 2хз + х4 + 7х5 = 4, ")
— Xj -|- Зх2 — 2х3 -j~ Х4 -|- 3%5 = 5. J
Введем теперь вспомогательные, или искусствен-
ные, неизвестные yi, у2 (по одному на каждое уравне-
ние) следующим образом:
У\ = 4 — (— 2Х[ -4- 2х2 — 2х3 + х4 + 7х5), ")
= 5— (—%i + 3x2 — 2х3 + х4 + Зх5). )
Очевидно, все решения исходной системы (4) можно
получить, взяв решения системы (5), удовлетворяю-
щие условиям z/i = 0, z/г = 0, и оставив от каждого
из этих решении лишь значения xlt ..., х5.
В системе (5) неизвестные у1у у2 образуют базис.
Предположим, что нам удастся, отправляясь от этого
базиса, перейти к другому базису, не содержащему
ни одного искусственного неизвестного. Тогда, опуская
в полученных уравнениях члены с yt и у2 (или, что то
же, полагая yi — 0, z/2 = 0), получим систему, равно-
сильную исходной системе (4), причем эта системй
будет разрешена относительно некоторого базиса.
Остается решить, каким образом в системе (5)
неизвестные г/i, у2 можно перевести в небазисные. За-
мечательно, что для этой цели мы можем опять-таки
применить симплекс-метод. А именно, будем решать
при помощи этого метода задачу о минимизации
101
функции
Г = У i + У2
при ограничениях (5), а также при условиях Xj
0, ..., х5 0, у1 ;> 0, у2 ;> 0. Предпосылки, при
которых начинает действовать симплекс-метод, здесь
выполнены, так как система (5) имеет требуемый вид
(выделен исходный базис уи у2). После некоторого
числа шагов будет получен искомый минимум. Так
как F 0, то и min F 0, поэтому возможны два
случая:
1.	min F > 0. Это означает, что система (5) не
имеет неотрицательных решений, для которых = 0,
(/2 = 0 (в противном случае minF = 0). Следова-
тельно, в этом случае исходная система (4) не будет
иметь неотрицательных решений. Отсюда будет следо-
вать, что любая задача линейного программирования
с такой системой ограничений неразрешима.
2.	minF = 0. Пусть в этом случае (х®.....х®
г/®, у°) — оптимальное решение. Поскольку у® ф- у% =
= minF = 0, то у® = 0, y^ — Q. Отсюда следует, что
(х®...х®) будет неотрицательным решением исход-
ной системы (4).
Таким образом, в случае min F — 0 система огра-
ничений (4) будет иметь по крайней мере одно неот-
рицательное решение.
Далее, если по окончании процесса (т. е. когда уже
достигнут min F = 0) окажется, что искусственные
неизвестные г/ь у2 находятся среди небазисных, то мы
достигли цели — выделен базис из числа неизвестных
Х\, ..., х5. Если же выяснится, что какие-то из неиз-
вестных t/i, Уг еще продолжают входить в базис, то
необходимы дальнейшие преобразования.
Итак, решаем задачу минимизации функции
F — у\ ф- у2 = [4 — (— 2Х] ф- 2х2 — 2х3 ф- х4 ф- 7х5)] ф-
ф- [5 — (— Х\ ф- Зх2 — 2х3 ф- х4 ф- Зх5)] =
- ~ 9 Ф~ ЗХ| — 5х2 ф~ 4хз	2х4 — IOX5.
Коэффициент при х4 в выражении для F отрица-
телен, поэтому пробуем уменьшить значение F, уве-
личивая х4. Сопоставляя коэффициенты при х4 в урав-
нениях (5) со свободными членами, находим, что х4
102
можно увеличивать только до 4 — тогда r/i обращает-
ся в нуль. Новый базис состоит из х4, z/г- Разрешаем
первое уравнение относительно х4 и полученное выра-
жение для х4 подставляем во второе уравнение, а так-
же в F. Задача принимает вид
х4 = 4 + 2%! — 2х2 + 2х3 — 7х5 — уь 4
у>— 1 — Xi— Х2 + 4x5 + t/i; J
F=l— %!— Х2 +4X5 + 2//!.
На этом заканчивается первый шаг процесса. В резуль-
тате него неизвестное у\ удалось сделать небазисным.
Коэффициент при Xi в новом выражении для F от-
рицателен. Рассматривая уравнения (6), видим, что
можно увеличивать только до 1, тогда yz обра-
щается в нуль. Новый базис состоит из х4, xt. Пере-
страивая уравнения (6) и выражение для F (послед-
нее, впрочем, уже необязательно), получаем
Xi — 6 — 4х2 + 2х3 + х$ + У\ — 2у2, 4
Xi = 1 — х2 + 4х5 + Уу — у2, )
F = У1 + /72-
Таким образом, в результате второго шага искусствен-
ные неизвестные i/i, z/2 стали небазисными. Отбрасы-
вая в уравнениях (7) члены с /л, У2, получаем
х4 = 6 — 4х2 -|- 2х3 -|- х3, 4
Xi = 1 — х2 + 4х5. /
Это означает, что в исходной системе (4) выделен
базис. Задача решена.
Как уже отмечалось, при нахождении симплекс-методом ми-
нимума функции F, равной сумме искусственных неизвестных,
может случиться, что к моменту окончания процесса (т. е. когда
уже достигнут min F = 0) часть искусственных неизвестных еще
продолжает входить в базис. С помощью простых приемов, ко-
торые мы продемонстрируем на примере, можно и эти неиз-
вестные перевести в небазисные.
Пусть, скажем, после некоторого числа шагов задача при-
обрела вид
11,3	3	1	1
Хз 2	2	4- 2	2 %2	2
У2=	х, — Хз + 11Х4 + бх5 + 2yt,
У2=	6X1 + 6х3 + 6х4 4- 4х5 +	2у,-
F =	7x1 + 5x3 + 17x4 + 9x5 +	5//!.
(8)
Тс-з
Мы видим, что функция F уже достигла минимума, равного
нулю, поэтому из дальнейших рассмотрений ее можно исклю-
чнть. Неизвестные у2 и уз еще продолжают входить в базис.
Однако свободные члены в уравнениях для у2 и уз равны нулю,
и это не случайно: ведь min F = 0 означает, что в полученном
базисном решении уз = 0 и уз = 0. Этим обстоятельством мы
сейчас и воспользуемся, чтобы вывести из базиса у2 и уз. Для
этого заметим, что среди коэффициентов при неизвестных
хь ..., х5 в уравнении для у2 имеется отрицательное число)
это коэффициент —1 прн хз. Произведем замену Хз*->г/2 (не-
известное Хз сделаем базисным, а у2 переведем в небазисные).
С этой целью второе из уравнений разрешаем относительно Хз
и полученное выражение для Хз подставляем в остальные урав-1
иения. Так как свободный член второго уравнения равен нулю,
то в результате такой операции свободные члены уравнений не
изменятся (и, значит, останутся неотрицательными),	<
Получим:
1	5	3
*2 “= -g- -}- Xi + 15х4 + 7хз + У1 —2 ^2>
(9)
Хз= х1+11х4 + 5х5+ 2«/i—	у2>
Уз=^	12х[ + 72х4 + 34хз + 141/] — 6у2. '
Теперь уже в уравнении для уз нет отрицательных коэффи-
циентов (при Xi, х5), поэтому нам не удастся перебросить
уз в небазисные неизвестные. Однако не следует особенно огор-
чаться по этому поводу. Ведь если какие-то числа X!.......х3
удовлетворяют исходной системе ограничений, то yt, уг и уз
должны равняться нулю. Значит,
12xi + 72х4 + 34х5 = 0.
Так как все коэффициенты прн неизвестных здесь имеют одни
и тот же знак, то отсюда должно следовать;
Xi = х4 = Хз = 0
— эти равенства являются, таким образом, следствиями исходной
системы ограничений н условий х< 0 (;' = 1......5). Если счи-
тать их выполненными, то от системы (9) остается
1 У
Х2 = Т’ I
хз = 0. J
Итак, заданная система ограничений прн условии неотрицатель-
ности неизвестных допускает только одно решение:
Хз = тр хз = 0, xi =0, х4 = 0, хе = 0,
104
§ 14. ТЕОРЕМА ДВОЙСТВЕННОСТИ
В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ
В различных разделах математики встречаются
так называемые теоремы двойственности. Каждая из
них позволяет для любого утверждения данной тео-
рии построить — по определенному стандартному пра-
вилу—другое утверждение таким образом, что из
справедливости первого автоматически следует спра-
ведливость второго. Замечательный пример теоремы
двойственности мы встречаем и в линейном програм-
мировании.
Пусть дана некоторая задача линейного програм-
мирования — будем в дальнейшем называть ее исход-
ной задачей или задачей А. При этом ограничения
заданы в форме неравенств. Итак, дана система
«141 + а12х2 +	...	4- а[пхп +	0,	|
«21*1 4- «22*2 +	...	+ а2пхп -h	4	> О,	’
«т41 4~ «/п2'^2 4~	• • •	"4” ^miAn Т"	j
(1)
т линейных неравенств с п неизвестными и линейная
функция
f = CtXi 4- с2х2 4 • • • 4“ спхп.
Требуется из всех неотрицательных (дц 0, х2 4
О, ..., хп 4 0) решений системы (1) выбрать та-
кое, которое сообщает функции f наибольшее значе-
ние (максимизирует/).
Свяжем с задачей А новую задачу, которую назо-
вем двойственной по отношению к задаче А или за-
дачей А'. Вот ее формулировка: дана система
«141 4- «242 4- ... 4- «т4т 4- «1 =4 0,
«12^1 4- а1‘>У2 4- • • • 4- АлУУт 4- «2 С 0, t
а1пУ1 4” «2г42 4” ... 4” ОтпУШ 4- «ц 0 _
п линейных неравенств с т неизвестными и линейная
функция
<р — bii/t 4- b2y2 4- ... 4- Ьтут.
105
Требуется из всех неотрицательных решений системы
(Г) выбрать такое, которое сообщает функции <р наи-
меньшее возможное значение (минимизирует ср).
Сравнивая задачи А и А', мы замечаем, что:
1.	Коэффициент цри /-м неизвестном в i-м уравне-
нии системы (Г) тот же самый, что и. коэффициент
при i-м неизвестном в ji-м уравнении системы (I).
2.	Свободные члены неравенств в каждой ив задач
совпадают с коэффициентами при неизвестных в ли-
нейной функции другой задачи.
3.	В системе неравенств задачи А все неравенства
типа 0, причем в этой задаче требуется достичь
максимума f. В системе неравенств задачи А', наобо-
рот, все неравенства типа Q, но зато в ней тре-
буется достичь минимума ср.
Одна из основных теорем линейного программиро-
вания — так называемая теорема двойствен-
ности — утверждает следующее.
Теорема двойственности. Если исходная
задача имеет решение, то и двойственная ей также
имеет решение. При этом максимум: функции f равен
минимуму функции ср:
max f = min ср.
Мы докажем эту теорему, сведя ее к вопросу о со-
вместности некоторой системы неравенств.
Чтобы было удобнее следить за доказательством,
разобьем его на несколько этапов.
Этап 1. Лемма. Если х®, ..., х’ — какое-либо
неотрицательное решение системы (1),а	.... y9m —
какое-либо неотрицательное решение системы (!'), то
значения функций f а ср для этих решений связаны
неравенством
/о Фо-
Доказательство. Рассмотрим неравенства
системы (I), куда вместо Xi, . .., хп подставлены зна-
чения х°{, .... х°. Умножим первое из этих неравенств
на у°, второе — на у% и т. д. и затем; все полученные
неравенства сложим:
+ ... + атпу^х°п) + ЗД + ... + Ьту*т > О
(следует учесть, что мы умножаем неравенства на не-
отрицательные числа, поэтому знаки неравенств не
106
меняются.). Точно так же умножим первое не,равен"
ство системы (У) на xj, второе —на х°2 и т. д., а за-
тем сложим:
(«п^ + ... +атпуотхоп) + с1Х°+ ... + с„х®„<0.
В обоих случаях в скобках стоит выражение, равное
сумме членов вида а/;.^.х9 по всем i = 1.... т, j =
= 1, ..., п. Следовательно, оба выражения в скобках
совпадают. Но тогда
С1х°+ ... + спх®<М + ••• + ьтУт
или fo Фо- Лемма доказана.
Этап 2. Сведение задач Аи А'к решению неко-
торой системы неравенств.
Рассмотрим следующую «комбинированную» си-
стему неравенств:
flll-Xl +	+ ClinXn
amiXi + ... + amnxn
+ 6, >0
+ ът о
апУ1 + ••• + amiym + Ci <0
(S)
Ч\пУ\ + • • • + ЛшпУщ + Сц 0
CjXi + ... + cnxn
b iff i	... bmym
Она, как видно из написанного, составлена из си-
стемы (1), системы (!') и неравенства f — ф 0. Не-
известными в системе (S) являются xlt ..., хп, yi, ...
..., ут (всего п 4- т неизвестных). Установим прежде
всего такой факт.
Если система (S) имеет неотрицательное решение
х®, ..., }fin, у®.у°т, то числа х®, ..., х® дают ре-
шение задачи А, а числа у®, ..., у°т — решение за-
дачи А', причем f0 = ф0.
Задержимся немного в этом месте, чтобы подчерк-
нуть принципиальную роль сформулированного выше
предложения. В нем замечательно то, что задача ли-
нейного программирования, т. е. задача о максими-
зации, сводится к решению некоторой системы ли-
нейных неравенств без каких бы то ни было
требований максимизации. На самом деле,
конечно, решение системы (S) (в области неотрица-
107
тельных значений неизвестных) ничуть не легче, чем
решение исходной задачи линейного программирова-
ния (задачи А); однако самый факт такого сведения
очень любопытен.
Итак, докажем выдвинутое выше утверждение.
Прежде всего ясно, что числа х°, ..., х° неотрица-
тельны и удовлетворяют системе (1); аналогично
числа у\.....у°т неотрицательны и удовлетворяют
(Г). Кроме того, для этих чисел справедливо нера-
венство
fo Фо
(вытекающее из последнего неравенства системы (S)).
С другой стороны, по лемме имеем
fo Д фо-
Следовательно, fo — фо-
Далее, если х,.....хп — какое-нибудь неотрица-
тельное решение системы (1), то снова по лемме
имеем
f <Фо-
Сопоставляя это с f0 = фо, получаем f f0, откуда
следует, что fo есть максимальное значение f.
Аналогично, если у1г ут — какое-нибудь неот-
рицательное решение системы (Iх), то по лемме имеем
fo Д ф;
сопоставляя это с fo = фо, получаем фо Д Ф, т. е. фЭ
есть минимальное значение ф. Этим доказано сфор-
мулированное выше предложение.
Этап 3. Завершение доказательства. Нам оста-
лось теперь показать следующее: если задача А имеет
решение, то система (S) имеет неотрицательное ре-
шение. Ибо тогда, как показано выше, fo = фо, т. е.
max f — min ф.
Будем рассуждать от противного, т. е. предполо-
жим, что система (S) не имеет неотрицательных ре-
шений. Для этого случая у нас имеется следствие из
теоремы о несовместных системах (§ 9). Правда, это
следствие относится к системе, состоящей из нера-
венств ^0, а у нас в системе (S) имеются неравен-
108
ства 0. Но это положение легко исправить, записав
систему (S) в виде
вцХ| + .	. + а1пхп	+ bi 2=			0. j
От1 ^1 “Ь •	• +атпХп			+ Ьт~^	= 0,
		— ЙЦ1/! — .	• — ЯпчУт	— Cl 2^	0,
		— ainyi — .	. — ОтпУт	сп	= 0,
С1Х| + .	 + спхп	— biyi — .	 — Ътут		°.
(S')
Итак, предположим, что система (S') не имеет не-
отрицательных решений. Согласно следствию из тео-
ремы о несовместных системах, найдутся неотрица-
тельные числа ki....km, li....ln, s (всего m + n -f-
-f- 1 число) такие, что *)
«п^1+ ••• + dm\km + CjS 0,
Я1Л “Ь • • • “Ь "T" CnS 0,
(2)
—• «11^1 — ... — ainln —	0, )
..............................................?	(2')
0, )
+ ... + bmkm— C\l\— ... —cnln < 0.	(3)
Покажем прежде всего, что число s не равно нулю.
В самом деле, допустим, что это не так, т. е. s = 0.
Рассмотрим какое-либо неотрицательное решение
х°п системы (1). Рассуждая, как при доказа-
тельстве леммы, найдем, что
(flnM + ... + amnkmx°n) + blki + ... + bmkm > 0.
Но выражение, стоящее в скобках, «g: 0 (это полу-
чается, если умножить первое из неравенств (2) на * •••
*) Числа k\, ..., km, lt, ..., ln, s — кгк раз те самые, на
которые мы умножаем первое, второе...........(т + « + 1)-е
неравенства системы (S'), чтобы получить (после сложения)
противоречивое неравенство а,Х| + ... +	+ “,</] + ...
••• + атУт + ^>0, где ар ..., ап, а', ..., а'т^ 0, ad — отри-
цательное число.
109
х®, второе — на хп и т. д., учтя при этом s = 0, а за-
тем произвести сложение). Отсюда
^1^1+ •••	(4)
после чего из (3) следует
Ci^i +  • • + сп1п > 0.
Далее, умножая неравенства (2') (где s = 0) на про-
извольное положительное число X, получим
+ ••• + aln%ln >0,
............................... (5)
ат\^\Л- ••• +
Если теперь к каждому из неравенств (1), куда вме-
сто Xi, .... хп подставлены х°..х®, прибавим со-
ответствующее неравенство (5), то найдем, что числа
4 + Ц......Л + К
также составляют неотрицательное решение системы
(1). Значение функции f для этого решения равно
<¥ц + ... +спх°п + Цс^+ ... +сп1п),
и так как выражение в скобке строго положительно,
то значение f неограниченно возрастает с ростом X.
Это означает, что max f — оо, т. е. задача А решения
не имеет, вопреки условию.
Итак, s не равно нулю. В таком случае из (2) сле-
kjyj
дует, что числа —, ..., -у составляют неотрица-
тельное решение системы (1), из (2')—что числа
..., у составляют неотрицательное решение си-
стемы (1')> а из (3)—что для этих решений <р — f <
< 0. Но это противоречит лемме. Итак, предположив,
что система (S) не имеет неотрицательных решений,
мы приходим к противоречию. Следовательно, такие
решения обязательно существуют, что и доказывает
теорему двойственности.
Пример. Найти максимальное значение функции
f = 2х2 + 12х3
110
при условии, что переменные х1г х2, xs неотрицательны
и удовлетворяют неравенствам
х,— х2— х3 + 2>0, |
— Xi — х2 — 4х3 + 1	0. )
Решение. Назовем поставленную задачу зада-
чей А. Двойственная к ней задача (задача А') должна
формулироваться так: найти минимальное значение
функции
<Р = 2z/] + у2
при условии, что переменные у2 неотрицательны и
Удовлетворяют неравенствам
Ух — У2 < 0, '
— Ух — У2 + 2 < 0, >
(6)
— Ух — 4у2 +12^0. -
Задачу А' можно решить графически, изобразив
на координатной плоскости у\Оу2 область решений си-
стемы (6). Это сделано на рис. 48. На том же ри-
сунке видно, что своего наименьшего значения функ-
ция ф достигает в точке (0, 3)—одной из вершин об-
ласти. Это значение равно 3. По теореме двойствен-
ности максимум функции f тоже должен равняться 3.
СОДЕРЖАНИЕ
Предисловие............................................. 3
§ 1.	Несколько фактов из аналитической геометрии ...	5
§ 2.	Геометрический смысл системы линейных неравенств
с двумя или тремя неизвестными..........................14
§ 3.	Выпуклая оболочка системы точек..................19
§ 4.	Выпуклый многогранный конус .....................23
§ 5.	Область решений системы линейных неравенств с дву-
мя неизвестными.........................................30
§ 6.	Область решений системы с тремя неизвестными . . 43
§ 7.	Системы линейных неравенств с любым числом неиз-
вестных ................................................52
§ 8.	Решение системы линейных неравенств путем последо-
вательного уменьшения числа неизвестных.................57
§	9.	Несовместные системы.............................65
§ 10.	Однородная система линейных неравенств. Фундамен-
тальный набор решений...................................71
§11.	Решение неоднородной системы неравенств .... 84
§	12.	Задача линейного программирования................87
§	13.	Симплекс-метод...................................95
§ 14.	Теорема двойственности в линейном программировании 105

ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ
Вып. 1. А. И. Маркушевич. Возвратные последовательности.
Вып. 2. И. П. Натансон. Простейшие задачи на максимум н минимум.
Вып. 3. И. С. СоминскиЙ. Метод математической индукции.
Вып. 4. А. И. Маркушевич. Замечательные кривые.
Вып. 5. 11. II. Коровкин. Неравенства.
Вып. б. Н. Н. Ворооьев. Числа Фибоначчи.
Вып. 7. А. Г. Курош. Ътгеораические уравнения произвольных сте-
пеней.
Вып. 8. А. О. Гельфонд. Решение уравнений в целых числах.
Вып. 9. А. И. Маркушевич. Площади н логарифмы.
Вып. 10. А. С. Смогоржевский. Метод координат.
Вып. Н. Я. С. Дубнов. Ошибки в геометрических доказательствах.
Вып. 12. И. П. Натансон. Суммирование бесконечно малых величин.
Вып. 13. А. И. Маркушевич. Комплексные числа и конформные ото-
бражения.
Вып. 14. А. И. Фетисов. О доказательствах в геометрии.
Вып. 15. И. Р. Шафаревич. О решении уравнений высших степеней.
Вып. 16. В. Г. Шсрватов. Гиперболические функции.
Вып. 17. В. Г. Болтянский. Что такое дифференцирование?
Вып. 18. Г. М. Миракьян. Прямой круговой цилиндр.
Вып. 19. Л. А. Люстерннк. Кратчайшие липни.
Вып. 20. А. М. Лопшнц. Вычисление площадей ориентированных фигур.
Вып. 21. Л. И. Головина и И. М. Я гл ом. Индукция в геометрии.
Вып. 22. В. Г. Болтянский. Равновеликие и равносоставленные фигуры.
Вып. 23. А. С. Смогоржевский. О геометрии Лобачевского.
Вып. 24. Б. И. Аргунов и Л. А. Скорняков. Конфигурационные тео-
ремы.
Вып. 25. А. С. Смогоржевский. Линейка в геометрических построе-
ниях.
Вып. 26. Б. А. Трахтеиброт. Алгоритмы и машинное решение задач.
Вып. 27. В. А. Успенский. Некоторые приложения механики к матема-
тике.
Вып. 28. Н. А. Архангельский и Б. И. Зайцев. Автоматические цифро-
вые машины,
Вып. 29. А. Н. К остове кий. Геометрические построения одним циркулем.
Вып. 30. Г. Е. Шилов. Как строить графики.
Вып. 31. А. Г. Дорфман. Оптика конических сечений.
Вып, 32. Е. С. Вентце ль. Элементы теории нгр.
Вып 33. А. С. Барсов. Что такое линейное программирование.
Выл. 34. Б. Е. Маргулис. Системы линейных уравнений.
Вып. 35. И. Я. Виленкин. Метод последовательных приближений.
Вып. 36. В. Г. Болтянский. Огибающая.
Вып. 37. Г. Е. Шилов. Простая гамма (устройство музыкальной шкалы).
Вып. 38. Ю. А. Шрейдер. Что такое расстояние?
Вып. 39. Н. Н. Воробьев. Признаки делимости.
Вып. 40. С. В. Фомин. Системы счисления.
Вып. 41. Б. Ю. Коган. Приложение механики к геометрии.
Вып. 42. Ю. И. Любич и Л. А. Шор. Кинематический метод в геометри-
ческих задачах.
Вып. 43. В. А. Успенский. Треугольники Паскаля.
Вып. 44. И. Я. Бакельман. Инверсия.
Вып. 45. И. М Я г лом. Необыкновенная алгебра.
Вып. 46. И. М. Соболь. Метод Монте-Карло.
Вып. 47. Л. А. Кал ужи ин. Основная теорема арифметики.
Вып. 48 А. С. Солодовников. Системы линейных неравенств.
Вып. 49. Г. Е. Шилов. Математический анализ в области рациональных
функций.
Вып. 50. В. Г. Болтянский, И. Ц. Гохберг. Разбиение фигур иа мень-
шие части.
Вып. 51. Н. М. Бескин. Изображения пространственных фигур.
' Вып. 52= Н. М. Бескин. Деление отрезка в данном отношении.
Вып. 53. Б. А. Розенфельд и Н. Д. Сергеева. Стереографическая
проекция.