Г.С.ГАНШИН
МЕТОДЫ
ОПТИМИЗАЦИИ
И РЕШЕНИЕ
УРАВНЕНИЙ
МОСКВА «НАУКА»
ГЛАВНАЯ РЕДАКЦИЯ
ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ
1987

ББК 22.18
Г19
УДК 519.6
ГаншинГ. С. Методы оптимизации и решение
уравнений.— М.: Наука. Гл. ред. физ.-мат. лит., 1987.
— 128 с.
На элементарном уровне представлены методы
решения задач линейного программирования и задач
оптимизации для функций одной переменной.
Описание методов носит рецептурный характер,
иллюстрируется достаточным количеством численных
примеров.
Для инженеров, преподавателей и студентов вузов
инженерно-технического и экономического профилей.
Табл. 4. Библиогр. 27 назв.
Рецензент
доктор физико-математических наукФ. П. Васильев
г 1702070000—059 © Издательство «Наука».
053@2)-87 12-87 Главная редакция
физико-математической
литературы, 1987

ОГЛАВЛЕНИЕ
Предисловие 5
Введение 7
Глава I. Общая задача линейного программирования 13
§ 1. Постановка задач. Основные понятия и
обозначения , 13
§ 2. Алгоритм решения правильной ЗЛП 21
§ 3. Алгоритм решения канонической ЗЛП 26
§ 4. Несколько примеров 28
§ 5. В помощь преподавателю 32
Глава II. Транспортная задача 35
§ 1. Постановка задачи. Система обозначений .... 35
§ 2. Построение допустимого плана ТЗ по методу
минимальных элементов 40
§ 3. Метод добротностей 42
§ 4. Некоторые свойства ТЗ 44
§ 5. Построение оптимального плана 50
§ 6. Построение всех оптимальных планов 56
§ 7. Вычисление /р 58
Глава III. Граничные константы и вычисление их
оценок 60
§ 1. Граничные константы. Основные понятия и
обозначения 60
§ 2. Простейшие способы вычисления оценок
граничных констант 64
§ 3. Рекуррентные вычислительные процедуры .... 65
§ 4. Модификация схемы Горнера 67
§ 5. Вычисление оценок граничных констант для
функциональных многочленов 69
§ 6. Блочные методы вычисления оценок 71
§ 7. Еще один способ вычисления неопределенных
оценок для алгебраических многочленов 72
3

Глава IV. Вычисление наибольшего значения функции 76
§ 1. Основные понятия и обозначения. Простейшие
методы вычисления НЗФ 76
§ 2. Элементарные оценки для НЗФ 81
§ 3. Сеточные оценки 82
§ 4. Вычисление НЗФ с заданной точностью
алгоритмами, использующими равномерные сетки 85
§ 5. Монотонные алгоритмы вычисления НЗФ .... 89
Глава V. Решение уравнений 94
§ 1. Постановка задач. Основные понятия и
обозначения 94
§ 2. Определение границ корней уравнения 98
§ 3. Отделение корней 102
§ 4. Вычисление всех корней на заданном отрезке . . . 104
§ 5. Вычисление корня. Монотонные вычислительные
процессы 108
§ 6. Вычисление простых корней 115
Список литературы 121
Предметный указатель 123
Список обозначений и аббревиатур 125

ПРЕДИСЛОВИЕ
Эту книгу следует рассматривать как дополнение к
обширной литературе по методам оптимизации и численным
методам решения уравнений. Значительная часть
материала данной книги не нашла отражения в вышедших в свет
монографиях, часть результатов публикуется здесь
впервые.
Книга предназначена в первую очередь для инженеров,
преподавателей и студентов технических вузов и
экономических факультетов. Главной методической целью автора
было такое изложение материала, которое требовало бы
от читателя минимальных усилий на освоение методов
решения задач. Поэтому описание методов носит
конспективный характер, иллюстрируется достаточным
количеством численных примеров, а обоснование методов, как
правило, дается схематически.
Все численные примеры, содержащиеся в книге,
достаточно просты, и решение любых подобных примеров
можно проводить «вручную». Однако для решения более
сложных задач необходимо привлечение ЭВМ. И здесь уже от
читателя требуется квалификация программиста и
определенная изобретательность.
Заметим, что для многих рассматриваемых в книге
задач существуют стандартные программы их решения на
ЭВМ и нужно лишь уметь ими воспользоваться. Однако,
чтобы успешно формулировать и решать задачи на ЭВМ
(даже те, для которых существуют стандартные
программы), необходимо хорошо ознакомиться с самой задачей —
ее формулировкой, особенностями, с основными идеями,
приводящими к ее решению. Наилучший путь такого
знакомства — это самостоятельное решение «вручную»
простейших моделей рассматриваемой задачи. При этом совсем
не обязательно в точности повторять ту технологию
решения задачи, которая заложена в стандартной
программе для ЭВМ. Для целей обучения важно использовать
наиболее простые схемы решения, сокращающие время
5

освоения метода и время «ручного» счета модельных задач.
Именно с этих позиций и написана данная книга.
Первые две главы содержат материал традиционный для
курсов математического программирования, методы
решения задач линейного программирования. Однако
нетрадиционное изложение этого материала позволяет резко
сократить время на его освоение. В частности, принятая схема
изложения не использует таких фундаментальных
понятий, как базис, преобразование пространства и т. д. Это
позволяет, например, исключить из учебных планов
экономических факультетов курс линейной алгебры как
самостоятельную дисциплину либо существенно его
сократить.
Принятая здесь методика значительно сокращает
также время решения модельных задач линейного
программирования. Так, например, время решения модельных
транспортных задач в студенческой аудитории сокращается
в несколько раз и измеряется теперь не часами, а
минутами. Заметим, что использование содержащихся в первых
двух главах новых идей может привести к повышению
эффективности решения и громоздких задач, решаемых на
ЭВМ.
Последние три главы посвящены задачам для функции
одной переменной. Методы этих глав условно можно
назвать «глобальными методами», или «методами с
глобальной сходимостью», поскольку они приводят к решению
задачи для любого исходного отрезка. В частности, для
применения методов последних глав не требуется, чтобы
на заданном отрезке исследуемая функция была
монотонной, выпуклой или унимодальной.

ВВЕДЕНИЕ
Каждая глава книги обладает значительной автономией
по отношению к остальному тексту, поэтому читатель
сразу может приступить к чтению интересующей его главы.
Однако целесообразно предварительно просмотреть
данное введение с тем, чтобы в первую очередь познакомиться
с основными принятыми здесь обозначениями. Кроме того,
во введении обсуждаются некоторые общие вопросы,
связанные с тематикой книги.
При решении самых разнообразных практических
задач хозяйственной, экономической, научной, инженерно-
технической деятельности людей возникает потребность
в определении максимального /* или минимального /d
значения некоторой функции / (х) в некоторой заданной
области D возможных значений ее аргумента х. Функцию
/ (х) будем называть целевой функцией, а любую точку
х ЕЕ D — допустимой точкой или допустимым планом
задачи математического программирования. Точку ,z;*GD,
в которой достигается максимальное на D значение /d
целевой функции /, будем называть точкой максимума или
оптимальным планом. Точку х° ЕЕ D, в которой
достигается минимальное значение функции /, назовем точкой
минимума; х° также называют оптимальным планом.
Определим теперь величины /#, /?>, ж*, ж0 с помощью формул *)
/* = / (Х*) = щах {/ (х)}, i*ED;
/
/г. = / №) = min {/ (х)},
D
Изучением и разработкой методов вычисления
°
у / /
#*, х° занимается раздел прикладной математики Мате-
*) В книге опускаются некоторые тонкие построения
математического анализа и рассматриваются только такие функции, для
которых максимальное и минимальное значения в области D
достигаются.

матическое программирование, в котором, в свою очередь,
можно выделить различные классы задач (например,
линейное программирование, выпуклое программирование
и т. д.); для каждого из них существуют специальные
методы решения. Выделение специальных классов задач
математического программирования происходит путем
наложения специальных ограничений на вид целевой функции
/ и на способы задания области D. Например, если / —
линейная функция нескольких переменных, а область D
задается с помощью линейных ограничений на переменные,
то мы приходим к задачам линейного программирования,
которым посвящены первые две главы.
В свою очередь, класс задач линейного
программирования можно разбить на более узкие классы задач,
каждый из которых обладает теми или иными особенностями.
При этом, используя указанные особенности, для более
узкого класса задач, как правило, удается построить
и более эффективные методы их решения. Это общее
свойство методов вычислительной математики. Так, например,
транспортная задача (ТЗ) является частным случаем
общей задачи линейного программирования. Транспортную
задачу, сформулированную в гл. II, можно записать в
форме канонической задачи линейного программирования
и применить для ее решения методы гл. I. Однако учет
специфических особенностей ТЗ позволяет построить
специальные методы ее решения, которые дают возможность
решать ТЗ значительно быстрее и в более компактной
форме по сравнению с методами гл. I.
В последних трех главах исследуется функция одной
переменной, и для этих глав D — отрезок, т. е. D = [а, Ь].
В гл. ID — это множество векторов размерности тг, т. е.
D d Rn. В гл. II D — множество целочисленных матриц,
имеющих т строк и п столбцов. Это множество
обозначается через Rmn.
Для упрощения изложения во всех задачах в данной
книге D — это множество точек с неотрицательными
координатами: если D = [а, Ь], то 0 ^ а < Ъ\ если D d Rn,
то для любого вектора х = (х±, . . ., хп) Е= D имеем хх ^> О
(г = 1, 2, . . ., п)\ если X ЕЕ D d Rmr\ то все элементы
матрицы X являются целыми неотрицательными числами.
Последнее ограничение не является принципиальным,
так как методы, излагаемые в книге, можно применить
и в тех случаях, когда это ограничение нарушено. Пусть,
например, рассматривается задача вычисления /р, где
D = [—[х, X], причем \i ^> 0 и X ^> 0. Существуют два пу-
8

ти сведения такой задачи к задаче (или задачам), где
изучаемая область содержит только положительные числа.
1. Отрезок D = [—[х, X] разбиваем на два отрезка:
D1 = [-щ 0], D2 = [0, X].
Вычисляем максимальное значение /В2 функции / (х) на
отрезке D2, а отрезок Dx переводим в отрезок D' путем
замены переменной х = —v. Такая замена порождает
вспомогательную функцию ф согласно формуле
Теперь /Ь можно вычислить по
где фВ' — максимальное значение функции ф на
отрезке D'.
2. Отрезок D = [—\i, X] переводим в отрезок D' =
= [0, X + ji] путем замены переменной и = х -\- \i. При
этом /В = фЬ-> где
Ф (у) = / (v — v), v е D' = [0, X + |л].
Аналогичные приемы можно применять и при решении
многомерных задач.
Следующим важным моментом является тот факт, что
формально существуют две различные задачи:
а) задача вычисления /В — максимума функции /;
б) задача вычисления /р — минимума функции /.
Однако практически достаточно научиться решать
одну из этих задач. В самом деле, пусть две функции / и ф
связаны соотношением
Ф (х) = —/ {х).
Тогда для любой области Z), на которой определена
функция/ (а следовательно, и функция ф), справедливо
равенство
f°D = -ФШ A)
причем
/(*°)=/2ь x° = v*, x\v*ZED,
фг> = ф (у*) = шах {ф (х)}.
Поэтому если у нас есть некоторый алгоритм А для
вычисления максимума функции {т. е. fr> = A {/, Z)}), а нам
нужно вычислить /о, то достаточно применить алгоритм А
9

к вспомогательной функции ср, т. е. вычислить ф^ =
= А {ф, D), и воспользоваться формулой A). С учетом
последнего замечания в гл. I и IV мы ограничиваемся
изучением методов вычисления f% — наибольшего значения
функции (НЗФ). В гл. II излагаются методы вычисления/р.
Линейные задачи первых двух глав допускают точное
решение. В гл. II точность решения обеспечивается
решением в целых числах. Заметим, что и общую задачу
линейного программирования также можно решать в целых
числах (см. пример 14 из гл. I). При этом если исходные
данные задачи даны в виде рациональных десятичных
чисел, то исходную задачу можно перевести в задачу с
целочисленными исходными данными умножением всех
исходных данных на 10*. Разработка эффективных алгоритмов
точного анализа (без округлений) на ЭВМ задач линейного
программирования может составить предмет
самостоятельного исследования. Подобные алгоритмы окажутся
полезными при решении плохо обусловленных задач, когда
обычные методы решения (с округлением) ведут к
недопустимо большим погрешностям.
В последних главах рассматриваются нелинейные
задачи, которые в общем случае допускают лишь
приближенное решение. В гл. IV описываются алгоритмы
приближенного вычисления /#. Эти алгоритмы используют
оценки граничных констант — типа константы Липшица
либо минимума второй производной. Те же самые оценки
используются в алгоритмах гл. V,' которые приближенно
вычисляют корни уравнений. Способы вычисления оценок
граничных констант описываются в гл. III.
Отметим тесную связь задачи вычисления НЗФ /р или
наименьшего на D значения fD функции / с задачей
вычисления корней уравнения (или системы уравнений в
многомерном случае). В самом деле, пусть /
дифференцируема на отрезке D = [а, Ь], a G' — множество корней
производной /' на отрезке D. Тогда если мы решим
уравнение
/' (я) ~0, ^Gfl,
т. е. определим конечное множество точек С?', то величины
/d и f% можно вычислить по формулам
f°D = min {/ (a), f F), &}, fG. = min {/ (v)};
G'
/J = max {/ (a),f(b), f%}, fG> = max {/ (v)}.
=G'
10

Здесь, как и в гл. V, для записи уравнений вместо знака
равенства используется символ ~.
С другой стороны, все корни функции / являются
точками минимума вспомогательной функции ср (х) = / (х)-
•/ (х), причем фх) = 0, если функция / имеет корни на
отрезке D. Такая тесная связь задачи вычисления НЗФ и
задачи вычисления корней уравнения обусловливает тот
факт, что методы решения этих задач обычно имеют много
общих мест. Не случайно поэтому оценки граничных
констант, вычисляемые методами гл. III, обслуживают
алгоритмы как гл. IV, так и гл. V.
Заканчивая обсуждение вычислительных аспектов
рассматриваемых здесь задач, хотелось бы отметить
чрезвычайную сложность и громоздкость уже сейчас созданного
здания вычислительной математики в целом и ее разделов,
посвященных методам оптимизации и решению уравнений,
в частности. Достаточно подробное знакомство даже
только с основными методами вычислительной математики
превращается в дорогое удовольствие, требующее много
времени и труда. В свете этого факта возрастает роль
универсальных методов, с помощью которых можно решить
возможно более широкий круг задач. Описание таких
универсальных методов должно предназначаться в первую
очередь для людей, не являющихся специалистами по
вычислительной математике, но использующих ее методы в
своей работе. К таким универсальным методам и
относятся алгоритмы, описанные в последних трех главах книги.
В отличие от локальных методов эти алгоритмы не
требуют проведения специальных исследований для выяснения
вопроса — можно ли решить имеющуюся задачу таким
алгоритмом, ибо приводят к решению для любого
исходного отрезка. Поэтому методы, описанные в гл. III, IV
и V, следует рекомендовать широкому пользователю при
решении относительно несложных задач, с которыми
справляется имеющаяся у пользователя вычислительная
техника.
Вместе с тем запросы практики заставляют
разрабатывать алгоритмы решения все более сложных задач, среди
которых задачи оптимизации являются одними из
наиболее трудных. Процитируем фрагмент из предисловия в
книге [11]: «Обсуждая свою знаменитую программу, Гильберт
высказывает надежду, что в XX в. математики
овладеют способами решения оптимизационных задач. Это
действительно проблема, ибо в вычислительном плане
оптимизационные задачи на порядок более трудоемкд, чем все
11

те задачи, с которыми до сих пор сталкивались
исследователи. Более того, уже сейчас ясно, что классические методы,
даже если в нашем распоряжении окажутся
гипотетические вычислительные машины предельного
быстродействия, позволят решать только относительно простые
задачи». Для решения сложных задач не существует
универсальных методов их решения. Поэтому всю литературу по
вычислительной математике и существующие библиотеки
стандартных программ следует рассматривать как
вспомогательный инструментарий. Ибо успешное решение
сложных задач (в особенности нелинейных многомерных)
существенно зависит от опыта и эрудиции вычислителя, его
изобретательности, умения учитывать и использовать
индивидуальные особенности задачи и имеющихся
вычислительных средств. При этом вычислитель должен быть во
всеоружии уже созданных методов и обладать навыками
конструирования новых алгоритмов.
Методику изложения, принятую в книге,
по-видимому, условно, можно назвать наглядной, поскольку
значительную нагрузку в описании методов несут численные
примеры. При этом хорошо иллюстрируются основные
идеи метода и в то же время часто опускаются многие
детали и подробности, которые необходимы для строгого
описания метода и которые следует учитывать при
построении стандартной программы реализации метода на ЭВМ,
предназначенной для решения класса задач.
Восстанавливать опущенные подробности должен уже сам читатель.
Такая форма изложения представляется автору вполне
приемлемой, ибо «интуиция, опыт — все то, что обычно
называется здравым смыслом или неформальным
мышлением,— в такой же мере имеют законное право на
существование при анализе математических задач, как и все
прочее» [11, с. 9].

Глава I
ОБЩАЯ ЗАДАЧА
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
§ 1. Постановка задач. Основные понятия
и обозначения
Задачи математического программирования, в
которых целевая функция / (х) — линейная функция, а
область D задается с помощью линейных равенств и (или)
неравенств, называются задачами линейного
программирования. Формально задачу линейного программирования
(ЗЛП) можно записать в виде
fD = ?, х* = ?, A)
&=/(**) = max {/(*)}, B)
/ (х) = <с, х> = с1х1 + с2х2 + . . . + спхп, C)
D = {х е Rn | f D)
E)
F)
G)
Здесь с, q, b, a ¦— заданные векторы; Q, В, А —
заданные матрицы; Rn — множество векторов размерности
щ Rmn — множество матриц, имеющих т строк и п
столбцов. В первых двух главах матрицы обозначаются
прописными латинскими буквами, соответствующие строчные
буквы с двумя нижними натуральными индексами
обозначают элементы этих матриц. Строчные латинские буквы
обозначают векторы, строчные латинские буквы с одним
нижним натуральным индексом обозначают координаты
векторов. Чтобы подчеркнуть, что Ъг — вектор
размерности т, делается запись Ъг GE Rm. При этом
Ьг = (Ьгъ Ьг2, . •., Ьгт).
13

Для обозначения скалярного произведения двух векторов
используются угловые скобки — см. формулу C). Знак
неравенства между двумя векторами означает, что такое
неравенство выполняется для каждой пары одноименных
координат этих векторов. Напоминаем (см. введение), что
в данной главе каждая переменная хг удовлетворяет
неравенству хг > 0.
В общей задаче линейного программирования,
представленной соотношениями A) — G), требуется найти
оптимальный план х* <Ez D, который сообщает максимальное
значение f% целевой функции C) на множестве допустимых
планов D. Для любых исходных данных, задаваемых
соотношениями C) — G), можно вести также речь о поиске
оптимального плана х° ЕЕ D, который сообщает
минимальное на D значение /?> целевой функции C). Величины
#*, Уо (либо х°, fD) будем называть решением ЗЛП. Все
основные рассуждения в данной главе относятся к задаче
вычисления х* и /В.
Область D может задаваться любыми сочетаниями
ограничений E), F), G), т. е. в формулировке ЗЛП любой
один либо любые два из трех видов ограничений E), F),
G) могут отсутствовать. Например, если область D
задается только с помощью неравенств, т. е. отсутствуют
ограничения-равенства G), то говорят, что ЗЛП задана в
стандартной или естественной форме.
Область D может быть задана только с помощью
ограничений-равенств с положительными свободными
членами в правых частях этих равенств, т. е.
D = {x^Rn\Ax = a, a>0, Л^Ктп}. (8)
Здесь 9 — нулевой вектор:
6 = @, 0, . . ., 0)GRm
В дальнейшем размерность нулевого вектора 0 совпадает
с размерностью вектора, который с ним сравнивается.
ЗЛП, заданную соотношениями A), B), C), (8), будем
называть канонической ЗЛП. Любая форма ЗЛП путем
несложных преобразований может быть приведена к
каноническому виду. Последнее утверждение опирается на
более простое: любое неоднородное равенство или
неравенство можно привести к каноническому равенству вида
<d, хУ = X, К > 0, d,iERn, ^E R.
Система равенств Ах = а в формуле (8) состоит из
канонических равенств. Конкретный пример канонического
14

равенства:
2хх — Зх2 + х± = 5.
Здесь X = 5, d = B, —3, О, 1), я = (х^ яа, я3, я4).
Далее приведем ьримеры преобразования конкретных
неравенств и равенства (ф) к каноническому равенству (ij)).
Пример 1.
ф: — 2хх + Зх2 — х± = —5,
ф: 2а?! — З.г2 + я4 = 5.
Пример 2.
ф: 2^ — Ъхг < 5,
яр: 2хх — Зх2 -\- х3 = 5 {х3^ 0).
Пример 3.
ф: 2хг — Зх2 > 5,
гр: 2хх — Зх2 — х3 = 5 (х3 > 0).
Пример 4.
ф: 2ях — Зх2 ^ —5,
-ф: —2х1 + Зя2 — х3 = 5.
В последнем примере каноническое равенство получено
путем двух элементарных преобразований:
Bхх — Зх2 < —5) ->- {—2х± + Ъх2 > 5) ->-
-> {—2х1 + Ъх2 — х3 = 5).
Пример 5. Рассмотрим конкретную ЗЛП:
fo = ?, / W = *2 - 2х3, (9)
D = {^GR3| - 4*x + 2*2 < -1, A0)
хг-х3>1, (И)
хг + х2 - 2х3 = 5}. A2)
Область допустимых планов D задана здесь двумя
ограничениями-неравенствами и одним ограничением-равенством.
Легко проверить, что два вектора
х1 = (х\, xl х\) = B, 3, 0),
х* = (xl xl xl) = A1/6, 19/6, 0), A3)
являются допустимыми планами этой ЗЛП, т. е.
координаты этих векторов удовлетворяют всем трем
ограничениям A0) — A2). Можно привести бесконечно много
подобных векторов, каждый из которых является допустимым
15

планом ЗЛП (9) — A2). В частности, любой вектор х,
вычисляемый по формулам
х = Хх1 + A — К) я2, X е @, 1),
является допустимым планом рассматриваемой задачи.
Для каждого допустимого плана х ЕЕ D можно
подсчитать значение целевой функции (9). Например,
/ (х1) = *J-2*1 = 3-2-0 = 3,
/ (х*) = 19/6.
Чтобы решить задачу (9) — A2), нужно из бесконечного
множества допустимых планов D выбрать такой план
х* Е= D (называемый оптимальным), на котором целевая
функция (9) достигает максимального значения. Обычно
процедура поиска оптимального плана х* для ЗЛП
общего вида содержит предварительный этап — сведение
исходной ЗЛП (9) — A2) к канонической ЗЛП. Преобразуя
ограничения A0), A1) по аналогии с примерами 3 и 4
введением двух дополнительных переменных *4, х$, приведем
исходную ЗЛП (9) — A2) к следующей канонической
ЗЛП:
Id — г
4*1 — 2*2 + 0-яз — 1 -я4 + О.аг6 = 1, (Щ
l.*i + 0-*a —1.*8 + 0.*4— 1-*в = 1, (И')
l-*i + 1-*2 —2.*з + 0.;г4 + 0.*5 = 5, A2')
/(*) = 0.*1 + 1.жа —2-*8 + 0.*4 + 0.*Б = <с, *>. (9')
Отбрасывая в этих соотношениях знаки равенства и все
буквенные символы и сохраняя лишь числовую
информацию, придем к табличной форме записи канонической
ЗЛП:
4
1
1
—2
0
1
0
—1
—2
—1
0
0
0
—1
0
1
1
5
L= 1 1—2 0 0 5 A4)
0 1—2 0 0 |
Для обозначения канонической ЗЛП будем использовать
букву L. Исходные данные канонической ЗЛП A4)
полностью определены заданием матрицы
Г4 —2 0 -1 СП
^= 1 0—1 0—1
[_1 1—2 0 0J
16

и векторов
а = A, 1,5), с = @,1, -2,0,0).
Отражая этот факт для канонической ЗЛП, в частности
для ЗЛП A4), будем использовать два таких обозначения:
А
а
= Ь{А, я, с),
где А е R™, flGRffl,ce Rn.
Методы построения оптимального плана х* для
канонической ЗЛП опираются на следующее утверждение.
Лемма 1. Если для канонической ЗЛП L {А, а, с}
вектор коэффициентов целевой функции с = (с±, . . ., сп)
не содержит положительных координат {т. е. с <^ 9), а
вектор х' = (х'х, . . ., х'п) является допустимым планом
данной ЗЛП и <с, х'У = 0, то вектор х' является
оптимальным планом ЗЛП L {А, а, с}, т. е. х' = х*. При
этом /d = 0.
Лемма очевидна, поскольку в условиях леммы целевая
функция <(с, хУ ^ 0 для любого х ЕЕ D (напомним, что
х > 8). Поэтому значение целевой функции <с, #*> = 0
является оптимальным (максимальным на D).
Аналогичным утверждением является
Лемма 2. Если для канонической ЗЛП L {А, а, с}
имеем с ^> 8, а для вектора х' выполняются условия
x'Gfl, О, х'У = 0,
wo х' = х° и fD = 0.
Алгоритмы вычисления #* для канонической ЗЛП
строят последовательность вспомогательных ЗЛП. Целью
таких построений является получение в итоге
вспомогательной ЗЛП Lp,, удовлетворяющей условию леммы 1.
При этом оптимальный план х* вспомогательной ЗЛП
Lp, оказывается также оптимальным планом и для
исходной ЗЛП. Так, например, применяя к ЗЛП A4) алгоритм,
описанный в § 2, 3, после трех тактов этого алгоритма
придем к ЗЛП
A5)
Легко проверить, что ЗЛП L3 = L {А3, а3, с3}
удовлетворяет условиям леммы 1 (так как с3 ^ 6) и для нее легко
17
0
1
= 0
0
0
0
1
0
2/6
—4/6
—8/6
-4/6
-1/6
-1/6
1/6
0
1
0
0
0
5/6
11/6
19/6

указать вектор, фигурирующий в этой лемме, а именно
х' = х* = A1/6, 19/6, 0, 0, 5/6). A6)
В самом деле, используя таблицу L3, распишем ЗЛП L3
в виде системы равенств относительно координат
вектора #*:
0# . п # . 2 * 1 *,у|* 5
-х1 + 0-х.2 + -Жз— -g- xi + l-x6 = -T,
А * i 4 * ^ # . 1 # п # 19
О-Жх + 1.Ж2 g" ^3 +"ё" ^4 + 0-Ж5 =-g-,
4 4+ °-4+ 0.4=<с8, **>.
Подставляя в эти соотношения координаты вектора A6),
мы видим, что первые три соотношения превращаются в
тождественные числовые равенства (т. е. х* Е= D), а
последнее соотношение превращается в равенство
0 = <с3, х*у.
Введем новые понятия. Столбец канонической ЗЛП,
записанной в табличной форме, назовем правильным,
если он содержит единственный ненулевой элемент, который
является к тому же положительным числом. В таблице
A5) первый, второй и пятый столбцы — правильные.
Правильной ЗЛП назовем всякую каноническую ЗЛП
L {А, а, с} (при А ?Е Rmn), в которой можно выделить как
минимум т правильных столбцов и при этом каждая
строка матрицы А содержит один ненулевой элемент этих
правильных столбцов *). Примером правильной ЗЛП
является ЗЛП A5).
Допустимым планом ЗЛП является вектор
размерности п, у которого может быть произвольное число
ненулевых координат. Допустимый план канонической ЗЛП
назовем опорным планом, если он содержит ровно т
ненулевых координат. В общем случае каноническая ЗЛП, в том
числе и правильная ЗЛП, содержит несколько (часто
весьма большое число) опорных планов. Тривиальным
опорным планом правильной ЗЛП назовем такой опорный план,
который для данной правильной ЗЛП определяется наи-
*) Здесь рассматриваются только такие канонические ЗЛП,
у которых т < п и все строки матрицы А линейно независимы.
18

более простым способом — достаточно лишь положить
равными нулю те координаты плана, которые
соответствуют неправильным столбцам. Если ненулевые элементы
правильных столбцов правильной ЗЛП равны единице,
то ненулевыми координатами тривиального опорного
плана будут элементы последнего столбца таблицы L.
Примером тривиального опорного плана является вектор A6)
для ЗЛП A5).
В заключение обсуждения постановки задач отметим, что не
всякая ЗЛП имеет решение. Решение ЗЛП может отсутствовать
по двум причинам. Во-первых, система ограничений ЗЛП может
оказаться несовместной — при этом D = 0.
Упражнение 1. Приведите примеры ЗЛП, у которых
D = 0i если ЗЛП задана: а) в стандартной форме; б) в канонической
форме.
Во-вторых, одно из решений ЗЛП (на максимум либо на
минимум) может отсутствовать, если D — неограниченное множество,
а целевая функция не ограничена на D (сверху либо снизу). Здесь
под неограниченностью D понимается неограниченность планов,
принадлежащих D, т. е. D не ограничено, если нельзя указать
такое число а, чтобы для любого гей выполнялось неравенство
х{ <; о для каждой координаты вектора х. Примером ЗЛП с не
ограниченной снизу на D целевой функцией является ЗЛП (9) — A2),
а следовательно, и ЗЛП A4).
Упражнение 2. Постройте примеры ЗЛП с не
ограниченным на D значением целевой функции для каждого из возможных
случаев: а) не существует конечного fD'i б) не существует
конечного /В*
Более подробно познакомиться со случаями отсутствия
решения ЗЛП читатель может по любой книге, где рассматриваются
задачи линейного программирования. Мы на этих вопросах далее не
останавливаемся, поскольку, на наш взгляд, ЗЛП, которые не
имеют решения, представляют в основном лишь теоретический
интерес, ибо любая реальная техническая или экономическая задача,
смоделированная в виде ЗЛП, обязательно должна иметь решение,
если, конечно, математическое моделирование проведено
достаточно качественно.
Теперь на примере поясним основную идею, на
которой базируются алгоритмы решения ЗЛП.
Пример 6. Вычислить f% для целевой функции
/ (х) ЗЛП Lp, заданной соотношениями
(х)
(х)
(х)
— 6X-L i
= 4*! +
= 2хг +;
5а:2 + 4г
х2 + 6*3
Ъхг + 4х;
3 = 6,
= 10,
в = /В
— х (;
^>0).
A7)
19

Здесь первые два равенства задают область Z).
Преобразуем ЗЛП A7) во вспомогательную ЗЛП Ьг:
^-х2 = 1, A8)
ЗЛП A8) получена из ЗЛП A7) по формулам
i|>i = ^ — бфь Д = / —4фь A9)
При этом из второго и третьего равенств в A7)
исключалась переменная х3.
Равенства A7), A8) остаются справедливыми для
любого х = (хг, х2, ж3)?Й, в частности для х = х*. Если
в соотношения A7), A8) подставить ж = ж*, то в
последних равенствах этих соотношений
Ь = Хо = 0. B0)
Поскольку #2 > 0, то /х (л:) ^ 0 для любого х ЕЙ
и поэтому максимальное значение целевой функции f1 (x)
на D равно нулю. В самом деле, подставив в A8) х2 = 0,
мы не получим противоречивых равенств, ибо из второго
равенства в A8) получим хх = 1, а из первого — xs = 1.
Выбирая вид преобразования ЗЛП A7) -> ЗЛП A8),
руководствуются следующими соображениями.
1. Стремятся, чтобы максимум целевой функции Д (х)
новой вспомогательной ЗЛП обращался бы в нуль (или,
по крайней мере, был возможно ближе к нулю). В данном
случае этого удалось добиться за одно преобразование.
Однако, как правило, для достижения цели приходится
проводить несколько преобразований. Целесообразно,
чтобы каждое последующее преобразование проводилось по
тем же правилам, что и первое. Последнее достигается
выполнением следующего условия.
2. Преобразование проводят так, чтобы во вновь
образованной ЗЛП A8) правые части равенств, задающих
D, вновь оказались бы положительными числами.
Параметр X, введенный в данном примере, имеет
важный вычислительный смысл. Из формул A7) — B0)
следует, что
K = fb- h (**),
20

и если X = О, /х (я*) = О, то Хг = f%. Этот вывод остается
справедливым (индекс 1 заменяется на v) и в общем случае,
когда для решения канонической ЗЛП проводится не
одно, a v преобразований. Для облегчения описания
алгоритмов в некоторых случаях параметр X вводится в
обозначения ЗЛП, т. е. вместоL{А, а, с} пишутL {А, а, с, X}.
Упражнение 3. Изучить, в каком смысле
эквивалентными являются различные формы записи ЗЛП, а также
эквивалентность различных преобразований ЗЛП. В частности, обратить
внимание на то, что в самом общем случае (отсутствует ограничение х >
1> 0) при неограниченности D возможны случаи, когда ЗЛП вообще
не имеет решения (отсутствуют конечные fD и /г>).
§ 2. Алгоритм решения правильной ЗЛП
Обозначим исходную правильную ЗЛП через Lo •=
= L {А0, а0, с0, Яо}, Хо = 0. Отправляясь от Lo, алгоритм
строит последовательность
Lo, L1? L2, . . ., Lv; B1)
Ц = Ь{А\ a\ c\ A*}, i = 0f 1, 2, ..., v.
Преобразование Lj_x -> Lj проводится по одному и тому
же правилу для каждого /, где l^/<^v — 1. У
последней вспомогательной ЗЛП Lv вектор cv не имеет
положительных координат, т. е. cv ^ 0. Последнее условие
служит критерием окончания построения последовательности
{LJ. Тривиальный опорный план ЗЛП Lv и будет
являться искомым оптимальным планом х* исходной задачи Lo
и при этом
/* = / (**) = ^.
Опишем первый такт (при / = 1) алгоритма
построения последовательности {Ь*}, т. е. правило, по которому
проводится преобразование
Lo = L {А\ а\ с\ Хо} -+ L {А\ с\а\ \} = Ьг.
Вначале в матрице А = {аЬ} выбирается ведущий элемент
аЬ (точнее, ведущая позиция к, t). Затем с помощью
ведущей (Ани) строки переменная xt исключается из всех
остальных строк ЗЛП Lo так, как это делается в методах
исключения при решении систем линейных
алгебраических уравнений. При этом будет получена ЗЛП Ьг.
Опишем способы выбора ведущей позиции к, t. Для
заданного t номер к ведущей строки определяется одно-
21

значно, а именно ведущей к-ж строкой объявляется такая
к-я строка, для которой
4t
В качестве ведущего столбца (с номером t) может быть
объявлен любой /-й столбец, если с] ^> 0. Для выбора
ведущего t-то столбца можно рекомендовать одно из
следующих трех правил.
1. t — нижний индекс у первой в ряду с\, с\, . . ., Сп
положительной координаты вектора с0.
2. t удовлетворяет условию: с\ — максимальная
компонента вектора с0.
3. t удовлетворяет условию
Заметим, что
^L=max c<?min-^ .
ctak
т. е. третье правило выбора номера t ведущего столбца
обеспечивает максимальное увеличение параметра %.
Поскольку последовательность {Lt} строится до достижения
параметром X своего максимального значения, равного
f%, то использование третьего правила выбора t обычно
ведет к снижению общего числа тактов алгоритма.
Пример 7. Решить следующую ЗЛП [1, с. 154],
в табличной записи которой (и в последующих таблицах)
вместо нулей используются точки:
3
1
—1
•
1
-2
1
4
1
1
•
-3
-1
3
4
L=V 114-32 B3)
/*
В процессе решения этой ЗЛП будет проведена следующая
цепочка преобразований:
Преобразуем каноническую ЗЛП L = L {А, а, с, К}
(К = 0) в правильную ЗЛП Lo = L {А0, а0, с0, Хо},
исключая из последней строки таблицы B3) переменные х2
22

и #4. Это исключение проводим путем двух
последовательных преобразований:
L ->- V по формуле /' = / + 2я|),
Z/ —>¦ Lo по формуле /0 = /' + 3q/,
ф'
L'=
/'
1
4
1 -1
3
9-3 10
/* + 4
B4)
фо
*>
/о
3
1
10
1
1
4
12
1
•
—1
3
7
/*
3
2
13
Полученная вспомогательная задача B4) является
правильной ЗЛП, и к ней уже можно применить
описанный выше алгоритм. При этом используем третье правило
для выбора номера t ведущего столбца. Проведем
преобразования L L L
Ф1
/i
ф2
и
1 . 1/3
. 1 11/3
. . 26/3
1 1/10
3/10
. -31/10
1/3
-1/3
—10/3
7/10
11/10
—27/10
-1/3
10/3
31/3
3/10
—1/10
—23/10
1
1
/*
1
11/10
3/10
/* — 1/10
Преобразование Lo
Ф1 = Фо/3, ^
проводилось по формулам
о — Фх, /i = /о —
B5)
т. е. в этом преобразовании с помощью первой строки
исключалась переменная хх. Однако, прежде чем проводить
вычисления по формулам B5), следовало выбрать номер
исключаемой переменной. Переменная хг была выбравд
на основании следующих рассуждений.
Для каждого столбца с положительным элементом в
последней строке (строке целевой функции) определяется
ведущий для данного столбца элемент. При этом
используется формула B2). Так, для первого столбца задачи B4)
имеем
aU
1
а?, 3 ' а» 1
23

Для третьего столбца имеем
4 . ( < 4
В пятом столбце матрицы ^4.° есть только один
положительный элемент а\ь = 3 — он и является ведущим, причем
ol = 2/3. Ведущие элементы в первом, третьем и пятом
столбцах задачи B4) подчеркнуты. Далее из этих
подчеркнутых элементов в качестве ведущего для преобразования
Lo ->¦ Lx следует выбрать такой, который обеспечивает
максимальное изменение параметра X (к = —13) для
задачи B4)) при исключении соответствующей переменной
из последней строки таблицы B4). Практически такой
выбор осуществляется по максимальному среди произведений
JcS = -i-.12 = 6,
оо
14
Первый столбец выбран ведущим, поскольку 10 > 6 ]>
> 14/3.
Аналогичным образом выбирался ведущий элемент
#25 — Ю/3 в матрице А1 = {alj} для преобразования Lx —>-
—>¦ L2. Преобразование Ьг -+• L2 проводилось по формулам
3 1 31
*2 = -jo-^i> 92 = 9i+-3"^|J, /2 = /i з"^2.
Поскольку задача L2 не содержит положительных
элементов в последней строке (с2<^0), то тривиальный
опорный план х2 ЗЛП L2 и является искомым оптимальным
планом ж* исходной задачи B3). Ответ:
х* = ^2 = A1/10, 0, 0, 0, 3/10), fD = 1/10.
В заключение полезно провести проверку
правильности проведенных вычислений, подставив найденный план
х* в каждую (или хотя бы в последнюю) строку исходных
данных B3). Для последней строки задачи B3) имеем
Несколько замечаний к примеру 7.
1. Если использовать второе правило выбора номера
t ведущего столбца, то заключительную вспомогательную
задачу L2 получим путем трех (вместо двух) преобразова-
24

ний: Lo ->- L[ -> L'2 -> ?2- Такой путь решения приведен
в книге [1, с. 155].
2. Более компактное решение задачи B3) дано в
примере 8 следующего параграфа.
3. Целевая функция правильной ЗЛП Lo
/о (х) = 10*! + 12*3 + 7*5
не имеет отрицательных коэффициентов. Поэтому
тривиальный опорный план
х = х° = @, 2, 0, 3, 0)
задачи Lo обеспечивает минимальное значение f% = —13
целевой функции <*, с> исходной задачи B3). Таким
образом, для задачи B3) имеем
-13 < <*, с} < 1/10, жей,
где D — множество допустимых планов, которое задано
первыми двумя строками таблицы B3).
4. Получим формулы результирующего
преобразования L -> L2. Приведем выкладки лишь для последней
строки ЗЛП:
/« = /i- -?-*. = (/о-
= (/' + 3q>') - Ю (фо/3) fj- С^о — Ф1)=
Зф^Ф^^ + (
X 11 . I 7
^-Чо-^ + То-Ф-
Здесь использованы очевидные соотношения
Аналогичным образом получая формулы для г|>2 и ф2,
придем к такому результату: ЗЛП L2 может быть
получена из ЗЛП L, заданной таблицей B3), по формулам
3 , 1 ,
11
5. Первый буквенный столбец в табличной записи ЗЛП
L, I/, LQ, Lx, L2 нам потребовался для упрощения пояс-
25

нений проводимых преобразований. В дальнейшем в
большинстве примеров этот столбец не будет выписываться.
Алгоритм данного параграфа всегда приводит к
решению задачи, если исходная задача является правильной
ЗЛП и в процессе решения не встречается так
называемого вырождения задачи — появления нулевых координат
у вектора аг для очередной вспомогательной ЗЛП Lt —
= L {Ai, аг, с\ Xt}. Если исходная задача не является
правильной ЗЛП, то ее следует предварительно
преобразовать в правильную ЗЛП, как это сделано, например,
в примере 7 (преобразование L -> Lo). Однако часто такое
преобразование провести весьма непросто. В следующем
параграфе описывается алгоритм, свободный от этого
недостатка.
§ 3. Алгоритм решения канонической ЗЛП
Если описание алгоритма предыдущего параграфа
дополнить еще одним правилом, которое приводится ниже,
то алгоритм можно применять для решения произвольных
канонических ЗЛП.
Пусть исходная ЗЛП Lo является канонической ЗЛП
и последовательность B1) строится по правилам
предыдущего параграфа. При выполнении неравенства cv ^ 9
возможны две ситуации.
1. Промежуточная ЗЛП Lv является правильной ЗЛП.
В этом случае задача решена и тривиальный опорный
план задачи Lv является оптимальным планом исходной
ЗЛП Lo.
2. Промежуточная ЗЛП Lv остается канонической
неправильной ЗЛП. При этом проводят следующее
преобразование Lv-> Lv+1, которое, как и ранее, заключается
в исключении из всех строк, кроме ведущей к-й строки,
ведущей переменной xt. Однако здесь уже используется
иное, чем прежде, правило выбора ведущей позиции /с, t.
Приведем это правило.
1. Вычеркиваются все строки ЗЛП Lv, которые
содержат ненулевые элементы правильных столбцов.
Правильным столбцом ЗЛП назовем столбец, содержащий
единственный ненулевой элемент.
2. Для каждой из оставшихся строк ведущим
объявляется максимальный элемент этой строки.
3. Из ведущих элементов строк в качестве ведущего
элемента alt преобразования Lv —>- Lv+1 выбирается
такой, который обеспечивает минимальное уменьшение па-
26

раметра %v при исключении соответствующей переменной
из последней строки ЗЛП Lv.
Алгоритм заканчивает свою работу, когда очередная
ЗЛП Ljj, оказывается правильной и для нее с^ ^ 0.
В примере 8 описанным здесь алгоритмом решается
ЗЛП из примера 7. При этом потребовалось провести лишь
два преобразования (Lo -> L± -> L2) вместо четырех в
примере 7.
Пример 8.
3
2
3
1
—1
0
1
—2
1
4
1
1
0
-3
—1
4
= 1/3
1/3
1/3
7/3
4/3
7*
1 О
О 1
—7/3
1
О
—10/3 —13/3 —3 0
11/3
2/3
/* — 8/3
0 —31/10 —27/10 —23/10 0
11/10
3/10
/* —1/10
Здесь и в дальнейшем ведущий элемент для очередного
преобразования отмечается прямоугольной рамкой. Для
ЗЛП Lo ведущий элемент а\ъ = 3 выбирался по правилам
§ 2. ЗЛП Lx не является правильной и в то же время для
нее с1 ^ 0 (в последней строке нет положительных
элементов). Поэтому ведущий элемент а\г = 10/3 выбирался
по правилам данного параграфа: вычеркивалась вторая
строка ЗЛП Ьх (поскольку она содержит ненулевой
элемент Й25 = 1 в правильном пятом столбце), а в
оставшейся первой строке элемент а\г = 10/3 является
максимальным.
Преобразование Lx ->• L2 приводит к правильной ЗЛП
L2, у которой с2 ^ 0. Поэтому тривиальный опорный план
ЗЛП Ь2 (см. решение примера 7) дает решение задачи.
При этом элементы столбцов матрицы Л2,
соответствующие отрицательным элементам в последней строке ЗЛП
L2, можно не вычислять.
Упражнение 4. Проведите теоретическое исследование
описанного здесь алгоритма, в частности докажите либо
опровергните следующие утверждения.
Гипотеза 1. Алгоритм данного параграф! за конечное
число тактов получает решение (если таковое существует) любой
канонической ЗЛПУ если процесс решения не приводит к случ.ю
вырождения ЗЛП.
27

Гипотеза 2. При этом число тактов алгоритма не
превосходит N, где:
а) N — п — число столбцов матрицы А0;
б) N = т — число строк матрицы А0.
Указание. Для опровержения любой гипотезы
достаточно построить хотя бы один пример, для которого утверждение
гипотезы оказывается ложным»
§ 4. Несколько примеров
Основу описания процедуры решения нижеследующих
примеров составляет последовательность таблиц Lo,
Lu . . ., Z/д. Переход от предыдущей таблицы к
последующей проводится согласно алгоритму, описанному в § 2, 3.
Словесные пояснения даются лишь по поводу
характерных особенностей данной конкретной задачи. Исходные
данные каждого (кроме последнего) примера заданы
таблицей Lo. В правом нижнем углу таблицы Lo вписывается
/*, если решается задача на максимум целевой функции,
либо /°, если решается задача на минимум целевой
функции. Во всех таблицах вместо нулей используются точки.
Пример 9.
2 3-1 |2| 1
Т = 1 -2 5 -3 •
0 4 10 3 1 •
4
1
4
3
.
3/2
5/2
17/2
—4
-1/2 1
7/2 .
|7/2| •
4 .
1/2
3/2
-1/2
—1
2
7
6
—4
10/7 19/7 •
1 —6
6/7 17/7 1
3/7
-1/7
— 24/7
1/2
—96/7 •
—3
. —3/7
. 1 .
. . 1
20/7
1
12/7
37/14
1/2
25/14
—45/14 —105/7 • • • —149/14
х* = @, 0, 25/14, 37/14, 1/2), f% = 149/14.
Данная задача (таблица Lo) получена путем
отбрасывания слагаемых с переменными #6, х7 в задаче из книги
[10, с. 73]. Интересно отметить, что /В и оставшиеся коор-
28

динаты оптимального плана х* при этом не изменились.
Случайно это или закономерно (если учесть, что х* =
= $ = 0)?
Пример 10.
4
1
16/10
26/10
8/10
2
1
4
2
to со
и
—1
*—1
5
3
3
2 1
-3 •
1 •
2 •
8/10
18/10
4/10
1
—19/10 17/10
|56/10| —28/10
3/10 1/10
24/10
9/28
33/10
1 —1/2
21/10
1
8/10
75/56
15/4
139/56
13/28
37/56
—41/56
x° = @, 37/56, 13/28, 0, 139/56), fD = 41/56.
В данном примере вычисляется минимум fr> = / ()
целевой функции / (х) — <#, с> (сравните результаты
данного и предыдущего примеров). При этом алгоритм
получения решения фактически остается прежним. Однако
поскольку решается противоположная ЗЛП (вместо f%
вычисляется Д), то и цели промежуточных
преобразований также изменяются на противоположные, а именно
стремятся в конечном итоге получить правильную ЗЛП
Ly, = L {А», а», с*1, ^}, у которой с» > Э.
В первую очередь исключают отрицательные глементы
последней строки ЗЛП. При этом ведущий столбец
выбирается из условия максимального уменьшения параметра
% (максимального увеличения последнего элемента
последней строки таблицы Lt). Если в последней строке нет
отрицательных элементов, но текущая ЗЛП еще не
правильная, то очередное исключение проводят с помощью
максимального элемента в невычеркнутой строке (см. § 3).
Если таких строк несколько, то выбирают строку,
которая, во-первых сохраняет положительными элементы
последнего столбца таблицы Li+1, и, во-вторых, выбранная
строка должна приводить к минимальному увеличению
параметра X.
29

1
2
1
2
1
1
1
1
2
—3
1
—1
—1
1
1
—1
2
6
7
/°» /*
Пример 11 [8, с. 66, пример 88/9].
я0 - @, 33/8, 2У8, 21/8), fD = 5/4;
** - C, О, 1, 3), /d - 2.
В книге [8] дан неверный ответ для /#, х°.
Пример 12. Вычислить максимальное значение
целевой функции
/ (х) = xt + 2x2 B6)
при ограничениях
А /у» I <у <^~ V
х± + 2^2< 24,
ж1 + 4жа<401 B7)
Вводя в задачу B6), B7) дополнительные переменные
х3, . . ., #7, приведем ЗЛП B6), B7) к каноническому виду:
— х1
х3 = 2,
ж4 = 24,
хь = 40,
#6 = 5,
^7 = 6,
B8)
Далее, представляя каноническую ЗЛП B8) таблицей
Lo, проводим преобразования Lo —>• Ьх —>¦ L2:
1 1 • • •
2 • 1 • •
4 . . 1 .
1 • • • 1
1 -1
2
24
40
5
/*
30

• -3
3
5
1 —1
3
1 • • • 4
• 1 • • — 1
• • 1 • — 1
... 1 !
.... !
. . . . —1
26
18
32
11
6
—6
. . 1 1
. 1 . 1/3 ..
- . . —5/3 1 •
1
1 . . 1/3 - .
3
-1/3
2/3
1
2/3
44
6
4
11
12
—1
• |-24
Тривиальный опорный план ЗЛП L2
х* = A2, 6, 44, 0, 4, И, 0)
является оптимальным планом исходной ЗЛП Lo.
Однако для данной ЗЛП существуют и другие оптимальные
планы.
Целевая функция <х, с2> ЗЛП L2 обращается в нуль
при х± = 0. Остальные переменные не влияют на значение
целевой функции <х, с2>. Поэтому любое неотрицательное
решение системы из 5 уравнений (представленных
первыми пятью строками таблицы L2) относительно шести
переменных #!, х2, х3, хь, xq, Xi (ж4 = 0), является
оптимальным решением ЗЛП L2, а следовательно, и исходной ЗЛП
Lo. В частности, такими оптимальными решениями
являются
х* = (Ю, 7, 35, 0, 2, 8, 3),
я* = (8, 8, 26, 0, 0, 5, 6).
Отбрасывая последние пять (дополнительных) координат
в выписанных здесь оптимальных планах канонической
ЗЛП Lo, придем к следующим трем оптимальным планам
исходной ЗЛП B6), B7):
х* = A2, 6), х* = A0, 7), я* = (8, 8).
Значение целевой функции B6) для каждого из этих
планов равно f% = 24.
31

§ 5. В помощь преподавателю
Ниже даются некоторые рекомендации, облегчающие
составление задач для проведения контрольных мероприятий в студенческой
аудитории. Полезными оказываются следующие утверждения.
1. Если ЗЛП такова, что множество D допустимых планов
непусто и ограничено, то целевая функция <я, с> принимает на D
максимальное /d и минимальное j°D значения, которые, вообще говоря,
могут быть найдены описанными выше методами.
2. Если для канонической ЗЛП L {А, а, с} матрица А имеет
хотя бы одну строку с положительными элементами либо в строке
содержится только один нуль, а остальные элементы
положительны, то множество допустимых планов D ограничено (ЗЛП имеет
решение, если D ф 0).
Опираясь на эти утверждения, легко строить примеры ЗЛП,
которые заведомо имеют решения. Приведем конкретный пример
подобных построений.
Сконструируем каноническую ЗЛП L {А, а, с} с матрицей А е
е К3»5. Зададимся произвольным вектором х = B, 0, 4, 1, 0),
который будет одним из опорных планов конструируемой ЗЛП
(такой вектор должен иметь два нуля). Далее начинаем заполнять
матрицу А, строки которой обозначим через Лх, А2, Аъ. Пусть А2 >
1> 0. В остальных строках матрицы А могут быть отрицательные
элементы. Строку А2 заполняем произвольными положительными
числами и нулем.
— 2
1
4
а12
3
«32
3
2
1
— 5
0
— 3
2
<*35
3
10
9
Ci С2 СЪ С4 СЪ |
Величину я2 = 10 определим, вычислив скалярное произведение
<ЛХ1 х> = <A, 3, 2, 0, 2), B, 0, 4, 1, 0)> = 10.
Затем заполняем строки А1ч А3 сначала положительными числами,
а затем отрицательными так, чтобы скалярные произведения <Л1?
х} и <Л3, х} были положительными. Свободные члены ах и а3
вычисляем по формулам
ai = <^i» х>> аз = <^з> х),
В итоге получаем выписанную выше таблицу L. В этой таблице
буквенные обозначения а12, я15, я32, а35> ci> • • •» съ можно заменять
любыми числами — при этом получим конкретную ЗЛП, для
которой существуют fD и /р.
В связи с обсуждением критериев ограниченности множества
допустимых планов рассмотрим следующий пример.
Пример 13.
2
7 —И 8 1
1 —2 ПП -3 •
~«— . 2 -17 13 .
2—7 8 . . | /о
32
B9)

11/5 13/5 • 7/5
, _ 1/5 —2/5 1 -3/5
bl~ 17/5 —24/5 • 14/5
21/5
1/5
37/5
7/5
11/13
-4/5
1 .
. 1
7/13
19/5 .
5/13 .
1
•
7/5
21/13
11/13
197/13
- I 35/13
x° = @, 21/13, 11/13, 0, 0, 197/13),
fD = -35/13.
Здесь элементы последней строки таблицы L2 также не
нужно вычислять, так как при исключении элемента с\ =
= —4/5 в последней строке таблицы L± не может
возникнуть других отрицательных элементов, поскольку все
элементы первой строки таблицы L2 положительны.
По таблице исходных данных Lo непосредственно нельзя
сделать вывод о том, существует ли решение данной задачи. Однако
уже после первого преобразования LQ —> Lx такой вывод сделать
можно.
Из первой строки таблицы Ьг следует ограниченность
переменных #!, х2, #41 хь Для любого ieD. Поскольку хъ х2, #4
ограничены, то из второй строки таблицы LL следует ограниченность
переменной ж3, а из третьей строки — ограниченность #в. Таким образом,
D ограничено и для ЗЛП с исходными данными B9) существуют как
i% так и /*.
Приведем и второе решение (на максимум) ЗЛП B9):
* /п 1 27 197 п п\ ,* 129
х =(°'Т0 ' 14 • "ТОГ' °. °). Ь=ТГ-
Для получения сборника задач с ответами
целесообразно составить специальную программу решения ЗЛП на
ЭВМ без использования округлений. Такая программа
может оказаться полезной и при решении плохо
обусловленных задач, для которых обычный путь решения ведет
к недопустимо большим погрешностям. Наиболее
рациональный путь построения такой программы заключается
в использовании алгоритма решения ЗЛП в целых
числах. Проиллюстрируем применение этого алгоритма на
процедуре решения задачи из предыдущего примера.
33

П р и м е р 14.
ф
ф
1
•
7
2
2
—И
5
—17
8
—3
13
1
•
•
1
2
1
4
h
11
1
17
7
2
13
-2
—24
4
—7
5
•
•
8
7
—3
14
19
• •
5 •
• •
• 5
/и
5
21
1
37
Ф2
ф*
^2
h
11
13
•
65
•
•
5
•
•
65
21
55
985
65/?,+
175
Lo=
Здесь преобразование Lo
проведено по формулам
а1 = 5а + 17ф, /х = 5/ + 7-ф;
преобразование L^ ->¦ />2 — по формулам
Ф2 = фх, г|J = 13фх + 2ф1ч
а2 - 13ах + 24Фх, /2 - 13/г + 4Ф1.
Ненулевые координаты искомого плана х° получим
делением элементов последнего столбца таблицы L2' на
ненулевые элементы правильных столбцов этой таблицы:
х\ = 21/13, 4 = 55/65, xl = 985/65.
Минимальное значение fD целевой функции получим,
приравняв нулю выражение в правом нижнем углу
таблицы L2;
65/°d + 175 = 0, т. е. fD = -175/65.

Глава II
ТРАНСПОРТНАЯ ЗАДАЧА
§ 1. Постановка задачи. Система обозначений
Привэдем экономическую формулировку транспортной
задачи. Имеется т поставщиков груза At (i = 1, . . ., т)
и п потребителей груза Bj (/ = 1, . . ., п). Весь груз
является однородным и измеряется в одних и тех же единицах
(это либо количество вагонов груза, либо число тонн
груза и т. д.) Приведем конкретные примеры триады
«поставщики — потребители — груз»:
1) карьеры — бетонные заводы — гравий;
2) овощные базы — магазины — капуста.
Здесь отметим, что транспортная задача (ТЗ) имеет
многочисленные приложения и в терминах ТЗ могут
формулироваться и такие задачи, которые никакого отношения
к перевозкам грузов не имеют. За подробностями отсылаем
читателя к обширной литературе по математическому
программированию, содержащей описание транспортной
задачи, в частности к книгам [5, 10].
От каждого поставщика At груз может поставляться
любому потребителю Bj. Через ctj обозначим стоимость
перевозки единицы груза от поставщика A t к
потребителю Bj. Через xtj обозначим объем перевозки от поставщика
Аг к потребителю Bj {xtj — число единиц груза).
Числовую матрицу X = {%ij} будем называть планом перевозок
или матрицей перевозок, числовую матрицу С = {ctj} —
матрицей стоимости.
Предполагается, что суммарный объем груза у
поставщиков в точности равен суммарной потребности этого
груза у потребителей. Любой план X, который обеспечивает
вывоз всего груза от поставщиков потребителям, назовем
допустимым планом. Суммарная стоимость всех
перевозок по любому допустимому плану X определяется
35

формулой
A)
В ТЗ требуется найти такой допустимый план, по
которому суммарная стоимость перевозок была бы
минимальной. Этот план, обеспечивающий минимальное значение
функции A), будем называть оптимальным и обозначать
через Х°.
Дадим теперь математическую формулировку
транспортной задачи. Компонентами всех векторов и матриц
данной главы являются целые неотрицательные числа (за
исключением векторов и матриц, обозначаемых в § 4
буквами М, |х, Л, X, которые могут иметь отрицательные
компоненты). Исходные данные любой ТЗ задаются
матрицей стоимости С = {ctj}, вектором поставок а = {at}
и вектором потреблений Ъ = {bj} (i = 1, . . ., т; j =
= 1, . . ., п). Для обозначения ТЗ будем использовать
букву Т, а для обозначения ТЗ вместе с ее исходными
данными будем использовать дге формы записи:
При этом Тг и Т2 — две различные ТЗ, если они имеют
различные исходные данные, например различаются
матрицей стоимости:
Тх = Т {С, а, Ъ), Т2= Т {С, а, Ъ].
Приведем численный пример транспортной задачи:
7 8 5 3
2 4 5 9
Т {С, а, Ъ) = 6 3 1 2
5 9 9 7
11
11
8 =
Здесь
[7 8 5 31
2 4 5 9,
6 3 1 2J
а = (аи а2, аг) = (И, 11, 8),
Ъ = (Ь„ Ь8, Ь3, К) = E, 9, 9, 7).
Отметим, что с математической точки зрения совершенно
безразлично, какой из двух векторов, а или Ь, называть
36

вектором поставок, а какой — вектором потреблений. На
решении задачи это никак не отразится.
В гл. I мы уже пользовались скалярным произведением
двух векторов, под которым понимается число, равное
сумме произведений одноименных координат этих векторов.
П р и м е р 1. Ъ = E, 9, 9, 7), d = B, 4, 0, 3), е =
= A,1,1,1);
<6,d> = 5-2 + 9-4+ 9-0 + 7-3 = 67,
<Ь,6>> = 5-1 + 9-1 +9-1 + 7-1 = 30.
Опуская в последнем скалярном произведении обозначение
единичного вектора е, придем к такой записи:
= 5 + 9 + 9 + 7 = 30.
Таким образом, заключение вектора в угловые скобки
будет означать число, равное сумме координат этого
вектора. Например, если а = A1, 11, 8), то <а> = 11 + 11 -+-
+ 8 = 30.
Ниже рассматриваются только такие транспортные
задачи Т {С, a, &}, для которых выполняется условие <а> =
= <Ь>. Такие ТЗ называются транспортными задачами
закрытого типа.
По аналогии со скалярным произведением векторов
вводится скалярное произведение матриц.
Скалярным произведением двух матриц называется
число, равное сумме произведений одноименных (с
одинаковыми индексами) элементов этих матриц. Для
обозначения скалярного произведения матриц также
используются угловые скобки.
Пример 2.
! fl,
Г&п Ь12 Ь1г1_Г2 4 27
U21 ь22 ь23] — [г о ij '
<4,5> = 3.2+1.4+4.2+2.3+5.0+3.1=27.
В каждой матрице можно выделить векторы,
составляющие строки этой матрицы, и векторы, составляющие ее
столбцы. Для обозначения вектор-строки матрицы
используется символ (буква), обозначающий эту матрицу,
снабженный вверху точкой, внизу — натуральным индексом,
который указывает номер строки. Если в подобном
обозначении вместо одной точки используются две точки над
буквой, то будем считать, что это вектор-столбец матрицы.
37

Пример 3. Для матрицы А из примера 2 имеем
Ai = («ш «i2» «is) = C, 1, 4),
А2 = (а21, а22, а23) = B, 5, 3),
Аг = («и, «12O ^2 = («12» «22)»
^8 = («13» «23) = D, 3),
<Л> =,3 + 1+4 = 8, <Л2> = 10,
<Л2> = 1+5-6, <ЛГ3> = 7.
Допустимым планом, транспортной задачи Т {С, а, й}
(С ЕЕ R™n) назовем любую матрицу X е Rmn, если
<Zf> — flf, г = 1, . . ., m;
<Z7> = bh j = 1,. . ., п.
Множество всех допустимых планов задачи Т {С, а, Ъ)
обозначим через D. Особо отметим, что множество
допустимых планов не зависит от элементов матрицы С
и всецело определяется заданием векторов а и Ъ. Отражая
этот факт, будем иногда множество D записывать в виде
D {а, Ъ}.
Для любого допустимого плана ХеД транспортной
задачи Т (С, а, Ъ) определена функция A), которую будем
называть целевой функцией. Целевую функцию / (X)
можно записать также в виде
/ (X) = <С, ХУ = <Х, СУ. B)
Матрицу Х° ЕЙ назовем оптимальным планом задачи
Т {С, а, Ь}, если
=fD = min «С, X».
Теорема1. Для любой ТЗ существует
оптимальный план.
Пример 4. Транспортная задача
3 4
1 6
C)
3 3 |
имеет только три допустимых плана:
ГЗ 1] Г2 21
l=[o 2j' X2==U 1-Г X3=
i 3"
38

На этих допустимых планах целевая функция принимает
следующие значения:
/ (Хг) = <С, А\> = 3-3 + 4-1 + 1-0 + 6-2 - 25,
/ (Х2) = <С, Х2У = 3-2 + 4-2 + 1-1 + 6-1 = 21,
/ (Х3) = <С, Х3> - 3-1 + 4-3 + 1-2 + 6-0 - 17.
Таким образом, для ТЗ C) имеем
D = {Х^ Х2У Х3},
X° = Xz=[l о]' /?> = 17.
J/d=25.
Обычно целью решения ТЗ является отыскание
оптимального для этой ТЗ плана Х° и минимального значения
целевой функции fjj. В некоторых случаях требуется
определить максимальное значение целевой функции /? и
допустимый план X*, на котором это максимальное значение
достигается (X* также называют оптимальным планом).
В заключение отметим, что ТЗ может иметь один (как
в примере 4) оптимальный план Х°, несколько
оптимальных планов либо даже все допустимые планы данной ТЗ
могут оказаться оптимальными.
Упражнение 1. Доказать, что при любых векторах а
и Ь целевая функция / (X) транспортной задачи Т {С, а, Ъ}
сохраняет постоянное значение на множестве допустимых планов D {о, Ь},
если только разность каждой пары соседних строк матрицы
стоимости дает один и тот же вектор вида (к, X, . . ., К), т. е.
Ск+г ~Ск= (К\К ...,>), к = 1, 2, . . ., /тг — 1.
Пример 5. Вычислить значения целевой функции
B) на всех допустимых планах следующей ТЗ:
1
4
7
2
5
8
3
6
9
2
3
2
4 1 2
Ответ: / (X) = 33 для любого

§ 2. Построение допустимого плана ТЗ
по методу минимальных элементов
При построении допустимого плана ТЗ естественно
стремление построить такой допустимый план,
стоимость перевозок по которому была бы как можно
меньше. Исходя из этого целесообразно назначать перевозки
по маршрутам с минимальной стоимостью перевозок.
Эти соображения приводят к методу минимальных
элементов.
Процедура метода минимальных элементов
заключается в следующем. Пусть c^t — минимальный элемент
матрицы стоимости С исходной ТЗ. Позиция к, t объявляется
ведущей и определяет положение очередного ненулевого
элемента x^t искомой матрицы X. В качестве величины x^t
принимается максимально допустимая перевозка по
данному маршруту
хы = min {ak, bt}.
Далее переходим к очередной промежуточной ТЗ,
которую получим из исходной ТЗ после того, как
перевозка Xkt выполнена. К этой вспомогательной
промежуточной ТЗ вновь применяем описанную выше процедуру,
принимая полученную промежуточную ТЗ за исходную,
и т. д. Рассмотрим применение этого метода на конкретном
примере.
Пример 6. Используя метод минимальных
элементов, построить допустимый план X следующей ТЗ:
7
2
6
5
8
4
3
9
5
5
1
9
3
9
2
7
И
И
8
D)
Результатом решения является такая матрица:
E)
Г- 3 1 71
=L5e8:J'
Здесь под точками понимаются нули. Ненулевые элементы
матрицы X вписывались в эту матрицу в такой
последовательности: 8, 5, 7, 6, 1, 3.
40

Приведем последовательность промежуточных ТЗ,
появлявшихся в процессе решения:
11 =
7
2
6
5
8
4
3
9
5
5
1
9
3
9
2
7
11
11
8
7
CNII
•
8
4
5
5
X
3
9
11
11
5 9 17
Т -
1 3 =
8 5 3
4 5 9
• X •
9 1 7
11
• 8
X 4
•
9
5 X
5 •
X •
1
4
6
• 8 5 X
,хх-
• X •
1
• 8 X X
Т _Х Х * '
1 G— . X '
Прокомментируем первый такт алгоритма. В исходной ТЗ
минимальным элементом является с33 = 1. Этот элемент
подчеркнут. В матрицу X вписывается элемент
х33 = niin {a3, Ъ3) = min {8, 9} = 8.
Далее переходим от ТЗ Тг к ТЗ Т2 следующим путем:
1) вычеркиваем третью строку ТЗ Т±, поскольку со
«склада» А3 вывезен весь груз;
2) получаем вместо Ь3 новое значение Ъ3 по формуле
К = Ъ3 — а3 = 9—8 = 1,
поскольку в «магазин» В3 поступило 8 т «капусты» и
неудовлетворенная потребность «магазина» В3 теперь равна
1 т.
Крестиками в промежуточных ТЗ указаны уже
заполненные к данному моменту позиции матрицы X.
При практическом решении подобных задач можно
пользоваться более компактной, по сравнению с
вышеприведенной, записью, совмещая все промежуточные ТЗ
в одном рисунке. Так, для рассмотренного примера вместо
отдельного выписывания всех промежуточных ТЗ Т1 — TQ

можно использовать такую запись:
2 6 5 3
6
4
1
7
2
6
5
0
8
4
3
9
3
0
5
5
1
9
1
0
3
9
2
7
0
11
11
8
4
6
0
3 0
0
Здесь цифры слева и сверху над матрицей С указывают
тот порядок, в котором появлялись нули справа и снизу
от матрицы С. Вместо подобней нумерации можно после
каждого такта алгоритма просто вычеркивать
соответствующую строку или столбец.
Нетрудно убедиться, что найденный по методу
минимальных элементов план E) является допустимым для ТЗ
D) и стоимость перевозок по плану E) равна
<Х, С) = 3-8 + 1-5 + 7-3 + 5-2 + 6-4 + 8-1 = 92.
Для сравнения приведем еще два допустимых плана:
Г5 6 • -1 Г- 9 2 1
Хе = \- 3 8-, Х*= • • 4 7.
L- • 1 7J 1.5 • 3 J
План Xg получен методом северо-западного угла (см. [5,
с. 97]), план X* является наихудшим (для задачи на
минимум) допустимым планом. Значения целевой функции
для этих планов:
(Xg, С> = 150, <Х*, С> = 198.
§ 3. Метод добротностей
Описываемый ниже метод добротностей, так же как и
метод минимальных элементов, служит для построения
допустимого плана. Однако метод добротностей обычно
приводит к лучшему допустимому плану. Более того, для
транспортных задач небольшой размерности метод
добротностей, как правило, непосредственно приводит к
оптимальному плану ТЗ. Для описания метода добротностей
нам потребуются новые понятия.
Матрицу, каждая строка и каждый столбец которой
содержат хотя бы один нуль, будем называть матрицей
запуленного типа.
42

Рассмотрим следующую последовательность матриц:
С С С"
Г4 5 2 01гГ4 3 2 (Л
-* I 0 2 3 7 -> 0 0 3 7 .
L5 2 0 lj L5 О О 1J
Вторая матрица получена из первой вычитанием из всех
элементов каждой строки минимального элемента этой
строки. Такое преобразование матриц обозначим через IT.
Третья матрица получена из второй вычитанием из всех
элементов каждого столбца минимального элемента этого
столбца (преобразование П"). В результате получена
матрица С" зануленного типа. Очевидно, что
последовательность преобразований ГГ, IT переводит любую матрицу
в матрицу зануленного типа. Через Пэ обозначим
описанную выше процедуру преобразования произвольной
матрицы С в матрицу С" зануленного типа (Пэ = П"ГГ).
Преобразование вида П'П" также зануляющее. При
этом будет получена иная матрица зануленного типа.
Добротностью к-й строки транспортной задачи
Т {С, а, Ъ) назовем произведение числа ак на сумму двух
минимальных элементов k-ik строки матрицы С.
Добротностью к-го столбца задачи Т {С, а, Ъ) назовем
произведение числа Ьк на сумму двух минимальных
элементов к-то столбца матрицы С.
По методу добротностей формирование ненулевых
компонент xkt искомого допустимого плана ХДб = {%ij}
и промежуточных ТЗ проводится так же, как и по методу
минимальных элементов. Изменяется лишь способ выбора
очередной ведущей позиции (индексного номера
очередной ненулевой компоненты x^t), и для каждой
промежуточной ТЗ (при необходимости), в том числе для исходной
ТЗ, проводится еще зануление матрицы стоимости. Детали
метода добротностей поясняются на примере.
Пример 7. Применяя метод добротностей,
построить допустимый план ХДб для ТЗ из примера 6.
Процесс решения представлен ниже
последовательностью промежуточных ТЗ:
20 0 18 7
7
2
6
8
4
3
5
5
1
3
9
2
11
11
8
пэ
22
0
0
4
0
5
3
0
0
2
3
О
0
7
1
11
11
8
5 9 9 7
5 9 9 7
43

4
0
5
3
0
0
2
3
0
X
4
11-
8
По4
10
2
0
5
0
1
0
0
0
0 X
3
0
4
11
8
9 9
О О
5 9 9
3 О
4
18
0
X
1
0
0
0
3
0
X
4
6
8
4
0
X
1
X
0
0
0
X
9
X
0
9
X
0
X
3 9
[. о \ П
L 3 5 -J
Здесь сверху и слева от матриц стоимости выписаны
добротности соответствующих строк и столбцов. На
каждом такте алгоритма в качестве ведущей позиции
объявляется позиция того нуля матрицы зануленного типа,
который находится в строке или столбце с максимальной
добротностью. Ведущий нуль в каждой матрице
подчеркнут. При этом ненулевые позиции искомого плана ХДб
заполнялись в следующем порядке:
', #21 = 5, Ь, 4, О, #33 = ^*
Очевидно, что построенный план ХДб является
допустимым для ТЗ D), а значение целевой функции для этого
плана равно
<Хдб, С> = 4-5 + 7-3 + 5-2 + 6-4 + 3-3 + 5-1 = 89.
В § 5 будет показано, что план ХДб является не только
допустимым, но и оптимальным, т. е.
2 О = 89.
где С, С S Rmn,
\ 7= !>• • •> л. F)
§ 4. Некоторые свойства ТЗ
Две матрицы С = {с^}, С'=
назовем эквивалентными, если
44

Условие эквивалентности F) можно записать в форме
с = с + м - л, с, с, Мь л е R", G)
Л =
Матрицу М будем называть столбцевой матрицей,
матрицу Л — строчной матрицей. При этом матрица М
порождается вектором [л = (jxl7 . . ., |х7П); матрица Л
порождается вектором X = (Ки. . ., Хп).
Вычисление матрицы С' по формуле F) или G) будем
называть эквивалентным преобразованием матриц. Для
обозначения эквивалентного преобразования матриц
будут использоваться буквы Р и П. Так, например, запись
С" = PC будет означать, что матрица С вычисляется по
формуле G). Эквивалентное преобразование G) назовем
допустимым, если матрицы С" и С не имеют
отрицательных элементов. Ниже будут использоваться только
допустимые эквивалентные преобразования.
Эквивалентное преобразование G) вполне определено
заданием двух векторов
[д. = (|А11в . ., цт), X = (Кг,. . ., Хп).
Отражая этот факт, иногда эквивалентное преобразование
Р будем записывать в виде Р {ц, X} или Р \Н.
Лемма 1. Если
iGfl {а, Ь}, аЕГ, &GRn,
то справедливы формулы
<Z, M> = <af |i>, (8)
<Х, Л> = <Ь, Х>. (9)
Например, формулу (8) получим, проведя следующие
выкладки:
Мг = (|Ai, |ii,. • ., |*i) = Hi A,1,. . ., 1) = Hi**
М2 = [л2е,..., Мт = \Lme, е е Rw;
= <Xif Mi)
45

Формула (S) доказана. Точно так же доказывается
формула (9), при этом вместо величин Xh Mt используются
величины Xj, Aj.
Транспортные задачи Т {С, я, Ь} и Т {С, а, Ь} назовем
эквивалентными, если эквивалентными являются
матрицы стоимости этих ТЗ, т. е. если С" = PC.
Теорема 2. Оптимальные планы эквивалентных ТЗ
совпадают.
Через D0 {С, а, Ъ} обозначим множество оптимальных
планов задачи Т {С, а, Ъ). Дадим теперь другую
формулировку теоремы 2.
Теорема 2. D0 {С, а, Ъ) = D0 {С, а, Ь}, если С =
Доказательство. Проведем доказательство
методом от противного. Пусть U — оптимальный план
задачи Т {С, а, 6}, и предположим, что U не является
оптимальным планом задачи Т (С\ а, Ь}, где С" = PC. Это.
означает, что существует матрица V ЕЕ # (а, Ь}, для
которой выполняется неравенство
<F, C> < <С/, С'У. A0)
На основании формул (8) и (9) имеем
«У, м> - <У, М> = <а,. li>1 A1)
<t/, Л> = <У, Л> - <Ь, Х>. A2)
Далее, используя формулы G), A1), A2) и свойства
скалярного произведения, получим
<С/, С> = <?/, С + М - Л> =
= <6Г, С> + <U, МУ - <U, Л> =
= <С/, О + <а, ц> - <Ь, X), A3)
<7, С> = <у, С + М - Л> = <F, C> +
+ <у, Л/> - <У, Л) = <F, С> + <а, ц> - <Ь, Я>. A4)
Подставляя A3), A4) в неравенство A0), придем к
неравенству
<v, О < <Е/, о,
что противоречит оптимальности плана U для задачи
Г {С, a, fe}. Теорема доказана, поскольку свойство
эквивалентности двух матриц является взаимным.
Опираясь на теорему 2, легко доказать, что имеет место
Теорема 3. Если:
1) С = PC;
46

2) U e D {а, ft};
3) <?/, СУ = О,
то U(EEDo {С, а, ft}.
Теорема 3 является основным утверждением, на
которое опирается излагаемый в следующем параграфе
метод построения оптимального плана ТЗ. Для описания
этого метода нам потребуется ряд вспомогательных
понятий и обозначений.
Зафиксируем две матрицы С, С" ЕЕ Rmn и определим
функцию ср:
ф (X) = <х, о - <х, о, х е R™.
Л е м м а 2. ЕЪш С" = PC, то функция ф (X)
сохраняет постоянное значение па множестве допустимых
планов D {а, ft} (а GRm, !?G Rn).
Доказательство. Пусть X ЕЕ D {а, Ь}.
Проведем выкладки
С = С + М - Л, С - С = Л - М, ф (X) - <Х, С> —
- <х, о = <х, с - су = <х, л -
н
Лемма доказана, так как значение функции
Ф (X) = <Ь, ^> - <а, ^> A5)
при X G В {в, 6} не зависит от X.
Значение A5) функции ф (X) на D назовем разностью
потенциалов задач Т {С, a, ft} и Г {С, а, ft}, a
минимальное значение целевой функции транспортной задачи на
множестве допустимых планов D {a, ft} назовем
потенциалом этой ТЗ. Для обозначения потенциала ТЗ будем
использовать букву Ф. Таким образом, для задачи Т =
= Т {С, a, ft} ее потенциал определяется формулой
ф = ф{Г} = min «X, СУ) =/?,.
Если рассматривать значения потенциала для
различных эквивалентных ТЗ, то потенциал ТЗ превращается
в функцию матрицы стоимости, т. е. Ф = Ф (С). Особую
роль в дальнейшем будут играть транспортные задачи
f = Т {С, a, ft}, эквивалентные исходной задаче Т {С, я,
ft} и обладающие нулевым потенциалом (Ф (С) -— 0, где
С — PC). Эквивалентное преобразование Р, которое
приводит к ТЗ с нулевым потенциалом, будем называть
минимизирующим. Практически минимизирующее пре-
47

образование Р получают как последовательность более
простых полезных преобразований (Р = РкРк„г . . . Р-^.
Эквивалентное преобразование Р = Р {\л, X} назовем
полезным для задачи Т = Т {С, а, Ъ), если оно ведет к
транспортной задаче Т' = Т {С, а, Ъ) с меньшим потенциалом,
т. е. если Ф {Т'} < Ф {Т}, где С = PC.
Назовем стоимостью преобразования Р — Р {\i, X}
величину
А (Р) = <Ь, Х> - <о, [i>. A6)
Отметим, что стоимость преобразования Р {|х, X} совпадает
с правой частью соотношения A5). Используя понятие
«стоимость эквивалентного преобразования», можно
сказать, что преобразование Р {\л, X} является полезным, если
Д (Р) > 0.
Упражнение 2. Докажите последнее утверждение.
Вектор назовем квазиединичным, если его
координатами являются нули и единицы. Множество всех
квазиединичных векторов обозначим буквой В; запись \i ЕЕ
ЕЕ Вт означает, что \i — квазиединичный вектор, имеющий
т координат.
Простым преобразованием называется эквивалентное
преобразование Р {|х, X}, порождаемое квазиединичными
векторами |х и Я. Для обозначения простых преобразований
применяется буква П. При этом будут использоваться два
вида простых преобразований П и П, которые
определяются следующими формулами:
1) если С = ПС, то С = С + М — Л;
2) если С = ПС, то С = С — М + Л.
Здесь \i?EBm, X е= Вп, П = П Цх, К} =П {?} , П =
Два квазиединичных вектора [х и jl называются
сопряженными, если |Л + ]Х = е.
Теорема 4. ?Ъш для задачи Т {С, а, Ь} простое
преобразование Р = П {(I, Х} является полезным, то
сопряженное простое преобразование Р = П {}Х, А,} также является
полезным для задачи Т {С, а, Ъ) и имеет ту же стоимость,
т. е. Д (Р) = А (?). З&кь р, = е — р; X = в — X; а е Лт;
Приведем примеры простых преобразований.
48

Пример 8. Вычислить матрицу С = П^, если
Г4 3 2 01
=\ 0 0 3 7.
L5 0 0 lj
Согласно формуле A7) преобразование Пх добавляет
единицу во вторую и третью строки и вычитает единицу
из первого, второго и третьего столбцов. При этом из
матрицы С будет получена матрица С вида
13 2 1 01
0 0 3 8.
5 0 0 2J
A8)
Можно сказать, что матрица С получена добавлением
к каждому столбцу матрицы С вектора \i = @, 1, 1) и
вычитанием из каждой строки вектора А, = A, 1, 1, 0).
Пример 9. Вычислить матрицу С = П2С, если
Г4 3 2 01
'= 0 0 3 7.
[_5 0 0 lj
Согласно формуле A9) преобразование П2 вычитает
единицу из первой строки и добавляет единицу в четвертый
столбец. При этом из матрицы С вновь будет получена
матрица С", задаваемая формулой A8). Таким образом,
преобразование П2 будет сопряженным преобразованием
по отношению к преобразованию И1 из примера 8 (см.
теорему 4).
Пример 10. Вычислить матрицу С" = П2С", где
матрица С" и преобразование П2 заданы формулами A8),
A9).
Добавляя единицу в четвертый столбец матрицы С
и вычитая единицу из первой строки, получим матрицу С":
ГЗ 2 1 ОТ Г2 1 0 О"!
С = о о з 8 JiX о о з 9 = с".
1Б 0 0 2j L5 0 0 3j
Здесь отметим, что матрица С" получена
последовательным применением преобразования П2 сначала к
матрице С, а затем к матрице С согласно формулам
С = П2С, B0)
С" - П2С B1)
4»

Подставив теперь в формулу B1) вместо С выражение для
С из формулы B0), получим
С" = П2С = П2 (П2С) = П2П2С = П3С,
т. е.
Таким образом, формулы
означают, что матрица С" получается из матрицы С
добавлением числа 2 в четвертый столбец и вычитанием двойки
из первой строки.
§ 5. Построение оптимального плана
Теорема 3 указывает удобный путь построения
оптимального плана ТЗ. Поскольку допустимый план и
матрица стоимости любой ТЗ не содержат отрицательных
элементов, то в теореме 3 условие <С7, СУ = 0 означает, что
ненулевые компоненты utj матрицы J7 расположены на
таких позициях (?, /), на которых расположены нули мат.
О 0
рицы С (если utj Ф 0, то ci;- = 0). Кроме того, задача
Т {С, я, Ь}, очевидно, обладает нулевым потенциалом. Эти
соображения подсказывают следующий путь построения
оптимального плана Х° для произвольной исходной
задачи Т {С, а, Ъ).
1. Вначале проводят зануление матрицы С, применяя
преобразование Пэ из § 3, т. е. получают матрицу Сх =
= ПЭС зануленного типа. Нетрудно проверить, что для
любой ТЗ преобразование Пэ является допустимым
полезным эквивалентным преобразованием.
2. Принимая за исходную задачу Тг = Т {Cj, a, b},
строят последовательность эквивалентных ТЗ 7\, 7,
Г3, ..., обладающую свойством
Ф{Г1}>Ф{Г2}>Ф{Г3}>. . . B2)
Наиболее просто такая последовательность строится
путем применения простых полезных преобразований.
Построение указанной последовательности ТЗ
продолжается, пока для очередной задачи Т}; не удастся найти
полезное преобразование.
50

3. Для последней в последовательности B2) задачи Тк
пытаются построить допустимый план, все ненулевые
элементы которого расположены на позициях нулевых
элементов матрицы стоимости транспортной задачи Тк.
Если это удалось сделать, то найденный таким образом
допустимый план является, согласно теореме 3, искомым
оптимальным планом для исходной ТЗ.
Пример 11. Найти оптимальный план для ТЗ из
примера 6. Вначале проводится зануление матрицы С:
7
2
6
8
4
3
5
5
1
3
9
2
И
11
8
4
0
5
3
0
0
2
3
0
0
7
1
И
И
8
= il »
5 9 9 7 I 5997 ]
To = Г {С, а, 6}, Тг= Т {Сг, a, 6}.
Проведение преобразования Пэ для данного случая
подробно описано в § 3. Здесь же отметим, что данное
преобразование Пэ есть эквивалентное преобразование
Р {|х, X}, определяемое формулами G), в которых следует
положить
[1 = (-3, -2, -1), X = @, 2, 0, 0).
Подобные рассуждения будем отражать такими
формулами:
Вычислим стоимость данного преобразования Пэ:
Д (Пэ) = <Ь, 1} - <а, ti> =
= <E, 9, 9, 7), @, 2, 0, 0)> - <A1, И, 8), (-3, -2, -
= 9-2 + 11-3 + И-2 + 8 = 81.
Следует подчеркнуть, что вычитание единицы из к-то
столбца (или к-й строки) есть элементарное полезное
эквивалентное преобразование, стоимость которого равна Ъ^
(или аъ для /с-й строки). Преобразование зануления Пэ
можно представить как последовательность (или, если
угодно, сумму) таких элементарных преобразований.
Каждое элементарное полезное преобразование ведет
к снижению потенциала ТЗ, а нашей задачей на первом
этапе решения является получение ТЗ с нулевым
потенциалом. Однако применять непосредственно элементарное
полезное преобразование к полученной промежуточной
Ы

транспортной задаче Тг с матрицей зануленного типа Сг
нельзя, так как вычитание единицы из любого столбца
и из любой строки матрицы Сг приведет к появлению
отрицательных элементов в матрице стоимости. Поэтому
построение дальнейших полезных преобразований
проводится путем комбинированного использования вредных и
полезных элементарных преобразований.
Элементарное преобразование назовем вредным, если
оно заключается в добавлении единицы к элементам какой-
либо строки или столбца матрицы стоимости. Стоимость
вредного элементарного преобразования является
отрицательным числом и равна (— ак) для к-й строки и (— Ьк)
для /с-го столбца. Вредное элементарное преобразование
ведет к повышению потенциала ТЗ.
Рассмотрим вновь промежуточную задачу Тг =
= Т {Сх, а, Ъ):
74 =
4
0
5
3
0
0
2
3
0
0
7
1
11
И
8
5 9 9 7
Проведем два последовательных преобразования
матрицы С±:
4
0
5
3
0
0
2
3
0
0
7
1
11
11
8
П'
4
0
5
3
0
0
2
3
0
1
8
2
И
И
8
П"
3
0
5
2
0
0
1
3
0
0
8
2
И
11
8
5 9 9 7
5 9 9 7
5 9 9 7
Здесь П' — элементарное вредное преобразование,
заключающееся в добавлении единицы в последний столбец
матрицы стоимости; П" — элементарное полезное
преобразование, заключающееся в вычитании единицы из
первой строки. Стоимость этих преобразований:
А AГ) = -7, А (П") = 11.
Вредное преобразование П' «закрыло» нуль в первой
строке и сделало допустимым проведение полезного
преобразования П". Поскольку «пользы» от преобразования П"
больше, чем «вреда» от преобразования П', то суммарное
преобразование Щ = П"П' будет полезным простым
преобразованием:
А (Пг) = А (П") + А (П") = 11-7 - 4,
ni=Mo:2;2.ib B3)
52

7*1 =
4
0
5
3
0
0
2
3
0
0
7
1
11
8
3
nt 0
—>• 5
2
0
0
1
3
0
0
8
2
11
11
8
5 9 9 7
5 9 9 7
Тг = Т
а,
Г2 = Т {С2, а, Ь}.
Ниже обозначения преобразования матриц будут при-
меняться и к транспортным задачам. Так запись Т2 =
= И1Т1 означает, что матрица стоимости С2 задачи Т2 =
= Т {С2, а, Ъ) получена из матрицы С± задачи Т1 =
= Т {Сг, а, Ъ) по формуле С2 = П^.
К задаче Т2 (см. B3)) вновь можно применить
преобразование П^ и получить очередную промежуточную ТЗ
по формуле Т3 = П1Г2« Однако, как уже отмечалось
в примерах 8—10, задачу Г3 можно получить также по
формулам
Тг =
4
0
5
3
0
0
2
3
0
0
7
1
11
11 _
8 —
2
X 5
1
0
0
0
3
0
0
9
3
11
11
8
5 9 9 7
5 9 9 7
Преобразование П3 для задачи Тг является полезным,
причем стоимость этого преобразования
А (П3) = 2-11-2.7 = 8.
Для полученной здесь задачи Т3 уже не удается найти
полезное преобразование, поскольку Т3 — транспортная
задача с нулевым потенциалом. Последнее выясняется
либо в результате перебора всех простых
преобразований, либо в результате выполнения заключительной
процедуры алгоритма — построения оптимального
плана для задачи Т3,
Строим допустимый для Т3 план X = {хи}, размещая
ненулевые элементы матрицы X на позициях нулевых
элементов матрицы стоимости задачи Т3 = Т {С3, а, Ъ).
При этом заполнение матрицы X начинают с тех нулевых
позиций матрицы С3, которые соответствуют
единственному в строке или столбце нулю. В данном случае «без
очереди» вписываются компоненты хи = 7 и х21 = 5.
После выполнения перевозок хи и х21 потребности первого
и четвертого «магазинов» полностью удовлетворены, а
53

промежуточная ТЗ имеет вид
X
1
0
0
0
3
0
X
4
6
8
9 9
Теперь «без очереди» вписываются компоненты х13 = 4,
^22 — 6. При этом приходим к промежуточной ТЗ
X X
X
X
о
3 5 | '
для которой уже заполняются позиции х32 = 3, х33 — 5.
В итоге получим оптимальный план
Г- . 4 71
Х° = X = 5 6 . .
L- 3 5 J
с нулевым значением целевой функции для задачи Г3%
т. е. <Х°, С3У = 0. Согласно теореме 3 найденный план
Х° будет оптимальным и для исходной задачи То =
= Т {С, а, &}, а оптимальное значение целевой функции
fD = <Z°, С) = 89
было уже подсчитано в примере 7.
После того как ТЗ уже решена, легко указать
минимизирующее преобразование Р, которое переводит исходную
задачу Го% в задачу Т3 с нулевым потенциалом (Т3 =
= РТ0). В самом деле, поскольку
Р = ПаПэ,
иэ — Г\ 0, 2, 0, 0
_ТТГ2, 0, 0 I рГ—2, 0, 0 1 _ Hi"!
113"" \0, 0, 0, 2\~ ^\ 0, 0, 0, — 2J ~ 1^1 '
то преобразование Р получим, вычисляя р, = р,' -f- jx",
X = Г + Г,
о, 2, 0,-
54

Используем данное преобразование Р:
7
2
6
8
4
3
5
5
1
3
9
2
11 о
И 1
8
2
+ о
5
1
0
0
0
3
0
0
9
3
11
11
8
5997| 5997|
Подсчитаем стоимость преобразования Р по формуле A6):
А (Р) = <Ь, ^> - <а, ji> = 9-2 - 7-2 + 11-5 + 11-2 +
+ 8-1 - 89.
Стоимость А (Р) можно посчитать и так:
А (Р) = А (Пэ) + А (П8) = 81+8-89.
Упражнение 3. Провести теоретическое исследование
эквивалентных преобразований, в частности доказать формулы
А (Р) = fD\
Д (Р) = Д (i>x) + Д (Р2) + Д (Р3), если Р = Р3Р2Рг.
Пример 12. Вычислить fD для следующей ТЗ:
= Т{С,а,Ъ} =
7
5
4
11
1
3
8
2
2
7
1
2
10
3
6
9
12
13
12
12
24 11 7 7 |
Выполним процедуру зануления матрицы С:
7
5
4
И
1
3
8
2
2
7
1
2
10
3
6
9
12
13
12
12
4
0
1
7
0
0
7
0
1
4
0
0
9
0
5
7
12
13
12
12
= ? 1
24 11 7 7
24 11 7
Для задачи 7\ можно указать три простых полезных
преобразования:
п. ГО, 1, 0, 01 ДШЛ —18-
111 — \1, 0, 0, 1] > &(Ui)— 1Й>
Упражнение 4. Для каждого из преобразований ГТ^
П2, П3 выпишите сопряженное простое преобразование.
55

Для очередного такта алгоритма можно использовать
любое из этих шести простых полезных преобразований.
Однако наиболее целесообразно выбрать преобразование
с максимальной стоимостью, т. е. Пх. Такая тактика
сокращает число тактов алгоритма — быстрее приводит к ТЗ
с нулевым потенциалом. Итак, для задачи Тг применим
преобразование Г^:
4
0
1
7
0
0
7
0
1
4
0
0
9
0
5
7
12
13 п,
12 —>¦
12
3
0
0
6
0
1
7
0
1
5
0
0
8
0
4
6
12
13
12
12
24 11 7 7 |
24 11 7
Для задачи Т2 тоже существует несколько простых
полезных преобразований. Применим к Г2 преобразование
3
0
0
6
24
0
1
7
0
И
1
5
0
0
7
8
0
4
6
7
12
13
12
12
0
0
0
6
0
4
10
0
1
9
3
0
5
0
4
6
12
13
12
12
24 И 7 7 |
Используя позиции нулей матрицы стоимости задачи Г3>
проводим назначение ненулевых перевозок в искомой
матрице X в следующем порядке: #24, х31, х±3, хА2, х12,
xin X2i- В результате получим оптимальный план
6 6 .
12
Теперь вычисляем минимальное значение целевой
функции:
f°D = <Х<\ С} =
= 6-7 + 6-1 + 6-5 + 7-3 + 12-4 + 5-2 + 7-2 = 171.
§ 6. Построение всех оптимальных планов
Рассмотренные в примерах 11, 12 транспортные задачи
имеют только один оптимальный план. Между тем часто
встречаются ТЗ, имеющие несколько оптимальных
планов. При этом иногда бывает целесообразно выписать все
56

оптимальные планы данной ТЗ и из множества D0 этих
оптимальных планов выбрать, например, такой, который
использует для перевозок минимальную суммарную
длину дорог.
Пример 13. Найти все оптимальные планы для
следующей ТЗ:
гп
1 0
5
2
2
7
3
3
1
9
4
6
4
8
7
6
3
6
3
8
3
9
10
15
20
10
12 ,20 10 3 10 I
Методом предыдущего параграфа находим
минимизирующее данную ТЗ преобразование Р:
zl: z\\ ~l\ "j,
Выпишем выражения для промежуточных
преобразований, опуская перед фигурными скобками символ Р:
г_3, -2, -1, -6 1 A,0,0, 0, 1
э~~\ 0, 0, 1, 0, 0J' У1 \0, 0, 1, 0, 1J'
Г 0,
—t-i,
0,
0, -1, 0, 0
o.o.o,
0, -1, -1, 0
1,-1,
1, 0 1
о, о, о;-
Здесь опущены промежуточные ТЗ, для которых легко
находятся выписанные выше простые полезные
преобразования Plt Р2, Р3.
Используем найденное преобразование Р'-
р
5
2
2
7
3
3
1
9
4
6
4
8
7
6
3
6
3
8
3
9
10
15
20
10
12 20 10 3 10 |
5
0
2
3
2
0
0
4
0
0
0
0
5
2
1
0
0
3
0
2
10
15
20
10
12 20 10 3 10 |
Для транспортной задачи f легко построить десять
различных оптимальных планов. Приведем два из них:
. - - - 10 _. - • .3-7-,
12 - 3 •
. 20 . .
. . 7 3
12 3
• 17
7 3
B4)
Стоимость перевозок по оптимальному плану
fb = <УХ, СУ = <72, СУ = 166.
57

1
2
3
2
0
0
20
0
0
0
3
0
3
0
10
10
3
20
— * вси
Для любого оптимального плана V = {и^} задачи Т
первые три (подчеркнутые) компоненты плана перевозок
определяются однозначно:
и21 - 12, г;44 - 3, vi3 = 7, B5)
поскольку соответствуют изолированным позициям нулей
матрицы стоимссти задачи Г- (Перевозка ^43 становится
изолированной после выполнения перевозки f44 = 3.)
Остальные ненулевые компоненты оптимального плана
могут варьироваться. Чтобы облегчить составление
различных вариантов оптимальных планов, следует
построить вспомогательную транспортную задачу Т1СП,
которую получим после выполнения в задаче Т
обязательных перевозок B5):
2 3 5
B6)
Сверху и слева от матрицы стоимости этой ТЗ указаны
номера соответствующих столбцов и строк задачи Т*
Дополнив любой оптимальный план задачи B6) обязательными
перевозками B5), получим оптимальный план задачи Г,
который будет также оптимальным и для задачи То.
Приведем четыре варианта (всего их десять)
оптимальных планов задачи B6):
Г 0 0 101 Г0 3 7] Г 0 0 10] Г 0 0 101
03 0 300 12 0 30 0
L20 0 Oj ' Ll7 0 3J > L19 1 0j » L17 3 oj •
Дополнив первые два из них обязательными перевозками
B5), получим выписанные в B4) оптимальные планы V± и
V2 исходной задачи Го.
§ 7. Вычисление //>*
Чтобы вычислить наибольшее на D значение f% целевой
функции заданной транспортной задачи То = Т {С, а, 6},
поступают следующим образом.
1. По заданной ТЗ То строят вспомогательную
транспортную задачу Т' = Т {С, а, Ь}, где элементы матрицы
58

С получают вычитанием соответствующих элементов
матрицы С из максимального элемента этой матрицы.
2. Для задачи Т' строится оптимальный план F0 ЕЕ
ЕЕ D {а, Ь}, на котором достигается минимальное
значение целевой функции задачи Т', т. е.
, с"».
Найденный таким образом план V0 и является искомым
планом X*, т. е. для плана V0 справедливо соотношение
<F°, C> = max {<*, С» = /?.
Пример 14. Для ТЗ из примера 7 построить план
X* и вычислить /J).
Проводим указанное выше преобразование То-+- Т'.
7
2
= 6
8
4
3
5
5
1
3
9
2
11
11
8
14 6
5 4 0
6 8 7
11
11
8 =Г.
5 9 9
5 9 9 7
Далее методом из § 5 найдем оптимальный план Vo
Для задачи Т':
2
7
3
5
1
5
6
9
4
4
8
9
6
0
7
7
11
11
8
1
7
0
5
0
5
3
9
0
1
2
9
5
С
4
7
11
11
8
3
9
0
5
0
5
1
9
0
1
0
9
5
0
2
7
11
11
8
ш
3
8
0
5
0
4
1
9
0
0
0
9
6
0
3
7
11
11
8
= т,
Л (Пх) = 6, А (П,) = 4,
Г- 9 2 ."I
X*=V° = \ • • 4 7
L5 • 3 -J
Id = <Х*, С> = 9-8 + 2.5+ 4-5+ 7-9 + 5-6+
+ 3-1 = 198.
Упражнение 5. Доказать, что для любой ТЗ описанный
в давном параграфе алгоритм приводит к вычислению /р-

Глава III
ГРАНИЧНЫЕ КОНСТАНТЫ
И ВЫЧИСЛЕНИЕ ИХ ОЦЕНОК
§ 1. Граничные константы. Основные понятия
и обозначения
Пусть на отрезке D = [а, Ъ] определена функция /,
к раз дифференцируемая на D. Через /</;> будем
обозначать к-ю производную функции /, причем /<0) (х) =
= / (х), /W (*) = /' (х) и т. д.
Число X назовем граничной константой функции /
на отрезке D, если:
1) найдется такая точка c€ED, для которой
выполняется одно из двух равенств
/№>(С)=Х, _/№>(с) = А,; A)
2) выполняется хотя бы одно из следующих неравенств
/<*> (х) < X, /<*> (х) > X,
-/W(x)<^, -/(*)(я:)>Х, (г)
которое остается верным для любого х ЕЕ D.
Число к €= {0, 1, 2, . . .} в этом определении
называется порядком граничной константы.
Граничные константы являются числовыми
характеристиками функции / на отрезке D. Из определения видно,
что для заданных / и D существует большое число
различных граничных констант. В частности, граничными
константами функции / на отрезке D являются наименьшие
и наибольшие значения на D самой функции / и ее
производных, т. е., например, числа:
f°D, ft q>S>, Ф*, фЬ, Ч&. C)
Здесь ф и г|) обозначают функции, являющиеся
производными для функции /, точнее
Ф = /', ф = Ф' = /". D)
60

Упражнение 1. Сформулируйте правило, по которому
вычисляются граничные константы /р, /^, если на D функция /
является:
1) линейной функцией;
2) квадратной параболой;
3) монотонной функцией;
4) выпуклой (вогнутой) функцией;
5) многочленом третьей степени.
Упражнение 2. Доказать, что граничными константами
для функции / являются, например, такие величины:
Ьг = max {| f (х) |}, E)
D
L2 = | inin {/" (x)} |. F)
Введем но вое обозначение. Символ {. . .}* будет
обозначать максимальный член последовательности, заключенной
в фигурные скобки. Символ {. . .}° означает минимальный
член последовательности. Примеры:
{2, 4, -3, 1}* = 4, {2, 4,< -3, 1}° = -3.
Если в фигурных скобках стоит функция, то верхний
индекс «*» (либо «О») означает наибольшее (наименьшее)
значение функции на множестве, которое указывается в
качестве нижнего индекса у фигурной скобки. Примеры:
{1+2^0,31=7.
Здесь использованы обозначения C), D).
Пример 1. Вычислить /г>, /?, tyb (Ф = /") для
следующих исходных данных:
/ (х) = 2 cos (х + 2), D = [3, 4].
Вводим новую переменную v = х + 2. При этом
когда х ЕЕ [3, 4], то v е= [5, 6]. Поскольку отрезок [5, 6]
есть часть отрезка [я, 2я], а на отрезке [я, 2я] функция
cosi; монотонно возрастает, то
fD = 2 cos 5 = 0,5673; ft = 2 cos 6 = 1,9203,
Вычислим теперь граничную константу для второй
производной:
l? = {/"}d = {-2 cos (x + 2)}°D =
= -2 {cos (x + 2)}d =
= —2 cos 6 » —1,9203.
61

Пример 2. Вычислить граничную константу
{фЛ?) (см- пример 9) для исходных данных
ф4 (х) = 2 cos Bх - 1), D = [3, 4].
Решение:
{фИ*)}г> = {-8cosB*-l)}°D =
= _8 {cos Bх — 1)}Ь -= —8 cos Bл) - —8.
В решении этих примеров использовано следующее
утверждение.
Лемма 1. Для любого числа X ^> 0, любых функций
Ф (х)ч г|) (х), определенных на D, и любого отрезка D
справедливы такие равенства:
Упражнение 3. Докажите, что граничную константу
E) можно записать в виде
Теорема 1. ?"с^гг функция / дифференцируема на
отрезке D = [<2, Ь], /гго выполняется соотношение
\I(y)-f(x)\KL1\y-x\, х, ytED. G)
Запись х, у Ez D означает, что неравенство G) выпол*
няется для любой пары точек х, у ЕЕ D.
Лемма 2. Для дифференцируемой на D функции /
соотношение
I / (У) - / И I < 2i I г/ - х |, х, yzaD, (8)
справедливо для любого числа %г > L1#
В научно-технической литературе соотношение (8)
называется условием Липшица. Условию Липшица могут
удовлетворять и недифференцируемые на отрезке D
функции. Коэффициент Хг называется константой
Липшица. Минимальное среди всех чисел Xi, для которых
выполняется условие (8), будем называть граничной
константой Липшица для заданных / и D.
Теорема 2. Для дифференцируемой на D функции /
граничной константой Липшица является граничная
константа Lt.
При решении практических задач граничные
константы, как правило, неизвестны и вычислить их точные
значения не представляется возможным. Поэтому вмегто
62

граничных констант часто будут использоваться оценки
граничных констант, для обозначения которых вместо
верхних индексов <«*» и «О» будут использоваться
символы «+» и «—» соответственно. Для подобных констант
справедливы, например, такие неравенства:
{ф"}Ь < W% < ф" (х) < WYb < WVn,
/Ь< /d < / (х) < fb < /Ь, х е D.
Для заданных / и D граничные константы являются
вполне определенными числами, например, f% — это
наибольшее значение функции / на множестве D. В то же
время оценки граничных констант — числа
неопределенные. В частности, /Ь — это любое число,
удовлетворяющее неравенству /Ь ^ /г>- Например, для / и D из
примера 1 справедливы следующие равенства:
{2 cos {х + 2)}5 = 2 cos 6, D = [3, 4];
{2 cos {x + 2)}j5 = 2, (9)
{2 cos (x + 2)}Ь = 5. A0)
Естественно, что для практических применений оценка (9)
предпочтительнее оценки A0). Однако оба равенства (9),
A0) справедливы; более того, равенства (9), A0)
справедливы для любого отрезка D.
В связи со сказанным выше оценки граничных
констант типа {. . .}Ь, {. • .}Б будем называть также
неопределенными оценками.
Пример 3. Для исходных данных
/ (х) = 2 - х2 - cos (х — 1/3), D = [0, 2],
записать граничную константу /р в виде десятичного
числа, по-видимому, невозможно. В то же время
неопределенная оценка /Ь выписывается элементарно:
/Б = {2 - x*)°D + {- cos (x - 1/3)}Ь - -2 + (-1) - -3.
Для обозначения различных граничных констант будет
использоваться буква L, которая, например, может
представлять любую граничную константу в перечне C) (см.
также формулы E), F)). Буква X будет использоваться
для обозначения неопределенных оценок граничных
констант.
63

§ 2. Простейшие способы вычисления оценок
граничных констант
Согласно определению граничными константами на
отрезке D являются наибольшие или наименьшие значения
самой функции / и ее производных, а также некоторые
величины, выражающиеся через такие значения —
например, граничные константы E), F). Поскольку
производные от функции, заданной аналитической формулой,
также задаются подобной же формулой, то для
оценивания граничных констант достаточно научиться оценивать
сверху наибольшее и снизу наименьшее значения
различных функций, заданных аналитической формулой.
Весьма грубые оценки сверху для /# обычно указать
нетрудно. Пусть
f(x)= SM*).
Тогда неопределенную оценку /# можно вычислить по
формуле
Если / — алгебраический многочлен и оценивается
наибольшее его значение на положительном отрезке D,
т. е.
/ (х) = S akx\ D = [а, Ъ], а > О, (И)
ТО
Более точную оценку X для этой функции при условии
A1) получим по формулам
а
Ясно, что здесь f% ^ X ^ /г>.
п
Если f (х) — 2 я* sin ^? то Для любого отрезка Z)
можно положить
64

Упражнение 4. Для всех рассмотренных выше случаев
выписать аналогичные выражения для неопределенной оценки /^.
Все приведенные выше оценки /?> являются весьма
грубыми. Между тем время решения практических задач
с применением неопределенных оценок граничных
констант существенно зависит от того, насколько точными
являются применяемые неопределенные оценки.
Поэтому важной задачей является разработка таких
вычислительных схем, которые бы позволили значительно более
точно вычислять оценки граничных констант при
относительно небольших затратах труда или времени ЭВМ.
Ниже описываются примеры подобных вычислительных
алгоритмов.
§ 3. Рекуррентные вычислительные процедуры
При решении вычислительных задач для получения
конечного результата, как правило, используется
рекуррентная вычислительная процедура, смысл которой
заключается в следующем. Вычислительный процесс
разбивается на отдельные такты. При выполнении каждого
такта вычисления проводятся по одним и тем же
формулам, но исходными данными для вычислений в каждом
последующем такте являются результаты вычислений
предыдущего такта. Простейшим примером
рекуррентной вычислительной процедуры является рекуррентный
вычислительный процесс вычисления суммы S большого
числа слагаемых а^:
п
S = S ак-
к-=1
Вычисление суммы S можно проводить по формулам
So = 0, A2)
S* = Sk-i + ak, A3)
к = 1,2, . . ., л, A4)
S = Sn. A5)
На первом такте вычисления проводятся по формуле A3)
при к = 1, т. е. вычисляется величина
Si = So + аг;
на втором такте вычисления проводятся по формуле A3)
при к = 2, т. е. вычисляется величина
S2 =
65

и т. д. На последнем такте реализуется формула
Sn = ??i-i + ап.
Формулы A2) — A4) задают рекуррентную
вычислительную процедуру. Как правило, в любой
вычислительной процедуре можно выделить четыре основные части:
1) формирование исходных данных — формула A2);
2) циклическая часть — формула A3);
3) условие окончания цикла—формула A4);
4) заключительная часть процедуры — формула A5).
Заметим, что каждая из этих частей может содержать
не одну, а несколько формул. Заключительная часть
рекуррентной процедуры в некоторых случаях может
отсутствовать.
Пример 4. Используя рекуррентный
вычислительный процесс A2) — A5), вычислить сумму
Здесь л — 7, ак = /с2 + 1. Результаты вычислений
сведены в таблицу:
к
ак
1
2
2
5
3
10
4
17
5
26
6
37
7
50
S, 2 7 17 34 60 97 147
Л I
Окончательный результат
S = S, = 147.
В качестве второго примера применим рекуррентную
вычислительную процедуру для вычисления
значения алгебраического многочлена
р = р (х) = S акхк A6)
по схеме Горнера. Алгоритм вычисления значения Р (х)
при заданном х можно записать в виде формул
Sk = sSfc-i + an^\ A8)
к = 1, 2,. . ., п; A9)
Р (х) = Sn. B0)
П р п м е р 5. Вычислить Р C), где
р (д.) = Х5 _ 18д:4 + 104хз _. ilQx2 _ 105х + 194.
66

Здесь п = 5, So = a5 = 1, а4 = —18, а3 = 104, а2 =
= —176, ах = —105, а0 = 194, я = 3. Результаты
вычислений по формулам A7)—B0) сведены в таблицу:
All 23 4 5
а5_Л. | _ is 104 — 176 — 105 194
Sh. | - 1Г> 59 1 - 102 - 112
Ответ: Р (S) = S5 = -112.
Отметим, что при вычислениях вручную удобно
использовать специальную вычислительную схему, которая
заключается в последовательном выписывании правых
частей формулы A8), при этом направление вычислений
указывается стрелочками. Покажем применение такой
схемы при вычислении Р C) для примера 5:
1.3- 18-*—15-3 + 104->59-3—176-^1-3—105->¦
~> -102-3 + 194 = -112. B1)
§ 4. Модификация схемы Горнера
Пусть заданы алгебраический многочлен Р и отрезок D:
п
р = Р(х)=% акх*, D = [а, Ъ]. B2)
fr=o
Опишем способ вычисления оценок Х° и X*:
X°^P°D -min{P (*)},
2* >/>? = max {/>(*)},
лей
вычислительная схема которого лишь незначительно
отличается от рассмотренной в предыдущем параграфе схемы
Горнера вычисления значения многочлена. Оценку «2*
можно вычислить по формулам
So = an; B4)
fa, если ?,-!< 0,
*~U если 5,.-1>0, (ZD)
/с = 1, 2, ,..,«; B6)
?* = 5П. B7)
67

Здесь циклическая часть рекуррентной вычислительной
процедуры содержит две формулы и при выполнении
каждого такта вначале вычисляется Кк, а затем Sk.
Теорема 3. Если отрезок D = [а, Ъ\
неотрицательный, т. е. 0^а< Ь, то для величины .%*, вычисляемой
по формулам B4)—B7), справедливо неравенство B3).
Пример 6.
р (я) = хъ - 18а:4 + 104;г3-176а:2 - 105* + 194,
D = [4, 6]. B8)
Для этих данных проведем вычисления оценки X* по
формулам B4) — B7), применяя вычислительную схему,
подобную той, которая использована в B1):
1-6 — 18-*—12-4 + 104 -> 56-6-176 -^ 160-6—105 -^
-* 855-6 + 194 = 5324.
Ответ: X* = 5324.
Оценку Х° ^ P°d можно вычислить по формулам
So = an; B9)
{а, если Sk-i ^> 0
Ъ, если $*_!<<), C0)
А = 1, 2, .... n; C1)
55° = 5W. C2)
Теорема 4. ?"с^1г отрезок D = [а, Ь]
неотрицательный, т. е. 0 <^ а < Ь, то для величины 55°,
вычисляемой по формулам B9)—C2), справедливо неравенство B3).
Пример 7. Проводя вычисления по формулам
B9)—C2) для исходных данных B8), придем к такому
результату: Х° = —3892.
Можно предложить много различных методов
получения более точных оценок для алгебраических
многочленов по сравнению с оценками, получаемыми описанным
выше методом модификации схемы Горнера. Естественно,
что более точные методы оказываются более сложными.
Проиллюстрируем применение одного из таких методов
на численном примере вычисления оценки 5S* для
исходных данных B8). Суть метода становится ясной из
приведенных ниже вычислений.
Пример 8.
р* = {р (х)}* = {хь _ i&z* + Ю4я3 - 176.Z2 - 105* +
+ 194}Ь = {х3 {х2 — 18* + 104) - 176я2 - 105я +
68

+ 194}? < {х3 {х* — 18* + 104}!, - 176а;2 - 105* +
+ 194}Ь = {48 х3 - 176Z2 - Ю5х + 194}Ь = {х D8z2-
- 176а: - 105) + 194}Ь < {х {А8х2 — 176—105}Ь +
}Ь = {567ж + 194}Ь = 3596
Ответ: #* = 3596.
Здесь неравенство РЪ ^ S* доказано в процессе
выполнения вычислений, причем полученная здесь оценка 56*
существенно меньше оценки в примере 6.
§ 5. Вычисление оценок граничных констант
для функциональных многочленов
Функциональным многочленом назовем функцию / вида
/(Jф()
г=1
Нас будут интересовать только такие функциональные
многочлены, у которых каждая из функций q^ (x) имеет
непрерывные на D производные до порядка п
включительно и вычисление граничных констант или их оценок
для функций ф^ (х) является достаточно простой задачей.
Функция а (х) называется мажорантой для функции
я|) (х) на отрезке Z), если неравенство
ф (х)< а (х)
справедливо для любого х Е= D. Одновременно при этом
функция ф (х) является минорантой для функции а (х)
на отрезке D.
Используя разложения функций q^ (x) в ряд Тейлора
около точки х = с с остаточным членом в форме Ла_
гранжа и заменяя в этих разложениях значение
производной q4n)(?) ее оценками ,35?, ,35*:
выпишем следующие формулы:
Ti (х) = q>i (с) + ? -^fi- (x - с)\
fr=i
Pi (х) = Ti (х) + 55? (х - с)п/п\,
Pi(z) = Tl(x) + a%(x-c)n/nl,
с= (а + ЪI2, D = [a, b], i = 1, . . ., т.
69

Всюду в данном параграфе будем считать п четным числом.
Упражнение 5. Доказать, что функция Р\ является
мажорантой, а функция Р} является минорантой для функции ф$ на
отрезке Z), т. е. для этих функций справедливы неравенства
Pi (*) < Фг (х) < Р\ (*), ^?D = k Ъ].
Образуем вспомогательные функции Р~, Р+ по формулам
т т
Р-(.т) = %Р-(х), Р+ (х) = 2 /\f (*) •
1=1 2=1
Упражнение 6. Доказать, что функции Р~ и Р+
являются соответственно минорантой и мажорантой уже для функции /,
т. е. для этих функций выполняются неравенства
Р- (*) < / (*) < Р+ (х), х е D = [/I, 6].
Вычислив теперь каким-либо способом оценки
<?° < (Р- (*)}^f {P+ (*)}* < 5?», C3)
получим тем самым соответствующие оценки и для функции /:
Упражнение 7. Доказать последнее утверждение.
Для вычисления оценок C3) можно использовать методы
предыдущего параграфа.
Пример 9. Доказать, что функция
^ (я) = -*-в*/2 _-L^/3 + 2cos(a: + 2) + 2cosBz— 1)
C4)
принимает только положительные значения на отрезке
D = [3, 4].
Представим функцию я|) (#) в виде
4
г=1
где
ф1 (ж) = -|- ^/2, ф2 (Х) = ^ ^/»,
Фз (а:) = 2 cos (х + 2), ф4 (а:) = 2 cos B# — 1).
Выпишем квадратные миноранты функций срг-:
РТ (х) = ф[ (х0) + (х — Хо) ф[ (хо) + -у- {ф{}?)(я — Д:оJ;
д:0 = 3,5; 1 = 1, 2, 3, 4.
70

Вычислим коэффициенты первой миноранты Рг:
хо/2 == C,5)/2 = 1,75; е1'75 = 5,7546;
ф; C,5) = -J- ei. w = 1,4386;
>1> = 4" ^ C) = " е1л = °'2801-
Вычислив таким образом коэффициенты остальных
минорант (см. при этом примеры 1, 2), выпишем для всех
четырех минорант выражения с числовыми
коэффициентами и просуммируем их:
2,877 + 1,4386 (х — х0) + 0,2801 (х — х0J
— 1,071 — 0,3568 (х — х0) — 0,0703 (х — х0J
+ 1,417 + 1,4110 (х — хо) — 1,9204 {х — х0)*
0,567 + 1,1176 (х — хр) — 4,0000 (х — х0)*
Р- (х) = 3,790 + 3,6104 (я: — х0) — 5,7106 (яг — х0J
Получили вспомогательную функцию Р~ (х), которая уже
является минорантой для исходной функции я|) (х), точнее,
для этих функций выполняется неравенство
/>-(*)<!>(*), а?е[3, 4]. C5)
Упражнение 8. Докажите это неравенство. Обратите
внимание на правило округления, использованное при вычислении
коэффициентов минорант.
Поскольку минимальное на D [3, 4] значение функции
Р-(х)
{Р' (x)}°D ж 0,557
является положительным числом, то в силу неравенства
C5) функция ij) (x) принимает на отрезке [3, 4] только
положительные значения.
§ 6. Блочные методы вычисления оценок
Суть блочных методов заключается в том, что исходный
отрезок D разбивается на ряд более мелких отрезков Di,
D2, ..., Dm и искомая оценка 55* > f% вычисляется по
формуле
l
где оценки #? > /Д, %t > /В2, • . ., %т > /Sm
вычисляются одним из методов, изложенных в § 4, 5.
71

Пример 10. Вычислить оценку Х>* > РЪ для
исходных данных B8), разбив отрезок D = [4, 6] на два
отрезка
D± = [4, 5], D2 = [5, 6] C6)
и применив блочный метод. Для вычисления оценок X*
и ?2 использовать метод, которым решается пример 8.
Проводим указанные вычисления:
% 2 — 18s + 104}Sf — 176л:2 — 105* + 194}* х =
— 176а:2 — ?
— 176а; —
194}?2 =
< {х {39*2 — 176* — 105}?2 + 194}?2 =
= {243* + 194}^2= 1652 = 35*,
= {1269; 1652}* = 1652.
= {215* + 194}^ = 1269 = #*,
Ответ: X* = 1652.
Упражнение 9. Для последнего примера доказать
справедливость неравенства Р^ ^ X* = 1652.
§ 7. Еще один способ вычисления
неопределенных оценок для алгебраических
многочленов
В § 4 описаны два метода вычисления
неопределенных оценок Рв и РЪ\ модификация схемы Горнера
и метод, который иллюстрируется решением примера 8.
Общий подход этих и некоторых других методов
вычисления неопределенной оценки Рв для полинома Р (*)
фактически состоит в построении последовательности
полиномов Ph. (х) убывающих степеней, причем
Р (х) = Рп (х) < Рп_х (х) < Рп-2 (*)<...< Рг (х) <
<Р1(*)<Ро(*) = РЬ, xzeD. C7)
Здесь Рк (х) — многочлен степени к. Каждый последующий
многочлен меньшей степени является мажорантой для
предыдущего многочлена на отрезке D. Некоторые
промежуточные многочлены в последовательности C7) могут от-
72

сутствовать. Многочлен Булевой степени Ро (х) — это
число Р#, которое оценивает сверху значения исходного
многочлена Р (х) на всем отрезке D. Ниже, в дополнение к
§ 4, описывается еще один способ построения
последовательности C7), который обычно приводит к более точным
результатам.
Упражнение 10. Докажите следующее утверждение.
Л е м м а 3. Для любых чисел а и Ъ неравенство
{а + Ь)х — (^4^J < х2 <(а + Ь) х ~ аЪ C8)
справедливо для каждого х ?Е [а, Ь].
Лемму 3 можно переписать в виде соотношения
2сх — с2 < *2 < 2сх — с2 + *2, C9)
х <= [а, Ъ], с= (а + Ь)/2, t = (Ъ — а)/2.
Формулы C9) оказываются более удобными для некоторых
теоретических рассуждений, в частности, для распространения
результатов данного параграфа на многомерные задачи.
Пример 11. Используя лемму 3, вычислить
неопределенную оценку сверху Рр значений многочлена
Р (х) = х5 — 18я4 + 104г3 — 176л;2 — 105* + 194 D0)
на отрезке D = [а, Ь] = [4, 6].
Решение. Подставляя а = 4, Ъ = 6 в
соотношения C8), придем к неравенству
10s - 25 < х2 < 10s - 24. D1)
Данное неравенство и все последующие соотношения
рассматриваются для х Е= [4, 6].
Двойное неравенство D1) перепишем в виде двух
неравенств
10s — 25 < х\ D2)
х2 < 10s - 24. D3)
Заметим далее, что хк > 0 для любого х ЕЕ [4, 6] и
любого й = 1, 2, ... Поэтому, умножая неравенство D3) на х3,
придем к неравенству
хь < Юя4 - 24я3. D4)
Суммируем равенство D0) и неравенство D4):
р (Х) = х* — 18*4 + 104*3 _ 176*2 _ Ю5* + 194
+ *5 < 10** — 24*з
Р(*)< — 8*4 + 80*3 — 176*2 — 105* + 194 D5)
73

Умножая теперь неравенство D2) на (—8*2), придем к
неравенству
-8*4 < -80*3 + 200а;2. D6)
Суммируя неравенства D5), D6), получим
Р (*) < 24*2 - 105а: + 194. D7)
Продолжая технологию решения задачи излагаемым
здесь способом и вновь используя неравенство D3),
перепишем его в виде
24*2 < 240* - 576. D8)
Суммируя неравенства D7), D8), приходим к неравенству
Р (*) < 135* - 382, D9)
правая часть которого является линейной мажорантой
многочлена D0) на отрезке [4, 6]. Теперь приходим к
числовой оценке
Р (х) < 135* — 382 < {135* — 382}$>6] = 428. E0)
Таким образом, можно положить
РЪ = 428 > Р (*), * 6Е [4, 6]. E1)
Сравните неопределенную оценку E1) с
неопределенными оценками, полученными в примерах 6 и 8.
Приведем компактную форму записи решения примера
11. При этом неравенства D2), D3) удобнее записать
в виде
х2 < 10* — 24, (*)
—*2 < —10* + 25. (**)
Далее проводим вычисления без пояснений:
Р (*) = х5 — 18а;* + 104*3 _ 176*2 _ Ю5* + 194
+ *5 < 10** — 24*3 — (*) . *з
Р(х)^_8**+ 80*з _ 176*2 _ Ю5* + 194
+ — 8*4< — 80*3 + 200я2 _ (**) . 8*2
Р (*) < 24*2 - 105* + 194
+ 24*2^ 240* — 576 — (*) . 24
Р(*)<135* —382
Теперь оценка Рг> получается по формулам E0), E1).
74

Пример 12. Используя метод данного параграфа,
т. е. опираясь на неравенства D2), D3), вычислите оценку
РЪ для исходных данных примера 11.
Ответ: РЪ = —82.
Сравните полученную здесь оценку РЪ с результатом
решения примера 7.
Заметим, что метод данного параграфа можно
применять также и в блочной модификации § 6.
Упражнение 11. Докажите следующее утверждение.
Л е м м а 4. Если О <^ а < Ь, то для любого х Е= [#, Ъ\
справедливо неравенство
где
а (х) = ЪЪх2 + (а2 — 2аЪ — 2b2) x + 2ab2 — a2b,
Р (х) = Ъах2 + {Ь2 - 2аЪ - 2a2) x + 2a2b - ab\
Пример 13. Опираясь на лемму 4, вычислите Pd
и РЪ для исходных данных примера 11. Сравните
полученные результаты с аналогичными результатами ранее
решенных примеров.
Упражнение 12. Опираясь на лемму 4, постройте
алгоритм вычисления Pj, для полинома произвольной степени и
напишите программу его реализации для ЭВМ на конкретном
алгоритмическом языке, в которой использовалось бы минимальное число
арифметических операций в каждом такте циклической части алгоритма.

Глава IV
ВЫЧИСЛЕНИЕ НАИБОЛЬШЕГО ЗНАЧЕНИЯ
ФУНКЦИИ
§ 1. Основные понятия и обозначения.
Простейшие методы вычисления НЗФ
В данной главе изучаются методы вычисления с
заданной точностью е > 0 наибольшего значения f% функции
/ на отрезке D = [а, Ь]. Вместо точного значения f% эти
методы позволяют вычислить некоторое число /, которое
отличается от искомого точного значения /В не более
чем на е, т. е. для / выполняется неравенство
I / - /Ы < 8. A)
Данное неравенство можно записать также в виде
двойного неравенства
/ - г < f% < / + 8. B)
Практически приближение f к наибольшему значению
функции (НЗФ) вычисляется по одной из следующих
формул:
f = F + e, / = Ф-8, ;=-^(^+ф), C)
где F — нижняя, а Ф — верхняя оценки для /S, т. е.
F < fD < Ф. D)
Отметим принципиальное различие между методами
данной и предыдущей глав. НЗФ /д является граничной
константой для функции /, и в предыдущей главе
описывались методы вычисления верхней оценки /? для величины
/S. В качестве нижней оценки для /? можно взять
значение функции / в любой точке отрезка/). Таким образом,
/(*)</?</?. ieu E)
76

Принципиальная разница между оценками, стоящими в
левой и правой частях неравенств D), E), заключается в том,
что оценки в E) являются неопределенными (например,
зная значение /?>» ничего нельзя сказать о величине
разности /J — /Ь). В то же время методы вычисления
оценок F в. Ф в данной главе гарантируют выполнение
неравенств
Ф-/?<2е, fD -F<2e,
а точнее — гарантируется выполнение неравенства
Ф - F < 2е. F)
Вторым важным моментом является то, что для
вычисления оценок F и Ф методы данной главы используют
неопределенные оценки для первой или второй
производной функции /, причем указанные неопределенные оценки
вычисляют методами предыдущей главы.
Ниже описываются простейшие методы вычисления
приближения f. Пусть W — равномерная сетка узлов иь
расположенных на отрезке D = [а, Ь]:
W = {иг, и2, . . ., ип+1}, h = (b — a)ln, G)
щ = а + (к — 1) h, к = 1, 2, . . ., п -f 1.
Через fw обозначим максимальное значение функции /
в узлах сетки W:
Для любых /, D и W CZ D справедливо неравенство
fw < /?• (8)
Упражнение 1. Докажите это неравенство.
Теорема! Если функция f удовлетворяет на
отрезке D условию Липшица C.8) — формула (8) в гл. Ill, a
сетка W задается формулами G), то
fo<fw + Zih/2. (9)
Теорема2. Если функция f удовлетворяет условию
-?</"(*), ^ED, 55 > 0, A0)
а сетка W задается формулами G), то
ffa A1)
Для функции /, удовлетворяющей условию Липшица
C.8)f согласно свойству (8) ц теореме A), можно в качест-
77

ве нижней оценки для /d положить F = /Jy, а в качестве
верхней оценки положить Ф = fw + %ih/2. При этом,
согласно последней формуле в C),
f = fw + SSifc/4, A2)
причем погрешность такого приближения оценивается
неравенством
I f ~ ft К (Ф - F)I2 = XJi/4.
Теперь для выполнения неравенства A) достаточно подоб"
рать шаг h сетки W так, чтобы выполнялось неравенство
Xxh/i < е, т. е.
Л<4е/55!. A3)
Точно так же, опирась на свойство (8) и теорему 2,
установим, что для дважды дифференцируемой функции /,
удовлетворяющей условию A0), приближение / можно
вычислить по формуле
/ = /Яг + да/16. A4)
При этом неравенство A) будет выполнено, если шаг h
сетки W удовлетворяет неравенству
fc< 4/8/5. A5)
Пример 1. Опираясь на теорему 2 и вычисляя
значения многочлена Р (х) только на концах отрезка D,
получить оценку Рр для исходных данных
Р (х) = хъ — 1&г4 + 104а;3 — 176.Z2 — 105х +
+ 194, D = [4, 6]. A6)
Решение. Здесь/ (х) = Р (х). Чтобы
воспользоваться формулой A1), следует вычислить оценку X =
= | {Р"}Ъ |. Имеем
Р" (х) = 20а:3 - 216я2 + 624а: - 352 >
> х {20х2 - 216а: + 624}?> - 352 = 40,8-х - 352 >
> {40,8-а: - 352}?) - -188,8.
Таким образом, —188,8 <Г Р" {х), х е D, и можно
положить (см. формулу A0))
X = 188,8. A7)
78

Поскольку узлами сетки W являются только концы
отрезка D, то
Ptv = {Р (а), Р F)}* = {Р D), Р F)}* =
= {30, 140}* = 140.
Воспользуемся теперь формулой A1), заменив в ней /
на Р:
P%<Pw + XhV8 = 140 + 188,8-2*/8 - 234,4.
Таким образом, можно положить Р& = 235.
Сравните эту оценку с результатом решения примеров 6, 8, 11
в предыдущей главе.
Пример 2. Для исходных данных A6) вычислить
Р% с точностью е — 1.
Решение. Подставим заданное е = 1 и оценку A7)
в неравенство A5):
h < 4/е/Ж = 4/1/188,8 « 0,291.
Можно положить h = 0,25. Для вычисления Р%?
используем сетку W с шагом h = 0,25:
W = {4; 4,25; 4,5; . . .; 5,75; 6}.
Вычисляя в узлах этой сетки значения многочлена Р (х)
найдем, что
Р%г = {Р D); Р D,25); . . .; Р F)}* = Р E,5) « 157.
Теперь по первой формуле в C) получим
р = р%г + е = 157 + 1 = 158.
При этом гарантируется выполнение неравенства
\p-pi |<1,
или 157 < P*D < 159.
Упражнение 2. Вычислите с точностью f = 0,1 гранич
ные константы г|)^ и г|)^ для исходных данных примера 9 из
предыдущей главы.
При вычислении неопределенных оценок (Хг или X)
может оказаться, что значение неопределенной оценки
равно нулю. При этом нельзя воспользоваться формулами
A3), A5). Однако в этом случае, например при X = 0,
неравенство A1) примет вид
79

Из совместного рассмотрения этого неравенства и
неравенства (8) следует, что f% = fw при любом h, в частности
при h = b — а. Последнее означает, что /# = {/ (а),
/ F)}*. Результаты подобных рассуждений относительно
и других неопределенных оценок граничных констант
сведены в следующей лемме.
Таблица 1
{/
{/'
{/"
{/"
Если
)~D>0
fD<°
\+D<°
A =
/S> =
TO
/(a),
1ifi),
{/(«), J
{/(«), /
f»
fD
(b)
(b)
= №
= /(*)
}°
}*
Лемма 1. Если выполняется неравенство в левом
столбце табл. 1, то справедливы равенства {или равенство) в
соответствующей строке правого столбца табл. 1.
С вычислительной точки зрения пользоваться
утверждениями данной леммы не очень удобно при решении
задач на ЭВМ, поскольку «нуль» и «машинный нуль» — это
не одно и то же. Поэтому для практического применения
целесообразно трансформировать соотношения табл. 1 с
учетом требуемой точности вычислений 8.
Л е м м а 2. Если для дважды дифференцируемой на
отрезке D — [а, Ь] функции f имеет место неравенство
{1°}Ъ > -16е/F - аJ, 8 > О, {Щ
то
/? < {/ (a), f (&)}* + 2е.
Поэтому если на отрезке D выполнено условие A8),
то можно положить
f = е + {/ (а), / F)}*.
При этом / удовлетворяет неравенству A).
Лемму 2 следует использовать вместо соотношений
последней строки табл. 1.
Упражнение 3. Сформулируйте и проведите обоснование
утверждений, аналогичных лемме 2, для первых трех строк табл. 1,
80

§ 2. Элементарные оценки для НЗФ
Лемма 3. Если функция f удовлетворяет на отрезке
D — [а, Ъ] условию Липшица C.8), то
ft < (fa +fb + ЗД/2 = Ф\ A9)
h = b-a, fa = f (a), fb = / F).
Доказательство. Положим
B0)
Упражнение 4. Доказать, что а ^ с ^ Ь.
Неравенство A9) доказывается отдельно для двух
возможных случаев:
1) я* G: [а, с] (при этом х* — а ^ с — а); B1)
2) х* е 1с, Ь] (при этом Ъ — х* < Ъ — с). B2)
Напомним, что я* — точка максимума функции /,
поэтому
/ (**) = /?• B3)
Пусть выполнено условие B1). Выпишем условие
Липшица C.8) для точек х*, а е D:
Отсюда, с учетом соотношений B3), B1), будем иметь
ft < fa + Zi (x* - а) < U + Xl (с - а). B4)
Точно так же для случая B3), выписывая условие
Липшица для точек Ь, #*, имеем
fD < h + %i (b - ж*Х/ь + Zi (b - с). B5)
Если в неравенства B4), B5) подставить выражение для с
из формулы B0), то каждое из неравенств B4), B5)
приводит к неравенству A9). Лемма 3 доказана.
Л е м м а 4. Если дважды дифференцируемая на
отрезке D = [а? Ь] функция f удовлетворяет условию A0), то
1Ь < {fa, /ь}* + Z (b - aJ/8. B6)
Доказательство. Если НЗФ достигается на
одном из концов отрезка D, то /В= {/а, /ь}* и
неравенство B6) справедливо. Пусть далее х*— внутренняя точка
отрезка D. При этом
/' (**) = 0. B7)
81

Используя соотношения A0), B3), B7) и формулу Лагран-
жа для дважды дифференцируемой функции, проведем
последовательность преобразований
/ (х) = / (х*) + f {х*) (х - х*) + Г (I) (х - х*у-/2 =
= /»+/• (I) (* - **)'/2 >fl-X(x- х*)*/2;
Отсюда приходим к неравенству
/В < / (х) + X (х - х*)Ч2, XEED. B8)
Далее следует отдельно рассмотреть два возможных
случая:
х* — а < (Ь — о)/2, B9)
Ъ — х* < (Ь — а) 12. C0)
Пусть выполнено условие B9). Подставляя в B8) х = а и
используя также A9), B9), проведем следующие
преобразования:
1Ъ < / (а) + X (а - х*)Ч2 = /а + S (а - Х*)У2 <
< {fa, U}* + 3 (а - **O2 < {/„, /ь}* + 5? F - аJ/8.
Таким образом, пришли к неравенству B6). Лемму 4
можно считать доказанной, поскольку случай выполнения
неравенства C0) рассматривается аналогично.
§ 3. Сеточные оценки
Через W обозначим произвольную сетку узлов иь на
отрезке D = [а, &]:
W = {щ, ы2, . . ., ип+1}, 3
а = ^ < w2 < . . . < мп < untl = Ь.
Расстояние hj между соседними узлами назовем шагом
сетки:
hj = uj+1 — uj, j = 1, 2, . . ., п.
Различают сетки с переменным (hj) и с постоянным (hj =
= h) щагом. Сетки с постоянным шагом будем называть
равномерными. Равномерные сетки уже использовались
в § 1.
Узлы сетки W разбивают отрезок D на отрезки Dj
меньшей длины:
Dt = [щ, и2], D2 = [и2, и3], . . ., Dn = [un, un,J.
82

Применяя лемму 3 к каждому отрезку Dj, придем к
следующему утверждению.
Л е м м а 5. Если функция f удовлетворяет на отрезке
D условию Липшица C.8), то при любой сетке W d D
справедливо соотношение
1Ъ. < (fj + 1т + Xth,)/2 = Ф;, C2)
fj — f (и])-> fj+i = / (uj+i)i 7 = 1, • « «, п.
Теперь уже легко доказать следующую теорему.
Теорема 3. Если функция f удовлетворяет на D
условию Липшица C.8), то при любой сетке W вида C1)
справедливо неравенство
C3)
Точно так же, опираясь на лемму 4, можно доказать
теорему 4.
Теорема 4. Если дважды дифференцируемая на D
функция / удовлетворяет условию A0), то при любой сетке
W вида C1) справедливо неравенство
fD < {ф; ф; ..., ф;>*=ф^, C4)
где
Ф'; = {/я/;+1>* + ^78>/^, /=1,2,..., п. C5)
Величину F = f%? назовем нижней сеточной оценкой
для /Ь. Величины Ф^, Ф^ назовем верхними сеточными
оценками величины f% для функций, удовлетворяющих
соответственно условию Липшица либо условию A0).
Полагая в формулах C1)—C5) hj = h, j = 1, 2, . . .
. . ., тг, придем к верхним сеточным оценкам НЗФ на
равномерной сетке
= Xxh/2 + \ {/i -f /„ U + /з, ...,/„ + /n+i>*, C6)
<tiw = fiv + %h*l&. C7)
Упражнение 5. Вывести эти формулы.
Формула C7) доказывает теорему 2.
Функция max (так же как и функция min) обладает
двумя очевидными свойствами. Напомним, что мы
пользуемся обозначением max {...} = {...}*.
Свойство1. Постоянное слагаемое можно выносить
за знак функции max. Например пусть
а* = Ич + К * = 1, 2, . • ., п.
83

Тогда справедливы формулы
{а1? а2, . . ., ап}* = {\хг + /с, \i2 + к, . . ., \in + /с}* =
= к + {(х1? ixa jxn}*. C8)
Свойство2. Постоянный положительный
множитель можно выносить за знак функции max. Например,
пусть
at = o\it, о > Q, г = 1, 2, . . ., /г.
Тогда справедливы формулы
{<*!, а2, . . ., ап}* = {а^, а^2, . . ., ащ}* =
= а {|11э fx2, . . ., jxj*. C9)
Упражнение 6. Проверьте эти свойства функции max
на конкретных числовых примерах. Приведите пример, когда
формула C9) неверна при а < 0.
Упражнение 7. Доказать неравенство
{/i + /2» /2 + /3> • • •. /я + W*/2< {/1. /2. /3.• • •. W * = /^- D°)
Из соотношений C6) и D0) следует более грубая по
сравнению с C6), но и более простая сеточная оценка Ф^
сверху величины f% на равномерной сетке для функции,
удовлетворяющей условию Липшица:
D1)
При этом выполняются неравенства
. D2)
Соотношения D1), D2) доказывают теорему 1.
Сеточные оценки*^ и Ф могут использоваться для
приближенного вычисления /В по формуле
f = (F + Ф)/2 D3)
с оценкой погрешности
I f - /Ы < (Ф - F)/2. D4)
Вычисление / по формуле D3) будем называть прибли-
жени ым вычислением НЗФ с апостериорной оценкой
погрешности D4). Смысл такого названия (с апостериорной
оценкой) заключается в том, что вычисление оценки
погрешности приближения / по формуле D4) проводится уже после
выполнения основных вычислений — определения
значений нижней и верхней сеточных оценок. В следующих
параграфах вычисление НЗФ проводится с априорной (задан-
84

ной заранее до вычислений) оценкой погрешности 8 и
апостериорная верхняя сеточная оценка (типа Ф\у либо Фуг)
в явном виде не вычисляется.
В заключение отметим, что более точное по сравнению
с формулой C7) вычисление верхней сеточной оценки для
дважды дифференцируемой функции дано в работе [27].
§ 4. Вычисление НЗФ с заданной точностью
алгоритмами, использующими равномерные сетки
В данном параграфе вычисление приближения к /р
проводится по формуле
f = fw + 8 D5)
и шаг h сетки W выбирается таким, чтобы гарантировалось
выполнение неравенства
lf-/?l<e._ D6)
Простейшим способом вычисления / является алгоритм
перебора значений функции / во всех узлах равномерной
сетки W с шагом h, для которого выполняется
неравенство A3) для функций, удовлетворяющих условию Липшица,
либо неравенство A5) для дважды дифференцируемых
функций, удовлетворяющих условию A0). Подобным
способом решалась задача в примере 2.
Для вычисления f вместо равномерной сетки можно
использовать квазиравномерную сетку
W = {ии и2, . . ., ип+1},
щ = а + (к — 1) h, к = 1, 2, . . ., п\ D7)
ип < 6, ип + h > fe, un+1 = Ъ.
Пример 3. Вычислить Р% с точностью 8=1 для
следующих исходных данных:
Р (х) = хъ — 18я4 + 104*3 — 176я2 — 105.Z +
+ 194, D = [4; 6]. D8)
Решение. Используем формулы D5), D7), в
которых положим а = 4, Ъ = 6, h = 0,29, поскольку h
должно удовлетворять неравенству h <; 0,291 (см. пример 2).
Используя сетку D7) с шагом h = 0,29
W = {4,00; 4,29; 4,58; . . .; 5,74; 6,00},
вычислим
Pw = Р E,45) ж 157.
Теперь, согласно формуле D5), имеем Р = 158,
85

Отметим, что использованная здесь сетка W содержит
восемь узлов, в то время как в примере 2 значения
функции / вычислялись в девяти точках.
Для вычисления величины fw совсем не обязательно
вычислять значения функции / во всех узлах сетки W.
Существует группа алгоритмов просеивания, которые в
процессе вычислений проводят отбраковку части узлов
сетки W, не вычисляя значений функции в отбракованных
узлах. Применение алгоритма просеивания
иллюстрируется процедурой решения следующего примера.
П р и м е р 4. Вычислить Р% с точностью 8 = 0,2 для
исходных данных D8).
Решение. Используя неравенство A5) и
неопределенную оценку A7), оцениваем допустимое значение шага
сетки:
h < 4 УШ = 4 /0,2/188,8 « 0,1302.
Для решения задачи по формуле D5) здесь можно
использовать квазиравномерную сетку D7) с шагом h = 0,13
либо равномерную сетку с шагом h = 0,125. К любой из
этих сеток для вычисления Pw можно применить
некоторую модификацию алгоритмов просеивания. Однако для
большей наглядности ниже используется равномерная
сетка D9) с шагом h = 0,1
W = {4,0; 4,1; 4,2; . . . ; 5,9; 6,0}. D9)
Вычисляя значение многочлена Р (х) в каждом узле этой
сетки, найдем, что
Pw = Р E,4) = 157,25 E0)
и с точностью e = 0,2 приближением к Р% будет величина
р = p*v + е = 157,25 + 0,2 = 157,45.
Проведем теперь вычисление величины E0), применяя
на сетке D9) алгоритм просеивания.
Вычисление Pw проведем в три этапа. На первом этапе
вычисляем значения функции Р в каждом четвертом узле
сетки W. Результаты этих вычислений представлены
таблицей на с. 87.
Числа v\ в первом столбце этой таблицы образуют
вспомогательную редкую сетку Wx = {4,0; 4,4; . . . ; 6,0} с
шагом hx = 0,4.

Обозначим через Da отрезки, на которые разбивается
отрезок D = [а, Ь] = [4; 6] узлами и[ первого этапа; через
I этап
4,0
4,4
4,8
5,2
5,6
6,0
30,00
86,37
129,42
153,32
155,93
140,77
90,146
133,196
157,096
159,706
159,706
Хп — неопределенные оценки сверху значений функции Р
на отрезке Di,:
Р (X) < Х[; X (= [Uку Uk+1] = А ,
* = 1,2, . . ., 5.
Применяя лемму 4 к каждому отрезку /)*,., запишем
неравенство
Р*' < {Р (»*)* Р (v'k+i))* + ЖЛ?/8 = Ж),. E1)
Используя оценку A7), вычислим постоянную
составляющую неопределенных оценок %-:
Xhl/8 - 188,8-@,4J/8 = 3,776.
Теперь вычисляем неопределенные оценки Х: по формуле
E1), например
= {Р №); Р
+ Xh2J8 = {30; 86,37}* +
3,776 = 90,146,
и вписываем значения L[ в третий столбец таблицы 1-го
этапа.
Максимальное значение функции Р на сетке Wx
первого этапа равно
P*rt = р E,6) = 155,93.
Поскольку Х[ < Х2 < Xw^ то в силу неравенства E1)
при к = 1 и при к = 2 делаем заключение, что
(я) < Pjr, при а: е [4,0; 4,8],
87

т. е. во всех узлах сетки W, принадлежащих отрезку [4,0;
4,8], значения функции Р будут меньше P*vr Так как
Pwt ^ Pw, то на величину Pw отрезок [4,0; 4,8] не
оказывает влияния и из дальнейшего рассмотрения этот
отрезок исключается.
Переходим к вычислениям второго этапа, в котором к
вычислениям подключаются новые узлы сетки W,
расположенные между узлами v%, v$, v'5, vfQ.
В таблице второго этапа во втором столбце вписаны
пишь вновь вычисляемые значения функции. Шаг сетки
4,8
5,0
5,4
5,6
5,8
6,0
144
157
149
II этап
;>
,00
,25
,88
144,944
154,264
158,194
158,194
156,874
150,824
W2 второго этапа h2 = 0,2. Для неопределенных оценок
Li сверху значений функции Р на отрезках [vl, vj:+1\
выписываем формулу, аналогичную формуле E1):
& = {Р W, Р (Й+i)}* + ЖЛ|/8. E2)
Вычисляем постоянное слагаемое в этой формуле
Zht/8 = 188,8- @,2J/8 = 0,944.
Результаты вычислений по формуле E2) заносим в третий
столбец таблицы II этапа. Вычислим, например, %[:
Х[ = {Р D,8); Р E,0)}* + Xh2z/8 =
= {129,42; 144,00}* + 0,944 = 144,944.
Максимальное значение функции Р на сетке W2
второго этапа равно
Р%2 = Р E,4) = 157,25.
Поскольку
88

то отрезки Du D2, D5, DQ из дальнейшего рассмотрения
исключаются.
Переходим к третьему этапу вычислений, подключая
новые узлы сетки W, расположенные между узлами vl,
Ill
lit
vi
5,2
5,3
5,4
5,5
5,6
этап
III
/<r«
155,
157,
95
22
Поскольку между узлами сетки W2 третьего этапа уже
нет узлов сетки W, т. е. все узлы сетки W исчерпаны, то
Pw = Pws=P E,4) = 157,25,
где
W3 = К, . . ., vl) = {5,2; 5,3; 5,4; 5,5; 5,6}.
В заключение отметим, что три этапа алгоритма
просеивания вычисляют значения функции Р лишь в 11 из 21
узла сетки D9).
§ 5. Монотонные алгоритмы вычисления НЗФ
Организуем вычисление / по формулам
i, Fo = f F), хг = а;
h =
i =h
(Ft -
hh i = 1, 2,
n;
f =
xn+1;
E3)
E4)
E5)
E6)
Здесь формулы E3) задают исходные данные для
выполнения первого такта рекуррентной вычислительной
процедуры, которая определена формулами E4). Алгоритм назван
монотонным потому, что точки хи в которых
вычисляются значения функции /, образуют монотонно
возрастающую последовательность чисел. При этом выполнение
тактов вычислительной процедуры продолжается до тех пор,
89

пока очередная точка хг не выйдет за пределы интервала
(а, 6), что указывается неравенством E5). По формуле E6)
проводится заключительный акт вычислений.
Т е о р е м а 5. Если функция / удовлетворяет на
отрезке D = [а, Ь] условию Липшица C.8), а величина f
вычисляется по формулам E3)—E6), то справедливо неравенство
D6).
Доказательство этой теоремы проводится по той же
схеме, по которой ниже доказывается теорема 6.
Организуем вычисление f по формулам
К = 2)ГЫХ, Fo = / (Ь), хг = а; E7)
/, = f (xt), Ft = {Ft-lt ft}*,
щ = f2 Be + Ft - ft)/Z, hi = [it + k, E8)
Xt+i = xi + hi-> i = 1, 2, . . ., /г;
xn < b < xn+1; E9)
f=Fn + s. F0)
Здесь E7) — исходные данные рекуррентной
вычислительной процедуры E8), а неравенства E9) — условие
окончания работы циклической части алгоритма.
Теорема 6. Если дважды дифференцируемая на D
функция f удовлетворяет условию A0), а величина f
вычисляется по формулам E7)—F0), то для f справедливо
неравенство D6).
Доказательство. Алгоритм E7)—F0)
вычисляет значения / (а) и / (Ь), причем
Fn > {/ {а), / (&)}*.
Поэтому если х* = а или х* = ft, то неравенство D6),
очевидно, выполняется.
Пусть далее х* е (а, Ь) и /' (я*) = 0, /" (ж*) < 0.
Используя разложение/ (#) в ряд Тейлора около точки х =
= х* с остаточным членом в форме Лагранжа, получим
/ (*) > /S- # (я - **J/2, ж е Д. F1)
Пусть х* ЕЕ: 1#/г» #fc+iL k ЕЕ {0, 1, . . ., /г — 1}. Если
я* е [#fr, #fr + fXfr], то, подставляя в F1) д; = я;^, придем
к неравенству
/5 - Ffc < 2e;
если же я* е [яъ+1 — К xk+ih то, подставляя в F1) х =
= arfr+1, получим

Каждое из последних двух неравенств, ввиду очевидных
соотношений
Fn>Fk, Fn>f(xn+1),
ведет к неравенству D6). Теорему можно считать
доказанной, поскольку случай
х* ЕЕ [хп, Ъ] F2)
рассматривается аналогично.
Упражнение 8. Докажите в условиях теоремы 6
неравенство D6) для случая F2) (см. при этом работы [19, 22)).
Пример 5. Для многочлена D8) вычислить Р% с
точностью е = 1 на отрезке D = [3, 8].
Решение. Для решения задачи воспользуемся
алгоритмом E7)—F0), в котором положим X = 176,
поскольку
-176 < Р" (х), iGfl
(см. пример 6). Исходные данные для алгоритма:
к = 2|/еТ2 = 2/1/176 » 0,151,
Fo = Р (Ъ) = Р (8) = 378, х1 = 3.
Промежуточные результаты трех итераций вычислений по
формулам E8), D8) содержит следующая таблица:
г
1
2
3
4
3
5,516
7,259
9,046
-112
157,096
114,690
Fi
378
378
378
2,365
1,592
1,736
После третьей итерации вычислительный процесс
обрывается, так как очередное вычисленное значение аргумента
х4 = 9,046 > Ъ = 8
выходит за пределы отрезка D = [3, 8]. Далее, по
заключительной формуле F0) имеем
р = рз + е = 378 + 1 = 379.
Заметим, что в решаемой задаче искомое точное значение
НЗФ равно
Pl = P (8) = 378.
91

Пример 6. Для исходных данных примера 5
вычислить неопределенную оценку {Р"}Ъ блочным вариантом
алгоритма, который использовался при решении
примера 10 в главе III. При этом отрезок D = [3, 8] разбить
целыми числами на пять равных отрезков:
Dx = [3, 4], D2 = [4, 5], . . ., Db = [7, 8].
Решение. Искомую величину вычисляем по
формуле
{РЪ = {%!,%*, * • ч2б>°, F3)
где %±, . . ., Хъ — локальные неопределенные нижние
оценки второй производной Р" на отрезках D±, . . ., Db\
Р° (х) = 20*3 — 216я2 + 624х - 352 =
= х B0я2 - 216* + 624) - 352 =
= ж-ф (х) - 352 > x-^d. — 352 > {x^°Dj - S52}°Dj = %h
x Eflj, ; = 1,..., 5.
Вычислим абсолютный минимум -ф0 функции
г|) (х) = 20х2 — 216* + 624
и точку х° ее абсолютного минимума:
я|/ (*°) = 40*° - 216 = 0;
х° = 216/40 = 5,4;
фо = ф (^0) = ф E,4) = 40,8.
Далее табулируем функцию г|) в узлах деления
отрезка D:
X
ф(*)
3
156
4
80
5
44
Теперь легко составить таблицу
7
-ф0
3
г*
1
80
—112
2
44
—176
6
48
значений
3
40,8
-148
7
92
8
176
j
4
48
-64
5
92
292
92

Например,
Хг = {x^°Dl - 352}^ = {80-я - 352}S>f = 80- 3 - 352 = -112.
Согласно формуле F3) минимальный элемент третьей
строки последней таблицы дает искомую величину
{Р"}1 = _176.
Упражнение 9. Для сравнения вычислите
неопределенную оценку F3) для исходных данных примера 6, используя для
вычисления локальных оценок SBX, <2?2* • • •» ^-т* метод модификации
схемы Горнера (см. § 4 гл. III).

Глава V
РЕШЕНИЕ УРАВНЕНИЙ
§ 1. Постановка задач. Основные понятия
и обозначения
Обычно уравнением называют запись двух функций,
соединенных знаком равенства. Вместо одной из функций
может стоять число, в частности нуль. Мы здесь вместо
знака равенства при записи уравнений будем использовать
символ ~. Примеры записей уравнений:
/ (х) ~ О, ф (х) ~ -ф (ж), 4г2 — 2 ~ 34.
Если вместо переменной х подставить в уравнение
некоторое число, то уравнение превращается либо в числовое
равенство, либо в числовое неравенство. Любое число,
которое (при подстановке этого числа в уравнение вместо
переменной) обращает уравнение в равенство, называется
корнем этого уравнения. Корнем уравнения может быть
действительное либо комплексное число. В данной книге
рассматриваются уравнения относительно
действительных чисел.
Важной характеристикой уравнения является число его
корней. Могут встретиться следующие случаи.
1. Уравнение не имеет корней. Примеры:
х2 + 4 ^ 0, sin х ~ 2.
2. Уравнение имеет один корень. Примеры:
2х + 1 ~ 0, х = —1/2;
sin -^— ~ х2 — 2# + 2, х = 1.
3. Уравнение имеет несколько корней. Примеры:
Ах2 — 2 ^ 34, х = 3, х = —3;
94

sin (--?г- )~#2, # = 0, x=i\
sin я# ~ 2л:, # = —1/2, # = 0, # = 1/2.
4. Уравнение имеет бесконечное множество корней.
Приведем пример:
sin six ~ 1, х = 1/2 + 2Л, /с = 0, 1, 2, . . .
Относительно заданного уравнения можно
сформулировать несколько стандартных задач.
1. Определить число корней уравнения.
2. Указать отрезок [г~, г+] возможно меньшей длины,
который содержит все корни уравнения. (Задача
определения границ г~, г+ корней уравнения.)
3. Указать отрезок, которому принадлежит только
один корень уравнения. (Задача отделения корня.)
Указать возрастающую последовательность точек
таких, что между любыми двумя соседними точками
содержится точно один корень уравнения.
4. Вычислить с заданной точностью один корень
уравнения (любой, минимальный положительный,
принадлежащий заданному отрезку, ближайший к заданной
начальной точке и т. п.).
5. Вычислить с заданной точностью все корни
уравнения (или все положительные (отрицательные); или все,
принадлежащие заданному отрезку).
При изучении данной главы в качестве упражнений
можно для любого уравнения ставить и решать любую из
сформулированных выше стандартных задач.
Далее опишем некоторые свойства уравнений.
Уравнения называются равносильными, если эти уравнения имеют
одни и те же корни. Для любого уравнения: существует
равносильное уравнение вида
/ (х) ^ 0. A)
Например, для уравнения
<р (х) - ф (х) B)
уравнение A) будет равносильным, если положить
/ {х) = ф (х) — ф (х).
Преобразование уравнения, в результате которого
получаем новое уравнение, равносильное исходному,
называется равносильным преобразованием. Можно говорить о
равносильном преобразовании уравнения на заданном
отрезке Z), под которым понимается такое преобразование,
95

которое не изменяет корней лишь на отрезке D, а вне этого
отрезка корни могут изменяться.
Основными равносильными преобразованиями
являются:
1) сложение уравнения с любым равенством;
2) умножение либо деление левой и правой частей
уравнения на любое число, не равное нулю, либо на функцию,
которая не обращается в нуль на отрезке D.
Поскольку уравнение / (х) ~ О определяется заданием
функции /, то корни уравнения / (х) ~ 0 будем также
называть корнями функции /.
Корнями функции f (x) называются такие значения
х' аргумента х, при которых значения / (х) функции /
обращаются в нуль, т. е. / (хг) = 0.
Любая грамотно организованная вычислительная
процедура решения уравнения выдает, как правило, не
точное значение корня х', а фактически лишь указывает
некоторый отрезок
D' = [а\ Ъг]
достаточно малой длины, которому принадлежит корень
х'. Любая точка отрезка D' может быть принята за
приближенное значение х корня х'. Обычно в качестве
приближения х к корню берут середину отрезка Z)', т. е.
Я = с' = {а1 + Ъ')/2.
При этом погрешность вычислений оценивается
неравенством
| х - х' | < (&' - а')/2.
С вычислительной точки зрения корни уравнений
делятся на два основных типа: простые корни и кратные корни.
Простым корнем х уравнения / (х) ~ 0 называется
такой корень, в котором график функции / (х) пересекает
ось х под некоторым углом. При этом
/(*') = 0, Г(х')фО.
Если же корень х уравнения / (х) ~ 0 является точкой
касания графика функции / (х) оси ж, то такой корень
называется кратным корнем. При этом
/ (*') = 0, /' (х1) = 0.
Если
f(a).f(b)<0, C)
96

то отрезок D = [а, Ъ] содержит один или несколько
корней функции /. Выпишем условие монотонности функции
/ на отрезке D:
Г(х)фО, xe^D. D)
Если для функции / выполняются оба условия C), D),
то отрезок D содержит один простой корень функции / и
других корней функции / на отрезке D нет. При этом
отрезок D будем называть отрезком локализации корня
функции /. Проверка выполнения условий C), D) является тем
практическим правилом, которое позволяет
приближенно вычислять простые корни уравнений. Если отрезок D
содержит кратный корень, то для этого отрезка
выполнение условия D) невозможно.
Пусть вычисления ведутся с заданной точностью 8.
Обычно вычислительная процедура поиска одного корня
заканчивается, когда выделен некоторый отрезок D =
= [<z, Ь], для которого выполняются условия
Ь — а < 2&* E)
| / (с) |< 8, с = (а + Ь)/2. F)
Отрезки Z), которые удовлетворяют условиям E), F),
но для которых не проверены либо не удается проверить
выполнение условий C), D), будем называть
подозрительными отрезками.
Пусть, например, для отрезка D выполняются условия
E), F), но не выполнено условие C), точнее на концах
отрезка D функция / принимает значения одного знака (при
этом / (a)f (b) ^> 0). Тогда для подозрительного отрезка D
возможна одна из следующих трех ситуаций:
1) отрезок D не содержит корней функции /;
2) отрезок D содержит несколько близких между
собой корней функции / (чаще всего два простых корня);
3) отрезок D содержит один кратный корень.
Если на отрезке D имеет место одна из первых двух
ситуаций, то повышением точности вычислений
(уменьшением е) можно добиться прояснения ситуации. Однако
если отрезок D содержит только один кратный корень, то
никакое повышение точности вычислений, в общем
случае, не позволит ответить на вопрос: какая же из трех
указанных выше ситуаций имеет место на самом деле. Это
принципиальный факт 9

§ 2. Определение границ корней уравнения
Определение границ корней будем проводить для
уравнения, записанного в виде / (х) ~ 0.
Любое число г+ называется верхней границей корней
функции /, если для этого числа выполняется одно из
следующих двух условий:
1) / (х) > 0 при любом х > г+;
2) / (#) < 0 при любом я > г+.
Точно так же для нижней границы г~ корней функции
/ выполняется одно из таких условий:
3) / (х) ^> 0 при любом х < г~;
4) / (#) < 0 при любом ж<г.
Для вычисления границ корней алгебраических
многочленов можно предложить много различных способов.
Большинство из них, так или иначе, сводится к
последовательному решению линейных или квадратных
неравенств. В трех нижеследующих примерах
иллюстрируются три таких различных способа вычисления верхней
границы rY корней многочлена
Р (х) - хь — 18х4 + Ю4г3 -176*2 —105* + 194. G)
Пример 1. Разбиваем многочлен Р (х) на сумму
более простых многочленов Рt (x) так, чтобы у каждого
многочлена Pt коэффициент при старшей степени х был бы
положительным:
Р (х) = Рг (х) + Р2 (х) + 194,
Рг (х) = хъ — 18я4, Р2 {х) = 104.Г3 — 176я2 - 105*.
Вычислим ri и г-2 — верхние границы корней многочленов
Рг и Ро соответственно.
Неравенство Рг (х) = «г4 (х — 18) > 0 справедливо
при любых х ^> 18. Поэтому г? = 18.
Для вычисления г2+ проведем дополнительные
преобразования (полагая, что х ^ 1):
Р2 (х) = 104л:3 - 176х2 - 105х >
> 104л;3 - 176.Z2 - 105х2 = я2 A04л: - 281) > 0
при любых х > 281/104. Поэтому г2+ = 281/104,
Окончательно находим
г+ = К, г2+}* - {18, 281/104}* = 18,
Пример 2. Пусть снова
Р И = ^i W + ^2 И + 194,

но
р1 (х) = хъ — Ш4 + 8Ь3,
Р2 (х) = 2Ъх* — 176л:2 - 105*.
Вычислим г\ и rj. Заметим, что
Рх (х) = х3 (х2 - 18* + 81) =х*(х — 9J > 0
при любых х > 0. Поэтому ri" = 0.
Докажите утверждение:
Р2 (х) = а; B3*2 - 176а: - 105) > 0
при любых х р> 10. Поэтому г2 = 10. Окончательно
находим
г+ = К, г2+}* = {0, 10}* = 10.
Пример 3. Доказать, что в качестве верхней
границы г+ корней многочлена G) можно взять г+ = 8.
Доказательством служат следующие два утверждения:
Р (8) > 0; (8)
Р' (х) > 0 при любых х > 8. (9)
В справедливости неравенства (8) убеждаемся
непосредственным вычислением значения Р (8) = 378.
Докажем далее неравенство (9):
Р' (х) = Ьх* - 12х* + 312я2 - 352^ - 105,
Р' (х) = Рг (х) + Р2 (х),
Рг (х) = 5х* - 72х3 + 256х2, A0)
Р2 (х) = 56.г2 - 352х - 105.
Проведем анализ многочленов Рг и Р2:
Р1 (х) = х2 [Ъх2 — 12х + 256) = х2а (х)ч
G (8) = 0, а' (х) = Юя — 72 > 0 при х > 8.
Поэтому а (ж) ^> 0 при я ^> 8, и, следовательно,
i\ (я) > 0 при х > 8. (И)
Далее исследуем многочлен Р2 (х). Во-первых, Р2 (8) =
= 663 > 0. Затем
Р2 (х) = П2х — 352 > 0 при ж > 8.
Поэтому
Р2 (ж) > 0 при х > 8. A2)
Соотношения A0) — A2) доказывают утверждение (9).
Тем самым полностью доказано утверждение,
содержащееся в условии примера 3.
99

При доказательстве многих неравенств в ходе решения
примеров использовалась
Лемма 1. Произведение двух монотонно
возрастающих функций также является монотонно возрастающей
функцией.
Упражнение 1. Для каждого из последних трех
примеров проведите строгое доказательство того, что вычисляемая в
примере величина г+ действительно является верхней границей корней
многочлена G).
Упражнение 2. Постройте алгоритм и проведите
вычисление нижней границы г" корней многочлена G).
Пример 4. Указать отрезок, которому
принадлежат все корни уравнения
sin nx ~ x/G. A3)
Поскольку нер авенство
—1 <; sin nx <; 1
верно для любых х, то левая часть уравнения A3) может
оказаться равной правой части этого уравнения только
для тех х, которые удовлетворяют неравенству —1 ^
^ х/6 <С 1. Таким образом, все корни уравнения A3)
принадлежат отрезку [—6, 6].
Для уравнения A3) легко ответить на вопрос о числе
его корней и решить задачу отделения всех его корней.
В частности, все положительные корни уравнения A3)
принадлежат отрезкам [0, 1], [2, 3], [4, 5]. На каждом из
этих отрезков график функции у = sin nx является
выпуклой вверх кривой, которая пересекается прямой у —
= х/6 в двух точках. Чтобы убедиться в этом, достаточно
вычислить значения функции / (х) = x/Q — sin nx в
середине каждого отрезка и на его концах. Однако не всегда
дело обстоит так просто.
Упражнение 3. Определите, сколько положительных
корней имеют уравнения
sin х ~ х/7,78; sin x ~ аг/7,79.
Дайте строгое обоснование своим выводам.
Пример 5. Рассмотрим функцию
/ (х) = ех?2 — е*/з + 2 sin (x + 2)+ sin Bя — 1). A4)
Эта функция имеет бесконечно много отрицательных
корней, для которых не существует нижней границы.
100

Поставим задачу указать верхнюю границу г+ корней
функции A4). Имеем
/ (х) = е*/а — е*/з + 2 sin (х + 2) + sin Bх — 1) >
_ дос/з — 3 = Ф (х). A5)
Дальнейшее исследование проводится для х ^> О и
опирается на следующие очевидные неравенства:
2,7 <е< 2,72,
е*/2 _ gsc/з > о при х > 0.
Исследуем производную вспомогательной функции ф:
=_ txl2 L ex'3 \. J_ ех/2 L ех/3 jL(ex/2 exf3
Следовательно, функция ср (х) монотонно возрастает.
Теперь достаточно найти такое значение х, при котором
Ф (х) ^> 0. Попробуем взять х = 6:
ф F) = *з _ е2 _ з > 2,73 — 2,722 - 3 > 0. A6)
Далее выпишем три неравенства, из которых первое
следует из A5), второе есть следствие монотонного
возрастания функции ф, третье следует из A6). Просуммировав
эти три неравенства, придем к соотношению A7):
/ (я) > Ф (х)
~^~ Ф (х) > Ф F) при х ^> 6
фF)>0
/(я?)>0 при я>6. A7)
Таким образом, можно положить г+ = 6.
Дальнейшим подбором можно уточнить эту границу.
Например,
ф D) =е2 - е^ - 3 > 2,72 - 2,724/3 - 3 >
>2,72 - 2,72-1,4 — 3 = 0,482 > 0.
Здесь использованы соотношения
2,724/3 = 2,72ухД2, 1^2/72 < 1,4.
Теперь в качестве верхней границы корней функции A4)
можно взять г+ = 4.
101

§ 3. Отделение корней
Корень х ЕЕ (а, Ъ) некоторого уравнения называется
изолированным на отрезке D = [а, Ь], если отрезок D не
содержит других корней этого уравнения. Задача
отделения корней для заданного уравнения заключается в
определении отрезков с изолированными на этих отрезках
корнями.
Пример 6. Отделить все положительные корни
функции
/ (х) = е*/2 — е^ъ + 2 sin (х + 2) + sin Bx — 1). A8)
Из решения примера 5 следует, что все положительные
корни функции / принадлежат отрезку [0, 4]. Вычислим
в целочисленных точках этого отрезка значения функции/.
Результаты вычислений поместим в таблицу:
X
0
0,9771
1
1,3768
2
—0,6019
3
-1,1134
4
3,6936
Поскольку на концах двух отрезков [1, 2] и [3, 4] функция
/ принимает значения разных знаков, то каждый из этих
отрезков содержит хотя бы один корень функции /.
Таким образом, функция A8) имеет не менее двух
положительных корней. Далее мы докажем, что эта функция
имеет точно два положительных корня.
В решении примера 9 из гл. III показано, что
производная /' (х) = я|) (х) принимает на отрезке [3, 4] только
положительные значения. Это означает, что функция
/ (х) монотонно возрастает на отрезке [3, 4] и,
следовательно, отрезок [3, 4] содержит только один корень
функции /.
Далее исследуем поведение функции / на отрезке D2 =
= [1, 2]. Вычислим значение производной
/' (х) = t|) (х) = \ е*/* - 4" *Л/3 +
+ 2 cos (x + 2) + 2 cos Bx — 1) A9)
в середине отрезка D2: г|э A,5) = —2,1963. Если
производная /' (х) остается отрицательной на всем отрезке [1, 2],
то функция / (х) монотонно убывает и отрезок [1, 2]
содержит только один корень функции /.
Чтобы убедиться в том, что функция г|э (х) принимает
только отрицательные значения на ZJ, следует построить
102

вспомогательную мажоранту
тр+(х) >ф (z), ^GD2,
и вычислить {я()+}В2. Если окажется, что {ф+}д, < 0, то,
очевидно, г|) (х) < 0 для всех х ЕЕ D2.
Квадратную мажоранту i|)+ (х) можно было бы
построить тем же методом, которым в примере 9 из гл. III
строилась квадратная миноранта Р" (х) для отрезка [3, 4]. Мы
здесь построим квадратную мажоранту более простым
способом, при этом получим и более грубую, по сравнению
с методом примера 9 из главы 3, оценку сверху значений
функции г|э (х) на D2. Однако в данном случае такой
грубой оценки оказывается вполне достаточно.
Квадратную мажоранту г|)+ (х) на отрезке D2 — [1, 2]
для функции A9) сконструируем по формуле
где
- 2 {cos (ж + 2)}°Dt - 8 {cos B* — 1)}Ъ2 =
= _1_е _ -ij-ei/з _ 2 cos я — 8 cos 3 = 10,208.
Перепишем функцию г|)+, вычислив ее коэффициенты:
-ф+ (ж) = -2,1963 - 1,7775 (х - 1,5) + 5,104 (х - 1,5)а.
Теперь вычисляем
{^+ (х)}Ъ% = -0,0315.
Монотонность функции / на отрезке D2 = [1, 2] доказана.
Мы показали, что все положительные корни функции
A8) принадлежат отрезку [0, 4], а на отрезках [1, 2] и
[3, 4] находится по одному корню функции /. Для
завершения решения задачи отделения положительных корней
функции / осталось доказать, что на оставшихся отрезках
Z>! = [0, 1], D3 = [2, 3] нет корней функции A8).
Последнее доказывается вычислением оценок {f}Dt и {/}ё8* для
которых выполняются неравенства
{/>5.>0, {/}?,< 0. B0)
Так, например, для отрезка D3 имеем
{/}Ь, = {/ B,5) + (х- 2,5) /' B,5) +
+ {/"}ё. (х - 2,5J/2}Ва = -0,2842,
J03

где
{ПК = 4"
— 2 {sin (x + 2)}\ — 4{sin Bx - 1)}\ = 6,904.
Упражнение 4. Для функции A8) на отрезке D± = [0, 1]
вычислить оценку {/J^i удовлетворяющую неравенству B0).
§ 4. Вычисление всех корней на заданном отрезке
Дадим грубое описание алгоритма, который
практически позволяет вычислить все корни функции / на
заданном отрезке D, в tjm числе и кратные корни. Алгоритм
заключается в последовательной выбраковке и исключении
из дальнейшего рассмотрения отдельных участков
исходного отрезка D, заведомо не содержащих корней
функции /. При этом из отрезка D выделяются отрезки
меньшей длины Dk, которые мы назовем частичными и на
которых только и могут находиться искомые корни. Каждый
очередной такт алгоритма проводит исследование
крайнего правого частичного отрезка Dk = [а&, Ьк] и
заключается в следующем.
1. Вычисляются ск = (ак + Ьк)/2 и значение / (ск).
2. Если / (ск) ^> 0, то конструируется квадратная
миноранта для функции / на отрезке Dk; если / (ск) < 0, то
конструируется мажоранта.
3. Часть отрезка Dk, расположенная между корнями
миноранты (мажоранты) из дальнейшего рассмотрения
исключается. При этом возможны три случая: отрезок Dk
заменяется на: а) два новых частичных отрезка; б) один
новый частичный отрезок; в) отрезок Dk полностью
исключается из дальнейшего рассмотрения.
4. Вычисления заканчиваются, когда для каждого из
оставшихся частичных отрезков Dk выполняются условия
E), F).
Середину каждого из частичных отрезков Dk,
удовлетворяющих условиям E), F), можно условно (см.
обсуждение в § 1) принять за приближенное значение корня
функции /. При необходимости проводят дополнительное
исследование подозрительных отрезков Dk. Более детально
с данным алгоритмом познакомимся на нижеследующем
примере.
Пример 7. Вычислить с точностью до е = 0,1 все
положительные корни функции
/ (х) = е*'2 — е*'3 + 2 sin {х + 2) + sin Bх - 1),
М

Выпишем производные этой функции
/' (Х) = -\- е*'* — 4" еХ/3 + 2 cos (я + 2) + 2 cos Bх — 1),
f (х) = -L ^/2 _ -L ^/з __ 2 sin (ж + 2) — 4 sin Bж — 1).
В качестве исходного принимаем отрезок
Do= [а0, Ьо] = [0; 4],
поскольку все положительные корни функции /
принадлежат этому отрезку (см. пример 5).
Такт 1.
с0 = (а0 + Ь0)/2 = @ + 4)/2 = 2,
/ (с0) = / B) = -0,602, /' (с0) = /' B) = -2,577.
Поскольку / (с0) <С 0, то конструируем мажоранту
Р+о (х) =jB) + (x- 2) /' B) + (х- 2Y {/"}+DJ2. B1)
Вычисляем оценку
- 4 {sin Bх - 1)}Ь. = 4"е2 ~ 4" + 2 + 4 = 7'736-
Вводя новую переменную Д = х — 2, подставляя
вычисленные значения коэффициентов
/ B), /' B), {f%J2
в формулу B1) и приравнивая полученное выражение
нулю, придем к квадратному уравнению
-0,602 - 2,577-Д + 3,868-Д2 ~ 0,
которое имеет два корня
Дх = -0,183, Д2 = 0,850.
Корнями мажоранты B1) будут числа
хх = Со + Дх = 2 - 0,183 - 1,817,
х2 = с0 + Д2 = 2 + 0,850 = 2,850.
Из отрезка DQ исключается интервал (х.и х2). При этом
получаем частичные отрезки Du D2*
Вычисления в последующих тактах алгоритма
проводим без подробных пояснений. В начале описания
каждого такта выписываем все частичные отрезки, которые
подлежат дальнейшему исследованию.
105

Такт 2.
D± = [0; 1,817], D2 = [aa, 62] = [2,850; 4],
c2 = (a2 + 62)/2 - B,85 + 4)/2 - 3,425,
/ (c2) = 0,478, /' (ca) = 4,850,
*2 И = / (C2) + (* - C2) f (C2) + (X- C2f {/"K/2.
- 2 {sin (ж + 2)}?2 - 4 {sin B* - 1)}?,=
= -L ei.«5 L е^ззз __ 2 sin 6 — 4 sin 7 = — 1,4M,
A = x — c2 = x — 3,425;
0,478 + 4,85-Д - 0,7255-A2 ~ 0,
Ax = -0,095; A2 = 3,438;
xi — C2 + ^i = 3,330; x2 = c2 + A2 = 6,863.
Такт 3.
Dx = [0; 1,817], JD3 = ra3, b3] - [2,850; 3,330],
c3 - 3,090; / (c3) = -0,8648; /' (<?8) = 3,049;
{f }+з = Л. ^i,665 _ J_ ^0,95 _ 2 Sin 4,85 — 4 sin 4^ = 7,015;
- 0,865 + 3,049-Д + 3,5075.Д2 = 0;
Дх = -0,931; Xl = 3,09 - 0,931 = 2,159;
A2 = 0,062; ^r2 = 3,09 + 0,062 = 3,152.
Поскольку хг < a3, .r2 6= ZK, то из отрезка ZK
исключается интервал [a3; ^2)- При этом оставшийся частичный
отрезок
[*2, Ь3] = [ЗД52; 3,330] - [а4, Ь4] = Д4
удовлетворяет условию E), но не удовлетворяет условию
F). Поэтому отрезок D4 подлежит дальнейшему
исследованию.
Замечание. Если для данного отрезка /L, или
предварительно для отрезка ZK, либо для отрезка D2
была решена методом предыдущего параграфа задача
отделения корня, то середину отрезка ZL можно было бы
принять за приближенное значение первого найденного
корня, а отрезок ZL из дальнейшего рассмотрения исключить.
106

Т а к т 4.
Dx = [0; 1,817], Dt = [3,152; 3,3301,
с4 = 3,241; / (с4) = —0,335; /' (с4) = 3,946;
{/'U = 6,134;
-0,335 + 3,946-А + 3,067-А2 ~ 0;
Дх = -1,367; Д2 = 0,080;
хх = 1,874; х2 = 3,321.
Для очередного частичного отрезка
Вь = [аъ, Ъъ] = [3,321; 3,3301
выполняются оба условия E) и F), так как
Ъъ - аъ = 3,330 - 3,321 = 0,009 < 0,2 = 2е,
с5 = 3,326; / (сь) = 0,019 < 0,1 = е.
Поэтому первый искомый корень х[ с заданной точностью
вычислен и можно положить х\_ ~ хг = 3,3.
Такт 5.
Z?! = [0; 1,817], сх = 0,909;
/ (Cl) = 1,412; /' (Cl) = -0,242;
{/")Ъ, =^-е° Lео,еоб_2sin^-_4sin-2- = - 5,954;
At = -0,731; Д2 = 0,649;
Xl = 0,178; х2 = 1,558.
Такт 6.
Ds = [0; 0,178], D? = [1,558; 1,817],
с7 = 1,688; / (с7) = 0,141; /' (с7) = -2,573;
|/"}о7 = -i.co.779 _ _1_ео,бо« _ 2 sin 3,558 — 4sin 2,116 =
= -2,270;
0,141 - 2,573-А - 1,135-А2 ~ 0;
Ai = -2,321; Аа = 0,054;
xt = -0,633; ж2<>= 1,742.
Для очередного частичного отрезка
Ds = [1,742; 1,817]
выполняются оба условия E), F), так как
bs - а8 = 1,817 - 1,742 = 0,075 < 0,2 = 2е,
с8 = 1,7795; | / (с) \ = | -0,016 |< 0,1 = е.
107

Поэтому, округляя величину с8 до первого знака после
запятой, можно за приближенное значение второго
вычисленного корня принять величину хг = 1,8.
Такт 7.
D6 = [0; 0,178], cG =¦• 0,089; / (ce) = 1,020;
f (св) = 0,550;
{/"}Б6 = -i- е° — -L е0'0595_ 2 sin 2 — 4 sin (— 0,644) = 0,715.
Поскольку / (cq) ^> 0, а квадратная миноранта
Pi (х) = 1 (се) + (х- с.) f (с.) + (х - СвJ {f }ЪЛ
не имеет действительных корней, то это означает, что на
отрезке D6 нет корней функции /.
Упражнение 5. Доказать последнее утверждение.
Решение примера 7 закончено. При этом найдено два
положительных действительных корня функции /,
значения которых с точностью до 0,1 задаются величинами
Si = 3,3; 5*2 = 1,8.
§ 5. Вычисление корня.
Монотонные вычислительные процессы
Ниже описывается метод построения монотонной
последовательности
точек #fr, сходящихся к ближайшему относительно
произвольной начальной точки х0 корню функции /. При этом
по нашему желанию последовательность B2) может либо
монотонно возрастать и сходиться к корню,
расположенному справа от начальной точки #0, либо
последовательность B2) будет монотонно убывать и сходиться к корню,
расположенному слева от точки х0. Основное описание
ниже дается для случая возрастающей
последовательности B2).
Пусть дан отрезок [a, b] = D, х0 = а,
/ (*о) > 0 B3)
и X — минимальный на D корень функции /. При этом
/(г)>0, *,<*<Я,/(А,) = О. B4)
108

Пусть, далее, для любой точки х% ЕЕ D мы можем
построить непрерывную на D вспомогательную функцию
ак (х) = а (х, хк), B5)
обладающую следующими свойствами:
1) а (хк, хк) = / (хк), а^хк<Ь; B6)
2) <х(х, zk)<f(x), xk<x^b; B7)
3) решение уравнения
а (х, хк) aO^e [**, Ы, B8)
является простой задачей. Корень уравнения B8)
обозначим через хк+1, т. е.
Ч) = 0, хк< хк+1 < 6. B9)
Отметим, что уравнение B8) всегда имеет решение,
если только хк < К. Доказательство последнего
утверждения сводится к выявлению того, что функция B5)
принимает значения разных знаков на концах отрезка [хк, к],
что фактически доказывается формулами, которые ниже
моделируют такты 1, 2 алгоритма.
Функцию <хк (х) = а (х, хк) будем называть
минорантой для функции /, проведенной через точку хк.
Определение корня хк+1 функции ак (х), лежащего правее точки
хк, является содержанием к-го такта алгоритма построения
возрастающей последовательности B2). Многократное
выполнение подобных тактов является уже содержанием
всего алгоритма в целом. Вычислительный процесс
построения последовательности B2) обычно заканчивают,
когда для двух очередных точек этой последовательности
впервые выполнится неравенство
Хк+1 — Хк < 8,
где 8 — достаточно малое положительное число —
заданная точность вычисления. При этом полагают х ^ хк+1.
Иногда в качестве критерия окончания вычислений
используют неравенство / (хк) < 8.
Проведем моделирование первых двух тактов
алгоритма построения возрастающей последовательности B2) при
условии B3). При этом описываемые ниже модели тактов
фактически содержат и обоснование алгоритма.
Такт 1.
* = 0, / (*0) > 0, а = х0 < К < 6, (*)
109

а0 {х) = а (#, х0)
а0
= а
= / («о) > О
> О
а0
= О
< А,
О = а0 (х±) = а
(**)
Здесь формулы (*) являются исходными данными для
первого такта. Результатом первого такта является точка
хг. Цепочка формул (**) нужна для формирования
исходных данных второго такта.
Т а к т 2.
> 0, хх < X ^ Ъ (#)
(х) =а
t
«1 (xi) =. а (хи хг) = f (xi) > 0
a1(X)=a(X,x1)<f(l)=0
> 0
«i (x2) = 0
^1 < #2 < ^
0 =
(•¦)
Результатом выполнения второго такта является
точка х2, которая вместе с неравенством / {х2)^> 0 образует
исходные данные для третьего такта. В третьем такте
будет получена точка х3 и т. д.
Многие широко известные итеративные процессы
вычисления корней уравнений можно рассматривать как
частные случаи описанного выше алгоритма. К таковым
относятся метод Ньютона, модифицированный метод
Ньютона, метод хорд, метод касательных парабол и т. д.
Для практической реализации алгоритма нужно
указать способ построения функций a (x, xk).
110

В качестве функции а можно использовать линейную
миноранту
а (х, хк) = / (хк) + (х- х,) L, C0)
L = {f}°D или L = {ПЪ; C1)
либо квадратную миноранту
а (х, хк) = / (хк) + (х- хк) f (хк) + (х -xkfU2, C2)
L = {f}°D или L = {/"}Б. C3)
Примечание. В данном параграфе L — либо
граничная константа, либо ее неопределенная оценка.
Упражнение 6. Докажите, что функция C0), C1), а
также функция C2), C3) удовлетворяют условиям B6), B7), B8),
в частности, докажите справедливость следующего утверждения.
Лемма 2. Если f (xk) ^> 0 и отрезок [xki b]
содержит хотя бы один корень функции /, то квадратная
парабола C2), C3) имеет два действительных корня \1г, \х2,
причем \1г < xk < |i2.
Указание. Для доказательства леммы
необходимо воспользоваться формулой Лагранжа для дважды
дифференцируемой функции /.
Рассмотрим применение линейной миноранты C0).
В качестве очередной точки хк+1 берется решение
уравнения а (х, хк) ^ 0, т. е. точка хк+1 удовлетворяет
равенству
а (хк+1, хк) = 0. C4)
С учетом формулы C0) перепишем равенство C4) в виде
/ (хк) + (хкп — хк) L = 0,
откуда получаем
хк+1 = хк — -^^- , к = 0,1, 2, 3,... C5)
Пример 8. Вычислить наименьший
положительный корень функции
/ (х) = 2 - х2 — cos (x — 1/3). C6)
Так как / @) > 0, / B) < 0, то отрезок [0, 2] содержит
хотя бы один корень функции C6)
к ЕЕ [0, 2] =Я, f (к) = 0.
Легко убедиться, что
/' (х) = -2х + sin (х - 1/3) > -5, х е [0, 2],
111

и поэтому можно положить
L = {/'}В = -5.
Используя это значение L в формуле C5) и положив х0 =
= О, придем к следующей рекуррентной
вычислительной процедуре:
Хо = 0, к = 'о, 1, 2, ... ' C7)
После 27 итераций по формулам C7), C6) на ЭВМ с
пятиразрядной десятичной сеткой представления чисел
Таблица 1
xQ=0
*t =0,21101
х2 =0,40360
х3 =0,57152
1,05504
0,96295
0,83958
0,70160
0,21101
0,19259
0,16792
0,14032
г = 1,1454
было получено приближенное значение корня х =
= х27 = 1,1454. Начало этого вычислительного процесса
представлено в табл. 1.
Пример 9. Решить предыдущий пример, применяя
вычислительный процесс, основанный на использовании
квадратной миноранты C2), C3).
Выпишем очевидное неравенство для второй
производной функции C6):
f (х) = —2 + cos (х - 1/3) > -3.
Поэтому можно положить
L = {Г)Ъ = -3, L/2 = -1,5. C8)
Введем обозначение приращения аргумента
Afr = х — хк, At = хъ+1 — хк C9)
и перепишем уравнение а (х, хк) ~ 0 в виде
/ (хк) + Г Ы-Лк - 1,5-А? ^ 0. D0)
112

Здесь учтены формулы C2), C8), C9). Очередная точка
#fc+i будет получена по формуле
Zk+i = хк + At,
где At — положительный корень Д& = А? уравнения D0)
(см. лемму 2). Используя формулу для вычисления
корней квадратного уравнения, окончательно получим
следующие формулы:
хо = 0, хк+1 = хк + А$,
- f Ы/2]/15
ft = 0,1,2,...
За четыре итерации по формулам D1), C6) приходим к
тому же результату, который в предыдущем примере был
получен за 27 итераций. Численная реализация
вычислительного процесса D1), C6) представлена в табл. 2.
Н
Ч
Х2
Х3
Ч
X
= 0
= 0
= 1
= 1
= 1
к
,73667
,07509
,14290
,14543
1
0
0
0
,05504
,53756
,10690
, 00397
—
-0
^
л
—1
Таб
,32719
,08085
,4746
,56181
—
0
0
0
0
лица 2
4
,73667
,33842
,06781
,00253
В заключение сделаем ряд замечаний.
1. Пусть мы не знаем, имеется ли на отрезке D = [а, Ь]
корень функции /. Если при этом / (а) ]> 0 и монотонно
возрастающая (при х0 - а) последовательность B2),
организованная с помощью миноранты C0), C1) либо C2),
C3), выходит за пределы отрезка [а, Ь], т. е. некоторое
очередное хк ^> 6, то это служит доказательством
отсутствия на отрезке [а, Ь] корней функции /.
2. Для организации монотонно убывающей
последовательности B2) при / (х0) )>0в качестве очередной
точки хк+1 следует брать минимальный корень квадратной
миноранты C2), C3) (см. лемму 2).
3. Если в начальной точке / (х0) < 0, то вместо
минорант следует использовать мажоранты, которые получим,
113

если в формулах C0)—C3) положим
L = {/'}? или L == {ГУо
вместо формулы C1) и
L={ffD или Ь = {Щ
вместо формулы C3).
4. В некоторых случаях (например, для
алгебраических многочленов) оценка | L | граничной константы резко
возрастает с ростом длины исходного отрезка D = [а, Ь].
Поскольку | L | стоит в знаменателе формул для
приращения аргумента (см. формулы C5), D1)), то
вычислительный процесс резко замедляется при большой разности
Ъ — а. В подобных случаях целесообразно применять
либо блочную оценку граничной константы (см. § 6 гл. 3),
либо блочный вариант для всего вычислительного
процесса, при котором исходный отрезок!) делится на более
мелкие отрезки D7-, к каждому из которых применяется
алгоритм описанного выше типа. При этом для каждого
отрезка Dj учитываются предыдущие замечания. Здесь
может также оказаться полезным выполнение следующего
упражнения.
Упражнение 7. Сформулируйте и докажите
утверждения о существовании корней уравнения в зависимости от знака
неопределенных оценок граничных констант. (По этому поводу см.
лемму 1 из предыдущей главы.)
Пример 10. Вычислить с точностью 8 = 0,0001
максимальный корень многочлена
р (Х) = хь -18*4 + 104г3 - 176*2 - 105* + 194. D2)
Решение. В примере 3 вычислена верхняя
граница корней этого многочлена г+ = 8. Поскольку Р (8) =
= 378 ]> 0, Р C) = —112 <С 0, то максимальный корень
х% многочлена D2) находится на отрезке D = [3, 8].
В примере 6 предыдущей главы была найдена для
многочлена D2) неопределенная оценка {Р"}Ъ = —176, т. е.
-176 <Р" (я), xGfl = [3, 8].
Для вычисления максимального на отрезке D корня х%
организуем монотонно убывающую последовательность
точек {хь}, сходящуюся к корню х'%, по формулам (см. [17])
х0 = 8, L = 176, хк+1 = хк + Дь
А, = (Р'к - Y{Pl:f + 2PkL)/L, D3)
Рк - Р Ы, Р'к = Р' Ы, к = 0, 1, 2, ...
114

Критерием окончания вычислений по этим формулам
является выполнение неравенства
Ак > -0,0001.
При этом за приближенное значение искомого корня х*
принимается величина х = хк+1.
Формула для Afr в D3) получена из условия, чтобы
точка ,Tfc+1 являлась меньшим корнем (см. лемму 2)
квадратной миноранты C2), C3). Здесь учитывается, что Р* > 0,
в частности Ро = Р (х0) ]> 0, и принято обозначение
L = | {Р"}Б I = I L |.
Проводя вычисления по формулам D3), D2), после 8
итераций приходим к приближенному значению искомого
корня
х'х » х = xs = 3,80418.
В заключение отметим, что в работе [16] для решения
данного примера используется более простой алгоритм,
в котором не требуется знания неопределенной оценки
{Р"}Б> Однако решение там получено после 833 итераций
(против 8 здесь). Заметим также, что на отрезке [х*, 8j
многочлен D2) принимает два экстремальных значения и
поэтому применить здесь методы с локальной сходимостью
(например, метод Ньютона) нельзя.
§ 6. Вычисление простых корней
Пусть
/(а)./(Ь)<0, D4)
т. е. на концах отрезка D = [а, Ь] функция / принимает
значения разных знаков. Выполнение условия D4)
означает, что на отрезке [а, Ь] есть корень функции /.
Рассматривается задача вычисления с заданной точностью
е ^> 0 корня х ?Е D функции / при условии D4). Для
решения этой задачи существует группа краевых методов,
которые объединяет общая идея, положенная в основу
этих методов. Алгоритмы краевых методов при условии
D4) строят последовательность вложенных отрезков:
[а, Ъ] = [а0, Ьо] Z) Ui, Ьг] Ц) [а2, Ь2] ZD . . . Z) [ап, Ьп],
D5)
причем длина каждого последующего отрезка меньше
длины предыдущего и каждый последующий отрезок со-
115

держит корень функции /. Опишем процедуру А
построения очередного отрезка [ак+1, 6^+1], предполагая, что для
исходного заданного отрезка [ак, Ьк] выполняется условие
Описание процедуры А.
1. Выбираем точку ск ЕЕ (ак, Ьк).
2. Вычисляем / (ск).
3. Если / (ск) = О, то ск — искомый корень
функции /.
4. Пусть / (ск) ф 0. Тогда
если /Ы-/Ю<0; то [ак+ъ Ьк+1] = [аъ ск];
если /Ы-/К)>0' то [ак+ъ bk+1] = [ckJ bk].
После выполнения п. 4 процедуры А гарантируется
выполнение неравенства
т. е. отрезок [afc+1, bk+1] содержит корень функции / и к
нему вновь можно применить процедуру А.
Последовательность отрезков D5) и строится путем
последовательного применения процедуры А вначале к отрезку [а0, Ьо],
затем к отрезку [а1ч fej и т. д.
Различные краевые методы отличаются друг от друга
тактикой выбора точки ск. Широко известными
представителями краевых методов являются следующие методы.
1. Метод половинного деления [7, с. 118], для которого
Ск = (dk + h)/2, ск = ск. D6)
2. Метод хорд [7, с. 120], для которого
Вычислительный процесс по методу хорд заканчивается,
когда впервые выполнится неравенство
I Ск | < 8.
При этом полагают х' ^ ск+1. Однако здесь вопрос о
погрешности такого приближения к корню х' остается
открытым.
По методу половинного деления вычисления
заканчивают при выполнении неравенства
&* — <**< 2е {к = п). D8)
116

При этом полагают
х' ~ (ап + Ьп)/2 = х, D9)
а погрешность приближенного значения х оценивается
неравенством
I * - *' I < (Ьп - а»)/2 < е. (гH)
Для метода половинного деления
Ьх — а± = F — а)/2,
Ь2 — а2 == — (pi — а{) = >22- (Ь — а)-
Продолжая подобным образом далее, получим
h — ak= -^ F — а).
Подставляя это выражение (при к = п) в E0), придем к
неравенству
{Ъ - а)/& < 2n+1. E1)
Минимальное значение тг, удовлетворяющее этому
неравенству, указывает число итераций (шагов), необходимых
для вычисления корня методом половинного деления с
погрешностью, не превышающей заданного 8.
Если функция / вычисляется просто, то при высокой
требуемой точности следует пользоваться методом
половинного деления. Однако нередко возникают задачи,
когда вычисление каждого значения функции / требует
значительных усилий (функция / задана громоздкой формулой
или, например, значение функции / получают в результате
проведения некоторого эксперимента и т. д.). В подобных
случаях можно рекомендовать комбинированный краевой
метод, при котором
Ck = QCk + A ~ q) с'ъ, 0 < q < 1, E2)
где ci, cl определяются формулами D6), D7). Вопрос о
наилучшем значении q остается открытым. Мы
рекомендуем брать для q одно из следующих значений: 1/2; 1/4;
0,2. При этом меньшее значение следует брать при
большей требуемой точности (при меньшем г) и лучшей
начальной локализации корня.
Весьма перспективным, на наш взгляд, является
применение комбинированного метода, в котором значения q
изменяются в процессе вычислений, например по такому
закону:
9о = U ft = 1/2*. * = 1, 2, . . . E3)
117

При этом, согласно формуле E2), точки ск будут
определяться формулами
со = Со, сг = (с[ + Ci)/2,
с2 = (С; + Зсг)/4, сз = (с; + 7^/8 E4)
и т. д.
Комбинированный метод обычно быстрее снижает
длину отрезков последовательности D5) по сравнению
с методом половинного деления, и для комбинированного
метода также можно пользоваться формулами D8)—E0).
Пример 11. Комбинированным методом с
использованием тактики выбора параметра q по формулам E3)
вычислить с точностью е = 0,01 корень уравнения (см.
пример 8)
f(x) = 2-z2- cos (x - 1/3), х е [0, 2]. E5)
Опишем подробно два первых такта применения к
данному уравнению процедуры А с использованием формул D6),
D7), E2)-E4).
Такт 1.
[а0) Ьо] = [0, 2], q0 = 1,
/ Ы = / @) = 1,0550; / (Ьо) = / B) = -1,9043;
с0 = (а0 + 60)/2 = @ + 2)/2 = 1,
со = ЧЧ + A — q) с'о = 1-Со + A — 1)-Со = с0 =1,
f(c0) =/(!) = 0,2141.
Поскольку / (с0) > 0, / (Ьо) < 0, то
[ах, 6J = [с0, Ьо] = [1, 2J.
Такт 2.
К, 6J = [1, 2], qi = 1/2.
/ (в1) = / A) = 0,2141; / (Ь,) = / B) = -1.90-W;
с; = (в1 + 6i)/2 = A + 2)/2 = 1,5;
" _ ajf (b{) - bj (Д1) _ !•(-1,9043)-2.0,2141, 1(И1.
1— /Fi)-/(«i) ~ -1,9043-0,2141 —1>1 м'
t'i = gici + A — <7i) cj = (c[ + ci)/2 =
= A,5+ l,10il)/2 = 1,»MI3
/ (Cl) = / A,3006) = -0,2591.
Поскольку / (ax) > 0, / (cx) < 0, то
[a2, b2) = [ax, cj = [1; 1,3006].
118

Аналогичным образом проведя еще две итерации, в
которых точки с2, с3 вычисляются по формулам E4), придем
к отрезку
[а4, Ь4] = [1,1396; 1,1545], E6)
для которого
Ь4 _ а, = 1,1545 -1,1396 = 0,0149 < 0,02 - 2е.
Поэтому, согласно критерию D8), вычисления
закапчиваем и середину отрезка E6)
х = (д4 + Ь4)/2 = A,1396 + 1,1545)/2 » 1,147
принимаем за приближенное значение искомого корня х.
При этом
1,137 <*' < 1,157.
Основные промежуточные результаты описанных
вычислений сведены в табл. 3.
Таблица 3
к
0
1
2
3
4
1
1
0
1
1
,1396
,1396
1
1
1
2
2
,3006
,3006
,1545
1
1
1
cfr
1
,3006
,1396
,1545
/<cfc)
0,2141
—0,2591
0,0091
—0,0142
Отметим, что решение уравнения E5) с точностью 8 =
= 0,01 комбинированным методом потребовало
проведения четырех итераций. Решение этой же задачи методом
половинного деления потребует, согласно критерию E1),
уже семи итераций.
Сделаем заключительное замечание. Если отрезок [a, b]
содержит несколько корней функции /, то при условии
D4) любой краевой метод с критерием останова D8)
приводит к одному из корней функции /, принадлежащих
отрезку [а, Ь], причем, как правило, найденный корень
будет простым. Краевой метод может привести к
кратному корню, если случайно очередная точка ск окажется
таким корнем (сработает п. 3 процедуры А).
119

Упражнение 8. Приведите пример задачи, для которой
первые шаги метода хорд приводят к худшему приближению к
корню по сравнению с приближением, которое дает такое же число
шагов метода половинного деления.
Упражнение 9. В методе хорд точка с^ является корнем
линейной функции, значения которой совпадают со значениями
функции / на концах отрезка [а^, Ь^]. Постройте и исследуйте
алгоритм «метода квадратных хорд», у которого точка с^ ^ [ак, &kJ
является корнем квадратной параболы, совпадающей со
значениями функции / на концах отрезка [я^-х, bfc-i] и в точке c/c-i s [я&-1,

СПИСОК ЛИТЕРАТУРЫ
1. Абрамов Л. М., Капустин В.Ф. Математическое
программирование.— Л.: Изд-во ЛГУ, 1981. 328 с.
2. Б а х в а л о в Н. С. Численные методы.— М.: Наука, 1975.
631 с.
3. Б е р е з и н И. С, Ж и д к о в Н. П. Методы вычислений.
Т. 11.— М.: Физматгиз, 1962,—639 с.
4. Васильев Ф. П. Численные методы решения
экстремальных задач.— М.: Наука, 1980.— 518 с.
5. Г о л ь ш т е й н Е. Г., Юдин Д. Б. Задачи линейного
программирования транспортного типа.— М.: Наука, 1969.—
382 с.
6. Данциг Дж. Линейное программирование, его применения
и обобщения.— М.: Прогресс, 1966.— 600 с.
7. Д е м и д о в и ч Б. П., М а р о и И. А. Основы
вычислительной математики.— М.: Наука, 1970.— 664 с.
8. Калихман И. Л. Сборник задач по математическому
программированию.— М.: Высшая школа, 1975.— 270 с.
9. К а н т о р о в и ч Л. В., Г о р с т к о А. Б. Оптимальные
решения в экономике.— М.: Наука, 1972.— 231 с.
10. Л я ш е н к о И. Н., К а р а г о д о в а Е. А.,
Черникова Н. В., Щ о р Н. 3. Линейное и нелинейное
программирование.— Киев: Вища школа, 1975.— 371 с.
11. Моисеев Н. Н., И в а и и л о в 10. П.,
Столярова Е. М. Методы оптимизации.— М.: Наука, 1978.— 351 с.
12. П у л ь к и н СП. Теория и практика вычислений.— М.:
Просвещение, 1967.— 183 с.
13. СтронгинР. Г. Численные методы в много экстремальных
задачах.— М.: Наука, 1978,— 240 с.
14. Юдин Д. Б., Гольштейн Е. Г. Линейное
программирование.— М.: Наука, 1969.— 424 с.
15. Ганшин Г. С. Расширение области сходимости метода
Ньютона // ЖВМ и МФ.— 1971, № 5.— С. 1294—1296.
16. Г а н ш и н Г. С. Вычисление действительных корней
полинома // ЖВМ и МФ.— 1971, № 6.— С. 1581—1584.
17. ГаншинГ.С. К теории итерационных процессов //
Вычислительная и прикладная математика.— Киев: Изд-во Киев,
унта.— 1973, № 19.— С. 143—147.
18. Ганшин Г. С. Вычисление наибольшего значения
функций // ЖВМ и МФ.— 1976, № 1.— С. 30—39.
19. Г а н ш и н Г. С. Простейший последовательный алгоритм
поиска наибольшего значения дважды дифференцируемой
функции // Мат. заметки.— 1976, т. 19, вып. бГ— С, 871—872.
т

20. ГаншинГ. С. Оптимальные пассивные алгоритмы
вычисления наибольшего значения функции на отрезке // ЖВМ и МФ,-
1977, № 3.— С. 562-571.
21. Г а н ш и н Г. С. Оптимизация алгоритмов на классах сеток //
ЖВМ и МФ.— 1979, № 4.— С. 811—821.
22. Васильеве. Б., ГаншинГ. С. Последовательный
алгоритм поиска наибольшего значения дважды
дифференцируемой функции // Мат. заметки.— 1982, т. 31, вып. 4.— С. 613—
618.
23. ГаншинГ. С. Оценивание функции, покоординатно
удовлетворяющей условию Липшица // Изв. вузов. Математика.
1982, № 12.- С. 84.
24. Ганшин Г. С. Вычисление наибольшего значения функций
нескольких переменных // Кибернетика.— 1983, № 2.—
С. 61—63.
25. Евтушенко Ю. Г. Численный метод поиска глобального
экстремума функции // ЖВМ и МФ.— 1971, № 6.— С. 1390—
1403.
26. П и я в с к и й С. А. Один алгоритм отыскания абсолютного
экстремума функции // ЖВМ и МФ.— 1972, № 4.— С. 888—
896.
27. Ганшин Г. С. Вычисление наибольшего значения дважды
дифференцируемой функции с апостериорной оценкой
погрешности // Мат. заметки.— 1984, т. 35, вып. 2.— С. 243—249.

ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
Алгоритм просеивания 86
Вектор квазиединичный 48
— перевозок 36
— поставок 36
Векторы сопряженные 48
Вредное преобразование ТЗ 52
Вырождение задачи 26
Границы корней уравнения 95,
98
Граничная константа 60
Липшица 62
Добротность столбца ТЗ 43
— строки ТЗ 43
Допустимый план 7
ТЗ 38
Задача линейного
программирования (ЗЛП) 13
каноническая 14
правильная 18
стандартная
(естественная) 14
— определения границ корней
95, 98
— отделения корня 95
Квазиединичный вектор 48
Комбинированный краевой метод
117
Константа Липшица 62
Корень уравнения 94
— функции 96
изолированный 102
кратный 96
простой 96
Краевые методы 115
Мажоранта 69
Матрица зануленного типа 42
Матрица перевозок 35
— стоимости 35
— столбцевая 45
— строчная 45
Метод половинного деления 46
— комбинированный краевой
117
— хорд 46
Методы краевые 115
Минимизирующее
преобразование 47
Миноранта 69, 109
Множество допустимых планов
13, 14
Неопределенные оценки 63
Опорный план 18
Оптимальный план 14
ТЗ 38, 39
Отрезок локализации корня 97
Подозрительные отрезки 97
Порядок граничной константы 60
Потенциал ТЗ 47
Правильный столбец
канонической ЗЛП 18
Преобразование матриц
допустимое 45
эквивалентное 45
— простое 48
— ТЗ полезное 48
Простой корень уравнения 96
Равносильное преобразование
уравнения 95
на заданном отрезке 95
Равносильные уравнения 95
Разность потенциалов двух ТЗ
47
Решение ЗЛП 14
123

Скалярное произведение векто- Условие Липшица 62
ров 13, 14, 37
матриц 37 Функциональный многочлен 69
Сопряженные квазиединичные
векторы 48 Целевая функция 7
Стоимость преобразования ТЗ 48 ЗЛП 13, 14
Схема Горнера 66 ТЗ 38
Транспортная задача (ТЗ) 35, 36 Эквивалентные матрицы стоимос-
закрытого типа 37 ти 44
Тривиальный опорный план 18 — ТЗ 46
124

СПИСОК ОБОЗНАЧЕНИЙ И АББРЕВИАТУР
ЗЛП — задача линейного программирования
ТЗ — транспортная задача
НЗФ — наибольшее значение функции
D = 0 — множество D пусто, т. е. не содержит ни одного
элемента
{a*, ar2f . . ., xn}* = max {xb x29 . . ., #n}
{rci, a:2, . . ., zn}° = min {a*, a:2, . . ., :rn}
/' W» /" W, . . ., /'^ (x) — производные функции / (x)
L1 = max{\f(x)\}
X\ — константа Липшица в неравенстве
I /(*)-/ fo) I < #i I * - У I
W = {wi, и2» • • •» Mn+i^ — сетка на отрезке [а, Ь], при этом
а = mi < и2 < . . . < ип < мя+1 = Ъ
кг = щЛ1— иг — шаг сетки W
х — (хи х27 . ш ., хп) — вектор размерности п
~ап а12 ... а1п
а21 а22 ... а2п
А = | | — матрица, имеющая т строк и
п столбцов
А = {aij} — матрица с элементами ац
А\ = (fliii ai3» • - • 1 ain) — строка матрицы Л
А] = («I?» a2j» • • •» flwj) — столбец матрицы А
Rn — множество векторов размерности п
ftmn — множество матриц, имеющих т строк и п столбцов
0 = (О, 0, . . ., 0) — нулевой вектор
125

Если с = (си с2, . . ., сп) и х = (хи х2, . . ., хп), То
<с, #> — cia:i + ^2^2 + • • • + спхп — скалярное произведение
векторов с и х
с < х — ci^ Xi для i = 1, 2, . . ., п
с < х — с| < я* для i = 1, 2, . . ., я
Если
Г°" ¦ • • ei» 1 Г6и ... 61П -I
4= - Н '
то
т п
<А,В>= 3 S aijbif
L {Л, а, с} = —JL — обозначение канонической ЗЛП
Г {С, а, 6} = — обозначение ТЗ
-D0 {С, а, Ь} — множество оптимальных планов ТЗ
D {а, Ь) — множество допустимых планов ТЗ
Ф {Т} = min {<Х, С)} — потенциал ТЗ
С]
Р = Р {[г, Х\ = Р \^> — эквивалентное преобразование
матриц. Здесь [I = (fix, . . ., ji^), Я = (Хи . . ., Хп) — векторы,
порождающие преобразование Р
Запись С— PC для матриц С ~ (с^) и С — (ci;), имеющих
m строк и п столбцов, означает выполнение равенств
i = 1, . . ., ттг, j = 1, . . ., тг
Запись С — PC означает выполнение равенств
с' = Cij — |lj + A,j,
i = 1, . . ., ттг, / = 1, . . ., п
П = П {^i, X} = П -L г — простое преобразование матриц (т. eL
эквивалентное преобразование, порождаемое квазиединичными
векторами \х и X)
\? — квазиединичный вектор, сопряженный к вектору \i (\i +
+ р = е= A,1,- • .,D)
Вш — множество квазиединичных векторов размерности m
А (Р) = <Ь, Я,> — <а, |л> — стоимость эквивалентного
преобразования Р

Герман Сергеевич Ганшин
МЕТОДЫ ОПТИМИЗАЦИИ И РЕШЕНИЕ УРАВНЕНИЙ
Редактор Е. Е. Тыртышнипов
Художественный редактор Т. Н. Иольченпо
Технически"! редактор Л. В. Лихачева
Корректоры Е. Ю. Рычагова, Т. С. Вайсберг
ИБ № 32306
Сдано в набор 09.06.86. Подписано к печати 02.02.87
Т-05236. Формат 84хЮ8»/з2.
Бумага кн. жури. Гарнитура обыкновенная. Печать высокая.
Усл. печ. л. 6,72. Усл. кр.-отт. 7,0i. Уч.-изд. л. 6,39.
Тираж 17 000 экз. Заказ № 2753. Цена 40 коп.
Ордена Трудового Красного Знамени
издательство «Наука»
Главная редакция
физико-математической литературы
117071 Москва В-71, Ленинский проспект, 15
2-я типография издательства «Наука»
121099 Москва Г-99, Шубинский пер., 6.

ИЗДАТЕЛЬСТВО «НАУКА»
ГЛАВНАЯ РЕДАКЦИЯ
ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ
117071 МоСква В-71, Ленинский проспект, 15
ГОТОВИТСЯ К ПЕЧАТИ
ВоеводинВ. В., ТыртышниковЕ. Е.
Вычислительные процессы с теплицевыми
матрицами.— М.: Наука. Гл. ред. физ.-мат. лит., 1987.
Во многих актуальных задачах акустики,
электродинамики, оптики, обработки изображений,
распознавания образов и других областях науки и техники часто
приходится проводить вычисления с теплицевыми и
близкими к ним матрицами. Потребности практики
требуют для решения этих задач разработки
высокоэффективных численных методов, а также создания
специализированных параллельных вычислительных
систем, обеспечивающих возможность работы в режиме
реального времени. Обо всех этих вопросах идет речь
в настоящей книге.
Для студентов старших курсов, аспирантов и
научных работников в области прикладной математики
и информатики.
(Темплан 1987 г., №10.)
Предварительные заказы на данную книгу
принимаются без ограничения всеми магазинами
Книготорга i n Академкниги, распространяющими физико-мате-
у[атическую литературу.