В последние 20,—: 25 лет в прикладной математике большое внимание уделяется новому классу задач оптимизации, за&шрчаю-щихся в нахождении в заданной области точек,,наибольшего или наименьшего значения некоторой функции, зависящей от большого числа переменных. Это так называемые задачи математического программирования, возникающие в самых разнообразных областях человеческой деятельности и прежде всего в экономических исследованиях, в практике планирования и организации производства.
Математическое программирование принадлежит сейчас к числу наиболее интенсивно используемых дисциплин прикладной математики, и потому соответствующий куре в том или ином объеме включен в учебные планы почти всех вузов.
Предлагаемая книга написана в связи с изучением в университетах курса «Математическое программирование» и является, по существу, первой попыткой создания учебного пособия по этой дисциплине. Необходимость в таком пособии ощущается очень остро. '••'• ' ;
Имеющейся монографической литературы по математическому программированию пока недостаточно (возможно, это не относится только к такому его разделу, как линейное программирование). . •-.::,.
Настоящее учебное пособие написано на основе опыта чтения лекций и проведения практических занятий по математическому программированию на кафедре экономической кибернетики Киевского государственного университета. Цель пособия — ознакомить студентов с существующими методами оптимизации и их применением при решении практических задач. Учитывая достаточно серьезный уровень математической подготовки студентов университета, мы значительное место отвели теоретическим вопросам методов оптимизации и, в частности, наиболее эффективных приближенных методов решения задач нелинейного программирования. Почти все теоретические положения проиллюстрированы числовыми примерами, а излагаемые методы доведены до вычислительных схем, ориентированных на ЭВМ. Во введении дается понятие ° математическом моделировании' и приводятся математические
модели некоторых практических задач, укладывающихся в рамки математического программирования.
Материал разбит на три части, которые" соответствуют основным разделам математического программирования — линейному, дискретному и нелинейному программированию а состоит из шести глав. В первой главе изложены общие вопросы линейного программирования; дается обоснование симплекс-метода и его модификаций. Во второй главе рассматриваются некоторые специальные классы задач линейного программирования — транспортные задачи, задача о Назначениях, задачи с блочной структурой, задачи с параметром — и даны методы их решения. В главе третьей рассмотрены линейные задачи целочисленного типа и основные методы их решения — различные методы отсечения, приближенные методы, аддитивный алгоритм. В четвертой главе изложены основные комбинаторные методы решения задач дискретного программирования— метод последовательного анализа вариантов, метод ветвей и границ.
Пятая глава посвящена общим вопросам нелинейного программирования. В ней приведены основные свойства выпуклых множеств, выпуклых функций и теоретические результаты выпуклого программирования, изложен метод множителей Лагранжа. В шестой главе изложены численные методы нелинейного программирования: различные градиентные методы, методы штрафных функций, методы возможных направлений, а также методы решения задач квадратичного и сепарабельного программирования. Здесь же рассмотрены некоторые модели задач стохастического программирования и изложен метод обобщенного стохастического градиента.
Материал расположен в порядке возрастания сложности используемого математического аппарата. Учитывая, что линейное программирование читается в вузах с различным уровнем общематематической подготовки студентов (в отличие от нелинейного программирования, которое читается, как правило, в вузах с достаточно большим объемом общематематических дисциплин), мы излагали линейное программирование с более подробными объяснениями, чем другие разделы книги.
В целом пособие написано в соответствии с требованиями ныне действующей программы по курсу «Математическое программирование», для студентов специальности «Экономическая кибернетика» факультета кибернетики Киевского государственного университета. Книга также может быть полезной студентам математических, технических и экономических специальностей вузов.
При написании пособия мы стремились, насколько это было возможно, учесть современные достижения бурно развивающейся теории оптимизации. Нами использовалась монографическая литература, приведенная в списке литературы, а также журнальные, статьи Ю. М. Ермольева, И. И. Еремина, Б. Т. Поляка, Н. 3. Шора и других авторов.
Авторский коллектив выражает благодарность академику д Н УССР В. С. Михалевичу (Институт кибернетики АН УССР) ^ коллективу кафедры экономической кибернетики Донецкого государственного университета (зав. кафедрой доц. В. Н. Амитан) за пенные замечания, которые способствовали улучшению пособия.
Авторы будут признательны читателям за критические замечания и пожелания, которые просим присылать по адресу; 252054, К нее, 54, Гоголевская, 7, Головное издательство издательского объединения «Вища школа», редакция литературы по математике и физике. • , .
Авторы
СОДЕРЖАНИЕ
Предисловие............................ 3
Введение <;........................... 6
Часть 1. Линейное 'программирование • ~
Глава 1. Общая задача линейиогр программирования ' •§•'"'•' 1. Различные" амбивалентные'''формы задали линейного программирования.............................1 24
в 2. Геометрический смысл задачи линейного программирования при п =
= 2, 3. . ;..;:. ... . . . . . ..... ',;.....•:.'.. ..... 32
§ 3. Основные свойства задачи линейного программирования. Предварительное понятие о симплекс-методе............... 39
-§ 4. Обоснование симплекС'Метода для невырожденной задачи линейного
программирования . . ............. . .... ... 50
§ 5. Алгоритм симплекс-метода. Симплекс-таблицы. ......... 69
§ 6. Симплекс-метод в общем случае. Возможность зацикливания процесса и его предупреждение. , . . . .}, . . ........ . . и . .•,. 76
§ 7. Отыскание исходного базиса................... 80
§ 8. Модифицированный симплекс-алгоритм.; ........ . , .... 94
§ 9. Двойственность в линейном программировании........:. . 102
§ 10. Переменные двойственной задачи и функция Лагранжа для задачи
линейного программирования..................111
§ 11. Двойственный симплекс-метод (метод последовательнргр уточнения
оценок).....................'. ".' . ."'. ... 125
Глава 2. Специальные задачи и методы линейного программирования
, §. 1. Транспортные задачи и методы их решения........... . 134
§* 2. Задача о назначениях...................... 158
§ 3. Задачи линейного программирования с блочной структурой .... 164
§ 4. Задачи линейного программирования с параметром......... 196
Часть II. Дискретное программирование
Глава .3. Линейные целочисленные задачи
§ 1. Постановки экономических задач, приводящие к требованию цело-
численности ........................... 210
§ 2. Методы этеечения........................ 215
§ 3. Приближенные методы....................... 239
§ 4. Аддитивный алгоритм.........,............ 244
Глава 4. Комбинаторные методы в дискретном программировании
§ 1.' Постановка задач........................ 251
§ 2. Метод последовательного анализа вариантов........... 253
§ 3. Метод ветвей и границ..................... 262
Часть III. Нелинейное программирование
Глава 5. Общие вопросы нелинейного программирования
§ 1. Общая задача математического программирования. ....... 275
§ 2. Свойства выпуклых множеств и выпуклых функций....... 280
§ 3. Обобщенное правило множителей Лагранжа. ....... 292
§ 4. Выпуклое программирование................... 300
Глава 6. Численные методы нелинейного программирования
§ 1. Градиентные методы...................... , 307
§ 2. Методы штрафных функций .<..-................. 331
? 3. Методы возможных направлений................. 336
§ 4. Квадратичное программирование................. 343
§ 5. Сепарабельные задачи...................... 348
§ 6 Задачи и методы стохастического программирования....... 361
Литература ',
Цена: 150руб.
