/
Текст
ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ
ВЫПУСК 33
А. С. БАРСОВ
ЧТО ТАКОЕ
ЛИНЕЙНОЕ
ПРОГРАММИРОВАНИЕ
ГОСУДАРСТВЕННОЕ ИЗДАТЕЛЬСТВО
ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ
МОСКВА 1959
АННОТАЦИЯ
Книга знакомит читателя с важным разделом
математики — линейным программированием, полу-
получившим i! последние годы широкое применение и раз-
различных областях экономики, техники, военного дела.
В книге дается постановка общей задачи линей-
линейного программирования, методы ее решении и при-
приложения к конкретным экономическим задачам.
Рассматривается применение теории линейного про-
программирования к решению транспортных задач при
минимуме стоимости и минимуме времени перево-
перевозок, а также намечены пут решения задачи с уче-
учетом обоих факторов.
Книга рассчитана на магемагиков, инженеров и
экономистов, занимающихся вопросами математиче-
математического планирования, в частности применением авто-
автоматических цифровых вычислительных машин к
этим вопросам.
Алексей Сергеевич Парсов.
Что такое линейное программироиание.
Редактор Я. Д. Розенкноп.
Техн. редактор К. Ф. НруОно. Корректор ,?. Ft. Моисеева
Сдано а набор 30, VIII 1939 г. Подписано к печати IOXI l!)"i!l г. Бумага S4XWS'/.,,.
Физ. печ. л. 3,23. Услопн. псч. д. 3,33. Уч.-изд. л. 5,40.
Тираж 13.000 экз. Т-ПП-10. Цена книги 1 р. СО к. Заказ № 3534.
Государственное издательство физико-матемагнческоп литературы. ^
Москна, В-71, Ленннск-nii проспект, 13.
Первая О^рлзцосаи тиши рафия имени Л. Л. Жданоиа
Московского городского Сон1 лрхоза. Москна, Ж-34, Валоиаи, 2$.
ОГЛАВЛЕНИЕ
Предисловие .
Введение -
5
Глава 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
§11. Постановка задачи , 66
§ 12. Основные решении транспортной задачи по критерию
стоимости 67
§ 13. Оптимальный выбор 71
§ 14. Инвариантность последовательности выборов эквивалент-
эквивалентным преобразованиям матрицы стоимости 76
§15. Алгоритм нахождения оптимального решения 77
Глава IV. Решение транспортной задачи по критерию вре-
времени . . -. 90
§ 16. Постановка и решение задачи 90
§ 17. Решение задач транспортировки с учетом времени и
cioiiMociii .... 101
Литература 104
1*
ПРЕДИСЛОВИЕ
В данной работе рассматриваются вопросы теории и методы
решения некоторых задач линейного программирования.
Работа предназначена для широкого круга лиц, занимаю-
занимающихся вопросами применения математических методов в орга-
организации и планировании производства.
Рассматриваются основы линейного программирования, при
этом приводятся только те сведения и доказательства, которые
необходимы для элементарного изложения методов линейного
программирования.
Работа возникла па основе лекций, прочитанных автором
в 1957 году для лиц, занимающихся решением задач линей-
линейного программирования на электронных вычислительных ма-
машинах.
Член-коррсспопдепт АН СССР Л. А. Люстериик внимательно
ознакомился в марте 1959 года с материалами лекций, дал
ряд ценных советов и содействовал выходу в свет этой работы.
Автор благодарит проф. А. А. Ляпунова и Н. С. Красиль-
никова за помощь в разрешении трудностей, возникавших
в процессе написания данной работы.
Автор особенно признателен редактору В. Д. Розенкнопу,
тщательная работа которого значительно способствовала улуч-
улучшению книги.
А. С. Барсов
ВВЕДЕНИЕ
Задачи дальнейшего развития производительных сил, улуч-
улучшения планирования социалистического производства, повыше-
повышения экономической эффективности капитальных вложений в па-
пашей стране с каждым юдом приобретают все большее значение.
Многообразие возможных технических решений и путей
развития в современной промышленности, взанмоевнзанность
различных отраслей народного хозяйства и другие экономиче-
экономические проблемы делают' поставленные выше задачи исключи-
исключительно сложными.
При решении этих задач существенную помощь могут ока-
оказать математические методы и, в частности, методы линейного
программировании, а также современные технические средства —
электронные вычислительные машины.
Теория линейного программирования, возникшая в послед-
последние два десятилетия, в насюищее время получила широкое
практическое применение, особенно в вопросах организации и
планирования производства.
Первыми работами в этом направлении были работы члена-
корреспондента АН СССР Л. В. Канторовича. В этих работах
приведены математические методы решения таких задач, как
задача повышения эффективности работы транспорта, определе-
определения оптимальных производственных режимов, рационального рас-
раскроя промышленных материалов и т. п.
В дальнейшем были созданы общие методы линейного про-
программирования, как, например, симплексный, комбинаторный и
другие методы, которые эффективно используются для реше-
решения разнообразных оптимальных задач планирования. Разра-
Разработкой этих методов занимались Dantzig, Charnes и ряд со-
советских и зарубежных ученых.
Линейное программирование охватывает методы решения
ряда оптимальных задач, имеющих дело со многими взаимо-
взаимосвязанными переменными, подчиняющимися определенным
ограничивающим условиям. Постановку задач линейного про-
программирования можно сформулировать следующим образом:
Имеется некоторая величина (например, стпмоогь, время),
являющаяся линейной функцией ряда переменных. Переменные
в свою очередь должны удовлетворять ограничениям, выражен-
выраженным в виде системы линейных неравенств или равенств.
Требуется отыскать такие неотрицательные значения пере-
переменных, при которых величина, являющаяся их функцией, при-
принимала бы наименьшее (наибольшее) значение.
В качестве примера рассмотрим транспортную задачу. Эта
задача может быть сформулирована следующим образом:
Из данных т пункт» отправления, в каждом из которых
имеется по а. единиц груза, необходимо перевезти в каждый
из а пунктов назначения по Ь- единиц того же груза
(/= 1, 2, .. ., т; у=1, 2, ..., и).
Требуется спланировать перевозки таким образом, чтобы
затраты на последние были минимальны. Пусть xtj обозначает
количество груза, перевозимого из /-го пункта отправления
в у'-й пункт назначения. В таком случае задача математиче-
математически сводится к нахождению таких неотрицательных значе-
значений Хц, удовлетворяющих уравнениям
при которых общая стоимость перевозок
становится наименьшей, при этом с^ есть стоимость перевозки
единицы груза из /-го пункта отправления в у-й пункт на-
назначения.
В ряде практически важных случаев задача ставится так:
требуется спланировать перевозку груза из данных т пунктов
отправления в п пунктов назначения так, чтобы операция
транспортировки была завершена в кратчайший срок.
Другим примером применения линейного программирования
может служить следующая задача.
На многих заводах выпуск различных изделий или какой-
либо продукции производится па автоматических линиях. В этих
случаях могут возникать различные вопросы наиболее рацио-
рациональной организации производства.
Пусть, например, цех располагает т машинами (станками)
для производства различных я изделий. Каждая машина /-я
(/==1, 2, . . ., т) характеризуйся определенным />, возможным
месячным рабочим временем, мормон нремепп /(., на изготовление
одной единицы /-го изделия (J = 1, 2 /г), а также сто-
стоимостью Cjj, затрачиваемой па изготовление одной единицы
того же у-го изделия на 1-й машине. Если цеху дано задание
выпустить в наступающем месяце определенное а, количество
каждого из различных изделий, то возникает задача такой
организации работ, при которой задание будет выполнено при
минимальном расходе средств. Если через Xj, обозначить
количество у'-х изделий, производимое па /-м станке, то по-
поставленная задача сводится к такому распределению загрузки
машин, чтобы удовлетворигь условиям
и сделать значение общей стоимости
как можно меньше.
В задачах линейного программирования условии, налагае-
налагаемые на область допустимых значений переменных, определяются
системой линейных неравенств пли равенств, при этом функция,
наименьшее (наибольшее) значение которой находится, явля-
является также линейной функцией тех же переменных. Этот факт
и подчеркнут в названии линейное программирование.
Методы линейного программирования для определения опти-
оптимального решения требуют рассмотрения нескольких решений.
При анализе практических задач, например задачи рациональ-
рациональной загрузки станков пли предприятий, при определенных
ограничивающих условиях переходу от решения к решению
соответствует последовательное рассмотрение различных произ-
производственных программ. Оiсюда происходит название линейное
программирование.
Так как задача линейного программирования есть задача
на нахождение точки области, в которой функция принимает
наибольшее (наименьшее) значение, то, естественно, возникает
вопрос", почему нельзя обойтись известными классическими
методами решения уксфема.тьных задач, например методом
Лагранжа?
Дело в том, что классические методы требуют существо-
существования частных производных функции и точке, где достигается
экстремум. Между тем .чиненная функция достигает экстремаль-
экстремального значения на границе обласш, где частые производные
не существуют.
Эго и послужило причиной создания новых методов реше-
решения экстремальных задач, к числу которых п относится линей-
линейное программирование.
Практика решения задач линейного программирования по-
показывает, что при большом числе переменных для решения
таких задач необходимо применять электронные вычислитель-
вычислительные машины, при этом задачи, на которые затрачивает человек
до недели, машина решает за две-пять минут. При очень боль-
большом количестве переменных эти задачи могут быть решены
только посредством электронных вычислительных машин.
Примером может служить задача определения оптимального
плана перевозок строительного песка к строительным площад-
площадкам г. Москвы. В этой задаче было задано 10 пунктов отправ-
отправления и 230 пунктов назначения. Полученный на машине
«Стрела:> оптимальный план перевозок дал только за одну
декаду июня 1958 года экономию около 11°/0.
Ниже рассматриваются математические основы и методы
решения некоторых задач линейного программирования, в част-
частности транспортных задач.
ГЛАВА I
НЕКОТОРЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ
ЛИНЕЙНОЙ АЛГЕБРЫ
В этой главе излагаются основные понятия и определения
линейной алгебры /и-мериого пространства, необходимые для
решения задачи линейного программирования.
§ 1. Понятие об m-мерном пространстве
Всякая упорядоченная тройка (яг а2, аа) действительных
чисел может бь еометрическп истолкована как точка про-
пространства. В соответствии с этим геометрическим представле-
представлением в математике принято следующее определение: трехмер-
трехмерное пространство есть множество всевозможных упорядо-
упорядоченных троек («,, пг, а3) действительных чисел*). При этом
говорят, что система чисел (av n2, as) определяет точку М
в трехмерном пространстве с координатами ар «2, as пли
вектор Р с компонентами «,, а2, as в том же пространстве.
Для задания некоторых объектов, процессов или состояний
недостаточно трех действительных чисел. Так, определение по-
положения твердого тела в пространстве требует шести коорди-
координат. В случае если район производит определенные промыш-
промышленные и сельскохозяйственные товары, например железнодо-
железнодорожные вагоны, автомашины, хлеб, молоко, спички и т. д.,
то для характеристики промышленного и сельскохозяйственного
производства данного района требуется упорядоченная после-
последовательность действительных чисел. Так, имея таблицу 1,
*) Аналогично множество всевозможных действительных чисел (а,)
есть одномерное пространство, геометрическим образом которого мо-
может служить прямая; множество всевозможных пар действительных
чисел ((?,, п2) ее п. шухмерпое прос ip;inerno, I еометрнчеекпм образом
которого может служиil плоскость.
можно сказать, что район № 2 ежегодно производит а21 тонн
угля, я22 тонн железной руды, п,3 тонн стали, ..., агп тонн
пшеницы-
Подобно этому, например, количество авиационного горю-
горючего различных типов, используемых в дайной стране, количе-
количество товаров различной номенклатуры, находящихся на данном
складе, также определяются с помощью упорядоченной после-
последовательности чисел. ^
Т а б л м ца I
Район N-7
Район N?2
Район N-м
Уголь
(ГП)
?•/
Жел.руда
(ГП)
а,г
а
С/па, и
(///)
a,j
ап
Пшеница
г/т»
а,п
Эти примеры указывают на целесообразность рассмотрения
совокупности всевозможных упорядоченных последовательностей
из т действительных чисел, где т — любое натуральное число.
Известно, что упорядоченная система т действительных чисел
(я,, «а, . .., ah ..., ат) называется т-мерным вектором.
Числа ah i =—1,2, . . ., т, называются компонентами вектора
Р(«„«2, •••,«„)•
Векторы Р(я,, «2, . . ., пт) и Q(A,, l\, . . ., />т) считаются
равными в том и только в том случае, если совпадают их
компоненты, стоящие на одинаковых местах, т. е. при а{ =^t?l
для всех г= 1, 2, . . ., т.
Если нас интересует суммарная производительность двух
районов по различным видам продукции, то, очевидно, она
может быть получена сложением соответствующих производи-
тслыюстей этих районов*). Так, если производительность
района № 1 но каждому виду продукции определяется векто-
вектором Р,(«,,, «12, ...,«,,„), а района № 2 — вектором Р2 («21,
я2„, . . ., <72т), го суммарная производительность этих районов
характеризуется вектором
''') Прои.чцптителыюсть в ланнпм случае (ппачаег количество про-
продукции, выпускаемое за определенный отрезок времени.
10
Если производигелыюсть района определяется вектором
Р = Р(а1, аг, . .., ат), то увеличение производительности
района по каждому из товаров в k раз можно выразить век-
вектором Q, где Q = Q(knJ, ka,, . . ., kam).
Введенные определении являются обобщением известных пра-
правил действий над векторами трехмерного пространства. Распро-
Распространяя понятие трехмерного пространства на последователь-
последовательности действительных т чисел, получаем следующее важное
определение: совокупность всевозможных /и-мериых векторов
Pfflj, a2, ...,ат) с действительными компонентами называется
/и-мерным пространством и обозначается Р<т). По определению,
сложить два /w-мерных вектора Р и Q — значит получить тре-
третий вектор Rr=P-j~Q с компонентами, равными суммам соот-
соответствующих компонент слагаемых векторов. Умножить век-
вектор Р на число /г — значит умножить каждую компоненту на
это число.
Вектор Р(«,, «2, ..., «„) называется пропорциональным
вектору Q(fr,, Л2, ..., />„), если существует такое число /г,
что b1 — kal, fJ--ka2, ...,/>„ =/г«„. В этом случае P—&Q.
Обобщением понятия пропорциональности векторов служит
понятие линейной комбинации векторов.
Вектор Р называется линейной комбинацией векторов
Р., Р„, . ..,РС, если существуют такие действительные числа
/„ /„ ..., /,, что Р = /1Р,+/,Р8+...
чае г-я компонента вектора Р (i=^), 2,
произведений г'-х компонент векторов Р
ветствепно па 1г, 1„, ..., 1Г
Система векторов Р,, Р2, . . ., Рг_,, Рг
зависимой, если хотя бы одни из этих
линейной комбинацией остальных векторов.
Это определение эквивалентно другому:
система некторов называется линейно
¦/„Ру. В этом слу-
т) равна сумме
, . . ., Р„ соот-
пазываетсн линейно
векторов является
зависимой, если
., kr, но
существуют такие действительные числа /г,, k2, .
крайней мере одно из которых отлично от нуля, что имеет
место равенство
В противном случае система векторов называется линейно
независимой.
Если вектор Ро
Р,, Р2, ..., Р„,
является линейной комбинацией векторов
то говорят, что Ро линейно выражается
через систему векторов JP,}, где J=
P,}
что если вектор линейно выражается
2, ...,«. Попятно,
через некоторую
11
подсистему данной системы, ю он будет линейно выражаться
и через систему — достаточно остальные векторы системы
взять с коэффициентами, ранными нулю.
Обобщая эту терминологию, говорят, что система векто-
векторов Q,, Q2, ..., Q9 линейно выражается через систему век-
векторов Р,, Р2, ..., Рн, если всякий вектор Q;, /—1, 2, . . ., s,
является линейной комбинацией векторов системы {Р,}>
)—- 1, 2, . .., п.
Рассмотрим в пространстве Р(т) векторы:
i,0. о, о, .... 0), }
М°. 1, 0, ..., 0),
1,„@, 0, 0, ..., 1). j
Эти векторы называются ортами. Система векторов
является линейно независимой, так как kjl -]- кг\г -f-
...-(- kmim = 0, только если /г,- = 0 для всех /=1,2,
Всякий вектор Р(я,, л2, . .., «„,) пространства Ptm)
выражается через векторы
A), а именно
0)
A)
. . ., т.
линейно
системы
Рис. 1.
Можно показать, что всякая система
векторов пространства Р(т), со-
состоящая более чем из т векторов,
линейно зависима.
Так, если в плоскости из начала
координат выходят два вектора Р,
и Рг, не направленные по одной
прямой, т. с. линейно независимые
векторы, то любой третий вектор Ро
можно представить как линейную комбинацию этих векторов.
Аналогично, если в трехмерном пространстве заданы три
вектора, не лежащие в одной плоскости и выходящие из
начала координат, то любой вектор этого пространства выра-
выражается как линейная комбинация этих векторов. Так, на
рис. 1 изображен случай, когда вектор Ро представляется
комбинацией линейно независимых векторов Pv P2, Р8, которая
имеет вид
Р = Р 4- -- Р -I- — Р
г о ri Г ') г 1 4 8
12
В двухмерном пространстве двум линейно независимым
векторам Р, (ап, а21) и Р2 (а12, а2г) соответствует определитель
отличный от нуля.
Абсолютное значение этого определителя равно площади па-
параллелограмма, построенного на векторах Pt и Р2 (рис. 2).
В трехмерном пространстве три линейно независимых вектора
р, К,. a2,. «,,)• РЛ«,2. "». а,г) и p8(«,s. «2S- «33)
образуют параллелепипед (рис. 3). В этом случае абсолютное
значение определителя
отлично от нуля и равно объему параллелепипеда.
По аналогии, если в /я-мерпом пространстве заданы т
линейно независимых векторов
?1 / \ ' 1 О
/= I, 2, ..., т,
то, как показано в курсах высшей алгебры, определитель
ви ам ¦•• аи
а„ .
а„п атг ¦•¦ ап
отличен от нуля.
13
Пусть в /и-мерном просфлпстве зядано п произвольных
векторов
p/(«i/. агр •••> ац «тА у^1. 2. ••-. л;
/ = 1, 2, . . ., от.
Образуем из компонент этих векторов матрицу *) порядка
B)
Столбцы этой матрицы, рассматриваемые как /я-мерные век-
векторы, могу г, вообще говоря, быть линейно зависимыми.
Максимальное число линейно независимых столбцов матрицы B)
называется рангом этой матрицы **). Иначе говоря, ранг
матрицы B) равен максимальному числу линейно независимых
векторов Pj, компоненты которых составляют ее столбцы.
Всякая максимальная линейно независимая система векторов
npocipaiicriui P'm) называется базисом этого прос транс л па.
Пусть векторы Р„ Р2 Р^,, Р;, Р/+1, ..., Рт
образуют базис просфансгва Р""', koiopuii назовем Л-бази-
сом. Тогда любой пек гор Р эгош пространства может быть
представлен, н притом однозначно, в данном базисе в виде
линейной комбинации векторов Ру, j----\, 2, ..., т. Все ба-
базисы векторного пространства состоят из одного и того же
числа векторов.
Возьмем произвольный вектор Q, не принадлежащий базису
Р,, Р2, ..., Рт. Тогда, ес.м» вектор Q не равен нулю, то
в линейной комбинации
4-а- Р- 4- -1-7 Р
I - + 1*7 + 1 I • • • I J-mrm
имеется по крайней мере один коэффициент, отличный от нуля.
*) Здесь и в дальнейшем компоненты некторон Ру будем распо-
располагать в виде колонок матриц.
**) Всегда максимальное число линейно независимых строк мат-
матрицы рашю максимальному числу линейно независимых сюлбцов.
14
Пусть, например,
представит!) в виде:
тогда вектор Р; Л-базиса можно
1
Q
а; /+»
Исключим из Л-базиса вектор Р и присоединим к оставшимся
векторам вектор Q. Система векторов Р,, Р2, ..., Р;-_,, Q,
РуМ, ..., Рт снова является базисом. В самом деле, в силу
однозначного разложения любого вектора по векторам базиса,
после исключения вектора Ру из Л-базиса, вектор Q уже не
может быть представлен в виде линейной комбинации остав-
оставшихся векторов. Это означает, что система векторов
Р,, Р2, ..., Р;-_, Q, Ру + 1, ••¦, Р,я является линейно неза-
независимой системой, т. е. образует базис.
/i-базис, полученный из Л-базиса заменой некоторого век-
вектора на вектор, не принадлежащий Л-базнсу, назовем базисом
однократного замещения по отношению к А-базису.
Пусть в /я-мерпом пространстве задано п -(-1 векторов
Р„, Р,, Р2 Р/,
имеют разложения:
Р/, • • ., Р„, которые в базисе Q,, Q2, . . ., Qm
C)
Образуем матрицу из компонент разложений C)
Р, Р, •• Р/ ¦•• Р„
... я
„ ...
D)
/?« апа ¦ ¦ • <>,,„ • ¦ • атп \
15
Допустим теперь, что векторы q,, q2, ..., qm образуют
новый базис в Р(т). Пусть эти векторы имеют следующие
разложения в базисе Q,, Q2, ..., Qm:
Так как qp q2, ..., qm образуют базис, то определитель
д., а.„ ... (/,„,
' 1 1 ' 12 1 1Ш
<72, д22 ... дгт
/mi Чтг
imm
E)
отличен от нули.
Перейдем от базиса Q,, Q2, . . ., Qm к базису q,, q2, . . ., qm.
Тогда векторы Ро, Р,, Р2, ..., Р,( будут иметь в базисе
qt, q2, . . ., qm коэффициенты разложения, вообще говоря,
отличные от коэффициентов разложения в базисе Q,, Q2,. . . ,Qm:
Матрица разложений в этом случае имеет вид
Ро
р, •
«;, •
а
.. Р, .
. ¦ «!/ •
.. Р
.. «;
F)
• • • ат
Как известно, элементы матрицы F) определяются через эле-
элементы матрицы D) и определитель E) но следующим форму-
формулам:
где
Чи •
'h, ¦
1т, ¦
7м •
'hi ¦
Imi ¦
•" ?'•'-'
•• ?,,,--,
¦ • '/2, ,--i
Ь.2
К
ач
a,nl
1v
'h,
1m,
1,
<h
I2
1Ч1
1-1 1
/ +1
, ,'4-1
. /hi
•¦• «7/m
••• 1гт
' ' ' 1mm
;
¦ ¦ • lim
¦ ¦ ¦ 1,m
• ' • 1 mm
(/=1, 2, ..., да; /=1, 2, ..., и).
В дальнейшем мы наряду с обозначениями этих определителей
через Д, Д°, Af будем пользоваться иногда обозначениями
вида:
Рассмотрим пример определения разложений данной системы
векторов при переходе к новому базису.
Пусть и базисе Р,, Р2, Р, векторы Ро, Р„ Р2, Р,, Р4, Р5, Р,
имеют разложения, определяемые матрицей
Р Р Р Р Р Р Р
5 1 0 0—34—1
3 0 10—1 1 —2
2 0 0 1 2 1 1
Так как определитель, составленный из компонент векторов
Р*. р5- Рв
— 3 4 — 1
Д = (Р4, Р5, Р.):
— 1 1 —2
= —18,
2 1 1
отличен от пуля, то векторы Р4, Р,, Рв образуют базис.
17
Найдем разложения векторов Ро, Р,, Р2, Рз, Р4, Р5, Рв
в базисе Р4, Р5, Р„. Пользуясь формулами G), получим
р р р р р р *
*0 *1 *2 Г1 ^1 *5
(P0P5Pe), (P,P5P6), (P2P5P6), (PSP5P6), (P4P5PS), (P5P5Pe).
(Р4Р0Р6), (Р4Р,Р6), (Р4Р2Рв), (Р4Р,Р6), (Р4Р4Р6), (Р4Р5Р6),
(Р4Р5Р0), (P^sP,), (P4PSP2), (Р4Р5Р3), (Р4Р5Р4), (Р4Р5Р5),
Производя соответствующие выкладки, Пудем иметь матрицу,
представляющую разложение данных векторов в базисе Р4, Р5, Р9:
Р Р Р Р Р Р Р
f8 10
8
1)
11
т
2Я
?
1
?
1
?
1
?
о
Г8
1
18
11
78
/
Тй
5
~Т8
1
~Т8
Как известно скалярным произведением двух векторов
Р и Q называется выражение, определяемое формулой
(Р ¦ Q) = albl + а А + . . . + яД. + . . . + ajm,
где ah bt — компоненты векторов Р и Q. Векторы Р и Q
называются ортогональными, если их скалярное произведе-
произведение равно нулю. Так как матрицу порядка т X п можно рас-
рассматривать как (т X «)-мерпый вектор, то скалярным про-
произведением матриц
«.I
0. ...
а ...
я „. . .
... а
... а
...tf,
И fi^=
18
будем называть алгебраическую сумму всех элементов матрицы
«.А, Й.А2 «.Л»
"nn hnnamAn
и обозначать (.-V •
§ 2. Гиперплоскость и полупространство
И:) апалншческой геометрии известно, что линейному
уравнению
'\Xl-\-AiXt-\-Atxt = C (8)
в трехмерном пространстве coomeiciuyer
нам к вектору А (.<!,, ,-12, Лг).
Приведем уравнение (8)
к виду
плоскость, нормаль-
нормальУравнение плоскости
= 1. (9)
Плоскость, соответс твующая
этому уравнению, отсекает
на осях координат отрезки
а,, я2, я, (рис. 4).
Кроме того, ураиненпо
плоскости в трехмерном про-
пространстве может быть пред- риС 4.
ставлено в векторной форме
(А°-Х)=~//, где А° — вектор единичной длины, нормальный к
плоскости; X--текущий вектор, соединяющий начало коорди-
координат с точкой, принадлежащей плоскости; здесь (А°-Х)—скаляр-
(А°-Х)—скалярное произведение векторов А° и X, равное по величине проек-
проекции h вектора X на направление, определяемое вектором А°.
Величина h равна расстоянию от начала координат до плос-
плоскости. При h = 0 плоскость проходит через начало координат.
Любой вектор X, соединяющий начало координат с точ-
точкой плоскости, имеет одну и ту же проекцию h на направ-
направление А0 (рис. 5).
19
По аналогии будем называть гиперплоскостью или просто
Плоскостью в /77-мерном пространстве множество всех точек
(л:,, х2, ..., хт), удовлетворяющих уравнению
Условимся говорить, что эта гиперплоскость нормальна к
вектору А (.4,, А2
,А
). Будем говорить
уравнению
также, что
'---= 1
(9'
соответствует гиперплоскость, отсе-
отсекающая на осях координат отрезки
д.'
а., а.
чало хоордина/п
Рис. 5.
концы
Наконец, векторное уравнение
(А°-Х) = А в пространстве Р(т)
определяет гиперплоскость, нор-
нормальную к единичному вектору А0
и отстоящую от начала координат
па расстоянии п.
Прямая на плоскости делит последнюю на две части, каж-
каждая из которых называется полуплоскостью. Из рис. 6 видно,
что прямая делит плоскость на две полуплоскости. Кроме того,
проекции Ос1 векторов X,, концы которых лежат в одной
полуплоскости, меньше Л=Ос,
которых принадлежат другой
полуплоскости, больше А.
Плоскость в трехмерном про-
пространстве также делит все про-
пространство на две части, каждая
из которых называется полу-
полупространством.
Аналогично будем говорить,
что гиперплоскость в «-мерном
пространстве делит это про-
пространство на две части, каж-
каждая из которых называется
полупространством.
Пусть гиперплоскость в • пространстве Р(""
уравнением (А°-Х) = Л. Тогда для точек М одного из полу-
полупространств проекций изображающих их векторов X па на-
направление А° меньше А, а для точек другого полупростран-
полупространства— больше Л. Таким образом, одно из полупространств
Рис.
выражается
20
>h).
< 5.
есть множество векторов X, для которых выполняется нера-
неравенство (А"-Х)<^/г, а для векторов другого полупростран-
полупространства— (А0-Х)^> h. Сама гиперплоскость (А°-Х) = /г может
быть присоединена к одному из полупространств. Тогда все
множество точек /«-мерного пространства будет разделено на
два вида: точки, для которых (А°-Х)^/г, и точки, для кото-
которых (А°-Х)>/г (или в другом случае (А°-Х)</г и (А°-Х);
Пример 1. Дано полупространство — 5xt -J- 4х2—Зх,
Определить, принадлежит ли ему точка @, 0, 0).
Для ответа достаточно подставить значения xl = 0; х2 = 0;
X, = 0 в неравенство. Будем иметь —5-0-f-4-0 — 3-0 < 5,
откуда следует, что точка
@, 0, 0) действительно при-
принадлежит полупросграпству
Плоскость — 5х1 -|-
-J- 4х2 — Зл", = 5 перпенди-
перпендикулярна вектору А ( — 5,
4,-3) (рис. 7).
П р и м е р 2. Определить,
принадлежит ли точка девяги-
мерпого пространства xt = 0;
А1-5А-3)
Уравнение плоскости
Рис. 7.
xs=0; xo = O, лг,.---!); х8=1; х9 = 0 полупространству
4лг, -\- Ъхг — 7хг -\- х5 — 2х6 -\- 1 2л-, — Зхв s? 11. Подставив
координаты этой точки в неравенство, получим 4 • 0 —|— 4 ¦ 5 —
— 3-7 —7-0 + 0-1—2-0 —9-12—1-0 —3-0=109 >11.
Следовательно, эта точка не принадлежит заданному полупро-
полупространству.
§ 3. Выпуклые многогранники
Выпуклым телом называется такое тело, которое
вместе с любыми двумя своими точками содержит и весь
соединяющий их отрезок.
Примерами выпуклых тел могут служить круг, шар, куб,
угол, образованный двумя лучами, выходящими из одной
точки (рис. 8).
Пусть точки х и у являются общими для выпуклых тел
А и В (рис. 9). Тогда х \\ у принадлежат телу А, а поэтому
отрезок, соединяющий точки х и у, также принадлежит А.
Аналогично этот же отрезок принадлежит и телу В. Следо-
Следовательно, он принадлежи!' и общей части тел А к В. Эго
означает, что оощая часть или пересечение выпуклых тел
есть выпуклое тело.
Возьмем на плоскости многоугольник, лежащий по одну
сторону от каждой прямой, учаавующей в образовании этого
многоугольника. Как видно из рис. 10,«, эгот многоугольник
является выпуклым. Действительно, любые две точки х и у
l>ik\ S.
такого многоугольника принадлежат ему н.месге с соединяю-
соединяющим их отрезком. Напротив, многоугольник, представленный
на рис. 10,6, не лежит по одну сторону or каждой прямой,
участвующей в образовании этого многоугольника. Такой мно-
многоугольник не является выпуклым.
Возьмем произвольную точку М, не принадлежащую вы-
выпуклому многоугольнику (рис. 11,«). Всегда можно указать
такую прямую PQ, чго точка М и многоугольник лежат по
разные стороны от PQ. Для выпуклого многоугольника можно
построит!) множество таких пря-
прямых, что каждая из них имеет
по крайней мере одну общую
точку с многоугольником, и
1аких, что весь многоугольник
находится по одну сторону от
каждой из них. Такие прямые
называются опорными.
Так. па рис. 11,6 прямые
/ID, СИ, ПН и FN являются
опорными. Опорная прямая может иметь с выпуклым много-
многоугольником общую часть, состоящую или из одной точки,
или отрезка.
В трехмерном пространстве тело, ограниченное плоскостями
и лежащее по одну сторону от каждой плоскости, содержа-
содержащей его грань, является выпуклым и называется выпуклым
многогранником. Примерами таких тел могут служить мно-
многогранный алмаз, призма и т. д. Опорной плоскостью вы-
выпуклого многогранника называется плоское 1Ь, которая имеет
22
с многогранником по крайней мере одну общую точку, и
такая, что многогранник лежит по одну сторону от этой пло-
плоскости. Опорная плоскость может иметь с многогранником
общую часть, состоящую из одной точки, называемой верши-
пой многогранника, н.ч отрезка, называемого ребром, или,
Рис. 10.
наконец, из многоугольника, называемого гранью. Ясно, что
через каждую вершину и ребро многогранника можно про-
провести бесконечное множество опорных плоскостей, в то время
как через любую грань проходит только одна опорная пло-
плоское 1Ь.
о М
F С
Ранее мы убедились, чго общая часть нескольких выпук-
выпуклых тел является выпуклым телом. Поэтому общая часть
нескольких многогранников есть выпуклое тело. Поскольку
плоскость ее п. выпуклое тело, то пересечение многогранника
с плоскостью есть выпуклое тело и представляет либо точку,
либо отрезок, либо выпуклый .многоугольник. Аналогично свой-
свойствам выпуклых гол трехмерного пространства можно рассмат-
рассматривать скоПсша выпуклых мел» многомерных пространств.
Некоюрые из этих CBoiiciB будут рассмотрены в § 4 и 5.
23
§ 4. Система линейных неравенств
Пусть в двухмерном пространстве заданы п неравенств
вида
ailxl-Jraizx2^b! (/=l, 2, ...,«)*)¦ A0)
Каждое такое неравенство определяет одну из двух полупло-
полуплоскостей с граничной прямой лпл', -}- «,-2x2 = А,-. Граничная
прямая GA лг^ —(— л,2л:2 = Ь{ нормальна к вектору А,- (я,-,, я,-2).
4B,3}
2х;+Зхг>В
Уравненир прямой
2
х.
Рис. 12 {а, б).
Всякая пара чисел (х,, хг), удовлетворяющая всем нера-
неравенствам системы A0), называется решением данной системы
неравенств. Иными словами, всякая точка плоскости (х,х2),
координаты которой удовлетворяют системе A0), является ре-
решением.
Рассмотрим несколько примеров:
1. Неравенство
.?¦_ _|_ Ц. <=5 1 или 2л-, -f Ъхг < б
определяет полуплоскость (рис. 12,я). Этому неравенству
удовлетворяет любая точка, лежащая в заштрихованной
части плоскости. Граничная прямая выражается уравнением
2х, -\- Ъхг = б и нормальна к вектору А B, 3).
2. Два неравенства
определяют часть плоскости, как изображено на рис. 12,6'.
*) Всякое неравенство вида я;1х, -f- rt/2x2 ;з ft,- после умножения
обеих частей его на —I приводится к виду A0).
3. Трем неравенствам
2.v,
З.г, < 6,
— х, — Зх2 sS 3
удовлетворяет множество точек плоскости, образующих тре-
треугольник решении ЛИВ (рис. 12,а).
х,
4. Четырем неравенствам
2а-, + Зх2 < 6,
xi Зх2
х.
3,
3
A)
B)
C)
D)
Соответствует множество точек плоскости, образующее мно-
многоугольник решений ABCD (рис. 12,г).
5. Семи неравенствам
2а-, -j-3x2<6, A)
ХА- *2<2, B)
— х, —3x2s=3, C)
2х, ^ 3, D)
— Зл-,+7*,<21, F)
х,-3х2<3 G)
25
соответствует то же множество точек, чго и в примере 4.
Неравенства E), F) и G) могу г быть исключены без изме-
изменения множества решений. При эгом неравенства E) и F)
определяют граничные прямые, не имеющие с мшн-оуголыш-
E)
BJ
е)
Рис. \2 (д, ,').
ком ABCD общих точек. Прямая G) имеет одну общую точку
с многоугольником и является опорной (рис. 12/)).
6. Система неравенств
S б,
A)
B)
C)
D)
E')
не имеет ни одного решения. Геометрически это означает,
что не существует пи одной точки, координаты которой удов-
удовлетворяют всем неравенствам (рис. 12,с).
Рассмотрение этих примеров приводит к следующим вы-
выводам:
1. Система неравенств с двумя переменными может быть
совместна. Тогда существует по крайней мере одна точка
плоскости, принадлежащая всем полуплоскостям, определяемым
данной системой неравенств. Множество всех таких точек мо-
может быть полуплоскостью, ограниченным и неограниченным
многоугольником, прямой или ее отрезком и, наконец, одной
точкой. Совокупность точек, удовлетворяющих системе нера-
неравенств, есть выпуклое тело.
26
2. Система неравенств может оказаться несовместной.
В этом случае не существует ни одной точки плоскости,
удовлетворяющей одновременно всем неравенствам системы.
Пез ограничении общности систему п неравенств в трех-
трехмерном пространстве можно записать в виде
Как мы уже знаем, каждое из неравенств A1) определяет
полупространство с граничной плоскостью
Совокупность неравенств A1) может оказаться совместной.
В этом случае существует некоторое множество точек трех-
трехмерного пространства, удовлетворяющих системе неравенств.
Это множество есть выпуклое множество и может представ-
представляться в виде полупространства, многогранника, плоскости,
мношуголышка, прямой, отрезка или, наконец, одной точки.
В случае совместности среди неравенств системы могут
быть и <липшие) неравенства, удаление которых не изменяет
множества решений данной системы неравенств. Эти. «лишние»
неравенства могут быть двух видов: 1 вид — неравенства,
граничные плоскости коюрнх не имеют пересечения с множе-
множеством всех решений системы; 2 вид — неравенства, граничные
плоскости которых являются опорными для множества решений.
Может оказаться, что в пространстве трех измерений нет
ни одной точки, одновременно удовлетворяющей всем нера-
неравенствам. В этом случае система неравенств называется несов-
несовместной.
Пусть в. m-мерном пространстве задана система неравенств
а,-,*, + я,-,*2 + • • • + aimxm < *,. (/ = 1, 2, . . ., я). A2)
По аналогии с трехмерным пространством будем говорить,
что каждое из неравенств A2) определяет в /я-мерпом про-
пространстве полупространство с граничной плоскостью
Если в /«-мерном пространстве существует по крайней мере
одна точка /И (.г,, х2, ..., хт), удовлетворяющая одновре-
одновременно всем неравенствам, то система A2) называется совмест-
совместной. Множество всех таких точек будем называть «много-
«многогранником решений >.
Пусть в /и-мерном пространстве заданы две точки
М.' (х'и К' ¦¦¦> хт) и М" (х"и К> •••> х"т)' Множество точек
27
М (х1, хг, ...,хт), координаты которых удовлетворяют усло-
условиям:
Хт ХтЛ 1 (хт Хт)
при изменении параметра i от 0 до 1, называют отрезком,
соединяющим точки М' и Л1". Являясь пересечением полупро-
полупространств, «многогранник решений/) есть выпуклое множество.
Это означает, что вместе с точками М' и М" ему принадлежат
и все точки соединяющего их отрезка.
Неравенства, которые можно удалить n:i системы A2), не
изменяя множества ее решений, называются зависимыми или
«лишними». Уда.чяя из заданной системы последовательно одно
за другим неравенства такого вида, получим подсистему не-
неравенств, множество решений которой совпадает с множеством
решений первоначальной системы.
Удаление «лишних» неравенств является очень сложным
и трудоемким процессом. Одна из особенностей методов ли-
линейного программирования состоит в том, что для определения
наименьшего (наибольшего) значения линейной функции на
многограннике не требуется специального процесса выделения
«лишних» неравенств. Если системе неравенств A2) не удов-
удовлетворяет ии одна точка /w-мерпого пространства, то такая
система называется несовместной.
§ 5. Наименьшее и наибольшее значения линейной формы
на многограннике
Рассмотрим совместную систему линейных неравенств с двумя
переменными. Предположим, что мы исключили все «лишние»
неравенства 1-го и 2-го видов и тем самым выделили много-
многоугольник решений в «чистом виде» (рис. 13). Пусть, кроме
того, задана линейная функция двух переменных
Найдем среди множества точек (xv лг2) многоугольника реше-
решений такие, которые придают линейной функции /=:clxl-\-ctxt
наименьшее и наибольшее значения. Рассмотрим множество
всех точек {хх, хг) плоскости, в каждой из которых функция
f=clx1-\-ctx2 принимает фиксированное значение / = /t.
Множество таких точек есть прямая clxl-\-clxi=--fl. Эта
28
прямая, как отмечалось в предыдущем параграфе, нормальна
к вектору C(ct;ct), выходящему из начала координат. Про-
Проведем прямую F (рис. 13), нормальную к вектору С, и будем
ее передвигать параллельно самой себе в положительном на-
направлении вектора С. Пусть при движении прямой F она впер-
впервые встретится с многоугольником в вершине А. В этом
положении F' прямая F становится опорной. При дальнейшем
движении в том же направле-
направлении прямая F пройдет через
Рис. 13.
Рис. 14.
вершину В и станет также опорной примой. Так как направ-
направление вектора С (с,; сг) есть направление наибольшего возра-
возрастания линейной функции /= с,лг, + с2х„ то на опорной
прямой F' функция/ принимает наименьшее значение, а на опор-
опорной прямой F"—наибольшее значение среди значений /, при-
принимаемых на многоугольнике решений.
Таким образом, наименьшее и наибольшее значения линейной
функции /=с,х,-|-сл на многоугольнике решений дости-
достигаются в точках пересечения этого многоугольника с опорными
прямыми, нормальными к вектору С (с,; сг). Пересечение опорной
прямой с многоугольником решений может состоять либо из
одной точки *) (вершины многоугольника), либо из бесчисленного
множества точек (в этом случае это множество есть сторона
многоугольника).
На рис. 14 изображен случай, когда линейная функция/
достигает наименьшего значения в каждой точке отрезка AtAz,
*) Эта точка может оказаться в бесконечности.
в то время как наибольшее значение достигается в бесконечно
удаленных точках многоугольника.
Аналогично линейная функция грех переменных /=с1х1-\~
~Н сгхг Лт ciX> принимает постоянное значение на плоскости,
Рис. 15
нормальной к вектору С (с,; cs; cs). Направление С есть направле-
направление максимального возрастания функции / (рис. 15). Наибольшее
и наименьшее значения этой функции на многограннике решений
также достигаются в точках
пересечения этого многогран-
многогранника с опорными плоскостями,
нормальными к вектору С (с,,
с2, с,); при этом на одной из
опорных плоскостей / дости-
достигает наименьшего, а па дру-
i ой— наибольшего значе-
значения. Пересечение многогран-
многогранника с опорной плоскостью
может представляться либо
одной точкой (вершина мно-
многогранника), либо бесчислен-
бесчисленным множеством точек (в
этом случае это множество
Рис. 16. а а г
есть либо ребро, либо грань
многогранника).
Например, на рис. 16 изображен случай, когда /достигает
наименьшего значения в каждой точке грани ABQP, а наи-
наибольшего— в точке О,
Обобщением понятия линейных функций от двух и трех пе-
переменных явлнею! функции вида /'= <',л*, -}- с\х,-\-. . ,-]~спх1г
or л вещественных переменных .г,, х2.. . ., хп, начинаемая линей-
линейной формой; здесь с,, с
Фиксируя значения
. . .; / =~
гиперплоскости
¦
,, с.,, ... , с„ — вещественные числа,
линейной формы /--/,; / = /2; •••
мы тем самым определяем в «-мерном пространстве
"I"
-с,х, - - <\х.
нормальные к «-мерному вектору С (с,, с2, сг). Обозначим через
/„„¦„ наименьшее значение формы
/= c,-v, -|- с2х2 -)-...-(- спхп
на многограннике peiiiennii, а через /1Пах — наибольшее зна-
значение. Так как пек гор С определяет направление наибольшего
Возрастания ЛПнепПОЙ формы/, ТО При /'<C/min и ИР"/'^/тах
соответствующие гиперплоскости /' = с1х1 -\~сгх2 -\- . . . -\-спхп
не имеют пересечений с многогранником решений. С другой
стороны, каждая гиперплоскость/" = с,лг1 -\-с2хг -(- . . . -\-спхп,
для которой /Ш1П ss:/" ^-/щах, имеет общие точки с много-
многогранником решений. Множество точек /И(х,, хг, ... ,хп),
» которых линейная форма / достигает наименьшего значения,
есть пересечение многогранника решений с опорной гипер-
гиперплоскостью с1х1 -\-с2хг -}-¦¦¦ -[- с„л:п =yiilin, нормальной к век-
вектору С (с,, с2, . . . , сп). Аналогично, наибольшего значения /
достигает в точках пересечения многогранника с опорной
гиперплоскостью с^х, -j- сгхг -(-... ~\тспхп=/тм, также нор-
нормальной к вектору С.
Пересечение многогранника решений с опорной гиперпло-
гиперплоскостью есть вершина, ребро или «грань» многогранника.
Таким образом, оптимальное значение линейной формы
на многограннике решений достигается в точках, среди которых
всегда имеется по крайней мере одна из вершин. Поэтому
для определения оптимального решения достаточно выбрать
ту вершину многогранника, в которой линейная форма дости-
достигает наименьшего (наибольшего) значения.
31
§ 6. Сведение неравенств к равенствам
При решении задач линейного программирования
Пусть задана система т линейных неравенств с п пере-
переменными:
A2)
определяющая в л-мерпом пространстве многогранник решений.
Рассмотрим наряду с этой системой неравенств систему т
линейных алгебраических уравнений с п-\~т переменными:
A2'
Покажем, что всякому решению х\, х'\, . . . , дг° системы не-
неравенств A2) соответствует определенное решение х\, х\,..., х"п;
Iр \l\, . . . , jjl^, системы линейных алгебраических уравнений
A2'), причем дополнительные переменные удовлетворяют
условию ji'SsO, jjl° 5= 0, . . . , Ц^Э3 О- В самом деле, если
х°, х", ... , х", есть решение системы A2), то имеют место
неравенства:
32
К-
Обозначим через:
A2"
К = Ьт — К,
Тогда, во-первых, }л"
система чисел х"., х",
5-^ 0, jj>° 5= 0, . . . , ц°; Гз 0; во-вторых,
. . . , л:^; jjl'>, ]in,,_. . . , \s."m, как следует
из A2"), есть решение системы линейных алгебраических уравне-
уравнений A2').
Докажем, наоборот, что всякому решению х\, х'!, . . . , х°;
ц°, ц°, . . . , ц"„ системы уравнений A2'), удовлетворяющему
условию [л" 5= 0
ленное решение
[л" ?и0, ... , ;i^ 2s 0, соответствует опреде-
опредесистемы неравенств A2). В самом деле. По-
Поскольку система чисел х", х'1,
jjlJ,
решение системы A2'), то можно записать:
\s."m
есть
Так как по предположепшо числа jxj, [л°,
тельны, то имеют место неравенства:
= h,
нсотрица-
т. е. система чисел х°, л"° х"н есть решение системы
неравенств A2).
Таким образом, установлено взаимнооднозначное соответст-
соответствие между множеством всех решений х\, х", ... , x"t системы A2)
\ " ] ° "
и множеством решений х\, х],
х"п; ]s.], jjl°,
, ]i"m системы
A2'), причем дополнительные переменные jxj, jjl", . .. , \i."m не-
неотрицательны. Таким образом, задача решения системы линейных
неравенств вида A2) сводится к решению соответствующей
системы линейных уравнений вида A2').
В задачах линейного программирования нас будут интере-
интересовать решения системы неравенств, удовлетворяющие условию
2 А. С. Барсов
33
л\^г-О, хг ';з- О, ... , х„>0. Такие решения называются нр-
отрицительными. Полному, так как решение системы нера-
неравенств сводится к решению соотвекгвующей системы линейных
алгебраических уравнений, то оишм n:i важных вопросов
линейного программирования является определение неотрица-
неотрицательных решений системы линейных уравнений.
Пример. Требуемся определить неотрицательное решение
системы неравенств:
-L3.Y.
'6.
- *, - :iv8 ^ -л.
Вводи дополни те.тьпые переменные [j
получим систему уравнений:
р.2 ~ - 0, Ji, ^ О,
-xt--Axs + ц,=-3.
Всякому неотрицательному решению этой системы уравнений
соответствует определенное неотрицательное решение исходной
системы неравенств, н наоборот. Так, например, неотрицатель-
неотрицательному решению хх -= I; х2 = 1; ji, — 1; ;л2 = 2; р., = 7 системы
уравнений соответствует неотрицательное решение х1=\;
jc2=l исходной системы неравенств.
Заметим, что если система неравенств несовместна в области
¦неотрицательных решений, ю соответствующая система линей-
линейных уравнений не имеет ни одного неотрицательного решения.
Известно, что наименьшее (наибольшее) значение линейной
¦ формы на многограннике, определяемом системой неравенств,
достигается в определенной вершине многогранника решений.
.Можно показать, что каждой вершине многогранника решений
¦отвечает неотрицательное решение соответствующей системы
линейных алгебраических уравнений, причем по крайней мере
одна дополнительная переменная равна нулю. Дополнительные
переменные р.1^0, |л2 ^ 0, . . . , \хт 5з 0, вводимые в систему
неравенств, можно иллюстрировать геометрически.
Рассмотрим многогранник решений системы неравенств:
а,.х, 4-й. „*"„ 4- . • . 4-п. „А'., ее/?,.
аш А < Ьт.
34
Пусть имеется одно из нетрицатсльпых решений х°, л:', ..., х"п
системы неранепстн. Ему соответствует точка М(х\, х°,. . . , лг°),
принадлежащая многограннику решений.
Пусть /г,- обозначает расстояние от точки М до /-й гипер-
гиперплоскости. Значения дополнительных переменных:
пропорциональны расе юямням от точки М (х", х", .
гранпчн1IХ гиперплоскостей:
"Г
. . , х"п) до
Дейстнпгел1)Но, по определению расстояние от точки М до г-й
гиперплоскости раино
b,- — (ahx'[ + (ii2xl -f- . . . + <г,-„л',';)
откуда и следует, чт:
(/= 1, 2, 3,...,т),
ГЛАВА П
РЕШЕНИЕ ОБЩЕЙ ЗАДАЧИ
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Линейное программирование — это раздел математики,
в котором рассматриваются методы решении следующей за-
да,чи: задана система т линейных алгебраических уравнений
с п переменными:
1 "miXi I
, = ь„
A3)
и линейная форма / тех же переменных
f - v i r „ i _j_ r .- I
J t.,A, -f- (,2Л2 -p . . . -|- С Лу-р
A4)
Требуется среди решений системы A3) найти такое неотри-
неотрицательное решение, при котором линейная форма / принимает
минимальное значение *). Такое решение будем называть
оптимальным решением данной задачи.
В этой главе рассматривается метод определения одного
из неотрицательных решений системы A3), а также один из
алгоритмов решения общей задачи линейного программиро-
программирования.
*) Аналогично формулируется заллча для нахождения неотрица-
неотрицательного решения, при котором / принимает максимальное зна-
значение.
§ 7. Тождественные преобразования системы
линейных алгебраических уравнений
Пусп, задана система A3), содержащая г линейно неза-
независимых уравнений и разрешенная относиге.тыю г переменных.
Без ограничения общности можно считать, что система раз-
разрешена относигедыю мерных г неременных из первых г урав-
уравнений:
L г ' -
2Г (- \ Г - 1 "| 2ГЧ 2 Г f2 I * * *
xi
A5)
Система уравнений A5) в сокращенной записи имеет вид
i = 1, 2, .. ., г.
/r^r-l ,
A5')
Предположим, что свободные члени />,¦ и уравнениях A5) не-
неотрицательны.
Каждое из уравнении системы A5) можно рассматривать
как проекцию векторного уравнения
У у р . р
A6)
па векторы Р,, Р5, ..., Рг, где Р,^Р,A, 0, ... 0);
Р2=^Р2@, 1, ... 0); ...; Рг=Рг@, 0, ... 1). Векторы
Р,, Р2, ..., Рг образуют базис в /--мерном пространстве. При
этом матрица разложении векторов Ро, Рг Р2, . . ., Рг, . .., Ри
в базисе Рр Ps, ..., Рг представляется в виде
Р Р Р Р Р Р Р Р
1 .
hi air,i ¦ "U ¦ "in
A7)
• "г/ •
м • "г/
3?
Допустим, что совокупность векторов Р;, Р, Рг, Рг+1, ..., Р„,
входящих в уравнение A6), образует несколько базисов г-го
порядка, отличающихся один от другого хотя бы одним
вектором. Будем называть каждый из этих базисов собствен-
собственным базисом.
Пусть А , Аг, . . ., А,„ . . . —собственные базисы системы
векторов Р,, Р2, ..., Р,! ..., Рг; РЛ+1 Ру, ..., Р„. При
переходе от базиза к базису все коэффициенты уравнений A5)
будут преобразовываться по формулам G) предыдущей главы.
Система A5) при этом будет переходить в эквивалентные ей
системы, т. е. в системы с теми же решениями.
Базис А будем пазыиап. положительным по отношению
к непулевому вектору Ро, если Ро представляйся в этом базисе
г
в виде Ро — -^] },-Р{, р(-~-0. Как видно из уравнений A5),
/'—.I
базис Л, содержащий векторы Рг Р , Рл, соответствую-
соответствующие разрешенным переменным, являемся положительным, так
как по предположению Ь: Т: О- Переменные (ххх„. . .хг), относи-
относительно которых система A5) разрешена, называются основ-
основными, а остальные — неосновными. Решение системы, полу-
получаемое приравниванием неосновных переменных пулю, назы-
называется основным.
В силу теоремы об однозначном разложении вектора
в каждом базисе основное решение определяется однозначно
на любом собственном базисе.
В дальнейшем мы будем рассматривать системы линейных
алгебраических уравнений только в собственных положитель-
положительных базисах. Поэтому дли сокращения письма слова «собст-
«собственный» и «положительным**) опустим.
Рассмотрим систему A5). Определим правила перехода от
одного базиса к другому. Для этого воспользуемся ма-
матрицей A7).
I. Находим один из столбцов у (/"~]-1 ~ij-^n), у кото-
которого среди коэффициентов а1]-, « ¦, . . ., air . . ., arj (I --^ i ^ r)
при неразрешенной переменной х, имеются положительные
коэффициент*) (случай, когда такого столбца не существует,
рассматриваемся в § 8).
Пусть это будет столбец уг
II. Определяем min |—'-} по всем /, для которых я(-У) по-
положительны. /у'
*) Учитываются знаки кол^фшшопгои, находящихся и скобках, при
записи урдвиеип!) и виде системы A5j.
Пусть одно из min отношений будет при /- -il. Э.темеи г ai ,
назовем ризреишющим по о i ношению к системе A5).
111. Разрешим /,-е уравнение относительно переменной X]
и подставим ее выражение в остальные уравнении системы A5).
При этом система A5) перейдет в эквивалентную ей си-
систему A8):
t'h ( Л7, , V «''
X
Ь:
х.---[Ь.
V
1, /,-1-1, ..
'/i (; ¦ ¦
г—1),
A8)
(у--- г-\~], . . ., п),
а группа векторов Рр Рп, . . ., Р,-._,, РУ[, Р,г).,, . . ., Рг станет
новым базисом Л.,. И самом деде. Из A8) следует, что эти
векторы образуют базис, так как соответствующий им опре-
определитель отличен от нули
р, p,---»v,
р р р
/г 1, I 1 " ' Г
V,
1
Этот базис положительный, потому что новые свободные
члены неотрицательны. Действительно, свободные члены
имеют вид
I Ь; Ь;.
и I II/, и;
г ' 1 i • ' \
Если aiji ^> 0, то по правилу 11 — 53 — и свободный член
39
если же
ач,
; 0, то свободный член опять
неотрицателен;
неотрицаюлен.
Преобразование системы (|Г>) и систему A8), определяемое
правилами 1, 11, 111, называемся толсдественны.и или симплекс-
преобразованием.
Из определения тождественных преобразований следует,
что система линейных ал1 ебранческих уравнений типа A5)
может быть подвергнута этим мреобра^онапиим всякий раз,
если в правых чаешх имеются положительные коэффициенты
при переменных. Последом [елыюеть тождественных преобра-
преобразований системы линейных алгебраических уравнений может
быть геометрически истолкована как последовательное разло-
разложение векторного уравнения, соотнечетвующего эти системе,
в различных положительных Собственных базисах однократного
замещения.
Имея в виду использование тождественных преобразований
для решения основной задачи линейною программирования, мы
рассмотрим их при следующем дополнительном условии.
Пусть последнее /--е уравнение системы A5) допускает
бесконечную последовательность тождественных преобразований
этой системы *). Это означает, что какое бы число тождест-
тождественных преобразований мы ни произвели, в r-м уравнении
всегда имеются положительные коэффициенты при переменных
в правой части, а разрешающий элемент при каждом преоб-
преобразовании этому уравнению не принадлежит.
Последовательное in тождественных преобразований соот-
соответствует последовательность Л,—> Л2—> Л,—>-. . . переходов
от базиса к базису. Так как при конечных г и я существует
конечное число различных базисов, то в последовательности
Л1—у Л2—'Л,—>¦. . . должны быть возвращения к уже встре-
чашпимся базисам. Будем говори п., что в этом случае имеет
место «зацикливание».
Если при каждом тождественном преобразовании напмень-
' ''/ )
——у свооодных членов Ь,
шее отношение паи
к соответ-
— помер столбца, содер-
отлично от нуля, то
ствующпм коэффициентам а,д, где ik -
мшцего разрешающий элемент arj-k,
значение свободного члена в r-м уравнении системы A8)
с каждым шагом только убывает, что видно непосредственно
из выражения этого свободного члена. Выбор базиса одно-
*) Рассуждении, приводимые ниже, сираве.цры для любого /-го
уравнения системы A5) A и: ('<. г).
40
значно определяет значение свободных членов системы урав-
уравнений, поэтому разным базисам соответствуют разные сово-
совокупности свободных членов, и наоборот. Поэтому в этом случае
возвращение к одному из ранее встречавшихся базисов невоз-
невозможно, а следовательно, не может быть и бесконечной последо-
последовательности преобразований. Эго означает, что после конечного
числа преобразований или все коэффициенты при неизвестных,
справа в г-м уравнении становятся неположительными, ar/ sg: О
(г-]- 1 sS/sg; п), или разрешающий элемент при некотором
преобразовании оказывается принадлежащим этому уравнению.
Если же, начиная с некоторого преобразования, разрешаю-
разрешающий элемент принадлежит уравнениям с пулевым свободным
членом bjt то значение свободного члена в г-м уравнении
остается неизменным. Действительно, из последнего уравнения
системы A8) видно, что вычитаемое в выражении свободного
члена
br — a
rjt
в этом случае равно нулю. В этих усло-
внмх возникает возможность зацикливания.
Гиперплоскость, проходящую по крайней мере через два
базисных вектора, назовем базисной гиперплоскостью.
Наличие нулевых свободных членов в уравнениях преобра-
преобразуемой системы означает, что вектор Ро принадлежит одной
или нескольким базисным гиперплоскостям. Следуя принятой
в литературе терминологии, будем говорить, что в последнем
случае имеет место вырождение.
Таким образом, необходимым условием зацикливания
является существование вырождения.
В качестве примера рассмотрим систему уравнений:
¦2— х.
¦ 2.v.
Соответствующее векторное уравнение имеет вид л^Р,-|-
~\~хгРг ~\~XJ*3 ~- Р|> — (.v4P4-|- -V5PS). При этом компоненты
векторов определяют матрицу
1
0
0
0
1
0
0
0
1
2
3
2
2
3
1
Векторы Рр Р„, Р3, Р4, Р5 (рис. 17, а) образуют несколько
базисов, например базисы Рр Р2, Ps и Р2, Р3, Р4. Базису
41
Р,, Р2, Р3 соответствует основное решение х, == 2;
х3 = 2; х4 = 0; х5—-0. Н этом случае вектор о
ляется линейной комбинацией с положительными коэффициен-
коэффициентами
2
Ро представ-
представГеометрически это означает, что нсктор Ро «пронизывает»
параллелепипед, построенный на вектрах Рг Р2, Р3 (рис. 17,6).
Представим те же уравнении в базисе Р„, Р3, Р4. Для этого
произведем тождественное преобразование. И колонке при
О
переменной х4 имеются положигельпые коэффициенты. Находим
/ ¦) з '> \
mini—; -5-; -j- j . Принимаем за разрешающий элемент коэф-
коэффициент при х4 в первом уравнении. Разрешаем это уравнение
относительно х4 п полученное выражение подставляем в осталь-
остальные два; при этом уравнения принимаю! вид:
1
Из последних уравнений следует, что
базисе Р2, Р3, Р4
вектор Ро представляется в виде Ро = ()-Р„-|-Р3-|-Р4. В этом
случае имеет место вырождение, так как вектор Ро находится
в базисной плоскости, определяемой векторами Р и Р
11
поэтому Ро лежит на грани параллелепипеда, образованного
векторами Р2, Р3, Р4 (рис. 17, о). Заметим, что если бы мы
нарушили правила тождественных преобразований, то пришли
бы к базису, в котором Ро не может быть представлен неот-
неотрицательной линейной комбинацией векторов базиса. Напри-
42
мер, если за разрешающий элемент принять не тот, которому
/ 'I ¦¦> •) \
соответствует min I-^ ; — ; -^- , а коэффициент при перемен-
переменной х4 в третьей строке, то после преобразовании уравнений
будем иметь:
*» = 2-( д-, + 2*,),
xi=-2-(-2xt-3xt),
Из этих уравнений следует, что в оазисе Рг Р2, Р3 вектор
Ро представляется отрицательной комбинацией, содержащей
отрицательные коэффпциенп>1
а решение оказывается неположительным:
В этом случае вектор Ро не пересекает параллелепипеда,
построенного на векторах Р,, Р2, Р4 (рис. 17, г).
Таким образом, нарушение правил определенных выше
тождественных преобразований может привести к отрицатель-
отрицательному базису.
Рассмотрим пример системы уравнении, тождественные
преобразования которой могу г привести к зацикливанию:
х. — 0 — I
хг =- 0 —
х3,-, 1 —
2л-4
U-\-x.
, + х5 -f Зл-, — 8.V,).
рассматривать преобразования этой системы относи-
относитретьего уравнения. И этом уравнении коэффициент
положителен и равен единице. Среди отношений
у| отметим первое. Оно является одним из наимень-
наименьБудем
тельно
при xt
° °
j-; у-
ших среди этих ошошеппй. Поэтому за разрешающий элемент
можно принять коэффициент при переменной х4 в нервом
уравнении. После разрешения первого уравнения относитель-
относительно х4 и подстановки выражения х4 в два других уравнения
получим преобразованную систему:
2-v. + хь
— I— v Л~'} <
4х„ —Ux,).
43
В последнем уравнении снова имеются положительные коэффи-
коэффициенты при переменных в правом часш, например при х5.
Разрешающим элементом в анш случае является коэффициент
. | 0 1 \
при хъ во втором уравнении, так как nun { -г- ; -ту I соответ-
соответствует второму уравнению. Проведем тождественные преобра-
преобразования, соответствующие новому разрешаещему элементу.
Б результате получим систему:
х __ q / 2 v* —-
, = () —
Л
Х2 4" V Л'в — 5*7
-V,, — л'-
В трем.ем уравнении снова имеемся положителыплИ коэффи-
коэффициент при д-в, при этом за разрешающий элемент можно при-
принять коэффициент при переменной л"в во втором уравнении.
После тождественною преобразовании будем иметь:
xt --= 0 - (- 2.V,
2л-2
2.V, - 4л-,
-Зл-4+ л-7
Продолжим последовательное1ь таких преобразований, каждый
раз подчеркивая в третьем уравнении один ил положительных
коэффициентов и выделяя жирным шрифтом соответствующий
ему разрешающий элемент1. В результате получим выражения
исходной системы уравнений в различных положительных
собственных базисах:
х ,--=-- 0 —( *,—2*s--
х„ =- 0 — Bл-, — (i.v3 - -
3.v4+ хь),
10.v4 + 4л-8),
7л-4-Зд-,).
=—0 — ( — ;i.v2 - -
-1.9
>.+и
х, = 0
2-v4 — л-5 — -i л-
^ 2
— х5 — - х6 4-
44
Как видим, после шести тождественных преобразований мы
возвратились к исходной cueiе.ме уравнений.
Таким образом, последовательность тождественных преоб-
преобразований в базисах
12 3 4 2 3 5 4 3 6 5 3 7 6 3 1 7 3
—> Р,Р2Р3 приводит к зацикливанию.
Однако наличие вырождения не обязательно приводит
к зацикливанию, что следует из приведенного ниже примера:
хг = 0 — i
2л-,— *.
х, =-- 0 — ( — а-4 -1- 2хъ — Зх, 4- Зх, - 4л-8 4- х,),
0 =1— ( 3_*г— Хь—xe4- X7— *8 + X9).
В последнем уравнении коэффициент при перемеиопой хл
положителен, а аа разрешающий элемент можно принять
коэффициент при хл в первом уравнении.
Проведя тождественное преобразование, будем иметь:
0
7хв -
2л:.
— 7xs
О = 1 _ (_ Зх, 4-=5хя — 14х, — 2х, 4- 8х8 — 2х,).
Продолжая этот процесс, получим:
2,1 7 4 . 4 , 2
0=1—1 тх, —тха —т.
V О А 6
Затем
к*~и~[ T>.xiV Т Хг "Г Jo хз — Т2 Х|> ^ Т2 Xs "Г 12 XV '
10 _^ji_ __И . _42 ,//4 _92
lii о I*- 1 л /л 11
и
\_
()
_3
42
7х8 +2х
1_ _ И)
> "о •> Jv г
7
3
39 , 38
X
45
В последнем уравнении положительный коэффициент при Xt
одновременно является н разрешающим элементом, так что
бесконечной последовательности тождественных преобразований
не образовалось. Таким образом, вырождение не привело
к зацикливанию.
Произведи тождественные преобразования, соответствующие
114
разрешающему элементу а48 = —у и положив значение неос-
неосновных переменных равным нулю, мы найдем одно из основ-
основных решений исходной системы уравнений:
13
Т8'
4 _
8 '
7
X? 38 '
= 0; xt = 0;
4
* 38'
Отметим, что построение примеров с зацикливанием пред-
представляет большие трудности, так как для осуществления
зацикливания коэффициенты системы линейных уравнений
должны удовлетворять большому числу условий, и только
тщательный подбор коэффициентов может привести к обра-
образованию цикла.
Покажем, что при наличии только двух уравнений
п
A9)
. 'hjXJ)
зациклнвппия быть не может. Матрица векторов, соответствующих
системе A9), имеет вид:
Р, Рг Ро Р3 Р4 Р,
0 0 rris nu rti;-
0 1 b a,3 a2i a2j\
b ^> 0. Тогда вскюры Р, и Р2 образуют базис. Значе-
Значевектора Р, в этом базисе можно представить опреде-
опредеПо допущению
ние компонент
лителями
Пусть я2, и я13 больше ну.тн. Это означает, что уравнения A9) можно
б 6 P Р б
подвергнуть
Р Р
()
Р2 к базису
13 у ур
преобразованиям, переходя or 6a:mca
3 2 р is ррй
Р3, Р2 коэффициенты уравнений A9) принимают значения, определяемые
по формулам G) предыдущей главы. Так, значения коэффициентов
ру рр , 2 у
Р3, Р2 и принимая элемент ais за разрешающий. В новом базисе
Р фф й 19
46
при переменной х4 будут иметь вид:
1
в первои строке -г-
1
во второй строке -г-
я,
23
где Л =
а.
О
.. ... «23 1
Если числители этих выражений положительны, то в базисе Р„ Р2
коэффициенты при х4 положительны. Так как наименьшее отношение
для системы (И)) споил приходится на первое уравнение, то, принимая
коэффициент при х4 в первом уравнении за разрешающий элемент,
можно повторить преобразование системы уравнений, перейдя от базиса
Р„ Рг к базису Р4', Р2.
Допустим, что после каждого преобразования можно провести
следующее так, что последовательность базисов
Р2 — Р3, Р2 — Р4, Р2
образует цикл. Тогда каждый из
дователыюсти:
(Р,Р2) (Р,Р2) (Р,Р2)
Р„
—*...-— Рк, Рг ~> Р„ Р2
определителей и следующей после-
послеB0)
(Р,Р3
должен быть положительным (определители нижнего ряда соответ-
стиуют последовательности положительных коэффициентов во втором
уравнении, определи гели
верхнего ряда — последова-
последовательности разрешающих эле-
элементов). В данном случае
векторы Рудвухмерные, и по-
поэтому значение каждого ш
определителей п последова-
последовательности ('20) как по знаку,
так и по величине совпадает
с соответствующим вектор-
векторным произведением. Тогда
требование положительное гп
всех определителей ('20) рав-
равносильно требованию, чтобы
вектор Р, лежал между век-
векторами Р, и Р2, образующими
острый угол; вектор Р4 —
Р
и
между векторами , 2
и т. д. Продолжая эти рассуждения, получим, что вектор Р, должен
лежать между векторами Рк и Р2, чего быть не может (рис. 18). Про-
тппоречне леи<о может быть обнаружено и аналитически. Запишем систе-
систему векторных panciici в.
Рз = 231Р, + :
B1)
p. =
47
Умножая каждое из равенств B1) пекторно один ран справа на Р2,
а другой раз слева на торой иектор, входящий в правую часть каж-
каждого равенства, убедимся, что псе коэффициенты в равенствах B1)
положительны, так как но допущению нее соответствующие вектор-
векторные произведения также положительны. Так, для уравнения Р,=
=ra31P,+=<s2P2 имеем (Р3Р2) = x,,(P,P2)-f з32 (Р2Р2)/ откуда а,, > 0.
Умножая то же уравнение слева на Р,, получим, что а,2 > 0. Далее,
подставим и выражение для Vk вместо Pk-\ его выражение, в полу-
полученное выражение подсташш вместо Р^_2 его выражение и т. д.
б + 0 0
р
В результате будет иметь Pft =
Р* р
^2 р
i +T2*P2> 'Uk > 0| Тг* > 0, откуда
ТжАг Га
Сопоставляя полученное равенство с последним равенством систе-
системы B1)
Р, = a.xkVk + сг12Р2, а1к>0; а12>0,
приходим к протипоречию.
Покажем, что для образования цикла при любом числе п уравнений,
и > 2, нужно совершить не менее шести тождественных преобразо-
преобразовании. Так как мы рассматриваем только однократные замещения
в базисах, то возвращение к исходному базису можно ожидать после
'Ik преобразований, где &=1, 2,3, ... Возвращение при ^=1 невоз-
невозможно, так как определители, отвечающие этому случаю, имеют вид:
(Р,р2...р,. ..рг); (Р,р2...ру...рг); (р,р2...р,...рг)
\
(Р1Р2...Р,...Ру); (Р.Р....РУ...Р,.).
Два последних определителя отличаются одной перестановкой
P,- м Ру, а поэтому имеют разные знаки, что противоречит
предположению их положи гелыюсги.
Для доказательства невозможности образования цикла при fe = 2
нужно показать, что пи один из путей тождественных преобразований,
представленных ниже, неосуществим.
1. (Р,Р2... Ри... Р„... Рг) -+ (Р,Р2... Р •... Р,-2... Рг) —+
(Р1Р2
2.
3.
(Р,Р2...Р,,.,
¦(р/р/.-.р/.
(Р.Р2- -.РД.
.р|'...Рг)-*
р,2..Рг);
..Pi р,) ->
.Р/з"..Рг)^
.Рл...Рг) —
(Р,Р2...Р,,...Р1г..Рг);
-(Р,Р2...Р/1...Р,2...РГ)
•(P1P2...Py1...P/V..P,.)-
Первый путь перехода от базиса к базису невозможен, так как
он сводится к случаю двух уравнений.
Второй путь также невозможен, так как первый и последний
определители отличаются одной перестановкой и поэтому не могут
быть оба положительными.
Остается показать невозможность третьего пути. Для этого надо
убедиться в том, что предположение о положительности всех опреде-
определителей л-го порядка, ныннс.шны.ч ниже, ведет к противоречию:
1
1....Г,
1.
1 •
/.
'/,/2
''2/2
'Г/2
".л
"Vs/i
1
"l/.
"'.У.
"г/,
1
(Jl/2
«.•,/2
«hh
arji
"i, к
Раскрывая эгп семь определнгелей, будем иметь:
2) а'г'/'у> (>;' 5) a';'/J,[yt); ''' ''Н
л) a; )nhl — /?, -я,- ., > 0; 6) п,- }аг/ — аг/ а,- , < 0;
" "" 7) яг>;<Ь.
Из 1), 2), 4) и 7) следует, что а^/г < 0. Из 2), 5), 6) и 7) следует,
что ahjx < 0.
Введем обозначения:
t, k, q, т„ kv qt — положительные числа.
Тогда из 3) имеем tqi — /•',G1ti2 > 0
п.) 4) имеем — etj -|- k^kzr, > 0
из 6) <7,t,2 — liqi2 > 0
qr > tl.qj*
kit, - 1 > 0,
> 0,
0,
43
Сопоставляя неравенство 1 >/?,/? с ранее полученным &,?>1,
обнаруживаем противоречие.
Итак, зацикливание может наступить только после того, как бу-
будет совершено не менее шести преобразований.
§ 8. Метод определения неотрицательного решения
системы линейных алгебраических уравнений
Пусть задана система т линейных алгебраических уравне-
уравнений с п переменными:
amjXj
A3)
Без ограничения общности будем считать, что Ь- 5» 0 (этого
всегда можно достигнуть умножением обеих частей соответст-
соответствующих уравнений на —1).
Представим систему A3) в виде
'=1,2,..., т.
B2)
Если в системе B2) имеется переменная, входящая только
в одно уравнение, и коэффициент при переменной внутри
скобок имеет знак «-]-», то такое уравнение можно разре-
разрешить относительно этой переменной.
Допустим, что уравнения системы B2) разрешены относи-
относительно всех таких переменных. Тогда после соответствующей
перенумерации переменных система может быть записана в виде:
=(>ь-— («2г0+Ли + 1 + "¦„„, 2х ,
0 =
0 = Ьт — (а
Или сокращенно:
X, =
и i V
B3)
0=.b-, — (
2
7 = Л,-И
где
/== 1,2 /0; Y=l,2, ..., у0;
= 0.
Любое уравнение в системе B3), не разрешенное относительно
какой-либо переменной, будем называть ^-уравнением.
Таким образом, всякая система линейных алгебраических
уравнений может быть приведена к виду B3)*).
Для отыскания неотрицательного решения системы B3)
подвергнем ее последовательным тождественным преобразова-
преобразованиям, удовлетворяющим следующим условиям:
1. Отыскиваем О-ураиненне, у которого свободный член Ь{
больше нуля. (Если такого О-уравненпи нет, то значения пе-
переменных
Xl=^bt; Xj^Q (/=1,2, ...,/„; J=l0 + 1, . . ., k)
образуют неотрицательное решение системы B3).) Пусть это
будет 1-е уравнение.
2. Отмечаем в г-м уравнении положительный коэффици-
коэффициент а/у.| **).
3. Находим разрешающий элемент а:-^ и производим тож-
тождественное преобразование системы B3).
4. i-й О-уравпепне используем для дальнейших преобразо-
преобразований системы до тех пор, пока мы не разрешим его или не
установим, что система B3) несовместна **).
5. После разрешения /-го О-уравнения отыскиваем следу-
следующее О-уравпение с положительным свободным членом и про-
производим с ним аналогичные действия.
*) Если и системе B3) нет ни одного уравнения, разрешенного
относительно какой-либо переменной, то („ = 0, и система B3) состоит
только из О-ураппеннй.
**) Если в /'-м уравнении нет положительных коэффициентов при
неизвестных, то система B3) оказывается несовместной, так как урав-
уравнение 0 = ft,- — {~a,jXj), и котором ft,- > 0, а все я,у=5: 0, не может быть
удовлетворено ни при каких неотрицательных значениях переменных
O
51
6. Этот процесс продолжаем до тех пор, пока не освобо-
освободимся от всех О-уравненпй.
Примечания: 1. Число уравнений в преобразованной системе
может оказаться меньше т, так как при подстановке выражения раз-
разрешенной переменной в остальные уравнения некоторые из этих
уравнений могут обраппься в тождества 0 = 0, которые следует
исключить из дальнейшего рассмотрения.
II. Пусть в исходной системе B3) или в преобразованной системе
обнаружено уравнение, разрешенное относительно некоторой неремен-
неременной, имеющее свободный член, равный пулю: х, = 0 — (I'jS^.vA и такое,
что все его коэффициенты при переменных в правой части неотри-
неотрицательны. Так как роль таких переменных может быть только пуле-
пулевая, чтобы х,- были неотрицательны, следует положить их равными
нулю по всех уравнениях, от чего испытуемая система значительно
упрощается. Аналогично исключаем те О-уранпсння, у которых сво-
свободный член равен нулю, а отличные от пуля коэффициенты при пе-
переменных в правой части имеют одинаковый знак. Значении этих пе-
переменных в остальных уравнениях принимаем равными пулю.
Рассмотрим, к каким результатам могут привести после-
последовательные тождественные преобразования, удовлетворяющие
условиям 1—6.
а) Возможно, что после конечного числа тождественных
преобразований система освободится от 0-уравнепий. Оче-
Очевидно, и этом случае система BJ5) совместна. Совокупность
значений переменных, получаемых приравниванием неосновных
переменных нулю, а основных — свободным членам в системе, не
содержащей 0-уравнений, является неотрицательным решением.
б) Возможно, что после конечного числа тождественных
преобразований обнаружится, что используемое 0-уравнеиие
превращается в уравнение вида
0 — Ь\ (jj a'i/xj)>
где b'i^>0, a'-, sg: 0 для всех j. В этом случае система несов-
несовместна.
в) Наконец, может иметь место случай, когда система не
освобождается полностью от 0-уравпений, а условия возмож-
возможности применения тождественных преобразований не наруша-
нарушаются. Так как при последовательном применении тождествен-
тождественных преобразований число 0-уравненнн не может возрастать,
то в этом случае некоторое 0-уравненпе обладает тем свой-
свойством, что оно всегда имеет по крайней мере один положи-
положительный коэффициент при переменных в правой части, но раз-
разрешающий элемент ему никогда не принадлежит. Заменяя это
0-уравнение
52
уравнением
где s — сколь угодно малое положительное число, и рассмат-
рассматривая последнее уравнение имес ге с разрешенными, мы видим,
что в случае в) происходит зацикливание.
Изложенное выше дает возможность высказать следующее
утверждение:
Какова бы ни была система т алгебраических у равнений
с п переменными, последовательное применение к ней тож-
дественчых преобразовании позволяет через конечное число
шагом (::а исключением случи- в зацикливания) определить,
совместна ли система в области неотрицательных значе-
значений переменных, /i случае совместности системы на по-
последнем- шаге преобразований образуется некоторое неот-
неотрицательное решение.
Важным свойством приведенного метода является его при-
применимое п> к произвольной системе линейных алгебраических
уравнений, в том числе и к линейно зависимой системе, при этом
не требуется заранее выделять линейно независимые уравнения.
Кроме того, так как всякая система линейных неравенств
добавлением неотрицательных переменных может быть сведена
к системе равенств, то этот метод также пригоден как для
определения совместности системы неравенств, так и для
нахождения одного из неотрицательных решений в случае их
совместности, при этм также не требуется выделения много-
многогранника решений в '„чистом виде.;.
На рис. 1!) приведена блок-схема программы определения
неотрицательного решения произвольной системы линейных
алгебраических уравнений с помощью электронных вычисли-
вычислительных машин.
Машине задаются коэффициенты при переменных и исход-
исходной системе и свободные члены. Кроме того, при решении за-
задач линейного программирования задаются коэффициенты ми-
минимизируемой линейной формы. По программе машина, выпол-
выполняя последовательность тождественных преобразований, про-
проверяет условия совместноегп системы.
В случае несовместной системы машина сигнализирует об
этом факте и останавливается. Если система совместна, то ма-
машина определяет неотрицательное решение, выдает его (если
необходимо) и переходит к поиску оптимального решения.
Рассмотрим примеры.
53
Проверка наличии положительных коэф-
коэффициентов при ней.(постных в уравне-
уравнениях системы
несовмес I на
Останов
машины
Переход к поиску
оптимального
решения
Выдача неотрица-
неотрицательного решения
Выбор первого положите.1ыюго коэф-
коэффициент а.. /,. и нервом О-ураннешш
Выбор положи
а,-,-.,: в столоне
системы
ел
Г
Ы1ЫХ
среди
коэффициентов
нсе.ч уравнений
Вычисление опюшешш
Ь;
Нахождение iniii - '- - среди чисел — '-
Разрешение уравнения /:': относительно
переменной л,,.
Перемещение разрешенною уравнения
на место первого в сие семе уравнений
Запоминание номера j'~ переменной х ¦„.
Исключение переменно!"! Xjg из псе.х
уравнений системы
Проверка наличия тождеств вида
О 5з 0 в системе к амивегстеппо со-
сокращение числа уравнений
Проверка наличия О-уравпепнй
- 1-
Рис. 19.
54
Пример. Определить, совместна ли система в области
неотрицательных значений переменных:
0.-^7 —A.*,
2*.
4*,
В первом О-уравненни положительный коэффициент при хи
равный единице, одновременно является и разрешающим эле-
элементом:
+
Во втором О-уравнеипп коэффициент при х, положителен;
разрешающий элемент принадлежит первому уравнению:
Система несовместна, так как в последнем уравнении свобод-
свободный член положителен, а оба коэффициента в скобках отри-
отрицательны; поэтому второму уравнению не удовлетворяет ни
одна точка, для которой д;,5=0; х25=0.
Пример. Найти неотрицательное решение системы урав-
уравнений:
1) о —Я--(~2а-1+*, + 4.1
О —- Г) — ( -2л-, + 2х2 + 7
Производим тождественные преобразования системы:
л. ——— ,. 1 ~,v-^o~i~ *^а ~i
2) 0 ---^ (> - ( 2а-2 -]- 6х, 4- 4х4),
1 /1
У ' i
J
Одно из неотрицательных решений системы есть
Изложенный выше метод нахождении неотрицательного решения
системы уравнений может служить одним m способов определения
ранга матрицы. В самом деле" Пусть дана матрица
Примем ее столбцы за векторы Р,, Р2, ...,Р„ и составим уравнение
0 -^ Р» - (
2
/—
в котором положим Ро = Pj. Ясно, что это уравнение имеет неотри-
неотрицательное решение (например, х, = 1; х-=0; / = 2, 3, ... ,//). Пред-
Представляя векторное уравнение
к ро - B
xjpj>i!
виде системы т
уравнений и подвергая последнюю тождественным преобразованиям,
освободимся от О-уравненнй. Число разрешенных уравнений, получен-
полученное после исключения О-уравнеиий, определяет ранг матрицы. При
этом, как можно показан., число преобразований, которые необходимо
провести, также равно рангу матрицы.
Пример. Найти ранг матрицы
2—4 3 I 0
1—2 1—42
0 1—1 3 1
4 7 4-45|
Выполним последовательность тождественных преобразований:
0 = I - ( х, - 2а-2
0 = 0-( л-2
0 -.= 4 - D.у, - 7л-2
^,+ .v4),
л-, - 4.v4 + 2х6),
.vs+H.v4-|- .vs),
4л-, - 4.у4 Л-\^
х, = 1 - ( - 2х2 + л-, - Лх, 4- 2л-5).)
0 = 0-( х,+ 9x4-4.v5),
О П / 1I
0 = 0 — ( х2 — а-., -(- 3.V, 4- v,l
0 = 0 — С л-2 \- 12л-, - Зу,)
Ш'1Г
56
D.r4 - 4.v5), -
л-, ^: I - ( - 2.v2 -
3x5).
" ОЛ-) )
of /
II шаг
- ( IXv,-
^ - 4.v5),
III шаг
0 -- О
Ранг матицы /• — 3.
§ 9. Решение задачи линейного программирования
Задача линейного программирования, как сказано выше,
может быть сформулирована следующим образом:
задана система т линейных уравнений с п переменными
A3)
amiX, +
= Ьт
н линейная форма f^~-clxl -|- f 2.va -|" • • • + V/ + • • • + с»хп
тех же переменных. Требуется среди всевозможных неотрица-
неотрицательных решений
..., х„)
системы A3) найти такое решение {х\\ х0,; ...; х°), при ко-
котором / принимает наименьшее возможное значение.
Для решения этой задачи определим одно из неотрица-
неотрицательных решений системы A3) способом, изложенным в преды-
предыдущем параграфе. В результате система A3) перейдет
67
в эквивалентную ей систему *):
2 "Г
*;,-*;¦
х' —
г = 1, 2,
:+•••+«;/•;-г-
г; л с? от; г А- к
B4)
Подставляя выражения основных переменных и линейную форму
н вводя соответствующие обозначения для постоянных величин,
представим / в виде линейной функции
/~r
B5)
В соответствии с симплекс-методом для нахождения оп-
оптимального решения систему уравнений B4) и линейную функ-
функцию B5) подвергаем тождественным преобразованиям до тех
пор, пока не нарушатся условия их осуществления, т. е. пока
не исчезнут положительные коэффициенты при переменных в
форме B5). Но так как изложенное в первых двух парагра-
параграфах этой главы о зацикливании относится и к задаче линей-
линейного программирования, то можно высказать следующее утвер-
утверждение:
Применение конечного числа тождественных преобразо-
преобразований позволяет (за исключением случаев зацикливания)
найти неотрицательное решение системы уравнений, при
котором форма принимает наименьшее значение.
В целях исключения возможности зацикливании предложено
несколько методов. Некоторые из этих методов требуют при
проведении тождественных преобразований дополнительных
операций всякий раз, как имеет место вырождение. При вы-
*) После соответствующей перенумерации неизвестных.
58
рождении разрешающий элемент определяется неоднозначно.
Дополнительные операции позволяют на каждом шаге тожде-
тождественных преобразований в случае вырождения выбрать раз-
разрешающий элемент так, что зацикливание исключается. Слу-
Случай вырождения, как уже было отмечено, всегда имеет место,
как только вектор Ро принадлежит одной или нескольким ба-
Анализ практического решения задач
мировання подтверждает предположение о малой вероятности
зацикливания, а построение примеров зацикливания встретило
довольно значительные трудности, связанные с необходимостью
Те редкие случаи, когда образуется цикл, при ручном ре-
решении задачи могут быть обнаружены непосредственно.
Так, поставив задачу нахождения неотрицательного реше-
решения системы
-Злг.
х., ¦== 0 _
при котором линейная функция
достигает наименьшего значения, и проделав последователь-
последовательность тождественных преобразований, как в примере, рассмот-
рассмотренном на стр. 44, мы обнаруживаем, что пришли к исходной
группе основных переменных. Если не обратить внимания
на этот факт, то процесс решения может оказаться беско-
бесконечным, значение же линейной функции при этом остается по-
постоянным.
При обнаружении зацикливания следует изменить последо-
последовательность тождественных преобразований, выбрав другой
разрешающий элемент. Так, поступая в рассмотренном примере,
как изложено ниже, мы устанавливаем, что линейная функция/
не ограничена снизу:
л- ---0 ( х.—х. — х.-А-Зх.).
/=--3 —
- 8*.).
69
у Г) __ I .
/=з- -i
4
13
В данном случае значение формы может быть уменьшено
за счет увеличения значения Л',, но так как в колонке коэф-
коэффициентов при переменной хл отсутствуют положительные ко-
коэффициенты, т. е. нет пи одного разрешающего элемента, то
это означает, что нет никаких ограничений увеличению пере-
переменной jc4. При этом функция / сганови icw неограниченной
снизу.
При решении задач на электронных вычислительных ма-
машинах в программе следует предусмотреть возможность обна-
обнаружения возвращения к уже встречавшейся группе основных
переменных. И только в случае обнаружения зацикливания
следует ввести ту часть программы, которая предусматривает
дополнительные операции, исключающие возможность зацик-
зацикливания.
При этом наиболее простой дополнительной операцией
является выбор другого разрешающего элемента на том шаге,
на котором обнаружено повторение.
Пример. Определить наименьшее значение линейной
функции /=5дг, — 10л'„-j-7л — 3xi па множестве неотрица-
неотрицательных решений системы уравнений:
= |-(-2*,-
= 4- (
60
xi 2
Х2 = 0-
0 = 0-
J_ ^
(роль х, может быть только равна 0!).
¦1—|
/-= — 18 —(-
/rniT^"-7^ при ДГ1=О,
х, = 0,
у. 1
_ J_
' 2 •)
Пример. Среди неотрицательных решений системы не-
неравенств:
— 20.V, + 12х2 — 15х3 ===: 60,
л-,+ 2.v,— Зх3^б,
¦Ч-Ь К+ 4л-3<12,
*, = о- -^-^ .
/=-J-(?^
Зх.. ?=: 60,
2х3^ 10,
— 20х,
найти такое, при котором линейная форма f==xl-\-xi-\-xs
достигает наименьшего значении.
Решение. Систему неравенств путем введения дополни-
дополнительных переменных сводим к системе уравнений:
уу = 60 — ( — 20л-, 4- 12х2 — 15xs),
Уг= 6 — ( х,4- 2х2— Зх3),
— ( _ 20х, — 15х2 + 3*,),
О -:
0 =
42 — ( 6л, 4" 7х2 + 42х, —у%)
61
и подвергаем тождественным преобразованиям:
х. = 1 '' - ¦ ' '
125 ,87 1о
7 Х1-ГТГЛ'2 л^Л >
32
:95^-
: 7~-
5i~
5
И
54 *2 I 72-^5 216-
1383
~5T '
95
1512-5'"
72 У*
10
54 2 ' 72- 5
265
14.4
ОА 5 / 265 14.4
Одним из неотрицательных решений системы неравенств яв-
7 А 5 п
ляется решение х1 = -^-; х2 = 0; х3:=-г-. Выразим теперь
линейную форму через неосновные переменные: /=2 —
7 j^ 1
18х* \2У* 36 -v«
Как видно из последнего выражения линейной формы, даль-
дальнейшее ее уменьшение в области неотрицательных значений
переменных невозможно. Поэтому первое решение л;1=у-;
х2 = 0; х3 = -т- явилось и оптимальным, а соответствующее
значение линейной формы /lllin = 2.
62
§ 10. Об одной задаче на минимаке
Пусть задано п ли-мерных векторов Р;- н множество Г =
= {/ } соответствующих им вещественных чисел tj, j= I, 2,. ..
. . ., п.
Рассмотрим множество К—--{_у} всевозможных неотрица-
неотрицательных решений у---. {х } уравнения
где Ро — заданный век юр в да-мерпом пространстве, не равный
нулю.
Переменные х • ¦-/ 0 в любом из решений у условимся обо-
обозначать через х ., а соответствующие значения tj—через tj.
Через {tjv\ обозначим систему чисел tj, соответствующих
переменным х-/^0 в решении у.
Наибольшее число среди системы чисел {tJy\ условимся
обозначать через iу.
Таким образом,
/ = max {tjy}.
Теперь поставим задачу:
Среди всевозможных решений у ? Y найти такое уопг, для
которого соответствующее
или
УпУ
Решение у (если оно существует), удовлетворяющее этому
условию, будем ни.зьшать оптимальным и обозначать через ^Ш1Т.
Такие задачи называются задачами на минимаке. (Частным
случаем этой задачи является транспортная задача но крите-
критерию времени, которая подробно рассмотрена в главе IV.)
Подвергая систему т линейных алгебраических уравнений
с п переменными
= Ь{, 1
\т\
соответствующую векторному уравнению У! ¦x;;P/==Poi тожде-
01
ственпым преобразованиям, мы можем через конечное число
шагов получить оптимальное решение.
Для этого надо;
1. Построить начальное неотрпцаимыюе решение системы
уравнений.
2. Среди основных переменных х; найш ту, которой соот-
соответствует наибольшее значение /,-, ранное /mix.
3. Исключить из дальнейшего расою iрения неосновные
переменные х}-, для которых tj ^s /™ах.
4. В i-й строке найти под знаком 2 положительный ко-
коэффициент я,у> и определить разрешающий элемент а^р
после чего провести тождественное преобразование.
5. Повторяя (если необходимо) этап 4 несколько раз,
вывести неременную xt из совокупности основных переменных
и исключить ее из дальнейшего рассмотрения.
6. Этапы 2— 5 повторять до тех пор, пока на некото-
некотором шаге в соответствующей строке преобразованной системы
уравнений все коэффициенты при неременных станут неполо-
неположительными.
Основное решение, полученное на этом шаге, является оп-
оптимальным.
В самом деле. Пусть после некоторого числа тождествен-
тождественных преобразований исходная система примет вид:
X:
=f>i —(!«,- /X,).
Р j P1 '
<kJ
Пусть переменной х- соответствует наибольшее значение tm?*.
Тогда, если Ь-<0, то, исключив х{ из дальнейшего рас-
рассмотрения, получим несовместную систему. (Если bi =0, то
согласно примечанию II на стр. 52 следует положить х,- =0,
ft
а также лГу = О для тех у, для которых a- j ^ 0. После этого
следует продолжить тождественные преобразования.)
ГЛАВА HI
РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ
ПО КРИТЕРИЮ СТОИМОСТИ
Ниже рассматривается одна из типичных задач линейного
программировании—т\< начинаемая транспортная задача. При
планировании нереио.юк грузов часто возникают вопросы наи-
наиболее рациональной организации перевозок. В одних случаях
это означает определение такого плана перевозок, при котором
стоимость последних пила бы минимальна. В других случаях
более важным является выигрыш времени, и поэтому среди
возможных планов транспортировки ставится задача определе-
определения такою плана, реализация которого дает возможность до-
доставить грузы к потребителю в самое короткое время.
Первая задача получила название транспортной задачи но
критерию стоимости, а вторая — транспортной задачи по кри-
критерию времени.
Первая задача является частным случаем задачи линейного
программировании и может быть решена изложенным в преды-
предыдущей главе симплексным методом. Однако в силу особенно-
особенностей этой задачи она проще решается так называемым комби-
комбинаторным методом. При малом количестве пунктов отправления
и назначения этот метод позволяет решать такие задачи
вручную. При большом количестве пунктов отправления и
назначения задача может быть решена лишь с применением
электронных вычислительных машин. Так, задача транспорти-
транспортировки из 'АО пунктов отправления в 40 пунктов назначения
решается на машине «Стрела > за 25—30 мин.
В главе III излагается комбинаторный метод решения
транспортной задачи по критерию стоимости и приводится
упрощенная блок-схема решения этой задачи на вычислитель-
вычислительных машппач.
3 А. С. Барсов 65
§ 11. Постановка задачи
Транспортная задача но критерию стоимости может быть
сформулирована следующим образом.
Обозначим через av a2 ат количество единиц одно-
однородного груза, находящегося и каждом из т пунктов отправ-
отправления, а через />,, Ьг,..., Ьп — количество единиц груза, по-
потребного для каждого из п пунктов назначения.
Пусть Хц означает количество единиц груза, которое мы
планируем для перевоза из /-го пункта отправления в у-й
пункт назначения, а с^ — стоимость перевозки единицы груза
от /-го пункта отправления к у'-му пункту назначения.
Т а б л и ц а '2
а,
аг
а,-
ь, ¦¦
cjl^xn
^^
/^
/^
/^
'^
ьл
/^
Пусть количество груза, отправляемого из всех т пунктов,
равно количеству груза, потребного в п пунктах назначения.
В этом случае должно выполняться условие
т п
>>,•= 2 bi- B6)
Будем записывать условия такого типа задач в виде таблицы 2.
Матрицу X—-{x(J) порядка /и Xл с неотрицательными эле-
элементами л:,-у^=0, которая удовлетворяет условиям
(/=1, 2...,/я),
B6')
(У=1,2,...,л),
B6")
назовем решением задачи транспортировки. Условие B6') озна-
означает, что из j'-го пункта отправления вывозится весь груз, а
66
условие B6") означает, что потребность у-го пункта удовлет-
удовлетворяется полностью. Задача сводится к определению таких
неотрицательных значений х!/} чтобы общая стоимость пере-
перевозки
была наименьшей.
Используя определение скалярного произведения матриц,
задачу транспортировки по критерию стоимости можно сфор-
мулировать иначе.
Пусть задана матрица С=(с/;), где с^ — вещественные
неотрицательные числа. Требуется среди всех решений X,
записанных в виде матриц и удовлетворяющих условиям B6')
и B6"), найти такое, для которого скалярное произведение
(СХ) достигает минимального значения. Решение, представля-
представляемое матрицей X, удовлетворяющей этому условию, назовем
оптимальным.
§ 12. Основные решения транспортной задачи
по критерию стоимости
Рассмотрим заданную матрицу С=(с;у) и произвольную
матрицу-решение X = (х,у) (/=1, 2,..., т); (у= 1, 2,..., я).
Будем считать, что т^п, так как в противном случае их
можно поменять ролями.
Введем некоторые определения.
Пару натуральных чисел ij назовем клеткой, а произволь-
произвольное множество клеток — набором. Последовательность клеток,
имеющая вид t1jv /,у2, г2у2, iz
называется цепью.
Цепь называется замкнутой, если она имеет вид
Всякую замкнутую цепь назовем циклом. Набор называется
циклическим, если он содержит по крайней мере один цикл.
Набор называется ациклическим, если он не содержит циклов.
Каждой клетке ij соответствует один и только один эле-
элемент х(;. матрицы-решения X, а также один и только один
элемент с{1 матрицы стоимости С. Поэтому всякий набор кле-
клеток является одновременно и набором соответствующих эле-
элементов как xtj, так и с!;-.
Перенумеруем элементы замкнутой цепи 0, обходя ее, на-
например, по часовой стрелке. Будем говорить, что элементы
3*
67
этой цепи с нечетными номерами образуют нечетную полуцепь
в", а элементы с четными номерами — четную полуцепь В4.
Условимся сумму элементов c(J- нечетной полуцепн обозна-
обозначать через 2 ci/> a сумму элементов Monioii полуцепи через
Теорема. Каково бы ни было решение X с циклическим
набором отличных от нули элементов х;-, существует ре-
решение У с ациклическим набором элементов _у/;- и такое,
что (CY) sc: (CX), а число отличных от нуля элемен-
элементов решения Y меньше числа таких же элементов ре-
решения X.
Доказательство. Пусть отличные от пуля элементы
матрицы X образуют замкнутую цепь Н(. Сравним суммы
ZuiJ и 2 с0'' одиа из сумм, например ^У] с'/;., должна бы п.
в;1 е;1 в;1
такой, что 2С//^2С//-
вч а»
Образуем новую матрицу Х'=--(х'^) из матрицы Х--(х^)
изменением элементов в цени
х(,/, =x>ih~
следующим оорпзом:
, mm
ч '
•-А1
Ч
Здесь
полуцепп В"
В'1
')
а
— наи-
наи,, /2_/а,. . ., ifjt — клочки нечетной
'|Л> 'Jii'-м h/i — клетки четной полуцепн
меньший элемент в нечетной полуцепп В". Для всех других
клеток ij положим х'., = х{]-.
Легко видеть, что матрица X', получаемая из матрицы X
перемещением но цепи В элемента А'.1", также будет решением
транспортной задачи. Число нсех элементов х/(, отличных от
нуля, у матрицы X' станет по крайней мере па единицу меньше.
Так как (СХ')-(СХ) -|- (^ сц --^] си) л™1", то (С.'А") ^~(СЛ').
Продолжая построение таких решений и далее, мы через
конечное число шагов придем к решению }', у которого от-
отсутствуют замкнутые цени О среди члемеитв л".-, отличных
от пуля, a (CY) sg (CX). Теорема доказана.
Следствие. Для нахождения хотя бы одного опти-
оптимального решения достаточно рассмотреть всевозможные
решения X с ациклическими наборами отличных от нули
элементов х,ч.
Всякое решение Аг, представленное в виде матрицы, отлич-
отличные от нуля элементы х/;- которой образуют ациклический
набор, называется основным.
Вообще говоря, в матрице X, представляющей произволь-
произвольное решение, может быть различное число элементов xt-, от-
отличных от нуля. Однако, какое бы решение X мы ни
взяли, оно имеет не менее п отличных от нуля элементов, что
следует из условия B6") § 11. С друтй стороны, справед-
справедлива следующая
Теорема. Число N элементов xijt отличных от нуля,
в любом основном решении удовлетворяет условию
п s=S N s? т -\- п — 1, где т — количество пунктов отправле-
отправления, а п — количество пунктов назначения.
Доказательство. Предварительно убедимся в спра-
справедливости двух лемм. Построим в (т-}-я)-мериом простран-
пространстве т X и векторов и поставим их во взаимно однозначное
соответствие с множеством всех клеток ij матрицы C=(ci/).
Клетке ij поставим в соответствие вектор р.-, имеющий все
компоненты, равные нулю, за исключением /-и п т -{-/-й,
каждая из которых равна единице. Очевидно, всякому набору
клеток соответствует некоторое подмножество векторов и,
обратно, всякому подмножеству векторов соответствует неко-
некоторый набор клеток.
Лемма 1. Если множество векторов {Р,у} линейно за-
зависимо, то соответствующий набор клеток циклический.
В самом деле. Пусть известно, что множество {Р,у} векто-
векторов линейно зависимо. Тогда существует линейная комбинация
этих векторов, приводящая к нулевому вектору q @, 0,..., 0),
причем по крайней мере один из коэффициентов отличен от
нуля. Будем рассматривать векторы, входящие в эту комбина-
комбинацию, только с коэффициентами, отличными от нуля. Пусть
это будет, например, вектор Piljv Тогда обязательно в ли-
линейную комбинацию должен входить по крайней мере один
вектор с тем же индексом /,, например Pilji. Это про-
происходит потому, что в векторе q все компоненты равны пулю,
но поскольку в комбинацию входит вектор P,\jv то для обра-
обращения /-й компоненты в нуль надо иметь в комбинации по
крайней мере еще одни вектор с той же компонентой, отлич-
отличной от нуля. Так как теперь входит вектор с компонентой у2,
то должен входить по крайней мере еще один вектор с такой
же компонентой, например вектор Р,-„,-,. Рассуждая аналогично,
мы построим последовательность векторов
Р.-
1/2'
Р'2/3, • • •
3* А. С. Барсов
69
Поскольку имеется только конечное число векторов, то
после некоторого числа шагов мы должны прийти к вектору
Р',у,, от него — к век гору Р,,/г Эти последовательности век-
векторов соответствует набор клеток
'.Л- '2Л
'(Л-
который является циклическим.
Лемма 2. Всякий набор из т-\-п клеток является
циклическим.
Чтобы убедиться в справедливости этой леммы, достаточно
показать, что любые (т-\-п) векторов из числа построенных
линейно зависимы. Докажем это.
Рассмотрим (т -f- и)-мерный вектор
Q(—1, —1,...,
1;
1).
Он ортогонален ко всем Р,-,. Отсюда следует, что все
векторы Р,-.- принадлежат т-\-п — 1-мерному пространству, а
поэтому всякие т-\-п из них линейно зависимы.
Из условия B6") § 11 и последней леммы следует, что
n<C_N<^m -\-п. А так как непосредственно па примерах
можно убедиться, что существуют задачи, для которых М=п,
н задачи, для которых N=m-\-n—1, то окончательно по-
получаем, что N действительно удовлетворяет условию и sg N^
sgm-j-я—1, н теорема доказана.
Из только что доказанных лемм следует, что множество
векторов {Р,у}, соответствующее ациклическому набору из
т-\-п—1 клеток, является базисом в (/я-|-н)-мерном про-
пространстве построенных векторов Р... Обозначим через И про-
произвольный ациклический набор из т-\-п—1 клеток.
В силу взаимно однозначного соответствия всевозможных
базисов (т -(-л)-мерного пространства и ациклических наборов
из т-\-п—1 клеток, известные свойства базисов многомер-
многомерных пространств применительно к ациклическим наборам из
т-\-п—1 клеток можно выразить следующим образом.
Свойство 1. Пусть //, — некоторый ациклический
тА-п—\ набор и (/_/) ? Нх*). Тогда набор Нг, полученный
присоединением (//) к набору //,, содержит один и только
один цикл 6.
*) Знак ? означает, что клетка Ц набору Я, не принадлежит.
Свойство 2. Пусть (/", j')^=(i, j) и (/', у") ? в. Тогда
набор /У3, получаемый из Нг исключением клетки (/', у"), снова
является ациклическим т-\~п—1 набором.
Наборы Нх и Н3, о которых говорится в свойствах 1 и
2, отличаются только одной клеткой.
Определение. Два ациклических т-\-п — 1 набора,
отличающиеся только одной клеткой, называются ацикличес-
ациклическими т-\-п—1 наборами однократного замещения.
Рассмотрим произвольное основное решение Х={х^). По
теореме (см. стр. 69) число Л/ отличных от нуля элементов Хц
удовлетворяет условию п sg N ?=; т -\- п—1. Остальные
т X п — TV элементы решения равны 0.
Построим ациклический т-\-п—1 набор Н такой, что
все отличные от пуля элементы x;j решения X расположены
в клетках этого набора.
Определение. Элементы х{, решения X, равные нулю
и расположенные в клетках ациклического т-\-п—1 набора
И, называются выбранными нулями.
Определение. Совокупность ненулевых элементов х^
основного решения X вместе с дополняющими их до ацикли-
ациклического т -)- п — 1 набора Н выбранными пулями называется
выбором.
Определение. Элементы ci} матрицы С, соответствую-
соответствующие элементам выбора Л', называются х-вью ранными.
Следовательно, выбор есть основное решение, в котором
из всех нулевых элементов х;/=^0 выделены те, которые до-
дополняют множество ненулевых элементов дг^-^О до ацикли-
ациклического т-\-п— 1 набора Н. Окончательно приходим к выводу,
что для нахождения хотя бы одного оптимального решения
достаточно рассмотреть всевозможные выборы.
§ 13. Оптимальный выбор
Методика определения оптимального решения заключается
в том, что, отправляясь от некоторого начального выбора, мы
переходим последовательно к другим выборам с меньшим зна-
значением скалярного произведения (СХ) и через конечное число
шагов приходим к оптимальному решению. Поэтому возникает
вопрос о построении первого выбора.
Рассмотрим следующий способ построения первого выбора.
Определяем элементы первой строки матрицы Х=(х^).
Для этого в первой строке матрицы С-=(с,-у)
меньший элемент. Пусть это будет
элемент
отыскиваем наи-
наиC\jx. Тогда
3*»
полагаем лг171 = min (аг; ?д). Если ax^>bjv отыскиваем в той
же строке второй наименьший элемент Cijt, удовлетворяющий
условию Cijt^Ss Ci/\, и полагаем Xiy2 = min (я, — л^д; bj2). Эти
шаги продолжаем, пока полностью не удовлетворим первому
п
уравнению «,= У\ х1.-. Если на некотором шаге этого про-
щему bjk, то, положив хук равным этому остатку х^к = Ь/к,
дополнительно полагаем следующее, соответствующее по вели-
величине, значение переменной Xijk + 1 = 0. После этого переходим
ко второй строке, третьей и т. д. При этом в столбцы, соот-
соответствующие уравнения которых полностью удовлетворены,
пуль не записывается.
Из построения следует, что полученное таким образом пер-
первое решение является выбором, ибо число отмеченных элемен-
элементов равно т-\-п—1 и среди них нет ни одной замкнутой
цепи.
Для пояснения рассмотрим следующий пример. Пусть тре-
требуется построить первое решение для транспортной задачи,
определяемой матрицей, пред-
Т а блица 3 ставленной в таблице 3.
В первой строке наимень-
наименьшим из чисел (8, 3, 5, 2) яв-
является число 2, поэтому при-
принимаем х14 = min A0; 15) =
= 10. Так как груз первого
пункта отправления полно-
полностью распределен, то пере-
переходим к распределению груза
второго пункта отправления.
во второй строке таблицы 3 отыскиваем наимень-
шсел D, 1, 6, 7). Число 1 есть наименьшее. Поэтому
л:,, = min A5; 10)=10. Так как в этом случае
во втором пункте отправления, равный
этого
из
Для
шее
полагаем
имеется
22
остаток
15—10 = 5 единицам, то отыскиваем во второй строке сле-
следующий наименьший элемент. Это будет число 4. Полагаем
x21 = minA5—10; 5) = 5. Учитывая, что потребность пер-
первого пункта назначения полностью удовлетворена, а остаток
во втором пункте равен 0, отыскиваем третий наименьший
элемент во второй строке. Таким элементом является число 6.
Поэтому полагаем xit---(). Теперь переходим к распределению
груза третьего пункта отправления. Для этого среди чисел
A, 9, 4, 3) третьей строки отыскиваем наименьшее. Так как
потребность первого пункта назначения полностью удовлетво-
удовлетворена, то число 1, стоящее на пересечении третьей строки
и первого столбца, в расчет не принимается. Поэтому отыски-
отыскиваем наименьшее из чисел (9, 4, 3). Число 3 наименьшее среди
них. Полагаем x34 = min B5, 15—10) = 5. После этого нахо-
находим в третьей строке следующее наименьшее число 4 и пола-
полагаем хаз = 20.
Легко убедиться, что полученное распределение есть реше-
решение. Кроме того, построенное решение является выбором.
В самом деле, число выбранных элементов равнот-|-я—1 =
== 3 —(— 4 — 1=6, и они не образуют между собою циклов.
Напротив, всякий не выбранный элемент х^, как легко
видеть, образует один и только один цикл с элементами
выбора.
В дальнейшем мы будем пользоваться изложенным спосо-
способом построения первого решения.
Пусть построен первый выбор — решение Х1 с набором //,.
Пусть соответствующее скалярное произведение (CXt) равно С,.
Оценим каждый элемент с(у, не входящий в Н1} посредством
выражения
04
где
,сп
, — суммы элементов соответственно нечетной
и четной иолуцепей единственной замкнутой цепи, образуемой
каждым элементом с,у с х-выбранными (оцениваемый элемент
с,-, принимается за первый в цепи Н). Отметим элемент с,-^,
которому соответствует наименьшая оценка 1™и\ и его замкну-
замкнутую цепь с х-выбрапными элементами. Построим второй
выбор Л'2, для чего передвинем наименьший элемент х,™"'
первого выбора из четной полуцепи в нечетную полуцепь.
При этом, если в четной полуцепи имеется несколько элемен-
элементов х1;-, равных наименьшему х™п, то, для определенности,
исключаем из набора /У, клетку ij с элементом л™, встре-
встречающуюся первой в четной полуцепн при обходе ее по часо-
часовой стрелке. Вместо исключенной из набора /У, клетки ij
вводим клетку ijv которой соответствует е,-^, и новый
элемент выбора X/ji = x?)in (заметим, что за счет передви-
передвижения элемента х™ по цепи в выборе Хг может оказаться
несколько нулевых элементов). Так как выбор Хг отличается
73
элемента cij^
,<0, ска-
от выбора Хг только изменением в цепи
то, если справедливо неравенство У] (с- ¦) —
лярное произведение (СХ2) будет меньше {СХХ) на величину
¦(. Л—^l-""™' Учитывая, что х™ может оказаться рав-
уч
ным нулю, мы приходим к выводу, что С, ^ С2. Только что
проведенное построение можно повторить и, отправляясь от
выбора Хг, построить выбор Хг и т. д. В результате обра-
образуется последовательность выборов Хх, X2, ..., Хк, ...
такая, что соответствующая последовательность значений
скалярных произведений С\ ^з~- С2 ;э= . . . ^-- Ск ;э= ... является
невозрастающей функцией номера выбора.
Выбор Xk с набором Нк называется оптимальным, если
каждый из элементов с,-_,-, не входящих в Нк, имеет неотри-
неотрицательную оценку Д^гО.
Так как для любого элемента cfj, не входящего в набор Нк,
справедливо неравенство 2(с</) — 2jcu^®' го "среход по-
W нч
средством однократных замещений к любому другому выбору
от выбора Xk, не может уменьшить значение скалярного
произведения по сравнению со значением скалярного произве-
произведения Ск, соответствующего выбору Хк*).
Теорема. Для всякой матрицы С=(с^) с веществен-
вещественными элементами при я(.^>0, hj^>0 последовательность
выборов Хх, Х2, ..., Хк, ... через конечное число шагов
заканчивается оптимальным выбором.
Доказательство.
/ случай. Если при переходе от выбора к выбору при
построении последовательности Хи Х2,
выборов не появляется х^=^0, то п х'"/
цепи, отлично от нуля. В этом случае значение скалярного
произведения с каждым шагом уменьшается. А так как при
конечных тип может быть только конечное число различных
наборов /У, на каждом из которых однозначно определяется
выбор, то бесконечного числа шагов быть не может.
// случай. Если при переходе от выбора к выбору в по-
последних могут появляться нулевые значения X/ •, то возникает
сомнение в конечности последовательности Хх, Х2, . . ., так как
в этом случае х™п = 0, и значение скалярного произведения
ни в одном из
переносимое по
*) Ниже будет показано, что
время и оптимальное решение,
оптимальный выбор есть в то же
74
не уменьшается. Однако сомнение полностью устраняется, если
наряду с исходной задачей транспортировки рассмотреть задачу
с той же матрицей С=(с/у), по с
ai =«,- + e,
К = ьп + ms,
/== 1, 2, ..., т,
y^l, 2, ..., (я —
где ? — достаточно малое положительное число. Назовем эту
вторую задачу s-задачей. Построим первые выборы Хх и Х\
для этих двух задач. Тогда в силу малости г наборы Н1 и
Н\ совпадут и в выборе Х\ не будет пулевых элементов
х*у=0. В самом деле, появление нулевых значений Хц в вы-
выборе в исходной задаче происходит в тех случаях, когда
существуют такие сочетания строк и столбцов, что имеют
место равенства
.2. «« =
.2.
Поэтому появление нулевых значений
в двух случаях:
i=iq
.It fl/ + 9S=
J=Jp
в задаче может быть
Выбирая ? отличным от корней уравнений, ш>|ражаемых усло-
условиями а) и б), мы исключаем возможность появления нулевых
элементов в выборе A'f. Так как матрица С=(с^) одна и
та же для обеих задач, то совпадают элементы Сц с наиболь-
наибольшей отрицательной оценкой, замкнутые цепи этих элементов
с элементами выборов А, и Х\, а также положение в набо-
наборах Н1 и Hi элементов х™" и аг//Ш1П, подлежащих переносу
по цепи. Переход от выбора А', к выбору Х2 в исходной
задаче является переходом от выбора Х\ к выбору Х^ для
?-задачн. В силу малости ? эти рассуждения справедливы на
любом шаге. Так как s-задача является задачей при отсутст-
отсутствии xi;- — Q, когда имеет место уменьшение скалярного произ-
произведения на каждом шаге, то для ?-задачи через конечное
75
число шагов мы придем к оптимальному выбору Л'|. В силу
совпадения матриц C=(c|V) и наборов Hk и Н\, выбор Xk
также является оптимальным.
Теорема доказана.
§ 14. Инвариантность последовательности выборов
эквивалентным преобразованиям матрицы стоимости
Определение оценок элементов связано с большим объемом
вычислений. Возникает задача определения таких простых
преобразований исходной матрицы С=(с-), которые, не меняя
последовательности выборов, значительно сокращают процесс
нахождения оптимального выбора.
Для этого введем понятие эквивалентного преобразования
матрицы.
Определение. Пусть задана матрица С==(с(.) и про-
произвольные числа г,; гг\ ...; rm; st, .чг, ..., sn. Назовем мат-
матрицу D = (di]) эквивалентной матрицей С=(с,-.), если она
получена из матрицы С по формуле D-= (с- -j-r,- —|— -S'y)-
Теорема. Последовательность выборов инвариантна
относительно эквивалентных преобразований матрицы.
Доказате л ь с т в о. 11реобразуем матрицу С в эквива-
эквивалентную ей матрицу D. Построим для матрицы С начальный
выбор Хх и, отправляясь от него, посредством однократных
замещений построим последовательность Л",, А, А, ...,
сходящуюся к оптимальному выбору Xk.
Отправляясь от того же самого выбора Аг1, построим по-
последовательность А",, Х[, Х'г, . . . для матрицы D, сходящуюся
к оптимальному выбору X'k. Легко видеть, что разность оце-
мок А,-у—\ц для любых двух элементов c,j и с,у, не входя-
входящих в выбор А",, равна нулю:
2 D-+и + Sj)
fcT
Последние две суммы равны по величине и противоположны
по знаку, так как всякое число г{ (пли Sj), содержащееся
в нечетной полуцепи, содержится и в четной пол у цепи.
Поскольку оценки элементов для матриц С и D совпадают,
76
то совпадают и элементы с наименьшей оценкой. Поэтому при
переходе от выбора Xt к следующему выбору как для мат-
матрицы С, так и для матрицы D выборы Хо и Х[ совпадают.
Проведенные рассуждения остаются справедливыми на любом
шаге. Эго означает, что последовательность А',. А, ..., Xk
выборов не изменяется при эквивалентных преобразованиях
матрицы. Теорема доказана.
Очевидно, справедливость утверждения не нарушается при
неоднократном применении эквивалентных преобразований
к матрице С.
Так как элементы любого выбора не образуют замкнутых
цепей между собою, то на каждом шаге можно построить
эквивалентное преобразование, которое обращает х-выбранные
элементы и нуль. Для этого достаточно, например, к элемен-
элементам каждого столбца (строки) прибавить число, противопо-
противоположное по знаку алгебраической сумме числа, прибавленного
к строке (столбцу), и величины jt-выбранного элемента, обра-
обращаемого в пуль.
Матрица с нулевыми л'-выбранпыми элементами обладает
тем свойством, что оценка любого из ее элементов, не являю-
являющегося х-ныбранным, равна самому элементу. Поэтому не
требуется производить огромные расчеты для определения
оценок всех элементов. Для построения следующего выбора
достаточно указать наибольший отрицательный элемент
(по абсолютному значению). Если же все элементы преобразован-
преобразованной матрицы оказываются неотрицательными при нулевых
.v-вибрапных элементах, то последний выбор и есть оптималь-
оптимальный. Из инвариантное тп последовательности матриц следует,
что оптимальный выбор ее i ь в то же время и оптимальное
решение. 15 самом деле. Оптимальный выбор с эквивалентно
преобразованной матрицей, у коюрой .v-иыбранные элементы
равны нулю, обладает тем свойством, что скалярное произве-
произведение для него меньше (или, в крайнем случае, равно) ска-
скалярного пронзнедеппя любого из решений. Поэтому найденный
нами оптимальный выбор есть оптимальное решение.
§ 15. Алгоритм нахождения оптимального решения
I. Условия задачи записываются в виде таблицы.
II. Определяем первый выбор.
III. Обращаем х-выбранные элементы в нули. Если при этом
остальные элементы преобразованной таблицы оказываются
неотрицательными, го первый выбор и является оптимальным.
77
IV. Если после обращения х-выбранных элементов в нули
в таблице имеются отрицательные числа, то находим наиболь-
наибольший отрицательный элемент (по абсолютному знамению).
V. Образуем замкнутую цепь наибольшего отрицательного
элемента с обращенными в нуль х-выбранными элементами
и строим второй выбор, передвигая по цепи число х.;1, равное
наименьшему в четной полуцепи.
VI. Так как наибольший отрицательный элемент стал
х-выбранным, то обращаем его в нуль, но так, чтобы осталь-
остальные х-выбраниые элементы, соответствующие новому выбору,
оставались также равными нулю.
С,
Cf/>,)- начальная стоимость
А, С(Л7}~ конечная стоимость
IN.4 4
[>ис. 20.
VII. Эти шаги повторяем до тех пор, пока не придем
к выбору, для которого в преобразованной таблице все
х-выбранные элементы равны нулю, а остальные -неотрица-
-неотрицательные. Этот последний выбор и будет оптимальным реше-
решением.
VIII. Для подсчета стоимости транспортировки, соот-
соответствующей оптимальному решению, следует соединить в одну
таблицу первоначальную матрицу стоимости п последнее
решение. Сумма парных произведений чисел, стоящих в клет-
клетках таблицы, определяет значении стоимости перевозок.
Для наглядности процесса нахождения оптимального реше-
решения приведем его геометрическую интерпретацию (рис. 20).
Отложим по горизонтальной оси номера решений, а по вер-
вертикальной оси соответствующие значения стоимости. Вначале,
построив первое решение, мы находим одну из точек А1.
Обращение х-выбранпых элементов в нуль приводит нас па гори-
горизонтальную ось в точку.4'. Если для эти тчкп преобразован-
78
ная таблица не имеет отрицательных элементов, то решение,
соответствующее точке Alt и есть оптимальное. Если этим
свойством преобразованная таблица не обладает, находим
точку А2 и вновь возвращаемся на оси в точку А'2 и иссле-
исследуем, не достигли ли мы оптимального решения. Если нет,
определяем точку А3 и т. д.
Через конечное число шагов мы обязательно достигнем
последней точки, котрой и соответствует оптимальное реше-
решение. Мы получим ломаную стоимости, как изображено на рис. 20.
Как видно из рисунка, с каждым шагом значение стоимости
уменьшается (во всяком случае не возрастет).
Т а б л и u a 4
+ 3
ю
75
25
1
г
3
5
^5
1^
10
, 2
9^^
zo
J
5 ^^
^20
/5
(U^0
®/5
-5y^
Продолжим решение транспортной задачи, поставленной
на cip. 72. Первый выбор для нее представляется таблицей 4.
Обращаем х-выбранные элементы в пули. Для этого из эле-
элементов первого столбца матрицы стоимости вычтем 4, из
элементов второго столбца — вычтем 1. В результате х-вы-
бранные элементы, стоящие на пересечении второй строки
с первым и вторым столбцами, обратятся в нули. Из элемен-
элементов третьего столбца вычтем 6, тогда х-выбранный элемент,
стоящий на пересечении второй строки с третьим столбцом,
также обратится в нуль, а элемент матрицы стоимости, стоя-
стоящий на пересечении третьей строки и третьего столбца,
примет значение, равное D — ()=--—2). Прибавим к элементам
третьей строки матрицы стоимости число 2, а из элементов
четвертого столбца вычтем число 5. Тогда элементы, стоящие
на пересечении третьей строки с третьим и четвертым столб-
столбцами, обратятся в нули.
Наконец, остается обратить в нуль х-выбранпый элемент,
стоящий на пересечении первой строки и четвертого столбца.
Для этого к элементам первой строки нужно прибавить число 3.
В результате такого эквивалентного преобразования матрицы
стоимости таблица 4 примет вид таблицы 5.
79
Как видно, в таблице 5 имеется отрицательный элемент (—1).
Поэтому мы не можем быть уверены, что первый выбор явля-
является оптимальным. Так как в данном примере имеется один
Т а б л и и а о
/У ¦
15
25
3
—
gJ
Щ
5
—
5
0,
10
Ю
- ю
20'"
2. ¦ '"'
@^io
2
15
отрицательный элемент, то он же является и наибольшим
(по абсолютной пелпчипе).
Образуем замкнутую цепь этого отрицательного элемента
с х-выбранными и построим второй выбор, как показано
Т а б липр fi
A- 5
a. ^i I Г
10
15
го
ю
2_q_
\2
9^L'^-^ro\''p
м
\ro^
+ ;
в таблице 6. Для этого иередтшем из четной полуцепи в не-
нечетную число единиц груза, являющееся наименьшим в четной
полуцепи.
Т а б л и ц а 7
10
15
25
!
г
3
5
7
*^
10
'°/^
20
з
5^
{^15
15
2^^
Так как число — I стало х-выбрапным, го его надо обра-
обратить в нуль, для чего снопа подвергнем матрицу стоимости
тождественным преобразованиям. Прибавим к элементам пер-
80
вого столбца в таблице 6 число, равное 1. В результате
получим таблицу 7, в которой пет ни одного отрицательного
элемента, а все х-внбраннне элементы равны нулю.
Поэтому выбор, представленный в таблице 7, является
оптимальным решением. Соединим в одну таблицу 8 исходную
Т а б л и ц а 8
10
15
25
1
J
5
i
10
i'
|?
20
,7
15
4
матрицу стоимости ii оптимальное решение. Стоимость пере-
перевозок, соответствующая этому плану, составляет С== 2-10 —[—
-f-5-б-у- Ю-1 -[-5-3-J-4-15-}- 1 -5 — 140 единиц стоимости.
Сглрппшрмптво N-t
Строительство /v-J
15
Строительство /V-/
. _
Рис. 21.
Согласно этому плану перевозку нужно организовать сле-
следующим образом (рис. 21). Весь груз первого пункта отправ-
отправления транспортируется к четвертому потребителю; второй
пункт отправления обеспечивает 10 единицами груза второго
потребителя и 5—¦ третьего; с третьего пункта отправления
5 единиц груза транспортируется к первому потребителю,
81
15 — к третьему, а остальные 5 единиц груза доставляются
четвертому потребителю. При таком плане стоимость перево-
перевозок (при всех прочих равных условиях) будет минимальна.
Рассмотрим более сложный пример.
Пример. Найти оптимальный план перевозки однородного
груза из четырех пунктов отправления в тесть пунктов назна-
назначения при условиях, определяемых таблицей 9. В этой таблице
a,-, bj выражены в тысячах тонн, а с,-/—в тысячах рублей.
Т а б л II ц а 9
5
7
в
г
2^^
/^"
2^
4
4^
3.'
1^
5
3 ^
2 /-"
3
3 ^"
7
в
3 /
Перепишем еще раз исходную таблицу, внесем в нижние
полуклетки числа начального выбора и представим весь про-
процесс получения оптимального решения в виде последователь-
последовательности таблиц 9а, б, в, г, д, с.
Т а б л 11 ц а 9 а
Первый
выбор
С,=75
©/
+/ Обращаем
х-выбранные
~~ элементы
-/ таблицы в О
Квадратиком
отмечен эле-
элемент, кото-
врешение
О
Щ7
+4 +4
±z
Т а б л II ц а 9 б
По цепи перено-
переносим 5единиц.
Стоимость
понижается
на ВО единиц
82
Таблица 9в
Заштрихован элемент, который исключается из решения
Второй
выбор
Сг=55
О
-4 ..
Первая цепь
Ла цели перено-
переносим О единиц.
Стоимость
остается той же
-4
ешир
Cf-55
У 2
у у
/
-гу
(ру
У о
0 /
У
'РУ
У
А у
4 /
(у
®у
У 5
®у
/_ 3
3 /
у
-1 /
о у
2 /
®у
у р
1 /
У
У
У 5
¦0)
У
®
0
1
-г
Втирая цепь
Четряртый
Таблица 9 г
По первой цепи пере*
носим 2, по второй!.
Стоимость понижа-
понижается на 2-2+2 1 ~
= Б единиц
Таблица 9 д
По цепи переме-
перемещаем единицу.
Стоимость пони-
понижается на /¦? =
= 7 стоимости
Пятый
еыйар
Таблица 9е
Оптимальное
решение
Соединим вместе первоначальную
оптимальное решение (таблица 10).
таблицу стоимости и
5
• 7
в
г /
з /
у
0)~7
у Z
У
(/<)/
/ 3
5 /
($у
у 1
5
!/ У
/
/
¦} /
^ у
/
W
У 5
3
(jy
У
оу
У1
3у
г
4 у
cry
У 2
4/
зу
у
5 у
®У
/5
®у
/ 1
в у
Последняя таблица укапывает, как нужно организовать
перевозки, чтобы обеспечить наименьшие расходы. Против
первого варианта ошп.мальный вариант обеспечивает снижение
стоимости перевозок па 27 тыс. рублей, гак как расходы на
перевозки по первому варианту составляют 75 тыс. рублей,
а по оптимальному только 48 тыс. руб.
Интересно отметить, чш таблица с оптимальным вариантом
E-й выбор) указывает не одно оптимальное решение, а все
решении с той же стоимостью.
Действительно, в этой таблице имеются нулевые элементы,
не отмеченные кружком. От меч им их звездочкой. Каждый из
этих элементов образует замкнутую цепь с элементами решения.
Производя однократные замещения по тем же правилам,
можно получить другие решения при той же стоимости.
Это позволяет принять за оптимальное решение, например,
такое, как представлено в таблице 11. Стоимость, соответ-
соответствующая этому плану перевозок, также равна
С= 1 -2-|-4-3-]-4. 1 -J- 1 -5-j- 1 • 1 -|- 1 -2-{- 1 -2 + 5- 1 +
Легко видеть, что в этом случае каждая замкнутая цепь, со-
состоящая только из нулевых элементов, обладает тем свойством,
что у соответствующей замкнутой цепи исходной таблицы
суммы стоимостей четной и нечетной полуцепей равны и это
позволяет переносить по цепи х'Я.1" без изменения обшей сто-
стоимости. В ряде случае» определение всех оптимальных решений
оказывается очень полезным. Как будет рассмотрено дальше,
применяя к множеству оптимальных решений правила пахожде-
84
иия оптимального варианта перевозок по времени, можно ука-
указать план перевозок, реализация ко троп) требует наименьшего
времени.
Наконец, скажем несколько слои о нахождении замкнутой
цепи, образуемой наибольшим офнца К'льным элементом
с х-выбраннымп элементами. Ксли т и п небольшие, то цепи
видны непосредственно, как это и имело место для рассмот-
рассмотренных выше примеров. Пслп же т и п сравнительно велики,
К) нахождение замкнутой цепи проще всего устанавливается
следующим образом. Вычеркиваются строки п столбцы, содер-
содержащие по одному отмеченному нулю (так как для образования
цепи надо пмсчь в столбце или строке не менее двух нулей);
после первого вычеркивания во всей таблице делается второе
и т. д., пока не придем к положению, из которого сразу видна
замкнутая цепь.
Так как подробное решение примера с большой таблицей
заняло бы много места, то в данной работе ограничимся рас-
рассмотрением случая, при котором необходимо найти замкнутую
Т л 6 i и и л 1 1
¦0)
у ^.^
' -^ 7
1 ,.--
,и) --^¦?
1 ^
°/^
цепь. Эта ситуация представлена в таблице 12. Вначале вы-
вычеркиваем все сю.мбцы, содержащие но одному пулю (конечно,
за исключением столбца, в котором находится наибольший
отрицательный элемент). Далее рассматриваем все строки и
вычеркиваем те, в которых оаалось по одному нулю. Снова
просматриваем столбцы и делаем то же самое.
Теперь для носiроения замкнутом цепи оаалось соединить
оставшиеся, начиная с отршипе.тьнот числа и обходя пулевые
элементы, например, по часовой стрелке.
Мы рассмотрели .методику решения транспортных задач по
критерию стоимости при vctorimi, что 2Я'>==2^/' ^
этом случае количество груза во всех пунктах отправления
равно количеству погребною груза для всех пункте назна-
назначения.
«5
Если 2 я/-
/-I )=
с потребностью Ьп{,
, то вводим фиктивный пункт назначения
п
' 2 Ь,- и с0 стоимостью перв-
первую 1
y
возки груза в этот пункт с,- Hf]=0 для г=1, 2, ..., т.
Т а б .1 II и ,1 VI
1 2 3 4 5 В 7 8 9 Ю 11 /г 13 14 15
О
О
О
О
»
я.
8:
О
О
8
О
О
¦я
О
&
О
я
О
О
ж
1
-9
О
Т а 6 л и
ц л
70
40
50
го
30
40
(Р^о
(^<0
30
{5^0
la; -180. Ibj = /00- fy = 80
Пример. Пусть в четырех хранилищах имеется со-
соответственно 70, 40, 50, 20 тонн горючего. Требуется сплани-
спланировать перевозки горючего к трем потребителям так, чтобы
затраты на транспортировку были минимальны. Пусть условия
задачи определяются таблицей 13. В этом случае построение
первого решения целесообразно вести по столбцам. Это реше-
решение отмечено кружками в таблице 14.
Легко проверить, ччо решение, представленное в таблице 14,
является оптимальным. Согласно эюму решению к первому
86
потребителю надо подвезти 10 тонн из первого и 20 тонн
из четвертого хранилища, ко второму потребителю 30 тонн из
первого и 10 тонн из второго хранилища, к третьему потребителю
30 тонн из второго хранилища, при этом в первом хранилище
еще остается 30 тонн горючего, запасы третьего хранилища
в данных условиях использовать нецелесообразно.
Т а б л и ц а 14
70
40
50
20
30
30
Щ^'ю l^l> i^
0 ^^
80
V-"^ 30
°^
°^
Задачи норного и шор.го типа, методы решения которых
описаны выше, связаны с организацией перевозок с точки
зрения экономии средств на последние. Что касается задач
третьего типа, то, как говорилось выше, они связаны с орга-
организацией перевозок в кратчайшие сроки. Метод решения
такого типа задач изложим в следующей главе.
Т а б л и ц a lo
1
г
3
4
S
6
7
в
а
33
18
г
38
14
23
31
38
3
1
18
18
15
4
9
7
и
9
12
7
и
13
3
го
в
7
w
17
3
12
Г
3
27
15
17
11
3
15
14
1
11
4
4
7
7
3
2
13
1
9
9
9
5
ь
18
6
4
7
13
7
7
2
3
8
в
12
1
4
1
14
2
3
16
13
13
7
11
12
3
4
11
4
в
W
14
20
8
30
9
15
8 4
6
7
9
IS
S
1
9
' 8
11
з
4
13
7
7
7
6
to
д
3
14
11
5
3
4
;/
8
4
и
20
17
г
17
19
1
5
14
7
19
12
8
19
13
16
18
19
и
г
е
17
Id
и
3
6
г
3
20
13
4
3
/
14
?
6
1
3
7
3
14
7
15
3
Изложенный алгоритм решения транспортной задачи по
критерию стоимости может быть представлен как однообраз-
однообразный процесс арифметических и логических операций. Такой
процесс легко реализуется на электронной вычислительной
матине. На рис. 22 приведена упрощенная блок-схема реше-
решения задачи. В соответствии с этой блок-схемой составлена
программа решения задачи на машине «Стрела».
87
Для матриц порядка ту п <С 'ГH0 время решения задачи
не превышаете—10 мину г; для ма! риц порядка туп<
Построение начального
выбора
Обращение х-выбраиных эле-
элементов матрицы стоимости
в нули (преобразование
матрицы)
Отыскание в преобразован-
преобразованной матрице наибольшего по
абсолютной величине отри-
ца гелыюго элемента
Контроль окончания решения:
проверка наличия отрицатель-
отрицательных элементом в преобразо-
преобразованной матрице
Отыскание замкнутой пси»,
образуемой наибольшим по
абсолютной величине отрица-
отрицательным элементом и х вы-
выбранными элементами
Построение нового выбора
Вычисление стоимости пере-
перевозок но оптимальному
плану
Выдача оптимального плана
перевозок и соответствующей
стоимости
Останов машины
Рис. 'П.
при решении задачи может потребоваться до 25—40 минут;
для матриц порядка т X п в несколько тысяч для решения
задачи на машине «Стрела» требуется до 8—10 часов.
Так, на машине (Стрела» была решена следующая транс-
транспортная задача.
88
Требуется из девяти пунктов отправления перевезти груз
к четырнадцати пунктам назначения (таблица 15). Начальный
выбор, полученный на машине, представлен в таблице 16.
г
2
3
4
5
fi
7
8
3
33
18
2
38
j/,
Z3
31
зв
3
I
18
18
г
13
13
3
Zl
21
7
Z
5
T
5
18
13
5
\ 6 л
Б
12
/;.'
и ц a It
/ д
8
3
30
18
IZ
9
15
6
9
ю
9
8
0
1
ii
го
и
9
,2
8
8
13
и
t
11
14
7
7
Конечный выбор, соответствующий оптимальному решению,
изображен в таблице 17.
Легко подсчитать, что неличина стоимости, соответствую-
соответствующая начальному выбору, имеет значение, равное С = 971,
а для оптимального С=703.
Т а б л и и а 17
4 5 В ? 8
W t) t2 13 J4
1
г
3
s
в
7
3
S
ж
33
18
г
38
16
гз
31
38
3
18
Z
11
1
1
3
13
13
2!
ZO
1
7
7
18
18
1Z
12
11
11
30
30
?5
8
7
9
9
го
6
14
8
8
/;
//
7
7
Время решения этого примера (в один просчет) составило
около одной минуты.
Нремя решения другой транспортной задачи с матрицей
стоимости т X « = 30 X 38 (при двойном просчете) составило
37 минут.
ГЛАВА IV
РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ ПО КРИТЕРИЮ
ВРЕМЕНИ
При составлении плана мереншок в ряде практически важ-
важных случаев крайне необходима экономия примени. Например,
при транспортировке скоропортящихся продуктов необходима
доставка их в пункты назначения п минимально возможное
время. Во время хлебоуборочной кампании очень важным фак-
фактором является наиболее быстрая вывозка зерна па заготови-
заготовительные пункты.
Задача такого типа является задачей транспортировки по
критерию времени. Ниже рассматривается олин из алгоритмов
решения транспортной задачи по кршерию времени.
§ 16. Постановка и решение задачи
Пусть имеется т пунктов отправления однородного груза
и п пунктов назначения. Обозначим через «,, аг, . . .
...,а(, ..., ат количество единиц груза, находящегося в пер-
первом, втором, ...,/-м, ..., яг-м пунктах отправления, а через
bv b2, ..., b-, ..., bn — количество единиц груза, которое
должно быть доставлено в каждый из п пунктов назначения.
Пусть tf, есть время (в сутках, часах), потребное па перевозку
груза из /-го пункта отправления в у-й пункт назначения,
а Хц — количество единиц груза, которое мы планируем пере-
перевезти из /-го пункта отправления в у-й пункт назначения.
Требуется найти оптимальный план перевозок, т. е. такие
неотрицательные числа х(-, при которых время доставки всех
необходимых грузов к пунктам назначения было бы минимально.
Математическая формулировка этой задачи сводится к сле-
следующему.
90
Задана система линейных алгебраических уравнений:
|>,у = «/ A=\, 2, ..., т),
причем числа а- и Ь, удовлетворяют условию
B7)
Пусть, кроме того, задана матрица времен 7=(//у). Каждому
неотрицательному решению А'=(х/у) системы уравнений B7),
т. е. плану перевозок, соответствует определенная матрица
•¦к ¦!*
Tx=(t,j), элементы которой равны Uj^tij, если л:;у^>0,
^/у- = 0, если Хц = 0. Обозначим через /™ах наибольший эле-
элемент матрицы I х ¦
Требуется определить такое неотрицательное решение Хппг,
для которого '"vJX будет наименьшим среди всех txa%, соот-
отп
ветствуюшнх различным неотрицательным решениям X. Условия
этой задачи удобно представить в виде таблицы 18.
Т а Г) л и ц а 18
а,
аг
Hi
ат
4
4
Эта задача, как легко показать, не решается с помощью
алгоритма, описанного для транспортной задачи по критерию
стоимости.
Так, например, решение, для которого линейная форма
С = 2'гл:/7 Достигает минимального значения, как правило,
не является оптимальным по времени. Для примера, заданного
таблицей 19 и изображенного на рис. 21, оптимальное решение
91
по минимуму линейной формулы C = ^iti]-xi)- представ-
представляется таблицей 20. Из этой таблицы видно, что несь груз
будет доставлен в пункты назначения только через шесть
Т ,] <"> л II и a l'l
ю
15
25
5
8^
4^
10
20
15
^^
суток. С другой стороны, варианту перевозок, представлен-
представленному в таблице 21, соответствует несколько большее значение
Т а б л II ц а 20
а,
\4
10
15
25
<?,
1
5
10
20
Г
'''^15
2
/-
7
3
15
ЧЮ^ 351 4/5+ 1-5= МО
Т а б л н ц а "Л
10
!5
25
5
8^
10
3/^
20
5^^
{^20
15
7^^
*..?•?+ 4-го'+
л-5 =
линейной формы, по перевозка грузов к пунктам назначения
выполняется за четверо суюк.
При перевозке скоропортящихся продуктов расходы на до-
дополнительный пробег вагонов (автомашин) окупаются сохране-
сохранением качества тысяч тонн продуктов питания, предназначенного
для населения.
Доказательство описываемого ниже .метода решения сле-
следует из общей теории линейного npoi раммпровапня, изложен-
изложенной в главе II.
92
Описание метода рассмотрим на решении задачи, заданной
таблицей 22. Из этой таблицы следует, чго требуется пере-
перевезти 125 единиц груза, находящегося в шести пунктах
отправления, в семь пунктов назначения. Пусть числа этой
таблицы означают время в часах, необходимое для перевозки
груза соответственно из пункта отравления в пункты назна-
назначения. Так, например, число 31, стоящее на пересечении
четвертой строки н четвертого столбца, показывает, что время
на перевозку груза из четвертого пункта отправления к чет-
четвертому пункту назначения составляет 31 час. Требуется найти
оптимальный по времени план перевозок.
а о л и ц а 11
Ньппенаписанную таблицу (будем называть ее малой) пред-
представим в виде большой таблицы (таблица 23).
Верхняя строка содержит индексы переменных xi;- от 11
до 67, а нижняя — значения itj, содержащиеся в соответствую-
соответствующих клетках ij. Например, пара чисел 43 в верхней строке
означает место переменной xls, а соответствующее этой пере-
переменной значение времени t%i есть 39; поэтому 43 и 39 нахо-
находятся в одной колонке.
Вся таблица разделена на полосы. Число полос равно
числу пунктов отправления или, что то же, — числу строк в
исходной таблице. Кроме того, таблица разделена горизонталью,
так что в верхней полуполосе шесть строк — число строк исход-
исходной таблицы, а в нижней — семь, число столбцов ее. В верхней
полуполосе прогни каждого числа написано по семи минусов
в соответствующей вертикальной полоске. Так, против 30 ми-
минусы написаны в четвертой полоске. Если посмотреть на
исходную таблицу, то увидим, что такая запись означает
93
S
Тч
as
S3
fea
U
Si
sr
"^
$
is
SQ
-
и
II
s§
II
SJ
и
i
?a
и
II
I
1
1
1
I
1
II
1
1
I
I
T
1
1
1
1
1
1
1
11
1
1
1
1
1
1
и
1
._
1
1
1
1
I
11
1
1
1
1
I
1
11
1
1
1
1
—
I
—
1
11
So
:*
So
^
^
EC-,
Ж
to
1
^.
5o
t\
^_
s_
выражение остатка груза в четвертом пункте отправления:
Подобно этому в нижней полосе положение минусов в каждой
строке выражает значение недостатка груза в пунктах назна-
назначения. Так, расположение минусов против 27 означает, что
недостаток груза и пункте назначения, соответствующем чет-
четвертой колонке, ранен
27 - х.
Л*2 4 *31
X,
Иначе говоря, расположение минусов в таблице соответствует
уравнениям, выражающим условия задачи.
Построим первое решение, используя способ, который при-
применялся в главе III. 15 единиц первого пункта отправления
распределим между пунктами назначения с наименьшим време-
временем пробега; 7 единиц второго пункта отправления — между
не удовлетворенными еще пунктами назначения с наименьшим
временем пробега и т. д. Это дает нам первое решение (вооб-
(вообще говоря, еще не оптимальное), представленное таблицей 24.
Т а 6 л и ц а 24
Как ьидим, элементарное построение привело к решению,
реализация которого требует 28 часов на перевозку грузов.
Это позволяет нам в дальнейшем исключить из рассмотрения
клетки с /,-;Х>-28, что и сделано в приведенной таблице.
Для построения следующего варианта решения, реализация
которого требовала бы менее 28 часов, обратимся к большой
таблице. Построение первого выбора применительно к этой
таблице происходит так: в нижней строке значений t(j оты-
отыскиваем наименьшее из чисел в первой полосе. Это — число 7,
соответствующее колонке 14, т. е. переменной х]4. Просматри-
Просматривая эту колонку, убеждаемся, что xvi можем положить равным
95
15, так как запас груза составляет 15 единиц, а потреб-
потребность— 27. Это позволяет записать переменную х14 слева от
равенства в первой строке, а знак минус ма пересечении пер-
первой строки и колонки 14 опустить. Что касается второго
минуса этой колонки, стоящего против 27, то его также
нужно опустить, а из строки, соответствующей числу 27, вы-
вычесть строку, соответствующую числу 15.
В первой и десятой строках н первой полосе произошли
изменения. Эти изменения имеют вид:
Переходим ко второй строке и мторой полосе. Отыскиваем
наименьшее из чисел t^ второй полосы. Эм> число (i, соот-
соответствующее переменной х26. Пробегая колонку по вертикали,
выбираем наименьшее из двух чисел, стоящих слева против
минусов этой колонки. Это число 5. Записываем слева от
равенства против 5 переменную xtt, опуская минус, стоящий
на пересечении этой строки и колонки 26. Минус опускаем
также на пересечении второй строки и колонки 26, а из вто-
второй строки, соответствующей числу 7, вычитаем строку,
соответствующую числу 5. Во второй строке остается число 2.
Это означает, что груз второго пункта отправления еще не
распределен между пунктами назначения. Поэтому во второй
полосе в строке значений f-. отыскиваем следующее по вели-
величине число. Это число 7, стоящее в колонке переменной x2i.
Пробегая по колонке, находим наименьшее из чисел слева
против минусов колонки B0, 2). Опускаем минусы и колонке 21,
записываем слева от равенства против 2 переменную х21 и
вычитаем из седьмой строки вторую. Этим заканчиваем рас-
распределение единиц второй строки. Этот процесс продолжаем
до распределения единиц шестой строки. В результате полу-
получаем первое решение, совпадающее с решением, записанным
в таблице 24. Большая таблица теперь преобразовалась
в таблицу 25.
В правильности решения убеждаемся отсутствием «-(-»
и «—» в одной из строк. В этой строке, в случае отсут-
отсутствия ошибок в распределении, должны быть только нули.
Такой строкой в данном примере оказалась последняя. (В силу
условия
2
°ДНО из уравнений системы B7) должно
быть следствием остальных.)
?ч
из
tx
999
$
ч^
ЕЯ
7ч~
?
О-,
5?
if3
-Э-
j?.
-Р^
"Я?
¦X'l
гч
S§
^-,
==-
-- -
\<с
т
;-|
I
У^
1
1
х \
+
_^
1
1
i
=
Si
—»-
-R'
+x
4-
4-
+^
+
4-
44-
+
4-
1
'ST
1
1
: i
i
i
II
1С
+
+v
+_
4-
4-
^+?
4^
4-
+
1
^o
1
1
1
Щ.
'";
i
i
¦C
1
1
\^
i.
1
1;
1
,v
4-х
+
~4-;
I-
"§"
J_
I
S\C\
1
1-
„:
i
к
-t-
4-
4-
1
Й5
f-
[^
1
Xv
1
.\-\^
-"-¦'
^ ,\
1
—
1
1
r
_
4-
rP
4-
.Ф,
4-
4-
if
1^
1
_i_
i
i
'^
i
I
g.x
1
1
M;
4-
+
+
t4
1
$xx'
'-XX
XXV
~?
xt
I
xVv
X \
x\
II
S3
?
s^
Rj
1
i
В таблице колонки, соответствующие основным пере-
переменным, обозначены прямой штриховкой, а колонки, для
которых соответствующие /,;.^>28,—косой. Последние из
дальнейшего рассмотрения исключаем. Таблица 25 указывает
пути построения лучшего варианта но сравнению с первым.
В самом деле, нам желательно найги такое решение, в кото-
котором бы переменная, стоящая в той же колонке, что и /^. = 28,
т. е. xi7, равнялась бы нулю. Но шестая строка в этой таб-
таблице показывает, что уменьшение значения переменной х^
может быть получено за счет увеличения или хй1, или xih.
Т а о л н ц а 26
Х„
1»,
':¦?
.гн;
г„
х\,
ха
хм
•Г„
х,г
= /.5
= 2
= 7
-ZS
-12
= .Ч
-и
=и
=11
-12
=г
-5
а
-
•+
/Г
-
+
13
/¦>
Ф
if
-¦
-
+
17
-
-
-
+
+
1"
С/
0
-
+
-
13
-
+
-
+
10
<•¦'>
'-
-
,;7
+
-
г
—
-
-
+
-
-
17
+
+
-
-
У,
+
-
-
22
+
+
+
-
-
-
1Б
г, 7
44)
61
@
63
®
65
-
0
-
+
0
гз
Поскольку неременной х61 ^„••••^•^i..J^. .„,¦
ной х„ /й5 = 23, го произведем уменьшение х„
соответствует /gl=15, а перемен-
личения хв1. Пробегая по колонке 01, находим, что наимень-
наименьшим числом, стоящим с левой стороны таблицы против «—»
колонки 61, является значение х67 = 5.
Теперь произведем преобразование последней таблицы сле-
следующим образом. Исключим колонки с косой штриховкой и
колонку, соответствующую переменной х67 (или, что то же,—
числу tij, равному 28). Вместо хв7 напишем хв1. Далее, из
строк с минусами в колонке 61 вычтем строку, соответствую-
соответствующую переменной хб1, а к строкам с плюсами в колонке 61
прибавим строку, соответствующую той же переменной, после
чего в колонке 61 все '¦ — - и « -\- ~> исчезнут.
В результате получим таблицу 26. Из этой таблицы сле-
следует, что нами построено второе решение, реализация кото-
которого требует значительно меньше времени: не 28 часов,
а только 21. (Заметим, что если бы обращение переменной
хв, в 0 мы начали производить не за счет увеличения хв1,
а за счет увеличения x6S, то был бы построен вариант реше-
решения с максимальным временем = /es —23. После этого, вы-
вычеркивая все колонки с /(у^>23, нам нужно было бы сделать
еще шаг для построения третьего решения с максимумом t^ = 21.)
Отметим переменные, изменение которых привело ко вто-
второму решению:
образовали
хв
х)
в7, х)Ь,
замкнутую цепь
„, х31, х1Ь, хв1. Эти переменные
(таблица 27). Занумеруем клетки
Т а б л и ц а 27
с переменными, образовавшими цепь, принимая клетку с пере-
переменной хв7 (подлежащей исключению) за первую. Эта цепь
обладает тем свойством, что н ее нечетных клетках находятся
обязательно х-иыбрапиые элементы, а в четных—значения
t..sc:t"jK, где ^//к — значение /,у, подлежащее исключению
(в данном случае /К = 28). Назовем такую цепь разгрузоч-
разгрузочной. После нахождения разгрузочной цепи для образования
нового решения передвигаем по цепи количество единиц груза,
равное минимальному из них в нечетной полуцепи. Это построе-
построение на малой таблице приводит нас ко второму решению,
совпадающему со вторым решением, построенным на большой
таблице. Исключим из дальнейшего рассмотрения колонки
(клетки) со значениями i{j >21. В результате получаем малую
таблицу 28 и большую таблицу 26 (считая колонки 41, 55,
65 вычеркнутыми). Спрашивается: имеется ли более оптималь-
оптимальное решение, т. е. решение, реализация которого требует
менее 21 часа? Для ответа на поставленный вопрос обращаемся
к таблице 26. В строке значений t.j отыскиваем наиболь-
наибольшее— 21. Этому значению /а1 = 21 соответствует переменная
у
jrA, в строке которой находятся только «-]-». Отсутствие
99
«—» означает невозможность уменьшить значение .v34 за
счет какой-либо переменной. Вывести х31, а следовательно, и
освободиться от /31 = 21 не преде тавляекя возможным. Таким
образом, полученный последний вариант является оптимальным
по времени. Его реализации, как уже сказано выше, требует
21 часа. В малой таблице 28 в этом случае пи представляется
возможным построить разгрузочную цепь.
Для облегчения уяснения метода нахождения оптимального
варианта по времени мы пользовались большими и малыми
таблицами. В действительности при решении таких задач
Т а 6 л и ц а 28
С=171БК
требуется одна или большая, или малая кн'лнца, исполненная
в карандаше. Переход от наршппа к варианту совершается на
одной таблице посредством карандаша и резппкн.
Правила нахождения оптимального варианта по времени при
пользовании малой таблицей сводятся к следующему:
1. Записываем условие задачи в малой таблице.
2. Находим первое решение (например, указанным выше
способом).
3. Определяем г1//"'1", соответствующий этому решению.
4. Зачеркиваем в таблице все клетки с /,-,О> /,/' '*.
5. Исследуем /,,m'lx па наличие /'нагрузочных цепей
с оставшимися элементами в таблице.
6. При наличии разгрузочных цепей строим повое решение.
7. Если не представляется возможным полностью разгру-
разгрузить клетку, соответствующую /,;'"'х (обратить соответствую-
соответствующее
в 0), то решение с /,-/т
является оптимальным.
8. При полной разгрузке клетки с 7//nJX находим /j/"" во
вновь полученном решении.
100
Мы выполнили псрш,п'1 шаг па пути к получению опти-
оптимального решении. Если при этом не получено оптимальное
решение, то надо выполнить второй шаг, применяя вновь
правила из пункта 4.
Для получения оптимального решения необходимо будет
совершить конечное число шагов.
Единственная трудность при пользовании этими прави-
правилами заключается в выявлении разгрузочных цепей. В этом
отношении использование большой таблицы, правила преобра-
преобразования которой описаны достаточно подробно выше, дает
возможность получить оптимальное решение без особого труда.
Можно принести и другие приемы решения этой задачи.
При малых т и я такие задачи могут быть решены
вручную. При больших т и п так же, как и в задачах но
критерию стоимости, необходимо использование электронных
вычислительных машин. При эюм машинное время решения та-
таких задач, для соогнетешующнх т и я, примерно совпадает
с затратами времени при решении задач по критерию стоимости.
§ 17. Решение задач транспортировки с учетом времени
и стоимости
В практических условиях может представиться более целе-
целесообразным реалп lainiH плана перевозок, являющегося неко-
некоторым средним между оптимальным по времени и оптималь-
оптимальным по стоимости. Для просто п.! изложения предположим,
что стоимость пропорциональна времени на перевозку,
т. С. сч^-Юи.
Для рассмотренного выше примера оптимальный вариант
по стоимости представляется таблицей 29 и выполняется, как
Т,1|').ппы 20
101
видно, за 28 часов при стоимости затрат на перевозки
С=К{7 ¦ 15 -f- 6¦ 5 -f- 10- 2 + И ¦ 20 +20¦ 13+2Ы2 4-5-9-f
-j-12-21 -f- 14-12-|-16- 11-}-28-5)=/<Г-1668 единиц стоимости.
Стоимость перевозок, соответствующая оптимальному варианту
Таблица 30
по времени (таблица 28), составляет С= КG-15 —j— 7 - 2 —{—
4-6-5-f-ll • 13-|-20-13-J-21 ¦ 12-|-21 - 7 -j- 5- 2 -j- 12-28-f
—[- 14-12 -(— 15-5 -|— 16-11) = 1716ДГ единиц стоимости. Затра-
Затрачивая дополнительную стоимость, равную 1716Д"—1668A"=:
= 48 К, мы завершим операцию перевозки грузов на 7 часов
Т л б л и и а 3!
раньше по сравнению с планом перевозок, определяемым
оптимальным вариантом по стоимости.
Как следует из рассмотренного выше примера, сравнитель-
сравнительно небольшие дополнительные расходы на перевозки могут
значительно сократить время на операцию транспортировки.
В случае, если заданы сроки выполнения операции транс-
102
портпровки, то, используя описанные методы, можно найти опти-
оптимальный вариант по стоимости, реализация которого осуществ-
осуществляется в пределах заданного срока. Если же потеря времени не-
недопустима, то определяем оптимальный вариант по времени.
Если полученный вариант с t°"T не является лучшим по стои-
стоимости, то, применяя алгоритм нахождения оптимального реше-
решения по минимуму линейной формы, можем получить оптималь-
оптимальный по стоимости из всех оптимальных по времени
(выполняемых за одно и то же время, равное t°"T). Так,
оптимальное решение по времени для рассматриваемого примера,
представленное таблицей 30, не является оптимальным но
стоимости. В самом деле, обратим х-выбранные элементы
в 0 (при обращении х-выбранных элементов в 0 значения
элементов, стоящих в перечеркнутых клетках, во внимание не
принимаются) (таблица 31).
В результате получим таблицу, в которой имеется отрица-
отрицательное число (—14). Преобразовав еще раз таблицу 31,
получим таблицу 32. В преобразованной таблице 32 х-вы-
бранные элементы равны 0, а остальные неотрицательные.
Т а б л и и а 32
15
7
45
3D
12
IS
го
20^
73
11
27
%^5
9
5
40
^2
^26
С=16ввН
Поэтому построенный вариант решения является оптимальным
но стоимости. Стоимость реализации этого варианта, выпол-
выполняемого также за 21 час, составляет С= 1688 АГ, что значи-
значительно меньше, чем 1716 АГ-
За последние годы методы линейного программирования
находят все более широкое применение в таких областях, как
экономика, техника, военное дело и т. п. Теория и методы
103
линейного программирования непрерывно совершен^ гвуются,
позволяя решать все поные и новые задачи. Бурное развитие
вычислительной техники сделало возможным практически
решать любые задачи из облает линейного программиро-
программировании.
Дальнейшее развитие мечодив линейного программирования
и применение их к решению народнохозяйственных задэт
будут способствовать улучшению организации п илапиро-
вання производства в нашей стране.
ЛИТЕРАТУРА
1. Л. 15. К а и т (I ]>о и 11 ч, М.исм.ипчоскнс: мспцы организации и ила-
инроиаиня lipoiiiHo.'iciii.i, изд. ЛГУ, 1939.
2. Л. В. К а н т о р о и и ч и М. К. Га ну I'nil, Математические мето-
методы анализа грузопотоков, сб. АН СССР '„Проблемы повышения
эффекпшностн работы Tpaiicnopia \ 1953.
3. IS. М. Каган и Т. М. Т с р-М и к а э л я и, i'eiiienue инженерных
задач па автоматических цифровых вычислительных машинах, Гос-
энергомздат, 1958.
4. А. И. К и т о в, Электронные цифровые машины, изд. «Сои. радио»,
1956.
5. А. Г. К у роли, Курс высшей алгебры, Фмзматгмз, 1!)Г)9.
6. Л. А. Л ю с т с р п и к, Выпуклые фшуры и мтч'огранннкн, Гостех-
издат, 19.16.
7. С. И. Черников, Линейные неравенства, УМН, т. 8, цып. 2
A953).
8. Н. В. Черникова, Наименьшие и наибольшие значения линейной
формы па мпо1'ограппике, УМП, т. 12, иып. 2 A957).
9. A. Charncs, W. W. Cooper ami A. 11 с ml er s on, An Intro-
Introduction to Linear i'ro^ranmiiny,', John Wiley, New York, VJb'A.
10. C. W. С h и г с h m a n, R. I.. А с k о f f, C. I.. A r u о f f, Introduction
in Operations Research, London — New York, 1955.
11. D. Chandler, Linear Programming and Computers, Now York,
1955.
12. A. G I a i s e 1, 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.