NONLINEAR AND DYNAMIC PROGRAMMING BV 0. HADLEY University of Chicago and Universidad de Los Andes Bogota, Colombia ADDISON-WESLEY PUBLISHING COMPANY, INC. READING, MASSACHUSETTS • PALO ALTO • LONDON 1964 Дж. Хедли НЕЛИНЕЙНОЕ и ДИНАМИЧЕСКОЕ П РО ГРАММ ИРОВАНИЕ Перевод с английского Ю. И. ВОЛКОВА. А. Б. ГОРСТКО. А. А. КАПЛАНА, Э. О. РАПОПОРТА Под редакцией, Г. П. АКИЛОВА ИЗДАТЕЛЬСТВО .МИР" МОСКВА 1967 УЛК 519.9 Монография содержит подробное исследование теоретических и вычислительных аспектов нелинейного и динамического про- граммирования. Автор систематически рассматривает вопросы практической реализуемости предлагаемых вычислительных мето- дов. В книге имеется большое количество примеров. Предпола- гается, что читатель знаком с математическим анализом, линей- ной алгеброй и линейным программированием, однако для удоб- ства в книгу включена глава, содержащая необходимый минимум сведений. Книга рассчитана на научных работников, инженеров, эконо- мистов и лиц других специальностей, интересующихся матема- тическими методами планирования, а также на математиков, занимающихся приложениями к экономике. Она доступна сту- дентам и аспирантам соответствующих специальностей. Редакция литературы по математическим наукам Инд. 2-2-3 ОТ РЕДАКТОРА ПЕРЕВОДА Предлагаемая вниманию читателя книга Дж. Хедли «Нели- нейное и динамическое программирование» имеет целью позна- комить неискушенного в математике читателя с задачами, ре- шение которых сводится к отысканию наибольшего или наи- меньшего значения некоторой функции, зависящей, как правило, от большого числа переменных. Такие задачи возникают в самых разнообразных областях человеческой деятельности и в первую очередь — это и обусловило повышенный инте- рес к ним—в практике планирования и организации производ- ства. Имея в виду указанный выше круг читателей, автор не стре- мится углубляться в дебри теоретических исследований. Его интересует, во-первых, математическое описание различных си- туаций, типичных для оптимального планирования, и, во-вторых, численное решение возникающих при этом математических за- дач. Надо сказать, что эти стороны вопроса совершенно недо- статочно освещены в советской литературе. Поэтому столь по- дробное их изложение, которое мы находим в книге Дж. Хедли, следует расценивать как явление весьма положительное. Все это дает основания надеяться, что книга окажется полезной для обширного круга специалистов, так или иначе свя- занных с оптимальным планированием: от сотрудников научных учреждений до практических работников предприятий и плано- вых органов, занимающихся организацией и планированием производства. Книга не обращена непосредственно к математикам, но те из них, кто работает по реализации на ЭВМ задач математиче- ской экономики или им подобных, также прочтут ее с пользой для себя. Or редактора перевода При переводе мы сочли нужным сделать некоторые, впрочем совсем небольшие, сокращения. В ряде случаев оказались не- обходимыми и другие отступления от текста, главным образом уточнения отдельных формулировок. Указанные изменения в оригинале ввиду их незначительности, как правило, не оговари- ваются. Список литературы дополнен важнейшими советскими изда- ниями, имеющими прямое отношение к затронутым в книге во- просам. Главы 1, 10, 11 переведены А. Б. Горстко, главы 2, 8— Ю. И. Волковым, главы 3, 4, 6. 7 — А. А. Капланом, главы 5, 9—Э. О. Рапопортом. Г. П. Акилов ПРЕДИСЛОВИЕ Эта книга задумана как продолжение книги автора «Линей- ное программирование» и посвящена изучению теоретических и вычислительных аспектов нелинейного программирования. Первая глава посвящена обсуждению тех трудностей, ко- торые возникают при переходе от линейных задач к нелинейным. Во второй главе делается попытка дать необходимые для дальнейшего чтения сведения по математике, а также вводятся принятые обозначения. Благодаря включению этой главы на- стоящую книгу можно читать независимо от книг автора «Ли- нейное программирование» и «Линейная алгебра». Глава 3 содержит описание классических методов оптимиза- ции, основанных на использовании дифференциального исчисле- ния. Особенно подробно обсуждается метод множителей Ла- гранжа. Здесь же определяются основные свойства выпуклых и вогнутых функций, которые используются в дальнейшем. В этой главе не делается попытки изучить вариационное исчисление, так как для этого понадобилось бы слишком много места. О нем лишь коротко упоминается в главах, посвященных динамиче- скому программированию. В гл. 4 изучаются приближенные методы для отыскания ло- кальных или глобальных экстремумов в задачах нелинейного программирования. Пятая глава посвящена задачам стохастического программи- рования, а шестая—теории Куна—Таккера. Задачи квадратичного и целочисленного программирования обсуждаются соответственно в седьмой и восьмой главах. Глава 9 посвящена градиентным методам решения нелиней- ных задач, а две последние главы—динамическому программи- рованию. Проблемы нелинейного программирования гораздо шире и разнообразнее, чем проблемы линейного программирования. От- части это и послужило причиной того, что отдельные главы иногда содержат описания никак не связанных между собой методов решения специальных типов задач. Другая причина состоит в том, что в настоящее время не существует теории, Предисловие объединяющей все относящееся к нелинейному программирова- нию, да и вычислительные алгоритмы разработаны лишь для очень специальных классов задач. Схемы этих алгоритмов весьма существенно зависят от особенностей решаемых задач. Для решения рассматриваемых в книге задач было предло- жено множество вычислительных методов. Так как не предста- влялось возможным изложить все методы, автор был вынужден отобрать лишь наиболее интересные. Конечно, в ряде случаев этот выбор был довольно субъективным, так как не имелось данных, позволяющих сравнить эффективность различных вы- числительных схем. Некоторые интересные методы могли ока- заться неупомянутыми просто потому, что автор не знал об их существовании. Нелинейное программирование в настоящее время бурно развивается. При выборе материала для этой книги автор ста- рался включать то, что более или менее уже выдержало испы- тание временем. Однако вполне возможно, что в недалеком бу- дущем многие из обсуждаемых алгоритмов будут вытеснены но- выми, которые окажутся лучше существующих. Математическая подготовка, необходимая для изучения этой книги, неодинакова для разных глав. В большинстве случаев не- обходимы первоначальные сведения из линейной алгебры и ли- нейного программирования (например, в пределах nepiBbix вось- ми-девяти глав книги автора «Линейное программирование»). Большая часть материала, относящегося к динамическому про- граммированию, может быть изучена и без этих сведений. При чтении третьей и шестой глав необходимо знание, хотя и не слишком основательное, дифференциального исчисления. Как уже говорилось, в гл. 2 сделана попытка собрать все не- обходимые для дальнейшего изложения сведения из матема- тики. Исключение составила лишь элементарная теория вероят- ностей, даже не упоминающаяся в этой главе, но используемая далее в гл. 3, 5,10 и 11. Автор очень обязая Д. Е. Моррису, который подобрал вели- колепные эпиграфы к каждой главе. Рецензенты Р. Дорфман и С. Дрейфус внесли много полез- ных предложений, за которые автор им очень благодарен. По- мощь при перепечатывании рукописи и издании книги была любезно оказана аспирантурой Школы бизнеса Чикагского уни- верситета. Дж. Кед ли Богота, Колумбия июнь 1964 г. ГЛАВА 1 ВВЕДЕНИЕ Каждое дерзание — Это новый риск, новый шаг в темноту непознанного Со старым и все более устаревающим оснащением. Т. С. Элиот. Восточный Колос 1.1. Задачи математического программирования. Всякая задача, в которой отыскивается максимум или минимум числовой функ- ции (или функционала), может быть отнесена к задачам опти- мизации. Эти задачи уже давно интересуют математиков, физиков и инженеров. Возможность использования методов дифференциального и вариационного исчислений для решения некоторых типов таких задач, возникающих в геометрии и фи- зике, была известна с середины XVIII в. В последние пятнадцать лет значительно возрос интерес к новому классу задач оптимизации, которые, как правило, не поддаются решению классическими методами. Это так называе- мые задачи математического программирования. Задачи математического программирования в отличие от классических задач, возникающих в геометрии и физике, часто относятся к вопросам математической экономики. Как правило, они возникают в тех случаях, когда заданные дефицитные ре- сурсы—людей, машины и сырье—следует распределить таким образом, чтобы произвести необходимое количество продуктов и в то же время максимизировать или минимизировать некото- рую целевую функцию (прибыль, затраты). Большой интерес к этим задачам объясняется именно тем, что они встречаются не только в теоретической экономике, но и в практике производ- ства. торговли, управления и в военном деле. Общг-я задача математического программирования может быть сформулирована следующим образом: требуется найти значения п переменных х\, Xs, ..., х.п, которые удовлетворяют m уравнениям или неравенствам g-,(Xi, х>, ..., х„) {<,==,>} bi, i=\, 2, ..., m, (1.1) 26 /'л. 1. Введение fTEPATVPA') Э р р о у К. Дж., Г у р в и ц Л., У д з а в а X., Исследования по линейному и нелинейному программированию, ИЛ, М., 1962. Barankin E. W., Dorfman R., Towards Quadratic Programming, Office of Naval Research Logistics Projects at Columbia University and University of California, Berkeley, 1955. Be ale E. M. L., On Minimizing a Convex .Function Subject to Linear Inequalities, J. Roy. Statist. Soc. (B), 17 (1955), 173—184. Беллман Р., Динамическое программирование, ИЛ, М., 1960. Беллман Р., Дрейфус С., Прикладные задачи динамического про- граммирования, изд-во «Наука», М., 1964. С h a r n e s A., L e m k e С., Minimization of Nonlinear Separable Convex Functionals, Nav. Res. Logist. Quart., 1 (1954), 301—312. D a n t z i g G. В., Recent Advances in Linear Programming, Manag. Sci., 2 (1956), 131—144. D a n t z i g G. В., F u 1 k e г s о n D. R., J о h n s о n S., Solution of a Large- Seals Traveling-Salesman Problem, /. Operat. Res. Soc. Amer., 2 (1954), 393—410. Д e н н и с Дж. Б., Математическое программирование и электрические цепи, ИЛ, М., 1961. Frank M., Wolfe P., An Algorithm for Quadratic Programming, Nav. Res. Logist. Quart., 3 (1956), 95—110. G о m о г у R., Essentials of an Algorithm for Integer Solutions to Linear Programs, Bull. Amer. Math. Soc., 64 (1958), 275—278. G о m о г у R., An Algorithm for the Mixed Integer Problem, RM-2597, RAND Corp., 1960. H a d 1 e у G., Linear Programming, Reading, Addison-Wesley, 1962. H i 1 d r e t h C., A Quadratic Programming Procedure, Nav. Res. Logist. Quart., 14 (1957), 79—85. Houthakker H., The Capacity Method of Quadratic Programming, Econometrica, 28 (1960), 62—87. Koopmans T. (ed.), Activity Analysis of Production and Allocation, New York, Wiley, 1951. Kuhn H. W., Tucker A. W., Nonlinear Programming, Proc. Second Berkeley Symp, on Math. Statistics and Probability, 1951, 481—492. Lemke С.,. The Constrained Gradient Method of Linear Programming, /. Soc. Indust. and Appl. Math., 9 (1961), 1—17. Markowitz H., The Optimization of a Quadratic Function Subject to Linear Constraints, Nav. Res. Logist. Quart., 3 (1956), 111—133. Markowitz H., M a n n e A. S., On the Solution to Discrete Programm- ing Problems, Econometrica, 25 (1957), 84—110. Miller С. E., The Simplex Method for Local Separable Programming, in Graves R., Wolfe P. (ed.), Recent Advances in Mathematical Pro- J ramming, New York, McGraw-Hill, 1963. о s e n J., The Gradient Projection Method for Nonlinear Programming. Part I. Linear Constraints, /. Soc. Indust. and Appl. Math., 9 (1960), 181—217. Wolfe P., The Simplex Method for Quadratic Programming, Econometri- ca, 27 (1959), 382—398. Z о u t e n d i j k G., Maximizing a Function in a Convex Region, J. Roy. Statist. Soc. (B), 21 (1959), 338—355. !. Г о л ь шт e и н E. Г., Юдин Д. Б., Новые направления в линейном про- граммировании, изд-во «Советское радио», М., 1966. ') Звездочкой отмечены названия, включенные переводчиками и редак- тором перевода. — Прим. ред. Упражнения 27 Зойтендейк Г., Методы возможных направлений, ИЛ, М„ 1963. Канторович Л. В., Математические методы организации и планиро- вания производства. Л., 1939. К а н т о р о в и ч Л В., Об одном эффективном методе решения некото- рых классов экстремальных проблем, ДАН СССР, 28 (1940), № 3, 212— 215. Юдин Д. Б., Г о л ь ш т e и н E. Г., Задачи и методы линейного про- граммирования, изл-во «Советское радио», М., 1961. Graves R., Wolfe P. (ed.), Recent Advances in Mathematical Pro- gramming, New York, McGraw-Hill, 1963. Упражнения Решить следующие задачи нелинейного программирования и проиллю- стрировать их с помощью геометрических построений: 1.1. 0,5л: i +^2<4. Зл-i +^2< 15, X, +Л-2>1. л-i, х^О; найти min г = 4 (^-i — б)2 + 6 (^ — 2)2. 1.2. 0,5;к, +^2<4. Зх, +^2< 15, ^1+^"2>1. Д-1, JV2>°; найти тах г = 3 (xi — 1,5)2 + 6 (д-г — 1,5)2. 1.3. ^,—^>0, Xi + Хз < 4, ^•i<3; найти тах и min г = 2^i -4- Зх^ + Ах\ + 1х^ + х^. 1.4. (х,-2у+(х,-\У^9. Xi, Д-2>0; найти тах г == 3^i -)- Ix^. 1.5. ^1-»'2> 1, ^+д-|<9; найти min г == 7 (д:1 — б)2 + 3 (д-2 — 4)2. ИМЕННОЙ УКАЗАТЕЛЬ') Балинский (Balinski M. L.) 153 Баранкин (Barankin E. W.) 23 Бауман (Bowman E. H.) 299 Беллман (Bellman R.) 15, 24, 359, 413 Бил (Beale E. M. L.) 23, 177, 290 Бомол (Baumol W.) 153 Вайнгартнер (Weingartner H. M.) 275 Вольф (Wolfe P.) 23, 24, 222, 229, 230, 241, 251 Гилдрет (Hildreth С.) 23, 242, 244 Гильберт (Hilbert D.) 88 Гирш (Hirsh W. H.) 153 Голыптейн Е. Г. 11, 29 Гомори (Gomory R.) 24, 255, 276, 277, 287, 298 Гурвиц (Hurwicz L.) 23, 353, 354 Данциг (Dantzig G. В.) 10, 23, 24, 140, 153, 174, 177, 178, 275, 277, 298 Джонсон (Johnson S.) 24, 275 Деннис (Dennis J. В.) 24 Дойг (Doig A.) 290 Дорфман (Dorfman R.) 23 Дрейфус (Dreyfus S.) 24, 219, 414 Зойтендейк (Zoutendijk G.) 24, 316, 318, 320, 337 Канторович Л. В. 437 Кун (Kuhn H. W.) 23, 195, 200, 204 Курант (Courant R.) 88 Лемке (Lemke С.) 23, 140, 318 Лэнд (Land A. H.) 281, 290 ') При составлении указателя т в конце каждой главы. — Прим. ред. Манне (Маппе А.) 24, 277, 489 Марковиц (Markowitz H.) 23, 24 226, 277 Миллер (Miller С. Е.) 23, 140 Модильяни (Modigliani F.) 467 Моисеев H. H. 460 Мут (Muth J.) 467 Розен (Rosen J. В.) 24, 322, 338 Симон (Simon H. A.) 467, 469 Таккер (Tucker A. W.) 23, 195, 200, 204 Тейл (Theil H.) 469 Уайтин (Whitin T. М.) 190 Удзава (Uzawa H.) 23 Фалкерсон (Fulkerson D.) 24, 275 Фергюсон (Ferguson A. R.) 178 Франк (Frank M.) 23, 241, 251 Фример (Freimer M.) 219 Хартли (Hartley H. 0.) 148 Хаутеккер (Houthakker H.) 23, 244 Хедли (Hadley G.) 190 Хилдрет (Hildreth С.) 23 Ховард (Howard R.) 476 Хольт (Holt С.) 467 Чарнс (Charnes A.) 23, 140, 229, 295 Черноусько Ф. Л. 460 Эпен (d'Epenoux F.) 489 Эрроу (Arrow К. J.) 23, 353, 354 Юдин Д. Б. 11, 29 учитывалась литература, приведенная ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Базис 35 ортонормированный 53 Вариационное исчисление 422, 456, 460 Вектор (строка, столбец) 32 — вводимый в базис 42 — выпуклая комбинация 50 — единичный 33 — исключаемый из базиса 42 — искусственный 43 — лексикографически положитель- ный 282 — линейная зависимость 35 — нормальный к гиперплоскости 50 — нормированный 53 — ортогональность 34 — порождение пространства 35 — скалярное произведение 34 — сложение 33 — умножение на скаляр 33 — характеристический (собственный) 53 Вероятность перехода 472 Вольфа способ в квадратичном про- граммировании 230 Выпуклая комбинация векторов 50 Гессиан 58 Гилдрета метод в квадратичном про- граммировании 242 Гиперплоскость 50 — касательная 60 — опорная 52 Гиперповерхность 56 — вогнутая 97 — выпуклая 97 Гиперсфера 50 Гомори алгоритм для полностью це- лочисленных задач 276 Гомори алгоритм для частично цело- численных задач 287 Градиент 57 Градиентные методы 302 — — в задачах с линейными огра- ничениями 303 программирова- программиро- - — — линейном нии 333 - — — нелинейном вании 337, 340 - — метод Эрроу—Гурвица 353 - — проективный метод 332 Двойственность в задаче максимиза- ции 87 — — программировании квадратич- ном 246 — — — линейном 48 Детерминированные задачи последо- вательного принятия решений 387 — — теории создания запасов 391 Динамическое программирование 15, 359 Евклидово пространство 34 Задача детерминированная см. Де- терминированные задачи — квадратичного программирования 13, 220 — математического программирова- ния линейная 10, 11 — — — нелинейная 11, 12 — оптимизации классическая 13 — приближенная см. Приближенная задача — стохастическая см. . Стохастичес- кие задачи — с условиями очередности 266 — с фиксированными затратами 151 498 Предметный указатель Задача с фиксированными затратами сведение к целочисленной 255 — целочисленная 14, 254 Задача о бродячем торговце 271 — — выборе направления наиболь- шего изменения функции 93 — — загрузке корабля 375, 434 — — замене оборудования 409, 454 — — запасах 184, 391, 414, 430, 495 — — использовании рабочей силы 387 — — капитальных вложениях 273, 297 — — линии сборки 298, 299 — — надежности 428 — — нефтяной компании 190 — — планировании выпуска авто- мобилей 476 — — — — конденсаторов 432 — — — производства 194, 2J8, 430, 460 — — производителе продуктов 179, 261, 434 — — производстве деталей 71, 180, 301 — — — насосов 432 — — — продукции с переналадкой оборудования 156 — — подводной лодке 173, 372 — — раскрашивании карты 298 — — распределении допусков 376 — — — поставок 375 — — — самолетов по маршрутам 178 — — — средств на производство и рекламу 423 — — реализации проектов и кален- дарном планировании 266 — — снабжении морской базы 428 — — торговце одеждой 88, 172 — — — хлебом 153 — расписания 299, 300 — транспортная t69, 174, 434, 447, 452 Линейные правила принятия реше- ний 467 Линия уровня 55 Максимум абсолютный (глобальный) 16, 65 — относительный (локальный) 16 — сильный 66 — слабый 66 — условный 73 Марковские процессы 472 Матрица, определения и основные свойства 29—31 — конгруэнтная 53 — неособенная 37 — обратная 37 — ортогональная 53 — подобная 53 — расширенная система уравнений 38 — характеристический вектор, поли- ном, число 53 Минимум 66 — условный 73 Многогранник выпуклый 52 Множество точечное, определение и основные свойства 49—52 Множители Лагранжа 76, 79 — — в линейном программировании 94 — — интерпретация 85 — — использование для уменьше- ния размерности 449 Неравенство Шварца (Буняковского) 34 Нормаль к поверхности 60 Ньютона метод отыскания стацио- нарной точки 69 Квадратичная форма 54 Квадратичные затраты 462 Конечные альтернативы в линейном программировании 260 Куна — Таккера теорема 203 — условия регулярности ограниче- ний 205, 206 Кусочно-линейная аппроксимация 117 Линейная зависимость 35 Линейное преобразование 39 Образ 39 Ограничения 10 — линейные 11 — сепарабельные 13 Октант неотрицательный 51 Ортогональное дополнение подпро- странства 36 Отображение 39 Отрезок 50 Параметры состояния 371 Переменная (базисная, небазисная) 39 Предметный указатель 499 Переменная вспомогательная 40 — искусственная 43 — истинная 43 — управляющая 170, 371 Поверхность уровня 60 Подпространство 36 Политика 371 Полупространство (замкнутое, крытое) 50 Порождение пространства вектора- ми 35 Приближенная задача в б-форме 129 — — в ^-форме 117 Принцип декомпозиции 140 — оптимальности Р. Беллмана 372 Проблема размерности 436, 439, 441, 446, 490 Производная функции 56 — частная 56, 57 — в направлении г 58 Прямая 50 Ребро множества 52 Решение базисное 39 — — вырожденное 39 — в прямом направлении 387 — в обратном направлении 387 — допустимое 16, 41 — тривиальное 39 ^/•-политика 406 Седловая точка 88, 195 — — глобальная 196 — — — достаточные условия 199 — — — необходимые условия 198 Сечение 275 — Гомори 277, 290 — Данцига 277 — Марковица и Манне 277 Симплекс-метод 40—44 — таблица 44 Симплекс-метод двойственный 49 Симплекс-метод модифицированный 44—47 — — — таблица 45 Система координат 33 — — ортогональная 34 Средняя стоимость детерминирован- ная 191 — — из-за неопределенности 191 Стационарная точка 69 — — при наличии ограничений 308 Стохастические задачи математиче- ского программирования 171 Стохастические задачи многошаговые 184 — — одношаговые со случайностя- ми в спросе 172 — — — — — в технологических ко- эффициентах 180 — — последовательного принятия решений 414, 460, 469 — — теории создания запасов 414 Стратегия 478 — смешанная 478 — чистая 479 Теорема о неявных функциях 62 — Тейлора 59 — Куна—Таккера 203 Точка множества внутренняя 50 — — граничная 50 — — крайняя 51 Точка перегиба функции 68 Точки множества смежные 52 Транспортная задача 159, 174, 434, 447, 452 Управление 371 Управляющая переменная 170, 371 Условия регулярности ограничений Куна—Таккера 205, 206 Фактор производства 266 Фаркаша лемма 209 Фиксированные затраты 151 Франк и Вольфа метод в квадратич- ном программировании 241 Функциональное уравнение 405 Функция 55 — вогнутая 97 — — максимум и минимум 108 — выпуклая 97 — — максимум и минимум 105, 106 — Лагранжа 76, 79 — — интерпретация 86 — линейная 56 — непрерывная 56 — сложная 58 — состояния 374 — строго вогнутая 98 — — выпуклая 98 — целевая, см. Целевая функция Характеристический вектор 53 — полином 53 — уравнение 53 — число 52 600 Предметный указатель Хартли метод максимизации 148 Чарнса способ в квадратичном про- Хаутеккера метод в квадратичном граммировании 229 программировании 244 , Экстремум функции 74 Целевая функция 10 — — необходимые условия 74 — — линейная 11 Эрроу—Гурвнца градиентный метод — — нелинейная 12 353 — — параметрическая 230 — — сепарабельная 12 Целочисленные задачи линейного Якобиан 62 программирования 14, 254 Цикл 407 ОГЛАВЛЕНИЕ : От редактора перевода ................... 5 Предисловие ......,,.,,..........,. у Глава 1. Введение .......................... 9 I 1.1. Задачи математического программирования ........ 9 1.2. Типы задач .................. И | 1.3. Вычислительные методы ................. 15 | 1.4. Трудности, порождаемые нелинейноетями ......... 16 1.5. Краткий исторический обзор ............... 23 1.6. Обзор дальнейшего содержания .............. 25 Литература ...................... 26 Упражнения ...................... 27 Глава 2. Необходимый математический аппарат ........... 29 2. 1. Матрицы и векторы ................ 29 2. 2. Системы линейных уравнений .............. 38 2. 3. Линейное программирование ............... 40 2. 4. Модифицированный симплекс-метод ........... 44 2. 5. Двойственность ..................... 48 2. 6. Выпуклые множества ............... 49 2. 7. Характеристические числа и квадратичные формы .... 52 2. 8. Функция п переменных .................. 55 2. 9. Частные производные .... .............. 56 2.10. Теорема Тейлора ..................... 59 2.11. Теорема о неявных функциях .............. 60 Литература ...................... 63 Упражнения ...................... 63 Глава 3. Классические методы оптимизации и свойства выпуклых функций ......................... 65 3. 1. Введение ....................... 65 3. 2. Максимум и минимум при отсутствии ограничений .... 65 ИМЕННОЙ УКАЗАТЕЛЬ') Балинский (Balinski M. L.) 153 Баранкин (Barankin E. W.) 23 Бауман (Bowman E. H.) 299 Беллман (Bellman R.) 15, 24, 359, 413 Бил (Beale E. M. L.) 23, 177, 290 Бомол (Baumol W.) 153 Вайнгартнер (Weingartner H. M.) 275 Вольф (Wolfe P.) 23, 24, 222, 229, 230, 241, 251 Гилдрет (Hildreth С.) 23, 242, 244 Гильберт (Hilbert D.) 88 Гирш (Hirsh W. H.) 153 Голыптейн Е. Г. 11, 29 Гомори (Gomory R.) 24, 255, 276, 277, 287, 298 Гурвиц (Hurwicz L.) 23, 353, 354 Данциг (Dantzig G. В.) 10, 23, 24, 140, 153, 174, 177, 178, 275, 277, 298 Джонсон (Johnson S.) 24, 275 Деннис (Dennis J. В.) 24 Дойг (Doig A.) 290 Дорфман (Dorfman R.) 23 Дрейфус (Dreyfus S.) 24, 219, 414 Зойтендейк (Zoutendijk G.) 24, 316, 318, 320, 337 Канторович Л. В. 437 Кун (Kuhn H. W.) 23, 195, 200, 204 Курант (Courant R.) 88 Лемке (Lemke С.) 23, 140, 318 Лэнд (Land A. H.) 281, 290 ') При составлении указателя т в конце каждой главы. — Прим. ред. Манне (Маппе А.) 24, 277, 489 Марковиц (Markowitz H.) 23, 24 226, 277 Миллер (Miller С. Е.) 23, 140 Модильяни (Modigliani F.) 467 Моисеев H. H. 460 Мут (Muth J.) 467 Розен (Rosen J. В.) 24, 322, 338 Симон (Simon H. A.) 467, 469 Таккер (Tucker A. W.) 23, 195, 200, 204 Тейл (Theil H.) 469 Уайтин (Whitin T. М.) 190 Удзава (Uzawa H.) 23 Фалкерсон (Fulkerson D.) 24, 275 Фергюсон (Ferguson A. R.) 178 Франк (Frank M.) 23, 241, 251 Фример (Freimer M.) 219 Хартли (Hartley H. 0.) 148 Хаутеккер (Houthakker H.) 23, 244 Хедли (Hadley G.) 190 Хилдрет (Hildreth С.) 23 Ховард (Howard R.) 476 Хольт (Holt С.) 467 Чарнс (Charnes A.) 23, 140, 229, 295 Черноусько Ф. Л. 460 Эпен (d'Epenoux F.) 489 Эрроу (Arrow К. J.) 23, 353, 354 Юдин Д. Б. 11, 29 учитывалась литература, приведенная ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Базис 35 ортонормированный 53 Вариационное исчисление 422, 456, 460 Вектор (строка, столбец) 32 — вводимый в базис 42 — выпуклая комбинация 50 — единичный 33 — исключаемый из базиса 42 — искусственный 43 — лексикографически положитель- ный 282 — линейная зависимость 35 — нормальный к гиперплоскости 50 — нормированный 53 — ортогональность 34 — порождение пространства 35 — скалярное произведение 34 — сложение 33 — умножение на скаляр 33 — характеристический (собственный) 53 Вероятность перехода 472 Вольфа способ в квадратичном про- граммировании 230 Выпуклая комбинация векторов 50 Гессиан 58 Гилдрета метод в квадратичном про- граммировании 242 Гиперплоскость 50 — касательная 60 — опорная 52 Гиперповерхность 56 — вогнутая 97 — выпуклая 97 Гиперсфера 50 Гомори алгоритм для полностью це- лочисленных задач 276 Гомори алгоритм для частично цело- численных задач 287 Градиент 57 Градиентные методы 302 — — в задачах с линейными огра- ничениями 303 программирова- программиро- - — — линейном нии 333 - — — нелинейном вании 337, 340 - — метод Эрроу—Гурвица 353 - — проективный метод 332 Двойственность в задаче максимиза- ции 87 — — программировании квадратич- ном 246 — — — линейном 48 Детерминированные задачи последо- вательного принятия решений 387 — — теории создания запасов 391 Динамическое программирование 15, 359 Евклидово пространство 34 Задача детерминированная см. Де- терминированные задачи — квадратичного программирования 13, 220 — математического программирова- ния линейная 10, 11 — — — нелинейная 11, 12 — оптимизации классическая 13 — приближенная см. Приближенная задача — стохастическая см. . Стохастичес- кие задачи — с условиями очередности 266 — с фиксированными затратами 151 498 Предметный указатель Задача с фиксированными затратами сведение к целочисленной 255 — целочисленная 14, 254 Задача о бродячем торговце 271 — — выборе направления наиболь- шего изменения функции 93 — — загрузке корабля 375, 434 — — замене оборудования 409, 454 — — запасах 184, 391, 414, 430, 495 — — использовании рабочей силы 387 — — капитальных вложениях 273, 297 — — линии сборки 298, 299 — — надежности 428 — — нефтяной компании 190 — — планировании выпуска авто- мобилей 476 — — — — конденсаторов 432 — — — производства 194, 2J8, 430, 460 — — производителе продуктов 179, 261, 434 — — производстве деталей 71, 180, 301 — — — насосов 432 — — — продукции с переналадкой оборудования 156 — — подводной лодке 173, 372 — — раскрашивании карты 298 — — распределении допусков 376 — — — поставок 375 — — — самолетов по маршрутам 178 — — — средств на производство и рекламу 423 — — реализации проектов и кален- дарном планировании 266 — — снабжении морской базы 428 — — торговце одеждой 88, 172 — — — хлебом 153 — расписания 299, 300 — транспортная t69, 174, 434, 447, 452 Линейные правила принятия реше- ний 467 Линия уровня 55 Максимум абсолютный (глобальный) 16, 65 — относительный (локальный) 16 — сильный 66 — слабый 66 — условный 73 Марковские процессы 472 Матрица, определения и основные свойства 29—31 — конгруэнтная 53 — неособенная 37 — обратная 37 — ортогональная 53 — подобная 53 — расширенная система уравнений 38 — характеристический вектор, поли- ном, число 53 Минимум 66 — условный 73 Многогранник выпуклый 52 Множество точечное, определение и основные свойства 49—52 Множители Лагранжа 76, 79 — — в линейном программировании 94 — — интерпретация 85 — — использование для уменьше- ния размерности 449 Неравенство Шварца (Буняковского) 34 Нормаль к поверхности 60 Ньютона метод отыскания стацио- нарной точки 69 Квадратичная форма 54 Квадратичные затраты 462 Конечные альтернативы в линейном программировании 260 Куна — Таккера теорема 203 — условия регулярности ограниче- ний 205, 206 Кусочно-линейная аппроксимация 117 Линейная зависимость 35 Линейное преобразование 39 Образ 39 Ограничения 10 — линейные 11 — сепарабельные 13 Октант неотрицательный 51 Ортогональное дополнение подпро- странства 36 Отображение 39 Отрезок 50 Параметры состояния 371 Переменная (базисная, небазисная) 39 Предметный указатель 499 Переменная вспомогательная 40 — искусственная 43 — истинная 43 — управляющая 170, 371 Поверхность уровня 60 Подпространство 36 Политика 371 Полупространство (замкнутое, крытое) 50 Порождение пространства вектора- ми 35 Приближенная задача в б-форме 129 — — в ^-форме 117 Принцип декомпозиции 140 — оптимальности Р. Беллмана 372 Проблема размерности 436, 439, 441, 446, 490 Производная функции 56 — частная 56, 57 — в направлении г 58 Прямая 50 Ребро множества 52 Решение базисное 39 — — вырожденное 39 — в прямом направлении 387 — в обратном направлении 387 — допустимое 16, 41 — тривиальное 39 ^/•-политика 406 Седловая точка 88, 195 — — глобальная 196 — — — достаточные условия 199 — — — необходимые условия 198 Сечение 275 — Гомори 277, 290 — Данцига 277 — Марковица и Манне 277 Симплекс-метод 40—44 — таблица 44 Симплекс-метод двойственный 49 Симплекс-метод модифицированный 44—47 — — — таблица 45 Система координат 33 — — ортогональная 34 Средняя стоимость детерминирован- ная 191 — — из-за неопределенности 191 Стационарная точка 69 — — при наличии ограничений 308 Стохастические задачи математиче- ского программирования 171 Стохастические задачи многошаговые 184 — — одношаговые со случайностя- ми в спросе 172 — — — — — в технологических ко- эффициентах 180 — — последовательного принятия решений 414, 460, 469 — — теории создания запасов 414 Стратегия 478 — смешанная 478 — чистая 479 Теорема о неявных функциях 62 — Тейлора 59 — Куна—Таккера 203 Точка множества внутренняя 50 — — граничная 50 — — крайняя 51 Точка перегиба функции 68 Точки множества смежные 52 Транспортная задача 159, 174, 434, 447, 452 Управление 371 Управляющая переменная 170, 371 Условия регулярности ограничений Куна—Таккера 205, 206 Фактор производства 266 Фаркаша лемма 209 Фиксированные затраты 151 Франк и Вольфа метод в квадратич- ном программировании 241 Функциональное уравнение 405 Функция 55 — вогнутая 97 — — максимум и минимум 108 — выпуклая 97 — — максимум и минимум 105, 106 — Лагранжа 76, 79 — — интерпретация 86 — линейная 56 — непрерывная 56 — сложная 58 — состояния 374 — строго вогнутая 98 — — выпуклая 98 — целевая, см. Целевая функция Характеристический вектор 53 — полином 53 — уравнение 53 — число 52 600 Предметный указатель Хартли метод максимизации 148 Чарнса способ в квадратичном про- Хаутеккера метод в квадратичном граммировании 229 программировании 244 , Экстремум функции 74 Целевая функция 10 — — необходимые условия 74 — — линейная 11 Эрроу—Гурвнца градиентный метод — — нелинейная 12 353 — — параметрическая 230 — — сепарабельная 12 Целочисленные задачи линейного Якобиан 62 программирования 14, 254 Цикл 407 ОГЛАВЛЕНИЕ : От редактора перевода ................... 5 Предисловие ......,,.,,..........,. у Глава 1. Введение .......................... 9 I 1.1. Задачи математического программирования ........ 9 1.2. Типы задач .................. И | 1.3. Вычислительные методы ................. 15 | 1.4. Трудности, порождаемые нелинейноетями ......... 16 1.5. Краткий исторический обзор ............... 23 1.6. Обзор дальнейшего содержания .............. 25 Литература ...................... 26 Упражнения ...................... 27 Глава 2. Необходимый математический аппарат ........... 29 2. 1. Матрицы и векторы ................ 29 2. 2. Системы линейных уравнений .............. 38 2. 3. Линейное программирование ............... 40 2. 4. Модифицированный симплекс-метод ........... 44 2. 5. Двойственность ..................... 48 2. 6. Выпуклые множества ............... 49 2. 7. Характеристические числа и квадратичные формы .... 52 2. 8. Функция п переменных .................. 55 2. 9. Частные производные .... .............. 56 2.10. Теорема Тейлора ..................... 59 2.11. Теорема о неявных функциях .............. 60 Литература ...................... 63 Упражнения ...................... 63 Глава 3. Классические методы оптимизации и свойства выпуклых функций ......................... 65 3. 1. Введение ....................... 65 3. 2. Максимум и минимум при отсутствии ограничений .... 65 502 i Оглавление 3. 3. Пример ........................ 3. 4. Условный максимум и минимум. Множители Лагранжа 3. 5. Общий случай ................. 3. 6. Случай неотрицательных переменных и ограничений в форме неравенств ..................... 3. 7. Интерпретация множителей Лагранжа ........ 3. 8. Интерпретация функции Лагранжа; двойственность .... 3. 9. Примеры . . ...... ................ 3.10. Выпуклые и вогнутые функции ............. 3.11. Примеры ........................ 1 3.12. Максимум и минимум выпуклых и вогнутых функций . . . 1 Литература ............................ 1 Упражнения ........................... 1 Глава 4. Приближенные методы решения задач с сепарабельными функциями ...................... 1 4. 1. Введение ....................... 1 4. 2. Построение приближенной задачи и определение локаль- ного максимума ..................... 1 4. 3. Пример ...... ................... 1 4. 4. Другая формулировка .................. 1 4. 5. Замена переменных для получения сепарабельности . . . . 1 4. 6. Случаи, когда локальный экстремум одновременно являет- ся глобальным ..................... 1 4. 7. Использование принципа декомпозиции при наличии огра- ничений сверху ..................... 1 4. 8. Пример ........................ 1 4. 9. Метод Хартли для максимизации функции на выпуклом множестве при сепарабельных ограничениях ...... 1 4.10. Задача с фиксированными затратами ...... . . . . 1 4.11. Пример задачи с фиксированными затратами ...... 1 4.12. Транспортные задачи с выпуклыми сепарабельньщи це- левыми функциями ................ 1 Литература ............................ 1' Упражнения ..................... ...... 1 Глава 5. Стохастическое программирование ............. 1 5.1. Введение ................... ..... 1 5.2. Одношаговые стохастические задачи со случайностями, по- являющимися только в спросе .............. 1 5.3. Одношаговые стохастические задачи со случайными вели- чинами в технологических коэффициентах ......... 1 Оглавление 5.4. Многошаговые стохастические задачи ......... 5.5. Средняя стоимость из-за неопределенности ....... 5.6. Замена случайных параметров их средними значениями . Литература ................ ........... Упражнения .......................... Глава 6. Теория Куна—Танкера .................. 6.1. Введение . ............. ......... 6.2. Необходимые и достаточные условия для седловой точк! 6.3. Теорема Куна—Таккера ................. 6.4. Установление необходимых условий методом Куна—Таккерг 6.5. Один частный случай и пример ............. Литература ........................... Упражнения .......................... Глава 7. Квадратичное программирование ............. 7.1. Введение ....................... 7.2. Решение задачи квадратичного программирования с отри- цательно определенной формой x'Dx .......... 7.3. Окончание процесса в случае отрицательной определенно- сти формы x'Dx ................. 7.4. Способ Чарнса для случая неположительности квадратич- ной формы ....................... 7.5. Способ Вольфа, использующий параметризацию целевой функции ................... 7.6. Пример ......................... 7.7. Другие методы решения задач квадратичного програм- мирования ....................... 7.8. Двойственность в квадратичном программировании . . . . Литература .... ........................ Упражнения ........................... Глава 8. Целочисленное линейное программирование ......... 8. 1. Введение ........................ 8. 2. Задача с фиксированными затратами .......... 8. 3. Определение глобального экстремума для приближенной задачи в б-форме ................ 8. 4. Определение глобального экстремума для приближенной задачи в Х-форме .................... 8. 5. Представление некоторых поверхностей ........ 8. 6. Конечные альтернативы ................ 8. 7. Задачи с условиями очередности ............ 8. 8. Реализация проектов и календарное планирование .... 504 Оглавление 8. 9. Задача о бродячем торговце ............... S 8.10. Капитальные вложения фирмы .............. 2 8.11. Решение целочисленных задач линейного программирова- ния ..................... S 8.12. Алгоритм Гомори для решения полностью целочислен- ной задачи ........................ 2 8.13. Доказательство конечности ............. .2 8.14. Алгоритм для решения частично целочисленных задач . . . S 8.15. Доказательство конечности для случая частично целочислен- ной задачи ........................ S 8.16. Пример ........................ S Литература ............................ S Упражнения ........................... S Глава 9. Градиентные методы .................... S 9. 1. Введение ........................ i 9. 2. Случай линейных ограничений .............. i 9. 3. Сходимость итерационного процесса ........... 9. 4. Геометрическая интерпретация ............. 9. 5. Численное определение г .............. i 9. 6. Градиентный проективный метод ............ 9. 7. Геометрические иллюстрации . . ............ 9. 8. Сравнение методов определения г .......... 9. 9. Решение задач линейного программирования с использо- ванием градиентных методов .............. 9.10. Задачи с нелинейными ограничениями .......... 9.11. Градиентный метод для задач с сепарабельными ограни- чениями ........................ 9.12. Определение допустимого решения ........'.... 9.13. Пример ......................... 9.14. Некоторые дополнительные замечания о сходимости . . . 9.15. Градиентный метод Эрроу—Гурвица для вогнутого про- граммирования ..................... Литература .... ........................ Упражнения ..................... ...... Глава 10. Динамическое программирование I ............. 10. 1. Введение ....................... 10. 2. Сущность вычислительного метода ......... 10. 3.. Эффективность метода ................. 10. 4. Основные свойства динамического программирования . . 10. 5. Численный пример ................... '> Оглавление 10. 6. Несколько других практических примеров ....... 10. 7. Случай непрерывности переменных . ........ 10. 8. Случай выпуклости или вогнутости функций fj(x,} . . . 10. 9. Детерминированные задачи последовательного принятия решений ........................ 10.10. Простая задача об использовании рабочей силы . . . . . 10.11. Детерминированные задачи создания запасов ...... 10.12. Случай, когда f,(X}, у,} — вогнутые функции ...... 10.13. Пример ........................ 10.14. Функциональные уравнения для систем с бесконечным числом шагов ...................... 10.15. Явное решение функционального уравнения ....... 10.16. Задачи о замене оборудования ............. 10.17. Стохастические задачи последовательного принятия ре- шений ......................... 10.18. Стохастическая динамическая модель в теории создания запасов ........................ 10.19. Динамическое программирование и вариационное исчис- ление ..... .................... 10.20. Программы для решения задач методом динамического программирования на вычислительных машинах . . . . Литература ............................ Упражнения ........................... а в а 11. Динамическое программирование II ............ 11. 1. Введение ....................... 11. 2. Задача распределения с двумя ограничениями ..... 11. 3. Задача с двумя переменными управления ........ 11. 4. Случаи непрерывности переменных ........... 11. 5. Сравнение линейного и динамического программирования , 11. 6. Использование динамического программирования в тран- спортных задачах с двумя пунктами производства . . . . . 11. 7. Использование множителей Лагранжа для уменьшения размерности ....................... 11.8. Замена оборудования ..................; 11. 9. Некоторые задачи вариационного исчисления ....... 11.10. Планирование выпуска продукции и задачи теории соз- дания запасов ...................... t 11.11. Случай квадратичных затрат .............. t 11.12. Доказательство эквивалентности стохастической и детер- минированной задач в случае квадратичных затрат . . . ^ 11.13. Стохастические задачи последовательного принятия реше- ний с бесконечным планируемым промежутком и марков- ские процессы ...................... 4 506 Оглавление 11.14. Пример ........................ 476 11.15. Оптимальность чистых стратегий ............ 478 11.16. Сведение к задаче линейного программирования .... 480 11.17. Двойственная задача линейного программирования . . . 483 11.18. Дополнительные обсуждения ... ........... 487 11.19. Заключительные замечания о проблеме размерности . . . 490 Литература ............................ 491 Упражнения ........................... 492 Именной указатель .............. ...... 496 Предметный указатель .................. 497 Дж. Хедли Нелинейное и динамическое программирование Редактор В. В. Величенко Художник Л. Л. Бессонов Художественный редактор Б. И. Шаповалов Технический редактор Л. М, Харьковская Сдано в производство 23/V 1967 г. Подписано к печати 22/XI 1967 г. Бумага кама мелован. GOxSO'/is^S.SS. бум. л. 31,75 усл. печ. л., Уч.-изд. л. 29,45. Изд. № 1/4075 Цена 2 р. 30 коп. Зак. 735 ИЗДАТЕЛЬСТВО »МИР» Москва, 1-й Рижский пер., 2 Ленинградская типография Л« 2 имени Евгении Соколовой Главполиграфпрома Комитета по печати при Совете Министров СССР Измайловский проспект, 29