- А б р'а м о в Л- М., Капустин В. Ф. Математическое программирование. Л., Изд-во Ленингр. унта, 1976., 184 с. ,
Книга написана на основе кури, Который читается на отделении экономической кибернетики экономического факультета Ленинградского университета. В ней содержатся теоретические основы выпуклого программирования и алгоритмы решения линейных задач. Рассматриваются некоторые экономические ситуации, которые формализуются как задачи математического программирования. Строгость, изложения сочетается с возможностью освоения вычислительных алгоритмов без предварительного разбора их обоснования и изучения теоретического материала.
Книга рассчитана на студентов экономических вузов и факультетов, а также специалистов экономических служб предприятий и ведомств. Ил. — 12,. библиогр. — 36 назв.
ПРЕДИСЛОВИЕ л
Настоящая книга является первой частью учебного пособия по курсу математического программирования, который читается на отделении экономической кибернетики экономического факультета Ленинградского университета. В ней додержится общая теория, точнее, теория выпуклого программирования, и алгоритмы решения линейных задач. Обсуждаются вопросы, связанные с экономико-математическим моделированием. Во вторую часть учебного пособия предполагается включить алгоритмы решения задач выпуклого, квадратичного и дискретного программирования и некоторые смежные вопросы.
Можно привести довольно много хороших книг и статей («л далеко не полный список помещен в конце данного издания), которые полезно использовать как учебные пособия или охра-.:" вочные материалы по отдельным разделам курса математического программирования. Однако, некоторые из них (например, [9, 21, 22, 31]) уже давно являются библиографической редкостью, другие [24] изданы малым тиражом и практически недоступны студентам, наконец, часть книг просто не соответствует программе, методике и традициям преподавания курса математического программирования в Ленинградском университете. Все перечисленное вызвало необходимость предоставить студентам рабочий материал для изучения названного курса. Именно с этой целью и написана данная книга. '
Весь материал книги (вероятно, кроме § 3 второй главы) знаком специалистам. Поэтому ссылки tна первоисточники почти • не приводятся. Исключением являются^ параграф, посвященный экономико-математическому моделированию, и, те места, где формулируются без доказательств нетривиальные утверждения и теоремы. ч . • •'.
Что^касаетея формы изложения, то она не является традиционной. Мы далеки от мысли считать ее бесспорной. Это, скорее, один из вариантов, имеющий право на существование,. отвечающий педагогическому опыту и вкусам авторов. Отметши наиболее важные моменты.
1. В книге рассмотрены теория выпуклого программирова- ; ния и выпуклая теория дврйственностй; теории квадратичного линейного программирования и линейная двойственность пол$4 чены как частные случаи общей теории..
2. Мы рассматриваем алгоритмы не только как последей^а-тельные вычислительные и логические предписания, приводйщие к соответствующим результатам, но и как конструкции, х0*врые
можно использовать для эффективного доказательства не» рых утверждений, теорем и т. п.
3. Алгоритмы не доведены до машинной реализации. О лишь могут служить основой для написания машинных п грамм; принципы и методы их составления не являются rip Метом изучения курса математического программирования, щ скольку, как нам кажется, это сузило бы круг читателей стоящей книги и увело бы их в сторону от непосредственны проблем решения задач оптимизации.
4. Мы старались писать книгу таким образом, чтобы можр было изолированно изучать теорию и вычислительные методь в первую очередь знакомить читателя (даже неподготовленного с вычислительными аспектами методов и лишь после этого ^ с идеями и точным обоснованием. В какой мере это удалось** судить читателю.
Одним из недостатков книги (мы надеемся, что их окажет| не слишком много) является отсутствие в ее тексте задач J упражнений, что объясняется как необходимостью эконом| места, так и предполагаемым изданием задачника, согласовав ного с настоящим курсом. С другой стороны, мы так част предлагаем самостоятельные исследования, что это вполне м< жет компенсировать отсутствие задач и упражнений.
Казалось бы естественным в соответствии со структура третьей главы рассмотреть общие алгоритмы решения задй выпуклого программирования и лишь потом, как их конкретВ зацию, алгоритмы решения задач линейного программирование Однако такой подход встречает технические трудности, п<| скольку алгоритмы решения задач линейного программирована используются при построении общих алгоритмов для задач вь| пуклого, квадратичного и дискретного . программирование Поэтому мы и поместили алгоритмы решения задач линейног программирования в первой ^части книги, оставив общие алг ритмы для второй ее части.
, В конце книги приведено незначительное количество изд иий. В случае необходимости список литературы можно^попо нить, обратившись .к библиографии книг приведенного'списк
О системе обозначений и ссылок. Нумерация формул повт ряется с начала каждого параграфа. Ссылки на формулы пределах параграфа осуществляются обычным образом, ссыл в пределах главы производятся с указанием номера параграф а ссылки на формулы параграфов других глав — с указаний номера главы. Пункты параграфа нумеруются двумя цифрам; первая соответствует номеру параграфа, вторая — HOMCJ пункта. Ссылки на пункты других глав производятся с ука| нием номера соответствующей главы.
.Мы благодарим-Л. М. Брэгмана и И. В. Романовского, <1 суждавших с нами тематику книги и различные варианты виси.
ОГЛА-ВЛЕНИЕ
Т'лава 1. Некоторые сведения из алгебры и выпуклого анализа . г S
§ 1. Алгебра . , . , . . . ...... - * — "
| 2, Выпуклые множества а /?" . х , . . ' . . . . ' - 8-
§ 3. Выпуклые функции . . ... . . . ,-- 11
Глава 2. Экстремальные задачи . ....... 13-
§ 1, Экстремальнее задачи. Формальная классификация. . . — § 2. -Экономико-математическое моделирование. Примеры эк-
стремальных задач . . ....... 15
3. Эквивалентные экстремальные задачи ...... 27
4. Примеры эквивалентных экстремальных задач ... 23
'Глава 3. Критерии оптимальности . ...... 3S
*г
§ 1. Критерии оптимальности при условиях дифференцируемости —
1" § 2. Теорема' Куна *- Таккера . . " . . . . . 46
§ 3. Двойственность в математическом дрогранмировании . . 54
Глава 4. Основные вычислительные методы линейного, программиро-
вания • .. '•':-, . . . ..... ^ , 65
§ 1. Предварительные замечания ..... —
§ 2. Симплекс-метод . . ........ 6?
§ 3. Симплекс-метод — вычислительная - схема, связанная с пре-
образованием обратных матриц , ч. . . / ^ . 75 $ 4, Метод решения задачи линейного программирования' ,с
' * ограниченными сверху переменными . ' .* . . . -'83
\ § 5. Двойственный симплекс-метод . '"..-. . .... 93
§6. Градиентный, метод . . . . . -... . . .. , 106
§ 7. Вырожденность. Решение вырожденных задач . • «, . .:П6
Глава 5. Специальные классы задач линейного программирования и •
методы их решения :-..- . : . ' '. ., *. . -, ,„ 120
§ 1. Специальные классы задач линейного программирования, Проблемы генерирования их .условий и вычислительной ин-
формации. Симуляция допустимых планов. . , . , —
§ 2. Блочная задача. Метод декомпозиции Дашщгдг^Вулф'а . 126
§ 3. Транспортные сети и транспортные задачи . , , . 189 ' § 4. Транепортная задача' с ограниченными сверху переменны-
•^ ми (сетевая постановка). Метод потенциалов . Ч: . 145 § 5. Транспортная задача в матричной постановке. Венгерский
метод .' •'•'.-. . . . . -.'. '. -..:-" . . . 156
Глава & Параметрические задачи . . . * . . - . 163
, § 1. Параметрические задачи линейного- Я}Лграмм1фрвааия . — §2. Алгоритм решения параметрической задачи 'линейного про-
граимирования с параметром в функционале . . . 166 § 3. Алгоритм решения параметрической задачи линейного про-
/ • граммирования с параметром в еграниченвях , .• . 174
Указатель литературы . ч . . . . . . . . . 181
