ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ
ВЫПУСК 33
А. С. БАРСОВ
ЧТО ТАКОЕ
ЛИНЕЙНОЕ
ПРОГРАММИРОВАНИЕ
ГОСУДАРСТВЕННОЕ ИЗДАТЕЛЬСТВО
ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ
МОСКВА 1959
АННОТАЦИЯ
Книга знакомит читателя с важным разделом
математики — линейным программированием, полу-
чившим в последние годы широкое применение в раз-
личных областях экономики, техники, военного дела.
В книге дается постановка общей задачи линей-
ного программирования, методы ее решения и при-
ложения к конкретным экономическим задачам.
Рассматривается применение теории линейного про-
граммирования к решению транспортных задач при
минимуме стоимости п минимуме времени перево-
зок, а также намечены nyin решения задачи с сче-
том обоих факторов.
Книга рассчитана на математиков, инженеров и
экономистов, занимающихся вопросами математиче-
ского планирования, в частности применением авто-
матических цифровых вычисли тельных машин к
этим вопросам.
Алексей Сергеевич Ларсов.
Что такое линейное программирование.
Редактор В. Д. Розенкнои.
Техн, редактор Д'. Ф. Врудно.	Корректор 3. В. Моисеева
Сдано в набор 30, VIII 1959 г. Подписано к печати It'XI 1959 р. Бумага S4x<10S1/32«
Физ. печ. л. 3,25. Условн. печ. л. 5,33. Уч.-изд. л. 5,40.
Тираж 15.000 экз. Т-ТЮ-10, Цена книги 1 р. 60 к. Заказ № 3554.
Государегвенпос издательство физико-матемагическои литературы.
Москва, В-71, Ленинский проспект, 15.
Первая Образцовая тиши рафия имени Л. Л. Жданова
Московского городского Сон- ..рхоза. Москва, Ж-54, Валовая, 28.
ОГЛАВЛЕНИЕ
Предисловие................................................................................. д
Введение ...................................................
Глава I. Некоторые понятия и определения линейной
алгебры ..................................................... 9
. §	1.	Понятие об m-мерном пространстве ................................................ 9
§	2.	Гиперплоскость и полупространство ................................................19
§	3.	Выпуклые многогранники ...........................................................21
§	4.	Система линейных неравенств.......................................................24
§ 5.	Наименьшее и наибольшее значения линейной формы
на многограннике........................................28
§ 6.	Сведение неравенств к равенствам при решении задач
линейного программирования ............................ 32
Глава II. Решение общей задачи линейного программиро-
вания ..........................  .	............36
§ 7.	Тождественные преобразования системы линейных ал-
гебраических уравнений..................................37
§	8.	Метод определения неотрицательного	решения системы
линейных алгебраических уравнений	..... 50
§	9.	Решение задачи линейного программирования.57
§	10.	Об одной задаче па минимакс................63
Глава III. Решение транспортной задачи по критерию сто-
имости ......................................................65
§ 12.	Основные решения транспортной задачи по критерию
стоимости .............................................67
§ 13.	Оптимальный выбор................................71
§ 14.	Инвариантность последовательности выборов эквивалент-
ным преобразованиям	матрицы	стоимости .......... 76
§15.	Алгоритм нахождения оптимального	решения.........77
Глава IV. Решение транспортной задачи по критерию вре-
мени .	. ....................................90
§ 16.	Постановка	и решение задачи .....................90
§17.	Решение задач транспортировки с учетом времени и
сюимосги	....	  101
Литература................................................ 164
1*
ПРЕДИСЛОВИЕ
В данной работе рассматриваются вопросы теории и методы
решения некоторых задач линейного программирования.
Работа предназначена для широкого круга лиц, занимаю-
щихся вопросами применения математических методов в орга-
низации и планировании производства.
Рассматриваются основы линейного программирования, при
этом приводятся только те сведения и доказательства, которые
необходимы для элементарного изложения методов линейного
программирования.
Работа возникла на основе лекций, прочитанных автором
в 1957 году для лиц, занимающихся решением задач линей-
ного программирования на электронных вычислительных ма-
шинах.
Член-корреспондент АН СССР Л. А. Люстерник внимательно
ознакомился в марте 1959 года с материалами лекций, дал
ряд ценных советов и содействовал выходу в свет этой работы.
Автор благодарит проф. А. А. Ляпунова и Н. С. Красиль-
никова за помощь в разрешении трудностей, возникавших
в процессе написания данной работы.
Автор особенно признателен редактору В. Д. Розенкнопу,
тщательная работа которого значительно способствовала улуч-
шению книги.
А. С. Барсов
ВВЕДЕНИЕ
Задачи дальнейшего развития производительных сил, улуч-
шения планирования социалистического производства, повыше-
ния экономической эффективности капитальных вложений в па-
шей стране с каждым годом приобретают все большее значение.
Многообразие возможных технических решений и путей
развития в современной промышленности, взаимосвязанность
различных отраслей народного хозяйства и другие экономиче-
ские проблемы делают поставленные выше задачи исключи-
тельно сложными.
При решении эт их задач существенную помощь могут ока-
зать математические методы и, в частности, методы линейного
программирования, а также современные технические средства —
электронные вычислительные машины.
Теория линейного программирования, возникшая в послед-
ние два десятилетия, в настоящее время получила широкое
практическое применение, особенно в вопросах организации и
планирования производства.
Первыми работами в этом направлении были работы члеиа-
корреснондепта АН СССР Л. В. Канторовича. В этих работах
приведены математические методы решения таких задач, как
задача повышения эффект явности работы транспорта, определе-
ния оптимальных производственных режимов, рационального рас-
кроя промышленных материалов и т. и.
В дальнейшем были созданы общие методы линейного про-
граммирования, как, например, симплексный, комбинаторный и
другие методы, которые эффективно используются для реше-
ния разнообразных оптимальных задач планирования. Разра-
боткой этих методов занимались Dantzig, Charnes и ряд со-
ветских и зарубежных ученых.
Линейное программирование охватывает методы решения
ряда оптимальных задач, имеющих дело со многими взаимо-
связанными переменными, подчиняющимися определенным
5
ограничивающим условиям. Постановку задач линейного про-
граммирования можно сформулировать следующим образом:
Имеется некоторая величина (например, стоимость, время),
являющаяся линейной функцией ряда переменных. Переменные
в спою очередь должны удовлетворять ограничениям, выражен-
ным в виде системы линейных неравенств или равенств.
Требуется отыскать такие неотрицательные значения пере-
менных, при которых величина, являющаяся их функцией, при-
нимала бы наименьшее (наибольшее) значение.
В качестве примера рассмотрим транспортную задачу. Эта
задача может быть сформулирована следующим образом:
Из данных т пупкиов отправления, в каждом из которых
имеется по «(. единиц груза, необходимо перевезти в каждый
из п пунктов назначения по Ь}. единиц того же груза
(Z = 1, 2, .. ., т; J = 1, 2, . . ., и).
Требуется спланировать перевозки таким образом, чтобы
затраты на последние были минимальны. Пусть xtj обозначает
количество груза, перевозимого из z-го пункта отправления
в у-й пункт назначения. В таком случае задача математиче-
ски сводится к нахождению таких неотрицательных значе-
ний Xjj, удовлетворяющих уравнениям
н	т
^lxij = al-	yXiJ = bj,
(=i
при которых общая стоимость перевозок
т п
становится наименьшей, при этом с,у есть стоимость перевозки
единицы груза из /-го пункта отправления в у-й пункт на-
значения.
В ряде практически важных случаев задача ставится так:
требуется спланировать перевозку груза из данных т пунктов
отправления в п пунктов назначения так, чтобы операция
транспортировки была завершена в кратчайший срок.
Другим примером применения линейного программирования
может служить следующая задача.
На многих заводах выпуск различных изделий или какой-
либо продукции производится на автоматических линиях. В этих
случаях могут возникать различные вопросы наиболее рацио-
нальной организации производства.
6
Пусть, например, цех располагает nt машинами (стайками)
для производства различных п изделий. Каждая .машина /-я
(7=1, 2, . . ., т) характеризуется определенным Ь- возможным
месячным рабочим временем, нормой времени /(у. на изготовление
одной единицы /-го изделия (/=— 1, 2...../г),	а также сто-
имостью с,-, затрачиваемой на изготовление одной единицы
того же /-го изделия на 7-й машине. Если цеху дано задание
выпустить в наступающем месяце определенное <ij количество
каждого из различных изделий, то возникает задача такой
организации работ, при которой задание будет выполнено при
минимальном расходе средств. Если через .у/;. обозначить
количество у'-х изделий, производимое на /-м станке, то по-
ставленная задача сводится к такому распределению загрузки
машин, чтобы удовлетворить условиям
т	и
и сделать значение общей стоимости
т а
S .-П/
। 7— 
как можно меньше.
В задачах линейного программирования условия, налагае-
мые на область допустимых значений переменных, определяются
системой линейных неравенств или равенств, при этом функция,
наименьшее (наибольшее) значение которой находится, явля-
ется также линейной функцией тех же переменных. Этот факт
и подчеркнут в названии линейное программирование.
Методы линейного программирования для определения опти-
мального решения требуют рассмотрения нескольких решений.
При анализе практических задач, например задачи рациональ-
ной загрузки станков или предприятий, при определенных
ограничивающих условиях переходу от решения к решению
соответствует последовательное рассмотрение различных произ-
водственных программ. Отсюда происходит название линейное
программирование.
Так как задача линейного программирования есть задача
на нахождение точки области, в которой функция принимает
наибольшее (наименьшее) значение, то, естественно, возникает
вопрос: почему нельзя обойтись известными классическими
методами решения экстремальных задач, например методом
Лагранжа?
7
Дело в том, что классические методы требуют существо-
вания частных производных функции в точке, где достигается
экстремум. Между тем .iiineiinan функция достигает экстремаль-
ного значения на границе области, где частные производные
не существуют.
Эго и послужило причиной создания новых методов реше-
ния экстремальных задач, к числу которых и относится линей-
ное программирование.
Практика решения задач линейного программирования по-
казывает, что при большом числе переменных для решения
таких задач необходимо применять электронные вычислитель-
ные машины, при этом задачи, на которые затрачивает человек
до педели, машина решает за две-пять минут. При очень боль-
шом количестве переменных эти задачи могут быть решены
только посредством электронных вычислительных машин.
Примером может служить задача определения оптимального
плана перевозок строительного песка к строительным площад-
кам г. Москвы. В этой задаче было задано 10 пунктов отправ-
ления и 230 пунктов назначения. Полученный па машине
«Стрела:> оптимальный план перевозок дал только за одну
декаду июня 1958 года экономию около 11°/0.
Ниже рассматриваются математические основы и методы
решения некоторых задач линейного программирования, в част-
ности транспортных задач.
ГЛАВА I
НЕКОТОРЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ
ЛИНЕЙНОЙ АЛГЕБРЫ
В этой главе излагаются основные понятия и определения
линейной алгебры /«-.мерного пространства, необходимые для
решения задачи линейного программирования.
§ 1. Понятие об m-мерном пространстве
Всякая упорядоченная тройка (аг я2, os) действительных
чисел может ......еометрическп истолкована как точка про-
странства. В соответствии с этим геометрическим представле-
нием в математике принято следующее определение: трехмер-
ное пространство есть множество всевозможных упорядо-
ченных троек а2, а3) действительных чисел*). При этом
говорят, что система чисел («г rz2, определяет точку Л!
в трехмерном пространстве с координатами аг, аг, а3 пли
вектор Р с компонентами а2, а3 в том же пространстве.
Для задания некоторых объектов, процессов или состояний
недостаточно трех действительных чисел. Так, определение по-
ложения твердого тела в пространстве требует шести коорди-
нат. В случае если район производит определенные промыш-
ленные и сельскохозяйственные товары, например железнодо-
рожные вагоны, автомашины, хлеб, молоко, спички и т. д.,
то для характерце гики промышленного и сельскохозяйственного
производства данного района требуется упорядоченная после-
довательность действительных чисел. Так, имея таблицу 1,
*) Аналогично множество всевозможных действительных чисел (я,)
есть одномерное пространство, геометрическим образом которого мо-
жет служить прямая; множество всевозможных пар действительных
чисел |<Тр <д2) еегь двухмерное нрос i рапс гво, iеометрпческим образом
которого может служшь плоскость.
9
можно сказать, что район № 2 ежегодно производит «21 тонн
угля, (7ОО тонн железной руды, о,, тонн стали, ап„ тонн
пшеницы.
Подобно этому, например, количество авиационного горю-
чего различных типов, используемых в данной стране, количе-
ство товаров различной номенклатуры, находящихся на данном
складе, также определяются с помощью упорядоченной после-
довательности чисел.
Т а б л п ц а 1
	Уголь tm/	Жел. руда (т)	С/па. 1ь (WJ			Лшеацца (07/
Район N-1	а„	а;г	а,а			о
Район 2	аг!	агг				
									
Район N-к		аь?.			ат
Эти примеры указывают на целесообразность рассмотрения
совокупности всевозможных упорядоченных последовательностей
из т действительных чисел, где т — любое натуральное число.
Известно, что упорядоченная система т действительных чисел
(«,, а . .., а.[, ат) называется т-лерныл вектором.
Числа ait /=—1,2, . . ., т, называю тся компонентами вектора
Р(п,, «2, . . .,
Векторы Р(«,, «2, . . ., ат) и Q (А,, Ь2, . .	1>гп) считаются
равными в том и только в том случае, если совпадают их
компоненты, стоящие на одинаковых местах, т. е. iipiia( — bj
для всех /—1,2, . . ., т.
Если нас интересует суммарная производительность двух
районов ио различным видам продукции, то, очевидно, она
может быть получена сложением соответствующих производи-
тельностей эт их районов*). Так, если производительность
района № 1 по каждому виду продукции определяется векто-
ром Р, («„, «12,	а района № 2 — вектором Р2 («21,
я2„, . . ., <т2т), то суммарная производительность этих районов
характеризуется вектором
Q(«» + «21> «12 + «22> •••> flIm + «2J-
-) Прои.знотительность в данном случае означает количество про-
дукции, выпускаемое за определенный отрезок времени.
10
Если производигельность района определяется вектором
P = P(tz1, а2,	<7т), то увеличение производительности
района но каждому из товаров в k раз можно выразить век-
тором Q, где Q = Q(A/?I, ka.„ . . katn).
Введенные определения являются обобщением известных пра-
вил действий над векторами трехмерного пространства. Распро-
страняя понятие трехмерного пространства на последователь-
ности действительных т чисел, получаем следующее важное
определение: совокупность всевозможных /и-мерпых векторов
Р(аг, а2,	с действительными компонентами называется
/п-мерным пространством и обозначается Р<т). По определению,
сложить два /«-мерных вектора Р и Q — значит получить тре-
тий вектор RP; Q с компонентами, равными суммам соот-
ветствующих компонент слагаемых векторов. Умножить век-
тор Р па число k- значит умножить каждую компоненту на
эго число.
Вектор Р(п,, «2, ..., «„) называется пропорциональным
вектору Q(Z\, /?2, ..., />„), если существует такое число k,
что b^ — ka^ bI — kai, =/го„. В этом случае P—ftQ.
Обобщением понятия пропорциональности векторов служит
понятие линейной комбинации векторов.
Вектор Р называется линейной комбинацией векторов
Р,, Р2, . . ., Р^, если существуют такие действительные числа
/2, ..., /2, что Р=.-/1Р1-|-/2Р2.-|-/?Ру. В этом слу-
чае z-я компонента вектора Р (/= 1, 2, ..., т) равна сумме
произведений г'-х компонент векторов Р2, Р2, ..., Р9 соот-
ветственно на /2,	...,
Система векторов Рг Р2, . ,.,РГ1, Рг называется линейно
зависимой, если хотя бы один из этих векторов является
линейной комбинацией остальных векторов.
Это определение эквивалентно другому:
система векторов называется линейно зависимой, если
существуют такие действительные числа kt, k2, kr, ио
крайней мере одно из которых отлично от нуля, что имеет
место равенство
^р, + ^Л+---+^А = о.
В противном случае система векторов называется линейно
независимой.
Если вектор Ро является линейной комбинацией векторов
Р], Р2,	Р„, то говорят, что Ро линейно выражается
через систему векторов jPy}, где j = 1, 2, . .., п. Понятно,
что если вектор линейно выражается через некоторую
11
подсистему дайной системы, то он будет линейно выражаться
и через систему—достаточно остальные векторы системы
взять с коэффициентами, равными нулю.
Обобщая эту терминологию, говорят, что система векто-
ров Q,, Q2, ..., Q, линейно выражается через систему век-
торов Рр Р2, Рн, если всякий вектор Q,, г—1, 2, ..., .s’,
является линейной комбинацией векторов системы {Р,},
У — 1, 2, . . ., п.
Рассмотрим в пространстве P,m> векторы:
i, (1, 0,	0,	. . .,	0),	I
i, (0, 1,	0,	. . .,	0),	|
i,„(0, 0,	0,	...,	1).	J
(В
Эти векторы называются ортами. Система векторов (1)
является линейно независимой, так как	/г212	.
. . . Ц- Аот1,я = 0, только если k,- = 0 для всех i = 1, 2, . . ., т.
Всякий вектор Р(«,, аг, ..., «„,) пространства Р'т) линейно
можно представить как
Аналогично, если в
выражается через векторы системы
(1), а именно
Р = Н’ (12^г + • • • + ат^т-
Можно показать, что всякая система
векторов пространства Р(т), со-
стоящая более чем из т векторов,
линейно зависима.
Так, если в плоскости из начала
координат выходят два вектора Р,
и Р не направленные по одной
прямой, т. е. линейно независимые
векторы, то любой третий вектор Ро
линейную комбинацию этих векторов,
трехмерном пространстве заданы три
вектора, не лежащие в одной плоскости и выходящие нз
начала координат, то любой вектор этого пространства выра-
жается как линейная комбинация этих векторов. Так, на
рис. 1 изображен случай, когда вектор Ро представляется
комбинацией линейно независимых векторов Рр Р2, Р8, которая
имеет вид
Р — Р : - — Р -4- — Р .
г о г 1 Г 2	2 1 3 s
12
В двухмерном пространстве двум линейно независимым
векторам Р, (ам, а21) и Р2 (а12, а22) соответствует определитель
«и «12
«21 «22
отличный от нуля.
Абсолютное значение этого определителя равно площади па-
раллелограмма, построенного на векторах Р, и Р2 (рис. 2).
Рис. 3.
В трехмерном пространстве три линейно независимых вектора
Р. («„, а21, «„), Р2(«12, а22, «,2) и Р,(л18, а22, «23)
образуют параллелепипед (рпс. 3). В этом случае абсолютное
значение определителя
<?п «12 а13
«2,	а22	а2.
а.<,	а,2	а2,
отлично от нуля и равно объему параллелепипеда.
По аналогии, если в /л-мерном пространстве заданы т
линейно независимых векторов
₽/(«./. «2у> •••- air •••> «,„/)> 7=1- 2.........т>
/= 1, 2, ..., т,
то, как показано в курсах высшей алгебры, определитель
Д11	«12	.. .	
«2,	«22	аи	а2ГП
«,Л1	«„12	. . .	^тт
отличен от нуля.
13
Пусть в /«-мерном прос i ранет во задано п произвольных
векторов
Р/(«ы> «2/, ••• аи......2> • ••- «;
i = 1, 2, . . ., т.
Образуем
(mX«)
из компонент этих векторов матрицу * **)) порядка
Р, Рг Р/ Р.
«12 ... ач- . . .
«21 «22 ... а2/ ... «2„
.................. llii	 • • 
,lmi m2 * * * (lmJ • ' • 1!тп
(2)
Столбцы этой матрицы, рассматриваемые как /«-мерные век-
торы, могут, вообще говоря, быть линейно зависимыми.
Максимальное число линейно независимых столбцов матрицы (‘2)
называется рингом этой матрицы Иначе говоря, ранг
матрицы (2) равен максимальному числу линейно независимых
векторов Ру, компоненты которых составляют ее столбцы.
Всякая максимальная линейно независимая система векторов
пространства Ptm| называется базисом этого пространства.
Пусть векторы Р,, Р2........ Р/_1, Р;, Р;+), Рп
образуют базис просiранегва Р'"'1, который назовем Л-бази-
сом. Тогда любой вектор Р этою просiранства может быть
представлен, п притом однозначно, в данном базисе в виде
линейной комбинации векторов Р-,	-1, 2, ..., т. Все ба-
зисы векторного пространства состоят из одного и того же
числа векторов.
Возьмем произвольный вектор Q, не принадлежащий базису
Р,, Р2, ..., Рт. Тогда, если вектор Q не равен нулю, то
в линейной комбинации
Q = аЛ + 7.2р2 + . . . + а._ 1Р/_, + а/Р7 +
+ «/+Лч, + ---+М\
имеется по крайней мере один коэффициент, отличный от нуля.
*) Здесь и в дальнейшем компоненты векторов Ру будем распо-
лагать в виде колонок матриц.
**) Всегда максимальное число линейно независимых строк мат-
рицы равно максимальному числу линейно независимых столбцов.
14
Пусть, маиримср,
представки, в виде:
а .^0, тогда вектор Ру Л-базнса можно
1	5,
P/ = 7.Q . р
— р.
Ч/.
—р/
а, 7
— 41р
а,- т
Исключим из /1-базиса вектор Р; и присоединим к оставшимся
векторам вектор Q. Система векторов Р>, Р2,	Ру_,, Q,
Р-|_„ Р„г снова является базисом. В самом деле, в силу
однозначного разложения любого вектора ио векторам базиса,
после исключения вектора Ру из Л-базиса, вектор Q уже ие
может быть представлен в виде линейной комбинации остав-
шихся векторов. Эго означает, что система векторов
Ри Р2, ..., Ру_, Q, Ру+1, ..., Рт является линейно неза-
висимой системой, т. е. образует базис.
//-базис, полученный из Л-базиса заменой некоторого век-
тора на вектор, не принадлежащий Л-базису, назовем базисом
однократного замещения по отношению к А-базису.
Пусть в w-мерном пространстве задано /z —1 векторов
Ро, Р,, Р2.....Ру, •  Р,г, которые в базисе Q,, Q2, . . ., Qm
имеют разложения:
Р> — 1Q1 + 40г + • • • + Мда
Р. - т "1/4 ‘4 а21Q2 4’ • • • 4" ат^по
Р2---"1“ ' ' ’ ~4
........................................ }	(3)
Py = fliyQi 4" •  • 4"йт/О/И’
P„==--"1HQi4-a2zzQ2 4- 
• 4-	
Образуем матрицу из компонент разложений (3)
Р„	Р,	...	Ру	...	Р„
![/’,	...	ах/	. . .	I
4	«2.	• • '	• • •	«2»	!
/>,.	«;1	...	atj	...	ain	|
i 4zz	4zzi	  •	l>mi	  ‘	tlmn
(4)
15
Допустим теперь, что векторы qt, q2, ..., qm образуют
новый базис в Р'т*. Пусть эти векторы имеют следующие
разложения в базисе Q,, Q2, Qm:
Ч) —9,А +72iQ2+   • +^iiQot>
Чг 9i2Qi 4“ Q22Q2 “Ч • • • “Ч Чт&т'
4m	4im^i + 42nf^z ~I- • • • “Ь”
Так как qp q2, ..., qm образуют базис, то определитель
9ц 912 ••• 9lm
921 Ч22 Чгт
Чт, 9m2 • • • Ятт
(5)
отличен от нуля.
Перейдем от базиса Q,, Q2, . . ., Qm к базису qp q2, . . ., qm.
Тогда векторы Ро, Р,, Р2,	Р,( будут иметь в базисе
qt, q2, . . ., qm коэффициенты разложения, вообще говоря,
отличные от коэффициентов разложения в базисе Q,, Q2,. . . ,Qm:
ро = ^i4i + ^42 + • • • + ^4ОТ.
р/ = «441 + «4'42 + •  • + «4/Ч„, (7=1, 2.....п).
Матрица разложений в этом случае имеет вид
ро	р1	•••	Р/	••• Р,,
7?;	...	«;,	...
'//,	щ,	...	«4	...
|л;	...	«;,•	...
,11 т   • "4/ • • • а'т,
(6)
Как известно, элементы матрицы (6) определяются через эле-
менты матрицы (4) и определитель (5) ио следующим форму-
лам:
Д°	А/
«7 = ^-.	(7)
16
где
<7„	Z’i 4i,!+i 4im
I  42 1 * * ' ^2,1-1	^2 ^2, i I I ’ ’ ’ 42m
4 mi * ' * 4m,i-t ^m 4m, i + i ’ * * 4 mm
4n  4>,	<hj 4i, ,4i	• • • 4im
'  421 •  • 4z, 1-1 ^2/ 4i, f-1-l	* * • 42m
4mi ‘ ‘ ‘ 4 m, i-i amJ 4 г, i + i • • • 4mm
(Z 2= 1, 2, . .., nr, 7=1, 2, ..., n).
В дальнейшем мы наряду с обозначениями этих определителей
через Д, Д’, Д7 будем пользоваться иногда обозначениями
вида:
Д = (ч> ч2 qm); ^;° = (qi ••• q,-iP<>q,+1 ••• q‘J;
A/ = (q, ••• q,->P/q,+1 ••• qj-
Рассмотрим пример определения разложений данной системы
векторов при переходе к новому базису.
Пусть и базисе Р,, Р2, Р, векторы Ро, Рр Р2, Р,, Р4, РБ, Р,
имеют разложения, определяемые матрицей
Р	Р	Р	Р	Р	Р	Р
012	8	4	5	6
15	1	0	0	—3	4	—1
]3	0	1	0	— 1	1	—2
2	0	0	1	2	1	1
Так как определитель,
Р Р Р
*41 S’ 9
составленный пз компонент векторов
— 34—1
Д = (Р4, Р;
Р.)= -1 1
1
= —18,
2
— 2
1
отличен от пуля, то векторы Р4, Р5, Р6 образуют базис.
17
Найдем разложения векторов Ро, Pt, Р2, Р3, Р4, Р5, Рв
в базисе Р4, Р5, Р„. Пользуясь формулами (7), получим
Рп Р, Р:	Р, Р4 Р *’ Р.
о*	z	з	4	&	б
£
Д
(P0P5Pe), (Р,Р5Р6), (Р2Р5Р6), (Р8Р5Р6), (P4P5PS), (Р5Р5Рв), (Р0Р5Р6)
(Р4Р0Р6), (Р4Р,Р6), (Р4Р2РД (Р4РаР6), (Р4Р4Р6). (Р4Р5РД (Р4РвР6)
(Р4Р5РО), (Р4Р5Р1), (P4PSP2), (Р4Р5Р3), (Р4Р6Р4), (Р4Р5Р5), (Р4РЬР2)
Производя соответствующие выкладки, будем иметь матрицу,
представляющую разложение данных век торов в базисе Р4, Р5, Ра:
Ро	Р,	Р2	р,	Р4	Р4	р9
8 "9	6	5 18	7 18	1	0	0!
__ 11 “у	1 X	1 Ts	.5 18	0	1	0
1	23	ф б	н "IS	1 — Т8	0	0	1
Как известно скалярным произведением двух векторов
Р и Q называется выражение, определяемое формулой
(Р - Q) = -ф а2Ьг —.. . —«Д- + • • • + ат11п^
где a-, bt— компоненты векторов Р и Q. Векторы Р и Q
называются ортогональными, если их скалярное произведе-
ние равно нулю. Так как матрицу порядка т)(п можно рас-
сматривать как (т X «фмерпый вектор, то скалярным про-
изведением матриц
ami amz.........а	mn ,1
	bit	l\z-	.. ... btn	
Bz=	h.2'	^?92 *	.. ..	* ^2П
	^mi	bmz 	,.ф7.	' ^mn
18
будем называть алгебраическую сумму всех элементов матрицы
«.А, а12/’12 ...... «„А,г
«?Al "2Л2..............«2,Л„
;.......... • .............. 
ат ^тхатг^тг...........ат/пп
и обозначать (Л-В}.
§ 2.	Гиперплоскость и полупространство
Из авали i пческой геометрии известно, что линейному
уравнению
А*, + А-'-2 + .4л = С	(8)
в трехмерном пространстве coomeic туе г
нам к вектору А (.4,, Л2, ,13).
Приведем уравнение (8)
к виду
плоскость, нормаль-
Рис. 4.
единичной длины, нормальный к
Ат -И Л> 4- —’ = 1. (9)
11\	1	‘12	(13	'
Плоскость, соотве г с твующая
этому уравнению, отсекаег
на осях координат отрезки
а,, я2, а, (рис. 4).
Кроме того, уравнение
плоскости в трехмерном про-
странстве может oiiiTb пред-
ставлено в векторной форме
(А°-Х) — //, где А ° — вектор
плоскости; X--текущий вектор, соединяющий начало коорди-
нат с точкой, принадлежащей плоскости; здесь (А°-Х)—скаляр-
ное произведение векторов А ° и X, равное по величине проек-
ции h вектора X на направление, определяемое вектором А°.
Величина h равна расстоянию от начала координат до плос-
кости. При h =- 0 плоскость проходит через начало координат.
Любой вектор X, соединяющий начало координат с точ-
кой плоскости, имеет одну и ту же проекцию h на направ-
ление А° (рис. 5).
19
По аналогии будем наливать гиперплоскостью или просто
Плоскостью в ///-.мерном пространстве множество всех точек
(/,, х2, хт), удовлетворяющих уравнению
Aixi +-42-г2+ •  • +^,Л = С-	(8')
Условимся говорить, что эта гиперплоскость нормальна к
вектору А (.4р Аг, ...,Ат}. Будем говорить также, что
уравнению
Рис. 5.
2
".
П1
соответствует гиперплоскость, отсе-
кающая на осях координат отрезки
длины п2, . . ., ят.
Наконец, векторное уравнение
(А°-Х) = Л в пространстве Р‘т)
определяет гиперплоскость, нор-
мальную к единичному вектору А0
и отстоящую от начала координат
на расстоянии h.
Прямая на плоскости делит последнюю на две части, каж-
дая из которых называется полуплоскостью. Из рис. 6 видно,
что прямая делит плоскость на две полуплоскости. Кроме того,
проекции Ос} векторов X концы
полуплоскости, меньше h—Oc,
которых принадлежат другой
полуплоскости, больше h.
Плоскость в трехмерном про-
странстве также делит все про-
странство на две части, каждая
из которых называется полу-
пространством.
Аналогично будем говорить,
что гиперплоскость в /п-мерном
пространстве делит это про-
странство на две части, каж-
дая из которых называется
которых лежат в одной
для векторов X,, концы
полупространством.
Пусть гиперплоскость в пространстве Р('7,> выражается
уравнением (А°.Х) = Л. Тогда для точек М одного из полу-
пространств проекций изображающих их векторов X на на-
правление А° меньше h, а для точек другого полупростран-
ства— больше h. Таким образом, одно из полупространств
20
есть множество векторов X, для которых выполняется нера-
венство (А°-Х)<>, а для векторов другого полупростран-
ства—(А°-Х)>/г. Сама гиперплоскость (А°-Х) = /г может
быть присоединена к одному из полупространств. Тогда все
множество точек т-мерного пространства будет разделено на
два вида: точки, для которых (А°-Х)^Л, и точки, для кото-
рых (А°-Х) > h (или в другом случае (А° -X) <> и (А°-Х)	h).
Пример 1. Дано полупространство — бх, Ц- 4х2—Зх2=С 5.
Определить, принадлежит ли ему точка (0, 0, 0).
Для ответа достаточно подставить значения х, = 0; х2 = 0;
Х, = 0 в неравенство. Будем иметь —5-0 Ц-4-0— 3-0 <5,
откуда следует, что точка
(0, 0, 0) действительно при-
надлежит полупрос।ранству
— 5х,	4х2 — Зх, eg 5.
Плоскость — 5х, -|-
4х2 — Зх, = 5 перпенди-
кулярна вектору А ( — 5,
4,-3) (рис. 7).
П р и м е р 2. Определить,
принадлежит ли точкадевяги-
мерного пространства х, = 0;	' llL' 7'
х2 = 4; х, = 3; х4 = —7;
х5=0; хо = О, х79; xg=l; х9 = 0 полупространству
4х, -> 5х2 — 7хя Ц- х5 — 2х6 Ц- 12х, — Зх9 11. Подставив
координаты этой точки в неравенство, получим 4-0Ц-4-5—
— 3-7 —7-0 4-0-1 —2-0 —9-12—1-0 —3-0=109 >11.
Следовательно, эта точка не принадлежит заданному полупро-
странству.
§ 3.	Выпуклые многогранники
Выпуклым телом называется такое тело, которое
вместе с любыми двумя своими точками содержит и весь
соединяющий их отрезок.
Примерами выпуклых тел могут служить круг, шар, куб,
угол, образованный двумя лучами, выходящими из одной
точки (рис. 8).
Пусть точки х и у являются общими для выпуклых тел
А и В (рис. 9). Тогда х и у принадлежат телу А, а поэтому
отрезок, соединяющий точки х и у, также принадлежит А.
Аналогично этот же отрезок принадлежит и телу В. Следо-
вательно, он принадлежит и общей части тел А и В. Эго
21
означает, что оощая часть или пересечение выпуклых тел
есть выпуклое тело.
Возьмем на плоскости многоугольник, лежащий по одну
сторону от каждой прямой, участвующей в образовании этого
многоугольника. Как видно из рис. 10,<z, этот многоугольник
является выпуклым. Действительно, любые две точки х и у
Рис. S.
такого многоугольника принадлежат ему вместе с соединяю-
щим их отрезком. Напротив, многоугольник, представленный
на рис. 10,6, не лежит по одну сторону от каждой прямой,
участвующей в образовании этого многоугольника. Такой мно-
гоугольник не является выпуклым.
Возьмем произвольную точку /VI, не принадлежащую вы-
пуклому многоугольнику (рис. 11,а). Всегда можно указать
такую прямую /’Q, что точка М и многоугольник лежат по
разные стороны от PQ. Для выпуклого многоугольника можно
построить множество таких пря-
мых, что каждая из них имеет
s'""° крайней мере одну обитую
/	точку с многоугольником, и
( Тело А ДДд Тело В >	J
\	vz’P--?-7	таких, что весь многоугольник
находится по одну сторону от
укаждой из них. Такие прямые
называются опорными.
Рис.9.	Так. на рис. 11,б прямые
AD, СП, Г)Н и FN являются
опорными. Опорная прямая может иметь с выпуклым много-
угольником общую часть, состоящую или из одной точки,
или отрезка.
В трехмерном пространстве тело, ограниченное плоскостями
и лежащее по одну сторону от каждой плоскости, содержа-
щей его грань, является выпуклым и называется выпуклым
многогранником. Примерами таких чел могут служить мно-
гогранный алмаз, призма и т. д. Опорной плоскостью вы-
пуклого многогранника называется плоскость, которая имеет
22
с многогранником по крайней мере одну общую точку, и
такая, что многогранник .нежит но одну сторону от этой пло-
скости. Опорная плоскость может иметь с многогранником
общую часть, состоящую из одной точки, называемой верши-
ной многогранника, из отрезка, называемого ребром, или,
наконец, из многоугольника, называемого гранью. Ясно, что
через каждую вершину и ребро многогранника можно про-
вести бесконечное множество опорных плоскостей, в то время
как через любую грань проходит только одна опорная пло-
ское 1Ь.
Ранее мы убедились, ч го общая часть нескольких выпук-
лых тел является выпуклым телом. Поэтому общая часть
нескольких многогранников есть выпуклое тело. Поскольку
плоскость есть выпук'юе тело, то пересечение многогранника
с плоскостью есть выпуклое тело и представляет либо точку,
либо отрезок, либо выпуклый многоугольник. Аналогично свой-
ствам выпуклых тел трехмерного пространства можно рассмат-
ривать свойства выпуклых тел» многомерных пространств.
Некоторые из этих свойств будут рассмотрены в § 4 и 5.
23
§ 4.	Система линейных неравенств
Пусть в двухмерном пространстве заданы п неравенств
вида
ai,x, + а,2Х2	(/=1, 2, ...,«)*).	(10)
Каждое такое неравенство определяет одну из двух полупло-
скостей с граничной прямой «^х,	а-2х2 = Ь;. Граничная
прямая ahx ai2x2 = Ь{ нормальна к вектору A, (aiv а!г).
Рис. 12 (и, б).
Всякая пара чисел (х,, х2), удовлетворяющая всем нера-
венствам системы (10), называется решением данной системы
неравенств. Иными словами, всякая точка плоскости (х^^,
координаты которой удовлетворяют системе (10), является ре-
шением.
Рассмотрим несколько примеров:
1.	Неравенство
-у- sC 1 или 2xt Зх2 ' 6
определяет полуплоскость (рис. 12,й). Этому неравенству
удовлетворяет любая точка, лежащая в .заштрихованной
части плоскости. Граничная прямая выражается уравнением
2х, Зх2 = 6 и нормальна к вектору А (2, 3).
2.	Два неравенства
2х 4-Зх2<6,
— х,+ х2<2
определяют часть плоскости, как изображено на рис. 12,(г.
*) Всякое неравенство вида ^/lxl <il2x2 г- Ь, после умножения
обеих частей его на —1 приводится к виду (10).
24
3.	Трем неравенствам
2х, + Зх2 < 6,
•'Л 4-	2,
— х, — Зх2	3
удовлетворяет множество точек плоскости, образующих тре-
угольник решении AFB (рис. 12,а).

Рис. 12 (в, г).
4.	Четырем неравенствам
2х,+Зх2<6,	(1)
-х,+ х2^2,	(2)
— х, — Зх2 ' 3,	(3)
Л’,	<4	И)
соответствует множество точек плоскости, образующее мно-
гоугольник решений ABCD (рис. 12,г).
5.	Семи неравенствам
2х1-|~Зх2<6,	(1)
х,+ х2<2,	(2)
—	х, — Зх2 so 3,	(3)
2х,	3,	(4)
—	-v,	< 3,	(5)
— Зх,+7х2<21,	(6)
х2 — 3х2=^3	(7)
25
соответствует то же множество точек, чго и в примере 4.
Неравенства (5), (6) и (7) могу г быть исключены без изме-
нения множества решении. При этом неравенства (5) и (6)
определяют граничные прямые, не имеющие с многоуголыш-
' ком АВСГ) общих точек. Прямая (7) имеет одну общую точку
с многоугольником и является опорной (рис. 12/)).
6. Система неравенств
2х, Зх. 6,	(1)
-х,+ х2^2,	(2)
-х,-3х2^3,	(3)
2х,	< 3,	(4)
-Зх,-2х2<-12	(5')
не имеет ни одного решения. Геометрически эго означает,
что не существует пи одной точки, координаты которой удов-
летворяют всем неравенствам (рис. 12,е).
Рассмотрение этих примеров приводит к следующим вы-
водам:
1. Система неравенств с двумя переменными может быть
совместна. Тогда существует по крайней мере одна точка
плоскости, принадлежащая всем полуплоскостям, определяемым
данной системой неравенств. Множество всех таких точек мо-
жет быть полуплоскостью, ограниченным и неограниченным
многоугольником, прямой или ее отрезком и, наконец, одной
точкой. Совокупность точек, удовлетворяющих системе нера-
венств, есть выпуклое тело.
26
2. Система неравенств может оказаться несовместной.
В этом случае не существует ни одной точки плоскости,
удовлетворяющей одновременно всем неравенствам системы.
Вез ограничения общности систему п неравенств в трех-
мерном пространстве можно записать в виде
+	(/== 1, 2,	л).	(И)
Как мы уже знаем, каждое из неравенств (11) определяет
полупространство с граничной плоскостью
«;1х, + at2X2 + ai,x, =
Совокупность неравенств (11) может оказаться совместной.
В этом случае существует некоторое множество точек трех-
мерного пространства, удовлетворяющих системе неравенств.
Это множество есть выпуклое множество и может представ-
ляться в виде полупространства, многогранника, плоскости,
мнш оу голышка, прямой, отрезка или, наконец, одной точки.
В случае совместности среди неравенств системы могут
быть и «лишние» неравенства, удаление которых не изменяет
множества решений данной системы неравенств. Эти. «лишние»
неравенства могут быть двух видов: 1 вид — неравенства,
граничные плоскости коюрых не имеют пересечения с множе-
ством всех решений системы; 2 вид — неравенства, граничные
плоскости которых являются опорными для множества решений.
Может оказаться, что в пространстве трех измерений нет
ни одной точки, одновременно удовлетворяющей всем нера-
венствам. В этом случае система неравенств называется несов-
местной.
Пусть в. ///-мерном пространстве задана система неравенств
а/гх, + ai2X2 + •  • + aimxm ' f’i (* = h 2, ..., /г).	(12)
По аналогии с трехмерным пространством будем говорить,
что каждое из неравенств (12) определяет в /«-мерном про-
странстве полупространство с граничной плоскостью
«к*. + а1гХ2 + • • • + “imXm =
Если в /«-мерном пространстве существует по крайней мере
одна точка М (х,, х2, ..., хт), удовлетворяющая одновре-
менно всем неравенствам, то система (12) называется совмест-
ной. Множество всех таких точек будем называть «много-
гранником решений).
Пусть в /«-мерном пространстве заданы две точки
М' (х(, х', ..., хт) и /И''(Х1, х", ..., х'т). Множество точек
27
И4 (хг хг, ...,хт), координаты которых удовлетворяют усло-
виям:
x1 = x'1-{-t (х'{ — х\),
*2 =-< + z « ~ О’
Хт = Х’,п + t (.х",п — О
при изменении параметра t от 0 до 1, называют отрезком,
соединяющим точки /И' и Л1". Являясь пересечением полупро-
странств, «многогранник решений/) есть выпуклое множество.
Это означает, что вместе с точками М’ и М" ему принадлежат
и все точки соединяющего их отрезка.
Неравенства, которые можно удалить из системы (12), не
изменяя множества ее решений, называю!ся зависимыми или
«липшими». Удаляя из заданной системы последовательно одно
за другим неравенства такого вида, получим подсистему не-
равенств, множество решений которой совпадает с множеством
решений первоначальной системы.
Удаление «лишних» неравенств является очень сложным
и трудоемким процессом. Одна из особенностей методов ли-
нейного программирования состоит в том, что для определения
наименьшего (наибольшего) значения линейной функции на
многограннике не требуется специального процесса выделения
«лишних» неравенств. Если системе неравенств (12) не удов-
летворяет ни одна точка те-мерпого пространства, то такая
система называется несовместной.
§ 5. Наименьшее и наибольшее значения линейной формы
на многограннике
Рассмотрим совместную систему линейных неравенств с двумя
переменными. Предположим, что мы исключили все «лишние»
неравенства 1-го и 2-го видов и гем самым выделили много-
угольник решений в «чистом виде» (рис. 13). Пусть, кроме
того, задана линейная функция двух переменных
/=с,х1Ц-с2х2.
Найдем среди множества точек (хр х2) многоугольника реше-
ний такие, которые придают линейной функции /= c1xi-}-cixt
наименьшее и наибольшее значения. Рассмотрим множество
всех точек (х , х2) плоскости, в каждой из которых функция
f^=clxl~\-clx2 принимает фиксированное значение / = /г
Множество таких точек есть прямая сtxt <2х2 = -/г Эта
28
прямая, как отмечалось в предыдущем параграфе, нормальна
к вектору С(с1;с2), выходящему из начала координат. Про-
ведем прямую F (рис. 13), нормальную к вектору С, и будем
ее передвигать параллельно самой себе в положительном на-
правлении вект ора С. Пусть при движении прямой F она впер-
вые встретится с многоугольником в вершине А. В этом
положении F' прямая F становится опорной. При дальнейшем
движении в том же направле-
нии прямая F пройдет через
вершину В и станет также опорной прямой. Так как направ-
ление вектора С (с,; г2) есть направление наибольшего возра-
стания линейной функции /= ctxt -ф- с2х2, то на опорной
прямой F' функция / принимает наименьшее значение, а на опор-
ной прямой F"—наибольшее значение среди значений /, при-
нимаемых на многоугольнике решений.
Таким образом, наименьшее и наибольшее значения линейной
функции /= с1х1 с2хг на многоугольнике решений дости-
гаются в точках пересечения этого многоугольника с опорными
прямыми, нормальными к вектору С (с,; с2). Пересечение опорной
прямой с многоугольником решений может состоять либо из
одной точки *) (вершины многоугольника), либо из бесчисленного
множества точек (в этом случае это множество есть сторона
многоугольника).
На рис. 14 изображен случай, когда линейная функция f
достигает наименьшего значения в каждой точке отрезка А1Аг,
*) Эта точка может оказаться в бесконечности.
29
в то время как наибольшее значение достигается в бесконечно
удаленных точках многоугольника.
Аналогично линейная функция грех переменных
4~ сгхг “Ь ctx> принимает постоянное значение на плоскости,
нормальной к вектору С (с(; сг\ с,). Направление С есть направле-
ние максимального возрастания функции / (рис. 15). Наибольшее
и наименьшее значения этой функции на многограннике решений
Р»с. 16.
большего— в точке D,
также достигаю гея в точках
пересечения этого многогран-
ника с опорными плоскостями,
нормальными к вектору С (с,,
Т2. с3); при этом на одной из
опорных плоскостей f дости-
гает наименьшего, а на дру-
гой— наибольшего значе-
ния. Пересечение многогран-
ника с опорной плоскостью
может представляться либо
одной точкой (вершина мно-
гогранника), либо бесчислен-
ным множеством точек (в
этом случае это множество
есть либо ребро, либо грань
многогранника).
Например, на рис. 16 изображен случай, когда / достигает
наименьшего значения в каждой точке грани ABQP, а наи-
30
j	Обобщением понятия линейных функций от двух и трех ие-
J ременных яи.1яе1ся функция вида / = ф- с2л\-ф- . .-феихп
ог// вещественных переменных хг, х2,. . ., л'„, называемая линей-
ной формой', здесь с,,	, с„ — вещественные числа.
Фиксируя значения линейной формы	/ = /2;...
j	f~f mi,i тем самым определяем в /z-мерном пространстве
гиперплоскости
/1 — <’1Х1 4“ Г2Л\ “4 • • • + СПХ,^
Л-а-п-НаН- • ~\~спх,о
Л/ -'--’А-г • •  4аа.
нормальные к //-мерному вектору С (с,, с2, с3). Обозначим через
/п11- наименьшее значение формы
/=С.Л', + СА+--- 4аа
на многограннике pemeiiiiii, а через /11ах— наибольшее зна-
чение. Так как вектор С определяет направление наибольшего
возрастания линейной формы /, то при f <ф/|П111 и при f ф>/тах
соответствующие гиперплоскости f — сгх3 -фс2х2 ф- . . . фсх„
не имеют пересечений с многогранником решений. С другой
стороны, каждая гиперплоскость/'==с1х1 4axz 4“ . . . -ф-фх^,
для которой /1П||1 «S/"	имеет общие точки с много-
гранником решений. Множес тво точек М (х3, Хг, . . . , х ),
и которых линейная форма / достигает наименьшего значения,
есть пересечение многогранника решений с опорной гипер-
плоскостью с1х1 -ф е2х2 -ф . . . -ф crlxn = /,1И11, нормальвой к век-
тору С (с,, с2, ... ,<?„). Аналогично, наибольшего значения /
достигает в точках пересечения многогранника с опорной
гиперплоскостью crv, -ф сгхг -ф . . . -ф спхп =/тах, также нор-
мальной к вектору С.
Пересечение многогранника решений с опорной гиперпло-
скостью есть вершина, ребро или «грань» многогранника.
Таким образом, оптимальное значение линейной формы
на многограннике решений достигается в точках, среди которых
всегда имеется по крайней мере одна из вершин. Поэтому
для определения оптимального решения достаточно выбрать
ту вершину многогранника, в которой линейная форма дости-
гает наименьшего (наибольшего) значения.
31
§ 6. Сведение неравенств к равенствам
При решении задач линейного программирования
Пусть задана система т линейных неравенств с п пере-
менными:
• • •+Я!Л <4
«21Л + «22*2 Н - • • • Н - (,2Г1ХН
+ а,2Х2 + • • • + <li,lXH
(12)
amiXi 4* ft«2x2 4* • • • 4* °тХ1Г^	,
определяющая в л-мериом пространстве многогранник решений.
Рассмотрим наряду с этой системой неравенств систему т
линейных алгебраических уравнений с п-[-т переменными:
а1>Х1 4" а12Х2 4" • • • 4* ,11ПХП + >Х1	-- 4
«214 + а22Х2 +•••+ ^2ПХП + Н2 =4.
e;ixi 4* ai2x2 4 •  • 4 (Чпхп 4* и, — bi’
amiXl 4" ат2Х2 4- • • • + ампхи 4" V-,n — bm- ,
Покажем, что всякому решению х\, х)’, . . . , х° системы не-
равенств (12) соответствует определенное решение х®, х“,. . ., х°;
Р-2, • • • > 14 системы линейных алгебраических уравнений
(12'), причем дополнительные переменные удовлетворяют
условию р’^гО, р“ 0, . . . ,	53 0. В самом деле, если
х°, х’, ... , х® есть решение системы (12), то имеют место
неравенства:
Обозначим через:
Х = /’> — XXX ".XX • • • ~! ",,Х)>
^ = /’2 — К-ХлХт • • • Х"2ХХ
«Х + •••X ",-Х)’ J °27
X = X — XX -I- °,ИХ X • • • X- %Х)- 1
Тогда, во-первых, pj :?= О, р’ 5= 0, .. . , р”; Дэ 0; во-вторых,
система чисел х°, х", . . . , хл; р'>, р",..• • , X- как следует
из (12"), есть решение сис гемы линейных алгебраических уравне-
ний (12').
Докажем, наоборот, что всякому решению xj, х?, . . . , х“;
р°, р", . • • , системы уравнений (12'), удовлетворяющему
условию р, 3= 0, р1’ >0, ,.. , р)л 0, соответствует опреде-
ленное решение системы неравенств (12). В самом деле. По-
скольку система чисел х", х?, . . . , х“; pj, р", . . . р“л есть
решение системы (12'), то можно записать:
«>ХХ«.ХХ  • • Х«.,ХХи? = Х
"т1х° X w." X • • • X "«,Х» X X=ьт-
Так как по иредноложепшо числа ц?, |1°, ... , неотрица-
тельны, то имеют моею неравенства:
X X • • • X «.„X < X
атА X %Х X • • • X атпх°„ X-
т. е. система чисел х“, х°.......х" есть решение системы
неравенств (12).
Таким образом, установлено взаимнооднозначное соответст-
вие между множеством всех решений xj, х", ... , х„ системы (12)
и множеством решений xj, х?, ... , хр’, р°, ... , рл/ системы
(12'), причем дополнительные переменные р°, р’, . .. , р“; не-
отрицательны.Таким образом, задача решения системы линейных
неравенств вида (12) сводится к решению соответствующей
системы линейных уравнений вида (12').
В задачах линейного программирования нас будут интере-
совать решения системы неравенств, удовлетворяющие условию
2 А. С. Bapcoi
33
х Дд 0, х рд О......х 0. Такие решения называются не-
отрицательными. 11ооюму, так как решение системы нера-
венств сводится к решению соответствующей системы линейных
алгебраических уравнений, io отнпм из важных вопросов
линейного программирования является определение неотрица-
тельных решений системы линейных уравнений.
Пример. Требуемся определить неотрицательное решение
системы неравенств:
2.v, ' з.с:,- в.
— М- -д--2,
— -Д — 'X 3-
Вводя дополнительные переменные	'х О, g2 " - О, |18 -X О,
получим систему уравнении:
Зх2 —JJ.J	’ 6,
— *.+ х2 +н2	=--=‘2,
— %! — Зл'2	—3.
Всякому неотрицательному решению этой системы уравнений
соответствует определенное неотрицательное решение исходной
системы неравенств, и наоборот. Так, например, неотрицатель-
ному решению хх — 1; х2 = 1; [Л, — 1; р, -- 2; р3 = 7 системы
уравнений соответствует неотрицательное решение xt = 1;
,х2= 1 исходной системы неравенств.
Заметим, что если система неравенств несовместна в области
неотрицательных решений, ю соответствующая система линей-
ных уравнений не имеет ни одного неотрицательного решения.
Известно, что наименьшее (наибольшее) значение линейной
формы на многограннике, определяемом системой неравенств,
достигается в определенной вершине многогранника решений.
.Можно показать, что каждой вершине многогранника решений
отвечает неотрицательное решение соответствующей системы
линейных алгебраических уравнений, причем по крайней мере
одна дополнительная переменная равна нулю. Дополнительные
переменные р, 5» 0, ,и2	0, . . . , р;л Дл 0, вводимые в систему
неравенств, можно иллюстрировать геометрически.
Рассмотрим многогранник решений системы неравенств:
«>1Х1 + «12*2 + ’ ’ • + М» ''Л.
«7п1*1 Ч- атг*г Ч~ • • ' Ч- атпхп
34
Пусть имеется одно из неоiрицательных решений х°, х®, ..х®
системы неравенств. Ему соответствует точка 7И(х", ха,. . . , х’),
принадлежащая многограннику решений.
Пусть h; обозначает расстояние от точки Л1 до z'-й гипер-
плоскости. Значения дополнительных переменных:
I1!	("и'Ч 4~ "12Л’44 • • • 4“ (>1ПХи^
К. = — («„„-< + ат2х} + • • • + «„„X)
пропорциональны рассюяния.м от точки (х", х", . . . , х’) до
граничных гиперплоскостей:
 • • + «.Л = 4-
V, + « + • • • + ПтпХп = f’m-
Действительно, по определению расстояние от точки М до Z-й
гиперплоскости равно
(/= 1, 2, З....М
V + ‘i’h + • • • +
откуда п следует, чю:
Р-i -- 4 V "Е +	+ •  • + (О;>
Р;-------Г rt/T + 'гб Д • •  +
Pm —~ hm У а;,п + (,т. Я" • • • 4’ а',гт-
ГЛАВА II
РЕШЕНИЕ ОБЩЕЙ ЗАДАЧИ
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Линейное программирование — это раздел математики,
в котором рассматриваются методы решения следующей за-
дали: задана система т линейных алгебраических уравнений
с п переменными:
+ в12Х2 + • • • +	+ axnXn
«21Х1 + «22-4 +•••-]- a./Xj + • • ’ + Я2,ЛП
+ а1гХ2 + ’ ’ ’ + "ijXi + • • • + ai„Xn
= Л,, '
amiXI + Vi + •  • + nmixi + • • • + атХп ~ Ьт ,
и линейная форма / тех же переменных
/===cixi 4- c,x2 Ц- .. . +	• • • -!гспхп- (14)
Требуется средн решений системы (13) найти такое неотри-
цательное решение, при котором линейная форма / принимает
минимальное значение *). Такое решение будем называть
оптимальным решением данной задачи.
В этой главе рассматривается метод определения одного
из неотрицательных решений системы (13), а также один из
алгоритмов решения общей задачи линейного программиро-
вания.
*) Аналогично формулируется задача для нахождения неотрица-
тельного решения, при котором / принимает максимальное зна-
чение.
36
§ 7. Тождественные преобразования системы
линейных алгебраических уравнений
Пусть задана система (13), содержащая г линейно неза-
висимых уравнений и разрешенная относительно г переменных.
Без ограничения общности можно считать, что система раз-
решена относительно первых г переменных из первых г урав-
нений:
Система уравнений (15) в сокращенной записи имеет вид
п
= — ( 2 «,7-v/, i = 1, 2, . . г. (15')
1~г-\ 1
Предположим, что свободные члены /о в уравнениях (15) не-
отрицательны.
Каждое из уравнений системы (15) можно рассматривать
как проекцию векторного уравнения
2 ' Л’; Ро
(16)
на векторы Р,, Р5, ..., Рг, где Р1--Р, (1, 0, ... 0);
Р2=^Р2(0, 1, ... 0); ...; Рг=.Рг(0, 0, ... 1). Векторы
Р Р2, ..., Рг образуют базис в г-мерном пространстве. При
этом матрица разложений векторов Р„, Рг Р2, . . ., Рг, . . ., Р„
в базисе Рр Р2, ..., Рг представляется в виде
Р.Р,-
I
1
.Р,...РгР„Рг+1 •• Р/ • -Р„
Ь„
(iir+i
1  hi air^		<‘ij		ai,t
'	1 'hr "r, ...	•	“ri	
(17)
3?
Допустим, что совокупность векторов Рр Р„...Рг, Рг+1, Рп,
входящих в уравнение (16), образует несколько базисов г-го
порядка, отличающихся один от другого хотя бы одним
вектором. Будем называть каждый из этих базисов собствен-
ным базисом.
Пусть Л,, Д2, . . ., ДА„ ...—собственные базисы системы
векторов Р,, Р2,	Р,, Рг; Рг+].........Ру, Р,;. При
переходе от базиза к базису все коэффициенты уравнений (15)
будут преобразовываться ио формулам (7) предыдущей главы.
Система (15) при этом будет переходить и эквивалентные ей
системы, т. е. в системы с теми же решениями.
Базис А будем называи, положительным но отношению
к ненулевому вектору Ро, если Ро представляется в этом базисе
Г
в виде Р, - -^jp,P,', Р, Г'О. Как видно из уравнений (15),
I -- -1
базис Л, содержащий векторы Рк Р........... Рг, соответствую-
щие разрешенным переменным, является положительным, так
как по предположению /?;- = 0. Переменные . ,хг), относи-
тельно которых система (15) разрешена, называются основ-
ными, а остальные — неосновными. Решение системы, полу-
чаемое приравниванием неосновных переменных нулю, назы-
вается основным.
В силу теоремы об однозначном разложении вектора
в каждом базисе основное решение определяется однозначно
на любом Собственном базисе.
В дальнейшем мы будем рассматривать системы линейных
алгебраических уравнений только в собственных положитель-
ных базисах. Поэтому для сокращения письма слова «собст-
венный» и «положительный» опустим.
Рассмотрим систему (15). Определим правила перехода от
одного базиса к другому. Для этого воспользуемся ма-
трицей (17).
1. Находим один из столбцов у (г-] - 1 -ij-мсп), у кото-
рого среди коэффициентов ц1у, «2у, . . ., п; /, . . ., arj (1 egZsCr)
при неразрешенной переменной л-у имеются положительные
коэффициенты') (случай, когда такого столбца не существует,
рассматривается в § 8).
Пусть эго будет столбец у).
И. Определяем	но всем /, для которых «/уУ по-
ложительны.	'7'
*) Учитываются знаки коэффициентов, находящихся в скобках, при
записи уравнений в виде системы (15).
38
Пусть одно из min отношений будет при i Элемен г ai
назовем /таре тающим по о i ношению к системе (15).
111. Разрешим /(-е уравнение относительно переменной Ху
и подставим ее выражение в остальные уравнения системы (15).
При этом система (15) перейдет в эквивалентную ей си-
стему (18):
а группа векторов Pr Р,, . . P;i_,, Ру, Р,н.,, . . ., Рг станет
новым базисом И.,. В самом деле. Из (18) следует, что эти
векторы образуют базис, гак как соответствующий им опре-
делитель отличен от нуля
Р. Р2 - Р(,-> Р/, Р, .. - Р,
а
а
а
и,
Этот базис положительный,
члены неотрицательны,
имеют вид
потому
Действительно,
что
новые свободные
свободные члены
/ Ь;
Ь;,
,l/t h


Если aiji 0, то по правилу 11
bi'
— и свободный член
39
неотрицателен; если же «1;-	0, то свободный член опять
пестрина 1е.тен.
Преобразование системы (15) в систему (18), определяемое
правилами 1, 11, 111, называй гея тождественным или симплекс-
преобразование м.
Из определения тождественных преобразований следует',
что система линейных а.и ебраических уравнений типа (15)
может быть подвергнута этим преобразованиям всякий раз,
если в правых чаС1Ях имеются положи тельные коэффициенты
при переменных. 11оследова 1елыюсть тождественных преобра-
зований системы линейных алгебраических уравнений может
быть геометрически истолкована как последовательное разло-
жение векторного уравнении, соотнсчствующего эк>й системе,
в различных положительных собственных базисах однократного
замещения.
Имея в виду использование тождественных преобразований
для решения основной задачи линейного программирования, мы
рассмотрим их при следующем дополнительном условии.
Пусть последнее г-е уравнение системы (15) допускает
бесконечную последовательность тождественных преобразований
этой системы *). Это означает, что какое бы число тождест-
венных преобразований мы ин произвели, в r-м уравнении
всегда имеются положительные коэффициенты при переменных
в правой части, а разрешающий элемент при каждом преоб-
разовании этому уравнению не принадлежит.
Последовательное hi тождественных преобразований соот-
ветствует последовательность П,—► Л2—>- Л —>. . . переходов
от базиса к базису. Так как при конечных г и п существует
конечное число различных базисов, то в последовательности
—> Аг—> А3—. должны быть возвращения к уже встре-
чавшимся базисам. Будем говори п», что в этом случае имеет
место «зацикливание».
Если при каждом тождественном преобразовании наимеиь-
. ( Ь, )
шее отношение min/ — свободных членов Ь,- к соответ-
> I "щ./
стиующим коэффициентам «,д, где il{ — номер столбца, содер-
жащего разрешающий элемент щд, отлично от нуля, то
значение свободного члена в r-м уравнении системы (18)
с каждым шагом только убывает, что видно непосредственно
из выражения этого свободного члена. Выбор базиса одно-
*) Рассуждения, проводимые ниже, справе.иушы для любого /-го
уравнения системы (15) (1 i щ гр
40
значно определяет значение свободных членов системы урав-
нений, поэтому разным базисам соответствуют разные сово-
купности свободных членов, и наоборот. Поэтому в этом случае
возвращение к одному из ранее встречавшихся базисов невоз-
можно, а следовательно, не может быть и бесконечной последо-
вательности преобразований. Эго означает, что после конечного
числа преобразований или все коэффициенты при неизвестных
справа в r-м уравнении становятся неположительными,
(г-]-1 sg л), или разрешающий элемент при
преобразовании оказывается принадлежащим этому
Если же, начиная с некоторого преобразования,
щий элемент принадлежит уравнениям с нулевым
членом то значение свободного члена в г-.м
некотором
уравнению,
разрешаю-
свободным
уравнении
остается неизменным. Действительно, из последнего уравнения
системы (18) видно, что вычитаемое в выражении
свободного
члена Ьг — ат,---- в этом случае равно нулю. В
виях возникает возможность зацикливания.
этих усло-
Гиперплоскость, проходящую но крайней мере через два
базисных вектора, назовем базисной гиперплоскостью.
Наличие нулевых свободных членов в уравнениях преобра-
зуемой системы означает, что вектор Ро принадлежит одной
или нескольким базисным гиперплоскостям. Следуя принятой
is литературе терминологии, будем говорить, что в последнем
случае имеет место вырождение.
Таким образом, необходимым условием зацикливания
является существование вырождения.
В качестве примера рассмотрим систему уравнений:
х_ = 2-(2а-4 + х6),
Хг = 3 — (Зх4—%,),
х3 = 2 — ( д-4-ф-2л-5).
Соответствующее векторное уравнение имеет вид д^Р
-ф- Д2Р2 Ц- х,Р3 — Р„ — (л-4Р4-]-х5Р5). При этом компоненты
векторов определяют матрицу
Р. Р2 Р, Ро Р, Р5
10 0 2 2	1
0 1 0 3 3 —1 .
0 0 12 1	2
Векторы Р,, Р,, Р3, Р4, Р5 (рис. 17, о) образуют несколько
базисов, например базисы Рр Р2, Р3 и Р2, Р3, Р4. Базису
41
Р], Р2, Р3 соответствует основное решение = 2; xs — 3;
Л'3=2; х4 = 0; xs— -0. В этом случае вектор Ро представ-
ляется линейной комбинацией с положительными коэффициен-
тами
Р|) — 2Р,ЗРг —2Ра.
Геометрически это означает, что вектор Ро «пронизывает»
параллелепипед, построенный на векюрзх Р4, Р2, Р3 (рис. 17,6).
Представим те же уравнения в ба.шее Р„, Р3, Р4. Для этого
произведем тождественное преобразование. В колонке при
Рис. 17.
переменной х4 имеются положи тельные коэффициенты. Находим
min^~; у; . Принимаем за разрешающий элемент коэф-
фициент при лг4 в первом уравнении. Разрешаем это уравнение
относительно х4 и полученное выражение подставляем в осталь-
ные два; при этом уравнения принимают вид:
л\ ~а-5
-v,	1 - (— 7 л', - Г ч Л’з) •
Из последних уравнений следует, что в базисе Р2, Р3, Р4
вектор Ро представляется в виде Ро = 0 • Р„ Ц- Р3 Р4. В этом
случае имеет место вырождение, так как вектор Ро находится
в базисной плоскости, определяемой векторами Р3 и Р4,
поэтому Р лежит на грани параллелепипеда, образованного
векторами Р2, Р3, Р4 (рис. 17, в). Заметим, что если бы мы
нарушили правила тождественных преобразований, то пришли
бы к базису, в котором Р„ не может быть представлен неот-
рицательной линейной комбинацией векторов базиса. Наири-
42
мер, если за разрешающий элемент принять нс тот, которому
/ 2 з 2 \
соответствует min I 0-; -у’, у 1 , а коэффициент при перемен-
ной х4 в третьей строке, то после преобразования уравнений
будем иметь:
** =	2 —( х, 4 -2x0,
х,=-2-(-2х3-Зх5),
лг2 == — 3 — (— Зх,— 7x0.
Из этих уравнений следует, что в базисе Рг Р2, Р3 вектор
Ро представляется отрицательной комбинацией, содержащей
отрицательные коэффпциенгы
Р„ - - 2Р, - ЗР2 + 2Р4,
а решение оказывается неположительным:
х,=—2;	х2—-— 3;	х3 = 0; х4 = 2; х5 = 0.
В этом случае вектор Ро не пересекает параллелепипеда,
построенного на векторах Р,, Р2, Р4 (рис. 17, г).
Таким образом, нарушение правил определенных выше
тождественных преобразований может привести к отрицатель-
ному базису.
Рассмотрим пример системы уравнений, тождественные
преобразования которой могут привести к зацикливанию:
х, . И ( х4 —х6 — хв 4-3x0,
л-2	0 — ( 2х4 -- х5 — ух6 -л'7) ,
л:3 --- 1 — (л\ 4~ х. 4- Зхв — 8х,).
Будем рассматривать преобразования этой системы относи-
тельно третьего уравнения. В этом уравнении коэффициент
при х4 положителен и ранен единице. Среди отношений
/ 0	0	! \	„
l~j-; у-; у- \ отметим первое. Оно является одним из наимень-
ших среди этих отношений. Поэтому за разрешающий элемент
можно принять коэффициент при переменной х4 в нервом
уравнении. После разрешения первого уравнения относитель-
но х4 и подстановки выражения х4 в два других уравнения
получим преобразованную систему:
х4 = 0 — ( х, —х5 4- хв 4-3x0,
х2 = ° — ( --2.V, -4 х5 -П у хв — 5х7) ,
Х3 — 1 — (—X, 4-2х5 4- 4хв — 11X0.
43
В последнем уравнении снова имеются положительные коэффи-
циенты при переменных в правой часик например при х.
Разрешающим элементом в этом случае является коэффициент
при х5 во втором уравнении, так как пип ^у; -^-1 соответ-
ствует второму уравнению. Проведем тождественные преобра-
зования, соот ветствующие новому' разрешавшему элементу.
В результате получим систему:
*	5 = 0 — ( — 2*. -Г х2 + 4 *в — 5х7) ,
*	4 = 0 ~ “ *1 "Г *2 Ч- 4 Х« ~ ~Х^ ) ’
•	v,	1	(	3.V, 2ЛУ ; л„ . х;).
В третьем уравнении снова имеется положит единый коэффи-
циент при хв, при этом за разрешающий элемент .можно при-
нять коэффициент при переменной л'в во втором уравнении.
После тождественно!о преобразования будем иметь:
х6 0 - (- 2х, + 2х, + 2л-„ - 4х,),
х5 0 — ( х, — 2х2 - Зх4 + х7),
х3 = 1 —(	5х, — 4х2 — 2х44-Зх_7).
Продолжим последовательность таких преобразований, каждый
раз подчеркивая в трет ьем уравнении один из положи тельных
коэффициентов и выделяя жирным шрифтом соответствующий
ему разрешающий элемент-. 1? результате получим выражения
исходной спсгемы уравнений в различных положительных
собственных базисах:
Д',.	О	( х, 2.с. Зх4•	х5),	'
х6О -- (2х, — (>х2 - - 10х4 + 4х5),	.
х3	1	Т.П-,	; 2х;;	 7х4 — Зх5).
х, =- 0 — ( — Зх2 - - 5х4 - J - 2х5 -1г 4 х„) , j
х, = 0—(х;-ф2х4 —х5~у х6) ,
х3=1—(8х2-|-17х, —7х.- хв). )
*. = 0 — (х4 — х5 — хв-|-Зх7),
*2 = 0—	(2*4 — *5— 4	}
*3 = 1 — (*4 + *3 “Г ЗЛ'6 — 8*,)- j
44
Как видим, после шести тождественных преобразований мы
возвратились к исходной сиоеме уравнений.
Таким образом, последовательность тождественных преоб-
разований в базисах
ррр —> р р р * 1Г 2*3	* 4* 2 3	Р5РЛ  РвР5Р, — Р7РвРз — Р.Р,Р. — —> Р1Р2Р3 приводит к зацикливанию.
Однако наличие вырождения не обязательно приводит
к зацикливанию, что следует из приведенного ниже примера:
х, = 0 —( х4 —2х54-4хв4- х7 —Зх84~ х9),
х2 = 0 —(	2х3 — луф- хв — 2х7 — 2х8 4~ 4х0),
х, = 0 — ( — .	+ 2хъ — К + Зх7 — 4л’з ’Г XJ>
0=1—( Зл\— хъ — 2х,-|- -v, У о л\4
В последнем уравнении коэффициент при неремепоиой х4
положителен, а за разрешающий элемент можно принять
коэффициент при х4 в нервом уравнении.
Проведя тождественное преобразование, будем иметь:
Л- 0---(	х,— 2х5+ 4х8 -ф х, —Зх8+ х,),
х2 = 0 — (— 2х, -J- Зхэ — 7х„ - - 4х, 4- 4х8 -J- 2х„),
xs = 0 — ( х, -4 х8 -4 4х7	7х8	-4 2х0),
0=1 — (— 3xt ~4 5х5 — 14хв — 2х, ~4 8х8	2х0).
Продолжая этот процесс, получим:
„	/2,1	7	4	, 4	,	2 \
xs — 0	( з -vi 4 з	х2 з хв	-	х, Ц- з	х8 4	з	х9 \	,
х4 = 0— (—уХ,	,2	2	5	1	, 7	\ + 3	з	л'«	3	А’ 3	%8 + з ’
х3 = 0 — (	х, 0 = 1 — ( 4- х, • \ Затем xi ~	~4 Х* х5 = 0-(-±х1	+ А’в “Ь 4xi	7л'в 4~ 2xs)> <5	7	, 14	, 4	16	\ ~ “з л’2	3 Ав “Ь 3 х7 + 3 х8 3 хэ) ’ , 1	,1	7	, 2	\ + Т *s + Т xi	4	xs + у Х9 J	> , 1	,1 6	3	। 4' \ 4~~3	+ у х. з Л'«	3	А8“Г з J	>
*4 = 0— ( Y>Xi О	1	(	10 °=1 — 1--Х.	, 2	, 5	3	39	. 38 \ 4~ з хг “Ь 12Л'3	12Ae	12А'8-1~ 12 Х*) ’ i>	14	42	. 114	92	\ ~3Xs’~12A’»	12А<>Т 12 Х8 ЦЛ'»1-
45
В последнем уравнении положительный коэффициент при .ф
одновременно является п разрешающим элементом, так что
бесконечной, последовательности тождественных преобразований
не образовалось. Таким образом, вырождение не привело
к зацикливанию.
Произведя тождественные преобразования, соответствующие
114
разрешающему элементу а48 — ~ру и положив значение неос-
новных переменных равным нулю, мы найдем одно из основ-
ных решений исходной системы уравнений:
х, = 0; л'2о; х3=0; л'й^0; х,=0;
___13	__ 4	___ 7	.  _4
731 х-, 3s ’	38 ’ A’s — 38 •
Отметим, что построение примеров с зацикливанием пред-
ставляет большие трудности, так как для осуществления
зацикливания коэффициенты системы линейных уравнений
должны удовлетворять большому числу условий, п только
тщательный подбор коэффициентов может привести к обра-
зованию цикла.
Покажем, что при наличии только двух уравнений
п	\
X, = о - («13х3 ф щ4х4 ф ‘4jxjY
Г	(19)
Х2 Ь (cZ23A'j ф TZ24.C4 ф П2уХу)
у.-.т	>
зацикливания быть не может. Матрица векторов, соответствующих
системе (19), имеет вид:
Р, Р2 Ро Ps Р4 Ру
110 0 <zis п14 щЛ
I 0 1 b (1г>з п24 п2у
По допущению b > 0. Тоща векторы Р, и Р2 образуют базис. Значе-
ние компонент вектора Р3 в этом базисе можно представить опреде-
лителями
Пусть л23 и л13 больше нуля. Это означает, что уравнения (19) можно
подвергнуть преобразованиям, переходя от базиса Р,. Р2 к базису
Р3, Р2 и принимая элемент щ. за разрешающий. В новом базисе
Р3, Р2 коэффициенты уравнений (19) принимают значения, определяемые
по формулам (7) предыдущей главы. Так, значения коэффициентов
46
при переменной х4 будут иметь вил:
’ II «14 0 I
в первой строке —	, ,
А I <?24 1 (
1 I а<, <7,11	. I а., 0 I
во второй строке 13	, где А =	, .
А | п23 п241	| rt23 1 |
Если числители этих выражений положительны, то в базисе Р„, Р2
коэффициенты при х4 положительны. Так как наименьшее отношение
для системы (И)) снова приходится на первое уравнение, то, принимая
коэффициент при х4 в первом уравнении за разрешающий элемент,
можно повторить преобразование системы уравнений, перейдя от базиса
Р3, Р2 к базису Р4, Р2.
Допустим, что после каждого преобразования можно пронести
следующее так, что последовательность базисов
Р,, Р2 -- Р3, Р2 - Р4, Р2 — ...	> РА, Р2 — Р„ Р2
образует цикл. Тогда каждый из определителей в следующей после-
довательности:
(Р,Р2) (Р3Р2) (Р,Р2)
(Р,Р2)'
(Р/г->Р2)	(Р*Р2)
(20)
\	\	\	|	3 Л |
(Р,Р3) (Р3Р4) ... (Р*_2РА_г) (P*_,Pft) (PftP.)
должен быть положительным (определители нижнего ряда соответ-
ствуют последовательности положительных коэффициентов во втором
уравпешш, определи гели
верхнего ряда — последова-
тельности разрешающих эле-
ментов), В данном случае
векторы Ру двухмерные, и по-
этому значение каждого из
определи гелей в последова-
тельности (20) как но знаку,
так и по величине совпадает
с соответствующим вектор-
ным произведением. Тогда
требование положительное ги
всех определителей (20) рав-
носильно требованию,
вектор "
торами
острый
между
чтобы
Р3 лежал между век-
Р( и Р2, об| Ш yiOIIU IM II
угол; вектор Р4 —
векторами Р3 и Р2
Продолжая эти рассуждения, получим, что век гор Р, должен
между векторами РА. и Р2, чего быть не может (рис. 18). Про-
лежать	,	....
тиворечие легко может быть обнаружено и аналитически. Запишем систе-
му векторных равенств.	р  а р _. 2 р
^5 --- ^54^4 4 ^52^2»
(21)
г. Л
Pt^. ,,Рь4
47
Умножая каждое из равенств (21) векторио один раз справа на Р2,
а другой раз с.тсна на в,торой вектор, входящий в правую часть каж-
дого равенства, убедимся, что все коэффициенты в равенствах (21)
положительны, так как по допущению все соответствующие вектор-
ные произведения также положительны. Так, для уравнения Р3 =
=“3>Pi+“32Р2 имеем (Р8Р2) = я31 (Р,Р2)-Ь *32 (Р2Р2), откуда а31 > 0.
Умножая то же уравнение слева па Р,, получим, что а32 > 0. Далее,
подставим в выражение для РА вместо его выражение, в полу-
ченное выражение подставим вместо РА_2 его выражение и т. д.
В результате будет иметь Pft = 7lftP, -Hf2ftP2, у1А > 0; у2* > 0, откуда
Р, = — Р/г —	Р2.
Ti* Та
Сопоставляя полученное равенство с последним равенством систе-
мы (21)
Р1 = “1*Р* + а.гРг. aik > 0; а12 > 0,
приходим к противоречию.
Покажем, что для образования цикла при любом числе п уравнений,
п > 2, нужно совершить не менее шести тождественных преобразо-
ваний. Так как мы рассматриваем только однократные замещения
в базисах, то возвращение к исходному оазису можно ожидать после
‘2k преобразований, где k—-\, 2,3, ... Возвращение ирп k=\ невоз-
можно, так как определители, отвечающие этому случаю, имеют вид:
(Р,Р2.. ,р;.. ,рг); (Р,Р2...Р/...РГ); (Р,Р2...Р,...РГ)
(Р,Р2.. Р;... Ру); (Р1Р2...Ру...Р,).
Два последних определителя отличаются одной перестановкой
векторов Р, и Ру, а поэтому имеют разные знаки, что противоречит
предположению их положительности.
Для доказательства невозможности образования цикла при ft = 2
нужно показать, что пн один из путей тождественных преобразований,
представленных ниже, неосуществим.
1.	(Р^...Р„...Р„.. .Рг) —► (Р,Р2.. .Ру...Р,....Рг) —*
->(Р1Р2...Ру„..Р,;...Рг) —
— (Р1Р2...Ру,...Р,.„...Рг)->
— (Р1Р2...Р„...Р,2...РГ);
2.	(Р1Р2...Р,....Р/..Р,.)—»(Р,Р2...Ру]...Р/....Р,) ->
— (Р1Р2...Ру,...Рд...Рг) —>
— (Р^.-.Ру.-.Р,,...?,) —
— (P.P^.-P,,...?,,...?,);
3.	(Р,Р2. . . Р„. . • Р,2. . . Рг) — (Р,Р2. . . Ру,. . . Р,2. . . Рг) —
- >(Р1Р2...Ру,...Ру,...Рг)-^
— (Р1Р2...Р,...Руг...Рг)->
—> (Р,Р2.. .Р,.. .р,,.. ,р,).
Первый путь перехода от базиса к базису невозможен, так как
он сводится к случаю двух уравнении.
46

Сопоставляя неравенство 1 > kxk с ранее полученным kxk > 1,
обнаруживаем противоречие.
Итак, зацикливание может наступить только после того, как бу-
дет совершено не менее шести преобразований.
§ 8. Метод определения неотрицательного решения
системы линейных алгебраических уравнений
Пусть задана система т линейных алгебраических уравне-
ний с п переменными:
«,/, +Я12Х2 + • • • + °1/X/ +	•	•	• + aM,Xn = 4	j
«2,4 + «22*2 + • ’ ' + nzjXj +	•	’	 4-’72,сП, ---=	।
ailXl "4 «/2X2 + ' ' ' 4~ aijXf 4~	•	•	' + air:X,l	3)
amtX i 4' птгХг + • '• + amjXj 4"	•	•	• 4" am>,Xn “ Л«-	,
Без ограничения общности будем считать, что /7 ,л- 0 (этого
всегда можно достигнуть умножением обеих частей соответст-
вующих уравнений на —1).
Представим систему (13) в виде
0 = />. —(2 а,ул7), /=1,2, ...,да.	(22)
Если в системе (22) имеется переменная, входящая только
в одно уравнение, и коэффициент при переменной внутри
скобок имеет знак «4», то такое уравнение можно разре-
шить относительно этой переменной.
Допустим, что уравнения системы (22) разрешены относи-
тельно всех таких переменных. Тогда после соответствующей
перенумерации переменных система может быть записана в виде:
4	(4(„+,4„+, 4“ «,0 + 2-4‘-2 + - 4~°1/х/+  4"а1Л)'
хг = Ьг — («2Zo+14 + 1 4- 4/„ • 2х,а; 2 + •• 4- «=/-4 i - -Кл),
50
или сокращенно:
(23)
k
ьг--{ 2 «,•*),
/=/.,+<
k
о=^ь, —( 2 «тлд
j=t.,+i
где
/=1,2,...,/0; Y=1,2, ..., Yo;
Zo + Yo=:OT; l0-[-k = n; ftz>0; b-^Q.
Любое уравнение в системе (23), не разрешенное относительно
какой-либо переменной, будем называть Q-уравнением.
Таким образом, всякая система линейных алгебраических
уравнений может быть приведена к виду (23)*).
Для отыскания неотрицательного решения системы (23)
подвергнем ее последовательным тождественным преобразова-
ниям, удовлетворяющим следующим условиям:
1.	Отыскиваем 0-уравнение, у которого свободный член Ь(
больше нуля. (Если такого О-уравнения нет, то значения пе-
ременных
xp—bp x^Q (/=1,2,...,/,; у = /0 + 1, .... k)
образуют неотрицательное решение системы (23).) Пусть это
будет г'-е уравнение.
2.	Отмечаем в /-м уравнении положительный коэффици-
3.	Находим разрешающий элемент и производим тож-
дественное преобразование системы (23).
4.	z-е О-уравнепие используем для дальнейших преобразо-
ваний системы до тех пор, пока мы не разрешим его или не
установим, что система (23) несовместна **).
5.	После разрешения Z-го 0-уравнения отыскиваем следу-
ющее О-уравнение с положительным свободным членом и про-
изводим с ним аналогичные действия.
*) Если в системе (23) нет ни одного уравнения, разрешенного
относительно какой-либо переменной, то 1, = О, и система (23) состоит
только из О-уравнений.
*-) Если в /-м уравнении нет положительных коэффициентов при
неизвестных, то система (23) оказывается несовместной, так как урав-
нение 0 = ft,- — (Е’щ-уХу), и котором ft,- > 0, а все 0, ие может быть
удовлетворено ни при каких неотрицательных значениях переменных
То 0.
51
6.	Этот процесс про то окаем до тех пор, пока не освобо-
димся от всех О-уравненпй.
Примечания: 1. Число уравнении в преобразованной системе
может оказаться меньше tn, так как при подстановке выражения раз-
решенной переменной в остальные уравнения некоторые из этих
уравнений могут обратшься в тождества 02Д(), которые следует
исключить из дальнейшего рассмотрения,
II. Пусть в исходной системе (23) или в нреобра товаиной системе
обнаружено уравнение, разрешенное относительно некоторой перемен-
ной, имеющее свободный член, равный нулю: х, ==0 —	), и такое,
что все его коэффициенты при переменных в правой части неотри-
цательны. Так как роль таких переменных может быть только пуле-
вая, чтобы X/ были неотрицательны, следует положить их равными
нулю во всех уравнениях, от чего испытуемая система значительно
упрощается. Аналогично исключаем те 0-уравнения, у которых сво-
бодный член равен нулю, а отличные от нуля коэффициенты при пе-
ременных в правой части имеют одинаковый знак. Значения этих пе-
ременных в остальных уравнениях принимаем равными нулю.
Рассмотрим, к каким результатам могут привести после-
довательные тождественные преобразования, удовлетворяющие
условиям 1—6.
а)	Возможно, что после конечного числа тождественных
преобразований система освободится от О-уравнений. Оче-
видно, в этом случае система (23) совместна. Совокупность
значений переменных, получаемых приравниванием неосновных
переменных нулю, а основных — свободным членам в системе, не
содержащей 0-уравнений, является неотрицательным решением.
б)	Возможно, что после конечного числа тождественных
преобразований обнаружится, что используемое О-уравнение
превращается в уравнение вида
о=- (2
где Ь'{ > 0, а\. • 0 для всех j. В этом случае система несов-
местна.
в)	Наконец, может иметь место случай, когда система не
освобождается полностью от О-уравненпй, а условия возмож-
ности применения тождественных преобразований не наруша-
ются. Так как при последовательном применении тождествен-
ных преобразований число О-уравненпй не может возрастать,
то в этом случае некоторое О-уравненпе обладает тем свой-
ством, что оно всегда имеет по крайней мере один положи-
тельный коэффициент при переменных в правой части, но раз-
решающий элемент ему никогда не принадлежит. Заменяя это
0-уравнение
° = —£Н/*у)
52
уравнением
у-.	(У<,X),
'ее •‘-J Л‘1 1'
где е — сколь угодно малое положительное число, и рассмат-
ривая последнее уравнение вмес те с разрешенными, мы видим,
что в случае в) происходит зацикливание.
Изложенное выше дает возможность высказать следующее
утверждение:
Какова бы ни была система т алгебраических у равнений
с п переменными, последовательное применение к ней тож-
дественных преобразований позволяет через конечное число
шагов (за исключением случа в зацикливания} определить,
совместна ли система в области неотрицательных значе-
ний переменных. Н случае совместности системы на по-
следнем таге преобразований образуется некоторое неот-
рицательное решение.
Важным свойством приведенного метода является его при-
менимость к произвольной системе линейных алгебраических
уравнений, в том числе и к линейно зависимой системе, при этом
не требуется заранее выделять линейно независимые уравнения.
Кроме того, так как всякая система линейных неравенств
добавлением неотрицательных переменных может быть сведена
к системе равенств, то этот метод также пригоден как для
определения совмесгностп системы неравенств, так и для
нахождения одного из неотрицательных решений в случае их
совместное ги, при эюм также не требуется выделения много-
гранника решений в (.чистом виде.:.
На рис. 1!) приведена блок-схема программы определения
неотрицательного решения произвольной системы линейных
алгебраических уравнений с помощью электронных вычисли-
тельных машин.
Машине задаются коэффициенты при переменных в исход-
ной системе и свободные члены. Кроме того, при решении за-
дач линейного программирования задаются коэффициенты ми-
нимизируемой линейной формы. По программе машина, выпол-
няя последовательность тождественных преобразований, про-
веряет условия совместности системы.
В случае несовместной системы машина сигнализирует об
этом факте и останавливается. Если система совместна, то ма-
шина определяет неотрицательное решение, выдает его (если
необходимо) и переходит к поиску оптимального решения.
Рассмотрим примеры.
53
Рис. 1У.
54
Пример. Определить, совместна ли система в области
неотрицательных значений переменных:
1 • х, Зх2 -j- Зх3 = 2,
1 • х г ~(— 2х 2 —j— 4х3	I,
— 3х1 4- Зх2 -L- х3 = 3.
О—=2— ( х, 4-Зх24-Зх3),
О—7--(1 -V, + 2х2 + 44),
0	3 - (— Зх, + Зх2 — х3).
В первом 0-уравнении положительный коэффициент при х,,
равный единице, одновременно является и разрешающим эле-
ментом:
х1-_-2--(Зх2+5х3),
0-5- (---х2 + х3),
0 = 9-(12х2 + 8х,).
Во втором О-уравненни коэффициент при х3 положителен;
разрешающий элемент принадлежит первому уравнению:
2 П ,5
4 - у у X, + Х2 J ,
0=—— f — J-x—2х2^ .
з \ з 1 у
Система несовместна, так как в последнем уравнении свобод-
ный член положителен, а оба коэффициента в скобках отри-
цательны; поэтому второму уравнению не удовлетворяет ни
одна точка, для которой х3 5= 0; х2У=0.
Пример. Найти неотрицательное решение системы урав-
нений:
0 —- 3 — ( 2Х] + 4 -ф- 2х3 + 2х4),
1) оз 2х, 4~ 4 + 4х3 + 2х4), 
0	6 - ( -2х, + 2х, + 7х, 4- 4х4). ,
Производим тождественные преобразования системы:
3	/1 . , , ,	5 х
4—	'у+- i 4 1 4у > ]
2) 0^-6 - ( 2х24-6х,4-4х4),	}
0 9 -( Зх24 94 + 64). f
А'з 1 — ( У Х2 + У 4) , |
-- 1	+	 I 1	\	}
4 —	b Л 2 4 3	’ I
J
Одно из неотрицательных решений системы есть
у, = 1;	Л'2 — 0; хг = 0.
Изложенный выше метод нахождения неотрицательного решения
системы уравнений может служить одним и 5 способов определения
ранга матрицы. В самом деле. Пусть дана матрица
j яи ^12 • • *	:
(Т21	(722 • • • ^2ц
а ту ^т?.' • • ати
Примем ее столбцы за векторы Р1} Р21...,РМ и составим уравнение
п
0-Р„-( £ Х/Р/,
У-л
в котором положим Ро = Р4. Ясно, что это уравнение имеет неотри-
цательное решение (например, лс, = 1; Ху=(); / = 2, 3, ... ,//). Пред-
п
ставляя векторное уравнение 0 = Ро— (2 х.Р/) в виде системы т
уравнений и подвергая последнюю тождественным преобразованиям,
освободимся от О-уравненнй. Число разрешенных уравнений, получен-
ное после исключения О-ураннений, определяет ранг матрицы. При
этом, как можно показать, число преобразований, которые необходимо
провести, также равно рангу матрицы.
Пример. Найти ранг матрицы
2—4	3 I 0 |!
1—2	1—42
0	1 — 1	3 1'*
4	7	4 - 4 й ;
Выполним последовательность тождественных
преобразований:
0 — 2 — (2х( — 4х2 Зх, 4- -х4),
0=1 — ( х, — 2х2 -j- л, — 4,\д -J- -ЧД’
0 = 0	( х2 х3 4- Зх4 4
0 = 4- (4х, - 7х2 4- 4х3 - 4х4 4- 5xs)
х4 — 1 — ( — 2х2 4" а’з — ^х4 T" -Х'5). 1
0 = 0-( ха+ 9х.4-4хП
0 = 0 —(	х2 — х, 4~ З.у, 4- v-,>. |
О = 0 - (	х2__	4 12х, - 3 у J J
I шаг
56
*3 — 0 - (	9х4 — 4л-5). 4
*1 —: I — ( — 2л', — 13л4 -р 6л3). I
О — О — (	л'2 j- 1 2л4 — З.х5).
____*2 -1- l^,-3x5),
хг --()-( 12л-, - Зл-5),
*3-0-( йлу-йлД.
л, = I — 11л„
о-- О
Ранг ма 1 рпцы г 3.
II шаг
III шаг
§ 9. Решение задачи линейного программирования
Задача линейного программирования, как сказано выше,
может быть сформулирована следующим образом:
задана система т линейных уравнений с п переменными
«..*, + «>2*2+	«.А = ^Р
аг l-*i —I- <l22* 2 1 - • • • tl2j^ j ~~I- агпХп ^2’
W, + П12Х2 + ’ • • + ni)Xj + • • • + ai„X„ =
(13)
am\Xi + nmzx2 + • • • + nmiX/ + • • • 4" amnXn h m .
и линейная форма f—cixl c2.va Ц-" • • • cjxj • • • 4“ cnxn
тех же переменных. Требуется среди всевозможных неотрица-
тельных решений
(*о х2> •••- х„)
системы (13) найти такое решение (х?;	х,°), при ко-
тором / принимает наименьшее возможное значение.
Для решения этой задачи определим одно из неотрица-
тельных решений системы (13) способом, изложенным в преды-
дущем параграфе. В результате система (13) перейдет
57
в эквивалентную ей систему *):
(24)
x'i = b’i — К+ 1+С т2<+ 2 “Г • • Ч ~ <4 ' Г   
•	• • ",’л)'
=	—	1+Чч 2^.2 + • 	
•	• • ) </Лл-)-
/=1, 2, ..., г; г-~у т; гk C-ti.
Подставляя выражения основных переменных в линейную форму
н вводя соответствующие обозначения для постоянных величин,
представим f в виде линейной функции
В соответствии с симплекс-методом для нахождения оп-
тимального решения систему уравнений (24) и линейную функ-
цию (25) подвергаем тождественным преобразованиям до тех
пор, пока не нарушатся условия их осуществления, т. е. пока
не исчезнут положительные коэффициенты при переменных в
форме (25). Но гак как изложенное в первых двух парагра-
фах этой главы о зацикливании относится н к задаче линей-
ного программирования, то можно высказать следующее утвер-
ждение:
Применение конечного числи тождественных преобразо-
ваний позволяет (за исключением случаев зацикливания)
найти неотрицательное решение системы уравнений, при
котором форма принимает наименьшее значение.
В целях исключения возможности зацикливания предложено
несколько методов. Некоторые из этих методов требуют при
проведении тождественных преобразований дополнительных
операций всякий раз, как имеет место вырождение. При вы-
*) После соответствующей перенумерации неизвестных.
58
рождении разрешающий элемент определяется неоднозначно.
Дополнительные операции позволяют на каждом шаге тожде-
ственных преобразований в случае вырождения выбрать раз-
решающий элемент так, что зацикливание исключается. Слу-
чай вырождения, как уже было отмечено, всегда имеет место,
как только вектор Ро принадлежит одной или нескольким ба-
зисный гиперплоскостям.
Анализ практического решения задан ЛТОЙХАКА'б
мировання подтверждает предположение о малой вероятности
зацикливания, а построение примеров зацикливания встретило
довольно значительные трудности, связанные с необходимостью
ЛОН’ЛеГНОрхУГГ, CcYA\AWA''J 4WC.SVJ усжшшедшнл УСЛСШЙ,.
Те редкие случаи, когда образуется никл, ири ручном ре-
шении задачи могут быть обнаружены непосредственно.
Так, поставив задачу нахождения неотрицательного реше-
ния системы
( х3 xt VrK)'
х2 = ° -- (2*а — xt — 4*s+ *.),
при котором линейная функция
3 ~ К + + 'Х —
достигает наименьшего значения, и проделав последователь-
ность тождественных преобразований, как в примере, рассмот-
репном на стр. 44, мы обнаруживаем, что пришли к исходной
группе основных переменных. Если не обратить внимания
на этот факт, то процесс решения может оказаться беско-
нечным, значение же линейной функции при этом остается по-
стоянным.
При обнаружении зацикливания следует изменить последо-
вательность тождественных преобразований, выбрав другой
разрешающий элемент. Так, поступая в рассмотренном примере,
как изложено ниже, мы устанавливаем, что линейная функция f
не ограничена снизу:
( х х: — Л'5 + Зхв),
Л2:	(1 ^-vs Xi 2'Xs4~-*-e)>
/— 3 — ( л4 Д- 3xs — 8х,),
59
В данном случае значение формы может быть уменьшено
за счет увеличения значения л;,, но так как в колонке коэф-
фициентов при переменной х, отсутствуют положительные ко-
эффициенты, т. е. нет ни одного разрешающего элемента, то
это означает, что нет никаких ограничений увеличению пере-
менной х4. При этом функция / ciaiioiniiCH неограниченной
снизу.
При решении задач на электронных вычислительных ма-
шинах в программе следует предусмотреть возможность обна-
ружения возвращения к уже встречавшейся группе основных
переменных. И только в случае обнаружения зацикливания
следует ввести ту части, программы, которая предусматривает
дополнительные операции, исключающие возможность зацик-
ливания.
При этом наиболее простой дополнительной операцией
является выбор другого разрешающего элемента на том шаге,
на котором обнаружено повторение.
Пример. Определить наименьшее значение линейной
функции /=5х1— lO.v,-1-7х3 — З.г на множестве неотрица-
тельных решений системы уравнений:
7
0 = у — ( -П + Л'2 + 7-И + 2*4),
0 = |-(-2х.- >-2 + Зх3-Нд-4),
0 = 4-(	2л-, + ^ + 8.п+ хд)
= 2 —( Л4-Ч-Ц4
60
х2 = 0 — (
0 = 0— f
11
3 л>
может быть только равна 0!).
х4=1-(2х,),
а'2 “ I — <3л'j.
~18-(-43х3)
/n.in= - 18 ПРИ *,=°,
хз ~ °>
Xt = 1,
1
*2= У
Пример. Среди неотрицательных решений системы не-
равенств:
20л; -ф-1 2х2 — 1 ;>х3 sg 60,		
-П +	2л;— Зл;	= 6,
Зл; -ф	6хг-|- 4л;	< 12,
20л; —	15л2+ Зх,	^60,
10х,+	5л; — 2л;	7= 10,
6х, -ф-	7х2 ф- 42х3	тл 12
найти такое, при котором линейная форма f = хх-\-х2-\-х3
достигает наименьшего значения.
Решение. Систему неравенств путем введения дополни-
тельных переменных сводим к системе уравнений:
уу = 60 — ( — 20л; -L- 12х2 — 15х3),
6 —(	*.+	2х2—	3хЛ-
у3 = 12 — (	3х1 -ф-	6х2 -ф-	4х3),
А = 60 — ( —	20х, — 1 5л; -ф-	3х2),
О —-10 — (	Ю.^ф-	5л;—	2х3—J’s)»
0 = 42 - (	6л; -ф- 7л; +ф2х,	— у()
61
и подвергаем тождественным преобразованиям:
х» = ' —	/	1	1	1	1	\ 1тХ+(Г^-42-''«}
_У1 = 75 — |	7125	, 87	15	\ ^xi+-x2-4^vj)
Л = 9-|	/10	, 5	.3	\ ^+ 2“*2"45-V4
Л= 8- 1	717	32	. 4	5 <7Xi+ 6-Л'*+42-У4
Л = 57-(	/143	93	, 3 А . 7 'V‘	6 ’V2 + 42-'’e J ’
0 = 12 — (	Л72	, 16	2 7 Х> + 7 А'2	42-ve -
X, =	т-(	14 27	Х2	— 4'^	1 А 21(г'’» /
*3 =	4-(	54	Х2	+ А-5'*	2Тб-У») ’
yt = 95	5__/ 6	\	1383 54	"^2	—	665 1512-'’’
Л = 7	J	/ У \	95 27	-г2	10 - 72Л-	14 А 216-v«J’
Л= 5	1 / 6 \	220 54	Х2	1	17 + -7V	। 'б' А । T5l2-'’e7
Л = 80	5	/	265	Х2-	143	35 А
	6	\	54 '		72 У5	1512- «Г
У,
Одним из неотрицательных решений
ляется решение x1 = -g-; х2 = 0; х,
линейную форму через неосновные
[	7	1	1	\
V 18	12-'’5	36-'’»7
Как видно из последнего выражения линейной формы, даль-
нейшее ее уменьшение в
переменных невозможно.
х =0; х, =	явилось
* d ь
значение линейной формы /П1Н1 = 2.
системы неравенств яв-
5
= Выразим теперь
переменные: /=2—
области неотрицательных значений
Поэтому первое решение xf= —;
и оптимальным, а соответствующее
62
§ 10. Об одной задаче на минимакс
Пусть задано п z/z-мерных векторов Р;- и множество Т =
= соответствующих нм вещее гневных чисел /у, 7=1, 2,. ..
. . ., п.
Рассмотрим множество P={.v} всевозможных неотрица-
тельных решений у = {х} уравнения
А- Р -I - V Р -I-	 Г Р = Р
Л1* 1 I 'Д. 2 |	• 1 ' tl'fl ' О’
где Р„ — заданный век юр в да-мерном пространстве, не равный
нулю.
Переменные ас- -/ 0 в любом из решений у условимся обо-
значать через Ау, а соответствующие значения /у—через /у.
Через {/),} обозначим систему чисел /у, соответствующих
переменным Ау-^0 в решении уч
Наибольшее число среди системы чисел {t  } условимся
обозначать через t .
Таким образом,
^ = тах{/у>}.
j
Теперь поставим задачу:
Среди всевозможных решений у С У найти такое _уопг, для
которото соответствующее
или
tv =min(/).
'on,	у
Решение у (если оно существует), удовлетворяющее этому
условию, будем называть оптимальным и обозначать через у .
Такие задачи называются задачами на минимакс. (Частным
случаем этой задачи является транспортная задача по крите-
рию времени, которая подробно рассмотрена в главе IV.)
Подвергая систему m линейных алгебраических уравнений
с п переменными
п
2 а^х- —	1 sC / m; 1 j п,
п
соответствующую векторному уравнению xpj = Г*о> тожде-
ственным преобразованиям, мы можем через конечное число
шагов получить оптимальное решение.
63
Для этого надо;
1.	Построить начальное неотрицаюыюе решение системы
уравнений.
2.	Среди основных переменных х; нагни ту, которой соот-
ветствует наибольшее значение ранное Л’1,х-
3.	Исключить из дальнейшего расс.могрения неосновные
переменные ху-, для которых /•	/™ах.
4.	В Лй строке найти иод знаком У] положительный ко-
эффициент и определить разрешающий элемент
после чего провести тождественное преобразование.
5.	Повторяя (если необходимо) этап 4 несколько раз,
вывести переменную х- из совокупности основных переменных
и исключить ее из дальнейшего рассмотрения.
6.	Этапы 2 — 5 повторять до тех пор, пока иа некото-
ром шаге в соответствующей строке преобразованной системы
уравнений все коэффициенты при переменных станут неполо-
жительными.
Основное решение, полученное на этом шаге, является оп-
тимальным.
В самом деле. Пусть после некоторого числа тождествен-
ных преобразований исходная система примет вид:
/

х,- = />,. —	,Х-).
!р 'р i ‘pJ ‘
Пусть переменной х,- соответствует наибольшее значение /п).ах.
Тогда, если bik < 0, то, исключив х;/ из дальнейшего рас-
смотрения, получим несовместную систему. (Если fy. = О, то
согласно примечанию 11 на стр. 52 следует положить x;=Q,
а также ху- = 0 для тех у, для которых aikj 0. После этого
следует продолжить тождественные преобразования.)
ГЛАВА 111
РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ
ПО КРИТЕРИЮ СТОИМОСТИ
Ниже рассматривается одна из типичных задач линейного
программирования—iai< называемая транспортная задача. При
планировании перевозок грузов часто возникают вопросы наи-
более рациональной организации перевозок. В одних случаях
это означает определение такого плана перевозок, при котором
стоимость последних была бы минимальна. В других случаях
более важным является выигрыш времени, и поэтому среди
возможных планов транспортировки ставится задача определе-
ния такого плана, реализация которого дает возможность до-
ставить грузы к потребителю в самое короткое время.
Первая задача получила название транспортной задачи ио
критерию стоимости, а вторая — транспортной задачи по кри-
терию времени.
Первая задача является частным случаем задачи линейного
программирования и может быть решена изложенным в преды-
дущей главе симплексным методом. Однако в силу особенно-
стей этой задачи она проще решается так называемым комби-
наторным методом. При малом количестве пунктов отправления
и назначения этот метод позволяет решать такие задачи
вручную. При большом количестве пунктов отправления и
назначения задача может быть решена лишь с применением
электронных вычисли тельных машин. Так, задача транспорти-
ровки из 30 пунктов отправления в 40 пунктов назначения
решается на машине «Стрела) за 25—30 мин.
В главе III излагается комбинаторный метод решения
транспортной задачи по критерию стоимости и приводится
упрощенная блок-схема решения этой задачи на вычислитель-
ных машинах.
3 А. С. Барсов
65
§ 11. Постановка задачи
Транспортная задача ио критерию стоимости может быть
сформулирована следующим образом.
Обозначим через а2......... ат количество единиц одно-
родного груза, находящегося в каждом из т пунктов отправ-
ления, а через Ьг	— количество единиц груза, по-
требного для каждого из п пунктов назначения.
Пусть xtj означает количество единиц груза, которое мы
планируем для перевоза из z-го пункта отправления в у-й
пункт назначения, а — стоимость перевозки единицы груза
от /-го пункта отправления к у-му пункту назначения.
Пусть количество груза, отправляемого из всех т пунктов,
равно количеству груза, потребного в п пунктах назначения.
В этом случае должно выполняться условие
т	п
2	2	ь,.
<•=1	/=1
(26)
Будем записывать условия такого типа задач в виде таблицы 2.
Матрицу А'=(х1у) порядка т Xп с неотрицательными эле-
ментами	которая удовлетворяет условиям
=	(/= 1, 2. ..,/те),	(26')
/=1
т
2*// = ^	(y=l,2,...,«),	(26")
1--1
назовем решением задачи транспортировки. Условие (26') озна-
чает, что из /-го пункта отправления вывозится весь груз, а
66
условие (26") означает, что потребность /-го пункта удовлет-
воряется полностью. Задача сводится к определению таких
неотрицательных значений х;/, чтобы общая стоимость пере-
возки
гп п
с= 2 2 сихи
i=\ j=A
была наименьшей.
Используя определение скалярного произведения матриц,
задачу транспортировки ио критерию стоимости можно сфор-
мулировать иначе.
Пусть задана матрица С=(с,у), где с(у—вещественные
неотрицательные числа. Требуется среди всех решений X,
записанных в виде матриц и удовлетворяющих условиям (26')
и (26"), найти такое, для которого скалярное произведение
(СХ) достигает минимального значения. Решение, представля-
емое матрицей X, удовлетворяющей этому условию, назовем
оптимальным.
§ 12. Основные решения транспортной задачи
по критерию стоимости
Рассмотрим заданную матрицу С=(с,у) и произвольную
матрицу-решение (х,у) (/= 1, 2,..., от); (/ = 1, 2,...,«).
Будем считать, что т-Х,п, так как в противном случае их
можно поменять ролями.
Введем некоторые определения.
Пару натуральных чисел ij назовем клеткой, а произволь-
ное множество клеток — набором. Последовательность клеток,
имеющая вид itjv i,j2, i2j2, i2/3, ..., называется цепью.
Цепь называется замкнутой, если она имеет вид
А71> А А’ А 7а> • • • > A 7f> Ц 71 •
Всякую замкнутую цепь назовем циклом. Набор называется
циклическим, если он содержит по крайней мере один цикл.
Набор называется ациклическим, если он не содержит циклов.
Каждой клетке ij соответствует одни и только один эле-
мент Ду матрицы-решения X, а также один и только один
элемент cif матрицы стоимости С. Поэтому всякий набор кле-
ток является одновременно и набором соответствующих эле-
ментов как х(у, так и с-.
Перенумеруем элементы замкнутой цепи 0, обходя ее, на-
при'мер, по часовой стрелке. Будем говорить, что элементы
3*	67
этой цепи с нечетными номерами образуют нечетную полуцепь
0Н, а элементы с четными номерами — четную полуцепь 0Ч.
Условимся сумму элементов ctJ- нечетной полуцени обозна-
чать через с(у, а сумму элементов четной полуцени через
Теорема. Каково бы ни было решение X с циклическим
набором отличных от нуля элементов х,у, существует ре-
шение Y с ациклическим набором элементов у у и такое,
что (CY) =g (СХ), а число отличных от нуля элемен-
тов решения Y меньше числа таких же элементов ре-
шения X.
Доказательство. Пусть отличные от нуля элементы
х 7 матрицы X образуют замкнутую цепь 0,. Сравним суммы
X сП и 2 cty одна из сумм, например с у, должна быть
©;•	о;1
такой, что
о;1	о;1
Образуем новую матрицу X' — (х^.) из матрицы А’— (х,у)
изменением элементов в цепи 0, следующим образом:
х'. . = х,- /. -I- х™ 11,. . ., х'. . - - X;, mi",
<1/1	'Ы1	I ij .	.	,,л. oil	I ,7	>
х'. . = Хе/,--А?.1",..., х' , - Хд /	- Л
11Л	'172	,/ >	’	ah ,j
Здесь	— клетки нечетной полуцени 0", а
CAi	hJ\ — клетки четной полуцепи 0’1, .\Ч'"— наи-
меньший элемент в нечетной полуцени 0". Для всех других
клеток ii положим х'.. = х,-,-.
J	ij и
Легко видеть, что матрица X’, получаемая из матрицы X
перемещением но цепи 0 элемента х;.”"’, также будет решением
транспортной задачи. Число всех элементов х,.., отличных от
нуля, у матрицы X' станет по крайней мере на единицу меньше.
Так как (СА") = (САГ) + ci .	Д™"', то (ОД")^(С’АД
(-)'< И» J
Продолжая построение таких решений и далее, мы через
конечное число шагов придем к решению }', у' которого от-
сутствуют замкнутые цепи 0 средн элемитов хт, отличных
от нуля, а (СТ) sg (СА'). Теорема доказана.
Следствие. Для нахождения хотя бы одного опти-
мального решения достаточно рассмотреть всевозможные
решения X с ациклическими наборами отличных от нуля
элементов х^.
68
Всякое решение X, представленное в виде матрицы, отлич-
ные от нуля элементы х,у которой образуют ациклический
набор, называется основным.
Вообще говоря, в матрице X, представляющей произволь-
ное решение, может быть различное число элементов xi;., от-
личных о г нуля. Однако, какое бы решение X мы ни
взяли, оно имеет не менее п отличных от нуля элементов, что
следует из условия (26") § 11. С друюй стороны, справед-
лива следующая
Теорема. Число N элементов х^, отличных от нуля,
в любом основном решении удовлетворяет условию
— 1, где т — количество пунктов отправле-
ния, а п — количество пунктов назначения.
Доказательство. Предварительно убедимся в спра-
ведливости двух лемм. Построим в (т «(-мерном простран-
стве т X и векторов и поставим их во взаимно однозначное
соответствие с множеством всех клеток ij матрицы С=(с//).
Клетке ij поставим в соответствие вектор Р,у, имеющий все
компоненты, равные нулю, за исключением /-й и т -(-/-й,
каждая из которых равна единице. Очевидно, всякому набору
клеток соответствует некоторое подмножество векторов и,
обратно, всякому подмножеству векторов соответствует неко-
торый набор клеток.
Лемма 1. Если множество векторов {Р,у} линейно за-
висимо, то соответствующий набор клеток циклический.
В самом деле. Пусть известно, что множество {Р,у} векто-
ров линейно зависимо. Тогда существует линейная комбинация
этих векторов, приводящая к нулевому вектору q (0, 0,0),
причем по крайней мере один из коэффициентов отличен от
нуля. Будем рассматривать векторы, входящие в эту комбина-
цию, только с коэффициентами, отличными от нуля. Пусть
это будет, например, вектор Р,х/1. Тогда обязательно в ли-
нейную комбинацию должен входить ио крайней мере один
вектор с тем же индексом z\, например Рг1/2. Это про-
исходит потому, что в векторе q все компоненты равны нулю,
но поскольку в комбинацию входит вектор Рт171, то для обра-
щения z-й компоненты в нуль надо иметь в комбинации по
крайней мере еще одни вектор с той же компонентой, отлич-
ной от нуля. Так как теперь входит вектор с компонентой /2,
то должен входить ио крайней мере еще один вектор с такой
же компонентой, например вектор Рассуждая аналогично,
мы построим последовательность векторов
Р<г/з> • * •
3* А. С. Барсов	69
Поскольку имеется только конечное число векторов, то
после некоторого числа шагов мы должны прийти к вектору
Pi'tji, от него — к вектору Р,,71. Эюй последовательности век-
торов соответствует набор клеток
СЛ- СЛ- СЛ- z273,..., z(7(, itj\,
который является циклическим.
Лемма 2. Всякий набор из т п клеток является
циклическим.
Чтобы убедиться в справедливости этой леммы, достаточно
показать, что любые (/и —я) векторов из числа построенных
линейно зависимы. Докажем это.
Рассмотрим (т ;/)-мерный вектор
т членов	п членов
q(—~i, —С.., —“П	+1, +С.., +~п.
Он ортогонален ко всем Р^. Отсюда следует, что все
векторы Р(у принадлежат т-\-п— 1-мерному пространству, а
поэтому всякие т -|- и из них линейно зависимы.
Из условия (26") § 11 и последней леммы следует, что
п <6jN <jmп. А так как непосредст венно па примерах
можно убедиться, что существуют задачи, для которых W=zz,
н задачи, для которых N т- п—1, то окончательно по-
лучаем, что N действительно удовлетворяет условию zz Wsg
^т-\-п—1, и теорема доказана.
Из только что доказанных лемм следует, что множество
векторов {Р.}, соответствующее ациклическому набору из
mj-n—1 клеток, является базисом в (т zz)-MepnoM про-
странстве построенных векторов Р(... Обозначим через Н про-
извольный ациклический набор нз тп—1 клеток.
В силу взаимно однозначного соответствия всевозможных
базисов (т -|- я)-мерного пространства и ациклических наборов
из т п—1 клеток, известные свойства базисов многомер-
ных пространств применительно к ациклическим наборам из
т -|-п—1 клеток можно выразить следующим образом.
Свойство 1. Пусть //, — некоторый ациклический
/И —(—я — 1 набор и (ij) С *)• Тогда набор Н2, полученный
присоединением (ij) к набору /7,, содержит один и только
один цикл 0.
*) Знак £ означает, что клетка ij набору //, не принадлежит.
/О
Свойство 2. Пусть (/',	J) и (i', j') g 0. Тогда
набор Hs, получаемый из Нг исключением клетки (/',/), снова
является ациклическим тн—1 набором.
Наборы /7, и 7/3, о которых говорится в свойствах 1 и
2, отличаются только одной клеткой.
Определение. Два ациклических т-\-п— 1 набора,
отличающиеся только одной клеткой, называются ацикличес-
кими т п—1 наборами однократного замещения.
Рассмотрим произвольное основное решение А'=(х(.у.). По
теореме (см. стр. 69) число М отличных от нуля элементов х;у
удовлетворяет условию п sg N -С т п — 1. Остальные
т'р^п— N элементы решения равны 0.
Построим ациклический т-\-п—1 набор Н такой, что
все отличные от нуля элементы х^ решения X расположены
в клетках этого набора.
Определение. Элементы х(у решения .¥, равные нулю
и расположенные в клетках ациклического т-\-н—1 набора
И, называются выбранными нулями.
Определение. Совокупность ненулевых элементов х.у
основного решения X вместе с дополняющими их до ацикли-
ческого т п—1 набора Н выбранными нулями называется
выбором.
Определение. Элементы матрицы С, соответствую-
щие элементам выбора X, называются х-выбранными.
Следовательно, выбор есть основное решение, в котором
из всех нулевых элементов Д,- - 0 выделены те, которые до-
полняют множество ненулевых элементов х;у:/=0 до ацикли-
ческого т -|- п— 1 набора Н. Окончательно приходим к выводу,
что для нахождения хотя бы одного оптимального решения
достаточно рассмотреть всевозможные выборы.
§ 13. Оптимальный выбор
Методика определения оптимального решения заключается
в том, что, отправляясь от некоторого начального выбора, мы
переходим последовательно к другим выборам с меньшим зна-
чением скалярного произведения (СХ) и через конечное число
шагов приходим к оптимальному решению. Поэтому возникает
вопрос о построении первого выбора.
Рассмотрим следующий способ построения первого выбора.
Определяем элементы первой строки матрицы Х-(х^).
Для этого в первой строке матрицы	отыскиваем наи-
меньший элемент. Пусть это будет элемент Ci71. Тогда
3**
71
полагаем х^ — min (я,; ft71). Если а2^> bJv отыскиваем в той
же строке второй наименьший элемент cI/s, удовлетворяющий
условию cij2 Дэ Ci71, и полагаем xI;-2 = min («, — Лц71; bj2). Эти
шаги продолжаем, пока полностью не удовлетворим первому
п
уравнению «,= 2 хи'' Если на некотором шаге этого про-
/=1
цесса окажется, что остаток от а, точно равен соответствую-
щему Ь}1., то, положив равным этому остатку хцк = Ь/к,
дополнительно полагаем следующее, соответствующее по вели-
чине, значение переменной х17,. + 1 = 0. После этого переходим
ко второй строке, третьей и т. д. При этом в столбцы, соот-
ветствующие уравнения которых полностью удовлетворены,
нуль не записывается.
Из построения следует, что полученное таким образом пер-
вое решение является выбором, ибо число отмеченных элемен-
тов равно т-\-п—1 и среди них нет ни одной замкнутой
Т а б л и н а 3
цепи.
Для пояснения рассмотрим следующий пример. Пусть тре-
буется построить первое решение для транспортной задачи,
определяемой матрицей, пред-
ставленной в таблице 3.
В первой строке наимень-
шим из чисел (8, 3, 5, 2) яв-
ляется число 2, поэтому при-
нимаем х14 ---min (10; 15) =
= 10. Так как груз первого
пункта отправления полно-
стью распределен, то нере-
ходим к распределению груза
второго пункта отправления.
Для этого во второй строке таблицы 3 отыскиваем наимень-
шее из чисел (4, 1, 6, 7). Число 1 есть наименьшее. Поэтому
полагаем х22 = min (15; 10)= 10. Так как в этом случае
имеется остаток во втором пункте отправления, равный
15—10 = 5 единицам, то отыскиваем во второй строке сле-
дующий наименьший элемент. Это будет число 4. Полагаем
x21 = min(15—10; 5) = 5. Учитывая, что потребность пер-
вого пункта назначения полностью удовлетворена, а остаток
во втором пункте равен 0, отыскиваем третий наименьший
элемент во второй строке. Таким элемен гом является число 6.
Поэтому полагаем a'2S = 0. Теперь переходим к распределению
груза третьего пункта отправления. Для этого среди чисел
72
(1, 9, 4, 3) третьей строки отыскиваем наименьшее. Так как
потребность первого пункта назначения полностью удовлетво-
рена, то число 1, стоящее на пересечении третьей строки
и первого столбца, в расчет не принимается. Поэтому отыски-
ваем наименьшее из чисел (9, 4, 3). Число 3 наименьшее среди
них. Полагаем x31 = min(25, 15—10) = 5. После этого нахо-
дим в третьей строке следующее наименьшее число 4 и пола-
гаем хаз = 20.
Легко убедиться, что полученное распределение есть реше-
ние. Кроме того, построенное решение является выбором.
В самом деле, число выбранных элементов равно т п—1 =
= 3 —|—4—1=6, и они не образуют между собою циклов.
Напротив, всякий не выбранный элемент х^, как легко
видеть, образует один и только один цикл с элементами
выбора.
В дальнейшем мы будем пользоваться изложенным спосо-
бом построения первого решения.
Пусть построен первый выбор — решение X с набором Нг.
Пусть соответствующее скалярное произведение (CXJ равно Cv
Оценим каждый элемент с^, не входящий в Hlt посредством
выражения
где Cjj и У1, с,-,— суммы элементов соответственно нечетной
и четной полуцепей единственной замкнутой цепи, образуемой
каждым элементом ci}- с х-выбранными (оцениваемый элемент
Cj  принимается за первый в цепи В). Отметим элемент С/^,
Amin
___ ,	,	I , и его замкну-
тую цепь с х-выбраиными элементами. Построим второй
выбор А’2, для чего передвинем наименьший элемент х™"‘
первого выбора из четной полуцени в нечетную полуцепь.
При этом, если в четной полуцепи имеется несколько элемен-
тов х,--, равных наименьшему х™п, то, для определенности,
исключаем из набора л, клетку ij с элементом х;у , встре-
чающуюся первой в четной полуцени при обходе ее по часо-
вой стрелке. Вместо исключенной из набора клетки if
вводим клетку ijt, которой соответствует C/j, и новый
элемент выбора х,^ = х™п (заметим, что за счет передви-
жения элемента х,у1п по цепи в выборе Х2 может оказаться
несколько нулевых элементов). Так как выбор Х2 отличается
73
от выбора zY, только изменением в цени элемента
то, если справедливо неравенство	— §^<°- со-
лярное произведение (СХ2) будет меньше (СА\) на величину
—21х™'' Учитывая, что х™'11 может оказаться рав-
ным нулю, мы приходим к выводу, что СХУ~С2. Только что
проведенное построение можно повторить и, отправляясь от
выбора zY2, построить выбор Х2 и т. д. В результате обра-
зуется последовательность выборов	Х2.	...,	X k, ...
такая, что соответствующая последовательность значений
скалярных произведений С, С2	Ск	...	является
невозрастающей функцией номера выбора.
Выбор Хк с набором Hk называется	оптимальным, если
каждый из элементов с,-, не входящих	в	Нк,	имеет	неотри-
цательную оценку
Так как для любого элемента с,у, не входящего в набор Нк,
справедливо неравенство	то "ереход по-
средством однократных замещений к любому другому выбору
от выбора Xk, не может уменьшить значение скалярного
произведения по сравнению со значением скалярного произве-
дения Ck, соответствующего выбору Хк*).
Теорема. Для всякой матрицы С=(с^) с веществен-
ными элементами при а(У>0, Ау>0 последовательность
выпоров Xt, Х2, ..., Хк, ... через конечное число шагов
заканчивается, оптимальным выбором.
Доказательство.
I случай. Если при переходе от выбора к выбору при
построении последовательности zY,, Х2. . . . ни в одном из
О	min
, то и Xij , переносимое по
цепи, отлично от нуля. В этом случае значение скалярного
произведения с каждым шагом уменьшается. А так как при
конечных т и п может быть только конечное число различных
наборов Н, на каждом из которых однозначно определяется
выбор, то бесконечного числа шагов быть не может.
II случай. Если при переходе от выбора к выбору в по-
следних могут появляться нулевые значения •, то возникает
сомнение в конечности последовательности zY,, A'z, . . ., так как
в этом случае х™п = 0, и значение скалярного произведения
*j Ниже будет показано, что оптимальный выбор есть в то же
время и опти.чальное решение.
74
не уменьшается. Однако сомнение полностью устраняется, если
наряду с исходной задачей транспортировки рассмотреть задачу
с той же матрицей С=(с,-), но с
a'i~ai -J-e, z=l, 2,	т,
2,	(zz— 1),
b'n = bn Ц- ms,
где г — достаточно малое положительное число. Назовем эту
вторую задачу г-задачей. Построим первые выборы X и Xf
для этих двух задач. Тогда в силу малости г наборы Н и
А/1 совпадут и в выборе Х[ не будет пулевых элементов
х'у=0. В самом деле, появление нулевых значений х(у в вы-
боре в исходной задаче происходит в тех случаях, когда
существуют такие сочетания строк и столбцов, что имеют
место равенства
'S?	7==Л'
.2 ai~ 2 Ь/-
' —И	/=7г
Поэтому появление нулевых значений в задаче может быть
в двух случаях:
‘~т	i^ip
a)	S я/+9г= 2 bj,
j=^j\
J=JP
6)	2 я/ + <7г= 2 br\-bn + ms.
i-h	i~ h
Выбирая E отличным от корней уравнений, выражаемых усло-
виями а) и б), мы исключаем возможность появления нулевых
элементов в выборе A’t Так как матрица С— (с^) одна и
та же для обеих задач, то совпадают элементы с(-у с наиболь-
шей отрицательной оценкой, замкнутые цепи этих элементов
с элементами выборов X, и A'i, а также положение в набо-
pax пх и Н\ элементов х,7- и х/у , подлежащих переносу
по цепи. Переход от выбора X к выбору А'2 в исходной
задаче является переходом от выбора А'1Е к выбору Х^ для
s-задачи. В силу малости г эти рассуждения справедливы на
любом шаге. Так как s-задача является задачей при отсутст-
вии Xjj — 0, когда имеет место уменьшение скалярного произ-
ведения на каждом шаге, то для s-задачи через конечное
75
число шагов мы придем к оптимальному выбору Л'*. В силу
совпадения матриц С=(с(.,.) и наборов Hk и выбор Xk
также является оптимальным.
Теорема доказана.
§ 14. Инвариантность последовательности выборов
эквивалентным преобразованиям матрицы стоимости
Определение оценок элементов связано с большим объемом
вычислений. Возникает задача определения таких простых
преобразований исходной матрицы С=(г;..), которые, не меняя
последовательности выборов, значительно сокращают процесс
нахождения оптимального выбора.
Для этого введем понятие эквивалентного преобразования
матрпцы.
Определение. Пусть задана матрица С=-(с,у) и про-
извольные числа г,; г2; ...; гт; s2, sn. Назовем мат-
рицу D = (dij) эквивалентной матрицей С—(с(у), если она
получена из матрицы С по формуле D —	- -j- r;. Sj).
Теорема. Последовательность выборов инвариантна
относительно эквивалентных преобразований матрицы.
Доказательство. Преобразуем матрицу С’ в эквива-
лентную ей матрицу D. Построим для матрицы С начальный
выбор Д', и, отправляясь от него, посредством однократных
замещений построим последовательность Xt, Хг, JV3,
сходящуюся к оптимальному выбору Х/г.
Отправляясь от того же самого выбора Х1У построим по-
следовательность Хх, Х3, Х’3. . . . для матрицы D, сходящуюся
к оптимальному выбору X'k. Легко видеть, что разность оце-
нок А,у— для любых двух элементов с*у и 4у, не входя-
щих в выбор A'j, равна нулю:
а^у	д°=[2 (rJ>) — 2 (с5)] ~ [2 (со-+ч+sj) —
о11	о4	“
- 2	+ П + *;)] = [2	— 2 (Ну)1 - [2(<7/) — Жб)]—
tF	ын w‘‘ w" ”
- 2 (п + *у)+2 (п + sy)=о.
0Н
Последние две суммы равны по величине и противоположны
по знаку, так как всякое число г- (пли 5у), содержащееся
в нечетной полуцепи, содержится и в четной полуцепи.
Поскольку оценки элементов для матриц С и D совпадают,
76
то совпадают и элементы с наименьшей оценкой. Поэтому при
переходе от выбора Xt к следующему выбору как для мат-
рицы С, так и для матрицы D выборы Х2 и X'. совпадают.
Проведенные рассуждения остаются справедливыми на любом
шаге. Эго означает, что носледова гелыюсть Х}, Хг, Xk
выборов не изменяется при эквивалентных преобразованиях
матрицы. Теорема доказана.
Очевидно, справедливость утверждения не нарушается при
неоднократном применении эквивалентных преобразований
к матрице С.
Так как элементы любого выбора не образуют замкнутых
цепей между собою, то па каждом шаге можно построить
эквивалентное преобразование, которое обращает х-выбранные
элементы в нуль. Для этого достаточно, например, к элемен-
там каждого столбца (строки) прибавить число, противопо-
ложное по знаку алгебраической сумме числа, прибавленного
к строке (столбцу), и величины х-выбранного элемента, обра-
щаемого в пуль.
Матрица с нулевыми х-выбранпыми элементами обладает
тем свойством, что оценка любого из ее элементов, не являю-
щегося х-выбраиным, равна самому элементу. Поэтому не
требуется производить огромные расчеты для определения
оценок всех элементов. Для пост роения следующего выбора
достаточно указать наибольший отрицательный элемент
(по абсолютному значению). Если же все элементы преобразован-
ной матрицы оказываются нео трпиательнымп при нулевых
х-выбранпых элементах, то последний выбор и есть оптималь-
ный. Из инвариантное ги носледова гелыюс ти матриц следует,
что оптимальный выбор есп> в то же время и оптимальное
решение. В самом деле. Оптимальный выбор с эквивалентно
преобразованной матрицей, у Koiopoii х-выбранные элементы
равны нулю, обладает тем свойством, чю скалярное произве-
дение для него меньше (пли, в крайнем случае, равно) ска-
лярного произведения любого из решений. Поэтому найденный
нами оптимальный выбор есть оптимальное решение.
§ 15.	Алгоритм нахождения оптимального решения
1.	Условия задачи записываются в виде таблицы.
II.	Определяем первый выбор.
111.	Обращаем х-выбранные элементы в нули. Если при этом
остальные элементы преобразованной таблицы оказываются
неогрпцательнымп, го первый выбор и является оптимальным.
77
IV.	Если после обращения х-выбраиных элементов в нули
в таблице имеются отрицательные числа, то находим наиболь-
ший отрицательный элемент (по абсолютному значению).
V.	Образуем замкнутую цепь наибольшего отрицательного
элемента с обращенными в нуль х-выбранными элементами
и строим второй выбор, передвигая по цепи число х/у., равное
наименьшему в четной полуцени.
VI.	Так как наибольший отрицательный элемент стал
х-выбранным, то обращаем его в нуль, но так, чтобы осталь-
ные х-выбранные элементы, соответствующие новому выбору,
оставались также равными нулю.
VII.	Эти шаги повторяем до тех пор, пока не придем
к выбору, для которого в преобразованной таблице все
х-выбранные элементы равны нулю, а остальные -неотрица-
тельные. Этот последний выбор и будет оптимальным реше-
нием.
VIII.	Для подсчета стоимости транспортировки, соот-
ветствующей оптимальному решению, следует соединить в одну
таблицу первоначальную матрицу стоимости и последнее
решение. Сумма парных произведений чисел, стоящих в клет-
ках таблицы, определяет значение стоимости перевозок.
Для наглядности процесса нахождения оптимального реше-
ния приведем его геометрическую интерпрегацпю (рис. 20).
Отложим ио горизонтальной осн номера решений, а по вер-
тикальной оси соответствующие значения стоимости. Вначале,
построив первое решение, мы находим одну из точек Дг
Обращение х-выбранпых элементов в нуль приводит нас на гори-
зонтальную ось в точку.4'. Если для эюй ючкп нреобразован-
78
ная таблица не имеет отрицательных элементов, то решение,
соответствующее точке Д,, и есть оптимальное. Если этим
свойством преобразованная таблица не обладает, находим
точку А2 и вновь возвращаемся на оси в точку Д' и иссле-
дуем, не достигли ли мы оптимального решения. Если нет,
определяем точку Д3 и т. д.
Через конечное число шагов мы обязательно достигнем
последней точки, коюрой и соответствует оптимальное реше-
ние. Мы получим ломаную стоимости, как изображено на рис. 20.
Как видно из рисунка, с каждым шагом значение стоимости
уменьшается (во всяком случае не возрастет).
Продолжим решение транспорт ней задачи, поставленной
на стр. 72. Первый выбор для нее представляется таблицей 4.
Обращаем х-выбранные элементы в нули. Для этого из эле-
ментов первого столбца матрицы стоимости вычтем 4, из
элементов второго столбца — вычтем 1. В результате х-вы-
бранные элементы, стоящие па пересечении второй строки
с первым и вторым столбцами, обратятся в нули. Из элемен-
тов третьего столбца вычтем 6, тогда х-выбранный элемент,
стоящий на пересечении второй строки с третьим столбцом,
также обратится в нуль, а элемент матрицы стоимости, стоя-
щий на пересечении третьей строки и третьего столбца,
примет значение, равное (4 — 6—-—2). Прибавим к элементам
третьей строки матрицы стоимости число 2, а из элементов
четвертого столбца вычтем число 5. Тогда элементы, стоящие
на пересечении третьей строки с третьим и четвертым столб-
цами, обратятся в нули.
Наконец, остается обратить в нуль х-выбранпый элемент,
стоящий на пересечении первой строки и четвертого столбца.
Для этого к элементам первой строки нужно прибавить число 3.
В результате такого эквивалентного преобразования матрицы
стоимости таблица 4 примет вид таблицы 5.
79
Как видно, в таблице 5 имеется отрицательный элемент (—1).
Поэтому мы не можем быть уверены, что первый выбор явля-
ется оптимальным. Так как в данном примере имеется один
отрицательный элемент, то он же является и наибольшим
(но абсолютной величине).
Образуем замкнутую цепь этого отрицательного элемента
с х-выбранными и построим второй выбор, как показано
в таблице 6. Для этого передвинем из четной полуцени в не-
четную число единиц груза, являющееся наименьшим в четной
полуцени.
Так как число —1 стало х-выбранным, го его надо обра-
тить в нуль, для чего снова подвергнем матрицу стоимости
тождественным преобразованиям. Прибавим к элементам пер-
80
вого столбца в таблице 6 число, равное 1. В результате
получим таблицу 7, в которой нет ни одного отрицательного
элемента, а все х-выбранные элементы равны нулю.
Поэтому выбор, представленный в таблице 7, является
оптимальным решением. Соединим в одну таблицу 8 исходную
Т а б л и ц а 8
\ А-		5	ю	20	15
		/		л	
10	7	ж			
15 25			9^- ”		
матрицу стоимости и оптимальное решение. Стоимость пере-
возок, соответствующая этому плану, составляет C=2-10-f-
4~ 5  6-j-10 • 1-|-5 • 34  15-J-1 • 5- .-140 единиц стоимости.
Согласно этому плану перевозку нужно организовать сле-
дующим образом (рис. 21). Весь груз первого пункта отправ-
ления транспортируется к четвертому потребителю; второй
пункт отправления обеспечивает 10 единицами груза второго
потребителя и 5—’третьего; с третьего пункта отправления
5 единиц груза транспортируется к первому потребителю,
81
15 — к третьему, а остальные 5 единиц груза доставляются
четвертому потребителю. При таком плане стоимость перево-
зок (при всех прочих равных условиях) будет минимальна.
Рассмотрим более сложный пример.
Пример. Найти оптимальный план перевозки однородного
груза из четырех пунктов отправления в шесть пунктов назна-
чения при условиях, определяемых таблицей 9. В этой таблице
ait bj выражены в тысячах тонн, а с,у—в тысячах рублей.
Табл ица 9
Перепишем еще раз исходную таблицу, внесем в нижние
полуклетки числа начального выбора и представим весь про-
цесс получения оптимального решения в виде последователь-
ности таблиц 9а, б, в, г, д, е.
Первый
выбор
Ct=75
Т а б л и ц а 9 б
Квадратикам
отмечен элв-
мент, кото-
рый вводится
врешение
По цепи перено-
сим 5единиц.
Стоимость
понижается
на 20 единиц
82
Т а б л и ц а9в
Второй
выбор
Сг-55
Заштрихован элемент, который исключается из решения
По первой цепи пере*
носим 2. по второй Z
Стоимость понижа-
ется на 2 Z+21 ~
= Б единиц
Таблица 9г
По цепи переме-
щаем единицу.
Стоимость пони-
жается на 1-1 =
= J стоимости
+7	+/ +/
Таблица 9 д
Соединим вместе первоначальную таблицу стоимости и
оптимальное решение (таблица 10).
первого варианта on шпальный вариант обеспечивает снижение
стоимости переволок на 27 тыс. рублей, так как расходы на
перевозки ио первому варианту составляют 75 тыс. рублей,
а но оптимальному только 48 тыс. руб.
Интересно отметить, чю таблица с оптимальпым вариантом
(5-й выбор) указывает не одно оптимальное решение, а все
решения с той же стоимостью.
Действительно, в агой таблице имеются нулевые элементы,
не отмеченные кружком. Отметим их звездочкой. Каждый из
этих элементов образует замкнутую цепь с элементами решения.
Производя однократные замещения по тем же правилам,
можно получить другие решения при той же стоимости.
Это позволяет принять за оптимальное решение, например,
такое, как представлено в таблице 11. Стоимость, соответ-
ствующая этому плану перевозок, также равна
С = 1 .24-4• 34 • 1 4 1.5-!- 1 • 1 -|-1 .2-1- 1-245-1 4
4-3-5 = 48.
Легко видеть, что в этом случае каждая замкнутая цепь, со-
стоящая только из нулевых элементов, обладает тем свойством,
что у соответствующей замкнутой цепи исходной таблицы
суммы стоимостей четной и нечетной полуцепей равны и это
позволяет переносить ио цени х'Р."1 без изменения общей сто-
имости. В ряде случаев определение всех оптимальных решений
оказывается очень полезным. Как будет рассмотрено дальше,
применяя к множеству оптимальных решений правила пахожде-
84
пня оптимального варианта перековок по времени, можно ука-
зан) план перевозок, реализация коюрого i ребуе г наименьшего
времени.
Наконец, скажем несколько слов о нахождении замкнутой
цени, образуемой наибольшим отрттцателытым элементом
с х-выбранными элементами. Исли т и « небольшие, то цени
видны непосредственно, как эго и имело место для рассмот-
ренных выше примеров. Если же т п п сравнительно велики,
то нахождение замкнутой цени проще всего устанавливается
следующим образом. Вычеркиваются строка н столбцы, содер-
жащие по одному о । меченному нулю (гак как для образования
цепи надо иметь в столбце или строке не менее двух нулей);
после первого вычеркивания во всей таблице делается второе
и т. д., пока не придем к положению, из которого сразу видна
замкнутая цепь.
Так как подробное решение примера с большой таблицей
заняло бы много места, то в данной работе ограничимся рас-
смотрением случая, при котором необходимо найти замкнутую
'Г а б I и ц а 1 1
цепь. Эта ситуация представлена в таблице 12. Вначале вы-
черкиваем все с голбцы, содержащие по одному пулю (конечно,
за исключением столбца, в котором находится наибольший
отрицательный элемент). Далее рассматриваем все строки и
вычеркиваем те, в которых осталось по одному пулю. Снова
просматриваем столбцы и делаем то же самое.
Теперь для построения замкнутой цени осталось соединить
оставшиеся, начиная с отрицательною числа и обходя нулевьте
элементы, например, но часовой стрелке.
Мы рассмотрели методику решения транспортных задач но
т	п
критерию стоимости при условии, что
этом случае количество груза во всех пунктах отправления
равно количеству погребною груза для всех пункюв назна-
чения.

т	п
Если 2 «/>2. Лто вводим фиктивный пункт назначения
/=.-1
т	п
с потребностью Л„_(1=2Я/— 2^/ 11 с0 стоимостью пере-
возки груза в этот пункт С/ HF]=0 для z = 1, 2, . т.
Т а б .1 и и а 12
Пример. Пусть в четырех хранилищах имеется со-
ответственно 70, 40, 50, 20 тонн горючего. Требуется сплани-
ровать перевозки горючего к трем потребителям так, чтобы
затраты на транспортировку были минимальны. Пусть условия
задачи определяются таблицей 13. В этом случае построение
первого решения целесообразно вести по столбцам. Это реше-
ние отмечено кружками в таблице 14.
Легко проверить, что решение, представленное в таблице 14,
является оптимальным. Согласно эюму решению к первому
86
потребителю надо подвезти 10 тонн из первого и 20 тонн
из четвертого хранилища, ко второму потребителю 30 тонн из
первого и 10 тонн из второго хранилища, к третьему потребителю
30 тонн из второго хранилища, при этом в первом хранилище
еще остается 30 тонн горючего, запасы третьего хранилища
в данных условиях использовать нецелесообразно.
Т а б л и ц а 14
	30		30	80
70	(^'0		5^	^^30
40	8^'		^0	0
00	/	5	6	
го			° s''''	yS''
Задачи первого и uiop.ro типа, методы решения которых
описаны выше, связаны с организацией перевозок с точки
зрения экономии средств на последние. Что касается задач
третьего типа, то, как говорилось выше, они связаны с орга-
низацией перевозок в кратчайшие сроки. Метод решения
такого типа задач изложим в следующей главе.
Таблица 15
J г 3	4	5 в 7	8	9 Ю П 12 13	14
	18	13	г;	7	18	1г	7/	30	15	9	го	8	и	7
33	18	3	15	7	6	1	12	8	4	3	17	19	3	6
18	15	го	17	3	4	4	3	6	11	14	г	13	б	1
г	6	в	11	2	7	1	4	7	3	11	17	16	г	3
38	9	7	3	13	13	14	И	9	4	5	!9	18	3	7
16	7	1в	15	1	7	г	4	18	13	3	1	19	го	3
гз	11	17	14	9	7	3	в	8	7	4	5	11	13	14
31	9	3	1	9	2	16	19	з	7	11	14	г	4	7
38	1г	12	11	9	3	13	14	9	7	8	7	6	3	15
3	7	1	4	5	8	13	го	в	6	4	19	17	1	3
Изложенный алгоритм решения транспортной задачи по
критерию стоимости может быть представлен как однообраз-
ный процесс арифметических и логических операций. Такой
процесс легко реализуется на электронной вычислительной
машине. На рис. 22 приведена упрощенная блок-схема реше-
ния задачи. В соответствии с этой блок-схемой составлена
программа решения задачи на машине «Стрела».
87
Для матриц порядка т X п <Z 500 время решения задачи
не превышаете—10 минут; для Maipnn порядка т\п <4 500
Рис. 2'2.
при решении задачи .может потребоваться до 25—40 минут;
для матриц порядка т X п в несколько тысяч для решения
задачи на машине «Стрела» требуется до 8—10 часов.
Так, на машине (Стрела» была решена следующая транс-
портная задача.
88
Требуется из девяти пунктов отправления перевезти груз
к четырнадцати пунктам назначения (таблица 15). Начальный
выбор, полученный на машине, представлен в таблице 16.
Т а б лица 16
г з «	5 s / д э ю п /г и и
	18	13	21	7	18	12	11	30	15	9	80	8	11	7
33		13				12				8			i	
18											11			7
2				2										
38			21						6				11	
14				5						О	9			
Тз					13				9	1				
31					Г}			18				8		
~8	18						8	12						
LX							3								—
Конечный выбор, соответствующий оптимальному решению,
изображен в таблице 17.
Легко подсчитать, что величина стоимости, соответствую-
щая начальному выбору, имеет значение, равное С = 971,
а для оптимального 703.
Таблица 17
1	2	3	4	5 в 7	8	9	10 11	12 13 14
	18	13	21	7	18	12	11	30	15	9	20	в	11	7
33		13				12	11		8					
18			—											7
г	2													J
38	п		20						7					
~1з	1			7							6			
										9	14			
31			1					30						
38	1				18							8	11	
3	3													
Время решения этого примера (в один просчет) составило
около одной минуты.
Время решения другой транспортной задачи с матрицей
стоимости ту^п — 30X88 (при двойном просчете) составило
37 минут.
ГЛАВА IV
РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ ПО КРИТЕРИЮ
ВРЕМЕНИ
При составлении плана перевозок в ряде практически важ-
ных случаев крайне необходима экономия времени. Например,
при транспортировке скоропортящихся продуктов необходима
доставка их в пункты назначения в минимально возможное
время. Во время хлебоуборочной кампании очень важным фак-
тором является наиболее быстрая вывозка зерна па заготови-
тельные пункты.
Задача такого типа является задачей транспортировки ио
критерию времени. Ниже рассматривается один из алгоритмов
решения транспортной задачи по критерию времени.
§ 16. Постановка и решение задачи
Пусть имеется т пунктов отправления однородного груза
и п пунктов назначения. Обозначим через nt, аг, . . .
. .., ат количество единиц груза, находящегося в пер-
вом, втором, ...,/-м, да-м пунктах отправления, а через
bv Ьг, Ь,, ..., Ьн — количество единиц груза, которое
должно быть доставлено в каждый из п пунктов назначения.
Пусть	tjj	есть	время (в	сутках, часах),	потребное па перевозку
груза	из	z-го	пункта	отправления в	у-й пункт назначения,
а — количество единиц груза, которое мы планируем пере-
везти	из	z-го	пункта	отправления в	у-й пункт назначения.
Требуется найти оптимальный план перевозок, т. е. такие
неотрицательные числа xi;-, при которых время доставки всех
необходимых грузов к пунктам назначения было бы минимально.
Математическая формулировка этой задачи сводится к сле-
дующему.
90
Задана система линейных алгебраических уравнений:
(/ = 1, 2, ..., т),
U = 1, 2, . . ., п),
(27)
причем числа а, и bj удовлетворяют условию
Пусть, кроме тою, задана матрица времен 7'=(/)..). Каждому
неотрицательному решению А'~(х/у) системы уравнений (27),
т. е. плану перевозок, соответствует определенная матрица
7’х.= (/;у), элементы которой равны = если х;уЛ> О,
Z/; = 0, если х(у = 0. Обозначим через /™ах наибольший эле-
мент матрицы 1'х 
Требуется определить такое неотрицательное решение Л'опт,
углах --	.max
для которого Тх будет наименьшим среди всех tx , соот-
отп
ветствующнх различным неотрицательным решениям X. Условия
этой задачи удобно представить в виде таблицы 18.
Т а б л и н а 18
Эта задача, как легко показать, не решается с помощью
алгоритма, описанного для транспортной задачи по критерию
стоимости.
Так, например, решение, для которого линейная форма
достигает минимального значения, как правило,
не является оптимальным но времени. Для примера, заданного
таблицей 19 и изображенного на рис. 21, оптимальное решение
91
по минимуму линейной формулы С = 2 bjxij представ-
ляется таблицей 20. Из этой таблицы видно, что весь груз
будет доставлен в пункты назначения только через шесть
Т а б ,т и ц а 1'1
суток. С другой стороны, варианту перевозок, представлен-
ному в таблице 21, соответствует несколько большее значение
Т а б л н ц а 20
С-2'10+ Ь 5177/7 а 551 015 + 15- 150
С-2'10+3-5+0'20 + 1-W+ 0-5 = 105
линейной формы, но перевозка грузов к пунктам назначения
выполняется за четверо суток.
При перевозке скоропортящихся продуктов расходы на до-
полнительный пробег вагонов (автомашин) окупаются сохране-
нием качества тысяч тонн продуктов пи гания, предназначенного
для населения.
Доказательство описываемого ниже метода решения сле-
дует из общей теории линейного upoiраммировапия, изложен-
ной в главе 11.
92
Описание метода рассмотрим на решении задачи, заданной
таблицей 22, Из этой таблицы следует, что требуется пере-
везти 125 единиц груза, находящегося в шести пунктах
отправления, в семь пунктов назначения. Пусть числа этой
таблицы означают время в часах, необходимое для перевозки
груза соответственно из пункта отправления в пункты назна-
чения. Так, например, число 31, стоящее на пересечении
четвертой строки и четвертого столбца, показывает, что время
на перевозку груза из четвертого пункта отправления к чет-
вертому пункту назначения составляет 31 час. Требуется найти
оптимальный по времени план перевозок.
Т а б л и ц а 22
V4	20	13	11	27	0	5	40
75	*41	13 ^/5	^13	7..^		29^	19 ^5 — 17 ./-77
7			36 ^23	4o6^ ^^3.24		6^ 26	
45	"6^			21/f	21	29^ ^36	31
30	27^ 'S'	12 ^42	39	31 ^3^44	^3^45	36 _^^46	12^ ^^47
12	17	17^5	32^	36^ ^54		16 5''	
16	75^	38^ Хб2	16^5 ^•^63	зз^5			
Вышенаписанную таблицу (будем называть ее малой) пред-
ставим в виде большой таблицы (таблица 23).
Верхняя строка содержит индексы переменных х(]- от 1 1
до 67, а нижняя — значения t-j, содержащиеся в соответствую-
щих клетках Ij. Например, пара чисел 43 в верхней строке
означает место переменной xls, а соответствующее этой пере-
менной значение времени /13 есть 39; поэтому 43 и 39 нахо-
дятся в одной колонке.
Вся таблица разстелена на полосы. Число полос равно
числу пунктов отправления или, что то же, — числу строк в
исходной таблице. Кроме того, таблица разделена горизонталью,
так что в верхней полуполосе шесть строк — число строк исход-
ной таблицы, а в нижней — семь, число столбцов ее. В верхней
полуполосе против каждого числа написано по семи минусов
в соответствующей вертикальной полоске. Так, против 30 ми-
нусы написаны в четвертой полоске. Если посмотреть на
исходную таблицу, то увидим, что такая запись означает
93

выражение остатка груза в четвертом пункте отправления:
30 — х41 - -	- xit
•^44	Л43	'^44	'^4 7'
Подобно этому в нижней полосе положение минусов в каждой
строке выражает значение недостатка груза в пунктах назна-
чения. Так, расположение минусов против 27 означает, что
недостаток груза и пункте назначения, соответствующем чет-
вертой колонке, равен
27
Иначе говоря, расположение минусов в таблице соответствует
уравнениям, выражающим условия задачи.
Построим первое решение, используя способ, который при-
менялся в главе 111. 15 единиц первого пункта отправления
распределим между пунктами назначения с наименьшим време-
нем пробега; 7 единиц второго пункта отправления — между
не удовлетворенными еще пунктами назначения с наименьшим
временем пробега и т. д. Это дает нам первое решение (вооб-
ще говоря, еще не оптимальное), представленное таблицей 24,
Т a fi л и ц а 24
Как видим, элементарное пос троение привело к решению,
реализация которого требует 28 часов на перевозку грузов.
Это позволяет нам в дальнейшем исключить из рассмотрения
клетки с !'(-7)>-28, что и сделано в приведенной таблице.
Для построения следующего варианта решения, реализация
которого требовала бы менее 28 часов, обратимся к большой
таблице. Построение первого выбора применительно к этой
таблице происходит так: в нижней строке значений оты-
скиваем наименьшее из чисел в первой полосе. Это — число 7,
соответствующее колонке 14, т. е. переменной х]4. Просматри-
вая эту колонку, убеждаемся, что х14 можем положить равным
95
15, так как запас груза составляет 15 единиц, а потреб-
ность— 27. Это позволяет записать переменную х14 слева от
равенства в первой строке, а знак минус на пересечении пер-
вой строки и колонки 14 опустить. Что касается второго
минуса этой колонки, стоящего против 27, то его также
нужно опустить, а из строки, соответствующей числу 27, вы-
честь строку, соответствующую числу 15.
В первой и десятой строках в первой полосе произошли
изменения. Эти изменения имеют вид:
*.4=151-1-1-1 I-I-I-I,
= 12| + | + ) + | l+1-H + i-
Переходим ко второй строке и второй полосе. Отыскиваем
наименьшее из чисел /;у, второй полосы. Эю число 6, соот-
ветствующее переменной х26. Пробегая колонку но вертикали,
выбираем наименьшее из двух чисел, стоящих слева против
минусов этой колонки. Это число 5. Записываем слева от
равенства против 5 переменную х2а, опуская минус, стоящий
на пересечении этой строки и колонки 26, Минус опускаем
также на пересечении второй строки и колонки 26, а из вто-
рой строки, соответствующей числу 7, вычитаем строку,
соответствующую числу 5. Во второй строке остается число 2.
Это означает, что груз второго пункта отправления еще не
распределен между пунктами назначения. Поэтому во второй
полосе в строке значений /(.. отыскиваем следующее по вели-
чине число. Это число 7, стоящее в колонке переменной х21.
Пробегая по колонке, находим наименьшее из чисел слева
против минусов колонки (20, 2). Опускаем минусы в колонке 21,
записываем слева от равенства против 2 переменную х21 и
вычитаем из седьмой строки вторую. Этим заканчиваем рас-
пределение единиц второй строки. Этот процесс продолжаем
до распределения единиц шестой строки. В результате полу-
чаем первое решение, совпадающее с решением, записанным
в таблице 24. Большая таблица теперь преобразовалась
в таблицу 25.
В правильности решения убеждаемся отсутствием «»
и «—» в одной из строк. В этой строке, в случае отсут-
ствия ошибок в распределении, должны быть только нули.
Такой строкой в данном примере оказалась последняя. (В силу
т	п
условия	bj одно из уравнений системы (27) должно
быть следствием остальных.)
9S
Таблица 25
В таблице колонки, соответствующие основным пере-
менным, обозначены прямой штриховкой, а колонки, для
которых соответствующие /,.>-28,—косой. Последние из
дальнейшего рассмотрения исключаем. Таблица 25 указывает
пути построения лучшего варианта по сравнению с первым.
В самом деле, нам желательно найти такое решение, в кото-
ром бы переменная, стоящая в той же колонке, что и = 28,
т, е. хв7, равнялась бы нулю. Но шестая строка в этой таб-
лице показывает, что уменьшение значения переменной хв7
может быть получено за счет увеличения или или х,,.
J	J	61’	66
личения ая1. Пробегая но колонке 61, находим, что наимень-
шим числом, стоящим с левой стороны таблицы против «—»
колонки 61, является значение аЯ7=5.
Теперь произведем преобразование последней таблицы сле-
дующим образом. Исключим колонки с косой штриховкой и
колонку, соответствующую переменной а67 (или, что то же,—
числу равному 28). Вместо хв7 напишем хв1. Далее, из
строк с минусами в колонке 61 вычтем строку, соответствую-
щую переменной хв1, а к строкам с плюсами в колонке 61
прибавим строку, соответствующую той же переменной, после
чего в колонке 61 все '• — - и «	» исчезнут.
В результате получим таблицу 26. Из этой таблицы сле-
дует, что нами построено второе решение, реализация кото-
рого требует значительно меньше времени: не 28 часов,
а только 21. (Заметим, что если бы обращение переменной
хв, в 0 мы начали производить не за счет увеличения хв1,
а за счет увеличения л'в5, то был бы построен вариант реше-
ния с максимальным временем = / — 23. После этого, вы-
черкивая все колонки с /(у^>23, нам нужно было бы сделать
еще шаг для построения третьего решения с максимумом tff = 21.)
Отметим переменные, изменение которых привело ко вто-
рому решению: xe,, xJS, х17, х31, х15, хв1. Эти переменные
образовали замкнутую цепь (таблица 27). Занумеруем клетки
'Г а б л и и а 27
	20	13	11	27	9	5	40
15	12^--	13 18^'	‘36^	*40^	8	29~^	5^^
7					"38^		777^
45	11 гт^	20 /0	Z? 12^'''	''ЗО. 39^	21 ^9	21		З!^'
30					5	'35^	1г^9>
							
1г	О//'	17^	'32^	33^	гг^		
16	15^	'38^	,В^)	"33-^	23^		
с переменными, образовавшими цепь, принимая клетку с пере-
менной л'в7 (подлежащей исключению) за первую. Эта цепь
обладает тем свойством, что в ее нечетных клетках находятся
обязательно х-выбранные элементы, а в четных—значения
t	где /“7СК — значение /,-у, подлежащее исключению
(в данном случае = 28). Назовем такую цепь разгрузоч-
ной. После нахождения разгрузочной цепи для образования
нового решения передвигаем по цепи количество единиц груза,
равное минимальному из них в нечетной полуцепи. Это построе-
ние на малой таблице приводит нас ко второму решению,
совпадающему со вторым решением, построенным на большой
таблице. Исключим из дальнейшего рассмотрения колонки
(клетки) со значениями /.у. (>21. В результате получаем малую
таблицу 28 и большую таблицу 26 (считая колонки 41, 55,
65 вычеркнутыми). Спрашивается: имеется ли более оптималь-
ное решение, т. е. решение, реализация которого требует
менее 21 часа? Для ответа на поставленный вопрос обращаемся
к таблице 26. В строке значений tif отыскиваем наиболь-
шее— 21. Этому значению /31 = 21 соответствует переменная
х в строке которой находятся только «-}-». Отсутствие
99
«—» означает невозможность уменьшить значение .vsl за
счет какой-либо переменной. Вывести х31, а следовательно, и
освободиться от /31 —21 не нредс тавляе i ся возможным. Таким
образом, полученный последний вариант является оптимальным
по времени. Его реализация, как уже сказано выше, требует
21 часа. В малой таблице 28 в этом случае не представляется
возможным построить разгрузочную цепь.
Для облегчения уяснения метода нахождения оптимального
варианта по времени мы пользовались большими и малыми
таблицами. В действительности при решении таких задач
Т а б л н ц а 28
С=17К К
требуется одна или большая, или малая шб.тица, исполненная
в карандаше. Переход от варнапia к варианту совершается на
одной таблице посредством карандаша и резники.
Правила нахождения оптимального варианта по времени при
пользовании малой таблицей сводятся к следующему:
1.	Записываем условие задачи в малой таблице.
2.	Находим первое решение (например, указанным выше
способом).
3.	Определяем б/1”*, соответствующий этому решению.
4.	Зачеркиваем в таблице все клетки с ft ~у>
5.	Исследуем	на наличие разгрузочных цепей
с оставшимися элементами в таблице.
6.	При наличии разгрузочных цепей строим новое решение.
7.	Если не представляй гея возможным полностью разгру-
зить клетку, соответствующую (ооратнть соответствую-
.Л них
щее в 0), то решение с /// является оптимальным.
8.	При полной разгрузке клетки с Z;ynjx находим /;/тах во
вновь полученном решении.
100
Мы выполнили первый шаг на пути к получению опти-
мального решения. Если при этом ие получено оптимальное
решение, то надо выполнить второй шаг, применяя вновь
правила из пункта 4.
Для получения оптимального решения необходимо будет
совершить конечное число шагов.
Единственная трудность при пользовании этими прави-
лами заключав таи в выявлении разгрузочных цепей. В этом
отношении использование большой таблицы, правила прсюбра-
зовання которой описаны достаточно подроопо выше, дает
возможность получить онгнмальное решение без осооого труда.
Можно привести и другие приемы решения этой задачи.
При малых т и и такие задачи могут быть решены
вручную. При больших т и п так же, как и в задачах по
критерию стоимости, необходимо использование электронных
вычислительных машин. При том машинное время решения та-
ких задач, для соо свете i вующпх т и «, примерно совпадает
с затратами времени при решении задач ио критерию стоимости.
§ 17. Решение задач транспортировки с учетом времени
и стоимости
В практических условиях может представиться более целе-
сообразным реали нация плана перевозок, являющегося неко-
торым средним между оптимальным ио времени и оптималь-
ным но стоимости. Для просто in изложения предположим,
что стоимость пропорциональна времени па перевозку,
т. е. с,у —А7.,..
Для рассмотренного выше примера оптимальный вариант
ио стоимости представляется таблицей 29 и выполняется, как
Т л б л н н a 2Q
С-КИЛ' К
101
видно, за 28 часов при стоимости затрат на перевозки
С~К(1-15-4-6-5-4- 10-2-1- 11 -20 -1-20  13-4-21 -12 4-5-9-|-
-(-12-21-|-14-12~4-16-11-4-28-5)=7<-1668 единиц стоимости.
Стоимость перевозок, соответствующая оптимальному варианту
Таблица 30
X	20	13	11	27	9	5	40	
15	12/^	13//		7/(и\	8		19//	+ 74+4
7		1В//					10/-/	+ <?
45		2О/&		/^)				+ 4
30		12//	/х				12/^	+ 20
Z2		17//					,W' W	+ 18
75		X'		х				
	-15	-20 -4	-16	~21 -4	-21 -4	-в -8	-14 -18	
по времени (таблица 28), составляет С— /<(7• 15-|-7-24-
--6-5-4- 11 • 134-20-134-21 -124-21-74-5-24-12-284-
--14-124" 15-54“ 16• 11) == 1716/С единиц стоимости. Затра-
чивая дополнительную стоимость, равную 1716^— 1668^=:
= 48 К, мы завершим операцию перевозки грузов на 7 часов
Т а б л и ц а 31
X;	20	13	11	27	9	5	40	
15	15/'/	T/^		(^^5	1/S'		5^/	
7		Z'/'				(Q-/'5	^2	+14
45	Ъ'-'К			^^2	^5	Xc		
30		8//						
IZ	20//	ll^'				20//	^12	
10	^5							
						-14		
раньше по сравнению с планом перевозок, определяемым
оптимальным вариантом по стоимости.
Как следует из рассмотренного выше примера, сравнитель-
но небольшие дополнительные расходы на перевозки могут
значительно сократить время на операцию транспортировки.
В случае, если заданы сроки выполнения операции транс-
103
портировки, то, используя описанные методы, можно найти опти-
мальный вариант по стоимости, реализация которого осуществ-
ляется в пределах заданного срока. Если же потеря времени не-
допустима, то определяем оптимальный вариант по времени.
Если полученный вариант с не является лучшим по стои-
мости, то, применяя алгоритм нахождения оптимального реше-
ния по минимуму линейной формы, можем получить оптималь-
ный по стоимости из всех оптимальных по времени
(выполняемых за одно и то же время, равное //;"f). Так,
оптимальное решение по времени для рассматриваемого примера,
представленное таблицей 30, не является оптимальным ио
стоимости. В самом деле, обратим х-выбранные элементы
в 0 (при обращении х-выбранных элементов в 0 значения
элементов, стоящих в перечеркнутых клетках, во внимание не
принимаются) (таблица 31).
В результате получим таблицу, в которой имеется отрица-
тельное число (—14). Преобразовав еще раз таблицу 31,
получим таблицу 32. В преобразованной таблице 32 х-вы-
бранные элементы равны 0, а остальные неотрицательные.
Т а б л и ц а 32
\ А	20	13	11	27	9	5	40
15	15^'	7^/'		©©''15	1^'"'		б/'
7	14/'	16 z'				©^5	©/''г
45	©^©5	^©3		©/'©2	©©''©		
30							©©''©6
12	20/"	О/''				6 z''	©©^©2
16	%^5		©/'п				
С-1688К
Поэтому построенный вариант решения является оптимальным
по стоимости. Стоимость реализации этого варианта, выпол-
няемого также за 21 час, составляет С— 1688 К, что значи-
тельно меньше, чем 1716/6.
* *
*
За последние годы методы линейного программирования
находят все более широкое применение в таких областях, как
экономика, техника, военное дело и т. п. Теория и методы
103
линейного программирования непрерывно совершено гвуются,
позволяя решать все новые и новые задачи. Бурное развитие
вычисли тельной техники сделало возможным практически
решать любые задачи из области линейного программиро-
вания.
Дальнейшее развитие методов линейного программирования
и применение их к решению iiapo'iiioxodniic i венных задам
будут способствовать улучшению организации и планиро-
вания производства в нашей стране.
ЛИТЕРАТУРА
1.	Л. В. Канторович, Ма тема т ические истцы организации в ила-
ииронапия iipoiiiBo.'ic'iB.i, изд. ЛГУ, 1939.
2.	Л. В. Канторович и М. К. Га пурин, Математические мето-
ды анализа грузопотоков, со. АН СССР '..Проблемы повышения
эффектI1H1IOCTH работы транспорта >. 1953.
3.	Б. М. Каган п Т. М. Т е р-М и к а э л я п, Решение инженерных
задач па автоматических цифровых вычислит единых машинах, Гос-
эттерт’оиздат, 1958.
4.	А. И. К н т о в, Электронные цифровые машины, изд. «Ков. радио»,
1956.
5.	А. Г. Курош, Курс высшей алгебры, Физматгттз, 1959.
6.	Л. А. Л тостер тт и к, Выпуклые фшуры и многогранники, Гостех-
издат, 1956.
7.	С. И. Черников, Линейные неравенства, УМН, т. 8, цып. 2
(1953).
8.	Н. В. Черникова, Паимспьише и наибольшие значения линейной
формы па многограннике, УМН, т. 12, выи. 2 (1957).
9.	A. Charncs, W. W. Cooper and A. lie ml er.son, An Intro-
duction to Linear Programming, John Wiley, New York, 1953.
10.	C. W. C h и r c h ni a n, R. L. A с k о f f, C. 1.. A г и о f f, Introduction
in Operations Research, London — New York, 1955.
J1.	D. Ch a nd I e r, Linear Programming and Computers, New York,
1955.
12.	A. G lais el, Algorithm for Solution of Transportation Problem,
1955.
13.	S. V a j d a, The Theory of Cemes and Linear Programming, London—
New York, 1956.